High Dimensional Mode Hunting Using Pettiest Components Analysis

Tianhao Liu, Daniel Andrés Díaz-Pachón, J. Sunil Rao, Jean-Eudes J. DazardIEEE TPAMI 2023 · DOI

TL;DR

This paper introduces "Pettiest Components Analysis" (PCA), a novel approach to dimensionality reduction that prioritizes components with the smallest variance. They demonstrate that these "pettiest" components are crucial for accurately identifying modes (clusters or "bumps") in high-dimensional data, outperforming traditional principal components analysis, especially for tasks like image reconstruction.

What Problem Does This Paper Address?

Principal Component Analysis (PCA) is a standard technique for reducing the dimensionality of datasets by projecting data onto directions that capture the most variance. The common practice is to discard components with low variance, assuming they contain less information. However, this paper challenges this assumption, arguing that these "low-variance" or "pettiest" components can be surprisingly important, particularly for mode hunting – the task of identifying dense regions or clusters in data. Traditional methods for mode hunting in high dimensions are computationally expensive and can struggle with complex data structures. This paper aims to bridge the gap between dimensionality reduction and effective mode detection by leveraging the information contained in the less-explored pettiest components.

Methods

The core of this paper is the introduction and theoretical justification of "Pettiest Components Analysis" (PCA). Instead of focusing on the principal components (those with the largest variance), this method focuses on the components with the smallest variance. The authors prove that for multivariate normal and Laplace distributions, regions of minimal volume with a fixed probability (B-modes) are optimally found by projecting onto the subspace defined by the pettiest components.

They utilize a modified version of the Patient Rule Induction Method (PRIM), called fastPRIM, which is designed for finding minimal volume B-modes. fastPRIM works by first rotating the data space according to the eigenvectors of the covariance matrix. Then, it iteratively "peels" away regions of the data to isolate the B-mode. The key innovation here is applying fastPRIM not to the principal components, but to the subspace spanned by the pettiest components.

The paper also introduces and uses active information as a metric to quantify the information gain achieved by identifying B-modes. A higher active information value indicates a more concentrated region (smaller volume for a given probability), which the authors link to better mode detection.

Datasets

The primary dataset used for evaluation is the MNIST dataset, a widely used benchmark for handwritten digit recognition. The authors use the training portion of MNIST, which consists of 60,000 images of digits, each represented by 28x28 pixels (784 dimensions). They preprocess the data by centering the images and removing zero-valued pixels (representing white space) to avoid biasing the mode hunting towards these sparse regions.

Key Insights and Ideas

  • Pettiest Components Hold Crucial Information: Contrary to the conventional wisdom of discarding low-variance components, this paper demonstrates that the "pettiest" components are vital for accurate mode detection and can reveal information missed by traditional PCA.
  • Optimal B-Modes Lie in Pettiest Component Subspaces: For certain distributions (multivariate normal and Laplace), the smallest volume regions of a given probability (B-modes) are found by projecting onto the subspace defined by the pettiest components.
  • Active Information as a Metric for Mode Quality: Active information provides a principled way to measure the "quality" of a detected mode, correlating with smaller volumes and thus more informative regions.
  • fastPRIM with Pettiest Components is Highly Effective: The combination of fastPRIM and pettiest components analysis yields significantly smaller and more informative B-modes compared to using principal components or standard PRIM.
  • Mode Hunting for Writing vs. Reading Digits: The paper suggests that principal components are useful for understanding digit variability (like reconstructing digits), while pettiest components are better for understanding digit identity or "platonic ideals" (like generating digits).

Key Results

  • Improved Mode Detection: In simulations with multivariate normal distributions and the MNIST dataset, fastPRIM applied to pettiest components consistently identified B-modes with significantly smaller volumes than those found using principal components.
  • MNIST Reconstruction: Reconstructions of handwritten digits using the modes identified by fastPRIM with pettiest components were visually superior, appearing more "homogeneous" and better defined, especially for digits where the active information difference between principal and pettiest components was large.
  • Quantitative Gains: Table 1 shows that fastPRIM with pettiest components achieved densities that were an order of magnitude higher than other methods. Table 2 indicates that pettiest components led to a tenfold decrease in variance and bias compared to principal components.
  • Active Information Ranking: For the MNIST dataset, the ranking of digits by active information revealed that simpler digits (like '1' and '0') had higher active information, suggesting they are more easily identifiable modes.

Limitations and Future Work

  • Distributional Assumptions: The theoretical proofs for the optimality of B-modes in pettiest component subspaces are based on multivariate normal and Laplace distributions. While the MNIST example shows promise for non-normal data, further generalization is needed.
  • Selection of p': The paper acknowledges that determining the optimal number of pettiest components (p') to select is an open question, likely requiring practitioner input.
  • Spectral Instability: The authors note that spectral instability can be a concern, especially for non-Hermitian matrices, though they mitigated this in their MNIST analysis by removing zero pixels.
  • Future Work: The authors suggest several avenues for future research:
  • Extending the theory to a broader class of unimodal symmetric multivariate distributions.
  • Investigating how marginal distributions can deviate from standard families while maintaining the results.
  • Developing more robust numerical methods for calculating stable eigenvalues for pettiest components.
  • Extending the theory to handle distributions with multiple modes, potentially by partitioning the space.

Summary updated

BibTeX
@article{liu2023high,
  author = {Tianhao Liu and Daniel Andrés Díaz-Pachón and J. Sunil Rao and Jean-Eudes J. Dazard},
  title = {{High Dimensional Mode Hunting Using Pettiest Components Analysis}},
  journal = {IEEE Trans. Pattern Anal. Mach. Intell.},
  year = {2023},
  doi = {10.1109/tpami.2022.3195462},
}
Figure