Machine learning bình dân (phần 3): Tinder hoạt động như thế nào?
Phần 1: https://spiderum.com/bai-dang/Machine-Learning-giai-thich-theo-ngon-ngu-binh-dan-Phan-1-kmx Phần 2: https://spiderum.com/bai-dang/Machine-Learning-giai-thich-theo-ngon-ngu-binh-dan-phan-2-Hoc-giam-sat-kvu...
Trong hai phần trước (được viết cách đây hơn 1 năm :D), mình đã chia sẻ một cách tổng quát nhất về học máy (machine learning, viết tắt là ML), các nhánh chính trong ML, và đi sâu vào học giám sát (supervised learning, viết tắt là SL) – phân nhánh có thể coi là đang phát triển và phổ biến nhất trong ngành. Những nội dung này đều được mình dịch và chú giải thêm từ một bài viết nước ngoài.
Tuy nhiên, nhận thấy phần tự chú giải của bản thân còn dài hơn phần dịch, nên từ phần này trở đi, mình sẽ tự viết chứ không còn là lược dịch và thêm thắt như trước nữa.
Trong phần 3 này, chúng ta sẽ tìm hiểu về một nhánh khác của học máy, ít phổ biến hơn nhưng ko kém phần hay ho thú vị: Học không giám sát (unsupervised learning, viết tắt là UL), với hai bài toán lớn: Cluster analysis (phân cụm) và Recommender system (Hệ thống gợi ý người dùng), qua case study xuyên suốt mang tên: Tinder.
I. Tại sao cần học không giám sát ? (hay một cái mở bài khá là dài dòng)
Các kĩ thuật học giám sát đã cho thấy những ứng dụng tuyệt vời của chúng trong đủ mọi lĩnh vực, từ dự đoán nợ xấu trong tín dụng, dự đoán giá nhà đất trong bất động sản, đến chẩn đoán ung thư phổi trong y tế … Điểm chung của những kĩ thuật này là 3 yêu cầu bắt buộc: dữ liệu để huấn luyện (training data), các đặc trưng (feature) và “nhãn” (label). Để dự đoán nợ xấu, chúng ta cần một tập dữ liệu các khách hàng đã vay ở ngân hàng, với các đặc trưng tiêu biểu như thu nhập, tuổi tác, nghề nghiệp, lịch sử tín dụng…, và gán nhãn xem mỗi khoản vay đó là tốt (khách hàng trả đúng hạn), hay xấu (khách hàng xù nợ). Để dự đoán giá nhà đất, chúng ta cần một tập dữ liệu các ngôi nhà với diện tích, số tầng, vị trí (cách trung tâm bao xa), tuổi đời… , và “nhãn” có thể hiểu là giá bán của ngôi nhà đó. Với bài toán chẩn đoán ung thư phổi, chúng ta cần có một tập dữ liệu các phim X-quang phổi của mỗi bệnh nhân, với nhãn là bệnh nhân đó có bị ung thư phổi hay không; các đặc trưng của bài toán này không trực quan như hai bài toán trước, bạn cứ hình dung một trong những đặc trưng đó có thể là kích thước khối u chẳng hạn.
Sau đó, một mô hình học máy supervised sẽ được huấn luyện, để từ những dữ liệu đã được gán nhãn, học cách phân biệt nợ xấu, dự đoán giá nhà, hay chẩn đoán ung thư.
Tuy nhiên, một vấn đề phát sinh là, không phải lúc nào chúng ta cũng có các dữ liệu đã được gắn nhãn sẵn. Để biết được một khoản vay là tốt hay xấu, ở công ty mình đang làm việc, phải đợi khoảng 6 tháng sau khi đã giải ngân cho khách hàng. Những công việc đặc thù hơn như gán nhãn “ung thư” hay “không phải ung thư” cho các phim chụp X-quang cần đến chuyên môn của các bác sĩ. Và theo mình biết, đến thời điểm hiện tại, những việc này đều được làm thủ công.
Có thể nói, dữ liệu được gán nhãn là một điều xa xỉ.
Và, quan trọng hơn, không phải bài toán nào cũng cần dữ liệu phải được gán nhãn.
Có thể bạn đã biết: với hơn 66 triệu active users hàng tháng [1], một trong những vấn đề quan trọng nhất của Tinder (hay bất kì mạng xã hội nào khác) là giữ chân người dùng càng lâu càng tốt. Để làm được điều đó, Tinder phải gợi ý cho bạn những đối tượng hẹn hò tiềm năng. Nhưng thế nào là “tiềm năng”?
Trong một bài phỏng vấn năm 2016, CEO của Tinder đã tiết lộ về hệ thống tính điểm “Elo” (một thuật ngữ xuất phát từ giới cờ vua để xếp hạng trình độ người chơi). Nhiệm vụ của hệ thống này là đưa ra một điểm số, gọi là điểm Elo, mà theo như CEO này, sẽ phản ánh độ hấp dẫn (desirability) của mỗi người dùng, dựa trên tỉ lệ match của họ [2]. Đại khái là, nếu số match trên tổng số profiles mà bạn quẹt phải càng cao, thì điểm của bạn càng cao. Và nếu bạn match với những profile có điểm cao thì sẽ giúp tăng điểm hơn là những profile có điểm thấp. Sau đó, Tinder sẽ gợi ý những người có cùng mức điểm Elo với nhau thường xuyên hơn.
Tuy nhiên, điều gì đảm bảo 2 người có cùng mức độ hấp dẫn thì sẽ thích nhau? Tại sao không phải là gợi ý dựa trên “gu” của người dùng? Ví dụ, nếu mình hay quẹt phải những cô gái sống ở Hà Nội, yêu mèo và thích đọc sách, liệu có phải Tinder nên gợi ý cho mình những cô gái “tương tự” như vậy không? Dù cho điểm Elo của họ có thể chênh lệch với mình rất nhiều?
Thật vậy, 3 năm sau, Tinder đã đăng tải một bài blog trên chính trang web của họ, giải thích rằng hệ thống chấm điểm Elo đã lỗi thời và không còn được sử dụng nữa. Thay vào đó, thuật toán gợi ý của app sẽ hoạt động dựa trên địa điểm, gu tuổi tác, gu giới tính, sở thích, và cả hành vi quẹt trong quá khứ của bạn, mà không xếp hạng người dùng theo một cách “cạnh tranh” như trước nữa [3].
Giả sử bạn là một kĩ sư phần mềm của Tinder, bạn sẽ thiết kế hệ thống gợi ý profile như thế nào?
Trong thực tế, có 3 hướng đi chính:
- Một là, dựa trên những đặc điểm nhân khẩu học như tuổi tác, khu vực sinh sống, nghề nghiệp, sở thích..., chia người dùng (người quẹt) thành các nhóm tương tự nhau. Ví dụ, nếu bạn là nam, 20-25 tuổi, sống ở Hà Nội, thích đi phượt, có thể bạn cũng sẽ thích những cô gái được quẹt phải bởi những bạn nam cùng độ tuổi, cùng sống ở Hà Nội và cùng thích đi phượt như bạn. Nhiệm vụ của Tinder là làm sao để phân chia hàng triệu người dùng của họ thành những nhóm có cùng đặc điểmvới nhau như vậy? Trong machine learning, những bài toán như vậy được gọi là Cluster analysis – bài toán phân cụm.
- Hai là, gợi ý dựa trên hành vi sử dụng app. Cụ thể là, nếu như những người bạn quẹt phải, cũng được quẹt phải bởi một nhóm các người dùng khác, thì có thể bạn và nhóm người dùng này có cùng gu hẹn hò, và Tinder sẽ gợi ý cho bạn những profile khác mà nhóm người dùng kia cũng đã quẹt phải, và ngược lại. Trong machine learning, những hệ thống như vậy được gọi là “Collaborative filtering” – lọc cộng tác - một nhánh con của recommender system - hệ thống gợi ý người dùng.
- Ngoài ra, một ý tưởng khác có thể bạn đã nghĩ đến, đó là thay vì phân cụm profile của người quẹt, chúng ta phân cụm profile của người được quẹt thành các cụm tương tự nhau. Nếu người dùng X quẹt phải với nhiều profile trong cụm A chẳng hạn, Tinder sẽ gợi ý cho X những profile khác cũng trong cụm A đó. Bài toán này cũng có thể được giải quyết bằng việc phân cụm hợp lí.
II. K-means và bài toán phân cụm người dùng
Thoạt đầu, bài toán phân cụm có vẻ không khác gì bài toán phân loại (classification) của học giám sát. Mục tiêu của hai bài toán đều là phân chia dữ liệu thành các nhóm. Tuy nhiên, với bài toán phân loại, chúng ta biết mình cần phân loại cái gì với cái gì (nợ xấu hay nợ tốt, ung thư hay không ung thư, chó hay mèo), cũng như cần một tập dữ liệu đã được gán nhãn sẵn để huấn luyện mô hình. Với bài toán phân cụm, chúng ta không xác định trước các nhóm, mà để máy tính tự tìm ra cách chia nhóm riêng. Tinder không quan tâm họ cần phân loại người dùng là “hấp dẫn” hay “không hấp dẫn”, “truyền thống” hay “hiện đại”, họ chỉ cần một cách phân chia người dùng thành K nhóm riêng biệt, sao cho những người thuộc cùng một nhóm sẽ mang những đặc điểm giống nhau nhất có thể. Do các nhãn không được xác định trước (thực ra là chả có nhãn nào ở đây cả), nên kiểu bài toán này được gọi là học không giám sát, nghĩa là máy tính tự học mà không cần có sự hướng dẫn (gán nhãn) của con người.
K-means là một trong những thuật toán phổ biến và trực quan nhất để giải quyết bài toán phân cụm. Chúng ta sẽ cùng tìm hiểu cách K-means hoạt động bằng việc thử phân cụm người quẹt!
Giả sử Tinder có những dữ liệu sau về người dùng là nam giới ở Việt Nam:
Bảng dữ liệu người dùng của Tinder (hư cấu). Vị trí được thể hiện bởi kinh độ và vĩ độ.
Chúng ta muốn đưa tất cả những đặc điểm này vào phân cụm người dùng. Tuy nhiên, máy tính chỉ làm việc được với các con số, vậy làm sao để “mã hóa” cột sở thích thành những con số?
Trong machine learning, một kĩ thuật được sinh ra để mã hóa những dữ liệu dạng phân loại (categorical) như thế này, mang tên mã hóaOne-hot (One-hot-encoding).
Giả sử Tinder chỉ cho người dùng lựa chọn trong 3 sở thích: Mèo, karaoke, và đi phượt (trong thực tế có nhiều sở thích hơn vậy). Vậy, với mỗi giá trị của cột Sở thích, chúng ta tạo thêm 1 cột riêng, nhận giá trị 1 hoặc 0 để phản ánh Sở thích đó có xuất hiện ở người dùng X hay không. Vì chỉ có 3 sở thích tất cả, chúng ta sẽ chỉ tạo thêm 3 cột mới là "Mèo", "Karaoke", và "Đi phượt".
Bảng dữ liệu, sau khi được mã hoá sẽ trông như thế này:
Vì Nam thích Mèo và Karaoke nên sẽ nhận giá trị 1 ở cột Mèo và Karaoke. Tương tự, vì Khá chỉ thích Mèo nên các cột Karaoke và Đi phượt của Khá sẽ nhận giá trị 0.
Như mình đã viết ở phần 2, để thuận tiện cho việc tính toán của máy tính, dữ liệu của mỗi người dùng sẽ được đóng gói thành một điểm trong không gian 6 chiều (vì ngoài cột Tên người dùng không phải một "đặc điểm" hữu ích để phân cụm, chúng ta có 6 cột tất cả). Ví dụ, điểm dữ liệu (hay vectơ dữ liệu) của Nam, trong không gian 6 chiều, sẽ là (27, 105.85, 21.03, 1, 1, 0).
Lưu ý: Toạ độ của một điểm trong không gian n chiều cũng chính là toạ độ của vectơ từ gốc toạ độ đến điểm đó. Ví dụ: Toạ độ điểm A trong không gian 3 chiều là (1,2,3), thì toạ độ của vectơ OA, với O là gốc toạ độ, cũng là (1,2,3). Vậy nên đôi khi mình sẽ không gọi là điểm dữ liệu mà gọi là véctơ dữ liệu.
Cách Tinder thu thập dữ liệu về sở thích người dùng
"Độ giống nhau" giữa 2 người dùng bất kì sẽ tỉ lệ nghịch với khoảng cách của 2 điểm dữ liệu tương ứng trong không gian toạ độ.
2. Khoảng cách Euclide
Trong chương trình toán cấp 3, chúng ta đã biết cách tính khoảng cách giữa 2 điểm trong mặt phẳng 2 chiều như sau:
Đây chính là một trường hợp cụ thể của một công thức mang tên khoảng cách Euclide. Một cách tổng quát, khoảng cách Euclide giữa 2 điểm bất kì trong không gian n chiều sẽ là:
Quay trở lại với Tinder, nếu điểm dữ liệu của Nam và Minh là (27, 105.85, 21.03, 1, 1, 0) và (25, 105.92, 21.12, 0, 1, 0), thì khoảng cách Euclide của 2 điểm này trong không gian 6 chiều sẽ là:
Tương tự, chúng ta có thể tính được khoảng cách Euclide giữa 2 người dùng bất kì. Khoảng cách này càng nhỏ thể hiện độ giống nhau càng lớn.
3. Thuật toán K-means
Chúng ta đã có đủ công cụ để hiểu về thuật toán K-means. Giả sử chúng ta muốn chia tất cả người dùng thành K cụm. Hãy cùng xem thuật toán K-means sẽ làm như thế nào:
Bước 1: Chọn K điểm ngẫu nhiên làm tâm điểm (center) của K cụm.
Bước 2 (Phân cụm): Với mỗi điểm dữ liệu X của mỗi người dùng, tính khoảng cách Euclide từ X đến K tâm điểm trên và phân X vào cụm mà có tâm điểm gần với X nhất. Kết quả của bước này là mỗi điểm dữ liệu sẽ được phân vào 1 cụm nhất định.
Bước 3 (Cập nhật): Cập nhật lại tâm điểm của mỗi cụm bằng cách lấy trung bình cộng của tất cả các điểm đã được phân vào cụm đó.
Bước 4: Lặp lại bước 2 và bước 3
Quy trình này được lặp lại đến khi toạ độ của tất cả các tâm điểm, sau khi đã được cập nhật ở bước 3, không thay đổi so với tọa độ cũ của chúng.
Có vẻ khó hiểu? Để dễ hình dung, hãy cùng mình đi qua một ví dụ minh hoạ trong không gian 2 chiều (thay vì 6 chiều).
Giả sử (lại giả sử...), chúng ta chỉ phân cụm người dùng dựa trên vị trí địa lý, thể hiện bởi 2 đặc trưng là Kinh độ và vĩ độ. Nghĩa là mỗi người dùng sẽ được giản lược hóa bằng một điểm trong không gian 2 chiều thay vì 6 chiều như trước. Trong thực tế, điều này khiến việc phân cụm trở nên kém hiệu quả hơn, vì chúng ta muốn tìm ra những nhóm người dùng chung cả sở thích, độ tuổi… nữa. Tuy nhiên, minh họa mọi thứ trên mặt phẳng 2 chiều thì dễ hơn nhiều.
Hãy tưởng tượng, mỗi người dùng được minh họa bởi 1 chấm xanh đáng yêu trong không gian 2 chiều (kinh độ và vĩ độ) như thế này . Và chúng ta muốn phân chia người dùng thành 2 cụm thôi (K=2).
Bước 1: Chúng ta chọn 2 điểm ngẫu nhiên làm tâm điểm của mỗi cụm (hình vuông xanh và hình vuông vàng).
Bước 2 (Phân cụm): Tính khoảng cách Euclide giữa mỗi chấm tròn xanh đến 2 chấm vuông, chấm tròn gần chấm vuông nào hơn sẽ được xếp vào cụm của chấm vuông đó. Đường nét đứt minh họa việc chia các chấm tròn thành 2 cụm.
Kết quả sau bước 2
Bước 3 (cập nhật): Ta cập nhật tâm điểm của mỗi cụm bằng việc lấy trung bình cộng của tọa độ của tất cả các điểm trong cụm đó. Sau khi được cập nhật, 2 hình vuông xanh và vàng mà ta chọn ngẫu nhiên ban đầu, sẽ dịch chuyển thành 2 hình vuông nét đứt như trên hình.
Sau khi điều chỉnh, 2 tâm điểm mới sẽ trông như thế này:
Đến đây, ta lại lặp lại bước 2: Tính khoảng cách giữa mỗi chấm tròn đến 2 tâm điểm mới và phân chúng vào cụm mà có tâm điểm gần hơn.
Lặp lại bước 3: cập nhật tâm điểm
Lại lặp lại bước 2..
Lại lặp lại bước 3: Cập nhật tọa độ tâm điểm mới của mỗi cụm. Tuy nhiên, đến đây chúng ta thấy toạ độ tâm điểm mới sau khi được cập nhật không thay đổi so với tâm điểm cũ. -> Thuật toán dừng lại.
Tada! Vậy là "máy" đã "học" xong từ tập dữ liệu huấn luyện, và cho ra kết quả là 2 cụm như thế này.
Bây giờ, với mỗi người dùng mới X (không nằm trong các chấm tròn ở trên), Tinder sẽ:
- Minh họa “chấm tròn” của X trên mặt phẳng 2 chiều.
- Tính khoảng cách giữa X đến 2 tâm điểm của 2 cụm đã thu được trong quá trình học ở trên.
- X nằm gần tâm điểm nào hơn thì phân X vào cụm đó. Xong!
Có thể bạn sẽ đặt câu hỏi: vậy số cụm bao nhiêu mới là hợp lí? 5 cụm, 10 cụm, hay 1000 cụm? Câu trả lời là: thử và sai! Tinder có thể test thử mô hình với từng số K, sau đó họ so sánh để tìm ra một số K tốt nhất. Điều này vượt ra khỏi khuôn khổ của bài viết nên mình sẽ không đi sâu vào nó.
Sau khi đã có được số cụm được phân chia bởi K-means, với mỗi người dùng mới, dựa trên những đặc điểm nhân khẩu học của họ, Tinder sẽ biết họ thuộc nhóm người dùng nào (phân vào cụm nào), từ đó gợi ý những profile mà những người dùng trong cùng nhóm (cụm) đó đã quẹt phải từ trước.
So far so good. Thuật toán phân cụm sẽ rất hữu ích để gợi ý profile cho những người dùng mới, khi họ chưa có hoặc có rất ít hành vi quẹt. Tuy nhiên, việc phân cụm, bởi chỉ được thực hiện dựa trên các đặc điểm như độ tuổi, sở thích và vị trí địa lí... nên khi áp dụng để gợi ý những đối tượng tiềm năng cho người dùng cũ, sẽ không tận dụng được lịch sử hành vi quẹt, những dữ liệu góp phần không nhỏ vào việc phản ánh “gu” hẹn hò của một người dùng. User-user Collaborative filtering sẽ giúp giải quyết việc này.
III. User-user Collaborative filtering - gợi ý dựa trên hành vi
User-user Collaborative filtering (lọc cộng tác dựa trên người dùng) - một trong các kĩ thuật thiết kế hệ thống Recommender system - là thuật toán gợi ý cho người dùng dựa trên hành vi của họ và những người dùng tương tự họ. Khác với clustering, sự tương tự ở đây không dựa trên các dữ liệu nhân khẩu học, mà dựa trên hành vi người dùng, hay với Tinder là hành vi quẹt phải (trái). Ví dụ, nếu X và Y cùng quẹt phải (và quẹt trái) một số lượng profile (đủ nhiều), thuật toán sẽ suy luận ra họ có cùng gu và gợi ý cho X những profile khác mà Y đã quẹt phải và ngược lại. Vậy, thuật toán này hoạt động như thế nào?
Để đơn giản, (lại) giả sử Tinder chỉ có 10 người dùng (4 nam và 6 nữ). Chúng ta sẽ xây dựng hệ thống gợi ý các profile nữ cho 4 người dùng nam trên.
1. Ma trận tiện ích (Utility matrix)
Trước tiên, ta định nghĩa một thang đo từ 1 đến 5 về mức độ yêu thích (rating) của một người dùng với một profile bất kì, dựa trên việc họ quẹt trái (hay quẹt phải) profile đó, và thời gian dừng lại trước profile đó là bao lâu.
Ví dụ, cùng là quẹt phải, nhưng nếu Minh quẹt phải trong 1-5s khi thấy profile của Hồng sẽ khác với việc Minh dừng lại trước profile trong 30s rồi mới quẹt phải. Việc định nghĩa một thang đo rộng hơn (chứ không phải chỉ Thích và Không thích) sẽ giúp hệ thống đưa ra kết quả cụ thể hơn, không chỉ là Minh có thích Hồng không, mà còn là mức độ thích như thế nào, từ đó hệ thống sẽ đưa các profile mà hệ thống dự đoán mức độ yêu thích cao nhất lên gợi ý trước.
Trước tiên, chúng ta xây dựng một ma trận tiện ích (Utility matrix) lưu trữ mức độ yêu thíchcủa người dùng với từng profile (mà họ đã tương tác) như sau:
Ma trận tiện ích của 4 người dùng nam với 6 profile nữ (hư cấu)
Những ô đánh dấu ‘?’ ám chỉ người dùng chưa tương tác với những profile đó, nhiệm vụ của hệ thống là dự đoán mức độ yêu thích của người dùng với những profile này.
Bằng mắt thường, bạn có thể nhận ra rằng Minh và Nam có gu khá giống nhau, vì cùng thích profile của Quỳnh và Mai. Hoàng và Khá cũng có gu giống nhau, vì cùng thích Linh, Hằng và trung lập với Phương. Tuy nhiên, làm sao để máy tính nhận ra điều này?
Trước hết, ta cần đóng gói thông tin mỗi người dùng bằng một vectơ, tạm gọi là vectơ hành vi hẹn hò, trong trường hợp này là trong không gian 6 chiều (vì có 6 cô gái tất cả). Ví dụ, vectơ hành vi hẹn hò của Minh sẽ là (5, 2, ?, 4, ?, ?).
Tiếp theo, chúng ta cần một công thức để đo mức độ tương tự giữa 2 vectơ (2 người dùng).
Trong thực tế, Tinder có hàng triệu profile, nghĩa là mỗi vectơ hành vi hẹn hò sẽ được biểu diễn trong không gian rất nhiều chiều. Khi đó, công thức Euclide sẽ không còn phản ánh tốt độ tương tự giữa 2 vectơ nữa. Vấn đề này được gọi là Curse of dimensionality, bạn có thể tham khảo thêm ở đây [4].
Vì vậy, trong Collaborative filtering, người ta dùng một chỉ số khác để đo độ tương tự, gọi là Cosine similarity.
Thực chất, chúng ta cũng đã được làm quen với khái niệm này trong chương trình toán cấp 3. Bạn còn nhớ cách tính cosine của góc giữa 2 vectơ n1 (a1,b1) và n2 (a2,b2) trong mặt phẳng 2 chiều không?
Độ similarity giữa 2 vecto, bản chất là cos của góc tạo bởi 2 vectơ đó, nên có giá trị trong khoảng [-1,1]. Giá trị này càng lớn chứng tỏ 2 vecto đó càng tương tự nhau. Giá trị similarity bằng 1 đồng nghĩa với việc góc giữa 2 vecto đó bằng 0 (cos 0 =1, bạn còn nhớ chứ?), nghĩa là 2 vecto đó hoàn toàn tương tự nhau. Ngược lại, độ similarity bằng -1 phản ánh 2 vecto hoàn toàn trái ngược nhau.
Hình minh hoạ Cosine similarity (θ) và Euclide distance (d) của 2 vecto OA và OB trong mặt phẳng 2 chiều
3. User-user Collaborative Filtering
Để tính được cosine similarity giữa 2 vecto, ta cần biết toạ độ "đầy đủ" của 2 vecto đó. Tuy nhiên, các vecto hành vi hẹn hò lại chứa các dấu '?' thể hiện các giá trị chúng ta chưa biết. Vậy, ta cần thay thế các dấu '?' bằng một giá trị nào đó. Mình xin trích nguyên văn cách giải thích từ blog Machine Learning cơ bản [5]:
Vậy mỗi dấu ‘?’ nên được thay bởi giá trị nào để hạn chế việc sai lệch quá nhiều? Một lựa chọn bạn có thể nghĩ tới là thay các dấu ‘?’ bằng giá trị ‘0’. Điều này không thực sự tốt vì giá trị ‘0’ tương ứng với mức độ quan tâm thấp nhất. Một giá trị an toàn hơn là 2.5 vì nó là trung bình cộng của 0, mức thấp nhất, và 5, mức cao nhất. Tuy nhiên, giá trị này có hạn chế đối với những users dễ tính hoặc khó tính. Với các users dễ tính, thích tương ứng với 5 sao, không thích có thể ít sao hơn 1 chút, 3 sao chẳng hạn. Việc chọn giá trị 2.5 sẽ khiến cho các items còn lại là quá negative đối với user đó. Điều ngược lại xảy ra với những user khó tính hơn khi chỉ cho 3 sao cho các items họ thích và ít sao hơn cho những items họ không thích.
Một giá trị khả dĩ hơn cho việc này là trung bình cộng của các ratings mà user tương ứng đã thực hiện. Việc này sẽ tránh được việc users quá khó tính hoặc dễ tính, tức lúc nào cũng có những items mà một user thích hơn so với những items khác.
(item trong đoạn trích trên chính là các profile trong trường hợp của Tinder).
Như vậy, bước 1 trong Collaborative Filtering chính là thay thế các dấu '?' của một người dùng bằng giá trị trung bình của các ratings mà người dùng đó đã thực hiện. Ví dụ, với Minh, Minh đã "rate" 3 profile với mức điểm là 5, 2, 4, vậy ta sẽ thay thế các dấu '?' của Minh bằng giá trị trung bình là (5+2+4)/3 = 3.67.
Vectơ hành vi hẹn hò của Minh trở thành (5, 2, 3.67, 4, 3.67, 3.67).
Ma trận tiện ích ban đầu
Sau khi đã điền các ô chứa dấu '?' bằng giá trị trung bình
Bước 2: Chuẩn hoá. Đơn giản là, với mỗi vecto hành vi hẹn hò, chúng ta trừ đi giá trị trung bình ở trên.
Ví dụ, với Minh, giá trị trung bình là 3.67, nên vecto của Minh sau khi chuẩn hoá sẽ trở thành (1.33, -1.67, 0, 1.33, 0, 0).
Việc trừ đi trung bình cộng của mỗi cột khiến trong mỗi cột có những giá trị dương và âm. Những giá trị dương tương ứng với việc user thích item, những giá trị âm tương ứng với việc user không thích item. Những giá trị bằng 0 tương ứng với việc chưa xác định được liệu user có thích item hay không.
- (trích blog Machine Learning cơ bản) -
Vậy, sau khi đã chuẩn hoá, chúng ta thu được Ma trận tiện ích như sau:
Các ô chứa dấu '?', sau khi được điền giá trị trung bình và chuẩn hoá, sẽ nhận giá trị 0, thể hiện rằng chúng ta chưa biết người dùng có thích profile này hay không.
Bước 3: Chúng ta dùng công thức Cosine similarity để tính độ tương tự giữa 2 người dùng bất kì.
Nhận xét:
- Giá trị Cosine similarity của một người với chính họ thì bằng 1, bởi góc giữa 2 vecto trùng nhau thì bằng 0. Điều này là hiển nhiên, bởi một người tất nhiên là giống chính bản thân mình.
- Cosine similarity (A, B) = Cosine similarity (B, A). Điều này cũng là hiển nhiên, bởi A giống B bao nhiêu thì B cũng giống A từng đó.
Bước 4: Dự đoán giá trị rating (đã được chuẩn hoá) của một người dùng X trên mỗi profile Y mà họ chưa tương tác. Cách thực hiện như sau:
- Lọc ra những người dùng đã tương tác với profile đó.
- Trong những người dùng đó, lọc ra K người dùng có similarity với X cao nhất.
- Giá trị rating được dự đoán sẽ là trung bình cộng có trọng số của K rating đến từ K người dùng đó.
Để đơn giản, hãy lấy ví dụ với K =2, nghĩa là ta sẽ dự đoán rating dựa trên 2 người giống nhất. Hãy xem rating của Minh với Linh sẽ được tính như thế nào:
- Những ai đã rate profile của Linh: Nam, Hoàng và Khá.
- Similarity của Minh với Nam, Hoàng, và Khá lần lượt là 0.17, -0.35, 0.67 => Nam và Khá là 2 người có similarity với Minh cao nhất.
- Gía trị rating của Nam và Khá với Linh (sau chuẩn hoá) là -2.4 và 0.5.
Vậy, giá trị rating của Minh với Linh sẽ là:
Rating dự đoán của Minh với Linh, được tính bằng trung bình cộng có trọng số của rating của 2 người "giống" Minh nhất là Nam và Khá.
Như vậy, hệ thống sẽ dự đoán được rating của mỗi người dùng với mỗi profile chưa tương tác, bằng cách sử dụng rating của 2 người "giống" với người dùng đó nhất.
Ma trận tiện ích với các giá trị rating dự đoán
Sau khi đã dự đoán xong, ta thấy trong 3 profile của Linh, Hằng và Chi, có vẻ như Minh sẽ thích Chi nhất, sau đó là Hằng, cuối cùng là Linh; vậy hệ thống sẽ gợi ý cho Minh profile của Chi, rồi Hằng, rồi mới đến Linh.
Như mình đã chia sẻ, User-user collaborative filtering chỉ là một trong các cách xây dựng một hệ thống gợi ý người dùng. Một hướng tiếp cận khác có thể kể đến như Item-item collaborative filtering, ý tưởng chính là thay vì dựa trên Cosine similarity của người dùng với người dùng, hệ thống sẽ dựa trên Similarity của profile với profile để dự đoán rating.
IV. Kết bài
Mình vừa cùng các bạn đi qua hai bài toán phổ biến nhất sử dụng học không giám sát (unsupervised learning) là phân cụm người dùng và hệ thống gợi ý profile với case study về Tinder. Trong thực tế, học không giám sát còn được ứng dụng cho các lĩnh vực khác như: phân cụm khách hàng trong siêu thị để offer các chương trình khuyến mãi phù hợp cho từng cụm, hay gợi ý sản phẩm mua kèm trong thương mại điện tử (Tiki, Amazon..)
Trong phần sau, chúng ta sẽ tìm hiểu về nhánh cuối cùng của học máy: học củng cố (Reinforcement Learning) với những bước tiến vượt trội như xe tự lái, AI chơi cờ vua, hay mới đây là OpenAI chiến thắng những nhà vô địch trong game Dota2. Đây cũng là phương pháp học mà cá nhân mình đánh giá là gần gũi với con người nhất: thử, sai và tự điều chỉnh hành vi của mình trong môi trường sống. Stay tuned!
