Задача 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 баллов]