Previsão de clique em anúncios em redes sociais

01 · CONTEXTO

Por que prever cliques sustenta um sistema de anúncios

Em anúncios online, o anunciante só dá lances e paga por respostas mensuráveis do usuário, como cliques. A eficiência do leilão de anúncios depende da precisão e da calibração da previsão de clique.

O paper do Facebook parte de um requisito claro: o sistema de previsão precisa ser robusto, adaptável e capaz de aprender com volumes massivos de dados. No Facebook os anúncios não se associam a uma consulta; eles especificam segmentação demográfica e de interesses, e por isso o volume de anúncios elegíveis a cada visita pode ser maior do que na busca patrocinada.

Para lidar com muitos anúncios candidatos por pedido, o paper descreve uma cascata de classificadores de custo computacional crescente. O foco dele, e deste caso, é o último estágio: o modelo de previsão de cliques que gera as previsões para o conjunto final de candidatos.

02 · MÉTRICAS

Medir bem: entropia normalizada e calibração

O paper avalia a precisão da previsão, e não métricas ligadas diretamente a lucro e receita. As duas métricas principais são a entropia normalizada (NE) e a calibração.

A NE é a perda logarítmica preditiva normalizada pela entropia do CTR de fundo, e quanto menor o valor, melhor a previsão. Já a calibração é a razão entre o CTR médio estimado e o CTR empírico, isto é, entre os cliques esperados e os cliques realmente observados.

A calibração importa porque uma previsão precisa e bem calibrada do CTR é essencial para o sucesso de lances e leilões online. O AUC mede só a qualidade do ranking, sem considerar a calibração, enquanto a NE mede a qualidade das previsões e reflete a calibração de forma implícita.

03 · O MODELO HÍBRIDO

Árvores impulsionadas alimentando uma regressão logística

O modelo do paper concatena árvores de decisão impulsionadas e um classificador linear esparso e probabilístico, e supera cada um desses métodos isolado em mais de 3%.

Antes das árvores, o paper descreve duas transformações simples para um classificador linear. Uma é discretizar um atributo contínuo e tratar o índice da faixa como atributo categórico. A outra é criar atributos em tupla, que para categóricos significa, na força bruta, o produto cartesiano; nem toda combinação é útil e as inúteis podem ser podadas.

1. A visita ao Facebook dispara um pedido de anúncios candidatos ao ranker.

2. Os atributos da impressão passam por árvores de decisão impulsionadas, que funcionam como transformação de atributos.

3. A saída de cada árvore vira um atributo categórico, cujo valor é o índice da folha em que a instância cai, e segue como entrada do classificador linear esparso.

4. Ajustar o classificador linear a esse vetor binário equivale a aprender pesos para o conjunto de regras que os caminhos das árvores representam.

Isoladas, a regressão logística e as árvores têm precisão comparável, com a regressão logística um pouco melhor; é a combinação que dá o salto de precisão. As transformações por árvores reduzem a NE em mais de 3,4% em relação ao modelo sem elas, enquanto a maioria dos experimentos de engenharia de atributos só reduz a NE em uma fração de ponto percentual.

04 · FRESCOR DOS DADOS

Retreinar sempre: o modelo envelhece

O paper treina um modelo em um dia e o avalia nos dias seguintes. A precisão cai à medida que o atraso entre treino e teste aumenta, e treinar por dia em vez de por semana reduz a NE em cerca de 1%. Os autores concluem que vale retreinar diariamente.

As árvores são treinadas em lote, o que pode levar mais de 24 horas com um único núcleo de CPU para centenas de árvores e centenas de milhões de instâncias; na prática, a concorrência numa máquina multinúcleo reduz isso a poucas horas. O paper indica que as árvores podem ser treinadas a cada dia ou a cada par de dias, enquanto o classificador linear pode ser treinado em quase tempo real com aprendizado online.

Para o treino online do classificador linear, o paper compara esquemas de taxa de aprendizado do gradiente descendente estocástico. A taxa por coordenada teve a melhor precisão, com NE quase 5% menor do que a taxa por peso, que teve o pior desempenho entre as opções.

O paper também compara essa regressão logística (LR) com o BOPR, um esquema bayesiano de aprendizado online para regressão probit.

Como o BOPR dá a distribuição preditiva completa, ela pode servir para calcular percentis usados em esquemas de explorar e aproveitar.

05 · ONLINE JOINER

Gerando o rótulo de clique em tempo real

Para treinar o classificador linear online é preciso gerar dados de treino em tempo real. O paper apresenta um sistema experimental, o online joiner, cuja operação crítica é juntar os rótulos (clique ou sem clique) às entradas de treino (impressões de anúncios) de forma online, e que entrega o fluxo de treino a uma infraestrutura chamada Scribe.

O rótulo positivo é bem definido, o clique, mas não existe um botão de sem clique. Uma impressão recebe o rótulo negativo se o usuário não clicar depois de um período fixo e suficientemente longo, e o tamanho dessa janela de espera precisa ser ajustado com cuidado. Esse é o problema dos labels atrasados: o rótulo negativo só pode ser decidido depois de esperar.

1. Ao visitar o Facebook, o usuário dispara um pedido de anúncios ao ranker; em paralelo, cada anúncio e os atributos usados no ranking entram no fluxo de impressões.

2. Se o usuário clica no anúncio, o clique entra no fluxo de cliques.

3. O joiner faz uma junção distribuída entre os dois fluxos, com o identificador do pedido como componente principal, e usa uma HashQueue: fila FIFO como janela de buffer e mapa hash para rotular impressões com acesso rápido.

4. A impressão rotulada só sai para o fluxo de treino depois que a janela de junção expira; se nenhum clique foi juntado, ela sai como exemplo negativo.

5. O treinador aprende continuamente do fluxo de treino e publica modelos novos periodicamente para o ranker.

6. Como proteção, o paper cita mecanismos de detecção de anomalias, por exemplo desconectar o treinador do joiner se a distribuição dos dados de treino mudar de repente.

Uma janela longa demais atrasa os dados de treino em tempo real e aumenta a memória usada para guardar impressões à espera do clique. Uma janela curta demais perde parte dos cliques, porque a impressão correspondente pode já ter sido descartada e rotulada como sem clique.

Esse corte afeta a cobertura de cliques, a fração de todos os cliques juntados com sucesso às impressões. Sem cobertura total, o conjunto de treino fica enviesado, com um CTR empírico um pouco menor que a verdade. O paper relata que é fácil reduzir esse viés a casas decimais de um ponto percentual com janelas de memória administrável.

Nesse arranjo experimental, o treinador aprende continuamente do fluxo de treino e publica modelos novos periodicamente para o ranker. Isso forma um ciclo fechado e curto, em que mudanças na distribuição dos atributos ou no desempenho do modelo podem ser capturadas, aprendidas e corrigidas em sucessão rápida.

O paper sugere detecção de anomalias como defesa: por exemplo, desconectar automaticamente o treinador online do joiner se a distribuição dos dados de treino mudar de forma abrupta.

06 · ATRIBUTOS, CUSTO E CALIBRAÇÃO

O que mais pesa e como conter o custo

O paper separa os atributos em dois tipos. Os de contexto dependem só de informação atual sobre onde o anúncio será exibido, como o dispositivo ou a página atual. Os históricos dependem de interações anteriores com o anúncio ou o usuário, como o CTR do anúncio na última semana ou o CTR médio do usuário.

Poucos atributos concentram o poder explicativo: os 10 mais importantes respondem por cerca de metade da importância total, e todos eles são históricos.

A latência da previsão também cresce com o número de árvores: mais árvores deixam a previsão mais lenta, com retorno decrescente, já que quase toda a melhora de NE vem das primeiras 500 árvores.

Para controlar o custo de treino, uma técnica comum é reduzir o volume de dados. A subamostragem uniforme das linhas é fácil de implementar e o modelo resultante serve sem modificação. Com apenas 10% dos dados, a NE perde só 1% em relação ao conjunto completo, sem perda de calibração.

1. Um dia de impressões pode ter uma quantidade enorme de instâncias, e reduzir o volume dos dados de treino é uma técnica comum para controlar o custo.

2. A subamostragem de negativos ataca o desbalanceamento de classes; o paper relata que ela pode acelerar o treino e melhorar o desempenho do modelo.

3. Um modelo treinado com negativos subamostrados também calibra a previsão no espaço subamostrado.

4. É preciso recalibrar o modelo para o tráfego ao vivo, de modo que o ranker receba previsões de volta ao CTR real.