Aprendizagem de Máquina é Divertido! Parte 2
Usando Aprendizagem de Máquina para gerar níveis de Super Mario Maker
Nota: Este post é a tradução de um artigo por Adam Geitgey, de uma série de artigos originalmente em inglês. Leia a série completa original: Part 1, Part 2, Part 3, Part 4, Part 5, Part 6, Part 7 and Part 8!
Você pode ler em português a Parte 1, Parte 2, Parte 3, Parte 4, Parte 5, Parte 6, Parte 7 e Parte 8.
Na Parte 1, dissemos que Aprendizagem de Máquina é o uso de algoritmos genéricos para descobrir coisas interessantes sobre os seus dados sem ter que escrever nenhum código específico para o problema que você está resolvendo. (Se você ainda não leu a parte 1, leia agora!)
Desta vez, vamos ver um destes algoritmos genéricos fazer algo realmente irado — criar um nível de vídeo game que parece ter sido feito por humanos. Iremos construir uma rede neural, alimentá-la com níveis de Super Mário existentes e observar novos níveis serem criados.
Assim como na Parte 1, este guia é para qualquer um que tenha curiosidade sobre Aprendizagem de Máquina (AM) mas não tem idéia de por onde começar. O objetivo é ser acessível à todos — o que significa que vai haver muita generalização e vamos pular muitos detalhes. Mas quem se importa? Se este artigo fizer com que alguém fique mais interessado em AM, então, missão cumprida.
Fazendo estimativas mais inteligentes
Na Parte 1, criamos um algoritmo simples que estimava o valor de venda de um imóvel baseado nos seus atributos. A partir de dados como por exemplo:
Construimos uma função simples para estimar o valor de venda:
def preco_venda_imovel_estimado(num_quartos, metros, bairro):
price = 0# um pouco disso
price += num_of_bedrooms * 0.123# um bocado daquilo
price += sqft * 0.41# talvez uma pitada disto aqui
price += neighborhood * 0.57return price
Em outras palavras, estimamos o valor do imóvel multiplicando cada um dos seus atributos por um peso. Depois, somamos tudo para obter o valor de venda estimado do imóvel.
Ao invés de mostrar código, vamos representar a mesma função com um diagrama simples:
Este algoritmo, contudo, funciona apenas para problemas simples onde o resultado tem um relacionamento linear com as entradas. E se a verdade por trás do verdadeiro valor de venda não for tão simples? Por exemplo, talvez o bairro tenha mais influência para imóveis grandes e pequenos, mas não seja tão importante para imóveis de tamanho médio. Como podemos capturar este tipo de detalhes complicados no nosso modelo?
Para ser mais inteligente, podemos rodar nosso algoritmo várias vezes com pesos diferentes para capturar vários casos extremos:
Agora temos quatro estimativas de preço diferentes. Vamos combinar estas quatro estimativas em uma estimativa final. Vamos aplicar o mesmo algoritmo novamente (mas utilizando outro conjunto de pesos)!
Nossa nova Super Respota combina as estimativas de quatro tentativas diferentes para resolver o problema. Devido a isto, ela pode modelar mais casos do que capturaríamos com apenas um modelo.
O que é uma Rede Neuronal?
Vamos combinar nossas quatro tentativas de predição em um único grande diagrama:
Isto é uma rede neuronal! Cada nodo sabe como tomar um conjunto de entradas, aplicar pesos a elas, e calcular um valor de saída. Ao encadearmos vários destes nodos, podemos modelar funções complexas.
Estou deixando de fora muita coisa pra manter este texto conciso (por exemplo escalonamento de atributos — feature scaling — e função de ativação — activation function), porém o mais importante é que as seguintes ideias fiquem claras:
- Fizemos uma função de estimativa simples que toma um conjunto de entradas e as multiplica para gerar uma saída. Chame esta função simples de neurônio.
- Ao encadearmos vários neurônios simples, podemos modelar funções que são muito complicadas para ser modeladas por um único neurônio.
É igual ao LEGO! Não se pode modelar muita coisa com apenas um bloco que LEGO, mas podemos modelar qualquer coisa se tivermos um quantidade suficiente de blocos de LEGO à disposição:
Adicionando Memória à nossa Rede Neuronal
A rede neuronal que vimos sempre retorna a mesma resposta quando recebe as mesmas entradas. Ela não tem memória. Em termos de programação, é um algoritmo sem estado ( stateless algorithm).
Em muitos casos (como estimar preço de imóveis), isto é exatamente o que queremos. Porém, uma coisa que este tipo de modelo não faz é responder a padrões nos dados ao longo do tempo.
Imagine que eu lhe entregasse um teclado e pedisse que você escrevesse um texto. Mas antes de começar, vou tentar advinhar a primeira letra que você irá digitar. Qual letra eu deveria chutar?
Eu posso utilizar meu conhecimento da língua para aumentar minhas chances de advinhar a letra correta. Por exemplo, você provavelmente irá digitar a letra que é mais comum no início de palavras. Se eu tiver acesso a outros textos que você escreveu, eu poderia restringir minha escolha às letras que você geralmente utiliza no início de seus textos. Uma vez que eu tenha todo os textos, eu posso utilizá-los para construir uma rede neuronal para modelar a probabilidade de você iniciar com uma letra específica.
Nosso modelo pode ficar assim:
Mas vamos tornar o problema ainda mais difícil. Digamos que eu precise advinhar a próxima letra que você irá digitar a qualquer ponto no texto. Este é um problema muito mais interessante.
Vamos utilizar as primeiras palavras de The Sun Also Rises, de Ernest Hemingway ( “O Sol também se levanta”):
Robert Cohn was once middleweight boxi
Qual letra virá a seguir?
Você provavelmente chutou ‘n’ — a palavra é provavelmente boxing. Sabemos disso baseado nas letras que já vimos na sentença e nosso conhecimento de palavras comuns em Inglês. Além disso, a palavra ‘middleweight’ nos dá uma dica extra de que estamos falando sobre boxe.
Em outras palavras, é fácil advinhar a próxima letra se levarmos em conta a sequencia de letras anteriores combinado com o conhecimento das regras da lingua inglesa.
Para resolver este problema com uma rede neuronal, teremos que adicionar estado ao nosso modelo. Cada vez que consultarmos uma resposta na nossa rede neuronal, vamos também salvar um conjunto de cálculos intermediários e reutilizá-los na próxima vez como parte da entrada. Assim, nosso modelo irá ajustar suas predições de acordo com as entradas recentes.
Manter um registro do estado no modelo possibilita que ele não apenas faça prediçoes sobre a possível primeira letra no texto, mas também predições sobre a mais provável próxima letra dado todas as letras anteriores.
Esta é a idea básica de uma Rede Neuronal Recorrente (Recurrent Neural Network). Atualizamos a rede sempre que a utilizamos. Isto permite atualizar suas predições a partir das entradas mais recentes. Pode-se até mesmo modelar padrões temporais, desde que se tenha memória suficiente.
Para que serve uma única letra?
Predizer a próxima letra em um texto pode parecer bem inútil. Qual é o objetivo?
Uma aplicação interessante pode ser o auto-predict para o teclado do smarphone.
E se levarmos esta ideia ao extremo? E se pedíssemos ao modelo para predizer o próximo caractere várias vezes seguidas — inúmeras vezes? Estaríamos pedindo ao modelo para escrever um texto completo para nós!
Gerando um texto
Nós vimos como prever a próxima letra em uma sentença de Hemingway. Vamos tentar gerar um texto inteiro no estilo Hemingway.
Para tanto, vamos usar a implementação de Redes Neuronais Recorrentes escrita por Andrej Karpathy. Andrej é um pesquisador de Deep Learning em Stanford e escreveu uma excelente introdução à geração de textos com RNRs. Você pode acessar o código para o modelo no github.
Vamos criar nosso modelo a partir do texto completo de O Sol Também se Levanta — 362,239 caracteres usando 84 letras únicas (incluindo pontuação, maíusculas, minúsculas, etc). Este conjunto de dados é de fato bem pequeno se comparado a uma aplicação do mundo real típica. Para gerar um modelo do estilo de Hemingway realmente bom, seria melhor ter muito mais amostras de texto. Mas este texto é bom o suficiente para usarmos como exemplo inicial.
Logo no início do treino, a RNR não é muito boa ao prever letras. Veja o que ela gera após 100 iterações de treinamento:
hjCTCnhoofeoxelif edElobe negnk e iohehasenoldndAmdaI ayio pe e h’e btentmuhgehi bcgdltt. gey heho grpiahe.
Ddelnss.eelaishaner” cot AAfhB ht ltny
ehbih a”on bhnte ectrsnae abeahngy
amo k ns aeo?cdse nh a taei.rairrhelardr er deffijha
Como você pode perceber, ela já descobriu que algumas vezes palavras tem espaço entre elas, e só.
Após cerca de 1000 iterações, as coisas parecem um pouco mais promissoras:
hing soor ither. And the caraos, and the crowebel for figttier and ale the room of me? Streat was not to him Bill-stook of the momansbed mig out ust on the bull, out here. I been soms
inick stalling that aid.
“Hon’t me and acrained on .Hw’s don’t you for the roed,” In’s pair.”
“Alough marith him.”
O modelo começa a identificar os padrões em estruturas básicas das sentenças. Já adiciona ponto ao final das sentenças e até usa aspas para os diálogos. Umas poucas palavras são reconhecíveis, mas ainda há um monte de baboseiras sem sentido.
Depois de muitos milhares de iterações a mais, os resultados já são muito bons:
He went over to the gate of the café. It was like a country bed.
“Do you know it’s been me.”
“Damned us,” Bill said.
“I was dangerous,” I said. “You were she did it and think I would a fine cape you,” I said.
“I can’t look strange in the cab.”
“You know I was this is though,” Brett said.
“It’s a fights no matter?”
“It makes to do it.”
“You make it?”
“Sit down,” I said. “I wish I wasn’t do a little with the man.”
“You found it.”
“I don’t know.”
“You see, I’m sorry of chatches,” Bill said. “You think it’s a friend off back and make you really drunk.”
Neste ponto, o algoritmo já capturou o padrão básico do diálogo curto e direto de Hemingway. Algumas poucas sentenças até chegam a fazer um certo sentido.
Compare com um trecho real do texto do livro:
There were a few people inside at the bar, and outside, alone, sat Harvey Stone. He had a pile of saucers in front of him, and he needed a shave.
“Sit down,” said Harvey, “I’ve been looking for you.”
“What’s the matter?”
“Nothing. Just looking for you.”
“Been out to the races?”
“No. Not since Sunday.”
“What do you hear from the States?”
“Nothing. Absolutely nothing.”
“What’s the matter?”
Mesmo apenas procurando padrões de uma única letra por vez, nosso algoritmo reproduziu prosa que parece plausível depois de uma formatação adequada. Isto é impressionante!
Mas não temos que gerar texto do zero. Podemos alimentar o algoritmo com algumas primeiras letras e deixá-lo descobrir as letras restantes.
Só pro diversão, vamos fazer uma capa falsa para nosso livro imaginário gerando um nome e um título usando como primeiras letras “Er, “He” e “The S”:
Nada mal!
Mas a parte que é realmente de virar a cabeça é que este algoritmo pode identificar padrões em qualquer sequencia de dados. Ele pode gerar receitas que parecem reais, ou discursos falsos do Obama. Mas porquê nos limitarmos a linguagem humana? Podemos aplicar esta mesma ideia a qualquer sequencia de dados onde haja um padrão.
Fazendo Mario sem realmente fazer Mario
Em 2015, a Nintendo lançou Super Mario Maker™ para o Wii U game system.
Este jogo permite que você crie seus próprios níveis de Super Mario Brothers no gamepad e os distribua na internet para que seus amigos possam jogar neles. Você pode incluir todos os power-up clássicos e inimigos dos jogos originais do Mario nos seus níveis. É como um LEGO virtual para pessoas que cresceram jogando Super Mario Brothers.
Podemos usar o mesmo modelo que gerou textos falsos de Hemmingway para gerar níveis de Super Mario Brothers?
Primeiro, precisamos de um conjunto de treinamento para nosso modelo. Vamos usar todos os níveis do Super Mario Brothers original lançado em 1985:
Este jogo em 32 níveis e cerca de 70% dele tem o mesmo estilo externo. Então, vamos nos concentrar nestes.
Para obter os mapas de cada nível, eu peguei uma cópia original do jogo e escrevi um programa para extrair o mapa do nível da memória do computador. Super Mario Bros. é um jogo de 30 anos de idade e há muitos recursos online que ajudam a entender como os níveis são armazenandos na memória do jogo. Extrair dados sobre o nível de um vídeo game antigo é um exercício de programação divertido que você deveria tentar um dia.
Aqui está o primeiro nível do jogo (que você provavelmente lembra, se você já jogou):
Se observarmos bem de perto, podemos ver que o nível é composto de uma grade simples de objetos:
Poderíamos de maneira simples representar esta grade como uma sequencia de caracteres com cada caractere representando um objeto:
--------------------------
--------------------------
--------------------------
#??#----------------------
--------------------------
--------------------------
--------------------------
-##------=--=----------==-
--------==--==--------===-
-------===--===------====-
------====--====----=====-
=========================-Substituimos cada objeto no nível por um caractere:
- ‘-’ é um espaço em branco
- ‘=’ é um bloco sólido
- ‘#’ é um bloco quebrável
- ‘?’ é um bloco com moeda
… e assim por diante, usando um caractere diferente para cada tipo diferente de objeto no nível.
O resultado são arquivos de textos parecidos com o seguinte:
Analisando o arquivo de texto, podemos ver que os níveis de Mario não seguem um padrão se você os ler linha por linha:
Os padrões em um nível aparecem realmente quando consideramos os níveis como uma série de colunas:
Portanto, para que o algoritmo encontre padrões nos nossos dados, precisamos passar os dados em forma de coluna. Descobrir a maneira mais efetiva de representar os dados de entrada (chamado seleção de caracteristicas —feature selection) é uma dos pontos chave para se utilizar bem os algoritmos de aprendizagem de máquina.
Para treinar o modelo, precisei rotacionar meus arquivos de texto 90 graus. Isto garante que os caracteres são passados para o modelo em uma ordem em que o padrão poderá aparecer mais facilmente:
-----------=
-------#---=
-------#---=
-------?---=
-------#---=
-----------=
-----------=
----------@=
----------@=
-----------=
-----------=
-----------=
---------PP=
---------PP=
----------==
---------===
--------====
-------=====
------======
-----=======
---=========
---=========Treinando Nosso Modelo
Do mesmo modo que aconteceu quando criamos o modelo da prosa de Hemmingway, um modelo vai melhorando à medida que o treinamos.
Logo após o inicio do treinamento, nosso modelo gera apenas lixo:
--------------------------
LL+<&=------P-------------
--------
---------------------T--#--
-----
-=--=-=------------=-&--T--------------
--------------------
--=------$-=#-=-_
--------------=----=<----
-------b
-Ele captura a ideia de que ‘-’ e ‘=’ tem que aparecer muito, mas é só isso. Nenhum modelo foi descoberto ainda.
Depois de vários milhares de iterações, já começa a se parecer com algo:
--
-----------=
----------=
--------PP=
--------PP=
-----------=
-----------=
-----------=
-------?---=
-----------=
-----------=O modelo já quase descobriu que cada linha tem que ser do mesmo tamanho. Até mesmo começou a descobri alguma lógica do Mario: os tubos no Mario tem sempre dois blocos de largura e pelo menos dois blocos de altura, por isso os “P”s no dados devem aparece como grupos de 2x2. Isto é muito legal!
Com um pouco mais de treino, o modelo chega ao ponto de gerar dados perfeitamente válidos:
--------PP=
--------PP=
----------=
----------=
----------=
---PPP=---=
---PPP=---=
----------=Vamos pegar os dados de um nível inteiro no nosso modelo e rotacionar de volta para horizontal:
Estes dados parecem muito bons! Há varias coisas interessantes para se notar:
- Ele colocou um Lakitu (o monstro que flutua nas nuvens) no céu no início de um nível —igual a um nível real de Mario.
- Ele sabe que tubos flutuando no ar devem estar apoiados em um bloco sólido e não pairando no ar.
- Ele coloca inimigos nos lugares corretos.
- Ele não coloca nada que pudesse impedir um jogador de mover-se para frente.
- O resultado parece um nível real de Super Mario Bros. 1 porque é baseado no estilo dos níveis originais que existiam para este jogo.
E finalmente, vamos usar este nível e recria-lo no Super Mario Maker:
Experimente!
Se você tem o Super Mario Maker, você pode jogar este nível usando o link bookmarking online ou procurando pelo código de nível 4AC9–0000–0157-F3C3.
Aplicações Simples vs. Mundo Real
O algoritmo de Rede Neuronal Recorrente que utilizamos para treinar nosso modelo é o mesmo algoritmo utilizaod por companias do mundo real para resolver problemas difíceis como reconhecimento de voz e tradução. O que faz o nosso modelo ser simples (toy problem) ao invés de inovador é que nosso modelo foi gerado a partir de uma quantidade muito pequena de dados. Não há níveis suficiente no jogo Super Mario Brothers para gerar dados em quantidade necessária para treinar um modelo realmente bom.
Se tivessémos acesso às centenas de milhares de níveis de Super Mario Maker criados por usuários, poderíamos fazer um modelo muito melhor. Mas não podemos — porque a Nintendo não nos dá acesso a eles. Grandes companias não disponibilizam seus dados de graça.
Com o aumento da importância da aprendizagem de máquina em mais indústrias, a diferença entre um programa bom e um programa ruim vai ser a quantidade de dados que você tem para treinar seus dados. Por isto que companias como a Google e o Facebook precisam dos seus dados tão deseperadamente.
Por exemplo, recentemente a Google abriu o código do TensorFlow, sua ferramenta de construção de aplicações de aprendizagem de máquina de larga escala. É um notável que a Google torne distribua gratuitamente uma tecnologia tão importante e capaz. Esta é a mesma tecnologia por trás do Google Translate.
Mas sem a quandidade gigantesca de dados de todas as líguas que a Google possui, você não pode criar um competidor para o Google Translate. Dados é o que proporciona ao Google sua vantagem competitiva. Pense nisto na próxima vez que você abrir seu Histórico de Localizações no Google Maps ou or Histórico de Localizações no Facebook e observe que ele registra todos os lugares em que você esteve.
Leitura adicional
Em aprendizagem de máquina, nunca há uma única maneira de solucionar um problema. Você tem opções ilimitadas para decidir como pre-processar seus dados e qual algoritmo utilizar. Muitas vezes, combinar multiplas abordagens vai dar melhores resultados que qualquer abordagem isolada.
Vários leitores enviaram links para outras abordagens interessantes para gerar níveis de Super Mario:
- Justin Michaud expandiu a abordagem que eu usei aqui para gerar nível e descobriu um meio de colocar os níveis gerados em arquivo NES_rom original file (code written over 30 years ago)! Você pode até jogar esta rom hackeada online.
- A equipe de Amy K. Hoover utilizou uma abordagem que representa cada tipo de objeto no nível (tubos, chão, plataformas, etc.) como se fosse uma voz única em uma sinfonia. Usando uma técnica chamada functional scaffolding, o sistema pode acrescentar blocos de qualquer tipo aos níveis. Por exemplo, você pode esboçar o formato básico de um nível e ele pode adicionar tubos e blocos de interrogação para completar seu nível.
- A equipe de Steve Dahlskog mostrou que modelar cada coluna de um nível como uma série de “palavras” n-gramas possibilita a geração de níveis com um algoritmo muito mais simples do que uma RNR de grande escala.
Nota do autor: Se você gostou deste artigo, considere assinar a minha lista de emails Machine Learning is Fun! Só irei enviar mensagens quando eu tiver alguma coisa nova e interessante para compartilhar. Esta é a melhor maneira de ficar sabendo quando eu escrever mais artigos iguais a este.
Você pode me seguir no Twitter em @ageitgey, me enviar email diretamente ou me encontrar no linkedin. Eu vou adorar poder ajudá-lo ou a sua equipe com aprendizagem de máquina.
Nota do tradutor: Agora, continue a jornada com Aprendizagem de Máquina é Divertido Parte 3!
