Traditional machine learning models provide a single-class prediction for a given input instance. This may be inadequate in some scenarios, especially when the cost of erroneous predictions is high. Cautious random forests are cautious classification models that may output sets of possible classes as predictions when uncertainty is high, thus reducing the risk of making incorrect decisions. However, making such indeterminate predictions carries a cost, as resolving indeterminacy typically necessitates further analysis and manual intervention. This work focuses on explaining why an indeterminate prediction has been made and how indeterminacy can be resolved. To this end, we use counterfactual examples associated with determinate predictions. We propose a branch-and-bound algorithm that can efficiently generate proximal, plausible, and actionable counterfactual examples. Several experimental results are presented to demonstrate the advantages of our proposed method.

International audience

Occupancy grids are common tools used in robotics to represent the robot environment, and that may be used to plan trajectories, select additional measurements to acquire, etc. However, deriving information about those occupancy grids from sensor measurements often induce a lot of uncertainty, especially for grid elements that correspond to occluded or far away area from the robot. This means that occupancy information may be quite uncertain and imprecise at some places, while being very accurate at others. Modelling finely this occupancy information is essential to decide the optimal action the robot should take, but a refined modelling of uncertainty often implies a higher computational cost, a prohibitive feature for real-time applications. In this paper, we introduce the notion of credal occupancy grids, using the very general theory of imprecise probabilities to model occupancy uncertainty. We also show how one can perform efficient, real-time inferences with such a model, and show a use-case applying the model to an autonomous vehicle trajectory planning problem.

We propose a method for reliable prediction in multi-class classification, where 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 a recent proposal for modeling uncertainty in classification, in which a distinction is 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. Experimentally, we show that our method is able to appropriately balance reliability and precision of predictions.

Indeterminate classifiers are cautious models able to predict more than one class in case of high uncertainty. A problem that arises when using such classifiers is how to evaluate their performances. This problem has already been considered in the case where all prediction errors have equivalent costs (that we will refer as the "0/1 costs" or accuracy setting). The purpose of this paper is to study the case of generic cost functions. We provide some properties that the costs of indeterminate predictions could or should follow, and review existing proposals in the light of those properties. This allows us to propose a general formula fitting our properties that can be used to produce and evaluate indeterminate predictions. Some experiments on the cost-sensitive problem of ordinal regression illustrate the behavior of the proposed evaluation criterion.

Binary decomposition techniques transform a multi-class problem into several simpler binary problems. In such techniques, a classical issue is to ensure the consistency between the binary assessments of conditional probabilities. Nested dichotomies, which consider tree-shaped decomposition, do not suffer from this issue. Yet, a wrong probability estimate in the tree can strongly biase the results and provide wrong predictions. To overcome this issue, we consider in this paper imprecise nested dichotomies, in which binary probabilities become imprecise. We show in experiments that the approach has many advantages: it provides cautious inferences when only little information is available, and allows to make efficient computations with imprecise probabilities even when considering generic cost functions.

Fuzzy or hard partitioning methods aim at grouping objects according to their similarity. Recently, a new concept of partition based on belief function theory, called credal partition, has been proposed and has been shown to generate meaningful description of the data. Hard, fuzzy or credal partitions are generally obtained using unsupervised learning methods, using only the numeric description between two objects to compute their similarity. However, in some applications, some kind of background knowledge about the objects or about the clusters is available. To integrate this auxiliary information, constraint-based (or semi-supervised) methods have been proposed. A popular type of constraints specifies whether two objects are in the same cluster (must-link) or in different clusters (cannot-link). We propose here a new algorithm, called CECM, which computes a credal partition using a constrained clustering method. We show how to translate the available information into constraints, and how to integrate them in the search of the credal partition. The paper ends with some experimental results. Results of CECM are compared to other constrained clustering algorithms. Then an application in image segmentation is described.

Knowledge of traffic demand at a junction is crucial for most transport systems. Generally, it is represented by an origin-destination (OD) matrix, where each element is a volume of vehicle flow between one of the OD pair of zones of a junction. This paper introduces a new method for a short-time estimation of OD matrices at a signalised junction with a complex structure and fitted out with video cameras. The estimation is made by taking into account the traffic lights and by fusion of different multisensor traffic data, which are subject to imprecision and uncertainty. The method proceeds in two steps. First, vehicle conservation law, expressed in terms of undertermined system of equations, is built dynamically for a short-time period. Second, four approaches, that overcome the system indetermination and model the data imperfection, are proposed to provide the best and unique estimates of the OD matrix. An experimental study has been made with data collected at the real signalised junction.

The discounting operation is a well known operation on belief functions, which has proved to be useful in many applications. However, the discounting operation only allows one to weaken a source, whereas it is sometimes useful to strengthen it when it is deemed to be too cautious. For that purpose, the de-discounting operation was introduced as the inverse operation of the discounting operation by Denoeux and Smets. From another point of view, Zhu and Basir introduced an extension of the classical discounting operation by allowing the discount rate to be out of the range [0,1]. This operation performs a discounting or a de-discounting of a belief function. A new interpretation of this scheme is presented in this paper. A more general form of reinforcement process, as well as a parameterized family of transformations encompassing all previous schemes, are also introduced

This paper describes an extension of principal component analysis (PCA) allowing the extraction of a limited number of relevant features from high-dimensional fuzzy data. Our approach exploits the ability of linear autoassociative neural networks to perform information compression in just the same way as PCA, without explicit matrix diagonalization. Fuzzy input values are propagated through the network using fuzzy arithmetics, and the weights are adjusted to minimize a suitable error criterion, the inputs being taken as target outputs. The concept of correlation coefficient is extended to fuzzy numbers, allowing the interpretation of the new features in terms of the original variables. Experiments with artificial and real sensory evaluation data demonstrate the ability of our method to provide concise representations of complex fuzzy data.

A new relational clustering method is introduced, based on the Dempster-Shafer theory of belief functions (or evidence theory). Given a matrix of dissimilarities between n objects, this method, referred to as evidential clustering (EVCLUS), assigns a basic belief assignment (or mass function) to each object in such a way that the degree of conflict between the masses given to any two objects reflects their dissimilarity. A notion of credal partition is introduced, which subsumes those of hard, fuzzy, and possibilistic partitions, allowing to gain deeper insight into the structure of the data. Experiments with several sets of real data demonstrate the good performances of the proposed method as compared with several state-of-the-art relational clustering techniques.

A new method is proposed in order to reconstruct the geometrical configuration of a large points set using minimal information. The paper develops algorithms based on graph and kinematics theories to determine the minimum number of distances, needed to uniquely represent n points in d-dimensional Euclidean space. Therefore, it is found that this theoretical minimum is d(n-2)+1 interpoint distances. The method is evaluated, on the basis of basic parameters, by means of Monte Carlo simulation using genetic algorithms for better optimization procedures. This evaluation takes into account the real case where the metric informations are interpoint dissimilarities instead of exact Euclidean distances. Two applications on real data successfully illustrate the efficiency of the method. Finally, on the basis of Monte Carlo results, the authors provide some practical recommendations to experimenters who wish to use the method in order to scale a many-objects set.