Perfect compression is equivalent to finding the Kolmogorov complexity of a string. That's incomputable and so perfect compression is beyond any algorithm, even a "generally intelligent" algorithm. Generality in compression might increase an algorithms effectiveness but there's no proof this generality is equivalent to generality in dealing with the world humans deal with.
Not "perfect compression" but any compression. Perfect compression would be equivalent to perfectly digested experiences i.e. that anything that could be deduced from a collection of sensations had been deduced. The link above explains it well.
> In 2000, Hutter proved that finding the optimal behavior of a rational agent is equivalent to compressing its observations. Essentially he proved Occam's Razor, the simplest answer is usually the correct answer. The proof applies to any goal-seeking agent in any unknown environment which can be simulated by a computer. For example, an agent could be a person or computer whose goal is to accumulate money or some other reward signal in an unknown world.
> Formally, the agent and environment are a pair of interacting Turing machines that pass messages back and forth at each time step. In addition, the environment outputs a reward signal (a number) to the agent, and the agent's goal is to maximize the accumulated reward. What Hutter proved is that the optimal behavior of an agent is to guess that the environment is controlled by the shortest program that is consistent with all of the interaction observed so far.
> The problem of finding this program known as AIXI. AIXI implies a solution to optimal algorithmic compression: coding a string as the shortest program that outputs it. The problem is worth studying because it is hard. The general problem is not computable, although Hutter proved that if we assume time bounds t and space bounds l on the environment, then this restricted problem, known as AIXItl, can be solved in O(t2l) time.
edit: I mean, it makes intuitive sense. To have perfect compression of a string would be to have extracted all of the order out of it, every possible pattern, and every possible pattern of patterns etc. It's obviously impossible to know when you've gotten to that point.
Hutter proved that finding the optimal behavior of a rational agent is equivalent to compressing its observations. Essentially he proved Occam's Razor, the simplest answer is usually the correct answer.
But "rational agent" isn't a standard object mathematicians work with. This person no doubt defined an object they called a "rational agent" and then proved things about it. That's still just plausible reasoning relative to the many informal and incompatible concepts of "rational agent" out-there, not to mention models of environment.
> But "rational agent" isn't a standard object mathematicians work with
Yes it is; it's a standard definition used across many fields, including parts of mathematics (e.g. game theory and decision theory) https://en.wikipedia.org/wiki/Rational_agent
Rational agent as general concept is common in many places. But rational agent doesn't have a single mathematical definition in the fashion of a group or a ring. You should notice that the definition of rational agent found in game theory doesn't imply any kind of prediction or computation, what the OP was claiming about "rational agents"
> what the OP was claiming about "rational agents"
Since prediction and compression are isomorphic, OP's point is that compression algorithms are relevant to these decision processes. This actually references the work of Marcus Hutter, who added an extra axiom to these established definitions: that agents and environments are (Turing) computable.
This lets us apply techniques from Algorithmic Information Theory, like Solomonoff Induction, and prove that the optimal policy is to:
- Compress all of the observations received so far, into the smallest program possible (for a predetermined Universal Turing Machine). Note that this is uncomputable, since it would tell us its Kolmogorov complexity!
- Predict the outcome of our possible actions, by simulating them against that program
- Choose the action whose simulation leads to the highest reward
Sure it's not an algebraic object; but it's still a well-defined mathematical notion.
Nah, it's just an informal concept. A game theoretic "rational agent" in general isn't assumed to have any limitations on it's computing ability, for example.
[Game theory is] trying to solve a partially-observable Markov decision problem
Not according to standard texts on game theory. In fact, this is just can't be true in any usual interpretation. POMDPs are "single agent" problems whereas game theory nearly always deals with two competing players/agents each assume attempting to optimize their returns - it's the difference between a single optimum and a saddle point, maximum and minimax.
This actually references the work of Marcus Hutter, who added an extra axiom to these established definitions: that agents and environments are (Turing) computable.
This is my point. You can't "add an extra axiom" and be referencing a standard mathematical object at the same time.
Optimisation algorithms like simulated annealing require some representation to optimise. The most general representation is a computer program, in which case genetic programming might be a better fit :)
That's a factor to some extent, but if you're sticking with lossless then the better your compression gets the more your remaining data is dominated by noise.
that's why you need two brains, one to losslessly compress through symbolic expressiveness and another to lossily compress by generating noise like the incompressible noise
http://mattmahoney.net/dc/rationale.html
...which gives way to the theory of mind known as compressionism:
http://ceur-ws.org/Vol-1419/paper0045.pdf