Arquivo da categoria: computação

Vale a pena fazer o curso de machine learning do Coursera?

As plataformas de cursos online surgiram nos últimos anos para realizar o sonho de muita gente: poder assistir aulas formuladas pelas melhores universidades do mundo sem precisar sair de casa, enquanto come um Doritos e veste apenas uma cueca. Esse não era meu sonho, mas resolvi que deveria experimentar esse conteúdo pelo menos pela experiência.

Aprendizado de máquina é um assunto que me interessa, por isso resolvi me matricular neste curso gratuito do Coursera. Já havia estudado o assunto antes por conta própria através de livros e até usado um pouco da teoria na prática. Além de poder aprender mais algumas coisas e solidificar o que já tinha visto, essa foi a chance de conhecer e avaliar um conteúdo didático criado em Stanford. É o equivalente para um amante de café ter a chance de experimentar de graça aquele café que é considerado um dos melhores do mundo, feito com grãos retirados das fezes de um roedor que não lembro o nome.

Antes de saber se você deveria fazer este curso é uma boa ideia ter uma noção do que é aprendizado de máquina. E acho que a melhor forma de motivar alguém a conhecer melhor o assunto, é ter uma noção de suas aplicações práticas. Usando machine learning você pode criar software que reconhece objetos em imagens, detecta fraudes em operações financeiras, dirige um automóvel ou drone, avalia o crédito de pessoas, avalia a probabilidade de um paciente ter uma doença, prevê que um servidor pode sofrer uma falha, e muitas outras coisas que parecem mágica. Mas conhecendo melhor sobre o assunto você vai ver que essa lista que fiz é bem limitada.

Depois de se interessar pelo curso, sua preocupação pode ser em saber se você precisa ser um campeão de olimpíada de matemática para conseguir acompanhar o curso. Este é um assunto que usa muita matemática, mas o curso foi pensado para alunos que pelo menos consigam ler uma fórmula com somatórias, matriz e vetores. Existem até aulas opcionais com álgebra linear básica para ajudar com os conceitos que vão ser usados durante as aulas. E graças ao professor Andrew Ng, as aulas são muito didáticas a ponto de ele fazer todos os passos de cálculos necessários nos exemplos. Em casos em que seria necessário um conhecimento matemático maior, o professor dá uma explicação sobre a intuição do que está sendo feito, mas não é exigido que o aluno saiba resolver uma derivada ou decompor uma matriz, por exemplo. Mas minha opinião é que tendo uma base mais do que básica sobre cálculo e álgebra linear vai tornar o conteúdo muito mais fácil de assimilar e entender, sem deixar que alguns passos nos algoritmos pareçam ter aparecido por mágica.

Saber programar é um pré-requisito. Os projetos a entregar são programas escritos em Matlab ou Octave. Mas não é necessário conhecer uma dessas linguagens, pois algumas das aulas vão te ensinar o necessário para realizar todas as tarefas. Eu mesmo nunca havia usado essas linguagens. Apesar de não ser muito difícil de aprender, muitas vezes perdi muito tempo por detalhes da linguagem que causavam erros nas minhas tarefas. Mas o fato de que você só precisar programar o principal das tarefas, com o código que cuida de preparar os dados e mostrar resultados já pronto, facilitou e economizou muito meu tempo, considerando que é um curso que muita gente vai fazer no tempo livre. E o sistema de envio das tarefas com correção automática funciona muito bem. Você resolve cada passo do exercício, envia para o sistema e ele te diz se você acertou ou não.

Um ponto muito positivo é que todo o conteúdo, por ser ensinado pela mesma pessoa, tenta seguir mais ou menos a mesma notação do começo ao fim. Isso ajuda muito para comparar os algoritmos. Quando você tenta aprender cada uma dessas coisas por fontes diferentes, você acaba vendo notações diferentes que dependem da preferência do autor. É como tentar entender uma história que teve uma parte contada por uma pessoa e o final contada por outra, mas a que contou o final só se refere aos envolvidos por apelidos que você não conhecia.

O melhor do curso para mim são as ferramentas que ele ensina para que você entenda se sua solução de machine learning está funcionando bem, e o que você pode fazer para melhorá-la. É esse o conhecimento que eu esperaria de alguém que fosse usar esses algoritmos na prática.

Vejo poucos pontos negativos, que são pequenos perto das qualidades do curso. Algo que me incomoda um pouco são as questões que aparecem no meio dos videos. Muitas vezes eles nem estão testando se você entendeu a teoria que está sendo ensinada, mas verificando se você está acordado e prestou atenção na notação que o professor acabou de usar. Outra coisa que me fez falta, que se deve mais ao formato, é não ter um material que possa consultar facilmente depois. É impraticável procurar no meio dos videos algo que você não lembra direito onde viu, por isso recomendo anotar principalmente as dicas que são baseadas na experiência do professor Andrew.

Talvez algumas pessoas possam se sentir incomodadas pela falta de formalidade técnica que o assunto é tratado, mas considerando que aprendizado de máquina é uma área em que os métodos funcionam mesmo sem os matemáticos entenderem muito bem, acho que o conteúdo habilita alguém a se tornar um praticante. Um conhecimento mais formal seria necessário apenas para quem deseja se tornar um pesquisador na áreae nesse caso este curso funcione bem como uma introdução geral.

Por tudo isso digo que vale muito a pena fazer o curso de machine learning oferecido pela Universidade de Stanford pelo Coursera. Valeria a pena mesmo se fosse pago, sendo grátis eu tenho a vontade de visitar meus amigos programadores e obrigá-los a assistir essas aulas.

Anúncios

Algoritmos genéticos – um resumo e um exemplo

Quando você tem um problema com um número muito grande de candidatos a solução (mas muito grande mesmo), o que você precisa é de um algoritmo de busca. Não de busca no sentido Google, mas de busca de solução. Hoje em dia, em tempos de guerra de “search engines” o nome talvez confunda um pouco, mas algoritmos de busca são fundamentais em computação. Basicamente o que você quer com um algoritmo de busca é navegar pelo mar de possíveis respostas, de preferência de uma forma esperta para te ajudar a encontrar a melhor solução.

“E que problemas eu resolvo com essas bagaças? Resolve minha dívida no bar do bigode?” Os algoritmos de busca em geral são bem genéricos, então podem resolver um número muito grande de problemas. O trabalho do computólogo (ou computeiro, sei lá) é modelar o problema para que ele possa ser resolvido pelo algoritmo, o que geralmente não é um trabalho muito simples. Você não paga sua dívida no bar do bigode diretamente usando esses algoritmos, talvez, mas você pode escrever um algoritmo para calcular quais são as melhores jogadas que você deve fazer nas partidas de dominó para tirar um troco. Ou você pode criar um algoritmo para gerar projetos mais econômicos de circuitos eletrônicos, vender para uma IBM da vida, e comprar o bar do bigode com esse dinheiro.

A situação ideal é quando o algoritmo te dá uma solução sem levar muito tempo computando e a solução é a melhor possível (ou quando você passa um final de semana com a Megan Fox). E existem diversos algoritmos que são capazes de fazer isso (encontrar uma solução, não a parada da Megan Fox), mas isso depende muito do problema específico e de seu tamanho. Mas e quando você precisa mesmo da solução e esses algoritmos não são capazes de computar algo em um tempo razoável? É aí que você pode usar um algoritmo heurístico de busca, como por exemplo algoritmos genéticos. E por coincidência, este é o título deste post.

Heurística? É de comer?

A grosso modo, uma heurística é um chute mais esperto, um critério ou estratégia que pode te ajudar a encontrar uma solução boa. Pode ajudar, às vezes não vai te ajudar. Você pode por exemplo bolar uma estratégia para pegar a Megan Fox (de novo?) e de vez em quando isso funcionar. Mas de vez em quando você acabar com a Amy Winehouse. Enfim, no mínimo com este artigo você aprendeu uma palavra nova para usar na “night”.

Algoritmos genéticos

Algoritmos genéticos são algoritmos heurísticos de busca inspirados na teoria da evolução, seleção natural e nos processos biológicos envolvidos. Se você ainda lembra de conceitos como meiose, mutação, cross-over, vai ver que o algoritmo praticamente simula a idéia de como as coisas ocorrem com os cromossomos e DNA, mas utilizando os dados do problema que você quer resolver. Se você gosta muito de computação E de biologia, a ponto de ter um pôster do Richard Dawkins no seu quarto, vai ter um orgasmo cerebral de saber que um negócio desses funciona.

Eu não tenho um pôster do Richard Dawkins

Eu não tenho um pôster do Richard Dawkins

Vou tentar explicar rapidamente a idéia do algoritmo, mas provavelmente você entenderá melhor olhando para o exemplo mais abaixo. Mas já deixo claro que esta explicação abaixo tem como objetivo ser uma introdução rápida, por isso não vou ficar me desculpando no meio do texto por causa de detalhes técnicos e outros “poréns”.

A primeira coisa que você precisa ter é uma forma de representar os candidatos de preferência como uma sequência de elementos, assim como o DNA é uma sequência de bases (lembra, adenina, guanina, citosina e timina? Eu não lembrava, procurei no Google). E da mesma forma que na natureza, os primeiros patos tinham sua sequência de DNA, você precisa de um primeiro conjunto de candidatos a solução do seu problema. Esses primeiros candidatos você gera à vontade, afinal, como no caso dos patos, os primeiros não precisam ser muito bons. A seleção natural é que vai transformá-los nos super patos que existem hoje, e te ajudar a encontrar uma boa solução para o seu problema.

A natureza desempenha a seleção natural para os patos. Para o seu problema, você vai ter que bolar um critério de seleção, criando uma função de fitness que possa calcular o quanto aquele candidato a solução é um bom candidato. Esse é o seu trabalho, que depende bastante do seu problema. E usando essa função, você decide na sorte quais indivíduos sobrevivem para a próxima fase, dando mais chances para os que tiveram uma boa nota na sua funçaõ de fitness. É mais ou menos como o programa Tentação do Silvio Santos, onde só os melhores e mais sortudos passam para a próxima fase.

Depois é a hora de misturar DNA. A forma como os patos fazem isso você deve saber: ao som de Barry White ao lado da lareira. E pegando um teco de material genético do papai e misturando com o da mamãe, o que a gente chama de crossover. E isso é o que você vai fazer para ajudar a resolver seu problema, pegar um pedaço de duas das soluções sorteadas na etapa anterior e misturar para gerar uma nova solução. E aí você faz isso para gerar diversas soluções filhas, para usar no próximo passo do algoritmo.

Por último entra um processo muito conhecido pelos X-Men: a mutação. Graças a isso você pode ter características novas nas populações existentes, como patos que atiram laser pelos olhos. Ou uma solução melhor para seu problema. Também podem surgir patos de duas cabeças ou soluções piores para seu problema. Por isso é uma etapa em que você não realiza muitas mudanças, podendo muitas vezes nem mudar nada. Sorteie um ou mais dos pedaços do seu candidato a solução e dê uma mudadinha nele (ou não). Pronto, você tem uma solução mutante.

Pato após mutação

Pato após mutação

Depois é só aplicar todos esses passos (fitness, crossover e mutação) várias vezes, gerando várias soluções, que se tudo estiver direitinho e se sua modelagem do problema for boa, você pode encontrar uma solução para seu problema. Você pode definir algum critério para esse algoritmo parar, como por exemplo rodar até encontrar uma solução boa o suficiente de acordo com a sua função de fitness, ou rodar 1000 vezes.

Não entendi. Desenha pra mim?

Acho que o problema mais simples para usar como exemplo é o problema das N-Rainhas. Se você não sabe, no xadrez a rainha é a peça mais poderosa, que pode se movimentar em qualquer direção, incluindo diagonais, e qualquer número de casas. Ela é ferrada. E normalmente, em um jogo normal, você tem só duas rainhas, uma para cada adversário. Mas no problema das n-rainhas, você tem n rainhas e um tabuleiro com n linhas e n colunas (por exemplo, no problema das 4-rainhas você tem um tabuleiro de 4×4 e 4 rainhas). O desafio consiste em posicionar as n rainhas no tabuleiro sem que nenhuma delas esteja se atacando. Para um n pequeno, o problema é meio bobo, mas se você tiver um n como 4378564378543, aí a coisa complica. Óbvio que resolvendo isto você não vai comprar o bar do bigode, mas acho que te ajudará a aprender como funcionam os algoritmos genéticos.


nrainha1

Exemplo A: aqui o problema não foi resolvido, porque as rainhas das duas últimas colunas podem se atacar pelas diagonais.


nrainha2

Exemplo B: Uma solução para o problema.

Pelos dois exemplos acima você já deve ter sacado que é uma coisa esperta você tentar não colocar mais de uma peça por coluna por exemplo. E isso nos ajuda a modelar a forma como podemos representar esses candidatos a solução. Lembra quando falei que seria legal se o candidato a solução pudesse ser representado por uma sequência de elementos? Podemos representar os exemplos acima, com um vetor de números, em que a primeira posição do vetor indica a linha em que colocamos a rainha da primeira coluna, a segunda posição no vetor a linha da rainha da segunda coluna, e assim por diante. Com isso, o exemplo A seria representado por (1, 4, 2, 3) e o exemplo B por (2, 4, 1, 3). Essas representações são como o DNA do seu problema.

Com essa representação, você está pronto para começar o algoritmo, gerando alguns candidatos a solução que vão ser a primeira geração. Como gerá-los e quantos gerar fica a seu critério. Você pode ter por exemplo uns 20 candidatos gerados de forma aleatória (sorteando cada valor em cada posição).

Agora o que a gente precisa é uma função de fitness, que vai ser usada para fazer a seleção dos candidatos para a próxima fase. Você quer que a função de fitness dê uma probabilidade maior para uma solução quase resolvida do que para uma solução com muitas rainhas se atacando. Neste problema, podemos dizer que o melhor candidato é aquele com menor número de rainhas se atacando e usar isso para construir a função de fitness. Então você pode por exemplo estabelecer que se um candidato a solução tem 4 rainhas se atacando, a probabilidade dele passar para a próxima fase seja de 10%, se tiver 3 rainhas se atacando seja de 30%, e assim por diante. Então para cada candidato a solução você calcula seu fitness e joga o seu dado de 100 lados para cima para ver se esse candidato sobrevive para a próxima fase. Se o dado gerar um número menor que a probabilidade dada pela função de fitness, deixe o candidato continuar.

Chega a etapa de crossover, de misturar as soluções. Primeiro agrupe os candidatos em pares (papai e mamãe). Você pode sortear um número para saber o tamanho do pedaço inicial da solução papai que será substituída no candidato mamãe, e fazer essa substituição para gerar um novo candidato. Por exemplo, se você tiver um papai (2, 3, 4, 4) e uma mãe (1, 3, 2, 1), você pode decidir pegar as duas primeiras colunas do pai e as duas últimas da mãe para gerar o novo (2, 3, 2, 1). Continue com essa orgia de candidatos até gerar o mesmo número de candidatos que você tinha inicialmente.

A mutação também é uma etapa simples. Primeiro decida aleatoriamente se vai ocorrer mutação para aquele candidato (de preferência com uma probabilidade baixa, para que isso não seja tão frequente). Se for decidido que deve haver mutação, sorteie uma das colunas do candidato e mude esse valor para um valor aleatório. Por exemplo, o candidato (1, 4, 3, 3) pode sofrer uma mutação na última coluna e se transformar em (1, 4, 3, 1), por exemplo.

Daí em diante repita, até conseguir um candidato sem nenhum conflito.

Gostei, vou usar para resolver todos os meus problemas!

Calma, algoritmo genético não é a solução para todos os males (apesar de alguns pesquisadores com fome por número de publicações acharem que é). Ele não vai funcionar tão bem para alguns problemas, e isso você só descobre depois que teve todo o trabalho de implementar e rodar. Você pode precisar das respostas dentro de um certo tempo, e o algoritmo pode precisar rodar por muito tempo para chegar em alguma resposta razoável (o que é um problema de muitas buscas heurísticas). Ele pode não chegar a uma resposta boa o suficiente. E modelar o problema e gerar uma boa função de fitness não é um trabalho simples, e o desempenho do algoritmo depende muito do seu modelo.

Mesmo com essas restrições, existem diversas aplicações (e tentativas de aplicação) de algoritmos genéticos na indústria, no mercado financeiro e (ironicamente) em bioinformática, além de ser uma ferramenta auxiliar no ambiente acadêmico. Se duvida disso, dê uma olhada nos resultados do Google.

Espero que algum dia um algoritmo genético possa te ajudar a evoluir na resolução de um problema.

Monges, torres e porque não adianta apenas comprar mais hardware

Se você já visitou a casa de algum pai que goste de presentear seus filhos com brinquedos educacionais (ou você é um desses pais), já deve ter visto uma torre de Hanoi. É aquele brinquedo que é composto de várias peças de tamanhos diferentes e três pauzinhos onde as peças se encaixam.

Este jogo não existe para Playstation 3

Este jogo não existe para Playstation 3

O que poucas pessoas sabem (principalmente as crianças que ganham esses brinquedos) é que esse é um quebra cabeças, com regras bem definidas e cuja solução algorítmica até já foi estudada por vários pesquisadores de matemática e computação.

Existe uma lenda sobre a torre de Hanoi, que diz que existem monges em um templo tentando resolver uma torre de Hanoi para o caso de 64 discos de ouro. E que quando eles conseguirem resolver, o mundo vai acabar. Agora você deve ter ficado preocupado, porque provavelmente se você conseguiu resolver a torre de Hanoi que seu filho tem em casa, daqui a pouco esses monges que não tem mais nada para fazer vão terminar esse negócio e o mundo vai acabar. E você já pagou suas férias de dezembro!!

Calma, se tudo der certo, você ainda vai poder viajar em dezembro. Pelo menos dificilmente os monges vão atrapalhar suas férias. O número mínimo de operações para se resolver uma torre de Hanoi de 64 discos é 264-1 movimentos. Ou seja, mesmo que os monges nunca errassem e pudessem realizar cada movimento em 1 segundo, a solução do problema inteiro levaria mais de 580 bilhões de anos para terminar. Sem pausa para a novela.

E se os monges fizessem um upgrade e usassem uma máquina tão rápida quanto o supercomputador mais potente atualmente? Olhando no TOP500, o campeão atual é o Roadrunner, um cluster da IBM, que realizou no benchmark até 1456704 GFlops (bilhões de operações de ponto flutuante por segundo). Como o problema da torre de Hanoi não pode ser paralelizado (sempre tenho que mover uma peça por vez) para simplificar vamos pegar um de seus processadores, que faz 12.8 GFlops. Se os monges pudessem realizar 12800000000 movimentos por segundo será que o fim do mundo aconteria antes da próxima copa do mundo? Melhoraria bastante (só uns 45 anos) mas ainda ocorreriam muitas copas até lá. 

Para quem já resolveu uma torre de Hanoi de brinquedo, com 8 discos, deve ser muito estranho uma torre que nem tem tantos discos a mais necessitar de um número tão grande de operações para ser resolvida. Isso em computação é muito comum e e conhecido como explosão exponencial. Às vezes o problema parece bobo quando você aplica o algoritmo para versões pequenas do problema, mas o número de operações para resolver versões só um pouco maiores cresce para um tamanho probitivo, em que simplesmente não valeria a pena tentar resolver por levar tempo demais.

O exemplo desse fenômeno é encontrado na resolução da torre de Hanoi. A versão infantil, com 8 discos, exige no mínimo 255 operações. Dobrando-se o número de discos, 65535 operações. Com 24 discos, 16777215 operações. Moral da história: se quiser deixar seu filho bem ocupado, dê uma torre de Hanoi com uns 20 discos.

É raro uma empresa se deparar com um problema desses e tentar resolvê-lo (na ignorância de que o problema gera uma explosão exponencial). E você nem precisa trabalhar em uma empresa que resolve torres de Hanoi. Depois de algum tempo tentando resolver o problema, a empresa pode se frustrar e desistir, ou culpar o coitado do programador que fica marcado como incompetente.

Obs.: Este post foi livremente inspirado nas aulas do professor Coelho do IME-USP. O original obviamente é melhor.