Машинное обучение

Материал из MachineLearning.

(Различия между версиями)
Перейти к: навигация, поиск
м (Курсы лекций: оформление)
Строка 12: Строка 12:
* [[:Категория:Приложения в медицине]]
* [[:Категория:Приложения в медицине]]
** [[Медицинская диагностика]]
** [[Медицинская диагностика]]
 +
* [[:Категория:Приложения в геологии и геофизике]]
* [[:Категория:Приложения в социологии]]
* [[:Категория:Приложения в социологии]]
* [[:Категория:Приложения в экономике]]
* [[:Категория:Приложения в экономике]]
Строка 34: Строка 35:
== Общая постановка задачи обучения по прецедентам ==
== Общая постановка задачи обучения по прецедентам ==
-
Дано конечное множество ''прецедентов'' (объектов, ситуаций), по каждому из которых собраны (измерены) некоторые ''данные''. Требуется по этим ''частным'' данным выявить ''общие'' зависимости, закономерности, взаимосвязи, присущие не только этим прецедентам, но вообще всем прецеденты, в том числе тем, которые ещё не наблюдались.
+
Дано конечное множество ''прецедентов'' (объектов, ситуаций), по каждому из которых собраны (измерены) некоторые ''данные''. Данные о прецеденте называют также его ''описанием''. Совокупность всех имеющихся описаний прецедентов называется [[обучающая выборка|обучающей выборкой]]. Требуется по этим ''частным'' данным выявить ''общие'' зависимости, закономерности, взаимосвязи, присущие не только этой конкретной выборке, но вообще всем прецедентам, {{S|в том}} числе тем, которые ещё не наблюдались.
 +
 
 +
Наиболее распространённым способом описания прецедентов является [[признаковое описание]].
 +
Фиксируется совокупность {{S|''n'' показателей}}, измеряемых у всех прецедентов.
 +
Если все ''n'' показателей числовые, то признаковые описания представляют собой числовые векторы {{S|размерности ''n''}}.
 +
Возможны и более сложные случаи, когда прецеденты описываются
 +
[[Временной ряд|временными рядами]] или [[сигнал]]ами, [[изображение|изображениями]], [[видеоряд]]ами, [[Обработка текстов|текстами]], попарными отношениями друг с другом, например отношением сходства или интенсивности взаимодействия, {{S|и т. д.}}
 +
 
 +
Для решения задачи обучения по прецедентам в первую очередь фиксируется ''модель зависимости''.
 +
Затем вводится [[функционал качества]], значение которого показывает, насколько хорошо модель описывает наблюдаемые данные.
 +
Выбирается такой набор параметров модели, при котором функционал качества принимает оптимальное значение; это и есть ''обучение'' (или ''настройка'') модели по выборке данных.
 +
Как правило, процедура обучения сводится к применению численных методов для оптимизации функционала качества.
== Типология задач обучения по прецедентам ==
== Типология задач обучения по прецедентам ==
Строка 40: Строка 52:
<!-- непродумано, недописано
<!-- непродумано, недописано
=== По структуре исходных данных ===
=== По структуре исходных данных ===
-
* [[Поиск ассоциативных правил]]
+
*
* [[Коллаборативная фильтрация]]
* [[Коллаборативная фильтрация]]
-
=== Типы входных данных ===
+
=== Типы функционалов качества ===
 +
-->
-
* [[Признаковое описание]] объектов — наиболее распространённый случай.
+
* [[Обучение с учителем]] (supervised learning) — наиболее распространённый случай. Каждый прецедент представляет собой пару «объект, ответ». Требуется найти функциональную зависимость ответов от описаний объектов и построить ''алгоритм'', принимающий на входе описание объекта и выдающий на выходе ответ. Функционал качества обычно определяется как средняя ошибка ответов, выданных алгоритмом, по всем объектам выборки.
-
* Описание взаимоотношений между объектами, чаще всего отношения попарного сходства.
+
** Задача [[классификация|классификации]] (clssification) отличается тем, что множество допустимых ответов конечно. Их называют ''метками классов'' (class label). Класс — это множество всех объектов с данным значением метки.
-
* [[Временной ряд]] или [[сигнал]].
+
** Задача [[регрессия|регрессии]] (regression) отличается тем, что допустимым ответом является действительное число или числовой вектор.
-
* [[Изображение]] или [[видеоряд]].
+
** Задача [[прогнозирование|прогнозирования]] (forecasting) отличается тем, что объектами являются отрезки временных рядов, обрывающиеся в тот момент, когда требуется сделать прогноз на будущее. Для решения задач прогнозирования часто удаётся приспособить методы регрессии или классификации, причём во втором случае речь идёт скорее о задачах ''принятия решений''.
-
=== Типы выходных данных ===
+
* [[Обучение без учителя]] (unsupervised learning). В этом случае ответы не задаются, и требуется искать зависимости между объектами.
 +
** Задача [[кластеризация|кластеризации]] (clustering) заключается в том, чтобы сгруппировать объекты в [[кластер]]ы, используя данные о попарном сходстве объектов. Функционалы качества могут определяться по-разному, например, как отношение средних межкластерных и внутрикластерных расстояний.
 +
** Задача [[поиск ассоциативных правил|поиска ассоциативных правил]] (association rules learning). Исходные данные представляются в виде признаковых описаний. Требуется найти такие наборы признаков, и такие значения этих признаков, которые особенно часто (неслучайно часто) встречаются в признаковых описаниях объектов.
-
* [[Классификация]] — множество возможных ответов конечно.
+
* [[Обучение с подкреплением]] (reinforcement learning). Роль объектов играют пары «ситуация, принятое решение», ответами являются значения функционала качества, характеризующего правильность принятых решений (реакцию среды). Данный подход используется при самообучении роботов.
-
* [[Кластеризация]] — множество возможных ответов конечно, но неизвестно.
+
-
* [[Регрессия]] — ответы являются действительными числами или векторами.
+
-
=== Типы функционалов качества ===
+
* [[Активное обучение]] (active learning) отличается тем, что обучаемый имеет возможность самостоятельно назначать следующий объект, на котором станет известен верный ответ. См. также [[Планирование экспериментов]].
-
-->
+
 
 +
'''Вспомогательные задачи''', как правило, не представляют основного интереса с прикладной точки зрения, но используются в других (перечисленных выше) случаях для повышения качества решения.
 +
 
 +
* [[Сокращение размерности]] (dimension reduction) или отбор информативных признаков (features selection). Часто применяется в задачах классификации и регрессии, поскольку лишние признаки удорожают получение исходных данных, усложняют процесс обучения и приводят к [[переобучение|переобучению]].
 +
* [[Фильтрация выбросов]] — обнаружение в обучающей выборке небольшого числа нетипичных (шумовых) объектов, появившихся в результате ошибки или сбоя. Как правило, удаление таких объектов или придание им меньшего ''веса'' приводит к построению более надёжных ([[Робастные методы|робастных]]) алгоритмов.
 +
* [[Восполнение пропущенных данных]] — замена недостающих значений в признаковых описаниях их прогнозными значениями.
 +
 
 +
== Подходы и методы ==
 +
 
 +
'''Подход''' к задачам обучения — это концепция, парадигма, точка зрения на процесс обучения, приводящая к набору базовых предположений, гипотез, эвристик, на основе которых строится модель, функционал качества и методы его оптимизации.
 +
 
 +
Разделение методов {{S|«по подходам»}} довольно условно.
 +
Разные подходы могут приводить к одной и той же модели, но разным методам её обучения.
 +
{{S|В некоторых}} случаях эти методы отличаются очень сильно, {{S|в других}} — совсем немного и «плавно трансформируются» друг в друга путём незначительных модификаций.
-
* [[Обучение с учителем]] — наиболее распространённый случай. Для каждого прецедента задаётся и объект, и ответ. Функционал качества определяется как средняя ошибка ответов. Предполагается, что искомый алгоритм должен его минимизировать.
+
=== Статистическая классификация ===
-
* [[Обучение без учителя]], в частности, [[кластеризация]]. Для каждого прецедента задаётся только объект. Требуется сгруппировать объекты в [[кластер]]ы, используя данные о попарном сходстве объектов. Функционалы качества могут определяться по-разному, например, как отношение средних межкластерных и внутрикластерных расстояний.
+
В статистике решение задач классификации принято называть ''дискриминантным анализом''.
-
* [[Обучение с подкреплением]]. Роль объектов играют пары «ситуация, принятое решение», ответами являются значения функционала качества, характеризующего правильность принятых решений (реакцию среды). Данный подход используется при самообучении роботов.
+
-
* [[Активное обучение]] отличается тем, что обучаемый алгоритм имеет возможность самостоятельно назначать следующий объект, на котором станет известен верный ответ. См. также [[Планирование экспериментов]].
+
-
=== Методы ===
+
Классический подход основан на [[Байесовский классификатор|оптимальном байесовском классификаторе]], в котором приходится [[Оценивание плотности распределения|оценивать плотности распределения]] классов по обучающей выборке.
 +
Различные методы оценивания плотности порождают большое разнообразие байесовских методов:
 +
* [[наивный байесовский классификатор]];
 +
* [[квадратичный дискриминант]];
 +
* [[линейный дискриминант Фишера]];
 +
* [[метод парзеновского окна]] и, отчасти, [[метод ближайших соседей]];
 +
* методы на основе разделения смеси плотностей и [[EM-алгоритм]]а, в частности, [[метод радиальных базисных функций]].
-
* [[Байесовский классификатор]]:
+
Другие теоретико-вероятностные и статистические подходы:
-
** [[линейный дискриминант Фишера]];
+
* [[скрытая марковская цепь]];
-
** [[метод парзеновского окна]];
+
* [[байесовская сеть]].
-
** [[метод потенциальных функций]];
+
-
** [[метод ближайших соседей]].
+
-
* [[Байесовская сеть]].
+
=== Разделяющие поверхности ===
 +
* [[персептрон]];
 +
* [[метод потенциальных функций]];
 +
* [[метод опорных векторов]].
-
* [[Кластеризация]]:
+
=== Кластеризация ===
-
** [[иерархическая кластеризация]].
+
* [[графовые алгоритмы кластеризации]];
 +
* [[cтатистические алгоритмы кластеризации]];
 +
* [[иерархическая кластеризация]].
-
* [[Статистическая регрессия]]:
+
=== Регрессия ===
-
** [[линейная регрессия]];
+
* [[линейная регрессия]];
-
** [[нелинейная регрессия]];
+
* [[нелинейная регрессия]];
-
** [[векторная регрессия]];
+
* [[векторная регрессия]];
-
** [[логистическая регрессия]].
+
* [[логистическая регрессия]].
-
* [[Нейронная сеть]]:
+
=== Нейронные сети ===
-
** [[персептрон]];
+
* [[персептрон]];
-
** [[многослойный персептрон]];
+
* [[многослойный персептрон]];
-
** [[самоорганизующаяся сеть Кохонена]];
+
* [[самоорганизующаяся сеть Кохонена]];
-
** [[гибридная сеть встречного распространения]];
+
* [[гибридная сеть встречного распространения]];
-
** [[сеть радиальных базисных функций]];
+
* [[сеть радиальных базисных функций]];
-
** [[машина опорных векторов]].
+
-
* [[Индукция правил]]:
+
=== Индукция правил (поиск закономерностей) ===
-
** [[решающее дерево]];
+
* [[решающее дерево]];
-
** [[решающий список]];
+
* [[решающий список]];
-
** [[решающий лес]];
+
* [[решающий лес]];
-
** [[тестовый алгоритм]];
+
* [[тестовый алгоритм]];
-
** [[алгоритм вычисления оценок]].
+
* [[алгоритм вычисления оценок]].
-
* [[Алгоритмическая композиция]]:
+
=== Алгоритмические композиции ===
-
** [[взвешенное голосование]];
+
* [[взвешенное голосование]];
-
** [[бустинг]];
+
* [[бустинг]];
-
** [[бэггинг]];
+
* [[бэггинг]];
-
** [[метод комитетов]];
+
* [[метод случайных подпространств]];
-
** [[смесь экспертов]].
+
* [[метод комитетов]];
 +
* [[смесь экспертов]].
-
* [[Сокращение размерности]]:
+
=== Сокращение размерности ===
-
** [[селекция признаков]] = [[отбор признаков]];
+
* [[селекция признаков]] = [[отбор признаков]];
-
** [[метод главных компонент]];
+
* [[метод главных компонент]];
-
** [[метод независимых компонент]];
+
* [[метод независимых компонент]];
-
** [[многомерное шкалирование]].
+
* [[многомерное шкалирование]].
-
* [[Выбор модели]]:
+
=== Выбор модели ===
-
** [[минимизация эмпирического риска]];
+
* [[минимизация эмпирического риска]];
-
** [[структурная минимизация риска]];
+
* [[структурная минимизация риска]];
-
** [[минимум длины описания]];
+
* [[минимум длины описания]];
-
** [[критерий Акаике]] = [[AIC]];
+
* [[критерий Акаике]] = [[AIC]];
-
** [[байесовский информационный критерий]] = [[BIC]];
+
* [[байесовский информационный критерий]] = [[BIC]];
-
** [[скользящий контроль]];
+
* [[скользящий контроль]];
-
** [[извлечение признаков]];
+
* [[извлечение признаков]];
-
** [[метод группового учёта аргументов]] = [[МГУА]] = [[самоорганизация моделей]];
+
* [[метод группового учёта аргументов]] = [[МГУА]] = [[самоорганизация моделей]];
-
** [[случайный поиск с адаптацией]];
+
* [[случайный поиск с адаптацией]];
-
** [[генетический алгоритм]].
+
* [[генетический алгоритм]].
== Использованная литература ==
== Использованная литература ==

Версия 01:50, 29 марта 2008

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

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

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

Содержание

Приложения

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

Сфера применений машинного обучения постоянно расширяется. Повсеместная информатизация приводит к накоплению огромных объёмов данных в науке, производстве, бизнесе, транспорте, здравоохранении. Возникающие при этом задачи прогнозирования, управления и принятия решений часто сводятся к обучению по прецедентам. Раньше, когда таких данных не было, эти задачи либо вообще не ставились, либо решались совершенно другими методами.

Общая постановка задачи обучения по прецедентам

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

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

Для решения задачи обучения по прецедентам в первую очередь фиксируется модель зависимости. Затем вводится функционал качества, значение которого показывает, насколько хорошо модель описывает наблюдаемые данные. Выбирается такой набор параметров модели, при котором функционал качества принимает оптимальное значение; это и есть обучение (или настройка) модели по выборке данных. Как правило, процедура обучения сводится к применению численных методов для оптимизации функционала качества.

Типология задач обучения по прецедентам

  • Обучение с учителем (supervised learning) — наиболее распространённый случай. Каждый прецедент представляет собой пару «объект, ответ». Требуется найти функциональную зависимость ответов от описаний объектов и построить алгоритм, принимающий на входе описание объекта и выдающий на выходе ответ. Функционал качества обычно определяется как средняя ошибка ответов, выданных алгоритмом, по всем объектам выборки.
    • Задача классификации (clssification) отличается тем, что множество допустимых ответов конечно. Их называют метками классов (class label). Класс — это множество всех объектов с данным значением метки.
    • Задача регрессии (regression) отличается тем, что допустимым ответом является действительное число или числовой вектор.
    • Задача прогнозирования (forecasting) отличается тем, что объектами являются отрезки временных рядов, обрывающиеся в тот момент, когда требуется сделать прогноз на будущее. Для решения задач прогнозирования часто удаётся приспособить методы регрессии или классификации, причём во втором случае речь идёт скорее о задачах принятия решений.
  • Обучение без учителя (unsupervised learning). В этом случае ответы не задаются, и требуется искать зависимости между объектами.
    • Задача кластеризации (clustering) заключается в том, чтобы сгруппировать объекты в кластеры, используя данные о попарном сходстве объектов. Функционалы качества могут определяться по-разному, например, как отношение средних межкластерных и внутрикластерных расстояний.
    • Задача поиска ассоциативных правил (association rules learning). Исходные данные представляются в виде признаковых описаний. Требуется найти такие наборы признаков, и такие значения этих признаков, которые особенно часто (неслучайно часто) встречаются в признаковых описаниях объектов.
  • Обучение с подкреплением (reinforcement learning). Роль объектов играют пары «ситуация, принятое решение», ответами являются значения функционала качества, характеризующего правильность принятых решений (реакцию среды). Данный подход используется при самообучении роботов.

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

  • Сокращение размерности (dimension reduction) или отбор информативных признаков (features selection). Часто применяется в задачах классификации и регрессии, поскольку лишние признаки удорожают получение исходных данных, усложняют процесс обучения и приводят к переобучению.
  • Фильтрация выбросов — обнаружение в обучающей выборке небольшого числа нетипичных (шумовых) объектов, появившихся в результате ошибки или сбоя. Как правило, удаление таких объектов или придание им меньшего веса приводит к построению более надёжных (робастных) алгоритмов.
  • Восполнение пропущенных данных — замена недостающих значений в признаковых описаниях их прогнозными значениями.

Подходы и методы

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

Разделение методов «по подходам» довольно условно. Разные подходы могут приводить к одной и той же модели, но разным методам её обучения. В некоторых случаях эти методы отличаются очень сильно, в других — совсем немного и «плавно трансформируются» друг в друга путём незначительных модификаций.

Статистическая классификация

В статистике решение задач классификации принято называть дискриминантным анализом.

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

Другие теоретико-вероятностные и статистические подходы:

Разделяющие поверхности

Кластеризация

Регрессия

Нейронные сети

Индукция правил (поиск закономерностей)

Алгоритмические композиции

Сокращение размерности

Выбор модели

Использованная литература

  1. Айвазян С. А., Енюков И. С., Мешалкин Л. Д. Прикладная статистика: основы моделирования и первичная обработка данных. — М.: Финансы и статистика, 1983.
  2. Айвазян С. А., Енюков И. С., Мешалкин Л. Д. Прикладная статистика: исследование зависимостей. — М.: Финансы и статистика, 1985.
  3. Айвазян С. А., Бухштабер В. М., Енюков И. С., Мешалкин Л. Д. Прикладная статистика: классификация и снижение размерности. — М.: Финансы и статистика, 1989.
  4. Вапник В. Н. Восстановление зависимостей по эмпирическим данным. — М.: Наука, 1979.
  5. Журавлев Ю. И., Рязанов В. В., Сенько О. В. «Распознавание». Математические методы. Программная система. Практические применения. — М.: Фазис, 2006. ISBN 5-7036-0108-8.
  6. Загоруйко Н. Г. Прикладные методы анализа данных и знаний. — Новосибирск: ИМ СО РАН, 1999. ISBN 5-86134-060-9.
  7. Шлезингер М., Главач В. Десять лекций по статистическому и структурному распознаванию. — Киев: Наукова думка, 2004. ISBN 966-00-0341-2.
  8. Hastie T., Tibshirani R., Friedman J. The Elements of Statistical Learning. — Springer, 2001. ISBN 0-387-95284-5.
  9. Mitchell T. Machine Learning. — McGraw-Hill Science/Engineering/Math, 1997. ISBN 0-07-042807-7.
  10. Schölkopf B., Smola A.J. Learning with Kernels. Support Vector Machines, Regularization, Optimization, and Beyond. — MIT Press, Cambridge, MA, 2002 ISBN 13-978-0-262-19475-4 [1]
  11. Vapnik V.N. Statistical learning theory. — N.Y.: John Wiley & Sons, Inc., 1998. [2]
  12. Witten I.H., Frank E. Data Mining: Practical Machine Learning Tools and Techniques (Second Edition). - Morgan Kaufmann, 2005 ISBN 0-12-088407-0 [3]

Курсы лекций

Личные инструменты