Stratification Learning: Detecting Mixed Density and Dimensionality in High Dimensional Point Clouds

Gloria Haro, Gregory Randall, Guillermo SapiroNeurIPS 2006 · OpenReview

Standard manifold learning assumes that high-dimensional data lies on a single, uniform low-dimensional surface. This paper introduces "stratification learning," a framework using a Poisson Mixture Model (PMM) to simultaneously cluster data points and estimate the varying dimensions and densities of multiple underlying structures within a single point cloud.

The Problem: Beyond Single Manifolds

In fields ranging from neuroscience to image analysis, researchers often work with "point clouds"—collections of data points embedded in high-dimensional spaces. Traditional manifold learning techniques, such as Isomap or Locally Linear Embedding (LLE), typically operate under a restrictive assumption: that these points are sampled from a single, unique manifold.

However, real-world data is rarely that simple. It is often a stratification: a collection of multiple manifolds that may have different intrinsic dimensions (e.g., a 1D curve intersecting a 2D surface) and different sampling densities. Existing methods usually attempt to solve this in two disconnected steps: first estimating local dimensionality for every point, and then clustering those estimates. This two-step approach is often noisy and frequently fails to capture the global structure. The authors aim to bridge this gap by treating clustering and dimensionality estimation as a single, unified optimization problem.

Methodology: The Poisson Mixture Model

The authors build upon the work of Levina and Bickel, who modeled the number of points falling into a small neighborhood as a Poisson process to estimate local dimension.

The core contribution of this paper is the introduction of the Poisson Mixture Model (PMM). Instead of calculating a dimension for each point independently, the authors model the entire dataset as a mixture of $J$ different Poisson distributions. Each "expert" in the mixture represents a cluster with its own distinct parameters:

  • Intrinsic Dimension ($m$): The "true" dimensionality of that specific manifold.
  • Sampling Density ($\theta$): How densely the points are packed within that manifold.
  • Mixture Coefficient ($\pi$): The proportion of the total dataset belonging to that cluster.

To solve this, they employ the Expectation-Maximization (EM) algorithm. In the E-step, the model calculates the probability (soft assignment) of each point belonging to each of the $J$ clusters. In the M-step, it updates the dimension and density parameters to best fit the points assigned to them. This iterative process allows the clustering to be informed by the dimensionality, and vice versa.

Experimental Validation

The researchers evaluated their PMM approach across several types of data, ranging from synthetic shapes to real-world video sequences.

Synthetic Accuracy: Swiss Roll and Line

A primary test involved a "Swiss Roll" (a 2D manifold) and a 1D line embedded together in 3D space, tested both with and without Gaussian noise.

Comparison of PMM and LD+IB on the Swiss Roll and Line dataset

On this mixture, the PMM perfectly separated the two structures, accurately estimating their dimensions as approximately 2.01 and 1.00, respectively. As shown in the figure above, even with high noise introduced (bottom row), PMM maintained clear separation where traditional two-step methods (like LD+IB) failed to cleanly isolate the structures.

Real-World Applications

  • MNIST Database: The model successfully separated handwritten '1's from '2's. Interestingly, it found that '1's have a lower intrinsic dimension (~8.5) compared to '2's (~12.8), reflecting the relative simplicity of drawing a straight line versus a curved shape.
  • Natural Image Patches: Using $3 \times 3$ pixel patches from images of houses and biological tissues, the model successfully distinguished between "flat" regions, edges, and complex textures based on their intrinsic geometry.
  • Human Activity Video: The PMM successfully clustered 1,673 video frames into four distinct activity classes (standing, walking, jumping, and waving) based purely on the pixel-cloud's intrinsic dimensionality and density. This demonstrates significant potential for automated video analysis without the need for complex, hand-crafted feature engineering.

Key Insights

  • Simultaneity is Key: By performing clustering and estimation at the same time, the model is significantly more robust. A cluster provides more collective "evidence" for a dimensionality estimate than a single point's isolated neighborhood ever could.
  • Density Matters: The model doesn't just look at the "shape" (dimension) but also the "concentration" (density). This allows it to separate two different 1D lines if one is sampled much more heavily than the other.
  • Self-Correcting Model Selection: The authors found that if they set the number of desired classes ($J$) higher than the actual number of manifolds, the algorithm naturally leaves the extra classes nearly empty or gives them redundant parameters. This effectively allows the model to "discover" the true number of structures.
  • Noise as Dimension: An interesting observation is that as noise increases, the estimated intrinsic dimension also increases. This occurs because noise "fills" the surrounding high-dimensional space, making a 1D line look more like a 2D or 3D "tube."

Limitations and Future Directions

While powerful, the proposed framework has areas for improvement:

  • Boundary Effects: Errors typically occur at the boundaries or intersections of manifolds, where the local neighborhood assumptions of the Poisson process start to break down.
  • Euclidean Bias: The current model relies on Euclidean distance. Using metrics more adapted to the specific data type (like geodesic distances) could yield better results.
  • Geometric Shapes: The counting process currently uses spherical "balls." The authors propose using ellipsoids in future iterations to better capture the directional geometry of manifolds.
  • Spatial Regularization: For image tasks, the model currently treats pixels as independent points. Adding spatial constraints—acknowledging that a pixel is highly likely to belong to the same cluster as its immediate neighbor—is a key area for future research.

Summary updated

Abstract

The study of point cloud data sampled from a stratification, a collection of manifolds with possible different dimensions, is pursued in this paper. We present a technique for simultaneously soft clustering and estimating the mixed dimensionality and density of such structures. The framework is based on a maximum likelihood estimation of a Poisson mixture model. The presentation of the approach is completed with artificial and real examples demonstrating the importance of extending manifold learning to stratification learning.
BibTeX
@inproceedings{haro2006stratification,
  author = {Gloria Haro and Gregory Randall and Guillermo Sapiro},
  title = {{Stratification Learning: Detecting Mixed Density and Dimensionality in High Dimensional Point Clouds}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2006},
  url = {https://openreview.net/forum?id=rJZJivWd-H},
}
Figure