LINEの“すべて”のサービスから最適なコンテンツを届ける、推薦システムのアーキテクチャ

LINEサービス横断の新推薦システム

並川淳氏：みなさん、こんにちは。おつかれさまです。本日、この発表がこのホールでの最後の発表になります。「Building a smart recommender system across LINE services」というタイトルで、LINEの機械学習エンジニアの並川が発表したいと思います。フェローという、役員のようでエンジニアという不思議な肩書きの役職もつとめさせてもらってます。

今日のお話は、タイトルにあるとおり、LINEにあるさまざまなサービスを横断して、統一的な推薦を行うためのシステムについての話になります。

最初に、今日お話しするシステムを開発するに至った背景について説明したいと思います。

LINEには中心となるメッセンジャーアプリを筆頭に、様々なサービスが存在します。それらのサービスの中には、LINEスタンプ、ニュース、マンガなど、大量のコンテンツを持っているものも少なくありません。このような場合、単純にコンテンツを並べるだけではユーザが自分に必要なコンテンツに辿り着くことは困難です。そのため、レコメンデーションのような仕組みを使ってユーザに必要な情報を届ける必要があり、LINEではこれまで各サービスでレコメンデーションの機能を実現し提供してきました。

しかし、仮に各サービスのページ、アプリに行けば欲しい情報が見つかるとしても、もはやこれだけサービスが多くなると、各サービスのページを巡るだけでも一苦労ですよね？　あるサービスに自分にとって欲しい情報が追加されても、多くのサービスがあると気づくことが難しい。とくに時間が経てば価値を失うような情報であれば尚更です。

なので、サービスの中のコンテンツをおすすめするだけではなく、もちろんサービスだけをオススメするわけでもなく、サービスを横断してサービス×コンテンツで推薦をしてほしい。そういう発想になってくるわけです。

「Smart Channnel」のコンセプト

そこで最近、LINE のトークタブの一番上にコンテンツを表示するようになっています。右の画像の赤枠の部分です。

この会場の中にも、ここにコンテンツが表示されているのに気がついた方もいると思うんですけど、最初はここには天気などのごく限られたコンテンツが表示されていましたが、もう今ではマンガとか占いとかスタンプ、ニュースなど、さまざまなコンテンツが表示されるようになっています。

そして、例えばスタンプならスタンプショップ、ニュース記事はLINE NEWS、マンガはLINEマンガなど、コンテンツそのものは各サービスが持っているわけです。そしてチャットタブの表示枠はたった1つなので、それら全く違うサービスの全く異なるコンテンツの中から1つ選んで表示する必要があるわけです。それをどうやっているのでしょうか？

こちらがコンテンツをユーザーの下に届けるまでの流れを描いた概念図になります。

見ていただければわかると思うんですけど、要するに各サービスからコンテンツを集めてきて、それらからユーザーが必要とするだろうコンテンツを選び出す中央集権的なシステムが存在します。

原理的には、各サービスがそれぞれ自分たちの最適化のロジックに基づいて独立にトークタブにコンテンツを表示することも可能です。技術的には可能なんですけど、ユーザーにとって一番好ましい情報を届けようと思った場合には、いったん中央にコンテンツを集約して、その中からユーザーにとって最も望まれるであろうコンテンツを選ぶ必要があると我々は考えました。

そして、この中央部分のシステムが、今日お話ししたいサービス横断でコンテンツを推薦する推薦システムになります。

グラフで振り返る「Smart Channel」の歴史

推薦システムの詳細に入る前に、Smart Channelの歴史といいますか、どういう歩みだったのかをグラフをもとに説明させてください。

このグラフは、Smart Channelがユーザーに初めて表示されてから、Dailyの数値の時系列になっています。横軸が時間ですね。

縦軸は、青色がインプレッションで、ユーザーにコンテンツが表示された1日あたりの回数になっています。緑色が我々が「Score」と呼んでいる数値で、「クリック」と「バツボタンを押してミュートした」という値の比になっています。

このScoreという緑色の数値がどういう意味かというと、クリックは当然コンテンツに興味があるからクリックするわけでポジティブなアクションで、一方、バツボタンを押して消すのは「見たくない」ということを意味するので、こっちはネガティブな評価だと。

なので、このScoreという緑色の値は高ければ高いほどポジティブな反応がユーザーから得られたという値になっています。なので、この緑色の数値は大きければ大きいほどいいわけです。

今日とくにフォーカスするのは、この緑色の部分が大きく上がっていった部分のところです。この時期に我々がどういう取り組みをしたのかという話になります。

一方で、青色のインプレッションを増やすほうでも、これを増やすためには表示できるコンテンツの種類を増やしたり、そのためにサービス連携など開発や企画を進める必要があったので、ここはここでいろいろとおもしろい物語があるんですけど、そちらは別の発表に譲って、今日の僕の発表では、緑色のScoreという数字、ユーザーの満足度を上げる施策をたくさんやった話に絞ってご紹介したいと思います。

システム開発における3つの制約条件

それでは、まず推薦システムのアーキテクチャについてご紹介します。

今日お話しするのはマシンラーニングのシステムの話なんですけど、マシンラーニングであろうがなんであろうが、システムであれば、まずどういうものを作る必要があるのか、例えば「制約条件は何か？」などを最初に考えなければいけないのは、他のシステム開発と一緒です。なので、当然我々も今回のシステムを開発するにあたって必要条件、制約条件を最初に考えました。

今回のシステムでとくに考えるべき項目は次の3つでした。1つ目は、すでに存在する各サービスの推薦システムとどのように連携するか。2つ目が、LINEでは常に問題になるスケーラビリティの問題。3つ目は、推薦システムについて詳しくない方は聞いたことがないかもしれないですけど、コールドスタート問題と呼ばれている問題です。まずそれぞれについて説明していきたいと思います。

最初のほうにも話したように、LINEのサービスにはすでに推薦システムが存在するものが数多くあります。ここに載せてあるサービスはあくまで一例で、少なくともこれらについてはもう推薦システムがあって、それによってコンテンツが選ばれて表示されています。

この画面のキャプチャはその一例で、赤枠の中で個人単位で推薦されたニュース記事が表示されていたり、スタンプショップに行けば「あなたへのおすすめ」で、あなたに合ったスタンプが推薦されています。

これら異なるサービスではそれぞれ異なる推薦システムが動いています。それは単純に実装が違うだけの場合もあれば、使っているアルゴリズムが違う場合もあります。単純に協調フィルタリングを使っているだけのケースもあれば、画像や文章の類似度で推薦しているケースもありますし、ユーザーの行動ログと画像解析などをディープラーニングを使って組み合わせて推薦しているケースもあります。いろいろな手法が使われています。

そして目的もさまざまで、あるサービスではCTRの向上を目的にしていますし、別のサービスでは売上を向上させようとしています。なので、目的も違います。

今回、最初に考えるべきだったのは、こういったLINEのレコメンデーションの資産をすべて無視して完全にゼロから開発をスタートするのか、それとも利用できる部分は利用するのか、どっちがいいのかという点でした。

2つ目に考慮すべき点はスケーラビリティです。ここに載せてある数字はSmart Channelにおける最近の実績値なんですけど、だいたいインプレッションが1日あたり5億件あって、1日あたりのDAUがグローバルで1億以上あって、推薦すべき新規コンテンツが1日あたり6万件以上追加されてくるような状態になっています。

このような数値は実は開発前から見積もることができていたので、私たちはこの規模を処理できるように推薦システムを設計する必要がありました。

そして3つ目です。すごく挑戦的な文章が書いてあるんですけど、これは要するに、表示するコンテンツは、新しければ新しいほどよいということです。

これはどういうことかというと、Smart Channelはトークタブの一番上に表示されます。トークタブの一番上はすごく大事な場所ですし、そもそも古くても価値を失わない情報は各アプリのところに行ったときに表示されていれば、それで十分なわけです。なので、あのような大事な場所でわざわざ表示する以上、それは時間が経つと価値を失うような情報である必要がある。そうでなければ意味がないわけです。なので、当然新しいコンテンツ、新しい情報を表示する必要があります。

ただ一方で、新しいコンテンツを推薦するのは推薦システム側から見ると難しい問題を含んでいるんですね。それがコールドスタート問題と呼ばれています。

これはどういうことかというと、マシンラーニングは一般にデータがたくさんあるとうまく動きやすいものなんですけど、新しいコンテンツは基本的に誰もほとんど見ていないので、推薦アルゴリズムを作る上で重要なデータソースの1つであるユーザーの行動ログ・行動パターンが不足している状態なわけです。

今回作るシステムはこの新しいコンテンツをうまく表示できる必要があるので、このような行動ログ・行動パターンが不足している状態であってもうまく推薦できる必要があります。

推薦システムのアーキテクチャ

ここまで考慮すべき点を3つほど紹介したので、そういった点を踏まえて我々がどのようなシステムを作ることにしたのかを紹介したいと思います。まず最初にシステム全体の構成図を説明していきたいと思います。

図の一番左にあるのが、各サービスの推薦システムですね。ここにこれが書いてあるということは、我々は今回、各サービスの推薦システムをそのまま再利用することにしたことを意味します。

システムがどう挙動するかというと、まず各推薦システムから各ユーザーごとに上位○件の推薦アイテムを取り出し、中央のキャッシュするシステムに取り込みます。

そして、一番右下のLINE appから推薦アイテムが必要というリクエストが来たら、Rankerが各ユーザに対する上位○個の推薦リストをキャッシュから読み出し、そこから最もユーザに好まれそうなアイテムを一つ選んでLINE appに返します。

そして、LINE appから得られたユーザの行動ログを使ってTrainerが学習し、モデルパラメータを更新してRankerに返す。このようにして、各サービスから送られて来た推薦アイテムリストを定期的に受け取りつつ、その中からサービス横断で一番良いアイテムを選べるように学習し続けるようなシステムになっています。

そして、ここにあるTrainerとRankerが今回のサービス横断の推薦システムの肝になる部分です。次のスライドからはその部分に焦点を当てて説明したいと思います。

探索・活用をハイブリッドにこなすアルゴリズムを採用

まず最初にRanker。コンテンツを選ぶ部分ですね。Rankerはリクエストを受けるたびに表示可能なアイテムのリストそれぞれに対して、その予測スコアといいますか、どれぐらいユーザーに好まれるかを予測します。

この表示可能なアイテムは当然ユーザーごとに異なりますし、当然どういうものが好きかもユーザーごとに違うので、この予測スコアの計算はリクエストのたびに実行されます。そしてRankerは一番大きなスコアをつけたアイテムを選んで返します。

この計算なんですけど、アルゴリズムとしてはContextual Banditと呼ばれるバンディットアルゴリズムを使って計算しています。

先ほどシステムの要件のところで説明したように、このシステムで推薦したいものは基本的に新しいものです。なので、データが十分にたまってないことは前提として織り込んでいる必要があります。

なので、予測されるスコアが正しくないケースはけっこうあるんですね。でも、ユーザーに表示してアクション……クリックなりバツボタンを押されるなり、無視されるなりを繰り返さない限りはデータはたまらないので、「データを取得して予測精度を上げること」と「一番良いアイテムを選ぶこと」の2つを同時にやる必要があります。

これを探索と活用と言ったりもするんですけど、この探索と活用をちょうどよいバランスで行って、結果的にユーザーに一番良いコンテンツを多く届けることができるのがバンディットアルゴリズムと呼ばれるものです。ここではバンディットアルゴリズムの中でもContextual Banditと呼ばれるアルゴリズムを使っています。

バンディットアルゴリズムの具体的なモデル

次はバンディットアルゴリズムで使っている具体的なモデルについて説明します。現在、ここでは我々はBayesian Factorization Machineというものを使っています。

まず最初に「Bayesian」がついていないFactorization Machineについて説明させていただくと、Factorization Machineは、入力とした特徴量の相互作用をうまく計算できるモデルです。例えば特徴量として年齢と性別が入ってきた時に年齢と性別のAND条件をうまく表現できるようなモデルです。

そのFactorization Machineをバンディットアルゴリズムで使えるようにするために拡張したのがBayesian Factorization Machineになります。

当然、モデルがあっても入力としての特徴量がなければうまく動かないので、特徴量の説明もします。使っている特徴量は大きく分けて3つあります。

1つは、ユーザーとアイテムの埋め込みベクトルのdot productを取ったものになります。これはどういう意味かというと、ユーザー単位×アイテム単位の情報を使って特徴を計算することを意味しています。この部分で何ができるかというと、「あるユーザーがあるコンテンツを好きか・嫌いか」みたいなものをユーザー単位×コンテンツ単位で詳細にパーソナライズして計算することができます。

2つ目が、User Featureと書いてあって、ここではLINE社内で保有している推定された年齢や性別などの属性が入ります。

3つ目は、その他のFeatureで、例えば現在時刻のようなものが1時間単位でone hot encodingされた値が入ってきます。

モデルの出力はどのようにエンコードされているかというと、インプレッションが0.5で、クリックが1.0で、バツボタンでミュートされたときに0.0になるようにしています。つまりクリックされると予測したときには大きな値を、バツボタンを押されると予測したときには小さな値を出力するようなモデルです。

次はこのモデルのパラメータをどのようにシステムで学習しているのかという説明に入りたいと思います。

こちらがその学習側のシステム構成になります。ここで何をやっているかというと、まず上のTrainerという部分を見てもらいたいんですけど、LINEはすごくトラフィックが多いので、マシンラーニングも並列化しなければ到底計算できないような規模のデータが来ます。

なので、複数のノードを使って複数のプロセスでモデルを学習していくわけなんですけれども、バラバラに学習した結果がバラバラなままだと、並列に計算した意味がぜんぜんないので、どこかで1つにまとめる必要があるんですね。そうしないと学習を並列化できたことになりません。

そのまとめる部分の処理をParameter Serverと呼ばれるシステムが担っています。各Trainerは独立して学習した後、その学習したパラメータの差分をParameter Serverに送ります。Parameter Serverはその差分と、自分が持っているパラメータを上手く混ぜ合わせてパラメータを更新します。

あとはRankerと呼ばれる実際にランキングを計算するシステムも、定期的にParameter Serverにパラメータを問い合わせ、その取得したパラメータでランキングの計算をするようなシステムになっています。

並列化のアルゴリズム

Parameter Serverの話を先ほどしたんですけど、ここでは少し踏み込んで、並列化のアルゴリズムについて少しだけ紹介します。ここでは数式も少し使ったりもするんですけど、雰囲気だけわかれば十分なので、気楽に聞いていただければと思います。

まず、左の図を見ていただきたいです。3本の横に向かった線が書いてあるんですけど、これは何を意味しているかというと、真ん中がParameter Serverで上と下がTrainer A・Trainer BというTrainerが2つ存在するケースの時間的な流れを表現しています。

この絵はどういうシチュエーションを描いているかというと、最初にTrainer AがParameter Serverからパラメータを受け取って、しばらく学習して学習がある程度進んだので、そのパラメータの差分をParameter Serverに送って、パラメータをまたもらっているんですけど、その一連の作業の間にTrainer BはParameter Serverと複数回やりとりしてるんですね。

どうしてそういうことが起こるかというと、一例としては、Trainer Bのほうが計算が速いことや、Trainer Bにたくさんのログが届いたことや、いろいろな条件によって学習が進む速さは当然プロセスごとに変わってくるためです。

このような並列学習は非同期型の学習と呼ばれます。一方で同期型の学習というのもあって、機械学習の観点では同期型の方が精度を出しやすい、と言われています。それでは、なぜ非同期型を考えているかというと、今回はオンライン学習のシステムなので、どのモデルにたくさんのデータが到達するのかが事前に読めないんですね。

なぜかというと、バンディットアルゴリズムによってどのモデルが適用されるかは動的に変わってくるので、事前にデータの量を見積もることができない。そのような場合にスループットを十分に満たすためには非同期型の学習をする必要があります。

非同期型の学習をすると、この例のような、Trainer Aはせっかく学習したんだけど、その間にParameter Serverは他のTrainerとたくさんやりとりして学習が進んでしまって、せっかく学習結果を送った頃には、すでにそのデータは古くてなんの役にも立たないという状況が発生します。

そういう状況ではどうするか？　データを捨ててしまうのは1つの手なんですけど、そうするとデータがもったいない。なんとかしてこの古くなった学習結果が使えないか？　そう考えるわけです。

データを完全に捨てることなく処理

そのような事態に対処するための数式の一つがこれです。この式は2つの要素によって構成されています。

1つ目がこの緑色で囲った部分で、これが減速のパラメータです。これは何をやっているかというと、「Parameter Serverが現在持っているパラメータ」と「Trainerが過去にParameter Serverから受け取ったパラメータ」の差が大きければ大きいほど減速して、パラメータの更新量の適用を小さくしています。

実際にはデータが、その差分が古くなっているので、それをそのまま適用すると学習が変な方向に向かって壊れちゃうかもしれない。なので、差分を適用する大きさを減らすことでその危険性を減らす。そのような効果を持つのがこの緑色の項になります。

2つ目がこのBacktrackと書いている部分で、これは何をやっているかというと、Parameter Serverが持っているパラメータを少しだけ昔に戻すような項になっています。

これはどういう意味かというと、Trainer Aが学習したときのシチュエーションは古いわけですよ。それがちゃんと適用できるかどうかは、Trainer Aが学習したシチュエーションに近づければ近づけるほど当然うまく適用できるわけです。完全に戻すわけじゃないんですけど、Trainer Aが学習したときのパラメータに少しだけ戻してあげることで、学習が壊れないようにしてうまく混ぜ合わせる。そういう機能を持っているのがこの青色の部分です。

この2つの項をうまく組み合わせることによって、非同期で学習していても、データを完全に捨てることなく取り込むことができます。

ただし、このような工夫をすると学習はできるんですけど、減速するのもBacktrackするのも学習を遅くする性質を持っています。なので、なるべく必要がなければやらなくて済むように、今度はエンジニアリング的な手法で、ロードバランサーをうまく組んで、同じモデルの同じデータはなるべく同じプロセスにいくように処理することで、データが押し寄せてきて並列化しなければ処理が間に合わなくなるその時まで、なるべく並列化を遅延させるようにしてます。

このスライドがMLアーキテクチャについては最後のスライドになります。ここでは最後にモデルパラメータをどのようにストレージに保存しているかを説明しています。

モデルのパラメータは大きく分類して3種類あるんですね。1つはBayesian Factorization Machineのパラメータ。2つ目はアイテムのEmbedding。3つ目がユーザーのEmbeddingになります。

このうちBayesian Factorization MachineのパラメータとItem EmbeddingはParameter Serverを経由してRedisのようなストレージに保存しています。一方、ユーザーのEmbeddingだけはParameter Serverを介さずに直接ストレージで読み書きしていて。

これなぜかというと、LINEではユーザーがグローバルで1億を超えるような状況でして、User Embeddingは当然ユーザーの数だけベクトルを持っていることになるので、サイズがとても大きいのでキャッシュを持つのが難しいことがまず1つあります。

もう1つは、BayesianのモデルやItem Embeddingは複数のノードで計算されることが多いんですけど、ユーザーのEmbeddingは滅多なことでは同時に複数のノードで計算されることはないですし、仮にそういうケースがあったとしても確率的に非常にまれなので、そこでロスがあっても統計的に無視できる。

なので、スループットの向上と学習の精度を天秤にかけて、このようなシステム構成を我々は採用しています。