Calculando a Probabilidade de Cliques em 4 Milhões de Anúncios Usando Métodos para Big Data

A Avazu é uma plataforma de publicidade que oferece anúncios em sites e aplicativos móveis. Um dos maiores desafios do ramo é determinar qual o anúncio com a maior relevância para o usuário. Se o anúncio estiver de acordo com os interesses do usuário, a chance dele clicar é maior, e isso aumenta os lucros tanto da plataforma quanto do anunciante, que terá um cliente em potencial visitando seu site.

Machine Learning têm sido usado por várias empresas que oferecem anúncios no formato pay-per-click. Ou seja, que são pagas pelo anunciante a cada clique no anúncio oferecido. Dentre as aplicações, a criação de modelos inteligente para calcular a probabilidade de um usuário clicar no anúncio, baseando-se em:

Informações de perfil: localização, dispositivo utilizado;
Informações do anunciante: categoria, tamanho e cor do anúncio;

E também dados sobre o site ou aplicativo no qual o anúncio é exibido.

Neste repositório disponibilizo o código original para a implementação do FTRL Proximal pelo usuário tinrtgu do Kaggle, baseado no paper desenvolvido pelo Google, e também o código modificado para obter meu melhor modelo individual.

Descrição dos dados

Nesta competição a Avazu ofereceu um dataset com 10 dias de informações, tanto sobre os usuários, quanto sobre os anunciantes e as plataformas de exibição. O objetivo era prever a probabilidade de um visitante, em um aplicativo ou site, clicar no anúncio exibido. Como teste, foi reservado um dia, 31/10/2014, para avaliar o modelo.

O training set possuía cerca de 40 milhões de linhas, e o teste cerca de 4 milhões. Além disso, é um problema de alta dimensionalidade, com mais de 1 milhão de variáveis independentes.

A métrica escolhida para avaliação foi a LogLoss, que pune previsões incorretas que são muito confiantes. Um detalhe é que existia um desequilíbrio entre a proporção de exemplos positivos e negativos, e esta métrica favorece acertos na classe com maior representação (no caso, os negativos).

Modelo base

Atribuir uma probabilidade de 50% a todos os exemplos oferecia uma log loss de 0,6932.

O primeiro modelo, mais simples, que testei foi uma regressão logística com Vowpal Wabbit, sem regularização e com apenas 1 passe sobre os dados. Ele oferecia a log loss de 0,3993.

Limpeza dos dados

Devido ao grande número de variáveis independentes, algumas delas acabam aparecendo pouco no dataset, e podem atrapalhar a classificação. Como neste caso o modelo utilizado foi a regressão logística, e ela é sensível a outliers, a remoção deles poderia melhorar a performance.

Desta maneira, fiz dois testes: remover os outliers, ou agrupá-los sob uma variável “rara”.

A escolha que melhorou significativamente a log loss foi agrupar as variáveis que apareciam menos de 5 vezes sob uma variável comum. A regressão logística, sem otimização, aplicada ao dataset “limpo” alcançou uma log loss de 0,3954.

Problemas com validação

Nesta competição um dos grandes problemas era encontrar uma maneira adequada de fazer validação. Estes são dados que mudam rapidamente, novas variáveis entram, e antigas deixam de ser utilizadas em questão de dias ou semanas, então é natural que haja esta dificuldade para chegar a um consenso sobre a performance exata do modelo.

Algumas formas foram discutidas no fórum da competição, e duas delas foram bastante utilizadas:

Holdout

Nesta modalidade, a cada N exemplos utilizados para treinar o modelo, é calculada a log loss no exemplo N+1. Após passar pelo dataset inteiro, é calculada a média. Nas minhas tentativas este se mostrou um método bastante otimista quanto à realidade.

Validação nos últimos dias

Neste caso, por se tratar de dados com dependência temporal, o modelo era treinado excluindo-se o último, ou os dois últimos dias do dataset, que eram utilizados para validação. Esta alternativa parecia ser mais precisa do que a outra, mas não era robusta à escolha de interações entre as variáveis, então era necessário ter cuidado com o overfitting nestes casos.

Criação de variáveis

Todas as variáveis desta competição eram binárias, e algumas delas eram anônimas, então eu não tinha informações sobre o que elas representavam. Desta maneira, testei duas alternativas para criar novas variáveis que pudessem colaborar na classificação.

Frequência

Uma das alternativas foi contar quantas vezes cada variável aparecia no dataset e usar este valor na classificação. Esta tentativa não deu certo, e piorou o desempenho. Uma alternativa que apresentou melhora, mas nada significativo, foi criar uma variável indicando se um determinado exemplo possuía mais ou menos de 100 ocorrências.

Modelos utilizados

Regressão Logística – Vowpal Wabbit

Aproveitei esta oportunidade para conhecer uma nova ferramenta: Vowpal Wabbit. Uma implementação rápida de algoritmos com funções convexas de Machine Learning tanto para regressão, quanto para classificação. Só para lembrarmos, a regressão logística “pura”, sem limpeza dos dados, apresentava uma log loss de 0,3993. Após a limpeza este número caiu para 0,3954.

SVM calibrado – Vowpal Wabbit

Como era necessário enviar uma lista de probabilidades para o Kaggle, tentei utilizar a distância dos dados para o hiperplano do SVM como inputs, tanto para uma regressão logística (inspirado em Platt’s scaling), quanto para uma regressão isotônica, disponível no scikit-learn. São dois modos populares de calibrar um SVM para que ele nos dê probabilidades. As duas não apresentaram uma boa melhora na pontuação.

Follow the Regularized Leader Proximal (FTRL Proximal)

Paper Google – Ad Click Prediction (em inglês)

Este foi o algoritmo que me ajudou a melhorar bastante a log loss. Ele foi implementado por um dos competidores e disponibilizado no fórum da competição. Desenvolvido pelo Google para a mesma tarefa de calcular a probabilidade de clique num anúncio, baseado em informações do usuário, ele cria uma representação mais esparsa dos dados, e acaba sendo mais robusto contra outliers. Neste paper o autor descreve a implementação e as características dele comparado a outros algoritmos utilizados para a mesma tarefa.

Pode-se dizer que ele é basicamente uma regressão logística com ajustes para não precisar utilizar tanta memória para armazenar os pesos, e também uma forma de otimização que força os pesos menos significativos a tomarem o valor de zero absoluto. Ou seja, num problema com milhões de variáveis como este, desconsidera aquelas que não são realmente importantes. Faz a seleção de atributos automaticamente.

Com os dados limpos, uma leve otimização, e 3 passes sobre os dados, este modelo atingiu log loss de 0,3925.

Redes Neurais

Fiz uma tentativa de classificação com redes neurais tanto no Vowpal Wabbit quanto com uma implementação própria. No Vowpal Wabbit a rede neural possui apenas um hidden layer com ativação sigmóide. Não houve melhora.

Criei, em Python, uma rede neural com unidades de ativação ReLu. Este tipo de ativação tem sido bastante utilizado na área de Deep Learning, devido a não ter o problema de gradientes explodindo ou desaparecendo, além de favorecerem uma representação de dados esparsa. Em alguns casos o resultado é equivalente, ou melhor, do que redes previamente ativadas com treinos não supervisionados.

Utilizei apenas um hidden layer, e neste caso, houve uma melhora na validação dos dados, mas ela não se traduziu em melhora na pontuação oficial da competição. Talvez utilizar mais de um hidden layer, e começar a entrar na área de Deep Learning tivesse ajudado, mas eu não tive tempo para testar.

O fato de só termos variáveis binárias também dificulta o trabalho da rede neural em encontrar uma representação adequada, e aprender interações que possam ser relevantes para a classificação. Usar variáveis numéricas, derivadas das originais, poderia facilitar o trabalho

A melhor rede neural, nos dados originais limpos, com 30 neurônios no hidden layer, e ativação ReLu, atingiu a log loss de 0,3937.

Interação entre variáveis

Outra alternativa era criar interações entre duas ou mais variáveis. Isso era feito simplesmente criando uma variável que indicasse a presença de combinações entre variáveis. Num primeiro momento tentei a interação entre todas as duplas de variáveis, o que piorou o desempenho.

Fiz uma nova tentativa, desta vez criando manualmente combinações que me pareciam relevantes (representando o acesso de um determinado usuário a um aplicativo, por exemplo). E elas acabaram por melhorar o modelo, reduzindo a log loss para 0,3897.

Estas tentativas foram feitas utilizando o código FTRL Proximal.

Hashing trick

Num problema com muitas variáveis independentes como este surge a dificuldade de armazenar pesos para todas elas na memória. Apesar deste ser um dataset pequeno quando falamos de big data, já requer o uso do hashing trick. Esta técnica consiste em fazer o hashing das variáveis e atribuir pesos aos buckets, em vez de diretamente a cada variável. Neste caso, por termos apenas variáveis binárias, é bastante fácil utilizar.

Após feito o hash, utiliza-se uma lista com os índices dos buckets que devem ter seus pesos atualizados naquela iteração. Existe o risco de colisão, e quanto maior o número de buckets, menor este risco. Mesmo assim, na prática não há uma perda significativa de performance por esta razão, por isso esta se tornou uma técnica amplamente utilizada em problemas que envolvem alta dimensionalidade dos dados.

Tanto o Vowpal Wabbit, quanto o FTRL Proximal utilizam esta técnica.

Ensemble

É quase impossível pontuar bem numa competição do Kaggle sem juntar modelos num ensemble. Eu não conheço uma competição que os participantes nas melhores posições não tenham usado esta técnica. Basicamente, se você tiver modelos que tenham uma precisão parecida, mas erros diferentes, há uma boa probabilidade que, se juntar as previsões deles, você terá uma previsão melhor.

Visite este artigo para saber mais sobre maneiras de usar ensemble learning para melhorar seus modelos de machine learning.

Modelos em subdivisões dos dados baseados nas variáveis independentes

A primeira tentativa de ensemble foi criar modelos individuais para determinadas subdivisões do dataset. Por exemplo, criar 24 datasets, cada um contendo apenas os exemplos gerados numa determinada hora, ou criar um dataset para cada ID de aplicativo, e treinar modelos individuais neles. Depois, subdividir da mesma maneira o test set e obter previsões destes modelos individuais.

Em alguns casos, se as subdivisões forem feitas em grupos que realmente apresentem diferença entre eles, a performance pode melhorar bastante. No nosso caso, por exemplo, utilizando apenas os modelos divididos por hora, a log loss da regressão logística, antes da limpeza dos dados, caiu para 0,3976.

Após criar vários modelos baseados em subgrupos que pareciam ser diferentes entre eles, o ensemble final, fazendo a média simples de 8 modelos, atingiu uma log loss de 0,3935.

Modelos baseados em interações aleatórias das variáveis

Outra alternativa para criar ensembles é utilizar variáveis diferentes para cada modelo. Após verificar que algumas interações melhoravam a pontuação utilizando o FTRL Proximal, decidi criar um script que testava o efeito que uma interação teria na pontuação do ensemble. Apesar de interessante, deve-se tomar bastante cuidado com o overfitting.

Cada modelo selecionava uma interação e testava se o desempenho de um ensemble entre ele, e alguns com outras interações, melhorava. Esta tentativa gerou 5 modelos lineares com diferentes combinações de variáveis, que juntos, fazendo a média simples, atingiram uma log loss de 0,3888.

Juntando os melhores os modelos

No fim, juntei vários modelos que apresentavam uma boa pontuação, e cheguei à log loss de 0,3878 que garantiu a 42ª posição, entre as 3% melhores soluções. A diferença entre a log loss desta solução e da vencedora foi de 0,0087.

Outras ideias e solução vencedora

Após o término da competição é comum que os participantes com as melhores colocações divulguem seus modelos e ideias que contribuíram para alcançar uma boa performance.

Neste caso, além dos métodos descritos aqui, duas aproximações se destacaram: atributos que levavam em conta fatores temporais, como o número de visitas de um usuário a um site ou aplicativo na última hora; quantidade de visitas no mesmo dia; e utilizar atributos relacionados à contagem de vezes que a variável, ou interações entre variáveis, apareciam.

Saber utilizar as características temporais dos dados parece ter favorecido bastante os melhores colocados.

Leave a Reply

Your email address will not be published. Required fields are marked *