Resumo Técnico: Um Teste de Independência com Kernel Martingala

1. Declaração do Problema

O artigo aborda os desafios computacionais e de calibração estatística inerentes aos testes de independência baseados em kernels, especificamente o Critério de Independência Hilbert–Schmidt (HSIC) e sua extensão à independência conjunta, dHSIC.

As implementações padrão de HSIC e dHSIC dependem de estatísticas V degeneradas. Sob a hipótese nula de independência ($H_0$), as estatísticas reescaladas convergem para uma soma ponderada de variáveis aleatórias $\chi^2$, onde os pesos dependem da distribuição conjunta desconhecida dos dados. Consequentemente, a calibração prática exige testes de permutação para aproximar a distribuição nula. Esse processo envolve recalcular a estatística $B$ vezes (tipicamente $B \ge 200$), inflando o custo computacional por teste de $O(n^2)$ para $O(B n^2)$, um fator de duas ordens de grandeza.

Os autores visam eliminar completamente a etapa de permutação ao construir estatísticas com um limite nulo conhecido e livre de distribuição (normal padrão), reduzindo assim o custo por teste para igualar a complexidade quadrática da própria estatística V enviesada.

2. Metodologia

A abordagem proposta adapta a recente construção de MMD martingala para testes de duas amostras (Chatterjee e Ramdas [2025]) ao cenário de independência. A ideia central é transformar o estimador quadrático de tempo padrão em uma soma de diferenças martingala, que pode então ser studentizada para convergir a uma distribuição normal padrão via o Teorema do Limite Central (CLT) de martingala auto-normalizada.

2.1 A Estatística mHSIC (Independência Bivariada)

Para testar a independência entre duas variáveis $X$ e $Y$, os autores definem o mHSIC.

• Construção: A estatística é uma soma triangular inferior studentizada do produto de Hadamard de duas matrizes de Gram centradas empiricamente ($K_X$ e $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}$$
• Studentização: A estatística é normalizada por sua variação quadrática empírica $\hat{\sigma}_n$.
• Base Teórica: Sob $H_0$, o produto de kernels $\bar{k}_X \bar{k}_Y$ (onde $\bar{k}$ denota kernels centrados na população) forma uma sequência de diferenças martingala. Embora a matriz de centragem empírica $H$ introduza um viés, os autores provam que esse viés é $O_P(1/\sqrt{n})$ e assintoticamente negligenciável após a studentização.
• Propriedades: Sob condições limitadas de momento de quarta ordem, o mHSIC converge para $\mathcal{N}(0, 1)$ independentemente da lei dos dados. É consistente contra cada alternativa fixa e mantém um custo computacional de $O(n^2)$ sem divisão de amostra.

2.2 A Estatística mdHSIC (Independência Conjunta)

Para testar a independência conjunta entre $d$ variáveis ($X_1, \dots, X_d$), uma extensão ingênua do mHSIC falha.

• O Fracasso do Produto Direto: Substituir o kernel bivariado por um produto $d$-plo de kernels centrados empiricamente resulta em um viés agregado de $O_P(d/\sqrt{n})$. Quando o número de variáveis $d$ excede $\sqrt{n}$, esse viés domina a escala studentizada, quebrando a calibração normal padrão.
• A Solução de Meia-Amostra Martingala (mdHSIC): Para resolver isso, os autores introduzem uma única divisão de meia-amostra:
  1. Divisão: A amostra é dividida em $S_1$ (primeira metade) e $S_2$ (segunda metade).
  2. Centragem: As incorporações de médias e kernels centrados são estimados usando apenas $S_1$.
  3. Execução Martingala: A soma martingala auto-normalizada triangular inferior é computada usando os kernels centrados em $S_1$ aplicados a pares dentro de $S_2$.
• Base Teórica: Essa construção garante que o resíduo de média condicional do produto de kernels seja $O_P(m^{-d/2})$ (onde $m \approx n/2$). Esse resíduo é exponencialmente pequeno em $d$, tornando-o negligenciável para qualquer $d \ge 2$ fixo.
• Propriedades: O mdHSIC converge para $\mathcal{N}(0, 1)$ para qualquer $d$ fixo sob independência conjunta. O custo por teste é $O(d n^2)$, linear em $d$, evitando o fator de permutação $B$.

3. Contribuições Principais

1. mHSIC: Uma estatística livre de permutação e livre de divisão de amostra para independência bivariada que converge para uma distribuição normal padrão sob a nula, igualando o custo $O(n^2)$ da estatística V enviesada do HSIC.
2. mdHSIC: Uma estatística livre de permutação para independência conjunta de $d$ variáveis. Corrige o viés de centragem empírica de extensões de produto direto via uma única divisão de meia-amostra, garantindo normalidade assintótica para qualquer $d$ fixo com complexidade $O(d n^2)$.
3. Garantias Teóricas: Provas de convergência para $\mathcal{N}(0, 1)$ sob a nula (Teoremas 3 e 6) e consistência contra alternativas fixas, baseadas no CLT de martingala auto-normalizada (Fan [2018]).
4. Validação Empírica: Demonstração de que ambas as estatísticas correspondem às taxas de erro Tipo-I e ao poder dos testes das linhas de base calibradas por permutação, enquanto alcançam acelerações significativas.

4. Resultados Experimentais

Os autores avaliaram os métodos em dados sintéticos com dimensões e tamanhos de amostra variados.

• Calibração (Erro Tipo-I):
  • mHSIC: Em dados bivariados com dimensões ambientais de até 500, a taxa de erro Tipo-I empírica em $\alpha=0.05$ permaneceu próxima ao nível nominal para $n$ suficientemente grande. Os autores notam uma "maldição da dimensionalidade de amostra finita" onde a taxa de erro infla se $d_{\text{ambient}} \gtrsim n^{0.875}$ devido ao viés de centragem residual.
  • mdHSIC: Em tarefas de independência conjunta com $d \in \{2, \dots, 10\}$, a taxa de erro Tipo-I permaneceu dentro de $[0.036, 0.066]$ em todos os tamanhos de amostra e dimensões testados, confirmando a calibração livre de distribuição.
• Poder: Ambas as estatísticas exibiram aumentos monotônicos de poder com a força de dependência e o tamanho da amostra, igualando o desempenho das linhas de base baseadas em permutação.
• Eficiência Computacional:
  • mHSIC e mdHSIC foram 25 a 60 vezes mais rápidos que suas contrapartes calibradas por permutação (HSIC-perm e dHSIC-perm com $B=200$).
  • Para $n=16.000$, o mHSIC levou 0,042 segundos, comparado a 2,532 segundos para o HSIC-perm.
  • A aceleração escala com $n$ porque o custo de permutação cresce linearmente com $B$, enquanto o custo martingala permanece constante por teste.

5. Significado e Alegações

O artigo alega resolver o gargalo de calibração nos testes de independência baseados em kernels. Ao aproveitar estruturas martingala, os autores eliminam a necessidade de reamostragem por permutação dispendiosa, reduzindo o ônus computacional em duas ordens de grandeza enquanto preservam a validade estatística.

• Livre de Permutação: O significado principal é a substituição da etapa de permutação $O(B n^2)$ por uma única consulta de quantil normal, tornando os testes viáveis para conjuntos de dados em grande escala onde a permutação é proibitiva.
• Robustez: Os métodos são livres de distribuição; o limite nulo é normal padrão independentemente da lei subjacente dos dados, desde que condições suaves de momento sejam atendidas.
• Escalabilidade: A estatística mdHSIC aborda especificamente o problema de escalabilidade no teste de independência conjunta de alta dimensionalidade, onde extensões ingênuas falham devido ao viés cumulativo.

Os autores posicionam seu trabalho como uma adaptação direta do paradigma de MMD martingala (Chatterjee e Ramdas [2025]) ao problema de independência, oferecendo uma alternativa prática aos métodos existentes de divisão de amostra (como xHSIC) ao reter a estrutura triangular inferior que utiliza todos os pares disponíveis na segunda metade da amostra, melhorando assim o poder estatístico em relação às abordagens de blocos cruzados retangulares.