Esercizio 4

Sia \(X\) un insieme finito di cardinalità finita \(k\). Sia \(A\) un algoritmo di apprendimento che, dato un campione \(S=((x_1, y_1), \ldots, (x_m, y_m)) \in (X \times \{0,1\})^m\), restituisce una funzione \(A(S)\) tale che:

Se \(x=x_i\) per qualche \(i \in \{1, \ldots, m\}\), allora \(A(S)(x)= y_i\),

Se \(x \notin \{x_1, \ldots, x_m\}\), allora \(A(S)(x)\) è scelto casualmente con probabilità \(1/2\) per ciascuna etichetta in \(\{0,1\}\).

Data una funzione \(f: X \to \{0,1\}\), definiamo una distribuzione di probabilità \((U,f)\) su \(X \times \{0,1\}\) assegnando probabilità \(1/k\) a ogni coppia \((x, f(x))\) e probabilità 0 a ogni \((x,y) \notin \{(x, f(x)): x \in X\}\).

Mostrare che per ogni \(f: X \to \{0,1\}\) e \(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}.\]

[Totale 7 punti]