Zadatak 4

Neka je \(X\) konačan skup konačne veličine \(k\). Neka je \(A\) algoritam učenja koji na uzorku \(S=((x_1, y_1), \ldots, (x_m, y_m)) \in (X \times \{0,1\})^m\) daje funkciju \(A(S)\) takvu da:

Ako je \(x=x_i\) za neko \(i \in \{1, \ldots, m\}\), tada je \(A(S)(x)= y_i\),

Ako je \(x \notin \{x_1, \ldots, x_m\}\), tada se \(A(S)(x)\) bira nasumično sa verovatnoćom \(1/2\) za svaku oznaku iz \(\{0,1\}\).

Neka je data funkcija \(f: X \to \{0,1\}\). Definišite raspodelu verovatnoće \((U,f)\) nad \(X \times \{0,1\}\) tako što se svakoj uređenoj paru \((x, f(x))\) dodeljuje verovatnoća \(1/k\), a verovatnoća 0 svakom \((x,y) \notin \{(x, f(x)): x \in X\}\).

Pokažite da za svaku funkciju \(f: X \to \{0,1\}\) i \(S=((x_1, f(x_1)), \ldots, (x_m, f(x_m)))\) važi

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

[Ukupno 7 poena]