Approximate full conformal prediction in an RKHS

Resumo Técnico: Predição Conforme Total Aproximada em um RKHS

Definição do Problema
A predição conforme total é um framework livre de distribuição que constrói regiões de predição de confiança com cobertura garantida para uma ampla gama de estimadores. No entanto, sua aplicação prática é severamente limitada pela intratabilidade computacional. Para calcular a região de predição conforme total para um novo dado de entrada $X_{n+1}$, é necessário avaliar um escore de não conformidade para cada candidato possível de saída $y \in \mathcal{Y}$. Como o preditor subjacente $\hat{f}_{D_y}$ deve ser retreinado para cada candidato $y$ (onde $D_y$ inclui o novo ponto $(X_{n+1}, y)$), isso requer o treinamento de um número infinito de estimadores quando $\mathcal{Y} = \mathbb{R}$.

Alternativas existentes, como a predição conforme dividida (split-conformal) e a predição conforme cruzada (cross-conformal), reduzem os custos computacionais ao treinar um número fixo de preditores. No entanto, esses métodos incorrem em uma perda de informação ao descartar dados durante o treinamento ou divisão, resultando frequentemente em regiões de predição maiores e menos informativas. Outras abordagens baseadas em soluções de forma fechada (por exemplo, para regressão ridge) ou formas específicas de p-valor são limitadas a cenários estreitos e não se generalizam para funções de perda arbitrárias ou Espaços de Hilbert de Núcleo Reproduzível (RKHS).

Metodologia
Os autores propõem uma estratégia genérica para aproximar a região de predição conforme total de forma eficiente, sem dividir os dados. O núcleo da metodologia envolve:

1. Preditores Aproximados: Em vez de retreinar o preditor para cada candidato $y$, o método aproxima o preditor $\hat{f}_{D_y}$ usando um preditor fixo $\hat{f}_{D_z}$ (treinado em um ponto fixo $z$) ou uma correção de primeira ordem baseada em funções de influência.
2. Escores de Não Conformidade Aproximados: Usando o preditor aproximado, os autores definem escores de não conformidade aproximados $\tilde{S}_{D_y}$.
3. Limitação do Erro de Aproximação: Crucialmente, o método deriva limites superiores explícitos ($\tau$) sobre a discrepância entre os escores reais e os escores aproximados. Esses limites dependem da suavidade da função de perda e das propriedades do núcleo (kernel).
4. Sanduíche da Região: Ao incorporar esses limites de erro no cálculo do p-valor conforme, os autores constroem uma região aproximada "superior" ($\hat{C}^{up}$) e uma região aproximada "inferior" ($\hat{C}^{lo}$). A verdadeira região conforme total é garantida como estando contida dentro deste sanduíche ($\hat{C}^{lo} \subseteq \hat{C}^{full} \subseteq \hat{C}^{up}$).
5. Quantificação da Espessura: Uma nova métrica chamada "espessura" (thickness) é introduzida para quantificar o volume da diferença simétrica entre as regiões de predição aproximada e a conforme total, fornecendo uma medida da proximidade da aproximação além da simples probabilidade de cobertura.

O artigo desenvolve três níveis de aproximação baseados nas suposições de suavidade da função de perda:

• Nível 0 (Estabilidade Uniforme): Utiliza constantes Lipschitz uniformes para as funções de perda e de escore. Isso recupera limites semelhantes às abordagens de estabilidade uniforme, mas permite funções de perda gerais em RKHS.
• Nível 1 (Estabilidade Local): Explora a diferenciabilidade da função de perda para derivar limites de estabilidade local que variam com $y$, estreitando as constantes de aproximação.
• Nível 2 (Funções de Influência): Aproveita a suavidade de ordem superior (função duas e três vezes diferenciável) e funções de influência (função de influência de Bouligand) para criar uma aproximação de preditor que depende de $y$ via uma expansão de Taylor de primeira ordem. Isso resulta em taxas de convergência mais rápidas para o erro de aproximação.

Principais Contribuições

• Estratégia de Aproximação Genérica: O artigo fornece um framework de aproximação genérico e livre de distribuição para regiões conforme totais em configurações de RKHS com funções de perda gerais (não quadráticas), incluindo perdas robustas como Logcosh, Pseudo-Huber e Pinball suavizada.
• Garantias Não Assintóticas: Diferente de abordagens anteriores baseadas em funções de influência que oferecem apenas garantias assintóticas, este trabalho fornece limites não assintóticos sobre a qualidade da aproximação e garante que a região resultante seja uma região de confiança válida (cobertura $\geq 1-\alpha$).
• Métrica de Espessura: A introdução da "espessura" permite a quantificação da discrepância entre as regiões de predição aproximada e a conforme total em termos de volume (medida de Lebesgue), não apenas probabilidade de cobertura.
• Melhores Taxas de Convergência: Ao utilizar funções de influência e suposições de suavidade de ordem superior, os autores demonstram que o erro de aproximação decai a uma taxa mais rápida ($O(n^{-1+r+\min(-1+2r, 0)})$) comparado aos limites de estabilidade uniforme ($O(n^{-1+r})$), particularmente quando o parâmetro de regularização $\lambda$ decai lentamente.

Resultados

• Limites Teóricos: A análise teórica mostra que a espessura da aproximação é limitada superiormente por termos dependentes das propriedades do kernel, do parâmetro de regularização e da suavidade da perda. Para funções de perda suaves, os limites tornam-se significativamente mais estreitos à medida que o tamanho da amostra $n$ aumenta.
• Desempenho Empírico: Experimentos com dados sintéticos (Friedman1) comparam quatro estratégias: Split-conformal, Estabilidade Uniforme (Nível 0), Estabilidade Local (Nível 1) e Função de Influência (Nível 2).
  • Cobertura: Todos os métodos propostos alcançam cobertura empírica próxima ao nível alvo ($1-\alpha = 0.9$).
  • Tamanho da Região: O método baseado em Função de Influência produz as regiões de predição mais estreitas (mais informativas) com baixa variância, superando tanto o método split-conformal quanto os métodos baseados em estabilidade.
  • Computação: Embora o método de Função de Influência exija mais tempo de computação (devido à inversão da matriz Hessiana), ele permanece tratável. O método de Estabilidade Local oferece um compromisso favorável entre precisão e custo computacional.
• Visualização: Gráficos log-log da lacuna de "espessura" versus tamanho da amostra confirmam as taxas de convergência teóricas, mostrando que a abordagem de Função de Influência converge mais rápido que a abordagem de estabilidade uniforme.

Significância e Alegações
Os autores alegam que seu trabalho preenche a lacuna entre a otimalidade teórica da predição conforme total e a viabilidade computacional dos métodos de predição conforme dividida (split-conformal). Ao evitar a divisão de dados, o método proposto utiliza o conjunto de dados completo para o treinamento, preservando a informação e gerando regiões de predição mais estreitas. O framework é significativo porque estende a aproximação conforme total a uma ampla classe de funções de perda e configurações de RKHS, fornecendo garantias não assintóticas rigorosas tanto sobre a cobertura quanto sobre a "estreiteza" (espessura) das regiões resultantes. O artigo enfatiza que, embora a aproximação seja computacionalmente eficiente (exigindo apenas um ou poucos avaliações do preditor), ela mantém a validade livre de distribuição do framework conforme total.