## Exercise 1 (3 points): Principal Component Analysis [Python]


In this exercise, we cover probably one of the most popular data analysis techniques: principal component analysis (PCA). It is used in many applications and is often part of the pre-processing steps. With its help, we can find new axes which are designed to reflect the variation present in the data. What is more, we can represent each data point relative to these new axes and when we choose fewer axes we effectively project our data to a lower-dimensional projection space. This way, PCA can also be used as a dimensionality reduction technique where we keep only the dimensions which explain most of the variance. However, this specific aspect is postponed until Exercise 3.


There are far too many applications of PCA to be covered in a single exercise and you will probably encounter some of them in other lectures anyway. However, we still want to look at an example to understand the basics.


Suppose you have captured an image of a brick as shown in Figure 1 (a). Additionally, you have already extracted a mask which discriminates the background from the brick. The file shapeData.pickle is attached to this exercise and contains a matrix of size 6752 × 2 which stores a list of all non-zero positions of this mask. We are going to apply PCA to this data and will see what we can do with it. For the test script, please pay also attention to Table 1.


1. Load the data points stored in the file shapeData.pickle and plot the result. Hint: set an equal axes scaling so that the mask of the brick does not look distorted

2. Centre the data so that it has zero mean, i.e. when $X \in \mathbb{R}^{nx2}$ denotes our data matrix, calculate
\begin{equation} X =  \tilde{X} - (\mu_1 \hspace{0.3cm} \mu_2)\end{equation}
where $\mu_i$ denotes the mean of the 𝑖-th column of $\tilde{X}$

3. Compute the covariance matrix
\begin{equation}C = \frac{1}{n-1}X^TX \end{equation}

4. We can now calculate the eigensystem, i.e. the principal components.
    
    a) Compute the eigenvalues and corresponding eigenvectors of $C$. You can use the $np.linalg.eig$ function for this task. But make sure (like in one of the previous exercises) that the result is sorted descendingly by the eigenvalues.

    b) The eigenvalue $\lambda_i$ corresponds to the variance along the new axis $u_i$ (which is defined by the respective eigenvector). Calculate the explained variance of each axis (in percentage terms).

5. The eigensystem $U = (u_1 \hspace{0.3cm} u_2)$ defines its own feature space and we can describe our points relative to the new axes. Project each data point to the new eigensystem and plot the result. Before you do so, think about what you would expect the shape to change to and then check if the result matches with your expectation.

## Exercise 2 (4 points): Singular Value Decomposition

Singular value decomposition (SVD) is related to PCA since it ends up with a similar result even though the computation is different. In this exercise, we want to discuss the similarities and the differences between these two approaches.

Roughly speaking, SVD is an extended diagonalization technique which allows us to decompose our data matrix
\begin{equation}X = U\Sigma V^T\end{equation}

As usual, $X \in \mathbb{R}^{n×d}$ stores the observations in rows and the variables in columns. Here, we assume that $X$ is already centred, i.e. the columns have zero mean. $\Sigma$ is a diagonal matrix storing the singular values $s_i$ and the column vectors of $U$ and $V$ contain the left and right singular vectors, respectively.

In PCA, we need to calculate the covariance matrix $C$ (Equation 2). This matrix is symmetric so we can diagonalize it directly
\begin{equation} C = \frac{1}{n-1}X^TX = WDW^T \end{equation}
where 𝑊 stores the eigenvectors in the columns and 𝐷 has the eigenvalues 𝜆𝑖 on the diagonal. 

1. [Pen and Paper] Let’s begin with the matrices of SVD and see how they are related to PCA. For this, fill out the missing properties summarized in Table 2.

    a) For the matrices $U$ and $V$, do the singular vectors correspond to the eigenvectors of $X^TX$ or $XX^T$? For this, show the mappings of the third column of Table 2 with the help of Equation 3, Equation 4 and \begin{equation} \tilde{C} = \frac{1}{n-1}X^TX = \tilde{W}\tilde{D}\tilde{W}^T \end{equation}

    b) Based on your previous findings, what is the relationship between the singular values $s_i$ and the eigenvalues $\lambda_i$? \begin{equation} s_i = … \end{equation}
    
    c) Decide about the matrix dimensions (the mappings should help with this decision). Assume that zero rows/columns have not been removed. 
    
    d) We can also interpret the matrices geometrically. What is the corresponding affine transformation (translation, scaling, rotation, etc.) of each matrix? Hint: think about the special properties of the matrices

2. [Python] We saw that there is a strong relationship between the result of PCA and SVD since we can define a mapping between the eigenvectors/eigenvalues and singular vectors/singular values. However, the algorithm used to compute the results is different. For the standard approach with PCA1, we need to calculate the covariance matrix but this is not the case in SVD. It turns out that this is an advantage for SVD since these calculations can get numerically unstable. We now want to explore this circumstance a bit further by calculating the singular values of the matrix <br/></br/>\begin{equation} \begin{pmatrix}1 & 1 & 1\\ \epsilon & 0 & 0\\ 0 & \epsilon & 0\\ 0 & 0 & \epsilon \end{pmatrix} \end{equation}  <br/><br/> where $\epsilon \in \mathbb{R}^+$ is a small number. We are not interested in the corresponding vectors in this part.
    
    a) Define a function which takes 𝜀 as an argument and defines the matrix 𝐴 accordingly. 
        i. Calculate the singular values via the standard PCA method 
\begin{equation} C = A^TA \\ \lambda = eval(C) \\ s = \sqrt{\lambda} \end{equation}  <br/> 
        It is helpful to calculate this in a step-by-step fashion and to print the exact definition after each step with full precision. For the latter, you can use the astype(str) method of the ndarray objects.
        
        ii. Calculate the singular values $s$ again but this time using an SVD algorithm (e.g.np.linalg.svd) and print the result.

    b) Call your function and set $\epsilon$ to the tiny number $10^{-7}$
\begin{equation} epsilon = 1.0e-7 \end{equation}
    
    c) Now, set 𝜀 = 10−8 and repeat the calculations. If done correctly, you should get an error. What is the problem here?

    d) How can you tell that the standard PCA approach returns at least one incorrect result for the eigenvalues $\lambda$? Hint: look for a property of the covariance matrix which is violated here.

## Exercise 3 (3 points): PCA vs. LDA [Python]

As mentioned in Exercise 1, it is also common to use PCA (or SVD) as a dimensionality reduction technique. Instead of projecting our data points to all new axes, we select only a subset and this subset is designed to cover as much of the variance in the data as possible.


We already saw another dimensionality reduction technique in previous assignments, namely
linear discriminant analysis (LDA). We are going to apply PCA also to the Statlog (Vehicle
Silhouettes) dataset and compare the result with the one obtained by LDA. For the test script,
please pay also attention to Table 3.
1. Load the data from the train.csv file into your Python program.

2. PCA may not work well when the features are scaled differently as it is the case with our
dataset. As a countermeasure, standardize the data (as discussed in assignment 3). You
can use the StandardScaler from the sklearn package for this purpose.

3. Apply PCA to the dataset and calculate the (two-dimensional) projections of the data
to the new coordinate system. There is a PCA class in the sklearn.decomposition
package which you can use.

4. Show the explained variance (in percentage terms) as a cumulative sum over all eigenvalues
in a plot (Figure 2 shows an example solution).

5. Plot the data with respect to the first two principal components (𝒖1 and 𝒖2) and compare
the result with your LDA plot.

6. Fill out Table 4 which compares some properties of PCA with LDA.
    
    a) Is the procedure supervised or unsupervised?
    
    b) What is the focus of the new axes, i.e. are they designed to explain the variance in
the data or to discriminate the classes?
    
    c) What is the maximal number of eigenvectors we can retrieve, i.e. the maximal dimension size of the projection space?

a547ddaea067ea4b5c0e9b2416dc3ed5d91dc304
ipynb
Jupyter Notebook
09_pca_svd_lda/PCA.ipynb
jhinga-la-la/pattern-recognition-course
7ad4f70b2c427f3c37f59f47768b90371873823c
Apache-2.0
09_pca_svd_lda/PCA.ipynb
jhinga-la-la/pattern-recognition-course
7ad4f70b2c427f3c37f59f47768b90371873823c
Apache-2.0
09_pca_svd_lda/PCA.ipynb
jhinga-la-la/pattern-recognition-course
7ad4f70b2c427f3c37f59f47768b90371873823c
Apache-2.0
Qwen/Qwen-72B
1. YES
2. YES