フードデリバリーの多様な課題に向き合う　出前館の機械学習システム開発の裏側

推薦システムについて

曽弘博氏：では、推薦システムについての解説に入りましょう。こちらでやりたかったことを復習すると、「それぞれのユーザーに対して、そのユーザーの好みに合わせた店舗の推薦リストを提示すること」でした。

このタスクにに関して、ここでは2つの多様性という課題に関してお話をいたしましょう。

1つは推薦リスト全体での店舗の多様性です。ここでいう多様性というのは、「全てのユーザーに対する推薦リストを集めてきたときに、そのリストの集まりの中には十分な種類の店舗がありますか?」という意味での多様性です。

もっと具体的に言うと、「だいたいどのユーザーにも、だいたい似たような店舗を出していませんよね？」という意味での多様性です。

だいたいどのユーザーにもだいたい似たような店舗を出すというのは、加盟店間の公平性という観点から望ましいものではありませんし、「だいたいどのユーザーにも似たような店舗を出す」ような推薦リストは、往々にして人気店に偏ってしまいます。

でも人気店というのは、ランキング見ればわかるわけですので、ここの個別化した推薦という枠でそれを出すのは、あまり望ましいことではありません。

また、もう1つの多様性の課題として、個々の推薦リストにおけるジャンルの多様性が挙げられます。これは「それぞれのユーザーへ出した、1つの推薦リストを考えましょう。その推薦リストの中のジャンルが十分に多様になっていますか？」という意味での多様性です。

もっとわかりやすくいうと、「カレーばかりであったり、寿司ばかりであったり、そんなことになっていませんよね？」という意味での多様性です。

ジャンルが偏ってしまうと、ユーザーとしても飽きてしまいますし、ユーザーの気分の変化にも対応できません。また、ユーザーとしても毎日同じものを食べるのは、健康にもあまりよくないという問題もあります。

さて、これら2つの多様性なのですが、1点注意が必要な点があります。それは、多様性と精度はある程度トレードオフの関係にあるということです。ここでいう精度というのは、「推薦システムが推薦したもののうち、ユーザーがその後実際に買ったものはどれくらいありますか?」という意味での精度です。

この「精度と多様性」のトレードオフに関しては後で触れますのでこの点に注意しながら、この2つの多様性に関して述べていきたいと思います。

推薦リスト全体での店舗の多様性

まずは店舗の多様性についてです。人気店にはより多くの注文のデータがあるので、ナイーブに学習や評価を行うと、人気店のデータの影響が強く出てしまい、店舗の多様性が下がってしまいます。そこで、学習や評価の際にデータをうまくサンプリングして、人気店のバイアスを消す、ということを考えました。

具体的に見ていきましょう。まず評価に当たっては、データを店舗の人気度に反比例した重みに応じてサンプリングします。また学習の際にも類似したサンプリングを行います。学習時のサンプリングでどの程度バイアスを消すかは、ハイパーパラメーターで変更可能になっていて、このハイパーパラメーターを調節することで、多様性と精度のトレードオフを調節することが可能になっています。なお、ハイパーパラメーターの探索と候補の選定に当たっては、Optunaなどのツールを用いました。

なお、このバイアス軽減のためのサンプリングは「今回のシステムのためにイチから実装しましたよ」というわけではなくて、チームで開発したmasalaというフレームワークを利用しています。こちらは2020年のLINE DEVELOPER DAY 2020で話していますので、興味がある方はご覧いただければと思います。

では実際にこのサンプリングしたデータを用いて、評価した結果をお見せしましょう。こちらのグラフ、1個1個の点はモデルに対応しています。ハイパーパラメータの組といってもいいですね。横軸はnDCGという精度を表す指標。縦軸はエントロピーという推薦リスト全体での店舗の多様性を表す指標になっています。いずれも大きいほうが望ましい指標です。ですので、右上にあるモデルほど、いいモデルということになりますね。

そして青いモデルは、このそれぞれの青い点よりも右上にモデルが存在しないという意味で、精度と多様性の良いトレードオフをもつモデルになっています。

ではこの青いモデルのどれを使うかということなのですが、これはオフラインで評価するのは難しいので、ここからいくつかを選んでオンラインテストを行い、そこで例えばコンバージョンレートなどの指標で評価することが望ましいと考えられます。

以上が、全体での店舗の多様性についてでした。

個々の推薦リストにおけるジャンルの多様性

次に個々の推薦リストにおけるジャンルの多様性について考えましょう。推薦問題でよく用いられているembeddingモデル、例えばグラフニューラルネットワークですね、こういったモデルは精度は高いのですが、ジャンルの多様性は低くなりがちなことが知られています。

それに対して共起情報を用いたモデル、例えばPMIモデル（Pointwise Mutual Information model）などですが、こういったモデルはジャンルの多様性は高いのですが、精度はembeddingモデルに比べると下がってしまうことが知られています。

そこで、これら2つのモデルをうまく組み合わせて、精度とジャンルの多様性、どちらも確保しにいこうという試みを行っています。

具体的には、まず共起情報を用いたモデルで店舗の候補をざっと選び、第2段階では、第1段階のスコアも加味しつつ、embeddingモデルを使ってより詳細なランク付けを行うといった手法です。

こちらの手法での実験結果をお見せしましょう。nDCGとエントロピーは先ほどもお話しした指標ですが、そこにIntra List Similarityという指標を新しく加えています。これは、推薦リストの中のジャンルがどれぐらい似ているかを表す指標です。今は似ていないほうがうれしいので、この指標の値は小さいほうがうれしいです。

1行目のGNNはembeddingモデルですが、3行目が、ここにPMIモデルを組み合わせたTwo−stageモデルになっています。1行目と3行目を比べると、Intra List Similarityが下がっている、つまりジャンルの多様性が上がっていることが見て取れます。

またnDCGとエントロピーも上がっています。こちらは考え方の異なるモデルを組み合わせることで全体の精度を上げるという、アンサンブルの効果があるのではないかなと考えられます。

以上、出前館における推薦システム開発の取り組みに関して見てきました。開発に当たっては、2つの多様性という課題があり、全体での店舗の多様性については、店舗の人気度に応じたサンプリング、ジャンルの多様性にはTwo−stageモデルというアプローチを試みています。

料理の準備時間予測

では次のセクションに移りましょう。こちらでは、料理の準備時間予測タスクを考えます。

まず何がやりたかったかを復習しましょう。最終的にやりたかったのは、料理の配達時間を予測することでした。そのうち、図の白枠で囲った部分、料理を注文してから料理の準備ができるまでを予測するのが、料理準備時間予測という、ここで考えるタスクです。

1点注意が必要なのですが、料理の準備時間というのは調理にかかる時間だけではなくて、調理できた料理をパッキングしたり、そういった時間も含めてすべてを準備時間と呼んでいます。

さてこのタスクに取り組むに当たって、いくつかの課題に直面したのですが、今回はそのうち3つについてお話ししたいと思います。

1つ目、「何時何分に料理ができましたよ」というデータが正確に取れていないという問題。2つ目は、店舗やエリアによってはデータが少ない、データが偏っているという問題。3つ目は、予測対象が最新の状況に応じて強く変動するという課題です。

以下では、これら3つの課題のそれぞれに関して、課題の詳細と、それらの課題にどのように取り組んでいるかを1つずつお話ししていきます。

ではまず1つ目。最初の正確なログがないという課題に対してです。そもそも正確なログがないってなんでですか？という話をまずしておきましょう。

出前館では、ドライバーのアプリや加盟店のアプリを、例えば「料理の注文の配達をします」だったり「料理の注文を受け付けました」といったタイミングでドライバーや加盟店のスタッフの方々が操作し、その操作の時刻を記録しています。

なのですが、加盟店のアプリには現在、「何時何分に料理ができました」を記録する、料理ができたタイミングで押すボタンが存在していません。こういったボタンを付けることは可能ですが、店舗の運用上の負担を考えると、あまり望ましくないと考えられます。

そこで今回は、現在実際に取れている2つのタイムスタンプを用いて、料理の準備時間を近似することにしました。

具体的には、まずユーザーが料理を注文した注文時刻。もう1つはドライバーが「店舗で料理を受け取りましたよ」というピックアップ完了時刻。これら2つの時刻の差を、料理の準備時間の近似値として用いることにしました。

ですが、これそのまま使うと大きな問題が2つあります。順に見ていきましょう。

まず1つ目。先程の「ピックアップ完了時刻」が必ずしも本当に料理を受け取った時刻になっていないことがありました。

具体的に見てみましょう。ドライバーは「注文の配達を担当します」というタイミングでタップして、店舗で料理を受け取ったら「受け取った」というボタンをタップして、そして注文の配達が完了したら「配達を完了した」というボタンをタップします。これが本来あるべき、想定されているタップの仕方です。

なのですが、全部のデータがこうなっているわけではなくて、場合によっては、例えば「料理の配達を請け負いました」でタップをするのですが、店舗の受け取りのタイミングで、なんらかの理由でタップをせず、最後に2つのボタンをまとめてタップする、などというデータもありました。

この問題に対しては、GPSのログを利用したデータのクレンジングで対処しました。具体的には、料理受け取りのボタンをタップしたタイミングでのドライバーのGPSのデータを見て、ドライバーの位置が店舗から大きく離れている場合、そのデータを学習データ・評価データから除外しました。

タイムラグの問題

さて、こうやってクレンジングを行ったのですが、まだこのデータ、そのまま使うわけにはいきません。というのも、料理の準備ができてからドライバーが受け取りに来るまで、タイムラグが発生し得るからです。

例えば料理の準備ができてからドライバーが来るまで10分かかったということであれば、ドライバーのピックアップのタイミングは料理の準備完了の時刻より10分遅れているので、ピックアップ完了時刻を、料理の準備が完了した時刻として代用することができません。

この課題に対しても、ドライバーのGPSのログを利用して対処しました。具体的には、データを2つに分けます。

まずケース1、ドライバーが店舗に着いて、そこで料理の受け取りまである程度の時間待った場合です。この場合はある程度待っているわけですので、ドライバーが到着したタイミングでは料理はできていなくて、料理の準備が完了してからドライバーは料理を受け取ったことになります。従って、ピックアップ完了時刻は、料理の準備完了時刻とほぼ等しいものになります。

対してケース2。ドライバーが店舗に着いてすぐに受け取りを完了した場合、つまり店舗で待たなかった場合ですね。この場合は、ドライバーが店舗に到着するよりも前に料理の準備ができているわけなので、ピックアップ完了時刻というのは、料理の準備完了時刻として正確でないものになります。

ケース1のデータだけを用いて学習や評価を行うこともできるのですが、右側のケース2のデータも非常に多数あったので、両方を用いることにしました。ただし、もちろんそのまま混ぜるわけではありません。ここでは損失関数を工夫しました。それを次のスライドで見てみましょう。

まず左のグラフを見てください。横軸は予測値、縦軸はその予測値に対するペナルティです。

今、1つのデータを考えて、そのデータにおいてユーザーが注文してからドライバーがピックアップ完了するまでの時間が5分だったとしましょう。この5分という値が、この縦の破線に対応しています。

これは釈迦に説法かもしれないのですが、機械学習では損失関数の値が一番小さくなるところに予測が来るように学習が進みます。

今仮にこのデータがケース2のデータ、つまり、「ドライバーが店舗で待ちましたよ」というデータだとしましょう。この場合は実際の料理の準備完了時刻も5分ですので、図のオレンジ色のl2損失関数を用います。

この場合、この誤差関数の最小点は5分にきています。先ほど申し上げましたとおり、ドライバーがピックアップを完了するまでにかかった時間の5分が、実際に料理の準備完了までにかかった時間とほぼ等しいわけですので、ここに予測がきてほしい、そういった意図を反映しています。

それに対して、このデータがケース1の場合、ドライバーが店舗で待たなかった場合のものだとしましょう。この場合は、ドライバーがピックアップを完了したのは注文から5分後ですが、実際に料理の準備ができているのは注文から5分よりも前になっているわけです。そこで、このデータに関しては、図の緑色の損失関数を用います。

ここでは、最小点が5分より小さくなっていることに注目してください。これは先ほどいった、「ピックアップよりも料理が準備完了できた時間が早いはずですよね」という直感を反映したものです。

どの程度小さいほうにズラすかというのは、右の式をご覧ください。r’という値を用いて決めています。αは内分点の比を決める値で、これはハイパーパラメータになっています。

また、緑のグラフの左右の非対称性にも着目してください。これは「5分より大きいほうに間違えたら、確実に間違っているので大きめのペナルティを与えよう、でも小さいほうに間違っている場合は、我々は料理ができた正確な時間を知らないので、大目に見てペナルティは小さくしよう」という意図を反映しています。

以上が、料理ができた正確な時刻がわからないという課題に対するアプローチでした。

データの偏りの問題

次に2つ目の課題を考えましょう。地域やエリアによってデータが少ない、データの偏りがあるという問題です。

まず地域の偏りについて、左の地図をご覧ください。ダミーデータになりますが、イメージは伝わるかなということで、これを用いて説明します。

六角形がそれぞれの地域を表していて、色が濃いところが注文数が多い地域、色が薄いところが注文数が少ない地域です。注文数が多い地域は非常に限られていて、だいたいの地域は注文が非常に少ないことが見て取れます。

店舗に関しても同様になっていまして、こちらの右のヒストグラム、横軸はある一定期間での店舗が受け取った注文数、縦軸はその注文数をもつ店舗の数になっています。

ある程度大きい注文数をもつ店舗もあるにはあるのですが、非常に多くの店舗は少ない注文数しか持たないことが見て取れます。

この状況でナイーブにモデルを作ると、多数を占める部分ばかり当てに行くようになったり、また、特徴量を作るための集計において集計値が不安定になったりしてしまうことが起こり得ます。ですので、いくつか工夫が必要になります。それを順に見ていきましょう。

まず、モデルに関して見ておきましょう。このタスクでは、モデルとしてLightGBMを用いることにしました。勾配決定木の実装の1つですね。LightGBMを用いる理由ですが、勾配決定木は複数の決定木を利用して予測を行うのですが、新しい決定木を作る時に、それまで作った決定木たちではうまく予測できないデータ点を重点的に学習します。ですので、ある程度データが少ない店舗に関しても、それなりに予測が安定することが期待されます。

また、予測精度という観点から深層学習系のモデルがよく比較に挙げられるのですが、LightGBMのほうが軽量であり、また、データ数が多くなくてもうまく動くことが知られています。そこで今回LightGBMを用いることにしました。

次に特徴量に関して2つ見ていきましょう。まずはターゲットエンコーディングにスムージングをかけるという話です。そもそもターゲットエンコーディングとは何ぞやといいますと、一言でいうとカテゴリーごとのターゲット(予測対象)の値の平均値です。

もっと具体的にいうと、ここでのカテゴリーは店舗や地域、ターゲットは準備時間ですので、店舗ごと、地域ごとの準備時間の平均値が、ターゲットエンコーディングになっています。

このような特徴量を与えると、モデルはカテゴリーごとの平均値はもうわかっていますので、そのカテゴリーの平均値と個々のインスタンスの差に着目でき、学習がうまくいきやすくなることが知られています。ただし、カテゴリー当たりのデータ数が少ないと、集計値が不安定になってしまうという問題があります。

これに対しては、今回はターゲットエンコーディングにスムージングをかけるという対処をしました。具体的には、カテゴリーごとの平均値と、カテゴリーを問わずに全体で取った平均値、これら2つの平均値の重み付け平均を取りました。

全体の平均値の重みWは、ハイパーパラメータとなっています。このようなスムージングによって、データが少ないカテゴリーに対しても、安定的にターゲットエンコーディングを出せるようになります。

さて、特徴量の2つ目。今度は画像特徴量に関してです。「店舗や地域が異なっていても、似たような商品であれば似たような傾向を示すだろう」というアイデアから画像特徴量を利用することにしました。

具体的には、例えば「カレーは作り置きしてあるから比較的出すのが早いかもしれないけど、ピザは注文を受けてから焼くので時間がかかるかもしれない」といったものです。

ですので、こういったアイテムごとのジャンルのような特徴をモデルに与えることによって、精度が上がるんじゃないかと期待されます。今回は、事前学習済みの深層学習モデルを用いて、商品の画像からembeddingを取得しました。

そして予測対象の注文に含まれている商品のembeddingの平均値を取り、これをLightGBMに与えることにしました。

リアルタイムな状況に強く依存するという課題

では最後の課題の話にまいりましょう。予測したい値が当日の状況に強く依存するという課題です。ここでの「当日の状況」としては、例えば店舗の混雑であったり、その日の店舗にいるスタッフの方々の習熟度などがあり得ます。

今言ったような情報は、さすがにデータとして直接取ることはできないのですが、今回はそれらに連動するような特徴量をリアルタイムで集計し、これをモデルに与えることで、情報を間接的にモデルに伝えることを試みています。

具体的には2つの特徴量を作成しました。順に見ていきましょう。

まず1つ目は、直近n分間でのターゲットエンコーディングです。これは店舗ごと、エリアごと、あとは全国平均も取っています。

この特徴量を与えると、普段と比べて当該店舗/地域が普段と比べてどれくらい忙しいかをモデルに伝えることができます。例えば今ある店舗の直近n分間でのターゲットエンコーディングが、その店舗の過去すべてのデータを見たターゲットエンコーディングの値と比べて大きくなっている場合は「あ、今この店舗は普段に比べて混雑しているんだな」ということがわかります。

もう1つの特徴量としては、これまた直近n分でのドライバーと注文数の比を考えました。これはドライバーが注文に対してどの程度不足しているか、または余裕があるかを表す特徴量になっています。

ドライバーが不足している場合は、なかなか配送を担当するドライバーが決まりませんので、そこで待ち時間がかかります。またドライバー1人で複数の注文を順に配送したりするかもしれず、その場合は、店舗に着くのが遅れてしまうかもしれません。この特徴量は、「そういった遅れが発生しますよ」という情報をモデルに伝えることができます。

さて、今これらの特徴量、リアルタイムで集計すると申し上げたのですが、本番環境で運用し始めると、ある程度集計に遅れが発生することが見込まれます。では、リアルタイムであってほしいこれらの特徴量は、どれぐらい遅れても許容可能なのか、それを本番適用する前に実験しました。

この結果がこちらのグラフになります。横軸は集計の遅れの時間です。縦軸は、その遅れが発生した時の精度指標です。ここではsMAPEと呼ばれる、パーセンテージ誤差指標を用いています。この指標は、値が小さいほうがうれしい指標です。

さて、グラフを見るとすぐにわかるかと思うのですが、集計した値がモデルに渡されるのが遅れるにつれ、つまりグラフが右側にいくにつれ、精度が悪くなる、つまりグラフが上にいくことがわかります。

ここには書いていないのですが、これらのリアルタイムで集計した特徴量を使わない場合のモデルの精度が0.38でしたので、集計した値がモデルに渡されるのがおおよそ15分以上遅れると、これらの特徴量を使わない時よりも、モデルの精度が悪くなってしまいます。逆に15分よりも短い遅れで集計可能になれば、モデルの精度を改善できることが見て取れます。

実際の遅れがどの程度かというと、現在、ストリーミング処理を担当するKSETLチームのご尽力により、おおよそ30秒程度、1分以下で集計が可能になっています。そのため、こちらのリアルタイムの特徴量が、モデルの精度向上に寄与することが期待されます。

以上が、準備時間予測についてでした。ここでは3つの課題、具体的には、料理の準備完了時刻の正確なログが取れない、店舗やエリアによってデータの量に偏りがある、予測すべき時間が最新の状況に強く依存する、という課題と、それらに対する取り組みを見てきました。

機械学習を用いた取り組みでサービス体験の向上を目指す

ではまとめに入りましょう。出前館では現在、サービス刷新のために大規模なシステム改修を行っています。システム改修に当たって機械学習を用いた取り組みを進めていて、これによって出前館を利用するすべての方々にとってのサービス体験の向上を目指しています。

フードデリバリーサービスではユーザー、加盟店、ドライバー、さまざまな方が、さまざまなかたちで相互作用します。そのため、取り組むべき課題も多岐にわたり、そのそれぞれに多様な難しさがあります。これらの難しさに対して我々は特徴量エンジニアリングであったり、ストリーミング処理であったり、多目的最適化であったり、さまざまな技術を用いて対応に当たっています。

今後は継続的な精度改善や、本番にデプロイした後の精度のモニタリング、また必要に応じて新しい機械学習コンポーネントの開発などに取り組んでいきたいと考えています。

以上、ご清聴ありがとうございました。