มิติ VC และความจุ

มิติ Vapnik-Chervonenkis (VC dimension) ใช้วัดความจุของคลาสแบบจำลองโดยพิจารณาจากชุดจุดที่ใหญ่ที่สุดที่แบบจำลองสามารถจำแนกได้ในทุกรูปแบบที่เป็นไปได้ ซึ่งเป็นการวัดความซับซ้อนของผู้เรียนรู้

Definition

มิติ Vapnik-Chervonenkis ของคลาสตัวจำแนก (classifiers) คือจำนวนจุดที่มากที่สุดที่คลาสสามารถจำแนกได้ในทุกรูปแบบที่เป็นไปได้ ซึ่งเป็นการวัดความจุที่จำกัดขอบเขตว่าคลาสสามารถเกิดภาวะการเรียนรู้เกิน (overfit) ได้มากน้อยเพียงใด และด้วยเหตุนี้จึงบ่งบอกถึงปริมาณข้อมูลที่จำเป็นสำหรับการเรียนรู้ที่น่าเชื่อถือ

Scope

หัวข้อนี้ครอบคลุมการวัดความสมบูรณ์ของคลาสสมมติฐาน: แนวคิดของการ 'shattering' ชุดของจุด, มิติ Vapnik-Chervonenkis ในฐานะขนาดของชุดที่ถูก 'shatter' ที่ใหญ่ที่สุด, ฟังก์ชันการเติบโต (growth function), และวิธีที่การวัดความจุเหล่านี้ถูกนำมาใช้ในการจำกัดขอบเขตการสรุปผล (generalization bounds) นอกจากนี้ยังอธิบายว่าเหตุใดความจุจึงเป็นตัวกำหนดความสามารถในการสรุปผล มากกว่าจำนวนพารามิเตอร์เพียงอย่างเดียว

Core questions

• การที่คลาสแบบจำลอง 'shatter' ชุดของจุดหมายความว่าอย่างไร?
• มิติ Vapnik-Chervonenkis ถูกนิยามและคำนวณอย่างไร?
• เหตุใดความจุจึงเป็นตัวกำหนดการสรุปผล มากกว่าจำนวนพารามิเตอร์?
• ความจุมีผลต่อขอบเขตของช่องว่างระหว่างข้อผิดพลาดจากการฝึกฝนและข้อผิดพลาดที่แท้จริงอย่างไร?

Key theories

การ Shattering และความจุ

คลาสจะ 'shatter' ชุดของจุดได้ หากสามารถสร้างการจำแนกประเภทที่เป็นไปได้ทั้งหมดของจุดเหล่านั้นได้ และชุดที่ใหญ่ที่สุดที่สามารถ 'shatter' ได้นี้จะกำหนดมิติ Vapnik-Chervonenkis ซึ่งเป็นการวัดความยืดหยุ่นของคลาสที่ไม่ขึ้นกับการกระจายตัว

ความจุควบคุมการลู่เข้าอย่างสม่ำเสมอ

ความจุที่จำกัดทำให้มั่นใจได้ว่าข้อผิดพลาดเชิงประจักษ์ (empirical error) จะลู่เข้าสู่ข้อผิดพลาดที่แท้จริงอย่างสม่ำเสมอทั่วทั้งคลาส ดังนั้นผู้เรียนรู้ที่มีมิติ Vapnik-Chervonenkis ที่มีขอบเขตจะไม่สามารถเกิดภาวะการเรียนรู้เกินได้อย่างไม่จำกัดเมื่อข้อมูลเพิ่มขึ้น

ความจุเทียบกับจำนวนพารามิเตอร์

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

Clinical relevance

มิติ Vapnik-Chervonenkis เป็นการวัดความจุหลักในทฤษฎีการเรียนรู้แบบคลาสสิกและสนับสนุนแนวปฏิบัติในการควบคุมความซับซ้อนของแบบจำลอง นอกจากนี้ยังเป็นพื้นฐานของการวิเคราะห์แบบจำลองเครื่องจักรเวกเตอร์ค้ำจุน (support vector machines) โดยอาศัยระยะขอบ (margin-based analysis) และเป็นกรอบในการทำความเข้าใจว่าเหตุใดแบบจำลองที่มีความจุสูงมากบางแบบจึงยังคงสามารถสรุปผลได้ดี

History

Vapnik และ Chervonenkis ได้นำเสนอแนวคิดมิติที่ตั้งชื่อตามพวกเขาในงานช่วงปลายทศวรรษ 1960 และในบทความปี 1971 เกี่ยวกับการลู่เข้าอย่างสม่ำเสมอ (uniform convergence) ซึ่งเป็นการสร้างทฤษฎีความจุที่ไม่ขึ้นกับการกระจายตัว (distribution-free theory of capacity) แนวคิดนี้ได้กลายเป็นรากฐานสำคัญสำหรับเครื่องจักรเวกเตอร์ค้ำจุนและการวิเคราะห์การสรุปผลในวงกว้าง

Key figures

• Vladimir Vapnik
• Alexey Chervonenkis

Seminal works

• vapnik1971
• vapnik1995
• hastie2009

Frequently asked questions

การ 'shattering' หมายความว่าอย่างไร?

ชุดของจุดจะถูก 'shatter' โดยคลาสแบบจำลอง หากสำหรับการกำหนดป้ายกำกับที่เป็นไปได้ทั้งหมดให้กับจุดเหล่านั้น มีแบบจำลองบางตัวในคลาสที่สร้างการจำแนกประเภทนั้นได้อย่างแม่นยำ ขนาดของชุดที่ใหญ่ที่สุดที่สามารถ 'shatter' ได้คือมิติ Vapnik-Chervonenkis

แบบจำลองที่มีพารามิเตอร์มากขึ้นมีความจุสูงกว่าเสมอไปหรือไม่?

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