Vu-Linh Nguyen
email: vu.linh.nguyen@uni-paderborn.de

Sébastien Destercke
email: sebastien.destercke@hds.utc.fr

Marie-Hélène Masson
email: mmasson@hds.utc.fr

Rashad Ghassani
email: rashad.ghassani@gmail.com

Racing trees to query partial data

Keywords: partial data, data querying, active learning, racing algorithms, decision trees

Dealing with partially known or missing data is a common problem in machine learning. This work is interested in the problem of querying the true value of data to improve the quality of the learned model, when those data are only partially known. This study is in the line of active learning, since we consider that the precise value of some partial data can be queried to reduce the uncertainty in the learning process, yet can consider any kind of partial data (not only entirely missing one). We propose a querying strategy based on the concept of racing algorithms in which several models are competing. The idea is to identify the query that will help the most to quickly decide the winning model in the competition. After discussing and formalizing the general ideas of our approach, we study the particular case of decision trees in case of interval-valued features and setvalued labels. The experimental results indicate that, in comparison to other baselines, the proposed approach significantly outperforms simpler strategies in the case

Introduction

Classical learning schemes assume that every instance is fully specified, yet there are many cases where such an assumption is unlikely to hold, and where some features or the label (class) of an instance may be only partially known. Such situations are commonly encountered in various fields, such as biostatistics [START_REF] Heitjan | Ignorability and coarse data: Some biomedical examples[END_REF], agronomy [START_REF] Lagacherie | A spatial approach using imprecise soil data for modelling crop yields over vast areas[END_REF], or economy [START_REF] Mcdonald | On using interval response data in experimental economics[END_REF]. These data can be generated by coarse or censored measurements (see e.g., [START_REF] Efron | Censored data and the bootstrap[END_REF]), anonymization techniques [START_REF] Dobra | Bounds for cell entries in contingency tables given marginal totals and decomposable graphs[END_REF], or can be obtained from expert opinions.

Multiple solutions have been proposed to deal with such problems. A first solution is to try to automatically complete the data by imputing their values [START_REF] Rubin | Inference and missing data[END_REF][START_REF] Farhangfar | Impact of imputation of missing values on classification error for discrete data[END_REF][START_REF] Lobato | Multi-objective genetic algorithm for missing data imputation[END_REF]. A second one is to adapt learning methods so that they can integrate directly imprecise data [START_REF] Xia | Adjusted weight voting algorithm for random forests in handling missing values[END_REF]. This latter approach has recently gained an increasing attention, both from the theoretical perspective [START_REF] Hüllermeier | Learning from imprecise and fuzzy observations: Data disambiguation through generalized loss minimization[END_REF][START_REF] Liu | Learnability of the superset label learning problem[END_REF][START_REF] Cabannnes | Structured prediction with partial labelling through the infimum loss[END_REF]) and the practical one [START_REF] Zhang | Partial label learning via feature-aware disambiguation[END_REF][START_REF] Utkin | An imprecise extension of svm-based machine learning models[END_REF], with applications in different fields like image or natural language processing [START_REF] Cour | Learning from partial labels[END_REF][START_REF] Cour | Learning from ambiguously labeled images[END_REF]. However, in both cases the imprecision in the data usually leads to less accurate models, which in turn can lead to wrong decisions. It is therefore desirable, if possible, to reduce this imprecision in meaningful and efficient ways, to obtain the best possible model. This work explores this particular issue: if we have the possibility to gain more information on some of the partial instances, which instance and what feature of this instance should we query to increase the final quality of the learned model? In the case of a completely missing label (and to a lesser extent of missing features), this problem is known as active learning and has already been largely treated [START_REF] Settles | Active learning literature survey[END_REF][START_REF] Ma | Online active learning of decision trees with evidential data[END_REF]. However, except for some recent works focusing on k-nn models [START_REF] Nguyen | Querying partially labelled data to improve a k-nn classifier[END_REF], we are not aware of such works for generic partial data. Moreover, we also deal with the problem of partially specified features (i.e., issued from an unreliable sensor, from expert opinions), a problem that to our knowledge has never been treated in an active learning setting (the problem of completely missing features itself has received much less attention (Settles, 2009, Sec. 5.2.)).

While it may not always be possible to perform such a querying of partial data, we can think of many situations where it would be possible. This will be typically the case when cheap rough measurements can be complemented with a limited number of precise yet costly ones. For instance, coarse satellite images [START_REF] Prince | A model of regional primary production for use with coarse resolution satellite data[END_REF] or expert opinions (e.g., of building features to detect problems [START_REF] Feng | Deep active learning for civil infrastructure defect detection and classification[END_REF]) can be enriched by selected field measurements. In medicine, data issued from general health checks can be made more precise by asking for complementary exams.

In this paper, we propose to apply an approach [START_REF] Nguyen | Partial data querying through racing algorithms[END_REF] inspired from the idea of racing algorithms [START_REF] Maron | The racing algorithm: Model selection for lazy learners[END_REF], initially used to statistically select an optimal configuration of a given lazy learning model, and since then applied to other settings such as multi-armed bandits [START_REF] Busa-Fekete | Preference-based reinforcement learning: evolutionary direct policy search using a preference-based racing algorithm[END_REF]. The idea of such racing algorithms is to oppose a (finite) set of alternatives in a race, and to progressively discard losing ones as the race goes along. In our case, the set of alternatives will be different possible models. As the data is partial, the performance of each model is uncertain and several candidate models can be optimal. The race will consist in iteratively making queries, i.e. in asking to an oracle the precise value of a partial data.

The key question is then to identify those data that will help the most to reduce the set of possible winners in the race and to converge quickly to the optimal model, hence those data that help the most in differentiating bad from good models. Provided the set of alternatives is rich and diverse enough, this should help in improving the quality of the model finally learned from the updated data.

We investigate how this general approach can be applied to decision tree classifiers [START_REF] Quinlan | Induction of decision trees[END_REF][START_REF] Safavian | A survey of decision tree classifier methodology[END_REF]. Decision trees are well-known to be sensitive to changes in the data, hence the importance of querying meaningful data for such classifiers. We show that detecting the data to query in our method can be done efficiently for decision trees when either the labels or the features are imprecise.

As the paper provides many algorithmic as well as mathematical results, we now provide a detailed description of the article contents to help the reader to navigate through it:

-Section 2 provides the necessary notations and preliminaries to understand the paper content; -Section 3 provides a generic description of the racing approach we intend to apply in this paper, that was previously described and applied to SVM in [START_REF] Nguyen | Partial data querying through racing algorithms[END_REF]. In particular, Algorithm 1 provides a generic description of our partial data querying method, applicable to any learning method. Although its reading is not absolutely necessary to understand the peculiar application to decision trees, it is useful to get the general ideas of our approach; -Section 4 investigates how our general approach can be applied to decision trees when output labels are partially known and features precisely known. The first part of the section, up to Section 4.4, describes the formal elements and properties used to implement the querying method. Section 4.4 then provide details about the algorithmic implementation, in which Algorithm 2 provides the details of a single query, and refer to specific algorithms used in each step of the process; -Section 5 investigates how our general approach can be applied to decision trees when features are partially known, which turns out to be trickier to handle than partial labels. Again, the first part (up to Section 5.4) provides formal justification of the algorithmic procedures. Section 5.4 then provides details about the algorithmic implementation, with Algorithm 7 being central and describing a general query, with reference to sub-routines to be used within the process; -Finally, some experiments are performed on different data sets in Section 6, showing that our method is particularly interesting in the case where features are imprecisely known.

As the paper can get heavy in terms of notations, Table 1 summarizes the main notations and indices used in the paper.

Preliminaries

In classical supervised setting, the goal of the learning approach is to find a model m : X → Y within a set M of models from a data set D = {(x n , y n )} N n=1 ⊂ X × Y of N input/output samples, where X and Y are respectively the input and the output spaces1 . The empirical risk R(m) associated to a model m is evaluated as

R(m) = N n=1 (y n , m(x n )) , (1)
where : Y ×Y → R is the loss function, and (y, m(x)) is the loss of predicting m(x) when observing y. The selected model is then the one that minimizes (1), that is

m * = arg min m∈M R(m) . (2)
Another way to see the model selection problem is to assume that a model m l is said to be better than

m k (denoted m l m k ) if R(m k ) -R(m l ) > 0 , (3)
or, in other words, if the risk of m l is lower than the risk of m k .

In this work, we are interested in a more general case where data is potentially only partially known, that is where general samples are of the kind (X n , Y n ) ⊆ X ×Y. In such a case, Equations (1), ( 2) and (3) are no longer well-defined, and there are different ways to extend them. Two of the most common ways to extend them is either to use a minimin (optimistic) [START_REF] Hüllermeier | Learning from ambiguously labeled examples[END_REF] or a minimax (pessimistic) approach [START_REF] Guillaume | Maximum likelihood with coarse data based on robust optimisation[END_REF]. That is, if we extend Equation (1) to a lower bound R(m) and an upper bound R(m) such that

R(m) = inf (xn,yn)∈(Xn,Yn) N n=1 (y n , m(x n )) = N n=1 inf (xn,yn)∈(Xn,Yn) (y n , m(x n )) := N n=1 (Y n , m(X n )) , (4)
R(m) = sup (xn,yn)∈(Xn,Yn) N n=1 (y n , m(x n )) = N n=1 sup (xn,yn)∈(Xn,Yn) (y n , m(x n )) := N n=1 (Y n , m(X n )) , (5)
then the optimal minimin m * mm and minimax m * mM models are

m * mm = arg min m∈M R(m) , (6)
m * mM = arg min m∈M R(m) . (7)
The minimin approach usually assumes that data are distributed according to the model, and tries to find the best data replacement (or disambiguation) combined with the best possible model [START_REF] Hüllermeier | Learning from imprecise and fuzzy observations: Data disambiguation through generalized loss minimization[END_REF].

Conversely, the minimax approach assumes that data are distributed in the worst possible way, and selects the model performing the best in the worst situation, thus guaranteeing a minimum performance of the model [START_REF] Guillaume | Maximum likelihood with coarse data based on robust optimisation[END_REF]. However, such an approach, due to its conservative nature, may lead to sub-optimal models. When having to choose a preferred model in the race, we will follow the optimistic approach, that is also in line with the idea of racing algorithms. For a deeper discussion on the differences between the optimistic and pessimistic approaches, we refer to [START_REF] Hüllermeier | Learning from imprecise data: adjustments of optimistic and pessimistic variants[END_REF]. However, in this paper, we are not primarily interested into learning a single model from partial data, but want to determine which partial data makes the potentially best models incomparable, in order to complete such data through query. To define such a set of potentially optimal models,we will say that a model m l is better than

m k (still denoted m l m k ) if R(m k-l ) = inf (xn,yn)∈(Xn,Yn) R(m k ) -R(m l ) > 0 , (8)
which is a direct extension of Equation (3). That is, m l m k if and only if it is better under every possible precise instances (x n , y n ) consistent with the partial instances (X n , Y n ). Such an approach is similar to decision rules used, for instance, in imprecise probability [START_REF] Troffaes | Decision making under uncertainty using imprecise probabilities[END_REF]. We can then denote by

M * = {m ∈ M : ∃m ∈ M s.t. m m} (9)
the set of undominated models within M, that is the set of models that are maximum with respect to the partial order .

X 2 X 1 1 2 3 4 5 m 2 m 1 R(m 1 ) = 0, R(m 1 ) = 5 R(m 2 ) = 1, R(m 2 ) = 3 R(m 1-2 ) = -1 R(m 2-1 ) = -2
Fig. 1 Illustration of partial data and competing models

Example 1 Figure 1 illustrates a situation where Y consists of two different classes (gray and white), and X of two dimensions. Only imprecise data are numbered.

Squares are assumed to have precise features. Points 1, 2 and 3 are imprecise with respect to their second feature. Shaded squares (points 4 and 5) have unknown labels. Assuming that M = {m 1 , m 2 } (the models could be decision stumps, i.e, one-level decision trees (Rodríguez and Maudes, 2008), we would have that m 2 = m * mM is the minimax model and m 1 = m * mm the minimin one. The two models would however be incomparable according to (8), hence M * = M in this case, and the minimax and minimin rules would have given us different answers.

3 Partial data querying: a racing approach This section presents a general querying scheme based on racing idea and then investigates the computational issue of such a scheme for the specific setting of decision trees.

Both the minimin and minimax approaches (6)-( 7) have the same goal: obtaining a unique model from partially specified data. Our objective in this paper is different: we want to query those data that will increase the most the accuracy of a learned model. To do so, we propose to start from a set M of potentially optimal models, and to identify in a racing scheme those data that will be the most efficient in reducing our uncertainty about which model is the optimal one within M, hence are likely to be determinant in differentiating model quality in general. Much like querying-bycommittee in classical active learning [START_REF] Abe | Query learning strategies using boosting and bagging[END_REF], the purpose of the race is to select the query to be made, as M is unlikely to contain the risk minimizing model. Once the queries have been made, a new model should be learned from the updated data set. How we quantify the usefulness of a query within the race is formalized in what follows.

Let us first assume that X = X 1 × . . . × X P is a Cartesian product of P spaces, that a partial data (X n , Y n ) can be expressed as (× P p=1 X p n , Y n ), and furthermore that if X p ⊆ R is a subset of the real line, then X p n is a closed interval. A query on a partial data (× P p=1 X p n , Y n ) consists in transforming one of its dimension X p n or Y n into the true precise value x p n or y n , provided by an oracle (an expert, a precise measuring device). More precisely, q p n denotes the query made on X p n or Y n , with p = P + 1 for Y n . Given a model m k and a data (× P p=1 X p n , Y n ), we are interested in knowing two things:

whether the result of a query can have an effect on the the empirical risk bounds

R(m k ) = [R(m k ), R(m k )] ,
which will be the case only if the query can have an effect on the interval

L(Y n , m k (X n ) = [ (Y n , m k (X n )), (Y n , m k (X n ))] .
We will then speak about the single effect of a query, as we will consider a single model; whether the model m l can be preferred to m k after performing a query, in which case we have to assess whether the query can have an influence on the lower bound R(m k-l ) or not, since m l will be preferred to m k as soon as this bound becomes positive.

This can be formalized by two functions:

E q p n :M → {0, 1} , (10)
J q p n :M × M → {0, 1} , (11)
such that:

E q p n (m k ) = 1 if ∃x p n ∈ X p n that reduces R(m k ) 0 else . J q p n (m k , m l ) = 1 if ∃x p n ∈ X p n that increases R(m k-l ) 0 else . When p = P +1, X p
n is to be replaced by Y n . E q p n simply tells us whether or not the query can affect our evaluation of m k performances, while J q p n (m k , m l ) informs us whether the query can help to differentiate m k and m l . Let [S] := {1, 2, . . . , S}. If we denote by

k * = arg min k∈[S] R(m k )
the currently winning model (racing algorithms do focus on this model, trying to determine if it is really the winner of the race), the total effect of a query q p n is defined as

V alue(q p n ) = E q p n (m k * ) + k =k * J q p n (m k , m k * ) . ( 12
)
This value or utility is then used to assess which data (label or feature) should be queried next. It should be noticed that scores (10) and ( 11) can be modified, for example to account for different loss functions. Unless there are other reasons to change it, our choice appears to be the simplest and most straightforward.

Example 2 In Figure 1, questions related to partial classes (points 4 and 5) and to partial features (points 1, 2 and 3) have respectively the same potential effect, so we can restrict our attention to q 3 4 (the class of point 4) and to q 2 3 (the second feature of point 3). For these two questions, we have

-E q 3 4 (m 1 ) = E q 3 4 (m 2 ) = 1. -J q 3 4 (m 1 , m 2 ) = J q 3 4 (m 2 , m 1 ) = 0. -E q 2 3 (m 1 ) = 1, E q 2 3 (m 2 ) = 0. -J q 2 3 (m 1 , m 2 ) = J q 2 3 (m 2 , m 1 ) = 1.
This example shows that while some questions may reduce our uncertainty about many model risks (q 3 4 reduce risk intervals for both models), they may be less useful than other questions to tell two models apart (q 2 3 can actually lead to declare m 2 better than m 1 , while q 3 4 cannot).

The effect of a query being now formalized, we can propose a method inspired by racing algorithms. To create the initial set of racing models, a convenient method is to sample S times a precise data set

D = {(x n , y n ) ∈ (X n , Y n )} N n=1
and then to learn an optimal model for each such selection. Algorithm 1 summarises the general procedure applied to find the best query and to update the race. This algorithm simply searches the query that will have the biggest impact on the minimin model and its competitors, adopting the optimistic attitude of racing algorithms. Once a query has been made, the data set as well as the set of competitors are updated, so that only potentially optimal models remain. Note that in practice, such a sampling is close to methods used in queryby-committee approaches [START_REF] Abe | Query learning strategies using boosting and bagging[END_REF][START_REF] Nigam | Pool-based active learning for text classification[END_REF], and makes no specific assumption about the process that has led to imprecision. Also, as in usual query-by-committee and racing approaches, we also assume that we work with models of the same nature and of comparable complexity.

The next Section presents the practical computations of racing algorithm (Algorithm 1) for the case of set-valued labels, when the ones for the case of intervalvalued features will be given in the Section 5.

Algorithm 1: One iteration of the racing algorithm to query data.

Input: data {(X n , Y n )} N n=1
, set of models M = {m 1 , . . . , m S } Output: updated data and set of models

1 k * = arg min k∈[S] R(m k ); 2 foreach query q p n do 3 V alue(q p n ) = E q p n (m k * ) + k =k * J q p n (m k , m k * ); 4 (n * , p * ) = arg max (n,p) V alue(q p n ); 5 Get value x p * n * of X p * n * ; 6 foreach k, ∈ [S] × [S], k = do 7 Compute R(m k-) ; 8 if R(m k-) > 0 then remove m k from M ;
4 Application to decision trees: set-valued labels

In this section, we consider that the labels of some instances are partially given, but that all the features are precise. A query will simply be denoted by q n meaning that the label of instance x n is queried. In the classical setting of decision trees, the input space is

X = X 1 × . . . × X P ⊆ R p (where R is the real line) and the output space is Y = {λ 1 , . . . , λ G }, where λ g , g ∈ [G]
, encode all the possible classes. A decision tree m k is formally a rooted tree structure consisting of terminal nodes and non-terminal nodes [START_REF] Quinlan | Induction of decision trees[END_REF][START_REF] Safavian | A survey of decision tree classifier methodology[END_REF]:

-each non-terminal node of the tree is associated to an attribute X p (p ∈ [P ]), and to each branch issued from this node is associated a condition on this attribute that determines which data of the sample D go into that branch. -terminal nodes are called leaves. Each leaf is associated to a predicted class λ h ∈ Y and a partition element

A h = A 1 h × . . . × A P h where A p h ⊆ X p .
In the rest of this paper, we will adopt, for each leaf t h , the following notation

t h = (A h , λ h )
as such information is enough for the purpose of making prediction for new instances: for any instance

x n ∈ A h , we have m(x n ) = λ h .
The next small example illustrates those notations.

Example 3 We consider a given tree trained from data set D ∈ X with P = 2 attributes, and M = 3 classes. Input and output spaces are described as follows: Assume we have new instances x 1 = (2, 17) and x 2 = (6, 11). Then x 1 will reach leaf t 4 and be assigned to class m k (x 1 ) = c while x 2 will reach leaf t 1 with an assigned class m k (x 2 ) = a.

X 1 = [1, 10], X 2 = [10, 20], Y = {a, b, c}.
We will focus on the classical 0 -1 loss function defined as follows: for a given instance (x n , y n )

(y n , m k (x n )) = 0 if y n = m k (x n ) 1 otherwise . ( 13
)
In case of partially labelled data, the label is a set Y n ⊆ Y instead of a single label. The loss in (13) be-

comes an interval L(Y n , m k (X n ) whose bounds are (Y n , m k (x n )) = min λ∈Yn (λ, m k (x n )) , ( 14
) (Y n , m k (x n )) = max λ∈Yn (λ, m k (x n )) . ( 15
)
Example 4 Let us now continue with the data set and the decision tree from Example 3. Assume that instances x 1 and x 2 are partially labelled with Y 1 = {a, c} and Y 2 = {b, c}, respectively. Then using ( 14) and ( 15), we can easily get

L(Y 1 , m k (X 1 ) = [0, 1] , L(Y 2 , m k (X 2 ) = [1, 1] .
The next sections investigate how we can apply the racing algorithm presented in Section 3 to the practical case of partial labels in decision trees. We first study under which conditions a given partial label introduces imprecision in the empirical risks, before detailing the computation of querying value scores.

Instances introducing imprecision in empirical risk

For a given instance (x n , Y n ) and a decision tree m k , the lower and upper losses in ( 14) and ( 15) can be determined as follows:

(Y n , m k (x n )) = 0 if m k (x n ) ∈ Y n , 1 otherwise, ( 16
) (Y n , m k (x n )) = 0 if {m k (x n )} = Y n , 1 otherwise. ( 17
)
Given a decision tree m k , we will say that an instance is imprecise w

.r.t. m k if (Y n , m k (x n )) = (Y n , m k (x n )) . ( 18
)
The next proposition characterizes simple conditions under which an instance is imprecise w.r.t. m k .

X 2 t 1 = ([1, 10] × [10, 15), a) X 2 < 1 5 X 1 X 2 t 3 = ([1, 4] × (17, 20], b) X 2 > 1 7 t 4 = ([1, 4] × [15, 17], c) X 2 ≤ 1 7 X 1 ≤ 4 t 2 = ((4, 10] × [15, 20], b) X 1 > 4 X 2 ≥ 1 5 Fig. 2 Decision tree illustration m k Proposition 1 Given a model m k and instance (x, Y ), then (x, Y ) is imprecise w.r.t. m k if and only if m k (x) ∈ Y and |Y | > 1 . ( 19
)
Proof Let us first note that by definitions we always have

(Y, m k (x)) ≤ (Y, m k (x)) .
Then combining with condition (18) the lower and upper losses of an imprecise instance can be determined explicitly by

(Y, m k (x)) = 0 and (Y, m k (x)) = 1 . (20) Conditions in (13) guarantee that (Y, m k (x)) = 0 is equivalent to condition that m k (x) ∈ Y . Furthermore, condition |Y | > 1 ensures that (Y, m k (x)) = 1 (other- wise, {m k (x)} = Y
, and both lower and upper losses will be 0).

Proposition 1 simply translates the fact that imprecision can happen only if a partial label could contain the prediction of m k . Using Proposition 1, we can conclude that in Example 4, instance x 1 is imprecise w.r.t. m k while x 2 is precise, even if it has a partial label.

We are now going to investigate the practical computation of the empirical risk bounds of a single model, the pairwise risk bounds in a given set M of models and the effect of querying partial labels on those risks. It is easy to see that the empirical risk bound of a given model can be changed only by querying imprecise instances and the pairwise risk bounds can be changed if the chosen instance is imprecise w.r.t. at least one model. We will then focus on those cases in the next Sections.

Empirical risk bounds and single effect

Equation (4) (resp. ( 5)) implies that the computation of R(m k ) (resp. R(m k )) can be done by computing

(Y n , m k (x n )) (resp. (Y n , m k (x n ))), ∀ n ∈ [N ]
, and then by summing the obtained values. Therefore, the computation of the lower and upper risks of a given model can be carried out easily after determining the lower and upper losses of each instance.

Before going to present conditions under which a query q n have an effect on modifying the interval R(m k ) (or in other words E qn (m k ) = 1), let us first note that a query q n is effective if and only if L(Y n , m k (X n ) can be modified. Then, as pointed out in the next proposition, such effect (i.e E qn (m k ) = 1) will simply hold for all imprecise instances.

Proposition 2 Given an instance (x n , Y n ) and a model m k , then E qn (m k ) = 1 if and only if (x n , Y n ) is impre- cise w.r.t. m k .
Proof Firstly, it is easy to see that querying any instance that is precise w.r.t. m k will not help to modify L(Y n , m k (X n ). Furthermore, (20) implies that q n have an effect by either increasing (Y n , m k (x n )) or decreasing (Y n , m k (x n )). We will now show that at least one of such losses can be changed after querying any imprecise instance (x n , Y n ).

Assuming that λ is the label we get after query q n , then either λ = m k (x n ) or λ = m k (x n ). In the first case, both of lower and upper losses will be 0 after performing q n while both lower and upper losses will be 1 in the latter case. In other words,

E qn (m k ) = 1 if (x n , Y n ) is imprecise w.r.t. m k .
Computation of pairwise risk bounds and the effect J qn (m k , m l ) will be investigated in the next Section. Again, if an instance is precise w.r.t. both models, then querying it will not affect the pairwise risk bounds. Therefore, we will focus our interest on instances that are imprecise with respect to at least one model.

Pairwise risk bounds and effect

Let us now focus on how to compute, for a pair of models m k and m l , the corresponding pairwise risk R(m k-l ) and whether a query q n can increase this risk. The computation will be treated in two cases: when an instance is imprecise w.r.t. only one model and when an instance is imprecise w.r.t. both.

First note that, similarly to the empirical risk bounds of a unique model, the computation of R(m k-l ) can be carried out by simply summing up the values

k-l (Y n , x n ) for all (x n , Y n ) with k-l (Y n , x n ) = inf yn∈Yn (y n , m k (x n )) -(y n , m l (x n )) .
Furthermore, a query q n can increase R(m k-l ) if and only if it can increase the value k-l (Y n , x n ). This is why, in this section, we focus on computing k-l (Y n , x n ) and its possible change after a query q n .

Imprecision with respect to one model

We are going to present the computation of k-l (Y n , x n ) and the conditions under which J qn (m k , m l ) = 1.

Proposition 3 Given (x n , Y n ) and two models m k and m l s.t. x n is imprecise w.r.t. one and only one model, we have the following relations:

-if x n is imprecise w.r.t. m l , then k-l (Y n , x n ) = (Y n , m k (x n )) -1 . (21) -if x n is imprecise w.r.t. m k , then k-l (Y n , x n ) = 0 -(Y n , m l (x n )) . ( 22
)
Proof Since x n is imprecise w.r.t. only one model, the imprecision is only associated to such a model, and we can select the worst case: (y n , m (x n )) = 1 for Equation ( 21) and (y n , m k (x n )) = 0 for Equation ( 22).

Now we are going to study under which conditions a query q n can increase k-l . As the given instance is imprecise w.r.t. only one model, it can only increase the pairwise risk by either increasing (y n , m k (x n )) or decreasing (y n , m l (x n )). As shown in the next Proposition, this can always happen, meaning that we systematically have J qn (m k , m l ) = 1 in this case.

Proposition 4 Given (x n , Y n ) and two models m k and m l s.t x n is imprecise w.r.t. one and only one model, then query q n can always increase k-l , or in other words J qn (m k , m l ) = 1.

Proof We investigate the case where (x n , Y n ) is imprecise w.r.t. m k , the case for m l can be treated similarly.

Assuming that (x n , Y n ) is imprecise w.r.t. m k , then Proposition 2 ensures that there always exists a label λ ∈ Y n such that the lower bound (y n , m k (x n )) will be increased to 1 after query q n . Similar claim about decreasing the upper bound (y n , m l (x n )) can be carried when (x n , Y n ) is imprecise w.r.t. m l .

Imprecision with respect to both models

For the cases where x n is imprecise w.r.t. both models m k and m l , the computation of k-l (Y n , x n ) and the conditions under which J qn (m k , m l ) = 1 will be investigated separately in two circumstances: when

m k (x n ) = m l (x n ) and when m k (x n ) = m l (x n ).
Proposition 5 Given (x n , Y n ) and two models m k and m l s.t x n is imprecise w.r.t. both models, then the following results hold

-if m k (x n ) = m l (x n ), then k-l (Y n , x n ) = 0 and J qn (m k , m l ) = 0 . -if m k (x n ) = m l (x n ), then k-l (Y n , x n ) = -1 and J qn (m k , m l ) = 1 . Proof -Let m k (x n ) = m l (x n ), then (λ, m k (x n )) = (λ, m l (x n )) , ∀λ ∈ Y n .
Therefore, we always have

k-l (Y n , x n ) = k-l (Y n , x n ) = k-l (Y n , x n ) = 0 .
Furthermore, for any label λ ∈ Y n to be given after performing query q n , the difference k-l (Y n , x n ) will be 0. Or in other words, if

m k (x n ) = m l (x n ), then we can conclude that k-l (Y n , x n ) = 0 and J qn (m k , m l ) = 0. -In case m k (x n ) = m l (x n ),
k-l (Y n , x n ) = -1.
The effect J qn (m k , m l ) = 1 follows simply by assuming that label λ = m l (x n ) will be given after querying x n which implies that k-l (Y n , x n ) will be increased into 1.

The next section provides practical algorithms to perform a single querying step.

Algorithms

Algorithm 2 summarizes the complete procedure to perform an iteration of our querying strategy. Sub-routines are described in other algorithms. Algorithm 3 computes the individual risk bounds of every model, according to the corresponding values of (Y n , m k (x n )) and (Y n , m k (x n )). Algorithm 4 simply summarises the model selection procedure, that will also be used in the case of interval-valued features.

Finally, Algorithm 5 summarises the main procedure that determines the value of the different possible queries, allowing us to pick the best one among all the possible ones. Let us now analyse the complexity of this procedure. Lines 1-2 of Algorithm 2 are performed in O(S × N ), as Algorithm 3 is called S times and is in O(N ). Line 3 of Algorithm 2 is in O(S). Finally, since Algorithm 5 is in O(S), lines 4-5 of Algorithm 5 are in O(S × N ). So the overall complexity of Algorithm 5 is in O(S × N ), meaning that the approach is computationally affordable.

Algorithm 2: A single step to query setvalued data.

Input: Training data set {(x n , Y n } N n=1 , label set Ω = {λ 1 , . . . , λ G }, set of undominated model M. Output: The optimal query q n * 1 foreach m k ∈ M do 2 Compute empirical risk (R(m k ), R(m k )) bounds using Alg. 3;
3 Determine the best model m k * and the undominated model set M using Alg. 4;

4 foreach n ∈ [N ] do 5
Determine the query effect value V alue(q n ) using Alg. 5;

6 Determine q n * = arg max n V alue(q n );
Algorithm 3: Compute the empirical risk bounds (R(m k ), R(m k )).

Input: Training data set {(x n , Y n } N n=1 , label set Ω = {λ 1 , . . . , λ G }, model m k . Output: Empirical risk bounds (R(m k ), R(m k )) 1 R(m k ) = 0, R(m k ) = 0; 2 foreach n ∈ [N ] do 3 if |Y n | > 1 then 4 if m k (x n ) / ∈ Y n then R(m k ) = R(m k ) + 1; 5 R(m k ) = R(m k ) + 1 6 else if {m k (x n )} = Y n then R(m k ) = R(m k ) + 1, R(m k ) = R(m k ) + 1;
5 Application to decision trees: interval-valued features

We now deal with the case of interval-valued features, which is much more involved than the case of partial labels, yet still manageable from a computational point of view. Such additional difficulties may explain why there

k * = arg min m k ∈M R(m k ); 2 R min = min m k ∈M R(m k ) ; 3 foreach m k ∈ M do 4 if R(m k ) > R min then Remove m k from M;
Algorithm 5: Determine the effect value of a query V alue(q n ).

Input: Training instance (x n , Y n ), undominated model set M * . Output: The querying effect value V alue(q n ) 1 Initialize E q n (m k * ) = 0, J q n = 0; 2 if |Y n | > 1 and m k * (x n ) ∈ Y n then 3 E q n (m k * ) = 1; 4 foreach m k ∈ M and k = k * do 5 if m k (x n ) ∈ Y n and m k (x n ) = m k * (x n ) then J q n = J q n + 1; 6 else if m k (x n ) ∈ Y n then J q n = J q n + 1; 7 else if |Y n | > 1 then 8 foreach m k ∈ M and k = k * do 9 if m k (x n ) ∈ Y n then J q n = J q n + 1; 10 V alue(q n ) = E q n (m m * ) + J q n ;
are very few active learning methods dealing with missing features, and none (to our knowledge) dealing with partially known features, at least to our knowledge.

Instances introducing imprecision in empirical risk

Before going further, let us remind that, for a given tree m, each terminal node (which is sufficient in later analysis) is associated with a partition element

A h = A 1 h × . . . , ×A P h , (23)
where A p h can be a closed, open or semi-closed interval in our case. However, for the sake of practical implementation and exposure, we will from now on assume that A p h is a closed interval. Since we work with interval-valued feature data, for each instance (X n , y n ), its feature X n can be represented as a hyper-cube (similar to terminal node in (23)) denoted by

X n = X 1 n × . . . × X P n . (24)
The intersection between partition elements and/or partial instances is nothing else but the one of two hypercubes. Given two such hyper-cubes

U = U 1 × . . . × U P X 2 X 1 (A 2 , 1) (A 3 , 1) (A 6 , 1) (A 4 , 1) (A 5 , 0) (A 1 , 0) (X 1 , 0) (X 2 , 1) Fig. 3 Example of imprecise instance and V = V 1 × . . . × V P , their corresponding intersec- tion, denoted by U ∩ V is U ∩ V = × P p=1 U p ∩ V p . (25)
(25) provides a practical way to check whether the intersection of two cubic forms is non-empty. More precisely, we have that

U ∩ V = ∅ iff U p ∩ V p = ∅, ∀p ∈ [P ] . (26)
As for the case of partial labels, an instance (X, y) is said to be imprecise w.r.t. a decision tree

m k if ∃x, x ∈ X s.t (y, m k (x)) = (y, m k (x )) . (27)
Furthermore, as an instance can intersect several partition elements which are possibly associated to different labels, then ( 27) is equivalent to the following relation

∃A h , A h s.t X ∩ A h = ∅, X ∩ A h = ∅
and λ h = y and λ h = y .

Note that (28) can be easily determined using (26). The following Example gives illustrations of an imprecise instance w.r.t. a given decision tree.

Example 5 Figure 3 gives an example of a tree m k and two instances, (X 1 , 0), (X 2 , 1). It is easy to see that (X 1 , 0) is a precise instance since it only intersects with a partition element associated to label 0. However X 2 is imprecise since (28) holds. More precisely, (X 2 , 1) intersects with A 5 and A 6 whose associated labels are different.

Empirical risk bounds and single effect

We are now going to investigate how risk bounds R(m k ) can be computed efficiently from data {(X n , y n )} N n=1 by computing bounds L(y n , m k (X n )), and how the potential effect of a query q p n (q p n corresponding to ask the true value within X p n ) on those bounds can be estimated.

Let us first study how bounds on loss functions can be estimated. Similarly to the case of set-valued labels, an instance X n will get the imprecise empirical risk bounds L(y n , m k (X n )) = [0, 1] iff it satisfies condition (28). Otherwise, the corresponding loss is precise and such an instance can be discarded from the querying process. For example, in Figure 3, we can see that

L(y 1 , m k (X 1 )) = [0, 0] while L(y 2 , m k (X 2 )) = [0, 1].
Note that a training instance (X n , y n ) is precise if and only if partition elements that intersect with it either are all of label y n or all different from y n . To determine whether such a condition holds, let us firstly introduce the following information vectors

K = (k 1 , . . . , k H ) , k h = 1 if X n ∩ A h = ∅ , 0 otherwise, ( 29
)
B yn = (b 1 yn , . . . , b H yn ) , b h yn = 0 if λ h = y n , 1 otherwise , (30)
C yn = (c 1 yn , . . . , c H yn ) , c h yn = 1 if λ h = y n , 0 otherwise , (31)
with H the number of terminal nodes of the decision tree m k . Note that K can easily be built using ( 26), and that B, C have to be built only once. A given training instance X n is imprecise w.r.t. m k if and only if (KB yn )(KC yn ) = 0, where ab is the dot product of two vectors a and b. Before going further, let us note that we can use information vectors to deduce that (y n , m k (X n )) has the precise value 0 and 1, as this happens when KB yn = 0 and KC yn = 0, respectively. One can see that performing a query q p n can only change K. Denoting by K q p n the vector resulting from q p n , the single effect E q p n (m k ) = 1 if and only if (KB yn )(KC yn ) = 0 and ∃x p n ∈ X p n s.t.(K q p n B yn )(K q p n C yn ) = 0 . Verifying whether such a situation happens can be done by checking the two following conditions

∃x p n ∈ X p n s.t (K q p n B yn ) = 0 or ∃x p n ∈ X p n s.t (K q p n C yn ) = 0
We will present detailed developments and computations for the first condition and then present the result for the second one (which can be developed in a similar manner). The definition of K ensures that only elements of value 1 can change to zero after a query, since reducing X p n can only lead to the fact that a nonempty intersection with A h becomes empty. Furthermore, (26) implies that if k h = 1 then for all dimensions p = 1, . . . , P , we have X p n ∩A p h = ∅. Such an observation ensures that the results after performing q p n , k h = 0 if and only if ∃x p n ∈ X p n s.t x p n ∩ A p h = ∅, that is if the intersection with A h on dimension p can become empty after querying X p n . It then implies that the condition ∃x p n ∈ X p n s.t (K q p n B yn ) = 0 is equivalent to the following condition

∃x p n ∈ X p n s.t x p n ∩ A p h = ∅, ∀h where k h b h yn = 1,
or, in other words, there is a value x p n ∈ X p n s.t x p n does not belong to any of A p h for which the condition k h b h yn = 1 holds, that is for this value the resulting hyper-cube intersects with no leaves having y n as prediction. Such a condition comes down to check whether the following assertion is true:

X p n \ ∪ k h b h yn =1 A p h = ∅. (32)
Similarly, to determine whether

∃x p n ∈ X p n s.t (K q p n C yn ) = 0 ,
we can simply investigate whether

∃x p n ∈ X p n s.t x p n ∩ A p h = ∅, ∀h when k h c h yn = 1,
which can be done by checking the condition

X p n \ ∪ k h c h yn =1 A p h = ∅. ( 33
)
The general problem we have to solve is to check whether an interval X p n = a p n , b p n contains a value that is outside the union of some collection of intervals d i , d i (here, the intervals A p h satisfying the conditions in (32) and ( 33)). Once we notice this, we can rewrite the computational problem in the following form

a p n , b p n \ ∪ I i=1 d i , d i = ∅ , when ∀i = 1, . . . , I, a p n , b p n ∩ d i , d i = ∅. ( 34
)
The intuitive idea is that ( 34 are closed before another one starts (as illustrated in Figure 4). In formal terms, there exists an index j s.t.

{d i : d i < d (j) } = j -1 ,
which expresses the fact that before the jth interval [d (j) , d j) ] starts, the j -1 previous ones are closed, hence their union is not a closed interval. Provided ∪ I i=1 d i , d i is a closed interval, then checking whether it includes a p n , b p n can simply be done by checking that I) .

d (1) ≤ a p n ≤ b p n ≤ d (
For a given interval a p n , b p n and a set of interval

d i , d i |i ∈ [I] ,
then whether there is a value within

a p n , b p n that is not included in ∪ i d i , d i (i.
e., whether condition (34) is satisfied) can be checked using Algorithm 6.

Algorithm 6: Checking whether the condition (34) is satisfied. 34) is satisfied and 0 otherwise 1 Order {d 1 , . . . , d I } into {d (1) , . . . , d (I) } ; Let us now illustrate how to practically determine the single effect using a simple example.

Input: a p n , b p n , sets d i , d i |i ∈ [I] s.t, for ∀i, a p n , b p n ∩ d i , d i = ∅ Output: Return In = 1 if (
2 foreach i ∈ [I] do 3 if |{d k : d k < d (i) }| = i -1,
Example 6 Consider the tree m k and two instances X 1 , X 2 illustrated in Figure 3. Instance X 1 is precise w.r.t. the model m k , hence querying its feature is useless for

X 2 X 1 (A 2 , 1) (A 3 , 1) (A 6 , 1) (A 4 , 1) (A 5 , 0) (A 1 , 0) (X 2 , 1) x 1 2 x 1 2 x 2 2
x 2 2 Fig. 5 Example of determining the single effect this model. We then focus on determining the effect of querying the features of X 2 . Using ( 29)-( 31), the information vectors associated to X 2 are

K = (1, 1, 1, 1, 1, 1) , B y2 = (1, 0, 0, 0, 1, 0) , C y2 = (0, 1, 1, 1, 0, 1) .
Let us now investigate whether X 2 can become precise (w.r.t. the model m k ) by querying its feature X 1 2 . We have that

∪ k h b h yn =1 A 1 h = A 1 1 ∪ A 1 5
as leaves A 1 and A 5 are overlapping with X 2 and predict a different class from its true one. We can see on the picture that A 1 1 ∪ A 1 5 is a closed interval that does not includes X 1 2 . Then, for any value x 1 2 belonging to the interval (x 1 2 , x 1 2 ] as illustrated in the Figure 5, we have that K q p n B y2 = 0. In other words, we have that instance X 2 can become a precise instance after querying its feature X 1 2 . Similarly, for the case of querying X 2 2 , we have that

∪ k h b h yn =1 A 2 h = A 2 1 ∪ A 2 5 .
Since A 2 1 ∪ A 2 5 is not a closed interval, then, for any value x 2 2 belonging to the interval (x 2 2 , x 2 2 ) (illustrated in the Figure 5), we have that K q p n B y2 = 0. Finally, we conclude that instance X 2 can become a precise instance after querying either X 1 2 or X 2 2 .

Pairwise risk bounds and effect

This section focuses on how to compute, for a pair of models m k and m l , the corresponding pairwise risk bounds k-l (y n , X n ) for all instance X n and whether a query q p n can increase this risk. In a way similar to the case of set-valued labels (Section 4.3.2), computations will be treated in two cases: when the instance is imprecise w.r.t. only one model; and when it is imprecise for both.

Imprecision with respect to one model

In case an instance X n is imprecise w.r.t. one model (either m k or m l ), the pairwise risk bound k-l (y n , X n ) can be determined in a way similar to the case of setvalued labels (Proposition 3). Note that this bound is, in the context of imprecise features, defined as:

k-l (y n , X n ) = inf xn∈Xn (y n , m k (x n )) -(y n , m l (x n )) .
Proposition 6 Given (X n , y n ), and two models m k and m l s.t X n is imprecise w.r.t. one and only one model, then the following results hold

-if X n is imprecise w.r.t. m l , then k-l (y n , X n ) = (y n , m k (X n )) -1 . (35) -if X n is imprecise w.r.t. m k , then k-l (y n , X n ) = -(y n , m l (X n )) . ( 36
)
Proof Similar to proof of Proposition 3.

Then a query q p n will have an effect

J q p n (m k , m l ) = 1 if either q p n increases (y n , m l (X n )) or q p n decreases (y n , m k (X n )).
The detailed arguments can be found in the next proposition.

Proposition 7 Given (X n , y n ) and two models m k and m l s.t. X n is imprecise w.r.t. one and only one model, then J q p n (m k , m l ) = 1 if and only if one of the following conditions holds -if X n is imprecise w.r.t. m k , then J q p n (m k , m l ) = 1 if and only if Equation (33) holds for the model m k .

-if X n is imprecise w.r.t. m l , then J q p n (m k , m l ) = 1 if and only if Equation (32) holds for the model m l .

Proof Let us start with the case when X n is imprecise w.r.t. model m k . The condition that Equation ( 33) holds for the model m k simply implies that after performing a query q p n , the loss (y n , m k (X n )) becomes precisely 1. Hence it is clear that the pairwise risk bound is increased.

Similarly, when X n is imprecise w.r.t. model m l , that Equation (32) holds implies that after performing a query q p n , the loss (y n , m l (X n )) is precisely 0 which results in increasing k-l (y n , X n ).

Imprecision with respect to both models

Note that when an instance X n is imprecise with respect to both models m k and m l , the pairwise risk bounds k-l (y n , X n ) can get values in {-1, 0, 1}. Let us denote by λ m l h the label associated to the partition A h of a tree m l , then the relation between X n and leaves of m k and m l can be encoded in matrix form as follows

W k,l = w k,l i,j i=1,...,H k ,j=1,...,H l (37)
where the values of w k,l i,j and the corresponding conditions are

w k,l i,j Corresponding condition 2 X n ∩ A m k i ∩ A m l j = ∅ 1 X n ∩ A m k i ∩ A m l j = ∅, λ m k i = y n , λ m l j = y n 0 X n ∩ A m k i ∩ A m l j = ∅, λ m k i = λ m l j -1 X n ∩ A m k i ∩ A m l j = ∅, λ m k i = y n , λ m l j = y n (38)
It is easy to see that the matrix W k,l covers all possible values of k-l (y n , X n ), with 2 being an arbitrary value to denote that X n prediction does not depend on A m k i ∩ A m l j . The pairwise lower risk bound is then simply the minimum value of elements in matrix W k,l i.e.,

k-l (y n , X n ) = min i,j w k,l i,j . (39)
Before going to determine whether a query q p n can increase the pairwise risk bound k-l (y n , X n ), note that whether X n ∩ A m k i ∩ A m l j = ∅ can be easily determined as a consequence of Equation ( 25), as we have

X n ∩ A m k i ∩ A m l j = × P p=1 X p n ∩ A m k i,p ∩ A m l j,p .
Then for an instance X n , its corresponding pairwise risk bound w.r.t. two models m k and m l can be determined explicitly using Equations ( 37) and (38). A query q p n can increase the pairwise risk bound if and only if it can increase the value of all elements of value min i,j w k,l i,j . Let

S min = w k,l i ,j |w k,l i ,j = min i,j w k,l i,j (40)
be the set of such elements, then

J q p n (m k , m l ) = 1 if ∃ x p
n ∈ X p n s.t after querying X p n , all elements in the set S min are increased.

Note that for a given pair A m k i , A m l j , using (26), we have that their intersection is

A i,j = A m k i ∩ A m l j = × P p=1 A m k i,p ∩ A m l j,p := × P p=1 A p i,j , (41)
where A p i,j is a closed interval, for p = 1, . . . , P . Furthermore, a query q p n can increase the pairwise risk bound if ∃ x p n ∈ X p n s.t x p n / ∈ A p i,j , for all w k,l i,j ∈ S min . The next Proposition provides a practical procedure to check whether such a condition holds. Proposition 8 Given a training instance X n which is imprecise w.r.t. both models m k and m l , the corresponding W k,l matrix, assuming that min i,j w k,l i,j < 1, then

X 2 X 1 A 2,1 (1, 1) A 1,1 (0, 1) A 1,2 (0, 1) A 2,2 (1, 1) A 2,3 (1, 0) A 3,2 (1, 0) A 3,3 (1, 1)
J q p n (m k , m l ) = 1 if and only if X p n \ ∪ i,j|w k,l i,j ∈Smin A p i,j = ∅. ( 42
) Proof Let us first note that if (42) holds, then ∃ x p n ∈ X p n s.t x p n / ∈ A p i,j
, for all w k,l i,j ∈ S min . Then the corresponding elements w k,l i,j are increased to be 2. It is then resulting in the increasing of min i,j w k,l i,j , or in other words, the pairwise risk bound k-l (y n , X n ).

Checking whether Equation ( 42) is true can easily be reformulated in the form of Equation (34), Algorithm 6 can then be used to perform the check. In practice, such a check is quadratic in the number of leaves of the models m k , m l , which remains affordable from a computational standpoint. The next example illustrates how to practically determine the effect of queries on the pairwise risk bounds.

Example 7 Assume that we have two models m 1 and m 2 with 3 leaves each, whose intersection of partition elements is illustrated in Figure 6.

Instance X covers the red region and has label y = 1. From Figure 6, we can see that X is imprecise w.r.t. both models m 1 and m 2 , and its corresponding information matrix W 1,2 can be determined as follows

W 1,2 =   1 1 2 0 0 2 2 -1 2   Then it is clear that 1-2 (y, X) = -1 and S min = w k,l i ,j |w k,l i ,j = min i,j w k,l i,j = w 1,2 3,2 .
Let us now investigate whether the empirical risk bound 1-2 (y, X) can increase by querying the features of X. It is easy to see that A 1 3,2 is a closed interval that does not include X 1 . Then we always can find value

if In = 1 then E q p n (m) = 1; 6 In ← Alg. 6 with inputs X p n , {A p h |k h y n b h y n = 1}; 7 if In = 1 then E q p n (m) = 1;
The overall complexity is polynomial in all parameters, which may be considered as reasonable when the number of partial data, and the complexity of the trees both remain limited. Also, this is a worst-case complexity, assuming that every feature of every training data is imprecise, and that every resulting hyper-cube intersect all leaves of all the decision trees in M. In practice, we may expect partial features to be quite less numerous, as well as their intersections with tree leaves.

It should also be noticed that since the models will not change during the race, and that data will only be queried iteratively, one can in principle compute all matrices at the start of the race, and then proceed to if In = 1 then J q p n = J q p n + 1;

a minimal update at each query, thus considerably reducing the time to determine optimal queries. Finally, it should be noticed that querying data mainly makes sense when data are scarce (as an increased quantity of data improves the model accuracy even in the presence of imperfections).

Experiments

In this section, we run experiments on a "contaminated" version of 4 standard benchmark data sets as described in Table 2. To evaluate the efficiency of our proposal, we compare our racing algorithm with baseline algorithms whose details will be described separately in each setting of partial data. Note that when data are partial and in contrast with classical active learning, it is usually difficult to divide the data between a set of training data and a set of data with missing values, especially if all data are partial. This is why we will do the queries on the same data we use to train the models. As the situation where both input and output are partially given rarely happens in practice, we only focus on two settings: partiality in inputs; and partiality in outputs.

In both cases and for each selection of precise data, we use a standard CART decision tree learned in which splits are selected by Gini scores. It should be noted that changing the scores, e.g. for entropy, has usually little influence on the result [START_REF] Dubois | Comparing probability measures using possibility theory: A notion of relative peakedness[END_REF], as most of them are refinements of a unique ordinal notion. The next two subsections present details about the experimental settings and the results for intervalvalued features and set-valued labels data, respectively. It should be noted here that our primary goal is to verify that our approach query useful data, in the sense that those data are those that make the notion of best model ambiguous. Once this is confirmed, and after data have been queried, one could use other learning or aggregation methods such as ensemble learning to optimize accuracy from queried data.

Interval-valued features

We follow a 2 × 5 fold cross-validation procedure: Each data set is randomly split into 5 folds. Each fold is in turn considered as the training set D, while other folds are used for testing T. For each feature x p n in the training set, a biased coin is flipped in order to decide whether or not this example will be contaminated; the probability of contamination is δ. The level of partiality δ is fixed to two values (0.3 and 0.6) which correspond to a low and a high level of imprecision. In case x p n is contaminated, a width p n is generated from a uniform distribution on the unit interval. Then the generated interval valued data is

X p n = [x p n + p n (D p -x p n ), x p n + p n (D p - x p n )] where D p = min n (x p n ) and D p = max n (x p n ).
Example 8 Assume that the initial precise observed value is x = 1, that the domain is [D, D] = [0, 10], and that we have randomly picked = 0.5. In this case, the resulting interval-valued data is X = [0.5, 5.5].

To get the initial set of models for the race, we randomly generate 100 completions of interval-valued data.

From each completion, one tree model (with a minimal number of training observations in any terminal node fixed to 3 for first two small data sets and 5 for the two later ones) is trained and the set of such models is considered as the initial set of undominated models. The budget will be fixed to be the total number of partially featured values. After each query, we discard the dominated models and determine the best potential model. In case of multiple minimum risk models, the one with a minimum value of R m will be chosen as the best potential model.

The two following baseline algorithms are employed to query interval-valued data and make comparison about the evolution of the size of the sets of undominated models and the performance of the best potential model:

a random querying strategy where, at each iteration, the queried example and feature will be chosen randomly, -and the most partial querying strategy designed such that, at each iteration, examples with the largest imprecision will be queried.

Those baselines are quite straightforward, and we expect our method to perform better than those. As we mentioned in the introduction, we are not aware of other methods that intends to query the most influential data when features are partial, hence can only compare ourselves to those standard baselines in the case of partial features.

In practice, it may be the case that not all features appear in the set of racing trees. In those cases, keeping all the features in the instances would disadvantage both random and most partial querying in the race, since in this latter only the features present in the trees are relevant (i.e., will play a role to discard racing models). To make a comparable setting and to not give an unfair advantage to our method, we thus eliminate the features that do not appear in the trained trees.

In order to evaluate the performances of those different strategies, we will use three measures:

-the similarity of the best potential model m k * with a reference model m ref is computed on the precise test set T = {(x t , y t )} T t=1 . This similarity is computed as

|{t ∈ [T ]|m ref (x t ) = m k * (x t )}| T .
This similarity is 1 if the two models make identical predictions on the test set (hence have the same performances), and 0 if they systematically disagree. The reference model is chosen to be the one in the initial undominated set that has the best accuracy on the fully precise training set. It is thus the model towards which any querying strategy, and the race in particular, should converge; -the size of the undominated set M * , that should decrease as fast as possible, both to ensure computational efficiency and model performances. The 5-folds process is repeated 2 times. The average size of the sets of models and the average similarity of the best potential model are reported.

The experimental results are presented in Figure 7 and8. They show that, using the racing approach, the size of the undominated set can be quickly reduced and that the best potential model converges very fast to the desired model when knowing a small number of the precise data. The reduction of the size of the set is much slower for other querying strategies. This is true for the four tested data sets, and the advantage of using the racing approach is obvious whether we have little (δ = 0.3) or a lot (δ = 0.6) of imprecision. The exception observed for high imprecision (δ = 0.6) in the case of the segment data set is due to the fact that few features are used in the different trees, hence all models are quite similar, and all querying strategies focus on those features, converging at comparable speeds. For convenience, Table 3 also summarizes the obtained results after having queried 10% of the partial data. From the table, we can see that our approach is usually the best one, both at discarding sub-optimal models and at getting closer to the optimal one, except for the Vowel and Segment data sets in case of high imprecision. For the Segment data set, Figure 8.h confirms that all methods are comparable, while for the Vowel data set Figure 8.f shows that our approach is outperforming the others, yet only at the end of the querying process.

Set-valued labels

We perform on the same data sets as before (cf. Table 2) and the 2 × 5 cross-validation procedure as described for partially featured data (without the feature filtering step as we only consider the partial labels here).

In order to contaminate a given data set, we used the following strategy: for each example in the training set, a biased coin is flipped in order to decide whether or not this example will be contaminated; the probability of contamination is δ. When an example is contaminated, the class candidates are added with probability η, independently of each other. Thus, the contamination procedure is parametrized by the probabilities δ and η, where δ corresponds to the expected fraction of imprecise examples in a data set, and η reflects the average number of classes added to contaminated examples. The expected cardinality of a label set, in case of contamination, is given by 1 + (G -1)η. In all experiments, δ and η are fixed respectively to 0.3 and 0.8. To start the race, 100 precise replacements for each imprecise labels are randomly chosen. From each selection, one classification tree is trained. Similarly to the case of partial features, the minimal number of observations in any terminal node is fixed to 3 and 5 for the first two data sets and the later ones, respectively. To make comparisons, the two baseline querying schemes are also employed to query set valued-labels:

a random query strategy where, each time, imprecise examples will be chosen randomly to be queried. -a query by committee approach (QBC) in which each model is allowed to vote on the labellings of query candidates. The most informative query is considered to be the instance for which they most disagree. The disagreement measure used is the vote entropy:

x

* VE = argmax x - G g=1 V x (λ g ) S log V x (λ g ) S
where V x (λ g ) denotes the number of models predicting class λ g for a given instance x, and S = |M * | denotes the number of models in the committee. QBC approaches usually give good performance in active learning settings with missing labels, and give stateof-art results [START_REF] Vandoni | Evidential query-by-committee active learning for pedestrian detection in high-density crowds[END_REF].

In a way similar to the interval-valued setting, the size of the sets of models and the similarity of the best potential model m k * w.r.t. to the reference model are reported and used to make comparison. The experimental results, presented in Figures 9 and 10, show that, among the three approaches, random queries usually converge more slowly towards the reference model (except for the vowel data set), while the set of undominated models decreases similarly for all data sets and all strategies (with a slight advantage for the QBC strategy, and a poorly performing random queries for the segment data set). This contrasts with the partial feature case, where our approach significantly outperforms the others. A reason for that maybe that the case of partial labels offers much less degrees of freedom, hence the impact of the querying strategy may be quite less important than for the feature case. Table 4 summarizes the results for partial labels in the same way as Table 3 did for the features. We can see that all results are quite close in this table, as they are in the figures, and that there is essentially no big differences between the approaches. Note that it would have been possible to add many other more complex baselines, yet since both a random strategy and a more complex strategy such as QBC are on par with our proposed approach, we think this is sufficient to draw some conclusions.

Conclusion

The problem of actively learning with partial data has been little explored in the literature, in particular the case of partially known features. Indeed, active learning techniques usually focus on the case where a part of the labels are completely missing, while a few are known. To solve the problem, we apply in this paper an approach based on the idea of racing algorithms to the specific case of decision trees. To do so, we have developed a number of efficient algorithms to detect which data should be queried, in order to identify as soon as possible the best model among a set of racing ones.

We have then made some experiments to study the behaviour of our approach, compared to other querying strategies, starting from the same set of initial models. Our conclusion is that our approach significantly outperforms simpler strategies in the case of partially specified features, while it achieves similar performances in the case of partially specified labels. We think that this is due to the fact that partial labels offer much less degrees of freedom to the learning algorithms, meaning that most smart strategies, or even random ones will perform similarly. This is not the case for partial features, where purely random strategies as well as querying the most partial features perform poorly. This study considers a non-parametric classifier that can also be considered as a peculiar rule-based system, i.e., decision trees. As such, we can expect some of the conclusions and algorithmic procedures developed in this paper to also be applicable to generic rulebased systems [START_REF] Hühn | Furia: an algorithm for unordered fuzzy rule induction[END_REF]. Our paper therefore ideally complements our previous study [START_REF] Nguyen | Partial data querying through racing algorithms[END_REF], that focused on a parametric linear classifier, i.e., SVMs.

Compliance with Ethical Standards

Figure 2

 2 Figure2illustrates a possible decision tree m k for the above setting.

Algorithm 4 :

 4 Determine the best model m k * and the undominated model set M * . Input: Model set M, empirical risk bounds {(R(m k ), R(m k ))|∀m k ∈ M} Output: The best model m k * and the undominated model set M 1

then 4 Return

 4 In = 1 and Stop the Algorithm 5 if min i d i > a p n then 6 Return In = 1 and Stop the Algorithm 7 else if b p n > max i d i then 8 Return In = 1 and Stop the Algorithm 9 Return In = 0;

Fig. 6

 6 Fig. 6 Example of determining the pairwise effect

Fig. 8

 8 Fig. 7 Interval-valued features: Size of undominated model sets

Fig. 10

 10 Fig. 9 Set-valued labels: Size of undominated sets

Table 2

 2 Data set used in the experiments

	Name	# instances # features # classes
	wine	178	13	3
	breast-cancer	569	30	2
	vowel	990	10	11
	segment	2310	19	7

Table 4

 4 Partial labels: results after querying 10% of the partial data

	Data set	δ = 0.3, ν = 0.8
	# undominated models
		Rac. Rand. QBC
	Wine	93.8	91.7	94.6
	Breast	95.5	87.8	90.4
	Vowel	100	100	100
	Segment	97.4	94.4	95.6
	Similarity to best model
		Rac. Rand. QBC
	Wine	0.78	0.9	0.94
	Breast	0.82	0.88	0.9
	Vowel	0.54	0.59	0.74
	Segment	0.82	0.97	0.97

As X is often multi-dimensional, we will denote its elements and subsets by bold letters.

Funding: This work was carried out in the framework of Labex MS2T and UML-NET projects, which were funded by the French National Agency for Research (Reference ANR-11-IDEX-0004-02, ANR-14-CE24-0026).

x 1 ∈ X 1 s.t A 1 3,2 ∩ x 1 = ∅. In other words, we can increase the bound 1-2 (y, X) by querying X 1 .

However, as A 2 3,2 is a closed interval that includes X 2 , there is no value x 2 ∈ X 2 s.t A 2 3,2 ∩ x 2 = ∅, or in other words, the bound 1-2 (y, X) can not be increased by querying X 2 .

Algorithms

Algorithm 7 summarizes how to determine the optimal query for a single querying step in case of imprecise features. It is very similar to Algorithm 2, but takes different sub-routines specific to the case of partially known features.

Algorithm 7: A single step to query intervalvalued data.

3 Determine the best model m k * and the undominated model set M * using Alg. 4;

n (m k * ), . . . , E q P n (m k * )) using Alg. 9 with model m k * ; 6 Determine the cumulative pairwise effects (J q 1 n , . . . , J q P n ) using Alg. 10;

Algorithm 8 summarises how risk bounds, from which can be deduced the best potential model (through Algorithm 4, that remains unchanged), can be computed.

Algorithms 9 and 10 describe how potential effects of querying an instance (X n , y n ), respectively on empirical risk bounds and on pairwise risk bound, can be determined. Note that Algorithm 10 computes the sum of the pairwise effects between the best potential model m k * and the other ones. Let us now look at the complexity of Algorithm 8, assuming that all decision trees have H leaves. Before doing that, note that checking whether two hyper-cubes do intersect is in O(P ), according to Equation ( 26). Lines 2-3 are in O(S × N × H × P ), since Algorithm 8 is in O(N × H × P ), as computing vector K (line 3 of Algorithm 8) is in O(H × P ). Algorithm 4 remains in O(S). Lines 4-9 of Algorithm 8 is in O(N × S × P × H 4 ): indeed, in Algorithm 10, lines 7-9 are in O(P × H 4 ), as we must apply Algorithm 6 to at most H 2 intervals.

In particular, Algorithm 10 treats both the cases of an instance that is imprecise with respect to both models, as well as the other cases (other loops): Line 2 determines whether the instance is imprecise w.r.t m k * , Line 4 whether it is imprecise w.r.t m k . So Lines 4-9 correpond to imprecision with respect to both models, lines 10-13 to imprecision w.r.t only m k * , and lines 15-19 w.r.t only m k .

Algorithm 9: Determine the single effects (E q 1 n (m), . . . , E q P n (m)).

Input: Training instance (X n , y n ), a model m.

Output: The single effects (E q 1 n (m), . . . , E q P n (m))

Algorithm 10: Determine the cumulative pairwise effects (J q 1 n , . . . , J q P n ).

Input: Training instance (X n , y n ), undominated model set M, best model m k * . Output: The cumulative pairwise effects (J q 1 n , . . . , J q P n ) 1 Initialize (J q 1 n , . . . , J q P n ) = (0, . . . , 0); Conflict of Interest: all authors declare that they have no conflict of interest.

Ethical approval: This article does not contain any studies with human participants or animals performed by any of the authors.