Теория Вапника – Червоненкиса

Раздел статистической теории вычислительного обучения

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

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

• 1 Введение
• 2 Обзор VC теория в эмпирических процессах
  • 2.1 Предпосылки к эмпирическим процессам
  • 2.2 Симметризация
  • 2.3 Связь VC
• 3 Неравенство VC
  • 3.1 Теорема (Неравенство VC)
• 4 Ссылки

Теория VC охватывает как минимум четыре части (как объясняется в разделе «Природа статистической теории обучения»):

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

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

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

Предпосылки к эмпирическим процессам

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

$Q\; f\; =\; \int \; fd\; Q\; \{\backslash \; displaystyle\; Qf\; =\; \backslash \; int\; fdQ\}$

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

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

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

$п\; N\; знак\; равно\; N\; -\; 1\; \sum \; я\; знак\; равно\; 1\; N\; \delta \; Икс\; я,\; \{\backslash \; Displaystyle\; \backslash \; mathbb\; \{P\}\; \_\; \{п\}\; =\; п\; ^\; \{-\; 1\}\; \backslash \; сумма\; \_\; \{я\; =\; 1\}\; ^\; \{п\}\; \backslash \; delta\; \_\; \{X\_\; \{i\}\},\}$

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

$f\; \mapsto \; P\; nf\; =\; 1\; n\; (\; е\; (Икс\; 1)\; +...\; +\; е\; (Икс\; n))\; \{\backslash \; Displaystyle\; f\; \backslash \; mapsto\; \backslash \; mathbb\; \{P\}\; \_\; \{n\}\; f\; =\; \{\backslash \; frac\; \{1\}\; \{n\}\}\; (f\; (X\_\; \{1\})\; +...\; +\; f\; (X\_\; \{n\}))\}$

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

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

  $\Vert \; П\; N\; -\; п\; \Vert \; F\; \to \; N\; 0,\; \{\backslash \; displaystyle\; \backslash \; |\; \backslash \; mathbb\; \{P\}\; \_\; \{n\}\; -P\; \backslash \; |\; \_\; \{\backslash \; mathcal\; \{F\}\}\; \{\backslash \; underset\; \{n\}\; \{\backslash \; to\}\}\; 0,\}$

То есть при $n\; \to \; \infty \; \{\backslash \; displaystyle\; n\; \backslash \; to\; \backslash \; infty\}$,

$|\; 1\; n\; (f\; (X\; 1)\; +...\; +\; F\; (X\; n))\; -\; \int \; f\; d\; P\; |\; \to \; 0\; \{\backslash \; displaystyle\; \backslash \; left\; |\; \{\backslash \; frac\; \{1\}\; \{n\}\}\; (f\; (X\_\; \{1\})\; +...\; +\; f\; (X\_\; \{n\}))\; -\; \backslash \; int\; fdP\; \backslash \; right\; |\; \backslash \; to\; 0\}$

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

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

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

В первом случае $F\; \{\backslash \; displaystyle\; \{\backslash \; mathcal\; \{F\}\}\}$называется классом Гливенко-Кантелли, а в последнем случае (в предположении ) класс $F\; \{\backslash \; displaystyle\; \{\backslash \; mathcal\; \{F\}\}\}$называется Донскером или П-Донскером. Класс Донскера является вероятностным по Гливенко-Кантелли в результате применения теоремы Слуцкого.

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

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

$N\; (\epsilon ,\; F,\; \Vert \; \cdot \; \Vert )\; \{\backslash \; displaystyle\; N\; (\backslash \; varepsilon,\; \{\backslash \; mathcal\; \{F\}\},\; \backslash \; |\; \backslash \; cdot\; \backslash \; |)\}$

- минимальное количество шаров необходимо для покрытия множества $F\; \{\backslash \; displaystyle\; \{\backslash \; mathcal\; \{F\}\}\}$(здесь, очевидно, предполагается, что там является базовой нормой для $F\; \{\backslash \; displaystyle\; \{\backslash \; mathcal\; \{F\}\}\}$). Энтропия - это логарифм числа покрытия.

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

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

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

, тогда $F\; \{\backslash \; displaystyle\; \{\backslash \; mathcal\; \{F\}\}\}$является P-Донскером для любой вероятностной меры P такой, что . В последнем интеграле обозначение означает

$\Vert \; е\; \Vert \; Q,\; 2\; =\; (\int \; |\; f\; |\; 2\; d\; Q)\; 1\; 2\; \{\backslash \; displaystyle\; \backslash \; |\; f\; \backslash \; |\; \_\; \{Q,\; 2\}\; =\; \backslash \; left\; (\backslash \; int\; |\; f\; |\; ^\; \{2\}\; dQ\; \backslash \; right)\; ^\; \{\backslash \; frac\; \{1\}\; \{2\}\}\}$.

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

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

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

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

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

$f\; \mapsto \; P\; n\; 0\; f\; =\; 1\; n\; \sum \; i\; =\; 1\; n\; \epsilon \; if\; (X\; i)\; \{\backslash \; displaystyle\; f\; \backslash \; mapsto\; \backslash \; mathbb\; \{P\}\; \_\; \{n\}\; ^\; \{0\}\; f\; =\; \{\backslash \; dfrac\; \{1\}\; \{n\}\}\; \backslash \; sum\; \_\; \{i\; =\; 1\}\; ^\; \{n\}\; \backslash \; varepsilon\; \_\; \{i\}\; f\; (X\_\; \{i\})\}$

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

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

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

Доказательство леммы о симметризации опирается на введение независимых копий исходных переменных $X\; i\; \{\backslash \; displaystyle\; X\_\; \{i\}\}$(иногда называемый призрачным образцом) и заменяя внутреннее ожидание LHS этими копиями. После применения неравенства Дженсена можно было вводить разные знаки (отсюда и название «симметризация») без изменения математического ожидания. Доказательство можно найти ниже из-за его поучительного характера.

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

Представьте «призрачный образец» $Y\; 1,\dots ,\; Y\; n\; \{\backslash \; displaystyle\; Y\_\; \{1\},\; \backslash \; ldots,\; Y\_\; \{n\}\}$, чтобы быть независимым копии $X\; 1,\dots ,\; X\; n\; \{\backslash \; displaystyle\; X\_\; \{1\},\; \backslash \; ldots,\; X\_\; \{n\}\}$. Для фиксированных значений $X\; 1,\dots ,\; X\; n\; \{\backslash \; displaystyle\; X\_\; \{1\},\; \backslash \; ldots,\; X\_\; \{n\}\}$один имеет:

$\Vert \; P\; n\; -\; P\; \Vert \; F\; =\; sup\; f\; \in \; F\; 1\; n\; |\; \sum \; i\; =\; 1\; n\; f\; (X\; i)\; -\; E\; f\; (Y\; i)\; |\; \le \; E\; Y\; sup\; f\; \in \; F\; 1\; n\; |\; \sum \; я\; знак\; равно\; 1\; n\; f\; (X\; i)\; -\; f\; (Y\; i)\; |\; \{\backslash \; displaystyle\; \backslash \; |\; \backslash \; mathbb\; \{P\}\; \_\; \{n\}\; -P\; \backslash \; |\; \_\; \{\backslash \; mathcal\; \{F\}\}\; =\; \backslash \; sup\; \_\; \{f\; \backslash \; in\; \{\backslash \; mathcal\; \{F\}\}\}\; \{\backslash \; dfrac\; \{1\}\; \{n\; \}\}\; \backslash \; left\; |\; \backslash \; sum\; \_\; \{i\; =\; 1\}\; ^\; \{n\}\; f\; (X\_\; \{i\})\; -\; \backslash \; mathbb\; \{E\}\; f\; (Y\_\; \{i\})\; \backslash \; right\; |\; \backslash \; leq\; \backslash \; mathbb\; \{E\}\; \_\; \{Y\; \}\; \backslash \; sup\; \_\; \{f\; \backslash \; in\; \{\backslash \; mathcal\; \{F\}\}\}\; \{\backslash \; dfrac\; \{1\}\; \{n\}\}\; \backslash \; left\; |\; \backslash \; sum\; \_\; \{i\; =\; 1\}\; ^\; \{n\}\; f\; (X\_\; \{i\})\; -\; f\; (Y\_\; \{i\})\; \backslash \; right\; |\}$

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

$\Phi \; (\Vert \; P\; n\; -\; P\; \Vert \; F)\; \le \; EY\; \Phi \; (\Vert \; 1\; n\; \sum \; i\; =\; 1\; nf\; (X\; i)\; -\; е\; (Y\; я)\; \Vert \; F)\; \{\backslash \; Displaystyle\; \backslash \; Phi\; (\backslash \; |\; \backslash \; mathbb\; \{P\}\; \_\; \{n\}\; -P\; \backslash \; |\; \_\; \{\backslash \; mathcal\; \{F\}\})\; \backslash \; leq\; \backslash \; mathbb\; \{E\}\; \_\; \{Y\}\; \backslash \; Phi\; \backslash \; left\; (\backslash \; left\; \backslash \; |\; \{\backslash \; dfrac\; \{1\}\; \{n\}\}\; \backslash \; sum\; \_\; \{i\; =\; 1\}\; ^\; \{n\}\; f\; (X\_\; \{i\})\; -\; f\; (Y\_\; \{i\})\; \backslash \; right\; \backslash \; |\; \_\; \{\backslash \; mathcal\; \{F\}\}\; \backslash \; right)\}$

Принятие математического ожидания относительно $X\; \{\backslash \; displaystyle\; X\}$дает:

$E\; \Phi \; (\Vert \; P\; n\; -\; P\; \Vert \; F)\; \le \; EXEY\; \Phi \; (\Vert \; 1\; N\; \sum \; я\; знак\; равно\; 1\; NF\; (X\; я)\; -\; е\; (Y\; я)\; \Vert \; F)\; \{\backslash \; Displaystyle\; \backslash \; mathbb\; \{E\}\; \backslash \; Phi\; (\backslash \; |\; \backslash \; mathbb\; \{P\}\; \_\; \{п\}\; -P\; \backslash \; |\; \_\; \{\backslash \; mathcal\; \{F\}\})\; \backslash \; leq\; \backslash \; mathbb\; \{E\}\; \_\; \{X\}\; \backslash \; mathbb\; \{E\}\; \_\; \{Y\}\; \backslash \; Phi\; \backslash \; left\; (\backslash \; left\; \backslash \; |\; \{\backslash \; dfrac\; \{1\}\; \{n\}\}\; \backslash \; sum\; \_\; \{i\; =\; 1\}\; ^\; \{n\}\; f\; (X\_\; \{i\})\; -\; f\; (Y\_\; \{i\})\; \backslash \; right\; \backslash \; |\; \_\; \{\backslash \; mathcal\; \{F\}\}\; \backslash \; right)\}$

Обратите внимание, что добавление знак минус перед членом $f\; (X\; i)\; -\; f\; (Y\; i)\; \{\backslash \; displaystyle\; f\; (X\_\; \{i\})\; -\; f\; (Y\_\; \{i\})\}$не меняет правую часть, потому что это симметричная функция от $X\; \{\; \backslash \; displaystyle\; X\}$и $Y\; \{\backslash \; displaystyle\; Y\}$. Таким образом, RHS остается неизменным при «возмущении знака»:

$E\; \Phi \; (\Vert \; 1\; n\; \sum \; i\; =\; 1\; nei\; (f\; (X\; i)\; -\; f\; (Y\; i))\; \Vert \; F)\; \{\backslash \; displaystyle\; \backslash \; mathbb\; \{E\; \}\; \backslash \; Phi\; \backslash \; left\; (\backslash \; left\; \backslash \; |\; \{\backslash \; dfrac\; \{1\}\; \{n\}\}\; \backslash \; sum\; \_\; \{i\; =\; 1\}\; ^\; \{n\}\; e\_\; \{i\}\; \backslash \; left\; (f\; (X\_\; \{i\})\; -\; f\; (Y\_\; \{i\})\; \backslash \; right)\; \backslash \; right\; \backslash \; |\; \_\; \{\backslash \; mathcal\; \{F\}\}\; \backslash \; right)\}$

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

$E\; \Phi \; (\Vert \; P\; n\; -\; P\; \Vert \; F)\; \le \; E\; \epsilon \; E\; \Phi \; (\Vert \; 1\; n\; \sum \; i\; =\; 1\; n\; \epsilon \; i\; (f\; (X\; i)\; -\; f\; (Y\; i))\; \Vert \; F)\; \{\backslash \; displaystyle\; \backslash \; mathbb\; \{E\}\; \backslash \; Phi\; (\backslash \; |\; \backslash \; mathbb\; \{P\}\; \_\; \{n\}\; -P\; \backslash \; |\; \_\; \{\backslash \; mathcal\; \{F\}\})\; \backslash \; leq\; \backslash \; mathbb\; \{E\}\; \_\; \{\backslash \; varepsilon\}\; \backslash \; mathbb\; \{E\}\; \backslash \; Phi\; \backslash \; left\; (\backslash \; left\; \backslash \; |\; \{\backslash \; dfrac\; \{1\}\; \{n\}\}\; \backslash \; sum\; \_\; \{i\; =\; 1\}\; ^\; \{n\}\; \backslash \; varepsilon\; \_\; \{i\}\; \backslash \; left\; (f\; (X\_\; \{i\})\; -\; f\; (\; Y\_\; \{i\})\; \backslash \; right)\; \backslash \; right\; \backslash \; |\; \_\; \{\backslash \; mathcal\; \{F\}\}\; \backslash \; right)\}$

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

$E\; \Phi \; (\Vert \; P\; n\; -\; P\; \Vert \; F)\; \le \; 1\; 2\; E\; \epsilon \; E\; \Phi \; (2\; \Vert \; 1\; n\; \sum \; i\; =\; 1\; n\; \epsilon ,\; если\; (X\; i)\; \Vert \; F)\; +\; 1\; 2\; E\; \epsilon \; E\; \Phi \; (2\; \Vert \; 1\; N\; \sum \; я\; знак\; равно\; 1\; N\; \epsilon ,\; если\; (Y\; я)\; \Vert \; F)\; \{\backslash \; Displaystyle\; \backslash \; mathbb\; \{E\}\; \backslash \; Phi\; (\backslash \; |\; \backslash \; mathbb\; \{P\}\; \_\; \{n\}\; -P\; \backslash \; |\; \_\; \{\backslash \; mathcal\; \{F\}\})\; \backslash \; leq\; \{\backslash \; dfrac\; \{1\}\; \{2\}\}\; \backslash \; mathbb\; \{E\}\; \_\; \{\backslash \; varepsilon\}\; \backslash \; mathbb\; \{E\}\; \backslash \; Phi\; \backslash \; left\; (2\; \backslash \; left\; \backslash \; |\; \{\backslash \; dfrac\; \{1\}\; \{n\; \}\}\; \backslash \; sum\; \_\; \{i\; =\; 1\}\; ^\; \{n\}\; \backslash \; varepsilon\; \_\; \{i\}\; f\; (X\_\; \{i\})\; \backslash \; right\; \backslash \; |\; \_\; \{\backslash \; mathcal\; \{F\}\}\; \backslash \; right)\; +\; \{\backslash \; dfrac\; \{1\}\; \{\; 2\}\}\; \backslash \; mathbb\; \{E\}\; \_\; \{\backslash \; varepsilon\}\; \backslash \; mathbb\; \{E\}\; \backslash \; Phi\; \backslash \; left\; (2\; \backslash \; left\; \backslash \; |\; \{\backslash \; dfrac\; \{1\}\; \{n\}\}\; \backslash \; sum\; \_\; \{i\; =\; 1\}\; ^\; \{n\}\; \backslash \; varepsilon\; \_\; \{i\}\; f\; (Y\_\; \{i\})\; \backslash \; right\; \backslash \; |\; \_\; \{\backslash \; mathcal\; \{F\}\}\; \backslash \; right)\}$

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

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

VC Connection

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

Рассмотрим коллекцию $C\; \{\backslash \; displaystyle\; \{\backslash \; mathcal\; \{C\}\}\}$подмножеств выборочного пространства $X\; \{\backslash \; displaystyle\; \{\backslash \; mathcal\; \{X\}\}\; \}$. $C\; \{\backslash \; displaystyle\; \{\backslash \; mathcal\; \{C\}\}\}$, как говорят, выбирает определенное подмножество $W\; \{\backslash \; displaystyle\; W\}$из конечного множества $S\; =\; \{x\; 1,\dots ,\; xn\}\; \subset \; X\; \{\backslash \; displaystyle\; S\; =\; \backslash \; \{x\_\; \{1\},\; \backslash \; ldots,\; x\_\; \{n\}\; \backslash \}\; \backslash \; subset\; \{\backslash \; mathcal\; \{X\}\}\}$если $W\; =\; S\; \cap \; C\; \{\backslash \; displaystyle\; W\; =\; S\; \backslash \; cap\; C\}$для некоторых $C\; \in \; C\; \{\backslash \; displaystyle\; C\; \backslash \; in\; \{\backslash \; mathcal\; \{C\}\}\}$. $C\; \{\backslash \; displaystyle\; \{\backslash \; mathcal\; \{C\}\}\}$, как говорят, разрушает S, если выбирает каждое из двух его подмножеств. VC-индекс (аналогично размерности VC + 1 для правильно выбранного набора классификаторов) $V\; (C)\; \{\backslash \; displaystyle\; V\; (\{\backslash \; mathcal\; \{C\}\})\}$из $C\; \{\backslash \; displaystyle\; \{\backslash \; mathcal\; \{C\}\}\}$- наименьшее n, для которого ни один набор размера n не разбивается на $C\; \{\backslash \; displaystyle\; \{\backslash \; mathcal\; \{C\}\; \}\}$.

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

$max\; x\; 1,\dots ,\; xn\; \Delta \; n\; (C,\; x\; 1,\dots ,\; xn)\; \le \; \sum \; j\; =\; 0\; V\; (C)\; -\; 1\; (nj)\; \le \; (ne\; V\; (C)\; -\; 1)\; V\; (C)\; -\; 1\; \{\backslash \; displaystyle\; \backslash \; max\; \_\; \{x\_\; \{1\},\; \backslash \; ldots,\; x\_\; \{n\}\}\; \backslash \; Delta\; \_\; \{n\}\; (\{\backslash \; mathcal\; \{C\}\},\; x\_\; \{1\},\; \backslash \; ldots,\; x\_\; \{n\})\; \backslash \; leq\; \backslash \; sum\; \_\; \{j\; =\; 0\}\; ^\; \{V\; (\{\backslash \; mathcal\; \{C\}\})\; -\; 1\}\; \{n\; \backslash \; choose\; j\}\; \backslash \; leq\; \backslash \; left\; (\{\backslash \; frac\; \{ne\}\; \{V\; (\{\backslash \; mathcal\; \{C\; \}\})\; -\; 1\}\}\; \backslash \; right)\; ^\; \{V\; (\{\backslash \; mathcal\; \{C\}\})\; -\; 1\}\}$

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

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

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

$N\; (\epsilon ,\; IC,\; L\; r\; (Q))\; \le \; KV\; (C)\; (4\; e)\; V\; (\; С)\; \epsilon \; -\; р\; (В\; (С)\; -\; 1)\; \{\backslash \; Displaystyle\; N\; (\backslash \; varepsilon,\; \{\backslash \; mathcal\; \{I\}\}\; \_\; \{\backslash \; mathcal\; \{C\}\},\; L\_\; \{r\}\; (Q))\; \backslash \; leq\; KV\; (\{\; \backslash \; mathcal\; \{C\}\})\; (4e)\; ^\; \{V\; (\{\backslash \; mathcal\; \{C\}\})\}\; \backslash \; varepsilon\; ^\; \{-\; r\; (V\; (\{\backslash \; mathcal\; \{C\}\})\; -\; 1)\}\}$

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

$N\; (\epsilon \; \Vert \; F\; \Vert \; Q,\; 2,\; F,\; L\; 2\; (Q))\; \le \; C\; \epsilon \; -\; V\; \{\backslash \; displaystyle\; N\; \backslash \; left\; (\backslash \; varepsilon\; \backslash \; |\; F\; \backslash \; |\; \_\; \{Q,\; 2\},\; \{\; \backslash \; mathcal\; \{F\}\},\; L\_\; \{2\}\; (Q)\; \backslash \; right)\; \backslash \; leq\; C\; \backslash \; varepsilon\; ^\; \{-\; V\}\}$

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

$журнал\; \; N\; (\epsilon \; \Vert \; F\; \Vert \; Q,\; 2,\; sconv\; \; F,\; L\; 2\; (Q))\; \le \; K\; \epsilon \; -\; 2\; VV\; +\; 2\; \{\backslash \; displaystyle\; \backslash \; log\; N\; \backslash \; left\; (\backslash \; varepsilon\; \backslash \; |\; F\; \backslash \; |\; \_\; \{Q,\; 2\},\; \backslash \; operatorname\; \{sconv\}\; \{\backslash \; mathcal\; \{F\}\},\; L\_\; \{2\}\; (Q)\; \backslash \; right)\; \backslash \; leq\; K\; \backslash \; varepsilon\; ^\; \{-\; \{\backslash \; frac\; \{2V\}\; \{V\; +2\}\}\}\}$

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

$2\; VV\; +\; 2>2,\; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{2V\}\; \{V\; +\; 2\}\}>2,\}$

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

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

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

Возьмите $n\; =\; dim\; \; (F)\; +\; 2\; \{\backslash \; displaystyle\; n\; =\; \backslash \; dim\; (\{\backslash \; mathcal\; \{F\}\})\; +\; 2\}$очков. $(x\; 1,\; t\; 1),\dots ,\; (xn,\; tn)\; \{\backslash \; displaystyle\; (x\_\; \{1\},\; t\_\; \{1\}),\; \backslash \; ldots,\; (x\_\; \{n\},\; t\_\; \{n\})\}$. Векторы:

$(f\; (x\; 1),\dots ,\; f\; (xn))\; -\; (t\; 1,\dots ,\; tn)\; \{\backslash \; displaystyle\; (f\; (x\_\; \{1\}),\; \backslash \; ldots,\; f\; (x\_\; \{n\})))\; -\; (t\_\; \{1\},\; \backslash \; ldots,\; t\_\; \{n\})\}$

находятся в - 1-мерном подпространстве R . Возьмем 0 вектор, ортогональный этому подпространству. Следовательно:

Рассмотрим набор $S\; =\; \{(\; xi,\; ti):\; ai>0\}\; \{\backslash \; displaystyle\; S\; =\; \backslash \; \{(x\_\; \{i\},\; t\_\; \{i\}):\; a\_\; \{i\}>0\; \backslash \}\}$. Этот набор нельзя выбрать, так как если есть какие-то $f\; \{\backslash \; displaystyle\; f\}$такой, что $S\; =\; \{(xi,\; ti):\; f\; (xi)>ti\}\; \{\backslash \; displaystyle\; S\; =\; \backslash \; \{(x\_\; \{i\},\; t\_\; \{\; i\}):\; f\; (x\_\; \{i\})>t\_\; \{i\}\; \backslash \}\}$, что означает, что LHS строго положительный, а RHS отрицательный.

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

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

$S\; (F,\; n)\; =\; max\; x\; 1,\dots ,\; x\; n\; |\; \{(f\; (x\; 1),\dots ,\; f\; (x\; n)),\; f\; \in \; F\}\; |\; \{\backslash \; displaystyle\; S\; (\{\backslash \; mathcal\; \{F\}\},\; n)\; =\; \backslash \; max\; \_\; \{x\_\; \{1\},\; \backslash \; ldots,\; x\_\; \{n\}\}\; |\; \backslash \; \{(f\; (x\_\; \{1\}),\; \backslash \; ldots,\; f\; (\; x\_\; \{n\})),\; f\; \backslash \; in\; \{\backslash \; mathcal\; \{F\}\}\; \backslash \}\; |\}$

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

$max\; x\; 1,\dots ,\; xn\; \Delta \; n\; (C,\; x\; 1,\dots ,\; xn)\; \{\backslash \; displaystyle\; \backslash \; max\; \_\; \{x\_\; \{1\},\; \backslash \; ldots,\; x\_\; \{n\}\}\; \backslash \; Delta\; \_\; \{n\}\; (\{\backslash \; mathcal\; \{C\}\},\; x\_\; \{1\},\; \backslash \; ldots,\; x\_\; \{n\})\}$.

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

Пусть $D\; n\; =\; \{(X\; 1,\; Y\; 1),\dots ,\; (X\; n,\; Y\; m)\}\; \{\backslash \; displaystyle\; D\_\; \{n\}\; =\; \backslash \; \{(X\_\; \{1\},\; Y\_\; \{\; 1\}),\; \backslash \; ldots,\; (X\_\; \{n\},\; Y\_\; \{m\})\; \backslash \}\}$- наблюдаемый набор данных. Предположим, что данные созданы с помощью неизвестного распределения вероятностей $P\; X\; Y\; \{\backslash \; displaystyle\; P\_\; \{XY\}\}$. Определите $R\; (f)\; =\; P\; (f\; (X)\; \ne \; Y)\; \{\backslash \; displaystyle\; R\; (f)\; =\; P\; (f\; (X)\; \backslash \; neq\; Y)\}$как ожидаемое 0/1 проигрыш. Конечно, поскольку $PXY\; \{\backslash \; displaystyle\; P\_\; \{XY\}\}$вообще неизвестен, никто не имеет доступа к $R\; (f)\; \{\backslash \; displaystyle\; R\; (f)\}$. Однако эмпирический риск, определяемый по формуле:

$R\; ^\; n\; (f)\; =\; 1\; n\; \sum \; i\; =\; 1\; n\; I\; (f\; (X\; i)\; \ne \; Y\; i)\; \{\backslash \; displaystyle\; \{\backslash \; hat\; \{R\}\}\; \_\; \{n\}\; (f)\; =\; \{\backslash \; dfrac\; \{1\}\; \{n\}\}\; \backslash \; sum\; \_\; \{i\; =\; 1\}\; ^\; \{n\}\; \backslash \; mathbb\; \{I\}\; (f\; (X\_\; \{i\})\; \backslash \; neq\; Y\_\; \{i\})\}$

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

Теорема (VC Inequality)

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

$P\; (sup\; f\; \in \; F\; |\; R\; ^\; n\; (f)\; -\; R\; (f)\; |>\epsilon )\; \le \; 8\; S\; (F,\; n)\; e\; -\; n\; \epsilon \; 2/32\; E\; [sup\; f\; \in \; F\; |\; R\; ^\; n\; (f)\; -\; R\; (f)\; |\; ]\; \le \; 2\; журнал\; \; S\; (F,\; n)\; +\; журнал\; \; 2\; N\; \{\backslash \; Displaystyle\; \{\backslash \; begin\; \{align\}\; P\; \backslash \; left\; (\backslash \; sup\; \_\; \{f\; \backslash \; in\; \{\backslash \; mathcal\; \{F\}\}\}\; \backslash \; left\; |\; \{\backslash \; hat\; \{R\}\}\; \_\; \{n\}\; (f)\; -R\; (f)\; \backslash \; right\; |>\backslash \; varepsilon\; \backslash \; right)\; \backslash \; leq\; 8S\; (\{\backslash \; mathcal\; \{F\}\},\; n)\; e\; ^\; \{-\; n\; \backslash \; varepsilon\; ^\; \{2\; \}\; /\; 32\}\; \backslash \backslash \backslash \; mathbb\; \{E\}\; \backslash \; left\; [\backslash \; sup\; \_\; \{f\; \backslash \; in\; \{\backslash \; mathcal\; \{F\}\}\}\; \backslash \; left\; |\; \{\backslash \; hat\; \{R\}\}\; \_\; \{n\}\; (f)\; -R\; (f)\; \backslash \; right\; |\; \backslash \; right]\; \backslash \; leq\; 2\; \{\backslash \; sqrt\; \{\backslash \; dfrac\; \{\backslash \; log\; S\; (\{\backslash \; mathcal\; \{F\}\},\; n)\; +\; \backslash \; log\; 2\}\; \{n\}\}\}\; \backslash \; end\; \{align\}\}\}$

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

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

$|\; R\; ^\; n\; -\; R\; |\; F\; \{\backslash \; displaystyle\; \backslash \; left\; |\; \{\backslash \; hat\; \{R\}\}\; \_\; \{n\}\; -R\; \backslash \; right\; |\; \_\; \{\backslash \; mathcal\; \{F\}\}\}$

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

• ^Вапник, Владимир N (2000). Природа статистической теории обучения. Информатика и статистика. Спрингер-Верлаг. ISBN 978-0-387-98780-4.
• Вапник, Владимир N (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). «О равномерной сходимости относительных частот событий к их вероятностям». Теория вероятн. Appl. 16 (2): 264–280. doi :10.1137/1116025.