Many common statistical techniques for modeling multidimensional dynamic data sets can be seen as variants of one (or multiple) underlying linear/nonlinear model(s). These statistical techniques fall into two broad categories of supervised and unsupervised learning. The emphasis of this dissertation is on unsupervised learning under multiple generative models. For linear models, this has been achieved by collective observations and derivations made by previous authors during the last few decades. Factor analysis, polynomial chaos expansion, principal component analysis, gaussian mixture clustering, vector quantization, and Kalman filter models can all be unified as some variations of unsupervised learning under a single basic linear generative model. Hidden Markov modeling (HMM), however, is categorized as an unsupervised learning under multiple linear/nonlinear generative models. This dissertation is primarily focused on hidden Markov models (HMMs). On the first half of this dissertation we study enhancements on the theory of hidden Markov modeling. These include three branches: 1) a robust as well as a closed-form parameter estimation solution to the expectation maximization (EM) process of HMMs for the case of elliptically symmetrical densities; 2) a two-step HMM, with a combined state sequence via an extended Viterbi algorithm for smoother state estimation; and 3) a duration-dependent HMM, for estimating the expected residency frequency on each state. Then, the second half of the dissertation studies three novel applications of these methods: 1) the applications of Markov switching models on the Bifurcation Theory in nonlinear dynamics; 2) a Game Theory application of HMM, based on fundamental theory of card counting and an example on the game of Baccarat; and 3) Trust modeling and the estimation of trustworthiness metrics in cyber security systems via Markov switching models. As a result of the duration dependent HMM, we achieved a better estimation for the expected duration of stay on each regime. Then by robust and closed form solution to the EM algorithm we achieved robustness against outliers in the training data set as well as higher computational efficiency in the maximization step of the EM algorithm. By means of the two-step HMM we achieved smoother probability estimation with higher likelihood than the standard HMM. / Ph. D.

Wireless has proved to be one of the most important and fastest growing fields of communications especially during last few decades. To achieve reliable communication, we model a wireless system to analyze its performance and to find ways to improve the reliability of a particular system. Extensive research is being done to accurately model wireless systems, and to achieve better performance. Simulation techniques have been in use for many years to support the design and evaluation of electronic communication systems. Over the past few decades, Computer Aided Design (CAD) techniques (including both computerized analytical techniques and simulation) have matured, and are now usually applied at some point in the system design/development process. The aim of this thesis is to find efficient algorithms that can model third generation wireless channels in a discrete sense. For modeling these channels, mathematical tools known as hidden Markov models are used. These models have proved themselves to be very efficient in many areas of electrical engineering including speech recognition, pattern recognition, artificial intelligence, wavelets and queuing theory. Wideband Code Division Multiple Access (W-CDMA) wireless communication parameters including channels fading statistics, Bit Error Rate (BER) performance and interval distribution of errors are modeled using different Markov models, and their results are tested and validated. Four algorithms for modeling error sources are implemented, and their results are discussed. Both hidden Markov models and semi-hidden Markov models are used in this thesis, and their results are validated for the W-CDMA environment. The state duration distributions for these channels are also approximated using Phase-Type (PH) distribution. / Master of Science

Methods to detect patterns of variation associated with ongoing positive selection often focus on identifying regions of the genome with extended haplotype homozygosity - indicative of recently shared ancestry. Whilst these have been shown to be powerful they have two major challenges. First, these methods are constructed to detect variation associated with a classical selective sweep; a single haplotype background gets swept up to a higher than expected frequency given its age. Recently studies have shown that other forms of positive selection, e.g. selection on standing variation, may be more prevalent than previous thought. Under such evolution, a mutation that is already segregating in the population becomes beneficial, possibly as a result of an environmental change. The second challenge with these methods is that they base their inference on non-parametric tests of significance which can result in uncontrolled false positive rates. We tackle these problems using two approaches. First, by exploiting a widely used model in population genomics we construct a new approach to detect regions where a subset of the chromosomes are much more related than expected genome-wide. Using this metric we show that it is sensitive to both classical selective sweeps, and to soft selective sweeps, e.g. selection on standing variation. Second, building on existing methods, we construct a Bayesian test which bi-partitions chromosomes at every position based on their allelic type and tests for association between chromosomes carrying one allele and significantly reduced time to common ancestor. Using simulated data we show that this approach results in a powerful, fast, and robust approach to detect signals of positive selection in sequence data. Moreover by comparing our model to existing techniques we show that we have similar power to detect recent classical selective sweeps, and considerably greater power to detect soft selective sweeps. We apply our method, ABACUS, to three human populations using data from the 1000 Genome Project. Using existing and novel candidates of positive selection, we show that the results between ABACUS and existing methods are comparable in regions of classical selection, and are arguably superior in regions that show evidence for recent selection on standing variation.

Much research in recent years for evidence evaluation in forensic science has focussed on methods for determining the likelihood ratio in various scenarios. One proposition concerning the evidence is put forward by the prosecution and another is put forward by the defence. The likelihood of each of these two propositions is calculated, given the evidence. The likelihood ratio, or value of the evidence, is then given by the ratio of the likelihoods associated with these two propositions. The aim of this research is twofold. Firstly, it is intended to provide methodology for the evaluation of the likelihood ratio for continuous autocorrelated data. The likelihood ratio is evaluated for two such scenarios. The first is when the evidence consists of data which are autocorrelated at lag one. The second, an extension to this, is when the observed evidential data are also believed to be driven by an underlying latent Markov chain. Two models have been developed to take these attributes into account, an autoregressive model of order one and a hidden Markov model, which does not assume independence of adjacent data points conditional on the hidden states. A nonparametric model which does not make a parametric assumption about the data and which accounts for lag one autocorrelation is also developed. The performance of these three models is compared to the performance of a model which assumes independence of the data. The second aim of the research is to develop models to evaluate evidence relating to traces of cocaine on banknotes, as measured by the log peak area of the ion count for cocaine product ion m/z 105, obtained using tandem mass spectrometry. Here, the prosecution proposition is that the banknotes are associated with a person who is involved with criminal activity relating to cocaine and the defence proposition is the converse, which is that the banknotes are associated with a person who is not involved with criminal activity relating to cocaine. Two data sets are available, one of banknotes seized in criminal investigations and associated with crime involving cocaine, and one of banknotes from general circulation. Previous methods for the evaluation of this evidence were concerned with the percentage of banknotes contaminated or assumed independence of measurements of quantities of cocaine on adjacent banknotes. It is known that nearly all banknotes have traces of cocaine on them and it was found that there was autocorrelation within samples of banknotes so thesemethods are not appropriate. The models developed for autocorrelated data are applied to evidence relating to traces of cocaine on banknotes; the results obtained for each of the models are compared using rates of misleading evidence, Tippett plots and scatter plots. It is found that the hiddenMarkov model is the best choice for themodelling of cocaine traces on banknotes because it has the lowest rate of misleading evidence and it also results in likelihood ratios which are large enough to give support to the prosecution proposition for some samples of banknotes seized from crime scenes. Comparison of the results obtained for models which take autocorrelation into account with the results obtained from the model which assumes independence indicate that not accounting for autocorrelation can result in the overstating of the likelihood ratio.

The aim of the project presented in this paper was to investigate the possibility toautomatically sub-classify the superfamily of Short-chain Dehydrogenase/Reductases (SDR).This was done based on an algorithm previously designed to sub-classify the superfamily ofMedium-chain Dehydrogenase/Reductases (MDR). While the SDR-family is interesting andimportant to sub-classify there was also a focus on making the process as automatic aspossible so that future families also can be classified using the same methods.To validate the results generated it was compared to previous sub-classifications done on theSDR-family. The results proved promising and the work conducted here can be seen as a goodinitial part of a more comprehensive full investigation

Thesis (MSc)--Stellenbosch University, 2015 / ENGLISH ABSTRACT: Steganography is the art of hiding information inside a data host called the cover. The amount of distortion caused by that embedding can influence the security of the steganographic system. By secrecy we mean the detectability of the existence of the secret in the cover, by parties other than the sender and the intended recipient. Crandall (1998) proposed that coding theory (in particular the notion of covering radius) might be used to minimize embedding distortion in steganography. This thesis provides a study of that suggestion. Firstly a method of constructing a steganographic schemes with small embedding radius is proposed by using a partition of the set of all covers into subsets indexed by the set of embeddable secrets, where embedding a secret s is a maximum likelihood decoding problem on the subset indexed by s. This converts the problem of finding a stego-scheme with small embedding radius to a coding theoretic problem. Bounds are given on the maximum amount of information that can be embedded. That raises the question of the relationship between perfect codes and perfect steganographic schemes. We define a translation from perfect linear codes to steganographic schemes; the latter belong to the family of matrix embedding schemes, which arise from random linear codes. Finally, the capacity of a steganographic scheme with embedding constraint is investigated, as is the embedding efficiency to evaluate the performance of steganographic schemes. / AFRIKAANSE OPSOMMING: Steganografie is die kuns van die wegsteek van geheime inligting in 'n data gasheer genoem die dekking. Die hoeveelheid distorsie veroorsaak deur die inbedding kan die veiligheid van die steganografiese stelsel beïnvloed. Deur geheimhouding bedoel ons die opspoorbaarheid van die bestaan van die geheim in die dekking, deur ander as die sender en die bedoelde ontvanger partye. Crandall (1998) het voorgestel dat kodeerteorie (in besonder die idee van dekking radius) kan gebruik word om inbedding distorsie te verminder in steganografie. Hierdie tesis bied 'n studie van daardie voorstel. Eerstens 'n metode van die bou van 'n steganografiese skema met 'n klein inbedding radius word voorgestel deur die gebruik van 'n partisie van die versameling van alle dekkings in deelversamelings geïndekseer deur die versameling van inbedbare geheime, waar inbedding 'n geheime s is 'n maksimum waarskynlikheid dekodering probleem op die deelversameling geïndekseer deur s. Dit vat die probleem van die vind van 'n stego-skema met klein inbedding radius na 'n kodering teoretiese probleem. Grense word gegee op die maksimum hoeveelheid inligting wat ingebed kan word. Dit bring op die vraag van die verhouding tussen perfekte kodes en perfekte steganographic skemas. Ons definieer 'n vertaling van perfekte lineêre kodes na steganographic skemas; laasgenoemde behoort aan die familie van matriks inbedding skemas, wat ontstaan as gevolg van ewekansige lineêre kodes. Laasten, die kapasiteit van 'n steganografiese skema met inbedding beperking word ondersoek, asook die inbedding doeltreffendheid om die prestasie van steganografiese skemas te evalueer.

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.

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 / iNet is a project aimed at improving and modernizing telemetry systems by moving from a link to a networking solution. Changes introduce new risks and vulnerabilities. The nature of the security of the telemetry system changes when the elements are in an Ethernet and TCP/IP network configuration. The network will require protection from intrusion and malware that can be initiated internal to, or external of the network boundary. In this paper we will discuss how to detect and counter FTP password attacks using the Hidden Markov Model for intrusion detection. We intend to discover and expose the more subtle iNet network vulnerabilities and make recommendations for a more secure telemetry environment.

For many sequence prediction tasks in Natural Language Processing, modeling dependencies between individual predictions can be used to improve prediction accuracy of the sequence as a whole. Supertagging, involves assigning lexical entries to words based on lexicalized grammatical theory such as Combinatory Categorial Grammar (CCG). Previous work has used Bayesian HMMs to learn taggers for both POS tagging and supertagging separately. Modeling them jointly has the potential to produce more robust and accurate supertaggers trained with less supervision and thereby potentially help in the creation of useful models for new languages and domains. Factorial Hidden Markov Models (FHMM) support joint inference for multiple sequence prediction tasks. Here, I use them to jointly predict part-of-speech tag and supertag sequences with varying levels of supervision. I show that supervised training of FHMM models improves performance compared to standard HMMs, especially when labeled training material is scarce. Secondly, FHMMs trained from tag dictionaries rather than labeled examples also perform better than a standard HMM. Finally, I show that an FHMM and a maximum entropy Markov model can complement each other in a single step co-training setup that improves the performance of both models when there is limited labeled training material available. / text

A Profile Hidden Markov Model (HMM) is a statistical model for representing a multiple sequence alignment (MSA). Profile HMMs are important tools for sequence homology detection and have been used in wide a range of bioinformatics applications including protein structure prediction, remote homology detection, and sequence alignment. Profile HMM methods result in accurate alignments on datasets with evolutionarily similar sequences; however, I will show that on datasets with evolutionarily divergent sequences, the accuracy of HMM-based methods degrade. My dissertation presents a new statistical model for representing an MSA by using a set of HMMs. The family of HMM (fHMM) approach uses multiple HMMs instead of a single HMM to represent an MSA. I present a new algorithm for sequence alignment using the fHMM technique. I show that using the fHMM technique for sequence alignment results in more accurate alignments than the single HMM approach. As sequence alignment is a fundamental step in many bioinformatics pipelines, improvements to sequence alignment result in improvements across many different fields. I show the applicability of fHMM to three specific problems: phylogenetic placement, taxonomic profiling and identification, and MSA estimation. In phylogenetic placement, the problem addressed is how to insert a query sequence into an existing tree. In taxonomic identification and profiling, the problems addressed are how to taxonomically classify a query sequence, and how to estimate a taxonomic profile on a set of sequences. Finally, both profile HMM and fHMM require a backbone MSA as input in order to align the query sequences. In MSA estimation, the problem addressed is how to estimate a ``de novo'' MSA without the use of an existing backbone alignment. For each problem, I present a software pipeline that implements the fHMM specifically for that domain: SEPP for phylogenetic placement, TIPP for taxonomic profiling and identification, and UPP for MSA estimation. I show that SEPP has improved accuracy compared to the single HMM approach. I also show that SEPP results in more accurate phylogenetic placements compared to existing placement methods, and SEPP is more computationally efficient, both in peak memory usage and running time. I show that TIPP more accurately classifies novel sequences compared to the single HMM approach, and TIPP estimates more accurate taxonomic profiles than leading methods on simulated metagenomic datasets. I show how UPP can estimate ``de novo'' alignments using fHMM. I present results that show UPP is more accurate and efficient than existing alignment methods, and estimates accurate alignments and trees on datasets containing both full-length and fragmentary sequences. Finally, I show that UPP can estimate a very accurate alignment on a dataset with 1,000,000 sequences in less than 2 days without the need of a supercomputer. / Computer Sciences / text