Введение в машинное обучение. Просто о сложном

Кратчайшая история искусственного интеллекта

Искусственный интеллект, как научная область активно развивается с начала XIX века. Наибольшая активность в области происходила в 60-х и 70-х годах. В то время казалось, что ИИ это близкое будущее, что, в общем, не удивительно, т.к направление прогрессировало невероятно быстро. Компьютеры все чаще обыгрывали лучших шахматистов, а на исследования в области ИИ выделялись огромные деньги. Однако, к 1973 году стало понятно, что не все так хорошо, как кажется. В этом году был опубликован так называемый отчет Лайтхилла — документ «Искусственный интеллект: Общий обзор», дающий крайне пессимистические прогнозы для основных направлений отрасли. Документ предвещал наступление т.н. «зимы искусственного интеллекта».

Основными причинами «Зимы ИИ» стали:

1. Проблема комбинаторного взрыва (Резкий рост временной сложности алгоритма при увеличении размера входных данных).
2. Низкая производительность компьютеров (Более высокая производительность могла бы частично решить первую проблему).
3. Проблема представлений знаний «здравого мысла» (Например, задача формализации процесса распознавания речи человеком не решена до сих пор).
4. Парадокс Моравеца (Для компьютера многие задачи, очевидные с человеческой точки зрения, становятся сложными и наоборот).

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

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

Введение в машинное обучение

Нестрогое определение машинного обучения дал Артур Самуэль в далеком 1959 году в своей инновационной работе по компьютерным шашкам. Он определил машинное обучение следующим образом:

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

Если говорить о строгом, формальном определении, то его хорошо дал Том Митчел в своей книге о машинном обучении, ставшей классической.

Говорят, что компьютерная программа обучается на основе опыта E по отношению к некоторому классу задач T и меры качества P, если качество решения задач из T, измеренное на основе P, улучшается с приобретением опыта E.

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

Список прикладных сфер применения машинного обучения невероятно широк. Сферы применения машинного обучения:

1. Распознавание речи.
2. Компьютерное зрение.
3. Компьютерная лингвистика и обработка естественных языков.
4. Медицинская диагностика.
5. Техническая диагностика.
6. Рубрикация текстов.
7. Интеллектуальные игры.

В рамках машинного обучение существует большое количество открытых вопросов. Например:

1. Какое количество и какой информации необходимо для обучения?
2. Какие данные лучше выбирать для обучения и почему?
3. Какой алгоритм решает поставленную задачу наилучшим образом?
4. Как свести какую-либо задач обучения к аппроксимации или оптимизации некоторой функции?

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

Машинное обучение разделяется на несколько типов:

1. Обучение с учителем (обучение по прецедентам) — На подмножестве рассматриваемых объектов известны ответы для каждого из них. Учителем, обычно, называют обучающую выборку пар объект-ответ. Задачей такого обучение является нахождение закономерности, согласно которой можно найти ответ для любого объекта.
2. Частичное обучение — При частичном обучении большая часть ответов неизвестна.
3. Активное обучение — Очень похоже на обучение с учителем с той разницей, что ответы изначально неизвестны. Основная идея состоит в том, что алгоритм сам может обучаться на малых выборках, если он сам выбирает какие данные ему нужны. То есть алгоритм составляет запросы, ответы на которые помогают ему обучаться.
4. Стимулируемое обучение (обучение с подкреплением) — В этом случае правильных ответов не существует, а алгоритм пытается найти оптимальную стратегию.
5. Обучение без учителя — (Алгоритм ищет не пары объект-ответ, а связи между объектами.

Рассмотрим подробнее обучение с учителем и без него.

Обучение с учителем

Определение

Пусть X — множество объектов, Y — множество ответов и имеется некоторая зависимость (детерминированная или вероятностная), позволяющая по x∈X предсказать y∈Y. То есть, если эта зависимость детерминированная, то существует некоторая функция ƒ*:X→Y. Причем изначально, эта зависимость известна только на объектах из обучающей выборки. Задача машинного обучения с учителем — научиться по новым объектам x∈X предсказывать y∈Y, т.е восстановить зависимость.

В зависимости от множества Y выделяют типы задач обучения:

1. Задача классификации (Y={1,2,..,K} конечно) — множество X разбивается на K классов. По x∈X требуется предсказать к какому классу он принадлежит. В частности, задачей классификации является задача распознавания образов.
2. Задача восстановления регрессии (Y=R) — требуется найти функцию ƒ из определенного класса, которая аппроксимирует ƒ*.

Практическое применение

Рассмотрим в качестве примера задачу медицинской диагностики.
Неформальная постановка задачи: по некоторому набору симптомов и характеристик пациента необходимо поставить диагноз или определить, что пациент здоров.
Формализуем задачу. Определим множество объектов X, как множество симптомов, а множество ответов Y, как множество всех существующих болезней и элемента «пациент здоров». Очевидно, что Y конечно, а, значит, перед нами задача классификации.  Обучение будет проходить на достаточном объеме прецедентов.

Нам могут встречаться признаки различных типов:

1. Бинарные (Пол, наличие боли в спине, в сознании ли пациент).
2. Номинальные (Тип боли: колющая, режущая, ноющая).
3. Порядковые (Общее состояние больного: удовлетворительное, средней тяжести, тяжелое, крайне тяжелое).
4. Количественные (Температура тела, пульс, артериальное давление).

Пусть, например, у нас имеется некоторая информация о N пациентах. История болезни каждого из них состоит из информации о восьми различных характеристиках, а, также о том болен он сахарным диабетом или нет. Эта информация будет обучающей выборкой. Задача алгоритма — на основе обучающей выборки научиться по набору этих характеристик определять болен пациент (не из обучающей выборки) сахарным диабетом или нет.
Мы имеем N точек в 8-мерном пространстве.

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

Можно спроецировать на двухмерную плоскость уровень глюкозы и индекс массы тела пациентов.

Задачей машинного обучения будет нахождение зависимости между набором характеристик и диагнозом. Однако, очевидно, что при небольшой обучающей выборке доверять программе будет нельзя. А вот при обучающей выборке в несколько сотен тысяч человек, машина будет правильно диагностировать в 99% случаев.

Обучение без учителя

Определение

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

Практическое применение

Рассмотрим в качестве примера задачу выделения групп родственных естественных языков на основе списка Сводеша. Список Сводеша — это список из 207 слов базового словаря языков.

На основе списка Сводеша можно построить матрицу родственности между языками.

В качестве заключения

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