Amostragem por reservatório: como fazer uma seleção aleatória justa em dados de tamanho desconhecido
(samwho.dev)- Amostragem por reservatório é uma técnica de extração que mantém apenas uma quantidade fixa de itens na memória mesmo em fluxos de dados cujo tamanho total é desconhecido, dando a todos os itens a mesma chance de serem escolhidos
- Para arrays cujo tamanho é conhecido, embaralhar ou fazer seleção de índices aleatórios já é suficiente, mas em streams nos quais não é possível voltar a itens já passados, é necessária outra abordagem
- Na seleção de um único item, o n-ésimo item é aceito com probabilidade 1/n, equilibrando a possibilidade de escolha do novo item e a chance de sobrevivência dos itens já vistos
- Ao escolher vários itens, o novo item é aceito com probabilidade k/n de acordo com a quantidade k mantida, e, se necessário, substitui aleatoriamente um dos itens atualmente armazenados
- Aplicada à coleta de logs, ela permite não ultrapassar um limite de processamento como no máximo 5 por segundo, ao mesmo tempo em que reduz a perda de logs em períodos tranquilos e o uso de memória
Amostragem em conjuntos de tamanho conhecido
- Se você for escolher 3 cartas aleatoriamente de um baralho de 10, basta embaralhar tudo e pegar as 3 primeiras para dar a cada carta a mesma probabilidade de seleção
- Se o número de cartas aumentar para 1 milhão, embaralhar diretamente fica difícil, mas em estruturas acessíveis por índice, como arrays, escolher 3 índices aleatórios cumpre o mesmo objetivo
- Um array em memória permite acessar um índice específico com facilidade, mas contar a 436.234ª carta em uma pilha física é, na prática, demorado
Restrições que surgem em um stream de tamanho desconhecido
- Se você só puder ver 1 carta por vez, só puder segurar 1 carta ao mesmo tempo e não puder voltar às cartas já passadas, terá de escolher 1 carta final sem saber o total
- Um serviço de coleta de logs enfrenta um problema parecido
- recebe mensagens de log de outros serviços e as armazena em um só lugar
- quando uma release ruim ou um pico de tráfego despeja muitos logs, o serviço coletor pode ficar sobrecarregado
- No exemplo, o serviço de coleta de logs tem um limite de 5 logs por segundo que consegue processar
- Enviar apenas 10% dos logs evita ultrapassar o limite durante picos, mas descarta desnecessariamente 90% dos logs mesmo em períodos tranquilos
- O comportamento desejado é enviar todos os logs em períodos tranquilos e, em picos, enviar no máximo 5 por segundo
- Se você enviar apenas os primeiros 5 logs vistos a cada segundo, os logs que chegarem depois perdem a chance de serem selecionados, então isso não é justo
Amostragem por reservatório de um único item
- A amostragem por reservatório mantém uma amostra justa entre os itens vistos até agora, mesmo sem conhecer a quantidade total
- Também seria possível guardar todas as mensagens na memória e escolher depois, mas sem saber o tamanho do pico é difícil prever quanta memória será necessária
- Essa abordagem resolve o mesmo problema sem usar mais memória do que a quantidade de amostras pedida
- A regra para escolher uma única carta é simples
- a primeira carta é sempre guardada
- a n-ésima nova carta é guardada com probabilidade 1/n
- se a nova carta for guardada, a carta atualmente mantida é descartada
- Substituir a cada carta com 50% de probabilidade não é justo, porque favorece as cartas do fim
- para a primeira carta continuar até a 10ª, ela teria de sobreviver a várias oportunidades de substituição
- a última carta pode permanecer na mão se for escolhida uma única vez
- A regra de 1/n ajusta não só a probabilidade de seleção do novo item, mas também a probabilidade de sobrevivência dos itens já existentes
- a primeira carta é guardada com probabilidade 1/1, isto é, 100%
- na segunda carta, a nova é escolhida com probabilidade 1/2, e a primeira também permanece com probabilidade 1/2
- na terceira carta, a nova é escolhida com probabilidade 1/3, e a carta já mantida também fica com probabilidade 50% × 2/3, ou seja, 1/3
- Em geral, na etapa n, a probabilidade de uma carta existente permanecer é
1/(n-1) * (1-(1/n)), e a probabilidade de a nova carta ser escolhida é1/n, ficando iguais
Expansão para escolher vários itens
- A seleção de um único item pode ser estendida para a seleção de vários itens
- Para escolher k itens, duas regras mudam
- o novo item é selecionado com probabilidade k/n, em vez de
1/n - se for preciso substituir, um dos k itens atualmente mantidos é escolhido aleatoriamente e trocado pelo novo item
- o novo item é selecionado com probabilidade k/n, em vez de
- A probabilidade de seleção de um item existente é expressa como
k/(n-1), e a justiça é mantida ao multiplicar isso pela probabilidade de ele não ser substituído pelo novo item - Como todos os itens armazenados têm a mesma chance de serem escolhidos para substituição, a possibilidade de cada um continuar no reservatório também permanece igual em cada etapa
- A implementação pode ser resumida como o uso de um array de tamanho k
- para cada novo item, gera-se um número aleatório entre 0 e n
- se o número aleatório for menor que k, o item naquele índice é substituído pelo novo item
- caso contrário, o novo item é descartado
Aplicando a um serviço de coleta de logs
- No exemplo de coleta de logs, define-se
k=5para manter no máximo 5 mensagens de log por vez - A cada segundo, os logs selecionados são enviados ao serviço de coleta e, em seguida, o array de tamanho 5 é esvaziado para recomeçar
- Esse método cria um padrão em blocos de envio de logs em intervalos fixos, em vez de um fluxo contínuo em tempo real
- Em compensação, a quantidade de logs enviados não ultrapassa o limite e, em períodos tranquilos, o total de logs e o total enviado acompanham-se quase juntos
- Em períodos tranquilos, nenhum log é perdido; em picos, não são enviados mais logs por segundo do que o limite; e o espaço de armazenamento também não passa de
k=5logs
Quando há necessidade de pesos
- Alguns logs podem ser mais valiosos do que outros
- Por exemplo, você pode querer guardar todos os logs de erro
- Nesses casos, pode-se usar uma variação de amostragem por reservatório com pesos
- A amostragem por reservatório é um algoritmo que permite resolver, com pouca memória, um problema de amostragem em stream que à primeira vista parece impossível
1 comentários
Comentários do Hacker News
Quando eu era criança, morava no interior, e ouvi dizer que um amigo do meu pai, por causa do trabalho, precisava contar todos os anos a população de lagópodes-brancos nas montanhas.
Ele caminhava por uma rota definida, assustava as aves em intervalos regulares para fazê-las levantar voo, contava quantas eram e enviava o total ao órgão público, que usava aquilo para estimar a população total.
Em um certo ano, ele precisou viajar para o exterior bem na época da pesquisa, então explicou o método em detalhes a um amigo e pediu que fizesse no lugar dele. Só que o amigo esqueceu no dia e, como também dava trabalho, enviou um número mais ou menos plausível.
No ano seguinte, a manchete da primeira página do jornal local foi população de lagópodes-brancos tem aumento recorde; o amigo não tinha pensado que aquela estimativa seria usada para definir a quantidade de licenças de caça.
https://en.wikipedia.org/wiki/Rock_ptarmigan
Anos atrás, eu criei sistemas de reserva para resorts de esqui bem grandes e, quando o cronograma atrasou e eu estava virando a noite trabalhando, uma das últimas coisas que faltavam terminar era um relatório de estatísticas oficiais, como o número de hóspedes, publicado pelo governo.
Digamos apenas que as estatísticas daquele ano tinham muito pouca relação com a realidade.
Sou o autor do artigo. Posso responder a perguntas, e feedback é bem-vindo.
O código de todos os posts está em https://github.com/samwho/visualisations e está sob licença MIT, então podem usar livremente.
Uma extensão mais interessante da amostragem por reservatório é, em vez de sortear um número aleatório para cada item para decidir se substitui e qual item substituir, sortear um valor de uma distribuição geométrica para determinar quantos itens podem ser pulados com segurança antes da próxima substituição.
Isso é especialmente útil quando é barato pular muitos itens, como quando dá para avançar rapidamente uma unidade de fita sem saber o comprimento total, ou quando a maior parte do sistema pode ficar em modo de economia de energia enquanto os itens são pulados.
Ao escolher k itens entre n, esse método faz aproximadamente O(k * log (n/k)) operações de amostragem e salto.
Conceitualmente, prefiro uma versão da amostragem por reservatório em que cada carta recebe uma prioridade aleatória fixa ao chegar, e mantemos apenas as k cartas de maior prioridade.
O problema que segue daí é escolher os k maiores em um fluxo de comprimento desconhecido em tempo O(n) e espaço O(k). A solução simples de manter um heap mínimo usa O(k) de espaço, mas leva O(n log k) de tempo.
Em vez disso, dá para manter um buffer não ordenado com capacidade de até 2k, adicionar itens e, quando ele encher, usar quickselect aleatório ou median-of-medians para ficar apenas com os k maiores em O(k). Como, para todos os n itens, fazemos O(2k) de trabalho a cada k itens, o tempo de execução fica O(n).
Um tema relacionado é rendezvous hashing: https://en.wikipedia.org/wiki/Rendezvous_hashing
Como observação lateral, há também um bom artigo sobre o método alias para amostrar de distribuições de probabilidade discretas: https://www.keithschwarz.com/darts-dice-coins/
Mas, no começo, a história era sobre escolher aleatoriamente 3 cartas de um baralho de 10 ou 436.234 cartas, e de repente passou a ser sobre escolher só 1 carta, então fiquei confuso por um momento.
Acho que ficaria mais claro se houvesse um título de seção antes de “Now let me throw you a curveball...”, algo como “A partir de agora, vamos passar para uma hipótese simplificada: manter apenas 1 carta, não 3, e também não saber o tamanho do baralho”.
Mas não sei se entendi bem a validade estatística dessa abordagem. Entendo que todos os logs de um determinado período têm a mesma probabilidade de serem incluídos, mas então os logs gerados em “horários lentos” não ficam super-representados nas métricas gerais?
Por exemplo, se eu quiser saber quais endpoints consomem mais tempo para reduzir o custo total da frota inteira (CPU-segundos etc.), um endpoint que recebe tráfego em rajadas pode ficar sub-representado em relação a um endpoint com tráfego constante, então esse método me parece inadequado.
Nesse caso, posso acabar desperdiçando tempo otimizando endpoints que na prática não recebem tanto tráfego.
Também fico curioso se, no planejamento de capacidade por serviço, faz sentido que serviços com tráfego em rajadas fiquem sub-representados.
Gostaria de saber para quais casos de uso a amostragem por reservatório é adequada e que análises estatísticas podem ser feitas com os dados retornados.
O texto e as explicações são excelentes
Do ponto de vista prático, ainda assim acho que eu usaria essa abordagem por último para coleta de logs. Entendo que, se houver um pico, alguma coisa precisa ser descartada, mas o ponto central é o que deve ser descartado
Não parece haver grande valor em decidir “de forma justa” o que descartar
É melhor descartar primeiro os logs de baixa prioridade e, se houver níveis de log como debug/info/warning/error, priorizar eventos de maior gravidade e descartar primeiro logs de debug verbosos
Também é possível agrupar sequências de logs como parte de uma única atividade: para atividades concluídas com sucesso, registrar apenas o início e o fim, ou mudanças de estado essenciais, e omitir logs intermediários repetitivos
Em vez de armazenar todas as linhas de log durante um pico, agregar e resumir mensagens parecidas ou duplicadas reduz o volume e também deixa as tendências mais visíveis
E também se quer limitar o número total de linhas de log coletadas a um orçamento maior. A amostragem por reservatório consegue lidar com tudo isso
A amostragem por reservatório justa também pode ser tornada injusta de forma controlada. Por exemplo, itens com conteúdo especialmente interessante podem ter uma probabilidade maior de serem mantidos
Como último recurso, é uma técnica que compete com seleção aleatória enviesada menos principiada ou até com algoritmos de seleção que nem sequer são aleatórios
É um texto muito bem escrito e bem visualizado
Como extensão avançada, há algoritmos que calculam quantos registros pular em vez de fazer uma tentativa para cada registro. Há um bom texto sobre isso aqui: https://richardstartin.github.io/posts/reservoir-sampling
A variante de amostragem por reservatório ponderada é usada no ReSTIR (Reamostragem Espaço-Temporal por Reservatório para ray tracing em tempo real). Ele é um estimador de transporte de luz probabilístico com denoising espaço-temporal embutido
Um estimador de transporte de luz tenta calcular a quantidade de luz que passa por uma cena (https://en.wikipedia.org/wiki/Radiance). Para isso, precisa integrar a radiância de todos os caminhos possíveis que a luz pode percorrer, mantendo a conservação de energia (https://en.wikipedia.org/wiki/Rendering_equation)
Exceto em casos muito simples, essa integral da equação de renderização não tem uma solução fechada tratável, então precisa ser resolvida de forma probabilística
A ideia básica é o método de Monte Carlo (https://en.wikipedia.org/wiki/Monte_Carlo_method): amostrar aleatoriamente muitos caminhos possíveis e tirar a média
Nas décadas seguintes, evoluíram estratégias mais sofisticadas, como amostragem por importância (IS), amostragem por múltipla importância (MIS), reamostragem por importância de amostras (SIR), amostragem por importância com reamostragem (RIS), amostragem por reservatório ponderada (WRS) e o ReSTIR, que combina RIS e WRS
Há um texto detalhado aqui: https://agraphicsguynotes.com/posts/understanding_the_math_b...
Isso me faz pensar que eu deveria refletir mais sobre o algoritmo usado pelos Aliados para estimar o número de tanques alemães por números de série
As estimativas de campo eram cerca de 5 vezes maiores que a produção real, mas a técnica dos números de série teve mais de 90% de precisão
Bom texto, e a explicação também é excelente. Parece tratar do Algorithm R, que provavelmente foi descrito primeiro por Vitter: https://www.cs.umd.edu/~samir/498/vitter.pdf
O artigo anterior de Vitter https://dl.acm.org/doi/10.1145/358105.893 cita o volume 2 de TAOCP, de Knuth, e Knuth, por sua vez, não traz outra citação
Do ponto de vista de ciência de dados, a quantidade de dados em si também contém informações muito importantes, então é bom registrar nos logs quantos itens cada ponto de dados representa
Por exemplo, se a taxa de amostragem for 10%, incluir um campo com o valor 10 permite reconstruir e estimar a maioria das estatísticas, como count, sum e average
A estrutura é boa e a explicação também. Se você tem curiosidade sobre a versão com pesos, já expliquei um pouco aqui: https://gregable.com/2007/10/reservoir-sampling.html
Também há uma versão distribuída que pode ser feita facilmente com MapReduce
Um algoritmo bem simples é criar um par aleatório para cada item do stream e manter os N maiores com base nesse valor aleatório
Primeiro, a implementação intuitiva que ranqueia com
POW(RANDOM(), 1.0 / weight)e depois escolhe os N maiores tem problemas de estabilidade numérica quando os pesos são muito grandes ou muito pequenosSegundo, a amostra resultante não tem a mesma distribuição da população original nem em termos de valor esperado. Isso é especialmente verdadeiro quanto mais o peso total se concentra em poucos elementos da população, mas, em muitos casos, é uma aproximação utilizável
Tratei mais desses problemas aqui: https://blog.moertel.com/posts/2024-08-23-sampling-with-sql....
Excelente texto, acessível e com ótimas visualizações
No $WORK, usamos uma variação parecida para resolver o problema relacionado de estimar algum percentil em um stream em execução
O percentil que queremos escolher muda de vez em quando, mas em geral fica fixo por mais de 1 trilhão de iterações, e os dados subjacentes são quase estacionários
Se apoiarmos esse processo em uma árvore splay, é possível estimar percentis em O(1) amortizado. Com o mesmo uso de RAM, a margem de erro é maior do que em várias outras técnicas, mas é muito rápido
Também dá para ajustar a probabilidade de substituição para criar uma “meia-vida dos dados” por tempo ou por contagem e enviesar a estimativa para eventos mais recentes, o que é mais adequado para alguns problemas