任务 4

设 \(X\) 为一个大小为 \(k\) 的有限集合。设 \(A\) 为一个学习算法，对样本 \(S=((x_1, y_1), \ldots, (x_m, y_m)) \in (X \times \{0,1\})^m\) 输出一个函数 \(A(S)\)，满足：

若存在某个 \(i \in \{1, \ldots, m\}\) 使得 \(x=x_i\)，则 \(A(S)(x)= y_i\)，

若 \(x \notin \{x_1, \ldots, x_m\}\)，则 \(A(S)(x)\) 以概率 \(1/2\) 在标签集合 \(\{0,1\}\) 中随机选取。

给定一个函数 \(f: X \to \{0,1\}\)，在 \(X \times \{0,1\}\) 上定义一个概率分布 \((U,f)\)：对任意 \((x, f(x))\) 赋予概率 \(1/k\)，对所有 \((x,y) \notin \{(x, f(x)): x \in X\}\) 的对赋予概率 0。

证明：对于任意 \(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 分]