2 Структура обучения PAC (стр. 17-18)

2.2 Гарантии для конечного набора допущений — непротиворечивый случай

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

Теорема 2.1. Граница обучения — конечный H, непротиворечивый случай

Предполагать $H$ От $X$ прибыть $Y$ Конечный набор функций для карты. Предполагать $A$ это алгоритм для любого целевого понятия $с е Н$ и образцы iid $S$ Возвращает последовательную гипотезу $h_S: \широкая шляпа R(h_S) = 0$ . Тогда для любого $\epsilon,δ > 0$ , неравенство $\ underset {S ∼ D_m} {Pr} [R (h_S) ≤ \ эпсилон] ≥ 1−δ$ установлено, если

m\ge\frac{1}{\epsilon}\bigg(log|H|+log\frac{1}{δ}\bigg).(2.8)

Этот образец результата сложности допускает следующие эквивалентные утверждения в качестве границ обобщения: $\эпсилон, δ > 0$ , с вероятностью не менее 1 − δ,

R(h_s)\leq \frac{1}{m}\bigg(log|H|+log\frac{1}{δ}\bigg).(2.9)

доказыватьфиксированный $\epsilon>0$ , мы не знаем, какая консенсусная гипотеза была выбрана алгоритмом A $h_S ∈ H$ . Это предположение также зависит от обучающих выборок. $S$ . Следовательно, нам нужно дать непротиворечивую границу сходимости, которая справедлива для множества всех непротиворечивых гипотез, которые, что более важно, включают $h_S$ . Поэтому мы ограничим некоторые $ч е Н$ Непротиворечивый и ошибка больше, чем $\epsilon$ Вероятность:

\begin{align} & \quad Pr[\exists h\in H:\widehat R(h)=0\land R(h)>\epsilon]\\ &=Pr[(h_1\in H,\widehat R (h_1)=0\land R(h_1)>\epsilon)\lor (h_2\in H,\widehat R(h_2)=0\land R(h_2)>\epsilon)\lor ...]\\ & \le \sum_{h\in H}Pr[\widehat R(h)=0\land R(h)>\epsilon] \quad\quad\quad\quad\quad\quad(совместное ограничение)\\ &\ le \sum_{h\in H}Pr[\widehat R(h)=0 | R(h)>\epsilon]\quad\quad\quad\quad\quad\quad\quad(определение условной вероятности) \end {выровнено}

Теперь рассмотрим любую гипотезу $h\in H$ ,в $R(h)>\epsilon$ .Потом, $h$ Вероятности обучающих выборок, взятых в i.i.d. $S$ согласуется с вышеизложенным, т. е. находится в $S$ В любой точке нет ошибки, и границы могут быть определены как:

Pr[\widehat R(h)=0|R(h)>\epsilon]\le(1-\epsilon)^m.

Предыдущее неравенство означает, что

Pr[\exists h\in H:\widehat R(h)=0\land R(h)>\epsilon]\le |H|(1-\epsilon)^m.

Установите правую часть равной δ и найдите ε, чтобы получить доказательство.

Теорема утверждает, что когда множество гипотез $H$ Конечное время, алгоритм консенсуса $A$ является алгоритмом обучения PAC, поскольку сложность выборки, заданная (2.8), определяется выражением $1/\epsilon$ и $1/δ$ полиномиальное доминирование в . Как показано в (2.9), верхняя граница ошибки обобщения непротиворечивого предположения определяется размером выборки $m$ условия, которые уменьшаются в зависимости от . Это общий факт: как и ожидалось, алгоритмы обучения выигрывают от больших помеченных обучающих выборок. Однако, гарантированный теоремой $O(1/m)$ Скорость снижения особенно благоприятна.
Стоимость разработки алгоритма консенсуса заключается в использовании большего набора гипотез, содержащего целевую концепцию. $H$ . Конечно, верхний предел (2.9) при $|H|$ и увеличить. Однако эта зависимость является только логарифмической. Обратите внимание на терминологию $log |H|$ , или родственный термин $log_2 |H|$ отличается от него постоянным множителем, который можно интерпретировать как представляющий $H$ необходимое количество цифр. Следовательно, обобщение теоремы гарантируется отношением числа битов, $log_2 |H|$ и размер выборки $m$ контроль.