Математические методы распознавания образов (курс лекций, А.Е. Лепский, А.Г. Броневич)

Материал из MachineLearning.

(Различия между версиями)
Перейти к: навигация, поиск
(Новая: == '''Математические методы распознавания образов (курс лекций, А.Е. Лепский, А.Г. Броневич)''' == ---- '''Мате...)
(Лабораторные работы)
 
(17 промежуточных версий не показаны.)
Строка 1: Строка 1:
-
== '''Математические методы распознавания образов
+
'''Математические методы распознавания образов''' — односеместровый курс лекций, читаемый студентам 4-го курса факультета естественно-научного и гуманитарного образования специальности 010200 «Прикладная математика и информатика» Таганрогского Технологического института Южного федерального университета. Основная цель курса — формирование, прежде всего, математических знаний и навыков по основным разделам теории распознавания образов, привитие навыков разработки детерминистских и стохастических систем распознавания, нейронных сетей, развитие интуиции студентов для лучшего понимания основных идей, лежащих за этими методами.
-
(курс лекций, А.Е. Лепский, А.Г. Броневич)''' ==
+
-
----
+
Авторы курса — А. Е. Лепский, А. Г. Броневич.
-
'''Математические методы распознавания образов''' — односеместровый курс лекций, читаемый студентам 4-го курса факультета естественно-научного и гуманитарного образования специальности 010200 “Прикладная математика и информатика” Таганрогского Технологического института Южного федерального университета. Основная цель курса — формирование, прежде всего, математических знаний и навыков по основным разделам теории распознавания образов, привитие навыков разработки детерминистских и стохастических систем распознавания, нейронных сетей, развитие интуиции студентов для лучшего понимания основных идей, лежащих за этими методами.
+
Лабораторные работы разработаны А. Е. Лепским, А. В. Гончаровым.
-
Авторы курса – А.Е. Лепский, А.Г. Броневич.
+
== Лекции. Часть I. Детерминистский подход в теории распознавания образов ==
 +
 +
=== Предмет распознавания образов ===
 +
# Основные задачи теории распознавания образов.
 +
# Типы характеристик образов.
 +
# Типы систем распознавания.
 +
# Математическая постановка задач распознавания. Распознавание как некорректная задача.
-
Лабораторные работы разработаны А.Е. Лепским, А.В. Гончаровым.
+
=== Классификация с помощью решающих функций ===
 +
# Понятие решающих функций.
 +
# [[Линейный классификатор|Линейные решающие функции (ЛРФ)]].
 +
# Общий подход к нахождению линейных решающих функций. [[Алгоритм Хо-Кашьяпа]].
 +
# Обобщенные решающие функции (ОРФ).
 +
# Задача [[понижение размерности|понижения размерности]].
 +
#* [[Метод главных компонент]].
 +
#* [[Линейный дискриминант Фишера]].
-
{| class="wikitable"
+
=== Классификация с помощью функций расстояния ===
-
|-
+
# Способы стандартизации признаков и векторов-образов.
-
! Содержание
+
# Способы измерения расстояний между векторами признаков.
-
|-
+
# Способы определения расстояния между вектором-образом и классом.
-
| 1 Лекции
+
-
|-
+
-
| 2 Лабораторные работы
+
-
|-
+
-
| 3 Индивидуальные задания
+
-
|-
+
-
| 4 Типовые задачи по курсу
+
-
|-
+
-
| 5 Ссылки
+
-
|}
+
 +
=== Разбиение класса на кластеры ===
 +
# Постановка [[кластеризация|задачи кластеризации]].
 +
# [[Алгоритм k-средних|Алгоритм k-внутригрупповых средних (k-means)]].
 +
# Алгоритмы расстановки центров кластеров.
 +
#* Алгоритм простейшей расстановки центров кластеров.
 +
#* Алгоритм, основанный на методе просеивания.
 +
#* Алгоритм максиминного расстояния.
 +
#* Алгоритм ИСОМАД (ISODATA).
-
[править] '''1. Лекции'''
+
=== Метод (машина) опорных векторов ===
 +
# [[Линейно разделимая выборка| Линейно разделимый случай]].
 +
# [[Линейно неразделимая выборка| Линейно неразделимый случай]].
-
Оглавление
+
=== Нейронные сети и проблемы распознавания ===
-
Основные обозначения
+
# Понятие [[персептрон]]а.
-
Предисловие
+
#* Алгоритм обучения персептрона.
-
Часть I Детерминистский подход в теории распознавания образов
+
#* Сходимость алгоритма персептрона.
-
1. Предмет распознавания образов
+
#* Алгоритм обучения слоя персептронов разделению нескольких классов.
-
1.1. Основные задачи теории распознавания образов
+
# Идеология нейроинформатики.
-
1.2. Типы характеристик образов
+
# Элементы [[нейронная сеть|нейронных сетей]].
-
1.3. Типы систем распознавания
+
# Архитектуры нейронных сетей.
-
1.4. Математическая постановка задач распознавания. Распознавание как некорректная задача
+
# Математические возможности нейронных сетей.
-
2. Классификация с помощью решающих функций
+
# Базовые математические задачи, решаемые нейронными сетями.
-
2.1. Понятие решающих функций
+
# Основные алгоритмы обучения нейронных сетей.
-
2.2. Линейные решающие функции (ЛРФ)
+
#* Алгоритмы обучения одного нейрона.
-
2.3. Общий подход к нахождению линейных решающих функций. Алгоритм Хо-Кашьяпа
+
#** [[Алгоритм Хебба|Алгоритм обучения Хебба]].
-
2.4. Обобщенные решающие функции (ОРФ)
+
#** Персептронный метод обучения.
-
2.5. Задача понижения размерности
+
#** Адаптивное обучение нейрона. Формула Уидроу.
-
2.5.1. Метод главных компонент
+
#* Обучение многослойной НС [[Метод обратного распространения ошибки|методом обратного распространения ошибки]].
-
2.5.2. Линейный дискриминант Фишера
+
#* Алгоритм и [[Нейронная сеть Кохонена|сеть Кохонена]].
-
3. Классификация с помощью функций расстояния
+
#* Сети ассоциативной памяти.
-
3.1. Способы стандартизации признаков и векторов-образов
+
#** Алгоритм и сеть Хопфилда.
-
3.2. Способы измерения расстояний между векторами признаков
+
#** Алгоритм и сеть Хэмминга.
-
3.3. Способы определения расстояния между вектором-образом и классом
+
-
4. Разбиение класса на кластеры (обучающее векторное квантование)
+
-
4.1. Постановка задачи кластеризации
+
-
4.2. Алгоритм k-внутригрупповых средних (k-means)
+
-
4.3. Алгоритмы расстановки центров кластеров
+
-
4.3.1. Алгоритм простейшей расстановки центров кластеров
+
-
4.3.2. Алгоритм, основанный на методе просеивания
+
-
4.3.3. Алгоритм максиминного расстояния
+
-
4.4. Алгоритм ИСОМАД (ISODATA)
+
-
5. Метод (машина) опорных векторов
+
-
5.1. Линейно разделимый случай
+
-
5.2. Линейно неразделимый случай
+
-
6. Нейронные сети и проблемы распознавания
+
-
6.1. Понятие персептрона
+
-
6.1.1. Алгоритм обучения персептрона
+
-
6.1.2. Сходимость алгоритма персептрона
+
-
6.1.3. Алгоритм обучения слоя персептронов разделению нескольких классов
+
-
6.2. Идеология нейроинформатики
+
-
6.3. Элементы нейронных сетей
+
-
6.4. Архитектуры нейронных сетей
+
-
6.5. Математические возможности нейронных сетей
+
-
6.6. Базовые математические задачи, решаемые нейронными сетями
+
-
6.7. Основные алгоритмы обучения нейронных сетей
+
-
6.7.1. Алгоритмы обучения одного нейрона
+
-
6.7.1.1. Алгоритм обучения Хебба
+
-
6.7.1.2. Персептронный метод обучения
+
-
6.7.1.3. Адаптивное обучение нейрона. Формула Уидроу
+
-
6.7.2. Обучение многослойной НС методом обратного распространения ошибки
+
-
6.7.3. Алгоритм и сеть Кохонена
+
-
6.7.4. Сети ассоциативной памяти
+
-
6.7.4.1. Алгоритм и сеть Хопфилда
+
-
6.7.4.2. Алгоритм и сеть Хэмминга
+
-
7. Метод потенциальных функций
+
-
Часть II Статистический подход в теории распознавания образов
+
-
1. Вероятностные характеристики среды распознавания и основные задачи статистической теории распознавания образов
+
-
2. Байесовский классификатор
+
-
2.1. Постановка задачи байесовской классификации
+
-
2.2. Простейший байесовский классификатор
+
-
2.3. Отклонение величины средней ошибки неправильной классификации от наименьшей при небайесовской классификации
+
-
2.4. Обобщенный байесовский классификатор
+
-
3. Минимаксный критерий классификации
+
-
4. Критерий Неймана-Пирсона
+
-
5. Критерии классификации в случае нормального распределения признаков в каждом классе
+
-
5.1. Критерии классификации в случае нормального одномерного распределения признаков
+
-
5.1.1. Байесовская классификация
+
-
5.1.2. Минимаксный классификатор
+
-
5.1.3. Классификатор Неймана-Пирсона
+
-
5.2. Классификация в случае многомерного нормального распределения признаков в классах
+
-
5.2.1. Многомерное нормальное распределение
+
-
5.2.2. Байесовский классификатор для нормального многомерного распределения признаков в классах
+
-
5.2.3. Вероятности ошибки неправильной классификации в случае байесовского классификатора для нормального распределения признаков в классах
+
-
6. Статистическое оценивание вероятностных характеристик
+
-
6.1. Параметрическое оценивание вероятностного распределения
+
-
6.1.1. Метод максимального правдоподобия
+
-
6.1.2. Метод моментов
+
-
6.2. Непараметрические методы оценивания
+
-
6.2.1. Гистограммный метод оценивания
+
-
6.2.2. Адаптивный гистограммный метод оценивания
+
-
6.2.3. Методы локального оценивания
+
-
6.2.3.1. Метод парзеновского окна
+
-
6.2.3.2. Метод kN ближайших соседей
+
-
6.2.3.3. Решающее правило, основанное на методе kN ближайших соседей
+
-
6.2.4. Метод оценивания с помощью аппроксимации функции плотности
+
-
Литература
+
-
Приложение 1. Нахождения дискриминантной функции по прецедентам методом потенциальных функций
+
-
Приложение 2. Построение байесовского классификатора по выборке двумерных нормально распределенных векторов
+
-
Приложение 3. Построение гистограмм функций плотности распределения
+
-
Приложение 4. Построение байесовского классификатора по прецедентам
+
-
[Скачать курс лекций] (PDF)
+
=== Метод потенциальных функций ===
-
----
+
== Лекции. Часть II. Статистический подход в теории распознавания образов ==
-
[править] '''2. Лабораторные работы'''
+
=== Вероятностные характеристики среды распознавания и основные задачи статистической теории распознавания образов ===
-
В качестве основной вычислительной среды для проведения лабораторных работ используется MatLab. Предлагаются к выполнению следующие лабораторные работы:
+
=== Байесовский классификатор ===
 +
# Постановка задачи байесовской классификации
 +
# Простейший [[байесовский классификатор]]
 +
# Отклонение величины средней ошибки неправильной классификации от наименьшей при небайесовской классификации
 +
# Обобщенный байесовский классификатор
-
•определение минимального пространства признаков и построение линейных решающих функций;
+
=== Минимаксный критерий классификации ===
-
•преобразование Хау;
+
 
-
•распознавание с помощью функций расстояния;
+
=== Критерий Неймана-Пирсона ===
-
•алгоритмы кластеризации;
+
 
-
•машина опорных векторов;
+
=== Критерии классификации в случае нормального распределения признаков в каждом классе ===
-
•обучения однослойного персептрона;
+
# Критерии классификации в случае нормального одномерного распределения признаков
-
•алгоритмы обучения Хопфилда и Хэмминга.
+
#* Байесовская классификация
 +
#* Минимаксный классификатор
 +
#* Классификатор Неймана-Пирсона
 +
# Классификация в случае многомерного нормального распределения признаков в классах
 +
#* [[Многомерное нормальное распределение]]
 +
#* Байесовский классификатор для нормального многомерного распределения признаков в классах
 +
#* Вероятности ошибки неправильной классификации в случае байесовского классификатора для нормального распределения признаков в классах
 +
 
 +
=== Статистическое оценивание вероятностных характеристик ===
 +
# Параметрическое оценивание вероятностного распределения
 +
#* [[Метод максимального правдоподобия]]
 +
#* [[Метод моментов]]
 +
# Непараметрические методы оценивания
 +
#* Гистограммный метод оценивания
 +
#* Адаптивный гистограммный метод оценивания
 +
#* Методы локального оценивания
 +
#** [[Метод парзеновского окна]]
 +
#** [[Метод ближайших соседей|Метод ''k'' ближайших соседей]]
 +
#** Решающее правило, основанное на методе ''k'' ближайших соседей
 +
#* Метод оценивания с помощью аппроксимации функции плотности
 +
 
 +
== Приложения ==
 +
# Нахождения дискриминантной функции по прецедентам методом потенциальных функций
 +
# Построение байесовского классификатора по выборке двумерных нормально распределенных векторов
 +
# Построение гистограмм функций плотности распределения
 +
# Построение байесовского классификатора по прецедентам
 +
 
 +
== Литература ==
 +
 
 +
[http://www.lepskiy.ucoz.com/lect_Lepskiy_Bronevich_pass.pdf скачать курс лекций] (2.23 Mb, PDF)
 +
 
 +
[http://www.lepskiy.ucoz.ru/_1_pass.pdf скачать презентацию к курсу лекций, часть 1] (4.3 Mb, PDF)
 +
 
 +
[http://www.lepskiy.ucoz.ru/_2_pass.pdf скачать презентацию к курсу лекций, часть 2] (1.5 Mb, PDF)
 +
 
 +
== Лабораторные работы ==
 +
 
 +
В качестве основной вычислительной среды для проведения лабораторных работ используется [[MatLab]].
 +
Предлагаются к выполнению следующие лабораторные работы:
 +
 
 +
* определение минимального пространства признаков и построение линейных решающих функций;
 +
* преобразование Хау;
 +
* распознавание с помощью функций расстояния;
 +
* [[кластеризация|алгоритмы кластеризации]];
 +
* [[машина опорных векторов]];
 +
* обучение [[однослойный персептрон|однослойного персептрона]];
 +
* алгоритмы обучения Хопфилда и Хэмминга.
Задания к лабораторным работам включают реализации алгоритмов распознавания образов и/или экспериментальное сравнение таких алгоритмов между собой.
Задания к лабораторным работам включают реализации алгоритмов распознавания образов и/или экспериментальное сравнение таких алгоритмов между собой.
-
Методические указания к практическим и лабораторным занятиям [Скачать] (PDF)
+
Методические указания к практическим и лабораторным занятиям [http://www.lepskiy.ucoz.ru/Posobie/2005_MMAI_laboratory.pdf скачать] (PDF)
-
----
+
 
 +
== Индивидуальные задания ==
 +
В рамках курса предусмотрено выполнение индивидуальных заданий. Необходимо предложить решение одной из сформулированных ниже задач и осуществить программную реализацию предложенных методов. По результатам проделанной работы нужно составить отчет, в котором необходимо обосновать выбор метода решения задачи, а также провести исследование предложенных методов по следующим критериям: качество работы, требования к вычислительным ресурсам, скорость работы, область применимости. Отчет также должен содержать четкую математическую постановку решаемой задачи, краткий обзор (1 — 2 с.) существующих подходов к решению этой задачи, описание предложенных алгоритмов и методов, листинг программы (с комментариями), список используемой литературы.
 +
Предлагаемые к решению задачи по характеру анализируемой информации разделены на группы (текст, звук, изображения). Кроме перечисленных ниже задач, можно предложить свою задачу, при этом необходимо обосновать ее актуальность.
 +
 
 +
=== Текст ===
 +
 
 +
'''1. Система классификации текстов по жанрам (поэзия, роман, фантастика и т.п.)'''
 +
 
 +
Крупный книжный интернет-магазин решил привлечь новых покупателей за счет размещения на своем сайте удобного рубрикатора книжных произведений. При этом выяснилось, что для 70% книг отсутствует информация о жанре произведения, что не позволяет их добавить в пользовательский рубрикатор, а следовательно снижает уровень продаж. Поскольку в ассортименте интернет-магазина находится более 100 000 наименований, руководство магазина отказалось от ручной классификации книг и обратилось к Вам с просьбой разработать метод, позволяющий автоматически классифицировать книги. О книгах доступна следующая информация: изображение обложки, имена авторов, название книги, год издания, аннотация и текст первых 20-30 страниц с сохранением оригинального форматирования. Необходимо предложить метод, позволяющий на основании доступной информации автоматически классифицировать книги. Кроме того, предложить способ визуализации рубрикатора.
 +
 
 +
'''2.Система проверки авторства литературных произведений'''
 +
 
 +
Авторитетные члены литерного сообщества часто спорят относительно авторства некоторых малоизвестных произведений классиков. Сомнения относительно авторства обычно связаны с тем, что по мнению критиков, стиль этих произведений не соответствует стилю автора. Литературное сообщество обратилось к Вам с просьбой разработать метод, позволяющий на основе анализа текстов известных произведений автора определить, является ли анализируемый текст также произведением этого автора.
 +
 
 +
'''3. Построение рекомендующей системы для литературных произведений'''
 +
 
 +
Крупная фирма построила свой бизнес на том, что каждый месяц высылает своим клиентам одну из книжных новинок по своему усмотрению. Клиенты по электронной почте сообщают компании, понравилась ли им данная книга или нет. Компания стремится к тому, что бы удовлетворить вкусы своих клиентов, а именно каждый раз направлять клиенту интересную для него книгу. Бизнес оказался очень успешным, и компания уже не может вручную отслеживать вкусы каждого клиента, так как их число превысило 10000. Руководство этой фирмы обратилось к Вам с просьбой разработать рекомендующую систему для литературных произведений. В Вашем распоряжении история каждого клиента за последние три года, а именно, список книг, понравившихся и не понравившихся читателю.
 +
 +
'''4. Система выявление плагиата в текстовых документах'''
 +
 
 +
Аттестационная комиссия ведущего российского вуза всерьез обеспокоилась качеством поступающих на защиту дипломных работ. За последние годы резко возросло количество случаев выявления плагиата в работах по гуманитарным наукам. Принимая во внимание особую важность вопроса, принято решение разработать автоматическую систему обнаружения плагиата. В соответствии с принятым решением объявлен тендер на разработку программного обеспечения для выявления плагиата в текстовых документах. В распоряжении разработчика передаются электронные версии выпускных работ за последние 10 лет.
 +
 
 +
'''5. Система выявления плагиата в текстах программ'''
 +
 
 +
Крупнейшая девелоперская фирма после нескольких судебных исков относительно использования открытого программного кода в своих коммерческих продуктах решила внедрить систему внутреннего контроля качества, осуществляющую автоматическую проверку текстов программ, написанных сотрудниками фирмы, на предмет схожести с доступным открытым программным кодом. Поскольку все программисты фирмы погружены в текущие проекты, принято решение открыть новый отдел по разработке данной системы. Вам поручено возглавить этот отдел и в кратчайшие сроки разработать первую версию системы контроля качества.
 +
 
 +
=== Звук ===
 +
 
 +
'''6. Разработка системы поиска нечетких дубликатов'''
 +
 
 +
Для борьбы с пиратством в сфере музыкальных произведений было предложено разработать поисковый сервис, позволяющий находить в Сети незаконные копии музыкальных произведений. Выяснилось, что простое сравнение файлов по формальным признакам не приводит к удовлетворительным результатом, поскольку пиратские копии зачастую искажены (например, из-за сжатия, преобразования формата файлов, преобразования многоканального звука в стерео формат и т.п.). Вам необходимо разработать способ выявления нечетких дубликатов музыкальных произведений, а также предложить способ поиска пиратских сайтов в Сети.
 +
 +
'''7. Разработка системы навигации по большим музыкальным коллекциям'''
 +
 
 +
Крупный производитель mp3-плееров решил порадовать своих покупателей интеллектуальными возможностями очередной новинки. Планируемый объем памяти новинки превышает 100 ГБ, таким образом, остро встает проблема навигации по музыкальным коллекциям и поиска нужного произведения. Вам необходимо разработать метод визуализации музыкальных коллекций, а также разработать процедуру формирования списков произведения по запросу пользователя.
 +
 
 +
'''8. Разработка рекомендующей системы музыкальных произведений'''
 +
 
 +
Крупный интернет-магазин, специализирующийся на продаже музыкальных альбомов решил повысить объем продаж за счет внедрения рекомендующей системы. В базе данных магазина храниться информация о всех покупателях, а именно список покупок каждого клиента. Вам предложено заняться разработкой рекомендующего сервиса музыкальных произведений, основываясь на накопленную информацию о предыдущих покупках.
 +
 
 +
=== Изображения ===
 +
 
 +
'''9. Классификация изображений по жанрам'''
 +
 
 +
Популярный интернет-сервис планирует ввести новую систему навигации по коллекции изображений. Основная идея предлагаемой системы навигации заключается в разделении некоторой области на подобласти, соответствующие тематикам изображений. Технический отдел компании обратился к Вам с просьбой разработать соответствующий алгоритм кластеризации изображений по жанрам. Для разработки метода кластеризации Вам предоставлена часть коллекции изображений, для которых пользователи добавили описание (тэги). Предложенный способ кластеризации должен удовлетворять следующим требованиям: похожие изображения должны отображаться в близки точки на плоскости навигации, а изображениям из различных жанров должны соответствовать удаленные точки плоскости навигации.
 +
 
 +
'''10. Разработка системы поиска нечетких дубликатов изображений'''
 +
 
 +
Популярный интернет-сервис для защиты авторских прав своих пользователей решила внедрить поисковую систему, позволяющую отслеживать незаконное появление авторских фотографий в Сети. Как правило, ворованные фотографии подвергаются некоторой обработке — масштабированию, изменению гаммы, кадрированию и т.п. Технический отдел компании предложил Вам разработать метод поиска нечетких дубликатов изображений в Сети. Обычной практикой при нахождении незаконного размещения изображения является отправка грозного письма в адрес администрации соответствующего сайта. Ввиду того, что ежедневно более 1000 пользователей обращаются с жалобами на подобное нарушение, необходимо рассмотреть возможность сделать процесс обработки подобных случаев полностью автоматическим. Для оценки такой возможности, нужно рассчитать характеристику поискового алгоритма в терминах полнота/точность.
-
[править] '''3. Индивидуальные задания'''
+
'''11. Построение рекомендующей системы изображений'''
-
В рамках курса предусмотрено выполнение индивидуальных заданий.
+
Интернет-портал решил привлечь новых пользователей за счет внедрения системы, которая бы анализировала страницы, посещаемые пользователями и предлагала им для просмотра интересные фотографии. Вам поручено разработать рекомендующую систему изображений, основываясь на логах сервера о посещаемых страницах сайта.
-
Примерные темы индивидуальных заданий:
+
'''12. Поиск изображений по содержанию'''
-
----
+
-
[править] '''4. Типовые задачи по курсу'''
+
Крупный поисковый портал решил привлечь новых пользователей за счет расширения функциональных возможностей медийного поиска. Традиционно, при поиске картинок по текстовому запросу результат формируется на основе текста, размещенного рядом с картинкой. Идея нового сервиса состоит в том, чтобы брать найденные по текстовому поиску изображения в качестве запроса для поиска изображений по содержанию и таким образом расширять результаты поиска. Вам необходимо разработать метод поиска изображений по графическому запросу и охарактеризовать его работоспособность по таким критериям, как полнота/точность, скорость обработки запроса, размер индекса.
-
[Скачать типовые задачи] (PDF)
+
'''13. Система извлечения информации из изображений для маркетинговых исследований'''
-
[править]''' 5. Ссылки'''
+
Отделение фирмы, специализирующееся на разработке мобильных телефонов решило провести крупное маркетинговое исследование. Для разработки рекламной кампании маркетологи решили проанализировать, какие модели телефонов привлекают внимание тех или иных социальных групп. Было установлено, что наиболее существенной является информация о поле и возрасте покупателя, а так же о том, какие эмоции возникают у покупателей при первом взгляде на телефон (разочарование, удивление или отсутствие каких либо эмоций). Технический отдел разместил на витринах с телефонами скрытые видеокамеры, позволяющие фиксировать лица людей, которые обратили свое внимание на конкретную модель телефона. Перед Вами поставлена задача определить по 10 секундной видеозаписи пол и возраст потенциального покупателя, а также характер эмоций, вызываемый конкретной моделью телефона.
 +
== Ссылки ==
 +
* [http://www.lampai.tsure.ru Лаборатория математических методов искусственного интеллекта] Технологического института Южного федерального университета в г.Таганроге.
 +
*А.Е. Лепский - страница участника, [[Участник:Лепский Александр]]
 +
*[http://lepskiy.ucoz.ru А.Е. Лепский - домашняя страница на русском]
 +
*[http://lepskiy.ucoz.com А.Е. Лепский - домашняя страница на английском]
[[Категория:Учебные курсы]]
[[Категория:Учебные курсы]]

Текущая версия

Математические методы распознавания образов — односеместровый курс лекций, читаемый студентам 4-го курса факультета естественно-научного и гуманитарного образования специальности 010200 «Прикладная математика и информатика» Таганрогского Технологического института Южного федерального университета. Основная цель курса — формирование, прежде всего, математических знаний и навыков по основным разделам теории распознавания образов, привитие навыков разработки детерминистских и стохастических систем распознавания, нейронных сетей, развитие интуиции студентов для лучшего понимания основных идей, лежащих за этими методами.

Авторы курса — А. Е. Лепский, А. Г. Броневич.

Лабораторные работы разработаны А. Е. Лепским, А. В. Гончаровым.

Содержание

Лекции. Часть I. Детерминистский подход в теории распознавания образов

Предмет распознавания образов

  1. Основные задачи теории распознавания образов.
  2. Типы характеристик образов.
  3. Типы систем распознавания.
  4. Математическая постановка задач распознавания. Распознавание как некорректная задача.

Классификация с помощью решающих функций

  1. Понятие решающих функций.
  2. Линейные решающие функции (ЛРФ).
  3. Общий подход к нахождению линейных решающих функций. Алгоритм Хо-Кашьяпа.
  4. Обобщенные решающие функции (ОРФ).
  5. Задача понижения размерности.

Классификация с помощью функций расстояния

  1. Способы стандартизации признаков и векторов-образов.
  2. Способы измерения расстояний между векторами признаков.
  3. Способы определения расстояния между вектором-образом и классом.

Разбиение класса на кластеры

  1. Постановка задачи кластеризации.
  2. Алгоритм k-внутригрупповых средних (k-means).
  3. Алгоритмы расстановки центров кластеров.
    • Алгоритм простейшей расстановки центров кластеров.
    • Алгоритм, основанный на методе просеивания.
    • Алгоритм максиминного расстояния.
    • Алгоритм ИСОМАД (ISODATA).

Метод (машина) опорных векторов

  1. Линейно разделимый случай.
  2. Линейно неразделимый случай.

Нейронные сети и проблемы распознавания

  1. Понятие персептрона.
    • Алгоритм обучения персептрона.
    • Сходимость алгоритма персептрона.
    • Алгоритм обучения слоя персептронов разделению нескольких классов.
  2. Идеология нейроинформатики.
  3. Элементы нейронных сетей.
  4. Архитектуры нейронных сетей.
  5. Математические возможности нейронных сетей.
  6. Базовые математические задачи, решаемые нейронными сетями.
  7. Основные алгоритмы обучения нейронных сетей.

Метод потенциальных функций

Лекции. Часть II. Статистический подход в теории распознавания образов

Вероятностные характеристики среды распознавания и основные задачи статистической теории распознавания образов

Байесовский классификатор

  1. Постановка задачи байесовской классификации
  2. Простейший байесовский классификатор
  3. Отклонение величины средней ошибки неправильной классификации от наименьшей при небайесовской классификации
  4. Обобщенный байесовский классификатор

Минимаксный критерий классификации

Критерий Неймана-Пирсона

Критерии классификации в случае нормального распределения признаков в каждом классе

  1. Критерии классификации в случае нормального одномерного распределения признаков
    • Байесовская классификация
    • Минимаксный классификатор
    • Классификатор Неймана-Пирсона
  2. Классификация в случае многомерного нормального распределения признаков в классах
    • Многомерное нормальное распределение
    • Байесовский классификатор для нормального многомерного распределения признаков в классах
    • Вероятности ошибки неправильной классификации в случае байесовского классификатора для нормального распределения признаков в классах

Статистическое оценивание вероятностных характеристик

  1. Параметрическое оценивание вероятностного распределения
  2. Непараметрические методы оценивания
    • Гистограммный метод оценивания
    • Адаптивный гистограммный метод оценивания
    • Методы локального оценивания
    • Метод оценивания с помощью аппроксимации функции плотности

Приложения

  1. Нахождения дискриминантной функции по прецедентам методом потенциальных функций
  2. Построение байесовского классификатора по выборке двумерных нормально распределенных векторов
  3. Построение гистограмм функций плотности распределения
  4. Построение байесовского классификатора по прецедентам

Литература

скачать курс лекций (2.23 Mb, PDF)

скачать презентацию к курсу лекций, часть 1 (4.3 Mb, PDF)

скачать презентацию к курсу лекций, часть 2 (1.5 Mb, PDF)

Лабораторные работы

В качестве основной вычислительной среды для проведения лабораторных работ используется MatLab. Предлагаются к выполнению следующие лабораторные работы:

Задания к лабораторным работам включают реализации алгоритмов распознавания образов и/или экспериментальное сравнение таких алгоритмов между собой.

Методические указания к практическим и лабораторным занятиям скачать (PDF)

Индивидуальные задания

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

Текст

1. Система классификации текстов по жанрам (поэзия, роман, фантастика и т.п.)

Крупный книжный интернет-магазин решил привлечь новых покупателей за счет размещения на своем сайте удобного рубрикатора книжных произведений. При этом выяснилось, что для 70% книг отсутствует информация о жанре произведения, что не позволяет их добавить в пользовательский рубрикатор, а следовательно снижает уровень продаж. Поскольку в ассортименте интернет-магазина находится более 100 000 наименований, руководство магазина отказалось от ручной классификации книг и обратилось к Вам с просьбой разработать метод, позволяющий автоматически классифицировать книги. О книгах доступна следующая информация: изображение обложки, имена авторов, название книги, год издания, аннотация и текст первых 20-30 страниц с сохранением оригинального форматирования. Необходимо предложить метод, позволяющий на основании доступной информации автоматически классифицировать книги. Кроме того, предложить способ визуализации рубрикатора.

2.Система проверки авторства литературных произведений

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

3. Построение рекомендующей системы для литературных произведений

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

4. Система выявление плагиата в текстовых документах

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

5. Система выявления плагиата в текстах программ

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

Звук

6. Разработка системы поиска нечетких дубликатов

Для борьбы с пиратством в сфере музыкальных произведений было предложено разработать поисковый сервис, позволяющий находить в Сети незаконные копии музыкальных произведений. Выяснилось, что простое сравнение файлов по формальным признакам не приводит к удовлетворительным результатом, поскольку пиратские копии зачастую искажены (например, из-за сжатия, преобразования формата файлов, преобразования многоканального звука в стерео формат и т.п.). Вам необходимо разработать способ выявления нечетких дубликатов музыкальных произведений, а также предложить способ поиска пиратских сайтов в Сети.

7. Разработка системы навигации по большим музыкальным коллекциям

Крупный производитель mp3-плееров решил порадовать своих покупателей интеллектуальными возможностями очередной новинки. Планируемый объем памяти новинки превышает 100 ГБ, таким образом, остро встает проблема навигации по музыкальным коллекциям и поиска нужного произведения. Вам необходимо разработать метод визуализации музыкальных коллекций, а также разработать процедуру формирования списков произведения по запросу пользователя.

8. Разработка рекомендующей системы музыкальных произведений

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

Изображения

9. Классификация изображений по жанрам

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

10. Разработка системы поиска нечетких дубликатов изображений

Популярный интернет-сервис для защиты авторских прав своих пользователей решила внедрить поисковую систему, позволяющую отслеживать незаконное появление авторских фотографий в Сети. Как правило, ворованные фотографии подвергаются некоторой обработке — масштабированию, изменению гаммы, кадрированию и т.п. Технический отдел компании предложил Вам разработать метод поиска нечетких дубликатов изображений в Сети. Обычной практикой при нахождении незаконного размещения изображения является отправка грозного письма в адрес администрации соответствующего сайта. Ввиду того, что ежедневно более 1000 пользователей обращаются с жалобами на подобное нарушение, необходимо рассмотреть возможность сделать процесс обработки подобных случаев полностью автоматическим. Для оценки такой возможности, нужно рассчитать характеристику поискового алгоритма в терминах полнота/точность.

11. Построение рекомендующей системы изображений

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

12. Поиск изображений по содержанию

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

13. Система извлечения информации из изображений для маркетинговых исследований

Отделение фирмы, специализирующееся на разработке мобильных телефонов решило провести крупное маркетинговое исследование. Для разработки рекламной кампании маркетологи решили проанализировать, какие модели телефонов привлекают внимание тех или иных социальных групп. Было установлено, что наиболее существенной является информация о поле и возрасте покупателя, а так же о том, какие эмоции возникают у покупателей при первом взгляде на телефон (разочарование, удивление или отсутствие каких либо эмоций). Технический отдел разместил на витринах с телефонами скрытые видеокамеры, позволяющие фиксировать лица людей, которые обратили свое внимание на конкретную модель телефона. Перед Вами поставлена задача определить по 10 секундной видеозаписи пол и возраст потенциального покупателя, а также характер эмоций, вызываемый конкретной моделью телефона.

Ссылки

Личные инструменты