UML5.1 – Định lý không có bữa ăn trưa miễn phí (The No-Free-Lunch Theorem)

This entry is part 2 of 3 in the series understanding machine learning chapter 5

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
    1. \(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\).
    2. 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:

    1. 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\)
    2. 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.

UML5.2 – Phân tích lỗi

This entry is part 3 of 3 in the series understanding machine learning chapter 5

Nhắc lại: như phần trước chúng ta đã phân tách lỗi của một bộ dự đoán \(ERM_{\mathcal H}\) thành 2 thành phần bias (approximation error) và complexity (estimation error) (Độ phức tạp của lớp giả thiết \(\mathcal H\)). Gọi \(h_{S}\) là một giả thiết \(ERM_{\mathcal H}\). chúng ta có thể viết lại:

\(L_{D}(h_{S}) = \epsilon_{app} + \epsilon_{est}\) trong đó:

\(\epsilon_{app}  = \min\limits_{h \in \mathcal H} L_{\mathcal D}(h)) \\ \epsilon_{est} = L_{D}(h_{S})  –  \epsilon_{app} \)
  • Lỗi xấp xỉ (Approximation Error): là rủi ro tối thiểu đạt được bởi một bộ dự đoán trong một lớp giả thiết. Số hạng này không phụ thuộc vào kích thước mẫu mà nó phụ thuộc vào lớp giả thiết đã được lựa chọn. Việc mở rộng lớp giả thiết có thể giảm đi lỗi xấp xỉ (approximation error).
  • Lỗi ước lượng (Estimation Error): là hiệu giữa lỗi xấp xỉ và lỗi đạt được bởi bộ dự đoán ERM. Số hạng này phụ thuộc vào kích thước tập huấn luyện hoặc độ phức tạp của lớp giả thiết \(\mathcal H\).

Mục đích của chúng ta là tối thiểu hóa tổng rủi ro vậy nên chúng ta đối mặt với việc cân bằng giữa bias-complexity. Việc chọn lớp giả thiết \(\mathcal H\) lớn thì sẽ giảm lỗi xấp xỉ tuy nhiên đồng thời lại tăng lỗi ước lượng. Vậy nên một lớp giả thiết \(\mathcal H\) lớn có thể dẫn đến Overfitting. Ngược lại, khi một lớp giả thiết \(\mathcal H\) nhỏ thì lại dễ dẫn tới Underfitting. Mặc dù chúng ta không thể biết được làm thể nào để xây dựng một lớp giả thiết tối ưu, tuy nhiên chúng ta vẫn có thể dựa vào một vài kiến thức biết trước của một bài toán cụ thể mà có thể thiết kế được lớp giả thiết có lỗi xấp xỉlỗi ước lượng không quá lớn.  Ví dụ, mặc dù chúng ta không thể biết chính xác màu sắc và độ cứng để dự đoán một quả đu đủ ngon nhưng dựa trên những kiến thức biết trước về những loại quả khác có màu sắc độ cứng sẽ ngon như nào thì ta cũng có thể xây dựng được bộ dự đoán tốt cho việc dự đoán vị ngon của quả đu đủ.

 

UML5 – Giới thiệu cân bằng giữa Bias-Complexity

This entry is part 1 of 3 in the series understanding machine learning chapter 5

Như trong chương 2, chúng ta đã thấy rằng dữ liệu huấn luyện có thể làm sai lệch bộ học và dẫn đến kết quả là Overfitting. Để khắc phục điều đó, thì chúng ta đã giới hạn không gian tìm kiếm trên một vài lớp giả thiết \(\mathcal H\). Lớp giả thiết này được xem như là một vài kiến thức biết trước (prior knowledge) mà bộ học biết về bài toán và có một niềm tin rằng một trong những giả thiết \(\mathcal h\) của lớp \(\mathcal H\) là một mô hình có lỗi thực nhỏ. Ví dụ trong bài toán đu đủ có vị ngon hay dở,  dựa trên kiến thức biết trước về các loại quả khác thì chúng ta phần nào có thể dự đoán được vị quả đu đủ dựa trên một số vùng màu sắc-độ cứng của quả.

Và trong chương 5 này, chúng ta sẽ trả lời 2 câu hỏi:

  • Liệu kiến thức biết trước có cần thiết cho sự thành công của việc học?
  • Liệu rằng có một bộ học tổng quát có thể giải được tất các bài toán? Chúng ta sẽ toán học hóa chút câu hỏi này. Một bài toán học cụ thể được định nghĩa bởi một phân phối chưa biết \(\mathcal D\) trên \(\mathcal X \times \mathcal Y \). Mục tiêu của bộ học là để tìm một bộ dự đoán \(\mathcal h\): \(\mathcal X \rightarrow \mathcal Y\) mà rủi ro thực tế, \(L_{\mathcal D}(h)\) là đủ nhỏ. Câu hỏi đặt ra là liệu có tồn tại một thuật toán học A và kích thước tập huấn luyện \(\mathcal m\), với mọi phân phối \(\mathcal D\), nếu A nhận được \(\mathcal m\) i.i.d mẫu học từ \(\mathcal D\) thì thuật toán học A có khả năng sinh ra bộ dự đoán \(\mathcal h\) mà có rủi ro thực tế thấp hay không?

Ứng với từng câu trả lời sẽ là từng phần của chương này:

Phần đầu tiên 5.1: Sẽ trả lời cho câu hỏi thứ 2 ứng với định lý nổi tiếng “Không có bữa ăn nào miễn phí”(No-Free Lunch Theorem) tuyên bố rằng không tồn tại bộ học tổng quát. Nghĩa là rằng, không có bộ học nào có thể giải được tất cả các bài toán bởi vì luôn luôn tồn tại một phân phối mà nó làm cho bộ học này thất bại tuy nhiên bộ học khác lại học thành công.

Từ định lý này, một bài toán học cụ thể được định nghĩa bởi một vài phân phối \(\mathcal D\) thì chúng ta nên có thêm một vài kiến thức biết trước trên \(\mathcal D\). Một số dạng kiến thức biết trước:

      • Kiến thức biết trước đến từ một vài họ tham số cụ thể của phân phối \(\mathcal D\) (sẽ học trong chương 24)
      • Kiến thức biết trước mà chúng ta đã học khi định nghĩa mô hình học PAC. Chúng ta đã giả sử có tồn tại giả thiết \(\mathcal h\) trong lớp giả thiết hữu hạn \(\mathcal H\) mà \(L_{\mathcal D}(h) = 0\)
      • Kiến thức biết trước mà chúng ta học khi định nghĩa mô hình học agnostic PAC . Giả thiết rằng, trong lớp hữu hạn \(\mathcal H\) có tồn tại \(min_{\mathcal h \in \mathcal H}L_{\mathcal D}(\mathcal h)\)

Phần thứ hai 5.2: Chúng ra sẽ nghiên cứu lợi ích và tác hại của việc khi thêm kiến thức biết trước trong một lớp giả thiết. Chúng ta sẽ phân tách lỗi của một thuật toán ERM qua lớp giả thiết \(\mathcal H\) thành 2 thành phần:

      • Phản ánh chất lượng của kiến thức biết trước được đo bằng rủi ro nhỏ nhất của một giả thiết trong một lớp giả thiết \(min_{h \in \mathcal H}L_{\mathcal D}(h)\). Thành phân này gọi là bias hay lỗi xấy xỉ (approximation error).
      • Lỗi do overfitting nó phụ thuộc vào kích thước và độ phức tạp của lớp giả thiết \(\mathcal H\). Thành phần này gọi là comlexity hay estimation error.

Trong đó, biascomlexity của một lớp giả thiết \(\mathcal H\) có quan hệ trái ngược nhau và chúng ta cần cân bằng điều chỉ để hợp lý chúng. Bởi vì, nếu ta tăng độ phức tạp của lớp giả thiết \(\mathcal H\) thì nó sẽ giảm bias tuy nhiên lại tăng khả năng overfitting, còn nếu ta giảm độ phức tạp của lớp giả thiết \(\mathcal H\) thì nó sẽ tăng bias nhưng lại giảm khả năng overfitting.