Tarea 4

Sea \(X\) un conjunto finito de tamaño finito \(k\). Sea \(A\) un algoritmo de aprendizaje que, dado un conjunto de muestras \(S=((x_1, y_1), \ldots, (x_m, y_m)) \in (X \times \{0,1\})^m\), produce una función \(A(S)\) tal que:

Si \(x=x_i\) para algún \(i \in \{1, \ldots, m\}\), entonces \(A(S)(x)= y_i\),

Si \(x \notin \{x_1, \ldots, x_m\}\), entonces \(A(S)(x)\) se elige aleatoriamente con probabilidad \(1/2\) para cada etiqueta en \(\{0,1\}\).

Dada una función \(f: X \to \{0,1\}\), defina una distribución de probabilidad \((U,f)\) sobre \(X \times \{0,1\}\) asignando probabilidad \(1/k\) a cualquier par \((x, f(x))\) y probabilidad 0 a cualquier \((x,y) \notin \{(x, f(x)): x \in X\}\).

Demuestre que para toda \(f: X \to \{0,1\}\) y \(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 puntos]