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:

resultados = lista vazia max_r = 1 para i de 0 à quantidade de pesos fornecidos: .. r = Número aleatório no intervalo (0, max_r] .. s = 0 .. para cada peso na lista de pesos: ... . s + = peso .... se s = r: ...... peso acréscimo para resultados ...... peso de remoção de pesos ...... max_r = max_r - peso .... .. quebrar resultados de retorno

Esse algoritmo ingênuo tem uma complexidade de $O(n^2)$ . 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: $w \ rightarrow r ^ {1 / w}$
.. (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 $O(n \log n)$ muito melhor $O(n^2)$ , 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:

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.
Depois de formalizarmos a distribuição que queremos, encontraremos uma distribuição específica que podemos usar para amostragem ponderada.
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 $w \ rightarrow r ^ {1 / w}$ 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 $w_1 = 1$ e $w_2 = 2$ , 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 $w_2$ 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) $w_2$ 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 ( $m_2, m_1$ ) 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 $w_1 = 1$ e $w_2 = 2$ , gostaríamos de encontrar uma distribuição de probabilidade que produzirá e $m_1, m_2$ que obedeça:

$m_1, m_2: \ begin {cases} m_2 m_1, \ text {com probabilidade} p = \ frac {2} {3} \\ m_2 m_1, \ text {com probabilidade} p = \ frac {1} {3} \ end {cases}$

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

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

Afirmo que a distribuição de probabilidade definida pela Função de Distribuição Cumulativa (CDF) $F_w (x) = x ^ w$ obedece ao requisito acima - e vou provar. Por isso, lembre-se que a função de densidade de probabilidade (pdf) $f_w (m)$ obedece $f_w (m) = \ frac {d} {dm} F_w (m)$ , e, portanto, no nosso caso: $f_w (m) = wm ^ {w-1}$ . Também denotarei a Função Indicadora como $Eu$ (o que significa que $I_ (m_1 m_2)$ é 1 quando $m_1 m_2$ e 0 caso contrário). Por fim,

trabalharemos apenas no intervalo [0,1]:

$\ begin {align *} p (M_1 M_2) = \ int_ {m_2 = 0} ^ 1 \ int_ {m_1 = 0} ^ 1 \ mathbb {I} _ {m_1 m_2} f_ {w_1} (m_1) f_ {w_2} (m_1) dm_1 dm_2 \\ = \ int_ {m_2 = 0} ^ 1 \ int_ {m_1 = 0} ^ {m_2} f_ {w_2} (m_2) f_ {w_1} (m_1) dm_1 dm_2 \ \ = \ int_ {m_2 = 0} ^ 1 f_ {w_2} (m_2) \ biggr [m_1 ^ {w_1} \ biggr] _ {m_1 = 0} ^ {m_2} dm_2 \\ = \ int_ {m_2 = 0} ^ 1 w_2 m_2 ^ {w_2-1} \ cdot m_2 ^ {w_1} dm_2 \\ = \ int_ {m_2 = 0} ^ 1 w_2m_2 ^ {w_1 + w_2 - 1} dm_2 \\ = \ frac { w_2 \ cdot m_2 ^ {w_1 + w_2}} {w_1 + w_2} \ biggr | _ {m_2 = 0} ^ 1 \\ = \ frac {w_2} {w_1 + w_2} \ end {align *}$

Portanto, provamos que a distribuição com CDF $F_w (m) = m ^ w$ 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 $D_w$ (ou seja $X \ sim D_w$ ), qual é a probabilidade de X ser menor que algum número $\alfa$ ? Isto é dado pelo CDF:

$p (X \ alpha) = F_w (\ alpha) = \ alpha ^ w$

Vamos examinar outra variável, Y , que definiremos como $Y = \ sqrt [w] {R}$ , quando R se originar da distribuição uniforme $r \sim U(0,1)$ . Qual é a probabilidade de Y ser menor que $\alfa$ ? Vamos calcular, lembrando que o CDF de $U (0,1)$ for any $0 \ leq u \ leq 1$ é $F_U (u) = u$ :

$p (Y \ alpha) = p (\ sqrt [w] {R} \ alpha) = p (R \ alpha ^ w) = F_U (\ alpha ^ w) = \ alpha ^ w$

Este é o mesmo resultado que temos para X que foi amostrado a partir de $D_w$ , e isto significa que podemos provar um número de $U (0,1)$ , tomar o seu w th raiz, e seria como se nós usamos $D_w$ o tempo todo. Isso significa que a prioridade m de um número w é dada por $m = r ^ (1 / w)$ . 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: $m = r ^ (1 / w)$ . 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, $r ^ {1 / w}$ torna-se muito pequeno, como $r 1$ e $1 / w 1$ . 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:

de importação aleatória aleatória m = lambda w: random () ** (1.0 / w) m (0.002), m (0.001) (0.0, 0.0)

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: $\ log (r ^ {1 / w}) = \ frac {\ log (r)} {w}$ . Vamos ver isso em ação:

da importação aleatória aleatória do log de importação matemática m = lambda w: log (aleatório ()) / w m (0,002), m (0,001) (-402.5850708710584, -758.9101125141252)

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 $w_1 = 1$ e $w_2 = 2$ , não teremos $m_1 m_2$ 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: $w \ rightarrow \ log (r) / w$
.. (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.

Projetando Algoritmos para Amostragem

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

A Solução Teórica

Parte I: Formalização

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

Parte III: Vinculando à Distribuição Uniforme

Realmente fazendo funcionar

Conclusão

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

Strong

Projetando Algoritmos para Amostragem

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

A Solução Teórica

Parte I: Formalização

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

Parte III: Vinculando à Distribuição Uniforme

Realmente fazendo funcionar

Conclusão

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

Strong

Tudo sobre os Ruindows Phone (Error 500)

Muitas ferramentas de comunicação? Você não está sozinho

Alimentos Diuréticos: O que são, benefícios e como consumir