ゼロから始めるランク学習

この記事はランク学習（Learning to Rank） Advent Calendar 2018 - Adventarの1本目の記事です

この記事は何？

「ランク学習」をご存知でしょうか？ランク学習は機械学習の枠組みの１つで、文書の並び順を予測する手法です。
ランク学習について日本語でまとまった資料が少ないので、私の勉強を兼ねてランク学習をざっくりまとめてみたいと思います。

---

「良い」検索結果と「悪い」検索結果

私たちは日常的に検索サービスに触れていると思います。
例えば、Googleやヤフーといったweb検索を使わない日は無いでしょう。
web検索だけでなく、Amazonを始めとしたECサイトで欲しい商品を探したり、食べログで近場のレストランを探したり…と、検索サービスはありとあらゆるところに存在します。

さて、Googleで「任天堂 switch」と検索してみます。（2018/12/2時点の結果）

検索結果の1件目と2件目は任天堂の公式ホームページ、3件目と4件目はAmazonが出てきました。
この検索結果は非常に素晴らしいと思います、公式ホームページが検索結果上位に出るべきですし、AmazonなどのECサイトを出すことでユーザーの購買行動にも繋がります。

…ところで、検索サービスを使っていると、残念な検索結果に出くわすことは無いでしょうか。
例えばAmazonで「任天堂 switch」と検索したところ、なぜか「Switch（字幕版）」というプライムビデオが現れました。

キーワードと関係無い商品が多少検索結果に入っていてもそこまで気になりませんが、予想と全く異なる検索結果が返ってきてビックリすることもあるのではないでしょうか。

---

検索結果・スコア付け

さて、あなたはweb検索サービスを作ることになりました。「良い」検索結果を返すweb検索サービスを作るにはどうしたら良いでしょうか。

検索結果で返すwebページはキーワードとマッチしていないといけません。例えば、「任天堂 switch」というキーワードに対して、少なくとも「任天堂」と「switch」という単語を含むwebページを返すべきでしょう。
ここでは詳しく説明しませんが、この処理は検索エンジンにおけるインデックス処理に対応します。「任天堂」という単語を含むwebページと「switch」という単語を含むwebページをあらかじめ集めておいて、キーワードが投げられたタイミングで両方の単語を含むwebページを返します。

「任天堂」と「switch」が含まれるwebページを集めることはできましたが、検索結果を作るにはこれらのwebページを何かしらの基準で並べないといけません。

「任天堂」と「switch」がwebページの文書にたくさん入っていれば、その文書はキーワードとの関連性が高いと思われるので、高いスコアを付けるのは正しそうです。
この辺りのスコア付けは様々な手法が提案されていますが、TF-IDFやBM25といった手法が有名です。

takuti.me
sonickun.hatenablog.com

---

機械学習によるランキング

ところで、キーワードと文書間の関連性だけ考えていれば良いのでしょうか。
例えば、ECサイトでは関連性も大事だけど、そもそもユーザーが買ってくれそうな商品を検索結果に出さないといけません。食べログのようなサービスでは位置情報も検索結果に反映したいです。

…このように、検索サービスによって「良い」検索結果の考え方は変わりますし、web検索の例でも「webページの登録日」や「リンクのクリックされた回数」などキーワードと文書間の関連性以外の指標も考慮に入れた方が良いかもしれません。

そこで出てくるのが、機械学習によるランキング：ランク学習です。*1

---

例えばweb検索の例を考えます。

webページの特徴量としては「TF-IDFのスコア」「BM25のスコア」「そのページの登録日」「リンクのクリックされた回数」などが考えられるでしょう。

ラベルについては、例えば人手で各キーワードとwebページの組に「検索結果に出るべき→1・出ない方が良い→0」のようにラベルを振ることが考えられます。
とはいえ人手のラベリングは恐ろしく大変なので、既に検索サービスを運用しているならユーザー行動ログを使ってラベリングすることもできるでしょう。

そうして得られた学習データを用いることで、機械学習によるランキングモデルを構築し、ランキングモデルによるスコアを用いて文書を並べることができます。

---

まとめ

この記事では機械学習によるランキング：ランク学習の導入を紹介しました。次の記事では、ランク学習の考え方・ランキングモデルはどのように学習するのかを紹介したいと思います。

*1:ところで、ランク学習が生まれた本当に最初の話・モチベーションって何なのでしょうか。 "Automatic Combination of Multiple Ranked Retrieval Systems", B. T. Bartell, 1994 や、 "Optimizing Search Engines using Clickthrough Data", T. Joachims, 2002ですかね？