Zero knowledge hidden Markov model inference

Hidden Markov models (HMMs) are widely used in pattern recognition. HMM construction requires an initial model structure that is used as a starting point to estimate the model’s parameters. To construct a HMM without a priori knowledge of the structure, we use an approach developed by Crutchfield and Shalizi that requires only a sequence of observations and a maximum data window size. Values of the maximum data window size that are too small result in incorrect models being constructed. Values that are too large reduce the number of data samples that can be considered and exponentially increase the algorithm’s computational complexity. In this paper, we present a method for automatically inferring this parameter directly from training data as part of the model construction process. We present theoretical and experimental results that confirm the utility of the proposed extension.     

A modified hidden Markov model

This paper considers two discrete time, finite state processes X$X$ and Y$Y$. In the usual hidden Markov model X$X$ modulates the values of Y$Y$. However, the values of Y$Y$ are then i.i.d. given X$X$. In this paper a new model is considered where the Markov chain X$X$ modulates the transition probabilities of the second, observed chain Y$Y$. This more realistically can represent problems arising in DNA sequencing. Algorithms for all related filters, smoothers and parameter estimations are derived. Versions of the Viterbi algorithms are obtained.     

Storage workload modelling by hidden Markov models: Application to Flash memory

A workload analysis technique is presented that processes data from operation type traces and creates a hidden Markov model (HMM) to represent the workload that generated those traces. The HMM can be used to create representative traces for performance models, such as simulators, avoiding the need to repeatedly acquire suitable traces. It can also be used to estimate the transition probabilities and rates of a Markov modulated arrival process directly, for use as input to an analytical performance model of Flash memory. The HMMs obtained from industrial workloads-both synthetic benchmarks, preprocessed by a file translation layer, and real, time-stamped user traces-are validated by comparing their autocorrelation functions and other statistics with those of the corresponding monitored time series. Further, the performance model applications, referred to above, are illustrated by numerical examples.     

Efficient backward decoding of high-order hidden Markov models

The forward-backward search (FBS) algorithm [S. Austin, R. Schwartz, P. Placeway, The forward-backward search algorithm, in: Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing, 1991, pp. 697-700] has resulted in increases in speed of up to 40 in expensive time-synchronous beam searches in hidden Markov model (HMM) based speech recognition [R. Schwartz, S. Austin, Efficient, high-performance algorithms for N-best search, in: Proceedings of the Workshop on Speech and Natural Language, 1990, pp. 6-11; L. Nguyen, R. Schwartz, F. Kubala, P. Placeway, Search algorithms for software-only real-time recognition with very large vocabularies, in: Proceedings of the Workshop on Human Language Technology, 1993, pp. 91-95; A. Sixtus, S. Ortmanns, High-quality word graphs using forward-backward pruning, in: Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing, 1999, pp. 593-596]. This is typically achieved by using a simplified forward search to decrease computation in the following detailed backward search. FBS implicitly assumes that forward and backward searches of HMMs are computationally equivalent. In this paper we present experimental results, obtained on the CallFriend database, that show that this assumption is incorrect for conventional high-order HMMs. Therefore, any improvement in computational efficiency that is gained by using conventional low-order HMMs in the simplified backward search of FBS is lost.This problem is solved by presenting a new definition of HMMs termed a right-context HMM, which is equivalent to conventional HMMs. We show that the computational expense of backward Viterbi-beam decoding right-context HMMs is similar to that of forward decoding conventional HMMs. Though not the subject of this paper, this allows us to more efficiently decode high-order HMMs, by capitalising on the improvements in computational efficiency that is obtained by using the FBS algorithm.     

A combination of hidden Markov model and fuzzy model for stock market forecasting

This paper presents a novel combination of the hidden Markov model (HMM) and the fuzzy models for forecasting stock market data. In a previous study we used an HMM to identify similar data patterns from the historical data and then used a weighted average to generate a ‘one-day-ahead’ forecast. This paper uses a similar approach to identify data patterns by using the HMM and then uses fuzzy logic to obtain a forecast value. The HMM's log-likelihood for each of the input data vectors is used to partition the dataspace. Each of the divided dataspaces is then used to generate a fuzzy rule. The fuzzy model developed from this approach is tested on stock market data drawn from different sectors. Experimental results clearly show an improved forecasting accuracy compared to other forecasting models such as, ARIMA, artificial neural network (ANN) and another HMM-based forecasting model.     

A trigram hidden Markov model for metadata extraction from heterogeneous references

Our objective was to explore an efficient and accurate extraction of metadata such as author, title and institution from heterogeneous references, using hidden Markov models (HMMs). The major contributions of the research were the (i) development of a trigram, full second order hidden Markov model with more priority to words emitted in transitions to the same state, with a corresponding new Viterbi algorithm (ii) introduction of a new smoothing technique for transition probabilities and (iii) proposal of a modification of back-off shrinkage technique for emission probabilities. The effect of the size of data set on the training procedure was also measured. Comparisons were made with other related works and the model was evaluated with three different data sets. The results showed overall accuracy, precision, recall and F1 measure of over 95% suggesting that the method outperforms other related methods in the task of metadata extraction from references.     

脱机手写体签名识别的小波包隐马尔可夫模型

提出了一种基于小波包隐马尔可夫的脱机手写体签名识别方法。该方法用小波包对归一化的签名图像进行特征提取,用混合高斯模型刻画各频带的小波包的系数分布,并用隐马尔可夫的状态转移模型描述了高斯模型在各频带间的相关性和依赖性。该方法数据预处理简单,特征提取完全可逆,避免了复杂分割,很好地描述了签名图像的小波包分解的统计特性,实验表明具有较好的抗噪性、鲁棒性、适应性和较高的识别率。     

On-line recognition of Korean characters using ART neural network and hidden Markov model

This paper proposes an efficient method for on-line recognition of cursive Korean characters. The recognition of cursive strokes and the representation of a large character set are important determinants in the recognition rate of Korean characters. To deal with cursive strokes, we classify them automatically by using an ART-2 neural network. This neural network has the advantage of assembling similar patterns together to form classes in a self-organized manner. To deal with the large character set, we construct a character recognition model by using the hidden Markov model (HMM), which has the advantages of providing an explicit representation of time-varying vector sequence and probabilistic interpretation. Probabilistic parameters of the HMM are initialized using the combination rule for Korean characters and a set of primitive strokes that are classified by the ART stroke classifier, and trained with sample data. This is an efficient means of representing all the 11,172 possible Korean characters. We tested the model on 7500 on-line cursive Korean characters and it proved to perform well in recognition rate and speed.     

基于模糊滑窗隐马尔可夫模型的入侵检测研究

针对传统基于隐马尔可夫模型（HMM）入侵检测中普遍存在误报与漏报过高的问题,提出了一种基于模糊窗口隐马尔可夫模型（FWHMM）的入侵检测新方法。该方法通过运用状态转移依赖滑窗的设置提高了系统的检测精度,通过将状态的随机转移转变为模糊随机转移,提高了系统的鲁棒性和自适应性。实验结果表明,使用本文方法的检测效果要明显优于基于经典HMM的方法。     

Increasing mapping based hidden Markov model for dynamic process monitoring and diagnosis

Hidden Markov models (HMMs) perform parameter estimation based on the forward–backward (FB) procedure and the Baum–Welch (BW) algorithm. The two algorithms together may increase the computational complexity and the difficulty to understand the algorithm structure of HMMs clearly. In this study, an increasing mapping based hidden Markov model (IMHMM) is proposed. Between the observation sequence and possible state sequence an increasing mapping is established. The re-estimation formulas for the model parameters are derived straightforwardly based on these mappings instead of FB variables. The IMHMM has simpler algorithm structure and lower storage requirement than the HMM. Based on IMHMM, an expandable process monitoring and fault diagnosis framework for large-scale dynamical process is developed. To characterize the dynamic process, a novel index considering serial correlation is used to evaluate process state. The presented methodology is carried out in Tennessee Eastman process (TEP). The results show improvement over HMM in terms of memory complexity and training time of the model. Also, the power of IMHMM can be observed compared with principal component analysis (PCA) based methods.