Tâche 4

Soit \(X\) un ensemble fini de cardinal fini \(k\). Soit \(A\) un algorithme d’apprentissage qui, à partir d’un échantillon \(S=((x_1, y_1), \ldots, (x_m, y_m)) \in (X \times \{0,1\})^m\), produit une fonction \(A(S)\) telle que :

Si \(x=x_i\) pour un certain \(i \in \{1, \ldots, m\}\), alors \(A(S)(x)= y_i\),

Si \(x \notin \{x_1, \ldots, x_m\}\), alors \(A(S)(x)\) est choisi aléatoirement avec probabilité \(1/2\) pour chacune des étiquettes de \(\{0,1\}\).

Étant donnée une fonction \(f: X \to \{0,1\}\), définir une distribution de probabilité \((U,f)\) sur \(X \times \{0,1\}\) en attribuant une probabilité \(1/k\) à toute paire \((x, f(x))\) et une probabilité 0 à tout \((x,y) \notin \{(x, f(x)): x \in X\}\).

Montrer que pour toute fonction \(f: X \to \{0,1\}\) et tout échantillon \(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 points]