Что означает теория обучения PAC?

Я новичок в машинном обучении. Я изучаю курс машинного обучения (Стэнфордский университет), и я не понял, что подразумевается под этой теорией и в чем ее польза. Мне интересно, может ли кто-нибудь описать эту теорию для меня.

Эта теория основана на этом уравнении.

Вероятно, приблизительно правильная (PAC) теория обучения помогает проанализировать, будет ли ученик и при каких условиях выводить приблизительно правильный классификатор. (Вы увидите, что некоторые источники используют букву А вместо буквы Л. )$L$$A$$L$

Во-первых, давайте определим «приблизительный». Гипотеза является приблизительно верной, если ее погрешность в распределении входов ограничена некоторыми ϵ , 0 ≤ ϵ ≤ $h \in H$Т.е.,етготД(ч)<ε, гдеDпредставляет собой распределение по входам.$\epsilon, 0 \le \epsilon \le \frac{1}{2}.$$error_D(h)\lt \epsilon$$D$

Далее «наверное». Если выведет такой классификатор с вероятностью 1 - δ , с 0 ≤ δ ≤ $L$$1 - \delta$ , мы называем этот классификатор,вероятно,приблизительно правильным.$0 \le \delta \le \frac{1}{2}$

Знание того, что целевая концепция может быть изучена PAC, позволяет вам ограничить размер выборки, необходимый для того, чтобы, вероятно, выучить приблизительно правильный классификатор, как показано в приведенной вами формуле:

Чтобы получить некоторое представление об этом, обратите внимание на влияние на при изменении переменных в правой части. При уменьшении допустимой ошибки необходимый размер выборки увеличивается. Кроме того, он растет с вероятностью приблизительно правильного ученика, и с размером гипотезы пространства H . (Скорее всего, пространство гипотез - это набор классификаторов, которые рассматривает ваш алгоритм.) Более просто, поскольку вы рассматриваете больше возможных классификаторов или хотите меньшую ошибку или более высокую вероятность правильности, вам нужно больше данных, чтобы различать их.$m$$H$

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

$(x_i, y_i)$$x_i$$y_i$$\tilde{x}$$\tilde{y}$
скажем, хотя 1000000 Если бы вам дали последовательность 1, 2, 3, ... 999 999, можно было бы быть уверенным, что следующее число - 1 000 000. Однако следующее число может быть 999 999,5 или даже 5. Дело в том, что чем больше данных вы видите, тем больше уверенность в том, что вы создали точную модель, но никогда не можете быть абсолютно уверены.

$x_i, 1 \leq i \leq m$$y_i$$f_{\theta}$$f_{\Theta}$$p >1-\delta$$f_{\Theta}$$\epsilon$$(\delta,\epsilon)$$(\delta,\epsilon)$ и насколько сложен данный класс гипотез.

$\mathcal{H}$$f_{\theta}$$(\epsilon, \delta)$$0 < \epsilon,\delta , <.5$$f_{\Theta}$$\tilde{x}, \tilde{y}$$Err(f_{\Theta}(\tilde{x}) ,\tilde{y} ) < \epsilon$$p > 1-\delta$$m = m(\delta,\epsilon,\mathcal{H})$$(f_{\Theta}(\tilde{x}) -\tilde{y})^2$

$(\delta,\epsilon)$