Ứng dụng học máy trong hệ khuyến nghị tự động

15 min readJul 25, 2018

Giới thiệu

Chúng ta đang sống trong thời đại bùng nổ thông tin, đặc biệt là các nguồn thông tin trực tuyến từ Internet. Hàng ngày có hàng ngàn bản tin được viết và đưa lên Internet, hàng trăm bài hát được thu âm, hàng trăm đầu sách được xuất bản. Làm thế nào chúng ta có thể tìm được đúng nội dung mình quan tâm? Điểm đến đầu tiên của hầu hết mọi người có lẽ là Google. Nhưng Google chỉ thực sự hữu ích khi ta biết chính xác mình cần cái gì, hay nói cách khác, khi ta biết rõ “từ khóa” cần thiết. Nhưng thử nghĩ xem, khi chúng ta cần tìm một bản nhạc “hay”, có lẽ ta sẽ mất rất nhiều thời gian với Google, bởi khái niệm “hay” ở đây rất không rõ ràng, và có thể rất khác nhau đối với mỗi người. Trong trường hợp đó, ta có thể lên Facebook để tham khảo bạn bè. Nhưng việc đó có thể cũng không hữu ích và tốn thời gian khi ta có ít bạn bè hoặc sự quan tâm, hoặc sở thích của bạn bè cũng không giống mình.

Những nhu cầu như vậy xảy ra rất thường xuyên với đa số mọi người, và một hệ thống khuyến nghị tự động, giúp gợi ý những nội dung phù hợp nhất với mỗi người là nhu cầu hết sức phổ biến và cần thiết. Bài biết này sẽ mô tả ứng dụng của các hệ khuyến nghị và tổng quan một số kỹ thuật, mô hình trong học máy có thể áp dụng hiệu quả trong việc xây dựng các hệ thống khuyến nghị tự động. Việc cài đặt, triển khai một hệ thống khuyến nghị trên một môi trường, ngôn ngữ lập trình cụ thể nằm ngoài phạm vị của bài viết.

Các hệ khuyến nghị

Hệ thống khuyến nghị (Recommendation system) là một loại hình cụ thể của kỹ thuật lọc thông tin (như tin tức, phim ảnh, âm nhạc, trang web…) mà người dùng quan tâm. Nó rất quan trọng cho sự thành công của thương mại điện tử và ngành công nghệ thông tin hiện nay, và dần dần trở nên phổ cập trong các ứng dụng khác nhau (ví dụ như Netflix, Google tin tức, Amazon). Các thống kê đã chỉ ra rằng, hai phần ba (⅔) số phim trên hệ thống Netflix được xem là nhờ kết quả gợi ý của hệ khuyến nghị, 38% lượng nhấp chuột trên hệ thống tin tức Google News và 35% sản phẩm bán được trên hệ thống thương mại điện tử Amazon đều nhờ vào hệ khuyến nghị tự động.

Hệ tư vấn thường được xây dựng tự động dựa trên hồ sơ (profile) của người dùng. Hệ thống so sánh hồ sơ của người dùng với một số đặc điểm tài liệu tham khảo, và tìm cách để dự đoán “đánh giá” mà người dùng sẽ cung cấp cho một nội dung mà người dùng đó vẫn chưa đánh giá.

Thông tin về người sử dụng được dùng cho việc khuyến nghị tự động có thể chia thành hai loại: thông in ẩn và thông tin hiện. Các thông tin ẩn bao gồm các thông tin như thời gian người mua xem sản phẩm, quá trình người dùng duyệt qua các sản phẩm trước khi chọn sản phẩm cuối để xem, nguồn mà người dùng truy cập đến trang hiện tại… Các nội dung này rất dễ thu thập, nhưng thường có độ nhiễu cao và không có tương tác trực tiếp với người dùng (hệ thống tự động ghi lại lịch sử). Các thông tin hiện là các kết quả nhận được khi người dùng trực tiếp đưa ra đánh giá về sản phẩm như thích/không thích, chấm điểm, bình luận… Các thông tin này thường khó thu thập hơn rất nhiều so với các thông tin ẩn, nhưng độ chính xác cao hơn và rất hữu ích cho việc khuyến nghị.

Kết quả của một hệ tư vấn là i) dự đoán “đánh giá” của người dùng cho một sản phẩm nhất định (ví dụ, khả năng 80% người dùng sẽ thích sản phẩm này) và ii) danh sách những sản phẩm người dùng có thể sẽ thích.

Các hệ tư vần thường phải xử lý một khối lượng lớn thông tin phức tạp và để đạt được hiệu quả tốt thường cần một số kỹ thuật học máy nâng cao để thực hiện. Bài viết này mô tả một số kỹ thuật như vậy.

Ứng dụng học máy trong hệ khuyến nghị thông minh

Bài toán khuyến nghị tự động có thể được phát biểu một cách hình thức như sau:

Cho U là tập tất cả người dùng; P là tập tất cả các sản phẩm (sách, bài hát, phim…) có thể khuyến nghị. Hàm r(u,p) là những đánh giá mức độ phù hợp (xếp hạng) của sản phẩm p với người dùng u, r: U×P → R. Với mỗi người dùng u ∈ U cần tìm sản phẩm p’ ∈ P sao cho hàm r(u,p’) đạt giá trị lớn nhất:

Các kỹ thuật khuyến nghị tự động có thể được chia làm hai loại: i) Lọc dựa trên nội dung (Content-based Filtering) và ii) Lọc cộng tác (Collaborative Filtering). Kỹ thuật lọc dựa trên nội dung khai thác các khía cạnh nội dung thông tin sản phẩm người dùng đã từng sử dụng hay truy nhập trong quá khứ để khuyến nghị. Kỹ thuật lọc cộng tác lựa chọn dựa trên ý kiến hay lời khuyên của những người dùng khác về các sản phẩm, sử dụng các thuật toán nhằm tận dụng các gợi ý được cung cấp bởi một cộng đồng người dùng tương tự để cung cấp cho người dùng hiện tại (người đang tìm kiếm các khuyến nghị).

Kỹ thuật lọc dựa trên nội dung

Với kỹ thuật khuyến nghị dựa trên nội dung, mức độ phù hợp r(u,p) của sản phẩm phẩm p với người dùng u được đánh giá dựa trên mức độ phù hợp r(u,pj), trong đó pj ∈ P và tương tự như p. Ví dụ, để gợi ý một bộ phim cho người dùng u, hệ thống tư vấn sẽ tìm các đặc điểm của những bộ phim từng được u đánh giá cao (như diễn viên, đạo diễn, thể loại…); sau đó chỉ những bộ phim tương đồng với sở thích của u mới được giới thiệu.

Kỹ thuật lọc dựa trên nội dung thông thường sử dụng các mô hình: sử dụng tập hồ sơ sản phẩm và tập hồ sơ người dùng để xây dựng nên mô hình huấn luyện. Mô hình dự đoán sau đó sẽ sử dụng kết quả của mô hình huấn luyện để sinh ra tư vấn cho người dùng. Trong cách tiếp cận này, lọc nội dung có thể sử dụng các kỹ thuật học máy như mạng Bayes (Bayes network), phân cụm (clustering), cây quyết định (decision tree), mạng nơ-ron nhân tạo (Neural network) để dự đoán.

Các kỹ thuật này hoạt động rất tốt với các sản phẩm giàu nội dung như các sản phẩm trong lĩnh vực công nghệ, truyền thông, y tế… và áp dụng được cho cả các sản phẩm mới (chưa có lịch sử tương tác) nên phù hợp khi danh sách sản phẩm được cập nhật liên tục.

Các bước chính để thực hiện việc lọc dựa trên nội dung bao gồm:

Biểu diễn sản phẩm dưới dạng một vec-tơ thuộc tính
Khuyến nghị các sản phẩm tương tự nhau
Hoặc xây dựng hồ sơ (profile) người dùng theo các thuộc tính sản phẩm và khuyến nghị sản phẩm có thuộc tính phù hợp với hồ sơ người dùng.

Điểm mấu chốt của phương pháp này là việc biểu diễn sản phẩm dưới dạng một vec-tơ các thuộc tính và sử dụng các độ đo tương tự để đánh giá mức độ tương đồng của giá trị các thuộc tính. Các thuộc tính có thể có các dạng dữ liệu khác nhau như số nguyên, số thực, các giá trị rời rạc… nên cần các độ đo tương tự khác nhau. Một số độ đo phổ biến có thể kể đến như khoảng cách Mahalanobis, khoảng cách Hamming, khoảng cách Levenshtein, khoảng cách Euclidean, độ tương tự Cosine, chỉ số tương tự Jaccard… Phần tiếp theo sẽ mô tả chi tiết hơn vể một độ đo phổ biến trong các kỹ thuật khuyến nghị — khoảng cách Mahalanobis.

Khoảng cách Mahalanobis. Khoảng cách Mahalabobis là độ đo khoảng cách từ một điểm x đến một phân bố S, được đề xuất bởi P. C. Mahalabobis vào năm 1936. Khoảng cách Mahalanobis từ một quan sát

đến một tập hợp các quan sát với giá trị trung bình

và ma trận hiệp phương sai (covariance matrix) S được định nghĩa như sau:

Khoảng cách này bằng 0 nếu x ở trung bình của D và lớn dần khi x di chuyển ra xa trung bình. Đây là khoảng cách không có đơn vị, và không bị thay đổi khi dữ liệu được tăng theo hệ số (scale invariant).

Hình bên dưới mô tả ba nhóm dữ liệu được dánh dấu bởi ba đường e-líp. Tất cả các điểm nằm trên mỗi đường e-líp này có khoảng cách Mahalabobis đến trung bình của mỗi nhóm bằng nhau.

Khoảng cách Mahalanobis cũng có thể dùng để độ độ lệch giữa hai vec-tơ x và y của cùng một phân bố với ma trận hiệp phương sai S như sau:

Kỹ thuật lọc cộng tác

Kỹ thuật lọc cộng tác (Collaborative Filtering) dựa trên nguyên tắc hoạt động là các khuyến nghị dựa trên ảnh hưởng của nhiều người khác nhau với giả thuyết căn bản: người dùng tương tự nhau sẽ quan tâm đến sản phẩm tương tự nhau.

Khác so với kỹ thuật lọc dựa trên nội dụng, hệ thống cộng tác dự đoán mức độ phù hợp r(u,p) của một sản phẩm p với người dùng u dựa trên mức độ phù hợp r(ui, p) giữa người dùng ui và p, trong đó ui là người có cùng sở thích với u. Ví dụ, để gợi ý một bộ phim cho người dùng u, đầu tiên hệ thống cộng tác tìm những người dùng khác có cùng sở thích phim ảnh với u (cũng xem và đánh giá tương tự nhau cho một số bộ phim khác). Sau đó, những bộ phim được họ đánh giá cao sẽ được dùng để tư vấn cho u.

Kỹ thuật này chỉ dựa vào lịch sử giao dịch để tìm các quy luật tương tác giữa người dùng với sản phẩm mà không cần biết thuộc tính của sản phẩm và có khả năng khai thác thông tin ngoài phạm vi của các thuộc tính sản phẩm. Vì vậy, lọc cộng tác rất hiệu quả với các hệ thống có nhiều tương tác giữa người dùng và sản phẩm (nhiều người dùng, nhiều giao dịch, nhiều phản hồi) cũng như các hệ thống với những sản phẩm có ít thuộc tính.

Các kỹ thuật lọc cộng tác lại được chia thành hai loại: i) lọc cộng tác dựa trên người dùng (user-based filtering); và ii) lọc cộng tác dựa trên sản phẩm (item-based filtering).

Lọc cộng tác dựa trên người dùng

Lọc cộng tác dựa trên người dùng: là phương pháp dự đoán đánh giá của người dùng u cho một sản phẩm p’ dựa trên các người dùng “láng giềng” với người dùng u. “Láng giềng” với người dùng u là người dùng khác mà có quan điểm về các sản phẩm tương tự như người dùng u.

Phương pháp này được thực hiện qua các bước sau:

Biểu diễn mỗi người dùng bằng một vector các sản phẩm đã tương tác, có thể có trọng số
Tính độ tương tự giữa các vector đại diện cho người dùng.
Đối với người dùng A, ước tính độ phù hợp của sản phẩm dựa vào lịch sử của nhóm người dùng tương tự A.
Có thể chọn k người dùng gần giống A nhất, hoặc chọn tất cả người dùng nhưng thêm trọng số để ưu tiên những người giống A hơn

Tương tự với trường hợp lọc theo nội dung ở trên, trong các phương pháp này, việc tính toán độ phù hợp đóng vai trò chủ chốt cho chất lượng của bộ lọc. Độ phù hợp trong trường hợp này có thể được tính như sau:

Trong đó:

prx,k: độ phù hợp ước tính của sản phẩm k với người dùng x
mx: độ phù hợp trung bình của các sản phẩm với người dùng x
ry,k: độ phù hợp của sản phẩm k với người dùng y
my: độ phù hợp trung bình của các sản phẩm với người dùng y

Trong trường hợp giới hạn k người dùng gần giống nhất:

sim(ux, uy) = 1
Nx: tập hợp k người dùng gần giống x nhất

Trong trường hợp không giới hạn người dùng tương tự:

sim(ux, uy): độ tương tự giữa các vector người dùng x và y, hoặc một hàm đồng biến dựa trên độ tương tự
Nx: tập hợp người dùng có ít nhất một sản phẩm tương tác trùng với x

Với m người dùng và n sản phẩm, độ phức tạp tính toán của phương pháp này như sau:

Trong trường hợp xấu nhất, độ phức tạp của thuật toán là O(mn)
Trên thực tế, phần lớn người dùng chỉ tương tác với một số nhỏ các sản phẩm, nên độ phức tạp tính toán cho nhóm này là O(m)
Với số ít người dùng tương tác với nhiều sản phẩm, độc phức tạp tính toán sẽ là O(n)
Như vậy, trên thực tế, độ phức tạp tính toán trung bình sẽ là O(m+n).

Ngoài ra, trong các hệ thống lớn, một số kỹ thuật phụ trợ có thể được áp dụng để tăng hiệu suất của hệ thống, như: phân nhóm bằng cách giảm chiều (dimensionality reduction) để thu nhỏ không gian trạng thái; phân cụm (clustering) để chia tập người dùng thành nhiều cụm nhỏ, khi cần khuyến nghị cho người dùng nào thì chỉ cần xét cụm chứa người dùng đó; sử dụng các mô hình phân lớp (classification) và hồi quy (regression) để tính độ phù hợp thay cho công thức tính trung bình.

Lọc cộng tác dựa trên sản phẩm

Lọc cộng tác dựa trên sản phẩm: là phương pháp dự đoán đánh giá của người dùng u cho một sản phẩm p’ dựa trên xếp hạng mặt hàng “láng giềng” p cũng được đánh giá bởi cùng một người dùng u. Một “láng giềng” của sản phẩm là những sản phẩm khác mà có xu hướng được xếp hạng tương tự của người dùng u.

Phương pháp này được thực hiện qua các bước sau:

Biểu diễn mỗi sản phẩm bằng một vector các người dùng đã tương tác.
Tính độ tương tự giữa các sản phẩm.
Đối với người dùng A, tìm các sản phẩm tương tự với sản phẩm A đã tương tác.
Khuyến nghị sản phẩm cho A từ các sản phẩm nói trên, bằng các tiêu chí như trọng số cao, nhiều người tương tác…

Thuật toán tính độ tương tự giữa các sản phẩm được mô tả như sau:

Với mỗi sản phẩm A:

Với mỗi người dùng X đã tương tác với A: Với mỗi sản phẩm B khác A mà X đã tương tác: Lưu dữ kiện là một người dùng đã tương tác với cả A và B.
Với mỗi sản phẩm B khác A đã có cùng người dùng tương tác: Tính độ tương tự giữa A và B dựa trên các dữ kiện đã lưu.

Trong phương pháp này, khối lượng tính toán lớn nhất nằm ở phần tính độ tương tự giữa các sản phẩm. Giả sử có m người dùng và n sản phẩm:

Độ phức tạp tính toán trong trường hợp xấu nhất là O(n²m)
Trên thực tế, độ phức tạp thường là O(mn) vì dữ liệu thưa, đại đa số các cặp sản phẩm không có cùng người dùng tương tác.
Độ phức tạp tuy lớn, nhưng bước này chỉ cần tính một lần cho tất cả các lượt người dùng.

Một số kỹ thuật phụ trợ có thể được áp dụng nhằm tăng hiệu suất của hệ thống như: ước tính trước độ tương tự giữa các sản phẩm và cập nhật định kỳ (không cần làm liên tục); bổ sung thông tin về thuộc tính sản phẩm khi tính độ tương tự để giải quyết trường hợp ít tương tác; áp dụng các kỹ thuật phân nhóm, phân lớp, hồi quy… như với trường hợp lọc cộng tác dựa trên người dùng ở trên.

Các kỹ thuật lai

Kỹ thuật lai (hybrid) là phương pháp kết hợp của cả hai kỹ thuật trên. Một số ứng dụng kết hợp cả hai kỹ thuật lọc cho hệ thống khuyến nghị dựa theo nội dung và lọc cộng tác. Mỗi kỹ thuật đều có những ưu điểm và nhược điểm riêng, do đó khi kết hợp có thể khắc phục những hạn chế của từng kỹ thuật. Nó cải thiện hiệu suất dự đoán, và quan trọng hơn, từ đó khắc phục được những vấn đề tồn tại trong lọc thông tin như dư liệu thưa thớt và mất thông tin. Tuy nhiên, sự kết hợp của hai kỹ thuật để thực hiện sẽ gia tăng độ phức tạp và chi phí phát triển. Thông thường hầu hết các hệ thống khuyến nghị thương mại là các hệ thống lai, ví dụ như hệ thống khuyến nghị tin tức của Google.

Thông thường có bốn cách kết hợp hai kỹ thuật trên để tạo thành một hệ thống lai như sau:

Cài đặt hai phương pháp riêng rẽ rồi kết hợp dự đoán của chúng với nhau: Có hai kịch bản cho trường hợp này là:
- Cách 1: Kết hợp kết quả của cả hai phương pháp thành một kết quả chung duy nhất.
- Cách 2: Tại mỗi thời điểm chọn một phương pháp cho kết quả tốt hơn
Tích hợp các đặc trưng của phương pháp dựa trên nội dung vào hệ thống cộng tác.
Tích hợp các đặc trưng của phương pháp cộng tác vào hệ thống dựa trên nội dung.
Xây dựng mô hình hợp nhất, bao gồm các đặc trưng của cả hai phương pháp.

Kết luận

Hệ khuyến nghị tự động là một nhu cầu hết sức phổ biến và cần thiết cho hầu hết các hệ thống kinh doanh trực tuyến hiện nay. Đây là một hệ thống phức tạp và đòi hỏi các kỹ thuật xử lý thông minh dựa trên trí tuệ nhân tạo và các phương pháp học máy. Bài viết này là bài mở đầu nhằm đặt vấn đề cho bài toán hệ khuyến nghị tự động cũng như đưa ra một số khái niệm, kỹ thuật cụ thể. Trong bài viết, tác giả đã đưa ra mô tả về hệ khuyến nghị tự động, các loại hệ khuyến nghị, cũng như khảo sát một số kỹ thuật học máy có thể áp dụng hiệu quả cho các hệ khuyến nghị tự động. Trong các bài viết tiếp theo, tác giả dự kiến sẽ đi sâu vào việc cài đặt và triển khai một hệ khuyến nghị tự động cho một hệ thống trực tuyến cụ thể, cũng như việc mở rộng hệ thống khuyến nghị cỡ lớn trên nền tảng Dữ liệu lớn (Big Data).

Tham khảo

[1] Francesco Ricci and Lior Rokach and Bracha Shapira,Introduction to Recommender Systems Handbook, Recommender Systems Handbook, Springer, 2011,

[2] Xiaoyuan Su, Taghi M. Khoshgoftaar, A survey of collaborative filtering techniques, Advances in Artificial Intelligence archive, 2009

[3] Prem Melville and Vikas Sindhwani,Recommender Systems, Encyclopedia of Machine Learning, 2010.

[4] Elahi, Mehdi; Ricci, Francesco; Rubens, Neil. A survey of active learning in collaborative filtering recommender systems. Computer Science Review, 2016, Elsevier.

[5]. Zheng Wen, Recommendation System Based on Collaborative Filtering, 2008

[6]. Michael D.Ekstrand, John T. Riedl, Joseph A. Konstan, Collaborative Filtering Recommender Systems, University of Minnesota, 2011

[7]. T. Hofmann, Latent Semantic Models for Collaborative Filtering, ACM Trans. Inf.Syst., 22(1):89–115, 2004.

[8]. Yehuda Koren, Robert Bell and Chris Volinsky, Matrix factorization techniques for recommender system, IEEE Computer, 2009

[9]. Badrul Sarwar, George Karypis, Joseph Konstan, and John Riedl, Item-Based Collaborative Filtering Recommendation Algorithms, University of Minnesota, Minneapolis, MN 55455

[10]. Léon Bottou, Stochastic Gradient Descent Tricks, Microsoft Research, Redmond, WA,2012

[11]. Shameem Ahamed Puthiya Parambath, Matrix Factorization Methods forRecommender Systems, Master’s Thesis in Computing Science, 2013.

[12]. Ron zacharski, A programmer’s Guide to Data Mining, The Ancient Art of the Numerati, 2012

[13]. Michael D.Ekstrand, John T. Riedl, Joseph A. Konstan, Collaborative Filtering Recommender Systems, University of Minnesota, 2011

[14]. Francesco Ricci, Lior Rokach, Bracha Shapira, Paul B. Kantor, Recommender Systems Handbook, Springer, 2011.

[15]. Jonathan L. Herlcocker, Joseph A. Konstan, Loren G. Terveen, and John T. Riedl, Evaluating Collaborative Filtering Recommender Systems, Oregon State University and University of Minnesota, 2004

[16] Deza, Elena; Deza, Michel Marie (2009). Encyclopedia of Distances. Springer.