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

Определение 2.4 Независимое обучение PAC

Предполагать $H$является набором гипотез. $A$непостижимоеPACалгоритм обучения, если есть полиномиальная функция$poly(·,·,·,·)$сделать для любого$\epsilon > 0$ и $δ > 0$, за$X × Y$Все раздачи на$D$, следующее относится к любому размеру выборки$m ≥ поли(1/\эпсилон, 1/δ, n, размер(с))$:

Если A далее запустить в poly(1/ε, 1/δ, n, size(c)) , то он считается эффективным алгоритмом обучения PAC, не зависящим от него.

Когда метка точки может быть определена некоторой измеримой функцией$ж : Х → Y$(с вероятностью 1), когда он однозначно определен, сценарий называется детерминированным. В этом случае рассмотрим распределение по входному пространству$D$ Будет достаточно. Обучающие выборки получаются$D$рисовать$(x1, . . , xm)$получены и через$f$Получите этикетку:$y_i = f(x_i)$для всех$я ∈ [1,m]$. В этом детерминированном сценарии можно сформулировать многие проблемы обучения.
В предыдущих разделах и в большей части материала, представленного в этой книге, мы для простоты ограничили введение детерминированными сценариями. Однако для всего этого материала расширения для случайных сценариев должны быть понятны читателю.

2.4.2 Байесовская ошибка и шум

В детерминированном случае по определению существует целевая функция f:R(h)=0 без ошибки обобщения. В случайных случаях существует минимальная ненулевая ошибка для любой гипотезы

Определение 2.5 Байесовская ошибка

данный$X×Y$распространение на$D$, байесовская ошибка$Р^*$определяется как измеримая функция$ч: X→Y$Инфимум полученной ошибки:

$R (ч) = R ^ *$Гипотеза h называется байесовской гипотезой или байесовским классификатором.
По определению в детерминированном случае имеем$Р^* = 0$, но в случайных случаях$R^*\neq 0$Очевидно, байесовский классификатор$h_{Bayes}$можно определить в соответствии с условной вероятностью как:

$h_{Bayes}$ существует $х е Х$Средняя ошибка на$min{Pr[0|x], Pr[1|x]}$, что является наименьшей возможной ошибкой. Это приводит к следующему определению шума.

Определение 2.6 Шум

данный $X × Y$распространение на$D$,точка $х е Х$Шум при определяется как

средний шум или$D$Сопутствующий шум$E[noise(x)]$.
Таким образом, средний шум — это просто байесовская ошибка:$noise = E[noise(x)] = R^*$. Шум является характеристикой учебной задачи, указывающей на ее сложность. один пункт $х е Х$, его шум$(x)$около $1/2$, иногда называемый шумом, безусловно, является проблемой для точных прогнозов.