Consistent Distribution-Free $K$-Sample and Independence Tests for Univariate Random Variables

Ruth Heller, Yair Heller, Shachar Kaufman, Barak Brill, Malka Gorfine

TL;DR

This paper introduces a new family of statistical tests for detecting relationships between variables that are "distribution-free," meaning they don't rely on assumptions about the underlying data distributions. These tests are shown to be consistent, meaning they reliably detect relationships as sample sizes grow, and are computationally efficient, making them practical for real-world applications.

What Problem Does This Paper Address?

In statistics, a fundamental task is to determine if two variables are related (dependent) or not (independent). Traditional methods often struggle with complex, non-linear relationships and can be sensitive to the specific distributions of the data. This paper tackles the challenge of developing tests that are both powerful in detecting a wide range of dependencies and "distribution-free," meaning their validity doesn't depend on assumptions about the data's probability distributions. This is particularly important in modern data analysis where complex, unknown distributions are common. The authors also address the "K-sample problem," which is a special case of testing for differences in distributions across multiple groups.

Methods

The core innovation of this paper lies in developing tests based on partitioning the sample space into a grid of cells. The authors propose two main aggregation strategies for scores calculated over these partitions:

  • Summation: Aggregating scores by summing them across all possible partitions of a given size.
  • Maximization: Aggregating scores by taking the maximum across all possible partitions of a given size.

A key contribution is the development of "regularized" tests that aggregate scores over all possible partition sizes, effectively adapting to the optimal partition size without needing to know it in advance. This is achieved through methods like taking the minimum p-value across different partition sizes. The authors also provide efficient algorithms for computing these test statistics, which is crucial given the combinatorial explosion of partitions as data size and partition complexity increase. They leverage techniques like dynamic programming and efficient data structures to achieve polynomial time complexity for many of their methods.

Datasets

The paper evaluates its methods using simulated datasets across various scenarios designed to test for different types of dependencies (e.g., shifts, scale changes, complex mixtures, non-monotone relationships). They also apply their methods to the yeast gene expression dataset from Hughes et al. (2000) to demonstrate their utility on real-world biological data.

Key Insights and Ideas

  • The power of fine partitions: For complex, non-monotone relationships, using finer partitions (more cells in the grid) significantly improves the power of the tests compared to traditional methods that rely on coarse partitions.
  • Regularization is key: The "regularized" tests that consider all partition sizes are remarkably effective at adapting to the optimal partition size, achieving power close to that of tests using the (unknown) optimal partition. This makes them robust to the choice of partition size.
  • Summation vs. Maximization: The choice between summation and maximization aggregation depends on the nature of the dependency. Maximization tends to be better for very local dependencies, while summation is preferred for more spread-out differences.
  • Computational efficiency matters: The development of efficient algorithms is critical for making these powerful tests practical for analyzing large datasets.

Key Results

  • The proposed distribution-free tests are shown to be consistent against general alternatives, meaning they reliably detect dependencies as sample size increases.
  • The minimum p-value statistic (which aggregates across partition sizes) demonstrates excellent power, often outperforming existing distribution-free tests, especially for complex non-monotone relationships.
  • In simulations, the regularized tests achieve power very close to that of tests using the optimal (but unknown) partition size.
  • For the yeast gene expression data, the new tests revealed interesting non-linear relationships that were missed by classical methods.
  • The authors provide efficient algorithms with polynomial time complexity for many of their proposed statistics, making them computationally feasible.

Limitations and Future Work

  • The authors acknowledge that for the independence problem, polynomial-time algorithms for aggregation by maximization are not known for arbitrary partition sizes, limiting their practical use to smaller m values.
  • They suggest that a thorough investigation of their mutual information estimator and exploring its asymptotic distribution would be valuable.
  • Future work could explore modifying the tests for situations where paired observations are not independent but are independent within blocks, or where temporal dependence exists.
  • Investigating the performance of their methods with different distance metrics and exploring the bias of their mutual information estimator are also mentioned as future directions.

Summary updated

Abstract

A popular approach for testing if two univariate random variables are statistically independent consists of partitioning the sample space into bins, and evaluating a test statistic on the binned data. The partition size matters, and the optimal partition size is data dependent. While for detecting simple relationships coarse partitions may be best, for detecting complex relationships a great gain in power can be achieved by considering finer partitions. We suggest novel consistent distribution-free tests that are based on summation or maximization aggregation of scores over all partitions of a fixed size. We show that our test statistics based on summation can serve as good estimators of the mutual information. Moreover, we suggest regularized tests that aggregate over all partition sizes, and prove those are consistent too. We provide polynomial-time algorithms, which are critical for computing the suggested test statistics efficiently. We show that the power of the regularized tests is excellent compared to existing tests, and almost as powerful as the tests based on the optimal (yet unknown in practice) partition size, in simulations as well as on a real data example.
BibTeX
@article{heller2016consistent,
  author = {Ruth Heller and Yair Heller and Shachar Kaufman and Barak Brill and Malka Gorfine},
  title = {{Consistent Distribution-Free $K$-Sample and Independence Tests for Univariate Random Variables}},
  journal = {JMLR},
  year = {2016},
}
Figure