Нежное введение в теорию вычислительного обучения

Теория вычислительного обучения или статистическая теория обучения относятся к математическим основам для количественной оценки задач и алгоритмов обучения.

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

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

Прочитав этот пост, вы узнаете:

• Теория вычислительного обучения использует формальные методы для изучения задач обучения и алгоритмов обучения.
• Обучение PAC позволяет количественно оценить вычислительную сложность задачи машинного обучения.
• VC Dimension предоставляет способ количественной оценки вычислительной мощности алгоритма машинного обучения.

Начните свой проект с моей новой книги «Вероятность для машинного обучения», включающей пошаговые руководства и файлы исходного кода Python для всех примеры.

Давайте начнем.

Обзор руководства

Этот урок разделен на три части; они есть:

1. Теория вычислительного обучения
2. PAC Learning (Теория проблем обучения)
3. VC Dimension (Теория алгоритмов обучения)

Теория вычислительного обучения

Теория вычислительного обучения, или сокращенно CoLT, — это область исследования, связанная с использованием формальных математических методов, применяемых к обучающимся системам.

Он стремится использовать инструменты теоретической информатики для количественной оценки проблем обучения. Сюда входит характеристика трудности обучения конкретным задачам.

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

• Теория вычислительного обучения (CoLT): формальное изучение задач обучения.
• Статистическая теория обучения (SLT): формальное исследование алгоритмов обучения.

Такое разделение задач обучения и алгоритмов обучения является произвольным, и на практике эти две области во многом совпадают.

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

- Страница 210, Машинное обучение: вероятностная перспектива, 2012.

В современном использовании их можно считать синонимами.

… теоретическая основа, известная как теория вычислительного обучения, которую также иногда называют статистической теорией обучения.

- Страница 344, Распознавание образов и машинное обучение, 2006.

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

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

- Страница 713, Искусственный интеллект: современный подход, 3-е издание, 2009 г.

Вопросы, изучаемые в теории вычислительного обучения, могут включать:

• Как мы узнаем, что модель имеет хорошее приближение целевой функции?
• Какое пространство гипотез следует использовать?
• Как мы узнаем, есть ли у нас хорошее решение на местном или глобальном уровне?
• Как избежать переобучения?
• Сколько примеров данных необходимо?

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

Существует множество подобластей исследования, хотя, пожалуй, двумя наиболее широко обсуждаемыми областями исследования теории вычислительного обучения являются:

• Обучение ПКК.
• ВК Измерение.

Вкратце, мы можем сказать, что PAC Learning — это теория проблем машинного обучения, а измерение VC — это теория алгоритмов машинного обучения.

Вы можете столкнуться с этими темами как практик, и полезно иметь краткое представление о том, о чем они. Давайте подробнее рассмотрим каждый.

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

• Введение в теорию вычислительного обучения, 1994.

PAC Learning (Теория проблем обучения)

Вероятно приблизительно правильное обучение, или PAC-обучение, относится к теоретической структуре машинного обучения, разработанной Лесли Валиант.

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

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

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

Дополнительную информацию об использовании «гипотезы» в машинном обучении для обозначения подходящей модели см. в руководстве:

• Что такое гипотеза в машинном обучении?

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

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

Основополагающий принцип заключается в том, что любая серьезно ошибочная гипотеза почти наверняка будет «обнаружена» с высокой вероятностью после небольшого количества примеров, поскольку она будет давать неправильный прогноз. Таким образом, любая гипотеза, согласующаяся с достаточно большим набором обучающих примеров, вряд ли будет серьезно ошибочной: то есть TELY, вероятно, должна быть приблизительно правильной.

- Страница 714, Искусственный интеллект: современный подход, 3-е издание, 2009 г.

Этот вероятностный язык дал теореме название: «вероятность приблизительно правильная». То есть гипотеза стремится «приблизить» целевую функцию и является «вероятно» хорошей, если она имеет низкую ошибку обобщения.

Алгоритм обучения PAC относится к алгоритму, который возвращает гипотезу, которая является PAC.

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

Цель структуры PAC — понять, насколько большим должен быть набор данных, чтобы обеспечить хорошее обобщение. Это также дает границы вычислительных затрат на обучение…

- Страница 344, Распознавание образов и машинное обучение, 2006.

Кроме того, пространство гипотез (алгоритм машинного обучения) эффективно в рамках PAC, если алгоритм может найти гипотезу PAC (подходящую модель) за полиномиальное время.

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

- Страница 210, Машинное обучение: вероятностная перспектива, 2012.

Дополнительную информацию об обучении PAC можно найти в основополагающей книге по этой теме под названием:

• Вероятно, приблизительно верно: Природные алгоритмы обучения и процветания в сложном мире, 2013.

VC Dimension (Теория алгоритмов обучения)

Теория Вапника-Червоненкиса, или сокращенно теория VC, относится к теоретической структуре машинного обучения, разработанной Владимиром Вапником и Алексеем Червоненкисом.

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

Теория венчурного капитала состоит из множества элементов, в первую очередь из аспекта венчурного капитала.

Измерение VC количественно определяет сложность пространства гипотез, например. модели, которые могут быть адаптированы с учетом представления и алгоритма обучения.

Один из способов оценить сложность пространства гипотез (пространства моделей, которые могут подойти) основан на количестве содержащихся в нем различных гипотез и, возможно, на том, как в этом пространстве можно перемещаться. Измерение венчурного капитала — это умный подход, который вместо этого измеряет количество примеров из целевой проблемы, которые можно различить с помощью гипотез в пространстве.

Измерение VC измеряет сложность пространства гипотез […] количеством различных экземпляров из X, которые можно полностью различить с помощью H.

— Страница 214, Машинное обучение, 1997.

Размерность VC оценивает возможности или возможности алгоритма машинного обучения классификации для конкретного набора данных (количество и размерность примеров).

Формально измерение VC — это наибольшее количество примеров из набора обучающих данных, которые пространство гипотез алгоритма может «разрушить».

Размерность Вапника-Червоненкиса VC(H) пространства гипотез H, определенного над пространством экземпляров X, представляет собой размер наибольшего конечного подмножества X, разрушенного H.

— Страница 215, Машинное обучение, 1997.

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

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

Например, линия (пространство гипотез) может использоваться для разбиения трех точек, но не четырех точек.

Любое размещение трех точек на 2d-плоскости с метками классов 0 или 1 можно «правильно» разделить меткой с линией, например разбит. Но существуют размещения четырех точек на плоскости с метками двоичных классов, которые невозможно правильно разделить меткой с линией, например. нельзя разбить. Вместо этого необходимо использовать другой «алгоритм», например овалы.

На рисунке ниже это ясно видно.

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

Классификатор, который прогнозирует одно и то же значение во всех случаях, будет иметь размерность VC, равную 0, без баллов. Большой размер VC указывает на то, что алгоритм очень гибок, хотя гибкость может достигаться за счет дополнительного риска переобучения.

Аспект венчурного капитала используется как часть структуры обучения PAC.

Ключевой величиной в обучении PAC является размерность Вапника-Червоненкиса, или размерность VC, которая обеспечивает меру сложности пространства функций и позволяет расширять структуру PAC на пространства, содержащие бесконечное количество функций.

- Страница 344, Распознавание образов и машинное обучение, 2006.

Дополнительную информацию о PCA Learning можно найти в основополагающей книге по этой теме:

• Природа статистической теории обучения, 1999.

Дальнейшее чтение

В этом разделе представлены дополнительные ресурсы по этой теме, если вы хотите углубиться в нее.

Книги

• Вероятно, приблизительно верно: Природные алгоритмы обучения и процветания в сложном мире, 2013.
• Искусственный интеллект: современный подход, 3-е издание, 2009 г.
• Введение в теорию вычислительного обучения, 1994.
• Машинное обучение: вероятностная перспектива, 2012.
• Природа статистической теории обучения, 1999.
• Распознавание образов и машинное обучение, 2006.
• Машинное обучение, 1997.

Статьи

• Статистическая теория обучения, Википедия.
• Теория вычислительного обучения, Википедия.
• Наверное примерно правильное обучение, Википедия.
• Теория Вапника–Червоненкиса, Википедия.
• Измерение Вапника–Червоненкиса, Википедия.

Краткое содержание

В этом посте вы открыли для себя краткое введение в теорию вычислительного обучения для машинного обучения.

В частности, вы узнали:

• Теория вычислительного обучения использует формальные методы для изучения задач обучения и алгоритмов обучения.
• PAC-обучение позволяет количественно оценить вычислительную сложность задачи машинного обучения.
• VC Dimension предоставляет способ количественной оценки вычислительной мощности алгоритма машинного обучения.

У вас есть вопросы?
Задавайте свои вопросы в комментариях ниже, и я постараюсь ответить.