Answers.Body: <p><a href="https://ai.stackexchange.com/a/10377/2444">AIXI</a> is a Bayesian, non-Markov, reinforcement learning and artificial general intelligence agent that is <a href="https://en.wikipedia.org/wiki/Computable_function#Uncomputable_functions_and_unsolvable_problems" rel="noreferrer">incomputable</a>, given the involved <a href="https://en.wikipedia.org/wiki/Kolmogorov_complexity#Uncomputability_of_Kolmogorov_complexity" rel="noreferrer">incomputable Kolmogorov complexity</a>. However, there are approximations of AIXI, such as AIXItl, described in <a href="http://hutter1.net/ai/uaibook.htm" rel="noreferrer">Universal Artificial Intelligence:  Universal Artificial Intelligence: Sequential Decisions based on Algorithmic Probability</a> (2005), by Marcus Hutter (the original author of AIXI), and <a href="https://arxiv.org/abs/0909.0801" rel="noreferrer">MC-AIXI-CTW</a> (which stands for Monte Carlo AIXI Context-Tree Weighting). Here is a Python implementation of MC-AIXI-CTW: <a href="https://github.com/gkassel/pyaixi" rel="noreferrer">https://github.com/gkassel/pyaixi</a>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-10-21T00:15:49.743Z
Answers.LastActivityDate: 2019-10-21T00:15:49.743Z
Answers.UserDisplayName: nbro
Answers.Body: <p><em>Exact</em> Bayesian inference is (often) <a href="https://en.wikipedia.org/wiki/Computational_complexity_theory#Intractability" rel="nofollow noreferrer"><em>intractable</em></a> (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.</p>
  <p>More precisely, for example, if you want to find the parameters <span class="math-container">$\mathbf{\theta} \in \Theta$</span> of a model given some data <span class="math-container">$D$</span>, then <a href="https://en.wikipedia.org/wiki/Bayesian_inference" rel="nofollow noreferrer">Bayesian inference is just the application of the Bayes' theorem</a></p>
  <p><span class="math-container">\begin{align}
  p(\mathbf{\theta} \mid D) 
  &amp;= \frac{p(D \mid \mathbf{\theta}) p(\mathbf{\theta})}{p(D)} \\
  &amp;= \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} \\
  &amp;= \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}</span></p>
  <p>where <span class="math-container">$p(\mathbf{\theta} \mid D)$</span> is the posterior (which is what you want to find or compute), <span class="math-container">$p(D \mid \mathbf{\theta})$</span> is the likelihood of your data given the (fixed) parameters <span class="math-container">$\mathbf{\theta}$</span>, <span class="math-container">$p(\mathbf{\theta})$</span> is the prior and <span class="math-container">$p(D) = \int_{\Theta} p(D \mid \mathbf{\theta}^\prime) p(\mathbf{\theta}^\prime) d \mathbf{\theta}^\prime$</span> is the evidence of the data (which is an integral given that <span class="math-container">$\mathbf{\theta}$</span> is assumed to be a continuous random variable), which is intractable because the integral is over all possible values of <span class="math-container">$\mathbf{\theta}$</span>, that is, <span class="math-container">${\Theta}$</span>. If all terms in \ref{1} were tractable (polynomially computable), then, given more data <span class="math-container">$D$</span>, you could iteratively keep on updating your posterior (which becomes your prior on the next iteration), and exact Bayesian inference would become tractable.</p>
  <p>The <a href="https://en.wikipedia.org/wiki/Variational_Bayesian_methods" rel="nofollow noreferrer">variational Bayesian approach</a> casts the problem of inferring <span class="math-container">$p(\mathbf{\theta} \mid D)$</span> (which requires the computation of the intractable <em>evidence</em> term) as an optimization problem, which <em>approximately</em> finds the posterior, more precisely, it approximates the intractable posterior, <span class="math-container">$p(\mathbf{\theta} \mid D)$</span>, with a tractable one, <span class="math-container">$q(\mathbf{\theta} \mid D)$</span> (the <em>variational distribution</em>). For example, the important <a href="https://arxiv.org/abs/1312.6114" rel="nofollow noreferrer">variational auto-encoder (VAEs)</a> 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.</p>
  <p>The variational Bayesian approach (VBA) becomes always more appealing in machine learning. For example, <a href="https://arxiv.org/abs/1505.05424" rel="nofollow noreferrer">Bayesian neural networks</a> (which can partially solve some of the inherent problems of non-Bayesian neural networks) are usually inspired by the results reported in <a href="https://arxiv.org/abs/1312.6114" rel="nofollow noreferrer">the VAE paper</a>, which shows the feasibility of the VBA in the context of deep learning.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-10-20T21:24:27.673Z
Answers.LastActivityDate: 2021-01-19T14:26:19.770Z
Answers.LastEditDate: 2021-01-19T14:26:19.770Z
Answers.UserDisplayName: nbro
Answers.Body: <p>This question gets at a really interesting fact about AI research in general: <strong>AI is hard</strong>.</p>
  
  <p>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 <strong>not the whole story</strong>. Usually AI researchers then proceed to develop <em>tractable</em> techniques according to one of two schools:</p>
  
  <ul>
  <li>Algorithms that usually work in practice, and are always fast, but are not completely correct.</li>
  <li>Algorithms that are always correct, and are usually fast, but are sometimes very slow, or only work on specific kinds of sub-problem.</li>
  </ul>
  
  <p>Take together, these let AI address most problems. For example:</p>
  
  <ul>
  <li><a href="https://en.wikipedia.org/wiki/Graph_traversal" rel="noreferrer">Search</a> was developed as a general purpose AI technique for solving <a href="https://en.wikipedia.org/wiki/Automated_planning_and_scheduling" rel="noreferrer">planning</a> and <a href="https://en.wikipedia.org/wiki/Automated_theorem_proving" rel="noreferrer">logic</a> problems. The first algorithm, called the <a href="https://en.wikipedia.org/wiki/General_Problem_Solver" rel="noreferrer">general problem solver</a>, always worked, but was extremely slow. Eventually, we developed heuristic guided search techniques like <a href="https://en.wikipedia.org/wiki/A*_search_algorithm" rel="noreferrer">A*</a>, domain specific tricks like <a href="https://en.wikipedia.org/wiki/Graphplan" rel="noreferrer">GraphPlan</a>, and stochastic search techniques like <a href="https://en.wikipedia.org/wiki/Monte_Carlo_tree_search" rel="noreferrer">Monte-Carlo Tree Search</a>.</li>
  <li>Bayesian Learning (or <a href="https://en.wikipedia.org/wiki/Bayesian_inference" rel="noreferrer">Bayesian Inference</a>) 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 <a href="https://en.wikipedia.org/wiki/NP-hardness" rel="noreferrer">NP-Hard</a>. A very simple algorithm involves applying brute force and enumerating all of the options, but this is too slow. Eventually, we developed techniques like <a href="https://en.wikipedia.org/wiki/Gibbs_sampling" rel="noreferrer">Gibbs Sampling</a> (that is always fast, and usually right), or <a href="https://en.wikipedia.org/wiki/Variable_elimination" rel="noreferrer">Variable Elimination</a> (that is always right, and usually fast). Today we can solve most problems of this kind very well.</li>
  <li>Reasoning about language was thought to be very hard (see the <a href="https://en.wikipedia.org/wiki/Frame_problem" rel="noreferrer">Frame Problem</a>), 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 <a href="https://en.wikipedia.org/wiki/Hidden_Markov_model" rel="noreferrer">Hidden Markov Models</a> and <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.248.4448&amp;rep=rep1&amp;type=pdf" rel="noreferrer">Deep Neural Networks</a>, that aren't certain to work, but work so well in practice that language problems are, if not completely solve, getting <a href="https://translate.google.com/" rel="noreferrer">very close</a>.
  
  <ul>
  <li>Games of chance, like Poker, were thought to be impossible, because they are <a href="https://en.wikipedia.org/wiki/%E2%99%AFP-complete" rel="noreferrer">#P-Hard</a> to complete exactly (this is <em>harder</em> than NP-Hard). There will probably never be an exact algorithm for these. In spite of this, techniques like <a href="https://poker.cs.ualberta.ca/publications/2015-ijcai-cfrplus.pdf" rel="noreferrer">CFR+</a> can derive solutions that are so close to exactly perfect that you would need to play for decades against them to tell the difference.</li>
  </ul></li>
  </ul>
  
  <p>So, what's <strong>still</strong> hard?</p>
  
  <ul>
  <li><a href="https://www.hindawi.com/journals/complexity/2018/1591878/" rel="noreferrer">Inferring</a> the <em>structure</em> of a Bayesian network. This is closely related to the problem of <em>causality</em>. 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.</li>
  <li>Picking a machine learning algorithm to use for an arbitrary problem. The <a href="https://ai.stackexchange.com/questions/15650/what-are-the-implications-of-the-no-free-lunch-theorem-for-machine-learning/15651#15651">No Free Lunch theorem</a> tells us this is not possible in general, but it seems like we ought to be able to do it pretty well in practice.</li>
  <li>More to come...?</li>
  </ul>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-19T14:17:16.060Z
Answers.Text: I don't consider myself an expert in Bayesian inference, although I've done my master's thesis on _Bayesian neural networks_, but note that MC-based approaches to approximately solve the Bayesian inference problem in the context of Bayesian neural networks (the main contributor to this specific topic was Radford M. Neal) are not very "successful", i.e. they typically only work well for small-scale problems/models. As far as I understand and recall, convergence is the main problem for this approach. This is the idea I have after having done, a few months ago, a little bit of literature review.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-10-21T19:04:00.377Z
Answers.LastActivityDate: 2019-10-22T14:49:18.230Z
Answers.LastEditDate: 2019-10-22T14:49:18.230Z
Answers.UserDisplayName: John Doucette
Answers.Body: <p>The <a href="https://intelligence.org/2016/09/12/new-paper-logical-induction" rel="noreferrer">logical induction algorithm</a> can make predictions about whether mathematical statements are true or false, which are eventually consistent; e.g. if <code>A</code> is true, its probability will eventually reach 1; if <code>B</code> implies <code>C</code> then <code>C</code>'s probability will eventually reach or exceed <code>B</code>'s; the probability of <code>D</code> will eventually be the inverse of <code>not(D)</code>; the probabilities of <code>E</code> and <code>F</code> will eventually reach or exceed that of <code>E AND F</code>; etc.</p>
  
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-10-21T19:22:06.527Z
Answers.Text: ohh, this is very cool! MIRI stuff is very hard and i am forced by dumbness to ignore much of their work, but thank you for the source and a short description
Answers.UserDisplayName: k.c. sayz 'k.c sayz'
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-10-21T17:13:14.770Z
Answers.LastActivityDate: 2019-10-21T17:13:14.770Z
Answers.UserDisplayName: Warbo
Answers.Body: <p>Hutter's <a href="https://www.semanticscholar.org/paper/The-Fastest-and-Shortest-Algorithm-for-All-Problems-Hutter/acf58b7dd2b902fa519db8f7cf8af2e3294d56ee" rel="noreferrer">"fastest and shortest algorithm for all well-defined problems"</a> is the ultimate <a href="https://en.wikipedia.org/wiki/Just_in_time_compilation" rel="noreferrer">just-in-time compiler</a>. 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 <span class="math-container">$O(1)$</span> term (the time taken to find the proof, which doesn't dependent on the input size). For example, it will run <a href="https://en.wikipedia.org/wiki/Bubble_sort" rel="noreferrer">Bubble Sort</a> in at most <span class="math-container">$O(n~log (n))$</span>) time, by finding a proof that it's equivalent to such a fast algorithm (like <a href="https://en.wikipedia.org/wiki/Merge_sort" rel="noreferrer">Merge Sort</a>) then switching to that algorithm.</p>
  
  <p>Hutter's algorithm is similar to the best <a href="https://en.wikipedia.org/wiki/Compiler" rel="noreferrer">ahead-of-time compilers</a>, known as <a href="https://en.wikipedia.org/wiki/Superoptimization" rel="noreferrer">super-optimisers</a>. 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 <a href="https://stackoverflow.com/questions/9067545/what-is-supercompilation">super-compilation</a> (a rather general optimisation, which is not optimal and involves no search).</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-10-22T04:50:25.913Z
Answers.LastActivityDate: 2019-10-22T04:50:25.913Z
Answers.UserDisplayName: Warbo
Answers.Body: <p><a href="http://www.scholarpedia.org/article/Universal_search" rel="nofollow noreferrer">Levin's search algorithm</a> is a general method of function inversion. Many AI tasks are of this sort, e.g. given a cost or reward function (<code>object -&gt; cost</code> or <code>object -&gt; reward</code>), its inverse (<code>cost -&gt; object</code> or <code>reward -&gt; object</code>) would find an object with the given cost/reward; we could ask this inverse function for an object with low cost or high reward.</p>
  
  <p>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.</p>
  
  <p>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 <code>givenProgram(outputOfHaltedProgram) = desiredOutput</code>, e.g. whether <code>cost(outputOfHaltedProgram) = low</code>).</p>
  
  <p>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 <span class="math-container">$p$</span> which generate that value, and minimising the sum of: <span class="math-container">$p$</span>'s length (in bits) plus the logarithm of <span class="math-container">$p$</span>'s running time (in steps). If we ignored running time we would get <a href="https://en.wikipedia.org/wiki/Kolmogorov_complexity" rel="nofollow noreferrer">Kolmogorov complexity</a>, which is theoretically nicer but is incomputable (we don't know when to give up waiting for short non-halting programs, due to the <a href="https://en.wikipedia.org/wiki/Halting_problem" rel="nofollow noreferrer">Halting Problem</a>). 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 <span class="math-container">$T$</span> steps waiting for a possible loop of length <span class="math-container">$N$</span>, we can start trying programs that are <span class="math-container">$N+1$</span> bits long for <span class="math-container">$T/2$</span> steps).</p>
  
  <p>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 <span class="math-container">$p$</span> is <span class="math-container">$1/2^{complexity(p)}$</span>, 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.</p>
  
  <p>The <a href="http://people.idsia.ch/~juergen/toesv2/node28.html" rel="nofollow noreferrer">FAST algorithm</a> 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 <a href="http://people.idsia.ch/~juergen/toesv2/node31.html" rel="nofollow noreferrer">GUESS algorithm</a> 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).</p>
  
  <p>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".</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-10-22T05:36:06.480Z
Answers.LastActivityDate: 2019-10-22T14:41:27.890Z
Answers.LastEditDate: 2019-10-22T14:41:27.890Z
Answers.UserDisplayName: Warbo
Answers.Body: <p>In general, <a href="https://arxiv.org/pdf/1301.2308.pdf" rel="nofollow noreferrer">partially-observable Markov decision processes (POMDPs) are also computationally intractable to solve exactly</a>. However, there are <a href="https://en.wikipedia.org/wiki/Partially_observable_Markov_decision_process#Approximate_POMDP_solutions" rel="nofollow noreferrer">several approximations methods</a>. See, for example, <a href="https://arxiv.org/abs/1106.0234" rel="nofollow noreferrer">Value-Function Approximations for Partially Observable Markov Decision Processes</a> (2000) by Milos Hauskrecht.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-10-21T00:30:36.727Z
Answers.LastActivityDate: 2019-10-21T00:30:36.727Z
Answers.UserDisplayName: nbro
Body: <p>To produce tangible results in the field of AI/ML, one must take theoretical results under the lens of computational complexity.</p>
  <p>Indeed, minimax effectively solves any two-person &quot;board game&quot; 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.</p>
  <p>In fact, this issue seems to cut at the heart of intelligence itself: the <a href="https://plato.stanford.edu/entries/frame-problem/" rel="noreferrer"><em>Frame Problem</em></a> highlights this by observing that any &quot;intelligent&quot; agent that operates under logical axioms must somehow deal with the explosive growth of computational complexity.</p>
  <p>So, we need to deal with <em>computational complexity</em>: 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.</p>
  <p>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)?</p>
  
Tags: <machine-learning><reference-request><computational-complexity><intractability>
Title: What are examples of promising AI/ML techniques that are computationally intractable?
UserDisplayName: k.c. sayz 'k.c sayz'
ThreadText: # What are examples of promising AI/ML techniques that are computationally intractable?
  
  (Asked by: username_0 on 2019-10-20)
  
  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*](https://plato.stanford.edu/entries/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)?
  
  **Tags:** machine-learning, reference-request, computational-complexity, intractability
  
  ---
  
  ## 7 answers
  
  ### Answer by username_1 on 2019-10-21. Score: 16
  
  [AIXI](https://ai.stackexchange.com/a/10377/2444) is a Bayesian, non-Markov, reinforcement learning and artificial general intelligence agent that is [incomputable](https://en.wikipedia.org/wiki/Computable_function#Uncomputable_functions_and_unsolvable_problems), given the involved [incomputable Kolmogorov complexity](https://en.wikipedia.org/wiki/Kolmogorov_complexity#Uncomputability_of_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](http://hutter1.net/ai/uaibook.htm) (2005), by Marcus Hutter (the original author of AIXI), and [MC-AIXI-CTW](https://arxiv.org/abs/0909.0801) (which stands for Monte Carlo AIXI Context-Tree Weighting). Here is a Python implementation of MC-AIXI-CTW: <https://github.com/gkassel/pyaixi>.
  
  
  ---
  
  ### Answer by username_1 on 2019-10-20. Score: 15
  
  *Exact* Bayesian inference is (often) [*intractable*](https://en.wikipedia.org/wiki/Computational_complexity_theory#Intractability) (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](https://en.wikipedia.org/wiki/Bayesian_inference)
  
  \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](https://en.wikipedia.org/wiki/Variational_Bayesian_methods) 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)](https://arxiv.org/abs/1312.6114) 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](https://arxiv.org/abs/1505.05424) (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](https://arxiv.org/abs/1312.6114), which shows the feasibility of the VBA in the context of deep learning.
  
  
  ---
  
  ### Answer by username_2 on 2019-10-21. Score: 12
  
  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](https://en.wikipedia.org/wiki/Graph_traversal) was developed as a general purpose AI technique for solving [planning](https://en.wikipedia.org/wiki/Automated_planning_and_scheduling) and [logic](https://en.wikipedia.org/wiki/Automated_theorem_proving) problems. The first algorithm, called the [general problem solver](https://en.wikipedia.org/wiki/General_Problem_Solver), always worked, but was extremely slow. Eventually, we developed heuristic guided search techniques like [A\*](https://en.wikipedia.org/wiki/A*_search_algorithm), domain specific tricks like [GraphPlan](https://en.wikipedia.org/wiki/Graphplan), and stochastic search techniques like [Monte-Carlo Tree Search](https://en.wikipedia.org/wiki/Monte_Carlo_tree_search).
  * Bayesian Learning (or [Bayesian Inference](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/NP-hardness). 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](https://en.wikipedia.org/wiki/Gibbs_sampling) (that is always fast, and usually right), or [Variable Elimination](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/Hidden_Markov_model) and [Deep Neural Networks](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.248.4448&rep=rep1&type=pdf), that aren't certain to work, but work so well in practice that language problems are, if not completely solve, getting [very close](https://translate.google.com/).
    + Games of chance, like Poker, were thought to be impossible, because they are [#P-Hard](https://en.wikipedia.org/wiki/%E2%99%AFP-complete) 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+](https://poker.cs.ualberta.ca/publications/2015-ijcai-cfrplus.pdf) 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](https://www.hindawi.com/journals/complexity/2018/1591878/) 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](https://ai.stackexchange.com/questions/15650/what-are-the-implications-of-the-no-free-lunch-theorem-for-machine-learning/15651#15651) 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...?
  
  > **Comments:**
  > **username_1**: I don't consider myself an expert in Bayesian inference, although I've done my master's thesis on _Bayesian neural networks_, but note that MC-based approaches to approximately solve the Bayesian inference problem in the context of Bayesian neural networks (the main contributor to this specific topic was Radford M. Neal) are not very "successful", i.e. they typically only work well for small-scale problems/models. As far as I understand and recall, convergence is the main problem for this approach. This is the idea I have after having done, a few months ago, a little bit of literature review.  
  
  ---
  
  ### Answer by username_3 on 2019-10-21. Score: 5
  
  The [logical induction algorithm](https://intelligence.org/2016/09/12/new-paper-logical-induction) 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.
  
  > **Comments:**
  > **username_0**: ohh, this is very cool! MIRI stuff is very hard and i am forced by dumbness to ignore much of their work, but thank you for the source and a short description  
  
  ---
  
  ### Answer by username_3 on 2019-10-22. Score: 5
  
  Hutter's ["fastest and shortest algorithm for all well-defined problems"](https://www.semanticscholar.org/paper/The-Fastest-and-Shortest-Algorithm-for-All-Problems-Hutter/acf58b7dd2b902fa519db8f7cf8af2e3294d56ee) is the ultimate [just-in-time compiler](https://en.wikipedia.org/wiki/Just_in_time_compilation). 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](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/Merge_sort)) then switching to that algorithm.
  
  Hutter's algorithm is similar to the best [ahead-of-time compilers](https://en.wikipedia.org/wiki/Compiler), known as [super-optimisers](https://en.wikipedia.org/wiki/Superoptimization). 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](https://stackoverflow.com/questions/9067545/what-is-supercompilation) (a rather general optimisation, which is not optimal and involves no search).
  
  
  ---
  
  ### Answer by username_3 on 2019-10-22. Score: 4
  
  [Levin's search algorithm](http://www.scholarpedia.org/article/Universal_search) 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](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/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](http://people.idsia.ch/~juergen/toesv2/node28.html) 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](http://people.idsia.ch/~juergen/toesv2/node31.html) 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".
  
  
  ---
  
  ### Answer by username_1 on 2019-10-21. Score: 3
  
  In general, [partially-observable Markov decision processes (POMDPs) are also computationally intractable to solve exactly](https://arxiv.org/pdf/1301.2308.pdf). However, there are [several approximations methods](https://en.wikipedia.org/wiki/Partially_observable_Markov_decision_process#Approximate_POMDP_solutions). See, for example, [Value-Function Approximations for Partially Observable Markov Decision Processes](https://arxiv.org/abs/1106.0234) (2000) by Milos Hauskrecht.
  
  
  ---
  
  