Uppgift 4

Låt \(X\) vara en ändlig mängd med ändlig storlek \(k\). Låt \(A\) vara en inlärare som på ett stickprov \(S=((x_1, y_1), \ldots, (x_m, y_m)) \in (X \times \{0,1\})^m\) ger ut en funktion \(A(S)\) sådan att:

Om \(x=x_i\) för något \(i \in \{1, \ldots, m\}\) så är \(A(S)(x)= y_i\),

Om \(x \notin \{x_1, \ldots, x_m\}\), så väljs \(A(S)(x)\) slumpmässigt med sannolikhet \(1/2\) för varje etikett i \(\{0,1\}\).

Givet en funktion \(f: X \to \{0,1\}\), definiera en sannolikhetsfördelning \((U,f)\) över \(X \times \{0,1\}\) genom att tilldela sannolikheten \(1/k\) till varje par \((x, f(x))\) och sannolikheten 0 till varje \((x,y) \notin \{(x, f(x)): x \in X\}\).

Visa att för varje \(f: X \to \{0,1\}\) och \(S=((x_1, f(x_1)), \ldots, (x_m, f(x_m)))\),

\[L_{(U,f)}(A(S)) -L_S(A(S)) \geq \frac{(k-m)}{2k}.\]

[Totalt 7 poäng]