任務 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)\) 會在 \(\{0,1\}\) 的每個標籤上以機率 \(1/2\) 隨機選取。

給定一個函數 \(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 分]