15

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

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{\...


10

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 ...


5

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 ...


4

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 ...


3

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 ...


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.


3

If you are a freelancer, when a client asks to create a website we can easily measure how much the total cost is needed based on the requirements of the client. (the backend, UI/UX design, features, etc.). We can even measure the estimated time of completion. This is only the case when the full scope and design of the site is a well understood and ...


2

What is the time complexity? The time complexity of an algorithm is the number of basic operations, such as multiplications and summations, that the algorithm performs. The time complexity is usually expressed as a function of the input's size $n$ (but this does not always have to be the case: for instance, you can express the time complexity as a function ...


1

Regarding your first point, it depends on what neural network you would like to use, the sensor temporal resolution, and the capabilities of the embedded system. You can figure out the number of operations required for a forward pass of your network, then when combined with the internal clock of the embedded system, you can calculate the approximate time it ...


1

I was struggling with the same question. This is what I came up with after thinking it through. With depth-first-search, you backtrack to a node that is a non-expanded child of your parent (or the parent of the parent when your parent has no more non-expanded children (and so on going up the tree)). So the space complexity is limited by your ancestors and ...


1

It's not completely clear from your question, but it looks like you want to prove that exact inference in a Bayesian Network is both NP-Hard and P-Hard. It appears that you have proven that it is NP-Hard, but are unsure how to show that it is also P-Hard. This is more of a TCS question than an AI question, but shouldn't be too difficult. You just need to ...


Only top voted, non community-wiki answers of a minimum length are eligible