Inference for Clustering: Conformal Sets for Cluster Labels

Resumo Técnico: Inferência para Agrupamento (Clustering) – Conjuntos Conformais para Rótulos de Cluster

1. O Problema

O agrupamento (clustering) é uma tarefa fundamental de aprendizado não supervisionado amplamente utilizada em ciência e indústria. No entanto, a quantificação da incerteza nas atribuições de rótulos de cluster é raramente abordada com garantias rigorosas.

• Desafio Central: Os rótulos de cluster não são observados (são latentes); eles são estimados a partir dos dados.
• Falha dos Métodos Atuais:
  • A aplicação ingênua de métodos de inferência conformal (projetados para classificação supervisionada) usando rótulos determinísticos estimados viola a premissa de troca (exchangeability), levando a uma cobertura subestimada (under-coverage).
  • Métodos baseados em "corte" (cutoff) de probabilidades suaves (soft labels) tendem a ser ou muito conservadores (conjuntos de confiança grandes e não informativos) ou falham em calibrar a incerteza corretamente em amostras finitas.
• Objetivo: Desenvolver um framework que produza conjuntos de confiança para rótulos de cluster que garantam uma cobertura marginal válida ($1-\alpha$) de forma agnóstica ao modelo e livre de distribuição, mesmo quando os rótulos são estimados.

2. Metodologia Proposta

Os autores propõem um novo framework baseado em Inferência Conformal Dividida com Rótulos Estocásticos (Split Conformal Clustering with Stochastic Labels).

A. Abordagens Ingênuas (e por que falham):

1. Corte de Probabilidade Suave: Definir o conjunto de confiança como os rótulos cuja soma de probabilidades excede $1-\alpha$. Falha porque as probabilidades estimadas não são bem calibradas e o método não se adapta à variabilidade da estimação.
2. Conformal Dividido com Rótulos Duros (Determinísticos): Treinar um classificador em rótulos de cluster obtidos de um conjunto de treino e calibrar em um conjunto de calibração. Falha porque a atribuição determinística não reflete a incerteza real, quebrando a troca e causando subcobertura severa.

B. O Algoritmo Proposto (Algoritmo 1):
O método introduz estocasticidade no processo de agrupamento para restaurar a validade inferencial.

1. Divisão dos Dados: Os dados não rotulados são divididos aleatoriamente em conjuntos de treino e calibração.
2. Agrupamento Estocástico: Em vez de atribuir um rótulo único, o algoritmo de agrupamento (ex: Mistura de Gaussianas) gera vetores de probabilidade (rótulos suaves). Para o conjunto de treino e calibração, os rótulos são amostrados dessas distribuições de probabilidade (usando uma distribuição categórica).
3. Treinamento do Classificador: Um classificador "soft" (que prevê vetores de probabilidade) é treinado no conjunto de treino usando os rótulos amostrados.
4. Alinhamento de Rótulos: Como os rótulos de treino e calibração podem sofrer permutações (devido à natureza não supervisionada), um alinhamento ótimo é encontrado no conjunto de calibração para minimizar a discordância entre as previsões do classificador e os rótulos amostrados.
5. Construção do Conjunto de Confiança:
   • Calculam-se scores de conformidade no conjunto de calibração.
   • Define-se um limiar baseado na distribuição empírica desses scores.
   • Para um novo ponto de teste $x$, o conjunto de confiança $\hat{C}(x)$ contém todos os rótulos $y$ cujo score de conformidade está abaixo do limiar.

3. Contribuições Teóricas Principais

Os autores estabelecem garantias de cobertura para o método proposto:

• Limite Inferior de Cobertura em Amostra Finita (Teorema 1):
  A cobertura real é limitada inferiormente por $1 - \alpha - \text{Erro}$. O erro de subcobertura é controlado por duas propriedades do algoritmo de agrupamento:

  1. Consistência: O erro de estimação das probabilidades de rótulo suaves deve convergir para zero.
  2. Estabilidade "Replace-One": A mudança na distribuição conjunta dos rótulos quando um único ponto de dados é substituído deve ser pequena (invariância assintótica).
  • Insight: O uso de rótulos estocásticos é crucial para garantir que essas propriedades sejam satisfeitas, ao contrário de rótulos duros que são instáveis.

• Cobertura Assintótica (Teoremas 2 e 3):
  Sob condições de regularidade (como em modelos de mistura paramétricos bem especificados onde os parâmetros são estimados consistentemente), o termo de erro tende a zero quando $n \to \infty$, garantindo que a cobertura atinja o nível nominal $1-\alpha$.

4. Resultados Empíricos

Os autores validaram o método através de simulações e dados reais:

• Simulações (Modelos de Mistura):

  • Testados em Modelos de Mistura Gaussiana (GMM) e Gamma (GaMM) em dimensões baixas e altas.
  • Comparação: O método proposto ("Split CC Stochastic") atingiu consistentemente a cobertura alvo (ex: 90%) com tamanhos de conjunto de confiança informativos (pequenos para regiões claras, maiores para fronteiras).
  • Falha dos Baselines: O método "Split CC Naive" (rótulos duros) apresentou subcobertura severa (ex: 60-70% em vez de 90%). O método "Cutoff" produziu conjuntos excessivamente grandes e não informativos.
  • Visualização: Mapas de calor mostram claramente regiões de alta certeza (rótulo único) e regiões de incerteza (fronteiras entre clusters com múltiplos rótulos no conjunto).

• Aplicação em Dados Reais (Genômica de Célula Única):

  • Aplicado ao dataset PBMC-3K (RNA-seq) para identificar tipos celulares.
  • Resultados: O método quantificou a incerteza biologicamente plausível. Células B e NK (bem definidas) tiveram conjuntos de confiança unitários (alta certeza). Células T, monócitos e dendríticos (com estados sobrepostos) apresentaram conjuntos de confiança maiores, refletindo a ambiguidade biológica real.
  • Demonstrou utilidade prática para identificar onde as atribuições de cluster são confiáveis e onde são ambíguas.

5. Significado e Impacto

• Pioneirismo: Este é um dos primeiros trabalhos a aplicar rigorosamente a inferência conformal a um problema puramente não supervisionado, superando o desafio da ausência de rótulos verdadeiros.
• Mudança de Paradigma: Transita a visão de incerteza em clustering de uma propriedade de uma partição fixa para uma propriedade de uma regra de rotulagem definida sobre o espaço de características.
• Utilidade Prática: Fornece aos pesquisadores uma ferramenta para tomar decisões mais robustas, identificando pontos de dados onde a atribuição de cluster é ambígua, o que é crítico em áreas como biomedicina e descoberta de fármacos.
• Direções Futuras: O trabalho abre caminho para inferência pós-seleção (escolha do número de clusters $K$), agregação de múltiplos preditores e extensão para métodos de agrupamento não paramétricos.

Em resumo, o artigo oferece uma solução teórica e prática para o problema de "como saber quão confiante devemos estar em um rótulo de cluster?", transformando o clustering de uma ferramenta puramente exploratória para uma ferramenta com garantias estatísticas de incerteza.