Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/331498
Type: TESE DIGITAL
Degree Level: Doutorado
Title: Método de pontos interiores para estimar os parâmetros de uma gramática probabilística livre de contexto
Title Alternative: Interior point method for estimating of parameters for stochastic context-free grammar
Author: Mamián López, Esther Sofía, 1985-
Advisor: Oliveira, Aurelio Ribeiro Leite de, 1962-
Abstract: Resumo: No marco do Processamento da Linguagem Natural (PLN), nosso objetivo é modelar uma linguagem natural, por exemplo: Inglês, Português, etc. O modelo probabilístico mais simples para modelar linguagens naturais, são as chamadas Gramáticas Probabilísticas Livres de Contexto (GPLC), isto é, uma gramática livre de contexto na qual cada regra tem associado um valor de probabilidade. Para o processo de treino de uma GPLC (determinar as probabilidades associadas às regras), supomos que a parte estrutural da GPLC é dada, quer dizer, os símbolos não terminais, símbolos terminais, regras da gramática e símbolo inicial são conhecidos. Treinar a gramática pode ser entendido como o processo de encontrar os valores de probabilidade ótimos para cada una das regras da GPLC. A estratégia está baseada em um treino a partir de um corpus, onde este além de conter a parte estrutural da GPLC, contém exemplos de sentenças da linguagem. Assim determinamos uma função critério da amostra e um método para otimizá-la. O método clássico para estimar os parâmetros de um GPLC é o método Inside-Outside, este demanda uma grande quantidade de tempo tornando-o inviável para aplicações complexas, pois é de ordem de Opm3n3 q onde m é o comprimento da sentença, e n é o número de símbolos não terminais da gramática. Nesse contexto, nossa proposta é estudar a aplicação de métodos de pontos interiores primal-dual para o processo de treinamento de uma gramática probabilística livre de contexto. A escolha de este método é em razão que eles são bem-sucedidos para problemas de programação não linear de grande porte

Abstract: In many Natural Language Processing tasks, one aim is modeling Natural Language (NL), ie, English, Portuguese, etc. The simplest probabilistic model for NL is a Probabilistic Context Free Grammar (PCFG), which is a context free grammar with probabilities added to the rules. For training a PCFG (to calculate probabilities), we assume that the structure of the grammar in terms of the number of terminals and nonterminals symbols, the rules, and the start symbol are given in advance. Training the grammar comprises simply a process that tries to find the optimal probabilities to assign for different grammar rules within this grammar structure. The approach, for this purpose, is corpus-based work, meaning we have a corpus (sample of sentences) of a natural language and we will training the grammar with it. From corpus we recover structural part of grammar and a sample of sentences, so we need defined a criterion function and optimization method for probabilities assign to grammar rules. The Inside-Outside algorithm allows us to train the parameters of a PCFG on sentences of a natural language. However, for each sentence, each iteration of training is O(m^3n^3), where m is the length of sentence, and n is the number of nonterminal symbols in the grammar. For this, our aim is studying primal-dual Interior Point Methods for training probabilistic context free grammar, because computational experiments and the theoretical development, have show that primal-dual algorithms perform well for large-scale nonlinear programming problems
Subject: Métodos de pontos interiores
Processamento de linguagem natural (Computação)
Gramáticas probabilísticas livres de contexto
Language: Português
Editor: [s.n.]
Citation: MAMIÁN LÓPEZ, Esther Sofía. Método de pontos interiores para estimar os parâmetros de uma gramática probabilística livre de contexto. 2018. 1 recurso online (82 p.). Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação Científica, Campinas, SP. Disponível em: <http://www.repositorio.unicamp.br/handle/REPOSIP/331498>. Acesso em: 3 set. 2018.
Date Issue: 2018
Appears in Collections:IMECC - Tese e Dissertação

Files in This Item:
File SizeFormat 
Lopez_EstherSofiaMamian_D.pdf812.39 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.