Supervised Exponential Family Principal Component Analysis via Convex Optimization

Yuhong GuoNeurIPS 2008 · OpenReview

TL;DR

This paper introduces SEPCA (Supervised Exponential Family Principal Component Analysis), a dimensionality reduction technique that leverages label information and handles non-Gaussian data. Unlike previous methods that often get trapped in suboptimal "local optima," the authors reformulate the problem into a convex optimization framework. This guarantees a globally optimal solution, resulting in more reliable and accurate data embeddings.

What Problem Does This Paper Address?

Principal Component Analysis (PCA) is the "Swiss Army knife" of data science for reducing dimensions, but it suffers from two major weaknesses:

  1. It’s Unsupervised: PCA ignores categorical labels (like "cat" vs. "dog"). It simply looks for the directions of maximum variance, which might just be irrelevant noise.
  2. The Gaussian Trap: Standard PCA assumes data follows a Gaussian (Normal) distribution. If your data consists of binary values, counts, or is highly skewed, PCA often fails to capture the true underlying structure.

While "Supervised" and "Exponential Family" (non-Gaussian) versions of PCA exist, they typically rely on Expectation-Maximization (EM) algorithms. EM is notorious for getting stuck in local optima—meaning the algorithm might yield a different, potentially worse result every time it runs. This paper aims to provide a supervised, non-Gaussian method that is mathematically guaranteed to find the best possible solution through convex optimization.

Methods

The authors propose SEPCA, which stands out through three key technical innovations:

  • Convex Reformulation: By applying Fenchel Duality and exploiting eigenvector properties, the authors transform a non-convex likelihood maximization problem into a convex-concave min-max problem. This ensures that the optimization landscape has no "false peaks."
  • Sample-Based Approximation: Instead of forcing the user to choose a specific distribution (like Poisson or Bernoulli), they use a data-driven approximation of the exponential family's log-partition function. This makes the model "distribution-agnostic" and allows the method to be kernelized to handle non-linear relationships in the data.
  • Bundle Method & Coordinate Descent: To solve the resulting complex optimization, they use a "subgradient bundle method." To ensure it scales to larger datasets, they implement a coordinate descent procedure that breaks the problem into smaller, manageable chunks.

Datasets

The authors evaluated SEPCA against four competitors (SDR_GLM, SPPCA, LDA, and MVU) using:

  • Synthetic Data: Four Gaussian clusters (to test non-Gaussian robustness) and concentric circles (to test non-linear/kernel performance).
  • Real-World Data: Face image datasets (Yale & YaleB), high-dimensional gene expression data (11 Tumor), handwritten digits (Usps3456), and large-scale text documents (Newsgroup).

Key Insights and Ideas

  • Labels are Filters: The core insight is that labels are not just for classification; they act as a filter to suppress noise in high-dimensional space, helping the model focus only on the features that define the data's categories.
  • Global Optimality Matters: The paper demonstrates that an optimization process that gets stuck in local optima (like EM) will consistently underperform a globally optimal convex model, regardless of the underlying theory.
  • Automatic Kernelization: One of the most elegant parts of the paper is that their sample-based approximation naturally leads to a kernel matrix. This means the transition from linear to non-linear dimensionality reduction happens almost for free.

Key Results

  • Robustness to Non-Linearity: In synthetic tests designed to challenge linear assumptions, SEPCA demonstrated a clear advantage. When tested on non-linear concentric circles, SEPCA successfully separated the classes, whereas standard probabilistic PCA variants and other baselines failed to capture the structure.
SEPCA successfully separates non-linear concentric circles compared to baseline methods.
  • Superior Accuracy on Real Data: SEPCA consistently outperformed competing dimensionality reduction techniques across multiple real-world datasets. On the high-dimensional "11 Tumor" dataset, SEPCA achieved 88.9% accuracy, dwarfing the next best supervised method (SDR_GLM at 63.5%).
Classification accuracy across various real-world datasets, highlighting SEPCA's strong performance.
  • Text Processing: On the high-dimensional Newsgroup dataset, SEPCA significantly outperformed other probabilistic methods, proving its effectiveness in sparse, high-dimensional settings where traditional PCA struggles.

Limitations and Future Work

  • Computational Complexity: Even with coordinate descent, the dual optimization scales quadratically relative to the number of samples. This makes it excellent for high-dimensional data with fewer samples (like genomics), but potentially slow for "Big Data" with millions of rows.
  • Convergence Guarantees: While the main problem is convex, the authors note that coordinate descent on nondifferentiable objectives isn't strictly guaranteed to reach the global minimum in all theoretical cases, though it performed exceptionally well empirically.
  • Future Directions: The authors suggest that the projection method used for new testing data could be further refined to better integrate with other supervised dimensionality reduction frameworks.

Summary updated

Abstract

Recently, supervised dimensionality reduction has been gaining attention, owing to the realization that data labels are often available and strongly suggest important underlying structures in the data. In this paper, we present a novel convex supervised dimensionality reduction approach based on exponential family PCA and provide a simple but novel form to project new testing data into the embedded space. This convex approach successfully avoids the local optima of the EM learning. Moreover, by introducing a sample-based multinomial approximation to exponential family models, it avoids the limitation of the prevailing Gaussian assumptions of standard PCA, and produces a kernelized formulation for nonlinear supervised dimensionality reduction. A training algorithm is then devised based on a subgradient bundle method, whose scalability can be gained through a coordinate descent procedure. The advantage of our global optimization approach is demonstrated by empirical results over both synthetic and real data.
BibTeX
@inproceedings{guo2008supervised,
  author = {Yuhong Guo},
  title = {{Supervised Exponential Family Principal Component Analysis via Convex Optimization}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2008},
  url = {https://openreview.net/forum?id=SkZRSuZd-H},
}
Figure