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.
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.
Để 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 formula_1 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 formula_2 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à formula_3. Trong bài toán khoảng, không gian trường hợp là formula_4, trong đó formula_5 là tập hợp số thực.
Một "khái niệm" là một tập hợp con formula_6. 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 formula_3. Trong ví dụ tìm khoảng, một khái niệm có thể là khoảng từ formula_8 đến formula_9. Một "lớp khái niệm" formula_10 là một tập hợp các khái niệm trên tập formula_2. 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 formula_12 là một thủ tục trả về một mẫu formula_13 phân phối theo một phân bố xác suất formula_14 và đồng thời cũng trả về formula_15, bằng 1 nếu formula_16 và 0 trong trường hợp còn lại.
Giả sử tồn tại thuật toán formula_17 sao cho khi thuật toán được gọi thủ tục formula_12 và cung cấp các giá trị formula_19 và formula_20 thì, với xác suất ít nhất formula_21, formula_17 trả về một giả thuyết formula_23 có lỗi tổng quát hóa nhỏ hơn hoặc bằng formula_19 khi các mẫu trong formula_2 được phân phối theo phân bố formula_14. Nếu tồn tại thuật toán như vậy cho mọi khái niệm formula_27, mọi phân bố formula_14 trên formula_2, và mọi formula_30 và formula_31 thì formula_10 là PAC-học được (hay " PAC-học được không phụ thuộc phân bố"). Ta cũng gọi formula_17 là một thuật toán học PAC của formula_10.
Một thuật toán chạy trong thời gian formula_35 nếu nó dùng không quá formula_35 mẫu và chạy trong không quá formula_35 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 formula_38, formula_39 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: