14.3 Dimensionality Reduction I: PCA

The Curse of Dimensionality

As the number of features (dimensions) in a dataset grows, the volume of the space increases so fast that the available data becomes sparse. This "curse of dimensionality" can make it difficult to train machine learning models, as the distance between data points becomes less meaningful.

Dimensionality reduction techniques aim to reduce the number of features while preserving as much of the important information as possible. Principal Component Analysis (PCA) is one of the most fundamental and widely used methods for this purpose.

Principal Component Analysis (PCA)

PCA is a linear technique that transforms the data into a new coordinate system. The new axes, called principal components, are chosen to be orthogonal and to capture the maximum amount of variance in the data.

The first principal component is the direction along which the data varies the most. The second principal component is orthogonal to the first and captures the next largest amount of variance, and so on.

Mathematical Foundation

PCA is based on the eigendecomposition of the data's covariance matrix.

1. Standardize the Data: First, the data is centered by subtracting the mean from each feature. Often, the features are also scaled to have unit variance.
2. Compute the Covariance Matrix: The covariance matrix \(\mathbf{\Sigma}\) measures how different features vary with respect to each other. For a dataset \(\mathbf{X}\) with \(n\) features, \(\mathbf{\Sigma}\) is an \(n \times n\) matrix.

   \(\mathbf{\Sigma} = \frac{1}{m-1} \mathbf{X}^T \mathbf{X}\) (where \(m\) is the number of samples)

3. Eigendecomposition: We then find the eigenvectors and eigenvalues of the covariance matrix.

   \(\mathbf{\Sigma} \mathbf{v} = \lambda \mathbf{v}\)

   Here, \(\mathbf{v}\) is an eigenvector and \(\lambda\) is the corresponding eigenvalue. The eigenvectors represent the directions of the principal components, and the eigenvalues represent the amount of variance captured by each component.
4. Select Principal Components: The eigenvectors are sorted by their corresponding eigenvalues in descending order. The top \(k\) eigenvectors are chosen to form a new feature space.
5. Transform the Data: The original data is projected onto the new feature space defined by the selected principal components.