Informally speaking, Solomonoff Induction provides an Bayesian optimal way to predict the next symbol from observed symbol sequences $S_1S_2S_3...S_n$ where each $S_i$ belongs to a finite symbol set $\Sigma$. To get the posterior probability distribution of the next symbol, we make a weighted average prediction of all Turing Machines that produces first $n$ symbols. For each Turing Machine $M$ within consideration, the weight would be inverse exponential of "complexity" of that Turing Machine.

$$p(M) = 2^{-L(M)}$$

Where $L(M)$ is the description length of $M$ in context of an universal Turing Machine $U$.

If we replace:

  • finite symbol set $\Sigma$ to continuous domain $D$, such as $R^n$.
  • Symbol sequence $S_i$ to discrete time series, for example $x_1x_2x_3...x_n$ where $x_i \in D$
  • Turing Machine $M$ to discrete time dynamical system, for example $x_{n+1} = f(x_n)$, which is mapping $R^n \to R^n$

The Bayesian inference would still work in this case, however we have to redefine the complexity measure $p(f) \to [0, \infty)$, which is probability density function of $f$.

Question: Is there any work or related theory that extends the complexity measure elegantly to dynamical systems?

I would also be interested in results for continuous dynamical systems, in terms of differential equations.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.