Дискриминантный анализ. Линейный дискриминант Фишера. Персептронная функция критерия. Линейный дискриминантный анализ (lda,дискриминант Фишера)
Сейчас мы покажем, что при очень простых (и потому, как правило, не соответствующих действительности) предположениях о пространстве совместных распределений P (см. раздел 1.1.3) инженерное решение (46), как загнать образ линейного оператора в симплекс, становится простым следствием теории, а обучение распознавателя проводится не итеративно, а по явным формулам. Подчеркиваем: для этого делаются простые, но, как правило, неверные предположения.
А именно, предположим, что для каждого из q классов (для j-го) распределение векторов признаков этого класса - гауссово с центром j X и одинаковой для всех классов матрицей ковариации . Вероятность j-го класса обозначим через j и будем считать, что j > 0 (а иначе j-й класс можно выкинуть). То есть7
|
p(x,y)=ypy(x)=y (2)[ d/2][ 1/2] e[ 1/2]1(xy,xy)
(52)и
|
Тогда условные вероятности Py(x)=P{yx}, которые и должен оценивать классификатор, равны
|
|
|
|
| (53) | |||||||||
|
|
|
|
|
|
то есть в точности имеют вид (46).
Обучение классификатора состоит в оценке его параметров j, j при 1 j q и по имеющемуся обучающему набору T. Это можно сделать методом наибольшего правдоподобия, т.е. решением задачи
|
где плотности вероятностей p(xi,yi) вычисляются по формуле (52). Поскольку сумма вероятностей j всех классов равна 1, нужно написать лагранжиан
|
| = |
|
|
| ||||||
---|---|---|---|---|---|---|---|---|---|---|---|
|
|
|
|
|
| ||||||
|
|
|
|
|
|
ln(p(T))+( | q j=1 | j1) |
(54)
|
= |
1(xiyi,xiyi) ln 1 ln(2)1 ln(yi) d
2
2
2 |
N i=1
|
|
+( | q j=1 | j1) |
и приравнять нулю его производные по всем переменным , j, j и (точнее, удобно дифференцировать не по элементам матрицы , а по элементам матрицы 1). Получающаяся система уравнений8
|
|
|
|
| |||||||||||
|
|
|
|
| |||||||||||
|
|
|
|
| |||||||||||
|
|
|
|
| |||||||||||
|
|
|
|
|
легко решается:
|
|
|
|
|
| |||||
|
|
|
|
| (55) | |||||
| j |
|
|
|
| |||||
|
|
|
|
|
|
= |
|
#{iyi=j} |
|
(56)
kl |
= |
|
N | , |
(57)и получаются традиционные в статистике оценки вероятности как частоты, математического ожидания как центра тяжести и ковариации.
Плотность совместного распределения (52) оценена, а значит обучен байесовский классификатор (раздел 1.2.3), самый лучший из возможных. При чем тут линейный дискриминантный анализ?
Дискриминантами называются функции, различающие классы, то есть такие функции ij(x), что неравенство pi(x) > pj(x) (вектор x скорее принадлежит i-му классу, чем j-му) равносильно неравенству ij(x) > 0. В частности, для любого классификатора, оценивающего условные плотности вероятностей pj(x) или совместные плотности вероятностей p(x,j), дискриминантами являются попарные разности pi(x)pj(x) или p(x,i)p(x,j). Для описываемого классификатора более удобными дискриминантами, причем линейными, являются функции
|
|
|
|
|
| |||||||||
|
|
|
|
|
| |||||||||
|
|
|
|
| (58) |
При = Id и i=j множество уровня 0 дискриминанта (58) - это гиперплоскость, проходящая через середину отрезка [i,j] перпендикулярно ему. При i j гиперплоскость смещена относительно середины, а при Id она не перпендикулярна, а ее направление сопряжено направлению отрезка [i,j] относительно квадратичной формы 1 (см. рис. 3). Еще одно полезное геометрическое соображение: для классификации любого d-мерного вектора признаков достаточно знать его проекцию (при = Id - ортогональную, в общем случае - вдоль сопряженной относительно 1 плоскости) на не более чем (q1)-мерную линейную оболочку точек j.
Рис.3: Разделяющие плоскости дискриминанта Фишера (58) для двух классов и разных соотношений между вероятностями j
Если распределения векторов признаков для разных классов считать гауссовыми, но не с общей матрицей ковариации, а с независимыми, то распознаватель тоже можно обучить методом наибольшего правдоподобия. При этом оценки (55) и (56) остаются неизменными, а оценка (57) естественно распадается на q независимых оценок
|
Но аналог дискриминанта (58) будет уже не линейным, а квадратичным.
Конструкция дискриминанта (58), оценки (55,56,57) и геометрическая интерпретация разделяющих гиперплоскостей идут от работы Р.Фишера 1936 года [Fis36]. Линейный (и квадратичный тоже) дискриминантный анализ был полезен в докомпьютерные времена из-за явных формул для ответа и наглядной геометрической интерпретации. Более общий метод из раздела 2.2.1 тоже дает линейные дискриминанты, не требует никаких сомнительных предположений о распределении векторов признаков каждого класса и на практике приводит к лучшему распознаванию.
- «Обработка изображений и распознавание образов» Визильтер Юрий Валентинович Методическое пособие-2010
- Раздел 2. Распознавание образов. 165
- 1.1. Задачи и приложения машинного зрения. Примеры практических приложений.
- Уровни и методы машинного зрения
- Растровое изображение Изображение как двумерный массив данных
- Алгебраические операции над изображениями
- Физическая природа изображений
- Изображения различных диапазонов длин волн
- Изображения различной физической природы
- Тип пикселя
- Возможности и особенности системыPisoft
- Базовые средства просмотра и анализа изображений и видеопоследовательностей
- Алгебра изображений
- Геометрические преобразования изображений
- Устройства оцифровки и ввода изображений
- Линейки и матрицы, сканеры и камеры
- Геометрия изображения
- Цифровые и аналоговые устройства
- Пространственное разрешение
- Программное обеспечение
- Обработка цветных изображений
- Цветовая модельRgb
- Цветовая модель hsv
- Цветовая модель yuv
- Цветовая сегментация изображения
- Гистограмма и гистограммная обработка изображений
- Профиль вдоль линии и анализ профиля
- Проекция и анализ проекции
- Бинаризация полутоновых изображений
- Сегментация многомодальных изображений
- Выделение и описание областей
- Выделение связных областей на бинарных изображениях
- 1. Отслеживающие алгоритмы на примере алгоритма обхода контура.
- 2. Сканируюющие алгоритмы.
- 1.3. Фильтрация. Выделение объектов при помощи фильтров
- Оконная фильтрация изображений в пространственной области
- Фильтрация бинарных изображений Модель шума «соль и перец»
- Структура оконного фильтра
- Логическая фильтрация помех
- Бинарная медианная фильтрация
- Бинарная ранговая фильтрация
- Взвешенные ранговые фильтры
- Анизотропная фильтрация
- Расширение-сжатие (простая морфология)
- Стирание бахромы
- Нелинейная фильтрация полутоновых изображений
- Ранговая оконная фильтрация
- Минимаксная фильтрация
- Задача выделения объектов интереса
- Бинарные фильтры для выделения объектов
- Метод нормализации фона
- Скользящее среднее в окне
- Гауссовская фильтрация
- Преобразование Фурье. Линейная фильтрация в частотной области
- Преобразование Фурье
- Комплексное представление преобразования Фурье
- Быстрое преобразование Фурье
- Двумерное преобразование Фурье
- Свертка с использованием преобразования Фурье
- Фильтрация изображений в частотной области
- Вейвлет-анализ
- Пирамида изображений
- Вейвлет-преобразование
- Операторы вычисления производных
- Операторы вычисления векторов градиентов
- Операторы Марра и Лапласа
- Постобработка контурного изображения Локализация края
- Утончение контура
- Сегментация полутоновых изображений
- Пороговая и мультипороговая сегментация
- Методы слияния, разбиения и слияния/разбиения областей
- Способы описания выделенных областей
- Текстурные признаки
- 1.6.Морфологические методы анализа сцен (по ю.П. Пытьеву) Методы обнаружения объектов, заданных эталонами
- Согласованная фильтрация.
- Корреляционное обнаружение.
- Морфологический подход ю.П. Пытьева.
- Форма изображения как инвариант преобразований изображений, отвечающих вариациям условий регистрации
- Сравнение изображений по форме
- Выделение отличий изображений по форме
- Обнаружение объекта по его изображению и оценка его координат
- *Морфология на базе кусочно-линейной интерполяции
- Преобразование Хафа для поиска прямых
- *Различные способы параметризации прямых
- Преобразование Хафа для поиска окружностей
- Анализ аккумулятора при поиске геометрических примитивов
- Обобщенное преобразование Хафа
- *Специализированная процедура голосования для поиска эллипсов
- *Рекуррентное преобразование Хафа в скользящем окне
- 1.8.Математическая морфология (по ж. Серра)
- Морфологические операции на бинарных изображениях
- Морфологические операции на полутоновых изображениях
- Морфологическое выделение «черт» и объектов
- Морфологический спектр
- Морфологические скелеты. Непрерывная бинарная морфология Непрерывная бинарная морфология
- Непрерывное гранично-скелетное представление изображения
- Обработка и использование скелета
- *Обобщенные скелетные представления бинарных фигур
- Алгоритмы утончения дискретного бинарного изображения
- *Регуляризация скелетов
- Типы нерегулярностей скелета
- Устранение нерегулярностей
- Регуляризация скелета по Тихонову
- *Селективные морфологии
- 1.9. Анализ движения. Выделение движущихся объектов. Разность кадров. Вычитание фона. Анализ оптических потоков. Слежение за движущимися объектами. Корреляционное слежение.
- Обучение с учителем. Детерминированные методы, основанные на «близости». Линейные решающие правила. Метод построения эталонов. Метод ближайшего соседа. Методkближайших соседей.
- Линейные решающие правила
- Метод построения эталонов
- Методы ближайших соседей
- Параметрические и непараметрические методы
- Дискриминантные и моделирующие методы обучения
- Способность распознавателя к обобщению. Регуляризация.
- Байесовская теория решений. Случай двух классов. Классификаторы, разделяющие функции и поверхности решений. Вероятности ошибок. Разделяющие функции для случая нормальной плотности.
- Дискриминантный анализ. Линейный дискриминант Фишера. Персептронная функция критерия. Линейный дискриминантный анализ (lda,дискриминант Фишера)
- Персептрон Розенблатта
- Анализ свидетельств
- Байесовское объединение свидетельств
- Структурное распознавание
- Автоматизированное конструирование алгоритмов обнаружения объектов на основе преобразований модельных описаний объектов.
- Нейросетевое распознавание
- Нейронные сети ассоциативной памяти. Сети Хопфилда.
- Многослойные персептроны. Оптимизационное обучение. Метод обратного распространения ошибки.
- Многослойные персептроны. Правило Хебба.
- *Связь с байесовским распознаванием
- Сети встречного распространения. Самоорганизующиеся сети.