Embedded representation of genetic programming trees

Abstract

Aprendizado de representações é uma área que investiga formas de representações de dados que facilitem para os algoritmos de aprendizado de máquina extraírem informações úteis deles. O aprendizado profundo atualmente possui os métodos mais eficazes para essa tarefa e pode aprender representações vetoriais reais - também conhecidas como embeddings - capazes de representar diferentes propriedades dos dados e suas relações. Nessa direção, este trabalho introduz uma nova maneira de visualizar indivíduos de programação genética (GP) em formato de árvore para regressão simbólica. A Programação Genética é um ramo da computação evolucionária onde os indivíduos são gerados para representar estruturas gerais, também conhecidas como programas. Quando essas estruturas são usadas em regressão simbólica, os indivíduos geralmente são representados por árvores, onde cada árvore é mapeada para uma função matemática. Como em qualquer tarefa de regressão, o objetivo da regressão simbólica é encontrar a função $f$ que mapeia o conjunto de variáveis que descrevem um exemplo de dados para um valor real y pertencente aos números reais. Assim como em outros algoritmos evolucionários, os GPs exploram o espaço de busca de funções $f$ usando os princípios da evolução e sobrevivência do mais apto. Primeiro, cada solução é avaliada para medir sua capacidade de resolver o problema, gerando o valor da função de aptidão (fitness). A aptidão é então usada em um processo probabilístico de seleção de indivíduos. Em seguida, os indivíduos selecionados passam por operações de cruzamento e mutação. Nos GPs baseados em árvores, é sabido que as operações genéticas acabam sendo restritas pela sintaxe e na maioria das vezes não há garantia de que o resultado das operações de cruzamento seja significativo ou apenas equivalente a uma mutação. Há muitas tentativas de levar a semântica em consideração nesse tipo de algoritmo, mas as abordagens propostas até agora não alteram as próprias representações individuais para tentar aproveitar a robustez fornecida pelos embeddings. Motivados por isso, dado um conjunto de operadores predefinidos usados para gerar as soluções para o problema (funções) representadas por árvores e um número suficientemente grande de árvores amostradas do espaço, treinamos um transformer para aprender uma função de codificação/decodificação. Ao transformar uma representação de árvore em uma representação vetorial numérica, somos capazes de medir distâncias entre árvores de maneira muito mais eficiente e, mais importante, gerar o potencial para que essas representações capturem semântica. Mostramos que a distância considerando o embedding apresenta resultados muito semelhantes aos de uma distância de edição de árvore, o que reflete sua similaridade sintática. Embora o modelo ainda não possa capturar a semântica, mostramos seu potencial usando o modelo de representação de árvore gerado em tarefas simples: medindo distâncias entre árvores em um cenário de fitness sharing, onde a diversidade é a propriedade desejável e pode ser medida considerando distâncias entre árvores, e gerando visualizações das árvores dentro de uma população evoluída.