eng
Содержание
Предисловие 6
Используемые обозначения 8
Глава 1. Основные задачи, модели и подходы
к машинному обучению 9
1.1.
Задачи распознавания образов и машинного обучения 9
1.2.
Способность распознавателя к обобщению.
Переобучение и регуляризация 16
1.3.
Применение формулы Байеса для оценок параметров
моделей 29
1.4.
Обучение, проверка, выбор модели распознавателя.
Характеристики качества классификации 37
1.5.
Классификатор Байеса 46
1.6.
Энтропия. Расхождение Кульбака — Лейблера 54
Глава 2. Линейные модели регрессии и классификации
в машинном обучении 60
2.1.
Линейная модель регрессионного распознавателя 60
2.2.
Последовательное обучение регрессионного
распознавателя 65
2.3.
Регуляризация в методе наименьших квадратов 66
2.4.
Представление ошибки регрессионного
распознавателя в виде составляющих смещения
и разброса 72
2.5.
Линейные модели в задаче классификации 79
2.6.
Нахождение параметров линейных моделей 83
2.7.
Порождающие вероятностные модели классификаторов 89
2.8.
Дискриминантные вероятностные модели
классификаторов. Логистическая регрессия
для двух классов 96
2.9.
Логистическая регрессия с несколькими классами 103
2.10.
Пробит-регрессия 105
4
Содержание
Глава 3. Применение искусственных нейронных сетей
для распознавания образов 108
3.1.
Персептрон и его использование в бинарной
классификации 108
3.2.
Нейронные сети прямого распространения 118
3.3.
Обучение нейронной сети методом обратного
распространения ошибки 124
3.4.
Перекрестная энтропия как функция штрафа
в методе обратного распространения ошибки 132
3.5.
Модифицированные методы градиентного поиска,
ускоряющие обучение нейронных сетей 134
3.6.
Инициализация сети и предобработка данных.
Пакетная нормализация 141
3.7.
Регуляризация при обучении нейронных сетей 147
3.8.
Упрощение структуры сети на основе матрицы Гессе 154
3.9.
Теорема об универсальной аппроксимации.
Проблемы глубокого обучения 160
3.10.
Сверточные нейронные сети — инструмент для
распознавания изображений 163
Глава 4. Метод опорных векторов 176
4.1.
Задача выпуклого программирования.
Теорема Куна — Таккера 176
4.2.
Метод опорных векторов для двух линейно
разделимых классов 179
4.3.
Метод опорных векторов для линейно неразделимых
классов 186
4.4.
Машины опорных векторов 192
4.5.
Применение метода опорных векторов для задачи
регрессии 201
4.6.
Выявление аномалий данных с использованием
метода опорных векторов 207
Содержание 5
Глава 5. Ансамбли распознавателей.
Отбор и преобразование признаков 213
5.1.
Модель распознавателя как дерево решений.
Деревья регрессии 213
5.2.
Деревья классификации 219
5.3.
Ансамбли распознавателей. Бэггинг, случайный лес 225
5.4.
Усиление ансамбля распознавателей (бустинг) 230
5.5.
Градиентный бустинг 238
5.6.
Формирование и преобразование признаков 241
5.7.
Селекция признаков. Метод главных компонент 247
5.8.
Оценка значимости признаков для модели
распознавателя 256
Глава 6. Обучение распознавателя без учителя 259
6.1.
Задача кластеризации данных 259
6.2.
Сети Кохонена 268
6.3.
Самоорганизующиеся карты Кохонена 273
6.4.
Модели распределений в виде гауссовых смесей 281
6.5.
Общая схема алгоритма ЕМ 289
Глава 7. Марковские модели последовательных данных 294
7.1.
Цепи Маркова 294
7.2.
Скрытые марковские модели 300
7.3.
Определение параметров скрытых марковских
моделей по выборке последовательных данных 304
7.4.
Прямой и обратный проход в ЕМ-алгоритме
для скрытой марковской модели 309
7.5.
Определение параметров скрытых марковских
моделей по выборке: итоги 318
Библиографический список 322
Предисловие
Предлагаемое вниманию читателя пособие было написано как
часть методического обеспечения (не включающая лабораторный
практикум) учебного курса «Распознавание образов и машинное
обучение», который на протяжении ряда лет читался автором в на-
циональном исследовательском университете МИЭТ. Этот курс
является введением в научную дисциплину, которая представляет
собой один из краеугольных камней такой крайне важной и бур-
но развивающейся области знаний, как искусственный интеллект
(ИИ).
В начале XXI века мощным импульсом развития теории и прак-
тики ИИ вообще и распознавания образов в частности послужил
революционный прогресс в создании высокопроизводительных
систем и платформ на основе технологий распределенных и парал-
лельных вычислений. Вследствие этого, в частности, открылись
новые горизонты для применения алгоритмов и методов на основе
искусственных нейронных сетей (ИНС), которые на сегодняшний
день являются технологической основой многих, если не большин-
ства, систем ИИ.
Вопросам, связанным с применением ИНС для распознавания
образов, в пособии уделено немалое внимание, но все же в ключе
первого знакомства, причем в большей степени с теоретической
точки зрения. ИНС — это очень важный для ИИ, но не единствен-
ный инструмент. Его совершенствование и усложнение невозможно
без опоры на общую теорию машинного обучения и распознавания
образов, в основе которой лежит весьма прочный математический
фундамент. Учебное пособие представляет собой введение в дан-
ную теорию.
В концептуальном плане по используемому математическому
аппарату в теории распознавания образов традиционно выделя-
ются два подхода: детерминистский и статистический (вероят-
ностный). Первый основывается прежде всего на математическом
программировании, теории графов, математической логике и лин-
гвистике. Во втором подходе доминирующую роль играют тео-
рия вероятностей и математическая статистика. Однако подобное
Предисловие 7
разделение становится все более условным вследствие наблюдае-
мой конвергенции этих подходов.
На взгляд автора, в терминах статистической теории исходные
формулировки практических задач распознавания выглядят бо-
лее естественно, хотя часто их постановки (и решения) могут быть
даны и в таких формах, которые вообще не требуют привлечения
понятия «вероятность». Как следует из названия пособия, при его
написании автор придерживался главным образом статистическо-
го подхода. На такое методологическое видение, а также на исполь-
зуемые методические приемы изложения, в значительной степени
повлияла классическая монография К. Бишопа [11].
Автор стремился придерживаться такого изложения, кото-
рое, с одной стороны, было бы в достаточной степени обосновано
теоретически, а с другой — предполагало все-таки ориентацию
на аудиторию студентов профильных инженерных направлений
(математика и компьютерные науки, прикладная математика, про-
граммная инженерия), т. е. практиков. Для изучения материала по-
собия никаких начальных знаний из области машинного обучения
и распознавания образов не требуется, однако предполагается, что
в объеме вузовских математических курсов читатель достаточно
хорошо владеет аппаратом математического анализа, линейной
алгебры, теории вероятностей, а также знаком с основами методов
оптимизации. Учебное пособие предназначено прежде всего для
студентов бакалавриата и магистратуры, обучающихся по направ-
лениям «Прикладная математика» и «Математика и компьютерные
науки». Однако автор надеется, что пособие окажется полезным
и для более широкого круга читателей.
Конечно, для инженера, и тем более исследователя, который
будет далее специализироваться в области ИИ, освоения изложен-
ного в пособии материала общего теоретического характера, скорее
всего, окажется недостаточно для дальнейшей профессиональной
деятельности. Со многими важными современными тенденциями,
такими как обучение с подкреплением, состязательное обучение
и многое другое, нужно будет познакомиться уже на следующем
шаге изучения данной чрезвычайно быстро развивающейся пред-
метной области. Для этого шага можно рекомендовать прежде всего
монографии [1, 5, 7, 12].
Èñïîëüçóåìûå îáîçíà÷åíèÿ
Везде в данном пособии автор стремился использовать однотипные
обозначения в соответствии со следующими соглашениями.
Скалярные величины обозначаются латинским курсивом (как
строчными, так и прописными буквами) или прямыми строчными
греческими буквами, например: x, С, . Векторные величины счи-
таются векторами-столбцами и обозначаются прямыми полужир-
ными символами (по возможности строчными), например: x, ω.
Матрицы обозначаются прописными буквами полужирным шриф-
том: X, Ω. Верхний индекс T означает транспонирование матриц
(векторов) и в записи вида x = (x1, x2, …, xM)T указывает на то, что x —
это вектор-столбец. Если интерпретация какого-либо вектора как
строки или как столбца не играет роли, то указывающий на транс-
понирование индекс T может быть опущен: x = (x1, x2, …, xM).
Случайные величины скалярного типа обозначаются пропис-
ным латинским курсивом (например X) или прямыми греческими
буквами (например ). Для векторных случайных величин исполь-
зуется прямой полужирный шрифт (как строчные, так и прописные
буквы): X, Ω, x, ω. Вновь, если в контексте изложения трактовка
некоторого случайного вектора как вектора-строки или вектора-
столбца непринципиальна, может использоваться как обозначе-
ние X = (X1, …, XN)T, так и запись X = (X1, …, XN). Или x = (X1, …, XN)T,
x = (X1, …, XN).
Для математического ожидания случайной величины X ис-
пользуется обозначение M[X], для дисперсии — D[X]. Вероятности
обозначаются прописными курсивными буквами P (например
P(yk) = P{Y = yk} ), а плотности вероятностей — строчными курсив-
ными буквами: p(x).
В тексте пособия используется двойная нумерация для рисун-
ков, формул, примеров и упражнений: первая цифра обозначает
главу, вторая — порядковый номер формулы (рисунка, примера,
упражнения) в главе. Начало и окончание решений примеров обо-
значается соответственно символами ◄ и ►.
Предлагаемое вниманию читателя пособие было написано как
часть методического обеспечения (не включающая лабораторный
практикум) учебного курса «Распознавание образов и машинное
обучение», который на протяжении ряда лет читался автором в на-
циональном исследовательском университете МИЭТ. Этот курс
является введением в научную дисциплину, которая представляет
собой один из краеугольных камней такой крайне важной и бур-
но развивающейся области знаний, как искусственный интеллект
(ИИ).
В начале XXI века мощным импульсом развития теории и прак-
тики ИИ вообще и распознавания образов в частности послужил
революционный прогресс в создании высокопроизводительных
систем и платформ на основе технологий распределенных и парал-
лельных вычислений. Вследствие этого, в частности, открылись
новые горизонты для применения алгоритмов и методов на основе
искусственных нейронных сетей (ИНС), которые на сегодняшний
день являются технологической основой многих, если не большин-
ства, систем ИИ.
Вопросам, связанным с применением ИНС для распознавания
образов, в пособии уделено немалое внимание, но все же в ключе
первого знакомства, причем в большей степени с теоретической
точки зрения. ИНС — это очень важный для ИИ, но не единствен-
ный инструмент. Его совершенствование и усложнение невозможно
без опоры на общую теорию машинного обучения и распознавания
образов, в основе которой лежит весьма прочный математический
фундамент. Учебное пособие представляет собой введение в дан-
ную теорию.
В концептуальном плане по используемому математическому
аппарату в теории распознавания образов традиционно выделя-
ются два подхода: детерминистский и статистический (вероят-
ностный). Первый основывается прежде всего на математическом
программировании, теории графов, математической логике и лин-
гвистике. Во втором подходе доминирующую роль играют тео-
рия вероятностей и математическая статистика. Однако подобное
Предисловие 7
разделение становится все более условным вследствие наблюдае-
мой конвергенции этих подходов.
На взгляд автора, в терминах статистической теории исходные
формулировки практических задач распознавания выглядят бо-
лее естественно, хотя часто их постановки (и решения) могут быть
даны и в таких формах, которые вообще не требуют привлечения
понятия «вероятность». Как следует из названия пособия, при его
написании автор придерживался главным образом статистическо-
го подхода. На такое методологическое видение, а также на исполь-
зуемые методические приемы изложения, в значительной степени
повлияла классическая монография К. Бишопа [11].
Автор стремился придерживаться такого изложения, кото-
рое, с одной стороны, было бы в достаточной степени обосновано
теоретически, а с другой — предполагало все-таки ориентацию
на аудиторию студентов профильных инженерных направлений
(математика и компьютерные науки, прикладная математика, про-
граммная инженерия), т. е. практиков. Для изучения материала по-
собия никаких начальных знаний из области машинного обучения
и распознавания образов не требуется, однако предполагается, что
в объеме вузовских математических курсов читатель достаточно
хорошо владеет аппаратом математического анализа, линейной
алгебры, теории вероятностей, а также знаком с основами методов
оптимизации. Учебное пособие предназначено прежде всего для
студентов бакалавриата и магистратуры, обучающихся по направ-
лениям «Прикладная математика» и «Математика и компьютерные
науки». Однако автор надеется, что пособие окажется полезным
и для более широкого круга читателей.
Конечно, для инженера, и тем более исследователя, который
будет далее специализироваться в области ИИ, освоения изложен-
ного в пособии материала общего теоретического характера, скорее
всего, окажется недостаточно для дальнейшей профессиональной
деятельности. Со многими важными современными тенденциями,
такими как обучение с подкреплением, состязательное обучение
и многое другое, нужно будет познакомиться уже на следующем
шаге изучения данной чрезвычайно быстро развивающейся пред-
метной области. Для этого шага можно рекомендовать прежде всего
монографии [1, 5, 7, 12].
Èñïîëüçóåìûå îáîçíà÷åíèÿ
Везде в данном пособии автор стремился использовать однотипные
обозначения в соответствии со следующими соглашениями.
Скалярные величины обозначаются латинским курсивом (как
строчными, так и прописными буквами) или прямыми строчными
греческими буквами, например: x, С, . Векторные величины счи-
таются векторами-столбцами и обозначаются прямыми полужир-
ными символами (по возможности строчными), например: x, ω.
Матрицы обозначаются прописными буквами полужирным шриф-
том: X, Ω. Верхний индекс T означает транспонирование матриц
(векторов) и в записи вида x = (x1, x2, …, xM)T указывает на то, что x —
это вектор-столбец. Если интерпретация какого-либо вектора как
строки или как столбца не играет роли, то указывающий на транс-
понирование индекс T может быть опущен: x = (x1, x2, …, xM).
Случайные величины скалярного типа обозначаются пропис-
ным латинским курсивом (например X) или прямыми греческими
буквами (например ). Для векторных случайных величин исполь-
зуется прямой полужирный шрифт (как строчные, так и прописные
буквы): X, Ω, x, ω. Вновь, если в контексте изложения трактовка
некоторого случайного вектора как вектора-строки или вектора-
столбца непринципиальна, может использоваться как обозначе-
ние X = (X1, …, XN)T, так и запись X = (X1, …, XN). Или x = (X1, …, XN)T,
x = (X1, …, XN).
Для математического ожидания случайной величины X ис-
пользуется обозначение M[X], для дисперсии — D[X]. Вероятности
обозначаются прописными курсивными буквами P (например
P(yk) = P{Y = yk} ), а плотности вероятностей — строчными курсив-
ными буквами: p(x).
В тексте пособия используется двойная нумерация для рисун-
ков, формул, примеров и упражнений: первая цифра обозначает
главу, вторая — порядковый номер формулы (рисунка, примера,
упражнения) в главе. Начало и окончание решений примеров обо-
значается соответственно символами ◄ и ►.