• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Tesis Doctoral
DOI
10.11606/T.43.2005.tde-14112013-135303
Documento
Autor
Nombre completo
Roberto Castro Alamino
Instituto/Escuela/Facultad
Área de Conocimiento
Fecha de Defensa
Publicación
São Paulo, 2005
Director
Tribunal
Alfonso, Nestor Felipe Caticha (Presidente)
Idiart, Marco Aurelio Pires
Prado, Carmen Pimentel Cintra do
Rosenfeld, Rogério
Vicente, Renato
Título en portugués
Aprendizado em modelos de Markov com variáveis de estado escondidas
Palabras clave en portugués
Mecânica estatística
Mecânica estatística clássica
Resumen en portugués
Neste trabalho estudamos o aprendizado em uma classe específica de modelos probabilísticos conhecidos como modelos de Markov com variáveis de estado escondidas (em inglês, Hidden Markov Models ou HMMs). Primeiramente discutimos sua teoria básica e em seguida fazemos um estudo detalhado do comportamento de cinco diferentes algoritmos de aprendizado, dois deles já conhecidos na literatura e os outros três propostos por nós neste trabalho. Os cinco algoritmos estão descritos abaixo e são estudados na seqüência apresentada: Algoritmo de Baum-Welch (BW): consiste em um célebre algoritmo off-line obtido através da aplicação do algoritmo EM ao caso particular dos HMMs. Na literatura, é comum referir-se a ele pelo nome de Fórmulas de Reestimação de BaumWelch. Algoritmo de Baum-Welch On-line (BWO): versão on-line de BW proposta por nós. Algoritmo de Baldi-Chauvin (BC): algoritmo on-line proposto por Baldi e Chauvin em [5] onde uma representação do tipo softma:x é utilizada para as probabilidades dos HMMs e cujo objetivo é, a cada passo de iteração, maximizar a verossimilhança do modelo. Algoritmo Bayesiano On-line (BKL): algoritmo desenvolvido por nós baseado numa proposta de Opper [74], onde, após a atualização da distribuição de probabilidades do modelo a cada novo dado, projeta-se a densidade obtida em uma família paramétrica de distribuições tratáveis minimizando-se a distância de KullbackLeibler entre as duas. Algoritmo Posterior Média (PM): uma simplificação de BKL onde a projeção após a atualização é feita na distribuição posterior média. Para cada um dos algoritmos acima, obtemos curvas de aprendizado através de simulações onde utilizamos duas medidas distintas de erro de generalização: a distância de Kullback-Leibler (dKL) e a distância euclideana (d IND. E). Com exceção do algoritmo BW, que só pode ser utilizado em situações de aprendizado off-line, estudamos para todos os outros algoritmos as curvas de aprendizado tanto para a situação on-line quanto para a off-line. Comparamos as performances dos algoritmos entre si e discutimos os resultados obtidos mostrando que, apesar de um tempo de computação maior, o algoritmo bayesiano PM, proposto por nós, é superior aos outros algoritmos não-bayesianos quanto à generalização em situações de aprendizado estáticas e possui uma performance muito próxima do algoritmo bayesiano BKL. Fazemos, também, uma comparação entre os algoritmos PM e BC em situações de aprendizado variáveis com o tempo, com dados gerados artificialmente e em uma situação com dados reais, porém com um cenário simplificado, onde os utilizamos para prever o comportamento do índice da bolsa de valores de São Paulo (IBOVESPA), mostrando que, embora necessitem de um período longo de aprendizado, após essa fase inicial as previsões obtidas por esses algoritmos são surpreendentemente boas. Por fim, apresentamos uma discussão sobre aprendizado e quebra de simetria baseada nos estudos feitos.
Título en inglés
Learning in Hidden Markov Models
Palabras clave en inglés
Classical statistical mechanics
statistical mechanics
Resumen en inglés
In this work we study learning in a specific class of probabilistic models known as Hidden Markov Models (HMMs). First we discuss its basic theory and after we make a detailed study of the behavior of five different learning algorithms, two of them already known in the literature and the other three proposed by us in this work. The five algorithms are described below in the sequence they are presented in the thesis: Baum-Welch Algorithm(BW): consists of a renowed offline algorithm obtained by applying the EM-algorithm to the particular case of HMMs. Through the literature it is common to refer to it by the name Baum-Welch Reestimation Formulas. Baum-Welch Online Algorithm (BWO): online version of BW proposed by us. Baldi-Chauvin Algorithm (BC): online algorithm proposed by Baldi and Chauvin in [5] where a softmax representation for the probabilities of the HMMs is used and where the aim is to maximize the model likelihood at each iteration step. Online Bayesian Algorithm (BKL): an algorithm developed by us based on the work of Opper [74] where, after updating the probability distribution of the model with each new data, the obtained density is projected into a parametric family of tractable distributions minimizing the Kullback-Leibler distance between both. Mean Posterior Algorithm (PM): a simplification of BKL where the projection after the update is made on the mean posterior distribution. For each one of the above algorithms, we obtain learning curves by means of simulations where we use two distinct measures of generalization error: the Kullback-Leibler distance (dKL) and the Euclidian distance (dE). With exception of the BW algorithm, which can be used only in offline learning situations, we study for all the other algorithms the learning curves for both learning situations: online and offiine. We compare the performance of the algorithms with one another and discuss the results showing that, besides its larger computation time, the bayesian algorithm PM, proposed by us, is superior to the other non-bayesian algorithms with respect to the generalization in static learning situations and that it has a performance that is very close to the bayesian algorithm BKL. We also make a comparison between algorithms PM and BC in learning situations that change with time using artificially generated data and in one situation with real data, with a simplified scenario, where we use them to predict the behavior of the São Paulo Stock Market Index (BOVESPA) showing that, although they need a large learning period, after that initial phase the predictions obtained by both algorithms are surprisingly good. Finally, we present a discussion about learning and symmetry breaking based on the presented studies.
 
ADVERTENCIA - La consulta de este documento queda condicionada a la aceptación de las siguientes condiciones de uso:
Este documento es únicamente para usos privados enmarcados en actividades de investigación y docencia. No se autoriza su reproducción con finalidades de lucro. Esta reserva de derechos afecta tanto los datos del documento como a sus contenidos. En la utilización o cita de partes del documento es obligado indicar el nombre de la persona autora.
RE47300Alamino.pdf (8.73 Mbytes)
Fecha de Publicación
2013-12-17
 
ADVERTENCIA: Aprenda que son los trabajos derivados haciendo clic aquí.
Todos los derechos de la tesis/disertación pertenecen a los autores
Centro de Informática de São Carlos
Biblioteca Digital de Tesis y Disertaciones de la USP. Copyright © 2001-2020. Todos los derechos reservados.