Workshop on Machine Learning, Interpretability, and Logic

Logistics

• Date: Monday-Friday, April 10-14
  
• In-person Location:

• Registration: Click here to register

Titles and Abstracts

Speaker: Gilles Audemard

Title: Computing explanations for tree-based classifiers

Abstract: ML classifiers based on trees (Decision Trees, Random Forests or Boosted Trees) are powerful models for classification, especially when dealing with tabular data. Explaining the predictions made by such classifiers
is an important issue that has stimulated much research in AI for the past couple of years. In this talk, several types of local explanations suited to tree-based classifiers are considered. We propose efficient algorithms to compute abductive explanations (the “why” question) and contrastive ones (the “why not” question). We also show how to take user preferences into account when computing explanations.

Speaker: Shai Ben-David

Title: IA short introduction to IML and using logic for impossibility results in ML

Abstract: TBA

Speaker: Sebastian Bordt

Title: Explanations and Regulation

Abstract: Recent years have seen an increasing amount of debate around the question whether and how the usage of machine learning systems should be regulated. These debates are especially relevant for interpretable machine learning. The reason for this is that obligations to provide information about algorithms and their functioning are frequently interpreted as obligations to “explain”. In this talk, I first outline the basic case for regulating the usage of machine learning systems. This includes discussing a number of historical examples and a short dive into economic theory. I then consider the particular case of the European Union’s Artificial Intelligence Act and the usage of post-hoc explanation algorithms. It will be seen that these algorithms are unsuitable to achieve the transparency objectives that are inherent in the law. The reason for this is the high degree of ambiguity of post-hoc explanations in realistic application scenarios. I close the talk with some general remarks on explainable machine learning and regulation that will hopefully lead to lively debate. The second part of the talk is based on our ACM FAccT’22 paper: https://dl.acm.org/doi/abs/10.1145/3531146.3533153

Speaker: Simina Brânzei

Title: Online Learning in Multi-unit Auctions for Carbon.

Abstract: In a carbon auction, licenses for CO2 emissions are allocated among multiple interested players. Inspired by this setting, we consider repeated multi-unit auctions with uniform pricing, which are widely used in practice. In each round, m identical units of a good are sold to a group of buyers that have valuations with diminishing marginal returns. The buyers submit bids for the units, and then a price p is set per unit. We consider two variants of the auction, where the price is set to the mth highest bid and m+1st highest bid, respectively. Both of these rules represent the Walrasian mechanism, where the mth highest bid represents the maximum Walrasian price, while the m+1-st highest bid represents the minimum Walrasian price. We analyze the bidding strategies and properties of these auctions in both the offline and online settings.

Speaker: Rich Caruana

Title: Friends Don’t Let Friends Deploy Black-Box Models: The Importance of Intelligibility in Machine Learning

Abstract: In machine learning often tradeoffs must be made between accuracy and intelligibility: the most accurate models usually are not very intelligible, and the most intelligible models usually are less accurate.  This can limit the accuracy of models that can safely be deployed in mission-critical applications such as healthcare where being able to understand, validate, edit, and trust models is important.  EBMs (Explainable Boosting Machines) are a learning method based on generalized additive models (GAMs) that are as accurate as full complexity black-box models, even more intelligible than linear models, and which can be made differentially private with surprisingly little loss in accuracy.  EBMs make it easy to understand what a model has learned and to edit the model when it learns inappropriate things.  In the talk I’ll present several case studies where EBMs discover surprising patterns in data that would have made deploying black-box models risky.

Speaker: Lee Cohen

Title: Finding Safe Zones of Markov Decision Processes Policies

Abstract: Markov models are among the first go-to models for dynamic systems and reinforcement learning. When learning Markov models from data, a common goal is to learn the whole model. We present the problem of learning a SafeZone: The smallest subset of states that most trajectories do not escape from, even by a single state. Other than safe reinforcement learning, the problem has applications in anomaly detection, imitation learning, and explainability. We first show that the SafeZone problem is computationally hard. On the positive side, we prove a bi-criteria polynomial approximation algorithm that returns an almost 2 approximation set, where the approximation is in terms of both the escape probability and SafeZone size, with high probability. This is joint work with Yishay Mansour and Michal Moshkovitz.

Speaker: Zachary Lipton

Title: Responsible ML’s Causal Turn

Abstract: With widespread excitement about the capability of machine learning systems, this technology has been instrumented to influence an ever-greater sphere of societal systems, often in contexts where what is expected of the systems goes far beyond the narrow tasks on which their performance was certified. Areas where our requirements of systems exceed their capabilities include (i) robustness and adaptivity to changes in the environment, (ii) compliance with notions of justice and non-discrimination, and (iii) providing actionable insights to decision-makers and decision subjects. In all cases, research has been stymied by confusion over how to conceptualize the critical problems in technical terms. And in each area, causality has emerged as a language for expressing our concerns, offering a philosophically coherent formulation of our problems but exposing new obstacles, such as an increasing reliance on stylized models and a sensitivity to assumptions that are unverifiable and (likely) unmet. This talk will introduce a few recent works, providing vignettes of reliable ML’s causal turn in the areas of distribution shift, fairness, and transparency research.

Speaker: Gyorgy Turan

Title: Machine learning interpretability and knowledge representation

Abstract: Explainability in scientific, engineering and other similar machine learning application areas differs from societal applications in that the required kind of explanation can be more clearly specified by the context or the user. Developing XAI techniques for such applications is related to knowledge representation, a classical topic in AI, which aims at finding frameworks to represent knowledge with certain expressivity and reasoning requirements. We discuss ongoing work related to these issues on using explanations to enhance the learning capabilities of graph neural networks, and on interpreting deep-learned error-correcting codes. We also mention some background and motivation from the philosophy of science. Joint work with Natasha Devroye, Tamas Horvath, Neshat Mohammadi, Abhijeet Mulgund, Harish Naik, Raj Shekhar, Yeqi Wei, Milos Zefran and Yingyao Zhou.

Speaker: Guy Van den Broeck

Title: AI can learn from data. But can it learn to reason?

Abstract: Many expect that AI will go from powering chatbots to providing mental health services. That it will go from advertisement to deciding who is given bail. The expectation is that AI will solve society’s problems by simply being more intelligent than we are. Implicit in this bullish perspective is the assumption that AI will naturally learn to reason from data: that it can form trains of thought that “make sense”, similar to how a mental health professional or judge might reason about a case, or more formally, how a mathematician might prove a theorem. This talk will investigate the question whether this behavior can be learned from data, and how we can design the next generation of AI techniques that can achieve such capabilities, focusing on neuro-symbolic learning and tractable deep generative models.

Student Presenter: Gregoire Fournier

Title: Finite model theory and logics for AI

Abstract: Recent advances in AI have raised concerns about its black-box nature and lack of explainability. We follow a line of research that aims at characterizing AI through a finite model theoretic point of view. In particular, we study the graph neural network architecture (GNN), its proximity with the Weisfeiler-Lehman (WL) family of algorithms, and graded modal logic. We introduce an Ehrenfeucht–Fraïssé (EF) game and a semantic suitable to capture first order logic with counting, and apply it to linear orders.

Student Presenter: Anmol Kabra

Title: Reasonable modeling assumptions for real-world principal-agent games

Abstract: Machine learning systems in decision-making often induce unintended strategic behavior in participants (agents), who can modify their features to gain more favorable scores from the systems. In strategic classification, the principal would want to create systems that are robust to strategic modifications, whereas in incentive design, the principal would specify incentives to persuade agents to attain desired results. Both settings can be modeled as principal-agent games, which are special Stackelberg games. We formulate regulator-hospital dynamics in the US healthcare system as multi-objective principal-agent games, and study feasibility conditions. Along the way, we review the various modeling assumptions in (repeated) Stackelberg games literature, and comment on their applicability in real-world game dynamics.

Student Presenter: Omid Halimi Milani

Title: Predicting Incident Hypertension in Obstructive Sleep Apnea Using Machine Learning

Abstract: This study examines the relationship between the development of hypertension and obstructive sleep apnea (OSA), which is not easy to predict. We propose using machine learning to create a model that can predict the prevalence of hypertension up to five years after an OSA diagnosis. The sample consisted of 2,652 participants from the Sleep Heart Health Study (SHHS) cohort who did not have pre-existing hypertension at baseline. Out of these participants, 1,814 had follow-up data available after 5 years, and half of them had developed incident hypertension. The study analyzed various features extracted from polysomnography data, including heart rate variability and electroencephalography delta power, as well as clinical data. The features are calculated after removing artifacts detected and removed from the signals. The proposed model consists of parallel SVM models all of which runs on a different set of preprocessed and filtered features. At top of each SVM, a rule is trained to predict the labels. All predicted labels are fed into a fusion model that has been trained to make a decision about the final predicted label. The study found that the SVM model had a test accuracy of 70.05%, a sensitivity of 78.48%, and a specificity of 35.59%. The results suggest that supervised machine learning models may be useful for predicting high blood pressure associated with OSA.

Student Presenter: Kavya Ravichandran

Title: A Simple Image Model for Combinatorial Dictionary Learning and Inference.

Abstract: We are often interested in decomposing complex, structured data into simple components that explain the data. The linear version of this problem is well-studied as dictionary learning and factor analysis. In this work, we propose a combinatorial model in which to study this question and related questions of robustness. First, we identify a property we call “well-structuredness” of a set of low-dimensional components which ensures that no two components in the set are too similar. Next, we formalize the process by which high-dimensional instances, which we call “images,” are generated from the low-dimensional components, which we call “objects,” and we show how well-structuredness is sufficient for learning which objects comprise a set of sample images. We then consider the inverse problem: given a set of objects and an image generated from some unknown subset of them, identify which parts of the image arise from which objects. We consider two variants: (1) determine the minimal number of objects required to explain the image; (2) determine the correct explanation for as many locations as possible. For the latter goal, we also devise a version that is robust to adversarial corruptions, with just a slightly stronger assumption on the objects. Our work represents an attempt to put forth and study a non-standard model for dictionary learning.

Student Presenter: Liren Shan

Title: Explainable 𝑘-Means: Don’t Be Greedy, Plant Bigger Trees!

Abstract: We provide a new bi-criteria Õ(log^2 k) competitive algorithm for explainable k-means clustering. Explainable k-means was recently introduced by Dasgupta, Frost, Moshkovitz, and Rashtchian (ICML 2020). It is described by an easy to interpret and understand (threshold) decision tree or diagram. The cost of the explainable k-means clustering equals to the sum of costs of its clusters; and the cost of each cluster equals the sum of squared distances from the points in the cluster to the center of that cluster. The best non bi-criteria algorithm for explainable clustering Õ (k) competitive, and this bound is tight. Our randomized bi-criteria algorithm constructs a threshold decision tree that partitions the data set into (1+δ)k clusters (where delta is a parameter of the algorithm). The cost of this clustering is at most Õ (1/δ ⋅ log^2 k) times the cost of the optimal unconstrained k-means clustering. We show that this bound is almost optimal.

Student Presenter: Yuzhang Shang

Title: Neural Network Compression and its Application on Large Models

Abstract: Over the past few years, Deep Neural Networks (DNNs) have enabled remarkable breakthroughs in a variety of scenarios, including autonomous driving, extended reality (XR), and visual synthesis with large models. Edge devices, with their power-efficient and specialized processors and real-time scenario suitability, are becoming the primary carriers for these emerging applications. Recently, as a result of AutoML tools (e.g., Network Architecture Search) and other training-related advancements, DNNs are designed to be deeper with increasingly complex structures and larger computation sizes. Given the increasing computational demands, real-time DNN execution is an ideal but difficult goal due to the limited computing and storage resources. Thus, network compression is an important tool to realize this DNN-in-reality goal.

In this talk, I will present our recent efforts to accelerate the DNN inference from perspectives of theory and application. It mainly focuses on three innovative aspects: (1) we mitigate the overfitting of smaller compressed network by introducing the Lipschitz continuity into knowledge distillation framework; (2) targeting the information degradation in the network binarization process, we propose to maximize the mutual information between full-precision and binarized networks; and (3) our latest work is to implement post-training quantization (PTQ) on powerful but computation-expensive diffusion models. In the end, I will describe my other work directions for the real-time machine learning as well as my future research directions.

Student Presenter: Han Shao

Title: Eliciting User Preferences for Personalized Multi-Objective Decision Making through Comparative Feedback.

Abstract: In classic reinforcement learning (RL) and decision making problems, policies are evaluated with respect to a scalar reward function, and all optimal policies are the same with regards to their expected return. However, many real-world problems involve balancing multiple, sometimes conflicting, objectives whose relative priority will vary according to the preferences of each user. Consequently, a policy that is optimal for one user might be sub-optimal for another. In this work, we propose a multi-objective decision making framework that accommodates different user preferences over objectives, where preferences are learned via policy comparisons. Our model consists of a Markov decision process with a vector-valued reward function, with each user having an unknown preference vector that expresses the relative importance of each objective. The goal is to efficiently compute a near-optimal policy for a given user. We consider two user feedback models. We first address the case where a user is provided with two policies and returns their preferred policy as feedback. We then move to a different user feedback model, where a user is instead provided with two small weighted sets of representative trajectories and selects the preferred one. In both cases, we suggest an algorithm that finds a nearly optimal policy for the user using a small number of comparison queries.

Student Presenter: Kevin Stangl

Title: Sequential Strategic Screening

Abstract: We initiate the study of strategic behavior in screening processes with multiple classifiers. We focus on two contrasting settings: a conjunctive setting in which an individual must satisfy all classifiers simultaneously, and a sequential setting in which an individual to succeed must satisfy classifiers one at a time. In other words, we introduce the combination of strategic classification with screening processes. We show that sequential screening pipelines exhibit new and surprising behavior where individuals can exploit the sequential ordering of the tests to zig-zag between classifiers without having to simultaneously satisfy all of them. We demonstrate an individual can obtain a positive outcome using a limited manipulation budget even when far from the intersection of the positive regions of every classifier. Finally, we consider a learner whose goal is to design a sequential screening process that is robust to such manipulations, and provide a construction for the learner that optimizes a natural objective.

Student Presenter: Ruo Yang

Title: A Framework to Eliminate Explanation Noise from Integrated Gradients

Abstract: Integrated Gradients (IG) as well as its variants are well-known techniques for interpreting the decisions of deep neural networks. While IG-based approaches attain state-of-the-art performance, they often integrate noise into their explanation saliency maps, which reduce their interpretability. To minimize the noise, we examine the source of the noise analytically and propose a new approach to reduce the explanation noise based on our analytical findings. We propose the Important Direction Gradient Integration (IDGI) framework, which can be easily incorporated into any IG-based method that uses the Reimann Integration for integrated gradient computation. Extensive experiments with three IG-based methods show that IDGI improves them drastically on numerous interpretability metrics.

Student Presenter: Kevin Zhou

Title: Query learning of automata

Abstract: Learning various forms of automata via queries is a long-studied area of problem, initiated by Angluin in 1987 with the introduction of the L* algorithm to learn regular languages in polynomially many equivalence and membership queries. Since then, the L* algorithm has been adapted to many other settings. More recently, Chase and Freitag, inspired by ideas in model theory, gave a general method for proving query learning bounds in terms of the Littlestone dimension and consistency dimension of the concept classes in question. Applying this method to regular languages, they obtain qualitatively different results from previous work. We give an outline of the method and apply it to two other settings of automata, automata with advice and nominal automata.