Redes Neurais e algoritmos genéticos - Joguinhos simples
Olá, vou abordar neste post, uma das questões que gosto bastante quando o assunto é IA. Os tais joguinhos simples que funcionam com inteligência artifical atravéz de uma rede neural. Abordrei alguns aspéctos justamente por não ser especialista na área, então será um breve resumo e mostrarei um jogo que fiz em Python que usa esses conceitos. |
Redes Neurais
Antes de começar, vamos entender como funciona uma rede neural? uma rede neural ou rede neural artificial (RNA) são camadas de um sistema artificial que busca agir e replicar de forma similar o funcionamento do cerébro humano, no que se refere ao comportamento do processo de interceptação de informações entre os nossos neurônios. Em suma, as redes neurais buscam emular matematicamente o comportamento da transação das informações interceptados pela cadeia de neurônios do cerébro humano.
As redes neurais são um subconjunto da área de Machine Learning (aprendizado de máquina), dentro do contexto de Deep Learning (Aprendizado profundo). Sendo compostas por camandas e nós, sempre possuindo uma camada de entrada, camadas ocultas e uma saída, com seus neurônios e diferentes limites e pesos acossiados.
Opa opa opa, limites e pesos? como assim?.
Nossas entradas não são infinitas, e cada entrada possui um determinado peso, nem todas as entradas tem a mesma importância, logo damos pesos a elas para que possamos aprimorar o RNA. No caso de RNAs em que não sabemos quais pesos são mais importantes que outros, já que a priori, não sabemos qual RNA é o ideal, temos que dar pesos aleatórios de acordo com a progressão no nosso RNA.
Ah então é assim que uma rede neural aprende?
Não exatamente, redes neurais aprendem atrávez de tentativa e erro, necessitando de um validador externo de suas saídas, mas como não sabemos qual o melhor resultado, temos sempre que usar uma aproximação, e ficar comparando as saídas do RNA, existem estratégias para fazer isso na propria RNA, uma delas é o Backpropagation, mas para explicar ela temos que falar da Feedforward antes.
Uma RNA Feedforward, os caminhos das camadas seguem a mesma direção, onde não existem caminho de volta, logo a rede é linear. Já em uma RNA Backpropagation, a saída é validada por um outro algoritmo que corrige os erros da saída e altera os pesos em todas as camadas, sendo necessário supervisionamento para validar se a saída está errada ou não.
Não entendi!
Bom o computador não age por si só, ele não é inteligente, logo, se queremos que ele tome uma decisão, devemos "estimular" um comportamento padrão, do contrário ou ele não agiria, ou teria um comportamento imprevisível. Tal estímulo é chamado de "Bias" (Viés), que adicionamos junto como um valor de input do nosso RNA, normalmente sendo um valor positivo de “1.0”, já que queremos que o nosso RNA sempre tenha tendencias a agir.
Calma, a imagem acima representa de forma abstrata uma RNA, mas é possivel resumir ela de forma matemática, onde:
- 𝑥 é o nosso input
- 𝑤 os nossos pesos que tamos a cada input
- ∑ é onde parte da mágica acontece, onde devemos somar todos as nossas entradas e seus pesos previamente calculados, resultando em um valor y
- ƒ(y) é nossa função de ativação, é onde a mágica acontece, a função de ativação serve apra limitar a saída da rede neural.
Desta forma, uma RNA é matemáricamente dada por uma equação onde um dado yj é:
∑𝑛 𝑤ij𝑥i + bj ou ∑𝑛 𝑤ij𝑥i
𝑖=1 𝑖=0
Ué, 2 formulas?, não...apenas uma, é que em alguns casos podemos escolher o nosso bias como sendo o nosso indice 0 da equação, logo ele apresenta pesos também.
Certo e a função de ativação?, a função de ativação sendo o nosso ƒ(y) é uma formula em que temos 2 resultados, se nosso y for maior ou igual a 0, então a função de ativação retorna 1, se o contrário então retorna 0. Existem algumas funções de ativação que podemos ter 1 se maior que 0 e 0 se menor ou igual a 0, há uma terceira alternativa com -1 por exemplo, mas não vem ao caso. Normalmente a função de ativação é representada por 𝝋, o papel da função de ativação é limitar nossa saída a um valor que podemos usar para a tomada de decisão no nosso exemplo.
Algumas funções de ativação são:
- A Degrau, função linear com 𝝋(y) = { 1 se y ≥ 0 e 0 se y < 0 }
- A Degrau Bipolar, função linear com 𝝋(y) = { 1 se y > 0; -1 se y < 0; 0 se y = 0 }
- A Sigmoid, função não linear que é uma curva em s que limita a saída entre 0 e 1 com 𝝋(y):
E se y for menor que 0?, então removemos o "-y" da potencia, dexamos apenas o "y", e adicionamos 1 - 𝝋(y). Já que isso evita erros no computador.
Certo, e como sabemos qual decisão tomar?
Simples, podemos escolher que se o resultado não for 0, o nosso RNA toma a decisão positiva, caso contrário ele não faz nada, no caso da sigmoid podemos escolher como positivo se o resultado for maior que 0.5.
E esse "J", quem é ele? ele é o elemento da camada oculta, lembra da imagem anterior? vamos decompor ela melhor, vamos assumir que "i" seja o indíce, e j seja o o Neurônio Intermediário superior e k o Neurônio Intermediário inferior. Em uma Rede Neural de 3 camadas, teremos a camada de Input dado pelos x's, a camada oculta dada pelos w's e p's e a camada de saída dada pela função de ativação resultante. Nesta nossa rede teremos um Neurônio de saída, o resto não conta pois é a nossa Hidden Layer (Camada Oculta).
Então vamos seguir o básico, um valor X é multiplicado por um peso W e atribuido ao P, que é a combinação de todos os X com os W que vão para aquele P. Em seguida após a combinação, o resultado de P é multiplicado por um peso W gerando um Y, Y que é usado na função de ativação. Desta forma, determina a saída da nossa RNA, assim é uma Rede Feedforward.
Ah, então se eu tiver mais saídas, mais neuronios eu preciso? sim! no nosso exemplo cada decisão importante precisa ter um Neurônio específico para ela. Mas existem limites para quantos neuronios podemos usar em determinada quantidade de entradas, já que a nossa Hidden Layer precisa necessáriamente ser maior que a quantidade de Neurônios da Rede.
Certo então como treinar essa RNA? bom, usaremos um algoritmo genético.
Algoritmo Genético
Os algoritmos genéticos (AG) são uma das partes mais simples da área de ciência de dados aplicados a IA, eles replicam o comportamento evolutivo da seleção natural de passar os melhores genes adiante para uma dada população que sobreviva. Basicamente é uma técnica de usada para buscar os melhores indivíduos (aqueles que atendam o objetivo ou que sobrevivam por mais tempo) de uma população com base em um genoma que identifique cada indivíduo do algorítmo.
Todo AG tem uma representação “genética” que irá ser o “cromossomo” de um indivídio e uma função "Fitness" ou Ranking, (um objetivo a ser alcançado, como uma pontuação por exemplo, aqueles que atingirem a maior pontuação são os que serão passados adiante).
Os AG's devem possuir os seguintes funções e parametros:
- Inicialização: O Start-up da população, onde devemos gerar n indivíduos para compor uma população aleatória inicial, sempre sendo um numero finito para que cada geração tenha o mesmo tamanho.
- Indivíduo: O indivíduo nada mais é que um portador do genoma, ele que irá carregar o código genético que identificará o mesmo.
- Seleção : A forma de selecionar o melhor ou melhores indivíduos dessa população.
- Reprodução / Operador genético: A forma como tais indivíduos selecionados irão passar o seu código genético adiante para uma nova população, em alguns casos é feita a combinação dos genomas dos pais para gerar um novo indivíduo com parte de ambos, em outros pode ser por mutações do genoma, também é possível usar as duas estratégias juntas.
- Mutação: A mutação é feita de forma aleatória, através de uma percentagem, isto é, ao gerarmos novos indivíduos para uma nova população, podemos por exemplo colocar uma taxa de 25% de que ocorra uma mutação no genoma de um indivíduo já existente, assim, ao recomeçar o algoritmo, podemos manter os antigos individos inicialmente gerados ou criar uma mutação em um ou mais valores de seu cromossomo. É possivel também usar da clonagem do melhor indivíduo e combinar a mutação para criar variações do melhor da primeira geração e ir replicando até as seguintes, fazendo com que apenas a primeira leva seja de indivíduos completamente aleatórios.
- Reprodução: A reprodução é feita atravez de selecionar 2 indivíduos que serão os pais, e então pegar metade do genoma de um e metade do outro, combinar-los e gerar um novo cromossomo que terá parte dos valores de ambos.
- Geração: Em algoritmos genéticos é importante saber em qual geração da população estamos, assim é possivel observar o desempenho da população e em quantas gerações aproximadamente os indivíduos com os melhores genomas surgem.
- Função-Objetivo: A função objetivo do algoritmo, o que determina o ranking dos indivídos, entre os melhores e piores, normalmente desconhecemos a função objetivo, sendo ela a necessidade do AG de solucionar o problema, é ela que atribui a importância ao Fitness.
É possivel representar um cromossomo de um AG como uma lista de valores binários, algo como:
[ 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1 ]
Mas isso não ajudaria no nosso modelo atual, afinal os pesos de uma rede neural não podem ser representados como “Zeros” e “Ums”, então vamos usar um dicionário e substituir os 1 e 0 para pontos flutuantes. Criaremos um dicionário com os seguintes parametros:
cromossomo = {
'GN01': 0, 'GN02': 0,
'GN11': 0, 'GN12': 0,
'GN21': 0, 'GN22': 0,
'GN31': 0, 'GN32': 0,
'GN41': 0, 'GN42': 0,
'GF01': 0, 'GF11': 0,
'GF02': 0, 'GF12': 0,
'GF21': 0, 'GF22': 0
}
Não se preocupe, pois os nomes são importantes para identificarmos um determinado valor dentro do genoma. Agora, atribuiremos alguns valores para esse genoma, para facilitar vou arredondar os valores:
cromossomo = {
'GN01': -0.598, 'GN02': 0.893,
'GN11': -0.008, 'GN12': 0.305,
'GN21': -0.951, 'GN22': -0.555,
'GN31': -0.695, 'GN32': 0.108,
'GN41': -0.413, 'GN42': 0.647,
'GF01': -0.443, 'GF11': 0.574,
'GF02': -0.451, 'GF12': -0.653,
'GF21': 0.996, 'GF22': -0.324
}
Certo, então como vamos usar ela junto com a RNA? simples, lembra que não sabemos os pesos ideais para a nossa RNA e que não vamos usar o Backprogation para descobrir? com o algoritmo genético a função objetivo será determinar os melhores pesos para obtermos o melhor resultado. Desta forma unindo o AG com o RNA nós podemos criar indivídos que terão uma RNA que irão compor uma população, e com o passar das gerações, poderemos observar os melhores indivíduos que melhor atingem o objetivo do nosso RNA.
Logo, os melhores pesos do RNA estarão diretamente ligados aos melhores indivíduos, a melhor forma de fazer isso, é usar o proprio genoma dos indivíduos como pesos para cada RNA, por isso criamos um dicionário com valores não binários para treinar nossa RNA FeedForward.
Interessante né? mas como aplicar isso em um jogo simples?. É facil, vamos usar o joguinho do dinossauro do google para entender.
Quem usava o Navegador Google Chorme e ficou sem internet em algum momento, já se deparou com o joguinho do dinossauro do google, nele você tem que pular ou abaixar para evitar ser atingido pelos obstaculos enquanto a velocidade aumenta conforme vai avançando, existe uma pontuação que representa a distância já percorrida.
O jogo começa com poucos obstaculos com o dinossauro correndo automaticamente e a pontuação vai incrementando conforme o jogador vai sobrevivendo por mais tempo, esse é o objetivo do dinossauro, logo essa é nossa função-objetivo, atingir a maior pontuação. | |
Vai surgindo obstaculos que se tocarem no jogador, é Game Over, desta forma o dino precisa usar a ação de pular na hora certa para sobreviver a um obstáculo. Logo essa é uma Ação que o jogador pode fazer, entretanto não adianta ficar pulando muito longe do obstaculo pois isso pode ocasionar em um erro do jogador e ele ser atingido. | |
O Jogador também pode executar a Ação de abaixar, mas se essa ação for executada em determinados obstaculos o jogador pode acabar perdendo também se ele se abaixar em um obstáculo que não permite esse tipo de ação. | |
Os Pterodáctilos que aparecem podem vir a uma determinada altura do chão, logo é nesse momento que o jogador usa o "Abaixar", já que se ele usar o pulo ele pode atingir esse obstaculo a uma certa altura. |
Então o que podemos entender com isso? vamos detalhar.
- O Jogador possui duas ações possiveis
- Pular
- Abaixar
- Existem obstaculos que se estiverem a uma determinada altura e distância, uma ação errada pode impactar em Game Over.
- Pular somente quando o obstáculo estiver a uma certa altura do solo.
- Abaixar somente quando o obstáculo estiver a uma certa altura do solo.
- A distância entre o obstáculo o o jogador é fundamental para a ação ser executada corretamente.
- A velocidade com a qual o mapa se move, já que essa vai aumentando conforme vai sendo avançado.
Com isso tempos as seguintes entradas para os valores de Inputs para a rede neural.
- X0 → BIAS (Com valor "1" para que o nosso algorítmo tenha a tendência a tomar ação)
- X1 → Velocidade do jogo.
- X2 → Altura do obstáculo para o solo.
- X3 → Distância do obstáculo para o jogador.
Com as seguintes sáidas para a decisão:
- f(y) → Pular
- f(y) → Abaixar
- * f(y) → Não fazer nada?
* A opção de não fazer nada é caso padrão, logo ela não entra como uma decisão já que ela é a ausencia da decisão de Pular e Abaixar.
Desta forma a rede neural fica parecido com essa imagem:
Definindo os pesos
Como não sabemos quais os pesos que iremos usar, podemos usar o algoritmo genético para gerar N indivíduos com um genoma de valores aleatórios que serão os pesos da nossa rede neural, no nosso exemplo, podemos criar um genoma qualquer aleatório para cada indivíduo. Vamos exemplificar usando o cromossomo anterior:
|
O nosso genoma é um dicionário de chave-valor, com cada chave representando um valor específico de peso, imagine que cada indivíduo terá valores específicos e aleatórios da primeira população de N indivíduos, para facilitar chamamos os valores de genes que serão pesos "W" que vamos usar nos neurônios como "GN" e os que serão pesos da camada oculta para a função de ativação como "GF".
Espere, se cada chave do gene representa um peso W que vai ser aplicado ao input, não deveria ter 6 “GN's” ao invéz de 8 e 4 "GF's"?
Os pesos extras, são justamente aplicados ao nosso BIAS, que é um valor estático e constante, como queremos sempre que o nosso algorítmo tome uma decisão de ação, usamos o BIAS junto com os nossos pesos, neste exemplo foi optado por aplicar o BIAS tanto na camada exterior quanto na oculta para influenciar o resultado.
Pesos nas Matrizes
Matrizes? Sim, se olharmos com atenção a função da RNA:
∑𝑛 𝑤ij𝑥i + bj ou ∑𝑛 𝑤ij𝑥i
𝑖=1 𝑖=0
Percebemos que isso nada mais é que uma multiplicação de matrizes, com o 𝑤ij Sendo uma posição em uma matriz e o 𝑥i um valor que multiplicará a esse valor. Além disso, se formos descrever cada valor manualmente, essa comparação ficaria mais clara, mas para explicar melhor, vamos destrinchar os Inputs e Pesos.
Sabemos quais são os nossos inputs e outputs que nosso algoritmo deve ler e executar, agora para definir os pesos ideais vamos usar o algorítmo genético para para criar uma população, desta população cada genoma do indivíduo será os pesos que irão na rede neural. Como temos 4 inputs (Que inclui o BIAS), vemos que a primeira camada de pesos do genoma deve ter 8 Valores, vamos explicar com as matrizes. A matriz de entradas como sendo uma matriz vertical e a matriz de pesos como uma matriz horizontal:
Matriz de Entradas | Sua representação em Linguagem de Programação. |
|
Matriz de Pesos | Sua representação em Linguagem de Programação. |
|
Agora devemos fazer a multiplicação de matrizes para resultar em uma nova matriz, para isso o numero de colunas da matriz A deve ser igual ao numero de linhas da matriz B. Logo, a matriz A será a matriz de pesos que tem 4 colunas (2x4), e a matriz B a nossa matriz de entradas que possui 4 linhas, (4x1), isso resultará em uma nova matriz C de 2 linhas e uma coluna (2x1), isso porque devemos usar o somatório dos resultados para gerar o valor final.
Então a nova matriz resultante “C” pode ser representada como a camada oculta dos nossos neurônios da rede neural, se percebermos bem, a matriz resultante tem exatamente 2 elementos, que correspondem a cada ação que será executada, um para o pulo, e outra para abaixar.
Matriz C resultante (Camada oculta) | Sua representação em Linguagem de Programação. |
|
Agora que temos a camada oculta de valores, vamos inserir novamente o BIAS como mais uma linha e multiplicar com os outros pesos (É possivel aplicar uma função de ativação após inserir o BIAS para dar uma reduzida nos valores).
Matriz de Entradas (Camada oculta) | Sua representação em Linguagem de Programação. |
|
Matriz de Pesos | Sua representação em Linguagem de Programação. |
|
Executando o mesmo procedimento de multiplicação e anterior, teremos a seguinte resultante. A qual chamaremos de matriz "S", que é a matriz de saída dos valores, ela possui 2 valores com cada um representando uma ação do nosso personagem. :
Agora finalizando o nosso algoritmo, vamos aplicar para cada um dos valores resultades da Matriz S uma função de ativação, neste exemplo vamos usar a função Sigmoid. Basicamente vamos pegar a saída do Sigmoid para cada um dos elementos da matriz, e aplicar o famoso if (Olha o if-else da IA aí). Como queremos que o nosso personagem tome uma decisão, vamos fazer o seguinte, se a saida for maior que 0.5 aquela ação será tomada, se não ele não toma essa ação, por exemplo:
Matriz S resultante (Saída) | Sua representação em Linguagem de Programação. |
|
Finalmente temos as ações que o jogador pode tomar, agora para selecionar o melhor indivíduo de N, vamos pegar somente aquele que tiver a alcançado a melhor pontuação (sobreviveu mais tempo), desta forma usaremos o genoma aleatório deste cara para gerar uma nova geração. Isso pode ser feito pegando esse indivíduo e clonando ele até N indivíduos e aplicando "mutações" no código genetico deles (gerando valores aleatórios em uma parte aleatória do genoma) para que possam se basear em alguns de seus pesos existentes, mas também terem os seus proprios e ir treinando eles como sendo a proxima geração.
Primeira população
Como vamos usar o AG, a primeira população será, por definição, a que terá os valores 100% aleatórios no genoma, desta forma a primeira geração será a unica que terá essa característica, todas as gerações subsequentes, ou serão clones com mutações do melhor indivíduo, ou serão uma mescla dos melhores indivíduos, ou será composta por uma parcela de clones, uma parcela de reprodução e uma parcela de aleatórios.
No nosso exemplo, a população inicial será de N indivíduos com genoma aleatório e quando essa geração terminar, vamos pegar o melhor indivíduo e clonar ele em novos N indivíduos e aplicar uma tecnica de taxa de mutação com um pouco de aleatóriedade.
Mutação
Vamos exemplificar com um algoritmo, nesse algoritmo temos 3 fatores, o cromossomo do indivíduo, a taxa de mutação e se será randômico ou não, caso seja randomico ele vai simpliemente gerar um novo valor para um gene (Chave) aleatório do cromossomo, se não ele vai pegar um gene existente e aplicar uma "mutação", fica a seu critério o tipo de mutação a ser aplicada, nesse exemplo eu coloquei alguns calculos, mas não é necessário tudo isso.
|
Assim, temos a função que será responstável por fazer a mutação de cada "Clone" do melhor indíviduo de cada geração. A Taxa de mutação vai determinar quantos genes serão alterados, se for 100% todos os genes vão ser alterados, então dependendo da construção do algoritmo, e do que vai ser treinado. Uma taxa muito alta, pode fazer com que uma população seja cheia de indivíduos que não serão mais clones do melhor e que podem não atender ao objetivo do algoritmo genético, criando uma geração inútil, sendo o ideal, usar uma proporção de entorno de 10% à 30% de mutação para não mudar muito o genoma dos indivíduos para seleção.
No nosso exemplo usarei uma taxa de 25% por considerar a taxa ideal de genes que podem ter mutação, já que o nosso cromossomo é bem pequeno e não teremos uma população tão grande (apenas 50 indivíduos) e o randomize como “Verdadeiro” para que ele gere um valor aleatório sempre nesses genes que forem alterados.
Exemplo de Rede Neural Artificial com Algoritmo Genético
Nada melhor que um exemplo prático do funcionamento, que tal esse exemplo com um joguinho simples feito por mim na faculdade, usei alguns sprites de um alien do Metal Slug e uns sprites de solo que peguei da internet, segue alguns pontos.
- Nesse jogo o objetivo é coletar o máximo de moedas
- O jogador morre toda vez que tocar em um obstáculo
- O jogador não pode ignorar as moedas, se ele ignorar o raio da morte vai se aproximando dele até mata-lo (Condição criada para impedir da IA ignorar as moedas para se manter somente desviando).
- O jogador possui uma sombra com a qual ele pode inverter de posição com ela, já que existem obstáculos que são impossiveis de pular por serem muito largos.
- A velocidade do mapa vai aumentando conforme avança no game.
- O jogo permite que você jogue ele se selecionar o modo de jogador ao invéz de IA.
Para os sensores, temos os seguintes:
- A distância entre o obstáculo e a sombra
- A distância entre o obstáculo e o jogador
- A largura do obstáculo
- A velocidade do mapa.
Game com Sprites | Apenas a visualização sem os sprites |
É um game bastante interessante que fiz no tempo livre como um projeto da faculdade, não é 100% e não deve ser usado como parâmetro de qualidade, mas é algo que me diverte.
Como é possivel ver, eu me inspirei bastante no jogo do dinossauro do google, mas adicionei uns toques a mais para dificultar a rede neural.
Segue o video do treinamento com o passar das gerações.
O projeto está no Github: https://github.com/clebsonluiz/UAST-2020.1-REC-PAD
Espero que tenham gostado, até a proxíma :)