Analogical reasoning is a powerful inductive mechanism, widely used in human cognition and increasingly applied in artificial intelligence. Formal frameworks for analogical inference have been developed for Boolean domains, where inference is provably sound for affine functions and approximately correct for functions close to affine. These results have informed the design of analogy-based classifiers. However, they do not extend to regression tasks or continuous domains. In this paper, we revisit analogical inference from a foundational perspective. We first present a counterexample showing that existing generalization bounds fail even in the Boolean setting. We then introduce a unified framework for analogical reasoning in real-valued domains based on parameterized analogies defined via generalized means. This model subsumes both Boolean classification and regression, and supports analogical inference over continuous functions. We characterize the class of analogy-preserving functions in this setting and derive both worst-case and average-case error bounds under smoothness assumptions. Our results offer a general theory of analogical inference across discrete and continuous domains.

International audience

International audience

This paper presents a hybrid socio-technical methodology for constructing fuzzy numbers from numerical data while incorporating expert knowledge through an interactive Deck of Cards (DoC) process. The approach extends the existing DoC membership function construction framework by introducing a data-driven pipeline based on a convex version of Fuzzy C -Means, in which each computational step produces intermediate outputs that are translated into card-based structures for expert validation and tuning. The proposed method ensures interpretability, adaptability, and consistency between empirical evidence and expert semantics.

Abstract The H - Coloring problem is a well-known generalization of the classical -complete problem k - Coloring where the task is to determine whether an input graph admits a homomorphism to the template graph H . This problem has been the subject of intense theoretical research and in this article we study the complexity of H - Coloring with respect to the parameters clique-width and the more recent component twin-width , which describe desirable computational properties of graphs. We give two surprising linear bounds between these parameters, thus improving the previously known exponential and double exponential bounds. Our constructive proof naturally extends to related parameters and as a showcase we prove that total twin-width and linear clique-width can be related via a tight quadratic bound. These bounds naturally lead to algorithmic applications. The linear bounds between component twin-width and clique-width entail natural approximations of component twin-width, by making use of the results known for clique-width. As for computational aspects of graph coloring, we target the richer problem of counting the number of homomorphisms to H (# H - Coloring ). The first algorithm that we propose uses a contraction sequence of the input graph G parameterized by the component twin-width of G . This leads to a positive result for the counting version. The second uses a contraction sequence of the template graph H and here we instead measure the complexity with respect to the number of vertices in the input graph. Using our linear bounds we show that our algorithms are always at least as fast as the previously best # H -Coloring algorithms (based on clique-width) and for several interesting classes of graphs (e.g., cographs, cycles of length $$\varvec{\ge 7}$$ ≥ 7 , or distance-hereditary graphs) are in fact strictly faster.

Case-based prediction (CBP) methods do not learn a model of the target decision function but instead perform an inference process that depends on two similarity measures and a reference case base. This paper proposes a strategy, called EnergyCompress, to learn an effective case base by selecting relevant cases from an initial set. Use of EnergyCompress decreases CBP inference time, through case base compression, and also increases prediction performance, for a wide variety of CBP algorithms. EnergyCompress relies on the proposition of a general formulation of the CBP task in the framework of energy-based models, which leads to a new and valuable characterization of the notion of competence in case-based reasoning, in particular at the source case level. Extensive experimental results on 18 benchmark datasets comparing EnergyCompress to 5 reference algorithms for case base maintenance support the benefit of the proposed strategy.

The construction of a knowledge graph (KG) can be performed manually. Nevertheless, ensuring minimal coverage of a KG often requires the automatic data extraction from multiple sources. However, sources and extraction algorithms often vary in quality, may provide conflicting data with different levels of specificity or even contradict each other for the same entity. To reconcile these conflicting data and integrate them consistently within the KG, numerous fusion models can be adopted that simultaneously evaluate both the quality of the sources and the data provided. However, most of these models are usually evaluated on datasets that do not specifically represent differences in specificity, the heterogeneity of data types, or the presence of long-tail entities. These three challenges are frequently encountered in KG construction, making the data fusion process more complex. In this paper, we propose to overcome these limitations by introducing WikiConflict, a dataset built from the Wikidata revision history and designed for KG construction.

To build a knowledge graph, knowledge can be extracted from multiple data sources. However, for a given topic, multiple data sources rarely provide a unified view of the data. The data may differ in unit scales, levels of specificity, or even be contradictory. To jointly find the most trustworthy data and evaluate the reliability of the sources, data fusion approaches are usually applied. Although existing tools implement such approaches, they often lack essential functionalities such as a template for developing data fusion approaches, evaluation metrics, or a user-friendly visualization of the fused results. To overcome these limitations, we introduce TrustFuse, a comprehensive testbed that supports experimentation with fusion models, their evaluation, and the visualization of datasets as graphs or tables within a unified user interface.

Knowledge graphs (KGs) have become ubiquitous publicly available knowledge sources, and are nowadays covering an ever increasing array of domains. However, not all knowledge represented is useful or pertaining when considering a new application or specific task. Also, due to their increasing size, handling large KGs in their entirety entails scalability issues. These two aspects asks for efficient methods to extract subgraphs of interest from existing KGs. To this aim, we introduce KGPrune, a Web Application that, given seed entities of interest and properties to traverse, extracts their neighboring subgraphs from Wikidata. To avoid topical drift, KGPrune relies on a frugal pruning algorithm based on analogical reasoning to only keep relevant neighbors while pruning irrelevant ones. The interest of KGPrune is illustrated by two concrete applications, namely, bootstrapping an enterprise KG and extracting knowledge related to looted artworks.

With the introduction of (large) language models, there has been significant concern about the unintended bias such models may inherit from their training data. A number of studies have shown that such models propagate gender stereotypes, as well as geographical and racial bias, among other biases. While existing works tackle this issue by preprocessing data and debiasing embeddings, the proposed methods require a lot of computational resources and annotation effort while being limited to certain types of biases. To address these issues, we introduce REFINE-LM, a debiasing method that uses reinforcement learning to handle different types of biases without any fine-tuning. By training a simple model on top of the word probability distribution of a LM, our bias agnostic reinforcement learning method enables model debiasing without human annotations or significant computational resources. Experiments conducted on a wide range of models, including several LMs, show that our method (i) significantly reduces stereotypical biases while preserving LMs performance; (ii) is applicable to different types of biases, generalizing across contexts such as gender, ethnicity, religion, and nationality-based biases; and (iii) it is not expensive to train.

Counterfactual visual explanations are aimed at identifying changes in an image that will modify the prediction of a classifier.Unlike adversarial images, counterfactuals are required to be realistic.For this reason generative models such as variational autoencoders (VAE) have been used to restrain the search of counterfactuals on the data manifold.However such gradient-based approaches remain limited even when they deal with simple datasets such as MNIST.Conjecturing that these limitations result from a plateau effect which makes the gradient noisy and less informative, we improve the gradient estimation by training an ensemble of classifiers directly in the latent space of VAEs.Several experiments show that the resulting method called Clarity delivers counterfactual images of high-quality, competitive with the state-of-the-art.

In this paper, we present a bias and sustainability focused investigation of Automatic Speech Recognition (ASR) systems, namely Whisper and Massively Multilingual Speech (MMS), which have achieved state-of-the-art (SOTA) performances. Despite their improved performance in controlled settings, there remains a critical gap in understanding their efficacy and equity in real-world scenarios. We analyze ASR biases w.r.t. gender, accent, and age group, as well as their effect on downstream tasks. In addition, we examine the environmental impact of ASR systems, scrutinizing the use of large acoustic models on carbon emission and energy consumption. We also provide insights into our empirical analyses, offering a valuable contribution to the claims surrounding bias and sustainability in ASR systems.

The enumeration of logical connectives and aggregation functions defined on a finite chain has been a hot topic in the literature for the last decades. Multiple advantages can be derived from knowing a general formula about their cardinality, for instance, the ability to anticipate the computational cost required for generating operators with different properties. This is of paramount importance in image processing and decision making scenarios, where the identification of the most optimal operator is essential. Furthermore, it facilitates the examination of how constraining a certain property is in relation to its parent class. As a consequence, this paper aims to compile the main existing formulas and the methodologies with which they have been derived. Additionally, we introduce some novel formulas for the number of smooth discrete aggregation functions with neutral element or absorbing element, idempotent conjunctions, and commutative and idempotent conjunctions.

Knowledge Graph Construction (KGC) can be seen as an iterative process starting from a high quality nucleus that is refined by knowledge extraction approaches in a virtuous loop. Such a nucleus can be obtained from knowledge existing in an open KG like Wikidata. However, due to the size of such generic KGs, integrating them as a whole may entail irrelevant content and scalability issues. We propose an analogy-based approach that starts from seed entities of interest in a generic KG, and keeps or prunes their neighboring entities. We evaluate our approach on Wikidata through two manually labeled datasets that contain either domain-homogeneous or -heterogeneous seed entities. We empirically show that our analogy-based approach outperforms LSTM, Random Forest, SVM, and MLP, with a drastically lower number of parameters. We also evaluate its generalization potential in a transfer learning setting. These results advocate for the further integration of analogy-based inference in tasks related to the KG lifecycle.

Analogical proportions are statements of the form “A is to B as C is to D” that are used for several reasoning and classification tasks in artificial intelligence and natural language processing (NLP). For instance, there are analogy based approaches to semantics as well as to morphology. In fact, symbolic approaches were developed to solve or to detect analogies between character strings, e.g., the axiomatic approach as well as that based on Kolmogorov complexity. In this paper, we propose a deep learning approach to detect morphological analogies, for instance, with reinflexion or conjugation. We present empirical results that show that our framework is competitive with the above-mentioned state of the art symbolic approaches. We also explore empirically its transferability capacity across languages, which highlights interesting similarities between them.

Unintended biases in machine learning (ML) models are among the major concerns that must be addressed to maintain public trust in ML. In this paper, we address process fairness of ML models that consists in reducing the dependence of models on sensitive features, without compromising their performance. We revisit the framework FixOut that is inspired in the approach “fairness through unawareness” to build fairer models. We introduce several improvements such as automating the choice of FixOut's parameters. Also, FixOut was originally proposed to improve fairness of ML models on tabular data. We also demonstrate the feasibility of FixOut's workflow for models on textual data. We present several experimental results that illustrate the fact that FixOut improves process fairness on different classification settings.

A current challenge in graph clustering is to tackle the issue of complex networks, i.e , graphs with attributed vertices and/or edges. In this paper, we present GraphTrees, a novel method that relies on random decision trees to compute pairwise dissimilarities between vertices in a graph. We show that using different types of trees, it is possible to extend this framework to graphs where the vertices have attributes. While many existing methods that tackle the problem of clustering vertices in an attributed graph are limited to categorical attributes, GraphTrees can handle heterogeneous types of vertex attributes. Moreover, unlike other approaches, the attributes do not need to be preprocessed. We also show that our approach is competitive with well-known methods in the case of non-attributed graphs in terms of quality of clustering, and provides promising results in the case of vertex-attributed graphs. By extending the use of an already well established approach – the random trees – to graphs, our proposed approach opens new research directions, by leveraging decades of research on this topic.

Packet filtering is widely used in multiple networking applications, including firewalls, intrusion detection systems, routers and load balances, to decide whether to accept or deny an incoming packet. This mechanism relies on packet's header fields to filter such traffic by using range rules of IP addresses or ports. However, the set of packet filters has to handle a growing number of connected nodes and many of them are compromised and used as sources of attacks. For instance, IP filter sets available in blacklists may reach several millions of entries, and may require large memory space for their storage in filtering appliances. In this paper, we propose a new method based on a double mask IP prefix representation associated to a linear transformation algorithm to build a reduced set of range rules. Our experiments show that the proposed method achieves a reduction ratio of up to 74% on synthetic range rule sets.

The majority function $\langle xyz\rangle$ evaluates to true, if at least two of its Boolean inputs evaluate to true. The majority function has frequently been studied as a central primitive in logic synthesis applications for many decades. Knuth refers to the majority function in the last volume of his seminal The Art of Computer Programming as “probably the most important ternary operation in the entire universe.” Majority logic sythesis has recently regained signficant interest in the design automation community due to nanoemerging technologies which operate based on the majority function. In addition, majority logic synthesis has successfully been employed in CMOS-based applications such as standard cell or FPGA mapping. This tutorial gives a broad introduction into the field of majority logic synthesis. It will review fundamental results and describe recent contributions from theory, practice, and applications.

It has been observed that a particular form of analogical inference, based on analogical proportions, yields competitive results in classification tasks. Using the algebraic normal form of Boolean functions, it has been shown that analogical prediction is always exact iff the labeling function is affine. We point out that affine functions are also meaningful when using another view of analogy. We address the accuracy of analogical inference for arbitrary Boolean functions and show that if a function is epsilon-close to an affine function, then the probability of making a wrong prediction is upper bounded by 4 epsilon. This result is confirmed by an empirical study showing that the upper bound is tight. It highlights the specificity of analogical inference, also characterized in terms of the Hamming distance.

Training set extension is an important issue in machine learning. Indeed when the examples at hand are in a limited quantity, the performances of standard classifiers may significantly decrease and it can be helpful to build additional examples. In this paper, we consider the use of analogical reasoning, and more particularly of analogical proportions for extending training sets. Here the ground truth labels are considered to be given by a (partially known) function. We examine the conditions that are required for such functions to ensure an error-free extension in a Boolean setting. To this end, we introduce the notion of Analogy Preserving (AP) functions, and we prove that their class is the class of affine Boolean functions. This noteworthy theoretical result is complemented with an empirical investigation of approximate AP functions, which suggests that they remain suitable for training set extension.

We study the so-called signed discrete Choquet integral (also called non-monotonic discrete Choquet integral) regarded as the Lovász extension of a pseudo-Boolean function which vanishes at the origin. We present axiomatizations of this generalized Choquet integral, given in terms of certain functional equations, as well as by necessary and sufficient conditions which reveal desirable properties in aggregation theory.

In this paper we consider a multicriteria aggregation model where local utility functions of different sorts are aggregated using Sugeno integrals, and which we refer to as Sugeno utility functions. We propose a general approach to study such functions via the notion of pseudo-Sugeno integral (or, equivalently, pseudo-polynomial function), which naturally generalizes that of Sugeno integral, and provide several axiomatizations for this class of functions. Moreover, we address and solve the problem of factorizing a Sugeno utility function as a composition q(φ1(x1),…,φn(xn)) of a Sugeno integral q with local utility functions φi, if such a factorization exists.