J Bussac

A NON-EQUILIBRIUM MULTI-COMPONENT MODEL WITH MISCIBLE CONDITIONS

This paper concerns the study of a full non-equilibrium model for a compressible mixture of any number of phases. Miscible conditions are considered in one phase, that lead to non symmetric constraints on the statistical fractions. These models are subject to the choice of interfacial and source terms. We show that under a classical assumption on the interfacial velocity, the interfacial pressures are uniquely defined. The model is hyperbolic and symmetrizable under non-resonance conditions. Classes of entropy-consistent source terms are then proposed.

Introduction

The present paper concerns the modelling of multiphase compressible flows which arise in many industrial applications, especially in the nuclear safety framework. Among several senarii that are studied (see IRSN website [START_REF]Accident de perte de réfrigérant primaire (aprp) avec défaillances multiples[END_REF]), the Loss Of Coolant Accident (LOCA) involves these types of flow. It is a brutal rupture in the coolant circuit that creates phase transition waves in the loop and leads to the appearance of vapor inside the liquid, these phases interacting with the ambiant air. Other types of accidents require to consider more phases, for instance in vapor explosion type scenarii [START_REF] Berthoud | Vapor explosions[END_REF]. Consequently, a model must account for the dynamical and the thermodynamical disequilibrium.

A wide range of multiphase flow models has been proposed since decades, especially in the two-phase flow situation, see for instance [START_REF] Baer | A two-phase mixture theory for the deflagration-to-detonation transition (ddt) in reactive granular materials[END_REF][START_REF] Coquel | Closure laws for a two-fluid twopressure model[END_REF][START_REF] Drew | Mathematical modeling of two-phase flow[END_REF][START_REF] Hérard | A three-phase flow model with two miscible phases[END_REF][START_REF] Kapila | Two-phase modeling of deflagration-to-detonation transition in granular materials: Reduced equations[END_REF] for the Baer-Nunziato two-fluid approach and [START_REF] Barberon | Finite volume simulation of cavitating flows[END_REF][START_REF] Hurisse | Numerical simulations of steady and unsteady two-phase flows using a homogeneous model[END_REF][START_REF] Mathis | A thermodynamically consistent model of a liquid-vapor fluid with a gas[END_REF] for the homogeneous (in terms of velocity) models. More recently, three-phase flows have been investigated with full non-equilibrium models in the immiscible [START_REF] Hantke | Closure conditions for a one temperature non-equilibrium multicomponent model of baer-nunziato type[END_REF][START_REF] Hérard | A three-phase flow model[END_REF][START_REF] Hérard | A class of compressible multiphase flow models[END_REF] and miscible [START_REF] Hérard | A four-field three-phase flow model with both miscible and immiscible components[END_REF] conditions, and also with homogeneous models [START_REF] Barberon | Finite volume simulation of cavitating flows[END_REF][START_REF] Hurisse | Numerical simulations of steady and unsteady two-phase flows using a homogeneous model[END_REF][START_REF] Mathis | A thermodynamically consistent model of a liquid-vapor fluid with a gas[END_REF]. Among all these models, two classes can be distinguished: the majority of them is based on the multifluid approach [START_REF] Baer | A two-phase mixture theory for the deflagration-to-detonation transition (ddt) in reactive granular materials[END_REF][START_REF] Coquel | Closure laws for a two-fluid twopressure model[END_REF][START_REF] Hantke | Closure conditions for a one temperature non-equilibrium multicomponent model of baer-nunziato type[END_REF][START_REF] Hérard | A three-phase flow model with two miscible phases[END_REF][START_REF] Hérard | A three-phase flow model[END_REF][START_REF] Hérard | A four-field three-phase flow model with both miscible and immiscible components[END_REF][START_REF] Kapila | Two-phase modeling of deflagration-to-detonation transition in granular materials: Reduced equations[END_REF], where each component has its own velocity field. The second one are the homogeneous models [START_REF] Barberon | Finite volume simulation of cavitating flows[END_REF][START_REF] Hurisse | A homogeneous model for compressible three-phase flows involving heat and mass transfer[END_REF][START_REF] Mathis | A thermodynamically consistent model of a liquid-vapor fluid with a gas[END_REF] where all the component share the same velocity.

In the multifluid approach, the dynamics of each component is described by an Euler-type model and the different systems are coupled through interfacial nonconservative terms and source terms which model the return to the equilibrium. Closure conditions have been investigated in the immiscible case in [START_REF] Coquel | Closure laws for a two-fluid twopressure model[END_REF][START_REF] Hérard | A three-phase flow model[END_REF] respectively for two-phase and three-phase flow. Analysis of this model for a two-phase flow has been done for instance in [START_REF] Coquel | Two properties of two-velocity two-pressure models for two-phase flows[END_REF][START_REF] Embid | Mathematical analysis of a two-phase continuum mixture theory[END_REF], and a generalization with all these features has been proposed in [START_REF] Müller | Closure conditions for non-equilibrium multi-component models[END_REF]. More recently, these type of results have been investigated with miscible conditions in [START_REF] Hérard | A three-phase flow model with two miscible phases[END_REF][START_REF] Hérard | A four-field three-phase flow model with both miscible and immiscible components[END_REF].

Date: June 17, 2022. For the sake of clarity, let us precise that the term "phase" refers to a state of the matter, "component" to a chemical substance and "field" to a component in a given phase. For instance, an hybrid mixture of liquid water, vapor water and an inert gas is composed of three fields, two phases and two components.

The present work focuses on the modelling of a N -phase mixture of M fields, with N ≤ M , where all the miscible part of the fluid is contained in the N th phase. That is a physically relevant situation where this latter phase would be the gaseous phase, and no miscibility can be observed for another state of the matter. These miscible components are then supposed to be perfectly intricate like ideal gases, and so all their statistical frations are equal [START_REF] Baer | A two-phase mixture theory for the deflagration-to-detonation transition (ddt) in reactive granular materials[END_REF] ∀k ≥ N, α k = α N .

Since we consider that no void can occur, the global volume constraint is

(2)

N k=1 α k = 1, with α k ∈ [0; 1] for all k = 1, ..., N .
The outline of the article is the following. The first part presents the model by introducing the thermodynamical framework, the system of equations and the evolution equation of the mixture entropy. Then we demonstrate the uniqueness of the pressure interfacial terms under classical hypotheses concerning the interfacial velocity. In the third part, the analysis of the convective system is investigated, by studying its hyperbolicity and the symmetrization. Finally, admissible forms of source terms are detailed, in order to satisfy the second principle of thermodynamics.

Model

2.1. Thermodynamical framework. The fluid is composed of N ≥ 2 phases that are immiscible, where only the N th phase can contain several components of number K ≥ 1. The fluid is then composed of M = N + K -1 fields. In other words, we consider a mixture of N phases and M fields, where the phase N contains all the miscible components of the fluid. We define K the set of fields, and thus we have #K = M . 1 2 3 ... N, N+1, ..., M 2.1.1. Equations of state. Each field k ∈ K is depicted by its phasic specific volume τ k > 0 and its specific energy e k > 0. The thermodynamical behaviour of each phase k is fully described by its intensive entropy function

(τ k , e k ) → s k (τ k , e k ) defined on Ω k ⊂ (R + * ) 2
, that is a complete EoS. By adopting the Gibbs formalism, each entropy function s k complies with the following differential form

(3) T k ds k = de k + p k dτ k ,
where the phasic temperature

T k = T k (τ k , e k ) and pressure p k = p k (τ k , e k ) are defined by (4) 1 T k = ∂s k ∂e k τ k , p k = T k ∂s k ∂τ k e k ,
and the phasic chemical potential by the relation ( 5)

µ k = -T k s k + p k τ k + e k .
2.1.2. Volume constraints and mixture entropy. We now turn to the description of the thermodynamical behaviour of the mixture. The volume conservation plus the miscibility hypotheses give the following relations on the statistical fractions ( 6)

N k=1 α k = 1 α k = α N for k ≥ N ,
thus the derivatives verify ( 7)

N -1 k=1 ∂ x α k = -∂ x α N .
These constraints are fundamental to manage the different mathematical proofs. We define the state vector of the field k by

Y k = (α k , ρ k , v k , e k ),
where ρ k = 1/τ k and v k is the phasic velocity. For a given mixture state (τ, e), the mixture entropy is defined as a combination of the phasic entropies with weights

m k = α k ρ k . Denoting Y = k∈K Y k , it reads (8) σ(Y) = k∈K m k s k (Y k ).
Finally, the specific total energy of the phase k is noted

E k = e k + v 2 k /2.

2.2.

Set of partial differential equations. Following the models in [START_REF] Hérard | A three-phase flow model with two miscible phases[END_REF][START_REF] Hérard | A three-phase flow model[END_REF][START_REF] Hérard | A four-field three-phase flow model with both miscible and immiscible components[END_REF][START_REF] Müller | Closure conditions for non-equilibrium multi-component models[END_REF], the fluid equations contain N transport equations on α k , for k = 1, ..., N

∂ t α k + V I (Y)∂ x α k = Φ k (Y), (9)
plus, for k ∈ K, the following Euler-type systems

(10) ∂ t (m k ) + ∂ x (m k v k ) = Γ k (Y), ( 11
) ∂ t (m k v k ) + ∂ x (m k v 2 k + α k p k ) + l∈K l̸ =k P k,l (Y)∂ x α l = S q,k (Y), ( 12
) ∂ t (m k E k ) + ∂ x (m k v k (E k + p k ρ k )) + l∈K l̸ =k P k,l (Y)V I (Y)∂ x α l = S E,k (Y),
Source terms Φ k , Γ k , S q,k , S E,k must be chosen in agreement with the second law of thermodynamics. Let us emphasize at the (Φ k ) k=1,...,N are only defined for the N first statistical fractions.

Exchanges between the different fields are accounted by non conservative terms in equations ( 9), [START_REF] Hérard | A class of compressible multiphase flow models[END_REF] and [START_REF] Hérard | A four-field three-phase flow model with both miscible and immiscible components[END_REF], involving interfacial velocity V I and interfacial pressures (P k,l ), defined for k ̸ = l. These terms must be specified in order to close the system, which will be done in Section 2.3.

Remark 1. Following recent works [START_REF] Hérard | A three-phase flow model with two miscible phases[END_REF][START_REF] Hérard | A four-field three-phase flow model with both miscible and immiscible components[END_REF], we consider that source terms and interfacial closures only depend on Y. These could depend on the derivatives of Y, as suggested for instance in [START_REF] Hérard | An hyperbolic two-fluid model in a porous medium[END_REF][START_REF] Saurel | A multiphase model with internal degrees of freedom: application to shock-bubble interaction[END_REF].

Since we consider a closed system, the total mass, momentum and energy exchanges must balance, thus the source terms must verify [START_REF] Hérard | Pressure relaxation in some multiphase flow models[END_REF] k∈K

Γ k (Y) = 0, k∈K S q,k (Y) = 0, k∈K S E,k (Y) = 0.
Moreover, as we consider no vacuum occurence, the source terms on the void fractions verify ( 14)

N k=1 Φ k (Y) = 0.
Besides, the interfacial pressure terms (P k,l ) should cancel each other [START_REF] Hérard | An hyperbolic two-fluid model in a porous medium[END_REF] k∈K l∈K l̸ =k

P k,l (Y)∂ x α l = 0,
in order to preserve the mixture conservative equations on momentum and energy.

2.2.1. Entropy production. The mixture entropy has been defined in [START_REF] Embid | Mathematical analysis of a two-phase continuum mixture theory[END_REF], and it is well known [START_REF] Hérard | A three-phase flow model with two miscible phases[END_REF][START_REF] Hérard | A four-field three-phase flow model with both miscible and immiscible components[END_REF] that it verifies the following equation ( 16)

∂ t σ(Y) + ∂ x f σ (Y) = A σ (Y, ∂ x Y) + RHS σ (Y),
where f σ (Y) = k∈K m k s k v k is the entropy flux and the production terms are defined by ( 17)

A σ (Y, ∂ x Y) = k∈K 1 T k (v k -V I ) l∈K l̸ =k P k,l (Y)∂ x α l + p k ∂ x α k ,
that correspond to the interfacial contribution, and

RHS σ (Y) = k∈K 1 T k S E,k (Y) -Γ k (Y)e k -v k (S q,k (Y) - 1 2 Γ k (Y)v k ) + ρ k ∂e k ∂ρ k (ρ k Φ k (Y) -Γ k (Y)) + k∈K s k Γ k (Y) + ρ k ∂s k ∂ρ k (Γ k (Y) -ρ k Φ k (Y)) ,
which correspond to the source terms contribution. According to the second law of thermodynamics, these production terms have to be non-negative. By following the work in [START_REF] Coquel | Closure laws for a two-fluid twopressure model[END_REF][START_REF] Hérard | A three-phase flow model[END_REF] in the two and three-phase flow context, our concern here is to determine constraints such as [START_REF]Accident de perte de réfrigérant primaire (aprp) avec défaillances multiples[END_REF] A σ (Y, ∂ x Y) = 0, corresponding to the minimal entropy dissipation model, which is the subject of the following section. The second term RHS σ relies on the source terms, that we will study later on, see 4.

2.3.

Definition of the interfacial pressures. The system of partial derivative equations ( 9)-( 12) requires an unique definition of the pressure interfacial terms. The work has been done for immiscible two, three and then N -phase flow in [START_REF] Coquel | Closure laws for a two-fluid twopressure model[END_REF][START_REF] Hérard | A three-phase flow model[END_REF][START_REF] Müller | Closure conditions for non-equilibrium multi-component models[END_REF], or more recently for hybrid mixtures in [START_REF] Hérard | A three-phase flow model with two miscible phases[END_REF][START_REF] Hérard | A four-field three-phase flow model with both miscible and immiscible components[END_REF].

For this purpose, we postulate that the interfacial velocity is a convex combination (using Galilean invariance) of the phasic velocities [START_REF] Kapila | Two-phase modeling of deflagration-to-detonation transition in granular materials: Reduced equations[END_REF] V

I (Y) = k∈K β k (Y)v k , with (20)
k∈K β k (Y) = 1 β k (Y) ≥ 0 ∀k ∈ K .
Determining the interfacial pressures (P k,l ) as it is done in [START_REF] Müller | Closure conditions for non-equilibrium multi-component models[END_REF] is out of reach due to reasons coming from the miscibility constraints. However, these constraints allow to consider another set of pressure terms that we define here.

Let us introduce the interfacial terms (K k,l ), defined for k = 1, ..., M and l = 1, ..., N -1. For the sake of clarity, we allow ourselves to write the initial pressure terms (P k,l ) for k = l. The definition is then

(21) K k,l = P k,l (1 -δ k,l ) - M j=N P k,j (1 -δ k,j ),
and the following notation for the same indices

(22) χ k,l = δ k,l - M j=N δ k,j =    0 if k ≤ N -1 and k ̸ = l, 1 if k = l, -1 if k ≥ N for all l ≤ N -1,
.

where δ k,l is the Kronecker symbol. We now introduce the following lemma that contains fundamental rewriting techniques used in this paper. Lemma 1. For all k = 1, ..., M and l = 1, ..., N -1, we have the two relations

(23) l∈K l̸ =k P k,l ∂ x α l = N -1 l=1 K k,l ∂ x α l , (24)
l∈K l̸ =k P k,l ∂ x α l + p k ∂ x α k = N -1 l=1 (K k,l + χ k,l p k )∂ x α l ,
Proof. By using miscibility constraints [START_REF] Coquel | Two properties of two-velocity two-pressure models for two-phase flows[END_REF] and relation [START_REF] Drew | Mathematical modeling of two-phase flow[END_REF], we can rewrite the sum as

l∈K l̸ =k P k,l ∂ x α l = N -1 l=1 P k,l (1 -δ k,l )∂ x α l + M j=N P k,j (1 -δ k,j )∂ x α j (25) = N -1 l=1 P k,l (1 -δ k,l )∂ x α l + ∂ x α N M j=N P k,j (1 -δ k,j ) = N -1 l=1 P k,l (1 -δ k,l )∂ x α l - N -1 l=1 ∂ x α l M j=N P k,j (1 -δ k,j ) = N -1 l=1 P k,l (1 -δ k,l ) - M j=N P k,j (1 -δ k,j ) ∂ x α l = N -1 l=1 K k,l ∂ x α l ,
where K k,l has been defined in [START_REF] Mathis | A thermodynamically consistent model of a liquid-vapor fluid with a gas[END_REF]. The second relation can be deduced by the first one, we just need to express the term

p k ∂ x α k in function of the (∂ x α l ) 1≤l≤N -1 , that is (26) p k ∂ x α k = N -1 l=1 χ k,l p k ∂ x α l ,
where χ k,l is defined by [START_REF] Müller | Closure conditions for non-equilibrium multi-component models[END_REF]. Then we deduce the relation [START_REF] Saurel | A multiphase model with internal degrees of freedom: application to shock-bubble interaction[END_REF]. □

These relations allow us to rewrite any expression involving (∂

x α l ) 1≤l≤M in terms of the first N -1 quantities (∂ x α l ) l≤N -1 .
Using Lemma 1, the momentum and energy equations ( 11)-( 12) can be rewritten

(27) ∂ t (α k ρ k v k ) + ∂ x (α k ρ k v 2 k + α k p k ) + N -1 k=1 K k,l ∂ x α l = 0, ( 28
) ∂ t (α k ρ k E k ) + ∂ x (α k ρ k v k (E k + p k /ρ k )) + N -1 k=1 K k,l V I ∂ x α l = 0,
Thereby, we have reduced the number of interfacial unknowns. Indeed, there was M (M -1) coefficients (P k,l ) and now there are M (N -1) effective coefficients (K k,l ). We can now rewrite the minimal entropy dissipation condition [START_REF]Accident de perte de réfrigérant primaire (aprp) avec défaillances multiples[END_REF] in function of the (K k,l ).

Lemma 2. The term

A σ (Y, ∂ x Y) reads (29) A σ (Y, ∂ x Y) = k∈K 1 T k (v k -V I ) N -1 l=1 (K k,l + χ k,l p k )∂ x α l ,
with (χ) k,l defined by [START_REF] Müller | Closure conditions for non-equilibrium multi-component models[END_REF].

Proof. It consists in rewriting [START_REF]Accident de perte de réfrigérant primaire (aprp) avec défaillances multiples[END_REF] in function of the N -1 firsts (∂ x α k ), using Lemma 1. □

Let us now give the main result of this paper.

Proposition 1. (Minimal entropy production due to the interfacial states) Let us assume that (15) hold true. If all the phasic temperatures are positive, then for any convex combination [START_REF] Kapila | Two-phase modeling of deflagration-to-detonation transition in granular materials: Reduced equations[END_REF], the interfacial pressure terms (K k,l ) are uniquely defined.

Proof. The idea of the proof is very similar to [START_REF] Müller | Closure conditions for non-equilibrium multi-component models[END_REF]. We determine equations thanks to

(1) The independence of the derivatives (

∂ x α k ) (2)
The independence of the relative velocities (v k+1 -v k )

Then we obtain N -1 linear systems, one for each l = 1, ..., N -1, in the variables (K k,l ) k=1,...,M .

According to [START_REF] Coquel | Two properties of two-velocity two-pressure models for two-phase flows[END_REF], the (∂ x α l ) 1≤l≤N -1 must be independant. Using this and Lemma 2, imposing A σ (Y, ∂ x Y) = 0 is equivalent to write for l = 1, ..., N -1 the following relations (30)

k∈K 1 T k (v k -V I )(K k,l + χ k,l p k ) = 0.
Using the convex combination [START_REF] Kapila | Two-phase modeling of deflagration-to-detonation transition in granular materials: Reduced equations[END_REF], we rewrite the difference v k -V I as

(31) v k -V I = k-1 i=1 i j=1 (-β j )(v i -v i+1 ) + M -1 i=k M j=i+1 (β j )(v i -v i+1 ),
that allows us to rearrange (30) in terms of the independant differences

(v i -v i+1 ). Introducing c i = i j=1 β j , c i = M j=i+1 β j , for i = 1, ..., M -1, we obtain the following relations (32) i k=1 1 T k c i K k,l - M k=i+1 1 T k c i K k,l = i k=1 1 T k c i χ k,l p k - M k=i+1 1 T k c i χ k,l p k ,
for l = 1, ..., N -1 and i = 1, ..., M -1. We define for the same indices

d i l = i k=1 a k c i χ k,l p k - M k=i+1 a k c i χ k,l p k and a i = 1 T i .
We obtain the final system defined by the following equations for l = 1, ..., N -1 and i = 1, ..., M -1

(33) i k=1 c i a k K k,l - M k=i+1 c i a k K k,l = d i l .
In other words, for any l = 1, ..., N -1, there are M -1 equations for M unknows that are the (K k,l ) 1≤k≤M . This can be compensated by adding the constraint (15) that gives, using [START_REF] Mathis | A thermodynamically consistent model of a liquid-vapor fluid with a gas[END_REF] and the independence of (∂

x α l ) l≤N -1 , for l = 1, ..., N -1 (34) k∈K K k,l = 0.
Then we have N -1 linear systems of size M × M , for each l ∈ {1, ..., N -1}, that are

(35) AK l = d l , with • A =        c 1 a 1 -c 1 a 2 -c 1 a 3 • • • -c 1 a M c 2 a 1 c 2 a 2 -c 2 a 3 • • • -c 2 a M . . . . . . c M -1 a 1 c M -1 a 2 • • • c M -1 a M -1 -c M -1 a M 1 1 • • • • • • 1        , • K l = (K 1,l , K 2,l , ..., K M,l ) ⊤ , • d l = (d 1 l , d 2 l , ..., d M l ) ⊤
. Finally, we need to show that A is regular so the (K k,l ) are uniquely determined. Let us note D = det A. The idea of the proof is to develop this determinant on the last row, then express the minors of size M -1 with a second order determinant thanks to M -3 developments.

We remind here two relations that we will need. For i = 1, ..., M -1, we have

(36) c i + c i = 1, c i+1 -c i = -β i .
By developing D on the last row and factorizing by āi , we get

(37) D = M i=1 (-1) M +i āi D i ,
where D i is the minor formed by deleting the last row and the ith column, and āi = M j̸ =i a j . For i = 1, ..., M -1, we have (38)

D i = det                c 1 -c 1 • • • -c 1 -c 1 • • • -c 1 c 2 c 2 • • • • • • -c 2 . . . -c i-1 -c i-2 . . . . . . c i-1 -c i-1 . . . c i -c i c i+1 c i+1 . . . . . . . . . c M -1 c M -1 • • • c M -1 c M -1 • • • -c M -1               
, that we can rewrite with the columns

C j = (-c 1 , ..., -c j-1 , c j , ..., c M -1 ) ⊤ ∈ R M -1 as (39) D i = det C 1 C 2 ... C i-1 C i+1 ... C M .
Then, D i can be reduced to a second order determinant with M -3 operations:

• C 1 ← C 1 -C 2 and a development along C 1 is done i -2 times, • C n ← C n -C n-1 and a development along C n is done M -(i + 1) times,
where n is the size of the considered minor.

It appears a factor (-1) for each second type operation, thus we have (40)

D i = (-1) M -(i+1) det c i-1 -c i-1 c i -c i ,
so, thanks to relations (36), we can express the latter determinant as

D i = (-1) M -(i+1) (-β i ) (41) = (-1) M -i β i ,
for i = 2, ..., M -1. On the other hand, the cases i = 1 and i

= M give D 1 = c 1 and D M = c M -1 .
Coming back to (37), we get

(42) D = ā1 c 1 + ā M c M -1 + M -1 i=2 (-1) M +i āi (-1) M -i β i , that simplifies into (43) D = ā1 c 1 + ā M c M -1 + M -1 i=2 āi β i > 0.
Since i β i = 1 and a i > 0 for all i = 1, ..., M , then det A > 0 and the interfacial terms (K k,l ) are fully determined. □ Remark 2. Even if the approach differs from [START_REF] Hérard | A three-phase flow model with two miscible phases[END_REF][START_REF] Hérard | A four-field three-phase flow model with both miscible and immiscible components[END_REF], we verified at different stages of the proof that the results were in agreement with these references.

Remark 3. (Preservation of the pressure equilibria) An important feature is the preservation of an initial steady state where the fluid is supposed to be at the thermodynamical equilibrium : the phasic pressures verify the Dalton's law, the phasic temperatures are equal to each other and the velocities are equal to zero. A detailed explanation is given in [START_REF] Hérard | Pressure relaxation in some multiphase flow models[END_REF]. This must be verified, but it seems difficult to achieve without an explicit expression of the interfacial pressure terms.

Analysis

In this section, we investigate the hyperbolicity and the symmetrization of the system.

3.1. Hyperbolicity. First, we consider the convective system associated to ( 9)-( 12) and rewrite it in the primitive variables w = (α 1 , ..., α N -1 , w 1 , ..., w M ), where

w k = (ρ k , v k , p k ). For k = 1, ..., N we have (44) ∂ t α k + V I ∂ x α k = 0, and for k ∈ K (45) ∂ t ρ k + ρ k α k (v k -V I )∂ x α k + v k ∂ x ρ k + ρ k ∂ x v k = 0, ( 46
) ∂ t v k + 1 α k ρ k l∈K P k,l ∂ x α l + p k ∂ x α k + v k ∂ x v k + 1 ρ k ∂ x p k = 0, ( 47
) ∂ t p k + ρ k α k (v k -V I ) l∈K l̸ =k C 2 k,l ∂ x α l + ρ k c 2 k ∂ x v k + v k ∂ x p k = 0,
where C k,l and c k are respectively the interfacial sound speed and the phasic sound speed, defined by

C 2 k,l = -(∂p k /∂e k )P k,l /ρ 2 k + (∂p k /∂ρ k ) , (48)
c 2 k = ∂p k /∂ρ k + p k /ρ k + p k /ρ 2 k (∂p k /∂e k ). Then, we express the (∂ x α l ) 1≤l≤M in function of the (∂ x α l ) l≤N -1 by using Lemma 1, it reads (49) ∂ t α k + V I ∂ x α k = 0, ∂ t ρ k + ρ k α k (v k -V I ) (1 - M j=N δ k,j )∂ x α k - M j=N δ k,j N -1 l=1 ∂ x α l (50) +v k ∂ x ρ k + ρ k ∂ x v k = 0 (51) ∂ t v k + 1 α k ρ k N -1 l=1 (K k,l + χ k,l p k )∂ x α l + v k ∂ x v k + 1 ρ k ∂ x p k = 0 (52) ∂ t p k + ρ k c 2 k ∂ x v k + ρ k α k (v k -V I ) N -1 l=1 γ k,l ∂ x α l + v k ∂ x p k = 0, with γ k,l = C 2 k,l (1 -δ k,l ) - M j=N C 2 k,j (1 -δ k,j
) and K k,l defined by [START_REF] Mathis | A thermodynamically consistent model of a liquid-vapor fluid with a gas[END_REF]. Note that we used the argument from Lemma 2 for the velocity equation.

Thus we have the following quasi-linear system (53)

∂ t w + B(w)∂ x w = 0, where B(w) ∈ M N -1+3M (R) is the block matrix (54) B(w) =     V I I N -1 0 ... 0 A 1 B 1 ... ... A M B M     .
The matrices

A k ∈ M 3,N -1 (R)and B k ∈ M 3 (R) are defined by (55) A k =    ρ k α k (v k -V I )(e ⊤ k (1 - M j=N δ k,j ) -1 ⊤ N -1 M j=N δ k,j ) 1 α k ρ k β ⊤ k ρ k α k (v k -V I )γ ⊤ k    , (56) B k =   v k ρ k 0 0 v k 1/ρ k 0 ρ k c 2 k v k   ,
where

• e k is the kth unit vector in R N -1 , with the convention e k = 0 if k ≥ N ,

• 1 N -1 is the vector in R N -1 whose components are all equal to 1,

• the vectors β k , γ k ∈ R N -1 are defined, for l = 1, ..., N -1, by

β k = K k,1 + χ k,1 p k , ... , K k,N -1 + χ k,N -1 p k ⊤ (57)
γ k = γ k,1 , ... , γ k,N -1 ⊤ . ( 58
)
We remark that the phasic matrices B k do not differ from the immiscible case [START_REF] Müller | Closure conditions for non-equilibrium multi-component models[END_REF], but the A k matrices do change. The eigenstructure of B is exactly the same than in this latter case, thus we only remind here the elements and refer to [START_REF] Müller | Closure conditions for non-equilibrium multi-component models[END_REF] for more details.

The eigenvalues are:

• λ I,k = V I , k = 1, ..., N -1 • λ k = v k and λ k,± = v k ± c k , k = 1, ..., M .
Remark 4. The nature and properties of these characteristic fields are as expected, see [START_REF] Embid | Mathematical analysis of a two-phase continuum mixture theory[END_REF] for their analysis in the two-phase framework. We emphasize that the nature of V I remains unknown, and so its Riemann invariants, that obviously depend on its definition. One can refer to [START_REF] Coquel | Closure laws for a two-fluid twopressure model[END_REF] where different closures for V I are investigated for a two-phase mixture, allowing to define unique jump relations.

We now turn to the determination of the eigenvectors. The matrix R composed of the right eigenvectors has a block structure and reads

(59) R =     R 0 I 0 ... 0 R 1 I R 1 ... ... R M I R M     ,
The phasic problems are well known and so R k is. For R k I , we introduce the following notations (60)

κ 0 = M l=1 α l σ l , κ k = M l=1,̸ =k α l σ l , k = 1, ..., M (61)
σ k = δ 2 k -c 2 k and δ k = v k -V I . Thus we have (62) R k I = κ k ρ k    α k c 2 k β ⊤ k -δ 2 k γ ⊤ k -(α k β ⊤ k -γ ⊤ k )δ k /ρ k -σ k (e ⊤ k (1 - M j=N δ k,j ) -1 ⊤ N -1 M j=N δ k,j ) + α k β ⊤ k -γ ⊤ k    , (63)
R 0 I = κ 0 I N -1 , R k =   1 1 1 -c k /ρ k 0 c k /ρ k c 2 k 0 c 2 k   .
The matrix R is regular under the following well known condition (64)

σ k ̸ = 0, ⇐⇒ V I ̸ = v k ± c k ∀k = 1, ..., M
called the non-resonance condition.

Proposition 2. The system (9)-( 12) is hyperbolic under the non-resonance condition (64).

The non-resonance condition appears when a genuinely non linear field associated to v k ± c k overlaps the coupling wave V I . In such a situation, the vector space is not anymore spanned by the eigenvectors.

3.2. Symmetrization. The proof of the symmetrization relies on the same arguments than in [START_REF] Coquel | Two properties of two-velocity two-pressure models for two-phase flows[END_REF][START_REF] Hérard | A three-phase flow model with two miscible phases[END_REF] and is exactly the same than in the generalized immiscible case of N phases [START_REF] Müller | Closure conditions for non-equilibrium multi-component models[END_REF]. We build a symmetric positive definite matrix P = P (w) such that P B is symmetric, by using the block structure of B and its left and right eigenvectors matrices. We remind here the general idea.

First we define P k the symmetrizer of the phasic problem by (65)

P k =   1 0 -1/c 2 k 0 0.5(ρ k /c k ) 2 0 -1/c 2 k 0 1.5/c 4 k   ,
that is a symmetric positive definite matrix. Moreover it is such that P k B k symmetric. We then define P k,α under the non-resonance condition (64) by ( 66)

P k,α = L ⊤ k (Λ k -V I I 3 ) -1 R ⊤ k P k A k
, where L k is the left eigenvectors matrix of B k and Λ k is the eigenvalues matrix of B k . We remind that these matrices verify

L k B k R k = Λ k and L k R k = I 3 .
Thus we can define the symmetrizer for B, that is

(67) P =     N P α I N -1 P ⊤ 1,α ... P ⊤ M,α P 1,α P 1 ... ... P M,α P M     ,
where P α I N -1 must be speficied. The cornerstone is that (V 1 P k,α + P k A k ) ⊤ = P ⊤ k,α B k , that traduces the symmetry of the first row and column of block of P B.

It relies on the fact than P ⊤ k,α A k is a symmetric matrix, since

P ⊤ k R k = L ⊤ k . Now we prove that P is positive definite. Let a ∈ R N -1+3M such as a = (a α , a 1 , ..., a M ), with a α ∈ R N -1 . (68) a ⊤ P a = P α N -1 k=1 N -1 i=1 a α,i + (P ⊤ k,α a k ) i /P α 2 + M k=1 1 P α a ⊤ k Qa k ,
where Q = P α P k -P k,α P ⊤ k,α . Let us determine a condition on P α such as the terms a ⊤ k Qa k are non-negative. We consider the Cholesky decomposition of

P k = C k C ⊤ k and we define E k = C -1 k P ⊤ k,α P k,α C ⊤ k
, that is a symmetric matrix. Thus, there exists T k such that

T k E k T ⊤ k = D k = diag(µ k 1 , µ k 2 , µ k 3 ), where (µ k i ) 1≤i≤3 are the eigenvalues of E k . Thus we have (69) a ⊤ k Qa k = b ⊤ k (P α I 3 -D k )b k = 3 i=1 b k,i (P α -µ k i ), with b k = T ⊤ k C ⊤ k a k . Choosing P α > max i,k |µ k i | > 0 the term a ⊤ k Qa k is non- negative and is positive for a k ̸ = 0, so a ⊤ Qa is.
Finally, the system (49)-( 52) is symmetrizable and according to Kato's theorem [START_REF] Kato | The cauchy problem for quasi-linear symmetric hyperbolic systems[END_REF], there exists a local-in-time smooth solution to the associated Cauchy problem.

Admissible source terms

We investigate in this section some conditions on the source terms in order to satisfy the second principle of thermodynamics.

We omit the dependence in Y of the source terms for the sake of readability. We first give the form of each source term, and then we determine conditions on each contribution.

Firstly, let us remark that the mechanical transfer source terms Φ k verify

(70) ∀k ≥ N, Φ k = Φ N , N k=1 Φ k = 0,
that is a consequence of the miscibility and saturation constraints. This allows us to use a similar rewriting than ( 23) and ( 24), which will be useful later.

The mass transfer term Γ k is defined as a sum of dyadic contributions

(71) Γ k = l∈K l̸ =k Γ kl ,
where Γ kl represents the mass transfer from phase k towards phase l. In practical modelling, some of these terms may be equal to zero, for example if the phase k is a non-condensable gas.

The momentum contribution is decomposed into a drag term and a mass transfer term

(72) S q,k = l̸ =k D kl + l̸ =k Γ kl v kl .
Last, the total energy source term contains thermal transfer, drag effects and mass transfer (73)

S E,k = l̸ =k Ψ kl + l̸ =k v kl D kl + l̸ =k Γ kl H kl + l̸ =k P k,l Φ l ,
plus this last term, coming from the choice of modelling we made at the beginning of the paper. Indeed, by choosing the derivatives in space for α l in the energy equation [START_REF] Hérard | A four-field three-phase flow model with both miscible and immiscible components[END_REF], the associated source term S E,k contains a mechanical contribution, that is not the case for example in [START_REF] Hérard | A three-phase flow model with two miscible phases[END_REF][START_REF] Hérard | A four-field three-phase flow model with both miscible and immiscible components[END_REF].

Let us remark some relations on these contributions. First, the dyadic contributions of (71), (72) and (73) must verify

(74) Γ kl = -Γ lk , D kl = -D lk , Ψ kl = -Ψ lk .
Those from (73) give

v kl D kl = -v lk D lk ,
that impose v kl = v lk , thanks to the independance of the D kl . Similarly, we have H kl = H lk . Now we can regroup the contributions according to their nature (75)

RHS σ = RHS Φ σ + RHS Γ σ + RHS D σ + RHS Ψ σ .
In order to ensure the entropy growth, each of these four term must be positive.

• Admissible mechanical contribution Φ RHS Φ σ = k∈K a k l̸ =k P k,l Φ l + ρ 2 k ∂e k ∂ρ k Φ k -ρ 2 k ∂s k ∂ρ k Φ k = k∈K a k l̸ =k P k,l Φ l + p k Φ k = k∈K a k l≤N -1 (K k,l + χ k,l p k )Φ l = N -1 l=1 M k=1 a k (K k,l + χ k,l p k ) Φ l .
We obtain the condition, for all l = 1, ..., N -1

(76) M k=1 a k (K k,l + χ k,l p k ) Φ l ≥ 0.
• Amissible mass transfer contribution Γ By using the relation

µ k = e k -T k s k + p k /τ k , we have RHS Γ σ = k a k l̸ =k (H kl + v 2 k 2 -v k v kl )Γ kl - k l̸ =k a k µ k Γ kl .
By setting Knowing that a k (β lk + a l (1 -β lk )) > 0, the final condition is (79) (v l -v k )D kl ≥ 0.

H kl = v k v l
• Admissible thermal transfer contribution

RHS Ψ σ = k∈K l>k Ψ kl (a k -a l ),
and so the constraint is that for k ̸ = l, (80) Ψ kl (T l -T k ) ≥ 0.

Finally, these class of source terms comply with the second principle of thermodynamics. In practical cases, see [START_REF] Hérard | A three-phase flow model with two miscible phases[END_REF][START_REF] Hérard | A four-field three-phase flow model with both miscible and immiscible components[END_REF] for instance, the condition on the mechanical contribution Φ l can be given more precisely, and we refer to these papers for more details.

Conclusion

We have addressed in this paper the study of a Baer-Nunziato-like model for a compressible N -phase flow with miscibility conditions. The main result concerns the closure laws of the pressure interfacial terms. We demonstrate that under classical conditions on the interfacial velocity, the interfacial pressure terms are uniquely defined. Explicit expressions of these terms can be given in practical situations for given values of M and N , see for instance [START_REF] Hérard | A three-phase flow model with two miscible phases[END_REF][START_REF] Hérard | A four-field three-phase flow model with both miscible and immiscible components[END_REF].

Then, the hyperbolicity and symmetrization of the convective system have been investigated. The system is hyperbolic under the classical non-resonance condition. The symmetrization gives the local-in-time existence of a smooth solution.

Finally, we have determined constraints on the source terms in order to satisfy the second principle of thermodynamics. Results are the same than in practical models where M and N are given. The missing explicit expressions of the interfacial terms Φ k may be overcome in practical situations, see [START_REF] Hérard | A three-phase flow model with two miscible phases[END_REF][START_REF] Hérard | A four-field three-phase flow model with both miscible and immiscible components[END_REF].

If we turn to approximation of solutions of system ( 9)-( 12), recent works investigated relaxation schemes dedicated to the two-phase Baer-Nunziato model with strong properties, see [START_REF] Coquel | A positive and entropy-satisfying finite volume scheme for the baer-nunziato model[END_REF], and also in the three-phase immiscible barotrope case [START_REF] Saleh | A relaxation scheme for a hyperbolic multiphase flow model. Part I: barotropic eos[END_REF]. It would be interesting to extend these works to the two-phase three-field case and to begin a numerical study.

1

 1

2 and v kl = v k +v l 2 ,v

 22 the first sum is equal to zero. Hence, it imposes(77) ∀k ̸ = l, (a k µ k -a l µ l )Γ kl ≥ 0, that is equivalent to (78) ∀k ̸ = l, ( kl D kl -v k l̸ =k D kl .We assume the following form for v kl to comply with the Galilean invariance principlev kl = β kl v k + (1 -β kl )v l , with β kl + β lk = 1 and β kl ∈ [0; 1]. Then we impose for k ̸ = l a k (1 -β kl + a l (1 -β lk ))(v l -v k )D kl ≥ 0 ⇐⇒ a k (β lk + a l (1 -β lk ))(v l -v k )D kl ≥ 0.

Nantes Université, CNRS, Laboratoire de Mathématiques Jean Leray, LMJL, F-44000 Nantes, France

Email address: jean.bussac@univ-nantes.fr


P Rolet

M Sebag

O Teytaud

Upper Confidence Trees and Billiards for Optimal Active Learning

Keywords: Apprentissage actif, Fouille d'arbre Monte-Carlo, Bandits

This paper focuses on Active Learning (AL) with bounded computational resources. AL is formalized as a finite horizon Reinforcement Learning problem, and tackled as a single-player game. An approximate optimal AL strategy based on tree-structured multi-armed bandit algorithms and billiard-based sampling is presented together with a proof of principle of the approach.

Introduction

Active Learning, a most active topic in the Machine Learning (ML) field [START_REF] Kulkarni | Active learning using arbitrary binary valued queries[END_REF][START_REF] Cohn | Improving generalization with active learning[END_REF][START_REF] Schohn | Less is more: Active learning with support vector machines[END_REF][START_REF] Dasgupta | Analysis of a greedy active learning strategy[END_REF][START_REF] Castro R | Faster rates in regression via active learning[END_REF][START_REF] Hoi | Batch mode active learning and its application to medical image classification[END_REF][START_REF] Hanneke | A bound on the label complexity of agnostic active learning[END_REF], aims at finding accurate hypotheses with a significantly lesser number of labelled examples than the standard ML setting, through a judicious selection of the instances to be labelled by the expert. Prominent approaches in the active learning field (more in section 2) rely on the properties of the hypothesis space (VC dimension or covering numbers) and/or propose various criteria estimating the additional information provided by an example; they mostly proceed by iteratively selecting the optimal example in the sense of the above criterion.

This paper presents a new perspective on Active Learning (AL), formalized as a finite horizon Reinforcement Learning problem (Sutton & [START_REF] Barto | Reinforcement learning: An introduction[END_REF]. The selection of a new sample to be labelled by the expert is viewed as an action, and the final reward associated to a sequence of actions is the generalization error of the hypothesis learned from the so completed training set. Under mild assumptions (Bayesian realizable setting) detailed in section 3, this paper presents a provably optimal AL strategy, indexed by the considered finite horizon. As could have been expected, the formal derivation of an optimal active learning strategy is intractable. A tractable approximation thereof is thus presented (section 4) and constitutes the contribution of the paper 1 . This tractable approximation involves two main ingredients. Firstly, the tree-structured multi-armed bandit algorithm first presented by [START_REF] Kocsis | Bandit-based monte-carlo planning[END_REF][START_REF] Coulom R | Efficient selectivity and backup operators in Monte-Carlo tree search[END_REF] and extensively investigated in the domain of games [START_REF] Silver | Combining online and offline knowledge in uct[END_REF], is adapted to active learning, viewed as a single-player game. Secondly, an unbiased and frugal sampler of the hypothesis and instance spaces, based on billiard-based mechanisms (Rujan 1 The theoretical part of the paper is under review at the time of writing. CAp 2009[START_REF] Rujan | Advances in Large Margin Classifiers, chapter Computing the Bayes Kernel Classifier[END_REF][START_REF] Herbrich R | Bayes point machines[END_REF] is used. A proof of principle of the BAAL (Bandit-based Active Learner) algorithm is presented, with convincing empirical evidence (section 6).

The paper is organized as follows. Section 2 briefly introduces the notations used throughout the paper and reviews the state of the art. Section 3 formally describes AL as a Reinforcement Learning problem, and how to tackle it as a single-player game. The BAAL algorithm is described in section 4; some key issues are discussed in section 5 and the goal of experiments is presented. A proof of principle of the approach is given in section 6 and the paper concludes with some perspectives for further research.

Background and State of the art

Notations and definitions used in the paper are the following. Let s T = {(x t , y t ), x t ∈ X, y t ∈ Y, t = 1 . . . T } denote a T -size training set, with X the instance space and Y the label space (unless otherwise specified, only the classification case will be considered in the paper). From s T , a learner A extracts some hypothesis h in hypothesis space H, mapping X onto Y . The learning performance most usually refers to the expectation of the loss ℓ(h(x), h * (x)) incurred by h over the target hypothesis h * , where the expectation is taken over the joint distribution P XY on the problem domain. Whereas the standard supervised learning setting assumes that training examples (x t , y t ) are iid after P XY , active learning selects in each time step t a sample x t in the instance space X (or in the sample pool), the label y t of which is determined by the oracle. A sampler S is a mapping from (X × Y ) I N to X, also referred to as policy or strategy, selecting a new sample x to be labelled after the current training set s T . A learner A is a mapping from (X × Y ) I N to H associating a hypothesis h to any training set s T . The Version Space (VS) associated to a training set s T , noted H(s T ), is the set of hypothesis consistent with s T , i.e. such that h(x t ) = y t for 1 ≤ t ≤ T . A first AL research direction focuses on the uncertainty region (set of samples where VS hypotheses disagree). [START_REF] Cohn | Improving generalization with active learning[END_REF] reduce the VS through selecting new samples in the uncertainty region. Queryby-Committee algorithms [START_REF] Seung | Query by committee[END_REF][START_REF] Freund | Selective sampling using the query by committee algorithm[END_REF]) also aim to reducing the VS; their quasi-optimality in the realizable classification case (i.e. when the target hypothesis h * belongs to H) has been established by [START_REF] Dasgupta | Analysis of a greedy active learning strategy[END_REF]. More generally, when there exists a probability measure P H on H, AL aims to either reducing the measure of the version space, or the variance of the VS hypothesis labels2 .

Another AL research direction focuses on error reduction, meant as the expected generalization error improvement brought by an instance [START_REF] Cohn | Active Learning with Statistical Models[END_REF][START_REF] Freund | Selective sampling using the query by committee algorithm[END_REF][START_REF] Iyengar | Active learning using adaptive resampling[END_REF][START_REF] Mccallum | Toward optimal active learning through sampling estimation of error reduction[END_REF][START_REF] Lindenbaum | Selective sampling for nearest neighbor classifiers[END_REF]; many criteria, reflecting various measures of the expected error reduction, have been proposed and AL proceeds by greedily selecting the optimal samples in the sense of the considered criterion.

Other approaches exploit prior, learner-dependent knowledge about what makes a sample informative, e.g. its margin [START_REF] Schohn | Less is more: Active learning with support vector machines[END_REF]. [START_REF] Hoi | Batch mode active learning and its application to medical image classification[END_REF] considers batch active learning, querying a subset of samples that results in the largest reduction of the Fisher information. These approaches however happen to face learning instabilities, which might require to mix the active learning selection with a uniform selection [START_REF] Southey | Software testing by active learning for commercial games[END_REF]. Such instabilities suggest that an efficient AL system can hardly be obtained by iteratively selecting the most informative samples, at least using the criteria considered so far.

On the theoretical side, significant results have been obtained in terms of lower and upper bounds on the reduction of the sample complexity brough by AL, e.g. depending on the complexity of the hypothesis search space measured through covering numbers or Kolmogorov complexity [START_REF] Kulkarni | Active learning using arbitrary binary valued queries[END_REF][START_REF] Vidyasagar | A Theory of Learning and Generalization, with Applications to Neural Networks and Control Systems[END_REF][START_REF] Castro R | Faster rates in regression via active learning[END_REF]; the suitedness of hypothesis spaces to active learning has been studied [START_REF] Dasgupta | Coarse sample complexity bounds for active learning[END_REF][START_REF] Hanneke | A bound on the label complexity of agnostic active learning[END_REF] and an "almost" optimal (though intractable) algorithm has proposed by [START_REF] Dasgupta | Coarse sample complexity bounds for active learning[END_REF] in the realizable setting for finite VC-dimension.

An optimal Active Learning strategy

The rest of the paper relies on three assumptions: i) Bayesian setting (the existence of a probability measure P H on the hypothesis space H); ii) realizable setting (the target concept h * is deterministic and belongs to H); iii) short time horizon (the total number T of samples to be labelled along the AL process is in the order of tens or hundreds). Under these assumptions, this section formalizes AL as a Partially Observable Markov decision process (POMDP). The search for an optimal AL strategy is viewed as a Reinforcement learning problem, and tackled as a one-player game.

AL as a Markov Decision Process

Markov decision processes are basically described in terms of states, actions, reward, policy and transition functions [START_REF] Barto | Reinforcement learning: An introduction[END_REF]. As a first step, the state space S of AL is viewed as the set of possible training sets s t (this statement will be refined in section 3.2 since the unobserved target hypothesis is also part of the state). An action corresponds to the selection of a new sample to be labelled; let A denote the set of actions.

The reward function associated to state s t corresponds to the generalization error of the hypothesis A(s t ) learned from s t ; accordingly, the reward function is unknown except for horizon states (t = T ).

Any sampler S, mapping a state s t onto an action (a new sample x t+1 ), is a policy. Lastly, the transition function p : S × A × S → R + defines the probability of arriving at some state s t+1 by selecting action x in state s t (see below).

Considering horizon T , let S T (h) denote the training set built by applying T times policy S when learning the target concept h, and denote Err(A(S T (h)), h) the generalization error of the hypothesis learned from S T (h). It comes naturally that an optimal AL strategy is one minimizing the expectation of Err(A(S T (h)), h) when h ranges in H:

S * T = arg min S E h∼H Err(A(S T (h)), h). (1)
Likewise, let s T be a training set built after T decisions of the S policy; after the realizable assumption, the target hypothesis h is only bound to be in the version space of s T ,

CAp 2009 noted H(s T ). The reward function (value at horizon T ) V (s T ) thus is the expectation of the generalisation error, taken over H(s T ):

V (s T ) = E h∼H(s T ) Err(A(s T ), h). (2)
It remains to characterize transition function p(s t , x, s t+1 ). By construction, p is zero for all s t+1 except for s t+1 = (s t , (x t+1 = x, y t+1 )). In the latter case, p reflects the probability for the label of x to be y t+1 . After the same argument as above, p(s t , x, s t+1 ) is thus expressed as a function of the probability of the label of x, conditionally to the fact that the target hypothesis varies in H(s t ):

p(s t , x, (s t , (x t+1 = x, y t+1 ))) = p(h(x) = y t+1 |h ∈ H(s t )) (3)
It is shown that the above value (Eq. ( 2)) and transition (Eq. ( 3)) functions yield an optimal active learning sampling strategy in the sense of the minimization of the expected generalization error (Eq. ( 1)).

Theorem 1 (Optimal active learning policy) Let E denote the expectation operator defined after Eq. 3. Let value function V * be recursively defined as follows, where |s| denotes the number of examples in training set s:

V * (s) = E h∼H(s) Err(A(s), h) if |s| = T inf x∈X E s ′ ∼p(st,x,s ′ ) V * (s ′ ) otherwise (4)
Let the associated Bellman optimal strategy S * ,T be defined as:

S * ,T (s) = arg inf x∈X E s ′ ∼p(st,x,s ′ ) V * (s ′ ) (5)
Then S * ,T is optimal in the sense of Eq. ( 1).

A Partially Observable MDP

As mentioned earlier on, AL actually is a Partially Observable Markov Decision Process (POMDP): a state involves both the (observed) current training set, and the (unknown) target hypothesis. After [START_REF] Astrom | Optimal control of Markov decision processes with incomplete state estimation[END_REF] a POMDP can however be solved by MDP techniques, provided that the state set include all possible events (here, the possible sequences of samples and associated labels). In the AL context the size of the state set is however overwhelmingly large. An alternative to "embedding" the hidden variable in the state set is to model the hidden variable within the transition function of the MDP (Eq. ( 3)) and the reward function (Eq. ( 2)) [START_REF] Astrom | Optimal control of Markov decision processes with incomplete state estimation[END_REF]. This alternative leads to formalizing AL as a one player game, as follows. In each game, the AL strategy plays against an (unknown) hypothesis h, sampled in the version space H(s * ) of the initial training set s * after the realizable setting assumption 3 . Upon each move (selection of a sample x), hypothesis h is used as an oracle to label y = h(x). At the end of the game (after T samples have been selected, defining training set s T ), the reward can actually be estimated as the generalization error of A(s T ) (the hypothesis learnt from s T ) against h. The empirical reward thus is computed as a uniform draw of the random variable Err(A(s), h), where h ranges in H. The average empirical reward collected by the AL player after many games thus asymptotically converges toward the true expectation of this random variable, that is, the desired reward function (Eq. ( 2)).

Tractable Approximations of Optimal AL strategy

This section presents a tractable approximation of the optimal active learning strategy, relying on two components. Firstly, the UCT algorithm proposed for tree-structured multi-armed bandits [START_REF] Kocsis | Bandit-based monte-carlo planning[END_REF] is extended to the one-player game of AL. Secondly, a fair and frugal sampling algorithm, based on billiard approaches [START_REF] Herbrich R | Bayes point machines[END_REF], is proposed.

Bandit-based Active Learning

The UCT (Upper Confidence Tree) algorithm can be viewed as a Monte-Carlo treesearch algorithm [START_REF] Coulom R | Efficient selectivity and backup operators in Monte-Carlo tree search[END_REF], with the specificity of using the well-founded multiarmed bandit framework [START_REF] Auer | Using confidence bounds for exploitation-exploration trade-offs[END_REF] to select an arm (child node) at each node, thus offering good guarantees about sequential optimal decision under uncertainty. Notably, UCT became famous in the domain of strategic games as it inspired the computer-Go program MoGo, first to ever win over professional human players [START_REF] Silver | Combining online and offline knowledge in uct[END_REF].

UCT-based game strategy provides the basis for the proposed BAAL algorithm. The actual tree T is initialized to the root node (the current game position, here the initial training set s * ). T is constructed iteratively through N tree-walks, or simulations, where N is a user-supplied parameter controlling the computational resources. Each tree-walk starts by drawing the pretended target hypothesis h in H(s * ) (section 3.2), which will be used as oracle during this tree-walk. At each node s, either its child nodes belong to T ; or s is a leaf node of T . In the former case, some child node (sample x) is selected after Eq. ( 6), its label is set to h(x), and the next node is s ∪ (x, h(x)). In the latter case, a random path (selection of samples) is followed until reaching the maximum path length T , thus defining a training set s T . At this point the empirical reward (generalization error of A(s T ) w.r.t h) is computed, and used to update the reward estimates of the path nodes belonging to T ; further, the first node in the path not belonging to T is added to T .

The equation used to select the child node, referred to as Upper Confidence Bound (UCB) [START_REF] Auer | Using confidence bounds for exploitation-exploration trade-offs[END_REF], selects the i-th arm which maximizes the sum of the empirical reward μi (exploitation), and an exploration term depending on the number n i of times arm i has been selected; the exploration vs exploitation tradeoff is adjusted using some tuned constant C:

arg max i∈child nodes μi + C log( j∈child nodes n j ) n i (6)
Algorithm 1 Left: The BAAL algorithm, with input: measure P H on hypothesis space H; initial training set s * ; time horizon T ; number N of allowed tree-walks, returns a sample x to be labelled by the oracle. Right:

Tree-Walk(s, t, h) Increment n(s)
// number of times s has been visited BAAL (Alg. 1) implements UCT with two specific ingredients, the DrawHypothesis function used to select the random variable h for each tree-walk (section 4.3), and an ArmSet function needed to handle the huge number of arms (samples) (section 4.2). BAAL takes as input the probability distribution P H on hypothesis space H (Bayesian setting); the initial training set s * ; the time horizon T ; the number N of allowed treewalks. Its output is the sample x to be labelled by the oracle.

if t==0 then Compute r = Err(A(s), h) else X (s) = ArmSet(s, n(s)) Select x * = U CB(s, X (s))) // recursively call Tree-Walk r = Tree-Walk(s {(x * , h(x * ))}, t - 1, h) end if // update reward of leaf node s r(s) ← (1 -1 n(s) )r(s) + 1 n(s)

Progressive Widening

After Eq. ( 6), UCB requires each arm to be selected at least once. In the case where the number of arms is large w.r.t the time horizon, UCB thus tends to degenerate into pure exploration; the tuning of the tradeoff constant C cannot enforce an effective exploration vs exploitation tradeoff. UCT faces the same limitation, and even more so as many arms need be considered at each node of the tree. The progressive widening heuristics has been proposed by [START_REF] Coulom R | Efficient selectivity and backup operators in Monte-Carlo tree search[END_REF] to handle such cases. Let n denote the number of times node s has been visited so far; then the number of arms (branches) that can be considered from s is empirically limited to m = ⌊n 1/4 ⌋ [START_REF] Coulom R | Efficient selectivity and backup operators in Monte-Carlo tree search[END_REF][START_REF] Chaslot | Progressive strategies for montecarlo tree search[END_REF][START_REF] Wang | Algorithms for infinitely many-armed bandits[END_REF]. Typically, a single arm will be explored from the root node in the first fifteen tree-walks; an additional arm is considered in the sixteenth random walk; UCB will be used to select among both arms during random walks 16 to 80; a third arm is considered in random walk 81, and so forth.

The rationale behind this heuristics is that the better (i.e. the more visited) s, the more careful the investigation of its subtrees should be. In the AL context, progressive widening relaxes the finite sample pool assumption: function ArmSet returns the first m candidate samples, with m = ⌊n 1/4 ⌋, extracted from the pool or from the instance space in a random (fixed) order. ArmSet also provides room for hybridizing BAAL with AL criteria such as Maximum Uncertainty, as will be shown in section 5.2.

Billiard-based Hypothesis Sampling

BAAL relies on the uniform sampling of the hypotheses in H(s * ). The sampling mechanism we used is a ray-tracing a.k.a. billiard algorithm inspired from [START_REF] Rujan | Advances in Large Margin Classifiers, chapter Computing the Bayes Kernel Classifier[END_REF][START_REF] Herbrich R | Bayes point machines[END_REF].

Let us consider a connected domain Ω ⊂ IR d , defined from a set of constraints g 1 , . . . , g n : Ω = {x ∈ IR d s.t. g i (x) ≥ 0, i = 1 . . . n}. The billiard algorithm considers a point z ∈ IR d (not necessarily in Ω) and a direction v ( v ∈ IR d , || v|| = 1). The trajectory followed by z is such that: i) the set of constraints satisfied by z does not decrease; ii) z "bounces" when it meets an active constraint g, i.e. its direction v is changed into its symmetrical with respect to g (elastic shock); iii) the trajectory is stopped when the computational resources are exhausted, that is when its total length reaches some user-defined parameter L, and the final point is returned. Under strong conditions (small d and "sufficiently regular" constraints), and up to a few exceptions (excluding for instance the case of a rational initial direction v), a billiard trajectory is ergodic, i.e. it covers the whole domain when L goes to infinity; the distribution of the final trajectory point converges toward the uniform distribution on Ω. Although these

s 0 x 1 k k k k k k k k k k k k k k k k k k k x 2 ... x P s 10 0 Ø Ø Ø Ø Ø Ø Ø
F F F F F F x 1 l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l x 2 ... x P s 2110 0 Ø Ø Ø Ø Ø Ø Ø Ø Ø Ø Ø Ø Ø Ø s 2111 1 T T T T T T T s T O O O O O O O O
Figure 1: Search Tree developed by BAAL (binary classification case). At any state s t , a sample x is selected and labelled using the current random variable h draw.

good properties are only conjectured in the general case, billiard algorithms have been successfully used in ML, e.g. to estimate the Bayes classifier in a (high-dimensional) kernel feature space [START_REF] Rujan | Advances in Large Margin Classifiers, chapter Computing the Bayes Kernel Classifier[END_REF].

Algorithm 2 Billiard. Input: set of constraints g i , length L. Output: final point.

Randomly select z ∈ IR d satisfying at least one (but not necessarily all) constraints, and a direction v. while L > 0 //Find the set of satisfied constraints do J = {j; gj(p) ≥ 0}

//Go as far as possible while gj ≥ 0, j

∈ J λ * = sup{λ ≥ 0 s.t. ∀ℓ < λ, ∀j ∈ J, gj(z + ℓ v) ≥ 0} if J = {1, . . . , n} (all constraints satisfied) then if L > λ * then p = p + λ * v //Go until some gi is saturated L = L -λ * else Return p + L v //out of resources end if end if v = symmetric( v, gi)
//Bounce against gi end while

In the active learning case, the target domain is the hypothesis version space defined from the initial training set; each training example defines a constraint. In the simple case where the hypothesis space H is the set of separating hyperplanes, the bounce operator is defined as follows. Let x i be the "saturated constraint", let v = αx i + βv ′ (with < v ′ , x i >= 0), then symmetric( v, x i ) = -αx i + βv ′ (up to normalization).

Discussion

A key issue for UCT-based approaches concerns the trade-off between the number of tree-walks, aka simulations, used to estimate the targeted rewards, and the precision and cost of each simulation. In BAAL, each simulation involves two types of random variables: the random hypothesis h used as oracle (DrawHypothesis), and the choice of a new candidate arm when the number of visits to the current node reaches a new threshold (ArmSet). This section discusses the weaknesses of both functions, proposes some refinements, and finally defines the goal of experiments.

A better reward estimate

Although BAAL is based on an unbiased estimate of the reward (section 3.2), this estimate might have a high variance for it is based on a single hypothesis draw. Such a high variance might adversely affect the convergence of BAAL. UCB (Eq. 6) might stick to an arm for a while, even though this arm is non optimal, if this arm has gotten a few lucky rewards. In such cases, UCT will investigate in more depth the tree branches corresponding to these lucky arms, after the asymmetric development of the search tree (section 4.1). As these branches are more investigated, "cumulatively misleading" evidence is produced: the associated rewards look excellent while the true optimal branches are missed. All in all, a high reward variance might cause BAAL to leave aside optimal samples for a long while. In order to overcome this weakness, a better reward estimate will be considered: after a T -size training set s T has been built based on the draw of h, R additional hypotheses h 1 , . . . h R are uniformly sampled in H(s T ). The estimated reward is computed by averaging Err(A(s T ), h) and Err(A(s T ), h i ) for i = 1 . . . R. This BAAL variant referred to as Av(R)-BAAL involves R additional calls to the DrawHypothesis function, and reduces the reward variance by a factor √ R.

BAAL with Maximum Uncertainty

Likewise, BAAL can ignore optimal samples for a while if ArmSet considers an unlucky sample order: late introduced samples are at a disadvantage compared to the first ones, more investigated. Two variants of BAAL inspired from the uncertainty region [START_REF] Cohn | Improving generalization with active learning[END_REF][START_REF] Freund | Selective sampling using the query by committee algorithm[END_REF] are investigated to overcome this weakness. The uncertainty region, including all samples for which some hypotheses in the version space disagree, shrinks as the training set increases. In such cases, when ArmSet considers a randomly ordered sample pool, BAAL (referred to as RND-BAAL in the following) tends to select samples outside of the uncertainty region, thus gaining little information.

A first variant, referred to as MU-BAAL, thus orders the sample pool considered by ArmSet after the Maximum Uncertainty criterion, akin [START_REF] Freund | Selective sampling using the query by committee algorithm[END_REF].

A second and less aggressive variant, referred to as UR-BAAL, only biases the sample order toward the uncertainty region, with two motivations: computational savings, and better sample diversity compared to MU-BAAL. Practically, when a new sample is needed, the uncertainty region is sampled as follows. A hypothesis h U R is sampled in the version space of the current s t ; ii) a sample x, uniformly selected in the instance space, is projected onto h U R , thus defining a sample x U R (i.e. h U R (x U R ) = 0); iii) x U R is returned. The rationale behind this heuristics is that hypotheses "close to" h U R likely also belong to the version space; x U R being on the frontier of h U R will thus be classified differently by hypotheses close to h U R , that is, x U R belongs to the uncertainty region. In the experiments, hypothesis space H is set to the set of separating hyperplanes; the projection of x onto h U R thus is straightforward.

Goal of the experiments

The experimental validation of BAAL will be conducted in order to answer three questions. The first question naturally regards the performance of BAAL w.r.t the dimension of the instance space and the computational resources available, namely the time horizon and the number N of tree-walks allowed; along the same line, the impact of the billiard algorithms on the scalability of the approach is examined. A second question relates to the dilemma Better vs More simulations. Two types of refinement have been considered, enforcing low-variance estimates of the reward (section 5.1), or the selection of samples in the uncertainty region (section 5.2).

Experimental validation

This section describes the experimental setting and reports on the validation of the approach.

Experimental setting

Following [START_REF] Freund | Selective sampling using the query by committee algorithm[END_REF] and followers, the hypothesis space H is set to the homogenous separating hyperplanes on the instance space X = IR d . Distribution P H is uniform on the unit sphere of IR d . Each run is based on the selection of a target hypothesis h; a T -size training set s T is built, where instance x 1 is set to BAAL({}, T, N ), x 2 is set to BAAL({(x 1 , h(x 1 ))}, T -1, N ), and so forth. The performance of the run is Err(A(s T ), h), where learner A uniformly samples H(s T ). The overall performance is averaged over 300 independent runs. Time horizon T is set to 10. Dimension d is set to 2, 4, and 8; N is set to 2 i for i = 0, . . . , 18.

Two baseline algorithms are considered: the random active learner (RND) and the greedy Maximum Uncertainty, selecting in each step the example with maximum uncertainty in a 1,000-sample pool (MU-1000). By construction, the performance of the baseline corresponds to N = 1 tree-walks.

Performance and Scalability

RND-BAAL (using a randomly ordered 1,000 sample pool) significantly improves on the baseline as the number N of tree-walks increases (Fig. 2 (a) and (b); the baseline performances correspond to N = 1). The generalization error decreases from circa 7% to 1% (respectively from 28% to 23%) for N = 2 15 in dimension 2 (resp. dim. 8). MU-BAAL (sorting a 1,000 sample pool after Maximum Uncertainty) reaches the same [START_REF] Freund | Selective sampling using the query by committee algorithm[END_REF] in dimension 2, whatever the computational effort. This result is explained as the maximum uncertainty criterion is quasi-optimal for homogeneous hyperplanes in dimension 2 [START_REF] Dasgupta | Analysis of a greedy active learning strategy[END_REF]. Interestingly, in dimension 8 MU-BAAL does improve on Query-by-Committee; a tentative interpretation for this fact is that the 1,000 sample pool is sorted after a 100 committee; as the sample order becomes less accurate due to the higher dimension, it offers some room for improvement, and MU-BAAL does modestly but significantly improve on Query-by-Committee. Independently, the billiard-based sampling of the version space H(s T ) is compared to the rejection-based sampling (uniformly drawing h in H, until h belong to H(s T )); with same performances, billiard-based sampling shows one or several orders of magnitude cost reduction (Table 1).

More vs better simulations

Several variants of BAAL have been investigated (results omitted due to lack of space). Unexpectedly, Av(R)-BAAL, involving a low-variance reward estimate through averaging the reward over R = 10 or R = 50 hypotheses sampled in H(s T ) (section 5.1) does not improve the performance for d = 4 or 8, (Fig. 3.(a)) while significantly increasing the computational cost. Similar results were observed in the context of computer-Go [START_REF] Silver | Combining online and offline knowledge in uct[END_REF]. A tentative interpretation goes as follows: the more sophisticated the simulations, the more likely they suffer from some hidden bias, and the more chances they mislead the game strategy. The sampling of the uncertainty region (UR-BAAL, (

Conclusion and Perspectives

The main contributions of this paper regard AL with bounded computational resources.

It is believed that this perspective is relevant to many potential application domains of ML, such as Numerical Engineering, which can only afford some tens or hundreds of labelled examples as computing the response of a single sample might require days or weeks of computation.

The presented BAAL algorithm relies on a sound formalization of AL as a finite horizon reinforcement problem. Its pratical implementation relies on viewing active learning as a one-player game, tackled through a tree-structured multi-armed bandit algorithm. A proof of principle of the validity of the approach shows convincing empirical evidence. Further developments include the extension of BAAL to non-linear hypothesis spaces, including the development and analysis of billiard algorithms in such spaces.

  Figure2: BAAL: Generalization error vs log(N ) (computational effort), time horizon 10, dimension = 2,8.

  Figure 3: BAAL variants: Time horizon 20, dimension 4

Table 1 :

 1 Computational cost of billard-based sampling and rejection-based sampling w.r.t dimension d and time horizon T , for N = 16, 000 performances as MU-based active learning, aka Query-by-Committee

	Dim. d Horizon T	Reject	Billiard
	4	10	87s	40s
		20	1h10m	138s
	8	10	300s	51s
		20	>1 day	169s

In case such a probability measure P H does not exist, then the reduction of the version space can be expressed in terms of its diameter, that is, the measure of points where VS hypotheses differ.

For the sake of simplicity and when no confusion is to fear, the initial training set s * is omitted and H is used instead of H(s * ).