暗黙的フィードバックのための逐次行列分解ライブラリを公開しました

NewsPicksエンジニアの北内です。今回は、先日公開した協調フィルタリングのための行列分解ライブラリについて紹介します。

ニュースの推薦アルゴリズム

私が所属するアルゴリズムチームでは、アルゴリズムの力でNewsPicksのプロダクトやサービス全体を改善するための取り組みを行っています。その一つとして、NewsPicksアプリのフィード(ニュース一覧画面)をパーソナライズするための推薦アルゴリズムを開発しています。

note.uzabase.com

ユーザーに対してニュースなどのアイテムを推薦する手法として、内容ベースフィルタリング(Content-based filtering)と協調フィルタリング(Collaborative Filtering)の2つがよく用いられます。

内容ベースフィルタリングはアイテムやユーザーの特徴に基づいて推薦する手法で、たとえばニュースのタイトルや本文に含まれる単語の情報を使って、これまでに読んだニュースに類似するニュースを推薦します。協調フィルタリングはユーザーの行動履歴に基づいて推薦する手法で、たとえばこれまでに読んだニュースが類似する他のユーザーが読んだ別のニュースを推薦します。

NewsPicksではこの2つの手法を組み合わせてニュースを推薦しています。

行列分解による協調フィルタリング

協調フィルタリングの代表的な手法の一つとして行列分解(Matrix Factorization)があります。アイテムに対するユーザーの評価値を行列にした評価値行列を、各ユーザーのベクトルからなるユーザー行列と、各アイテムのベクトルからなるアイテム行列の積に分解するアルゴリズムです。ユーザーのベクトルとアイテムのベクトルの内積を計算することで、ユーザーがまだ評価していないアイテムの評価値を予測することができます。

f:id:tau3000:20210913172842p:plain
行列分解の例(出典

NewsPicksでも行列分解を使って協調フィルタリングを実現しようと考えました。ただし、その実現にあたっては2つの課題がありました。

一つは「暗黙的フィードバックデータ」に対応した行列分解の手法が必要だという点です。ニュースなどのアイテムに対するユーザーの反応をフィードバックと呼びます。フィードバックには、映画を1から5までの点数で評価するといった明示的フィードバックと、同じ映画を何回見た、あるいは全体の何割まで見たといった暗黙的フィードバックの大きく2種類があります。

NewsPicksには、ニュースに点数などをつけて明示的に評価するような機能はなく、「ニュースを読んだ」「ニュースにコメントを書いた」などの暗黙的フィードバックデータを数値化した評価値行列をもとに行列分解をする必要があります。

これに関しては、たとえばimplicitという行列分解ライブラリが暗黙的フィードバックデータに対応しており、現在のNewsPicksのフィードの推薦アルゴリズムではこのライブラリを利用して行列分解による協調フィルタリングを実現しています。

もう一つの課題は「新しいニュースのベクトルをなるべく早く計算したい」という点です。NewsPicksには新しいニュースが頻繁に取り込まれます。速報性はニュースの大きな価値の一つであり、新しいニュースを一刻も早くユーザーに届けることが大切です。NewsPicksアプリには直近の重要ニュース一覧が表示されるエリアがあり、運営メンバーが新しいニュースを随時チェックして、一日に何度も重要ニュース一覧を更新しています。それに加えて、各ユーザーにとって価値のあるニュースをアルゴリズムによって早く届けたいと考えました。

しかし、NewsPicksのフィードバックデータから作成した評価値行列を行列分解するには10分以上の時間がかかり、さらに行列分解によって得られたユーザーやニュースのベクトルをデータベースに格納するための処理時間も必要となります。

そこでオンライン学習が可能な手法、つまり最初にバッチ行列分解を実行したあと、追加のフィードバックデータのみを使って逐次的にパラメータを更新するような手法がないか探したところ、Fast Matrix Factorization for Online Recommendation with Implicit Feedbackという論文を見つけました。またこの論文にはJavaによるサンプル実装もありました。

行列分解アルゴリズムeALSの実装

この論文とサンプル実装を参考に、提案されているeALSというアルゴリズムをPythonで実装しました。ただ、PythonだとNumPyなどのライブラリを使ったとしても実用的な処理速度になりません。そこで、JITコンパイラによってPythonのコードを高速化してくれるNumbaというライブラリを使って処理を高速化しました。

最初は行列分解の処理をCythonで実装する方法も考えたのですが、Numbaを使うことでピュアなPythonのコードのまま大幅に高速化することができました。念のためCythonでも実装してみたのですが、ほぼ同じ処理速度だっため、メンテナンスしやすいピュアPythonとNumbaの組み合わせを採用しました。これにより、当初想定していたよりもかなり短期間で開発することができました。

ちなみに、ユーザベースグループには社内副業制度があり、FORCAS分析チームの中村も実装に参加しました。

実装したeALSのライブラリはGitHubに公開してあります。またPyPIにも登録してあるので pip install eals でインストールできます。

github.com

NewsPicksのアルゴリズムチームでは、現在このライブラリを使ったニュースの推薦機能を鋭意開発中です。

もしこのライブラリに興味があるという方は、ぜひ一度使っていただき、ご感想、ご要望等をいただけるとありがたいです!

© Uzabase, Inc. All rights reserved.