بُعد VC و ظرفیت

بُعد واپینک-چروننکیس ظرفیت یک کلاس مدل را با بزرگترین مجموعه‌ای از نقاط که می‌تواند به تمام روش‌های ممکن برچسب‌گذاری کند، اندازه‌گیری می‌کند و پیچیدگی یک یادگیرنده را کمی‌سازی می‌کند.

Definition

بُعد واپینک-چروننکیس یک کلاس طبقه‌بندی‌کننده، بزرگترین تعداد نقاطی است که کلاس می‌تواند به هر روش ممکن برچسب‌گذاری کند؛ این یک معیار ظرفیت است که میزان بیش‌برازش (overfit) کلاس و در نتیجه میزان داده مورد نیاز برای یادگیری قابل اعتماد را محدود می‌کند.

Scope

این موضوع معیارهای غنای یک کلاس فرضیه را پوشش می‌دهد: مفهوم خرد کردن (shattering) مجموعه‌ای از نقاط، بُعد واپینک-چروننکیس به عنوان اندازه بزرگترین مجموعه خرد شده، تابع رشد، و چگونگی ورود این معیارهای ظرفیت به کران‌های تعمیم. این موضوع توضیح می‌دهد که چرا ظرفیت، و نه تنها تعداد پارامترها، توانایی تعمیم را کنترل می‌کند.

Core questions

• برای یک کلاس مدل، خرد کردن (shatter) مجموعه‌ای از نقاط به چه معناست؟
• بُعد واپینک-چروننکیس چگونه تعریف و محاسبه می‌شود؟
• چرا ظرفیت و نه تعداد پارامترها، تعمیم را کنترل می‌کند؟
• ظرفیت چگونه در کران‌های شکاف بین خطای آموزش و خطای واقعی وارد می‌شود؟

Key theories

خرد کردن و ظرفیت

یک کلاس مجموعه‌ای از نقاط را خرد می‌کند اگر بتواند هر برچسب‌گذاری ممکن از آنها را محقق سازد؛ بزرگترین چنین مجموعه‌ای بُعد واپینک-چروننکیس را تعریف می‌کند، که یک معیار مستقل از توزیع برای میزان انعطاف‌پذیری کلاس است.

ظرفیت، همگرایی یکنواخت را کنترل می‌کند

ظرفیت محدود تضمین می‌کند که خطای تجربی به طور یکنواخت در طول کلاس به خطای واقعی همگرا می‌شود، بنابراین یک یادگیرنده با بُعد واپینک-چروننکیس محدود نمی‌تواند با افزایش داده‌ها به طور دلخواه بیش‌برازش کند.

ظرفیت در مقابل تعداد پارامترها

ظرفیت، نه تعداد خام پارامترها، تعمیم را تعیین می‌کند، بنابراین دو مدل با تعداد پارامترهای یکسان می‌توانند در میزان داده مورد نیازشان تفاوت زیادی داشته باشند.

Clinical relevance

بُعد واپینک-چروننکیس معیار مرکزی ظرفیت نظریه یادگیری کلاسیک را فراهم می‌کند و عمل کنترل پیچیدگی مدل را توجیه می‌کند؛ این بُعد زیربنای تحلیل مبتنی بر حاشیه ماشین‌های بردار پشتیبان است و تلاش‌های جاری برای درک اینکه چرا برخی از مدل‌های با ظرفیت بسیار بالا با این حال تعمیم می‌یابند را چارچوب‌بندی می‌کند.

History

واپینک و چروننکیس بُعدی را که نام آنها را یدک می‌کشد، در کارهای اواخر دهه 1960 و مقاله سال 1971 در مورد همگرایی یکنواخت معرفی کردند و نظریه‌ای مستقل از توزیع (distribution-free) برای ظرفیت ایجاد کردند. این مفهوم برای ماشین‌های بردار پشتیبان و برای تحلیل گسترده‌تر تعمیم، بنیادی شد.

Key figures

• Vladimir Vapnik
• Alexey Chervonenkis

Seminal works

• vapnik1971
• vapnik1995
• hastie2009

Frequently asked questions

خرد کردن (shattering) به چه معناست؟

مجموعه‌ای از نقاط توسط یک کلاس مدل خرد می‌شود اگر برای هر تخصیص ممکن از برچسب‌ها به آن نقاط، مدلی در کلاس دقیقاً آن برچسب‌گذاری را تولید کند. اندازه بزرگترین مجموعه قابل خرد شدن، بُعد واپینک-چروننکیس است.

آیا مدلی با پارامترهای بیشتر همیشه ظرفیت بالاتری دارد؟

لزوماً خیر. ظرفیت با بُعد واپینک-چروننکیس یا مقادیر مرتبط اندازه‌گیری می‌شود که می‌تواند با تعداد پارامترها متفاوت باشد. معیار صحیح پیچیدگی برای تعمیم، ظرفیت است، نه صرفاً تعداد پارامترهای یک مدل.