Indução gramatical - Grammar induction

Parte de uma série sobre
Aprendizado de máquina
e mineração de dados
Multi-Layer Neural Network-Vector-Blank.svg
Problemas
Aprendizagem supervisionada
( classificação  • regressão )
Clustering
Redução de dimensionalidade
Previsão estruturada
Detecção de anomalia
Rede neural artificial
Aprendizagem por reforço
Teoria
Locais de aprendizado de máquina
Artigos relacionados

A indução gramatical (ou inferência gramatical ) é o processo de aprendizado de máquina de aprendizagem de uma gramática formal (geralmente como uma coleção de regras ou produções reescritas ou, alternativamente, como uma máquina de estado finito ou autômato de algum tipo) a partir de um conjunto de observações, portanto construir um modelo que leva em conta as características dos objetos observados. De maneira mais geral, a inferência gramatical é aquele ramo do aprendizado de máquina em que o espaço de instância consiste em objetos combinatórios discretos, como strings, árvores e gráficos.

Aulas de gramática

A inferência gramatical tem sido freqüentemente muito focada no problema de aprendizado de máquinas de estados finitos de vários tipos (veja o artigo Indução de linguagens regulares para detalhes sobre essas abordagens), uma vez que existem algoritmos eficientes para este problema desde os anos 1980.

Desde o início do século, essas abordagens foram estendidas ao problema de inferência de gramáticas livres de contexto e formalismos mais ricos, como gramáticas livres de contexto múltiplas e gramáticas livres de contexto múltiplas paralelas. Outras classes de gramáticas para as quais a inferência gramatical foi estudada são gramáticas categóricas combinatórias , gramáticas estocásticas livres de contexto , gramáticas contextuais e linguagens de padrões.

Modelos de aprendizagem

A forma mais simples de aprendizagem é quando o algoritmo de aprendizagem apenas recebe um conjunto de exemplos retirados da linguagem em questão: o objetivo é aprender a linguagem a partir de exemplos dela (e, raramente, de contra-exemplos, isto é, exemplos que fazem não pertencem ao idioma). No entanto, outros modelos de aprendizagem foram estudados. Uma alternativa freqüentemente estudada é o caso em que o aluno pode fazer perguntas sobre os membros, como no modelo de aprendizagem por consulta exata ou no modelo de professor minimamente adequado introduzido por Angluin.

Metodologias

Existe uma grande variedade de métodos para inferência gramatical. Duas das fontes clássicas são Fu (1977) e Fu (1982) . Duda, Hart & Stork (2001) também dedicam uma breve seção ao problema e citam uma série de referências. O método básico de tentativa e erro que eles apresentam é discutido abaixo. Para abordagens para inferir subclasses de linguagens regulares em particular, consulte Indução de linguagens regulares . Um livro mais recente é de la Higuera (2010), que cobre a teoria da inferência gramatical de linguagens regulares e autômatos de estado finito. D'Ulizia, Ferri e Grifoni fornecem uma pesquisa que explora métodos de inferência gramatical para línguas naturais.

Inferência gramatical por tentativa e erro

O método proposto na seção 8.7 de Duda, Hart & Stork (2001) sugere adivinhar regras gramaticais (produções) sucessivamente e testá-las contra observações positivas e negativas. O conjunto de regras é expandido para poder gerar cada exemplo positivo, mas se um determinado conjunto de regras também gerar um exemplo negativo, ele deve ser descartado. Esta abordagem particular pode ser caracterizada como "teste de hipótese" e tem alguma semelhança com o algoritmo de espaço de versão de Mitchel . O texto de Duda, Hart & Stork (2001) fornece um exemplo simples que ilustra bem o processo, mas a viabilidade de tal abordagem de tentativa e erro não guiada para problemas mais substanciais é duvidosa.

Inferência gramatical por algoritmos genéticos

A indução gramatical usando algoritmos evolutivos é o processo de evolução de uma representação da gramática de uma língua-alvo por meio de algum processo evolutivo. As gramáticas formais podem ser facilmente representadas como estruturas de árvore de regras de produção que podem ser submetidas a operadores evolucionários. Algoritmos desse tipo derivam do paradigma de programação genética criado por John Koza . Outros trabalhos iniciais em linguagens formais simples usaram a representação de string binária de algoritmos genéticos, mas a estrutura inerentemente hierárquica de gramáticas expressas na linguagem EBNF tornou as árvores uma abordagem mais flexível.

Koza representou programas Lisp como árvores. Ele foi capaz de encontrar análogos para os operadores genéticos dentro do conjunto padrão de operadores de árvore. Por exemplo, trocar subárvores é equivalente ao processo correspondente de cruzamento genético, em que subcadeias de um código genético são transplantadas para um indivíduo da próxima geração. A aptidão é medida pontuando a saída das funções do código Lisp. Análogos semelhantes entre a representação lisp estruturada em árvore e a representação de gramáticas como árvores, tornaram possível a aplicação de técnicas de programação genética para a indução gramatical.

No caso da indução gramatical, o transplante de subárvores corresponde à troca de regras de produção que possibilitam a análise sintática de frases de alguma língua. O operador de aptidão para a gramática é baseado em alguma medida de quão bem ela se saiu na análise de algum grupo de sentenças do idioma de destino. Em uma representação em árvore de uma gramática, um símbolo terminal de uma regra de produção corresponde a um nó folha da árvore. Seus nós pais correspondem a um símbolo não terminal (por exemplo, um sintagma nominal ou um sintagma verbal ) no conjunto de regras. Em última análise, o nó raiz pode corresponder a uma frase não terminal.

Inferência gramatical por algoritmos gananciosos

Como todos os algoritmos gulosos , os algoritmos de inferência gramatical gulosos tomam, de maneira iterativa, decisões que parecem ser as melhores nesse estágio. As decisões tomadas geralmente lidam com coisas como a criação de novas regras, a remoção de regras existentes, a escolha de uma regra a ser aplicada ou a fusão de algumas regras existentes. Como existem várias maneiras de definir 'o estágio' e 'o melhor', também existem vários algoritmos de inferência gramaticais gananciosos.

Esses algoritmos de geração de gramática livre de contexto tomam a decisão após cada símbolo lido:

  • O algoritmo Lempel-Ziv-Welch cria uma gramática livre de contexto de forma determinística, de forma que é necessário armazenar apenas a regra inicial da gramática gerada.
  • Sequitur e suas modificações.

Esses algoritmos de geração de gramática livre de contexto primeiro leem toda a sequência de símbolos fornecida e, em seguida, começam a tomar decisões:

Aprendizagem distributiva

Uma abordagem mais recente é baseada na aprendizagem distributiva. Algoritmos que usam essas abordagens têm sido aplicados para aprender gramáticas livres de contexto e linguagens moderadamente sensíveis ao contexto e têm se mostrado corretos e eficientes para grandes subclasses dessas gramáticas.

Aprendizagem de linguagens de padrões

Angluin define um padrão como "uma cadeia de símbolos constantes de Σ e símbolos variáveis de um conjunto disjunto". A linguagem de tal padrão é o conjunto de todas as suas instâncias não vazias, isto é, todas as cadeias resultantes da substituição consistente de seus símbolos variáveis ​​por cadeias não vazias de símbolos constantes. Um padrão é chamado de descritivo para um conjunto finito de strings de entrada se sua linguagem for mínima (com relação à inclusão do conjunto) entre todas as linguagens de padrão que subsumem o conjunto de entrada.

Angluin fornece um algoritmo polinomial para calcular, para um determinado conjunto de strings de entrada, todos os padrões descritivos em uma variável x . Para este fim, ela constrói um autômato que representa todos os padrões possivelmente relevantes; usando argumentos sofisticados sobre comprimentos de palavras, que contam com x sendo a única variável, a contagem de estados pode ser drasticamente reduzida.

Erlebach et al. fornecer uma versão mais eficiente do algoritmo de aprendizado de padrões do Angluin, bem como uma versão paralelizada.

Arimura et al. mostram que uma classe de linguagem obtida de uniões limitadas de padrões pode ser aprendida em tempo polinomial.

Teoria de padrões

A teoria dos padrões , formulada por Ulf Grenander , é um formalismo matemático para descrever o conhecimento do mundo como padrões. Ela difere de outras abordagens da inteligência artificial porque não começa prescrevendo algoritmos e mecanismos para reconhecer e classificar padrões; em vez disso, prescreve um vocabulário para articular e reformular os conceitos de padrão em linguagem precisa.

Além do novo vocabulário algébrico, sua abordagem estatística era nova em seu objetivo de:

  • Identifique as variáveis ​​ocultas de um conjunto de dados usando dados do mundo real em vez de estímulos artificiais, o que era comum na época.
  • Formule distribuições anteriores para variáveis ​​ocultas e modelos para as variáveis ​​observadas que formam os vértices de um gráfico do tipo Gibbs.
  • Estude a aleatoriedade e a variabilidade desses gráficos.
  • Crie as classes básicas de modelos estocásticos aplicados listando as deformações dos padrões.
  • Sintetize (amostra) a partir dos modelos, não apenas analise os sinais com eles.

Ampla em sua cobertura matemática, a teoria de padrões abrange álgebra e estatística, bem como propriedades topológicas locais e entrópicas globais.

Formulários

O princípio da indução gramatical foi aplicado a outros aspectos do processamento da linguagem natural e foi aplicado (entre muitos outros problemas) à análise semântica , compreensão da linguagem natural , tradução baseada em exemplos , análise de morfemas e derivações de nomes de lugares. A indução gramatical também foi usada para compressão baseada em gramática e inferência estatística por meio dos princípios de comprimento mínimo de mensagem (MML) e comprimento mínimo de descrição (MDL). A indução gramatical também tem sido usada em alguns modelos probabilísticos de aquisição da linguagem .

Veja também

Notas

Referências

Fontes