Обучение ML — PAC Learning

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

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

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

Прежде чем углубляться в детали, сначала давайте посмотрим на представление / терминологию, которые мы собираемся использовать для представления инфраструктуры PAC.

c —Концепция/функции, где X -> Y, поскольку Y = {0,1}, X -> {0,1}
C —Класс концепции ( набор понятий/функций для изучения)
H —Гипотеза( множество понятий, которые могут не совпадать с C)
D —Распределение данных (рассматривается здесь идентичные независимо распределенные)
S —Выборка из H
hS — Гипотеза для S Sample
ε — Параметр точности
δ —Параметр достоверности

Обучение ПКК

Класс C называется PAC-обучаемым, если гипотеза (H), возвращенная после применения алгоритма (A) к числу выборок (N), считается приблизительно правильной, если она дает частоту ошибок меньше ε и вероятность не менее 1 - δ (где N – многочлен, а N – функция от 1/ε, 1/δ) . Комбинация вероятности и члена приблизительно в уравнении приводит к термину PAC — Вероятно, приблизительно правильно.
* Pr [(hs)≤ ε] ≥ 1 − δ

Здесь делается предположение, что (ε, δ) › 0, а гипотеза H конечна. Такой алгоритм/классификатор, который дает нам не менее 1 − δ вероятности, будет называться приблизительно правильным в изучении признаков/понятий.

Кроме того, если алгоритм A требует полиномиального времени при выполнении (в виде 1/ε, 1/δ), то C называется эффективно обучаемым PAC. Здесь мы ищем более обобщенное обучение (с меньшей ошибкой обобщения), а не запоминание понятий/признаков алгоритмом.

Ошибка обобщения — Мы находим вероятностьH(гипотеза) иC(класс концепции) так, что для случайных случаев, где h(x) != c(x) будет ошибкой обобщения, поскольку мы предполагаем, что они оба разные, или мы можем сказать, что они не перекрываются (пересекающиеся точки данных), и это будет наша истинная ошибка.
* Pr [h(x)!= c(x)]

Сложность выборки. Используя PAC, мы также можем найти количество выборок, что даст нам более высокую вероятность, здесь мы предполагаем, чтоCявляется обучаемым PAC. Таким образом, если мы находим гипотезу с вероятностью не менее1 − δ(высокая вероятность), то количество выборок, необходимых для обучения такой гипотезы, можно определить как
> N = 1/ε (ln|H|+ln|δ| )

Что, если гипотеза H бесконечна?

Предыдущая концепция, которую мы видели, будет верна для конечной гипотезы, но если гипотеза бесконечна, мы должны искать варианты того, как мы можем разделить гипотезу, расщепление гипотезы называется разрушением.

Чтобы сделать процесс более понятным, существует термин VC Dim или VC dim, который определяет наибольшее множество точек, которые могут быть разбиты алгоритмом.
Мы также можем сказать,
* VC = 2^k , где k — множество точек

Допустим, размерность VC равна d для выборки S, которая содержит набор точек d, которые можно разбить, но для d+ 1 нет множества точек, которые нужно разбить. Как? Давайте посмотрим на пример

Рассмотрим граф (а), где есть два набора T, F (d точек), которые разбиваются на два с помощью оси. Аналогичным образом можно выбрать любую другую ось.

Рассмотрим граф (b), где есть два набора F, T (d точек), которые разбиваются на два с помощью оси. Аналогичным образом можно выбрать любую другую ось.

Рассмотрим граф (а), где есть 4 точки множества — T,T,T, F(d+1 точка). Как мы можем разбить его, любой линия, которую мы выбираем, будет пересекать точку F, которая не является идеальным разделением, поэтому (а) график не может быть разрушен.

Рассмотрим граф (b), где есть 3 точки множества — T,T, F (d+1 точка). Этот график можно легко разделить с помощью линии.

В приведенных выше примерах мы видели, что если есть набор точек ≤ 3, его можно легко разделить, но если набор точек ≥4 (d + 1 балл), его нельзя разделить идеально.
Итак, последний набор точек которые могут быть разделены или разбиваются, - это размер VC ‹4.

Мы подошли к концу блога… В этом блоге мы получили представление об обучении PAC для конечных гипотез и VC dim для бесконечных гипотез. В следующем блоге я подниму еще одну интересную тему в области ИИ, а пока оставайтесь техновенторами :)

Ссылка -
https://www.youtube.com/watch?v=X4Oxst5huQA&t=909s
https://www.slideshare.net/sanghyukchun/pac -learning-42139787
Книга — Основы машинного обучения