12
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – owensmartin Apr 1 '15 at 18:39
  • $\begingroup$ @owensmartin do u have any idea, how these values calculated? $\endgroup$ – Dr. Hoshang Apr 3 '15 at 7:08
  • $\begingroup$ What is the definition of the Fisher criterion weight? $\endgroup$ – Vladislavs Dovgalecs Apr 3 '15 at 7:16
  • $\begingroup$ 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 ? $\endgroup$ – Dr. Hoshang Apr 3 '15 at 7:27
  • $\begingroup$ Hint: What will be the boundary between the two classes? Linear, polynomial, something else? $\endgroup$ – Vladislavs Dovgalecs Apr 3 '15 at 7:29
11
+25
$\begingroup$

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$enter image description here

$\endgroup$
  • 1
    $\begingroup$ This example is very interesting. The both lines separate the two classes but one of them is "better" from learning theory point of view. $\endgroup$ – Vladislavs Dovgalecs Apr 3 '15 at 22:49
  • 2
    $\begingroup$ Fisher Criterion is detailed at section 5-2-3 on books.google.com/… $\endgroup$ – nini Apr 4 '15 at 12:42
  • 1
    $\begingroup$ @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 ? $\endgroup$ – nini Apr 4 '15 at 18:09
  • 1
    $\begingroup$ Oh !!! challenging question, I recommend all to see page 2 on dml.ir/wp-content/uploads/2012/04/SPR-S12-M-Sol.pdf $\endgroup$ – user153695 Apr 4 '15 at 18:44
  • 1
    $\begingroup$ @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. $\endgroup$ – nini Apr 5 '15 at 18:41
7
$\begingroup$

$\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

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

$\endgroup$
  • 1
    $\begingroup$ Nice answer, you means answer of book is wrong!! Okey? $\endgroup$ – Dr. Hoshang Apr 5 '15 at 7:28
  • $\begingroup$ 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. $\endgroup$ – dksahuji Apr 5 '15 at 7:56
  • 2
    $\begingroup$ -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 $\endgroup$ – Dr. Hoshang Apr 5 '15 at 8:23
  • 2
    $\begingroup$ please complete solution 2 to reach value of W to bounty it $\endgroup$ – nini Apr 5 '15 at 8:34
  • 1
    $\begingroup$ @Dr.Hoshang: The solution in your book is wrong. I have no idea why. $\endgroup$ – amoeba says Reinstate Monica Apr 5 '15 at 8:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.