Sequential data modeling and analysis have become indispensable tools for analyzing sequential data, such as time-series data, because larger amounts of sensed event data have become available. These methods capture the sequential structure of data of interest, such as input-output relations and correlation among datasets. However, because most studies in this area are specialized or limited to their respective applications, rigorous requirement analysis of such models has not been undertaken from a general perspective. Therefore, we particularly examine the structure of sequential data, and extract the necessity of “state duration” and “state interval” of events for efficient and rich representation of sequential data. Specifically addressing the hidden semi-Markov model (HSMM) that represents such state duration inside a model, we attempt to add representational capability of a state interval of events onto HSMM. To this end, we propose two extended models: an interval state hidden semi-Markov model (IS-HSMM) to express the length of a state interval with a special state node designated as “interval state node”; and an interval length probability hidden semi-Markov model (ILP-HSMM) which represents the length of the state interval with a new probabilistic parameter “interval length probability.” Exhaustive simulations have revealed superior performance of the proposed models in comparison with HSMM. These proposed models are the first reported extensions of HMM to support state interval representation as well as state duration representation.
@cite_7: A procedure for modeling duration with some PDF (probability density function) or PMF (probability mass function) in the exponential family is presented. A means of selecting an appropriate member of the exponential family is suggested. The parameter estimation procedure presented here offers several advantages over other methods of duration modeling. First, the duration PMF can be found directly, rather than sampling and truncating the optimum density. Secondly, the optimum duration parameters are found from Ferguson's nonparametric PMF. This simplifies reestimation because the operation of casting a nonparametric PMF to the desired parametric family can be completely separated from the forward and backward algorithms. Thirdly, several competing members of the exponential family can be evaluated quickly for each state in the HMM. This makes it possible to model each state's duration with the best member from a set of parametric PMFs in the exponential family. Finally, the solution holds for an PDF or PMF in the exponential family, which includes a large number of promising candidates. >
@cite_9: Prior arts in handwritten word recognition model either discrete features or continuous features, but not both. This paper combines discrete symbols and continuous attributes into structural handwriting features and model, them by transition-emitting and state-emitting hidden Markov models. The models are rigorously defined and experiments have proven their effectiveness.
@cite_29: Existing algorithms for estimating the model parameters of an explicit-duration hidden Markov model (HMM) usually require computations as large as O((MD sup 2 + M sup 2 )T) or O(M sup 2 DT), where M is the number of states; D is the maximum possible interval between state transitions; and T is the period of observations used to estimate the model parameters. Because of such computational requirements, these algorithms are not practical when we wish to construct an HMM model with large state space and large explicit state duration and process a large amount of measurement data to obtain high accuracy. We propose a new forward-backward algorithm whose computational complexity is only O((MD + M sup 2 )T), a reduction by almost a factor of D when D > M and whose memory requirement is O(MT). As an application example, we discuss an HMM characterization of access traffic observed at a large-scale Web site: we formulate the Web access pattern in terms of an HMM with explicit duration and estimate the model parameters using our algorithm.
@cite_24: We consider problems of sequence processing and propose a solution based on a discrete-state model in order to represent past context. We introduce a recurrent connectionist architecture having a modular structure that associates a subnetwork to each state. The model has a statistical interpretation we call input-output hidden Markov model (IOHMM). It can be trained by the estimation-maximization (EM) or generalized EM (GEM) algorithms, considering state trajectories as missing data, which decouples temporal credit assignment and actual parameter estimation. The model presents similarities to hidden Markov models (HMMs), but allows us to map input sequences to output sequences, using the same processing style as recurrent neural networks. IOHMMs are trained using a more discriminant learning paradigm than HMMs, while potentially taking advantage of the EM algorithm. We demonstrate that IOHMMs are well suited for solving grammatical inference problems on a benchmark problem. Experimental results are presented for the seven Tomita grammars, showing that these adaptive models can attain excellent generalization.
@cite_23: Hidden Markov modeling (HMM) techniques have been used successfully for connected speech recognition in the last several years. In the traditional HMM algorithms, the probability of duration of a state decreases exponentially with time which is not appropriate for representing the temporal structure of speech. Non-parametric modeling of duration using semi-Markov chains does accomplish the task with a large increase in the computational complexity. Applying a postprocessing state duration penalty after Viterbi decoding adds very little computation but does not affect the forward recognition path. The authors present a way of modeling state durations in HMM using time-dependent state transitions. This inhomogeneous HMM (IHMM) does increase the computation by a small amount but reduces recognition error rates by 14-25 . Also, a suboptimal implementation of this scheme that requires no more computation than the traditional HMM is presented which also has reduced errors by 14-22 on a variety of databases. >
@cite_15: This paper deals with a recent statistical model based on fuzzy Markov random chains for image segmentation, in the context of stationary and non-stationary data. On one hand, fuzzy scheme takes into account discrete and continuous classes through the modeling of hidden data imprecision and on the other hand, Markovian Bayesian scheme models the uncertainty on the observed data. A non-stationary fuzzy Markov chain model is proposed in an unsupervised way, based on a recent Markov triplet approach. The method is compared with the stationary fuzzy Markovian chain model. Both stationary and non-stationary methods are enriched with a parameterized joint density, which governs the attractiveness of the neighbored states. Segmentation task is processed with Bayesian tools, such as the well known MPM (Mode of Posterior Marginals) criterion. To validate both models, we perform and compare the segmentation on synthetic images and raw optical patterns which present diffuse structures.
@cite_13: 
With regard to the extensions of HMM, Xue proposed transition-emitting HMMs (TE-HMMs) and state-emitting HMMs (SE-HMMs) to treat the discontinuous symbol @cite_9 , of which application is an off-line handwriting word recognition. The observation data contain discontinuous and continuous symbols between characters when writing in cursive letters. They specifically examined such discontinuous features and continuous features, and extended HMM to treat both of them. Bengio focused on mapping input sequences to the output sequences @cite_24 . The proposed model supports a recurrent networks processing style and describes an extended architecture under the supervised learning paradigm. Salzenstein dealt with a statistical model based on Fuzzy Markov random chains for image segmentations in the context of stationary and non-stationary data @cite_15 . They specifically examined the observation in a non-stationary context, and proposed a model and a method to estimate model parameters . Yu proposed the explicit-duration hidden Markov model @cite_29 @cite_7 @cite_23 @cite_13 . They emphasized the interval between state transition, and proposed a new forward-backward algorithm to estimate the model parameters.