Technische Samenvatting: Een Martingaal-Kernonafhankelijkheidstest

1. Probleemstelling

Het artikel behandelt de computationele en statistische kalibratie-uitdagingen die inherent zijn aan kerngebaseerde onafhankelijkheidstests, specifiek het Hilbert–Schmidt Independence Criterion (HSIC) en diens uitbreiding tot gezamenlijke onafhankelijkheid, dHSIC.

Standaardimplementaties van HSIC en dHSIC vertrouwen op degenererende V-statistieken. Onder de nulhypothese van onafhankelijkheid ($H_0$) convergeren de geschaalde statistieken naar een gewogen som van $\chi^2$-toevalsvariabelen, waarbij de gewichten afhangen van de onbekende gezamenlijke dataverdeling. Bijgevolg vereist praktische kalibratie permutatietests om de nulverdeling te benaderen. Dit proces houdt in dat de statistiek $B$ keer opnieuw wordt berekend (typisch $B \ge 200$), waardoor de rekenkosten per test oplopen van $O(n^2)$ naar $O(B n^2)$, een factor van twee orde van grootte.

De auteurs beogen de permutatiestap volledig te elimineren door statistieken te construeren met een bekende, verdelingsvrije nullimiet (standaardnormaal), waardoor de kosten per test worden teruggebracht tot de kwadratische complexiteit van de bevooroordeelde V-statistiek zelf.

2. Methodologie

De voorgestelde aanpak past de recente martingaale MMD-constructie voor tweestalen-tests (Chatterjee en Ramdas [2025]) toe op de onafhankelijkheidscontext. Het kernidee is om de standaard schatting met kwadratische tijd om te vormen tot een som van martingaaldifferenties, die vervolgens gestudentiseerd kunnen worden om via de zelfgenormaliseerde martingaal Centrale Limietstelling (CLT) te convergeren naar een standaardnormale verdeling.

2.1 De mHSIC-statistiek (Bivariate Onafhankelijkheid)

Voor het testen van onafhankelijkheid tussen twee variabelen $X$ en $Y$ definiëren de auteurs mHSIC.

• Constructie: De statistiek is een gestudentiseerde, onder-driehoekige som van het Hadamard-product van twee empirisch gecentreerde Gram-matrices ($K_X$ en $K_Y$).
  $$\hat{T}^{\text{mHSIC}}_n = \frac{1}{n} \sum_{i=2}^n \frac{1}{i} \sum_{j=1}^{i-1} (HK_XH)_{ij} (HK_YH)_{ij}$$
• Studentisering: De statistiek wordt genormaliseerd door zijn empirische kwadratische variatie $\hat{\sigma}_n$.
• Theoretische Basis: Onder $H_0$ vormt het kernproduct $\bar{k}_X \bar{k}_Y$ (waarbij $\bar{k}$ populatie-gecentreerde kernen aanduidt) een martingaaldifferentieserie. Hoewel de empirische centreringmatrix $H$ een vertekening introduceert, bewijzen de auteurs dat deze vertekening $O_P(1/\sqrt{n})$ is en na studentisering asymptotisch verwaarloosbaar.
• Eigenschappen: Onder voorwaarden voor begrenste vierde momenten convergeert mHSIC naar $\mathcal{N}(0, 1)$ ongeacht de datawet. Het is consistent tegenover elke vaste alternatief en behoudt een rekenkosten van $O(n^2)$ zonder steekproefsplitsing.

2.2 De mdHSIC-statistiek (Gezamenlijke Onafhankelijkheid)

Voor het testen van gezamenlijke onafhankelijkheid onder $d$ variabelen ($X_1, \dots, X_d$) faalt een naïeve uitbreiding van mHSIC.

• Het Falen van Direct Product: Het vervangen van de bivariate kern door een $d$-voudig product van empirisch gecentreerde kernen resulteert in een geaggregeerde vertekening van $O_P(d/\sqrt{n})$. Wanneer het aantal variabelen $d$ groter is dan $\sqrt{n}$, overheerst deze vertekening de gestudentiseerde schaal, waardoor de kalibratie naar de standaardnormaal verbroken wordt.
• De Split-Martingaal Oplossing (mdHSIC): Om dit op te lossen, introduceren de auteurs een enkele halve steekproefsplitsing:
  1. Splitsing: De steekproef wordt verdeeld in $S_1$ (eerste helft) en $S_2$ (tweede helft).
  2. Centrering: De gemiddelde inbeddingen en gecentreerde kernen worden geschat met uitsluitend $S_1$.
  3. Martingaalloop: De onder-driehoekige zelfgenormaliseerde martingaalsom wordt berekend met behulp van de in $S_1$ gecentreerde kernen toegepast op paren binnen $S_2$.
• Theoretische Basis: Deze constructie zorgt ervoor dat de conditionele gemiddelde residual van het kernproduct $O_P(m^{-d/2})$ is (waarbij $m \approx n/2$). Deze residual is exponentieel klein in $d$, waardoor deze verwaarloosbaar is voor elke vaste $d \ge 2$.
• Eigenschappen: mdHSIC convergeert naar $\mathcal{N}(0, 1)$ voor elke vaste $d$ onder gezamenlijke onafhankelijkheid. De kosten per test bedragen $O(d n^2)$, lineair in $d$, waardoor de permutatiefactor $B$ wordt vermeden.

3. Belangrijkste Bijdragen

1. mHSIC: Een permutatievrije, steekproefsplitsingsvrije statistiek voor bivariate onafhankelijkheid die onder de nulhypothese convergeert naar een standaardnormale verdeling, met kosten van $O(n^2)$ die overeenkomen met die van de bevooroordeelde HSIC V-statistiek.
2. mdHSIC: Een permutatievrije statistiek voor gezamenlijke onafhankelijkheid van $d$ variabelen. Het corrigeert de empirische centrering-vertekening van directe-productuitbreidingen via een enkele halve steekproefsplitsing, waardoor asymptotische normaliteit wordt gewaarborgd voor elke vaste $d$ met complexiteit $O(d n^2)$.
3. Theoretische Waarborgen: Bewijzen van convergentie naar $\mathcal{N}(0, 1)$ onder de nulhypothese (Stellingen 3 en 6) en consistentie tegenover vaste alternatieven, gebaseerd op de zelfgenormaliseerde martingaal CLT (Fan [2018]).
4. Empirische Validatie: Aantonen dat beide statistieken de Type-I foutpercentages en testkracht van permutatie-gekalibreerde baselines evenaren, terwijl aanzienlijke snelheidswinst wordt behaald.

4. Experimentele Resultaten

De auteurs evalueerden de methoden op synthetische data met variërende dimensies en steekproefgroottes.

• Kalibratie (Type-I Fout):
  • mHSIC: Op bivariate data met omgevingsdimensies tot 500 bleef het empirische Type-I foutpercentage bij $\alpha=0.05$ strak rond het nominale niveau voor voldoende grote $n$. De auteurs merken een "eindsteekproef-vloek van de dimensionaliteit" op waarbij het foutpercentage oploopt als $d_{\text{ambient}} \gtrsim n^{0.875}$ vanwege resterende centrering-vertekening.
  • mdHSIC: Op taken voor gezamenlijke onafhankelijkheid met $d \in \{2, \dots, 10\}$ bleef het Type-I foutpercentage binnen $[0.036, 0.066]$ over alle geteste steekproefgroottes en dimensies, wat de verdelingsvrije kalibratie bevestigt.
• Kracht: Beide statistieken vertoonden monotoon toenemende kracht met toenemende afhankelijkheidssterkte en steekproefgrootte, presterend gelijk aan permutatie-gebaseerde baselines.
• Rekenefficiëntie:
  • mHSIC en mdHSIC waren 25 tot 60 keer sneller dan hun permutatie-gekalibreerde tegenhangers (HSIC-perm en dHSIC-perm met $B=200$).
  • Voor $n=16.000$ duurde mHSIC 0,042 seconden tegenover 2,532 seconden voor HSIC-perm.
  • De snelheidswinst schaalt met $n$ omdat de permutatiekosten lineair groeien met $B$, terwijl de martingaalkosten per test constant blijven.

5. Betekenis en Claims

Het artikel claimt de kalibratie-flesnek in kerngebaseerde onafhankelijkheidstests op te lossen. Door gebruik te maken van martingaalstructuren elimineren de auteurs de noodzaak voor kostbare permutatie-resampling, waardoor de rekenlast met twee orde van grootte wordt verminderd terwijl de statistische geldigheid behouden blijft.

• Permutatievrij: De belangrijkste betekenis is de vervanging van de $O(B n^2)$ permutatiestap door een enkele zoekopdracht naar een normaal-quantiel, waardoor de tests haalbaar worden voor grootschalige datasets waar permutatie ondoenlijk is.
• Robuustheid: De methoden zijn verdelingsvrij; de nullimiet is standaardnormaal ongeacht de onderliggende datawet, mits lichte momentvoorwaarden worden voldaan.
• Schaalbaarheid: De mdHSIC-statistiek adresseert specifiek het schaalbaarheidsprobleem bij het testen van gezamenlijke onafhankelijkheid in hoge dimensies, waar naïeve uitbreidingen falen door cumulerende vertekening.

De auteurs positioneren hun werk als een directe aanpassing van het martingaal MMD-paradigma (Chatterjee en Ramdas [2025]) aan het onafhankelijkheidsprobleem, en bieden een praktisch alternatief voor bestaande steekproefsplitsingsmethoden (zoals xHSIC) door de onder-driehoekige structuur te behouden die alle beschikbare paren in de tweede halve steekproef benut, waardoor de statistische kracht ten opzichte van rechthoekige kruis-blokbenaderingen wordt verbeterd.