Dimensionality Reduction

Dimensionality Reduction

1. Why reduce dimensionality?

• The models we fit are typically higher-dimensional input data (2, 3,…,100-dimensional etc.)
• The model may not just consider the impact of each input feature separately, but also possible interactions of two or more features.
• Typically, each feature we wish to allow to impact our predictions requires a parameter in the model
• Thus, the model’s number of parameters grows (often super-linearly) with the dimensions.
• When we fit the model, we must find a joint setting of all these parameters. So the dimension of the optimization problem is the number of parameters.

Dimensionality reduction allows reducing the number of dimensions, and thereby the number of parameters.

Benefits of dimensionality reduction

• Computationally less expensive than fitting/using a model which dimensionality scales poorly.
• Numerically/statistically better to use lower-dimensional representations because it can often be more stable, leading to better performance.
• Interpretability/simplicity achieved by removing irrelevant/redundant, which helps expose key structures in data more clearly.

Why we can reduce dimensionality

• A key assumption in dimensionality reduction is the manifold hypothesis, that the data can be represented (approximated) well by lower-dimensional data.
• The data is said to lie on a lower-dimensional manifold.
• What follows is how to transform the higher-dimensional (real) vector-valued input data by (almost) projecting it onto a lower-dimensional subspace.

---

2. Principle Component Analysis (PCA)

Essentially, PCA finds lower-dimensional subspaces that describe the essential properties of our data. This allows one to project the data onto these lower-dimensional subspaces, sometimes leading to significant dimensionality reductions.

Principal components are closely related to the singular value decomposition (SVD).

PCA maximizes variance.

LDA is particularly useful in classification problems. We will discuss this classification technique later.

Change of basis

• PCA starts with finding the optimal basis (in some sense) for representing the data.
• Change of basis is implemented by multiplication by an orthogonal matrix $Q$.

We say $Q$ is orthogonal/orthonormal if $Q^{T}Q=Q{Q}^T=I$ or $Q^T=Q^{-1}$

• Since $Q{Q}^T=I$, $|Q|=\pm 1$
• Important special cases:
  • $Q$ is the identity matrix: $|Q|=1$
  • $Q$ is a permutation matrix: $|Q|=\pm 1$
  • $Q$ is a rotation matrix: $|Q|=1$
• Take note: Rotation preserve determinant; reflection about axis changes sign of determinant

Input/feature space

• Project a d-dimensional input (observation vector) $\text{x}$ onto another d-dimensional vector $\text{a}$:

$$pro{j}_a\text{x}=\frac{\text{x}\cdot \text{a}}{\Vert \text{a}{\Vert }^2}\text{a}\text{\hspace{1em}(2.1)}$$

• If $\text{a}$ is made a unit vector, the dot product $\text{a}\cdot \text{x}={\text{a}}^T\text{x}$ gives the length of the projection of $\text{x}$ onto $\text{a}$.
• We call the projection length, the score of $\text{x}$ for the feature $\text{a}$.
• Collecting a number of unit vectors as features into a matrix $A$ (one column per feature), $A^T\text{x}$ gives a vector of scores.
• This vector of scores is called the feature vector corresponding to $\text{x}$ for the feature space defined by $A$.

The dimensionality reduction approach looks for good ways to choose the feature matrix $A$.

Motivation for applying PCA

• Having the machine learning techniques not depend on the axis system of the collected/recorded data.
• The key idea for choosing features in PCA is thus to remove dependence on the input axes.

How to change the axis system:

1. Permuting the axes (changing the order of attributes)
2. Translating the origin (e.g. Celsius vs. Fahrenheit vs. Kelvin)
3. Scaling the axes (e.g. Celsius vs. Fahrenheit, imperial vs. metric)
4. Reflecting the axes (e.g. % increase vs. % decrease, profit vs. loss)
5. Rotating the axes (e.g. different camera orientations when capturing images)

• Projection can’t do translation, so it is typical to centre the data first and then subtract the mean from all observations.
• PCA defines a canonical set of axes (up to reflection) - ordering based on importance - which reduces dimension.

Data

• Given $N$ real vector-valued observations, each of dimension $d$.
• The original data $X$ is collected into a $d\times N$ matrix.
• The centered (mean-subtracted) data is collected into matrix $D$, also with shape $d\times N$.
• To center the data: subtract the mean of each attribute from the value of the corresponding attribute, for each observation.
• Equivalently, subtract the mean vector $\bar{\text{x}}$ from each column:

D = X - \bar{\textbf x}\textbf 1_N^T $$where $\textbf 1_N$ denotes a vector with N ones or equivalently,

\textbf d_i = \textbf x_i - \bar{\textbf x}

D = {\textbf d_i, \dots, \textbf d_N}

Given $N$ observations $\textbf x_n \in \mathbb{R}^d, n = 1,...,N$ of dimension $d$, we will begin by trying to find the directions of **maximum variation** in the data. Consider projecting the data points onto a one-dimensional subspace spanned by a unit vector $\textbf u_1$. Thus $\textbf x_n$ is projected onto the vector $(\textbf u_1^T\textbf x_n)\textbf u_1$and in this coordinate system the projected value is just given by $\textbf u_1^T \textbf x_n$. The idea is to choose $\textbf u_1$ in such a way that the variance of the projected values is as large as possible. If the sample mean vector is given by:

\bar{\textbf x} = \frac{1}{N}\sum_{n=1}^N \textbf x_n

then the mean of the projected data is $\textbf u_1^T \bar{\textbf x}$, and the **variance** of the projected data is:

\begin{aligned} &=\frac{1}{N}\sum_{n=1}^N (\textbf u_1^T\textbf x_n - \textbf u_1^T\bar{\textbf x})(\textbf u_1^T\textbf x_n - \textbf u_1^T\bar{\textbf x})^T \ &= \frac{1}{N}\sum_{n=1}^N \textbf u_1^T(\textbf x_n - \bar{\textbf x})(\textbf x_n - \bar{\textbf x})^T\textbf u_1 \ &= \textbf{u}1^T\left[\frac{1}{N}\sum{n=1}^N{(\textbf{x}_n-\bar{\textbf{x}})(\textbf{x}_n-\bar{\textbf{x}})^T}\right]\textbf{u}_1 \ &= \textbf{u}_1^TS\textbf{u}_1 \end{aligned} \tag{2.2}

where $S$ is the sample covariance matrix:

S = \frac{1}{N}\sum_{n=1}^N(\textbf x_n - \bar{\textbf x})(\textbf x_n - \bar{\textbf x})^T = \frac{1}{N}DD^T \tag{2.3}

#### Finding the first principal component ($\textbf u_1$) by optimization - Sample covariance matrix $S$ is a $d \times d$ matrix - $(i, j)$-th entry of S is covariance of attributes $i$ and $j$ - Consider a potential feature specified by a vector $\textbf u$. - The variance of the scores for this feature is $\textbf u^T S\textbf u$. (Note this is a scalar and is derived above) - In order to maximize this, $\textbf u$ needs to be a unit vector! #### Constrained optimization with Lagrange multiplier Optimize $\textbf{u}^TS\textbf{u}$ subject to $\textbf{u}^{T}\textbf{u} = 1$ Introduce Lagrange multiplier $\lambda$ for the constraint We optimize the Lagrangian:

\mathcal{L}(\textbf{u},\lambda) = \textbf{u}^TS\textbf{u} + \lambda(1-\textbf u^T\textbf u) \tag{2.4}

Set the gradient w.r.t $\textbf u$ equal to zero:

\nabla_u \mathcal{L} = \frac{\partial \mathcal{L}}{\partial\textbf u}\left[\textbf{u}^TS\textbf{u} + \lambda(1-\textbf u^T\textbf u)\right]= 2S\textbf u - 2\lambda\textbf u = 0

2S\textbf u = 2\lambda\textbf u \longrightarrow S\textbf u = \lambda\textbf u \tag{2.5}

Thus the critical points are eigenvectors, with the corresponding score variances given by the corresponding eigenvalues. For **(PC1)**, choose the eigenvector $\textbf u_1$ corresponding to the largest eigenvalue. #### Finding the rest of the principle components Since PCA requires principle components to be orthogonal, we simply add an additional constraint and **Lagrange Multiplier** to optimize the covariance. Maximize $\textbf u^TS\textbf u$ subject to $\textbf u^T\textbf u = 1$, but also $\textbf u^T\textbf u_1 = 0$ (orthogonal). Introduce Lagrange multipliers for both constraints, and optimize similarly:

\mathcal{L}(\textbf{u},\lambda_1,\lambda_2) = \textbf{u}^TS\textbf{u} + \lambda_1(1-\textbf u^T\textbf u) + \lambda_2\textbf u^T\textbf u_1 \tag{2.6}

Set the gradient w.r.t $\textbf u_1$ equal to zero:

\nabla_u \mathcal{L} = \frac{\partial \mathcal{L}}{\partial\textbf u}\left[\textbf{u}^TS\textbf{u} + \lambda_1(1-\textbf u^T\textbf u) + \lambda_2\textbf u^T\textbf u_1\right]= 2S\textbf u - 2\lambda_1\textbf u + \lambda_2\textbf u_1 = 0 \tag{2.7}

\frac{\partial \mathcal{L}}{\partial \lambda_1} = 1 - \textbf u^T\textbf u = 0 \tag{2.8}

\frac{\partial \mathcal{L}}{\partial \lambda_2} = \textbf u^T\textbf u_1 = 0 \tag{2.9} $$ We can prove that ${\lambda }_2$ is zero by multiplying ${\nabla }_u\mathcal{L}$ with ${\text{u}}_1^T$

$${\text{u}}_1^T{\nabla }_u\mathcal{L}={\text{u}}_1^T[2S\text{u}-2{\lambda }_1\text{u}+{\lambda }_2{\text{u}}_1]=2{\text{u}}_1^{T}S\text{u}-2{\text{u}}_1^T{\lambda }_1\text{u}+{\lambda }_2{\text{u}}_1^T{\text{u}}_1=0\text{\hspace{1em}(2.10)}$$

Then,

• ${\text{u}}_1^{T}S\text{u}=0$ (since ${\text{u}}_1$ and $\text{u}$ are orthogonal)
• ${\text{u}}_1^T{\lambda }_1\text{u}={\lambda }_1{\text{u}}_1^T\text{u}=0$ (since ${\text{u}}_1$ and $\text{u}$ are orthogonal)
• ${\lambda }_2{\text{u}}_1^T{\text{u}}_1=1$ (since ${\text{u}}_1$ is a unit vector)

Now equation $(2.10)$ can be used to show:

$${\text{u}}_1^T{\nabla }_u\mathcal{L}={\lambda }_2{\text{u}}_1^T\text{u}=0$$ $$\therefore {\lambda }_2=0$$

With this equation $(2.7)$ can be reduced to:

$${\nabla }_u\mathcal{L}=2S\text{u}-2{\lambda }_1\text{u}=0$$ $$2S\text{u}=2\lambda \text{u}⟶S\text{u}=\lambda \text{u}\text{\hspace{1em}(2.11)}$$

The solutions $(2.11)$ are once again the eigenvectors of S same result as in $(2.5)$, however, since they must be orthogonal, it is the next biggest eigenvalue’s eigenvector.

Therefore, the nth principle component is eigenvector corresponding to the nth biggest eigenvalue.

Finding principle components in practice

• Need to find the eigenvectors and eigenvalues of the covariance matrix.
• Natural tool: eigendecomposition of a symmetric matrix (a.k.a diagonalization).
• Also consider another approach: using the Singular Value Decomposition (SVD)
• Both approaches collect the eigenvectors of interest in a matrix, and we use matrix multiplication to project the observations into the feature space.

Finding principle components by eigendecomposition

• S is symmetric, so can be factored using eigendecomposition: S= Q\Lambda Q^T \tag{2.12}
• numpy.linalg.eigh optimizes eigendecomposition for symmetric matrices, and order eigenvalues in decreasing order.
• Columns of $d\times d$ matrix $Q$ are the principal components.
• Diagonal entries of $d\times d$ matrix $\Lambda$ are the eigenvalues.

Symmetric: $S=S^T$

Dimension reduction after eigendecomposition

• To reduce dimension, we use the first $v$ principal components by forming $Q_v$ from the first $v$ columns of $Q$.

Notation: when we subscript a matrix by an integer value e.g. $Q_v$, we are limiting the number of rows/columns from $d$ to that value.

• Then the transformed data is $Q_v^{T}D$
• When $v=d$, there is no dimensionality reduction, just a change of basis specified by $Q$.
• We have $S=Q\Lambda Q^T\approx Q_v{\Lambda }_v{Q}_v^T$, where ${\Lambda }_v$ contains $v$ largest eigenvalues on diagonal: $Q_v\Lambda Q_v^T$ is a rank-$v$ approximation to $S$.

The singular value decomposition (SVD)

Any $d\times N$ real matrix $X$ can be decomposed as $X=U\Sigma V^T$, where

• $U$ is a $d\times d$ orthogonal matrix
• $\Sigma$ is a $d\times N$ (rectangular) diagonal matrix with non-negative entries in non-increasing order down the diagonal
• $V$ is an $N\times N$ orthogonal matrix

Such a decomposition is called an SVD of X.

$\Sigma$ is fully determined by $X$ and its number of non-zero entries is the $rank(X)$.

The non-zero entries of $\Sigma$ are called the singular values of $X$.

Solving these matrices:

$$\begin{array}{rl}{X}^{T}X& =(U\Sigma V^T{)}^T(U\Sigma V^T)\\ & =V{\Sigma }^T{U}^{T}U\Sigma V^T\\ & =V{\Sigma }^T\Sigma V^T\\ & =V{\Sigma }^2{V}^T\\ X^{T}XV& =V{\Sigma }^2\end{array}\text{\hspace{1em}(2.13)}$$

Note: $(U\Sigma V^T{)}^T=V\Sigma U^T$, $U^{T}U=I$ because $U$ is orthogonal and ${\Sigma }^T\Sigma =\Sigma {\Sigma }^T={\Sigma }^2$ since $\Sigma$ is diagonal.

$X^{T}XV=V{\Sigma }^2$ is an eigenvalue problem ($Ax=\lambda x$), with $x=V$, $A=X^{T}X$, and ${\Sigma }^2=\lambda$, thus an eigendecomposition is used to compute $V$.

Similarly for $U$:

$$\begin{array}{rl}X{X}^T& =(U\Sigma V^T)(U\Sigma V^T{)}^T\\ & =U{\Sigma }^T{V}^{T}V\Sigma U^T\\ & =U{\Sigma }^T\Sigma U^T\\ & =U{\Sigma }^2{U}^T\\ X^{T}XU& =U{\Sigma }^2\end{array}\text{\hspace{1em}(2.14)}$$

More on the SVD

• The columns of $U$ and $V$ (not $V^T$) are left and right singular vectors of $X$ respectively.
• Each singular vector is associated with a corresponding singular value (in the same column) of $\Sigma$.
• If a singular value is distinct, its left and right singular vectors are unique up to negation.
• When $N\ll d$ i.e. much more samples than input dimensions (which is always the case in this course), we can trim $\Sigma$ and $V$ of many zero columns to get the reduced SVD: $X=U{\Sigma }_d{V}_d^T$
• Setting $r=rank(X)$, we get the compact SVD, which trims even more zeroes from all three matrices: $X=U{\Sigma }_r{V}_r^T$

Finding principal components by SVD

• We consider performing SVD on the centered data: $D=U\Sigma V^T=U{\Sigma }_d{V}_d^T$
• Plug this into the formula $S=\frac{1}{N}D{D}^T$ and compare the results to the eigendecomposition.

$$\begin{array}{rl}S& =\frac{1}{N}D{D}^T\\ & =\frac{1}{N}(U\Sigma V^T)(U\Sigma V^T{)}^T\\ & =\frac{1}{N}U\Sigma V^{T}V{\Sigma }^T{U}^T\\ & =U\left[\frac{{\Sigma }_d^2}{N}\right]U^T\\ & =Q\Lambda Q^T\end{array}\text{\hspace{1em}(2.15)}$$

Note: this is the equation $(2.12)$

• We see that $Q=U$ and $\Lambda =\frac{1}{N}{\Sigma }_d^2$ , so we can also use singular values to calculate variance for each principal component (PC).
• Benefits of using SVD over eigendecomposition is primarily numerical stability (by avoiding computing the covariance matrix).

Discarding dimensions with the SVD

• Suppose the rank of $D$ is $r<d$, so some diagonal entries of ${\Sigma }_d$ are zero.
• We can use the compact SVD, $D=U_r{\Sigma }_r{V}_r^T$, to obtain the $r$ PCs
• We can also get fewer PCs by approximating D with the truncated SVD: $D\approx D_v\equiv U_v{\Sigma }_v{V}_v^T$
• Important: $D_v$ here is an approximation to D, not just retaining $v$ rows/columns of $D$!

Input space to feature space