NEAT: uma abordagem incrível para NeuroEvolution

O NeuroEvolution pode otimizar e evoluir a estrutura da rede neural, e o algoritmo NEAT foi um dos primeiros a mostrar isso como uma abordagem viável!

Hunter Heidenreich Blocked Desbloquear Seguir Seguindo 3 de janeiro

Um mundo de neuroevolução

Recentemente, tenho lido muito sobre algo chamado neuroevolução. Em alto nível, a ideia é muito simples. Em vez de confiar em uma estrutura fixa para uma rede neural, por que não permitir que ela evolua por meio de um algoritmo genético? Para mim, isso faz muito sentido. Normalmente, quando se utiliza uma rede neural, seleciona-se uma estrutura que pode funcionar com base em evidências empíricas. Mas é a melhor estrutura que pode ser usada? Não há como saber com certeza.

Na minha leitura, me deparei com um artigo chamado Evoluindo Redes Neurais através do Levantamento de Topologias que discute o algoritmo NeuroEvolução de Topologias Aumentantes, mais comumente conhecido simplesmente como NEAT. Embora o artigo tenha sido lançado em 2002 e focado apenas na evolução de densas redes neurais, nó por nó e conexão por conexão, este artigo foi um ponto de partida crítico para eu mergulhar na neuroevolução e um artigo que planejo discutir neste artigo!

Agora, você pode estar se perguntando como esse algoritmo ainda pode ser útil se apenas evoluir NNs densos e tiver que evoluir especificamente as conexões entre os nós. Esta foi uma questão que eu estava pensando desde o início também. Mas a questão é que o progresso que fizemos com o treinamento de NNs através da descida de gradiente e da propagação reversa não precisa ser abandonado por um processo neuroevolutivo. De fato, os dois podem ser complementares. Artigos recentes destacaram maneiras de usar algoritmos NEAT e NEAT para evoluir a estrutura da rede neural e, em seguida, usar a propagação reversa e o gradiente descendente para otimizar essas redes, uma área que, acredito, se tornará cada vez mais relevante e importante.

Mas agora, sem mais delongas, NeuroEvolution of Augmenting Topologies:

Os problemas com a neuroevolução para topologias

Antes do NEAT, houve um punhado de tentativas de desenvolver topologias de redes que foram um pouco bem sucedidas, no entanto, eles identificaram uma série de problemas que precisariam ser superados antes que a tecnologia pudesse realmente fazer algo incrivelmente útil. O que tornou a NEAT e seu artigo tão interessantes são algumas das soluções que ela propôs para esses problemas, soluções que ainda hoje tornam este artigo relevante!

Codificação

Em biologia, temos um genótipo e um fenótipo. Um genótipo é a representação genética de uma criatura e o fenótipo é a representação física atualizada da criatura. Os algoritmos evolutivos sempre espelham fortemente a biologia, não sendo a neuroevolução diferente a esse respeito.

A questão da codificação vem da questão de como queremos representar os indivíduos geneticamente em nosso algoritmo. A maneira como codificamos nossos indivíduos estabelece o caminho para como nosso algoritmo lidará com os principais processos evolutivos: seleção, mutação e crossover (também conhecido como recombinação). Qualquer codificação vai cair em uma das duas categorias, direta ou indireta.

Uma codificação direta especificará explicitamente tudo sobre um indivíduo. Se ela representa uma rede neural, isso significa que cada gene estará diretamente ligado a algum nó, conexão ou propriedade da rede. Isso pode ser uma codificação binária de 1s e 0s, uma codificação de gráfico (vinculando vários nós por conexões ponderadas) ou algo ainda mais complexo. O ponto é que sempre haverá uma conexão direta entre genótipo e fenótipo que é muito óbvia e legível.

Uma codificação indireta é exatamente o oposto. Em vez de especificar diretamente como uma estrutura pode parecer, as codificações indiretas tendem a especificar regras ou parâmetros de processos para criar um indivíduo. Como resultado, as codificações indiretas são muito mais compactas. O outro lado é que definir as regras para uma codificação indireta pode resultar em um pesado viés dentro do espaço de pesquisa, portanto, é muito mais difícil criar uma codificação indireta sem conhecimento substancial sobre como a codificação será usada.

O algoritmo NEAT escolhe uma metodologia de codificação direta por causa disso. Sua representação é um pouco mais complexa do que um simples gráfico ou codificação binária, no entanto, ainda é fácil de entender. Simplesmente tem duas listas de genes, uma série de nós e uma série de conexões. Para ver o que isso parece visualmente, tenho uma foto do documento original aqui:

Os nós de entrada e saída não são desenvolvidos na lista de genes do nó. Nós ocultos podem ser adicionados ou removidos. Quanto aos nós de conexão, eles especificam onde a conexão entra e sai, o peso de tal conexão, se a conexão está ou não ativada, e um número de inovação (algo que discutiremos na próxima seção).

Mutação

No NEAT, a mutação pode alterar as conexões existentes ou adicionar nova estrutura a uma rede. Se uma nova conexão for adicionada entre um nó inicial e um nó final, ela será atribuída aleatoriamente a um peso.

Se um novo nó for adicionado, ele será colocado entre dois nós que já estão conectados. A conexão anterior está desativada (embora ainda presente no genoma). O nó inicial anterior é vinculado ao novo nó com o peso da conexão antiga e o novo nó é vinculado ao nó final anterior com um peso de 1. Isso foi encontrado para ajudar a atenuar problemas com novas adições estruturais.

Convenções Concorrentes

Outro grande problema com a evolução das topologias de redes neurais é algo que o jornal da NEAT chama de “convenções concorrentes”. A ideia é que apenas cruzando cegamente os genomas de duas redes neurais poderia resultar em redes terrivelmente mutantes e não funcionais. Se duas redes são dependentes de nós centrais que são recombinados da rede, temos um problema.

Mais do que isso, os genomas podem ser de tamanhos diferentes. Como alinhamos genomas que não parecem ser obviamente compatíveis? Em biologia, isso é resolvido através de uma idéia chamada homologia. Homologia é o alinhamento dos cromossomos com base em genes correspondentes para uma característica específica. Uma vez que isso aconteça, o cruzamento pode acontecer com muito menos chance de erro do que se os cromossomos estivessem cegamente misturados.

NEAT aborda esta questão através do uso de marcas históricas (como visto acima). Marcando novas evoluções com um número histórico, quando chega a hora de cruzar dois indivíduos, isso pode ser feito com muito menos chance de criar indivíduos que não sejam funcionais. Cada gene pode ser alinhado e (potencialmente) cruzado. Cada vez que um novo nó ou novo tipo de conexão ocorre, uma marcação histórica é atribuída, permitindo fácil alinhamento quando se trata de reproduzir dois de nossos indivíduos. Veja isso aqui:

Especiação

Uma ideia muito interessante apresentada no NEAT foi que a maioria das novas evoluções não são boas. De fato, adicionar uma nova conexão ou nó antes que qualquer otimização de pesos tenha ocorrido geralmente leva a um indivíduo com desempenho inferior. Isso coloca novas estruturas em desvantagem. Como podemos proteger novas estruturas e permitir que elas sejam otimizadas antes de eliminá-las da população inteira? NEAT sugere especiação.

A especiação simplesmente divide a população em várias espécies com base na similaridade de topologia e conexões. Se o problema da convenção concorrente ainda existisse, isso seria muito difícil de medir! No entanto, como o NEAT usa marcações históricas em sua codificação, isso se torna muito mais fácil de medir. Uma função para decidir como especular é dada no artigo, mas a parte importante a ser observada é que os indivíduos de uma população só têm que competir com outros indivíduos dentro dessa espécie. Isso permite que novas estruturas sejam criadas e otimizadas sem medo de serem eliminadas antes que possam ser verdadeiramente exploradas.

Mais do que isso, o NEAT dá um passo à frente através de algo chamado compartilhamento explícito de fitness. Isso significa que os indivíduos compartilham o quão bem eles estão fazendo em toda a espécie, aumentando as espécies de maior desempenho, embora ainda permitindo que outras espécies explorem sua otimização de estrutura antes de serem evoluídas.

Estrutura Mínima

Um grande objetivo do documento da NEAT era criar uma estrutura para redes em evolução que permitisse o desenvolvimento de redes mínimas. Os autores não quiseram criar um algoritmo que primeiro encontrasse boas redes e depois reduzisse o número de nós e conexões após o fato. Em vez disso, a ideia era construir um algoritmo que começasse com a quantidade mínima de nós e conexões, evoluindo a complexidade com o passar do tempo se, e somente se, fosse útil e necessário.

O NEAT configura seu algoritmo para desenvolver redes mínimas iniciando todas as redes sem nós ocultos. Cada indivíduo na população inicial é simplesmente nós de entrada, nós de saída e uma série de genes de conexão entre eles. Por si só, isso pode não necessariamente funcionar, mas quando combinado com a idéia de especiação, isso prova ser uma ideia poderosa na evolução de redes mínimas, mas de alto desempenho.

Então, como isso aconteceu?

Em 2002, quando este algoritmo foi proposto, foi uma ideia nova. Eles precisavam provar que poderiam fazer coisas básicas. Uma das primeiras coisas que os autores testaram para provar sua eficácia foi se poderia ou não evoluir a função XOR. Obviamente, de outra forma, provavelmente não estaríamos discutindo o algoritmo.

Outra tarefa que eles demonstraram no NEAT foi a tarefa de controle de balanceamento de polos. Se você não estiver familiarizado, essa é uma tarefa em que há um ambiente simulado no qual um algoritmo de controle pode mover um carrinho. Conectado ao carrinho é um poste. O objetivo do algoritmo de controle é equilibrar esse pólo pelo maior tempo possível. Existem várias variações desta tarefa que também foram avaliadas, como a tarefa de balanceamento de pólo duplo (agora com dois pólos!) E a tarefa de balanceamento de pólo duplo onde o algoritmo de controle não recebe nenhuma informação de velocidade sobre os pólos. O NEAT foi muito bem sucedido com todas as variações desta tarefa!

Empacotando

Então agora você está familiarizado com o algoritmo NEAT para evoluir redes neurais! Espero que, depois de ler este artigo, você pense que é uma abordagem legal para a neuroevolução e veja todas as razões pelas quais foi um grande avanço na neuroevolução.

Mas isso é apenas o começo. Encorajo-vos a ler o artigo, se você quiser mais detalhes sobre o algoritmo (incluindo como eles vão especificamente sobre o processo de especiação), ou melhor ainda, confira um repositório de código em sua linguagem de programação favorita!

Além do NEAT, há mais variações, como HyperNEAT , ES-HyperNEAT e CoDeepNEAT, para citar algumas que espero falar em breve! Todas essas são adições legais no topo do NEAT que eu encorajo você a explorar também.

E como sempre, deixe-me saber se você tiver dúvidas ou se eu perdi alguma coisa! Eu ainda estou aprendendo muito sobre esse conteúdo também e adoraria falar mais sobre isso (você sempre pode me encontrar no Twitter )!

Texto original em inglês.