ทฤษฎีการเรียนรู้เชิงคำนวณ

ทฤษฎีการเรียนรู้เชิงคำนวณศึกษาว่าแนวคิดใดบ้างที่สามารถเรียนรู้ได้อย่างมีประสิทธิภาพจากตัวอย่าง โดยถือว่าการเรียนรู้เป็นปัญหาของการคำนวณและความซับซ้อนของตัวอย่าง

Definition

ทฤษฎีการเรียนรู้เชิงคำนวณคือการศึกษาทรัพยากร ทั้งในด้านข้อมูลและการคำนวณ ที่จำเป็นสำหรับการเรียนรู้แนวคิดจากตัวอย่าง; ในแบบจำลองที่ถูกต้องโดยประมาณ (probably approximately correct model) กลุ่มแนวคิดจะสามารถเรียนรู้ได้หากอัลกอริทึมสามารถสร้างสมมติฐานที่แม่นยำด้วยความน่าจะเป็นสูงจากจำนวนตัวอย่างที่เป็นพหุนามและในเวลาที่เป็นพหุนาม

Scope

หัวข้อนี้ครอบคลุมแบบจำลองที่เป็นทางการของการเรียนรู้ได้: แบบจำลองที่ถูกต้องโดยประมาณ (probably approximately correct model) ซึ่งตั้งคำถามว่าแนวคิดสามารถเรียนรู้ได้ด้วยความแม่นยำสูงและความน่าจะเป็นสูงจากตัวอย่างและการคำนวณจำนวนพหุนามเมื่อใด, แบบจำลองขอบเขตความผิดพลาดและการเรียนรู้ออนไลน์ (mistake-bound and online-learning models), การเรียนรู้ได้แบบอ่อนเทียบกับแบบเข้มแข็งและการบูสต์ (weak versus strong learnability and boosting), และความเชื่อมโยงกับความซับซ้อนเชิงคำนวณ (computational complexity) โดยกล่าวถึงความเป็นไปได้ทั้งทางสถิติและทางอัลกอริทึมของการเรียนรู้

Core questions

• กลุ่มแนวคิดใดบ้างที่สามารถเรียนรู้ได้อย่างมีประสิทธิภาพจากตัวอย่าง?
• การเรียนรู้แนวคิดต้องใช้ข้อมูลและการคำนวณมากน้อยเพียงใด?
• ความสัมพันธ์ระหว่างการเรียนรู้ได้แบบอ่อนและการเรียนรู้ได้แบบเข้มแข็งคืออะไร?
• การเรียนรู้ได้เชื่อมโยงกับความซับซ้อนเชิงคำนวณอย่างไร?

Key theories

การเรียนรู้ที่ถูกต้องโดยประมาณ (Probably approximately correct learning)

แบบจำลองของ Valiant กำหนดว่ากลุ่มแนวคิดสามารถเรียนรู้ได้เมื่ออัลกอริทึมที่มีประสิทธิภาพสามารถสร้างสมมติฐานที่มีข้อผิดพลาดต่ำด้วยความน่าจะเป็นสูงจากตัวอย่างจำนวนพหุนาม ทำให้การเรียนรู้ได้เป็นคำถามเชิงคำนวณที่แม่นยำ

การเรียนรู้ได้แบบอ่อนและการบูสต์ (Weak learnability and boosting)

ผลลัพธ์สำคัญแสดงให้เห็นว่ากลุ่มใดๆ ที่สามารถเรียนรู้ได้ดีกว่าการเดาแบบสุ่มเล็กน้อยก็สามารถเรียนรู้ได้แบบเข้มแข็งเช่นกัน ซึ่งนำไปสู่การพัฒนาอัลกอริทึมการบูสต์ที่ขยายผู้เรียนรู้แบบอ่อนให้กลายเป็นผู้เรียนรู้ที่แม่นยำ

ข้อจำกัดทางสถิติและเชิงคำนวณ (Statistical and computational limits)

การเรียนรู้ได้ถูกจำกัดทั้งโดยความซับซ้อนของตัวอย่าง ซึ่งเชื่อมโยงกับการวัดความจุ และโดยความยากลำบากเชิงคำนวณ ดังนั้นบางกลุ่มจึงสามารถเรียนรู้ได้ทางสถิติแต่ไม่สามารถจัดการได้ในเชิงคำนวณ

Clinical relevance

ทฤษฎีการเรียนรู้เชิงคำนวณวางรากฐานที่เป็นทางการสำหรับสิ่งที่อัลกอริทึมการเรียนรู้สามารถทำได้และทำไม่ได้ และเป็นแรงบันดาลใจโดยตรงให้กับวิธีการปฏิบัติจริง โดยเฉพาะอย่างยิ่งการบูสต์ (boosting) ซึ่งเกิดขึ้นจากคำถามว่าผู้เรียนรู้แบบอ่อน (weak learners) สามารถรวมกันเป็นผู้เรียนรู้แบบเข้มแข็ง (strong ones) ได้หรือไม่; มันกำหนดกรอบการเรียนรู้ให้เป็นสาขาวิชาเชิงคำนวณที่เข้มงวด

History

Valiant ได้นำเสนอแบบจำลองที่ถูกต้องโดยประมาณ (probably approximately correct model) ในปี 1984 ซึ่งให้คำจำกัดความเชิงคำนวณที่แม่นยำของการเรียนรู้และก่อตั้งสาขาวิชานี้ขึ้นมา งานวิจัยต่อมาได้สร้างลักษณะเฉพาะของความซับซ้อนของตัวอย่าง (sample-complexity characterizations), ความเท่าเทียมกันของการเรียนรู้ได้แบบอ่อนและแบบเข้มแข็ง (equivalence of weak and strong learnability) ซึ่งเป็นแรงจูงใจในการพัฒนาการบูสต์ (boosting), และผลลัพธ์ที่แสดงถึงข้อจำกัดเชิงคำนวณของการเรียนรู้ (hardness results showing the computational limits of learning)

Key figures

• Leslie Valiant
• Michael Kearns
• Robert Schapire

Seminal works

• valiant1984
• kearns1994
• vapnik1995

Frequently asked questions

คำว่า 'ถูกต้องโดยประมาณ' (probably approximately correct) หมายความว่าอย่างไร?

หมายความว่า ด้วยความน่าจะเป็นสูงจากตัวอย่างสุ่ม ผู้เรียนรู้จะสร้างสมมติฐานที่ถูกต้องโดยประมาณ นั่นคือ มีข้อผิดพลาดเล็กน้อยกับข้อมูลในอนาคต การเรียนรู้ได้ต้องบรรลุสิ่งนี้จากจำนวนตัวอย่างและปริมาณการคำนวณที่เพิ่มขึ้นในลักษณะพหุนามเท่านั้น

ทฤษฎีการเรียนรู้ได้นำไปสู่การบูสต์ (boosting) ได้อย่างไร?

นักวิจัยตั้งคำถามว่าผู้เรียนรู้ที่ทำได้ดีกว่าการเดาแบบสุ่มเพียงเล็กน้อยจะสามารถเปลี่ยนเป็นผู้เรียนรู้ที่มีความแม่นยำสูงได้หรือไม่ การพิสูจน์ว่าการเรียนรู้ได้แบบอ่อนและการเรียนรู้ได้แบบเข้มแข็งนั้นเทียบเท่ากันเป็นแบบสร้างสรรค์ และการสร้างนั้นได้กลายเป็นอัลกอริทึมการบูสต์ที่ใช้กันอย่างแพร่หลายในทางปฏิบัติ