Chứng minh định lý cơ bản của học máy thống kê – phần 1
Nhắc lại định lý cơ bản của học máy thống kê, ta đánh số các mệnh đề lần lượt từ (1) đến (6). Ta có thể chứng minh đơn giản một số mối quan hệ kéo theo (implication) giữa các mệnh đề như sau:
-
-
- Mệnh đề (1) kéo theo mệnh đề (2): theo các chương trước, nếu \({\cal{H}}\) có tính chất hội tụ đều tức là với xác suất cao là chúng ta sẽ có một bộ dữ liệu huấn luyện đại diện. Vì vậy, khi áp dụng ERM rule để tối thiểu hàm lỗi trên bộ dữ liệu này, chúng ta sẽ có được một giả thiết \(h_S\) thỏa mãn hàm lỗi huấn luyện (training loss) \(L_S(h_S)\) không quá chênh lệch so với hàm lỗi tổng quát (generalization loss) \(L_{\cal{D}}(h_S)\). (xem lại các chương trước). Điều này tương đương với mệnh đề (2)
- Mệnh đề (2) kéo theo mệnh đề (3): theo định nghĩa của agnostic PAC learnability
- Mệnh đề (3) kéo theo mệnh đề (4): do PAC learnability là trường hợp đặc biệt của agnostic PAC learnability, khi tồn tại một giả thiết \(h\) trong \({\cal{H}}\) với hàm lỗi tổng quát \(L_{\cal{D}}(h)\) mang giá trị \(0\)
- Mệnh đề (4) kéo theo mệnh đề (5): theo định nghĩa của PAC learnability
- Mệnh đề (5) kéo theo mệnh đề (6): theo định lý “không có bữa trưa miễn phí”, nếu lớp giả thiết \({\cal{H}}\) của chúng ta có VC-dimension vô hạn thì \({\cal{H}}\) sẽ không có tính chất PAC learnability cũng như agnostic PAC learnability, kéo theo là không có ERM rule nào là một PAC learner thành công với \({\cal{H}}\). Do vậy, nếu mệnh đề (5) đúng thì buộc mệnh đề (6) phải đúng.
-
Vậy chúng ta đã chứng minh được các quan hệ kéo theo (1) \(\to\) (2), (2) \(\to\) (3), (3) \(\to\) (4), (4) \(\to\) (5), và (5) \(\to\) (6). Để hoàn tất chứng minh định lý cơ bản của học máy thống kê, ta cần chứng minh mối quan hệ kéo theo (6) \(\to\) (1).
Chứng minh định lý cơ bản của học máy thống kê – phần 2
Tiếp theo ta cần chứng minh mối quan hệ kéo theo (6) \(\to\) (1). Để chứng minh được mối quan hệ kéo theo này là một chặng đường rất dài và gian nan. Chúng ta sẽ bắt đầu từ các kiến thức nền trước.
Ý tưởng của chúng ta là:
-
-
- Bước 1: chứng minh rằng nếu \(\text{VCdim}({\cal{H}}) = d\) thì khi chúng ta giới hạn \({\cal{H}}\) vào một tập hữu hạn các điểm dữ liệu \(C \subset {\cal{X}}\), thì kích thước của \({\cal{H}}_C\) (effective size của \({\cal{H}}\)) sẽ có giá trị không quá lớn khoảng \(O(|C|^d)\).
- Bước 2: Khi các tập giả thuyết \({\cal{H}}\) thỏa mãn \({\cal{H}}_C \in O(|C|^d)\) như trên, tức là \(|{\cal{H}}_C|\) chỉ tăng theo hàm đa thức của \(|C|\), ta sẽ chứng minh rằng \({\cal{H}}\) có tính chất hội tụ đều.
-
Kiến thức nền tảng
Định nghĩa 6.9 (Hàm tăng trưởng – growth function): Hàm tăng trưởng của một lớp giả thiết \({\cal{H}}\) là
\(\tau_{\cal{H}}(m) = \max_{C \subset {\cal{X}}:|C| = m} |{\cal{H}}_C|\)
Nói cách khác, \(\tau_{\cal{H}}(m)\) là số cách tối đa để đánh nhãn \(m\) điểm dữ liệu bất kì (khác với restriction là số cách đánh nhãn \(m\) điểm dữ liệu cố định). Hàm tăng trưởng được dùng để đánh giá độ phức tạp của một lớp giả thiết \({\cal{H}}\).
Lưu ý rằng, khi \(\text{VCdim}({\cal{H}}) = d\) thì \(\tau_{\cal{H}}(m) = 2^m~\forall m \leq d\). Cụ thể, khi \(m \leq d\) thì lớp giả thiết \(\mathcal H\) có thể đánh nhãn ít nhất một tập \(m\) điểm dữ liệu một cách tùy ý.
Bổ đề 6.10 (Sauer-Shelah-Perles): nếu \(\text{VCdim}({\cal{H}}) \leq d < \infty\) thì \(\tau_{\cal{H}}(m) \leq \sum_{i=0}^d C(m, i) \forall m\) với \(C(m, i)\) là số tổ hợp chập \(i\) của \(m\). Đặc biệt, khi \(m < d+1\) thì \(\tau_{\cal{H}}(m) \leq (\frac{e m}{d})^d\).
Hệ quả của bổ đề Sauer chính là điều cần chứng minh ở bước 1. Cụ thể, khi \(\text{VCdim}({\cal{H}})\) hữu hạn, thì effective size của \({\cal{H}}\) sẽ nhỏ, và tăng theo hàm đa thức của \(m\), tức kích cỡ mẫu.
Chứng minh: Xem ở đây
Hội tụ đều cho các lớp giả thiết với hàm tăng trưởng nhỏ
Ta có một định lý như sau (tạm gọi là “Định lý về hội tụ đều cho các lớp giả thiết với effective size nhỏ”).
Định lý 6.11: Giả sử \({\cal{H}}\) là một lớp giả thiết và \(\tau_{\cal{H}}\) là hàm tăng trưởng của \({\cal{H}}\). Khi đó, với mọi phân phối dữ liệu \({\cal{D}}\) và \(\delta \in (0, 1)\), thì với xác suất ít nhất là \(1 – \delta\) trên các tập huấn luyện \(S \sim {\cal{D}}^m\), ta có
\(|L_{\cal{D}}(h) – L_S(h)| \leq \frac{4 + \sqrt{\log (\tau_{\cal{H}}(2m))}}{\delta \sqrt{2m}}\)
Chứng minh định lý 6.11: Xem ở đây
Định lý cơ bản của học máy thống kê (định lý 6.7) là hệ quả của định lý 6.11.
Chứng minh định lý 6.7: Ý tưởng chung của chứng minh là
\(m_{\cal{H}}^\text{UC} \leq 4 \frac{16d}{(\delta \epsilon)^2} \log (\frac{16d}{(\delta \epsilon)^2}) + \frac{16d \log (2e/d)}{(\delta \epsilon)^2}\)
Từ bổ đề Sauer, ta có: với \(m > d\), thì \(\tau_{\cal{H}}(2m) \leq (2em/d)^d\). Kết hợp với kết của của “Định lý về hội tụ đều cho các lớp giả thiết có effective size nhỏ”, ta có:
\(P[|L_S(h) – L_{\cal{D}}(h)| \leq \frac{4 + \sqrt{d \log(2em/d)}}{\delta \sqrt{2m}}] \geq 1-\delta\)
Giả sử rằng \(\sqrt{d \log (2em/d)} \geq 4\) (nhằm đơn giản hóa bài toán), ta có:
\(\frac{4 + \sqrt{d \log(2em/d)}}{\delta \sqrt{2m}} \leq \frac{2 \sqrt{d \log(2em/d)}}{\delta \sqrt{2m}}\)
Vì vậy,
\(|L_S(h) – L_{\cal{D}}(h)| \leq \frac{1}{\delta} \sqrt{\frac{2d \log(2em/d)}{m}}\)
Để đảm bảo rằng \(\frac{1}{\delta} \sqrt{\frac{2d \log(2em/d)}{m}}\) đạt tối đa là \(\epsilon\), ta cần:
\(m \geq \frac{2d \log(m)}{(\delta \epsilon)^2} + \frac{2d \log (2e/d)}{(\delta \epsilon)^2}\)
Điều kiện cần để bất đẳng thức trên thỏa mãn là
\(m \geq 4 \frac{2d}{(\delta \epsilon)^2} \log (\frac{2d}{(\delta \epsilon)^2}) + \frac{4 d \log(2e/d)}{(\delta \epsilon)^2} \hspace{1.0cm}\) (4)
LƯU Ý
Cận trên được triển khai cho \(m^\text{UC}_{\cal{H}}\) vừa rồi không phải là cận trên chặt nhất
Chứng minh bất phương trình (4)
Giả sử \(a \geq 1\) và \(b > 0\). Khi đó, \(x \geq 4 a \log (2 a) + 2 b\) sẽ kéo theo \(x \geq a \log(x) + b\)
Chứng minh: đề nghị mọi người xem sách – Lemma A.2 🙂