Como calcular os pesos dos critérios de Fisher?

12

Estou estudando reconhecimento de padrões e aprendizado de máquina e me deparei com a seguinte pergunta.

Considere um problema de classificação de duas classes com igual probabilidade de classe anterior

P(D1)=P(D2)=12

e a distribuição de instâncias em cada classe dada por

p(x|D1)=N([00],[2001]),

p(x|D2)=N([44],[1001]).

Como calcular os pesos dos critérios de Fisher?

Atualização 2: o peso calculado fornecido pelo meu livro é: .W=[4329]

Atualização 3: Como sugerido por @xeon, entendo que devo determinar a linha de projeção para o discriminante de Fisher.

Atualização 4: Seja W a direção da linha de projeção, o método discriminante linear de Fisher descobre que o melhor W é aquele para o qual a função de critério é maximizada. O desafio restante é como podemos obter numericamente o vetor W ?

Dr. Hoshang
fonte
Sua primeira distribuição é indefinida. Em particular, a segunda variável do par tem uma distribuição degenerada com variação 0, mas tem uma covariância positiva com a primeira variável, o que é impossível.
Owensmartin
@owensmartin você tem alguma idéia, como esses valores são calculados?
Dr. Hoshang
Qual é a definição do peso do critério Fisher?
Vladislavs Dovgalecs
Quero dizer que o discriminante linear de Fisher é dado pelo vetor w que maximiza ... é anotado em todo material como luthuli.cs.uiuc.edu/~daf/courses/Learning/Kernelpapers/… na p. 2. é okey @xeon?
Dr. Hoshang
Dica: qual será o limite entre as duas classes? Linear, polinomial, outra coisa?
Vladislavs Dovgalecs

Respostas:

11

Seguindo o artigo ao qual você vinculou (Mika et al., 1999) , precisamos encontrar que maximiza o chamado quociente generalizado de Rayleigh ,w

wSBwwSWw,

onde para médias e covariâncias C 1 , C 2 ,m1,m2C1,C2

SB=(m1m2)(m1m2),SW=C1+C2.

A solução pode ser encontrada resolvendo o problema generalizado de autovalores calculando primeiro os autovalores λ resolvendo det ( S B - λ S W ) = 0 e depois resolvendo o vetor próprio w . No seu caso, S B - λ S W = ( 16 - 3 λ 16 16 16 - 2 λ ) .

SBw=λSWw,
λ
det(SBλSW)=0
w
SBλSW=(163λ1616162λ).
O determinante dessa matriz 2x2 pode ser calculado manualmente.

O vetor próprio com o maior valor próprio maximiza o quociente de Rayleigh. Em vez de fazer os cálculos manualmente, resolvi o problema de autovalor generalizado no Python usando scipy.linalg.eige obtive que é diferente da solução encontrada em seu livro. Abaixo, plotei o hiperplano ideal do vetor de peso que encontrei (preto) e o hiperplano do vetor de peso encontrado em seu livro (vermelho).

w10.5547,w20.8321,

insira a descrição da imagem aqui

Lucas
fonte
1
Este exemplo é muito interessante. As duas linhas separam as duas classes, mas uma delas é "melhor" do ponto de vista da teoria da aprendizagem.
Vladislavs Dovgalecs
2
O critério Fisher está detalhado na seção 5-2-3 em books.google.com/…
nini
1
@ Lucas, talvez o resultado em questão seja próximo aos comentários xeon: "Talvez devêssemos relatar o vetor unitário w, já que o hiperplano é definido por direção, não por magnitude".
Nini
1
Oh !!! pergunta desafiadora, recomendo que todos vejam a página 2 em dml.ir/wp-content/uploads/2012/04/SPR-S12-M-Sol.pdf
user153695
1
@ Lucas Obrigado. você poderia adicionar outra imagem para W = [- 2/3 -2/3] e W = [- 4/3 -2/3] e W = [- 2 -3] com três cores diferentes para ver o limite? Obrigado. Eu concedo recompensa por uma boa resposta.
Nini
7

SOLUTION1:

Seguindo Duda et al. (Pattern CLassification), que tem uma solução alternativa para @lucas e, nesse caso, facilita muito a computação da solução manualmente. (Espero que esta solução alternativa ajude !! :))

Na LDA de duas classes, o objetivo é:

wTSBwwTSWw

SB=(m1m2)(m1m2)TSW=S1+S2S1,S2m1,m2

A solução desse quociente de raleigh generalizado é um probem de valor próprio de generalização.

SBw=λSWwSW1SBw=λw

SBm1m2wSW1(m1m2)

w

SW1(m1m2)=(S1+S2)1(m1m2)=([2001]+[1001])1([00][44])=([1/3001/2])([00][44])=[1.33332.0000][0.55470.8321]

Ref: Classificação de Padrões por Duda, Hart, Stork

SOLUTION2:

SBw=λSWw

determinant(SBλSW)SBw=λSWwλ1,λ2,...,λn, as roots of the polynomial. Now substitute λ=λi,i{1,2,..,n} and get the corresponding eigen vector as solution to the linear system of equations SBwi=λiSWwi. By doing this for each i you can get a set of vectors {wi}i=1n and it is a set of eigen vectors as solutions.

determinant(SBλSW)=[163λ1616162λ]=6λ280λ, So eigen values are roots to polynomial 6λ280λ.

So λ= 0 and 40/3 are the two solutions. For LDA, eigen vector corresponding to highest eigen value is the solution.

Solution to system of equation (SBλiSW)wi=0 and λi=40/3

which turns out to be [163λ1616162λ]wi[72484832]wi=0

Solution to the above system of equation is [0.55470.8321][0.55470.8321] which is same as previous solution.

Alternatively, we can say that [0.55470.8321] lies in the null space of [72484832].

For two class LDA, eigen vector with highest eigen value is the solution. In general, for C class LDA, the first C - 1 eigen vectors to highest C - 1 eigen values constitute the solution.

This video explains how to compute eigen vectors for simple eigen value problem. ( https://www.khanacademy.org/math/linear-algebra/alternate_bases/eigen_everything/v/linear-algebra-finding-eigenvectors-and-eigenspaces-example )

Following is an example. http://www.sosmath.com/matrix/eigen2/eigen2.html

Multi-class LDA: http://en.wikipedia.org/wiki/Linear_discriminant_analysis#Multiclass_LDA

Calculating Null Space of a matrix: https://www.khanacademy.org/math/linear-algebra/vectors_and_spaces/null_column_space/v/null-space-2-calculating-the-null-space-of-a-matrix

dksahuji
fonte
1
Nice answer, you means answer of book is wrong!! Okey?
Dr. Hoshang
I believe that this answer is correct and if your book defines SW and SB differently then see what you get with those definitions.
dksahuji
2
-1.33 is equal to -4/3 but the second element is differ. Maybe book report unit vector w? Isn't right? Thanks so much
Dr. Hoshang
2
please complete solution 2 to reach value of W to bounty it
nini
1
@Dr.Hoshang: The solution in your book is wrong. I have no idea why.
amoeba says Reinstate Monica