Module 13

Fundamentals of Dimensionality Reduction

Conceptual Overview: * In machine learning, data is typically represented as a matrix $X$ with dimensions $N \times D$ , where $N$ is the number of data points and $D$ is the number of attributes or features. * Dimensionality reduction involves transforming the original data into a new set of data $X'$ with dimensions $N \times k$ , such that k < D. * The primary goal is to perform data compression while preserving the essential parts of the original information.
Objectives and Benefits: * Data Smoothing: Reducing dimensions helps extract the "essence" of the data while discarding noise. * Improved Generalization: By eliminating noise and redundant features, the transformed data can lead to better performance in classification and regression models. * Overfitting Mitigation: Reducing the parameter space is a practical way to deal with overfitting. * Computational Efficiency: Smaller datasets require smaller models, leading to faster training times, more frequent experimentation, and more efficient hyperparameter searches. * Deployment: Models trained on reduced dimensions are easier to deploy and faster to execute in real-world predictive applications.

Mathematical Background: Covariance and Correlation

Covariance Definition: * Given two vectors $A_1$ and $A_2$ , each of length $N$ , the average (expectation) is defined as $E[A_1]$ and $E[A_2]$ . * The covariance between $A_1$ and $A_2$ is calculated as: $Cov(A_1, A_2) = \frac{(A_1 - E[A_1])^{T} \cdot (A_2 - E[A_2])}{N}$ * This represents the dot product of the mean-centered vectors divided by the number of observations.
Intuition of Covariance: * Covariance measures the correlation between two attributes. * A high covariance indicates a high correlation. For example, if $A_1$ is temperature in Celsius and $A_2$ is temperature in Fahrenheit, the covariance will be a high number due to their linear relationship. * If attributes are highly correlated, it suggests that some attributes can be dropped without losing significant information, which motivates dimensionality reduction.
Standardization: * Before calculating the covariance matrix, data should be standardized. * For every column (attribute) in matrix $X$ , the average value of that column is subtracted from every entry in that column, resulting in a mean of zero for all attributes.
The Covariance Matrix: * Assuming $X$ is an $N \times D$ standardized matrix, the covariance matrix $C$ is defined as: $C = X^{T} X$ * The resulting matrix $C$ has dimensions $D \times D$ . * The entry $C_{ij}$ represents the covariance between attribute $i$ and attribute $j$ . This matrix captures all pairwise correlations across the entire dataset.

Linear Algebra: Eigenvectors and Eigenvalues

Matrix Action on Vectors: * Applying a matrix to a vector (multiplication) generally rotates the vector and changes its length. * For a symmetric matrix $A$ , there exist special vectors called eigenvectors that do not change direction when the matrix is applied.
Eigenvector/Eigenvalue Equation: * A vector $W$ is an eigenvector of matrix $A$ if: $A W = \lambda W$ * Here, $\lambda$ (lambda) is the eigenvalue, which represents the factor by which the eigenvector is stretched or shrunk.
Example Calculation: * Consider the matrix $A = \begin{pmatrix} 2 & -1 \ -1 & 2 \end{pmatrix}$ . * For vector $W_1 = \begin{pmatrix} 1 \ 1 \end{pmatrix}$ : $\begin{pmatrix} 2 & -1 \ -1 & 2 \end{pmatrix} \begin{pmatrix} 1 \ 1 \end{pmatrix} = \begin{pmatrix} 1 \ 1 \end{pmatrix} = 1 \times \begin{pmatrix} 1 \ 1 \end{pmatrix}$ Thus, $W_1 = \begin{pmatrix} 1 \ 1 \end{pmatrix}$ is an eigenvector with eigenvalue $\lambda_1 = 1$ . * For vector $W_2 = \begin{pmatrix} 1 \ -1 \end{pmatrix}$ : $\begin{pmatrix} 2 & -1 \ -1 & 2 \end{pmatrix} \begin{pmatrix} 1 \ -1 \end{pmatrix} = \begin{pmatrix} 3 \ -3 \end{pmatrix} = 3 \times \begin{pmatrix} 1 \ -1 \end{pmatrix}$ Thus, $W_2 = \begin{pmatrix} 1 \ -1 \end{pmatrix}$ is an eigenvector with eigenvalue $\lambda_2 = 3$ .
Properties of Eigenvectors for Symmetric Matrices: * Orthogonality: Any two eigenvectors corresponding to different eigenvalues are orthogonal (their dot product is zero). In the example above: $W_1^{T} W_2 = (1 \times 1) + (1 \times -1) = 0$ . * Frobenius Norm Connection: For a $D \times D$ symmetric matrix, the sum of all squared entries is equal to the sum of the squared eigenvalues: $\sum_{i=1}^{D} \sum_{j=1}^{D} M_{ij}^{2} = \sum_{i=1}^{D} \lambda_i^{2}$ * The term on the left is known as the Frobenius norm of the matrix.

Principal Component Analysis (PCA)

Intuition of Principal Components: * In a multi-dimensional space, there is a single direction along which the data exhibits the highest variance. This is the First Principal Component ( $V_1$ ). * The Second Principal Component ( $V_2$ ) is the direction that maximizes variance among all directions orthogonal to $V_1$ . * This continues until $D$ components are identified for a $D$ -dimensional space.
Variance Maximization: * PCA seeks to find a direction vector that maximizes the variance of the projected data points. * Projecting points onto a line creates a new set of values $x_1, \dots, x_N$ along that line. The variance along that direction is: $\text{Variance} = \frac{\sum_{i=1}^{N} (x_i - \mu)^{2}}{N}$ * The first principal component is the direction that maximizes this scalar value.
Algorithmic Steps for PCA: 1. Standardize the dataset $X$ so that each attribute has a mean of zero. 2. Compute the covariance matrix $C = X^{T} X$ . 3. Solve the eigenvalue problem: $C W_i = \lambda_i W_i$ . 4. Sort the eigenvalues in descending order: \lambda_1 > \lambda_2 > \dots > \lambda_D. 5. Select the top $k$ eigenvectors corresponding to the largest eigenvalues. These eigenvectors are the principal components. 6. Construct the transformation matrix $W$ (of size $D \times k$ ) using these $k$ eigenvectors as columns. 7. Transform the data: $X' = X W$ .
Selecting the Number of Components (k): * The eigenvalues represent the amount of variance explained by each corresponding principal component. * Total variance can be measured by the sum of squared eigenvalues. * A common practice is to choose $k$ such that the cumulative explained variance meets a threshold, such as $90\%$ $\frac{\sum_{i=1}^{k} \lambda_i^{2}}{\sum_{j=1}^{D} \lambda_j^{2}} \geq 0.90$

Kernel Principal Component Analysis (Kernel PCA)

The Dual Problem: * The standard PCA equation is $X^{T} X W_i = \lambda_i W_i$ . * Multiplying by $X$ on the left gives: $X X^{T} (X W_i) = \lambda_i (X W_i)$ . * Letting $Z_i = X W_i$ , we get: $(X X^{T}) Z_i = \lambda_i Z_i$ . * This is an eigenvalue problem for the matrix $K = X X^{T}$ , which has dimensions $N \times N$ .
Similarity and the Kernel Trick: * The entry $K_{ij}$ in the $X X^{T}$ matrix represents the inner product (similarity) between data point $x_i$ and data point $x_j$ . * Standard PCA uses a linear similarity (the dot product). * Kernel PCA replaces this dot product with a kernel function $\kappa(x_i, x_j)$ , which represents similarity in a higher-dimensional engineered space without explicitly computing that space. * Common kernels include the RBF (Radial Basis Function) or Gaussian kernel: $\kappa(x_i, x_j) = e^{-\gamma |x_i - x_j|^{2}}$
Nonlinear Separation: * Linear PCA may fail to separate data that is not linearly separable (e.g., concentric circles or interleaved half-moons). * Kernel PCA can transform these datasets into a new space where they become linearly separable.
Implementation Considerations for Kernel PCA: * Computational Efficiency: Because Kernel PCA involves an $N \times N$ matrix, it can be computationally intensive or infeasible for very large datasets. * Re-centering: The kernel matrix must be re-centered so that every row and column has an average of zero, ensuring the data is standardized in the high-dimensional space. * Test Set Transformation: When applying the transformation to a test set, the statistics (mean-centering parameters) from the training set must be used to ensure consistency.

Experimental Results and Observations

Wine Dataset Experiment: * Initial dimension: 13 attributes. * Top two eigenvalues explained approximately $37\%$ and $19\%$ of the variance respectively, totaling $57\%$ * After projecting from 13D to 2D, a logistic regression classifier achieved high accuracy with clear linear separation between classes.
Nonlinear Datasets: * Two Moons: Standard PCA only rotates the data, maintaining the lack of linear separability. Kernel PCA (RBF kernel with $\gamma = 100$ ) transforms the mooons into a configuration that is linearly separable. * Concentric Circles: Standard PCA results in significant overlap when reduced to 1D. Kernel PCA yields a transformation where the circles are clearly separated, potentially even along a single principal component axis.