Trong phần này, chúng ta sẽ chứng minh rằng không có một bộ học tổng quát nào có thể thành công trên tất cả các bài toán học.
- Định lý 5.1 (No-Free-Lunch): Cho
- \(A\) là thuật toán học bất kì cho bài toán phân lớp nhị phân trên miền \(\mathcal X\) với hàm lỗi \(0-1\).
- Tập huấn luyện trên miền \(S\) kích thước \(m<|\mathcal X|/2 \).
Khi đó, tồn tại phân phối \(\mathcal D\) trên \(\mathcal X \times \{0, 1\}\) sao cho:
-
- Có hàm dự đoán \(f\) để \(f\) dự đoán hoàn hảo trên \(\mathcal D\): \(L_{\mathcal D}(\mathcal f) = 0\)
- Thuật toán A học “kém với xác suất không nhỏ”: \(\mathbb P_{S\sim \mathcal D^m}\left[ L_{\mathcal D}(A(S)) \geq 1/8\right] \geq 1/7\)
Định lý phát biểu rằng với mọi thuật toán học, luôn tồn tại bài toán (có lời giải) mà thuật toán học này không thể học tốt được.
Chứng minh định lý:
Cho \(C\) là một tập con của \(\mathcal X\) với kích thước \(2m\). Vậy sẽ có \(T=2^{2m}\) hàm từ \(C\) tới \(\{0,1\}\). Và chúng ta sẽ kí hiệu các hàm đó lần lượt là \(f_1, f_2, …, f_T\). Với mỗi hàm \(f_i\), cho \(\mathcal D_i\) là một phân phối trên \(C \times \{0,1\}\) được định nghĩa bởi:
\(\mathcal D_{i}(\{(x,y)\})=
\begin{cases}
1/|C| & \quad \text{nếu }y = f_{i}(x),\\
0 & \quad \text{trường hợp còn lại}
\end{cases}\)
Theo công thức trên ta thấy rằng xác suất để chọn một cặp \((x, y)\) là \(1/|C|\) nếu \(y\) là nhãn thực sự và có giá trị bằng \(0\) nếu \(y \ne f_{i}(x)\). Và rõ ràng \(L_{\mathcal D_i}(f_{i})= 0\)
Từ đó, với mọi thuật toán, \(A\), nhận một tập huấn luyện \(S\) gồm \(m\) mẫu từ miền \(C \times \{0,1\}\) và trả ra một hàm dự đoán \(A(S) : C \rightarrow \{0,1\}\) thì:
\(\max\limits_{i \in [T]} \underset{ S \sim \mathcal D_{i}^m}{\mathbb E} [L_{\mathcal D_i}(A(S))] \geq 1/4 \quad (5.1)\)
Bất đẳng thức (5.1) nghĩa là: có một chỉ số \(i\) sao cho khi tập huấn luyện \(S\) được lấy từ phân bố \(\mathcal D_i^m\), thì thuật toán \(A\) cho hàm dự đoán có kỳ vọng lỗi ít nhất là \(1/4\) (kỳ vọng được lấy theo phân bố của tập huấn luyện \(S\sim\mathcal D_i^m\)).
Vậy tổng quát hóa lên, với \(m\) mẫu từ miền \(X \times \{0,1\}\) ta có phát biểu:
Với mọi thuật toán học, \(A’\), mà nhận được một tập huấn luyện gồm \(m\) mẫu từ \(X \times \{0,1\}\), có một hàm \(f : \mathcal X \rightarrow \{0,1\}\) và một phân phối \(\mathcal D\) trên \(\mathcal X \times \{0,1\}\) sao cho \(L_{\mathcal D}(f) = 0\) và
\(\underset{ S \sim \mathcal D^m}{\mathbb E} [L_{\mathcal D}(A'(S))] \geq 1/4 \quad (5.2)\)
Phương trình (5.2) đủ để chứng minh rằng \({\mathbb P}[L_{\mathcal D}(A'(S)) \geq 1/8] \geq 1/7\)
- Chứng minh phương trình (5.1):
Có \(k = (2m)^m\) chuỗi gồm \(m\) mẫu từ \(C\) và kí hiệu các chuỗi này bởi \(S_1, S_2,…, S_k\). (\(S_j = (x_1,…,x_m)\)). Chúng ta kí hiêu \(S_{j}^i\) là các phần tử của chuỗi \(S_j\) được đánh nhãn bởi hàm \(f_i\), \(S_{j}^i = ((x_1, f_{i}(x_1)), (x_2, f_{i}(x_2)), …, (x_m, f_{i}(x_m)))\). Nếu phân phối là \(\mathcal D_i\) thì các tập huấn luyện mà thuật toán học A có thế nhận được là \(S_{1}^i, S_{2}^i, …, S_{k}^i\) và tất cả các tập huấn luyện cùng có xác suất của việc lấy mẫu như nhau nên:
\(\underset{ S \sim \mathcal D_{i}^m}{\mathbb E} [L_{\mathcal D_i}(A(S))] = \frac{1}{k} \sum_{1}^{k} L_{\mathcal D_i}(A(S_{j}^i)) \quad (5.3)\)
Bằng việc sử dụng tính tính chất maximum > average > minimum, ta có:
\(\max\limits_{i \in [T]} \frac{1}{k} \sum_{1}^{k} L_{\mathcal D_i}(A(S_{j}^i)) \geq \frac{1}{T} \sum_{1}^{T} \frac{1}{k} \sum_{1}^{k} L_{\mathcal D_i}(A(S_{j}^i)) \geq \min\limits_{j \in [k]} \frac{1}{T} \sum_{1}^{T} L_{\mathcal D_i}(A(S_{j}^i)) \quad (5.4) \\\)Cố định chuỗi \(S_{j} = (x_1, x_2,…, x_m)\) và \(v_1, v_2, …v_p\) là các mẫu trong \(C\) mà không xuất hiện trong \(S_j\). cho nên với mọi giả thiết \(h: C \rightarrow \{0,1\}\) và với mọi \(i\) ta có:
\(L_{\mathcal D_i}(h) = \frac{1}{2m} \sum_{x \in C} \mathbb 1 [h(x) \ne f_{i}(x)]\\ \quad \quad \quad \geq \frac{1}{2m} \sum_{r=1}^p \mathbb{1}[h(v_r) \ne f_{i}(v_r)] \\ \quad \quad \quad \geq \frac{1}{2p} \sum_{r=1}^p \mathbb{1}[h(v_r) \ne f_{i}(v_r)] \quad (5.5)\)
Vì thế áp dụng công thức (5.5),
\(\frac{1}{T} \sum_{1}^{T} L_{\mathcal D_i}(A(S_{j}^i)) \geq \frac{1}{T} \sum_{1}^{T} \frac{1}{2p} \sum_{r=1}^p 1[A(S_j^i)(v_r) \ne f_{i}(v_r)] \\ \quad \quad \quad \quad \quad \quad \quad \quad = \frac{1}{2p} \sum_{1}^{p} \frac{1}{T} \sum_{i=1}^T 1[A(S_j^i)(v_r) \ne f_{i}(v_r)] \\ \quad \quad \quad \quad \quad \quad \quad \quad \geq \frac{1}{2} \min\limits_{r \in [p]} \frac{1}{T} \sum_{i=1}^T 1[A(S_j^i)(v_r) \ne f_{i}(v_r)] \quad (5.6) \)Chúng ta có thể phân hoạch các hàm \(f_1, f_2, …, f_T\) thành \(T/2\) cặp không giao nhau. Trong đó 1 cặp \((f_i, f_i’)\) với mọi \(c \in C, f_{i}(c) \ne f_{i’}(c) \) nếu và chỉ nếu \(c = v_r\). Đối với 1 cặp như vậy chúng ta có \(S_{j}^i = S_{j}^{i’} \) thì:
\( 1[A(S_j^i)(v_r) \ne f_{i}(v_r)] + 1[A(S_j^{i’})(v_r) \ne f_{i’}(v_r)] =1 \)
Từ đó sinh ra,
\(\frac{1}{T} \sum_{r=1}^T 1[A(S_j^i)(v_r) \ne f_{i}(v_r)] = \frac{1}{2}\)
Từ công thức (5.6), (5.4) và (5.3) ta có thể suy ra công thức (5.1)
Vậy công thức (5.1) đã được chứng minh đồng nghĩa với (5.2) cũng được chứng minh. Vì công thức (5.2) bản chất là viết lại một cách khái quát của (5.1). Phần tiếp theo ta đi chứng minh định lý “không có bữa ăn nào miễn phí” (No-Free-Lunch).
Với (5.2) ta cần chứng minh \(\mathbb{P}[L_{\mathcal{D}}(A'(S)) \geq 1/8] \geq 1/7\)
Để chứng minh được bất đẳng thức trên cần sử dụng bổ đề B.1. Bổ đề B.1 được phát biểu và chứng minh như sau:
Bổ đề B.1: Cho \(Z\) là một biến ngẫu nhiên có giá trị trong khoảng \([0, 1]\). Giả sử rằng \(\mathbb{E}[Z] = \mu\). Thì với bất kì \(\alpha \in (0, 1)\)
\(\mathbb{P}[Z > 1 – \alpha] \geq \frac{\mu – (1-\alpha)}{\alpha}\)
hay viết cách khác rằng với mọi \(\alpha \in (0, 1)\)
\(\mathbb{P}[Z > \alpha] \geq \frac{\mu – \alpha}{1 -\alpha} \quad (5.7)\\\)
Chứng minh bổ đề B1:
Cho \(Y = 1 – Z\) thì \(Y\) là một biến ngẫu nhiên không âm với \(\mathbb{E}[Y] = 1 – \mathbb{E}[Z] = 1 – \mu\). Sử dụng bất đẳng thức Markov ta có:
\(\mathbb{P}[Z \leq 1 – \alpha] = \mathbb{P}[1-Z \geq \alpha] =\mathbb{P}[Y \geq \alpha] \leq \frac{\mathbb{E}[Y]}{\alpha} = \frac{1 – \mu}{\alpha}\\ \)Vậy nên
\(\mathbb{P}[Z > 1 – \alpha] \geq 1 – \frac{1 – \mu}{\alpha} = \frac{\alpha + \mu – 1}{\alpha} = \frac{\mu – (1-\alpha)}{\alpha} \)
Bất đẳng thức Markov: \(\forall \alpha \geq 0, \mathbb{P}[Z \geq \alpha] \leq \frac{\mathbb{E}[Z]}{\alpha}\)
Theo công thức (5.2) ta có: \(\underset{ S \sim \mathcal D^m}{\mathbb E} [L_{\mathcal D}(A'(S))] \geq 1/4\). Áp dụng công thức (5.7) với \( Z = L_{\mathcal D}(A'(S)), \alpha = 1/8 \) ta có:
\(\mathbb{P}[L_{\mathcal{D}}(A'(S)) > 1/8] \geq \frac{{\mathbb E} [L_{\mathcal D}(A'(S))] – 1/8}{1 – 1/8} \geq \frac{1/4 – 1/8}{7/8} =1/7 \)
- Hệ quả 5.2: Cho \(\mathcal X\) là một tập miền vô hạn và cho \(\mathcal H\) là tập tất cả các hàm từ \(\mathcal X\) đến \(\{0, 1\}\) thì lớp giả thuyết \(\mathcal H\) không thể học PAC.
Chứng minh: Sử dụng phương pháp phản chứng. Giả sử rằng lớp giả thiết có khả năng học. Chọn \(\epsilon < 1/8\) và \(\delta < 1/7\). Theo như định nghĩa về lớp giả thiết là PAC thì phải có một vài thuật toán học \(A\) và một số nguyên \( m = (\epsilon, \delta)\), sao cho bất kì phân phối dữ liệu được sinh ra trên \(\mathcal X \times \{0, 1\}\). Nếu có một vài hàm \(f : \mathcal X \rightarrow \{0, 1\}\) mà \(L_{\mathcal D}(f) = 0\) thì thuật toán \(A\) sẽ trả về một giả thuyết \(A(S)\) có xác suất ít nhất là \(1 – \delta\) sao cho \(L_{\mathcal D}(A(S)) \leq \epsilon\). Trong đó S là tập huấn luyện có kích thước \(m\) được sinh độc lập bởi phân phối \(\mathcal D\). Mặt khác, theo định lý (5.1-No-Free-Lunch) khi không gian \(|X| > 2m\) thì với mọi thuật toán học, tồn tại một phân phối \(\mathcal D\) sao cho với xác suất lớn hơn 1/7 > \(\delta\) và \(L_{\mathcal D}(A(S)) > 1/8 > \epsilon\). Điều này dẫn đến mâu thuẫn với bên trên.