In this thesis we develop a system for recognition of strings of connected digits that can be used in a hands-free telephone system. We present a detailed description of the elements of the recognition system, such as an endpoint algorithm, the extraction of feature vectors from the speech samples, and the practical issues involved in training and recognition, in a Hidden Markov Model (HMM) based speech recognition system. We use continuous mixture densities to approximate the observation probability density functions (pdfs) in the HMM. While more complex in implementation, continuous (observation) HMMs provide superior performance to the discrete (observation) HMMs. Due to the nature of the application, ours is a speaker dependent recognition system and we have used a single speaker's speech to train and test our system. From the experimental evaluation of the effects of various model sizes on recognition performance, we observed that the use of HMMs with 7 states and 4 mixture density components yields average recognition rates better than 99% on the isolated digits. The level-building algorithm was used with the isolated digit models, which produced a recognition rate of better than 90% for 2-digit strings. For 3 and 4-digit strings, the performance was 83 and 64% respectively. These string recognition rates are much lower than expected for concatenation of single digits. This is most likely due to uncertainties in the location of the concatenated digits, which increases disproportionately with an increase in the number of digits in the string. / Master of Science

This thesis investigates the application of Hidden Markov Models (HMMs) to model financial volatility-regimes and presents a parameter learning approach using real-world data. Although HMMs as regime-switching models are established, empirical studies regarding the parameter estimation of such models remain limited. We address this issue by creating a systematic approach (algorithm) for parameter learning using Python programming and the hmmlearn library. The algorithm works by initializing a wide range of random parameter values for an HMM and maximizing the log-likelihood of an observation sequence, obtained from market data, using expectation-maximization; the optimal number of volatility regimes for the HMM is determined using information criterion. By training models on historical market and volatility index data, we found that a discrete model is favored for volatility modeling and option pricing due to its low complexity and high customizability, and a Gaussian model is favored for asset allocation and price simulation due to its ability to model market regimes. However, practical applications of these models were not researched, and thus, require further studies to test and calibrate.

Many real-world systems experience deterioration with usage and age, which often leads to low product quality, high production cost, and low system availability. Most previous maintenance and reliability models in the literature do not incorporate condition monitoring information for decision making, which often results in poor failure prediction for partially observable deteriorating systems. For that reason, the development of fault prediction and control scheme using condition-based maintenance techniques has received considerable attention in recent years. This research presents a new framework for predicting failures of a partially observable deteriorating system using Bayesian control techniques. A time series model is fitted to a vector observation process representing partial information about the system state. Residuals are then calculated using the fitted model, which are indicative of system deterioration. The deterioration process is modeled as a 3-state continuous-time homogeneous Markov process. States 0 and 1 are not observable, representing healthy (good) and unhealthy (warning) system operational conditions, respectively. Only the failure state 2 is assumed to be observable. Preventive maintenance can be carried out at any sampling epoch, and corrective maintenance is carried out upon system failure. The form of the optimal control policy that maximizes the long-run expected average availability per unit time has been investigated. It has been proved that a control limit policy is optimal for decision making. The model parameters have been estimated using the Expectation Maximization (EM) algorithm. The optimal Bayesian fault prediction and control scheme, considering long-run average availability maximization along with a practical statistical constraint, has been proposed and compared with the age-based replacement policy. The optimal control limit and sampling interval are calculated in the semi-Markov decision process (SMDP) framework. Another Bayesian fault prediction and control scheme has been developed based on the average run length (ARL) criterion. Comparisons with traditional control charts are provided. Formulae for the mean residual life and the distribution function of system residual life have been derived in explicit forms as functions of a posterior probability statistic. The advantage of the Bayesian model over the well-known 2-parameter Weibull model in system residual life prediction is shown. The methodologies are illustrated using simulated data, real data obtained from the spectrometric analysis of oil samples collected from transmission units of heavy hauler trucks in the mining industry, and vibration data from a planetary gearbox machinery application.

Many real-world systems experience deterioration with usage and age, which often leads to low product quality, high production cost, and low system availability. Most previous maintenance and reliability models in the literature do not incorporate condition monitoring information for decision making, which often results in poor failure prediction for partially observable deteriorating systems. For that reason, the development of fault prediction and control scheme using condition-based maintenance techniques has received considerable attention in recent years. This research presents a new framework for predicting failures of a partially observable deteriorating system using Bayesian control techniques. A time series model is fitted to a vector observation process representing partial information about the system state. Residuals are then calculated using the fitted model, which are indicative of system deterioration. The deterioration process is modeled as a 3-state continuous-time homogeneous Markov process. States 0 and 1 are not observable, representing healthy (good) and unhealthy (warning) system operational conditions, respectively. Only the failure state 2 is assumed to be observable. Preventive maintenance can be carried out at any sampling epoch, and corrective maintenance is carried out upon system failure. The form of the optimal control policy that maximizes the long-run expected average availability per unit time has been investigated. It has been proved that a control limit policy is optimal for decision making. The model parameters have been estimated using the Expectation Maximization (EM) algorithm. The optimal Bayesian fault prediction and control scheme, considering long-run average availability maximization along with a practical statistical constraint, has been proposed and compared with the age-based replacement policy. The optimal control limit and sampling interval are calculated in the semi-Markov decision process (SMDP) framework. Another Bayesian fault prediction and control scheme has been developed based on the average run length (ARL) criterion. Comparisons with traditional control charts are provided. Formulae for the mean residual life and the distribution function of system residual life have been derived in explicit forms as functions of a posterior probability statistic. The advantage of the Bayesian model over the well-known 2-parameter Weibull model in system residual life prediction is shown. The methodologies are illustrated using simulated data, real data obtained from the spectrometric analysis of oil samples collected from transmission units of heavy hauler trucks in the mining industry, and vibration data from a planetary gearbox machinery application.

No description available.

La maintenance prédictive joue un rôle important dans le maintien des systèmes de production continue car elle peut aider à réduire les interventions inutiles ainsi qu'à éviter des pannes imprévues. En effet, par rapport à la maintenance conditionnelle, la maintenance prédictive met en œuvre une étape supplémentaire, appelée le pronostic. Les opérations de maintenance sont planifiées sur la base de la prédiction des états de détérioration futurs et sur l'estimation de la vie résiduelle du système. Dans le cadre du projet européen FP7 SUPREME (Sustainable PREdictive Maintenance for manufacturing Equipment en Anglais), cette thèse se concentre sur le développement des modèles de détérioration stochastiques et sur des méthodes d'estimation de la vie résiduelle (Remaining Useful Life – RUL en anglais) associées pour les adapter aux cas d'application du projet. Plus précisément, les travaux présentés dans ce manuscrit sont divisés en deux parties principales. La première donne une étude détaillée des modèles de détérioration et des méthodes d'estimation de la RUL existant dans la littérature. En analysant leurs avantages et leurs inconvénients, une adaptation d’une approche de l'état de l'art est mise en œuvre sur des cas d'études issus du projet SUPREME et avec les données acquises à partir d’un banc d'essai développé pour le projet. Certains aspects pratiques de l’implémentation, à savoir la question de l'échange d'informations entre les partenaires du projet, sont également détaillées dans cette première partie. La deuxième partie est consacrée au développement de nouveaux modèles de détérioration et les méthodes d'estimation de la RUL qui permettent d'apporter des éléments de solutions aux problèmes de modélisation de détérioration et de prédiction de RUL soulevés dans le projet SUPREME. Plus précisément, pour surmonter le problème de la coexistence de plusieurs modes de détérioration, le concept des modèles « multi-branche » est proposé. Dans le cadre de cette thèse, deux catégories des modèles de type multi-branche sont présentées correspondant aux deux grands types de modélisation de l'état de santé des système, discret ou continu. Dans le cas discret, en se basant sur des modèles markoviens, deux modèles nommés Mb-HMM and Mb-HsMM (Multi-branch Hidden (semi-)Markov Model en anglais) sont présentés. Alors que dans le cas des états continus, les systèmes linéaires à sauts markoviens (JMLS) sont mis en œuvre. Pour chaque modèle, un cadre à deux phases est implémenté pour accomplir à la fois les tâches de diagnostic et de pronostic. A travers des simulations numériques, nous montrons que les modèles de type multi-branche peuvent donner des meilleures performances pour l'estimation de la RUL par rapport à celles obtenues par des modèles standards mais « mono-branche ». / Predictive maintenance plays a crucial role in maintaining continuous production systems since it can help to reduce unnecessary intervention actions and avoid unplanned breakdowns. Indeed, compared to the widely used condition-based maintenance (CBM), the predictive maintenance implements an additional prognostics stage. The maintenance actions are then planned based on the prediction of future deterioration states and residual life of the system. In the framework of the European FP7 project SUPREME (Sustainable PREdictive Maintenance for manufacturing Equipment), this thesis concentrates on the development of stochastic deterioration models and the associated remaining useful life (RUL) estimation methods in order to be adapted in the project application cases. Specifically, the thesis research work is divided in two main parts. The first one gives a comprehensive review of the deterioration models and RUL estimation methods existing in the literature. By analyzing their advantages and disadvantages, an adaption of the state of the art approaches is then implemented for the problem considered in the SUPREME project and for the data acquired from a project's test bench. Some practical implementation aspects, such as the issue of delivering the proper RUL information to the maintenance decision module are also detailed in this part. The second part is dedicated to the development of innovative contributions beyond the state-of-the-are in order to develop enhanced deterioration models and RUL estimation methods to solve original prognostics issues raised in the SUPREME project. Specifically, to overcome the co-existence problem of several deterioration modes, the concept of the "multi-branch" models is introduced. It refers to the deterioration models consisting of different branches in which each one represent a deterioration mode. In the framework of this thesis, two multi-branch model types are presented corresponding to the discrete and continuous cases of the systems' health state. In the discrete case, the so-called Multi-branch Hidden Markov Model (Mb-HMM) and the Multi-branch Hidden semi-Markov model (Mb-HsMM) are constructed based on the Markov and semi-Markov models. Concerning the continuous health state case, the Jump Markov Linear System (JMLS) is implemented. For each model, a two-phase framework is carried out for both the diagnostics and prognostics purposes. Through numerical simulations and a case study, we show that the multi-branch models can help to take into account the co-existence problem of multiple deterioration modes, and hence give better performances in RUL estimation compared to the ones obtained by standard "single branch" models.

Depuis leur création, les codes graphiques constituent un outil d'identification automatique largement exploité en industrie. Cependant, les performances de lecture sont limitées par un flou optique et un flou de mouvement. L'objectif de la thèse est l'optimisation de lecture des codes 1D et 2D en exploitant des modèles de Markov cachés simples et doubles, et des méthodes d'estimation aveugles. En premier lieu, le système de lecture de codes graphiques est modélisé par une chaîne de Markov cachée, et des nouveaux algorithmes pour l'estimation du canal et la détection des symboles sont développés. Ils tiennent compte de la non stationnarité de la chaîne de Markov. De plus une méthode d'estimation de la taille du flou et de sa forme est proposée. La méthode utilise des critères de sélection permettant de choisir le modèle de dégradation le plus adéquat. Enfin nous traitons le problème de complexité qui est particulièrement important dans le cas d'un canal à mémoire longue. La solution proposée consiste à modéliser le canal à mémoire longue par une chaîne de Markov double. Sur la base de ce modèle, des algorithmes offrant un rapport optimisé performance-complexité sont présentés / Since its birth, the technology of barcode is well investigated for automatic identification. When reading, a barcode can be degraded by a blur , caused by a bad focalisation and/ or a camera movement. The goal of this thesis is the optimisation of the receiver of 1D and 2D barcode from hidden and double Markov model and blind statistical estimation approaches. The first phase of our work consists of modelling the original image and the observed one using Hidden Markov model. Then, new algorithms for joint blur estimation and symbol detection are proposed, which take into account the non-stationarity of the hidden Markov process. Moreover, a method to select the most relevant model of the blur is proposed, based on model selection criterion. The method is also used to estimate the blur length. Finally, a new algorithm based on the double Markov chain is proposed to deal with digital communication through a long memory channel. Estimation of such channel is not possible using the classical detection algorithms based on the maximum likelihood due to the prohibitive complexity. New algorithm giving good trade off between complexity and performance is provided

This thesis explored the possibilities of using a Hidden Markov Model approach for multi-target localisation in an urban environment, with observations generated from Wi-Fi sensors. The area is modelled as a network of nodes and arcs, where the arcs represent sidewalks in the area and constitutes the hidden states in the model. The output of the model is the expected amount of people at each road segment throughout the day. In addition to this, two methods for analyzing the impact of events in the area are proposed. The first method is based on a time series analysis, and the second one is based on the updated transition matrix using the Baum-Welch algorithm. Both methods reveal which road segments are most heavily affected by a surge of traffic in the area, as well as potential bottleneck areas where congestion is likely to have occurred. / I det här examensarbetet har lokalisering av gångtrafikanter med hjälp av Hidden Markov Models utförts. Lokaliseringen är byggd på data från Wi-Fi sensorer i ett område i Stockholm. Området är modellerat som ett graf-baserat nätverk där linjerna mellan noderna representerar möjliga vägar för en person att befinna sig på. Resultatet för varje individ är aggregerat för att visa förväntat antal personer på varje segment över en hel dag. Två metoder för att analysera hur event påverkar området introduceras och beskrivs. Den första är baserad på tidsserieanalys och den andra är en maskinlärningsmetod som bygger på Baum-Welch algoritmen. Båda metoderna visar vilka segment som drabbas mest av en snabb ökning av trafik i området och var trängsel är troligt att förekomma.

Thesis (MSc)--Stellenbosch University, 2011. / ENGLISH ABSTRACT: An off-line signature verification system attempts to authenticate the identity of an individual by examining his/her handwritten signature, after it has been successfully extracted from, for example, a cheque, a debit or credit card transaction slip, or any other legal document. The questioned signature is typically compared to a model trained from known positive samples, after which the system attempts to label said signature as genuine or fraudulent. Classifier fusion is the process of combining individual classifiers, in order to construct a single classifier that is more accurate, albeit computationally more complex, than its constituent parts. A combined classifier therefore consists of an ensemble of base classifiers that are combined using a specific fusion strategy. In this dissertation a novel off-line signature verification system, using a multi-hypothesis approach and classifier fusion, is proposed. Each base classifier is constructed from a hidden Markov model (HMM) that is trained from features extracted from local regions of the signature (local features), as well as from the signature as a whole (global features). To achieve this, each signature is zoned into a number of overlapping circular retinas, from which said features are extracted by implementing the discrete Radon transform. A global retina, that encompasses the entire signature, is also considered. Since the proposed system attempts to detect high-quality (skilled) forgeries, it is unreasonable to assume that samples of these forgeries will be available for each new writer (client) enrolled into the system. The system is therefore constrained in the sense that only positive training samples, obtained from each writer during enrolment, are available. It is however reasonable to assume that both positive and negative samples are available for a representative subset of so-called guinea-pig writers (for example, bank employees). These signatures constitute a convenient optimisation set that is used to select the most proficient ensemble. A signature, that is claimed to belong to a legitimate client (member of the general public), is therefore rejected or accepted based on the majority vote decision of the base classifiers within the most proficient ensemble. When evaluated on a data set containing high-quality imitations, the inclusion of local features, together with classifier combination, significantly increases system performance. An equal error rate of 8.6% is achieved, which compares favorably to an achieved equal error rate of 12.9% (an improvement of 33.3%) when only global features are considered. Since there is no standard international off-line signature verification data set available, most systems proposed in the literature are evaluated on data sets that differ from the one employed in this dissertation. A direct comparison of results is therefore not possible. However, since the proposed system utilises significantly different features and/or modelling techniques than those employed in the above-mentioned systems, it is very likely that a superior combined system can be obtained by combining the proposed system with any of the aforementioned systems. Furthermore, when evaluated on the same data set, the proposed system is shown to be significantly superior to three other systems recently proposed in the literature. / AFRIKAANSE OPSOMMING: Die doel van ’n statiese handtekening-verifikasiestelsel is om die identiteit van ’n individu te bekragtig deur sy/haar handgeskrewe handtekening te analiseer, nadat dit suksesvol vanaf byvoorbeeld ’n tjek,’n debiet- of kredietkaattransaksiestrokie, of enige ander wettige dokument onttrek is. Die bevraagtekende handtekening word tipies vergelyk met ’n model wat afgerig is met bekende positiewe voorbeelde, waarna die stelsel poog om die handtekening as eg of vervals te klassifiseer. Klassifiseerder-fusie is die proses waardeer individuele klassifiseerders gekombineer word, ten einde ’n enkele klassifiseerder te konstrueer, wat meer akkuraat, maar meer berekeningsintensief as sy samestellende dele is. ’n Gekombineerde klassifiseerder bestaan derhalwe uit ’n ensemble van basis-klassifiseerders, wat gekombineer word met behulp van ’n spesifieke fusie-strategie. In hierdie projek word ’n nuwe statiese handtekening-verifikasiestelsel, wat van ’n multi-hipotese benadering en klassifiseerder-fusie gebruik maak, voorgestel. Elke basis-klassifiseerder word vanuit ’n verskuilde Markov-model (HMM) gekonstrueer, wat afgerig word met kenmerke wat vanuit lokale gebiede in die handtekening (lokale kenmerke), sowel as vanuit die handtekening in geheel (globale kenmerke), onttrek is. Ten einde dit te bewerkstellig, word elke handtekening in ’n aantal oorvleulende sirkulêre retinas gesoneer, waaruit kenmerke onttrek word deur die diskrete Radon-transform te implementeer. ’n Globale retina, wat die hele handtekening in beslag neem, word ook beskou. Aangesien die voorgestelde stelsel poog om hoë-kwaliteit vervalsings op te spoor, is dit onredelik om te verwag dat voorbeelde van hierdie handtekeninge beskikbaar sal wees vir elke nuwe skrywer (kliënt) wat vir die stelsel registreer. Die stelsel is derhalwe beperk in die sin dat slegs positiewe afrigvoorbeelde, wat bekom is van elke skrywer tydens registrasie, beskikbaar is. Dit is egter redelik om aan te neem dat beide positiewe en negatiewe voorbeelde beskikbaar sal wees vir ’n verteenwoordigende subversameling van sogenaamde proefkonynskrywers, byvoorbeeld bankpersoneel. Hierdie handtekeninge verteenwoordig ’n gereieflike optimeringstel, wat gebruik kan word om die mees bekwame ensemble te selekteer. ’n Handtekening, wat na bewering aan ’n wettige kliënt (lid van die algemene publiek) behoort, word dus verwerp of aanvaar op grond van die meerderheidstem-besluit van die basis-klassifiseerders in die mees bekwame ensemble. Wanneer die voorgestelde stelsel op ’n datastel, wat hoë-kwaliteit vervalsings bevat, ge-evalueer word, verhoog die insluiting van lokale kenmerke en klassifiseerder-fusie die prestasie van die stelsel beduidend. ’n Gelyke foutkoers van 8.6% word behaal, wat gunstig vergelyk met ’n gelyke foutkoers van 12.9% (’n verbetering van 33.3%) wanneer slegs globale kenmerke gebruik word. Aangesien daar geen standard internasionale statiese handtekening-verifikasiestelsel bestaan nie, word die meeste stelsels, wat in die literatuur voorgestel word, op ander datastelle ge-evalueer as die datastel wat in dié projek gebruik word. ’n Direkte vergelyking van resultate is dus nie moontlik nie. Desnieteenstaande, aangesien die voorgestelde stelsel beduidend ander kenmerke en/of modeleringstegnieke as dié wat in bogenoemde stelsels ingespan word gebruik, is dit hoogs waarskynlik dat ’n superieure gekombineerde stelsel verkry kan word deur die voorgestelde stelsel met enige van bogenoemde stelsels te kombineer. Voorts word aangetoon dat, wanneer op dieselfde datastel geevalueerword, die voorgestelde stelstel beduidend beter vaar as drie ander stelsels wat onlangs in die literatuur voorgestel is.

Thesis (PhD (Electrical and Electronic Engineering))--University of Stellenbosch, 2007. / Most speech recognition and language identification engines are based on hidden Markov models (HMMs). Higher-order HMMs are known to be more powerful than first-order HMMs, but have not been widely used because of their complexity and computational demands. The main objective of this dissertation was to develop a more time-efficient method of decoding high-order HMMs than the standard Viterbi decoding algorithm currently in use. We proposed, implemented and evaluated two decoders based on the Forward-Backward Search (FBS) paradigm, which incorporate information obtained from low-order HMMs. The first decoder is based on time-synchronous Viterbi-beam decoding where we wish to base our state pruning on the complete observation sequence. The second decoder is based on time-asynchronous A* search. The choice of heuristic is critical to the A* search algorithms and a novel, task-independent heuristic function is presented. The experimental results show that both these proposed decoders result in more time-efficient decoding of the fully-connected, high-order HMMs that were investigated. Three significant facts have been uncovered. The first is that conventional forward Viterbi-beam decoding of high-order HMMs is not as computationally expensive as is commonly thought. The second (and somewhat surprising) fact is that backward decoding of conventional, high-order left-context HMMs is significantly more expensive than the conventional forward decoding. By developing the right-context HMM, we showed that the backward decoding of a mathematically equivalent right-context HMM is as expensive as the forward decoding of the left-context HMM. The third fact is that the use of information obtained from low-order HMMs significantly reduces the computational expense of decoding high-order HMMs. The comparison of the two new decoders indicate that the FBS-Viterbi-beam decoder is more time-efficient than the A* decoder. The FBS-Viterbi-beam decoder is not only simpler to implement, it also requires less memory than the A* decoder. We suspect that the broader research community regards the Viterbi-beam algorithm as the most efficient method of decoding HMMs. We hope that the research presented in this dissertation will result in renewed investigation into decoding algorithms that are applicable to high-order HMMs.