Khi nào việc học từ dữ liệu thực sự hiệu quả? Giải mã Định lý cơ bản của Học thống kê

Trong lĩnh vực Trí tuệ nhân tạo và Học máy, có một câu hỏi mang tính nền tảng: Khi nào việc học từ dữ liệu thực sự hoạt động hiệu quả?

Bạn huấn luyện một mô hình trên một tập dữ liệu mẫu, nó hoạt động rất tốt trên các mẫu đó, và bạn hy vọng nó cũng sẽ hoạt động tốt trên các dữ liệu mới chưa từng thấy. Khi nào thì hy vọng đó được chứng minh là đúng? Câu trả lời nằm ở Định lý cơ bản của Học thống kê (Fundamental Theorem of Statistical Learning).

Định lý này đưa ra một mối tương đương đẹp mắt: Một lớp giả thuyết có thể học được (learnable) nếu và chỉ nếu nó có chiều VC (VC Dimension) hữu hạn. Hãy cùng đi sâu vào các khái niệm toán học định nên lý thuyết này.

Bài toán Học máy: Rủi ro thực tế và Rủi ro thực nghiệm

Để hiểu khi nào học máy hoạt động, trước hết chúng ta cần định nghĩa "học" là gì trong bối cảnh toán học. Chúng ta xét bài toán phân loại nhị phân đơn giản nhất.

Có hai khái niệm quan trọng cần phân biệt:

• Rủi ro thực tế (True Risk) - $L_{\mathcal{D}}(h)$: Là xác suất mà giả thuyết $h$ phân loại sai một mẫu dữ liệu mới được rút ngẫu nhiên từ phân phối thực tế. Đây là con số chúng ta thực sự quan tâm nhưng không bao giờ biết chính xác.
• Rủi ro thực nghiệm (Empirical Risk) - $L_S(h)$: Là tỷ lệ lỗi mà giả thuyết $h$ mắc phải trên tập dữ liệu huấn luyện $S$. Đây là con số chúng ta có thể tính toán được.

Câu hỏi cốt lõi là: Khi nào thì việc có rủi ro thực nghiệm nhỏ ($L_S(h)$) đảm bảo rằng rủi ro thực tế ($L_{\mathcal{D}}(h)$) cũng nhỏ? Nếu rủi ro thực nghiệm nhỏ nhưng rủi ro thực tế lớn, mô hình của chúng ta đang bị quá khớp (overfitting).

Khả năng học PAC (Probably Approximately Correct)

Làm thế nào để định nghĩa một lớp giả thuyết là "có thể học được"? Các nhà khoa học máy tính sử dụng khái niệm PAC Learning (Probably Approximately Correct - Xác suất xấp xỉ đúng).

Một lớp giả thuyết $\mathcal{H}$ là PAC learnable nếu tồn tại một thuật toán $A$ và một hàm $m_{\mathcal{H}}(\epsilon, \delta)$ sao cho với mọi phân phối dữ liệu, nếu kích thước mẫu $m \ge m_{\mathcal{H}}(\epsilon, \delta)$, thì với xác suất ít nhất $1-\delta$:

$$ L_{\mathcal{D}}(A(S)) \le \min_{h \in \mathcal{H}} L_{\mathcal{D}}(h) + \epsilon $$

Trong đó:

• $\epsilon$ (epsilon): Tham số độ chính xác, cho phép sai số trong giới hạn cho phép.
• $\delta$ (delta): Tham số độ tin cậy, là xác suất thất bại mà chúng ta chấp nhận.

Nói một cách đơn giản: Nếu bạn thu thập đủ dữ liệu (tùy thuộc vào $\epsilon$ và $\delta$), bạn có thể tìm ra một mô hình hoạt động tốt gần như tốt nhất có thể trong lớp giả thuyết đó, bất kể dữ liệu được phân phối như thế nào.

Hội tụ đồng nhất (Uniform Convergence)

Để thuật toán đơn giản nhất là ERM (Empirical Risk Minimization - Tối thiểu hóa rủi ro thực nghiệm) hoạt động, chúng ta cần một điều kiện mạnh hơn gọi là hội tụ đồng nhất.

ERM hoạt động bằng cách chọn giả thuyết có lỗi thấp nhất trên tập huấn luyện. Tuy nhiên, nếu lỗi huấn luyện chỉ ước lượng chính xác lỗi thực tế cho một vài giả thuyết nhưng sai lệch lớn cho các giả thuyết khác, ERM có thể chọn nhầm một giả thuyết "tồi tệ" nhưng lại may mắn làm tốt trên tập huấn luyện.

Hội tụ đồng nhất đòi hỏi rằng với đủ dữ liệu, lỗi huấn luyện phải là một ước lượng tốt của lỗi thực tế cho mọi giả thuyết trong lớp $\mathcal{H}$ cùng một lúc.

Chiều VC (VC Dimension) và Định lý Sauer–Shelah

Đối với các lớp giả thuyết hữu hạn (số lượng mô hình hữu hạn), chúng ta có thể sử dụng bất đẳng thức Hoeffding và nguyên lý union bound để chứng minh khả năng học. Tuy nhiên, hầu hết các lớp giả thuyết thú vị trong học máy (như mạng nơ-ron hoặc các siêu phẳng trong không gian chiều cao) là vô hạn.

Đây là lúc Chiều VC phát huy vai trò.

Định nghĩa: Chiều VC của một lớp giả thuyết $\mathcal{H}$, ký hiệu là $\operatorname{VCdim}(\mathcal{H})$, là kích thước của tập hợp điểm lớn nhất có thể bị "bẻ gãy" (shattered) bởi $\mathcal{H}$. Một tập hợp điểm bị bẻ gãy nếu $\mathcal{H}$ có thể thực hiện mọi cách gán nhãn có thể (tất cả $2^m$ trường hợp) trên tập điểm đó.

Nếu chiều VC là $d$, thì lớp giả thuyết đó không thể bẻ gãy bất kỳ tập hợp nào có $d+1$ điểm.

Lemma Sauer–Shelah là một kết quả tổ hợp tuyệt vời nói rằng nếu chiều VC của một lớp là $d$, thì số lượng nhãn khác nhau mà lớp đó có thể tạo ra trên $m$ điểm bị chặn bởi một đa thức:

$$ |\mathcal{H}S| \le \sum{i=0}^{d} \binom{m}{i} \le \left(\frac{em}{d}\right)^d $$

Điều này có ý nghĩa cực kỳ quan trọng: Thay vì tăng trưởng theo cấp số nhân ($2^m$), số lượng hành vi của lớp giả thuyết chỉ tăng theo đa thức ($m^d$) nếu chiều VC hữu hạn. Sự chuyển đổi từ cấp số nhân sang đa thức chính là chìa khóa để học máy trở nên khả thi trên các lớp vô hạn.

Đối xứng hóa (Symmetrization) và Chặn tổng quát

Để chứng minh Định lý cơ bản, chúng ta cần giải quyết một vấn đề khó: Lỗi thực tế $L_{\mathcal{D}}(h)$ phụ thuộc vào phân phối dữ liệu chưa biết $\mathcal{D}$.

Kỹ thuật đối xứng hóa (symmetrization) giải quyết vấn đề này bằng một "mẫu ảo" (ghost sample). Thay vì so sánh lỗi huấn luyện với lỗi thực tế (vô hình), chúng ta so sánh lỗi huấn luyện trên tập $S$ với lỗi huấn luyện trên một tập độc lập khác $S'$. Nếu mô hình quá khớp trên $S$, rất có thể nó sẽ hoạt động kém trên $S'$.

Kỹ thuật này cho phép chúng ta cố định dữ liệu và chỉ randomize việc chia dữ liệu vào hai tập, từ đó áp dụng các bất đẳng thức tập trung.

Kết luận: Định lý cơ bản của Học thống kê

Tất cả các mảnh ghép trên—bất đẳng thức Hoeffding, Lemma Sauer–Shelah, và đối xứng hóa—kết hợp lại để tạo ra kết quả cuối cùng.

Định lý: Một lớp giả thuyết $\mathcal{H}$ là PAC learnable nếu và chỉ nếu $\operatorname{VCdim}(\mathcal{H})$ hữu hạn.

Hơn nữa, chúng ta có một chặn tổng quát (generalization bound) cụ thể: Với xác suất cao, sự khác biệt giữa lỗi thực nghiệm và lỗi thực tế bị chặn bởi:

$$ \sqrt{\frac{C \cdot d \log(m/d)}{m}} $$

Trong đó $d$ là chiều VC và $m$ là số lượng mẫu.

Điều này giải thích tại sao các mô hình phức tạp (có chiều VC lớn) cần nhiều dữ liệu hơn để học, và tại sao nếu mô hình quá phức tạp so với dữ liệu (quá khớp), khả năng tổng quát hóa sẽ kém. Định lý cơ bản của Học thống kê chính là "bảo chứng" toán học đảm bảo rằng việc học từ dữ liệu không phải là phép màu, mà là một khoa học chính xác.