Như chúng ta đã biết ở các chương trước, còn một số vấn đề mà chúng ta cần tập trung giải quyết, đó là:
Mục tiêu của chúng ta là tìm ra tính chất của tập \(\mathcal{H}\) đảm bảo học được (PAC learnable). Các chương trước chúng ta đã thấy rằng một tập giả thuyết \(\mathcal{H}\) hữu hạn thì học được. Vậy liệu một tập giả thuyết \(\mathcal{H}\) vô hạn có học được hay không và đặc điểm để một lớp giả thuyết \(\mathcal{H}\) học được là gì?
Ở chương này chúng ta sẽ chứng minh rằng một tập giả thiết \(\mathcal{H}\) vô hạn thì vẫn có thể học được. Chúng ta cũng đưa ra 1 điều kiện đủ để học được là \(\mathcal{H}\) có chiều VC hữu hạn.
Ví dụ về Tập giả thuyết vô hạn học được
Để chứng minh 1 tập giả thiết vô hạn \(\mathcal{H}\) mà vẫn học được, ta xem ví dụ như sau:
Bổ đề 6.1: Tập giả thuyết \(\mathcal{H}\) gồm các hàm ngưỡng \[\mathcal H = \{h_a: h_a(x) = \mathbb 1_{x\leq a}\}\] là tập giả thuyết học được (PAC learnable).
Chứng minh cho Bổ đề 6.1:
Giả sử \(a^*\) là ngưỡng của hàm giả thuyết tốt nhất \(h^*(x) = 1_{x<a^*}\), tức là \(L_D(h^*) = 0 \). Gọi \(\mathcal{D}_x\) là phân phối trên miền \(\mathcal{X}\) và \(a_0 < a^* < a_1\) sao cho
\[\underset{ x \sim \mathcal{D}_x}{\mathbb{P}}[x \in (a_0,a^*)] = \underset{ x \sim \mathcal{D}_x}{\mathbb{P}} [x \in (a^*,a_1)] = \epsilon \]
Cho 1 tập huấn luyện \(\mathcal{S}\), gọi \(b_0 = \max\{x:(x,1) \in \mathcal{S} \}\) và \(b_1 = \min\{x:(x,0) \in \mathcal{S} \}\) (\(b_0\) là giá trị lớn nhất của các dữ liệu có nhãn 1, \(b_1\) là giá trị nhỏ nhất của các dữ liệu có nhãn 0).
Gọi \(b_s\) là ngưỡng tìm được khi sử dụng thuật toán ERM, ứng với hàm \(h_S\), suy ra \(b_S \in (b_0,b_1)\). Do đó điều kiện đủ để \(L_D(h_S) \leq \epsilon \) là \(b_0 \geq a_0\) và \(b_1 \leq a_1\).
\[\underset{ S \sim \mathcal{D}^m}{\mathbb{P}}[L_\mathcal{D}(h_S) > \epsilon]
\leq
\underset{ S \sim \mathcal{D}^m}{\mathbb{P}}[b_0 < a_0 \vee b_1 > a_1 ] \]
hay có thể viết lại
\[\underset{ S \sim \mathcal{D}^m}{\mathbb{P}}[L_\mathcal{D}(h_S) > \epsilon]
\leq
\underset{ S \sim \mathcal{D}^m}{\mathbb{P}}[b_0 < a_0] + \underset{ S \sim \mathcal{D}^m}{\mathbb{P}}[b_1 > a_1]
\]
Mà biến cố \(b_0 < a_0\) xảy ra khi và chỉ khi S không thuộc vào khoảng \((a_0,a^*)\), mà mật độ xác suất trên khoảng đó là \(\epsilon\), ta có:
\[\underset{ S \sim \mathcal{D}^m}{\mathbb{P}}[b_0 < a_0] =
\underset{ S \sim \mathcal{D}^m}{\mathbb{P}}[\forall (x,y) \in S,x \notin (a_0,a^*)] = (1-\epsilon)^m \leq \epsilon^{-\epsilon m}
\]
Nếu ta chọn \(m > \log(2/\delta)/\epsilon\) thì biểu thức trên sẽ bé hơn \(\delta/2\). Tương tự với số hạng còn lại ta được \(\underset{ S \sim \mathcal{D}^m}{\mathbb{P}}[L_\mathcal{D}(h_S) > \epsilon]
\leq \delta \) tức là \(\mathcal H\) học được.
Ví dụ trên cho thầy 1 tập giả thuyết vô hạn vẫn có thể học được hay tính hữu hạn của tập giả thuyết không phải là điều kiện cần để học được.