Vapnik–Chervonenkis dimension

В теории Вапника-Червоненкиса измерение Вапника -Червоненкиса (VC) является мерой размера (емкости, сложности, выразительной силы, богатства или гибкости) класса множеств. Это понятие можно распространить на классы бинарных функций. Она определяется как мощность наибольшего набора точек, которые алгоритм может разрушить . Это означает, что алгоритм всегда может найти идеальный классификатор для любой маркировки хотя бы одной конфигурации этих точек данных. Первоначально его определили Владимир Вапник и Алексей Червоненкис .

Неформально, мощность классификационной модели связана с тем, насколько сложной она может быть. Например, рассмотрим определение порога высокой степени полинома : если результат полинома выше нуля, эта точка классифицируется как положительная, в противном случае — как отрицательная. Полином высокой степени может быть волнистым, поэтому он может хорошо соответствовать заданному набору обучающих точек. Но можно ожидать, что классификатор будет допускать ошибки и по другим пунктам, поскольку он слишком шаткий. Такой полином имеет высокую емкость. Гораздо более простой альтернативой является определение порога линейной функции. Эта функция может не подходить для обучающего набора, поскольку имеет низкую пропускную способность. Ниже это понятие емкости становится более строгим.

Определения

Измерение VC семейства множеств

Позволять $H$ быть семейством множеств (набором множеств) и $C$ набор. Их пересечение определяется как следующее семейство множеств:

$H\cap C:=\{h\cap C\mid h\in H\}.$

Мы говорим, что набор $C$ разрушен ​ ​ $H$ если $H\cap C$ содержит все подмножества $C$, то есть:

$|H\cap C|=2^{|C|}.$

Измерение венчурного капитала $D$ из $H$ — мощность наибольшего множества, разбитого $H$. Если сколь угодно большие множества можно разбить, размерность VC равна $\infty$.

Измерение VC модели классификации

Модель бинарной классификации $f$ с некоторым вектором параметров $\theta$ Говорят, что он разрушает набор обычно расположенных точек данных $(x_{1},x_{2},\ldots ,x_{n})$ если для каждого присвоения меток этим точкам существует $\theta$ такая, что модель $f$ не делает ошибок при оценке этого набора точек данных .

Размерность модели VC $f$ — максимальное количество точек, которые можно расположить так, чтобы $f$ разбивает их. Более формально, это максимальный кардинал $D$ так что существует общерасположенный набор точек данных мощности $D$ который может быть разрушен $f$.

Примеры

1. $f$ — постоянный классификатор (без параметров); Его размерность VC равна 0, поскольку он не может разрушить ни одну точку. В общем, размерность VC конечной модели классификации, которая может возвращать не более $2^{d}$ различных классификаторах, не более $d$ (это верхняя граница размерности VC; лемма Зауэра–Шела дает нижнюю оценку размерности).
2. $f$ — однопараметрический пороговый классификатор действительных чисел; то есть для определенного порога $\theta$, классификатор $f_{\theta }$ возвращает 1, если входное число больше, чем $\theta$ и 0 в противном случае. Размер венчурного капитала $f$ равен 1, потому что: (а) Он может разрушить одну точку. Для каждой точки $x$, классификатор $f_{\theta }$ помечает его как 0, если $\theta >x$ и помечает его как 1, если $\theta <x$. (б) Он не может разбить все наборы с двумя очками. Если для каждого набора из двух чисел меньшее число помечено 1, то и большее должно быть помечено 1, поэтому не все обозначения возможны.
3. $f$ — однопараметрический интервальный классификатор действительных чисел; т.е. по определенному параметру $\theta$, классификатор $f_{\theta }$ возвращает 1, если входное число находится в интервале $[\theta ,\theta +4]$ и 0 в противном случае. Размер венчурного капитала $f$ равно 2, потому что: (a) Это может разрушить некоторые наборы из двух точек. Например, для каждого набора $\{x,x+2\}$, классификатор $f_{\theta }$ помечает его как (0,0), если $\theta <x-4$ или если $\theta >x+2$, как (1,0), если $\theta \in [x-4,x-2)$, как (1,1), если $\theta \in [x-2,x]$, и как (0,1), если $\theta \in (x,x+2]$. (б) Он не может разрушить ни один набор из трех пунктов. Для каждого набора из трех чисел, если наименьшее и наибольшее число помечены цифрой 1, то среднее число также должно быть помечено цифрой 1, поэтому не все обозначения возможны.
4. $f$ — прямая линия как модель классификации точек на двумерной плоскости (это модель, используемая перцептроном ) . Линия должна отделять положительные точки данных от отрицательных точек данных. Существуют наборы из трех точек, которые действительно можно разбить с помощью этой модели (любые три точки, которые не лежат на одной прямой, можно разбить). Однако ни один набор из 4 точек не может быть разбит: по теореме Радона любые четыре точки можно разделить на два подмножества с пересекающимися выпуклыми оболочками , поэтому невозможно отделить одно из этих двух подмножеств от другого. Таким образом, размерность VC этого конкретного классификатора равна 3. Важно помнить, что, хотя можно выбрать любое расположение точек, расположение этих точек не может измениться при попытке разбить его для какого-либо присвоения метки. Обратите внимание, только 3 из 2 ³ = Для трех точек показаны 8 возможных назначений меток.
5. $f$ — однопараметрический синус- классификатор, т. е. для некоторого параметра $\theta$, классификатор $f_{\theta }$ возвращает 1, если входное число $x$ имеет $\sin(\theta x)>0$ и 0 в противном случае. Размер венчурного капитала $f$ бесконечно, поскольку может разрушить любое конечное подмножество множества $\{2^{-m}\mid m\in \mathbb {N} \}$.

3 очка разбиты			4 балла невозможно

Использование

В статистической теории обучения

Измерение VC может предсказать вероятностную верхнюю границу ошибки теста модели классификации. Вапник доказал, что вероятность отклонения тестовой ошибки (т. е. риска с функцией потерь 0–1) от верхней границы (на данных, которые взяты из того же распределения, что и обучающий набор), определяется выражением:

$\Pr \left({\text{test error}}\leqslant {\text{training error}}+{\sqrt {{\frac {1}{N}}\left[D\left(\log \left({\tfrac {2N}{D}}\right)+1\right)-\log \left({\tfrac {\eta }{4}}\right)\right]}}\,\right)=1-\eta ,$

где $D$ - измерение VC модели классификации, $0<\eta \leqslant 1$, и $N$ — размер обучающего набора (ограничение: эта формула действительна, когда $D\ll N$. Когда $D$ больше, ошибка теста может быть намного выше ошибки обучения. Это происходит из-за переобучения ).

Измерение VC также появляется в границах сложности выборки . Пространство бинарных функций с размерностью VC. $D$ можно изучить с помощью:

$N=\Theta \left({\frac {D+\ln {1 \over \delta }}{\varepsilon ^{2}}}\right)$

образцы, где $\varepsilon$ это ошибка обучения и $\delta$ — вероятность отказа. Таким образом, сложность выборки является линейной функцией размерности VC пространства гипотез.

В вычислительной геометрии

Размерность ВК является одним из критических параметров размера ε-сетей , определяющим сложность алгоритмов аппроксимации на их основе; Наборы диапазонов без конечной размерности VC могут вообще не иметь конечных ε-сетей.

Границы

0. Измерение VC двойного семейства множеств ${\mathcal {F}}$ строго меньше, чем $2^{\operatorname {vc} ({\mathcal {F}})+1}$, и это в лучшем случае.
1. Размерность VC конечного семейства множеств $H$ самое большее $\log _{2}|H|$. Это потому, что $|H\cap C|\leq |H|$ по определению.
2. Учитывая набор-семейство $H$, определять $H_{s}$ как семейство множеств, содержащее все пересечения $s$ элементы $H$. Затем: $$\operatorname {VCDim} (H_{s})\leq \operatorname {VCDim} (H)\cdot (2s\log _{2}(3s))$$
3. Учитывая набор-семейство $H$ и элемент $h_{0}\in H$, определять $H\,\Delta h_{0}:=\{h\,\Delta h_{0}\mid h\in H\}$ где $\Delta$ обозначает симметричную разность множеств . Затем: $$\operatorname {VCDim} (H\,\Delta h_{0})=\operatorname {VCDim} (H)$$

Примеры классов VC

Размерность VC конечной проективной плоскости

Конечная проективная плоскость порядка n — это совокупность n ² + n + 1 наборов (называемых «линиями») по n ² + n + 1 элементов (называемых «точками»), для которых:

• В каждой строке ровно n + 1 точка.
• Каждая прямая пересекает любую другую ровно в одной точке.
• Каждая точка содержится ровно в n + 1 строке.
• Каждая точка находится ровно на одной общей линии с каждой другой точкой.
• По крайней мере четыре точки не лежат на одной прямой.

Размерность VC конечной проективной плоскости равна 2.

Доказательство : (а) Для каждой пары различных точек существует одна линия, содержащая обе из них, строки, содержащие только одну из них, и строки, не содержащие ни одной из них, поэтому каждое множество размера 2 разбито. (б) Для любой тройки из трех различных точек, если существует линия x , содержащая все три, то не существует линии y , содержащей ровно две точки (поскольку тогда x и y пересекались бы в двух точках, что противоречит определению проективной плоскости). Следовательно, ни один набор размера 3 не будет разрушен.

Размерность VC повышающего классификатора

Предположим, у нас есть базовый класс $B$ простых классификаторов, размерность VC которых равна $D$.

Мы можем построить более мощный классификатор, объединив несколько разных классификаторов из $B$; этот метод называется повышением . Формально, учитывая $T$ классификаторы $h_{1},\ldots ,h_{T}\in B$ и вектор веса $w\in \mathbb {R} ^{T}$, мы можем определить следующий классификатор:

$f(x)=\operatorname {sign} \left(\sum _{t=1}^{T}w_{t}\cdot h_{t}(x)\right)$

Размерность VC набора всех таких классификаторов (для всех выборок $T$ классификаторы из $B$ и весовой вектор из $\mathbb {R} ^{T}$), предполагая $T,D\geq 3$, не более:

$T\cdot (D+1)\cdot (3\log(T\cdot (D+1))+2)$

VC-размерность нейронной сети

Нейронная сеть описывается ориентированным ациклическим графом G ( V , E ), где:

• V — набор узлов. Каждый узел представляет собой простую вычислительную ячейку.
• E — множество ребер. Каждое ребро имеет вес.
• Вход в сеть представлен источниками графа — узлами без входящих ребер.
• Выход сети представлен стоками графа — узлами без исходящих ребер.
• Каждый промежуточный узел получает на вход взвешенную сумму выходов узлов на его входящих ребрах, где веса — это веса на ребрах.
• Каждый промежуточный узел выводит определенную возрастающую функцию своего входа, например, знаковую функцию или сигмовидную функцию . Эта функция называется функцией активации .

Размерность нейронной сети VC ограничена следующим образом:

• Если функция активации является знаковой функцией, а веса общие, то размерность VC не превышает $O(|E|\cdot \log(|E|))$.
• Если функция активации является сигмовидной функцией, а веса общие, то размерность VC не менее $\Omega (|E|^{2})$ и самое большее $O(|E|^{2}\cdot |V|^{2})$.
• Если веса происходят из конечного семейства (например, веса представляют собой действительные числа, которые могут быть представлены в компьютере максимум 32 битами), то для обеих функций активации размерность VC не превышает $O(|E|)$.

Обобщения

Размерность VC определена для пространств бинарных функций (функций до {0,1}). Было предложено несколько обобщений для пространств небинарных функций.

• Для многоклассовых функций (например, функций {0,..., n-1 }) размерность Натараяна можно использовать. Бен Дэвид и др. дать обобщение этого понятия.
• Для функций с действительным знаком (например, функций с действительным интервалом [0,1]) псевдоразмерность Полларда можно использовать.
• Сложность Радемахера дает границы, аналогичные VC, и иногда может дать больше понимания, чем расчеты размерностей VC, в таких статистических методах, например, с использованием ядер. .
• Емкость памяти (иногда эквивалентная емкость памяти) дает нижнюю границу емкости, а не верхнюю границу (см., например: Искусственная нейронная сеть#Емкость ) и, следовательно, указывает точку потенциального переобучения.

См. также

• Функция роста
• Лемма Зауэра-Шела , ограничение количества множеств в системе множеств с точки зрения размерности VC.
• Теорема Карпинского–Макинтайра , граница размерности VC общих формул Пфаффа.

Ссылки

• Мур, Эндрю. «Учебное пособие по измерениям венчурного капитала» (PDF) .
• Вапник, Владимир (2000). Природа статистической теории обучения . Спрингер.
• Блюмер, А.; Эренфойхт, А.; Хаусслер, Д.; Вармут, МК (1989). «Обучаемость и измерение Вапника – Червоненкиса» (PDF) . Журнал АКМ . 36 (4): 929–865. дои : 10.1145/76359.76371 . S2CID   1138467 .
• Берджес, Кристофер. «Руководство по SVM для распознавания образов» (PDF) . Майкрософт . (содержит информацию также для измерения VC)
• Шазель, Бернар . «Метод противоречий» .
• Натараджан, Б.К. (1989). «Об изучении множеств и функций» . Машинное обучение . 4 : 67–97. дои : 10.1007/BF00114804 .
• Бен-Давид, Шай; Чеза-Бьянки, Николо; Лонг, Филип М. (1992). «Характеристики обучаемости классов {O,…, n }-значных функций». Материалы пятого ежегодного семинара по теории вычислительного обучения – COLT '92 . п. 333. дои : 10.1145/130385.130423 . ISBN  089791497X .
• Поллард, Д. (1984). Сходимость случайных процессов . Спрингер. ISBN  9781461252542 .
• Энтони, Мартин; Бартлетт, Питер Л. (2009). Обучение нейронных сетей: теоретические основы . ISBN  9780521118620 .
• Моргенштерн, Джейми Х.; Рафгарден, Тим (2015). О псевдоразмерности почти оптимальных аукционов . НИПС. arXiv : 1506.03684 . Бибкод : 2015arXiv150603684M .
• Карпински, Марек; Макинтайр, Ангус (февраль 1997 г.). «Полиномиальные границы размерности VC сигмоидальных и общих пфаффовых нейронных сетей» . Журнал компьютерных и системных наук . 54 (1): 169–176. дои : 10.1006/jcss.1997.1477 .