Размерность Вапника–Червоненкиса

Понятие в контролируемом машинном обучении

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

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

Определения

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

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

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

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

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

Размерность VC — это мощность наибольшего множества, которое разрушается . Если произвольно большие множества могут быть разрушены, размерность VC равна . ${\displaystyle D}$ ${\displaystyle H}$ ${\displaystyle H}$ ${\displaystyle \infty }$

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

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

Измерение VC модели — это максимальное количество точек, которые можно расположить так, чтобы они разбились. Более формально, это максимальный кардинал, такой, что существует в целом позиционированный набор точек данных с кардинальностью , который может быть раздроблен . ${\displaystyle f}$ ${\displaystyle f}$ ${\displaystyle D}$ ${\displaystyle D}$ ${\displaystyle f}$

Примеры

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

Использует

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

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

${\displaystyle \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 ,}$

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

Измерение VC также появляется в границах сложности выборки . Пространство бинарных функций с измерением VC может быть изучено с помощью: ^{[4] : 73} ${\displaystyle D}$

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

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

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

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

Границы

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

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

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

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

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

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

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

Измерение VC усиливающего классификатора

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

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

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

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

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

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

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

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

Размерность VC нейронной сети ограничена следующим образом: ^{[4] : 234–235}

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

Обобщения

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

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

Смотрите также

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

Сноски

1. Вапник, В. Н.; Червоненкис, А. Я. (1971). «О равномерной сходимости относительных частот событий к их вероятностям». Теория вероятностей и ее приложения . 16 (2): 264. doi :10.1137/1116025.Это английский перевод, сделанный Б. Секлером, русской статьи: "О равномерной сходимости относительных частот событий к их вероятностям". Докл. АН . 181 (4): 781. 1968.Перевод был воспроизведен как: Вапник, В. Н.; Червоненкис, А. Я. (2015). "О равномерной сходимости относительных частот событий к их вероятностям". Меры сложности . стр. 11. doi :10.1007/978-3-319-21852-6_3. ISBN 978-3-319-21851-9.
2. Mohri, Mehryar ; Rostamizadeh, Afshin; Talwalkar, Ameet (2012). Основы машинного обучения . США, Массачусетс: MIT Press. ISBN 9780262018258.
3. Вапник 2000.
4. Шалев-Шварц, Шай; Бен-Дэвид, Шай (2014). Понимание машинного обучения – от теории к алгоритмам . Cambridge University Press. ISBN 9781107057135.
5. Алон, Н.; Хаусслер, Д.; Вельцль, Э. (1987). "Разбиение и геометрическое вложение пространств диапазонов конечной размерности Вапника-Червоненкиса". Труды третьего ежегодного симпозиума по вычислительной геометрии – SCG '87 . стр. 331. doi :10.1145/41958.41994. ISBN 978-0897912310. S2CID  7394360.
6. Natarajan 1989.
7. Брухим 2022. sfn error: no target: CITEREFBrukhim2022 (help)
8. Поллард 1984.
9. Энтони и Бартлетт 2009.
10. Моргенштерн и Рафгарден 2015.
11. Карпински и Макинтайр 1997.

Ссылки

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