Теория Вапника – Червоненкиса (также известная как теория ВК ) была разработана в 1960–1990 гг. Владимиром Вапником и Алексеем Червоненкисом . Теория представляет собой форму теории вычислительного обучения , которая пытается объяснить процесс обучения со статистической точки зрения.
Теория ВК связана с теорией статистического обучения и эмпирическими процессами . Ричард М. Дадли и Владимир Вапник , среди прочих, применили теорию ВК к эмпирическим процессам .
Вступление
Теория ВК включает как минимум четыре части (как объясняется в «Природа статистической теории обучения» [1] ):
- Теория согласованности учебных процессов
- Каковы (необходимые и достаточные) условия согласованности процесса обучения на основе принципа минимизации эмпирического риска ?
- Неасимптотическая теория скорости сходимости процессов обучения
- Насколько высока скорость сходимости учебного процесса?
- Теория управления обобщающей способностью процессов обучения
- Как можно контролировать скорость сходимости ( способность к обобщению ) процесса обучения?
- Теория построения обучающих машин
- Как можно построить алгоритмы, контролирующие способность к обобщению?
Теория ВК - основная ветвь теории статистического обучения . Одно из его основных приложений в теории статистического обучения - обеспечение условий обобщения для алгоритмов обучения. С этой точки зрения теория ВК связана со стабильностью , которая является альтернативным подходом к характеристике обобщения.
Кроме того, теория VC и измерение VC играют важную роль в теории эмпирических процессов в случае процессов, индексируемых классами VC. Возможно, это наиболее важные приложения теории ВК, которые используются для доказательства обобщения. Будет представлено несколько методов, которые широко используются в эмпирическом процессе и теории ВК. Обсуждение в основном основано на книге « Слабая конвергенция и эмпирические процессы: приложения к статистике» . [2]
Обзор теории ВК в эмпирических процессах
Справочная информация об эмпирических процессах
Позволять быть случайными элементами, определенными на измеримом пространстве . По любым меркам на , и любые измеримые функции , определять
Вопросы измеримости здесь будут проигнорированы, более технические подробности см. В [3] . Позволять - класс измеримых функций и определите:
Определите эмпирическую меру
где δ здесь обозначает меру Дирака . Эмпирическая мера индуцирует отображение предоставлено:
Теперь предположим, что P является лежащим в основе истинным распределением данных, которое неизвестно. Теория эмпирических процессов направлена на определение классов для которых справедливы такие утверждения, как следующие:
- единый закон больших чисел :
- То есть как ,
- равномерно для всех .
- равномерная центральная предельная теорема :
В первом случае называется классом Гливенко-Кантелли , и в последнем случае (в предположении) класс называется Донскер или П- Донскер. Класс Донскера является вероятностным по Гливенко-Кантелли по применению теоремы Слуцкого .
Эти утверждения верны для одного , стандартными аргументами LLN , CLT в условиях регулярности, а трудность эмпирических процессов заключается в том, что совместные утверждения делаются для всех. Тогда интуитивно множество не может быть слишком большим, и, как выясняется, геометрия играет очень важную роль.
Один из способов измерения размера набора функций заключается в использовании так называемых покрывающих чисел . Покровный номер
минимальное количество шаров необходимо покрыть набор (здесь, очевидно, предполагается, что существует основная норма на ). Энтропия - это логарифм числа покрытия.
Ниже приведены два достаточных условия, при которых можно доказать, что множество это Гливенко-Кантелли или Донскер.
Класс является P -Гливенко-Кантелли, если он P -измерим с огибающей F такой, что и удовлетворяет:
Следующее условие - это версия знаменитой теоремы Дадли . Если - класс функций таких, что
тогда является P -донскеровским для любой вероятностной меры P такой, что. В последнем интеграле обозначения означают
- .
Симметризация
Большинство аргументов о том, как ограничить эмпирический процесс, основываются на симметризации, максимальном и концентрационном неравенствах и цепочках. Симметризация обычно является первым шагом доказательств, и, поскольку она используется во многих доказательствах машинного обучения для ограничения эмпирических функций потерь (включая доказательство неравенства ВК, которое обсуждается в следующем разделе), она представлена здесь.
Рассмотрим эмпирический процесс:
Оказывается, существует связь между эмпирическим и следующим симметризованным процессом:
Симметризованный процесс - это процесс Радемахера , обусловленный данными. Следовательно, это субгауссовский процесс по неравенству Хёффдинга .
Лемма (симметризация). Для любого неубывающего выпуклого Φ: R → R и класса измеримых функций,
Доказательство леммы о симметризации основано на введении независимых копий исходных переменных (иногда называемый призрачным образцом ) и заменяя внутреннее ожидание LHS этими копиями. После применения неравенства Дженсена можно было вводить разные знаки (отсюда и название «симметризация») без изменения математического ожидания. Доказательство можно найти ниже из-за его поучительного характера.
Представьте "призрачный образец" быть независимыми копиями . Для фиксированных значений надо:
Следовательно, по неравенству Дженсена :
Принимая ожидание в отношении дает:
Обратите внимание, что добавление знака минус перед термином не изменяет RHS, потому что это симметричная функция а также . Следовательно, RHS остается прежним при "возмущении знака":
для любой . Следовательно:
Наконец, используя сначала неравенство треугольника, а затем выпуклость дает:
Где два последних выражения в правой части совпадают, что завершает доказательство.
Типичный способ доказательства эмпирических CLT, сначала использует симметризацию, чтобы передать эмпирический процесс в а затем аргументируют условно данные, используя тот факт, что процессы Радемахера - это простые процессы с хорошими свойствами.
Подключение VC
Оказывается, существует интересная связь между некоторыми комбинаторными свойствами множества и числа энтропии. Равномерные числа покрытия можно контролировать с помощью понятия классов множеств Вапника-Червоненкиса или, сокращенно, множеств VC .
Рассмотрим коллекцию подмножеств пространства выборки . Говорят, что выбирает определенное подмножество конечного множества если для некоторых . Говорят, что он разрушит S, если выберет каждое из своих 2 n подмножеств. ВК-индекс ( по аналогии с VC размерности + 1 для соответствующего выбранного набора классификатора) из это наименьшее n, для которого ни один набор размера n не разрушается.
Затем лемма Зауэра утверждает, что число подмножеств, выбранных VC-классом удовлетворяет:
Это полиномиальное число подмножеств, а не экспоненциальное число. Интуитивно это означает, что из конечного VC-индекса следует, что имеет очевидную упрощенную структуру.
Аналогичная граница может быть показана (с другой константой, той же скоростью) для так называемых классов подграфов VC . Для функцииподграф является подмножеством такой, что: . Коллекция называется классом подграфа VC, если все подграфы образуют VC-класс.
Рассмотрим набор индикаторных функций в для дискретной эмпирической меры Q (или, что то же самое, для любой вероятностной меры Q ). Тогда можно показать, что весьма примечательно, что для:
Далее рассмотрим симметричную выпуклую оболочку множества: являясь набором функций формы с участием . Тогда если
для выпуклой оболочки :
Важным следствием этого факта является то, что
чего как раз достаточно, чтобы интеграл энтропии сходился, и, следовательно, класс будет П- Донскером.
Наконец, рассматривается пример класса VC-подграфа. Любое конечномерное векторное пространство измеримых функций VC-подграф индекса меньше или равен .
Брать точки . Векторы:
находятся в n - 1 мерном подпространстве в R n . Возьмите ≠ 0 , вектор, ортогональный к этому подпространству. Следовательно:
Рассмотрим множество . Этот набор нельзя выбрать, так как если есть какие-то такой, что это означало бы, что LHS строго положительный, но RHS неположительный.
Существуют обобщения понятия класса подграфов VC, например, понятие псевдоразмерности. Заинтересованный читатель может заглянуть в [4] .
VC Inequality
Рассматривается аналогичная настройка, которая более характерна для машинного обучения . Позволять пространство функций и . Функцияназывается классификатором. Позволятьбыть набором классификаторов. Как и в предыдущем разделе, определите коэффициент разрушения (также известный как функция роста):
Обратите внимание, что между каждой из функций в и множество, на котором функция равна 1. Таким образом, мы можем определить быть набором подмножеств, полученных из приведенного выше отображения для каждого . Следовательно, в терминах предыдущего раздела коэффициент дробления точно равен
- .
Из этой эквивалентности вместе с леммой Зауэра следует, чтобудет полиномиальным от n для достаточно большого n при условии, что набор имеет конечный VC-индекс.
Позволять это наблюдаемый набор данных. Предположим, что данные генерируются неизвестным распределением вероятностей. Определятьбыть ожидаемым убытком 0/1 . Конечно с тех пор неизвестно вообще, нет доступа к . Однако эмпирический риск , определяемый по формуле:
конечно можно оценить. Тогда справедлива следующая Теорема:
Теорема (неравенство ВК)
Для бинарной классификации и функции потерь 0/1 мы имеем следующие границы обобщения:
На словах неравенство ВК означает, что по мере увеличения выборки при условии, что имеет конечный размер венчурного капитала, эмпирический риск 0/1 становится хорошим показателем ожидаемого риска 0/1. Обратите внимание, что обе правые части двух неравенств будут сходиться к 0 при условии, чтополиномиально растет по n .
Связь между этой структурой и структурой эмпирического процесса очевидна. Здесь мы имеем дело с модифицированным эмпирическим процессом.
но неудивительно, что идеи совпадают. Доказательство неравенства ВК (первая часть) основывается на симметризации, а затем на условных аргументах на основе данных с использованием неравенств концентрации (в частности , неравенства Хёффдинга ). Заинтересованный читатель может проверить книгу [5] Теоремы 12.4 и 12.5.
Рекомендации
- ^ Вапника Владимир N (2000). Природа статистической теории обучения . Информатика и статистика. Springer-Verlag . ISBN 978-0-387-98780-4.
- Вапник, Владимир Н (1989).Статистическая теория обучения. Wiley-Interscience . ISBN 978-0-471-03003-4.
- ^ван дер Ваарт, Аад В .; Веллнер, Джон А. (2000). Слабая сходимость и эмпирические процессы: с приложениями к статистике (2-е изд.). Springer. ISBN 978-0-387-94640-5.
- ^Gyorfi, L .; Devroye, L .; Лугоши, Г. (1996). Вероятностная теория распознавания образов (1-е изд.). Springer. ISBN 978-0387946184.
- См. Ссылки в статьях: Ричард М. Дадли , эмпирические процессы , Разрушенное множество .
- ^Поллард, Дэвид (1990). Эмпирические процессы: теория и приложения. Серия региональных конференций NSF-CBMS по вероятности и статистике, Том 2. ISBN 978-0-940600-16-4.
- Bousquet, O .; Boucheron, S .; Лугоши, Г. (2004). «Введение в статистическую теорию обучения». У О. Буске; У. фон Люксбург; Г. Ратч (ред.). Расширенные лекции по машинному обучению . Конспект лекций по искусственному интеллекту. 3176 . Springer. С. 169–207.
- Вапник, В .; Червоненкис, А. (2004). «О равномерной сходимости относительных частот событий к их вероятностям». Теория вероятн. Прил . 16 (2): 264–280. DOI : 10.1137 / 1116025 .