Vapnik–Chervonenkis theory

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

Введение

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

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

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

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

Обзор теории венчурного капитала в эмпирических процессах

Общие сведения об эмпирических процессах

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

$Qf=\int fdQ$

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

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

Позволять $X_{1},\ldots ,X_{n}$ быть независимыми, одинаково распределенными случайными элементами $({\mathcal {X}},{\mathcal {A}})$. Затем определим эмпирическую меру

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

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

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

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

• единый закон больших чисел :

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

То есть, как $n\to \infty$,

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

одинаково для всех $f\in {\mathcal {F}}$.

• равномерная центральная предельная теорема :

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

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

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

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

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

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

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

Класс ${\mathcal {F}}$ является P -Гливенко–Кантелли, если он P -измерим с огибающей F такой, что $P^{\ast }F<\infty$ и удовлетворяет:

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

Следующее условие представляет собой вариант знаменитой теоремы Дадли . Если ${\mathcal {F}}$ — это класс функций таких, что

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

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

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

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

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

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

$f\mapsto (\mathbb {P} _{n}-P)f={\dfrac {1}{n}}\sum _{i=1}^{n}(f(X_{i})-Pf)$

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

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

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

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

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

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

Доказательство

Представляем «призрачный образец» $Y_{1},\ldots ,Y_{n}$ быть независимыми копиями $X_{1},\ldots ,X_{n}$. Для фиксированных значений $X_{1},\ldots ,X_{n}$ у одного есть:

$\|\mathbb {P} _{n}-P\|_{\mathcal {F}}=\sup _{f\in {\mathcal {F}}}{\dfrac {1}{n}}\left|\sum _{i=1}^{n}f(X_{i})-\mathbb {E} f(Y_{i})\right|\leq \mathbb {E} _{Y}\sup _{f\in {\mathcal {F}}}{\dfrac {1}{n}}\left|\sum _{i=1}^{n}f(X_{i})-f(Y_{i})\right|$

Следовательно, по неравенству Йенсена :

$\Phi (\|\mathbb {P} _{n}-P\|_{\mathcal {F}})\leq \mathbb {E} _{Y}\Phi \left(\left\|{\dfrac {1}{n}}\sum _{i=1}^{n}f(X_{i})-f(Y_{i})\right\|_{\mathcal {F}}\right)$

Ожидание относительно $X$ дает:

$\mathbb {E} \Phi (\|\mathbb {P} _{n}-P\|_{\mathcal {F}})\leq \mathbb {E} _{X}\mathbb {E} _{Y}\Phi \left(\left\|{\dfrac {1}{n}}\sum _{i=1}^{n}f(X_{i})-f(Y_{i})\right\|_{\mathcal {F}}\right)$

Обратите внимание, что добавление знака минус перед термином $f(X_{i})-f(Y_{i})$ не меняет правую часть, потому что это симметричная функция $X$ и $Y$. Следовательно, правая часть остается неизменной при «возмущении знака»:

$\mathbb {E} \Phi \left(\left\|{\dfrac {1}{n}}\sum _{i=1}^{n}e_{i}\left(f(X_{i})-f(Y_{i})\right)\right\|_{\mathcal {F}}\right)$

для любого $(e_{1},e_{2},\ldots ,e_{n})\in \{-1,1\}^{n}$. Поэтому:

$\mathbb {E} \Phi (\|\mathbb {P} _{n}-P\|_{\mathcal {F}})\leq \mathbb {E} _{\varepsilon }\mathbb {E} \Phi \left(\left\|{\dfrac {1}{n}}\sum _{i=1}^{n}\varepsilon _{i}\left(f(X_{i})-f(Y_{i})\right)\right\|_{\mathcal {F}}\right)$

Наконец, используя сначала неравенство треугольника, а затем выпуклость $\Phi$ дает:

$\mathbb {E} \Phi (\|\mathbb {P} _{n}-P\|_{\mathcal {F}})\leq {\dfrac {1}{2}}\mathbb {E} _{\varepsilon }\mathbb {E} \Phi \left(2\left\|{\dfrac {1}{n}}\sum _{i=1}^{n}\varepsilon _{i}f(X_{i})\right\|_{\mathcal {F}}\right)+{\dfrac {1}{2}}\mathbb {E} _{\varepsilon }\mathbb {E} \Phi \left(2\left\|{\dfrac {1}{n}}\sum _{i=1}^{n}\varepsilon _{i}f(Y_{i})\right\|_{\mathcal {F}}\right)$

Где последние два выражения в правой части совпадают, что и завершает доказательство.

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

Соединение ВК

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

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

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

$\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}$

Что является полиномиальным числом $O(n^{V({\mathcal {C}})-1})$ подмножеств, а не экспоненциальное число. Интуитивно это означает, что конечный индекс VC означает, что ${\mathcal {C}}$ имеет кажущуюся упрощенную структуру.

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

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

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

Далее рассмотрим симметричную выпуклую оболочку множества ${\mathcal {F}}$: $\operatorname {sconv} {\mathcal {F}}$ являющийся набором функций вида $\sum _{i=1}^{m}\alpha _{i}f_{i}$ с $\sum _{i=1}^{m}|\alpha _{i}|\leq 1$. Тогда, если

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

для выпуклой оболочки справедливо следующее ${\mathcal {F}}$:

$\log N\left(\varepsilon \|F\|_{Q,2},\operatorname {sconv} {\mathcal {F}},L_{2}(Q)\right)\leq K\varepsilon ^{-{\frac {2V}{V+2}}}$

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

${\frac {2V}{V+2}}<2,$

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

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

Доказательство: Возьмите $n=\dim({\mathcal {F}})+2$ очки $(x_{1},t_{1}),\ldots ,(x_{n},t_{n})$. Векторы:

$(f(x_{1}),\ldots ,f(x_{n}))-(t_{1},\ldots ,t_{n})$

находятся в n − 1- мерном подпространстве R ^н . Возьмем a ≠ 0 — вектор, ортогональный этому подпространству. Поэтому:

$\sum _{a_{i}>0}a_{i}(f(x_{i})-t_{i})=\sum _{a_{i}<0}(-a_{i})(f(x_{i})-t_{i}),\quad \forall f\in {\mathcal {F}}$

Рассмотрим набор $S=\{(x_{i},t_{i}):a_{i}>0\}$. Этот набор невозможно выбрать, так как если он есть $f$ такой, что $S=\{(x_{i},t_{i}):f(x_{i})>t_{i}\}$ это означало бы, что левая шкала строго положительна, а правая не положительна.

Существуют обобщения понятия класса подграфа VC, например, понятие псевдоразмерности.

Неравенство венчурного капитала

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

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

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

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

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

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

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

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

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

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

${\begin{aligned}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{aligned}}$

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

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

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

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

Ссылки

• См. ссылки в статьях: Ричард М. Дадли , Эмпирические процессы , Разрушенное множество .
• Буске, Оливье; Елисеев, Андре (1 марта 2002 г.). «Стабильность и обобщение» . Журнал исследований машинного обучения . 2 : 499–526. дои : 10.1162/153244302760200704 . S2CID   1157797 . Проверено 10 декабря 2022 г.
• Вапник, В.; Червоненкис, А. (2004). «О равномерной сходимости относительных частот событий к их вероятностям». Теория вероятностей. Приложение . 16 (2): 264–280. дои : 10.1137/1116025 .