2 Структура обучения PAC (стр. 21 22)

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

В самом общем случае в H могут отсутствовать допущения, согласующиеся с размеченными обучающими выборками. На самом деле это типичный случай на практике, когда проблема обучения может быть несколько сложной, или концептуальная аналогия более сложна, чем набор допущений, используемых алгоритмом обучения. Однако противоречивые предположения с небольшим количеством ошибок на обучающих выборках могут быть полезны и, как мы увидим, могут выиграть от благоприятных гарантий при определенных предположениях. Этот раздел предоставляет гарантии обучения для этого противоречивого случая и ограниченного набора предположений. Чтобы получить гарантии обучения в этой более общей ситуации, мы будем использоватьHoeffdingНеравенство (теорема D.1) или следующее следствие, которое включает ошибку обобщения и эмпирическую ошибку для одной гипотезы.

Вывод 2.1

фиксированный $\epsilon > 0$ и разреши $S$ Представляет размер i.i.d. $m$ образец. Тогда для любой гипотезы $ч: Х → \{0,1\}$ , имеет место следующее неравенство:

\begin{aligned} \underset {S\sim D^m}{Pr}[\widehat R(h)-R(h)\ge\epsilon]&\le exp(-2m\epsilon ^2)(2.14)\\ \underset {S\sim D^m}{Pr}[\widehat R(h)-R(h)\le -\epsilon]&\le exp(-2m\epsilon ^2).(2.15)\\ \end{aligned}

Согласно границе объединения это означает следующее двустороннее неравенство:

\underset {S\sim D^m}{Pr}[\widehat R(h)-R(h)\ge\epsilon]\le 2exp(-2m\epsilon ^2).(2.16)

доказыватьРезультат точно следует теореме D.1. Положим правую часть (2.16) равной $δ$ и решить $\epsilon$ Немедленно дает следующие оценки для одной гипотезы.

Следствие 2.2. Границы обобщения — единственная гипотеза.

исправить предположение $ч: Х → \{0,1\}$ . Тогда для любого $δ > 0$ , вероятность выполнения следующего неравенства не менее $1 - δ$ :

R(h)\le \widehat R(h)+\sqrt{\frac{log\frac{2}{δ}}{2m}}.(2.17)

Следующий пример иллюстрирует этот вывод на простом примере.

Пример 2.6 Подбрасывание монеты

Представьте, что вы подбрасываете необъективную монету, вероятность выпадения орла равна $p$ , пусть наша гипотеза будет той, которая всегда угадывает положительные. Тогда истинная частота ошибок равна $R(h) = p$ и эмпирическая частота ошибок $\widehat R(h)=\widehat p$ ,в $\widehat p$ — лобовая вероятность, основанная на обучающих выборках, составленных i.i.d. Следовательно, следствие 2.2 принимает по крайней мере $1 - δ$ гарантия вероятности.

|p-\widehat p|\le\sqrt{\frac{log\frac{2}{δ}}{2m}}.(2.18)

Следовательно, если мы выберем $δ = 0.02$ и используйте размер $500$ Выборка , с вероятностью не менее $98\%$ ,но $\widehat p$ Гарантируются следующие приблизительные качества:

|p-\widehat p|\le\sqrt{\frac{log(10)}{1000}}\approx 0.048.(2.19)

когда в образце $S$ Можем ли мы легко применить вывод 2.2, чтобы ограничить гипотезы, возвращаемые алгоритмом обучения при обучении на $h_s$ ошибка обобщения? нет потому что $h_s$ Не фиксированное предположение, а случайная величина, зависящая от выбранных обучающих выборок. Отметим также, что, в отличие от фиксированной гипотезы, для фиксированной гипотезы ожидаемое значение эмпирической ошибки равно ошибке обобщения (уравнение 2.3), ошибка обобщения $Р(ч_С)$ является случайной величиной, обычно отличной от ожидаемого значения $E[\widehat R(h_S)]$ , последняя является константой. Поэтому, как и при доказательстве в непротиворечивом случае, нам нужно получить непротиворечивую оценку сходимости, которая является a для всех предположений $h∈H$ Существуют границы с высокой вероятностью установления.