Une liste de décision est un modèle d'apprentissage automatique qui représente une tâche de classification ou de prédiction sous la forme d'une séquence ordonnée de règles « si-alors ». Chaque règle se compose d'une condition (un test sur une ou plusieurs caractéristiques d'entrée) et d'un résultat (une étiquette de classe ou une valeur prédite). Lorsqu'une nouvelle instance est présentée, le modèle évalue les règles dans l'ordre où elles apparaissent dans la liste, et le résultat de la première règle dont la condition est satisfaite est renvoyé comme prédiction. Si aucune règle ne correspond, un résultat par défaut, généralement la classe la plus fréquente dans les données d'entraînement, est utilisé. Cette structure rend les listes de décision intrinsèquement interprétables, car l'ensemble du processus de décision peut être lu comme un simple ensemble linéaire d'instructions.
Les listes de décision sont une forme d'apprentissage par règles, distincte des arbres de décision, qui utilisent une structure hiérarchique à branches. La nature séquentielle d'une liste de décision signifie que les règles antérieures priment sur les règles postérieures, ce qui permet une représentation compacte de frontières de décision complexes. Elles sont particulièrement utiles dans des domaines où l'explicabilité est cruciale, comme le diagnostic médical, la notation de crédit ou le raisonnement juridique, et elles ont été étudiées de manière approfondie dans le contexte de l'apprentissage automatique et de l'intelligence artificielle.
Origines historiques
Le concept de liste de décision a été formalisé au début des années 1990 par l'informaticien Ronald Rivest, qui l'a introduit dans un article de 1987 intitulé « Learning Decision Lists ». Rivest, connu pour ses travaux sur le cryptosystème RSA, a proposé les listes de décision comme un moyen d'apprendre des fonctions booléennes à partir d'exemples. Il a montré que les listes de décision de taille fixe sont PAC-apprenables (probablement approximativement correctes), ce qui signifie qu'elles peuvent être apprises efficacement à partir d'un nombre raisonnable d'exemples d'entraînement. Cette base théorique a positionné les listes de décision comme une alternative pratique à des modèles plus complexes comme les réseaux de neurones, qui étaient à l'époque moins compris et plus difficiles à entraîner.
Les travaux de Rivest se sont appuyés sur des recherches antérieures en induction de règles, comme l'algorithme ID3 pour les arbres de décision développé par le chercheur de l'université Carnegie-Mellon ross quinlan (bien que non inclus dans la liste de slugs fournie, son influence est notable). Les listes de décision ont ensuite été étendues pour gérer des caractéristiques continues et des problèmes multi-classes, et elles sont devenues un pilier dans le domaine de la programmation logique inductive.
Apprentissage algorithmique
L'apprentissage d'une liste de décision à partir de données implique généralement une approche gloutonne. L'algorithme commence avec une liste vide et sélectionne itérativement la meilleure règle qui couvre un sous-ensemble des instances d'entraînement, supprime ces instances, puis répète le processus sur les données restantes. La « meilleure » règle est souvent choisie en fonction de métriques comme la précision, le gain d'information, ou une combinaison de couverture et de précision. Ce processus se poursuit jusqu'à ce que toutes les instances soient couvertes ou qu'un critère d'arrêt soit atteint, comme un nombre minimal d'instances restantes ou une longueur maximale de liste.
Des variantes de cet algorithme incluent l'utilisation de la recherche en faisceau pour explorer plusieurs règles candidates simultanément, et l'incorporation de techniques d'élagage pour éviter le surapprentissage. Par exemple, l'algorithme CN2, développé à la fin des années 1980, utilise une recherche en faisceau pour induire des règles ordonnées, ce qui est étroitement lié à l'apprentissage de listes de décision. Des approches plus récentes ont intégré les listes de décision avec l'apprentissage profond en extrayant des règles de modèles de réseaux de neurones entraînés, un processus connu sous le nom d'extraction de règles, pour améliorer l'interprétabilité.
Applications et avantages
Le principal avantage des listes de décision est leur transparence. Contrairement aux grands modèles de langage ou aux systèmes basés sur des transformeurs, qui fonctionnent comme des boîtes noires, une liste de décision peut être inspectée et comprise par les humains, ce qui la rend adaptée aux décisions à enjeux élevés. Par exemple, dans le domaine de la santé, une liste de décision pourrait encoder des règles telles que « si âge > 60 et pression artérielle > 140, alors risque élevé », que les cliniciens peuvent facilement vérifier. En finance, elles sont utilisées pour la détection de fraude, où chaque règle correspond à un schéma spécifique de comportement suspect.
Les listes de décision nécessitent également des ressources informatiques minimales, car elles sont simples à stocker et à exécuter. Cela les rend attrayantes pour les systèmes embarqués ou les applications en temps réel où la latence est critique, comme dans les appareils mobiles alimentés par Qualcomm ou les microcontrôleurs basés sur Arm Holdings. Elles ont été utilisées dans des programmes de jeu d'échecs sur ordinateur pour encoder des heuristiques d'ouverture ou de fin de partie, et dans les systèmes de navigation TomTom pour la classification du trafic.
Relation avec d'autres modèles
Les listes de décision sont étroitement liées aux arbres de décision, mais elles diffèrent par leur structure. Un arbre de décision peut être converti en une liste de décision équivalente en parcourant chaque chemin de la racine aux feuilles comme une règle, bien que cela puisse entraîner une liste plus longue. Inversement, une liste de décision peut être représentée comme un arbre dégénéré où chaque nœud a au plus un enfant, mais cela n'est pas toujours efficace. Dans le paysage plus large de l'apprentissage automatique, les listes de décision sont considérées comme une forme de modèle « boîte blanche », par opposition aux modèles « boîte noire » comme les réseaux de apprentissage profond. Elles sont souvent utilisées comme référence pour comparer avec des algorithmes plus complexes, et elles servent de brique de base dans des méthodes d'ensemble, comme le boosting, où plusieurs listes de décision faibles sont combinées.
Dans la recherche moderne en IA, les listes de décision ont suscité un regain d'intérêt dans le contexte de l'IA explicable (XAI). Des chercheurs d'institutions comme MIT CSAIL et Stanford AI Lab ont exploré des méthodes pour générer des listes de décision à partir de prédictions de réseaux de neurones, visant à fournir des explications compréhensibles par les humains pour les décisions prises par des systèmes de IA générative. Cette approche hybride exploite la précision des modèles profonds tout en conservant l'interprétabilité des systèmes basés sur des règles.
Limites et extensions
Une limite clé des listes de décision est leur expressivité. Elles ne peuvent représenter que des frontières de décision alignées sur les axes (c'est-à-dire que chaque règle teste une seule caractéristique ou une conjonction de conditions simples), ce qui peut ne pas capturer des interactions complexes entre les caractéristiques. Cela peut entraîner une précision inférieure par rapport à des modèles non linéaires comme les réseaux résiduels ou les U-Net sur des tâches avec des schémas complexes. De plus, le processus d'apprentissage glouton peut produire des listes sous-optimales, et l'ordre des règles est crucial, car une règle trop large en début de liste peut masquer des règles plus spécifiques.
Des extensions pour résoudre ces problèmes incluent les listes de décision floues, qui permettent aux conditions d'avoir des degrés de vérité, et les listes de décision probabilistes, qui produisent des scores de confiance. Une autre extension est l'utilisation de listes de décision dans l'apprentissage par renforcement, où elles servent de politiques qui mappent les états aux actions, comme on le voit dans certains projets de robotique de Sanctuary AI. Malgré leur simplicité, les listes de décision restent un outil précieux dans la boîte à outils de l'IA, équilibrant précision et interprétabilité d'une manière que peu d'autres modèles peuvent égaler.