машинное обучение. А. М. Миронов Московский Государственный Университет Механикоматематический факультет Кафедра математической теории интеллектуальных систем Введение Книга
 Скачать 1.05 Mb.
|
|
Машинное обучение часть 1 А.М.Миронов Московский Государственный Университет Механико-математический факультет Кафедра математической теории интеллектуальных систем Введение Книга представляет собой введение в основные понятия, методы и ал- горитмы машинного обучения, которое находится в настоящее время в состоянии исключительно бурного развития и является теоретической основой для проектирования интеллектуальных систем обработки боль- ших данных. В первой части книги излагаются элементарные аспекты машинного обучения: ∙ виды задач и моделей машинного обучения, ∙ простейшие алгоритмы обучения для линейно разделимых обуча- ющих выборок, ∙ методы градиентного спуска и его разновидности, ∙ метод обучения нейронных сетей, ∙ метод опорных векторов, ∙ ядерные методы машинного обучения, ∙ регрессионный анализ, ∙ метрические и вероятностные модели машинного обучения. Во второй части будут рассмотрены более глубокие вопросы машин- ного обучения, в частности, методы прогнозирования индивидуальных последовательностей, сравнительная теория машинного обучения, бу- стинг, алгоритмы экспоненциального смешивания, агрегирующие алго- ритмы, методы теории игр в машинном обучении. В третьей части бу- дут изложены модели и методы автоматного и процессного обучения (automata learning и process mining). Просьба сообщать автору о всех замеченных недостатках и рекомен- дациях по улучшению данного текста по адресу amironov66@gmail.com 1 Оглавление 1 Задачи и модели машинного обучения 4 1.1 Задачи машинного обучения . . . . . . . . . . . . . . . . . . 4 1.1.1 Предмет машинного обучения . . . . . . . . . . . . . 4 1.1.2 Обучение функциональным зависимостям . . . . . . 4 1.1.3 Способ описания объектов . . . . . . . . . . . . . . . 5 1.1.4 Пример задачи машинного обучения . . . . . . . . . 6 1.1.5 Виды задач машинного обучения . . . . . . . . . . . 7 Задачи классификации . . . . . . . . . . . . . . . . . 7 Задачи регрессии 8 Задачи ранжирования . . . . . . . . . . . . . . . . . . 8 1.2 Модели машинного обучения . . . . . . . . . . . . . . . . . . 8 1.2.1 Понятие модели обучения 8 1.2.2 Примеры предсказательных моделей . . . . . . . . . 9 Линейная предсказательная модель . . . . . . . . . . 9 Предсказательная модель в виде нейронной сети . . 9 1.2.3 Алгоритмы обучения . . . . . . . . . . . . . . . . . . 12 1.3 Проблема переобучения . . . . . . . . . . . . . . . . . . . . . 14 1.4 Основные этапы решения задач машинного обучения . . . . 15 2 Элементарные методы и алгоритмы машинного обучения 16 2.1 Линейно разделимые выборки . . . . . . . . . . . . . . . . . 16 2.2 Алгоритм обучения Розенблатта . . . . . . . . . . . . . . . . 19 2.2.1 Описание алгоритма обучения Розенблатта . . . . . 20 2.2.2 Завершаемость алгоритма Розенблатта . . . . . . . . 21 2.2.3 Модификации алгоритма Розенблатта . . . . . . . . 23 2.3 Метод градиентного спуска . . . . . . . . . . . . . . . . . . . 23 2.3.1 Понятие градиентного спуска 23 2.3.2 Описание метода градиентного спуска . . . . . . . . 24 2.3.3 Модификации метода градиентного спуска . . . . . . 27 Метод стохастического градиента . . . . . . . . . . . 27 Регуляризация . . . . . . . . . . . . . . . . . . . . . . 28 2 2.4 Метод обратного распространения ошибки для обучения нейронных сетей . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.4.1 Идея метода . . . . . . . . . . . . . . . . . . . . . . . 29 2.4.2 Описание метода . . . . . . . . . . . . . . . . . . . . . 30 2.4.3 Достоинства и недостатки метода . . . . . . . . . . . 32 2.5 Метод опорных векторов . . . . . . . . . . . . . . . . . . . . 33 2.5.1 Оптимальность аппроксимирующих функций . . . . 33 2.5.2 Построение оптимальной разделяющей гиперплос- кости для строго линейно разделимой выборки . . . 35 Описание задачи . . . . . . . . . . . . . . . . . . . . . 35 Метод решения оптимизационной задачи . . . . . . . 37 Применение метода . . . . . . . . . . . . . . . . . . . 44 2.5.3 Построение оптимальной разделяющей гиперплос- кости по зашумленной выборке . . . . . . . . . . . . 47 2.6 Ядерный метод машинного обучения . . . . . . . . . . . . . 51 2.6.1 Спрямляющие пространства . . . . . . . . . . . . . . 51 2.6.2 Примеры ядер . . . . . . . . . . . . . . . . . . . . . . 55 2.6.3 Каноническое гильбертово пространство, определя- емое ядром . . . . . . . . . . . . . . . . . . . . . . . . 57 2.7 Задача регрессии . . . . . . . . . . . . . . . . . . . . . . . . . 60 2.7.1 Линейная регрессия . . . . . . . . . . . . . . . . . . . 60 2.8 Метрическая модель обучения 63 2.8.1 Понятие метрики 63 2.8.2 Метод ближайших соседей . . . . . . . . . . . . . . . 64 2.8.3 Метод окна Парзена . . . . . . . . . . . . . . . . . . . 65 2.8.4 Метод потенциалов . . . . . . . . . . . . . . . . . . . 66 2.8.5 Метод эталонов 67 2.9 Вероятностные модели обучения . . . . . . . . . . . . . . . . 68 2.9.1 Дискретная вероятностная модель обучения . . . . . 68 2.9.2 Оптимальные аппроксимирующие функции . . . . . 69 2.9.3 Построение АФ по обучающей выборке . . . . . . . . 72 2.9.4 Непрерывная вероятностная модель обучения . . . . 72 2.9.5 EM-алгоритм . . . . . . . . . . . . . . . . . . . . . . . 76 Число 𝑘 компонентов смеси известно . . . . . . . . . 77 Число компонентов смеси неизвестно . . . . . . . . . 79 3 Глава 1 Задачи и модели машинного обучения 1.1 Задачи машинного обучения 1.1.1 Предмет машинного обучения Машинное обучение (Machine Learning, ML) – это раздел теории искусственного интеллекта, предметом которого является поиск методов решения задач путем обучения в процессе решения сходных задач. Для построения таких методов используются средства алгебры, ма- тематической статистики, дискретной математики, теории оптимизации, численных методов, и других разделов математики. 1.1.2 Обучение функциональным зависимостям Одно из направлений ML связано с задачами следующего вида: имеются ∙ множество 𝑋 объектов, и ∙ множество 𝑌 ответов. Предполагается, что существует функциональная зависимость 𝑓 : 𝑋 → 𝑌 между объектами и ответами, но она неизвестна. Известна лишь совокуп- ность 𝑆 пар вида (объект, ответ), называемая обучающей выборкой (training sample): 𝑆 = {(𝑥 𝑖 , 𝑦 𝑥 𝑖 = 𝑓 (𝑥 𝑖 )) ∈ 𝑋 × 𝑌 | 𝑖 = 1, . . . , 𝑙}. 4 Требуется найти приближенный вид этой 𝑓 путем построения аппрок- симирующей функции (АФ) 𝑎 𝑆 : 𝑋 → 𝑌 (decision function), такой, что ∀ 𝑥 ∈ 𝑋 𝑎 𝑆 (𝑥) ≈ 𝑓 (𝑥). 1.1.3 Способ описания объектов Объекты в ML могут иметь самую различную природу: это могут быть люди, животные, растения, страны, организации, сайты, столы, стулья, изображения, фильмы, и т.д. Один из способов описания объектов в форме, пригодной для реше- ния описанных выше задач ML имеет следующий вид: ∙ задается множество ℑ признаков объектов (features), ∙ каждому признаку 𝑖 ∈ ℑ сопоставляется множество 𝐷 𝑖 значений этого признака, и ∙ каждому объекту 𝑥 ∈ 𝑋 и каждому признаку 𝑖 ∈ ℑ сопоставляется значение 𝑥 𝑖 𝑖–го признака на объекте 𝑥. Множество признаков объектов определяется решаемыми задачами ML. Адекватный выбор этого множества для каждой конкретной задачи ML – нетривиальная проблема, от правильного решения которой суще- ственно зависит успех в решении этой задачи ML. Каждый признак 𝑖 ∈ ℑ имеет определенный тип. Ниже мы пере- числяем некоторые из таких типов и указываем соответствующие им множества значений 𝐷 𝑖 : ∙ бинарный: 𝐷 𝑖 = {−1, 1} или {0, 1}, ∙ номинальный: 𝐷 𝑖 – конечное множество, ∙ порядковый: 𝐷 𝑖 – конечное линейно упорядоченное множество, ∙ количественный: 𝐷 𝑖 = R (множество действительных чисел). Для удобства мы будем предполагать, что ∙ множество ℑ признаков является конечным, его элементам сопо- ставлены натуральные числа 1, . . . , 𝑛, которые мы будем отождеств- лять с соответствующими им признаками, и ∙ значениями каждого признака являются действительные числа. 5 Описание объекта 𝑥 ∈ 𝑋 относительно множества {1, . . . , 𝑛} при- знаков – это кортеж (𝑥 1 , . . . , 𝑥 𝑛 ) значений каждого из признаков 1, . . . , 𝑛. Т.к. по предположению ∀ 𝑖 = 1, . . . , 𝑛 𝑥 𝑖 ∈ R, то описание объекта 𝑥 можно рассматривать как элемент векторного пространства R 𝑛 Напомним, что R 𝑛 состоит из всех векторов размерности 𝑛, т.е. по- следовательностей вида (𝛼 1 , . . . , 𝛼 𝑛 ), где ∀ 𝑖 = 1, . . . , 𝑛 𝛼 𝑖 ∈ R, операции сложения на данных последовательностях и умножения их на действи- тельные числа определяются стандартным образом: (𝛼 1 , . . . , 𝛼 𝑛 ) + (𝛼 ′ 1 , . . . , 𝛼 ′ 𝑛 ) def = (𝛼 1 + 𝛼 ′ 1 , . . . , 𝛼 𝑛 + 𝛼 ′ 𝑛 ), 𝛼(𝛼 1 , . . . , 𝛼 𝑛 ) = (𝛼 1 , . . . , 𝛼 𝑛 )𝛼 def = (𝛼𝛼 1 , . . . , 𝛼𝛼 𝑛 ). 1.1.4 Пример задачи машинного обучения В этом пункте мы приведем пример одной задачи ML и связанного с ней описания объектов. Данная задача называется задачей кредитно- го скоринга. Объектами в ней являются заявки на выдачу кредита в некотором банке, а ответами – элементы множеста {−1, 1}. Для каждого объекта 𝑥 ответ 𝑓 (𝑥) интепретируется как решение банка: ∙ ответ «1»: выдать кредит по заявке 𝑥, ∙ ответ «−1»: отказать в удовлетворении заявки 𝑥. Решение банка по удовлетворению заявки является правильным, если ∙ клиент, подавший эту заявку, и получивший кредит, вернет его в должный срок, или ∙ клиент, которому было отказано в удовлетворении заявки 𝑥, в слу- чае получения этого кредита с высокой вероятностью может не вер- нуть его в должный срок. Известно множество 𝑆 = {(𝑥 𝑖 , 𝑦 𝑥 𝑖 ) | 𝑖 = 1, . . . 𝑙} где ∀ 𝑖 = 1, . . . 𝑙 ∙ 𝑥 𝑖 – некоторая заявка на выдачу кредита, ∙ 𝑦 𝑥 𝑖 – решение банка по этой заявке, которое является правильным. Требуется обучиться функции 𝑎 𝑆 , вычисляющей по каждой новой за- явке правильное решение. Данную задачу можно решать методами ML, в которой 𝑆 рассматривается как обучающая выборка. Каждый объект в этой задаче связан с некоторым клиентом, и при- знаки объекта могут иметь вид различных характеристик этого клиента. Например, могут быть выбраны следующие признаки: 6 ∙ бинарные: пол, наличие постоянной работы, и т.д. ∙ номинальные: место проживания, профессия, работодатель и т.д. ∙ порядковые: образование, должность и т.д. ∙ количественные: возраст, зарплата, стаж работы, доход семьи, сум- ма кредита и т.д. Описанная выше задача ML может допускать различные обобщения. Например, можно обучаться не только нахождению правильных реше- ний банка, но и например оценке вероятности дефолта клиента (т.е. воз- никновения ситуации, когда клиент, получивший кредит, не вернет его в должный срок). 1.1.5 Виды задач машинного обучения Задачи классификации Изложенная в предыдущем пункте задача ML является примером задач классификации. В задачах данного вида ∙ множество ответов 𝑌 является конечным, ∙ каждый ответ 𝑦 ∈ 𝑌 соответствует некоторому классу объектов, и ∙ задача ML заключается в вычислении по каждому объекту соот- ветствующего ему класса. В описанной в предыдущем пункте задаче рассматривается класси- фикация с двумя классами объектов. Другой пример задач классифи- кации с двумя классами: объектами являются посетители поликлиники, требуется по признакам посетителя дать ответ: болен он, или нет. Могут быть задачи классификации с числом классов более двух, на- пример ∙ задача распознавания рукописных букв русского языка, в данном случае 𝑌 = {а, . . . , я}, ∙ пусть 𝑀 – некоторое множество болезней, 𝑋 – множество пациен- тов поликлиники, для которых требуется диагностировать набор болезней, которыми они болеют, в данном случае классы соответ- ствуют наборам болезней: 𝑌 = 𝒫(𝑀 ). 7 Задачи регрессии В задачах регрессии множество ответов 𝑌 имеет вид R или R 𝑚 . Задачи данного типа как правило связаны с прогнозированием (например, курса доллара, или курсов нескольких валют). Задачи ранжирования Задачи ранжирования возникают например в системах информационно- го поиска, или в рекомендательных системах. В данных задачах требу- ется по каждому объекту 𝑥 ∈ 𝑋 определить его приоритет в выдаче в качестве результата на некоторый запрос. Множество 𝑌 ответов здесь является конечным упорядоченным множеством, ∀ 𝑥 ∈ 𝑋 значение 𝑓 (𝑥) представляет собой соответствующий приоритет. 1.2 Модели машинного обучения 1.2.1 Понятие модели обучения Как правило, для решения задачи построения функции 𝑎 𝑆 : 𝑋 → 𝑌 по обучающей выборке 𝑆 выбирается некоторая модель обучения, состо- ящая из двух компонентов: 1. Первой компонентой модели обучения является функция 𝑎 : 𝑋 × 𝑊 → 𝑌 (1.1) где 𝑊 – множество, элементы которого называются параметрами. Искомая функция 𝑎 𝑆 ищется в виде 𝑎 𝑆 (𝑥) = 𝑎(𝑥, 𝑤), (1.2) где 𝑤 – фиксированный параметр. Функцию (1.1) иногда называют предсказательной моделью (predictive model). 2. Другой компонентой модели обучения является алгоритм обуче- ния, который представляет собой алгоритм поиска такого значения 𝑤, для которого функция 𝑎 𝑆 , определяемая соотношением (1.2), об- ладает некоторыми свойствами оптимальности. Более подробно об свойствах оптимальности функции 𝑎 𝑆 см. в пункте 1.2.3. 8 1.2.2 Примеры предсказательных моделей Линейная предсказательная модель В линейной предсказательной модели множество 𝑊 параметров имеет вид R 𝑛 , где 𝑛 – число признаков объектов, т.е. каждый параметр 𝑤 представляет собой вектор действительных чисел 𝑤 = (𝑤 1 , . . . , 𝑤 𝑛 ), и ∙ в задачах регресии и ранжирования 𝑌 = R, и 𝑎(𝑥, 𝑤) = ⟨𝑥, 𝑤⟩ def = 𝑛 ∑︁ 𝑖=1 𝑥 𝑖 𝑤 𝑖 (число ⟨𝑥, 𝑤⟩ называется скалярным произведением 𝑥 и 𝑤), ∙ в задачах классификации 𝑌 = {−1, 1}, и 𝑎(𝑥, 𝑤) = 𝑠𝑖𝑔𝑛(⟨𝑥, 𝑤⟩), где 𝑠𝑖𝑔𝑛 – функция знака, она сопоставляет неотрицательным числам значение 1, а отрицательным – значение −1. Если какая-либо задача ML не решается в некоторой линейной моде- ли, то для решения этой задачи можно попытаться расширить исходную линейную модель путем добавления новых признаков, получаемых из уже имеющихся признаков. Например, можно добавлять ∙ комбинации признаков (их произведение, и т.п.), ∙ функции от признаков, и т.д. Предсказательная модель в виде нейронной сети В современных технологиях машинного обучения очень популярны пред- сказательные модели, основанные на нейронных сетях. Данные модели используют преобразователи информации, являющи- еся аналогами биологических нейронов. Структура биологического ней- рона изображена на следующей картинке: 9 Преобразование информации в нейроне происходит в его центральной части (называемой телом), от которой отходят отростки двух типов: ∙ дендриты, по ним поступают входные сигналы, будем считать дендриты занумерованными натуральными числами 1, . . . , 𝑛, ∙ аксон, отросток такого типа ровно один, по нему проходит выход- ной сигнал. Схема работы нейрона имеет следующий вид: с каждым из дендритов связано некоторое неотрицательное действительное число, называемое весовым коэффициентом (или просто весом). Обозначим записью 𝑤 1 , . . . , 𝑤 𝑛 список весов, соответствующих каждому из дендритов (∀ 𝑖 = 1, . . . , 𝑛 дендриту номер 𝑖 соответствует вес 𝑤 𝑖 ). Кроме того, с нейроном связано число 𝑤 0 ≥ 0, называемое порогом возбуждения. Сигналы, поступаемые в нейрон по дендритам, являются электриче- скими импульсами различной интенсивности. Обозначим записью 𝑥 1 , . . ., 𝑥 𝑛 список интенсивностей сигналов, поступивших в текущий момент по каждому из дендритов (∀ 𝑖 = 1, . . . , 𝑛 𝑥 𝑖 – интенсивность сигнала, посту- пившего на нейрон номер 𝑖). Данные сигналы вызывают в центральной части нейрона электрический импульс интенсивности 𝑛 ∑︀ 𝑖=1 𝑥 𝑖 𝑤 𝑖 , и ∙ если интенсивность этого импульса превышает порог возбуждения нейрона 𝑤 0 , то нейрон выпускает по аксону выходной сигнал неко- торой интенсивности, 10 ∙ иначе по аксону выходной сигнал не выпускается (мы будем счи- тать, что в этом случае по аксону выпускается выходной сигнал нулевой интенсивности). Нейрон можно рассматривать как преобразователь числовой инфор- мации: на его вход поступает кортеж действительных чисел (𝑥 1 , . . . , 𝑥 𝑛 ), на выход он выдает число 𝑎, определяемое соотношением 𝑎 = 𝜎 (︁ 𝑛 ∑︁ 𝑖=1 𝑥 𝑖 𝑤 𝑖 − 𝑤 0 )︁ где 𝜎 – функция (называемая функцией активации), сопоставляющая неотрицательным числам значение 1, и отрицательным числам – значе- ние 0. Функционирование нейрона изображается диаграммой Ниже мы будем называть нейронами не только биологические ней- роны, но также и произвольные преобразователи числовой информации, работающие по описанному выше принципу. Функция активации (𝜎) в нейронах может иметь не только описанный выше вид, но также и другой вид, например: ∙ сигмоида: 𝜎(𝑥) = 1 1+𝑒 −𝑥 , или th(𝑥), ∙ ReLU: 𝜎(𝑥) = 0 при 𝑥 < 0, и 𝜎(𝑥) = 𝑥 при 𝑥 ≥ 0. Нейроны можно объединять в более сложные преобразователи число- вой информации, называемые многослойными нейронными сетями. В этих сетях сигналы, выдаваемые на выходах одних нейронов поступа- ют на входы других нейронов. При этом допускается, что один и тот же сигнал с выхода какого-либо нейрона может параллельно подаваться на входы нескольких нейронов. Приводимая ниже диаграмма является схематическим изображением двуслойной нейронной сети: 11 Понятие многослойной нейронной сети является основой для мето- дов глубокого обучения (deep learning), которые являются предме- том большого количества теоретических и прикладных исследований и коммерческих разработок, но в данном курсе рассматриваться не будут. |