New answers tagged algorithm
1
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 ...
2
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 ...
8
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 ...
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 ...
3
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.
14
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 ...
12
To be concrete, exact Bayesian inference is (often) intractable (that is, not polynomially computable) because it involves the computation of an integral over a range of real (or even floating-point) numbers, which is not a polynomial-time operation. More precisely, for example, if you want to find the parameters $\mathbf{\theta} \in \Theta$ of a model given ...
Top 50 recent answers are included
