Multi-view Sparse Laplacian Eigenmaps for nonlinear Spectral Feature Selection

Gaurav Srivastava, Gaurav Srivastava 0012, Mahesh Jangid

TL;DR

Researchers have developed Multi-view Sparse Laplacian Eigenmaps (MSLE), a new feature selection method that handles high-dimensional data by looking at it through multiple "views" simultaneously. By enforcing sparsity constraints, the algorithm can strip away up to 90% of redundant features while maintaining high classification accuracy, significantly improving model interpretability and computational efficiency.

What Problem Does This Paper Address?

In machine learning, we often suffer from the "curse of dimensionality." Datasets like those from wearable sensors or genomic sequences contain hundreds or thousands of variables (features), many of which are noisy or redundant. This leads to three major headaches: overfitting (the model learns noise instead of patterns), computational bloat, and poor interpretability (it’s hard to tell which sensors actually matter).

While traditional spectral methods like Laplacian Eigenmaps (LE) are excellent at capturing the non-linear "shape" of data, they have two major flaws:

  1. Lack of Sparsity: They typically use a combination of all original features to create a low-dimensional embedding, making it impossible to identify which specific features are the most important.
  2. Single-View Limitation: They struggle to integrate data coming from different sources or different mathematical representations (views) of the same phenomenon.

Methods

The authors propose MSLE, which bridges the gap between spectral embedding and sparse feature selection. The approach follows a three-step logic:

  1. Multi-view Integration: Instead of relying on one similarity graph, MSLE constructs a Laplacian matrix for each "view" of the data and integrates them into a single, robust multi-view Laplacian. This ensures the model captures the fundamental structure of the data that is consistent across different perspectives.
  2. Sparsity via $\ell_1$-Regularization: To force the model to pick only the most informative features, the authors add an $\ell_1$-norm penalty to the optimization objective. This "pressure" encourages the weights of irrelevant features to drop to exactly zero.
  3. Iterative Optimization: The resulting problem is non-trivial to solve. The authors employ an accelerated proximal gradient method with a backtracking line search. This allows the algorithm to alternate between updating the sparse coefficients and the graph structure efficiently, ensuring scalability for larger datasets.

Datasets

The study evaluates MSLE using the UCI-HAR (Human Activity Recognition) dataset.

  • The Data: Recordings from 30 individuals using smartphone accelerometers and gyroscopes.
  • The Task: Classifying six activities (Walking, Sitting, Lying Down, etc.).
  • The Scale: 561 features across 10,299 samples.
  • Significance: This is a classic "high-dimensional" benchmark where temporal features often overlap, making it a perfect stress test for feature selection.

Key Insights and Ideas

  • The Power of "Less is More": The most striking insight is the resilience of the data's structure. The researchers found that the "essential" information needed to distinguish human activities is buried in a tiny fraction of the 561 available features.
  • Robustness through Multi-view: By summing Laplacians from different views, the model becomes less susceptible to noise in any single view. If one sensor glitches, the shared structure from other views keeps the feature selection on track.
  • Interpretability as a First-Class Citizen: Unlike "black-box" dimensionality reduction (like standard PCA or t-SNE), MSLE provides a clear mapping back to the original features. This allows engineers to see exactly which sensor axes are driving the classification.

Key Results

The performance of MSLE on the UCI-HAR dataset was impressive, especially when paired with a Support Vector Machine (SVM):

  • Extreme Compression: Even after reducing the feature space by 90%, the SVM maintained an error rate of only 2.72%.
  • The "Sweet Spot": At an 80% reduction in features, the model achieved a peak accuracy of 96.69%.
  • Comparison: Before feature reduction, Linear Discriminant Analysis (LDA) was the top performer at 96.43% accuracy. MSLE allowed other classifiers to match or exceed this performance while using a fraction of the data.
  • Efficiency: The dimensionality reduction process took approximately 6 minutes and 13 seconds on a standard consumer-grade i7 processor, proving the method is viable for real-world applications.

Limitations and Future Work

While MSLE shows great promise, the authors note a few areas for growth:

  • Scalability Constraints: The runtime is currently dependent on the number of views and the size of the dataset. While 6 minutes is reasonable for 10k samples, very large-scale "big data" might require parallel computing optimizations.
  • Domain Diversity: The current study focuses heavily on Activity Recognition. The authors suggest that future work should test MSLE in other complex domains like Social Network Analysis and Natural Language Processing (NLP).
  • Algorithmic Refinement: There is potential to integrate MSLE with other feature selection techniques or deep learning architectures to further boost performance in even noisier environments.

Summary updated

Abstract

The complexity of high-dimensional datasets presents significant challenges for machine learning models, including overfitting, computational complexity, and difficulties in interpreting results. To address these challenges, it is essential to identify an informative subset of features that captures the essential structure of the data. In this study, the authors propose Multi-view Sparse Laplacian Eigenmaps (MSLE) for feature selection, which effectively combines multiple views of the data, enforces sparsity constraints, and employs a scalable optimization algorithm to identify a subset of features that capture the fundamental data structure. MSLE is a graph-based approach that leverages multiple views of the data to construct a more robust and informative representation of high-dimensional data. The method applies sparse eigendecomposition to reduce the dimensionality of the data, yielding a reduced feature set. The optimization problem is solved using an iterative algorithm alternating between updating the sparse coefficients and the Laplacian graph matrix. The sparse coefficients are updated using a soft-thresholding operator, while the graph Laplacian matrix is updated using the normalized graph Laplacian. To evaluate the performance of the MSLE technique, the authors conducted experiments on the UCI-HAR dataset, which comprises 561 features, and reduced the feature space by 10 to 90%. Our results demonstrate that even after reducing the feature space by 90%, the Support Vector Machine (SVM) maintains an error rate of 2.72%. Moreover, the authors observe that the SVM exhibits an accuracy of 96.69% with an 80% reduction in the overall feature space.
BibTeX
@inproceedings{srivastava2023multi,
  author = {Gaurav Srivastava and Gaurav Srivastava and Mahesh Jangid},
  title = {{Multi-view Sparse Laplacian Eigenmaps for nonlinear Spectral Feature Selection}},
  booktitle = {Icsse},
  year = {2023},
  doi = {10.1109/icsse58758.2023.10227143},
}
Figure