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

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

Предполагать $H$ представляет собой конечное множество гипотез. Тогда для любого $δ>0$ , с вероятностью не менее $1−δ$ , имеет место следующее неравенство:

\forall h\in H,R(h)\le \widehat R(r)+\sqrt {\frac{log|H|+log\frac{2}{δ}}{2m}}.(2.20)

доказыватьПредполагать $ч_1, …, ч_{|ч|}$ за $H$ Элементы. Использование совместной границы и применение следствия 2.2 к каждой гипотезе дает:

\begin{aligned} &Pr\Big[h\in H|\widehat R(h)-R(h)|>\epsilon \Big]\\ &=Pr\Big[(|\widehat R(h_1)-R(h_1)|>\epsilon)\vee...\vee (|\widehat R(h_{|H|})-R(h_{|H|})|>\epsilon)\Big]\\ &\le\sum_{h\in H}Pr[|\widehat R(h)-R(h)|>\epsilon]\\ &\le 2|H|exp(-2m\epsilon^2). \end{aligned}

приравнять правую часть к $δ$ завершить проверку

Следовательно, для конечного набора гипотез $H$ ,

R(h)\le\widehat R(h)+O\bigg(\sqrt\frac{log_2|H|}{m}\bigg).

Как упоминалось ранее, $log_2 | H |$ можно интерпретировать как означающее $H$ необходимое количество цифр. Здесь можно сделать что-то похожее на комментарии, сделанные по поводу границ обобщения в непротиворечивом случае: больший размер выборки $m$ гарантирует лучшее обобщение, и оценка возрастает с $|H|$ увеличивается с ростом, но только логарифмически. Однако предел здесь $\frac{log2 |H|}{m}$ Менее благоприятная функция , она зависит от квадратного корня члена. Это не маленькая цена: за фиксированную $|H|$ , для получения тех же гарантий, что и в согласованном случае, требуются квадратично большие помеченные выборки.

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

2.4 Введение

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

2.4.1 Детерминированные и стохастические сценарии

В самом общем сценарии обучения с учителем распределение $D$ определено в $X×Y$ выше данные обучения представляют собой $D$ Образцы, отмеченные i.i.d. $S$ :

S=((x_1,y_1),... ,(x_m,y_m)).

Задача обучения состоит в том, чтобы найти гипотезу с малой ошибкой обобщения. $h∈H$ ,

R(h)=\underset {(x,y)\sim D}{Pr}[h(x)\neq y]=\underset {(x,y)\sim D}{E}[1_{h(x)\neq y}].

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