Reservoir Sampling: Cara Mengambil Sampel Acak yang Adil dari Data yang Ukurannya Tidak Diketahui
(samwho.dev)- Reservoir sampling adalah teknik pengambilan sampel yang memberi setiap item peluang terpilih yang sama, meski pada stream data yang ukuran totalnya tidak diketahui, dengan hanya menyimpan jumlah item tertentu di memori
- Untuk array yang ukurannya diketahui, mengacak urutan atau memilih indeks acak sudah cukup, tetapi pada stream yang tidak memungkinkan kembali ke item yang sudah lewat, diperlukan pendekatan berbeda
- Dalam pemilihan satu item, item ke-n diterima dengan probabilitas 1/n, sehingga peluang item baru untuk terpilih dan peluang item lama untuk bertahan diseimbangkan
- Saat memilih beberapa item, item baru diterima dengan probabilitas k/n sesuai jumlah simpanan k, lalu jika perlu satu item yang sedang disimpan diganti secara acak
- Jika diterapkan pada pengumpulan log, metode ini dapat mengurangi kehilangan log pada periode sepi sekaligus penggunaan memori, tanpa melewati batas pemrosesan seperti maksimal 5 item per detik
Sampling dari himpunan yang ukurannya diketahui
- Jika ingin mengambil 3 kartu secara acak dari 10 kartu, cukup acak seluruhnya lalu pilih 3 kartu pertama untuk memberi setiap kartu probabilitas terpilih yang sama
- Jika jumlah kartu bertambah menjadi 1 juta, mengacak langsung menjadi sulit, tetapi pada struktur yang bisa diakses lewat indeks seperti array, memilih 3 indeks acak akan mencapai tujuan yang sama
- Array di memori memudahkan akses ke indeks tertentu, tetapi pekerjaan seperti menghitung kartu ke-436.234 dari tumpukan kartu akan memakan waktu lama dalam praktiknya
Kendala pada stream yang ukurannya tidak diketahui
- Jika Anda hanya bisa melihat 1 kartu pada satu waktu, hanya bisa memegang 1 kartu sekaligus, dan tidak bisa kembali ke kartu yang sudah lewat, Anda harus memilih 1 kartu akhir tanpa mengetahui jumlah totalnya
- Layanan pengumpulan log juga menghadapi masalah dengan bentuk yang mirip
- Menerima pesan log dari layanan lain dan menyimpannya di satu tempat
- Jika log membanjir karena rilis buruk atau lonjakan traffic, layanan pengumpul bisa kewalahan
- Layanan pengumpulan log pada contoh ini memiliki ambang batas untuk memproses 5 log per detik
- Pendekatan mengirim hanya 10% log membantu agar tidak melampaui ambang batas saat terjadi lonjakan, tetapi juga membuang 90% log secara tidak perlu pada periode sepi
- Perilaku yang diinginkan adalah mengirim semua log pada periode sepi, dan mengirim maksimal 5 log per detik pada periode lonjakan
- Jika setiap detik hanya 5 log pertama yang terlihat yang dikirim, log yang datang belakangan kehilangan kesempatan untuk terpilih, sehingga tidak adil
Reservoir sampling untuk satu item
- Reservoir sampling mempertahankan sampel yang adil dari item-item yang sudah terlihat sejauh ini, meski jumlah totalnya tidak diketahui
- Kita bisa saja menyimpan semua pesan di memori lalu memilih nanti, tetapi jika skala spike tidak diketahui, jumlah memori yang dibutuhkan juga sulit diprediksi
- Metode ini menyelesaikan masalah yang sama tanpa memakai memori lebih banyak daripada jumlah sampel yang diminta
- Aturan untuk memilih satu kartu sederhana
- Kartu pertama selalu disimpan
- Kartu baru ke-n disimpan dengan probabilitas 1/n
- Jika kartu baru diputuskan untuk disimpan, kartu yang sebelumnya disimpan dibuang
- Jika mengganti dengan probabilitas 50% pada setiap kartu, kartu-kartu di bagian akhir menjadi lebih diuntungkan sehingga tidak adil
- Kartu pertama harus bertahan dari banyak kesempatan penggantian agar tetap ada setelah kartu ke-10
- Kartu terakhir bisa tetap di tangan hanya dengan sekali terpilih
- Aturan 1/n menyeimbangkan bukan hanya probabilitas kartu baru untuk terpilih, tetapi juga probabilitas kartu lama untuk bertahan
- Kartu pertama disimpan dengan probabilitas 1/1, yaitu 100%
- Pada kartu kedua, kartu baru dipilih dengan probabilitas 1/2, dan kartu pertama juga tetap ada dengan probabilitas 1/2
- Pada kartu ketiga, kartu baru dipilih dengan probabilitas 1/3, dan kartu yang sedang disimpan juga menjadi berpeluang 1/3 karena 50% × 2/3
- Secara umum, pada langkah ke-n, probabilitas kartu lama tetap ada adalah
1/(n-1) * (1-(1/n)), dan probabilitas kartu baru terpilih adalah1/n, sehingga keduanya sama
Ekstensi untuk memilih beberapa item
- Pemilihan satu item dapat diperluas menjadi pemilihan beberapa item
- Untuk memilih k item, ada dua aturan yang berubah
- Item baru dipilih dengan probabilitas k/n, bukan
1/n - Jika perlu penggantian, salah satu dari k item yang sedang disimpan dipilih secara acak dan diganti dengan item baru
- Item baru dipilih dengan probabilitas k/n, bukan
- Probabilitas item lama terpilih dinyatakan sebagai
k/(n-1), lalu dikalikan dengan probabilitas tidak diganti oleh item baru, sehingga keadilan tetap terjaga - Karena semua item yang sedang disimpan memiliki probabilitas yang sama untuk menjadi target penggantian, peluang setiap item untuk tetap ada pada tiap langkah juga tetap sama
- Implementasinya dapat diringkas sebagai penggunaan array berukuran k
- Untuk setiap item baru, buat angka acak dari 0 sampai n
- Jika angka acak lebih kecil dari k, ganti item pada indeks tersebut dengan item baru
- Jika tidak, buang item baru
Menerapkannya pada layanan pengumpulan log
- Pada contoh pengumpulan log,
k=5ditetapkan sehingga hanya maksimal 5 pesan log yang disimpan sekaligus - Setiap detik, log yang terpilih dikirim ke layanan pengumpulan log, lalu array berukuran 5 dikosongkan dan proses dimulai lagi
- Metode ini membuat pola berbongkah yang mengirim kumpulan log pada interval tertentu, bukan stream log real-time
- Sebagai gantinya, jumlah log yang dikirim tidak melewati ambang batas, dan pada periode sepi jumlah seluruh log serta log yang dikirim bergerak hampir bersamaan
- Pada periode sepi, log tidak hilang; pada periode lonjakan, log yang dikirim tidak melebihi ambang batas per detik; dan ruang penyimpanan juga tidak melebihi
k=5log
Saat bobot diperlukan
- Sebagian log bisa lebih bernilai daripada log lain
- Misalnya, Anda mungkin ingin menyimpan semua log error
- Dalam kasus seperti ini, varian reservoir sampling berbasis bobot dapat digunakan
- Reservoir sampling adalah algoritme yang memungkinkan masalah sampling stream yang awalnya tampak mustahil diselesaikan dengan memori kecil
1 komentar
Komentar Hacker News
Saat kecil saya tinggal di daerah pedesaan, dan saya dengar teman ayah saya karena pekerjaannya harus menghitung populasi rock ptarmigan di pegunungan setiap tahun
Katanya dia berjalan di rute yang sudah ditentukan, mengejutkan burung agar terbang pada interval tertentu lalu menghitung jumlahnya, dan total itu diserahkan ke instansi pemerintah untuk dipakai memperkirakan populasi keseluruhan
Pada suatu tahun dia harus pergi ke luar negeri saat periode survei, jadi dia menjelaskan metodenya dengan rinci kepada seorang teman dan meminta temannya menggantikan
Namun temannya lupa pada hari-H, dan karena repot dia asal mengirim angka yang kelihatannya masuk akal
Tahun berikutnya, halaman depan koran lokal memuat judul kenaikan populasi rock ptarmigan yang memecahkan rekor, dan rupanya dia tidak memikirkan bahwa estimasi itu dipakai untuk menentukan kuota izin berburu
https://en.wikipedia.org/wiki/Rock_ptarmigan
Dulu saya membuat sistem reservasi untuk beberapa resor ski yang cukup besar, dan saat jadwal molor hingga kami lembur semalaman, salah satu hal terakhir yang harus saya selesaikan adalah laporan statistik resmi seperti jumlah tamu menginap yang diumumkan pemerintah
Cukup saya bilang bahwa statistik tahun itu hampir tidak ada hubungannya dengan kenyataan
Saya penulis artikel ini. Kalau ada pertanyaan saya bisa menjawab, dan masukan juga sangat diterima
Semua kode untuk artikel-artikel saya ada di https://github.com/samwho/visualisations dan berlisensi MIT, jadi silakan dipakai dengan bebas
Perluasan reservoir sampling yang lebih menarik adalah, alih-alih mengambil bilangan acak untuk tiap item guna menentukan apakah akan diganti dan item mana yang diganti, kita bisa mengambil nilai dari distribusi geometri untuk menentukan berapa banyak item yang bisa dilewati dengan aman sampai penggantian berikutnya
Ini sangat berguna terutama jika banyak item bisa dilewati dengan murah, misalnya saat tape drive bisa dipercepat tetapi panjang totalnya tidak diketahui, atau saat sebagian besar sistem bisa dibiarkan dalam mode hemat daya selama periode lompatan itu
Saat memilih k dari n item, pendekatan ini melakukan sampling dan lompatan sekitar O(k * log (n/k)) kali
Secara konseptual saya lebih suka versi reservoir sampling yang memberi prioritas acak tetap pada setiap kartu saat datang, lalu hanya mempertahankan k prioritas teratas
Masalah lanjutan di sini adalah memilih k teratas dari stream dengan panjang tak diketahui dalam waktu O(n) dan ruang O(k). Jika sekadar memelihara min-heap, ruangnya memang O(k) tetapi waktunya menjadi O(n log k)
Sebagai gantinya, kita bisa memakai buffer tak terurut berkapasitas maksimal 2k, terus menambahkan item, dan saat penuh gunakan quickselect acak atau median-of-medians untuk menyisakan hanya k item teratas dalam O(k). Karena untuk total n item kita melakukan kerja O(2k) setiap k item, waktu jalan totalnya menjadi O(n)
Topik terkait lainnya adalah rendezvous hashing: https://en.wikipedia.org/wiki/Rendezvous_hashing
Sebagai tambahan, ada juga tulisan bagus tentang metode alias untuk sampling dari distribusi probabilitas diskret: https://www.keithschwarz.com/darts-dice-coins/
Namun awalnya ceritanya tentang memilih 3 kartu secara acak dari dek berisi 10 atau 436.234 kartu, lalu tiba-tiba berubah menjadi memilih hanya 1 kartu, jadi saya sempat bingung
Akan lebih jelas kalau ada judul bagian sebelum “Now let me throw you a curveball...” seperti, “Mulai sekarang kita beralih ke asumsi yang disederhanakan: bukan lagi memegang 3 kartu, melainkan hanya 1 kartu, dan ukuran deknya juga tidak diketahui”
Tapi saya tidak yakin apakah saya benar-benar memahami validitas statistik dari pendekatan ini. Saya paham bahwa peluang semua log dari periode tertentu untuk ikut terambil itu sama, tetapi kalau begitu bukankah log yang muncul pada “jam sepi” jadi terlalu terwakili dalam metrik keseluruhan?
Misalnya jika saya ingin tahu endpoint mana yang paling banyak menghabiskan waktu untuk mengurangi total biaya seluruh fleet (CPU-detik dan sebagainya), endpoint yang menerima traffic bursty bisa jadi kurang terwakili dibanding endpoint yang menerima traffic stabil, sehingga metode ini tampak tidak cocok
Akibatnya kita bisa membuang waktu mengoptimalkan endpoint yang sebenarnya traffic-nya tidak terlalu besar
Saya juga penasaran, dalam perencanaan kapasitas per layanan, apakah memang benar layanan dengan traffic bursty akan kurang terwakili
Saya ingin tahu reservoir sampling cocok untuk kasus penggunaan seperti apa, dan analisis statistik apa yang bisa dilakukan pada data yang dikembalikannya
Tulisan dan penjelasannya sangat bagus
Dari sudut pandang praktis, saya tetap merasa cara ini akan menjadi opsi terakhir untuk pengumpulan log. Saya paham bahwa saat terjadi lonjakan, sesuatu memang harus dibuang, tetapi inti persoalannya adalah apa yang harus dibuang
Menentukan apa yang dibuang secara “adil” tampaknya tidak terlalu bermakna
Akan lebih baik membuang log berprioritas rendah terlebih dahulu, dan jika ada level log seperti debug/info/warning/error, maka peristiwa dengan tingkat keparahan lebih tinggi bisa diprioritaskan sementara log debug yang panjang dibuang lebih dulu
Log sequence juga bisa dikelompokkan sebagai bagian dari satu aktivitas; untuk aktivitas yang berhasil, cukup catat awal dan akhir atau perubahan status kunci, lalu hilangkan log tengah yang berulang
Saat terjadi lonjakan, alih-alih menyimpan setiap baris log, jika pesan yang mirip atau duplikat diagregasikan dan diringkas, jumlahnya berkurang dan tren juga akan terlihat lebih jelas
Dan jumlah total baris log yang dikumpulkan juga ingin dibatasi dengan anggaran yang lebih besar. Reservoir sampling bisa menangani semua ini
Reservoir sampling yang adil pun bisa dibuat tidak adil dengan cara yang terkontrol. Misalnya, item dengan isi yang sangat menarik bisa diberi peluang lebih besar untuk dipertahankan
Sebagai upaya terakhir, ini adalah teknik yang bersaing dengan pemilihan acak yang lebih bias dan kurang berprinsip, atau bahkan dengan algoritma pemilihan yang sama sekali tidak acak
Tulisan yang benar-benar bagus dan divisualisasikan dengan sangat baik
Sebagai pengembangan lanjutan, ada algoritme yang menghitung berapa banyak record yang dilewati alih-alih melakukan percobaan pada setiap record. Ada tulisan yang bagus tentang ini di sini: https://richardstartin.github.io/posts/reservoir-sampling
Varian weighted reservoir sampling digunakan dalam ReSTIR (spatiotemporal reservoir resampling untuk ray tracing real-time). Ini adalah estimator transport cahaya stokastik dengan denoising spatiotemporal bawaan
Estimator transport cahaya mencoba menghitung jumlah cahaya yang melewati sebuah adegan(https://en.wikipedia.org/wiki/Radiance). Untuk itu, ia harus mengintegralkan radiance dari semua jalur yang mungkin dilalui cahaya sambil menjaga kekekalan energi(https://en.wikipedia.org/wiki/Rendering_equation)
Kecuali untuk kasus yang sangat sederhana, integral pada persamaan rendering ini tidak memiliki solusi bentuk tertutup yang mudah ditangani, sehingga harus diselesaikan secara probabilistik
Ide dasarnya adalah metode Monte Carlo(https://en.wikipedia.org/wiki/Monte_Carlo_method), yaitu mengambil banyak sampel acak dari jalur yang mungkin lalu menghitung rata-ratanya
Setelah itu, selama beberapa dekade berkembang strategi yang lebih canggih seperti importance sampling (IS), multiple importance sampling (MIS), sample importance resampling (SIR), resampled importance sampling (RIS), weighted reservoir sampling (WRS), dan ReSTIR yang menggabungkan RIS dan WRS
Tulisan rinci ada di sini: https://agraphicsguynotes.com/posts/understanding_the_math_b...
Melihat ini membuat saya merasa perlu memikirkan lagi algoritme yang digunakan Sekutu untuk memperkirakan jumlah tank Jerman dari nomor seri
Estimasi lapangan sekitar 5 kali lipat dari produksi sebenarnya, tetapi teknik nomor seri itu akurat lebih dari 90%
Tulisan yang bagus dan penjelasannya juga sangat baik. Ini tampaknya membahas Algorithm R yang mungkin pertama kali dijelaskan oleh Vitter: https://www.cs.umd.edu/~samir/498/vitter.pdf
Makalah Vitter yang lebih lama https://dl.acm.org/doi/10.1145/358105.893 mengutip TAOCP jilid 2 karya Knuth, dan di Knuth pun tidak ada sitasi lagi
Dari sudut pandang data science, jumlah data itu sendiri juga memuat informasi yang sangat penting, jadi sebaiknya log juga mencatat berapa banyak data yang diwakili oleh setiap titik data
Misalnya jika rasio sampling adalah 10%, maka bisa ditambahkan field yang berisi 10, sehingga sebagian besar statistik seperti count, sum, dan average dapat direkonstruksi dan diestimasi kembali
Susunannya bagus dan penjelasannya juga sangat baik. Jika penasaran dengan versi berbobot, pernah dijelaskan sedikit di sini: https://gregable.com/2007/10/reservoir-sampling.html
Ada juga versi terdistribusi yang bisa dibuat dengan mudah menggunakan MapReduce
Untuk algoritme yang sangat sederhana, bisa juga membuat pasangan acak untuk setiap item dalam stream, lalu mempertahankan N teratas berdasarkan nilai acak tersebut
Pertama, implementasi intuitif yang memberi peringkat dengan
POW(RANDOM(), 1.0 / weight)lalu memilih N teratas memiliki masalah stabilitas numerik saat bobot sangat besar atau sangat kecilKedua, sampel hasilnya tidak memiliki distribusi yang sama dengan populasi asal bahkan jika dilihat dari nilai harapannya. Ini особенно berlaku saat total bobot terkonsentrasi pada sedikit elemen populasi, tetapi dalam banyak kasus masih merupakan pendekatan yang berguna
Masalah-masalah ini dibahas lebih lanjut di sini: https://blog.moertel.com/posts/2024-08-23-sampling-with-sql....
Tulisan yang luar biasa, mudah diikuti, dan visualisasinya juga sangat baik
Di $WORK kami memakai variasi yang mirip untuk menyelesaikan masalah terkait, yaitu memperkirakan persentil tertentu dari stream yang sedang berjalan
Persentil yang ingin dipilih kadang berubah, tetapi umumnya tetap selama lebih dari 1 triliun iterasi, dan ada kendala bahwa data dasarnya bersifat kuasi-stasioner
Jika proses ini ditopang dengan splay tree, estimasi persentil dengan amortized O(1) dimungkinkan. Dengan penggunaan RAM yang sama, rentang galatnya lebih besar daripada berbagai teknik lain, tetapi sangat cepat
Probabilitas penggantian juga bisa disesuaikan untuk memberi “waktu paruh data” berdasarkan waktu atau jumlah, sehingga estimasi menjadi bias ke event yang lebih baru, dan untuk beberapa masalah pendekatan ini lebih cocok