Resumo Técnico: Apostando em Momentos – Legendre Jumper Martingales para Testes de Exchangeabilidade Online

Declaração do Problema

Na predição conformal, a validade dos conjuntos de predição depende da suposição de exchangeabilidade, o que implica que a sequência de p-valores gerada por um transdutor conformal é independente e identicamente distribuída (IID) de acordo com uma distribuição uniforme em $[0, 1]$. Violações dessa suposição indicam mudanças distributivas.

Embora martingais de teste conformal (CTMs) sejam usados para testar a exchangeabilidade online, o Simple Jumper (SJ) padrão (Vovk et al., 2022) possui uma limitação crítica: ele utiliza uma função de aposta linear baseada no polinômio de Legendre deslocado de primeiro grau. Consequentemente, o SJ é geometricamente restrito à detecção de mudanças na média (localização) dos p-valores. Ele falha em acumular riqueza significativa quando a mudança de distribuição preserva a média, mas altera momentos de ordem superior, como variância, assimetria ou curtose. Além disso, tentativas de combinar múltiplas estratégias de aposta frequentemente sofrem com o "imposto de salto" (jumping tax), onde o capital é diluído em um espaço de estados que cresce exponencialmente, dificultando severamente a velocidade de detecção.

Metodologia

O artigo propõe uma família de martinais de teste conformal baseados em polinômios de Legendre deslocados ($\tilde{P}_k$), que são ortogonais no intervalo $[0, 1]$. Esses polinômios servem como a base para funções de aposta capazes de detectar desvios em momentos específicos da distribuição dos p-valores.

1. Simple Legendre Jumper (SLJ)

O SLJ generaliza o Simple Jumper substituindo a função de aposta linear por um polinômio de Legendre deslocado de grau $k$ arbitrário:
$$f^{(k)}_\epsilon(p) = 1 + \epsilon \tilde{P}_k(p)$$
onde $\epsilon$ é um parâmetro selecionado de uma grade discreta.

• Mecanismo: Para $k=1$, ele recupera o SJ padrão (detectando mudanças de média); para $k=2$, detecta mudanças de variância; para $k=3$, assimetria; e assim por diante.
• Limitação: Apostar exclusivamente em um único grau $k$ faz com que o martinal perca mudanças dominantes em outros momentos, levando a uma acumulação de evidência subótima.

2. Product Legendre Jumper (PLJ)

Para capturar desvios complexos e multimodais simultaneamente, o PLJ combina funções de aposta de múltiplos graus $K$ em um único produto:
$$f^K_\epsilon(p) = \frac{\prod_{k \in K} (1 + \epsilon_k \tilde{P}_k(p))}{Z(\epsilon)}$$
onde $Z(\epsilon)$ é uma constante de normalização necessária para $|K| \ge 3$ para garantir que a integral da função de aposta seja igual a 1.

• O "Imposto de Salto": O PLJ mantém uma cadeia de Markov sobre o espaço de estados conjunto $\mathcal{E} = \prod_{k \in K} \mathcal{E}_k$. À medida que o número de graus $|K|$ aumenta, o tamanho do espaço de estados cresce exponencialmente ($|\mathcal{E}| = g^{|K|}$). O "imposto de salto" refere-se à diluição do capital: quando o ambiente muda, o mecanismo de salto distribui o novo capital uniformemente através deste enorme espaço de estados, atrasando a concentração de riqueza na estratégia de aposta ideal.

3. Variational Legendre Jumper (VLJ)

Para resolver o escalonamento exponencial do PLJ, os autores introduzem o Variational Legendre Jumper, inspirado em aproximações de campo médio (mean-field) da inferência variacional.

• Desacoplamento: Em vez de uma única cadeia de Markov sobre o espaço do produto, o VLJ executa $|K|$ sub-jumpers independentes (um para cada grau $k \in K$).
• Consenso: Em cada etapa, o VLJ calcula um parâmetro de consenso $\bar{\epsilon}_k$ para cada grau baseado na média ponderada pela riqueza do estado do sub-jumper.
• Aposta Global: O martinal global atualiza o produto normalizado das funções de aposta avaliadas nesses parâmetros de consenso.
• Complexidade: Isso reduz o custo computacional de exponencial $O(g^{|K|})$ para linear $O(|K| \cdot g)$, tornando o teste de momentos de ordem superior computacionalmente viável com perda mínima de poder estatístico.

4. Composite Legendre Jumper

Seguindo o framework de Vovk et al. (2022), o Composite Legendre Jumper faz a média do martinal base (SLJ, PLJ ou VLJ) sobre uma grade de taxas de salto $J \in \{10^{-4}, \dots, 1\}$.

• Robustez: Isso garante robustez quando a escala de tempo da mudança distributiva é desconhecida.
• Piso de Riqueza: A inclusão de $J=1$ garante que o martinal nunca caia abaixo de $1/|\mathcal{E}|$, fornecendo um piso absoluto de riqueza sob exchangeabilidade que as variantes de taxa fixa não possuem.

Principais Contribuições

1. Generalização de Funções de Aposta: A introdução do Simple Legendre Jumper, que estende a função de aposta linear do Simple Jumper para polinômios de Legendre deslocados de grau arbitrário, permitindo a detecção de desvios de variância, assimetria e momentos de ordem superior.
2. Endereçamento do Imposto de Salto: O desenvolvimento do Product Legendre Jumper para capturar desvios conjuntos, seguido pelo Variational Legendre Jumper, que fatoriza o problema de adaptação conjunta via aproximação de campo médio. Isso reduz com sucesso o escalonamento do espaço de estados de exponencial para linear, mantendo o poder estatístico.
3. Robustez Composta: A integração desses métodos no Composite Legendre Jumper, que mistura sobre as escalas de tempo de salto para fornecer adaptação automática a escalas de tempo de mudança desconhecidas e um piso de riqueza garantido sob a hipótese nula.
4. Validação Empírica: Demonstração em uma tarefa de classificação do mundo real (dataset Wine Quality) mostrando que os métodos combinados (PLJ e VLJ) superam consistentemente os martinais de grau único sob mudanças distributivas, enquanto a aproximação variacional incorre em perda negligível em comparação ao produto exato.

Resultados

Os autores avaliaram os métodos propostos no dataset Wine Quality usando um classificador de vizinho mais próximo conformal sob quatro ordenações de dados: embaralhados (exchangeáveis), mudanças abruptas de pontos de mudança (Red $\to$ White, White $\to$ Red) e ordem original.

• Exchangeabilidade: Sob dados embaralhados, todos os martinais permaneceram próximos de zero ou declinaram levemente, confirmando que não geram falsos alarmes.
• Mudança Distributiva: Sob ordenações não-exchangeáveis, os Product e Variational Legendre Jumpers com $K=\{1, 2, 3\}$ alcançaram consistentemente os valores mais altos de log-martinal final, superando o Simple Legendre Jumper de grau único ($k=1$) em 30%–60% em escala de log de evidência.
• Falha de Grau Único: Martinais que apostam exclusivamente em variância ($k=2$) ou assimetria ($k=3$) tiveram desempenho ruim quando a mudança envolveu múltiplos momentos, acumulando ordens de magnitude menos evidência do que as abordagens combinadas.
• Eficiência vs. Poder: O Variational Legendre Jumper (VLJ) igualou quase exatamente o desempenho do Product Legendre Jumper (PLJ), mas exigiu significativamente menos estados (ex: 15 estados vs. 125 estados para $K=\{1, 2, 3\}$).
• Superioridade do Composite: O Composite Legendre Jumper superou decisivamente as variantes de taxa fixa sob mudanças distributivas (alcançando $\log_{10} M_n \approx 100$ vs. taxa fixa $\approx 90$) e evitou a acumulação lenta de perdas observada nos martinais de taxa fixa sob exchangeabilidade.

Significância e Alegações

O artigo alega que o Composite Legendre Jumper deve ser a escolha padrão para praticantes quando a escala de tempo das mudanças distributivas é desconhecida. Ele oferece uma solução robusta que:

1. Detecta desvios complexos e multimodais da uniformidade que as funções de aposta lineares perdem.
2. Evita a "maldição da dimensionalidade" associada a estratégias de aposta conjunta através da fatoração variacional.
3. Fornece um piso de riqueza teórico e prático, garantindo estabilidade sob a hipótese nula.

Os autores observam que, embora a aproximação variacional performe empiricamente no mesmo nível do produto exato, os limites teóricos sobre a perda de poder estatístico devido à fatoração de campo médio permanecem um problema em aberto. Eles também sugerem que trabalhos futuros possam explorar a seleção de graus polinomiais baseada em dados (analogamente à abordagem de Ledwina para o teste suave de Neyman) para otimizar ainda mais a eficiência. A implementação está disponível no pacote Python online-cp.