Resumo Técnico: Predição Conforme Online Livre de Parâmetros e Condicional por Grupo

1. Configuração do Problema e Motivação

Modelos de aprendizado de máquina são cada vez mais implantados em ambientes de alto risco e não estacionários (ex: triagem médica, veículos autônomos) onde as distribuições de dados sofem mudanças ao longo do tempo, violando a suposição de permutabilidade (exchangeability) exigida pela Predição Conforme (CP) padrão. A Predição Conforme Online (OCP) aborda isso gerando uma sequência de conjuntos de predição para fluxos de dados adversariais. No entanto, os métodos de OCP padrão garantem apenas a cobertura marginal (ou seja, a taxa de erro global aproxima-se de $1-\alpha$). Essa garantia marginal pode mascarar uma subcobertura sistemática para subpopulações específicas, levando a problemas de justiça (fairness) e segurança.

Embora trabalhos anteriores tenham proposto a OCP Condicional por Grupo (G-OCP) para garantir garantias de cobertura para grupos específicos, os métodos existentes (ex: GCACI) dependem de taxas de aprendizado (step sizes) que devem ser ajustadas manualmente. Em ambientes de dados adversariais ou em mudança, o ajuste de taxas de aprendizado é problemático porque:

1. Não há um conjunto de validação disponível para ajuste.
2. Mudanças arbitrárias nos dados podem tornar uma taxa de aprendizado previamente "boa" inadequada.
3. Os métodos de OCP livres de parâmetros existentes (ex: UP-OCP) alcançam apenas a cobertura marginal, não as garantias condicionais por grupo.

O problema central abordado é o design de um algoritmo de OCP livre de parâmetros que forneça simultaneamente garantias rigorosas de cobertura condicional por grupo sem exigir o ajuste manual de hiperparâmetros.

2. Metodologia: POGO

Os autores propõem o POGO (Portfolios for Online Group Conformal), o primeiro algoritmo livre de parâmetros para G-OCP. A metodologia baseia-se no conceito de otimização de Portfólio Universal (UP), aplicado anteriormente à OCP marginal (UP-OCP), e o estende para lidar com múltiplos grupos sobrepostos.

2.1 Formulação do Problema

Dado um fluxo de dados $(X_t, Y_t)$ e um preditor $\hat{Y}_t$, o objetivo é aprender uma sequência de raios $\tau_t$ tal que o intervalo de predição $I_t = [\hat{Y}_t - \tau_t, \hat{Y}_t + \tau_t]$ satisfaça:
$$\lim_{T \to \infty} \left| \frac{1}{T_j} \sum_{t=1}^T \mathbb{1}\{Y_t \in I_t\} c_j(X_t) - (1-\alpha) \right| = 0$$
para todos os $k$ grupos, onde $c_j(X_t) \in [0, 1]$ é uma função indicadora suave para a participação no grupo, e $T_j$ é a contagem cumulativa do grupo $j$.

2.2 Parametrização Linear

Ao contrário da OCP padrão que aprende um raio escalar, o POGO aprende um vetor de parâmetros $k$-dimensional $\theta_t \in \mathbb{R}^k$. O raio é parametrizado como uma função linear do vetor de participação no grupo $c(X_t)$:
$$\tau_t(X_t) = \langle \theta_t, c(X_t) \rangle$$
Isso permite que o algoritmo atribua diferentes raios com base nas participações de grupo específicas de uma amostra, enquanto garante a produção de um único intervalo de predição unificado.

2.3 Mecanismo de Otimização de Portfólio

O POGO trata o aprendizado de $\theta_t$ como um problema de otimização de portfólio.

1. Subgradientes como Erros: O algoritmo define uma perda de quantile (perda pinball) para cada grupo. O subgradiente $g_t$ desta perda quantifica o erro de subcobertura. Especificamente, a $j$-ésima entrada da soma do subgradiente cumulativo $\sum g_{t,j}$ corresponde ao erro de subcobertura para o grupo $j$.
2. Processos de Riqueza: Para cada grupo $j$, o POGO constrói um "mercado" com duas ações. Os retornos destas ações dependem de se a predição atual cobre o rótulo verdadeiro:
   • Se a predição falha (subcobertura), uma ação gera um alto retorno.
   • Se a predição cobre, a outra ação gera um retorno modesto.
3. Portfólio Universal (UP): O POGO emprega o algoritmo de Portfólio Universal (UP) para aprender uma sequência de pesos de portfólio $\lambda_{t,j}$ para cada grupo $j$. O objetivo é maximizar o crescimento logarítmico da "riqueza" $W_{t,j}$ associada a cada grupo.
4. Atualização de Parâmetros: Os parâmetros $\theta_{t,j}$ são derivados diretamente dos processos de riqueza $W_{t,j}$ e dos pesos do portfólio $\lambda_{t,j}$, garantindo que os subgradientes cumulativos cresçam lentamente. Esse crescimento lento traduz-se diretamente em uma subcobertura condicional por grupo limitada.

Crucialmente, este processo é livre de parâmetros; ele não requer uma taxa de aprendizado $\eta$ ou tamanho de passo, baseando-se nas propriedades intrínsecas do algoritmo de Portfólio Universal.

3. Principais Contribuições

1. Primeiro Algoritmo G-OCP Livre de Parâmetros: A introdução do POGO, que fornece garantias de cobertura condicional por grupo sem ajuste manual de taxas de aprendizado.
2. Garantias Rigorosas de Tempo Finito: Os autores estabelecem limites de cobertura teóricos para o POGO. A taxa de subcobertura para o grupo $j$ é limitada por:
   $$\text{MisCov}_T(c_j) \leq \frac{1}{T_j} \left[ U_T(k) + \sqrt{2T_j \alpha(1-\alpha) U_T(k)} \right]$$
   onde $U_T(k)$ escala logaritmicamente com o número de grupos $k$ e o tempo $T$. Isso representa os melhores resultados conhecidos de cobertura por grupo em tempo finito.
3. Escalabilidade Superior: A análise teórica mostra que o limite de erro do POGO depende logaritmicamente do número de grupos ($O(\ln k)$), enquanto os métodos dependentes de parâmetros existentes (como o GCACI) escalam com $\sqrt{k}$ e dependem fortemente da escolha da taxa de aprendizado.
4. Saída de Intervalo Único: Ao contrário de abordagens ingênuas que executam algoritmos de OCP separados para cada grupo (produzindo $k$ raios diferentes), o POGO produz um único raio $\tau_t$ para cada amostra, evitando problemas com intervalos conflitantes e potenciais vazamentos de privacidade em relação à participação no grupo.

4. Resultados Experimentais

Os autores avaliam o POGO em conjuntos de dados sintéticos e do mundo real, comparando-o com o GCACI (o padrão atual para OCP condicional por grupo) e o UP-OCP (OCP marginal livre de parâmetros).

4.1 Experimentos Sintéticos

• Scores Limitados e Variáveis Gradualmente: O POGO atinge as taxas de cobertura alvo dentro de 3% para todos os grupos e produz os menores raios médios em comparação com variantes do GCACI. Ele mantém alta adaptabilidade, com a sequência mais longa de eventos de subcobertia consecutiva sendo comparável ao melhor GCACI ajustado.
• Mudanças Abruptas: Quando as distribuições de dados mudam abruptamente, o POGO permanece robusto. Em contraste, o GCACI com uma taxa de aprendizado fixa (mesmo uma bem ajustada como $\eta=0.01$) sofre de baixa adaptabilidade, exibindo longas sequências de subcobertura até que a taxa de aprendizado seja efetivamente "reajustada" pelos dados.
• Scores Crescentes Não Limitados: Em cenários onde os scores de não conformidade crescem quadraticamente para um grupo específico, a maioria das variantes do GCACI falha em atingir a cobertura alvo. O POGO atinge consistentemente coberturas mais próximas dos níveis alvo, particularmente em requisitos de cobertura elevados ($1-\alpha \in [0.9, 0.95]$).

4.2 Dados do Mundo Real

• MIMIC-IV (Tempo de Permanência na UTI): Usando dados de pacientes (raça, seguro, sexo como grupos), o POGO atinge uma cobertura comparável ao GCACI, mas com tamanhos de conjuntos de predição (raios) menores.
• Mercado de Ações (Apple, Delta, Boeing): Para predição de preços diários, o Pogo demonstra novamente um desempenho competitivo, alcançando a cobertura alvo com tamanhos de conjunto menores que o GCACI.
• Compromissos (Trade-offs): Embora o POGO às vezes exiba sequências de subcobertura consecutiva ligeiramente mais longas do que o melhor GCACI ajustado em regimes estáticos específicos, ele supera significativamente o GCACI em regimes dinâmicos ou de mudança, onde o ajuste é impossível.

5. Significância e Alegações

O artigo afirma que o POGO estabelece uma base para a quantificação de incerteza justa e robusta em ambientes de mudança. Ao unificar a cobertura condicional por grupo com o aprendizado online livre de parâmetros, o método elimina a necessidade de ajuste manual de hiperparâmetros, o que é um gargalo crítico em configurações adversariais ou não estacionárias.

Os autores enfatizam que:

• O POGO fornece as melhores garantias de cobertura por grupo em tempo finito conhecidas.
• Ele alcança essas garantias sem a fragilidade da seleção da taxa de aprendizado.
• Oferece uma solução prática para aplicações de alto risco onde a justiça entre subpopulações é necessária e onde as distribuições de dados não podem ser assumidas como estáticas ou permutáveis.

O artigo conclui modestamente, observando que, embora o POGO utilize uma especificação linear para os raios, trabalhos futuros poderiam explorar modelos mais ricos para o raio e estender essas ferramentas para outras formas de quantificação de incerteza online, como calibração.