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 452–463. Berlin: Springer, 2006.
• Non-asymptotic calibration and resolution. Theoretical Computer Science (Special Issue devoted to ALT 2005) 387, 77–89 (2007).