В теории Вапника-Червоненкис , то размерность Вапник-Червоненкис (VC) является мерой способности (сложности, выразительной силы, богатства, или гибкости) набора функций , которые могут быть изучены с помощью статистического бинарной классификации алгоритма . Он определяется как мощность наибольшего набора точек, которые алгоритм может разрушить . Первоначально его определили Владимир Вапник и Алексей Червоненкис . [1]
Неформально емкость модели классификации связана с тем, насколько она может быть сложной. Например, рассмотрим пороговую обработку многочлена высокой степени : если значение многочлена больше нуля, эта точка классифицируется как положительная, иначе как отрицательная. Многочлен высокой степени может быть извилистым, поэтому он может хорошо соответствовать заданному набору обучающих точек. Но можно ожидать, что классификатор будет делать ошибки по другим пунктам, потому что он слишком шаткий. Такой многочлен имеет большую емкость. Гораздо более простой альтернативой является определение порога линейной функции. Эта функция может не подходить для обучающего набора, потому что у него низкая пропускная способность. Это понятие емкости будет уточнено ниже.
Определения
Размер VC набора-семейства
Позволять - семейство множеств (набор множеств) имножество. Их пересечение определяется как следующее семейство множеств:
Мы говорим, что набор будет разрушена по если содержит все подмножества , то есть:
Размер VC из является крупнейшей мощностью множеств подорвана. Если можно разбить произвольно большие подмножества, размер VC равен.
Измерение VC модели классификации
Модель бинарной классификации с некоторым вектором параметров Говорят, что разрушает набор точек данных если для всех присвоений меток этим точкам существует так что модель не делает ошибок при оценке этого набора точек данных.
Размер VC модели - максимальное количество точек, которые можно расположить так, чтобы разбивает их. Формально это максимальный кардинальныйтакой, что некоторый набор точек данных мощности может быть разбит .
Примеры
1. - постоянный классификатор (без параметров). Его размер VC равен 0, так как он не может разбить даже одну точку. В общем, размерность VC конечной классификационной модели, которая может возвращать не более различных классификаторов, не более (это верхняя оценка размерности VC; лемма Зауэра – Шелаха дает нижнюю оценку размерности).
2. - однопараметрический пороговый классификатор по действительным числам; т.е. для определенного порога, классификатор возвращает 1, если входное число больше, чем и 0 в противном случае. Размер венчурного капиталаравен 1, потому что: (a) Он может разбить одну точку. За каждую точку, классификатор помечает это как 0, если и помечает его как 1, если . (b) Он не может разбить ни один набор из двух точек. Для каждого набора из двух чисел, если меньшее помечено 1, то большее также должно быть помечено 1, поэтому не все обозначения возможны.
3. - однопараметрический интервальный классификатор по действительным числам; т.е. для некоторого параметра, классификатор возвращает 1, если входной номер находится в интервале и 0 в противном случае. Размер венчурного капиталаравно 2, потому что: (a) Он может разрушить некоторые наборы из двух точек. Например, для каждого набора, классификатор помечает его как (0,0), если или если , как (1,0), если , как (1,1), если , и как (0,1), если . (b) Он не может разрушить ни одну из трех точек. Для каждого набора из трех чисел, если наименьшее и наибольшее помечены 1, то среднее также должно быть помечено 1, поэтому не все обозначения возможны.
4. представляет собой прямую линию в качестве модели классификации точек на двумерной плоскости (это модель, используемая перцептроном ). Линия должна отделять положительные точки данных от отрицательных. Существуют наборы из 3 точек, которые действительно можно разбить, используя эту модель (любые 3 точки, которые не лежат на одной прямой, могут быть разбиты). Однако ни один набор из 4 точек не может быть разбит: по теореме Радона любые четыре точки можно разбить на два подмножества с пересекающимися выпуклыми оболочками , поэтому невозможно отделить одно из этих двух подмножеств от другого. Таким образом, размер VC этого конкретного классификатора равен 3. Важно помнить, что, хотя можно выбрать любое расположение точек, расположение этих точек не может измениться при попытке разбить для некоторого присвоения метки. Обратите внимание, что для трех точек показаны только 3 из 2 3 = 8 возможных присвоений меток.
3 очка разбиты | 4 балла невозможно |
5. является однопараметрическим синусоидальным классификатором, т.е. по определенному параметру, классификатор возвращает 1, если входной номер имеет и 0 в противном случае. Размер венчурного капитала бесконечно, так как может разрушить любое конечное подмножество множества . [2] : 57
Использует
В статистической теории обучения
Измерение VC может предсказать вероятностную верхнюю границу ошибки теста модели классификации. Вапник [3] доказал, что вероятность ошибки теста (т. Е. Риска с функцией потерь 0-1), отдаляющаяся от верхней границы (для данных, взятых iid из того же распределения, что и обучающая выборка), определяется выражением:
где - размер VC классификационной модели, , а также - размер обучающей выборки (ограничение: эта формула действительна, когда . Когдабольше, ошибка теста может быть намного больше, чем ошибка обучения. Это связано с переоснащением ).
Измерение VC также появляется в границах сложности выборки . Пространство бинарных функций с размерностью VC можно узнать с помощью:
образцы, где ошибка обучения и вероятность отказа. Таким образом, сложность выборки является линейной функцией размера VC пространства гипотез.
В вычислительной геометрии
Размерность ВК - один из критических параметров размера ε-сетей , который определяет сложность алгоритмов аппроксимации на их основе; Наборы диапазонов без конечной размерности VC могут вообще не иметь конечных ε-сетей.
Границы
0. Размерность VC двойственного семейства множеств строго меньше, чем , и это лучше всего.
1. Размерность VC конечного множества-семейства самое большее . [2] : 56 Это потому, что по определению.
2. Учитывая семейство наборов , определять как семейство множеств, которое содержит все пересечения элементы . Тогда: [2] : 57
3. Учитывая семейство наборов и элемент , определять где обозначает симметричную разность множеств . Тогда: [2] : 58
VC размерность конечной проективной плоскости
Конечная проективная плоскость порядка п представляет собой набор из п 2 + п + 1 множеств ( так называемые «линии») в течение п 2 + п + 1 элементов ( так называемые «точки»), для которых:
- Каждая строка содержит ровно n + 1 точку.
- Каждая линия пересекает каждую другую ровно в одной точке.
- Каждая точка содержится ровно в n + 1 строках.
- Каждая точка находится ровно на одной линии, общей с любой другой точкой.
- По крайней мере, четыре точки не лежат на одной линии.
Размерность VC конечной проективной плоскости равна 2. [4]
Доказательство : (a) Для каждой пары различных точек существует одна строка, содержащая их обе, строки, содержащие только одну из них, и строки, не содержащие ни одной из них, поэтому каждый набор размера 2 разбивается. (b) Для любой тройки из трех различных точек, если существует линия x , содержащая все три, то не существует прямой y , содержащей ровно две (поскольку тогда x и y пересекались бы в двух точках, что противоречит определению проективной плоскости). Следовательно, ни один комплект размера 3 не разрушен.
Размер VC повышающего классификатора
Предположим, у нас есть базовый класс простых классификаторов, размерность VC которых .
Мы можем создать более мощный классификатор, объединив несколько разных классификаторов из ; этот метод называется бустингом . Формально, учитывая классификаторы и вектор веса , мы можем определить следующий классификатор:
Размерность VC набора всех таких классификаторов (для всех выборок классификаторы из и вектор веса из ), предполагая , не более: [5] : 108–109
Размер виртуального канала нейронной сети
Нейронной сети описывается ориентированный ациклический граф G ( V , E ), где:
- V - набор узлов. Каждый узел представляет собой простую вычислительную ячейку.
- E - это набор ребер, каждое ребро имеет вес.
- Вход в сеть представлен источниками графа - узлами без входящих ребер.
- Выход сети представлен стоками графа - узлами без исходящих ребер.
- Каждый промежуточный узел получает в качестве входных данных взвешенную сумму выходных данных узлов на его входящих ребрах, где веса - это веса на ребрах.
- Каждый промежуточный узел выводит определенную возрастающую функцию своего входа, такую как функция знака или сигмоидальная функция . Эта функция называется функцией активации .
Размер виртуального канала нейронной сети ограничен следующим образом: [5] : 234–235
- Если функция активации является функцией знака, а веса являются общими, то размерность VC не превосходит .
- Если функция активации является сигмоидной функцией, а веса являются общими, то размерность VC составляет не менее и самое большее .
- Если веса происходят из конечного семейства (например, веса являются действительными числами, которые могут быть представлены на компьютере максимум 32 битами), то для обеих функций активации размер VC не превышает .
Обобщения
Размерность VC определена для пространств двоичных функций (функций до {0,1}). Было предложено несколько обобщений для пространств недвоичных функций.
- Для многозначных функций (функций для {0, ..., n }) можно использовать размерность Натараджана [6] . Бен Дэвид и др. [7] представляют обобщение этой концепции.
- Для функций с действительными значениями (например, функций с действительным интервалом [0,1]) можно использовать псевдоразмерность Полларда [8] [9] [10] .
- Сложность Радемахера обеспечивает аналогичные оценки для VC, и иногда может обеспечить более глубокий , чем расчеты размеров ОК в такие статистические методы , такие как те , которые используют ядра [ править ] .
Смотрите также
- Функция роста
- Лемма Зауэра – Шелаха , оценка количества множеств в системе множеств в терминах размерности VC.
- Теорема Карпинского – Макинтайра , [11] оценка размерности ВК общих формул Пфаффа.
Сноски
- ^ Вапник, ВН; Червоненкис, А.Я. (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.
- ^ а б в г Мохри, Мехриар ; Ростамизаде, Афшин; Талвалкар, Амит (2012). Основы машинного обучения . США, Массачусетс: MIT Press. ISBN 9780262018258.
- ^ Вапник 2000 .
- ^ Alon, N .; Haussler, D .; Вельцль, Э. (1987). «Разбиение и геометрическое вложение пространств значений конечной размерности Вапника-Червоненкиса». Материалы третьего ежегодного симпозиума по вычислительной геометрии - SCG '87 . п. 331. DOI : 10,1145 / 41958,41994 . ISBN 978-0897912310. S2CID 7394360 .
- ^ а б Шалев-Шварц, Шай; Бен-Давид, Шай (2014). Понимание машинного обучения - от теории к алгоритмам . Издательство Кембриджского университета. ISBN 9781107057135.
- ^ Натараджан 1989 .
- ↑ Бен-Давид, Чеза-Бьянки и Лонг 1992 .
- Перейти ↑ Pollard 1984 .
- ^ Энтони и Бартлетт 2009 .
- ^ Моргенштерн и Roughgarden 2015 .
- ^ Карпинский & Макинтайр 1997 .
Рекомендации
- Мур, Эндрю. «Учебник по измерениям ВК» .
- Вапник, Владимир (2000). Природа статистической теории обучения . Springer.
- Blumer, A .; Ehrenfeucht, A .; Haussler, D .; Вармут, МК (1989). «Обучаемость и размерность Вапника – Червоненкиса» (PDF) . Журнал ACM . 36 (4): 929–865. DOI : 10.1145 / 76359.76371 . S2CID 1138467 . CS1 maint: обескураженный параметр ( ссылка )
- Берджес, Кристофер. «Учебник по SVM для распознавания образов» (PDF) . (содержит информацию также для размера ВК)
- Шазель, Бернар . «Метод несоответствия» . CS1 maint: обескураженный параметр ( ссылка )
- Натараджан, Б.К. (1989). «Об обучающих наборах и функциях» . Машинное обучение . 4 : 67–97. DOI : 10.1007 / BF00114804 .
- Бен-Давид, Шай; Чеза-Бьянки, Николо; Лонг, Филип М. (1992). «Характеристики обучаемости для классов {O,…, n } -значных функций». Материалы пятого ежегодного семинара по теории вычислительного обучения - COLT '92 . п. 333. DOI : 10,1145 / 130385,130423 . ISBN 089791497X.
- Поллард, Д. (1984). Сходимость случайных процессов . Springer. ISBN 9781461252542.
- Энтони, Мартин; Бартлетт, Питер Л. (2009). Обучение нейронной сети: теоретические основы . ISBN 9780521118620.
- Morgenstern, Jamie H .; Roughgarden, Тим (2015). О псевдоразмерности аукционов, близких к оптимальным . НИПС. arXiv : 1506.03684 . Bibcode : 2015arXiv150603684M .
- Карпинский, Марек; Макинтайр, Ангус (февраль 1997 г.). "Полиномиальные границы для размерности VC сигмоидальных и общих нейронных сетей Пфаффа" . Журнал компьютерных и системных наук . 54 (1): 169–176. DOI : 10.1006 / jcss.1997.1477 .