Aprendizado em modelos de Markov com variáveis de estado escondidas

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.

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.