Завдання 4

Нехай \(X\) — скінченна множина деякого скінченного розміру \(k\). Нехай \(A\) — алгоритм навчання, який за вибіркою \(S=((x_1, y_1), \ldots, (x_m, y_m)) \in (X \times \{0,1\})^m\) повертає функцію \(A(S)\) таку, що:

Якщо \(x=x_i\) для деякого \(i \in \{1, \ldots, m\}\), то \(A(S)(x)= y_i\),

Якщо \(x \notin \{x_1, \ldots, x_m\}\), то \(A(S)(x)\) обирається випадково з імовірністю \(1/2\) для кожної мітки з \(\{0,1\}\).

Для заданої функції \(f: X \to \{0,1\}\) визначимо розподіл ймовірності \((U,f)\) на \(X \times \{0,1\}\), призначивши ймовірність \(1/k\) кожній парі \((x, f(x))\) і ймовірність 0 будь-якій \((x,y) \notin \{(x, f(x)): x \in X\}\).

Покажіть, що для кожної \(f: X \to \{0,1\}\) та \(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}.\]

[Усього 7 балів]