- Reservoir sampling là kỹ thuật lấy mẫu cho phép chỉ giữ một số lượng phần tử cố định trong bộ nhớ ngay cả với luồng dữ liệu không biết trước tổng kích thước, đồng thời bảo đảm mọi phần tử đều có cơ hội được chọn như nhau
- Với mảng đã biết kích thước, chỉ cần xáo trộn hoặc chọn chỉ mục ngẫu nhiên là đủ, nhưng với stream không thể quay lại các phần tử đã đi qua thì cần một cách tiếp cận khác
- Khi chọn một phần tử duy nhất, phần tử thứ n được chấp nhận với xác suất 1/n để cân bằng giữa khả năng được chọn của phần tử mới và khả năng sống sót của phần tử hiện có
- Khi chọn nhiều phần tử, phần tử mới được chấp nhận với xác suất k/n theo số lượng lưu trữ k, và nếu cần thì thay ngẫu nhiên một phần tử đang được giữ
- Áp dụng vào thu thập log, có thể không vượt quá giới hạn xử lý như tối đa 5 log mỗi giây, đồng thời giảm cả việc mất log trong các khoảng thời gian yên ắng lẫn lượng bộ nhớ sử dụng
Lấy mẫu trong tập hợp đã biết kích thước
- Nếu rút ngẫu nhiên 3 lá từ 10 lá bài, chỉ cần xáo trộn toàn bộ rồi chọn 3 lá đầu là có thể cho mỗi lá xác suất được chọn như nhau
- Nếu số lá bài tăng lên 1 triệu, việc xáo trộn trực tiếp trở nên khó khăn, nhưng với cấu trúc có thể truy cập bằng chỉ mục như mảng thì chọn 3 chỉ mục ngẫu nhiên sẽ đạt cùng mục đích
- Mảng trong bộ nhớ cho phép truy cập một chỉ mục cụ thể dễ dàng, nhưng việc đếm lá bài thứ 436,234 trong một chồng bài là thao tác thực tế rất tốn thời gian
Những ràng buộc phát sinh với stream không biết kích thước
- Nếu mỗi lần chỉ nhìn được 1 lá bài, đồng thời chỉ có thể cầm 1 lá, và không thể quay lại lá đã đi qua, thì phải chọn ra 1 lá cuối cùng mà không biết tổng số lá
- Dịch vụ thu thập log cũng gặp bài toán tương tự
- Nhận các thông điệp log từ những dịch vụ khác và lưu vào một nơi
- Khi có bản phát hành lỗi hoặc lưu lượng tăng đột biến, dịch vụ thu thập có thể bị quá tải
- Dịch vụ thu thập log trong ví dụ có ngưỡng xử lý 5 log mỗi giây
- Cách chỉ gửi 10% log giúp không vượt ngưỡng trong giai đoạn tăng đột biến, nhưng cũng khiến 90% log bị bỏ đi không cần thiết trong các giai đoạn yên ắng
- Hành vi mong muốn là gửi tất cả log trong giai đoạn yên ắng, còn khi tăng đột biến thì chỉ gửi tối đa 5 log mỗi giây
- Nếu chỉ gửi 5 log đầu tiên nhìn thấy trong mỗi giây thì những log đến sau sẽ mất cơ hội được chọn, nên không công bằng
Reservoir sampling với một phần tử
- Reservoir sampling duy trì một mẫu công bằng trong số các phần tử đã thấy cho đến thời điểm hiện tại ngay cả khi không biết tổng số phần tử
- Cũng có thể lưu tất cả thông điệp vào bộ nhớ rồi chọn sau, nhưng nếu không biết quy mô của đợt tăng đột biến thì cũng khó dự đoán lượng bộ nhớ cần thiết
- Cách này giải quyết cùng bài toán mà không dùng nhiều bộ nhớ hơn số lượng mẫu được yêu cầu
- Quy tắc chọn một lá bài rất đơn giản
- Luôn giữ lá đầu tiên
- Lá mới thứ n được giữ với xác suất 1/n
- Nếu quyết định giữ lá mới thì bỏ lá đang giữ hiện tại
- Nếu thay thế ở mỗi lá với xác suất 50% thì các lá về sau sẽ có lợi thế và kết quả không còn công bằng
- Lá đầu tiên phải sống sót qua tất cả các lần có thể bị thay thế để vẫn còn sau lá thứ 10
- Lá cuối cùng chỉ cần được chọn một lần là có thể nằm trong tay
- Quy tắc 1/n cân bằng không chỉ xác suất được chọn của lá mới mà cả xác suất sống sót của lá cũ
- Lá đầu tiên được giữ với xác suất 1/1, tức 100%
- Ở lá thứ hai, lá mới được chọn với xác suất 1/2 và lá đầu tiên cũng còn lại với xác suất 1/2
- Ở lá thứ ba, lá mới được chọn với xác suất 1/3 và lá đang được giữ từ trước cũng có xác suất 50% × 2/3 = 1/3
- Tổng quát, ở bước thứ n, xác suất lá cũ còn lại là
1/(n-1) * (1-(1/n))và xác suất lá mới được chọn là1/n, nên bằng nhau
Mở rộng để chọn nhiều phần tử
- Việc chọn một phần tử có thể mở rộng thành chọn nhiều phần tử
- Để chọn k phần tử, có hai quy tắc thay đổi
- Phần tử mới được chọn với xác suất k/n thay vì
1/n - Nếu cần thay thế, chọn ngẫu nhiên một trong k phần tử đang giữ rồi thay bằng phần tử mới
- Phần tử mới được chọn với xác suất k/n thay vì
- Xác suất được chọn của phần tử hiện có được biểu diễn là
k/(n-1), rồi nhân với xác suất không bị phần tử mới thay thế để giữ tính công bằng - Vì mọi phần tử đang giữ đều có cùng xác suất trở thành đối tượng bị thay thế, nên ở mỗi bước xác suất tiếp tục được giữ của từng phần tử cũng luôn như nhau
- Có thể triển khai bằng một mảng kích thước k
- Với mỗi phần tử mới, tạo một số ngẫu nhiên từ 0 đến n
- Nếu số ngẫu nhiên nhỏ hơn k thì thay phần tử ở chỉ mục đó bằng phần tử mới
- Nếu không thì loại bỏ phần tử mới
Áp dụng vào dịch vụ thu thập log
- Trong ví dụ thu thập log, đặt
k=5để tại một thời điểm chỉ giữ tối đa 5 thông điệp log - Mỗi giây gửi các log đã được chọn đến dịch vụ thu thập log, sau đó làm trống mảng kích thước 5 và bắt đầu lại
- Cách này tạo ra mẫu truyền theo lô theo từng khoảng thời gian thay vì luồng log thời gian thực liên tục
- Đổi lại, số log được gửi sẽ không vượt ngưỡng, và trong các giai đoạn yên ắng thì tổng log và log được gửi gần như biến động cùng nhau
- Trong giai đoạn yên ắng, log không bị mất; còn trong giai đoạn tăng đột biến, số log gửi đi không vượt quá ngưỡng mỗi giây, đồng thời dung lượng lưu trữ cũng không vượt quá
k=5log
Khi cần trọng số
- Một số log có thể giá trị hơn những log khác
- Ví dụ, có thể muốn giữ lại toàn bộ log lỗi
- Trong trường hợp này, có thể dùng biến thể weighted reservoir sampling
- Reservoir sampling là một thuật toán cho phép giải bài toán lấy mẫu stream tưởng như bất khả thi lúc đầu chỉ với ít bộ nhớ
1 bình luận
Các ý kiến trên Hacker News
Hồi nhỏ tôi sống ở vùng quê, và nghe kể rằng một người bạn của bố tôi, do tính chất công việc, hằng năm phải đếm số lượng cá thể gà gô đá trên núi
Ông ấy đi theo một tuyến đường định sẵn, cứ cách một khoảng lại làm chim hoảng sợ bay lên rồi đếm số lượng; tổng số đó được nộp cho cơ quan nhà nước và dùng để ước tính tổng quần thể
Có một năm, đúng thời điểm khảo sát ông ấy phải ra nước ngoài, nên đã giải thích chi tiết phương pháp cho một người bạn và nhờ làm thay, nhưng người bạn đó quên mất vào ngày hôm ấy, lại thấy phiền phức, nên chỉ nộp đại một con số nghe có vẻ hợp lý
Năm sau, trang nhất báo địa phương đăng tiêu đề số lượng cá thể gà gô đá tăng kỷ lục, vì người bạn đó đã không nghĩ đến việc ước tính ấy được dùng để quyết định hạn ngạch săn bắn
https://en.wikipedia.org/wiki/Rock_ptarmigan
Trước đây tôi từng xây dựng hệ thống đặt chỗ cho vài khu nghỉ dưỡng trượt tuyết khá lớn; vì tiến độ bị trễ nên trong một đêm làm xuyên đêm, một trong những việc cuối cùng phải hoàn tất là báo cáo thống kê chính thức kiểu như số khách lưu trú do chính phủ công bố
Tôi chỉ nói thế này: thống kê năm đó gần như không liên quan gì đến thực tế
Tôi là tác giả bài này. Nếu có câu hỏi tôi có thể trả lời, và cũng hoan nghênh phản hồi
Mã của tất cả bài viết nằm ở https://github.com/samwho/visualisations và dùng giấy phép MIT, nên mọi người có thể thoải mái sử dụng
Nếu mở rộng reservoir sampling theo hướng thú vị hơn, thay vì rút số ngẫu nhiên cho từng mục để quyết định có thay thế hay không và thay mục nào, ta có thể rút một giá trị từ phân phối hình học để xác định số mục có thể bỏ qua an toàn trước lần thay thế tiếp theo
Cách này đặc biệt hữu ích nếu có thể bỏ qua nhiều mục với chi phí thấp, chẳng hạn như có thể tua nhanh ổ băng nhưng không biết tổng độ dài, hoặc có thể đặt phần lớn hệ thống vào trạng thái tiết kiệm điện trong lúc bỏ qua
Khi chọn k mục trong n mục, cách này thực hiện xấp xỉ O(k * log (n/k)) lần lấy mẫu và bỏ qua
Về mặt khái niệm, tôi thích phiên bản reservoir sampling trong đó mỗi thẻ khi đến được gán một độ ưu tiên ngẫu nhiên cố định, và chỉ giữ lại k thẻ có độ ưu tiên cao nhất
Vấn đề tiếp theo ở đây là chọn k phần tử đứng đầu từ một luồng không biết độ dài trong thời gian O(n) và không gian O(k). Cách đơn giản là duy trì một min-heap thì đạt O(k) không gian nhưng tốn O(n log k) thời gian
Thay vào đó, có thể dùng một bộ đệm không có thứ tự với sức chứa tối đa 2k, thêm mục vào đó, và khi đầy thì dùng quickselect ngẫu nhiên hoặc median-of-medians để chỉ giữ lại k mục đứng đầu trong O(k). Vì với toàn bộ n mục, cứ mỗi k mục lại làm O(2k) việc, nên thời gian chạy là O(n)
Một chủ đề liên quan là rendezvous hashing: https://en.wikipedia.org/wiki/Rendezvous_hashing
Nhân tiện, cũng có một bài viết hay về phương pháp alias để lấy mẫu từ phân phối xác suất rời rạc: https://www.keithschwarz.com/darts-dice-coins/
Tuy nhiên lúc đầu câu chuyện là chọn ngẫu nhiên 3 lá từ bộ bài 10 lá hoặc 436.234 lá, rồi đột nhiên chuyển sang chuyện chỉ chọn 1 lá, nên tôi hơi bối rối trong chốc lát
Có lẽ sẽ rõ ràng hơn nếu trước đoạn “Now let me throw you a curveball...” có một tiêu đề mục kiểu như “Từ giờ ta chuyển sang giả định đơn giản hóa: chỉ giữ 1 lá thay vì 3 lá, và cũng không biết kích thước bộ bài”
Tuy vậy, tôi không chắc mình đã hiểu đúng tính hợp lệ về mặt thống kê của cách tiếp cận này. Tôi hiểu rằng mọi log trong một khoảng thời gian nhất định đều có xác suất được đưa vào như nhau, nhưng như vậy chẳng phải log phát sinh trong “khung giờ chậm” sẽ bị đại diện quá mức trong các chỉ số tổng thể sao?
Ví dụ, nếu muốn biết endpoint nào tiêu tốn nhiều thời gian nhất để giảm tổng chi phí của toàn bộ fleet (CPU-giây, v.v.), thì endpoint nhận lưu lượng bùng phát có thể bị đại diện thiếu so với endpoint nhận lưu lượng đều đặn, nên phương pháp này có vẻ không phù hợp
Khi đó ta có thể lãng phí thời gian tối ưu hóa một endpoint thực ra không có nhiều lưu lượng
Tôi cũng thắc mắc liệu trong lập kế hoạch dung lượng theo từng dịch vụ, việc các dịch vụ nhận lưu lượng bùng phát bị đại diện thiếu có phải là điều mong muốn không
Tôi muốn biết reservoir sampling phù hợp với những trường hợp sử dụng nào, và có thể thực hiện những phân tích thống kê nào trên dữ liệu được trả về
Bài viết và phần giải thích rất hay
Từ góc nhìn thực tế, dù vậy có lẽ tôi sẽ dùng cách này cho thu thập log sau cùng. Tôi hiểu rằng khi có đột biến thì buộc phải bỏ thứ gì đó, nhưng trọng tâm là phải bỏ cái gì
Việc quyết định “công bằng” xem sẽ bỏ gì dường như không có nhiều ý nghĩa
Tốt hơn là bỏ từ các log có mức ưu tiên thấp; nếu có các mức log như debug/info/warning/error thì có thể ưu tiên các sự kiện có độ nghiêm trọng cao và bỏ các log debug dài dòng trước
Cũng có thể gom chuỗi log thành một phần của một hoạt động: với hoạt động thành công thì chỉ ghi phần bắt đầu và kết thúc hoặc các thay đổi trạng thái cốt lõi, bỏ các log trung gian lặp lại
Khi có đột biến, thay vì lưu mọi dòng log, nếu tổng hợp·tóm tắt các thông điệp tương tự hoặc trùng lặp thì vừa giảm dung lượng, vừa làm xu hướng hiện rõ hơn
Và cũng muốn giới hạn tổng số dòng log được thu thập bằng một ngân sách lớn hơn. Lấy mẫu hồ chứa có thể xử lý tất cả những điều này
Lấy mẫu hồ chứa công bằng cũng có thể được làm cho bất công theo cách có kiểm soát. Ví dụ, có thể tăng xác suất giữ lại những mục có nội dung đặc biệt thú vị
Như phương án cuối cùng, đây là kỹ thuật cạnh tranh với lựa chọn ngẫu nhiên thiên lệch ít nguyên tắc hơn, hoặc với các thuật toán lựa chọn thậm chí không ngẫu nhiên
Bài viết thực sự được viết rất tốt và trực quan hóa rất tốt
Một mở rộng nâng cao là có những thuật toán tính số bản ghi cần bỏ qua thay vì thực hiện phép thử trên từng bản ghi. Có một bài viết hay về chủ đề này ở đây: https://richardstartin.github.io/posts/reservoir-sampling
Biến thể lấy mẫu hồ chứa có trọng số được dùng trong ReSTIR (tái lấy mẫu hồ chứa theo không-thời gian cho dò tia thời gian thực). Đây là một bộ ước lượng truyền ánh sáng xác suất có khử nhiễu không-thời gian tích hợp
Bộ ước lượng truyền ánh sáng cố gắng tính lượng ánh sáng đi qua cảnh (https://en.wikipedia.org/wiki/Radiance). Để làm vậy, cần tích phân radiance của mọi đường đi mà ánh sáng có thể đi qua, đồng thời duy trì bảo toàn năng lượng (https://en.wikipedia.org/wiki/Rendering_equation)
Ngoại trừ những trường hợp rất đơn giản, tích phân này của phương trình kết xuất không có nghiệm dạng đóng dễ xử lý, nên phải giải theo cách xác suất
Ý tưởng cơ bản là dùng phương pháp Monte Carlo (https://en.wikipedia.org/wiki/Monte_Carlo_method): lấy mẫu ngẫu nhiên thật nhiều đường đi khả dĩ rồi lấy trung bình
Trong nhiều thập kỷ sau đó, các chiến lược tinh vi hơn đã phát triển, như importance sampling (IS), multiple importance sampling (MIS), sample importance resampling (SIR), resampled importance sampling (RIS), weighted reservoir sampling (WRS), và ReSTIR kết hợp RIS với WRS
Có bài viết chi tiết ở đây: https://agraphicsguynotes.com/posts/understanding_the_math_b...
Nhìn cái này khiến tôi nghĩ rằng mình nên suy ngẫm thêm về thuật toán mà phe Đồng Minh dùng để ước tính số xe tăng Đức bằng số sê-ri
Ước tính tại hiện trường cao khoảng gấp 5 lần sản lượng thực tế, nhưng kỹ thuật dùng số sê-ri chính xác hơn 90%
Bài hay và giải thích cũng xuất sắc. Có vẻ bài này nói về Algorithm R, có lẽ được Vitter mô tả đầu tiên: https://www.cs.umd.edu/~samir/498/vitter.pdf
Bài trước đó của Vitter https://dl.acm.org/doi/10.1145/358105.893 trích dẫn tập 2 TAOCP của Knuth, còn Knuth thì lại không có trích dẫn
Từ góc nhìn khoa học dữ liệu, bản thân lượng dữ liệu cũng chứa thông tin rất quan trọng, nên tốt nhất là ghi vào log cả việc mỗi điểm dữ liệu đại diện cho bao nhiêu điểm
Ví dụ nếu tỷ lệ lấy mẫu là 10%, có thể thêm một trường chứa giá trị 10; khi đó có thể tái dựng và ước tính hầu hết các thống kê như count·sum·average
Bố cục tốt và phần giải thích cũng rõ ràng. Nếu bạn tò mò về phiên bản có trọng số, tôi từng giải thích một chút ở đây: https://gregable.com/2007/10/reservoir-sampling.html
Cũng có một phiên bản phân tán có thể tạo dễ dàng bằng MapReduce
Một thuật toán rất đơn giản khác là tạo một cặp ngẫu nhiên cho từng mục trong stream, rồi giữ lại N mục đứng đầu theo giá trị ngẫu nhiên đó
Thứ nhất, cách triển khai trực quan là xếp hạng bằng
POW(RANDOM(), 1.0 / weight)rồi chọn N mục đứng đầu sẽ gặp vấn đề về độ ổn định số học khi trọng số rất lớn hoặc rất nhỏThứ hai, mẫu kết quả, ngay cả xét theo kỳ vọng, cũng không có cùng phân phối với quần thể gốc. Điều này đặc biệt đúng khi tổng trọng số tập trung vào một số ít phần tử của quần thể, nhưng trong nhiều trường hợp nó vẫn là một xấp xỉ dùng được
Những vấn đề này được bàn kỹ hơn ở đây: https://blog.moertel.com/posts/2024-08-23-sampling-with-sql....
Một bài viết xuất sắc, dễ tiếp cận và phần trực quan hóa cũng rất tốt
Ở $WORK, chúng tôi dùng một biến thể tương tự để giải một bài toán liên quan: ước lượng một phân vị nào đó từ một stream đang chạy
Phân vị cần chọn thỉnh thoảng có thay đổi, nhưng nhìn chung được giữ cố định trong hơn 1 nghìn tỷ lần lặp, và dữ liệu nền có tính gần dừng
Nếu chống đỡ quá trình này bằng splay tree, có thể ước lượng phân vị với độ phức tạp khấu hao O(1). Với cùng lượng RAM sử dụng, biên độ sai số lớn hơn nhiều kỹ thuật khác, nhưng rất nhanh
Cũng có thể điều chỉnh xác suất thay thế để đặt “chu kỳ bán rã dữ liệu” theo thời gian hoặc số lượng, từ đó làm cho ước lượng thiên về các sự kiện gần đây hơn; với một số bài toán, cách này phù hợp hơn