GT 10: Thuật toán AMS ước lượng mô-măng tần số

10. Thuật toán AMS ước lượng mô-măng tần số

Tưởng tượng một chuỗi ${m}$ (rất nhiều, cả triệu) gói dữ liệu đi qua một router trong thời gian ngắn. Gói thứ ${i}$ có địa chỉ IP nguồn ${a_i}$ nào đó thuộc tập ${[n] = \{1, \cdots, 2^{32}\}}$ . Với mỗi ${j \in [n]}$ , gọi ${f_j}$ là số lần xuất hiện của địa chỉ ${j}$ , còn gọi là tần suất của ${j}$ . Đại lượng

$\displaystyle F_k = \sum_{j=1}^n f_j^k$

được gọi là mô-măng tần số bậc ${k}$ ( ${k}$ th frequency moment) của dòng dữ liệu này. Bài toán ước lượng mô-măng tần số là một bài toán kinh điển trong lý thuyết dòng dữ liệu. Chúng ta cần thiết kế một cấu trúc dữ liệu có kích thước càng nhỏ càng tốt, để sao cho tại một thời điểm bất kỳ có thể trả lời câu hỏi: “ ${F_k}$ hiện tại khoảng bằng bao nhiêu?”

Như vậy, con số ${m}$ không được biết trước cho đến khi câu hỏi được đặt ra. (Một query được gửi đến cấu trúc dữ liệu này vào thời điểm đó, và CTDL phải trả lời được câu hỏi này trong thời gian càng nhỏ càng tốt.) Cũng như các ví dụ trước, một cấu trúc dữ liệu mà cần bộ nhớ ${\Omega(m,n)}$ là không khả thi. Chúng ta cần kích thước của CTDL khoảng sub-linear (poly-log là tốt nhất) trên các tham số ${m}$ và ${n}$ .

Ước lượng được các mô-măng này có thể giúp chúng ta trả lời nhiều câu hỏi cơ bản về dòng dữ liệu. Ví dụ ${F_0}$ chính là tổng số địa chỉ nguồn khác nhau của dòng. Các mô-măng bậc cao hơn có thể là các đặc điểm dùng cho một thuật toán phân lớp thống kê nào đó: nếu mô-măng nhảy lên nhảy xuống quá độ thì có lẽ là đang có một cuộc tấn công của virus/worm trên mạng chẳng hạn.

Năm 1996, Noga Alon, Yossi Matias, và Mario Szegedy có một bài báo có ảnh hưởng rất lớn đến lý thuyết dòng dữ liệu về bài toán này. Ngoại trừ thuật toán AMS (họ 3 tác giả) sẽ thảo luận trong bài, họ còn giới thiệu kỹ thuật dùng các hàm băm có độ độc lập nhỏ (limited-independence) để tính ${F_2}$ trong không gian tối ưu, và kỹ thuật dùng độ phức tạp giao tiếp (communication complexity) để chứng minh chặn dưới cho độ phức tạp không gian của các thuật toán dòng dữ liệu. Bài báo của AMS được giải Godel năm 2005.

Ý tưởng chính của AMS là chúng ta thiết kế một cấu trúc dữ liệu ước tính một biến ngẫu nhiên ${X}$ sao cho ${E[X] = F_k}$ và phương sai ${\sigma^2 = \text{Var}[X]}$ cũng nho nhỏ thôi. Như đã thảo luận trong bài trước, để ước tính ${F_k}$ với sai số ${\epsilon}$ và độ tin cậy ${\delta}$ , nhờ cái mẹo trung vị chúng ta cần khoảng ${O\left( \frac{\sigma^2}{F_k^2 \epsilon^2} \ln(1/\delta) \right)}$ ước lượng độc lập. Tỉ lệ ${\sigma^2/F_k^2}$ sẽ là một hàm sub-linear trên ${m}$ và ${n}$ . Do đó, nếu có cách nào chỉ dùng ít bộ nhớ để lẫy một mẫu ${X}$ là sẽ dẫn đến giải pháp cho bài toán.

Cái khung ý tưởng trên đã được dùng để thiết kế cơ man nào là thuật toán dòng dữ liệu. Với mỗi bài toán cụ thể, ta phải chọn biến ${X}$ một cách thông minh để ${E[X]}$ (gần) bằng giá trị cần tính và phương sai của nó không quá lớn, sau đó dùng mẹo trung vị.

Lấy mẫu biến ngẫu nhiên ${X}$

Chọn ${l \in [m]}$ ngẫu nhiên với xác suất ${1/m}$ (nghĩa là chọn một gói dữ liệu ngẫu nhiên với phân bố đều trong ${m}$ gói dữ liệu).
Lưu vào bộ nhớ biến ${a_l}$ (địa chỉ IP hay bất kỳ cái gì khác, tùy ứng dụng).
Bắt đầu đếm số lần xuất hiện ${Y}$ của ${a_l}$ từ thời điểm ${l}$ cho đến cuối dòng.
Cuối cùng, trả về ${X = m(Y^k - (Y-1)^k)}$ .

Cần giải quyết ba vấn đề:

Không biết trước ${m}$ , làm sao để chọn ${l \in [m]}$ ngẫu nhiên với xác suất ${1/m}$ mà lại dùng rất ít bộ nhớ? Đây là một câu hỏi phỏng vấn kinh điển. Người ta có thể hỏi là làm thế nào để lấy mẫu ${k}$ phần tử trong dòng dữ liệu gồm ${m}$ phần tử mà chỉ quét qua một lần và ${m}$ không biết trước. Không phải chờ đến tốc độ khủng khiếp của Internet thì câu hỏi này mới có lý. Ngày xưa người ta cũng cần lấy mẫu dữ liệu từ các băng từ, chạy chậm nhưng rất dài, chứa nhiều dữ liệu và không biết khi nào thì dừng. Do đó, ta cũng cần lấy mẫu với chỉ một lần quét qua băng. Rờ-tua lại nó rất mất thời gian, do đó các thuật toán cần quét hơn một lần là không hay. Năm 1985, Jeffrey Vitter trả lời câu hỏi này trong một bài báo rất dễ thương. Thuật toán của Vitter thuộc họ thuật toán có tên là lấy mẫu bồn chứa (reservoir sampling).
Chứng minh ${E[X] = F_k}$ .
Chặn trên phương sai của ${X}$ , hy vọng là nó không quá lớn.

Phép lấy mẫu bồn chứa rất đơn giản. Ban đầu ta đặt ${Y = a_1}$ . (Chỉ cần ${\log n}$ bits để chứa biến này.) Khi ${a_2}$ đến thì gán ${Y = a_2}$ với xác suất ${1/2}$ (nghĩa là với xác suất ${1/2}$ thì ${Y}$ vẫn bằng ${a_1}$ ). Tổng quát, khi ${a_p}$ đến thì xác suất mà ${Y}$ đang bằng ${a_i, i<p}$ là ${1/(p-1)}$ . Ta chỉ việc thay ${Y = a_p}$ với xác suất ${1/p}$ , và giữ ${Y}$ như cũ với xác suất ${1-1/p}$ . Do ${(1-1/p) \cdot 1/(p-1) = 1/p}$ , ${Y}$ vẫn phân bố đều trên ${a_1,\cdots, a_p}$ .

Xác minh rằng ${E[X] = F_k = \sum_{j=1}^n f_j^k}$ không khó khăn gì. Để làm bài tập.

Cuối cùng, chúng ta chặn ${\sigma^2 = \text{Var}[X] = E[X^2] - (E[X])^2}$ . Trước hết,

$\displaystyle E[X^2] = \sum_{j=1}^n \sum_{i=1}^{f_j} \frac{m^2(i^k - (i-1)^k)^2}{m}.$

$\displaystyle (i^k - (i-1)^k)^2 \leq ki^{k-1}(i^k-(i-1)^k) \leq ki^{2k-1} - k(i-1)^{2k-1},$

ta có

$\displaystyle \sigma^2 \leq E[X^2] \leq \sum_{j=1}^n mkf_j^{2k-1} = mkF_{2k-1} = kF_1F_{2k-1}.$

Đặt ${F = \max_jf_j}$ . Một chút ảo thuật với bất đẳng thức (nhớ rằng chúng ta cần chặn trên ${\sigma^2}$ bằng ${F_k^2}$ nhân với một hệ số càng nhỏ càng tốt và hệ số đó phải là sub-linear trên các tham số ${m}$ và ${n}$ ):

$\displaystyle F_{2k-1} \leq F^{k-1}F_k \leq F_k^{(k-1)/k}F_k = F_k^{2-1/k}.$

Bất đẳng thức Holder cho ta ${F_1 \leq n^{1-1/k}F_k^{1/k}}$ . Vì thế

$\displaystyle \sigma^2 \leq kn^{1-1/k}F_k^2.$

Như vậy là tổng số ước lượng ${X}$ chúng ta cần lấy mẫu là ${O\left( \frac{kn^{1-1/k} \ln(1/\delta)}{\epsilon^2} \right)}$ . Mỗi mẫu chỉ cần bộ nhớ kích thước ${O(\log m + \log n)}$ . Một kết quả mạnh mà ý tưởng lại rất đơn giản và rõ ràng!

GT 10: Thuật toán AMS ước lượng mô-măng tần số

Post a Comment Cancel reply

Thông điệp ngắn

Phản hồi mới

Bài mới

Thư khố

Chuyên Mục

Báo chí

Bảo mật

Blog Việt

Chưa phân loại

Giáo dục

Kỹ thuật

Khoa học khác

Kinh tế, luật pháp, xã hội

Lý thuyết & thuật toán

Mạng

Não học

Toán học

Vật Lý