Lý thuyết học máy tính toán

Lý thuyết học máy tính toán nghiên cứu những khái niệm nào có thể được học một cách hiệu quả từ các ví dụ, coi việc học như một vấn đề về tính toán và độ phức tạp của mẫu.

Definition

Lý thuyết học máy tính toán là nghiên cứu về các tài nguyên, về dữ liệu và tính toán, cần thiết để học các khái niệm từ các ví dụ; trong mô hình gần đúng có thể đúng, một lớp khái niệm có thể học được nếu một thuật toán có thể, từ một số lượng mẫu đa thức và trong thời gian đa thức, đưa ra một giả thuyết chính xác với xác suất cao.

Scope

Chủ đề này bao gồm các mô hình chính thức về khả năng học: mô hình gần đúng có thể đúng (probably approximately correct) đặt ra câu hỏi khi nào một khái niệm có thể được học với độ chính xác cao và xác suất cao từ số lượng ví dụ và tính toán đa thức, các mô hình giới hạn lỗi và học trực tuyến, khả năng học yếu so với khả năng học mạnh và tăng cường (boosting), và các kết nối với độ phức tạp tính toán. Nó đề cập đến cả tính khả thi về mặt thống kê và thuật toán của việc học.

Core questions

• Những lớp khái niệm nào có thể được học một cách hiệu quả từ các ví dụ?
• Việc học một khái niệm đòi hỏi bao nhiêu dữ liệu và tính toán?
• Mối quan hệ giữa khả năng học yếu và mạnh là gì?
• Khả năng học kết nối với độ phức tạp tính toán như thế nào?

Key theories

Học gần đúng có thể đúng

Mô hình của Valiant định nghĩa một lớp khái niệm là có thể học được khi một thuật toán hiệu quả có thể tạo ra, với xác suất cao, một giả thuyết có lỗi thấp từ số lượng ví dụ đa thức, biến khả năng học thành một câu hỏi tính toán chính xác.

Khả năng học yếu và tăng cường (boosting)

Một kết quả trung tâm cho thấy rằng bất kỳ lớp nào có thể học được tốt hơn một chút so với ngẫu nhiên cũng có thể học được mạnh mẽ, điều này đã trực tiếp dẫn đến các thuật toán boosting khuếch đại những người học yếu thành những người học chính xác.

Giới hạn thống kê và tính toán

Khả năng học bị giới hạn bởi cả độ phức tạp của mẫu, gắn liền với các biện pháp năng lực, và bởi độ khó tính toán, do đó một số lớp có thể học được về mặt thống kê nhưng lại không thể xử lý được về mặt tính toán.

Clinical relevance

Lý thuyết học máy tính toán đưa ra nền tảng chính thức cho những gì các thuật toán học có thể và không thể đạt được, đồng thời trực tiếp truyền cảm hứng cho các phương pháp thực tế, đáng chú ý nhất là boosting, xuất phát từ câu hỏi liệu những người học yếu có thể được kết hợp thành những người học mạnh hay không; nó định hình việc học như một ngành khoa học tính toán nghiêm ngặt.

History

Valiant đã giới thiệu mô hình gần đúng có thể đúng vào năm 1984, đưa ra một định nghĩa tính toán chính xác cho việc học và thành lập lĩnh vực này. Các công trình tiếp theo đã thiết lập các đặc điểm phức tạp của mẫu, sự tương đương giữa khả năng học yếu và mạnh đã thúc đẩy boosting, và các kết quả khó khăn cho thấy giới hạn tính toán của việc học.

Key figures

• Leslie Valiant
• Michael Kearns
• Robert Schapire

Seminal works

• valiant1984
• kearns1994
• vapnik1995

Frequently asked questions

Gần đúng có thể đúng nghĩa là gì?

Nó có nghĩa là, với xác suất cao trên mẫu ngẫu nhiên, người học đưa ra một giả thuyết gần đúng, tức là có lỗi nhỏ trên dữ liệu trong tương lai. Khả năng học đòi hỏi phải đạt được điều này từ một số lượng ví dụ và một lượng tính toán chỉ tăng theo đa thức.

Lý thuyết học đã dẫn đến boosting như thế nào?

Các nhà nghiên cứu đã đặt câu hỏi liệu một người học chỉ tốt hơn một chút so với đoán ngẫu nhiên có thể được biến thành một người học có độ chính xác cao hay không. Bằng chứng cho thấy khả năng học yếu và mạnh là tương đương có tính xây dựng, và cấu trúc đó đã trở thành các thuật toán boosting được sử dụng rộng rãi trong thực tế.