K 29

K29 is an algorithm given by Defensive Forecasting tecnique to make forecasts of the events correspondingly to the purpose of competitive on-line prediction. The following algorithm was firsly named K29*, but now it is known as K29. If the forecaster follows this algortihm, he will compete with all functions on $ [0,1] \times X $ from the Reproducing Kernel Hilbert Space corresponding to the taken kernel.

K29 algorithm:
$\quad$Parameter: forecast-continuous kernel K on $ [0,1] \times X$
$\quad$FOR $n=1,2,\dots$:
$\qquad$Read $x_n \in X$
$\qquad$Set $S_n(\gamma)=\sum_{i=1}^{n-1} K((\gamma,x_n),(\gamma_i,x_i))(y_i-\gamma_i) + \frac{1}{2}K((\gamma,x_n),(\gamma,x_n))(1-2\gamma)$ for $\gamma \in [0,1]$.
$\qquad$If $sign(S_n(0)) = sign(S_n(1)) \ne 0$, output $\gamma_n=(1+sign(S_n(0)))\slash{}2$. Otherwise, output any root $\gamma: S_n(\gamma)=0$
$\qquad$Read $y_n \in \{0,1\}$
$\quad$END.

Such forecasts have the property calibration-cum-resolution. It is not proven, when if the function $S_n(\gamma)$ has the same sign in 0 and 1, it has no roots. But in practice it usually holds, and the root is unique.

Bibliography

  • On-line regression competitive with reproducing kernel Hilbert spaces (extended abstract). In: Theory and Applications of Models of Computation. Proceedings of the Third Annual Conference on Computation and Logic (ed by J-Y Cai, S B Cooper and A Li), Lecture Notes in Computer Science, vol 3959, pp 452463. Berlin: Springer, 2006.
  • Non-asymptotic calibration and resolution. Theoretical Computer Science (Special Issue devoted to ALT 2005) 387, 7789 (2007).