Este trabalho divide-se em três partes. Na primeira parte fazemos uma breve descrição de cadeias de Markov a tempo discreto e tempo contínuo. Na segunda parte, seguindo o artigo [5], introduzimos o formalismo termodinâmico no espaço de Bernoulli com símbolos dados em um espaço métrico compacto, generalizando a teoria usual onde o espaço de estados é finito. Após, seguindo o artigo [1], introduziremos uma versão do Operador de Ruelle para cadeias de Markov a tempo contínuo. Ainda, a partir de uma função V que funcionará como uma perturbação, definiremos um operador de Ruelle modificado e, para este operador, mostraremos a existência de uma auto-função e uma auto-medida. / This work is divided in three parts. In the first one, we give a brief description of Markov chains in both discrete time and continuous time. In the second one, following the article [5], we introduce the thermodynamic formalism in the Bernoulli space with symbols in a compact metric space, generalizing the usual theory, where the space of states is finite. Then, following the article [1], we will introduce a version of Ruelle Opemtor for Markov chains in continuous time. Also, using a V function, which will be seen as a perturbation, we will define a modified Ruelle operator and, for this operator, we will show the existence of a eigenfunction and a eigenmeasure.

A etiquetagem morfossintática envolve atribuir às palavras de uma sentença suas classes morfossintáticas de acordo com os contextos em que elas aparecem. Cadeias de Markov de Tamanho Variável (VLMCs, do inglês \"Variable-Length Markov Chains\") oferecem uma forma de modelar contextos maiores que trigramas sem sofrer demais com a esparsidade de dados e a complexidade do espaço de estados. Mesmo assim, duas palavras do português apresentam um alto grau de ambiguidade: \'que\' e \'a\'. O número de erros na etiquetagem dessas palavras corresponde a um quarto do total de erros cometidos por um etiquetador baseado em VLMCs. Além disso, essas palavras parecem apresentar dois diferentes tipos de ambiguidade: um dependendo de contexto não local e outro de contexto direito. Exploramos maneiras de expandir o modelo baseado em VLMCs através do uso de diferentes modelos e métodos, a fim de atacar esses problemas. As abordagens mostraram variado grau de sucesso, com um método em particular (aprendizado guiado) se mostrando capaz de resolver boa parte da ambiguidade de \'a\'. Discutimos razões para isso acontecer. Com relação a \'que\', ao longo desta tese propusemos e testamos diversos métodos de aprendizado de informação contextual para tentar desambiguá-lo. Mostramos como, em todos eles, o nível de ambiguidade de \'que\' permanece praticamente constante. / Part-of-speech tagging involves assigning to words in a sentence their part-of-speech class based on the contexts they appear in. Variable-Length Markov Chains (VLMCs) offer a way of modeling contexts longer than trigrams without suffering too much from data sparsity and state space complexity. Even so, two words in Portuguese show a high degree of ambiguity: \'que\' and \'a\'. The number of errors tagging these words corresponds to a quarter of the total errors made by a VLMC-based tagger. Moreover, these words seem to show two different types of ambiguity: one depending on non-local context and one on right context. We searched ways of expanding the VLMC-based model with a number of different models and methods in order to tackle these issues. The approaches showed variable degrees of success, with one particular method (Guided Learning) solving much of the ambiguity of \'a\'. We explore reasons why this happened. Rega rding \'que\', throughout this thesis we propose and test various methods for learning contextual information in order to try to disambiguate it. We show how, in all of them, the level of ambiguity shown by \'que\' remains practically c onstant.

Nesta dissertação de mestrado, vamos apresentar uma prova para os grandes desvios para variáveis aleatórias independentes e identicamente distribuídas com todos os momentos finitos e para a medida empírica de cadeias de Markov com espaço de estados finito e tempo discreto. Além disso, abordaremos os teoremas de Sanov e Gärtner-Ellis. / In this master thesis it is presented a proof of the large deviations for independent and identically distributed random variables with all finite moments and for the empirical measure of Markov chains with finite state space and with discrete time. Moreover, we address the theorems of Sanov and of Gartner-Ellis.

Grande parte do sucesso do Google provêm do algoritmo Page Rank, que avalia quantitativamente a importância de cada página na web. Esta ordenação é obtida através do vetor estacionário de uma matriz estocástica específica, utilizando o Método das Potências. A velocidade de convergência deste método será avaliada em detalhe, já que se trata de uma resposta imediata da pesquisa do usuário. Afim de entender as diferentes situações que o modelo pode enfrentar, diversas simulações são apresentadas neste trabalho. Em particular, estamos interessados nos fatores que influenciam a velocidade de convergência. Para tanto, o número de páginas total e de cada conjunto fechado, bem como o número de conjuntos fechados e de nós pendentes foram estudados. / Great part of Google\'s success comes from the Page Rank algorithm, wich quantitatively evaluates the importance of each page on the web. This sort is achieved through a specific stochastic matrix stationary vector, using the Power Method. The convergency speed of this method will be evaluated in details, since this is a imediate response for the user search. In order to understand the diferent situations the model can confront, several simulations are shown in this work. In particular, we are interested in the factors which influences the convergency speed. For that, the total and inside each closed set number of pages and also the closed sets and dangling nodes numbers were studied.

Uma forma de se reduzir o custo (em termos tanto de área de chip quanto de consumo de energia) de algoritmos de processamento de sinais é empregar aritmética de ponto fixo, usando o menor número de bits possível para se representar as variáveis e coeficientes necessários. Com isso, consegue-se reduzir a complexidade do hardware, levando a economias de energia e de área de chip em circuitos dedicados. A escolha do nível de quantização a que cada variável deve ser submetida depende de se conhecer o efeito da quantização de cada variável nas saídas do sistema, o que pode ser conseguido através de simulações (em geral lentas) ou por métodos analíticos. Este documento propõe avanços a uma nova metodologia de análise de algoritmos para processamento digital de sinais implementados em aritmética de ponto fixo, usando modelos baseados em cadeias de Markov. As contribuições desta dissertação são as seguintes: Filtros IIR de primeira e de segunda ordem são analisados via cadeia de Markov, pressupondo que a entrada possui uma função densidade de probabilidade conhecida. O modelo é desenvolvido de forma geral, de forma que pode ser considerada uma função de densidade de probabilidade qualquer. A saída dos filtros é usada para definir os estados da cadeia. O modelo via cadeia de Markov para o coeficiente do algoritmo LMS unidimensional é estendido para entrada correlacionada. Nesse caso, os estados passam a ser descritos em termos do coeficiente e do da entrada anterior. Um exemplo assumido função de densidade de probabilidade de entrada gaussiana para o filtro adaptativo é apresentado. / The implementation cost of signal processing algorithms may be reduced by using fixed-point arithmetic with the smallest possible word-length for each variable or parameter. This allows the designer to reduce hardware complexity, leading to economy of energy and chip area in dedicated circuits. The choice of word-length depends on the determination of the effect at the output of the quantization of each variable, which may be obtained through simulations (generally slow) or through analytical methods. This document proposes new advances to a new analysis method for digital signal processing algorithms implemented in fixed-point arithmetic, based on Markov chain models. Our contributions are the following: A Markov chain model is used to study first and second order IIR filters for an known input density probability function. The model is general and can be applied for any probability function. We use the output of the filters to define the states of the Markov chain. The unidimensional LMS Markov chain model is extended to correlated input. The states are defined by a pair considering the coefficient and the previous input and an example assuming Gaussian-distributed input is presented.

Mapas genéticos são arranjos lineares que indicam a ordem e distância entre locos nos cromossomos de uma determinada espécie. Recentemente, a grande disponibilidade de marcadores moleculares tem tornado estes mapas cada vez mais saturados, sendo necessários métodos eficientes para sua construção. Uma das etapas que merece mais atenção na construção de mapas de ligação é a ordenação dos marcadores genéticos dentro de cada grupo de ligação. Tal ordenação é considerada um caso especial do clássico problema do caixeiro viajante (TSP), que consiste em escolher a melhor ordem entre todas as possíveis. Entretanto, a estratégia de busca exaustiva torna-se inviável quando o número de marcadores é grande. Nesses casos, para que esses mapas possam ser construídos uma alternativa viável é a utilização de algoritmos que forneçam soluções aproximadas. O objetivo desse trabalho foi avaliar a eficiência dos algoritmos Try (TRY), Seriation (SER), Rapid Chain Delineation (RCD), Recombination Counting and Ordering (RECORD) e Unidirectional Growth (UG), além dos critérios PARF (produto mínimo das frações de recombinação adjacentes), SARF (soma mínima das frações de recombinação adjacentes), SALOD (soma máxima dos LOD scores adjacentes) e LMHC (verossimilhança via cadeias de Markov ocultas), usados juntamente com o algoritmo de verificação de erros RIPPLE, para a construção de mapas genéticos. Para tanto, foi simulado um mapa de ligação de uma espécie vegetal hipotética, diplóide e monóica, contendo 21 marcadores com distância fixa entre eles de 3 centimorgans. Usando o método Monte Carlo, foram obtidas aleatoriamente 550 populações F2 com 100 e 400 indivíduos, além de diferentes combinações de marcadores dominantes e codominantes. Foi ainda simulada perda de 10% e 20% dos dados. Os resultados mostraram que os algoritmos TRY e SER tiveram bons resultados em todas as situações simuladas, mesmo com presença de elevado número de dados perdidos e marcadores dominantes ligados em repulsão, podendo ser então recomendado em situações práticas. Os algoritmos RECORD e UG apresentaram bons resultados na ausência de marcadores dominantes ligados em repulsão, podendo então ser recomendados em situações com poucos marcadores dominantes. Dentre todos os algoritmos, o RCD foi o que se mostrou menos eficiente. O critério LHMC, aplicado com o algoritmo RIPPLE, foi o que apresentou melhores resultados quando se deseja fazer verificações de erros na ordenação. / Genetic linkage maps are linear arrangements showing the order and distance between loci in chromosomes of a particular species. Recently, the availability of molecular markers has made such maps more saturated and efficient methods are needed for their construction. One of the steps that deserves more attention in the construction of genetic linkage maps is the ordering of genetic markers within each linkage group. This ordering is considered a special case of the classic traveling salesman problem (TSP), which consists in choosing the best order among all possible ones. However, the strategy of exhaustive search becomes unfeasible when the number of markers is large. One possible alternative to construct such maps is to use algorithms that provide approximate solutions. Thus, the aim of this work was to evaluate the efficiency of algorithms Try (TRY), Seriation (SER), Rapid Chain Delineation (RCD), Recombination Counting and Ordering (RECORD) and Unidirectional Growth (UG), as well as the criteria PARF (product of adjacent recombination fractions), SARF (sum of adjacent recombination fractions), SALOD (sum of adjacent lod scores) and LMHC (likelihood via hidden Markov chains), used with the RIPPLE algorithm for error verification, in the construction of genetic linkage maps. For doing so, a linkage map of a hypothetical diploid and monoecious plant species was simulated, containing 21 markers with fixed distance of 3 centimorgans between them. Using Monte Carlo methods, 550 F2 populations were randomly simulated with 100 and 400 individuals, together with different combinations of dominant and codominant markers. 10 % and 20 % of missing data was also included. Results showed that the algorithms TRY and SER gave good results in all situations, even with presence of a large number of missing data and dominant markers linked in repulsion phase. Thus, these can be recommended for analyzing real data. The algorithms RECORD and UG gave good results in the absence of dominant markers linked in repulsion phase and can be used in this case. Among all algorithms, RCD was the least efficient. The criterion LHMC, applied with the RIPPLE algorithm, showed the best results when the goal is to check ordering errors.

Made available in DSpace on 2013-08-07T18:43:08Z (GMT). No. of bitstreams: 1 000423499-Texto+Completo-0.pdf: 2268638 bytes, checksum: a9a287a49644290eaf88a8b8d38f9f10 (MD5) Previous issue date: 2010 / Several formalisms have been defined throughout the years aiming the enhancement of the abstraction level which offer a more sophisticated modeling alternative than traditional Markov Chains. Examples of formalisms that use tensor algebra for descriptor storage are Stochastic Automata Networks, Superposed Generalized Stochastic Petri Nets, and Process Algebras. These descriptions employ modeling primitives among their components by capturing their operational semantics, and allow analysis by returning quantitative performance indexes when subjected to numerical solution. Solution mechanisms use both classic and generalized Tensor Algebra properties to multiply tensor terms of events among the states of the models (i. e., a Markovian descriptor) by a probability vector, using stationary or transient measurements. This operation is called Vector-Descriptor Multiplication (VDM), and can be performed by three different methods: sparsely (memory inefficient, time efficient), using the Shuffle Algorithm (memory efficient, time inefficient, depending on the model) or through the Split Algorithm, a combination between the two former approaches. The main contribution of the Split approach was the proposition of a hybrid method where memory increments (in a reasonable fashion) are used to accelerate the calculations per iteration. On the other hand, the main challenge of the Split Algorithm is the determination of each division point (e. g. the cut parameter), and how the tensor terms must be restructured to reduce computational costs per iteration, allowing quicker convergence for structured models. The present work addresses these problems in three distinct ways: i) by discussing the modeling primitives for system composition through more abstract ways of description, ii) by treating each tensor term of Markovian descriptors in different manners for more optimized VDM solution restructuring the original orders, iii) by executing the Algorithm Split having both constant or functional rates, demonstrating the results for a variety of models. The experiments discussed here demonstrate that the best gain considering time and memory is verified when the matrices of the tensor terms are reordered, treating the identity ones in the structured part and evaluating functional elements just once in the sparse part. When the functions were evaluated only once in all VDM process, a conversion of generalized to classic descriptor took place in execution time, with considerable gain in time for some classes of models. In addition, it was observed that synchronization or communication activities between each module or system partition and the total number of functional parameters play a crucial role in the overall performance. The present thesis is finalized with the identification of the most suitable class of models for the utilization of the Split Algorithm, and the proposition of a restructuration of Markovian that privileges sparsity and identity matrices to balance memory costs and execution time. / Os formalismos estruturados foram definidos ao longo dos anos com o objetivo de aumentar o nível de abstração e oferecer uma alternativa de modelagem mais sofisticada do que a proporcionada pelas tradicionais Cadeias de Markov. Exemplos de formalismos estruturados que utilizam álgebra tensorial para o armazenamento de seus descritores são as Redes de Autômatos Estocásticos, as Redes de Petri Estocásticas Generalizadas Superpostas e as Álgebras de Processo. Tais descrições utilizam primitivas de modelagem entre seus componentes capturando sua semântica operacional e permitindo a sua análise ao retornarem índices quantitativos de desempenho quando são resolvidos numericamente. Os mecanismos atuais de solução usam propriedades da Álgebra Tensorial (clássica ou generalizada) para multiplicar termos tensoriais de eventos entre os estados dos modelos (i. e., um descritor Markoviano) por um vetor de probabilidade, que contém a solução estacionária ou transiente. Esta operação é chamada de Multiplicação Vetor-Descritor (MVD) e é realizada de três maneiras básicas: de forma esparsa (ineficiente em memória, eficiente em tempo), utilizando o Algoritmo Shuffle (eficiente em memória, ineficiente em tempo para algumas classes de modelos) ou através do Algoritmo Split, que é uma combinação das duas primeiras abordagens. A principal contribuição deste último foi a proposição de um método híbrido onde incrementa-se a memória (de forma razoável) para acelerar o cálculo efetuado por iteração. Entretanto, o principal desafio do Algoritmo Split é relativo à determinação de cortes de cada termo tensorial e em como re-estruturá-lo para reduzir o custo computacional por iteração, acelerando a convergência de modelos estruturados. Este trabalho aborda estes problemas, baseando-se em três eixos: i) na discussão das primitivas de modelagem para composição de sistemas através de formas mais abstratas de descrição, ii) nas diferentes formas de tratamento de termos tensoriais de descritores Markovianos para execução mais otimizada da MVD a partir de re-estruturações das ordens originais, e iii) na execução do Algoritmo Split com taxas constantes ou funcionais demonstrando os resultados obtidos para diversas classes de modelos. Para os casos observados, foi demonstrado através de experimentos que o melhor ganho, balanceando-se tempo e memória, é verificado quando as matrizes dos termos tensoriais são reordenadas, tratando as do tipo identidade na parte estruturada e avaliando-se os elementos funcionais uma única vez na parte esparsa. Ao avaliar as funções somente uma vez em todo o processo de MVD, converte-se os descritores generalizados para clássicos em tempo de execução e promove-se ganhos consideráveis em tempo para determinadas classes de modelos. Observou-se também que as atividades de sincronização ou comunicação entre os módulos ou partições envolvidas bem como o total de parâmetros das dependências funcionais realizam um papel crucial no desempenho obtido. A presente tese é finalizada identificando as classes de modelos mais adequadas para a utilização do Algoritmo Split, propondo formas de re-estruturação de descritores Markovianos que privilegiem a esparsidade e a existência de matrizes do tipo identidade para balancear os custos em memória e tempo de execução.

Made available in DSpace on 2013-08-07T18:43:22Z (GMT). No. of bitstreams: 1 000447661-Texto+Completo-0.pdf: 550622 bytes, checksum: 5a831618aedabce5554e131c45fcd8d9 (MD5) Previous issue date: 2013 / This work presents a formalism for modeling systems called Stochastic Automata Networks (SAN), SAN formalism aims to increase the abstraction’s level and provides a sophisticated alternative model to the tadicional formalism of Markov Chains (MC). SAN uses both Classical (CTA) and Generalized Tensor Algebra (GTA) to simplify the matrix of transitions between states of the model. Despite all models described with GTA having at least one equivalent model described using CTA, and that the solution of certain models based on CTA could be faster than the equivalent GTA based model, this dissertation proposes an algorithm for translating a model described in GTA into the equivalent model described in CTA. It is expected that some models described using functions (using GTA) could be solved more quickly or taking less memory through the solution of its CTA-converted model. / Este trabalho apresenta o formalismo para modelagem de sistemas chamado Redes de Autômatos Estocásticos (SAN). O formalismo SAN tem o objetivo de aumentar o nível de abstração e oferece uma alternativa de modelagem mais sofisticada do que a proporcionada pelas tradicionais Cadeias de Markov (MC). Este formalismo utiliza a álgebra tensorial clássica (CTA) e geralizada (GTA) para simplificar a matriz das transições entre os estados do modelo. Embora todos os modelos SAN descritos utilizando GTA possuam pelo menos um modelo equivalente descrito utilizando CTA, e que a solução de certos modelos utilizando CTA possa ser mais rápido que o modelo equivalente que utiliza GTA, este trabalho propõe um algoritmo para traduzir um modelo descrito em GTA para o modelo equivalente descrito em CTA. Espera-se com isto permitir que um modelo descrito utilizando funções (usando GTA) possa ser resolvido mais rapidamente ou ocupando menos memória através da solução de seu modelo convertido para CTA.

Este trabalho estuda um tema relativamente recente na literatura econômica conhecido por contágio. Utilizando-se de modelos de mudança de regime markoviana multivariados (MS e MSGARCH) faz-se um estudo do comportamento das correlações ao longo do tempo entre alguns mercados de ações. Vale dizer, as correlações entre mercados de ações latino-americanos (Brasil, Argentina e México) e entre mercados asiáticos (Tailândia, Malásia e Coréia do Sul). O período abrangido pela amostra vai de janeiro de 1994 a início de janeiro de 2002, cobrindo, assim, as crises econômico-financeiras vivenciadas a partir de meados da década de noventa (a crise mexicana, em 1994/95, a crise asiática, em 1997, a crise russa, em 1998, e a crise brasileira, em 1999). A análise do comportamento das correlações ao longo do tempo mostrou que, para os mercados latino-americanos não houve evidência de contágio no período considerado, e sim, interdependência entre eles. Por outro lado, para os mercados de ações asiáticos, constatou-se a ocorrência de contágio entre os mercados tailandês e coreano e entre os mercados malaio e coreano.

Esta dissertação procura promover uma análise da mudança de regimes na volatilidade condicional do risco Brasil, após a implementação do Real, com ênfase nas mudanças markovianas de regimes. De acordo com a literatura de risco país, na presença de equilíbrios múltiplos e profecias auto-realizáveis, a deterioração dos fundamentos percebidos de um país é condição necessária para a determinação de um equilíbrio macroeconômico ruim de uma pequena economia aberta e em desenvolvimento (PEAD), com reversão de capitais, alto serviço da dívida pública, perspectivas sombrias de crescimento e uma avaliação do crédito como ruim (Razin & Sadka, 2001). Ainda que tal condição seja necessária, ela não parece ser suficiente para explicar por que, em alguns momentos, apesar de um nível alto de risco país, o equilíbrio tido como ruim não se materializa. Neste sentido, através da adaptação de um jogo típico de modelos de crises cambiais de segunda geração, esta dissertação lança a hipótese de que uma das razões pelas quais uma PEAD sofra tais crises de liquidez seja a deterioração da média dos fundamentos percebidos ao lado do aumento do medo dos investidores de que haja interrupções no fluxo de capitais. A metodologia utilizada é a dos modelos GARCH nãolineares com componentes observáveis e não observáveis markovianos, aplicados à série diária do risco país do Brasil entre maio de 1994 a setembro de 2002. Os resultados empíricos sugerem que, de fato, durante os episódios de crise de liquidez do Brasil, o risco país sobe e a volatilidade muda para um regime mais alto. Em contrapartida, nos períodos com regimes baixos de volatilidade, independentemente do nível do risco país, nenhuma crise severa e repentina atinge o país. Além disso, ainda que não desprovida de limitações, a análise da volatilidade condicional do risco país pode servir como um instrumento prático de monitoramento da duração de crises de liquidez para uma PEAD altamente dependente do influxo de capitais externos como o Brasil.