Ball divergence

Template:Orphan Ball Divergence (BD) is a novel statistical concept used to measure the difference between two probability distributions. It was introduced to address the shortcomings of traditional methods for comparing distributions, particularly in high-dimensional, non-normal, or imbalanced datasets. Unlike classical tests such as the Student's t-test or Hotelling’s T² test, which often require assumptions about the data (e.g., normality), Ball Divergence is a nonparametric measure, meaning it does not rely on any specific assumptions about the distribution of the data. This makes it especially useful in situations where the data do not conform to these assumptions, such as when there are outliers or heavy-tailed distributions.

Background

In statistics, distinguishing between two unknown samples in multivariate data is an important and challenging task. This comparison is essential in various fields such as hypothesis testing, machine learning, bioinformatics, and environmental studies. Traditionally, this task has been handled using parametric methods such as the Student’s t-test or Hotelling’s T² test. These tests typically assume that the data come from distributions that satisfy certain conditions, such as normality, homogeneity of variances, or independent samples. However, in practice, these assumptions often do not hold, particularly when the data are high-dimensional, contain outliers, or have heavy tails. In these situations, traditional tests may fail to detect meaningful differences between the distributions, leading to incorrect conclusions.

Previously, a more common non-parametric two-sample test method was the energy distance test. However, the effectiveness of the energy distance test relies on the assumption of moment conditions, making it less effective for extremely imbalanced data (where one sample size is disproportionately larger than the other). To address this issue, Chen, Dou, and Qiao proposed a non-parametric multivariate test method using ensemble subsampling nearest neighbors (ESS-NN) for imbalanced data. This method effectively handles imbalanced data and increases the test's power by fixing the size of the smaller group while increasing the size of the larger group.

Additionally, Gretton et al. introduced the maximum mean discrepancy (MMD) for the two-sample problem. Both methods require additional parameter settings, such as the number of groups 𝑘 in ESS-NN and the kernel function in MMD. Ball divergence addresses the two-sample test problem for extremely imbalanced samples without introducing other parameters.

Definition

The formal definition of Ball Divergence involves integrating the squared difference between two probability measures over a family of closed balls in a Banach space. This is achieved by first defining a metric (or distance function) within the space, which allows us to measure the distance between points. A closed ball around a point $u$ is simply the set of all points that are within a fixed distance $r$ from $u$, where $r$ is the radius of the ball.

The Ball Divergence formula is given as follows: $BD(\mu ,\nu )=\underset{\mathrm{V}\times \mathrm{V}}{\iint }[\mu -\nu {]}^2(\overline{B}(u,\rho (u,v)))(\mu (du)\mu (dv)+\nu (du)\nu (du)),$ where:

• $\mu$ and $\nu$ are the probability measures being compared.
• $B(u,\rho (u,v))$ represents a closed ball in the space, centered at $u$, with a radius determined by the distance between points $u$ and $v$ as measured by the norm $\rho (u,v)$.
• The integral is taken over all possible pairs of points, summing the squared differences of the two measures over all such balls.

This measure allows for a detailed, scale-sensitive comparison between the two distributions. The integral captures the global differences between the distributions, but the fact that it is defined over balls means that the comparison is inherently local as well, making it robust to variations in the data and more sensitive to local differences than traditional non-parameter methods.

Testing for equal distributions

Next, we will try to give a sample version of Ball Divergence. For convenience, we can decompose the Ball Divergence into two parts: $A=\underset{V\times V}{\iint }[\mu -\nu {]}^2(\overline{B}(u,\rho (u,v)))\mu (du)\mu (dv),$ and $C=\underset{V\times V}{\iint }[\mu -\nu {]}^2(\overline{B}(u,\rho (u,v)))\nu (du)\nu (dv).$ Thus $BD(\mu ,\nu )=A+C.$

Let $\delta (x,y,z)=I(z\in \overline{B}(x,\rho (x,y)))$ denote whether point $z$ locates in the ball $\overline{B}(x,\rho (x,y))$. Given two independent samples $\{X_1,\dots ,X_n\}$ form $\mu$ and $\{Y_1,\dots ,Y_m\}$ form $\nu$

$\begin{array}{cc}& A_{ij}^X=\frac{1}{n}\sum _{u=1}^n\delta (X_i,X_j,X_u),A_{ij}^Y=\frac{1}{m}\sum _{v=1}^m\delta (X_i,X_j,Y_v),\\ & C_{kl}^X=\frac{1}{n}\sum _{u=1}^n\delta (Y_k,Y_l,X_u),C_{ij}^Y=\frac{1}{m}\sum _{v=1}^m\delta (Y_k,Y_l,Y_v),\end{array}$ where $A_{ij}^X$ means the proportion of samples from the probability measure $\mu$ located in the ball $\overline{B}(X_i,\rho (X_i,X_j))$ and $A_{ij}^Y$ means the proportion of samples from the probability measure $\nu$ located in the ball $\overline{B}(X_i,\rho (X_i,X_j))$. Meanwhile, $C_{ij}^X$ and $C_{ij}^Y$ means the proportion of samples from the probability measure $\mu$ and $\nu$ located in the ball $\overline{B}(Y_i,\rho (Y_i,Y_j))$. The sample versions of $A$ and $C$ are as follows

$A_{n,m}=\frac{1}{n^2}\sum _{i,j=1}^n{(A_{ij}^X-A_{ij}^Y)}^2,C_{n,m}=\frac{1}{m^2}\sum _{k,l=1}^m{(C_{kl}^X-C_{kl}^Y)}^2.$ Finally, we can give the sample ball divergence

$B{D}_{n,m}=A_{n,m}+C_{n,m}.$

Properties

${\displaystyle }$ 1. $BD(\mu ,\nu )\ge 0$, where the equality holds if and only if $\mu =\nu$.

2. The square root of Ball Divergence does not satisfy the triangle inequality, so it is a symmetric divergence but not a metric.

3. BD can be generalized to the K-sample problem.Suppose that ${\mu }_1,\dots ,{\mu }_K$ are $K$ measures on Banach space.We can define that

$D({\mu }_1,\dots ,{\mu }_K)=\sum _{1\le l\le k\le K}\underset{\mathrm{V}\times \mathrm{V}}{\iint }[{\mu }_k-{\mu }_l{]}^2(\overline{B}(u,\rho (u,v)))(\mu (du)\mu (dv)+\nu (du)\nu (du)).$

Clearly, D(\mu_1, \ldots, \mu_K)=0 if and only if ${\mu }_1=\dots ={\mu }_K$.

3.Consistency: We have

$D_{n,m}\underset{n,m\to \mathrm{\infty }}{\overset{\text{ a.s. }}{\to }}D(\mu ,v),$ where $\frac{n}{n+m}\to \tau$ for some $\tau \in [0,1]$.

Define $\xi (x,y,z_1,z_2)=\delta (x,y,z_1)\cdot \delta (x,y,z_2)$, and then let $Q(x,y;x^{\prime },y^{\prime })=({\varphi }_A^{(2,0)}(x,x^{\prime })+{\varphi }_A^{(1,1)}(x,y)+{\varphi }_A^{(1,1)}(x^{\prime },y^{\prime })+{\varphi }_A^{(0,2)}(y,y^{\prime })),$ where

$\begin{array}{cc}{\varphi }_A^{(2,0)}(x,x^{\prime })=& E\left[\xi (X_1,X_2,x,x^{\prime })\right]+E\left[\xi (X_1,X_2,Y,Y_3)\right]\\ & -E\left[\xi (X_1,X_2,x,Y)\right]-E\left[\xi (X_1,X_2,x^{\prime },Y_3)\right]\\ {\varphi }_A^{(1,1)}(x,y)=& E\left[\xi (X_1,X_2,x,X_3)\right]+E\left[\xi (X_1,X_2,y,Y_3)\right]\\ & -E\left[\xi (X_1,X_2,x,y)\right]-E\left[\xi (X_1,X_2,X_3,Y_3)\right]\\ {\varphi }_A^{(0,2)}(y,y^{\prime })=& E\left[\xi (X_1,X_2,X,X_3)\right]+E\left[\xi (X_1,X_2,y,y^{\prime })\right]\\ & -E\left[\xi (X_1,X_2,X,y)\right]-E\left[\xi (X_1,X_2,X,y^{\prime })\right].\end{array}$ The function $Q(x,y;x^{\prime },y^{\prime })$ has spectral decomposition: $Q(x,y;x^{\prime },y^{\prime })=\sum _{k=1}^{\mathrm{\infty }}{\lambda }_k{f}_k(x,y)f_k(x^{\prime },y^{\prime }),$ where ${\lambda }_k$ and $f_k$ are the eigenvalues and eigenfunctions of $Q$. For $k=1,2,\dots$, $Z_{1k},Z_{2k}$ are i.i.d. $N(0,1)$, and $\begin{array}{cc}{a}_k^2(\tau )& =(1-\tau )E_X{[E_Y{f}_k(X,Y)]}^2,b_k^2(\tau )=\tau E_Y{[E_X{f}_k(X,Y)]}^2,\\ \theta & =2E\left[E(\delta (X_1,X_2,X)(1-\delta (X_1,X_2,Y))\mid X_1,X_2)\right].\end{array}$

4.Asymptotic distribution under the null hypothesis: Suppose that both $n$ and $m\to \mathrm{\infty }$ in such a way that $\frac{n}{n+m}\to \tau ,0\le \tau \le 1$. Under the null hypothesis, we have $\frac{nm}{n+m}B{D}_{n,m}\underset{n\to \mathrm{\infty }}{\overset{d}{\to }}\sum _{k=1}^{\mathrm{\infty }}2{\lambda }_k[{(a_k(\tau )Z_{1k}+b_k(\tau )Z_{2k})}^2-(a_k^2(\tau )+b_k^2(\tau ))]+\theta \text{. }$

5. Distribution under the alternative hypothesis: let ${\delta }_{1,0}^2=\mathrm{Var}(g^{(1,0)}(X))\text{ and }{\delta }_{0,1}^2=\mathrm{Var}(g^{(0,1)}(Y)).$ Suppose that both $n$ and $m\to \mathrm{\infty }$ in such a way that $\frac{n}{n+m}\to \tau ,0\le \tau \le 1$. Under the alternative hypothesis, we have $\sqrt{\frac{nm}{n+m}}(B{D}_{n,m}-BD(\mu ,\nu ))\underset{n\to \mathrm{\infty }}{d}N(0,(1-\tau ){\delta }_{1,0}^2+\tau {\delta }_{0,1}^2).$

6. The test based on $D_{n,m}$ is consistent against any general alternative $H_1$. More specifically, $\underset{n\to \mathrm{\infty }}{\lim }{\mathrm{Var}}_{H_1}\left(D_{n,m}\right)=0$ and $\mathrm{\Delta }(\eta ):=\underset{n\to \mathrm{\infty }}{\mathrm{lim\; inf}}(E_{H_1}{D}_{n,m}-E_{H_0}{D}_{n,m})>0.$ More importantly, $\mathrm{\Delta }(\eta )$ can also be expressed as $\mathrm{\Delta }(\eta )\equiv D(\mu ,\nu ),$ which is independent of $\eta$.