Técnicas de otimização em alinhamentos múltiplos de sequência via Cadeias de Markov

Pós-graduação em Ciência da Computação - IBILCE

New markov chain based methods for single and cross-domain sentiment classification

Nowadays communication is switching from a centralized scenario, where communication media like newspapers, radio, TV programs produce information and people are just consumers, to a completely different decentralized scenario, where everyone is potentially an information producer through the use of social networks, blogs, forums that allow a real-time worldwide information exchange. These new instruments, as a result of their widespread diffusion, have started playing an important socio-economic role. They are the most used communication media and, as a consequence, they constitute the main source of information enterprises, political parties and other organizations can rely on. Analyzing data stored in servers all over the world is feasible by means of Text Mining techniques like Sentiment Analysis, which aims to extract opinions from huge amount of unstructured texts. This could lead to determine, for instance, the user satisfaction degree about products, services, politicians and so on. In this context, this dissertation presents new Document Sentiment Classification methods based on the mathematical theory of Markov Chains. All these approaches bank on a Markov Chain based model, which is language independent and whose killing features are simplicity and generality, which make it interesting with respect to previous sophisticated techniques. Every discussed technique has been tested in both Single-Domain and Cross-Domain Sentiment Classification areas, comparing performance with those of other two previous works. The performed analysis shows that some of the examined algorithms produce results comparable with the best methods in literature, with reference to both single-domain and cross-domain tasks, in $2$-classes (i.e. positive and negative) Document Sentiment Classification. However, there is still room for improvement, because this work also shows the way to walk in order to enhance performance, that is, a good novel feature selection process would be enough to outperform the state of the art. Furthermore, since some of the proposed approaches show promising results in $2$-classes Single-Domain Sentiment Classification, another future work will regard validating these results also in tasks with more than $2$ classes.

La movilidad social de los emigrantes españoles en Europa

La migración española de la segunda mitad del siglo XX se ha caracterizado en un primer momento por su carácter masivo y poco cualificado, seguido por un interregno de procesos de retorno y finalmente por una migración estable, no masiva pero altamente cualificada. La atención prestada a la inmigración masiva que recibe España a finales del siglo XX relegó a un segundo plano esta emigración cualificada de españoles. En este artículo se considera la relación entre movilidad espacial (migración de españoles) y su posible consecuencia sobre la movilidad social ascendente que experimentan. Para ello se utilizan los datos procedentes de la encuesta internacional EIMSS (European Internal Migrations Social Survey) y los procedimientos de escalamiento de clase social basados en la ocupación de Goldthorpe. El análisis se complementa con una simulación sobre la movilidad de clase, con la finalidad de visualizar y comparar los efectos sobre la movilidad social de la emigración de españoles a Francia, Alemania, Italia y Gran Bretaña.

Searching for convergence in phylogenetic Markov chain Monte Carlo

Markov chain Monte Carlo (MCMC) is a methodology that is gaining widespread use in the phylogenetics community and is central to phylogenetic software packages such as MrBayes. An important issue for users of MCMC methods is how to select appropriate values for adjustable parameters such as the length of the Markov chain or chains, the sampling density, the proposal mechanism, and, if Metropolis-coupled MCMC is being used, the number of heated chains and their temperatures. Although some parameter settings have been examined in detail in the literature, others are frequently chosen with more regard to computational time or personal experience with other data sets. Such choices may lead to inadequate sampling of tree space or an inefficient use of computational resources. We performed a detailed study of convergence and mixing for 70 randomly selected, putatively orthologous protein sets with different sizes and taxonomic compositions. Replicated runs from multiple random starting points permit a more rigorous assessment of convergence, and we developed two novel statistics, delta and epsilon, for this purpose. Although likelihood values invariably stabilized quickly, adequate sampling of the posterior distribution of tree topologies took considerably longer. Our results suggest that multimodality is common for data sets with 30 or more taxa and that this results in slow convergence and mixing. However, we also found that the pragmatic approach of combining data from several short, replicated runs into a metachain to estimate bipartition posterior probabilities provided good approximations, and that such estimates were no worse in approximating a reference posterior distribution than those obtained using a single long run of the same length as the metachain. Precision appears to be best when heated Markov chains have low temperatures, whereas chains with high temperatures appear to sample trees with high posterior probabilities only rarely. [Bayesian phylogenetic inference; heating parameter; Markov chain Monte Carlo; replicated chains.]

A Markov chain location-allocation meta-model for hurricane relief

An emergency is a deviation from a planned course of events that endangers people, properties, or the environment. It can be described as an unexpected event that causes economic damage, destruction, and human suffering. When a disaster happens, Emergency Managers are expected to have a response plan to most likely disaster scenarios. Unlike earthquakes and terrorist attacks, a hurricane response plan can be activated ahead of time, since a hurricane is predicted at least five days before it makes landfall. This research looked into the logistics aspects of the problem, in an attempt to develop a hurricane relief distribution network model. We addressed the problem of how to efficiently and effectively deliver basic relief goods to victims of a hurricane disaster. Specifically, where to preposition State Staging Areas (SSA), which Points of Distributions (PODs) to activate, and the allocation of commodities to each POD. Previous research has addressed several of these issues, but not with the incorporation of the random behavior of the hurricane's intensity and path. This research presents a stochastic meta-model that deals with the location of SSAs and the allocation of commodities. The novelty of the model is that it treats the strength and path of the hurricane as stochastic processes, and models them as Discrete Markov Chains. The demand is also treated as stochastic parameter because it depends on the stochastic behavior of the hurricane. However, for the meta-model, the demand is an input that is determined using Hazards United States (HAZUS), a software developed by the Federal Emergency Management Agency (FEMA) that estimates losses due to hurricanes and floods. A solution heuristic has been developed based on simulated annealing. Since the meta-model is a multi-objective problem, the heuristic is a multi-objective simulated annealing (MOSA), in which the initial solution and the cooling rate were determined via a Design of Experiments. The experiment showed that the initial temperature (T0) is irrelevant, but temperature reduction (δ) must be very gradual. Assessment of the meta-model indicates that the Markov Chains performed as well or better than forecasts made by the National Hurricane Center (NHC). Tests of the MOSA showed that it provides solutions in an efficient manner. Thus, an illustrative example shows that the meta-model is practical.

O uso de modelos ocultos de Markov no estudo do fluxo de rios intermitentes

In this work, we present our understanding about the article of Aksoy [1], which uses Markov chains to model the flow of intermittent rivers. Then, we executed an application of his model in order to generate data for intermittent streamflows, based on a data set of Brazilian streams. After that, we build a hidden Markov model as a proposed new approach to the problem of simulation of such flows. We used the Gamma distribution to simulate the increases and decreases in river flows, along with a two-state Markov chain. The motivation for us to use a hidden Markov model comes from the possibility of obtaining the same information that the Aksoy’s model provides, but using a single tool capable of treating the problem as a whole, and not through multiple independent processes

Likelihood-Based Inference for Partially Observed Multi-Type Markov Branching Processes

Thesis (Ph.D.)--University of Washington, 2016-08

Análise do crescimento econômico no Rio Grande do Sul através da aplicação de cadeias de Markov

O estudo do crescimento econômico é de suma importância para que possamos averiguar a trajetória de uma economia ao longo do tempo, a proposta desse trabalho é analisar o crescimento econômico no estado do Rio Grande do Sul, através do instrumental das cadeias de Markov, a ideia principal do estudo está na hipótese de convergência de renda. Primeiramente será testado a hipótese de convergência de renda do estado por meio das microrregiões, para isso serão utilizados dados de produto per capita dos anos de 1990, 2000 e 2010. Também será testado a hipótese de convergência para os municípios do Conselho Regional de Desenvolvimento Sul, situado no Rio Grande do Sul, utilizando dados de renda per capita dos anos de 1991, 2000 e 2010. Os resultados obtidos para as microrregiões do Rio Grande do Sul mostram que as economias não estão convergindo em sua totalidade para uma classe de renda especifica, porém é percebido que no longo prazo haverá uma maior concentração das microrregiões nos extratos de renda próximos a média, o tempo esperado para que as economias cheguem ao seu estado estacionário é de seis períodos. Por meio dos resultados obtidos para a região do Corede Sul, temos que as economias convergirão em sua maioria para a classe de renda médio pobre, seguido pela classe dos médios ricos. Ambas as classes estão situadas próximas a média regional, sendo que as classes de renda pobre e rico situadas aos extremos serão extintas no longo prazo. O tempo esperado para que as economias cheguem ao estado estacionário é de onze períodos.

Análise do crescimento econômico no Rio Grande do Sul através da aplicação de cadeias de markov

O estudo do crescimento econômico é de suma importância para que possamos averiguar a trajetória de uma economia ao longo do tempo, a proposta desse trabalho é analisar o crescimento econômico no estado do Rio Grande do Sul, através do instrumental das cadeias de Markov, a ideia principal do estudo está na hipótese de convergência de renda. Primeiramente será testado a hipótese de convergência de renda do estado por meio das microrregiões, para isso serão utilizados dados de produto per capita dos anos de 1990, 2000 e 2010. Também será testado a hipótese de convergência para os municípios do Conselho Regional de Desenvolvimento Sul, situado no Rio Grande do Sul, utilizando dados de renda per capita dos anos de 1991, 2000 e 2010. Os resultados obtidos para as microrregiões do Rio Grande do Sul mostram que as economias não estão convergindo em sua totalidade para uma classe de renda especifica, porém é percebido que no longo prazo haverá uma maior concentração das microrregiões nos extratos de renda próximos a média, o tempo esperado para que as economias cheguem ao seu estado estacionário é de seis períodos. Por meio dos resultados obtidos para a região do Corede Sul, temos que as economias convergirão em sua maioria para a classe de renda médio pobre, seguido pela classe dos médio ricos. Ambas as classes estão situadas próximas a média regional, sendo que as classes de renda pobre e rico situadas aos extremos serão extintas no longo prazo. O tempo esperado para que as economias cheguem ao estado estacionário é de onze períodos.

A path-based framework for analyzing large markov models

Reliability and dependability modeling can be employed during many stages of analysis of a computing system to gain insights into its critical behaviors. To provide useful results, realistic models of systems are often necessarily large and complex. Numerical analysis of these models presents a formidable challenge because the sizes of their state-space descriptions grow exponentially in proportion to the sizes of the models. On the other hand, simulation of the models requires analysis of many trajectories in order to compute statistically correct solutions. This dissertation presents a novel framework for performing both numerical analysis and simulation. The new numerical approach computes bounds on the solutions of transient measures in large continuous-time Markov chains (CTMCs). It extends existing path-based and uniformization-based methods by identifying sets of paths that are equivalent with respect to a reward measure and related to one another via a simple structural relationship. This relationship makes it possible for the approach to explore multiple paths at the same time,· thus significantly increasing the number of paths that can be explored in a given amount of time. Furthermore, the use of a structured representation for the state space and the direct computation of the desired reward measure (without ever storing the solution vector) allow it to analyze very large models using a very small amount of storage. Often, path-based techniques must compute many paths to obtain tight bounds. In addition to presenting the basic path-based approach, we also present algorithms for computing more paths and tighter bounds quickly. One resulting approach is based on the concept of path composition whereby precomputed subpaths are composed to compute the whole paths efficiently. Another approach is based on selecting important paths (among a set of many paths) for evaluation. Many path-based techniques suffer from having to evaluate many (unimportant) paths. Evaluating the important ones helps to compute tight bounds efficiently and quickly.

A Unified Model for XVA, including Interest Rates and Rating

We start in Chapter 2 to investigate linear matrix-valued SDEs and the Itô-stochastic Magnus expansion. The Itô-stochastic Magnus expansion provides an efficient numerical scheme to solve matrix-valued SDEs. We show convergence of the expansion up to a stopping time τ and provide an asymptotic estimate of the cumulative distribution function of τ. Moreover, we show how to apply it to solve SPDEs with one and two spatial dimensions by combining it with the method of lines with high accuracy. We will see that the Magnus expansion allows us to use GPU techniques leading to major performance improvements compared to a standard Euler-Maruyama scheme. In Chapter 3, we study a short-rate model in a Cox-Ingersoll-Ross (CIR) framework for negative interest rates. We define the short rate as the difference of two independent CIR processes and add a deterministic shift to guarantee a perfect fit to the market term structure. We show how to use the Gram-Charlier expansion to efficiently calibrate the model to the market swaption surface and price Bermudan swaptions with good accuracy. We are taking two different perspectives for rating transition modelling. In Section 4.4, we study inhomogeneous continuous-time Markov chains (ICTMC) as a candidate for a rating model with deterministic rating transitions. We extend this model by taking a Lie group perspective in Section 4.5, to allow for stochastic rating transitions. In both cases, we will compare the most popular choices for a change of measure technique and show how to efficiently calibrate both models to the available historical rating data and market default probabilities. At the very end, we apply the techniques shown in this thesis to minimize the collateral-inclusive Credit/ Debit Valuation Adjustments under the constraint of small collateral postings by using a collateral account dependent on rating trigger.

Communication structure of cortical networks

Large-scale cortical networks exhibit characteristic topological properties that shape communication between brain regions and global cortical dynamics. Analysis of complex networks allows the description of connectedness, distance, clustering, and centrality that reveal different aspects of how the network's nodes communicate. Here, we focus on a novel analysis of complex walks in a series of mammalian cortical networks that model potential dynamics of information flow between individual brain regions. We introduce two new measures called absorption and driftness. Absorption is the average length of random walks between any two nodes, and takes into account all paths that may diffuse activity throughout the network. Driftness is the ratio between absorption and the corresponding shortest path length. For a given node of the network, we also define four related measurements, namely in-and out-absorption as well as in-and out-driftness, as the averages of the corresponding measures from all nodes to that node, and from that node to all nodes, respectively. We find that the cat thalamo-cortical system incorporates features of two classic network topologies, Erdos-Renyi graphs with respect to in-absorption and in-driftness, and configuration models with respect to out-absorption and out-driftness. Moreover, taken together these four measures separate the network nodes based on broad functional roles (visual, auditory, somatomotor, and frontolimbic).

Context tree selection: A unifying view

Context tree models have been introduced by Rissanen in [25] as a parsimonious generalization of Markov models. Since then, they have been widely used in applied probability and statistics. The present paper investigates non-asymptotic properties of two popular procedures of context tree estimation: Rissanen's algorithm Context and penalized maximum likelihood. First showing how they are related, we prove finite horizon bounds for the probability of over- and under-estimation. Concerning overestimation, no boundedness or loss-of-memory conditions are required: the proof relies on new deviation inequalities for empirical probabilities of independent interest. The under-estimation properties rely on classical hypotheses for processes of infinite memory. These results improve on and generalize the bounds obtained in Duarte et al. (2006) [12], Galves et al. (2008) [18], Galves and Leonardi (2008) [17], Leonardi (2010) [22], refining asymptotic results of Buhlmann and Wyner (1999) [4] and Csiszar and Talata (2006) [9]. (C) 2011 Elsevier B.V. All rights reserved.

TESTING STATISTICAL HYPOTHESIS ON RANDOM TREES AND APPLICATIONS TO THE PROTEIN CLASSIFICATION PROBLEM

Efficient automatic protein classification is of central importance in genomic annotation. As an independent way to check the reliability of the classification, we propose a statistical approach to test if two sets of protein domain sequences coming from two families of the Pfam database are significantly different. We model protein sequences as realizations of Variable Length Markov Chains (VLMC) and we use the context trees as a signature of each protein family. Our approach is based on a Kolmogorov-Smirnov-type goodness-of-fit test proposed by Balding et at. [Limit theorems for sequences of random trees (2008), DOI: 10.1007/s11749-008-0092-z]. The test statistic is a supremum over the space of trees of a function of the two samples; its computation grows, in principle, exponentially fast with the maximal number of nodes of the potential trees. We show how to transform this problem into a max-flow over a related graph which can be solved using a Ford-Fulkerson algorithm in polynomial time on that number. We apply the test to 10 randomly chosen protein domain families from the seed of Pfam-A database (high quality, manually curated families). The test shows that the distributions of context trees coming from different families are significantly different. We emphasize that this is a novel mathematical approach to validate the automatic clustering of sequences in any context. We also study the performance of the test via simulations on Galton-Watson related processes.

POLLING SYSTEMS WITH PARAMETER REGENERATION, THE GENERAL CASE

We consider a polling model with multiple stations, each with Poisson arrivals and a queue of infinite capacity. The service regime is exhaustive and there is Jacksonian feedback of served customers. What is new here is that when the server comes to a station it chooses the service rate and the feedback parameters at random; these remain valid during the whole stay of the server at that station. We give criteria for recurrence, transience and existence of the sth moment of the return time to the empty state for this model. This paper generalizes the model, when only two stations accept arriving jobs, which was considered in [Ann. Appl. Probab. 17 (2007) 1447-1473]. Our results are stated in terms of Lyapunov exponents for random matrices. From the recurrence criteria it can be seen that the polling model with parameter regeneration can exhibit the unusual phenomenon of null recurrence over a thick region of parameter space.