Вычислительная теория обучения привела к нескольким практическим методам:
- PAC (вероятно, примерно правильно) обучение → бустинг
- Теория ВК (Вапника – Червоненкиса) → машины опорных векторов
Бритва Оккама
- Ищите закономерности в наблюдаемом явлении.
- Их можно обобщить от наблюдаемого прошлого к будущему.
- Выберите самую простую непротиворечивую модель.
Нет бесплатного обеда
- Если нет предположений о том, как прошлое связано
с будущим, предсказание невозможно. - Если нет ограничения на возможные явления,
обобщение невозможно.
Вероятно приблизительно правильное (PAC) обучение
Формализм, основанный на осознании того, что лучшее, на что мы можем надеяться, это алгоритм:
- В большинстве случаев он работает хорошо (вероятно, примерно правильно)
Два понятия эффективности:
- Вычислительная сложность. Предпочтите быстро работающий алгоритм
алгоритму, работающему вечно. - Сложность выборки: количество примеров, необходимых вашему
алгоритму для достижения поставленных целей.
Вапник-Червоненкис (ВК) Измерение
- Классическая мера сложности бесконечных классов гипотез
, основанная на этой интуиции. - Измерение VC — это очень ориентированное на классификацию понятие сложности. Идея состоит в том, чтобы рассмотреть конечный набор неразмеченных примеров. Как бы ни были помечены эти точки, сможем ли мы найти гипотезу, которая правильно их классифицирует.
- Идея состоит в том, что по мере того, как вы добавляете больше точек, возможность
представлять произвольную маркировку становится все труднее и труднее.
Сколько точек может точно классифицировать линейная граница? (1D)
Сколько точек может точно классифицировать линейная граница? (2D)
Рекомендации
[1] В основном адаптировано из https://web.cs.hacettepe.edu.tr/~erkut/ain311.f22/slides/l6-colt-basic_probability.pdf
