AmazonからYouTubeまで
有名Webサービスを支える推薦アルゴリズムのこれまでとこれから

推薦アルゴリズムの今までとこれから

2018年3月29日、株式会社サイバーエージェントが主催するイベント「春の機械学習祭り 〜Data Engineering & Data Analysis WS#4〜」が開催されました。サイバーエージェントのデータ分析基盤とデータ活用、およびそれらの技術を共有する本イベントでは、秋葉原ラボ所属メンバーを中心に基盤と分析について具体的かつ実践的な技術を紹介します。プレゼンテーション「推薦アルゴリズムの今までとこれから」では、内藤遥氏が登場。Amebaを支える推薦基盤について、その裏側を語ります。

推薦アルゴリズムの変遷

内藤遥氏(以下、内藤):それでは、まず初めに私のほうから、「推薦アルゴリズムの今までとこれから」というテーマで発表させていただきます。タイトルだけ聞くと「ちょっと基調講演みたいだよね」ってけっこう言われたんですけど(笑)。内容はそんな仰々しいものではないので、みなさんご了承ください。よろしくお願いします。

まず初めに簡単な自己紹介なんですけど、私は内藤遥と申します。2012年度にサイバーエージェントに入社いたしまして、入社後は一貫して、技術本部の秋葉原ラボに所属しています。現在は、推薦基盤や検索基盤の開発や運用をメインでやっています。

好きなラーメンは台湾まぜそばで、こちらは名古屋で発祥したラーメンというか、まぜそばなんですけれども。秋葉原ラボの近くにけっこうおいしいまぜそば屋さんがありまして、週2回ほど足を運んでいます。好きなお笑い芸人はジャルジャルです。去年の『M-1グランプリ』のピンポンをネタにした漫才が僕にとって衝撃的で、それ以降食い入るようにYouTubeを見たりしています。そんな感じです。

さっそく目次なんですけれども、まず始めのほうに、題目どおり推薦アルゴリズムの変遷についてお話しできればと思っています。後半部分では、「Amebaにおける推薦基盤の現状とこれから」ということでお話しできればと思っています。よろしくお願いします。

初めに推薦アルゴリズムの種類についてなんですけれども、こちらは大きく2つあります。

1つは協調フィルタリングと呼ばれるもので、これはどういったものかと言うと、自分と自分以外の多くの人の評価データを利用した推薦になっています。例で言うと、「この商品を買った人はこんな商品も買っています」といったものです。

こちらはドメイン知識が不要になるのですごくメリットがあるんですけれども、一方でコールドスタート問題というのがあります。要は、新規ユーザーや新規アイテムといった、評価データが貯まらないものに関しては推薦ができない、といったデメリットも抱えています。

もう1つにコンテンツベースというものがありまして、こちらはアイテムの特徴の類似度に基づく推薦となっています。コンテンツベースはドメイン知識が必要になるんですけれども、コールドスタートでも推薦が可能になる、といったメリットも持ち合わせています。今回お話しする内容は、上の協調フィルタリングのお話になります。

さっそく推薦アルゴリズムの変遷ということで、これからお話する内容を1枚の図にまとめてみました。

まず初めにユーザーベースだったりアイテムベースの協調フィルタリングのお話をしまして、そのあとに行列分解だったり、コンテキスト情報を追加できるような手法の紹介、そして最後にはユーザーの嗜好の推移を学習できる手法についてお話できればと思っています。

GroupLensとItem-based Collaborative Filtering

初めにGroupLensについてなんですけれども、こちらはユーザーベースの協調フィルタリングです。協調フィルタリングシステムのパイオニア的手法であるとも言われています。現在このGroupLensという名前は、ミネソタ大学の研究所の名称にもなっています。

手法で言うと、あるユーザーのアイテムに対する評価値を、まずそのユーザーと似ているユーザーを見つけて、似ているユーザーの評価値を利用して予測する、といったものになっています。ここで言う評価値というのは、App Storeのレビューのようなものと考えていただければわかりやすいかと思います。

そしてItem-based Collaborative Filteringの話なんですけど、これは名前のとおりアイテムベースの協調フィルタリングの話で、Amazonさんが利用していることでも有名です。

GroupLensとはある意味逆の手法になっています。あるユーザーのアイテムに対する評価値をユーザーではなく、そのアイテムと似ているアイテムを見つけて、似ているアイテムに付けられた評価値を利用して予測するような手法です。

この手法ではアイテムの類似度を計算するので、その類似度を基に、あるアイテムに関連する別のアイテムを推薦することも可能です。また、このアイテム間の類似度の計算をオフラインで行うことで、スケーラビリティの確保もできるといった利点があります。

次に、Amebaでの利用についてお話しします。類似度の計算のところでアイテム数が増えると、全アイテムペア間の類似度の計算時間がすごく大変そうに見えるんですけれども、実際には評価値行列が疎になってることが多いので、共起した要素を持たない、すなわちどのユーザーも同時に評価したことがないようなアイテムのペアがたくさんあります。

なので、そういったペアに関しては計算が不要なので、事前に共起情報をチェックすることで計算時間を短縮できます。この手法はとくにハイパーパラメータもないので、手軽に導入できるといったメリットがあります。

従来の問題を解決できる手法「Matrix Factorization」

続いて、Matrix Factorizationの話に進んでいきます。ちょっと呼びにくいので、以降「MF」と呼ばせてください。こちらは推薦の話をする上で必ず出てくるであろう、「Netflix Prize」と呼ばれるアルゴリズムコンテストの中で登場した手法になっています。

もともと従来の協調フィルタリングでは、先ほどお話したように評価値行列が疎になっていることが多いので、精度面の問題や、データが少ないと類似するユーザーやアイテムを十分に見つけられない問題がありました。この手法は、これらの問題を解決できるような手法です。

手法について、図で説明するとこんな感じになっています。

要は、ユーザー・アイテムの評価値行列Rを、ユーザーの特徴量行列Pとアイテムの特徴量行列Qに分解するような手法です。

MFの目的関数の最小化なんですけど、このような式になっています。

ここで、rはユーザーのアイテムに対する評価値、p、qはそれぞれ、行列分解後のユーザーベクトル、アイテムベクトルに対応しています。右側のλは正則化項になっていまして、評価値とユーザー・アイテムベクトルの内積の値がより近くなるようにp、qを学習していく、といったかたちになっています。この式はSGDやALSといった最適化アルゴリズムで学習されます。Sparkでは分散処理がしやすいということで、ALSが採用されています。

そしてAmebaでは主に閲覧履歴や購入履歴といった、ユーザーが明示的には評価しないもののシステムで取得できるような、暗黙的評価を利用する場合に使用しています。通常はアクションの回数を評価値として扱いますが、閲覧が1、お気に入りが2、購入が3、みたいな感じで、アクションごとに評価値をヒューリスティックに決めて組み合わせることがあります。いろいろ組み合わせはあると思うんですけど、そこはオフラインでの精度評価やA/Bテストを通して、一番良いと思われる組み合わせを決定していくかたちをとっています。

属性情報やコンテキストを組み込むことができる「Factorization Machines」

次に、Factorization Machinesについての説明をしていきたいと思います。ちょっと言いにくいので以降は「FM」と呼ばせてください。

FMは2010年に登場した、識別問題をはじめとするさまざまな問題に適用できる一般的なモデルです。MFではシンプルにユーザーとアイテムの評価値行列を分解するので、それだけでは難しかったユーザーやアイテムの属性、例えばユーザーの年齢とか性別、アイテムでいくとカテゴリー情報といった属性情報だったり、あとはコンテキストですね。時間や位置情報など、ユーザーの状況を表すような情報をモデルに組み込むことができるようになりました。

FMを図で表すとこんな感じになります。

FMでは1つの評価を1行で表現しています。ここで左側の青枠やオレンジの枠が、それぞれユーザーやアイテムのone-hotベクトルに対応しています。あとは右側、属性やコンテキストの情報を好きなように追加することができます。そしてそれらの情報に対して評価値が紐づいている、といった内容になっています。

FMの予測式はこのような感じになっていまして、ポイントで言うと右側の赤枠の部分になります。

こちらは交互作用項になっています。交互作用項の重みになるところをベクトルの内積で近似しているところがポイントになっています。こうすることで、膨大な数になったであろう交互作用項のパラメータの数を抑えて、結果として学習時間を短縮できる、といったメリットがあります。

次にAmebaでの利用については、SparkでFMを実装していまして、Spark上で動かしています。ただし導入サービスは少なくて、その理由としては、MFがシンプルな内積の計算だったのに対して、FMは予測の計算にすごく時間がかかってしまうので、アイテム数が多くなった時にTopN件の算出をするのがすごく難しいということだったりとか。あとは特徴選択のところでドメイン知識が必要になってくるので、ちょっと連携しにくいところもあったりするためです。

嗜好情報を時系列データとして学習する「Recurrent Neural Networks」

続いて、Recurrent Neural Networksの話に進んでいきます。こちらもちょっと言いにくいので、以降「RNN」と言わせてください。こちらは名前のとおり、再帰型ニューラルネットワークと呼ばれるものです。こちらの手法が使われる狙いとしては、ユーザーの嗜好が時間と共に変化していくことによります。例えば、昔長澤まさみを好きだった人は、今はガッキーが好きかもしれない、みたいな感じです。まあ、僕のことです。

(会場笑)

といったように、この手法を使う狙いは、ユーザーの嗜好情報を時系列データとしてパターンを学習して、ユーザーが「今」本当に欲しい情報だったり、欲しいアイテムを推薦する、といったものです。

RNNを実際に使っているサービスもけっこうありまして、例えばYahoo! Japanさんでは、ユーザーに対するお勧め記事のモジュールにRNNを使っていたりします。こちらでは、ユーザーの視聴履歴の各記事の分散表現を入力値、そしてユーザーベクトルを出力とするようなRNNを考えられています。学習方法で言うと、クリックされた記事に対して、ユーザーベクトルと記事ベクトルの内積のスコアがより大きくなるように学習しています。

一方で、YouTubeでも最近論文が出されていまして。こちらでは、ユーザーの視聴履歴の各ビデオの分散表現を入力、そしてsoftmaxによる各ビデオIDの確率値を出力とするようなRNNになっています。この論文の特徴としては、Time Deltaと呼ばれる前回からの視聴時間の差分だったり、Software Clientと呼ばれる、iOSだったりAndroidだったりChromecastといった種類の情報をコンテキスト情報として隠れ層に組み込むことができる、といった特徴を持っています。

最近注目しているのは「Collaborative Metric Learning」

最後になるんですけど、最近我々が注目している手法として、Collaborative Metric Learningと呼ばれるものがあります。この手法に注目している動機は、オンラインで行う計算はなるべく高速化したいということで、先ほど例に挙げたYahoo! Japanさんや、Gunosyさんもそうなんですけど、オンラインでの計算はユーザーや記事のベクトルの内積の計算がメインになっています。

この場合、一定数のアイテムに対してはぜんぜん問題なく計算できるんですけど、もっとアイテム数が多い場合はどうするか、というところで、2つ解があるかなと思っていて。1つは、アイテムの候補を絞ること。もう1つは近似的に解くということで、この手法は後者の解法になります。

手法については、まずユーザーとアイテムを同じ次元の空間に写像して、その上であるユーザーとユーザーが高く評価したアイテムが、より近くなるように距離を学習することで、距離計算の問題に変わります。なのでLSHなどの近似最近傍探索のアルゴリズムを使うことができて、結果としてオンラインでの計算も高速に行うことができる、といった手法となっています。

Amebaにおける推薦基盤の現状

以上が推薦アルゴリズムの変遷の話になります。これからはAmebaにおける推薦基盤の現状とこれからについてお話したいと思います。Amebaにおける各種推薦ということで、いろいろなサービスで我々の推薦の機能を使ってもらっています。

例えば左上の、「FRESH!」という生配信の放送サービスがあるんですけど、こちらはその関連番組のモジュールで使ってもらっていたり、左下の「グルっぽ」と呼ばれるAmeba内のコミュニティサービスでも使ってもらっていたり。あとは真ん中のAmebaアプリですね。「見つける」面という最近できたモジュールにも組み込まれていたり。あと一番右側に「読書のお時間です」という漫画のECサイトがあるんですけども、そちらでも使ってもらっています。

ここで、Amebaにおける推薦基盤について簡単に説明したいと思います。システムの全体図を表すとこんな感じになっています。

秋葉原ラボではPatriotと呼ばれるHadoopのデータ解析基盤を持っているんですけど、その上で大規模データを活用して、各種サービス向けに協調フィルタリングをメインとした推薦機能を提供しています。

推薦の流れについて簡単に説明しますと、まず前提として、各サービスからの閲覧履歴や購入履歴といった行動ログがPatriotに送られています。その行動ログを利用して、各サービスに対して推薦のバッチジョブを実行して、推薦結果を作ってHBaseに書き出す、といったことをやっています。それらの推薦結果を、各サービスからAPIを通して取得できる、といった流れになっています。

一方で各サービスには、推薦結果に対するimpとclickの情報のログを吐いてもらうお願いをしていて、それらの情報を基にCTRのレポーティングや、バンディットアルゴリズムを使ってオンラインで推薦結果をリランクする、みたいなこともやっていたりします。

バッチフレームワークの「ジョブ」「タスク」「レシピ」

次に、推薦基盤では推薦特化のバッチフレームワークなるものを開発しています。目的としては、新規サービスの導入コストや運用コストの削減です。なぜ新しく作る必要があるのかというと、良いフレームワークとはなにかを考えたときに、「柔軟性がある」だったり「読むべきコードが最小化されている」「安全である」ことが挙げられると思うんです。その「柔軟性」と「読むべきコードの最小化」を同時に達成しようとすると、ドメイン特化にならざるを得ないよね、ということで、今回新しく開発したという感じです。

バッチフレームワークでは、3つの「ジョブ」「タスク」「レシピ」と呼ばれる概念を定義しています。まず「ジョブ」、こちらはタスクを組み合わせた一連の処理の枠組みで、例で言うと推薦ジョブだったりとか、推薦元データ取得ジョブなどがあります。

次に「タスク」なんですけれども、こちらはデータの読み込みや書き出しなど、機能で分割された処理の単位を表していて、例で言うとReaderだったりRecommenderだったり、Writerといったものがあります。

最後に「レシピ」なんですけれども、こちらはジョブの中身を形成する設定ファイルで、どこからデータを取得するか、どの推薦アルゴリズムを使うかの設定ができるようになったりします。それをYAML形式で管理しています。

次に推薦ジョブのワークフローについて見ていくんですけれども、まず初めに、Readerのところで推薦元のデータの読み出しを行って、続いてProcessorのところで、必要に応じてデータの加工をします。次にRecommenderで実際に推薦結果の作成をして、最後にWriterのところで推薦結果の書き出し、といったことをやっています。

これらの処理の一連の流れはサービスごとで同じになるんですけれども、もちろんサービスごとのビジネスロジックというものも存在しています。そういうビジネスロジックは、Service Processorと呼ばれるタスクに集約しています。こうすることで、新規サービスを導入するときに、基本的にはService Processorの実装のみ注力すればいいような設計になっています。

次に、レシピの例についてちょっと載せてみました。YAMLで書かれていて、Sparkの起動設定やデータの読み込み設定、サービスのビジネスロジックの参照部分があったり、推薦ロジックの設定だったり、データ書き出しの設定ができるような感じになっています。

Amebaにおける推薦基盤の現状とこれから

続いてAmebaの推薦基盤の現状についてお話ししていきます。推薦アルゴリズムは現在、MFが主流となっています。一部でFMだったり、Item2Vecと呼ばれるWord2Vecのレコメンド版みたいなものがあるんですけど、それを試験的に導入しているような感じです。基本的に今、バッチ処理で推薦結果を作っているので、更新性の担保が課題となっています。

以上を踏まえた上で、Amebaの推薦基盤のこれからについてお話ししたいんですけれども、RNN化だったりリアルタイム化に向けて、今いろいろと構想を練っている感じです。

ただ、課題もたくさんありまして。まずRNNに入力するアイテムのベクトル化をどうするかというところです。サービスによってアイテムのフォーマットがぜんぜん違うので、それらの違いを吸収するレイヤーが必要になったり、モデルの更新フローや管理周りの整備も必要になります。リアルタイム化のところで言うと、新着アイテムやユーザーの検知周りの整備というのも進めていかなければいけません。

最後にまとめとしては、推薦アルゴリズムではMFをはじめとして行列分解の手法から、ディープラーニングの一種であるRNNへトレンドがシフトしています。一方で行動履歴だけじゃなくて、ユーザーやアイテムの属性であったり、コンテキストの情報をいかにモデルに組み込めるかが重要になってくるんじゃないかな、と思っています。

一方でAmebaの推薦基盤は、現状は推薦特化のバッチフレームワークだったり、A/Bテストだったりレポーティング機能を有しています。現状はバッチ処理がメインになっているんですけども、それをリアルタイム化していくとか、現状でMFやFMを使っているところをRNN化していければいいな、というのが今後の展望になっています。

発表は以上になります。ご清聴ありがとうございました。

処理のリアルタイム化とRNN化をどう両立させる?

質問者1:最後のスライドに「処理のリアルタイム化」と「RNN化」というのがあるんですけど、これ一見矛盾するように見えるんですが。というのは、RNNって重いので、リアルタイム化するのはすごく難しいと思いまして。これはなにかアイディアが……?

内藤:それに関して言うと、モデルの更新をリアルタイムでするわけではなくて、新着アイテムとか、新着ユーザーもそうなんですけど、それに対して分散表現と言うか、ベクトル化できるようになればいいなというのが「リアルタイム化」の目的になっています。

質問者1:更新分の切り分けをリアルタイムでやるんですか?

内藤:そうですね。そういう感じです。

質問者1:ありがとうございます。

質問者2:リアルタイム化ということになりますと、だったら計算機をただ増やしたらいい、という感じもしなくはないんですけど、それではやっぱりダメですか? 例えばマシン間のレイテンシーが多すぎるとか。そういった制約はやっぱりあるんでしょうか?

内藤:確かにマシンを増やせば、パワープレイでできるんじゃないかということなんですけども、やはりサーバーのリソースの問題というところも兼ね合いになってくるので。そこはやはり、効率良くできるようにしたいね、みたいな課題はあったりします。

質問者2:だいたいどれくらいの計算量になるんですか?

内藤:計算量ですか?

質問者2:例えば配列で言うと、100万行列×100万行列でするみたいな話だったり。

内藤:オンラインのTopN件抽出のところで言うと、サービスで抱えているアイテム数に依存するかな、と思っています。数千とか数万単位のアイテムだったら、まあ内積の計算とかでもいいんですけども。

それ以上になってくると、ちょっと工夫しないとオンラインで計算できないよね、というところで、先ほどお伝えしたCollaborative Metric Learningの手法だったりとか。まだほかにもいろいろあると思うので、その辺を模索していきたいなと考えています。

質問者3:推薦アルゴリズムにはぜんぜん詳しくないんですが、そのアルゴリズムを選ぶ良さや評価はどのようにやられているんでしょうか? 「この推薦は良かった」っていうのはどうやってやるんでしょう?

内藤:評価に関しては、オフライン評価とオンライン評価の2つに分かれています。オフライン評価もいろいろあるんですけども、やっぱりオフライン評価の結果が実際リリースしたときの結果に紐づくかって言われると、そういうわけではないので。現状で言うと、オンライン評価。オンラインでCTRを見て「良くなったね」みたいな評価をしているのが現状です。

質問者3:例えばビジネス的なKPIに貢献があったということで。

内藤:そうです。

質問者3:わかりました。

司会者:それでは、講演ありがとうございました。

内藤:ありがとうございました。

(会場拍手)

Occurred on , Published at

Data Engineering & Data Analysis WS

Data Engineering & Data Analysis WSに関する記事をまとめています。コミュニティをフォローすることで、Data Engineering & Data Analysis WSに関する新着記事が公開された際に、通知を受け取ることができます。

スピーカーをフォロー

関連タグ

人気ログ

人気スピーカー

人気コミュニティ

ピックアップ

編集部のオススメ

ログミーTechをフォローして最新情報をチェックしよう!

人気ログ

人気スピーカー

人気コミュニティ

ピックアップ

編集部のオススメ

そのイベント、ログしないなんて
もったいない!
苦労して企画や集客したイベント「その場限り」になっていませんか?