3 Сложность Радемахера и размерность VC

Набор предположений, обычно используемых в машинном обучении, бесконечен. Однако оценки сложности выборки из предыдущей главы неинформативны при работе с бесконечными наборами гипотез. Можно спросить, когда гипотетический набор$\mathcal H$Можно ли эффективно учиться на конечных выборках, когда бесконечность. Наш анализ семейства выровненных по оси прямоугольников (пример 2.4) показывает, что это действительно возможно, по крайней мере, в некоторых случаях, потому что мы показываем, что бесконечные классы понятий сжимаемы. Наша цель в этой главе — обобщить этот результат и вывести общие гарантии обучения для бесконечных наборов гипотез.
Общая идея сделать это состоит в том, чтобы свести бесконечный случай к анализу конечного набора предположений, а затем выполнить шаги из предыдущей главы. Существуют разные методы такого упрощения, каждый из которых опирается на свой набор предполагаемых понятий сложности. Первое понятие сложности, которое мы будем использовать, этоСложность Радемахера. Это поможет нам получить гарантии обучения, используя относительно простые доказательства, основанные на неравенствах МакДиармида, и получить высококачественные оценки, включая оценки, зависящие от данных, которые мы будем часто использовать в следующих главах. Однако для некоторых наборов гипотез оценка с доказанной сложностью Радемахера оказывается NP-трудной. Поэтому введем два других чисто композиционных понятия,функция ростаиизмерение ВК. Сначала мы связываем сложность Радемахера с функцией роста, а затем ограничиваем функцию роста в соответствии с размерностью VC. Параметр VC обычно легче связать или оценить. Мы рассмотрим серию примеров, показывающих, как ее вычислить или связать, а затем свяжем функцию роста с измерением VC. Это приведет к границам обобщения, основанным на размерности VC. Наконец, мы даем нижние границы на основе измерения VC при двух разных настройках:достижимые настройки, где по крайней мере одна гипотеза в рассматриваемом наборе гипотез достигает нулевой ожидаемой ошибки, инедостижимые настройки, где ни одна гипотеза в наборе гипотез не достигает нулевой ожидаемой ошибки.

3.1 Сложность Радемахера

мы будем продолжать использовать$\mathcal H$для представления гипотезы, установленной в предыдущей главе. Многие результаты в этом разделе носят общий характер и применимы к произвольным функциям потерь.$L:\mathcal Y × \mathcal Y\to \mathbb R$. ниже,$\mathcal G$обычно интерпретируется как$Z=X×Y$прибыть$\mathbb R$из$\mathcal H$Сопоставьте соответствующее семейство функций потерь:

Однако определение находится в семействе функций$\mathcal G$из любого входного пространства$\mathcal Z$сопоставить с$\mathbb R$дается в общем случае.

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

Определение 3.1: (эмпирическая сложность Радемахера)

Предполагать$\mathcal G$это из$\mathcal Z$сопоставить с$[а, б]$семейство функций,$\mathcal S=(z_1,...,z_m)$размер$\mathcal m$и элемент$\mathcal Z$фиксированный образец в формате . Потом,$\mathcal G$относительно образца$S$Эмпирическая сложность Радемахера определяется как:

В формуле$\epsilon=(\sigma_i,...,\sigma_m)^{T}$,в$\sigma$это взять$\{−1, +1\}$. Случайные переменные$\sigma_i$называется переменной Радемахера.

Предполагать$g_S$Представляет собой вектор значений, которые функция g принимает на выборке S:$g_S=(g(z_1),…,g(z_m))^T$. Тогда эмпирическая сложность Радемахера может быть переписана как

Внутренний продукт$\sigma·g_S$Измерение$g_S$со случайным вектором шума$\sigma$корреляция. супремум$\sup_{g\in\mathcal G\frac{\sigma g_S}{m}}$класс функции меры$\mathcal G$в образце$\mathcal S$на с$\sigma$индикаторы релевантности. Таким образом, эмпирическая сложность Радемахера измеряет в среднем класс функций$\mathcal G$и$\mathcal S$Корреляция случайного шума сверху. Это описывает семью$\mathcal G$богатство: более богатые или более сложные семьи$\mathcal G$можно сгенерировать больше векторов$g_S$, что в среднем лучше коррелирует со случайным шумом.

Определение 3.2 (сложность Радемахера)

Предполагать$\mathcal D$Представляет распределение, из которого была взята выборка. для любого целого числа$m\ge 1$,$\mathcal G$Сложность Радемахера основана на$\mathcal D$Размер чертежа$m$Ожидаемое значение эмпирической сложности Радемахера для всех выборок:

Теперь мы готовы дать нашу первую обобщающую оценку, основанную на сложности Радемахера.

Теорема 3.3

Предполагать$\mathcal G$От$\mathcal Z$сопоставить с$[0,1]$семейство функций. Тогда для любого$\delta>0$, с вероятностью не менее$1−\дельта$по размеру$m$образцы iid$\mathcal S$, следующее относится ко всем$g\in\mathcal G$ :

Доказательство: для любого образца$S = (z_1, ..., z_m)$и любой$g\in \mathcal G$,мы используем$\hat{\mathbb E}_S[g]$Представляет эмпирическое среднее значение мульчи:$\hat{\mathbb E}_S[g]=\frac{1}{m}\sum^m_{i=1}g(z_i)$. Доказательство заключается в применении неравенства МакДиармида к произвольным выборкам.$S$Функция$\Phi$, где функция определяется как:

Предполагать$S$и$S'$две выборки, которые только близки друг к другу, пусть$S$середина$z_m$и$S'$середина$z'_m$. Тогда, поскольку разность супремума не превосходит супремума разности, имеем

Так же мы можем получить$\Phi(S)−\Phi(S')\le\frac{1}{m}$,следовательно$|\Phi(S)−\Phi(S')|\le\frac{1}{m}$. Тогда согласно неравенству МакДиармида для любого$\delta>0$, с вероятностью не менее$1-\ гидроразрыва {\ дельта} {2}$, имеет место следующая формула:

Затем мы ограничиваем ожидаемое значение с правой стороны до:

$\qquad\qquad\underset{S}{\mathbb E}[\Phi (S)]=\underset{S}{\mathbb E}[\underset{g\in \mathcal G}{\sup}(\mathbb E[g]-\hat{\mathbb E}_S(g))]$

Уравнение (3.8) использует тот факт, что$S'$Точки в отбираются iid, поэтому$\mathbb E[g]=\mathbb E_{S'}[\hat{\mathbb E}_{S'}(g)]$, как показано в (2.3). Неравенство 3.9 выполняется в силу субаддитивности супремум-функции.

В уравнении (3.11) введем переменную Радемахера$\sigma_i$, которая является равномерно распределенной независимой случайной величиной, которая принимает значение в {−1, 1}, как показано в определении 3.2. Это не меняет ожидание, фигурирующее в (3.10): когда$\sigma_i=1$, соответствующая сумма остается той же, когда$\sigma_i=−1$, связанная сумма и знак переворота, что эквивалентно$S$и$S_0$обмен между$z_i$и$z_0$. Поскольку мы знаем все возможные$S$и$S_0$Сделайте ожидание, чтобы замена не повлияла на общее ожидание; мы просто меняем порядок суммирования внутри ожидания.

Уравнение (3.12) определяется субаддитивностью супремум-функции, т. е. неравенством$\sup (U+V)\le\sup(U)+\sup(V)$. Наконец, (3.13) следует из определения сложности Радемахера и переменных$\sigma_i$и$−\sigma_i$распределяются таким же образом.

в уравнении (3.13)$\mathcal R_m(\mathcal G)$Сокращение , дает оценку в уравнении (3.3), используя$\delta$заменять$\delta/2$. чтобы вывести$\hat{\mathcal R}_S(\mathcal G)$Оценивая , заметим, что по определению 3.1 изменение$S$Максимум одно очко в изменении$1/m$из$\hat{\mathcal R}_S(\mathcal G)$. Затем, снова используя неравенство МакДиармида, вероятность равна$1− \дельта/2$Следующее:

Наконец, мы используем объединение, связанное для объединения неравенств 3.7 и 3.14 с вероятностью не менее$1-\delta$ :

Вышеупомянутое соответствует (3.4).

Следующие результаты предполагают, что множество$\mathcal H$Эмпирическая сложность Радемахера с бинарной потерей (ноль-единичная потеря) случай с$\mathcal H$Семейство связанных функций потерь$\mathcal G$Связаться.

Лемма 3.4

Предполагать$\mathcal H$для стоимости в$\{−1,+1\}$Семейство функций в , пусть G будет семейством нулевых функций потерь, связанных с H:$\mathcal G=\{(x,y)\to 1_{h(x)\neq y}:h\in\mathcal H\}$. за$\mathcal X\times\{-1,+1\}$образец любого элемента в$S=((x_1,y_1),...,(x_m,y_m))$,Предполагать$S_\mathcal X$указывает, что это$\mathcal X:S_\mathcal X=(x_1,...,x_m)$Проекция на: . Так,$\mathcal G$и$\mathcal H$Эмпирическая сложность Радемахера имеет следующую связь:

---

доказывать:за$\mathcal X \times \{-1,+1\}$образец любого элемента в$S=((x_1,y_1),...,(x_m,y_m))$, по определению,$\mathcal G$Эмпирическая сложность Радемахера может быть выражена как:

Здесь мы используем$1_{h(x_i)\neq y_i}=(1-y_ih(xi)/2)$факт, а для фиксированного$y_i\in\{-1,+1\}$,$\sigma_i$и$-y_i\sigma_i$Дело в том, что он распространяется таким же образом.

Заметим, что из этой леммы следует, что, взяв математическое ожидание, для любого$m\ge1$ , $\mathcal R_m(\mathcal G)=\frac{1}{2}\mathcal R_m(\mathcal H)$. Эти связи между эмпирической сложностью Радемахера и средней сложностью Радемахера можно использовать для$\mathcal H$Сложность Радемахера для получения границ обобщения для бинарной классификации.

---

Теорема 3.5 (границы сложности Радемахера — бинарная классификация)

Предполагать$\mathcal H$представляет собой семейство функций, диапазон значений$\{−1, +1\}$;Предполагать$\mathcal D$место для ввода$\mathcal X$раздача на. Тогда для любого δ>0 согласно$\mathcal D$сделать образец размером m$S$и его вероятность не менее$1-\delta$, то для любого$h\in \mathcal H$Оба установили:

Доказательство. Результат следует теореме 3.3 и лемме 3.4.

Эта теорема дает две границы обобщения для бинарной классификации, основанной на сложности Радемахера. Обратите внимание, что вторая оценка (3.18) связана с данными: эмпирическая сложность Радемахера$\hat{\mathcal R}_S(\mathcal H)$это конкретный образец$S$Функция. Следовательно, если мы можем вычислить$\hat{\mathcal R}_S(\mathcal H)$, эта оценка может быть особенно полезной. Но как вычислить эмпирическую сложность Радемахера? использовать снова$\sigma_i$и$−\sigma_i$Распределяя таким же образом, мы можем написать

Теперь, для$\sigma$фиксированное значение , расчет$\inf_{h\in\mathcal H}\frac{1}{m}\sum^m_{i=1}\sigma_ih(x_i)$эквивалентноЭмпирическая минимизация рискаПроблема в том, что это трудно вычислить для некоторых наборов гипотез. Поэтому в некоторых случаях вычисление$\hat{\mathcal R}_S(\mathcal H)$могут быть вычислительно сложными. В следующем разделе мы свяжем сложность Радемахера с комбинированными показателями, которые легче вычислить и которые имеют независимое применение при анализе обучения во многих условиях.

3.2 Функция роста

Здесь мы покажем, как сложность Радемахера основана нафункция ростаограничить.

Определение 3.6 (Функция роста)

набор гипотез$\Pi_\mathcal H:\mathbb H\to\mathbb H$функция роста$\mathcal H$Определяется следующим образом:

другими словами,$\prod_\mathcal H(m)$использовать$\mathcal H$гипотеза в$m$Максимальное количество различных способов классификации точек. Каждая из этих различных классификаций называется бинарной классификацией, поэтому функция роста подсчитывает количество дихотомий, реализуемых гипотезой. Это обеспечивает набор гипотез$\mathcal H$Еще одна мера богатства. Однако, в отличие от сложности Радемахера, эта метрика не зависит от распределения, она является чисто комбинаторной.

Чтобы связать сложность Радемахера с функцией роста, воспользуемся леммой Массарта.

Теорема 3.7 (лемма Массара)

Предполагать$\mathcal A\subseteq\mathbb R^m$является конечным множеством, и$r=\max_{x\in A}||X||_2$, то выполняется следующее уравнение:

В формуле$σ_is$— независимая равномерная случайная величина, значение которой равно${−1, 1}$и$x_1,...,x_m$вектор$X$количество.

---

доказывать:из-за случайных величин$\sigma_ix_i$независимы, и каждый$\sigma_ix_i$Возьмите значение в$[−|x_i |,|x_i |]$и$\sqrt{\sum^m_{i=1}x^2_i}\le r^2$середина. Таким образом, результат следует непосредственно из границы максимального ожидания, полученной в следствии D.11.

Используя этот результат, теперь мы можем ограничить сложность Радемахера функцией роста.

---

Вывод 3.8

Предполагать$\mathcal G$представляет собой семейство функций ценности$\{−1,+1\}$, Тогда имеет место следующее:

---

доказывать:для фиксированных образцов$S=(x_1,...,x_m)$,мы используем$\mathcal G_{|S}$набор векторов, представляющих значения функции$(г(х_1),...,г(х_м))$,в$g$существует$\mathcal G$середина. поскольку$g\in\mathcal G$принять значение$\{−1, +1\}$, норма этих векторов ограничена$\sqrt m$. Тогда мы можем применить лемму Массара следующим образом:

По определению,$|\mathcal G_{|S}|$Таким образом, ограниченный функцией роста,

Таков вывод доказательства.

Сочетание оценки обобщения (3.17) теоремы 3.5 со следствием 3.8 в терминах функции роста немедленно дает следующую оценку обобщения.

---

Вывод 3.9 (Границы обобщения функции роста)

Предполагать$\mathcal H$представляет собой семейство функций ценности$\{−1, +1\}$. Тогда для любого$\delta>0$, с вероятностью не менее$1−\дельта$, для любого$h\in\mathcal H$ ,

Рисунок 3.1Размер ВК интервала на сплошной линии. (a) Любые две точки могут быть нарушены. (b) Ни один из образцов трех точек не может быть раздавлен, потому что (+,-,+) не может быть помечено.

Границы функции роста также могут быть получены напрямую (без предварительного использования границ сложности Радемахера). Полученные границы выглядят следующим образом:

Оно отличается от (3.22) только константами.

Вычисление функции роста не всегда может быть удобным, поскольку по определению требует вычисления всех$m\ge1$из$\Pi_\mathcal H(m)$. Наборы гипотез представлены в следующем разделе.$\mathcal H$Другая мера сложности, основанная на одном скаляре, оказывается тесно связанной с поведением функции роста.

3.3 Размер ВК

Здесь мы вводим понятие размерности ВК (размерность Вапника-Червоненкиса). Измерение VC также является чисто комбинаторным понятием, но обычно его легче вычислить, чем функцию роста (или сложность Радемахера). Как мы увидим, параметр VC является ключевой величиной в обучении и напрямую связан с функцией роста.

Чтобы определить набор гипотез$\mathcal H$Измерение VC, мы сначала вводим понятие фрагментации. Напомним из предыдущего раздела, предположим, что коллекция$\mathcal H$,собирать$S$Дихотомия заключается в использовании$\mathcal H$Гипотетические маркеры в$S$Один из возможных способов указать. когда$\mathcal H$При реализации всех возможных дихотомий S, т.е.$\Pi_\mathcal H(m)=2^m$час,$m>1$набор точек$S$гипотетический набор$\mathcal H$вламываться.

Определение 3.10 (параметр VC)

набор гипотез$\mathcal H$Измерение VC доступно по$\mathcal H$Размер самого большого набора смэшей:

Заметим, что по определению, если$VC\dim(\mathcal H)=d$, то есть набор размеров, которые можно раздавить. Однако это не означает, что все размеры$d$или более мелкие коллекции разбиты, на самом деле это обычно не так.

Рисунок 3.2использовать$\mathbb R^2$Гиперплоскость в делает нереализуемую дихотомию четырех точек. (a) Все четыре точки лежат на выпуклой оболочке. (b) Три точки расположены на выпуклой оболочке, а остальные точки расположены внутри.

   Чтобы дополнительно проиллюстрировать эту концепцию, мы рассмотрим ряд примеров гипотетических множеств и определим размерность VC в каждом случае. Для расчета размерности VC мы обычно отображаем нижнюю границу ее значения, а затем верхнюю границу соответствия. чтобы дать$VCdim(\mathcal H)$Нижняя граница, просто докажите мощность$d$коллекция$S$возможно$\mathcal H$разрушать. Чтобы дать верхнюю оценку, нам нужно доказать, что нет мощности$d+1$коллекция$S$возможно$\mathcal H$Разрушение, которое обычно сложнее.

Пример 3.11 (интервал на сплошной линии)

Наш первый пример включает гипотетический класс интервалов на реальной прямой. Ясно, что размерность ВК не меньше двух, поскольку все четыре дихотомии$(+,+),(-,-),(+,-),(-,+)$Все могут быть достигнуты, как показано на рисунке 3.1 (а). Наоборот, согласно определению интервала, поскольку невозможно достичь$(+,-,+)$знак, поэтому набор из трех точек не может быть нарушен. следовательно,$VC\dim(interval\quad in\quad\mathbb R)=2$.

Пример 3.12 (Гиперплоскость)

учитывать$\mathbb R^2$Множество гиперплоскостей в , мы сначала наблюдаем$\mathbb R^2$Любые три точки, не лежащие на одной прямой, можно раздавить. Чтобы получить первые три дихотомии, мы выбираем гиперплоскость с двумя точками на одной стороне и третьей точкой на другой. Чтобы получить четвертую дихотомию, мы располагаем все три точки на одной стороне гиперплоскости. Остальные четыре дихотомии достигаются простым переключением знака. Далее мы покажем, что четыре точки нельзя разбить, рассмотрев два случая: (i) четыре точки лежат на выпуклой оболочке, определяемой четырьмя точками, и (ii) три из четырех точек лежат на выпуклой оболочке , остальные точки являются внутренними. В первом случае невозможно добиться положительных меток для одной диагональной пары и отрицательных меток для другой, как показано на рис. 3.2(а). Во втором случае невозможно получить метки с положительными точками на выпуклой оболочке и отрицательными точками внутри, как показано на рис. 3.2(b). следовательно,$VC\dim(hyperplanes\quad in\quad\mathbb R^2)=3$.

   В целом, в$\mathbb R^d$, мы начинаем с$\mathbb R^d$Начиная с набора d точек в$\Chi_0$установить в качестве источника и$\Chi_i$определяется как$i\in\{1,...,d\}$, то есть точка, координаты которой равны 1, а все остальные точки равны 0, что дает нижнюю границу. Предполагать$y_0,y_1,...y_d$да$\Chi_0,\Chi_1,...,\Chi_d$любой набор этикеток. Предполагать$W$во-первых$i$координаты$y_i$вектор. Тогда по уравнению$W\cdot\Chi+\frac{y_0}{2}=0$Декомпозиция классификатора, определяемая гиперплоскостью$\Chi_0,\Chi_1,...,\Chi_d$, так как для любого$i\in\{0,...,d\}$,

Чтобы получить верхнюю границу, просто покажите, что не существует множества$d+2$Достаточно того, что точка может быть уничтожена полупространством. Для доказательства воспользуемся следующей общей теоремой.

Теорема 3.13 (теорема Радона)

$d+2$любой набор точек$\mathcal X$можно разделить на два подмножества$\mathcal X_1$и$\mathcal X_2$, так что$\mathcal X_1$и$\mathcal X_2$Выпуклая оболочка пересекается.

доказывать:Предполагать$\mathcal X=\{X_1,...,X_{d+2}\}\subset\mathbb R^d$. Ниже приведены$\alpha_1,...,\alpha_{d+2}$середина$d+1$Система линейных уравнений:

Поскольку первое уравнение ведет к уравнению, каждая компонента соответствует одному уравнению. Количество неизвестных$d+2$больше, чем количество уравнений$d+1$, поэтому система допускает ненулевые решения$\beta_1,...,\beta_{d+2}$. так как$\sum^{d+2}_{i=1}\beta_i=0$,$\mathcal J_1=\{i\in[d+2]:\beta_i>0\}$и$\mathcal J_1=\{i\in[d+2]:\beta_i\le0\}$все непустые множества,$\mathcal X_1=\{X_i:i\in\mathcal J_1\}$и$\mathcal X_2=\{X_i:i\in\mathcal J_2\}$составляет часть X. Согласно последнему уравнению (3.26),$\sum_{i\in\mathcal J_1}\beta_i=-\sum_{i\in\mathcal J_2}\beta_i$. Предполагать$\beta=\sum_{i\in\mathcal J_1}$. Тогда из первой части (3.26) следует

использовать$\sum_{i\in\mathcal J_1}\frac{\beta_i}{\beta}=\sum_{i\in\mathcal J_2}\frac{-\beta}{\beta}=1$сказал, и$\frac{\beta_i}{\beta}\ge0$выражать$i\in\mathcal J_2$,$\frac{-\beta_i}{\beta}\ge0$выражать$i\in\mathcal J_2$. Согласно определению выпуклой оболочки (Б.6) это означает, что$\sum_{i\in\mathcal J_1}\frac{\beta_i}{\beta}X_i$оба принадлежат$\mathcal X1$Выпуклая оболочка , также принадлежит$\mathcal X_2$выпуклая оболочка.
Теперь позвольте$\mathcal X$это группа$d+2$точка. По теореме Радона его можно разделить на два множества$\mathcal X_1$и$\mathcal X_2$, так что их выпуклые оболочки пересекаются.

Теперь позвольте$\mathcal X$это группа$d+2$точка. По теореме Радона его можно разделить на два множества$\mathcal X_1$и$\mathcal X_2$, так что их выпуклые оболочки пересекаются. Обратите внимание, что когда два набора точек$\mathcal X_1$и$\mathcal X_2$Когда они разделены гиперплоскостью, их выпуклые оболочки также разделены этой гиперплоскостью. следовательно,$\mathcal X_1$и$\mathcal X_2$нельзя разделить гиперплоскостью,$\mathcal X$И не сломается. Комбинируя наши верхние и нижние оценки, мы показываем, что$VC\dim(\mathbb R^d в гиперплоскости)=d+1$.

Пример 3.14 (прямоугольник, выровненный по оси):

Рассматривая четыре точки ромба, мы сначала доказываем, что размерность ВК не меньше четырех. Тогда становится ясно, что можно реализовать все 16 дихотомий, некоторые из которых показаны на рис. 3.3(а). И наоборот, для любого набора из пяти различных точек, если мы построим наименьший выровненный по оси прямоугольник, содержащий точки, одна из точек окажется внутри этого прямоугольника.

Рисунок 3.3Размеры прямоугольника, выровненного по оси VC. (а) Пример достижимой дихотомии четырех точек в ромбовидном узоре. (b) Пятиточечная выборка не может быть достигнута, если внутренние точки и остальные точки имеют противоположные метки.

Представьте, что мы присваиваем отрицательную метку этой внутренней точке и положительную метку каждой из оставшихся четырех точек, как показано на рисунке 3. 3(б). Прямоугольник без выравнивания оси достигает этой разметки. Следовательно, никакой набор из пяти различных точек не может быть раздавлен и$VC\dim(прямоугольник, выровненный по оси)=4$.

Пример 3.15 (выпуклый многоугольник)

В основном мы изучаем классы выпуклых d-углов на плоскости. Чтобы получить нижнюю оценку, докажем, что любой набор$2d+1$Точки можно раздавить. Для этого выбираем$2d+1$Точки, для конкретной метки, если отрицательных меток больше, чем положительных, точки с положительными метками будут использоваться как вершины многоугольника, как показано на рисунке 3.4(a). В противном случае касательная отрицательной точки используется как ребро многоугольника, как показано в (3.4)(b). Чтобы получить верхнюю границу, можно показать, что выбор точек на окружности максимизирует количество возможных дихотомий, поэтому$ВК\тусклый(выпуклый)=2d+1$. Также обратите внимание$VCdim(выпуклый многоугольник)=+\infty$.

Пример 3.16 (синусоидальная функция)

Предыдущий пример показывает, что$\mathcal H$Измерение VC и определение$\mathcal H$Количество свободных параметров такое же. Например, количество параметров, определяющих гиперплоскость, соответствует ее размерности VC. Однако это не относится к общему случаю. Несколько упражнений в этой главе иллюстрируют этот факт. Яркий пример с этой точки зрения приведен ниже. Рассмотрим следующее семейство синусоидальных функций:$\{T\to\sin(\Omega T):\Omega\IN\Mathbb R\}$. Пример этого функционального класса показан на рис. 3.5. Эти синусоидальные функции можно использовать для классификации точек на сплошной линии:

Рисунок 3.4Выпуклая плоскость$d$Углы можно сломать$2d+1$точка. (а) D-образная конструкция, когда отрицательных меток больше. (b) когда передних этикеток больше$d$структура формы.

Рисунок 3.5функция синуса для классификации$(\omega=50)$Пример.

Используется для классификации точек на сплошной линии: если точка находится над кривой, она помечается как положительная, в противном случае — как отрицательная. Хотя это семейство синусоид определяется параметром ω, можно показать, что$VC\dim(sin)=+\infty$(Упражнение 3.20).

   Размерность VC многих других гипотетических множеств может быть определена или оценена сверху аналогичным образом (см. упражнение в этой главе). В частности, размерность$r<\infty$любого векторного пространства$VC$Размеры могут отображаться до$r$(Упражнение 3.19). Следующий результат, лемма Атола, проясняет, что концепция функции роста связана с$VC$связи между измерениями.

Рисунок 3.6В доказательстве леммы Зауэра$\mathcal G_1$и$\mathcal G_2$Иллюстрация того, как построить.

Теорема 3.17 (лемма Зауэра)

Предполагать$\mathcal H$за$VC\dim(\mathcal H)=d$набор гипотез. Тогда для всех$m\in]mathbb N$, имеет место следующее неравенство:

доказывать:Доказательство проводится по индукции$m+d$осуществляется выше. Утверждение, очевидно, относится к$m=1$и$d=0$или$d=1$. Теперь предположим, что это работает для$(m-1,d-1)$и$(m-1,d)$. исправлено с$\Pi\mathcal H(m)$Коллекция дихотомий$\mathcal S=\{x_1,...,x_m\}$, и установите$\mathcal G=\mathcal H_{|S}$по праву$\mathcal S$концепции, вытекающие из ограничений$\mathcal H$коллекция.

   Теперь рассмотрим$S'=\{x_1,...,x_{m-1}\}$上的下列数族。 мы будем$\mathcal G_1=\mathcal G_{|\mathcal S'}$определяется как ограничение$S'$результирующая концепция$\mathcal H$коллекция. Далее, определяя каждое понятие как$S'$или$S$Это коллекция ненулевых точек, мы можем быть определены как

так как$g'\subseteq\mathcal S'$ , $g'\in\mathcal G$значит не добавлять$x_m$,это$\mathcal G$концепция. Кроме того, ограничения$g'\cup\{x_m\}\in\mathcal G$значит$x_m$добавить в$g'$также сделать это$\mathcal G$Концепция чего-либо.$\mathcal G_1$и$\mathcal G_2$Структура показана на рисунке 3.6. наблюдать$|\mathcal G_1|+|\mathcal G_2|=|\mathcal G|$получить$\mathcal G_1$и$\mathcal G_2$Определение.

так как$VC\dim(\mathcal G_1)\le VC\dim(\mathcal G)\le d$, то через определение функции роста, используя предположение индукции,

Кроме того, согласно$\mathcal G_2$Определение того, если множество$\mathcal Z\subseteq\mathcal S'$одеяло$\mathcal G'$разбить, а потом собрать$\mathcal Z\cup\{x_m\}$одеяло$\mathcal G$разгромить. следовательно,

Согласно определению функции роста и индуктивному предположению,

следовательно,

Это завершает индуктивное доказательство.

Важность леммы   Зауэра можно увидеть в следствии 3.18, которое показывает, что функция роста демонстрирует только два типа поведения:$VC\dim(\mathcal H)=d<+\infty$, при этих обстоятельствах$\Pi_\mathcal H(m)=O(m^d)$,или$VC\dim(\mathcal H)=+\infty$, при этих обстоятельствах$\Pi_\mathcal H(m)=2^m$.

Следствие 3.18.

Предполагать$\mathcal H$за$VC\dim(\mathcal H)=d$набор гипотез. тогда для всех$m\ge d$Сказать,

доказывать:Доказательство начинается с леммы Зауэра. Первое неравенство умножает каждую сумму на единицу из$m\ge d$Стартовый коэффициент равен или больше 1, второе неравенство будет неотрицательным и к нему добавляются.

После упрощения выражения с помощью биномиальной теоремы воспользуемся общим неравенством$(1-x)\le e^{-x}$чтобы получить окончательное неравенство.

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

Вывод 3.19 (граница обобщения размерности VC)

Предполагать$\mathcal H$представляет собой семейство функций ценности$\{−1, 1\}$с размерностью ВК$d$. Тогда для любого$δ>0$, с вероятностью не менее$1−\дельта$, следующее относится ко всем$h\in\mathcal H$ :

Следовательно, форма этого круга обобщения

Это подчеркивает важность соотношения/данных обобщения. Эта теорема представляет собой еще один пример бритвы Оккама, где простота измеряется меньшими размерами VC.

Границы размерности VC могут быть получены непосредственно без использования промежуточных оценок сложности Радемахера, как в (3.23): Объединение леммы Зауэра с (3.23) дает следующие оценки высокой вероятности

Его общий вид (3.30). Логарифмический множитель играет в этих оценках лишь незначительную роль. Фактически, для устранения этого фактора можно использовать более детальный анализ.

3.4 Нижний мир

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

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

Теорема 3.20 (нижняя оценка, случай достижимости)

Предполагать$\mathcal H$размер vc$d>1$набор гипотез. Тогда для любого$m\ge1$и любой алгоритм обучения$\mathcal A$, есть раздача$\mathcal D$разделить на$\mathcal X$и целевая функция$f\in\mathcal H$так что

доказывать:Предполагать$\bar X=\{x_0,x_1,...,x_{d-1}\}\subseteq X$это$\mathcal H$Разбитая коллекция. для любого$\epsilon>0$,Мы выбираем$\mathcal D$, сократив свою поддержку до$\bar X$, так точка$x_0$с очень большой вероятностью$(1-8\epsilon)$, остальная вероятностная масса равномерно распределена по остальным точкам:

С этим определением большинство образцов содержат$X_0$,так как$X$быть раздавленным, когда определится$x_i$Когда на таблице нет меток, попадающих в обучающую выборку,$\mathcal A$В общем, не лучше, чем подбросить монетку.

мы предполагаем, что$\mathcal A$существует$x_0$В приведенном выше нет ошибки, но без потери общности. для образца$S$, мы позволяем$\bar S$означает, что его элементы находятся в$\{x_1,...,x_{d-1}\}$набор в , пусть$\mathcal S$размер$m$образец$S$сборник, такой$|\bar S|\le(d-1)/2$. Теперь исправьте образец$S\in\mathcal S$, и учитывать все метки$f:\bar X\to\{0,1\}$равномерное распределение по$\mathcal U$, так как набор уничтожен, все метки находятся в$\mathcal H$середина. Тогда имеет место следующая нижняя оценка:

Первая нижняя оценка верна, потому что, когда мы рассматриваем только$x\notin\bar S$вместо$\bar X$все в$X\notin\bar S$, мы удаляем неотрицательный член из суммы. После перестановки членов следующее уравнение остается верным, потому что мы имеем$f\in\mathcal H$принять ожидаемое значение, каждый$f$и$\mathcal H$равные веса на$\mathcal H$разгромить$\bar X$. так как$\mathcal D$и$\bar S$Определение , окончательная нижняя оценка верна, последняя означает, что$|\bar X-\bar S|\ge(d-1)/2$.

   Так как (3.33) применимо ко всем$S\in\mathcal S$, так что это также относится ко всем$S\in\mathcal S$:$\mathbb E_{S\in\mathcal S}[\mathbb E_{f\sim\mathcal U}[R_\mathcal D(h_S,f)]]\ge 2\epsilon$. Согласно теореме Фубини математическое ожидание можно переставить, поэтому

это означает$\underset{f\sim\mathcal U}{\mathbb E}[\underset{S\in\mathcal S}{\mathbb E}[R_\mathcal D(h_S,f)]]\ge2\epsilon$хотя бы для одного тега$f_0\in\mathcal H$. Разбейте это ожидание на две части и используйте$R_\mathcal D(h_S,f_0)\le\mathbb P_\mathcal D[\bar X-\{x_0\}]$,у нас есть:

$\mathbb P_{S\in\mathcal S}[R_\mathcal D(h_S,f_0)\ge\epsilon]$Совокупные элементы в доходе

Поэтому все образцы$S$(не обязательно в$S$Вероятность на ) может быть нижней границей следующим образом:

что приводит нас к$\mathbb P[S]$нижняя граница. Согласно мультипликативной границе Чернова (теорема D.4), для любого$\gamma>0$, больше, чем$(д-1)/2$указать на размер$m$Образец построен в:

Следовательно, для$\epsilon=(d-1)/(32m)$и$\gamma=1$,

за$\delta\le.01.$получить$\mathbb P[\mathcal S]\ge7\delta$и$\mathbb P_S[R_\mathcal D(h_S,f_0)\ge\epsilon]\ge\delta$.
Теорема утверждает, что для любого алгоритма$\mathcal A$, оба существуют$X$«Плохое» распределение и целевая функция на$f$, который определяется$\mathcal A$Возвращенная предполагаемая ошибка представляет собой константу, умноженную на$\frac{d}{m}$, с некоторой постоянной вероятностью. Это еще раз демонстрирует ключевую роль, которую играет фактор ВК в обучении. Результаты показывают, что когда размерность VC бесконечна, обучение PAC невозможно при достижимых условиях.
   Заметим, что доказательство показывает более сильный результат, чем утверждение теоремы: распределение$\mathcal D$Выбор не зависит от алгоритма$\mathcal A$. Теперь у нас есть теорема, которая дает нижнюю оценку для нереализуемого случая. Для его доказательства необходимы следующие две леммы.

Лемма 3.21

Предполагать$\alpha$является равномерно распределенной случайной величиной, принимающей$\{\alpha_-,\alpha_+\}$значение в , где$\alpha_-=\frac{1}{2}-\frac{\epsilon}{2}$и$\alpha_+=\frac{1}{2}+\frac{\epsilon}{2}$,Предполагать$S$за$m\ge1$выборка случайных величин,$X_1,...,X_m$Выбирать$\{0,1\}$значение в , и согласно$\mathbb P_{\mathcal D_\alpha}[X=1]=\alpha$Распределение определения$\mathcal D_\alpha$независимыми и равномерно распределенными. Предполагать$h$От$X^m$прибыть$\alpha_-,\alpha_+$функции справедлива следующая формула:

в$\Phi(m,\epsilon)=\frac{1}{4}(1-\sqrt{1-\exp(-\frac{m\epsilon^2}{1-\epsilon^2})})$означает все$m$и$\epsilon$.
доказывать:Эту лемму можно использовать с двумя уравнениями с$\alpha_-$и$\alpha_+$Объясняется эксперимент с предвзятой монетой. Это означает, что на основе$\mathcal D_{\alpha_-}$или$D_{\alpha_+}$пробы, взятые из$S$дискриминантное правило$h(S)$, чтобы определить, какая монета была подброшена, размер выборки$m$должен быть не менее$\Omega(1/\epsilon^2)$. Это доказательство остается в качестве упражнения (упражнение D.3). Воспользуемся тем, что для любого фиксированного$\epsilon$, функция$m\mapsto\Phi(m,x)$выпукла, что нетрудно установить.

Лемма 3.22

Предполагать$Z$брать$[0,1]$значение случайной величины. Тогда для любого$\gamma\in[0,1)$ ,

доказывать:так как$Z$Возьмите значение в$[0,1]$середина,

Таков вывод доказательств.

Теорема 3.23 (нижняя оценка, неизменяемый случай)

Предполагать$\mathcal H$за$VC$измерение$d>1$набор гипотез. Тогда для любого$m\ge1$и произвольные алгоритмы обучения$\mathcal A$, есть раздача$\mathcal D$разделить на$X\times\{0,1\}$,тем самым:

Аналогично, для любого алгоритма обучения проверка сложности выборки

доказывать:Предполагать$\bar X=\{x_1,...,x_d\}\subseteq X$для группы$\mathcal H$измельченные частицы. для любого$\alpha\in[0,1]$и любой вектор$\sigma=(\sigma_1,...,\sigma_d)^T\in\{-1,+1\}^d$, мы определяем распределение$\mathcal D_\sigma$, его поддержка$\bar X\times\{0,1\}$следующее:

Поэтому каждая точка$x_i,i\in[d]$Этикетки следуют за распределением необъективных монет.$\mathbb P_{\mathcal D_\sigma}[\cdot|x_i]$, где отклонение определяется выражением$\sigma_i$символы и$\alpha$размер определяет. Для определения каждой точки$x_i$наиболее вероятная метка , поэтому алгоритму обучения необходимо сравнить$\alpha$Оценки с более высокой точностью$\mathbb P_{\mathcal D_\sigma}[1|x_i]$. Для дальнейшего увеличения сложности будут выбраны в соответствии с алгоритмом$\alpha$и$\sigma$, как показано в лемме 3.21,$\Omega(1/\alpha^2)$каждая точка обучающей выборки$x_i$пример.

   Очевидно, для всех$i\in[d]$, байесовский классификатор$h^*_{\mathcal D_\sigma}$Зависит от$h^*_{\mathcal D_\sigma}(x_i)=\arg\max_{y\in\{0,1\}}\mathbb P[y|x_i]=1_{\sigma_i>0}$определение. так как$\bar X$разбился, значит$h^*_{\mathcal D_\sigma}$существует$\mathcal H$середина. для всех$h\in\mathcal H$ ,

позволять$h_S$Алгоритмы обучения представлению$\mathcal A$при получении$\mathcal D_\sigma$нарисованный образец маркера$S$Предположения вернулись позже. мы будем использовать$|S|_x$Представительство$x$существует$S$явления в . Предполагать$\mathcal U$выражать$\{-1,+1\}^d$равномерное распределение на. Тогда, учитывая, что$(3.44)$, имеет место следующее представление:

так как$\sigma$Ожидаемое значение на$\Phi(m/d+1,\alpha)$нижняя граница , поэтому должно быть некоторое$\sigma\in\{-1,+1\}^d$

Тогда по лемме 3.22 для$\sigma$, для любого$\gamma\in[0,1]$,

в$u=\Phi(m/d+1,\alpha)$. выберите$\delta$и$\epsilon$, так что$\delta\le(1-\gamma)u$и$\epsilon\le\gamma\alpha u$

Чтобы соответствовать определению$\epsilon$и$\delta$Неравенство , пусть$\gamma=1-8\delta$. потом

выберите$\alpha=8\epsilon/(1-8\delta)$дает$\epsilon=\gamma\alpha/8$и условия

позволять$f(1/\epsilon^2)$Указывает на правую сторону. Мы ищем форму$m/d\le\omega/\epsilon^2$достаточное условие. от$\epsilon\le1/64$начать, обеспечить$\omega/\epsilon^2\le f(1/\epsilon^2)$, применяя$\frac{\omega}{(1/64)^2}=f(\frac{1}{(1/62)^2})$Будет достаточно. Это условие дает

следовательно,$\epsilon^2\le\frac{1}{320(m/d)}$достаточно для обеспечения неравенства. Теорема утверждает, что для любого алгоритма$\mathcal A$, в случае невозможности$X\times\{0,1\}$Существует «плохое» распределение на , такое что$\mathcal A$Возвращенная предполагаемая ошибка представляет собой константу, умноженную на$\sqrt{\frac{d}{m}}$, с некоторой постоянной вероятностью. В этом общем случае измерение VCD также является ключевой величиной в обучении. В частности, независимое обучение PAC невозможно при бесконечных размерностях VC.

3.5 Примечания к главе 3.5

Колчинский [2001], Колчинский и Панченко [2000] и Бартлетт, Бушерон и Лугоши [2002a] впервые выступили за использование сложности Радемахера для получения границ обобщения в обучении, см. также [Колчинский и Панченко, 2002, Бартлетт и Мендельсон, 2002]. ]. Бартлетт, Буске и Мендельсон [2002b] ввели понятие локальной сложности Радемахера, то есть сложность Радемахера ограничена подмножеством множества гипотез, ограниченным границей дисперсии. Это можно использовать для получения лучших гарантий при определенных предположениях о регулярности шума.

   Теорема 3.7 должна быть представлена ​​Массату [2000]. Вапник и Червоненкис [1971] ввели понятие размерности ВК и подробно его изучили [Вапник, 2006, Вапник и Червоненкис, 1974, Blumer et al., 1989, Assouad, 1983, Dudley, 1999]. Помимо ключевой роли в машинном обучении, измерение VC широко используется в других областях информатики и математики (см., например, Shelah [1972], Chazelle [2000]). Теорема 3.17 представляет собой лемму Ас-Зауэра, известную в учебном сообществе, но ее результаты были впервые даны Вапником и Червоненкисом [1971] (в немного отличающихся версиях), а затем независимо Зауэром [1972] и Шелахом [1972].

&emps;  Когда это достижимо, Вапник и Червоненкис [1974] и Хаусслер и др. [1988] дают нижние границы ожидаемой ошибки в терминах VCD. Затем дается нижняя граница вероятности ошибки, как указано в теореме 3.20 Блумера и др. [1989]. Теорема 3.20 и ее доказательство, улучшающее предыдущие результаты, принадлежат Ehrenfeucht, Haussler, Kearns, and Valiant [1988]. Devroye and Lugosi [1995] дали более точные оценки для той же задачи с более сложными выражениями. Теорема 3.23 дает нижнюю оценку в нереализуемом случае, а данное доказательство принадлежит Энтони и Бартлетту [1999]. См. ссылку Алона и Спенсера [1992] для других примеров применения вероятностных методов, демонстрирующих их полные возможности.

&emps;  Есть несколько других мер сложности ряда функций, используемых в машинном обучении, включая числа покрытия, числа переноса и некоторые другие меры сложности, обсуждаемые в главе 11. Каждая мера сложности естественным образом сводит бесконечный набор гипотез к конечному набору гипотез, что приводит к границе обобщения для бесконечного набора гипотез. Упражнение 3.31 иллюстрирует использование покрывающих чисел для получения границ обобщения с помощью очень простого доказательства. Между этими мерами сложности также существует тесная связь: например, согласно теореме Дадли, эмпирическая сложность Радмахера может быть рассчитана как$\mathcal N_2(\mathcal G,\epsilon)$Чтобы определить [Dudley, 1967, 1987], числа покрытия и упаковки могут быть определены размерностью VC [Haussler, 1995]. См. также [Ledoux and Talagrand, 1991, Alon et al., 1997, Anthony and Bartlett, 1999, Cucker and Smale, 2001, Vidyasagar, 1997] для получения информации о показателях покрытия для некоторых других мер границы сложности.

3.6    Упражнения

1,$\mathbb R$Функция роста в среднем интервале. Предполагать$\mathcal H$за$\mathbb R$Коллекция промежуточных интервалов.$\mathcal H$Размерность VC равна 2. Рассчитайте коэффициент дробления$\Pi_\mathcal H(m),m\ge0$. Сравните результаты с общими оценками функции роста.

2,$\mathbb R$Функция роста и сложность Радемахера для средних порогов. Предполагать$\mathcal H$представляет собой семейство пороговых функций на вещественной прямой:$\mathcal H=\{x\mapsto1_{x\le\theta}:\theta\in\mathbb R\}\cup\{x\mapsto1_{x\ge\theta}:\theta\in\mathbb R\}$. дать функцию роста$\Pi_m(\mathcal H)$верхняя граница. использовать его для получения$\Re_m(\mathcal H)$верхняя граница.

3. Функция роста линейной комбинации.$\mathbb R^d$Коллекция средних векторов$\mathcal X$Линейно отделимый маркер$\mathcal X$Разделены на два набора$\mathcal X^+$и$\mathcal X^-$и$\mathcal X^+=\{X\in\mathcal X:W\cdot X>0\}$и$\mathcal X^-=\{X\in\mathcal X:W\cdot X<0\}$для определенного$W\in\mathbb R^d$.

Предполагать$\mathcal X=\{X_1,...,X-m\}$да$\mathbb R^d$подмножество .

• (а) Пусть$\{\mathcal X^+,\mathcal X^-\}$да$\mathcal X$Дихотомия , пусть$X_{m+1}\in\mathbb R^d$. доказывать$\{\mathcal X^+\cup\{X_{m+1}\},\mathcalX^-\}$и$\{\mathcal X^+, \mathcal X^-\cup\{X_{m+1}\}\}$линейно отделима над гиперплоскостью, проходящей через начало координат тогда и только тогда, когда$\{\mathcal X^+,\mathcal X^-\}$происходит через происхождение и$X_{m+1}$Гиперплоскости линейно отделимы.
• (б) установить$\mathcal X=\{X_1,...,X_m\}$да$\mathbb R^d$подмножество такое, что$\mathcal X\le d$любой$k$Подмножество элементов с$k\le d$линейно независим. Затем было доказано$\mathcal X$Количество линейно отделимых маркеров равно$C(m,d)=2\sum^{d-1}_{k=0}(^{m-1}_k)$. (Подсказка: докажите по индукции$C(m+1,d)=C(m,d)+C(m,d-1)$ )
• (с) установить$f_1,...,f_p$да$p$ручка$\mathbb R^d$сопоставить с$\mathbb R$Функция. определение$\mathcal F$для семейства классификаторов, основанных на линейных комбинациях этих функций:

пройти через$\Psi(x)=(f_1(x),...f_p(x))$определение$\Psi$. предположим, что существует$x_1,...,x_m\in\mathbb R^d$, так что$\{\Psi(x_1),\Psi(x_m)\}$каждого$p$Все подмножества линейно независимы. Затем получите

4. Нижняя граница функции роста. Докажите, что лемма Зауэра (теорема 3.17) является строгой. Докажите существование размерности vc$d$гипотетический класс$\mathcal H$,сделать$\Pi_\mathcal H(m)=\sum^d_{i=0}(^m_i)$.

5. Улучшенная верхняя граница Радмахера. Доказательство может быть дано формулой ES[Π(G, S)]$\mathcal G$Более тонкая верхняя граница сложности семейства Радемахера, где Π(G, S) — количество способов пометить точки в выборке S.

6. Класс одноэлементных гипотез. Рассмотрим тривиальные наборы гипотез$\mathcal H$.

• а) Докажите, что любой$m>0$имеют$\Re_m(\mathcal H)=0$.
• (b) Используйте аналогичную структуру для доказательства строгости леммы Массара (теорема 3.7).

7. Класс двухфункциональных гипотез. Предполагать$\mathcal H$представляет собой набор гипотез, который сводится к двум функциям:$\mathcal H=\{h_{-1},h_{+1}\}$ , $S=(x_1,...,x_m)$является выборкой размера m.

• (а) Предположение$h-1$— постоянная функция со значением −1,$h+1$является постоянной функцией со значением +1. Что такое vc размерность d?Верхняя граница эмпирической сложности Радемахера RS(H) (подсказка: выразить RS(H) через абсолютное значение суммы переменных Радемахера и применить неравенство Йенсена), и использовать$\sqrt{d/m}$Сравните верхнюю границу.
• (б) Предположения$h-1$является постоянной функцией со значением -1, и$h+1$это функция, которая принимает значение -1, за исключением точки x1, которая принимает значение +1. Какова размерность d функции vc?Рассчитайте эмпирическую сложность Радемахера RS(H).

8. Тождество Радемахера. ремонт$м≥1$. Функция доказательства начинается с$\mathcal X$сопоставить с$\mathbb R$любой из$\alpha\in\mathbb R$и любые два набора гипотез$\mathcal H$и$\mathcal H'$Следующие тождества для :

• (a) $\hat\Re(\alpha\mathcal H)=|\alpha|\Re_m(\mathcal H)$.
• (b) $\hat\Re(\mathcal H+\mathcal H)=\Re_m(\mathcal H)+\Re_m(\mathcal H')$.
• (c) $\hat\Re(\{\max(h,h'):h\in\mathcal H,h'\in\mathcal H'\})\le\Re_m(\mathcal H)+\Re_m(\mathcal H')$

9. Сложность пересечения понятий Радемахера. Предполагать$\mathcal H_1$и$\mathcal H_2$будет$\mathcal X$сопоставить с$\{0,1\}$два набора функций, пусть$\mathcal H=\{h_1h_2:h_1\in\mathcal H_1,h_2\in\mathcal H_2\}$. Докажите, что для любого размера$m$образец$S$ , $\mathcal H$Эмпирическая сложность Радемахера может иметь следующие границы:

Совет: используйте функцию Липшица$x\mapsto\max(0,x-1)$и лемма Талагранда о стягивании.

используйте это, чтобы ограничить$c_1$и$c_2$и$c_1\in\varrho_1$и$c_2\in\varrho_2$пересечение$\mathcal U$Радемахеровская сложность семейства$\Re_m(\mathcal U)$,в соответствии с$c_1$и$c_2$Сложность Радемахера.

10. Вектор предсказания сложности Радемахера. Предполагать$S=(x_1,...,x_m)$размер$m$образец, зафиксированный как$h\to\mathbb R$.

• (а) с$u$выражать$h$правильно$S:u=[\begin{array}{cc}&h(x_1)\\&\dots\\&h(x_m)\end{array}]$вектор предсказания. давать$\mathcal H$Эмпирическая сложность Радемахера$\hat\Re_S(\mathcal H)$верхнюю границу , используя$||u||_2$Представление (подсказка: используйте ожидаемое представление абсолютного значения$\hat\Re_S(\mathcal H)$и применяя неравенство Дженсена). Предположение$h(x_i)\in\{0,-1,+1\}$для всех$i\in[m]$. с разреженной мерой$n=|\{i|h(x_i)\neq0\}|$Представляет границу сложности Радемахера. Какова верхняя граница экстремального значения меры разреженности?
• (б) установить$\mathcal F$будет$\mathcal X$сопоставить с$\mathbb R$семейство функций. использовать$\hat\Re_S(\mathcal F)$и$||u||_2$давать$\mathcal F+h=\{f+h:f\in\mathcal F\}$и$\mathcal F\pm h=(\mathcal F+h)\cup(\mathcal F-h)$Верхняя граница эмпирической сложности Радемахера.

11. Радемахеровская сложность регуляризованных нейронных сетей. Пусть входное пространство будет$\mathcal X=\mathbb R^{n_1}$. В этой задаче мы рассматриваем отображение$\mathcal X$прибыть$\mathbb R$Семейство регуляризованных нейронных сетей, определяемое набором функций:

в$о$является L-липшицевой функцией. Например,$о$Может быть сигмовидной функцией, т. е. 1-липшицевой.

• (доказательство$\hat\Re_S(\mathcal H)=\frac{\Lambda'}{m}\mathbb E_\sigma[\sup_{||u||_2\le\Lambda}|\sum^m_{i=1}\sigma_i\sigma(u\cdot X_i)|]$.
• (b) Используйте лемму Талагранда для всех наборов гипотез.$\mathcal H$и l-липшицевая функция$\Phi$эффективный:

до верхней границы$\hat \Re_S(\mathcal H)$, в соответствии с эмпирической сложностью Радемахера H', где H' определяется как

• (c) Используйте неравенство Коши-Шварца, чтобы доказать

• (г) Используя неравенство$\mathbb E_V[||V||_2]\le\sqrt{\mathbb E_V[||V||^2_2]}$, верхняя граница которого поддерживается неравенством Дженсена$\hat\Re_S(\mathcal H')$.

*(e) Предполагая, что для всех$X\in S$ , $||X||_2\le r$для определенного$r>0$. Используя предыдущий вопрос, используйте$r$вывести$\mathcal H$Верхняя граница сложности Радемахера.

12. Сложность везде. Профессор Джесету утверждает, что согласно его размерности vc$VC\dim(\mathcal H)$, обнаружил какое-либо предположение, что функция setHof находится в$\{−1,+1\}$Лучшая оценка сложности Радемахера при взятии значения. Его царство$\Re_m(\mathcal H)\le O(\frac{VC\dim(\mathcal H)}{m})$форма. Можете ли вы доказать, что профессор Джесту не прав? (Подсказка: рассмотрим предположение, что sethreed — это всего лишь две простые функции.)

13. Размерность vc объединения k интервалов. Какова размерность vc сплошного подмножества, состоящего из объединения k интервалов?

14. Размерность vc конечного множества гипотез. Максимальное значение размерности vc для доказательства конечной гипотезы равно$\log_2|\mathcal H|$.

15. Подмножество измерения vc. по одному параметру$\alpha:I_\alpha=[\alpha,\alpha+1]\cup[\alpha+2,+\infty)$Подмножество параметризованных сплошных линий$I_α$какой размер vc

16. Размер оси квадрата и треугольника vc.

• а) Каков размер vc осевого квадрата на плоскости?
• б) Рассмотрим на плоскости прямоугольные треугольники, стороны которых параллельны осям координат с прямым углом, а прямой угол находится в левом нижнем углу. Каков размер риска этой семьи?

17.$\mathbb R^n$Размер vc замкнутой сферы. доказывать$\mathbb R^n$Размерность vc всех наборов замкнутых сфер в ,

18. Размерность vc эллипсоида.$\mathbb R^n$Какова размерность vc множества всех эллипсоидов в ?

19. Размерность vc векторного пространства действительных функций. да$\mathbb R^n$конечномерное векторное пространство действительных функций,$\dim(F)=r<\infty$. Предполагать$\mathcal H$Для набора гипотез:

20. Размерность vc функции синуса. Рассмотрим семейство гипотез для функции синуса (пример 3.16):$\{x\to\sin(\omega x):\omega\in\mathbb R\}$

• а) Докажите, что для любого$x\in\mathbb R$точка$x,2x,3x,4x$Не может быть разложен семейством синусоидальных функций.
• (b) Докажите, что размерность vc семейства синусоидальных функций бесконечна. (Подсказка: докажите, что {2−i:i≤m} можно раздавить любым m>0)

21. Размерность vc объединения полупространств. данный$k$Верхняя граница vc-размерности класса гипотез, описываемых объединением полупространств.

22. Размерность vc пересечения полупространств. учитывать$k$Выпуклая полупространства$\varrho_k$своего рода. дает$VCdim(\varrho_k)$Верхние и нижние оценки .

23. Размерность vc концепции пересечения.

• (а) Пусть$\varrho_1$и$\varrho_2$два концептуальных класса. для любого концептуального класса$\varrho=\{c_1\cap c_2:c_1\in\varrho_1,c_2\in\varrho\}$,

• (б) установить$\varrho$является классом понятий размерности vc d, множество$\varrho$Все понятия для s от$\varrho$, класс понятий, образованный пересечением s≥1. доказал$\varrho_s$Размерность vc$2ds\log_2(3s)$. (Подсказка: для любого$х≥2,\log_2(3x)$ )

24. Понятие объединения размерности vc. Пусть A и B — два набора функций, отображающих X в {0,1}, и предположим, что A и B имеют конечную размерность VC, VCdim(A) = dA, VCdim(B) = dB. Пусть C=A∪B — объединение A и B.

• (a) Покажите, что для всех m$\Pi_\varrho(m)\le\Pi_\mathcal A(m)+\Pi_\mathcal B(m)$.
• (b) Используя лемму Зауэра, доказывается, что когда$m\ge d_\mathcal A+d_\mathcal B+2$час,$\Pi_\varrho(m)<2^m$, и дает$\varrho$Граница размерности vc.

25. Размерность vc концептуального симметричного различия. для обоих наборов$\mathcal A$и$\mathcal B$,Предполагать$\mathcal A\Delta\mathcal B$выражать$\mathcal A$и$\mathcal B$Разность симметрии , т.е.$\mathcal A\Delta\mathcal B=(\mathcal A\cup\mathcal B)-(\mathcal A\cap\mathcal B)$. Предполагать$\mathcal H$имеет конечную размерность vc$\mathcal X$Непустое семейство подмножеств. Предполагать$\mathcal A$да$\mathcal H$Элемент , определяет$\mathcal H\Delta\mathcal A=\{X\Delta\mathcal A:X\in\mathcal H\}$. показывать,

26. Симметричные функции. функция:$\{0,1\}^n\to\{0,1\}$является симметричным, если его значение однозначно определяется количеством единиц во входных данных. Предполагать$\varrho$представляет собой набор всех симметричных функций.

• (а) определить$\varrho$Размерность vc .
• (б) дает$\varrho$Верхняя и нижняя границы сложности выборки произвольного последовательного алгоритма обучения PAC.
• (c) Обратите внимание, что любые предположения$h\in\varrho$можно использовать вектор$(y_0,y_1,...,y_n)\in\{0,1\}^{n+1}$сказал, из которых$y_i$имеет$i 1$в примере$h$ценность. Дизайн на этой основе$\varrho$последовательный алгоритм обучения.

27. Размерность vc нейронной сети.

Предполагать$\varrho$да$\mathbb R^r$Класс понятий верхнего измерения vc. с промежуточным слоем$\varrho$Нейронная сеть определяется в$\mathbb R^n$Вышеупомянутая концепция может быть представлена ​​направленным ациклическим графом, как показано на рисунке 3.7, входной узел является нижним узлом, а концепция используется между каждым узлом$c\in\varrho$помечать.

заданный входной вектор$(x_1,...,x_n)$Выражение следующее. Во-первых, каждый$n$входные узлы отмечены как$x_i\in\mathbb R$. Далее, чтобы разрешить$u$Применяется значение входного узла заднего фронта$c$, получить верхний узел$u$отмечен как$c$значение .

Рисунок 3.7Есть нейронная сеть с промежуточным слоем.

Обратите внимание, что из-за$c$Значение находится в$\{0,1\}$, так$u$Значение находится в$\{0,1\}$середина. Значение верхнего узла или выходного узла также получается путем применения соответствующего понятия к значению узла, допускающего ребро к выходному узлу.

• (а) Пусть$\mathcal H$означает указанное выше$k\ge2$Набор всех нейронных сетей с внутренними узлами. Докажите функцию роста$\Pi_\mathcal H(m)$Его можно формально ограничить произведением функций роста множества гипотез, определенных на каждом промежуточном слое.

• (b) использовать его для верхней границы$\varrho$Размер vc нейронной сети (подсказка: вы можете использовать$m=2x\log_2(xy)\Longrightarrow m>x\log_2(ym)$правильно$м≥1$эффективный,$x, y>0$и$xy>4$эффективный).

• (с) установить$\varrho$пороговая функция$\varrho=\{sgn(\sum^r_{j=1}w_ix_j):W\in\mathbb R^r\}$Определенное семейство концептуальных классов. дать$k$и$r$указано$\mathcal H$Верхняя граница измерения vc.

28. Размерность vc выпуклой комбинации. Предполагать$\mathcal H$для подчиненного входного пространства$\mathcal X$сопоставить с$\{−1,+1\}$семейство функций, пусть$T$является положительным целым числом. семейство функций данного определения$\mathcal F_T$Верхняя граница размерности vc

(Подсказка: вы можете использовать упражнение 3.27 и его решение).

29. Неограниченное измерение vc.

• (a) Докажите, что если класс понятий$\varrho$Существуют бесконечные измерения vc, тогда они не поддаются обучению.
• (b) В стандартном сценарии обучения PAC алгоритм обучения сначала получает все примеры, а затем вычисляет свои гипотезы. В этом случае, как упоминалось ранее, класс концепций PAClearning бесконечной размерности vc невозможен.
  Теперь представьте себе другой сценарий, в котором алгоритм обучения может переключаться между рисованием дополнительных примеров и вычислениями. Цель этой задачи — продемонстрировать, что PAC-обучение возможно для некоторых концептуальных классов с бесконечными размерностями vc.
  Например, рассмотрим класс понятий подмножества всех натуральных чисел$\varrho$особые обстоятельства. У профессора Витреса есть идея для первого этапа алгоритма обучения. На первом этапе L рисует столько точек, что вероятность рисования точек за пределами наблюдаемого максимального значения M мала и с высокой достоверностью. Сможете ли вы реализовать идею профессора Витреса, описав второй этап алгоритма? Следует также показать, что L можно изучить с помощью pac$\varrho$.

30. Случай, когда vc-мерное обобщение ограничено и достижимо. В этом упражнении мы покажем, что в достижимых условиях оценки, данные в следствии 3.19, могут быть улучшены до$O(\frac{d\log(m/d)}{m})$. Предполагая, что мы находимся в достижимом сценарии, т.е. Целевое понятие содержится в нашем гипотетическом классе$\mathcal H$середина. Покажем, что если гипотеза с выборкой$S\sim\mathcal D^m$последовательным, то для любого$\epsilon>0$ , $m\epsilon\ge8$

• (а) Пусть$\mathcal H_S\subseteq\mathcal H$есть с образцом$S$Непротиворечивое подмножество гипотез, пусть$\hat R_S(h)$выраженный относительно образца$S$эмпирическая ошибка , и будет$S'$определяется как другой из$\mathcal D^m$Независимая выборка, взятая из . Докажите следующие неравенства для любого$h_0\in\mathcal H_S$Учредил:

• (б) Доказательство$\mathbb P[B(m,\epsilon)>\frac{m\epsilon}{2}]\ge\frac{1}{2}$. Используйте это неравенство и результат (а), чтобы доказать, что для любого$h_0\in\mathcal H_S$

• (c) Вместо двух выборок мы можем взять выборку T размером 2m и разделить ее равномерно и случайным образом на S и S'. Правую часть части (б) можно переписать так:

Предполагать$h_0$да$\hat R_T(h_0)>\frac{\epsilon}{2}$гипотеза,$l>\frac{m\epsilon}{2}$да$h_0$Общее количество ошибок для T, указывающее, что все ошибки попадают в$S'$Верхняя граница вероятности равна$2^{-l}$.

• Часть (b) пункта (d) гласит, что для любого$h\in\mathcal H$

Используйте эту оценку, чтобы доказать, что любой$h\in\mathcal H$

• (e) Использовать и привязать к верхней границе$\underset{\underset{T\to[S,S']}{T\sim\mathcal D^{2m}:}}{\mathbb P}[\exists h\in\mathcal H:\hat R_S(h)=0\wedge\hat R_{S'}(h)>\frac{\epsilon}{2}]$Завершите доказательство неравенства (3.54), показав, что можно получить$O(\frac{d\log(m/d)}{m})$Граница порядка с высокой вероятностью обобщения.

31. Границы обобщения на основе чисел покрытия. Предполагать$\mathcal H$будет$\mathcal X$отображать на действительные числа$\mathcal y\subseteq\mathbb R$Подмножество семейства функций. для любого$\epsilon>0$ , $L_\infty$норма$\mathcal H$покрытия$\mathcal N(\mathcal H,\epsilon)$очень маленький$k\in\mathbb N$, так что$h\in\mathcal H$можно закруглить как$\epsilon$из$k$охват мяча, т. е. есть$\{h_1,...,h_k\}\subseteq\mathcal H$, так что для всех$h\in\mathcal H$,существует$я≤к$и$||h-h_i||_\infty=\max_{x\in\mathcal X}|h(x)-h_i(x)|\le\epsilon$. В частности, когда$\mathcal H$является компактным множеством, радиус может быть$\epsilon$мяча$\mathcal H$ограниченное покрытие извлекается из покрытия, поэтому$\mathcal N$ограничено.
Числа покрытия обеспечивают меру сложности класса функций: чем больше число покрытия, тем богаче семейство функций. Цель этой задачи — проиллюстрировать это, доказав границу обучения в случае квадрата потерь. позволять$\mathcal D$выражать$\mathcal X\times\mathcal Y$Распределение на , из которого можно извлечь помеченные примеры. Потом,$h\in\mathcal H$Ошибка обобщения для квадрата потерь определяется выражением$R(h)=\mathbb R_{(x,y)\sim\mathcal D}[(h(x)-y)^2]$определение, которое для меченых образцов$S=((x_1,y_1),...,(x_m,y_m))$Эмпирическая ошибка определяется выражением$\hat R_S(h)-\frac{1}{m}\sum^m_{i=1}(h(x_i)-y_i)^2$определение. Мы предполагаем, что это ограничено, т.е. существует$M>0$сделать$|h(x)−y|\le M$для всех$(x,y)\in\mathcal X\times\mathcal Y$. Оценка обобщения для доказательства этой проблемы такова:

Доказательство основано на следующих шагах.

• (а) Пусть$L_S=R(h)−\шляпа R_S(h)$, то для всех$h_1,h_2\in\mathcal H$и произвольно помеченные образцы со следующими неравенствами:

• (б) Предположения$\mathcal H$возможно$k$подмножество$\mathcal B_1,...,\mathcal B_k$покрытие, то есть$\mathcal H=\mathcal B_1\cup...\cup\mathcal B_k$. Затем докажите, что для любого$\epsilon$, имеет место следующая верхняя оценка:

• в) Наконец, пусть$k=\mathcal N(\mathcal H,\frac{\epsilon}{8M})$это радиус$\epsilon/(8M)$,от$\mathcal H$центр, обложка$h_1,...,h_k$, обозначенный частью (а) для всех$i\in[k]$,

И применим неравенство Хёффдинга (теорема D.2) для доказательства (3.55).