We introduce a novel approach (COpt) to Fixed-Budget Best-Arm Identification (FBBAI) specifically designed for contexts where both the expected rewards and their variances are unknown a priori. Our methodology starts with the derivation of a general upper bound on the misidentification probability applicable to sub-Gaussian distributions. Based on this theoretical foundation, we develop an algorithm that iteratively solves a non-linear optimization problem over empirical estimators to determine the optimal allocation of the residual sampling budget among the arms. We conducted empirical validation across a range of synthetic distribution classes and a real-world scenario based on the MovieLens dataset. Experimental results demonstrate that COpt consistently achieves superior accuracy compared to established algorithms, including Sequential Halving, VBR, and Gap-EV. Execution time remains within the range of tens of milliseconds, making it suitable for a wide range of applications.

International audience

Controlled Query Evaluation (CQE) is a methodology designed to maintain confidentiality by either rejecting specific queries or adjusting responses to safeguard sensitive information. In this investigation, our focus centers on CQE within Description Logic ontologies, aiming to ensure that queries are answered truthfully as long as possible before resorting to deceptive responses, a cooperativity property which is called the “longest honeymoon”. Our work introduces new semantics for CQE, denoted as MC-CQE, which enjoys the longest honeymoon property and outperforms previous methodologies in terms of cooperativity. We study the complexity of query answering in this new framework for ontologies expressed in the Description Logic DL-Lite_R. Specifically, we establish data complexity results under different maximally cooperative semantics and for different classes of queries. Our results identify both tractable and intractable cases. In particular, we show that the evaluation of Boolean unions of conjunctive queries is the same under all the above semantics and its data complexity is in AC^0. This result makes query answering amenable to SQL query rewriting. However, this favorable property does not extend to open queries, even with a restricted query language limited to conjunctions of atoms. While, in general, answering open queries in the MC-CQE framework is intractable, we identify a sub-family of semantics under which answering full conjunctive queries is tractable.

A deductive module of a knowledge base KB is a subset of KB that preserves a specified class of consequences. Module extraction is applied in ontology design, debugging, and reasoning. The locality-based module extractors of the OWL API are less effective when the knowledge base contains facts such as ABox assertions. The competing module extractor PrisM computes smaller modules at the cost of higher computation time. In this paper, we introduce and study a novel module extraction technique, called conditional module extraction , that can be applied to satisfiable SRIQ ( D ) knowledge bases. Experimental analysis shows that conditional module extraction constitutes an appealing alternative to PrisM and to the locality-based extractors of the OWL API, when the ABox is nonempty.

This paper introduces and investigates k-unmatchability, a counterpart of k-anonymity for knowledge graphs. Like k-anonimity, k-unmatchability enhances privacy by ensuring that any individual in any external source can always be matched to either none or at least k different anonymized individuals. The tradeoff between privacy protection and information loss can be controlled with parameter k. We analyze the data complexity of k-unmatchability under different notions of anonymization.

The spilling of suspicious or illegal substances in wastewater poses a serious global threat to human health. Low-cost sensor technologies enabling wastewater continuous monitoring are an important tool that can help face this problem. In this paper, electrical impedance measurements on different sensors are proposed in order to have a dataset of raw data to be used to perform the classification of possible contaminants in a water environment. In detail, the sensor technology is based on a proprietary multi-sensing platform called SENSIPLUS, which is arranged in a suitable set-up able to carry out measurements in water for prolonged times. Sensors metalized with different materials are jointly used to exploit sensitivity diversity to different contaminants. An ad-hoc measurement procedure has been designed, including data acquisition during the warm-up period, contaminant injection, and steady-state conditions. The dataset proposed in this paper has been acquired in different European laboratories (Italy and Poland) and is made publicly available for testing new data analysis or machine learning techniques for the detection and classification of ten wastewater dangerous “contaminants” (https://aida.unicas.it/icprchallenge2022/).