- Reservoir sampling, toplam boyutu bilinmeyen veri akışlarında bile yalnızca belirli sayıda öğeyi bellekte tutup tüm öğelere eşit seçilme şansı veren bir örnekleme tekniğidir
- Boyutu bilinen bir dizi için karıştırma veya rastgele indeks seçimi yeterlidir; ancak bir kez geçilen öğelere geri dönülemeyen akışlarda farklı bir yaklaşım gerekir
- Tek öğe seçiminde, n’inci öğe 1/n olasılıkla kabul edilerek yeni öğenin seçilme olasılığı ile mevcut öğenin elde kalma olasılığı dengelenir
- Birden fazla öğe seçerken, saklama sayısı k’ye göre yeni öğe k/n olasılıkla kabul edilir ve gerekirse şu anda saklanan öğelerden biri rastgele değiştirilir
- Log toplamaya uygulandığında, saniyede en fazla 5 gibi bir işleme üst sınırını aşmadan, sakin aralıklardaki log kaybını ve bellek kullanımını birlikte azaltabilir
Boyutu bilinen bir kümeden örnekleme
- 10 karttan rastgele 3 kart seçilecekse, tüm desteyi karıştırıp ilk 3 kartı seçmek her karta aynı seçilme olasılığını vermek için yeterlidir
- Kart sayısı 1 milyona çıktığında doğrudan karıştırmak zorlaşır; ancak dizi gibi indeksle erişilebilen yapılarda 3 rastgele indeks seçmek aynı amacı sağlar
- Bellekteki dizilerde belirli bir indekse erişmek kolaydır; ancak bir kart destesindeki 436.234’üncü kartı sayarak bulmak pratikte uzun sürer
Boyutu bilinmeyen akışlarda ortaya çıkan kısıtlar
- Bir seferde yalnızca 1 kart görebiliyor, aynı anda yalnızca 1 kart tutabiliyor ve geçmiş kartlara geri dönemiyorsanız, toplam sayıyı bilmeden nihai 1 kartı seçmeniz gerekir
- Log toplama servisleri de benzer türde bir sorunla karşılaşır
- Diğer servislerden log mesajları alıp tek bir yerde saklar
- Kötü bir sürüm yayını veya trafik artışı nedeniyle loglar yığılırsa toplama servisi bunların altında ezilebilir
- Örnekteki log toplama servisinin saniyede 5 log işleyebilen bir eşiği vardır
- Logların yalnızca %10’unu gönderme yöntemi, ani artış aralıklarında eşiğin aşılmasını engeller; ancak sakin aralıklarda da gereksiz yere logların %90’ını atar
- İstenen davranış, sakin aralıklarda tüm logları göndermek, ani artış aralıklarında ise saniyede en fazla 5 log göndermektir
- Her saniye ilk görülen 5 log gönderilirse, daha sonra gelen loglar seçilme şansını kaybedeceği için bu adil değildir
Tek öğeli reservoir sampling
- Reservoir sampling, toplam sayının bilinmediği durumda bile şimdiye kadar görülen öğeler içinden adil bir örnek tutar
- Tüm mesajları bellekte saklayıp daha sonra seçim yapmak da mümkündür; ancak ani yükselişin ölçeği bilinmiyorsa gereken bellek miktarını tahmin etmek de zordur
- Bu yöntem, istenen örnek sayısından daha fazla bellek kullanmadan aynı sorunu çözer
- Tek bir kart seçme kuralı basittir
- İlk kart her zaman saklanır
- n’inci yeni kart 1/n olasılıkla saklanır
- Yeni kart saklanacaksa, mevcut saklanan kart atılır
- Her kartta %50 olasılıkla değiştirme yapılırsa, sondaki kartlar avantajlı hale gelir ve bu adil olmaz
- İlk kartın 10’uncu karttan sonra da kalması için birçok değiştirme fırsatının hepsinden sağ çıkması gerekir
- Son kartın elde kalması için yalnızca bir kez seçilmesi yeterlidir
- 1/n kuralı, yalnızca yeni kartın seçilme olasılığını değil, mevcut kartın elde kalma olasılığını da dengeler
- İlk kart 1/1, yani %100 olasılıkla saklanır
- İkinci kartta yeni kart 1/2 olasılıkla seçilir, ilk kart da 1/2 olasılıkla kalır
- Üçüncü kartta yeni kart 1/3 olasılıkla seçilir; mevcut saklanan kartın olasılığı da %50 × 2/3 ile 1/3 olur
- Genel olarak n’inci adımda mevcut kartın kalma olasılığı
1/(n-1) * (1-(1/n)), yeni kartın seçilme olasılığı ise1/nolur ve ikisi eşitlenir
Birden fazla öğe seçmeye genişletme
- Tek öğe seçimi, birden fazla öğe seçimine genişletilebilir
- k öğe seçmek için iki kural değişir
- Yeni öğe
1/ndeğil, k/n olasılıkla seçilir - Değiştirme gerekiyorsa, şu anda saklanan k öğeden biri rastgele seçilip yeni öğeyle değiştirilir
- Yeni öğe
- Mevcut öğenin seçilme olasılığı
k/(n-1)olarak ifade edilir ve yeni öğe tarafından değiştirilmememe olasılığıyla çarpılarak adillik korunur - Saklanan tüm öğelerin değiştirilme hedefi olma olasılığı aynı olduğundan, her adımda her öğenin kalmaya devam etme olasılığı da eşit tutulur
- Uygulama, boyutu k olan bir dizi tutma şeklinde özetlenebilir
- Her yeni öğe için 0 ile n arasında rastgele bir sayı üretilir
- Rastgele sayı k’den küçükse, o indeksteki öğe yeni öğeyle değiştirilir
- Değilse yeni öğe atılır
Log toplama servisine uygulama
- Log toplama örneğinde
k=5olarak ayarlanır ve aynı anda en fazla 5 log mesajı saklanır - Her saniye seçilen loglar log toplama servisine gönderilir; ardından boyutu 5 olan dizi boşaltılıp baştan başlanır
- Bu yöntem, gerçek zamanlı log akışı yerine belirli aralıklarla log demetleri gönderen parçalı bir desen oluşturur
- Buna karşılık gönderilen log sayısı eşiği aşmaz ve sakin aralıklarda toplam loglar ile gönderilen loglar neredeyse birlikte hareket eder
- Sakin aralıklarda log kaybedilmez; ani artış aralıklarında saniyelik eşikten fazla log gönderilmez ve depolama alanı da
k=5logu aşmaz
Ağırlık gerektiği durumlar
- Bazı loglar diğerlerinden daha değerli olabilir
- Örneğin hata loglarının tamamını saklamak isteyebilirsiniz
- Bu tür durumlarda ağırlık tabanlı reservoir sampling varyasyonu kullanılabilir
- Reservoir sampling, ilk bakışta imkânsız görünen akış örnekleme problemini az bellekle çözmeyi sağlayan bir algoritmadır
1 yorum
Hacker News yorumları
Çocukken kırsalda yaşıyordum; babamın bir arkadaşının işi gereği her yıl dağlarda kaya ptarmiganı popülasyonunu sayması gerektiğini duymuştum.
Belirlenmiş bir rotada yürür, belli aralıklarla kuşları ürkütüp havalandırır, sonra sayılarını sayar; toplamı da resmi makamlara sunar, bu sayı genel popülasyon tahmininde kullanılırmış.
Bir yıl, sayım döneminde yurt dışına çıkması gerekmiş; yöntemi bir arkadaşına ayrıntılı anlatıp ondan yerine yapmasını istemiş. Ama o arkadaşı o gün unutmuş, uğraştırıcı da geldiği için kabaca makul görünen bir sayı göndermiş.
Ertesi yıl yerel gazetenin birinci sayfasında kaya ptarmiganı popülasyonunda rekor artış başlığı çıkmış; o arkadaş, bu tahminin avlanma izin miktarını belirlemede kullanıldığını düşünememiş.
https://en.wikipedia.org/wiki/Rock_ptarmigan
Eskiden epey büyük kayak tesisleri için rezervasyon sistemleri geliştirmiştim. Takvim gecikince sabahlayarak çalıştığımız sırada bitirmemiz gereken son işlerden biri, hükümetin yayımladığı konaklayan misafir sayısı gibi resmi istatistik raporuydu.
O yılki istatistiklerin gerçekle neredeyse hiç ilgisi yoktu, bu kadarını söyleyeyim.
Bu yazının yazarıyım. Sorularınız varsa yanıtlayabilirim; geri bildirimlere de açığım.
Tüm yazıların kodu https://github.com/samwho/visualisations adresinde ve MIT lisanslı, yani özgürce kullanabilirsiniz.
Reservoir sampling daha ilginç biçimde genişletilirse, her öğe için rastgele sayı çekip değiştirip değiştirmeyeceğine ve nereyi değiştireceğine karar vermek yerine geometrik dağılımdan bir değer çekerek bir sonraki değişime kadar güvenle atlanabilecek öğe sayısı belirlenebilir.
Teyp sürücüsünü hızlı ileri sarabildiğiniz ama toplam uzunluğu bilmediğiniz durumlarda ya da atlama sırasında sistemin büyük kısmını güç tasarrufu modunda tutabildiğiniz durumlarda olduğu gibi, çok sayıda öğeyi ucuza atlayabiliyorsanız özellikle faydalıdır.
n öğeden k örnek seçerken bu yöntem yaklaşık O(k * log (n/k)) kez örnekleme ve atlama yapar.
Kavramsal olarak, her kart geldiğinde ona sabit bir rastgele öncelik atayan ve yalnızca en yüksek öncelikli k öğeyi tutan reservoir sampling sürümünü daha çok tercih ediyorum.
Buradan çıkan problem, uzunluğu bilinmeyen bir akışta en yüksek k öğeyi O(n) zamanda ve O(k) bellekle seçmektir. Basitçe bir min-heap tutarsanız O(k) bellek olur ama O(n log k) zaman alır.
Bunun yerine kapasitesi en fazla 2k olan sırasız bir tampon tutup öğeleri ekleyebilir; dolunca rastgele quickselect veya median-of-medians ile O(k) içinde yalnızca en yüksek k öğeyi bırakabilirsiniz. Toplam n öğe için her k öğede O(2k) iş yapıldığı için O(n) çalışma süresi elde edilir.
İlgili bir konu olarak rendezvous hashing de var: https://en.wikipedia.org/wiki/Rendezvous_hashing
Bir yan not olarak, ayrık olasılık dağılımlarından örnekleme için alias method hakkında iyi bir yazı da var: https://www.keithschwarz.com/darts-dice-coins/
Yalnız başta 10 kartlık ya da 436.234 kartlık desteden rastgele 3 kart seçme hikâyesiyken birden yalnızca 1 kart seçme hikâyesine dönmesi kısa süreliğine kafamı karıştırdı.
“Artık 3 kart değil 1 kart tuttuğumuz ve deste boyutunu da bilmediğimiz basitleştirilmiş varsayıma geçiyoruz” gibi bir bölüm başlığı “Now let me throw you a curveball...”dan önce olursa daha net olabilir.
Ancak bu yaklaşımın istatistiksel geçerliliğini iyi anladığımdan emin değilim. Belirli bir dönemdeki tüm logların dahil edilme olasılığının eşit olduğunu anlıyorum; ama bu durumda “yavaş zaman dilimlerinde” oluşan loglar toplam metriklerde fazla temsil edilmiş olmaz mı?
Örneğin tüm filonun toplam maliyetini (CPU-saniye vb.) azaltmak için hangi endpoint’in en çok zaman harcadığını bilmek istiyorsanız, ani trafik patlamaları alan endpoint, istikrarlı trafik alan endpoint’e kıyasla eksik temsil edilebilir; bu yüzden bu yöntem uygunsuz görünüyor.
Bu durumda aslında çok trafik almayan bir endpoint’i optimize etmeye zaman harcayabilirsiniz.
Servis bazlı kapasite planlamasında da ani trafik patlamaları alan servislerin eksik temsil edilmesinin doğru olup olmadığını merak ediyorum.
Reservoir sampling hangi kullanım senaryolarına uygundur ve dönen verilerle hangi istatistiksel analizler yapılabilir, bunu bilmek isterim.
Yazı ve açıklama harika
Pratik açıdan bakınca yine de bu yöntemi log toplama için en son tercih ederdim. Ani artışlar olursa bir şeylerin atılması gerektiğini anlıyorum, ama asıl mesele neyin atılacağı
Neyin atılacağını “adil” biçimde belirlemenin çok anlamlı göründüğünü sanmıyorum
Düşük öncelikli loglardan başlamak daha iyi; debug/info/warning/error gibi log seviyeleri varsa daha yüksek ciddiyetteki olaylara öncelik verip ayrıntılı debug loglarını önce atabilirsiniz
Ayrıca log dizilerini tek bir etkinliğin parçası olarak gruplayıp, başarılı etkinliklerde yalnızca başlangıç ve bitişi ya da temel durum değişikliklerini kaydetmek, tekrarlayan ara logları çıkarmak da mümkün
Ani artış sırasında her log satırını saklamak yerine benzer veya yinelenen mesajları toplayıp özetlemek hem hacmi azaltır hem de eğilimleri daha iyi ortaya çıkarır
Ayrıca toplanan toplam log satırı sayısını da daha büyük bir bütçeyle sınırlamak istersiniz. Reservoir sampling bunların hepsini halledebilir
Adil reservoir sampling de kontrollü bir biçimde adaletsiz hâle getirilebilir. Örneğin içeriği özellikle ilginç olan öğelerin tutulma olasılığı artırılabilir
Son çare olarak, daha az ilkesel yanlı rastgele seçimlerle ya da rastgele bile olmayan seçim algoritmalarıyla rekabet eden bir tekniktir
Gerçekten iyi yazılmış ve iyi görselleştirilmiş bir yazı
Daha ileri bir uzantı olarak, her kayıt için deneme yapmak yerine atlanacak kayıt sayısını hesaplayan algoritmalar var. Bu konuda iyi bir yazı burada: https://richardstartin.github.io/posts/reservoir-sampling
Ağırlıklı reservoir sampling varyantı ReSTIR’da (gerçek zamanlı ışın izleme için uzay-zamansal reservoir resampling) kullanılıyor. Bu, yerleşik uzay-zamansal gürültü giderme özelliğine sahip olasılıksal bir ışık taşınımı tahminleyicisi
Işık taşınımı tahminleyicisi, bir sahneden geçen ışık miktarını hesaplamaya çalışır (https://en.wikipedia.org/wiki/Radiance). Bunun için enerji korunumu sağlanırken ışığın izleyebileceği tüm yolların radiance’ını integre etmek gerekir (https://en.wikipedia.org/wiki/Rendering_equation)
Çok basit durumlar dışında, rendering equation’daki bu integralin kolay ele alınabilir kapalı formda bir çözümü yoktur; bu yüzden olasılıksal olarak çözülmesi gerekir
Temel fikir Monte Carlo yöntemidir (https://en.wikipedia.org/wiki/Monte_Carlo_method): olası yolları rastgele çok sayıda örnekleyip ortalamasını almak
Sonraki onlarca yıl içinde önem örneklemesi (IS), çoklu önem örneklemesi (MIS), örnek önem yeniden örneklemesi (SIR), yeniden örnekleme önem örneklemesi (RIS), ağırlıklı reservoir sampling (WRS) ve RIS ile WRS’yi birleştiren ReSTIR gibi daha gelişmiş stratejiler geliştirildi
Ayrıntılı yazı burada: https://agraphicsguynotes.com/posts/understanding_the_math_b...
Bunu görünce Müttefiklerin seri numaralarından Alman tanklarının sayısını tahmin ettiği algoritmayı daha çok düşünmem gerektiğini hissettim
Sahadaki tahmin gerçek üretimin yaklaşık 5 katıydı, ama seri numarası tekniği %90’dan fazla doğruydu
Güzel bir yazı ve açıklaması da harika. Bu, Vitter’ın muhtemelen ilk kez açıklamış olduğu Algorithm R’yi ele alıyor gibi görünüyor: https://www.cs.umd.edu/~samir/498/vitter.pdf
Vitter’ın önceki makalesi https://dl.acm.org/doi/10.1145/358105.893 Knuth’un TAOCP 2. cildine atıf yapıyor; Knuth’ta da ayrıca bir atıf yok
Veri bilimi açısından veri miktarının kendisi de çok önemli bilgi taşıdığından, her veri noktasının kaç öğeyi temsil ettiğini de loglamak iyi olur
Örneğin örnekleme oranı %10 ise 10 değerini tutan bir alan koyarsanız count, sum, average gibi çoğu istatistiği yeniden oluşturup tahmin edebilirsiniz
Yapısı iyi, açıklaması da başarılı. Ağırlıklı sürümü merak ediyorsanız, burada biraz anlatmıştım: https://gregable.com/2007/10/reservoir-sampling.html
MapReduce ile kolayca yapılabilecek dağıtık bir sürümü de var.
Çok basit bir algoritma olarak, akıştaki her öğe için rastgele bir çift oluşturup bu rastgele değere göre en üstteki N öğeyi tutmak da mümkün.
Birincisi,
POW(RANDOM(), 1.0 / weight)ile sıralama yapıp en üstteki N öğeyi seçen sezgisel uygulamada, ağırlık çok büyük veya çok küçük olduğunda sayısal kararlılık sorunları oluşur.İkincisi, sonuç örneklem beklenen değer açısından da ana popülasyonla aynı dağılıma sahip olmaz. Toplam ağırlık az sayıda popülasyon öğesinde yoğunlaştıkça bu özellikle böyledir, ama çoğu durumda kullanılabilir bir yaklaşımdır.
Bu sorunları burada daha ayrıntılı ele almıştım: https://blog.moertel.com/posts/2024-08-23-sampling-with-sql....
Harika bir yazı; erişilebilir ve görselleştirmeleri de çok başarılı.
$WORK’te buna benzer bir varyant kullanarak, çalışan bir akışta belirli bir yüzdelik dilimi tahmin etme gibi ilişkili bir problemi çözüyoruz.
Seçilmek istenen yüzdelik dilim ara sıra değişiyor, ancak çoğunlukla 1 trilyondan fazla yineleme boyunca sabit kalıyor; temel veri de yarı durağan.
Bu süreci bir splay tree ile destekleyince amortize O(1) yüzdelik dilim tahmini mümkün oluyor. Aynı RAM kullanımında hata payı başka birçok tekniğe göre daha büyük, ama çok hızlı.
Değiştirme olasılığını ayarlayarak zaman veya sayı bazlı bir “veri yarı ömrü” koyup tahmini daha yakın olaylara doğru yanlı hâle getirmek de mümkün; bazı problemler için bu daha uygun.