Alain Venditti

J Blot

P Cartigny

J P Drugeon

J M Grand- Mont

P Michel

L Montrucchio

Weak Concavity Properties of Indirect Utility Functions in Multisector Optimal Growth Models

Keywords: Indirect utility function, social production function, multisector optimal growth model, weak concavity. Journal of Economic Literature Classification Numbers: C62, E32, O41

Studies of optimal growth in a multisector framework are generally addressed in reduced form models. These are defined by an indirect utility function which summarizes the consumers' preferences and the technologies. Weak concavity assumptions of the indirect utility function allow one to prove differentiability of optimal solutions and stability of steady state. This paper shows that if the consumption good production function is concave-γ, and the instantaneous utility function is concave-ρ, then the indirect utility function is weakly concave, and its curvature coefficients are bounded from above by a function of γ and ρ.

Introduction

Studies of the qualitative properties of capital accumulation paths in continuous or discrete-time multisector optimal growth models are generally addressed in reduced form infinite-horizon problems (P) such that:

W (k 0 ) = max k(t) +∞ 0 e -δt V (k(t), k(t))dt, s.t. (k(t), k(t)) ∈ D k(0) = k 0 given W (k 0 ) = max {kt} t≥0 +∞ t=0 β t V (k t , k t+1 ) s.t. (k t , k t+1 ) ∈ D k 0 given
where D is a non-empty compact convex subset of R 2n . V is the indirect utility function which summarizes the main characteristics of the consumers' preferences and the underlying technological structure, W the value function, δ the discount rate and β the discount factor, which are respectively assumed to be positive and taken between 0 and 1. Differentiability and concavity of indirect utility functions are of the greatest importance to characterize the local and global dynamic properties of optimal capital accumulation paths. For example, McKenzie [START_REF] Mckenzie | Turnpike theory, discounted utility, and the von Neumann facet[END_REF] shows that if the utility function is not differentiable at the long-run steady state, neither local nor global stability can be proved. In contrast, Yano [START_REF] Yano | The primal route to the turnpike and asymptotic stability[END_REF] shows that if the slope of a marginal utility function is bounded from both below and above by quadratic approximations, the asymptotic stability can be proved even in the non-differentiable case.

Since the early work of McKenzie [START_REF] Mckenzie | Optimal economic growth, turnpike theorems and comparative dynamics[END_REF], Brock and Scheinkman [START_REF] Brock | Global asymptotic stability of optimal control systems with applications to the theory of economic growth[END_REF], Cass and Shell [START_REF] Cass | The structure and stability of competitive dynamical systems[END_REF], Magill [START_REF] Magill | Some new results on the local stability of the process of capital accumulation[END_REF] and Rockafellar [START_REF] Rockafellar | Saddle points of Hamiltonian systems in convex Lagrange problems having a nonzero discount rate[END_REF], 1 it is also well-known that there exists a trade-off between the curvature of the indirect utility function, and the turnpike property. Strict concavity is indeed a central assumption to obtain stability results and to prove differentiability of the indirect utility function. Benhabib and Nishimura [START_REF] Benhabib | Stability of equilibrium in dynamic models of capital theory[END_REF] have proved that if all goods are produced non-jointly under decreasing returns to scale, then V is strictly concave.

More recently, all these former contributions have been used to study the existence of optimal endogenous fluctuations. Montrucchio [START_REF] Montrucchio | The neighbourhood turnpike property for continuous-time optimal growth models[END_REF][START_REF] Montrucchio | A new turnpike theorem for discounted programs[END_REF][START_REF] Montrucchio | A turnpike theorem for continuous time optimal control models[END_REF], Nishimura [START_REF] Nishimura | On uniqueness of a steady state and convergence of optimal paths in multisector models of optimal growth with a discount rate[END_REF], Rockafellar [START_REF] Rockafellar | Saddle points of Hamiltonian systems in convex Lagrange problems having a nonzero discount rate[END_REF] and Sorger [START_REF] Sorger | Local stability of stationary states in discounted optimal control systems[END_REF] prove that the set of discount rate values for which the steady state is saddle-point stable depends 1 See also the more recent contribution of Marena and Montrucchio [START_REF] Marena | Neighborhood turnpike theorem for continuous-time optimization models[END_REF].

1 on some precise degrees of curvature of the indirect utility function. More precisely, periodic or even chaotic dynamics are shown to be compatible with low discounting provided the degree of concavity is adequately chosen (see Boldrin and Montrucchio [4], Montrucchio [15]). For instance, based on the example provided in Benhabib and Rustichini [START_REF] Benhabib | Equilibrium cycling with small discounting[END_REF], Venditti [START_REF] Venditti | Endogenous cycles with small discounting in multisector optimal growth models: continuous time case[END_REF] shows that the smaller are some degrees of concavity of the indirect utility function, the lower are the discount rate values compatible with the endogenous business cycles.

Concavity is also crucial to establish differentiability properties. Montrucchio [START_REF] Montrucchio | Lipschitz continuous policy functions for strongly concave optimization problems[END_REF][START_REF] Montrucchio | Dynamic complexity of optimal paths and discount factors for strongly concave problems[END_REF][START_REF] Montrucchio | A new turnpike theorem for discounted programs[END_REF], Gota and Montrucchio [START_REF] Gota | On Lipschitz continuity of policy functions in continuous-time optimal growth models[END_REF] and Sorger [START_REF] Sorger | On the sensitivity of optimal growth paths[END_REF][START_REF] Sorger | Some notes on discount factor restrictions for dynamic optimization problems[END_REF] show that the policy function, i.e. the optimal capital accumulation path, is Lipschitzcontinuous and that its Lipschitz constant depends on the degree of curvature of V (see also Montrucchio [19], Santos [START_REF] Santos | Smoothness of the policy function in discrete time economic models[END_REF], Santos and Vila [START_REF] Santos | Smoothness of the policy function in continuous-time economic models[END_REF] in which the C 1 -differentiability of the policy function is obtained). It is worth noting however that the way endogenous fluctuations and the stability of the longrun steady state relate to the curvature of the utility function is still not completely understood in the literature. Beside the conclusions of Yano [START_REF] Yano | The primal route to the turnpike and asymptotic stability[END_REF], Nishimura and Yano [START_REF] Nishimura | Nonlinear dynamics and chaos in optimal growth: an example[END_REF] have established the existence of chaotic optimal paths for the case in which the indirect utility function is non-differentiable.

Whatever the conclusions, most of these results are proved using some precise concavity properties:

-the α-concavity, or strong concavity, which provides a measure of the lower curvature of the function. The parameter α is indeed related to the smaller eigenvalue in absolute value of the Hessian matrix. A function f is α-concave if it is "at least as concave" as the quadratic form -(α/2)||x||2 . A strongly concave function is necessarily strictly concave.

-the concavity-γ, or weak concavity, which provides a measure of the upper curvature of the function. 2 Compared with strong concavity, weak concavity is the "Alice's mirror image". The parameter γ is indeed related to the greater eigenvalue in absolute value of the Hessian matrix. A function f is concave-γ if it is "at most as concave" as the quadratic form -(γ/2)||x|| 2 . A weakly concave function may not be strictly concave.

Though the indirect utility function is a reduced form, which gives a summary of the representative consumer's utility function and the production functions, beside the contribution of Benhabib and Nishimura [START_REF] Benhabib | Stability of equilibrium in dynamic models of capital theory[END_REF], the literature did not provide during many years any precise details on the link between these assumptions and the concavity properties of the fundamentals. As explicited in Boldrin and Woodford [START_REF] Boldrin | Equilibrium models displaying endogenous fluctuations and chaos: a survey[END_REF], it was simply stated that the curvature of the indirect utility function "depends (albeit in a very complicated way) on the curvature of the technology and the preferences". But as the literature on endogenous business cycles developped extensively in the 90's, a central problem was to provide some conditions on the fundamentals giving rise to a strongly and / or weakly concave indirect utility function.

In Venditti [START_REF] Venditti | Strong concavity properties of indirect utility functions in multisector optimal growth models[END_REF], we provide sufficient conditions for strong concavity mainly based on the α-concavity of the consumption good's production function and on Lipschitz continuity the capital goods' technologies. The present paper focuses on weak concavity. We provide sufficient conditions based on the weak concavity of the consumption good's technology and of the utility function, and we give some upper bounds for the degree of concavity-γ of the indirect utility function. Moreover, as this property is widely used in discrete-time optimal growth models, 3 we also study the weak concavity of the value function characterizing the standard Bellman equation.

In section 2, we present a step-by-step construction of the indirect utility function. We introduce in section 3 the definition of weak concavity and we establish one mathematical result which is used to prove our main result. Section 4 is devoted to the study of the indirect utility function concavity properties. We also provide some economic interpretations of our conclusions. In Section 5, we focus on discrete-time models and give conditions for the concavity-γ of the value function of the Bellman equation. All the proofs are gathered in the Appendix.

The model

We consider a (n + 1)-sector competitive economy with one consumption good and n capital goods. Total labor is normalized to one, and the model is defined by the following equations:

4 y i ≤ f i (k 1i , . . . , k n1 , l i ), i = 0, 1, . . . , n 1 = n i=0 l i and k j = n i=0 k ji , j = 1, . . . , n (1)
where y 0 is the consumption good output, y j the output of capital good j, k ji the amount of capital good j used in the production of good i, l i the amount of labour used in the production of good i, k j the stock of capital good j, and f i the technology of good i.

Assumption 1. The functions f i : R n+1 + → R + , i = 0, . . . , n, are timeinvariant, C r with r ≥ 2, strictly increasing in each argument and concave.

The n stocks of capital goods k j are such that k j ∈ R + . Assuming a growth rate of labour force g > 0, a capital depreciation rate µ ∈ [0, 1] which is constant and identical across sectors, we obtain the capital accumulation equations in continuous and discrete time for each good j = 1, . . . , n:

y j (t) = kj (t) + (µ + g)k j (t), y jt = (1 + g)k jt+1 -(1 -µ)k jt (2)
We assume that net investment vectors k form a convex set I ⊆ R n . Let us maximize the production of the consumption good y 0 subject to the technological constraints, namely:

max (k 10 ,...,k n0 ,l 0 ) f 0 (k 10 , . . . , k n0 , l 0 ) s.t. y j ≤ f j (k 1j , . . . , k nj , l j ) j = 1, . . . , n (3) 1
= n i=0 l i , k j = n i=0 k ji j = 1, . . . , n (4)
k ji ≥ 0, l i ≥ 0 i = 0, . . . , n and j = 1, . . . , n (5)
This program is denoted ( Pk,y ). Let X i = (k 1i , . . . , k ni , l i ), i = 0, . . . , n, and k = (k 1 , . . . , k n ) be the vector of capital goods stocks. Considering the n + 1 linear constraints (4), we have

X 0 = A(k, X 1 , . . . , X n ) = a + A(k, X 1 , . . . , X n ) (6)
with a T = ( n 0, . . . , 0, 1) and

A : R n(n+2) → R n+1 (which is precisely defined in the Appendix). Let F 0 (k, X 1 , . . . , X n ) ≡ (f 0 o A)(k, X 1 , . . . , X n ). The optimization program ( Pk,y ) becomes max (X j ) n j=i F 0 (k, X 1 , . . . , X n ) s.t. y j ≤ f j (X j ) j = 1, . . . , n (7)
A(k, X 1 , . . . , X n ) ≥ 0 and X j ≥ 0 j = 1, . . . , n (8)
This new program is denoted (P k,y ). For each given (k, y), the set of admissible vectors for (P k,y ), denoted

Q k,y = (A(k, X 1 , . . . , X n ), X 1 , . . . , X n ) ∈ R n+1 n+1 /X j ≥ 0, A(k, X 1 , . . . , X n ) ≥ 0, f j (X j ) ≥ y j , j = 1, . . . , n (9)
is convex. We thus obtain:

Lemma 1. Consider the optimization program (P k,y ) and the set of admissible vectors Q k,y . Under Assumption 1, if for a given (k, y) ∈ R 2n + , Q k,y is non empty, then Q k,y is a compact set and (P k,y ) has an optimal solution.

The optimal solution gives the maximal level of consumption as a function of capital goods stocks k j and output y j , i.e.:

y * 0 = c = T (k 1 , . . . , k n , y 1 , . . . , y n ) (10)
The social production function T is defined over a convex set K ⊆ R 2n + , and gives the frontier of the production possibility set. Consider equations [START_REF] Benhabib | Stability of equilibrium in dynamic models of capital theory[END_REF]. Using notation which is consistent with continuous and discrete time, we get

T (k, y) = (T o B)(k, z) (11
) where B : R 2n → R 2n is a linear map defined by the matrix

B = I n 0 bI n dI n (12)
with b, d ∈ R and I n the n × n identity matrix. We thus have either

z = k, b = (µ + g), d = 1, or z = k t+1 , b = (µ -1), d = (1 + g).
Labor supply is inelastic and the preferences of the representative agent are described by some utility function u(c) such that:

Assumption 2. u : R + → R is time-invariant, C r , r ≥ 1, increasing and concave.

Let us introduce the set

D = {(k, z) ∈ R n × R n /B(k, z) = (k, y) ∈ K} (13)
The indirect utility function is finally defined as

V : D → R with V (k, z) ≡ (u o T o B)(k, z) (14)
3 On weak concavity Concavity assumptions used in economics do not in general provide precise restrictions on the degree of curvature of a function. The concept of curvature is associated with the eigenvalues and the determinant of the Hessian matrix.

In this paper we are concerned with the concept of weak concavity which relies on the greater eigenvalue in absolute value, and which provides an upper bound for the curvature.

U (tx 1 + (1 -t)x 2 , ty 1 + (1 -t)y 2 ) ≤ tU (x 1 , y 1 ) + (1 -t)U (x 2 , y 2 ) + (1/2)gt(1 -t)||x 1 -x 2 || 2 + (1/2)ht(1 -t)||y 1 -y 2 || 2 for all (x 1 , y 1 ), (x 2 , y 2 ) ∈ D and all t ∈ [0, 1]. If γ > 0 or η > 0, U is called concave-(γ, η)
or equivalently weakly-concave. 5In Section 2 we have shown that the indirect utility function V is obtained at the end of a process which combines maximization and composition of several functions. To prove that V may be weakly concave, we need the following mathematical result: Proposition 1. Let F ⊂ R n × R n be a non-empty, compact convex set, and f : F → R be a differentiable concave-(α, β) function, with α > 0 or β > 0. Let g : R → R be a differentiable, monotone increasing, and concave-γ function with γ > 0. Let ||Df (x)|| = sup ν =0 ||Df (x)ν||/||ν|| and p = sup x∈F ||Df (x)||. If g (x) is bounded from above by a finite number q, then the composite function

g o f is concave-(ϕ, χ) over F with ϕ ≤ αq + γp 2 and χ ≤ βq + γp 2 .
This proposition is an extension to the global case of a result proved by Bougeard and Penot [START_REF] Bougeard | Approximation and decomposition properties of some classes of locally d.c. Functions[END_REF] (see also Vial [31]). Moreover, assuming that g is weakly concave allows us to provide a more precise characterization of the concavity coefficients of g o f .

Weak concavity of indirect utility functions

Let us first consider the social production function defined by program (P k,y ). We prove the robustness of weak concavity with respect to maximization. Proposition 2. Let f 0 be concave-α with α > 0, and f j be concave, j = 1, . . . , n. Then under Assumption 1, the value function T (k, y) of program (P k,y ) is such that for any given y ≥ 0, T (., y) is concave-γ with γ ≤ α(1+n).

Benhabib and Nishimura [START_REF] Benhabib | Stability of equilibrium in dynamic models of capital theory[END_REF] also study the concavity properties of T (k, y). With standard arguments of concave programming, it is easy to prove that under Assumption 1, T is a concave function. However strict concavity is more difficult to obtain. Benhabib and Nishimura [START_REF] Benhabib | Stability of equilibrium in dynamic models of capital theory[END_REF] provide two results depending on the returns to scale of the consumption and capital goods technologies. Indeed, under the assumption of non-joint production:

-if each good is produced under decreasing returns to scale, then the Hessian matrix of T (k, y) has full rank, i.e. T is strictly concave;

-on the contrary, if the consumption good and one capital good at least are produced under constant returns to scale, then the Hessian matrix of T (k, y) cannot have full rank. Therefore, T may not be strictly concave. Their results differ drastically from ours since weak concavity is fully compatible with non strict concavity, and with constant or decreasing returns to scale. Let us now consider the following assumptions on T and u: Before establishing our main result, we have to comment on Assumption 3. Let us consider program (P k,y ) which gives the social production function. It is well-known that the static optimization conditions imply:

DT (k, y) = (T 1 (k, y), T 2 (k, y)) = (ω(k, y), -π(k, y))
with ω and π the vectors of the rental rates and prices of the capital goods in terms of the price of the consumption good. Assumption 3 then implies that over the production possibility set, the competitive prices remain bounded. Note also that Assumption 4 rules out the Inada condition.

Denoting p = τ ||B|| with ||.|| the Euclidean norm, we obtain the main result of the paper: Theorem 1. Let Assumptions 1-4 hold. Assume that f 0 is concave-α with α > 0, and that u is concave-ρ with ρ > 0.

Let D k = {ζ ∈ R n /(k, ζ) ∈ D}. Then the indirect utility function V (., z) is concave-ϕ for every given z ∈ D k with ϕ ≤ α(1 + n)r + ρp 2 .
Note that if the utility function u is assumed to be linear, we have u(c) = rc and ρ = 0. The indirect utility function has thus a parameter of weak concavity which satisfies ϕ ≤ α(1 + n)r. Moreover, if Assumption 3 does not hold, i.e. if τ is not finite, then the linearity of u becomes a sufficient condition for the weak concavity of V (., z).

Our goal is to understand how a modification of the curvature of both the production function f 0 and the utility function u may lead to a modification of the indirect utility function's degree of weak concavity. In particular, is it possible to have an indirect utility function which is less and less concave ? To answer this question we have to study the interdependence between the parameters α, r, ρ and p. The parameter r may depend on ρ since the shape of the utility function u varies when its curvature is modified. But recall that since u is weakly concave, u is at most as concave as the quadratic form -(ρ/2)||x|| 2 . Then, if for instance ρ goes toward zero, u is closer and closer to a linear function and r is finite. Similarly, the parameter τ may depend on α. As in the previous case, it is easy to see that if α goes toward zero, the social production function is closer and closer to a linear function and the norm of its gradient remains bounded. Then a weakening of the curvature of the consumption good technology f 0 and the utility function u allows to decrease the indirect utility function's degree of weak concavity.

One may then wonder how to economically interpret these properties. The degree of weak concavity α gives a measure of the transformations of the consumption good production function which are necessary to obtain some non-decreasing returns to scale. In other words, let us consider the set of all production functions devided in two subsets according as the returns to scale are non-increasing or non-decreasing. α provides information on the distance between the given technology and the frontier of the subset containing the non-decreasing returns to scale technologies. ρ may be interpreted as a measure of the inverse of the intertemporal elasticity of substitution in consumption: if ρ tends to 0, u becomes linear and the elasticity tends to infinity. Note also that the greater ρ is, the lower the agent's level of consumption saturation is.

In continuous-time infinite-horizon models, the weak concavity of V (., z) for every given z ∈ D k has been used to establish the existence of endogenous business cycles with low discounting. Indeed, we know since Rockafellar [START_REF] Rockafellar | Saddle points of Hamiltonian systems in convex Lagrange problems having a nonzero discount rate[END_REF] that the more concave is the indirect utility function, the higher is the value of the discount rate δ below which the turnpike property holds. This result then suggests that if the degree of concavity of V is low enough, the steady state can become unstable with a low discount rate. Assuming that V (., z) is concave-ϕ for every given z ∈ D k , Venditti [START_REF] Venditti | Endogenous cycles with small discounting in multisector optimal growth models: continuous time case[END_REF] shows that endogenous persistent fluctuations occur through a Hopf bifurcation when the discount rate δ is larger than a bound δ * which is bounded above by an increasing function of ϕ. As a consequence of Theorem 1, the smaller are the degrees α and ρ of weak concavity of the pure consumption good's production function f 0 and of the utility function u, the lower are the discount rate values compatible with the endogenous business cycles. This general result is illustrated using the example of a three-sector economy with Cobb-Douglas technologies and a linear utility function provided by Benhabib and Rustichini [START_REF] Benhabib | Equilibrium cycling with small discounting[END_REF].

On the value function of discrete-time models

As we explained in the introduction, weak concavity has been extensively used in discrete-time models to prove Lipschitz-continuity of the policy function and turnpike results. 6 In such a framework, the infinite-horizon problem (P) is strictly related to the Bellman equation

W (k) = max z∈D k {V (k, z) + βW (z)} (15)
More precisely, it is shown in Montrucchio [START_REF] Montrucchio | Dynamic complexity of optimal paths and discount factors for strongly concave problems[END_REF][START_REF] Montrucchio | A new turnpike theorem for discounted programs[END_REF] and Sorger [START_REF] Sorger | On the sensitivity of optimal growth paths[END_REF][START_REF] Sorger | Some notes on discount factor restrictions for dynamic optimization problems[END_REF] that if the value function W (k) is concave-γ, then the policy function as defined by z = h(k) = argmax z∈D k {V (k, z) + βW (z)} is Lipschitz-continuous. Moreover, under the same restriction, Montrucchio [START_REF] Montrucchio | A new turnpike theorem for discounted programs[END_REF] shows that the turnpike property holds for any β > β * with β * an increasing function of γ.

Based on Theorem 1, we can provide precise restrictions on the fundamentals that ensure the weak concavity of the value function W (k).

Corollary 1. Let Assumptions 1-4 hold. Assume that f 0 is concave-α with 6 See Boldrin and Montrucchio [START_REF] Benhabib | Equilibrium cycling with small discounting[END_REF], Montrucchio [START_REF] Montrucchio | Dynamic complexity of optimal paths and discount factors for strongly concave problems[END_REF][START_REF] Montrucchio | A new turnpike theorem for discounted programs[END_REF], Sorger [START_REF] Sorger | On the sensitivity of optimal growth paths[END_REF][START_REF] Sorger | Some notes on discount factor restrictions for dynamic optimization problems[END_REF]. α > 0, and that u is concave-ρ with ρ > 0. Then the value function W (k) as defined by ( 15) is concave-ϕ with ϕ ≤ α(1

+ n)r + ρp 2 .
According to Theorem 4.1 in Montrucchio [START_REF] Montrucchio | A new turnpike theorem for discounted programs[END_REF], this Corollary shows that in discrete-time infinite-horizon models, other things being equal, the smaller are the degrees α and ρ of weak concavity of the pure consumption good's production function f 0 and of the utility function u, the closer to 0 will be the lower bound β * above which the turnpike property holds. This conclusion drastically differs from the one established by Benhabib and Rustichini [START_REF] Benhabib | Equilibrium cycling with small discounting[END_REF] and Venditti [START_REF] Venditti | Endogenous cycles with small discounting in multisector optimal growth models: continuous time case[END_REF] within continuous-time models where the turnpike property becomes less robust when α and ρ are closer to 0.

Appendix

Proof of Lemma 1

Consider program ( Pk,y ). Let X i = (k 1i , . . . , k ni , l i ), i = 0, . . . , n, and k = (k 1 , . . . , k n ) be the vector of capital goods stocks. ( Pk,y ) may be more precisely defined from a mathematical point of view using the following procedure. Defining a new objective function f 0 (X 0 , X 1 , . . . , X n ) ≡ f 0 (X 0 ), ( Pk,y ) becomes: maximize f 0 (X 0 , X 1 , . . . , X n ) with respect to (X 0 , X 1 , . . . , X n ), subject to the constraints (3)- [START_REF] Boldrin | Equilibrium models displaying endogenous fluctuations and chaos: a survey[END_REF]. For a given vector (k, y), the set of admissible vectors for ( Pk,y ) is defined as follows:

Θ k,y = (X 0 , X 1 , . . . , X n ) ∈ R n+1 n+1 /X i ≥ 0, i = 0, . . . , n, f j (X j ) ≥ y j , j = 1, . . . , n

Using the constraints (4) and ( 5), we obtain:

||X i || ≤ n j=1 k 2 j + 1 < +∞ for i = 0, 1, . . . , n so that ||(X 0 , . . . , X n )|| = n i=0 ||X i || 2 ≤ √ n + 1 n j=1 k 2 j + 1 < +∞
Then there exists C > 0 such that (X 0 , . . . , X n ) ∈ Θ k,y implies ||(X 0 , . . . , X n )|| ≤ C, i.e. Θ k,y is a bounded subset of (R n+1 ) n+1 . Therefore, under Assumption 1, Θ k,y is a compact set. Let us now consider the optimization program (P k,y ) which gives the social production function T . For every given (k, y), the set of admissible vectors is now

Q k,y = (A(k, X 1 , . . . , X n ), X 1 , . . . , X n ) ∈ R n+1 n+1 /X j ≥ 0, A(k, X 1 , . . . , X n ) ≥ 0, f j (X j ) ≥ y j , j = 1, . . . , n
The problem is then to know the link between Θ k,y and Q k,y . Using f 0 , we obtain

F 0 (k, X 1 , . . . , X n ) ≡ f 0 (A(k, X 1 , . . . , X n ), X 1 , . . . , X n ). Therefore, we have Θ k,y = Q k,y since the constraint A(k, X 1 , . . . , X n ) ≤ 0 of program (P k,y
) is equivalent to the constraints (4) and X 0 ≥ 0 of program ( Pk,y ). It follows that Q k,y is a compact set, and under Assumption 1, (P k,y ) has an optimal solution.

Proof of Proposition 1

Let x, y ∈ R be such that x = f (a) and

y = f (b) with a = (a 1 , a 2 ), b = (b 1 , b 2 ) in F. For all t ∈ [0, 1] we have g(tf (a) + (1 -t)f (b)) ≤ tg(f (a)) + (1 -t)g(f (b)) + γ 2 t(1 -t)||f (a) -f (b)|| 2 Moreover, f is a concave-(α, β) function such that f (ta+(1-t)b) ≤ tf (a)+(1-t)f (b)+ α 2 t(1-t)||a 1 -b 1 || 2 + β 2 t(1-t)||a 2 -b 2 || 2 Since g is a monotone increasing function we get g f (ta + (1 -t)b) -α 2 t(1 -t)||a 1 -b 1 || 2 -β 2 t(1 -t)||a 2 -b 2 || 2 ≤ t(g o f )(a) + (1 -t)(g o f )(b) + γ 2 t(1 -t)||f (a) -f (b)|| 2
Owing to the mean value theorem, there exist θ, η ∈ (0, 1) such that g

f (ta + (1 -t)b) -α 2 t(1 -t)||a 1 -b 1 || 2 -β 2 t(1 -t)||a 2 -b 2 || 2 -g(f (ta + (1 -t)b)) = -Dg(θX + (1 -θY ) 1 2 t(1 -t) α||a 1 -b 1 || 2 + β||a 2 -b 2 || 2 with X = f (ta + (1 -t)b) -α 2 t(1 -t)||a 1 -b 1 || 2 -β 2 t(1 -t)||a 2 -b 2 || 2 , Y = f (ta + (1 -t)b), and f (a) -f (b) = Df (ηa + (1 -η)b)(a 1 -b 1 , a 2 -b 2 ) Assume now that g (x) is bounded from above by a finite number q. Since ||(x, y)|| 2 = ||x|| 2 + ||y|| 2 , we finally obtain (g o f )(ta + (1 -t)b) ≤ t(g o f )(a) + (1 -t)(g o f )(b) + qt(1-t) 2 α||a 1 -b 1 || 2 + β||a 2 -b 2 || 2 + γp 2 t(1-t) 2 ||a 1 -b 1 || 2 + ||a 2 -b 2 || 2 with p = sup x∈F ||Df (x)|| and ||Df (x)|| = sup ν =0 ||Df (x)ν||/||ν||. There- fore, g o f is concave-(ϕ, χ) over F with ϕ ≤ αq + γp 2 and χ ≤ βq + γp 2 .

Proof of Proposition 2

Before proving Proposition 2, we need to establish two useful Lemma. Lemma 6.1. Let A be the affine map as given by [START_REF] Bougeard | Approximation and decomposition properties of some classes of locally d.c. Functions[END_REF]. Let f 0 be concaveα with α > 0. Then under Assumption 1-2, f 0 o A is concave-γ with γ ≤ α(n + 1).

Proof : Let x, x ∈ R n(n+2) . Since f 0 be a concave-α, and A is an affine map, we have

f 0 (A(tx + (1 -t)x ) ≤ tf 0 (A(x)) + (1 -t)f 0 (A(x )) + αt(1-t) 2 ||A(x -x )|| 2 ≤ tf 0 (A(x)) + (1 -t)f 0 (A(x )) + α||A||t(1-t) 2 ||x -x || 2 The linear part A of A is defined as follows   I n×n -I n×(n+1) • • • -I n×(n+1) 0 • • • 0 n 0 • • • 0 n -1 • • • 0 • • • 0 n -1   with I n×m the n × m identity matrix. The matrix product AA T is equal to the diagonal matrix I (n+1)×(n+1) .( n n + 1, • • • , n + 1, n) T .
The greater eigenvalue in absolute value is then equal to n + 1, and the Euclidean norm of A is: ||A|| = √ n + 1 (see Strang [START_REF] Strang | Linear Algebra and its Applications[END_REF]). Then the composite function f 0 o A is concave-γ with γ ≤ α(n + 1).

We have now to state a technical result which allows to study the constraints of program (P k,y ), and which is used to prove Proposition 2. Let us consider the following program which is equivalent to (P k,y ): max f (x 1 , . . . , x m ) s.t. (x 1 , . . . , x m ) ∈ D and g 1 (x 1 ) ≥ z 1 , . . . , g m (x m ) ≥ z m with f and g i some real-valued concave functions, and D a convex set. This new program is denoted (P z ). In the following, let MI = {f : R m → R/∂f /∂x i > 0, i = 1, . . . , m} be the set of real-valued strictly increasing functions, and MD = {f : R m → R/∂f /∂x i > 0, i = 1, . . . , m} be the set of real-valued strictly decreasing functions. Lemma 6.2. Let f and g i , i = 1, . . . , m, be some real-valued concave functions. Let z = (z 1 , . . . , z m ) T , x(z) = (x 1 (z), . . . , xm (z)) be the optimal solution of program (P z ), and J (z) = {i/g i (x i (z) = z i } be the set of binding constraints. If f ∈ MD (resp. MI) and if g i ∈ MI (resp. MD) for i = 1, . . . , m, then #J (z) = m.

Proof of Theorem 1: Lemmas 6.1-6.

Proof of Corollary 1

Theorem 1 shows that under Assumptions 1-4, if f 0 is concave-α and u is concave-ρ, V (., z) is concave-ϕ for every given z ∈ D k with ϕ ≤ α(1 + n)r + ρp 2 . Consider the Bellman equation W (k) = max z∈D k {V (k, z) + βW (z)}. Let (k 1 , y 1 ), (k 2 , y 2 ) ∈ D such that W (k 1 ) = V (k 1 , z 1 ) + βW (z 1 ), W (k 2 ) = V (k 2 , z 2 ) + βW (z 2 ) and k = tk

Assumption 3 .

 3 τ = sup (k,y)∈K ||DT (k, y)|| < +∞ with ||DT (k, y)|| = sup ν =0 ||DT (k, y)ν||/||ν||. Assumption 4. sup x∈R + u (x) = r < +∞.

  3 and Proposition 2 imply that if f 0 is concave-α, then (T o B)(., z) is concave-γ for any given z ∈ D k with γ ≤ α(n + 1). Moreover, (T o B) satisfies ||D(T o B)(k, z)|| = ||D(T (B(k, z))B|| ≤ ||D(T (B(k, z))||.||B|| Under Assumption 3, we have sup (k,z)∈D ||D(T o B)(k, z)|| ≤ τ ||B|| ≡ p. If u is concave-ρ and satisfies Assumption 4, Proposition 1 implies that V (., z) is concave-ϕ for every given z ∈ D k with ϕ ≤ α(1 + n)r + ρp 2 .

2 ||k 1 - 2 ||k 1 -

 2121 1 + (1 -t)k 2 with t ∈ [0, 1]. We get W ( k) = max z∈Dk V ( k, z) + βW (z) = V ( k, z) + βW (z) with z = z(k) the solution of the Bellman equation. Since V (., z) is concaveϕ for every given z ∈ D k we conclude W ( k) ≤ t [V (k 1 , z) + βW (z)] + (1 -t) [V (k 1 , z) + βW (z)] + γt(1-t) k 2 || 2 But as by definition W (k 1 ) ≥ V (k 1 , z) + βW (z) and W (k 2 ) ≥ V (k 2 , z) + βW (z), we derive W ( k) ≤ tW (k 1 ) + (1 -t)W (k 2 ) + γt(1-t) k 2 ||2 and the value function W (k) is also concave-γ.

  Definition 1. Let R n be endowed with the Euclidean norm ||.||, and D= X × Y ⊆ R n × R

n be a non empty convex set. Let U : D → R be a real-valued concave function. Let γ and η be the greatest lower bounds of the set of real numbers g and h such that the function U (x, y) + (1/2)g||x|| 2 + (1/2)h||y|| 2 is convex over D, i.e.

Sorger [26,[START_REF] Sorger | Some notes on discount factor restrictions for dynamic optimization problems[END_REF] uses the notation "(-γ)-convexity" instead of "concavity-γ".

See Boldrin and Montrucchio[START_REF] Benhabib | Equilibrium cycling with small discounting[END_REF], Montrucchio[START_REF] Montrucchio | Dynamic complexity of optimal paths and discount factors for strongly concave problems[END_REF][START_REF] Montrucchio | A new turnpike theorem for discounted programs[END_REF], Sorger[START_REF] Sorger | On the sensitivity of optimal growth paths[END_REF][START_REF] Sorger | Some notes on discount factor restrictions for dynamic optimization problems[END_REF].

The lack of the time index t means that the model may be considered as either in discrete or continuous time.

See Vial[START_REF] Vial | Strong and weak convexity of sets and functions[END_REF], Bougeard and Penot[START_REF] Bougeard | Approximation and decomposition properties of some classes of locally d.c. Functions[END_REF].

* This work was supported by French National Research Agency Grant (ANR-08-BLAN-0245-01).

Proof : Let x(z) = (x 1 (z), . . . , xm (z)) be the optimal solution of program (P z ). Assume that x(z) is such that a constraint i = i 0 is not binding, i.e. g i 0 (x i 0 (z)) > z i 0 . Let us then consider x ∈ D such that xi = xi (z) for every i = i 0 , and g i 0 (x i 0 ) > z i 0 . Assume first that f ∈ MD and g i ∈ MI for all i = 1, . . . , m. It is then easy to verify that xi 0 < xi 0 (z) and f (x) > f (x(z)). Therefore, if x(z) is the optimal solution, we cannot have g i 0 (x i 0 (z)) > z i 0 . Since this result holds for any i, x(z) is necessarily such that all the constraints are binding. The same result holds if f ∈ MI and g i ∈ MD. On the other hand, if f, g i ∈ MD, or f, g i ∈ MI, the same reasoning proves that no constraint is binding.

Proof of Proposition 2: Under Assumption 1, and from the definition of F 0 , Lemma 6.2 implies that every constraint y j ≤ f j (X j ), j = 1, . . . , n, is binding. Let k, k , y ∈ R n be such that (k, y), (k , y) ∈ K and k = tk + (1t)k . Let X * (k, y), X * (k , y) and X * ( k, y) be the corresponding solutions of (P k,y ) with

. Moreover, under Assumption 1, for each given y ≥ 0, the function X * (., y) is continuous (see Benhabib and Nishimura [START_REF] Benhabib | The Hopf bifurcation and the existence and stability of closed orbits in multisector models of optimal economic growth[END_REF], pp. 438-441). Then we get

and the value function T (., y) is concave-γ with γ ≤ α(1 + n).

Proof of Theorem 1

Before proving Theorem 1, we need to establish a last useful Lemma. Lemma 6.3. Let T (., y) be concave-γ for each given y ≥ 0, and B be the linear map as given by [START_REF] Mckenzie | Turnpike theory, discounted utility, and the von Neumann facet[END_REF]. Then (T o B)(., z) is concave-γ for any given


Rim Romdhane
email: [rim.romdhane@inria.fr

Carlos Fernando Crispim
email: carlos-fernando.crispimjunior@inria.fr

Francois Bremond
email: francois.bremond@inria.fr

Monique Thonnat
email: monique.thonnat]@inria.fr

Activity Recognition and Uncertain Knowledge in Video Scenes

Activity recognition has been a growing research topic in the last years and its application varies from automatic recognition of social interaction such as shaking hands, parking lot surveillance, traffic monitoring and the detection of abandoned luggage. This paper describes a probabilistic framework for uncertainty handling in a description-based event recognition approach. The proposed approach allows the flexible modeling of composite events with complex temporal constraints. It uses probability theory to provide a consistent framework for dealing with uncertain knowledge for the recognition of complex events. We validate the event recognition accuracy of the proposed algorithm on real-world videos. The experimental results show that our system can successfully recognize activities with a high recognition rate. We conclude by comparing our algorithm with the state of the art and showing how the definition of event models and the probabilistic reasoning can influence the results of real-time event recognition.

Introduction

In the literature, many video event recognition systems have been proposed. However, many challenging problems still remain to obtain a robust recognition because of noise, illumination changes, segmentation issues and occlusions. We propose a constraint-based approach for realworld video interpretation based on probabilistic reasoning for composite event recognition. The main goal is to improve the techniques of video data interpretation taking into account the imprecision and uncertainty of low level data.

The paper is organized as follows: In section 2, we review the related work. In section 3 and 4 we describe the proposed video interpretation framework for event recognition. The experiments realized to evaluate the proposed method are shown in section 5. Finally, we present the conclusion in section 6.

Related work

Automatic activity recognition is a very important and active area of research [START_REF] Fouhey | People Watching: Human Actions as a Cue for Single-View Geometry[END_REF], [START_REF] Delaitre | Scene semantics from long-term observation of people[END_REF], [START_REF] Romdhane | Uncertainty for Complex Event Recognition[END_REF]. Activity recognition approaches can be divided into two main approaches: probabilistic approaches and description-based approaches. The probabilistic approaches include Bayesian Networks and Hidden Markov Models. The main characteristic of these techniques is to model explicitly the uncertainty.

Bayesian Network have been successfully applied to person interaction [START_REF] Park | A Hierarchical Bayesian Network for Event Recognition of Human Actions and Interactions[END_REF] such as 'shake hands', parking lot surveillance [START_REF] Nevatia | Video-based event recognition : activity representation and probabilistic recognition methods[END_REF], traffic monitoring [START_REF] Kumar | Framework for real-time behavior interpretation from traffic video[END_REF] and detection of left luggage [START_REF] Lv | Left luggage detection using bayesian inference[END_REF]. However, Bayesian Network are not adapted to model temporal compositions of events. Temporal representation is often done using a static representation, where time points or time slices are represented as static processes. HMMs and their extensions [START_REF] Oliver | Layered representations for human activity recognition[END_REF], [START_REF] Duong | Activity recognition and abnormality detection with the switching hidden semi-markov model[END_REF], [START_REF] Chiang | Scene-based event detection for baseball videos[END_REF] have been widely used. Their advantage compared to Bayesian Network is the ability to recognize sequence of events. However HMMs are limited in recognizing sequence of events which involve several mobile objects because the probability of being in a state for a mobile object has to be combined with the probability of being in another state for all other mobile objects. These combinations lead the recognition process to a combinatorial explosion.

Description-based approaches have also been largely used to recognize activities for few decades. Constraint Satisfaction Problem (CSP) has been applied to model activities as constraint networks [START_REF] Reddy | Recognition of Users Activities Using Constraint Satisfaction[END_REF]. Description-based approaches are suitable for recognizing high-level activities. They can more easily incorporate human knowledge into the systems and require less training data as pointed out by many researchers [START_REF] Oliver | Layered representations for human activity recognition[END_REF], [START_REF] Nevatia | Hierarchical languagebased representation of events in video streams[END_REF], [START_REF] Ryoo | Recognition of composite human activities through context-free grammar based representation[END_REF]. But the formalism of the event modeling and recognition is largely deterministic and convenient mechanism to handle uncertainty and compensate for the failures of low-level is generally unavailable.

The approaches combining logic and probabilistic reasoning have been designed to overcome the limitations of the previous approaches. Ryoo and Aggarwal [START_REF] Ryoo | Semantic representation and recognition of continued and recursive human activities[END_REF], [START_REF] Ryoo | Stochastic Representation and Recognition of High-Level Group Activities[END_REF] have taken advantage of the concept of the hallucinated time intervals, similar to the one used in [START_REF] Minnen | Expectation grammars: Leveraging high-level expectations for activity recognition[END_REF] to deal with un-certainty. Tran and Davis [START_REF] Tran | Event modeling and recognition using Markov logic networks[END_REF] have adopted probabilistic graphical model, Markov logic networks (MLNs) to probabilistically infer events in a parking lot. In [START_REF] Brendel | Probabilistic Event Logic for Interval-Based Event Recognition[END_REF] authors have presented a probabilistic event logic (PEL) which uses weighted event-logic formulas to represent probabilistic constraints among events. However, they do not deal with the low-level uncertainty and consider only the recognition of primitive events of basketball game. Kwak et al. [START_REF] Kwak | Scenario-Based Video Event Recognition by Constraint Flow[END_REF] have adopted constraint flows to summarize the combination of the primitive events composing a complex event.But the complexity of the recognition algorithm is not described. The logic-probabilistic combination is an promising field of research. However, it has not been fully explored and many efforts are still needed to provide a complete framework for fully handling the uncertainty of recognition. Thus, in this paper, we propose a new approach for complex event recognition which combine logic and probabilistic reasoning for a better performance of the recognition.

Event Representation

We propose a generic event representation formalism that is capable to represent all types of events used for the automatic video recognition and that is able to manage the uncertainty of recognition at the event modeling level. This formalism contains the Event description Language described in [START_REF] Vu | A Novel Algorithm for Temporal Scenario Recognition[END_REF] which is declarative and intuitive, so that the experts of the application domain can easily define and modify it. The main limitation of this language is the lack of mechanism to handle the uncertainty of recognition. For this, we proposed 2 extensions, mainly, we propose (i) the notion of 'utility' to deal with missed observations (see section 3.1) and we propose (ii) a specific relation in the representation of the event to manage the tracking identifier maintenance (see section 3.2).

There are four types of activities going from simple to more complex: primitive states, composite states, primitive events and composite events. An event model is composed of five elements:

• Physical objects: objects of interest involved in the event. The type of the objects depends on the application domain. Physical objects includes mobile objects (e.g. person, vehicle), contextual objects (equipment, zones).

• Components: the sub-events composing the event.

• Constraints: conditions between the physical objects and/or the components including symbolic, logical, spatial and temporal constraints based on Allen predicates [START_REF] Allen | Maintaining knowledge about temporal intervals[END_REF]. • Alarm: The alarm information describes the importance of the scenario model in terms of emergency (i.e. not urgent, urgent, very urgent). The alarm level can be used to filter the recognized events, for displaying only important events to the user.

The figure 1 illustrates an event model example 'Matching-SheetssActivity' and its sub-events. This activity is modeled with the help of clinicians to define the cognitive functioning status of patients and their motor skills. In this activity, the patient is asked to match a set of sheets (named A, B, C and D) in their specific placement dispersed over the room. The patient have to move from the coffee corner where there is the sheet named A, to the library (sheet B), to TV zone (sheet C, D) and go back to coffee corner.

Missed Observation

Occlusion and bad imaging conditions (e.g. dark, shadowed areas of the scene) are common conditions that prevent us from observing the occurrence of some events. When we miss the recognition of one of the sub-events the whole event is missed. To prevent from this, we propose a notion of 'utility' in the definition of the event model by associating a coefficient to each sub-event. Utility which is defined by a human expert expresses the importance or priority of sub-events for the recognition of the whole event. Its range is in the interval ]0,1], higher is the utility value higher is the importance of the sub-event in the recognition of the whole event. The value 1 means that the sub-event is required for the recognition. Figure 2 shows that the utility coefficient associated to 'PersonSlumping' is choosen lower (i.e. 0.2) than the utility for 'PersonStanding' and 'PersonSitting' (i.e. 0.6). We make the choice to consider that the detection the primitive state 'PersonSlumping' is not mandatory for the recognition of the event. This choice can be explained by the fact that the posture algorithm is more performant to detect 'PersonStanding' and 'Person-Sitting' than 'PersonSlumping'.

Identity Maintenance

Identity maintenance is necessary when there exist multiple identities that actually refer to the same mobile object. It is caused by lack of visual information (appearance, shape, etc.) to make unique identity connections across observation gaps. Identity maintenance is a primary source of uncertainty for activity recognition. It affects more precisely the recognition of long-term events.

Our approach to solve this issue in the level of event modeling is to propose the use of specific relation 'equal' in the representation of the event. More precisely, the identification whether the identifier of two objects A and B refer to the same object is represented by the relation equal(A, B).

In this work, the evaluation of this relation is done using appearance matching (e.g. 3D height, 3D width, etc). This logic relation is very useful in the case where the vision algorithm (i.e. tracking algorithm) fails to match and maintain the tracking identifier of the detected mobile object. Many other identifying contextual cues about identities can be discussed in the litterature. These cues are based on the individuals belongings, closed place activity, knowledge and appearance as pointed in [START_REF] Tran | Event modeling and recognition using Markov logic networks[END_REF].

Event Recognition: a Generic Framework

For the recognition process, an event model tree is computed as described in [START_REF] Vu | A Novel Algorithm for Temporal Scenario Recognition[END_REF]. The tree defines which sub-event triggers the recognition of which event: the sub-event which happens last in time triggers the recognition of the global event. The first step of the event recognition process is to recognize all the possible primitive statesby instantiating all the models with the detected objects. The second step consists in recognizing complex events according to the event model tree and the simple events previously recognized. The final step checks whether the recognized event at time t has been already recognized previously to update the event end-time or create a new event instance.

Probabilistic Elementary Event Recognition

The observations are inherently uncertain, hence a formal probabilistic approach is needed to reason under uncertainty. We propose to compute the conditional probability of the recognition of the event instance e belonging to an event model Ω given that the mobile physical objects in the model Ω have been observed and given that the constraints in the model Ω are satisfied by the observation O.

P (e ∈ Ω|ζ(Ω, O), V Ω = po O e ) = P (ζ(Ω, O)|e ∈ Ω) × P (V Ω = po O e |e ∈ Ω) × P (e ∈ Ω) P (ζ(Ω, O), V Ω = po O e ) (1)
• e ∈ Ω, e is an instance of event model Ω.

• ζ(Ω, O), the constraints of event model Ω are satisfied by observation O.

• V Ω = po O e , the tracked physical objects in the observation O correspond to physical object variables V in the model Ω of event instance e.

P (e ∈ Ω) is the prior probability that a certain scenario model Ω is detected. We can assume that all scenarios in a certain universe are equally probable, so as not to favor any scenario just because it happens more often. For example, the universe of the scenario models that describe a person posture is: (PersonStanding,PersonSitting and PersonBending).

P (e ∈ Ω) = 1 N br.ScenarioΩU niverse (2)
P (ζ(Ω, O)|e ∈ Ω)
is the probability that the constraints of the event model are verified given that the event e is true. This probability is computed as following:

P (ζ(Ω, O)|e ∈ Ω) = n i=1 (ζ(Ω, O) i ∧ e ∈ Ω) (e ∈ Ω ∧ V ζi Ω ∈ po O e ) ×P (ζ i (Ω, O)) (3) The term (ζ(Ω, O) i ∧ e ∈ Ω)
implies that only frames where event e have been identified (i.e. annotated) as an instance of Ω are considered, and for each constraint of event model Ω, the number of frames where it is satisfied are counted. The term (e ∈ Ω ∧ V ζi Ω ∈ po O e ) indicates that we only consider the frames of the training dataset where the event e is annotated and the physical objects are correctly tracked. The computation of P (ζ i (Ω, O)) is detailed in section 4.3. P (V Ω = po O e |e ∈ Ω) is the probability that the physical object variables in the event model Ω have been detected given that e is an event instance of the event model Ω. This probability is provided by the tracking algorithm as described in [START_REF] Chau | A multi-feature tracking algorithm enabling adaptation to context variations[END_REF].

The probability P (ζ(Ω, O), V Ω = po O e ) is computed based on the following equation (4):

P (ζ(Ω, O), V Ω = po O e ) = P (ζ(Ω, O), V Ω = po O e |e ∈ Ω) × P (e ∈ Ω)+ P (ζ(Ω, O), V Ω = po O e | e ∈ Ω ) × P ( e ∈ Ω ) (4)

Probabilistic Complex Event Recognition

The probabilistic recognition of complex event is defined as a hierarchical Bayesian inference. The objective is to recognize the complex event e given an observation O. What we want to calculate here is : 'The probability to recognize a complex event instance e belonging to an event model Ω given that the components (sub-events) in the model Ω are observed and the constraints in the model Ω are satisfied in the observation'. The proposed way of calculating this is:

P (e ∈ Ω|SE(Ω, O), ζ(Ω, O)) = P (SE(Ω, O)|e ∈ Ω) × P (ζ(Ω, O)|e ∈ Ω) × P (e ∈ Ω) P (SE(Ω, O), ζ(Ω, O)) (5)
• SE(Ω, O), the components (sub-events) of the model Ω are observed in O.

The different probability terms are calculated in the same manner that for the primitive event case.

Probabilistic Constraint Verification

In this work, we consider the spatial constraints related to the mobile object speed, position and closeness to a given contextual objects (e.g. person near TV), the constraints related to the posture (e.g. person is sitting) and we use the Allen [START_REF] Allen | Maintaining knowledge about temporal intervals[END_REF] temporal constraints. A main problem is the imprecision and uncertainty in the detection of the location of mobile objects due to low level detection errors (e.g. reflections, shadows or occlusions). Thus the verification of the constraint may fail. A solution to cope with this problem is to propose a probabilistic verification of the constraint. In the process of spatial constraint verification, we take into account (i) the geometrical uncertainty which is related to the verification of the constraint (e.g. verifying the spatial constraint 'person-inside-zone' consists in the geometrical computation whether a point representing the person is inside a polygon representing the zone). The first step consists in computing the distance dist of the person to the contextual objects (i.e. zone), the second step is to find a probability distribution function (PDF) that maximize the value of probability when the distance dist is small and a minimum value when the distance dist is big. We validate experimentally that the distribution of the distances fit into the Gaussian distribution denoted by N (µ, σ) (Eq. 6), the mean µ and the standard deviation σ are learned off-line.

N (µ, σ) = 1 √ 2πσ exp(- (dist -µ) 2 2σ 2 ) (6)
We take also into account (ii) the uncertainty of the attribute values due to noisy data and low-level algorithm errors. This type of uncertainty handling is described in section 4.4 by proposing a new dynamic model for the re-estimation of the attribute values to deal with noisy data..

Dynamic Model for temporal attribute filtering

Observations with real video sequences can be corrupted by noise, thus our goal is to estimate more accurately an attribute value given its observed value. The proposed process of the temporal filtering of attributes works in two steps as described in [START_REF] Romdhane | Probabilistic Recognition of Complex Events[END_REF]: -The first step (1) consists in computing the expected value a exp of an attribute a at the current instant t c given the estimated value of a and its velocity at the previous time t p .

-The second step ( 2) is to compute the estimated value a est of the attribute based on the previous one.

-The final value ā of the attribute is the mean between the expected and the estimated values of the attribute weighted by the expected and estimated reliability values

Dealing with the Tracking Identifier

The recognition of an event over time needs the maintaining of the same identifier for each mobile object when recognizing its sub-events, otherwise it will be considered as a different object. To deal with this tracking error at the event detection level, we propose the use of the recognition history of an event e, {e 1 , ..., e t-2 , e t-1 }: the recognized events over time are stored in a buffer and for each time t, and for each detected event e, we propose to look at the change of its physical objects identifier. If the identifier of a physical object changes suddenly and/or for a short period of time, we do not consider the new identifier and we maintain the last identifier of the physical object.

Experimental Results

We have evaluated the event recognition accuracy of our algorithm on two real world health care applications (Tab.1and Tab.2) and have compared our results with the approach proposed in [START_REF] Vu | A Novel Algorithm for Temporal Scenario Recognition[END_REF] (Tab.3). For the first dataset, Video recordings of 37 patients are used to assess the proposed framework performance. These patients are part of a clinical trial for Alzheimer's study and they are asked to perform a set of activities. video dataset will be soon public. The second dataset consists in monitoring elderly observed in an experimental laboratory during 4 hours, the data is available on wwwsop.inria.fr/members/Francois.Bremond/topicsText/gerhome Project.html.

Table . 1 shows that we manage to successfully recognize primitive states (e.g. 'Close phone': 85.7%, 'In coffee Corner': 98%) with a low false detection rate. By avoiding miss detections of primitive states and using a flexible event description, the proposed system recognizes the complex events with a recognition rate about 58% for the 'Matching-SheetsActivity' event and 100% for the event 'Move from reading zone to coffeeCorner'(Tab. 1).

The comparison (Table 2) shows that the recognition rate of the complex event MatchingSheetssActivity in the case of the proposed algorithm (58%) is higher than the deterministic algorithm [START_REF] Vu | A Novel Algorithm for Temporal Scenario Recognition[END_REF] (38%). This can be explained by the fact that the deterministic algorithm fails to recognize some primitive states because the person was not correctly detected. However, the proposed algorithm manages to recognize the primitive state and as a consequence the complex event. It can also be explained by the fact that the algorithm [START_REF] Vu | A Novel Algorithm for Temporal Scenario Recognition[END_REF] does not manage the loss of tracking identifier which can deeply affect the recognition of long-term events even though its sub-events are detected.

We have evaluated also our approach on the 'Building Entrance' real world videos of ETISEO [START_REF] Nghiem | ETISEO, performance evaluation for video surveillance systems[END_REF] dataset (fig. 4). We have selected this public dataset because it has been used previously in several work [START_REF] Lavee | Propagating Uncertainty in Petri Nets for activity Recognition[END_REF].

Conclusions

We have proposed a description-based event recognition approach to describe and recognize video activities. The proposed approach allows flexible modeling of activities and manages the uncertainty of recognition. We have detailed the conditional probability estimation of activities as a Bayesian process. We have presented how we manage low level uncertainty at the level of event modeling and at the level of event recognition. The proposed approach recognizes successfully activities of real world videos. We have finally compared our approach with the state of the art showing how the fexible modeling and the probabilistic reasoning can improve the results of real-time event recognition.

Figure 1 .

 1 Figure 1. Event Models.

Figure 2 .

 2 Figure 2. Utility coefficient associated to each sub-event of the event model 'PersonStandingUp-FromChair'.

Figure 3 .

 3 Figure 3. Activity detection evaluated on Health care videos.

Table 2 .

 2 Recognition Results of the proposed algorithm on Gerhome dataset: the recognition rate (% R), the false positive (FP) and the false negative (FN). The ground truth GT corresponds to 4 videos sequences, with a total of 9452 frames, 8 fps.

Figure 4 .

 4 Figure 4. Illustration of the Etiseo activity detection. Algorithm GT % R FP FN Approach [25] MatchingSheetssActivity 31 38 0 19 Proposed algorithm MatchingSheetssActivity 31 58 1 13

Table 1 .

 1 The length of each video sequence is about 12(±5) min, 8 fps. The Recognition Results of the proposed algorithm: the recognition rate (% R), the false positive (FP) and the false negative (FN). 37 patients, 12(±5) min, 8 fps.

	Events	GT % R FP FN
	Person sitting	21 76.2	6	5
	Close phone	14 85.7	0	2
	In coffee Corner	51	98	3	1
	In reading zone	28	100	5	0
	In zone library	19	95	2	1
	In zone TV	14	100	2	0
	Move from coffeeCorner to reading zone 17	100	0	0
	Move from reading zone to coffeeCorner 15	100	2	0
	Move from coffeeCorner to library zone	11	90	2	1
	Move from library zone to coffeeCorner	10	100	0	0
	Person reading	14	92	2	1
	MatchingSheetssActivity	31	58	1	13

Table 3 .

 3 Comparison of recognition rate (% R), the false positive (FP) and the false negative (FN) of the proposed algorithm with the state of the art algorithm. The ground truth GT correspond to 31 videos sequences (12(±5) min, 8 fps)