Học PAC

Trong lý thuyết học tính toán, học PAC (viết tắt từ tên tiếng Anh probably approximately correct learning, tạm dịch học đúng xấp xỉ với xác suất cao) là một mô hình các thuật toán học máy. Nó được đề xuất năm 1984 bởi Leslie Valiant.^[1]

Trong mô hình này, thuật toán học nhận được một loạt các mẫu được sinh ngẫu nhiên cùng với nhãn của chúng, và phải chọn một hàm tổng quát hóa (được gọi là một giả thuyết) trong một lớp các hàm cho trước. Mục tiêu là,với xác suất cao, hàm được chọn có lỗi tổng quát hóa thấp. Thuật toán học phải học được với tỉ lệ xấp xỉ, xác suất thành công, và phân bố xác suất của các mẫu bất kì.

Mô hình sau đó được mở rộng cho cả trường hợp có nhiễu (có mẫu được gắn nhãn sai).

Một đổi mới quan trọng của mô hình PAC là việc đưa các khái niệm trong lý thuyết độ phức tạp tính toán vào học máy. Cụ thể hơn, thuật toán học phải tìm một hàm hiệu quả (có thời gian và bộ nhớ bị chặn bởi một đa thức của kích thước mẫu), và thuật toán học cũng phải là thuật toán hiệu quả (số ví dụ cần dùng bị chặn bởi một đa thức của kích thước khái niệm cần học, có thể phụ thuộc tỉ lệ xấp xỉ và xác suất thành công).

Định nghĩa và các thuật ngữ liên quan

Để định nghĩa khái niệm PAC-học được, trước hết cần định nghĩa một số khái niệm liên quan.^[2][3]

Để minh họa cho định nghĩa, ta sẽ sử dụng hai ví dụ. Ví dụ thứ nhất là bài toán nhận dạng chữ viết được cho dưới dạng một mảng ${\displaystyle n}$ bit. Ví dụ thứ hai là bài toán tìm một khoảng xếp loại sao cho các điểm trong khoảng là dương tính và ngoài khoảng là âm tính.

Đặt ${\displaystyle X}$ là tập hợp tất cả các mã hóa của các mẫu, gọi là không gian trường hợp, và mỗi trường hợp có một độ dài nhất định. Trong bài toán nhận dạng chữ viết, không gian trường hợp là ${\displaystyle X=\{0,1\}^{n}}$. Trong bài toán khoảng, không gian trường hợp là ${\displaystyle X=\mathbb {R} }$, trong đó ${\displaystyle \mathbb {R} }$ là tập hợp số thực.

Một khái niệm là một tập hợp con ${\displaystyle c\subset X}$. Trong ví dụ nhận dạng chữ viết, một khái niệm có thể là tập hợp tất cả các mã hóa của chữ cái "P" trong ${\displaystyle X=\{0,1\}^{n}}$. Trong ví dụ tìm khoảng, một khái niệm có thể là khoảng từ ${\displaystyle \pi /2}$ đến ${\displaystyle {\sqrt {10}}}$. Một lớp khái niệm ${\displaystyle C}$ là một tập hợp các khái niệm trên tập ${\displaystyle X}$. Trong ví dụ nhận dạng chữ viết, đây có thể là tập hợp các tập hợp con gồm các dãy bit mã hóa các nét vẽ có độ rộng bằng 1.

Đặt ${\displaystyle EX(c,D)}$ là một thủ tục trả về một mẫu ${\displaystyle x}$ phân phối theo một phân bố xác suất ${\displaystyle D}$ và đồng thời cũng trả về ${\displaystyle c(x)}$, bằng 1 nếu ${\displaystyle x\in c}$ và 0 trong trường hợp còn lại.

Giả sử tồn tại thuật toán ${\displaystyle A}$ sao cho khi thuật toán được gọi thủ tục ${\displaystyle EX(c,D)}$ và cung cấp các giá trị ${\displaystyle \epsilon }$ và ${\displaystyle \delta }$ thì, với xác suất ít nhất ${\displaystyle 1-\delta }$, ${\displaystyle A}$ trả về một giả thuyết ${\displaystyle h\in C}$ có lỗi tổng quát hóa nhỏ hơn hoặc bằng ${\displaystyle \epsilon }$ khi các mẫu trong ${\displaystyle X}$ được phân phối theo phân bố ${\displaystyle D}$. Nếu tồn tại thuật toán như vậy cho mọi khái niệm ${\displaystyle c\in C}$, mọi phân bố ${\displaystyle D}$ trên ${\displaystyle X}$, và mọi ${\displaystyle 0<\epsilon <1/2}$ và ${\displaystyle 0<\delta <1/2}$ thì ${\displaystyle C}$ là PAC-học được (hay PAC-học được không phụ thuộc phân bố). Ta cũng gọi ${\displaystyle A}$ là một thuật toán học PAC của ${\displaystyle C}$.

Một thuật toán chạy trong thời gian ${\displaystyle t}$ nếu nó dùng không quá ${\displaystyle t}$ mẫu và chạy trong không quá ${\displaystyle t}$ bước. Một lớp khái niệm là PAC-học được hiệu quả nếu nó là PAC-học được bởi một thuật toán chạy trong thời gian đa thức của ${\displaystyle 1/\epsilon }$, ${\displaystyle 1/\delta }$ và chiều dài mỗi trường hợp.

Khái niệm tương đương

Nếu giả sử một số điều kiện chính quy, thì các điều kiện sau là tương đương:

1. Lớp khái niệm C là PAC-học được.
2. Số chiều VC của C là hữu hạn.
3. C là một lớp Glivenko-Cantelli đều.

Ghi chú

1. L. Valiant. A theory of the learnable. Communications of the ACM, 27, 1984.
2. Kearns & Vazirani 1994, tr. 1–12
3. Balas Kausik Natarajan, Machine Learning, A Theoretical Approach, Morgan Kaufmann Publishers, 1991

Tham khảo

• Kearns, M.; Vazirani, U. (1994), An Introduction to Computational Learning Theory, MIT Press
• D. Haussler. Overview of the Probably Approximately Correct (PAC) Learning Framework Lưu trữ 2011-09-28 tại Wayback Machine.