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