Search

International audience

In this paper, we investigate the computational intelligibility of Boolean classifiers, characterized by their ability to answer XAI queries in polynomial time. The classifiers under consideration are decision trees, DNF formulae, decision lists, decision rules, tree ensembles, and Boolean neural nets. Using 9 XAI queries, including both explanation queries and verification queries, we show the existence of large intelligibility gap between the families of classifiers. On the one hand, all the 9 XAI queries are tractable for decision trees. On the other hand, none of them is tractable for DNF formulae, decision lists, random forests, boosted decision trees, Boolean multilayer perceptrons, and binarized neural networks.

Statistical computational learning is the branch of Machine Learning that defines and analyzes the performance of learning algorithms using two metrics: sample complexity and runtime complexity. This chapter is a short introduction to this important area of research, geared toward the reader interested in developing learning algorithms for AI models. We first provide the formal background about statistical learning problems, captured by three basic ingredients: tasks, models and loss functions. We next examine the PAC learning framework and its generalizations, used to capture the concepts of statistical learnability and computational (or efficient) learnability. Based on this framework, the conditions of statistical learnability are investigated through the properties of uniform convergence and algorithmic stability. We also survey several theoretical results and algorithms in the topics of concept learning and convex learning, which take a central place in statistical computational learning. We then conclude this survey with some trends and open questions in learning AI models, by mainly focusing on sparse models, probabilistic models, preference models and deep neural models.

International audience; Constraint programming is used to model and solve complex combina- torial problems. The modeling task requires some expertise in constraint programming. This requirement is a bottleneck to the broader uptake of constraint technology. Several approaches have been proposed to assist the non-expert user in the modelling task. This paper presents the basic architecture for acquiring constraint networks from examples classified by the user. The theoretical questions raised by constraint acquisition are stated and their complexity is given. We then propose Conacq, a sys- tem that uses a concise representation of the learner’s version space into a clausal formula. Based on this logical representation, our architecture uses strategies for eliciting constraint networks in both the passive acquisition context, where the learner is only provided a pool of examples, and the active acquisition context, where the learner is allowed to ask membership queries to the user. The computational properties of our strategies are analyzed and their practical effectiveness is experimentally evaluated.

International audience; L'automatisation de la configuration des solveurs a reçu une grande attention ces dernières années notam-ment pour la capacité à ajuster ses différents paramètres selon l'instance à résoudre. De plus, cette automatisation évite à l'utilisateur le choix d'une configuration appropriée à chaque instance et ainsi, évite une tâche requérant des qualités d'expert et rend plus accessible les outils de la programmation par contraintes. Les techniques basées sur les portfolios ont été grandement étudiées dans le but de configurer les solveurs de contraintes. Son principe est d'entraîner le solveur à résoudre plusieurs instances afin de trouver la meilleure configuration lors de la résolution d'une instance inconnue. Dans cette étude, nous portons notre attention sur le choix de la meilleure stratégie de recherche, à savoir la meilleure heuristique de choix de variables. Nous proposons une structure algorithmique générique qui optimise la sélection des différentes heu-ristiques de choix de variables grâce à l'apprentissage en ligne, c'est-à-dire sans aucune connaissance apriori. Dans ce but, nous utilisons une technique en apprentissage, appelée les bandits multi-bras, permettant d'automatiser la sélection de l'heuristique la plus appropriée et guidant au mieux la recherche. Nous essayons deux politiques différentes basées sur les bandits multi-bras gérant la proportion d'exploration-exploitation. Une évaluation ex-périmentale démontre que la machine proposée résulte en un solveur plus efficace et stable. Abstract Automating solver's configuration has received a great attention last years as it can adjust the various parameters of a solver to the instance to be solved. In addition, this automation releases the user from choosing the suitable configuration each time, task that requires a great expertise and thus, burdens the widespread of * Papier doctorant : Hugues Wattez 1,2 est auteur principal. constraint programming technology and tools. Portfolio based techniques have been vastly used to configure constraint solvers. The principle of portfolios is to train themselves by solving many instances in advance , in order to find the right combination of parameters of the solver when solving an unknown instance. In this work, we turn our attention to the selection of the best search strategy, namely the best variable ordering. We propose a generic algorithmic framework that selects among several variable ordering heuristics using on-line learning, i.e. without any prior knowledge. For this purpose, we deploy a machine learning technique, called multi-armed bandits, that allows to automatically select the appropriate heuris-tic to guide the search. We tried two different policies for multi-armed bandits that manage the proportion of exploration-exploitation. We make a thorough experimental evaluation that demonstrates that the proposed framework results in a more efficient and stable solver.

The overall goal of online feature selection is to iteratively select, from high-dimensional streaming data, a small, “budgeted” number of features for constructing accurate predictors. In this paper, we address the online feature selection problem using novel truncation techniques for two online sub-gradient methods: Adaptive Regularized Dual Averaging (ARDA) and Adaptive Mirror Descent (AMD). The corresponding truncation-based algorithms are called B-ARDA and B-AMD, respectively. The key aspect of our truncation techniques is to take into account the magnitude of feature values in the current predictor, together with their frequency in the history of predictions. A detailed regret analysis for both algorithms is provided. Experiments on six high-dimensional datasets indicate that both B-ARDA and B-AMD outperform two advanced online feature selection algorithms, OFS and SOFS, especially when the number of selected features is small. Compared to sparse online learning algorithms that use \(\ell _1\) regularization, B-ARDA is superior to \(\ell _1\)-ARDA, and B-AMD is superior to Ada-Fobos. Code related to this paper is available at: https://github.com/LUCKY-ting/online-feature-selection.

In this paper, we investigate the problem of sparse online linear classification in changing environments. We first analyze the tracking performance of standard online linear classifiers, which use gradient descent for minimizing the regularized hinge loss. The derived shifting bounds highlight the importance of choosing appropriate step sizes in the presence of concept drifts. Notably, we show that a better adaptability to concept drifts can be achieved using constant step sizes rather than the state-of-the-art decreasing step sizes. Based on these observations, we then propose a novel sparse approximated linear classifier, called sparse approximated linear classification (SALC), which uses a constant step size. In essence, SALC simply rounds small weights to zero for achieving sparsity and controls the truncation error in a principled way for achieving a low tracking regret. The degree of sparsity obtained by SALC is continuous and can be controlled by a parameter which captures the tradeoff between the sparsity of the model and the regret performance of the algorithm. Experiments on nine stationary data sets show that SALC is superior to the state-of-the-art sparse online learning algorithms, especially when the solution is required to be sparse; on seven groups of nonstationary data sets with various total shifting amounts, SALC also presents a good ability to track drifts. When wrapped with a drift detector, SALC achieves a remarkable tracking performance regardless of the total shifting amount.

Symmetry detection is a promising approach for reducing the search tree of games. In General Game Playing (GGP), where any game is compactly represented by a set of rules in the Game Description Language (GDL), the state-of-the-art methods for symmetry detection rely on a rule graph associated with the GDL description of the game. Though such rule-based symmetry detection methods can be applied to various tree search algorithms, they cover only a limited number of symmetries which are apparent in the GDL description. In this paper, we develop an alternative approach to symmetry detection in stochastic games that exploits constraint programming techniques. The minimax optimization problem in a GDL game is cast as a stochastic constraint satisfaction problem (SCSP), which can be viewed as a sequence of one-stage SCSPs. Minimax symmetries are inferred according to themicrostructure complement of these one-stage constraint networks. Based on a theoretical analysis of this approach, we experimentally show on various games that the recent stochastic constraint solver MAC-UCB, coupled with constraint-based symmetry detection, significantly outperforms the standard Monte Carlo Tree Search algorithms, coupled with rule-based symmetry detection. This constraint-driven approach is also validated by the excellent results obtained by our player during the last GGP competition.

The challenge of General Game Playing (GGP) is to devise game playing programs that take as input the rules of any strategic game, described in the Game Description Language (GDL), and that effectively play without human intervention. The aim of this paper is to address the GGP challenge by casting GDL games (potentially with chance events) into the Stochastic Constraint Satisfaction Problem (SCSP). The stochastic constraint network of a game is decomposed into a sequence of µSCSPs (also know as one-stage SCSP), each associated with a game round. Winning strategies are searched by coupling the MAC (Maintaining Arc Consistency) algorithm, used to solve each µSCSP in turn, together with the UCB (Upper Confidence Bound) policy for approximating the values of those strategies obtained by the last µSCSP in the sequence. Extensive experiments conducted on various GDL games with different deliberation times per round, demonstrate that the MAC-UCB algorithm significantly outperforms the state-of-the-art UCT (Upper Confidence bounds for Trees) algorithm.

National audience