ECCC-Report TR01-043https://eccc.weizmann.ac.il/report/2001/043Comments and Revisions published for TR01-043en-usMon, 18 Jun 2001 15:38:06 +0300
Paper TR01-043
| Predictive complexity and information |
Mikhail V. Vyugin,
Vladimir Vyugin
https://eccc.weizmann.ac.il/report/2001/043A new notion of predictive complexity and corresponding amount of
information are considered.
Predictive complexity is a generalization of Kolmogorov complexity
which bounds the ability of any algorithm to predict elements of
a sequence of outcomes. We consider predictive complexity for a wide class
of bounded loss functions which are generalization of square-loss function.
Relations between unconditional $KG(x)$ and conditional $KG(x|y)$
predictive complexities are studied. We define an algorithm
which has some ``expanding property''. It transforms with positive
probability sequences of given predictive
complexity into sequences of essentially bigger predictive complexity.
A concept of amount of predictive information $IG(y:x)$ is studied. We show
that this information is non-commutative in a very strong sense and present
asymptotic relations between values $IG(y:x)$, $IG(x:y)$, $KG(x)$ and
$KG(y)$.
Mon, 18 Jun 2001 15:38:06 +0300https://eccc.weizmann.ac.il/report/2001/043