Sarcina 4

Fie \(X\) o mulțime finită de dimensiune finită \(k\). Fie \(A\) un algoritm de învățare care, pentru un eșantion \(S=((x_1, y_1), \ldots, (x_m, y_m)) \in (X \times \{0,1\})^m\), produce o funcție \(A(S)\) astfel încât:

Dacă \(x=x_i\) pentru un anumit \(i \in \{1, \ldots, m\}\), atunci \(A(S)(x)= y_i\),

Dacă \(x \notin \{x_1, \ldots, x_m\}\), atunci \(A(S)(x)\) este ales aleator cu probabilitatea \(1/2\) pentru fiecare etichetă din \(\{0,1\}\).

Dată fiind o funcție \(f: X \to \{0,1\}\), definiți o distribuție de probabilitate \((U,f)\) pe \(X \times \{0,1\}\) atribuind probabilitatea \(1/k\) fiecărei perechi \((x, f(x))\) și probabilitatea 0 oricărei perechi \((x,y) \notin \{(x, f(x)): x \in X\}\).

Arătați că pentru orice \(f: X \to \{0,1\}\) și \(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}.\]

[Total 7 puncte]