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:
-
-
-
- Tồn tại hàm \(f:\mathcal{X} \rightarrow \{0,1\}\) mà hàm lỗi \(\mathcal{L}_D(f) = 0\)
- 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:
-
- Chỉ ra rằng có một tập \(\mathcal{C}\) kích thước \(m\) mà \(\mathcal{H}\) chia tách được
- 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.