Geralmente, a necessidade deste B.Sc. o material termina quando um contrato é assinado, já que a maioria dessas questões de baixo nível é tratada para nós, nos bastidores das modernas linguagens de codificação e bibliotecas externas. Ainda assim, há pouco tempo, nos deparamos com uma dessas questões na vida real:  encontre um algoritmo eficiente para amostragem ponderada em tempo real . Por mais ingênuo que possa parecer à primeira vista, gostaríamos de mostrar por que realmente não é - e depois mostrar como resolvemos isso, para o caso de você encontrar algo semelhante. Então aperte o cinto, temos algumas estatísticas e integrais a seguir!

Por que precisamos de amostragem ponderada na produção?

No Avance Network, nosso principal negócio é personalizar a experiência de usabilidade on-line de nossa comunidade. Milhares de sites em todo o mundo confiam em nós para exibir a cada usuário visitante os anúncios com os quais ele provavelmente se relacionará e com maior probabilidade de clicar e interagir. Fazemos isso treinando vários modelos baseados em aprendizado profundo que prevêem a CTR (taxa de cliques) de cada anúncio para cada usuário. O processo de prever a CTR e exibir os itens mais bem classificados é conhecido como  Exploração , à medida que exploramos as previsões do modelo. Mas a exploração não é suficiente para um modelo de sucesso a longo prazo - nós precisamos permitir que ele faça algum E XPLORAÇÃO de novas possibilidades também, a fim de encontrar melhores anúncios.

Uma de nossas idéias para essa exploração foi a seguinte: peça ao modelo para prever a CTR de uma lista de anúncios que gostaríamos de exibir e, em vez de exibir os itens com a classificação mais alta, faça uma amostra aleatória dos itens dessa lista usando uma amostra ponderada. Isso às vezes é conhecido como  Soft-Exploration : os itens com classificação mais alta ainda são os mais prováveis, mas cada item tem uma probabilidade diferente de zero de ser mostrado.

Então, precisamos fazer amostragem ponderada. A abordagem mais ingênua para fazer isso será algo como isto:

Esse algoritmo ingênuo tem uma complexidade de . Considerando o fato de que as listas são longas e tudo isso está acontecendo em tempo real, esse algoritmo é inútil. Mas tem que haver uma maneira melhor de fazer isso, certo? Bem, sim, mas tivemos que projetá-lo nós mesmos.

A Solução Teórica

Olhando bastante o suficiente para um algoritmo, produziu um artigo chamado  Amostragem Aleatória Ponderada por Efraimidis Spirakis. Uma única linha neste artigo forneceu um algoritmo simples para o que deveríamos fazer (página 2, algoritmo A-Res, linha 2):

1) mapeie cada número da lista:  
.. (r é um número aleatório, escolhido de maneira uniforme e independente para cada número)
2) reordene os números de acordo com os valores mapeados
. (O primeiro número será o que tiver o maior mapeado -value e assim por diante)

Esse algoritmo envolve mapear e classificar, tornando-o muito melhor  , mas ainda existe um problema - os autores nunca o provaram. E como não tínhamos prova de que isso realmente está funcionando, tivemos que provar isso sozinhos. Preparem-se, integrais estão chegando.

Antes de começarmos, como as seguintes linhas podem ser facilmente confusas, deixe-me descrever brevemente o que estou prestes a fazer:

1. Primeiro, descreverei como uma distribuição de probabilidade de amostragem ponderada deve se comportar. Como é isso que estamos procurando, formalizá-lo matematicamente é provavelmente uma boa ideia.
2. Depois de formalizarmos a distribuição que queremos, encontraremos uma distribuição específica que podemos usar para amostragem ponderada.
3. Por fim, depois de encontrar uma distribuição específica, vou vinculá-la à Distribuição Uniforme (assim como o algoritmo acima). Ficamos surpresos com o fato de o mapeamento sugerido   realmente imitar a amostragem aleatória.

Pronto? Vamos lá.

Parte I: Formalização

Como se comporta a amostragem ponderada? Digamos que temos dois números  e , sobre os quais realizamos amostragem ponderada. Esperamos obter a sequência (2,1) dois terços do tempo e a sequência (1,2) um terço do tempo. Portanto, esperamos  ser o primeiro número 66,6% das vezes e o segundo 33,3% das vezes. Outra maneira de analisar isso é que, como estamos classificando os números em uma lista, esperamos que a  prioridade  (o quão perto um número esteja do cabeçalho da lista)   seja os dois terços mais altos das vezes e o menor terço das vezes. Você pode ver facilmente essa  prioridade , que iremos denotar como m , se comporta de maneira semelhante a um índice inverso, significando o m mais alto é o primeiro da lista. Nós o preferimos ao invés do índice por dois motivos: primeiro, a prioridade aumenta à medida que w aumenta e é mais intuitivo que o índice, que diminui à medida que  w aumenta. Segundo, os valores absolutos das prioridades não são relevantes; não importa se ( ) seja igual a (4,5, 3) ou (-1, -5) ou (1024, 5). Tudo o que importa é a ordem entre eles - o mais alto será o primeiro, depois o segundo mais alto e assim por diante. Essas duas características nos permitirão generalizar melhor mais tarde. Então, para finalizar este exemplo, no caso de   e , gostaríamos de encontrar uma distribuição de probabilidade que produzirá e   que obedeça:

Vamos generalizar e formalizar matematicamente: para cada dois números , gostaríamos de ter duas variáveis ​​aleatórias que se originam de uma distribuição de probabilidade (significado :), onde é uma distribuição de probabilidade definida por todos os valores de w fornecidos (neste exemplo simples existem apenas dois e , mas geralmente pode haver mais). Esperamos com probabilidade .

Parte II: Encontrando uma Distribuição Específica

Afirmo que a distribuição de probabilidade definida pela Função de Distribuição Cumulativa (CDF)   obedece ao requisito acima - e vou provar. Por isso, lembre-se que a função de densidade de probabilidade (pdf)   obedece   , e, portanto, no nosso caso:  . Também denotarei a Função Indicadora como  (o que significa que é 1 quando e 0 caso contrário). Por fim, 

trabalharemos apenas no intervalo [0,1]:

Portanto, provamos que a distribuição com CDF    realmente imita a amostragem ponderada.

Parte III: Vinculando à Distribuição Uniforme

Como programadores, a distribuição uniforme é geralmente a mais acessível que temos, independentemente da linguagem ou das bibliotecas. Só fará sentido vincular a distribuição personalizada que acabamos de encontrar à Distribuição Uniforme, que nos permitirá usar essa última para amostragem ponderada.

Digamos que X seja produzido (ou seja ), qual é a probabilidade de X ser menor que algum número ? Isto é dado pelo CDF:

Vamos examinar outra variável, Y , que definiremos como , quando R se originar da distribuição uniforme . Qual é a probabilidade de Y ser menor que ? Vamos calcular, lembrando que o CDF de  for any  é  :

Este é o mesmo resultado que temos para X que foi amostrado a partir de , e isto significa que podemos provar um número de , tomar o seu w th raiz, e seria como se nós usamos o tempo todo. Isso significa que a prioridade  m de um número  w é dada por . Arrumado.

Realmente fazendo funcionar

Gosto de um ditado que afirma que a diferença entre teoria e prática é que a teoria só funciona na teoria. Então, encontramos um algoritmo rápido o suficiente, provamos matematicamente e, é claro, não funciona. Por quê? Porque computadores. Vamos dar uma olhada em nossas  m  valores novamente:  . Como mencionado anteriormente, usamos nossos modelos para prever a CTR e, portanto, w = CTR, que é sempre um número no intervalo de [0,1] e geralmente muito pequeno. Como r também é amostrado da mesma faixa, torna-se muito pequeno, como e . Na verdade, torna-se tão pequeno e com tanta frequência que o computador não lida com a precisão muito bem e obtemos zeros para todos os valores. Vamos ver um exemplo usando Python:

Não é bom.

Então o que nós podemos fazer? Mais uma vez, matemática para o resgate! Como dissemos anteriormente, não nos importamos com os valores absolutos de m , mas apenas com a ordem entre eles. Isso significa que podemos aplicar qualquer função monotônica nos valores mapeados e controlar a rapidez com que os números diminuem. Para nós, um logaritmo simples fez o truque: . Vamos ver isso em ação:

Muito melhor. Ainda assim, isso não vem sem um preço - o logaritmo que aplicamos diminui a precisão do algoritmo. Isso significa que, no nosso exemplo de  e , não teremos    a probabilidade 2/3, mas algo próximo. Para nós, porém, esse desvio é algo com o qual estamos bem.

Portanto, para finalizar, nosso algoritmo de amostragem aleatória para nossos serviços de produção em tempo real é:

1) mapeie cada número da lista: 
.. (r é um número aleatório, escolhido de maneira uniforme e independente para cada número)
2) reordene os números de acordo com os valores mapeados
. (O primeiro número será o que tiver o maior mapeado -value e assim por diante)

Sucesso.

Conclusão

Resumindo esse processo, começamos com um algoritmo ingênuo que não era suficientemente eficiente, passamos exatamente para o oposto - um algoritmo eficiente que não funciona e o modificamos para uma versão quase exata que funciona muito bem e também é eficiente.

Se eu precisar concluir, só posso dizer isso - há algo super empolgante em deixar nossa rotina diária de desenvolver modelos de IA de ponta e retornar às nossas raízes como desenvolvedores de algoritmos; voltando ao básico, desenvolvendo provas matemáticas, dormindo à beira do rio sob o céu estrelado e preparando o jantar junto à lareira - não chegamos a isso todos os dias, e acho que estamos todos felizes por termos feito isso desta vez. Portanto, onde quer que você navegue on-line, saiba que acabamos de melhorar sua experiência usando matemática simples.

Máxima comunicação com proteção ao extremo? Avance Network: A verdadeira rede social junte-se a nós