Computational complexity results in Neural Nets

1 Computational cost of explaining complex reasoning

Intuitively, something might be, should be difficult, computationally about explaining the reasoning of a large neural network. Surely simpler things cannot explain more complex things?

As an extreme example, we might run into incompleteness results. (Prove the consistency of the following system of axioms…) I can believe such extreme esoterica would not be relevant in practice, but could problems close to those arise in practice? TBC.

2 Incoming

• Sean Trott, Perceptrons, XOR, and the first “AI winter” is a decent summary of the history of connectionist approaches dying out for a while in AI.

  I haven’t read Minsky and Papert (1972) which is commonly credited with burying NNs in favour of GOFAI for a while, but I gather the argument is essentially geometric rather than computational. I think the parallels can be made though (heh).

• Language Generation in the Limit (Kleinberg and Mullainathan 2024) looks interesting.

  Cheng Soon Ong described it as a

  talk by Jon Kleinberg on language generation being easier than language identification. He mentions an interesting tension between hallucination and mode collapse.

• Neural algorithmic reasoning

• Unveiling Transformers with LEGO (Zhang et al. 2022)

• Blazek claims his non-gradient-based neural networks implement predicate logic directly and yet are tractable which would be interesting to look into (Blazek and Lin 2021, 2020; Blazek, Venkatesh, and Lin 2021). This sounds like a reboot of the GOFAI project; I wonder what would be the secret sauce that would give the author hope? Would it be enough to persuade me also? I don’t put much prior stock in this plan.

3 References