Capítulo 12: Otimização de cliques em anúncios

Visão geral do capítulo

Este capítulo aborda o problema de otimizar a política de definição de lances para maximizar retornos em plataformas de e-commerce como Google e Facebook. Essas plataformas executam leilões sofisticados para garantir que estão recebendo o valor de mercado integral pelos anúncios que exibem. A modelagem do problema, e o design das políticas, é complicada pela necessidade de representar três formas de incerteza: a probabilidade de vencermos o lance que fazemos em um anúncio, o resultado de vencermos ou não o lance, e a receita obtida ao vencer o lance.

Exploramos três políticas. As duas primeiras são relativamente simples: uma política gulosa que escolhe o melhor lance dadas nossas estimativas atuais de todas as quantidades incertas, e uma versão aleatorizada da política gulosa que incentiva a exploração. A terceira é mais sofisticada: conhecida como “gradiente de conhecimento”, ela maximiza o valor da informação obtida ao fazer um determinado lance. Isso requer encontrar uma expectativa da melhoria a partir do que aprendemos com um dado lance. O gradiente de conhecimento envolve cálculos de probabilidade relativamente sofisticados.

Narrativa

Empresas que fazem publicidade em sites da internet como o Google precisam dar lances para colocar seus anúncios em uma posição visível (isto é, no topo da lista de anúncios patrocinados). Quando um cliente digita um termo de busca, o Google identifica todos os licitantes que listaram o mesmo termo de busca (ou similar) em sua lista de palavras-chave de anúncios. O Google então pega todas as correspondências, as ordena de acordo com quanto cada participante ofertou, e realiza um leilão. Quanto maior o lance, maior a probabilidade de seu anúncio ser posicionado perto do topo da lista de anúncios patrocinados, o que aumenta a probabilidade de um clique. A Figura 12.1 é um exemplo do que é produzido após inserir os termos de busca “hotels in baltimore md.”

Se um cliente clica no anúncio, há um retorno esperado que reflete a quantia média que um cliente gasta ao visitar o site da empresa. O problema é que não sabemos qual é a curva de resposta ao lance. A Figura 12.2 reflete uma família de possíveis curvas de resposta. Nosso desafio é testar diferentes lances para aprender qual curva é a correta.

Começamos assumindo que podemos ajustar o lance após cada leilão, o que significa que aprendemos apenas uma única resposta (o cliente clicou ou não no link). É possível que o cliente tenha olhado para um link exibido e decidido não clicar nele, ou nosso lance pode ter sido tão baixo que nem sequer estávamos na lista de anúncios exibidos.

Nosso desafio é projetar uma política para definir os lances. O objetivo é maximizar a receita líquida, incluindo o que ganhamos com a venda de nossos produtos ou serviços, menos o que gastamos com cliques em anúncios.

Enquadrando o problema

As respostas às nossas três perguntas de enquadramento são:

• Métricas: Maximizar a receita líquida esperada com a venda de produtos anunciados na plataforma, menos o valor pago para veicular o anúncio.
• Decisões: Quanto dar de lance pelo anúncio.
• Incertezas: Se um lance é bem-sucedido, e o valor da receita recebida com um lance bem-sucedido.

Modelo básico

Vamos assumir que usamos algum tipo de modelo parametrizado para capturar a probabilidade de que um cliente clique em um anúncio. No mínimo, essa probabilidade dependerá de quanto oferecemos pelo anúncio – quanto maior o lance, mais alto o anúncio aparecerá na lista de anúncios patrocinados, o que aumenta a probabilidade de um cliente clicar nele. Seja $K^n = 1$ se o $n$-ésimo cliente clicar no anúncio. Seja

onde $Prob[K^{n+1}=1\vert \theta=\theta_k,x]$ será descrito por uma função logística dada por

Essa função é parametrizada por $\theta = (\theta^{const}, \theta^{bid})$. Não sabemos qual é $\theta$, mas vamos assumir que é um dentre um conjunto amostrado $\Theta = \lbrace \theta_1, \ldots,\theta_K\rbrace $.

Variáveis de estado

O estado inicial $S^0$ inclui $\Theta = \lbrace \theta_1, \ldots, \theta_K\rbrace $, o conjunto de valores possíveis que $\theta$ pode assumir; e $\Rbar^0$, a estimativa inicial da receita obtida quando um cliente clica em um link.

As variáveis de estado dinâmicas $S^n$ incluem $p^n_k$, a probabilidade de que o verdadeiro $\theta = \theta_k$, com $p^n = (p^n_k)_{k=1}^K$; e $\Rbar^n$, a estimativa da receita obtida com um clique no anúncio após $n$ leilões.

Nossa variável de estado dinâmica, então, é

Observe que podemos criar uma estimativa pontual de $\theta$ após $n$ observações usando

mas esta é uma estatística que podemos calcular a partir da informação em $S^n$, portanto não colocamos $\thetabar^n$ na variável de estado.

Variáveis de decisão

Nossa única variável de decisão é o lance, que definimos como $x^n$, o lance (em ＄ por clique) para o $(n+1)$-ésimo leilão. Como antes, deixamos $X^\pi(S^n)$ ser nossa política genérica que nos dá o lance $x^n$ em função da informação disponível para nós, representada por $S^n$, o que significa que escreveríamos

Assumimos que a política impõe quaisquer restrições, como garantir que o lance não seja negativo ou muito grande.

Informação exógena

Em nosso modelo inicial, observamos apenas os resultados de um único leilão, que modelamos usando:

e $\Rhat^{n+1}$, a receita obtida no $n+1$-ésimo leilão. Isso significa que nossa variável completa de informação exógena é

Função de transição

A função de transição para este problema parecerá muito mais complicada do que outras neste volume, porque estamos atualizando crenças sobre a incerteza no vetor de parâmetros $\theta$. Precisamos enfatizar que todas as equações de transição podem ser codificadas com relativa facilidade.

Vamos atualizar nossa receita estimada quando um cliente clica no anúncio usando:

Assim, só atualizamos nossa receita estimada quando obtemos um clique. O parâmetro $\alpha^{lrn}$ é um parâmetro de suavização (às vezes chamado de “taxa de aprendizado”) entre 0 e 1 que fixamos de antemão.

Em seguida, tratamos da atualização das probabilidades $p^n_k$. Deixamos $H^n$ ser o histórico de estados, decisões e informação exógena

Usamos isso para escrever

A forma de ler o condicionamento no histórico $H^n$ é “$p^n_k$ é a probabilidade $\theta = \theta_k$ dado o que sabemos após $n$ observações.” Em seguida, usamos o teorema de Bayes para escrever

Lembre-se de que o histórico $H^n$ inclui a decisão $x^n$ que, dada uma política para tomar essas decisões, é diretamente uma função do estado $S^n$ (que por sua vez é uma função do histórico $H^n$). Agora usamos nossa curva logística na equação $\eqref{eq:adclicklogisticregression}$ para escrever

Em seguida, observamos que

Finalmente, observamos que o denominador pode ser calculado usando

Nosso uso de uma representação amostrada dos possíveis resultados de $\theta$ está nos ajudando aqui. Mesmo que $\theta$ tenha apenas duas dimensões (como é o caso aqui, mas apenas por enquanto), realizar uma integral bidimensional sobre uma distribuição multivariada para $\theta$ seria problemático.

As equações $\eqref{eq:adclicktransition2a}$–$\eqref{eq:adclicktransition2c}$ nos permitem calcular nossa equação de atualização bayesiana para as probabilidades em $\eqref{eq:adclicktransition2}$. As equações $\eqref{eq:adclicktransition1}$–$\eqref{eq:adclicktransition2}$ compõem nossa função de transição

Função objetivo

Começamos escrevendo a função de lucro de um único período como

o que significa que não ganhamos nada se o cliente não clicar no anúncio ($K^{n+1} = 0$). Se o cliente clicar no anúncio ($K^{n+1} = 1$), recebemos receita dada por $\Rhat^{n+1}$, mas também temos que pagar o que oferecemos pelo clique no anúncio, dado pelo nosso lance $x^n$.

Acabaremos tomando a contribuição esperada, que escrevemos como

Há três variáveis aleatórias ocultas na expectativa:

• $\theta$, com distribuição $p^n = (p^n_1, \ldots, p^n_K)$ (contida em $S^n$).
• $K^{n+1}$, onde $P^{click}(\theta,x) = Prob[K^{n+1}=1\vert \theta,x]$.
• $\Rhat^{n+1}$, que observamos a partir de alguma distribuição desconhecida se $K^{n+1}=1$, e onde $\Rhat^{n+1}=0$ se $K^{n+1}=0$ (não obtemos nenhuma receita se o cliente não clicar no anúncio).

Podemos então decompor a expectativa em três expectativas aninhadas:

Começamos tomando a expectativa sobre $\Rhat$ onde simplesmente usamos $\E \lbrace \Rhat^{n+1}\vert S^n\rbrace = \Rbar^n$ (lembre-se de que $\Rbar^n$ está na variável de estado $S^n$), o que nos permite escrever

Em seguida, vamos tomar a expectativa sobre $K^{n+1}$ para um dado $\theta$ usando

onde usamos o fato de que $(\Rbar^n - x^n) K^{n+1}=0$ se $K^{n+1}=0$.

Finalmente, tomamos a expectativa sobre $\theta$ usando

Vamos deixar $\Cbar(S^n,x)$ ser a contribuição esperada, ou seja,

Nossa função objetivo agora pode ser escrita como

Observe que o condicionamento em $S_0$ é como comunicamos nossa priori $p^0_k = Prob[\theta=\theta_k]$ ao modelo. Como antes, aproximaríamos a expectativa fazendo uma média sobre amostras simuladas do valor verdadeiro de $\theta$, e dos cliques observados $K^n$ e receitas $R^n$.

Modelando a incerteza

Temos três formas de incerteza: o clique no anúncio $K^{n+1}$, a receita que recebemos $\Rhat^{n+1}$ se $K^{n+1}=1$, e então o valor verdadeiro de $\theta$. Vamos assumir que simplesmente observamos $\Rhat^{n+1}$ a partir de um fluxo de dados real, o que significa que não precisamos de um modelo de probabilidade formal para essas variáveis aleatórias. Assumimos que $K^{n+1}$ é descrito por nossa função logística

mas é importante reconhecer que esta é apenas uma curva ajustada. Os valores de $K^{n+1}$ são observados a partir de dados, o que significa que não temos garantia de que a distribuição corresponda precisamente à nossa regressão logística.

Finalmente, assumimos que $\theta \in \Theta = \lbrace \theta_1, \ldots, \theta_K\rbrace $, o que também é uma aproximação. Existem maneiras de relaxar a exigência de um conjunto amostrado, mas a lógica se torna um pouco mais complicada sem agregar muito valor educacional.

Projetando políticas

Vamos explorar três políticas de aprendizado:

• Exploração pura (pure exploitation) – Aqui sempre colocamos o lance que parece ser o melhor de acordo com nossas estimativas atuais.
• Uma política de excitação – Introduzimos exploração (exploration) em nossa política de exploração pura adicionando um termo de ruído aleatório que força o sistema a explorar regiões próximas às áreas que consideramos melhores (isso é popular em engenharia, onde estados e decisões são contínuos).
• Uma política de valor da informação – Vamos maximizar o valor da informação obtida ao fazer um lance e aprender o resultado.

Exploração pura

O ponto de partida de qualquer política online deve ser a exploração pura, o que significa fazer o melhor que pudermos. Para calcular isso, começamos usando

Para encontrar o melhor lance, encontramos (após um pouco de álgebra) a derivada em relação ao lance $x$

onde

Agora queremos encontrar o lance $x^\ast $ onde

A Figura 12.3 mostra $\frac{d \Cbar(x\vert \theta)}{d x}$ versus o lance $x$, mostrando o comportamento de começar positivo e transicionar para negativo. O ponto onde é igual a zero seria o lance ótimo, um ponto que pode ser encontrado numericamente com bastante facilidade. Seja $X^{explt}(S^n)$ o lance $x^\ast $ que satisfaz $d \Cbar(x)/dx = 0$.

Isso significa que temos que executar um algoritmo numérico para calcular a política. Esta é uma política gulosa que se enquadra na classe CFA, mas sem nenhum parâmetro ajustável.

Uma política de excitação

Uma possível limitação de nossa política de exploração pura é que ela ignora o valor de tentar uma gama mais ampla de lances para ajudar no processo de aprendizado dos valores corretos de $\theta$. Uma estratégia popular é adicionar um termo de ruído, conhecido em engenharia como “excitação,” dando-nos a política

onde $\varepsilon(\rho) \sim N(0,\rho^2)$. Nesta política, $\rho$ é nosso parâmetro ajustável que controla a quantidade de exploração na política. Se for muito pequeno, pode não haver exploração suficiente. Se for muito grande, escolheremos lances distantes do ideal, possivelmente sem nenhum benefício do aprendizado.

Uma política de valor da informação

As políticas de exploração pura e de excitação que acabamos de introduzir são ambas relativamente simples. Agora vamos considerar uma política que maximiza o valor da informação no futuro. Isso parece uma ideia razoável, mas requer que pensemos sobre como a informação agora afeta qual decisão podemos tomar no futuro, e isso será um pouco mais difícil.

Nossa política de exploração assume que os parâmetros estimados $\theta^n$ após $n$ experimentos são o valor correto, e escolhe um lance com base nessa estimativa. Agora imagine que fazemos um lance $x^n=x$ e observamos $K^{n+1}$ e $\Rhat^{n+1}$, e usamos essa informação para obter uma estimativa atualizada de $\theta^{n+1}$ assim como de $\Rbar^{n+1}$. Podemos então usar essas estimativas atualizadas para tomar uma decisão melhor. Queremos escolher o lance $x$ que nos dá a maior melhora no valor da informação a partir de uma decisão, reconhecendo que não sabemos o resultado de $W^{n+1} = (\Rhat^{n+1},K^{n+1})$ até realmente colocarmos o lance.

Seja $\theta^{n+1}(x^n,W^{n+1})$ a estimativa atualizada de $\theta$ assumindo que fazemos um lance $x^n=x$ e observamos $W^{n+1} = (\Rhat^{n+1},K^{n+1})$. Esta é uma variável aleatória, porque estamos pensando em colocar um lance $x^n=x$ para o $n+1$-ésimo leilão, mas ainda não colocamos o lance, o que significa que ainda não observamos $W^{n+1}$.

Para simplificar nossa análise, vamos assumir que a variável aleatória $K^{n+1} = 1$ com probabilidade $P^{click}(\theta,x)$ e $K^{n+1} = 0$ com probabilidade $1-P^{click}(\theta,x)$. Vamos então assumir que nossa estimativa da receita que recebemos de um clique no anúncio se estabilizou, o que significa que $\Rbar^{n+1} \approx \Rbar^n$.

Podemos pensar nisso como um modelo aproximado de horizonte de previsão, onde $\Rbar^n$ não muda. Escreveríamos então nossa informação exógena em nosso modelo de horizonte de previsão como

onde o sobrescrito duplo $(n,n+1)$ significa que esta é a informação em um modelo de horizonte de previsão criado no tempo $n$, olhando para o que pode acontecer no tempo $n+1$. A variável aleatória $\Ktilde^{n,n+1}$ é o clique no anúncio que estamos simulando que pode acontecer em nosso modelo de horizonte de previsão, em vez da observação real de se alguém clicou no anúncio. Apenas lembre-se de que usamos til para qualquer variável em nosso modelo de horizonte de previsão, e essas variáveis serão indexadas por $n$ (o tempo em que estamos iniciando o modelo de horizonte de previsão), e $n+1$ (já que estamos olhando um período de tempo à frente no modelo de horizonte de previsão).

Em seguida, usamos nossa equação de atualização $\eqref{eq:adclicktransition2}$ para as probabilidades $p^n_k = Prob[\theta=\theta_k\vert H^n]$. Podemos escrever essas probabilidades atualizadas como $\ptilde^{n,n+1}_k(\Ktilde^{n,n+1})$ para capturar a dependência da atualização em $\Ktilde^{n,n+1}$ (a equação $\eqref{eq:adclicktransition2}$ é escrita para $\Ktilde^{n,n+1}=1$). Como $\Ktilde^{n,n+1}$ pode assumir dois resultados (0 ou 1) teremos dois valores possíveis para $\ptilde^{n,n+1}_k(\Ktilde^{n,n+1})$.

Agora imagine que realizamos nossa política de exploração pura $X^{explt}(S^n\vert \theta^n)$ que descrevemos acima, mas vamos fazê-la em nosso modelo aproximado de horizonte de previsão (é aqui que ignoramos mudanças em $\Rbar^n$). Seja $\Stilde^{n,n+1}$ representando nosso estado no modelo de horizonte de previsão dado por

Lembre-se – já que $\Ktilde^{n,n+1}$ é uma variável aleatória (ainda estamos no tempo $n$), $\Stilde^{n,n+1}(\Ktilde^{n,n+1})$ também é uma variável aleatória, motivo pelo qual escrevemos sua dependência explícita do resultado $\Ktilde^{n,n+1}$.

A forma de pensar sobre este modelo de horizonte de previsão é como se você estivesse jogando um jogo (como xadrez) em que você pensa em um movimento (para nós, isso seria o lance $x^n$) e então, antes de fazer o movimento, pensa sobre o que pode acontecer no futuro. Neste problema, nosso futuro tem apenas dois resultados (se um cliente clica ou não no anúncio), o que significa dois valores possíveis de $\Stilde^{n,n+1}$, que produzem dois conjuntos de probabilidades atualizadas $\ptilde^{n,n+1}(K^{n+1})$.

Finalmente, isso significa que haverá dois valores do lance míope ótimo (usando nossa política de exploração pura) $X^{explt}(\Stilde^{n,n+1})$. A contribuição esperada que faríamos no futuro é então dada por $\Ctilde(\Stilde^{n,n+1},\xtilde^{n,n+1})$ onde $\xtilde^{n,n+1}$ (esta é a decisão que estamos pensando em tomar no futuro) é dada por

Isso significa que há duas decisões ótimas possíveis, o que significa dois valores diferentes da contribuição esperada $\Ctilde(\Stilde^{n,n+1},X^{explt}(\Stilde^{n,n+1}))$. Para maior compactação, vamos chamar esses valores de $\Ctilde^{n,n+1}(1)$ (se $\Ktilde^{n,n+1} = 1$) e $\Ctilde^{n,n+1}(0)$ (se $\Ktilde^{n,n+1} = 0$). Pense nesses valores como as contribuições esperadas que podem acontecer no futuro dado o que sabemos agora. Finalmente podemos calcular a esperança sobre $\Ktilde^{n,n+1}$ para obter a contribuição esperada de colocar um lance $x^n=x$ agora, que podemos calcular usando

Nossa política, então, é escolher o lance $x$ que maximiza $\Cbar^n(x)$. Assuma que discretizamos nossos lances em um conjunto $\Xcal = \lbrace x_1, \ldots, x_M\rbrace $. Nossa política de valor da informação seria escrita como

Notamos que esta é uma classe de política de aproximação de horizonte de previsão direto (DLA).

Políticas de valor da informação são bastante poderosas. Elas são mais difíceis de calcular, mas não têm nenhum parâmetro ajustável. Imagine, por exemplo, fazer esse cálculo quando há mais de dois resultados. Por exemplo, se não tivéssemos feito nossa simplificação de manter $\Rbar^n$ constante, teríamos que reconhecer que essa variável de estado também está mudando.

Notamos apenas de passagem que realizamos muitas comparações de diferentes políticas de aprendizado, e o valor da informação de horizonte de um passo frequentemente funciona bastante bem. Usamos esse cenário porque tornou as derivações muito mais simples.

Uma palavra de cautela é necessária. Problemas de aprendizado onde o resultado é 0 ou 1 são problemas em que um único experimento fornece muito pouca informação. Em vez disso, é melhor assumir que tomamos nossa decisão (isto é, definimos o lance) e depois a observamos para, digamos, $M$ leilões. Isso significa que $\Ktilde^{n,n+1}$ agora pode ser um número entre 0 e $M$. O número $M$ torna-se um parâmetro ajustável, e os cálculos ficaram um pouco mais complexos (temos que somar sobre $M+1$ realizações em vez de apenas duas), mas essa abordagem pode funcionar bastante bem.

Extensão: Clientes com atributos simples

Suponha que sabemos a localização de um cliente até a região ou a cidade principal mais próxima, que designamos por $L$. Se acharmos que o comportamento de cada região é diferente, poderíamos indexar $\theta$ por $\theta_\ell$ se o cliente for da localização $L=\ell$. Isso significa que, se houver 1.000 localizações, teremos que estimar 1.000 modelos, o que significa 1.000 valores de $\theta = (\theta^{const},\theta^{bid})$.

Uma abordagem alternativa seria especificar um modelo da forma

onde vamos agora usar como nossa função de utilidade

Este é um modelo mais compacto porque agora assumimos que o termo constante $\theta^{const}$ e o coeficiente de lance $\theta^{bid}$ não dependem da localização. Em vez disso, estamos apenas adicionando um deslocamento $\theta^{loc}_\ell$. Assim, ainda temos 1.000 parâmetros a estimar (os coeficientes de localização), mas antes tínhamos 2.000 parâmetros a estimar – $\theta^{const}_\ell$ e $\theta^{bid}_\ell$ para cada localização $\ell \in \lbrace 1, \ldots, L\rbrace $.

O que aprendemos?

• Este é outro problema de aprendizado puro (nosso problema de diabetes no Capítulo 4 foi um problema de aprendizado puro), mas desta vez estamos usando um modelo de crença não linear, com um modelo amostrado para o parâmetro desconhecido $\theta$ que determina a resposta ao preço.
• A função de transição inclui a atualização bayesiana das crenças sobre as probabilidades $p^n_k$ de que o parâmetro desconhecido $\theta$ seja igual a um valor específico $\theta_k$.
• Há três formas de incerteza: se alguém vai clicar em um anúncio dado o preço do lance; a receita obtida ao clicar no anúncio (por exemplo, se o cliente comprou o produto), e a incerteza sobre a resposta do mercado capturada pelo parâmetro desconhecido $\theta$.
• Ilustramos uma política de exploração pura, uma política de excitação (que simplesmente aleatoriza o preço recomendado pela política de exploração), e uma política de gradiente do conhecimento que maximiza o valor da informação.

Exercícios

Questões de revisão

1. Qual modelo probabilístico é assumido para a variável aleatória $K^n$ que indica se um cliente clicou no anúncio ou não?
2. Qual modelo probabilístico assumimos para o vetor de parâmetros desconhecido (e, portanto, incerto) $\theta$?
3. Qual distribuição de probabilidade assumimos para a receita $\Rhat^{n+1}$ que recebemos quando o cliente clica em um anúncio?
4. Forneça os números das equações que compõem a função de transição.
5. Qual informação probabilística está no estado inicial $S^0$?
6. O que se consegue ao adicionar o termo de ruído $\varepsilon(\rho)$ para criar a política de excitação? Quais parâmetros específicos isso nos ajuda a identificar?
7. Descreva em palavras a lógica por trás da política de valor da informação. Qual é o valor de aprender se um cliente clica ou não no anúncio caso isso não mude o que vamos ofertar?

Questões de resolução de problemas

1. Sistema de recomendação parte I - Modelo de crença - Você vai ajudar a projetar um sistema de recomendação que recomenda produtos para anunciar quando um cliente está rolando a tela em um site. Como o cliente precisa fazer login, podemos identificar o $n$-ésimo cliente por um vetor de atributos $a=a^n$ que inclui:

   $a_1$	Gênero (2 tipos).
   $a_2$	Faixa etária $(0$–$10, 11$–$20, \ldots, 70$–$100)$ (8 tipos).
   $a_3$	Tipo de dispositivo (smartphone, laptop, tablet) (3 tipos).
   $a_4$	Região (200).
   $a_5$	ID único (endereço de e-mail) (100 milhões).

   Imagine que estamos recomendando artigos de texto. Suponha que o artigo que recomendamos para o $n$-ésimo cliente tenha atributos $b=b^n$ que incluem:

   $b_1$	Notícias, esportes, artes, negócios, culinária, imóveis (6 tipos).
   $b_2$	Subcategoria: se notícias, então internacional, nacional (por país), regional (região dentro de um país); se esportes, então por esporte, e depois por time (ou atleta); e assim por diante (um total de 500).
   $b_3$	Fonte (site, jornal, ...) (5 fontes).
   $b_4$	Autor (2.000).
   $b_5$	ID único do artigo (6 milhões).

   Gostaríamos de estimar:

   $P(b^n\vert a^n)$ = Probabilidade de que o $n$-ésimo cliente com atributo $a^n$ clique no link de um artigo com atributo $b^n$.

   Quando o cliente $a^n$ chega, vamos assumir que temos que escolher um artigo de notícia de um conjunto $\Bcal^n$, que é o conjunto de artigos disponíveis quando o $n$-ésimo cliente chega (esse conjunto muda ao longo do tempo). Gostaríamos de escolher um artigo com atributo $b\in\Bcal^n$ que maximize a probabilidade de que nosso cliente clique nesse artigo de notícia. Nossa política tem que escolher um artigo específico com atributo $b^n$.

   Idealmente, queremos $P(b^n_5\vert a^n_5)$ que é a probabilidade de que o usuário $a^n_5$ selecione o artigo $b^n_5$, mas há usuários e artigos demais para obter estimativas razoáveis dessa probabilidade. Se considerarmos apenas os elementos $a_1, a_2, a_3$ e $a_4$, haveria 9.600 combinações, com uma média de aproximadamente 10.000 pessoas para cada uma dessas quatro primeiras elementos. Abaixo, vamos assumir que usamos apenas $a_1$ e $a_2$, o que significa 16 tipos de pessoas.

   Vamos criar um conjunto de características $\Fcal$ que são construídas a partir dos elementos de $a$ e $b$ que desejamos considerar. Vamos usar apenas os elementos $\lbrace a_1,a_2,b_1,b_2,b_3\rbrace $ a partir dos quais construiremos um conjunto de variáveis de característica $\phi_f(a,b),~f\in\Fcal$. Como esses cinco elementos são todos categóricos, as características mais elementares são variáveis indicadoras. Por exemplo, para o atributo de gênero $a_1$ temos dois gêneros a partir dos quais criamos duas características:

   $$ \phi_{male}(a) = \begin{cases} 1 & \text{if } a_1 = male, \\ 0 & \text{otherwise.} \end{cases} \qquad \phi_{female}(a) = \begin{cases} 1 & \text{if } a_1 = female, \\ 0 & \text{otherwise.} \end{cases} $$

   Se nos restringirmos a essas características elementares, teríamos uma característica para cada valor possível de cada elemento dos atributos $a_1,a_2,b_1,b_2,b_3$.

   Nosso processo começa quando o primeiro cliente faz login com vetor de atributos $a^1$, momento em que temos que decidir os atributos de um artigo $b^1$ para exibir a esse usuário, e então observar $Y^1$, onde $Y^1 = 1$ se o cliente clicar no artigo ou 0 caso contrário. Essa informação é usada para criar um estado atualizado $S^1$, após o qual observamos o cliente $a^2$.

   Se $a^n$ são os atributos do $n$-ésimo cliente, então nossa decisão é escolher $b^n$ usando o que sabemos, o que designamos por $S^n$. Nosso objetivo é modelar esse problema e projetar uma política $B^\pi(S^n)$ que determine $b^n$.

   Nosso primeiro desafio é desenvolver um modelo de crença:

   1. Se usarmos um modelo de crença de tabela de consulta para $P(b\vert a)$ usando os atributos $\lbrace a_1,a_2, b_1,b_2,b_3\rbrace $, quantos parâmetros estamos tentando estimar?
   2. Em vez disso, considere usar uma regressão logística. Primeiro defina uma função de utilidade $$ U(a,b\vert \theta) = \sum_{f\in\Fcal} \theta_f \phi_f(b\vert a), $$ onde $\Fcal$ é o conjunto de características elementares que podemos construir a partir dos elementos $\lbrace a_1,a_2,b_1,b_2,b_3\rbrace $. Agora crie um modelo de regressão logística para a probabilidade de clicar em um artigo usando $$ P(Y=1\vert a,b,\theta) = \frac{e^{U(a,b\vert \theta)}}{1+e^{U(a,b\vert \theta)}}. $$ Qual é a dimensionalidade do vetor $\theta$ supondo que usemos apenas variáveis indicadoras elementares?
   3. Reconhecendo que o número de parâmetros no modelo paramétrico da parte (b) é muito menor do que o número de parâmetros no modelo de tabela de consulta da parte (a), por que alguém usaria um modelo de crença de tabela de consulta em vez de um modelo paramétrico como a regressão logística? Discuta os prós e contras de cada tipo de modelo de crença.
   4. Agora precisamos estimar $\theta$. Suponha que geremos uma amostra de valores possíveis do vetor $\theta$ que representamos como $\lbrace \theta_1, \ldots, \theta_k, \ldots, \theta_K\rbrace $, onde cada $\theta_k$ é um vetor com elemento $\theta_{kf},~f\in\Fcal$. Comece com a probabilidade a priori $p^0_k = 1/K$. Em seguida, suponha que observamos os atributos do primeiro cliente $a^1$, e então tomamos a decisão de exibir um artigo com atributo $b^1$ (esta é nossa variável de decisão). Assumindo que você conhece $p^n_k$, escreva o teorema de Bayes para calcular $p^{n+1}_k$ após observar um cliente com atributo $a^{n+1}$, e então escolher um artigo com atributo $b^{n+1}$ após o qual você observa o resultado $Y^{n+1} = 1$.
2. Sistema de recomendação parte II - Modelo do sistema - Agora vamos modelar todos os cinco elementos do problema.
   1. Dê os elementos do estado pré-decisão $S^n$ e do estado pós-decisão $S^{b,n}$.
   2. Existem duas formas de informação exógena nesse processo. Quais são elas?
   3. Escreva a sequência de estados (pré e pós), decisões e as diferentes formas de informação exógena começando com o que você sabe no tempo 0 e prosseguindo até (mas excluindo) a chegada do terceiro cliente. Escreva-os na ordem em que ocorrem, com a indexação adequada (por exemplo, $n$ versus $n+1$).
   4. Escreva as equações que representam a função de transição.
   5. Escreva a função objetivo para encontrar a melhor política $B^\pi(S^n)$ (sem especificar o tipo de política).
3. Sistema de recomendação parte III - Projeto de política - Finalmente, vamos tentar projetar políticas. Suponha que temos $K=20$ valores possíveis de $\theta$.
   1. Comece supondo que sabemos que $\theta = \theta_k$. Escreva uma política de pura explotação em que escolhemos o atributo $b\in\Bcal^n$ que maximiza a probabilidade de ser escolhido, dado que $\theta = \theta_k$.
   2. Em seguida, suponha que não sabemos que $\theta=\theta_k$. Em vez disso, $\theta=\theta_k$ com probabilidade $p^n_k$. Reescreva sua política da parte (a) onde você precisa tratar $\theta$ como uma variável aleatória. Você precisará inserir uma esperança em algum lugar.
   3. A política em (b) pode ser vista como muito cara de calcular. Você pode simplificá-la substituindo a variável aleatória $\theta$ por sua esperança $$ \thetabar^n = \E^n \theta_k = \sum_{k=1}^K \theta_k p^n_k. $$ Reescreva sua política da parte (b) usando essa estimativa pontual. Suponha que você esteja considerando apenas artigos em que a probabilidade de clicar em um artigo seja maior que 0,5. Como você acha que a probabilidade de clicar em um artigo calculada usando a estimativa pontual em (c) se compararia à estimativa fornecida usando a esperança em (b)?
   4. A política de estimativa por intervalo usa, digamos, o percentil 95 da estimativa do valor de uma escolha. Seja $\rho$ o percentil desejado, e suponha que ele tenha que ser arredondado para 0,05 (porque escolhemos $K=20$ valores possíveis para $\theta$). Mostre como projetar uma política que escolhe o vetor de atributos $b$ que maximiza a $\rho$-ésima probabilidade (em vez da estimativa pontual), e dê a função objetivo para encontrar o melhor valor de $\rho$ para maximizar o número total de cliques em anúncios.