Weighted Conformal Clustering

Resumo Técnico: Agrupamento Conformal Ponderado

Formulação do Problema
O agrupamento (clustering) é uma ferramenta fundamental para descobrir estruturas latentes em dados não rotulados, mas os fluxos de trabalho padrão tipicamente resultam em atribuições "rígidas" de observações a agrupamentos sem uma quantificação rigorosa da incerteza de atribuição. Embora métodos existentes abordem a incerteza por meio de bootstrapping, testes globais de existência de agrupamentos ou conjuntos de credibilidade bayesianos, eles frequentemente negligenciam a incerteza específica inerente à atribuição de observações individuais.

Trabalhos recentes de [11] introduziram um arcabouço de inferência conformal para agrupamento, tratando a atribuição de rótulos como um problema preditivo. No entanto, existe uma limitação teórica crítica: os rótulos de calibração utilizados em [11] são sintéticos, gerados por um algoritmo de agrupamento dependente dos dados, e não por rótulos reais observados. Consequentemente, a suposição de permutabilidade (exchangeability) necessária para uma predição conformal válida é violada, levando a uma potencial subcobertura. O desafio é construir conjuntos de confiança para rótulos de agrupamento que mantenham garantias de cobertura em amostra finita, apesar desse descompasso distributivo entre os rótulos de calibração sintéticos e os rótulos latentes reais não observados.

Metodologia
Os autores propõem um arcabouço de Agrupamento Conformal Ponderado que aborda o descompasso distributivo formulando o problema como um deslocamento condicional de distribuição de rótulos. A metodologia central procede em três estágios:

1. Agrupamento Conformal de Divisão Ponderado por Oráculo:
   Os autores primeiro derivam um procedimento "oráculo" que alcança cobertura marginal exata em amostra finita. Esta abordagem utiliza predição conformal ponderada, onde os pesos são construídos para corrigir a discrepância entre a distribuição de rótulos sintéticos (induzida pelo algoritmo de agrupamento) e a verdadeira distribuição de rótulos latentes. Os pesos são definidos como razões de verossimilhança comparando a densidade de rótulos condicional real $p^*_{Y|X}$ com as probabilidades de rótulos sintéticos geradas pelo algoritmo de agrupamento. Embora teoricamente sólido, este procedimento de oráculo é computacionalmente intratável porque requer a avaliação da regra de agrupamento em conjuntos de dados aumentados de leave-one-out para cada ponto de calibração e ponto de teste.

2. Mecanismo de Calibração Aumentada:
   Para tornar o método computacionalmente viável, os autores introduzem um novo mecanismo de calibração aumentada. Em vez de ajustar o algoritmo de agrupamento separadamente no conjunto de calibração e repetidamente em conjuntos de leave-one-out, o algoritmo ajusta o modelo de agrupamento uma única vez em um conjunto de dados aumentado $D_{aug} = D_{ca} \cup \{x\}$, onde $D_{ca}$ é o conjunto de calibração e $x$ é o ponto de teste. Este ajuste único permite que os termos de verossimilhança sintética se fatorizem e se cancelem durante a normalização, reduzindo os pesos a uma forma de razão de verossimilhança pontual. Este mecanismo une as abordagens full-conformal e split-conformal, eliminando a necessidade de reajustes repetidos.

3. Construção de Peso Estimado:
   Como a verdadeira densidade condicional $p^*_{Y|X}$ é desconhecida, o método substitui os pesos de oráculo por pesos estimados usando um classificador suave $\hat{\pi}$ treinado em uma divisão de treinamento separada. O algoritmo final (Algoritmo 1) envolve:

   • Dividir os dados em conjuntos de treinamento e calibração.
   • Ajustar um algoritmo de agrupamento no conjunto de treinamento para gerar rótulos e um classificador suave.
   • Ajustar o algoritmo de agrupamento no conjunto de calibração aumentado ($D_{ca} \cup \{x\}$) para gerar rótulos sintéticos.
   • Alinhar os rótulos sintéticos com os rótulos de treinamento via uma permutação $\hat{\sigma}$.
   • Calcular escores de conformidade e construir o conjunto de confiança usando os pesos estimados derivados da razão entre a densidade condicional estimada e as probabilidades de agrupamento aumentadas.

Principais Contribuições
O artigo apresenta três contribuições primárias:

1. Novo Arcabouço: Introduz um arcabouço para quantificação de incerteza em agrupamento que modela explicitamente o problema como um deslocamento condicional de distribuição de rótulos, utilizando predição conformal ponderada para lidar com a natureza não permutável dos rótulos sintéticos.
2. Calibração Aumentada: Propõe um mecanismo de "calibração aumentada" computacionalmente tratável. Esta inovação remove o fardo computacional do reajuste leave-one-out enquanto retém os benefícios teóricos da predição conformal ponderada, oferecendo um novo princípio aplicável ao aprendizado não supervisionado além do agrupamento.
3. Garantias Teóricas: Os autores estabelecem limites de cobertura em amostra finita para o procedimento de peso estimado. A perda de cobertura é explicitamente limitada pela distância de variação total entre a distribuição de rótulos condicional estimada e a distribuição latente real. Diferente de abordagens anteriores, este arcabouço não depende de suposições de estabilidade de "substituição de um" (replace-one), pois o mecanismo de aumento estabiliza intrinsecamente o processo.

Resultados Empíricos
O método proposto (Algoritmo 1) é avaliado contra o método de agrupamento conformal de divisão (split conformal clustering) ([11]) e um método de corte ingênuo em diversos cenários:

• Modelos de Mistura Gaussiana (GMM): Tanto em configurações de baixa dimensão ($R^2$) quanto de alta dimensão ($R^{50}$), a abordagem ponderada mantém cobertura válida com tamanhos de conjuntos de confiança informativos (menores). Em alta dimensão usando agrupamento espectral, o método de divisão conformal produz conjuntos excessivamente grandes e pouco informativos, enquanto o método ponderado permanece informativo.
• Agrupamento Não Linear: Experimentos nos conjuntos de dados "three moons" e "two concentric circles" demonstram que o método ponderado mantém tamanhos de conjuntos informativos sobre uma gama mais ampla de níveis de ruído (variância) em comparação ao método de divisão conformal, que falha em produzir conjuntos informativos conforme o agrupamento se torna mais difícil.
• Aplicação MNIST: Aplicado ao agrupamento profundo no conjunto de dados MNIST, o método quantifica a incerteza com sucesso. Ele produz conjuntos de elemento único (singleton sets) para centros de agrupamento claros e conjuntos maiores para regiões de fronteira ambíguas, identificando corretamente dígitos difíceis de classificar.

Significância e Alegações
O artigo posiciona este trabalho como um passo substantivo adiante no campo emergente do agrupamento conformal. Ao tratar os rótulos sintéticos como indutores de um deslocamento de distribuição, os autores estendem a aplicabilidade da predição conformal além dos modelos de mistura paramétricos suaves considerados em trabalhos anteriores ([11]). O método é particularmente significativo para aplicações de agrupamento não linear e de alta dimensão, onde abordagens conformais padrão têm dificuldade em fornecer conjuntos de confiança informativos. Os autores alegam que seu arcabouço oferece uma abordagem mais rigorosa e versátil para a quantificação de incerteza, fornecendo garantias de cobertura válidas mesmo quando o algoritmo de agrupamento subjacente é complexo ou a distribuição dos dados não é padrão. O artigo conclui que o mecanismo de calibração aumentada representa um princípio metodológico mais amplo com potenciais aplicações no aprendizado não supervisionado além do contexto específico de agrupamento.