La construction d'arbres de compétences (CST) est un algorithme d'apprentissage par renforcement hiérarchique qui construit automatiquement des arbres de compétences à partir d'un ensemble de trajectoires de solutions échantillonnées obtenues par démonstration. Il a été introduit par George Konidaris, Scott Kuindersma, Andrew Barto et Roderic Grupen en 2010. L'algorithme identifie des sous-compétences réutilisables au sein des comportements démontrés et les organise en une structure arborescente, permettant à un agent de résoudre de nouvelles tâches plus efficacement en réutilisant des composants appris.
CST fonctionne en segmentant chaque trajectoire de démonstration en compétences discrètes à l'aide d'un algorithme incrémental de détection de points de changement par maximum a posteriori (MAP). Ces compétences sont ensuite alignées et fusionnées entre les trajectoires pour former un arbre de compétences, où chaque nœud représente une compétence et les arêtes indiquent des relations temporelles ou hiérarchiques. L'approche est conçue pour fonctionner en ligne, traitant les démonstrations de manière incrémentale sans nécessiter toutes les données au préalable.
Aperçu de l'algorithme
L'algorithme CST se compose de trois composants principaux : la détection de points de changement, l'alignement et la fusion. L'accent principal est mis sur la détection de points de changement en ligne, qui segmente les données en compétences en utilisant la somme de la récompense actualisée comme variable de régression cible. Chaque compétence détectée se voit attribuer une abstraction appropriée, et un filtre particulaire contrôle la complexité computationnelle.
L'algorithme de détection de points de changement traite les données pour les temps t dans T, étant donné un ensemble de modèles Q avec des probabilités a priori p(q). Il ajuste des segments du temps j+1 à t en utilisant le modèle q, calculant une probabilité d'ajustement P(j,t,q) basée sur un modèle de régression linéaire avec bruit gaussien. Le bruit a priori a une moyenne nulle et une variance suivant une distribution InverseGamma, tandis que chaque poids a priori suit une distribution Normale.
La probabilité d'ajustement est calculée à l'aide d'une formule spécifique impliquant des déterminants matriciels et des fonctions gamma. CST calcule ensuite la probabilité d'un point de changement au temps j avec le modèle q en utilisant un algorithme de Viterbi, incorporant une fonction de hasard g et sa distribution cumulative G pour modéliser les longueurs de segments.
Détails de la détection de points de changement
Pour chaque point de changement potentiel, CST calcule P_t(j,q) comme le produit de la probabilité de survie, de la probabilité d'ajustement, de la probabilité a priori du modèle et de la probabilité MAP au temps j. La probabilité MAP P_j^MAP est déterminée en maximisant sur les points de changement précédents et les modèles, pondérés par la fonction de hasard. Cette formulation récursive permet un traitement en ligne efficace.
Le modèle de régression utilise la récompense actualisée comme variable cible, permettant à l'algorithme de se concentrer sur les compétences qui mènent à des récompenses cumulatives plus élevées. Le filtre particulaire maintient un ensemble de points de changement candidats, gardant le coût computationnel gérable même avec de longues trajectoires.
Alignement et fusion des compétences
Après la détection de points de changement, CST aligne les compétences entre différentes trajectoires de démonstration. Les compétences qui présentent des schémas temporels et des dynamiques de récompense similaires sont regroupées. Le processus d'alignement utilise les paramètres de régression ajustés pour faire correspondre les segments qui représentent probablement la même compétence sous-jacente.
La fusion intègre ensuite les compétences alignées dans l'arbre de compétences. Lorsque plusieurs démonstrations contiennent des compétences similaires, elles sont combinées en un seul nœud avec des statistiques associées. La structure arborescente capture à la fois les dépendances séquentielles (quelles compétences suivent d'autres) et les relations hiérarchiques (compétences composées de sous-compétences).
Applications et importance
CST a été appliqué dans les domaines de l'apprentissage robotique, où les démonstrations d'opérateurs humains ou de téléopération sont utilisées pour amorcer un comportement autonome. Les arbres de compétences résultants permettent un apprentissage plus rapide de nouvelles tâches en réutilisant des compétences précédemment acquises, réduisant le besoin d'exploration extensive.
L'algorithme contribue au domaine plus large de l'apprentissage par renforcement hiérarchique, qui vise à décomposer des tâches complexes en sous-problèmes gérables. Contrairement à certaines méthodes nécessitant des hiérarchies de tâches prédéfinies, CST découvre la structure directement à partir des données, ce qui le rend adapté aux domaines où la décomposition manuelle est impraticable.
La nature en ligne de CST le distingue des algorithmes par lots, lui permettant de s'adapter à mesure que de nouvelles démonstrations arrivent. Cette propriété est précieuse dans les scénarios d'apprentissage interactif où un robot ou un agent reçoit un retour incrémental. L'utilisation de la détection de points de changement bayésienne fournit un moyen fondé d'équilibrer la complexité du modèle contre la qualité de l'ajustement, évitant la sur-segmentation.
Concepts connexes
CST est lié à d'autres approches en apprentissage automatique et apprentissage par renforcement qui exploitent les démonstrations, telles que apprentissage curriculaire qui structure la formation progressivement. L'utilisation de modèles statistiques par l'algorithme se connecte à des travaux plus larges en inférence bayésienne et en analyse de séries temporelles. Dans le contexte de l'intelligence artificielle moderne, l'idée de décomposition hiérarchique de CST résonne avec les architectures de apprentissage profond qui apprennent des représentations en couches, bien que CST opère sur des abstractions de compétences symboliques plutôt que sur des données sensorielles brutes.
La recherche sur la découverte de compétences continue dans des domaines comme la robotique et les agents autonomes, où la réutilisation efficace des comportements appris est critique. L'accent de CST sur l'apprentissage en ligne et incrémental s'aligne avec les tendances vers les systèmes d'apprentissage tout au long de la vie qui s'adaptent continuellement. Bien que non directement lié à la recherche sur les grands modèles de langage, le principe de construction de composants réutilisables à partir de démonstrations a des parallèles dans l'ingénierie de prompts et l'utilisation d'outils dans les systèmes d'IA modernes.
Limitations et extensions
L'algorithme CST original suppose l'accès aux signaux de récompense pendant la démonstration, ce qui peut ne pas toujours être disponible. Des extensions ont exploré l'utilisation de critères de segmentation alternatifs lorsque les récompenses sont rares. Le modèle de régression linéaire limite la complexité des compétences qui peuvent être représentées, bien que le cadre puisse accommoder des modèles non linéaires avec des modifications appropriées.
Le filtre particulaire introduit des erreurs d'approximation, et le choix de la fonction de hasard affecte la granularité de la segmentation. Les chercheurs ont étudié des paramètres adaptatifs pour améliorer la robustesse à travers différents domaines de tâches. Malgré ces limitations, CST reste une contribution fondamentale à l'apprentissage hiérarchique de compétences, influençant les travaux ultérieurs sur la découverte d'options et l'abstraction hiérarchique dans l'apprentissage par renforcement.