For example > you could have some sequence where the computation time of the n-th > bit take n^1000 computation cycles. There is only one pattern and > it's highly compressible as it has a pretty short algorithm however > there is no way you'll ever learn what the pattern is.
To say a bit more/correct myself/repeat what you said/repeat myself: Every long sequence where the number of computation cycles needed for computation the nth element is not smaller than a constant C is not practically compressible. The amount of information that the nth element depends on is then also limited by some constant. If computation time grows like 2^n, n^1000, n or log(n), computation will become unfeasible in the long run. For log(n) that might be a very long time, but still eventually impossible. This seems to me to be a more useful notion of compressibility than Kolmogorov's: feasible compressibility. If the nth element just depends on the near past (say the last 5 elements or so) and the number of computations is bounded by some not very high constant finding a good prediction function is easy (with neural networks at least). But that is not the case in general. There may have been cardinal events in the past that need to be remembered in order to predict well. In that case computation can also be feasible. Of course if the determining events are too far in the past it's impossible to find the causal connection. The trick is to identify those cardinal events, and then remember them, completely or just a part. For this I use a recurrent neural network system (Abstraction/Prediction). It is trained on prediction success. There is always a fixed number of calculations based on a fixed amount of information. Abstraction (input, context) -> new context Prediction (input ,context) -> predicted new input Alas, a known problem with recurrent networks is that with backpropagation of errors the contributions of the far past to the error gradient go to zero too fast. (I remember, I may have stated this problem wrong) A module in my system on its own can therefor only predict well on the basis of the near past. That near past and the near future must be feasibly compressible. Whether the rest is does not matter for this method. A method help to solve (live with) this problem: The state of the recurrent neural network (context) can be seen as an abstract description of the state the (perceived) sequence is in. The recent past is compressed into it (it can be said to simulate the Markov property), all relevant information is kept because of the training on prediction. irrelevant information is filtered out. It can be seen as a classification of the near past sequence (and the expected near future), which I mentioned in earlier mails. Sutton calls such state descriptions that help to predict predictive representations of state, PRS. These states can themselves be predicted, by a higher level module. To get grip on a farther past than the base level can, this module must run 'slower', i.e. not try to predict every PRS every time. It must predict the state of the PSR every 2, 10 or so cycles of the base level. Otherwise it will have the same time horizon as the base level. A more natural way seems to me: predict what state the PRS is in the next time a prediction failure (of the base level) happens. The PRS can be seen as containing all the information about the future (also future PRSes) until a prediction failure. Apparantly the environment then switches to some new unforseen behaviour. Until then the environment did not contain any new information; it can be compressed to the PRS (and the Abstraction and Prediction neural networks which are fixed during run time). The higher level module predicts the new PRS of the base level. It thus predicts in which abstract class the sequence will fall when it 'switches' to a new behaviour. If it is successful it can be said to have a farther predictive horizon than the base module. The drawback is that the predictions are stated less precise, in terms of a class of sequences, the PRS (if the environment is so complex that information had to be filtered out). Will it work? Only if the environment (and therefor the sequence) is simple enough. The perceived sequence must be feasibly compressible in the abstract representations of the PRS (of the base level), in the near past and the near future. The horizons are farther away than for the base module. After that a third module can be build on the second to predict the PRS of the second module, and so on. If the environment allows it, the future will be predicted further and further, but also vaguer and vaguer, or maybe better said, in more general terms (in complex but still feasible environments). The input of the top level will be the cause of many different sequences. This method seems to me to make long term planning possible in feasibly compressible environments in general terms. The longer the term of planning the less precise (more abstract) a plan can be stated. Arnoud Michel ------- To unsubscribe, change your address, or temporarily deactivate your subscription, please go to http://v2.listbox.com/member/[EMAIL PROTECTED]
