最近、システムという観点での推薦システムって、一般的にどうやって作られてるんだろう？って考えることがありました。 そんなことを考えていたところ、最近こちらのブログを拝見しました。
今回はこちらのブログを読んで、考えてみたことをまとめていきたいと思います。
はじめに
システムとしての推薦
推薦システムではユーザーの好みや行動に合わせて表示するアイテムを表示し分けます。 オススメされるアイテムが1件の場合もあれば、複数件のアイテムが優先度順になって表示されていることもあります。
ちょうど、Googleの推薦の概要紹介ではアプリストアの例が挙げられており、下記のようにユーザーに複数のアプリがおすすめされるように動作しています。
アプリストアにあるアプリは非常に多く、その中から我々は自分たちが求めるアプリを見つけ出さなくてはならず、こういった状況でユーザーが求めているものを見つけだす際に推薦は非常に重要な役割を果たします。
ただし、推薦システムの研究・文献というと、その多くが機械学習等を駆使したモデルに関するものかと思います。 一方で、実際に推薦システムを作ろうとすると、機械学習モデル構築以外にも多くの解決しなければならない問題があります。
データ量
推薦をシステムとして扱う際に問題になってくるのが、そのアイテム数の多さです。 推薦する対象になるアイテムの総数は数百万から数億、場合によっては数十億にも登ることもあります。 ユーザーに合わせた推薦を行うことを考えた場合、これらのアイテムをユーザーごとに優先度付けしていく必要がありますが、すべてのユーザーに対してアイテムすべてについて優先度をつける処理は現実的ではありません。
ビジネスロジック
また、推薦という文脈で考えたときには、ビジネスロジックが入り込むかもしれません。 例えばECサイトであれば、ユーザーに推薦する商品は在庫がある商品が望ましいですし、ユーザーの年齢によってはオススメしてはいけない商品があったりします。
通常これらのビジネスロジックを適用するために、優先度付けだけに頼るのではなく、フィルタリング条件によって推薦候補を制御する必要があります。
推薦システムの概念的な処理の流れ
ここまで簡単に推薦"システム"の難しいところについて確認したところで、今度は実際の推薦システムはどのようにして作られているのかについて確認します。 今回参考にさせていただいたRecommender Systems, Not Just Recommender Models によれば、推薦システムは以下の概念図の抽象化されるようです。
大まかに下記の4つの処理が行われることで推薦が実現されるといいます。
- Retrieval
- 推薦に使用するアイテムの候補を絞り込む
- Filtering
- ビジネスロジック等によって、推薦すべきではないアイテムを除外
- Scoring
- 残った推薦候補のアイテムに対してスコアリング
- Ordering
- スコアリングに基づいてアイテムの表示位置を並べ替え
これらは、区分の名称こそ異なりますが、他の文献で同様の流れで推薦システムの概念的処理が語られることが多いように思います。 例として、先に紹介したGoogleの推薦の概要紹介では、下記のように
- Candidate Generation
- Scoring
- Re-ranking
に分けて紹介されています。
この場合でも、
- Candidate Generation = Retrieval + Filtering
- Re-ranking = Ordering
と考えると、呼び名は異なるとはいえ、一般的にこのような流れになるようですね。
Retrievalでは、多いときには数十億にも及ぶアイテムの中から、下流の処理に受け渡すアイテムが高速に絞り込まれます。 現代でのRetrievalの処理には多くの場合、ユーザーに関する情報（場合によっては検索クエリなども含む）をもとにEmbeddingを作成し、近似最近傍探索 (ANN) によって関連しそうなアイテムを絞り込むことが多いようです。
ただし、これがすべての手法というわけではなく、例えばグラフ構造でアイテムを表現しているときにはグラフ構造の近傍探索が使用されたりしますし、ECなどのドメインではユーザーが購入した商品と一緒に買われることが多い商品を協調フィルタリングによって計算することでRetrievalが行われるなど、Retrievalの手法にも様々あることがわかります。 共通するのは、これらの段階では粗く高速に、推薦の候補となるアイテム群を絞り込むことが行われている点だと考えられます。
Filteringでは、Retrievalで取得したアイテムの中から、推薦から外すべきアイテムが除去されます。 例えば、音楽のストリーミングサービスで過去の聞いたことがある楽曲を推薦対象から除外して新しい楽曲をおすすめしたり、ECサイトで在庫切れのアイテムをオススメする候補から除外したりしています。
Scoringでは、Filteringまでで得られた「推薦するアイテムの候補」に対して、優先度を割り振っていきます。 ここでは、Learning to Rankが用いられたり、機械学習による分類問題によってScoreが割り当てられます。 Filteringまでは推薦候補を粗く高速に取得している対して、Scoring以降では正確に上位の候補をスコアリングしていきます。
最後にOrderingで、Scoringによって得られた優先度に基づいてアイテムを並べ替え、その並び順に基づいてアイテムが実際に表示されていきます。 場合によってはここでもビジネスロジックが入る必要があり、Orderingにテコ入れされたりして、最終的な出力が得られます。
オンラインとオフラインの切り分け
上記のようなフローで推薦が行われたとき、オンラインでの処理とオフラインでの処理はどのように切り分けられるでしょうか？ それについて確認していきます。
Offline
オフラインではオンライン環境で使用するデータの準備全てを行っていきます。 RetrievalでANNを使用する際には、アイテムを適切な位置のEmbeddingに振り分けるEmbeddingモデルを作成し、それを用いてANN用のインデックスを事前に構築することが行われます。その他、ナレッジグラフの構築が行われる場合もあります。
Filteringはビジネスロジックによって様々ですが、bloom filterが使用できるかもしれません。 bloom filterは確率的データ構造で、これを使用することによってFilteringを高速に行うことができる場合もあります。 このフィルタを用意するのは一つオフライン処理で必要になるかもしれません。
Scoringでは、アイテムに優先度付けを行っていくわけですが、その際に使用するモデルはオフラインで構築しておく必要があります。 また、Scoringのモデルの入力になる特徴量についても事前計算しておく必要があるかもしれません。
Orderingでは、基本的には優先度に基づいて並べ替えるだけとは言うものの、そこにもビジネスロジックが入り込んだいります。 音楽ストリーミングサービスなら「n曲以上連続して同じアーティストをおすすめしない」といった制約が入ったり、ECサイトであれば「同じメーカーの商品は1つだけ推薦リストの中で1つだけ」といった制約が入るかもしれません。 こういったビジネスロジックを事前に盛り込んでおくことがオフラインでの準備になりそうです。
Online
オンラインでは、オフライン処理によって事前に準備したモデルやビジネスロジックを駆使して、RetrievalからOrderingまでが、順に実行され高速にレスポンスを返していきます。
冒頭で紹介したように、推薦システムでは推薦の候補となるアイテムが非常に大きいことが問題になりますが、これをRetrievalとFilteringによって候補を絞ることで高速に処理を行います。また、ビジネスロジックが入り込む必要がある場合には、FilteringやOrderingの際にロジックを適用することで対応していきます。
このようにして、一般的な推薦システムは実現されているようです。
事例
上記で紹介した一般的な推薦システムのモデルケースの挙動を踏まえた上で、実際のTech企業ではどのような挙動をしているのか確認していきたいと思います。
YouTube
この手のシステムの話をするときに、よく紹介される事例としてYouTubeが挙げられます。 YouTubeでは何十億というユーザーが日々動画を閲覧しています。 また、何時間にも及ぶような動画コンテンツが1秒間に何本もアップロードされており、新しくアップロードされたコンテンツやユーザーの最新の行動に基づいて推薦を切り替えることが求められます。
そのようなことが求められる中でこのときのYouTubeでは、RetrievalでANNを使用してCandidate Generationを行い、Scoringでは動画の視聴履歴やユーザーが使用する言語、動画に含まれる言語などから作成されるEmbeddingを使用したNNによってスコアが付与されていました。
この例でも、Candidate Generation -> Rankingの流れで推薦が行われていますね。
Alibaba
Alibabaのシステムでも上記と似たような処理が行われているようです。
Alibabaではグラフ埋め込みのフレームワークに基づいて推薦が設計されています。 特に、Candidate generationについて、事前に構築したアイテムグラフと、アイテムに関する補足情報を使用してGraph Embeddingを作成します。
Embedding作成時には、アイテムグラフについてランダムウォークを行うことで学習データを生成し、これをSkip-gramでEmbeddingを学習しています。 こうして生成されたEmbeddingに対して、内積による類似度計算を行うことによって、推薦の候補集合を作成しています。
推薦の候補集合に対して、ランキングモデルが別途スコアリングをし、スコア順に並べ替えることでオススメの商品が画面に表示されているようですね。
こちらも、Graph Embeddingを用いてはいますが、YouTube同様Candidate Generationを行った後、それらをオンラインでScoring・Orderingしていることがわかりますね。
Pinterestでも、複雑ではありますが、同様のフローによって推薦が行われています。
特にPinterestではCandidate generationに多様なやり方を取っているようです。 単純にPin (ここでは推薦のフックとなるアイテム) に紐づく他のボードのアイテムについて、ランダムウォークによって推薦候補となるアイテムを選択していくことで、マイナーなアイテムも推薦候補に入りやすくすることを行っていたりします。 また、ユーザーの行動の時系列も考慮しており、同じセッションないでユーザーが行動したアイテムに関する埋め込みが小さくなるように設計されたPin2Vecという仕組みで埋め込みを作成し、それに基づいて候補を選択していたりもします。 その他にもユーザーの所在地によってFilteringしたアイテムを候補に入れたり、画像の類似度や検索クエリに基づく候補を入れたりと、多様な方法を組み合わせてCandidate Generationを行っているようです。
こうして生成された推薦の候補のアイテムに対して、GBDTを使用してアイテムがユーザーに保存されるかの予測に基づいてScoringし、その順でOrderingしているようです。
上記2つとは異なり、複数の方法を組み合わせて推薦の候補集合を作成してはいますが、Candidate Generationを行った後、それらをオンラインでScoring・Orderingしています。 （事業のドメインから異なるので当たり前ですが）内部の実装は各社大きく異なるとはいえ、推薦システムとしての動作の概念フローはだいたいどこも同じようになるんだなと言うことがわかりました。
参考文献
この記事を書くにあたり、下記の文献を参考にさせていただきました。
- Recommender Systems, Not Just Recommender Models | by Even Oldridge | NVIDIA Merlin | Apr, 2022 | Medium
- System Design for Recommendations and Search
- Introduction | Recommendation Systems | Google Developers
- ブルームフィルターの使い道は？ | NHN Cloud Meetup
論文メモ
この記事を書くにあたって読んだ論文のメモはこちら。 （まだ読み終わっていないものもありますが）
- Deep Neural Networks for YouTube Recommendations · Issue #44 · nogawanogawa/paper_memo · GitHub
- Billion-scale Commodity Embedding for E-commerce Recommendation in Alibaba · Issue #43 · nogawanogawa/paper_memo · GitHub
- Related Pins at Pinterest: The Evolution of a Real-World Recommender System · Issue #45 · nogawanogawa/paper_memo · GitHub
感想
情報推薦に関して、推薦モデルに関する文献をよく見かけますが、それを実際にどうやってシステムとして運用しているのかは、意外と文献が見つかりにくかったりします。 今回、その推薦”システム”について勉強してみて、結構スッキリまとまった文献があったので、いろんな会社のシステム構成と見比べて理解を深めてみました。
当然、速度面の要件はサービスによって異なりますし、アイテム数や取り巻くビジネスロジックも大きく異なります。 大事なこととして、こんな感じのこともブログでは書かれています。
But before you get too excited, think hard about whether you need real-time retrieval and ranking, or if batch recommendations will suffice.
System Design for Recommendations and Search
要するに、「リアルタイムでの検索・推薦が本当に必要なのかは、事前に十分に考えてね♡」ってことです。 バッチ推薦で十分なのか、それともリロードや画面遷移の度に都度推論を実行する必要があり、オンラインの検索・推薦を行う必要があるかによって、システムが求められる要件は大きく変わりそうですしね。
今回色々調べて推薦”システム”としての難しさはある程度共通な気がしますし、その難しさに対する対応もなんとなく明らかになった気がするので、今回は満足です。勉強になりました。
