Dang-Phong Bach

Ngoc-Thang Bui

Carranza Alarcon

Yonatan Carlos

Alia Chebly

Xuan-Nam Do

Clé- Ment Dubos

Dinh-Hiep Duong

Alberto García-Durán

Duc-Anh Hoang

Mohamed Ali Kandi

Minh-Ly Lieu

Duc-Hieu Nguyen

Tan-Nhu Nguyen

Cong-Cuong Pham

Trung-Nghia Phung

Shameem Puthiya Parambath

Khoat Than

Linh Nguyen

Nguy ˜ên Vu

˜ Linh

Keywords: imprecision, machine learning, active learning, racing algorithms, epistemic uncertainty, aleatoric uncertainty, multi-class classification

Imprecision in Machine Learning Problems

by Vu-

List of Notations

Query related notations q p n a query: asking for the precise value of the X p n q n a query: asking for the precise label of instance n E q p n (θ l ) single effect of query q p n J q p n (θ k , θ l ) pairwise effect of query q p n Decision tree related notations H number of terminal nodes of a tree

Introduction

This work focuses on imprecision modeling in machine learning problems, where available data or knowledge suffers from important imperfections. By imperfect data, we refer to the situations where either some features or the labels are imperfectly known, that is can be specified by sets of possible values rather than precise ones. For example, when the label of some training instances is only known to belong to a set of labels, or when some features are imprecisely given in the form of intervals (or, more generally, sets). In the second scenario, imperfect knowledge refers to the situations where data are precisely specified, however, there are classes, that cannot be distinguished due to a lack of knowledge (also known as epistemic uncertainty) or due to a high uncertainty (also known as aleatoric uncertainty). In this introduction, we are going to formulate the problems we will consider, before providing a quick overview of our contributions. We are first going to summarize the basics of the learning problem, then highlight possible scenarios where the classical methods is likely to be insufficient and quickly introduce our proposals to tackle these situations.

Learning problems

Learning is, in general, the problem of teaching a learner (classifier) to generalize from experience [7,[START_REF] James | An introduction to statistical learning[END_REF]. In the context of supervised learning, generalization refers to the ability of a learning machine to perform accurately on new examples after having experienced a training data set [START_REF] Vapnik | An overview of statistical learning theory[END_REF][START_REF] Vapnik | Statistical Learning Theory[END_REF]. Almost of the works on supervised learning literature can be categorized into either inductive techniques or transductive techniques. Roughly speaking, inductive techniques learn a model θ * issued from the hypothesis space Θ ⊆ Y X that best fits the training data set D = {(x n , y n )} N n=1 ⊆ X × Y of N input/output samples, where X := R P and Y := {y 1 , . . . , y M } are, respectively, the input and the output spaces, and uses θ * to make predictions for new instances (t, ?). When using transductive techniques, training data are used directly to perform the inference step (on new instances (t, ?)) without any induction step. This is illustrated by Figure 1.1.

Before going further, let us note that, we denote by Θ the underlying hypothesis space, i.e., the class of candidate models θ : X -→ Y the learner can choose from. Often, hypotheses are parametrized by a parameter vector θ ∈ Θ; in this case, we equate a hypothesis with the parameter θ, and the model space with the parameter space Θ.

Inductive learning

The goal of inductive learning (the upper path of Figure 1.1) is to extract a model θ * : X → Y within a model space Θ which best fits the training data set D [START_REF] Friedman | The Elements of Statistical Learning[END_REF][START_REF] Guyon | Structural risk minimization for character recognition[END_REF][START_REF] Vapnik | An overview of statistical learning theory[END_REF][START_REF] Vapnik | Estimation of dependences based on empirical data[END_REF][START_REF] Vapnik | Principles of risk minimization for learning theory[END_REF]. This strategy has been widely studied and detailed for numerous applications, e.g, support vector machine (SVM) [START_REF] Burges | A tutorial on support vector machines for pattern recognition[END_REF][START_REF] Cortes | Support-vector networks[END_REF], logistic regression [START_REF] Cox | The regression analysis of binary sequences[END_REF][START_REF] Walker | Estimation of the probability of an event as a function of several independent variables[END_REF], Naive Bayes [START_REF] Russell | Artificial intelligence: A modern approach[END_REF], etc. Two classical map to derive the optimal model θ * are to use either the loss minimisation approach which seeks for the model (in the hypothesis space) that minimizes the loss on the training set, or, the likelihood maximization approach whose optimal candidate is the one that is most probable for the training data, usually assuming that there are i.i.d observations. In the loss minimization approach, candidates of Θ are assessed by the mean of a risk scoring function R : Θ → R and seeks for the one minimizing this risk function function, i.e, the one minimizes the expected loss R(θ) = X ×Y (y, θ(x))dP(x, y),

where : Y × Y → R is the loss function, and (y, θ(x)) is the loss of predicting θ(x) when observing y. It is obvious that the probability measure P(x, y), which specifies the data generating process, is unknown, thus the risk (1.1) cannot be computed directly. Therefore, in practice, it is usually estimated using the empirical risk R(θ | D), that is

R(θ | D) = N n=1
(y n , θ(x n )).

(1.

2)

The selected model is then the one minimizing (1.2). Thus, loss minimisation approach can be in principle applied as soon as a loss function is defined [START_REF] Hüllermeier | Learning from Imprecise and Fuzzy Observations: Data Disambiguation through Generalized Loss Minimization[END_REF][START_REF] Vapnik | Principles of risk minimization for learning theory[END_REF]. Maximum likelihood estimation (MLE) [START_REF] Fisher | On the Mathematical Foundations of Theoretical Statistics[END_REF][START_REF] Myung | Tutorial on maximum likelihood estimation[END_REF] requires a well-defined likelihood function and a probabilistic hypothesis space. MLE is based on the principle (originally developed by R.A. Fisher [START_REF] Fisher | On the Mathematical Foundations of Theoretical Statistics[END_REF]) stating that the desired probability distribution is the one that makes the observed data most likely, which means the optimal model should be the one maximizing the likelihood function [START_REF] Myung | Tutorial on maximum likelihood estimation[END_REF]. This can be done by either maximizing the conditional probability p θ (y | x), for discriminative methods, or, the joint probability p θ (x, y), for generative learning methods [START_REF] Ng | On Discriminative vs. Generative classifiers: A comparison of logistic regression and naive Bayes[END_REF].

-The discriminative methods, e.g, logistic regression [START_REF] Cox | The regression analysis of binary sequences[END_REF][START_REF] Walker | Estimation of the probability of an event as a function of several independent variables[END_REF], or, support vector machines (SVM) [START_REF] Burges | A tutorial on support vector machines for pattern recognition[END_REF][START_REF] Cortes | Support-vector networks[END_REF], assume some functional form of p θ (y | x), the conditional probability that the label y ∈ Y will be assigned to the instance x, and seek for the model θ * ∈ Θ maximizing the discriminative likelihood function, i.e, (1.

3)

The optimal model θ * is then used to make inference/predictions on new instances (t, ?), typically using the expected loss minimisation, e.g, to assign for t the label y * ∈ Y with the highest conditional probability p θ * (y | t).

-Generative learning methods, for instance, Naive Bayes [START_REF] Russell | Artificial intelligence: A modern approach[END_REF], assume some functional form of p θ (y) and p θ (x | y). With the assumption of conditional independence, which is typically made for generative models, the joint probability p θ (x, y) can be expressed in the factorized form as follows p θ (x, y) = p θ (y)p θ (x | y) = p θ (y) P p=1 p θ (x p | y).

(1.4)

Thus, the optimal model θ * , which will be used to make inference, is the one maximizing the generative likelihood function, that is

θ * = arg max

Transductive learning

In a transductive learning approach, in contrast with inductive learning one, estimates for each new instance (t, ?) a potential model by using additional information related to this point [START_REF] Joachims | Transductive Inference for Text Classification using Support Vector Machines[END_REF][START_REF] Kasabov | Transductive support vector machines and applications in bioinformatics for promoter recognition[END_REF][START_REF] Pang | Inductive vs transductive inference, global vs local models: SVM, TSVM, and SVMT for gene expression classification problems[END_REF][START_REF] Vapnik | Statistical Learning Theory[END_REF] (the lower path of the Figure 1.1). This means that, in a transductive approach, the training data D are always maintained and are used to make inference for the new instances (t, ?) (rather than using an optimal model θ * as in inductive learning). For instance, in case of the K nearest neighbours (K-nn) method, a non-parametric classifier, for each new instance (t, ?), we extract directly from D a set of K nearest neighbours, denoted by N t , and derive an optimal prediction y * for t based on the voting scores given by training instances in N t . Let us remind that, in traditional learning problems, the input and output data are supposed to be precise, i.e, (x, y) ∈ X × Y. In this work, one of our interest is to investigate what could happen when either the input or the output becomes partially known, i.e, when having data of the form (X, Y ) ⊆ X × Y.

Learning from partial data

The first question we look at is what happens when data becomes partial, i.e, given in form (X, Y ) ⊆ X × Y, and we have to learn from them. 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. In particular, partially labelled data may come from easy-to-obtain high-level information. For instance, when characterizing names in subtitles to identify those characters present in an image/video [START_REF] Cour | Learning from Partial Labels[END_REF], labeling characters with its location in word segmentation [100] or in signal segmentation [START_REF] Briggs | Rank-loss support instance machines for MIML instance annotation[END_REF][START_REF] Liu | A Conditional Multinomial Mixture Model for superset label learning[END_REF]. Another possible setting of partial data is when some features of some instances can only be partially specified, i.e, belong to intervals (or sets). This kind of data may come from imprecise measurement devices, imperfect knowledge of an expert, or can also be the result of the summary of a huge data set.

To tackle the problem of learning from partial data, generic learning methods have to be adapted to cope with partial data, as the notion of optimal model is no longer well-defined. Two general trends in literature are:

-to adapt the criteria, for instance, likelihood [START_REF] Denoeux | Maximum Likelihood Estimation from Fuzzy Data using The EM algorithm[END_REF][START_REF] Denoeux | Maximum Likelihood Estimation from Uncertain Data in the Belief Function Framework[END_REF] or loss function [START_REF] Cour | Learning from Partial Labels[END_REF][START_REF] Hüllermeier | Learning from Imprecise and Fuzzy Observations: Data Disambiguation through Generalized Loss Minimization[END_REF][START_REF] Hüllermeier | Superset Learning Based on Generalized Loss Minimization[END_REF] (e.g, the ones defined in (1.2)-(1.5)), so that the notions of optimal models are again well-defined, -or, to consider sets of models corresponding to ways in which the data can be completed, e.g., by comparing interval-valued loss function, or by considering imprecise likelihoods [START_REF] Utkin | Decision making under incomplete data using the imprecise Dirichlet model[END_REF].

Note that, in general, one may consider problems where only a part of the data is partially specified: either the labels or the features.

Partially labelled data

There are different approaches to learn from partially labelled data, i.e, data are given in the form (x, Y ).

-T. Cour, et al. [START_REF] Cour | Learning from Partial Labels[END_REF] assume that the precise value and observed partial data x, y, Y are distributed according to an (unknown) distribution p θ (x, y, Y ) = p θ (x)p θ (y | x)p θ (Y | x, y) and seek for the the distribution (model) with high conditional entropy for p θ (Y | x, y). The generic approach is formulated and investigated for the particular case of voting classifiers, which assign, for a given instance x, a score g θ (y | x) to each label y and select the highest scoring label g θ (. | x). The optimal model θ * is the candidate within Θ that minimizes the Convex Loss for Partial Labels (CLPL), a generalization of (1.2) with (y, θ(x)) being the 0/1 loss.

-Adopting the superset assumption, which does not assume anything else than the observation Y being a superset of y, in [START_REF] Hüllermeier | Learning from Imprecise and Fuzzy Observations: Data Disambiguation through Generalized Loss Minimization[END_REF][START_REF] Hüllermeier | Learning from Ambiguously Labeled Examples[END_REF][START_REF] Hüllermeier | Superset Learning Based on Generalized Loss Minimization[END_REF], some authors propose to choose the optimal model by minimizing the optimistic superset loss (OSL).

-Another method to learn from partial data is fuzzy EM (FEM) [START_REF] Denoeux | Maximum Likelihood Estimation from Fuzzy Data using The EM algorithm[END_REF][START_REF] Denoeux | Maximum Likelihood Estimation from Uncertain Data in the Belief Function Framework[END_REF] which proposes to estimate the parameters of a probabilistic model based on maximizing the observed-data likelihood defined as the probability of the fuzzy data.

These methods differ by the choice of the likelihood/loss function and/or the prior assumptions about the incompleteness process generating partial data [START_REF] Couso | A general framework for maximizing likelihood under incomplete data[END_REF].

The first part of this work focuses on the superset assumption based approach [START_REF] Hüllermeier | Learning from Imprecise and Fuzzy Observations: Data Disambiguation through Generalized Loss Minimization[END_REF][START_REF] Hüllermeier | Superset Learning Based on Generalized Loss Minimization[END_REF], this means we will process under a very generic assumption that whenever a feature or label is partially given, it is a superset of (i.e, covers) the true value. Yet, this approach has been detailed and justified, in both theoretical and experimental aspects, for the case of partially labelled data. Adapting the approach for the case of partially featured data is still challenging.

Active learning: missing and partial data

Missing data

In classical active learning, some observed data are complete and form the initial training data set D = {(x n , y n )} N n=1 . The goal of active learning is to determine which new data is useful to improve the learned model.

A popular assumption in classical active learning is that it is possible to ask for the label of unlabelled data. In this work, we will concentrate on the solution where we have a set of precise data D, and a pool U of unlabelled data. In this solution, several active learning approaches exist:

-The uncertainty sampling approach [START_REF] Lewis | A Sequential Algorithm for Training Text Classifiers[END_REF], measures how uncertain the current optimal model θ * is about each instance within the given pool U, using an utility score, e.g, conditional entropy, maximum conditional, margin of confidence, etc., and queries the instance with the highest uncertain score.

-The query-by-committee approach [START_REF] Seung | Query by committee[END_REF] assumes that a set of models Θ QBC ⊆ Θ is available and can be employed to assess the instances within the pool U. For each unlabelled instance (t, ?) ∈ U, each member θ ∈ Θ QBC is then allowed to vote for its prediction θ(t). The most informative query is considered to be the instance about which they most disagree, e.g, to maximize the vote entropy or the Kullback-Leibler (KL) divergence.

-The expected model/error approach [START_REF] Settles | Multiple-instance active learning in Proceedings of the 20[END_REF] has been developed upon the intuition that the learner seeks for instances that are likely to most influence the model, regardless of its true label. This approach has been highlighted to work well in empirical studies, however, can be computationally expensive if both the number of features and cardinality of the output space Y are very large.

These approaches assess the effect of querying each unlabelled instance, within a given pool U, by mean of an utility score and query the instance with the highest score. Thus, they differ by the choice of utility score. Yet, classical active learning approaches have shown advantages, including simple implementations and interpretable results, it have been debated for the lack of informing about the reasons for why an instance is considered uncertain, although this might be relevant for judging the usefulness of an instance. This demand comes from the fact that different sources of uncertainty could play quite different roles in specific applications [START_REF] Senge | Reliable Classification: Learning Classifiers that Distinguish Aleatoric and Epistemic Uncertainty[END_REF][START_REF] Sharma | Evidence-based Uncertainty Sampling for Active Learning[END_REF]. For instance, in active learning, Sharma and Bilgic [START_REF] Sharma | Evidence-based Uncertainty Sampling for Active Learning[END_REF] propose an evidence-based approach to active learning, in which conflicting-evidence uncertainty is distinguished from insufficient-evidence uncertainty. Experimentally, they support their conjecture that the former is more informative for an active learner than the latter, however, the uncertainty measures used by [START_REF] Sharma | Evidence-based Uncertainty Sampling for Active Learning[END_REF] are somewhat ad-hoc, and their approach is tailored for a specific learning algorithm (Naïve Bayes [START_REF] Russell | Artificial intelligence: A modern approach[END_REF]).

Pursuing a similar purpose, in [START_REF] Senge | Reliable Classification: Learning Classifiers that Distinguish Aleatoric and Epistemic Uncertainty[END_REF], authors proposed a distinction between the epistemic, caused by a lack of training data, and aleatoric, due to intrinsic randomness, uncertainty. Thus, it is reasonable to make the hypothesis that, when doing active learning, querying instances with high degrees of epistemic uncertainty could provide a significant improvement on the classifiers performance comparing with querying the ones of high aleatoric and other types of uncertainty. Furthermore, the formal model in [START_REF] Senge | Reliable Classification: Learning Classifiers that Distinguish Aleatoric and Epistemic Uncertainty[END_REF] is generic as it can be, in principle, applied to any probabilistic classifier with a well-defined likelihood function. Thus, active learning methods (if can be) developed upon this building block can be applied in a broader context (compared to the ones of evidence-based approach).

Partially specified data

Classical active learning assumes either full or completely missing information, and mostly focuses on the output data. A much less studied setting is the case of partially known data, either in features or labels. Note that in this case, it is not clear that whether we should (1) made a distinction between the (partial) training set D := {(X n , Y n ) N n=1 } and pool U, consisting of data to be queried, or (2) it is desirable to use the partial data in the learning step.

In this work, by assuming that the pool U is identical to the partial training set D, we thus look at the following question: given the partial data D = {(X n , Y n ) N n=1 } and some model Θ to learn, what partial data should we query (by query we mean choosing partially specified features or labels and asking its precise value to an oracle) in order to better learn the optimal model θ * . This problem can be seen as a generalisation of the classical active learning [START_REF] Fu | A Survey on Instance Selection for Active Learning[END_REF][START_REF] Lewis | A Sequential Algorithm for Training Text Classifiers[END_REF][START_REF] Settles | Active Learning Literature Survey[END_REF][START_REF] Settles | An Analysis of Active Learning Strategies for Sequence Labeling Tasks[END_REF], where training instances are precisely specified while the instances in the pool U have precise features X := x ∈ X and completely missing labels, i,e, Y is either empty or identical to the output space Y. The scenario where the feature values are either completely missing or precisely specified [START_REF] Melville | Active Feature-Value Acquisition for Classifier Induction[END_REF][START_REF] Melville | An Expected Utility Approach to Active Feature-Value Acquisition[END_REF] is also covered in our concern.

In our settings, we adopt the superset assumption [START_REF] Cour | Learning from Partial Labels[END_REF][START_REF] Hüllermeier | Learning from Imprecise and Fuzzy Observations: Data Disambiguation through Generalized Loss Minimization[END_REF][START_REF] Hüllermeier | Learning from Ambiguously Labeled Examples[END_REF][START_REF] Hüllermeier | Superset Learning Based on Generalized Loss Minimization[END_REF] and allow to use the partial data in the learning step. For instance, we will use the maximax approach [START_REF] Hüllermeier | Learning from Imprecise and Fuzzy Observations: Data Disambiguation through Generalized Loss Minimization[END_REF][START_REF] Hüllermeier | Learning from Ambiguously Labeled Examples[END_REF][START_REF] Hüllermeier | Superset Learning Based on Generalized Loss Minimization[END_REF] to make inferences. Thus, the presence of partial data can lead to the following indecision situations, where using active learning can be an efficient way to reduce the imprecision.

-When doing induction on a partial data set

D = {(X n , Y n )} N n=1 , it is reasonable to say that model θ is better than θ if L(θ | d) < L(θ | d), for any replacement d of D.
Thus there is a possibility of obtaining a set of models Θ * ⊆ Θ whose candidates are equivalently optimal, rather than a singleton. Yet, even if we can use either a minimin (optimistic) or a maximin (pessimistic) approach [START_REF] Troffaes | Decision Making under Uncertainty using Imprecise Probabilities[END_REF][START_REF] Wiencierz | On the Validity of Minimin and Minimax Methods for Support Vector Regression with Interval Data[END_REF] to learn an optimal model, this model is actually one candidate of Θ * and the larger the size of Θ * , the higher chance we pick up the wrong model. Thus if we are allowed to query some (partially specified) features or labels of some instances, we should query the data that can help to quickly reduce the set Θ * .

-Another possible scenario is when a non-parametric model, e.g, a K nearest neighbours classifier (K-nn), is employed to make inference. In this case, we are following a transductive learning approach where the partial training data D = {(X n , Y n )} N n=1 are used directly to perform the inference step. Thus, it is quite possible that for some new instances (t, ?), we see multiple optimal predictions, i.e, a set Y (t) ⊆ Y of labels that are equivalently optimal. Thus, if we can do active learning to reduce the risk of choosing wrong decision, we should query the data that can help the most to reduce Y (t).

Cautious inferences

In classical supervised learning, typical (probabilistic and/or deterministic) models, once learned from the precise training data set D = {(x n , y n )} N n=1 , will provide, for each new instance (t, ?), an optimal inference or prediction in the form of a single class [7,[START_REF] Friedman | The Elements of Statistical Learning[END_REF][START_REF] Vapnik | An overview of statistical learning theory[END_REF]]. Yet, there are situations where it could be useful to make cautious inferences, in the form of set-valued, or credal, predictions when we are unsure about the optimal class to predict. This is especially true in safety-critical applications, such as medical diagnosis [START_REF] Devetyarov | Conformal predictors in early diagnostics of ovarian and breast cancers[END_REF][START_REF] Papadopoulos | Reliable diagnosis of acute abdominal pain with conformal prediction[END_REF] or drug discovery process [1,[START_REF] Eklund | The application of conformal prediction to the drug discovery process[END_REF]. Cautious inference has been increasingly tackled in literature, for instances:

-A nondeterministic classifier [START_REF] Corani | Introduction to Imprecise Probabilities[END_REF] produces a set-valued prediction by invoking the principle of expected loss minimization, where the underlying cost measure combines the precision and correctness of the prediction.

-Methods based on imprecise probabilities, such as [START_REF] Corani | Introduction to Imprecise Probabilities[END_REF], augment probabilistic predictions into probability intervals or sets of probabilities, the size of which reflects the lack of information. Similar to this are methods based on confidence bands in calibration models, for instance [START_REF] Kull | Reliability maps: a tool to enhance probability estimates and improve classification accuracy[END_REF][START_REF] Xu | Evidential calibration of binary SVM classifiers[END_REF]. They usually control the amount of imprecision by adjusting some certainty parameters, e.g., a confidence value.

-Conformal prediction [4,[START_REF] Shafer | A Tutorial on Conformal Prediction[END_REF] is another generic approach to reliable (set-valued) prediction that combines ideas from probability theory (specifically the principle of exchangeability), statistics (hypothesis testing, order statistics), and algorithmic complexity. Roughly speaking, for each new instance (t, ?), it assigns a non-conformity score to each candidate output. Then, considering each of these outcomes as a hypothesis, those outcomes for which the hypothesis can be rejected with high confidence are eliminated. The set-valued prediction is given by the set of outcomes that cannot be rejected.

These proposals can be seen as extensions of classification with a reject option whose prediction is either a singleton set or the entire Y [START_REF] Chow | On optimum recognition error and reject tradeoff[END_REF]. Yet the predictive abilities of theses set-valued prediction classifiers have been studied both theoretically and experimentally. Giving the reasons for why a class should be included into or discarded from a set-value prediction seems to be challenging. In a cautious inference approach, it is important to identify those instances for which the prediction is the most uncertain, or the less robust (i.e., for which a slight model change would change the prediction), and to find a good balance between informativeness (providing rather precise, but possibly wrong predictions) and cautiousness (predicting numerous classes probably containing the right one, but being poorly informative). It thus appears important, in this problem, to identify what make the prediction uncertain or poorly robust: is it ambiguous due to statistical variability and effects that are inherently random, or, to a lack of knowledge due to inadequate training data?

These two types of uncertainty, as mentioned in the active learning problem, are usually referred as aleatoric and epistemic [START_REF] Hora | Aleatory and Epistemic Uncertainty in Probability Elicitation with an Example from Hazardous Waste Management[END_REF][START_REF] Senge | Reliable Classification: Learning Classifiers that Distinguish Aleatoric and Epistemic Uncertainty[END_REF]. The distinction between epistemic and aleatoric can indeed provides insightful evidences for why we should be cautious while its complement, i.e, the strict preferences in favor of predicting one class over another/others are important when insisting on the informativeness.

Yet, the distinction epistemic/aleatoric is well-accepted in the literature on uncertainty [START_REF] Hora | Aleatory and Epistemic Uncertainty in Probability Elicitation with an Example from Hazardous Waste Management[END_REF] and has been very recently considered in machine learning [START_REF] Kendall | What Uncertainties do We Need in Bayesian Deep Learning for Computer Vision[END_REF][START_REF] Senge | Reliable Classification: Learning Classifiers that Distinguish Aleatoric and Epistemic Uncertainty[END_REF]. To practically determine/estimate such degrees of uncertainty may become rather complex and highly depends on the choice of the class of hypothesis and likelihood function. Thus, developing practical procedures to determine/estimate these degrees certainly benefits further applications based on this distinction. For instances, the problem of making cautious inference, considered here, or, the active learning problem highlighted in the previous Section.

Our contributions

In this work, we make the following contributions: -In the case of transductive learning, and more precisely K nearest neighbours (K-nn) classifier, we propose to look at both the learning problem and the active learning problem from partial data, solving the first one by using a maximax approach and the second one by proposing a querying scheme inspired by voting rules with incomplete information. This will be detailed in Chapter 2.

-Considering partial data and imprecisely-valued loss functions, we propose a generic racing approach to query partial data, in order to improve the subsequent learning step. Our proposal can also be seen as a contribution to formulate the active learning problem for partial data. This will be detailed in Chapter 3.

-In chapter 4, we differentiate two kinds of uncertainties: an aleatoric or irreducible one, that just comes from the fact that classes are mixed, and an epistemic or reducible one, that comes from the fact that we have few information about the instance. We provide estimation methods for the classical models that are logistic regression, local models and Naive Bayes. Finally, we explain how these estimates can be used to solve two problems: the one of active learning, and the one of performing cautious inferences.

Before detailing the proposals, let us note that there are two possible readings of this work: following a problem flow as sketched in the horizontal structure of

Transductive learning and partial data

This chapter first tackles the problem of making inference from the partially specified data and then presents active learning methods to reduce the imprecision in the inference step introduced by partially specified data.

Problem statements

The setting we consider here is when the training data set is partially specified, i.e,

D = {(X n , Y n )} N n=1
, and the maximax approach [START_REF] Hüllermeier | Learning from Imprecise and Fuzzy Observations: Data Disambiguation through Generalized Loss Minimization[END_REF][START_REF] Hüllermeier | Learning from Ambiguously Labeled Examples[END_REF][START_REF] Hüllermeier | Superset Learning Based on Generalized Loss Minimization[END_REF] is used to make inference for new (precise) instance (t, ?) (the general case when new instance can be partially specified is left as an open problem). We will process both learning and active learning problem under the superset assumption that is whenever a label or a feature is partially specified, the partial information covers the true value.

A Maximax approach for learning from partial data

Let us first recall that, in the classical loss minimization approach [START_REF] Hüllermeier | Learning from Imprecise and Fuzzy Observations: Data Disambiguation through Generalized Loss Minimization[END_REF][START_REF] Vapnik | Principles of risk minimization for learning theory[END_REF], the candidates of hypothesis space Θ are assessed by the mean of a risk scoring function R : Θ → R and the chosen model is the one minimizing the expected loss

R(θ) = X ×Y (y, θ(x))dP(x, y), (2.1)
where : Y × Y → R is the loss function, and (y, θ(x)) is the loss of predicting θ(x) when observing y. As recalled in the introduction, in practice, it is usually estimated using the empirical risk

R(θ | D) on the training data D = {(x n , y n )} N n=1 , that is R(θ | D) = N n=1 (y n , θ(x n )), (2.2)
The selected model is then the one minimizing (2.2), that is

θ * = arg min θ∈Θ R(θ | D). (2.3)
Given the optimal model θ * , we can simply assign for each new instance t the label candidate that minimizes the prediction loss (y, θ * (t)), i.e, y * = arg min y∈Y (y, θ * (t)).

(2.4)

Assuming that the non-parametric K-nn classifiers [START_REF] Cover | Nearest Neighbor Pattern Classification[END_REF][START_REF] Wu | Top 10 algorithms in data mining[END_REF] are used to make predictions, i.e, following a transductive approach [START_REF] Joachims | Transductive Inference for Text Classification using Support Vector Machines[END_REF][START_REF] Pang | Inductive vs transductive inference, global vs local models: SVM, TSVM, and SVMT for gene expression classification problems[END_REF][START_REF] Vapnik | Statistical Learning Theory[END_REF], for each new instance t its prediction is learned directly from the training data D = {(x n , y n )} N n=1 . This mean that only the inference step (2.4) is concerned (without any learning step (2.2)-(2.3)). Denoting by N t = {(x k , y k )} K k=1 and w = (w 1 , . . . , w k ), the set of K nearest neighbours of t within D and the corresponding weight vectors, respectively, each label y ∈ Y will be given a voting score s t (y) (of how likely it will be assigned for t) s.t,

s t (y) = K k=1 w k 1 y=y k , (2.5) with 1 A the indicator function of A (1 A = 1 if A is
true and 0 otherwise). The optimal prediction for t is thus the one maximizing (2.5), i.e, y * = arg max y∈Y s t (y).

(2.6)

The maximax approach [START_REF] Hüllermeier | Learning from Imprecise and Fuzzy Observations: Data Disambiguation through Generalized Loss Minimization[END_REF][START_REF] Hüllermeier | Learning from Ambiguously Labeled Examples[END_REF][START_REF] Hüllermeier | Superset Learning Based on Generalized Loss Minimization[END_REF] can be seen as a generalization of this K-nn classifier. Let us remind that in the case of general partial data, i,e, when having a training data

D = {(X n , Y n )} N n=1
and a new precise instance t, the superset assumption means that the observation X p n and Y n are supersets of x p n and y n , respectively. We define the set of possible replacements of D as follows:

D = d := {(x n , y n ) ∈ (X n , Y n )} N n=1 . (2.7)
Thus, a replacement d of D is a precise data set where each partial information (either a feature or the label of an instance) in D is replaced by a possible precise value. For each replacement d ∈ D, denoting by

N d t = (x 1 , y 1 ), . . . , (x K , y K ) , (2.8)
the set of K nearest (precise) neighbour instances of t in the replacement d. Thus, the voting score that can be given for a label y ∈ Y is defined as follows

s d t (y) = K k=1 w k 1 y=y k , (2.9)
Thus to minimize the optimistic superset loss (OSL) [START_REF] Hüllermeier | Learning from Imprecise and Fuzzy Observations: Data Disambiguation through Generalized Loss Minimization[END_REF][START_REF] Hüllermeier | Superset Learning Based on Generalized Loss Minimization[END_REF] is the main task when adopting this maximax approach. This maximax approach is detailed for the scenario of set-valued labelled and precisely specified data, i.e, [START_REF] Hüllermeier | Learning from Ambiguously Labeled Examples[END_REF] and further justified in [START_REF] Cour | Learning from Partial Labels[END_REF][START_REF] Hüllermeier | Learning from Imprecise and Fuzzy Observations: Data Disambiguation through Generalized Loss Minimization[END_REF][START_REF] Hüllermeier | Superset Learning Based on Generalized Loss Minimization[END_REF]. In this specific case, the maximum score can be simply determined using counting operations, that is

D = {(x n , Y n )} N n=1 , in
s max t (y) = K k=1 w k 1 y∈Y k .
(2.12)

As the nearest neighbour sets is determined based on a distance in X , in case of partially labelled data, the possible replacements differ only by its choice of the replacement of partial labels. Determining the maximum score (2.11) is reduced to manipulate a set of set-valued labels, i,e., the set {Y k } K k=1 where Y k is the partial labels of the k-th nearest neighbour of t. However, it is not necessarily the case where some features of some instances are partially specified. In this later case, the notion of nearest neighbour set N t is no-longer well defined. To tackle this issue, we adopt an optimistic approach, in Section 2.2, to replace the ill-known values, that requires to compute sets of possible and necessary neighbours of an instance.

Active learning for partial data

Let us first note that under the superset assumption, it is reasonable to consider that the optimal predictions learned from different replacements d ∈ D (i.e, the labels maximizing the score (2.9) for at least one replacement d) have equal possibility to be the true optimal one. Thus, in this sense, by minimizing the optimistic superset loss (OSL), the maximax approach assigns for each new instance t a possible optimal prediction. On the other hand, if a label y ∈ Y is the winner in all the possible replacements, it should remain to be the optimal one when having the complete precise training data, i.e, a necessary optimal label. In the specific case of partially labelled data [START_REF] Cour | Learning from Partial Labels[END_REF][START_REF] Hüllermeier | Learning from Imprecise and Fuzzy Observations: Data Disambiguation through Generalized Loss Minimization[END_REF][START_REF] Hüllermeier | Learning from Ambiguously Labeled Examples[END_REF][START_REF] Hüllermeier | Superset Learning Based on Generalized Loss Minimization[END_REF], the sets of such possible and necessary optimal labels are identical to the possible and necessary winner sets, respectively, studied in the voting procedures with incomplete preferences [5,[START_REF] Konczak | Voting Procedures with Incomplete Preferences in Proceedings of the IJCAI[END_REF][START_REF] Moulin | Handbook of Computational Social Choice[END_REF].

The notions of possible and necessary label sets, denoted by PL t and NL t , respectively, can be easily extended for the general setting of partial data, i.e, D = {(X n , Y n )} N n=1 . For a new instance t, denoting by y d t its corresponding optimal prediction learned from a replacement d, we can define its possible and necessary label sets as follows:

PL t = {y ∈ Y | ∃d ∈ D s.t y = y d t } (2.13) NL t = {y ∈ Y | ∀d ∈ D, y = y d t } (2.14)
Thus, if we have to make a precise inference, we should assign for t a label y * ∈ PL t , e.g, by using the maximax approach. This means a larger size of PL t implies a higher chance of picking up a wrong decision, or, a higher degree of imprecision. We thus tackle the following problem: if we are allowed to query (ask for the true values of) some features or labels of some partial instances, which partial data should we query first to reduce the imprecision in the inference step? Let us remind that by querying partial data, we assume that the pool U is identical to the partial training set D in a active learning setting.

It is clear from (2.7) that the number of possible replacements d ∈ D should be reduced along the querying process. Thus, the cardinality of the possible label set PL t (2.13) should decrease while the cardinality of the necessary label set NL t (2.14), in contrast, should increase when the querying process goes along. The changes of possible and necessary label sets will be considered as the potential effects in our active learning proposals.

-For the purpose of making (precise) inference, it is clear that we should look for partial data which, if they are queried (to know its precise value and update the training data set), can help to quickly reduce the cardinality of the possible label set PL t .

-Also, at the beginning (of the querying process), it is reasonable to assume that the training data contains many partial data and there is a high chance of seeing empty necessary label sets. Furthermore, as soon as we see a non-empty empty necessary label set, i.e, NL t = ∅, we can pick up any of them as an optimal prediction of t and making any further query is redundant. Thus seeking for a quick enlargement of the necessary label set NL t should be considered as another potential effect when querying partial data.

Our querying proposals developed upon these intuitions will be detailed for the case of partially labelled data in Section 2.3 and perspectives on developing similar proposals for partially featured data are given in Section 2.4.

Learning from partially featured data

We are going to detail the maximax approach for the case of interval-valued featured data (a simple yet reasonable assumption in the setting of partially featured data).

Of course, the general assumption where both of training and test data can be partially featured are more reasonable and popular in practice. However, working on such a setting requires extensions in mathematical-based technique, e.g, the extreme distances between instances. We thus focus on a simpler setting that the training data can be partially featured while the test data are precisely given and leave the general case as a future work. More precisely, we consider here the setting consisting of a partially featured training data set D = {(X n , y n )} N n=1 , where X n = (X 1 n , . . . , X P n ) and X p n = [a p n , b p n ], ∀p = 1, . . . , P , and precise test instances T = {(t t , ?)} T t=1 . In addition, we will only focus on the unweighted version of maximax approach while leaving the case of weighted maximax opened.

Let us remind that, the main concern when implementing the maximax approach, is to compute the maximum score s max t (y) (2.11) that can be assigned to each class candidate ∀y ∈ Y. Our idea here is to first determine the set of possible and necessary neighbour sets, through computing interval ranks of distances, and, from that, s max t (y) can be derived easily using simple counting operations.

Determining interval ranks

Given a partial training data instance X n ∈ D and a precise instance t, Groenen et al. [START_REF] Groenen | Multidimensional Scaling of Interval Dissimilarities[END_REF] provide simple formulae to determine the imprecise distance

d(X n , t) = d(X n , t), d(X n , t) of X n with respect to t: d(X n , t) = P p=1 |c p n -t p | + r p n 2 1/2 , (2.15) d(X n , t) = P p=1 max 0, |c p n -t p | -r p n 2 1/2 , ( 2
2 X 1 (t, ?) (X 1 , a) (X 2 , b) (X 3 , c) (X 4 , b) (X 5 , a) [d(X 1 , t), d(X 1 , t)] = [3, 5] [d(X 2 , t), d(X 2 , t)] = [1, 1.4] [d(X 3 , t), d(X 3 , t)] = [2.8, 4.4] [d(X 4 , t), d(X 4 , t)] = [3, 3.2] [d(X 5 , t), d(X 5 , t)] = [5.6, 7] Figure 2.1: Example with |D| = 5 X 1 X 2 X 3 X 4 X 5 r X 1 1 1 0 0 0 2 X 2 0 1 0 0 0 1 X 3 0 1 1 0 0 2 X 4 0 1 0 1 0 2 X 5 1 1 1 1 1 5 c 2 5 2 2 1
X i X j if d(X i , t) ≥ d(X j , t) (2.17)
where X i X j means that X i is farther than X j from t. As demonstrated by Patil and Taille [START_REF] Patil | Multiple Indicators, Partially Ordered Sets, and Linear Extensions: Multi-criterion Ranking and Prioritization[END_REF]Sec. 4.1], this partial order then allows us to derive interval rank values as we have that

X i X j ⇒ r(X i ) ≥ r(X j ),
where r(X i ) is the rank that can be assigned to X i . Once the relation is determined, D is a poset (partially ordered set) and the corresponding relation matrix, denoted by ζ, is a N × N matrix defined as

ζ i,j = 1 if X i X j 0 otherwise. (2.18)
The results given by Theorems 1 and 2 in [71, Sec. 4.1] imply that each instance X n ∈ D can be associated to an imprecise rank r n = [r n , r n ], which measures how close it is to the target instance t, where [2,4], [1,1], [2,4], [2,4], [5,5]).

r n = N j=1 ζ n,j and r n = N + 1 - N j=1 ζ j,n . (2
([r 1 , r 1 ], [r 2 , r 2 ], [r 3 , r 3 ], [r 4 , r 4 ], [r 5 , r 5 ]) = (
(2.20)

Determining the extreme scores

Denoting by R t = {r n = [r n , r n ] | n = 1, . . . , N } the imprecise ranks of the instances in D, we can easily determine the sets of possible and necessary neighbours as

PN t = {X n | r n ≤ K} (2.21)
and

NN t = {X n | r n ≤ K}. (2.22)
We have that

X n ∈ NN t if it is in the set of nearest neighbours X n ∈ N d t for any replacement d ∈ D, while X n ∈ PN t if X n ∈ N d
t only for some replacement d ∈ D. For each label y ∈ Y, we can then compute its minimum number of votes

s small t (y) = X n ∈ NN t | y n = y , (2.23)
given by its necessary neighbours. From s small t (y) we can then be deduced the maximal and minimal number of votes y can receive from K nearest neighbours, according to the following formulae: (2.25)

s max t (y) = min X n | X n ∈ PN t , y n = y , K - y =y s small t (y ) , (2.24)
These scores are simply derived from the fact that, among the K nearest neighbours, at least s small t (y) among them must give their votes to label y. This is proved in the next Lemma, where it is shown that s min t (y) and s max t (y) are the minimum and maximum number of votes that can be given to y over all replacements d ∈ D (i.e, they are consistent with the one defined in the general setting (2.11)

Learning from interval-valued feature data

The maximax approach (2.10) can be then practically implemented for interval-valued featured data as follows:

θ(t) = arg max y∈Y s max t (y) (2.28) = arg max y∈Y min X n | X n ∈ PN t , y n = y , K - y =y s small t (y ) .
It may also happen that Equation (2.28) returns multiple labels that have the highest number of votes. We can then follow a different strategy, where we consider the result of the K-nn procedure for a peculiar replacement. Since every label receives its maximal number of votes by considering the lower distance d(X n , t), a quite simple idea is to consider the result obtained by the case of set-valued labelled data [START_REF] Hüllermeier | Learning from Ambiguously Labeled Examples[END_REF] when we consider the replacement d giving d(X n , t) = d(X n , t) for every X n . The procedure to make predictions is summarized in Algorithm 1.

Experimental evaluation

Experiments

We run experiments on a contaminated version of 6 standard benchmark data sets described in Table 2.2 1 . By contamination, we mean that we introduce artificially imprecision in these precise data sets. These data sets have various numbers of classes and features, but have a relatively small number of instances, for the reason that handling imprecise data is mainly problematic in such situations: when a lot of data are present, we can expect that enough precise data will exist to reach an accuracy level similar to the one of fully precise methods. Our experimental setting is as follows: given a data set, we randomly chose a training set D consisting of 10% of instances and the rest (90%) as a test set to limit the number of training samples. For each training instance x n ∈ D and each feature x p n , p = 1, . . . , P and n = 1, . . . , N , a biased coin is flipped in order to decide whether or not the feature x p n will be contaminated; the probability of contamination is and we have tested different values of it ({0.2, 0.4, 0.6, 0.8}). In case x p n is contaminated, its precise value is transformed into an interval which can be asymmetric with respect to x p n . To do that, a pair of widths {l p n , r p n } will be generated from two Beta distributions, Beta(α l , β) and Beta(α r , β). To control the skewness of the generated data, we introduce a so called unbalance parameter η and assign {α l , α r } = {β * η, β/η}. Then the generated interval valued data is

X p n = [x p n + l p n (D p -x p n ), x p n + r p n (D p -x p n )] where D p = min n (x p n ) and D p = max n (x p n ).
As usual when working with Euclidean distance based K-nn, data is normalized. Then, the proposed method is used to make predictions on the test set and its accuracy is compared with the accuracy of two other cases: classical K-nn when fully precise data is given, and a basic imputation method consisting in replacing an interval-valued data X p n by its middle value, i.e,

x p n = (X p n + X p n )/2.
The disambiguated data is used to make predictions under the classical K-nn procedure.

Because the training set is randomly chosen and contaminated, the results maybe affected by random components. Then, for each data set, we repeat the above procedure 100 times and compute the average results. The experimental results on the data sets (described in Table 2.2) with several combinations of parameters (K, , η, β) are given in the Table 2.3, with the best results between imputation and the presented method put in bold (the precise case only serves as a reference value of the best accuracy achievable). These first results show that the difference between the two approaches is generally small. Surprisingly, this is true for all explored settings, even for skewed imprecision and high uncertainty (η = 0.25, = 0.8). However, on the two data sets dermatology and vehicle, our approach really provides a significant, consistent increase of accuracy, and this even for low and balanced imprecision (η = 1, = 0.2).

Conclusion

The very first experiments provided here suggest that a simple imputation method could often work as well as the presented approach, but for some data sets the maximax approach can bring a real advantage. In the future, we intend to do more experiments (varying K, increasing the number of data sets) and also try to understand the origin of the witnessed difference. However, the more interested point here is, by identifying possible and necessary neighbours, the maximax approach can also provides us with information about how uncertain our prediction is. This later advantage is instrumental in the next step we envision for this part of the work: determining which sample feature should be queried first to improve the overall algorithm accuracy, much like what we are going to investigate, in the next Section, for the case of partial labels.

Querying partially labelled data to improve the maximax approach

We are going to present our proposals for querying partially labelled data to improve the inference ability of the maximax method. We will first present a generic querying principle and a simple neighbour-based querying criteria which inspired by the highdensity regions based technique in classical active learning [START_REF] Settles | An Analysis of Active Learning Strategies for Sequence Labeling Tasks[END_REF], before detailing the idea highlighted in Section 2.

Generic querying scheme

General setting

In this proposal, we assume that we have a training data set D = {(x n , Y n )} N n=1 used to make predictions, with x n ∈ X the features and Y n ⊆ Y are partially specified labels. Let us remind that we will adopt the superset assumption that is to assume that Y n contains the true label y n , as usual when working with partial labels [START_REF] Cour | Learning from Ambiguously Labeled Images[END_REF][START_REF] Cour | Learning from Partial Labels[END_REF][START_REF] Hüllermeier | Learning from Imprecise and Fuzzy Observations: Data Disambiguation through Generalized Loss Minimization[END_REF][START_REF] Hüllermeier | Learning from Ambiguously Labeled Examples[END_REF][START_REF] Hüllermeier | Superset Learning Based on Generalized Loss Minimization[END_REF]100]. We also assume that we have an unlabelled target data set T = {(t t , ?)} T t=1 that will be used to determine the partial labels to query and can be defined differently based on the usage purposes as pointed out latter in Section 2.3.3.

For a new instance t and a value K, its set of nearest neighbours in D is denoted by N t = {x t k |k = 1, . . . , K} where x t k is its k-th nearest neighbour. We will also say that Y n ∈ N t if x n is among the K nearest neighbours of a given instance t. We also assume that we have a vector w t = (w t 1 , . . . , w t K ) weighting each neighbour in N t according to its distance to the target. Similarly, for a training instance x n ∈ D, we denote by G xn = {t | x ∈ N t } the set of target instances of which x n is a nearest neighbour.

In the remainder of this proposal, we will use the maximax approach [START_REF] Hüllermeier | Learning from Imprecise and Fuzzy Observations: Data Disambiguation through Generalized Loss Minimization[END_REF][START_REF] Hüllermeier | Learning from Ambiguously Labeled Examples[END_REF][START_REF] Hüllermeier | Superset Learning Based on Generalized Loss Minimization[END_REF] to make decision, i.e, assign for each new instance t, the prediction such that:

θ(t) = arg max y∈Y x t k ∈N t w t k 1 y∈Y t k .
(2.29)

The idea of the above method is to count one (weighted) vote for y whenever it is in the partial label Y t k .

Example 2. Let us consider the case illustrated in Figure 2.2, where the training data set contains 6 instances, the target set has 5 instances and the output space Y = {y 1 , y 2 , y 3 }.

Assuming that we work with K = 3, the nearest neighbours of each target instance and their associated (illustrative) weights are given in Table 2.4. And we have also:

G x 1 = G x 2 = G x 3 = {t 1 , t 2 } G x 4 = G x 5 = G x 6 = {t 3 , t 4 , t 5 }.
Instances x 5 and x 6 cannot be queried because they are precise, but which label among x 1 , x 2 , x 3 and x 4 should be queried is not obvious. Indeed, x 4 is involved in more decisions than the three other partial labels (as |G x 4 | is greater than all other sets), but getting more information about x 4 will not change these decisions, as the result of Equation (2.29) will not change whatever the true label of x 4 . In contrast, knowing the true label of x 1 , x 2 or x 3 may change our decision about x 1 and x 2 , hence, from a decision viewpoint, querying these partial labels seems more interesting.

t

N t w t t 1 {x 1 , x 3 , x 2 } (0.9,0.8,0.7) t 2 {x 2 , x 3 , x 1 } (0.8,0.8,0.4) t 3 {x 6 , x 4 , x 5 } (0.8,0.8,0.4) t 4 {x 6 , x 4 , x 5 } (0.7,0.7,0.7) t 5 {x 4 , x 5 , x 6 } (0.8,0.8,0.4) We are going to explore querying patterns following both intuitions (neighbourbased and ambiguity-based), but we first introduce a general querying scheme and a simple neighbour-based criteria.

A generic scheme

Our generic querying scheme follows a simple rule: for each partially labelled instance x n and each target instance t, we will define a function

f xn (t) (2.30)
called local effect score, whose exact definition will vary for different criteria. The role of this function is to evaluate whether querying the training instance x n can impact the result of the maximax method (2.29) for the target instance t. Since we want to improve the algorithm over the whole target set, this will be done by simply summing the effect of x n over all data in the target set T, that is by computing

f xn (T) = t∈T f xn (t), (2.31)
that we will call global score function. The chosen instance to be queried, denoted by x n * , will then simply be the one with the highest effect score, or in other words

x n * = arg max xn∈D f xn (T).
We will now propose different ways to define f xn (t), that will be tested in the experimental evaluation section. Since the computation of the global effect score from the local ones is straightforward, we will focus in the next sections on computing f xn (t) for a single instance. Also, we will denote by q n the query consisting in asking the true label of x n .

Neighbour-based querying criteria

Our first idea is quite simple and consists in evaluating whether a partially labelled instance x n is among the neighbours of the target instance t, hence if x n will participate to its classification, and how strongly x n does so. This can be estimated by the simple function f M W xn (t) as follows

f M W xn (t) = w n K k=1 w t k (2.32)
where w n is w t k if x n is the k-th neighbour of t, and zero otherwise. The global effect score of x n can then be computed using Equation (2.31). In the unweighted case, this score is the number of target instances of which x n is a neighbour. This strategy is similar to the one of querying data in high-density regions in active learning techniques [START_REF] Settles | An Analysis of Active Learning Strategies for Sequence Labeling Tasks[END_REF]. Table 2.5 summarizes the global effect scores for Example 2. As expected, x 4 is the one that should be queried according to f M W xn , since it is the one participating to most decisions.

f M W

Indecision-based querying criteria

This Section presents other effect scores based on whether a partially labelled instance x n introduces some ambiguity in the decision about an instance t. We first define what we mean by ambiguity.

Ambiguous instance: definition

In the maximax approach [START_REF] Hüllermeier | Learning from Imprecise and Fuzzy Observations: Data Disambiguation through Generalized Loss Minimization[END_REF][START_REF] Hüllermeier | Learning from Ambiguously Labeled Examples[END_REF][START_REF] Hüllermeier | Superset Learning Based on Generalized Loss Minimization[END_REF], each neighbour can be seen as a (weighted) voter in favor of her preferred class. Partial labels can then be assimilated to voters providing incomplete preferences. For this reason, we will define ambiguity by using ideas issued from plurality voting with incomplete preferences [5,[START_REF] Konczak | Voting Procedures with Incomplete Preferences in Proceedings of the IJCAI[END_REF][START_REF] Moulin | Handbook of Computational Social Choice[END_REF]. More precisely, we will use the notions of necessary and possible winners of such a voting scheme to determine when a decision is ambiguous.

For an instance t, as its set of neighbours N t = {x t 1 , . . . , x t K } can be derived easily, manipulating the set of possible replacement D is thus reduced to handling the following set Let us remind that querying partial labels is equivalent to reducing the number of possible replacements d t . Thus, we can reduce the ambiguity of t by either reducing PL t or increasing NL t , eventually getting NL t = PL t . We are going to investigate those effects and then present our querying proposals.

D t = {d t =: (y t 1 , . . . , y t K ) | y t k ∈ Y t k }, i,e.,

Ambiguous instance: computation

A first issue is how to actually compute NL t and PL t . The problem of determining NL t is very easy [START_REF] Konczak | Voting Procedures with Incomplete Preferences in Proceedings of the IJCAI[END_REF]. However, determining PL t is in practice much more difficult. In the unweighted case, known results [5,[START_REF] Xia | Determining Possible and Necessary Winners under Common Voting Rules given Partial Orders[END_REF] indicate that PL t can be determined in cubic (hence polynomial) time with respect to M , by solving a maximum flow problem and using the fact that when votes are (made) unitary, the solution of this flow problem is integer-valued (due to the submodularity of the constraint matrix).

However, when votes are non-unitary (when weights are different), this result does not hold anymore, and the problem appears to be NP-complete, as it can be reduced to a 3-dimensional matching problem. A refined analysis of the complexity in terms of fixed parameters (M or K) could however help to identify those cases that are harder to solve from those that remain easy (polynomial). In addition to that, in our setting we can have to evaluate the set of possible labels PL t a high number of times (in contrast with what happens in social choice, where NL t and PL t have to be evaluated at most a few times), hence even a cubic algorithm may have a prohibitive computational time. This is why we will provide an easy-to-compute approximation of it, denoted by APL t . Let us first provide some definitions.

Given the set of nearest neighbours N t , we denote by The next proposition states that APL t is an outer approximation of PL t (therefore not missing any possible answer) and that both coincide whenever NL t is nonempty (therefore guaranteeing that using APL t will not make some instance artificially ambiguous). The following Lemma which determines a condition for a label y to not be in PL t , and an illustrative example are necessarily to carry out the proof of the Proposition.

Y t = ∪ K k=1 Y t k ⊆ Y
(y) = s max t (y) = s min t (y ) ≥ s d t (y ) for y ∈ Y t \ {y, y }. Hence y is also in PL t , or in other words APL t ⊆ PL t .

Effect of a query on ambiguous instances

Now that we have defined how to identify an ambiguous instance, the question arises as to how we can identify queries that will help to reduce this ambiguity. This Section provides some answers by using the notions of necessary and (approximated) possible labels to define a local effect score (2.30). More precisely, the local effect score f xn (t) will take value one if a query can modify either the sets PL t or APL t , or the set NL t . Additionally, as this local effect score aims at detecting whether a query can affect the final decision, it will also take value one if it can change the decision θ(t) taken by Equation (2.29). In some sense, such a strategy is close to active learning techniques aiming to identify the instances for which the decision is the most uncertain (uncertainty sampling [START_REF] Lewis | A Sequential Algorithm for Training Text Classifiers[END_REF], query-by-committee [START_REF] Seung | Query by committee[END_REF]).

To define this score, we need to know when a query q n can potentially change the values of the possible label set PL t , the approximated possible label set APL t , the prediction set θ(t) or the necessary label set NL t . A first remark is that if an instance x n ∈ N t is not among the neighbours of t, then a query q n cannot change any of these values. Let us now investigate the conditions under which q n can change the sets when x n ∈ N t . We first introduce some useful relations between the sets PL t , APL t , or NL t . We will denote by PL qn t , APL qn t , and NL qn t the sets potentially obtained once x n is queried.

In this proposal, a query will be considered interesting (i.e., having a local effect score of one) if at least one value y ∈ Y n can change NL t , PL t , APL t or θ(t). Indeed, requiring all possible values y ∈ Y n to change the sets of necessary labels NL t , possible labels PL t , approximation APL t or prediction set θ(x) is much too demanding, and is unlikely to happen in practice.

We will go from the cases that are the most likely to happen in practice, that is changes in PL t or APL t , to the most unlikely cases, that is changes in NL t . The next proposition investigates conditions under which APL t will not change. (y ) regardless of the result of q n , implying that y ∈ APL qn t .

(B2) Case y ∈ APL t ∩ Y n : once a query q n is done, it can decrease the maximal score of a label within Y n of at most w n , meaning that at worst we have s max,qn (y) = s max (y) -w n , while we still have

max y ∈Yn\{y} s min,qn t (y ) = max y ∈Yn\{y} s min t (y ) + w n .
Condition (B2) holding implies that s max,qn (y) ≥ max y =y s min,qn t (y ), regardless of the result of q n , hence y ∈ APL qn t .

According to Equation (2.38), a label y ∈ APL t if there is a label y whose minimal score s min t (y ) is higher than s max t (y). Proposition 3 identifies, for a label y ∈ APL t , those conditions under which an increase of the minimal score s min t (y ) for other labels is not sufficient to become higher than s max t (y). Otherwise, y could get out of APL t . The case of PL t is more complex, and since estimating it requires to enumerate selections, the same goes for evaluating whether a query can change it. In particular, we could not find any simple-to-evaluate conditions (as those of Proposition 3) to check whether a query can change PL t , and we are reduced to provide the following definition. This means that evaluating whether a query can change the set PL t will only be doable when K or the cardinality of partial labels neighbours will be small. Definition 3. Given partial label Y n , nearest neighbours N t , possible label set PL t , set Y t and weight w t , a query q n on x n ∈ N t is said to not affect PL t if, for every possible answer y ∈ Y n of the query, we have PL qn=y t = PL t , where PL qn=y t denotes the set PL qn when Y n = y.

The next proposition investigates whether or not a query can change the decision given by Equation (2.29) that we use to make predictions from partially labelled neighbours.

Proposition 4. Given target instance t, nearest neighbour set N t , prediction set θ(t), label set Y t and weight w t , query q n does not affect θ(t) if at least one of following conditions hold

C1 θ(t) ∩ Y n = ∅. C2 ∀y ∈ θ(t) ∩ Y n , s max t (y) -w n > max y ∈Y t \{y} s max t (y ) (2.39)
Proof. (C1) Note that Equation (2.29) is equivalent to

θ(t) = y | y = arg max y∈Y t s max t (y) .
It is clear that for a query q n on x n such that θ(t) ∩ Y n = ∅, then s max,qn t (y) = s max t (y) for all y ∈ θ(t), while the maximal scores for y ∈ θ(t) can only decrease. Hence θ qn (t) = θ(t).

(C2) Since y ∈ θ(t) ∩ Y n , its maximal score either become s max,qn t (y) = s max t (y)w n in the worst case or is unchanged. Then Equation (2.39) guarantees that y ∈ θ qn (t), regardless of the true label of Y n .

Since classifier θ takes decisions based on the maximal number of votes a label can receive, this proposition simply identifies the cases where the reduced score of s max t (y) with y ∈ θ(x) (or non-reduction in case C1) cannot become smaller than another s max t (y ). Finally, we give some conditions under which NL t will not change, which may happen in practice. We will proceed as for Proposition 3, by showing that if y ∈ NL t and satisfies (D1) and (D2), then y ∈ NL qn t , which is equivalent to show that at least one label has a maximal score higher than y, i.e., s min,qn t (y) < max y =y s max,qn t (y ).

(2.40)

Again, note that (D1) and (D2) form a partition of NL t , hence, the two cases can be treated separately. (D2) Case y ∈ NL t and y ∈ Y n : after performing query q n , the minimal score of y can increase to s min,qn t (y) = s min t (y) + w n . Such an increase also implies that for all other labels y ∈ Y n and y = y, we have s max,qn t (y ) = s max t (y ) -w n , while the maximal scores of labels outside Y n remain unchanged. Therefore, satisfying Equation (2.40) in case (D2) is equivalent to

s min t (y) + w n < max max y ∈Yn s max t (y ), max y ∈Yn\{y} s max t (y ) -w n .
According to Equation (2.36), a label y ∈ NL t if its minimal score s min t (y) is higher than the maximal scores of all the other labels y . Proposition 5 identifies, for a given label y ∈ Y t , the conditions under which a decrease of the maximal score s max t (y ) of the other labels is not sufficient to become lower than s min t (y) (otherwise, y could be included in NL t after the query). Condition D1 covers the cases where y is certainly not the true label, while condition D2 covers the cases where it may be the true label. We can now use those propositions and definitions to define the two local effect scores measuring whether querying x n can impact our decision on t: In the next Sections, query schemes corresponding to f P L xn (t) and f AP L xn (t) are denoted shortly by PL and APL, respectively. Since f P L xn (t) uses exact information to identify the ambiguous instances, we can expect the model accuracy to improve faster by using it, yet getting f P L xn (t) is computationally demanding. In practice, f AP L xn (t) offers a cheap approximation that can still provide good results (this will be confirmed by our experiments).

APL t θ(t) NL t PL t Prop. 3 Prop. 4 Prop. 5 Def. 3 x 1 No (y 3 ) No (y 2 ) No (y 3 ) No (y 3 ) t 1 x 2 No (y 3 ) Yes Yes Yes x 3 No (y 2 ) No (y 2 ) Yes Yes x 1 Yes No (y 2 ) Yes Yes t 2 x 2 Yes No (y 1 ) Yes No (y 3 ) x 3 No (y 3 ) No (y 3 ) No (y 3 ) No (y 3 )
f P L xn (t 1 ) f AP L xn (t 1 ) f P L xn (t 2 ) f AP L xn (t 2 ) x 1 0.4 0.4 0.2 0.2 x 2 0 0.3 0.4 0.4 x 3 0.3 0.3 0.4 0.4
f P L xn (t) = 0 if Def.
Tables 2.7 and 2.8 provide an overview of the computations associated to Example 2. Each time a proposition does not hold, we provide between parenthesis the specific answer for which it does not hold.

From Table 2.8, we can see that

f P L x 3 (T) = f AP L x 3 (T) = 0.7, but that f P L x 2 (T) = 0.4 and f AP L
x 2 (T) = 0.7, meaning that the two effect scores given by Equations (2.42) and (2.41) would provide different results. Finally, note that since f P L xn (t) and f AP L xn (t) will be positive as soon as only one proposition or definition does not hold, we do not need to evaluate all of them if we know that one does not hold.

We are going to finish this section with comments on the relation between the approximation approach f AP L and the exact approach f P L . Let us first note that there are queries that can change APL t , however it can not change PL t . In particular, such an example can be derived by focusing on the elements of APL t \ PL t . For example, if we query Y 1 in the example 4 and its true value is y 2 , thus PL t is remain, however we can reduce APL q 1 t = {y 2 , y 3 }. Let us remind that if a query q n can discard a label y from the PL t , hence, there is no replacement d ∈ D whose winners contain y (after performing q n ). Thus, y cannot belong to APL qn t since the definition of s max t (y) (2.11) implies that y is the winner of the replacement (among the possible replacements) which gives the maximum voting score for y. Or in other word, if a query can change PL t , it can also change APL t .

In short, there two approaches would provide different results when the querying process goes along. However, as pointed out the next section, the improvements provided by two approaches appear to be experimentally close. Furthermore, if we have sufficient precise data, we should have NL t = ∅ where APL t = PL t as discussed in A2 of the proposition 2.

Experimental evaluation

This Section presents the experimental setup and the results obtained with benchmark data sets which are used to illustrate the behaviour of the proposed schemes.

Experimental setup

We do experiments on "contaminated" versions of standard, precise benchmark data sets. To contaminate a given data set, we used two methods [START_REF] Hüllermeier | Learning from Ambiguously Labeled Examples[END_REF]:

Random Model: Each training instance is contaminated randomly with probability . In case an example x n is contaminated, the set Y n of candidate labels is initialized with the original label y n , and all other labels y ∈ Y \ {y n } are added with probability η, independently of each other.

Bayes Model: In order to take the dependencies between labels (more likely to happen in practice) into account, a second approach is used. First, a Naive Bayes classifier θ is trained using the original data (precise labels) so that each label is associated to a posterior probability p θ (y | x n ). As before, each training instance will be contaminated randomly with probability . In case of contamination, the true label is retained, the other labels are re-arranged according to their probabilities and the k-th label is included in the set of labels with probability 2kη

|Y| . Note that in Bayes model, the probability 2kq /|Y| can exceed 1 when parameter is greater than 0.5. However, this value of 2kη /|Y| ensures that the expected cardinality of the partial labels, in case of contamination, is 1 + (M -1)η for both contamination models, making them comparable [START_REF] Hüllermeier | Learning from Ambiguously Labeled Examples[END_REF]. In practice, we lowered 2kη /|Y| to 1 once it goes over it.

Results have been obtained for 15 UCI data sets described in Table 2.9. Three different values for K (3, 6 and 9) have been used for all experiments. The weight

w t k for an instance t is w t k = 1 -(d t k )/( K j=1 d t j
) with d t j the Euclidean distance between x t j and t. As usual when working with Euclidean distance based K-nn, data is normalized.

We use a three-folds cross-validation procedure: each data set is randomly split into 3 folds. Each fold is in turn considered as the test set, the other folds are used for the training set. The training set is contaminated according to one of the models with two combinations of ( , η) parameters: ( = 0.7, η = 0.5) and ( = 0.9, η = 0.9), which correspond to low and high levels of partiality. The error rate is computed as the average error obtained from the 3 test sets. This process is repeated 10 times and results are also averaged. For each data set, the number of queries I has been fixed to 10% of the number of training data.

Similarly to what is done in active learning, the pool of instances to be queries U is identical the set of partially labelled instances, i.e,

U = {(x n , Y n ) | (x n , Y n ) ∈ D, |Y n | > 1}.
The target set T used to assess the querying effects is defined as the data space with imperfect information, i.e, T = {(x n , ?) apply the querying process using only information from training data set D, instead of requiring a separated validation/target set.

| (x n , Y n ) ∈ U}.
RD MP/ACT MW APL PL O(1) O(T ) O(T K) O(T M (M + K)) O(T M K )
To evaluate the efficiency of the proposed query schemes (MW, PL and APL), we compare our results with 3 baseline schemes:

-RD: a query is picked up at random from the pool;

-MP: the one with the largest partial label is picked up; -ACT: partially labelled instances are considered as unlabeled ones and ModFF, a classical active learning scheme [START_REF] Joshi | Coverage optimized active learning for k-NN classifiers[END_REF], is used to query instances. ModFF selects the queries in such a way that all target data have labelled samples at a bounded maximum distance.

The complexity of each scheme for a single query is given in Table 2.10. Note that the more computationally demanding PL scheme was only tested for the case K = 3.

Results

For each scheme, the error rate after querying 10% of the number of training data has been computed and the schemes have been ranked according to this error rate. The average error rates and the average ranks of the schemes over the 15 data sets are given in Table 2.11.

A Friedman test done over the ranks indicates that, in all settings, there are significant evidence that not all algorithms are equivalent (except for the random setting with low partiality that gave a p-value of 0.002, all other are below 10 -5 ). Nemenyi post-hoc test performed to identify the differences between the schemes indicate that our proposed schemes (MW, PL, APL) work almost systematically better than any baseline, with APL having a significant positive difference in pairwise tests.

Random

Bayes Random Bayes K Scheme = 0.7 = 0.7 = 0.9 = 0.9 η = 0.5 η = 0.5 η = 0.9 η = 0.9 A noticeable exception is when the partiality is low and K = 9. However in this case it can be seen from Table 2.11 that all querying techniques only improve results in a very marginal way (with an accuracy gain around 1% for all methods).

A second look at Table 2.11 confirms that the proposed methods really provide an edge (in terms of average accuracy gain) in the situations where ambiguous situations are the most present, that is when:

-K is low, in which case even a few partial labels among the neighbours may lead to ambiguous situations, a fact that is much less likely when K gets higher.

-There is a large amount of partial labels, in which case increasing the value of K will have a very limited effect on the number of ambiguous cases.

Both cases are of practical interest, as even if picking a higher value of K is desirable when having low partiality, it may be computationally unaffordable. Finally, we can notice that the Bayes contamination induces slightly more ambiguity in the data sets, as more likely classes (hence similar labels in a given region of the input space) have more chances to appear in the contaminated labels. Bayes contamination also seem somehow more realistic, as experts or labellers will have a tendency to provide sets of likely labels as partial information.

Perspectives on querying partially featured data

Yet, in the case of partially featured data and precisely featured test data, by using the specific properties of the partially ordered sets and the monotonicity of the extreme distances, we can perform the querying procedure with a manageable complexity (polynomial time). However, no significant improvement has been observed from the experiments we did on the case of partially featured data. Let us note that in Section 2.2, we restrict ourselves to the unweighted version of the maximax. Thus, the unpromising experimental results in this very specific case is somehow insufficient to envision any conclusion about the performance the maximax in the more generic settings, e.g, to investigate the performance of the weighted version or to explore the general setting of partially featured data where both training and test data can be partially featured. On the other hand, the computations of the possible and necessary label sets, summarizing in this section, might suggest extensions/adaptations for other generic settings which are still left opened.

Determining the possible label set

Let us note that we will only consider the setting consists of a partially featured training data set

D = {(X n , y n )} N n=1
, where X n = (X

s d t (y i ) = K, (2.43)
and

min s d t (y m ), s max t (y i ) ≥ s d t (y i ) ≥ s min t (y i ), i = 1, . . . , M. (2.44)
The condition M i=1 s d t (y i ) = K simply ensures that d is a legal replacement. The constraint (2.44) then ensures that all other labels have a score lower than s d t (y m ) for the replacement d (note that min(s d t (y m ), s max t (y m )) = s d t (y m )), and that their scores are bounded by Eq. (2.27).

The question is now to know whether we can instantiate such a vector making a winner of y m . To achieve this task, we will first maximise its score, such that

s d t (y m ) = s max t (y m ).
The scores of all other labels y i is also lower-bounded by s min t (y i ), meaning that among the K neighbours we choose in d, only K -s max t (y m ) -M i=1,i =m s min t (y i ) remain to be fixed in order to specify the score vector. Then we can focus on the relative difference between s min (y i ) and the additional number of chosen neighbours voting for y i . Solving the problem defined by Eqs. (2.43), (2.44) is equivalent to determine a score vector (w(y 1 ), . . . , w(y m-1 ), w(y m+1 ), . . . , w(y M ))

with w(y i ) = s d t (y i ) -s min t (y i ), ∀i = m, s.t. M i=1,i =m w(y i ) = K-s max t (y m ) - M i=1,i =m s min t (y i ), (2.45
) (y i ), then there no chance for y m to be a possible label.

min s max t (y m ), s max t (y i ) -s min t (y i ) ≥ w(y i ) ≥ 0, ∀i = m. ( 2
We will now give a proposition allowing to determine in an easy way if a label belongs to the set of possible labels.

K -s max t (y m ) - M i=1,i =m s min t (y i ) = M i=1,i =m w(y i ).
If we replace w(y i ) by its upper bound (2.48), we get the following inequality

K -s max t (y m ) - M i=1,i =m s min t (y i ) ≤ M i=1,i =m min s max t (y m ), s max t (y i ) - M i=1,i =m s min t (y i ),
that is equivalent to the relation

K ≤ s max t (y m ) + M i=1,i =m min s max t (y m ), s max t (y i ) .
(⇐) Let us now show that if the conditions given by Eqs. (2.45)-(2.46) are satisfied, then y m ∈ PL t . First remark that, once we have assigned the maximal score to y m and the minimal ones to the other labels, there remain

K -s max t (y m ) - M i=1,i =m s min t (y i )
neighbours to choose from. We also know from (2.46) that at most

M i=1,i =m min s max t (y m ), s max t (y i ) -s min t (y i )
neighbours can still be affected to other labels than y m without making it a loser. Clearly, if

K -s max t (y m ) - M i=1,i =m s min t (y i ) ≤ M i=1,i =m min s max t (y m ), s max t (y i ) -s min t (y i ) ,
we can reach the number of K neighbours without making y m a loser, or inversely letting y m be a winner for the chosen replacement, meaning that y m ∈ PL t .

Example 5. Let us continue with the data set in Example 1 with value K = 3. From Table 2.1 and the interval ranks (2.20), we can see that

PN t = {(X 1 , a), (X 2 , b), (X 3 , c), (X 4 , b)}, NN t = {(X 2 , b)}.
Then the maximum and minimum scores for all the labels are

(s min t (a), s min t (b), s min t (c)) = (0, 1, 0) (s max t (a), s max t (b), s max t (c)) = (1, 2, 1).
We will now determine whether a given label in Y = {a, b, c} is a possible label. For label a, we have that

s max t (a) + min s max t (a), s max t (b) + min s max t (a), s max t (c) = 1 + 1 + 1 = 3 ≥ K,
hence a ∈ PL t . The same procedure applied to b and c gives the result PL t = {a, b, c}.

Determining the necessary label set

Let us now focus on characterizing the set NL t defined in (2.14). The following propositions gives a very easy way to determine it, by simply comparing the minimum score of a given label y m to the maximal scores of the others.

s d t (y m ) = K - j =m s max t (y j ) = s min t (y m ) < s max t (y i ) = s d t (y i ).
s d t (y m ) ≥ min d∈D (s d t (y m )) ≥ max d∈D (s d t (y i )) ≥ s d t (y i ), ∀i = m,
which is sufficient to get the proof.

Example 6. Consider the data set given in Example 5 with the maximum and minimum scores of the labels are

(s min t (a), s min t (b), s min t (c)) = (0, 1, 0) (s max t (a), s max t (b), s max t (c)) = (1, 2, 1).
Then (2.49) implies that the necessary label set NL t = {b}.

Conclusion

Our first contribution in this Chapter is an implementation of the maximax approach for the case of partially featured data. Our implementation is computationally tractable and the first experiments indicate that there are cases when the maximax approach can bring a real advantage. Thus, motivating further works on broadening the applications of the maximax approach. Let us note that, we have focused on the setting where only training data are partially specified. Yet, developing similar decision rules for the generic setting, i.e, both training and test data are partially featured, could be a potential direction. Detailing it could be complicated since defining the partial order (2.17) is still a challenge. One reason is that if we have a partially featured test instance t, we are no-longer allowed to freely choose and compare the possible positions of its neighbours.

Considering the active learning problem, we have proposed two querying schemes, both based on the computation of an effect score quantifying the impact of a disambiguation on the final result, to query partially labelled data. Our first strategy (neighbour-based) consists in selecting an instance when it is involved in many decisions. A more refined strategy (indecision-based) consists in selecting an instance when it can potentially reduce the ambiguity of one or several decisions. This second strategy is more complex from a computational point of view, and we have therefore proposed an approximate scheme leading to very close performance. The experiments have shown that the accuracy of the maximax method is significantly improved by querying partial label instances and that indecision-based querying strategies are the best-performing schemes.

Yet, our attempt on developing a similar querying scheme for the specific setting where only training data can be partially featured has not provided any significant improvement. The perspectives we presented could be useful for further tackling both learning and active learning problem in the generic setting where both training and test data are partially featured (and the weighted version of Maximax is employed to make prediction). Thus, there are at least two open issues, in order to completely tackle these problems:

1. to investigate the decision rules for the generic setting where both training and test data can be imprecise.

2. to develop efficient subsequent techniques to determine the possible and necessary label sets and its potential changes when the querying process goes along.

Chapter 3

Racing Algorithms

This Chapter focuses on imprecision modeling in the problem of learning from partially specified data. We first generalise the loss function to cope with partial data and highlight the potential issue of obtaining multiple optimal models, i.e, a set of undominated models. The size of this undominated model set will be considered as a degree of imprecision due to the presence of partial data. We thus focus on developing active learning schemes to identify the partially specified data that should be queried to quickly reduce the undominated model set. We are going to present a generic querying scheme inspired by the racing algorithms and then implement it for two specific settings: binary SVM and decision trees.

Loss function and expected risk for partial data

Let us remind that, in classical supervised setting, the goal of the learning approach is to extract a model θ * : X → Y within a set Θ of models from a data set D = {(x n , y n )} N n=1 . The empirical risk R(θ | D) associated to a model θ is then evaluated as

R(θ | D) = N n=1 (y n , θ(x n )), (3.1)
where (y n , θ(x n )) is the loss of predicting θ(x n ) when observing y n . The selected model is then the one that minimizes (3.1), that is

θ * = arg min θ∈Θ R(θ | D). (3.2)
Another way to see the model selection problem is to say that a model θ l is better than

θ k (denoted θ l θ k ) if R(θ k | D) -R(θ l | D) > 0, (3.3)
or, in other words, if the risk of θ l is lower than the risk of θ k .

In this proposal, 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 (3.1), (3.2) and (3.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. That is, if we extend Equation (3.1) to a lower bound

R(θ | D) = inf (xn,yn)∈(Xn,Yn) N n=1 (y n , θ(x n )) (3.4) = N n=1 inf (xn,yn)∈(Xn,Yn) (y n , θ(x n )) := N n=1 (Y n , θ(X n ))
and an upper bound

R(θ | D) = sup (xn,yn)∈(Xn,Yn) N n=1 (y n , θ(x n )) (3.5) = N n=1 sup (xn,yn)∈(Xn,Yn) (y n , θ(x n )) := N n=1 (Y n , θ(X n ))
then the optimal minimin θ * mm and minimax θ * mM models are

θ * mm = arg min θ∈Θ R(θ | D) and θ * mM = arg min θ∈Θ R(θ | D).
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 in Proceedings of the Tenth International Symposium on Imprecise Probability: Theories and Applications[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. However, in this proposal, we are not primarily interested into learning a single model from partial data, but we want to determine which partial data makes the potentially best models incomparable, in order to complete such data through queries. To define such a set of potentially optimal models, we will say that a model θ l is better than

θ k (still denoted θ l θ k ) if R(θ k-l | D) = inf (xn,yn)∈(Xn,Yn) R(θ k | D) -R(θ l | D) > 0, (3.6)
which is a direct extension of Equation (3.3). That is, θ l θ 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

Θ * = {θ ∈ Θ | ∃θ ∈ Θ s.t. θ θ} (3.7)
the set of undominated models within Θ, that is the set of models that are maximum with respect to the partial order .

Example 7. Assuming that Θ = {θ 1 , θ 2 } (the models could be decision stumps, i.e, one-level decision trees [START_REF] Rodríguez | Boosting recombined weak classifiers[END_REF], we would have that θ 2 = θ * mM is the minimax model and

θ 1 = θ * mm X 2 X 1 1 2 3 4 5 m 2 m 1 [R(θ 1 | D), R(θ 1 | D)] = [0, 5] [R(θ 2 | D), R(θ 2 | D)] = [1, 3] R(θ 1-2 | D) = -1 R(θ 2-1 | D) = -2

Our generic racing approach

We are going to present a generic querying scheme based on racing ideas and then investigate the computational issue of such a scheme for the specific settings of binary SVM and decision trees.

Both the minimin and minimax approaches have the same goal: obtaining a unique model from partially specified data. Our objective in this proposal is different: we want to query those data that will increase the most the accuracy of a learnt model. To do so, we propose to start from a set Θ of potentially optimal models, and to identify in a racing scheme those data that will help the most to select the best model within Θ, hence are likely to be determinant in differentiating model quality. Much like querying-by-committee in classical active learning [START_REF] Mamitsuka | Query Learning Strategies Using Boosting and Bagging[END_REF], the purpose of the race is here only to select the query to be made, as Θ is unlikely to contain the risk minimizing model. Once the queries have been made, a new model should be learned from the completed data set. How we quantify the usefulness of a query within the race is formalized in what follows.

Let us recall that we have been considering the setting that X = X 1 × . . . × X P is a Cartesian product of P real spaces R, 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 n ⊆ 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 , thanks to 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 θ l 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(θ l | D), R(θ l | D)],
which will be the case only if the query can have an effect on the interval

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

This can be formalized by two functions, E q p n : Θ → {0, 1} and J q p n : Θ × Θ → {0, 1} such that:

E q p n (θ l ) = 1 if ∃x p n ∈ X p n that reduces [R(θ l | D), R(θ l | D)] 0 else (3.8)
and

J q p n (θ k , θ l ) = 1 if ∃x p n ∈ X p n that increases R(θ k-l | D) 0 else.
(3.9)

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 θ l performances, while J q p n (θ k , θ l ) informs us whether the query can help to differentiate θ l and θ k . If we denote by k * = arg min k∈{1,...,S} R(θ k | D) 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 (θ k * ) + k =k * J q p n (θ k , θ k * ). (3.10)
This value or utility is then used to assess which data (label or feature) should be queried next. It should be noticed that scores (3.8) and (3.9) 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 most natural and simple.

Example 8. In Figure 3.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 (θ 1 ) = E q 3 4 (θ 2 ) = 1 and J q 3 4 (θ 1 , θ 2 ) = J q 3 4 (θ 2 , θ 1 ) = 0. -E q 2 3 (θ 1 ) = 1, E q 2 3 (θ 2 ) = 0 and J q 2 3 (θ 1 , θ 2 ) = J q 2 3 (θ 2 , θ 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 θ 2 better than θ 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

{(x n , y n ) ∈ (X n , Y n )} N
n=1 and then to learn an optimal model for each such selection. Algorithm 2 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 query-by-committee approaches [START_REF] Mamitsuka | 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.

Algorithm 2: One iteration of the racing algorithm to query data

Input: data (X n , Y n ), set Θ * := {θ 1 , . . . , θ S } of models Output: updated data and set of models

1 k * = arg min k∈{1,...,S} R(θ k | D); 2 foreach query q p n do 3 V alue(q p n ) = E q p n (θ k * ) + k =k * J q p n (θ k , θ 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, l ∈ {1, . . . , S} × {1, . . . , S}, k = l do 7 Compute R(θ k-l | D) ; 8 if R(θ k-l | D) > 0 then remove θ k from Θ * ;

Application to SVM

In this Section, we illustrate our proposed setting and its potential interest with the popular SVM algorithm. We separate the two cases of interval-valued features from set-valued labels, for three reasons: (i) we can expect that imprecision in both aspects is less likely to happen in practice, (ii) this makes the exposure of the methods easier to follow, and (iii) considering both cases at once would quickly induce a too important imprecision in the results. We leave the combination of the two approaches to the reader, especially since binary SVM are here used as an illustration of our general approach.

Interval-valued features

In the binary SVM setting [START_REF] Burges | A tutorial on support vector machines for pattern recognition[END_REF], the input space X = R P is the real space and the binary output space is Y = {-1, 1}, where -1, 1 encode the two possible classes. The model θ l = (w l , c l ) corresponds to the maximum-margin hyperplane w l x + c l with w l ∈ R P and c l ∈ R. For convenience sake, we will use (w l , c l ) and θ l interchangeably from now on. We will also focus in this section on the case of imprecise features and precise labels, and will denote y n the label of training instances. We will also focus on the classical 0-1 loss function defined as follows for an instance (x n , y n ):

(y n , θ l (x n )) = 0 if y n • θ l (x n ) ≥ 0 1 if y n • θ l (x n ) < 0, := l (y n , x n ) (3.11)
where θ l (x n ) = w l x n + c l , and l (y n , x n ) is used as a short notation for (y n , θ l (x n )).

Similarly, the extreme losses (y n , θ l (X n )) and (y n , θ l (X n )) are shortened to l (y n , X n ) and l (y n , X n ), respectively.

Instances inducing imprecision in empirical risk

Before entering into the details of how single risk bounds [R(θ l | D), R(θ l | D)] and pairwise risk bounds R(θ k-l | D) given by Equations (3.4)-(3.6), and query effects E q p n (θ l ) and J q p n (θ k , θ l ) given by Equations (3.8)-(3.9) can be estimated in practice, we will first investigate under which conditions an instance (X n , y n ) induces imprecision in the empirical risk. Such instances are the only ones of interest here, since if

l (y n , X n ) = l (y n , X n ) = l (y n , X n ), then E q p
n (θ l ) = 0 for all p = 1, . . . , P . Furthermore, if an instance (X n , y n ) is precise w.r.t both θ k and θ l , then J q p n (θ k , θ l ) = 0 for all p = 1, . . . , P . Thus, only instances which are imprecise w.r.t at least one model are interested when determining J q p n (θ k , θ l ). Definition 4. Given a SVM model θ l , an instance (X n , y n ) is called an imprecise instance w.r.t. θ l if and only if

∃x n , x n ∈ X n s.t θ l (x n ) ≥ 0 and θ l (x n ) < 0.
(3.12)

Instances that do not satisfy Definition 4 will be called precise instances (w.r.t. θ l ). Being precise means that the sign of θ l (x n ) is the same for all x n ∈ X n , which implies that the loss l (y n , X n ) = l (y n , X n ) is precisely known. The next example illustrates the notion of (im)precise instances. Example 9. Figure 3.2 illustrates a situation with two models and where the two different classes are represented by grey (y = +1) and white (y = -1) colours. From the figure, we can say that (X 1 , y 1 ) is precise w.r.t both θ 1 and θ 2 , (X 2 , y 2 ) is precise w.r.t θ 1 and imprecise w.r.t θ 2 , (X 3 , y 3 ) is imprecise w.r.t both θ 1 and θ 2 and (X 4 , y 4 ) is imprecise w.r.t θ 1 and precise w.r.t θ 2 .

Determining whether an instance is imprecise w.r.t. θ l is actually very easy in practice. Let us denote by

θ l (X n ) := inf xn∈Xn θ l (x n ) and θ l (X n ) := sup xn∈Xn θ l (x n ) (3.13)
the lower and upper bounds reached by model θ l over the space X n . The following result characterizing imprecise instances, as well as when a hyperplane θ l (x n ) = 0 intersects with a region X n , follows from the fact that the image of a compact set by a continuous function is also compact.

Proposition 8. Given θ l (x n ) = w l x n + c l and the set X n , then (X n , y n ) is imprecise w.r.t. θ l if and only if θ l (X n ) < 0 and θ l (X n ) ≥ 0. (3.14)
Furthermore, we have that the hyperplane θ l (x n ) = 0 intersects with the region X n if and only if (3.14) holds. In other words, ∃x n ∈ X n s.t. θ l (x n ) = 0.

Proof. Since continuous functions preserve compactness and connectedness [START_REF] Fitzpatrick | Advanced calculus[END_REF], then the image f (X) = Y of a compact and connected set X is compact and connected. Furthermore, a set on R P is compact if and only if it is closed and bounded (Heine-Borel Theorem [START_REF] Raman-Sundström | A pedagogical history of compactness[END_REF]), then X is a closed, bounded and connected set which is exactly a closed interval. Or in other words, we have that

θ l (X n ) = θ l (X n ), θ l (X n ) ,
is an interval consisting of every possible values that can take θ l (x n ) for x n ∈ X n . That (3.14) is equivalent to (3.12) then immediately follows. Also, we have that

∃x n ∈ X n s.t. θ l (x n ) = 0 if and only if 0 ∈ θ l (X n ), θ l (X n ) .
This proposition means that to determine whether an instance (X n , y n ) is imprecise, we only need to compute values θ l (X n ) and θ l (X n ), which can be easily done using Proposition 9. Proposition 9. Given (X n , y n ) with X p n = [a p n , b p n ] and SVM model (w l , c l ), we have

θ l (X n ) = w p l ≥0 w p l b p n + w p l <0 w p l a p n + c l θ l (X n ) = w p l ≥0 w p l a p n + w p l <0 w p l b p n + c l .
Proof. Since θ l (x n ) is a linear function, it is monotonic in each dimension, hence the extreme values are obtained at points x n ∈ × P p=1 {a p n , b p n }. Furthermore, θ l (x n ) decreases (increases) w.r.t x p n if w p l < 0 (w p l > 0). Hence, Proposition 9 holds. Again, it should be noted that only imprecise instances are of interest here, as these are the only instances that, once queried, can result in an increase of the lower empirical risk bounds. We will therefore focus on those in the next sections.

Example 10. Consider the model θ l on a 3-dimensional space given by w l = (2, -1, 1) and the partial instance

X n = [1, 3] × [2, 5] × [1, 2]. In this case, we have θ l (X n ) = 1 × 2 + 5 × -1 + 1 × 1 = -2, θ l (X n ) = 3 × 2 + 2 × -1 + 2 × 1 = 6,
hence the instance X n is imprecise with respect to θ l .

Empirical risk bounds and single effect

We are now going to investigate the practical computation of R(θ l | D), R(θ l | D), as well as the value E q p n (θ l ) of a query on a model θ l . Equations (3.4) (resp. (3.5)) implies that the computation of R(θ l | D) (resp. R(θ l | D)) can be done by first computing l (y n , X n ) (resp. l (y n , X n )) for n = 1, . . . , N and then summing the obtained values. This means that we can focus our attention on computing l (y n , x n ) and l (y n , x n ) for a single instance, as obtaining R(θ l | D), R(θ l | D) from them is straightforward. Note that we have l (y n , X n ) = 0 and l (y n , X n ) = 1 if and only if X n is imprecise w.r.t. θ l , a fact that can easily be checked using Proposition 8. The bounds of the loss interval for the model θ l and datum (X n , y n ) is

[ l (y n , X n ), l (y n , X n )] =      [0, 0] if min(y n • θ l (X n ), y n • θ l (X n )) ≥ 0 [0, 1] if θ l (X n ) • θ l (X n ) < 0 [1, 1] if max(y n • θ l (X n ), y n • θ l (X n )) < 0 (3.15)
Let us now focus on estimating the effect of a query. As with the loss bounds, the only situation where a query q p n can affect the empirical risk bounds, and hence the only situation where E q p n (θ l ) = 1, is when the interval [ l (y n , X n ), l (y n , X n )] can be reduced by querying X p n . Therefore we can also focus on a single instance to evaluate it.

In the case of 0-1 loss, the only case where E q p n (θ l ) = 1 is the one where the imprecise loss [ l (y n , X n ), l (y n , x n )] goes from [0, 1] before the query to a precise value after it, or in other words if there is x p n ∈ X p n such that X q p n n = × p =p X p n × {x p n } is precise w.r.t. θ l . According to Proposition 8, this means that either θ l (X q p n n ) should become positive, or θ l (X q p n n ) should become negative after a query q p n . The conditions to check whether this is possible are given in the next proposition. Proposition 10. Given (X n , y n ) with X p n = [a p n , b p n ] and a model θ l s.t. X n is imprecise, then E q p n (θ l ) = 1 if and only if one of the following conditions holds

θ l (X n ) ≥ -|w p l |(b p n -a p n ) (3.16) or θ l (X n ) < |w p l |(b p n -a p n ). (3.17)
Proof. Let us concentrate on the first condition (the second one can be proved similarly). If we denote by θ l (X q p n n ) the lower bound reached by θ l on X q p n n (the set resulting from the query answer), then we have the following inequality

θ q p n l (X q p n n ) ≤ θ l (X n ) + |w p l |(b p n -a p n )
giving us a tight upper bound for it. Indeed, if w p l ≥ 0, then θ l is obtained for x p n = a p n (by Proposition 9), and it can increase by at most w p l (b p n -a p n ) if the result of the query q p n is x p n = b p n (the case w p l ≤ 0 is similar). Since θ l (X n ) is known to be negative (from Proposition 8 and the fact that X n is imprecise), it can only become positive after a query

q p n if θ l (X n ) + |w p l |(b p n -a p n
) is positive. Finally, by investigating the change of sign(w p l ), we have:

B1: q p n can change the sign of θ l (x n ) iff θ l (x n ) + w p l (b p n -a p n ) ≥ 0 if w p l ≥ 0, θ l (x n ) -w p l (b p n -a p n ) ≥ 0 if w p l < 0. B2: q p n can change the sign of θ l (x n ) iff θ l (x n ) -w p l (b p n -a p n ) < 0 if w p l ≥ 0 θ l (x n ) + w p l (b p n -a p n ) < 0 if w p l < 0. R(θ l | D), R(θ l | D)
, needed in the line 1 of Algorithm 2 to identify the most promising model k * , are computed easily by summing over all training instances the intervals [ l (y n , X n ), l (y n , X n )] given by Equation (3.15), while Equations (3.16)-(3.17) give easy ways to estimate the values of E q p n (θ k * ), needed in line 3 of Algorithm 2. Example 11. Let us consider again Example 10, and check whether querying the last (p = 3) or second dimension may induce some effect on the emprical risk bounds. Using Proposition 10, we have for q 3 n that

θ l (X n ) = -2 < -1 × (2 -1) and θ l (X n ) = 6 > 1 × (2 -1),
hence E q 3 n (θ l ) = 0, as none of the conditions are satisfied. We do have, on the contrary, that

θ l (X n ) = -2 ≥ -1 × (5 -2), hence E q 2 n (θ l ) = 1. Indeed, if x 2 n = 2
(the query results in the lower bound), then the model becomes positive for any replacement of X

q 2 n n = [1, 3] × 2 × [1, 2].

Pairwise risk bounds and effect

Let us now focus on how to compute, for a pair of models θ k and θ l , whether a query q p n will have an effect on the value R(θ k-l | D). For this, we will have to compute R(θ k-l | D), which is a necessary step to estimate the indicator J q p n (θ k , θ l ) of a possible effect of q p n . To do that, note that R(θ k-l ) can be rewritten as

R(θ k-l | D) = inf xn∈Xn,n=1,...,N (R(θ k | D) -R(θ l ) | D) = N n=1 k-l (y n , X n ) (3.18) with textwith k-l (y n , X n ) = inf xn∈Xn k (y n , x n ) -l (y n , x n ) , (3.19)
meaning that computing R(θ k-l | D) can be done by summing up k-l (y n , X n ) over all X n , similarly to R(θ l | D) and R(θ l | D). Also, J q p n (θ k , θ l ) = 1 if and only if q p n can increase k-l (y n , X n ). We can therefore focus on the computation of k-l (y n , X n ) and its possible changes.

First note that if X n is precise w.r.t. both θ k and θ l , then k (y n , X n )l (y n , X n ) is a well-defined value, as each loss is precise, and in this case J q p n (θ k , θ l ) = 0. Therefore, the only cases of interest are those where X n is imprecise w.r.t. at least one model. We will first treat the case where it is imprecise for only one, and then we will proceed to the more complex one where it is imprecise w.r.t. both. Note that imprecision with respect to each model can be easily established using Proposition 8.

Case 1: Imprecision with respect to one model

Let us consider the case where X n is imprecise w.r.t. either θ k or θ l . In each of these two cases, the loss induced by (X n , y n ) on the model for which it is precise is fixed. Hence, to estimate the lower loss k-l (y n , X n ), as well as the effect of a possible query q p n , we only have to look at the model for which

(X n , y n ) is imprecise. The next proposition establishes the lower bound k-l (y n , X n ), necessary to compute R(θ k-l ). Proposition 11. Given (X n , y n ) with X p n = [a p n , b p n ]
and two models θ k and θ l s.t (X n , y n ) is imprecise w.r.t. one and only one model, then we have

k-l (y n , X n ) = k (y n , X n ) -1 if X n imprecise w.r.t. θ l (3.20) k-l (y n , X n ) = 0 -l (y n , X n ) if X n imprecise w.r.t. θ k . (3.21)
Proof. We will only prove Equation (3.20), the proof for Equation (3.21) being similar. First note that if X n is precise with respect to θ k , then k (y n , X n ) is precise. Second, the value of l (y n , X n ) ∈ {0, 1}, since X n is imprecise with respect to θ l , hence the lower bound is obtained for x n ∈ X n such that l (y n , x n ) = 1.

We kept the 0 in Equation (3.21) to make clear that we take the lower bound of the loss w.r.t. θ k , and the precise value of l (y n , X n ). Let us now study under which conditions a query q p n can increase k-l (y n , X n ), hence under which conditions J q p n (θ k , θ l ) = 1. The two next propositions respectively address the case of imprecision w.r.t. θ k and θ l . Given a possible query q p n on X n , the only possible way to increase k-l (y n , X n ) is for the updated X q p n n to become precise w.r.t. the model for which X n was imprecise, and moreover to be so that l (y n ,

X q p n n ) = 0 ( k (y n , X q p n n ) = 1) if X n is imprecise w.r.t. θ l (θ k ). Proposition 12. Given (X n , y n ) with X p n = [a p n , b p n ]
and two models θ k and θ l s.t. (X n , y n ) is imprecise w.r.t. θ l , the question q p n is such that J q p n (θ k , θ l ) = 1 if and only if one of the two following conditions holds

y n = 1 and θ l (X n ) ≥ -|w p l |(b p n -a p n ) (3.22)
or

y n = -1 and θ l (X n ) < |w p l |(b p n -a p n ). (3.23)
Proof. First note that if X n is imprecise w.r.t. θ l , then the only case where k-l (X n ) increases is when the updated instance X q p n n is precise w.r.t. θ l after the query q p n is performed and the precise loss becomes l (y n , X q p n n ) = 0. Let us consider the case y n = 1 (the case y n = 0 is similar). To have l (y n , X q p n n ) = 0, we must have θ l (X q p n n ) ≥ 0. Using the same argument as in Proposition 10, we easily get the result.

Proposition 13. Given (X n , y n ) with X p n = [a p n , b p n ]
and two models θ k and θ l s.t. (X n , y n ) is imprecise w.r.t. θ k , the query q p n is such that J q p n (θ k , θ l ) = 1 if and only if one of the two following condition holds

y n = 1 and θ k (X n ) < |w p k |(b p n -a p n ) (3.24)
or

y n = -1 and θ k (X n ) ≥ -|w p k |(b p n -a p n ). (3.25)
The proof is analogous to the one of Proposition 12. In summary, if X n is imprecise w.r.t. only one model, estimating J q p n (θ k , θ l ) comes down to identify whether the X n can become precise with respect to such a model, in such a way that the lower bound is possibly increased. Propositions 12 and 13 show that this can be checked easily using our previous results investigated in the Proposition 10 concerning the empirical risk. Actually, in this case, the problem essentially boils down to the problem of determining the empirical risk bounds and single effect.

Case 2: Imprecision with respect to both models Given X n and two models θ k , θ l , we define :

θ k-l (X n ) = θ k (X n ) -θ l (X n ).
(3.26)

We thus have:

θ k-l (X n ) > 0 if θ k (x n ) -θ l (x n ) > 0 ∀x n ∈ X n (3.27) θ k-l (X n ) < 0 if θ k (x n ) -θ l (x n ) < 0 ∀x n ∈ X n . (3.28)
In the other cases, this means that there are x n , x n ∈ X n for which the model difference have different signs. The reason for introducing such differences is that, if

X 2 X 1 X n θ 1 θ 2 (a) θ1-2(Xn) > 0 X 2 X 1 X n θ 1 θ 2 (b) m1-2(Xn) < 0 X 2 X 1 X n θ 1 θ 2 (c) Non-constant sign
θ k-l (X n ) > 0 or θ k-l (X n ) < 0,
then not all combinations in {0, 1} 2 are possible for the pair ( k (y n , x n ), l (y n , x n )), while they are in the other case. These various situations are depicted in Figure 3.3, where the white class is again the negative one (y n = -1).

Since θ k (x n ) -θ l (x n
) is also of linear form (with weights w p k -w p l ), we can easily determine whether the sign of θ k-l (X n ) is constant: it is sufficient to compute the interval

inf xn∈Xn (θ k (x n ) -θ l (x n )), sup xn∈Xn (θ k (x n ) -θ l (x n )) that can be computed similarly to [θ l (X n ), θ l (X n )] in the Proposition 9. If zero is not within this interval, then θ k-l (X n ) > 0 if the lower bound is positive, otherwise θ k-l (X n ) < 0 if
k-l (y n , X n ) =      min(0, -y n ) if θ k-l (X n ) > 0 min(0, y n ) if θ k-l (X n ) < 0 -1 if θ k-l (X n ) can take both signs (3.29)
Proof. First note that when neither θ k-l (X n ) > 0 nor θ k-l (X n ) < 0 hold, then there are values x n for which θ k (x n ) and θ l (x n ) are either positive and negative, or negative and positive, or of the same sign. Hence there is always a value x n such that

k (y n , x n ) = 0 and l (y n , x n ) = 1.
Let us then deal with the situation where θ k-l (X n ) > 0 (the case θ k-l (X n ) < 0 can be treated similarly). In this case, there are values x n ∈ X n such that θ k (x n ) and θ l (x n ) have the same sign (0/1 loss difference is then null), or θ k (x n ) is positive and θ l (x n ) negative, but no values for which θ k (x n ) is negative and θ l (x n ) positive. When θ k (x n ) is positive and θ l (x n ) negative, the loss difference is -1 if y n = +1, and

1 if y n = -1.
The next question is to know under which conditions a query q p n can increase k-l (y n , X n ) (or equivalently R(θ k-l )), or in other words to determine a pair (n, p) s.t J q p n (θ k , θ l ) = 1. Proposition 14 tells us that k-l (y n , X n ) can be either 0 or -1 if θ k-l (X n ) > 0 or θ k-l (X n ) < 0, and is always -1 if θ k-l (X n ) can take both signs. The next proposition establishes conditions under which k-l (y n , X n ) can increase.

Set-valued labels

This section investigates the computations of racing algorithms to query set-valued labels when using binary SVM with precise features and when labels are partially given. Let us first note that, in the binary case, the problem of querying partial label data is identical to classical active learning as label data is either precise or fully partial (completely missing). One suitable technique in such a case is queryby-committee [START_REF] Seung | Query by committee[END_REF]. However, the strategies of query-by-committee technique and our racing technique are different. The previous one focus on missing labels that are the least consensual or the most ambiguous among a given set of models, while racing algorithms focus on labels having the most effect on reducing the uncertainty about the best potential model performance, as well as its difference to other models. From such intuitions, we could hope that, in practice, query-by-committee provide a quick reduction on the size of the set of undominated models while racing algorithms give faster convergence on determining the best potential model. In any case, it is worth exploring whether the two techniques perform similarly or if they show significant differences.

Before investigating the detailed computations of racing algorithms, let us recall that we focus here on binary SVM with 0/1 loss function (3.11). Also, as the output is partially given and inputs are precise, from now on and to facilitate exposure, we will adopt the notation (x n , Y n ) where Y n ⊆ {-1, 1} = Y and x n ∈ X . Let us first note that, in case of precise label (i.e, Y n = y n ), it is clear that the corresponding loss score is precisely given as in (3.34) and such an instance cannot be queried.

l (Y n , x n ) = l (Y n , x n ) = l (Y n , x n ) = 0 if Y n θ l (x n ) ≥ 0, 1 otherwise. ( 3.34)
We are now going to determine the imprecise loss function,

[ l (Y n , x n ), l (Y n , x n )]
and investigate under which conditions an imprecise label can have an effect on the risk bounds.

Proposition 16. Given a model θ l and an instance

(x n , Y n ), if Y n = {-1, 1}, then the following results hold A1 [ l (Y n , x n ), l (Y n , x n )] = [0, 1] A2 E qn (θ l ) = 1.
Proof. It is clear that, in the binary case, if Y n = {-1, 1}, whatever the prediction of the given model is (either 1 or -1), there always exist element y n and y n in Y n s.t

l (y n , x n ) = 0 and l (y n , x n ) = 1, or in other words, [ l (Y n , x n ), l (Y n , x n )] = [0, 1]. Furthermore, querying Y n always help to modify [ l (Y n , x n ), l (Y n , x n )]
into single value (either to 0 or 1). Or, in other words, A2 holds.

Proposition 16 simply points out that all partial labels give the same (intervalvalued) losses and have an effect on modifying the corresponding losses. In the next Proposition, we show that if the predictions of two given models for a partially labelled instance are different, then the corresponding lower pairwise difference is -1 and the effect of querying such labels is 1. Otherwise, both values are 0. Proposition 17. Given two models θ k and θ l and an imprecise instance

(x n , Y n ) (Y n = {-1, 1}) then the following properties hold B1 if θ k (x n ) = θ l (x n ) then k-l (Y n , x n ) = 0 and J qn (θ k , θ l ) = 0. B2 if θ k (x n ) = θ l (x n ) then k-l (Y n , x n ) = -1 and J qn (θ k , θ l ) = 1. Proof. B1 follows from the fact that if θ k (x n ) = θ l (x n ), then k-l (y n , x n ) = 0 for all y n ∈ Y n .
Furthermore, for any y qn n ∈ Y n to be returned after performing q n , we always have k-l (y qn n , x n ) = 0, or in other words J qn (θ k , θ l ) = 0. We are now going to give the proof for B2. Let us first notice that when

θ k (x n ) = θ l (x n ), there always exists y n ∈ Y n (i.e y n = θ l (x n )) s.t k-l (y n ) = -1. Then it is clear that k-l (Y n , x n ) = -1. Furthermore, if y qn n = θ l (x n )
is the given label after performing q n , then the pairwise difference qn k-l (y qn n , x n ) = 1. In other words, we have J qn (θ k , θ l ) = 1.

Propositions 16 and 17 provide an interesting property of V alue(q n ). In fact, for any given partial label Y n , the corresponding total effect (V alue(q n )) is exactly 1 + u i where u i is the number of models in the undominated set that give predictions against the best potential model (θ k * ). This means that while the query-by-committee approach does consider the consensus between all models for each instance, the racing algorithms are based on the consensus of each model w.r.t. to the best potential model, for all instances. Again, we can see similarities and differences between the two approaches, and comparing them makes sense.

The whole procedure is again summed up in Algorithm 2. Similarly to the case of interval-valued features, we summarize how to determine the query effect q n (line 2 -3 in Algorithm 2) and the set of undominated models (line 6 -8 in Algorithm 2) in Algorithm 5 and 6, respectively. The complexity analysis is similar to the one of interval-valued features.

Algorithm 5: Determining the query effect V alue(q n ) Input:

partial data (x n , Y n ) with Y n = {-1, 1}, set Θ = {θ 1 , . . . , θ S } of models, the best potential model θ k * Output: the query effect V alue(q n ) 1 initialize E qn (θ k * ) = 1; 2 foreach k = k * do 3 use Prop. 17 to get J qn (θ k , θ k * );
4 compute V alue(q n ) using Definition 3.10;

Experimental evaluation

We run experiments on a "contaminated" version of 7 standard benchmark (binary classes) data sets that are described in Table 3.1. The next two paragraphs present the details of the experiments and the results obtained in the two cases of interval-valued features and set-valued labels.

Algorithm 6: Determining the undominated set

Input:

data D = {(x n , Y n )} N n=1 , set Θ = {θ 1 , . . . , θ S } of models Output: the set of undominated model M * 1 foreach k, l ∈ {1, . . . , S} × {1, . . . , S}, k = l do 2 R(θ k-l | D) = 0; 3 foreach data (x n , Y n ) do 4 if (x n , Y n ) is imprecise then 5 use Prop. 17 to get k-l (Y n , x n ) ; 6 else 7 compute k-l (Y n , x n ) = k (Y n , x n ) -l (Y n , x n ) using (3.34) 8 R(θ k-l | D) = R(θ k-l | D) + k-l (Y n , x n ); 9 if R(θ k-l | D) > 0 then remove θ k from {θ 1 , . . . ,

Interval-valued features case

Given a data set, we randomly chose a training set D consisting of 10% of instances and the rest (90%) as a test set T. For each training instance x n ∈ D, and each dimension p = 1, ..., P , a biased coin is flipped in order to decide whether or not x p n will be contaminated; the probability of contamination is ( is fixed to 0.4 in all the experiments). Note that the probability that an instance has at least one contaminated feature is equal to 1 -0.6 P (the complement of having no features contaminated), which is quite high: 0.87 when P = 4, our lowest number of features in any data set. In case x p n is contaminated, a width η p n will be generated from a uniform distribution. 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 12. 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].

The set of undominated models is generated as follows: we randomly choose 100 precise replacements from the interval-valued training data. From each replacement, one linear SVM model is trained. The set of such 100 models is considered as the initial set Θ of undominated models.

After each query, the efficiency of the querying scheme is assessed based on the two following criteria:

-the proportion on the test set T = {(x t , y t )} T t=1 of identical predictions between the current best potential model θ k * and a reference model θ ref . This similarity is computed as

|{(x t , y t )|θ ref (x t ) = θ 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.

To make comparisons about the convergence of the two criteria, two baseline algorithms are also used to query interval-valued features:

-a random querying strategy where, each time, an interval feature to be queried is chosen randomly;

-the most partial querying strategy i.e, each time, the feature with the largest imprecision (i.e., the largest sampled value η p n ) is queried.

Because the training set is randomly chosen and contaminated, the results may be affected by random components. Then, for each data set, we repeat the above procedure 10 times and compute the average results.

Set-valued labels case

Experiments for the case of set-valued labels is performed in a similar way. Firstly, we randomly chose a training set D consisting of 20% of instances and the rest (of 80%) as a test set T. Then, each label y n in the training set D will be contaminated with probability ( is fixed to 0.8 in all the experiments). Since the label is binary, if a label is contaminated, it becomes completely missing.

To make comparisons, the two following baseline querying schemes are also used:

-a random querying strategy, where, each time, a set-valued label is chosen randomly,

-and a query-by-committee (QBC) strategy 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 = arg max x - M m=1 V x (y m ) S log V x (y m ) S
where V x (y m ) denotes the number of models predicting class y m for a given instance x, and S = |Θ * | denotes the number of models in the committee.

The experimental results for the case of interval-valued features and set-valued labels are given in Figures 3.4 In the case of set-valued labels, we can see that there are only slight differences between the methods. This result was expected, since, in the case of binary classification, partial labels are completely missing labels. Querying partial labels is thus equivalent to standard active learning methods like QBC. A lot of queries are needed to significantly reduce the set of undominated models and to converge through the best model. Also, the random strategy has performances that are often comparable to the active learning ones. In contrast, the performances of our approach are much better than the others in the case of interval-valued features. One can see that the size of the set of undominated models is very quickly reduced and that our racing algorithm converges faster than the other approaches to the winning model.

In order to provide some insights about the potential difficulties of adapting our method to other models, the next section discuss briefly computational issues by building upon the results obtained for SVM.

Discussion on computational issues

The reader may have noticed that the section devoted to SVM with interval-valued features was quite long, and presented more complex methods than the one about setvalued labels. Such an observation extends beyond SVM, and we try in this section to give some reasons why we may expect the problem of interval-valued features to be more complex than the problem of set-valued labels. As with the previous sections, we will stick to the case of 0-1 loss functions. We will first provide some general remarks about the implementation of our generic approach, and then will shortly discuss how results obtained for the SVM case could be extended to monotone models in general.

General discussion

A first remark is that when we have a partial data (X n , y n ) with interval-valued features, a query q p n will not make the data precise unless only one feature is partial, but will transform X n into X q p n n = × p =p X p n × x p n . In contrast, querying a partial data (x n , Y n ) with set-valued label Y n guarantees that the queried data becomes the precise data (x n , y qn n ), hence guaranteeing that the loss with respect to any model θ l will also become precise.

Let us now consider the problem of computing bounds of loss functions and potential effect of queries, with a focus on pairs of models and on the case where partial data will induce imprecision in the loss functions of both models, which constitute the most difficult aspects of our approach (our conclusions also apply to other calculations, yet these are typically easier to solve for both interval-valued features and set-valued labels).

Let us first consider the computations of k-l : in the case of set-valued label Y n , we do have

k-l (Y n , x n ) = 0 if θ k (x n ) = θ l (x n ) ∨ {θ k (x n ), θ l (x n )} ∩ Y n = ∅ -1 else (3.35)
as the first case describes the only situations where we cannot find a label y n ∈ Y n such that θ k (x n ) = y n and θ l (x n ) = y n . These conditions are rather easy to check in practice. In contrast, when one has interval-valued features, or more generally set-valued features X n with a precise label y n , we have that

k-l (y n , X n ) =      1 if ∀x n ∈ X n , θ k (x n ) = y n ∧ θ l (x n ) = y n -1 if ∃x n ∈ X n s.t. θ k (x n ) = y n ∧ θ l (x n ) = y n 0 else (3.36)
with the last case corresponding to the situation where we can only find

1 x n ∈ X n such that either θ k (x n ) = θ l (x n ) = y n , or θ k (x n ) = y n and θ l (x n ) = y n .
In contrast with Equation (3.35) whose conditions are easily checked provided θ k (x n ) and θ l (x n ) are easy to compute (this is the greatest majority of model-based learning methods), identifying which case of Equation (3.36) does apply is more complex and highly depends on the properties of the considered learning method. Similar conclusions can be drawn to compute the effect J q p n (θ k , θ l ) of a possible query. In the case of a set-valued label Y n , we can directly extend the observation made in Proposition 17 for SVM to have that

J qn (θ k , θ l ) = 1 iff k-l (Y n , x n ) = -1
where k-l (Y n , x n ) = -1 is given by the general and usually easy to estimate Equation (3.35). In contrast, we cannot extend Proposition 15 to arbitrary models when we have interval-valued features. Of course we still have that J q p n (θ k , θ l ) = 0 when k-l (y n , X n ) = 1, as it cannot be increased by any query. Yet, in the other cases, one must check that the conditions to have an increase of k-l (y n , X n ) are met at least for one value x p n ∈ X p n , and we do not see how to provide a generic, efficient algorithmic procedure to check them without considering the specificities of the considered model.

The case of monotone models

In the case of the SVM methods, Proposition 14 uses the fact that linear functions are monotonic in every dimension X p . Note that our analysis could be extended easily to all monotonic models, such as logistic regression or models based on Choquet Integral [START_REF] Tehrani | Learning monotone nonlinear models using the Choquet integral[END_REF] and more generally on non-additive and fuzzy integrals [START_REF] Grabisch | Classification by fuzzy integral: Performance and tests[END_REF].

As an illustration of this fact, let us consider the case of the logistic regression model. Keeping X = R P and the output space Y = {-1, 1} encoding the two possible classes, the logistic regression corresponding to a model θ l can be read2 as

θ l (x n ) = ln P l (1 | x n ) P l (-1 | x n ) = P p=0 w p l x p n ,
with P l (. | x n ) the posterior probabilities induced by model θ l , and vector w l its parameters with the convention x 0 n = 1. This model obviously shares with the SVM that it is monotone in each of its parameters, and in the case of the 0 -1 loss function, we also have

l (y n , x n ) = 0 if y n • θ l (x n ) ≥ 0 1 if y n • θ l (x n ) < 0. . (3.37) Indeed, if θ l (x n ) > 0, we have P l (1 | x n ) ≥ P l (-1 | x n ), hence predicting ŷn = 1.
If we consider now that the features x n are imprecisely known (as said in the previous section, the major computational difficulties will mostly happen in the case of setvalued features), and that X p n = [a p n , b p n ] (note that we still have X 0 n = [1, 1]), we can again easily determine when (X n , y n ) will be imprecise (1) w.r.t. a model θ l and (2) w.r.t. both models θ k and θ l . Clearly, for the first case, we will have

[θ l (X n ), θ l (X n )] =   w p l ≥0 w p l a p n + w p l <0 w p l b p n , w p l ≥0 w p l b p n + w p l <0 w p l a p n   ,
and (X n , y n ) will be imprecise w.r.t. θ l if and only if it contains the value 0 (arguments are similar to the one of the SVM case). Let us now consider the case of not one but two models θ k and θ l , (X n , y n ) being imprecise w.r.t. both of them (in the other situations, the same remarks as the one done for the SVM case apply). Without loss of generality, we can assume that y n = 1, and we then have that

k-l (y n , X n ) =      1 if ∀x n ∈ X n , θ k (x n ) < 0 ∧ θ (x n ) > 0 -1 if ∃x n ∈ X n , θ k (x n ) > 0 ∧ θ (x n ) < 0 0 else .
It is clear that the first case will never happen, as (X n , y n ) is imprecise w.r.t. θ k (so there is an x n for which θ k is positive). To check the second condition, we have to know whether we can find x n with θ l (x n ) < 0, under the constraint that θ k (x n ) > 0. This comes down to solve the following linear optimisation problem and to check whether it is negative, in which case the lower bound is -1, and 0 otherwise. The methodology is here slightly different than in the SVM case, but still takes advantage of the monotonicity and linearity of the model. Completely implementing our proposal in the case of logistic regression would of course require some additional work (left here to the interested reader), but seems quite doable in the light of the above remarks.

Application to decision trees

We are going to implement our generic racing approach to the particular case of 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. Similar to the case of binary SVM, we will focus on the settings when either the labels or the features are imprecise.

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 = {y 1 , . . . , y M }, where y m , m = 1, . . . , M , encode all the possible classes. A decision tree θ l 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 ∈ {1, . . . , 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.

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
-terminal nodes are called leaves. Each leaf is associated to a predicted class y 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 , y h ) (3.38)
as such information is enough for the purpose of making prediction for new instances: we have θ l (x n ) = y h for any instance x n ∈ A h .

The next small example illustrates those notations.

Example 13. Let us consider a given tree trained from data set D ∈ X P 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 θ l (x 1 ) = c while x 2 will reach leaf t 1 with an assigned class θ l (x 2 ) = a.

X 1 = [1,
We will focus on the classical 0 -1 loss function defined as follows: for a given instance (x n , y n ),

l (y n , x n ) = 0 if y n = θ l (x n ) 1 otherwise. (3.39)
In case of partially labelled data, the label is a set Y n ⊆ Y instead of a single label. Then the loss in (3.39)

becomes an interval l (Y n , x n ), l (Y n , x n ) where l (Y n , x n ) = min yn∈Yn l (y n , x n ), (3.40)
l (Y n , x n ) = max yn∈Yn l (y n , x n ). ( 3
(Y n , x n ) (resp. l (Y n , x n ))
for n = 1, . . . , 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(θ l | D), R(θ l | D)] (or in other words E qn (θ l ) = 1), let us first note that a query q n is effective if and only if [ l (Y n , x n ), l (Y n , x n )] can be modified. Then, as pointed out in the next proposition, such effect (i.e E qn (θ l ) = 1) will simply hold for all imprecise instances. Proposition 19. Given a model θ l and an instance

(x n , Y n ), then E qn (θ l ) = 1 if and only if (x n , Y n ) is imprecise w.r.t. θ l .
Proof. Firstly, it is easy to see that querying any instance that is precise w.r.t. θ l will not help to modify [ l (Y n , x n ), (Y n , θ l (x n )]. Furthermore, (3.46) implies that q n have an effect by either increasing l (Y n , x n ) or decreasing l (Y n , 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 y qn n is the label we get after query q n , then either y qn n = θ l (x n ) or y qn n = θ l (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 (θ l ) = 1 if (x n , Y n ) is imprecise w.r.t. θ l .
Computation of pairwise risk bounds and the effect J qn (θ k , θ 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 θ k and θ l , the corresponding pairwise risk R(θ k-l | D) 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(θ k-l | D) 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 k (y n , x n ) -l (y n , x n ) .
Furthermore, a query q n can increase R(θ k-l | D) if and only if it can increase the value k-l (Y n , x n ). This is why, in this section, we will focus on computing k-l (Y n , x n ) and its possible change after a query q n .

Case 1: Imprecision with respect to one model

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

Proposition 20. Given (x n , Y n ) and two models θ k and θ l s.t. x n is imprecise w.r.t. one and only one model, then we have

k-l (Y n , x n ) = k (Y n , x n ) -1 if x n imprecise w.r.t. θ l , (3.47) k-l (Y n , x n ) = 0 -l (Y n , x n ) if x n imprecise w.r.t. θ k . (3.48)
Proof. Since instance 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: l (y n , x n ) = 1 for Equation (3.47) and k (y n , x n ) = 0 for Equation (3.48).

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

Proposition 21. Given (x n , Y n ) and two models θ k and θ 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 (θ k , θ l ) = 1.

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

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

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

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

-if θ k (x n ) = θ l (x n ), then k-l (Y n , x n ) = 0 and J qn (θ k , θ l ) = 0. -if θ k (x n ) = θ l (x n ), then k-l (Y n , x n ) = -1 and J qn (θ k , θ l ) = 1.
Proof.

-When

θ k (x n ) = θ l (x n ), then (y n , θ k (x n )) = (y n , θ l (x n ))
for any value of y 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 ∈ Y n to be given after performing query q n , the lower difference (i.e, k-l (Y n , x n )) will be 0. Or in other words, if θ k (x n ) = θ l (x n ), then we can simply conclude that k-l (Y n , x n ) = 0 and J qn (θ k , θ l ) = 0.

-In case θ k (x n ) = θ l (x n ), as pointed out in Proposition 18, x n being imprecise w.r.t. both models implies that

θ k (x n ) ∈ Y n and θ l (x n ) ∈ Y n . (3.49)
Then there always exists a label y n in Y n (i.e y n = θ k (x n )) s.t. model θ k returns a true prediction while θ l returns a wrong one. In other words, we have

k-l (Y n , x n ) = -1.
The effect J qn (θ k , θ l ) = 1 follows simply by assuming that label y = θ 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 7 summarizes the complete procedure to perform an iteration of our querying strategy. Sub-routines are described in other algorithms. Algorithm 8 computes the individual risk bounds of every model, according to the corresponding values of l (Y n , x n ), l (Y n , x n ). Algorithm 9 simply summarises the model selection procedure, that will also be used in the case of interval-valued features.

Finally, Algorithm 10 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 7 is in O(S × N ), as Algorithm 8 is called S times and is in O(N ). Line 3 of Algorithm 7 is in O(S). Finally, since Algorithm 10 is in O(S), lines 4-5 of Algorithm 10 are in O(S × N ). So the overall complexity of Algorithm 10 is in O(S × N ), meaning that the approach is computationally affordable. 3 Determine the best model m k * and the undominated model set Θ using Alg. 9; 4 foreach n = 1, . . . , N do 5 Determine the query effect value V alue(q n ) using Alg. 10;

6 Determine q n * = arg max n V alue(q n );

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 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 θ l , each terminal node (which is sufficient in later analysis) is associated with a partition element

A h = A 1 h × . . . , ×A P h , (3.50)
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 (3.50)) denoted by

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

U = U 1 × . . . × U P and V = V 1 × . . . × V P , their corresponding intersection, denoted by U ∩ V is U ∩ V = × P p=1 U p ∩ V p . (3.52)
(3.52) 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 = 1 . . . , P. (3.53)
As for the case of partial labels, an instance (X n , y n ) is said to be imprecise w.r.t. a decision tree θ l if

∃x n , x n ∈ X n s.t l (y, x n ) = l (y, x n ).
(3.54)

Furthermore, as an instance can intersect several partition elements which are possibly associated to different labels, then (3.54) is equivalent to the following relation Example 15. Figure 3.9 gives an example of a tree θ l and two instances, (X 1 , 0), (X 2 , 1).

∃A h , A h s.t X n ∩ A h = ∅, X n ∩ A h = ∅
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 (3.55) 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(θ l ), R(θ l )] can be computed efficiently from data {(X 1 , y 1 )} N n=1 by computing extreme bounds l (y n , X n ), l (y n , 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 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, (3.60)
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 = ∅. (3.61)
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, (3.62)
which can be done by checking the condition

X p n \ ∪ k h c h yn =1 A p h = ∅. (3.63)
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 (3.61) and (3.63)). Once we notice this, we can rewrite the computational problem in the following form there is a gap in the union of intervals. Let {d (1) , . . . , d (I) } be the ordered list of lower bounds, or starts of intervals. A gap happens if, when increasing values from a p n to b p n , all intervals that have been opened are closed before another one starts (as illustrated in Figure 3.10). In formal terms, there exists an index j such that

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 = ∅. ( 3
{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

d (1) ≤ a p n ≤ b p n ≤ d (I) .
For a given interval a p n , b p n and a set of interval d i , d i |i = 1, . . . , 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 (3.64) is satisfied) can be checked using Algorithm 11.

Let us now illustrate how to practically determine the single effect using a simple example.

Example 16. Consider the tree θ l and two instances X 1 , X 2 illustrated in Figure d (1) d

(1)

d (j) d (j)
d (j+1) max{d (1) , . . . , d (j) } gap

Input: a p n , b p n , sets d i , d i |i = 1, . . . , I s.t, for ∀i, a p n , b p n ∩ d i , d i = ∅ Output: Return In = 1 if (3.64
) is satisfied and 0 otherwise 1 Order {d 1 , . . . , d I } into {d (1) , . . . , d (I) } ;

2 foreach i = 1, . . . , I do 3 if |{d k : d k < d (i) }| = i -1, then 4
Return 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; 3.9. Instance X 1 is precise w.r.t. the model θ l , hence querying its feature is useless for this model. We then focus on determining the effect of querying the features of X 2 . Using (3.56)-(3.58), the information vectors associated to X 2 are K = (1, 1, 1, 1, 1, 1) and B y 2 = (1, 0, 0, 0, 1, 0) and C y 2 = (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 3.11, we have that K q p n B y 2 = 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 3.11), we have that K q p n B y 2 = 0. Finally, we conclude that instance X 2 can become a precise instance after querying either X 1 2 or X 2 2 .

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

Pairwise risk bounds and effect

This section focuses on how to compute, for a pair of models θ k and θ 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 3.4.1), 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.

Case 1: Imprecision with respect to one model

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

k-l (y n , X n ) = inf xn∈Xn k (y n , x n ) -l (y n , x n ) .
Proposition 23. Given (X n , y n ), and two models θ k and θ l s.t X n is imprecise w.r.t. one and only one model, we have

k-l (y n , X n ) = k (y n , X n ) -1 if X n imprecise w.r.t. θ l (3.65) k-l (y n , X n ) = -l (y n , X n ) if X n imprecise w.r.t. θ k . (3.66)
Proof. Similar to proof of Proposition 20.

Then a query q p n will have an effect

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

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

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

Proof. Let us start with the case when X n is imprecise w.r.t. model θ k . The condition that Equation (3.63) holds for the model θ k simply implies that after performing a query q p n , the loss k (y n , 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 θ l , that Equation (3.61) holds implies that after performing a query q p n , the loss l (y n , X n ) is precisely 0 which results in increasing k-l (y n , X n ).

Case 2: Imprecision with respect to both models Note that when an instance X n is imprecise with respect to both models θ k and θ l , the pairwise risk bounds k-l (y n , X n ) can get values in {-1, 0, 1}. Let us denote by y θ l h the label associated to the partition A θ l h of a tree θ l , then the relation between X n and leaves of θ k and θ 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 (3.67) s.t w k,l i,j =            2 if X n ∩ A θ k i ∩ A θ l j = ∅, 1 if X n ∩ A θ k i ∩ A θ l j = ∅, y θ k i = y n , y θ l j = y n , 0 if X n ∩ A θ k i ∩ A θ l j = ∅, y θ k i = y θ l j , -1 if X n ∩ A θ k i ∩ A θ l j = ∅, y θ k i = y n , y θ l j = y n . (3.68)
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 θ k i ∩ A θ 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 . (3.69)
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 θ k i ∩ A θ l j = ∅ can be easily determined as a consequence of Equation (3.52), as we have

X n ∩ A θ k i ∩ A θ l j = × P p=1 X p n ∩ A θ k i,p ∩ A θ l j,p . (3.70)
Then for an instance X n , its corresponding pairwise risk bound w.r.t. two models θ k and θ l can be determined explicitly using Equations (3.67) and (3.68). 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 (3.71)
be the set of such elements, then J q p n (θ k , θ 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 θ k i , A θ l j , using (3.53), we have that their intersection is

A i,j = A θ k i ∩ A θ l j = × P p=1 A θ k i,p ∩ A θ l j,p := × P p=1 A p i,j , (3.72)
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 25. Given a training instance X n which is imprecise w.r.t. both models θ k and θ 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)
Figure 3.12: Example of determining the pairwise effect

J q p n (θ k , θ l ) = 1 if and only if X p n \ ∪ i,j|w k,l i,j ∈S min A p i,j = ∅. (3.73)
Proof. Let us first note that if (3.73) 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 (3.73) is true can easily be reformulated in the form of Equation (3.64), Algorithm 11 can then be used to perform the check. In practice, such a check is quadratic in the number of leaves of the models θ k , θ 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 17. Assume that we have two models θ 1 and θ 2 with 3 leaves each, whose intersection of partition elements is illustrated in Figure 3.12.

Instance X covers the red region and has label y = 1. From Figure 3.12, 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

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 .

if In = 1 then J q p n = J q p n + 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 Θ. In practice, we may expect partial features to be quite less numerous, as well as their intersections with tree leaves.

Name

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 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).

Experimental evaluation

In this section, we run experiments on a "contaminated" version of 4 standard benchmark data sets as described in Table 3.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. The next two subsections present details about the experimental settings and the results for interval-valued features and set-valued labels data, respectively.

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. Similarly to the SVM experimental parts, in case x p n is contaminated, a width η p n is generated from a uniform distribution on the unit interval and 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 ). Similar to the case of binary SVM, we generate an initial set of undominated models from 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. 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(θ k | D) 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.

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 θ k * with a reference model θ ref is computed on the precise test set T.

-the size of the undominated set Θ * , that should decrease as fast as possible, both to ensure computational efficiency and model performances.

-the accuracy on the test set. The above criteria aim to assess the effect of querying strategies in the learning step. To evaluate the relevance of the queries on unseen data, we consider the queried data set after querying 5% of the partial values, and this up to 30% (so, we test our queried data set for 5%, 10%, 15%, . . . queries). Since some partial data remain, we first impute those ones (replacing X p n by their middle values), learn a model θ * on the obtained fully precise training set, and evaluate its accuracy on the test set.

The 5-folds process is repeated 2 times and the average size of the sets of models, the average similarity of the best potential model and the average acuracy on the test set are reported.

The experimental results are presented in Figure 3.13 to 3.15. 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. Regarding the interest of the queries on the final learnt model, we can see that the racing approach provides better improvements in most cases, in particular when the accuracy difference before and after querying is significant.

Set-valued labels

We perform on the same data sets as before (cf. Table 3.2) and the 2 × 5 crossvalidation 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 + (M -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. Similar to the case of binary SVM, we compare our racing approach with two baseline querying schemes: a random query and a query by committee approach (QBC). Finally, the size of the sets of models and the similarity of the best potential model θ k * w.r.t. the reference model θ ref are reported and used to make comparison. Since in the case of partial labels there is almost no difference between the approaches, we did not evaluate their performances on test sets.

The experimental results, presented in Figure 3.16, 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.

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 precisely known. To solve the problem, we have proposed in this Chapter a generic querying approach based on the idea of racing algorithms. Our generic approach has been then detailed for the specific cases of binary SVM and 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 performs poorly.

Epistemic uncertainty for active learning and cautious inferences

As mentioned in the introduction, we think that differentiating sources of uncertainty should benefit to machine learning applications. For instances, it could be useful for developing querying criteria when doing active learning or balancing the informativeness and cautiousness when making cautious inferences. This research direction has been well-studied in the literature on uncertainty and machine learning. We will restrict ourselves, in this chapter, to a distinction between two sources of uncertainty: epistemic, caused by a lack of training data and, and aleatoric, due to intrinsic randomness. After summarizing the basic concepts and presenting the practical procedures to estimate these degrees of uncertainty, we will explain how these estimates can be used to solve two machine learning problems: active learning and cautious inferences.

Likelihood to estimate epistemic and aleatoric uncertainties

We are going to provide a quick literature review on this line of research and then recall the basics of a contour-likelihood based approach which will be adopted in the later proposals. To facilitate subsequent applications, we will propose practical procedures to estimate the degrees of uncertainty for popular classifiers.

A formal framework for uncertainty modeling

Epistemic uncertainty in learning theory

As already said, the problem of differentiating sources of uncertainty has been increasingly investigated [START_REF] Hora | Aleatory and Epistemic Uncertainty in Probability Elicitation with an Example from Hazardous Waste Management[END_REF][START_REF] Kendall | What Uncertainties do We Need in Bayesian Deep Learning for Computer Vision[END_REF][START_REF] Kull | Reliability maps: a tool to enhance probability estimates and improve classification accuracy[END_REF][START_REF] Senge | Reliable Classification: Learning Classifiers that Distinguish Aleatoric and Epistemic Uncertainty[END_REF][START_REF] Sharma | Evidence-based Uncertainty Sampling for Active Learning[END_REF]. In this line of research, several approaches exist and have been successfully implemented for different applications, including classification [START_REF] Kull | Reliability maps: a tool to enhance probability estimates and improve classification accuracy[END_REF][START_REF] Senge | Reliable Classification: Learning Classifiers that Distinguish Aleatoric and Epistemic Uncertainty[END_REF] and active learning [START_REF] Sharma | Evidence-based Uncertainty Sampling for Active Learning[END_REF]. We are going to quickly mention approaches related to our interests as well as their subsequent applications.

-Sharma and Bilgic [START_REF] Sharma | Evidence-based Uncertainty Sampling for Active Learning[END_REF] recently proposed an evidence-based approach to active learning, in which conflicting-evidence uncertainty is distinguished from insufficient-evidence uncertainty. Roughly speaking, a high conflicting evidence captures the case where the evidences are close and both of large magnitude. In other words, it refers to the situation where a model is highly uncertain about an instance, and has strong but conflicting evidence for both classes. On the other hand, a high insufficient-evidence uncertainty refers to the case where a model is highly uncertain about an instance because of not having enough evidence for either class. Experimentally, they support their conjecture that the conflicting-evidence uncertainty is more informative for an active learner than the conflicting-evidence one.

-Conformal prediction [4,[START_REF] Shafer | A Tutorial on Conformal Prediction[END_REF] is a generic approach to reliable (set-valued) prediction that combines ideas from probability theory (specifically the principle of exchangeability), statistics (hypothesis testing, order statistics), and algorithmic complexity. The basic version of conformal prediction is designed for sequential prediction in an online setting, and comes with certain correctness guarantees (predictions are correct with probability 1-ξ, where ξ is a confidence parameter). Roughly speaking, given an instance t, it assigns a non-conformity score to each candidate output. Then, considering each of these outcomes as a hypothesis, those outcomes for which the hypothesis can be rejected with high confidence are eliminated. The set-valued prediction is given by the set of those outcomes that cannot be rejected.

-Cautious (set-valued) prediction methods based on imprecise probabilities, such as [START_REF] Corani | Introduction to Imprecise Probabilities[END_REF], augment the probabilistic predictions into probability intervals or sets of probabilities, the size of which reflects the lack of information (reflecting epistemic uncertainty). Similar to this are approaches based on confidence bands in calibration models, for instance [START_REF] Kull | Reliability maps: a tool to enhance probability estimates and improve classification accuracy[END_REF][START_REF] Xu | Evidential calibration of binary SVM classifiers[END_REF], which usually control the amount of imprecision by adjusting some certain parameters, e.g., a confidence value.

-Credal uncertainty sampling [3] is another approach that seeks to differentiate between parts of the uncertainty. This approach assumes that a credal set C ⊆ Θ is given and learns for each label y ∈ Y, an interval-valued probability

[p C (y | t), p C (y | t)].
In this case, p C (y | t) and p C (y | t) are the minimum and maximum conditional probabilities that can be given for y by candidates of C, respectively. The widths of the interval-valued probabilities reflect the reducible part of uncertainty while its extreme probabilities reflect the irreducible one. More precisely, we can shrink the interval [p C (y | t), p C (y | t)] (or, reduce the epistemic part) by acquiring additional training data, eventually getting a precise value. We will only illustrate how the extreme probabilities reflect the irreducible part (of uncertainty) in the case of binary classification, i.e, Y := {0, 1} (the case of multi-class classification could be rather complicated and will not be investigated here). In this case, we could image that if the interval probabilities [p C (y | t), p C (y | t)] is symmetrical around 0.5, shrinking such intervals is not very helpful in distinguishing the classes (i.e, a high irreducible uncertainty), especially when its extreme probabilities are close to 0.5. However, if

[p C (y | t), p C (y | t)
] is highly asymmetrical around 0.5, shrinking it should benefit in distinguishing the classes (i.e, a low irreducible uncertainty).

-The distinction between the epistemic and aleatoric uncertainty involved in the prediction for an instance t is well-accepted in the literature on uncertainty [START_REF] Hora | Aleatory and Epistemic Uncertainty in Probability Elicitation with an Example from Hazardous Waste Management[END_REF][START_REF] Senge | Reliable Classification: Learning Classifiers that Distinguish Aleatoric and Epistemic Uncertainty[END_REF] and has been considered in only few recently machine learning works, e.g, [START_REF] Kendall | What Uncertainties do We Need in Bayesian Deep Learning for Computer Vision[END_REF]. Roughly speaking, the aleatoric uncertainty refers to the notion of randomness, that is, the variability in the outcome of an experiment which is due to inherently random effects. As opposed to this, the epistemic uncertainty refers to the uncertainty caused by a lack of knowledge. Thus, the distinction considered here appears to be quite related to the one between conflicting-evidence and insufficient-evidence uncertainty [START_REF] Sharma | Evidence-based Uncertainty Sampling for Active Learning[END_REF], and the one considered in credal uncertainty sampling [3]. Detailed comparisons will be given in our proposal for active learning.

Yet, the concepts of the degrees of epistemic and aleatoric uncertainty are, in principle, defined in the literature. Practically quantifying these degrees for different classifiers still remains a challenge. We are going to summarize the contour-likelihood based approach [START_REF] Senge | Reliable Classification: Learning Classifiers that Distinguish Aleatoric and Epistemic Uncertainty[END_REF] and then detail it for the local model, logistic regression and Naive Bayes classifiers.

Contour-likelihood based approach

In the rest of this chapter, we adopt the contour-likelihood based approach proposed by Senge et al. [START_REF] Senge | Reliable Classification: Learning Classifiers that Distinguish Aleatoric and Epistemic Uncertainty[END_REF], which is based on the use of relative likelihoods, historically proposed by Birnbaum [6] and then justified in other settings such as possibility theory [START_REF] Walley | Upper Probabilities based only on the Likelihood Function[END_REF]. In the following, the essence of this approach is briefly recalled.

We proceed from an instance space X = R P , an output space Y = {0, 1} encoding the two classes, and a hypothesis space Θ consisting of probabilistic classifiers θ : X -→ [0, 1]. We denote by p θ (1 | x) = θ(x) and p θ (0 | x) = 1 -θ(x) the (predicted) probability that instance x ∈ X belongs to the positive and negative class, respectively. Given a set of training data D = {(x n , y n )} N n=1 , the contour likelihood of a model θ is defined as

π Θ (θ | D) = L(θ | D) L(θ * | D) = L(θ | D) max θ ∈Θ L(θ | D) , (4.1)
where

L(θ | D) = N n=1 p θ (y n | x n )
is the likelihood of θ, and θ * ∈ Θ the maximum likelihood estimation on the training data D. For a given instance t, the degrees of support (plausibility) of the two classes are defined as follows:

π(1 | t) = sup θ∈Θ min π Θ (θ | D), p θ (1 | t) -p θ (0 | t) , (4.2)
π(0 | t) = sup θ∈Θ min π Θ (θ | D), p θ (0 | t) -p θ (1 | t) . (4.3)
So, π(1 | t) is high if and only if a highly plausible model supports the positive class much stronger (in terms of the assigned probability mass) than the negative class (and π(0 | t) can be interpreted analogously) 1 . Note that, with f (a) = 2a -1, we can also rewrite (4.2)-(4.3) as follows:

π(1 | t) = sup θ∈Θ min π Θ (θ | D), f (θ(t)) , (4.4)
π(0 | t) = sup θ∈Θ min π Θ (θ | D), f (1 -θ(t)) . (4.5)
Given the above degrees of support, the degrees of epistemic uncertainty u e and aleatoric uncertainty u a are defined as follows [START_REF] Senge | Reliable Classification: Learning Classifiers that Distinguish Aleatoric and Epistemic Uncertainty[END_REF]:

u e (t) = min π(1 | t), π(0 | t) , (4.6)
u a (t) = 1 -max π(1 | t), π(0 | t) . (4.7)
Thus, the epistemic uncertainty refers to the case where both the positive and the negative class appear to be plausible, while the degree of aleatoric uncertainty (4.7) is the degree to which none of the classes is supported. These uncertainty degrees are completed with degrees s 1 (t) and s 0 (t) of (strict) preference in favor of the positive and negative class, respectively:

s 1 (t) =        1 -(u a (t) + u e (t)) if π(1 | t) > π(0 | t), 1-(ua(t)+ue(t)) 2 if π(1 | t) = π(0 | t), 0 if π(1 | t) < π(0 | t).
With an analogous definition for s 0 (t), we have s 0 (t) + s 1 (t) + u a (t) + u e (t) ≡ 1 ,

i.e., the quadruple (s 1 (t), s 0 (t), u e (t), u a (t)) defines a partition of unity. Besides, it has the following properties:

s 1 (t) (s 0 (t)) will be high if and only if, for all plausible models, the probability of the positive (negative) class is significantly higher than the one of the negative (positive) class;

u e (t) will be high if the class probabilities strongly vary within the set of plausible models, i.e., if we are unsure how to compare these probabilities. In particular, it will be 1 if and only if we have θ(t) = 1 and θ (t) = 0 for two totally plausible models θ and θ ;

u a (t) will be high if the class probabilities are similar for all plausible models, i.e., if there is strong evidence that θ(t) ≈ 0.5. In particular, it will be close to 1 if all plausible models allocate their probability mass around θ(t) = 0.5.

Roughly speaking, the aleatoric uncertainty is due to influences on the data-generating process that are inherently random, whereas the epistemic uncertainty is caused by a lack of knowledge. Or, stated differently, u e and u a measure the reducible and the irreducible part of the total uncertainty, respectively. As said in [START_REF] Senge | Reliable Classification: Learning Classifiers that Distinguish Aleatoric and Epistemic Uncertainty[END_REF], determining the degrees of support (4.4)-(4.5) comes down to solving optimization problems, the complexities of which strongly depend on the model space Θ, and may become rather complex. We are going to summarize the details for the case of Parzen window classifiers, whose details is given in [START_REF] Senge | Reliable Classification: Learning Classifiers that Distinguish Aleatoric and Epistemic Uncertainty[END_REF] and presents our proposals for the cases of logistic regression and Naive Bayes.

Estimation for local models

By local learning, we refer to a class of non-parametric models that derive predictions from the training information in a local region of the instance space, for example the local neighborhood of a query instance [START_REF] Bottou | Local Learning Algorithms[END_REF][START_REF] Cover | Nearest Neighbor Pattern Classification[END_REF]. As a simple example, we consider the Parzen window classifier [START_REF] Chapelle | Active Learning for Parzen Window Classifier in Proceedings of the Tenth International Workshop on Artificial Intelligence and Statistics[END_REF], to which our approach can be applied in a quite straightforward way. To this end, for a given instance t, we define the set of its neighbours as follows:

R(t, δ) = (x n , y n ) ∈ D | x n -t ≤ δ , (4.8)
where δ is the width of the Parzen window (a practical method to determine such a width will be given latter).

In binary classification, a local region R can be associated with a constant hypothesis θ ∈ Θ = [0, 1], where θ(t) is the probability of the positive class in the region; thus, θ predicts the same probabilities θ(1 | t) = θ and θ(0 | t) = 1 -θ for all t ∈ R. The underlying hypothesis space is given by Θ = {θ | 0 ≤ θ ≤ 1}. With α and β the number of positive and negative instances, respectively, within a Parzen window R(t, δ), the likelihood is then given by

L t (θ | D) = α + β β θ α (1 -θ) β , (4.9)
and the maximum likelihood estimate is

θ * = α α + β . (4.10)
Therefore, the degrees of support for the positive and negative classes are

π(1|t) = sup θ∈[0,1] min   θ α (1 -θ) β α α+β α β α+β β , 2θ -1   , (4.11)
π(0|t) = sup θ∈[0,1] min   θ α (1 -θ) β α α+β α β α+β β , 1 -2θ   .
(4.12) Solving (4.11) and (4.12) comes down to maximizing a scalar function over a bounded domain, for which standard solvers can be used. We applied Brent's method2 (which is a variant of the golden section method) to find a local minimum in the interval θ ∈ [0, 1]. From (4.11-4.12), the epistemic and aleatoric uncertainties associated with the region R can be derived according to (4.55) and (4.56), respectively. For different combinations of α and β, these uncertainty degrees can be pre-computed (cf. Figure 4.2). How to determine the width δ of the Parzen window? This value is difficult to assess, and an appropriate choice strongly depends properties of the data and the dimensionality of the instance space. Intuitively, it is even difficult to say in which range this value should lie. Therefore, instead of fixing δ, we fixed an absolute number K of neighbors in the training data, which is intuitively more meaningful and easier to interpret. A corresponding value of δ is then determined in such a way that the average number of nearest neighbours of instances x n in the training data D is just K (see Algorithm 16). In other words, δ is determined indirectly via K.

Since K is an average, individual instances may have more or less neighbors in their Parzen windows. In particular, a Parzen window may also be empty. In this case, we set u e (t) = 1 by definition, i.e., we consider this as a case of full epistemic uncertainty. Likewise, the uncertainty is considered to be maximal for all other sampling techniques. If the accuracy of the Parzen classifier needs to be determined, we assume that it yields an incorrect prediction. This means that learning the model comes down to estimating a parameter vector θ = (θ 0 , . . . , θ P ), which is commonly done through likelihood maximization [START_REF] Menard | Applied Logistic Regression Analysis[END_REF]. To avoid numerical issues (e.g, having to deal with the exponential function for large θ) when maximizing the target function, we employ L 2 -regularization. The corresponding version of the log-likelihood function (4.14) is strictly concave [START_REF] Rennie | Regularized Logistic Regression is Strictly Convex[END_REF]:

l(θ | D) = log L(θ | D) = N n=1 y n   θ 0 + P p=1 θ p x p n   (4.14) - N n=1 ln   1 + exp   θ 0 + P p=1 θ p x p n     - γ 2 P p=0 (θ p ) 2 ,
where the regularization parameter γ will be fixed to 1.

We now focus on determining the degree of support (4.4) for the positive class, and then summarize the results for the negative class (which can be determined in a similar manner). Associating each hypothesis θ ∈ Θ with a vector θ ∈ R P +1 , the degree of support (4.4) can be rewritten as follows:

π(1 | t) = sup θ∈R d+1 min π Θ (θ | D), 2θ(t) -1 (4.15)
It is easy to see that the target function to be maximized in (4.15) is not necessarily concave. Therefore, we propose the following approach.

Let us first note that whenever θ(t) < 0.5, we have

2θ(t) -1 ≤ 0 and min π Θ (θ | D), 2θ(t) -1 ≤ 0.
Thus the optimal value of the target function (4.15) can only be achieved for some hypotheses θ such that θ(t) ∈ [0.5, 1].

For a given value α ∈ [0.5, 1), the set of hypotheses θ such that θ(t) = α corresponds to the convex set

θ α = θ θ 0 + P p=1 θ p x p = ln α 1 -α . ( 4.16)
The optimal value π * α (1 | t) that can be achieved within the region (4.16) can be determined as follows:

π * α (1 | t) = sup θ∈θ α min π Θ (θ | D), 2α -1 = min sup θ∈θ α π Θ (θ | D), 2α -1 . (4.17)
Thus, to find this value, we maximize the concave log-likelihood over a convex set:

θ * α = arg sup θ∈θ α l(θ | D) (4.18)
As the log-likelihood function (4.14) is concave and has second-order derivatives, we tackle the problem with a Newton-CG algorithm [START_REF] Nocedal | Numerical Optimization[END_REF]. Furthermore, the optimization problem (4.18) can be solved using sequential least squares programming3 [START_REF] Philip | Sequential Quadratic Programming Methods[END_REF]. Since regions defined in (4.16) are parallel hyperplanes, the solution of the optimization problem (4.15) can then be obtained by solving the following problem: Following a similar procedure, we can estimate the degree of support for the negative class (4.5) as follows:

sup α∈(0,0.5] π * α (0|x) = sup α∈(0,0.5] min π Θ (θ * α | D), 1 -2α (4.20)
Note that limit cases α = 1 and α = 0 cannot be solved, since the region (4.16) is then not well-defined (as ln(∞) and ln(0) do not exist). For the purpose of practical implementation, we handle (4.19) by discretizing the interval over α. That is, we optimize the target function for a given number of values α ∈ [0.5, 1) and consider the solution corresponding to the α with the highest optimal value of the target function π * α (1 | t) as the maximum estimator. Similarly, (4.20) can be handled over the domain (0, 0.5].

In practice, we evaluate (4. [START_REF] Couso | A general framework for maximizing likelihood under incomplete data[END_REF]) and (4.20) on uniform discretizations of cardinality 50 of [0.5, 1) and (0, 0.5], respectively. We can further increase efficiency by avoiding computations for values of α for which we know that 2α -1 and 1 -2α are lower than the current highest support value given to class 1 and 0, respectively. See Algorithm 17 for a pseudo-code description of the whole procedure.

The log-likelihood function is defined for binary Naive Bayes classifier as follows [START_REF] Collins | The Naive Bayes model, Maximum-likelihood Estimation, and the EM Algorithm[END_REF]

l(θ | D) : = N n=1 ln p θ (y n ) P p=1 p θ (X p = x p n |Y = y n ) =
s 0 + γ 2 , (4.29)
where γ ∈ [0, 1] is the regularization parameter and will be fixed to be 0.001. Let us note that we employ the regularization form of the log-likelihood estimate here to avoid unexpected effect caused by the zero count, which is common when works with Naive Bayes, especially when dealing with small data sets with a large number of features. We now focus on determining the degree of support for the positive class (4.4) and then summarize the results for the negative class (4.5) (which can be determined in a similar manner). Given an unlabelled instance t = (t 1 , . . . , t P ), denoting by θ p,1 t := p θ (X p = t p |Y = 1) = θ p,t p 1 , p = 1, . . . , P, (4.30) θ p,0 t := p θ (X p = t p |Y = 0) = θ p,t p 0 , p = 1, . . . , P. (4.31)

Then, the degree of support (4.4) can be rewritten explicitly as follows

π(1|t) = sup θ∈Θ min π Θ (θ | D), max 2θ(t) -1, 0 (4.32)
where, θ(t) = θ 1

P p=1 θ p,1 t θ 1 P p=1 θ p,1 t + θ 0 P p=1 θ p,0 t (4.33)
Let us notice that the target function to be maximized in (4.32) is not necessarily concave, which can lead to difficulties when maximizing the function. We propose the following approach inspired by ε-contamination model. Given θ * , the maximum likelihood estimate computed using (4.28), for a given number ε ∈ [0, 1], we define a contour region Θ ε as follows

Θ ε = {θ|θ ∈ Θ ∩ [(1 -ε)θ * , (1 -ε)θ * + ε]}. (4.34)
The intuitive idea we interest here is to enlarge Θ ε from a singleton {θ * } to the entire hypothesis space Θ by increasing ε from 0 to 1. Following this direction, we can, as pointed out in the following, simultaneously increase θ(t) and decrease π Θ (θ | D) (in general). Thus, starting from the highest value of π Θ (θ | D), we will converge to the value of π Θ (θ | D) where θ(t) and π Θ (θ | D) are identical (or closed in practice), which is the optimal estimate for the solution of (4.32). For a contour region Θ ε , the highest value of θ(t) attained at

θ t ε = arg max θ∈Θε θ(t) (4.35) = (1 -ε)(θ 1 ) * + , (1 -ε)(θ 0 ) * , (1 -ε)(θ p,1 t ) r + ε, (1 -ε)(θ p,0 t ) r , p = 1, . . . , P .
The formula given in (4.35) comes from the combination of the monotonicity of θ(t) and the property that guarantees the feasibility of θ t ε s.t,

(1 -ε)(θ 1 ) * + ε + (1 -)(θ 0 ) * = (1 -ε) (θ 1 ) * + (θ 0 ) * + ε = 1, ∀ε ∈ [0, 1].
When assessing the probability θ(t), the regularization (θ p,1 t ) r , (θ p,0 t ) r is employed (instead of (θ p,1 t ) * , (θ p,0 t ) * ) to overcome the effect of zero count. Furthermore, the monotonicity of θ(t) ensures that we can increase θ(t) (and consequently 2θ(t) -1) by increase ε. In other words, for ε ≤ ε , we have that θ t ε (t) ≤ θ t ε (t). It is worth noticing that θ t ε only contains 2 + 2 * d variables which is relatively smaller than f , the total number of variables within θ. Thus, the highest value θ(t) over Θ ε is associated to a region θ t ε ∩ Θ ε . That is to fix all the variables given in (4.35) while letting others freely as long as the condition of belonging to Θ ε still satisfied.

The highest value that π Θ (θ | D) can attain within Θ ε when fixing θ(t) to be θ t ε (t) can be determined as follows:

π Θ (θ t ε ) = arg max θ∈Θε∩θ t ε π Θ (θ | D). (4.36)
Thus, the highest degree of support π(1|t) can be given to t over the hypothesis region Θ ε can be approximated as

π ε (1|t) = min 2θ t ε (t) -1, π Θ (θ t ε | D) (4.37)
To this end, we obtain an estimate of π(1|t) as follows

π(1|t) = arg max ε∈[0,1] π ε (1|t). (4.38)
Let us notice that at the beginning, we always have that π Θ (θ t 0 | D) ≥ 2θ t 0 (t) -1. This observation is quite interesting for making an early stopping criteria (as the optimization problem (4.36) could be expensive due to large number of variables) that is to continually increase ε (from 0 to 1) as long as π Θ (θ t ε | D) ≥ 2θ t ε (t) -1 and stop as soon as the side is reversed, i.e, when seeing ε s.

t π Θ (θ t ε | D) ≤ 2θ t ε (t) -1.
The intuitive idea of this criteria is that when seeing a reverse, we are quite sure that we just already jumped over the crossing point, i,e, the optimal solution θ t s.t

π(1|t) = π Θ (θ t | D) = 2θ t (t) -1,
Thus, simply approximating π(1|t) = π ε (1|t) could give a close estimate. Readers interested in more accurate approximations are recommended to do a further search within the region [ε, ε ].

Following a similar manner, we find an estimate of π(0|t) s.t

π(0|t) = arg max ∈[0,1] π ε (0|t). (4.39)
Assuming a probabilistic model producing predictions in the form of probability distributions p θ (• | t) on Y, the utility score is typically defined in terms of a measure of uncertainty. Thus, instances on which the current model is highly uncertain are supposed to be maximally informative [START_REF] Settles | Active Learning Literature Survey[END_REF][START_REF] Settles | An Analysis of Active Learning Strategies for Sequence Labeling Tasks[END_REF][START_REF] Sharma | Evidence-based Uncertainty Sampling for Active Learning[END_REF]. Popular examples of such measures include -the entropy:

s(θ, t) = - y∈Y p θ (y | t) log p θ (y | t) , (4.40)
-the least confidence:

s(θ, t) = 1 -max y∈Y p θ (y | t) , (4.41)
-the smallest margin:

s(θ, t) = p θ (y m | t) -p θ (y n | t) , (4.42)
where y m = arg max y∈Y p θ (y | t) and y n = arg max y∈Y\ym p θ (y | t).

While the first two measures ought to be maximized, the last one has to be minimized.

In the case of binary classification, i.e, Y = {0, 1}, all these measures rank unlabelled instances in the same order and look for instances with small difference between p θ (0 | t) and p θ (1 | t).

Evidence-based uncertainty sampling

In their evidence-based uncertainty sampling approach [START_REF] Sharma | Evidence-based Uncertainty Sampling for Active Learning[END_REF], the authors propose to differentiate between conflicting-evidence uncertainty and insufficient-evidence uncertainty. The corresponding measures are specifically tailored for the Naive Bayes classifier as a learning algorithm.

In the spirit of the Naive Bayes predictor, evidence-based uncertainty sampling first looks at the influence of individual features t p in the feature representation t = (t 1 , . . . , t P ) of instances. More specifically, given the current model θ, denote by p θ (t p | 0) and p θ (t p | 1) the class-conditional probabilities on the values of the p th feature. For a given instance t, the set of features is partitioned into those that provide evidence for the positive and for the negative class, respectively:

P θ (t) := t p p θ (t p | 1) p θ (t p | 0) > 1 , (4.43)
N θ (t) := t p p θ (t p | 0) p θ (t p | 1) > 1 . (4.44)
Then, the total evidence for the positive and the negative class is determined as follows:

E 1 (t) = t p ∈P θ (t) p θ (t p | 1) p θ (t p | 0) , (4.45)
E 0 (t) = t p ∈N θ (x) p θ (t p | 0) p θ (t p | 1) . ( 4.46)
The conflicting evidence-based approach simply queries the instance with the highest conflicting evidence, while the insufficient evidence-based approach looks for the one with the highest insufficient evidence:

t * conf = arg max t∈S E 1 (t) × E 0 (t) , (4.47)
t * insu = arg min t∈S E 1 (t) × E 0 (t) . (4.48)
Note that the selection is restricted to the set S of top high uncertain instances, i.e., those instances t in the pool U having a high score s(θ, t) according to standard uncertainty sampling. This ensures that the evidences for the two classes, E 0 (t) and E 1 (t), are close to each other. Then, a high conflicting evidence (4.47) captures the case where the evidences are close and both of large magnitude. In other words, it refers to the situation where a model is highly uncertain about an instance, and has strong but conflicting evidence for both classes. On the other hand, a high insufficientevidence uncertainty (4.48) refers to the case where a model is highly uncertain about an instance because of not having enough evidence for either class. Note, however, that this line of reasoning neglects the influence of the prior class probabilities, which is especially relevant in the case of imbalanced class distributions. In such cases, evidence-based uncertainty may strongly deviate from standard uncertainty, i.e., the entropy of the posterior distribution. For instance, E 0 (t) and E 1 (t) could both be very large, and p θ (t | 0) ≈ p θ (t | 1), although p θ (0 | t) is very different from p θ (1 | t) due to unequal prior odds, and hence the entropy small. Likewise, the entropy of the posterior can be large although both evidence-based uncertainties are small.

Credal uncertainty sampling

Credal uncertainty sampling [3] is another approach that seeks to differentiate between the reducible and irreducible part of the uncertainty. Denote by C ⊆ Θ a credal set of models, i.e., a set of plausible candidate models. We say that a class y dominates another class y if y is more probable than y for each distribution in the credal set, that is

s(y, y , t) := inf θ∈C p θ (y | t) p θ (y | t) > 1 . (4.49)
The credal uncertainty sampling approach simply looks for the instance t with the highest uncertainty, i.e, the least evidence for the dominance of one of the classes. In the case of binary classification with Y = {0, 1}, this is expressed by the score Such interval-valued probabilities can be produced within the framework of the Naive credal classifier [2,3,[START_REF] De Campos | Probability Intervals: A Tool for Uncertain Reasoning[END_REF]103]. In the case of binary classification, where p θ (0 | t) = 1 -p θ (1 | t), the score s(1, 0, t) can be rewritten as follows:

s(t) = -max s(1, 0, t), s(0, 1, t) . ( 4
s(1, 0, t) = inf θ∈C p θ (1 | t) p θ (0 | t) = inf θ∈C p θ (1 | t) 1 -p θ (1 | t) = p C (1 | t) 1 -p C (1 | t) (4.52)
Likewise,

s(0, 1, t) = inf θ∈C p θ (0 | t) p θ (1 | t) = inf θ∈C 1 -p θ (1 | t) p θ (1 | t) = 1 -p C (1 | t) p C (1 | t) . (4.53)
Finally, the uncertainty score (4.50) can simply be expressed as follows:

s(t) = -max p C (1 | t) 1 -p C (1 | t) , 1 -p C (1 | t) p C (1 | t) (4.54)

Principle of our method

Let us remind that, aleatoric uncertainty is due to the influences on the data-generating process that are inherently random, whereas the epistemic uncertainty is caused by a lack of knowledge. Or, stated differently, u e and u a , respectively defined in (4.6) and (4.7), measure the reducible and the irreducible part of the total uncertainty, respectively. It thus appears reasonable to assume that epistemic uncertainty is more relevant for active learning: while it makes sense to query additional class labels in regions where uncertainty can be reduced, doing so in regions of high aleatoric uncertainty appears to be less reasonable. This leads us to the principle of epistemic uncertainty sampling, which prescribes the selection t * = arg max t∈U u e (t) .

(4.55)

For comparison, we will also consider an analogous selection rule based on the aleatoric uncertainty, i.e.,

t * = arg max t∈U u a (t) , (4.56)
as well the toal uncertainty:

t * = arg max t∈U (u e (t) + u a (t)) . (4.57)
Note that the latter is closest to standard uncertainty sampling, where the entire uncertainty is quantified in a single measure. Let us remind that the above approach is completely generic and can in principle be instantiated with any hypothesis space Θ. The uncertainty measures (4.6-4.7) can be derived very easily from the support degrees (4.2-4.3). The computation of the latter may become difficult, however, as it requires the solution of an optimization problem, the properties of which depend on the choice of Θ (as studied in Sections 4.1.2-4.1.4).

Comparison with the evidence-based uncertainty sampling

Although the concepts of conflicting evidence and insufficient evidence of Sharma & Bilgic [START_REF] Sharma | Evidence-based Uncertainty Sampling for Active Learning[END_REF] appear to be quite related, respectively, to aleatoric and epistemic uncertainty, the correspondence becomes much less obvious (and in fact largely disappears) upon a closer inspection. Besides, a direct comparison is complicated due to various technical issues with their evidence-based approach. In particular, we will subsequently ignore the preselection of top high uncertain instances (i.e., the set S) in evidence-based uncertainty sampling, so as to separate the effect of their measures from standard entropy.

As a first important observation, note that the evidences E 1 (t) and E 0 (t) solely depend on the relation of the class-conditional probabilities p θ (t p | 1) and p θ (t p | 0), which hides the number of training examples they have been estimated from, and hence their confidence. The latter, however, has an important influence on whether we qualify something as aleatorically or epistemically uncertain. As an illustration, consider a simple example with two binary attributes, the first with domain {a 1 , a 2 } and the second with domain {b 1 , b 2 }. Denote by n i,j = (n + i,j , n - i,j ) the number of positive and negative example observed for (t 1 , t 2 ) = (a i , b j ). Here are three scenarios:

b 1 b 2 a 1 (1, 1) (1, 1) a 2 (1, 1) (1, 1) b 1 b 2 a 1 (100, 100) (100, 100) a 2 (100, 100) (100, 100) b 1 b 2 a 1 (1, 1) (10, 1) a 2 (1, 10) (1, 1)
In the first two scenarios, the insufficient evidence would be high, because all classconditional probabilities are equal. In our approach, however, the first scenario would largely be a case of epistemic uncertainty, due to the few number of training examples, whereas the second would be aleatoric, because the equal posteriors4 are sufficiently confirmed.

Similar remarks apply to conflicting evidence. In the third scenario, the latter would be high for (a

1 , b 1 ), because p θ (a 1 | 1) p θ (a 1 | 0) and p θ (b 1 | 0) p θ (b 1 | 1)
. The same holds for (a 2 , b 2 ), whereas the uncertainties for (a 1 , b 2 ) and (a 2 , b 1 ) would be low. Note, however, that in all these cases, exactly the same conditional probability estimates p θ (t p | 1) and p θ (t p | 0) are involved.

We would argue that the epistemic uncertainty should directly refer to these probabilities, because they constitute the parameter θ of the model. Thus, to reduce the epistemic uncertainty (about the right model θ), one should look for those examples that will mostly improve the estimation of these probabilities. Aleatoric uncertainty may occur in cases of posteriors close to 1/2, in which case the conflicting evidence may indeed be high (although, as already mentioned, the latter ignores the class priors). Yet, we would not necessarily call such cases a conflict, because the predictions are completely in agreement with the underlying model (Naive Bayes), which assumes class-conditional independence of attributes, i.e., an independent combination of evidences on different attributes.

Comparison with the credal uncertainty sampling

Credal uncertainty sampling seems to be closer to our approach, at least in terms of the underlying principle. In both approaches, the model uncertainty is captured in terms of a set of plausible candidate models from the underlying hypothesis space, and this (epistemic) uncertainty about the right model is translated into uncertainty about the prediction for a given t. In the credal uncertainty sampling, the candidate set is given by the credal set C, which corresponds to the distribution π Θ (θ | D) in our approach-as a difference, we thus note that ours is a graded set, to which a candidate θ belongs with a certain degree of membership (the relative likelihood), whereas a credal set is a standard set in which a model is either included or not. Using machine learning , the larger the score s(t), with the maximum being obtained for the case [0, 1] of complete ignorance. This is well in agreement with our degree of epistemic uncertainty. In the limit, when [p C (1 | t), p C (1 | t)] reduces to a precise probability p θ (1 | t), i.e., the epistemic uncertainty disappears, (4.54) is maximal for p θ (1 | t) = 1/2 and minimal for p θ (1 | t) close to 0 or 1. Again, this behavior is in agreement with our conception of aleatoric uncertainty. More generally, comparing two intervals of the same length, (4.54) will be larger for the one that is closer to the middle point 1/2. Thus, it seems that the credal uncertainty score (4.54) combines both epistemic and aleatoric uncertainty in a single measure.

Yet, upon closer examination, its similarity to our measure of epistemic uncertainty is much higher than the similarity to aleatoric uncertainty. Note that, for our approach, the special case of a credal set C can me imitated with the measure π

Θ (θ | D) = 1 if θ ∈ C and π Θ (h)(θ | D) = 0 if θ ∈ C. Then, (4.2) and (4.3) become π(1 | t) = sup θ∈C max[ 2 p θ (1 | t) -1, 0 ] = max[ 2 p C (1 | t) -1, 0 ] , π(0 | t) = sup θ∈C max[ 2 p θ (0 | t) -1, 0 ] = max[ 1 -2 p C (1 | t), 0 ] ,
and u e and u a can be derived from these values as before. Figure 4.2 shows a graphical illustration of the credal uncertainty score5 (4.54) as a function of the probability bounds p C and p C , and the same illustration is given for epistemic uncertainty u e and aleatoric uncertainty u a . From the visual impression, it is clear that the credibility score closely resembles u e , while behaving quite differently than u a . This impression is corroborated by a simple correlation analysis, in which we ranked the intervals In summary, the credal uncertainty score appears to be quite similar to our measure of epistemic uncertainty. As potential advantages of our approach, let us mention the following points. First, our degree is normalized and bounded, and thus easier to interpret. Second, it is complemented by a degree of aleatoric uncertainty-the two degrees are carefully distinguished and have a clear semantics. Third, handling candidate models in a graded manner, and modulating their influence according to their plausibility, appears to be more reasonable than creating an artificial separation into plausible and non-plausible models (i.e., the credal set and its complement).

[p C , p C ] ∈ I a,b = a 100 , b 100

Experimental evaluation

Some experiments are conducted to illustrate the performance of our uncertainty measures in active learning. Our main concern here is how fast different uncertainty sampling approaches improve the performance of classifiers and restrict ourselves to three classical models that are the local model, the logistic regression and the Naive Bayes classifier.

Local method

Data sets and experimental setting

We perform experiments on data sets from the UCI repository whose descriptions are given in Table 4.1. We follow a 5 × 5-fold cross-validation procedure: each data set is randomly split into 5 folds. Each fold is in turn considered as the test set, while the other folds are used for learning. The latter is randomly split into a training data set and a pool set. The proportions of (training, pool, test) sets are (20%, 60%, 20%). The whole procedure is repeated 5 times, and accuracies are averaged. The budget of the active learner is fixed to be the length of the pool, and the performance of the classifiers is monitored over the entire learning process.

After each query, we update the data sets and, correspondingly, the classifiers. The improvements of the classifiers are compared for four different uncertainty measures, i.e., uncertainty sampling (following the strategy presented in Algorithm 18) based on four measures for selecting unlabelled instances: standard uncertainty (4.41), epistemic uncertainty (4.6), aleatoric uncertainty (4.7), total of epistemic and aleatoric uncertainty (4.57).

We also evaluate how quickly the querying procedure will be able to fill the low density regions. To this end, we measure the maximal distance between testing instances and their nearest neighbours.

Experimental results

Experiments were conducted for two values of the width , corresponding to neighborhood sizes K = 4 and K = 8. These can be considered as a small and large width of the Parzen window. Since the results are very similar, we only present those for the case K = 8.

As it can be seen in Figure 4.3, the results are nicely in agreement with our expectations: the epistemic uncertainty sampling performs the best and the aleatoric uncertainty sampling the worst. Moreover, the standard uncertainty sampling is inbetween the two, very similar to total uncertainty (aleatoric plus epistemic). This supports our conjecture that, from an active learning point of view, the epistemic uncertainty is the more useful information. Even if the improvements compared to standard uncertainty sampling are not huge, they are still visible and quite consistent.

Figure 4.4 also shows that the epistemic uncertainty sampling achieves the best coverage of the instance space, measured in terms of the maximal distance between testing instances and their nearest neighbours. As expected, the aleatoric uncertainty is again the worst, and standard uncertainty sampling is in-between.

Logistic regression

Data sets and experimental setting

We perform experiments on the same UCI data sets as before (cf. Table 4.1). To avoid the relatively strong bias imposed by the linear model assumption, we start with a very small amount of initial training data, thereby making improvements in the beginning more visible. We conduct a 10 × 3-fold cross validation procedure: each data set is split into 3 folds. Each fold is in turn considered as the learning set, while other folds are used for testing. The learning set is randomly split into a training data set and a pool set. The proportions of (training, pool, test) set are (1%, 32%, 67%).

The whole procedure is repeated 10 times, and the accuracies are averaged. Similar to the case of the local learning, we fix the budget to be the length of the pool.

In addition to accuracy, we monitor the convergence of the ML estimate θ toward the best model θ * . Since the latter is not known, we use the parameter that would have been learned on the entire data as a surrogate. More specifically, we measure the convergence in terms of the Euclidean distance θ-θ * , and average over a sufficiently large number of repetitions to smooth the curves.

As before, the uncertainty sampling (Algorithm 18) is instantiated with four measures for selecting unlabelled instances: standard uncertainty (4.41), epistemic uncertainty (4.6), aleatoric uncertainty (4.7), and the sum of epistemic and aleatoric uncertainty (4.57). This time, we also include the conflicting-evidence (Conf) and insufficient-evidence (Insu) measures by Sharma & Bilgic [85]6 . Let us remind that these measures are tailored for Naive Bayes as a classifier. Yet, in contrast to the case of local learning, a comparison is now meaningful, because both linear regression and Naive Bayes construct a linear decision boundary.

Experimental results

As can be seen in Figure 4.5, the epistemic uncertainty sampling does again perform quite well in comparison to the others, except on the ionosphere data. Moreover, it achieves the overall best convergence to the best model, as shown in Figure 4.6. Furthermore, in Figure 4.6, it is clear that the improvements provided by difference uncertain measure are well-fitted to our expectation that epistemic and aleatoric uncertainty sampling provide, respectively, the best and the least improvement while the classical uncertainty sampling and the total of epistemic and aleatoric uncertainty provide something in between. Finally, no general pattern has been drawn for evidence-based uncertain measures.

Compared with the case of local learning, however, the improvements in comparison to standard uncertainty sampling are now smaller, and sometimes completely disappear. This is arguably due to the relatively strong bias imposed by the linear model assumption: Although we initialize with a comparatively small set of training data, the learning curves converge quite quickly (in the case of climate and blood, there is almost no improvement at all). In other words, the linear model is more or less fixed from the beginning, so that it becomes difficult for any sampling strategy to make a real difference.

Naive Bayes

Data sets and experimental setting

We perform experiments on the first two small data sets described in the Table 4.1.

Similarly to the case of logistic regression, we start with a very small amount of initial training data, thereby making improvements in the beginning more visible. We conduct a 10 × 3-fold cross validation procedure: Each data set is split into 3 folds. The learning set is randomly split into a training data set and a pool set. The proportions of (training, pool, test) set are (5%, 28%, 67%). The whole procedure is repeated 10 times, and the accuracies are averaged. We fix the budget to be the length of the pool. Let us note that we start from a slightly larger training data to reduce the effect of the zero frequency problem which could present unexpected effects when assessing the improvements provided by the methods.

In addition to accuracy, we monitor the convergence of the Kullback-Leibler divergence (KL divergence) of θ toward the best model θ * . Since the latter is not known, we use the parameter that would have been learned on the entire data as a surrogate. More specifically, we measure convergence in terms of D KL (θ * θ), which is often called the information gain achieved if θ is used instead of θ * , such that:

D KL (θ * θ) = - i θ * (i) ln θ(i) θ * (i) .
As before, uncertainty sampling (Algorithm 18) is instantiated with six measures for selecting unlabelled instances: standard uncertainty (4.41), epistemic uncertainty (4.6), aleatoric uncertainty (4.7), the sum of epistemic and aleatoric uncertainty (4.57), the conflicting-evidence (Conf) and insufficient-evidence (Insu) measures by Sharma & Bilgic [START_REF] Sharma | Evidence-based Uncertainty Sampling for Active Learning[END_REF]. In addition, we employ the credal uncertainty sampling (Credal), which shares similar purpose with our interests and is applicable for Naive Bayes, to select unlabelled instances.

Experimental results

As can be seen in Figure 4.7-4.8, there are very similar improvements provided by four methods: standard uncertainty (4.41), epistemic uncertainty (4.6), aleatoric uncertainty (4.7), the sum of epistemic and aleatoric uncertainty (4.57). The evidence-based methods and credal uncertainty sampling (Credal) appear less effective in this test.

We think that these behaviors could be due to the presence of zero frequencies. For instance, if we see zero frequencies when assessing an instance t, (4.33) implies that the probabilities assigned for both classes are close to 0.5. On the other hand, the plausible hypotheses tend to assign for t the conditional probabilities around 0.5. Consequently, (4.19) and (4.20) suggest that the degrees of support for both classes are close to zero, i.e, a high degree of aleatoric uncertainty.

We thus derive a hypothesis that zero frequency problem have introduced another kind of uncertainty (lack of knowledge on the unobserved parameters θ p,tp 1 and θ p,tp 0 ) that will be preferred by both the standard uncertainty (4.41) and aleatoric uncertainty (4.7). In contrast, the epistemic uncertainty (4.6) is interested in the lack of knowledge on some observed parameters. How to effectively investigate such situations is not obvious, we thus leave it as an open problem.

Cautious inference

This section presents a method for reliable prediction in multi-class classification, where the reliability refers to the possibility of partial abstention in cases of uncertainty. More specifically, we allow for predictions in the form of preorder relations on the set of classes, thereby generalizing the idea of set-valued predictions. Our approach relies on combining learning by pairwise comparison with the distinction made between reducible (a.k.a. epistemic) uncertainty caused by a lack of information and irreducible (a.k.a. aleatoric) uncertainty due to intrinsic randomness. The problem of combining uncertain pairwise predictions into a most plausible preorder is then formalized as an integer programming problem. This inference procedure is inspired by the belief functions-based approach proposed recently by Masson et al. [START_REF] Masson | Modelling and predicting partial orders from pairwise belief functions[END_REF].

Principle of our method

We are going to present our approach to reliable multi-class prediction, which is based on the idea of binary decomposition and a stepwise simplification (approximation) of the information contained in the set of pairwise comparisons between classes-first in terms of a preorder and then in terms of a set.

Learning by Pairwise Comparison

In Learning by pairwise comparison (LPC) a.k.a. all-pairs is a decomposition technique that trains one (binary) classifier θ i,j for each pair of classes (y i , y j ), 1 ≤ i < j ≤ M [START_REF] Fürnkranz | Round robin classification[END_REF]. The task of θ i,j , which is trained on D i,j = D i ∪ D j , is to separate instances with label y i from those having label y j . Suppose we solve these problems with the approach described in the previous section, instead of using a standard binary classifier. Then, given a new query instance t ∈ X , we can produce predictions in the form of a quadruple I i,j (t) := s i,j y i (t), s i,j y j (t), u i,j e (t), u i,j a (t) ,

one for each pair of classes (y i , y j ). These predictions can also be summarized in three [0, 1] M ×M relations, a (strict) preference relation P , an indifference relation A, and an incomparability relation E: P = s i,j y i (t) i,j , A = u i,j a (t) i,j , E = s i,j e (t) i,j

Let us note that, in our approach, predictions are always derived per instance, i.e., for an individual query instance t. Likewise, all subsequent inference steps are tailored for that instance. Keeping this in mind, we will henceforth simplify notations and often omit the dependence of scores and relations on t.

Inferring a preorder

The structure (P, A, E) provides a rich source of information, which we seek to represent in a condensed form. To this end, we approximate this structure by a preorder R. This approximation may also serve the purpose of correction, since the relational structure (P, A, E) is not necessarily consistent; for example, since all binary classifiers are trained independently of each other, their predictions are not necessarily transitive.

Recall that a preorder is a binary relation R ⊆ Ω × Ω that is reflexive. In the following, we will also use the following notation: y i R y j (or simply y i y j ) if r i,j = 1, r j,i = 0 , y i ∼ R y j (or simply y i ∼ y j ) if r i,j = 1, r j,i = 1 , y i ⊥ R y j (or simply y i ⊥ y j ) if r i,j = 0, r j,i = 0 , where r i,j = 1 if (y i , y j ) ∈ R and r i,j = 0 if (y i , y j ) ∈ R. Note that the binary relations , ∼, ⊥ are in direct correspondence with the relations P , A, and E, respectively. How compatible is a relation R with a structure (P, A, E)? Interpreting the scores (4.58) as probabilities, we could imagine that a relation R is produced by randomly "hardening" the soft (probabilistic) structure (P, A, E), namely by selecting one of the relations y i y j , y j y i , y i ∼ y j , y i ⊥ y j with probability s i,j y i , s i,j y j , u i,j a , and u i,j e , respectively. Then, making a simplifying assumption of independence, the probability of ending up with R is given as follows: p(R) = y i R y j s i,j y i y j R y i s i,j y j y i ⊥ R y j u i,j e y i ∼ R y j u i,j a (4.59)

The most probable preorder R * then corresponds to

R * = arg max R∈R p(R) , (4.60)
where R is the set of all preorders on Y.

Let us now propose a practical procedure to determine R * , which is based on representing the optimization problems (4.60) as a binary linear integer program. To this end, we introduce the following variables: X 1 i,j = r i,j (1 -r j,i ), X 2 i,j =r j,i (1 -r i,j ), X 3 i,j = (1 -r i,j )(1 -r j,i ), X 4 i,j = r i,j r j,i .

Then, by adding the constraints 4 l=1 X l i,j = 1 and X l i,j ∈ {0, 1}, we can rewrite the probability (4.59) as follows:

p(R) = i<j s i,j λ i X 1 i,j s i,j λ j X 2
i,j u i,j e X 3 i,j u i,j a X 4 i,j (4.61) Furthermore, the transitivity property r i,k + r k,j -1 ≤ r i,j , ∀ i = j = k.

(4. [START_REF] Menard | Applied Logistic Regression Analysis[END_REF] can easily be encoded by noting that r i,j = X 1 i,j + X 4 i,j and r i,j = X 2 j,i + X 4 j,i if i < j and j < i, respectively.

Altogether, the most probable preorder R * ∈ R is determined by X * = (X 1 i,j , . . . , X 4 i,j ) i,j , which is the solution of the following optimization problem: max i<j X 1 i,j ln s i,j λ i + X 2 i,j ln s i,j λ j + X 3 i,j ln u i,j e + X 4 i,j ln u i,j a (4.63) s.t. X l i,j = 1, ∀ 1 ≤ i < j ≤ M , X 1 i,j , X 2 i,j , X 3 i,j , X 4 i,j ∈ {0, 1}, ∀ 1 ≤ i < j ≤ M , r i,k + r k,j -1 ≤ r i,j , ∀ i = j = k . Note that if u i,j e = 0 for all pairs, then the solution will be a complete preorder (in which the binary relations are either ∼ or ) between class probabilities, which is consistent with our interpretation. Similarly, if u i,j a = 0 and u i,j e = 0 for all pairs, we would obtain a linear ordering, as in [START_REF] Cheng | Probability estimation for multi-class classification based on label ranking[END_REF].

Obtaining credible sets from R * Consider the preorder R * = R * (t) for an unlabelled query instance t, and suppose we seek a set-valued prediction θ(t) ⊆ Y. A reasonable way to obtain such a prediction is to collect all non-dominated classes, i.e., to exclude only those classes y j for which y i R * y j for at least one competing class y i . A class label of that kind can be seen as a potentially optimal prediction for t. Adopting the above notation, the set-valued prediction can thus be determined as

θ(t) = y i ∈ Y | j<i X 1 j,i + i<j X 2 i,j = 0 , (4.64)
which means that it can immediately be derived from the solution of (4.63). Note that full uncertainty, i.e, θ(t) = Y, only occur if all pairs (y i , y j ) are incomparable or indifferent. How to obtain a set-valued prediction from the pairwise information is illustrated in the following example.

Example 18. Assume that we have the output space Y = {y 1 , . . . , y 5 } and pairwise information (4.58) for an unlabelled instance t given by the following quadruples: I 1,2 (t) = (0, 0.1, 0.6, 0.3), I 1,3 (t) = (0.6, 0, 0.1, 0.2), I 1,4 (t) = (0.9, 0, 0.1, 0), I 1,5 (t) = (0.4, 0, 0.3, 0.3), I 2,3 (t) = (0.6, 0, 0.2, 0.2), I 2,4 (t) = (0.7, 0, 0, 0.3), I 2,5 (t) = (0.9, 0, 0, 0.1), I 3,4 (t) = (0.6, 0, 0.2, 0.2), I 3,5 (t) = (0.9, 0, 0.1, 0), I 4,5 (t) = (0.05, 0.05, 0.4, 0.5).

Solving the optimization problem (4.63) gives the most probable preorder R * pictured in Figure 4.9 with the corresponding value X * s.t. X 3 1,2 = X 1 1,3 = X 1 2,3 = X 1 3,4 = X 1 3,5 = X 4 4,5 = 1. Finally, from (4.64) we get θ(t) = {1, 2}.

Experimental evaluation

This section presents some experimental results to assess the performance of our approach to reliable classification.

Data sets and experimental setting

We perform experiments on 15 data sets from the UCI repository (cf. Table 4.2), following a 10 × 10-fold cross-validation procedure. We compare the performance of our method (referred to as PREORDER) with two competitors. To make the results as comparable as possible, these methods are also implemented with pairwise learning using a logistic regression classifier as base learner. Thus, they only differ in how the pairwise information provided by the logistic regression is turned into a (reliable) multi-class prediction.

• VOTE: The first method is based on aggregating pairwise predictions via standard voting, which is a common approach in LPC. However, instead of simple weighted voting, we apply the more sophisticated aggregation technique proposed in [START_REF] Hüllermeier | Combining predictions in pairwise classification: An optimal adaptive voting strategy and its relation to weighted voting[END_REF], which shows better performance. Note that, by predicting the winner of the voting procedure, this approach always produces a precise prediction.

• NONDET: As a baseline for set-valued predictions, we use the approach of [START_REF] Coz | Learning Nondeterministic Classifiers[END_REF], which has been shown to exhibit competitive performance in comparison to other imprecise prediction methods [104]. Recall that this approach produces nondeterministic predictions from precise probabilistic assessments. This requires turning pairwise probability estimates into conditional probabilities (p θ (y 1 | t), . . . , p θ (y M | t)) on the classes, a problem known as pairwise coupling. To this end, we apply the δ 2 method, which performs best among those investigated in [START_REF] Wu | Probability estimates for multi-class classification by pairwise coupling[END_REF].

Evaluation metrics for assessing set-valued predictions have to balance correctness (the true class y is an element of the predicted set Y := θ(t)) and precision (size of the predicted set) in an appropriate manner. For example, in [104], the authors argue that using the simple discounted accuracy (1/|Y | if y ∈ Y and 0 otherwise) is equivalent to saying that producing a set-valued prediction is the same as choosing within this set (uniformly) at random. This means that the discounted accuracy does not reward any cautiousness. Also, it can be shown that minimizing the expected discounted accuracy in expectation would never lead to imprecise predictions [ Here, we therefore adopt the average utility-discounted accuracy measure, which has been proposed and formally justified in [104]:

u(y, Y ) =    0 if y / ∈ Y φ 1 |Y | - φ 2 |Y | 2 otherwise
More specifically, we use the measures u 65 with (φ 1 , φ 2 ) = (1.6, 0.6) and u 80 with (φ 1 , φ 2 ) = (2.2, 1.2). Note that, in the case of precise decisions, both u 65 and u 80 reduce to standard accuracy.

Experimental Results

The average performances in terms of the utility-discounted accuracies are shown in Table 4.3, with ranks in parenthesis (note that we provide one set of ranks for u 65 , and another one for u 80 ). Firstly, we notice that PREORDER yields the best average ranks over the 15 data sets, both for u 80 and u 65 . Furthermore, a Friedman test [START_REF] Demšar | Statistical comparisons of classifiers over multiple data sets[END_REF] on the ranks yields p-values of 0.0003138 and 0.002319 for u 80 and u 65 , respectively, thus strongly suggesting performance differences between the algorithms. The Nemenyi post-hoc test (see Table 4.4) further indicates that PREORDER is significantly better than VOTE regarding u 80 and NONDET in the case of u 65 . Since u 80 rewards cautious predictions stronger than u 65 does, it is not surprising that indeterminate classifiers do better in this case. Yet, even when considering u 65 , PREORDER remains competitive with VOTE. This suggests that it tends to be more precise than NONDET, while still accurately recognizing those instances for which we have to be cautious.

Ideally, an imprecise classifier should abstain (i.e., provide set-valued predictions) on difficult cases, on which the precise classifier is likely to fail [101]. The goal of Figure of correct partial predictions, while the corresponding percentages of VOTE vary in a wider range. Also, the accuracy of the latter significantly drops on those instances (for example, the average accuracy for data set g is 50% in Table 4.3, but drops to less than 30% in Figure 4.10(a)), confirming that the imprecise classifiers do indeed abstain on difficult cases. Finally, note that the points in Figure 4.10(a) are a bit more to the left than those in Figure 4.10(b), again suggesting that PREORDER is doing slightly better in recognizing difficult instances than NONDET.

For the two imprecise classifiers, we also compare the average proportion of partial predictions and the average (normalized) size of the predictions when at least one method produces a partial prediction.

Conclusion

Yet the distinction between epistemic and aleatoric uncertainty has been increasingly studied, a lack of efficient techniques to estimate these degrees of the uncertainty seems to restrict its subsequent applications. We have proposed estimators for popular classifiers and used it to solve two machine learning problems: active learning and cautious inference. Our general conclusion is that the distinction between epistemic and aleatoric uncertainty can indeed provide advantages for subsequent machine learning applications.

Active learning

We reconsider the principle of uncertainty sampling in active learning from the perspective of uncertainty modeling. More specifically, it starts from the supposition that, when it comes to the question of which instances to select from a pool of candidates, a learner's predictive uncertainty due to not knowing should be more relevant than its uncertainty due to inherent randomness.

To corroborate this conjecture, we have proposed the epistemic uncertainty sampling, in which standard uncertainty measures such as the entropy are replaced by a novel measure of epistemic uncertainty. The latter is borrowed from a recent framework for uncertainty modeling, in which the epistemic uncertainty is distinguished from the aleatoric uncertainty [START_REF] Senge | Reliable Classification: Learning Classifiers that Distinguish Aleatoric and Epistemic Uncertainty[END_REF]. In comparison to previous proposals based on similar ideas, our approach is arguably more principled. Moreover, it is completely generic and can be instantiated with any (probabilistic) classifier as a learning algorithm.

We interpret the experiments conducted with a simple local learning algorithm (Parzen window classifier) and logistic regression as evidence in favor of our conjecture. They clearly show that a separation of the total uncertainty (into epistemic and aleatoric) is effective, and that the epistemic part is the better criterion for selecting instances to be queried. As already said, investigating how to effectively implement our approach for the case of Naive Bayes requires significant extra efforts and will be left as an open problem.

Cautious inference

We have introduced an approach to cautious inference and reliable prediction in multiclass classification. The basic idea is to provide predictions in the form of preorder relations, which allow for representing preferences for some candidate classes over others, as well as indifference and incomparability between them; the two latter relations are in direct correspondence with two types of uncertainty, aleatoric and epistemic. This can be seen as a sophisticated way of partial abstention, which generalizes setvalued predictions and classification with reject option. Technically, our approach combines reliable binary classification with pairwise decomposition and approximate inference over preorders. Our experiments on this type of problem are quite promising and suggest that our method is highly competitive to existing approaches to reliable prediction. Yet, by using to the set of maximal elements, we only used preorder predictions for the purpose of set-valued classification. The preoder, however, provides very rich information about the preference for classes, which could be used for other purposes.

Chapter 5

Conclusion, perspectives and open problems

In this work, we have studied different aspects of imprecision treatment, focusing on two potential settings where imprecision due to imperfect data and imperfect knowledge, respectively. Considering the former setting, we have studied both the problem of making inference and the one of learning an optimal model from partially specified data. We have investigated different potential situations where one may have to deal with multiple optimal decisions (either labels or models) due to the presence of partial data and developed active learning techniques to tackle these situations. We have focused, in the later setting, on the situations where data are precisely specified, however, these are classes that can not be distinguished due to a lack of knowledge or due to a high uncertainty. In particular, we have advocated a distinction between epistemic and aleatoric uncertainty in machine learning problems.

The main conclusions from Chapter 2, in which we have (1) implemented the maximax approach for the case of partially featured data and (2) developed active learning approaches to reduce the imprecision in the inference step due to the presence of partial data, are following:

-We can employ the maximax approach to make inferences from partially specified data using tractable and scalable techniques. Furthermore, in complement to the promising results regarding the case of partially labelled data, our experiments indicate that, in the case of partially featured data, a simple imputation method could often work as well as the maximax approach, but for some data sets the maximax approach can bring a real advantage. This conclusion can motivate further research on broadening the applications of the maximax approach.

-The possible and necessary label sets have appeared to be efficient tools for quantifying the imprecision introduced to learners by partial data. Experimentally, our investigation have indicated that (1) there are situations where partial data can indeed affect the predictive ability of the maximax approach (e.g, when employing a small number K or there is a large amount of partial labels) and

(2) by doing active learning, we can significantly improve the performance of the maximax approach.

-The perspectives we provided in the end of this Chapter could benefit future attempts on tackling both the problem of making inferences and the active learning in the generic setting of partially specified data.

The first conclusion from Chapter 3 is that, together with the active learning proposal presented in Chapter 2, we have addressed different settings of the active learning problem for partial data. This problem has been little explored in the literature, in Chapter 5. Conclusion, perspectives and open problems particular in the case of partially featured data. Furthermore, the improvements on all criteria suggest that the presence of partial data can introduce significant imprecision to the learning step. Considering the case of partially featured data, our racing algorithms have consistently outperformed other simple baselines. This means that doing active learning in this case is a promising direction while it is not necessarily the case for partially labelled data where even random strategies performs similar to others. Yet, our proposals have been developed upon noticeable intuitions. Developing more sophisticated approaches would be a worthy research direction.

From Chapter 4, we can conclude that a separation of the total uncertainty into epistemic and aleatoric part is effective.

-In the active learning problem, the epistemic part has appeared to be the better criterion for querying instances. Given this affirmation, we are now encouraged to elaborate on epistemic uncertainty sampling in more depth, and to develop it in more sophistication. This also includes an extension to other active learning strategies (e.g., expected model change).

-Considering the problem of making cautious inferences, the distinction epistemic/aleatoric uncertainty provides pairwise information from which we can learn predictions in the form of preorder relations. Such a preorder allows for representing preferences for some candidate classes over others, as well as indifference and incomparability between them. It thus suggests reasons for why a class should be included into or discarded from the set-valued prediction. This characteristic gives the ability to appropriately balance reliability and precision which is a crucial demand when doing cautious inferences. Thus, next research efforts should focus on exploiting more of the potential of preorder predictions, and to use such predictions in other contexts and problem settings. In active learning, for example, preorder predictions may provide very useful information for guiding the selection of queries. Since our approach applies as soon as a likelihood is defined, extending it to other kinds of likelihood such as evidential ones [START_REF] Denoeux | Likelihood-based belief function: justification and some extensions to low-quality data[END_REF] would be another promising direction.

xiii List of Figures 1 . 1

 11 Inductive versus transductive learning . . . . . . . . . . . . . . . . . . 2.1 Example with |D| = 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 3-nn classifiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1 Illustration of partial data and competing models . . . . . . . . . . . . 3.2 Illustration of interval-valued instances . . . . . . . . . . . . . . . . . . 3.3 Illustrations for the different possible cases corresponding to the pairwise difference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Experiments for interval-valued features data with preferred model . . 3.5 Experiments for interval-valued features data with preferred model . . 3.6 Experiments for set-valued labels data with preferred model . . . . . . 3.7 Experiments for set-valued labels data with preferred model . . . . . . 3.8 Decision tree illustration θ l . . . . . . . . . . . . . . . . . . . . . . . . 3.9 Example of imprecise instance . . . . . . . . . . . . . . . . . . . . . . . 3.10 Case where the union of intervals is not an interval . . . . . . . . . . . 3.11 Example of determining the single effect . . . . . . . . . . . . . . . . . 3.12 Example of determining the pairwise effect . . . . . . . . . . . . . . . . 3.13 Interval-valued features: Size of undominated model sets . . . . . . . . 3.14 Interval-valued features: Similarity between the current best and reference models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.15 Interval-valued features: Accuracy on the test set . . . . . . . . . . . . 3.16 Experiments for set-valued label data with preferred model . . . . . . 4.1 From left to right: Epistemic, aleatoric, and the total of epistemic aleatoric uncertainty as a function of the numbers of positive (x-axis) and negative (y-axis) examples in a region (Parzen window) of the instance space (lighter colors indicate higher values). . . . . . . . . . . 4.2 From left to right: Exponential rescaling of the credal uncertainty measure, epistemic uncertainty and aleatoric uncertainty for interval probabilities with lower probability (x-axis) and upper probability (y-axis). Lighter colors indicate higher values. . . . . . . . . . . . . . . . . . . . 4.3 Average accuracies (y-axis) over 5 × 5-folds for the Parzen window classifier (K = 8) as a function of the number of examples queried from the pool (x-axis). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4 Average maxmin distances (y-axis) over 5 × 5-folds for the Parzen window classifier (K = 8) as a function of the number of examples queried from the pool (x-axis). . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.5 Average accuracies (y-axis) over 10 × 3-folds for logistic regression as a function of the number of examples queried from the pool (x-axis). . . 4.6 Average distances (y-axis) over 10 × 3-folds for logistic regression as a function of the number of examples queried from the pool (x-axis). . .

xiv 4 . 7

 47 Average accuracies (y-axis) over 10 × 3-folds for Naive Bayes as a function of the number of examples queried from the pool (x-axis). . . . . 4.8 Average KL divergence (y-axis) over 10 × 3-folds for Naive Bayes as a function of the number of examples queried from the pool (x-axis). . . 4.9 Preorder induced by Example 18 (strict preference symbolized by directed edge, indifference by undirected edge, incomparability by missing edge). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.10 (a) Correctness of the PREORDER in the case of abstention versus accuracy of the VOTE. (b) Correctness of the NONDET in the case of abstention versus accuracy of the VOTE. (c) Proportion of partial predictions when at least one method produces a partial prediction. (d) Average normalized size of the predictions in such cases. . . . . . . . .

Figure 1 . 1 :

 11 Figure 1.1: Inductive versus transductive learning

θ

  * = arg max θ∈Θ L(θ | D) := arg max θ∈Θ N n=1 p θ (y n | x n ).

  θ∈Θ L(θ | D) : = arg max θ∈Θ N n=1 p θ (x n , y n ) = arg max θ∈Θ N n=1 p θ (y n ) P p=1 p θ (x p n | y n ). (1.5)

  .16) where c p n = (b p n + a p n )/2 and r p n = (b p n -a p n )/2, the center and width of the interval X p n = [a p n , b p n ], for p = 1, . . . , P . Such interval of distances allow us to define a partial

X

Figure 2 . 2 :

 22 Figure 2.2: 3-nn classifiers

( D1 )

 D1 Case y ∈ NL t and y ∈ Y n : once query q n is performed, the minimal score of y is unchanged because y ∈ Y n , s min,qn t (y) = s min t (y). The maximal scores of labels in Y n is max y ∈Yn s max,qn t (y ) = max max y ∈Yn s max t (y ) -w n , min y ∈Yn s max t (y ) , because all labels within Y n see their maximal scores decrease, except one. The maximal scores outside y n remain unchanged: max y =y,y ∈Yn s max,qn t (y ) = max y =y,y ∈Yn s max t (y ). Then satisfying Equation (2.40) in case (C1) is equivalent to

Figure 3 .

 3 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.

Figure 3 . 1 :

 31 Figure 3.1: Illustration of partial data and competing models

2 Figure 3 . 2 :

 232 Figure 3.2: Illustration of interval-valued instances

Figure 3 . 3 :

 33 Figure 3.3: Illustrations for the different possible cases corresponding to the pairwise difference

  the upper bound is negative. The next proposition indicates how to easily compute the lower bound k-l (y n , X n ) for the different possible situations. Proposition 14. Given (X n , y n ) with X p n = [a p n , b p n ] and two models θ k , θ l s.t. (X n , y n ) is imprecise w.r.t. both models, then the minimal difference value is

Figure 3 . 4 :Figure 3 . 5 :Figure 3 . 6 :Figure 3 . 7 :

 34353637 Figure 3.4: Experiments for interval-valued features data with preferred model

Figure 3 . 8 :

 38 Figure 3.8: Decision tree illustration θ l

  10], X 2 = [10, 20], Y = {a, b, c}.

Figure 3 .

 3 Figure 3.8 illustrates a possible decision tree θ l for the above setting.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 θ l (x 1 ) = c while x 2 will reach leaf t 1 with an assigned class θ l (x 2 ) = a.

Algorithm 7 :

 7 A single step to query set-valued data. Input: Training data set D = {(x n , Y n )} N n=1 , label set Y = {y 1 , . . . , y M }, set of undominated models Θ * . Output: The optimal query q n * 1 foreach θ k ∈ Y do 2 Compute empirical risk (R(θ k | D), R(θ k )) bounds using Alg. 8;

  and y h = y n and y h = y n . (3.55) Note that (3.55) can be easily determined using (3.53). The following Example gives illustrations of an imprecise instance w.r.t. a given decision tree.

Figure 3 . 10 :Algorithm 11 :

 31011 Figure 3.10: Case where the union of intervals is not an interval

2 x 2 2Figure 3 . 11 :

 22311 Figure 3.11: Example of determining the single effect

Figure 3 . 13 :Figure 3 . 14 :Figure 3 . 15 :

 313314315 Figure 3.13: Interval-valued features: Size of undominated model sets

# 1 #Figure 3 . 16 :

 1316 Figure 3.16: Experiments for set-valued label data with preferred model

Figure 4 . 1 :

 41 Figure 4.1: From left to right: Epistemic, aleatoric, and the total of epistemic aleatoric uncertainty as a function of the numbers of positive (x-axis) and negative (y-axis) examples in a region (Parzen window) of the instance space (lighter colors indicate higher values).

Algorithm 16 : 2 foreach x m = x n do 3 compute d x n , x m ; 4 form 1 ×; 4 . 1 . 3

 162341413 Determining the width δ. Input: D-normalized data, K-number Output: the local width δ K 1 foreach x n ∈ D do (n -1) vector d n = d x n , x m | n = m ; 5 sort d n by increasing order and determine the K-th element d K n ; 6 return δ K = Estimation for logistic regressionRecall that logistic regression assumes posterior probabilities to depend on feature vectors x = (x 1 , . . . , x P ) ∈ R P in the following way:θ(x) = p θ (1 | x) = exp θ 0 + P p=1 θ p x p1 + exp θ 0 + P p=1 θ p x p (4.13)

1 )

 1 min π Θ (θ * α | D), 2α -1 (4.19)

. 50 )

 50 Practically, the computations are based on the interval-valued probabilities, denoted by [p C (y | t), p C (y | t)], assigned to each class y ∈ Y, where p C (y | t) := inf θ∈C p θ (y | t) , p C (y | t) := sup θ∈C p θ (y | t) .(4.51)

Figure 4 . 2 :

 42 Figure 4.2: From left to right: Exponential rescaling of the credal uncertainty measure, epistemic uncertainty and aleatoric uncertainty for interval probabilities with lower probability (x-axis) and upper probability (y-axis). Lighter colors indicate higher values.

Figure 4 . 3 :

 43 Figure 4.3: Average accuracies (y-axis) over 5×5-folds for the Parzen window classifier (K = 8) as a function of the number of examples queried from the pool (x-axis).

Figure 4 . 4 :

 44 Figure 4.4: Average maxmin distances (y-axis) over 5 × 5-folds for the Parzen window classifier (K = 8) as a function of the number of examples queried from the pool (x-axis).

Figure 4 . 6 :

 46 Figure 4.6: Average distances (y-axis) over 10 × 3-folds for logistic regression as a function of the number of examples queried from the pool (x-axis).

  0

Figure 4 . 8 :

 48 Figure 4.8: Average KL divergence (y-axis) over 10 × 3-folds for Naive Bayes as a function of the number of examples queried from the pool (x-axis).

  the multi-class classification setting, we are dealing with a set of M > 2 classes Y = {y 1 , . . . , y M }. Suppose a set of training data D = {(x n , y n )} N n=1 to be given, and denote by D m = {x n | (x n , y m ) ∈ D} the observations from class y m .

4 l=1

 4

Figure 4 . 9 :

 49 Figure 4.9: Preorder induced by Example 18 (strict preference symbolized by directed edge, indifference by undirected edge, incomparability by missing edge).

# H 0 u 80 u 65 1 VTable 4 . 4 :

 144 = P 0.00017 0.3101 2 V = N 0.11017 0.1102 3 P = N 0.11017 0.0015 Nemenyi post-hoc test: null hypothesis H 0 and p-value 4.10(a,b) is to verify this ability.

Figure 4 .

 4 10(a) displays, for each data set, the percentage of times the true class is in the prediction of PREORDER, given the prediction was imprecise, versus the accuracy of VOTE on those instances.

Figure 4 .

 4 10(b) does the same for NONDET. Both imprecise classifiers achieve high percentages (> 80)

Figures 4. 10

 10

  (c) and4.10(d) indicate that NONDET produces more partial predictions of (slightly) larger size.

Figure 4 . 10 :

 410 Figure 4.10: (a) Correctness of the PREORDER in the case of abstention versus accuracy of the VOTE. (b) Correctness of the NON-DET in the case of abstention versus accuracy of the VOTE. (c) Proportion of partial predictions when at least one method produces a partial prediction. (d) Average normalized size of the predictions in such cases.

Table 1 .

 1 1, or going through the vertical structure for a method flow.

			Method
	Problem	Transductive	Inductive Loss minimization likelihood
	Learning from partial data	Chapter 2
	Active learning for partial data	Chapter 2	Chapter 3
	Active learning for classical data		Chapter 4
	Cautious inference		Chapter 4

Table 1 .

 1

1: Summary of the work Chapter 2

Table 2 .

 2

1: The corresponding ζ matrix for example in Figure 2.1 order on the set D of training instance as follows

  ). bounds the number of instances that could be in the set of nearest neighbours and have y for label, while the value |{X n | X n ∈ PN t , y n = y}| simply gives the maximal number of such elements that are available within the set of possible neighbours, and that may be chosen freely to be/not be in the neighbour set, as long as they remain lower than the bound Ky =y s small

	(y ). So, maximising t (y), recalling that we just proved that t (y). (y) = min d∈D s d this number of elements simply provides s max t Let us now prove that s min t s max (y) is reachable for some replacement. We are going to focus on two cases: t Case 1: s small t (y) ≥ K -y =y s max t (y ) implies that s min t (y) = s small t (y), hence
	for every replacement there is at least s small t more, s small t (y) ≥ K -y =y s max t (y ) implies that y =y s max (y) nearest neighbors of label y. Further-t (y ) + s small t (y) ≥ K,
	meaning that we can choose the remaining K -s small t for other labels. In other words, we can find a replacement d where s small (y) neighbours so that they vote t (y) = s d t (y), proving that s min (y) = min d∈D s d t (y) in the first case. Case 2: s small t (y) < K-y =y s max t (y ) implies that s min t (y) = K-y =y s max t (y ).
	First note that for any replacement we cannot have s d t (y) < K -y =y s max t	(y ),
	otherwise the set of nearest neighbour would be necessarily lower than K. s min t	(y)
	then reaches this lower bound by simply taking the replacement d for which we have
	s d t (y ) = s max t	(y ), proving that s min t	(y) = min d∈D s d t (y) in the second case.
	Lemma 1. Given a number of nearest neighbours K, a target instance t, the corre-
	sponding maximum and minimum score vectors
	s min t	(y 1 ), . . . , s min t	(y M ) and s max t	(y 1 ), . . . , s max t	(y M ) ,
	then, for any y ∈ Y, we have that
		s min t	(y) = min d∈D	s d t (y) and s max t	(y) = max d∈D	s d t (y)	(2.26)
	and consequently, we have that, ∀d ∈ D,
				s max

t (y) ≥ s d t (y) ≥ s min t (y), ∀y ∈ Y. (2.27) Proof. The relation that s max t (y) = max d∈D s d t (y) can be simply proved by observing that Ky =y s small t (y )

Table 2 . 2 :

 22 Data sets used in the experiments

	T,

Table 2 .

 2

	3: Experimental Results: Accuracy of classifiers (%)

Table 2 . 4 :

 24 Weights and neighbours of Example 2

Table 2 . 5 :

 25 Effect scores obtained by using f M W in Example 2

	xn	t 1	t 2	t 3	t 4	t 5	T
	x 1	0.4 0.2	0	0	0	0.6
	x 2	0.3 0.4	0	0	0	0.7
	x 3	0.3 0.4	0	0	0	0.7
	x 4	0	0	0.4 0.3 0.4	1.1

the set of possible replacements of N t with cardinality |D t | =

	y	s cores	x 1	x 2	x 3	x 4	x 5
	y 1	s min s max	0 0.7 0.8 0	1.2 1.4 1.2 2 2.1 2
	y 2	s min s max	0 1.7 1.2 0.8 0.7 0.8 0 0 0 0
	y 3	s min s smax	0 2.4	0 2	0 0		0 0	0 0
								K k=1 |Y t k |. For a
	given replacement d t , the corresponding winner(s) of the voting procedure is (are)
					K
			y d t = arg max y∈Y	k=1	w t k 1 y t k =y
	with w t k the weight corresponding to the k-th neighbor. Let us note that the arg max
	can return multiple labels.
	The possible and necessary label sets of t (i.e., PL t and NL t defined in (2.13)-
	(2.14)) can be determined as follows:
		PL t = {y ∈ Y | ∃d t ∈ D t s.t y ∈ y d t }	(2.33)
			and
		NL t = {y ∈ Y | ∀d t ∈ D t , y ∈ y d t },	(2.34)
	which are nothing else but the set of possible and necessary winners in social choice
	theory [5, 52, 64]. By definition, we have NL t ⊆ PL t . Given a target instance t, we
	adopt the following definition of ambiguity.

Table 2 . 6 :

 26 Minimal and maximal scores for Example 2 Definition 1. A target instance t is called ambiguous if NL t = PL t .

Table 2 .

 2 6 provides the score bounds obtained for the different x n of Example 2. From the minimal and maximal scores, we can easily get NL t and an approximation (APL t ) of PL t , as indicated in the next proposition and definition. Proposition 1. Given target instance t, weight w t and nearest neighbour set N t , a label y ∈ NL t iff According to Table2.6, the sets obtained for Example 2 with K = 3 areNL t 3 = NL t 4 = NL t 5 = APL t 3 = APL t 4 = APL t 5 = {y 1 } and NL t 1 = NL t 2 = ∅ APL t 1 = APL t 2 = {y 1 , y 2 , y 3 },showing, as expected, that only t 1 , t 2 are ambiguous.

	all labels

  Lemma 2. Given t , w t and N t , y ∈ PL t if ∃ y = y s.t s min (y ) > s max (y).Thus APL t is an outer approximation of PL t . The next example shows that APL t can indeed be a strict superset of PL t . Consider the simple unweighted case whereK = 4, Y 1 = {y 1 , y 2 } and Y 2 = Y 3 = Y 4 = {y 2 , y 3 }. As we have s min ∈ Y, then APL t = {y 1 , y 2 , y 3 }, but PL t = {y 2 , y 3 } (indeed,y 1 can get only one vote, while the two others will receive at least two votes). Proposition 2. Given target instance t, weight w t and nearest neighbour set N t , the following properties hold A1 APL t ⊇ PL t A2 if NL t = ∅, then APL t = PL t . Proof. (A1): By definition of PL t and NL t , we have that PL t ⊇ NL t . Lemma 2 together with the definition of APL t tells us that all labels not in APL t are also not in PL t , hence APL t ⊇ PL t ⊇ NL t . with Example 4 showing that APL t can be a strict outer-approximation of PL t . (A2): We are going to show that if NL t = ∅, then APL t = PL t . Since (A1) ensures APL t ⊇ PL t , then (A2) will be proved by showing that if NL t = ∅, then APL t ⊆ PL t . Since NL

	Proof. If ∃ y = y s.t s min t	(y ) > s max t	(y), then for ∀d t , we have
	s d t (y ) ≥ s min (y ) > s max t	(y) ≥ s d t (y),
	or s d t (y ) > s d t (y), then y is not a possible label of t.
	Example 4. t	(y) = 0 and s max

t (y) > 0 for all labels y t = ∅, then ∃y ∈ NL t s.t s min s d t (y ) ≥ s max s d t (y) for y = y . From that, we can infer that if y ∈ APL t , then we have s min s d t (y ) = s max s d t (y) for any y ∈ NL t . This means that ∃d t s.t s d t

  Proposition 3. Given target instance t, nearest neighbour set N t , approximated possible label set APL t of t and weight w t , query q n cannot change APL t if the two following conditions hold B1 for any y ∈ APL t \ Y n , we have B2 and for any y ∈ APL t ∩ Y n , we have Proof. It is clear from the definition (2.33) that APL qn t ⊆ APL t . To show that APL qn t = APL t under conditions (B1) and (B2), we will show that (B1) and (B2) imply APL qn

		s max t	(y) ≥ max y ∈Yn	s min t	(y ) + w n .
	s max t	(y) -w n ≥ max	max y ∈Yn\{y}	s min t	(y ) + w n , max y ∈Y t \Yn	(s min t	(y ) .

t ⊇ APL t . To do so, we will show that if y ∈ APL t , and y satisfies (B1) and (B2), then y ∈ APL qn t . As (B1) and (B2) partition APL t in two disjoint sets (we have either y ∈ APL t \ Y n or y ∈ APL t ∩ Y n ), we can treat them separately. Also recall that if y ∈ APL t , then s max t (y) ≥ max y =y,y ∈Y t s min t (y ). (B1) Case y ∈ APL t \ Y n : once a query q n is done for x n , it can only increase the minimal score of one label (the true unknown one) by w n , hence the highest increase of a minimal score is max y ∈Yn s min,qn t (y ) = max y ∈Yn s min t (y ) + w n , meaning that if condition (B1) holds, we have s max,qn t (y) ≥ max y =y s min,qn t

  Proposition 5. Given target instance t, nearest neighbour set N t , necessary label set NL t and weight w t , then query q n cannot change NL t if the two following conditions hold D1 for any y ∈ NL t and y ∈ Y n , It is implied by the definition of NL t (2.34) that NL qn t ⊆ NL t , hence showing that under Conditions (D1) and (D2), NL qn t ⊇ NL t is sufficient to show the desired equality.

	s min t	(y) < max	max y =y,y ∈Y t \Yn	s max t	y ∈Yn (y ), max	s max
			y ∈Yn	s max t	y ∈Yn\{y} (y ), max	s max

t (y ) -w n , min y ∈Yn s max t (y ) , D2 for any y ∈ NL t and y ∈ Y n s min t (y) + w n < max max t (y ) -w n . Proof. Note that showing that NL qn t = NL t is equivalent to show that NL t = NL qn t , where NL t (NL qn t ) denotes the complement of NL t (NL qn t ).

Table 2 . 7 :

 27 Check for propositions for Example 2

Table 2 .

 2

8: Ambiguity effect for Example 2

Table 2 .

 2 Thus, we Chapter 2. Transductive learning and partial data

	Name	# instances # features # labels
	iris	150	4	3
	wine	178	13	3
	forest	198	27	4
	seeds	210	7	3
	glass	214	9	6
	ecoli	336	7	8
	libras	360	91	15
	dermatology	385	34	6
	vehicle	846	18	4
	vowel	990	10	11
	yeast	1484	8	12
	winequality	1599	11	6
	optdigits	1797	64	10
	segment	2300	19	7
	wall-following	5456	24	4

9: Data set used in the experiments

Table 2 .

 2

10: Complexities of query schemes

Table 2 .

 2

11: Average error rates % (average ranks) over the 15 data sets

  . . . , P , and precise target instances T = {(t t , ?)} T t=1 . For a label y m ∈ Y, the relations among scores (2.27) and the definition of the possible label set (2.13) imply that y m is a possible label (y m ∈ PL t ) if and only if there is a replacement d ∈ D with a score vector s d

	1 n , . . . , X P n ) and X p n = [a p n , b p n ],
	∀p = 1,

t (y 1 ), . . . , s d t (y M ) such that M i=1

  Proposition 6. Given the number of nearest neighbours K, a target instance t, its corresponding maximum and minimum score vectors s min ), for ∀y i ∈ Y \ {y m }, then y m is a possible label if and only if

	s max t	t (y m ) ≥ s min t (y i K ≤ s max (y 1 ), . . . , s min t (y 1 ), . . . , s max t (y M ) . Assuming that s max t M t (y m ) + min s max t (y m ), s max t (y i ) .	(y M ) and (2.47)
			i=1,i =m
	Proof. (⇒) Let us prove that y m being a possible label implies (2.47). First, if y m ∈
	PL t and d is a legitimate replacement, we have that
		w(y i ) ≤ min s max t	(y m ), s max t	(y i ) -s min t	(y i ), ∀i = m	(2.48)
	otherwise y m would not be a winner, or we would give a higher score to y i than it
	actually can get (we would have s d t (y i ) > s max t	(y i )). Since for any replacement we
	have that Eq. (2.45) must be satisfied, we have necessarily

  Proposition 7. Given the maximum and minimum scores s min

	and s max		t	(y 1 ), . . . , s min t	(y M )
	necessary. Let us consider the two cases
	1. K -j =m s max t	(y j ) ≥ s small t	(y m ), then for ∀j = m, we give its the maximum
	score s.t s d t (y j ) = s max
	Then it is clear that

t (y 1 ), . . . , s max t (y M ) , then a given label y m is a necessary label if and only if

s min t (y m ) ≥ s max t (y i ), ∀i = m. (

2

.49) Proof. (⇒) We proceed by contradiction. Assuming that ∃ y m ∈ NL t and ∃ y i ∈ Y where s min t (y m ) < s max t (y i ), we show that we can always find a replacement d ∈ D s.t s d t (y m ) < s d t (y i ), or in other words, ∃ d ∈ D s.t y m ∈ y d t , and therefore y m is not t (y j ) and give y m the score s d t (y m ) = Kj =m s max t (y j ).

  ) nearest neighbours from at most j ={m,i} s max t (y j ) possible nearest neigbours whose labels are not y m or Y n . In such a replacement we have s d t (y m ) < s d t (y i ).(⇐) We are going to prove that (2.49) implies that the label y m ∈ NL t is necessary.

	Let us first note that
	min d∈D	s d t (y m ) = s min t	(y m ) and max d∈D	s d t (y i ) = s max t	(y i ), ∀i = m,
	then (2.49) ensures that, for any replacement d ∈ D,

2. Kj =m s max t (y j ) < s small t (y m ), then we give y m a score s d t (y m ) = s small t (y m ) and give y i a score s d t (y i ) = s smax t (y i ). As we have K < j ={m,i} s max t (y j ) + s small t (y m ) + s max t (y m ) by assumption, we can choose K -s small t (y m ) -s smax t (y i

  θ S } ;

	Name	# instances # features
	parkinsons	197	22
	vertebral-column	310	6
	ionosphere	351	34
	climate-model	540	18
	breast-cancer	569	30
	blood-transfusion	784	4
	banknote-authentication	1372	4

Table 3 .

 3

1: Data set used in the experiments

  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 (3.4) (resp. (3.5)) implies that the computation of R(θ l | D) (resp. R(θ l | D))
	can be done by computing l

.41) Example 14. Let us now continue with the data set and the decision tree from Example 13. Assume that instances x 1 and x 2 are partially labelled with Y 1 = {a, c} and bound of a

Table 3 . 2 :

 32 Data set used in the experiments

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

  s 1 ln(θ 1 ) + s 0 ln(θ 0 ) +

			P
			s	p,tp 1	ln(θ	p,tp 1 ) + s p,tp 0	ln(θ	p,tp 0 ) .	(4.27)
			p=1
	with its maximum estimate θ *
		(θ 1 ) * , (θ 0 ) * = (θ p,tp 1 ) * , (θ p,tp 0 ) * = s 1 N	,	s 0 N s p,tp , 1 s 1	,	0 s 0 s p,tp	.	(4.28)
	Thus, the corresponding regularized log-likelihood estimate θ * are
	(θ	p,tp 1 ) r , (θ	p,tp 0 ) r = (1 -γ)		s s 1 p,tp 1	,	p,tp s 0

Table 4 . 1 :

 41 a, b ∈ {0, 1, . . . , 100}, a ≤ b , i.e., a quantization of the class of all probability intervals, according to the different measures, and then computed the Kendall rank correlation. While the ranking according to (4.54) is strongly correlated with the ranking for u e (Kendall is around 0.86), it is almost uncorrelated with u a . Data set used in the experiments

	#	name	# instances # features attributes
	1	parkinsons	197	22	real
	2	vertebral-column	310	6	real
	3	ionosphere	351	34	real
	4	climate-model	540	18	real
	5	breast-cancer	569	30	real
	6	blood-transfusion	748	5	real
	7 banknote-authentication	1372	4	real

  Average accuracies (y-axis) over 10 × 3-folds for Naive Bayes as a function of the number of examples queried from the pool (x-axis).

	0.84		0.78
	0.82		0.74
	0.79		0.71
	0.77		0.67
		7	14 21 28 35 42 49 56		0	12	24	36	48	60	72	84
			(a) parkinsons				(b) vertebral
			Conf				Insu
			EpAl				Stan
			Epis				Alea
				Credal
			(c) methods
	0 33 66 99	7 Figure 4.7: 0 14 21 28 35 42 49 56	0 6.5 13 19.5	0	12	24	36	48	60	72	84
			(a) parkinsons				(b) vertebral
			Conf				Insu
			EpAl				Stan
			Epis				Alea
				Credal
			(c) methods

Table 4 . 2 :

 42 Data sets used in the experiments

	#	name	# instances # features # labels
	a	iris	150	4	3
	b	wine	178	13	3
	c	forest	198	27	4
	d	seeds	210	7	3
	e	glass	214	9	6
	f	ecoli	336	7	8
	g	libras	360	91	15
	h	dermatology	385	34	6
	i	vehicle	846	18	4
	j	vowel	990	10	11
	k	yeast	1484	8	12
	l	wine quality	1599	11	6
	m	optdigits	1797	64	10
	n	segment	2300	19	7
	o wall-following	5456	24	4

Table 4 .

 4 102]. , 1) 90.45(1) 83.29(2) 86.71(2) 76.88(3) b 96.35(1, 1) 95.89(2) 93.18(2) 93.47(3) 88.92(3) c 89.76(2, 1) 92.15(1) 88.82(2) 88.49(3) 81.57(3) ) 71.07(1) 62.17(2) 68.92(2) 57.17(3) j 39.57(3, 2) 51.10(1) 42.57(1) 48.22(2) 37.27(3) k 49.35(3, 2) 60.60(2) 50.04(1) 60.84(1) 49.22(3) l 58.10(3, 3) 69.65(2) 59.92(1) 71.02(1) 59.16(2) m 96.37(3, 2) 97.67(1) 96.81(1) 96.85(2) 95.46(3) n 84.51(3, 3) 91.87(1) 89.16(1) 90.01(2) 85.49(2) o 68.69(3, 3) 76.42(2) 70.79(1) 77.34(1) 70.39(2) aver. (u 80 , u 65 )

		VOTE	PREORDER	NONDET
	#	acc.	u 80	u 65	u 80	u 65
	a 84.33(3d 88.81(3, 1) 92.15(1) 88.16(2) 90.03(2) 83.60(3)
	e	47.14(3, 3) 67.32(1) 57.24(1) 65.03(2) 52.98(2)
	f	75.57(3, 1) 80.66(1) 75.25(2) 77.02(2) 68.89(3)
	g	50.50(3, 3) 70.51(1) 63.91(1) 62.50(2) 53.02(2)
	h	96.43(2, 2) 97.70(1) 96.46(1) 96.01(3) 93.38(3)
	i	63.99(3, 1u 80	u 65	u 80	u 65
	rank (2.73, 1.93)	1.27	1.40	2.00	2.67

3: Average utility-discounted accuracies (%)

In this thesis, all experiments will be performed on data sets from the UCI repository http: //archive.ics.uci.edu/ml/index.php

In addition to those possible xn for which θ k (xn) = yn and θ l (xn) = yn.

The adopted formulation allows us to better shows the similarities with the SVM case.

Technically, we assume that, for each t ∈ X , there are hypotheses θ, θ ∈ Θ such that θ(t) ≥ 0.5 and θ (t) ≤ 0.5, which implies π(1 | t) ≥ 0 and π(0 | t) ≥ 0.

For an implementation in Python, see https://docs.scipy.org/doc/scipy-0.19.1/ reference/generated/scipy.optimize.minimize_scalar.html

For an implementation in Python, see https://docs.scipy.org/doc/scipy/reference/ generated/scipy.optimize.minimize.html

The class priors are ignored here.

The score s is not well scaled, and may assume very large negative values. For better visibility, we therefore plotted the monotone transformation exp(s).

For better comparison, we use the measures in a pure form, that is, without using the high uncertainty criterion as a pre-filter. Thus, we seek to avoid mixing the effect of their measures with standard entropy.

Acknowledgements

This work has been funded by the University of Technology of Compiègne (UTC).

My first thanks go to my two supervisors, Dr. Sébastien destercke and Assoc. Prof. Marie-Hélène

To my parents

Chapter 3. Racing Algorithms Proposition 15. Given (X n , y n ) with X p n = [a p n , b p n ] and two models θ k and θ l s.t (X n , y n ) is imprecise w.r.t both of the given models, then J q p n (θ k , θ l ) = 1 if the following conditions hold if k-l (y n , X n ) = -1 and y n = 1:

if k-l (y n , X n ) = -1 and y n = -1:

if k-l (y n , X n ) = 0 and θ k-l (X n ) < 0:

if k-l (y n , X n ) = 0 and θ k-l (X n ) > 0:

Proof. Let us first investigate the case where k-l (y n , X n ) = -1 and y n = 1 (the case k-l (y n , X n ) = -1 and y n = -1 is similar). In this case, J q p n (θ k , θ l ) = 1 if and only if q p n can either increase k (y n , X n ) = 0 or decrease l (y n , X n ) = 1, that is become precise for at least one of them, with k (y n , X q p n n ) = 1 or l (y n , X q p n n ) = 0. The conditions are then obtained by following arguments similar to those of Proposition 10.

The second case k-l (y n , X n ) = 0 only happens when either θ k-l (X n ) < 0 or θ k-l (X n ) > 0, and we will treat the first case. According to Proposition 14, this means that y n = -1. Also, since according to Proposition 11 the value 0 is an upper bound of k-l (y n , X n ) when X n is imprecise with either θ k or θ l , to go from k-l (y n , X n ) = 0 to k-l (y n , X q p n n ) = 1, we need a value x p n ∈ X p n such that θ k (X q p n n ) < 0 and θ l (X q p n n ) > 0, as y n = -1. Again, we can get the conditions to have such a value by deriving arguments similar to those of Proposition 10.

For instance, in Figure 3.3(a) and 3.3(b), J q 1 n (θ 2 , θ 1 ) = 0 and J q 2 n (θ 2 , θ 1 ) = 1 for both cases. The whole procedure is summed up in Algorithm 2. Algorithm 3 summarizes how to determine the query effect q p n , which can be considered as the main computational difficulty when performing the querying step (line 2-3 in Algorithm 2). Determining the set of undominated models (line 6 -8 in Algorithm 2) is summarized in Algorithm 4.

Let us now study the complexity of the whole approach. Lines 2 and 4 of Algorithm 3 are in O(P ), since they correspond to linear operations. Iterations from 5 -10 are in O(S × P ), since we must check all undominated models once. Iterations from 13 -15 are also in O(S × P ), for the same reason. Thus, one run of Algorithm 3 is in O(S × P ). If we have I partial features in the data, then loop 2 -3 of Algorithm 2 takes O(I × S × P ) in the case of SVM, so it remains linear in each of the parameter. Algorithm 4 corresponds to lines 6-8 of Algorithm 2, and computing R(θ k-l ) can be done in O(N × P ) since we must compute for each data point. Finally, since this must be done for every pair of models in the worst case, performing Algorithm 4 is in O(S 2 × N × P ), which is quadratic in S and linear in the other parameters. This can be approximated by only comparing intervals [R(θ k ), R(θ k )] of every models, that would bring down the complexity to O(S × N × P ), but would provide a super-set of the set of undominated models.

Algorithm 3: Determining the query effect V alue(q p n ) Input: partial data (X n , y n ), set Θ = {θ 1 , . . . , θ S } of models, the best potential model θ k * Output: the query effect V alue(q p n )

Let us note that the detail computations in this case is quite similar to the case of SVM, as highlighted in the Section 3.3.4. 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 θ l , the lower and upper losses in (3.40) and (3.41) can be determined as follows:

Given a decision tree θ l , we will say that an instance is imprecise w.r.t.

The next proposition characterizes simple conditions under which an instance is imprecise w.r.t. θ l .

Proposition 18. Given a model θ l and instance

(3.45)

Proof. Let us first note that by definitions we always have

Then combining with condition (3.44) the lower and upper losses of an imprecise instance can be determined explicitly by

and both lower and upper losses will be 0).

Proposition 18 simply translates the fact that imprecision can happen only if a partial label could contain the prediction of θ l . Using Proposition 18, we can conclude that in Example 14, instance x 1 is imprecise w.r.t. model θ l 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 Θ of models and the effect of querying partial labels on those risks. It is easy to see that the empirical risk

Algorithm 9: Determine the best model θ k * and the undominated model set

Algorithm 10: Determine the effect value of a query V alue(q n ).

Input: (3.55). Otherwise, the corresponding loss is precise and such an instance can be discarded from the querying process. For example, in Figure 3.9, we can see that l (y 1 , X 1 ), l (y 1 , X 1 ) = [0, 0] while l (y 2 , X 2 ), l (y 2 , 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

with H the number of terminal nodes of the decision tree θ l . Note that K can easily be built using (3.53), and that B, C have to be built only once. A given training instance X n is imprecise w.r.t. θ l 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 l (y n , 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 (θ l ) = 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

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 non-empty intersection with A h becomes empty. Furthermore, (3.53) 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 Algorithms Algorithm 12 summarizes how to determine the optimal query for a single querying step in case of imprecise features. It is very similar to Algorithm 7, but takes different sub-routines specific to the case of partially known features.

Algorithm 13 summarises how risk bounds, from which can be deduced the best potential model (through Algorithm 9, that remains unchanged), can be computed. Algorithms 14 and 15 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 15 computes the sum of the pairwise effects between the best potential model θ k * and the other ones. Let us now look at the complexity of Algorithm 13, 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 (3.53). Lines 2-3 are in O(S ×N ×H ×P ), since Algorithm 13 is in O(N ×H ×P ), as computing vector K (line 3 of Algorithm 13) is in O(H × P ). Algorithm 9 remains in O(S). Lines 4-9 of Algorithm 13 is in O(N × S × P × H 4 ): indeed, in Algorithm 15, lines 7-9 are in O(P × H 4 ), as we must apply Algorithm 11 to at most H 2 intervals.

In particular, Algorithm 15 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 θ k * , Line 4 whether it is imprecise w.r.t θ k . So Lines 4-9 corresponding to imprecision with respect to both models, lines 10-13 to imprecision w.r.t only θ k * , and lines 15-19 w.r.t only θ k . 3 Determine the best model θ k * and the undominated model set Θ * using Alg. 9; 4 foreach n = 1, . . . , N do 5 Determine (E q 1 n (θ k * ), . . . , E q P n (θ k * )) using Alg. 14 with model θ k * ;

6 Determine the cumulative pairwise effects (J q 1 n , . . . , J q P n ) using Alg. 15;

9 Determine (n * , p * ) = arg max (n,p) V alue(q p n );

Compute K, B yn and C yn using (3.56)-(3.58);

Algorithm 14: Determine the single effects (E q 1 n (θ l ), . . . , E q P n (θ l )). Input: Training instance (X n , y n ), a model θ l . Output: The single effects (E q 1 n (θ l ), . . . , E q P n (θ l ))

Algorithm 15: Determine the cumulative pairwise effects (J q 1 n , . . . , J q P n ). (3.67); if min W k,k * < 1 then foreach p = 1, . . . , P and X p n > 0 do

In ← Alg. 11 with inputs X p n , {A p i,j : w k,k * i,j = min W k,k * };

if In = 1 then J q p n = J q p n + 1;

Estimation for Naive Bayes

Let us first remind that we have been working on a training data set D = {(x n , y n )} N n=1 , where x n = (x 1 n , . . . , x P n ) s.t x p n ∈ X p = {a p 1 , . . . , a p Tp }, for p = 1, . . . , P . For each feature X p , denoting by

we then have that Furthermore, denoting by θ 1 := p θ (Y = 1) and θ 0 := p θ (Y = 0), we have that The underlying hypothesis space Θ ⊆ R f , where f = 2 P p=1 T p + 2, and its individual θ can be rewritten as follows:

Active learning

In this proposal, we advocate a distinction between two different types of uncertainty, referred to as epistemic and aleatoric, in the context of active learning. We conjecture that, in uncertainty sampling, the usefulness of an instance is better reflected by its epistemic than by its aleatoric uncertainty. This leads us to suggest the principle of epistemic uncertainty sampling, which we instantiate by means of a concrete approach for measuring epistemic and aleatoric uncertainty.

Related methods

In this section, we recall the setting of uncertainty sampling and present two recent approaches that are related to our work in that they also distinguish different sources of uncertainty.

Uncertainty sampling

As usual in active learning, we assume to be given a labelled set of training data D = {(x n , y n )} N n=1 and a pool of unlabeled instances U = {(t t , ?)} T t=1 that can be queried by the learner. Instances are represented as features vectors x n = x 1 n , . . . , x P n ∈ X = R P . In this proposal, we only consider the case of binary classification, where labels y n are taken from Y = {0, 1}, leaving the more general case of multi-class classification for future work.

In uncertainty sampling, instances are queried in a greedy fashion. Given the current model θ that has been trained on D, each instance t in the current pool U is assigned a utility score s(θ, t), and the next instance to be queried is the one with the highest score [START_REF] Lewis | A Sequential Algorithm for Training Text Classifiers[END_REF][START_REF] Settles | Active Learning Literature Survey[END_REF][START_REF] Settles | An Analysis of Active Learning Strategies for Sequence Labeling Tasks[END_REF][START_REF] Sharma | Evidence-based Uncertainty Sampling for Active Learning[END_REF]. The chosen instance is labelled (by an oracle or expert) and added to the training data D, on which the model is then re-trained. The active learning process for a given budget B (i.e, the number of unlabelled instances to be queried) is summarized in Algorithm 18.