6533b7dcfe1ef96bd1272df4
RESEARCH PRODUCT
Computational complexity of prediction strategies
Karlis Podniekssubject
machine learning:MATHEMATICS [Research Subject Categories]function predictioninductive inferencedescription
The value f(m+1) is predicted from given f(1), ..., f(m). For every enumeration T(n, x) there is a strategy that predicts the n-th function of T making no more than log2(n) errors (Barzdins-Freivalds). It is proved in the paper that such "optimal" strategies require 2^2^cm time to compute the m-th prediction (^ stands for expoentiation).
| year | journal | country | edition | language |
|---|---|---|---|---|
| 1977-01-01 |