Contrastive Identification and Generation in the Limit

Resumo Técnico: Identificação e Geração Contrastivas no Limite

Definição do Problema
Este artigo inicia o estudo teórico-aprendizagem da identificação e geração contrastivas no limite. Os autores abordam uma lacuna nos modelos clássicos de aprendizagem no limite (Gold, 1967; Angluin, 1980) e nos modelos de geração recentes (Kleinberg e Mullainathan, 2024), que dependem de fluxos de exemplos positivos (texto) ou dados totalmente rotulados (informante). Em muitos cenários naturais — como testes A/B, experimentos comparativos e anotações de similaridade-dissimilaridade — os dados chegam como pares não ordenados $\{x, y\}$ onde o aprendiz sabe que os exemplos discordam sob a hipótese alvo $h$ (ou seja, $h(x) \neq h(y)$), mas não sabe qual elemento é positivo ($h(x)=1$) e qual é negativo ($h(x)=0$).

O aprendiz observa um fluxo de tais pares contrastivos que eventualmente cobre todo exemplo positivo (cobertura do lado positivo), mas nunca rotula explicitamente um único ponto. O objetivo é determinar as condições sob as quais um aprendiz pode:

1. Identificar a hipótese alvo $h$ de uma classe conhecida $\mathcal{H}$ (estabilizando na hipótese correta).
2. Gerar novos exemplos positivos de $h$ (saindo elementos em $\text{supp}(h)$ ainda não vistos no fluxo).

Metodologia e Estrutura Técnica
A contribuição técnica central é a introdução do grafo de cruzamento comum, denotado $\Gamma(h, g) = \Delta(h) \cap \Delta(g)$, onde $\Delta(h)$ é o conjunto de todos os pares que cruzam o corte definido por $h$. Este grafo codifica a ambiguidade par-a-par entre hipóteses: uma aresta existe em $\Gamma(h, g)$ se o par for uma observação válida tanto para $h$ quanto para $g$.

Os autores aplicam este objeto geométrico em três escalas:

• Pares: Para analisar a eliminabilidade entre duas hipóteses.
• Famílias Finitas: Para analisar obstruções à geração via apresentações compartilhadas.
• Conjuntos de Defeito Infinitos: Para analisar robustez contra corrupção adversária.

O artigo utiliza uma tradução teórica de grafos onde a ambiguidade contrastiva par-a-par se reduz a uma questão de cobertura: uma hipótese $g$ não é eliminável de $h$ se e somente se o suporte de $h$ for coberto pelos vértices incidentes às arestas em $\Gamma(h, g)$.

Principais Contribuições e Resultados

1. Caracterização Exata da Identificação Contrastiva (CtrId)
O artigo fornece uma condição necessária e suficiente para que uma classe $\mathcal{H}$ seja identificável a partir de dados contrastivos. Uma classe está em CtrId se e somente se:

• For identificável por texto (satisfaz a condição de "dica reveladora" de Angluin).
• Condição de Cobertura Sobreposta: Todo par de hipóteses incomparáveis em $\mathcal{H}$ deve formar uma "cobertura sobreposta". Isso significa que seus suportes devem se intersectar ($\text{supp}(h) \cap \text{supp}(g) \neq \emptyset$) e sua união deve cobrir todo o espaço de exemplos ($\text{supp}(h) \cup \text{supp}(g) = X$).
• Implicação: Dados contrastivos introduzem uma nova obstrução: se duas hipóteses são incomparáveis, disjuntas ou se intersectam, mas não cobrem o espaço, elas não podem ser distinguidas.

2. Geração Contrastiva e a Dimensão de Fechamento
Os autores introduzem a dimensão de fechamento contrastivo ($C^\Delta$), uma dimensão combinatória análoga à dimensão de fechamento para dados positivos (Raman et al., 2025).

• Definição: $C^\Delta(\mathcal{H})$ é o supremo do tamanho de conjuntos de arestas "oco" finitos (conjuntos de pares que forçam nenhum novo elemento positivo fora dos vértices observados).
• Resultado: Uma classe admite um gerador contrastivo uniforme se e somente se $C^\Delta(\mathcal{H}) < \infty$. A complexidade de amostra apertada é $C^\Delta(\mathcal{H}) + 1$.
• Geração Não Uniforme: Uma classe é gerável não uniformemente se puder ser decomposta em uma cadeia de subclasses com dimensões de fechamento contrastivo finitas.
• Obstruções: O artigo identifica "obstruções de família finita" onde um conjunto de hipóteses admite uma apresentação contrastiva compartilhada com uma interseção finita de suportes, impedindo a geração de novos elementos.

3. A Hierarquia Diamante
Em classes contáveis com suporte uniformemente ilimitado (UUS), as quatro famílias de aprendizagem formam uma hierarquia diamante estrita, em vez de uma cadeia linear:

• Contenções Estritas: $\text{CtrId} \subsetneq \text{CtrGen}$ e $\text{CtrId} \subsetneq \text{TxtId}$. Tanto $\text{CtrGen}$ quanto $\text{TxtId}$ estão estritamente contidos em $\text{TxtGen}$.
• Incomparabilidade: $\text{CtrGen}$ e $\text{TxtId}$ são mutuamente incomparáveis.
  • TxtId $\not\subseteq$ CtrGen: Classes com suportes disjuntos são identificáveis por texto, mas bloqueadas da geração contrastiva por obstruções de interseção finita.
  • CtrGen $\not\subseteq$ TxtId: Classes com "suportes perfurados" (removendo um elemento de um conjunto infinito) são geráveis contrastivamente via núcleos eventuais, mas carecem de conjuntos de dica reveladora finitos para identificação por texto.

4. Reversão de Robustez sob Corrupção Adversária
O artigo prova uma reversão aguda na relação entre modos de identificação sob corrupção adversária finita:

• Fragilidade do Texto: Um único exemplo positivo corrompido pode tornar uma classe não identificável no cenário de texto.
• Robustez Contrastiva: Os autores definem um número de defeito $\kappa(h \to g)$, contando as violações mínimas forçadas de uma hipótese $g$ em qualquer apresentação válida de $h$. Se $\kappa(h \to g) = \infty$, nenhuma corrupção finita pode mascarar as violações.
• Classe Co-unitária: A classe onde cada hipótese rotula todos os exemplos como positivos, exceto um "buraco", é identificável sob qualquer orçamento finito de corrupção no cenário contrastivo (usando um algoritmo de "contagem de ausência"), mas é não identificável sob até mesmo uma corrupção no cenário de texto.
• Resultado: Para cada $k \ge 1$, a identificação contrastiva com $k$ corrupções e a identificação de texto com $k$ corrupções são mutuamente incomparáveis.

Significado e Alegações
O artigo alega que o grafo de cruzamento comum serve como um objeto técnico unificador que codifica ambiguidade par-a-par, obstruções de geração ao nível da família e defeitos de corrupção em uma única linguagem. Os autores argumentam que, embora a falta de direção nos dados contrastivos seja uma fraqueza em cenários limpos (introduzindo novas obstruções em comparação com o texto), ela se torna uma força sob corrupção adversária, pois pares corrompidos criam "não-arestas" estruturalmente detectáveis que violam a restrição XOR.

O trabalho sugere que os paradigmas clássicos de aprendizagem no limite admitem refinamentos frutíferos quando as observações não são unitárias, revelando uma estrutura teórica de grafos de dois lados: custosa em relação a dados rotulados quando limpa, mas protetora quando perturbada adversariamente. O artigo nota explicitamente que suas construções para identificação e geração não uniforme são teóricas da informação (baseadas na existência de famílias de dica reveladora ou cadeias de dimensão) e deixa a questão de procedimentos efetivos e construtivos para classes mais amplas como um problema aberto.