Principal Component Analysis

The first step is to do mean normalization and feature scaling. This is to make sure that the features are comparable.

$X_{normalized} = \frac{X - \mu}{\sigma^2}$

where

$\mu_j = \frac{1}{m}\sum_{i=1}^{m}x_j^{i}$

$\sigma^2_j = \frac{1}{m - 1}\sum_{i=1}^{m} (x_j^{i} - \mu^{i}_{j})^2$

Let the given data contain n features and we want to reduce the dimensions to k with minimum information loss.

The task is find a hyperplane of dimension k such that the squared distance between the datapoints X and the hyperplane is at a minimum. Once you find that, you can use projection theorem to find the projection $p\ \epsilon\ \mathbb{R}^d$ of each datapoint $x\ \epsilon\ \mathbb{R}^n$ .

Covariance Matrix

To find the similarity between two vectors x1 and x2, you take dot product between two vectors. Because we subracted the input data from it’s mean, the dot product will also corresponds to variance.

$variance = x_1^Tx_1$

Consider the following matrix A.

$A = [x_1\ x_2\ x_3]$

The covariance between x1 and x2 is given by

$covariance(x_1, x_2) = x_1^Tx_2$

We want to find the covariance between all vectors – $x_1, x_2, x_3$ . Simplest way to do this is to take $A^TA$ .

$A^TA = \begin{bmatrix} x_1^T\ x_2^T\ x_3^T \end{bmatrix} \begin{bmatrix} x_1 & x_2 & x_3 \end{bmatrix}$

$A^TA = \begin{bmatrix} x_1^Tx_1 & x_1^Tx_2 & x_1^Tx_3\ x_2^Tx_1 & x_2^Tx_2 & x_2^Tx_3\ x_3^Tx_1 & x_3^Tx_2 & x_3^Tx_3 \end{bmatrix}$

Now, we have covariance between all of the vectors. The challenge now is to find the direction of highest variance. Fortunately, we have eigen value and eigen vectors for the rescue. Eigen vector is a vector whose direction doesn’t change even after transformation.

$A \cdot x = \lambda \cdot x;\ \text{where } \lambda \neq0$

To understand further about eigen values and eigen vectors, refer to mit linear algebra document.

By calculating the eigen value and eigen vector of the covariance matrix $\Sigma$ , we get the directions of the vectors whose direction remains same even after transforming the vector by $\Sigma$ . The eigen vectors are linearly independent and can be the basis vectors for the input space. If we choose k eigen vectors with maximum eigen values, it represents the k directions of maximum variance. The input data will then be projected on to hyperplane formed by these k vectors (Let the matrix of k vectors be represented by U).

$z = U^Tx$

$z^i_{k \times 1} = U^T_{k \times n} x^i_{n \times 1}$

To choose k, calculate the error or the distance between original dataset and dimensionality reduced dataset and divide it by total variance in the dataset. Choose k such that the ratio is very small.

Choose smallest value of k that satisfies the following condition (Click here to see the video).

$\frac{\frac{1}{m} \sum_{i = 1}^{m}||x^{(i)} - x^{(i)}*{approx}||^2}{\frac{1}{m} \sum_{i = 1}^{m}||x^{(i)}||^2} \leq 0.01$

Final note: We run PCA only on the training set, not on the validation set (We just project the test set on to the basis found by pca).

ML/DL Page

# ML – Principal Component Analysis

Principal Component Analysis

Covariance Matrix

Leave a Reply Cancel reply