Định nghĩa (so sánh giả thiết):hàm giả thiết \(h\) là \(\epsilon,\delta\)-không tồi so với giả thuyết \(h’\) nếu
\[\mathbb P\left[L_{\mathcal D}(h) \leq L_{\mathcal D}(h’)+\epsilon\right]\geq 1-\delta\]
Trong trường hợp học kiểu PAC (hoặc agnostic PAC), số mẫu dữ liệu \(m\) chỉ phụ thuộc vào \(\epsilon,\delta\). Trong chương này, ta xem xét trường hợp số mẫu dữ liệu phụ thuộc vào cả giả thiết mục tiêu, tức là \(m_{\mathcal H} = m_{\mathcal H}(\epsilon,\delta, h) \).
Định nghĩa 7.1: Lớp giả thiết \(\mathcal H\) học được không đồng nhất nếu có thuật toán \(A\) và một hàm \(m_{\mathcal H}^{NUL}(\epsilon,\delta, h)\) sao cho với mọi \(\epsilon,\delta\in(0,1)\), với mọi \(h\in\mathcal H\), khi \(m \geq m_{\mathcal H}^{NUL}(\epsilon,\delta, h)\), ta có
\[\mathbb P_{S\sim\mathcal D^m}\left[L_{\mathcal D}(A(S)) \leq L_{\mathcal D}(h)+\epsilon\right] \geq 1-\delta\]
Định lý 7.2: Điều kiện cần và đủ để lớp giả thiết nhị phân \(\mathcal H\) học được không đồng nhất là \(\mathcal H\) là hợp của một tập đếm được (countable) các tập giả thiết học được kiểu PAC (agnostic PAC learnable).
Định lý 7.3: Giả sử lớp giả thiết \(\mathcal H = \cup_{n\in\mathbb N}\mathcal H_n\) mà mỗi \(\mathcal H_n\) có tính chất hội tụ đều, khi đó \(\mathcal H\) học được không đồng nhất.
Chứng minh định lý 7.2:
Nếu \(\mathcal H = \cup_{n\in\mathbb N}\mathcal H_n\) mà \(\mathcal H_n\) học được kiểu PAC. Ta có \(\mathcal H_n\) là các tập giả thiết có tính chất hội tụ đều (theo định lý cơ bản của học máy thống kê). Do đó theo định lý 7.3, \(\mathcal H\) học được không đồng nhất.
Nếu \(\mathcal H\) học được không đồng nhất bằng thuật toán \(A\), ta viết \(\mathcal H = \cup_{n\in\mathbb N}\mathcal H_n\), trong đó \(\mathcal H_n = \{h\in\mathcal H: m_{\mathcal H}^{NUL}(1/8,1/7, h)\leq n\}\). Theo định lý “no-free-lunch”, chiều VC của \(\mathcal H_n\) phải hữu hạn, tức là nó có thể học kiểu PAC (theo định lý cơ bản của học máy thống kê).
Ví dụ 7.1: Xét lớp giả thiết \(\mathcal H = \cup_{n\in\mathbb N}\mathcal H_n\) trong đó \(\mathcal H_n = \{h: h(x) = \mathrm{sign}(p(x))\}\) với \(p(x)\) là đa thức bậc \(n\) trên \(\mathbb R\). Có thể tính được chiều VC của \(\mathcal H_n\) là \(n+1\) trong khi chiều VC của \(\mathcal H\) là \(\infty\). Như vậy \(\mathcal H\) không học được kiểu PAC nhưng học được không đồng nhất theo định lý 7.3.