Bài này chúng ta sẽ nghiên cứu kĩ thuật thiết kế giải thuật cho một hệ thống gợi ý với dữ liệu rất lớn (lên tới 100 triệu user và 100 triệu items). Trọng tâm của bài này là sử dụng phép băm. Gọi $\mathcal{U} = \{U_1,U_2,\ldots, U_N\}$ và $\mathcal{I} = \{I_1,I_2,\ldots, I_M\}$ lần lượt là tập các user, item trong hệ thống. Một chú ý quan trọng của bài này đó là dữ liệu của chúng ta là rất lớn, do đó tất cả các giải thuật với độ phức tạp $O(NM)$ là đều không thể sử dụng được.

Tổng quan về hệ thống gợi ý

Giải thuật gợi ý thường được chia thành 3 dạng chính:

1. Gợi ý dựa trên nội dung (Content Based Recommendation): Giải thuật kiểu này dựa trên các sở thích của người dùng để gợi ý. Ví dụ một người thích xem phim Mỹ, Hành Động, và diễn viên yếu thích là Jason Statham và Vin Diesel thì có lẽ nên gợi ý phim Fast And Furious 7 (nếu người này chưa xem phim đó) vì phim này có chứa nhiều tính chất liên quan đến sở thích của người đó.
2. Gợi ý sử dụng lọc cộng tác (Collaborative Filtering Recommendation) :Giải thuật lọc cộng tác thì thường dựa vào lịch sử thăm của người dùng, mà cụ thể là Visit Log, để gợi ý. Có thể hiểu Visit Log là biểu diễn thưa của một ma trận User/Item, kí hiệu là $M$, trong đó mỗi hàng của mà trận biểu diễn một user và mỗi cột biểu diễn một item. $M[i, j] = 1$ nếu User $i$ có thăm Item $j$ trong quá khứ và $M[i,j] = 0$ nếu ngược lại. Ma trận này là tất cả những gì chúng ta cần cho các giải thuật lọc cộng tác.
3. Giải thuật lai ghép (Hybrid Algorithm): Là những giải thuật sử dụng cả nội dung và Visit Log. Loại giải thuật này cố gắng tận dụng mọi thông tin sẵn có để thực hiện gợi ý. Mô hình cho giải thuật kiểu này thường khá phức tạp.

Trong bài này, chúng ta chỉ tập trung vào giải thuật lọc cộng tác. Giải thuật lọc cộng tác lại chia thành 2 nhóm chính:

1. Gợi ý dựa trên user (User-Based Recommendation): Gợi ý được thực hiện dựa trên các user tương tự. Cụ thể, với một user $A$ cho trước, tìm tập các user giống với $A$ nhất, i.e các users thăm các item mà $A$ thăm, sau đó gợi ý cho $A$ những item được thăm bởi tập user tương tự đó (có thể xếp hạng các item theo thứ tự phù hợp).
2. Gợi ý dựa trên item (Item-Based Recommendation): Gợi ý được thực hiện trên các item tương tự. Cụ thể, từ tập các item mà user $A$ đã thăm trong quá khứ, gợi ý cho $A$ các item giống với tập các item đó nhất.

Mặc dù hai phương pháp này khác nhau về mặt khái niệm, các thức thực thi thì lại tương tự nhau. Do đó, trong bài này, chúng ta chỉ tập trung vào một phương pháp, mà cụ thể là phương pháp dựa trên user.

Ý tưởng của thuật toán

Độ đo tương tự

Trước hết chúng ta sẽ nói đến độ đo tương tự. Thông thường với dữ liệu có số chiều cao mà thưa như visit log, người ta sử dụng 2 độ đo chính là độ đo Cosine và độ đo Jaccard. Tại sao các độ đo khác không phù hợp thì chúng ta không bàn thêm ở đây (xem thêm tại Wikipedia).

Với độ đo Cosine, chúng ta coi mỗi user như một vector với mỗi chiều tương ứng với một item. Sự tương tự giữa 2 user được tính là Cosin giữa 2 vector tương ứng. Do độ đo Cosine sử dụng căn bậc 2, một thao tác khá tốn kém, nên ta sẽ không dùng. Như vậy, lựa chọn còn lại là độ đo Jaccard.

Độ đo Jaccard giữa 2 tập hợp $A$ và $B$ được định nghĩa như sau:

$J(A,B) = \frac{|A\cap B|}{|A \cup B|} \qquad (1)$

Ví dụ $A = \{x,y,z\}$, $B = \{x,y,c\}$ thì độ đo Jaccard của $A$ và $B$ là:

$J(A,B) = \frac{|\{x,y\}|}{|\{x,y,z,c\}|} = \frac{2}{4} = \frac{1}{2}$

Độ đo Jaccard áp dụng cho hai user cho trước chính là độ tương tự giữa 2 tập item tương ứng mà 2 user đó thăm. Ví dụ $U_1$ đã thăm các item ${x,y,z}$ và $U_2$ đã thăm các item ${x,y,c}$ thì độ tương tự giữa $U_1$ và $U_2$ là $1/2$.

Ý tưởng của giải thuật

Sau khi ta đã thống nhất một độ đo tương tự, ta có thể thực hiện gợi ý đơn giản như sau:

Phân tích: Hai vòng lặp ngoài cùng sử dụng $O(N^2)$ bước lặp. Tính $J(A,B)$ mất thời gian $O(M)$, trong trường hợp tồi nhất. Trong thực tế, số các item được xem bởi một user thường nhỏ hơn tổng số items rất nhiều, và có thể coi là $O(1)$. Như vậy, trong trường hợp lạc quan nhất thì thời gian của thuật toán vẫn là $O(N^2)$.

Kể cả trong kịch bản tốt nhất, thời gian $O(N^2)$ vẫn là quá lớn (trong thực tế số users có thể lên tới $100$ triệu thì giải thuật này không khả thi).

Trong thuật toán trên, với mỗi user $A$, ta chỉ quan tâm đến các user $B$ mà $J(A,B)\geq s$ (giá trị thực tến của $s$ thường là $0.5$). Trong thực tế, các user có $J(A,B) \geq s$ thường không quá nhiều (khoảng vài ngàn). Tuy nhiên, thuật toán trên phải duyệt qua tất cả các user để lọc ra những user có độ tương tự cao với $A$. Một ý tưởng cải tiến khá tự nhiên đó là: sử dụng một hàm băm $h(.)$ thỏa mãn:

Condition 1: Nếu $J(A,B) \geq s$ thì $A,B$ sẽ được băm vào cùng một cụm (với xác suất cao), và ngược lại.

Ở đây, ta nói với xác suất cao là vì các hàm băm tốt, về mặt lý thuyết, đều phải là các hàm băm ngẫu nhiên. Hàm băm $h(.)$ với tính chất như trên được gọi là hàm băm LSH (Locality Senstive Hashing). Giả sử hàm băm $h(.)$ như thế tồn tại, giải thuật SlowRecommendation có thể được viết lại như sau:

Chúng ta có thể dễ dàng nhận ra trong kịch bản tốt nhất, thời gian của thuật toán trên là $O(N)$

Chi tiết thực thi thuật toán

Trong phần này chúng ta sẽ thảo luận cách thức thực thi thuật toán FastRecommendation. Trước hết ta tạm quên đi Condition 1, thay vào đó, ta xem xét gợi ý với hàm băm đơn giản sau:

 
Hàm MinHash($A, S$) về cơ bản trả về chỉ nhỏ nhất trong hoán vị $S$ trong số các item mà $A$ đã xem trong quá khứ. Ví dụ ta có 3 items: $\{a,b,c\}$ và user $A$ thăm $\{a,c\}$. Giả sử hoán vị chúng ta sinh ra ngẫu nhiên là $\{3,1,2\}$. Có nghĩa là $a$ có chỉ số 3, $b$ có chỉ số 1, và $c$ có chỉ số 2. MinHash($A, S$) sẽ trả về $2$ vì 2 là chỉ số nhỏ nhất trong tập chỉ số $\{3,2\}$.

Câu hỏi mà ta sẽ tìm hiểu với hàm băm này đó là xác suất hai user $A$ và $B$ có cũng mã băm (băm vào cùng một cụm) là bao nhiêu?

 
Chứng minh: Dễ thấy, trong tập $M$ item $\mathcal{I}$, xác suất để một item bất kì có chỉ số nhỏ nhất trong hoán vị ngẫu nhiên $S$ là $1/M$. Mở rộng ra, xác suất để một item bất kì trong một tập con các item $\mathcal{I}'$ của $\mathcal{I}$ có chỉ số nhỏ nhất trong hoán vị ngẫu nhiên $S$ là $\frac{1}{|\mathcal{I}'|}$.

Do đó, xác xuất để $h(A) = h(B)$ chính là xác suất mà một phần tử (bất kì) trong tập hợp $A\cup B$ trở thành phần tử có chỉ số nhỏ nhất trong tập hợp $A\cup B$. Xác suất này chính là $J(A,B)$.

Từ phân tích ở trên, ta thấy, hàm băm $h(.)$ mà ta chọn thông qua hoán vị ngẫu nhiên $S$ có một tính chất khá thú vị đó là xác suất hai user được băm vào một cụm bằng độ tương tự Jaccard giữa hai user đó. Tuy nhiên, ta chưa thể áp dụng ngay ý tưởng này vào gợi ý được vì còn hai lí do:

1. Hàm $h(.)$ mô tả ở trên chưa thỏa mãn Condition 1. Ví dụ với $s = 0.5$ thì xác suất 2 user được băm vào một cụm là $0.5$, đây không phải là một xác suất cao.
2. Mô tả hàm $h(.)$ tốn rất nhiều bộ nhớ, vì để mô tả một hoán vị ngẫu nhiên, ta mất ít nhất $\log(n!) = \Omega(n\log n)$ bít. Số lượng bít này là quá nhiều với dữ liệu lớn. Thông thường, ví dụ như hàm băm sử dụng trong thiết kế bảng băm, ta chỉ sử dụng $O(\log n)$ bít để mô tả.

Ta sẽ giải quyết vấn đề đầu tiên trước.

Tăng cường xác suất

Phần này ta sẽ nghiên cứu phương pháp đơn giản để tăng cường xác suất sao cho hàm băm ở trên thỏa mãn Condition 1. Thay vì chỉ sử dụng một hàm băm, ta sẽ sử dụng $K$ hàm băm $h_1(.), ...,h_K(.)$ MinHash như trên (bằng cách chọn $K$ hoán vị ngẫu nhiên khác nhau). Chia $K$ hàm băm này thành $p$ nhóm, mỗi nhóm $r$ hàm băm. Với mỗi user, ví dụ $A$, ta sẽ băm $A$ vào $p$ cụm, trong đó mỗi cụm sẽ tương ứng với $r$ hàm băm.

Ví dụ với $K = 30, p = 10, r= 3$, ta chia hàm băm thành 10 nhóm, mỗi nhóm 3 hàm băm. 10 Nhóm đó là $[h_1,h_2,h_3]$, $[h_4,h_5,h_6]$,$\ldots$,$[h_{28},h_{29},h_{30}]$. Như vậy, mỗi user $A$ sẽ được phân vào 10 cụm, đó là:

$\begin{array}{lcl} C_1 & = & [h_1(A),h_2(A),h_3(A)] \\ C_2 & = & [h_4(A),h_5(A),h_6(A)] \\ \ldots & = & \ldots \\ C_{10} & = & [h_{28}(A),h_{29}(A),h_{30}(A)] \end{array}$

 
Chứng minh:

• Xác suất để hai user được băm vào một cụm đầu tiên là:

  $P_1 = Pr[h_1(A) = h_1(B)]\cdot Pr[h_2(A) = h_2(B)]\cdots Pr[h_r(A) = h_r(B)] = x^r $

  Đây cũng chính là xác suất để hai user được băm vào một cụm cho trước bất kì.

• Xác suất để hai user KHÔNG được băm vào cùng MỘT cụm cho trước là: $P_2 = 1 - P_1 = 1-x^r$.
• Xác suất để hai user KHÔNG được băm vào cùng BẤT KÌ cụm nào trong $p$ cụm là: $P_3 = P_2^p = (1-x^r)^p$.
• Xác suất để hai user ĐƯỢC băm vào cùng ÍT NHẤT một cụm là: $P_4 = 1 - P_3 = 1 - (1-x^r)^p$.

Ví dụ với $K= 20, r=2, p = 10$, thì ta có $P_4 = 1 - (1-x^2)^10$. Từ đó ta suy ra xác suất để hai user với độ tương tự ít nhất $J(A,B) = 0.5$ được băm vào cùng ít nhất một cụm là $1 - (1-x^2)^{10} \sim 94\%$. Rõ ràng xác suất này cao hơn nhiều so với $J(A,B)$. Hay nói cách khác, ta đã tăng cường được xác suất mà hai users được băm vào cùng một cụm. Trong thực tế, với ngưỡng $s$ cho trước, ta chỉ việc chọn $r,p$ sao cho phù hợp. Vấn đề đầu tiên coi như đã xong. Ta tiếp tục với vấn đề thứ 2: làm sao để thực hiện hàm băm với hoán vĩ ngẫu nhiên?

Thực thi hàm băm với hoán vị ngẫu nhiên

Như đã phân tích ở trên, ta cần $O(n\log n)$ bít để mô tả một hoán vị ngẫu nhiên. Rất may, dựa vào phân tích của Theorem 1, ta thấy chúng ta không nhất thiết phải sử dụng hoán vị ngẫu nhiên để thực hiện hàm băm MinHash. Tính chất mà chúng ta cần đó là một hàm (ngẫu nhiên) có thể ánh xạ tập hợp $X$ vào tập các số nguyên $D$ (ví dụ 64 bít) sao cho xác suất để một phần tử bất kì trong $X$ có giá trị (ảnh) nhỏ nhất trong $D$ là $\frac{1}{|X|}$. Điều này lại gợi cho chúng ta sử dụng hàm băm. Hàm băm thỏa mãn tính chất này người ta gọi là hàm băm Minwise Independent Hashing (MIH) [4]. Mình sẽ không đi sâu thêm ở đây vì lý thuyết của loại hàm băm này khá phức tạp. Các bạn xem thêm tại [4] và cách xấp xỉ hàm băm này trong [5].

Giải thuật đầy đủ

Sau đây là giải mã của giải thuật đầy đủ, kết hợp tất cả các ý tưởng ở trên.

Dễ thấy trong kịch bản tốt nhất, thời gian của thuật toán là $O(NK + M) = O(N+M)$ vì số lượng hàm băm $K$ mà ta chọn trong thực tể chỉ khoảng vài chục đến vài trăm.

Tham khảo
[1] Das, Abhinandan S., Mayur Datar, Ashutosh Garg, and Shyam Rajaram. Google News Personalization: Scalable Online Collaborative Filtering. Proceedings of the 16th International Conference on World Wide Web. ACM, 2007.
[2] Jure Leskovec, Anand Rajaraman, Jeff Ullman. Mining of Massive Datasets, 2nd Edition, Chapter 3.
[3] FNV Hash function: http://isthe.com/chongo/tech/comp/fnv/, accessed 08/01/2012
[4] Broder, Andrei Z., Moses Charikar, Alan M. Frieze, and Michael Mitzenmacher. Min-wise Independent Permutations. In Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, pp. 327-336. ACM, 1998.
[5] Indyk, Piotr. A Small Approximately Min-wise Independent Family of Hash Functions. Journal of Algorithms 38.1 (2001): 84-90.