“Học máy” từ góc nhìn của lý thuyết tính toán, mô hình nhất quán
Ngô Quang Hưng ( 09/07/2008 )
Computational Learning Theory (COLT) bắt đầu từ bài báo kinh điển của Valiant hồi 1984 trên tờ CACM. (Thế mới thấy CACM bây giờ chán, không còn thấy original research articles mấy nữa. Hy vọng là cố gắng cải tổ của Moshe Vardi mới đây sẽ làm CACM thú vị hơn, thành một tờ Science cho ngành CS). Tôi quan tâm đến COLT trong quá trình tìm hiểu xem làm thế nào để mô tả về mặt toán học khái niệm “learnability” (của máy, và có khi cả của người). Ví dụ: làm thế nào để biết/chứng minh rằng một vấn đề nào đó là không thể learn được.
Chuỗi bài này có thể xem là nhật ký của tôi trong hành trình tìm hiểu này. Góc nhìn của COLT đến vấn đề learning là góc nhìn của một nhà lý thuyết tính toán và độ phức tạp. Vì thế, COLT nhảy vào các vấn đề tractability (theo nghĩa lý thuyết tính toán), độ phức tạp không/thời gian, … của learning ngay lập tức. Đây là những vấn đề mà các cách tiếp cận khác hầu như không đề cập. Ví dụ: các quyển The Nature of Statistical Learning Theory của Vapnik hay Pattern Recognition and Machine Learning của Bishop không có chương nào nói về tractability của learning problem(s). Có cả pros lẫn cons của cách tiếp cận COLT, như chúng ta sẽ thấy trong hành trình.
Bài viết thứ nhất này xoay quanh chương 1 quyển Introduction to Computational Learning Theory của Kearns và Vazirani, cộng với tham khảo một số bài giảng của Bob Schapire ở Princeton, cộng với triết lý 3-xu của tôi. Bài tutorial này của Avrim Blum cũng hay, nhưng ta sẽ quay lại với nó sau.
1. Machine Learning (ML) và mục tiêu của nó.
Xem phần giới thiệu của rất nhiều sách về ML để biết câu trả lời :-) . Tôi chỉ phác thảo một số khía cạnh để làm động cơ cho COLT thôi.
Một trong những bài toán cơ bản của ML là bài toán phân loại (classification problem). Chúng ta sẽ chỉ xét bài toán classification trong chuỗi bài này. Hình dưới đây trình bày bài toán classification:
Ví dụ: cho một đống emails (training examples) mà bạn đã đánh dấu spam hay not spam , một thuật toán ML sẽ đưa ra một “bộ luật” (prediction rule) mà dùng nó bạn có thể tự động lọc các emails trong tương lai vào spam folder. Sample space trong ví dụ này là tập hợp tất cả các emails.
Có cực kỳ nhiều mục tiêu khác nhau cho một thuật toán ML (chú ý rằng các mục tiêu có thể đạp giò cản lẫn nhau):
* độ chính xác cao (đừng filter email của bà xã vào spam folder),
* dùng ít tài nguyên tính toán (spam filter chứ có phải MS Office đâu mà cần 4GB bộ nhớ và 2 phút để khởi động)
* dùng ít training data (đừng bắt tôi click spam/non-spam 3 năm liên tục rồi mới chịu làm việc)
* có tính khái quát cao, tiếng Anh gọi là general-purpose (một thuật toán có thể dùng cho cả spam filter, packet filter trong firewalls, nhận dạng chữ viết tay, và nhiều thức khác)
* có prediction rule đơn giản (như nguyên lý Occam’s Razor trong phương pháp [luận] khoa học, mặc dù Vapnik có thể không đồng ý với mục tiêu này)
* prediction rule có thể hiểu được bởi chuyên gia (nếu có thuật toán quyết định xem bệnh nhân có ung thư hay không, thì thuật toán nên giải thích cho bác sĩ hiểu lý do tại sao)
* …
* Mục tiêu tối hậu của ML là nâng tầm hiểu biết của chúng ta về nhận thức của con người (human cognition: con người nhận thức ra sao, thế nào, giới hạn ở đâu, v.v.) và vấn đề qui nạp (induction problem) trong nhận thức luận (epistemology). Cho đến nay thì chiều ngược lại đúng hơn: ML hưởng lợi từ khoa học nhận thức và triết học.
Đề có thể mô tả cụ thể về mặt toán học các mục tiêu trên, ta cần một mô hình toán học cho vấn đề learning. COLT là một (bộ các) mô hình như thế.
2. Các mô hình toán học cho vấn đề learning và một mô hình ví dụ
Một learning model là một định dạng toán học (a formulation) một vấn đề learning nào đó, như vấn đề classification mà ta sẽ xem xét. Chúng ta muốn learning model thỏa mãn những tính chất gì?
* Learning model phải hùng mạnh và đơn giản. Hùng mạnh để nắm bắt được vấn đề learning thực tế. Đơn giản để có thể viết papers được, và vì thế tốt nghiệp, kiếm việc làm, kiếm tiền mua sữa cho con nó tiếp tục … learn! Hùng mạnh và đơn giản xem qua có vẻ như oxymoron? Không hẳn thế!
* Cụ thể hơn, learning model phải đủ “hùng mạnh” để nắm bắt các khái niệm sau đây:
1. Học cái gì?
2. Lấy data từ đâu ra, như thế nào?
3. Data được đưa cho learner (nghĩa là thuật toán ML) như thế nào? (On-line, Off-Line, bỏ phong bì tuồn dưới gầm bàn, …)
4. Tối ưu hóa cái gì? Tối ưu dưới các ràng buộc nào?
Cụ thể hơn, hãy xét một mô hình đơn giản nhất gọi là mô hình nhất quán (Consistency Model) cho bài toán classification.
Về mặt trực quan, mô hình này nói rằng: cho một mớ data, tìm một hàm toán học nhất quán với toàn bộ data. Ví dụ: cho một mớ emails với nhãn spam/non-spam, ta có thể kết luận là các emails có các chữ “Viagara”, “Nigeria”, “Banking” là các spam emails. Kết luận này phù hợp với toàn bộ emails trong training set. Chưa định dạng gì hết về mặt toán học là ta đã thấy rất nhiều vấn đề với mô hình này:
* Trên thực tế data rất thường bị nhiễu (noise), sai nhãn chẳng hạn. “Nhất quán với noisy data” thì chất lượng chẳng cao.
* Kể cả khi không có noise, nhất quán với quá khứ không chắc đã dẫn đến đoán tương lai tốt. Tìm một đa thức khớp với giá stocks trong một trăm năm qua rất dễ. Nhưng đa thức này chẳng đoán được giá stock ngày mai, nếu không bọn Wall Street đã chẳng làm giàu được. Nhất quán quá đáng với quá khứ sẽ dẫn đến vấn đề overfitting, vi phạm Occam’s Razor.
* Các ngành lịch sử hay chính trị học, tôi có cảm giác, thường hay bị vấn đề “nhất quán” này. Họ có một lý thuyết nào đó giải thích được phần lớn quá khứ nhưng chẳng đoán được gì trong tương lai với độ chính xác “chịu đựng được”. Có biết bao nhiêu quyển sách viết về chiến tranh và giải thích lý do xảy ra chiến tranh? Có bao nhiều dự đoán chiến tranh chính xác (Israel có tọng Iran trong 5 năm tới không)? Có bao nhiêu “chuyên gia” giải thích một cách hoàn hảo tại sao Bush thắng cử, JFK thắng cử? Các chuyên gia nọ có đoán được Obama hay McCain thắng không? Thảy một đồng tiền và dự đoán của bạn chưa chắc đã kém chuyên gia.
* Nhất quán với quá khứ là điều tốt. Mô hình nhất quán đơn giản sẽ giúp chúng ta “nén” lịch sử một cách gọn gàng, viết sách giáo khoa cho sinh viên … learn! (Ta nên cực kỳ nghi ngờ các phân tích nhân quả trong sách sử!!!) Nhưng chỉ “nhất quán” không thì không đủ là khoa học, và nó là phần dễ nhất của vấn đề.
* …
Mặc dù mô hình nhất quán có nhiều mặt hạn chế như vậy, chúng ta vẫn sẽ định nghĩa nó cụ thể bằng toán học, vì một số ý tưởng sẽ được dùng cho các mô hình tốt hơn.
Toán học của “Mô hình nhất quán” (cho bài classification)
1. Học cái gì?
Gọi \Omega là domain hay instance space của bài toán. (Ví dụ tập hợp tất cả các emails.) Chúng ta muốn học một khái niệm (concept), là một hàm số c: . (Ví dụ: gán spam email giá trị 1, và non-spam email giá trị 0.) Ngoài ra, chúng ta giả sử là có một lớp các khái niệm cho trước
. Khái niệm cần phải học thuộc về lớp này. (Lớp khái niệm chẳng qua là một tập các hàm từ vào , sẽ có ví dụ sau.)
2. Lấy data từ đâu ra? Lấy thế nào? Training data là một tập con của domain, mỗi phần tử đều có “nhãn”.
3. Data được đưa cho learner thế nào? Đưa off-line, toàn bộ S.
4. Tối ưu hóa cái gì? Tối ưu dưới các ràng buộc nào? Trong thời gian đa thức (polynomial time) Learner cần đưa ra một giả thuyết (hypothesis) h \in nhất quán với toàn bộ data, nghĩa là
Trích: http://www.procul.org/blog/2008/07/09/h%E1%BB%8Dc-may-t%E1%BB%AB-goc-nhin-c%E1%BB%A7a-ly-thuy%E1%BA%BFt-tinh-toan-1/
Ngô Quang Hưng ( 09/07/2008 )
Computational Learning Theory (COLT) bắt đầu từ bài báo kinh điển của Valiant hồi 1984 trên tờ CACM. (Thế mới thấy CACM bây giờ chán, không còn thấy original research articles mấy nữa. Hy vọng là cố gắng cải tổ của Moshe Vardi mới đây sẽ làm CACM thú vị hơn, thành một tờ Science cho ngành CS). Tôi quan tâm đến COLT trong quá trình tìm hiểu xem làm thế nào để mô tả về mặt toán học khái niệm “learnability” (của máy, và có khi cả của người). Ví dụ: làm thế nào để biết/chứng minh rằng một vấn đề nào đó là không thể learn được.
Chuỗi bài này có thể xem là nhật ký của tôi trong hành trình tìm hiểu này. Góc nhìn của COLT đến vấn đề learning là góc nhìn của một nhà lý thuyết tính toán và độ phức tạp. Vì thế, COLT nhảy vào các vấn đề tractability (theo nghĩa lý thuyết tính toán), độ phức tạp không/thời gian, … của learning ngay lập tức. Đây là những vấn đề mà các cách tiếp cận khác hầu như không đề cập. Ví dụ: các quyển The Nature of Statistical Learning Theory của Vapnik hay Pattern Recognition and Machine Learning của Bishop không có chương nào nói về tractability của learning problem(s). Có cả pros lẫn cons của cách tiếp cận COLT, như chúng ta sẽ thấy trong hành trình.
Bài viết thứ nhất này xoay quanh chương 1 quyển Introduction to Computational Learning Theory của Kearns và Vazirani, cộng với tham khảo một số bài giảng của Bob Schapire ở Princeton, cộng với triết lý 3-xu của tôi. Bài tutorial này của Avrim Blum cũng hay, nhưng ta sẽ quay lại với nó sau.
1. Machine Learning (ML) và mục tiêu của nó.
Xem phần giới thiệu của rất nhiều sách về ML để biết câu trả lời :-) . Tôi chỉ phác thảo một số khía cạnh để làm động cơ cho COLT thôi.
Một trong những bài toán cơ bản của ML là bài toán phân loại (classification problem). Chúng ta sẽ chỉ xét bài toán classification trong chuỗi bài này. Hình dưới đây trình bày bài toán classification:
Ví dụ: cho một đống emails (training examples) mà bạn đã đánh dấu spam hay not spam , một thuật toán ML sẽ đưa ra một “bộ luật” (prediction rule) mà dùng nó bạn có thể tự động lọc các emails trong tương lai vào spam folder. Sample space trong ví dụ này là tập hợp tất cả các emails.
Có cực kỳ nhiều mục tiêu khác nhau cho một thuật toán ML (chú ý rằng các mục tiêu có thể đạp giò cản lẫn nhau):
* độ chính xác cao (đừng filter email của bà xã vào spam folder),
* dùng ít tài nguyên tính toán (spam filter chứ có phải MS Office đâu mà cần 4GB bộ nhớ và 2 phút để khởi động)
* dùng ít training data (đừng bắt tôi click spam/non-spam 3 năm liên tục rồi mới chịu làm việc)
* có tính khái quát cao, tiếng Anh gọi là general-purpose (một thuật toán có thể dùng cho cả spam filter, packet filter trong firewalls, nhận dạng chữ viết tay, và nhiều thức khác)
* có prediction rule đơn giản (như nguyên lý Occam’s Razor trong phương pháp [luận] khoa học, mặc dù Vapnik có thể không đồng ý với mục tiêu này)
* prediction rule có thể hiểu được bởi chuyên gia (nếu có thuật toán quyết định xem bệnh nhân có ung thư hay không, thì thuật toán nên giải thích cho bác sĩ hiểu lý do tại sao)
* …
* Mục tiêu tối hậu của ML là nâng tầm hiểu biết của chúng ta về nhận thức của con người (human cognition: con người nhận thức ra sao, thế nào, giới hạn ở đâu, v.v.) và vấn đề qui nạp (induction problem) trong nhận thức luận (epistemology). Cho đến nay thì chiều ngược lại đúng hơn: ML hưởng lợi từ khoa học nhận thức và triết học.
Đề có thể mô tả cụ thể về mặt toán học các mục tiêu trên, ta cần một mô hình toán học cho vấn đề learning. COLT là một (bộ các) mô hình như thế.
2. Các mô hình toán học cho vấn đề learning và một mô hình ví dụ
Một learning model là một định dạng toán học (a formulation) một vấn đề learning nào đó, như vấn đề classification mà ta sẽ xem xét. Chúng ta muốn learning model thỏa mãn những tính chất gì?
* Learning model phải hùng mạnh và đơn giản. Hùng mạnh để nắm bắt được vấn đề learning thực tế. Đơn giản để có thể viết papers được, và vì thế tốt nghiệp, kiếm việc làm, kiếm tiền mua sữa cho con nó tiếp tục … learn! Hùng mạnh và đơn giản xem qua có vẻ như oxymoron? Không hẳn thế!
* Cụ thể hơn, learning model phải đủ “hùng mạnh” để nắm bắt các khái niệm sau đây:
1. Học cái gì?
2. Lấy data từ đâu ra, như thế nào?
3. Data được đưa cho learner (nghĩa là thuật toán ML) như thế nào? (On-line, Off-Line, bỏ phong bì tuồn dưới gầm bàn, …)
4. Tối ưu hóa cái gì? Tối ưu dưới các ràng buộc nào?
Cụ thể hơn, hãy xét một mô hình đơn giản nhất gọi là mô hình nhất quán (Consistency Model) cho bài toán classification.
Về mặt trực quan, mô hình này nói rằng: cho một mớ data, tìm một hàm toán học nhất quán với toàn bộ data. Ví dụ: cho một mớ emails với nhãn spam/non-spam, ta có thể kết luận là các emails có các chữ “Viagara”, “Nigeria”, “Banking” là các spam emails. Kết luận này phù hợp với toàn bộ emails trong training set. Chưa định dạng gì hết về mặt toán học là ta đã thấy rất nhiều vấn đề với mô hình này:
* Trên thực tế data rất thường bị nhiễu (noise), sai nhãn chẳng hạn. “Nhất quán với noisy data” thì chất lượng chẳng cao.
* Kể cả khi không có noise, nhất quán với quá khứ không chắc đã dẫn đến đoán tương lai tốt. Tìm một đa thức khớp với giá stocks trong một trăm năm qua rất dễ. Nhưng đa thức này chẳng đoán được giá stock ngày mai, nếu không bọn Wall Street đã chẳng làm giàu được. Nhất quán quá đáng với quá khứ sẽ dẫn đến vấn đề overfitting, vi phạm Occam’s Razor.
* Các ngành lịch sử hay chính trị học, tôi có cảm giác, thường hay bị vấn đề “nhất quán” này. Họ có một lý thuyết nào đó giải thích được phần lớn quá khứ nhưng chẳng đoán được gì trong tương lai với độ chính xác “chịu đựng được”. Có biết bao nhiêu quyển sách viết về chiến tranh và giải thích lý do xảy ra chiến tranh? Có bao nhiều dự đoán chiến tranh chính xác (Israel có tọng Iran trong 5 năm tới không)? Có bao nhiêu “chuyên gia” giải thích một cách hoàn hảo tại sao Bush thắng cử, JFK thắng cử? Các chuyên gia nọ có đoán được Obama hay McCain thắng không? Thảy một đồng tiền và dự đoán của bạn chưa chắc đã kém chuyên gia.
* Nhất quán với quá khứ là điều tốt. Mô hình nhất quán đơn giản sẽ giúp chúng ta “nén” lịch sử một cách gọn gàng, viết sách giáo khoa cho sinh viên … learn! (Ta nên cực kỳ nghi ngờ các phân tích nhân quả trong sách sử!!!) Nhưng chỉ “nhất quán” không thì không đủ là khoa học, và nó là phần dễ nhất của vấn đề.
* …
Mặc dù mô hình nhất quán có nhiều mặt hạn chế như vậy, chúng ta vẫn sẽ định nghĩa nó cụ thể bằng toán học, vì một số ý tưởng sẽ được dùng cho các mô hình tốt hơn.
Toán học của “Mô hình nhất quán” (cho bài classification)
1. Học cái gì?
Gọi \Omega là domain hay instance space của bài toán. (Ví dụ tập hợp tất cả các emails.) Chúng ta muốn học một khái niệm (concept), là một hàm số c: . (Ví dụ: gán spam email giá trị 1, và non-spam email giá trị 0.) Ngoài ra, chúng ta giả sử là có một lớp các khái niệm cho trước
. Khái niệm cần phải học thuộc về lớp này. (Lớp khái niệm chẳng qua là một tập các hàm từ vào , sẽ có ví dụ sau.)
2. Lấy data từ đâu ra? Lấy thế nào? Training data là một tập con của domain, mỗi phần tử đều có “nhãn”.
3. Data được đưa cho learner thế nào? Đưa off-line, toàn bộ S.
4. Tối ưu hóa cái gì? Tối ưu dưới các ràng buộc nào? Trong thời gian đa thức (polynomial time) Learner cần đưa ra một giả thuyết (hypothesis) h \in nhất quán với toàn bộ data, nghĩa là
Trích: http://www.procul.org/blog/2008/07/09/h%E1%BB%8Dc-may-t%E1%BB%AB-goc-nhin-c%E1%BB%A7a-ly-thuy%E1%BA%BFt-tinh-toan-1/