## Exercise 1 (10 points): Linear Discriminant Analysis [Pen and Paper]

Not every feature dimension is equally useful for classification. Usually, some are more important to distinguish between classes than others. To evaluate the different dimensions, we can use linear discriminant analysis (LDA) which constructs a new feature space where the axes are designed to discriminate the classes as much as possible. In addition, LDA also reduces the
dimensions of our feature space which saves computational costs and can help to overcome overfitting.

In this exercise, we look at a two-dimensional example of a two-class problem (with the classes 𝜔1 and 𝜔2) and try to understand the basic concepts behind LDA. The next assignment then focusses on a more realistic example where LDA is used as a preprocessing step in a classification problem. 

The general idea of LDA is to maximize the criterion function

\begin{equation} J(w) = \frac{\tilde{\mu}_1 - \tilde{\mu}_2}{\tilde{\sigma}_1^2 + \tilde{\sigma}_2^2}  = 
\frac{w^TS_Bw}{w^TS_Ww}\end{equation}

<br/>
$𝑤$ is the normalized vector representing the axes of the new feature space. $\tilde{\mu}_1, \tilde{\mu}_2$ and $\tilde{\sigma}_1^2, \tilde{\sigma}_2^2$ are the means and variances, respectively, of the two classes which are projected to the new feature space, i.e. projected on the vector $w$. Remember that an arbitrary point $x$ is projected on $w$ via<br/> <br/>
\begin{equation} x = w^Tx \end{equation}

<br/>
$\tilde{x}$ denotes the one-dimensional value relative to the new coordinate system spanned by $w$. To maximize $J(w)$, we need the between-class scatter matrix <br/> <br/>
\begin{equation} S_B = (\mu_1 - \mu_2)(\mu_1 - \mu_2)^T \end{equation}

<br/>
where $\mu_i = (\mu_{ix}, \mu_{iy}$ denotes the mean vectors of the two classes (column vectors). For our dataset, they are defined as (the complete dataset was centred around the origin)
$$ \mu_1 = 
\begin{pmatrix}
-1.7\\
-1.20\\
\end{pmatrix}
\hspace{0.5cm}and\hspace{0.5cm}
\mu_2 = 
\begin{pmatrix}
1.17\\
1.20\\
\end{pmatrix}
$$

Finally, for the within-scatter matrix 𝑆𝑊 we use the combined covariance matrix which simply sums up the covariance matrices of the two classes: $S_W = \sum = {\sum}_1 + {\sum}_2$.
1. We first want to take a look at the between-class scatter matrix $S_B$.
    
    a) Figure 2 shows the dataset we are using throughout this exercise and labels the horizontal and vertical distances between the mean vectors. <br/><br/> \begin{equation} dx = (\mu_{1x} − \mu_{2x}) = −2.33 \hspace{0.5cm}and\hspace{0.5cm} dy = (\mu_{1y} − \mu_{2y}) = −2.40\end{equation}<br/>Calculate all values of the matrix $S_B$ (Equation 3) without using the definitions of Equation 4 (but you can use it to check your result). Hint: start by deriving the general form of $S_B$ and then plug in $dx$ and $dy$.
    
    b) Building upon your previous results, what is the rank of $𝑆_𝐵$

2. Figure 3, Figure 4 and Figure 5 show the situation of the weight vectors $w_1$, $w_2$ and $w_3$, respectively. The vector $w_1$ of Figure 3 maximizes the distance between the projected means, $w_2 $ of Figure 4 minimizes it and $w_3$ of Figure 5 finally maximizes the criterion function of Equation 1. In the next steps, we want to calculate the corresponding missing values of Table 1.

    a) Start by mapping each line of Table 1 to the corresponding figure based on the values of the projected variances $\omega_1^2 \hspace{0.5cm}and\hspace{0.5cm} \omega_2^2$.

    b) Calculate the squared differences between the projected means $(\tilde{\mu}_1 - \tilde{\mu}_2)^2$. Hint: you can name one value directly, another can be calculated based on the definitions of Equation 4 and for yet another you need to project the mean values $\mu_1$ and $\mu_2$ first onto the new axis $w$ (cf. Equation 2).

    c) Find the missing vectors $w_1 $and $w_2$ (normalized).

    d) Finally, we arrive at the point where we can actually compute the values of the criterion function $J(w)$ of Equation 1. Calculate the missing values in the last column of Table 1. If done correctly, Figure 5 should correspond to the line where $J(w)$ is maximal.


3. Explain why it is not enough to maximize only the squared distance between the projected means when we want to achieve a good class discrimination (Figure 3 vs. Figure 5).

4. We can use the result of LDA to construct a new coordinate system with good classdiscrimination capabilities. To achieve this, we need to solve the regular eigenvalue problem
\begin{equation}S_W^-1 S_Bw = \lambda w. \end{equation}
<br/>
Asking a computer system to calculate the eigenvalues $\lambda_i$ and corresponding eigenvectors $\mu_i$ for the matrix $S_W^{-1}S_B$ rewards us with <br/> <br/> \begin{equation}\lambda_1 = 14.15, \lambda_2 = 0 \hspace{0.5cm}and\hspace{0.5cm} \
\mu_1 = 
\begin{pmatrix}
-0.97\\
-0.25\\
\end{pmatrix},
\mu_2 = 
\begin{pmatrix}
-0.72\\
0.70\\
\end{pmatrix}
\end{equation}
<br/>
As you can see, the result is already ascendingly sorted by the magnitude of the eigenvalues and the eigenvectors are normalized, i.e. $‖u_i‖ = 1$. Also, note that $u_1 = w_3$ which is not a coincidence since the vector in Figure 5 was chosen to maximize Equation 1.

    a) Why is $\lambda_2 = 0$? Is this only related to the specific dataset here or can you maybe infer a general rule? Hint: argue with what you found out about the rank of $𝑆_𝐵$ previously.
    
    b) We can use the first eigenvector and Equation 2 to project every data point onto the line of the new coordinate system. The result of this process can be seen graphically in Figure 1. Calculate for the two points<br/> <br/> $$ x_1 = 
\begin{pmatrix}
-0.42\\
-0.38\\
\end{pmatrix} \in \omega_1
\hspace{0.5cm}and\hspace{0.5cm}
x_2 = 
\begin{pmatrix}
1.88\\
1.08\\
\end{pmatrix} \in \omega_2
$$ <br/> the projection onto $u_1$ numerically, i.e. the values $\tilde{x}_1$ and $\tilde{x}_2$.

    c) Based on the definition of the first eigenvector $u_1$ and the calculation you just performed, which of the original features, i.e. the axes 𝑥 and 𝑦, is more important for class discrimination?

    d) Which threshold $w_0 \in \mathbb{R}$ would you choose to classify new data points $x_i$ based on their projected value $\tilde{x}_i$?

35d43a72b308fd8bbe2afa797576bfd622ae7d89
ipynb
Jupyter Notebook
06_linear_discrimant_analysis/linear_discrimant_analysis.ipynb
jhinga-la-la/pattern-recognition-course
7ad4f70b2c427f3c37f59f47768b90371873823c
Apache-2.0
06_linear_discrimant_analysis/linear_discrimant_analysis.ipynb
jhinga-la-la/pattern-recognition-course
7ad4f70b2c427f3c37f59f47768b90371873823c
Apache-2.0
06_linear_discrimant_analysis/linear_discrimant_analysis.ipynb
jhinga-la-la/pattern-recognition-course
7ad4f70b2c427f3c37f59f47768b90371873823c
Apache-2.0
Qwen/Qwen-72B
1. YES
2. YES