Data-Driven Representations for Testing Independence: Modeling, Analysis and Connection with Mutual Information Estimation

The problem of detecting independence from i.i.d. samples in a learning setting (distribution-free) is fundamental in statistics and has found numerous applications in statistical signal processing, data analysis, machine learning, inference, and decision problems [1, 2, 3, 4]. For instance, the capacity to detect independent and conditional independent structures from data is relevant when having invariances and probabilistic symmetries in decision and machine learning models [5, 6, 7, 8]. This capacity has been used in blind source separation, independent component analysis (ICA) [1, 2, 3, 4, 9] and the detection of associations in data [10]. Detecting independence from data has been systematically studied, and the literature is vast. Different non-parametric strategies have been proposed for this task using kernel-based statistics [11, 12, 13, 14], distance-based approaches [15, 16, 17, 18, 19], histogram-based approaches [20, 21, 22, 10, 23, 24], log-likelihood statistics [20, 25], correlation-based approaches [26, 27], $\phi$-divergence estimators [25, 20], entropy and mutual information estimators [28, 29, 30, 10, 10], among many others.

A natural strategy, and the one we follow in this paper, is to partition the observation space (the binning approach) to evaluate the discrepancy (in some sense) between two empirical distributions [20, 12, 29, 15, 22, 21]. We highlight the following work using this approach: Gretton and Györfi [20] introduced a family of product data-independent partitions using the $L_{1}$-statistics [31] and the I-divergence statistics [32]. With these two approaches, sufficient conditions are established on the partition and other learning parameters to achieve strong consistency for detecting independence distribution-free in a continuous multivariate scenario. Szekely et al. [15] also use partitions on the sample space, utilizing empirical distance correlation and distance covariance statistics to introduce a novel test of independence. The test is consistent and shows better empirical results than classical likelihood-ratio tests in scenarios with non-linear dependencies. Shi et al. [33] address the multivariate scenario by incorporating the concept of transportation-based ranks and signs. They propose plugging the center-outward distribution function into the mentioned distance covariance statistic [15] to determine a distribution-free test of independence.

More recently, Zhang [22] proposed a non-parametric test of independence assuming a rich class of models with known marginal distributions (uniform over $[0,1]$). This work proposed a binary expansion filtration of the space and deeply studied some symmetric properties to create a novel test that is uniformly consistent (on the power loss) and minimax for the power (in the sample size) assuming a large class of alternative distributions. Zhang et al. [34] presented a novel extension of the binary expansion filtration strategy [22] to a multidimensional setting by cleverly approximating an oracle Neyman-Pearson (NP) statistic. They propose a data-adaptive weight strategy (for the binary expansion) to approximate the ideal weight of the NP test. This new test unifies several important tests ($\chi^{2}$ test statistics, distance correlation) and shows promising empirical results.

On the important connection between testing independence and information measures [35, 36], we highlight the work of Kontoyiannis and Skoularidou [30], where the problem of estimating directed information (directed information rate) between two discrete (finite alphabet) processes was explored based on a plug-in estimator. Importantly, the authors used this plug-in estimator to test the presence or absence of causality between the processes. Along the same lines, Suzuki [29] explored different strategies to estimate mutual information between discrete and continuous random variables and then evaluated those strategies experimentally for the task of testing independence. Finally, Reshef et al. [10] introduced the maximal information coefficient (MIC) to measure complex functional dependencies between a pair of variables by maximizing the (empirical) mutual information computed for collections of (adaptive) partitions of different resolutions.

In many of the methods mentioned that use partitions (or binning) for testing independence, a component that has not been explored systematically is the role played by data-driven partitions [37, 38, 10]. Data-driven partitions use data for the binning process (vector quantization) to construct the cells and define the final structure of the partition. This flexibility offers the capacity to better address inference and learning problems. Supporting this idea, data-driven representations have shown great approximation properties and better decision-estimation performance in numerous non-parametric learning problems [37, 38, 39, 40, 41].

In our context, the motivation that piqued our interest in data-driven partitions is the fact that under the hypothesis of independence, the trivial partition (the partition with one cell that contains all the space) is a sufficient representation of the problem. Our initial conjecture is that a well-designed adaptive data-driven partition could have the ability to detect (learn from data) this trivial solution by implementing a form of explicit regularization in its design. This adaptive ability could provide better detection of independence than non-adaptive partition schemes, which has prompted the exploration of data-driven methods for testing independence in this work.

Motivated by this, we look at the problem of designing a new learning criterion that selects a data-driven partition of the space (adaptive binning) as the optimal trade-off between estimation and approximation errors in a learning problem. To formulate this representation learning task, we adopt ideas from universal source coding to introduce a regret term that measures the discrepancy attributed to the use of empirical log-likelihood statistics — restricted over a partition — with respect to the oracle sufficient statistics of an ideal test that knows the true (two) probabilities: the oracle test against independence [36, 42]. Using this regret analysis, we establish a novel connection with the problem of mutual information (MI) estimation [30]. Furthermore, general conditions are derived to obtain a strongly consistent test of independence in the strong (almost-sure and distribution-free) sense introduced in [20].

We apply this framework in the context of tree-structured partitions (TSP) [39], which is the main application focus of this work. TSP algorithms were selected for the following important reasons: Their implementation is simple, TSP have a binary structure that can be used to address learning tasks efficiently for a large class of optimization problems (minimum cost-tree pruning) [43, 44, 45], and they have been shown to be expressive (with good approximation properties) when compared with other partition strategies in non-parametric learning and decision tasks [37, 38, 39, 40, 41, 43, 46, 37, 44].

On the proposed test, we derive concrete connections with results on mutual information estimation [39]. From these connections, we established new design conditions to obtain a strongly consistent test of independence and, more importantly, non-asymptotic results that express our framework’s capacity to approximate the information term of the oracle (ideal) test with a finite sample-size. Going a step further in this finite length performance analysis, we study our scheme’s capacity to detect independence structurally with the underlying data-driven partition, which was one of the original motivations used to explore data-driven partition for this task.

Indeed, we show that under the independence assumption, our data-driven partition collapses to the trivial solution with one cell (implying that the resulting MI estimator is zero) with a finite sample-size almost surely. This is a remarkable property attributed to our scheme’s capacity to adapt its representation to the sufficient statistics of the problem, which is the trivial partition in the context of independence. From this ability, we improve our original result concerning our test’s consistency (density-free) and provide refined sampling complexity bounds for detecting the scenario of independence.

To implement our approach, we propose a learning algorithm that offers a computationally efficient implementation of our data-driven strategy for testing independence. The algorithm is divided in two important phases (a growing and pruning stage), which are both shown to have a polynomial complexity on the side of the problem (the sample size). Finally, we provide empirical evidence of the advantage of our strategy in some controlled simulation scenarios. For this last analysis, we introduce concrete non-asymptotic metrics (in the form of sampling complexity indicators) to measure the test’s ability to detect the correct hypothesis with a finite number of samples.

A preliminary version of this work was presented in [47]. This work significantly expands the technical contribution in [47] and explores implementations and experimental analyses.

Let us consider two random variables $X$ and $Y$ taking values in $\mathbb{R}^{p}$ and $\mathbb{R}^{q}$, respectively, with joint distribution $P$ in $(\mathbb{R}^{d},\mathcal{B}(\mathbb{R}^{d}))$, where $d=p+q$ and $\mathcal{B}(\mathbb{R}^{d})$ is the Borel sigma field. Let us denote by $\mathcal{P}_{0}$ the class of probabilities in $(\mathbb{R}^{d},\mathcal{B}(\mathbb{R}^{d}))$ under which $(X,Y)$ are independent, meaning that if $P\in\mathcal{P}_{0}$, then $P(A\times B)=P(\mathbb{R}^{p}\times B)\cdot P(A\times\mathbb{R}^{q})$ for any $A\in\mathcal{B}(\mathbb{R}^{p})$ and $B\in\mathcal{B}(\mathbb{R}^{q})$.

Given $n$ i.i.d. samples of $(X,Y)$, denoted by $Z^{n}_{1}\equiv(Z_{1}\equiv(X_{1},Y_{1}),Z_{2}\equiv(X_{2},Y_{2}),..,Z_{n}\equiv(X_{n},Y_{n}))\in\mathbb{R}^{d}$ driven by the model $P\in\mathcal{P}(\mathbb{R}^{d})$, the problem is to decide from $Z^{n}_{1}$ whether $X$ and $Y$ are independent (meaning that $P\in\mathcal{P}_{0}$) or, alternatively, $X$ and $Y$ have some statistical dependency, i.e., $P\notin\mathcal{P}_{0}$. In this context, a decision rule $\phi_{n}(\cdot)$ of length $n$ is a function from $(\mathbb{R}^{d})^{n}$ to $\left\{0,1\right\}$, where $\phi_{n}(z^{n}_{1})=0$ means that the rule decides that the underlying probability producing $z^{n}_{1}$ belongs to $\mathcal{P}_{0}$. Then, for any decision rule $\phi_{n}\in\Pi_{n}$¹¹1$\Pi_{n}$ denotes the collection of binary rules acting on $\mathbb{R}^{dn}$. of length $n$, we recognize two errors:

• •

  Assuming that $P\in\mathcal{P}_{0}$ ($\mathcal{H}_{0}$), the non-detection of independence between $X$ and $Y$ is measured by²²2$\mathbb{P}$ denotes the entire process distribution of $(Z_{n})_{n\geq 1}$ and $P^{n}$ is the $n$-fold probability in $\mathbb{R}^{dn}$ induced by the marginal $P$.

  $$\mathbb{P}(\phi_{n}(Z^{n}_{1})=1)=P^{n}(\left\{z^{n}_{1}:\phi_{n}(z^{n}_{1})=1\right\}),$$

• •

  Assuming that $P\notin\mathcal{P}_{0}$ ($\mathcal{H}_{1}$), the false detection of independence between $X$ and $Y$ is measured by

  $$\mathbb{P}(\phi_{n}(Z^{n}_{1})=0)=P^{n}(\left\{z^{n}_{1}:\phi_{n}(z^{n}_{1})=0\right\}).$$

The following is the classical notion of strong-consistency used to evaluate the asymptotic goodness of a universal scheme (collection of rules of different lengths) for detecting independence from data [20].

In this work, we adopt a histogram-based log-likelihood statistics approach [20]. We interpret this approach as an empirical version of the Neyman-Pearson (NP) test against independence [42]. The ideal (oracle) NP test against independence decides whether the samples belong to the following two known cases: $P$ (for some $P\notin\mathcal{P}_{0}$) or $Q^{*}(P)\in\mathcal{P}_{0}$, where $Q^{*}(A\times B)=P(\mathbb{R}^{p}\times B)\cdot P(A\times\mathbb{R}^{q})$ for any $A\in\mathcal{B}(\mathbb{R}^{p})$ and $B\in\mathcal{B}(\mathbb{R}^{q})$.⁴⁴4$Q^{*}(P)$ can be interpreted as the projection of $P$ on $\mathcal{P}_{0}$ in the information divergence sense, i.e., $Q^{*}(P)$ is the solution of $\min_{Q\in\mathcal{P}_{0}}D(P||Q)$.

The specific approach proposed in this work is a two-stage process that uses the data $Z^{n}_{1}\sim P^{n}$ twice: first, to estimate $P$, and its projected version $Q^{*}(P)$ (over $\mathcal{P}_{0}$), with the caveat that the estimation is restricted over the events of a finite partition of the joint space $\mathbb{R}^{d}$ (i.e., a histogram-based estimation of $P$ and $Q^{*}(P)$, respectively); second, to compute an empirical version of the log likelihood-ratio to decide (using a threshold) if $\hat{P}=\hat{Q}^{*}$ (independence) or $\hat{P}\neq\hat{Q}^{*}$ (non-independence).

There are two elements of learning design that determine our empirical test. The first is a data-driven partition rule denoted by $\pi_{n}(\cdot)$, which is a function that maps sequences in $(\mathbb{R}^{d})^{n}$ into a finite measurable partitions of $\mathbb{R}^{d}$. The second element is a non-negative threshold denoted by $a_{n}\in\mathbb{R}^{+}$. Then given a pair $(\pi_{n}(\cdot),a_{n})$ and some data $z^{n}_{1}\in\mathbb{R}^{dn}$, the data-driven test is constructed as follows:
1) Use the quantization $\pi_{n}(z^{n}_{1})=\left\{A_{i},i=1,..,\left|\pi_{n}(z^{n}_{1})\right|\right\}\subset\mathcal{B}(\mathbb{R}^{d})$ to estimate $P$ over the cells $\pi_{n}(z^{n}_{1})$:

for any $A\in\pi_{n}(z^{n}_{1})$. In Eq.(4) we assume that the cells of $\pi_{n}(z^{n}_{1})$ have a product structure, i.e., $A=A^{1}\times A^{2}$ where $A^{1}\in\mathcal{B}(\mathbb{R}^{p})$ and $A^{2}\in\mathcal{B}(\mathbb{R}^{q})$.⁵⁵5This event-wise product structure on the cells of $\pi_{n}(z^{n}_{1})$ is needed to estimate both $P$ and $Q^{*}$ from i.i.d. samples of $P$.
2) Project the data $z^{n}_{1}$ over the cells of $\pi_{n}(z^{n}_{1})$. A simple projection (or representation) function is the following:

The projected data is given and denoted by $o^{n}_{1}\equiv(o_{1}=O_{\pi_{n}}(z_{1}),..,o_{n}=O_{\pi_{n}}(z_{n}))$.
3) Compute the log-likelihood ratio of the empirical distributions in (3) and (4) using the quantized (or projected over $\sigma(\pi_{n}(z^{n}_{1}))$) data $o^{n}_{1}$. In particular, we consider the following log-likelihood ratio per sample as

where $\hat{P}_{O_{\pi_{n}}}$ and $\hat{Q}^{*}_{O_{\pi_{n}}}$ denote the empirical distributions of the quantized random variable $O_{\pi_{n}}$ in its representation space $\left\{1,..,\left|\pi_{n}(z^{n}_{1})\right|\right\}$, meaning that by construction $\hat{P}_{O_{\pi_{n}}}(j)=\hat{P}_{n}(A_{j})$ and $\hat{Q}_{O_{\pi_{n}}}(j)=\hat{Q}^{*}_{n}(A_{j})$ for all $j\in\left\{1,..,\left|\pi_{n}(z^{n}_{1})\right|\right\}$.
4) Finally, the decision is given by the following rule:

The second step introduced $O_{\pi_{n}}(Z)$ in (5). This object captures the role played by the data-driven partition ($\pi_{n}$) in our log-likelihood statistics in (6).

To analyze the quality of the proposed test, in this section we compare the proposed statistics in (6) with the statistics used by an oracle NP test. We consider the data-driven partition in the pair $(\pi_{n}(\cdot),a_{n})$ as a learning agent. For this analysis, let us first fix a finite partition $\pi=\left\{A_{i},i=1,..,\left\{1,..,J\right\}\right\}$. Given i.i.d. realizations $Z_{1},..,Z_{n}$ from $P\in\mathcal{P}(\mathbb{R}^{d})$, we consider the empirical-quantized log-likelihood statistics in (6). Adopting the notion of regret from universal source coding [35], let us consider as a reference the true likelihood ratio of $P$ with respect to $Q^{*}(P)$ associated with the expression in (6) but with no quantization effects, i.e., ⁶⁶6By construction $P\ll Q^{*}$; therefore, the RN derivative $\frac{dP}{dQ^{*}}$ is well defined in (8) where it is clear that if $(\log\frac{dP}{dQ^{*}}(z))_{z\in\mathbb{R}^{d}}\in\ell_{1}(P)$, then $I(X,Y)=\mathbb{E}_{Z\sim P}\left\{\log\frac{dP}{dQ^{*}}(Z))\right\}<\infty$.

$i_{n}(z_{1},...,z_{n})$ is the ideal (oracle) information term used by the NP test against independence [35]. We measure the (sample-wise) regret of $\pi$ as

which measures the discrepancy between the empirical-quantized statistics in (6) and the oracle term in (8).

In this section, an empirical version of (13) is studied considering for $\Pi$ a dictionary of tree-structured data-driven partitions (TSP). This TSP family was introduced in [39] for the problem of MI estimation. The focus of this section is to demonstrate its potential for the problem of testing independence.

In this section, we focus on finite-length (non-asymptotic) results. We establish conditions where the solution of (17) nearly matches the performance of its equivalent oracle version in (13) with high probability. This non-asymptotic result is instrumental to show later one of the main findings of our work: the capacity of our scheme to detect $\mathcal{H}_{0}$ with the structure of the partition.

The proof of this result is presented in Appendix C.

This result presents two optimality bounds for the information term of the TSP scheme under the two main hypotheses ($\mathcal{H}_{0}$ and $\mathcal{H}_{1}$) of our problem. Under $\mathcal{H}_{0}$, our regularization approach is capable of detecting this structure (with an arbitrary high probability $1-\epsilon$) in the sense that $\hat{T}_{b_{n},\delta_{n}}$ in (17) reduces to the trivial partition $\left\{\mathbb{R}^{d}\right\}$. From this, we obtain the zero regret condition $\hat{i}_{\pi_{b_{n},\delta_{n}}}(O_{\pi_{b_{n},\delta_{n}}}(Z_{1}),....,O_{\pi_{b_{n},\delta_{n}}}(Z_{n}))=i_{n}(Z_{1},...,Z_{n})$. This means that the solution of $\hat{T}_{b_{n},\delta_{n}}$ by itself (with no threshold) is capable of detecting independence.

On the other hand, under $\mathcal{H}_{1}$, we notice that it is only relevant to bound the under-estimation of $i_{n}(Z_{1},...,Z_{n})$ with the empirical (log-likelihood ratio) information $\hat{i}_{\pi_{b_{n},\delta_{n}}}(O_{\pi_{b_{n},\delta_{n}}}(Z_{1}),....,O_{\pi_{b_{n},\delta_{n}}}(Z_{n}))$. Limiting the analysis only to the underestimation of $i_{n}(Z_{1},...,Z_{n})$ can be argued from the well-known observation that quantization (on average) provides a bias (under-estimation) estimation of $\mathbb{E}(i_{n}(Z_{1},...,Z_{n}))=I(X;Y)$. More importantly for our problem, an overestimation of the oracle information $i_{n}(Z_{1},...,Z_{n})$ does not increase the type 2 error when using $\hat{i}_{\pi_{b_{n},\delta_{n}}}(O_{\pi_{b_{n},\delta_{n}}}(Z_{1}),....,O_{\pi_{b_{n},\delta_{n}}}(Z_{n}))$ instead of the oracle $i_{n}(Z_{1},...,Z_{n})$ under $\mathcal{H}_{1}$.

In summary, Theorem 2 indicates that with an arbitrary high probability, the empirical TSP solution of (17) achieves the performance of the oracle solution that optimizes the upper bound on the regret derived in Eq.(13) over the TSP family $\left\{\pi_{T},T\ll T^{full}_{b_{n}}\right\}$.