МИРЭА / Методичка_2010 / Методичка_2010

Дискриминантный анализ. Линейный дискриминант Фишера. Персептронная функция критерия. Линейный дискриминантный анализ (lda,дискриминант Фишера)

Сейчас мы покажем, что при очень простых (и потому, как правило, не соответствующих действительности) предположениях о пространстве совместных распределений P (см. раздел 1.1.3) инженерное решение (46), как загнать образ линейного оператора в симплекс, становится простым следствием теории, а обучение распознавателя проводится не итеративно, а по явным формулам. Подчеркиваем: для этого делаются простые, но, как правило, неверные предположения.

А именно, предположим, что для каждого из q классов (для j-го) распределение векторов признаков этого класса - гауссово с центром _j  X и одинаковой для всех классов матрицей ковариации . Вероятность j-го класса обозначим через _j и будем считать, что _j > 0 (а иначе j-й класс можно выкинуть). То есть⁷

p_j(x)=p(xy=j)=(2)^^[ d/2]^^[ 1/2] e^^[ 1/2]^^1(x^_j^,x^_j⁾,

p(x,y)=_yp_y(x)=_y (2)^^[ d/2]^^[ 1/2] e^^[ 1/2]^^1(x^_y^,x^_y⁾

(52)и

p(x)=

q  j=1

p(x,j)=

q  j=1

_j (2)^^[ d/2]^^[ 1/2] e^^[ 1/2]^^1(x^_j^,x^_j⁾.

Тогда условные вероятности P_y(x)=P{yx}, которые и должен оценивать классификатор, равны

P_y(x)

p(x,y)

p(x)

_y e^^[ 1/2]^^1(x^_y^,x^_y⁾

q  j=1

_j e^^[ 1/2]^^1(x^_j^,x^_j⁾

(53)

e^^1(x,^_y⁾^^[ 1/2]^¹⁽^_y^,^_y^)+ln(^_y⁾

q  j=1

e^^1(x,^_j⁾^^[ 1/2]^¹⁽^_j^,^_j^)+ln(^_j⁾

то есть в точности имеют вид (46).

Обучение классификатора состоит в оценке его параметров _j, _j при 1  j  q и  по имеющемуся обучающему набору T. Это можно сделать методом наибольшего правдоподобия, т.е. решением задачи

ln(p(T))=

N  i=1

ln(p(x_i,y_i)) 

min ,,

где плотности вероятностей p(x_i,y_i) вычисляются по формуле (52). Поскольку сумма вероятностей _j всех классов равна 1, нужно написать лагранжиан

L(T,,,,)

ln(p(T))+(

q  j=1

_j1)

(54)

^1(x_i_yi,x_i_yi)  ln 1 ln(2)1  ln(_yi)  d 

N  i=1

+(

q  j=1

_j1)

и приравнять нулю его производные по всем переменным , _j, _j и  (точнее, удобно дифференцировать не по элементам матрицы , а по элементам матрицы ^¹). Получающаяся система уравнений⁸

L



q  j=1

_j1

L

_j



#{iy_i=j}

_j

+ 

L

_j



 iy_i=j

^¹(x_i  _j)

L

^¹_kl



^kl +

N  i=1

(x_i^k_yi^k)(x_i^l_yi^l)

легко решается:



_j

#{iy_i=j}

(55)

_j

 iy_i=j

x_i

#{iy_i=j}

(56)

^kl

N  i=1

(x_i^k_yi^k)(x_i^l_yi^l)

(57)и получаются традиционные в статистике оценки вероятности как частоты, математического ожидания как центра тяжести и ковариации.

Плотность совместного распределения (52) оценена, а значит обучен байесовский классификатор (раздел 1.2.3), самый лучший из возможных. При чем тут линейный дискриминантный анализ?

Дискриминантами называются функции, различающие классы, то есть такие функции _ij(x), что неравенство p_i(x) > p_j(x) (вектор x скорее принадлежит i-му классу, чем j-му) равносильно неравенству _ij(x) > 0. В частности, для любого классификатора, оценивающего условные плотности вероятностей p_j(x) или совместные плотности вероятностей p(x,j), дискриминантами являются попарные разности p_i(x)p_j(x) или p(x,i)p(x,j). Для описываемого классификатора более удобными дискриминантами, причем линейными, являются функции

p_i(x)

p_j(x)

_i

_j



( ^¹(x_i,x_i)^¹(x_j,x_j) )

_i

_j



( ^¹(_i,_i)^¹(_j,_j) ) +^¹(x,_i_j)

_i

_j

+^¹(x

_i+_j

,_i_j).

(58)

При  = I_d и _i=_j множество уровня 0 дискриминанта (58) - это гиперплоскость, проходящая через середину отрезка [_i,_j] перпендикулярно ему. При _i  _j гиперплоскость смещена относительно середины, а при   I_d она не перпендикулярна, а ее направление сопряжено направлению отрезка [_i,_j] относительно квадратичной формы ^¹ (см. рис. 3). Еще одно полезное геометрическое соображение: для классификации любого d-мерного вектора признаков достаточно знать его проекцию (при  = I_d - ортогональную, в общем случае - вдоль сопряженной относительно ^¹ плоскости) на не более чем (q1)-мерную линейную оболочку точек _j.

Рис.3: Разделяющие плоскости дискриминанта Фишера (58) для двух классов и разных соотношений между вероятностями _j

Если распределения векторов признаков для разных классов считать гауссовыми, но не с общей матрицей ковариации, а с независимыми, то распознаватель тоже можно обучить методом наибольшего правдоподобия. При этом оценки (55) и (56) остаются неизменными, а оценка (57) естественно распадается на q независимых оценок

_j^kl=

 iy_i=j

(x_i_yi)^k(x_i_yi)^l

#{iy_i=j}

Но аналог дискриминанта (58) будет уже не линейным, а квадратичным.

Конструкция дискриминанта (58), оценки (55,56,57) и геометрическая интерпретация разделяющих гиперплоскостей идут от работы Р.Фишера 1936 года [Fis36]. Линейный (и квадратичный тоже) дискриминантный анализ был полезен в докомпьютерные времена из-за явных формул для ответа и наглядной геометрической интерпретации. Более общий метод из раздела 2.2.1 тоже дает линейные дискриминанты, не требует никаких сомнительных предположений о распределении векторов признаков каждого класса и на практике приводит к лучшему распознаванию.

Содержание