Author: Nguyễn Văn Phi

UML 6.2. Chiều VC của tập giả thuyết

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

Chúng ta sẽ tiếp cận điều kiện cần cho PAC learnable bằng định nghĩa về giới hạn \(\mathcal{H}\) vào \(\mathcal{C}\) và tính khả tách.

Định nghĩa 6.2 (Giới hạn \(\mathcal{H}\) vào \(\mathcal{C}\)): Giả sử \(\mathcal{H}\) là một tập giả thuyết (ánh xạ từ \(\mathcal{X}\) sang \(\{0,1\}\) và gọi \(\mathcal{C} = \{ c_1,….c_m \} \in \mathcal X\) là một tập các mẫu dữ liệu từ \(\mathcal X\). Giới hạn \(\mathcal{H}\) vào \(\mathcal{C}\) là tập các phần tử của \(\{0,1\}^m\) có được khi sử dụng các giả thuyết trong \(\mathcal H\) trên các mẫu dữ liệu trong \(\mathcal C\)
\[ \mathcal{H}_{\mathcal C} = \{(h(c_1),…,h(c_m)): h \in \mathcal{H}\} \subseteq \{0,1\}^m\]

Định nghĩa 6.3 (Tính khả tách): Tập giả thuyết \(\mathcal{H}\) chia tách được tập hữu hạn \(\mathcal{C} \subset \mathcal{X}\) nếu giới hạn của \(\mathcal{H}\) vào \(\mathcal{C}\) là tất cả các chuỗi nhị phân có độ dài \(m\). Tức là

\[ \mathcal{H}_{\mathcal C} = \{0,1\}^m\]

Ví dụ 6.2. Gọi \(\mathcal{H}\) là tập các hàm ngưỡng trên \(\mathbb{R}\).

  • Xét tập dữ liệu có 1 phần tử, \(\mathcal{C} = \{c_1\}\). Nếu lấy \(a = c_1 + 1\) thì \(h_a(c_1) = 1\). Nếu lấy \(a = c_1 – 1\) thì \(h_a(c_1) = 0\) nên \(\mathcal{H}_{\mathcal C} = \{0,1\}\). Tức là \(\mathcal{H}\) chia tách được \(\mathcal{C}\).
  • Xét tập dữ liệu có 2 phần tử, \(\mathcal{C} = \{c_1,c_2\}\) và \(c_1 < c_2\). Dễ thấy không tồn tại hàm \(h \in \mathcal{H}\) để \( (h(c_1), h(c_2)) = (0,1) \). Vì nếu hàm \(h\) cho \(h(c_1) = 0\) thì rõ ràng \(h(c_2) = 0\). Do đó \(\mathcal{H}\) không chia tách được \(\mathcal{C}\).

VC Dimension – No Free Lunch

Chúng ta sẽ kết hợp VC-Dimension và định lý no free lunch ở chương trước, đầu tiên chúng ta sẽ nhắc lại định lý no free lunch

No free lunch: Với thuật toán học \(\mathcal A\) bất kỳ trên tập tất cả các giả thuyết, gọi \(m\) là số nhỏ hơn một nửa số phần tử của \(\mathcal{X}\), là kích thước tập huấn luyện. gọi \(\mathcal{D}\) là phân bố \(\mathcal{X}\) \times \{0,1\} sao cho:

        1. Tồn tại hàm \(f:\mathcal{X} \rightarrow \{0,1\}\) mà hàm lỗi \(\mathcal{L}_D(f) = 0\)
        2. Với xác suất ít nhất 1/7 có thể chọn được tập \(\mathcal S\) từ \(\mathcal{D}^m\) sao cho \(\mathcal{L}_D(A(S)) \geq 1/8\)

Chứng minh của định lý cho thấy không thể học một tập \(\mathcal{C}\)  có kích thuớc \(2m\) nếu tập huấn luyện của nó chỉ có kích thước là \(m\).

Bây giờ chúng ta sẽ phát biểu lại định lý no free lunch với tính khả tách của \(\mathcal{H}\).

Hệ quả 6.4 (Định lý No Free Lunch): Gọi \(\mathcal{H}\) là một tập giả thuyết ánh xạ từ \(\mathcal{X}\) sang \(\{0,1\}\) và \(m\) là kích thước tập huấn luyện. Giả sử có tập \(\mathcal{C} \subset \mathcal{X}\) có kích cỡ \(2m\) có thể chia tách được bởi \(\mathcal{H}\). Với mọi thuật toán học, \(\mathcal A\), tồn tại phân bố \(\mathcal{D}\) trên \(\mathcal{X} \times \{0,1\}\) và hàm gắn nhãn \(h \in \mathcal{H}\) sao cho \(L_\mathcal{D}(h) = 0\) nhưng với xác suất ít nhất 1/7 có thể chọn được tập \(\mathcal S\) từ \(\mathcal{D}^m\) sao cho \(\mathcal{L}_D(A(S)) \geq 1/8\)

Định lý cho thấy \(\mathcal{H}\) không thể học được  khi \(\mathcal{H}\) chia tách được \(\mathcal{C}\) có kích thước 2m với kích thước tập huấn luyện là \(m\).

Định nghĩa 6.5 (chiều VC – Vapnik–Chervonenkis Dimension): Chiều VC của tập giả thiết \(\mathcal{H}\), ký hiệu \(\mathrm{VCdim}(\mathcal{H})\), là kích thước tối đa của tập \(\mathcal{C} \subset \mathcal{X}\) có thể chia tách được bởi \(\mathcal{H}\). Nếu \(\mathcal{H}\) có thể chia tách được mọi tập \(\mathcal C\) thì ta nói \(\mathcal{H}\) có chiều VC vô hạn.

Định lý 6.6: Nếu \(\mathcal{H}\) có chiều VC vô hạn thì \(\mathcal{H}\) không học được.

Chứng minh: Vì (\(\mathcal{H}\)) có chiều VC vô hạn, bất kỳ tập huấn luyện có kích thước \(m\) nào thì luôn có tập phân tách được có kích thước \(2m\), do hệ quả 6.4 (No Free Lunch), ta có điều phải chứng minh.

Phần sau sẽ chứng minh rằng nếu hữu hạn VC-dim thì (\(\mathcal{H}\)) PAC learnable.

Một số ví dụ về chiều VC của một tập giả thuyết

Để tính \(\mathrm{VCdim}(\mathcal{H})\) ta thực hiện 2 bước:

    1. Chỉ ra rằng có một tập \(\mathcal{C}\) kích thước \(m\) mà \(\mathcal{H}\) chia tách được
    2. Mọi tập \(\mathcal{C}\) kích thước \(m+1\) thì \(\mathcal{H}\) không chia tách được.

Ví dụ về hàm ngưỡng. Ví dụ 6.2 cho thấy tập \(\mathcal H\) các hàm ngưỡng có chiều VC bằng 1.

Ví dụ hàm khoảng (interval). Gọi \(\mathcal{H}\) là tập các hàm khoảng trên \(\mathbb{R}\), \(\mathcal{H} = \{h_{a,b}: a,b \in \mathbb{R}, a < b\}\) sao cho \(h_{a,b}(x) = 1_{x\in(a,b)}\).

Khi \(\mathcal{C} = \{c_1,c_2\}\)

      •  \(h_{c_1-2,c_1-1}\) cho \((0,0)\)
      • \(h_{(c_1+c_2)/2, c_2+1}\) cho \((0,1)\)
      • \(h_{c_1-1, (c_1+c_2)/2}\) cho \((1,0)\)
      •  \(h_{c_1-1, c_2+1}\) cho \((1,1)\)

Tức là \(\mathcal{H}\) chia tách được \(\mathcal{C}\) bất kỳ có kích thước bằng 2 hay \(\mathrm{VCdim}(\mathcal{H}) \geq 2\)

Tuy nhiên với \(\mathcal{C} = \{c_1,c_2,c_3\}\) thì \(\mathcal{H}\) không  thể ánh xạ \(\mathcal{C} \rightarrow \{1,0,1\}\) nên \(\mathcal{H}\) không phân tách được \(\mathcal{C}\) có 3 phần tử.

Kết luận: chiều VC của lớp các hàm khoảng bằng 2.

Chiều VC và số tham số của mô hình

Ta thường thấy \(\mathrm{VCdim}(\mathcal{H})\) thường bằng số tham số của \(\mathcal{H}\). Tuy nhiên điều này không phải lúc nào cũng đúng, một ví dụ là khi \(\mathcal{X} = \mathbb{R}\) với \(\mathcal{H} = \{h_{\theta} = \lceil 0.5 sin(\theta x)\rceil: \theta \in \mathbb R\} \) thì \(\mathcal H\) có chiều VC vô hạn.

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.