Consistent distribution-free tests of association between univariate random variables

Ruth Heller, Yair Heller, Shachar Kaufman, Malka GorfinearXiv 2013 · DOI · arXiv

TL;DR

This paper introduces a new family of "distribution-free" statistical tests for detecting associations between two random variables. These tests are powerful, computationally efficient, and can identify a wide range of dependencies beyond simple linear or monotonic relationships, making them valuable for complex data analysis like genomics.

What Problem Does This Paper Address?

In many scientific fields, researchers are interested in understanding relationships between variables. A fundamental question is whether two variables are independent or dependent. While many statistical tests exist to detect dependence, a significant challenge arises when we want tests that are:

  1. Distribution-free: Their performance doesn't depend on the specific underlying probability distributions of the variables. This is crucial because we often don't know these distributions or they might be complex.
  2. Consistent against all dependent alternatives: They can detect any form of dependence, not just specific types like linear (e.g., correlation) or monotonic (e.g., Spearman's rank correlation).
  3. Computationally efficient: Especially when dealing with large datasets or testing many pairs of variables (like genes in a microarray), the tests need to be fast.

Existing distribution-free tests, like Hoeffding's test, are often less powerful or only consistent against specific types of dependence. Conversely, tests that are powerful against all dependence types (like distance covariance) are often not distribution-free, meaning their null distribution depends on the unknown marginal distributions, making them computationally intensive to use in practice, especially for large-scale hypothesis testing. This paper aims to bridge this gap by proposing tests that are simultaneously distribution-free, powerful against general dependence, and computationally efficient.

Methods

The core of the paper introduces novel test statistics based on partitioning the two-dimensional space of the data. These tests fall into two main categories:

  • All Derived Partitions (ADP): These tests consider all possible ways to partition the data space into a grid of $k \times k$ cells. The test statistic is derived from the observed counts within these cells compared to expected counts under independence.
  • Data Derived Partitions (DDP): These tests use the data points themselves to define the partitions. Specifically, a subset of $k-1$ points is chosen to define the boundaries of the $k \times k$ grid.

For each partition, the authors use either a Pearson's score (based on the squared difference between observed and expected counts) or a likelihood ratio score for each cell. These cell scores are then aggregated across all partitions using either summation (leading to a "von-Mises type" statistic) or maximization (leading to a "Kolmogorov-Smirnov type" statistic).

A key contribution is the development of innovative algorithms that make computing these test statistics efficient, especially for larger values of $k$. These algorithms reduce the computational complexity from naive approaches, making the tests practical for real-world applications. The paper also shows that one of these statistics (the summation variant of the ADP test using the likelihood ratio score) is a consistent estimator of mutual information.

Datasets

The paper uses two main types of data for evaluation:

  • Simulated Data: Various complex bivariate relationships (e.g., sine, spiral, Doppler effect) are generated to test the power of the proposed methods under different dependence structures. These scenarios are drawn from existing literature to allow for comparison with other methods.
  • Real Data: A microarray dataset from Hughes et al. (2000) containing gene expression levels for 94 genes is analyzed to demonstrate the practical application of the tests in identifying co-dependent genes.

Key Insights and Ideas

  • The Power of Partitioning: The fundamental idea is that dependence between variables will manifest as deviations from expected counts in specific regions of the data space. By systematically partitioning this space and analyzing these deviations, we can detect dependence.
  • Beyond Linearity: The proposed methods are designed to capture complex, non-linear relationships that traditional correlation-based tests might miss.
  • Distribution-Free Advantage: By relying on ranks and partitions, the tests avoid assumptions about the underlying data distributions, making them more robust.
  • Computational Efficiency is Key: The development of efficient algorithms is crucial for the practical utility of these tests, especially in high-dimensional settings like genomics.
  • Mutual Information Connection: The link between one of the test statistics and mutual information suggests that these tests can not only detect dependence but also quantify its strength.

Key Results

  • Excellent Power: Simulations show that the proposed tests, particularly the summation variant of the All Derived Partitions (ADP) test with $k \in \{3, \dots, 10\}$, consistently outperform existing distribution-free tests (like Hoeffding's) and are competitive with or superior to non-distribution-free tests (like distance covariance) in detecting non-monotone dependencies.
  • Parameter Sensitivity: The choice of partition size $k$ is shown to be the most critical parameter, with $k \ge 4$ generally providing excellent power for complex relationships. For hundreds of observations, $k=5$ is suggested for complex relationships, while $k=3$ or $k=4$ can be sufficient for less complex ones or when computational time is a concern.
  • Real-World Application: In the gene expression data analysis, the proposed tests identified a significantly larger number of co-dependent gene pairs compared to methods like Spearman's correlation or maximal information coefficient, highlighting their ability to detect subtle and complex associations.
  • Mutual Information Estimation: The ADP summation statistic is shown to be a consistent estimator of mutual information under certain conditions.

Limitations and Future Work

  • Parameter Tuning: While $k$ is identified as the most important parameter, choosing the optimal $k$ can still be challenging and may depend on the specific dataset and the nature of the expected dependencies. The paper suggests $k=5$ as a good general choice for several hundred observations.
  • Mutual Information Estimator: The theoretical investigation of the mutual information estimator was limited to the ADP summation statistic. The authors suggest that an estimator based on Data Derived Partitions (DDP) might also be useful and warrants future exploration.
  • Multivariate Extension: The current work focuses on bivariate associations. The authors intend to generalize these methods to univariate two-sample or multi-sample problems, drawing connections to classic non-parametric tests.
  • Ties: The current implementation handles ties by random breaking, which maintains the distribution-free property. Alternative approaches for handling ties are mentioned but not fully explored in terms of their impact on the distribution-free nature of the tests.

Summary updated

Abstract

We consider the problem of testing whether pairs of univariate random variables are associated. Few tests of independence exist that are consistent against all dependent alternatives and are distribution free. We propose novel tests that are consistent, distribution free, and have excellent power properties. The tests have simple form, and are surprisingly computationally efficient thanks to accompanying innovative algorithms we develop. Moreover, we show that one of the test statistics is a consistent estimator of the mutual information. We demonstrate the good power properties in simulations, and apply the tests to a microarray study where many pairs of genes are examined simultaneously for co-dependence.
BibTeX
@misc{heller2013consistent,
  author = {Ruth Heller and Yair Heller and Shachar Kaufman and Malka Gorfine},
  title = {{Consistent distribution-free tests of association between univariate random variables}},
  year = {2013},
  eprint = {1308.1559},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1308.1559},
}
Figure