• 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
 
 
Thèse de Doctorat
DOI
10.11606/T.43.2005.tde-14112013-135303
Document
Auteur
Nom complet
Roberto Castro Alamino
Unité de l'USP
Domain de Connaissance
Date de Soutenance
Editeur
São Paulo, 2005
Directeur
Jury
Alfonso, Nestor Felipe Caticha (Président)
Idiart, Marco Aurelio Pires
Prado, Carmen Pimentel Cintra do
Rosenfeld, Rogério
Vicente, Renato
Titre en portugais
Aprendizado em modelos de Markov com variáveis de estado escondidas
Mots-clés en portugais
Mecânica estatística
Mecânica estatística clássica
Resumé en portugais
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.
Titre en anglais
Learning in Hidden Markov Models
Mots-clés en anglais
Classical statistical mechanics
statistical mechanics
Resumé en anglais
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.
 
AVERTISSEMENT - Regarde ce document est soumise à votre acceptation des conditions d'utilisation suivantes:
Ce document est uniquement à des fins privées pour la recherche et l'enseignement. Reproduction à des fins commerciales est interdite. Cette droits couvrent l'ensemble des données sur ce document ainsi que son contenu. Toute utilisation ou de copie de ce document, en totalité ou en partie, doit inclure le nom de l'auteur.
RE47300Alamino.pdf (8.73 Mbytes)
Date de Publication
2013-12-17
 
AVERTISSEMENT: Apprenez ce que sont des œvres dérivées cliquant ici.
Tous droits de la thèse/dissertation appartiennent aux auteurs
Centro de Informática de São Carlos
Bibliothèque Numérique de Thèses et Mémoires de l'USP. Copyright © 2001-2020. Tous droits réservés.