UML 6.1 Tập giả thuyết vô hạn học được (PAC learnable)

This entry is part 1 of 6 in the series understanding machine learning chapter 6
\(\)

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.