Оглавление
Изучение Оккама
-
Определение и свойства алгоритма Оккама
- Алгоритм Оккама – это алгоритм, который выводит гипотезу, наиболее близкую к истинной концепции.
- Алгоритм использует обучающие примеры для определения гипотезы, которая минимизирует количество бит, необходимых для ее представления.
- Алгоритм является обобщением алгоритма обучения с учителем, который использует обучающие примеры для обучения гипотезам.
-
Теоремы обучения Оккама и PAC
- Обучение Оккама эквивалентно обучению с учителем в классе концепций, которые являются полиномиально замкнутыми в списках исключений.
- Теорема о мощности утверждает, что алгоритм Оккама может вывести непротиворечивую гипотезу с вероятностью не менее 1-δ.
- Теорема об изучении Оккама подразумевает теорему PAC, но не обязательно обратное.
-
Доказательство эквивалентности
- Доказательство основано на определении ошибки отображения стиля и вероятности согласованности набора выборок с гипотезой.
- Для доказательства используется вторая теорема, которая утверждает, что вероятность согласованности набора выборок с гипотезой ограничена.
-
Применение к задачам обучения
- Алгоритмы Оккама могут быть использованы для получения более строгих оценок сложности типовых задач, включая конъюнкции и списки решений.
-
Расширения и приложения
- Алгоритмы Оккама эффективны при наличии ошибок, вероятностных концепций и в функциональном обучении.
-
Рекомендации для дальнейшего чтения
- Статья Блюмера и др. содержит более подробное обсуждение обучаемости и аспекта Вапника-Червоненкиса.