Теория Вапника – Червоненкиса. - Vapnik–Chervonenkis theory

Теория Вапника – Червоненкиса. (также известен как Теория ВК) была разработана в 1960–1990 гг. Владимир Вапник и Алексей Червоненкис. Теория - это форма теория вычислительного обучения, который пытается объяснить процесс обучения со статистической точки зрения.

Теория ВК связана с теория статистического обучения и чтобы эмпирические процессы. Ричард М. Дадли и Владимир Вапник, среди прочего, применили теорию ВК к эмпирические процессы.

Вступление

Теория венчурного капитала охватывает как минимум четыре части (как описано в Природа статистической теории обучения^[1]):

• Теория последовательность процессов обучения
  • Каковы (необходимые и достаточные) условия согласованности процесса обучения на основе минимизация эмпирического риска принцип?
• Неасимптотическая теория скорости сходимости процессов обучения
  • Насколько высока скорость сходимости учебного процесса?
• Теория управления обобщающей способностью процессов обучения
  • Как можно контролировать скорость сходимости ( обобщение способности) учебного процесса?
• Теория построения обучающих машин
  • Как можно построить алгоритмы, контролирующие способность к обобщению?

VC Theory - одна из основных ветвей теория статистического обучения. Одно из его основных приложений в теории статистического обучения - обеспечение обобщение условия обучения алгоритмов. С этой точки зрения теория ВК связана с стабильность, который является альтернативным подходом к характеристике обобщения.

Кроме того, теория ВК и Размер ВК играют важную роль в теории эмпирические процессы, в случае процессов, индексированных классами VC. Возможно, это наиболее важные приложения теории ВК, которые используются для доказательства обобщения. Будут представлены несколько методов, которые широко используются в эмпирическом процессе и теории ВК. Обсуждение в основном основано на книге Слабая конвергенция и эмпирические процессы: в приложениях к статистике.^[2]

Обзор теории ВК в эмпирических процессах

Справочная информация об эмпирических процессах

Позволять ${ Displaystyle X_ {1}, ldots, X_ {n}}$ быть случайными элементами, определенными на измеримом пространстве ${ displaystyle ({ mathcal {X}}, { mathcal {A}})}$. По любым меркам ${ displaystyle Q}$ на ${ displaystyle ({ mathcal {X}}, { mathcal {A}})}$, и любые измеримые функции ${ displaystyle f: { mathcal {X}} to mathbf {R}}$, определять

${ Displaystyle Qf = int fdQ}$

Проблемы измеримости здесь будут проигнорированы, для получения более подробной технической информации см. ^[3]. Позволять ${ Displaystyle { mathcal {F}}}$ - класс измеримых функций ${ displaystyle f: { mathcal {X}} to mathbf {R}}$ и определите:

${ displaystyle | Q | _ { mathcal {F}} = sup { vert Qf vert : f in { mathcal {F}} }.}$

Определите эмпирическую меру

${ displaystyle mathbb {P} _ {n} = n ^ {- 1} sum _ {i = 1} ^ {n} delta _ {X_ {i}},}$

куда δ здесь означает Мера Дирака. Эмпирическая мера индуцирует отображение ${ Displaystyle { mathcal {F}} to mathbf {R}}$ предоставлено:

${ displaystyle f mapsto mathbb {P} _ {n} f = { frac {1} {n}} (f (X_ {1}) + ... + f (X_ {n}))}$

Теперь предположим п является лежащим в основе истинным распределением данных, которое неизвестно. Теория эмпирических процессов направлена ​​на определение классов ${ Displaystyle { mathcal {F}}}$ для которых справедливы такие утверждения, как следующие:

• униформа закон больших чисел:

  ${ displaystyle | mathbb {P} _ {n} -P | _ { mathcal {F}} { underset {n} { to}} 0,}$

То есть как ${ Displaystyle п к infty}$,

${ displaystyle left | { frac {1} {n}} (f (X_ {1}) + ... + f (X_ {n})) - int fdP right | to 0}$

равномерно для всех ${ displaystyle f in { mathcal {F}}}$.

• униформа Центральная предельная теорема:

${ displaystyle mathbb {G} _ {n} = { sqrt {n}} ( mathbb {P} _ {n} -P) rightsquigarrow mathbb {G}, quad { text {in}} ell ^ { infty} ({ mathcal {F}})}$

В первом случае ${ Displaystyle { mathcal {F}}}$ называется Гливенко-Кантелли класс, а в последнем случае (в предположении ${ displaystyle forall x, sup nolimits _ {f in { mathcal {F}}} vert f (x) -Pf vert < infty}$) класс ${ Displaystyle { mathcal {F}}}$ называется Донскер или же п-Донскер. Класс Донскера является вероятностным по Гливенко-Кантелли применением Теорема Слуцкого .

Эти утверждения верны для одного ${ displaystyle f}$, по стандарту LLN, CLT аргументы в условиях регулярности, и трудность эмпирических процессов возникает из-за того, что совместные утверждения делаются для всех ${ displaystyle f in { mathcal {F}}}$. Тогда интуитивно множество ${ Displaystyle { mathcal {F}}}$ не может быть слишком большим, и, как оказывается, геометрия ${ Displaystyle { mathcal {F}}}$ играет очень важную роль.

Один из способов измерения размера набора функций ${ Displaystyle { mathcal {F}}}$ заключается в использовании так называемого покрывающие числа. Покровный номер

${ Displaystyle N ( varepsilon, { mathcal {F}}, | cdot |)}$

минимальное количество шаров ${ Displaystyle {г: | г-е | < varepsilon }}$ необходимо покрыть набор ${ Displaystyle { mathcal {F}}}$ (здесь, очевидно, предполагается, что существует основная норма на ${ Displaystyle { mathcal {F}}}$). Энтропия - это логарифм числа покрытия.

Ниже приведены два достаточных условия, при которых можно доказать, что множество ${ Displaystyle { mathcal {F}}}$ это Гливенко-Кантелли или Донскер.

Класс ${ Displaystyle { mathcal {F}}}$ является п-Гливенко-Кантелли, если это п-меряется с конвертом F такой, что ${ Displaystyle P ^ { ast} F < infty}$ и удовлетворяет:

${ Displaystyle forall varepsilon> 0 quad sup nolimits _ {Q} N ( varepsilon | F | _ {Q}, { mathcal {F}}, L_ {1} (Q)) < infty.}$

Следующее условие - разновидность знаменитого Теорема Дадли. Если ${ Displaystyle { mathcal {F}}}$ - класс функций таких, что

${ displaystyle int _ {0} ^ { infty} sup nolimits _ {Q} { sqrt { log N left ( varepsilon | F | _ {Q, 2}, { mathcal { F}}, L_ {2} (Q) right)}} d varepsilon < infty}$

тогда ${ Displaystyle { mathcal {F}}}$ является п-Donsker для каждой вероятностной меры п такой, что ${ Displaystyle P ^ { ast} F ^ {2} < infty}$. В последнем интеграле обозначения означают

${ Displaystyle | е | _ {Q, 2} = left ( int | f | ^ {2} dQ right) ^ { frac {1} {2}}}$.

Симметризация

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

Рассмотрим эмпирический процесс:

${ displaystyle f mapsto ( mathbb {P} _ {n} -P) f = { dfrac {1} {n}} sum _ {i = 1} ^ {n} (f (X_ {i} )-ПФ)}$

Оказывается, существует связь между эмпирическим и следующим симметризованным процессом:

${ displaystyle f mapsto mathbb {P} _ {n} ^ {0} f = { dfrac {1} {n}} sum _ {i = 1} ^ {n} varepsilon _ {i} f (X_ {i})}$

Симметризованный процесс - это Процесс Радемахера, условно по данным ${ displaystyle X_ {i}}$. Следовательно, это субгауссов процесс по Неравенство Хёффдинга.

Лемма (симметризация). Для каждого неубывающего выпуклого Φ: р → р и класс измеримых функций ${ Displaystyle { mathcal {F}}}$,

${ displaystyle mathbb {E} Phi ( | mathbb {P} _ {n} -P | _ { mathcal {F}}) leq mathbb {E} Phi left (2 left | mathbb {P} _ {n} ^ {0} right | _ { mathcal {F}} right)}$

Доказательство леммы о симметризации основано на введении независимых копий исходных переменных ${ displaystyle X_ {i}}$ (иногда называемый образец призрака) и заменяя этими копиями внутреннее ожидание ЛГС. После применения Неравенство Дженсена можно было ввести разные знаки (отсюда и название «симметризация») без изменения ожидания. Доказательство можно найти ниже из-за его поучительного характера.

Типичный способ доказательства эмпирических CLT: сначала используется симметризация, чтобы передать эмпирический процесс в ${ displaystyle mathbb {P} _ {n} ^ {0}}$ а затем аргументируют условно данные, используя тот факт, что процессы Радемахера - это простые процессы с хорошими свойствами.

Подключение VC

Оказывается, существует интересная связь между некоторыми комбинаторными свойствами множества ${ Displaystyle { mathcal {F}}}$ и числа энтропии. Равномерные покрывающие числа можно контролировать с помощью понятия Классы множеств Вапника-Червоненкиса - или в ближайшее время Наборы ВК.

Рассмотрим коллекцию ${ displaystyle { mathcal {C}}}$ подмножеств пространства выборки ${ displaystyle { mathcal {X}}}$. ${ displaystyle { mathcal {C}}}$ говорят выбрать определенное подмножество ${ displaystyle W}$ конечного множества ${ Displaystyle S = {x_ {1}, ldots, x_ {n} } subset { mathcal {X}}}$ если ${ Displaystyle W = S cap C}$ для некоторых ${ displaystyle C in { mathcal {C}}}$. ${ displaystyle { mathcal {C}}}$ говорят разбить S если он выберет каждый из своих 2^п подмножества. В VC-индекс (похожий на Размер ВК +1 за правильно выбранный набор классификаторов) ${ Displaystyle V ({ mathcal {C}})}$ из ${ displaystyle { mathcal {C}}}$ самый маленький п для которых нет набора размеров п разбит ${ displaystyle { mathcal {C}}}$.

Лемма зауэра затем заявляет, что число ${ displaystyle Delta _ {n} ({ mathcal {C}}, x_ {1}, ldots, x_ {n})}$ подмножеств, выбранных VC-классом ${ displaystyle { mathcal {C}}}$ удовлетворяет:

${ displaystyle max _ {x_ {1}, ldots, x_ {n}} Delta _ {n} ({ mathcal {C}}, x_ {1}, ldots, x_ {n}) leq sum _ {j = 0} ^ {V ({ mathcal {C}}) - 1} {n choose j} leq left ({ frac {ne} {V ({ mathcal {C}}) ) -1}} right) ^ {V ({ mathcal {C}}) - 1}}$

Какое полиномиальное число ${ Displaystyle О (п ^ {V ({ mathcal {C}}) - 1})}$ подмножеств, а не экспоненциальное число. Интуитивно это означает, что из конечного VC-индекса следует, что ${ displaystyle { mathcal {C}}}$ имеет очевидную упрощенную структуру.

Аналогичную оценку можно показать (с другой постоянной, той же скоростью) для так называемого Классы подграфов VC. Для функции ${ displaystyle f: { mathcal {X}} to mathbf {R}}$ в подграф это подмножество ${ Displaystyle { mathcal {X}} times mathbf {R}}$ такой, что: ${ Displaystyle {(х, т): т <е (х) }}$. Коллекция ${ Displaystyle { mathcal {F}}}$ называется классом подграфа VC, если все подграфы образуют VC-класс.

Рассмотрим набор индикаторных функций ${ displaystyle { mathcal {I}} _ { mathcal {C}} = {1_ {C}: C in { mathcal {C}} }}$ в ${ displaystyle L_ {1} (Q)}$ для дискретного эмпирического типа меры Q (или эквивалентно для любой вероятностной меры Q). Тогда можно показать, что весьма примечательно для ${ displaystyle r geq 1}$:

${ Displaystyle N ( varepsilon, { mathcal {I}} _ { mathcal {C}}, L_ {r} (Q)) leq KV ({ mathcal {C}}) (4e) ^ {V ({ mathcal {C}})} varepsilon ^ {- r (V ({ mathcal {C}}) - 1)}}$

Далее рассмотрим симметричная выпуклая оболочка набора ${ Displaystyle { mathcal {F}}}$: ${ displaystyle operatorname {sconv} { mathcal {F}}}$ являясь набором функций формы ${ Displaystyle сумма _ {я = 1} ^ {м} альфа _ {я} е_ {я}}$ с ${ Displaystyle сумма _ {я = 1} ^ {м} | альфа _ {я} | Leq 1}$. Тогда если

${ Displaystyle N left ( varepsilon | F | _ {Q, 2}, { mathcal {F}}, L_ {2} (Q) right) leq C varepsilon ^ {- V}}$

для выпуклой оболочки ${ Displaystyle { mathcal {F}}}$:

${ displaystyle log N left ( varepsilon | F | _ {Q, 2}, operatorname {sconv} { mathcal {F}}, L_ {2} (Q) right) leq K варепсилон ^ {- { frac {2V} {V + 2}}}}$

Важным следствием этого факта является то, что

${ displaystyle { frac {2V} {V + 2}}> 2,}$

чего как раз достаточно, чтобы интеграл энтропии сходился, и, следовательно, класс ${ displaystyle operatorname {sconv} { mathcal {F}}}$ будет п-Донскер.

Наконец, рассматривается пример класса VC-подграфа. Любое конечномерное векторное пространство ${ Displaystyle { mathcal {F}}}$ измеримых функций ${ displaystyle f: { mathcal {X}} to mathbf {R}}$ VC-подграф индекса меньше или равен ${ displaystyle dim ({ mathcal {F}}) + 2}$.

Существуют обобщения понятия класса подграфа VC, например есть понятие псевдоразмерности. Заинтересованный читатель может заглянуть в^[4].

VC Inequality

Рассматривается аналогичная настройка, которая чаще встречается в машинное обучение. Позволять ${ displaystyle { mathcal {X}}}$ это пространство функций и ${ Displaystyle { mathcal {Y}} = {0,1 }}$. Функция ${ displaystyle f: { mathcal {X}} to { mathcal {Y}}}$ называется классификатором. Позволять ${ Displaystyle { mathcal {F}}}$ быть набором классификаторов. Как и в предыдущем разделе, определите коэффициент разрушения (также известная как функция роста):

${ displaystyle S ({ mathcal {F}}, n) = max _ {x_ {1}, ldots, x_ {n}} | {(f (x_ {1}), ldots, f ( x_ {n})), f in { mathcal {F}} } |}$

Обратите внимание, что между каждой из функций в ${ Displaystyle { mathcal {F}}}$ и множество, на котором функция равна 1. Таким образом, мы можем определить ${ displaystyle { mathcal {C}}}$ быть набором подмножеств, полученных из указанного выше отображения для каждого ${ displaystyle f in { mathcal {F}}}$. Следовательно, в терминах предыдущего раздела коэффициент дробления точно равен

${ displaystyle max _ {x_ {1}, ldots, x_ {n}} Delta _ {n} ({ mathcal {C}}, x_ {1}, ldots, x_ {n})}$.

Эта эквивалентность вместе с Лемма Зауэра подразумевает, что ${ Displaystyle S ({ mathcal {F}}, п)}$ будет полиномиальным от п, для достаточно больших п при условии, что сбор ${ displaystyle { mathcal {C}}}$ имеет конечный VC-индекс.

Позволять ${ Displaystyle D_ {п} = {(X_ {1}, Y_ {1}), ldots, (X_ {n}, Y_ {m}) }}$ - наблюдаемый набор данных. Предположим, что данные генерируются неизвестным распределением вероятностей ${ displaystyle P_ {XY}}$. Определять ${ Displaystyle R (е) = п (е (X) neq Y)}$ быть ожидаемым 0/1 проигрыш. Конечно с тех пор ${ displaystyle P_ {XY}}$ неизвестно вообще, нет доступа к ${ Displaystyle R (f)}$. Тем не менее эмпирический риск, предоставленный:

${ displaystyle { hat {R}} _ {n} (f) = { dfrac {1} {n}} sum _ {i = 1} ^ {n} mathbb {I} (f (X_ { i}) neq Y_ {i})}$

конечно можно оценить. Тогда справедлива следующая Теорема:

Теорема (неравенство ВК)

Для двоичной классификации и функции потерь 0/1 мы имеем следующие границы обобщения:

${ Displaystyle { begin {align} P left ( sup _ {f in { mathcal {F}}} left | { hat {R}} _ {n} (f) -R (f) right |> varepsilon right) & leq 8S ({ mathcal {F}}, n) e ^ {- n varepsilon ^ {2} / 32} mathbb {E} left [ sup _ {f in { mathcal {F}}} left | { hat {R}} _ {n} (f) -R (f) right | right] & leq 2 { sqrt { dfrac { log S ({ mathcal {F}}, n) + log 2} {n}}} end {выровнен}}}$

На словах неравенство ВК означает, что по мере увеличения выборки при условии, что ${ Displaystyle { mathcal {F}}}$ имеет конечный размер венчурного капитала, эмпирический риск 0/1 становится хорошим показателем ожидаемого риска 0/1. Обратите внимание, что обе правые части двух неравенств будут сходиться к 0 при условии, что ${ Displaystyle S ({ mathcal {F}}, п)}$ полиномиально растет по п.

Связь между этой структурой и структурой эмпирического процесса очевидна. Здесь мы имеем дело с модифицированным эмпирическим процессом.

${ displaystyle left | { hat {R}} _ {n} -R right | _ { mathcal {F}}}$

но неудивительно, что идеи совпадают. Доказательство неравенства ВК (первая часть) опирается на симметризацию, а затем условно аргументирует данные, используя неравенства концентрации (в частности, Неравенство Хёффдинга ). Заинтересованный читатель может проверить книгу ^[5] Теоремы 12.4 и 12.5.

Рекомендации

• ^ Вапник Владимир Н (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. Дои:10.1137/1116025.