Multiscale Cochran-Mantel-Haenszel Scanning for Conditional Dependency

1. O Problema

O artigo aborda o desafio de testar a Independência Condicional (IC) entre duas variáveis aleatórias $X$ e $Y$, dado um conjunto de variáveis de condicionamento $Z$ ($X \perp Y | Z$). Este é um problema fundamental em estatística e aprendizado de máquina, utilizado para seleção de variáveis, modelagem de densidade e descoberta de estruturas causais.

Os métodos existentes enfrentam limitações significativas:

• Métodos baseados em Kernel (RKHS): Embora robustos, geralmente possuem complexidade computacional $O(n^2)$, tornando-os inviáveis para grandes conjuntos de dados. Além disso, seu poder estatístico decai polinomialmente em dimensões altas e depende criticamente da escolha de parâmetros de banda.
• Métodos baseados em Discretização: Estratificam o espaço de $Z$ para criar tabelas de contingência locais. No entanto, enfrentam um paradoxo: as estratificações devem ser pequenas o suficiente para controlar o erro de discretização (evitando falsos positivos) e grandes o suficiente para conter amostras suficientes para ter poder estatístico. Em dimensões altas, isso exige que o tamanho da amostra por estrato cresça infinitamente, uma condição difícil de satisfazer na prática.
• Métodos de Regressão/Previsão: Frequentemente exigem estimativa não paramétrica de distribuições completas ou funções de média, o que se torna um gargalo em altas dimensões.

2. Metodologia Proposta: MultiCMH

Os autores propõem uma abordagem não paramétrica chamada MultiCMH (Multiscale Cochran-Mantel-Haenszel), que generaliza o teste clássico CMH (usado para tabelas $2 \times 2 \times T$) para espaços de amostra contínuos e de alta dimensão.

Principais Componentes da Metodologia:

1. Princípio da Condicionalidade e Estatísticas Ancilares:

   • O método condiciona nas estatísticas de ordem marginais (totais de margem), que são "quase ancilares" em relação à dependência condicional.
   • Isso permite que o teste opere sob uma assintótica de dados esparsos: a consistência do teste é garantida pelo aumento do número de estratos, e não pelo aumento do tamanho de cada estrato. Isso supera a limitação de métodos anteriores que exigem tamanhos de estrato infinitos.

2. Estratificação Recursiva (Mediana):

   • Para lidar com $Z$ contínuo e de alta dimensão, o algoritmo utiliza uma partição recursiva baseada em medianas amostrais (semelhante a uma árvore k-d).
   • O espaço é dividido em hiper-retângulos com contagens quase iguais.
   • Vantagens: É invariante a transformações monótonas (mudanças de unidades não alteram o resultado), robusto em altas dimensões (evita o problema da concentração de distâncias) e possui complexidade computacional de $O(n \log n)$.

3. Varredura Multiescala (Divide-and-Conquer):

   • Para variáveis contínuas $X$ e $Y$, o método aplica partições dicotômicas recursivas (árvores binárias) para discretizá-las em bins.
   • Isso transforma o problema global em uma série de testes locais em tabelas de contingência $2 \times 2 \times T$ (janelas de varredura) de diferentes resoluções.
   • Fatoração da Probabilidade: Sob a hipótese nula e condicionando nos totais marginais de cada estrato, a distribuição conjunta das tabelas de contingência fatoriza-se em produtos de distribuições independentes (hipergeométricas de Fisher).
   • Independência dos P-valores: Consequentemente, os p-valores dos testes CMH realizados em janelas aninhadas ou sobrepostas são assintoticamente independentes.

4. Correção de Múltiplos Testes Hierárquica:

   • O algoritmo aplica uma correção de Šidák em três estágios hierárquicos para controlar a Taxa de Erro Familiar (FWER):
     1. Dentro da mesma partição de produto ($I \times J$).
     2. Entre partições da mesma resolução.
     3. Através de todas as resoluções (escalas).
   • Isso permite identificar não apenas se há dependência, mas onde no espaço de suporte $(X, Y)$ essa dependência ocorre.

3. Contribuições Chave

• Generalização do CMH: Estende o teste clássico para espaços contínuos e multidimensionais, mantendo a capacidade de identificar a direção e a força da associação local.
• Consistência sem Crescimento de Tamanho de Estrato: Resolve o paradoxo da discretização ao provar consistência sob assintótica de dados esparsos (número de estratos $\to \infty$, tamanho do estrato fixo).
• Escalabilidade: O algoritmo possui complexidade quase linear $O(n \log n)$, tornando-o aplicável a conjuntos de dados com milhões de amostras e centenas de dimensões.
• Ferramenta Diagnóstica: Diferente de testes que apenas rejeitam a hipótese nula, o MultiCMH mapeia as regiões de dependência e estima os odds ratios locais, fornecendo insights sobre a natureza da relação condicional.
• Invariância e Robustez: O uso de medianas para estratificação torna o método robusto a mudanças de escala e unidades, e eficaz em altas dimensões onde métricas de distância falham.

4. Resultados Experimentais

Os autores realizaram simulações extensivas e um estudo de caso:

• Controle de Erro Tipo I (T1E): Em simulações com o modelo de ruído pós-não-linear (padrão na literatura), o MultiCMH controlou rigorosamente o erro Tipo I (nível 0.05) em diversas dimensões e tamanhos de amostra, enquanto outros métodos (como CCIT e RCIT) mostraram calibração inadequada.
• Poder Estatístico: O método demonstrou poder consistente, convergindo para 1 à medida que o tamanho da amostra aumenta. Ao contrário de muitos métodos baseados em distância ou kernel, o poder do MultiCMH não degrada significativamente com o aumento da dimensionalidade de $Z$.
• Eficiência Computacional: O MultiCMH foi o método mais rápido em todos os cenários. Em testes com $n=800$ e $d=128$, foi ordens de magnitude mais rápido que concorrentes como CDIT e GCM. Em escalas de até 1 milhão de amostras, manteve complexidade linear, enquanto outros métodos falharam por falta de memória ou tempo.
• Estudo de Caso (Uber): Aplicado a dados de solicitações de corridas da Uber (ETA vs. Decisão de Solicitação, condicionado ao Preço). O método rejeitou a independência condicional e identificou que a sensibilidade ao tempo de espera (ETA) aumenta significativamente para tempos de espera mais longos e varia sistematicamente com o contexto de precificação. Isso demonstrou a capacidade do método de revelar heterogeneidade estrutural nos dados.

5. Significância e Conclusão

O trabalho oferece uma solução prática e teoricamente fundamentada para o teste de independência condicional em cenários modernos de "Big Data". Ao combinar a robustez estatística do teste CMH com uma estratégia de varredura multiescala eficiente, o MultiCMH preenche uma lacuna crítica entre métodos teóricos complexos e ferramentas aplicáveis em larga escala.

A principal inovação reside na capacidade de realizar testes consistentes sem exigir que o tamanho da amostra por estrato cresça infinitamente, permitindo a detecção de dependências locais sutis em espaços de alta dimensão. Além disso, a capacidade de fornecer estatísticas resumidas (odds ratios) sobre a natureza da dependência torna o método uma ferramenta valiosa para análise exploratória e interpretação de modelos, indo além da simples rejeição da hipótese nula.