Combinatorics of Distance Covariance: Inclusion-Minimal Maximizers of Quasi-Concave Set Functions for Diverse Variable Selection

Praneeth Vepakomma, Yulia KempnerarXiv 2017 · DOI · arXiv

Abstract

In this paper we show that the negative sample distance covariance function is a quasi-concave set function of samples of random variables that are not statistically independent. We use these properties to propose greedy algorithms to combinatorially optimize some diversity (low statistical dependence) promoting functions of distance covariance. Our greedy algorithm obtains all the inclusion-minimal maximizers of this diversity promoting objective. Inclusion-minimal maximizers are multiple solution sets of globally optimal maximizers that are not a proper subset of any other maximizing set in the solution set. We present results upon applying this approach to obtain diverse features (covariates/variables/predictors) in a feature selection setting for regression (or classification) problems. We also combine our diverse feature selection algorithm with a distance covariance based relevant feature selection algorithm of [7] to produce subsets of covariates that are both relevant yet ordered in non-increasing levels of diversity of these subsets.

Introduction

In the fields of machine learning and statistics, variable selection is traditionally viewed through the lens of relevance: identifying which features provide the most predictive power for a target variable. However, relevance alone often leads to the selection of highly redundant features. For instance, in a sensor network, two sensors placed in close proximity may both be highly relevant to a target outcome but provide nearly identical information. Such redundancy results in models that are computationally expensive, difficult to interpret, and prone to overfitting.

The challenge lies in "diverse variable selection"—the task of identifying a subset of features that are both relevant to the target and statistically independent of one another. Because this combinatorial problem is typically NP-hard, existing solutions often rely on linear assumptions or provide only approximate results. This paper introduces a mathematically rigorous, non-parametric approach to finding globally optimal sets of diverse features using the properties of distance covariance.

Theoretical Framework: Distance Covariance and Quasi-Concavity

The authors utilize Distance Covariance (dCov), a powerful statistical measure capable of detecting all types of dependencies—both linear and non-linear—between random variables. The central theoretical contribution of this work is the proof that the negative sample distance covariance function is a quasi-concave set function.

This discovery is significant because quasi-concavity allows for the application of specific combinatorial optimization techniques. While many diversity-promoting methods (such as those based on sub-modular functions) can only guarantee a "good enough" approximation (often the $1 - 1/e$ bound), the quasi-concave nature of negative dCov allows a greedy algorithm to achieve global optimality for the defined objective.

The DiverseMinimalMaximDCoV Algorithm

Building on this theoretical foundation, the authors propose Algorithm 1 (DiverseMinimalMaximDCoV). This greedy algorithm is designed to identify "inclusion-minimal maximizers"—sets of solutions that are globally optimal and are not proper subsets of any other maximizing set. Unlike standard greedy approaches, this algorithm is proven to find exact, globally optimal solutions for the diversity objective.

To address the dual needs of relevance and diversity, the authors implement a hybrid approach:

  1. Relevance Filtering: An existing relevance-based algorithm (the Kong-Wang-Wahba algorithm) is used to identify a pool of features significantly associated with the target variable.
  2. Diversity Optimization: The DiverseMinimalMaximDCoV algorithm is then applied to this pool to select the most diverse subset, ensuring that the final features are both predictive and non-redundant.

Experimental Evaluation

The proposed method was tested against the popular mRMR (Minimum Redundancy Maximum Relevance) Ensemble method using three real-world datasets from the UCI Machine Learning Repository:

  • Facebook Comment Volume: Predicting engagement based on post metrics.
  • Parkinson’s Speech Dataset: Predicting disease severity (UPDRS scores) from acoustic voice recordings.
  • Efron’s Diabetes Data: Predicting disease progression from baseline patient variables.

Key Results

The hybrid approach consistently outperformed mRMR across the test cases. Notably, on the Parkinson’s dataset, the proposed method achieved a Mean Squared Error (MSE) of 148.84, a significant improvement over the 154.39 achieved by mRMRe. Furthermore, visual validation using ISOMAP manifold learning confirmed that the algorithm successfully selected features that were spatially "far apart" in the feature space, validating the diversity objective.

Discussion and Insights

Several key insights emerged from this research:

  • Global Optimality: By leveraging quasi-concavity, the researchers moved beyond the standard guarantees of sub-modular approximations to achieve 100% optimality for their specific diversity objective.
  • Model Agnosticism: Since distance covariance is non-parametric, the selection process is independent of the final model type, whether it be linear regression, random forests, or neural networks.
  • The Role of Preprocessing: The study emphasizes that centering and scaling data is critical. Proper preprocessing ensures that distance covariance serves as a reliable proxy for distance correlation, which is necessary for consistent performance across variables with different scales.

Limitations and Future Directions

While the algorithm provides a path to optimal diversity, the trade-off between relevance and diversity remains a heuristic choice. Future work could focus on quantifying this "sweet spot" more precisely. Additionally, the computational complexity of the algorithm is $O(N^3 g)$, where $N$ is the number of features. While efficient for many applications, scaling to "big data" environments with extremely high dimensionality may require the integration of faster distance covariance approximations.

Conclusion

This paper provides a robust mathematical framework for diverse variable selection. By proving the quasi-concavity of negative distance covariance, the authors have transformed a complex combinatorial problem into one that can be solved optimally and efficiently, offering a significant advancement for building interpretable and efficient machine learning models.

Summary updated

Abstract

In this paper we show that the negative sample distance covariance function is a quasi-concave set function of samples of random variables that are not statistically independent. We use these properties to propose greedy algorithms to combinatorially optimize some diversity (low statistical dependence) promoting functions of distance covariance. Our greedy algorithm obtains all the inclusion-minimal maximizers of this diversity promoting objective. Inclusion-minimal maximizers are multiple solution sets of globally optimal maximizers that are not a proper subset of any other maximizing set in the solution set. We present results upon applying this approach to obtain diverse features (covariates/variables/predictors) in a feature selection setting for regression (or classification) problems. We also combine our diverse feature selection algorithm with a distance covariance based relevant feature selection algorithm of [7] to produce subsets of covariates that are both relevant yet ordered in non-increasing levels of diversity of these subsets.
BibTeX
@misc{vepakomma2017combinatorics,
  author = {Praneeth Vepakomma and Yulia Kempner},
  title = {{Combinatorics of Distance Covariance: Inclusion-Minimal Maximizers of Quasi-Concave Set Functions for Diverse Variable Selection}},
  year = {2017},
  eprint = {1702.05340},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1702.05340},
}
Figure