4. feladat

Legyen \(X\) egy véges, \(k\) elemszámú halmaz. Legyen \(A\) egy tanuló, amely egy \(S=((x_1, y_1), \ldots, (x_m, y_m)) \in (X \times \{0,1\})^m\) mintára egy \(A(S)\) függvényt ad kimenetként úgy, hogy:

Ha \(x=x_i\) valamely \(i \in \{1, \ldots, m\}\) esetén, akkor \(A(S)(x)= y_i\),

Ha \(x \notin \{x_1, \ldots, x_m\}\), akkor \(A(S)(x)\) véletlenszerűen kerül kiválasztásra úgy, hogy mindkét címke \(\{0,1\}\)-beli értéke \(1/2\) valószínűséggel fordul elő.

Adott egy \(f: X \to \{0,1\}\) függvény; definiáljunk egy \((U,f)\) valószínűségi eloszlást az \(X \times \{0,1\}\) halmazon úgy, hogy \(1/k\) valószínűséget rendelünk minden \((x, f(x))\) párhoz, és 0 valószínűséget minden olyan \((x,y)\) párhoz, amelyre \((x,y) \notin \{(x, f(x)): x \in X\}\).

Mutasd meg, hogy minden \(f: X \to \{0,1\}\) és \(S=((x_1, f(x_1)), \ldots, (x_m, f(x_m)))\) esetén

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

[Összesen 7 pont]