Zadanie 4

Niech \(X\) będzie skończonym zbiorem o skończonej liczności \(k\). Niech \(A\) będzie algorytmem uczącym, który dla próbki \(S=((x_1, y_1), \ldots, (x_m, y_m)) \in (X \times \{0,1\})^m\) zwraca funkcję \(A(S)\) taką, że:

Jeśli \(x=x_i\) dla pewnego \(i \in \{1, \ldots, m\}\), to \(A(S)(x)= y_i\),

Jeśli \(x \notin \{x_1, \ldots, x_m\}\), to \(A(S)(x)\) jest wybierane losowo z prawdopodobieństwem \(1/2\) dla każdej etykiety z \(\{0,1\}\).

Dana jest funkcja \(f: X \to \{0,1\}\). Zdefiniuj rozkład prawdopodobieństwa \((U,f)\) na \(X \times \{0,1\}\), przypisując prawdopodobieństwo \(1/k\) każdej parze \((x, f(x))\) oraz prawdopodobieństwo 0 każdej parze \((x,y) \notin \{(x, f(x)): x \in X\}\).

Pokaż, że dla każdej funkcji \(f: X \to \{0,1\}\) oraz \(S=((x_1, f(x_1)), \ldots, (x_m, f(x_m)))\) zachodzi

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

[Łącznie 7 punktów]