Résumé technique : Structure des frontières de classificateurs : Étude de cas pour un classificateur Bayésien

1. Énoncé du problème

L'article aborde le défi de la compréhension des frontières de décision des classificateurs opérant dans des espaces d'entrée discrets de haute dimension. Bien que les classificateurs soient omniprésents dans des domaines allant de la reconnaissance faciale aux véhicules autonomes, la géométrie de leurs frontières de décision — spécifiquement l'ensemble des points d'entrée où une perturbation minimale modifie la sortie de classification — est souvent mal comprise.

Les auteurs se concentrent sur une étude de cas spécifique : la classification de lectures d'ADN courtes (longueur 101) générées par des séquenceurs de nouvelle génération (NGS) en l'un des trois génomes viraux candidats (Adénovirus, SARS-CoV-2 et SARS-CoV). L'espace d'entrée est discret (séquences de nucléotides) et les « voisins » d'une séquence sont définis comme ceux différant exactement par un nucléotide (Polymorphismes d'un seul nucléotide ou SNPs). Le problème central consiste à quantifier la taille, la géométrie et l'incertitude associées à la frontière où la décision du classificateur change, particulièrement étant donné que les données du monde réel contiennent souvent des erreurs de séquençage ou des polymorphismes naturels qui placent les lectures près de ces frontières.

2. Méthodologie

2.1 Le classificateur

L'étude utilise un classificateur Bayésien déterministe basé sur les distributions de triplets (codons).

• Espace d'entrée ($I$) : Toutes les séquences de longueur 101 issues de l'alphabet $\{A, C, G, T, N\}$ (où $N$ représente les bases indéterminées).
• Espace de sortie ($O$) : $\{Adeno, COVID, SARS\}$.
• Mécanisme : Le classificateur calcule la probabilité a posteriori pour chaque génome en utilisant une loi a priori uniforme et des fonctions de vraisemblance dérivées des distributions de triplets (modélisées comme des chaînes de Markov d'ordre deux). La décision est l'estimation du Maximum A Posteriori (MAP).
• Définition du voisinage : Deux lectures sont voisines si leur distance de Hamming est 1. Chaque lecture possède 404 voisins.

2.2 Définition de la frontière et mesures d'incertitude

La Frontière ($B$) est définie comme l'ensemble des entrées $R$ où au moins un voisin $R'$ est classé différemment ($C(R) \neq C(R')$).

Pour quantifier l'incertitude pour tout classificateur (même ceux dépourvus de sorties probabilistes inhérentes), les auteurs proposent deux mesures d'incertitude de substitution :

1. Statut de la frontière (BS) : Le nombre d'autres génomes apparaissant dans la classification des voisins d'une lecture.
   • $BS=0$ : Tous les voisins correspondent à la classification de la lecture (point intérieur).
   • $BS=1$ : Un autre génome apparaît parmi les voisins.
   • $BS=2$ : Les deux autres génomes apparaissent parmi les voisins.
2. Similarité des voisins (NS) : Une métrique basée sur la distance de Hellinger entre la distribution de classification de la lecture (dégénérée) et la distribution des classifications de ses voisins.
   • $NS=1$ : Tous les voisins partagent la même décision (forte certitude).
   • $NS=0$ : Les voisins sont maximalement diversifiés (forte incertitude).
   • Note : L'article distingue cela de la « justesse » ; un NS élevé implique une cohérence avec les voisins, pas nécessairement une justesse par rapport à la vérité terrain.

2.3 Stratégies d'exploration

L'article examine trois méthodes pour localiser et explorer la frontière :

• Chemins de Hamming : Retracer des chemins entre des lectures de classifications différentes pour identifier les points de franchissement.
• Marches aléatoires : Effectuer des marches aléatoires sur le graphe d'entrée pour détecter lorsque la décision du classificateur bascule.
• Ramper sur la frontière : Tenter de se déplacer le long de la frontière (en restant dans $B$) pour évaluer sa connectivité et sa complexité géométrique.

3. Résultats clés

3.1 Taille et géométrie de la frontière

Contrairement à l'intuition selon laquelle les frontières de décision dans les espaces de haute dimension sont « minces » (variétés de dimension inférieure), l'étude révèle que la frontière est grande et complexe.

• Taille : Environ 30,52 % (1 791 sur 5 869) des lectures de l'ensemble de données se situent sur la frontière.
• Complexité : La frontière n'est pas « mince » ; les marches aléatoires partant de points aléatoires traversent fréquemment la frontière, et le fait de « ramper » sur la frontière révèle qu'elle est contiguë et « poilue » (contenant de nombreuses pointes locales où la poursuite est impossible sans faire demi-tour).
• Connectivité : La frontière semble être connectée ; des algorithmes gloutons ont réussi à connecter des points de frontière sans quitter l'ensemble de la frontière dans près de 100 essais.

3.2 Relation avec la performance de classification

• Corrélation avec l'erreur : Il existe une forte corrélation entre le fait de se trouver sur la frontière et la mauvaise classification. 64,66 % des lectures mal classées se situent sur la frontière, contre seulement 22,81 % des lectures correctement classées.
• Variation selon la source : Les lectures SARS avaient significativement plus de chances de se situer sur la frontière (40,0 %) par rapport à Adeno (30,0 %) ou COVID (22,1 %).
• Mesures de substitution vs mesures inhérentes : La Similarité des voisins (NS) corrèle fortement avec les mesures d'incertitude inhérentes du classificateur :
  • Corrélation avec la Probabilité A Posteriori Maximale (MP) : $0,8488$.
  • Corrélation avec l'Entropie A Posteriori (PE) : $-0,7167$.
  • Les courbes Caractéristiques de Fonctionnement du Récepteur (ROC) montrent que l'utilisation de NS comme seuil pour l'acceptation de la décision est essentiellement identique en performance à l'utilisation du seuil de Probabilité A Posteriori Maximale (MAP).

3.3 Généralisabilité

• Autres ensembles de données : Lorsqu'appliquées à des séquences aléatoires ou à des génomes distants (par exemple, E. coli, chromosome 1 humain), la taille de la frontière a diminué (par exemple, ~10-20 % pour E. coli), mais est restée substantielle. Dans les régions éloignées des données d'entraînement, le classificateur tend à dégénérer (classant presque tout comme Adénovirus), réduisant la densité de la frontière.
• Autres classificateurs : Des expériences préliminaires avec des modèles de partition, des forêts aléatoires et des réseaux de neurones sur les mêmes données ont montré des comportements similaires concernant la taille de la frontière et la Similarité des voisins, suggérant que ces propriétés ne sont pas uniques au classificateur Bayésien.

4. Contributions clés

1. Conceptualisation de la frontière : L'article définit et caractérise la frontière du classificateur dans des espaces discrets de haute dimension, démontrant qu'elle peut constituer une partie significative (jusqu'à 30 %) de l'espace d'entrée plutôt que d'être un ensemble négligeable de dimension inférieure.
2. Mesures d'incertitude de substitution : L'introduction du Statut de la frontière et de la Similarité des voisins en tant que métriques d'incertitude calculables applicables à n'importe quel classificateur opérant sur un espace d'entrée structuré en graphe, indépendamment du fait que le classificateur fournisse ou non des scores de confiance internes.
3. Techniques d'exploration : Le développement et l'évaluation d'algorithmes (chemins de Hamming, marches aléatoires, ramper sur la frontière) pour cartographier la topologie des frontières de décision.
4. Preuves empiriques : Fournir des preuves concrètes qu'une forte incertitude (faible Similarité des voisins) est un indicateur fort d'une éventuelle mauvaise classification et que la frontière est une caractéristique omniprésente de l'espace d'entrée.

5. Importance et affirmations

L'article affirme que la compréhension de la frontière éclaire le fonctionnement d'un classificateur et met en évidence la « fragilité » des points situés près de la frontière.

• Utilité diagnostique : La Similarité des voisins sert d'outil diagnostique pratique. Une faible valeur de NS indique qu'une entrée spécifique est instable (un petit changement modifie la sortie), suggérant la nécessité de prudence ou d'une investigation plus poussée, en particulier dans des applications critiques comme la détection d'agents pathogènes.
• Qualité des données : Les auteurs suggèrent qu'une forte sensibilité aux changements de nucléotide unique (statut de frontière élevé) peut indiquer des problèmes de qualité des données ou que l'entrée se situe en dehors de la distribution « attendue » des données d'entraînement.
• Portée modeste : Les auteurs reconnaissent les limitations computationnelles. Le calcul de NS pour tous les voisins est coûteux (nécessitant 404 évaluations de classificateur par lecture). Bien que des stratégies d'échantillonnage montrent des promesses (estimer NS avec 20 voisins échantillonnés donne une erreur de 5 %), l'article ne prétend pas que ce problème est résolu pour des systèmes de production à grande échelle sans optimisation supplémentaire.
• Question fondamentale : L'article conclut en posant une question statistique : une faible valeur de NS est-elle une affirmation concernant la lecture (elle est ambiguë/problématique) ou le classificateur (il est mal entraîné ou les données d'entraînement sont insuffisantes) ? Les auteurs suggèrent que si une lecture se trouve sur la frontière pour plusieurs classificateurs, il est probable que ce soit la lecture elle-même qui soit problématique.

En résumé, l'article soutient que pour les données discrètes, la frontière de décision est une structure grande, complexe et connectée qui impacte significativement la fiabilité du classificateur, et que la Similarité des voisins fournit une méthode robuste et agnostique au modèle pour quantifier l'incertitude associée aux décisions de classification individuelles.