Diagnostic Actif par Maximisation de l'AUC : Une Approche Efficace pour l'Identification Multiple de Pannes dans de Grands Réseaux Bruyants

Le problème du diagnostic actif se pose dans plusieurs applications telles que le diagnostic des maladies et le diagnostic des pannes dans les réseaux informatiques, où l'objectif est d'identifier rapidement les états binaires d'un ensemble d'objets (par exemple, défectueux ou fonctionnels) en sélectionnant et en observant séquentiellement des réponses (bruyantes) à des requêtes binaires. Les algorithmes actuels dans ce domaine reposent sur la propagation de croyances en boucle pour la sélection active de requêtes. Ces algorithmes ont une complexité temporelle exponentielle, ce qui les rend lents et même intractables dans de grands réseaux. Nous proposons un algorithme glouton basé sur le rang qui choisit séquentiellement des requêtes de sorte que l'aire sous la courbe ROC de la sortie basée sur le rang soit maximisée. Le critère AUC nous permet de faire une hypothèse simplificatrice qui réduit considérablement la complexité de la sélection de requêtes actives (de exponentielle à presque quadratique), avec peu ou pas de compromis sur la qualité de performance.