GATE DS&AI 2024 | Question: 12

Question

​​​​​​For any binary classification dataset, let $S_{B} \in \mathbb{R}^{d \times d}$ and $S_{W} \in \mathbb{R}^{d \times d}$ be the between-class and within-class scatter (covariance) matrices, respectively. The Fisher linear discriminant is defined by $u^{*} \in \mathbb{R}^{d}$, that maximizes

\[
J(u)=\frac{u^{T} S_{B} u}{u^{T} S_{W} u}
\]

If $\lambda=J\left(u^{*}\right), S_{W}$ is non-singular and $S_{B} \neq 0$, then $\left(u^{*}, \lambda\right)$ must satisfy which ONE of the following equations?

Note: $\mathbb{R}$ denotes the set of real numbers.

• A. $S_{W}^{-1} S_{B} u^{*}=\lambda u^{*}$
• B. $S_{W} u^{*}=\lambda S_{B} u^{*}$
• C. $S_{B} S_{W} u^{*}=\lambda u^{*}$
• D. $u^{* T} u^{*}=\lambda^{2}$

Answer 1

Answer is A.

$\textbf{Proof}:$

Here our objective function is:

  

 $$J(u)=\frac{u^TS_Bu}{u^TS_wu}$$

$\textbf{Method 1:}$

We maximize $J(u)$ by taking the derivative wrt $u$ and setting it to zero as:

$\frac{d}{du}J(u) = \frac{\frac{d}{du}(u^TS_Bu)u^TS_Wu - \frac{d}{du}(u^TS_Bu)u^TS_Wu}{(u^TS_W u)^2}$ 

$\frac{d}{du}J(u) =\frac{(2S_Bu)u^TS_wu -(2S_Wu)u^TS_Bu}{(u^TS_W u)^2} = 0$   

So,

$u^TS_wu(S_Bu)-u^TS_Bu(S_Wu) =0$

   

$\frac{u^TS_Wu(S_Bu)}{u^TS_Wu}-\frac{u^TS_Bu(S_Wu)}{u^TS_Wu} =0$  

$\Rightarrow S_Bu - \frac{u^TS_Bu(S_Wu)}{u^TS_Wu}=0$

Hence,

$S_Bu = \lambda S_wu$  

Where $\lambda = \frac{u^TS_Bu}{u^TS_Wu}$

Therefore,

$S_W^{-1}S_Bu=\lambda u$

So, at $u=u^*$

$S_W^{-1}S_Bu^*=\lambda u^*$

  

$\textbf{Method 2:}$ 

  

Here we can write the same problem as:

   

maximize $u^TS_Bu$ such that $u^TS_Wu=1$

  

So,

 Lagrangian Multiplier is:   

  

$L(u,\lambda) =u^TS_Bu - \lambda (u^TS_Wu -1)$

   

$\nabla L= 2S_Bu-2 \lambda S_W u = 0 $

  

Hence, $S_B u = \lambda S_W u$

 

Therefore, $S_W^{-1}S_B u = \lambda u$ 

where $u$ is the eigen vector of $S_W^{-1}S_B$