Resumo Técnico: Indução de Gramática Gulosa com Evidência Negativa Indireta

Declaração do Problema

O artigo aborda o desafio de induzir Gramáticas Livres de Contexto (CFGs) a partir apenas de dados positivos. Resultados clássicos (Gold, 1967; Angluin, 1980) estabelecem que classes de linguagens ricas não podem ser identificadas a partir de textos positivos arbitrários sem restrições adicionais. As abordagens existentes tipicamente restringem a classe alvo, exigem amostras características ou dependem de otimização probabilística (por exemplo, PCFGs treinados por EM), que frequentemente carecem de garantias de equivalência fraca com um alvo desconhecido e sofrem de espaços de busca não convexos.

Este trabalho propõe um procedimento de indução simbólica não lexicalizada que separa o problema de indução de gramática em dois testes distintos:

1. Reconhecimento: A gramática deve reconhecer a apresentação finita observada.
2. Rejeição: A gramática não deve gerar strings pré-terminais curtas que não sejam suportadas pela evidência.

O aprendiz opera sobre strings pré-terminais, assumindo um léxico externo de palavra-para-pré-terminal, focando assim na indução estrutural da gramática.

Metodologia

O Limite de Cobertura de Regra ($\ell^*(G)$)

O mecanismo central é o limite de cobertura de regra, denotado por $\ell^*(G)$. Para uma gramática $G$, este é definido como o máximo, sobre todas as regras $r \in G$, do comprimento da mais curta string pré-terminal cuja derivação utiliza essa regra.

• Este limite induz um universo de comparação finito $\Sigma^{\le \ell^*(G)}_{pre}$.
• Dentro deste universo, qualquer string gerada por uma gramática candidata, mas ausente na apresentação observada, serve como evidência negativa indireta contra a sobregeração.

A Função de Aptidão e o Cenário Guloso

O aprendiz emprega uma função de aptidão (fitness) $f(D|G)$ definida sobre o horizonte finito $\ell^*(G)$. A pontuação é a razão entre as strings de evidência geradas por $G$ e o total de strings geradas por $G$ dentro desse horizonte.

• Aptidão = 1: Todas as strings geradas dentro do horizonte são suportadas pelos dados.
• Aptidão < 1: A gramática sobregera strings não suportadas dentro do horizonte.

O artigo prova que, sob uma apresentação saturada (onde todas as strings até um certo comprimento geradas pelo alvo estão presentes nos dados), o espaço de busca forma um "cenário guloso" (greedy landscape):

• Monotonicidade: Adicionar regras não pode remover strings não suportadas previamente geradas. Uma vez que um candidato gera uma string curta não suportada, ele falha permanentemente no teste de aptidão.
• Persistência: Subgramáticas do alvo que geram pelo menos uma string dentro do horizonte permanecem no "platô de aptidão" (aptidão = 1).
• Comutatividade: A ordem em que as strings de evidência não analisadas mais curtas são descobertas não destrói a possibilidade de encontrar outros caminhos que preservem o alvo.

O Algoritmo de Aprendizado

O algoritmo realiza uma busca gulosa sobre conjuntos de regras usando os seguintes componentes:

1. Adjacência Canônica: Enumera conjuntos de regras principais em uma ordem específica para evitar redundância de permutação.
2. Geração Guiada por Wildcard: Filtra adições de regras candidatas verificando se elas podem participar de uma derivação da próxima string de evidência não analisada (usando uma relaxação de wildcard para não-terminais improdutivos).
3. Abdução CKY de Pré-terminais: Infere as extensões de mapeamento funcional necessárias (não-terminais estruturais para pré-terminais) apenas para a string específica não analisada, evitando uma busca de produto cartesiano completa.
4. Filtragem de Fita de Pareto (Pareto-Ribbon): Mantém um conjunto de hipóteses de aptidão completas baseadas em um compromisso entre o tamanho do conjunto de regras (parcimônia) e a taxa de crescimento da gramática (estreiteza), controlado por um parâ de largura de fita $\eta$.
5. Folga Pós-Solução (Post-Solution Slack): Limita a profundidade da busca após encontrar a primeira solução completa para evitar expansão desnecessária.

Principais Contribuições

1. Aptidão de Cobertura de Regra: A definição do limite de cobertura de regra $\ell^*(G)$ e o teste de aptidão induzido, que transforma strings geradas curtas não suportadas em evidência formal contra a sobregeração.
2. Cenário Guloso Induzido por Aptidão: Provas teóricas de monotonicidade, persistência e comutatividade de strings mais curtas, justificando o uso de busca gulosa sobre subgramáticas aptas sob apresentações saturadas.
3. Recuperação Fraca Condicional: Um teorema estabelecendo que, se uma gramática alvo é $(L, k)$-alcançável (ou seja, alcançável via uma cadeia de incrementos limitados testemunhados pelos dados) e a apresentação é $L$-saturada, o aprendiz exato tem a garantia de alcançar uma gramática fracamente equivalente ao alvo.
4. Implementação e Avaliação: Uma implementação concreta utilizando abdução CKY, guia de wildcard e filtragem de Pareto. A análise de complexidade é feita por fatias: para um raio de incrementalidade $k$ fixo, a busca explora muitos conjuntos de regras de forma polinomial.

Resultados

O aprendiz foi avaliado através de 31 execuções de benchmark cobrindo:

• Linguagens Dyck-$k$ ($1 \le k \le 4$).
• Linguagens Palíndromo.
• A linguagem não substituível $\{a^n b^n\}$.
• Fragmentos recursivos semelhantes ao Inglês (incluindo estruturas sujeito-objeto-verbo e adjunção ambígua de PP).
• Uma linguagem de união inerentemente ambígua.

Descobertas:

• A análise ao nível da gramática estabeleceu equivalência fraca entre cada gramática retornada e seu alvo em todas as 31 execuções.
• Os limites de cobertura de regra ($\ell^*$) para as gramáticas equivalentes ao alvo variaram de 3 a 5.
• Os tempos de execução (wall-clock) foram geralmente baixos (segundos a minutos), sendo que o caso mais complexo de união inerentemente ambígua levou aproximadamente 2 horas e 28 minutos.
• O sistema lidou com sucesso com casos onde a estrutura de argumento não era representada explicitamente por pré-terminais separados (codificação de categoria única).

Significância e Alegações

O artigo afirma fornecer um teorema de recuperação de busca finita em vez de um teorema de identificação no limite. A significância reside em:

• Rota Simbólica: Oferecer uma alternativa não probabilística aos PCFGs neurais e métodos baseados em EM, com garantias explícitas de equivalência fraca sob condições específicas.
• Evidência Negativa Indireta: Formalizar como dados positivos podem servir como evidência negativa contra a sobregeração dentro de um universo limitado definido pela própria estrutura da gramática.
• Garantias Condicionais: A garantia de recuperação é explícita: ela ocorre se o alvo for alcançável via incrementos limitados e os dados forem suficientemente saturados para testemunhar esses incrementos. Fora dessas condições, o aprendiz garante apenas o parsing dos dados observados e a prevenção de strings não suportadas até o seu próprio limite de cobertura de regra, consistente com os limites clássicos sobre aprendizado apenas de dados positivos.

Os autores enfatizam que o requisito de saturação é uma condição de cobertura finita, não uma consequência livre de distribuição, e que o fornecimento de tal cobertura por entradas naturalísticas é uma questão empírica. O trabalho demonstra que, com saturação e alcançabilidade limitadas suficientes, a recuperação exata de gramáticas fracamente equivalentes é alcançável via busca gulosa.