Dimensionality Reduction Study Notes

Dimensionality Reduction

Overview of Content
  • Dimensionality Reduction
  • Filtering-based feature selection
  • Information gain filtering
  • Wrapper-based feature selection
  • Forward selection
  • Backward elimination
  • Recursive feature elimination (RFE)
  • Principal Components Analysis (PCA)
Definition
  • Dimensionality Reduction: The process involves condensing dataset information while preserving essential characteristics. The primary objective is to reduce algorithmic complexity and enhance model performance by removing redundant or irrelevant features without significant information loss.
    • It compares dimensionality reduction with feature selection: feature selection is akin to projecting the feature space to a lower-dimensional subspace perpendicular to removed features while dimensionality reduction can involve other types of projections such as PCA that represent data using linear combinations of original features.
Conceptual Understanding of Dimensionality
  • Dimensionality: Refers to the number of features or attributes in the dataset.
    • Datasets can have a very large number of features.
    • Example in text corpus: Each distinct word can be a feature (bag of words model).
    • Example in image datasets: Each of the 1024 x 768 pixels can be treated as a feature.
    • Goal: Reduce the number of features while minimizing information loss to ensure good performance in clustering, classification, etc.
Importance of Dimensionality Reduction
  • The feature space may be sparsely populated. For example, in a text corpus, individual words may appear in a small subset of documents, leading to:
    • Poor performance of ML models on sparse feature spaces.
    • Models rely on statistical counts of observations in various regions of feature space.
    • As dimensionality increases, there are fewer observations per region, leading to the Curse of Dimensionality: Training examples needed increase exponentially with dimensionality.
    • Other reasons include the presence of irrelevant or redundant features (highly correlated features) and the desire to visualize high-dimensional data.

Methods of Dimensionality Reduction

Overview of Methods
Two Broad Categories

  1. Feature Selection:

    • Selecting a subset of features from the original set.
    • Example: For spam email classification, differentiate between time of day of the email and the number of spam-words.

  2. Feature Extraction:

    • Define a new set of features smaller than the original set.
    • Example: Given marks in 8 subjects, total variation may be captured through 3 new dimensions – Science, Social Science, Arts.
Supervised vs Unsupervised Feature Selection
  • Supervised Methods: Utilize both feature values and class labels of data points.
    • Techniques are focused on selecting a subset of original features based on scores assigned to each feature.
  • Unsupervised Methods: Utilize only feature values, not class labels.
    • These methods project the data points onto lower-dimensional space while retaining maximum information (e.g., PCA minimizes reconstruction error).

Feature Selection Approach

Filtering-based Feature Selection
  • All features are initially evaluated and filtered down to a subset.
Wrapper-based Feature Selection
  • Involves calling a learning method multiple times to help select features based on their performance in constructing a predictive model.
State Space for Feature Selection
  • State: Set of features.
  • Start State: Empty (in forward selection) or full (in backward elimination).
  • Operators: Add/subtract features based on scoring using training or validation accuracy.
Forward and Backward Selection
  • Forward Selection
    • Initialize an empty set and iteratively add features that improve model score until no further improvements can be made.
  • Backward Elimination
    • Start with all features and iteratively remove the least significant ones based on performance evaluation until score decreases.
Recursive Feature Elimination (RFE)
  • Train a model on all features.
  • Rank features by coefficient magnitude.
  • Remove the lowest-ranked features iteratively until model performance decreases.

Principal Component Analysis (PCA)

Overview
  • PCA: A fundamental technique for extracting the most informative features and transforming high-dimensional data into a manageable low-dimensional form.
    • It identifies orthogonal axes called principal components (PCs) capturing maximum variance upon projection.
PCA Algorithm
  1. Compute the mean of data points.
  2. Mean center the data: calculate $x_i - ar{x}$
  3. Compute covariance matrix: S = rac{1}{n} (X - ar{X})^T (X - ar{X})
  4. Perform eigenvalue decomposition: S=Vextdiag(exteigenvalues)VTS = V ext{diag}( ext{eigenvalues}) V^T
  5. Select top $m$ eigenvectors corresponding to the largest eigenvalues (these are the principal components).
  6. Create the projection matrix: U=[v1,v2,…,vm]U = [v_1, v_2, …, v_m]
  7. Project data onto lower-dimensional space: Y=UTXY = U^T X
Key Properties of PCA
  • Dimensionality reduction implies some degree of information loss; PCA aims to minimize this by managing reconstruction error effectively.
  • Each principal component accounts for as much of the data variability possible, ensuring that dimensions are orthogonal, thus uncorrelated.
  • The number of principal components can be chosen based on desired variance retention (e.g., 90% or 95%).
Covariance and Variance
  • Covariance: A measure of how two variables change together; it can be positive or negative depending on the correlation direction.
  • Covariance Matrix: A $M imes M$ matrix where each entry $c_{ij}$ measures the covariance between features $i$ and $j$.
Geometric Interpretation and Eigenvectors
  • PCA involves rotating the coordinate system to align the axes with maximum data variation; this involves the eigenvalues and eigenvectors of the covariance matrix.
  • Eigenvectors correspond to directions of maximum variance; eigenvalues indicate the amount of variance along their associated eigenvector direction.