7. Неравномерная обучаемость

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

   Мы начинаем обсуждение с определения концепции «неравномерной обучаемости», которая позволяет размеру выборки зависеть от предположения, с которым сравнивается учащийся. Затем мы характеризуем неравномерную обучаемость и показываем, что неоднородная обучаемость является строгим ослаблением независимой обучаемости PAC. Мы также показываем, что достаточным условием неравномерной обучаемости является$\mathcal H$является счетным объединением гипотетических классов, каждый из которых сходится равномерно. Эти результаты будут продемонстрированы в разделе 7.2 путем введения новой парадигмы обучения под названием минимизация структурных рисков (SRM). В разделе 7.3 мы определяем парадигму SRM для класса счетных гипотез, что приводит к парадигме минимальной длины описания (MDL). Парадигма MDL обеспечивает формальный аргумент в пользу индуктивного философского принципа, известного как бритва Оккама. Далее, в разделе 7.4, мы вводим согласованность как более слабое понятие обучаемости. Наконец, мы обсудим значение и полезность различных концепций обучаемости.

7.1 Неравномерная обучаемость

«Неравномерная обучаемость» позволяет размеру выборки быть неравномерным для разных гипотез конкурирующих учащихся. Скажем, гипотеза$h$с другим предположением$h^\prime$конкурировать$(\epsilon,\delta)$, вероятность которого больше, чем$(1-\delta)$,

В обучаемости PAC понятие «конкурентоспособность» не очень полезно, так как мы ищем гипотезу с абсолютно низким риском (в достижимом случае) или гипотезу, сравнимую с гипотезой в нашем классе (в агностическом случае). ) для достижения минимального риска по сравнению с допущением с низким риском. Следовательно, размер выборки зависит только от параметров точности и достоверности. Однако при неравномерной обучаемости допустимы размеры выборки вида$m_\mathcal H(\epsilon,δ,h)$; то есть это зависит еще и от того, с кем мы конкурируем$h$. официально,

Определение 7.1

Если есть метод обучения А и функция$m_\mathcal H^{NUL}:(0,1)^2\times \mathcal H\to \mathbb N$так что всем$\epsilon,\delta \in (0,1)$и все$h\in \mathbb H$,если$m\ge m_\mathcal H^{NUL}(\epsilon,\delta,h)$Тогда для каждого распределения D для$S\backsim D^m$Вероятность выбора не менее$1-\delta$. тогда устанавливается гипотеза$\mathcal H$является неравномерно обучаемым. он думает

На этом этапе может быть полезно просмотреть определение независимой обучаемости PAC (определение 3.3):

Если существует алгоритм обучения A и функция$m_\mathcal H:(0,1)^2\to \mathbb N$так что всем$\epsilon,\delta \in (0,1)$и все распределения D, если$m\ge m_\mathcal H(\epsilon,\delta)$,правильно$S\backsim D^m$Вероятность выбора не менее$1-\delta$. тогда устанавливается гипотеза$\mathcal H$агностический PAC поддается обучению, думает он

Заметим, что это означает, что для всех$h\in H$

В обоих типах обучаемости мы требуем, чтобы выходная гипотеза конкурировала со всеми другими гипотезами в классе.$(\epsilon,\delta)$. Но разница между этими двумя концепциями обучаемости заключается в том, зависит ли размер выборки от$A(S)$Предположения сравнения ошибок. Обратите внимание, что неравномерная обучаемость является ослаблением независимой обучаемости PAC. То есть, если класс является агностическим PAC-обучаемым, то он также неоднородно обучаем.

7.1.1 Представление неравномерной обучаемости

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

Теорема 7.2: Гипотетические классы для бинарных классификаторов$\mathcal H$является неравномерно обучаемым тогда и только тогда, когда он является счетным объединением классов агностических PAC обучаемых гипотез.

Доказательство теоремы 7.2 опирается на результаты следующих независимых интересов:
Теория 7.3. Предположим$\mathcal H$— гипотетический класс, который можно записать как счетное объединение гипотетических классов,$\mathcal H=\bigcup _{n∈N}\mathcal H_n$, каждый, из которых$\mathcal H_n$Все имеют равномерную сходимость. Тогда он неравномерно обучаем.
Напомним, что в главе 4 мы показали, что равномерной сходимости достаточно для обучаемости агностических PAC. Теория 7.3 обобщает этот результат на неравномерную обучаемость. В следующем разделе мы докажем эту теорему, представив новую парадигму обучения. Теперь докажем теорему 7.2.

Доказательство теоремы 7.2.

Сначала предположим$\mathcal H=\bigcup _{n∈N}\mathcal H_n$, каждый$\mathcal H_n$Все они независимы от PAC. Используя Фундаментальную теорему статистического обучения, доказывается, что каждый$\mathcal H_n$Все имеют равномерную сходимость. Поэтому, используя теорему 7.3, рассмотрим$\mathcal H$является неравномерно обучаемым.
   Для другого направления предположим$\mathcal H$Неравномерная обучаемость может использовать некоторый алгоритм А. для всех$n\in N$, сделать$\mathcal H_n=\{h\in \mathcal H:m_{\mathcal H}^{NUL}(1/8,1/7,h)\le n\}$. Очевидно,$\mathcal H=\bigcup _{n∈N}\mathcal H_n$. Кроме того, используйте$m_{\mathcal H}^{NUL}$Из определения мы знаем, что для любого распределения$D$удовлетворить$H_n$предположение о достижимости, в$S\sim D^n$Вероятность не менее$6/7$случае, мы получаем$L_D(A(S))\le 1/8$, Используя Фундаментальную теорему статистического обучения, что означает$\mathcal H_n$Размерность VC должна быть конечной, поэтому$\mathcal H_n$является агностическим PAC обучаемым.
   Следующий пример показывает, что неравномерная обучаемость является строгим ослаблением обучаемости независимого PAC, то есть существуют гипотетические классы, которые неравномерно обучаемы, но не обучаемы независимому PAC.

Пример 7.1

Рассматривайте домен экземпляра как$X= \mathbb R$проблема бинарной классификации. для всех$n∈\mathbb N$Предполагать$\mathcal H_n$за$n$Класс полиномиальных классификаторов степени, т. е.$\mathcal H_n$Это в форме$h(x)=sign(p(x))$Коллекция всех классификаторов, где$p:R\to R$да$n$полином степени. Предполагать$\mathcal H=\bigcup _{n\in \mathbb N}\mathcal H_n$,следовательно,$\mathcal H$да$R$Класс всех полиномиальных классификаторов выше. легко проверить$VCdim(\mathcal H)=\infty$и$VCdim(\mathcal H_n)=n+1$(См. упражнение 12.) Следовательно,$\mathcal H$не поддается обучению PAC, а согласно теореме 7.3$\mathcal H$является неравномерно обучаемым.

7.2 Минимизация структурных рисков

Пока что мы указали$\mathcal H$Мы думаем, что классовая гипотеза кодирует наши предшествующие знания.$\mathcal H$Классовая гипотеза является хорошим предсказателем для поставленной учебной задачи. Другой способ выразить наше предварительное знание — указать$\mathcal H$Внутреннее предпочтение гипотез. В парадигме минимизации структурных рисков (SRM) мы сначала предполагаем$\mathcal H$можно записать как$\mathcal H=\bigcup _{n\in \mathbb N}\mathcal H_n$Затем укажите весовую функцию,$w:N\to [0,1]$, который присваивает вес каждому классу гипотез,$\mathcal H_n$, так что чем выше вес, тем сильнее предпочтение класса гипотез. В этом разделе мы обсудим, как использовать эти априорные данные для обучения. В следующем разделе мы опишем несколько важных схем взвешивания, включая минимальную длину описания.

В частности, предположим$\mathcal H$— гипотетический класс, который можно записать как$\mathcal H=\bigcup _{n\in \mathbb N}\mathcal H_n$. Например,$\mathcal H$может быть классом всех полиномиальных классификаторов, где каждый$\mathcal H_n$да$n$Класс полиномиальных классификаторов степени (см. пример 7.1). Предполагая, что для каждого$n$,своего рода$\mathcal H_n$Имеет последовательную конвергенцию (см. Определение 4.3 в главе 4) и имеет функции сложности образца$m^{UC}_{\mathcal H_n}(\epsilon,\delta)$Определим также функцию$\epsilon_n :\mathbb N\times(0,1)\to (0,1)$Зависит от

Другими словами, у нас есть фиксированный размер выборки.$m$, мы заинтересованы в этом, используя$m$Выборочная выборка, наименьшая возможная верхняя граница разрыва между эмпирическим риском и истинным риском.
Схождение от равномерного и$\epsilon_n$Из определения видно, что для всех$m$и$δ$, с вероятностью не менее$1- δ$существует$S\sim D^M$О вариантах, которые у нас есть

Предполагать$w:N\to [0,1]$такая функция$\sum^\infty_{n=1}w(n)\le 1$.мы будем$w$гипотетический класс$\ Mathcal h_1, \ mathcal h_2 \ cdot \ cdot \ cdot \ cdot$весовая функция вкл. . Такая весовая функция может отражать важность учащегося для каждого класса гипотез или некоторую меру сложности различных классов гипотез. если$\mathcal H$да$N$конечное объединение гипотетических классов, то одни и те же веса могут быть просто$1/N$Присваивается всем гипотетическим классам. Такие равные веса не соответствуют априорным предпочтениям ни для одного из гипотетических классов. Конечно, если кто-то считает (как априорное знание), что определенный класс гипотез с большей вероятностью будет содержать правильную целевую функцию, то ему следует присвоить больший вес, чтобы отразить это априорное знание. когда$H$заключается в том, что равномерное взвешивание невозможно, если предполагается (счетно) бесконечное объединение классов, но могут работать многие другие схемы взвешивания. Например, вы можете выбрать$ш (п) = \ гидроразрыва {6} {π ^ 2n ^ 2}$или$ш (п) = 2 ^ {- п}$. Позже в этой главе мы предоставим еще один удобный способ определения весовых функций с помощью языка описания.
  Правила SRM следуют подходу «минимизации границ». Это означает, что цель парадигмы — найти гипотезу, минимизирующую некоторую верхнюю границу истинного риска. Граница, которую хочет минимизировать правило SRM, дается в следующей теореме.

Теорема 7.4.

Предполагать$w:N\to [0,1]$такая функция$\sum^\infty_{n=1}w(n)\le 1$.Предполагать$\mathcal H$— гипотетический класс, который можно записать как$\mathcal H=\bigcup _{n\in \mathbb N}\mathcal H_n$, где для каждого$n$,$\mathcal H_n$Удовлетворить функцию сложности выборки$m^{UC}_{\mathcal H_n}(\epsilon,\delta)$последовательная сходимость. позволять$\epsilon_n$как определено в уравнении (7.1). Затем для каждого$δ\in(0,1)$и распространение$D$, с вероятностью не менее$1−\дельта$о$S\sim D^m$выбор, следующие оценки (одновременно) для всех$n\in N$и$h\in \mathcal H_n$Резерв.

Следовательно, для каждого$δ\in(0,1)$и распространение$D$, с вероятностью не менее$1−\дельта$он думает

доказывать

для каждого$n$,определение$\delta_n=w(n)\delta$. Примените скорость, указанную в уравнении (7.2), ко всем$n$Сохраняя предположение о равномерной сходимости, получаем, что если предварительно зафиксировать$n$, то вероятность не менее$1−δ$выбор$S\sim D^m$.

существует$п=1,2,\кдот\кдот\кдот\кдот,$применяется и разграничивается. , получаем вероятность не менее$1−\sum_n\delta_n=1−δ\sum_nw(n)\ge 1−\delta$Предыдущая формула применима ко всем$n$, что является нашим доказательством.
выражать

Тогда уравнение (7.3) означает

Парадигма SRM ищет h, который минимизирует эту границу, как описано в следующем псевдокоде:

Минимизация структурных рисков (SRM) Предыдущие знания: $\mathcal H=\bigcup_n\mathcal H_n$в$\mathcal H_n$и$m^{UC}_{\mathcal H_n}w:\mathbb N\to[0,1]$Сходимость равномерно, в которой$\sum_nw(n)\le 1$ определение:$\epsilon_n$Как показано в уравнении (7.1),$n(h)$как показано в уравнении (7.4) Вход: тренировочный набор$S\sim \mathcal D^m$,Уверенность$\delta$ вывод:$h\in argmin_{h\in\mathcal H}[L_S(h)+\epsilon_{n(h)}(m,w(n(h))\cdot\delta)]$

В отличие от парадигмы ERM, обсуждавшейся в предыдущих главах, мы больше не заботимся только об эмпирическом риске.$L_S(h)$, но чтобы уменьшить ошибку оценки, мы хотим сравнить некоторые из наших предубеждений в отношении низкого эмпирического риска с нашими$\epsilon_{n(h)}(m,w(n(h))\cdot\delta)$Предубеждения меньших категорий обмениваются.
Далее мы показываем, что парадигма SRM может использоваться для неравномерного обучения каждого класса, счетного объединения гипотетических классов, которые сходятся равномерно.

Теорема 7.5.

Предполагать$\mathcal H$является гипотетическим классом таким, что$\mathcal H=\bigcup_{n\in\mathbb N}\mathcal H_n$, каждый, из которых$\mathcal H_n$Имеет сложность выборки$m^{UC}_{\mathcal H_n}$последовательная сходимость. позволять$w:N\to[0,1]$сделать$ш (п) = \ гидроразрыва {6} {п ^ 2π ^ 2}$. Затем, используя правила и тарифы SRM,$\mathcal H$является неравномерно обучаемым.

доказывать

Предполагать$A$речь идет о весовой функции$w$алгоритм СРМ. для всех$h\in H$,$\epsilon$и$\delta$,Предполагать$m\ge m^{UC}_{\mathcal H_{n(h)}}$. использовать$\sum_nw(n)=1$Тот факт, что мы можем применить теорему 7.4, чтобы получить с вероятностью не менее$1−δ$выбор$S\sim \mathcal D^m$, каждый из нас$h^\prime\in\mathcal H$имеют,

Вышеизложенное особенно верно для Гипотезы А, возвращаемой правилом SRM. По определению SRM получаем

Наконец, если$m\ge m^{UC}_{\mathcal H_{n(h)}} (\epsilon/2,w(n(h)\delta)$затем явно$\epsilon_{n(h)}(m,w(n(h))\delta)\le \epsilon/2$, Также от каждого$\mathcal H_n$Исходя из последовательной сходимости , мы получаем вероятность большую, чем$1-δ$ ,

Объединяя все предыдущие результаты, получаем$L_\mathcal D(A(S))\le L_{\mathcal D}(h)+\epsilon$, что является нашим доказательством.

Заметим, что предыдущая теорема также доказывает теорему 7.3.

Замечание 7.2

(У неравномерной обучаемости бесплатных обедов не бывает) Мы показали, что любое счетное объединение конечных VC-мерных классов неравномерно обучаемо. Оказывается, для любого бесконечного множества областей$X$,$X$Классы всех вышеперечисленных бинарных функций не являются счетными объединениями конечномерных классов. Мы оставляем доказательство этого утверждения в качестве (нетривиального) упражнения (см. упражнение 5). Таким образом, в некотором смысле неоднородное обучение справедливо и для теоремы о небесплатном обеде: т. е. пока область не конечна, для всех детерминированных бинарных классификаторов не существует неоднородного обучаемого (хотя для каждого такого классификатора , существует простой алгоритм для его изучения — ERM для гипотетических классов, которые содержат только этот классификатор).

Интересно сравнить результаты неравномерной обучаемости, приведенные в теореме 7.5, с задачей независимого ПАК, обучающего только любой конкретной HN. неровный$\mathcal H$Учащиеся класса имеют слабые предварительные знания или предвзятость - это$\mathcal H$Ищите модели внутри классов, а не сосредотачивайтесь на конкретном$\mathcal H_n$. Цена ослабления предшествующих знаний связана с любым конкретным$h\in \mathcal H$Для соревнований требуется повышенная сложность образца. Для конкретной оценки этого разрыва рассмотрим задачу бинарной классификации с нулевой или единичной потерей. Предположим, что для всех n$VCdim(\mathcalH_n)=n$. так как$m^{UC}_{\mathcal H_{n(h)}}(\epsilon,\delta)=C\frac {n+log(1/\delta)}{\epsilon^2}$(где C — константа, фигурирующая в теореме 6.8), простое вычисление показывает, что

То есть передать предварительные знания учащегося из цели включения.$h$Конкретный$\mathcal H_n$Стоимость релаксации в счетный союз зависит от$h$Индекс первого класса, в котором он находится. Эта стоимость увеличивается с индексом категории, который можно интерпретировать как отражение ценности знания правильной расстановки приоритетов в$\mathcal H$.

7.3 Минимальная длина описания и бритва Оккама

Предполагать$\mathcal H$есть класс счетных гипотез. Тогда мы можем положить$\mathcal H$Записывается как счетное объединение мономорфных классов, т.е.$\mathcal H=\bigcup _{n\in\mathbb N}\{h_n\}$. Согласно неравенству Хёффдинга (лемма 4.5) каждый мономорфный класс имеет равномерную сходимость, скорость сходимости$m^{UC}(\epsilon,\delta)=\frac {log(2/\delta)}{2\epsilon^2}$. Следовательно, функция в уравнении (7.1)$\epsilon_n$стать$\epsilon_n(m,\delta)=\frac {log(2/\delta)}{2m}$, правило SRM становится

Эквивалентно, мы можем$w$считается от$\mathcal H$прибыть$[0,1]$функция , то правило SRM становится

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

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

Предположение$\mathcal H$— это гипотетический класс, который мы хотим описать. исправлен некоторый ограниченный набор символов$\sum$(или «символы»), которые мы называем алфавитом. Для конкретики положим$\sum=\{0,1\}$. Строка из$\sum$Конечная последовательность символов для начала, например,$\sigma=(0,1,1,1,0)$длина$5$Нить. мы используем$|\sigma|$Указывает длину строки. Набор всех строк конечной длины представлен как$\sum^*$ . $\mathcal H$Язык описания функции$d:\mathcal H\to\sum^*$, будет$\mathcal H$каждый член$h$сопоставить со строкой$d(h)$.$d(h)$называется "$h$описание", длина которого определяется$|h|$Выражать.

Мы потребуем, чтобы язык описания был беспрефиксным, т. е. для каждого отдельного$h$,$h\prime$ , $d(h)$нет$d(h\prime)$префикс. То есть мы не допускаем никаких строк$d(h)$оказывается любой более длинной строкой$d(h\prime)$первое$| h |$символ. Коллекция строк без префикса имеет следующие комбинированные свойства:
Лемма 7.6 (неравенство Крафта), если$S\subseteq \{0,1\}^*$представляет собой набор строк без префикса, то

доказывать Определение$S$Распределение вероятностей участников выглядит следующим образом: при неоднократном подбрасывании непредвзятой монеты решка помечается как$0$и$1$, пока результирующая последовательность не будет$S$член; в этот момент остановитесь. для каждого$\sigma \in S$, Предполагать$P(\sigma)$генерировать строку для процедуры$\sigma$Вероятность. Обратите внимание, потому что$S$не имеет префикса, поэтому для каждого$\sigma \in S$, если результат подбрасывания монеты следует$\sigma$позже, только если результирующая последовательность равна$\sigma$когда мы остановимся. Следовательно, для каждого$\sigma \in S$, мы получили$P(\sigma) =\frac {1}{2^{|σ|}}$. Поскольку вероятности в сумме не превышают 1, наше доказательство заканчивается.
Согласно неравенству Крафта предполагается, что класс$\mathcal H$Любой язык описания без префикса дает весовую функцию для этого гипотетического класса$w$Мы просто установим$w(H)=\frac{1}{2^|h|}$. Это наблюдение сразу же приводит к следующим выводам:

Теорема 7.7.

Предполагать$\mathcal H$— гипотетический класс, пусть$d:\mathcal H\to \{0,1\}^∗$да$\mathcal H$Язык описания без префиксов для . Затем для каждого объема выборки$m$, каждый доверительный параметр$\delta>0$, каждое распределение вероятностей$\mathcal D$, вероятность больше, чем$1−\дельта$о$S\sim \mathcal D^m$Выбор у нас есть,

в$|h|$да$d(h)$длина.
доказыватьвыберите$w(H)=\frac{1}{2^|h|}$, применяя теорему 7.4 в$\epsilon_n(m,\delta)=\sqrt\frac{ln(2/\delta)}{2m}$,Уведомление$ln(2^{|h|})=|h| ln(2)<|h|$.
Как и в случае теоремы 7.4, этот результат показывает, что$\mathcal H$Парадигма обучения - с учетом обучающего набора$S$, гипотеза поиска$h\in \mathcal H$предел минимизации ,$L_S(h)+\sqrt\frac{|h|+ln(2/\delta)}{2m}$. В частности, предлагается взвешивать эмпирические риски, чтобы сократить длину описания. Это приводит к парадигме обучения с минимальной длиной описания.

Минимальная длина описания (MDL) Предыдущие знания: $\mathcal H$класс счетных гипотез $\mathcal H$Зависит от$\{0,1\}$Описания языков без префиксов на для всех$h\in \mathcal H$,$\mid h\mid$да$h$представление длины Вход: тренировочный набор$S\sim D^m$,Уверенность$\delta$ вывод:$h\in argmin_{h\in\mathcal H}\bigg[L_S(h)+\sqrt {\frac {\mid h \mid+ln(2/\epsilon)}{2m}} \bigg].$

Пример 7.3

позволять$\mathcal H$все предсказанные классы, которые могут быть реализованы с использованием некоторого языка программирования, такого как C++. Давайте представим каждую программу (в алфавите) с помощью двоичной строки, полученной при выполнении команды gzip в программе.$\{0,1\}$создать язык описания без префиксов). Потом,$\mid h \mid$это с$h$Длина (в битах) вывода gzip при запуске соответствующей программы C++.

7.3.1 Бритва Оккама

Теорема 7.7.

Это говорит о том, что если две гипотезы имеют одинаковый эмпирический риск, истинный риск, описывающий более короткую гипотезу, может быть ограничен меньшим значением. Следовательно, этот результат можно рассматривать как передачу философского сообщения:
Краткие объяснения (то есть гипотезы меньшей длины) имеют тенденцию быть более эффективными, чем длинные объяснения.
Это хорошо известный принцип, известный как бритва Оккама, названный в честь английского логика XIV века Уильяма Оккама, которому приписывают то, что он первым сформулировал его. Здесь мы предлагаем возможное обоснование этого принципа. Неравенство теоремы 7.7 показывает, что, полагая$h$Чем сложнее (в смысле более длинного описания), тем большему размеру выборки он должен соответствовать, чтобы гарантировать, что он имеет меньший реальный риск.$L_{\mathcal D}(h)$.

С другой стороны, наши утверждения о бритве Оккама кажутся немного ошибочными. В контексте, когда в науке обычно используется бритва Оккама, язык, сложность которого измеряется, является естественным языком, тогда как здесь мы можем рассматривать любой абстрактный язык описания. Предположим, у нас есть два предположения$\mid h^\prime \mid$Сравнивать$\mid h \mid$значительно меньше. Согласно предыдущим результатам, если оба находятся в данном обучающем наборе$S$такая же ошибка на$\mid h \mid$Истинная ошибка может быть намного выше, чем$\mid h^\prime \mid$истинная ошибка , поэтому следует предпочесть$\mid h^\prime \mid$вместо$\mid h \mid$. Однако мы можем выбрать другой язык описания, например, длину$3$строка, назначенная$h$, присваивая строку длиной 100000$h^\prime$. Внезапно люди предпочитают$h$вместо$h^\prime$. но это то же самое$h$и$h^\prime$, мы поспорили два предложения назад$h^\prime$должно быть предпочтительным. Где здесь ловушка?

На самом деле между гипотезами нет присущей общности различий. Ключевым аспектом здесь является порядок зависимостей между исходным выбором языка (или гипотезой о предпочтениях) и обучающей выборкой. Как мы знаем из базовой границы Хеффдинга (уравнение (4.2)), если мы делаем какие-либо предположения до того, как увидим данные, то мы гарантированно получим довольно малый член ошибки оценки$L_{\mathcal D}(h)\le L_S(h)+\sqrt\frac{ln(2/\delta)}{2m}$. Выбор языка описания (или, что то же самое, некоторого взвешивания гипотезы) — это слабая форма гипотезы приверженности. Вместо того, чтобы придерживаться одной гипотезы, мы распространяем нашу приверженность на многих. Наша граница обобщения верна до тех пор, пока она выполняется независимо от обучающих выборок. Точно так же, как выбор отдельных гипотез для оценки выборкой может быть произвольным, выбор языка описания также произволен.

7.4 Другие концепции обучаемости — последовательность

Позволяя требуемому размеру выборки зависеть не только от$\эпсилон, \дельта, ч$, но также зависит от генеративного распределения вероятностей$\mathcal D$Базовые данные (используемые для создания обучающих выборок и определения риска) могут еще больше ослабить концепцию обучаемости. Этот тип гарантии производительности достигается путем изучения последовательного понятия правил.

Определение 7.8 (Непротиворечивость)

Предполагать$Z$это набор доменов,$P$да$Z$Набор распределений вероятностей на$\mathcal H$является гипотетическим классом. если есть функция$m _ {\ mathcal H} ^ {CON}: (0,1) ^ 2 \ times \ mathcal H \ times P \ to \ mathbb N$, то правило обучения$A$и$H$и$P$последовательно, для каждого$\эпсилон, \дельта \in(0,1)$, каждый$h\in H$,все$\mathcal D \in P$, если$m\ge m^{NUL}_{\mathcal H}(\epsilon,\delta,h,\mathcal D)$, то вероятность не менее$1−\дельта$о$S\sim \mathcal D^m$выбор, он считает

если$P$это множество всех дистрибутивов$^2$,мы говорим$A$за$H$в целом соответствует.

Конечно, понятие согласованности является ослаблением нашего предыдущего понятия неравномерной обучаемости. Очевидно, что если алгоритм изучает класс неравномерно$\mathcal H$, что также в целом соответствует этому классу. Релаксация является строгой, потому что существуют последовательные правила обучения, которые не успешны для неконформных учащихся. Например, алгоритм Память, определенный в Примере 7.4 позже.$\mathbb N$согласуется для всех классов бинарного классификатора на . Однако, как мы обсуждали ранее, этот класс не является неравномерно обучаемым.

Пример 7.4

Рассмотрим память алгоритма прогнозирования классификации, определенную следующим образом. Алгоритм хранит обучающие примеры, и в заданной контрольной точке$x$В случае предсказания всех меток, присутствующих в обучающей выборке$x$Метка большинства в экземпляре (если отсутствует в обучающем наборе$x$например, предсказать некоторые фиксированные метки по умолчанию). Можно показать (см. упражнение 6), что для любого счетного поля$X$и ограниченный набор этикеток$Y$(Говоря о потере «ноль-один»), алгоритм памяти в целом непротиворечив.
Интуитивно не очевидно, следует ли считать алгоритм памяти обучаемым, потому что ему не хватает аспекта обобщения, то есть использования наблюдаемых данных для предсказания меток для невидимых примеров. Тот факт, что память является непротиворечивым алгоритмом для всех классов функций в любом наборе счетных полей, ставит под вопрос полезность гарантий непротиворечивости. Кроме того, внимательные читатели могут заметить, что мы$2$«Плохие ученики», которые приводят к переобучению, представленные в главе, на самом деле являются алгоритмами памяти. В следующем разделе мы обсудим значение различных концепций обучаемости и вернемся к теореме о бесплатном обеде с точки зрения различных определений обучаемости.

---

1. В литературе непротиворечивость часто определяется с использованием понятия вероятностной сходимости (соответствующей слабой непротиворечивости) или почти достоверной сходимости (соответствующей сильной непротиворечивости).
2. В общем случае мы предполагаем, что Z задано некоторое подмножество сигма-алгебры Ω, и под «всеми распределениями» мы понимаем все распределения, для которых Ω включено в связанное с ними семейство измеримых подмножеств.

7.5 Обсудите различные концепции обучаемости

Мы дали три определения обучаемости и теперь обсудим их полезность. Часто полезность математического определения зависит от того, для чего оно нам нужно. Поэтому мы перечисляем несколько возможных целей, которых можно достичь, определяя обучаемость, и обсуждаем полезность различных определений в свете этих целей.
Каковы риски усвоенных предположений?
Первая возможная цель получения гарантий производительности для алгоритмов обучения — ограничить риск вывода предикторов. Здесь как обучение PAC, так и неоднородное обучение дают нам верхнюю границу истинного риска эмпирического предположения об обучении, основанном на риске. Гарантии непротиворечивости не дают таких ограничений. Однако набор проверки (как описано в главе 11) всегда можно использовать для оценки риска вывода предиктора.
Сколько примеров нужно для сравнения с$\mathcal H$так же хорошо, как лучшая гипотеза в ?
При решении задачи обучения возникает естественный вопрос: сколько примеров нам нужно собрать, чтобы изучить ее. Здесь PAC Learning дает четкий ответ. Однако для неравномерного обучения и согласованности мы не знаем обучения заранее.$\mathcal H$Сколько примеров нужно. При неравномерном обучении это число зависит от$\mathcal H$Лучшее предположение в последовательности, это также зависит от базового дистрибутива. В этом смысле PAC-обучение — единственное полезное определение обучаемости. С другой стороны, мы должны иметь в виду, что даже если ошибка оценки нашего изученного предиктора мала, если$\mathcal H$При больших ошибках аппроксимации риск также может быть большим. Поэтому даже гарантия PAC не дает нам четкого ответа на вопрос, «сколько примеров нужно, чтобы быть таким же хорошим, как оптимальное значение предсказания Байеса». Это отражает тот факт, что полезность обучения PAC зависит от качества наших предварительных знаний.
Гарантии PAC также могут помочь нам понять, что мы должны делать дальше, если наш алгоритм обучения возвращает очень рискованную гипотезу, потому что мы можем ограничить часть ошибки, вызванной ошибкой оценки, и, таким образом, узнать, какая часть ошибки связана с ошибкой аппроксимации. . Если ошибка аппроксимации велика, мы знаем, что следует использовать другой класс гипотез. Точно так же, если неоднородный алгоритм терпит неудачу, мы можем рассмотреть различные весовые функции (подмножества) предположений. Однако, когда алгоритм консенсуса терпит неудачу, мы не знаем, происходит ли это из-за ошибки оценки или ошибки аппроксимации. Кроме того, даже если мы определим, что существует проблема с членом ошибки оценки, мы не знаем, сколько еще примеров необходимо, чтобы сделать ошибку оценки малой.
Как научиться? Как выразить предварительные знания?
Возможно, наиболее полезным аспектом теории обучения является ответ на вопрос «как учиться». Определение PAC-обучения создает ограничения обучения (через теорему о небесплатном обеде) и необходимость в предварительных знаниях. Это дает нам четкий способ кодирования предшествующих знаний путем выбора класса гипотез, и как только этот выбор сделан, у нас есть общее правило обучения — ERM. Определение неравномерной обучаемости также позволяет определить$\mathcal H$Четкий способ кодирования предшествующих знаний с помощью весов гипотез (подмножеств). Как только этот выбор сделан, у нас снова есть общее правило обучения — SRM. Правила SRM также имеют преимущества в задачах выбора модели, поскольку априорные знания являются частичными. Мы подробно остановились на выборе модели в главе 11, а здесь мы приводим простой пример.
Рассмотрим задачу подбора одномерного многочлена к данным, то есть наша цель — изучить функцию$h:\mathbb R\to\mathbb R$, априори рассмотрим гипотетический класс полиномов. Однако мы можем быть не в состоянии определить, какая степень d даст наилучшие результаты для нашего набора данных:$d$может плохо соответствовать данным (т. е. иметь большие ошибки аппроксимации), в то время как высокая степень$d$Может привести к переоснащению (т.е. будет иметь большую ошибку оценки). Далее мы описываем$2$,$3$и$10$Результат подгонки полинома степени к тому же обучающему набору.

Легко видеть, что эмпирический риск уменьшается с увеличением степени. Следовательно, если мы выберем$H$это все$10$класс полиномов степени, то правило ERM для этого класса будет выводить$10$полиномом степени и будет соответствовать. С другой стороны, если мы выберем гипотетический класс, который слишком мал, например, до$2$полинома степени, ERM будет страдать от недообучения (т. е. больших ошибок аппроксимации). Напротив, мы можем использовать правило SRM для всех наборов многочленов, в то время как$\mathcal H$Порядок подмножеств ранжирует его, что дает кубический полином, поскольку комбинация его эмпирического риска и границы его ошибки оценки является наименьшей. Другими словами, правила SRM позволяют нам выбрать правильную модель на основе самих данных. Цена, которую мы платим за эту гибкость (помимо небольшого увеличения ошибки оценки оптимальности по сравнению с обучением PAC), заключается в том, что мы не знаем заранее, сколько примеров необходимо для соответствия$\mathcal H$Конкурс на лучшую гипотезу в .
В отличие от концепций обучаемости PAC и неравномерной обучаемости, определение согласованности не дает естественной парадигмы обучения или способа кодирования предшествующих знаний. Фактически, во многих случаях никаких предварительных знаний не требуется вообще. Например, мы видим, что даже алгоритмы запоминания (которые интуитивно не следует называть алгоритмами обучения) являются непротиворечивыми алгоритмами для любого класса, определенного над счетным полем и конечным набором меток. Это означает, что согласованность является очень слабым требованием.

Какой алгоритм обучения выбрать?
Кто-то может возразить, что хотя согласованность является более слабым требованием, алгоритмы обучения$\mathcal X$прибыть$\mathcal Y$Все наборы функций для также согласованы, что дает нам гарантию, что для достаточного количества обучающих примеров мы всегда будем такими же хорошими, как байесовский оптимальный предиктор. Следовательно, если у нас есть два алгоритма, один из которых непротиворечивый, а другой непротиворечивый, мы должны выбрать непротиворечивый алгоритм. Однако этот аргумент проблематичен по двум причинам. Во-первых, для большинства «естественных» распределений мы можем наблюдать на практике, что сложность выборки алгоритмов консенсуса настолько велика, что в каждом практическом случае мы не можем получить достаточно выборок, чтобы воспользоваться этой гарантией. Во-вторых, для любого из$\mathcal X$Любому PAC или непоследовательному ученику нетрудно прийти к классу функций Y. В частности, рассмотрим счетные поля$\mathcal X$, ограниченный набор меток$\mathcal Y$и гипотетический класс$\mathcal H$,от$\mathcal X$прибыть$\mathcal Y$Функция. Мы можем использовать следующий простой трюк, чтобы сделать$\mathcal H$любого неоднородного ученика с$\mathcal X$прибыть$\mathcal Y$Классы всех классификаторов согласованы: получив обучающую выборку, мы сначала запустим на обучающей выборке неоднородный обучающий элемент, а затем получим оценку истинного риска обучения предиктора. Если эта граница достаточно мала, мы закончили. В противном случае возвращаемся к алгоритму памяти. Эта простая модификация делает алгоритм$\mathcal X$прибыть$\mathcal Y$одинаковы во всех функциях. Поскольку любой алгоритм легко согласуется, может быть неразумно выбирать один алгоритм вместо другого только из соображений согласованности.

7.5.1 Пересмотр принципа «Нет бесплатного обеда»

Напомним, что теорема об отсутствии бесплатного обеда (теорема 5.1 в главе 5) означает, что ни один алгоритм не может изучить все классы классификаторов над бесконечным полем. Напротив, в этой главе мы видели, что алгоритмы памяти согласуются со всеми классами классификаторов над счетно бесконечными полями. Чтобы понять, почему эти два утверждения не противоречат друг другу, давайте сначала рассмотрим формальное утверждение «теоремы об отсутствии бесплатных обедов».

Предполагать$\mathcal X$счетно бесконечное поле,$\mathcal Y =\{±1\}$. Теорема об отсутствии бесплатных обедов означает: для любого алгоритма$A$и размер тренировочного набора$m$,существует$\mathcal X$распределения и функции на$h^*: \mathcal X\to\mathcal Y$, если вы получите$h^*$Примеры обучающих примеров с помеченными IID$m$,Потом$A$Может вернуть классификатор с большей ошибкой.

Непротиворечивость памяти означает: для$\mathcal X$каждое распределение и функция маркировки на$h^*: \mathcal X\to\mathcal Y$, есть размер$m$обучающая выборка (в зависимости от распределения и$h^*$), так что если Память получит хотя бы$m$Например, он, скорее всего, вернет классификатор с небольшой ошибкой.

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

7.6 Резюме

Мы вводим неравномерную обучаемость в ослабление обучаемости PAC и согласованность в ослабление неравномерной обучаемости. Это означает, что даже классы бесконечномерных VC могут быть изучены в несколько более слабом смысле обучаемости. Мы обсудим полезность различных определений обучаемости.
Для класса счетных гипотез можно применить схему минимальной длины описания, где предпочтение отдается гипотезам с более короткими описаниями по принципу бритвы Оккама. Интересным примером является гипотетический класс всех предикторов, которые мы можем реализовать на C++ (или любом другом языке программирования), которые мы можем изучить (неоднородно), используя схему MDL.
Все предикторы, которые мы можем реализовать на C++, представляют собой один мощный класс и, вероятно, содержат все, что мы хотим изучить на практике. Возможность пройти курс впечатляет, и кажется, что эта глава должна быть последней в книге. Это не так из-за вычислительного аспекта обучения: времени выполнения, необходимого для применения изученных правил. Например, чтобы реализовать парадигму MDL для всех программ на C++, нам нужно выполнить полный поиск по всем программам на C++, который будет продолжаться вечно. даже во всех$1000$При реализации всех программ на C++ с длиной описания 2 бита парадигма ERM требует$2^{1000}$исчерпывающий поиск гипотез. В то время как примерная сложность изучения класса составляет всего$\frac{1000+log(2/\delta)}{\epsilon^2}$, но время выполнения$\le 2^{1000}$Это огромное число — намного больше, чем количество атомов в видимой Вселенной. В следующей главе мы формально определим вычислительную сложность обучения. Во второй части этой книги мы рассмотрим гипотетические классы, которые могут эффективно реализовать схему ERM или SRM.

7.7 Библиографические примечания

Наше определение неравномерной обучаемости связано с определением алгоритма OCCAM в Blumer, Ehrenfeucht, Haussler & Warmuth (1987). Концепция SRM возникла из (Вапник, Червоненкис, 1974, Вапник, 1995). Концепция MDL возникла благодаря (Rissanen 1978, Rissanen 1983). Вапник (1995) обсуждает взаимосвязь между SRM и MDL. Эти понятия также тесно связаны с понятием регуляризации (например, Тихонов (1943)).
Мы подробно рассмотрим регуляризацию во второй части книги. Концепция согласованности оценок восходит к Фишеру (1922). Наше введение в непротиворечивость следует за Steinwart & Christmann (2008), которые также вывели несколько теорем о том, что бесплатный обед невозможен.

7.8 Упражнения

1. доказать, что для любого конечного класса$\mathcal H$и любой язык описания$д:Н\к\{0,1\}^*$, $\mathcal H$Размерность VC не более$2sup\{|d(h)| :h\in \mathcal H\}$– Максимальная длина описания предиктора в единицах$\mathcal H$. Кроме того, если$d$является описанием без префикса, то$VCdim(H)\le sup\{|d(h)| :h\in \mathcal H\}$.
2. Предполагать$\mathcal H=\{h_n:n\in \mathbb N\}$— бесконечно счетный гипотетический класс для бинарной классификации. показать, что невозможно$\mathcal H$— бесконечно счетный гипотетический класс для бинарной классификации. показать, что это невозможно$\mathcal H$Гипотезы присваивают веса, а гипотезы присваивают веса, таким образом

• Используйте эти веса, чтобы учиться неравномерно$\mathcal H$. То есть весовая функция$w:\mathcal H\to [0,1]$должны быть соблюдены условия$\sum_{h\in \mathcal H}w(h)\le 1$.
• Веса будут монотонно инвариантны. То есть, если$i<j$,Так$w(h_i)\le w(h_j)$

3. • Рассмотрим гипотетический класс$\mathcal H= \bigcup_{n=1}^\infty$, где каждый$n\in \mathbb N$,$\mathcal H_n$ограничено. Найдите весовую функцию$w:\mathcal H\to[0,1]$так$\sum_{h\in\mathcal H}w(h)\le 1$Поэтому для всех$h\in\mathcal H$,$w(h)$Зависит от$n(h)=min\{n:h\in\mathcal H_n\}$и$|\mathcal H_{n(h)}|$Конечно.

• (*) определить такую ​​функцию$w$, когда все$\mathcal H_n$счетно (возможно, бесконечно).

4. Предполагать$\mathcal H$для гипотетического класса. для любого$h\in\mathcal H$, согласно фиксированному языку описания, установить$| H |$выражать$\mathcal H$длина описания. Рассмотрим парадигму обучения MDL, в которой алгоритм возвращает:

в$S$размер$m$образец. для любого$B>0$,Предполагать$\mathcal H_B={h\in\mathcal H:|h|\le B}$и определить

доказывать$L_D(h_S)−L_D(h^∗_B)$A граница B, параметр доверия$\delta$и тренировочный набор$m$размер.

• Примечание. Эта граница известна в литературе как неравенство оракула: мы хотим оценить нашу связь с эталонным классификатором (или «оракулом»).$ч ^ * _ B$как хорошо по сравнению с

5. В этой задаче мы хотим показать результат небесплатного обеда для неравномерной обучаемости: т. Е. В любом бесконечном поле класс всех функций не поддается обучению даже при ослабленных неоднородных вариантах обучения.

Напомним, что если существует функция$m^{NUL}_\mathcal H:(0,1)^2\times\mathcal H\to\mathbb N$, то алгоритм$A$Изучение классов гипотез неравномерно$\mathcal H$, для каждого$\эпсилон, \дельта\в (0,1)$и для всех$h\in\mathcal H$, если$m≥ m^{NUL}_\mathcal H(\epsilon, \delta, \mathcal H)$, то для каждого распределения$\mathcal D$, с вероятностью не менее$1− \дельта$о$S\sim D^m$выбор, он считает

Если такой алгоритм существует, то говорят$\mathcal H$является неравномерно обучаемым.

1. позволять$A$стать$\mathcal H$класс неоднородных учащихся. для каждого$n\in\mathbb N$определение$\mathcal H^A_n=\{h\in\mathcal H:m^{NUL}(0.1,0.1,\mathcal H)\le n\}$. доказать каждый класс$\mathcal H_n$Все размеры VC ограничены.
2. доказать, что если класс$\mathcal H$неравномерно обучаема, то существует класс$\mathcal H_n$, так что$\mathcal H=\bigcup _{n\in\mathbb N} \mathcal H_n$, для всех$n\in\mathbb N$, VCdim$(\mathcal H_n)$ограничено.
3. Предполагать$\mathcal H$— класс, разбивающий бесконечные множества. Затем для каждой последовательности классов$(\mathcal H_n:n\in\mathbb N)$сделать$\mathcal H=\bigcup _{n\in\mathbb N} \mathcal H_n$, есть некоторые$n$Для VCdim$(\mathcal H_n)=\infty$.

Подсказка: задан класс$\mathcal H$, он разбивает некоторые бесконечные множества$K$, и серия занятий$(\mathcal H_n:n\in\mathbb N)$, каждый с конечной размерностью VC, из определяющих подмножеств$K_n\subseteq K$начать, для всех$n$,$|K_n|>VCdim(\mathcal H_n)$, для любого$n\neq m$,$K_n\cap K_m=\empty$, Теперь для каждого такого$Kn$выбрать функцию$f_n:K_n\to \{0,1\}$тогда нет$h\in\mathcal H_n$с доменом$K_n$Вверх$f_n$Последовательный. Наконец, определите$f:X\to\{0,1\}$путем объединения этих$f_n$и доказать$f\in(\mathcal H\setminus \bigcup_{n\in\mathbb N}\mathcal H_n)$.
4. Построить интервал из единицы$[0,1]$прибыть$\{0,1\}$класс функций$\mathcal H_1$, который является неоднородным обучаемым, но не обучаемым PAC.
5. Построить подчиненный интервал$[0,1]$прибыть$\{0,1\}$функция класса$H_2$, он не является неравномерно обучаемым.
6. В этой задаче мы хотим показать, что алгоритм Память является последовательным обучаемым для каждого класса (бинарных) функций над любым счетным полем. Предполагать$\mathcal X$счетное поле,$\mathcal D$за$\mathcal X$распределение вероятностей на .

1. Предполагать$\{x_i:i\in\mathbb N\}$да$\mathcal X$перечисление элементов, поэтому для всех$i\le j$,$\mathcal D(\{x_i\})\le \mathcal D(\{x_j\})$. доказывать

2. дать любой$\epsilon>0$доказать существование$\epsilon_D>0$,тем самым

3. доказательство для всех$\eta > 0$,если$n$для всех$i>n$да$D(\{x_i\})<\eta$, то для всех$m\in\mathbb N$,

4. сделать вывод, что если$\mathcal X$счетно, то для$\mathcal X$Каждое распределение вероятностей на$\mathcal D$, есть функция$m_\mathcal D:(0,1)\times(0,1)\to\mathbb N$затем для каждого$\epsilon,\delta >0$если$m>m_\mathcal D(\epsilon,\delta)$,

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