Inferencia gramatical : aplicações em composição algorítmica para modelagem de sequencia de acordes.

Abstract

Inferência Gramatical é uma área amplamente estudada que utiliza algoritmos para inferir uma gramatica formal. As gramáticas inferidas podem ser aplicadas em uma grande vari- edade de áreas, como Linguística Computacional e Composição algorítmica. A literatura carece de algoritmos que tentam inferir Gramaticas Livres de Contexto Probabilísticas, ou mais expressivas. Para as primeiras, a literatura pode se beneficiar de algoritmos que tentam identificar as estruturas internas de uma gramatica. Na Composição Algorítmica, estudos re- centes mostraram que Modelos Ocultos de Markov podem superar Cadeias de Markov em termos de acurácia, porém não há diferenças significativas entre Modelos Ocultos de Markov e Gramaticas Livres de Contexto Probabilísticas (GLCPs). Nao há resultados na literatura que comprovam se inferir probabilidades sensíveis ao contexto podem superar ambas gramaticas. Este trabalho possui duas principais frentes, elaborar algoritmos de Inferência Gramatical e aplicar as gramaticas inferidas na área de Composição Algorítmica. Neste trabalho, desenvol- vemos um novo algoritmo para inferência de Gramáticas Livres de Contexto Probabilísticas chamado Pumping Inference. Ele foi capaz de inferir as linguagens Dyck-n e um subcon- junto da base de dados CoNLL-2003 com acurácia de predição melhor que a Amostragem de Gibbs. Na Composição Algorítmica, aplicamos um algoritmo de Amostragem de Gibbs para inferir Gramaticas (k, l)-Sensíveis ao Contexto Probabilísticas (G(k, l)CSPs) para mode- lar sequencia de acordes musicais. Nossos resultados mostram que a Amostragem de Gibbs e G(k, l)CSPs podem superar GLCPs e o algoritmo de busca de distribuição de probabilidades Metropolis-Hastings com perplexidades até 48% menores em media (valor-p 0,0026).