# Efficient and Effective Learning of HMMs Based on Identification of Hidden States

Authors: Tingting Liu; Jan Lemeire
Journal: Mathematical Problems in Engineering
 (2017)

---

## Abstract

The predominant learning algorithm for Hidden Markov Models (HMMs) is local search heuristics, of which the Baum-Welch (BW) algorithm is mostly used. It is an iterative learning procedure starting with a predefined size of state spaces and randomly chosen initial parameters. However, wrongly chosen initial parameters may cause the risk of falling into a local optimum and a low convergence speed. To overcome these drawbacks, we propose to use a more suitable model initialization approach, a Segmentation-Clustering and Transient analysis (SCT) framework, to estimate the number of states and model parameters directly from the input data. Based on an analysis of the information flow through HMMs, we demystify the structure of models and show that high-impact states are directly identifiable from the properties of observation sequences. States having a high impact on the log-likelihood make HMMs highly specific. Experimental results show that even though the identification accuracy drops to 87.9% when random models are considered, the SCT method is around 50 to 260 times faster than the BW algorithm with 100% correct identification for highly specific models whose specificity is greater than 0.06.


---

## Body

## 1. Introduction

Hidden Markov Models (HMMs) [1] are one of the statistical modelling tools showing great success and have been widely used in diverse application fields such as speech processing [2], machine maintenance [3], acoustics [4], biosciences [5], handwriting and text recognition [6], and image processing [7]. Despite the merit of simplicity and learning capabilities, HMMs are still facing open problems such as learning effectiveness and efficiency.There are two major problems in HMM learning: (1) choosing model size (number of hidden states); (2) estimating model parameters. Regarding the first problem, state-of-the-art approaches normally train multiple HMMs with different numbers of states and the best one is selected using specific criteria (e.g., the Akaike information criterion (AIC) [8], the Bayesian Information Criterion (BIC) [9]). In order to tackle the second problem, traditional learning algorithms such as the Baum-Welch (BW) algorithm are used to iteratively optimize model parameters starting from a, most often randomly chosen, initial set of parameters. Such iterative optimization heuristic approaches are prone to local optima. Therefore, multiple runs (typically, 10 [10, 11] or 20 [12, 13]) with several different initializations are performed and the optimal one of these is chosen. However, such iterative approaches with multiple trainings have significant drawbacks of time inefficiency and a high computational cost. Hsu et al. [14] introduced a noniterative method employing spectral-based algorithm for learning HMMs. It is simple and employs only a singular value decomposition and matrix multiplications. Nonetheless, it is evaluated in [15] and shown to be only applicable to identify systems when relatively few observations are available but fail completely for systems when the available observations are large. Fox et al. [8] proposed a sticky HDP-HMM which is a nonparametric, infinite-state model that automatically learns the size of state spaces and the smoothly varying dynamics robustly. However, this approach is computationally prohibitive when datasets are very large [9]. Therefore, in spite of the limitations, classical iterative approaches are still widely used to estimate model size and model parameters, for lack of alternatives.The aim of this paper is to improve the effectiveness and efficiency in model learning compared to the conventional BW algorithm, in the sense of accurately and quickly finding the correct model. One of the HMM assumptions is that the observed data is only dependent on the hidden states given the model. Therefore, the observed data often reflects the structure and statistical properties of the model, which motivates us to introduce a data-driven preestimation procedure to estimate the number of states and choose proper initial model parameters.We firstly provide insight into the essential features of an HMM model that help to improve the model’s expressiveness as a stochastic process [16]. This is conducted by inspecting the role of each hidden state in generating observation distributions as well as providing information on the model structure. Hidden states with a large influence on observation sequences increase the value of a model more than those without or with low influence. By analysing how the information flows through the HMMs, we determine which cases make a state have a high impact. As discussed in Section 3, persistent and/or transient-cyclic states appear to be high-impact states. Moreover, a model with high-impact states is highlyspecific and will be easy to identify. We introduce the termspecificity as the minimum model distance between a model and the best of HMMs with one state less. On the contrary, some HMMs are in principle unidentifiable which has been proved in [17] by linking the learning of HMMs to the nonlearnability results of finite automata. Furthermore, there are models in between the learnable and the unlearnable HMMs, which are hard to learn from observation sequences. Such HMMs contain complex parameter configurations with low specificity and low-impact states. Overall, experimental results show that a better number of states and proper initialization learned by the proposed method increase the learning speed and accuracy of highly specific HMMs compared to the traditional Baum-Welch algorithm.The remainder of the paper is organized as follows: in Section2, the preliminaries about HMMs and the Baum-Welch learning problems are briefly reviewed, followed by the concepts and definitions of model characteristics such as model identifiability, model equivalence, and the minimality of models. In Section 3, the impact of states on model specificity is studied through the information analysis. Followed by the approximate identification framework in Section 4, experiments and results are discussed in Section 5. Finally, conclusions are given in Section 6.


## 2. Preliminaries

An HMM [1] is a doubly stochastic process where the underlying process is characterized by a Markov chain and unobservable (hidden) but can be observed through another stochastic process which emits the sequence of observations. Let Q denote the number of states and M the number of observation symbols. Let S=s1,s2,…,sQ and V=v1,v2,…,vM denote the set of states and the set of observations, respectively. Using qt and ot to represent the state and the emitted observation at time t, respectively, the state and observation sequences are denoted by vectors q1:t=q1,q2,…,qt and o1:t=o1,o2,…,ot, where 1≤t≤T, and T is the number of states or observations in the sequence. A discrete time HMM model can be characterized by the quintuple λ=(π,Q,M,A,B) [1]: the initial state probability distribution is a column vector π=πi, where the ith element is(1)πi=Pq1=si1≤i≤Qthe state transition probability distribution matrix is A=aij∈R+Q×Q, where the i,jth element is(2)aij=Pqt+1=sj∣qt=si,1≤i,j≤Q,and the observation probability distribution matrix is B=bik∈R+Q×M, where the i,kth element is(3)bik=Pot=vk∣qt=si,1≤i≤Q,1≤k≤M.To note that the state transition probabilities of state sr include bothincoming andoutgoing probabilities, theincoming state transition probabilities of sr are the rth column vector of A, denoted as(4)a:r=a1r,a2r,…,aQr=airi=1Q∈R+Q×1and theoutgoing state transition probabilities of sr is the rth row vector of A, denoted as(5)ar:=ar1,ar2,…,arQ=arii=1Q∈R+1×Q,where 1≤r≤Q and R+ represents the set of nonnegative real numbers.


### 2.1. The Baum-Welch Learning Algorithm

One of the three basic problems for HMMs is the learning problem [1], which is often solved by an Expectation-Maximization (EM) algorithm [18], named the Baum-Welch algorithm [19, 20]. Starting with an initial guess of the model λ0 at random, the model parameters are iteratively reestimated as long as the new model has an increased likelihood compared to the previous one; that is, Pλ~(o1:T)≥Pλ(o1:T), where Pλ(o1:T) and Pλ~(o1:T) represent the likelihood values of an observation sequence o1:T generated by the previous model λ and the newly updated model λ~, respectively. This procedure continues until the likelihood converges to a stationary point. However, the BW algorithm suffers from the problem of getting stuck at a local optimum if the initial model parameters are not well chosen, which inspires this study to search for a better estimation of the initial parameters.For the analysis, we need to calculate the likelihood of observations given the model, that is,Pλ(o1:t). It can be written by the use of the projection operations; see, for instance, [16, p. 18]. Let αt=αtii=1Q∈R+Q×1 and τt=τtii=1Q∈R+Q×1, where(6)τti=Pλqt=sit=1Pλqt=si,o1:t-11<t≤T,αti=Pλqt=si,o1:t1≤t≤T;thus(7)αt=Botτt,τt+1=Aαt,where ot=vk∈V,1≤t≤T and Bot=diag⁡b1k,b2k,…,bQk∈R+Q×Q which denotes the diagonal matrix of which the diagonal elements are the kth column of B.Therefore, thelikelihood of the observations given the model can be expressed as(8)Pλo1:t=Pλo1∏t=2TPλot∣o1:t-1=τtTBote,where e is a column vector of length Q with all entries equal to 1; that is, e=11⋯1T=1Q×1. For the convenience of calculations, the logarithm of likelihoodlog-likelihood (LL) is often used rather than the likelihood. Moreover, in this dissertation, we useunit log-likelihood, an averaged LL, to present the LL per single observation, that is, 1/Tlog⁡Pλ(o1:T), where T is the number of observations. Within this paper, the termlog-likelihood is used to representunit log-likelihood for simplicity.


### 2.2. Definitions of Model Characteristics

In this paper, we determine the learnability of HMMs through model identifiability. If two models are equivalent, the true model cannot be uniquely identified. Hence we firstly introduce the definition for model equivalence. Note that the HMM learning can be considered as a probability distribution specific problem, where every HMM has to be identified from the observations generated according to its own likelihood distribution. Therefore, the equivalence of HMMs can be defined based on their observation likelihood distributions as follows.Definition 1 (HMM equivalence).
Two HMM modelsλ and λ~ areequivalent if and only if both models have the same observation emission probabilities (i.e., likelihood distribution over time series) for every observation sequence o1:t(9)Pλo1:t=Pλ~o1:t;alternatively,(10)Pλo1=Pλ~o1Pλot∣o1:t-1=Pλ~ot∣o1:t-1∀t,2<t≤T.Note that the observation probabilitiesPλ(o1:t) can remain the same by permuting the states of λ since the states can be arbitrarily labeled. The model λ~ with permuted states is called atrivial equivalent model of the original model λ as defined in [21]. We considertrivial equivalent models as the same model. In order to compare the models in later sections, we need to label states in a unique way such that corresponding states receive the same label. Therefore we define a process to normalize HMMs as follows.Definition 2 (HMM normalization).
For each statesi, a score is calculated by ϖ=∑k=1Mbikk. Based on the score, we sort the states in ascending order.Additionally, we can always construct an equivalent HMM with additional state numbers [22]; hence, in this paper, we consider HMM identifiability only when it isminimal, as defined below.Definition 3 (HMM minimality).
An HMMλ=(π,Q,M,A,B) isminimal if and only if it has equal number of states to or fewer number of states than any other equivalent model λ~=(π~,Q~,M~,A~,B~); that is, Q≤Q~. Model λ is called asimpler model of λ~ if they are equivalent and Q<Q~.Definition 4 (HMM identifiability).
An HMMλ isidentifiable if and only if it is minimal and there does not exist anynontrivially equivalent model λ~ with an equal number of states; that is, Q≠Q~.Moreover, in this study we only address the identification ofstationary (orhomogeneous) HMMs where the prior probabilities can be eliminated in calculations. The initial state prior probability distribution π has an influence on learning only at the beginning of an observation sequence and its impact on large sequences vanishes over time and thus can be excluded for learning HMMs in practice. A stationary HMM is defined as follows.Definition 5 (stationary HMM).
An HMM isstationary if its state distribution remains the same at every time instant; that is, π1=π2=⋯=π(t)=π, where π equals the equilibrium state distribution; that is, ABotπ=π [23, p. 4902].The elementπ(t) is a column vector with π(t)=Pqt=sii=1Q∈R+Q×1,1≤t≤T, and eTπ(t)=1. The element ABot represents the probability of going from state si to state sj while emitting the observation vk by state si, that is, P(qt+1=sj,ot=vk∣qt=si).Our proposed learning approach is based on the properties of observation sequences that make a state have a large impact on the model. To describe the degree of influence that a state can make on a model, we define a new term calledspecificityS(λ) as thedistance between model λ and thebest model with one state less. Bybest, we mean that it matches the most on observations generated by the original model λ among all the one-state-fewer models, which also means that it has the minimum model distance to the original model λ. A general definition ofmodel distance is as follows.Definition 6 (HMM model distance).
A model distance between two HMMsλ1 and λ2 is the difference of the unit log-likelihood of an observation sequence o1:Tλ2 [1, p. 271]:(11)Dλ1,λ2=E1Tlog⁡Pλ2o1:Tλ2-log⁡Pλ1o1:Tλ2,where E· refers to the expectation operator, o1:Tλ2 is an observation sequence generated by model λ2, and T is the size of the sequence. Equation (11) is basically a measure of how well model λ1 matches observations generated by model λ2, in comparison with how well model λ2 matches observations generated by itself [1]. Thespecificity of a model can be then defined as follows.Definition 7 (HMM specificity).
Thespecificity of an HMM λ with Q states is(12)Sλ=minλ~∈ΛQ-1E1TlogPλ⁡o1:Tλ-log⁡Pλ~o1:Tλ,where Λ(Q-1) represents the set of all HMMs with Q-1 states and T is the length of an observation sequence o1:Tλ generated by λ. We denote the optimal model λ~ with the minimum distance to model λ in (12) as λ¯Q-1(λQ).We have to note that, to use Definitions6 and 7 in practice, we will calculate the expectation with a single generated observation sequence. We assume that this sequence is long enough such that it is a typical sequence and gives a stable value which comes close to the expected value and as such is independent of the exact sequence, as is done by Rabiner [1].To use the above definitions on a limited set of observation sequences, we have to rely on an approximate equivalence approach. In order to compare the HMMs according to the likelihood probabilityPλ(o1:T) given a set of observation sequences o1:T, we have to define a threshold on the model distance to decide whether two HMM models are equivalent or not.Definition 8 (distance threshold of equivalent HMMs).
Thedistance threshold is defined as(13)-3σ,+3σ,where N(μ,σ2) is the asympototic distribution of log-likelihood 1/Tlog⁡Pλ(o1:T(λ,i)) with T→∞, the element o1:T(λ,i),(i=1,2,…,n) represents randomly generated sequences by model λ, T is the length of an observation sequence, and n is the total number of observation sequences [24]. Duan et al. [24] prove that the distribution of the log-likelihood 1/Tlog⁡Pλ(o1:T(λ,i)) can be approximated by a normal distribution N(μ,σ2). According to the “three-sigma” rule, the interval (μ-3σ,μ+3σ) contains 99% of the whole distribution. Thus a sequence o1:T(λ,i) has a 99% certainty of being generated by the model λ~ if its log-likelihood 1/Tlog⁡Pλ~(o1:T(λ,i))∈(μ-3σ,μ+3σ),∀i. As defined in Definition 1, two models are equivalent if and only if both models have the same likelihood distribution on observations. Hence for any sequence o1:T(λ,i) generated by model λ, if λ~ has a log-likelihood within the interval, that is, 1/Tlog⁡Pλ~(o1:T(λ,i))∈(μ-3σ,μ+3σ),∀i, we can say the two models are approximately equal. Therefore, the model distance threshold of equivalence is approximated as (-3σ,+3σ) of the reference model for practical use.As defined in Definition3, a model isminimal if and only if it has equal number of states to or fewer number of states than any other equivalent models. In order to check model minimality in practice, we verify if there exists no one-state simpler model λ~ which is equivalent to model λ, in particular, to verify if the minimum distance between λ~ and λ (i.e., the specificity of λ~; see Definition 7) is outside the threshold of equivalent models defined in Definition 8. Therefore, the practical condition to checkmodel minimality is defined as follows: a model λ can be approximately taken asminimal if the absolute value of itsspecificity is outside thedistance threshold of 3-sigma; that is, S(λ)>3σ.


## 2.1. The Baum-Welch Learning Algorithm

One of the three basic problems for HMMs is the learning problem [1], which is often solved by an Expectation-Maximization (EM) algorithm [18], named the Baum-Welch algorithm [19, 20]. Starting with an initial guess of the model λ0 at random, the model parameters are iteratively reestimated as long as the new model has an increased likelihood compared to the previous one; that is, Pλ~(o1:T)≥Pλ(o1:T), where Pλ(o1:T) and Pλ~(o1:T) represent the likelihood values of an observation sequence o1:T generated by the previous model λ and the newly updated model λ~, respectively. This procedure continues until the likelihood converges to a stationary point. However, the BW algorithm suffers from the problem of getting stuck at a local optimum if the initial model parameters are not well chosen, which inspires this study to search for a better estimation of the initial parameters.For the analysis, we need to calculate the likelihood of observations given the model, that is,Pλ(o1:t). It can be written by the use of the projection operations; see, for instance, [16, p. 18]. Let αt=αtii=1Q∈R+Q×1 and τt=τtii=1Q∈R+Q×1, where(6)τti=Pλqt=sit=1Pλqt=si,o1:t-11<t≤T,αti=Pλqt=si,o1:t1≤t≤T;thus(7)αt=Botτt,τt+1=Aαt,where ot=vk∈V,1≤t≤T and Bot=diag⁡b1k,b2k,…,bQk∈R+Q×Q which denotes the diagonal matrix of which the diagonal elements are the kth column of B.Therefore, thelikelihood of the observations given the model can be expressed as(8)Pλo1:t=Pλo1∏t=2TPλot∣o1:t-1=τtTBote,where e is a column vector of length Q with all entries equal to 1; that is, e=11⋯1T=1Q×1. For the convenience of calculations, the logarithm of likelihoodlog-likelihood (LL) is often used rather than the likelihood. Moreover, in this dissertation, we useunit log-likelihood, an averaged LL, to present the LL per single observation, that is, 1/Tlog⁡Pλ(o1:T), where T is the number of observations. Within this paper, the termlog-likelihood is used to representunit log-likelihood for simplicity.


## 2.2. Definitions of Model Characteristics

In this paper, we determine the learnability of HMMs through model identifiability. If two models are equivalent, the true model cannot be uniquely identified. Hence we firstly introduce the definition for model equivalence. Note that the HMM learning can be considered as a probability distribution specific problem, where every HMM has to be identified from the observations generated according to its own likelihood distribution. Therefore, the equivalence of HMMs can be defined based on their observation likelihood distributions as follows.Definition 1 (HMM equivalence).
Two HMM modelsλ and λ~ areequivalent if and only if both models have the same observation emission probabilities (i.e., likelihood distribution over time series) for every observation sequence o1:t(9)Pλo1:t=Pλ~o1:t;alternatively,(10)Pλo1=Pλ~o1Pλot∣o1:t-1=Pλ~ot∣o1:t-1∀t,2<t≤T.Note that the observation probabilitiesPλ(o1:t) can remain the same by permuting the states of λ since the states can be arbitrarily labeled. The model λ~ with permuted states is called atrivial equivalent model of the original model λ as defined in [21]. We considertrivial equivalent models as the same model. In order to compare the models in later sections, we need to label states in a unique way such that corresponding states receive the same label. Therefore we define a process to normalize HMMs as follows.Definition 2 (HMM normalization).
For each statesi, a score is calculated by ϖ=∑k=1Mbikk. Based on the score, we sort the states in ascending order.Additionally, we can always construct an equivalent HMM with additional state numbers [22]; hence, in this paper, we consider HMM identifiability only when it isminimal, as defined below.Definition 3 (HMM minimality).
An HMMλ=(π,Q,M,A,B) isminimal if and only if it has equal number of states to or fewer number of states than any other equivalent model λ~=(π~,Q~,M~,A~,B~); that is, Q≤Q~. Model λ is called asimpler model of λ~ if they are equivalent and Q<Q~.Definition 4 (HMM identifiability).
An HMMλ isidentifiable if and only if it is minimal and there does not exist anynontrivially equivalent model λ~ with an equal number of states; that is, Q≠Q~.Moreover, in this study we only address the identification ofstationary (orhomogeneous) HMMs where the prior probabilities can be eliminated in calculations. The initial state prior probability distribution π has an influence on learning only at the beginning of an observation sequence and its impact on large sequences vanishes over time and thus can be excluded for learning HMMs in practice. A stationary HMM is defined as follows.Definition 5 (stationary HMM).
An HMM isstationary if its state distribution remains the same at every time instant; that is, π1=π2=⋯=π(t)=π, where π equals the equilibrium state distribution; that is, ABotπ=π [23, p. 4902].The elementπ(t) is a column vector with π(t)=Pqt=sii=1Q∈R+Q×1,1≤t≤T, and eTπ(t)=1. The element ABot represents the probability of going from state si to state sj while emitting the observation vk by state si, that is, P(qt+1=sj,ot=vk∣qt=si).Our proposed learning approach is based on the properties of observation sequences that make a state have a large impact on the model. To describe the degree of influence that a state can make on a model, we define a new term calledspecificityS(λ) as thedistance between model λ and thebest model with one state less. Bybest, we mean that it matches the most on observations generated by the original model λ among all the one-state-fewer models, which also means that it has the minimum model distance to the original model λ. A general definition ofmodel distance is as follows.Definition 6 (HMM model distance).
A model distance between two HMMsλ1 and λ2 is the difference of the unit log-likelihood of an observation sequence o1:Tλ2 [1, p. 271]:(11)Dλ1,λ2=E1Tlog⁡Pλ2o1:Tλ2-log⁡Pλ1o1:Tλ2,where E· refers to the expectation operator, o1:Tλ2 is an observation sequence generated by model λ2, and T is the size of the sequence. Equation (11) is basically a measure of how well model λ1 matches observations generated by model λ2, in comparison with how well model λ2 matches observations generated by itself [1]. Thespecificity of a model can be then defined as follows.Definition 7 (HMM specificity).
Thespecificity of an HMM λ with Q states is(12)Sλ=minλ~∈ΛQ-1E1TlogPλ⁡o1:Tλ-log⁡Pλ~o1:Tλ,where Λ(Q-1) represents the set of all HMMs with Q-1 states and T is the length of an observation sequence o1:Tλ generated by λ. We denote the optimal model λ~ with the minimum distance to model λ in (12) as λ¯Q-1(λQ).We have to note that, to use Definitions6 and 7 in practice, we will calculate the expectation with a single generated observation sequence. We assume that this sequence is long enough such that it is a typical sequence and gives a stable value which comes close to the expected value and as such is independent of the exact sequence, as is done by Rabiner [1].To use the above definitions on a limited set of observation sequences, we have to rely on an approximate equivalence approach. In order to compare the HMMs according to the likelihood probabilityPλ(o1:T) given a set of observation sequences o1:T, we have to define a threshold on the model distance to decide whether two HMM models are equivalent or not.Definition 8 (distance threshold of equivalent HMMs).
Thedistance threshold is defined as(13)-3σ,+3σ,where N(μ,σ2) is the asympototic distribution of log-likelihood 1/Tlog⁡Pλ(o1:T(λ,i)) with T→∞, the element o1:T(λ,i),(i=1,2,…,n) represents randomly generated sequences by model λ, T is the length of an observation sequence, and n is the total number of observation sequences [24]. Duan et al. [24] prove that the distribution of the log-likelihood 1/Tlog⁡Pλ(o1:T(λ,i)) can be approximated by a normal distribution N(μ,σ2). According to the “three-sigma” rule, the interval (μ-3σ,μ+3σ) contains 99% of the whole distribution. Thus a sequence o1:T(λ,i) has a 99% certainty of being generated by the model λ~ if its log-likelihood 1/Tlog⁡Pλ~(o1:T(λ,i))∈(μ-3σ,μ+3σ),∀i. As defined in Definition 1, two models are equivalent if and only if both models have the same likelihood distribution on observations. Hence for any sequence o1:T(λ,i) generated by model λ, if λ~ has a log-likelihood within the interval, that is, 1/Tlog⁡Pλ~(o1:T(λ,i))∈(μ-3σ,μ+3σ),∀i, we can say the two models are approximately equal. Therefore, the model distance threshold of equivalence is approximated as (-3σ,+3σ) of the reference model for practical use.As defined in Definition3, a model isminimal if and only if it has equal number of states to or fewer number of states than any other equivalent models. In order to check model minimality in practice, we verify if there exists no one-state simpler model λ~ which is equivalent to model λ, in particular, to verify if the minimum distance between λ~ and λ (i.e., the specificity of λ~; see Definition 7) is outside the threshold of equivalent models defined in Definition 8. Therefore, the practical condition to checkmodel minimality is defined as follows: a model λ can be approximately taken asminimal if the absolute value of itsspecificity is outside thedistance threshold of 3-sigma; that is, S(λ)>3σ.


## 3. Impact of States on Observation Likelihood

We start the study through an information flow analysis as to see the impact of different types of states on model specificity.


### 3.1. Information Flow Analysis

Our aim is to understand which parameters make an HMM have a higher specificity. However, an analytical equation for the specificity functionS(λ) requires us to know the optimal one-state-simpler model λ¯Q-1(λQ), which is still an open problem. This leads us to an alternative approach by analysingstate properties of models. In the following analysis, we will study which properties make up ahigh-impact state and which do not. Ahigh-impact state makes itself more specific with a significant influence on Pλ(o1:t); thus it emits relatively unique patterns of observation sequences which can be distinguished from other states. Using this analysis, we will in this paper propose a framework to identify thehigh-impact states.To study what influences thespecificity of an HMM, we analyse the impact of a state on the likelihood Pλ(o1:t) and how it contributes to S(λ) as follows. Consider Pλ(ot+1∣o1:t) in (10). It can be seen as a probability used in predicting the future from the past and it represents the information flow from the past to the future. Hence we will analyse the contribution of a specific state to this probability. There are three cases whereby the probability of the state qt plays a role in the information flow, as shown in Figure 1:(a)
The present state probability depends on the previous state probability and partly determines the observation probabilityPλ(ot∣o1:t-1).(b)
The present state probability depends on the observations and determines the succeeding state probability. The observation probabilityPλ(ot+1∣o1:t) depends on Pλ(qt∣o1:t) which is updated with the knowledge of ot.(c)
The present state probability is determined by the past state probability and affects the future state probability.Figure 1
Role of a state in the likelihood.
(a) (b) (c)


### 3.2. High-Impact States

We now investigate the high-impact states on likelihoodPλ(o1:t), more specifically on thespecificityS(λ). Such states should have ahigh andunique impact on the likelihood wherehigh means a high information flow passing from the past to the future states andunique ensures that no other states can fill in the same role, such that it cannot be mimicked by other states either with combined similar probabilities or emitting similar observation probabilities. For instance, a state with a probability of 0.5 can be mimicked by a combination of two states with probabilities of 0.1 and 0.9, respectively; or a state with observation emission probabilities of 0.5 is also not unique. Note that a relatively high or low probability is more difficult to be mimicked than 0.5 in the previous examples. Hence for the three cases outlined in Figure 1, the state plays an intermediate role in predicting the future based on the past; we can define the following conditions for high-impact state, respectively:(a)
(1) The incoming transition probabilitiesa:r (see (4)) of state sr at time t are maximal or minimal; that is, air≫aiq∥air≪aiq,∀q≠r,1≤i≤Q; (2) state sr has adominant observation vk at time t, meaning the observation probability brk (see (3)) is maximal; that is, brk≫bqk,∀q≠r.(b)
(1) The outgoing transition probabilitiesar: (see (5)) of state sr at time t are maximal or minimal; that is, ari≫aqi∥ari≪aqi,∀q≠r,1≤i≤Q; (2) state sr has adominant observation vk at time t; refer to condition a(2).(c)
Refer to conditions a(1) and b(1).For high specificity, the above conditions should be met for all states of a model. Note that these conditions are based on statetransition andobservation probabilities. Regardingtransition probabilities, a highly specific HMM should containpersistent and/ortransient-cyclic states, as defined below:(i)
Apersistent state is a state with a higherself-transition probability than the probabilities to transit to other states. When all states of an HMM arepersistent, the HMM remains for a certain period in one state before changing into another state. Such HMM is called apersistent HMM.(ii)
Atransient state, on the other hand, has a lowerself-transition probability. Atransient-cyclic state has one specific incoming transition probability which is high and dominant and one outgoing transition probability which is high. When all states of an HMM aretransient-cyclic, the HMM flips from one state to another, mostly following a certain pattern (e.g., s1→s2⋯→sQ→s1→s2⋯). Such HMM is called atransient-cyclic HMM. Otherwise, it is called atransient-acyclic HMM.(iii)
When an HMM contains bothpersistent andtransient-cyclic states, we call it ahybrid HMM.Secondly, regardingobservation probabilities, a highly specific HMM should containprivileged states, which is defined as follows:Aprivileged state is a state with at least onedominant observation probability.HMMs containing onlyprivileged states are calledprivileged HMMs. This is possible when the number of observations is larger than the number of states; that is, M≥Q.Considering bothtransition andobservation probabilities, we define ahighly specific HMM as an HMM containing onlypersistent states and/ortransient-cyclic states, which will be shown as identifiable from observation sequences. Note that it is impossible to identify all minimal HMMs, especially when the influence of some states on a model is low, in the sense that such states can be neglected and the resultant simpler model is comparable to a complex one. In order to learn aminimal identifiable HMM, we propose in a later section an effective and efficient model approximation method which identifiespersistent states with segmentation and clustering methods andtransient-cyclic states with a transient analysis based on the following theorem.Theorem 9.
The presence of transient-cyclic states with dominant observations can be identified as follows: for values ofk,l,m∈1,M,k≠l≠m, if P-(ot=vk,ot+1=vl)>ξ and P-(ot+1=vl,ot+2=vm)>ξ, where 0≤ξ≤1, P-(∗) represents therelative frequency (i.e., the ratio of the number of times) of event ∗ occurring in the observed sequence, which is also the predicted probability of the occurrence of event ∗; then for(14)ħk,l,m=P-ot=vk,ot+1=vlP-ot+1=vl,ot+2=vmP-ot=vk,ot+1=vl,ot+2=vm,(a)
ifħ≈1, that is, ħ∈1-ϵ,1+ϵ, ϵ≈0, the triple P-(ot=vk,ot+1=vl,ot+2=vm) does not reveal hidden transient-cyclic states and thus it can be modelled by a 1-order Markov model,(b)
ifħ≉1, the triple P-(ot=vk,ot+1=vl,ot+2=vm) reveals that hidden transient-cyclic states are present:
(i)
Ifħ<1-ϵ, the triple reveals states with dominant observations.(ii)
Ifħ>1+ϵ, the triple reveals states with dominant observations and an extra mixing state.The proof is in AppendixA.The definitions of a Markov model and amixing state used in the theorem are given as follows:(i)
AMarkov model is a stochastic process that is characterized by a Markov chain. It models the observed states with a random variable which satisfies the Markov property; that is, the distribution of the current state depends only on that of the previous state instead of the whole historical states. The state transition probability distribution and the initial state probability distribution are denoted by the same expressions as the HMM defined previously. The model can be written as λ=(π,A).(ii)
Amixing state is a state which outputs the same observation probabilities as a mixture of other states. HMM models containing mixing states are problematic, since one state has the same output distribution as a convex mixture of some other states’ output distribution; therefore it is difficult to distinguish the ground truth state between a single state and a mixture of several states [14].


### 3.3. Equivalent States

Now we try to understand when a state has zero impact on the specificity such that in the extreme case a simpler HMM exists with the same distributions. Considering the information flowpast→state→future, for the first arrow, the influence of a state is negligible when (1a) P(state=sr∣past) is close to zero; (1b) the state has an equal influence as another state if the probability equals that of another state; or (1c) the influence of the state can be mimicked by the other state if the probability is constant. Note that if it is neither constant nor the same as another state, the state probability will fluctuate which makes that its influence cannot be incorporated into that of other states. For the second arrow, the influence of the state can be incorporated into that of other states if (2a) P(future∣state=sr) is the same as the probabilities of another state or (2b) the probability distribution is not dominant.In case (1a) the state plays no role and can be removed, in cases (1b) and (2a) the state can be merged with a similar state, and in cases (1c) and (2b) the influence of the state can be “taken over” by some of the remaining states. This leads to the conditions for eliminating redundant (i.e., equivalent) states as shown in Table1. Note that the difference between “removal” and “taken over” is that, by removing a state, its information is removed together with the state, while “taking over” a state means that even though the state is deleted, its information stays and is passed to other states instead.Table 1
Conditions on a stater(1≤r≤Q) to achieve minimality through the removal of the state, the merging with another state, or the adjustment of the probabilities by some other states such that the influence is “taken over.”
State reduction State conditions Removal (1a)air=0,∀i∈[1,Q]  Merge (1b)air=aiq,∀q≠r,∀i∈[1,Q] (2a)ari=aqi,∀q≠r,∀i∈[1,Q]  Taken over (1c)air=C,∀i∈[1,Q], C is constant (2b) non dominantbrk,∀k∈[1,M]Based on the conditions of equivalent states defined in Table1, we now can formalize the results of our analysis in sufficient conditions for nonminimality HMMs as follows.Theorem 10.
A stationary HMM is not minimal if one of the following conditions holds:(i)
The HMM contains a stater that has zero incoming state transition probabilities; that is, air=0,∀i∈1,Q.(ii)
The HMM contains two statesq and r that have the same state transition probabilities; that is, aiq=air and aqi=ari,∀i∈1,Q.(iii)
The HMM contains two statesq and r that have the same observation probabilities bqk=brk,∀k∈1,M and meets one of the following conditions: (1) they have the same incoming state transition probabilities; that is, aiq=air,∀i∈1,Q; (2) they have the same outgoing state transition probabilities; that is, aqi=ari,∀i∈1,Q; or (3) aiq=air and aqi=ari,∀i∈1,Q∖q,r.(iv)
The HMM has two observation values(M=2) and contains a state r that has constant incoming state transition probabilities; that is, air=C and for all k, r has nondominant observation probabilities; that is, brk<bik,∀i∈1,Q∖r,∀k∈1,M.The proof is in AppendixB.


### 3.4. Low-Impact States

Unlike high-impact or equivalent (zero-impact) states, some states have larger-than-zero but very low impact, which makes them hard to learn. Such states are called low-impact states. HMMs containing these states are calledhard to learn HMMs, as will be shown later.Since low-impact states are in between high-impact and equivalent states, they meet a combination of partial conditions defined for both cases. As introduced in Section3.2 for high-impact states, a learnable HMMs should contain onlypersistent and/ortransient-cyclic states withprivileged observations, while an unlearnable HMMs contains states which contains one or two states under conditions defined in Theorem 10. Therefore, combined partial conditions of both can be defined forhard to learn HMMs.An HMM ishard to learn if it contains mostlypersistent ortransient-cyclic states withprivileged states with dominant observations and is also under one of the following conditions:(i)
There exists a mixing stater whose observation distribution is a mixture of the observation distributions of two other states q and k; that is, brj=(bqj+bkj)/2, where q,r,k∈1,Q,∀j∈1,M.(ii)
There exists a stater with constant incoming transitions, self-included; that is, air=1/Q, where r∈1,Q,∀i∈1,Q.(iii)
There exists a stater with constant incoming transitions, self-excluded; that is, air=1-arr/Q-1, where r∈1,Q,∀i∈1,Q∖r.(iv)
There exists a stater with constant outgoing transitions, self-included; that is, ari=1/Q, where r∈1,Q,∀i∈1,Q.(v)
There exists a stater with constant outgoing transitions, self-excluded; that is, ari=1-arr/Q-1, where r∈1,Q,∀i∈1,Q∖r.(vi)
There exist two statesq and r with the same observation probabilities bqj=brj, where q,r∈1,Q,∀j∈1,M.(vii)
There exists a stater with constant (nondominant) observation emissions; that is, brj≅1/M, where r∈1,Q,∀j∈1,M.


## 3.1. Information Flow Analysis

Our aim is to understand which parameters make an HMM have a higher specificity. However, an analytical equation for the specificity functionS(λ) requires us to know the optimal one-state-simpler model λ¯Q-1(λQ), which is still an open problem. This leads us to an alternative approach by analysingstate properties of models. In the following analysis, we will study which properties make up ahigh-impact state and which do not. Ahigh-impact state makes itself more specific with a significant influence on Pλ(o1:t); thus it emits relatively unique patterns of observation sequences which can be distinguished from other states. Using this analysis, we will in this paper propose a framework to identify thehigh-impact states.To study what influences thespecificity of an HMM, we analyse the impact of a state on the likelihood Pλ(o1:t) and how it contributes to S(λ) as follows. Consider Pλ(ot+1∣o1:t) in (10). It can be seen as a probability used in predicting the future from the past and it represents the information flow from the past to the future. Hence we will analyse the contribution of a specific state to this probability. There are three cases whereby the probability of the state qt plays a role in the information flow, as shown in Figure 1:(a)
The present state probability depends on the previous state probability and partly determines the observation probabilityPλ(ot∣o1:t-1).(b)
The present state probability depends on the observations and determines the succeeding state probability. The observation probabilityPλ(ot+1∣o1:t) depends on Pλ(qt∣o1:t) which is updated with the knowledge of ot.(c)
The present state probability is determined by the past state probability and affects the future state probability.Figure 1
Role of a state in the likelihood.
(a) (b) (c)


## 3.2. High-Impact States

We now investigate the high-impact states on likelihoodPλ(o1:t), more specifically on thespecificityS(λ). Such states should have ahigh andunique impact on the likelihood wherehigh means a high information flow passing from the past to the future states andunique ensures that no other states can fill in the same role, such that it cannot be mimicked by other states either with combined similar probabilities or emitting similar observation probabilities. For instance, a state with a probability of 0.5 can be mimicked by a combination of two states with probabilities of 0.1 and 0.9, respectively; or a state with observation emission probabilities of 0.5 is also not unique. Note that a relatively high or low probability is more difficult to be mimicked than 0.5 in the previous examples. Hence for the three cases outlined in Figure 1, the state plays an intermediate role in predicting the future based on the past; we can define the following conditions for high-impact state, respectively:(a)
(1) The incoming transition probabilitiesa:r (see (4)) of state sr at time t are maximal or minimal; that is, air≫aiq∥air≪aiq,∀q≠r,1≤i≤Q; (2) state sr has adominant observation vk at time t, meaning the observation probability brk (see (3)) is maximal; that is, brk≫bqk,∀q≠r.(b)
(1) The outgoing transition probabilitiesar: (see (5)) of state sr at time t are maximal or minimal; that is, ari≫aqi∥ari≪aqi,∀q≠r,1≤i≤Q; (2) state sr has adominant observation vk at time t; refer to condition a(2).(c)
Refer to conditions a(1) and b(1).For high specificity, the above conditions should be met for all states of a model. Note that these conditions are based on statetransition andobservation probabilities. Regardingtransition probabilities, a highly specific HMM should containpersistent and/ortransient-cyclic states, as defined below:(i)
Apersistent state is a state with a higherself-transition probability than the probabilities to transit to other states. When all states of an HMM arepersistent, the HMM remains for a certain period in one state before changing into another state. Such HMM is called apersistent HMM.(ii)
Atransient state, on the other hand, has a lowerself-transition probability. Atransient-cyclic state has one specific incoming transition probability which is high and dominant and one outgoing transition probability which is high. When all states of an HMM aretransient-cyclic, the HMM flips from one state to another, mostly following a certain pattern (e.g., s1→s2⋯→sQ→s1→s2⋯). Such HMM is called atransient-cyclic HMM. Otherwise, it is called atransient-acyclic HMM.(iii)
When an HMM contains bothpersistent andtransient-cyclic states, we call it ahybrid HMM.Secondly, regardingobservation probabilities, a highly specific HMM should containprivileged states, which is defined as follows:Aprivileged state is a state with at least onedominant observation probability.HMMs containing onlyprivileged states are calledprivileged HMMs. This is possible when the number of observations is larger than the number of states; that is, M≥Q.Considering bothtransition andobservation probabilities, we define ahighly specific HMM as an HMM containing onlypersistent states and/ortransient-cyclic states, which will be shown as identifiable from observation sequences. Note that it is impossible to identify all minimal HMMs, especially when the influence of some states on a model is low, in the sense that such states can be neglected and the resultant simpler model is comparable to a complex one. In order to learn aminimal identifiable HMM, we propose in a later section an effective and efficient model approximation method which identifiespersistent states with segmentation and clustering methods andtransient-cyclic states with a transient analysis based on the following theorem.Theorem 9.
The presence of transient-cyclic states with dominant observations can be identified as follows: for values ofk,l,m∈1,M,k≠l≠m, if P-(ot=vk,ot+1=vl)>ξ and P-(ot+1=vl,ot+2=vm)>ξ, where 0≤ξ≤1, P-(∗) represents therelative frequency (i.e., the ratio of the number of times) of event ∗ occurring in the observed sequence, which is also the predicted probability of the occurrence of event ∗; then for(14)ħk,l,m=P-ot=vk,ot+1=vlP-ot+1=vl,ot+2=vmP-ot=vk,ot+1=vl,ot+2=vm,(a)
ifħ≈1, that is, ħ∈1-ϵ,1+ϵ, ϵ≈0, the triple P-(ot=vk,ot+1=vl,ot+2=vm) does not reveal hidden transient-cyclic states and thus it can be modelled by a 1-order Markov model,(b)
ifħ≉1, the triple P-(ot=vk,ot+1=vl,ot+2=vm) reveals that hidden transient-cyclic states are present:
(i)
Ifħ<1-ϵ, the triple reveals states with dominant observations.(ii)
Ifħ>1+ϵ, the triple reveals states with dominant observations and an extra mixing state.The proof is in AppendixA.The definitions of a Markov model and amixing state used in the theorem are given as follows:(i)
AMarkov model is a stochastic process that is characterized by a Markov chain. It models the observed states with a random variable which satisfies the Markov property; that is, the distribution of the current state depends only on that of the previous state instead of the whole historical states. The state transition probability distribution and the initial state probability distribution are denoted by the same expressions as the HMM defined previously. The model can be written as λ=(π,A).(ii)
Amixing state is a state which outputs the same observation probabilities as a mixture of other states. HMM models containing mixing states are problematic, since one state has the same output distribution as a convex mixture of some other states’ output distribution; therefore it is difficult to distinguish the ground truth state between a single state and a mixture of several states [14].


## 3.3. Equivalent States

Now we try to understand when a state has zero impact on the specificity such that in the extreme case a simpler HMM exists with the same distributions. Considering the information flowpast→state→future, for the first arrow, the influence of a state is negligible when (1a) P(state=sr∣past) is close to zero; (1b) the state has an equal influence as another state if the probability equals that of another state; or (1c) the influence of the state can be mimicked by the other state if the probability is constant. Note that if it is neither constant nor the same as another state, the state probability will fluctuate which makes that its influence cannot be incorporated into that of other states. For the second arrow, the influence of the state can be incorporated into that of other states if (2a) P(future∣state=sr) is the same as the probabilities of another state or (2b) the probability distribution is not dominant.In case (1a) the state plays no role and can be removed, in cases (1b) and (2a) the state can be merged with a similar state, and in cases (1c) and (2b) the influence of the state can be “taken over” by some of the remaining states. This leads to the conditions for eliminating redundant (i.e., equivalent) states as shown in Table1. Note that the difference between “removal” and “taken over” is that, by removing a state, its information is removed together with the state, while “taking over” a state means that even though the state is deleted, its information stays and is passed to other states instead.Table 1
Conditions on a stater(1≤r≤Q) to achieve minimality through the removal of the state, the merging with another state, or the adjustment of the probabilities by some other states such that the influence is “taken over.”
State reduction State conditions Removal (1a)air=0,∀i∈[1,Q]  Merge (1b)air=aiq,∀q≠r,∀i∈[1,Q] (2a)ari=aqi,∀q≠r,∀i∈[1,Q]  Taken over (1c)air=C,∀i∈[1,Q], C is constant (2b) non dominantbrk,∀k∈[1,M]Based on the conditions of equivalent states defined in Table1, we now can formalize the results of our analysis in sufficient conditions for nonminimality HMMs as follows.Theorem 10.
A stationary HMM is not minimal if one of the following conditions holds:(i)
The HMM contains a stater that has zero incoming state transition probabilities; that is, air=0,∀i∈1,Q.(ii)
The HMM contains two statesq and r that have the same state transition probabilities; that is, aiq=air and aqi=ari,∀i∈1,Q.(iii)
The HMM contains two statesq and r that have the same observation probabilities bqk=brk,∀k∈1,M and meets one of the following conditions: (1) they have the same incoming state transition probabilities; that is, aiq=air,∀i∈1,Q; (2) they have the same outgoing state transition probabilities; that is, aqi=ari,∀i∈1,Q; or (3) aiq=air and aqi=ari,∀i∈1,Q∖q,r.(iv)
The HMM has two observation values(M=2) and contains a state r that has constant incoming state transition probabilities; that is, air=C and for all k, r has nondominant observation probabilities; that is, brk<bik,∀i∈1,Q∖r,∀k∈1,M.The proof is in AppendixB.


## 3.4. Low-Impact States

Unlike high-impact or equivalent (zero-impact) states, some states have larger-than-zero but very low impact, which makes them hard to learn. Such states are called low-impact states. HMMs containing these states are calledhard to learn HMMs, as will be shown later.Since low-impact states are in between high-impact and equivalent states, they meet a combination of partial conditions defined for both cases. As introduced in Section3.2 for high-impact states, a learnable HMMs should contain onlypersistent and/ortransient-cyclic states withprivileged observations, while an unlearnable HMMs contains states which contains one or two states under conditions defined in Theorem 10. Therefore, combined partial conditions of both can be defined forhard to learn HMMs.An HMM ishard to learn if it contains mostlypersistent ortransient-cyclic states withprivileged states with dominant observations and is also under one of the following conditions:(i)
There exists a mixing stater whose observation distribution is a mixture of the observation distributions of two other states q and k; that is, brj=(bqj+bkj)/2, where q,r,k∈1,Q,∀j∈1,M.(ii)
There exists a stater with constant incoming transitions, self-included; that is, air=1/Q, where r∈1,Q,∀i∈1,Q.(iii)
There exists a stater with constant incoming transitions, self-excluded; that is, air=1-arr/Q-1, where r∈1,Q,∀i∈1,Q∖r.(iv)
There exists a stater with constant outgoing transitions, self-included; that is, ari=1/Q, where r∈1,Q,∀i∈1,Q.(v)
There exists a stater with constant outgoing transitions, self-excluded; that is, ari=1-arr/Q-1, where r∈1,Q,∀i∈1,Q∖r.(vi)
There exist two statesq and r with the same observation probabilities bqj=brj, where q,r∈1,Q,∀j∈1,M.(vii)
There exists a stater with constant (nondominant) observation emissions; that is, brj≅1/M, where r∈1,Q,∀j∈1,M.


## 4. Approximate Identification Algorithm

An HMM is either identifiable or unidentifiable. In order to describe how hard it is to identify a model, we use the termlearnability: for an identifiable HMM, it can be easy, moderate, or hard to learn. Thus, before presenting the approximate identification algorithm, we firstly explain our hypothesis on the correlations between model learnability and specificity as shown in Figure 2, which will be validated experimentally in Section 5. HMMs containing states with higher specificity have higher distances with less complex models and as shown later are easier to learn, and vice versa. Therefore, we classify HMMs into three identification categories based on their specificity: (1)learnable HMMs with relatively high specificity; (2)hard to learn HMMs with low specificity; and (3)unlearnable HMMs with almost zero specificity. Our focus is to identify learnable and highly specific models with high-impact states.Figure 2
Learnability versus specificity of HMMs.


### 4.1. Algorithm Structure

Based on the previous analysis of the hidden states, we can construct an algorithm that identifies high-impact states directly from the observation sequences. Inspired by signal processing method such as Empirical Mode Decomposition- (EMD-) and wavelet-based denoising methods [25], which decompose the noisy signal into a number of components, filter each component, and finally reconstruct the denoised signal using the filtered components, here we reassemble the above procedures as follows: an unknown HMM is composed out of a number of hidden states. These states can be identified from observations and combined to form a reconstructed HMM∗, as shown in Figure 3. In such manner, we decompose the model identification procedure into a combination of state identifications. The approximate state identification approach firstly recognizes persistent and transient states separately from observation sequences, then combines them into a set of identified states, and finally reduces or merges similar states into a new set of reconstructed states. The details of the identification framework will be explained as follows.Figure 3
Identification of HMMs.Models with high-impact states generate specific samples which are unique. Therefore, the states are identifiable through data analysis. The output of apersistent state is likely to stay in a period within which the behavior at each time step is “similar," which we call aregime. Thus a segmentation approach is advised splitting a signal sequence into regimes by identifying the specific behaviors within certain periods. In order to identifytransient-cyclic states, our approach is to capture the changing of behaviors with a transient analysis based on Theorem 9.Therefore, we propose a framework to identify most high-impact and minimal states: (1) persistent privileged states; (2) transient-cyclic privileged states; and (3) hybrid: persistent and transient-cyclic privileged states. A schema of the proposed algorithm is shown in Figure4. We assume that both persistent and transient states exist in the model; therefore, both segmentation and clustering and transient analysis methods are applied on the data, followed by a reparameterization procedure to combine the parameters learned from both the previous methods. Finally, a model reduction step is conducted in the end to form a simplified minimal HMM model. We name our proposed method as Segmentation-Clustering and Transient analysis (SCT) framework.Figure 4
Scheme of the proposed approach.


### 4.2. Segmentation-Based Approach

The segmentation-based approach is defined using the following steps: Step1: signals are split by segmentation techniques into different regimes with different signal behaviors; Step 2: the “similar” regimes of signals are grouped together by clustering techniques according to their similarities (the clusters are labeled and each cluster is a hidden state); Step 3: a clustering validation index is employed to determine the proper number of states; finally, Step 4: HMM parameters are estimated by calculating statistical occurrences of the observations and the estimated hidden states.Step 1 (identification of persistent states by segmentation).
Data sequences emitted bypersistent states can be segmented into subsequences with constant behavior (observations are drawn from a stationary distribution). The transition from one state to another can be identified by detecting a difference in signal behavior. This is called achange point. In this paper, we propose a sliding window-based Bayesian segmentation based on the test of [26]. The Bayesian probability is calculated to determine whether two sequences have been generated by the same or by a different multinomial model.
Amultinomial model is a stochastic process where the observations follow a multinomial distribution. It is sufficient to model observations instead of states, since the observations in a multinomial model can represent states correspondingly with absolute state knowledge. Each observed symbol ot at time t is independent and falls into one of N categories with a fixed probability, denoted by P=p1,p2,…,pN, where ∑i=1Npi=1. The observation probability distribution is denoted by π=P(ot=si)∈P, where si∈S,S=s1,s2,…,sN,1≤t≤T. The model can be represented with a compact notation λ=(π).
The first sequence always starts from the last change point (the first point if at the beginning) and ends at the current time point; the second sequence is a fixed-length sliding window starting from the next time point. If the two successive sequences are very likely from different models, the point in between is marked as a change point. The procedure repeats until the end of the signal.Step 2 (combination of states by clustering).
With HMMs, segments corresponding to the same state will recur over time. Assuming that there is a finite number of states, segments with the same states are detected and clustered together. In this study, the classicalk-means clustering approach [27, 28] is chosen to group and label segments. In our case, the k-means clustering algorithm tries to group the segments into k unique states based on the mean value of data features within each cluster, given by k. Because of the fact that k-means clustering encounters the problem of randomness in selecting initial parameters, we perform a preliminary step for selecting centroid starting locations. The selected properties in the segmentation step are a one-dimension sequence, which contains k subsequences with equal length. The median values of the subsequences are then used as initial centroid locations.Step 3 (cluster validity).
In order to select the optimal number of clusters, we propose a constraint-based clustering analysis considering both the cluster separation capabilities of hidden states and the simplicity of HMM models.Constraint 1: lower Davies-Bouldin index (DBI) [29] suggests that the clustering exhibited a better intracluster grouping and intercluster separation of each state.Constraint 2: instead of selecting the minimum DBI, an allowance with a threshold of 0.05 is given so that a smaller number of states will be selected if its DBI is within the range of min⁡(DBI)+0.05.
Suppose datasetX is partitioned into K disjoint nonempty clusters Ci and let C1,C2,…,CK denote the obtained partitions, such that Ci∩Cj=∅ (empty set), i≠j,Ci≠∅, and X=⋃i=1KCi. The Davies-Bouldin index [29] is defined as(15)DBI=1K∑i=1Kmaxi≠j⁡diam⁡⁡Ci+diam⁡⁡Cjdist⁡⁡Ci,Cj,where(16)diam⁡⁡Ci=maxxm,xn∈Ci⁡dxm,xn,dist⁡⁡Ci,Cj=minxm∈Ci,xn∈Cj,i≠j⁡dxm,xnindicate the intracluster diameter and the intercluster distance, respectively. The partition with the minimum Davies-Bouldin index is considered as the optimal choice.Step 4 (parameter estimations).
Parameters of an HMM (i.e., probability matricesλpers=(πpers,Apers,Bpers)) can be calculated by simply counting the occurrence of the observed signal and the hidden states (i.e., labels retrieved from clustering), which is the same calculation as the reestimation step of the Baum-Welch algorithm [1]:(17)π¯i=expected  frequency  (number  of  times)  in  statesiat  timet  =  1,a¯ij=expected  number  of  transitions  fromsitosjexpected  number  of  transitions  fromsi,b¯jk=expected  number  of  times  insjobservingvkexpected  number  of  times  insj.


### 4.3. Transition-Based Approach

In this section we present a transition-based approach in order to identify transient-cyclic states. In order to estimate the observation matrix, we apply Theorem9 which is dedicated to identifying transient-cyclic privileged with or without mixing states. Firstly, the first-order transition probabilities can be identified by a Markov model assumption via counting the occurrence of the observation sequences:(18)P¯ot=vk,ot+1=vl=expected  number  of  transitions  fromvktovlexpected  total  number  of  1-order  transitions.Similarly, a second-order transition probability can be modelled by an HMM assumption and calculated by counting:(19)P¯ot=vk,ot+1=vl,ot+2=vm=expected  number  of  transitions  fromvktovltovmexpected  total  number  of  2-order  transitions,where k,l,m∈1,M,k≠l≠m. A threshold for dominant probabilities is calculated as(20)ξ¯=1expected  total  number  of  1-order  transitions.If the two continuous first-order probabilities are dominant, that is, P¯(ot=vk,ot+1=vl)>ξ¯ and P¯(ot+1=vl,ot+2=vm)>ξ¯, where 0≤ξ¯≤1, then the division of the second-order transition probabilities calculated from a Markov chain and from an HMM assumption is(21)ħ¯=P¯ot=vk,ot+1=vlP¯ot+1=vl,ot+2=vmP¯ot=vk,ot+1=vl,ot+2=vm.If ħ¯=1, there is no transient-cyclic states. Otherwise, the first-order transition probabilities are taken as the dominant observation probabilities and used to build the observation matrix. If ħ¯>1, a mixing state is present and one extra state is added to the observation matrix with a uniformly distributed probability of 1/M. In the end, we map each observation value vk, vl, and vmon a different state because we look for states with at least one dominant observation value. If a state has multiple observation values, they will be merged into one state. See Table 1 for conditions of model state reduction.Take a simple 2-observation case as an example; we generate a 10-series sequence with length of 1000. The first-order observation transition probabilities areP(ot=v1,ot+1=v1)P(ot=v1,ot+1=v2)P(ot=v2,ot+1=v1)P(ot=v2,ot+1=v2). If the calculated occurrence probabilities are 0.46030.04200.04220.4555, the dominant transitions larger than 1/4 are P(ot=v1,ot+1=v1) and P(ot=v2,ot+1=v2). Thus, the dominant second-order probabilities are P(ot=v1,ot+1=v1,ot+2=v1)P(ot=v2,ot+1=v2,ot+2=v2), equal to 0.42170.4170 calculated by a Markov model, while being equal to 0.43360.4269 calculated by an HMM. Thus, the division of the two is ħ=0.97250.9768. Since both probabilities are smaller than 1, they are dominant states and there is no mixing state. Therefore, we map the two dominant probabilities to the observation probabilities of two states and the final observation matrix is Btran⁡=0.97250.02750.02320.9768.Furthermore, for calculating the prior and transition probabilities, we stick to the assumption that privileged state behaviors can be reflected by observation properties; therefore, we assume the number of states is the same as the number of observations and use a Markov model for learning state probabilities.The prior and transition matrices can be calculated by counting the observation occurrences:(22)π¯i=expected  frequency  (number  of  times)  in  observationviat  timet=1,a¯ij=expected  number  of  transitions  fromvitovjexpected  number  of  transitions  fromvi.Therefore, a model λtran⁡=(πtran⁡,Atran⁡,Btran⁡) is learned containing only transient-cyclic states.


### 4.4. Reparameterization

Parameters learned for bothpersistent andtransient-cyclic states are combined together by a procedure calledreparameterization. Let λpers=(πpers,Apers,Bpers) be the parameters forpersistent states and λtran⁡=(πtran⁡,Atran⁡,Btran⁡) be the parameters for thetransient-cyclic states. Let Qpers and Qtran⁡ be the number ofpersistent andtransient-cyclic states, respectively. Thus the combined number of states is Q′=Qpers+Qtran⁡. The parameters of the combined model λ′π′,A′,B′ can be calculated as(23)π′=Normalizeπpersπtran⁡N′×1,A′=Stochastic1Q′∗1Q′×Q′+Apers0Qpers×Qtran⁡0Qtran⁡×QpersAtran⁡Q′×Q′,B′=StochasticBpersBtran⁡Q′×M,where the functionNormalize ensures that the sum of the given vectors equals 1 and theStochastic function ensures that the sum of each row of the given matrix equals 1.


### 4.5. Model Reduction

After combining the persistent and transient-cyclic states, redundant states may occur. We introduce a model reduction procedure which removes redundant states to obtain minimal HMMs according to the conditions defined in Theorem10. We relax the strict conditions given in the theorem via adding thresholds.(i)
An HMM contains a staterthat has zero incoming state transition probabilities; that is,air=0,∀i∈1,Q.Instead of using a zero vector as a strict rule, a threshold is defined to allow near-zero cases such that if the sum of the incoming transition state probabilities of stater is lower than threshold θa, that is,(24)∑i=1Qair<θa,the stater can be removed.(ii)
An HMM contains two statesqandrthat have the same state transition probabilities; that is,aiq=airandaqi=ari,∀i∈1,Q.We replace the equivalence condition by a subtraction calculation. If the maximum of the incoming and outgoing state transition probabilities of the two statesq and r is below a threshold θb, that is,(25)max⁡max1≤i≤Q⁡aiq-air,max1≤i≤Q⁡aqi-ari<θb,the two states can be merged into one.(iii)
An HMM contains two statesqandrthat have the same observation probabilitiesbqk=brk,∀k∈1,M,and meet one of the following conditions: (1) they have the same incoming state transition probabilities; that is,aiq=air,∀i∈1,Q; (2) they have the same outgoing state transition probabilities; that is,aqi=ari,∀i∈1,Q; or (3)aiq=airandaqi=ari,∀i∈1,Q∖q,r.Similar to (ii), we use subtraction instead of strict equivalence with added thresholdθc. Moreover, theAND condition and theOR conditions can be represented by selecting the maximum and minimum values, respectively. Therefore, if(26)max⁡max1≤k≤M⁡bqk-brk,minmax1≤i≤Q⁡aiq-air,max1≤i≤Q⁡aqi-ari,maxmax1≤i≤Qi≠r≠q⁡aiq-air,max1≤i≤Qi≠r≠q⁡aqi-ari<θc,∀i∈1,Q,the two statesq and r can be merged.(iv)
An HMM has two observation values(M=2)and contains a staterthat has constant incoming state transition probabilities,air=Cand∀k, andrhas nondominant observation probabilities,brk<bik,∀i∈1,Q∖r,∀k∈1,M.(27)max1≤i≤Q⁡air-a¯ir<θd,brk=min1≤k≤M⁡bik,∀i∈1,Q,wherea¯ir is the average of air and the state r can be “taken over.”The selection of thresholds is conducted empirically since the correlation between the likelihood value and each condition is complex and is not our focus in this paper.


## 4.1. Algorithm Structure

Based on the previous analysis of the hidden states, we can construct an algorithm that identifies high-impact states directly from the observation sequences. Inspired by signal processing method such as Empirical Mode Decomposition- (EMD-) and wavelet-based denoising methods [25], which decompose the noisy signal into a number of components, filter each component, and finally reconstruct the denoised signal using the filtered components, here we reassemble the above procedures as follows: an unknown HMM is composed out of a number of hidden states. These states can be identified from observations and combined to form a reconstructed HMM∗, as shown in Figure 3. In such manner, we decompose the model identification procedure into a combination of state identifications. The approximate state identification approach firstly recognizes persistent and transient states separately from observation sequences, then combines them into a set of identified states, and finally reduces or merges similar states into a new set of reconstructed states. The details of the identification framework will be explained as follows.Figure 3
Identification of HMMs.Models with high-impact states generate specific samples which are unique. Therefore, the states are identifiable through data analysis. The output of apersistent state is likely to stay in a period within which the behavior at each time step is “similar," which we call aregime. Thus a segmentation approach is advised splitting a signal sequence into regimes by identifying the specific behaviors within certain periods. In order to identifytransient-cyclic states, our approach is to capture the changing of behaviors with a transient analysis based on Theorem 9.Therefore, we propose a framework to identify most high-impact and minimal states: (1) persistent privileged states; (2) transient-cyclic privileged states; and (3) hybrid: persistent and transient-cyclic privileged states. A schema of the proposed algorithm is shown in Figure4. We assume that both persistent and transient states exist in the model; therefore, both segmentation and clustering and transient analysis methods are applied on the data, followed by a reparameterization procedure to combine the parameters learned from both the previous methods. Finally, a model reduction step is conducted in the end to form a simplified minimal HMM model. We name our proposed method as Segmentation-Clustering and Transient analysis (SCT) framework.Figure 4
Scheme of the proposed approach.


## 4.2. Segmentation-Based Approach

The segmentation-based approach is defined using the following steps: Step1: signals are split by segmentation techniques into different regimes with different signal behaviors; Step 2: the “similar” regimes of signals are grouped together by clustering techniques according to their similarities (the clusters are labeled and each cluster is a hidden state); Step 3: a clustering validation index is employed to determine the proper number of states; finally, Step 4: HMM parameters are estimated by calculating statistical occurrences of the observations and the estimated hidden states.Step 1 (identification of persistent states by segmentation).
Data sequences emitted bypersistent states can be segmented into subsequences with constant behavior (observations are drawn from a stationary distribution). The transition from one state to another can be identified by detecting a difference in signal behavior. This is called achange point. In this paper, we propose a sliding window-based Bayesian segmentation based on the test of [26]. The Bayesian probability is calculated to determine whether two sequences have been generated by the same or by a different multinomial model.
Amultinomial model is a stochastic process where the observations follow a multinomial distribution. It is sufficient to model observations instead of states, since the observations in a multinomial model can represent states correspondingly with absolute state knowledge. Each observed symbol ot at time t is independent and falls into one of N categories with a fixed probability, denoted by P=p1,p2,…,pN, where ∑i=1Npi=1. The observation probability distribution is denoted by π=P(ot=si)∈P, where si∈S,S=s1,s2,…,sN,1≤t≤T. The model can be represented with a compact notation λ=(π).
The first sequence always starts from the last change point (the first point if at the beginning) and ends at the current time point; the second sequence is a fixed-length sliding window starting from the next time point. If the two successive sequences are very likely from different models, the point in between is marked as a change point. The procedure repeats until the end of the signal.Step 2 (combination of states by clustering).
With HMMs, segments corresponding to the same state will recur over time. Assuming that there is a finite number of states, segments with the same states are detected and clustered together. In this study, the classicalk-means clustering approach [27, 28] is chosen to group and label segments. In our case, the k-means clustering algorithm tries to group the segments into k unique states based on the mean value of data features within each cluster, given by k. Because of the fact that k-means clustering encounters the problem of randomness in selecting initial parameters, we perform a preliminary step for selecting centroid starting locations. The selected properties in the segmentation step are a one-dimension sequence, which contains k subsequences with equal length. The median values of the subsequences are then used as initial centroid locations.Step 3 (cluster validity).
In order to select the optimal number of clusters, we propose a constraint-based clustering analysis considering both the cluster separation capabilities of hidden states and the simplicity of HMM models.Constraint 1: lower Davies-Bouldin index (DBI) [29] suggests that the clustering exhibited a better intracluster grouping and intercluster separation of each state.Constraint 2: instead of selecting the minimum DBI, an allowance with a threshold of 0.05 is given so that a smaller number of states will be selected if its DBI is within the range of min⁡(DBI)+0.05.
Suppose datasetX is partitioned into K disjoint nonempty clusters Ci and let C1,C2,…,CK denote the obtained partitions, such that Ci∩Cj=∅ (empty set), i≠j,Ci≠∅, and X=⋃i=1KCi. The Davies-Bouldin index [29] is defined as(15)DBI=1K∑i=1Kmaxi≠j⁡diam⁡⁡Ci+diam⁡⁡Cjdist⁡⁡Ci,Cj,where(16)diam⁡⁡Ci=maxxm,xn∈Ci⁡dxm,xn,dist⁡⁡Ci,Cj=minxm∈Ci,xn∈Cj,i≠j⁡dxm,xnindicate the intracluster diameter and the intercluster distance, respectively. The partition with the minimum Davies-Bouldin index is considered as the optimal choice.Step 4 (parameter estimations).
Parameters of an HMM (i.e., probability matricesλpers=(πpers,Apers,Bpers)) can be calculated by simply counting the occurrence of the observed signal and the hidden states (i.e., labels retrieved from clustering), which is the same calculation as the reestimation step of the Baum-Welch algorithm [1]:(17)π¯i=expected  frequency  (number  of  times)  in  statesiat  timet  =  1,a¯ij=expected  number  of  transitions  fromsitosjexpected  number  of  transitions  fromsi,b¯jk=expected  number  of  times  insjobservingvkexpected  number  of  times  insj.


## 4.3. Transition-Based Approach

In this section we present a transition-based approach in order to identify transient-cyclic states. In order to estimate the observation matrix, we apply Theorem9 which is dedicated to identifying transient-cyclic privileged with or without mixing states. Firstly, the first-order transition probabilities can be identified by a Markov model assumption via counting the occurrence of the observation sequences:(18)P¯ot=vk,ot+1=vl=expected  number  of  transitions  fromvktovlexpected  total  number  of  1-order  transitions.Similarly, a second-order transition probability can be modelled by an HMM assumption and calculated by counting:(19)P¯ot=vk,ot+1=vl,ot+2=vm=expected  number  of  transitions  fromvktovltovmexpected  total  number  of  2-order  transitions,where k,l,m∈1,M,k≠l≠m. A threshold for dominant probabilities is calculated as(20)ξ¯=1expected  total  number  of  1-order  transitions.If the two continuous first-order probabilities are dominant, that is, P¯(ot=vk,ot+1=vl)>ξ¯ and P¯(ot+1=vl,ot+2=vm)>ξ¯, where 0≤ξ¯≤1, then the division of the second-order transition probabilities calculated from a Markov chain and from an HMM assumption is(21)ħ¯=P¯ot=vk,ot+1=vlP¯ot+1=vl,ot+2=vmP¯ot=vk,ot+1=vl,ot+2=vm.If ħ¯=1, there is no transient-cyclic states. Otherwise, the first-order transition probabilities are taken as the dominant observation probabilities and used to build the observation matrix. If ħ¯>1, a mixing state is present and one extra state is added to the observation matrix with a uniformly distributed probability of 1/M. In the end, we map each observation value vk, vl, and vmon a different state because we look for states with at least one dominant observation value. If a state has multiple observation values, they will be merged into one state. See Table 1 for conditions of model state reduction.Take a simple 2-observation case as an example; we generate a 10-series sequence with length of 1000. The first-order observation transition probabilities areP(ot=v1,ot+1=v1)P(ot=v1,ot+1=v2)P(ot=v2,ot+1=v1)P(ot=v2,ot+1=v2). If the calculated occurrence probabilities are 0.46030.04200.04220.4555, the dominant transitions larger than 1/4 are P(ot=v1,ot+1=v1) and P(ot=v2,ot+1=v2). Thus, the dominant second-order probabilities are P(ot=v1,ot+1=v1,ot+2=v1)P(ot=v2,ot+1=v2,ot+2=v2), equal to 0.42170.4170 calculated by a Markov model, while being equal to 0.43360.4269 calculated by an HMM. Thus, the division of the two is ħ=0.97250.9768. Since both probabilities are smaller than 1, they are dominant states and there is no mixing state. Therefore, we map the two dominant probabilities to the observation probabilities of two states and the final observation matrix is Btran⁡=0.97250.02750.02320.9768.Furthermore, for calculating the prior and transition probabilities, we stick to the assumption that privileged state behaviors can be reflected by observation properties; therefore, we assume the number of states is the same as the number of observations and use a Markov model for learning state probabilities.The prior and transition matrices can be calculated by counting the observation occurrences:(22)π¯i=expected  frequency  (number  of  times)  in  observationviat  timet=1,a¯ij=expected  number  of  transitions  fromvitovjexpected  number  of  transitions  fromvi.Therefore, a model λtran⁡=(πtran⁡,Atran⁡,Btran⁡) is learned containing only transient-cyclic states.


## 4.4. Reparameterization

Parameters learned for bothpersistent andtransient-cyclic states are combined together by a procedure calledreparameterization. Let λpers=(πpers,Apers,Bpers) be the parameters forpersistent states and λtran⁡=(πtran⁡,Atran⁡,Btran⁡) be the parameters for thetransient-cyclic states. Let Qpers and Qtran⁡ be the number ofpersistent andtransient-cyclic states, respectively. Thus the combined number of states is Q′=Qpers+Qtran⁡. The parameters of the combined model λ′π′,A′,B′ can be calculated as(23)π′=Normalizeπpersπtran⁡N′×1,A′=Stochastic1Q′∗1Q′×Q′+Apers0Qpers×Qtran⁡0Qtran⁡×QpersAtran⁡Q′×Q′,B′=StochasticBpersBtran⁡Q′×M,where the functionNormalize ensures that the sum of the given vectors equals 1 and theStochastic function ensures that the sum of each row of the given matrix equals 1.


## 4.5. Model Reduction

After combining the persistent and transient-cyclic states, redundant states may occur. We introduce a model reduction procedure which removes redundant states to obtain minimal HMMs according to the conditions defined in Theorem10. We relax the strict conditions given in the theorem via adding thresholds.(i)
An HMM contains a staterthat has zero incoming state transition probabilities; that is,air=0,∀i∈1,Q.Instead of using a zero vector as a strict rule, a threshold is defined to allow near-zero cases such that if the sum of the incoming transition state probabilities of stater is lower than threshold θa, that is,(24)∑i=1Qair<θa,the stater can be removed.(ii)
An HMM contains two statesqandrthat have the same state transition probabilities; that is,aiq=airandaqi=ari,∀i∈1,Q.We replace the equivalence condition by a subtraction calculation. If the maximum of the incoming and outgoing state transition probabilities of the two statesq and r is below a threshold θb, that is,(25)max⁡max1≤i≤Q⁡aiq-air,max1≤i≤Q⁡aqi-ari<θb,the two states can be merged into one.(iii)
An HMM contains two statesqandrthat have the same observation probabilitiesbqk=brk,∀k∈1,M,and meet one of the following conditions: (1) they have the same incoming state transition probabilities; that is,aiq=air,∀i∈1,Q; (2) they have the same outgoing state transition probabilities; that is,aqi=ari,∀i∈1,Q; or (3)aiq=airandaqi=ari,∀i∈1,Q∖q,r.Similar to (ii), we use subtraction instead of strict equivalence with added thresholdθc. Moreover, theAND condition and theOR conditions can be represented by selecting the maximum and minimum values, respectively. Therefore, if(26)max⁡max1≤k≤M⁡bqk-brk,minmax1≤i≤Q⁡aiq-air,max1≤i≤Q⁡aqi-ari,maxmax1≤i≤Qi≠r≠q⁡aiq-air,max1≤i≤Qi≠r≠q⁡aqi-ari<θc,∀i∈1,Q,the two statesq and r can be merged.(iv)
An HMM has two observation values(M=2)and contains a staterthat has constant incoming state transition probabilities,air=Cand∀k, andrhas nondominant observation probabilities,brk<bik,∀i∈1,Q∖r,∀k∈1,M.(27)max1≤i≤Q⁡air-a¯ir<θd,brk=min1≤k≤M⁡bik,∀i∈1,Q,wherea¯ir is the average of air and the state r can be “taken over.”The selection of thresholds is conducted empirically since the correlation between the likelihood value and each condition is complex and is not our focus in this paper.


## 5. Experiments

Simulated data has been used to evaluate the effectiveness and efficiency of the proposed SCT inference framework. The simulated data were sampled from different classes of HMM models: nonminimal equivalent HMMs, identifiable (selected and random) minimal HMMs, and hard to learn HMMs.


### 5.1. Nonminimal Equivalent HMMs

Equivalent HMMs contains two cases: (1) two HMMs with the same number of states, where permutations of states apply to both models; (2) two HMMs with different numbers of states. This experiment focuses on case (2) and aims to test the model reduction conditions defined in Table1, where a nonminimal HMM can remove, merge, or take over its redundant states to become an equivalent minimal HMM. One model λ is selected under each of the three reduction conditions and is used to construct an equivalent model λ~ by removing the redundant state (set as the last state here). The model parameters are listed hereafter, respectively:With aremovable state:
HMMλ1:(28)π1=0.330.330.33,A1=0.90.100.10.900.50.50,B1=0.90.050.050.050.90.050.050.050.9HMMλ~1:(29)π~1=0.50.5,A~1=0.90.10.10.9,B~1=0.90.050.050.050.90.05With amergeable state:
HMMλ2:(30)π2=0.330.330.33,A2=0.450.450.10.450.450.10.050.050.9,B2=0.90.050.050.050.90.050.050.050.9HMMλ~2:(31)π~2=0.670.33,A~2=0.90.10.10.9,B~2=0.4750.4750.050.050.050.9With ataken-over state:
HMMλ3:(32)π3=0.330.330.33,A3=0.60.20.20.20.60.20.40.40.2,B3=0.90.10.10.90.50.5HMMλ~3:(33)π~3=0.50.5,A~3=0.7080.2920.2920.708,B~3=0.8330.1670.1670.833Each of the reference nonminimal modelsλi,i=1,2,3 is used to generate 1000 datasets of random observations containing N=20 sequences of T=5000 observation points. The datasets are used to determine log-likelihood distributions of the models and the distance threshold of equivalent models defined in Definition 8. By calculating the percentage of the log-likelihood values of the minimal model λ~i which fall inside the threshold of equivalence for the nonminimal model λi, we can obtain a confidence level. The results in Table 2 show that the two models are approximate equivalent models for all the three cases with high confidence levels. Moreover, the log-likelihood histograms are plotted in Figure 5. The highly overlapping histograms further demonstrate the model equivalence for the three examples.Table 2
Distance threshold test results for nonminimal equivalent models.
Cases Remove Merge Take over Models λ 1 λ ~ 1 λ 2 λ ~ 2 λ 3 λ ~ 3 μ - 0.92 - 0.92 - 1.24 - 1.24 - 0.97 - 0.97 σ 0.012 0.012 0.014 0.014 0.003 0.003 [ μ - 3 σ , μ + 3 σ ] [ - 0.955 , - 0.881 ] [ - 0.955 , - 0.881 ] [ - 1.279 , - 1.191 ] [ - 1.279 , - 1.191 ] [ - 0.978 , - 0.959 ] [ - 0.977 , - 0.960 ] Confidence of equivalence (%) 99.9 99.8 99.8Figure 5
The histogram of log-likelihoods.


### 5.2. Highly Specific HMMs

As discussed previously, persistent and transient-cyclic HMMs with privileged observations are identifiable HMMs that have a high specificity. In this section, we compare the learning of such identifiable HMMs with the Baum-Welch (BW) algorithm and the proposed SCT method.Firstly, we constructed 9 persistent and 9 transient-cyclic models as ground truth models with a fixed equal number of states and observations (Q=M) ranging from 2 to 10. These models can be expressed as follows:Persistentλpers:(34)πpers=1Q1Q⋮1QQ×1,Apers=p1α1α1α1p1α⋱α1α1p1Q×Q,Bpers=p1α1α1α1p1α1⋱α1α1p1Q×QTransient-cyclicλtran⁡:(35)πtran⁡=1Q1Q⋮1QQ×1,Atran⁡=α2p2α2⋱α2α2p2p2α2α2Q×Q,Btran⁡=p2α2α2α2p2α2⋱α2α2p2Q×QThe state self-transition probabilities for persistent models and the transition probabilities to the next neighboring state for transient-cyclic models were both set to a value close to 1, noted asp1 and p2, respectively, where p1,p2∈0.8,0.99. The remaining transitions have equal probabilities; that is, αi=(1-pi)/(Q-1),i=1,2. For all the 18 models, the observation matrices are set the same as the transition matrices of persistent models in order to obtain privileged observations. The initial parameters are uniformly distributed.We also generated 20 hybrid models as ground truth models containing both persistent and transient-cyclic states. The number of statesq1 and q2 for both cases was randomly chosen from 2 to 3, amounting to a total number of states Q=q1+q2 within a range of 4,6. The rest of the parameters were generated in the same manner as before. For simplicity, we use αi to represent a matrix containing only element αi. Thus, a hybrid model can be represented as follows:Hybridλhybr:(36)πhybr=1Q1Q⋮1QQ×1,Ahybr=Apersq1×q1α1q1×q2α2q2×q1Atran⁡q2×q2Q×Q,Bhybr=Bpersq1×q1α1q1×q2α2q2×q1Btran⁡q2×q2Q×QThe experiments were carried out by using each of the constructed models as a reference model to generate a dataset of 10 series of 1000 observations. The first seven series were used as a training set and the last three series as a test set. The true number of statesQ was assumed to be unknown and the learning methods have to select the number of states from a state pool of 2,Q+2. For the BW learning algorithm, Q+1 models were generated with a number of states ranging from 2 to Q+2 and the model with the best Q is selected by the AIC criterion [30]. The learning of the BW algorithm was repeated 20 times to eliminate local optima and the one with the minimum AIC value is selected. In total, 20∗(Q+1) models were generated to determine an optimal model. Moreover, for comparison purpose, we also train BW with a given number of states Q; therefore, a total of 20 models were generated and a best model is selected by the AIC criterion. On the other hand, for the proposed SCT method, the number of states is selected by the clustering validation method in Step 3 (See Section 4.2). Only one SCT model is trained and used for comparison the two best models selected by the BW method (with and without a given Q).In order to use the 3-sigma rule to indicate if a true model is learned, 100 datasets of 10 series of 1000 observations were generated from each of the true models and used for calculating the log-likelihood distributionN(μ,σ) (see Definition 8). If the log-likelihood difference between the ground truth model and the learned model is outside the distance threshold of -3σ,3σ, we consider that the true model has not been found (i.e., a local optimum is learned). Moreover, for better understanding the log-likelihood results, we additionally calculated the log-likelihoods for the following models: (1) λ¯Q-1(λQ): the best model with Q-1 states selected from 100 randomly generated models and trained with BW; (2) λ¯Q-2(λQ): the best model with Q-2 states selected from 100 randomly generated models and trained with BW; (3) a multinomial model: the model assuming that there are no hidden states and the observations are the actual visible states. If an HMM model has similar log-likelihood as a multinomial model, the states have no impact on the model.In addition to log-likelihoods, we define other performance indicators of accuracy as follows: (1) thepercentage of convergence is the percentage of 20 BW learned models which did not fall into a local optimum; (2) thepercentage of identification is the percentage of the best BW or the SCT learned models which did not fall into a local optimum; (3) theparameter distance is defined as the mean difference of the triples (π,A,B) between two HMM models. If the two models have different state space, values of 0s are filled into the probability matrices of the simpler model in order to have an equal number of states to the complex one. Moreover, all the permutations of the models are considered and the minimum distance is chosen as theparameter distance.An average information of the ground truth models can be found in Table3. The hybrid models are less specific than the persistent or transient-cyclic states only models, which make them harder to identify. Detailed learning results can be found in Table 4. The results show that the proposed SCT method learns much faster than the traditional BW algorithm, with a speedup around 180 to 260 times. The BW algorithm tends to overfit the model by using a larger number of states, resulting in a higher parameter distance. Even when the true number of states Q is given, for persistent cases, the BW still cannot learn correctly, which has a larger test-set log-likelihood difference and a lower convergence and identification rate.Table 3
Average characteristics of ground truth HMMs.
Type Specificity Minimal (%) μ ( L L true ) σ ( L L true ) Persistent 0.25 100 - 1.00 0.018 Transient-cyclic 0.32 100 - 1.25 0.017 Hybrid 0.17 100 - 0.93 0.019 Note:μ(LLtrue): mean of the log-likelihood distribution of the true model; σ(LLtrue): standard deviation of the log-likelihood distribution of the true model.Table 4
Identification results on identifiable HMMs.
Type Method # Iters. Time (s) Q select Δ Q Δ L L t e s t Para. Dist. Conv. (%) Identi. (%) Pers. BW 15 1054 Min. AIC 1.67 0.028 0.15 45.56 88.89 CorrectQ 0.00 0.058 0.02 16.11 66.67 SCT 4 4 DBI 0.00 0.012 0.00 — 100  Tran. BW 22 1276 Min. AIC 1.00 0.014 0.08 100 100 CorrectQ 0.00 0.012 0.01 75.56 100 SCT 8 5 DBI 0.00 0.011 0.01 — 100  Hybr. BW 19 891 Min. AIC 1.75 0.008 0.19 88 100 CorrectQ 0.00 0.007 0.00 36.50 100 SCT 10 5 DBI 0.00 0.007 0.00 — 100 # Iters.: average number of iterations; Conv. (%): rate of convergence; Identi. (%): percentage of identification; ΔLLtest: unit log-likelihood difference between the true models and the learned model on test-sets; Para. Dist.: parameter distance; Pers.: Persistent; Tran.: Transient-cyclic; Hybr.: Hybrid. Note that, for the BW, when calculating ΔQ, ΔLLtest, and Para. Dist., the learned model is the best one selected from the 20(Q+1) repeated random models.Learning results for a 10-state persistent model, a 10-state transient-cyclic model, and a 6-state hybrid model are used as examples for visualization. For the persistent model, the iterative learning process is shown in Figures6(a) and 6(b). In Figure 6(a), the BW training was conducted with an unknown number of states Q, while in Figure 6(b), Q was given. Similarly, results for the transient-cyclic model are shown in Figures 7(a) and 7(b). and the hybrid models are in Figures 8(a) and 8(b). The figures show that the proposed SCT method starts from a good initial model at the beginning and converges much faster than most of the 20 randomly initialized BW models which start from an almost equivalent level of the multinomial model for which hidden states play no roles. Moreover, although some of the best BW model converges in the end, the log-likelihood values are still not as good as the SCT method. We see that some of the repeated 20 models with Q states have been stuck in a local optimum with similar log-likelihood to model λ¯Q-1(λQ) or λ¯Q-2(λQ).Figure 6
Identification performance for a 10-state discrete persistent HMM. (a) and (b) show a comparison of log-likelihoods during iterative trainings with different models: the 20 repetitive BW models with an unknown or known number of statesQ, the SCT models, the selected best BW models without or with a given Q, the ground truth HMM, the multinomial model, the best one-state simpler model λ¯Q-1(λQ), and the best two-state simpler model λ¯Q-2(λQ). (c) shows a comparison of the model parameter heat maps for the ground truth HMM, the best BW models with an unknown or a given Q, and the SCT model.
(a)
Log-likelihoods during iterative training, BW with unknownQ (b)
Log-likelihoods during iterative training, BW given correctQ (c)
Heatmap of HMM model parametersFigure 7
Identification performance for a 10-state discrete transient-cyclic HMM. See caption of Figure6 for more details.
(a)
Log-likelihoods during iterative training, BW with unknownQ (b)
Log-likelihoods during iterative training, BW given correctQ (c)
Heatmap of HMM model parametersFigure 8
Identification performance for a 7-state discrete hybrid HMM. See the caption of Figure6 for more details.
(a)
Log-likelihoods during iterative training, BW with unknownQ (b)
Log-likelihoods during iterative training, BW given correctQ (c)
Heat map of HMM model parametersIn order to compare the model parameters, heat maps of the original and inferred state transition and observation matrices are plotted in Figures6(c), 7(c), and 8(c). A lighter color indicates a higher probability value close to one, while a darker color indicates a lower probability value close to zero. We notice that the BW method with an unknown Q learns a complex model with two more states than the true model for all the three cases, which is overfitting, while the SCT approach learns the state size correctly. Moreover, the SCT method has a one-to-one correspondence of the high probabilities (in white/light-yellow) between the transition and observation parameter matrices, meaning the SCT trained model is almost equivalent to the reference true model. However, for the BW method, especially when Q is unknown, there are no one-to-one relations in both transition and observation matrices, noticeable by some of the varied colors of heat maps from the true model. It means that some of the probabilities are wrongly learned.


### 5.3. Hard to Learn HMMs

For each of the seven hard to learn conditions defined in Section3.4, we construct five ground truth models, resulting in a total of 35 models. For each model, persistent and transient-cyclic state numbers are randomly generated from a range of 3,5. The privileged state probability is set randomly within a range of 0.85,0.99. The remaining probabilities are uniformly distributed. For conditions (ii), (iii), (iv), and (v), one extra state is generated accordingly to the specified conditions. For condition (i), state 3 is defined as a mixing state of states 1 and 2. For condition (vi), the first two states are set to have the same observations. For condition (vii), state 2 is set to have a constant observation emission probabilities. The rest of the experiment is set the same as previous experiments designed for identifiable models. Results show that only 31% of the 35 ground truth models are specific with an average specificity of 0.04. A detailed comparison of the learning results is presented in Table 5.Table 5
Identification results on hard to learn HMMs.
Method # Iters. Time (s) Q select Δ Q Δ L L t e s t Para. Dist. Conv. (%) Identi. (%) BW 26 1835 Min. AIC 1.71 0.014 0.14 87.14 100 CorrectQ 0.00 0.013 0.03 52.00 100 SCT 15 8 DBI - 0.66 0.030 0.11 — 97.14 See abbreviations and notes in Table4 for more details.From the results in Table5 we can see that the BW algorithm is slower than the proposed SCT method with almost double learning convergence iterations. The SCT method is around 230 times faster than the BW algorithm. A positive average delta Q indicates that the BW method mostly overfits the true models with an average of 1.71 extra states, while the SCT has a negative delta Q indicating a slightly underfitting with an average of 0.66 fewer states. Even though the test-set log-likelihood difference of the SCT is higher than the BW method, the average parameter distance further proves that the BW algorithm tends to overfit the models in order to have a lower log-likelihood. Moreover, the percentage of convergence reveals that the number of repetitions (e.g., 20 times in this experiment) is still necessary for the BW method to learn effectively, even with the trade-off of longer learning time. Lastly, the SCT has a slightly lower but compatible identification percentage which has a significant learning speedup in return.To visualize the results, we select two models under condition (i), a state being a mixing state, and condition (v), a state with constant self-excluded outgoing transaction, as examples shown in Figures9 and 10, respectively.Figure 9
Identification performance for a 6-state hard to learn HMM under condition (i). See caption of Figure6 for more details.
(a)
Log-likelihoods during iterative training, BW with unknownQ (b)
Log-likelihoods during iterative training, BW given correctQ (c)
Heatmap of HMM model parametersFigure 10
Identification performance for an 8-state hard to learn HMM under condition (v). See caption of Figure6 for more details.
(a)
Log-likelihoods during iterative training, BW with unknownQ (b)
Log-likelihoods during iterative training, BW given correctQ (c)
Heatmap of HMM model parametersFigures9 and 10 show that the BW algorithm with an unknown Q overfits the truth models with two extra states while the SCT method underfits the model with one state fewer where both the mixing state and the state with the same outgoing transactions in the two examples are merged into other states because they are not specific enough to be identified.


### 5.4. Random HMMs

In this experiment, we generated 10000 random HMM models configured with a combination of randomQ(Q∈3,5) and random M(M∈3,5). In order to guarantee that each HMM is minimal, we select models according to two criteria: (1) the model should have a higher test-set log-likelihood than the one of a multinomial model; (2) the model compared to the best Q-1 state model should not satisfy the three-sigma rule for model equivalence criteria defined in Definition 8. A random HMM is discarded if it is not minimal. In the end, we obtain 149 specific minimal HMMs. The training procedure is conducted in the same way as in Section 5.2.Experiment shows that the average specificity of the true models is 0.03, which is around 10 times less specific than the identifiable models used in the previous experiments in Section5.2. Moreover, the mean of the log-likelihood distribution of the true model is 1.58, which is also much higher than the identifiable models. The above results indicate that random models are less specific and therefore less identifiable. A detailed comparison of the identification results is shown in Table 6.Table 6
Identification results on random minimal HMMs.
Method # Iters. Time (s) Q select Δ Q ΔLLtest Para. Dist. Conv. (%) Identi. (%) BW 17 348 Min. AIC 1.16 0.0019 0.21 93.83 100 CorrectQ 0.00 0.0018 0.05 46.64 100 SCT 18 7 DBI 1.70 0.0051 0.22 — 87.92 See abbreviations and notes in Table4 for more details.The results show that the SCT method needs in average one more iteration than the BW algorithm and the identification results are less adequate because the models are not specific enough to be estimated correctly. However, the speedup of the SCT method shows an improvementvis-a-vis the Baum-Welch method, around 50 times. Both of the approaches overfit the models with an average of more than one state.Figure11(a) provides the dependence between true modelspecificity and test-setlog-likelihood difference with the true models. When the specificity is too low, the SCT method identifies less correctly the models. Thus, the less specific the model is, the harder it becomes for the SCT method to learn. For the purpose of comparison, we plot the same figure in Figure 11(b) but for highly specific models which were generated in Section 5.2. The results further confirm that, for highly specific models, when the specificity is relatively low, the SCT method outperforms the BW method. The log-likelihood differences of the models learned by Baum-Welch have significantly increased indicating that completely wrong models are learned.Figure 11
Specificity versus log-likelihood difference with ground truth model. (a) Random specific models generated in Section5.4. (b) Highly specific models generated in Section 5.2.
(a) (b)The results are expected because the SCT method is designed for highly specific models but not for random ones with less specificity. In order to see the influence of specificity for the SCT method to learn correctly, we plot the identification accuracy versus the specificity thresholds ranging from −0.01 to 0.2 with a step of 0.01 as shown in Figure12. The models are selected when they have a specificity higher than a specificity threshold; then the percentage of correctly identified models within the selected models is used as the identification accuracy.Figure 12
Correlation between specificity threshold and identification accuracy.The identification accuracy of the SCT method starts with a low value of 87.9% and generally increases with an increase specificity threshold. When the specificity threshold is at 0.06, the identification percentage of the SCT drops to 93.8%. It is caused by a single case which is observable in Figure11(a) with the highest log-likelihood difference. Such case cannot represent the dependency trend between specificity threshold and identification accuracy and thus can be ignored. When the threshold is higher than 0.06, the proposed SCT method converges to an identification of 100%.


## 5.1. Nonminimal Equivalent HMMs

Equivalent HMMs contains two cases: (1) two HMMs with the same number of states, where permutations of states apply to both models; (2) two HMMs with different numbers of states. This experiment focuses on case (2) and aims to test the model reduction conditions defined in Table1, where a nonminimal HMM can remove, merge, or take over its redundant states to become an equivalent minimal HMM. One model λ is selected under each of the three reduction conditions and is used to construct an equivalent model λ~ by removing the redundant state (set as the last state here). The model parameters are listed hereafter, respectively:With aremovable state:
HMMλ1:(28)π1=0.330.330.33,A1=0.90.100.10.900.50.50,B1=0.90.050.050.050.90.050.050.050.9HMMλ~1:(29)π~1=0.50.5,A~1=0.90.10.10.9,B~1=0.90.050.050.050.90.05With amergeable state:
HMMλ2:(30)π2=0.330.330.33,A2=0.450.450.10.450.450.10.050.050.9,B2=0.90.050.050.050.90.050.050.050.9HMMλ~2:(31)π~2=0.670.33,A~2=0.90.10.10.9,B~2=0.4750.4750.050.050.050.9With ataken-over state:
HMMλ3:(32)π3=0.330.330.33,A3=0.60.20.20.20.60.20.40.40.2,B3=0.90.10.10.90.50.5HMMλ~3:(33)π~3=0.50.5,A~3=0.7080.2920.2920.708,B~3=0.8330.1670.1670.833Each of the reference nonminimal modelsλi,i=1,2,3 is used to generate 1000 datasets of random observations containing N=20 sequences of T=5000 observation points. The datasets are used to determine log-likelihood distributions of the models and the distance threshold of equivalent models defined in Definition 8. By calculating the percentage of the log-likelihood values of the minimal model λ~i which fall inside the threshold of equivalence for the nonminimal model λi, we can obtain a confidence level. The results in Table 2 show that the two models are approximate equivalent models for all the three cases with high confidence levels. Moreover, the log-likelihood histograms are plotted in Figure 5. The highly overlapping histograms further demonstrate the model equivalence for the three examples.Table 2
Distance threshold test results for nonminimal equivalent models.
Cases Remove Merge Take over Models λ 1 λ ~ 1 λ 2 λ ~ 2 λ 3 λ ~ 3 μ - 0.92 - 0.92 - 1.24 - 1.24 - 0.97 - 0.97 σ 0.012 0.012 0.014 0.014 0.003 0.003 [ μ - 3 σ , μ + 3 σ ] [ - 0.955 , - 0.881 ] [ - 0.955 , - 0.881 ] [ - 1.279 , - 1.191 ] [ - 1.279 , - 1.191 ] [ - 0.978 , - 0.959 ] [ - 0.977 , - 0.960 ] Confidence of equivalence (%) 99.9 99.8 99.8Figure 5
The histogram of log-likelihoods.


## 5.2. Highly Specific HMMs

As discussed previously, persistent and transient-cyclic HMMs with privileged observations are identifiable HMMs that have a high specificity. In this section, we compare the learning of such identifiable HMMs with the Baum-Welch (BW) algorithm and the proposed SCT method.Firstly, we constructed 9 persistent and 9 transient-cyclic models as ground truth models with a fixed equal number of states and observations (Q=M) ranging from 2 to 10. These models can be expressed as follows:Persistentλpers:(34)πpers=1Q1Q⋮1QQ×1,Apers=p1α1α1α1p1α⋱α1α1p1Q×Q,Bpers=p1α1α1α1p1α1⋱α1α1p1Q×QTransient-cyclicλtran⁡:(35)πtran⁡=1Q1Q⋮1QQ×1,Atran⁡=α2p2α2⋱α2α2p2p2α2α2Q×Q,Btran⁡=p2α2α2α2p2α2⋱α2α2p2Q×QThe state self-transition probabilities for persistent models and the transition probabilities to the next neighboring state for transient-cyclic models were both set to a value close to 1, noted asp1 and p2, respectively, where p1,p2∈0.8,0.99. The remaining transitions have equal probabilities; that is, αi=(1-pi)/(Q-1),i=1,2. For all the 18 models, the observation matrices are set the same as the transition matrices of persistent models in order to obtain privileged observations. The initial parameters are uniformly distributed.We also generated 20 hybrid models as ground truth models containing both persistent and transient-cyclic states. The number of statesq1 and q2 for both cases was randomly chosen from 2 to 3, amounting to a total number of states Q=q1+q2 within a range of 4,6. The rest of the parameters were generated in the same manner as before. For simplicity, we use αi to represent a matrix containing only element αi. Thus, a hybrid model can be represented as follows:Hybridλhybr:(36)πhybr=1Q1Q⋮1QQ×1,Ahybr=Apersq1×q1α1q1×q2α2q2×q1Atran⁡q2×q2Q×Q,Bhybr=Bpersq1×q1α1q1×q2α2q2×q1Btran⁡q2×q2Q×QThe experiments were carried out by using each of the constructed models as a reference model to generate a dataset of 10 series of 1000 observations. The first seven series were used as a training set and the last three series as a test set. The true number of statesQ was assumed to be unknown and the learning methods have to select the number of states from a state pool of 2,Q+2. For the BW learning algorithm, Q+1 models were generated with a number of states ranging from 2 to Q+2 and the model with the best Q is selected by the AIC criterion [30]. The learning of the BW algorithm was repeated 20 times to eliminate local optima and the one with the minimum AIC value is selected. In total, 20∗(Q+1) models were generated to determine an optimal model. Moreover, for comparison purpose, we also train BW with a given number of states Q; therefore, a total of 20 models were generated and a best model is selected by the AIC criterion. On the other hand, for the proposed SCT method, the number of states is selected by the clustering validation method in Step 3 (See Section 4.2). Only one SCT model is trained and used for comparison the two best models selected by the BW method (with and without a given Q).In order to use the 3-sigma rule to indicate if a true model is learned, 100 datasets of 10 series of 1000 observations were generated from each of the true models and used for calculating the log-likelihood distributionN(μ,σ) (see Definition 8). If the log-likelihood difference between the ground truth model and the learned model is outside the distance threshold of -3σ,3σ, we consider that the true model has not been found (i.e., a local optimum is learned). Moreover, for better understanding the log-likelihood results, we additionally calculated the log-likelihoods for the following models: (1) λ¯Q-1(λQ): the best model with Q-1 states selected from 100 randomly generated models and trained with BW; (2) λ¯Q-2(λQ): the best model with Q-2 states selected from 100 randomly generated models and trained with BW; (3) a multinomial model: the model assuming that there are no hidden states and the observations are the actual visible states. If an HMM model has similar log-likelihood as a multinomial model, the states have no impact on the model.In addition to log-likelihoods, we define other performance indicators of accuracy as follows: (1) thepercentage of convergence is the percentage of 20 BW learned models which did not fall into a local optimum; (2) thepercentage of identification is the percentage of the best BW or the SCT learned models which did not fall into a local optimum; (3) theparameter distance is defined as the mean difference of the triples (π,A,B) between two HMM models. If the two models have different state space, values of 0s are filled into the probability matrices of the simpler model in order to have an equal number of states to the complex one. Moreover, all the permutations of the models are considered and the minimum distance is chosen as theparameter distance.An average information of the ground truth models can be found in Table3. The hybrid models are less specific than the persistent or transient-cyclic states only models, which make them harder to identify. Detailed learning results can be found in Table 4. The results show that the proposed SCT method learns much faster than the traditional BW algorithm, with a speedup around 180 to 260 times. The BW algorithm tends to overfit the model by using a larger number of states, resulting in a higher parameter distance. Even when the true number of states Q is given, for persistent cases, the BW still cannot learn correctly, which has a larger test-set log-likelihood difference and a lower convergence and identification rate.Table 3
Average characteristics of ground truth HMMs.
Type Specificity Minimal (%) μ ( L L true ) σ ( L L true ) Persistent 0.25 100 - 1.00 0.018 Transient-cyclic 0.32 100 - 1.25 0.017 Hybrid 0.17 100 - 0.93 0.019 Note:μ(LLtrue): mean of the log-likelihood distribution of the true model; σ(LLtrue): standard deviation of the log-likelihood distribution of the true model.Table 4
Identification results on identifiable HMMs.
Type Method # Iters. Time (s) Q select Δ Q Δ L L t e s t Para. Dist. Conv. (%) Identi. (%) Pers. BW 15 1054 Min. AIC 1.67 0.028 0.15 45.56 88.89 CorrectQ 0.00 0.058 0.02 16.11 66.67 SCT 4 4 DBI 0.00 0.012 0.00 — 100  Tran. BW 22 1276 Min. AIC 1.00 0.014 0.08 100 100 CorrectQ 0.00 0.012 0.01 75.56 100 SCT 8 5 DBI 0.00 0.011 0.01 — 100  Hybr. BW 19 891 Min. AIC 1.75 0.008 0.19 88 100 CorrectQ 0.00 0.007 0.00 36.50 100 SCT 10 5 DBI 0.00 0.007 0.00 — 100 # Iters.: average number of iterations; Conv. (%): rate of convergence; Identi. (%): percentage of identification; ΔLLtest: unit log-likelihood difference between the true models and the learned model on test-sets; Para. Dist.: parameter distance; Pers.: Persistent; Tran.: Transient-cyclic; Hybr.: Hybrid. Note that, for the BW, when calculating ΔQ, ΔLLtest, and Para. Dist., the learned model is the best one selected from the 20(Q+1) repeated random models.Learning results for a 10-state persistent model, a 10-state transient-cyclic model, and a 6-state hybrid model are used as examples for visualization. For the persistent model, the iterative learning process is shown in Figures6(a) and 6(b). In Figure 6(a), the BW training was conducted with an unknown number of states Q, while in Figure 6(b), Q was given. Similarly, results for the transient-cyclic model are shown in Figures 7(a) and 7(b). and the hybrid models are in Figures 8(a) and 8(b). The figures show that the proposed SCT method starts from a good initial model at the beginning and converges much faster than most of the 20 randomly initialized BW models which start from an almost equivalent level of the multinomial model for which hidden states play no roles. Moreover, although some of the best BW model converges in the end, the log-likelihood values are still not as good as the SCT method. We see that some of the repeated 20 models with Q states have been stuck in a local optimum with similar log-likelihood to model λ¯Q-1(λQ) or λ¯Q-2(λQ).Figure 6
Identification performance for a 10-state discrete persistent HMM. (a) and (b) show a comparison of log-likelihoods during iterative trainings with different models: the 20 repetitive BW models with an unknown or known number of statesQ, the SCT models, the selected best BW models without or with a given Q, the ground truth HMM, the multinomial model, the best one-state simpler model λ¯Q-1(λQ), and the best two-state simpler model λ¯Q-2(λQ). (c) shows a comparison of the model parameter heat maps for the ground truth HMM, the best BW models with an unknown or a given Q, and the SCT model.
(a)
Log-likelihoods during iterative training, BW with unknownQ (b)
Log-likelihoods during iterative training, BW given correctQ (c)
Heatmap of HMM model parametersFigure 7
Identification performance for a 10-state discrete transient-cyclic HMM. See caption of Figure6 for more details.
(a)
Log-likelihoods during iterative training, BW with unknownQ (b)
Log-likelihoods during iterative training, BW given correctQ (c)
Heatmap of HMM model parametersFigure 8
Identification performance for a 7-state discrete hybrid HMM. See the caption of Figure6 for more details.
(a)
Log-likelihoods during iterative training, BW with unknownQ (b)
Log-likelihoods during iterative training, BW given correctQ (c)
Heat map of HMM model parametersIn order to compare the model parameters, heat maps of the original and inferred state transition and observation matrices are plotted in Figures6(c), 7(c), and 8(c). A lighter color indicates a higher probability value close to one, while a darker color indicates a lower probability value close to zero. We notice that the BW method with an unknown Q learns a complex model with two more states than the true model for all the three cases, which is overfitting, while the SCT approach learns the state size correctly. Moreover, the SCT method has a one-to-one correspondence of the high probabilities (in white/light-yellow) between the transition and observation parameter matrices, meaning the SCT trained model is almost equivalent to the reference true model. However, for the BW method, especially when Q is unknown, there are no one-to-one relations in both transition and observation matrices, noticeable by some of the varied colors of heat maps from the true model. It means that some of the probabilities are wrongly learned.


## 5.3. Hard to Learn HMMs

For each of the seven hard to learn conditions defined in Section3.4, we construct five ground truth models, resulting in a total of 35 models. For each model, persistent and transient-cyclic state numbers are randomly generated from a range of 3,5. The privileged state probability is set randomly within a range of 0.85,0.99. The remaining probabilities are uniformly distributed. For conditions (ii), (iii), (iv), and (v), one extra state is generated accordingly to the specified conditions. For condition (i), state 3 is defined as a mixing state of states 1 and 2. For condition (vi), the first two states are set to have the same observations. For condition (vii), state 2 is set to have a constant observation emission probabilities. The rest of the experiment is set the same as previous experiments designed for identifiable models. Results show that only 31% of the 35 ground truth models are specific with an average specificity of 0.04. A detailed comparison of the learning results is presented in Table 5.Table 5
Identification results on hard to learn HMMs.
Method # Iters. Time (s) Q select Δ Q Δ L L t e s t Para. Dist. Conv. (%) Identi. (%) BW 26 1835 Min. AIC 1.71 0.014 0.14 87.14 100 CorrectQ 0.00 0.013 0.03 52.00 100 SCT 15 8 DBI - 0.66 0.030 0.11 — 97.14 See abbreviations and notes in Table4 for more details.From the results in Table5 we can see that the BW algorithm is slower than the proposed SCT method with almost double learning convergence iterations. The SCT method is around 230 times faster than the BW algorithm. A positive average delta Q indicates that the BW method mostly overfits the true models with an average of 1.71 extra states, while the SCT has a negative delta Q indicating a slightly underfitting with an average of 0.66 fewer states. Even though the test-set log-likelihood difference of the SCT is higher than the BW method, the average parameter distance further proves that the BW algorithm tends to overfit the models in order to have a lower log-likelihood. Moreover, the percentage of convergence reveals that the number of repetitions (e.g., 20 times in this experiment) is still necessary for the BW method to learn effectively, even with the trade-off of longer learning time. Lastly, the SCT has a slightly lower but compatible identification percentage which has a significant learning speedup in return.To visualize the results, we select two models under condition (i), a state being a mixing state, and condition (v), a state with constant self-excluded outgoing transaction, as examples shown in Figures9 and 10, respectively.Figure 9
Identification performance for a 6-state hard to learn HMM under condition (i). See caption of Figure6 for more details.
(a)
Log-likelihoods during iterative training, BW with unknownQ (b)
Log-likelihoods during iterative training, BW given correctQ (c)
Heatmap of HMM model parametersFigure 10
Identification performance for an 8-state hard to learn HMM under condition (v). See caption of Figure6 for more details.
(a)
Log-likelihoods during iterative training, BW with unknownQ (b)
Log-likelihoods during iterative training, BW given correctQ (c)
Heatmap of HMM model parametersFigures9 and 10 show that the BW algorithm with an unknown Q overfits the truth models with two extra states while the SCT method underfits the model with one state fewer where both the mixing state and the state with the same outgoing transactions in the two examples are merged into other states because they are not specific enough to be identified.


## 5.4. Random HMMs

In this experiment, we generated 10000 random HMM models configured with a combination of randomQ(Q∈3,5) and random M(M∈3,5). In order to guarantee that each HMM is minimal, we select models according to two criteria: (1) the model should have a higher test-set log-likelihood than the one of a multinomial model; (2) the model compared to the best Q-1 state model should not satisfy the three-sigma rule for model equivalence criteria defined in Definition 8. A random HMM is discarded if it is not minimal. In the end, we obtain 149 specific minimal HMMs. The training procedure is conducted in the same way as in Section 5.2.Experiment shows that the average specificity of the true models is 0.03, which is around 10 times less specific than the identifiable models used in the previous experiments in Section5.2. Moreover, the mean of the log-likelihood distribution of the true model is 1.58, which is also much higher than the identifiable models. The above results indicate that random models are less specific and therefore less identifiable. A detailed comparison of the identification results is shown in Table 6.Table 6
Identification results on random minimal HMMs.
Method # Iters. Time (s) Q select Δ Q ΔLLtest Para. Dist. Conv. (%) Identi. (%) BW 17 348 Min. AIC 1.16 0.0019 0.21 93.83 100 CorrectQ 0.00 0.0018 0.05 46.64 100 SCT 18 7 DBI 1.70 0.0051 0.22 — 87.92 See abbreviations and notes in Table4 for more details.The results show that the SCT method needs in average one more iteration than the BW algorithm and the identification results are less adequate because the models are not specific enough to be estimated correctly. However, the speedup of the SCT method shows an improvementvis-a-vis the Baum-Welch method, around 50 times. Both of the approaches overfit the models with an average of more than one state.Figure11(a) provides the dependence between true modelspecificity and test-setlog-likelihood difference with the true models. When the specificity is too low, the SCT method identifies less correctly the models. Thus, the less specific the model is, the harder it becomes for the SCT method to learn. For the purpose of comparison, we plot the same figure in Figure 11(b) but for highly specific models which were generated in Section 5.2. The results further confirm that, for highly specific models, when the specificity is relatively low, the SCT method outperforms the BW method. The log-likelihood differences of the models learned by Baum-Welch have significantly increased indicating that completely wrong models are learned.Figure 11
Specificity versus log-likelihood difference with ground truth model. (a) Random specific models generated in Section5.4. (b) Highly specific models generated in Section 5.2.
(a) (b)The results are expected because the SCT method is designed for highly specific models but not for random ones with less specificity. In order to see the influence of specificity for the SCT method to learn correctly, we plot the identification accuracy versus the specificity thresholds ranging from −0.01 to 0.2 with a step of 0.01 as shown in Figure12. The models are selected when they have a specificity higher than a specificity threshold; then the percentage of correctly identified models within the selected models is used as the identification accuracy.Figure 12
Correlation between specificity threshold and identification accuracy.The identification accuracy of the SCT method starts with a low value of 87.9% and generally increases with an increase specificity threshold. When the specificity threshold is at 0.06, the identification percentage of the SCT drops to 93.8%. It is caused by a single case which is observable in Figure11(a) with the highest log-likelihood difference. Such case cannot represent the dependency trend between specificity threshold and identification accuracy and thus can be ignored. When the threshold is higher than 0.06, the proposed SCT method converges to an identification of 100%.


## 6. Conclusions

This paper studied the possibility of identifying HMMs from properties of the observation sequences directly. We conducted an analysis of the information flow throughout an HMM. Based on this analysis we were able to show that there are two types of states, namely, persistent and transient, that have a high impact on the observation likelihood. An HMM consisting of high-impact states is highly specific, in the sense that it differs substantially in observation likelihood from the best HMM with one state less.A learning algorithm, called SCT, was constructed based on this analysis which correctly identifies highly specific models. But even for low-specific models, the identification accuracy is still around 88%. The algorithm is about two orders of magnitude faster than the traditional Baum-Welch algorithm.



---

*Source: 7318940-2017-02-23.xml*