Tecnologia. Inteligente.

Como eu disse no post anterior sobre o desafio da Netflix, a grande maioria dos times no topo da tabela de classificação utiliza variações dos mesmos algoritmos básicos. Cada time cria novas formas de tornar os algoritmos mais sofisticados e inteligentes, refinando suas técnicas de forma incremental.

Computadores que jogam Xadrez funcionam da mesma maneira: todos os melhores programas utilizam variações do mesmo algoritmo básico. O algoritmo original é bastante simples, mas as variações são cada vez mais complexas e ricas, refletindo avanços incrementais e bastante focados.

Muitas vezes esse foco em sofisticação da tecnologia faz com que as pessoas ignorem idéias muito mais simples e eficazes. Um bom exemplo aconteceu recentemente em Stanford, onde o Prof. Anand Rajaraman ministra uma matéria de mineração de dados. Como trabalho final na disciplina, vários grupos de alunos atacaram o problema da Netflix.

A maioria dos grupos agiu de forma parecida com os times que lideram o desafio, criando variações complexas e refinadas de algoritmos de recomendação simples. O grupo que se deu melhor, e chegou perto dos melhores resultados na tabela de classificação, usou um algoritmo muito simples e, ao invés de refiná-lo, melhorou os dados. Eles aumentaram os dados iniciais com meta-informação sobre cada filme extraída do IMDB. Com dados melhores e mais ricos, um algoritmo simples bateu técnicas bem mais sofisticadas.

tem uma música do Carlinhos Vergueiro chamada “Procotolo” que ficou um pouco mais famosa na interpretação de artistas como Ana Carolina e Lúdica Música, cuja letra é assim

É o Procotolo
É a Cardeneta
É a Falculdade
É o Estaltuto
É o Fenonemo
É um Pogresso
E é Sempre um crima
E aí vareia
É a largatixa
Que o pobrema
Essa é que é a Questã
Essa é que é a Questã
Quanto menas vezes falar dela é melhor
Essa é que é a Questã
Essa é que é a Questã
Quanto menas vezes falar dela é melhor
Com sastifação.

Antes de mais nada, deixe-me contar que tive muita dificuldade em achar esta letra no google porque, a cada palavra que eu escrevia errado, ele me corrigia

Essa fantástica letra tem tudo a ver com um probleminha que aconteceu uns dias atrás com a minha namorada (eu gosto de chamar a minha mulher de namorada). No trabalho dela, é comum enviar mala direta para diversas pessoas e instituições.

Muitas vezes, essas malas diretas são fundidas a partir de várias fontes: listas adquiridas de empresas especializadas (você pode comprar por exemplo listas de operadoras de cartão de crédito, do CDL, tudo bem segmentado e nada barato…), nomes e endereços das pessoas que preenchem as fichas de avaliação dos eventos, gente cadastrada no CRM da empresa, etc etc etc.

Como vocês podem imaginar, um monte de informação dos mesmos segmentos de público acabam gerando duplicatas, afinal, poucos conferem ANTES de inserir.

Para listas muito grandes, esse custo começa a se fazer visível. Aí você cai na situação de pedir para a pessoa do suporte técnico localizar para você ONDE E QUAIS são estas duplicatas. Só que a maioria das pessoas do suporte técnico vai tentar resolver isso com queries SQL, e como as queries SQL não são exatamente a coisa mais bem uniformizada do mundo, vai depender do fabricante do seu banco de dados se você tem como fazer busca aproximada em texto ou não.

Uma forma de tentar minimizar este problema é usar algum tipo de medida de similaridade no seu texto. Embora possa parecer para alguns um bicho de sete cabeças, é algo que surpreendentemente se encontra pronto por aí.

Uma das primeiras formas de resolver isso foi através do SOUNDEX, que são técnicas que medem a semelhança entre palavras baseado em sua fonética, ou seja, dos sons dela. Ainda hoje, é possível encontrar bons sistemas onde, se uma pessoa digita uma palavra errada, o sistema sugere palavras com sons aproximados.

Exemplo prático: você vive num país de terceiro mundo onde grande parte da população é semi-analfabeta e sua interface tem que ser boa o suficiente para entender o que uma pessoa de pouca instrução está digitando (isso SE ela estiver digitando). Lembre-se: a boa interface é feita para PESSOAS usarem.

Mas SOUNDEX não foi a solução que eu usei para ajudar a minha namorada. Se você lida com JAVA, então você ama o projeto Jakarta e já usou o Jakarta Commons Lang prá alguma coisa. Não foi diferente. Escondido dentro do StringUtils, você vai encontrar um obscuro método chamado getLevenshteinDistance().

Essa “distância” mede o quão diferente uma palavra difere de outra. E segundo este excelente livro do Berthier e do Baeza-Yates, na seção 6.3.4, você pode ler que esta medida é superior ao SOUNDEX para detectar erros de sintaxe, então não há porque não tentar :-).

Mais especificamente, ele mede quantas modificações são necessárias para se transformar uma palavra na outra. Por exemplo, de “joão” prá “joao”, basta trocar o “ã” pelo “a”, então a distância é 1. Se fosse “joão” para “xoao”, seria 2. Se fossem iguais, a distância seria zero. Então, quanto mais próximo de zero, mais semelhantes.

Só que a distância sozinha não serve porque o impacto de 1 ou 2 letras em palavras menores é maior do que em palavras (vamos assumir que espaços são parte das palavras aqui) grandes, de 20, 30 letras. A chance de 2 letras serem um erro ortográfico numa palavra grande é maior que numa palavra pequena. Não é uma verdade absoluta, é um pressuposto.

Uma forma muito simples de compensar isso (não é a melhor, mas é simples, e simples geralmente é bom) é dividir essa distância pelo tamanho da palavra, o que vai te dar um índice de densidade de diferenças ortográficas entre duas linhas.

Você vai cair em vários problemas típicos destas coisas “inexatas” como por exemplo

- como você sabe QUAL o melhor valor desse “índice de densidade” para separar os erros dos não erros? - no caso, eu tentei o olhômetro mesmo. Os pares selecionados parecem ser os errados mesmo?. Nem sempre é fácil assim.

- você vai ter dois tipos de erro: as duplicatas que o sistema não achou (as piores) e os pares que o sistema achou que eram duplicatas, que eram parecidas, mas que não eram duplicatas (as menos piores). Novamente, eu estava fazendo um favor para a minha namorada, então ela sabe que há uma margem de erro aí.

Porém, diante da situação de ter que triar manualmente uma lista de cerca de 6000 endereços, meu programinha, que gera uma lista de “pares suspeitos”, já facilita um pouquinho a vida dela. E como o conjunto de dados dela tem cerca de 22% de linhas duplicadas, nessa brincadeira, já foi uma economia de impressão e envio de cerca de 1200 folders. Não está ruim(*).

E o melhor de tudo, claro, o programinha, feito em JAVA, tem cerca de 50 linhas, levou 10 minutos para codificar e 15 minutos prá rodar.

Tente você mesmo(a), experimente procurar livros do “Paolo Coelho” nas lojas da web e veja quais lojas querem vender e quais querem te mandar de volta pro seu professor de Português porque você não é digno o suficiente prá comprar na mão deles

* Só este mês, minha namorada deve enviar mala direta para cerca de 40.000 endereços ao custo de R$ 0,80 por folheto enviado. 22% disso corresponde a R$ 7000. Isso já paga pelo menos a cerveja. ;-). Olha como este blog é bom!

Lembra do post sobre Human Computation, de alguns dias atrás, falando sobre uma apresentação no Google Tech Talks que mostrava como usar pessoas para categorizar fotos? (esqueci de contar que esta é uma das maneiras que o google usa para indexar suas imagens… se você já ouviu falar do Google Labeler)

Bem, essa abordagem, comercialmente falando, acaba de ser noticiada no excelente TechCrunch. Após vários startups de empresas que tentaram categorizar fotos automaticamente (Riya, Ookles, Polar Rose), surge a TagCow, que –acredita-se–, usa pessoas para categorizar as fotos. Porque os resultados são impressionantes. (infelizmente, o site deles parece estar fora do ar, provavelmente porque está todo mundo tentando acessar… mas o link que eu deixei aí é de um blog com as impressões de um cara que usou o sistema)

Se for verdade (muita gente está apostando que seja), o negócio passa a ser a infra-estrutura necessária para manter milhares de pessoas categorizando fotos manualmente diariamente. Um problema sério de escalabilidade e disponibilidade, mas não que não possa ser resolvido, no caso de fotos de álbuns na internet.

Não é o tipo de solução que você gostaria para monitorar o uso de equipamento remoto ou para biometria em sistemas de segurança privados.

Até então, sempre tivemos um sistema econômico em que as massas menos favorecidas só podiam vender sua força de trabalho em tarefas simples, e geralmente braçais, que exigem pouca ou nenhuma qualificação. Podemos estar entrando numa era em que um potencial muito básico do cérebro humano (com quantos anos uma criança poderia classificar estas imagens de forma satisfatória?) pode ser a nova força de trabalho. Ou seja, a qualificação pode ser ainda menor…

Você já parou para pensar se isso é bom ou ruim? Imagine gente nas favelas, nos países pobres da África, da Índia (onde a web chegar, claro), passando o dia inteiro em lan houses ganhando centavos a cada foto categorizada… O que você acha?

Nos comentários do post do Kenji sobre clusterização, a Adriana mencionou o desafio da NetFlix. Eu acho que merece o seu próprio post.

A NetFlix é uma locadora virtual de DVDs, de enorme sucesso nos EUA. Você se associa, escolhe quais filmes gostaria de ver e põe numa fila. A NetFlix manda os filmes pelo correio à medida que estão disponíveis, com envelope pago para você devolvê-los. Em um plano comum, você pode alugar até 3 DVDs de uma vez e fica quanto tempo quiser com eles, mas só recebe o próximo depois de devolver pelo menos um.

Pois a NetFlix tem um sistema de recomendações chamado Cinematch, que funciona até bem. Querendo melhorar a qualidade das recomendações eles lançaram, em 2006, um desafio. O primeiro a diminuir o erro das recomendações em 10% ganha US$1 milhão. É, um milhão de verdinhas. Os erros podem ser de dois tipos. Falsos positivos são quando o sistema faz recomendações estúpidas. Falsos negativos são quando ele deixa de recomendar algo que você ia gostar.

A idéia é genial: outsourcing da inovação. Gente do mundo inteiro, times acadêmicos e nerds em garagens estão participando e a NetFlix só paga se alguém conseguir os resultados que eles querem. Fora a publicidade gratuita e o incentivo à pesquisa - dezenas de publicações surgiram desse desafio.

Não é fácil. Em menos de um mês, já tinha gente na metade do caminho, com 5% de melhora. Mas depois disso, o progresso foi cada vez mais lento. Depois de um ano, um time da AT&T Labs Research tinha reduzido o erro em 8.43% e ganhou um prêmio de progresso de US$50.000,00 e uma placa horrível de “honra ao mérito”. Eles são os atuais líderes, com 9% de redução.

A grande maioria dos líderes no desafio utiliza métodos similares para gerar novas recomendações: eles se baseiam em filmes que você assistiu e gostou (ou quer assistir) e recomendam outros filmes similares. Isso é outra aplicação de clusterização.  O segredo está em definir uma forma de medir essa similaridade que faça sentido para quem está alugando os filmes, o consumidor final da NetFlix.

Recentemente, um outro competidor chamou atenção. Ao contrário dos times de laboratórios e universidades, esse é só um cara em casa. E sua formação original é em psicologia. Ele começou a trabalhar no problema um ano depois de anunciado e seus resultados melhoraram mais rapidamente que os de qualquer time até então. Atualmente, Gavin Potter está em nono lugar. Qual o seu segredo?

A maneira mais comum de medir a “similaridade” entre dois filmes é representar os filmes como um conjunto de números, onde cada número tem um significado específico.  Assim, o primeiro número pode ser o gênero do filme e duas comédias tendem a ser mais similares que uma comédia e um épico de guerra, por exemplo.  O segundo número pode indicar a linguagem do filme, e assim por diante.  Quando se caracteriza um filme dessa maneira, cada número é uma dimensão.

Existem métodos automáticos para determinar quais dimensões são importantes para um problema específico, mas eles são sujeitos a erros e decisões estúpidas, como toda técnica heurística.  Pois o segredo do Gavin é exatamente sua formação original.  Como psicólogo ele tem uma intuição muito melhor que a dos computeiros a respeito do valor de cada dimensão, e pensa em dimensões importantes que outros times ignoram.

Mesmo que ele não ganhe o prêmio, seu relativo sucesso em pouco tempo me lembra um velho ditado: a inteligência artificial não é páreo para a burrice natural.  Ou, de forma menos agressiva, nunca subestime o valor do conhecimento dos especialistas no assunto.

Esta interessante apresentação no Google Tech Talks (uma fonte eterna de vídeos bacanas, mas apenas em inglês, sorry) mostra todo o potencial que existe na web atualmente quando se trata de usar o potencial de raciocínio humano para resolver problemas complicados.

A apresentação é cheia de informações interessantes e piadas boas [coisa rara. humor costuma ser um bom indicativo de inteligência e confirma minha teoria que o Sr Ahn é muito bom de serviço]

De uma forma muito engenhosa, Luis Von Ahn, professor da Carnegie Mellon, conseguiu criar uma maneira de identificar e classificar imagens usando pessoas… com a ajuda de um viciante joguinho na web. Nunca devemos ignorar o poder de um monte de gente com tempo sobrando na web.

Alguns outros exemplos de “computação humana”

#1 - alguém já se perguntou, ao baixar suas piratarias dos file sharings da vida, se aquele captcha (aquelas letras tortinhas que vc tem que digitar para provar que não é um programa) não é o mesmo captcha que é usado em algum outro site para bloquear comentários de SPAMs ou coisa do tipo? Ou para criar uma conta falsa de email? Ou para acessar pornografia?

#2 - o facebook traduziu o site deles para alemão em 2 semanas com a ajuda de “apenas” 2000 voluntários

A web traz uma escala que possibilita coisas impressionantes. Encontrar a motivação para este poder computacional: eis o grande desafio da Web 2.0.

Esta semana, a Vivisimo, uma spin-off da universidade de Carnegie Mellon especializada em clusterização aplicada a mecanismos de busca, andou levantando um bocado de dinheiro em investimento. Ótimo momento, para quem andou acompanhando a tensão do aceita-não-aceita da proposta de compra da Yahoo pela Microsoft.

Para ver a tecnologia da Vivisimo em ação, confira o site Clusty e faça rapidamente uma busca, digamos, por “harmônica” (também conhecido como gaita de boca).

Além dos resultados tradicionais, note do lado esquerdo que algumas respostas estão “categorizadas” em itens como “blues harp” (gaita blues), “harmonica lessons” (aulas de gaita) e etc.

O interessante da tecnologia da Vivísimo, diga-se de passagem que não é nenhuma novidade, é que essa separação em categorias não é manual. Ninguém colocou um monte de estagiários para separar essas categorias. Isso é clusterização.

Clusterização, a grosso modo, é uma forma de, dado um monte de itens e um conjunto de características destes itens, separar o que é diferente e juntar o que é similar. Como você pode imaginar, há um monte de aplicações interessantes para isso.

Aqui no Labs, uma das aplicações disto é nas pesquisas de biotech que fazemos para diversos clientes, especialmente a Biomind. É comum os biólogos terem vários dados sobre como genes se comportam em diversas condições, e é muito interessante que, suponhamos, dentre 40.000 genes, os biólogos possam analisar apenas uns 10 ou 20 genes que, de alguma forma, tenham um comportamento parecido dentro de um determinado processo (por exemplo, quando comparamos tecidos de pessoas saudáveis e pessoas com câncer). Uma das formas de selecionar estes genes é através de algoritmos de clustering.

Outra aplicação famosa de clustering é no e-commerce. Se você já fez compras na Amazon, deve ter se deparado com aquelas sugestões de itens do tipo “pessoas que compraram este livro também compraram estes outros”. E com o dólar baixo, o dedo coça :-).

O algoritmo que a Amazon usa, que não deixa de ser um tipo muito refinado de clustering, é patenteado e é um tipo de Collaborative Filtering (filtro colaborativo). No fim das contas, baseado no perfil de compras de todos os clientes da Amazon, existem vários conjuntos de clientes que se comportam de maneira parecida, que compram parecido, que gostam das mesmas coisas. O sistema, estudando estes grupos, sugere para o cliente os livros que mais parecem agradar aquele segmento.

Naturalmente que um bom vendedor, ou o dono de uma livraria, aprende com o tempo a “clusterizar” seus clientes, e muito bem diga-se de passagem, enquadrando pessoas dentro de “perfis”. Tal cliente é o estudante de matemática que gosta de livros de ficção. Outra cliente é a dona-de-casa sagitariana que gosta de romances água-com-açúcar. Contudo, vale lembrar alguns aspectos aqui.

• A Amazon lida com muito mais gente que o nosso competente dono de livraria.
• A Amazon faz estas contas e indica produtos relacionados o tempo todo, a cada passo que você dá dentro do site deles. O que significa que a NAVEGAÇÃO do site é modificada DINAMICAMENTE, ou seja, o site se ajusta a cada passo do usuário.
• O algoritmo da Amazon pode encontrar padrões nos perfis de usuários que uma pessoa não encontraria.
• Estudar estes padrões encontrados pelo algoritmo ajudam a conhecer melhor o seu próprio negócio.
• Aplicar este tipo de algoritmo aos mais diversos tipos de dados não é uma coisa incrivelmente difícil ou cara.

Fica meu gigante ponto de interrogação: por que a submarino não me sugere outras coisas que eu gostaria de comprar?

Este post comenta ESTE ARTIGO (inglês)

Quem: Sandy Pentland, MIT

Definição: Mineração de Realidade Pessoal (Personal reality mining) infere relações e comportamento através de técnicas de data mining coletada a partir do uso de celulares

O MIT soltou uma lista das tecnologias mais promissoras para os próximos anos, e dentre elas, havia este esotérico termo chamado “reality mining”. Hypes à parte, nada mais é que data mining em cima de dados pessoais obtidos através de celulares, uma tecnologia que agora está na mão de muita gente. Pense em todas as possibilidades, para o bem e para o mal, que um celular com GPS pode oferecer.
Além de, claro, ter um grande volume de dados, reality mining também tem tudo a ver com outra tendência: as redes sociais. Afinal, o que são os celulares senão outra interface que liga você aos seus amigos, familiares, colegas de trabalho, etc? E isso vai desde a análise de padrões de comportamento até o rastreamento de doenças infecciosas, como SARS.

A polêmica óbvia em cima disso é: as pessoas querem ter suas intimidades esmiuçadas neste nível de granularidade? Entra no debate as questões éticas e morais, a privacidade e etc, mas o fato é que, sob vários aspectos, a tecnologia permite a extração de várias informações que irão interessar muita gente.

Data mining não é uma ciência nova e está presente em nossas vidas há muito tempo. Dizem que quem mais conhece sua vida é seu gerente de banco. Analisando anos de extratos bancários, não é difícil ver onde você gastou com livros para a faculdade, se você passou aperto ou não, se vc progrediu no seu emprego, quando vc se casou, quando vc teve filhos, quando você precisou pagar por coisas caras e relevantes, ou até se você é fiel ou não no seu casamento.

Números não mentem. Mas também não esclarecem, se a análise não for bem feita. Data mining é extrair conhecimento através da análise de bases de dados. É encontrar e interpretar padrões, para diversos fins. Desde conhecer melhor seu objeto de estudo até tentar prever ações futuras.

Lembrei imediatamente de uma piadinha sem graça. Maria liga no celular do Manoel, que atende desesperado dizendo “Maria! Como descobriste que eu estava a te trair no motel?”

Pode ser uma piada mais sem graça ainda depois que deixar de ser piada ;-).