30abr/122

Implementação de classificador Naïve Bayes em MongoDB

O presente artigo é derivado do que escrevi para o evento Equinócio de Outono de 2012, promovido por São Paulo Perl Mongers.

Porém, ao invés de servir como uma espécie de complemento, é uma "volta às origens". O algoritmo original, desenvolvi em JavaScript puro, depois traduzi para Perl, refinei, detalhei e escrevi sobre. A intenção agora é ser mais show me the code possível, com um exemplo simples, enxuto e prático. Portanto, a teoria e os detalhes continuam lá no artigo original. Aqui, é mão na massa!

Ensinando o classificador

O classificador funciona por palavras-chave, e o MongoDB, nesse estágio, atua como um mero key/value storage. Salve o código de inicialização a seguir como init.js e carregue com mongo bayes init.js

db.bayes.update({_id: 'pelos'}, {$inc: {total: 1, 'categ.gato': 1}}, 1);
db.bayes.update({_id: 'bigodes'}, {$inc: {total: 1, 'categ.gato': 1}}, 1);
db.bayes.update({_id: 'pata'}, {$inc: {total: 1, 'categ.gato': 1}}, 1);
db.bayes.update({_id: 'pata'}, {$inc: {total: 1, 'categ.gato': 1}}, 1);
db.bayes.update({_id: 'pata'}, {$inc: {total: 1, 'categ.gato': 1}}, 1);
db.bayes.update({_id: 'pata'}, {$inc: {total: 1, 'categ.gato': 1}}, 1);
db.bayes.update({_id: 'rabo'}, {$inc: {total: 1, 'categ.gato': 1}}, 1);
db.bayes.update({_id: 'pelos'}, {$inc: {total: 1, 'categ.cachorro': 1}}, 1);
db.bayes.update({_id: 'pata'}, {$inc: {total: 1, 'categ.cachorro': 1}}, 1);
db.bayes.update({_id: 'pata'}, {$inc: {total: 1, 'categ.cachorro': 1}}, 1);
db.bayes.update({_id: 'pata'}, {$inc: {total: 1, 'categ.cachorro': 1}}, 1);
db.bayes.update({_id: 'pata'}, {$inc: {total: 1, 'categ.cachorro': 1}}, 1);
db.bayes.update({_id: 'rabo'}, {$inc: {total: 1, 'categ.cachorro': 1}}, 1);
db.bayes.update({_id: 'pata'}, {$inc: {total: 1, 'categ.galo': 1}}, 1);
db.bayes.update({_id: 'pata'}, {$inc: {total: 1, 'categ.galo': 1}}, 1);
db.bayes.update({_id: 'bico'}, {$inc: {total: 1, 'categ.galo': 1}}, 1);
db.bayes.update({_id: 'asa'}, {$inc: {total: 1, 'categ.galo': 1}}, 1);
db.bayes.update({_id: 'asa'}, {$inc: {total: 1, 'categ.galo': 1}}, 1);
db.bayes.update({_id: 'penas'}, {$inc: {total: 1, 'categ.galo': 1}}, 1);
db.bayes.update({_id: 'bico'}, {$inc: {total: 1, 'categ.ornitorrinco': 1}}, 1);
db.bayes.update({_id: 'pata'}, {$inc: {total: 1, 'categ.ornitorrinco': 1}}, 1);
db.bayes.update({_id: 'pata'}, {$inc: {total: 1, 'categ.ornitorrinco': 1}}, 1);
db.bayes.update({_id: 'pata'}, {$inc: {total: 1, 'categ.ornitorrinco': 1}}, 1);
db.bayes.update({_id: 'pata'}, {$inc: {total: 1, 'categ.ornitorrinco': 1}}, 1);
db.bayes.update({_id: 'rabo'}, {$inc: {total: 1, 'categ.ornitorrinco': 1}}, 1);
db.bayes.update({_id: 'pelos'}, {$inc: {total: 1, 'categ.ornitorrinco': 1}}, 1);

Agora, entrando em MongoDB Interactive Shell com mongo bayes, podemos ver a estrutura resultante com db.mongo.find():

{ "_id" : "bigodes", "categ" : { "gato" : 1 }, "total" : 1 }
{ "_id" : "bico", "categ" : { "galo" : 1, "ornitorrinco" : 1 }, "total" : 2 }
{ "_id" : "asa", "categ" : { "galo" : 2 }, "total" : 2 }
{ "_id" : "penas", "categ" : { "galo" : 1 }, "total" : 1 }
{ "_id" : "pata", "categ" : { "cachorro" : 4, "galo" : 2, "gato" : 4, "ornitorrinco" : 4 }, "total" : 14 }
{ "_id" : "rabo", "categ" : { "cachorro" : 1, "gato" : 1, "ornitorrinco" : 1 }, "total" : 3 }
{ "_id" : "pelos", "categ" : { "cachorro" : 1, "gato" : 1, "ornitorrinco" : 1 }, "total" : 3 }

Cada palavra-chave é associada aos contadores das categorias, além do contador geral de ocorrências. Agora, vamos processar essa estrutura de dados!

Classificador em map/reduce

O código a seguir é quase que um programa independente em JavaScript, salve-o como bayes-mongodb.js:

var words = [];
for (var word in doc)
    words.push(word);
 
var categ = [
    'gato',
    'cachorro',
    'galo',
    'ornitorrinco'
];
 
var guess = db.runCommand({
    mapreduce: 'bayes',
    out: { inline: 1 },
    query: {
        _id: {
            $in: words
        }
    },
    scope: {
        categ: categ,
        doc: doc,
    },
    map: function () {
        for (var i = 0; i < categ.length; i++) {
            var ctg = categ[i];
            var prob = Math.log(
                typeof(this.categ[ctg]) != 'undefined'
                ? this.categ[ctg]
                : 1.18e-38
            );
            prob -= Math.log(this.total);
 
            emit(ctg, prob * doc[this._id]);
        }
    },
    reduce: function (key, values) {
        var result = 0;
        values.forEach(function (value) {
            result += value;
        });
        return result;
    }
});
 
var res = { value: -Infinity };
for (var i in guess.results)
    if (guess.results[i].value > res.value)
        res = guess.results[i];
 
print(res._id);

Para passar parâmetros via linha de comando, usamos a opção --eval do MongoDB Shell, e o script imprime na tela a categoria "adivinhada":

$ mongo bayes --quiet --eval 'var doc = { bigodes: 1, rabo: 1 }' bayes-mongodb.js 
gato
$ mongo bayes --quiet --eval 'var doc = { bico: 1, rabo: 1, patas: 4 }' bayes-mongodb.js 
ornitorrinco
$ mongo bayes --quiet --eval 'var doc = { bico: 1, asa: 2 }' bayes-mongodb.js 
galo

Conclusão

O básico do básico esta aí
É evidente que os resultados e a eficiência do classificador bayesiano variam de caso para caso, e até de implementação para implementação. Se a primeira tentativa não for um sucesso, se quiser entender para que serve o "número mágico" 1.18e-38, ou se quiser automatizar o "treinamento" através de um pequeno script em Perl, consulte o artigo original!

Tags: AI, Bayes, classificador, HOWTO, MongoDB, tutorial 2 Comentários

21abr/120

Y is the new X

Segue aqui uma listinha de utilitários ligeiramente diferentes dos tradicionais e consolidados, mas cujas pequenas e grandes melhorias me fizeram renunciar quase que completamente os mais clássicos e abraçar os bleeding edge ;)

mosh is the new ssh

Não me entenda mal: SSH é muito mais do que uma simples shell remota! Também serve para tunelamento de conexões, transferência de arquivos, autenticação remota... Aliás, o próprio Mosh se autentica via SSH. Só que daí em diante, é outra história.

Mosh utiliza o protocolo UDP ao invés do TCP, então não precisa manter uma conexão. Simplificando muito, Mosh faz sincronização do estado do terminal remoto com o local, ao invés de redesenhar as telas caractere por caractere.

Ou seja: o seu link pode ser muito ruim, que o Mosh não está nem aí. Pode perder conexão, pode colocar o notebook em standby; quando o link voltar, está aí a sua shell, do jeito que você deixou! 'Network error: Connection reset by peer'‎, nunca mais.

Outro "efeito colateral" bacana do Mosh é que ele dispensa buffers. Já me ferrei dando um lsof numa conexão lerda; até que todo o output saia, SSH não deixa nem o input de Ctrl-C passar.

Para finalizar, o comparativo de tempo de resposta de SSH com Mosh, do site oficial do MIT:

tmux is the new screen

Mesmo que você seja um ávido fã do screen, o tmux vale uma espiada. O grande distintivo talvez seja o modelo client/server, que garante uma grande flexibilidade às sessões gerenciadas pelo tmux. Por exemplo, dá para mover janelas entre diversas sessões, ou então replicar o input em várias janelas (útil quando se quer iniciar o mesmo processo em diversos nós). Os atalhos de teclas tem perfis pré-definidos "emprestados" de Vim ou Emacs, e, é claro, dá para redefinir quase tudo do jeito que quiser pelo arquivo de configuração bastante legível. Ah, um bônus: split vertical da tela funciona sem patch adicional

Um breve tutorial:

htop is the new top

Esse dispensa apresentações. É praticamente um 'Activity Monitor.app' versão terminal. Infelizmente, a versão para MacOS tem algumas esquisitices (especialmente na parte que se refere à exibição da quantidade de memória). Ainda assim, é excelente para overview geral do sistema. Sempre mantenho um htop aberto nos meus servidores 😉

ack is the new grep

Descobri o ack recentemente. Não é bem um grep, mas sim uma combinação de find/grep específica para trabalhar com código-fonte. Em suma, ele faz busca recursiva utilizando regexp "sabor Perl", e desconsidera coisas como subdiretórios do Git ou SVN. Por exemplo uma versão (very) quick & dirty do Perl::PrereqScanner seria:

ack -ho --perl '^\s*use\s+[\w+\.:]+' | sort -u

xz is the new bzip2

Um pequeno devaneio: aparentemente, Inteligência Artificial e compressão de dados são assuntos afins. Os organizadores do Hutter Prize, por exemplo, acreditam que uma compressão eficiente de um texto natural seria de dificuldade equivalente a passar no teste de Turing.

Voltando ao tema original: anos atrás, quando clock de um PC high-end não passava de 1 GHz, e conexão broadband ainda estava engatinhando nos países do 3-o mundo, ver um código-fonte compactado com bzip2 numa página de download era de restaurar a fé na humanidade. Pois era evidentemente um ato altruístico por parte do disponibilizador levar muito mais tempo para compactar para poupar um pouquinho de tempo e banda de quem fizer o download.

Hoje, o bzip2 roda na velocidade do gzip de outrora. Eis que revive o algoritmo LZMA: muito mais voraz quanto à CPU/RAM, na grande maioria dos casos chuta bonito o traseiro do bzip2! O conheci através do 7-Zip, de longe o melhor compactador para Windows (xupem, WinZip e WinRAR!). Depois, para a minha alegria, descobri o xz, que:

É mais fácil de digitar do que 'bzip2';
Compacta mais do que o bzip2;
Usa os mesmos parâmetros que o bzip2 (cat ... | xz -cv9 > dump.xz continua válido).

E você, tem algum exemplo assim? Comente!

Tags: ack, alternativas, bzip2, CLI, grep, htop, mosh, screen, ssh, tmux, top, UNIX, xz Sem Comentários

17abr/120

Extreme WYSIWYG

Essa semana, Slashdot nos contemplou com dois deliciosos eye-candies na área de interface e usabilidade:

Gliimpse

Devo confessar que, se eu tivesse como utilizar esse tipo de preview para redigir HTML, esse blog teria updates muito mais frequentes :P

Não me habituei com nenhum editor WYSIWIG, e até os meus slides faço em POD e renderizo com S5.

Realmente, me parece uma bela de uma mão na roda!

Light Table

Light Table - a new IDE from Chris Granger on Vimeo.

Demais esse conceito de IDE + REPL, que está para virar protótipo!

Só vejo um porém. Exemplificando metaforicamente: a melhor definição de uma "linguagem de programação" que conheço é "capacidade de produzir loop infinito". Por isso, falar "programador HTML", por exemplo, é meio que nonsense. Agora, apesar do loop infinito ser tão importante na teoria, não é nada bom na prática. Por exemplo, digitar :(){ :|:& };: na linha de comando do Linux ou Mac e dar ENTER leva ao suicídio do sistema operacional. Enfim, quem já programou em JavaScript e usou alert() para debugar, sabe do que estou falando :)

Agora, o cara usou um exemplo muito feliz: IDE dele é totalmente voltada para linguagens funcionais, tanto que a menor unidade de código, para ele, é a função. Por obséquio, linguagens funcionais não tem loop! Tem recursão, que até pode ser infinita, mas convenhamos: quem domina programação funcional, dificilmente vai cometer essa gafe...

Concluindo: a ideia é genial, mas daria certo para poucos. O meu palpite é que surgirá a versão dessa IDE para trabalhar com JavaScript, tanto client- quanto server-side (Node.js), pois JavaScript, surpreendentemente, é funcional (tecnicamente falando, JavaScript é quase um Domain Specific Language de Scheme, que é dialeto de Lisp).

Implementação de classificador Naïve Bayes em MongoDB

Ensinando o classificador

Classificador em map/reduce

Conclusão

Y is the new X

mosh is the new ssh

tmux is the new screen

htop is the new top

ack is the new grep

xz is the new bzip2

Extreme WYSIWYG

Gliimpse

Light Table

Categorias

Tags

Posts recentes

Lista de Links

Meus bookmarks recentes

Lançamentos para Cydia