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)))/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).