Blog
メルカリにおける機械学習による検索のリランキングへの道のり
※本記事は2023年1月1日に公開された記事の翻訳版です。
メルカリのマーケットプレイスにおける商品検索は、お客さまが欲しい物を発見する最も基本的な方法です。この中核となる機能は、テキストマッチングによる情報検索システムによって実現されています。
しかし最近、私たちは自問自答しました。お客さまの検索体験を向上させる、合理的な機械学習ベースのアプローチはあるのだろうか？という疑問が生まれました。メルカリアプリ上のお客さまの行動を、彼らにとってより関連性の高い検索結果についてのヒントとして捉えることはできないでしょうか？学習データにラベルを付け、単体のユーザークリックという行為をもとにした分析の限界を念頭に置きながら、モデルが学習するための、より情報量の多いコンテキストを構築できないでしょうか？ビジネスKPIとの関係を把握するために、どのようにデータラベリングを利用できるでしょうか？
それは、長く、困難で、興味深い旅であり、我々はその過程で多くの教訓を得ました。この記事で紹介した取り組みや開発を通じて、私たちはビジネスのKPIに統計的に有意な変化をもたらしました。今では私たちのモデルは本番環境における「ベストマッチ」（この記事では「おすすめ順」での検索ベストマッチと呼びます）検索フローのトラフィックの100％を処理しています。しかし、これはほんの始まりに過ぎません。
2021年4月時点の検索の実装状況
メルカリでの検索は、Elasticsearchのテキストマッチングをベースとした情報検索システムを利用していました。デフォルトでは、ElasticsearchはOkapi BM25と呼ばれるランキングアルゴリズムを利用しています。BM25アルゴリズムは、与えられたクエリ内のキーワードのうちインデックス内の検索対象となるフィールドにマッチするのはそのうちのいくつかなのかを考慮し、特徴的なマッチや短いフィールドへのマッチがより高い関連性スコアに貢献します。
しかし、メルカリでは検索結果をそのまま提供するのではなく、結果をお客さまに表示する際にはカスタムランキングの手法を採用しています。そのためメルカリでは、BM25をそのまま利用せず、商品の出品時間を重視した独自のランキング関数（Recency Boosting）を定義しています。メルカリでは、ユーザーにとって重要な検索体験を提供するために、検索フローの種類に応じて、マッチしたクエリをさまざまな方法で並べます。例えば、一般的な検索フローとして、「新しく出品された商品」と「ベストマッチ」の2つの項目があります。「ベストマッチ」ランキングでは、類似度スコアの高い、しかし古いアイテムが検索結果の上位に含まれることを避けたいため、Recency Boosting（アイテム/リストがいつ作成されたか）も組み込んでいます。
過去には、お客さまにより良い検索ユーザー体験を提供するために、機械学習によるランキングの試みも数多く行われました。これらの試みの中には、A/Bテストにおいて成功したものもありましたが、これらはビジネスKPIの統計的に有意な改善にはつながりませんでした。
今回のブログでは、メルカリで行われた機械学習技術を応用して検索結果の精度を向上させる取り組みのうち、そのうちのひとつだけに焦点を当てています。この取り組みの焦点は、メルカリで「ベストマッチ」フローと呼ばれる検索動作の改善でした。ここでいう「ベストマッチ」とは、テキストマッチング型情報検索システムのランキング機能によって決定される、クエリと文書の類似度スコアが高いことを意味します。
通常のテキストマッチングシステムの機能をベースに
最近のテキストマッチ型情報検索システムは、全文検索が可能で、高速かつ強力です。また、自然言語処理（NLP）機能を利用して、数値（dense）ベクトルとして表現されたテキスト埋め込みを用いてテキストの言語的内容を把握し、クエリと文書間の意味的類似性の評価に利用できる場合もあります。
強力なシステムではありますが、インデックスされたコンテンツに加え、どのようなシグナル（ユーザー行動から得られる情報）を取得できるかという点ではまだ限界があります。例えばメルカリのお客さまは、検索行動の習慣によって、いくつかの特徴的な利用傾向を見出すことできます。
- どんな商品を買ったり見たりするのが好きなのか
- 検索結果のスクロールをどこまで許容するか
- 提示された検索結果から、実際にプレビューした結果の数
- 商品の詳細を見るときの滞在時間
- その他ビジネス交流など
買い手だけでなく、売り手も売りたい商品の参考価格を決定するために検索を利用します。例えば検索結果で売り切れた商品をチェックして値付けを決めることもあります。
通常のテキストマッチングシステムでは、このような暗黙的・明示的なユーザーシグナルを捉えることができません。これらは、ユーザーが認識する検索結果の関連性やパーソナライズを向上させるための潜在的なシグナルとなり得ます。
情報検索システムが出す検索結果の関連性を高めたい場合、一次検索処理のあとに何らかの後処理を施して、エンドユーザーに表示する項目の順番を最適化する必要があります。これに対するアプローチとして、情報検索／推薦システムで広く使われているのが、機械学習を活用した検索後処理、すなわちリランキング(Re-ranking）です。
これは実はかなり一般的な情報検索システムのアーキテクチャで、テキストマッチングシステム（例：Elasticsearch、Solrなど）から最初の結果セットを取得する第一段階の検索があります。これは「Recall」フェーズであり、「クエリに関連する文書をすべて取得できたか？」という問で表現できます。次に、機械学習によって検索結果の後処理を行うフェーズでRe-rankingを行うわけです。これが「Precision」のフェーズで、「検索された文書から、どの文書が関連性があるか？」という問いかけで表現できます。つまり「精度」のフェーズでは検索結果のうち、よりクエリに対する関連性が高い結果の部分集合を得るプロセスを指します。
Learning-to-Rank – 理論と課題
我々は、LTR（Learning-to-Rank）機械学習アプローチを活用して、インデックスから取得した検索結果に、メルカリユーザーの行動から得られる様々なシグナルを活用した検索後処理を追加することにしました。LTRは機械学習アルゴリズムの一種で、シグナルを用いて検索結果のリランキングを自動的に行う方法を学習する手法です。
Liu（2009）らはLTRを「…学習データを用いてランキングモデルを自動的に構築し、そのモデルが関連性、好み、重要性の度合いに応じて新しいオブジェクトをソートできるようにするタスク」と定義しています[1]
伝統的に、これはスコアリングモデルを生成する教師付き機械学習タスクであり、学習データはクエリとそれぞれの文書結果で構成されます。ある種のランキングロスを最小化する学習段階において、モデルは各入力 x = (q, d)（qはクエリ、dはドキュメント）に対する関連性スコアを予測するように学習します。関連性スコアはクエリに対するドキュメントの関連性の重要度を表します。
メルカリでは各文書の関連性スコアを予測するモデルを構築しました。文書の特徴を1つのスコア値に対応付ける小型の多層パーセプトロンに基づくアーキテクチャをその推論速度から採用しました。また、データを最大限に活用するため、nDCG[5]に近似したリストワイズ手法を利用したロス関数を用いてモデルに学習させました。推論時には、各クエリとドキュメントのペアに対してモデルを実行し、モデルによって与えられたスコアに基づいてドキュメントをソートします。しかし、この取り組みにはまだ解決しなければならないことがいくつもありました。
課題1:データセットラベリング
LTRでは、モデルを学習するためにラベル付けされたデータが必要です。1つの方法として、検索クエリと検索結果のログに手動で明示的なラベルを付け、各項目を人間が判断して関連性スコアを割り当てる方法があります。しかし、想像できるように、これは非常にコストと時間のかかるプロセスであり、十分に良いラベルを生成することが保証されていません（もちろん、アノテーションされたデータセットはそれ自体で価値があり、研究において重要な位置を占めています！）
例えば、アノテーションされたデータセットの限界として、それらは固定しており（すなわち、一度作成されたデータセットは変化しない）、より新鮮な意図を統合することによって関連性の将来の変化を含みません（Lefortierら、2014）[2]。また，アノテーターとユーザーの意見が一致しないことが多いです（Sanderson, 2010）[3]．
また、よりスケーラブルなアプローチとして、メルカリユーザーの検索結果とのインタラクション（行動）から、ユーザーの嗜好を示すような情報を学習する方法があります。この手法に関する詳細と課題もまた後ほど触れます。
課題2：クリックを利用して良いラベルを自動生成する
ユーザーのクリック（検索結果に対する人間の反応）は、ラベルとして使うべき明らかなシグナルの1つですが、残念ながら、ビジネスドメインやデータコーパスによっては、常に最良の選択とは限りません。
ユーザー行動内のノイズ
残念ながら、C2Cのマーケットプレイスにおいて、モデルが何が重要かを学習するのに、クリック数だけでは十分なシグナルとなりえません。一般的に人間は、しばしば予期せぬ理由でクリックをおこなうため、ブラウジングの際に多くの「ノイズ」を発生させるものです。多くの場合、ユーザーは自分が欲しいものがわからず、商品を見たり、ブラウジングするのに多くの時間を費やします。その間、多くの商品がクリックされますが、実際に購入に至る商品はそれほど多くありません。仮にクリックが発生しても、関連性があるから発生したとは限りません。その逆もまた同じで、商品に関連性があるにもかかわらずクリックされないこともよくあります。したがって、モデルはこのようなノイズの多い信号から多くを学ぶことができませんし、仮に学んだとしても、売上に関連するものなど、さまざまなビジネスのKPIに悪影響を与える可能性があります。
もう一つの要因として、botの存在があります。どのようなWebサービスにおいても、自動的なスクレイピング／ボット活動の可能性は存在します。私たちのクライアントログのユーザー活動がボットに起因しているケースは多々あります。しかし、メルカリでは幸いにも膨大なユーザーベースを抱えており、その結果、膨大なクライアントログを利用することができます。そのため、クリックのみを含む検索セッションは学習データから除くという保守的なアプローチをとっています。これにより、私たちのマーケットプレイスで商品を検索し購入するという強い意思を持ったユーザーからモデルを学習させることができ、モデルの品質が向上することがわかりました。
クリック数とバイアス
検索結果に対する人間の行動は、その関連性以外の要因に影響されることがよくあります。例えば、上位にランクされた結果がより注目されるポジション・バイアス（すなわちユーザーインタラクションのデータログ上、注目度が高いためより関連性が高いとみなされるケース）や、表示された検索結果に対する行動に限定されるインタラクション・バイアス、表示結果ごとにユーザーが異なって行動するプレゼンテーション・バイアスなど、ケースは様々です。
ここで少し話を変えて、ポジション・バイアスについてもう少し触れたいと思います。ポジション・バイアスは、選択バイアスと呼ばれる別の問題を引き起こし、モデルが偏りのある時系列データによって効果的にトレーニングされるため、自己強化のフィードバックループによってバイアスが永続化されることになるのです。
さらに具体的に説明しましょう。上位20の検索結果でほとんどのクリックが発生するシナリオを想像してみてください。一定期間のクリックログを収集しキュレーションした場合、モデルはこれらのクリックをラベルとしたデータセットを学習し、オンラインのA/Bテスト経由で評価され、同じクリック位置のバイアスを含む新しいデータで再学習する、というループが発生します。このため、関連性が高いにもかかわらず下位に表示されている商品は、ユーザーエンゲージメントが低いため、順位が上がらない可能性があります。
EコマースのビジネスKPIに対するクリックシグナルの弱さ
実際、クリック数だけを追っていても、モデルが学習するのに十分な情報量を持つシグナルとは言えないかもしれません。もちろん、これはどのようなランキング問題を解決しようとしているかと、情報検索システムのビジネスドメインやデータコーパスによって異なります。例えば、ウェブ検索では、クリック数（とその派生指標であるクリックスルー率）はユーザーエンゲージメントを測るのにも使えるので、ユーザーにとって何が関連しうるかを判断するときに使うには良いシグナルの一つでしょう。しかし、C2Cのマーケットプレイスでは、クリック数だけでは、なぜユーザーが購入するのかをモデル化するのに十分なコンテキストを提供することはできません。
課題3：ラベルのユーザー行動からアイテムの関連性に関する豊富なコンテキストを取得する
ラベルにリッチなコンテキストを提供するために、私たちはユーザーと商品エンゲージメントジャーニーというコンセプトを思いつきました。商品エンゲージメントジャーニーは、ユーザーが商品をクリック（商品詳細のプレビュー）するところから始まります。しかし、クリックした後はどうなるのでしょうか？ユーザーは、その商品に「いいね！」をつけるでしょうか？あるいはコメントするのでしょうか？購入手続きをするのでしょうか？これらの問いを元に、単純な「クリックされた」「クリックされていない」という二値ラベルではなく、「アイテム購入イベント」を商品のエンゲージメント・ジャーニーの最終段階とした、段階的な関連性ラベルをつけることにしました。
メルカリでは、クリックが最も低く、購入が最も高いというように、商品の異なるアクティビティイベントにスコアを割り当てています。そのため、ある商品がクリックされ、「いいね！」を付けられ、その後購入された場合、その商品のラベルは学習データセットの購入イベントのスコアとなりました。
もちろん「段階」の計算方法はさまざまであり、我々のアプローチも決して網羅的ではありません。例えば、別のアプローチとして、異なるイベントのスコアの累積和を最終的なラベルスコアとして割り当て、それを実験することも可能です。ただ最初はシンプルに始めることにして、商品エンゲージメントジャーニーで商品に発生したイベントの中で、最も高いイベントスコアをラベル値として使用しました（商品購入イベントである場合もあれば、そうでない場合もあります）
またデータにラベルを付ける際に、ビジネスKPIとの関係をより明確に把握できるようになり、かつモデルの学習によりリッチなコンテキストを提供できるようになりました。
ここで指摘しておきたいのは「段階的関連性」というコンセプトは、私たちが考え出した斬新なものではない、ということです。情報検索業界では、データにラベルを付ける際に複数の信号を活用することはごく一般的なことです。
課題4：高品質なデータ機能が不可欠
スコアリングするために、モデルにできるだけ多くのデータを与えたいと考えるのが世の常です。私たちはElasticsearchのインデックスからすぐに利用できる特徴量や、日々更新されるFeature Store（Redis）にも特徴量を格納しています。動的な特徴量として、商品のクリックスルー率（CTR）とインプレッション確率（「インプレッション」＝検索結果に表示されたアイテム）であり、これらはランキングモデルに強力なシグナルを提供します。各商品のインプレッション確率は、その商品のインプレッション数を特定期間の全商品のインプレッション数の合計で割ったものと定義されています。これはメルカリのサービスにおけるユーザーの活動が一定でないことを考慮して設計されています。
中でもRecency boostingが特に重要であるため、モデル学習に取り入れられています。Recency（購入日の近さ）は出品イベントと検索クエリの間の時間スパンとして定義されます。この指標を重要視する理由は、C2Cマーケットプレイスでは、商品の価格は出品者によって決定されるからです。そのため、価格が安い（つまり魅力的な買い物ができる）商品は多くの注目を集め、すぐに売れてしまうのです。逆に、適切に値付けされていない商品は、長期間売れ残る傾向があります。言い換えれば、新しく出品された商品はお得な内容である傾向が高いため、お客様も一番に見たいと思う傾向があるのです。
Recency boostingに加えて、検索クエリと商品の意味理解をするためには、クエリと商品のタイトルテキストそのものが重要です。このため、私たちはクエリと商品のタイトルをトークン化し、学習データに含まれる固定長語に対する単語の埋め込みを学習させます。これらの単語埋め込みは特定のクエリや商品タイトルに対して平均化され、集約された埋め込みが入力特徴としてモデルに渡されます。
またニューラルネットワークは最大入力値に影響されやすいため、私たちは入力を対数空間（具体的にはlog1p [6]）に正規化することを選択しました。価格や鮮度などの入力の多くは、歪んだロングテール分布に従うため、対数入力でネットワークを最適化すると、データ中の異常値の影響が少なくなって学習が安定し、全体的な性能が向上することを経験的に発見したのです。
課題5：ビジネスKPIへの貢献度
検索結果にRe-rankingを適用する際、アプリケーションのビジネスドメインも意識した上でリランキングの精度を評価する必要があります。nDCGやCTR（クリックスルー率）といった指標における統計的に有意な改善だけに頼っていては、必ずしもビジネスにおける価値に結びつかないことがよくあります。言い換えれば、Eコマースのビジネス領域におけるリランキングの問題は、検索の関連性の向上がビジネスKPIにも結びつく必要があると同時に、より良いエンドユーザー体験を提供する必要があるため、非常に難しいのです。
一般的なビジネス目標は売上を増やすことなので、最初は売上が明らかな指標であるように思われます。しかし、売上高は分散が大きく、統計的に有意な変化を検出することが難しいため、必ずしもよい指標とは言えません。その代わり、今回のランク付けでは、ユーザーあたりの平均トランザクション数や購入者コンバージョン率（Average Transactions per User/Buyer Conversion Rate）など、分散が小さい購入者指標に焦点を当てました。具体的には、ATPUはアクティブユーザー1人あたりの平均トランザクション数を示しています。収益とは異なり、価格差の影響が排除されているため、分散が低くなっています。したがって、統計的に有意な変化を検出することがより現実的になります。
BCRは、ATPUよりもさらに進んで、実際に何かを購入したアクティブユーザーの数を調べることで、ヘビーバイヤー（高頻度の購入者）とライトバイヤー（低頻度の購入者）の違いから生じるばらつきを取り除いています。この指標は統計的な有意性を測定するために、ATPUよりもさらに使いやすくなっています。最終的にメルカリでは、ATPU/BCRが販売実績の先行指標であり、どれだけのユーザーが当社のサービスから価値を得たかを示すものとなっています。
私たちが得た教訓
1.品質ラベルの定義戦略に時間をかけよう
データのラベル付けを始めるにあたり、私たちはビジネスケースの詳細、つまりモデルが何を達成する必要があるのかをより良く理解し、定義しようとしました。まず、バイナリ（アイテムがクリックされたかどうか）のラベルを実験に使用することで、小さくシンプルにスタートしました。残念ながら、これはモデルが学習できるほど有益な情報量ではなかったため、ビジネスKPIの改善につながるnDCGの増加を観察することはできませんでした。そこで、学習データにどのようなラベルを付けるべきかという仮説を立て、それを繰り返していくうちに、ユーザーと商品のエンゲージメントの関係性の仮説を構築し、モデルにとってより強力なラベルと、より豊かなコンテキストを定義することができるようになりました。
2.nDCGの "死角 "から目を離さない
ランキングの質は一般的にランキングメトリクス、例えば正規化割引累積利得（nDCG）を用いて評価されます。これはLTRモデルがしばしばnDCG損失で学習されることを意味し、学習データセット上の結果をランク付けするために学習する際に、モデルがnDCGを最大化しようとすることを意味します。
LTRモデル（検索結果の事後処理を行う第2フェーズ）のリランキングの精度は、第1フェーズ（検索結果の取得）の出来に大きく依存します。もしインデックスから悪いマッチが得られた場合、たとえモデルがnDCGを最大化し、モデルがうまく機能しているように見えても、ユーザーの観点からは、悪い結果をリランキングし続けるため、よくない検索体験を提供していることになってしまいます。
3.データクリーニングの重要性
ランキングモデルを開発する過程で、私たちは何度もデータに関する問題に直面しました。最も大きな問題は、以下の通りです。
-
極端な異常値が存在すること。例えば、現実的にありえない状況でも最大許容価格である9,999,999円で出品している人は存在します。また、ユーザーが珍しい商品を検索した結果、メルカリのほとんどの商品と比較して非常に古い（つまりRecency boostingのスコアが極端に高い）商品が検索されるような例もあります。突発的に極端な特徴量が現れると、勾配ベースの学習手法が不安定になるため、こうした異常値データを除外することと、ロバストな正規化を選択することの両方を行いました。
-
リランキングについては、すべてのクリックが等価ではないことがわかりました。クライアントのログを見たところ、一部のユーザーは表示された項目の大半を吟味する傾向があることがわかりました。極端な例では、検索結果に表示されたすべての項目をタップしているケースもあります。これでは、機械学習のための関連性ラベルがうまく生成されないのは明らかです。また、ユーザーが数秒おきに毎日同じクエリを送信しているような、ボットのような行動も見受けられました。
重要なことは、ユーザーの真の意図を表すデータサンプルを抽出する必要があるということです。そうでなければ、モデルを学習すること、そして実際に評価することが難しくなります。ノイズの多いデータを使ってモデルを評価しても、モデルについて何もわかりません。
おわりに
我々は、Learning-to-Rank技術の応用という文脈で、以下のような様々な興味深い問題に取り組んでいます。
- Wangら（2016）[4]が初めて紹介したIPS（inverse propensity scoring）を活用し、選択＆学習バイアスの一因となるユーザーのクリックバイアスの対応
- 検索結果のパーソナライゼーションをさらに向上させるインタラクションシグナルの追加活用
- 指数関数的に減衰する段階的関連性ラベルの実験
- 埋め込みに基づくリランキングと密ベクトル検索のためのアプローチをの探索
今後の記事を通して、皆様に私たちの機械学習の旅に参加し、今後これらの問題にともに取り組み、学び、成長することができれば嬉しいです。
参考文献
- Liu, T.. (2009). Rank learning for information retrieval. Foundations and Trends. Information Retrieval. 3. 225-331.
- Lefortier, P. Serdyukov, and M. de Rijke. Online exploration for detecting shifts in fresh intent. In CIKM 2014: 23rd ACM Conference on Information and Knowledge Management. ACM, November 2014.
- Sanderson, Mark. (2010). Test Collection Based Evaluation of Information Retrieval Systems. Foundations and Trends in Information Retrieval. 4. 247-375. 10.1561/1500000009.
- Wang, M. Bendersky, D. Metzler, and M. Najork. Learning to rank with selection bias in personal search. In Proceedings of the 39th International ACM SIGIR conference on Research and Development in Information Retrieval, pages 115–124. ACM, 2016.
- Tao Qin, Tie-Yan Liu, Hang Li. A General Approximation Framework for Direct Optimization of Information Retrieval Measures. October, 2008
- Wang, M. Bendersky, et. al, (2019). TF-Ranking: Scalable TensorFlow Library for Learning-to-Rank. 2970-2978. 10.1145/3292500.3330677.