Định lý 6.7 – Định lý cơ bản của Học máy thống kê
Phiên bản gốc
Giả sử ta có một lớp giả thiết \({\cal{H}}\) và một hàm lỗi \(0-1\). Khi đó, ta có các mệnh đề sau là tương đương:
-
-
- \({\cal{H}}\) có thuộc tính hội tụ đều
- Các thuật toán ERM (Tối thiểu lỗi thực nghiệm) là thuật toán học agnostic PAC cho \({\cal{H}}\)
- \({\cal{H}}\) có tính chất học được kiểu agnostic PAC
- \({\cal{H}}\) có tính chất học được kiểu PAC
- Các thuật toán ERM là thuật toán học PAC cho \({\cal{H}}\).
- \({\cal{H}}\) có VC-dimension hữu hạn
-
Phiên bản định lượng
Giả sử lớp giả thiết \({\cal{H}}\) có VC-dimension là \(d < \infty\), khi đó độ phức tạp mẫu để \({\cal{H}}\) có tính chất hội tụ đều, cũng như agnostic PAC learnability là \(\Theta(\frac{d + \log (1/\delta)}{\epsilon^2})\) với \((1 – \delta)\) và \(\epsilon\) lần lượt là “độ tự tin” và “tỉ lệ lỗi” mong muốn.
Bên cạnh đó, độ phức tạp mẫu để \({\cal{H}}\) có tính chất PAC learnability, biết trước rằng giả thiết tối ưu trong \({\cal{H}}\) có tỉ lệ lỗi bằng \(0\), là \(\Theta(\frac{d + \log (1/\delta)}{\epsilon})\).
LƯU Ý
- Định lý cơ bản về học máy thống kê nêu trên có thể thỏa mãn đối với một số các bài toán học máy khác, bên cạnh bài toán phân lớp nhị phân, tuy nhiên không phải thỏa mãn đối với tất cả bài toán học máy.
- Khả năng học (learnability) đôi khi cũng có thể xảy ra khi lớp giả thiết không có tính chất hội tụ đều.
- Trong một số trường hợp, ERM rule có thể thất bại, tuy nhiên khả năng học (learnability) vẫn hoàn toàn có thể xảy ra đối với các mô hình học máy (learning rule) khác.
Nhắc lại kiến thức
Hàm lỗi \(0-1\):
Trong bài toán phân lớp nhị phân, giả sử ta có giá trị dự đoán \(h\) và giá trị thực tế \(y\), hàm lỗi \(0-1\) được định nghĩa như sau:
\(L(y, h) = \begin{cases} 0 & y = h \\ 1 & y \neq h\end{cases}\)
Đối với một tập các giá trị thực và giá trị dự đoán tương ứng \(S = \{(y^{(i)}, h^{(i)})\}_{i=1}^n\), hàm lỗi \(0-1\) được định nghĩa như sau:
\(L(S) = \frac{1}{n} \sum_i L(y^{(i)}, h^{(i)})\)
Tức, trung bình cộng của các \(L(y^{(i)}, h^{(i)})\) trong tập \(S\).
Mô hình Empirical Risk Minimization (ERM)
Đây là mô hình tối ưu với mục đích là tìm ra giả thiết tối ưu trong tập \({\cal{H}}\) đối với dữ liệu huấn luyện \(S\). Trong bài này, chúng ta giả sử rằng giả thiết tối ưu \(h_S\), đối với tập \(S\), trong \({\cal{H}}\) luôn được tìm thấy bởi mô hình ERM.
\(h_S = \arg\min_{h\in\mathcal H} L_S(h)\)
Xem chi tiết tại đây
Định lý “không có bữa trưa miễn phí”
Theo định lý “Không có bữa trưa miễn phí”, nếu một lớp giả thiết \({\cal{H}}\) (VD: một mô hình mạng nơ-ron nhân tạo) có VC-dimension vô hạn thì tập giả thiết này không thể học được (not learnable).
Xem chi tiết tại đây
Tính chất hội tụ đều của lớp giả thiết
Một lớp giả thiết \({\cal{H}}\) được cho là có tính chất hội tụ đều nếu khi kích thước tập dữ liệu huấn luyện đạt tới một mức nào đó thì, với xác suất cao là \(1 – \delta\), ta sẽ có được một tập dữ liệu \(S\) phản ánh được khả năng của \({\cal{H}}\) trên phân bố dữ liệu \(\mathcal D\), hay còn gọi là tập đại diện \(\epsilon\). Nói cách khác, \(|L_{\cal{D}}(h) – L_S(h)| \leq \epsilon\) với mọi giả thuyết \(h \in \mathcal H\), trong đó có \(h_S\) là giả thiết được tìm ra bởi một mô hình học ERM.
Xem chi tiết tại đây
PAC learnability – khả năng học “có thể gần đúng”
Học được kiểu PAC (Probably Approximate Correct learnable) – khả năng học có thể gần đúng (viết tắt là học được) là một tính chất quan trọng của một lớp giả thuyết. Nó cho biết với xác suất cao, chúng ta có thể học được giả thiết xấp xỉ giả thuyết tốt nhất \(h^*\) với lớp giả thiết \({\mathcal{H}}\) hay không.
Agnostic PAC learnability (khả năng học có thể gần đúng trong trường hợp bất khả tri): khả năng học được một giả thiết tốt nhất, hoặc xấp xỉ tốt nhất, trong tập các giả thiết \({\cal{H}}\) hay không.
PAC learnability (khả năng học có thể gần đúng) là trường hợp đặc biệt của Agnostic PAC learnability, khi này, chúng ta đưa ra thêm giả định rằng giả thiết tối ưu trong tập \({\cal{H}}\) có thể đưa ra dự đoán chính xác 100% với mọi dữ liệu thực tế, tức hàm lỗi thực tế bằng \(0\).
Chiều VC
VC-dimension của một lớp giả thiết \({\cal{H}}\) được định nghĩa là số điểm dữ liệu tối đa mà tập giả thuyết \({\cal{H}}\) có thể chia tách được, sử dụng một trong những giả thiết trong \({\cal{H}}\).
Xem chi tiết tại đây.