Construindo árvores de habilidades (CST) é um algoritmo de aprendizado por reforço hierárquico que constrói automaticamente árvores de habilidades a partir de um conjunto de trajetórias de solução de amostra obtidas por demonstração. Foi introduzido por George Konidaris, Scott Kuindersma, Andrew Barto e Roderic Grupen em 2010. O algoritmo identifica sub-habilidades reutilizáveis dentro de comportamentos demonstrados e as organiza em uma estrutura de árvore, permitindo que um agente resolva novas tarefas de forma mais eficiente ao reutilizar componentes aprendidos.
O CST opera segmentando cada trajetória de demonstração em habilidades discretas usando um algoritmo incremental de detecção de ponto de mudança máximo a posteriori (MAP). Essas habilidades são então alinhadas e mescladas entre trajetórias para formar uma árvore de habilidades, onde cada nó representa uma habilidade e as arestas indicam relações temporais ou hierárquicas. A abordagem é projetada para funcionar online, processando demonstrações incrementalmente sem exigir que todos os dados estejam disponíveis antecipadamente.
Visão Geral do Algoritmo
O algoritmo CST consiste em três componentes principais: detecção de ponto de mudança, alinhamento e mesclagem. O foco central é a detecção online de ponto de mudança, que segmenta dados em habilidades usando a soma da recompensa descontada como a variável alvo de regressão. Cada habilidade detectada recebe uma abstração apropriada, e um filtro de partículas controla a complexidade computacional.
O algoritmo de detecção de ponto de mudança processa dados para tempos t em T, dado um conjunto de modelos Q com probabilidades a priori p(q). Ele ajusta segmentos do tempo j+1 ao t usando o modelo q, calculando uma probabilidade de ajuste P(j,t,q) com base em um modelo de regressão linear com ruído gaussiano. A priori do ruído tem média zero e variância seguindo uma distribuição InverseGamma, enquanto cada priori de peso segue uma distribuição Normal.
A probabilidade de ajuste é calculada usando uma fórmula específica envolvendo determinantes de matrizes e funções gama. O CST então calcula a probabilidade de um ponto de mudança no tempo j com o modelo q usando um algoritmo de Viterbi, incorporando uma função de risco g e sua distribuição cumulativa G para modelar comprimentos de segmentos.
Detalhes da Detecção de Ponto de Mudança
Para cada ponto de mudança potencial, o CST calcula P_t(j,q) como o produto da probabilidade de sobrevivência, probabilidade de ajuste, priori do modelo e a probabilidade MAP no tempo j. A probabilidade MAP P_j^MAP é determinada maximizando sobre pontos de mudança e modelos anteriores, ponderados pela função de risco. Esta formulação recursiva permite processamento online eficiente.
O modelo de regressão usa recompensa descontada como a variável alvo, permitindo que o algoritmo se concentre em habilidades que levam a recompensas cumulativas mais altas. O filtro de partículas mantém um conjunto de pontos de mudança candidatos, mantendo o custo computacional gerenciável mesmo com trajetórias longas.
Alinhamento e Mesclagem de Habilidades
Após a detecção de ponto de mudança, o CST alinha habilidades entre diferentes trajetórias de demonstração. Habilidades que exibem padrões temporais e dinâmicas de recompensa semelhantes são agrupadas. O processo de alinhamento usa os parâmetros de regressão ajustados para corresponder segmentos que provavelmente representam a mesma habilidade subjacente.
A mesclagem então integra habilidades alinhadas na árvore de habilidades. Quando múltiplas demonstrações contêm habilidades semelhantes, elas são combinadas em um único nó com estatísticas associadas. A estrutura da árvore captura tanto dependências sequenciais (quais habilidades seguem outras) quanto relações hierárquicas (habilidades compostas de sub-habilidades).
Aplicações e Significância
O CST foi aplicado em domínios de aprendizado de robôs, onde demonstrações de operadores humanos ou teleoperação são usadas para inicializar comportamento autônomo. As árvores de habilidades resultantes permitem aprendizado mais rápido de novas tarefas ao reutilizar habilidades previamente adquiridas, reduzindo a necessidade de exploração extensiva.
O algoritmo contribui para o campo mais amplo de aprendizado por reforço hierárquico, que visa decompor tarefas complexas em subproblemas gerenciáveis. Ao contrário de alguns métodos que exigem hierarquias de tarefas predefinidas, o CST descobre estrutura diretamente dos dados, tornando-o adequado para domínios onde a decomposição manual é impraticável.
A natureza online do CST o distingue de algoritmos em lote, permitindo que ele se adapte à medida que novas demonstrações chegam. Esta propriedade é valiosa em cenários de aprendizado interativo onde um robô ou agente recebe feedback incremental. O uso de detecção bayesiana de ponto de mudança fornece uma maneira fundamentada de equilibrar complexidade do modelo contra qualidade do ajuste, evitando super-segmentação.
Conceitos Relacionados
O CST está relacionado a outras abordagens em aprendizado de máquina e aprendizado por reforço que aproveitam demonstrações, como aprendizado curricular que estrutura o treinamento progressivamente. O uso de modelos estatísticos pelo algoritmo conecta-se a trabalhos mais amplos em inferência bayesiana e análise de séries temporais. No contexto da inteligência artificial moderna, a ideia de decomposição hierárquica do CST ressoa com arquiteturas de aprendizado profundo que aprendem representações em camadas, embora o CST opere em abstrações de habilidades simbólicas em vez de dados sensoriais brutos.
A pesquisa sobre descoberta de habilidades continua em áreas como robótica e agentes autônomos, onde a reutilização eficiente de comportamentos aprendidos é crítica. O foco do CST em aprendizado online e incremental alinha-se com tendências em direção a sistemas de aprendizado ao longo da vida que se adaptam continuamente. Embora não esteja diretamente ligado à pesquisa de modelos de linguagem grandes, o princípio de construir componentes reutilizáveis a partir de demonstrações tem paralelos na engenharia de prompts e no uso de ferramentas em sistemas modernos de IA.
Limitações e Extensões
O algoritmo CST original assume acesso a sinais de recompensa durante a demonstração, o que pode nem sempre estar disponível. Extensões exploraram o uso de critérios alternativos de segmentação quando as recompensas são esparsas. O modelo de regressão linear limita a complexidade das habilidades que podem ser representadas, embora a estrutura possa acomodar modelos não lineares com modificações apropriadas.
O filtro de partículas introduz erros de aproximação, e a escolha da função de risco afeta a granularidade da segmentação. Pesquisadores investigaram configurações adaptativas de parâmetros para melhorar a robustez em diferentes domínios de tarefas. Apesar dessas limitações, o CST permanece uma contribuição fundamental para o aprendizado hierárquico de habilidades, influenciando trabalhos subsequentes sobre descoberta de opções e abstração hierárquica em aprendizado por reforço.