Xây dựng hệ thống khuyến nghị (Recommendation Engine) cho New York Times

New York Times

New York Times

The New York Times (NYT) xuất bản hơn 300 bài viết, bài đăng trên blog và những câu chuyện tương tác (interactive stories) mỗi ngày. Bằng việc tinh chỉnh lại cách mà người đọc tìm kiếm nội dung trên NYT – cá nhân hoá vị trí các bài báo trên các ứng dụng mobile và website – có thể giúp người đọc tìm thấy những thông tin liên quan đến mình nhiều hơn, chẳng hạn như đưa đúng tin tức tại đúng thời điểm, sắp xếp các sự kiện chính và các câu chuyện theo sở thích của từng độc giả.

Trong bài này, ta sẽ thảo luận về việc các kĩ sư tại NYT cải tiến lại thuật toán khuyến nghị các bài viết trong chuyên mục Recommended for You như thế nào.

Các hướng tiếp cận cũ

Content-based filtering (Lọc dựa trên nội dung)

Tin tức khuyến nghị phải hoạt động tốt trên những nội dung mới: tin giật gân mà chưa được nhiều độc giả xem qua. Do đó, dữ liệu bài viết tại thời điểm được đăng có thể sẽ có ích: các chủ đề, tác giả, các tags từ khóa liên quan của mỗi bài viết.

Hệ thống khuyến nghị giai đoạn đầu của NYT sử dụng những tags từ khoá này để đưa ra các khuyến nghị. Bằng cách sử dụng tags cho các bài viết và lịch sử đọc bài viết trong 30 ngày của một độc giả, thuật toán đưa ra các bài viết khuyến nghị gần với những gì mà người xem đã đọc.

Hướng tiếp cận khá dễ mường tượng: nếu một độc giả đọc 10 bài viết với tag là “Clinton” thì trong tương lại họ sẽ có khả năng thích đọc các bài viết cũng gán tag là “Clinton”. Kĩ thuật này hoạt động tốt trên cả nội dung mới lẫn nội dung cũ vì nó dựa vào dữ liệu có sẵn tại thời điểm được đăng.

Tuy nhiên,  do dựa trên mô hình hướng nội dung nên thỉnh thoảng cũng xảy ra các hiệu ứng ngoài ý muốn. Vì thuật toán đặt trọng số cho các tags thông qua số lượng trong ngữ liệu (corpus), thẻ càng hiếm thì trọng số càng lớn. Mặc dù hầu hết mọi thứ đều ổn nhưng đôi khi lại làm giảm trải nghiệm của người dùng. Ví dụ, một độc giả quan tâm đến những mẫu tin về đồng tính (same-sex), thường nằm trong chuyên mục Weddings, nhưng lại được khuyến nghị đọc những bài về các cặp hôn nhân khác giới. Điều này là do tag “Weddings và Engagements” có tần suất thấp nằm trong một bài viết được đọc trước đó.

Collaborative Filtering (Lọc dựa trên cộng tác)

Để thích ứng với những thiếu sót của phương pháp trên, ta thử nghiệm với phương pháp lọc dựa trên cộng tác. Kĩ thuật này lọc nội dung bề mặt dựa trên những gì mà các độc giả trước đã đọc. Trong trường hợp này, tính tương tự được định nghĩa bởi lịch sử đọc các bài viết.

Hướng tiếp cận này cũng khá rõ ràng: nếu một độc giả có những sở thích tương tự như các độc giả khác, các bài viết mà độc giả đầu tiên đọc cũng có thể thu hút các độc giả tiếp theo xem qua và ngược lại.

Tuy nhiên, hướng tiếp cận này thất bại trong việc đề xuất các bài viết mới đăng, những bài viết chưa hề có người đọc. Nghĩa là các bài viết nằm trong nhóm các độc giả cùng sở thích nhưng chưa có ai trong nhóm đọc các bài viết này cả.

Hướng tiếp cận hiện nay

Điều này chỉ ra rằng ta có thể cải tiến bằng cách kết hợp cả hai phương pháp. Ta sẽ xây dựng một thuật toán dựa trên những ưu điểm của các kĩ thuật trên, Collaborative Topic Modeling (CTM), (1) mô hình hoá nội dung, (2) điều chỉnh mô hình dựa trên tương tác của độc giả, (3) mô hình hoá sở thích của người đọc và (4) đưa ra các đề xuất theo tính tương tự giữa sở thích và nội dung quan tâm.

Tổng quan

Thuật toán của chúng ta bắt đầu bằng việc mô hình hoá mỗi bài viết theo sự tổng hợp các chủ đề mà nó đề cập. Ta có thể xem một chủ đề là chủ đề chưa được quan sát, như Politics hay Environment, có ảnh hưởng đến các từ tìm thấy trong bài viết. Ví dụ, nếu một bài viết về environment, ta hy vọng tìm thấy các từ “tree” hay “conservation”.

Ta mô hình hoá từng độc giả dựa trên những chủ đề mà họ quan tâm. Từ đó, đề xuất các bài viết dựa vào các chủ đề gần với các chủ đề mà độc giả quan tâm.

Ta xem ví dụ sau, giả sử ta chạy thuật toán trên các bài viết của NYT được đăng vào tháng trước được biểu diễn bởi sự kết hợp của hai chủ đề (PoliticsArt). Ta tìm được bài viết, America Deepens its Footprint in Iraq Once More, 100% là Politics, và một film review bởi A.O.Scott, 100% là Art. Khi trộn hai chủ đề này lại, ta có bài viết Frick Museum Abandons Contested Renovation Plan, với nhãn là 50% Politics, 50% Art.

Trong không gian PoliticsArt, ta có thể mô tả các bài viết theo biểu đồ dưới đây:

Frick museum

Frick museum

Tiếp theo, giả sử rằng một độc giả khác có xu hướng đọc Art 60% và Politics 40%. Ta biểu diễn độc giả này bằng dấu chéo màu đỏ trên biểu đồ. Điểm thú vị đó là trong không gian này, các chủ đề nằm dọc trên đường kẻ các chủ đề mà họ quan tâm. Mặc dù họ chưa đọc chúng bao giờ, ta có thể đề xuất các bài viết tương tự như vậy dựa vào không gian trên.

Có nhiều câu hỏi đặt ra cần chúng ta trả lời. Không gian chủ đề này có thể xác định sự nhập nhằng trong cách dùng từ hay không? Làm thế nào ta có thể phân tích sở thích của người đọc một cách tốt nhất? Dựa trên click nhìn chung không bền vững: ta chắc chắn một điều rằng, có thể ta vẫn click vào những link mà ta không quan tâm để rồi bỏ lỡ những bài viết thú vị hơn.

Đây là ba phần thử thách:

  • Phần 1: Làm thế nào để mô hình hoá một bài viết dựa trên văn bản (text) của nó.
  • Phần 2: Làm thế nào để cập nhật mô hình dựa trên thói quen của người đọc (audience reading patterns).
  • Phần 3: Làm thế nào để mô tả các độc giả dựa trên lịch sử đọc của họ.

Phần 1: Làm thế nào để mô hình hoá một bài viết dựa trên văn bản (text) của nó

Đầu tiên, thuật toán của chúng ta quan sát phần body của từng bài viết và áp dụng Latent Dirichlet Allocation (LDA), một thuật toán mô hình hoá nội dung. LDA học sự pha trộn (mixture) của các “topics” trong từng bài viết: Một topic được định nghĩa một cách hình thức như một phân bố trên một bộ từ vựng. Nếu một document có một topic được đánh trọng số cao thì những từ tìm thấy trong bài viết đó cũng được đánh trọng số cao theo topic đó.

Thuật toán LDA nhanh và chính xác phù hợp với mục đích của chúng ta cho các suy luận trực tuyến (online inference). Nghĩa là các topics được mô hình hoá tại thời điểm các bài viết mới vừa được đăng. Các topic trong LDA có phân bố rộng (ví dụ những topic Middle EastFilm và Healthcare), điều này cho phép chúng ta liên kết các thành phần từ những gốc độ khác nhau.

LDA dựa trên graphical model, có thể dễ dàng mở rộng để kết hợp những giả định mới vào thông tin hiện có. Trong trường hợp của chúng ta, ta sẽ mở rộng mô hình không chỉ dựa vào văn bản của bài viết mà còn hướng đến những độc giả cụ thể liên quan đến bài viết đó.

Phần 2: Làm thế nào để cập nhật mô hình dựa trên thói quen của người đọc

LDA nhận đầu vào là tập các từ, nhưng các từ này thường bị nhập nhằng: về ngữ cảnh, việc lên giọng và giảm tốc độ có thể thay đổi nghĩa của từ. Ví dụ, nếu Gail Collins viết một bài gồm các từ “dog”, “car” và “roof”, làm sao ta phân biệt được tác giả đang nói ẩn ý chứ không phải nói về các loài động vật và xe cộ?

Cụ thể, nếu chỉ áp dụng LDA thông thường, ta sẽ có bài viết của Gail Collins thuộc vào topic travel, bài viết thể hiện bằng chấm tròn màu xanh như biểu đồ bên dưới.

Dogging Mitt Romney

Dogging Mitt Romney

Tuy nhiên, một lượng lớn các độc giả đọc bài viết trên cũng đọc các bài về Hillary Clinton và Ted Cruz (mô phổng bằng các điểm x màu đỏ). Dó đó, ta muốn thuật toán điều chỉnh về điểm màu xanh lá gần với topic Politics. Bằng cách thêm vào độ dời vào độ lỗi của topic model, như đề cập trong bài báo CTM, thuật toán của chúng ta kết hợp thói quen đọc của người dùng với nội dung được mô hình hoá để tạo ra phương pháp lai (hybrid approach).

Thuật toán CTM hoạt động bằng việc điều chỉnh độ dời và tính toán lại điểm số (score) của độc giả. Thuật toán lặp cho đến khi độ sai biệt sau mỗi lần lặp không còn đáng kể. Bằng cách lọc ra tập con các độc giả, gọi là tập huấn luyện, ta sẽ được thông tin này.

Ta kiểm định hai phương pháp điều chỉnh độ dời: (1) CTM và (2) hướng tiếp cận Collaborative Poisson Factorization. Ta thấy rằng CTM hoạt động tốt hơn.

Phần 3: Làm thế nào để mô tả các độc giả dựa trên lịch sử đọc của họ

Các phương pháp để điều chỉnh topics của bài viết cũng tính toán sở thích của độc giả, nhưng chúng không mở rộng cho tất người dùng. Do vậy, ta cần một cách nhanh hơn để tính các sở thích của độc giả.

Một hướng tiếp cận đơn giản đó là tính trung bình các topic của mọi bài viết lại với nhau: nếu ta click vào một bài viết có tỉ lệ 40% Politics, 60% Art và bài viết khác có tỉ lệ 60% Politics, 40% Art, ta có không gian PoliticsArt [0.5, 0.5].

Tuy nhiên, giả định này cho rằng việc click vào các bài viết cũng là sở thích của người đọc. Điều gì xảy ra nếu ta click vào một bài viết mà ta không thích hay bỏ lỡ bài viết mà mình quan tâm? Một cách tiếp cận đó là lùi lại một chút (back off a bit), bảo rằng bạn chỉ thích 90% những bài viết mà bạn đọc và 10% những bài viết mà bạn không thích. Ta tạo một khoảng lỗi dành cho những cú click không chính xác trong trường hợp này.

Back off average

Back off average

Ở biều đồ trên, những chấm xanh lá biểu diễn các bài viết mà độc giả đã xem, và những chấm đỏ biểu diễn những bài viết mà độc giả chưa xem. Dấu x màu đen là tỉ lệ trung bình các bài viết đã đọc, dấu x màu xanh là hướng tiếp cận back-off.

Hướng tiếp cận back-off thận trọng hơn trong việc ước lượng điểm sở thích của độc giả, điều này cho phép chúng ta  kiểm soát được những dữ liệu ngoại lai. Ngoài ra còn giúp cho các độc giả thoát khỏi những bài viết được đề xuất một cách “cầu may”.

Bằng cách triển khai những thuật toán cải thiện tốc độ, ta đã có thể tính toán sở thích của độc giả dưới một mili giây cho mỗi độc giả, cho phép ta mở rộng tính toán này cho mọi người dùng.

Kết luận

Bằng cách mô hình hoá nội dung bài viết và sở thích của người đọc theo các chủ đề, sau đó điều chỉnh dựa trên thói quen của người đọc (reading patterns), ta đã cải tiến được hệ thống khuyến nghị của mình. Với hệ thống khuyến nghị mới này, NYT hy vọng sẽ mang lại nhiều trải nghiệm mới với các bài viết thú vị tại đúng thời điểm cho người đọc.

Nguồn: http://open.blogs.nytimes.com/2015/08/11/building-the-next-new-york-times-recommendation-engine/?_r=2

Advertisements

2 thoughts on “Xây dựng hệ thống khuyến nghị (Recommendation Engine) cho New York Times

  1. với thuật toán trên ta có thể sử dụng cho ngôn ngữ tiếng việt được ko anh? anh có bài viết nào về xử lý tiếng việt ko? em muốn nghiên cứu về bài toán phân loại nội dung trên ngôn ngữ tiếng viêt nhưng chưa biết phải bắt đầu từ đâu

    Like

    • hi em, các thuật toán chỉ phù hợp với tập dữ liệu nhất định, quan trọng em đã thu thập và gán nhãn đầy đủ hay chưa. Nếu mẫu dữ liệu em thu thập được đã thoả các điều kiện ban đầu của thuật toán thì hoàn toán có thể áp dụng được.
      về xử lý tiếng Việt, anh đang bổ sung từng bước cho blog 🙂

      Like

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s