(Originally published on August 21, 2018)

Any machine learning model building task begins with a collection of data vectors wherein each vector consists of a fixed number of components. These components represent the measurements, known as *attributes* or *features*, deemed useful for the given machine learning task at hand. The number of components, i.e. the *size* of the vector, is termed as the *dimensionality *of the feature space. When the number of features is large, we are often interested in reducing their number to limit the number of training examples needed to strike a proper balance with the number of model parameters. One way to reduce the number of features is to look for a subset of original features via some suitable search technique. Another way to reduce the number of features or dimensionality is to map or transform the original features in to another feature space of smaller dimensionality. The Principal Component Analysis (PCA) is an example of this feature transformation approach where the new features are constructed by applying a *linear transformation* on the original set of features. The use of PCA does not require knowledge of the class labels associated with each data vector. Thus, PCA is characterized as a *linear*, *unsupervised* technique for dimensionality reduction.

##### Basic Idea Behind PCA

The basic idea behind PCA is to exploit the correlations between the original features. To understand this, lets look at the following two plots showing how a pair of variables vary together. In the left plot, there is no relationship in how X-Y values are varying; the values seem to be varying randomly. On the other hand, the variations in the right side plot exhibits a pattern; the Y values are moving up in a linear fashion. In terms of correlation, we say that the values in the left plot show no correlation while the values in the right plot show good correlation. It is not hard to notice that given a X-value from the right plot, we can reasonably guess the Y-value; however this cannot be done for X-values in the left graph. This means that we can represent the data in the right plot with a good approximation lying along a line, that is we can reduce the original two-dimensional data in one dimensions. Thus achieving dimensionality reduction. Of course, such a reduction is not possible for data in the left plot where there is no correlation in X-Y pairs of values.

##### PCA Steps

Now that we know the basic idea behind the PCA, let's look at the steps needed to perform PCA. These are:

- We start with
*N**d*-dimensionaldata vectors, $\boldsymbol{x}_i, i= 1, \cdots,N$, and find the eigenvalues and eigenvectors of the sample covariance matrix of size*d x d*using the given data - We select the top
*k*eigenvalues,*k ≤ d,*and use the corresponding eigenvectors to define the linear transformation matrixof size**A***k x d*for transforming original features into the new space. - Obtain the transformed vectors, $\boldsymbol{y}_i, i= 1, \cdots,N$, using the following relationship. Note the transformation involves first shifting the origin of the original feature space using the mean of the input vectors as shown below, and then applying the transformation.

$\boldsymbol{y}_i = \bf{A}(\bf{x}_i - \bf{m}_x)$

- The transformed vectors are the ones we then use for visualization and building our predictive model. We can also recover the original data vectors with certain error by using the following relationship

$\boldsymbol{\hat x}_i = \boldsymbol{A}^t\boldsymbol{y}_i + \boldsymbol{m}_x$

- The mean square error (mse) between the original and reconstructed vectors is the sum of the eigenvalues whose corresponding eigenvectors are not used in the transformation matrix
.**A**

$ e_{mse} = \sum\limits_{j=k+1}\limits^d \lambda_j$

- Another way to look at how good the PCA is doing is by calculating the percentage variability,
*P*, captured by the eigenvectors corresponding to top*k*eigenvalues. This is expressed by the following formula

$ P = \frac{\sum\limits_{j=1}^k \lambda_j}{\sum_{j=1}^d \lambda_j}$

##### A Simple PCA Example

Let's look at PCA computation in python using 10 vectors in three dimensions. The PCA calculations will be done following the steps given above. Lets first describe the input vectors, calculate the mean vector and the covariance matrix.

Next, we get the eigenvalues and eigenvectors. We are going to reduce the data to two dimensions. So we form the transformation matrix * A* using the eigenvectors of top two eigenvalues.

With the calculated ** A **matrix, we transform the input vectors to obtain vectors in two dimensions to complete the PCA operation.

Looking at the calculated mean square error, we find that it is not equal to the smallest eigenvalue (0.74992815) as expected. So what is the catch here? It turns out that the formula used in calculating the covariance matrix assums the number of examples, *N*, to be large. In our case, the number of examples is rather small, only 10. Thus, if we multiply the mse value by *N/(N-1), known *as the* small sample correction*, we will get the result identical to the smallest eigenvalue. As *N *becomes large, the ratio *N/(N-1)* approaches unity and no such correction is required.

The above PCA computation was deliberately done through a series of steps. In practice, the PCA can be easily done using the scikit-learn implementation as shown below.

Before wrapping up, let me summarize a few takeaways about PCA.

- You should not expect PCA to provide much reduction in dimensionality if the original features have little correlation with each other.
- It is often a good practice to perform data normalization prior to applying PCA. The normalization converts each feature to have a zero mean and unit variance. Without normalization, the features showing large variance tend to dominate the result. Such large variances could also be caused by the scales used for measuring different features. This can be easily done by using sklearn.preprocessing.StandardScalar class.
- Instead of performing PCA using the covariance matrix, we can also use the correlation matrix. The correlation matrix has a built-in normalization of features and thus the data normalization is not needed. Sometimes, the correlation matrix is referred to as the standardized covariance matrix.
- Eigenvalues and eigenvectors are typically calculated by the singular value decomposion (SVD) method of matrix factorization. Thus, PCA and SVD are often viewed the same. But you should remember that the starting point for PCA is a collection of data vectors that are needed to compute sample covariance/correlation matrices to perform eigenvector decomposition which is often done by SVD.

## No comments:

## Post a Comment