Introduction to Machine Learning

by Albert Major

Dimensionality Reduction

1. Introduction to Dimensionality Reduction

• Definition: The process of transforming data from a high-dimensional space (D dimensions/features) to a lower-dimensional space (K dimensions), where K ≪ D.
• Goal: To find a mapping function that compresses data into a latent space (or embedding space) while preserving the most critical structures and information.
• Examples:
  • Compressing 784 pixels of MNIST images (28x28) into 2 dimensions.
  • Reducing 10,000 gene expressions into a few key genetic markers.
  • Summarizing 300 customer behavior features into 3 behavioral axes.

2. Motivations: Why Reduce Dimensions?

A. The Curse of Dimensionality

• "Fat" Data Problem: Machine learning struggles when there are many features (D) but limited samples (N). The ideal state is "thin" data (N ≫ D).
• Exponential Growth: As dimensions increase, the volume of the space grows exponentially. You need exponentially more data points to cover the space effectively.
• Counter-Intuitive Geometry:
  • In high dimensions, data space becomes "spiky."
  • Mass Concentration: The volume of a hypersphere inscribed in a hypercube approaches zero as dimensions increase. Almost all data points concentrate on the "edges" or boundaries of the space, leaving the center empty.
• Loss of Distance Meaning:
  • In high dimensions, the distance to the nearest neighbor (d_min) and the farthest neighbor (d_max) converge.
  • The ratio of distances approaches zero, making all points appear equidistant.
  • Consequence: Algorithms relying on distance (like k-Nearest Neighbors) fail because "closeness" loses its meaning.

B. Preventing Overfitting

• Generalization Gap: The difference between model performance on training data versus test data.
• High-dimensional data makes it easy to perfectly fit (memorize) training data, increasing the generalization gap.
• Reducing features reduces model complexity (fewer parameters/weights), forcing the model to learn general patterns rather than noise.

C. Computational Complexity

• Many algorithms have complexity scaling with D.
  • Example: Linear regression involves matrix inversion (O(D³)). Doubling features can increase computation time by 10x.
• Reducing D lowers computational cost and cloud computing fees.

D. Data Visualization

• Humans cannot visually interpret data beyond 3 dimensions.
• Reducing data to 2D or 3D allows for visual inspection of clusters and patterns.

3. Principal Component Analysis (PCA)

• Type: Linear transformation.
• Core Concept: Variance = Information.
  • PCA rotates the coordinate system to align with directions where data varies the most.
  • Principal Component 1 (PC1): The direction capturing the maximum variance.
  • PC2: Orthogonal (perpendicular) to PC1, capturing the next highest variance.
• Steps to Perform PCA:
  1. Standardization: Scale data so all features have a mean of 0 and standard deviation of 1.
     • Why? Without this, features with large scales (e.g., weight in grams) dominate features with small scales (e.g., height in meters), biasing the result.
  2. Center Data: Subtract the mean vector (ensure data is centered at the origin).
  3. Covariance Matrix: Calculate the D × D matrix representing correlations between all pairs of features.
  4. Eigenvalue Decomposition: Decompose the covariance matrix into:
     • Eigenvectors: The directions of the new axes (Principal Components).
     • Eigenvalues (λ): The magnitude of variance explained by each eigenvector.
  5. Sort & Select: Sort eigenvalues from high to low. Keep the top K eigenvectors that explain the most variance.
  6. Project: Map original data onto these selected vectors using a dot product.
• Selecting K (Elbow Method): Plot cumulative explained variance. Stop when variance reaches a threshold (e.g., 90-95%).
• Limitation: PCA assumes linear relationships and orthogonality. It cannot capture non-linear structures.

4. Non-Negative Matrix Factorization (NMF)

• Type: Part-based, interpretable decomposition.
• Constraint: Input matrix V must contain only positive numbers (e.g., RGB images, word counts).
• Mechanism: Decomposes input V (N × D) into two non-negative matrices:
  1. W (Parts/Basis Matrix): Represents latent "parts" or features (e.g., nose, eyes in face data; topics in text).
  2. H (Weights/Activation Matrix): Represents the contribution of each part to the original samples.
• Interpretability: Unlike PCA (which allows negative values and cancellations), NMF is additive. It builds data by adding parts together, making it semantically meaningful to humans.
• Algorithm:
  • Minimizes reconstruction error (Frobenius norm) between original V and approximation W × H.
  • Uses iterative updates (non-convex optimization).
• Limitations:
  • Requires positive data (must normalize inputs like 0-1 scaling).
  • Non-Convex: Has many local minima; different runs yield different results.

5. t-Distributed Stochastic Neighbor Embedding (t-SNE)

• Type: Non-linear dimensionality reduction.
• Primary Use: Visualization only (not for feature extraction/modeling).
• Goal: Preserves local pairwise similarities. If two points are neighbors in high dimensions, they should be neighbors in low dimensions.
• Mechanism:
  1. High-Dimensional Space: Calculates probability (P_ij) of point j being a neighbor of i using a Gaussian distribution.
  2. Low-Dimensional Space: Calculates probability (Q_ij) of points being neighbors using a Student's t-distribution (degree of freedom = 1).
     • Why t-distribution? It has "heavier tails" than Gaussian, which prevents the "crowding problem" and better preserves local structure.
  3. Optimization: Minimizes the Kullback-Leibler (KL) Divergence (difference) between probabilities P and Q.
• Key Hyperparameter: Perplexity
  • Controls the effective number of neighbors.
  • Low Perplexity (5-30): Captures local structure (small clusters).
  • High Perplexity (50-100): Captures global structure (broad shapes).
• Limitations:
  • Non-deterministic: Results change every time (unless initialized with PCA).
  • Global Distance is Meaningless: The distance between clusters in the visualization does not imply actual distance or similarity.
  • Computationally Expensive: Scales quadratically with samples (O(N²)). Slow on large datasets.