Principal Component Analysis

Principal component analysis (PCA) is a linear dimensionality reduction technique.

Advantages of PCA / SVD

• State of the art for many applications (supervised and unsupervised)
• Incredibly efficient (often, almost linear time)
• Strong theoretical background
• Can also be used to store data in more efficient way (image compression)
• Visual evaluation possible for small number of components (2 or 3)

Link to original

Abstract

PCA and SVD (singular value decomposition) are slightly different but similar. We look at PCA in this course (which often uses SVD).

Example

Say you have a bunch of house listings and you would like to group them into: student housing, regular, luxury

Let’s assume we have the features: floor size ($m^2$), no. of rooms, distance to supermarket, distance to King’s, “hipster vibe”.

We want to reduce this to two or three features, we can do it like this:

• Size (floor size, no. of rooms)
• Location (distance to supermarket & King’s, “hipster vibe”)

The floor size and number of rooms are often correlated:

We can take the line that minimises the Least Square Distance, which gives us the following projection of points:

We want to maximise the variance which helps retain more information.

3D to 2D

Let’s say we have our three dimensions as relating to location (on l.h.s):

We can reduce it to 2D so it looks like the r.h.s. We may wish to reduce it to just a line (1D) but this can be very lossy.

5D to 3D

If we plot our 5D data using the components we found (1 for size and 2 for location), we get this 3D plot: (we can see the classes are well-separated)

We’ve reduced the information but retained important factors.

Matrices

Matrix Multiplication

Link to original

Matrix Transpose

The transpose of a matrix $A$ is an operation which flips the matrix along its diagonal.

$$\begin{array}{rl}A& =\left(\begin{array}{cccc}a& b& c& d\\ e& f& g& h\end{array}\right)\\ A^T& =\left(\begin{array}{cc}a& e\\ b& f\\ c& g\\ d& h\end{array}\right)\\ {\left(\begin{array}{c}{A}^T\end{array}\right)}^T& =A\end{array}$$Link to original

Transformation Matrix Cheatsheet

Matrix Stretch Transformation

We can stretch along the $y$-axis and squish along the $x$-axis with the following matrix:

$$\left(\begin{array}{cc}0.5& 0\\ 0& 2\end{array}\right)\cdot \left(\begin{array}{c}x\\ y\end{array}\right)=\left(\begin{array}{c}0.5x\\ 2y\end{array}\right)$$

Link to original

Largest eigenvalue is ${\lambda }_1=2$ and second largest is ${\lambda }_2=0.5$.

The corresponding eigenvectors are $v_1=\left(\begin{array}{c}0\\ 1\end{array}\right)$ and $v_2=\left(\begin{array}{c}1\\ 0\end{array}\right)$.

Matrix Rotation Transformation

We can rotate counterclockwise:

$$\left(\begin{array}{cc}0& -1\\ 1& 0\end{array}\right)\cdot \left(\begin{array}{c}x\\ y\end{array}\right)=\left(\begin{array}{c}-y\\ x\end{array}\right)$$

Link to original

Matrix Shear Mapping Transformation

Shear mapping (let $m\approx 1$ for the example):

$$\left(\begin{array}{cc}1& m\\ 0& 1\end{array}\right)\cdot \left(\begin{array}{c}x\\ y\end{array}\right)=\left(\begin{array}{c}x+my\\ y\end{array}\right)$$

Link to original

Eigenvector

Eigenvector

When a vector doesn’t change its direction after multiplying with a matrix, then it’s an eigenvector.

Formally, a vector $v$ is an eigenvector of the matrix $M$ if $M\cdot v=\lambda v$where $\lambda$ is the corresponding eigenvalue.

For example, $\left(\begin{array}{c}1\\ 0\end{array}\right)$ does not change when shear mapping.

Link to original

Eigenvalue

In the stretching example earlier, both vectors were eigenvectors as they didn’t change direction, however they did change length: the value by which the length changes is called the eigenvalue $\lambda$. (values provided in example above as a note)

Link to original

Consider $M=\left(\begin{array}{cc}2& 2\\ 5& -1\end{array}\right)$

We can verify that $v_1=\left(\begin{array}{c}1\\ 1\end{array}\right)$ and ${\lambda }_1=4$:

$$M\cdot v_1=\left(\begin{array}{cc}2& 2\\ 5& -1\end{array}\right)\cdot \left(\begin{array}{c}1\\ 1\end{array}\right)=\left(\begin{array}{c}4\\ 4\end{array}\right)=4\cdot \left(\begin{array}{c}1\\ 1\end{array}\right)={\lambda }_1{v}_1$$

The second eigenvector is $v_2=\left(\begin{array}{c}-2\\ 5\end{array}\right)$ and we want to find ${\lambda }_2$ so we plug it into the formula.

PCA Algorithm

PCA Algorithm

Let’s say this is our data matrix (e.g. our houses), where each data point is a $d$-dimensional row vector.

$$X=\left(\begin{array}{ccc}-& x_1^T& -\\ -& x_2^T& -\\ & ⋮& \\ -& x_n^T& -\end{array}\right)$$

1. Compute the mean row vector $\bar{x}=\frac{1}{n}{\sum }_{i=1}^n{x}_i$
2. Compute the mean row matrix:

\bar X = \begin{pmatrix} 1 \ 1 \ \vdots \ 1 \end{pmatrix} \cdot \bar x^T = \begin{pmatrix} - & \bar x^T & - \ - & \bar x^T & - \ & \vdots \ - & \bar x^T & - \ \end{pmatrix} $$

The dimensions are $n\times d$. 3. Subtract mean (obtain mean centred data)

$$B=X-\bar{X}$$

The dimensions are $n\times d$. 4. Compute the covariance matrix of rows of $B$

$$C=\frac{1}{n}{B}^{T}B$$

The dimensions are $(n\times d{)}^T\times (n\times d)=(d\times n)\times (n\times d)=d\times d$. (more notes on why we do this below) 5. Compute the $k$ largest eigenvectors $v_1,v_2,\dots ,v_k$ of C (not covered in module, use Python or WolframAlpha). Each eigenvector has dimensions $1\times d$.

Note

Depending on implementation, may not be sorted (e.g. certain Python libraries). Hence, sort eigenvectors by decreasing order of eigenvalues.

6. Compute matrix $W$ of $k$-largest eigenvectors. $$W=\left(\begin{array}{cccc}|& |& & |\\ v_1& v_2& \dots & v_k\\ |& |& & |\end{array}\right)$$ Dimensions of $W$ are $(d\times k)$.
7. Multiply each datapoint $x_i$ for $i\in \{1,2,\dots ,n\}$ with $W^T$. Dimensions of $y_i$ are $(k\times d)\times (d\times 1)=k\times 1$

We’ve now reduced the number of dimensions from $d$ to $k$.

Link to original

Why do we compute the covariance matrix?

The covariance matrix measures the correlation between pairs of features. By finding the largest eigenvectors, we can explain most of the variance in data.

The more variance is explained by the eigenvectors, the more important they are.

We can measure the explained variance by considering the quantity:

$$\frac{{\sum }_{i=1}^r{\lambda }_i}{{\sum }_{i=1}^d{\lambda }_i}$$