Benjamin Heymann

J Frédéric Bonnans

Pierre Martinon

Francisco Silva

Fernando Lanas

Senior Member, IEEE Guillermo Jimenez

Continuous Optimal Control Approaches to Microgrid Energy Management

Keywords: Direct method, electricity production, Energy Management System (EMS), Dynamic Programming Principle (DPP), Mixed Integer Linear Programming (MILP), optimal control, Pontryagin Maximum Principle (PMP), semi-Lagrangian scheme, smart grid

.

. We achieve this performance by introducing a trick based on the Pontryagin Maximum Principle (PMP). The trick increases the computation speed by several orders and also improves the precision of the solution. For validation purposes, simulation are performed using datasets from an actual isolated microgrid located in northern Chile. Results show that DPP method is very well suited for this type of problem when compared with the MILP approach.

I. INTRODUCTION

A MICROGRID is a group of interconnected loads and dis- tributed energy resources that acts as a single controllable entity. It can operate connected to the main network or autonomously (isolated). In either case, an Energy Management System (EMS) is required to coordinate the different units that composes it. As described in [START_REF] Olivares | Trends in microgrid control[END_REF], the microgrid optimal energy management problem falls into the category of mixed integer nonlinear programming. Thus, the objective function and constraints may include functions of second or higher order polynomial equations with some start-up/shutdown variables. Complex constraints are involved to model the operational limitations of generation / storage devices or to represent controllable loads and commitment decisions. Furthermore, considering network constraints (load flow) adds another degree of complexity to the microgrid optimal energy management problem. To handle and solve these problem formulations, heuristic optimization techniques have been applied, including Genetic Algorithms (GA) [START_REF] Conti | Optimal dispatching of distributed generators in an MV autonomous micro-grid to minimize operating costs and emissions[END_REF], [START_REF] Hatziargyriou | Energy management and control of island power systems with increased penetration from renewable sources[END_REF], PSO [START_REF] Conti | Optimal dispatching of distributed generators in an MV autonomous micro-grid to minimize operating costs and emissions[END_REF], and Ant Colony Optimization (ACO) [START_REF] Colson | Ant colony optimization for microgrid multi-objective power management[END_REF]; the problem formulation has also been relaxed by incorporating the inequality constraints in the objective function using penalty factors. The minimization of total operating cost in stand-alone operation, and maximization of microgrids revenue in grid connected mode are two typically pursued objectives in secondary control. Nevertheless, MILP formulations have been also developed presenting adequate results but with difficulties for modeling battery charging/discharging behavior, and the diesel engine costs [START_REF] Olivares | Trends in microgrid control[END_REF]. However, some approaches have also incorporated the reduction of Greenhouse gas (GHG) emissions as an additional objective for the microgrid operation. In this case, the energy management problem is formulated as a multi-objective optimization problem and solved with different techniques [START_REF] Olivares | Trends in microgrid control[END_REF]. Pareto optimal solutions are investigated in [START_REF] Colson | Ant colony optimization for microgrid multi-objective power management[END_REF] and [START_REF] Colson | Towards realtime microgrid power management using computational intelligence methods[END_REF] by using PSO and ACO techniques, respectively, while a weighted objective function that combines different individual objective functions, together with heuristic optimization techniques, are used in [START_REF] Alvarez | On-line minimization of running costs, greenhouse gas emissions and the impact of distributed generation using microgrids on the electrical system[END_REF], [START_REF] Kanchev | Smart monitoring of a microgrid including gas turbines and a dispatched PV-based active generator for energy management and emissions reduction[END_REF]. Finally, recent works, focusing on micro grid energy management systems, have incorporated a more detailed modeling of the energy storage system, considering the importance of the cost associated with its replacement, so that extending the life span of the battery is part of the objective. In this context, GA have been implemented to solve the problem [START_REF] Zhao | Operation optimization of standalone microgrids considering lifetime characteristics of battery energy storage system[END_REF], and other predictive control approaches such as the ones described in [START_REF] Garcia | Optimal economic dispatch for renewable energy microgrids with hybrid storage using Model Predictive Control[END_REF], [START_REF] Pourmousavi | A framework for real-time power management of a grid-tied microgrid to extend battery lifetime and reduce cost of energy[END_REF], [START_REF] Hooshmand | A novel cost-aware multiobjective energy management method for microgrids[END_REF], [START_REF] Khasawneh | Battery cycle life balancing in a microgrid through flexible distribution of energy and storage resources[END_REF].

Considering the challenges involved with the microgrid EMS problem such as units modeling, CPU solving time for real applications and switching among others, a microgrid model formulation as a continuous time, optimal control problem is presented in this work. This approach keeps the original non-linear model for the numerical optimization, which may give more accurate solutions. The proposal considers two solution methods that are detailed as follows: The direct method uses a time discretization to transform the continuous optimal control problem into a Nonlinear Programming (NLP) problem. The (NLP) is then solved with any usual technique, see for instance [START_REF] Betts | Practical Methods for Optimal Control Using Nonlinear Programming, ser. Advances in design and control[END_REF]. The DPP method is based on Bellmans Principle and uses a discretization of both the time and space to compute the value function. This information then allows to reconstruct the optimal trajectory, see for example [START_REF] Bellman | Dynamic Programming[END_REF].

Numerical simulations are performed for both methods using the optimal toolbox BOCOP [START_REF] Bonnans | Bocop -a collection of examples[END_REF]. The proposed methods are validated based on a real microgrid operating in Huatacondo, an isolated northern Chilean village that relies completely on the microgrid concept for its electricity supply, which is described in section II. The present study uses a similar model to the one presented in [START_REF] Palma-Behnke | A microgrid energy management system based on the rolling horizon strategy[END_REF], so that the comparison is relevant showing obtained results for the three approaches, MILP, direct method and DPP.

The paper is organized as follows. Section II describes the microgrid system and the optimal control formulation for its energy management. Section III explains the numerical methods we use to solve the optimal control problem. Section IV presents the numerical simulations with the direct and DPP methods. Section V comments the results of the simulations. The following model is based on a real microgrid operating in Huatacondo, an isolated northern Chilean village that relies completely on the microgrid concept for its electricity supply. The microgrid consists of a photovoltaic (PV) power plant, a diesel generator and a Battery Energy Storage System (BESS). It uses a mix of fuel and renewable energy sources. The solar panel and the wind turbine produce electricity without any additional cost, but the generation pattern cannot be controlled, and depends on the everyday weather. The BESS can store energy for later use, but has a limited capacity and power. The diesel generator has a minimal and maximal output level, and has a fixed start-up cost. All these are local generation units, i.e. situated physically near the electrical consumption, and we do not consider electrical losses due to distribution. The aim is to find the optimal planning that meets the power demand and minimizes the operational costs, which in this case mainly relates to the diesel consumption. We follow the problem description from [START_REF] Palma-Behnke | A microgrid energy management system based on the rolling horizon strategy[END_REF].

2) Optimal Control Formulation: We take a fixed horizon T = 48 hours. For t ∈ [0, T ], we denote by P S (t) the solar power from the photovoltaic panels, P D (t) the diesel generator power and P L (t) the electricity load. The state of charge SOC(t) of the BESS evolves according to the dynamics

ṠOC(t) = 1 Q B (P I (t)ρ I -P O (t)/ρ O ) , (1)
where Q B is the maximum capacity of the battery, P I , P O > 0 are the input and output power of the BESS, and ρ I , ρ o ∈ [0, 1] are the efficiency ratios for the charge and discharge processes, assumed constant. We also introduce the slack variable P slack that represents the excess power (P slack < 0), which have to be shedded, or missing power in the microgrid (P slack > 0), which turns into unserved energy for the consumers. From the mathematical point of view, this ensures feasibility of the problem. From the practical point of view, a cost is associated to the unserved power, associated with a fine.

The underlying power equilibrium equation is

P D + P O + P S + P slack -P L -P I = 0 (2)
Taking into account the demand and the various power production devices, we obtain that P O and P I can be written as nonlinear functions of (t, P D ):

PO(t, PD) = -min(0, PS + PD -PL + P slack ) PI (t, PD) = max(0, PS + PD -PL + P slack ).
(3)

Fig. 1: Battery charge constraint

We model the fuel consumption of the diesel generator by the following strictly concave function

T 0 KP D (t) 0.9 dt, (4)
with K = 0.471426 obtained by regression on data from the actual generator consumption.

For physical reasons, the system is subject to the following constraints at every time t ∈ [0, T ]:

SOC(t) ∈ [0.2, 1] (5)
P D (t) ∈ {0} ∪ [P min , P max ] (6)
PI (PD(t), t) ∈ [0, 13.2] if SOC(t) < 0.9 PI (PD(t), t) ≤ 1320(SOC(t) -1) 2 otherwise ( 7)

PO(t) ∈ [0, 40], (8)
Note that (3) implies that ( 7)-( 8) are constraints on P D . The state constraint (5) expresses the maximum and minimum charge of the battery. Constraints ( 6) to ( 8) are control constraints. The minimal and maximal power for the diesel generator are given by [START_REF] Olivares | Trends in microgrid control[END_REF]. The charging and discharging limits for the battery are stated in [START_REF] Conti | Optimal dispatching of distributed generators in an MV autonomous micro-grid to minimize operating costs and emissions[END_REF] and [START_REF] Hatziargyriou | Energy management and control of island power systems with increased penetration from renewable sources[END_REF]. The charging limit depends on the state of charge, and is therefore a mixed control-state constraint, as illustrated on Fig. 1.

Since the operations time frame is larger than the optimization horizon, we impose a constraint on the final time to avoid the battery depletion. This constraint will be imposed through either a periodicity condition SOC(0) = SOC(T ) (direct method) or a penalization term g(SOC(T )) (DPP method).

To sum up, the optimal control problem to be solved can be written under the following abstract formulation

(OCP )                    min u T 0 (u(t))dt + g(x(T )) ẋ(t) = F (u(t), t) x(0) = x 0 u(t) ∈ U x(t) x(t) ∈ C. (9)
In the notation above, x is the state variable (SOC), u is the control variable (P D ), F is the dynamics of the system, U x(t) corresponds to the control constraints on u(t) that may depend on the value of x(t), and C corresponds to the state constraints.

B. Switching cost

Turning the diesel generator on consumes fuel. We model this by considering that the diesel generator has two modes: when off, the only admissible control is P D = 0, whereas when it is on, P D ∈ [P min , P max ]. At any time, one can switch from one mode to the other by paying the associated cost. It should be stressed out that while the modeling of the switching cost is made straightforward by the Dynamic Programming approach, it is challenging for the Direct Method approach.

III. PRESENTATION OF THE NUMERICAL METHODS

We give here a brief presentation of the two resolution approaches we are considering and explain how to apply them for solving [START_REF] Colson | Ant colony optimization for microgrid multi-objective power management[END_REF]. The interested reader will find more on those approaches in [START_REF] Falcone | Semi-Lagrangian Approximation Schemes for Linear and Hamilton-Jacobi Equations[END_REF], [START_REF] Bardi | Optimal control and viscosity solutions of Hamilton-Jacobi-Bellman equations, ser. Systems and Control: Foundations and Applications[END_REF].

A. The Direct Method Approach 1) Presentation: In the Direct Method we apply a time discretization to the dynamics equation. The optimal control problem is rewritten as a finite-dimensional optimization problem. The "decision" variables of this discretized problem are the values of the control variables for each time steps. Since the discretized problem is solved by locally convergent algorithms, we cannot guarantee that the obtained solution (if any) is close to a global optimum. On the other hand, this approach often provides efficient solutions for large optimal control problems, with limited computing times. Summary of the time discretization, using the Euler formula:

t ∈ [0, T ] → {t 0 = 0, . . . , t N = T } x(•), u(•) → Z = {x 0 , . . . , x N , u 0 , . . . , u N -1 } Criterion → min h N -1 i=0 (u i ) + G(x N ) Dynamics → x i+i = x i + hf (x i , u i ) i = 0, . . . , N Controls → u i ∈ U xi i = 0, . . . , N -1 States → x i ∈ C i = 0, . . . , N
We therefore obtain a nonlinear programming problem on the discretized state and control variables

(N LP ) min Z F (Z) LB ≤ C(Z) ≤ U B
In the optimal control toolbox BOCOP the discretized nonlinear optimization problem is solved by the IPOPT solver [START_REF] Waechter | On the implementation of an interiorpoint filter line-search algorithm for large-scale nonlinear programming[END_REF] that implements a primal-dual interior point algorithm.

2) Modeling Remarks: This method allows a periodicity constraint of the form SOC(0) = SOC(T ) where the actual value is optimized by the algorithm. On the other hand, the constraint ( 6) is simplified into P D ∈ [0, P max ]. Another drawback is that switching costs are binary decisions which are not easily handled in this framework. Finally, the cost function is regularized by a small quadratic term

T 0 P 2 O (t)
dt in order to improve convergence.

B. Dynamic Programming Approach

In order to solve the DPP, we propose a semi-Lagrangian scheme, which is adapted for problems with switching modes. We refer the reader to [START_REF] Falcone | Semi-Lagrangian Approximation Schemes for Linear and Hamilton-Jacobi Equations[END_REF] and the references therein for an introduction to semi-Lagrangian schemes applied to optimal control problems. In addition, the Pontryagin Maximum Principle (PMP), see [START_REF] Pontryagin | The Mathematical Theory of Optimal Processes[END_REF], can be used to give additional information on the optimal solution, which allows to significantly reduce the computational effort of the method.

1) Brief Presentation of the Theory: Let V (t, x 0 ) denote the value of problem [START_REF] Colson | Ant colony optimization for microgrid multi-objective power management[END_REF] with initial time t and initial condition x 0 . In R. Bellman's words [START_REF] Bellman | Dynamic Programming[END_REF] "An optimal policy has the property that whatever the initial state and initial decision are, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision." In mathematical terms, V satisfies for h ∈ (0, T -t):

V (t, x 0 ) = inf t+h t (u t )ds + V (t + h, x(t + h)) , (10
) the infimum being taken over the set of admissible controls. In our case, we will use an extended version of the DPP approach that handles the switchings.

2) Semi-Lagrangian scheme: The Semi-Lagrangian scheme consists in solving backward in time a discretization of (10) over the space. We have chosen this scheme to solve the problem because it has good stability properties, it allows large time steps and it is easy to implement. Let us motivate the scheme by first discretizing in time [START_REF] Colson | Towards realtime microgrid power management using computational intelligence methods[END_REF]. Given a time step h and N such that N h = T , let us set t k = kh (k = 0, . . . , N ). Denoting by V k the "approximated" value function at t k we have

V k (x) = min u∈Ux h (u) + V k+1 (x + hF (u, t k )) . (11)
The Semi-Lagrangian scheme is obtained from [START_REF] Alvarez | On-line minimization of running costs, greenhouse gas emissions and the impact of distributed generation using microgrids on the electrical system[END_REF], by discretizing in space the state variable x and introducing interpolation operators in order to approximate V k+1 (x + hF (u, t k )) in terms of its values in the space grid. The scheme is solved backward in time and, under standard conditions, it is shown that it converges to the solution V of (10).

3) The PMP trick: The problem has an interesting property that greatly reduces the numerical computations. If ū is the optimal control, denote by x the optimal state and by p the Lagrange multiplier associated to the dynamics constraint ẋ(t) = F (t, u(t)). Defining the Hamiltonian H(u, p, t) := pF (u, t) + (u) the PMP says that for all t ∈ [0, T ] we have

H(ū(t), p(t), t) ≤ H(v, p(t), t) for all v ∈ U x(t) .
Since v → H(v, p(t), t) is piecewise strictly concave, it can attain its minimum only at one of the extreme points of the pieces. Taking also into account the constraints, we have at most five possible optimal controls, as illustrated in figure 2. Moreover, the values of those controls can be computed explicitly, since they do not depend on p. Therefore, when doing the minimization in [START_REF] Alvarez | On-line minimization of running costs, greenhouse gas emissions and the impact of distributed generation using microgrids on the electrical system[END_REF], we can test only those controls instead of discretizing the control space, gaining both in speed and precision. It should be noted that the specific structure of the problem permits such a computational simplification. More precisely, we use the fact that all the candidates values for the optimal control do not depend on the adjoint state p and therefore can be evaluated and tested when computing the value function. In the general case, the control that minimizes the Hamiltonian is expressed from both the state and adjoint state, the latter being unavailable in the DPP approach (the adjoint actually corresponds to the gradient of the Value Function).

Remark 3.1: Slack variable In the five cases above, when we set the diesel power, we recompute the battery power from the power equilibrium (2), then adjust the slack variable if needed. When we set the battery power, we then recompute the diesel power from (2) and adjust the slack likewise.

4) Periodicity condition: We model the periodicity condition by taking a similar approach to the "big M method" in linear programming:

g(SOC(T )) = M ifSOC(T ) < SOC 0 g(SOC(T )) = 0 if SOC(T ) ≥ SOC 0
For the following simulations, we set SOC 0 = 0.7.

IV. NUMERICAL SIMULATIONS A. Comments on the inputs: solar power and power load

We test the algorithms on two historical data sets. Both data sets correspond to the two most representative 24 hours days, one data set was obtained with winter data, the other one with summer data. Figure 3 and4 show the load power and the solar power for the two days of each period.

Given the situation of the actual microgrid in the Atacama desert, we assume the production from the photovoltaic panels Fig. 3: Summer data, the bell shaped curve is the solar production, and the other one is the demand Fig. 4: Winter data, the bell shaped curve is the solar production, and the other one is the demand to be reliably predictable, with small variance and almost determistic. The demand on the other hand has a greater variability. While in this initial work it is modeled as deterministic, its stochastic modeling is under study.

B. Optimal solutions for the different methods

In addition to the direct and DPP methods, we also present the results obtained with the MILP approach from [START_REF] Palma-Behnke | A microgrid energy management system based on the rolling horizon strategy[END_REF] as baseline for comparison. The 6 solutions are illustrated in Figure 5 and 6 for the DPP approach, in Figure 7 and8 for the direct approach and in Figure 9 and 10 for MILP method. The numerical results are summarized in Table I Discussion on the solutions:

• MILP and DPP solutions are quite close, while direct solution shows some clear differences (different initial/final SOC, no minimal power, spurious switchings) is switched on once a day during the evening peak in demand. Diesel output is often greater than power demand. At this times it is used also to charge the battery • The battery fills the gaps between solar and diesel power in order to meet the demand, especially at night • A qualitative difference between MILP and DPP/direct is the existence of time intervals with a constant SOC, while the diesel exactly matches the power load. In the MILP solutions the diesel is either off or saturating the maximal charge limit. This behaviour seems consistent with the concavity of the diesel comsumption with respect to power output (i.e. the efficiency of the diesel is better at higher output). On the other hand, both the direct and DPP solutions present intervals with constant SOC, and the PMP confirms this situation to be a possible optimum. This point would deserve closer investigation, for instance is this discrepancy due to the linearization performed in MILP ?

C. Comparison of the methods

We highlight below the differences between the three different optimization methods.

Global optimum : Both the MILP and direct approaches are local methods and may converge to a local solution, depending on the provided starting point and the choice of the stopping criterion (gap). On the other hand, the DPP approach performs a global optimization over all possible (discretized) trajectories, and therefore always finds the global optimum. This is an advantage for the user since one does not have to find a "suitable" starting point. Also, the DPP solution has a control in feedback form, whereas MILP and direct solutions are open-loop.

Switching cost : Both MILP and DPP approaches take into account the switching costs for the diesel generator. They typically find solutions with one switch per day, located during the peak of power demand in the evening. On the other hand, the direct approach has free switchings, which explains why it may find solutions with lots of on-off oscillations. This bad behaviour, however, can be partially alleviated by using a regularization of the cost function.

Nonlinear model : The MILP method requires a piecewise linear reformulation of the nonlinear functions in the model, here for example the charging power limit or diesel consumption. Both direct and DPP methods use the original nonlinear model. This simplifies the actual implementation, and may also give more accurate solutions.

Periodicity constraint and minimal diesel power : Compared to MILP and DPP, the direct method is able to optimize the value of the initial/final SOC, instead of fixing it. On the other hand, it does not take into account the minimal power output for the diesel generator.

Computation time : For this problem the computation time is a few seconds for MILP and direct method, and less than one second for the DPP approach. An interesting question is how well each method would scale for higher dimensions. MILP and direct approach are iterative methods, so changing the problem size may also lead to a different convergence, making it difficult to asses the evolution of the CPU time. For the DPP approach, on the other hand, the number of operations is always known and the CPU time can be predicted reliably. Due to the state discretization, however, adding new state variables to the problem would have a significant impact on performance (the so-called curse of dimensionality). In terms of high performance computing, parallelization is possible with MILP and DPP methods, not so easily with the direct method.

V. CONCLUSION AND PERSPECTIVES

We have applied two methods from the continuous optimal control field to the optimal energy management of a microgrid, namely the direct and DPP approaches. Numerical simulations indicate that the DPP methods is very well suited to this problem. We were able to obtain the global optimum in less than one second of CPU time, while taking into account the switching cost for the diesel generator. Solutions are close to the ones obtained in [START_REF] Palma-Behnke | A microgrid energy management system based on the rolling horizon strategy[END_REF] with a MILP formulation, the main difference being the existence of time intervals where the battery stays at a constant SOC.

Ongoing work on this topic include a deeper investigation of the optimality conditions from Pontryagin's Principle, the extension to a stochastic model for the power demand, and the study of the long-term aging of the battery.

APPENDIX MODEL PARAMETERS

Name

  The conclusion sums up the main results and presents ongoing research in the continuation of this work. March 11, 2015 II. MODEL PRESENTATION A. General Aspects 1) Description of the Microgrid:

Fig. 2 :

 2 Fig. 2: The PMP trick illustrated

Fig. 7 :Fig. 8 :

 78 Fig. 5: Summer DPP Simulation

  .

		MILP	DIRECT	DPP
	Diesel range	[18.66,29.69] [2.63,14.23] [8.15,28.66]
	Switchings	2	3	2
	Total Cost	34785	36244	34378
	Cpu Time	3.92 s	4.41 s	0.88 s
	SOC(0)=SOC(T) 0.7	0.641	0.7
	SOC range	[0.20,0.89]	[0.38,0.75]	[0.30,0.83]
	Slack Range	[0,0]	[0,0]	[0,0]

TABLE I :

 I

Results: MILP, direct and DPP (summer case)

TABLE II :

 II Model parameters ACKNOWLEDGMENT This project is the product of a collaboration between the COMMANDS (INRIA, France) and Centro de Energia teams (Universidad de Chile, Chile).


Noureddine-Yassine Nair-Benrekia

Pascale Kuntz
email: pascale.kuntz@univ-nantes.fr

Frank Meyer
email: franck.meyer@orange.com

Learning from multi-label data with interactivity constraints: an extensive experimental study

Keywords: interactive learning, multi-label learning, comparative study

Interactive classification aims at introducing user preferences in the learning process to produce individualized outcomes more adapted to each user's behaviour than the fully automatic approaches. The current interactive classification systems generally adopt a singlelabel classification paradigm that constrains items to span one label at a time and consequently limit the user's expressiveness while he/she interacts with data that are inherently multi-label. Moreover, the experimental evaluations are mainly subjective and closely depend on the targeted use cases and the interface characteristics. This paper presents the first extensive study of the impact of the interactivity constraints on the performances of a large set of twelve well-established multi-label learning methods. We restrict ourselves to the evaluation of the classifier predictive and time-computation performances while the number of training examples regularly increases and we focus on the beginning of the classification task where few examples are available. The classifier performances are evaluated with an experimental protocol independent of any implementation environment on a set of twelve multi-label benchmarks of various sizes from different domains. Our comparison shows that four classifiers can be distinguished for the prediction quality: RF-PCT (Random Forest of Predictive Clustering Trees, Kocev (2012)), EBR (Ensemble of Binary Relevance, (Read et al., 2011)), CLR (Calibrated Label Ranking, Fürnkranz et al. (2008)) and MLkNN (Multi-label kNN, Zhang and Zhou (2007)) with an advantage for the first two ensemble 1 classifiers. Moreover, only RF-PCT competes with the fastest classifiers and is therefore considered as the most promising classifier for an interactive multi-label learning system.

Introduction

By integrating some user preferences in a classification process, human-centered systems aim at producing individualized outcomes more adapted to each user's behavior than the fully automatic approaches (e.g. [START_REF] Amershi | Power to the people: The role of humans in interactive machine learning[END_REF]; [START_REF] Porter | Interactive machine learning in data exploitation[END_REF]; [START_REF] Amershi | Designing for effective end-user interaction with machine learning[END_REF]; [START_REF] Lintott | Galaxy zoo: morphologies derived from visual inspection of galaxies from the sloan digital sky survey[END_REF]; [START_REF] Fails | Interactive machine learning[END_REF]; [START_REF] Ware | Interactive machine learning: letting users build classifiers[END_REF]). When the preferences are made explicit, they can be integrated in the learning model, for instance by defining some constraints on the dataset [START_REF] Wagstaff | Constrained k-means clustering with background knowledge[END_REF][START_REF] Bilenko | Integrating constraints and metric learning in semisupervised clustering[END_REF]. Otherwise, an alternative is to let the user interact with the system which dynamically learns from his/her behavior. As recently defined by [START_REF] Amershi | Power to the people: The role of humans in interactive machine learning[END_REF] « interactive machine learning is a process that involves a tight interaction loop between a human and a machine learner, where the learner iteratively takes input from the human, promptly incorporates that input, and then provides the human with output impacted by the results of the iteration ».

In a classification framework, the learning algorithm tries to quickly build a first predictive model from a restricted set of examples given by the user and it presents him/her with personalized predictions. For instance, to query a Video on Demand (VoD) catalogue for a good film to watch, a user defines his/her target concepts such as « Funny », « Masterpiece », and « Fairytale » and with an adapted interface he/she labels a small set of familiar films (e.g. Ice Age (« Funny »), Avatar (« Masterpiece », « Fairytale »)) (see Figure 1).

A classification algorithm tries to capture the user's preferences and to learn a predictive model which provides the user with other relevant films from the catalogue. To strengthen the predictive performance of the model, the user regularly inspects the quality of the predictions and possibly corrects the misclassified examples (i.e. relevance feedback [START_REF] Stumpf | Toward harnessing user feedback for machine learning[END_REF][START_REF] Salton | Improving retrieval performance by relevance feedback[END_REF]). The increasing importance currently given to personalized contents has led to the development of several interactive classification systems for various real-world applications: e.g. image classification [START_REF] Fogarty | Cueflik: interactive concept learning in image search[END_REF], file selection [START_REF] Ritter | Learning to generalize for complex selection tasks[END_REF], gesture classification [START_REF] Fiebrink | A metainstrument for interactive, on-the-fly machine learning[END_REF], document classification [START_REF] Drucker | Helping users sort faster with adaptive machine learning recommendations[END_REF], alarm triage [START_REF] Amershi | Cuet: human-guided fast and accurate network alarm triage[END_REF] and profile classification in social networks [START_REF] Amershi | Regroup: Interactive machine learning for on-demand group creation in social networks[END_REF]. Some experimental results on the targeted domain are promising but each of these approaches adopts a single-label classification paradigm that constrains items to span one label at a time. This simplifying framework significantly limits the user's expressiveness while he/she interacts with data that are inherently multi-label.

Learning from multi-label data has received significant attention over the past few years from machine learning and its related communities [START_REF] Zhang | A review on multi-label learning algorithms[END_REF][START_REF] Madjarov | An extensive experimental comparison of methods for multi-label learning[END_REF][START_REF] Sorower | A literature survey on algorithms for multi-label learning[END_REF][START_REF] Tsoumakas | Mining multi-label data[END_REF][START_REF] Tsoumakas | Multi-label classification: An overview[END_REF]. Initially developed for text categorization [START_REF] Schapire | Boostexter: A boosting-based system for text categorization[END_REF], approaches have been extended to diverse application domains: classification of multimedia contents including image [START_REF] Boutell | Learning multi-label scene classification[END_REF], audio [START_REF] Lo | Cost-sensitive multi-label learning for audio tag annotation and retrieval[END_REF] and video [START_REF] Snoek | The challenge problem for automated detection of 101 semantic concepts in multimedia[END_REF], web and rule mining [START_REF] Ozonat | Towards a universal marketplace over the web: Statistical multi-label classification of service provider forms with simulated annealing[END_REF][START_REF] Rak | Multi-label associative classification of medical documents from medline[END_REF], bioinformatics [START_REF] King | Knowledge discovery in multi-label phenotype data[END_REF], tag recommendation [START_REF] Katakis | Multilabel text classification for automated tag suggestion[END_REF] and information retrieval [START_REF] Yu | Multi-label informed latent semantic indexing[END_REF].

Our final objective in the next future is to integrate a multi-label approach into an interactive classification system to allow users to label examples with several subjective labels of interest and consequently express complex search queries on data; VoD being one of our privileged application field. And the first major issue common to all developers of such a system is: which multi-label classifier should we choose? The efficiency of a real-life interactive machine learning system depends on different factors such as, in particular, the quality of the learner, the data visualization display and the interaction tools. In this paper, we restrict ourselves to the analysis of the learner behaviours without taken into account the human interface dimension and we evaluate their performances with an experimental protocol independent of any implementation environment.

More precisely, we here consider the two following major constraints: learning from few training examples in a limited time. And we study the impact of these constraints on the performances of a large set of twelve well-established algorithms from the three major families of multi-label learning methods: five problem transformation methods, two algorithm adaptation methods and five ensemble methods. We evaluate each classifier on a collection of nested training sets of increasing sizes and we focus on the beginning of the classification process where the number of examples is limited. The literature presents a wide range of measures for the evaluation of the classifier predictive performances (e.g. [START_REF] Tsoumakas | Mining multi-label data[END_REF][START_REF] Zhang | A review on multi-label learning algorithms[END_REF]) but there is no consensus on the podium of the « best » measures. We here focus on the most useful criteria in the interactive context: ranking labels by relevance, ranking examples by relevance and classifying labels. These criteria have led us to select four measures from the literature (Ranking Loss, Accuracy, F 1 -score and multi-label Balanced Error Rate BER) and to propose an adaptation of the Ranking Loss for evaluating the quality of the label example ranking. For consolidating our conclusions, we additionally consider five classical measures: Coverage, One Error, Average Precision, Hamming Loss and Exact match. The computational efficiency of the classifiers is measured by both the running time observed in the experiments and the theoretical computational complexities required for training and testing the models.

The comparison of the twelve algorithms is performed on a set of twelve multi-label benchmarks of various sizes from five different domains (music, audio, image, biology and text). It shows that, for the learning quality criteria, the four classifiers which significantly outperform the others are: the problem transformation method CLR (Calibrated Label Ranking, [START_REF] Fürnkranz | Multilabel classification via calibrated label ranking[END_REF]), the algorithm adaptation method ML-kNN (Multi-Label k Nearest Neighbours, [START_REF] Zhang | Ml-knn: A lazy learning approach to multi-label learning[END_REF]), and the ensemble methods EBR (Ensemble of Binary Relevance, [START_REF] Read | Classifier chains for multi-label classification[END_REF]) and RF-PCT (Random Forest of Predictive Clustering Trees, [START_REF] Kocev | Ensembles for predicting structured outputs[END_REF]). A precise analysis of the difference in their predictive performances concludes that RF-PCT is the best classifier, closely followed by EBR. However, when considering the time criteria, only RF-PCT competes with the fastest classifiers that are the least accurate classifiers. Let us note that RF-PCT was already the best performing classifier for large training data sets [START_REF] Madjarov | An extensive experimental comparison of methods for multi-label learning[END_REF].

The rest of the paper is organized as follows. Section 2 presents some related recent works both in interactive classification and in multi-label learning. In Section 3, we precisely define the constraints considered in our interactive multi-label classification problem. The experimental protocol and the benchmark datasets are described in Section 4. Section 5 presents the classifier comparison for the learning efficiency with a limited training set and Section 6 presents the learning and predicting time evaluations.

Related Work

We first briefly present some interactive classification systems which have been recently developed. Then, we list the multi-label classifiers used in our comparisons and we recall the performances obtained from published extensive comparisons.

Interactive classification

In this section, we have retained five recent interactive classification systems to illustrate the potentialities of the user-centered approaches.

CueFlik [START_REF] Fogarty | Cueflik: interactive concept learning in image search[END_REF] is an image classifier that automatically recognizes a user's desired visual concept (e.g. scenic, visually busy, or colourful images). The user queries a catalogue of images and selects some images with and without the desired visual characteristics from the obtained results. A kNN algorithm re-ranks the images using a similarity measure whose parameters are learned from the user's actions. [START_REF] Ritter | Learning to generalize for complex selection tasks[END_REF]) is a file classifier to perform complex file search queries (e.g. selection of all files that contain the substring "old"). To train the classifier, the user only clicks few desired files. Using boosted decision trees, the system selects the rest. iCluster [START_REF] Drucker | Helping users sort faster with adaptive machine learning recommendations[END_REF][START_REF] Basu | Assisting users with clustering tasks by combining metric learning and classification[END_REF] is a document classifier that detects preferred documents. The user defines a set of desired labels and associates each document with the label that better describes it. From a restricted training set, the system provides two predictions: for a new example, a ranking of its predicted labels, and for a selected label, a ranking of its top(20) predicted new examples. It uses a hybrid learning mechanism that combines a logistic regression classifier with a metric learner.

Smart selection

CueT [START_REF] Amershi | Cuet: human-guided fast and accurate network alarm triage[END_REF] is an alarm classifier that helps network operators to triage alarms. A operator first defines a set of labels and then manually labels a restricted number of alarms according to their severity. From the triaging decisions, the system uses a nearest neighbour strategy combined with an adaptive distance function to predict the label of a new incoming alarm in the network.

Regroup [START_REF] Amershi | Regroup: Interactive machine learning for on-demand group creation in social networks[END_REF] is a profile classifier that recognizes desired profiles in a social network. To explain a target profile, a user selects some friends with the desired characteristics. Using a Naïve Bayes classifier, the system re-ranks the remaining friend set according to their probability to belong to the group. These systems show that interactive classification presents attractive properties for reallife applications. However, all of them constrain users to associate examples with a single label, which seems artificial for decisions on data that generally imply a combination of labels. For instance, images in CueFlik may contain many visual concepts, documents in iCluster may talk about several subjects and users in Regroup may belong to different social groups.

Multi-label classification

Generally speaking, the multi-label classification approaches can be categorized in three main families. The problem transformation methods are probably the most popular approaches. They do not learn directly from the multi-label data: they transform the multilabel learning problem into one or several single-label classification or regression problems.

The algorithm adaptation methods adapt existing learning algorithms to learn from multi-label data. The ensemble methods or meta-methods involve a collection of learners to make multi-label predictions. These learners belong to one of the two previous families.

An exhaustive description is beyond the scope of this paper. We here restrict ourselves to a brief presentation of the twelve approaches retained for our comparison. They are among the mostly-studied multi-label classifiers and they include the classifiers that [START_REF] Madjarov | An extensive experimental comparison of methods for multi-label learning[END_REF] have recommended from their recent extensive experimental study.

Problem transformation methods

We have selected five approaches plus a baseline. [START_REF] Schapire | Boostexter: A boosting-based system for text categorization[END_REF] is probably the most popular transformation method. It learns one binary classifier for each label independently. For a new instance, it outputs the union of the labels predicted by the learned models.

Binary Relevance (BR)

Classifier Chain (CC) [START_REF] Read | Classifier chains for multi-label classification[END_REF] is an extension of BR that trains the classifiers in a random chain and extends the feature space associated with each classifier with the labels of the previous classifiers in the chain. For a new instance, like BR, CC presents the union of the labels predicted by each classifier in the chain. [START_REF] Tsoumakas | Multi-label classification: An overview[END_REF] considers each label set as a single atomic label and then trains a single-label multi-class classifier. For a new instance, LP predicts the most likely label set. [START_REF] Fürnkranz | Multilabel classification via calibrated label ranking[END_REF] extends the Ranking by Pairwise Comparison method (RPC ) [START_REF] Hüllermeier | Label ranking by learning pairwise preferences[END_REF] by introducing an additional virtual label to separate the relevant labels from the irrelevant ones. For a new instance, CLR returns the average vote on all models for each label. [START_REF] Tsoumakas | Effective and efficient multilabel classification in domains with large number of labels[END_REF] recursively constructs a tree of LP classifiers which consider small label subsets. The labels of each node are distributed into several disjoint subsets using a balanced clustering algorithm such that each child node is associated with a different cluster. For a new instance, HOMER starts with the root classifier and follows a recursive process forwarding this instance to the multi-label classifiers of the child nodes.

Label Powerset (LP)

Calibrated Label Ranking (CLR)

Hierarchy Of Multi-label classifiERs (HOMER)

The Baseline computes the frequency of each label set in the training set. For a new instance, it returns the most frequent label set.

The problem transformation methods are flexible: they are free to use any existing single-label base classifier. However, their efficiency mainly depends on the choice of this base learner. In general, two base-learners are commonly used [START_REF] Tawiah | A study on multi-label classification[END_REF][START_REF] Madjarov | An extensive experimental comparison of methods for multi-label learning[END_REF][START_REF] Read | Scalable multi-label classification[END_REF]: Support Vector Machine (SVM) [START_REF] Platt | Probabilistic outputs for support vector machines and comparisons to regularized likelihood methods[END_REF] and C4.5 decision tree [START_REF] Quinlan | C4. 5: programs for machine learning[END_REF] with an advantage to SVM in terms of prediction quality. This choice has been further confirmed in an extensive comparative study of the effect of single-label classifiers on problem transformation methods [START_REF] Read | Scalable multi-label classification[END_REF]. However, in this study, the computation time constraint was not critical (up to 24 hours). Here, due to the strong computation time constraint in our interactive learning framework, we have selected C4.5 decision tree for its lower computational complexity: unlike SVM, it only requires a selected number of features to build a predictive model.

Algorithm adaptation methods

In this second group, we select two adaptation methods. [START_REF] Zhang | Ml-knn: A lazy learning approach to multi-label learning[END_REF]) is a binary relevance method which combines the standard lazy learning algorithm kNN and the Bayesian inference. As a lazy learner, ML-kNN does not learn a model but only estimates the prior and posterior probabilities from the training data. For a new instance, it retrieves its k nearest examples and measures the frequency of each label in this neighborhood. It combines this frequency with the estimated probabilities and finally determines its label set from the maximum a posteriori principle. [START_REF] Cheng | Combining instance-based learning and logistic regression for multilabel classification[END_REF]) is an extension of MLkNN that combines instance-based learning and logistic regression. Unlike MLkNN, it allows to capture the potentially existing interdependencies between the labels: it uses the labels of neighbours as additional features in a meta logistic regression scheme. For a new instance, as a binary relevance approach, it combines the predictions of all learned models.

Multi-Label k Nearest Neighbours (ML-kNN)

Instance-Based learning as Logistic Regression for the Multi-Label case (IBLR_ML)

Ensemble methods

In this third group, we select four ensemble methods.

RAndom k-labELsets (RAkEL) [START_REF] Tsoumakas | Random k-labelsets: An ensemble method for multilabel classification[END_REF] generates an ensemble of LP classifiers. Each LP classifier is trained with a different random label subset of small size. For a new instance, RAkEL outputs the average vote on all models for each label.

Ensemble of Classifier Chains (ECC) and Ensemble of Binary Relevance

(EBR) [START_REF] Read | Classifier chains for multi-label classification[END_REF] are ensemble methods that use a bagging strategy with CC and BR respectively. For a new instance, ECC and EBR output the average votes on all models for each label, like RAkEL. [START_REF] Kocev | Ensembles of multi-objective decision trees[END_REF][START_REF] Kocev | Ensembles for predicting structured outputs[END_REF] is an ensemble method that uses Predictive Clustering Trees (PCTs) as base classifiers. PCTs use a standard top-down induction of decision trees. For diversity, classifiers are trained with a bagging strategy and by selecting a random subset of the feature set at each node of the trees. For a new instance, the predictions of all decision trees are summed using a distribution vote approach.

Random Forest of Predictive Clustering Trees (RF-PCT)

Comparative studies of multi-label learning algorithms

Experimental studies have evaluated the predictive performances of the different algorithms in different contexts. Table 1 recalls the results of the main publications where each study (Reference) is described by its number of classifiers (#Classifiers), number of datasets (#Datasets), number of evaluation criteria (#Criteria) and the set of recommended classifiers (Recommendation). Let us note that, in the quoted studies, the classifiers are always trained on a large number of examples, and that the computation time limitation is very loose (up to many days in some cases). The recent study of [START_REF] Madjarov | An extensive experimental comparison of methods for multi-label learning[END_REF] which stands out of the others for its comprehensiveness and extensiveness is our point of reference.

Problem statement

In this section, we first formally define the considered learning problem. Then, we precise the selected performance measures for the two main interactivity constraints: learning to generalize from a limited training set and learning and predicting in a very limited time.

Learning model

In the following, we consider a set

F = {f 1 , f 2 , . . . , f m } of m numerical features f i (dom(f i ) ∈ R)
, and a set D = {x 1 , x 2 , . . . , x n } of n unlabelled examples x i described by the m features (dom(x j ) ∈ R m ). At the beginning t 0 of the process, we assume that the user defines a set L t 0 = {λ 1 , λ 2 , . . . , λ q } of q desired labels λ i (dom(λ i ) ∈ {0, 1}) and that he selects a small set T t 0 of n 0 examples that he/she labels either positively or negatively. More precisely, let y i (dom(y i ) ∈ {0, 1} q ) be the binary vector which describes the labels given to an example x i : y j i = 1 (resp. 0) if the label λ j is positively (resp. negatively) associated to x i . The set T t 0 of the labelled examples can be defined by

T t 0 = {(x i , y i )| i = 1.
.n 0 and but we here restrict ourselves to the binary relevance case where the user provides a simple 'yes' (1) or 'no' (0) answer.

|y + i | + |y - i | = q}
From the multi-label training set T t 0 , a multi-label learning algorithm learns a predictive model h t 0 . The learned model predicts the most likely label set ŷi = h t 0 (x i ) for each selected

z : [0..1] q → {0, 1} q
is a threshold function that turns values greater than z into ones (1) or zeros (0) otherwise:

PCut = argmin z ∈ {0.00,0.001,...,1.00} 1 |T | |T | i=0 |y + i | - 1 |S| |S| i=0 |f z ( ŷi ) + |
This threshold method was mainly used for large training sets. However, we here assume that the average number of labels in a limited or a large training set is not significantly different.

Constraint 1 : Learning to generalize from a limited training set

From decision theory, it is well-known that users have a limited focus when it comes to making decisions [START_REF] Simon | A behavioral model of rational choice[END_REF]. Asking a user to provide a large number of examples to explain a desired concept is consequently a hard task which must be avoided. For the evaluation of the classifier efficiency with a limited training set, we consider five complementary measures relevant for the requirements that are considered in priority in multi-label learning applications: ranking labels by relevance, ranking examples by relevance and classifying labels. Moreover, we consolidate the obtained results with five additional measures classically used in the literature. Table 2 provides a summary of these evaluation criteria called quality criteria in the following. We describe them below.

Requirement 1: Ranking labels by relevance

In practice, users are mostly interested in a label ranking for a given example. Consequently, when an example is selected, the learning system must present its most likely labels at the top of the prediction list. To evaluate the classifier performances for ranking the example labels, we select a common criterion: Ranking Loss (RL). It is defined in the interval [0.

.1] and its lowest values indicate the best performances. RL measures the number of times where relevant and irrelevant labels are reversely ordered. Formally, let r i be a ranking function that sorts the labels of each example x i in descending order with respect to their prediction precision ŷi :

r i (λ a ) = k, k ∈ {1, 2, . . . , q}, if ŷa i is the k th larger value
among the ŷi values. The RL of a classifier on a test set S is defined by

RL = 1 |S| |S| i=1 1 |y + i | × |y - i | |(λ a , λ b ) ∈ y + i × y - i : r i (λ b ) < r i (λ a )|

Requirement 2: Ranking examples by relevance

Users can also be interested in an example ranking for one or a set of labels. Therefore, when a label or a combination of labels is selected, the learning system must present its .1] |S| ) be the real-valued vector which describes the prediction precisions associated with the examples x i ∈ S for the label λ i . Then, let r i be a ranking function that sorts each vector γi in descending order:

r i (x a ) = k, k ∈ {1, 2, . . . , |S|},
if γa i is the k th larger value among the γi values. The macro-RL of a classifier on a test set S is defined by

macro -RL = 1 |L| |L| i=1 1 |γ + i | × |γ - i | |(x a , x b ) ∈ γ + i × γ - i : r i (x b ) < r i (x a )|

Requirement 3: Label classification

As previously mentioned, a label ranking is essential in a multi-label learning system but a label classification may be sometimes desired. Consequently, when an example is selected, the learning system must only present its most likely labels. To evaluate the classifier performances to correctly classify the example labels, we select three criteria: Accuracy and F 1 -score and the multi-label Balanced Error Rate (BER). In [START_REF] Madjarov | An extensive experimental comparison of methods for multi-label learning[END_REF], the Accuracy and the F 1 -score criteria help to detect the best classifiers and the BER criterion is adapted when the evaluation datasets are unbalanced (e.g. Slashdot [START_REF] Read | Classifier chains for multi-label classification[END_REF]).

The Accuracy [START_REF] Godbole | Discriminative methods for multi-labeled classification[END_REF]) for a single example x i is defined by the Jaccard similarity coefficient between its ground truth y i and the predicted label set ŷi .

More precisely, it is defined by

Accuracy = 1 |S| |S| i=1 |y i ∩ ŷi | |y i ∪ ŷi |
The F 1 -score [START_REF] Spyromitros | An empirical study of lazy multilabel classification algorithms[END_REF][START_REF] Tsoumakas | Multi-label classification: An overview[END_REF]) is commonly used in information retrieval but it is also popular in multi-label classification. It is the harmonic mean between the precision and the recall criteria of each example x i :

F 1 -score = 1 |S| |S| i=1 2 × |y i ∩ ŷi | |y + i | + | ŷi + |
The BER [START_REF] Chen | Combining svms with various feature selection strategies[END_REF] has mostly been used to evaluate single-label predictions but we here adapt it for the evaluation of multi-label predictions. It is defined by the ratio of incorrectly classified labels per example where T P i , T N i , F P i and F N i are the number of respectively true positive, true negative, false positive and false negative labels of an example

x i : BER = 1 |S| |S| i=1 1 2 × F P i F P i + T N i + F N i F N i + T P i
All these criteria are defined in the interval [0..1] and their highest values indicate the best performances except for the BER criterion whose smallest value indicate the best performances.

Additional quality criteria

In a previous work on multi-label classification, [START_REF] Tsoumakas | Mining multi-label data[END_REF] have organized the quality criteria into two groups: (i) the ranking-based measures which compare the predicted label ranking with the ground truth label ranking and (ii) the bipartition-based measures which are based on the comparison of the predicted relevant labels with the ground truth relevant labels. In order to limit bias induced by quality criteria selection in the conclusion, we have added five well-known quality criteria from each group: (i) Coverage, One-error and Average precision and (ii) Hamming lost and Exact match. Criteria from (i) (resp. (ii)) contribute to the evaluation of the requirement 1 Section 3.2.1 (resp. requirement 3 Section 3.2.3). Their definitions are recalled in Appendix 2. Table 2: A summary of the selected criteria for the evaluation of the prediction quality.

Constraint 2 : Learning and predicting in a very limited time

In an interactive framework, the response of the learning system must be short: whenever a user adds new examples, the learning system must quickly adjust its current understanding and provide him/her with predictions as fast as possible. In Human-Computer Interaction, interactive systems are often required to provide users with a response in less than 100 ms [START_REF] Dabrowski | Is 100 milliseconds too fast?[END_REF]; as far as we know, this constraint is currently too strong here and we relax it to few seconds. For each classifier, we compute the number of seconds required to learn from a limited training data, and we predict labelsets of large test data. Obviously, we are aware that the computation time mainly depends on the implementation of the classifiers, and that the obtained results might only provide tendencies of their computational complexities.

Experimental setting

We first describe the experimental protocol proposed to evaluate the classifier performances in a simplified interactive context which allows classifier comparisons under the same conditions. Then, we present the twelve multi-label classification benchmark problems used for the evaluations and the chosen classifier parameters.

Experimental protocol

Evaluating the relevance of classifiers for an interactive environment is a complex task and, unfortunately, due to the novelty of this research field, there is still no standard or widely accepted framework to compare different approaches. In works presented in Section 2.1, the evaluation is mainly subjective: a small sample of users rated the quality of the developed systems for different tasks. Some authors additionally introduced "objective" measures (e.g. prediction accuracy, average trial time and learning speed). However, they This online learning approach is adapted for the beginning of the interaction where the model is more likely to change (i.e. concept-drift). In practice, users define their desired concepts mainly in real time while interacting with data and the learning system, and they mostly have no clear idea about the concepts they have in mind before the interaction starts (i.e. concept flexibility [START_REF] Amershi | Designing for effective end-user interaction with machine learning[END_REF]).

Data sets

We use twelve different multi-label classification benchmark problems most of which were selected in various previous studies. Our experimental corpus includes datasets with different scale from five different application domains (music, image, audio, biology, text). The basic statistics (Table 3) confirm that they cover a wide range of situations. In particular, their number of features varies from 71 to 49060 which allows to evaluate the classifier behaviours in a large scale, and the number of labels varies from 6 to 30 labels as users are mostly interested in a limited number of labels. The datasets are briefly described below.

Emotions [START_REF] Trohidis | Multi-label classification of music into emotions[END_REF] is a small dataset which describes pieces of music by 71 numerical features. They can be labelled with 6 possible emotions: sad-lonely, angryaggressive, amazed-surprised, relaxing-calm, quiet-still, and happy-pleased. Yeast [START_REF] Elisseeff | A kernel method for multi-labelled classification[END_REF]) is a biological dataset where genes are described by 103 numerical features. They can be associated with 14 biological functions. Scene [START_REF] Boutell | Learning multi-label scene classification[END_REF] is a dataset where images are described by 294 numerical features. They can be annotated with up to 6 concepts: beach, sunset, field, fall-foliage, mountain, and urban. Birds [START_REF] Briggs | The 9th annual mlsp competition: New methods for acoustic classification of multiple simultaneous bird species in a noisy environment[END_REF]) is a small dataset where 645 ten-second audio recordings of bird sounds are described by 260 numerical features. They can be labelled with up to 19 bird species.

Slashdot [START_REF] Read | Classifier chains for multi-label classification[END_REF]) is a sparse text dataset where documents are defined by 1079 binary features. They can be associated with 20 subject categories (e.g. linux, technology, science). IMDB [START_REF] Read | Classifier chains for multi-label classification[END_REF]) is a sparse dataset where movies are defined by 1001 binary features. They can be tagged with up to 28 genres (e.g. Romance, Comedy, Drama).

Genbase [START_REF] Diplaris | Protein classification with multiple algorithms[END_REF] is another microbiological dataset where genes are described with 1186 binary features. They can be associated with 27 biological functions.

TMC (Srivastava and The diversity of the data sets considered in our experimentation is confirmed by the distributions of three classical criteria which measure their « multi-labelled-ness » (see Table 3 for the numerical values):

1. Label Cardinality (LCard) is arguably the most common measure of multi-labelledness in the literature [START_REF] Tsoumakas | Multi-label classification: An overview[END_REF]. It evaluates the average number of labels associated with each example in a dataset D:

LCard(D) = 1 n n i=1 |y + i |
2. Label Density (LDens) relates to LCard, but takes into account the size of the label space. It is equal to the ratio of the average number of the example labels in a dataset D by the label number q (Tsoumakas and [START_REF] Tsoumakas | Multi-label classification: An overview[END_REF]:

LDens(D) = 1 n n i=1 |y + i | q = LC q 3.
IBLR_ML k = 1 MULAN ours HOMER k = 3 MULAN default CLR / MULAN / RF-PCT N = 100, m = 0.1 × |F | + 1 CLUS Kocev 2011
Table 4: The input parameters of each multi-label classifier where q is the number of labels, N is the number of base learners for the ensemble methods, m is the number of features selected at each node in RF-PCT, and k could be the number of label subsets, the size of label subsets or the number of neighbours respectively for HOMER, RAkEL and instance-based methods.

Experimental results I: learning from a limited training set

Tables 5-9 present the results obtained for the quality criteria defined in subsection 3.2.

The average performance of each classifier is given for each training data size (from 2 to 64).

The classifier predictive performances significantly improve as new training examples are provided, especially when the training data size is greater than 8 -except for the macro-RL.

Let us note that, unsurprisingly, they all struggle to learn from the smallest training sets of size 2 -which explains their very close poor performances-. Moreover, the differences between the classifier performances increase with the number of training examples. The differences are confirmed by a Friedman statistical test (with a 5% significance level) for all criteria but the BER criterion.

For the major quality criteria (RL and macro-RL), the ensemble method RF-PCT outperforms the other classifiers for all training data sizes (Tables 56). It is closely followed by EBR, CLR and MLkNN which belong to the three multi-label method families. The Nemenyi post-hoc analysis does not reveal any statistical difference between these classifiers.

The detailed results obtained for three representative training data sizes (4, 16 and 64 examples) show that the best classifiers remain the same whatever the dataset (see Appendix 1 -Tables .13 to .18); this is confirmed by a Friedman statistical test.

When considering the other quality criteria (Accuracy, F 1 -score and BER), the podium remains the same and RF-PCT remains the winner (Tables 7 and9). Let us recall that RF-PCT and CLR were already among the best multi-label classifiers for the RL, Accuracy The main conclusion is that the learning capabilities of the ensemble methods RF-PCT and EBR remain good whatever the training set size. Additional details are given bellow for each criterion.

Ranking Loss (RL)

A precise analysis places RF-PCT first for all training data sizes. It is followed by CLR, EBR and MLkNN which obtain very close performances with a very slight advantage to CLR intrinsically optimizes this criterion; this is confirmed by a Friedman statistical test. In contrast, BR and CC, which were favourite in [START_REF] Madjarov | An extensive experimental comparison of methods for multi-label learning[END_REF], loose their effectiveness for small training sets. Moreover, when the number of training examples increase, each classifier was able to improve its ranking performance -except HOMER which has also previously provided poor performances for large training data sets. It seems that HOMER is more adapted for domains with a large label number (hundreds and more) [START_REF] Tsoumakas | Effective and efficient multilabel classification in domains with large number of labels[END_REF].

Some remarks can also be drawn for the different classifier families. For the ensemble learning methods, EBR is better than a single BR, ECC is slightly better than a single CC and RAkEL1 slightly outperforms RAkEL 2 . For the problem transformation methods, CC does not outperform BR and they obtain very close performances as in [START_REF] Madjarov | An extensive experimental comparison of methods for multi-label learning[END_REF]. For the algorithm adaptation methods, MLkNN outperforms IBLR_ML and this result differs from previous results obtained by [START_REF] Cheng | Combining instance-based learning and logistic regression for multilabel classification[END_REF] Baseline 0, 39 ± 0, 13 0, 37 ± 0, 14 0, 35 ± 0, 14 0, 34 ± 0, 13 0, 34 ± 0, 13 0, 33 ± 0, 13 LP 0,34 ± 0,13 0, 34 ± 0, 11 0, 32 ± 0, 11 0, 30 ± 0, 11 0, 28 ± 0, 11 0, 26 ± 0, 11 CC 0,34 ± 0,13 0, 33 ± 0, 12 0, 31 ± 0, 11 0, 29 ± 0, 10 0, 26 ± 0, 11 0, 24 ± 0, 11 RAkEL1 0, 35 ± 0, 13 0, 34 ± 0, 12 0, 32 ± 0, 12 0, 29 ± 0, 11 0, 26 ± 0, 11 0, 24 ± 0, 11 RAkEL2 0, 35 ± 0, 12 0, 36 ± 0, 13 0, 34 ± 0, 13 0, 31 ± 0, 13 0, 28 ± 0, 13 0, 25 ± 0, 13 MLkNN 0,34 ± 0,13 0, 32 ± 0, 13 0, 28 ± 0, 11 0, 24 ± 0, 09 0, 20 ± 0, 08 0, 18 ± 0, 08 HOMER 0, 43 ± 0, 10 0, 41 ± 0, 11 0, 39 ± 0, 12 0, 38 ± 0, 13 0, 37 ± 0, 14 0, 35 ± 0, 15 IBLR-ML 0,34 ± 0,13 0, 32 ± 0, 13 0, 30 ± 0, 11 0, 26 ± 0, 10 0, 23 ± 0, 09 0, 20 ± 0, 08 CLR 0,34 ± 0,13 0,31 ± 0,13 0, 28 ± 0, 12 0, 24 ± 0, 10 0, 20 ± 0, 07 0, 17 ± 0, 07 ECC 0, 37 ± 0, 13 0, 33 ± 0, 13 0, 31 ± 0, 13 0, 28 ± 0, 13 0, 25 ± 0, 12 0, 22 ± 0, 11 BR 0,34 ± 0,13 0, 33 ± 0, 12 0, 31 ± 0, 11 0, 28 ± 0, 10 0, 25 ± 0, 10 0, 23 ± 0, 10 EBR 0,34 ± 0,13 0, 32 ± 0, 12 0, 28 ± 0, 11 0, 24 ± 0, 09 0, 20 ± 0, 07 0, 17 ± 0, 07 RF-PCT 0,34 ± 0,13 0,31 ± 0,12 0,27 ± 0,11 0,23 ± 0,08 0,18 ± 0,06 0,15 ± 0,06

Macro-averaged Ranking Loss (macro-RL)

To our knowledge, the ability of multi-label classifiers to correctly rank examples of each label has not yet been evaluated. Table 6 shows that the ensemble method RF-PCT is clearly the best for all training set sizes -except for the smallest size where all classifiers suffer. It is followed by the ensemble methods ECC and EBR. This is confirmed by a Friedman statistical test. However, when the size of the training set increases, all classifiers struggle to improve their predictions except RF-PCT. It seems that the multi-label learning algorithms inherently focus on the label ranking and do not consider the example ranking. Baseline 0,49 ± 0,02 0, 49 ± 0, 02 0, 49 ± 0, 02 0, 49 ± 0, 02 0, 49 ± 0, 02 0, 49 ± 0, 02 LP 0,49 ± 0,02 0, 48 ± 0, 02 0, 47 ± 0, 03 0, 45 ± 0, 04 0, 43 ± 0, 07 0, 41 ± 0, 08 CC 0,49 ± 0,02 0, 48 ± 0, 02 0, 47 ± 0, 02 0, 46 ± 0, 03 0, 44 ± 0, 05 0, 43 ± 0, 07 RAkEL1 0,49 ± 0,02 0, 48 ± 0, 02 0, 47 ± 0, 03 0, 44 ± 0, 05 0, 42 ± 0, 07 0, 39 ± 0, 09 RAkEL2 0,49 ± 0,02 0, 48 ± 0, 02 0, 47 ± 0, 03 0, 44 ± 0, 05 0, 42 ± 0, 08 0, 39 ± 0, 09 MLkNN 0,49 ± 0,02 0, 49 ± 0, 02 0, 47 ± 0, 03 0, 45 ± 0, 06 0, 43 ± 0, 08 0, 42 ± 0, 10 HOMER 0,49 ± 0,02 0, 48 ± 0, 02 0, 47 ± 0, 03 0, 45 ± 0, 05 0, 44 ± 0, 07 0, 43 ± 0, 08 IBLR-ML 0,49 ± 0,02 0, 49 ± 0, 02 0, 48 ± 0, 02 0, 47 ± 0, 04 0, 44 ± 0, 07 0, 42 ± 0, 11 CLR 0,49 ± 0,02 0, 48 ± 0, 02 0, 47 ± 0, 03 0, 45 ± 0, 05 0, 42 ± 0, 08 0, 38 ± 0, 10 ECC 0,49 ± 0,02 0, 48 ± 0, 02 0, 46 ± 0, 04 0, 43 ± 0, 07 0, 40 ± 0, 09 0, 38 ± 0, 10 BR 0,49 ± 0,02 0, 48 ± 0, 02 0, 47 ± 0, 02 0, 46 ± 0, 04 0, 44 ± 0, 06 0, 42 ± 0, 07 EBR 0,49 ± 0,02 0, 48 ± 0, 02 0, 46 ± 0, 04 0, 43 ± 0, 07 0, 40 ± 0, 09 0, 38 ± 0, 10 RF-PCT 0,49 ± 0,02 0,46 ± 0,03 0,43 ± 0,06 0,39 ± 0,09 0,35 ± 0,11 0,32 ± 0,12

Accuracy, F 1 -score and BER

As the ranking measures have priority in an interactive multi-label classification framework, we only retain the best classifiers according to RL and macro-RL to deepen our understanding of their behaviours with the other evaluation criteria (accuracy, F 1 -score, BER). For the accuracy and the F 1 -score (Tables 7 and8), RF-PCT is still the most efficient for all training set sizes except for the smallest training set size where CLR is more efficient. Nemenyi post-hoc tests confirm that RF-PCT is significantly better than MLkNN for the F 1 -score and the Accuracy. However, for the BER criterion ( MLkNN 0, 17 ± 0, 10 0, 20 ± 0, 10 0, 24 ± 0, 11 0, 28 ± 0, 13 0, 31 ± 0, 13 0, 33 ± 0, 16 CLR 0,19 ± 0,10 0, 21 ± 0, 11 0, 24 ± 0, 12 0, 26 ± 0, 12 0, 30 ± 0, 12 0, 34 ± 0, 13 EBR 0, 18 ± 0, 10 0, 20 ± 0, 10 0, 26 ± 0, 11 0, 30 ± 0, 13 0, 33 ± 0, 14 0, 38 ± 0, 16 RF-PCT 0, 18 ± 0, 10 0,24 ± 0,12 0,28 ± 0,13 0,33 ± 0,12 0,39 ± 0,13 0,44 ± 0,17 MLkNN 0, 22 ± 0, 14 0, 27 ± 0, 13 0, 32 ± 0, 14 0, 36 ± 0, 15 0, 40 ± 0, 16 0, 42 ± 0, 18 CLR 0,26 ± 0,14 0, 28 ± 0, 15 0, 31 ± 0, 15 0, 35 ± 0, 15 0, 40 ± 0, 15 0, 43 ± 0, 15 EBR 0, 24 ± 0, 13 0, 27 ± 0, 13 0, 33 ± 0, 14 0, 37 ± 0, 15 0, 40 ± 0, 16 0, 45 ± 0, 18 RF-PCT 0, 24 ± 0, 14 0,29 ± 0,14 0,34 ± 0,15 0,39 ± 0,14 0,45 ± 0,15 0,51 ± 0,17 MLkNN 0, 40 ± 0, 10 0, 38 ± 0, 10 0,34 ± 0,10 0,31 ± 0,10 0, 28 ± 0, 10 0, 27 ± 0, 11 CLR 0,38 ± 0,11 0,37 ± 0,10 0,34 ± 0,10 0, 32 ± 0, 09 0,28 ± 0,09 0, 26 ± 0, 09 EBR 0, 39 ± 0, 10 0,37 ± 0,09 0,34 ± 0,10 0, 32 ± 0, 10 0, 30 ± 0, 10 0, 28 ± 0, 10 RF-PCT 0, 39 ± 0, 10 0,37 ± 0,09 0, 35 ± 0, 09 0, 32 ± 0, 08 0,28 ± 0,08 0,25 ± 0,09 Let us note that our conclusions are consolidated by the results obtained for the additional quality criteria introduced in Section 3.2.4 (see Appendix 2). The best results are still overall obtained by the ensemble methods RF-PCT and EBR (see Tables .19-.23).

Experimental results II: Learning and Predicting in a limited time

Tables 10 and11 present the average number of seconds measured for testing and training the classifiers. For the prediction time, four classifiers stand out of the rest of classifiers:

two ensemble methods RF-PCT and RAkEL 1 and two problem transformation methods LP and HOMER. For the training time, three problem transformation methods LP, CC and BR obtain good performances. They are followed by the ensemble method RF-PCT. If the observed training times are globally consistent with the theoretical computational complexities (Table 12), the observed prediction times are more surprising. In particular, RF-PCT, which requires hundred decision trees for the prediction, was expected to be less efficient than LP, HOMER and RAkEL 1 which require a smaller set of decision trees. Moreover, the positive correlation between the prediction time increasing with the number of training examples is only checked for the adaptation methods MLkNN and IBLR_ML.

These amazing experimental results may be partly explained by the coding quality heterogeneity of the algorithms which come from three different libraries (MULAN, MeKA, CLUS). Here, we have followed the previous comparisons in the literature by using the wellknown libraries of the community. A coding standardization will be necessary in the future for further analysis but this discussion opens questions that go far beyond the objective of this paper. Nevertheless, combining the theoretical complexity and the experimental results, we suggest to retain the problem transformation methods LP, BR and CC and the ensemble method RF-PCT which is efficient with the code provided in CLUS. Baseline 0, 00 ± 0, 00 0, 00 ± 0, 00 0, 00 ± 0, 00 0, 00 ± 0, 00 0, 00 ± 0, 00 0, 00 ± 0, 00 LP 0,04 ± 0,05 0,05 ± 0,06 0,07 ± 0,09 0,13 ± 0,17 0,37 ± 0,46 1,25 ± 1,52

Conclusion and Future work

Integrating multi-label classification in an interactive framework is a promising research area which has recently been stimulated by real-life applications from various domains. In the last decade, numerous multi-label classification approaches have been developed. But a major question is the selection of an algorithm which resists the interactivity constraints.

To the best of our knowledge, this paper presents the first extensive comparative study of multi-label learning algorithms in an interactive setting. We have compared twelve sifiers that obtain poor predictive performances. Consequently, we conclude that RF-PCT, which was already distinguished for the classical multi-label classification [START_REF] Madjarov | An extensive experimental comparison of methods for multi-label learning[END_REF], still remains efficient for an interactive multi-label classification.

In the next future, we plan to follow two complementary research directions: (i) improving the best approaches, in particular RF-PCT and CLR, by exploiting the structure of the unclassified data, and (ii) complexifying our experimental protocol. When the training data size is limited, it is commonly argued that the information induced from unclassified data enables learners to significantly improve their predictive performance [START_REF] Chapelle | Semi-supervised learning[END_REF]. We first want to extend our classifier comparison by confronting the best learners of this actual study to existing semi-supervised multi-label learning approaches (e.g. [START_REF] Liu | Semi-supervised multi-label learning by constrained non-negative matrix factorization[END_REF] and [START_REF] Kong | Transductive multilabel learning via label set propagation[END_REF]). Our ambition is to better understand the contribution of this added information to develop a more efficient interactive multi-label classification algorithm.

In this study we have identified the classifiers which satisfy the main constraints of any interactive environment. The next step is to analyse their behaviours in a more realistic framework by simulating user selection/correction and user addition of new labels of interest.

We are currently developing a prototype of an interactive learning system for the Video On Demand and we will soon conduct a subjective user evaluation of the system with each of the top classifiers.

Appendix 2

Definitions of the additional quality criteria and the obtained results are given below.

Additional quality criteria

The Hamming Loss evaluates the number of misclassified labels for an example x i :

Hamming -Loss = 1 |S| |S| i=1 |y i ŷi |
where is the symmetric difference between its ground truth and predicted label sets (y i and ŷi ).

The Exact match is a very strict criterion as it harshly punishes the model predictions.

It requires an exact match between the ground truth label set y i and the predicted label set ŷi for an example x i :

Exact match = 1 |S| |S| i=1 I[y i = ŷi ]
where I(true)=1 and I(false)=0.

The Coverage evaluates how many steps are required, on average, to go down the ranked label list so as to cover all the relevant labels of an example x i :

Coverage = 1 |S| |S| i=1 max λ j ∈y + i r i (λ j ) -1
The One error evaluates how many times the top-ranked label is not relevant for an example x i ;

One MLkNN 0, 73 ± 0, 20 0, 68 ± 0, 23 0,60 ± 0,22 0,54 ± 0,23 0,50 ± 0,25 0, 48 ± 0, 26 CLR 0,69 ± 0,22 0, 66 ± 0, 23 0, 62 ± 0, 23 0, 58 ± 0, 22 0, 52 ± 0, 22 0, 48 ± 0, 23 EBR 0, 72 ± 0, 19 0, 67 ± 0, 21 0,60 ± 0,22 0, 55 ± 0, 23 0, 51 ± 0, 24 0, 47 ± 0, 24 RF-PCT 0, 72 ± 0, 19 0,65 ± 0,22 0, 61 ± 0, 23 0, 56 ± 0, 22 0,50 ± 0,21 0,45 ± 0,23 MLkNN 0,19 ± 0,12 0, 20 ± 0, 12 0, 17 ± 0, 11 0, 15 ± 0, 10 0, 14 ± 0, 09 0, 13 ± 0, 08 CLR 0,19 ± 0,12 0, 18 ± 0, 12 0, 16 ± 0, 11 0, 16 ± 0, 10 0, 14 ± 0, 09 0, 13 ± 0, 08 EBR 0,19 ± 0,12 0, 20 ± 0, 11 0, 16 ± 0, 10 0, 14 ± 0, 09 0, 13 ± 0, 08 0, 12 ± 0, 08 RF-PCT 0,19 ± 0,12 0,16 ± 0,11 0,14 ± 0,10 0,13 ± 0,08 0,11 ± 0,07 0,10 ± 0,07 MLkNN 0, 42 ± 0, 16 0, 45 ± 0, 16 0,52 ± 0,15 0,57 ± 0,16 0, 60 ± 0, 17 0, 63 ± 0, 18 CLR 0,44 ± 0,16 0,47 ± 0,17 0, 50 ± 0, 16 0, 54 ± 0, 15 0, 59 ± 0, 15 0, 63 ± 0, 16 EBR 0, 42 ± 0, 16 0, 46 ± 0, 16 0,52 ± 0,16 0, 56 ± 0, 16 0, 60 ± 0, 17 0, 63 ± 0, 17 RF-PCT 0, 43 ± 0, 16 0,47 ± 0,16 0,52 ± 0,16 0, 56 ± 0, 15 0,62 ± 0,15 0,66 ± 0,16 MLkNN 0, 04 ± 0, 03 0, 04 ± 0, 03 0, 06 ± 0, 05 0, 06 ± 0, 05 0, 07 ± 0, 05 0, 09 ± 0, 09 CLR 0,05 ± 0,03 0, 04 ± 0, 03 0, 05 ± 0, 04 0, 04 ± 0, 04 0, 06 ± 0, 04 0, 08 ± 0, 05 EBR 0, 04 ± 0, 03 0, 04 ± 0, 04 0, 10 ± 0, 07 0, 13 ± 0, 11 0, 16 ± 0, 12 0, 20 ± 0, 13 RF-PCT 0,05 ± 0,03 0,10 ± 0,08 0,13 ± 0,09 0,17 ± 0,11 0,21 ± 0,14 0,26 ± 0,18

Figure 1 :

 1 Figure 1: Interactive classification of a VoD catalogue (a toy example).

  where |y + i | and |y - i | are respectively the number of positive and negative labels of x i . Gradual relevance can be used to label the examples (e.g. (Cheng et al., 2010))

  example x i ∈ S ⊂ D where S is a test set with |S| >> |T t 0 |. If the predictions provided by the model do not align well with the user's preferences, he/she can boost the predictive performance by correcting the mistakes or adding few more examples and the learning process is run again. In our proposed experimental protocol (see subsection 4.1), we do not simulate the user selection and correction. We restrict ourselves to the evaluation of the classifier predictive and time-computation performances while new examples are provided.Generally, the multi-label learning algorithms predict a vector of real-valued confidence outputs. To transform these real values into binary ones, a threshold function is needed. We here use a fast and effective threshold method Pcut (Proportional Cut Method) introduced in[START_REF] Read | Scalable multi-label classification[END_REF]). It chooses the z value which minimizes the label cardinality difference between the training data set T and the classified test data set S where f

  most likely examples at the top of the prediction list. To evaluate the classifier performances for ranking the label examples, we have adapted the RL definition and we define the macroaveraged Ranking-Loss criterion (macro-RL) which measures the number of times that relevant and irrelevant examples are reversely ordered. As for the RL definition, macro-RL is defined in the interval [0..1] and its lowest values indicate the best performances. Formally, let |γ + i | and |γ - i | be respectively the number of positive and negative examples associated with the label λ i . Let γi (dom( γi ) ∈ [0.

  only considered just one or a very restricted set of classification algorithms -often chosen without solid arguments-and few datasets -often one only-. The experimental evaluations closely depend on the chosen targeted use cases and the interface characteristics. The significance of their conclusions is consequently limited. To draw general conclusions helpful for guiding the choice of a suitable classifier during the development of an interactive multi-label classification system, we use a simplified simulation where the training sets regularly increase while staying small. The objective is to detect the classifiers which are able to "continuously" learn well with very limited training sets in a reasonable time. More precisely, we focus on the beginning of the classification task where few examples (from 2 to 64 examples) are available. In practice, this phase is crucial for catching the user interest and confidence in the system. To avoid bias in the comparisons, all the classifiers are trained with the same training examples. The principle of the experimental protocol is the following. Each dataset is divided into a small training set and a large test set. From each training set, training subsets of restricted sizes are successively created such that each one fits into the other. Thereafter, each classifier is trained with the nested data subsets and its performances are evaluated for each training data subset size on the same test set. This process allows to precisely follow the evolution of the classifier performances while the training set grows. It is repeated several times as precisely described below. 1. Divide each dataset D into 5 distinct folds. Use each fold for training (T = 20% of D)and the 4 remaining folds for testing (S = 80% of D). In total, there are 5 sets T i (i = 1 to 5) for training and 5 sets S i (i = 1 to 5) for testing (i.e. 5 cross-validation). 2. From each training set T i (1≤i≤5) , extract s sets of p nested training subsets of size 2 1 , 2 2 , . . . to 2 p . 3. Associate each classifier with the 5 × s × p training subsets of all folds (5 × s training data sets for each size). For each training subset size and for each criterion, evaluate its average performance for the 5 test sets. Then, average on all datasets.For all the experiments, s was fixed to 10 and p to 6, which corresponds to a number of 300 train-test evaluations for the 5-cross validation. The threshold (p = 6) is consistent with real-life experiments. From our practical experience, we have observed that users do not annotate more than 64 examples by themselves without any assistance of a learning algorithm.

  Zane-Ulman, 2005) is a sparse text dataset of flight readiness and discrepancy reports. It is described by 49060 binary features. The reports can be associated with up to 22 labels representing the problems being described. The four remaining text datasets (Arts, Business, Health and Computers) are web pages collected through the hyperlinks from Yahoo!'s top directory. Each data set is associated with four of Yahoo!'s top categories ("Arts & Humanities", "Business & Economy", "Computers & Internet", "Health"), and each page is labelled with one or more second level subcategories. In these four datasets, the minimum (maximum) values of |L| and |F| are 24 (30) and 21924 (34096), respectively.

and F 1

 1 -score criteria in the extensive study of[START_REF] Madjarov | An extensive experimental comparison of methods for multi-label learning[END_REF] which does not take the interactive constraints into account. In the previous study, EBR was not evaluated and MLkNN only performed well for the RL criterion with poor results for the Accuracy and the F 1 -score. The critical diagrams obtained from the statistical tests (Friedman and Nemenyi post-hoc) for the main quality criteria are given in Appendix 3 (Figures .2-.4).

  well-established multi-label learning algorithms from three families (problem transformation methods, adaptation methods, ensemble methods) for twelve datasets of different sizes from various domains. The quality of their predictions was evaluated for five complementary multi-label criteria: ranking-based criteria for the labels and the examples (RL and macro-RL), Accuracy, F 1 -score and Balanced Error Rate (BER)). For strengthening our conclusions, we have considered five additional measures from the literature: Coverage, One Error, Average Precision, Hamming Loss and Exact match. Their computation efficiency is basically evaluated by some observed running times and by their theoretical computational complexities for both training and predicting. Our analysis is focused on the first phase of the classification task where only few training examples are available. In practice, this phase is essential to gain user confidence in the interactive system.Our comparison shows that four classifiers can be distinguished for the prediction quality: RF-PCT (Random Forest of Predictive Clustering Trees), EBR (Ensemble of Binary Relevance), CLR (Calibrated Label Ranking) and MLkNN (Multi-label kNN) with an advantage for the first two ensemble classifiers. Moreover, RF-PCT also competes with the fastest clas-

  average performances of each classifier for all training sets of size 4 of each dataset in terms of the Ranking Loss criterion average performances of each classifier for all training sets of size 16 of each dataset in terms of the Ranking Loss criterion average performances of each classifier for all training sets of size 64 of each dataset in terms of the Ranking Loss criterion average performances of each classifier for all training sets of size 4 of each dataset in terms of the macro-averaged Ranking Loss criterion average performances of each classifier for all training sets of size 16 of each dataset in terms of the macro-averaged Ranking Loss criterion

Figure . 2 :

 2 Figure .2: The critical diagram for the Ranking loss criterion for all training data sizes.

Figure . 3 :Figure . 4 :

 34 Figure .3: The critical diagram for the macro-averaged Ranking loss criterion for all training data sizes.

Table 1 :

 1 The most relevant experimental studies of multi-label learning algorithms.

	Reference	#Classifiers	#Criteria	#Datasets	Recommendation
	(Li et al., 2006)	6	9	2	BR and ML_ADTree 1
	(Nasierding and Kouzani, 2012)	7	4	8	TREMLC 2 , MLkNN and BR
	(Madjarov et al., 2012)	12	16	11	RF-PCT, HOMER, BR and CC
	(Tawiah and Sheng, 2013)	6	5	11	MLkNN, RAkEL, CC and BR

Table 3 :

 3 LDens values are mostly very low because labelling is usually very sparse except for Emotions and Yeast where 30% of the labels are associated on average with each example. The low values of PUniq indicate that the labelling is generally regular except for IMDB and TMC where more than 20% of the examples are associated with unique labelsets MeKA 3 , MULAN 4 and CLUS 5 .

	In our selected evaluation datasets, LCard values are mostly smaller than 2.0 except
	for Yeast where examples are associated in average with more than 4.0 labels. Indeed, the
	low label cardinality is common to textual and multi-media data where most examples are
	associated with a single-label, and the "multi-labelled-ness" has only been used to avoid
	ambiguities.

Proportion of Unique label combinations (PUniq) is a new measure of multilabelled-ness which was recently introduced by (Read, 2010). It indicates the regularity or uniformity of the labelling scheme. Precisely, it evaluates the proportion of label sets which are unique across the total number of examples in a dataset D: P U niq(D) = |y i |∃! x i : (x i , y i ) ∈ D| n Basic statistics of the selected multi-label benchmarks (|F|: number of features, |D|: number of examples, |L|: number of labels, LCard: Label Cardinality, PUniq: Proportion of Unique label combinations,

Table 5 :

 5 The average performances of each classifier for each training set size for the Ranking Loss criterion (RL).

Table 6 :

 6 The average performances of each classifier for each training set size for the macro-averaged Ranking Loss criterion (macro-RL).

Table 9

 9

	), the classifiers

Table 7 :

 7 The average performances of the top(4) classifiers for each training set size for the Accuracy criterion.

	2	4	8	16	32	64

Table 8 :

 8 The average performances of the top(4) classifiers for each training set size for the F 1 -score criterion.

	2	4	8	16	32	64

Table 9 :

 9 The average predictive performance of the top(4) classifiers for each training set size for the BER criterion.

Table 10 :

 10 The average prediction times of each classifier for each training set size (in seconds).

	2	4	8	16	32	64

Table 11 :

 11 The average training times of each classifier for each training set size (in seconds).

	28

Table 12 :

 12 The computational complexities of each classifier for both training and predicting in terms of number of training examples (n), number of features (m) and number of labels (q). N is the number of base learners for the ensemble methods. C(.) is the computational complexity of the balanced clustering algorithm. k could be the number of label subsets, the size of label subsets or the number of neighbours respectively for HOMER, RAkEL and instance-based methods. m is the number of features selected at each node in RF-PCT. And, h B (.) (resp. h M (.)) and h B (.) (resp. h M (.)) denote the training and perinstance testing computational complexities of the binary (resp. multi-class) base learner B (resp. M ) used in problem transformation approaches.

  Table .18: The average performances of each classifier for all training sets of size 64 of each dataset in terms of the macro-averaged Ranking Loss criterion

  The Average precision evaluates the average fraction of labels λ k ∈ y + i ranked above a label λ j ∈ y + i for an example x i :

		AverageP recision =	1 |S|	|S| i=1	1 |y + i |	i λ j ∈y +	|w i | r i (λ j )
	where w i = {λ k |r k i ≤ r j i , λ k ∈ y + i }
	2. Experimental results
	2	4	8				16	32	64
		-Error =	1 |S|	|S| i=1	argmax i λ j ∈y +	ŷj i / ∈ y i

  Table .19: The average performances of the top(4) classifiers for each training set size for the One-error criterion.

	2	4	8	16	32	64

  Table .20: The average performances of the top(4) classifiers for each training set size for the Hamming loss criterion.

	2	4	8	16	32	64

  Table .21: The average performances of the top(4) classifiers for each training set size for the Average precision criterion.

	2	4	8	16	32	64

  Table .22: The average performances of the top(4) classifiers for each training set size for the Exact match criterion.

		2	4	8	16	32	64
	MLkNN	8, 32 ± 3, 92	7, 74 ± 3, 35	6, 89 ± 2, 81	6, 04 ± 2, 48	5, 33 ± 2, 36	4, 79 ± 2, 32
	CLR	8,26 ± 3,93 7,61 ± 3,34	6, 89 ± 2, 76	6, 13 ± 2, 42	5, 41 ± 2, 29	4, 80 ± 2, 31
	EBR	8, 30 ± 3, 92	7, 66 ± 3, 31	6, 91 ± 2, 85	6, 17 ± 2, 65	5, 46 ± 2, 57	4, 91 ± 2, 54
	RF-PCT	8, 31 ± 3, 92	7, 62 ± 3, 32	6,81 ± 2,78 5,94 ± 2,47 5,12 ± 2,36	4,48 ± 2,38

  Table .23: The average performances of the top(4) classifiers for each training set size for the Coverage criterion.

meka.sourceforge.net

mulan.sourceforge.net

dtai.cs.kuleuven.be/clus

Acknowledgement

We thank anonymous reviewers whose critical feedback and valuable suggestions have helped to improve and clarify the manuscript.

Appendix 1

The detailed results obtained for three representative training data sizes (4, 16 and 64 examples) for the main quality criteria (Ranking Loss and macro-averaged Ranking Loss) are presented below.

Appendix 3: Critical diagrams

The critical diagram represents a projection of the classifier average ranks on an enumerated axis. The classifiers are placed from left (best) to right (worst) and a bold line connects those whose average ranks do not differ significantly (for the significance level 0.05).