Теория Вапника – Червоненкиса. - 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 n\to \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 \{g:\|g-f\|<\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 \|f\|_{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})-Pf)}$

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

${\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}}$ (иногда называемый образец призрака) и заменяя этими копиями внутреннее ожидание ЛГС. После применения Неравенство Дженсена можно было ввести разные знаки (отсюда и название «симметризация») без изменения ожидания. Доказательство можно найти ниже из-за его поучительного характера.

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

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

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

Следовательно, по Неравенство Дженсена:

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

Принимая ожидание в отношении ${\displaystyle X}$ дает:

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

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

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

для любого ${\displaystyle (e_{1},e_{2},\ldots ,e_{n})\in \{-1,1\}^{n}}$. Следовательно:

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

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

${\displaystyle \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: сначала используется симметризация, чтобы передать эмпирический процесс в ${\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 O(n^{V({\mathcal {C}})-1})}$ подмножеств, а не экспоненциальное число. Интуитивно это означает, что из конечного VC-индекса следует, что ${\displaystyle {\mathcal {C}}}$ имеет очевидную упрощенную структуру.

Аналогичную оценку можно показать (с другой постоянной, той же скоростью) для так называемого Классы подграфов VC. Для функции ${\displaystyle f:{\mathcal {X}}\to \mathbf {R} }$ в подграф это подмножество ${\displaystyle {\mathcal {X}}\times \mathbf {R} }$ такой, что: ${\displaystyle \{(x,t):t<f(x)\}}$. Коллекция ${\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 \sum _{i=1}^{m}\alpha _{i}f_{i}}$ с ${\displaystyle \sum _{i=1}^{m}|\alpha _{i}|\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\varepsilon ^{-{\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}$.

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

Брать ${\displaystyle n=\dim({\mathcal {F}})+2}$ точки ${\displaystyle (x_{1},t_{1}),\ldots ,(x_{n},t_{n})}$. Векторы:

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

находятся в п − 1 мерное подпространство р^п. Брать а ≠ 0, вектор, ортогональный этому подпространству. Следовательно:

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

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

Существуют обобщения понятия класса подграфа 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}},n)}$ будет полиномиальным от п, для достаточно больших п при условии, что сбор ${\displaystyle {\mathcal {C}}}$ имеет конечный VC-индекс.

Позволять ${\displaystyle D_{n}=\{(X_{1},Y_{1}),\ldots ,(X_{n},Y_{m})\}}$ - наблюдаемый набор данных. Предположим, что данные генерируются неизвестным распределением вероятностей ${\displaystyle P_{XY}}$. Определять ${\displaystyle R(f)=P(f(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{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}}}$

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

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

${\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.