Arrow Research search

Author name cluster

Stefano Teso

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

36 papers
2 author rows

Possible papers

36

AAAI Conference 2026 Conference Paper

Human Cognitive Biases in Explanation-based Interaction: The Case of Within and Between Session Order Effect

  • Dario Pesenti
  • Alessandro Bogani
  • Katya Tentori
  • Stefano Teso

Explanatory Interactive Learning (XIL) is a powerful interactive learning framework designed to enable users to customize and correct AI models by interacting with their explanations. In a nutshell, XIL algorithms select a number of items on which an AI model made a decision (e.g., images and their tags) and present them to users, together with corresponding explanations (e.g., image regions that drive the model’s decision). Then, users supply corrective feedback for the explanations, which the algorithm uses to improve the model. Despite showing promise in debugging tasks, recent studies have raised concerns that explanatory interaction may trigger order effects, a well-known cognitive bias in which the sequence of presented items influences users’ trust and, critically, the quality of their feedback. We argue that these studies are not entirely conclusive, as the experimental designs and tasks employed differ substantially from common XIL use cases, complicating interpretation. To clarify the interplay between order effects and explanatory interaction, we ran a larger-scale user study (n = 713 total) designed to mimic common XIL tasks. Specifically, we assessed order effects both within and between debugging sessions by manipulating the order in which correct and wrong explanations are presented to participants. Order effects had a limited but significant impact on users’ agreement with the model (i.e., a behavioral measure of their trust), and only when examined within debugging sessions, not between them. The quality of users’ feedback reached satisfactory levels overall, with order effects exerting only a small and inconsistent influence both within and between sessions. Overall, our findings suggest that order effects do not pose a significant issue to the successful employment of XIL approaches. More broadly, our work contributes to the ongoing efforts for understanding human factors in AI.

PDF Details DOI

ICML Conference 2025 Conference Paper

Beyond Topological Self-Explainable GNNs: A Formal Explainability Perspective

  • Steve Azzolin
  • Sagar Malhotra
  • Andrea Passerini
  • Stefano Teso

Self-Explainable Graph Neural Networks (SE-GNNs) are popular explainable-by-design GNNs, but their explanations’ properties and limitations are not well understood. Our first contribution fills this gap by formalizing the explanations extracted by some popular SE-GNNs, referred to as Minimal Explanations (MEs), and comparing them to established notions of explanations, namely Prime Implicant (PI) and faithful explanations. Our analysis reveals that MEs match PI explanations for a restricted but significant family of tasks. In general, however, they can be less informative than PI explanations and are surprisingly misaligned with widely accepted notions of faithfulness. Although faithful and PI explanations are informative, they are intractable to find and we show that they can be prohibitively large. Given these observations, a natural choice is to augment SE-GNNs with alternative modalities of explanations taking care of SE-GNNs’ limitations. To this end, we propose Dual-Channel GNNs that integrate a white-box rule extractor and a standard SE-GNN, adaptively combining both channels. Our experiments show that even a simple instantiation of Dual-Channel GNNs can recover succinct rules and perform on par or better than widely used SE-GNNs.

Details

ICLR Conference 2025 Conference Paper

Logically Consistent Language Models via Neuro-Symbolic Integration

  • Diego Calanzone
  • Stefano Teso
  • Antonio Vergari

Current large language models (LLMs) are far from reliable: they are prone to generate non-factual information and, more crucially, to contradict themselves when prompted to reason about relations between real entities of the world. These problems are currently addressed with large scale fine-tuning or by delegating consistent reasoning to external tools. In this work, we strive for a middle ground and leverage a training objective based on a principled neuro-symbolic loss that teaches a LLM to be consistent with external knowledge in the form of a set of facts and rules. Fine-tuning with such a loss on a limited set of facts enables our LLMs to be more logically consistent than previous baselines for a given constraint. Our approach also allows to easily combine multiple logical constraints at once in a principled way, delivering LLMs that are more consistent w.r.t. all the selected rules. Moreover, our method allows LLMs to extrapolate to unseen but semantically similar factual knowledge, represented in unseen datasets, more systematically.

Details

ICLR Conference 2025 Conference Paper

Reconsidering Faithfulness in Regular, Self-Explainable and Domain Invariant GNNs

  • Steve Azzolin
  • Antonio Longa
  • Stefano Teso
  • Andrea Passerini

As Graph Neural Networks (GNNs) become more pervasive, it becomes paramount to build reliable tools for explaining their predictions. A core desideratum is that explanations are *faithful*, i.e., that they portray an accurate picture of the GNN's reasoning process. However, a number of different faithfulness metrics exist, begging the question of what is faithfulness exactly and how to achieve it. We make three key contributions. We begin by showing that *existing metrics are not interchangeable* -- i.e., explanations attaining high faithfulness according to one metric may be unfaithful according to others -- and can *systematically ignore important properties of explanations*. We proceed to show that, surprisingly, *optimizing for faithfulness is not always a sensible design goal*. Specifically, we prove that for injective regular GNN architectures, perfectly faithful explanations are completely uninformative. This does not apply to modular GNNs, such as self-explainable and domain-invariant architectures, prompting us to study the relationship between architectural choices and faithfulness. Finally, we show that *faithfulness is tightly linked to out-of-distribution generalization*, in that simply ensuring that a GNN can correctly recognize the domain-invariant subgraph, as prescribed by the literature, does not guarantee that it is invariant unless this subgraph is also faithful. All our code can be found in the supplementary material.

Details

NeurIPS Conference 2025 Conference Paper

Shortcuts and Identifiability in Concept-based Models from a Neuro-Symbolic Lens

  • Samuele Bortolotti
  • Emanuele Marconato
  • Paolo Morettin
  • Andrea Passerini
  • Stefano Teso

Concept-based Models are neural networks that learn a concept extractor to map inputs to high-level concepts and an inference layer to translate these into predictions. Ensuring these modules produce interpretable concepts and behave reliably in out-of-distribution is crucial, yet the conditions for achieving this remain unclear. We study this problem by establishing a novel connection between Concept-based Models and reasoning shortcuts (RSs), a common issue where models achieve high accuracy by learning low-quality concepts, even when the inference layer is fixed and provided upfront. Specifically, we extend RSs to the more complex setting of Concept-based Models and derive theoretical conditions for identifying both the concepts and the inference layer. Our empirical results highlight the impact of RSs and show that existing methods, even combined with multiple natural mitigation strategies, often fail to meet these conditions in practice.

PDF Details

NeurIPS Conference 2024 Conference Paper

A Neuro-Symbolic Benchmark Suite for Concept Quality and Reasoning Shortcuts

  • Samuele Bortolotti
  • Emanuele Marconato
  • Tommaso Carraro
  • Paolo Morettin
  • Emile van Krieken
  • Antonio Vergari
  • Stefano Teso
  • Andrea Passerini

The advent of powerful neural classifiers has increased interest in problems that require both learning and reasoning. These problems are critical for understanding important properties of models, such as trustworthiness, generalization, interpretability, and compliance to safety and structural constraints. However, recent research observed that tasks requiring both learning and reasoning on background knowledge often suffer from reasoning shortcuts (RSs): predictors can solve the downstream reasoning task without associating the correct concepts to the high-dimensional data. To address this issue, we introduce rsbench, a comprehensive benchmark suite designed to systematically evaluate the impact of RSs on models by providing easy access to highly customizable tasks affected by RSs. Furthermore, rsbench implements common metrics for evaluating concept quality and introduces novel formal verification procedures for assessing the presence of RSs in learning tasks. Using rsbench, we highlight that obtaining high quality concepts in both purely neural and neuro-symbolic models is a far-from-solved problem. rsbench is available at: https: //unitn-sml. github. io/rsbench.

PDF Details DOI

UAI Conference 2024 Conference Paper

BEARS Make Neuro-Symbolic Models Aware of their Reasoning Shortcuts

  • Emanuele Marconato
  • Samuele Bortolotti
  • Emile van Krieken
  • Antonio Vergari
  • Andrea Passerini
  • Stefano Teso

Neuro-Symbolic (NeSy) predictors that conform to symbolic knowledge {–} encoding, e. g. , safety constraints {–} can be affected by Reasoning Shortcuts (RSs): They learn concepts consistent with the symbolic knowledge by exploiting unintended semantics. RSs compromise reliability and generalization and, as we show in this paper, they are linked to NeSy models being overconfident about the predicted concepts. Unfortunately, the only trustworthy mitigation strategy requires collecting costly dense supervision over the concepts. Rather than attempting to avoid RSs altogether, we propose to ensure NeSy models are aware of the semantic ambiguity of the concepts they learn, thus enabling their users to identify and distrust low-quality concepts. Starting from three simple desiderata, we derive bears (BE Aware of Reasoning Shortcuts), an ensembling technique that calibrates the model’s concept-level confidence without compromising prediction accuracy, thus encouraging NeSy architectures to be uncertain about concepts affected by RSs. We show empirically that bears improves RS-awareness of several state-of-the-art NeSy models, and also facilitates acquiring informative dense annotations for mitigation purposes.

Details

TMLR Journal 2024 Journal Article

Personalized Algorithmic Recourse with Preference Elicitation

  • Giovanni De Toni
  • Paolo Viappiani
  • Stefano Teso
  • Bruno Lepri
  • Andrea Passerini

Algorithmic Recourse (AR) is the problem of computing a sequence of actions that -- once performed by a user -- overturns an undesirable machine decision. It is paramount that the sequence of actions does not require too much effort for users to implement. Yet, most approaches to AR assume that actions cost the same for all users, and thus may recommend unfairly expensive recourse plans to certain users. Prompted by this observation, we introduce PEAR, the first human-in-the-loop approach capable of providing personalized algorithmic recourse tailored to the needs of any end-user. PEAR builds on insights from Bayesian Preference Elicitation to iteratively refine an estimate of the costs of actions by asking choice set queries to the target user. The queries themselves are computed by maximizing the Expected Utility of Selection, a principled measure of information gain accounting for uncertainty on both the cost estimate and the user's responses. PEAR integrates elicitation into a Reinforcement Learning agent coupled with Monte Carlo Tree Search to quickly identify promising recourse plans. Our empirical evaluation on real-world datasets highlights how PEAR produces high-quality personalized recourse in only a handful of iterations.

PDF Details

ICLR Conference 2023 Conference Paper

Concept-level Debugging of Part-Prototype Networks

  • Andrea Bontempelli
  • Stefano Teso
  • Katya Tentori
  • Fausto Giunchiglia
  • Andrea Passerini

Part-prototype Networks (ProtoPNets) are concept-based classifiers designed to achieve the same performance as black-box models without compromising transparency. ProtoPNets compute predictions based on similarity to class-specific part-prototypes learned to recognize parts of training examples, making it easy to faithfully determine what examples are responsible for any target prediction and why. However, like other models, they are prone to picking up confounders and shortcuts from the data, thus suffering from compromised prediction accuracy and limited generalization. We propose ProtoPDebug, an effective concept-level debugger for ProtoPNets in which a human supervisor, guided by the model’s explanations, supplies feedback in the form of what part-prototypes must be forgotten or kept, and the model is fine-tuned to align with this supervision. Our experimental evaluation shows that ProtoPDebug outperforms state-of-the-art debuggers for a fraction of the annotation cost. An online experiment with laypeople confirms the simplicity of the feedback requested to the users and the effectiveness of the collected feedback for learning confounder-free part-prototypes. ProtoPDebug is a promising tool for trustworthy interactive learning in critical applications, as suggested by a preliminary evaluation on a medical decision making task.

Details

NeSy Conference 2023 Conference Paper

GlanceNets: Interpretable, Leak-proof Concept-based Models

  • Emanuele Marconato
  • Andrea Passerini
  • Stefano Teso

In this extended abstract, we briefly outline GlanceNets [1], a new class of deep learning classifiers that acquire high-level concepts from data and use them for both computing predictions and generating ante-hoc explanations of those predictions. In contrast with other concept-based networks, GlanceNets ensure the learned concepts, and the explanations built on them, are human interpretable, even in out-of-distribution scenarios. The core ideas at the heart of GlanceNets extend naturally to other Neuro-Symbolic architectures involving reasoning during inference.

Details

AIJ Journal 2023 Journal Article

Learning MAX-SAT from contextual examples for combinatorial optimisation

  • Mohit Kumar
  • Samuel Kolb
  • Stefano Teso
  • Luc De Raedt

Combinatorial optimisation problems are ubiquitous in artificial intelligence. Designing the underlying models, however, requires substantial expertise, which is a limiting factor in practice. The models typically consist of hard and soft constraints, or combine hard constraints with an objective function. We introduce a novel setting for learning combinatorial optimisation problems from contextual examples. These positive and negative examples show – in a particular context – whether the solutions are good enough or not. We develop our framework using the MAX-SAT formalism as it is a simple yet powerful setting having these features. We study the learnability of MAX-SAT models. Our theoretical results show that high-quality MAX-SAT models can be learned from contextual examples in the realisable and agnostic settings, as long as the data satisfies an intuitive “representativeness” condition. We also contribute two implementations based on our theoretical results: one leverages ideas from syntax-guided synthesis while the other makes use of stochastic local search techniques. The two implementations are evaluated by recovering synthetic and benchmark models from contextual examples. The experimental results support our theoretical analysis, showing that MAX-SAT models can be learned from contextual examples. Among the two implementations, the stochastic local search learner scales much better than the syntax-guided implementation while providing comparable or better models.

Details DOI

ICML Conference 2023 Conference Paper

Neuro-Symbolic Continual Learning: Knowledge, Reasoning Shortcuts and Concept Rehearsal

  • Emanuele Marconato
  • Gianpaolo Bontempo
  • Elisa Ficarra
  • Simone Calderara
  • Andrea Passerini
  • Stefano Teso

We introduce Neuro-Symbolic Continual Learning, where a model has to solve a sequence of neuro-symbolic tasks, that is, it has to map sub-symbolic inputs to high-level concepts and compute predictions by reasoning consistently with prior knowledge. Our key observation is that neuro-symbolic tasks, although different, often share concepts whose semantics remains stable over time. Traditional approaches fall short: existing continual strategies ignore knowledge altogether, while stock neuro-symbolic architectures suffer from catastrophic forgetting. We show that leveraging prior knowledge by combining neuro-symbolic architectures with continual strategies does help avoid catastrophic forgetting, but also that doing so can yield models affected by reasoning shortcuts. These undermine the semantics of the acquired concepts, even when detailed prior knowledge is provided upfront and inference is exact, and in turn continual performance. To overcome these issues, we introduce COOL, a COncept-level cOntinual Learning strategy tailored for neuro-symbolic continual problems that acquires high-quality concepts and remembers them over time. Our experiments on three novel benchmarks highlights how COOL attains sustained high performance on neuro-symbolic continual learning tasks in which other strategies fail.

Details

NeSy Conference 2023 Conference Paper

Neuro-Symbolic Reasoning Shortcuts: Mitigation Strategies and their Limitations

  • Emanuele Marconato
  • Stefano Teso
  • Andrea Passerini

Neuro-symbolic predictors learn a mapping from sub-symbolic inputs to higher-level concepts and then carry out (probabilistic) logical inference on this intermediate representation. This setup offers clear advantages in terms of consistency to symbolic prior knowledge, and is often believed to provide interpretability benefits in that – by virtue of complying with the knowledge – the learned concepts can be better understood by human stakeholders. However, it was recently shown that this setup is affected by reasoning shortcuts whereby predictions attain high accuracy by leveraging concepts with unintended semantics [1, 2], yielding poor out-of-distribution performance and compromising interpretability. In this short paper, we establish a formal link between reasoning shortcuts and the optima of the loss function, and identify situations in which reasoning shortcuts can arise. Based on this, we discuss limitations of natural mitigation strategies such as reconstruction and concept supervision.

Details

NeurIPS Conference 2023 Conference Paper

Not All Neuro-Symbolic Concepts Are Created Equal: Analysis and Mitigation of Reasoning Shortcuts

  • Emanuele Marconato
  • Stefano Teso
  • Antonio Vergari
  • Andrea Passerini

Neuro-Symbolic (NeSy) predictive models hold the promise of improved compliance with given constraints, systematic generalization, and interpretability, as they allow to infer labels that are consistent with some prior knowledge by reasoning over high-level concepts extracted from sub-symbolic inputs. It was recently shown that NeSy predictors are affected by reasoning shortcuts: they can attain high accuracy but by leveraging concepts with \textit{unintended semantics}, thus coming short of their promised advantages. Yet, a systematic characterization of reasoning shortcuts and of potential mitigation strategies is missing. This work fills this gap by characterizing them as unintended optima of the learning objective and identifying four key conditions behind their occurrence. Based on this, we derive several natural mitigation strategies, and analyze their efficacy both theoretically and empirically. Our analysis shows reasoning shortcuts are difficult to deal with, casting doubts on the trustworthiness and interpretability of existing NeSy solutions.

PDF Details

NeSy Conference 2023 Conference Paper

Semantic Probabilistic Layers for Neuro-Symbolic Learning

  • Kareem Ahmed
  • Stefano Teso
  • Kai-Wei Chang 0001
  • Guy Van den Broeck
  • Antonio Vergari

In this extended abstract, we briefly outline Semantic Probabilistic Layers [1], a new layer that can be plugged into any neural network to guarantee its predictions are consistent with a set of predefined symbolic constraints while being amenable to end-to-end learning via maximum likelihood. SPLs can faithfully, and efficiently, model complex SOP tasks beyond the reach of alternative neuro-symbolic layers. We empirically demonstrate that SPLs outperform these competitors in terms of accuracy on an array of challenging structured-output prediction tasks.

Details

IJCAI Conference 2022 Conference Paper

Federated Multi-Task Attention for Cross-Individual Human Activity Recognition

  • Qiang Shen
  • Haotian Feng
  • Rui Song
  • Stefano Teso
  • Fausto Giunchiglia
  • Hao Xu

Federated Learning (FL) is an emerging privacy-aware machine learning technique that applies successfully to the collaborative learning of global models for Human Activity Recognition (HAR). As of now, the applications of FL for HAR assume that the data associated with diverse individuals follow the same distribution. However, this assumption is impractical in real-world scenarios where the same activity is frequently performed differently by different individuals. To tackle this issue, we propose FedMAT, a Federated Multi-task ATtention framework for HAR, which extracts and fuses shared as well as individual-specific multi-modal sensor data features. Specifically, we treat the HAR problem associated with each individual as a different task and train a federated multi-task model, composed of a shared feature representation network in a central server plus multiple individual-specific networks with attention modules stored in decentralized nodes. In this architecture, the attention module operates as a mask that allows to learn individual-specific features from the global model, whilst simultaneously allowing for features to be shared among different individuals. We conduct extensive experiments based on publicly available HAR datasets, which are collected in both controlled environments and real-world scenarios. Numeric results verify that our proposed FedMAT significantly outperforms baselines not only in generalizing to existing individuals but also in adapting to new individuals.

PDF Details DOI

NeurIPS Conference 2022 Conference Paper

GlanceNets: Interpretable, Leak-proof Concept-based Models

  • Emanuele Marconato
  • Andrea Passerini
  • Stefano Teso

There is growing interest in concept-based models (CBMs) that combine high-performance and interpretability by acquiring and reasoning with a vocabulary of high-level concepts. A key requirement is that the concepts be interpretable. Existing CBMs tackle this desideratum using a variety of heuristics based on unclear notions of interpretability, and fail to acquire concepts with the intended semantics. We address this by providing a clear definition of interpretability in terms of alignment between the model’s representation and an underlying data generation process, and introduce GlanceNets, a new CBM that exploits techniques from disentangled representation learning and open-set recognition to achieve alignment, thus improving the interpretability of the learned concepts. We show that GlanceNets, paired with concept-level supervision, achieve better alignment than state-of-the-art approaches while preventing spurious information from unintendedly leaking into the learned concepts.

PDF Details

AAAI Conference 2022 Conference Paper

Machine Learning for Utility Prediction in Argument-Based Computational Persuasion

  • Ivan Donadello
  • Anthony Hunter
  • Stefano Teso
  • Mauro Dragoni

Automated persuasion systems (APS) aim to persuade a user to believe something by entering into a dialogue in which arguments and counterarguments are exchanged. To maximize the probability that an APS is successful in persuading a user, it can identify a global policy that will allow it to select the best arguments it presents at each stage of the dialogue whatever arguments the user presents. However, in real applications, such as for healthcare, it is unlikely the utility of the outcome of the dialogue will be the same, or the exact opposite, for the APS and user. In order to deal with this situation, games in extended form have been harnessed for argumentation in Bi-party Decision Theory. This opens new problems that we address in this paper: (1) How can we use Machine Learning (ML) methods to predict utility functions for different subpopulations of users? and (2) How can we identify for a new user the best utility function from amongst those that we have learned? To this extent, we develop two ML methods, EAI and EDS, that leverage information coming from the users to predict their utilities. EAI is restricted to a fixed amount of information, whereas EDS can choose the information that best detects the subpopulations of a user. We evaluate EAI and EDS in a simulation setting and in a realistic case study concerning healthy eating habits. Results are promising in both cases, but EDS is more effective at predicting useful utility functions.

PDF Details

NeurIPS Conference 2022 Conference Paper

Semantic Probabilistic Layers for Neuro-Symbolic Learning

  • Kareem Ahmed
  • Stefano Teso
  • Kai-Wei Chang
  • Guy Van den Broeck
  • Antonio Vergari

We design a predictive layer for structured-output prediction (SOP) that can be plugged into any neural network guaranteeing its predictions are consistent with a set of predefined symbolic constraints. Our Semantic Probabilistic Layer (SPL) can model intricate correlations, and hard constraints, over a structured output space all while being amenable to end-to-end learning via maximum likelihood. SPLs combine exact probabilistic inference with logical reasoning in a clean and modular way, learning complex distributions and restricting their support to solutions of the constraint. As such, they can faithfully, and efficiently, model complex SOP tasks beyond the reach of alternative neuro-symbolic approaches. We empirically demonstrate that SPLs outperform these competitors in terms of accuracy on challenging SOP tasks such as hierarchical multi-label classification, pathfinding and preference learning, while retaining perfect constraint satisfaction.

PDF Details

NeurIPS Conference 2021 Conference Paper

A Compositional Atlas of Tractable Circuit Operations for Probabilistic Inference

  • Antonio Vergari
  • YooJung Choi
  • Anji Liu
  • Stefano Teso
  • Guy Van den Broeck

Circuit representations are becoming the lingua franca to express and reason about tractable generative and discriminative models. In this paper, we show how complex inference scenarios for these models that commonly arise in machine learning---from computing the expectations of decision tree ensembles to information-theoretic divergences of sum-product networks---can be represented in terms of tractable modular operations over circuits. Specifically, we characterize the tractability of simple transformations---sums, products, quotients, powers, logarithms, and exponentials---in terms of sufficient structural constraints of the circuits they operate on, and present novel hardness results for the cases in which these properties are not satisfied. Building on these operations, we derive a unified framework for reasoning about tractable models that generalizes several results in the literature and opens up novel tractable inference scenarios.

PDF Details

NeurIPS Conference 2021 Conference Paper

Interactive Label Cleaning with Example-based Explanations

  • Stefano Teso
  • Andrea Bontempelli
  • Fausto Giunchiglia
  • Andrea Passerini

We tackle sequential learning under label noise in applications where a human supervisor can be queried to relabel suspicious examples. Existing approaches are flawed, in that they only relabel incoming examples that look "suspicious" to the model. As a consequence, those mislabeled examples that elude (or don't undergo) this cleaning step end up tainting the training data and the model with no further chance of being cleaned. We propose CINCER, a novel approach that cleans both new and past data by identifying \emph{pairs of mutually incompatible examples}. Whenever it detects a suspicious example, CINCER identifies a counter-example in the training set that - according to the model - is maximally incompatible with the suspicious example, and asks the annotator to relabel either or both examples, resolving this possible inconsistency. The counter-examples are chosen to be maximally incompatible, so to serve as \emph{explanations} of the model's suspicion, and highly influential, so to convey as much information as possible if relabeled. CINCER achieves this by leveraging an efficient and robust approximation of influence functions based on the Fisher information matrix (FIM). Our extensive empirical evaluation shows that clarifying the reasons behind the model's suspicions by cleaning the counter-examples helps in acquiring substantially better data and models, especially when paired with our FIM approximation.

PDF Details

AIJ Journal 2021 Journal Article

Learning Modulo Theories for constructive preference elicitation

  • Paolo Campigotto
  • Stefano Teso
  • Roberto Battiti
  • Andrea Passerini

This paper introduces CLEO, a novel preference elicitation algorithm capable of recommending complex configurable objects characterized by both discrete and continuous attributes and constraints defined over them. While existing preference elicitation techniques focus on searching for the best instance in a database of candidates, CLEO takes a constructive approach to recommendation through interactive optimization in a space of feasible configurations. The algorithm assumes minimal initial information, i. e. , a set of catalog attributes, and defines decisional features as logic formulae combining Boolean and algebraic constraints over the attributes. The (unknown) utility of the decision maker is modeled as a weighted combination of features. CLEO iteratively alternates a preference elicitation step, where pairs of candidate configurations are selected based on the current utility model, and a refinement step where the utility is refined by incorporating the feedback received. The elicitation step leverages a Max-SMT solver to return optimal configurations according to the current utility model. The refinement step is implemented as learning to rank, and a sparsifying norm is used to favor the selection of few informative features in the combinatorial space of candidate decisional features. A major feature of CLEO is that it can recommend optimal configurations in hybrid domains (i. e. , including both Boolean and numeric attributes), thanks to the use of Max-SMT technology, while retaining uncertainty in the decision-maker's utility and noisy feedback. In so doing, it adapts the recently introduced learning modulo theory framework to the preference elicitation setting. The combinatorial formulation of the utility function coupled with the feature selection capabilities of 1-norm regularization allow to effectively deal with the uncertainty in the DM utility while retaining high expressiveness. Experimental results on complex recommendation tasks show the ability of CLEO to quickly identify optimal configurations, as well as its capacity to recover from suboptimal initial choices. Our empirical evaluation highlights how CLEO outperforms a state-of-the-art Bayesian preference elicitation algorithm when applied to a purely discrete task

Details DOI

NeSy Conference 2021 Conference Paper

Neuro-Symbolic Constraint Programming for Structured Prediction

  • Paolo Dragone
  • Stefano Teso
  • Andrea Passerini

We propose N e s t e r, a method for injecting neural networks into constrained structured predictors. N e s t e r first uses a neural network to compute an initial prediction that may or may not satisfy the constraints, and then applies a constraint-based structured predictor to refine the raw predictions according to hard and soft constraints. N e s t e r combines the advantages of its two components: the network can learn complex representations from low-level data while the constraint program on top reasons about the high-level properties and requirements of the prediction task. An empirical evaluation on handwritten equation recognition shows that N e s t e r achieves better performance than both the either component in isolation, especially when training examples are scarce, while scaling to more complex problems than other neuro-programming approaches. N e s t e r proves especially useful to reduce errors at the semantic level of the problem, which is particularly challenging for neural network architectures.

Details

NeurIPS Conference 2020 Conference Paper

Efficient Generation of Structured Objects with Constrained Adversarial Networks

  • Luca Di Liello
  • Pierfrancesco Ardino
  • Jacopo Gobbi
  • Paolo Morettin
  • Stefano Teso
  • Andrea Passerini

Generative Adversarial Networks (GANs) struggle to generate structured objects like molecules and game maps. The issue is that structured objects must satisfy hard requirements (e. g. , molecules must be chemically valid) that are difficult to acquire from examples alone. As a remedy, we propose Constrained Adversarial Networks (CANs), an extension of GANs in which the constraints are embedded into the model during training. This is achieved by penalizing the generator proportionally to the mass it allocates to invalid structures. In contrast to other generative models, CANs support efficient inference of valid structures (with high probability) and allows to turn on and off the learned constraints at inference time. CANs handle arbitrary logical constraints and leverage knowledge compilation techniques to efficiently evaluate the disagreement between the model and the constraints. Our setup is further extended to hybrid logical-neural constraints for capturing very complex constraints, like graph reachability. An extensive empirical analysis shows that CANs efficiently generate valid structures that are both high-quality and novel.

PDF Details

IJCAI Conference 2020 Conference Paper

Learning in the Wild with Incremental Skeptical Gaussian Processes

  • Andrea Bontempelli
  • Stefano Teso
  • Fausto Giunchiglia
  • Andrea Passerini

The ability to learn from human supervision is fundamental for personal assistants and other interactive applications of AI. Two central challenges for deploying interactive learners in the wild are the unreliable nature of the supervision and the varying complexity of the prediction task. We address a simple but representative setting, incremental classification in the wild, where the supervision is noisy and the number of classes grows over time. In order to tackle this task, we propose a redesign of skeptical learning centered around Gaussian Processes (GPs). Skeptical learning is a recent interactive strategy in which, if the machine is sufficiently confident that an example is mislabeled, it asks the annotator to reconsider her feedback. In many cases, this is often enough to obtain clean supervision. Our redesign, dubbed ISGP, leverages the uncertainty estimates supplied by GPs to better allocate labeling and contradiction queries, especially in the presence of noise. Our experiments on synthetic and real-world data show that, as a result, while the original formulation of skeptical learning produces over-confident models that can fail completely in the wild, ISGP works well at varying levels of noise and as new classes are observed.

PDF Details DOI

AAAI Conference 2020 Conference Paper

Learning MAX-SAT from Contextual Examples for Combinatorial Optimisation

  • Mohit Kumar
  • Samuel Kolb
  • Stefano Teso
  • Luc De Raedt

Combinatorial optimization problems are ubiquitous in artificial intelligence. Designing the underlying models, however, requires substantial expertise, which is a limiting factor in practice. The models typically consist of hard and soft constraints, or combine hard constraints with a preference function. We introduce a novel setting for learning combinatorial optimisation problems from contextual examples. These positive and negative examples show – in a particular context – whether the solutions are good enough or not. We develop our framework using the MAX-SAT formalism. We provide learnability results within the realizable and agnostic settings, as well as HASSLE, an implementation based on syntax-guided synthesis and showcase its promise on recovering synthetic and benchmark instances from examples.

PDF Details

AAAI Conference 2020 Conference Paper

Learning Weighted Model Integration Distributions

  • Paolo Morettin
  • Samuel Kolb
  • Stefano Teso
  • Andrea Passerini

Weighted model integration (WMI) is a framework for probabilistic inference over distributions with discrete and continuous variables and structured supports. Despite the growing popularity of WMI, existing density estimators ignore the problem of learning a structured support, and thus fail to handle unfeasible configurations and piecewise-linear relations between continuous variables. We propose LARIAT, a novel method to tackle this challenging problem. In a first step, our approach induces an SMT(LRA) formula representing the support of the structured distribution. Next, it combines the latter with a density learned using a state-of-the-art estimation method. The overall model automatically accounts for the discontinuous nature of the underlying structured distribution. Our experimental results with synthetic and real-world data highlight the promise of the approach.

PDF Details

IJCAI Conference 2019 Conference Paper

Acquiring Integer Programs from Data

  • Mohit Kumar
  • Stefano Teso
  • Luc De Raedt

Integer programming (IP) is widely used within operations research to model and solve complex combinatorial problems such as personnel rostering and assignment problems. Modelling such problems is difficult for non-experts and expensive when hiring domain experts to perform the modelling. For many tasks, however, examples of working solutions are readily available. We propose ARNOLD, an approach that partially automates the modelling step by learning an integer program from example solutions. Contrary to existing alternatives, ARNOLD natively handles multi-dimensional quantities and non-linear operations, which are at the core of IP problems, and it only requires examples of feasible solution. The main challenge is to efficiently explore the space of possible programs. Our approach pairs a general-to-specific traversal strategy with a nested lexicographic ordering in order to prune large portions of the space of candidate constraints while avoiding visiting the same candidate multiple times. Our empirical evaluation shows that ARNOLD can acquire models for a number of realistic benchmark problems

PDF Details

AAAI Conference 2018 Conference Paper

Constructive Preference Elicitation Over Hybrid Combinatorial Spaces

  • Paolo Dragone
  • Stefano Teso
  • Andrea Passerini

Peference elicitation is the task of suggesting a highly preferred configuration to a decision maker. The preferences are typically learned by querying the user for choice feedback over pairs or sets of objects. In its constructive variant, new objects are synthesized “from scratch” by maximizing an estimate of the user utility over a combinatorial (possibly in- finite) space of candidates. In the constructive setting, most existing elicitation techniques fail because they rely on exhaustive enumeration of the candidates. A previous solution explicitly designed for constructive tasks comes with no formal performance guarantees, and can be very expensive in (or unapplicable to) problems with non-Boolean attributes. We propose the Choice Perceptron, a Perceptron-like algorithm for learning user preferences from set-wise choice feedback over constructive domains and hybrid Boolean-numeric feature spaces. We provide a theoretical analysis on the attained regret that holds for a large class of query selection strategies, and devise a heuristic strategy that aims at optimizing the regret in practice. Finally, we demonstrate its effectiveness by empirical evaluation against existing competitors on constructive scenarios of increasing complexity.

PDF Details

AAAI Conference 2018 Conference Paper

Decomposition Strategies for Constructive Preference Elicitation

  • Paolo Dragone
  • Stefano Teso
  • Mohit Kumar
  • Andrea Passerini

We tackle the problem of constructive preference elicitation, that is the problem of learning user preferences over very large decision problems, involving a combinatorial space of possible outcomes. In this setting, the suggested configuration is synthesized on-the-fly by solving a constrained optimization problem, while the preferences are learned iteratively by interacting with the user. Previous work has shown that Coactive Learning is a suitable method for learning user preferences in constructive scenarios. In Coactive Learning the user provides feedback to the algorithm in the form of an improvement to a suggested configuration. When the problem involves many decision variables and constraints, this type of interaction poses a significant cognitive burden on the user. We propose a decomposition technique for large preferencebased decision problems relying exclusively on inference and feedback over partial configurations. This has the clear advantage of drastically reducing the user cognitive load. Additionally, part-wise inference can be (up to exponentially) less computationally demanding than inference over full configurations. We discuss the theoretical implications of working with parts and present promising empirical results on one synthetic and two realistic constructive problems.

PDF Details

AAAI Conference 2018 Conference Paper

Learning Constraints From Examples

  • Luc De Raedt
  • Andrea Passerini
  • Stefano Teso

While constraints are ubiquitous in artificial intelligence and constraints are also commonly used in machine learning and data mining, the problem of learning constraints from examples has received less attention. In this paper, we discuss the problem of constraint learning in detail, indicate some subtle differences with standard machine learning problems, sketch some applications and summarize the state-of-the-art.

PDF Details

IJCAI Conference 2018 Conference Paper

Learning SMT(LRA) Constraints using SMT Solvers

  • Samuel Kolb
  • Stefano Teso
  • Andrea Passerini
  • Luc De Raedt

We introduce the problem of learning SMT(LRA) constraints from data. SMT(LRA) extends propositional logic with (in)equalities between numerical variables. Many relevant formal verification problems can be cast as SMT(LRA) instances and SMT(LRA) has supported recent developments in optimization and counting for hybrid Boolean and numerical domains. We introduce SMT(LRA) learning, the task of learning SMT(LRA) formulas from examples of feasible and infeasible instances, and we contribute INCAL, an exact non-greedy algorithm for this setting. Our approach encodes the learning task itself as an SMT(LRA) satisfiability problem that can be solved directly by SMT solvers. INCAL is an incremental algorithm that achieves exact learning by looking only at a small subset of the data, leading to significant speed-ups. We empirically evaluate our approach on both synthetic instances and benchmark problems taken from the SMT-LIB benchmarks repository.

PDF Details

IJCAI Conference 2018 Conference Paper

Pyconstruct: Constraint Programming Meets Structured Prediction

  • Paolo Dragone
  • Stefano Teso
  • Andrea Passerini

Constructive learning is the task of learning to synthesize structured objects from data. Examples range from classical sequence labeling to layout synthesis and drug design. Learning in these scenarios involves repeatedly synthesizing candidates subject to feasibility constraints and adapting the model based on the observed loss. Many synthesis problems of interest are non-standard: they involve discrete and continuous variables as well as arbitrary constraints among them. In these cases, widespread formalisms (like linear programming) can not be applied, and the developer is left with writing her own ad-hoc solver. This can be very time consuming and error prone. We introduce Pyconstruct, a Python library tailored for solving real-world constructive problems with minimal effort. The library leverages max-margin approaches to decouple learning from synthesis and constraint programming as a generic framework for synthesis. Pyconstruct enables easy prototyping of working solutions, allowing developers to write complex synthesis problems in a declarative fashion in few lines of code. The library is available at: http: //bit. ly/2st8nt3

PDF Details

AAAI Conference 2017 Conference Paper

Coactive Critiquing: Elicitation of Preferences and Features

  • Stefano Teso
  • Paolo Dragone
  • Andrea Passerini

When faced with complex choices, users refine their own preference criteria as they explore the catalogue of options. In this paper we propose an approach to preference elicitation suited for this scenario. We extend Coactive Learning, which iteratively collects manipulative feedback, to optionally query example critiques. User critiques are integrated into the learning model by dynamically extending the feature space. Our formulation natively supports constructive learning tasks, where the option catalogue is generated on-the-fly. We present an upper bound on the average regret suffered by the learner. Our empirical analysis highlights the promise of our approach.

PDF Details

AIJ Journal 2017 Journal Article

Structured learning modulo theories

  • Stefano Teso
  • Roberto Sebastiani
  • Andrea Passerini

Modeling problems containing a mixture of Boolean and numerical variables is a long-standing interest of Artificial Intelligence. However, performing inference and learning in hybrid domains is a particularly daunting task. The ability to model these kinds of domains is crucial in “learning to design” tasks, that is, learning applications where the goal is to learn from examples how to perform automatic de novo design of novel objects. In this paper we present Structured Learning Modulo Theories, a max-margin approach for learning in hybrid domains based on Satisfiability Modulo Theories, which allows to combine Boolean reasoning and optimization over continuous linear arithmetical constraints. The main idea is to leverage a state-of-the-art generalized Satisfiability Modulo Theory solver for implementing the inference and separation oracles of Structured Output SVMs. We validate our method on artificial and real world scenarios.

Details DOI

IJCAI Conference 2016 Conference Paper

Constructive Preference Elicitation by Setwise Max-Margin Learning

  • Stefano Teso
  • Andrea Passerini
  • Paolo Viappiani

In this paper we propose an approach to preference elicitation that is suitable to large configuration spaces beyond the reach of existing state-of-the-art approaches. Our setwise max-margin method can be viewed as a generalization of max-margin learning to sets, and can produce a set of diverse items that can be used to ask informative queries to the user. Moreover, the approach can encourage sparsity in the parameter space, in order to favor the assessment of utility towards combinations of weights that concentrate on just few features. We present a mixed integer linear programming formulation and show how our approach compares favourably with Bayesian preference elicitation alternatives and easily scales to realistic datasets.

PDF Details
v2026.09.13