Discovering Structure in High-Dimensional Data Through Correlation Explanation

Greg Ver Steeg, Aram Galstyan

Overview

In high-dimensional data, variables are rarely independent. If they were, the system wouldn't be truly high-dimensional—just a collection of unrelated parts. The existence of correlations implies the presence of "hidden common causes." Traditional approaches to finding these causes often fall into two camps: Bayesian Structure Learning, which is mathematically rigorous but computationally expensive, and Neural Networks/Autoencoders, which are scalable but often reliant on "black box" heuristics and specific model assumptions that are hard to justify theoretically.

Correlation Explanation (CorEx) is a novel unsupervised learning method that discovers hierarchical structure in high-dimensional data by finding latent factors that "explain away" correlations between variables. It offers a "middle way": a mathematically principled, information-theoretic approach that is unsupervised, requires no prior model assumptions, and scales linearly with the number of variables. CorEx successfully recovers complex structures in fields ranging from psychology to genomics.

Methods

The core idea of CorEx is to find a set of latent factors $Y$ such that, when you condition on $Y$, the variables in your data $X$ become as independent as possible.

  • Total Correlation (TC): CorEx uses Total Correlation (also known as multi-information) as its primary metric. TC measures the total amount of dependency shared among a group of variables.
  • The Objective: The algorithm maximizes the "explained correlation"—the difference between the TC of the original data and the TC of the data conditioned on the latent factors. Essentially, it looks for the simplest explanation that accounts for the most correlation.
  • Hierarchical Learning: By applying this principle iteratively—using the latent factors of one layer as the input for the next—CorEx builds a tree-like hierarchy of increasingly abstract representations.
  • Optimization: The authors derive a set of self-consistent equations using Lagrangian optimization. This leads to an efficient iterative update rule where the complexity scales linearly with the number of variables ($n$), making it much faster than traditional structure learning methods.

Datasets

The paper evaluates CorEx across several diverse domains:

  • Synthetic Data: Data generated from a hidden tree model to test recovery accuracy as dimensionality increases.
  • Personality Surveys: Data from the "Big Five" personality test (50 questions, ~10,000 respondents).
  • DNA (Genomics): 4,170 Single Nucleotide Polymorphisms (SNPs) from 952 individuals in the Human Genome Diversity Project.
  • Text (20 Newsgroups): A standard NLP benchmark consisting of ~18,000 posts across 20 different topical message boards.

Key Insights and Ideas

  • Model-Free Discovery: CorEx doesn't assume the data follows a specific distribution (like Gaussian) or a specific generative model. It lets the information theory do the talking.
  • Redundancy is the Signal: Unlike methods that might get distracted by high-variance noise, CorEx focuses on redundant information. Uncorrelated variables are essentially ignored, as they provide no "correlation" to explain.
  • Linear Scalability: While many latent tree learning methods scale at $O(n^2)$ to $O(n^5)$, CorEx scales at $O(n)$. This allows it to run on datasets that are orders of magnitude larger than what previous methods could handle.
  • The "Aha" Moment in Psychology: When applied to personality test data, CorEx perfectly reconstructed the "Big Five" traits (Extraversion, Neuroticism, etc.) without any prior knowledge that five categories existed. It outperformed ICA, PCA, and K-means, which all failed to recover the clean 5-factor structure.

Key Results

CorEx performance on synthetic data compared to other methods
  • Synthetic Benchmarks: CorEx maintained near-perfect accuracy in recovering latent clusters even as the number of variables grew to over 2,000, while competing methods like K-means, PCA, and Spectral Clustering saw their performance plummet.
  • Genomics: In the DNA dataset, CorEx automatically discovered latent variables that were nearly perfect predictors of gender, geography (e.g., Oceania, Americas), and specific ethnicities, purely from unsupervised analysis of SNPs.
  • Text Analysis: On the 20 Newsgroups dataset, the hierarchy successfully separated stylistic features (like specific author signatures) from topical content (like "space" vs. "medicine") and organized them into an intuitive tree structure.

Limitations and Future Work

  • Local Optima: Like many iterative optimization schemes, CorEx is guaranteed to converge to a local optimum, but not necessarily the global one.
  • Tree Constraint: In this specific implementation, the authors enforced a constraint where each variable belongs to only one group (a tree structure). While this makes the math tractable and provides a lower bound on Total Correlation, it may not capture systems where variables are influenced by multiple overlapping factors.
  • Domain Specificity (Computer Vision): The authors acknowledge that CorEx might perform poorly on image data compared to Convolutional Neural Networks (CNNs) because it doesn't inherently encode spatial priors (like the fact that adjacent pixels are related).
  • Future Directions: The authors suggest generalizing the approach to allow for non-tree representations and exploring deeper theoretical connections to the "Common Information" problem in information theory.

Summary updated

Abstract

We introduce a method to learn a hierarchy of successively more abstract representations of complex data based on optimizing an information-theoretic objective. Intuitively, the optimization searches for a set of latent factors that best explain the correlations in the data as measured by multivariate mutual information. The method is unsupervised, requires no model assumptions, and scales linearly with the number of variables which makes it an attractive approach for very high dimensional systems. We demonstrate that Correlation Explanation (CorEx) automatically discovers meaningful structure for data from diverse sources including personality tests, DNA, and human language.
BibTeX
@inproceedings{steeg2014discovering,
  author = {Greg Ver Steeg and Aram Galstyan},
  title = {{Discovering Structure in High-Dimensional Data Through Correlation Explanation}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2014},
}
Figure