domingo, 3 de setembro de 2017

"Learning to ranking" with xCLiMF python implementation

At Globo.com we try to optimize our personalized recommendation providing better content in a ranked list. We have a hybrid system that can automatically essemble collaborative filtering, content based and non personalized algorithms.

But none of our implemented algorithms are intented to rank. Our best collaborative filtering algorithm, based on the paper Collaborative Filtering for Implicit Feedback Datasets, doesn't optimizes a ranking metric like MRR or NDCG.

Even so we have good results of those algorithms choosing the best hyper parameters focusing in MRR, we thought we could get better results using algorithms focusing in optimizing a ranking metric: Our first hypothesis is xCLiMF.

xCLiMF is a latent factor collaborative filtering variant wich optimizes a lower bound of the smoothed reciprocal rank of "relevant" items in ranked recommendation list. It is a evolution o CLiMF algorithm that can handle using multiple levels of relevance data instead of using only unary user preferences.

Implementation references


Since xCLiMF is very similar to CLiMF, I implemented xCLiMF based on this python CLiMF repository ( https://github.com/gamboviol/climf ). During the process I found an error and submitted a pull request ( https://github.com/gamboviol/climf/pull/2 ).

I have also found a C++ xCLiMF implementantion by other brazilian guy ( https://github.com/gpoesia/xclimf ). But this solution have two problems: The first one is a bug reported here ( https://github.com/gpoesia/xclimf/issues/1 ) and the second one is related to performance, since it updates user and item vectors separately as two loops of other two chained loops.

My implementation


So my implementation also have some differences from original papers:

  • In the paper they don't mention any kind of previously normalization, but it's always a good practice to do it for machine learning algorithms input data. So I normalized dividing all rating by the maximum rating in the dataset. Using original ratings lead to some math errors:
    • Exponential function of large values causes math range error;
    • Exponential function of very large negative numbers get 0, and lead to some division by zero error; 
    • Log function of negative numbers, caused by large exponentials, causes math domain error
  • The paper experimentation setup uses N random ratings by user in training and in the cross validation data. Even so I have implemented this way, I have put an option to select 2N top ratings by user, randomly distributed in training and cross validation. For me, this last protocol reflected a more realistic kind of problem that xCLiMF is going to solve.
  • In the original paper they described the algorithm as two chained loops. Firstly I implemented as described in the paper. But them I updated the code to use a more vectorized solution, having a 54% improvement in the performance. I maintained the chained loop solution for comparison purpose ( https://github.com/timotta/xclimf/blob/master/tests/looping_update.py )
  • For the objective function, the paper describes that it's not necessary to divide by the number of users, because it is only used for validating if the gradient ascending is still increasing after many interactions. But I made this division for interpretability purposes.


Results


Using the experimentation protocol of N random ratings by user in training and in the cross validation, applied to the MovieLens 1M dataset, I got MRR variying from 0.08 to 0.09 at the 50 iteration using the hyper-parameters described in the paper.


Using the top K experimentation protocol in the same dataset I got MRR varying from 0.2 to 0.26. I tried those two experimentation protocol with the Alternative Least Squares implemented at Spark and the maximum MRR I got was 0.01.

The sequence of experiments, and how to run can be seen at https://github.com/timotta/xclimf

Conclusions and future


Now we have a working xCLiMF implementation in python, but it is not feasible to train it with Globo.com dataset. Running it using MovieLens 1M dataset that have 6k users took 4 minutes. With MovieLens 20M dataset that have 130k users took more than one hour. Globo.com datasets are much bigger than that, if we count only the logged users, our dataset of users preferences on shows has more than 4 millions users, it would take more than 40 hours to run.

That's why my next step is implementing this same algorithm on Spark. Since the updating user by user step is independent, it is possible to scale it running in parallel on our hadoop cluster.

I appreciate any help, correction, suggestion or criticism

References


CLiMF: Learning to Maximize Reciprocal Rank with Collaborative Less-is-More Filtering
Yue Shi, Martha Larson, Alexandros Karatzoglou, Nuria Oliver, Linas Baltrunas, Alan Hanjalic
ACM RecSys 2012

xCLiMF: Optimizing Expected Reciprocal Rank for Data with Multiple Levels of Relevance
Yue Shia, Alexandros Karatzogloub, Linas Baltrunasb, Martha Larsona, Alan Hanjalica
ACM RecSys 2013

Collaborative Filtering for Implicit Feedback Datasets
Yifan Hu, Yehuda Koren, Chris Volinsky
IEEE, 2008

sábado, 28 de novembro de 2015

Dados abertos do Web Democracia

Nas minhas conversas com os participantes do RecSys de 2015 em Viena foi possível notar o esgotamento deles em relação aos dados existentes para análise. Os acadêmicos longe de grandes empresas como Linkedin, Google, Facebook e Netflix, estavam sempre em busca de mais dados para tunar e implementar novos algoritmos. Em resumo, ninguém aguenta mais o MovieLens.

Por essa razão resolvi disponibilizar todos os dados de avaliações de políticos no Web Democracia publicamente.

Para garantir a privacidade dos usuários utilizei a total aleatorização dos IDs de forma a evitar qualquer engenharia reversa, deixando então as avaliações anônimas.

A descrição completa dos dados de avaliações de políticos do Web Democracia você encontra aqui.

Um exemplo simples de análise desses dados com pandas pode ser visto aqui.

Agora então os quase meio milhão de avaliações de políticos do Web Democracia é mais uma fonte de informação e de um domínio bem diferente que os tradicionais livros e filmes.

segunda-feira, 14 de outubro de 2013

Meu primeiro aplicativo Android

Publiquei essa semana no Google Play meu primeiro aplicativo Android. O 9Gag Offline trata-se de um aplicativo que permite que você baixe os gags do site 9Gag para momentos em que não haja conexão com internet. Por exemplo se você for viajar, no avião você ficará isolado do mundo mas poderá rir bastante com os gags que estarão guardados no seu celular.

Já fazia mais ou menos uns seis meses que estava estudando esporadicamente o sistema operacional da Google e fazendo diversos testes. A um mês atrás resolvi fechar de vez o aplicativo e colocá-lo ao público. Deu pra aprender bastante sobre o framework e reviver os problemas de sincronia e concorrência que haviam na época em que programava para desktop com Delphi, Kylix e Java Swing.

Espero que gostem e se acharem qualquer problema ou tiverem alguma sugestão é só avisar. Para baixar o 9Gag Offline basta clicar aqui e ir ao Google Play.

quinta-feira, 25 de julho de 2013

Plugin de Fonética Portuguesa para ElasticSearch

O ElasticSearch possui um plugin fonético que abrange diversas regras e padrões. No entanto nenhuma dessas regras é boa o bastante para as peculiaridades da lingua portuguesa.

Pensando nisso e de posse de uma gramática portuguesa, forkei o repositório e criei um encoder com as regras de nosso estimado idioma lusitano. Como alguns meses depois ainda não obtive resposta alguma da equipe do plugin original, promovi então este encoder a um novo plugin: Portuguese Phonetic Plugin.

Para utilizá-lo você precisa clonar o projeto no github e instalá-lo:

git clone https://github.com/timotta/elasticsearch-fonetica-portuguesa.git
cd elasticsearch-fonetica-portuguesa
./script/install.sh ~/Programas/elasticsearch-0.20.5
Depois é preciso configurar um analyser em config/elasticsearch.yml:
index :
    analysis :
        analyzer :
            fonetico :
                type : custom
                tokenizer : standard
                filter : [ standard, lowercase, foneticaportuguesa_filter, asciifolding ]
        filter :
            foneticaportuguesa_filter:
                type : foneticaportuguesa
                replace : false
Com tudo configurado, você pode criar um novo indice usando este analyser, como é mostrado abaixo:
$ curl localhost:9200/comfonetica -XPUT -d '
{
  "mappings" :{
     "document" : {
        "analyzer" : "fonetico"
     }
   }    
}'
Com o indice criado e configurado é possivel verificar as transformações de texto da seguinte forma:
$ curl -XGET 'localhost:9200/comfonetica/_analyze?analyzer=fonetico&pretty=true' -d chiclete
{
  "tokens" : [ {
    "token" : "XICLETE",
    "start_offset" : 0,
    "end_offset" : 8,
    "type" : "",
    "position" : 1
  }, {
    "token" : "chiclete",
    "start_offset" : 0,
    "end_offset" : 8,
    "type" : "",
    "position" : 1
  } ]
Repare que a palavra se transformou em duas. Isso acontece porque a configuração replace do filter está como false.

Atualmente só testei o plugin com a versão 0.20.5 do elasticsearch, se testarem em outras versões peço que reporte no github. Além disso, nem todas as regras fonéticas foram implementadas, então se você precisar de alguma que esteja faltando, colabore ou solicite lá também.

terça-feira, 16 de julho de 2013

Complexidade Ciclomática com Pygenie recursivo

Pygenie é uma biblioteca python bem simples para calcular a complexidade ciclomática de seus método. É tão simples, mas tão simples que para projetos mais complexos é preciso scriptar um pouco para que todos os diretórios sejam analisados.

Para facilitar então a nossa vida aqui na empresa, fiz uma contribuição (com pouca esperança de ser aceita pois o projeto está parado a dois anos) para que seja possível obter os resultado de forma recursiva. Com esta contribuição é possivel informar o parâmetro -r que analisará recursivamente todos os arquivos .py dentro de um diretório.

$ pygenie complexity mylib -r

Se dentro de seu projeto houver algum arquivo ou diretório que você não deseja que seja analisado você pode utilizar um outro parâmetro adicionado, o -e, onde você informar um pattern para ser excluído. Por exemplo se houver um diretório de testes:

$ pygenie complexity mylib -r -e tests

Caso você deseje utilizar desde já pode instalar o pygenie através do meu fork e neste meio tempo tentar incentivar nosso amigo Matthew Von Rocketstein a aceitar o pull request.

SlimIt, Head.js e django compressor

Ao configurar o django compressor com o filtro do SlimIt, o arquivo do head.js comprimido pela templatetag compress era gerado com um caracter  ï ao ínicio. Utilizando o SlimIt na mão eu obtinha o seguinte erro:

$ slimit head.js
Illegal character '\xbb' at 1:1 after LexToken(ID,'\xef',1,0)
Illegal character '\xbf' at 1:2 after LexToken(ID,'\xef',1,0)

Criei uma issue no repositório do SlimIt acreditando ser um problema desta lib. E determinado a corrigir tal problema acabei descobrindo que a raíz deste era o Head.js. No arquivo fonte desta biblioteca javascript havia realmente um caracter estranho, que nenhum editor exibia, nem mesmo o Vi. No entanto, se abríssemos o arquivo via python com um simples:

open("head.js").read()

Víamos claramente o caracter escondido. Espantosamente o único editor que testei e que exibiu o caracter estranho foi o editor online do github.

Forked, pull resqueted e merged: Felizes para sempre.

quarta-feira, 21 de novembro de 2012

Liberando o GIL do python para paralelizar seu código com threads

No Python o Global Interpreter Locker impede que duas threads executem ao mesmo tempo. Uma thread só é executada quando nenhuma outra estiver executando. A solução mais comum para aproveitar todos os cores de uma máquina em python é abandonar threads e utilizar vários processos. No entanto há uma maneira de aproveitar todos os cores com threads no python. Para isso vamos precisar criar uma extensão em C.

Primeiro vamos criar uma extensão que não libere o GIL para podermos comparar e conferir a melhoria de performance depois. O pivô dessa extensão é a seguinte função:

static int reduce_com_gil(int max, int (*f)(int x, int y)) {
   int retorno = 0;
   int i;
   for(i=0; i < max; i++){
       retorno = (*f)(retorno, i);
   }
   return retorno;
}

Essa função faz algo similar ao que um reduce faria, mas indo de 0 ao valor indicado em max. Para cada iteração a função enviada como segundo parâmetro é executada. A idéia é causar um grande processamento para que meu core fique travado. O uso dela está descrito no código abaixo:

static PyObject *antigil_calcular_com_gil(PyObject *self) {
   int valor = reduce_com_gil(100*1000, *antigil_calculos);
   char numero [5000];
   sprintf(numero, "%d", valor );
   return Py_BuildValue("s", numero);
}


Repare que eu passo para a função reduce_com_gil o ponteiro da função antigil_calculos. Essa outra função faz diversos cálculos a cada iteração do reduce. O nome antigil é o nome da extensão de exemplo. O código completo da extensão pode ser visto aqui.

Instalada a extensão, podemos testar a performance da lib com o seguinte código:

import antigil
antigil.calcular_com_gil()


E o seguinte comando:

$ time python teste.py
real 0m2.702s
user 0m2.692s


Mas o que a gente quer é saber como se comportam as threads. No caso o seguinte script abre 4 threads para aproveitar os 4 cores da minha máquina:

import antigil
from threading import Thread

threads = []
for i in xrange(4):
   t = Thread(target=antigil.calcular_com_gil)
   t.start()
   threads.append(t)

for t in threads:
   t.join()


No entando, acaba não aproveitando. Repare que ao executar 4 threads, o GIL age e impede que duas sejam executadas ao mesmo tempo. Dessa forma só um core da máquina é aproveitado. Isso pode ser observado pelo tempo total que é aproximadamente quatro vezes o tempo de execução de uma:

$ time python teste.py
real 0m10.910s
user 0m10.881s


Bom, vamos então à extensão não bloqueante. A chave do sucesso nesse caso são as macros Py_BEGIN_ALLOW_THREADS e Py_END_ALLOW_THREADS que respectivamente liberam o GIL e obtem o GIL de volta. Essas macros estão definidas em Python.h. O código da função reduce ficaria assim:

static int reduce_sem_gil(int max, int (*f)(int x, int y)) {
   int retorno = 0;
   Py_BEGIN_ALLOW_THREADS
   int i;
   for(i=0; i < max; i++){

       retorno = (*f)(retorno, i);
   }
   Py_END_ALLOW_THREADS
   return retorno;
}


Pronto, basta criar a função antigil_calcular_sem_gil similar à antigil_calcular_com_gil, utilizando a função reduce_sem_gil e então podemos repetir o teste. No caso parametrizei o script de teste para que você possa escolher qual função deseja executar:

import antigil
from threading import Thread
import sys

if 'com-gil' in sys.argv:
    calcular = antigil.calcular_com_gil
elif 'sem-gil' in sys.argv:
    calcular = antigil.calcular_sem_gil
else:
    print "Informar com-gil ou sem-gil"
    exit(0)

threads = []
for i in xrange(4):
   t = Thread(target=calcular)
   t.start()
   threads.append(t)

for t in threads:
   t.join()


O resultado é bem animador e mostra bem que o código rodou em paralelo:

$ time python teste.py sem-gil
real 0m3.414s
user 0m13.413s


Como o código utiliza apenas CPU, sem IO algum, ao aumentar para 8 threads, mesmo a versão que libera o GIL dobra de tempo pois só tenho disponível 4 cores na minha máquina. No entanto acredito que se fizer alguma operação de IO entre as macros Py_BEGIN_ALLOW_THREADS e Py_END_ALLOW_THREADS outras threads poderão ser executadas no caminho. Isso eu ainda preciso validar.

Só é preciso ter muito cuidado pois código entre essas macros está em território perigoso. A alteração de váriaveis globais ou ponteiros que podem ser compartilhados entre outras threads podem causar erros inesperados a qualquer momento. Portanto, é importante utilizar somente váriaveis locais e dados copiados.

O código completo da extensão em C antigil pode ser visto aqui.