Кіріспе
Бақыланатын машиналық оқытудағы ұғым. Вапник-Червоненкис теориясында Вапник-Червоненкис (ВК) өлшемі – жиындар класының мөлшерін (сыйымдылығы, күрделілігі, экспрессивтілігі, байлығы немесе икемділігі) көрсететін шама. Бұл ұғымды бинарлық функциялар класына да қолдануға болады. Ол алгоритмнің «бөлшектеуге» (shatter) болатын ең үлкен нүктелер жиынының кардиналдығы ретінде анықталады, яғни алгоритм осы дерек нүктелерінің кез келген конфигурациясының кез келген белгіленуі үшін мінсіз жіктегішті үйрене алады. Бұл ұғымды бастапқыда Владимир Вапник және Алексей Червоненкис анықтаған. Формальды емес тұрғыдан алғанда, жіктеу моделінің сыйымдылығы оның қаншалықты күрделі болуымен байланысты. Мысалы, жоғары дәрежелі полиномның шекті мәнін қарастырайық: егер полином нөлден жоғары мән берсе, онда бұл нүкте оң, әйтпесе теріс деп жіктеледі. Жоғары дәрежелі полином икемді болуы мүмкін, сондықтан ол берілген оқу нүктелері жиынына жақсы сәйкес келеді. Бірақ классификатор басқа нүктелерде қателіктер жасауы мүмкін, өйткені ол тым икемді. Мұндай полиномның сыйымдылығы жоғары. Ал қарапайым нұсқасы – сызықтық функцияның шекті мәнін қолдану. Бұл функция оқу жиынына жақсы сәйкес келмеуі мүмкін, өйткені оның сыйымдылығы төмен. Бұл сыйымдылық туралы түсінік төменде нақтыланады.
In Vapnik–Chervonenkis theory, the Vapnik–Chervonenkis (VC) dimension is a measure of the size (capacity, complexity, expressive power, richness, or flexibility) of a class of sets. The notion can be extended to classes of binary functions. It is defined as the cardinality of the largest set of points that the algorithm can shatter, which means the algorithm can always learn a perfect classifier for any labeling of at least one configuration of those data points. It was originally defined by Vladimir Vapnik and Alexey Chervonenkis. Informally, the capacity of a classification model is related to how complicated it can be. For example, consider the thresholding of a high degree polynomial: if the polynomial evaluates above zero, that point is classified as positive, otherwise as negative. A high degree polynomial can be wiggly, so it can fit a given set of training points well. But one can expect that the classifier will make errors on other points, because it is too wiggly. Such a polynomial has a high capacity. A much simpler alternative is to threshold a linear function. This function may not fit the training set well, because it has a low capacity. This notion of capacity is made rigorous below.
Жинақ отбасының VC өлшемдері
Келіңіздер, жиынтықтар отбасы (жиынтықтар жиыны) және жиынтық болсын. Олардың қиылысы келесі жиынтықтар отбасы ретінде анықталады:
Біз жиынтығының жиынтықтар отбасымен шашыратылғанын айтамыз, егер жиынтығы жиынтығының барлық ішкі жиынтықтарын қамтитын болса, яғни:
-нің VC өлшемі жиынтығымен шашыратылған ең үлкен жиынтықтың кардиналдығы болып табылады. Егер кез келген үлкен жиынтықтар шашыратылса, VC өлшемі болады.
Классификациялық модельдің VC өлшемдері
Параметр векторы бар екілік жіктеу моделі, егер осы нүктелерге кез келген жазбалар жиынтығы берілгенде, модель осы деректер нүктелері жиынтығын бағалау кезінде қателіктер жасамайтындей етіп, оларды толығымен жіктесе, онда ол деректер нүктелерінің жиынтығын «бұзады» делінеді. Модельдің VC өлшемі – оны бұза алатын ең көп нүктелер саны. Әлдеқайда формалдырақ айтқанда, бұл – модельдің бұза алатын, белгілі бір кардиналдылығы бар, жалпы орналасқан деректер нүктелері жиынының ең үлкен саны.
Статистикалық оқыту теориясында
VC өлшем классификациялық модельдің сынақ қатесіне ықтималдық жоғарғы шекті болжауға мүмкіндік береді. Вапник, сынақ қателігінің ықтималдығын (яғни 0–1 жоғалту функциясымен тәуекел) оқу жиынтығымен бірдей үлестірімнен алынған деректер бойынша жоғарғы шектен алшақтауын былай анықтады:
мұнда – классификациялық модельдің VC өлшемі, – және – оқу жиынтығының мөлшері (шектеу: бұл формула қашан жарамды). Егер үлкен болса, сынақ қатесі оқу қатесінен әлдеқайда жоғары болуы мүмкін. Бұл артық үйлесімнен туындайды. VC өлшемі үлгі күрделілігінің шегінде де кездеседі. VC өлшемі болған екілік функциялар кеңістігін мыналармен үйренуге болады:
үлгі, мұнда – оқу қатесі және – сәтсіздік ықтималдығы. Осылайша, үлгі күрделілігі гипотеза кеңістігінің VC өлшемінің сызықтық функциясы болып табылады.
Есептеу геометриясында
VC өлшемдері ε торларының мөлшерін анықтайтын маңызды параметрлердің бірі болып табылады, бұл оларға негізделген жуықтау алгоритмдерінің күрделілігін анықтайды; шекті VC өлшемі жоқ диапазон жиындары мүлдем шекті ε торларына ие болмауы мүмкін.
Шекаралары
Екілік жиынтық отбасының VC өлшемі қатаң түрде кішкентай , және бұл ең жақсы мүмкін нәтиже. Шекті жиынтық отбасының VC өлшемі ең көп дегенде . Дәлелдеу: (а) Әрбір екі түрлі нүкте үшін, оларды қамтитын бір түзу, тек біреуін қамтитын түзулер және ешқайсысын қамтимайтын түзулер бар, сондықтан 2 өлшемді кез келген жиынтық толығымен шашыратылады. (б) Үш түрлі нүктенің кез келген үштігі үшін, егер x түзуі барлық үш нүктені қамтитын болса, онда y түзуі дәл екі нүктені қамтитын болмайды (өйткені онда x және y екі нүктеде қиылысады, бұл проективті жазықтықтың анықтамасына қайшы келеді). Сондықтан, 3 өлшемді жиынтықтар шашыратылмайды.
Proof: (a) For each pair of distinct points, there is one line that contains both of them, lines that contain only one of them, and lines that contain none of them, so every set of size 2 is shattered. (b) For any triple of three distinct points, if there is a line x that contain all three, then there is no line y that contains exactly two (since then x and y would intersect in two points, which is contrary to the definition of a projective plane). Hence, no set of size 3 is shattered.
Жалпылау
VC өлшемдері бинарлық функциялар кеңістіктері үшін анықталады (функциялар {0,1} жиынына). Бинарлық емес функциялар кеңістіктері үшін бірнеше жалпыламалар ұсынылған. Көп класты функциялар үшін (мысалы, {0, ..., n-1} жиынына функциялар), Натараджан өлшемін қолдануға болады. Бен-Давид және авторлар бұл ұғымның жалпыламасын ұсынады. Нақты мәнді функциялар үшін (мысалы, нақты интервалға, [0,1] функциялар), Поллардтың псевдоөлшемін пайдалануға болады. Радемашер күрделігі VC-ге ұқсас шектеулер береді және кейде ядроларды қолдану сияқты статистикалық әдістерге, VC өлшемдерін есептеуден гөрі көбірек түсінік береді. Жад сыйымдылығы (кейде жадтың эквиваленттік сыйымдылығы) жоғарғы шек орнына төменгі шек сыйымдылығын береді (мысалы: Жасанды нейрондық желі#Сыйымдылық) және демек, ықтимал артық үйлесім нүктесін көрсетеді.