Taak 4

Laat \(X\) een eindige verzameling zijn met eindige grootte \(k\). Laat \(A\) een lerende zijn die op een steekproef \(S=((x_1, y_1), \ldots, (x_m, y_m)) \in (X \times \{0,1\})^m\) een functie \(A(S)\) output zodanig dat:

Als \(x=x_i\) voor een of andere \(i \in \{1, \ldots, m\}\), dan \(A(S)(x)= y_i\),

Als \(x \notin \{x_1, \ldots, x_m\}\), dan wordt \(A(S)(x)\) willekeurig gekozen met kans \(1/2\) voor elk label in \(\{0,1\}\).

Gegeven een functie \(f: X \to \{0,1\}\), definieer een kansverdeling \((U,f)\) over \(X \times \{0,1\}\) door kans \(1/k\) toe te kennen aan elk paar \((x, f(x))\) en kans 0 aan elk \((x,y) \notin \{(x, f(x)): x \in X\}\).

Laat zien dat voor elke \(f: X \to \{0,1\}\) en \(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}.\]

[Totaal 7 punten]