AI Concept Takeaway: PCA

My takeaway series follow a Q&A format to explain AI concepts at three levels:

TipConceptual Level

Anyone with general knowledge can understand them.

WarningImplementation Level

For anyone who wants to dive into the code implementation details of the concept.

ImportantMathematical Level

For anyone who wants to understand the mathematics behind the technique.

---

TipWhat is PCA?

Principal Component Analysis (PCA) is a dimensionality reduction technique. It finds the principal components in high-dimensional data and projects the data onto a lower-dimensional space. In AI context, PCA is an unsupervised learning algorithm.

ImportantWhat are the input and output of PCA?

PCA is a data dimensionality reduction technique.

Inputs:

• A dataset with $n$ samples and $d$ features, represented as a matrix $\mathbf{X}\in {\mathbb{R}}^{n\times d}$, where each row corresponds to a sample and each column corresponds to a feature with $d$ dimension.

Outputs:

• A transformed dataset with $n$ samples and $k$ principal components, represented as a matrix $\mathbf{Z}\in {\mathbb{R}}^{n\times k}$, where $k<d$.

ImportantHow to do PCA?

PCA is done by SVD (Singular Value Decomposition). The steps are as follows:

1. Standardize the data: Subtract the mean and divide by the standard deviation for each feature to ensure that each feature contributes equally to the analysis.

$$\mathbf{X}=\frac{\mathbf{X}-\mu }{\sigma }$$

2. Perform SVD on the standardized data matrix:

$$\mathbf{X}=\mathbf{U}\mathbf{\Sigma }{\mathbf{V}}^T$$

where $\mathbf{U}\in {\mathbb{R}}^{n\times n}$ is the left singular vectors, $\mathbf{\Sigma }\in {\mathbb{R}}^{n\times d}$ is a diagonal matrix with singular values, and ${\mathbf{V}}^T\in {\mathbb{R}}^{d\times d}$ is the right singular vectors.

3. Choose the top $k$ columns of $\mathbf{U}$ corresponding to the largest singular values in $\mathbf{\Sigma }$:

$${\mathbf{U}}_k=({\mathbf{u}}_1,\cdots ,{\mathbf{u}}_k)$$

4. Transform the data: Project the original standardized data onto the new feature space using the chosen principal components.

$${\mathbf{z}}_1=\mathbf{X}\cdot {\mathbf{u}}_1\in {\mathbb{R}}^n$$ $${\mathbf{z}}_2=\mathbf{X}\cdot {\mathbf{u}}_2\in {\mathbb{R}}^n$$ $$\cdots$$ $${\mathbf{z}}_k=\mathbf{X}\cdot {\mathbf{u}}_k\in {\mathbb{R}}^n$$

Each principal component $z_i$ represents a new feature that is a linear combination of the original features. This can be written in matrix form as:

$$\mathbf{Z}=\mathbf{X}\cdot {\mathbf{U}}_k\in {\mathbb{R}}^{n\times k}$$

ImportantWhat good is the feature transformed by the principal components ${\mathbf{U}}_k$?

1. The feature projected onto the first principal component ${\mathbf{u}}_1$ has the largest variance, the feature projected onto the second principal component ${\mathbf{u}}_2$ has the second largest variance, and so on.
2. The transformed feature are statistically uncorrelated to each other, that is, when a feature increases or decreases, the other features do not change in a predictable way.

These two properties make the new features:

1. More informative and less redundant, because the features carrying more information (less variance) are preserved first, and less informative (more variance) features are discarded.
2. More independent, because the features are uncorrelated.

ImportantWhat is the visual interpretation of PCA?

${\mathbf{U}}_k$ is a linear transformation. In linear algebra we learned, a linear transformation is a mathematical operation that can substitute the original coordinate system with a new coordinate system. If there is no bias term, the new coordinate system is also based on the same origin point. In (PCA-visualization?), it looks like the new coordinate system moves away from the original coordinate system, that is because we have zero centred the data.

In PCA, the new coordinate system is defined by the principal components ${\mathbf{u}}_i$. Since $\mathbf{U}$ is an orthogonal matrix, the principal components ${\mathbf{u}}_i$ are orthogonal to each other, so the new coordinate system is orthogonal.

PCA visual interpretation. (Source: NUMXL)

ImportantWhy do we need to standardize the data before applying PCA?

Standardizing the data is crucial before applying PCA because PCA is sensitive to the scale of the features. If the features are on different scales, PCA may give more importance to features with larger scales, leading to biased results. Standardization ensures that each feature contributes equally to the analysis by transforming them to have zero mean and unit variance.

ImportantWhat is SVD (Singular Value Decomposition)?

SVD is a mathematical technique that decomposes a matrix into three other matrices. For a given matrix $A\in {\mathbb{R}}^{m\times n}$, SVD decomposes it as follows:

$$A=U\mathrm{\Sigma }{V}^T$$

where:

• $U\in {\mathbb{R}}^{m\times m}$ is an orthogonal matrix whose columns are the left singular vectors of $A$.
• $\mathrm{\Sigma }\in {\mathbb{R}}^{m\times n}$ is a diagonal matrix whose diagonal entries are the singular values of $A$.
• $V^T\in {\mathbb{R}}^{n\times n}$ is an orthogonal matrix whose columns are the right singular vectors of $A$.

The singular values in $\mathrm{\Sigma }$ are non-negative and are typically arranged in descending order. The number of non-zero singular values is equal to the rank of the matrix $A$.

ImportantHow to compute SVD?

To compute the SVD of a matrix $A$, follow these steps:

1. Compute the covariance matrix of $A$:

$$C=A^{T}A$$

2. Compute the eigenvalues and eigenvectors of the covariance matrix $C$:

$$C{v}_i={\lambda }_i{v}_i$$

3. Form the matrix $V$ using the normalized eigenvectors $v_i$ as columns.

4. Compute the singular values ${\sigma }_i$ as the square roots of the eigenvalues:

$${\sigma }_i=\sqrt{{\lambda }_i}$$

5. Form the diagonal matrix $\mathrm{\Sigma }$ using the singular values ${\sigma }_i$.

6. Compute the left singular vectors $U$ using the relationship:

$$U=AV{\mathrm{\Sigma }}^{-1}$$

7. The SVD of $A$ is then given by:

$$A=U\mathrm{\Sigma }{V}^T$$