Christian Bidard

An oddity property for cross-dual games

Keywords: Complementarity problems, Generalized bimatrix game, Oddity, Parametric Lemke algorithm, Ricardo. AMS classi…cation. 01A55, 90-03, 90C33, 91B60

The parametric Lemke algorithm is used to show the existence of an odd number of solutions of a generalized bimatrix game in a certain domain. These solutions are classi…ed into two types according to the relative sign of two determinants. The British economist David Ricardo made an implicit use of that algorithm at the beginning of the nineteenth century.

Introduction

The 1 Lemke algorithm was …rst elaborated to …nd solutions of bimatrix games. One of its variants, the parametric Lemke algorithm, follows the deformations of a solution (w(t); z(t)) of a linear complementarity problem LCP (q; M ) when q = q(t) varies with a parameter t. An important property is that the distribution of the zeroes in w(t) and z(t) remains the same by intervals. A critical point is reached when some positive component of w(t) or z(t) vanishes and, then, a switch in one basic variable is required. As long as a new basic variable can indeed be de…ned at critical points, a solution obtained for q = q(0) allows us to obtain a solution for q = q(1). We return to that algorithm for cross-dual games, a nonlinear extension of bimatrix EconomiX, University Paris Ouest, 200 avenue de la République, F-92001 Nanterre. Tel: +(33) 1 40 97 59 47. E-mail: christian.bidard@u-paris10.fr 1 With acknowledgements to Emmanuel Hyon for comments and suggestions.

games (Sections 2 and 3). We show the connection between its working and the existence of an odd number of solutions in a certain domain, with a clas-si…cation of the solutions into two types according to the relative sign of two determinants (Section 4). That (generic) oddity result holds in particular for bimatrix games. In the historical Section 5, we attribute the idea of the algorithm to the economist David Ricardo who applied it to the land problem two centuries ago and we illustrate the economic problem linked to the presence of antitone moves.

The cross-dual game

By cross-dual game, we mean a complementarity problem of the type

f (x) c [y] (1) g(y) d [x] (2) x 0; y 0 (3)
where x is an n 1 vector in an open set f R n , with R n + f , f : f ! R l a continuous function, c an l 1 vector, y an l 1 vector in an open set g , with R l + g , g : g ! R n a continuous function, and d 2 R n is an n 1 vector (notation 0 means nonnegativity, > 0 semipositivity, >> 0 positivity). The bimatrix game is obtained when f and g are respectively represented by l n and n l matrices A and B. It is assumed that c is negative c << 0

The following Theorem generalizes a well known existence result for bimatrix games, the extension of assumption A + B T 0 being

8x 0 8y 0 y T f (x) + x T g(y) 0 (5)
The proof makes use of the (simpli…ed) Gale-Nikaido-Debreu lemma:

Lemma 1 (GND Lemma). Let S be a compact convex set in R m and z : p 2 S ! z(p) 2 R m be a continuous function satisfying the Walras identity p T z(p) = 0. There exists a vector p 0 2 S such that p T z(p 0 ) 0 for any p 2 S.

If S is the unit simplex, the conclusion is that p 0 is a solution of the complementarity problem z(p) 0, p 0, p T z(p) = 0. The following proof (same idea as in [START_REF] Bidard | Complementarity problems and general equilibrium[END_REF]) forces the Walras identity by considering the function z(p; t) = (tz(t 1 p); pz(t 1 p))

Theorem 1 Let f : R n + ! R l and g : R l + ! R n be continuous functions satisfying condition [START_REF] Lemke | Bimatrix equilibrium points and mathematical programming[END_REF]. Let f be homogeneous of degree one, vector c 2 R l be negative and vector d 2 R n be such that

fx > 0; f (x) 0g ) d T x < 0 (6)
Then the cross-dual game ( 1)-( 2)-( 3) admits a solution.

Proof. For " 0, let the simplex

S " in R n + R l + R + be de…ned by S " = ( (x; y; t); x 0; y 0; t "; X i x i + X j y j + t = 1 )
For any " > 0, the continuous function z :

S " ! R n R m R de…ned by z(x; y; t) = (tg(t 1 y) td; f (x) tc; x T d + y T c x T g(t 1 y) y T f (t 1 x)) (7)
satis…es the Walras identity (x; y; t) T z(x; y; t) = 0 on S " . According to the GND lemma, there exists a point (x " ; y " ; t " ) 2 S " such that inequality 8(x; y; t) 2 S " (x; y; t) T z(x " ; y " ; t " ) 0

holds. Taking into account assumption [START_REF] Lemke | Bimatrix equilibrium points and mathematical programming[END_REF], we obtain in particular that

8(0; y; t) 2 S " y T (f (x " ) t " c) + t(x T " d + y T " c) 0 (9)
Consider a cluster point (x 0 ; y 0 ; t 0 )2 S 0 of (x " ; y " ; t " ) when " tends to zero. By continuity, property (9) also holds for " = 0, therefore f (x 0 ) t 0 c 0 and x T 0 d + cy T 0 0. Suppose t 0 = 0. If x 0 > 0, a contradiction is obtained with assumption (6) and c << 0. If x 0 = 0, then y 0 > 0 and a contradiction is again obtained with assumption c << 0: Therefore t 0 6 = 0 and property (8) can be extended by continuity to " = 0. This shows that g(t

1 0 y 0 ) d 0; f (t 1 0 x 0 ) c 0; x T 0 d + y T 0 c x T 0 g(t 1 0 y 0 ) y T 0 f (t 1 0 x 0 ))
0, and (t 1 0 x 0 ; t 1 0 y 0 ) is a solution of the cross-dual game.

In the remaining of the paper, we shall not use Theorem 1 directly but proceed to a constructive proof. It will be assumed that f is linear and represented by matrix A. After introducing an asymmetric treatment of inequalities (1) and (2), inequality (2) will be replaced by an equality. Vector d can then be interpreted as a parameter in the problem CD(d). Note …rst that, when d is negative, the solution of CD(d) is unique: Lemma 2 Under hypotheses (4) and ( 5), the unique solution of CD(d) for d << 0 is x = 0, y = 0.

Proof. Complementarity implies that y

T c + x T d = y T f (x) + x T g(y)
0, therefore x = 0 and y = 0. Conversely, (x = 0, y = 0) is indeed a solution since inequality (5) implies f (0) 0 and g(0) 0.

Let the functions f : f ! R l R n and g : g R n ! R n be respectively de…ned by

f (x) = f (x) x (10)
g(y; z) = g(y) z (11)

and c be the (l + n) 1 vector c once completed by n zeroes. By setting y T = (y T ; z T ), we have y T f (x) + x T g(y) = y T f (x) + x T g(y), assumption (5) implies 8x 0 8y 0 y T f (x) + x T g(y) 0

A solution (x; y) of the cross-dual game CD(d) generates a solution (x; y) of the system

f (x) c [y] (13) g(y) = d (14) y 0 ( 15
)
where y is the (l + n) 1 vector obtained by stacking vectors y and g(y) d.

Conversely, a solution (x; y) of ( 13)-( 14)-(15) generates a solution (x; y) of the initial system, where vector y consists of the …rst n components of y.

An n-set K f1; :::; l + ng is said to sustain a solution of CD(d) if it is the support of a nonnegative vector y (i.e., the set of its nonzero components) in a solution of the equivalent problem (13)-( 14)-(15). Let R l+n K is the set of the (l + n) 1 vectors with support K. Given a subset S f1; :::; l + ng with cardinal s, f S : f ! R s is the projection of f on R S , i.e. it is the function de…ned by its components f i for i 2 S. Function g K is the restriction of function g to vectors with support K. Jf K (respectively [Jg K ]) is the Jacobian matrix of f K , Jf K (respectively Jg K ) its determinant (f and g are now assumed to be of class C 1 ). When f is linear and represented by an l n matrix A, f is represented by (l + n) n matrix A obtained by stacking A and the identity matrix I n , and Jf K = A K is the n n sub-matrix of A made of the rows corresponding to the set K:

The parametric Lemke algorithm

We consider the generic case, with no speci…c algebraic relationship between the data (A; g; c; d). Flukes apart, the complementarity relationship in inequality (13) requires that the number n of components of x is at least equal to the number of positive components of y, while equality (14) requires that the number of positive components of y is at least equal to n. The number of positive components of y is therefore generically equal to n (if g(0) = 0, as in a bimatrix game, the point d = 0 is an exception, since y = 0 works) and the number of strict inequalities in (13) is generically equal to l. If A K and g K are injective, each arbitrary n-set K sustains at most one solution of (14) and of (13), therefore the number of solutions is …nite: …nding a solution amounts basically to identifying the n-set K of the positive components of vector y. For that purpose, we make use of the parametric Lemke algorithm [START_REF] Cottle | The Linear Complementarity Problem[END_REF], where vector d is a parameter. The algorithm follows the deformations of a solution (x(d); y(d)) of the cross-dual game CD(d) when d varies, with a speci…c attention given to the support of y(d). An important property is that the support remains the same by intervals. A critical point is reached when some positive component of y(d) vanishes and, then, a switch in one basic variable is required. As long as a new basic variable can indeed be de…ned, a solution obtained for d 0 = d(0) allows us to obtain a solution for another vector d. The following Lemma reinterprets assumption (6) as a condition for the working of the algorithm.

Lemma 3 Assume (5). Let d belong to the set

D D = d; 9b z 0 d << A T b z (16)
and let y be a solution of CD(d). If det A K 6 = 0 and Jg K (y) 6 = 0, the parametric Lemke algorithm works in a neighborhood of d, except by ‡uke.

Proof. Let (x 0 ; y 0 ) be a solution of ( 13)-( 14)-(15) at d 0 , and assume …rst that y 0 has n positive components (set K). Since g K is a local di¤eomorphism, a slight change in d is met by an adaptation of the positive components of y = y(d), with no change in x 0 . Assume now that some positive component

k of y(d) = g 1 K (d) vanishes at point d 1 2 D for y = y 1 ('critical point').
The component k which vanishes is unique, ‡ukes apart. For L = Kn fkg, let A L be the corresponding rows of A. A L has dimension (n 1) n and the set of solutions to equation A L x c L = 0 is x = x 0 + x 0 where is an arbitrary scalar and x 0 a nonzero vector in the kernel of A L . Choose x 0 such that A k x 0 > 0 (otherwise, replace x 0 by x 0 ), so that the kth inequality in (13) with f = A is met for any nonnegative scalar . Consider the complementary subset K 0 of K, for which the strict inequality A K 0 x 0 >> c K 0 holds except by ‡uke, and assume for a moment that inequality

A K 0 x 0 0 (17)
also holds. Then, by de…nition of the nonzero vector x 0 ;we have Ax 0 0, hence Ax 0 0 and x 0 0. Since x 0 is nonzero, we obtain from (16) that d T 1 x 0 < b z T Ax 0 0, and from g L (y 1 ) = d 1 that g L (y 1 ) T x 0 < 0. Let x 00 be the semipositive vector x 0 completed by l zeroes. According to property (12) applied to x = x 00 and y = y 1 , we have y T 1 Ax 00 g(y 1 ) T x 00 = g L (y 1 ) T x 0 > 0, therefore y T 1 A L x 0 > 0. A contradiction being obtained with the de…nition of x 0 , inequality (17) does not hold, i.e. there exists at least one row m outside K such that A m x 0 < 0. Consider the smallest positive value of for which one of the strict inequalities A K 0 x 0 >> c K 0 is turned into an equality when x 0 is replaced by x 1 = x 0 + x 0 ( ‡ukes apart, that inequality is uniquely determined). Then (x 1 ; y 1 ) is another solution of CD(d 1 ). When the positive components of y remain close to those of y 1 , but its mth component y m becomes positive (half-neighborhood of y 1 ;with support M = L [ fmg), (x 1 ; y) sustains a solution of CD(d) for d varying in a half-neighborhood of d 1 :

We now examine whether the half-neigborhoods associated with each of the n-sets K and M coincide or are complementary. These n-sets have the (n 1)-set L in common.

Lemma 4

The determinants of the n n matrices A K and A M have opposite signs.

Proof. A K and A M have the submatrix A L in common, which is such that A L x 0 = 0. They only di¤er by one row, respectively A k or A m and, by construction, A k and A m are such that A k x 0 = a > 0 and A m x 0 = b < 0, therefore (bA k aA m )x 0 = 0. There follows that (bA K aA M )x 0 = 0, hence det(bA K aA M ) = 0 and the result. Proof. By continuity, the components of y = g 1 K (d) are close to those of g 1 K (d 1 ), therefore they are close to zero for the kth component and positive for the others. For i 2 K, let b i be the gradient of g i at y 1 . The algebraic equality d d 1 = X i2K (y y 1 ) i b i holds up to a …rst order approximation, from which there follows that the scalar det(b i ; i 2 L; d d 1 ) has the same sign as

(y y 1 ) k det(b i ; i 2 L; b k ) = (g 1 K (d)) k Jg K (y 1 ).
The same scalar has also the sign of (g 1 M (d)) m Jg M (y 1 ). The result follows.

De…nition 1 Let K be an n-set sustaining a solution of the cross-dual game CD(d). That solution is called white if det( A K ) and Jg K (y) have the same sign, black if they have opposite signs.

For instance, the unique solution obtained for c << 0 and d << 0 corresponds to the subset K = fl + 1; :::; l + ng for which A K = I n and g K = I n , therefore that solution is white.

Consider a path d = d(t) in the set D, a solution (x 0 ; y(t)) of CD(d(t)) for t 2 S = [t 1

; t 1 [ for which the support of y(t) is the set K, with y k (d(t)) vanishing at d(t 1 ) = d 1 . By Lemma 3, there exists an n-set M obtained from K by replacing k by an adequately chosen m, such that M is the support of another solution (x 1 ; y 0 ) of CD(d(t)) for t varying in one of the semi-intervals S or T = ]t 1 ; t 1 + ] (the semi-interval for which y ; t 1 + ; [. Assume …rst they have opposite signs. For the …rst solution with support K, y k (t) is positive when t is smaller than t 1 , therefore y 0 m (t) is negative on S and positive on T . This means that M sustains a solution when t continues to move in the same direction after t 1 . By Lemma 5, this case occurs when the Jacobians Jg K (y 1 ) and Jg M (y 1 ) have opposite signs or, taking into account Lemma 4 and De…nition 1, when the successive sets K and M have the same color. On the contrary, if y k (t) and y 0 m (t) have the same sign, M sustains another solution on the same half-interval as K, i.e. when d = d(t) makes a U-turn on the path (antitone move). That change of direction occurs when K and M have opposite colors.

Main result

Consider CD(d) and let d = d(t) move on an oriented curve in D which does not cross itself, starting from d 0 << 0, going to a given point d, and coming back to d 1 << 0. Starting from the unique solution for d 0 , that solution is transferred along the path. Even in the presence of antitone moves, the important property of the algorithm is that the same solution is not found twice (the law of succession of the sets K, M , ..., being uniquely de…ned along the path and reversible, a contradiction would be obtained by considering the …rst set which appears twice in that sequence), therefore the algorithm starting at d 0 goes …rst to d, then reaches d 1 . (The algorithm starting from d 1 follows the reverse path.) Each time the algorithm reaches d, a new solution of CD(d) is obtained. Taking into account the connection between the change of color and the change of direction on the path, we obtain that the solutions thus de…ned, which we call the accessible solutions (i.e., they are reached by following the given path d(t)), satisfy the following existence and oddity result: De…nition 2 Functions f = A and g are called regular if, for any n-set K f1; :::; l + ng, A K and g K are di¤eomorphisms.

Theorem 2 Let A and g be regular and such that condition (5) holds. Let c << 0. For d in the set D de…ned by ( 16), and ‡ukes apart, the number of white solutions of the cross-dual game CD(d) exceeds by one the number of black solutions.

Proof. Let us start from a given solution at d, which is sustained by a set K. By Lemma 3, it can be transferred along the path. If either d 0 or d 1 is reached ultimately, the solution belongs to the unique sequence of accessible solutions, for which the oddity result holds. If not, the sequence starting from K makes a loop and returns to K, hence to d. Considering the corresponding move on the path d(t), that loop sustains as many white as black solutions at d. The non accessible solutions are therefore partitioned into subsets containing as many solutions of each color. Hence the result when n 2. The case (n = 1; d > 0) is treated apart as any curve from d 0 < 0 to d > 0 then to d 1 < 0 makes a to-and-fro movement and crosses itself. Then the inequalities (1) are written a 1 x c; :::; a l x c and the only constraint which matters is the one corresponding to the smallest a i , therefore we may assume l = 1. The system is reduced to the scalar inequalities

ax c [y] g(y) d [x] x 0; y 0 with c < 0, d > 0, ay + g(y)
0 for any y 0 and a < 0 (otherwise, no scalar d > 0 belongs to D). If g(0) < d, the set of solutions is

S = f(x; y); x = c=a; g(y) = d)g; if g(0) > d, it is (x = 0; y = 0) [ S.
Since the color of a solution in S depends on the sign of g 0 (y) when g(y) = d, the result holds in both cases (the limit case g(0) = d corresponds to a degeneracy).

One may wonder if the proof of Lemma 3 and the oddity result can be extended to the case when f is nonlinear (then, one must distinguish between the local behavior of f associated with its Jacobian matrix and its global behavior). The proof.of the Lemma makes use of the following property: consider the curve (C) = x; ; f L (x) = c L which we also parameterize as x = x( ) with x(0) = x 0 , and choose a direction on that curve such that f k (x( )) is locally increasing when becomes positive. Then, for any i, function f i varies monotonously on the oriented curve and, if it is decreasing, its decreases to 1.That property holds when f is linear (then (C) is a straight line) but its extension to the nonlinear case seems rather arti…cial.

It follows from Theorem 2 that global uniqueness is obtained if and only if any solution is white [START_REF] Erreygers | On the uniqueness of cost-minimizing techniques[END_REF]. A reason why the oddity property has not been stated previously for bimatrix games is that it is not apparent, as bimatrix games may have an even number of solutions: some of them are located outside the set D on which the working of the parametric Lemke algorithm and the existence of a solution are both guaranteed.

A pioneer

Ricardo on lands

We would like to draw attention on the connection between the work of the British economist David Ricardo (1772-1823) who, in the Principles (1817), elaborated a theory of long-term prices and rents, and the parametric Lemke algorithm. We follow here a modern formalization of Ricardo's theory mainly due to [START_REF] Sra¤a | Production of Commodities by Means of Commodities. Prelude to Critique of Economic Theory[END_REF]. The data are the set of methods of production, the rate of pro…t r per year (r 0), the vector ( 0) of demand for consumption and the vector of scarcity constraints on lands. Let there be g goods and h qualities of lands. The ith method of production is represented by a vector u i 2 R g + of material inputs, a vector i 2 R h + of land inputs and a quantity c i 2 R ++ of labor (c << 0), and the product obtained one year after investment is represented by a vector v i 2 R g + . Nonnegative combinations of these l methods are allowed. The unknowns are the price vector (the wage being set equal to one) p 2 R g + , the vector 2 R h + of rents per acre of lands and the vector y 2 R m + representing the activity levels of the methods. A long-term equilibrium is a solution of the system

V T p + (1 + r)U T p + T c [y] (18) y [ ] (19) (V U )y [p] (20)
Condition (18) states that all operated methods yield the ruling rate of pro…t, while non-operated methods do not yield more. Condition (19) expresses the scarcity constraints on lands, and the complementarity relationship means that non fully cultivated lands yield a zero rent (competition between landowners). Condition (20) means that the demand for consumption is met by the net product, the overproduced commodities being zero priced. By introducing vector x obtained by stacking p and ; the problem is transformed into a bimatrix game with A = (1 + r)U T V T ; T and B = [V U; ] for which condition A + B T 0 is met. The parallel was pointed out by [START_REF] Salvadori | Land and choice of techniques within the Sra¤a framework[END_REF], who applied the existence result to the economic problem.

Ricardo was interested in the e¤ect of an increase of demand (especially an increase in the demand for corn) due to the increase in the number of workers. He stressed that, starting from an equilibrium for the present level of demand, it su¢ ces to increase the activity levels on partially cultivated lands, with no e¤ect on prices and rents, as long as no new scarcity constraint on lands is met. He also expressed the idea that, when a scarcity constraint is met, the price of corn rises up to the point where some new agricultural method, which was not operated before because it was too expensive when corn was cheap, becomes pro…table (law of succession of methods). A new equilibrium, with higher prices and rents, is obtained. Ricardo's ideas, even if they remain informal (at that time, economists did not write equations) are clearly the same as those sustaining the parametric Lemke algorithm [START_REF] Bidard | The Ricardian rent theory: an overview, Centro Sra¤a working paper[END_REF].

Ricardo considered two ways, which he considered as basically equivalent, to extend the production of corn. One consists in extending cultivation on a new land (extensive cultivation), the other in changing a method already in use on some land and adopting a more productive one (intensive cultivation). He did not see, however, that in the second case the incoming method designated by the law of succession of methods, which is only based on a pro…tability criterion, may in fact be less productive than the present method it replaces. In other words, Ricardo missed the possibility of an antitone move: from a formal point of view, the 'Ricardian dynamics'are the parametric Lemke algorithm with no antitone move. Contemporary economists have pointed at the possible multiplicity of equilibria but missed the link between the multiplicity phenomenon and the failure of the Ricardian dynamics on the path leading from low to high levels of demand.

Numerical examples

Simple numerical examples illustrate the di¢ culties of the Ricardian dynamics. Let there be a unique quality of land (h = 1) with total area =100 acres, a unique commodity (g = 1), corn, and three available methods to produce corn in one period by means of corn and labor. By setting l i = c i , method i (i = 1; 2; 3) is described as (u i quarters corn, l i days labor, i acres land) ! v i quarters corn with, respectively:

u 1 = 5; l 1 = 5; 1 = 1; v 1 = 15 u 2 = 5; l 2 = 20; 2 = 1; v 2 = 20 u 3 = 5; l 3 = 40; 3 = 1; v 3 = 25
Let the rate of pro…t be r = 1 and labor be chosen as numeraire. We solve system (18)-( 19)-(20) for these data, the level of demand being the parameter. For low levels of demand, land is not fully cultivated and the rent is zero. Method 1 is operated because it is the cheapest (competition among farmers) and then the price of corn is p = 1. Since the net product per acre of method 1 amounts to 10 quarters, that solution sustains a …nal demand for corn up to level = 1; 000 when land is fully cultivated. At this stage, the price p of corn rises and the rent per acre becomes positive. As method 1 will continue to be operated in the next equilibrium, equality 2(5p) + 5 + = 15p will hold, i.e. a rise of the price of corn from its present level to p = 1+ goes with a rise of the rent per acre from 0 to = 5 . These moves improve the pro…tability of the alternative methods and method 2 is the …rst to reach the ruling rate of pro…t r = 1 for = 2: The next equilibrium price is p = 3, with = 10: Method 2 is introduced and progressively substituted for method 1. As it is more productive per acre, that equilibrium sustains any demand in the interval [1; 000; 1; 500]. At level = 1; 500, land is fully cultivated by method 2, the price of corn and the rent rise up to p = 4 and = 20, allowing for the progressive replacement of method 2 by the more productive method 3: the Ricardian dynamics work.

Consider now the economy described by methods 1, 2 and 4, where method 4 is characterized by the data u 4 = 3; l 4 = 7; 4 = 1; v 4 = 12 For low levels of demand, method 1 is operated, with p = 1 and = 0. When the price of corn rises to p = 1 + and the rent to = 5 , method 4 becomes pro…table at level = 1, before method 2. Method 4 should be progressively substituted for 1 but, since it is less productive per acre, its introduction would lead to a fall in the net product: the Ricardian dynamics fail. By contrast, the Lemke algorithm goes on by reducing demand from 1; 000 to 900. In the next step, method 4 is maintained and the algorithm proceeds to the introduction of method 2 which replaces method 1. For the intermediate level = 920; two white solutions (method 1 alone, or joint use of methods 2 and 4) are found, as well as one black solution corresponding to the joint use of methods 1 and 4.

Finally, consider the economy described by methods 1 and 4 alone. At level = 920, there are two solutions, but this is not a counter-example to Theorem 2 since, after the disappearance of method 2, that level is outside the set D de…ned by (16).

For the economy de…ned by methods 1, 4 and 6 u 6 = 1; l 6 = 17:5; 6 = 1; v 6 = 11:5

the set D corresponds to levels of demands lower that 950. For demand starting from low levels and growing up to = 920, the equilibrium de…ned by method 1 is reached, but the black equilibria made of methods 1 and 4 and the white equilibrium made of methods 4 and 6 (with p = 3, = 11) are not accessible.

Conclusion

Oddity results are not so infrequent in mathematics. In this paper we link the property and the distinction of two types of equilibria to the working of the parametric Lemke algorithm. It is likely that, beyond the bimatrix and the cross-dual games, the strategy of proof applies to other types of complementarity problems and similar results can be obtained.

Lemma 5

 5 Let d be close to a critical point d 1 = g(y 1 ). The components of g 1 K (d) (respectively, g 1 M (d)) other than the kth (respectively, the mth) are positive. The components (g 1 K (d)) k and (g 1 M (d)) m have the relative sign as Jg K (y 1 ) and Jg M (y 1 ).

0m

  (d(t)) is positive). Both values y k (t) = y k (d(t))and y 0 m (t) = y 0 m (d(t)) change their sign at t = t 1 when d(t) crosses the hypersurface corresponding to y k = y 0 m = 0, therefore y k (t) and y 0 m (t) have either always opposite signs or always the same sign on ]t 1


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

CONTRIBUTION OF BELIEF FUNCTIONS TO HIDDEN MARKOV MODELS WITH AN APPLICATION TO FAULT DIAGNOSIS

Keywords: Evidential Hidden Markov Models, State Sequence Recognition, Partially Supervised Learning, System's Health Assessment

Evidence-theoretic propagations of temporal belief functions are proposed to deal with possibly dependent observations and for partially supervised learning of HMM. Solutions are formulated in Transferable Belief Model framework and experiments concern a diagnosis problem.

INTRODUCTION

Temporal data modelling and analysis are important in many fields [START_REF] Rabiner | A tutorial on hidden Markov models and selected applications in speech recognition[END_REF][START_REF] Murphy | Dynamic Bayesian Networks: Representation, inference and learning[END_REF] and one common solution is to use state sequence representation, learning and inference algorithms. A state generally represents a stationarity or a functioning mode in the data and describes the dynamical system at a given time while transitions represent the system dynamics. In practical applications, states are hidden and only features are observable. An additional modelling step is thus required to relate numerical features to states. In order to manage imperfections, the modelling should cope with uncertainty using [START_REF] Klir | Uncertainty-based information. Elements of generalized information theory[END_REF] probability theory, possibility theory or evidence theory, the latter being more general.

Hidden Markov Model (HMM) [START_REF] Rabiner | A tutorial on hidden Markov models and selected applications in speech recognition[END_REF] is a famous probabilistic and non-deterministic finite state machine for state sequence learning and inference under the concept of hidden states managing both discrete and continuous features. In HMM, the modelling method allows to generate a conditional probability (or a likelihood), denoted b j (O t ) for the j-th state, where

O t = [O 1 O 2 . . . O F ]
is the set of F features. Three problems concerning HMM can be tackled. What if information on states are represented by possibilities or belief functions or in several formalisms? How to express a lack of knowledge without choosing any artificial priors and is it then possible to take it into account in probabilitic HMM learning? What if observations are not independent (conditionally on states)?

In order to tackle these problems, one solution is to marry HMM mechanims with other representations of uncertainty [START_REF] Klir | Uncertainty-based information. Elements of generalized information theory[END_REF]. Mohamad and Gader [START_REF] Mohamed | Generalized HMM -part I: Theoretical frameworks[END_REF] introduced the Generalized HMM in which the generalization is narrowed down to possibility measures and thereby their framework is not able to manage belief functions. One advantage of their framework is the possibility to manage dependent observations by using fuzzy operators but the authors used the product thereby assuming statistical independence. Pieczynski et al. [START_REF] Fouque | Evidential markovian model for data fusion and unsupervised image classification[END_REF][START_REF] Pieczynski | Multisensor triplet Markov chains and theory of evidence[END_REF] pioneered in mixing belief functions with Markov chains leading to promising results. The main idea was to alleviate the problem of prior modelling in Markov chains [START_REF] Soubaras | An Evidential Measure of Risk in Evidential Markov Chains[END_REF] using Dempster's rule of combination (generalizing Bayesian inference [START_REF] Ph | Beliefs functions: The Disjunctive Rule of Combination and the Generalized Bayesian Theorem[END_REF]). However, either the prior or the belief state is evidential but not both, thereby underlying probability assumptions are present. Rombaut et al. [START_REF] Rombaut | State recognition in discrete dynamical systems using Petri nets and Evidence theory[END_REF] proposed a generalization of a Petri Net to belief functions based on the Generalized Bayesian Theorem (GBT) [START_REF] Ph | Beliefs functions: The Disjunctive Rule of Combination and the Generalized Bayesian Theorem[END_REF]. However, it is not robust to noise because links between states at successive instants are given by an evolving and sparse transition matrix depending on sensors measures. Moreover, no classification criterion was proposed. The fourth paper [START_REF] Ramasso | Human shape-motion analysis in athletics videos for coarse to fine action/activity recognition using Transferable Belief Model[END_REF] proposed a deterministic state machine called Belief Scheduler based on the Temporal Evidential Filter [START_REF] Ramasso | State filtering and change detection using TBM conflict[END_REF]. An original inference criterion based on conflict is proposed for classification of sequences. The problem is the sensitivity of some threshold settings.

Compared to previous work, evidential forward-backward-Viterbi propagations are extended to belief functions with underlying probability assumptions. The extension is based on special operators developed in the Transferable Belief Model (TBM) [START_REF] Ph | The Transferable Belief Model[END_REF] in order to consider possibly dependent observations. The problem of partially supervised learning of probabilistic HMM is also tackled using belief functions. ) and the transition matrix is A = [a ij ], i ∈ {1 . . . N}, j ∈ {1 . . . N} with size N × N and j a ij = 1. Transitions between states start from an initial distribution (t = 1) denoted π i , i ∈ {1 . . . N} and probabilities on states are then updated along time according to transitions and observations. An HMM λ = {A, B, Π} is thus characterized by three elements: the transition matrix A, the observation models B (generating likelihoods b i (O t )) and the initial distribution Π.

PROBABILISTIC HMM IN A NUTSHELL

Estimating the likelihood of an observation sequence given the model is computationally feasible using the forward propagation that evaluates the forward variable α t (s

t j ) = P (O 1 , O 2 . . . O t , s t j |λ) = ∀si∈Ωt-1 α t-1 (s i ) • a ij • b j (O t ).
For a classification problem, we need to compute the of observations for each HMM model λ and then to choose the best model by: λ * = argmax λ L p with log L p = -1 T t log sj ∈Ωt α t (s j ) . The backward propagation allows to compute the backward variable

β t (s i ) = P (O T , O T -1 . . . O t+1 |s i , λ) = ∀sj ∈Ωt+1 • a ij • b j (O t+1 ) • β t+1 (s j ).
Two particular combinations of these variables are used in HMM learning [START_REF] Rabiner | A tutorial on hidden Markov models and selected applications in speech recognition[END_REF]. The first is the smooth estimate of probabilities γ t (s t j ) = P (s t j |O 1:T , λ) with γ t (s j ) = α t (s j ) • β t (s j ), that is particularly used to both determine the most probable state at a given instant and models parameters. The second combination is ξ t (s t i , s t+1 j ) = P (s t i , s t+1 j | O 1:T , λ) with ξ t (s t i , s t+1 j ) ∝ α t (s i ) • a ij •b j (O t+1 )•β t+1 (s j ) and allows to compute the expected probabilities of transition by: a ij ∝ T -1 t=1 ξ t (s t i , s t+1 j ). Lastly, the Viterbi algorithm determines the best sequence of hidden states. It is actually a forward propagation where the sum-product operator is replaced by a max-product.

TRANSFERABLE BELIEF MODEL (TBM)

The belief of an agent on subsets of the frame of discernment Ω t can be represented by a belief mass assignment (BBA) m Ωt : 2 Ωt → [0, 1], A → m Ωt (A). The belief mass satisfies A⊆Ωt m Ωt (A) = 1 and can be assigned to singleton state (|A| = 1) or to subsets (|A| > 1), without assumption concerning additivity that is one important difference with probabilities. Conditional BBA can be used to represent state of knowledge, e.g. m Ωt|Ωt-1 [S i ](•) is a BBA defined on Ω t conditionally to subset S i ⊆ Ω t-1 . The mass m Ωt (∅) is the mass of conflict and dividing each belief mass by 1-m Ωt (∅) while forcing m Ωt (∅) = 0 is called Dempster normalization.

Several functions, which are in one-to-one correspondance [START_REF] Ph | The Transferable Belief Model[END_REF], can be computed from a BBA which are then used to simplify the computation of combination rules. In the sequel, the function w Ωt (representing the weights of the canonical conjunctive decomposition (WCD) [START_REF] Denoeux | Conjunctive and disjunctive combination of belief functions induced by non distinct bodies of evidence[END_REF]) will be used. They are defined ∀B ⊆ Ω t by:

w Ωt (B) = B⊆C q Ωt (C) (-1) |C|-|B|+1 (1)
where the commonality q is q Ωt (B) = C⊇B m Ωt (C). We will also use the credibility bel Ωt (B) = C⊆B m Ωt (C) and the plausibility pl Ωt (B) = C∩B =∅ m Ωt (C) with:

pl Ωt (Ω t ) = 1 -m Ωt (∅) (2)
The combinations of BBAs can then be achieved by four main rules [START_REF] Denoeux | Conjunctive and disjunctive combination of belief functions induced by non distinct bodies of evidence[END_REF]: the conjunctive combination (CRC, ∩ ), the disjunctive combination (DRC), the "cautious" CRC (CCRC, ∧ ), and the "bold" DRC. The two last ones are used when sources of belief are not independent. We have [START_REF] Denoeux | Conjunctive and disjunctive combination of belief functions induced by non distinct bodies of evidence[END_REF]:

w Ωt 1 2 (B) = w Ωt 1 (B) w Ωt 2 (B) (3)
where is a "generalized" cautious rule (GCR) based on positive t-norms/t-conorms (see [START_REF] Denoeux | Conjunctive and disjunctive combination of belief functions induced by non distinct bodies of evidence[END_REF]- §5.1 for details). This offers the possibility to use an infinity number of t-norm/tconorm operators ( and ⊥) defined in possibility theory.

For example [START_REF] Denoeux | Conjunctive and disjunctive combination of belief functions induced by non distinct bodies of evidence[END_REF] the Frank t-norm can be used:

x s y =        x ∧ y if s = 0 x • y if s = 1 log s 1 + (s x -1) • (s y -1) s -1 otherwise (4)
where s ∈ [0, 1] and ∧ is the minimum. If s = 0 (resp. s = 1), the CCRC (resp. the CRC) is obtained. If the CRC is used and the obtained belief mass is normalized then we obtain Dempster rule [START_REF] Dempster | A generalization of Bayesian inference[END_REF]. The conditioning process is a special case of conjunctive combination using the CRC between a first belief mass (to be conditioned) with a second one (said categorical) where the latter has the particularity to be not nil only for one element A ⊂ Ω t ("A" is the condition).

Decision making in TBM is made by choosing the best hypothesis from the pignistic probability distribution [START_REF] Ph | The Transferable Belief Model[END_REF] obtained ∀s k ∈ Ω t by:

BetP{m Ωt }(s k ) = 1 1 -m Ωt (∅) B⊆Ωt,s k ∈B m Ωt (B) |B| (5)

PARTIALLY-HIDDEN MARKOV MODELS

Before tackling the problem of evidential propagations with dependent observations, let consider an intermediate situation where one uses probabilistic HMM when data are annotated by belief functions. Let O t be an instance of the learning set. One can have information about the belief of this observation to belong to one of the K states, i.e.

each observation in the learning set is annotated by a belief function m Ωt o . This can be useful because one can learn a HMM in a supervised / unsupervised / partially supervised manner. Indeed, in case of supervised learning, the belief function of each data in the learning set is categorical (e.g. for all instances, the whole mass is assigned to one singleton) thus

m Ωt o (B) = 1 for B ⊆ Ω t and ∀B = C ⊆ Ω, m Ωt o (C) = 0.
In unsupervised learning, the belief function of each data is vacuous, i.e. m Ωt o (Ω t ) = 1 and semi-supervised learning is a mixing of both previous cases. Finally, in partially-supervised learning, belief functions are "general" thus

m Ωt o (B) ∈ [0, 1[, ∀B ⊆ Ω t .
So the problem is: how to take into account partial labels (fourth case) in probabilistic HMM learning? For that, we rely [START_REF] Côme | Mixture model estimation with soft labels[END_REF] concerning EM-based parameters learning using partial labels which has shown promising results for static data.

Let consider the forward variable that has a pivotal role in HMM learning:

α t (s j ) = P (O 1 , O 2 . . . O t , s j |λ) = ∀si∈Ωt-1 α t-1 (s i ) • a ij • b j (O t ).
In case a partial knowledge on states at t is available in the form of a belief function on states m Ωt o , it can be taken into account by the conjunctive combination with α t . Since the probabilistic forward variable has only positive values for singletons, the conjunctive combination leads to:

α t ∩ m Ωt o (s i ) = α t (s i ) • pl Ωt o (s i ) (6)
and thus the forward variable can be rewritten as:

α t (s j ) = ∀si∈Ωt-1 α t-1 (s i ) • a ij • b j (O t ) • pl Ωt o (s j ) (7)
A similar result can be obtained for the backward variable. Given a learning set annotated by belief functions, only plausibility on singletons need to be stored and then used in the forward and backward recursions for HMM learning 1 .

THE CLASSIFICATION PROBLEM

Evidential forward algorithm -The evidential forward propagation is used to assess the forward variable at instant t and requires 1) the BBA m

Ωt-1 α

[λ] of the forward variable at the previous instant t -1 (conditional to the parameters that governs the corresponding EvHMM), 2) the conditional WCD w Ωt a [S t-1 i ] defined on Ω t conditionally to subsets of preceding states (S t-1 i ⊆ Ω t-1 ) and representing transitions between subsets of states at t -1 and t, and 3) the WCD w Ωt b [O t ] obtained from observations at t. Proposition 1 The computation of the evidential forward variable at t satisfies a "prediction -update" mechanism:

w Ωt α [λ](S t j ) = w Ωt b [O t ](S t j ) S t-1 i ⊆Ωt-1 m Ωt-1 α [λ](S t-1 i ) • w Ωt a [S t-1 i ](S t j ) (8)
1 Thanks to Pr. Denoeux (HEUDIASYC lab, thierry.denoeux@utc.fr) for discussions on this subject.

GCR rules endow the evidential forward propagation with a panel of operators that could be chosen according to the application and the data [START_REF] Denoeux | Conjunctive and disjunctive combination of belief functions induced by non distinct bodies of evidence[END_REF]. It has been demonstrated in [START_REF] Denoeux | Conjunctive and disjunctive combination of belief functions induced by non distinct bodies of evidence[END_REF] that these operators are suited for dependent data. Moreover, another advantage is that the prior on states at t = 1 can be "vacuous" and this state of knowledge is easily represented by w Ω1 α [λ](S 1 i ) = 1, ∀S 1 i ⊆ Ω 1 meaning total ignorance. Besides, this evidential version generalizes the probabilistic one when transitions, observations and prior are all Bayesian (i.e. the belief masses are only on singleton hypotheses) and when one uses Dempster rule [START_REF] Dempster | A generalization of Bayesian inference[END_REF]. The complexity of the forward variable is in

T × |Ω t | × 2 |Ωt| .
A conflict may appear at each instant between prediction and observation meaning both quantities are contradictory. This conflict must be cancelled out because it is absorptive by a conjunctive rule. Actually, the required normalization procedure is the same as in probabilistic HMM [START_REF] Rabiner | A tutorial on hidden Markov models and selected applications in speech recognition[END_REF]. Unlike probabilistic HMM where the normalisation process consists in redistributing uniformly 1j α t (j) to each state at t, belief function framework provides complex and sound redistribution rules [START_REF] Ph | Analyzing the combination of conflicting belief functions[END_REF]. The parallel between both formalisms is more obvious when seeing the (seldom emphasized) relation between conflict and plausibility (Eq. 2) that represents a bridge between HMM and EvHMM. As shown in many applications (object association [START_REF] Ristic | The TBM global distance measure for the association of uncertain combat ID declarations[END_REF], image processing [START_REF] Capelle | Evidential segmentation scheme of multi-echo MR images for the detection of brain tumors using neighborhood information[END_REF], change detection and state sequence recognition [START_REF] Ramasso | State filtering and change detection using TBM conflict[END_REF][START_REF] Ramasso | Human shape-motion analysis in athletics videos for coarse to fine action/activity recognition using Transferable Belief Model[END_REF]), conflict is a useful information that is used below for classification of state sequences.

Classification in EvHMM -Given an observation sequence O 1:T (length T ) and a set of N EvHMM λ 1...N , how to choose the EvHMM that best fits observations? Proposition 2 The lower is the conflict throughout the whole observation sequence, the better is the EvHMM λ for explaining these observations. The whole conflict and the best EvHMM are given by:

L c (λ n ) = 1 T T t=1 log(1 -m Ωt α [λ n ](∅)) (9a) λ * = argmax n L c (λ n ) (9b)
This criterion reduces to the probabilistic one when using Dempster rule and Bayesian BBAs. Conclusively, the evidential forward algorithm can be used for online filtering of belief functions on states and for the classification of observation sequences in five steps: 1) the initial BBA (t = 1) on states can be vacuous, 2) Eq. 8 is applied from t = 2 to T , 3) the conflict at t is stored and then redistributed, 4) the classification criterion (Eq. 9) is finally computed.

TIME-INSTANT STATE RECOGNITION AND TRANSITION ESTIMATION

Evidential backward algorithm -The evidential backward algorithm is similar to the forward one and requires the BBA ] are obtained from plausibilities by calculating the conditional commonalities using the GBT [START_REF] Ph | Beliefs functions: The Disjunctive Rule of Combination and the Generalized Bayesian Theorem[END_REF]:

q Ωt|Ωt+1 a [S t+1 j ](S t i ) = s t i ∈S t i pl Ωt+1|Ωt a [s t i ](S t+1 j ) (11)
then used in Eq. 1 to obtain WCDs. Unknown prior at T is modelled by a vacuous BBA (w ΩT β (S T i ) = 1, ∀S T i ⊆ Ω T ). Eq. 10 reduces to the probabilistic case if all BBAs are Bayesian and if Dempster rule is used.

Instant state recognition -As in probabilistic HMM, the conjunctive combination of both forward and backward variables (called γ-variable) is performed when observations are available as a whole. Proposition 4 The γ-variable is given by:

w Ωt γ (S t j ) = w Ωt α (S t j ) w Ωt β (S t j ) (12)
One has to use the same rule as in the forward and backward variables. The γ-variable can then be exploited for two functionalities. The first one is offline smoothing of belief functions on states. The second one is the detection of the best state s * t at a given instant and for a given EvHMM. This state is found out by maximizing the pignistic probability (Eq. 5) based on m Ωt γ , ∀t ∈ {1 . . . T }, i.e. s * t = argmax si∈Ωt BetP{m Ωt γ }(s i ). As in the probabilistic case [START_REF] Rabiner | A tutorial on hidden Markov models and selected applications in speech recognition[END_REF], this technique is not always well-suited for state sequence recognition because is too "local". Instead, an evidential version of the Viterbi algorithm is proposed ( § 7).

Transition estimation -One can mimic the computation of the so-called ξ-variable [START_REF] Rabiner | A tutorial on hidden Markov models and selected applications in speech recognition[END_REF] that is used in probabilistic HMM for transition estimation in an Expectation-Maximization (EM) learning process. A proposition has been formulaed in [START_REF] Ramasso | Forwardbackward-viterbi procedures in TBM for state sequence analysis using belief functions[END_REF] for independent observations. However, by doing so, one can face a serious problem: loosing the interest of belief functions. Indeed, EM is an iterative procedure while (evidential) transition estimation is based on conjunctive combinations. Therefore, due to the repeted conjunctive combinations at each iteration, the transition matrix is expected to gradually tend to a probabilistic one. Therefore, we rather propose below an estimation formula of transitions that is independent of transitions themselves. It consists in computing the expected belief mass of making a transition from one state to another. For that, it is required to combine conjunctively two observed BBAs defined at two successive instants and then taking the mean of these belief masses as proposed below. Proposition 5 An estimation of the expected transition from subsets to subsets from observations is given by: m is the vacuous extension [START_REF] Ph | The Transferable Belief Model[END_REF] of the belief mass m Ωt b [O t ] on the cartesian product defined by: m

Ωt↑Ωt×Ωt+1 b (B) = m Ωt b (C) if C × Ω t+1 = B
and 0 otherwise. If one has prior information on transitions, it can be combined conjunctively with observations in Eq. 13.

The backward recursion requires Eq. 11 to be computed and for that one needs plausibilities conditional to singleton states. They can be obtained from the joint belief mass distribution (Eq. 13) by conditioning it by each singleton state s t i ∈ Ω t followed by a marginalization onto Ω t+1 , formally m Ωt×Ωt+1 â [s t+1 j ] ↓Ωt (the two processes are explained in [START_REF] Ph | Beliefs functions: The Disjunctive Rule of Combination and the Generalized Bayesian Theorem[END_REF][START_REF] Ph | The Transferable Belief Model[END_REF]). This solution satisfies the constraint of independence of conditional beliefs (transition) to apply the GBT. Due to the duality GBT-DRC [START_REF] Ph | Beliefs functions: The Disjunctive Rule of Combination and the Generalized Bayesian Theorem[END_REF], Eq. 11 computes implicitly the beliefs conditional to unions of states by the disjunctive rule. Transitions expressed as a joint belief mass can also be used directly in both forward-backward recursions and this requires to compute the conjunctive combination on a joint space followed by a marginalization onto Ω t to obtain the evidential variables at t. Eq. 13 has been used to estimate the parameters of the Temporal Evidential Filter [START_REF] Ramasso | State filtering and change detection using TBM conflict[END_REF].

STATE SEQUENCE FROM OBSERVATIONS

For a given model, the goal is to determine the best state sequence s 1 * , s 2 * , . . . s T * given the sequence of observations O 1:T . In probabilistic HMM, the powerful Viterbi algorithm, based on dynamic programming, achieves this goal by selecting the sequence with maximum likelihood without computing the N T sequences.

An optimal evidential Viterbi decoding -If we consider sequences of singleton states s 1 , s 2 , . . . s T , then one can apply exactly the same algorithm as in probabilistic HMM except that transitions and observations are represented by the plausibilities on (and conditional to) singletons computed from the related belief masses. The Viterbi metric is a thus propagated plausibility initialized to 1 at the beginning of the sequence reflecting missing prior. The complexity is then the same as in the probabilistic case.

A sub-optimal evidential Viterbi decoding -The previous algorithm, even if optimal in the sense of maximum plausibility / likelihood, reduces belief functions to single values due to the conditioning and propagation processes.

In [START_REF] Ramasso | Forwardbackward-viterbi procedures in TBM for state sequence analysis using belief functions[END_REF] was proposed an algorithm that draws benefits from belief function modelling and that is able to postpone the decision concerning the best predecessors. For that, at each step, it updates a propagated metric that is a belief function w Ωt δ . This algorithm is a Viterbi-like decoder since decisions are not directly propagated. In the sequel, conditioning on EvHMM parameters [λ] are omitted for simplicity. Proposition 6 When observations are not independent, the Viterbi-like metric at t is defined ∀S t j ⊆ Ω t by:

w Ωt δ (S t j ) = w Ωt b [O t ](S t j ) S t-1 ⊆Ωt-1 w Ωt|Ωt-1 a [S t-1 ∩ A t-1 ](S t j ) • m Ωt-1 δ (S t-1 ) (14)
where A t-1 = s t j ∈Ωt ψ (s t j ) is the union of predecessors of states at t. The main idea behind conditioning on the set of predecessors A t-1 is to make a one-step forward propagation of the belief masses of the most important subsets of m Ωt-1 δ . Set A t-1 is obtained by first searching which is the predecessor state at t -1 of each state at t and this is performed in three steps. First, since the predecessor of a state s t j is unknown, it is needed to condition w

Ωt-1 δ on all possible candidates s t-1 i ∈ Ω t-1 . Thus, a WCD w Ωt δ,i is computed by applying Eq. 14 and replacing w

Ωt|Ωt-1 a [S t-1 ∩ A t-1 ] by w Ωt|Ωt-1 a [S t-1 ∩ s t-1 i
]. The second step aims at making a decision concerning predecessors for each state s t j based on m Ωt δ,i using the decision criterion (Eq. 5):

P t [s t-1 i ](s t j ) = BetP{m Ωt δ,i }(s t j ) (15)
Conditioning on s t-1 i in the first step is equivalent to a conjunctive combination with a categorical BBA ( § 3) and the generated conflict m Ωt δ,i (∅) quantifies how irrelevant is the hypothesis "the predecessor of s t j is s t-1 i ". When the two first steps are done for all previous states s t-1 i ∈ Ω t-1 , the most probable predecessor of s t j ∈ Ω t is found by:

ψ t (s t j ) = argmax s t-1 i ∈Ωt-1 1 -m Ωt δ,i (∅) • P t [s t-1 i ](s t j ) (16)
where ψ t (s t j ) stores the best predecessor of s t j . Note that these three first steps are strictly equivalent to the probabilistic mechanism. Then, values of ψ t are used to generate A t-1 (Eq. [START_REF] Denoeux | Conjunctive and disjunctive combination of belief functions induced by non distinct bodies of evidence[END_REF]. They are also used to compute a propagated metric defined at each t by:

Q t (s t * , λ) = Q t-1 (ψ t (s t j ), λ) • pl Ωt δ (s t j ) (17)

ILLUSTRATION ON FAULT DIAGNOSIS

The evidential Viterbi-like decoder is illustrated on challenge data of diagnostic and prognostic of machine faults from the Int. Conf. on Prognostics and Health Management [START_REF] Saxena | Damage Propagation Modeling for Aircraft Engine Run-to-Failure Simulation[END_REF] (available at https://dashlink.arc.nasa. gov/member/goebel/). Data set consists of multiple multivariate time series with sensor noise (blue dots in Fig. 1). Each time serie is from a different engine of the same fleet and each engine starts with different degrees of initial wear and manufacturing variation unknown to the user and considered normal. The engine is operating normally at the start and develops a fault at some point. The fault grows in magnitude until system failure (we have used the file train FD001.txt for training and test FD001.txt for testing).

Given a new observation sequence measured on an engine, the goal is to diagnose its current mode and to determine whether the system is faulty. A fault occurs when a sequence of four modes is detected: steady → transition → up → faulty. One detector is built for each mode with an EM run on the training set using mixture of Gaussians with three components. A four states EvHMM is built where the evidential transition matrix is estimated as proposed in this paper and using the training set. The chosen GCR operator is the Frank t-norm (Eq. 4) with parameter s = 0.9. To exploit the EvHMM, we first use the GBT to transform the likelihoods generated by each detector into belief function distributions [START_REF] Ph | Beliefs functions: The Disjunctive Rule of Combination and the Generalized Bayesian Theorem[END_REF][START_REF] Delmotte | Target identification based on the Transferable Belief Model interpretation of Dempster-Shafer model[END_REF]. These beliefs are then used in the Viterbi decoder. To compare EvHMM with HMM, we transform the evidential transition matrix into a pignistic one and use the likelihoods directly.

An illustration of the detection by both systems is given in Fig. 1 (HMM in light magenta and EvHMM in bold red). The differences in detections come mainly from the lack of data for HMM learning while EvHMM are less sensitive. This lack of sensitivity on the size of the dataset, peculiar to belief functions [START_REF] Côme | Mixture model estimation with soft labels[END_REF], is important in fault diagnosis to decrease the number of tests on machines to build datasets. Moreover, the evidential Viterbi is better in part because it postpones the decision until the last instant thanks to the conditioned forward propagation. Table 1 presents confusion matrices of detections by HMM and EvHMM where EvHMM provides a classification rate of 75% against 68% for HMM. Confusion matrices reflects also an obvious mixing between "transitions" with both "steady" and "up" phases. One solution should be to consider "transition" as belonging to both "steady" and "up" phases while keeping only three modes. Sharing the same training set will not be a problem using GCR rules.

CONCLUSION

Extensions of HMM propagations to belief functions are presented. Contributions of belief functions to HMM are: 1) Possibility to process temporal belief functions, 2) Opportunity to mix several uncertainty formalisms into a flexible one, 3) Partially supervised learning of HMM, 4) Processing possibly-dependent observations by parametrized operators [START_REF] Denoeux | Conjunctive and disjunctive combination of belief functions induced by non distinct bodies of evidence[END_REF], 5) Availability of a variety of combination operators and normalization processes. Higher computational cost is expected but solutions exist to reduce it. A thorough exploration of EvHMM is required for further applications. Moreover, generalizing the approach developed here to other graphical models as well as the development of a criterion for learning in EvHMM taking into account both models and transitions together are under study.

Proposition 3

 3 of the backward variable defined on subsets of states at t+1, the set of conditional plausibilities pl Ωt+1 a [S t i ] representing transitions from subsets of states at t and t + 1 and the observed BBA m Ωt+1 b [O t+1 ]. The belief on states at t in the backward recursion is obtained by: the conjunctive combination of BBAs at Ω t+1 , i.e. m

Fig. 1 .

 1 Fig. 1. EvHMM and HMM Viterbi decodings. Modes: steady (1), transition (2), up (3), faulty (4). Blue dots: observations with values normalized in [0, 4] for visualization.

  States are said hidden: only F observations in O t are available at instants t ∈ {1..T } (T is the sequence length). The number of states is N and s t At each t, the likelihood of state i conditional to the cur-rent observation is denoted b i (O t ) = P (O t |s t i ) and is provided by a modelling technique such as a mixture of Gaussians[START_REF] Rabiner | A tutorial on hidden Markov models and selected applications in speech recognition[END_REF]. The transition from a state s t-1

	i	to a state s t j is
	made with a probability a ij = P (s t j |s t-1 i

i ∈ Ω t is the i-th state at t where Ω t = {s t 1 , s t 2 , . . . s t N } is the frame of discernment.

Table 1 .

 1 Confusion matrices for HMM (top, global accuracy: 68%) and EvHMM (bottom, global accuracy: 75%), values are percents.

		Steady	Transition	Up	Faulty
	Steady	82	48	7	0
	Transition	17	42	18	0
	up	1	1 0	57	4
	Faulty	0	0	1 8	96
		Steady	Transition	Up	Faulty
	Steady	87	36	2	0
	Transition	13	59	25	0
	up	0	5	56	2
	Faulty	0	0	1 7	98