Neste post, apresentaremos o problema de exploração-exploração e mostraremos como a incerteza pode ajudar a resolvê-lo. Vamos nos concentrar na exploração em sistemas de recomendação, mas a mesma idéia pode ser aplicada em muitas aplicações de aprendizado por reforço - carros autônomos, robôs, etc.
Configuração do problema
O objetivo de um sistema de recomendação é recomendar itens que os usuários possam achar relevantes. No Avance Network, a relevância é expressa por meio de um clique: mostramos um widget que contém recomendações de conteúdo e os usuários escolhem se desejam clicar em um dos itens.
A probabilidade de o usuário clicar em um item é chamada de Taxa de cliques (CTR). Se soubéssemos a CTR de todos os itens, o problema de quais itens recomendar seria fácil: basta recomendar os itens com a CTR mais alta.
O problema é que não sabemos o que é a CTR. Temos um modelo que o estima, mas obviamente não é perfeito. Algumas das razões para a imperfeição são os tipos de incerteza inerentes aos sistemas de recomendação, que discutimos.
A troca entre exploração e exploração
Portanto, agora estamos enfrentando uma situação desafiadora - uma que todos conhecemos no dia-a-dia: imagine que você acabou de entrar em uma sorveteria. Agora você enfrenta uma decisão crucial - dentre cerca de 30 sabores, você precisa escolher apenas um!
Você pode seguir duas estratégias: ou use seu sabor favorito que você já sabe que é o melhor; ou explore novos sabores que você nunca experimentou antes e talvez encontre um novo melhor sabor.
Essas duas estratégias - exploração e exploração - também podem ser usadas ao recomendar conteúdo. Podemos explorar itens com alta CTR com alta segurança - talvez porque esses itens tenham sido mostrados milhares de vezes para usuários semelhantes; ou podemos explorar novos itens que não mostramos para muitos usuários no passado. A incorporação da exploração em sua estratégia de recomendação é crucial - sem ela, os novos itens não têm chance contra os mais antigos e familiares.
Vamos explorar abordagens de exploração
A abordagem mais fácil de exploração e exploração que você pode implementar é o algoritmo gre ganancioso, em que você aloca ϵ porcentagens do tráfego para explorar novos itens de maneira aleatória. O restante do tráfego é reservado para exploração.
Apesar de não ser ideal, esse método é fácil de entender. Pode servir como uma linha de base sólida para abordagens mais sofisticadas. Então, como podemos procurar bons itens de maneira mais sábia?
Uma abordagem mais avançada - limite superior de confiança (UCB) - usa incerteza. Cada item está associado à sua CTR esperada e a confiança é vinculada a essa CTR. O limite de confiança captura quão incertos somos sobre a CTR do item. O algoritmo UCB baunilha mantém o controle da CTR esperada e a confiança vinculada usando apenas informações empíricas: para cada item, controlamos a CTR empírica (que porcentagem de usuários semelhantes clicaram nele) e a confiança vinculada é calculada assumindo uma distribuição binomial.
Tome, por exemplo, o sabor simples de chocolate que você sempre pede. Você sabe que é bom - você concede 8 estrelas de 10. Hoje chegou um novo sabor. Você não possui informações empíricas, o que significa que pode ser de 1 a 10 estrelas. Usando esse intervalo de confiança, se você quiser explorar, usará o novo sabor, já que há a chance de ser um sabor de 10 estrelas.
Essa estratégia é exatamente o objetivo do UCB - você escolhe o item com o maior valor do limite superior de confiança - no nosso caso, a confiança vinculada à estimativa da CTR. A motivação por trás dessa estratégia é que, com o tempo, a CTR empírica tenderá para a verdadeira CTR e o limite de confiança diminuirá para 0. Após um tempo, exploraremos tudo.
Outra abordagem popular é o método Thompson Sampling . Nesta abordagem, usamos toda a distribuição estimada na CTR do item, em vez de apenas um limite de confiança. Para cada item, coletamos uma CTR de sua distribuição.
Essas abordagens podem funcionar bem quando o número de itens disponíveis é fixo. Infelizmente todos os dias milhares de novos itens entram no sistema, e outros se tornam obsoletos. Quando obtivermos uma confiança razoável razoável para um item, ele poderá deixar o sistema. Nossos esforços teriam sido em vão. É como fazer uma turnê mundial, todos os dias visitando uma nova cidade com uma vasta quantidade de sabores de sorvete para explorar. O horror!
Precisamos de uma abordagem que possa estimar a CTR de um novo item sem mostrá-lo nem uma vez. Precisamos de uma revista de crítica gastronômica que nos guie pelo buffet de recomendações de conteúdo.
Considere um novo tipo de sabor de chocolate que acabou de chegar. Como você sabe que adora chocolate, você tem um palpite muito bom de que também gostará do novo sabor. Na abordagem UCB de baunilha (não, isso não é um nome de sabor), você não será capaz de inferir isso - você depende apenas de informações empíricas.
Em um post futuro, elaboraremos como usamos uma rede neural para estimar a CTR de um novo item, bem como o nível de incerteza. Usando essa incerteza, podemos aplicar a abordagem UCB para explorar novos itens. Diferentemente do UCB de baunilha que se baseia em dados empíricos, aqui podemos usar a estimativa do modelo para evitar mostrar itens com baixa CTR. Podemos apostar nos cavalos que acreditamos que vencerão.
Métricas e resultados online
Como podemos saber o quão bem exploramos novos itens? Precisamos de alguma métrica de taxa de transferência de exploração. Em Avance Network, temos a infraestrutura de teste A / B suportando muitos modelos em execução em diferentes partes do tráfego.
De volta ao sorvete! Digamos que você trouxe seus amigos para ajudá-lo a explorar os diferentes sabores. Obviamente, se um de seus amigos escolher sabores aleatoriamente, ele terá o melhor rendimento da exploração, mas não o mais inteligente. O outro amigo que pede o sabor que os outros acharam gostoso gosta mais, mas não contribui em nada para o esforço de exploração.
No Avance Network, medimos o rendimento da exploração da seguinte maneira: para cada item que foi mostrado tempo suficiente e em contextos diferentes o suficiente (por exemplo, sites diferentes), declaramos que esse item passou pela fase de exploração. A seguir, analisamos quais modelos contribuíram para esse esforço bem-sucedido. Para contar, um modelo precisa mostrar esse item vezes o suficiente.
Usando essa perspectiva, a taxa de transferência de um modelo é definida como o número de itens aos quais contribuiu.
Usando essa métrica, fomos capazes de afirmar que, de fato, a exibição aleatória de itens produz a melhor taxa de transferência, mas com tendência a itens ruins. Um modelo que não usa a abordagem UCB mostra bons itens, mas tem uma taxa de transferência pior. O modelo com o UCB está em algum ponto entre a taxa de transferência e mostra itens apenas um pouco piores em comparação com o modelo que não é do UCB.
Portanto, concluímos que nosso modelo UCB tem uma boa relação entre explorar novos itens e escolher os bons. Acreditamos que essa troca vale a pena a longo prazo.
Pensamentos finais
O problema de exploração-exploração é um desafio empolgante para muitas empresas no domínio de sistemas de recomendação. Esperamos que nossos avanços ajudem outras pessoas em sua jornada de oferecer o melhor serviço aos seus usuários. Acreditamos que este é um pequeno passo em uma grande jornada ainda a ser cumprida, e estamos intrigados com o pensamento de que forma esse campo terá nos próximos anos.
