この記事は何？
検索システムに携わっていて、特にクエリ理解のシステムや知識ベースの拡張をやっているときにふと「リコールを上げるだけなら任意の方法で候補を追加していけば達成できるけど、候補の追加は精度に対して下がる方向にしか働かないので、日々検索システムを改善していると思っていたが実は徒らに検索結果をノイジーにしているだけなのでは」と疑問に思うようになり、自分自身を納得させるために情報検索の主にランキングについて調べてみました。
背景と動機
朝起きて天気を調べる、目的地までのルートを確認する、カフェで調べ物をしながらレポートを書く、動画共有サイトで猫の動画を探す、など私たちは意識的に、あるいは無意識的に毎日何かしらの情報を検索しており、今や検索は現代社会において私たちの意思決定の手助けをする欠かせないツールになりました。また検索はユーザーに取ってだけではなく、企業にとっても直接的にエンゲージメントに影響を与えるため重要になってきています。
一方で、情報検索の分野では単一のテキストフィールドで構成された文書の検索が長らく中心的なトピックとして研究されてきましたが、現代の検索アプリでは文書は複数のフィールドで構成され、さらに各フィールドは短いテキスト、キーワードのセット、画像や動画など様々なフォーマットをとるようになっています。これにより情報検索の分野と実世界の問題設定に差が生まれてきましたが、その重要度にも関わらず複雑な構造を持つ文書のランキングモデルについてはまだ十分議論されているとは言えません。
例えばEコマースサイトで以下のような構造を持つ商品の検索を作るとします。
| フィールド | タイプ |
|---|---|
| 商品のタイトル | 短い文字列 |
| 商品の説明文 | やや長めの文字列 |
| 商品の画像 | 画像 |
| 価格 | 数値 |
| レビューのスコア | 数値 |
| 色 | カテゴリー |
| 登録日時 | 日付 |
| ... | ... |
検索エンジンにこれらのフィールドを持つ文書として格納します。「冷蔵庫 安い 黒」のような文字列のクエリが来たら単語に分解して各フィールドに一致する文書をフィルタして、なんらかの方法でソートして表示すればよさそうですね。このように基本的に検索システムは候補生成とランキングの多段構成になっています。候補生成に関してはクエリ拡張や候補拡張など様々な手法が提案されてきて、多くの現場で実際に使われていると思いますが、ランキングはどうでしょうか。
文書のランキングの目的は検索結果の有用性を最大化することです。1977年にRobertsonは与えられた文書セットに対して関連度の確率を高い順にソートしたときに有用性が最大になるというProbability Ranking Principleを提案し、それ以来人々は様々な方法で関連度を推定しようと試みてきました。
従来の単語の出現頻度からランク付けをする手法をProbability Ranking Principleに組み込んだのがBM25系のスコアリング関数で、1980年代に提案されてから長い時間が立ちましたが現在でも最もよく使われている手法だと思います。この方法は主に単語の出現頻度や文書の長さを変数として、人手によって少ないパラメータを調整する (つまり機械学習が必要ではなかった) ことで有用性を最大化しようとしたものでした。この方法はそれらの変数の分布が文書間で有意に異なるようなユースケースで威力を発揮しますが、商品検索の例のように短いテキストフィールドには同じ単語は二度以上出現することは稀で、フィルタ済みの候補間でスコアがほぼフラットになってしまうという問題があります。またこの方法は単語の意味を理解しないので、表記揺れに弱く、「安い」のような曖昧な定義を扱うことができず、あとそもそも画像のような文字情報でないものはスコアリングに反映することができないという問題がありました。
2000年代に入るとインターネット人口が爆発的に増えて、大量の検索ログを用いてフィードバックを行って改善する手法が現実的になり、いわゆるランク学習という分野が発展してきました。この時代にpointwise、pairwise、listwiseなど、どのようなロスを定義してどのように最小化するかや、評価指標とロスの関連性などが活発に議論されました。2013年にはニューラルネットワークをランク学習に応用したモデルDSSMが提案され、それ以降、情報検索はニューラル情報検索時代に突入しました。
Not to break our annual tradition, here's the plot for the % of #NeuralIR papers at SIGIR after updating with #SIGIR2020 full papers. All usual disclaimers apply w.r.t. how you interpret this trend. pic.twitter.com/865A4LVyVb
— Bhaskar Mitra (@UnderdogGeek) July 29, 2020
このままのペースで増え続けると来年のSIGIRの論文のニューラル率は100%を超える
— Student (@rejasupotaro) July 29, 2020
ニューラルランキングモデルはその構造から表現ベースと相互作用ベースのモデルに分けることができます。表現ベースはクエリと文書で別々にベクトルを生成して類似度を計測し、ポジティブなペアの距離を小さくするように学習したモデルです。一方、相互作用ベースのモデルは最初のレイヤーからクエリと文書の特徴を結合するなどして学習させたモデルです。
A Deep Look into Neural Ranking Models for Information Retrieval より
一般的に表現ベースのモデルは、クエリと文書の表現はお互いを知ることなく形成されるという性質上、相互作用ベースのモデルには性能が比べると劣ると言われています。
単一のテキストフィールドを持つ文書のランキングに対しては、局所表現と分散表現の両方を用いようとか、クエリの文脈を理解するためにBERTのようなContextualized Language Modelを使おうなど、様々なモデルが提案されてきましたが、構造化された文書のランキングに対する特にモデリングに焦点をあてたモデルはNRM-Fだけです。一応プロダクト検索などの文脈においては論文が書かれていますが分野自体がまだ黎明期なため単純な表現ベースでやってみたというものや、あるいはドメインに特化していて一般的にどうかという視点からの議論はあまりされてきませんでした。
NRM-Fは初めて構造化された文書をニューラルランキングモデルで扱うためのフレームワークとして提案されました。詳細は省略しますが、コアとなるアイデアはクエリと各フィールドのペアからベクトルを生成してそれらを結合するというものです。
_[An Introduction to Neural Information Retrieval](https://www.microsoft.com/en-us/research/uploads/prod/2017/06/fntir2018-neuralir-mitra.pdf) より_
ちなみにNRM-Fはウェブ検索を想定して設計されています（著者がMicrosoftの研究者のため）。現代ではウェブ検索をゼロから作るぞっていうユースケースよりホテル検索とかジョブ検索とかプロダクト検索みたいなユースケースの方が圧倒的に一般的だと思うのですが、そのような構造化された文書の検索というのは情報検索コミュニティにおいてまだメジャーではありません。
この「対象のオブジェクトが複数のフィールドを持ち、コンテキストに応じてランク付けを行い、リストの有用性の最大化を行う」というのは、情報推薦のコミュニティでは昔から議論されており、私の知りたかったトピック「構造化された文書のランキング」は情報推薦寄りなのではと思うようになりました。実際に推薦と情報検索のモデルを同時に学習させたときにお互いのタスクに対する性能が向上したという論文もあり (Joint Modeling and Optimization of Search and Recommendation)、この二つのタスクは潜在的なコンセプトを共有していると見るのが自然でしょう。
構造化された文書のランキングは伝統的な文書のランキングと情報推薦の中間あたりに位置しているとすると、テキストの表現は情報検索のコミュニティから、構造化された特徴の表現は情報推薦のコミュニティからアイデアを拝借できるのではと思いました。
二つのタスクは似ているとはいえ細かいところで違っていて、検索側の人間から見ると推薦のモデルはそれでいいの？みたいな疑問もあり、お互いの分野の共通点を探っていこうということで実験を行うことにしました。
実験の前に (1): Field-weighted Factorization Machinesについて
推薦においては Factorization Machines をベースにした手法が広く研究されています。FMは以下のように定義されています。
$$
\Phi_{FMs}(w,x) = w_0 + \sum_{i}w_i x_i + \sum_{i,j}x_i x_j \langle v_i,v_j \rangle
$$
$x_i$ がある特徴を表していて $x_ix_j$ が特徴の相互作用の2次の項となります。今回の実験ではNRM-Fと共に以下のように定義される Field-weighted Factorization Machines (FwFM) を用いました。
$$
\Phi_{FwFMs}(w,x) = w_0 + \sum_{i}x_i w_i + \sum_{i,j}x_i x_j \langle v_{i},v_{j} \rangle r_{F(i),F(j)}
$$
FwFMは各相互作用の結び付きの強さは組み合わせによって違うという仮定から、特徴のペアごとに重みを持っているという点でFMとは異なります。この手法を選んだ理由は、その特徴の組み合わせによって振る舞いを変えるべきアイデアがいいなと思った (情報検索においても同じことが言われている) のと実装がシンプルなので解釈しやすく拡張もしやすいと思ったからです。NRM-FとFwFMは以下のように異なるということを留意してください。
| NRM-F | FwFM | |
|---|---|---|
| 1次の項 | 使わない | 使う |
| 相互作用の選択 | クエリとフィールドのペア | 全てのペア |
| 相互作用の表現 | Hadamard Product | Dot Product |
| 相互作用の集約 | 結合 | 和 |
実験の前に (2): 検索アプリのカテゴライズについて
「構造化された文書のランキングと言ってもそもそもホテル検索もジョブ検索もプロダクト検索もレシピ検索も動画検索もウェブ検索も全部目的が違うし最適なアーキテクチャはアプリ次第でしょ」となりそうで、実際そうだと思うのですが、しかしその中でもこの検索アプリはこのような特徴があるのであの手法が使えそう、のような仮定は立てられると思うので、いくつかの項目を列挙してみました。
キーワードマッチ vs. フリーテキストマッチ: ユーザーの入力の視点です。キーワードマッチは「冷蔵庫 安い 黒」のようなユーザーが単語をスペース区切りで入力するような、どちらかというと伝統的な検索アプリです。一方でQAサイトや最近のウェブ検索では「なぜ猫は作業中に邪魔をしてくるのか？」のように、単語のセットではなく質問文に対して応答しなければなりません。前者はクエリはある文書からサンプルされたものと見做すことができ、文脈をあまり持たないと考えると単にAverage PoolingみたいなBag-of-Wordsな手法で十分良い性能が出ることが分かっています (e.g. Semantic Product Search)。後者はクエリと文書がヘテロなので、それらの類似度が関連度のサロゲートである、のような仮定を置いているモデルは性能を出しづらく、Contextualized Language Modelが効きそう、のような方向性で検討できるでしょう。
プレーンな文書 vs. 構造化された文書: 扱う文書のフォーマットの視点です。前のセクションで議論してきたように、主に文書の長さは文字情報のキャプチャのしやすさに影響し、また文書が複数のフィールドを持つ場合はクエリとフィールドはどのように相互作用するのかを考える必要があります。またフィールド間での情報のオーバーラップの量はembeddingを共有するか分けるべきかということも考える手掛かりになると思います。
一般的な話題 vs. ドメイン特化: 扱う文書の中身の視点です。ウェブ検索やQAサイトは神羅万象を扱う必要があるため、ドメインに特化したサービスに比べて語彙が膨大になるので、character-levelの表現の方がメモリ制約をクリアしやすいといったことがありそう。
| 語彙数 | |
|---|---|
| Recipes | 229,559 |
| MS MARCO (ウェブ検索) | 3,213,845 |
| Character Trigram | 26 letters ^ 3 grams = 17,576 |
| 語彙数の比較。Character Trigramを使えばどんなに巨大な語彙でも小さく収まる (ただし精度もそれなりになる)。 |
ランキング vs. リランキング: ランキングを行う空間の視点です。ランキングモデルは全ての文書の中で、リランキングはフィルタされた候補の中で関連度の推測を行います。プロダクションにはパフォーマンスの問題を無視できないのでリランキングモデルとして実装されることが多いと思います。候補生成は一般的には文字情報で行われるので、候補の中の文字情報の関連度がある程度保証されて、さらに上位は第一のランカーのスコアが均一になっていると考えると、リランキングはよりレコメンデーションに近いと言えるかもしれません。
実験
Cookpad UKから英語圏のレシピと検索ログを提供していただき実験を行いました。フィールドはたくさんあったのですが、シンプルにするためにクエリ、レシピタイトル、説明文、材料、そのレシピの公開された国を使ってモデルを学習させました。ちなみに各テキストフィールドの長さは以下のように分布しています。
またほとんどのクエリは1-3単語で構成されていて、ごく稀に "how to cut watermelon" のような質問文のクエリがありましたが、無視できるほど少ないと判断しました。以上のことからこれは「キーワードベースの構造化されたドメイン特化のリランキング」タスクとしてモデルの設計を行いました。
データセットは十分に大きかったのでタイムスタンプで10分割にして、分割された各データをさらにタイムスタンプで学習用と検証用に分割 (それでも1セットは一般的に論文で用いられている量より大きい) することで10個の独立した観測データを得ました。情報検索の評価についてもいろいろあるのですが (Proof By Experimentation? Towards Better IR Research)、なるべくフェアにするために評価指標にはNDCG@20を用いて、多重検定では補正を入れて統計的に有意かを検証しました。ロスには論文でよく用いられるPairwise Cross Entropyを用いました。
_近年の実験設定における評価指標とロス_
仮説
今回の実験では以下の仮説について検証していきます。
- ランキングモデルにおいて特徴の相互作用を学習することは重要である
- 特徴の相互作用をクエリとフィールドに制限することは必ずしも重要ではない
- 文書の特徴単体でもランキングモデルの性能の向上に貢献する
- 相互作用の重要度を計測することは可能か
1. ランキングモデルにおいて特徴の相互作用を学習することは重要である
ある論文では相互作用ベースのモデルは表現ベースのモデルより常に優れているという強い主張をしていたのですが、実験の導入として念の為に以下の3つのモデルの性能を比較しました。
- 表現ベース: クエリとレシピの2つのエンコーダを用いて生成された2つのベクトルのコサイン類似度を比較するモデル。
- 暗黙的な相互作用ベース: クエリとレシピの両方の特徴をフラットに結合して複数の全結合層を重ねたモデル。
- 明示的な相互作用ベース: クエリと各フィールドのペアからベクトルを生成して結合したモデル。NRM-Fをベースにレシピ検索用に簡素にしたもの。
NDCG@20の平均値は以下の通りです。
| Model | NDCG@20 |
|---|---|
| 表現ベース | 0.6376 |
| 暗黙的な相互作用 | 0.6429 |
| 明示的な相互作用 | 0.6483 |
やはり文献で言われているように明示的に表現ベースより相互作用ベースの手法の方が優れていて、相互作用の中でも明示的に学習させる方がいいのかと思ったのですが、boxplotを見ると表現ベースはパフォーマンスの上下激しく、さらに多重検定を行うとこれらのモデルに統計的に有意な差はありませんでした。
| モデルのペア | Tukey's multiple comparisonのp値 |
|---|---|
| 表現ベース vs. 暗黙的な相互作用 | 0.619 |
| 表現ベース vs. 明示的な相互作用 | 0.159 |
| 暗黙的な相互作用 vs. 明示的な相互作用 | 0.616 |
ここで？？？となったのですが、よく考えてみると基本的にニューラルネットワークは全結合層を重ねることで効率はさておき任意の関数が表現できると言われていますし、明示的な相互作用のモデルといってもNRM-FとFwFMでは性能が大きく違いますし、表現ベースのモデルもたぶんMetric Learningの文脈で進化し続けているので、その中から特定の実装を抜き出して「一般的にこのアーキテクチャは強い」とは中々言いづらいのでナンセンスな比較ではと思いました。
もし両者で精度に大きな差がないとすると、表現ベースのモデルはANNが使えてオペレーションがしやすいので、表現ベースのモデルを採用したいということもあると思います。ただこの実験だとなぜか上振れ下振れが大きかったので、どういうときに精度が上下するのかというのも別トピックで調べる必要があると思います。
2. 特徴の相互作用をクエリとフィールドに制限することは必ずしも重要ではない
NRM-Fはクエリとフィールドのペアのみを考慮していますが、一方でレコメンデーションのモデルは通常その特徴がコンテキストがどうかを区別しないので、相互作用を制限することは性能の向上に役立っているのか知りたいと思い、以下のようにNRM-FとFwFMのそれぞれのバリアントを作って比較しました。
- NRM-F (query-field): クエリとフィールドのペアで考慮する (オリジナルの実装)。
- NRM-F (all): クエリを区別しないで全ての特徴の相互作用を考慮する。
- FwFM (all): クエリを区別しないで全ての特徴の相互作用を考慮する (オリジナルの実装)。
- FwFM (query-field): クエリとフィールドのペアで考慮する。
結果はどちらのペアにおいてもクエリとフィールドのペアに制限した方が有意に性能が良かったです。これは情報検索においてはやはりクエリがどのように文書中の特徴と相互作用をするのかというのを学習させるのが良いということを示しているでしょう。
| モデル | NDCG@20 |
|---|---|
| NRM-F (all) | 0.6403 |
| NRM-F (query-field) | 0.6483 |
| FwFM (all) | 0.6616 |
| FwFM (query-field) | 0.6674 |
| モデルのペア | 対応のあるt検定のp値 |
|---|---|
| NRM-F (all) vs. NRM-F (query-field) | 0.0031 |
| FwFM (all) vs. FwFM (query-field) | 0.001 |
またNRM-FよりFwFMの方が性能が良かったですが、これが相互作用の重み、各相互作用の表現、相互作用の集約のどこから来るのかは不明ですが、この実験においては本質ではないので一旦置いておきます。
3. 文書の特徴単体でもランキングモデルの性能の向上に貢献する
NRM-Fでは特徴を単体で与えるとオーバーフィットしてしまうと考えられているからか1次の項を与えないのですが、情報推薦ではそこをあまり気にしていない (本当はそんなことはないと思いますが) のが気になりました。例えば、間接的に人気度のようなものを表現する特徴が文書側にあったとして「iphone (本体)」というクエリに対して以下のような文書をランク付けするとします。
| 商品名 | 人気度 | |
|---|---|---|
| 文書1 | iPhone ... | 0.1 |
| 文書2 | iPhone case ... | 0.9 |
ケースで文書1の方がユーザーの意図に沿っていそうですが、文書2の人気度が明確に高いため文書2が上位に表示される可能性が高くなります。ですが、実際にはモデルは評価指標が高くなるように学習するはずなので、1次の項を与えてもいいのではないかと思いました。そこで次にNRM-FとFwFMの相互作用の選択をちょうど逆にしたバージョンをそれぞれ比較してみました。
| モデルのペア | 対応のあるt検定のp値 |
|---|---|
| NRM-F (2nd) vs. NRM-F (1st + 2nd) | 0.5256 |
| FwFM (2nd) vs. FwFM (1st + 2nd) | 0.0 |
結果は、NRM-Fでは差はありませんでしたが、FwFMでは1次と2次の項の両方を与えた方が有意に性能が良くなりました。
4. 各相互作用の重要度を計測することは可能か
みなさん、海外でお寿司を食べますか？ちなみに英国にはパプリカ寿司というものがあるのですが、これは寿司ですか？
このように「寿司 (タイトル), イギリス (国)」と「寿司 (タイトル), 日本 (国)」はその組み合わせから違う概念になると思うのですが、クエリとフィールドのペアだけを見ているとこの差に気づくことができませんね。そこで全ての特徴の相互作用を調べて重要なものだけを考慮させることはできるかと思い立ちました。
ラッソのcoefを確認したり、FwFMの相互作用の重みをヒートマップにしたりしたのですが、どれもあまりしっくり来ず、今のところFwFMの最後に和を計算する直前のactivationを抽出したdistplotが最もそれっぽく見えました。括弧内はラベルとの相関係数です。
オレンジと青の分布が離れているほど良い特徴だと考えられます。クエリのactivationのラインがピタリと一致していますが、これはあるクエリに対して複数の異なる文書を与えてランク付けを行うというタスクにおいて、クエリ単体だけを見てどの文書がエンゲージするかを当てることはできないという直感に合っています。
まとめ
まだいろいろ検証中なのですが、今持っている実験結果から以下のことが言えるかもしれません。
- ランキングとレコメンデーションは目的を共有しているので情報推薦の新しめの論文を持ってきてモデルをそのまま使ってもある程度良い性能が出るかもしれない。
- リランキングのその検索アプリの特性をうまくモデルに組み込むと性能が良くなるかもしれない。
- クエリとフィールドの相互作用は特に重要と言えそう。
ちなみに、情報推薦においては特徴の重要度を計測して選択するのを人手やるよりはAttentionなどを用いて自動で重要な相互作用を学習させる方がトレンドだと思うのですが、Attentionの解釈性について諸説あるのと、情報検索は自動で学習させる前段階の議論がまず必要だと思ったので、今回は相互作用に焦点を当てた実験を行いました。
相互作用以外にも構造化された文書のランキングは伝統的なランキングとは違った固有の問題、例えば「冷蔵庫 安い 黒」っていうのはそれぞれどのフィールドに係っているの？などがまだまだあるので、情報検索のコミュニティでも盛り上がるといいなと思いました。