ITC/USA 2011 Conference Proceedings / The Forty-Seventh Annual International Telemetering Conference and Technical Exhibition / October 24-27, 2011 / Bally's Las Vegas, Las Vegas, Nevada / The introduction of network elements into telemetry systems brings a level of complexity that makes performance analysis difficult, if not impossible. Packet simulation is a well understood tool that enables performance prediction for network designs or for operational forecasting. Packet simulators must however be customized to incorporate aeronautical radio channels and other effects unique to the telemetry application. This paper presents a method for developing a Markov Model simulation for aeronautical channels for use in packet network simulators such as OPNET modeler. It shows how the Hidden Markov Model (HMM) and the Markov Model (MM) can be used together to first extract the channel behavior of an OFDM transmission for an aeronautical channel, and then effortlessly replicate the statistical behavior during simulations in OPENT Modeler. Results demonstrate how a simple Markov Model can capture the behavior of very complex combinations of channel and modulation conditions.

Markov Logic (ML) is a novel approach to Natural Language Processing tasks [Richardson and Domingos, 2006; Riedel, 2008]. It is a Statistical Relational Learning language based on First Order Logic (FOL) and Markov Networks (MN). It allows one to treat a task as structured classification. In this work, we investigate ML for the semantic processing tasks of Spoken Language Understanding (SLU) and Semantic Role Labelling (SRL). Both tasks consist of identifying a semantic representation for the meaning of a given utterance/sentence. However, they differ in nature: SLU is in the field of dialogue systems where the domain is closed and language is spoken [He and Young, 2005], while SRL is for open domains and traditionally for written text [M´arquez et al., 2008]. Robust SLU is a key component of spoken dialogue systems. This component consists of identifying the meaning of the user utterances addressed to the system. Recent statistical approaches to SLU depend on additional resources (e.g., gazetteers, grammars, syntactic treebanks) which are expensive and time-consuming to produce and maintain. On the other hand, simple datasets annotated only with slot-values are commonly used in dialogue system development, and are easy to collect, automatically annotate, and update. However, slot-values leave out some of the fine-grained long distance dependencies present in other semantic representations. In this work we investigate the development of SLU modules with minimum resources with slot-values as their semantic representation. We propose to use the ML to capture long distance dependencies which are not explicitly available in the slot-value semantic representation. We test the adequacy of the ML framework by comparing against a set of baselines using state of the art approaches to semantic processing. The results of this research have been published in Meza-Ruiz et al. [2008a,b]. Furthermore, we address the question of scalability of the ML approach for other NLP tasks involving the identification of semantic representations. In particular, we focus on SRL: the task of identifying predicates and arguments within sentences, together with their semantic roles. The semantic representation built during SRL is more complex than the slot-values used in dialogue systems, in the sense that they include the notion of predicate/argument scope. SRL is defined in the context of open domains under the premises that there are several levels of extra resources (lemmas, POS tags, constituent or dependency parses). In this work, we propose a ML model of SRL and experiment with the different architectures we can describe for the model which gives us an insight into the types of correlations that the ML model can express [Riedel and Meza-Ruiz, 2008; Meza-Ruiz and Riedel, 2009]. Additionally, we tested our minimal resources setup in a state of the art dialogue system: the TownInfo system. In this case, we were given a small dataset of gold standard semantic representations which were system dependent, and we rapidly developed a SLU module used in the functioning dialogue system. No extra resources were necessary in order to reach state of the art results.

Cette thèse se situe à l'interface de la statistique et de la fouille de données. Elle est composée de trois parties indépendantes. Dans la première, nous cherchons à estimer l'ordre (le nombre d'États cachés) d'un modèle de Markov caché dont la distribution d'émission appartient à la famille exponentielle. Nous nous plaçons dans le cas où aucune borne supérieure sur cet ordre n'est connue a priori. Nous définissons deux estimateurs pénalisés pour cet ordre, l'un basé sur le maximum de vraisemblance et l'autre sur une statistique de mélange bayésien. Nous montrons la consistance forte de ces estimateurs. Dans la deuxième partie, nous extrayons des motifs séquentiels dont la fréquence est exceptionnellement élevée par rapport à un modèle de Markov. L'approche consiste à dénombrer dynamiquement toutes les positions possibles d'un motif au sein d'une séquence. Puis la fréquence observée est comparée à la fréquence attendue à l'aide d'un test binomial. Une procédure est utilisée pour tenir compte des tests multiples. Des expérimentations sont menées sur des bases synthétiques et des séquences de protéines. Enfin, dans la troisième partie, nous nous intéressons au calcul de l'estimateur à noyau de la densité. Les observations sont regroupées dans des structures hiérarchiques d'arbres binaires. Les calculs sont réalisés sur les nœuds, plutôt que sur les points, pour une plus grande efficacité. Nous effectuons le calcul sur un Échantillon de points de chaque nœud, au lieu de sa totalité, en utilisant des inégalités de concentration non-paramétriques pour contrôler l'erreur. Puis, nous proposons un nouveau parcours de l'arbre pour effectuer ces échantillonnages sur un nombre réduit de nœuds. Nous testons notre approche sur des jeux de données synthétiques. / This Ph.D thesis lies at the interface of statistics and data mining. It contains three independent parts. In the first one, we aim at estimating the order (the number of hidden states) of a Hidden Markov Model, whose emission distribution belongs to the exponential family. We suppose that no upper bound is known on this order. We define two penalised estimators for this order, one based on the maximum likelihood, an the other on a bayesian mixture statistic. We prove that both estimators are strongly consistent. In the second part, we extract sequential patterns of exceptional frequency given a Markov model. We first dynamically enumerate all the possible occurences of a pattern in a sequence. Then, the observed frequency is compared to the expected frequency using a binomial test. Multiple testing is taken into account. Experiments are led on synthetic databases and protein sequences. Finally, in the third chapter, we are interested in kernel density estimation. The observations are gathered in hierarchical structures called binary trees. Computations are done on nodes of trees, rather than on raw observations, for greater efficiency. We only take into account samples on each node, instead of all the observations, using a non-parametric concentration inequality to control the error. We also propose to only browse some parts of the tree. We test our approach on synthetic datasets.

In this dissertation the results of Jerrum and Sinclair on the conductance of Markov chains are used to prove that almost all generalized Steinhaus graphs are rapidly mixing and an algorithm for the uniform generation of 2 - (4k + 1,4,1) cyclic Mendelsohn designs is developed.

Magíster en Gestión de Operaciones / Ingeniera Civil Industrial / La prevención del crimen ha ganado cada vez más espacio e importancia entre las políticas públicas en seguridad ciudadana, tanto en Chile como en el mundo. Durante la investigación realizada en este trabajo, se desarrolla un modelo para predecir los crímenes sobre una ciudad, que incluye el efecto de intervenciones preventivas y que permite además estudiar el fenómeno de desplazamiento que se le atribuye a este tipo de medidas. Ambos aspectos incluidos rara vez en los modelos de predicción revisados en la literatura. La estructura utilizada corresponde a un modelo de Markov oculto, donde el atractivo de un lugar para cometer un tipo específico de crimen se considera oculto y se estudia a través de el registro de crímenes observados en dicho lugar, considerando el efecto que intervenciones policiales podrían tener. De manera de demostrar el tipo de información y uso que se puede hacer del modelo desarrollado, se aplicó éste en un caso de estudio. Los datos de los crímenes y vigilancia policial utilizados se obtuvieron mediante un simulador del crimen sobre una ciudad ficticia. El modelo estimado, permitió comparar el efecto de la vigilancia en el lugar donde es ubicada, así como en las áreas aledañas, según el atractivo de cada lugar. Encontrándose que las celdas más atractivas son más susceptibles a esta vigilancia, tanto en la reducción de crímenes esperados al posicionarse un vigilante en un lugar, como en el aumento de la tasa de crímenes cuando un policía es ubicado en lugares aledaños. A partir de las matrices de transición se clasificaron las unidades de estudio, que componen la ciudad virtual, según su potencial para pasar a un estado de alta atractividad. Donde le grupo más numeroso corresponde al de celdas, de Bajo y Mediano Potencial, que permanecen en el mínimo estado de atractividad, reportando pocos crímenes en el lugar. Por el contrario, aquellas celdas, de Alto Potencial, que tienen probabilidades significativas de llegar y permanecer en estados de alta atractividad es el grupo menos numeroso, y el que además suele concentrar los crímenes. Esto se alinea con lo que sugiere la literatura respecto a unos pocos lugares concentrado la mayoría de los crímenes. Para validar el modelo se comparó su ajuste y predicciones con los obtenidos de otros cuatro modelos con diferentes especificaciones y estructuras (HMM Homogéneo, Clases Latentes, Regresión de Poisson y Persistencia), obteniendo mejores tasas de aciertos en la predicción de los crímenes futuros, de alrededor del 97%. Además el modelo destaca prediciendo los crímenes de las celdas de Alto Potencial, respecto a los modelos alternativos, alcanzando tasas de aciertos de 97% en comparación con las obtenidas por los otros cuatro modelos: 78%, 92%, 48% y 34% respectivamente. Se concluye además, en el experimento, que la inclusión del efecto de la policía permite capturar mejor el fenómeno delictivo, mejorando el desempeño al predecir el número de crímenes. Finalmente, en relación a los objetivos planteados en este trabajo, se puede concluir que el modelo HMM desarrollado logra incorporar de forma efectiva los dos atributos que se deseaban estudiar en el fenómeno delictivo: considerar la atractividad de forma dinámica,actualizándose período a período, e incluir el efecto de la vigilancia en la predicción.

Magíster en Gestión de Operaciones / Ingeniero Civil Industrial / Hidden Markov models (HMM) han sido ampliamente usados para modelar comportamientos dinámicos tales como atención del consumidor, navegación en internet, relación con el cliente, elección de productos y prescripción de medicamentos por parte de los médicos. Usualmente, cuando se estima un HMM simultáneamente para todos los clientes, los parámetros del modelo son estimados asumiendo el mismo número de estados ocultos para cada cliente. Esta tesis busca estudiar la validez de este supuesto identificando si existe un potencial sesgo en la estimación cuando existe heterogeneidad en el número de estados. Para estudiar el potencial sesgo se realiza un extenso ejercicio de simulación de Monte Carlo. En particular se estudia: a) si existe o no sesgo en la estimación de parámetros, b) qué factores aumentan o disminuyen el sesgo, y c) qué métodos pueden ser usados para estimar correctamente el modelo cuando existe heterogeneidad en el número de estados. En el ejercicio de simulación, se generan datos utilizando un HMM con dos estados para el 50% de clientes y un HMM con tres estados para el 50% restante. Luego, se utiliza un procedimiento MCMC jerárquico Bayesiano para estimar los parámetros de un HMM con igual número de estados para todos los clientes. En cuanto a la existencia de sesgo, los resultados muestran que los parámetros a nivel individual son recuperados correctamente, sin embargo los parámetros a nivel agregado correspondientes a la distribución de heterogeneidad de los parámetros individuales deben ser reportados cuidadosamente. Esta dificultad es generada por la mezcla de dos segmentos de clientes con distinto comportamiento. En cuanto los factores que afectan el sesgo, los resultados muestran que: 1) cuando la proporción de clientes con dos estados aumenta, el sesgo de los resultados agregados también aumenta; 2) cuando se incorpora heterogeneidad en las probabilidades condicionales, se generan estados duplicados para los clientes con 2 estados y los estados no representan lo mismo para todos los clientes, incrementando el sesgo a nivel agregado; y 3) cuando el intercepto de las probabilidades condicionales es heterogéneo, incorporar variables exógenas puede ayudar a identificar los estados igualmente para todos los clientes. Para reducir los problemas mencionados se proponen dos enfoques. Primero, usar una mezcla de Gaussianas como distribución a priori para capturar heterogeneidad multimodal, y segundo usar un modelo de clase latente con HMMs de distintos número de estados para cada clase. El primer modelo ayuda en representar de mejor forma los resultados agregados. Sin embargo, el modelo no evita que existan estados duplicados para los clientes con menos estados. El segundo modelo captura la heterogeneidad en el número de estados, identificando correctamente el comportamiento a nivel agregado y evitando estados duplicados para clientes con dos estados. Finalmente, esta tesis muestra que en la mayoría de los casos estudiados, el supuesto de un número fijo de estados no genera sesgo a nivel individual cuando se incorpora heterogeneidad. Esto ayuda a mejorar la estimación, sin embargo se deben tomar precauciones al realizar conclusiones usando los resultados agregados.

Consideremos uma sequência de lançamentos de moedas em que denotamos o resultado de cada lançamento por H, se der cara, ou por T, se der coroa. Formemos uma palavra apenas com H\'s e T\'s, por exemplo, HHHHH ou HTHTH. Quantas vezes arremessaremos uma mesma moeda ate que uma das duas palavras acima ocorrera? Por exemplo, dadas as sequências THTHHHHH e TTHTTHTHTH. O numero de vezes que arremessamos a moeda ate que HHHHH e HTHTH ocorreram pela primeira vez e oito e dez, respectivamente. Podemos generalizar a ideia acima para um numero finito de palavras em um alfabeto finito qualquer. Assim, o nosso principal objetivo dessa dissertação e encontrarmos a distribuição do tempo de espera ate que um membro de uma coleção finita de palavras seja observado em uma sequência de ensaios de Markov de letras de um alfabeto finito. Mais especificamente, as letras de um alfabeto finito são geradas por uma cadeia de Markov ate que uma das palavras de uma coleção finita ocorra. Além disso encontraremos a probabilidade de que determinada palavra ocorra antes das demais palavras pertencentes a um mesmo conjunto finito. Por ultimo encontraremos a função geradora de probabilidade do tempo de espera. / Consider a sequence of independent coin flips where we denote the result of any landing for H, if coming up head, or T, otherwise. Create patterns with H\'s and T\'s, for example, HHHHH or HTHTH. How many times do we have to land the same coin until one such two patterns happens? For example, let the sequences being THTHHHHH and TTHTTHTHTH. The number of times that we landed the coin until HHHHH and HTHTH happens it was eight and ten times respectively. We can generalize this idea for a finite number of patterns in any finite set. Then, the first of all interest of this dissertation is to find the distribution of the waiting time until a member of a finite colection of patterns is observed in a sequence of Markov chains of letters in from finite set. More specically the letters in a finite set are generated by Markov chain until one of the patterns in any finite set happens. Besides that, we will find the probability of a pattern happen before of all patterns in the same finite set. Finally we will find the generator function of probability of waiting time.

Orientador: Mário Hissamitsu Tarumoto / Resumo: A observação de fenômenos naturais, como as mudanças de temperatura é bastante frequente no mundo atual, de forma que vários estudos têm sido realizados com o intuito de prever a ocorrência delas tendo em vista o que ocorreu no passado. Estudos desta natureza, em que a coleta de dados ocorre de forma contínua, seja por medida horária ou diária, não apresenta independência entre as observações. Entre as possíveis formas de análise, há a aplicação de técnicas de séries temporais ou também a teoria dos valores extremos. No entanto, um dos objetivos deste estudo é construir uma matriz de transição, de tal forma que possamos determinar a probabilidade, por exemplo, de alta temperatura amanhã, dado que hoje foi observado este fenômeno. Para a obtenção deste resultado, uma possibilidade é construir um modelo baseado em dados dependentes que seguem um processo de Markov, em que a suposição é de que exista dependência somente com o dia anterior. Neste trabalho, pretendemos construir este modelo e realizar a aplicação em dados de temperatura na cidade de Presidente Prudente-SP no período de janeiro de 2011 a dezembro de 2016. Posteriormente vamos realizar comparações entre o modelo markoviano de nido a partir da distribuição Weibull bivariada de Marshall e Olkin e outros modelos markovianos de nidos a partir das funções cópulas. / Abstract: The observation of natural phenomena, such as temperature changes, is quite frequent in the world today, so that several studies have been carried out with the intention of predicting their occurrence in view of what has happened in the past. Data of this nature, in which the data collection occurs continuously, whether by hourly or daily measurement, does not present independence between observations. Among the possible forms of analysis is the application of time-series techniques, however, the purpose of this study is to construct a transition matrix, so that we can determine the probability, for example, of high temperature tomorrow, since today this phenomenon was observed. To obtain this result, one possibility is to construct a model based on dependent data that follows a Markov process, in which the assumption is that there is dependence only with the previous day. In this work, we intend to build this model and perform the application on temperature data in the city of Presidente Prudente-SP from January 2011 to December 2016. For which comparisons were made between the Markovian model de ned from the distribution Weibull bivariate of Marshall and Olkin and other Markovian models de ned from the copula functions. / Mestre

A contextualização de eventos próximos da realidade dos alunos aliada a utilização da informática como ferramenta auxiliar no aprendizado da probabilidade, pode ser um dos caminhos para a melhoria do ensino de Matemática. Assim, este trabalho buscou a modelagem matemática de eventos temporais do dia a dia dos alunos do ensino básico. A modelagem se baseou no conceito de Cadeias de Markov e teve o objetivo de auxiliar o professor dos ensinos fundamental e médio a introduzir o conceito de probabilidade. As aplicações das Cadeias de Markov também possibilitam apresentar aos alunos dos ensinos médio e fundamental como a Matemática pode resolver problemas do cotidiano. Para introduzir os conceitos de Cadeias de Markov foi necessário uma revisão teórica dos conceitos da teoria da probabilidade e os conceitos de Cadeias de Markov foram estudados em literatura em língua inglesa. Considerando o interesse e curiosidade demonstrado pelos alunos em experiência prévia com o material, as atividades mostraram-se muito eficientes. Espera-se que esse trabalho possa contribuir para a prática docente de outros professores. / The contextualization of events close to the reality of the students allied to the use of information technology as an auxiliary tool in the learning of probability, can be one of the ways to improve the teaching of Mathematics. Thus, this paper sought the mathematical modeling of temporal events from the daily of students of basic Education. The modeling was based on the concept of Markov Chains and aimed to help the middle and high school teachers to introduce the concept of probability. The applications of the Markov Chains also make it possible to present to the students of the middle and high school teachings how Mathematics can solve daily problems. To introduce the concepts of Markov Chains, a theoretical revision of the concepts of probability theory was necessary and the concepts of Markov Chains were studied in literature in English Language. Considering the interest and curiosity demonstrated by the students in previous experience with the material, the activities were very efficient. It is hoped that this paper may contribute to the teaching practice of other teachers.

A fibrilação atrial (FA) é um dos tipos mais freqüentes de arritmia cardíaca e é caracterizada principalmente pela aleatoriedade na ocorrência dos batimentos do coração. Sob este aspecto, a fibrilação atrial pode ser considerada um processo estocástico e por isso tem sido freqüentemente modelada através de cadeias de Markov. Seguindo trabalhos anteriores sobre este tópico, este trabalho modela seqüências temporais de batimentos cardíacos como um processo markoviano de três estados para detecção automática de FA. O modelo foi treinado e desenvolvido através dos sinais da base de dados MIT-BIH. Outro método mais consolidado na detecção de FA, denominado \"Razão RR\", também foi implementado, com o objetivo de comparar os resultados do Modelo Markoviano. A avaliação de desempenho para ambos os métodos implementados fo i realizada medindo-se a sensibilidade (Se) e o valor preditivo positivo (+P) para a detecção de FA. Estes dois métodos - Modelos Markovianos e \"Razão RR\" - tiveram seus coeficientes e limiares otimizados com o objetivo de maximizar, ao mesmo tempo, os valores de Se e +P. Após a otimização, ambos os métodos foram testados com uma nova base de dados, independente da base de dados de desenvolvimento. Os resultados obtidos com a base de dados de teste foram Se=84,940% e +P=81,579%, consolidando os Modelos Markoviano s para detecção de batimentos aleatórios. / Atrial fibrillation (AF) is one of the most common cardiac arrhythmia and it is mainly characterized by the presence of random RR intervals. In this way, atrial fibrillation has been studied as a stochastic process and it has been often modeled through Markov chains. Following previous studies on this subject, this work models time sequences of heartbeats as a three states Markov process for AF automatic detection. The model was trained and developed using signals from MIT-BIH database. Another consolidated method for AF detection, called \"RR Ratios\", was also applied to compare Markov Model\'s results. The performance evaluation of both methods was measured through sensitivity (Se) and positive predictive (+P) for AF detection. These two methods - Markov Model and \"RR Ratio\" - had their coefficients and thresholds optimized in order to maximize the values of Se and +P at the same time. After optimization, both methods were tested with another database, independent of development database. The obtained results were Se = 84,940% and +P = 81,579%, consolidating Markov Models for detecting random heartbeats.