Alpha-Beta Divergences Discover Micro and Macro Structures in Data

Karthik S. Narayan, Ali Punjani, Pieter AbbeelICML 2015

Dimensionality reduction techniques like t-SNE are essential for visualizing high-dimensional data, but they often act as a "black box." Most methods rely on a fixed divergence measure—usually the Kullback-Leibler (KL) divergence—which offers little flexibility. If a researcher wants to see how specific species of birds relate to one another (micro-structure) versus how birds as a whole relate to mammals (macro-structure), they are often stuck with whatever the default settings produce. Furthermore, SNE-based methods have historically struggled with scale, often failing or taking days to process millions of data points.

Presented at ICML 2015 by researchers from UC Berkeley and the University of Toronto, AB-SNE introduces a significant evolution of the popular t-SNE algorithm. By replacing the standard KL-divergence with the more flexible Alpha-Beta (AB) divergence, the authors provide an intuitive "tuning knob" for data visualization. This allows researchers to choose whether they want to see the "big picture" or the "fine details" of their data, all while running up to 20x faster than previous state-of-the-art implementations.

Methods: The Alpha-Beta Tuning Knob

The core innovation of AB-SNE is the application of the AB-divergence, which introduces two key hyperparameters, $\alpha$ and $\beta$. By analyzing the gradient updates of the algorithm, the authors derived a theoretical "recipe" for these parameters to control clustering behavior:

  • $\alpha$ (Local Control): Decreasing $\alpha$ below 1 emphasizes local repulsive forces, leading to tighter, more fine-grained "micro" clusters.
  • $\lambda = \alpha + \beta$ (Global Control): Setting $\lambda < 1$ increases the separation between major groups, revealing "macro" structures. Conversely, setting $\lambda > 1$ helps highlight "boundary" instances—points that sit between classes and are easily confused.
Effects of varying alpha and lambda on MNIST and CIFAR datasets.

To make this practical for massive datasets, the team implemented a parallelized version using Barnes-Hut approximations for both CPU and GPU. Their GPU implementation utilizes 13 specialized kernels to handle tree-based structures and gradient calculations efficiently, even when the dataset is too large to fit entirely in GPU memory.

Key Insights and Qualitative Discoveries

The authors evaluated AB-SNE across 10 datasets, ranging from standard benchmarks like MNIST and CIFAR-10 to massive scientific sets. A major takeaway is the power of blending divergences: minimizing a single divergence isn't enough, but blending $\alpha$ and $\beta$ allows for the discovery of hierarchical structures. Furthermore, these settings proved largely dataset-agnostic, meaning researchers can rely on theoretical intuition (e.g., $\alpha < 1$ for micro-structures) rather than tedious grid searches for every new dataset.

Qualitatively, AB-SNE excels at revealing smooth visual transitions and fine-grained sub-categories. When applied to 1.2 million images from the ILSVRC 2012 (ImageNet) dataset, AB-SNE successfully separated specific species—like Toucans versus Hummingbirds—while maintaining the broader "Bird" category. It also captured visual similarities that standard labels might miss, such as a cluster where "perched birds" smoothly transitioned into "swinging monkeys."

AB-SNE visualization of ImageNet revealing fine-grained bird species and visual transitions.

Performance and Scalability

Beyond qualitative improvements, AB-SNE delivers massive performance gains:

  • Speedup: The GPU implementation is 20x faster than the fastest previously published SNE code (the Fast Multipole Method).
  • Scalability: The authors successfully visualized the 11-million-point HIGGS physics dataset in about an hour. At the time of publication, this represented the largest SNE-based visualization ever achieved, a feat previously considered unreachable.

Limitations and Future Work

While highly effective, the authors note a few limitations. First, while the algorithm produced clear clusters in the massive HIGGS and SUSY physics datasets, these clusters did not perfectly align with the standard "Signal vs. Background" labels. Further collaboration with physicists is needed to understand the latent physical properties these clusters represent.

Additionally, for massive datasets (like the 11M instance HIGGS set), the implementation relies on swapping batches between CPU and GPU memory. While efficient, this remains a bottleneck compared to datasets that fit entirely in VRAM. Finally, while the parameter "recipe" is robust, extreme values of $\alpha$ and $\beta$ can still lead to unstable optimizations, a common trait in non-convex gradient descent problems.

Summary updated

BibTeX
@inproceedings{narayan2015alpha,
  author = {Karthik S. Narayan and Ali Punjani and Pieter Abbeel},
  title = {{Alpha-Beta Divergences Discover Micro and Macro Structures in Data}},
  booktitle = {International Conference on Machine Learning},
  year = {2015},
}
Figure