Dongshuang Hou
email: dshhou@126.com

Aymeric Lardon

Panfei Sun

Theo Driessen

Compromise for the per capita complaint: an optimization characterization of two equalitarian values

Keywords: Cooperative game, optimal complaint values, equalitarian values, equal maximal per capita complaint properties JEL Classification System: C71 MSC (2000) Classification: 91A12

The main purpose of this article is to introduce two new values for transferable utility (TU) games: the upper and lower optimal complaint values. These are based on two kinds of per capita complaint criteria and each involve a lower and upper bound of the core (Shapley, 1955 [13]). In the spirit of the nucleolus (Schmeidler, 1969 [12]), these two values are obtained by lexicographically minimizing a maximal complaint vector associated with each of the per capita complaint criterion. Interestingly, the upper and lower optimal complaint values respectively coincide with the Equal Allocation of Non-Separable Contributions (Moulin, 1985 [10]) and the Center-of-Gravity of Imputation Set Value (Driessen and Funaki, 1991 [4]) for a large class of TU-games. Moreover, a characterization of these two values is achieved by invoking the equal upper and lower maximal per capita complaint properties together with efficiency.

Introduction

Cooperative game theory is a mathematical framework to model and analyze allocation problems within a group of players establishing a contract on a joint plan of activities. A cooperative game with transferable utility (henceforth a TU-game) on a given set of players is a function which specifies, for each coalition of players, the amount its members can achieve without the help of any other player. A solution associates with each TUgame a non-empty set of payoff vectors that generally represents the possible allocations of the worth created when all players cooperate within the grand coalition. A value is a (single-valued) solution which assigns a single payoff to each player in the TU-game. The payoff received by a player can then be interpreted as his or her gains for participating in the TU-game. The core, one of the most fundamental (set-valued) solution concepts for TU-games, was proposed by [START_REF] Shapley | Markets as cooperative games[END_REF] [START_REF] Shapley | Markets as cooperative games[END_REF]. Roughly speaking, no coalition has an incentive to deviate from the grand coalition and guarantee its members a larger payoff on a core allocation. Once an allocation is made in a TU-game, players may be dissatisfied about their received payoffs and express an amount of complaint within a coalition. [START_REF] Davis | The kernel of a cooperative game[END_REF] [START_REF] Davis | The kernel of a cooperative game[END_REF] introduced the complaint of a coalition based on the excess criterion to determine the kernel of TU-games. The excess of a coalition manifests its members' potential to generate more utility if they decide to contest an allocation. In the same vein, [START_REF] Grotte | Computation of and observations on the nucleolus, the nomalized nucleolus and the central games[END_REF] [START_REF] Grotte | Computation of and observations on the nucleolus, the nomalized nucleolus and the central games[END_REF] proposed the per capita excess, which, for each coalition, measures the dissatisfaction per player about a payoff distribution. In this article, we propose alternative measures of players' dissatisfaction about an allocation in terms of per capita complaint involving a lower and upper bound of the core. For a TU-game with a non-empty core, a player's marginal contributions to the grand coalition can be seen as his or her ideal payoff since this corresponds to an upper bound of the core. Thus, when the sum of players' marginal contributions to the grand coalition cannot be covered by the worth of the grand coalition, some of them don't receive their expected payoffs and express an amount of complaint about a core allocation. Alternatively, coalition members may be satisfied if the other players only receive their individual amounts which constitute a lower bound of the core. Thereby, when the sum of players' individual worths can be covered by the worth of the grand coalition, players may complain about a core allocation since some other players obtain payoffs strictly greater than their individual worths. Based on the idea that the core is bounded above by players' marginal contributions to the grand coalition, for each coalition, we use the average gap between the sum of its members' marginal contributions to the grand coalition and the sum of their payoffs to determine the upper per capita complaint about an allocation. On the other hand, since the core is bounded below by players' individual worths, for each coalition, we compute the average gap between the sum of its non-members' payoffs and the sum of their individual worths to define the lower per capita complaint about a payoff distribution. From these two new measures of players' dissatisfaction, we define the upper and lower optimal complaint values, which, in the spirit of the nucleolus (Schmeidler, 1969 [12]), are obtained by lexicographically minimizing a maximal complaint vector associated with each of the two per capita complaint criteria described above. The most salient properties of these two values stems from the fact that, for a large class of TU-games, they respectively coincide with two equalitarian values, namely the Equal Allocation of Non-Separable Contributions (Moulin, 1985 [10]) and the Center-of-Gravity of Imputation Set Value (Driessen and Funaki, 1991 [4]). More precisely, when the sum of players' marginal contributions to the grand coalition cannot be covered by the worth of the grand coalition, the upper optimal complaint value is bounded above by such contributions. Moreover, when the sum of players' individual worths can be covered by the worth of the grand coalition, the lower optimal complaint value is bounded below by the individual worths. The Equal Allocation of Non-Separable Contributions and the Center-of-Gravity of Imputation Set Value have received considerable attention over the past few years, including several works focused on the axiomatic characterization of these two values invoking consistency principles together with other standard axioms for TU-games (Hwang, 2006 [7]; Xu et al., 2013 [16], 2015 [START_REF] Xu | Associated consistency characterization of two linear values for TU games by matrix approach[END_REF]). 1 Another interesting approach adopted by Béal et al. (2016) [START_REF] Béal | Comparable Axiomatizations of Two Allocation Rules for Cooperative Games with Transferable Utility and Their Subclass of Data Games[END_REF] uses the axiom of balanced collective contributions, inspired by the axiom of balanced contributions proposed by [START_REF] Myerson | Conference structures and fair allocation rules[END_REF] [START_REF] Myerson | Conference structures and fair allocation rules[END_REF], and the classical axiom of efficiency to characterize the Equal Allocation of Non-Separable Contributions. In this article, we focus on the axiomatic characterization of these two equalitarian values. Several solution concepts such as the (per capita) nucleolus and the kernel have been characterized on the basis of the optimization approach (see, for example, Huijink et al., 2015 [6]). Drawing on the upper and lower per capita complaint criteria, we propose two new axioms: the equal upper and lower maximal per capita complaint properties. These are inspired by the idea of the (pre-) kernel (Maschler and Peleg, 1966 [8], Maschler et al., 1972 [9]), which, together with efficiency, uniquely determine the Equal Allocation of Non-Separable Contributions and the Center-of-Gravity of Imputation Set Value. The article is organized as follows. Section 2 provides basic definitions and notations. The two optimal complaint values are introduced and studied in Section 3, with Section 4 devoted to their axiomatic characterizations. Finally, Section 5 concludes.

Definitions and notations

Let N = {1, 2, . . . , n} be a fixed and finite set of n players. An element i ∈ N is a player, while a non-empty subset S ⊆ N is a coalition, whose cardinality will be denoted by |S|. A cooperative game with transferable utility, or simply a TU-game, on the set N of players is a real-valued function v defined on the set 2 N of all subsets of N such that v(∅) = 0. For each coalition S ⊆ N , v(S) describes the value that coalition S can achieve when all its members cooperate. The set of all TU-games on N is denoted by Γ N . An allocation among the players is given by a n-tuple vector x = (x 1 , x 2 , • • • , x n ), called a payoff vector, whose components are real numbers. For notational convenience, we will write Σ i∈S x i as x(S). A solution on Γ N is a function ϕ, which associates with each TU-game v ∈ Γ N , a subset ϕ(v) ⊆ R n of payoff vectors. If ϕ assigns a unique payoff vector to each TU-game v ∈ Γ N , then ϕ is called a value. For a TU-game v ∈ Γ N , the pre-imputation set I * (v) is defined as:

I * (v) = {x ∈ R n | x(N ) = v(N )}.
Each element of I * (v) is a pre-imputation, whose the worth of the grand coalition is fully distributed among the players. The additional individual rationality condition permits to characterize the imputation set I(v) defined as:

I(v) = {x ∈ I * (v) | ∀i ∈ N, x i ≥ v({i})}.
Each element of I(v) is an imputation, whose players receive payoffs larger than or equal to their individual worths. It is worth noting that (Shapley, 1955 [13]) is defined through group rationality and efficiency conditions as follows:

I(v) = ∅ if and only if j∈N v({j}) ≤ v(N ). The core C(v)
C(v) = {x ∈ I * (v) | ∀S ⊆ N, x(S) ≥ v(S)}.
The set of TU-games with a non-empty core is denoted by Γ N 0 . For a TU-game v ∈ Γ N and a payoff vector x ∈ R n , the excess of a coalition with respect to x (Davis and Maschler, 1965 [START_REF] Davis | The kernel of a cooperative game[END_REF]) is defined as:

∀S ⊆ N , e v (S) = v(S) -x(S).
The excess of a coalition can be viewed as its complaint about a payoff distribution, i.e. the higher the excess is, the more dissatisfied coalition members feel. The excess criterion serves as the basis of several solution concepts for TU-games, such as the core (Shapley, 1955 [13]), the nucleolus (Schemeidler, 1969 [START_REF] Schmeidler | The nucleolus of a characteristic function game[END_REF]), and the kernel (Davis and Maschler, 1965 [3]). For example, the core results in non-positive excesses. In the next section, we will propose two new per capita complaint criteria, which will turn out to be closely related to well-known equalitarian values for TU-games introduced now. The Equal Allocation of Non-Separable Contributions (Moulin, 1985 [10]), denoted by EANSC(v), is the value defined as:

∀i ∈ N , EANSC i (v) = b v i + 1 n v(N ) - j∈N b v j ,
where,

∀i ∈ N , b v i = v(N ) -v(N \ {i}).
The EANSC value is characterized by the fact that after each player has obtained his or her marginal contribution to the grand coalition, the rest of non-separable contributions is equally distributed among its players. The Center-of-Gravity of Imputation Set Value (Driessen and Funaki, 1991 [4]), denoted by CIS(v), is the dual of the EANSC value, where the dual v D of a TU-game v ∈ Γ N is given by:

∀S ⊆ N , S = ∅, v D (S) = v(N ) -v(S).
Therefore, the CIS value is defined as:

∀i ∈ N , CIS i (v) = EANSC i (v D ), = v({i}) + 1 n v(N ) - j∈N v({j}) .
The CIS value gives to each player his or her individual worth and then equally distributes the remaining worth of the grand coalition among its players.

The optimal complaint values

In this section, we define two optimal complaint values, each based on a new per capita complaint criterion described in the next two subsections. Similar to the nucleolus (Schmeidler, 1969 [12]), these values are obtained by lexicographically minimizing a maximal complaint vector associated with each of the two per capita complaint criteria. To this end, we introduce the lexicographical ordering ≤ L of R 2 n -1 . For all x, y ∈ R 2 n -1 , we say that x is lexicographically less than or equal to y, denoted by x ≤ L y, if x = y or if there exists t ∈ {1, 2, . . . , 2 n -1} such that x l = y l for all l ∈ {1, 2, . . . , t -1} and x t < y t . Moreover, for a payoff vector x ∈ R n , we denote by θ(x) ∈ R 2 n -1 the associated complaint vector whose components are the complaints of the coalitions with respect to x arranged in nonincreasing order, i.e. θ j (x) ≤ θ i (x) for all i, j ∈ {1, . . . , 2 n -1} such that i ≤ j. For example, the nucleolus consists in lexicographically minimizing the maximal complaint vector θ(x) where the complaints of the coalitions are computed by means of the excess criterion defined above.

The upper optimal complaint value

For a TU-game v ∈ Γ N , players' marginal contributions to the grand coalition constitute an upper bound of the core since for each x ∈ C(v), x i ≤ b v i for all i ∈ N . From the upper bound b v , the upper per capita complaint of a coalition is defined as:

∀S ⊆ N , S = ∅, e(S, x, b v ) = b v (S) -x(S) |S| , (3.1)
where b v (S) = i∈S b v i . Thereby, the coalition members hope to obtain at least their marginal contributions to the grand coalition and express a positive amount of per capita complaint if their payoffs are below these expectations. The upper optimal complaint value corresponds to the unique pre-imputation x U OC ∈ I * (v) and whose complaint vector θ(x U OC ) derived from (3.1) possesses the smallest lexicographic order ≤ L , i.e.

∀y ∈ I * (v), θ(x U OC ) ≤ L θ(y). Lemma 3.1. Given a TU-game v ∈ Γ N and a payoff vector x ∈ R n , let T 1 = {k ∈ N | ∀l ∈ N, b v k -x k ≥ b v l -x l }. If p ∈ T 1
, then the largest per capita complaint with respect to x derived from (3.1) is given by θ

1 (x) = b v p -x p .
Proof. Consider any player p ∈ T 1 . By the definition of T 1 , for any coalition S ⊆ N :

b v p -x p ≥ k∈S (b v k -x k ) |S| , = b v (S) -x(S) |S| .
Thus, we conclude from (3.1) that

θ 1 (x) = b v p -x p . 2 Proposition 3.2. Given a TU-game v ∈ Γ N 0 , the upper optimal complaint value x U OC ∈ I * (v) is bounded above by b v , i.e. x U OC i ≤ b v i for all i ∈ N .
Proof. Assume, for the sake of contradiction, that x U OC i ≤ b v i does not hold for all i ∈ N . We distinguish two cases: Case 1: Suppose that x U OC i ≥ b v i for all i ∈ N and there exists at least one player j ∈ N such that x U OC j > b j . Then, it holds that:

x U OC (N ) > b v (N ) ≥ v(N ), (3.2)
where the last inequality holds because v ∈ Γ N 0 . Therefore, x U OC (N ) > v(N ) is a contradiction for x U OC ∈ I * (v). Case 2: Suppose that there exist at least two players s, t

∈ N such that x U OC s < b v s and x U OC t > b v t . Let T 1 = {k ∈ N | ∀l ∈ N, b v k -x U OC k ≥ b v l -x U OC l } and T 2 = {k ∈ N \ T 1 | ∀l ∈ N \ T 1 , b v k -x U OC k ≥ b v l -x U OC l }.
Here, T 1 and T 2 are manifestly nonempty sets such that T 1 ∩ T 2 = ∅. We take any p ∈ T 1 and any q ∈ T 2 and define

= min{b v p -x U OC p , x U OC t -b v t } > 0.
The new payoff vector x * ∈ R n as follows:

x * k =    x U OC k if k = t and k ∈ T 1 ; x U OC k + |T 1 | if k ∈ T 1 ; x U OC k - if k = t. (3.3)
Next, we distinguish two subcases: Subcase 1: Assume that q = t. It follows from (3.3) that:

b v t -x * t = b v t -x U OC t + , = b v t -x U OC t + min{b v p -x U OC p , x U OC t -b v t }, = min{b v t -x U OC t + b v p -x U OC p , 0}, ≤ 0, (3.4)
and

b v p -x * p = b v p -x U OC p - |T 1 | , = b v p -x U OC p - min{b v p -x U OC p , x U OC t -b v t } |T 1 | , ≥ 0. (3.5)
We deduce from (3.4) and (3.5) that:

b v p -x * p ≥ b v t -x * t . (3.6)
Moreover, for all s ∈ N \ (T 1 ∪ T 2 ∪ {t}), it follows from (3.3) that:

b v q -x * q = b v q -x U OC q , > b v s -x U OC s , = b v s -x * s , (3.7)
where the inequality holds because q ∈ T 2 and s ∈ T 1 ∪ T 2 . Therefore, by Lemma 3.1, (3.6), and (3.7):

θ 1 (x * ) = max{b v k -x * k , k ∈ N }, = max{b v p -x * p , b v q -x * q , b v t -x * t , b v s -x * s , s ∈ N \ (T 1 ∪ T 2 ∪ {t})}, = max{b v p -x * p , b v q -x * q }, = max{b v p -x U OC p - |T 1 | , b v q -x U OC q }, < b v p -x U OC p , = θ 1 (x U OC ).
Hence, we conclude that θ(x U OC ) > L θ(x * ), which is a contradiction. Subcase 2: Assume that q = t. It follows from (3.3) that:

b v q -x * q = b v q -x U OC q + , = b v q -x U OC q + min{b v p -x U OC p , x U OC q -b v q }, = min{b v q -x U OC q + b v p -x U OC p , 0}, ≤ 0. (3.8)
We deduce from (3.5) and (3.8) that:

b v p -x * p ≥ b v q -x * q . (3.9)
Therefore, by Lemma 3.1 and (3.9):

θ 1 (x * ) = max{b v k -x * k , k ∈ N }, = max{b v p -x * p , b v q -x * q , b v s -x * s , s ∈ N \ (T 1 ∪ T 2 )}, = max{b v p -x * p , b v s -x * s , s ∈ N \ (T 1 ∪ T 2 )}, = max{b v p -x U OC p - |T 1 | , b v s -x U OC s , s ∈ N \ (T 1 ∪ T 2 )}, < b v p -x U OC p , = θ 1 (x U OC ).
Hence, we conclude that θ(x U OC ) > L θ(x * ), which is a contradiction. 2

The important second inequality in (3.2) should draw our attention to the set of TUgames where the worth v(N ) cannot cover the sum of the marginal contributions, i.e. v(N ) ≤ b v (N ). We denote this set of TU-games by Γ N 1 , for which the conclusion in Proposition 3.2 still holds. Theorem 3.3. Given a TU-game v ∈ Γ N 1 , the upper optimal complaint value x U OC ∈ I * (v) is bounded above by b v .

The proof is omitted since it is similar to that of Proposition 3.2. By Theorem 3.3, we can narrow the scope of the upper optimal complaint value from the pre-imputation set

I * (v) to the set K = {x ∈ I * (v) | ∀i ∈ N, x i ≤ b v i }.
The following lemma compares the upper per capita complaints within a coalition for two given payoff vectors.

v l -x l > b v m -x m ≥ 0, let = b v l -x l -(b v m -xm) 2
> 0 and the new payoff vector x * ∈ K be defined as follows:

x * k =    x k if k ∈ {l, m}; x l + if k = l; x m - if k = m.
(3.10)

Then, the following five statements hold: (ii) For any S ⊆ N such that l, m ∈ S:

e(S, x * , b v ) = b v (S) -x * (S) |S| , = b v (S\{l, m}) -x * (S\{l, m}) + (b v l -x * l ) + (b v m -x * m ) |S| , = b v (S\{l, m}) -x(S\{l, m}) + (b v l -(x l + )) + (b v m -(x m -)) |S| , = b v (S) -x(S) |S| , = e(S, x, b v ).
(iii) For any S ⊆ N such that l ∈ S and m ∈ S, it holds that:

e(S, x * , b v ) = b v (S) -x * (S) |S| , = b v (S\{l}) -x * (S\{l}) + (b v l -x * l ) |S| , = b v (S\{l}) -x(S\{l}) + (b v l -(x l + )) |S| , = b v (S) -x(S) - |S| , = e(S, x, b v ) - |S| , < e(S, x, b v ),
where the last inequality holds because > 0.

(iv) For any S ⊆ N such that l ∈ S and m ∈ S: (v) Statement (v) follows directly from (i), (ii), (iii), and (iv). 2

e(S, x, b v ) = b v (S) -x(S) |S| , = b v (S\{m}) -x(S\{m}) + (b v m -x m ) |S| , < b v (S\{m}) -x(S\{m}) + (b v l -x l ) |S| , = b v (S ∪ {l}\{m}) -x(S ∪ {l}\{m}) |S| , = e(S ∪ {l}\{m}, x, b v ). ( 3
v l -x * l = b v m -x * m that: e(S, x * , b v ) = b v (S) -x * (S) |S| , = b v (S\{m}) -x * (S\{m}) + (b v m -x * m ) |S| , = b v (S\{m}) -x * (S\{m}) + (b v l -x * l ) |S| , = b v (S ∪ {l}\{m}) -x * (S ∪ {l}\{m}) |S| , = e(S ∪ {l}\{m}, x * , b v ). ( 3
We now show that the upper optimal value coincides with the Equal Allocation of Non-Separable Contributions on Γ N 1 .

Theorem 3.5. Given a TU-game v ∈ Γ N 1 and the upper optimal complaint value x U OC ∈ I * (v), it holds that:

(i) b v i -x U OC i is a constant for all i ∈ N ; (ii) x U OC = EANSC(v).
Proof. (i) Assume, for the sake of contradiction, that b

v i -x U OC i is not a constant for all i ∈ N , i.e. there exist l, m ∈ N such that b v l -x U OC l = b v m -x U OC m . Without loss of generality, we suppose that b v l -x U OC l > b v m -x U OC m
. By Theorem 3.3 and statement (v) of Lemma 3.4, there exists a payoff vector x * ∈ K such that θ(x U OC ) > L θ(x * ), a contradiction. (ii) It follows from point (i) and

x U OC ∈ I * (v) that x U OC i = EANSC i (v) for all i ∈ N . 2

The lower optimal complaint value

For a TU-game v ∈ Γ N , players' individual worths correspond to a lower bound of the core since for each x ∈ C(v), v({i}) ≤ x i for all i ∈ N . From the lower bound (v({i})) i∈N , the lower per capita complaint of a coalition (including the empty set) is defined as:

∀S N , e(S, x, (v({i})) i∈N ) = x(N \S) - j∈N \S v({j}) |N \S| . (3.13)
Thus, the coalition members hope that other players get nothing more than their individual worths and express a positive amount of complaint if their payoffs are above these expectations.

The lower optimal complaint value corresponds to the unique pre-imputation x LOC ∈ I * (v) and whose complaint vector θ(x LOC ) derived from (3.13) possesses the smallest lexicographic order ≤ L , i.e.

∀y ∈ I * (v), θ(x LOC ) ≤ L θ(y).

Lemma 3.6. Given a TU-game v ∈ Γ N and a payoff vector

x ∈ R n , let Q 1 = {k ∈ N | ∀l ∈ N, x k -v({k}) ≥ x l -v({l})}. If p ∈ Q 1 ,
then the largest per capita complaint with respect to x derived from (3.13) is given by θ 1 (x) = x p -v({p}).

Proof. Consider any player p ∈ Q 1 . By the definition of Q 1 , for any coalition S ⊆ N :

x p -v({p}) ≥ k∈S (x k -v({k})) |S| , = x(S) -k∈S v({k}) |S| ,
or equivalently, for any S N ,

x p -v({p}) ≥ x(N \ S) -k∈N \S v({k}) |N \ S| .
Thus, we conclude from (3.13) that θ 1 (x) = x p -v({p}). 2

Proposition 3.7. Given a TU-game v ∈ Γ N 0 , the lower optimal complaint value x LOC ∈ I * (v) is bounded below by (v({i})) i∈N , i.e. x LOC i ≥ v({i}) for all i ∈ N .

Proof. Assume, for the sake of contradiction, that x LOC i ≥ v({i}) does not hold for all i ∈ N . We distinguish two cases: Case 1: Suppose that x LOC i ≤ v({i}) for all i ∈ N and there exists at least one player j ∈ N such that x LOC j < v({j}). Then, it holds that:

x LOC (N ) < i∈N v({i}) ≤ v(N ), (3.14)
where the last inequality holds because v ∈ Γ N 0 . Therefore, x LOC (N ) < v(N ), which is a contradiction since x LOC ∈ I * (v). Case 2: Suppose that there are at least two players s, t ∈ N such that x LOC s < v({s}) and

x LOC t > v({t}). Let Q 1 = {k ∈ N | ∀l ∈ N, x LOC k -v({k}) ≥ x LOC l -v({l})} and Q 2 = {k ∈ N \ Q 1 | ∀l ∈ N \ Q 1 , x LOC k -v({k}) ≥ x LOC l -v({l})}. It is manifest that Q 1 and Q 2 are non-empty sets such that Q 1 ∩ Q 2 = ∅. We consider any p ∈ Q 1 and any q ∈ Q 2 and denote = min{x LOC p -v({p}), v({s}) -x LOC s } > 0.
The new payoff vector x * ∈ R n is constructed as follows:

x * k =    x LOC k if k = s and k ∈ Q 1 ; x LOC k -|Q 1 | if k ∈ Q 1 ; x LOC s + if k = s. (3.15)
Next, we distinguish two subcases: Subcase 1: Assume that q = s. It follows from (3.15) that:

x * s -v({s}) = x LOC s + -v({s}), = x LOC s -v({s}) + min{x LOC p -v({p}), v({s}) -x LOC s }, = min{x LOC s -v({s}) + x LOC p -v({p}), 0}, ≤ 0, (3.16)
and

x * p -v({p}) = x LOC p -v({p}) - |Q 1 | , = x LOC p -v({p}) - min{x LOC p -v({p}), v({s}) -x LOC s } |Q 1 | , ≥ 0. (3.17)
We deduce from (3.16) and (3.17) that:

x * p -v({p}) ≥ x * s -v({s}). (3.18)
Therefore, by Lemma 3.6,(3.15), and (3.18):

θ 1 (x * ) = max{x * k -v({k}), k ∈ N }, = max{x * p -v({p}), x * q -v({q})}, = max{x LOC p -v({p}) - |Q 1 | , x LOC q -v({q})}, < x LOC p -v({p}), = θ 1 (x LOC ).
Hence, we conclude that θ(x LOC ) > L θ(x * ), a contradiction. Subcase 2: Assume that q = s. It follows from (3.15) that:

x * q -v({q}) = x LOC q + -v({q}), = x LOC q -v({q}) + min{x LOC p -v({p}), v({q}) -x LOC q }, = min{x LOC q -v({q}) + x LOC p -v({p}), 0}, ≤ 0. ( 3.19)
We deduce from (3.17) and (3.19) that:

x * p -v({p}) ≥ x * q -v({q}). (3.20)
Therefore, by Lemma 3.6, (3.15) and (3.20), it holds that:

θ 1 (x * ) = max{x * k -v({k}), k ∈ N }, = max{x * p -v({p}), x * j -v({j}), j ∈ N \ (Q 1 ∪ {q})}, = max{x LOC p -v({p}) - |Q 1 | , x LOC j -v({j}), j ∈ N \ (Q 1 ∪ {q})}, < x LOC p -v({p}), = θ 1 (x LOC ).
Hence, we conclude that θ(x LOC ) > L θ(x * ), a contradiction. 2

The important second inequality in (3.14) informs us about the set of TU-games where the worth v(N ) can cover the sum of the individual worths, i.e. v(N ) ≥ k∈N v({k}). We denote this set of TU-games by Γ N 2 , for which the conclusion of Proposition 3.7 still holds.

Theorem 3.8. Given a TU-game v ∈ Γ N 2 , the lower optimal complaint value x LOC ∈ I * (v) is bounded below by (v({i})) i∈N .

The proof is omitted since it is similar to that of Proposition 3.7. By Theorem 3.8, the scope of the lower optimal complaint value can be restricted to the set K = {x ∈ I * (v) | ∀i ∈ N, v({i}) ≤ x i }. To prove that the lower complaint value coincides with the CIS value, we first need the following lemma. Lemma 3.9. Given a TU-game v ∈ Γ N 2 , a payoff vector x ∈ K , and two players l, m

∈ N such that x m -v({m}) > x l -v({l}) ≥ 0, let = xm-v({m})-(x l -v({l}))
2 > 0 and the new payoff vector x * ∈ K be defined as follows:

x * k =    x k if k ∈ {l, m}; x l + if k = l; x m - if k = m.
Then, θ(x) > L θ(x * ).

Theorem 3.10. Given a TU-game v ∈ Γ N 2 and the lower optimal complaint value x LOC ∈ I * (v), it holds that:

(i) x LOC i -v({i}) is a constant for all i ∈ N ; (ii) x LOC = CIS(v).
The proofs of Lemma 3.9 and Theorem 3.10 are omitted since they are similar to those of Lemma 3.4 and Theorem 3.5, respectively. This correspondence is due in part to the duality of the EANSC and CIS values (Oishi et al., 2016 [14]).

4 Axiomatic characterizations of the optimal complaint values

Characterization of the upper optimal complaint value

In this subsection we invoke two axioms. The first axiom of efficiency is classical, viz.

EFF. A value ϕ satisfies efficiency if for all v ∈ Γ N , i∈N ϕ i (v) = v(N ).
To introduce the next axiom we require an additional notion of complaint inspired by the idea of the (pre-) kernel (Maschler and Peleg, 1966 [8], Maschler et al., 1972 [9]). For a TU-game v ∈ Γ N 1 , the maximal upper per capita complaint of a player i ∈ N against another player j ∈ N with respect to x ∈ R n , denoted by h v ij (x, b v ), is defined as the maximal upper per capita complaint among coalitions containing i but not j, i.e. The maximal upper per capita complaint represents the maximal amount of complaint player i may express by withdrawing from x without the cooperation of player j. Thus, the maximal upper per capita complaint can be regarded as a measure of player i's negotiation power facing player j.

EUMC. A value ϕ satisfies the equal upper maximal per capita complaint property if for all v ∈ Γ N and for all i, j ∈ N ,

h v ij (ϕ(v), b v ) = h v ji (ϕ(v), b v ).
The equal upper maximal per capita complaint property requires that any pair of players have the same maximal upper per capita complaint, i.e. their negotiation powers balance each other out.

Proposition 4.1. Given a TU-game v ∈ Γ N 1 , the upper optimal complaint value x U OC ∈ I * (v) satisfies EFF and EUMC.

Proof. It is immediate that x U OC satisfies EFF. To prove that x U OC satisfies EUMC, note that by Theorem 3.5, the upper optimal complaint value coincides with the EANSC value. Hence: Proof. Assume, for the sake of contradiction, that b v i -ϕ i (v) is not a constant for all i ∈ N , i.e. there exist two players i, j ∈ N such that b v i -ϕ i (v) = b v j -ϕ j (v). Without loss of generality, assume that b v i -ϕ i (v) > b v j -ϕ j (v). It follows from (4.1) that:

h v ij (x U
h v ij (ϕ(v), b v ) = max b v (T ) -k∈T ϕ k (v) + b v i -ϕ i (v) |T | + 1 | T ⊆ N \{i, j} , and
h v ji (ϕ(v), b v ) = max b v (T ) -k∈T ϕ k (v) + b v j -ϕ j (v) |T | + 1 | T ⊆ N \{i, j} .
by [START_REF] Driessen | Coincidence of and collinearity between game theoretic solutions[END_REF] [START_REF] Driessen | Coincidence of and collinearity between game theoretic solutions[END_REF]. However, the relationships between these equalitarian values and other solution concepts are not obvious. By lexicographically minimizing the maximal complaint vector associated with other criteria, we can obtain a variety of values for TU-games, but their links with the core and kernel remain to be determined. This work is left for future research.

Lemma 3 . 4 .

 34 Given a TU-game v ∈ Γ N 1 , a payoff vector x ∈ K, and two players l, m ∈ N such that b

  (i) e(S, x * , b v ) = e(S, x, b v ) for any S ⊆ N such that l, m ∈ S; (ii) e(S, x * , b v ) = e(S, x, b v ) for any S ⊆ N such that l, m ∈ S; (iii) e(S, x * , b v ) < e(S, x, b v ) for any S ⊆ N such that l ∈ S and m ∈ S; (iv) For any S ⊆ N such that l ∈ S and m ∈ S, it is redundant to consider the relation between e(S, x, b v ) and e(S, x * , b v ) when comparing θ(x) and θ(x * ) in the lexicographic order; (v) θ(x) > L θ(x * ). Proof. (i) By the definition of x * ∈ K, it is immediate that for any coalition S ⊆ N with l, m ∈ S, we have e(S, x, b v ) = e(S, x * , b v ).

. 11 )

 11 Therefore, for any S ⊆ N such that l ∈ S and m ∈ S, there always exists a coalition S∪{l}\{m} for which e(S∪{l}\{m}, x, b v ) > e(S, x, b v ). Moreover, it follows from b

. 12 )

 12 Thus, by(3.11),(3.12), and the inequality e(S ∪ {l}\{m}, x * , b v ) < e(S ∪ {l}\{m}, x, b v ) which holds by (iii), it is redundant to consider the relation between e(S, x, b v ) and e(S, x * , b v ) when comparing θ(x) and θ(x * ) in the lexicographic order.

  h v ij (x, b v ) = max{e(S, x, b v ) | S ⊆ N , i ∈ S and j ∈ S}.(4.1)

2 Lemma 4 . 2 .

 242 OC , b v ) = max b v (S) -x U OC (S) |S| | S ⊆ N , i ∈ S, j ∈ S , = max b v (S) -k∈S EANSC k (v) |S| | S ⊆ N , i ∈ S, j ∈ S , = b v (N ) -v(N ) n .By a similar argument, we obtainh v ji (x U OC , b v ) = b v (N )-v(N )n , which concludes the proof.Given a TU-game v ∈ Γ N 1 , if a value ϕ satisfies EUMC, then b v i -ϕ i (v) is a constant for all i ∈ N .

We refer toBéal et al. (2016) [START_REF] Béal | Characterizations of three linear values for TU games by associated consistency: simple proofs using the Jordan normal form[END_REF] for unified proofs of these results.

The first author acknowledges financial support by National Science Foundation of China (NSFC) through grant No.71601156, 71571140, 71571143.

† Aymeric Lardon, Université Côte d'Azur, CNRS, GREDEG, France. This work has been supported through the UCA JEDI Investments in the Future project managed by the French National Research Agency (ANR) under grant ANR-15-IDEX-01.

‡ Panfei Sun,

Since b

), which is a contradiction since ϕ satisfies EUMC.

2

We now show that the upper optimal complaint value or, equivalently, the EANSC value, is characterized by efficiency and the equal upper maximal per capita complaint property.

Theorem 4.3. The upper optimal complaint value x

n for all i ∈ N , which concludes the proof. 2

Characterization of the lower optimal complaint value

In this subsection, we invoke another axiom of maximal per capita complaint. For a TUgame v ∈ Γ N 2 , the maximal lower per capita complaint of a player i ∈ N against another player j ∈ N with respect to x ∈ R n , denoted by h v ij (x, (v({i})) i∈N ), is defined as the maximal lower per capita complaint among coalitions containing i but not j, i.e.

The maximal lower per capita complaint has a similar interpretation as the maximal upper per capita complaint, viz.

ELMC.

A value ϕ satisfies the equal lower maximal per capita complaint property if for all v ∈ Γ N and all i, j ∈ N ,

The equal lower maximal per capita complaint property requires that any pair of players have equal maximal lower per capita complaints.

Proposition 4.4. Given a TU-game v ∈ Γ N 2 , the lower optimal complaint value x LOC ∈ I * (v) satisfies EFF and ELMC.

Proof. It is manifest that x LOC satisfies EFF. To prove that x LOC satisfies ELMC, note that, by Theorem 3.10, the lower optimal complaint value coincides with the CIS value. Hence:

By a similar argument, we obtain

, which concludes the proof. 2

Lemma 4.5. Given a TU-game v ∈ Γ N 2 , if a value ϕ satisfies ELMC, then ϕ i (v) -v({i}) is a constant for all i ∈ N .

Proof. Assume, for the sake of contradiction, that ϕ i (v) -v({i}) is not a constant for all i ∈ N , i.e. there exist two players i, j ∈ N such that

Without loss of generality, assume that ϕ i (v) -v({i}) > ϕ j (v) -v({j}). It follows from (4.2) that:

We now see that the lower optimal complaint value or, equivalently, the CIS value, is characterized by efficiency and the equal lower maximal per capita complaint property on Γ N 2 .

Theorem 4.6. The lower optimal complaint value x LOC ∈ I * (v) or, equivalently, the CIS value, is the unique value satisfying EFF and ELMC on Γ N 2 .

Proof. By Proposition 4.4, it remains to show that if a value ϕ satisfies EFF and ELMC on Γ N 2 , then it coincides with the CIS value. It follows from Lemma 4.5 that ϕ

for all i ∈ N , which concludes the proof. 2

Concluding Remarks

In this article, we have introduced two optimal complaint values. For large classes of TUgames, we have proven that the upper optimal complaint value coincides with the EANSC value, while the lower optimal complaint value coincides with the CIS value. Moreover, we have characterized these values by means of efficiency and equal maximal per capita complaint properties. The upper optimal complaint value may also coincide with the nucleolus since the coincidence between the EANSC value and the nucleolus was revealed


Lisheng Sun-Hosoya

Isabelle Guyon

Michèle Sebag

ActivMetaL: Algorithm Recommendation with Active Meta Learning

Keywords: Model Selection, Recommender, Active Meta Learning

come

Introduction

While Machine Learning and Artificial Intelligence are taking momentum in many application areas ranging from computer vision to chat bots, selecting the best algorithm applicable to a novel task still requires human intelligence. The field of AutoML (Automatic Machine Learning), aiming at automatically selecting best suited algorithms and hyper-parameters for a given task, is currently drawing a lot of attention. Progress in AutoML has been stimulated by the organization of challenges such as the AutoML challenge series1 . Among the winning AutoML approaches are AutoWeka and Auto-SkLearn, developed by the Freiburg team [START_REF] Feurer | Methods for improving bayesian optimization for automl[END_REF][START_REF] Feurer | Efficient and robust automated machine learning[END_REF][START_REF] Feurer | Initializing bayesian hyperparameter optimization via meta-learning[END_REF] (more in Section 2). These approaches, taking inspiration from Bayesian optimization [START_REF] Eggensperger | Towards an empirical foundation for assessing bayesian optimization of hyperparameters[END_REF], alternatively learn an inexpensive estimate of model performance on the current dataset, and use this estimate to reduce the number of model candidates to be trained and tested using the usual expensive cross-validation procedure. A novel ingredient of AutoSkLearn, referred to as "meta-learning", takes in charge the initialization of the Bayesian optimization process, with a predictor using "meta-features" describing the datasets. Metalearning reportedly yields significant improvements over random initializations.

Another approach targeting AutoML is based on recommender systems (RS), popularized by the Netflix challenge [START_REF] Bennett | Netflix: The Netflix prize[END_REF]. RS approaches seek the item best suited to a given user, based on historical user-item interactions and user preferences. By analogy [START_REF] Stern | Collaborative expert portfolio management[END_REF] proposed first to treat algorithm selection as a recommender problem in which datasets "prefer" algorithms solving their task with better performance. Along this line, the "Algorithm Recommender System" Alors [START_REF] Mısır | Alors: An algorithm recommender system[END_REF], combines a recommender system and an estimate of model performance based on predefined meta-features, to achieve AutoML (more in Section 2).

In this paper, we propose an active meta-learning approach inspired by Au-toSklearn and Alors. Formally (Section 3), given a matrix of historical algorithm performance on datasets, we aim at finding as fast as possible the model with best performance on a new dataset. The originality compared to the former approaches lies in the coupled search for the meta-features describing the dataset, the model performance based on these meta-features, and the selection of a candidate model to be trained and tested on the dataset.

This paper is organized as follows: After briefly reviewing the SOTA in Section 2, we formalize our problem setting in Section 3. We then describe the benchmark data in Section 4 and provide an empirical validation of the approach in Section 5. While the validation considers only the "classical" machine learning settings, it must be emphasized that the proposed approach does not preclude of any type of tasks or algorithms, hence is applicable to a broader range of problems.

State of the art

It is notorious that the success of model search techniques can be dramatically improved by a careful initialization. In AutoSkLearn, the search is improved by a sophisticated initialization using a form of transfer learning [START_REF] Pan | A survey on transfer learning[END_REF] called "meta-learning". The meta-data samples include all the datasets of openml.org [START_REF] Van Rijn | OpenML: A collaborative science platform[END_REF] (a platform which allows to systematically run algorithms on datasets). Systematically launching AutoSkLearn on each dataset yields the best (or near best) models associated with each dataset.

Independently, each dataset is described using so-called meta-features. Metafeatures are generally of two kinds: i) simple statistics of the dataset such as number of training examples, number of features, fraction of missing values, presence of categorical variables, etc.; ii) performance on the current dataset of "landmark algorithms", namely a well-chosen set of algorithms that can be trained and tested with moderate computational effort such as one nearest neighbor (1NN) or decision trees.

When considering a new dataset, AutoSkLearn first determines its nearest neighbors in the meta-feature space, and initializes the search using the best models associated with these neighbors. Other meta-learning formalisms, not considered further in this paper, are based on learning an estimate of the model performance from meta-features [START_REF] Rice | The algorithm selection problem[END_REF], or learning to predict the best performing algorithm, as a multi-class classification problem [START_REF] Sun-Hosoya | Lessons learned from the automl challenge[END_REF].

The delicate issue is to control the cost of the initialization step: considering many landmark algorithms comes with an expected benefit (a better initialization of the search), and with a cost (the computational cost of running the landmarks).

As said, recommender systems (RS) aim at selecting the item best suited to a particular user, given a community of users, a set of items and some historical data of past interactions of the users with the items, referred to as "collaborative matrix" [START_REF] Su | A survey of collaborative filtering techniques[END_REF][START_REF] Bobadilla | Recommender systems survey[END_REF], denoted S (for "score") in this paper. As first noted by [START_REF] Stern | Collaborative expert portfolio management[END_REF], algorithm selection can be formalized as a recommender problem, by considering that a dataset "likes better" the algorithms with best performances on this dataset. Along this line, one proceeds by i) estimating all algorithm performances on this dataset (without actually evaluating them by training and testing); and ii) recommending the algorithm(s) with best estimated performance on this dataset.

The merits of RS approaches regarding algorithm selection are twofold. Firstly, RS approaches are frugal (like other methods, e.g. co-clustering). RS proceeds by estimating the value associated with each (user, item) pair -here, the performance associated with each (algorithm, dataset) -from a tiny fraction of the (user, item) ratings, under the assumption that the collaborative matrix is of low rank k. More precisely the (usually sparse) matrix S of dimensions (p, N ) is approximated by U V , with U a (p, k) matrix and V a (N, k) matrix, such that U i,• , V j,• is close to S i,j for all pairs i, j (e.g. using maximum margin matrix factorization in [START_REF] Srebro | Maximum-margin matrix factorization[END_REF]). U (respectively V ) is referred to as latent representation of the users (resp. the items). In the model selection context, RS approaches are thus frugal: they can operate even when the performance of a model on a dataset is known on a tiny fraction of the (model, dataset) pairs. Secondly, most-recent RS approaches are ranking methods. Estimating algorithm performance is a harder problem than ranking them in order of merit. A second benefit of RS is that they can rank items conditionally to a given user. The CofiRank algorithm [START_REF] Weimer | CofiRank-maximum margin matrix factorization for collaborative ranking[END_REF] accordingly considers the rank matrix (replacing S i,j with the rank of item j among all items user i has rated) and minimizes the Normalized Discounted Cumulative Gain (NDCG) in which correctness in higher ranked items is more important. As optimizing NDCG is non-convex, CofiRank thus instead optimizes a convex upper-bound of NDCG.

In counterpart for these merits, mainstream RS is not directly applicable to AutoML, as it focuses on recommending items to known users (warm-start recommendation). Quite the contrary, AutoML is concerned with recommending items (models) to new users (new datasets), a problem referred to as cold-start recommendation [START_REF] Schein | Methods and metrics for cold-start recommendations[END_REF][START_REF] Gunawardana | Tied boltzmann machines for cold start recommendations[END_REF]. This drawback is addressed in the general purpose Alors system [START_REF] Mısır | Alors: An algorithm recommender system[END_REF], where external meta-features are used to estimate the latent representation Û• of the current dataset; this estimated latent representation is used together with the latent representation of any model to estimate the model performance (as Û• , V j ) and select the model with best estimated performance. The novel active meta-learning approach presented in this paper proposes a different approach to warm start, not requiring external meta-features: Previously evaluated algorithm scores are themselves used as meta-features (see Section 3).

Problem setting and algorithms

We define the active meta-learning problem in a collaborative filtering recommender setting as follows: GIVEN:

-An ensemble of datasets (or tasks) D of elements d (not necessarily finite); -A finite ensemble of n algorithms (or machine learning models) A of elements d,a) calculating the performance (score) of algorithm a on dataset d (e.g. by cross-validation). Without loss of generality we will assume that the larger S(d, a), the better. The evaluation of S(d, a) can be computationally expensive, hence we want to limit the number of times S is invoked. -A training matrix S, consisting of p lines (corresponding to example datasets

a j , j = 1, • • • , N ; -A scoring program S(
d i , i = 1, • • • p drawn from D)
and n columns (corresponding to all algorithms in A), whose elements are calculated as S ij = S(d i , a j ), but may contain missing values (denoted as NaN).

-A new test dataset d t ∈ D, NOT part of training matrix S. This setting can easily be generalized to test matrices with more than one line. GOAL: Find "as quickly as possible" j * = argmax j (S(d t , a j )).

For the purpose of this paper "as quickly as possible" shall mean by evaluating as few values of S(d t , a j ), j = 1, • • • , n as possible. More generally, it could mean minimizing the total computational time, if there is a variance in execution time of S(d t , a j ) depending on datasets and algorithms. However, because we rely in our experimental section on archival data without information of execution time, we reserve this refinement for future studies. Additionally, we assume that the computational cost of our meta-learning algorithm (excluding the evaluations of S) is negligible compared to the evaluations of S, which has been verified in practice.

In our setting, we reach our goal iteratively, in an Active Meta Learning manner (ActivMetaL), see Algorithm 1. The variants that we compare differ in the choices of InitializationScheme(S) and SelectNext(S, t), as described in Algorithms 2-5: Given a new dataset (an empty line), we need to initialize it with one or more algorithm performances, this initialization is done by InitializationScheme(S) and is indispensable to fire CofiRank. Algorithms 2-5 show 2 initialization methods: randperm in Algorithm 2 (the first algorithm is selected at random) and median in Algorithms 3-5 (the algorithms are sorted by their median over all datasets in training matrix S and the one with highest median is selected as the first algorithm to evaluate). Once we have evaluated the first algorithm, the next algorithms can be chosen with or without active learning, this is done by SelectNext(S, t): Algorithm 2-3 without active meta learning select next algorithms at random or according to median over training datasets, i.e. the knowledge from evaluated algorithms on the new dataset is not taken into account; Algorithm 4-5 run CofiRank for active meta learning, which, initialized with performances of evaluated algorithm, returns a ranking of algorithms on the new dataset. The difference is that in Alg. [START_REF] Eggensperger | Towards an empirical foundation for assessing bayesian optimization of hyperparameters[END_REF]

Benchmark data

To benchmark our proposed method, we gathered datasets from various sources (Table 1). Each dataset consists of a matrix S of performances of algorithms (or models) on tasks (or datasets). Datasets are in lines and algorithms in columns. The performances were evaluated with a single training/test split or by cross-validation. The tasks were classification or regression tasks and the metrics quasi-homogeneous for each S matrix (e.g. Balanced Accuracy a.k.a. BAC for classification and R 2 for regression). We excluded data sources for which metrics were heterogeneous (a harder problem that we are leaving for further studies).

Although ActivMetaL lends itself to using sparse matrices S (with a large fraction of missing values), these benchmarks include only full matrices S. The artificial dataset was constructed from a matrix factorization to create a simple benchmark we understand well, allowing to easily vary the problem difficulty. Matrix S is simply obtained as a product of three matrices U ΣV , U and V being orthogonal matrices and Σ a diagonal matrix of "singular values", whose spectrum was chosen to be exponentially decreasing, with Σ ii = exp(-βi), β = 100 in our experiments. The other benchmarks were gathered from the Internet or the literature and represent the performances of real algorithms on real datasets. We brought back all metrics to scores that are "the larger the better". In one instance (StatLog), we took the square root of the performances to equalize the distribution of scores (avoid a very long distribution tail). For AutoML, many algorithms were aborted due to execution time constraints. We set the corresponding performance to 0. To facilitate score comparisons between benchmark datasets, all S matrices were globally standardized (i.e. we subtracted the global mean and divided by the global standard deviation). This scaling does not affect the results.

We conducted various exploratory data analyses on the benchmark data matrices, including two-way hierarchical clustering, to visualize whether there were enough similarities between lines and columns to perform meta-learning. See our supplemental material referenced at the end of this paper. In this section, we analyze the experimental results of Table 2 and Figure 1. The graphs represent meta-learning curves, that is the performance of the best algorithm found so far as a function of the number of algorithms tried. 2 The ground truth of algorithm performance is provided by the values of the benchmark matrices (see Section 4).

We remind the reader that in a meta-learning problem, each sample is a dataset. To evaluate meta-learning we use the equivalent of a leave-one-out estimator, i.e. leave-one-dataset-out. Hence, we use as meta-learning training data all datasets but one, then create the learning curve for the left-out dataset. Thus, given a benchmark data matrix, we generate meta-learning curves using as matrix S a sub-matrix with one line left out (held out), which serves as target vector t for the dataset tested. Subsequently, we average all meta-learning curves, step-by-step. Thus the result shown in Figure 1 are the averaged learning curves obtained with the leave-one-dataset-out scheme, i.e. averaged over all datasets, for a given benchmark dataset.

To evaluate the significance of the efficiency of our proposed method, we ran 1000 times the Random search algorithm, in which algorithms are ran in a random sequence. We drew the curves of median performance (blue curves) and showed as blue shadings various quantiles. The fact that the red curves, corresponding to the proposed algorithm Active Meta Learning w. CofiRank is generally above the blue curve comforts us that the method is actually effective. It is not always significantly better than the median of Random search. However, this is a very hard benchmark to beat. Indeed, the median of Random search is not a practical method, it is the average behavior of random search over many runs. Thus, performing at least as good as the median of Random search is actually pretty good.

We also compared our method with two other baselines. (1) The SimpleRank w. median (green curves) uses the median performance of algorithms on all but the left-out dataset. Thus it does not perform any active meta-learning. (2) The Median Landmark w. 1 CofiRank (pink curves) makes only one call of CofiRank to reduce computational expense, based on the performance of only 3 Landmark algorithms, here simply picked based on median ranking.

The first benchmark using artificial data (Figure 1(a)) a relative position of curves that we intuitively expected: SimpleRankw.median (in green) does not perform well and Active Meta Learning w. CofiRank (in red) is way up in the upper quantiles of the random distribution, close to the ideal curve that goes straight up at the first time step (selects right away the best algorithm). Median Landmark w. 1 CofiRank (in pink) quickly catches up with the red curve: this is promising and shows that few calls to CofiRank might be needed, should this become a computational bottleneck.

However, the analysis of the results on real data reveals a variety of regimes. The first benchmark using the datasets of the AutoML challenge (Figure 1(b)) gives results rather similar to artificial data in which Active Meta Learning w. CofiRank still dominates, though SimpleRank w. median performs surprisingly well. More surprisingly, Active Meta Learning w. CofiRank does not beat SimpleRank w. median on the StatLog benchmark and beats it with difficulty (after more than 10% of the algorithms have been trained/tested) on the OpenML benchmark. Also, the cheap algorithm calling CofiRank just once (Median Landmark w. 1 CofiRank, performing no active learning) which looked promising on other benchmark datasets, performs poorly on the OpenML dataset. This is unfortunate since this is the largest dataset, on which running active-learning is most computationally costly. We provide a discussion of computational considerations in Section 6.

Table 2 sums up the results in terms of area under the meta-learning curves (AUMLC). Active Meta Learning w. CofiRank consistently outperforms other methods, although not significantly according to the error bars.

Discussion and conclusion

We have presented an approach to algorithm recommendation (or model selection) based on meta-learning, capitalizing on previous runs of algorithms on a variety of datasets to rank candidate algorithms and rapidly find which one will perform best on a new dataset. The originality of the paper lies in its active learning approach based on a collaborative-filtering algorithm: CofiRank. Collaborative filtering is a technique to fill in missing data in a collaborative matrix of scores, which in our case represents performances of algorithms on datasets. Starting from the evaluation of a single algorithm on a new dataset of interest, the CofiRank method ranks all remaining algorithms by completing the missing scores in the collaborative matrix for that new dataset. The next most promising algorithm is then evaluated and the corresponding score added to the collaborative matrix. The process is iterated until all missing scores are filled in, by trying all algorithms, or until the allotted time is exhausted.

We demonstrated that Active Meta Learning w. CofiRank performs well on a variety of benchmark datasets. Active Meta Learning w. CofiRank does not always beat the naive SimpleRank w. median baseline method, but it consistently outperforms the "hard-to-beat" median of Random ranking, while SimpleRank w. median does not.

We also investigated whether the (meta-) active learning aspect is essential or can be replaced by running CofiRank a single time after filling in a few scores for Landmark algorithms. This technique (called Median Landmark w. 1 CofiRank) seemed promising on the smallest benchmark datasets, but gives significantly worse results that Active Meta Learning w. CofiRank on the largest benchmark dataset on which it would help most (computationally). One avenue of future research would be to put more effort in the selection of better Landmarks.

Further work also includes accounting for the computational expense of model search in a more refined way. In this work, we neglected the cost of performing meta-learning compared to training and testing the algorithms. This is justified by the fact that their run time is a function of the volume of training data, which is considerably smaller for the collaborative matrix (of dimension usually 100 datasets times 100 algorithms) compared to modern-times "big data" datasets (tens of thousands of samples times thousands of features). However, as we acquire larger meta learning datasets, this cost may become significant. Secondly, we assumed that all algorithms had a comparable computational time (to be able to use meta-learning datasets for which this information was not recorded). In the future, we would like to take into account the duration of each algorithm to better trade-off accuracy and computation. It is also worth noting that ActivMetaL does not optimize the exploration/exploitation trade-off. It is more geared toward exploitation than exploration since the next best algorithm is chosen at every step. Further work may include incorporating monitoring the exploration/exploitation trade-off. In particular, as said, so far we have not taken into account the computational cost of running algorithms. When we have a total time budget to respect, exploring first using faster algorithms then selecting slower (but better) algorithms may be a strategy that ActivMetal could adopt (thus privileging first exploration, then exploitation). At last, the experiments performed in this paper assumed that, except to the new dataset being tested, there were no other missing values in the collaborative matrix. One of the advantages of collaborative filtering techniques is that they can handle matrices sparsely populated. This deserves further investigation.

Supplemental material, data and code

For full reproducibility of our results, datasets and code are available on Github. To run it, CofiRank must be installed. We recommend using the Docker [1] image we built for this purpose. Please refer to the Github repository for all instructions. Our repository also includes a Jupyter-notebook with additional graphs referred to in the text.

Fig. 1 :

 1 Fig. 1: Meta-learning curves. We show results of 4 methods on 4 meta-learning datasets, using the leave-one-dataset-out estimator. The learning curves represent performance of the best model trained/tested do far, as a function of the number of models tried. The curves have been averaged over all datasets held-out. The method Active Meta Learning w. CofiRank (red curve) generally dominates other methods. It always performs at least as well as the median of random model selection (blue curve), a hard-to-beat benchmark. The more computationally economical Median Landmark w. 1 CofiRank consisting in training/testing only 3 models (Landmarks) to rank methods using only 1 call to CofiRank (pink curve) generally performs well, except on OpenML data for which it would be most interesting to use it, since this is the largest meta learning datasets. Thus active learning cannot easily be replaced by the use of Landmarks, lest more work is put into Landmark selection. The method SimpleRank w. median that ranks algorithm with their median performance (green curve) is surprisingly a strong contender to Active Meta Learning w. CofiRank for the StatLog and OpenML datasets, which are cases in which algorithms perform similarly on all datasets.

  we run CofiRank for each selection of next algorithm, i.e. CofiRank is initialized with more and more known values. In Alg. 5 CofiRank is run only once at the beginning, initialized with 3 landmark values.

	Algorithm 5 MedianLandmarks1CofiRank
	1: procedure InitializationScheme(S)
	2:	r ←median(S, 2)		Column-wise median
	3: Algorithm 1 ActivMetaL return j+ ← argmax(r) 4: procedure SelectNext(S,t) 1: procedure ActivMetaL(A, S, S, dt, nmax) 5: evaluated ←notNaN(t)
	2: 6:	n ← size(S, 2) if length(evaluated) < num landmarks then Number of algorithms to be evaluated on dt
	3: 7:	t ← NaNvector(n) r ←median(S, 2)	Algorithm scores on dt are initialized w. missing values Column-wise median
	4: 8:	j+ ←InitializationScheme(S) else if length(evaluated) == num landmarks then Initial algorithm aj+ ∈ A is selected
	5: 9:	while n < nmax do static r ← CofiRank(S,t)	Keep the CofiRank predictions thereafter
	6: 7: 10: 8: 11:	t[j+] ← S(dt, aj+) Complete t w. one more prediction score of aj+ on dt r(evaluated) ← -Inf j+ = SelectNext(S, t) n ←length(notNaN(t)) number of algorithms evaluated on dt return j+ ← argmax(r)
	9:	return j+
	Algorithm 2 Random
	1: procedure InitializationScheme(S)
	2:	r ←randperm(size(S, 2))	Replaced by something more clever elsewhere
	3:	return j+ ← argmax(r)
	4: procedure SelectNext(S,t)
	5:	evaluated ←notNaN(t)
	6:	r ←randperm(size(S, 2))	Replaced by something more clever elsewhere
	7:	r(evaluated) ← -Inf
	8:	return j+ ← argmax(r)
	Algorithm 3 SimpleRankMedian
	1: procedure InitializationScheme(S)
	2:	r ←median(S, 2)		Column-wise median
	3:	return j+ ← argmax(r)
	4: procedure SelectNext(S,t)
	5:	evaluated ←notNaN(t)
	6:	r ←median(S, 2)		Column-wise median
	7:	r(evaluated) ← -Inf
	8:	return j+ ← argmax(r)
	Algorithm 4 ActiveMetaLearningCofiRank
	1: procedure InitializationScheme(S)
	2:	r ←median(S, 2)		Column-wise median
	3:	return j+ ← argmax(r)
	4: procedure SelectNext(S,t)
	5:	evaluated ←notNaN(t)
	6:	r ← CofiRank(S,t)	Collaborative filtering on [S; t] returning last line
	7:	r(evaluated) ← -Inf
	8:	return j+ ← argmax(r)

Table 1 :

 1 Statistics of benchmark datasets used. #Datasets=number of datasets, #Algo=number of algorithms, Rank=rank of the performance matrix.

		Artificial	Statlog	OpenML	AutoML
	#Dataset	50	21	76	30
	#Algo	20	24	292	17
	Rank	20	21	76	17
	Metric	None	Error rate	Accuracy	BAC or R 2
	Preprocessing	None	Take square	None	Scores for
			root		aborted algo.
					set to 0
	Source	Generated by	Statlog Dataset	Alors [9]	AutoML1
		authors	in UCI database	website	(2015-2016)

Table 2 :

 2 Results of meta-learning methods for all 4 meta-datasets. Performances of meta-learning algorithms are measured as the area under the meta learning curve (AUMLC) normalized by the area of the best achievable curve. Active Meta Learning w. CofiRank (our proposed method) performs always best, although not significantly considering the 1-sigma error bars of the leave-one-dataset-out procedure.

	5 Results
		Artificial	Statlog	OpenML	AutoML
	Active Meta	0.91 (±0.03) 0.802 (±0.117) 0.96 (±0.04)	0.84 (±0.11)
	Learning w.
	CofiRank
	Random	0.81 (±0.05)	0.77 (±0.05)	0.95 (±0.03)	0.79 (±0.07)
	SimpleRank w.	0.7 (±0.2)	0.798 (±0.102)	0.95 (±0.04)	0.82 (±0.12)
	median
	Median	0.88 (±0.04)	0.795 (±0.099)	0.92 (±0.08)	0.83 (±0.11)
	LandMarks w.
	1-CofiRank

http://automl.chalearn.org

In the future, when we have meta-learning datasets for which the computational run time of algorithms is recorded, we shall tackle the harder and more interesting problem of meta-learning performance as a function of "total" computational time rather than number of algorithms tried.


Ramón Giraldo
email: rgiraldoh@unal.edu.co

Sophie Dabo-Niang

Sergio Martínez

Statistical modeling of spatial big data: An approach from a functional data analysis perspective

A literature review on spatial big data analysis is given. We show an application of Universal Kriging to a massive spatial dataset. We also present some perspectives of future work in this field.

Introduction

Modern technology has facilitated the collection of very large datasets. Nowadays, we generate about several trillion bytes of data every day, characterized by high dimensionality and large sample size and called Big Data or massive volumes of data. The term Big data is relatively new, but gathering and storing huge amounts of data is an old subject. The early years of the new millennium saw the concept of large dataset [START_REF] Laney | 3D Data management: controlling data volume, velocity, and variety[END_REF]. However, due to its complexity, no universal definition can be given to big data.

The last two decades have seen an extensive development of statistical tools capable of managing huge quantities of data consisting of a matrix of n data vectors, each containing p measurements, usually with large n and p [START_REF] Izenman | Modern Multivariate Statistical Techniques[END_REF]. Among others Functional Data Analysis (FDA) [START_REF] Ramsay | Functional Data Analysis[END_REF] has arisen as a field of statistics for modeling data in this context, particularly when p ≫ n.

FDA is concerned with the modeling of data, such as curves, shapes, images or a more complex mathematical object, thought as smooth realizations of a stochastic process (which is an infinite dimensional data object). In this sense functional data are part of Big Data [START_REF] Zipunnikov | Functional principal component model for high-dimensional brain imaging[END_REF][START_REF] Chen | Stringing high-dimensional data for functional analysis[END_REF][START_REF] Chen | Quantifying infinite-dimensional data: functional data analysis in action[END_REF]. It is common to find applications of FDA where the size of data is of order of terabytes, as encountered for example in fMRI (functional magnetic resonance imaging), brain imaging analysis [START_REF] Chen | Quantifying infinite-dimensional data: functional data analysis in action[END_REF] or bioinformatics [START_REF] Yoo | Big data analysis using modern statistical and machine learning methods in medicine[END_REF].

In a number of diverse disciplines such as environmental sciences, agronomy or mining, the data have an inherent spatial component. Spatial statistics [START_REF] Cressie | Statistics for Spatio-Temporal Data[END_REF] embodies a suite of methods for analyzing this type of information. This characteristic is also present in some spatial massive dataset (called spatial big data). An example is when long time series of meteorological variables are recorded at each point of a monitoring network or space-time usage of the mobilephone network in a given area [START_REF] Secchi | Analysis of spatio-temporal mobile phone data: a case study in the metropolitan area of Milan[END_REF].

In this contribution, we highlight the use of FDA to model spatial big data. We briefly review in Section 2 the notion of spatial big data and some FDA tools that can be used to model such data, particularly for doing spatial prediction. Section 3 is dedicated to an illustration on a big spatial dataset of daily temperature curves. The article ends with a brief discussion and suggestions for further research in Section 4.

1

A review on modeling spatial big data by using functional data analysis

Today statistical techniques for the analysis of large and complex data with a spatial underlying structure are required. For example, it is the case in neurological studies when curves of the electrical activity are recorded in voxels of the brain [START_REF] Lindquist | The statistical analysis of fMRI data[END_REF]. Generally, some multivariate techniques of dimension reduction are used to solve the problem of high dimensionality that arises in these cases [START_REF] Izenman | Modern Multivariate Statistical Techniques[END_REF]. FDA may be an alternative in this scenario. High dimensional data become functional data which are posteriorly analyzed by using FDA methods [START_REF] Giraldo | Ordinary kriging for function-valued spatial data[END_REF]. Basically, it is considered that the data observed for several dependent spatial units correspond to realizations of stochastic processes, usually assumed to be in a metric, semi-metric, Hilbert or Banach space.

In fact, in the setting of functional spatial data analysis, complex high dimensional data is typically a set of curves or surfaces, spatially distributed, regarded as points in a functional space (space of squared integrable functions, . . . ).

Here, we give a review about the common basis of these approaches making an emphasis in the spatial prediction of functional data.

The last decade saw a dynamic literature on parametric or non-parametric FDA approaches for high dimensional spatially dependent data and applications to various domains, such as principal component analysis [START_REF] Li | Functional principal component analysis of spatiotemporal point processes with applications in disease surveillance[END_REF][START_REF] Liu | Functional principal component analysis of spatially correlated data[END_REF], clustering [START_REF] Giraldo | Hierarchical clustering of spatially correlated functional data[END_REF][START_REF] Secchi | Bagging voronoi classifiers for clustering spatial functional data[END_REF][START_REF] Romano | On the performance of two clustering methods for spatial functional data[END_REF], regression and prediction of stationary or non-stationary processes with kriging or non-parametric methods [START_REF] Ignaccolo | Analysis of air quality monitoring networks by functional clustering[END_REF][START_REF] Dabo-Niang | Spatial mode estimation for functional random fields with application to bioturbation problem[END_REF][START_REF] Nerini | Cokriging for spatial functional data[END_REF][START_REF] Delicado | Statistics for spatial functional data: some recent contributions[END_REF][START_REF] Giraldo | Ordinary kriging for function-valued spatial data[END_REF][START_REF] Dabo-Niang | On spatial conditional mode estimation for a functional regressor[END_REF][START_REF] Menafoglio | A universal kriging predictor for spatially dependent functional data of a Hilbert space[END_REF][START_REF] Sangalli | Spatial spline regression models[END_REF][START_REF] Caballero | A universal kriging approach for spatial functional data[END_REF][START_REF] Ternynck | Spatial regression estimation for functional data with spatial dependency[END_REF][START_REF] Zhu | Spatially varying coefficient model for neuroimaging data with jump discontinuities[END_REF][START_REF] Bohorquez | Optimal sampling for spatial prediction of functional data[END_REF][START_REF] Bohorquez | Multivariate functional random fields: prediction and optimal sampling[END_REF], testing [START_REF] Aston | Tests for separability in nonparametric covariance operators of random surfaces[END_REF], among others. For more details, see the recent review of [START_REF] Menafoglio | Statistical analysis of complex and spatially dependent data: a review of Object Oriented Spatial Statistics[END_REF] on object oriented spatial statistics and references therein.

In the following, we propose to illustrate spatial prediction involving complex high dimension datum by a modern functional prediction technique, namely, functional kriging.

Spatial prediction of temperature curves

In this section we show briefly an application of universal kriging for functional data [START_REF] Caballero | A universal kriging approach for spatial functional data[END_REF] as an example of a methodology for modeling spatial big data. We consider daily temperature data recorded at 772 stations from the meteorological monitoring network of Colombia (Fig. 1). Specifically, we have 13.149 data at each station corresponding to daily records of maximum temperature ( • C) obtained from January 1, 1980 to December 31, 2015. Note that this is a spatiotemporal dataset and could be analyzed by using, among other methodologies, space-time geostatistics [START_REF] Christakos | Modern Spatiotemporal Geostatistics[END_REF]. However, given the high volume of data it is reasonable or even necessary to assume an approach based on FDA.

In Fig. 1 we show the temperature data of a sample of ten stations (of the total of 772) randomly selected. We only show the data in this small sample of stations in order to identify more easily the temporal behavior of the temperature. In a first step of the analysis the discrete data at each station are converted into curves by using smoothing methods. Specifically, we expand each time series in terms of 100 Fourier basis functions. The number of basis functions was chosen by using cross-validation. The temperature in Colombia varies considerably according to the topography. For this reason we take the altitude as a covariable into the analysis. As an example, we carry out prediction on an unvisited location (red point in Fig. 1). In order to reduce the computational time, we use as input the curves corresponding to the 30 closest stations to the prediction site. The smoothed curves in these sites and the prediction at the unvisited site considered are shown in Fig. 2.

The methodology here illustrated has been replicated for the Colombian Institute of Hydrology, Meteorology and Environmental Studies as a procedure for getting information of this variable in remote and difficult to access zones of Colombia. This technique has been also used to predict the temperature values in large time periods with missing values.

Further research

The purpose of the present work shows the relevancy of using the functional framework in analyzing massive spatial data. After an introduction to functional data as part of big data and a review, a spatial prediction method is used to forecast high dimension spatial temperature data.

Conceptually, FDA is suited for spatial huge data as shown by the illustration presented in this paper. However, this last is relatively simple and deals with a single functional object. In fact, spatial big data will become increasingly common, and a large number of complex situations with many potential applications may be considered. The statistical community must then address the challenge of proposing new methods for describing and analyzing spatial big data with complex structures. For instance, one may consider, different big and non-big data objects of different types (qualitative, quantitative, ordinal, . . . ) for different regions and pay attention to hot topics such as, missing (for instance a continuous part of a curve) or extreme data. Particularly, in the meteorological context considered in Section 3, the modeling of satellite information (an example of massive spatial datasets) in combination with ground data or taking into account the peak (maximum) in the smoothing procedure, is an open research field. For FDA, reaching the peaks necessitates an important amount of basis functions. In addition, setting a FDA approach requires a proper definition of the targeted function spaces, suitable metrics to measure similarity between objects, spatial or space-time correlations techniques, . . . . In fact, a main challenge when analyzing (dimension reduction, clustering, parametric, non-parametric, semi-parametric, additive regression models, analysis of variance, tests, . . . ) complex spatial big data is to use statistical tools able to compute in a non-costly way [START_REF] Cressie | Statistics for Spatio-Temporal Data[END_REF] spatial correlations among huge amounts of data [START_REF] Zipunnikov | Functional principal component model for high-dimensional brain imaging[END_REF][START_REF] Chen | Quantifying infinite-dimensional data: functional data analysis in action[END_REF].

Fig. 1 .Fig. 2 .

 12 Fig. 1. Top: Temperature monitoring network of Colombia (black points). Red point corresponds to a station without information. Bottom: Records of daily maximum temperature ( • C) obtained from January 1, 1980 to December 31, 2015 in ten stations (randomly chosen) from the Colombian meteorological monitoring network. (For interpretation of the references to colour in this figure legend, the reader is referred to the web version of this article.)


Ines Sarray

Annie Ressouche

Sabine Moisan

Jean-Paul Rigault

Daniel Gaffé
email: daniel.gaffe@unice.fr

A Synchronous Approach to Activity Recognition

Activity Recognition aims at recognizing and understanding sequences of actions and movements of mobile objects (human beings, animals or artefacts), that follow the predefined model of an activity. We propose to describe activities as a series of actions, triggered and driven by environmental events.

Due to the large range of application domains (surveillance, safety, health care...), we propose a generic approach to design activity recognition systems that interact continously with their environment and react to its stimuli at run-time.

In our target applications, the data coming from sensors (video-cameras, etc.) are first processed to recognize and track objects and to detect low-level events. This low-level information is collected and transformed into higher level inputs to our activity recognition system.

Such recognition systems must satisfy stringent requirements: dependability, real time, cost effectiveness, security and safety, correctness, completeness... To enforce most of these properties our approach is to base the configuration of the system as well as its execution on formal techniques. We chose the synchronous approach which provides formal bases to perform static analysis, verification and validation, but also direct implementation.

Several synchronous languages such as Lustre, Esterel, Scade and Signal [START_REF] Halbwachs | Synchronous Programming of Reactive Systems[END_REF] have been defined to describe synchronous automata. These languages are for expert users. We propose a new user-oriented language, named ADeL (Activity Description Language) to express activities and to automatically generate recognition automata. This language is easier to understand and to use by non computer scientists (e.g., physicians) while relying on formal semantics.

1 The ADeL language and its semantics ADeL is a (synchronous) language that allows non-computer scientists to describe activities and behaviors to be recognized. It is a modular and hierarchical language, which means that activities can be simple or composed of one or more sub-activities. ADeL has the notions of (typed) roles, events and sub-activities, flow of control... It supports parallelism, variants (choices), and repetitions and it relies on a set of formally specified control and temporal operators. Some of these operators are "instantaneous" while others take at least one (synchronous) instant to process.

We provide our language with both a graphical and textual format. We propose a graphical tool which displays several windows, mainly to declare the scene where the activity will take place (zones, roles and equipment) and to describe the activity (expected events and "story board"). However, it may be difficult to express complex activities in a purely graphical way, thus we also provide an equivalent textual form. 1

Semantics

To provide the language with sound foundations we turn to a formal semantic approach. First, a behavioral semantics formally describes the behavior of ADeL programs in a "natural way", using conditional rewriting rules, thus, it gives them a clear interpretation and facilitates their analysis. However, it is not a convenient implementation basis nor is it suitable for proofs (e.g., model-checking). Hence, we also define an equational semantics which transforms an ADeL program into a finite state machine represented as a Boolean equation system. The ADeL compiler can easily translate this system into efficient code.

These semantics rely on the notion of environment which is a finite set of events. Environments memorize the status of their events in each instant. The goal of both semantics is to compute the status of output events from input event status. We use a 4-valued algebra (ξ = {⊥, 0, 1, }) to represent the status of events, in order to get information about status of events (0 and 1 representing absent and present status; ⊥ and being associated with undefined and overdefined). We defined two orders in ξ: a knowledge order (≤ K ) to represent how the information about event status grows and a Boolean order (≤ B ) which naturally extends the usual Boolean order. Then, the structures (ξ, ≤ K ) and (ξ, ≤ B ) are lattices and their respective meet and join operations allow us to determine event status. Moreover, each element of ξ can be encoded as pairs of Booleans in a bijective way. A complete description is detailed in [START_REF] Sarray | Synchronous Automata For Activity Recognition[END_REF].

Behavioral Semantics

This semantics formalizes each reaction of a program by formally computing the output environment from the input one. It defines a set of rewriting rules of the form:

p E ,term -----→ E p
where p and p are two ADeL instructions, E is the input environment, E is the resulting output environment, and term is a Boolean flag which describes the termination of p and which turns to true when p terminates. We compute an output environment from an input one by applying hierarchically these rules on the instruction root of a program.

Equational Semantics

The equational semantics allows us to make an incremental compilation of ADeL programs by translating each root instruction of programs into a ξ-equation system. A ξ-equation system is defined as the 4-tuple < I, O, R, D > where I are the input events, O are the output events, R are the registers, i.e specific variables acting as memories to record values useful to compute the next instant, and D is the definition of the equation system to calculate the status of each event.

First, we defined the semantics for the operators of ADeL and then we extended these definitions to programs. The equational semantics is a function S e which calculates an output environment from an input one. Let p be an ADeL instruction and E an input environment, we denote D(p) its equation system and p E the resulting output environment. We have S e (p, E) = p E iff E D(p) → p E . From the event valuation of E, the equation system D(p) gives the event valuation of p E . According to the bijective encoding of ξ elements into Boolean pairs, we can represent environments and ξ-equation systems as Boolean ones, then we can calculate output event values in the Boolean world and finally go back to the 4-valued world. The → notation means that p E is deduced by applying well known Boolean algebra properties on Boolean equation systems.

Relation between Behavioral and Equational Semantics

Since we have two different semantics, it is important to establish the relation between the solutions obtained by both semantics. To this aim, we proved that the execution of a program based on the equational semantics also conforms to the behavioral semantics: if the equational semantics yields a solution, there exists also a behavioral solution with the same outputs: For more details see [START_REF] Sarray | Synchronous Automata For Activity Recognition[END_REF].

Compilation and Validation

To compile an ADeL program, we first transform it into an equation system which represents its synchronous automaton. Then we directly implement this equation system, transforming it into a Boolean equation system. The latter system provides an effective implementation of the initial ADeL program.

Since the equations may not be independent, we need to find a valid order (compatible with their interdependencies) to be able to generate code for execution, simulation, and verification. Thus we defined an efficient sorting algorithm [START_REF] Ressouche | Compilation modulaire d'un langage synchrone[END_REF], using a critical path scheduling approach, which computes all the valid partial orders instead of one unique total order. This facilitates merging several equation systems and we can perform incremental compilation: we can include an already compiled and sorted code for a sub-activity into a main one, without recompiling the latter.

The internal representation as Boolean equation systems also makes it possible to verify and validate ADeL programs, by generating a format suitable for a dedicated model checker such as the off-the-shelf NuSMV model-checker1 .

Related work

We are in the line of synchronous models and languages. However, ADeL is dedicated to non computer scientist end users and applied to a domain not usually targeted by synchronous approaches, namely human activity recognition. Other models such as Message Sequence Chart (MCS) [START_REF] Haitao Dan | A framework for pathologies of Message Sequence Charts[END_REF] or Live Sequence Chart (LSC) [START_REF] Kumar | Improving translation of Live Sequence Charts to temporal logic[END_REF] can also be used to describe activities. These languages may be given formal semantics liable to analysis. However, their formal verification, especially with model-checking, may be delicate.

Results

Our first experiments showed that the code generated by the ADeL compiler, basically composed of Boolean equations, is easy to integrate in a recognition system, produces compact code, and is efficient at run time. We are currently validating the ADeL graphical tool with doctors to describe medical activities.

Theorem 1

 1 Let p be an ADeL instruction, O a set of output events, and E an input environment. If p E is the resulting environment computed by the equational semantics, then the following property holds: ∃p such that p E ,FINISHp ------→ E p and ∀o ∈ O, o has the same status in p E and E

http://nusmv.fbk.eu/