Thuật toán mới đếm số phần tử duy nhất một cách hiệu quả
(quantamagazine.org)- Thuật toán CVM xấp xỉ số lượng phần tử khác nhau trong một luồng dữ liệu dài, từ đó ước tính số phần tử duy nhất mà không cần lưu toàn bộ danh sách
- Tập trung vào bài toán phần tử duy nhất (distinct elements problem) khi toàn bộ đầu vào vượt quá bộ nhớ, và có thể áp dụng cho các nhật ký quy mô lớn hoặc luồng sự kiện có nhiều dữ liệu trùng lặp
- Thuật toán chỉ giữ lại một số phần tử vừa với bộ nhớ giới hạn và lặp lại việc xóa ngẫu nhiên mỗi khi hết chỗ, để cân bằng xác suất mỗi phần tử được giữ lại
- Trong ví dụ với Hamlet, với bộ nhớ 100 từ, trung bình sau 5 lần chạy thuật toán ước tính được 3.955, khá gần với số từ duy nhất thực tế là 3.967; với bộ nhớ 1.000 từ, giá trị trung bình được cải thiện lên 3.964
- Bộ nhớ càng lớn thì độ chính xác càng cao, và nếu đủ lớn để chứa mọi phần tử duy nhất thì có thể đạt độ chính xác 100%
Đếm phần tử duy nhất trong luồng dữ liệu dài
- Mục tiêu là ước tính hiệu quả số lượng phần tử duy nhất sau khi loại bỏ trùng lặp trong một danh sách dài mà các phần tử đi vào lần lượt từng cái một
- Cách đơn giản nhất là lưu tất cả các phần tử đã thấy cho đến thời điểm hiện tại và mỗi khi có phần tử mới đi vào thì so sánh với danh sách hiện có
- Trong khảo sát động vật hoang dã, cần liên tục kiểm tra danh sách ảnh các con vật đã thấy trước đó
- Với các danh sách lên đến hàng tỷ mục như số người dùng đăng nhập hằng ngày của Facebook, việc lưu trữ và so sánh trở nên khó khăn
- CVM là thuật toán được đặt theo tên của Sourav Chakraborty, Vinodchandran Variyam và Kuldeep Meel
- Có thể áp dụng cho các danh sách mà phần tử đi vào theo thứ tự tuần tự, như từ ngữ, hàng hóa trên băng chuyền hoặc xe cộ trên đường cao tốc
Ý tưởng cốt lõi của thuật toán CVM
- CVM không lưu toàn bộ các phần tử mà chỉ giữ lại một phần trong phạm vi bộ nhớ giới hạn
- Thuật toán dùng tính ngẫu nhiên để kiểm soát xác suất mỗi phần tử duy nhất còn tồn tại trong danh sách cuối cùng
- Andrew McGregor cho rằng thuật toán này rất đơn giản, dễ triển khai và có thể trở thành cách tiếp cận nền tảng cho bài toán phần tử duy nhất trong thực tế
Cách hoạt động qua ví dụ Hamlet
- Hamlet có tổng cộng 30.557 từ và thuật toán sẽ ước tính số từ duy nhất trong đó
- Giả sử bộ nhớ là một bảng trắng chứa được 100 từ, lúc đầu thuật toán bỏ qua các từ lặp lại và ghi 100 từ duy nhất đầu tiên
- Khi không gian đã đầy, với mỗi từ sẽ tung một đồng xu
- Nếu ra mặt ngửa thì giữ lại từ đó
- Nếu ra mặt sấp thì xóa từ đó
- Sau giai đoạn sơ bộ này sẽ còn lại khoảng 50 từ duy nhất
Điều kiện giữ lại ngày càng khắt khe qua từng vòng
- Ở Vòng 1, tiếp tục thêm các từ mới; nếu một từ đã có trong danh sách xuất hiện lại thì tung đồng xu và xóa nếu ra mặt sấp
- Khi danh sách lại đầy 100 từ, thuật toán xóa khoảng một nửa theo kết quả của 100 lần tung đồng xu và Vòng 1 kết thúc
- Từ Vòng 2 trở đi, việc sống sót của một từ trở nên khó hơn
- Nếu gặp từ lặp lại thì xóa nếu ra mặt sấp
- Nếu ra mặt ngửa thì tung thêm một lần nữa, và chỉ giữ lại nếu lần thứ hai cũng ra mặt ngửa
- Ở vòng thứ ba cần 3 lần mặt ngửa liên tiếp, còn ở vòng thứ tư cần 4 lần liên tiếp
- Nói chung, khi kết thúc vòng thứ k, xác suất mỗi từ còn lại sẽ là 1/2^k
Tính giá trị ước lượng và kết quả thực nghiệm
- Có thể ước tính tổng số từ duy nhất bằng cách lấy số từ còn lại trong danh sách cuối cùng chia cho xác suất còn tồn tại của chúng
- Ví dụ, nếu sau 6 vòng còn lại 61 từ thì chia cho xác suất 1/2^6 sẽ thu được ước lượng 3.904
- Số từ duy nhất thực tế trong Hamlet là 3.967
- Bộ nhớ càng lớn thì giá trị ước tính càng gần với giá trị thực
- Với bộ nhớ 100 từ, giá trị ước tính trung bình sau 5 lần chạy là 3.955
- Với bộ nhớ 1.000 từ, giá trị trung bình là 3.964
- Variyam và các đồng nghiệp đã chứng minh bằng toán học rằng độ chính xác của kỹ thuật này mở rộng theo kích thước bộ nhớ
Lời giải đơn giản nhưng không hề tầm thường
- CVM được xem là một bước tiến quan trọng trong bài toán phần tử duy nhất đã được nghiên cứu hơn 40 năm
- William Kuszmaul cho rằng ngay cả với những bài toán rất cơ bản và đã được nghiên cứu kỹ, vẫn có thể còn tồn tại những lời giải đơn giản nhưng không dễ nghĩ ra
1 bình luận
Các ý kiến trên Hacker News
Tôi đã tham gia cùng các tác giả triển khai phiên bản đếm thể tích DNF của thuật toán này. Bài viết liên quan ở đây: https://www.msoos.org/2023/09/pepin-our-probabilistic-approx...
Mã nguồn ở đây: https://github.com/meelgroup/pepin
Thuật toán nhanh đến mức phi lý, đôi khi 30% tổng thời gian được dùng cho I/O đọc file. Nhân tiện, Knuth cũng đã đóng góp cho thuật toán, ghi chú của ông ở đây: https://cs.stanford.edu/~knuth/papers/cvm-note.pdf
Ông ấy đã dành hẳn một tháng từ công việc TAOCP để làm việc này, và đúng như bạn tưởng tượng, ông ấy xuất sắc đến mức khó tin
Thuật toán này trông giống HyperLogLog, vốn cũng được trích dẫn trong bài báo. Nó dùng cùng trực giác là theo dõi các chuỗi mặt ngửa/mặt sấp liên tiếp để có được ước lượng, nhưng có cảm giác như đảo ngược ý tưởng để tạo thành một thuật toán đơn giản hơn: loại bỏ các giá trị đã nhớ tùy theo tính liên tiếp của kết quả tung đồng xu
Nó hoạt động đặc biệt hiệu quả trong bối cảnh streaming, cho phép duy trì một thứ giống như “bộ đếm” số lượng phần tử khác nhau, dù có sai số
Ưu điểm của HyperLogLog là ở một khía cạnh nào đó nó hoạt động như một hash set. Có thể thêm mục, đếm số mục khác nhau, và quan trọng là có thể hợp nhất hai HLL để tạo hợp, trong khi bộ nhớ vẫn cố định ở mức vài KB ngay cả với tập hợp hàng tỷ mục. Các kho dữ liệu phân tán dùng thủ thuật này trong cardinality agg của Elasticsearch/OpenSearch, và PFADD/PFMERGE/PFCOUNT của Redis/Redict
Tôi không rõ thuật toán CVM so sánh chính xác với HLL như thế nào, nhưng vì đã được Knuth xem xét và sinh viên đại học cũng có thể dễ dàng triển khai, có lẽ đây là một thuật toán khá ổn
http://oertl.github.io/hyperloglog-sketch-estimation-paper/
Ở công ty cũ, tôi đã triển khai đúng thuật toán này, đồng thời lưu cùng mỗi giá trị một ước lượng về số lần giá trị đó xuất hiện. Nhờ vậy có thể tạo một danh sách xấp xỉ các giá trị phổ biến nhất cùng count ước lượng của từng giá trị
Trước đây khi làm ở bệnh viện, tôi từng dùng reservoir sampling để tạo một tập con nhỏ các bản ghi được lưu trên băng DAT
Mất gần như cùng một khoảng thời gian để đọc bài báo khoa học như đọc bài blog, và bài báo hữu ích hơn
https://arxiv.org/pdf/2301.10191
Nội dung là ước lượng cardinality của tập các phần tử xuất hiện trong một stream. Thuật toán đơn giản đến mức trong lúc đọc bài báo có thể tự code thử và nghịch với nó
Các tác giả nói rõ rằng độc giả và mục đích mà thuật toán này nhắm tới là sinh viên đại học và giáo trình
Vì Knuth đã trực tiếp review, có lẽ ông cũng đã nhận xét thuật toán này thuộc loại đó. Nếu vậy, việc các tác giả đưa nó vào tiêu đề trông như một kiểu khoe khoang không khiêm tốn, nhưng cũng rất đáng để khoe
Ban đầu tôi nhớ nhầm rằng cách nói này là của Knuth, nhưng trí nhớ của tôi đã sai
Dùng một vòng lặp đơn giản có vẻ đỡ phiền hơn là giải thích https://en.wikipedia.org/wiki/Up_tack. [1]
[1] https://news.ycombinator.com/item?id=40388878
Trước hết, phần xử lý contradiction trông chỉ như lỗi hoặc panic, nên tôi không hiểu vì sao lại diễn đạt như vậy. Ngoài ra giả định 1..m cũng gây rối. Tôi không chắc có cần biết trước kích thước hay không, nhưng đọc thêm thì có vẻ là không. Ta chọn một ngưỡng và xác suất thay đổi theo kích thước stream, nhưng phần mô tả thuật toán lại như thể có một đầu ra duy nhất, nên gây nhầm lẫn
Chernoff bound và delta/epsilon cũng hoàn toàn không được giải thích trong bài báo, nên càng rối hơn. Code tôi thử triển khai bằng Go ở đây: https://github.com/betamos/distinct
Tách phần liên quan đến ngưỡng ra helper hợp lý hơn nhiều so với việc vô tình cấp phát quá nhiều bộ nhớ. Có lẽ cũng nên có phương thức ước lượng độ tin cậy hoặc tỷ lệ lỗi. Không ai biết trước kích thước stream, nên cập nhật giá trị này trong lúc chạy sẽ tự nhiên hơn
Xét đến chủ đề của bài báo, phần chú thích đặc biệt thú vị
Các tác giả nói rằng thay vì quy ước cũ sắp tên tác giả theo thứ tự alphabet, họ chọn thứ tự ngẫu nhiên và đánh dấu bằng r⃝. Bản ghi ngẫu nhiên hóa có thể kiểm chứng công khai ở đây: https://www.aeaweb.org/journals/policies/random-author-order...
[0]: https://arxiv.org/pdf/2301.10191
Có phải phần mô tả thuật toán bị sai không?
Nếu triển khai đúng theo mô tả “khi gặp một từ đã có trong danh sách thì lại tung đồng xu, nếu ra mặt sấp thì xóa từ đó”, tức là “kiểm tra có trong danh sách rồi mới xóa”, thì nó lặp khoảng 20 lần và cho ra ước lượng vô lý như 772800512
Ngược lại, nếu lưu từ trước rồi sau đó xóa từ trùng, thì nhận được 7240, gần với số từ duy nhất thực tế là 7233. Nói cách khác, thứ tự trong mô tả là quan trọng nhưng có vẻ đã được truyền đạt sai
Sau khi đọc bài báo thì kết quả ước lượng mới đúng, và vấn đề chỉ là một else nhỏ. Mô tả của Quanta đọc lên giống như “nếu chưa có trong danh sách thì thêm, nếu không thì xóa theo xác suất”, nhưng triển khai đúng là phải áp dụng điều kiện xác suất sau đó bất kể có thêm hay không
Ước lượng số phần tử duy nhất của một tập và đếm số phần tử duy nhất của một tập là hai việc rất khác nhau. Phương pháp thì hay, nhưng tiêu đề không ổn
Ví dụ trong bầu cử, người ta nói “đếm phiếu”, nhưng nếu kết quả sít sao thì sẽ “kiểm phiếu lại” và hoàn toàn có thể kỳ vọng con số hơi khác với lần đếm ban đầu. Vậy việc đếm phiếu thực ra cũng là ước lượng phiếu, còn kiểm phiếu lại chỉ là một ước lượng với biên lỗi hẹp hơn
Huyền thoại “countless stones” (https://en.wikipedia.org/wiki/Countless_stones) cũng giống như một lời nhắc dân gian rằng ngay cả những thứ to, cứng và tĩnh như các cột đá đứng thì cũng không thể quá chắc rằng mình đã đếm đúng
Trường hợp đếm không phải là ước lượng gần như chỉ giới hạn trong bối cảnh toán học. Đó là khi có thể bảo đảm rằng mọi mục đã được xét không bỏ sót, và không nhầm lẫn danh tính của mục nào với mục khác
Ví dụ mole là một số nguyên, nhưng giá trị của nó chỉ được biết xấp xỉ, và cũng chẳng ai quan tâm đến giá trị chính xác
Mình rất thích những ví dụ về tư duy vượt ra ngoài khuôn khổ kiểu này. Có lẽ càng thích hơn vì đó cũng là phần mình không giỏi trong công việc. Điều quan trọng không chỉ là học cách giải đúng một bài toán, mà là quá trình tìm ra những câu hỏi giúp bài toán đang có trở nên dễ hơn, đôi khi là khả thi hơn
Ở đây, câu hỏi cốt lõi là “không cần con số chính xác, chỉ cần xác định một khoảng xác suất trong các tham số đã định nghĩa”. Với những bài toán khác sẽ có những câu hỏi khác. Hy vọng nếu xem đủ nhiều ví dụ như thế này, ta có thể nội tại hóa quá trình tư duy đó và áp dụng cho đúng
Nếu bạn được trả tiền để ngồi cả ngày trước bảng trắng với những kỹ sư thông minh không kém ở một công ty lớn, chắc chắn bạn cũng có thể tạo ra thứ gì đó mà người đời nhìn vào sẽ gọi là “giải pháp ngoài khuôn khổ”
Nhưng đa số chúng ta được trả tiền để làm việc trên dây chuyền nhà máy JIRA, nên thời gian bám lấy một vấn đề duy nhất để thử nghiệm là có hạn
Ví dụ “nếu muốn đếm số người dùng khác nhau đăng nhập vào Facebook mỗi ngày, trong khi một số người dùng đăng nhập từ nhiều thiết bị và vào nhiều thời điểm thì sao?” có vẻ không phải là tình huống mà thuật toán này thực sự hữu ích cho lắm
Nếu khi thiết kế quy trình đăng nhập bạn đã biết mình cần thông tin này thì khá đơn giản. Chỉ cần lưu ngày đăng nhập gần nhất của từng tài khoản, và chỉ tăng bộ đếm người dùng duy nhất khi giá trị đã lưu khác với ngày hiện tại
Ngay cả nếu không làm vậy, về sau vẫn có thể “phát lại” luồng sự kiện đăng nhập từ cơ sở dữ liệu để phân tích. Trường hợp đã tích lũy dữ liệu nhiều năm thì có thể khác
Liên quan đến việc đếm, tôi muốn nhắc đến một thuật toán hiệu quả và cũng dễ triển khai để tìm k mục hàng đầu trong một luồng. Có vẻ nó ít được biết đến hơn tôi tưởng
A Simple Algorithm for Finding Frequent Elements in Streams and Bags
Karp, Shenker & Papadimitriou
https://www.cs.umd.edu/~samir/498/karp.pdf
Mô tả của bạn nghe như là tìm một số cố định k mục và bảo đảm rằng chúng nhất định là các mục đứng đầu. Còn phần tóm tắt nghe như là tìm các mục thỏa điều kiện lớn hơn một giá trị k cụ thể, với số lượng mục chưa biết trước
Có vẻ giống khác biệt giữa “tìm 100 người dùng lớn tuổi nhất” và “tìm tất cả người dùng trên 30 tuổi”; không biết tôi hiểu sai lời bạn hay phần tóm tắt? Tiếng Anh không phải tiếng mẹ đẻ của tôi nên hơi rối
Vậy là các nhà khoa học máy tính đã phát minh ra cách ước lượng kích thước tập con một cách tiết kiệm bộ nhớ