Modelos de Markov ocultos (MMOs) são uma ferramenta importante em matemática aplicada e estatística. Eles se baseiam em dois processos estocásticos. O primeiro é uma cadeia de Markov, que não é observada diretamente. O segundo é observável e sua distribuição depende do estado na cadeia de Markov. Supomos que os processos são discretos no tempo e assumem um número finito de estados. Para extrair informações dos MMOs, é necessário estimar seus parâmetros. Diversos algoritmos locais têm sido utilizados nas últimas décadas para essa tarefa. Nosso trabalho estuda a estimação de parâmetros em modelos de Markov ocultos, do ponto de vista da otimização global. Desenvolvemos algoritmos capazes de encontrar, em uma execução bem sucedida, todos os estimadores de máxima verossimilhança globais de um modelo de Markov oculto. Para tanto, usamos aritmética intervalar. Essa aritmética permite explorar sistematicamente o espaço paramétrico, excluindo regiões que não contém soluções. O cálculo da função objetivo é feito através da recursão \\textit, descrita na literatura estatística. Modificamos a extensão intervalar natural dessa recursão usando programação linear. Nossa abordagem é mais eficiente e produz intervalos mais estreitos do que a implementação padrão. Experimentos mostram ganhos de 16 a 250 vezes, de acordo com a complexidade do modelo. Revisamos os algoritmos locais, tendo em vista sua aplicação em métodos globais. Comparamos os algoritmos de Baum-Welch, pontos interiores e gradientes projetados espectrais. Concluímos que o método de Baum-Welch é o mais indicado como auxiliar em otimização global. Modificamos o \\textit{interval branch and bound} para resolver a estimação de modelos com eficiência. Usamos as condições KKT e as simetrias do problema na construção de testes para reduzir ou excluir caixas. Implementamos procedimentos de aceleração da convergência, como o método de Newton intervalar e propagação de restrições e da função objetivo. Nosso algoritmo foi escrito em \\textit{C++}, usando programação genérica. Mostramos que nossa implementação dá resultados tão bons quanto o resolvedor global BARON, porém com mais eficiência. Em média, nosso algoritmo é capaz de resolver $50\\%$ mais problemas no mesmo período de tempo. Concluímos estudando aspectos qualitativos dos MMOs com mistura Bernoulli. Plotamos todos os máximos globais detectados em instâncias com poucas observações e apresentamos novos limitantes superiores da verossimilhança baseados na divisão de uma amostra grande em grupos menores. / Hidden Markov models(HMMs) are an important tool in statistics and applied mathematics. Our work deals with processes formed by two discrete time and finite state space stochastic processes. The first process is a Markov chain and is not directly observed. On the other hand, the second process is observable and its distribution depends on the current state of the hidden component. In order to extract conclusions from a Hidden Markov Model we must estimate the parameters that defines it. Several local algorithms has been used to handle with this task. We present a global optimization approach based on interval arithmetic to maximize the likelihood function. Interval arithmetic allow us to explore parametric space systematically, discarding regions which cannot contain global maxima. We evaluate the objective function and its derivatives by the so called backward recursion and show that is possible to obtain sharper interval extensions for such functions using linear programming. Numerical experiments shows that our approach is $16$ to $250$ times more efficient than standard implementations. We also study local optimization algorithms hidden Markov model estimation. We compare Baum-Welch procedure with interior points and spectral projected gradients. We conclude that Baum-Welch is the best option as a sub-algorithm in a global optimization framework. We improve the well known interval branch and bound algorithm to take advantages on the problem structure. We derive new exclusion tests, based on its KKT conditions and symmetries. We implement our approach in C++, under generic programming paradigm. We show that our implementation is compatible with global optimization solver BARON in terms of precision. We also show that our algorithm is faster than BARON. In average, we can handle with $50\\%$ more problems within the same amount of time. We conclude studying qualitative aspects of Bernoulli hidden Markov models. We plot all global maxima found in small observations instances and show a new upper bound of the likelihood based on splitting observations in small groups.

This dissertation introduces work on face recognition using a novel technique based on Hidden Markov Models (HMMs). Through the integration of a priori structural knowledge with statistical information, HMMs can be used successfully to encode face features. The results reported are obtained using a database of images of 40 subjects, with 5 training images and 5 test images for each. It is shown how standard one-dimensional HMMs in the shape of top-bottom models can be parameterised, yielding successful recognition rates of up to around 85%. The insights gained from top-bottom models are extended to pseudo two-dimensional HMMs, which offer a better and more flexible model, that describes some of the twodimensional dependencies missed by the standard one-dimensional model. It is shown how pseudo two-dimensional HMMs can be implemented, yielding successful recognition rates of up to around 95%. The performance of the HMMs is compared with the Eigenface approach and various domain and resolution experiments are also carried out. Finally, the performance of the HMM is evaluated in a fully automated system, where database images are cropped automatically.

Orientador: Fábio Violaro / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-22T07:58:43Z (GMT). No. of bitstreams: 1 Carvalho_SarahNegreirosde_M.pdf: 2350561 bytes, checksum: 950d33430acbd816700ef5de4c78fa5d (MD5) Previous issue date: 2013 / Resumo: Com o contínuo desenvolvimento da tecnologia, há uma demanda crescente por sistemas de síntese de fala que sejam capazes de falar como humanos, para integrá-los nas mais diversas aplicações, seja no âmbito da automação robótica, sejam para acessibilidade de pessoas com deficiências, seja em aplicativos destinados a cultura e lazer. A síntese de fala baseada em modelos ocultos de Markov (HMM) mostra-se promissora em suprir esta necessidade tecnológica. A sua natureza estatística e paramétrica a tornam um sistema flexível, capaz de adaptar vozes artificiais, inserir emoções no discurso e obter fala sintética de boa qualidade usando uma base de treinamento limitada. Esta dissertação apresenta o estudo realizado sobre o sistema de síntese de fala baseado em HMM (HTS), descrevendo as etapas que envolvem o treinamento dos modelos HMMs e a geração do sinal de fala. São apresentados os modelos espectrais, de pitch e de duração que constituem estes modelos HMM dos fonemas dependentes de contexto, considerando as diversas técnicas de estruturação deles. Alguns dos problemas encontrados no HTS, tais como a característica abafada e monótona da fala artificial, são analisados juntamente com algumas técnicas propostas para aprimorar a qualidade final do sinal de fala sintetizado / Abstract: With the continuous development of technology, there is a growing demand for text-to-speech systems that are able to speak like humans, in order to integrate them in the most diverse applications whether in the field of automation and robotics, or for accessibility of people with disabilities, as for culture and leisure activities. Speech synthesis based on hidden Markov models (HMM) shows to be promising in addressing this need. Their statistical and parametric nature make it a flexible system capable of adapting artificial voices, insert emotions in speech and get artificial speech of good quality using a limited amount of speech data for HMM training. This thesis presents the study realized on HMM-based speech synthesis system (HTS), describing the steps that involve the training of HMM models and the artificial speech generation. Spectral, pitch and duration models are presented, which form context-dependent HMM models, and also are considered the various techniques for structuring them. Some of the problems encountered in the HTS, such as the characteristic muffled and monotone of artificial speech, are analyzed along with some of the proposed techniques to improve the final quality of the synthesized speech signal / Mestrado / Telecomunicações e Telemática / Mestra em Engenharia Elétrica

Předkládaná práce se zabývá problémem automatizované syntézy pravděpodobnostních systémů: máme-li rodinu Markovských řetězců, jak lze efektivně identifikovat ten který odpovídá zadané specifikaci? Takové rodiny často vznikají v nejrůznějších oblastech inženýrství při modelování systémů s neurčitostí a rozhodování i těch nejjednodušších syntézních otázek představuje NP-těžký problém. V dané práci my zkoumáme existující techniky založené na protipříklady řízené induktivní syntéze (counterexample-guided inductive synthesis, CEGIS) a na zjemňování abstrakce (counterexample-guided abstraction refinement, CEGAR) a navrhujeme novou integrovanou metodu pro pravděpodobnostní syntézu. Experimenty nad relevantními modely demonstrují, že navržená technika je nejenom srovnatelná s moderními metodami, ale ve většině případů dokáže výrazně překonat, někdy i o několik řádů, existující přístupy.

Pravdepodobnostné programy zohrávajú rozhodujúcu úlohu v rôznych technických doménach, ako napríklad počítačové siete, vstavané systémy, stratégie riadenia spotreby energie alebo softvérové produčkné linky. PAYNT je nástroj na automatizovanú syntézu pravdepodobnostných programov vyhovujúcich zadaným špecifikáciam. V tejto práci rozširujeme tento nástroj predovšetkým o podporu optimálnej syntézy a syntézy viacerých špecifikácií. Ďalej sme navrhli a implementovali novú metódu, ktorá dokáže efektívne syntetizovať parametre so spojitým definičným oborom ovplyvňujúce pravdepodobnostné prechody popri syntéze topológie programov, t.j., podporu pre syntézu topológie aj parametrov súčasne. Demonštrujeme užitočnosť a výkonnosť nástroja PAYNT na širokej škále prípadových štúdií z rôznych aplikačných domén ktoré majú uplatnenie v reálnom svete. Pri náročných problémoch syntézy môže PAYNT výrazne znížiť dobu behu až z dní na minúty a zároveň zaistiť úplnosť procesu syntézy.

One of the most common methods for isolated words recognition is based on Hidden Markov models. Speech signal can be considered as a sequence of successive parts of the signal with specific statistical parameters. Hidden Markov model corresponds to the statistical model with the final number of states, which may be useful for signals such as speech. HTK module is a software tools, which is mostly used to work with hidden Markov models.

Prediction and searching for homologous protein sequences is one of important tasks which are currently being addressed in the area of bioinformatics. According to the determination of homologous sequences of unknown protein sequence it is often possible to determine its structure and function in the organism. For searching homologous sequences, the most frequently used tools are based on direct sequence comparison, profile comparison or on the use of hidden Markov models. There is no universal method better than all others. To satisfy user`s request on needed sequence identity between domains and error rate between founded true positive and false positive pairs, the selection of proper method and its settings is needed. This work is focused to create tool which will help user to choose the best method and its settings according to his requirements. It was created on the basis of the analysis of method results with different settings. In addition, the implemented  application offers the possibility to run this method and show its results.

Protein p53 which is encoded by gene TP53 plays crucial role in cell cycle as a regulator of transcription of genes in cases when cell is under stress. Therefore p53 acts like tumor suppressor. Understanding the pathway of p53 regulation as well as predicting its binding sites on p53 regulated genes is one of the major concerns of modern research in genetics and bioinformatics. In first part of this project we aim to introduce basics from molecular biology to better understand the p53 protein pathway in gene transcription and introduction to analysis of prediction of p53 binding sites. Second part is about implementation and testing of tool which would be able to predict transcription factor binding sites for protein p53.

This diploma thesis deals with handwriting recognition in real-time. It describes the ways how the intput data are processed. It is also focused on the classi cation methods, which are used for the recognition. It especially describes hidden Markov models. It also present the evaluation of the success of the recognition based on implemented experiments. The alternative keyboard for MeeGo system was created for this thesis as well. The established system achieved the success above 96%.

Condition monitoring is very important for critical assets such as gearboxes used in the power and mining industries. Fluctuating operating conditions are inevitable for wind turbines and mining machines such as bucket wheel excavators and draglines due to the continuous uctuating wind speeds and variations in ground properties, respectively. Many of the classical condition monitoring techniques have proven to be ine ective under uctuating operating conditions and therefore more sophisticated techniques have to be developed. However, many of the signal processing tools that are appropriate for uctuating operating conditions can be di cult to interpret, with the presence of incipient damage easily being overlooked. In this study, a cost-e ective diagnostic methodology is developed, using machine learning techniques, to diagnose the condition of the machine in the presence of uctuating operating conditions when only an acceleration signal, generated from a gearbox during normal operation, is available. The measured vibration signal is order tracked to preserve the angle-cyclostationary properties of the data. A robust tacholess order tracking methodology is proposed in this study using probabilistic approaches. The measured vibration signal is order tracked with the tacholess order tracking method (as opposed to computed order tracking), since this reduces the implementation and the running cost of the diagnostic methodology. Machine condition features, which are sensitive to changes in machine condition, are extracted from the order tracked vibration signal and processed. The machine condition features can be sensitive to operating condition changes as well. This makes it difficult to ascertain whether the changes in the machine condition features are due to changes in machine condition (i.e. a developing fault) or changes in operating conditions. This necessitates incorporating operating condition information into the diagnostic methodology to ensure that the inferred condition of the machine is not adversely a ected by the uctuating operating conditions. The operating conditions are not measured and therefore representative features are extracted and modelled with a hidden Markov model. The operating condition machine learning model aims to infer the operating condition state that was present during data acquisition from the operating condition features at each angle increment. The operating condition state information is used to optimise robust machine condition machine learning models, in the form of hidden Markov models. The information from the operating condition and machine condition models are combined using a probabilistic approach to generate a discrepancy signal. This discrepancy signal represents the deviation of the current features from the expected behaviour of the features of a gearbox in a healthy condition. A second synchronous averaging process, an automatic alarm threshold for fault detection, a gear-pinion discrepancy distribution and a healthy-damaged decomposition of the discrepancy signal are proposed to provide an intuitive and robust representation of the condition of the gearbox under uctuating operating conditions. This allows fault detection, localisation as well as trending to be performed on a gearbox during uctuating operation conditions. The proposed tacholess order tracking method is validated on seven datasets and the fault diagnostic methodology is validated on experimental as well as numerical data. Very promising results are obtained by the proposed tacholess order tracking method and by the diagnostic methodology. / Dissertation (MEng)--University of Pretoria, 2016. / Mechanical and Aeronautical Engineering / MEng / Unrestricted