- Một số ký hiệu dùng trong phần này
\(Z\) – tập các mẫu dữ liệu
\(\mathcal H\) – không gian giả thuyết rút gọn (mô hình của hàm dự đoán \(h\))
\(\ell\) – hàm lỗi \(\ell: \mathcal H \times Z \rightarrow \mathbb R^+\)
\(\mathcal D\) – phân bố trên \(Z\) của dữ liệu
\(L_S(h)\) – rủi ro thực nghiệm (lỗi) trên tập dữ liệu \(S\)
\(L_{\mathcal D}(h)\) – rủi ro kỳ vòng trên phân bố dữ liệu \(\mathcal D\) - Chương trước đã chỉ ra rằng với giả định khả thi (realizability assumption), tập giả thuyết hữu hạn bất kỳ nào cũng có thể học được PAC (PAC learnable).
- Trong chương này, sẽ giới thiệu một công cụ tổng quát -hội tụ đều (uniform convergence) và áp dụng nó để chỉ ra rằng bất kỳ tập giả thuyết hữu hạn nào cũng có thể học được trong mô hình agnostic PAC với hàm lỗi tổng quát, khi phạm vi hàm lỗi bị giới hạn.
- Với một tập giả thuyết \(\mathcal{H}\), mô hình học ERM hoạt động như sau: Với một tập huấn luyện, thuật toán huấn luyện \(A\) đánh giá rủi ro thực nghiệm (hoặc lỗi) của mỗi hàm dự đoán (giả thuyết) \(h\) trong \(\mathcal{H}\) trên tập huấn luyện \(S\) và đưa ra một phần tử \(A(S) \in \mathcal{H}\) tối thiểu hóa rủi ro thực nghiệm này.
Chúng ta muốn khi hàm dự đoán \(h\) giảm thiểu rủi ro thực nghiệm đối với \(S\) thì \(h\) cũng làm giảm thiểu rủi ro kỳ vọng trên phân bố dữ liệu \(\mathcal D\). Nói cách khác, rủi ro thực nghiệm cần phải gần với rủi ro kỳ vọng trên tất cả các giả thuyết trong tập giả thuyết. - Định nghĩa 4.1 (\(\epsilon\)-representative sample-mẫu \(\epsilon\)-đại diện): Một tập huấn luyện \(S\) được gọi là \(\epsilon\)-đại diện (đối với miền \(Z\), tập giả thuyết \(\mathcal{H}\), hàm lỗi \(\ell \) và phân bố \(\mathcal{D}\)) nếu: \[\forall h \in \mathcal{H}, |L_S(h)-L_D(h)| \leq \epsilon \]
- Bổ đề sau chỉ ra rằng, bất cứ khi nào mẫu huấn luyện là (\(\frac{\epsilon}{2}\) – đại diện), thì thuật toán học ERM đảm bảo trả về một hàm dự đoán (giả thuyết) tốt.
- Bổ đề 4.2 Giả sử rằng một tập huấn luyện \(S\) là \(\frac{\epsilon}{2}\)-đại diện đối với \(\langle Z, \mathcal{H}, \ell, \mathcal{D}\rangle\), thì kết quả của thuật toán học \(ERM_{\mathcal H}\): \(h_S \in \underset{h \in \mathcal H}{\arg\min\ L_S(h)}\), thỏa mãn\[L_{\mathcal{D}} (h_S) \leq \underset{ h \in \mathcal {H} }{\min L_{\mathcal D } (h) } + \epsilon\]
Chứng minh: với mọi \(h \in \mathcal{H}\),
\(L_{\mathcal{D}} (h_S) \leq L_{S} (h_S) + \frac{\epsilon}{2} \leq L_{S} (\mathcal{h}) + \frac{\epsilon}{2} \leq L_{\mathcal{D}} (h) + \frac{\epsilon}{2} + \frac{\epsilon}{2} = L_{\mathcal{D}} (h) + \epsilon \)
– Bất đẳng thức 1 và 3 là do giả định \(S\) là \(\frac{\epsilon}{2} \)-đại diện
– Bất đẳng thức thứ 2 là do \(h_S\) là một dự đoán \(ERM\) thì \(L_{S} (h_S) \leq L_{S} (h)\)
- Định nghĩa 4.3 (Hội tụ đều): Một tập giả thuyết \(\mathcal{H}\) có tính chất hội tụ đều đối với \(\langle Z, \ell\rangle \) nếu tồn tại một hàm \(m_\mathcal{H}^{UC}: (0,1)^2 \rightarrow \mathbb{N}\) sao cho với mọi \(\epsilon, \delta \in (0, 1)\) và với mọi phân bố xác xuất \(\mathcal{D}\) trên \(Z\), nếu \(S\) là tập mẫu của \(m \geq \mathcal{m}_{H}^{UC} (\epsilon, \delta)\) phần tử được lấy độc lập với nhau trong tập \(\mathcal{D}\) thì với xác xuất ít nhất \(1-\delta\), \(S\) là tập \(\epsilon\)-đại diện.
- Hệ quả 4.4 Nếu \(\mathcal H\) có thuộc tính hội tụ đều với hàm \(m_\mathcal{H}^{UC}\) thì có thể học Xấp xỉ đúng với xác xuất cao (Agnostically PAC learnable) với độ phức tạp mẫu \(m_\mathcal{H} (\epsilon, \delta) \leq m_\mathcal{H}^{UC} (\frac{\epsilon}{2}, \delta)\). Hơn nữa, trong trường hợp này, thuật toán học \(ERM_\mathcal{H}\) là thuật toán học agnostic PAC trên \(\mathcal{H}\).