Измерение Вапник-Червоненкис
Материал от MachineLearning.
Вижте също насоки относно използването на Ресурса MachineLearning.ru в образователния процес.
Измерение Вапник-Червоненкис (капацитет, VC-измерение) е характеристика на семейство алгоритми (или класифициращи функции) за решаване на проблем с класификация, характеризираща сложността или капацитета на това семейство. Това е една от ключовите концепции в теорията на Вапник-Червоненкис за статистическо машинно обучение, кръстена на В. Н. Вапник и А. Я. Червоненкис .
Съдържание
Определение
Ако има число, такова, че растежът функционира и, тогава се извиква капацитет или Измерение Вапник-Червоненкис (VC-измерение) семейство алгоритми. Ако такъв брой не съществува, тогава се казва, че семейството има безкраен капацитет.
Друга формулировка на дефиницията (чрез разнообразие): Нека се даде набор от обекти и някакво семейство функции (алгоритми за класификация, правила за вземане на решения), които свързват всеки обект от множеството с един от двата дадени класа. Капацитетът на едно семейство е най-големият брой, такъв че има подмножество обекти в набора, които могат да се разделят на два класа по всички възможни начини. Ако такива подмножества съществуват за произволно големи, тогава се приема, че капацитетът е равен на безкрайност.
Ако едно семейство алгоритми има окончателно измерение Vapnik-Chervonenkis, тогава такова семейство се нарича клас Vapnik-Chervonenkis.
Линеен класификатор
Като пример, разгледайте проблема за разделяне на точките на равнина на два класа по права линия - това е така нареченият линеен класификатор. Набор от произволни три точки, които не лежат на една права линия, може да бъде разделен по права линия на два класа по всички възможни начини (2³ = 8 начина, фигурата по-долу показва две от тях), но набор от четири или повече точки вече няма. Следователно размерът на Вапник-Червоненкис на линейния класификатор в равнината е равен на три.