Experiments with random projections for machine learning

Dmitriy Fradkin, David MadiganKDD 2003 · DOI

TL;DR

This paper investigates the effectiveness of Random Projections (RP) as a dimensionality reduction technique for supervised machine learning, comparing it against the established Principal Component Analysis (PCA). While RP doesn't outperform PCA in predictive accuracy across tested learning methods, its significant computational advantages make it a compelling alternative for large-scale applications.

What Problem Does This Paper Address?

High-dimensional data presents a significant challenge for many machine learning algorithms due to increased computational complexity and the risk of overfitting. Dimensionality reduction techniques aim to mitigate these issues by projecting data into a lower-dimensional space while preserving important structural properties. Principal Component Analysis (PCA) is a popular choice, but its computational cost can be prohibitive for very large datasets. Random Projections (RP) offer a computationally cheaper alternative with theoretical guarantees on distance preservation, but their practical performance in supervised learning contexts, especially compared to PCA, was not well-established. This paper aims to fill that gap by empirically comparing RP and PCA across various datasets and machine learning algorithms.

Methods

The paper compares two primary dimensionality reduction techniques:

  • Principal Component Analysis (PCA): PCA is described as a method for finding a lower-dimensional approximation of data by projecting it onto the principal components, which are eigenvectors corresponding to the largest eigenvalues of the data's covariance matrix. The paper details the Singular Value Decomposition (SVD) approach to PCA.
  • Random Projections (RP): RP involves projecting data onto a randomly generated lower-dimensional subspace. The paper utilizes a specific method proposed by Achlioptas, where projection matrices have entries drawn from a simple distribution (±1 with probability 0.5). The authors note that while RP theoretically preserves distances, their focus is on preserving separation between points, and they don't strictly adhere to the theoretical bounds for RP dimensionality.

These dimensionality reduction techniques were applied to datasets before training three standard machine learning algorithms: C4.5 decision trees, k-Nearest Neighbors (kNN), and Support Vector Machines (SVM). The experimental setup involved multiple train/test splits and normalization of data.

Datasets

The experiments were conducted on five real-world datasets:

  • Ionosphere: A dataset with 351 instances and 34 attributes.
  • Colon: A dataset with 62 instances and 2000 attributes.
  • Leukemia: A dataset with 72 instances and 3571 attributes.
  • Spam (Spambase): A dataset with 4601 instances and 57 attributes.
  • Ads (Internet Ads): A dataset with 3279 instances and 1554 attributes. The paper notes that three attributes with missing values were removed from the original Ads dataset.

These datasets were chosen to represent different "shapes" in terms of the number of instances versus attributes, offering a diverse testbed for evaluating the dimensionality reduction methods.

Key Insights and Ideas

  • Computational Advantage of RP: The most significant takeaway is RP's substantial computational advantage over PCA, making it a viable option for scenarios where PCA's computational cost is prohibitive.
  • Predictive Performance Trade-off: While RP is computationally cheaper, PCA generally yields better predictive accuracy across the tested learning algorithms.
  • Learning Method Sensitivity: The performance difference between PCA and RP is highly dependent on the learning algorithm used. kNN methods showed the least degradation with dimensionality reduction, and their performance with RP approached that of the original space relatively quickly.
  • Decision Trees and RP Don't Mix Well: Decision trees (C4.5) performed poorly with RP, likely due to their reliance on axis-parallel boundaries and sensitivity to attribute transformations.
  • SVMs Benefit from RP: SVMs showed improvement with increasing projection dimensionality when using RP, and their performance with RP improved significantly compared to decision trees.
  • Theoretical vs. Practical Bounds: The paper hints that the theoretical bounds on the required dimensionality for RP might be conservative, as good results were observed even when projecting to dimensions lower than theoretically suggested.

Key Results

  • Accuracy: In most cases, PCA-reduced data resulted in higher accuracy than RP-reduced data for C4.5, kNN, and SVM. For example, on the Ionosphere dataset, PCA achieved accuracies in the mid-90s for most learning methods, while RP was typically in the high-80s.
  • kNN Robustness: kNN methods were the most robust to dimensionality reduction, with their performance degrading less than C4.5 or SVM. In some instances (Ionosphere, Ads), PCA projection even improved kNN accuracy.
  • SVM Improvement: SVM performance generally improved with increasing projection dimensions for both PCA and RP, with RP gradually catching up to PCA.
  • Support Vectors: RP generally led to a higher number of support vectors for SVMs compared to PCA, suggesting that RP-generated data might be more complex to separate. However, as projection dimensionality approached the original, the number of support vectors converged.
  • C4.5 Performance: C4.5 performed well with low-dimensional PCA projections but deteriorated with further reduction or with RP.

Limitations and Future Work

  • Predictive Performance: The authors acknowledge that RP predictively underperforms PCA.
  • Future Work: The paper suggests that RP's predictive performance improves with increasing dimensionality, particularly when combined with appropriate learning methods. Further experimentation is encouraged to explore the full potential of RP in supervised learning contexts, especially with learning methods that are less sensitive to attribute transformations. The authors also note that RP seems best suited for Nearest Neighbor methods and combines well with SVM.

Summary updated

BibTeX
@inproceedings{fradkin2003experiments,
  author = {Dmitriy Fradkin and David Madigan},
  title = {{Experiments with random projections for machine learning}},
  booktitle = {ACM SIGKDD Conference on Knowledge Discovery and Data Mining},
  year = {2003},
  doi = {10.1145/956750.956812},
}
Figure