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