Denis Serre

Alexis F Vasseur

About the relative entropy method for hyperbolic systems of conservation laws

We review the relative entropy method in the context of first-order hyperbolic systems of conservation laws, in one space-dimension. We prove that contact discontinuities in full gas dynamics are uniformly stable. Generalizing this calculus, we derive an infinitedimensional family of Lyapunov functions for the system of full gas dynamics.

Systems of conservation laws and entropies

We are interested in vector fields u(x, t) obeying first-order PDEs. The space variable x and time t run over the physical domain R d × (0, T ). The field takes values in a convex open subset U of R n .

A conservation law is a first-order PDE of the form

∂ t a + div x b = 0.
The terminology refers to the fact that weak solutions obey the identity

d dt Ω a(x, t) dx + ∂Ω b • ν ds(x) = 0,
for every regular open subdomain Ω ⊂ R d . Hereabove ν is the outer normal and ds is the area element over the boundary. Actually, the PDE is often derived from the latter identity, which expresses a physical principle such as conservation of mass, momentum, species, charge, energy, ... See C. Dafermos's book [START_REF] Dafermos | Hyperbolic conservation laws in continuum physics[END_REF] for a thorough description of this correspondance.

A given physical process is modelled by one or several conservation laws, which are written in a compact form as ∂ t u + Div x F = 0, where u is the field of conserved quantities, taking values in some open subset U of R n , and F , the flux, takes values in (n × d)-matrices. Mind that the operator Div x with a capital letter represents the row-wise divergence of a matrix-valued field. The system is closed when F is given as a function of u, in the form F = f (u) where f : U → R n×d is a given smooth field. We then have

(1) ∂ t u + Div x f (u) = 0, which must be understood in the sense of distributions. One speaks of a scalar equation if n = 1, and of a system if n ≥ 2. Mind that such a closure excludes dissipation processes such as viscous effects or thermal diffusion. Instead, it assumes a thermal equilibrium everywhere at any time.

The processes that we have in mind obey a kind of second principle of thermodynamics. Mathematically, this can be expressed in terms of one additional conservation law [START_REF] Chen | Vacuum states and global stability of rarefaction waves for compressible flow[END_REF] ∂ t η(u) + div q(u) = 0.

We say that a function η satisfying (2) for every C 1 -solution of ( 1) is a mathematical entropy of system (1), and q is its entropy flux. In order that (2) be compatible with (1), we have the linear differential relations In order that (2) brings some new information, it has to follow from (1) in a non-trivial way, by multiplying the system by the differential form dη(u). In particular, η should not be affine ; affine functions are called trivial entropies. When n ≥ 3, or when n, d ≥ 2, the number of constraints in (3) exceeds that of the unknown functions η, q α , and therefore non-trivial entropies are exceptional objects : if a system (1) is chosen at random, it should not admit any non-trivial entropy. However, it is a well documented fact that systems modelling physics do admit at least one non-trivial entropy η ; somehow, they are exceptional. It turns out that most of them admit only this entropy, in the sense that the solution set of ( 3) is spanned by η and the trivial entropies. Mind that this is not true if either n = 1, or when n = 2 and d = 1, because then the number of constraints does not exceed the number of unknowns.

The additional entropy η is often a convex smooth function (and then the phase space U is convex), strongly convex in the sense that the Hessian matrix D 2 η a is positive definite at every a ∈ U. It may happen that η be non convex, when (1) is an artificial first-order form of a system of second-order PDEs in several space dimensions, but then η has a related quasi-convex property. For the sake of simplicity, we shall assume throughout this paper that η is strongly convex. For a more general situation, one refers to the works [START_REF] Brenier | Hydrodynamic structure of the augmented Born-Infeld equations[END_REF][START_REF] Serre | Hyperbolicity of the non-linear models of Maxwell's equations[END_REF].

As mentionned above, if m is affine and λ is a positive constant, then u → λη(u) + m(u) is another strongly convex entropy, associated with the flux λ q + m • f . This observation is at the basis of the notion of relative entropy. Given a ∈ U, we define another entropy, still strongly convex, by u → η(u|a

) := η(u) -η(a) -dη a • (u -a).
This is an affine correction of η. The corresponding entropy flux is

u → q(u; a) := q(u) -q(a) -dη(a) • (f (u) -f (a)).
We warn the reader that the latter field is not an affine correction of u → q(u). This is why we employ a semi-colon, where we put a bar instead in the definition of η(u|a). The notation q(u; a) is actually a bit misleading, suggesting that it depends linearly on q. As a matter of fact, it may happen that q(u) ≡ 0, while q(u; a) is non-trivial. We shall give later on an example of such a paradox. The function (u, a) → η(u|a) is the relative entropy. Because η is convex, η(u|a) is positive away from the diagonal u = a. We point out that the partial function a → η(u|a) is not an entropy, unless η was quadratic. The strong convexity tells us that ( 4)

η(u|a) ≥ ω a |u -a| 2
for some ω a > 0 when u belongs to a compact neighbourhood of a. Therefore, estimating η(u|a) dx is a way to estimate u(•, t) -a in L 2 . Suppose for instance that u(•, t) -a has compact support, then the conservation law (2) tells us

R d η(u(x, t)|a) dx = R d η(u(x, 0)|a) dx, whence ω a u(•, t) -a 2 L 2 (R d ) ≤ R d η(u(x, 0)|a) dx.
This expresses the L 2 -stability of constant states.

The primary role of the entropy identity is therefore to provide an a priori estimate in L 2 , or at least in some appropriate Orlicz space. It is at work in the existence theory for the Cauchy problem too, although it is far from being sufficient. Because the flux is nonlinear, the existence theory requires estimates of some derivatives. These cannot be achieved directly, but it was found by Kato, Gårding and others that H s -estimates are valid, at least locally in time, whenever s > 1 + d 2 , for systems admitting a symmetrization in Friedrichs' sense. A symmetrization is a change of unknowns u → z by which (1) is transformed into

A 0 (z)∂ t z + d α=1 A α (z)∂ α z = 0,
where the matrices A 0 (z), . . . , A d (z) are symmetric, and A 0 (z) is positive definite. It was observed by Godunov [START_REF] Godunov | An interesting class of quasi-linear systems[END_REF] and independently by Friedrichs & Lax [START_REF] Friedrichs | Systems of conservation equations with a convex extension[END_REF] that systems of conservation laws admitting a strongly convex entropy can be symmetrized. One can either choose the conjugate unknowns z = ∇ u η, or take z = u and multiply the system by A 0 = D 2 η(u). We therefore derive the fundamental local existence result, see for instance Dafermos' book [START_REF] Dafermos | Hyperbolic conservation laws in continuum physics[END_REF], Theorem 1.1 If (1) is endowed with a strongly convex entropy, then the Cauchy problem is locally (in time) well-posed in the space

H s uloc (R d ) whenever s > 1 + d 2 .
The subscript "uloc" means "locally uniformly" : the norm is the supremum over all h ∈ R d of the H s -norm of the restriction to the unit ball centered at h. We point out that the threshold s > d+ 1 2 means that

H s uloc (R d ) ⊂ C 1 (R d )
, by Sobolev embedding. Therefore the theorem speaks about classical solutions of (1).

The question of global solutions

Let a ∈ U be given. The field ā(x, t) :≡ a is a particular solution of (1). Its stability can be analyzed, in a first instance, by linearizing the system about a. One finds the constant coefficient system

∂ t U + α df α (a)∂ α U = 0, or equivalently A 0 (a)∂ t Z + d α=1 A α (a)∂ α Z = 0.
This linear system propagates planar waves in direction ξ ∈ S d-1 at finite velocities λ 1 (a; ξ) ≤ • • • ≤ λ n (a; ξ) that are the eigenvalues of the matrix

M (a; ξ) := A 0 (a) -1 α ξ α A α (a).
The fact that this matrix-valued symbol is diagonalisable with real eigenvalues is classical. The diagonalisation can be performed uniformly with respect to ξ. This is referred to as the hyperbolicity of the linearized system. By extension, we say also that (1) is hyperbolic. Therefore every closed system of first-order conservation laws endowed with a strongly convex entropy is hyperbolic.

By linear superposition, one may design linear waves that are non-planar. They still propagate at finite velocity in the direction normal to the front.

Because of the non-linearity, the velocities depend on the state a ∈ U. This usually causes a loss of regularity in finite time for the solutions of (1). This can be seen even in the simplest nonlinear equation, named after Burgers,

∂ t u + ∂ x u 2 2 = 0, (n = d = 1).
Then the space derivative y := ∂ x u satisfies

(∂ t + u∂ x )y + y 2 = 0.
The former equation, written as (∂ t + u∂ x )u = 0, is a transport equation, telling us that u(X(t), t) ≡ u(X(0), 0) along the integral curves of dX dt = u(X, t) (the wave velocity is therefore u itself). The latter is a Riccati's equation along the same curves, whose solution blows up in finite time whenever y(X(0), 0) is negative. Therefore the solution of the forward Cauchy problem with initial data u 0 blows up in finite time in the C 1 -norm, unless u 0 is monotone non-decreasing.

We infer that for most systems of the form (1), and for most initial data, the classical solution exists only on some finite time interval. For practical applications it is however necessary to consider large-time, say global, solutions. This requires considering non-differentiable solution, for which (1) is interpreted in the distributional sense. To this end, it sufficies that u be a locally measurable bounded field. Within this framework, the blow-up described above is usually resolved by the development of discontinuities, which propagate along hypersurfaces. Let Σ be such a discontinuity front in R d × (0, T ), with unit normal n = (n 1 , . . . , n d , n 0 ), and let u ± be the limits of u(x, t) at some point (x, t) ∈ Σ from either side. Then it is well-known that (u -, u + ; n) satisfies the Rankine-Hugoniot condition [START_REF] Chen | Stability of Riemann solutions with large oscillation for the relativistic Euler equations[END_REF] n 0 (u

+ -u -) + α n α (f (u + ) -f (u -)) = 0.
Notice that for a genuine discontinuity, one has (n 1 , . . . , n d ) = 0. Denoting [h] := h(u + )-h(u -), Rankine-Hugoniot can therefore be written in the compact form

[f (u)] • ν = σ[u],
where ν ∈ S d-1 is the normal of the spatial trace of the front and σ is the normal velocity.

The possibility for solutions to (1) to admit discontinuities is not the end of the story. Although this extension makes up for the lack of classical solutions, it has the flaw that rough solutions are way too many. This is where the second principle comes into play, with the role of selecting the physically admissible solutions. Mathematically speaking, one first observes that the additional conservation law (2) is not any more a consequence of (1), because multiplying (1) by dη(u) does not make sense, and the chain rule does not apply for non-Lipschitz fields. Instead, one argues that first-order conservation laws are actually the limit (as some parameter > 0 tends to zero) of some second-order system that includes a natural diffusion process. For instance, the Euler equation of a perfect fluid is the limit of the Navier-Stokes-Fourier system. The latter system has a parabolic type which makes the solution smooth for t > 0 ; it is therefore liable to multiply it by dη(u), and apply the chain rule. One finds then that its solutions satisfy some differential inequality ∂ t η(u ) + div x q(u , ∇ x u ) ≤ 0.

Passing to the limit, we obtain, at least formally, the distributional inequality [START_REF] Brenier | Hydrodynamic structure of the augmented Born-Infeld equations[END_REF] ∂ t η(u) + div x q(u) ≤ 0, called the entropy inequality. We therefore declare that an admissible solution (1) must satisfy [START_REF] Brenier | Hydrodynamic structure of the augmented Born-Infeld equations[END_REF]. We speak of an entropy solution. Remark that [START_REF] Brenier | Hydrodynamic structure of the augmented Born-Infeld equations[END_REF] does not yield any additional information in zones where u is a Lipschitz function. However, it tells us that across a discontinuity Σ, (u -, u + ; n) satisfies

(7) [ q(u)] • ν ≤ σ[η(u)],
where u ± = lim h→0 + u(x ± hν, t). The role of the entropy condition is therefore to restore the uniqueness in the Cauchy problem, while leaving the door open to the existence. We don't know so far if this role is successful, except in a few instances. We have a complete and satisfactory theory for scalar equations in any dimension, due to Kruzkhov. A. Bressan and collaborators showed that the Cauchy problem for one-dimensional systems is well-posed as long as the initial data has small total variation, see [START_REF] Bressan | Well-posedness of the Cauchy problem for nn systems of conservation laws[END_REF]. When d = 1 and n = 2, R. DiPerna succeeded to prove the existence of an entropy solution for large initial data, if the system is sufficiently non-linear, by using the compensated compactness method initiated by L. Tartar. When n ≥ 3, the mere existence of an entropy solution for large data is still unknown. The uniqueness of entropy solution is doubtful in absence of BV regularity ; C. de Lellis and L. Székelyhidi provide actually counter-examples [START_REF] De Lellis | On admissibility criteria for weak solutions of the Euler equations[END_REF].

The method of relative entropy

The method of relative entropy is a technique devised by R. DiPerna [START_REF] Diperna | Uniqueness of solutions to hyperbolic conservation laws[END_REF] and C. Dafermos [START_REF] Dafermos | The second law of thermodynamics and stability[END_REF][START_REF] Dafermos | Stability of motions of thermoelastic fluids[END_REF] in order to estimate the L 2 -distance between two solutions, one of both being smooth or at least not too weak. It adapts to the context of first-order conservation laws the weak-strong estimates that is well-known for 3-D Navier-Stokes equation, for instance.

If u and v are smooth solutions of (1), say Lipschitz continuous, then the relative entropy, evaluated at (u, v), satisfies the identity

∂ t η(u|v) + div x q(u; v) = -R where R := α ∂ α (dη(v)) • f α (u|v),
with the obvious definition for f (u|v) (affine correction of f (u)). If u and v agree outside of some relatively compact domain Ω ⊂ R d , we deduce

d dt Ω η(u|v) dx = - Ω R dx.
The source term R can be bounded by

C ∇ x v ∞ |u -v| 2 .
Using (4), we infer that

d dt Ω η(u|v) dx ≤ C Ω η(u|v) dx, C := C ∇ x v ∞ ω .
The Gronwall inequality thus gives an estimate

Ω η(u|v) dx ≤ e C t Ω η(u 0 |v 0 ) dx,
where u 0 , v 0 are the initial data. This is the way uniqueness is proved for Lipschitz solutions, but also stability : if u 0 and v 0 are close to each other, then so are u(t) and v(t). Mind however that the distance between u(t) and v(t) may increase unboundedly as t → +∞. We speak of finite-time stability. In addition, because of the propagation of the information at finite velocity, the correct estimate is instead (again, see Dafermos' book)

Ω η(u|v) dx ≤ e C t Ω+B(0;V ) η(u 0 |v 0 ) dx,
where V is a suitable constant, larger than the wave velocities. When v is Lipschitz but u is only a bounded entropy solution, one still has

∂ t η(u|v) = ∂ t η(u) -∂ t η(v) -dη(v) • (∂ t u -∂ t v) -D 2 η v (∂ t v, u -v),
with a analogous formula for div x q(u; v). Using then the system for u and v, the entropy inequality for u and the entropy equality for v, we obtain the distributional inequality (8) ∂ t η(u|v) + div x q(u; v) ≤ -R.

From (8), we can reach the same conclusion as when u and v were both Lipschitz. We therefore have uniqueness and finite-time stability as long as the Cauchy problem admits a Lipschitz continuous solution v. This leaves open the uniqueness question beyond the blow-up time (except in the cases covered by Bressan's work). Such a result is very similar to the weakstrong stability/uniqueness statement for the incompressible Navier-Stokes in dimension three.

When v is globally defined, that is for all t > 0, and is Lipschitz, one may wonder whether the source term R remains non-negative, in which case the total relative entropy

R d η(u|v) dx
is a non-increasing function of time. We then say that v is uniformly stable. This happens in gas dynamics for solutions of the 1-d Riemann problem when only rarefaction waves occur (G.-Q. Chen & coll. [START_REF] Chen | Vacuum states and global stability of rarefaction waves for compressible flow[END_REF][START_REF] Chen | Stability of rarefaction waves and vacuum states for the multidimensional Euler equations[END_REF][START_REF] Chen | Uniqueness and asymptotic stability of Riemann solutions for the compressible Euler equations[END_REF][START_REF] Chen | Stability of Riemann solutions with large oscillation for the relativistic Euler equations[END_REF]), and also for multi-dimensional expanding flows (D. Serre [START_REF] Serre | Long-time stability in systems of conservation laws, using relative entropy/energy[END_REF]).

Stability of discontinuities

From now on, we restrict to the one-dimensional situation, but we consider the stability of a one-dimensional simple discontinuity

v(x, t) = u , if x < σt, u r , if x > σt.
Without loss of generality, we may assume σ = 0, up to replacing x by x -σt and f (u) by f (u) -σu. We thus restrict to a steady discontinuity, meaning that f (u ) = f (u r ) and q(u r ) ≤ q(u ).

Away from x = 0, the inequality ( 8) is still valid, while R ≡ 0, because v is constant on either sides of x = 0. We therefore obtain d dt R η(u|v) dx ≤ q(u + ; u r ) -q(u -; u ), where u ± stand for the right and left limits of u(x, t) as x → 0. The discontinuity will therefore be stable if the right-hand side, a numerical function of (u -, u + ), is non-positive. Unfortunately, this is usually not the case; the interested reader might compute a Taylor expansion and find that its sign is non constant, but let us present a more illuminating argument. Suppose ( 1) is a scalar equation with f > 0. Take u 0 = v 0 + φ, where φ is bounded, compactly supported. It is classical that the initial disturbance is absorbed by the shock: after some finite time T > 0, u coincides with the shifted shock v(• -h). The conservation of mass determines h

= 1 [u] R φ dx. With η(s) = 1 2 s 2 , that is η(a|b) = 1 2 (a -b) 2 , we deduce that R η(u|v) dx = 1 2 [u] R φ dx .
On the other hand, we have η(u

0 |v 0 ) = 1 2 φ 2 . Because the inequality [u] R φ dx ≤ R φ 2 dx
is violated for some (many) disturbances φ, we see that t → R η(u|v) dx is not a decreasing function in general. [START_REF] Leger | L 2 -stability estimates for shock solutions of scalar conservation laws using the relative entropy method[END_REF][START_REF] Leger | Relative entropy and the stability of shocks and contact discontinuities for systems of conservation laws with non-BV perturbations[END_REF] introduced the following refinement of the method. The example above suggests to estimate the distance between u(t) and v by the relative entropy, up to a shift. We thus define a functional

N. Leger & A. Vasseur

E(t) := inf h∈R R η(u(x, t)|v(x + h)) dx = inf h∈R h -∞ η(u|u ) dx + +∞ h η(u|u r ) dx .
The quantity in parenthesis is a continuous function of h, which tends to +∞ as h → ±∞. Therefore the infimum is attained at some h. If u has left and right limits at h, the left and right h-derivatives at h must be negative and positive respectively:

η(u -|u ) ≤ η(u -|u r ), η(u + |u ) ≥ η(u + |u r ).
If u is continuous at h, this tells us η(u|u ) = η(u|u r ) ; in other words, ū := u( h) belongs to the hyperplane defined by [dη]

• ū = [dη(u) • u -η(u)], which separates u from u r . If u + = u -, Rankine-Hugoniot gives instead f (u + ) -f (u -) = X (u + -u -)
, where we may suppose that X ≡ h locally (isolated times are not meaningful for the derivative), and therefore X = h . In conclusion, (u -, u + ) obey to severe constraints in both situations. Because

E (t) ≤ q(u + ; u r ) -q(u -; u ) -h (η(u + |u r ) -η(u -|u )) =: D(u ± ; u ,r ),
we see that the discontinuity v is stable up to a shift if D ≤ 0 for every pair (u -, u + , h ) satisfying the constraints above. We point out that the definition of D is not ambiguous: h is well-defined (by R.-H.) in the discontinuous case, while D = q(u; u r )-q(u; u ) in the continuous case. With this approach, Leger and Vasseur proved Theorem 3.1 For a scalar equation with a convex flux, shocks are uniformly stable up to a shift.

In terms of the entropy 1 2 u 2 , this can be viewed as an L 2 -contraction property: t → inf h uv(• -h) L 2 is non-increasing. We warn the reader that this is true only if v is a pure shock. When u, v are arbitrary entropy solutions, we only know the contraction in the L 1 -norm, which is a part of Kruzkhov's theory.

Using two entropies

In [START_REF] Serre | L 2 -type contraction for systems of conservation laws[END_REF], the authors applied the idea described above to systems (n ≥ 2). Unfortunately, most systems resist to the method. A new tool was therefore needed, which has been elaborated recently by Vasseur. Instead of one entropy η, one uses two entropies η ± to measure the distance from u to v. Let us consider the quantity

E(t) := 0 -∞ η -(u|u ) dx + +∞ 0 η + (u|u r ) dx.
Of course, we may incorporate a shift:

E min (t) := inf h h -∞ η -(u|u ) dx + +∞ h η + (u|u r ) dx .
In practice, η + and η -are proportional, because most systems admit only one independent nontrivial entropy. Say η ± = a ± η with a ± positive constants. Remark that the uniform stability (in terms of the decay of E) implies the stability up to a shift, due to the space-shift invariance of the Cauchy problem.

A calculation analogous to that in the scalar case can be made. If v 0 is a steady Lax shock associated with a genuinely nonlinear field, and if u 0 = v 0 + φ is a compactly supported perturbation where φ is small, then the asymptotic behaviour has been described by T.-P. Liu [START_REF] Liu | Pointwise convergence to N -waves for solutions of hyperbolic conservation laws[END_REF]. It consists of a superposition of so-called N -waves (which decay in L 2 -norm like t -1/4 ), of linear waves that just propagate at constant velocity, and of a shift of the shock from x = 0 to x = h. To determine h, we split the mass m = R φ dx into three parts X -+ h[u] + X + , where X -(resp. X + ) belongs to the stable (resp. unstable) subspace of df (u ) (resp. df (u r )). All these waves asymptotically separate from each other and therefore the limit of E(t) consists of the sum of contributions of the shift and of the linear waves. In particular, a decay of E(t) for t > 0 would imply that |h|η(u r |u ), or |h|η(u |u r ) is not greater than

0 -∞ η -(u + φ|u ) dx + +∞ 0 η + (u r + φ|u r ) dx ∼ R φ 2 dx.
This is obviously false, and therefore the uniform stability of shock waves cannot be obtained without involving a shift. As a matter of fact, Vasseur showed recently that the stability up to a shift may hold true for "extreme shocks", that is the slowest and the fastest shocks. The argument presented above does not settle the case of contact discontinuities, because then the asymptotics does not involve a shift. We have at least a positive result in the case of full gas dynamics. The system consists of conservation of mass, momentum and energy. In Lagrangian variables (where x is mass), it writes (9)

∂ t τ = ∂ x w, ∂ t w + ∂ x p(τ, e) = 0, ∂ t (e + 1 2 w 2 ) + ∂ x (wp) = 0,
where τ is the specific volume, w the flow velocity and e the internal energy. The pressure p is given by an equation of state p(e, τ ). Thermodynamics tells us that there exists a positive function θ(e, τ ) (the temperature) and a concave function s(e, τ ) (the entropy) satisfying the Gibbs relation θds = de + pdτ . The second principle is then that ∂ t s ≥ 0 for observable flows.

In other words, η = -s is an entropy in the mathematical sense, and admissible flows should satisfy the entropy inequality. Let us point out that q ≡ 0 in this example.

Theorem 4.1 Consider the 1-D system of full gas dynamics in Lagrangian variables. Then the contact discontinuity (u , u r ) is uniformly stable in the sense that

t → E(t) := - 0 -∞ θ s(u|u ) dx - +∞ 0 θ r s(u|u r ) dx
is non-increasing, for every solution u equal to u /u r as x is sufficiently large and negative/positive.

Of course, we may just ask that u(•, t) -u ∈ L 2 (R -) and u(•, t) -u r ∈ L 2 (R + ). Our statement has a counterpart when one uses the Eulerian variables, where x is then a space coordinate.

Proof

For x > 0, we have ∂ t s(u|u r ) + ∂ x q(u; u r ) ≤ 0, where q(a; b) = ds b • (f (a) -f (b)). We deduce

E (t) ≤ θ ds • (f --f (u )) -θ r ds r • (f + -f (u r ))
where f ± denote the right/left traces of f (u) along x = 0. The conservation laws (1) tells us, not only that these traces are well defined as bounded measurable functions, but also that they coincide. Because f (u r ) = f (u ), we have w r = w and p r = p , and therefore θ ds = θ r ds r . We thus have

E (t) ≤ (θds) ,r • (f --f -f + + f r ) = 0.
Remarks. -Full gas dynamics admits infinitely many independent entropies g • s, where g is any numerical function. Such entropies are strongly convex when g < 0 and g ≥ 0. We could therefore have chosen η ± = g ± • s in the estimate above. However the derivation of the entropy inequality from the Navier-Stokes-Fourier system works only for one entropy, namely -s (see [START_REF] Serre | The structure of dissipative viscous system of conservation laws[END_REF]). Therefore our estimates with η ± = -θ ,r s are the only one with physically relevance. -The calculation above can be adapted to more general systems for which λ ≡ 0 is a simple eigenvalue of df . The image of U under u → (f (u), q(u)) is a manifold of codimension 2. We ask that it be contained in a hyperplane, that is αq + L • f ≡ cst, with α = 0, say α > 0. Up to replacing η by αη + L(u), we may assume that q ≡ 0. One shows that there exists an analogue of the temperature θ(u) such that if (u , u r ) is a steady contact discontinuity, then [θdη] = 0. Therefore the analogue of Theorem 4.1 holds true:

t → E(t) := 0 -∞ θ η(u|u ) dx + +∞ 0 θ r η(u|u r ) dx
is non-increasing, for every solution u equal to u /u r as x is sufficiently large and negative/positive.

Lyapunov function for full gas dynamics

The calculus above suggests a fruitful generalization. On the one hand, we consider special solutions of (9) of the form v ≡ v(x) where the velocity w and the pressure p are constant. For instance, v could be a pure contact discontinuity as above. Such fields are parametrized by the choice of a positive measurable τ (x), bounded by below and above, and by the constants ( w, p). The internal energy is obtained by solving the equation p(τ (x), e(x)) = p. These solutions are precisely what we called linear waves in Section 4. Given a linear wave v, we may define a functional

L v [u] := - R θ(v)s(u|v) dx,
provided that u -v ∈ L 2 (R) 3 . In the periodic case, where the domain is R/M Z, we define instead

L v [u] := - M 0 θ(v)s(u|v) dx.
We have a seemingly new result:

Theorem 5.1 The functionals L v are Lyapunov functions: for every entropy solution of ( 9) such that u(t) -v ∈ L 2 , the function t → L v [u(t)] is non-increasing.

Proof

We first prove the result when τ is a smooth function. We have The differential form has constant coefficients and therefore we have ∂ t (θ(v)s(u|v)) ≥ ∂ x (ω • f (u)). Integrating in space, it comes d dt L v [u(t)] ≤ 0. If τ is not smooth, we may approach every function τ by a sequence τ = τ * ρ(•/ ), which converges boundedly almost everywhere. Then L v [u(t)] → L v [u(t)]. The monotony passes to the limit.

= 1 ,

 1 . . . , d, j = 1, . . . , n.

∂ 2 w 2 )

 22 t (θ(v)s(u|v)) = θ(v)(∂ t s(u) -ds v ∂ t u) ≥ θ(v)ds v ∂ x f (u) = (d(e + 1 -wdw + pdτ )∂ x f (u) =: ω(∂ x f (u)).

This work was partially supported by NSF grant DMS-1209420.


Giovanni Neglia
email: giovanni.neglia@inria.fr

Damiano Carra
email: damiano.carra@univr.it

Mingdong Feng
email: mfeng@akamai.com

Vaishnav Janardhan
email: vjanardh@akamai.com

Pietro Michiardi
email: pietro.michiardi@eurecom.fr

Dimitra Tsigkari
email: dimitra.tsigkari@inria.fr

Access-time aware cache algorithms

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The hit probability is a well-known key metric for caching systems: this is the probability that a generic request for a given content will be served by the cache. Most of the existing literature implicitly assumes that a hit occurs if the content is stored in the cache at the moment of the request. In practice, however, in real caching systems the actual hit rate is often limited by the speed at which the cache can serve requests. In particular, Hard-Disk Drive (HDD) access times can be the key factor capping cache performance.

As an illustrative example, Fig. 1 shows the percentage of CPU and HDD utilization, as reported by the operating system, over two days in the life of a generic caching server. As the amount of requests varies during the day, the resource utilization of the caching server varies as well: during peak hours, HDD utilization can exceed 95%. Such loads may cause the inability to serve a request even if the content is actually cached in the HDD. In case of a pool of cache servers, a solution based on dynamic load balancing may alleviate this problem by offloading the requests to another server. Nevertheless, this solution has its own drawbacks, because the rerouted queries are likely to generate misses at the new cache.

In this paper, we study if and how the RAM can be used to alleviate the HDD load, so that the cache can serve a higher rate of requests before query-rerouting becomes necessary.

The idea to take advantage of the RAM is not groundbreaking. Modern cache servers usually operate as a hierarchical cache, where the most recently requested contents are stored also in the RAM: upon arrival of a new request, content is first looked up in the RAM; if not found, the lookup mechanism targets the HDD. Hence, the RAM "shields" the HDD from most of the requests. The question we ask in this paper is: what is the optimal way to use the RAM? Which content should be duplicated in the RAM to minimize the load on the HDD? We show that, if content popularities are known, the problem can be formulated as a knapsack problem. More importantly, we design a new dynamic replacement policy that, without requiring popularity information to be known, can implicitly solve our minimization problem. Our policy is a variant of q-LRU. In q-LRU, after a cache miss, the content is stored in the cache with probability q and, if space is needed, the least recently used contents are evicted. We call our policy q i -LRU, because we use a different probability q i for each content i. The value q i depends on the content size and takes into account the time needed to retrieve contents from the HDD. Simulation results on real content request traces from the Akamai's Content Delivery Network (CDN) [START_REF] Nygren | The Akamai Network: A Platform for High-performance Internet Applications[END_REF] show that our policy achieves more than 80% load reduction on the HDD with an improvement between 10% and 20% in comparison to the standard LRU.

The paper is organized as follows. In Sec. 2 we formalize the problem and illustrate the underlying assumptions. In Sec. 3 we present the policy q i -LRU and prove its asymptotic optimality. We evaluate its performance under realworld traces in Sec. 4. Related works are discussed in Sec. 5. Some proofs are in the companion report [START_REF] Neglia | Access-time aware cache algorithms[END_REF].

Model

In this section, we illustrate our main assumptions about HDD operation and content request process and then formalize our optimization problem.

Hard Disk Service Time

Our study relies on some assumptions about the load imposed on the HDD by a set of requests. Consider a single file-read request for content i with size s i . We call service time the time the HDD works just to provide content i to the operating system. Our first assumption is that the service time is only a function of content size s i . We denote it as T (s i ). 1 The second assumption is that service times are additive, i.e. let A be a set of contents, the total time the HDD works to provide the contents in A is equal to i∈A T (s i ), independently of the specific time instants at which the requests are issued. Note that we are not assuming any specific service discipline for this set of requests: they could be served sequentially (e.g. in a FIFO or LIFO way) or in parallel (e.g. according to a generalized processor sharing). 2 But we are requiring that concurrent object requests do not interfere by increasing (or reducing) the total HDD service time.

The analytical results we provide in Sect. 3, which is the main contribution of our work, do not depend on a particular structure of the function T (s i ). Nevertheless, we describe here a specific form based on past research on HDD I/O throughput [3][4], and based on our performance study of disk access time observed in caching servers. We will refer to this specific form later to clarify some properties of the optimal policy. Furthermore, we will use it in our experiments in Sec. [START_REF] Spencer | Advances in Disk Technology: Performance Issues[END_REF].

Considering the mechanical structure of the HDD, every time a new read is done, we need to wait for the reading arm to move across the cylinders, and for the platter to rotate on its axis. We call these two contributions the average seek time and average rotation time, and we denote them by σ and ρ respectively. Each file is divided into blocks, whose size b is a configuration parameter. If we read a file whose size is bigger than a block, then we need to wait for the average seek time and the average rotation time for each block.

Once the reading head has reached the beginning of a block, the time it takes to read the data depends on the transfer speed µ. As a last contribution, we have a constant delay due to the controller overhead, φ.

Overall, the function that estimates the cost of reading a file from the hard disk is given by the following equation (see Table 1 for a summary of the variables used):

T (s i ) = (σ + ρ) s i b + s i µ + φ. (1)
Based on our experience on real-life production systems, the last column of Table 1 shows the values of the different variables for a 10'000 RPM hard drive.

We have validated Eq. ( 1) through an extensive measurement campaign for two different hard disk drives (10'000 RPM and 7'200 RPM). The results

Query Request Process

Let N = {1, 2, . . . N } denote the set of contents. For mathematical tractability, as done in most of the works in the literature (see Sec. 5), we assume that the requests follow the popular Independent Reference Model (IRM), where contents requests are independently drawn according to constant probabilities (see for example [START_REF] Edward | Operating Systems Theory[END_REF]). In particular, we consider the time-continuous version of the IRM: requests for content i ∈ N arrive according to a Poisson process with rate λ i and the Poisson processes for different contents are independent. While the optimality results for our policy q i -LRU are derived under such assumption, significant performance improvements are obtained also considering real request traces (see Sec. 4).

Problem Formulation

In general, the optimal operation of a hierarchical cache system would require to jointly manage the different storage units, and in particular to avoid to duplicate contents across multiple units. On the contrary, in the case of a RAM-HDD system, the problem is usually decoupled: the HDD caching policy is selected in order to maximize the main cache performance metric (e.g. hit ratio/rate), while a subset of the contents stored in the HDD can be duplicated in the RAM to optimize some other performance metric (e.g. the response time). The reason for duplicating contents in the RAM is twofold. First, contents present only in the RAM would be lost if the caching server is rebooted. Second, the global cache hit ratio/rate would not be significantly improved because the RAM accounts for a small percentage of the total storage available at the server. A consequence of such decoupling is that, at any time, the RAM stores a subset (M R ) of the contents stored in the HDD (M H ). 3 In our work we consider the same decoupling principle. As a consequence, our policy is agnostic to the replacement policy implemented at the HDD (LRU, FIFO, Random, . . . ).

We now look at how the RAM reduces the HDD load. An incoming request can be for a content not present in the HDD (nor in the RAM because we consider M R ⊂ M H ). In this case, the content will be retrieved by some other server in the CDN or by the authoritative content provider, and then stored or not in the HDD depending on the specific HDD cache policy. Note that the choice of the contents to be duplicated in the RAM plays no role here. Read/write operations can occur (e.g. to store the new content in the HDD), but they are not affected by the RAM replacement policy, that is the focus of this paper. We ignore then the corresponding costs. On the contrary, if an incoming request is for a content present in the HDD, the expected HDD service time depends on the set of contents M R stored in the RAM. It is indeed equal to

i∈M H \M R λ i j∈N λ j T (s i ) = i∈M H λ i j∈N λ j T (s i ) - i∈M R λ i j∈N λ j T (s i ), (2)
because, under IRM, λ i / j∈N λ j is the probability that the next request is for content i, and the request will be served by the HDD only if content i is not duplicated in the RAM, i.e. only if i / ∈ M R . Our purpose is to minimize the HDD service time under the constraint on the RAM size. This is equivalent to maximize the second term in Eq. [START_REF] Neglia | Access-time aware cache algorithms[END_REF]. By removing the constant j∈N λ j , we obtain then that the optimal possible choice for the subset M R is the solution of the following maximization problem:

maximize M R ⊂N i∈M R λ i T (s i ) (3) subject to i∈M R s i ≤ C
where C is the RAM capacity. This is a knapsack problem, where λ i T (s i ) is the value of content/item i and s i its weight. The knapsack problem is NP-hard.

A natural, and historically the first, relaxation of the knapsack problem is the fractional knapsack problem (also called continuous knapsack problem). In this case, we accept fractional amounts of the contents to be stored in the RAM. Let h i ∈ [0, 1] be the fraction of content i to be put in the RAM, the fractional problem corresponding to Problem (3) is:

maximize h1,...h N N i=1 λ i h i T (s i ) (4) subject to N i=1 h i s i = C.
From an algorithmic point of view, the following greedy algorithm is optimal for the fractional knapsack problem. Assume that all the items are sorted in decreasing order with respect to the profit per unit of size (i.e. λ i T (s i )/s i ≥ λ j T (s j )/s j for i ≤ j). The algorithm finds the biggest index c for which the sum c i=1 s i does not exceed the memory capacity. Finally, it stores the first c contents in the knapsack (in the RAM) as well as a fractional part of the content c + 1 so that the RAM is filled up to its capacity. A simple variant of this greedy algorithm guarantees a 1 2 -approximation factor for the original knapsack problem [6, Theorem 2.5.4], but the greedy algorithm itself is a very good approximation algorithm for common instances of knapsack problems, as it can be justified by its good expected performance under random inputs [START_REF] Kellerer | Knapsack problems[END_REF]Sec. 14.4].

From a networking point of view, if we interpret h i as the probability that content i is in the RAM, 4 then we recognize that the constraint in Problem (4) corresponds to the usual constraint considered under Che's approximation for cache networks [START_REF] Hao Che | Hierarchical Web caching systems: modeling, design and experimental results. Selected Areas in Communications[END_REF], where the effect of the finite cache size is taken into account by imposing the expected cache occupancy to be equal to the cache size C.

The last remark connects our problem to the recent work in [START_REF] Dehghan | A Utility Optimization Approach to Network Cache Design[END_REF], where the authors use Che's approximation to find optimal cache policies to solve the following problem:

maximize h1,...h N N i=1 U i (h i ) (5) subject to N i=1 h i s i = C,
where each U i (h i ) quantifies the utility of a cache hit for content i. 5 Results in [START_REF] Dehghan | A Utility Optimization Approach to Network Cache Design[END_REF] do not help us solve our Problem (4) because their approach requires the functions U i (h i ) to be (i) known and (ii) strictly concave in h i . On the contrary, in our case, content popularities (λ i ) are unknown and, even if they were known, the functions U i (h i ) would be λ i h i T (s i ) and then linear in h i . Besides deriving the cache policy that solves a given optimization problem, [START_REF] Dehghan | A Utility Optimization Approach to Network Cache Design[END_REF] also "reverseengineers" existing policies (like LRU) to find which optimization problem they are implicitly solving. In Sec. 3 we use a similar approach to study our policy.

After this general analysis of the problem, we are ready to introduce in the next section a new caching policy q i -LRU that aims to solve Problem (4), i.e. to store in the RAM the contents with the largest values λ i T (s i )/s i without the knowledge of content popularities λ i , for i = 1, . . . N .

The q i -LRU Policy

We start introducing our policy as a heuristic justified by an analogy with LRU.

Under IRM and Che's approximation, if popularities λ i are known, minimizing the miss throughput at a cache with capacity C corresponds to solving the following problem:

maximize h1,...h N N i=1 λ i h i s i (6) subject to N i=1 h i s i = C
The optimal solution is analogous to what discussed for Problem (4): set hit probabilities to one for the k most popular contents, a hit probability smaller than one for the (k + 1)-th most popular content, and hit probabilities to zero for all the other contents. The value of k is determined by the RAM size. Now, it is well known that, from a practical perspective, the traditional LRU policy behaves extremely well, despite content popularity dynamics. LRU is a good heuristic for Problem [START_REF] Kellerer | Knapsack problems[END_REF]: it implicitly selects and stores in the cache the contents with the largest values of λ i , even when popularities λ i are actually unknown.

Recall that our purpose is to store the contents with the largest values λ i T (s i )/s i : then, the analogy between the two problems suggests us to bias LRU in order to store more often the contents with the largest values of T (s i )/s i . Intuitively, upon a cache miss, the newly requested content i is cached with probability q i , which is an increasing function in T (s i )/s i . Specifically, we define q i as follows:

q i = e -β s i T (s i ) , i ∈ N , (7)
where β > 0 is a constant parameter. 6 In practical cases, as discussed in section 4, we set β such that q i ≥ q min for every i ∈ N , so that any content is likely to be stored in the cache after 1/q min queries on average. Our policy has then the same behaviour as the q-LRU policy, but the probability q is not fixed, it is instead chosen depending on the size of the content as indicated in Eq. [START_REF] Hao Che | Hierarchical Web caching systems: modeling, design and experimental results. Selected Areas in Communications[END_REF]. For this reason, we denote our policy by q i -LRU.

With reference to Fig. 2, the policy q i -LRU would store with higher probability the smallest contents as well as the contents whose size is slightly larger than a multiple of the block size b. Note that the policy q i -LRU does not depend on the model described above for the HDD service time, but it requires the ratio T (s)/s to exhibit some variability (otherwise we would have the usual q-LRU).

Until now we have provided some intuitive justification for the policy q i -LRU. This reasoning reflects how we historically conceived it. The reader may now want more theoretically grounded support to our claim that q i -LRU is a good heuristic for Problem [START_REF] Spencer | Advances in Disk Technology: Performance Issues[END_REF]. In what follows we show that q i -LRU is asymptotically optimal when β diverges in two different ways. We first prove in Sec. 3.1 that q i -LRU asymptotically stores in a cache the contents with the largest values λ i T (s i )/s i , as the optimal greedy algorithm for Problem (4) does. This would be sufficient to our purpose, but we find interesting to establish a connection between q i -LRU and the cache utility maximization problem introduced in [START_REF] Dehghan | A Utility Optimization Approach to Network Cache Design[END_REF]. For this reason, in Sec. 3.2, we reverse-engineer the policy q i -LRU and derive the utility function it is implicitly maximizing. We then let again β diverge and show that the utility maximization problem converges to a problem whose optimal solution corresponds to store the contents with the largest values λ i T (s i )/s i .

Asymptotic q i -LRU hit probabilities

In [START_REF] Garetto | A Unified Approach to the Performance Analysis of Caching Systems[END_REF] (and partially in the conference version [START_REF] Martina | A Unified Approach to the Performance Analysis of Caching Systems[END_REF]) it is proven that under the assumptions of the IRM traffic model, the usual q-LRU policy tends to the policy that statically stores in the cache the most popular contents when q converges to 0. We generalize their approach to study the q i -LRU policy when β diverges (and then q i converges to 0, for all i). In doing so, we address some minor technical details that are missing in the proof in [START_REF] Garetto | A Unified Approach to the Performance Analysis of Caching Systems[END_REF].

Let us sort contents in a decreasing order of λiT (si) si assuming, in addition, that λiT (si) si = λj T (sj ) sj

for every i = j. Note that the hit probability h i associated to the content i for the q i -LRU policy is given by the following formula (see [START_REF] Garetto | A Unified Approach to the Performance Analysis of Caching Systems[END_REF])

h i (β, τ c ) = q i (β)(1 -e -λiτc ) e -λiτc + q i (β)(1 -e -λiτc ) , (8)
where τ c is the eviction time that, under Che's approximation [START_REF] Hao Che | Hierarchical Web caching systems: modeling, design and experimental results. Selected Areas in Communications[END_REF], is assumed to be a constant independent of the selected content i. Now, by exploiting the constraint:

C = i s i h i (β, τ c ) (9)
it is possible to express τ c as an increasing function of β and prove that lim β→∞ τ c (β) = ∞. This result follows [START_REF] Garetto | A Unified Approach to the Performance Analysis of Caching Systems[END_REF], but, for the sake of completeness, we present it extensively in [START_REF] Neglia | Access-time aware cache algorithms[END_REF].

We can now replace q i = e -β s i T (s i ) in Eq. ( 8) and express the hit probability as a function of β only as follows:

h i (β) = 1 -e λiτc(β)
e τc(β)

s i T (s i ) β τc (β) -λi T (s i ) s i + 1 -e -λiτc(β) . ( 10
)
Let us imagine to start filling the cache with contents sorted as defined above. Let c denote the last content we can put in the cache before the capacity constraint is violated7 i.e.

c = max k k i=1 s i ≤ C .
We distinguish two cases: the first c contents fill exactly the cache (i.e. c i=1 s i = C), or they leave some spare capacity, but not enough to fit content c + 1. Next, we prove that q i -LRU is asymptotically optimal in the second case. The first case requires a more complex machinery that we develop in [START_REF] Neglia | Access-time aware cache algorithms[END_REF].

Consider then that

c i=1 s i < C < c+1 i=1 s i .
As an intermediate step we are going to prove by contradiction that

lim β→∞ β τ c (β) = λ c+1 T (s c+1 ) s c+1 . (11)
Suppose that this is not the case. Then, there exists a sequence β n that diverges and a number > 0 such that ∀n ∈ N

either β n τ c (β n ) ≤ λ c+1 T (s c+1 ) s c+1 - (12)
or

β n τ c (β n ) ≥ λ c+1 T (s c+1 ) s c+1 + . (13)
If inequality (12) holds, then ∀i ≤ c + 1

β n τ c (β n ) - λ i T (s i ) s i ≤ β n τ c (β n ) - λ c+1 T (s c+1 ) s c+1 ≤ -
From Eq. ( 10) it follows immediately that lim

βn→∞ h i (β n ) = 1 ∀i ≤ c + 1, but then it would be lim n→∞ c+1 i=1 h i (β n )s i = c+1 i=1 s i > C
contradicting the constraint [START_REF] Garetto | A Unified Approach to the Performance Analysis of Caching Systems[END_REF]. In a similar way it is possible to show that inequality (13) leads also to a contradiction and then Eq. ( 11) holds.

Because of the limit in Eq. ( 11) and of Eq. ( 10), we can immediately conclude that, when β diverges, h i (β) converges to 1, for i ≤ c, and to 0, for i > c + 1. Because of the constraint [START_REF] Garetto | A Unified Approach to the Performance Analysis of Caching Systems[END_REF], it holds that:

lim β→∞ h c+1 (β) = C -lim β→∞ i =c+1 h i s i s c+1 = C -i≤c s i s c+1 .
The same asymptotic behavior for the hit probabilities holds when c i=1 s i = C, as it is proven in [START_REF] Neglia | Access-time aware cache algorithms[END_REF]. 8 We can then conclude that: Proposition 3.1. When the parameter β diverges, the hit probabilities for the q i -LRU policy converge to the solution of the fractional knapsack problem (4), i.e.

lim β→∞ h i (β) =      1, for i ≤ c, (C - c i=1 s i )/s c+1 , for i = c + 1, 0, for i > c + 1.
Then the q i -LRU policy asymptotically minimizes the load on the hard-disk.

Reverse-Engineering q i -LRU

In [START_REF] Dehghan | A Utility Optimization Approach to Network Cache Design[END_REF], the authors show that existing policies can be thought as implicitly solving the utility maximization problem (5) for a particular choice of the utility functions U i (h i ). In particular they show which utility functions correspond to traditional policies like LRU and FIFO. In what follows, we "reverse-engineer" the q i -LRU policy and we show in a different way that it solves the fractional knapsack problem. We proceed similarly to what done in [START_REF] Dehghan | A Utility Optimization Approach to Network Cache Design[END_REF], extending their approach to the case where content sizes are heterogeneous (see [START_REF] Neglia | Access-time aware cache algorithms[END_REF]). We show that the utility function for content i is

U i (h i ) = -λ i s i 1-hi 0 dx ln 1 + 1-x qix , (14)
that is defined for h i ∈ (0, 1] and q i = 0. Each function U i (.) is increasing and concave. Moreover, U i (h i ) < 0 for h i ∈ (0, 1), U i (1) = 0 and lim hi→0 U i (h i ) = -∞.

We are interested now in studying the asymptotic behavior of the utility functions U i (h i ) when β diverges, and then q i converges to zero. First, we note that the following inequalities are true for every δ > 0 such that q δ i < 1 -h i :

1-hi 0 dx ln 1 + 1-x qix ≥ 1-hi q δ i dx ln 1 + 1-x qix ≥ 1 -h i -q δ i ln 1 + 1-q δ i q δ+1 i , (15)
where the last inequality follows from the fact that the integrand is an increasing function of x.

8 When c i=1 s i = C, h c+1 (β) converges to (C - c i=1 s i )/s c+1 = 0.
Similarly, it holds

1-hi 0 dx ln 1 + 1-x qix ≤ 1 -h i ln 1 + hi qi(1-hi) ≤ 1 -h i ln 1 + 1 qi . (16)
Asymptotically, when q i converges to zero, the lower bound in Eq. ( 15) is equivalent to 1-hi (1+δ) ln(1/qi) , and the upper bound in ( 16) is equivalent to 1-hi ln(1/qi) .9 For every δ > 0, we obtain the following (asymptotic) inequalities when q i converges to 0 (and then q δ i < 1 -h i asymptotically):

1

-h i (1 + δ) ln(1/q i ) ≤ 1-hi 0 dx ln 1 + 1-x qix ≤ 1 -h i ln(1/q i ) . (17)
Thus, when q i converges to 0, we get

1-hi 0 dx ln 1 + 1-x qix ∼ 1 -h i ln(1/q i ) ,
since, otherwise, we could find an ε > 0 and a sequence q i,n converging to 0 such that for large n

1-hi 0 dx ln 1 + 1-x qi,nx ≤ (1 -ε) 1 -h i ln(1/q i,n ) .
But, this would contradict the left-hand inequality in [START_REF] Cao | Cost-aware WWW proxy caching algorithms[END_REF], which is valid for every δ > 0. We conclude that, when q i converges to 0,

U i (h i ) = -λ i s i 1-hi 0 dx ln 1 + 1-x qix ∼ - λ i s i (1 -h i ) ln(1/q i ) .
Next, we consider q i = e -β s i T (s i ) and we can write

U i (h i ) ∼ - λ i T (s i )(1 -h i ) β , when β → ∞.
Maximizing the sum of the utilities i U i (h i ) over the hit probabilities is equivalent to maximizing

β i U i (h i ) + i λ i T (s i ).
We conclude that, when β diverges, the problem ( 5) can be formulated as follows

maximize h N i=1 λ i h i T (s i ) (18) subject to N i=1 h i s i = C,
which is exactly the formulation of the fractional knapsack problem.

Experiments

In this section, we evaluate the performance of our q i -LRU policy. Here we take a numerical perspective, and design a trace-driven simulator that can reproduce the behavior of several caching policies, which we compare against q i -LRU. We have used both synthetic traces generated according to the IRM and real traces collected at two vantage points of the Akamai network [START_REF] Nygren | The Akamai Network: A Platform for High-performance Internet Applications[END_REF]. We proved that q i -LRU is optimal under the IRM and indeed our experiments confirm it and show significant improvement in comparison to other replacement policies. For this reason, in this section we focus mainly on the results obtained with real traces. In the following, we describe our experimental methodology, show the characteristics of the real traces we use, and present the results of our evaluation.

Methodology and Performance indexes

The comparative analysis of different caching policies requires an environment where it is possible to reproduce exactly the same conditions for all the different policies. To do so, we adopt a trace-driven simulation approach,10 which allows us to control the initial conditions of the system, explore the parameter space and perform a sensitivity analysis, for all eviction policies. Our simulator reproduces two memory types: the main memory (RAM) and the hard disk (HDD). Each object is stored in the HDD according to the LRU policy. For the RAM we consider 3 different policies: LRU, SIZE and q i -LRU. They all evict the least recently requested content, if space is needed, but they adopt different criteria to decide if storing a new content after a miss:

• LRU always stores it;

• SIZE stores it if 1) its size is below a given threshold T , or 2) it has been requested at least N times, including once during the previous M hours;

• q i -LRU stores it with probability q i , as explained in the previous sections.

So, in addition to comparing q i -LRU to the traditional LRU policy, we also consider the SIZE policy since small objects are the ones that have a bigger impact on the HDD, in terms of their service time T (s i ) (see also Fig. 2). We therefore prioritize small objects, and we store objects bigger than the threshold T only after they have been requested for at least N times. The SIZE policy can thus be seen as a first attempt to decrease the impact of small objects on the HDD, and ultimately reduce the strain on HDD resources. With the q i -LRU policy, we aim at the same goal, but modulate the probability to store an object in RAM as a function of its size, and thus of its service time.

Note that the hit ratio of the whole cache depends only on the size of the HDD and its replacement policy (LRU). The RAM replacement policy does not affect the global hit ratio. In what follows, we focus rather on the number of requests served by the RAM and by the disk. More precisely, we consider the total disk service time: this is the sum of the T (s i ) of all the objects served by the HDD. Smaller disk service times indicate lower pressure on the disk. We show the results for a system with 4 GB RAM and 3 TB HDD. We have tried many different values for the RAM size up to 30 GB, and the qualitative results are similar (not shown here because of space constraints). For the SIZE policy, we have extensively explored the parameter space (threshold T , number of requests N , and number of hours M ) finding similar qualitative results. 11 For the q i -LRU policy, the default value of the constant β is chosen such that min i∈N q i = 0.1 (see Eq. ( 7)).

Trace characteristics

We consider two traces with different durations and collected from two different vantage points. The first trace has been collected for 30 days in May 2015, while the second trace for 5 days at the beginning of November 2015. Table 2 shows the basic characteristics of the traces.

Fig. 3 shows the number of requests for each object, sorted by rank (in terms of popularity), for both traces. For the 30-day trace, there are 25-30 highly requested objects (almost 25% of the requests are for those few objects), but the cumulative size of these objects is less than 8 MB. Since they are extremely popular objects, any policy we consider stores them in RAM, so they are not responsible for the different performance we observe for the different policies. Next, we study the relation between the size and the number of requests of each object. In Fig. 4, for each object, we plot a point that corresponds to its size (y-axis) and the number of requests (x-axis). For the 30-day trace, the plot does not include the 30 most popular objects. We notice that the 5-day trace does not contain objects smaller than 1 kB. For ease of representation, we consider the objects with at least 1000 requests (for the 30-day trace, we do not include the 30 most popular objects). This is also shown in Fig. 5, where we plot the empirical Cumulative Distribution Function (CDF) for the size of the requested objects (without aggregating requests for the same object). The 30-day trace contains a lot of requests for small objects, while the 5-day trace contains requests for larger objects (e.g., see the 90-th percentile). In the 30-day trace we have then a larger variability of the ratio T (s)/s (see Fig. 2) and we expect q i -LRU to be able to differentiate more among the different contents and then achieve more significant improvement, as it is confirmed by our results below.

Comparative analysis of the eviction policies

Tables 3 and4 summarize the aggregate results for the two traces we consider in our study. For the hit ratio, we see that the q i -LRU policy can serve more requests from the RAM. On the other hand, the overall number of bytes served by RAM is smaller: this means that the RAM is biased towards storing small, very popular objects, as expected. The last column shows the gain, in percentage, in disk service time between each policy and LRU, which we take as a de-facto reference (e.g., -10% for policy "x" means that its disk service time is 10% smaller than for LRU). This is the main performance metric we are interested in. For the 30-day trace, the q i -LRU policy improves by 23% the disk service time, over the LRU policy. For the 5-day trace, the improvement of q i -LRU over LRU is smaller, topping at a bit more than 7%. The reason behind this result relates to the object size distribution in the trace: as shown in Fig. 5, the trace contains objects starting from 1 kB, while, for the 30-day trace, 20% of the requests are for objects smaller than 1 kB. The impact of these objects on the overall T (s i ) is significant.

Next, we take a closer look at our policy, q i -LRU, in comparison to the reference LRU policy. We now consider the contribution to the overall hit ratio of each object, to understand their importance to cache performance. For the 5day trace, we sorted the objects according to their rank (in terms of popularity) and their size, and plot the difference between LRU hit ratio and q i -LRU hit ratio. Fig. 6 shows that both policies store the same 1000 most popular objects; then, the q i -LRU policy gains in hit ratio for medium-popular objects. Switching now to object size, both policies store the same set of small objects, while q i -LRU gains hit ratio with the medium-size objects. Figure 6: Difference between LRU hit ratio and q i -LRU hit ratio when objects are ordered by popularity (left) and by size (right) for the 30-day trace.

dered by rank or by size) and shows the difference between the service time reduction under LRU and under q i -LRU. Clearly, medium popular objects and medium size objects contribute the most to the savings in the service time that our policy achieves.

Sensitivity analysis

Next, we study the behavior of q i -LRU as a function of the parameter β, but we plot the results for the parameter q min = min i∈N q i , that is easier to interpret, being the minimum probability according to which a content is stored in the RAM.

Figure 8 provides two different views. On the left-hand side, it shows the percentage of HDD service time offloaded to the RAM by q i -LRU, both under the 30-day trace and a synthetic IRM trace generated using the same empirical distributions for object size and popularity as in the 30-day trace. As expected, under IRM, the improvement from q i -LRU increases as q min decreases, i.e. as β increases. Interestingly, the HDD benefits even more under the 30-day trace, with more than 80% of the service offloaded to the RAM. This is due to the temporal locality effect (see e.g. [START_REF] Traverso | Temporal Locality in Today's Content Caching: Why It Matters and How to Model It[END_REF]), i.e. to the fact that requests typically occur in bursts and then the RAM is more likely to be able to serve the content for a new request than it would be under the IRM model. We observe also that the performance of q i -LRU is not very sensitive to the parameter q min (and then to β), a feature very desirable for practical purposes. The right-hand side of Fig. 8 shows the relative improvement of q i -LRU in comparison to LRU (calculated as difference of the HDD service time under LRU and under q i -LRU, divided by the HDD service time under LRU). While q i -LRU performs better and better as q min decreases with the IRM request pattern, the gain reduces when q min approaches 0 (β diverges) with the 30-day trace. This is due also to temporal locality: when the probabilities q i are very small, many contents with limited lifetime have no chance to be stored in the RAM by q i -LRU and they need to be served by the HDD. Despite this effect, q i -LRU policy still outperforms LRU over a large set of parameter values and obtain improvements larger than 20% for 0.02 < q min < 0.4.

Related Work

Cache replacement policies have been the subject of many studies, both theoretical and experimental. We focus here on the more analytical studies, which are closer to our contribution in this paper. Moreover, our policy is explicitly designed to mitigate the burden on the HDD, a goal not considered in most previous experimental works, despite its practical importance. Most of the theoretical work in the past has focused on the characterization of the performance of LRU, RANDOM, and FIFO [7][12][10] [START_REF] Bianchi | Check before storing: What is the performance price of content integrity verification in LRU caching[END_REF]. These works do not design caching policies to solve a specific optimization problem.

The work in [START_REF] Rossini | Multi-Terabyte and multi-Gbps information centric routers[END_REF], instead, considers a 2-level hierarchy, with the content stored in the SSD and DRAM. They propose a new policy which decreases the response time by pre-fetching the content from SSD to DRAM. To this aim, they focus on a specific type of content, videos divided into chunks, for which the requests are strongly correlated, and a request for a chunk can be used to foresee future requests for other chunks of the same content. In our work, instead, we provide a model for the q i -LRU policy which does not assume any correlation on the requests arrivals, but prioritize the content that imposes a high burden on the HDD.

A different approach is taken in [START_REF] Araldo | Cost-aware caching: Caching more (costly items) for less (isps operational expenditures). Parallel and Distributed Systems[END_REF]. The authors consider that caching policies could be designed with other purposes than maximizing the local hit probability. For example, they propose a heuristic that takes into account the cost to retrieve the contents from expensive inter-domain links. Cost-aware caches have been the subject of many experimental studies [START_REF] Bahat | Optimal replacement policies for nonuniform cache objects with optional eviction[END_REF][17] [START_REF] Starobinski | Probabilistic methods for web caching[END_REF]. While these studies are similar in spirit, none of them considers cost functions analogous to the HDD service time that is the focus of this paper. Moreover, they did not prove the optimality of the replacement policies proposed.

The most related work to ours is the cache optimization framework in [START_REF] Dehghan | A Utility Optimization Approach to Network Cache Design[END_REF], that we have widely discussed through the paper. We stress again here, that they assume content popularities to be known (or to be explicitly estimated) and the utility functions to be strictly concave, and this is not the case in our problem.

Conclusion

Caches represent a crucial component of the Internet architecture: decreasing the response time is one of the primary objectives of the providers operating such caches. This objective can be pursued by exploiting the RAM of the cache server, while keeping most of the content in the HDD.

In this paper, we presented a new cache replacement policy that takes advantage of the access-time difference in the RAM and in the HDD to reduce the load on the HDD, so that to improve the overall cache efficiency for a capacity constrained storage systems. Our policy, called q i -LRU, is a variant of q-LRU, where we assign a different probability q i to each content based on its size.

We proved that q i -LRU is asymptotically optimal, and we provided an extensive trace-driven evaluation that showed between 10% and 20% reduction of the HDD load with respect to the LRU policy.

Figure 1 :

 1 Figure 1: Graph showing the CPU and HDD utilization percentage of a generic caching server.

Figure 2 :

 2 Figure 2: Graph of the function T (s i )/s i .

Figure 3 :

 3 Figure 3: Number of requests per object (ordered by rank). 11 As a representative set of results, we show here the case with T = 256 KB, N = 5 and M = 1 hour.

Figure 4 :

 4 Figure4: Size vs Number of requests. For ease of representation, we consider the objects with at least 1000 requests (for the 30-day trace, we do not include the 30 most popular objects).

Figure 5 :

 5 Figure 5: Cumulative fraction of the requests for objects up to a given size (for the 30-day trace, we do not include the 30 most popular objects).

Fig. 7

 7 considers the contribution to the disk service time of each object (or-

Figure 7 :

 7 Figure 7: Difference between HDD service time reduction under LRU and under q i -LRU when objects are ordered by rank (left) and by size (right) for the 30-day trace.

Figure 8 :

 8 Figure 8: Sensitivity analysis to the value of q min .

Table 1 :

 1 Summary of the variables used for T (s i ). In the figure, we actually plot the quantity T (s i )/s i : in Sect. 3 we will illustrate the key role played by this ratio. The estimated value of T (s i )/s i has discontinuity points at multiples of the block size b: in fact, as soon as the size of an object exceeds one of such values, the service time increases by an additional average seek time and an additional average rotation time. The points in the figures represent the output of our measurement campaign for a representative subset of sizes (in particular, for sizes close to the multiples of block size b, where the discontinuities occur). Each point is the average value for a given size over multiple reads. From the experiments, we conclude that the function T (s i ) shown in Eq. (1) is able to accurately estimate the cost of reading a file from the HDD.

	Variable	Meaning	Typical Value
	s i	Size of object i	-
	σ	Average seek time	3.7•10 -3 s
	ρ	Average rotation time	3.0•10 -3 s
	b	Block size	2.0 MB
	µ	Transfer bandwidth	157 MB/s
	φ	Controller Overhead	0.5•10 -3 s
	are shown in Fig. 2.

Table 2 :

 2 Traces: basic information.

		30 days	5 days
	Number of requests received 2.22 • 10 9 4.17 • 10 8
	Number of distinct objects	113.15 M	13.27 M
	Cumulative size	59.45 TB	2.53 TB
	Cumulative size of objects
	requested at least twice	20.36 TB	1.50 TB

Table 3 :

 3 Results for the 30-day trace with 4 GB RAM.

				bytes	service	∆ (%)
			% reqs served	time	w.r.t. LRU
	LRU	RAM	73.06	509 TB 4907 h	-
		HDD	26.94	157 TB 1663 h	-
	SIZE	RAM	76.38	512 TB 5055 h	+ 3.02%
		HDD	23.62	154 TB 1515 h	-8.90%
	q i -LRU RAM	84.27	489 TB 5294 h	+7.89%
		HDD	15.73	177 TB 1276 h	-23.27%

Table 4 :

 4 Results for the 5-day trace with 4 GB RAM.

				bytes	service	∆ (%)
			% reqs served	time	w.r.t. LRU
	LRU	RAM	79.61	159 TB 1058 h	-
		HDD	20.39	23 TB	219 h	-
	SIZE	RAM	80.31	160 TB 1064 h	+ 0.57%
		HDD	19.69	22 TB	213 h	-2.74%
	q i -LRU RAM	84.72	149 TB 1074 h	+1.51%
		HDD	15.28	33 TB	203 h	-7.31%

If the service time is affected by significant random effects, then T (s i ) can be interpreted as the expected service time for a content with size s i .

The specific service discipline would clearly have an effect on the time needed to retrieve a specific content.

Although it is theoretically possible that a content stored in the RAM and in the HDD may be evicted by the HDD earlier than by the RAM, these events can be neglected in practical settings. For example, in the scenario considered in Sec.

typical cache eviction times are a few minutes for the RAM and a few days for the HDD for all the cache policies considered.

Since the PASTA property holds under the IRM model, then h i is also the RAM hit probability.

The work in[START_REF] Dehghan | A Utility Optimization Approach to Network Cache Design[END_REF] actually assumes that all the contents have the same size, but their analysis can be easily extended to heterogenous sizes, as we do in Sec. 3.2.

The reader may wonder why we have chosen this particular relation and not simply q i proportional to T (s i )/s i . The choice was originally motivated by the fact that proportionality leads to very small q i values for some contents. Our analysis below shows that Eq. (7) is a sensible choice.

We consider the practical case when s 1 < C < N i=1 s i .

We say that f (x) is equivalent to g(x) when x converges to 0 if lim x→0 f (x)/g(x) = 1, and we write f (x) ∼ g(x).

As a future work, we plan to deploy our policy in a real production system. In this case, the methodology to perform a comparative analysis is substantially different.

Acknowledgment

This work was partially supported by the "Investments for the Future" Program reference #ANR-11-LABX-0031-01, funded by the French Government (National Research Agency, ANR). The authors would like to thank Bodossaki Foundation for having supported Dimitra Tsigkari's internship at Inria.


Pablo Azagra
email: pazagra@unizar.es

Yoan Mollard
email: yoan.mollard@inria.fr

Florian Golemo
email: fgolemo@gmail.com

Ana Cristina Murillo

Manuel Lopes
email: manuel.lopes@inria.fr

Javier Civera
email: jcivera@unizar.es

A Multimodal Human-Robot Interaction Dataset

This works presents a multimodal dataset for Human-Robot Interactive Learning. The dataset contains synchronized recordings of several human users, from a stereo microphone and three cameras mounted on the robot. The focus of the dataset is incremental object learning, oriented to human-robot assistance and interaction. To learn new object models from interactions with a human user, the robot needs to be able to perform multiple tasks: (a) recognize the type of interaction (pointing, showing or speaking), (b) segment regions of interest from acquired data (hands and objects), and (c) learn and recognize object models. We illustrate the advantages of multimodal data over camera-only datasets by presenting an approach that recognizes the user interaction by combining simple image and language features.

Introduction

Motivation. In the latest years we are witnessing a widespread adoption of robotics in multiple aspects of our daily life and activities, for example in household assistance devices and autonomous cars. One of the key aspects in service robotics is comfort / intuitive control in human-robot interaction, a topic notably approached by [START_REF] Reiser | Care-o-bot R 3-creating a product vision for service robot applications by integrating design and technology[END_REF][START_REF] Baraglia | Initiative in robot assistance during collaborative task execution[END_REF][START_REF] Dumora | Robot assistance selection for large object manipulation with a human[END_REF] among others. Some of the most relevant requirements for such interactions are learning world models, affordances and capabilities from the user's knowledge and behavior -as seen in [START_REF] Sinapov | Learning relational object categories using behavioral exploration and multimodal perception[END_REF] for example. From the robot's perspective, a framework for incremental object learning from human interaction should contain multiple modules: 1) recognizing the action that the user is performing, 2) extracting information (from the acquired sensory data) that is relevant to the object of interest (as for example in [START_REF] Kenney | Interactive segmentation for manipulation in unstructured environments[END_REF]), 3) assigning a class to the object of interest (with works like [START_REF] Iravani | Visual object classification by robots, using on-line, self-supervised learning[END_REF]) and incrementally update the model for each object class (with an approach similar to [START_REF] Camoriano | Incremental object recognition in robotics with extension to new classes in constant time[END_REF]). Figure 1 shows a schematic overview of this pipeline. Each of these modules is challenging on its own, specially if we address realistic environments and interactions. This work presents a public dataset for incremental object learning from human-robot interactions. We focus on multimodal data, since it intuitively seems to provide important advantages to advance towards the goal of seamless communication between robots and humans. However, multimodal data also presents additional challenges.

Contributions. The presented dataset contains synchronized acoustic (stereo microphone), visual (three cameras), and depth information (two of the cameras contain infrared sensors). To our knowledge, this is the first publicly available dataset that contains user interaction data from the robot's perspective with synchronized multi-camera and microphone data. We present an illustrative experiment showing the benefits of multimodal data.

Related Work. There are multiple aspects that are of relevance for interactive learning. In our particular case, we focus on the type of interaction and the multimodal data. In a realistic human-robot interactive learning scenario, the training data is expected to be presented in a very different way than standard datasets. The data should capture the human operator and his actions. That means the data should be recorded from the point of view (POV) of the robot. Recognizing a pedestrian from a close-up view from service robot is immensely different from performing the same task with the raw video data from a distant wide-angle surveillance camera.

Vatakis et al. [START_REF] Vatakis | A multimodal dataset of spontaneous speech and movement production on object affordances[END_REF] shows multimodal recording approach similar to ours, but the purpose of their dataset was to capture the reactions of users to stimuli with objects, or images on a screen. Datasets like [START_REF] Jaeyong | Human activity detection from rgbd images[END_REF] or [START_REF] Gong | A New Image Dataset on Human Interactions[END_REF] capture human-robot interaction from a third-person POV. This is useful in lab environments, but since we are working with service robots, information must be taken from the onboard sensors. Additionally, many datasets lack additional sensor data that is easy to find in human-robot interactive scenarios like speech from the user. As detailed in the next section, our dataset is focused not only on capturing the user's face, but also on capturing the scene information (hands, arms, desk, objects, etc.) related to the object classes being taught to the robot. This additional information is useful for future work, but for the purpose of this article we only labeled the interaction type in each clip.

The Multimodal Human-Robot Interaction (MHRI) dataset

The MHRI dataset1 is composed of recordings of several users teaching different object classes to the robot. It contains synchronized data from the following sensors:

• Chest-Kinect. Microsoft Kinect v1.0 (640 × 480). This first camera is mounted on the chest of the robot and is focused on the frontal interaction with the user. • Top-Kinect. Microsoft Kinect v1.0 (640 × 480). This camera is mounted on the head of the robot and gives a top global view including the user, the workspace and the objects. • Face-HDcam. 1280 × 720 RGB camera mounted on the screen of the Baxter robot and focused on the user's face. • Audio. Speech from the user, recorder with a USB microphone situated on the side of the table.

The cameras are mounted so that the user and the table on which the interaction occurs, are perfectly covered. Figure 2a shows the placement of the cameras in the Baxter robot used for the acquisition and Figure 2b shows some examples of the recordings.

The types of interactions captured in the dataset reflect the most common ways users show or teach objects to the robot: Point, Show, and Speak. The Point interaction captures a user pointing at an object and calling out its name to the robot. The Show interaction describes a user grabbing an object and bringing it approximately in front of the robot's torso camera while announcing the object's name. The Speak interaction captures a user describing to the robot where a certain object is placed. Figure 2c shows an example of each of these three types of interactions.

Table 1 contains a summary of the contents of the dataset. We recorded 10 users, each of them performing 10 object interactions for each of the 3 tasks (point, show, speak) for a total of 300 recordings. Each user got assigned a varied set of 10 objects out of a pool of 22 objects on the table, so that all objects have a roughly equal presence in the dataset. They were given unspecific instructions on the interactions, meaning no exact phrasing. As a result, there is a natural variation in the language usage between speakers.

Multimodal Action Recognition

This section describes an illustrative experiment showing the advantages of utilizing more than one modality of data acquired from the user interactions while teaching the robot. As we can see in prior work, such as Abdullah et al. [START_REF] Abdullah | Integrating audio visual data for human action detection[END_REF], combining language and image data can significantly boost the user action recognition.

Our dataset includes three types of interaction: Point, Show, and Speak. A rough classification of the type of interaction can simplify and optimize follow-up tasks, for example segmenting the object. If the user is pointing at an object, our system could estimate an image region where the object is very likely to be. If the user is grabbing an object and showing it to the robot, we know the object is held by the user's hand. In this case, the system should take into account that the hand is likely to occlude the object partially.

This experiment aims to recognize the three types of interactions described combining information from language and visual cues. Since we are seeking a simple pre-filter for an incremental object learning, and in order to avoid costly spatio-temporal video analysis, we propose a low-cost single-frame classifier. Figure 3a highlights the difficulty of the interaction recognition problem from a single frame. Classifying a single frame into Point, Show, or Speak can be difficult even for a human. Visual data features Our image descriptor is computed as follows. First, we segment the image into SLIC [START_REF] Achanta | Slic superpixels compared to state-of-the-art superpixel methods[END_REF] superpixels. We classify each superpixel as skin/not skin using color and depth and fuse the adjacent skin superpixels into blobs. Afterwards we divide the image into a 5 × 5 grid, with the descriptor being a histogram counting the skin votes of the blobs per each image cell.

Language data features Our language feature is the first word of each user sentence, which is 1) "that" when the user is pointing to something far; 2) "this" when the user is pointing to something close or showing something to the robot; 3) any other word if the user is just describing something to the robot, usually "the". Figure 3b shows the language feature distribution for each user and interaction. Notice that the feature is not discriminative for the classes Point and Show. A classifier cannot be trained with only this feature because the performance on those classes will simply be random.

Interaction classifier

We trained a RBF-SVM classifier first using only visual data and then using the combination vision-language. We report the confusion matrix (10-fold cross-validation) for both cases. Table 2a is vision-only and Table 2b contains the vision&language model. When comparing Table 2a and Table 2b, we can see the improvement in the division of Speak with the combination of visual-language data. In case of Point and Show there is also improvement, mostly focus on the Show interaction which is more discriminant with the language data.

Conclusion

This work presents an annotated multimodal dataset for Human-Robot interaction. A remarkable feature of the dataset is the synchronized recording of multimodal data, specifically two RGB-D cameras, one high resolution RGB camera, and audio data. We have shown how even a simple task, like classifying the type of user interaction from single-frame descriptors, can significantly benefit from multimodal data. The interaction recognition is a crucial step to facilitate future processing steps, such as automatic object and region of interest segmentation in images and videos. In addition to the interaction, our dataset presents other challenges like occlusions and low object resolution. Future lines of work, taking advantage of the multimodal dataset presented, will extend the presented approach by working on the next steps of an incremental and interactive learning framework.

Figure 1 :

 1 Figure 1: An interactive human-robot framework for incremental learning requires multiple modules: action recognition, object segmentation, incremental learning. This work includes an illustrative experiment of the action recognition step utilizing the presented MHRI dataset.

Figure 2 :

 2 Figure 2: (a) The Baxter robot setup used to record the data. (b) Examples from the dataset. Each column shows the same event captured from the 4 sensors. The first row contains the rgb-depth pair of images from the Chest-Kinect; the second row shows the rgb-depth pair from the Top-Kinect; the third one is the Face-HDcam and the last one represents the audio recorded from the user.(c) Sample images from the three user interaction types considered. The user is saying (from top to bottom) : "This is a box", while pointing at the box; "This is a box", while holding the box; "The box is next to the chips and has a banana on top."

Figure 3 :

 3 Figure 3: Challenges of interaction recognition with a single data source. (a) With visual information, it is often hard to distinguish from a single frame if the user is pointing at an object, about to pick it up, or just narrating. (b) Stacked graphic showing the language feature distribution on all recorded user interactions. Clearly, Point and Show actions can not be separated using only this language feature.

Table 1 :

 1 MHRI Dataset content summary.

	Users	10
	Interaction Types (Actions)	3	Point, Show, Speak
	Interactions per User	30	10 of each type. 1 random object per interaction.
			Apple, Banana, Bottle, Bowl, Cereal Box, Coke, Diet Coke,
	Objects	22	Ketchup, Kleenex, Knife, Lemon, Lime, Mug, Noodles, Orange,
			Plate, Spoon, Tall Mug, Tea Box, Vase

Table 2 :

 2 Confusion matrix for (a) interaction recognition using only visual data or (b) combining both visual and language features. Each row represents the ground truth and each columns the SVM-prediction.

		Point	Show	Speak		Point	Show	Speak
	Point	72,85% 12,36% 14,78%	Point	73,94% 26,06% 0,00%
	Show	76,01% 12,88% 11,11%	Show	66,45% 33,55% 0,00%
	Speak	55,46% 20,00% 24,54%	Speak	0,00%	0,00%	100%
		(a)				(b)

30th Conference on Neural Information Processing Systems (NIPS 2016), Barcelona, Spain.

The dataset can be downloaded at http://robots.unizar.es/IGLUdataset/

Acknowledgments

This research has been partially funded by the European Union (CHIST-ERA IGLU, PCIN-2015-122), the Spanish MINECO/FEDER projects DPI2015-67275, DPI2015-65962-R and DPI2015-69376-R, the Aragón regional government (Grupo DGA T04-FSE) and the University of Zaragoza (JIUZ-2015-TEC-03).