Машинное обучение. Наука и искусство построения алгоритмов, которые извлекают знания из данных

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

Наука и искусство построения алгоритмов, 
которые извлекают знания из данных

Петер Флах

Machine Learning

The Art and Science of Algorithms
that Make Sense of Data

Peter Flach

Москва, 2023

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

Наука и искусство построения алгоритмов, 
которые извлекают знания из данных

Петер Флах

2е издание, электронное

УДК 004.4
ББК 32.972
Ф70

Ф70
Флах, Петер.
Машинное обучение. Наука и искусство построения алгоритмов, которые извлекают 
знания из данных / П. Флах ; пер. с англ. А. А. Слинкина. — 2-е изд., эл. — 1 файл pdf : 
401 с. — Москва : ДМК Пресс, 2023. — Систем. требования: Adobe Reader XI либо Adobe 
Digital Editions 4.5 ; экран 10". — Текст : электронный.
ISBN 978-5-89818-300-4

Перед вами один из самых интересных учебников по машинному обучению — разделу искусственного 
интеллекта, изучающего методы построения моделей, способных обучаться, и алгоритмов 
для их построения и обучения. Автор воздал должное невероятному богатству предмета и не 
упустил из виду объединяющих принципов. Читатель с первых страниц видит машинное обучение 
в действии, но без не нужных на первых порах технических деталей. По мере изучения предмета 
тщательно подобранные примеры, сопровождаемые иллюстрациями, постепенно усложняются. 
В книге описан широкий круг логических, геометрических и статистических моделей, затрагиваются 
и такие находящиеся на переднем крае науки темы, как матричная факторизация и анализ 
РХП. Особое внимание уделено важнейшей роли признаков. Устоявшаяся терминология 
дополняется введением в рассмотрение новых полезных концепций. В конце каждой главы приводятся 
ссылки на дополнительную литературу с авторскими комментариями.
Благодаря всему этому книга задает новый стандарт изучения такой сложной дисциплины как 
машинное обучение.

УДК 004.4 
ББК 32.972

Электронное издание на основе печатного издания: Машинное обучение. Наука и искусство построения 
алгоритмов, которые извлекают знания из данных / П. Флах ; пер. с англ. А. А. Слинкина. — Москва : ДМК 
Пресс, 2015. — 400 с. — ISBN 978-5-97060-273-7. — Текст : непосредственный.

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

В соответствии со ст. 1299 и 1301 ГК РФ при устранении ограничений, установленных техническими средствами защиты авторских 
прав, правообладатель вправе требовать от нарушителя возмещения убытков или выплаты компенсации.

ISBN 978-5-89818-300-4
© Peter Flach 2012 
© Издание, перевод, ДМК Пресс, 2015

Посвящается Хэссел Флах 
(1923–2006)

Содержание

Предисловие ......................................................................... 11

Как читать эту книгу ...................................................................................................11
Благодарности ...............................................................................................................12

Пролог: пример машинного обучения ...................................... 14

1 Ингредиенты машинного обучения ..................................... 25

1.1  Задачи: проблемы, решаемые методами машинного обучения ...................25

В поисках структуры ..................................................................................................27
Оценка качества решения задачи ...........................................................................30

1.2 Модели: результат машинного обучения ............................................................32

Геометрические модели..............................................................................................33
Вероятностные модели ..............................................................................................37
Логические модели ......................................................................................................44
Группировка и ранжирование .................................................................................49

1.3 Признаки: рабочая лошадка машинного обучения ..........................................50

Два способа использования признаков ................................................................52
Отбор и преобразование признаков ......................................................................54
Взаимодействие между признаками .....................................................................56

1.4 Итоги и перспективы ..................................................................................................59

Что будет в книге дальше ..........................................................................................61

2 Бинарная классификация и родственные задачи ................. 62

2.1 Классификация ............................................................................................................65

Оценка качества классификации ...........................................................................66
Наглядное представление качества классификации .......................................70

2.2 Оценивание и ранжирование ..................................................................................75

Оценка и визуализация качества ранжирования .............................................78

Содержание

Преобразование ранжировщика в классификатор ..........................................84

2.3. Оценивание вероятностей классов .........................................................................87

Качество оценивания вероятностей классов......................................................88
Преобразование ранжировщиков в оценки вероятностей классов ............91

2.4 Бинарная классификация и родственные задачи: итоги 
и дополнительная литература .................................................................................93

3 За пределами бинарной классификации ............................. 96

3.1 Когда классов больше двух ......................................................................................96

Многоклассовая классификация ...........................................................................96
Многоклассовые оценки и вероятности ........................................................... 101

3.2 Регрессия ..................................................................................................................... 105
3.3 Обучение без учителя и дескриптивные модели ........................................... 108

Прогностическая и дескриптивная кластеризация ...................................... 109
Другие дескриптивные модели ............................................................................ 114

3.4 За пределами бинарной классификации: итоги и литература 
для дальнейшего чтения ......................................................................................... 116

4 Концептуальное обучение ................................................118

4.1 Пространство гипотез ............................................................................................. 119

Наименьшее обобщение ......................................................................................... 120
Внутренняя дизъюнкция........................................................................................ 122

4.2 Пути в пространстве гипотез ................................................................................ 124

Наиболее общие непротиворечивые гипотезы ............................................... 128
Замкнутые концепты ............................................................................................... 130

4.3 За пределами конъюнктивных концептов ....................................................... 130

Применение логики первого порядка ................................................................ 135

4.4 Обучаемость ............................................................................................................... 136
4.5 Концептуальное обучение: итоги и литература для дальнейшего 
чтения ............................................................................................................................ 139

5 Древовидные модели ........................................................142

5.1 Решающие деревья ................................................................................................... 146
5.2 Деревья ранжирования и оценивания вероятностей ................................... 151

Чувствительность к асимметричному распределению по классам ......... 156

5.3 Обучение деревьев как уменьшение дисперсии ............................................ 161

Деревья регрессии .................................................................................................... 161
Кластеризующие деревья ....................................................................................... 165

Содержание

5.4 Древовидные модели: итоги и литература для дальнейшего чтения ..... 168

6 Модели на основе правил ..................................................170

6.1 Обучение упорядоченных списков правил...................................................... 170

Списки правил для ранжирования и оценивания вероятностей ............. 176

6.2 Обучение неупорядоченных множеств правил .............................................. 179

Применение множеств правил для ранжирования и оценивания 
вероятностей ............................................................................................................... 183
Более пристальный взгляд на перекрытие правил ....................................... 187

6.3 Обучение дескриптивных моделей на основе правил ................................. 189

Обучение правил для выявления подгрупп .................................................... 190
Добыча ассоциативных правил ............................................................................ 194

6.4 Обучение правил первого порядка ..................................................................... 199
6.5 Модели на основе правил: итоги и литература для дальнейшего 
чтения ............................................................................................................................ 203

7 Линейные модели .............................................................206

7.1 Метод наименьших квадратов ............................................................................. 208

Многомерная линейная регрессия ..................................................................... 212
Регуляризованная регрессия ................................................................................ 216
Применение регрессии по методу наименьших квадратов к задаче 
классификации .......................................................................................................... 217

7.2 Перцептрон ................................................................................................................. 218
7.3 Метод опорных векторов ....................................................................................... 223

Метод опорных векторов с мягким зазором .................................................... 228

7.4 Получение вероятностей от линейных классификаторов .......................... 231
7.5 За пределами линейности – ядерные методы ................................................. 236
7.6 Линейные модели: итоги и литература для дальнейшего чтения ............ 239

8 Метрические модели ........................................................242

8.1 Так много дорог... ....................................................................................................... 242
8.2 Соседи и эталоны ...................................................................................................... 248
8.3 Классификация по ближайшему соседу ........................................................... 253
8.4 Метрическая кластеризация ................................................................................. 256

Алгоритм K средних ................................................................................................ 259
Кластеризация вокруг медоидов ......................................................................... 261
Силуэты ........................................................................................................................ 262

8.5 Иерархическая кластеризация ............................................................................. 264

Содержание

8.6 От ядер к расстояниям ............................................................................................ 269
8.7 Метрические модели: итоги и литература для дальнейшего чтения ...... 270

9 Вероятностные модели .....................................................273

9.1 Нормальное распределение и его геометрические интерпретации......... 277
9.2 Вероятностные модели для категориальных данных .................................. 284

Использование наивной байесовской модели для классификации........ 286
Обучение наивной байесовской модели ........................................................... 289

9.3 Дискриминантное обучение путем оптимизации условного 
правдоподобия ........................................................................................................... 293

9.4 Вероятностные модели со скрытыми переменными .................................... 297

EM-алгоритм .............................................................................................................. 299
Гауссовы смесовые модели .................................................................................... 300

9.5 Модели на основе сжатия ...................................................................................... 304
9.6 Вероятностные модели: итоги и литература для дальнейшего 
чтения ............................................................................................................................ 306

10 Признаки .........................................................................310

10.1 Виды признаков ........................................................................................................ 310

Вычисления с признаками ..................................................................................... 311
Категориальные, порядковые и количественные признаки ...................... 315
Структурированные признаки ............................................................................. 317

10.2 Преобразования признаков ................................................................................... 318

Задание порога и дискретизация......................................................................... 319
Нормировка и калибровка ..................................................................................... 325
Неполные признаки ................................................................................................. 333

10.3 Конструирование и отбор признаков ................................................................ 334

Преобразование и разложение матриц ............................................................. 336

10.4 Признак: итоги и литература для дальнейшего чтения .............................. 339

11 Ансамбли моделей ...........................................................342

11.1 Баггинг и случайные леса ...................................................................................... 343
11.2 Усиление....................................................................................................................... 345

Обучение усиленных правил ................................................................................ 349

11.3 Карта ансамблевого ландшафта .......................................................................... 350

Смещение, дисперсия и зазоры ............................................................................ 350
Другие ансамблевые методы ................................................................................. 352
Метаобучение ............................................................................................................. 352

Содержание

11.4 Ансамбли моделей: итоги и литература для дальнейшего чтения .......... 353

12 Эксперименты в машинном обучении ................................355

12.1 Что измерять .............................................................................................................. 356
12.2 Как измерять .............................................................................................................. 360
12.3 Как интерпретировать ............................................................................................. 362

Интерпретация результатов, полученных на нескольких наборах 
данных ........................................................................................................................... 365

12.4 Эксперименты в машинном обучении: итоги и литература 
для дальнейшего чтения ......................................................................................... 368

Эпилог: что дальше? .............................................................371

Что нужно запомнить ............................................................373

Библиография ......................................................................376

Предметный указатель ..........................................................387

Предисловие

Идея этой книги появилась летом 2008 года, когда Бристольский университет, 
где я в то время работал, предоставил мне годичную стипендию для проведения 
научных исследований. Написать общее введение в машинное обучение я решил 
по двум причинам. Во-первых, существовала очевидная потребность в такой 
книге, которая дополняла бы многочисленные специальные издания на эту тему, 
а во-вторых, это позволило бы мне самому изучить что-то новое – ведь, как известно, 
лучший способ чему-то научиться – начать это преподавать.
Перед любым автором, желающим написать вводный учебник по машинному 
обучению, стоит трудная задача – осветить невероятно богатый материал, не 
упустив из виду объединяющих его принципов. Стоит уделить чрезмерно много 
внимания разнообразию дисциплины – и вы рискуете получить сборник слабо 
связанных между собой «рецептов». А увлекшись какой-нибудь из своих излюбленных 
парадигм, вы оставите за бортом массу других не менее интересных вещей. 
В конце концов, методом проб и ошибок я остановился на подходе, который 
позволяет подчеркнуть как единство, так и разнообразие. Единство достигается 
путем разделения задач и признаков – и то, и другое присутствует в любом подходе 
к машинному обучению, но зачастую принимается как само собой разумеющееся. 
А разнообразие обеспечивается рассмотрением широкого круга логических, 
геометрических и вероятностных моделей.
Понятно, что сколько-нибудь глубоко охватить весь предмет машинного 
обуче ния на 400 страницах нет никакой надежды. В эпилоге перечисляется ряд 
важных дисциплин, которые я решил не включать. На мой взгляд, машинное 
обуче ние – это сочетание статистики и представления знаний, и темы для книги 
были отобраны соответственно. Поэтому сначала довольно подробно рассматриваются 
решающие деревья и обучение на основе правил, а затем я перехожу 
к материалу, основанному на применении математической статистики. В книге 
постоянно подчеркивается важность интуиции, подкрепленная многочисленными 
примерами и иллюстрациями, многие из которых взяты из моих работ по 
применению РХП-анализа1 в машинном обучении.

Как читать эту книгу

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

1 Рабочая характеристика приемника (ROC – receiver operating characteristic). – Прим. 
перев.

Предисловие

а затем сразу перейти к главе 5, посвященной решающим деревьям, – без существенного 
нарушения непрерывности изложения. Прочитав раздел 5.1, можно 
перескочить к первым двум разделам главы 6, чтобы узнать о классификаторах 
на основе правил.
C другой стороны, читатель, интересующийся линейными моделями, может 
после раздела 2.1 перейти к разделу 3.2 о регрессионных задачах, а затем к главе 
7, которая начинается с рассмотрения линейной регрессии. В порядке следования 
глав 4–9, посвященных логическим, геометрическим и вероятностным 
моделям, есть определенная логика, но по большей части их можно читать независимо; 
то же самое относится к главам 10–12 о признаках, ансамблях моделей 
и экспериментах в машинном обучении.
Отмечу также, что пролог и глава 1 носят вступительный характер и в значительной 
мере независимы от всего остального: в прологе есть кое-какие технические 
детали, но все они должны быть понятны даже человеку, не обучавшемуся в 
университете, а глава 1 содержит сжатый общий обзор материала, изложенного 
в книге. Обе главы можно бесплатно скачать с сайта книги по адресу www.cs.bris.
ac.uk/~fl ach/mlbook; со временем будут добавлены и другие материалы, в частности 
лекционные слайды. Поскольку в книге такого объема неизбежны мелкие погрешности, 
на сайте имеется форма, с помощью которой мне можно отправить 
извещения о замеченных ошибках и опечатках.

Благодарности

Работа над книгой одного автора всегда была уделом одиночек, но мне повезло – 
я пользовался помощью и поддержкой многочисленных друзей и коллег. Тим 
Ковач (Tim Kovacs) в Бристоле, Люк де Редт (Luc De Raedt) в Лёвене и Карла 
Бродли (Carla Brodley) в Бостоне организовали группы читателей, от которых 
я получал весьма полезные отзывы. Своими замечаниями со мной любезно поделились 
также Хендрик Блокил (Hendrik Blockeel), Натали Япковиц (Nathalie 
Japkowicz), Николас Лашиш (Nicolas Lachiche), Мартин ван Отерло (Martijn van 
Otterlo), Фабрицио Ригуци (Fabrizio Riguzzi) и Мохак Шах (Mohak Shah). Тем 
или иным способом мне помогали и многие другие – спасибо всем.
Хосе Хернандес-Оралло (Jose Hernandez-Orallo), выйдя далеко за пределы 
служебных обязанностей, внимательно прочитал рукопись и высказал много 
конструктивных критических замечаний, которые я учел в той мере, в какой позволяло 
время. Хосе, с меня причитается.
Большое спасибо моим коллегам по Бристольскому университету: Тареку Абу-
давуду (Tarek Abudawood), Рафалу Богачу (Rafal Bogacz), Тило Бургхардту (Tilo 
Burghardt), Нелло Кристианини (Nello Cristianini), Тийл де Бье (Tijl De Bie), 
Бруно Голениа (Bruno Golenia), Саймону Прайсу (Simon Price), Оливеру Рэю 
(Oliver Ray) и Себастьяну Шпиглеру (Sebastian Spiegler) – за совместную работу 
и поучительные дискуссии. Благодарю также своих зарубежных коллег Иохан-
неса Фурнкранца (Johannes Furnkranz), Цезаря Ферри (Cesar Ferri), Томаса 

Предисловие

Гарт нера (Thomas Gartner), Хосе Хернандес-Оралло, Николаса Лашиша (Nicolas 
Lachiche), Джона Ллойда (John Lloyd), Эдсона Мацубара (Edson Matsubara) и 
Роналдо Прати (Ronaldo Prati) за разрешение использовать в книге результаты 
нашей совместной работы и за иную помощь. В те моменты, когда проекту требовалось 
резкое ускорение, мне любезно обеспечивали уединение Керри, Пол, 
Дэвид, Рэни и Тринти.
Дэвид Транах (David Tranah) из издательства Кэмбридж Юниверсити Пресс 
всемерно содействовал запуску проекта и предложил пуантилистскую метафору 
для «извлечения знаний из данных», которая нашла отражение в рисунке на обложке 
книги (по мысли Дэвида, это «обобщенный силуэт», не обладающий портретным 
сходством ни с кем конкретно). Мэйри Сазерленд (Mairi Sutherland) 
тщательно отредактировала рукопись перед сдачей в набор.
Я посвящаю свой труд покойному отцу, который, безусловно, откупорил бы 
бутылку шампанского, узнав, что «эта книга» наконец закончена. Его трактовка 
проблемы индукции наводила на интересные, хотя и мрачноватые, размышления: 
та же рука, что каждый день кормит курицу, однажды сворачивает ей шею 
(приношу извинения читателям-вегетарианцам). Я благодарен своим родителям 
за то, что они снабдили меня всем необходимым для поиска собственного жизненного 
пути.
И наконец, не выразить словами все, чем я обязан своей жене Лайзе. Я начал 
писать эту книгу вскоре после нашей свадьбы, и мы даже представить не могли, 
что на эту работу уйдет почти четыре года. Ретроспективный взгляд – отличная 
штука: например, таким образом можно установить, что попытка закончить книгу 
одновременно с организацией международной конференции и капитальным 
ремонтом дома – не самая здравая мысль. Но наградой Лайзе за поддержку, ободрение 
и молчаливые страдания стал тот факт, что все три вещи все-таки приближаются 
к успешному завершению. Спасибо, любимая!

Петер Флах, Бристоль

Пролог: пример машинного обучения

О

чень может быть, что вы, сами того не подозревая, давно уже пользуетесь 
технологиями машинного обучения. В большинство почтовых клиентов 
встроены алгоритмы определения и фильтрации спама, или нежелательной 
почты. Первые фильтры спама основывались на технике сопоставления с образцами, 
например с регулярными выражениями, причем сами образцы кодировались 
вручную. Однако скоро стало понятно, что этот подход непригоден для 
сопровождения и зачастую не обладает достаточной гибкостью – ведь что для 
одного спам, то для другого желанное послание1! Необходимая адаптивность и 
гибкость достигается с помощью методов машинного обучения. 
SpamAssassin – широко известный фильтр спама с открытым исходным кодом. 
Он вычисляет оценку входящего почтового сообщения, опираясь на ряд встроенных 
правил, или «критериев» и, если оценка оказывается не менее 5, включает 
в заголовки сообщения признак «спам» и сводный отчет. Вот пример отчета для 
полученного мной сообщения:

-0.1 RCVD_IN_MXRATE_WL RBL:  
 
MXRate recommends allowing
 
 
 
 
 
[123.45.6.789 listed in sub.mxrate.net]
0.6 HTML_IMAGE_RATIO_02 BODY:   
HTML has a low ratio of text to image area
1.2 TVD_FW_GRAPHIC_NAME_MID BODY: 
TVD_FW_GRAPHIC_NAME_MID
0.0 HTML_MESSAGE BODY:   
 
HTML included in message
0.6 HTML_FONx_FACE_BAD BODY:  
 
HTML font face is not a word
1.4 SARE_GIF_ATTACH FULL:  
 
Email has a inline gif
0.1 BOUNCE_MESSAGE  
 
 
MTA bounce message
0.1 ANY_BOUNCE_MESSAGE   
 
Message is some kind of bounce message
1.4 AWL  
 
 
 
AWL: From: address is in the auto white-list

Слева направо идут: оценка, вычисленная для данного критерия, идентификатор 
критерия и краткое описание, содержащее ссылку на релевантную часть 
сообщения. Как видим, оценка критерия может быть как отрицательной (свидетельство 
в пользу того, что сообщение не является спамом), так и положительной. 
Поскольку итоговая оценка равна 5.3, то сообщение может быть спамом. 
На самом деле это конкретное сообщение было уведомлением от промежуточного 
сервера о том, что какое-то другое сообщение, с чудовищной оценкой 14.6, 
было сочтено спамом и отвергнуто. В сообщение о недоставке было включено и 
исходное сообщение, а значит, оно унаследовало кое-какие характеристики по-

1 Слово spam произошло от слияния двух слов: «spiced ham» (пряная ветчина). Так называлось 
мясное изделие, получившее недобрую славу после высмеивания в сериале 
«Летающий цирк Монти Пайтона». Поэтому в оригинале употреблена игра слов «one 
person’s spam is another person’s ham» – «что одному спам, то другому ветчина». – Прим. 
перев.

Пролог: пример машинного обучения

следнего, в частности низкое отношение текста к графике; отсюда и оценка, превышающая 
пороговое значение 5.
А вот пример важного письма, которого я долго ждал и в конце концов обнаружил 
в папке для спама:

2.5 URI_NOVOWEL URI:  
   URI hostname has long non-vowel sequence
3.1 FROM_DOMAIN_NOVOWEL     From: domain has series of non-vowel letters

Это письмо касалось работы, которую мы с коллегой отправили на Европейскую 
конференцию по машинному обучению (ECML) и на Европейскую конференцию 
по принципам и практическим методам выявления знаний в базах 
данных (European Conference on Principles and Practice of Knowledge Discovery 
in Databases  – PKDD), которые, начиная с 2001 года, проводятся совместно. 
Для освещения этих конференций, состоявшихся в 2008 году, в Интернете был 
создан домен www.ecmlpkdd2008.org, пользующийся заслуженно высокой репутацией 
у специалистов по машинному обучению. Однако в имени домена подряд 
идут одиннадцать согласных – вполне достаточно, чтобы возбудить подозрения 
у SpamAssassin! Этот пример наглядно демонстрирует, что ценность критериев 
SpamAssassin для разных пользователей может быть различна. Машинное обучение – 
великолепный способ создания программ, адаптирующихся к пользователю.




Как SpamAssassin вычисляет оценки, или «веса», для каждого из нескольких 
десятков критериев? Вот тут-то и приходит на помощь машинное обучение. Допустим, 
что имеется большой «обучающий набор» почтовых сообщений, которые 
были вручную помечены как «спам» или «неспам», и для каждого сообщения 
известны результаты по каждому критерию. Наша цель – вычислить вес для 
каждого критерия таким образом, чтобы все спамные сообщения получили итоговую 
оценку выше 5, а все хорошие – оценку ниже 5. В этой книге мы будем 
обсуждать различные способы решения этой задачи. А пока на простом примере 
проил люстрируем основную идею.

Пример 1 (линейная классификация ). Предположим, что есть только два критерия и четыре 
обучающих сообщения, одно из которых – спам (см. табл. 1). Для спамного сообщения оба критерия 
удовлетворяются, для одного хорошего не удовлетворяется ни один критерий, для второго 
удовлетворяется только первый, а для третьего – только второй. Легко видеть, что, приписав 
каждому критерию вес 4, мы сможем правильно «классифицировать» все четыре сообщения. 
В математической нотации, описываемой в замечании 1, этот классификатор можно было бы 
записать в виде 4x1 + 4x2 > 5 или (4,4) · (x1,x2) > 5. На самом деле при любом весе между 2.5 и 5 
порог будет превышен, только когда удовлетворяются оба критерия. Можно было бы даже назначить 
критериям разные веса – при условии, что каждый из них меньше 5, а сумма больше 5; 
правда, не понятно, зачем нужны такие сложности при имеющихся обучающих данных.