Введение
Понятие в обучении с учителем
В теории Вапника — Червоненкиса размерность Вапника — Червоненкиса (VC) является мерой размера (ёмкости, сложности, выразительной силы, богатства или гибкости) класса множеств. Это понятие может быть расширено на классы бинарных функций. Оно определяется как кардинальность наибольшего множества точек, которое алгоритм может "разрушить" (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 семейства наборов
Пусть $\mathcal{F}$ – семейство множеств (множество множеств), а $X$ – множество. Их пересечение определяется как следующее семейство множеств:
Мы говорим, что множество $S$ разбивается семейством $\mathcal{F}$, если $\mathcal{F}$ содержит все подмножества $S$, то есть:
VC-размерность семейства $\mathcal{F}$ – это мощность наибольшего множества, которое разбивается $\mathcal{F}$. Если произвольно большие множества могут быть разбиты, то VC-размерность равна бесконечности.
Размер VC классификационной модели
Модель бинарной классификации с некоторым вектором параметров называется разбивающей (shattering) набор точек данных в общем положении, если для любого присвоения меток этим точкам существует такое значение параметров, при котором модель не допускает ошибок при оценке этого набора точек данных. VC-размерность модели — это максимальное число точек, которые можно расположить так, чтобы модель разбивала их. Более формально, это максимальная кардинальность такого набора точек данных в общем положении, который может быть разбит моделью.
В теории статистического обучения
Размерность VC может предсказать вероятную верхнюю границу для ошибки тестирования классификационной модели. Вапник доказал, что вероятность отклонения ошибки тестирования (то есть риска с функцией потерь 0–1) от верхней границы (для данных, полученных независимо и одинаково распределёнными из того же распределения, что и обучающая выборка) задаётся выражением:
где – размерность VC классификационной модели, , а – размер обучающей выборки (ограничение: эта формула справедлива, когда . Если больше, то ошибка тестирования может значительно превышать ошибку обучения. Это связано с переобучением). Размерность VC также встречается в оценках сложности выборки. Пространство двоичных функций с размерностью VC можно изучить, используя:
образцов, где – ошибка обучения, а – вероятность ошибки. Таким образом, сложность выборки является линейной функцией размерности VC пространства гипотез.
В вычислительной геометрии
Размерность VC является одним из ключевых параметров при определении размера ε-сетей, что определяет сложность алгоритмов аппроксимации, основанных на них; множества диапазонов с бесконечной размерностью VC могут вообще не иметь конечных ε-сетей.
Границы
Размерность VC двойного семейства множеств строго меньше , и это оптимальный результат. Размерность VC конечного семейства множеств не превышает .
Доказательство: (a) Для каждой пары различных точек существует прямая, содержащая обе точки, прямые, содержащие только одну из них, и прямые, не содержащие ни одной из них, поэтому любое множество размера 2 разбивается. (b) Для любой тройки различных точек, если существует прямая 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, при анализе статистических методов, таких как методы с использованием ядер. Вместимость памяти (иногда называемая эквивалентной емкостью памяти) дает нижнюю оценку емкости, а не верхнюю (см., например, Искусственная нейронная сеть#Емкость) и, следовательно, указывает на точку потенциальной переобученности.