lundi 12 janvier 2026

par BUTEL Nathalie

Fionn McInerney, chercheur senior, en intelligence artificielle et apprentissage automatique chez Telefónica, (Barcelone, Espagne), donnera un séminaire le lundi 12 janvier 2026 à 14h au Centre Inria d'Université Côte d'Azur dans la salle Euler Violet.

Fionn McInerney est un ancien doctorant (2016-2019) de l'EPC COATI, sous la direction de Nicolas Nisse.

 

TITLE : Non-Clashing Teaching in Graphs

ABSTRACT : In batch machine teaching models, given a concept class $\mathcal{C}$, for each concept $C\in \mathcal{C}$, a teacher presents to a learner a carefully chosen set $T(C)$ of correctly labeled examples from $C$ in such a way that the learner can reconstruct $C$ from $T(C)$. This defines the teaching map $T$ and the teaching sets $T(C)$, $C\in \mathcal{C}$. The goal is to find a teaching map that minimizes the size of a largest teaching set (the teaching dimension). Non-Clashing teaching was recently introduced by Kirkpatrick et al. [ALT 2019] and Fallat et al. [JMLR 2023], and shown to be the most efficient batch machine teaching model satisfying the benchmark for collusion-avoidance set by Goldman and Mathias [COLT 1993]. 
As any finite binary concept class can be equivalently represented by a set of balls in a graph, we study non-clashing teaching for balls in graphs. We present numerous algorithmic results (NP-hardness, W[1]-hardness, FPT algorithms) and combinatorial results (trees, cycles, interval graphs) for the non-clashing teaching dimension of balls in graphs from our COLT 2024 and ICLR 2025 papers, mainly focusing on the natural setting where the teacher can only present positive examples.