# How to calculate Fisher criterion weights?

I am studying pattern recognition and machine learning, and I ran into the following question.

Consider a two-class classification problem with equal prior class probability $$P(D_1)=P(D_2)= \frac{1}{2}$$

and the distribution of instances in each classes given by

$$p(x|D_1)= {\cal N} \left( \begin{bmatrix} 0 \\0 \end{bmatrix}, \begin{bmatrix} 2 & 0 \\ 0 & 1 \end{bmatrix} \right),$$

$$p(x|D_2)= {\cal N} \left( \begin{bmatrix} 4 \\ 4 \end{bmatrix}, \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} \right).$$

How to calculate Fisher criterion weights?

Update 2: The calculated weight provided by my book is: $W=\begin{bmatrix} \frac{-4}{3} \\ \frac{-2}{9} \end{bmatrix}$.

Update 3: As hinted by @xeon, I understand that I should determine the projection line for the Fisher’s discriminant.

Update 4: Let $W$ be the direction of the projection line, then the Fisher linear discriminant method finds that the best $W$ is the one for which the criterion function is maximized. The remaining challenge is how can we get numerically $W$ vector?

• Your first distribution is undefined. In particular the second variate of the pair has a degenerate distribution with 0 variance, but does have a positive covariance with the first variate, which is impossible. – owensmartin Apr 1 '15 at 18:39
• @owensmartin do u have any idea, how these values calculated? – Dr. Hoshang Apr 3 '15 at 7:08
• What is the definition of the Fisher criterion weight? – Vladislavs Dovgalecs Apr 3 '15 at 7:16
• I means Fisher’s linear discriminant is given by the vector w which maximizes... it's noted on every material like as luthuli.cs.uiuc.edu/~daf/courses/Learning/Kernelpapers/… on p. 2. is it okey @xeon ? – Dr. Hoshang Apr 3 '15 at 7:27
• Hint: What will be the boundary between the two classes? Linear, polynomial, something else? – Vladislavs Dovgalecs Apr 3 '15 at 7:29

## 2 Answers

Following the paper you linked to (Mika et al., 1999), we have to find the $\mathbf{w}$ which maximizes the so called generalized Rayleigh quotient,

$$\frac{\mathbf{w}^\top \mathbf{S}_B \mathbf{w}}{\mathbf{w}^\top \mathbf{S}_W \mathbf{w}},$$

where for means $\mathbf{m}_1, \mathbf{m}_2$ and covariances $\mathbf{C}_1, \mathbf{C}_2$,

\begin{align} \mathbf{S}_B &= (\mathbf{m}_1 - \mathbf{m}_2)(\mathbf{m}_1 - \mathbf{m}_2)^\top, & \mathbf{S}_W &= \mathbf{C}_1 + \mathbf{C}_2. \end{align}

The solution can be found by solving the generalized eigenvalue problem \begin{align} \mathbf{S}_B\mathbf{w} = \lambda \mathbf{S}_W\mathbf{w}, \end{align} by first computing the eigenvalues $\lambda$ by solving \begin{align} \det(\mathbf{S}_B - \lambda \mathbf{S}_W) = 0 \end{align} and then solving for the eigenvector $\mathbf{w}$. In your case, $$\mathbf{S}_B - \lambda \mathbf{S}_W = \begin{pmatrix}16 - 3\lambda & 16 \\ 16 & 16 - 2\lambda\end{pmatrix}.$$ The determinant of this 2x2 matrix can be computed by hand.

The eigenvector with the largest eigenvalue maximizes the Rayleigh quotient. Instead of doing the calculations by hand, I solved the generalized eigenvalue problem in Python using scipy.linalg.eig and got $$w_1 \approx 0.5547, w_2 \approx 0.8321,$$ which is different from the solution you found in your book. Below I plotted the optimal hyperplane of the weight vector I found (black) and the hyerplane of the weight vector found in your book (red).

$\hskip1in$

• This example is very interesting. The both lines separate the two classes but one of them is "better" from learning theory point of view. – Vladislavs Dovgalecs Apr 3 '15 at 22:49
• Fisher Criterion is detailed at section 5-2-3 on books.google.com/… – nini Apr 4 '15 at 12:42
• @Lucas maybe the result in question is close to xeon comments, "Perhaps we should report unit vector w since the hyperplane is defined by direction, not magnitude. " isn't it ? – nini Apr 4 '15 at 18:09
• Oh !!! challenging question, I recommend all to see page 2 on dml.ir/wp-content/uploads/2012/04/SPR-S12-M-Sol.pdf – user153695 Apr 4 '15 at 18:44
• @Lucas Thanks. would you please add another picture for W=[-2/3 -2/3] and W=[-4/3 -2/3] and W=[-2 -3] with three different color to see the boundary? Thanks. I set bounty to you for nice answer. – nini Apr 5 '15 at 18:41

$\mathbf{SOLUTION 1:}$

Following Duda et al. (Pattern CLassification) which has an alternate solution to @lucas and in this case gives very easy to compute solution by hand. (Hope this alternate solution helps!! :))

In two class LDA the objective is:

$\frac{w^TS_Bw}{w^TS_Ww}$ which just means that increase the between class variance and decrease the within class variance.

where $S_B = (m_1-m_2)(m_1-m_2)^T$ and $S_W = S_1 + S_2$, here $S_1,S_2$ are covariance matrix and $m_1,m_2$ are means of class 1 and 2 respectively.

The solution of this generalized raleigh quotient is a generalized eigen value probem.

$S_Bw = \lambda S_Ww \rightarrow {S_W}^{-1}S_Bw = \lambda w$

The above formulation has a closed form solution. $S_B$ is a rank 1 matrix with basis $m_1-m_2$ so $w \propto {S_W}^{-1}(m1-m2)$ which can be normlizd to get the answer.

I just calculated the $w$ and got [0.5547;0.8321].

${S_W}^{-1}(m1-m2) = {(S_1 + S_2)}^{-1}(m1 - m2) = {(\begin{bmatrix} 2 & 0 \\ 0 & 1 \end{bmatrix} + \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix})}^{-1}(\begin{bmatrix} 0 \\ 0 \end{bmatrix} - \begin{bmatrix} 4 \\ 4 \end{bmatrix} ) ={(\begin{bmatrix} 1/3 & 0 \\ 0 & 1/2 \end{bmatrix})}(\begin{bmatrix} 0 \\ 0 \end{bmatrix} - \begin{bmatrix} 4 \\ 4 \end{bmatrix} ) = \begin{bmatrix} -1.3333 \\ -2.0000 \end{bmatrix} \propto \begin{bmatrix} 0.5547 \\ 0.8321 \end{bmatrix}$

Ref: Pattern Classification by Duda, Hart, Stork

$\mathbf{SOLUTION 2:}$

Alternatively, it can be solved by finding eigen vector to the generalized eigen value problem. $S_Bw = \lambda S_Ww$

A polynomial in lambda can be formed by $determinant(S_B - \lambda S_W)$ and the solutions to that polynomial will be the eigen value for $S_Bw = \lambda S_Ww$. Now lets say you got a set of eigen values $\lambda_1,\lambda_2, ..., \lambda_n,$ as roots of the polynomial. Now substitute $\lambda = \lambda_i, i \in \{1,2,..,n\}$ and get the corresponding eigen vector as solution to the linear system of equations $S_Bw_i = \lambda_i S_Ww_i$. By doing this for each i you can get a set of vectors $\{w_i\}_{i=1}^{n}$ and it is a set of eigen vectors as solutions.

$determinant(S_B - \lambda S_W) = \begin{bmatrix} 16 - 3\lambda & 16 \\ 16 & 16 - 2\lambda \end{bmatrix} =6\lambda^2 - 80\lambda$, So eigen values are roots to polynomial $6\lambda^2 - 80\lambda$.

So $\lambda=$ 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 $(S_B - \lambda_i S_W)w_i = 0$ and $\lambda_i = 40/3$

which turns out to be $\begin{bmatrix} 16 - 3\lambda & 16 \\ 16 & 16 - 2\lambda \end{bmatrix}w_i \propto \begin{bmatrix} -72 & 48 \\ 48 & -32 \end{bmatrix}w_i = 0$

Solution to the above system of equation is $\begin{bmatrix} -0.5547 \\ -0.8321 \end{bmatrix} \propto \begin{bmatrix} 0.5547 \\ 0.8321 \end{bmatrix}$ which is same as previous solution.

Alternatively, we can say that $\begin{bmatrix} 0.5547 \\ 0.8321 \end{bmatrix}$ lies in the null space of $\begin{bmatrix} -72 & 48 \\ 48 & -32 \end{bmatrix}$.

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

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

• Nice answer, you means answer of book is wrong!! Okey? – Dr. Hoshang Apr 5 '15 at 7:28
• I believe that this answer is correct and if your book defines $S_W$ and $S_B$ differently then see what you get with those definitions. – dksahuji Apr 5 '15 at 7:56
• -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 Apr 5 '15 at 8:23
• please complete solution 2 to reach value of W to bounty it – nini Apr 5 '15 at 8:34
• @Dr.Hoshang: The solution in your book is wrong. I have no idea why. – amoeba says Reinstate Monica Apr 5 '15 at 8:40