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).
В тексте пособия используется двойная нумерация для рисун-
ков, формул, примеров и упражнений: первая цифра обозначает
главу, вторая — порядковый номер формулы (рисунка, примера,
упражнения) в главе. Начало и окончание решений примеров обо-
значается соответственно символами ◄ и ►.
ÃËÀÂÀ 1
ÎÑÍÎÂÍÛÅ ÇÀÄÀ×È,
ÌÎÄÅËÈ È ÏÎÄÕÎÄÛ
Ê ÌÀØÈÍÍÎÌÓ
ÎÁÓ×ÅÍÈÞ
1.1. Çàäà÷è ðàñïîçíàâàíèÿ îáðàçîâ
è ìàøèííîãî îáó÷åíèÿ
Приведем сначала некоторые примеры практических задач, отно-
сящихся к предметной области распознавания образов:
• распознавание людей по фотографиям лиц;
• распознавание рукописного текста;
• распознавание речи (голосовых команд);
• медицинская диагностика заболеваний;
• геологическая диагностика;
• экономическое прогнозирование и т. д.
При теоретическом рассмотрении подобных задач под терми-
ном «распознавание образов» мы будем понимать отнесение объ-
екта к тому или иному классу из конечного множества (задача
классификации) или нахождение некоторого скалярного (вектор-
ного) значения, характеризующего определенные скрытые свой-
ства объекта (задача регрессии) [8, 15, 20, 21, 23]. Для распознавания
объектов используется их описание c помощью образов.
Так, в задачах медицинской диагностики объектами будут
пациенты, а их образами — результаты анализов и другие число-
вые характеристики, такие как возраст, вес и т. п. Задача класси-
фикации в данном случае может состоять в отнесении пациента
к здоровым или к больным (возможно, больным конкретным
10 Глава 1. Основные задачи, модели и подходы к машинному обучению
заболеванием). Задачей регрессии будет, например, получение
оценки вероятности полного выздоровления пациента после
лечения.
Числовые характеристики, используемые для классификации
образов, называются признаками. Признак — это некоторое коли-
чественное измерение объекта произвольной природы, а сформи-
рованный из них вектор признаков как раз и представляет собой
образ объекта.
Пример 1.1. Рассмотрим задачу диагностики опухолей по результа-
там биопсии. Положим, что доброкачественные (класс А) и злока-
чественные (класс Б) изменения дают разную оптическую картину
при изучении под микроскопом: гистологические образцы отли-
чаются интенсивностью и контрастностью изображения. Для фор-
мирования вектора признаков будем использовать две числовых
характеристики: среднее значение и среднеквадратичное откло-
нение яркости пикселей в цифровом изображении гистологиче-
ского образца. Предположим, что имеется база данных образцов
(рис. 1.1), для которых известна их правильная классификация:
принадлежность к классам A (кружки) и Б (треугольники).
Множества точек, соответствующие образцам разных классов,
на плоскости признаков (, ) в данном случае разделимы прямой
линией. Классификация неизвестного образа (соответствующая
точка обозначена на плоскости признаков звездочкой) состоит
в проверке положения этой точки
относительно разделяющей прямой.
Для приведенного на рис. 1.1 при-
мера объект будет отнесен по его
образу к классу А (доброкачествен-
ная опухоль).
Таким образом, далее в распо-
знавании образов мы будем выделять
задачи двух типов: регрессии и клас-
сификации. В математике регрес-
сия — это условное математическое
ожидание одной случайной величи-
ны относительно других; во многих
Б
А
Рис. 1.1. Иллюстрация к
примеру 1.1
1.1. Задачи распознавания образов и машинного обучения 11
задачах «распознавательная» регрессия (нахождение скалярной или
векторной численной характеристики объекта) оказывается именно
математической регрессией относительно вектора признаков.
Классификацией называем распознавание качественной (дис-
кретной) характеристики объекта k {1, …, q}, где q — число клас-
сов, а множество k объектов, для которых эта характеристика
принимает значение k K, называем K-м классом.
Как мы позднее увидим, ответ распознавателя-классифика-
тора лучше получать не как номер класса k, а как q-мерный вектор
y (y1, …, yq)T «уверенностей» в принадлежности объекта к каж-
дому из классов (часто компонента yk — это вероятность принад-
лежности объекта к классу k). Тогда, определяя номер класса K
по максимальной компоненте выходного вектора классификатора
как K y
k q
k
arg max
{1,, }
, мы сводим задачу классификации к частному
случаю векторной регрессии. Далее мы будем полагать, что при
классификации объектов на q классов отклик распознавателя
представляет собой вектор y q.
Упражнение 1.1. Приведите практические примеры задач регрес-
сии и задач классификации.
Для построения распознавателя необходимо задать решающее
правило, т. е. функцию f, определяющую отображение пространства
векторов признаков (образов) в пространство откликов распо-
знавателя . Термины «решающая функция» и «решающее правило»
мы будем понимать как синонимы для термина «распознаватель».
Чаще всего исходные данные для нахождения решающего
правила представлены только обучающей выборкой, т. е. набором
пар T n n n
N (x , t ) 1, где скаляр или вектор tn — это желаемый
результат распознавания образа xn . По обучающей выборке не-
обходимо подобрать решающую функцию f так, чтобы распозна-
вание образов было оптимальным, т. е. «наилучшим» в каком-то
смысле (для этого необходимо определить способ оценки качества
распознавания). Для функции распознавателя f могут использо-
ваться различные модели, подбор параметров этих моделей (чаще
всего итерационный) по выборке T n n n
N (x , t ) 1 называется обуче-
нием распознавателя. Такое статистическое обучение распознава-
теля называют также машинным обучением.
12 Глава 1. Основные задачи, модели и подходы к машинному обучению
Перейдем теперь к формальной постановке задачи построения
оптимального статистического распознавателя f по обучающей
выборке T. Сначала необходимо задать следующие исходные усло-
вия задачи [4].
1. Пространство векторов признаков , точками которого коди-
руются распознаваемые объекты (например d-мерное евкли-
дово пространство d).
2. Пространство ответов , точками которого кодируются ре-
зультаты распознавания (например q-мерное пространство q).
3. Пространство распознавателей f: . В случае евклидо-
вых пространств и , например, непрерывных, дифференци-
руемых, линейных, полиномиальных и т. п.
4. Пространство распределений (вероятностных мер) на ,
которые удовлетворяют каким-либо специфическим для за-
дачи условиям. В случае евклидовых пространств и этими
условиями могут быть непрерывность функции плотности, ее
представимость в виде гауссовых смесей и т. п.
5. Функция штрафа E: (называемая также функцией
ошибки, потерь, риска и т. п.), как правило, неотрицательная
и равная нулю при совпадении прогнозного ответа y с верным
ответом t. Например, в случае евклидова пространства при-
меняется квадратичный штраф
E(t,y) t y 2, (1.1)
а в случае дискретного пространства — бинарный штраф
E(t,y) t y
t y
0
1
при
при . (1.2)
6. Обучающий набор T N N (x ,t ),,(x ,t ) 1 1 , состоящий из пар (век-
тор признаков, желаемый ответ распознавателя) (xi, ti) ,
которые считаются значениями независимых случайных век-
торных величин с одним и тем же неизвестным распределени-
ем .
Обозначив для распределения функцию плотности ве-
роятности как p(x, t), оптимальным будем считать такой распо-
знаватель f , который при выполнении условий 1–6 доставляет
минимум математического ожидания функции штрафа [4]:
E f E f E f p d d
f ( ) M ( ), ( ), ( , ) min
( , )
x t x t x t x t
x t
. (1.3)
1.1. Задачи распознавания образов и машинного обучения 13
Однако в нашем распоряжении имеется только выборка T,
взятая из генеральной совокупности с неизвестным распределе-
нием . Совершенно очевидно, что при неизвестной плотности
распределения вероятностей p(x, t) определить минимум в (1.3)
невозможно и задача построения оптимального распознавателя f
в приведенной выше формулировке неразрешима. По этой причи-
не придется заменить в (1.3) математическое ожидание штрафа его
оценкой по выборке T:
E EfTN
f E f i i
i
N
( ) ( , ) ( ),
1
1
x t , (1.4)
и вместо (1.3) рассматривать минимизацию среднего штрафа обуче-
ния, или эмпирического риска1
E f T
N
E f i i
i
N
f
( , ) ( ), min
1
1
x t
. (1.5)
При замене (1.3) на (1.5) возникает вопрос о том, насколько это
влияет на итоговые характеристики распознавателя, прежде всего
на его способность к обобщению, т. е. насколько успешно будет рабо-
тать распознаватель, когда после обучения ему будут предъявлены
новые образы, отсутствовавшие в обучающей выборке T, по кото-
рой настраивалось решающее правило f. Сделаем по этому поводу
следующие важные замечания.
• Распознаватель, который получен в результате обучения, ми-
нимизирующего штраф (1.5), зависит от обучающего набора
данных T, а приближение (1.4) справедливо для функций f,
не зависящих от выборки T. В частности, как мы увидим позд-
нее, на обучающем наборе иногда можно добиться даже нуле-
вого среднего штрафа (1.5).
• Математическое ожидание штрафа (1.3) можно оценить бо-
лее корректно, взяв другой независимый от T набор тесто-
вых данных T N N (x , t ), , (x , t ) 1 1 той же природы (из той
же генеральной совокупности), что и выборка T, и посчитав
по (1.4) средний штраф тестирования E(f, T). Результат почти
наверняка будет хуже: E( f ,T ) E( f ,T ) , особенно при большой
1 Поиск решающей функции y f(x) минимизацией эмпирического
риска (1.5) с квадратичным штрафом (1.1) представляет собой смысловое
содержание метода наименьших квадратов.
14 Глава 1. Основные задачи, модели и подходы к машинному обучению
размерности пространства и малом количестве обучающих
векторов1.
Отметим, что использование другого тестового набора данных T,
отличного и независимого от обучающего T, является общеприня-
тым подходом при проверке характеристик качества распознавания.
Пример 1.2. Распознавание по ближайшим соседям. Пусть про-
странство векторов признаков — метрическое2 (например
d), пространство откликов — любое; задана обучающая вы-
борка T (x ,t ),,(xN ,tN ) 1 1 . Рассмотрим решающее правило бли-
жайшего соседа (nearest neighbor — NN): y f x tm ( ) , где индекс m
определяется по обучающей выборке T из условия ближайшего для
x соседа в пространстве : ( , ) min ( , )
, ,
x x x x m k N k
1
. Ответим на сле-
дующие вопросы.
1. Как поступать в случае, если у входного вектора x в обучающей
выборке T имеется два или более ближайших соседа на одина-
ковом расстоянии?
2. Как обобщить распознавание по ближайшему соседу на рас-
познавание по K 2 ближайшим соседям (не обязательно
равноудаленным)?
◄ 1. Если пространство ответов — линейное, например n (век-
торная регрессия), то ответы ближайших соседей можно усреднить;
если пространство ответов — конечное с небольшим числом эле-
ментов, например {0, 1} (классификация на два класса), то из ответов
ближайших соседей можно выбрать самый частый. Возможен также
вариант, при котором отклик классификатора выбирается случай-
ным образом из откликов равноудаленных ближайших соседей.
1 Высокая размерность пространства признаков может привести
к тому, что необходимый для удовлетворительного обучения распознава-
теля объем N обучающей выборки оказывается невозможно обеспечить
или же обучение становится неприемлемо долгим. Это явление в машин-
ном обучении называют проклятием размерности (curse of dimensionality).
Очевидно также, что чем больше у модели распознавателя f настраивае-
мых параметров, тем больше ему требуется данных для обучения.
2 Это означает, что в пространстве определена метрика (расстоя-
ние) (u, v) 0 между любыми элементами u , v .
1.1. Задачи распознавания образов и машинного обучения 15
2. Отличие от п. 1 состоит только в том, что K ближайших
от распознаваемого вектора x соседей из выборки T не являются
в общем случае равноудаленными от x в пространстве . В осталь-
ном правила формирования отклика можно сохранить (усредне-
ние, выбор наиболее частого ответа, случайный выбор). ►
Укажем на некоторые характерные особенности и свойства рас-
познавателя по K ближайшим соседям (K nearest neighbors — K-NN):
• NN-распознаватель (K 1) не делает ни одной ошибки на предъ-
явленном ему наборе T и может ошибаться только на новых,
неизвестных ему векторах признаков;
• K-NN-распознаватель (K > 1) не всегда распознает точки обуча-
ющего набора T безошибочно, но при небольших K, как пра-
вило, меньше ошибается на неизвестных ему векторах по срав-
нению с вариантом K 1;
• для K N ближайших соседей, где N — объем обучающей вы-
борки T, распознаватель дает постоянный ответ, не зависящий
от входного вектора признаков x;
• обучение происходит тривиально и состоит в простом запоми-
нании обучающего набора. Распознавание также тривиально,
но его сложность растет пропорционально объему обучающей
выборки N;
• при малом количестве обучающих векторов N (когда простран-
ство признаков заполнено ими «слабо») метод работает плохо.
Поэтому при большой размерности пространства может ока-
заться необходим такой большой объем обучающего набора N,
который сделает применение распознавателя K-NN невозмож-
ным. Этот эффект является проявлением вышеупомянутой
проблемы проклятия размерности.
Упражнение 1.2. Исследуйте на практике характеристики распо-
знавателя K-NN. Для этого, используя какой-либо математиче-
ский программный пакет, проведите эксперименты по следующему
плану.
1. Создайте обучающий набор данных T из N 1000 векторов
(xi, ti), где x — наудачу выбранная из отрезка [0;1] величина,
t sin(5x/2) + , а — гауссова случайная величина с нулевым
математическим ожиданием и СКО 0,25.
16 Глава 1. Основные задачи, модели и подходы к машинному обучению
2. Создайте аналогичным образом тестовый набор данных T
из других N/4 250 векторов (xi, ti).
3. Выбирая различные значения K 1 (обязательно рассмотрите
случай K 1), определите среднюю ошибку (1.5) (штрафная
функция — квадрат разности ti и отклика распознавателя) для
обучающего T и для тестового T наборов данных. Постройте
зависимости средних ошибок от K в виде двух графиков.
4. По графикам, полученным в п. 3, сделайте выводы о характере
зависимости эмпирического риска (1.5) от K. Определите зна-
чение K, для которого значение ошибки (1.5) получается наи-
меньшим. Сравните значения ошибок, получаемых на обучаю-
щем и тестовом наборах данных.
Рассмотренная в этом разделе задача построения оптималь-
ного статистического распознавателя f по обучающей выборке
T (x , t ),, (xN , tN ) 1 1 относится к варианту машинного обуче-
ния с учителем, когда для каждого вектора признаков xi из обучаю-
щей выборки известен желаемый отклик распознавателя ti. В этом
случае говорят также, что обучающая выборка T размечена, т. е.
каждый вектор-образ xi из T заранее помечен «учителем» меткой ti.
Каждую пару (xi, ti) T называют также прецедентом, а обучение
с учителем — обучением по прецедентам.
На практике возникают также задачи, в которых имеется только
выборка из векторов признаков {x } i i
N
1, а их метки ti отсутствуют (не-
известны). В этом случае распознаватель должен осуществлять груп-
пировку данных по классам на основе обучающей выборки {x } i i
N
1 без
внешнего участия учителя [17, 20]. Вопросы, связанные с машин-
ным обучением без учителя, будут рассмотрены нами в главе 6.
1.2. Ñïîñîáíîñòü ðàñïîçíàâàòåëÿ
ê îáîáùåíèþ. Ïåðåîáó÷åíèå
è ðåãóëÿðèçàöèÿ
Рассмотрим простейший случай регрессии, когда образ объ-
екта является скаляром x (вектор признаков состоит из одной
компоненты), а желаемый отклик распознавателя, или «метка»
1.2. Способность распознавателя к обобщению. 17
Переобучение и регуляризация
объекта, — это также скалярная величина t, которая присвоена
ему по следующему правилу:
t g(x) + ,
где g(x) — некоторая неизвестная распознавателю функция;
— случайная величина с математическим ожиданием M[] 0
и дисперсией 2. Требуется построить оптимальный распознава-
тель f, дающий минимальное среднее значение функции штрафа
E(t, y) (t − y)2, где y f(x).
Очевидно, что средний по всей генеральной совокупности
штраф (1.1) будет минимальным, если для решающего правила
y f(x) выбрать f(x) g(x), так как x:
M ( ) M ( ) ( ) t y g x f x
2 2
g(x) f (x) M[ ] g(x) f (x) M[ ] g(x) f ( 2
0 0
2 2
2
x
g x f x
)
, () ()
2
0
2
при
.
Однако функция g(x) распознавателю неизвестна, поэтому необ-
ходимо построить ее аппроксимацию f(x) g(x) путем обучения
на выборке T x t x t N N ( , ), , ( , ) 1 1 , минимизируя эмпирический
риск (1.4) с функцией ошибки E(t, y) (t − y)2.
Пример 1.3. Как и в упражнении 1.2, наблюдаемые значения меток
будем формировать по правилу
t sin(5x/2) + , (1.6)
где — гауссова случайная величина с нулевым средним
и СКО 0,25. Решающую функцию y f(x) будем искать в про-
странстве алгебраических многочленов степени M, т. е. будем
использовать для распознавателя модель вида
y f x wxj
j
j
M
( )
0
. (1.7)
Таким образом, по наблюдаемой выборке T x t x t N N ( , ), , ( , ) 1 1
необходимо построить аппроксимацию f(x) sin(5x/2) в виде мно-
гочлена (1.7). Сделаем это для частного случая N 11 при некото-
рых значениях M и изучим способность полученных распознавате-
лей к обобщению, которая характеризуется малостью ошибок при
распознавании образов, отсутствовавших в обучающей выборке.
◄ Очевидно, что при M N 1 можно подобрать такие коэффици-
енты полинома (1.7), что для всех элементов обучающей выборки T
18 Глава 1. Основные задачи, модели и подходы к машинному обучению
получим yi f(xi) ti и, соответственно, нулевое значение для эм-
пирического риска (1.4).
Для порядков M < N 1 вектор коэффициентов w (w0, …, wM)T
полинома (1.7) будем искать, минимизируя по параметрам wj ква-
дратичную функцию (1.4) или (что даст тот же самый результат
при фиксированном значении N) функцию
E t f x i i
i
N
(w) ( )
1
2
2
1
, (1.8)
где множитель 1/2 включают в выражение для удобства его после-
дующего дифференцирования.
Выбрав x i i ( 1) 10 (i 1, …, 11) и сгенерировав признаки ti
по правилу (1.6), получим на плоскости (x, t) некоторые точки,
случайным образом отклоняющиеся по оси t от графика функ-
ции sin(5x/2) на значения реализации нормальной величины
(рис. 1.2). Эти точки будем использовать в качестве обучающей
выборки T (x , t ), , (x , t ) 1 1 11 11 .
Методом наименьших квадратов найдем на этой выборке коэф-
фициенты w* w*, ,w* M
T
0 полиномов (1.7) порядка M 0, 1, …, 10,
которые обращают в минимум штраф (1.8). Графики полученных
полиномов (1.7) для M 1, 3, 6, 10 приведены на рис. 1.3.
Как и следовало ожидать, полином-прямая (M 1) дает пло-
хое приближение функции sin(5x/2). Хотя полином десятого
порядка и обеспечивает нулевую ошибку приближения в точ-
ках заданной обучающей последовательности T (и только в них),
полином шестого порядка
(M 6) дает визуально лучшее
приближение. Таким обра-
зом, анализ графиков рис. 1.3
позволяет предположить, что
увеличение порядка аппро-
ксимирующего алгебраиче-
ского полинома сначала повы-
шает точность аппроксимации
«скрытой» функции g(x) [в на-
шем примере g(x) sin(5x/2)],
а затем точность приближения
ухудшается.
0 0,2 0,4 0,6 0,8 1
–1,5
–1
–0,5
0
0,5
1
1,5
t
x
Рис. 1.2. График функции sin(5x/2)
(штриховая кривая) и точки обуча-
ющей выборки (11 шт.)
1.2. Способность распознавателя к обобщению. 19
Переобучение и регуляризация
Для изучения способности распознавателя к обобщению ис-
следуем среднюю ошибку распознавания на тестовой выборке
T, полученной по тому же правилу (1.6), но не содержащей дан-
ные, которые были включены в обучающую последовательность.
Для того чтобы можно было сравнивать выборки разного объе-
ма, от (1.8) вернемся к измерению среднего эмпирического риска
(1.4). На рис. 1.4 приведены значения среднеквадратичной ошибки
распознавания
E
N
t f x RMS n n
n
N
1 2
1
( )
[квадратного корня из (1.4)], полученные на рассмотренной обучаю-
щей выборке T из N 11 элементов, а также на независимо сгенери-
рованной по правилу (1.6) тестовой выборке T (x , t ),, (x , t ) 1 1 101 101
0 0,2 0,4 0,6 0,8 1
–1,5
–1
–0,5
0
0,5
1
1,5
t M = 1
x
0 0,2 0,4 0,6 0,8 1
–1,5
–1
–0,5
0
0,5
1
1,5
t M = 3
x
0 0,2 0,4 0,6 0,8 1
–1,5
–1
–0,5
0
0,5
1
1,5
t M = 6
x
0 0,2 0,4 0,6 0,8 1
–1,5
–1
–0,5
0
0,5
1
1,5
t M = 10
x
Рис. 1.3. Полиномы наилучшего (для заданной выборки) квадра-
тичного приближения порядка M. При M 10 ошибка
приближения равна нулю
20 Глава 1. Основные задачи, модели и подходы к машинному обучению
(N 101), для которой была взята сетка значений xi (i 1)/100
(i 1, …, 101).
Из рис. 1.4 видно, что на тестовой выборке среднеквадратич-
ные ошибки распознавания принимают наименьшие и примерно
одинаковые значения для полиномов, имеющих порядок 4 M 9.
Причем при одном и том же порядке M ошибка на тестовой выбор-
ке всегда больше ошибки на обучающей выборке.
При M 10, когда ошибку на обучающей выборке становится
возможным обратить в ноль, ошибка на тестовой выборке резко
возрастает. Если посмотреть на график соответствующего поли-
нома, у которого появляются большие осцилляции относительно
графика функции sin(5x/2) (см. рис. 1.3), то это не покажется уди-
вительным. Как можно видеть из табл. 1.1, рост осцилляций поли-
нома десятого порядка сопровождается значительным увеличени-
ем абсолютных величин коэффициентов w* (w*, ,w* ) . M
T
0
Эффект резкого увеличения средней ошибки на тестовой
выборке при увеличении количества варьируемых параметров
модели распознавателя (т. е. при увеличении сложности модели,
которая в нашем примере характеризуется значением M) называ-
ется переобучением распознавателя. Термин «переобучение» пони-
мается как чрезмерное, а не повторное обучение (overlearning, или
overfi tting, — чрезмерная под-
гонка под обучающие данные).
При большом количестве па-
раметров модели, используе-
мой для решающей функции
f, и малом объеме обучающей
выборки часто оказывается
возможным настроить модель
так, что распознаватель как
бы «запоминает» обучаю-
щие данные и дает для них
вообще нулевую ошибку (мы
это наблюдали в примере
1.2, где запоминание данных
происходило в буквальном
смысле). Вместе с тем каждый
0 2 4 6 8 10
Порядок полинома
0
0,2
0,4
0,6
0,8
1
1,2
Среднеквадратичная ошибка
Ошибка на тестовой выборке
Ошибка на обучающей выборке
Рис. 1.4. Среднеквадратичная ошиб-
ка распознавания ERMS, полученная
на обучающей выборке из 11 элемен-
тов и тестовой выборке из 101 эле-
мента для моделей полиномов (1.7)
разных порядков M 0, 1, …, 10
1.2. Способность распознавателя к обобщению. 21
Переобучение и регуляризация
прецедент в обучающей выборке предполагает наличие некото-
рого случайного фактора ошибки, содержащегося в присвоенной
учителем метке [как и в нашем примере, см. (1.6)], поэтому точное
запоминание прецедентов при обучении распознавателя лишено
смысла. Переобучение распознавателя влечет за собой ухудшение
его способности к обобщению, т. е. к распознаванию «незнакомых»
новых образов с малой средней ошибкой.
Для предотвращения переобучения необходимо, чтобы коли-
чество настраиваемых независимых параметров модели распо-
знавателя было намного меньше объема обучающей выборки. По-
смотрим, как для нашего примера с моделью решающей функции
(1.7) и правилом разметки (1.6) меняется способность распозна-
вателя к обобщению при увеличении объема обучающей выбор-
ки N. Графики решающей функции f(x) (полиномов наилучшего
среднеквадратичного приближения десятого порядка, получен-
ных на обучающих выборках объемов N 21 и N 101) приведе-
ны на рис. 1.5. Как и следовало ожидать, точность приближения
функции sin(5x/2) полиномом (1.7) повышается с увеличением
объема обучающей выборки.
Таблица 1.1. Коэффициенты полинома (1.7) порядка M, получен-
ные по обучающей выборке объема N 11 методом
наименьших квадратов
M 1 M 3 M 6 M 10
w0
* 0,3596 0,4272 0,2725 0,2725
w1
* 0,2856 4,401 0,9053 279,38
w2
* 0 19,05 73,14 7 524
w3
* 0 15,47 350,78 81 700
w4
* 0 0 547,67 472 947
w5
* 0 0 312,68 1 632 833
w6
* 0 0 43,95 3 530 061
w7
* 0 0 0 4 822 552
w8
* 0 0 0 4 042 083
w9
* 0 0 0 1 896 384
w10
* 0 0 0 381 133
22 Глава 1. Основные задачи, модели и подходы к машинному обучению
К сожалению, объем N реально имеющейся для обучения рас-
познавателя выборки часто оказывается недостаточным. В этом
случае для исключения эффекта переобучения применяется регу-
ляризация, которая состоит в добавлении в функцию эмпириче-
ского риска некоторого неотрицательного слагаемого, дополни-
тельно штрафующего за каждый выбор того или иного вектора
параметров w в модели решающей функции.
Большие абсолютные значения весов w* (w*, ,w* ) M
T
0 в моде-
ли (1.7) нежелательны и должны штрафоваться сильнее, так как
увеличивают осцилляцию решающей функции. Для рассматри-
ваемого примера модели (1.7) введем дополнительное слагаемое
регуляризации, например квадрат нормы вектора параметров1
w ww 2 2
0 T
k k
M w . Тогда новая функция штрафа, полученная
в результате регуляризации, будет выглядеть для решающего пра-
вила f(x) (1.7) следующим образом:
E t f x i i
i
N
(w) ( ) w
1
2 2
2
1
2 , (1.9)
где параметр 0 задает баланс между «значимостями» штрафа
за ошибку распознавания и штрафа за величину абсолютных зна-
чений весов модели (1.7). Как и ранее, дополнительный множитель
1 Поскольку коэффициент w0 влияет лишь на смещение по оси аб-
сцисс функции (1.7) и не влияет на «размах» ее осцилляций, параметр w0
часто не учитывается при подсчете квадрата нормы вектора w.
0 0,2 0,4 0,6 0,8 1
–1,5
–1
–0,5
0
0,5
1
1,5
N = 21
t
x 0 0,2 0,4 0,6 0,8 1
–1,5
–1
–0,5
0
0,5
1
1,5
N = 101
t
x
Рис. 1.5. Полиномы (1.7) наилучшего квадратичного прибли-
жения порядка M 10 (сплошная кривая), полученные
на выборках объема N 21 (слева) и N 101 (справа). Срав-
ните с рис. 1.3
1.2. Способность распознавателя к обобщению. 23
Переобучение и регуляризация
1/2 в слагаемом регуляризации введен для удобства последующего
дифференцирования; конкретное значение веса определяется
экспериментально.
На рис. 1.6 приведены графики полиномов (1.7) десятого по-
рядка, полученных на исходной (см. рис. 1.2) выборке из N 11
элементов в результате минимизации функции (1.9) для значений
10−10 и 1. Заметим, что случаю 0 (отсутствие регуляри-
зации) будет соответствовать правый нижний график на рис. 1.3.
Видим, что при 10−10 (рис. 1.6, график слева) полученная ре-
шающая функция f(x) приближает функцию sin(5x/2) намного
лучше, чем в случае отсутствия регуляризации, но все же хуже той
решающей функции, которая была найдена по обучающей выбор-
ке объема N 101 (правый график на рис. 1.5).
0 0,2 0,4 0,6 0,8 1
–1,5
–1
–0,5
0
0,5
1
1,5
= 10–10
t
x 0 0,2 0,4 0,6 0,8 1
–1,5
–1
–0,5
0
0,5
1
1,5
= 1
t
x
Рис. 1.6. Графики решающих функций (1.7) порядка M 10, полу-
ченных в результате минимизации штрафа (1.9) со сла-
гаемым регуляризации
Значения весовых коэффициентов w* (w*, ,w* ) M
T
0 , получен-
ных при использовании регуляризации, представлены в табл. 1.2.
Как и следовало ожидать, введение слагаемого регуляризации
уменьшило абсолютные величины коэффициентов полинома (1.7).
На рис. 1.7 приведены зависимости среднеквадратичной ошиб-
ки распознавания ERMS от значения параметра из (1.9), получен-
ные на тех же обучающей T (11 элементов, см. рис. 1.2) и тестовой
T (101 элемент) выборках, которые использовались для построе-
ния графиков рис. 1.4. Видим, что выбор 10−8 позволяет полу-
чить для решающей функции полинома порядка M 10 примерно
24 Глава 1. Основные задачи, модели и подходы к машинному обучению
такую же ошибку распознавания на тестовой выборке, которая
имела место ранее без применения регуляризации для лучшего ва-
рианта полинома порядка M 6.
В рассмотренном нами при-
мере модели распознавателя
(1.7) использование сложных ре-
шающих функций (c порядком
полинома M > 4) при обучающей
выборке объема N 11 оказалось
практически лишенным смыс-
ла, так как крайне незначитель-
но влияло на изменение ошибки
распознавания. Однако в общем
случае применение более слож-
ных моделей с большим коли-
чеством параметров способно
потенциально понизить ошибку
распознавания. При этом воз-
можно возникновение проблем
–15 –10 –5 0 lg
0
0,2
0,4
0,6
0,8
1
Ошибка на тестовой выборке
Ошибка на обучающей выборке
Среднеквадратичная ошибка
Рис. 1.7. Среднеквадратичная
ошибка распознавания ERMS, по-
лученная для разных значений
параметра функции штрафа (1.9)
на обучающей выборке из 11 эле-
ментов и тестовой выборке из 101
элемента для полинома (1.7) по-
рядка M 10
Таблица 1.2. Коэффициенты полинома (1.7) порядка M 10, по-
лученные по обучающей выборке объема N 11 при
использовании регуляризации
0 1010 1
w0
* 0,2725 0,2723 0,2728
w1
* 279,38 0,5698 0,3686
w2
* 7524 44,9265 0,2124
w3
* 81 700 169,4394 0,0281
w4
* 472 947 65,4488 0,0908
w5
* 1 632 833 82,4711 0,1542
w6
* 3 530 061 466,8941 0,1812
w7
* 4 822 552 577,2536 0,1862
w8
* 4 042 083 688,525 0,1785
w9
* 1 896 384 1284,8539 0,1641
w10
* 381 133 509,5763 0,1463
1.2. Способность распознавателя к обобщению. 25
Переобучение и регуляризация
обучения сложных моделей из-за необходимости использования
нереально больших объемов обучающих выборок. Эффективным
средством повышения качества обучения на выборках недостаточ-
ного объема является регуляризация, другие примеры и варианты
которой встретятся нам в следующих главах. ►
Удобным свойством часто используемой функции штрафа (1.8)
с полиномиальной моделью (1.7) является ее выпуклость, вслед-
ствие чего равенство нулю градиента E(w) 0 является не толь-
ко необходимым, но и достаточным условием минимума этой
функции.
Напомним, что функция F(x) является выпуклой на выпуклой
области D, если x1 D, x2 D:
F x x F x F x 1 2 1 2 (1 ) ( )(1 ) ( )
при любых значениях [0; 1].
Пример 1.4. Показать, что функция E(w) в (1.8) выпуклая.
◄ Подставим выражение для f(x) из (1.7) в (1.8):
E t w x E i j i
j
j
M
i
N
i
i
N
(w) (w)
1
2 0
2
1 1
, где E t w x i i j i
j
j
M
(w)
1
2 0
2
.
Для частных производных квадратичной функции Ei(w) имеем:
w
E
w
t wx x t wx
k
i
k
i j i
j
j
M
i
k
i j i
j
j
M
(w)
1
2 0
2
0
, k 0, 1, …, M;
2
w w
E x x x
k m
i i
k
i
m
i
(w) k m , k 0, 1, …, M; m 0, 1, …, M.
Для выпуклости квадратичной функции Ei(w) необходимо
и достаточно, чтобы матрица вторых производных (матрица Гессе)
H w i
k m
i
k m
M
i
k m
k m
M
w w
E x
2
0
0
( )
,
,
была положительно полуопределенной. Поскольку для любого
вектора y (y0, y1, …, yM)T квадратичная форма
yTH y
i i
k m
k m
m
M
k
M
i
k
k i
m
m
m
M
k
M
i
n
n
n
M
x y y x y x y x y
0 0 0 0 0
2
0,
26 Глава 1. Основные задачи, модели и подходы к машинному обучению
то матрица Hi положительно полуопределена, а функция Ei(w) вы-
пуклая. Функция E(w) (1.8) является выпуклой как сумма выпук-
лых функций Ei(w). ►
Упражнение 1.3. Покажите, что при использовании модели (1.7)
в функции штрафа (1.8) выражения для оптимальных коэффици-
ентов w* (w*, ,w* ) M
T
0 , обращающих в минимум (1.8), находятся
по обучающей выборке T x t x t N N ( , ),, ( , ) 1 1 в результате решения
следующей системы линейных уравнений:
a w b i j j
j
M
, i
0
, i 0, …, M, (1.10)
где a x i j n
i j
n
N
,
1
, b tx i n n
i
n
N
1
.
Убедитесь, что с использованием обозначений
X
x x x
x x x
x x x
x x
x
M
M
N N N
M
M
1
0
1
1
1
2
0
2
1
2
0 1
1 1 1
1
2 2
1
x
x x
M
N N
M
, t
t
t
tN
1
2
систему уравнений (1.10) можно представить в матричном виде
следующим образом: Aw b, где A XT X и b XT t. Причем в обо-
значениях примера 1.4 A H i i
N
1 , поэтому матрица A симметри-
ческая и положительно полуопределена.
Оказывается, что рассмотренную в примере 1.3 процедуру ре-
гуляризации, состоящую во включении в выражение для штраф-
ной функции ошибки распознавания дополнительного слагаемого
штрафа за выбор конкретных параметров модели, можно интер-
претировать как определенную модификацию системы уравнений
(1.10), направленную на повышение устойчивости ее решения1.
Поясним это утверждение.
Если матричное уравнение вида Aw b имеет плохо обусловлен-
ную матрицу A, т. е. число обусловленности (A) 1, то решение
1 Общая теория метода регуляризации, используемого для решения
некорректных задач, приводящих к плохо обусловленным системам ли-
нейных уравнений, разработана академиком А. Н. Тихоновым и его шко-
лой в 60-х гг. XX в.
1.2. Способность распознавателя к обобщению. 27
Переобучение и регуляризация
уравнения w A1b является неустойчивым1. Для симметрических
положительно полуопределенных матриц число обусловленности
выражается через собственные числа (которые являются неот-
рицательными) как (A) max/min, поэтому у плохо обусловлен-
ных матриц max min. В частности, для вырожденной матрицы
min 0 и (A) .
Если «поправить» симметрическую положительно полуопреде-
ленную матрицу следующим образом: A A + E, где скаляр 0,
E — единичная матрица, то собственные векторы у новой матрицы
A останутся теми же, а собственные числа станут больше на вели-
чину . Действительно, обозначив для матрицы A некоторый соб-
ственный вектор и соответствующее ему собственное число как rk
и k, для матрицы A получаем: Ar r k k k ( ) . По этой причине
для новой (также симметрической и положительно полуопреде-
ленной) матрицы число обусловленности уменьшится:
( ) max ( )
min
max
min
A A ,
и устойчивость решения w (A)1b повысится. Добавление сла-
гаемого регуляризации в (1.9) приводит к подобной модификации
системы уравнений (1.10).
Упражнение 1.4. Убедитесь, что функция (1.9) является выпуклой
и покажите, что замена штрафа (1.8) на (1.9) приводит к опти-
мальным параметрам w* (w*, ,w* ) M
T
0 модели (1.7), определяе-
мым системой линейных уравнений (A E)w b, полученной
из Aw b (1.10).
В примере 1.3 полиномиальная модель использовалась для
решающей функции распознавателя y f(x) в простейшем случае,
когда вектор признаков x был однокомпонентным, т. е. скаляром
(x x). Если размерность пространства признаков dim d 1, то
количество параметров, задающих алгебраический полином сте-
пени M, будет заметно больше, чем M + 1. Чему оно равно?
1 Такая ситуация имеет место, в частности, для системы линейных
уравнений (1.10), которая была получена в примере 1.3 на выборке объема
N 11 с полиномом (1.7) порядка M 10.
28 Глава 1. Основные задачи, модели и подходы к машинному обучению
Пример 1.5. Подсчитать количество параметров, задающих алге-
браический полином степени M от d переменных x1, …, xd.
◄ Рассматриваемый алгебраический полином имеет следующий
общий вид:
P x x w w x w x x d ii
i
d
i i i i
i
d
i
d
i
d
( 1, , ) 0 ,
1 1 1
1
1 2 1 2
1 2
2
i
d
i i i i i i
i
d
w xx x
M M
1 M
1 2 1 2
1 1
, , , .
Постоянная составляющая полинома определяется одним
параметром w0. В первой сумме, определяющей линейную часть
полинома, имеем s1(d) d параметров w1, …, wd.
В двойной сумме, определяющей квадратичную форму, пара
коэффициентов wi,j и wj,i при i j соответствует подобным слагае-
мым и поэтому определяет только один параметр ai,j в квадратич-
ной части полинома: w xx w x x a xx i, j i j j,i j i i, j i j ; обычно для симме-
трии принимают wi,j wj,i ai,j/2. Тогда количество независимых
параметров ai,j в квадратичной части полинома:
s d
i j i j
i j i j
d d
d
d d
2
2
2 2
1
2
( )
( , )
( , )
( )
,
где обозначение A принято для количества элементов в
множестве A.
Обобщим способ подсчета параметров, использованный выше
для квадратичной части полинома. Для того чтобы определить ко-
личество sk коэффициентов-параметров в k-кратной сумме
i
d
i
d
i i i i i i
i
d
w xx x
k k
1 2 k
1 2 1 2
1 1 1
, , , ,
которые останутся после приведения подобных слагаемых, необ-
ходимо подсчитать количество различных комбинаций (i1, i2, …, ik),
не различающихся порядком следования индексов, но с возмож-
ностью их повторений. Воспользуемся формулой для количества
сочетаний с повторениями из d по k:
s d C C
d k
d k k d
k
d k
( ) k
( )!
( )! !
1
1
1
.
Заметим, что эта формула является верной и для уже найденных
нами значений s0(d) 1, s1(d) d, s2(d) d(d + 1)/2.
1.3. Применение формулы Байеса для оценок параметров моделей 29
В итоге количество параметров полинома порядка M от d пере-
менных получаем равным
S d s d
d k
d k
S d
d M
d M k
k
M
k
M
M ( ) ( )
( )!
( )! !
( )
( )!
(
0 0
1
1
1
1
1)! !
( )!
M ! !
d M
d M
.
Последнее равенство обоснуйте самостоятельно методом мате-
матической индукции, обратив сначала внимание на то, что ито-
говое выражение верно для S0(d) и S1(d). Тогда в предположении
его применимости для SM−1(d) нужно показать справедливость по-
лученного выражения для SM(d). ►
Таким образом, количество числовых параметров, определяю-
щих алгебраический полином порядка M от d переменных, равно
S d
d M
d M M( )
( )!
! !
. (1.11)
Упражнение 1.5. Покажите, что порядок величины (1.11)
SM(d) O(dM) при d M и SM(d) O(Md) при M d, воспользо-
вавшись формулой Стирлинга n! 2nennn , применяемой для
аппроксимации факториала при больших значениях n.
Рост числа параметров полиномиальной модели, наблюдаемый
при увеличении размерности пространства векторов признаков,
представляет собой пример проклятия размерности.
1.3. Ïðèìåíåíèå ôîðìóëû Áàéåñà
äëÿ îöåíîê ïàðàìåòðîâ ìîäåëåé
Напомним понятие условной вероятности. Пусть A и B — некото-
рые случайные события. Условной вероятностью события B при
условии, что произошло событие A, называется величина
P B A
P AB
P A
( | )
( )
( )
,
где P(AB) — вероятность совместной реализации событий A и B;
P(A) — вероятность события A.
Формула Байеса получается непосредственно из приведенного
определения условной вероятности:
Предлагаемое вниманию читателя пособие было написано как
часть методического обеспечения (не включающая лабораторный
практикум) учебного курса «Распознавание образов и машинное
обучение», который на протяжении ряда лет читался автором в на-
циональном исследовательском университете МИЭТ. Этот курс
является введением в научную дисциплину, которая представляет
собой один из краеугольных камней такой крайне важной и бур-
но развивающейся области знаний, как искусственный интеллект
(ИИ).
В начале 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).
В тексте пособия используется двойная нумерация для рисун-
ков, формул, примеров и упражнений: первая цифра обозначает
главу, вторая — порядковый номер формулы (рисунка, примера,
упражнения) в главе. Начало и окончание решений примеров обо-
значается соответственно символами ◄ и ►.
ÃËÀÂÀ 1
ÎÑÍÎÂÍÛÅ ÇÀÄÀ×È,
ÌÎÄÅËÈ È ÏÎÄÕÎÄÛ
Ê ÌÀØÈÍÍÎÌÓ
ÎÁÓ×ÅÍÈÞ
1.1. Çàäà÷è ðàñïîçíàâàíèÿ îáðàçîâ
è ìàøèííîãî îáó÷åíèÿ
Приведем сначала некоторые примеры практических задач, отно-
сящихся к предметной области распознавания образов:
• распознавание людей по фотографиям лиц;
• распознавание рукописного текста;
• распознавание речи (голосовых команд);
• медицинская диагностика заболеваний;
• геологическая диагностика;
• экономическое прогнозирование и т. д.
При теоретическом рассмотрении подобных задач под терми-
ном «распознавание образов» мы будем понимать отнесение объ-
екта к тому или иному классу из конечного множества (задача
классификации) или нахождение некоторого скалярного (вектор-
ного) значения, характеризующего определенные скрытые свой-
ства объекта (задача регрессии) [8, 15, 20, 21, 23]. Для распознавания
объектов используется их описание c помощью образов.
Так, в задачах медицинской диагностики объектами будут
пациенты, а их образами — результаты анализов и другие число-
вые характеристики, такие как возраст, вес и т. п. Задача класси-
фикации в данном случае может состоять в отнесении пациента
к здоровым или к больным (возможно, больным конкретным
10 Глава 1. Основные задачи, модели и подходы к машинному обучению
заболеванием). Задачей регрессии будет, например, получение
оценки вероятности полного выздоровления пациента после
лечения.
Числовые характеристики, используемые для классификации
образов, называются признаками. Признак — это некоторое коли-
чественное измерение объекта произвольной природы, а сформи-
рованный из них вектор признаков как раз и представляет собой
образ объекта.
Пример 1.1. Рассмотрим задачу диагностики опухолей по результа-
там биопсии. Положим, что доброкачественные (класс А) и злока-
чественные (класс Б) изменения дают разную оптическую картину
при изучении под микроскопом: гистологические образцы отли-
чаются интенсивностью и контрастностью изображения. Для фор-
мирования вектора признаков будем использовать две числовых
характеристики: среднее значение и среднеквадратичное откло-
нение яркости пикселей в цифровом изображении гистологиче-
ского образца. Предположим, что имеется база данных образцов
(рис. 1.1), для которых известна их правильная классификация:
принадлежность к классам A (кружки) и Б (треугольники).
Множества точек, соответствующие образцам разных классов,
на плоскости признаков (, ) в данном случае разделимы прямой
линией. Классификация неизвестного образа (соответствующая
точка обозначена на плоскости признаков звездочкой) состоит
в проверке положения этой точки
относительно разделяющей прямой.
Для приведенного на рис. 1.1 при-
мера объект будет отнесен по его
образу к классу А (доброкачествен-
ная опухоль).
Таким образом, далее в распо-
знавании образов мы будем выделять
задачи двух типов: регрессии и клас-
сификации. В математике регрес-
сия — это условное математическое
ожидание одной случайной величи-
ны относительно других; во многих
Б
А
Рис. 1.1. Иллюстрация к
примеру 1.1
1.1. Задачи распознавания образов и машинного обучения 11
задачах «распознавательная» регрессия (нахождение скалярной или
векторной численной характеристики объекта) оказывается именно
математической регрессией относительно вектора признаков.
Классификацией называем распознавание качественной (дис-
кретной) характеристики объекта k {1, …, q}, где q — число клас-
сов, а множество k объектов, для которых эта характеристика
принимает значение k K, называем K-м классом.
Как мы позднее увидим, ответ распознавателя-классифика-
тора лучше получать не как номер класса k, а как q-мерный вектор
y (y1, …, yq)T «уверенностей» в принадлежности объекта к каж-
дому из классов (часто компонента yk — это вероятность принад-
лежности объекта к классу k). Тогда, определяя номер класса K
по максимальной компоненте выходного вектора классификатора
как K y
k q
k
arg max
{1,, }
, мы сводим задачу классификации к частному
случаю векторной регрессии. Далее мы будем полагать, что при
классификации объектов на q классов отклик распознавателя
представляет собой вектор y q.
Упражнение 1.1. Приведите практические примеры задач регрес-
сии и задач классификации.
Для построения распознавателя необходимо задать решающее
правило, т. е. функцию f, определяющую отображение пространства
векторов признаков (образов) в пространство откликов распо-
знавателя . Термины «решающая функция» и «решающее правило»
мы будем понимать как синонимы для термина «распознаватель».
Чаще всего исходные данные для нахождения решающего
правила представлены только обучающей выборкой, т. е. набором
пар T n n n
N (x , t ) 1, где скаляр или вектор tn — это желаемый
результат распознавания образа xn . По обучающей выборке не-
обходимо подобрать решающую функцию f так, чтобы распозна-
вание образов было оптимальным, т. е. «наилучшим» в каком-то
смысле (для этого необходимо определить способ оценки качества
распознавания). Для функции распознавателя f могут использо-
ваться различные модели, подбор параметров этих моделей (чаще
всего итерационный) по выборке T n n n
N (x , t ) 1 называется обуче-
нием распознавателя. Такое статистическое обучение распознава-
теля называют также машинным обучением.
12 Глава 1. Основные задачи, модели и подходы к машинному обучению
Перейдем теперь к формальной постановке задачи построения
оптимального статистического распознавателя f по обучающей
выборке T. Сначала необходимо задать следующие исходные усло-
вия задачи [4].
1. Пространство векторов признаков , точками которого коди-
руются распознаваемые объекты (например d-мерное евкли-
дово пространство d).
2. Пространство ответов , точками которого кодируются ре-
зультаты распознавания (например q-мерное пространство q).
3. Пространство распознавателей f: . В случае евклидо-
вых пространств и , например, непрерывных, дифференци-
руемых, линейных, полиномиальных и т. п.
4. Пространство распределений (вероятностных мер) на ,
которые удовлетворяют каким-либо специфическим для за-
дачи условиям. В случае евклидовых пространств и этими
условиями могут быть непрерывность функции плотности, ее
представимость в виде гауссовых смесей и т. п.
5. Функция штрафа E: (называемая также функцией
ошибки, потерь, риска и т. п.), как правило, неотрицательная
и равная нулю при совпадении прогнозного ответа y с верным
ответом t. Например, в случае евклидова пространства при-
меняется квадратичный штраф
E(t,y) t y 2, (1.1)
а в случае дискретного пространства — бинарный штраф
E(t,y) t y
t y
0
1
при
при . (1.2)
6. Обучающий набор T N N (x ,t ),,(x ,t ) 1 1 , состоящий из пар (век-
тор признаков, желаемый ответ распознавателя) (xi, ti) ,
которые считаются значениями независимых случайных век-
торных величин с одним и тем же неизвестным распределени-
ем .
Обозначив для распределения функцию плотности ве-
роятности как p(x, t), оптимальным будем считать такой распо-
знаватель f , который при выполнении условий 1–6 доставляет
минимум математического ожидания функции штрафа [4]:
E f E f E f p d d
f ( ) M ( ), ( ), ( , ) min
( , )
x t x t x t x t
x t
. (1.3)
1.1. Задачи распознавания образов и машинного обучения 13
Однако в нашем распоряжении имеется только выборка T,
взятая из генеральной совокупности с неизвестным распределе-
нием . Совершенно очевидно, что при неизвестной плотности
распределения вероятностей p(x, t) определить минимум в (1.3)
невозможно и задача построения оптимального распознавателя f
в приведенной выше формулировке неразрешима. По этой причи-
не придется заменить в (1.3) математическое ожидание штрафа его
оценкой по выборке T:
E EfTN
f E f i i
i
N
( ) ( , ) ( ),
1
1
x t , (1.4)
и вместо (1.3) рассматривать минимизацию среднего штрафа обуче-
ния, или эмпирического риска1
E f T
N
E f i i
i
N
f
( , ) ( ), min
1
1
x t
. (1.5)
При замене (1.3) на (1.5) возникает вопрос о том, насколько это
влияет на итоговые характеристики распознавателя, прежде всего
на его способность к обобщению, т. е. насколько успешно будет рабо-
тать распознаватель, когда после обучения ему будут предъявлены
новые образы, отсутствовавшие в обучающей выборке T, по кото-
рой настраивалось решающее правило f. Сделаем по этому поводу
следующие важные замечания.
• Распознаватель, который получен в результате обучения, ми-
нимизирующего штраф (1.5), зависит от обучающего набора
данных T, а приближение (1.4) справедливо для функций f,
не зависящих от выборки T. В частности, как мы увидим позд-
нее, на обучающем наборе иногда можно добиться даже нуле-
вого среднего штрафа (1.5).
• Математическое ожидание штрафа (1.3) можно оценить бо-
лее корректно, взяв другой независимый от T набор тесто-
вых данных T N N (x , t ), , (x , t ) 1 1 той же природы (из той
же генеральной совокупности), что и выборка T, и посчитав
по (1.4) средний штраф тестирования E(f, T). Результат почти
наверняка будет хуже: E( f ,T ) E( f ,T ) , особенно при большой
1 Поиск решающей функции y f(x) минимизацией эмпирического
риска (1.5) с квадратичным штрафом (1.1) представляет собой смысловое
содержание метода наименьших квадратов.
14 Глава 1. Основные задачи, модели и подходы к машинному обучению
размерности пространства и малом количестве обучающих
векторов1.
Отметим, что использование другого тестового набора данных T,
отличного и независимого от обучающего T, является общеприня-
тым подходом при проверке характеристик качества распознавания.
Пример 1.2. Распознавание по ближайшим соседям. Пусть про-
странство векторов признаков — метрическое2 (например
d), пространство откликов — любое; задана обучающая вы-
борка T (x ,t ),,(xN ,tN ) 1 1 . Рассмотрим решающее правило бли-
жайшего соседа (nearest neighbor — NN): y f x tm ( ) , где индекс m
определяется по обучающей выборке T из условия ближайшего для
x соседа в пространстве : ( , ) min ( , )
, ,
x x x x m k N k
1
. Ответим на сле-
дующие вопросы.
1. Как поступать в случае, если у входного вектора x в обучающей
выборке T имеется два или более ближайших соседа на одина-
ковом расстоянии?
2. Как обобщить распознавание по ближайшему соседу на рас-
познавание по K 2 ближайшим соседям (не обязательно
равноудаленным)?
◄ 1. Если пространство ответов — линейное, например n (век-
торная регрессия), то ответы ближайших соседей можно усреднить;
если пространство ответов — конечное с небольшим числом эле-
ментов, например {0, 1} (классификация на два класса), то из ответов
ближайших соседей можно выбрать самый частый. Возможен также
вариант, при котором отклик классификатора выбирается случай-
ным образом из откликов равноудаленных ближайших соседей.
1 Высокая размерность пространства признаков может привести
к тому, что необходимый для удовлетворительного обучения распознава-
теля объем N обучающей выборки оказывается невозможно обеспечить
или же обучение становится неприемлемо долгим. Это явление в машин-
ном обучении называют проклятием размерности (curse of dimensionality).
Очевидно также, что чем больше у модели распознавателя f настраивае-
мых параметров, тем больше ему требуется данных для обучения.
2 Это означает, что в пространстве определена метрика (расстоя-
ние) (u, v) 0 между любыми элементами u , v .
1.1. Задачи распознавания образов и машинного обучения 15
2. Отличие от п. 1 состоит только в том, что K ближайших
от распознаваемого вектора x соседей из выборки T не являются
в общем случае равноудаленными от x в пространстве . В осталь-
ном правила формирования отклика можно сохранить (усредне-
ние, выбор наиболее частого ответа, случайный выбор). ►
Укажем на некоторые характерные особенности и свойства рас-
познавателя по K ближайшим соседям (K nearest neighbors — K-NN):
• NN-распознаватель (K 1) не делает ни одной ошибки на предъ-
явленном ему наборе T и может ошибаться только на новых,
неизвестных ему векторах признаков;
• K-NN-распознаватель (K > 1) не всегда распознает точки обуча-
ющего набора T безошибочно, но при небольших K, как пра-
вило, меньше ошибается на неизвестных ему векторах по срав-
нению с вариантом K 1;
• для K N ближайших соседей, где N — объем обучающей вы-
борки T, распознаватель дает постоянный ответ, не зависящий
от входного вектора признаков x;
• обучение происходит тривиально и состоит в простом запоми-
нании обучающего набора. Распознавание также тривиально,
но его сложность растет пропорционально объему обучающей
выборки N;
• при малом количестве обучающих векторов N (когда простран-
ство признаков заполнено ими «слабо») метод работает плохо.
Поэтому при большой размерности пространства может ока-
заться необходим такой большой объем обучающего набора N,
который сделает применение распознавателя K-NN невозмож-
ным. Этот эффект является проявлением вышеупомянутой
проблемы проклятия размерности.
Упражнение 1.2. Исследуйте на практике характеристики распо-
знавателя K-NN. Для этого, используя какой-либо математиче-
ский программный пакет, проведите эксперименты по следующему
плану.
1. Создайте обучающий набор данных T из N 1000 векторов
(xi, ti), где x — наудачу выбранная из отрезка [0;1] величина,
t sin(5x/2) + , а — гауссова случайная величина с нулевым
математическим ожиданием и СКО 0,25.
16 Глава 1. Основные задачи, модели и подходы к машинному обучению
2. Создайте аналогичным образом тестовый набор данных T
из других N/4 250 векторов (xi, ti).
3. Выбирая различные значения K 1 (обязательно рассмотрите
случай K 1), определите среднюю ошибку (1.5) (штрафная
функция — квадрат разности ti и отклика распознавателя) для
обучающего T и для тестового T наборов данных. Постройте
зависимости средних ошибок от K в виде двух графиков.
4. По графикам, полученным в п. 3, сделайте выводы о характере
зависимости эмпирического риска (1.5) от K. Определите зна-
чение K, для которого значение ошибки (1.5) получается наи-
меньшим. Сравните значения ошибок, получаемых на обучаю-
щем и тестовом наборах данных.
Рассмотренная в этом разделе задача построения оптималь-
ного статистического распознавателя f по обучающей выборке
T (x , t ),, (xN , tN ) 1 1 относится к варианту машинного обуче-
ния с учителем, когда для каждого вектора признаков xi из обучаю-
щей выборки известен желаемый отклик распознавателя ti. В этом
случае говорят также, что обучающая выборка T размечена, т. е.
каждый вектор-образ xi из T заранее помечен «учителем» меткой ti.
Каждую пару (xi, ti) T называют также прецедентом, а обучение
с учителем — обучением по прецедентам.
На практике возникают также задачи, в которых имеется только
выборка из векторов признаков {x } i i
N
1, а их метки ti отсутствуют (не-
известны). В этом случае распознаватель должен осуществлять груп-
пировку данных по классам на основе обучающей выборки {x } i i
N
1 без
внешнего участия учителя [17, 20]. Вопросы, связанные с машин-
ным обучением без учителя, будут рассмотрены нами в главе 6.
1.2. Ñïîñîáíîñòü ðàñïîçíàâàòåëÿ
ê îáîáùåíèþ. Ïåðåîáó÷åíèå
è ðåãóëÿðèçàöèÿ
Рассмотрим простейший случай регрессии, когда образ объ-
екта является скаляром x (вектор признаков состоит из одной
компоненты), а желаемый отклик распознавателя, или «метка»
1.2. Способность распознавателя к обобщению. 17
Переобучение и регуляризация
объекта, — это также скалярная величина t, которая присвоена
ему по следующему правилу:
t g(x) + ,
где g(x) — некоторая неизвестная распознавателю функция;
— случайная величина с математическим ожиданием M[] 0
и дисперсией 2. Требуется построить оптимальный распознава-
тель f, дающий минимальное среднее значение функции штрафа
E(t, y) (t − y)2, где y f(x).
Очевидно, что средний по всей генеральной совокупности
штраф (1.1) будет минимальным, если для решающего правила
y f(x) выбрать f(x) g(x), так как x:
M ( ) M ( ) ( ) t y g x f x
2 2
g(x) f (x) M[ ] g(x) f (x) M[ ] g(x) f ( 2
0 0
2 2
2
x
g x f x
)
, () ()
2
0
2
при
.
Однако функция g(x) распознавателю неизвестна, поэтому необ-
ходимо построить ее аппроксимацию f(x) g(x) путем обучения
на выборке T x t x t N N ( , ), , ( , ) 1 1 , минимизируя эмпирический
риск (1.4) с функцией ошибки E(t, y) (t − y)2.
Пример 1.3. Как и в упражнении 1.2, наблюдаемые значения меток
будем формировать по правилу
t sin(5x/2) + , (1.6)
где — гауссова случайная величина с нулевым средним
и СКО 0,25. Решающую функцию y f(x) будем искать в про-
странстве алгебраических многочленов степени M, т. е. будем
использовать для распознавателя модель вида
y f x wxj
j
j
M
( )
0
. (1.7)
Таким образом, по наблюдаемой выборке T x t x t N N ( , ), , ( , ) 1 1
необходимо построить аппроксимацию f(x) sin(5x/2) в виде мно-
гочлена (1.7). Сделаем это для частного случая N 11 при некото-
рых значениях M и изучим способность полученных распознавате-
лей к обобщению, которая характеризуется малостью ошибок при
распознавании образов, отсутствовавших в обучающей выборке.
◄ Очевидно, что при M N 1 можно подобрать такие коэффици-
енты полинома (1.7), что для всех элементов обучающей выборки T
18 Глава 1. Основные задачи, модели и подходы к машинному обучению
получим yi f(xi) ti и, соответственно, нулевое значение для эм-
пирического риска (1.4).
Для порядков M < N 1 вектор коэффициентов w (w0, …, wM)T
полинома (1.7) будем искать, минимизируя по параметрам wj ква-
дратичную функцию (1.4) или (что даст тот же самый результат
при фиксированном значении N) функцию
E t f x i i
i
N
(w) ( )
1
2
2
1
, (1.8)
где множитель 1/2 включают в выражение для удобства его после-
дующего дифференцирования.
Выбрав x i i ( 1) 10 (i 1, …, 11) и сгенерировав признаки ti
по правилу (1.6), получим на плоскости (x, t) некоторые точки,
случайным образом отклоняющиеся по оси t от графика функ-
ции sin(5x/2) на значения реализации нормальной величины
(рис. 1.2). Эти точки будем использовать в качестве обучающей
выборки T (x , t ), , (x , t ) 1 1 11 11 .
Методом наименьших квадратов найдем на этой выборке коэф-
фициенты w* w*, ,w* M
T
0 полиномов (1.7) порядка M 0, 1, …, 10,
которые обращают в минимум штраф (1.8). Графики полученных
полиномов (1.7) для M 1, 3, 6, 10 приведены на рис. 1.3.
Как и следовало ожидать, полином-прямая (M 1) дает пло-
хое приближение функции sin(5x/2). Хотя полином десятого
порядка и обеспечивает нулевую ошибку приближения в точ-
ках заданной обучающей последовательности T (и только в них),
полином шестого порядка
(M 6) дает визуально лучшее
приближение. Таким обра-
зом, анализ графиков рис. 1.3
позволяет предположить, что
увеличение порядка аппро-
ксимирующего алгебраиче-
ского полинома сначала повы-
шает точность аппроксимации
«скрытой» функции g(x) [в на-
шем примере g(x) sin(5x/2)],
а затем точность приближения
ухудшается.
0 0,2 0,4 0,6 0,8 1
–1,5
–1
–0,5
0
0,5
1
1,5
t
x
Рис. 1.2. График функции sin(5x/2)
(штриховая кривая) и точки обуча-
ющей выборки (11 шт.)
1.2. Способность распознавателя к обобщению. 19
Переобучение и регуляризация
Для изучения способности распознавателя к обобщению ис-
следуем среднюю ошибку распознавания на тестовой выборке
T, полученной по тому же правилу (1.6), но не содержащей дан-
ные, которые были включены в обучающую последовательность.
Для того чтобы можно было сравнивать выборки разного объе-
ма, от (1.8) вернемся к измерению среднего эмпирического риска
(1.4). На рис. 1.4 приведены значения среднеквадратичной ошибки
распознавания
E
N
t f x RMS n n
n
N
1 2
1
( )
[квадратного корня из (1.4)], полученные на рассмотренной обучаю-
щей выборке T из N 11 элементов, а также на независимо сгенери-
рованной по правилу (1.6) тестовой выборке T (x , t ),, (x , t ) 1 1 101 101
0 0,2 0,4 0,6 0,8 1
–1,5
–1
–0,5
0
0,5
1
1,5
t M = 1
x
0 0,2 0,4 0,6 0,8 1
–1,5
–1
–0,5
0
0,5
1
1,5
t M = 3
x
0 0,2 0,4 0,6 0,8 1
–1,5
–1
–0,5
0
0,5
1
1,5
t M = 6
x
0 0,2 0,4 0,6 0,8 1
–1,5
–1
–0,5
0
0,5
1
1,5
t M = 10
x
Рис. 1.3. Полиномы наилучшего (для заданной выборки) квадра-
тичного приближения порядка M. При M 10 ошибка
приближения равна нулю
20 Глава 1. Основные задачи, модели и подходы к машинному обучению
(N 101), для которой была взята сетка значений xi (i 1)/100
(i 1, …, 101).
Из рис. 1.4 видно, что на тестовой выборке среднеквадратич-
ные ошибки распознавания принимают наименьшие и примерно
одинаковые значения для полиномов, имеющих порядок 4 M 9.
Причем при одном и том же порядке M ошибка на тестовой выбор-
ке всегда больше ошибки на обучающей выборке.
При M 10, когда ошибку на обучающей выборке становится
возможным обратить в ноль, ошибка на тестовой выборке резко
возрастает. Если посмотреть на график соответствующего поли-
нома, у которого появляются большие осцилляции относительно
графика функции sin(5x/2) (см. рис. 1.3), то это не покажется уди-
вительным. Как можно видеть из табл. 1.1, рост осцилляций поли-
нома десятого порядка сопровождается значительным увеличени-
ем абсолютных величин коэффициентов w* (w*, ,w* ) . M
T
0
Эффект резкого увеличения средней ошибки на тестовой
выборке при увеличении количества варьируемых параметров
модели распознавателя (т. е. при увеличении сложности модели,
которая в нашем примере характеризуется значением M) называ-
ется переобучением распознавателя. Термин «переобучение» пони-
мается как чрезмерное, а не повторное обучение (overlearning, или
overfi tting, — чрезмерная под-
гонка под обучающие данные).
При большом количестве па-
раметров модели, используе-
мой для решающей функции
f, и малом объеме обучающей
выборки часто оказывается
возможным настроить модель
так, что распознаватель как
бы «запоминает» обучаю-
щие данные и дает для них
вообще нулевую ошибку (мы
это наблюдали в примере
1.2, где запоминание данных
происходило в буквальном
смысле). Вместе с тем каждый
0 2 4 6 8 10
Порядок полинома
0
0,2
0,4
0,6
0,8
1
1,2
Среднеквадратичная ошибка
Ошибка на тестовой выборке
Ошибка на обучающей выборке
Рис. 1.4. Среднеквадратичная ошиб-
ка распознавания ERMS, полученная
на обучающей выборке из 11 элемен-
тов и тестовой выборке из 101 эле-
мента для моделей полиномов (1.7)
разных порядков M 0, 1, …, 10
1.2. Способность распознавателя к обобщению. 21
Переобучение и регуляризация
прецедент в обучающей выборке предполагает наличие некото-
рого случайного фактора ошибки, содержащегося в присвоенной
учителем метке [как и в нашем примере, см. (1.6)], поэтому точное
запоминание прецедентов при обучении распознавателя лишено
смысла. Переобучение распознавателя влечет за собой ухудшение
его способности к обобщению, т. е. к распознаванию «незнакомых»
новых образов с малой средней ошибкой.
Для предотвращения переобучения необходимо, чтобы коли-
чество настраиваемых независимых параметров модели распо-
знавателя было намного меньше объема обучающей выборки. По-
смотрим, как для нашего примера с моделью решающей функции
(1.7) и правилом разметки (1.6) меняется способность распозна-
вателя к обобщению при увеличении объема обучающей выбор-
ки N. Графики решающей функции f(x) (полиномов наилучшего
среднеквадратичного приближения десятого порядка, получен-
ных на обучающих выборках объемов N 21 и N 101) приведе-
ны на рис. 1.5. Как и следовало ожидать, точность приближения
функции sin(5x/2) полиномом (1.7) повышается с увеличением
объема обучающей выборки.
Таблица 1.1. Коэффициенты полинома (1.7) порядка M, получен-
ные по обучающей выборке объема N 11 методом
наименьших квадратов
M 1 M 3 M 6 M 10
w0
* 0,3596 0,4272 0,2725 0,2725
w1
* 0,2856 4,401 0,9053 279,38
w2
* 0 19,05 73,14 7 524
w3
* 0 15,47 350,78 81 700
w4
* 0 0 547,67 472 947
w5
* 0 0 312,68 1 632 833
w6
* 0 0 43,95 3 530 061
w7
* 0 0 0 4 822 552
w8
* 0 0 0 4 042 083
w9
* 0 0 0 1 896 384
w10
* 0 0 0 381 133
22 Глава 1. Основные задачи, модели и подходы к машинному обучению
К сожалению, объем N реально имеющейся для обучения рас-
познавателя выборки часто оказывается недостаточным. В этом
случае для исключения эффекта переобучения применяется регу-
ляризация, которая состоит в добавлении в функцию эмпириче-
ского риска некоторого неотрицательного слагаемого, дополни-
тельно штрафующего за каждый выбор того или иного вектора
параметров w в модели решающей функции.
Большие абсолютные значения весов w* (w*, ,w* ) M
T
0 в моде-
ли (1.7) нежелательны и должны штрафоваться сильнее, так как
увеличивают осцилляцию решающей функции. Для рассматри-
ваемого примера модели (1.7) введем дополнительное слагаемое
регуляризации, например квадрат нормы вектора параметров1
w ww 2 2
0 T
k k
M w . Тогда новая функция штрафа, полученная
в результате регуляризации, будет выглядеть для решающего пра-
вила f(x) (1.7) следующим образом:
E t f x i i
i
N
(w) ( ) w
1
2 2
2
1
2 , (1.9)
где параметр 0 задает баланс между «значимостями» штрафа
за ошибку распознавания и штрафа за величину абсолютных зна-
чений весов модели (1.7). Как и ранее, дополнительный множитель
1 Поскольку коэффициент w0 влияет лишь на смещение по оси аб-
сцисс функции (1.7) и не влияет на «размах» ее осцилляций, параметр w0
часто не учитывается при подсчете квадрата нормы вектора w.
0 0,2 0,4 0,6 0,8 1
–1,5
–1
–0,5
0
0,5
1
1,5
N = 21
t
x 0 0,2 0,4 0,6 0,8 1
–1,5
–1
–0,5
0
0,5
1
1,5
N = 101
t
x
Рис. 1.5. Полиномы (1.7) наилучшего квадратичного прибли-
жения порядка M 10 (сплошная кривая), полученные
на выборках объема N 21 (слева) и N 101 (справа). Срав-
ните с рис. 1.3
1.2. Способность распознавателя к обобщению. 23
Переобучение и регуляризация
1/2 в слагаемом регуляризации введен для удобства последующего
дифференцирования; конкретное значение веса определяется
экспериментально.
На рис. 1.6 приведены графики полиномов (1.7) десятого по-
рядка, полученных на исходной (см. рис. 1.2) выборке из N 11
элементов в результате минимизации функции (1.9) для значений
10−10 и 1. Заметим, что случаю 0 (отсутствие регуляри-
зации) будет соответствовать правый нижний график на рис. 1.3.
Видим, что при 10−10 (рис. 1.6, график слева) полученная ре-
шающая функция f(x) приближает функцию sin(5x/2) намного
лучше, чем в случае отсутствия регуляризации, но все же хуже той
решающей функции, которая была найдена по обучающей выбор-
ке объема N 101 (правый график на рис. 1.5).
0 0,2 0,4 0,6 0,8 1
–1,5
–1
–0,5
0
0,5
1
1,5
= 10–10
t
x 0 0,2 0,4 0,6 0,8 1
–1,5
–1
–0,5
0
0,5
1
1,5
= 1
t
x
Рис. 1.6. Графики решающих функций (1.7) порядка M 10, полу-
ченных в результате минимизации штрафа (1.9) со сла-
гаемым регуляризации
Значения весовых коэффициентов w* (w*, ,w* ) M
T
0 , получен-
ных при использовании регуляризации, представлены в табл. 1.2.
Как и следовало ожидать, введение слагаемого регуляризации
уменьшило абсолютные величины коэффициентов полинома (1.7).
На рис. 1.7 приведены зависимости среднеквадратичной ошиб-
ки распознавания ERMS от значения параметра из (1.9), получен-
ные на тех же обучающей T (11 элементов, см. рис. 1.2) и тестовой
T (101 элемент) выборках, которые использовались для построе-
ния графиков рис. 1.4. Видим, что выбор 10−8 позволяет полу-
чить для решающей функции полинома порядка M 10 примерно
24 Глава 1. Основные задачи, модели и подходы к машинному обучению
такую же ошибку распознавания на тестовой выборке, которая
имела место ранее без применения регуляризации для лучшего ва-
рианта полинома порядка M 6.
В рассмотренном нами при-
мере модели распознавателя
(1.7) использование сложных ре-
шающих функций (c порядком
полинома M > 4) при обучающей
выборке объема N 11 оказалось
практически лишенным смыс-
ла, так как крайне незначитель-
но влияло на изменение ошибки
распознавания. Однако в общем
случае применение более слож-
ных моделей с большим коли-
чеством параметров способно
потенциально понизить ошибку
распознавания. При этом воз-
можно возникновение проблем
–15 –10 –5 0 lg
0
0,2
0,4
0,6
0,8
1
Ошибка на тестовой выборке
Ошибка на обучающей выборке
Среднеквадратичная ошибка
Рис. 1.7. Среднеквадратичная
ошибка распознавания ERMS, по-
лученная для разных значений
параметра функции штрафа (1.9)
на обучающей выборке из 11 эле-
ментов и тестовой выборке из 101
элемента для полинома (1.7) по-
рядка M 10
Таблица 1.2. Коэффициенты полинома (1.7) порядка M 10, по-
лученные по обучающей выборке объема N 11 при
использовании регуляризации
0 1010 1
w0
* 0,2725 0,2723 0,2728
w1
* 279,38 0,5698 0,3686
w2
* 7524 44,9265 0,2124
w3
* 81 700 169,4394 0,0281
w4
* 472 947 65,4488 0,0908
w5
* 1 632 833 82,4711 0,1542
w6
* 3 530 061 466,8941 0,1812
w7
* 4 822 552 577,2536 0,1862
w8
* 4 042 083 688,525 0,1785
w9
* 1 896 384 1284,8539 0,1641
w10
* 381 133 509,5763 0,1463
1.2. Способность распознавателя к обобщению. 25
Переобучение и регуляризация
обучения сложных моделей из-за необходимости использования
нереально больших объемов обучающих выборок. Эффективным
средством повышения качества обучения на выборках недостаточ-
ного объема является регуляризация, другие примеры и варианты
которой встретятся нам в следующих главах. ►
Удобным свойством часто используемой функции штрафа (1.8)
с полиномиальной моделью (1.7) является ее выпуклость, вслед-
ствие чего равенство нулю градиента E(w) 0 является не толь-
ко необходимым, но и достаточным условием минимума этой
функции.
Напомним, что функция F(x) является выпуклой на выпуклой
области D, если x1 D, x2 D:
F x x F x F x 1 2 1 2 (1 ) ( )(1 ) ( )
при любых значениях [0; 1].
Пример 1.4. Показать, что функция E(w) в (1.8) выпуклая.
◄ Подставим выражение для f(x) из (1.7) в (1.8):
E t w x E i j i
j
j
M
i
N
i
i
N
(w) (w)
1
2 0
2
1 1
, где E t w x i i j i
j
j
M
(w)
1
2 0
2
.
Для частных производных квадратичной функции Ei(w) имеем:
w
E
w
t wx x t wx
k
i
k
i j i
j
j
M
i
k
i j i
j
j
M
(w)
1
2 0
2
0
, k 0, 1, …, M;
2
w w
E x x x
k m
i i
k
i
m
i
(w) k m , k 0, 1, …, M; m 0, 1, …, M.
Для выпуклости квадратичной функции Ei(w) необходимо
и достаточно, чтобы матрица вторых производных (матрица Гессе)
H w i
k m
i
k m
M
i
k m
k m
M
w w
E x
2
0
0
( )
,
,
была положительно полуопределенной. Поскольку для любого
вектора y (y0, y1, …, yM)T квадратичная форма
yTH y
i i
k m
k m
m
M
k
M
i
k
k i
m
m
m
M
k
M
i
n
n
n
M
x y y x y x y x y
0 0 0 0 0
2
0,
26 Глава 1. Основные задачи, модели и подходы к машинному обучению
то матрица Hi положительно полуопределена, а функция Ei(w) вы-
пуклая. Функция E(w) (1.8) является выпуклой как сумма выпук-
лых функций Ei(w). ►
Упражнение 1.3. Покажите, что при использовании модели (1.7)
в функции штрафа (1.8) выражения для оптимальных коэффици-
ентов w* (w*, ,w* ) M
T
0 , обращающих в минимум (1.8), находятся
по обучающей выборке T x t x t N N ( , ),, ( , ) 1 1 в результате решения
следующей системы линейных уравнений:
a w b i j j
j
M
, i
0
, i 0, …, M, (1.10)
где a x i j n
i j
n
N
,
1
, b tx i n n
i
n
N
1
.
Убедитесь, что с использованием обозначений
X
x x x
x x x
x x x
x x
x
M
M
N N N
M
M
1
0
1
1
1
2
0
2
1
2
0 1
1 1 1
1
2 2
1
x
x x
M
N N
M
, t
t
t
tN
1
2
систему уравнений (1.10) можно представить в матричном виде
следующим образом: Aw b, где A XT X и b XT t. Причем в обо-
значениях примера 1.4 A H i i
N
1 , поэтому матрица A симметри-
ческая и положительно полуопределена.
Оказывается, что рассмотренную в примере 1.3 процедуру ре-
гуляризации, состоящую во включении в выражение для штраф-
ной функции ошибки распознавания дополнительного слагаемого
штрафа за выбор конкретных параметров модели, можно интер-
претировать как определенную модификацию системы уравнений
(1.10), направленную на повышение устойчивости ее решения1.
Поясним это утверждение.
Если матричное уравнение вида Aw b имеет плохо обусловлен-
ную матрицу A, т. е. число обусловленности (A) 1, то решение
1 Общая теория метода регуляризации, используемого для решения
некорректных задач, приводящих к плохо обусловленным системам ли-
нейных уравнений, разработана академиком А. Н. Тихоновым и его шко-
лой в 60-х гг. XX в.
1.2. Способность распознавателя к обобщению. 27
Переобучение и регуляризация
уравнения w A1b является неустойчивым1. Для симметрических
положительно полуопределенных матриц число обусловленности
выражается через собственные числа (которые являются неот-
рицательными) как (A) max/min, поэтому у плохо обусловлен-
ных матриц max min. В частности, для вырожденной матрицы
min 0 и (A) .
Если «поправить» симметрическую положительно полуопреде-
ленную матрицу следующим образом: A A + E, где скаляр 0,
E — единичная матрица, то собственные векторы у новой матрицы
A останутся теми же, а собственные числа станут больше на вели-
чину . Действительно, обозначив для матрицы A некоторый соб-
ственный вектор и соответствующее ему собственное число как rk
и k, для матрицы A получаем: Ar r k k k ( ) . По этой причине
для новой (также симметрической и положительно полуопреде-
ленной) матрицы число обусловленности уменьшится:
( ) max ( )
min
max
min
A A ,
и устойчивость решения w (A)1b повысится. Добавление сла-
гаемого регуляризации в (1.9) приводит к подобной модификации
системы уравнений (1.10).
Упражнение 1.4. Убедитесь, что функция (1.9) является выпуклой
и покажите, что замена штрафа (1.8) на (1.9) приводит к опти-
мальным параметрам w* (w*, ,w* ) M
T
0 модели (1.7), определяе-
мым системой линейных уравнений (A E)w b, полученной
из Aw b (1.10).
В примере 1.3 полиномиальная модель использовалась для
решающей функции распознавателя y f(x) в простейшем случае,
когда вектор признаков x был однокомпонентным, т. е. скаляром
(x x). Если размерность пространства признаков dim d 1, то
количество параметров, задающих алгебраический полином сте-
пени M, будет заметно больше, чем M + 1. Чему оно равно?
1 Такая ситуация имеет место, в частности, для системы линейных
уравнений (1.10), которая была получена в примере 1.3 на выборке объема
N 11 с полиномом (1.7) порядка M 10.
28 Глава 1. Основные задачи, модели и подходы к машинному обучению
Пример 1.5. Подсчитать количество параметров, задающих алге-
браический полином степени M от d переменных x1, …, xd.
◄ Рассматриваемый алгебраический полином имеет следующий
общий вид:
P x x w w x w x x d ii
i
d
i i i i
i
d
i
d
i
d
( 1, , ) 0 ,
1 1 1
1
1 2 1 2
1 2
2
i
d
i i i i i i
i
d
w xx x
M M
1 M
1 2 1 2
1 1
, , , .
Постоянная составляющая полинома определяется одним
параметром w0. В первой сумме, определяющей линейную часть
полинома, имеем s1(d) d параметров w1, …, wd.
В двойной сумме, определяющей квадратичную форму, пара
коэффициентов wi,j и wj,i при i j соответствует подобным слагае-
мым и поэтому определяет только один параметр ai,j в квадратич-
ной части полинома: w xx w x x a xx i, j i j j,i j i i, j i j ; обычно для симме-
трии принимают wi,j wj,i ai,j/2. Тогда количество независимых
параметров ai,j в квадратичной части полинома:
s d
i j i j
i j i j
d d
d
d d
2
2
2 2
1
2
( )
( , )
( , )
( )
,
где обозначение A принято для количества элементов в
множестве A.
Обобщим способ подсчета параметров, использованный выше
для квадратичной части полинома. Для того чтобы определить ко-
личество sk коэффициентов-параметров в k-кратной сумме
i
d
i
d
i i i i i i
i
d
w xx x
k k
1 2 k
1 2 1 2
1 1 1
, , , ,
которые останутся после приведения подобных слагаемых, необ-
ходимо подсчитать количество различных комбинаций (i1, i2, …, ik),
не различающихся порядком следования индексов, но с возмож-
ностью их повторений. Воспользуемся формулой для количества
сочетаний с повторениями из d по k:
s d C C
d k
d k k d
k
d k
( ) k
( )!
( )! !
1
1
1
.
Заметим, что эта формула является верной и для уже найденных
нами значений s0(d) 1, s1(d) d, s2(d) d(d + 1)/2.
1.3. Применение формулы Байеса для оценок параметров моделей 29
В итоге количество параметров полинома порядка M от d пере-
менных получаем равным
S d s d
d k
d k
S d
d M
d M k
k
M
k
M
M ( ) ( )
( )!
( )! !
( )
( )!
(
0 0
1
1
1
1
1)! !
( )!
M ! !
d M
d M
.
Последнее равенство обоснуйте самостоятельно методом мате-
матической индукции, обратив сначала внимание на то, что ито-
говое выражение верно для S0(d) и S1(d). Тогда в предположении
его применимости для SM−1(d) нужно показать справедливость по-
лученного выражения для SM(d). ►
Таким образом, количество числовых параметров, определяю-
щих алгебраический полином порядка M от d переменных, равно
S d
d M
d M M( )
( )!
! !
. (1.11)
Упражнение 1.5. Покажите, что порядок величины (1.11)
SM(d) O(dM) при d M и SM(d) O(Md) при M d, воспользо-
вавшись формулой Стирлинга n! 2nennn , применяемой для
аппроксимации факториала при больших значениях n.
Рост числа параметров полиномиальной модели, наблюдаемый
при увеличении размерности пространства векторов признаков,
представляет собой пример проклятия размерности.
1.3. Ïðèìåíåíèå ôîðìóëû Áàéåñà
äëÿ îöåíîê ïàðàìåòðîâ ìîäåëåé
Напомним понятие условной вероятности. Пусть A и B — некото-
рые случайные события. Условной вероятностью события B при
условии, что произошло событие A, называется величина
P B A
P AB
P A
( | )
( )
( )
,
где P(AB) — вероятность совместной реализации событий A и B;
P(A) — вероятность события A.
Формула Байеса получается непосредственно из приведенного
определения условной вероятности: