1241941
Học PAC
https://vi.wikipedia.org/wiki?curid=1241941
Title: Học PAC
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: