Математические методы распознавания образов

МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ
РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное бюджетное образовательное учреждение
высшего образования
ОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
им. Ф.М. ДОСТОЕВСКОГО

А.В. Пролубников

МАТЕМАТИЧЕСКИЕ МЕТОДЫ
РАСПОЗНАВАНИЯ ОБРАЗОВ

Учебное пособие

Омск

2020

УДК 519.7
ББК 22.19я73
П809

Рецензенты:
д-р физ.-мат. наук А.Н. Шевляков,
канд. физ.-мат. наук И.А. Латыпов

Пролубников, А. В.

П809
Математические методы распознавания образов :
учебное пособие / А. В. Пролубников. — Омск : Изд-во
Ом. гос. ун-та, 2020. — 110 с.

ISBN 978-5-7779-2461-2

Рассматриваются наиболее популярные и широкие по своим приложениям подходы к решению задач распознавания образов и классификации.
Включает задачи по рассматриваемым темам.
Для студентов ИМИТ ОмГУ.

УДК 519.7
ББК 22.19я73

c○ Пролубников А.В., 2020
ISBN 978-5-7779-2461-2
c○ ФГБОУ ВО «ОмГУ
им. Ф.М. Достоевского», 2020

ОГЛАВЛЕНИЕ

Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5

1. Задачи распознавания образов и подходы
к их решению. Регистрация информации
. . . . . . . . . . . . . . .
7
1.1. Распознавание образов и машинное обучение . . . . . . . . . . . . . . .
7
1.1.1. Обучение с учителем . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
1.1.2. Обучение без учителя . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
1.2. Вектор признаков . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
1.3. Регистрация информации. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
1.3.1. Машинное восприятие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
1.3.2. Зашумление . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
1.3.3. Ошибки измерений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16

2. Элементы теории вероятностей
и математической статистики . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
2.1. Случайная величина . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
2.2. Равномерное и нормальное распределения . . . . . . . . . . . . . . . . . .
18
2.3. Центральная предельная теорема . . . . . . . . . . . . . . . . . . . . . . . . . .
21
2.4. Генерирование нормально распределённой
случайной величины . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
2.4.1. Табличный способ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
2.4.2. Способ, использующий центральную
предельную теорему . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
24
2.5. Формула Байеса и её применение в методах решения
задач распознавания образов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
25
2.5.1. Формула Байеса . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
25
2.5.2. Байесовский классификатор для распознавания
спама . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
26
Задания . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
29

3. Метод ближайшего соседа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
31
3.1. Метод ближайшего соседа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
31
3.2. Мера близости . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
31
3.3. Выбор параметров и дополнительные процедуры . . . . . . . . . . .
34
3.4. Проклятие размерности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
37
3.5. Распознавание растровых изображений с помощью
метода ближайшего соседа. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
41
Задания . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
43

3

4. Метод наименьших квадратов для решения задач
регрессионного анализа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
45
4.1. Задача регрессионного анализа и метод наименьших
квадратов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
45
4.2. Линейная регрессия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
46
4.3. Полиномиальная регрессия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
50
4.4. Переобучение и способы его устранения . . . . . . . . . . . . . . . . . . . .
50
4.4.1. Регуляризация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
52
4.4.2. Кросс-валидация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
53
4.5. Метод наименьших квадратов и метод наибольшего
правдоподобия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
56
4.6. Случай неизвестного распределения ошибки. . . . . . . . . . . . . . . .
59
Задания . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
63

5. Нейронные сети . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
65
5.1. Перцептрон . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
65
5.2. Многослойный перцептрон. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
71
5.3. Обучение нейронной сети . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
77
5.4. Вычисление градиента функции ошибки . . . . . . . . . . . . . . . . . . .
80
5.4.1. Приближённое вычисление . . . . . . . . . . . . . . . . . . . . . . . . . .
80
5.4.2. Метод обратного распространения ошибки . . . . . . . . . . .
81
Задания . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
84

6. Байесовская теория решений . . . . . . . . . . . . . . . . . . . . . . . . . . . .
86
6.1. Байесовское решающее правило. . . . . . . . . . . . . . . . . . . . . . . . . . . .
86
6.2. Минимизация ошибки и условный риск . . . . . . . . . . . . . . . . . . . .
89
6.3. Классификация в случае двух классов . . . . . . . . . . . . . . . . . . . . .
93
6.4. Задача классификации с возможным отказом от принятия
решения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
95
6.5. Разделяющие функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
96
6.6. Дискретный случай . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
Задания . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104

Литература
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

4

Введение

Распознавание образов — научная область, для которой характерна прикладная направленность исследований. Множество различных подходов к решению задач классификации и регрессии разработано для решения задач распознавания образов. В этой области широко применяются методы машинного обучения. Эти методы стали особенно распространены в последние десятилетия и широко применяются на практике в связи с возросшей доступностью
достаточных для их реализации вычислительных ресурсов.
В главе 1 даются типичные постановки задач распознавания образов, представляются подходы к машинному обучению с учителем
и без учителя. Рассматриваются вопросы, связанные с формированием вектора признаков, измерением их значений и возникающими
при этом ошибками.
Остальные главы пособия посвящены подходам к решению задач классификации и восстановления функциональной зависимости — это метод ближайшего соседа, линейная и полиномиальная
регрессия, метод нейронных сетей прямого распространения, байесовская теория решений. Рассматриваются процедуры, используемые при реализации этих подходов (нормализация, регуляризация,
кросс-валидация и др.).
Метод наибольшего правдоподобия используется в пособии при
рассмотрении задач регрессионного анализа в двух случаях: для
случая нормального распределения ошибки и для случая, когда
распределение ошибки неизвестно. В пособии показывается, что
во втором случае обоснованным является использование равномерного распределения. Показывается, что вид минимизируемой при
использовании метода наибольшего правдоподобия нормы вектора
ошибки определяется её распределением.

5

Главы пособия сопровождаются заданиями двух типов:
1) вопросы и задачи по темам раздела,
2) задания для программной реализации.

Настоящее пособие представляет собой введение в предмет и сосредоточено на тех разделах распознавания образов, которые, с одной стороны, являются базовыми для распознавания образов как
научной области, с другой, являются доступными для изложения
студентам в ограниченное учебной программой количество часов.
Изучение курса рассчитано на один семестр — 48 часов лекционных занятий. Для выполнения заданий и упражнений по курсу
предполагаются достаточными 64 часа в течение семестра, включая семинары по курсу.

6

1. ЗАДАЧИ РАСПОЗНАВАНИЯ ОБРАЗОВ
И ПОДХОДЫ К ИХ РЕШЕНИЮ.
РЕГИСТРАЦИЯ ИНФОРМАЦИИ

1.1. Распознавание образов и машинное обучение

Распознавание образов — это научное направление, связанное
с разработкой методов для нахождения в данных закономерностей, а также для установления принадлежности некоторого объекта (предмета, процесса, явления, ситуации, сигнала) к одному
из заранее выделенных классов объектов. Процесс распознавания
основан на сопоставлении признаков, характеризующих исследуемый объект с признаками других известных объектов, в результате
чего делается вывод о наиболее правдоподобном их соответствии.
Математические методы распознавания образов используются
для решения таких прикладных задач, как распознавание почерка и речи, лиц, классификации текстов по рубрикам, распознавания штрих-кодов, автомобильных номеров, изображений, выявления аномальных режимов работы сердца по вариабельности сердечного ритма, распознавания сейсмических режимов и прогнозирования сейсмической опасности и многих других.
В рамках этого учебного пособия мы будем иметь дело с двумя
типами задач распознавания образов:
1) задачи восстановления функциональной зависимости (или задачи регрессионного анализа);
2) задачи классификации — задачи установления принадлежности некоторого объекта одному из заданных классов объектов.
Второй случай может быть рассмотрен как разновидность первого, в котором восстанавливаемая функциональная зависимость
имеет конечную дискретную область значений. Однако, такая спе
7

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

Задача 1. Предполагается существование некоторой неизвестной
функции 𝑓 : 𝑋 → 𝑌 . Задана обучающая выборка — это множество
соответствующих друг другу значений 𝑥 ∈ 𝑋 и 𝑦 ∈ 𝑌 , т. е. набор
пар

{(𝑥(1), 𝑦(1)), (𝑥(2), 𝑦(2)), . . . , (𝑥(𝑁), 𝑦(𝑁))},

где 𝑦(𝑖) = 𝑓(𝑥(𝑖)). Необходимо найти такое отображение ˜𝑓 : 𝑋 → 𝑌 ,
которое было бы как можно более близким к неизвестному отображению 𝑓 в соответствии с некоторым критерием близости.

В случае решения задачи классификации 𝑋 — множество классифицируемых объектов, 𝑌 — множество заданных классов. Близость полученного отображения ˜𝑓 к неизвестному отображению 𝑓
оценивается с помощью обучающей выборки или с помощью другой, контрольной выборки, т. е. других пар соответствующих значений 𝑥 и 𝑦, используемых для такого оценивания.

Для решения задач распознавания образов и классификации
широко используются методы машинного обучения, которые характеризуются тем, что распознаванию (классификации) предшествует стадия обучения, в ходе которой на основе информации,
предоставляемой обучающей выборкой, строится функция ˜𝑓. Стадия обучения представляет собой выбор параметров некоторой математической модели, на основе которой производится распознавание.
Методы машинного обучения подразделяются на два типа:
1) методы обучения с учителем,
2) методы обучения без учителя.

8

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

При обучении с учителем считается заданной обучающая выборка («размеченная выборка»), исходя из которой на стадии обучения строится отображение ˜𝑓. Так, в случае решения задачи классификации предполагается, что имеется некоторый набор объектов, отнесённых к одному из заданных классов.
Примером задачи с заданной обучающей выборкой является
следующая задача 2. Такую постановку будет иметь задача распознавания растровых изображений, которую мы рассмотрим далее.

Задача 2. Пусть задано множество 𝒫 ={𝒫(1), . . . , 𝒫(𝑁)} некоторых
эталонных объектов, как-либо математически описанных. Имеется
объект 𝑃, который представляет собой некоторый объект 𝒫(𝑡) ∈𝒫,
подвергнутый преобразованию, затрудняющему распознавание —
определение того, из какого эталонного объекта в результате этого
преобразования получен 𝑃. Необходимо распознать 𝑃.

Задание множества эталонных объектов 𝒫, относительно которых необходимо классифицировать объект 𝑃, в этой задаче эквивалентно заданию обучающей выборки. Используя обучающую выборку 𝒫 и применяя какой-либо метод машинного обучения, мы
классифицируем объект 𝑃.
Обучение с учителем реализуется при решении задачи распознавания рукописного текста. На стадии обучения на вход алгоритма
классификации подаются образцы написания буквы с указанием
того, какой буквы образец написания подан. При этом для каждой
буквы может быть использовано несколько изображений, отличающихся друг от друга, но позволяющих зафиксировать особенности её начертания. В результате, когда на стадии классификации
на вход алгоритма подаётся изображение буквы, она распознаётся
исходя из зафиксированных на стадии обучения особенностей её
начертания. Предполагается, что распознаваемая буква имеет начертание, вообще говоря, отличное от тех, что были использованы
на стадии обучения.

9

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

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

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

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

10