What are examples of promising AI/ML techniques that are computationally intractable?

Question

To produce tangible results in the field of AI/ML, one must take theoretical results under the lens of computational complexity.

Indeed, minimax effectively solves any two-person "board game" with win/loss conditions, but the algorithm quickly becomes untenable for games of large enough size, so it's practically useless asides from toy problems.

In fact, this issue seems to cut at the heart of intelligence itself: the Frame Problem highlights this by observing that any "intelligent" agent that operates under logical axioms must somehow deal with the explosive growth of computational complexity.

So, we need to deal with computational complexity: but that doesn't mean researchers must limit themselves with practical concerns. In the past, multilayered perceptrons were thought to be intractable (I think), and thus we couldn't evaluate their utility until recently. I've heard that Bayesian techniques are conceptually elegant, but they become computationally intractable once your dataset becomes large, and thus we usually use variational methods to compute the posterior, instead of naively using the exact solution.

I'm looking for more examples like this: What are examples of promising (or neat/interesting) AI/ML techniques that are computationally intractable (or uncomputable)?

Answer 1

AIXI is a Bayesian, non-Markov, reinforcement learning and artificial general intelligence agent that is incomputable, given the involved incomputable Kolmogorov complexity. However, there are approximations of AIXI, such as AIXItl, described in Universal Artificial Intelligence: Universal Artificial Intelligence: Sequential Decisions based on Algorithmic Probability (2005), by Marcus Hutter (the original author of AIXI), and MC-AIXI-CTW (which stands for Monte Carlo AIXI Context-Tree Weighting). Here is a Python implementation of MC-AIXI-CTW: https://github.com/gkassel/pyaixi.

Answer 2

Exact Bayesian inference is (often) intractable (i.e. there is no closed-form solution, or numerical approximations are also computationally expensive) because it involves the computation of an integral over a range of real (or even floating-point) numbers, which can be intractable.

More precisely, for example, if you want to find the parameters $\mathbf{\theta} \in \Theta$ of a model given some data $D$, then Bayesian inference is just the application of the Bayes' theorem

\begin{align} p(\mathbf{\theta} \mid D) &= \frac{p(D \mid \mathbf{\theta}) p(\mathbf{\theta})}{p(D)} \\ &= \frac{p(D \mid \mathbf{\theta}) p(\mathbf{\theta})}{\int_{\Theta} p(D \mid \mathbf{\theta}^\prime) p(\mathbf{\theta}^\prime) d \mathbf{\theta}^\prime} \\ &= \frac{p(D \mid \mathbf{\theta}) p(\mathbf{\theta})}{\int_{\Theta} p(D, \mathbf{\theta}^\prime) d \mathbf{\theta}^\prime } \tag{1}\label{1} \end{align}

where $p(\mathbf{\theta} \mid D)$ is the posterior (which is what you want to find or compute), $p(D \mid \mathbf{\theta})$ is the likelihood of your data given the (fixed) parameters $\mathbf{\theta}$, $p(\mathbf{\theta})$ is the prior and $p(D) = \int_{\Theta} p(D \mid \mathbf{\theta}^\prime) p(\mathbf{\theta}^\prime) d \mathbf{\theta}^\prime$ is the evidence of the data (which is an integral given that $\mathbf{\theta}$ is assumed to be a continuous random variable), which is intractable because the integral is over all possible values of $\mathbf{\theta}$, that is, ${\Theta}$. If all terms in \ref{1} were tractable (polynomially computable), then, given more data $D$, you could iteratively keep on updating your posterior (which becomes your prior on the next iteration), and exact Bayesian inference would become tractable.

The variational Bayesian approach casts the problem of inferring $p(\mathbf{\theta} \mid D)$ (which requires the computation of the intractable evidence term) as an optimization problem, which approximately finds the posterior, more precisely, it approximates the intractable posterior, $p(\mathbf{\theta} \mid D)$, with a tractable one, $q(\mathbf{\theta} \mid D)$ (the variational distribution). For example, the important variational auto-encoder (VAEs) paper (which did not introduce the variational Bayesian approach) uses the variational Bayesian approach to approximate a posterior in the context of neural networks (that represent distributions), so that existing machine (or deep) learning techniques (that is, gradient descent with back-propagation) can be used to learn the parameters of a model.

The variational Bayesian approach (VBA) becomes always more appealing in machine learning. For example, Bayesian neural networks (which can partially solve some of the inherent problems of non-Bayesian neural networks) are usually inspired by the results reported in the VAE paper, which shows the feasibility of the VBA in the context of deep learning.

Answer 3

This question gets at a really interesting fact about AI research in general: AI is hard.

In fact, almost every AI problem is computationally hard (typically NP-Hard, or #P-Hard). This means that most new areas of AI research starts out by characterizing some problem that is intractable, and proposing an algorithm that technically works, but is too slow to be useful. However, that's not the whole story. Usually AI researchers then proceed to develop tractable techniques according to one of two schools:

• Algorithms that usually work in practice, and are always fast, but are not completely correct.
• Algorithms that are always correct, and are usually fast, but are sometimes very slow, or only work on specific kinds of sub-problem.

Take together, these let AI address most problems. For example:

• Search was developed as a general purpose AI technique for solving planning and logic problems. The first algorithm, called the general problem solver, always worked, but was extremely slow. Eventually, we developed heuristic guided search techniques like A*, domain specific tricks like GraphPlan, and stochastic search techniques like Monte-Carlo Tree Search.
• Bayesian Learning (or Bayesian Inference) has been known since the 1800's, but it is known to involve either the computation of intractable integrals, or the creation of exponentially sized discrete tables, making it NP-Hard. A very simple algorithm involves applying brute force and enumerating all of the options, but this is too slow. Eventually, we developed techniques like Gibbs Sampling (that is always fast, and usually right), or Variable Elimination (that is always right, and usually fast). Today we can solve most problems of this kind very well.
• Reasoning about language was thought to be very hard (see the Frame Problem), because there are an infinite number of possible sentences, and an infinite number of possible contexts they could be used in. Exact approaches based on rules did not work. Eventually we developed probabilistic approaches like Hidden Markov Models and Deep Neural Networks, that aren't certain to work, but work so well in practice that language problems are, if not completely solve, getting very close.
  • Games of chance, like Poker, were thought to be impossible, because they are #P-Hard to complete exactly (this is harder than NP-Hard). There will probably never be an exact algorithm for these. In spite of this, techniques like CFR+ can derive solutions that are so close to exactly perfect that you would need to play for decades against them to tell the difference.

So, what's still hard?

• Inferring the structure of a Bayesian network. This is closely related to the problem of causality. It's #P-Hard, but we don't currently have any good algorithms to even do this approximately very well. This is an active area of research.
• Picking a machine learning algorithm to use for an arbitrary problem. The No Free Lunch theorem tells us this is not possible in general, but it seems like we ought to be able to do it pretty well in practice.
• More to come...?

Answer 4

The logical induction algorithm can make predictions about whether mathematical statements are true or false, which are eventually consistent; e.g. if A is true, its probability will eventually reach 1; if B implies C then C's probability will eventually reach or exceed B's; the probability of D will eventually be the inverse of not(D); the probabilities of E and F will eventually reach or exceed that of E AND F; etc.

It can also give consistent predictions about itself, e.g. "the logical induction algorithm will predict the probability of X to be Y at timestep T", whilst avoiding paradoxes like the liar's paradox.

Answer 5

Hutter's "fastest and shortest algorithm for all well-defined problems" is the ultimate just-in-time compiler. It runs a given program and, in parallel, searches for proofs that some other program is equivalent but faster. The running program is restarted at exponentially-spaced intervals; if a faster program has been found, that is started instead. The running time of this algorithm is of the same order as the fastest provably-equivalent algorithm, plus a constant $O(1)$ term (the time taken to find the proof, which doesn't dependent on the input size). For example, it will run Bubble Sort in at most $O(n~log (n))$) time, by finding a proof that it's equivalent to such a fast algorithm (like Merge Sort) then switching to that algorithm.

Hutter's algorithm is similar to the best ahead-of-time compilers, known as super-optimisers. They search through all possible programs, starting with the smallest/fastest, until they find one equivalent to the given code. These are actually in use right now, but are only practical for programs that are a few (machine code) instructions long. The LLVM compiler contains some "peephole optimisations" (i.e. find/replace templates) that were found by a super-optimiser a few years ago. Note that super-optimisation should not be confused with super-compilation (a rather general optimisation, which is not optimal and involves no search).

Answer 6

In general, partially-observable Markov decision processes (POMDPs) are also computationally intractable to solve exactly. However, there are several approximations methods. See, for example, Value-Function Approximations for Partially Observable Markov Decision Processes (2000) by Milos Hauskrecht.

Answer 7

Levin's search algorithm is a general method of function inversion. Many AI tasks are of this sort, e.g. given a cost or reward function (object -> cost or object -> reward), its inverse (cost -> object or reward -> object) would find an object with the given cost/reward; we could ask this inverse function for an object with low cost or high reward.

Levin's algorithm is optimal iff the given function is a "black box" with no known pattern in its output. For example, if a small change in the input produces a small change in the output, Levin search wouldn't be optimal; instead we could use hill climbing or some other gradient method.

Levin's algorithm looks for the function's inverse by running all possible programs in parallel, assigning exponentially more time to shorter programs. Whenever a program halts, we check whether its output is the desired inverse (i.e. whether givenProgram(outputOfHaltedProgram) = desiredOutput, e.g. whether cost(outputOfHaltedProgram) = low).

This way "simpler" guesses at the inverse are made first; where we define the simplicity (AKA "Levin complexity") of a value by looking through all programs $p$ which generate that value, and minimising the sum of: $p$'s length (in bits) plus the logarithm of $p$'s running time (in steps). If we ignored running time we would get Kolmogorov complexity, which is theoretically nicer but is incomputable (we don't know when to give up waiting for short non-halting programs, due to the Halting Problem). Levin complexity is computable, since we can give up waiting for those loops once they've taken exponentially-many steps as a longer solution (e.g. once we've spent $T$ steps waiting for a possible loop of length $N$, we can start trying programs that are $N+1$ bits long for $T/2$ steps).

The running time of Levin Search is of the same order as the simplest such inverse-value-generating program. However, this is misleading, since the fraction of steps allocated to running any particular program $p$ is $1/2^{complexity(p)}$, so this constant factor will be slowing down the computation of the inverse too. There is also overhead associated with context-switching between all of these programs.

The FAST algorithm does the same job as Levin Search, in the same time, but avoids the overhead of context-switching between an infinite number parallel programs. Instead it runs one program at a time, cuts it off if it hasn't halted within an appropriate number of steps, then retries for twice as many steps later on. The GUESS algorithm is also equivalent, but chooses programs at random; the expected runtime is the same, but there's no need to keep track of loop counters like in FAST, plus it can be run on parallel hardware without having to coordinate anything (whilst still avoiding the infinite parallelism of the original).

Levin search is currently impractical in its original setting of searching through general-purpose, Turing-complete programs. It can be useful in less general domains, e.g. searching through the space of hyper-parameters or other domain-specific, configuration-like "programs".