Emmanuel Ramasso
email: emmanuel.ramasso@femto-st.fr

Thierry Denoeux
email: thierry.denoeux@hds.utc.fr

Noureddine Zerhouni
email: noureddine.zerhouni@ens2m.fr

Partially-Hidden Markov Models

HAL is

Introduction

Hidden Markov Models (HMM) are powerful tools for sequential data modelling and analysis. Many applications for several decades have found solutions based on HMM such as discovering word sequences based on speech audio recordings [START_REF] Rabiner | A tutorial on hidden Markov models and selected applications in speech recognition[END_REF], gene finding based on a DNA sequence [START_REF] Murphy | Dynamic Bayesian networks: Representation, inference and learning[END_REF], and performing prognostics and health detection of ball bearings degradation based on noisy sensors [START_REF] Dong | A segmental hidden semi-markov model (hsmm)-based diagnostics and prognostics framework and methodology[END_REF][START_REF] Ramasso | Contribution of belief functions to hidden markov models[END_REF]. In the sequel, we consider sequential data taking the form of a time-series of length T where each element is a multidimensional feature vector x t ∈ ℜ F ,t = 1 . . . T also called vector of observations [START_REF] Rabiner | A tutorial on hidden Markov models and selected applications in speech recognition[END_REF]. The modelling part assumes that the system (a speaker, a DNA sequence or a ball bearing) generating the time-series is a Markov process with unobserved (hidden, latent) discrete states. In HMMs, the states are not visible but when the system is entering in one of the states, the features follow a particular probability distribution. The sequence of observations thus provides information about the sequence of states. One of the most powerful characteristics of HMMs, accounting for its wide range of applications, is the possibility to estimate the parameters efficiently and automatically. Given a training dataset composed of the observed data X = {x 1 , . . . , x t , . . . , x T } (where x t can be continuous or discrete), and denoting by K the number of hidden states such that the state variable y t at time t can take a value in

Ω Y Y Y = {1, . . . , j, . . . , K} , (1)
the following parameters have to be estimated:

• Φ Φ Φ = {φ φ φ 1 , .
. . ,φ φ φ j , . . . ,φ φ φ K } is the set of parameters characterising the probability distribution of observations given each state:

b j (x t ) = P(x t |y t = j;φ φ φ j ), j = 1 . . . K (2) • A A A = [a i j ] with a i j = P(y t = j|y t-1 = i), i = 1 . . . K, j = 1 . . . K (3)
that is the probability of the system to be in state j at time-instant t, given the system was in state i at t -1, with ∑ j a i j = 1. • Π Π Π = {π 1 , . . . , π j , . . . , π K }, where

π j = P(y 1 = j) (4)
is the probability of state j at t = 1, such that ∑ i π i = 1.

In the sequel, all these parameters are aggregated in a vector θ :

θ = {A,Π Π Π ,Φ Φ Φ} . (5)
These parameters can be estimated using an iterative procedure called the Baum-Welch algorithm [START_REF] Baum | A maximization technique occurring in statistical analysis of probabilistic functions of markov chains[END_REF][START_REF] Rabiner | A tutorial on hidden Markov models and selected applications in speech recognition[END_REF] and relying on the Expectation-Maximisation process.

There are applications where some observations x t in the training data X are associated to a label that actually represents the state at time t. Instead of considering the labelling process as a binary one, where states can be known or unknown, we address the problem of partially-supervised HMM training, assuming the labels to be represented by belief functions. These functions can represent uncertainty and imprecision about the states and can be in time-series modelling and analysis.

The contribution of this paper holds in the development of a model called Partially-Hidden Markov Model (PHMM) that manages partial labelling of the training dataset in HMMs. Compared to [START_REF] Côme | Learning from partially supervised data using mixture models and belief functions[END_REF], we take into account the temporal dependency into account, helping in time-series modelling. The proposed approach is based on the Evidential Expectation-Maximisation (E2M) algorithm [START_REF] Denoeux | Maximum likelihood estimation from uncertain data in the belief function framework[END_REF].

Partially-Hidden Markov Models (PHMM)

Given the observation sequence X = {x 1 , x 2 , . . . , x T }, there are three main problems of interest in connection with HMMs [START_REF] Rabiner | A tutorial on hidden Markov models and selected applications in speech recognition[END_REF]: Problem 1: Given a model θ = {Π Π Π ,A A A,Φ Φ Φ}, how to compute its likelihood L(θ ; X)? Problem 2: Given a model θ , how to choose the state sequence Y * = {y * 1 , y * 2 , . . . , y * T } that best explains observations? Problem 3: How to estimate parameters θ = {Π Π Π ,A A A,Φ Φ Φ} of a model? These problems have been solved in different ways for some decades in HMM [START_REF] Rabiner | A tutorial on hidden Markov models and selected applications in speech recognition[END_REF]. In the sequel, we present the solutions for the case where partial information on states is available in the form of a set of belief functions m defined on the set of states Ω Y Y Y . States are then "partially hidden" and the case of completely hidden states is recovered when all the masses are vacuous.

The main idea behind the solutions of partially-supervised training in statistical models is to combine the probability distributions on hidden variables with the belief masses m. This combination can be computed from the contour function pl associated to m.

The next paragraph describes the main features of the E2M algorithm in order to introduce the conditioning process that plays a central role in solutions for problems 1, 2 and 3. The E2M algorithm will be used in the last paragraph dedicated to parameter estimation in PHMMs.

Generalized likelihood function and E2M algorithm

The Evidential EM (E2M) [START_REF] Denoeux | Maximum likelihood estimation from uncertain data in the belief function framework[END_REF] is an interative algorithm dedicated to maximum likelihood estimation in statistical models based on uncertain observations encoded by belief functions. As for the usual EM algorithm, the E2M algorithm does not maximise directly the observed-data likelihood function denoted here L(θ ; X, m) but it focuses instead on a lower bound called the auxiliary function [START_REF] Bishop | Pattern Recognition and Machine Learning[END_REF], and usually denoted by Q and defined as:

Q(θ , θ (q) ) = E θ (q) [log L(X, Y; θ )|X, pl] , (6)
where pl denotes the contour function associated to m and θ (q) is the fit of parameter θ at iteration q, and Q represents the conditional expectation of the completedata log-likelihood. In the E-step of the E2M algorithm, the conditional expectation in the auxiliary function Q is taken with respect to γ

′ def = P(•|X, pl; θ (q) ) = P(•|X; θ (q) )
⊕ pl, that is the combination of the expectation, denoted γ t , with the plausibilities using Demspter's rule [START_REF] Dempster | Upper and lower probabilities induced by multiple valued mappings[END_REF][START_REF] Denoeux | Maximum likelihood estimation from uncertain data in the belief function framework[END_REF]. The new expectation is then defined for each state j at time t by γ ′ t ( j|pl; θ (q) ) = P(y t = j|X, pl; θ (q) ):

γ ′ t ( j|pl; θ (q) ) = γ t ( j; θ (q) ) • pl t ( j)
L(θ (q) ; X, pl) [START_REF] Forney | The viterbi algorithm[END_REF] and the auxiliary function becomes:

Q(θ , θ (q) ) = ∑ Y P(Y|X; θ (q) ) • pl(Y) • log L(X, Y; θ ) L(θ (q) ; X, pl) . ( 8
)
The M-step is similar to to that of the usual EM algorithm and consists in maximising Q with respect to θ . The maximisation is ensured to increase the likelihood of observed data since E2M inherits the monotonicity of EM as for any sequence L(θ (q) ; X, pl), q = 1, 2 . . . , we have L(θ (q+1) ; X, pl) ≥ L(θ (q) ; X, pl).

Solution to problem 1 in PHMM

Using a similar process as in usual HMM (see [START_REF] Bishop | Pattern Recognition and Machine Learning[END_REF] for details on HMM), the marginal posterior distribution on latent variables for the set of parameters θ (q) at iteration q of E2M can be rewritten as:

γ ′ t = P(y t |X; θ (q) ) ⊕ pl t = α ′ t • β t (9)
with α ′ t def = P(X 1:t , y t |pl; θ (q) ) and β

′ t def = P(X t+1:T |y t ; θ (q)
). The definition of β remains the same as in the standard algorithm with β t (i; θ (q) ) = ∑ j β t+1 ( j; θ (q) ) • b j (x t+1 )•a ji , t = 2 . . . T starting from β T (i; θ (q) ) = 1, ∀i. The probability of jointly observing a sequence X 1:t up to t and state j at time t given the parameters and the uncertain data is given by the modified forward variable α ′ t such that α ′ t ( j; θ (q) ) = P(X 1:t , y t = j|pl; θ (q) ) with:

α ′ t ( j; θ (q) ) = α t ( j; θ (q) ) • pl t ( j)
L(θ (q) ; X, pl) [START_REF] Ramasso | Contribution of belief functions to hidden markov models[END_REF] and therefore

γ ′ t ( j; θ (q) ) = α t ( j; θ (q) ) • pl t ( j) • β t ( j; θ (q) ) L(θ (q) ; X, pl) . (11)
Variables α and β are the same as in HMM [START_REF] Bishop | Pattern Recognition and Machine Learning[END_REF]. Summing Eq. 11 over latent variables gives the observed data likelihood. Therefore, to assess the likelihood function L(θ (q) ; X, pl) at the current iteration of the E2M algorithm, we simply need to choose a time index t. A good candidate is the index T since in this case we do not need to evaluate β T (that equals to 1) reducing the computation load:

L(θ (q) ; X, pl) = K ∑ j=1 α T ( j; θ (q) ) • pl T ( j) (12)
Practically, we can use the normalization process proposed in [START_REF] Rabiner | A tutorial on hidden Markov models and selected applications in speech recognition[END_REF] in order to cope with the limited machine precision range.

Solution to problem 2 in PHMM

The Viterbi algorithm [START_REF] Forney | The viterbi algorithm[END_REF] was defined in order to retrieve the best sequence of hidden states within the noisy observations. The best sequence is found in K 2 × T operations (instead of K T for a greedy search) and is ensured to be the one with the highest likelihood. Given the observed data X, the Viterbi algorithm finds the maximum a posteriori (MAP) sequence Y * = {y * 1 , . . . , y * t , . . . , y * T }, y * t ∈ Ω Y . In PHMM, the MAP criterion is modified by taking soft labels into account, i.e., P(Y * |X, pl; θ (q) ) or, equivalently, log P(X, Y * |pl; θ (q) ). In HMMs, the Viterbi algorithm is called the max-sum product algorithm and it is equivalent to a forward propagation with conditioning at each time-step by the potential predecessors of each state. In PHMMs, a similar reasoning can be applied where conditioning (by singletons states) naturally leads to the use of plausibilities. The MAP criterion can be written as:

δ ′ t ( j; θ (q) ) = max i δ ′ t-1 (i; θ (q) ) • a i j • b j (x t ) • pl t ( j), t = 2 . . . T (13) starting from δ ′ 1 ( j; θ (q) ) = π j • pl t ( j) • b j (x 1
). Keeping track of the argument maximising this expression as

ψ ′ t ( j) = argmax i δ ′ t-1 (i; θ (q) )
• a i j , the backtracking of the best state sequence ending in y * t = j at time t is given by y

* t-1 = ψ ′ t (y * t ).

Solution to problem 3 in PHMM

In the E2M algorithm, the auxiliary function is given by Eq. 8. In order to define the maximisation step, the Q-function has to be computed. For that purpose, we introduce the multinomial representation of variables such that y t j = 1 if state j at time t is true, else y t j = 0. Then, we can write:

P(Y, X; θ ) = K ∏ j=1 π y 1 j j • T ∏ t=2 K ∏ i=1 K ∏ j=1 a y t-1,i ,y t j i j • T ∏ t=1 K ∏ j=1 b j (x t ) y t j (14)
Taking the logarithm of the above expression leads to the complete-data loglikelihood. In this paper, partial knowledge on y t j is assumed to be represented by a belief function (and in particular by its contour function pl t ( j), ∀t = 1 . . . T, j = 1 . . . K). The auxiliary function Q thus becomes:

Q(θ , θ (q) ) = E θ (q) [log P(X, Y; θ )|X, pl] (15a) = Q π (θ , θ (q) ) + Q A (θ , θ (q) ) + Q Φ Φ Φ (θ , θ (q) ) , (15b)
with Q π (θ , θ (q) ) = ∑ K j=1 E θ (q) y 1 j |X, pl • log π j given by:

Q π (θ , θ (q) ) = K ∑ j=1 γ ′ 1 ( j; θ (q) ) • log π j , (16)
and

Q A (θ , θ (q) ) = ∑ T t=2 ∑ K i=1 ∑ K j=1 E θ (q) [y t-1,i y t j |X, pl]
• log a i j with:

Q A (θ , θ (q) ) = T ∑ t=2 K ∑ i=1 K ∑ j=1 ξ ′ t-1,t (i, j; θ (q) ) log a i j , (17)
and

Q Φ Φ Φ (θ , θ (q) ) = ∑ T t=1 ∑ K j=1 E θ (q) [y t j |X, pl] • log b j (x t )
given by:

Q Φ Φ Φ (θ , θ (q) ) = T ∑ t=1 K ∑ j=1 γ ′ t ( j; θ (q) ) • log b j (x t ) . (18)
In the above expressions we have:

γ ′ t ( j; θ (q) ) = γ t ( j; θ (q) ) • pl t ( j) ∑ K l=1 γ t (l; θ (q) ) • pl t (l) , (19)
which is the marginal posterior distribution of a latent variable y j at t given pl, and

ξ ′ t-1,t (i, j; θ (q) ) = ξ t-1,t (i, j; θ (q) ) • pl t-1 (i) • pl t ( j) ∑ K l=1 ξ t-1,t (i, l; θ (q) ) • pl t-1 (i) • pl t (l) (20)
is the joint probability of two consecutive latent variables y t-1,i and y t j given pl. The optimal parameters at each iteration of E2M are given by using a similar reasoning as in the standard algorithm, but the posterior probability over latent variables now depends on the plausibilities:

π (q+1) j = γ 1 ( j; θ (q) ) • pl 1 ( j) K ∑ l=1 γ 1 (l; θ (q) ) • pl 1 (l) (21a) a (q+1) i j = T ∑ t=2 ξ t-1,t (i, j; θ (q) ) • pl t-1 (i) • pl t ( j) T ∑ t=2 K ∑ l=1 ξ t-1,t (i, l; θ (q) ) • pl t-1 (i) • pl t (l) (21b)
The maximisation of Q Φ Φ Φ (θ , θ (q) ) depends on the form of the distribution of observations given the latent variable j.

Partial results, conclusion and further work

Partial results: To illustrate this approach, we considered that observations can be modelled by mixtures of Gaussians. We proceeded as in standard HMM to derive the M-step in PHMM and to estimate the parameters of the distributions. Equations are however not reported in this paper.

For illustration purpose, we used the dataset of the PHM'08 data challenge [START_REF] Saxena | Damage propagation modeling for aircraft engine run-to-failure simulation[END_REF] concerning the health state of a turbofan engine. It was manually segmented into four states (to evaluate the results) such that each time-series is accompanied by a set of labels reflecting the current state of the fan, that is normal, transition, degrading or faulty mode. Each label corresponds to a mass function focused on a singleton, except in the transitions where doubt between two labels is defined. The segmentation and the associated BBA are available at http://www.femto-st.fr/ ˜emmanuel.ramasso/PEPS_INSIS_2011_PHM_by_belief_functions. html. The BBA were then transformed into plausibilities. For these tests, we corrupted them by additive noise: pl t ( j) ← pl t ( j)+σ k •ε t ( j), where σ k ∈ {0, 0.1, . . . , 1} and ε t ( j) ∼ U [0,1] was drawn from a uniform distribution. For each noise level, we considered the influence of the number of unlabelled data ν k ∈ {0%, 10%, . . . , 100%}. The partitioning of time-series in the testing dataset estimated by HMM and PHMM using the Viterbi algorithm as defined in HMM (since we do not know the labels for the testing) were compared using the Folkes and Mallows index (F ∈ [0, 1]) [START_REF] Saporta | Comparing two partitions: Some proposals and experiments[END_REF] by computed the relative performance improvement G = F pshmm /F hmm -1 with G ∈ [-1, 1] such that if G > 0 (resp. G < 0), the proposed PHMM provided a better (resp. worse) segmentation of the time-series into states.

The evolution of G is given in Figure 1 that shows an improvement by several percents when using the proposed PHMM (up to 12%). When all data were unlabelled and with no noise (bottom right hand-side corner), both models provided exactly the same results, as expected. When the noise increased, the performance decreased but was still higher than that of the standard HMM. The most difficult cases were encountered when the noise was high (top of figure), where PHMM improvements were between [2%, 5%].

Conclusion and further work:

Taking partial knowledge into account is of crucial importance in many statistical models. Encoding prior information by belief functions leads to simple modifications of the initial estimation formula while remaining theoretically sound. The statistical model considered in this paper was the Hidden Markov Models. Further work remains to be done in order to compute in developing reestimation formula for various distributions of observations given latent states.

Acknowledgements: This work was partially supported by a PEPS-INSIS-2011 grant from the French National Center for Scientific Research (CNRS) under the administrative authority of the French Ministry of Research.

Fig. 1

 1 Fig. 1 Performance (G-index): median value over 10 runs with different initialisation. Positive value reflects an improvement provided by PHMM. Here almost all values are positive except darkest areas.