ニュースパスを支える関連記事推薦と近似近傍探索

こんにちは。メディアロジック分析部の米田 (@mathetake) です。

今日はGunosy社とKDDI社が共同で運営するニュースパスというニュースアプリケーションで使われている関連記事推薦のアルゴリズムについて書きたいと思います。

特に、約半年前に私が導入しKPIの改善に成功した新しいアルゴリズムと、そこでコアとなる近似近傍探索(Approximate Nearest Neighbor search)の技術について述べます。

既存アルゴリズムとその課題

私が今回改善する以前から導入されていた既存の推薦アルゴリズムは、複数のアルゴリズムが混ざりあった複雑なものでした。例えば以下のようなものがあります:

特徴語を抽出
特徴語による文字列検索
簡単なスコアリングを行い上位N件を抽出

また、この過程で異なるメディア様が入稿する同一の内容の記事をまとめるための 重複記事判定という作業も入ります。

この既存のアルゴリズムは、大きく以下の問題点を抱えていました。

表面的な文字列の一致を取り扱うため、関連記事リストの枠が表示されている該当記事とほぼ同一の内容の記事が出やすい
バッチ処理により、実際にアクセスが来ていない記事に対してもあらかじめ関連記事推薦リストを作成しており無駄がある
処理が複雑でメンテナビリティが低い

1.については、ユーザー体験としてはクリティカルです。私自身いちユーザーとして「関連するニュースはみたいが全く同じ話題は当該記事で読んでいるので、少し離れた周辺の話題を読みたい」という想いがありました。

まさにこの「少し離れた周辺の話題」という点が「記事を連続なベクトルとして扱い、近傍探索を行うことで関連記事推薦をする」という新アルゴリズムの開発の一つのモチベーションとなりました。これは表面的な文字列の一致のみを考慮する文字列検索では成しえないという点に注意しておきます。

また、2.3.の問題点を解消するために、新しい推薦アルゴリズムに課した条件として以下を課しました。

ユーザーが記事リストを見た際にリアルタイムに関連記事推薦リストを作成する。つまりバッチ処理ではなく、リクエストベースでオンデマンドにアルゴリズムを実行可能であること
実行可能なだけでなく、 50 milliseconds or die. の思想に基づき高速なアルゴリズムで現実的な実行時間で処理可能であること

この条件を満たしつつ問題点1.を解消するのに「記事を連続ベクトル化して近似近傍探索によりリクエストベースで高速にリストを作成する」という落とし所が見つかったため、それを新しい推薦アルゴリズムとして採用することしました。

記事のベクトル化と近似近傍探索

上述の通り"周辺の記事"を高速に検索するために近似近傍探索を行いたいのですが、そのためにはまず記事を連続なベクトルとして表現しなければなりません。そのベクトル表現では、似た話題に関する記事はベクトルとしての"距離"が近く、また逆もしかりとなるようにしなければなりません。

そのベクトル化の方法は、上記のAWS Summitでの登壇資料の次のスライドで説明されています:

f:id:mathetake:20180927122159p:plain

数百次元の単語の分散表現をあらかじめ用意し、それをベースにニュース記事(文書)の分散表現、つまり連続なベクトル表現を獲得します。

さて、記事のベクトル表現を獲得したところで、それにたいして近似近傍探索により関連する周辺話題を検索を行います。近似近傍探索 (Approximate Nearest Neighbor search)とは、最近傍法探索に対する近似的な解を与えるアルゴリズムの総称で、これまで様々なアルゴリズムが提案されています。

WEB系のインダストリーでは、Spotify社のAnnoyと呼ばれるライブラリが最も有名と言われています:

github.com

Annoyに実装されているのはRandomized K-d treeを用いた空間分割系のアルゴリズムです。その辺りの詳しいことが気になる方は、包括的な資料として以下のサーベイを御覧ください:

[1610.02455] Approximate Nearest Neighbor Search on High Dimensional Data --- Experiments, Analyses, and Improvement (v1.0)

通常であればAnnoyをそのまま使えばいいのですが、AnnoyにはGo言語*1の安定したラッパーが存在しません。*2

そのため、個人的にAnnoyと似たアルゴリズムにより近似近傍探索を行う、gannというライブラリを実装しました:

github.com

gannで実装されているアルゴリズムについては下記のブログ記事で詳しく解説しています。

Approximate Nearest Neighbor search in Go

これでニュース記事に対して近似近傍探索を高速に行い、関連記事推薦リストを作成する準備が出来ました。

同一内容フィルタリング

近似近傍探索とはいえ、記事に含まれる単語が一致する場合は当然ベクトルが似てくるため同一の内容の記事が近傍として選ばれてしまうことがあります。

したがって近傍探索の結果をそのまま使ってしまうと既存アルゴリズムの問題点1.を解消することが出来ません。

新アルゴリズムでは、近似近傍探索を( bucketScale パラメータを大きく設定することで)広めに行い同一内容の記事が含まれないようにフィルタリングを行っています。

より具体的には近傍の記事に含まれる単語の重複具合を見て、しきい値以上に重複する記事はリストに含めずスキップするという、greedyな処理を行っています。作成すべきリストは多くて十数記事なのでこの処理は数ミリ秒以内に容易に完了します。

処理の流れ

下記の図はここまでで解説した関連記事推薦の処理の流れをまとめたものになっています:

f:id:mathetake:20180927152927p:plain

ユーザーからリクエストがあってから実際に記事のリストを返却するまで安定的に50ミリ秒を切っており *3、パフォーマンスに関する目標を達成することが出来ています。

実際には、リクエストを受け付けるサーバーは検索のインデックスの作成と更新をリクエストとは非同期に行っています。

結果

例えば イチローの師匠「巨人は思いきってOB・落合博満氏を監督に」 *4 という記事に対する関連記事推薦の結果は

"巨人不振と高橋監督 篠塚氏、城之内氏、江本氏らの見解"
"松井秀喜「巨人復帰拒否」を翻意させたウルトラ人事(1)“盟友”が引き抜かれて..."
"巨人V9エース「高橋由伸監督を支えるコーチ陣に能力ナシ」"
"吉田麻也、元プロ野球の大物投手と親戚だった？"
"中日・岩瀬 999試合の記憶――もう一度対戦したい打者は..."
"【MLB】大谷翔平のマルチな才能を球団OB絶賛 「試合前には熱唱、試合ではホームラン」"
"松井稼頭央が重ねたイチローの姿 V目前で引退決断、抹消後も貫いたライオンズ愛"
"巨人・杉内が古巣ソフトバンクにあいさつ 王会長からねぎらいの言葉"
"本塁打ゼロ「守備の男」が引退へ ロッテの岡田幸文"

のようになり、上手い具合に周辺の話題を提供できていることが直感的にも確認出来ます。

この新しいアルゴリズムは、ABテストでもその効果をしっかりと確認出来ました。下記の図はその集計結果の一部です。

f:id:mathetake:20180927154955p:plain