Bivariate Causal Discovery for Categorical Data via Classification with Optimal Label Permutation

Yang Ni

In the world of data science, we are often good at finding correlations but struggle with the "chicken or the egg" problem of causality. If we have two variables, $X$ and $Y$, how do we know if $X$ causes $Y$ or vice versa? While we have robust tools for continuous data (like height or temperature), categorical data—where values are qualitative labels like "Type of Sport" or "Eye Color"—has remained a much tougher nut to crack.

TL;DR

Researchers have developed a new method called COLP (Classification with Optimal Label Permutation) that identifies causal directions in categorical data by finding the most "parsimonious" (simplest) way to order labels. By treating the arrangement of categories as a learnable parameter, the model breaks the symmetry between cause and effect, allowing for provably accurate causal discovery.

What Problem Does This Paper Address?

Most causal discovery algorithms rely on the quantitative nature of data. For example, in the model $Y = f(X) + \text{noise}$, we can look at the properties of the "noise" to see which direction fits better. But for categorical data, the "order" of values is arbitrary. Is "Boxing" greater than "Volleyball"? Is "Blue eyes" less than "Brown eyes"?

Because these labels have no inherent magnitude, standard structural equations don't work well. Existing methods for categorical data often require very specific conditions or are "non-identifiable"—meaning the math says $X \to Y$ and $Y \to X$ look exactly the same, leaving us guessing. The challenge is to find a way to "break the symmetry" and prove that one direction is more likely than the other.

Methods

The author, Yang Ni, proposes a model called COLP. The core innovation is a hybrid between two standard statistical tools:

  1. Multinomial Regression: Flexible but too complex (too many parameters), making it impossible to distinguish cause from effect.
  2. Ordinal Regression: Simple and efficient, but it requires the data to have a natural order (like "Low, Medium, High").

COLP bridges this gap. It assumes that even if a variable is nominal (no natural order), there exists an optimal permutation of those labels that makes the relationship look like an ordinal one.

Diagram illustrating how the parsimonious COLP models are nested within the broader saturated multinomial model.

The algorithm treats the label order as a parameter to be optimized. To find the causal direction, the system:

  • Calculates the maximum likelihood of the model $X \to Y$ (finding the best label order for $Y$).
  • Calculates the maximum likelihood of the model $Y \to X$ (finding the best label order for $X$).
  • Compares the two. Because the model is parsimonious (it uses fewer parameters than a full joint distribution), the "true" causal direction will typically yield a significantly higher likelihood.

For datasets with many categories, where checking every possible order is impossible, the paper introduces a Greedy Search algorithm to efficiently find the best permutation.

Datasets

The method was validated using a mix of synthetic and real-world data:

  • Synthetic Data: Simulations with varying sample sizes and category counts, including tests with "hidden confounders" (unseen third variables influencing both $X$ and $Y$).
  • Pittsburgh Bridges: A classic dataset where the goal is to predict bridge properties (like material or length) from their purpose or era.
  • Abalone Dataset: Predicting physical measurements from the sex of the shellfish.
  • Tübingen Cause-Effect Pairs: A famous benchmark for causal discovery.
  • New Benchmark: The author introduced a new "Categorical Cause-Effect Pairs" dataset containing 33 pairs curated from R packages, where the causal direction is known from context (e.g., "treatment" causes "outcome").

Key Insights and Ideas

  • Parsimony is the Key to Truth: The "aha moment" is that a saturated model (one that can fit anything) is useless for causality. By forcing the model to be simpler (parsimonious), we create a situation where only the true causal direction "fits" well.
  • Latent Order Matters: Even if categories seem random, they often have a functional order relative to their cause. For example, if you are predicting "Sport Choice" based on "Height," an order of Gymnastics < Boxing < Volleyball emerges naturally because of the average height of athletes in those sports.
  • Robustness to Noise: Surprisingly, the model performed well even when hidden confounders were present, suggesting that the "simplest fit" principle is quite resilient.

Key Results

  • Superior Accuracy: On synthetic and benchmark datasets, COLP consistently outperforms existing state-of-the-art methods. For instance, on the new categorical benchmark, COLP correctly identified the causal direction 70% of the time, beating methods like HCR (61%) and ECI (52%).
Accuracy comparison showing COLP (both exhaustive and greedy search) outperforming the HCR method across various sample sizes.
  • Real-World Success: In the Pittsburgh Bridges dataset, COLP correctly identified all four causal pairs, whereas other methods missed one or two.
  • The "Middle Shelf" Discovery: In a dataset about cereal placement, COLP automatically discovered that shoppers prefer the middle shelf over the top or bottom—identifying a non-obvious "optimal ordering" that improved prediction.

Limitations and Future Work

While powerful, the paper notes a few areas for growth:

  • Bivariate Only: Currently, the model only looks at pairs of variables ($X$ and $Y$). Real-world systems are often multivariate webs.
  • No Unmeasured Confounders: The mathematical proof assumes there are no hidden variables, though empirical tests showed the model is somewhat robust when this assumption is violated.
  • Search Complexity: Even with a greedy search, very large sets of categories could become computationally expensive.

The author has released an R package (COLP) to allow other researchers to apply this "permutation-based" logic to their own categorical datasets.

Summary updated

Abstract

Causal discovery for quantitative data has been extensively studied but less is known for categorical data. We propose a novel causal model for categorical data based on a new classification model, termed classification with optimal label permutation (COLP). By design, COLP is a parsimonious classifier, which gives rise to a provably identifiable causal model. A simple learning algorithm via comparing likelihood functions of causal and anti-causal models suffices to learn the causal direction. Through experiments with synthetic and real data, we demonstrate the favorable performance of the proposed COLP-based causal model compared to state-of-the-art methods. We also make available an accompanying R package COLP, which contains the proposed causal discovery algorithm and a benchmark dataset of categorical cause-effect pairs.
BibTeX
@inproceedings{ni2022bivariate,
  author = {Yang Ni},
  title = {{Bivariate Causal Discovery for Categorical Data via Classification with Optimal Label Permutation}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=uRSvcqwOm0},
}
Figure