はじめに
情報検索系トップカンファレンスであるSIGIR2018での「Deep Learning for Matching in Search and Recommendation」というチュートリアルがめちゃくちゃ良かったので、（一部私見や補足も混ぜながら）内容を紹介しようと思います。
ただし、今回は序盤の検索手法が中心で、 推薦手法 と ディープラーニング手法 についてはあまり言及しないので注意してください。
アウトライン
最初にマッチングの観点から検索と推薦を解説した後、検索マッチング手法の変遷を説明していきます。
- Part 0: 検索と推薦におけるマッチング
- Part 1: 伝統的な方法
- Part 2: 深層学習を用いる方法（この記事では簡単な紹介のみ、きちんとした解説はスライドを参照のこと）
Part 0: 検索と推薦におけるマッチング
検索とは
「検索」とはユーザーのリクエストによるプル型の情報提供です。
検索ではユーザーのニーズを「クエリ」から読み取ります。
クエリとは「東京 美味しいお店」などの検索システムに投げる単語（群）のことです。
以下の図は一般的な検索エンジンのシステム構成を示しており、
サーチエンジンがクエリを入力として関連するWebページ等を提示する様子を示しています。
通常、検索システムから提示される情報はあらかじめデータベースにインデックスされています。
（図 p.3, http://www.comp.nus.edu.sg/~xiangnan/sigir18-deep.pdf )
クエリと文書の意味のギャップ
検索では重要な課題として、「クエリと文書（アイテム）の意味のギャップ」が挙げられます。
主に以下の2つの場合があります。
- クエリと文書（内の単語）の「単語表現」は一致しているが、「意味」が一致していない場合
- クエリと文書（内の単語）の「意味」は一致しているが、「単語表現」が一致していない場合
例として以下のようなクエリと文書がそれぞれ、単語表現と意味の（部分）一致を見てみる
| クエリ | 文書 | 単語表現の一致 | 意味の一致 |
|---|---|---|---|
| シアトルの最高なホテル | シアトルの最高なホテル | 完全一致 | 一致 |
| プールのスケジュール | スイミングプールのスケジュール | 部分一致 | 一致 |
| 日本橋 | 日本の橋 | 部分一致 | 不一致 |
| なぜWindowsは高価か | なぜMacは高価か | 部分一致 | 不一致 |
推薦とは
次に推薦について概要を見ていきます。
推薦はユーザーの意図を推定することによるプッシュ型の情報提供です。
推薦ではユーザーの興味を「履歴やデモグラフィック情報等」から読み取ることができます。
以下に示すのは、一般的な推薦システムのシステム構成です。
先ほど見た検索システムと類似した構成ですが、推薦システムではユーザーの情報等を入力として、そのユーザーが興味のあるアイテムをデータベース（Item Corpus）を元に提示します。
（図 p.7 http://www.comp.nus.edu.sg/~xiangnan/sigir18-deep.pdf )
ユーザーとアイテムのギャップ
推薦でも検索と同様、重要な課題として「ユーザーとアイテムの意味のギャップ」が挙げられます。
推薦では、ユーザーとアイテムが異なるタイプのモノであることに加えて、特徴量も異なるため、意味のギャップを埋めることは一般的に検索より困難とされます。
例えば映画推薦の場合、ユーザーとアイテムではそれぞれ以下のような特徴量を持ちます。
- ユーザー
- ユーザーID
- レイティングの履歴
- 年齢、性別、住所
- 収入レベル
- …
- アイテム
- アイテムID
- 説明文
- カテゴリー
- 値段
- パッケージ画像
- …
このようにユーザーとアイテムの間では共通した特徴量がほとんど出てこないため、表面的な特徴量ではマッチングを行うことができないことが課題となります。
検索と推薦
Hectorらの研究（CACM'11）では検索と推薦の情報提供の仕組みを以下のように整理しています。
| 検索 | 推薦 | |
|---|---|---|
| 情報提供モデル | プル | プッシュ |
| ユーザーと情報提供者のどちらが有益（優先）か | ユーザー | ユーザーと提供者 |
| 予想外は良いか | No | Yes |
| 集合知か | たぶん | たぶん |
| クエリは使えるか | Yes | たぶん |
| コンテクストへの依存 | たぶん | たぶん |
Hectorらによれば、検索・推薦に共通したゴールは「クエリとして表出されている／いないに関わらずコンテクストに合った情報（商品、ウェブページなど）を提供すること」です。
一方、両者に異なることは「マッチングに用いる特徴量」です。
以下に、マッチングの観点から検索と推薦を統合した一般的なシステム構成を示します。
(図 p.10 https://www.comp.nus.edu.sg/~xiangnan/sigir18-deep.pdf)
そして、繰り返しになりますが、検索と推薦における最大の課題が「意味のギャップ（Semantic Gap）」です。
以下に検索と推薦での意味のギャップに関する課題例を示します。
検索：クエリ・文書のミスマッチ
検索では語彙のマッチを利用するの方法がいまだに中心です。
例えば、「本」と検索した時に「本当」が引っかかるような検索エンジンが世の中にはゴロゴロあります。
それは、異なるクエリで同じ意味のものを扱うことが難しいためです。
例えば「酒」、「アルコール」、「飲み」という単語はそれぞれお同じような意味を表していますが、異なる表現です。通常、検索者と文書の作者が異なる単語表現を用いるため、文書とクエリのミスマッチが起こります。
推薦：ユーザー・アイテムのギャップ
先に見てきたようにユーザーとアイテムを表現する特徴量はほぼ全て異なっています。
例えば本の推薦を行う場合、ユーザーの情報（年齢、性別、住所など）と本の情報（タイトル、著者、出版年など）は全く違う特徴量です。
また、特徴量が部分的に一致している場合でも、直接マッチングを行うことには意味がありません。
本の推薦を行う場合、ユーザーの名前と本の著者名が一致していることは（興味を持つ人はいるかもしれませんが）一般的に興味を捉えていることにはなりません。
このように推薦ではユーザーとアイテムのギャップを埋めることが困難な課題となります。
マッチングのための機械学習
さて、上記のような検索や推薦を実現するためのに機械学習を用いる方法について、以下に概要を示します。
（図 p.12 http://www.comp.nus.edu.sg/~xiangnan/sigir18-deep.pdf ）
qはクエリ（もしくはユーザー）でdは文書（もしくはアイテム）です。
既存のデータからqとdの関係を学習させたモデルを用いて、新たなq_newとd_newのマッチングの結果（Yes or No、もしくはマッチ度合い）を予測するのが一般的な機械学習手法です。
Part 1: 検索における伝統的なマッチング手法
ここからは検索の伝統的な手法について説明して行きます。
クエリーと文書のマッチングで重要な要素
クエリーと文書のマッチングにおける重要な要素として、 単語間の意味的ギャップを埋めること や 単語の順序を考慮すること が挙げられます。
例えば、単語間の意味的ギャップについては、例えば「パソコン」と「コンピュータ」や、「料理」と「調理」といった異音同義語を扱えることが重要です。
また、単語の順序に関してはN-gramsや、N-termsといった技術を用いることで部分的に対処することもできます。
マッチングとランキングの関係
伝統的な情報検索では ランキング とは マッチング のことでした。つまり、従来ランキングとは「どの程度クエリとアイテムが適合しているか」を持ってランキングを行ってきたことになります。
例えば、BM25という手法（後述）ではクエリと文書のマッチ度を算出してランキングを行います。
しかし、近年のWebサーチではランキングとマッチングは分けて考えられます。
近年のWebサーチにおけるランキングでは マッチング度合いはランキングのための特徴量の一つ です。
以下にマッチングとランキングの違いを表にまとめました。
| マッチング | ランキング | |
|---|---|---|
| 予測するもの | クエリと文書のマッチング度合い | 文書のランキングリスト |
| モデル | f(q, d) | f(q, {d_1, d_2, ...}) |
| 課題 | ミスマッチ | 上位における正しいランキング |
伝統的な検索手法
検索において伝統的なクエリ-文書のマッチング手法は大きく以下の2種類があります。
1. 潜在空間を用いたマッチング手法
潜在空間を用いた検索手法では、クエリと文書を潜在空間に写像（マッピング）し、その中で両者のマッチ度を計算します。
2. 機械翻訳を用いたマッチング手法
機械翻訳によるマッチングでは、文書をクエリ空間に写像（マッピング）します。
簡単に言うと文書をクエリで表し、クエリで表された文書と、実際に入力されたクエリのマッチ度を測ります。
1. 潜在空間を用いたマッチング手法
では、ここからは「潜在空間を用いたマッチング」と「機械翻訳を用いたマッチング」の具体的な手法を紹介していきます。
まずは「潜在空間を用いたマッチング」について紹介して行きます。
（p.22 https://www.comp.nus.edu.sg/~xiangnan/sigir18-deep.pdf ）
単語空間でのマッチング: BM25
潜在空間を用いたマッチングを見ていくと言いましたが、まずは単語空間でのマッチ度を算出する手法であるBM25について紹介します。
クエリと文書をbag of words（BoW）手法を用いて単語空間に写像して、両者の内積をとってマッチ度を算出する方法です。
クエリについてはそのまま 1 or 0 で単語空間に写像し、文書についてはTF-IDFを用いた数式を使って単語間に重みを与えた上で写像します。
以下のような感じです。
（p.23 https://www.comp.nus.edu.sg/~xiangnan/sigir18-deep.pdf）
計算方法の詳細は【技術解説】単語の重要度を測る？TF-IDFとOkapi BM25の計算方法とはが詳しいので参照してください。
潜在空間でのマッチング
潜在空間でのマッチングにおいては以下、2つの仮定があります。
- クエリ・文書は類似点を持っている
- クリックログはクエリと文書間の「類似性」を表す
そして、潜在空間でのマッチングでは、いくつかの正則化ないしは制約のもと、クエリと文書を写像するといったアプローチをとります。
ここでは潜在空間でのマッチング手法としてPLSとRMLSという2つの手法を紹介します。
潜在空間でのマッチング：部分的最小二乗法（Partial Least Square (PLS)）
通常回帰の文脈でよく出てくる手法ですが、検索にも用います。
以下の式において、x と y はそれぞれ ドキュメント と クエリ を表していると考えてください。
あるクエリで一覧に表示されてクリックされたドキュメントについては +1 、クリックされなかったドキュメントについては -1 がつくようにして学習データ（training data）を作っていきます。
（p.25 https://www.comp.nus.edu.sg/~xiangnan/sigir18-deep.pdf）
ここで、潜在空間への写像を行うための関数 L_x と L_y を考えます。
これらの空間に写像した上での内積を計算する式は以下の通りとなります。
（p.25 https://www.comp.nus.edu.sg/~xiangnan/sigir18-deep.pdf ）
そして以下の目的関数（Objective function）を最適化することによって L_x, L_y を求めることができによって、潜在空間に写像した上でのクエリと文書の類似度を求めることができます。
（p.25 https://www.comp.nus.edu.sg/~xiangnan/sigir18-deep.pdf ）
この際、L_x, L_y でどの程度の要素を使うかによって、次元削減をすることもできます。
なお、PLSの手法についてはPartial least squares回帰と画像認識への応用がわかりやすかったです。
潜在空間でのマッチング：正規化潜在空間への写像（Regularized Mapping to Latent Space(RMLS)）
こちらは、PLSとほぼ同様の処理を行うのですが、目的関数においてL1/L2正則化というのを行う手法です。
目的関数は以下のようになります。
（p.26 https://www.comp.nus.edu.sg/~xiangnan/sigir18-deep.pdf ）
L1/L2正則化は簡単に言うと、過学習を抑えつついい感じのモデル（ここでは写像関数=行列）を作るための制約となります。
なお、L1/L2正則化についてはRでL1 / L2正則化を実践するがわかりやすいので、詳しく知りたい方はそちらを参照ください。
PLS v.s. RMLS
PLS と RMLS の違いを表にまとめると以下のようになります。
| PLS | RMLS | |
|---|---|---|
| 変換の前提 | 正規直交系 | L1/L2正則化 |
| 最適化手法 | 特異値分解 | 座標降下法 |
| 最適性 | 全体最適 | 局所最適 |
| 効率性 | 低い | 高い |
| スケーラビリティ | 低い | 高い |
クエリと文書の意味のギャップ再び（潜在空間編）
データから学習した写像関数を用いることによって、クエリや文書を潜在空間に写像することができることを見てきました。
潜在空間モデルを用いることによって、以下2つの利点があります。
- 次元削減を通して、単語レベルのマッチから意味レベルのマッチングを可能にする
- 意味的に類似した用語を相関させることができる
そして、この潜在空間を用いる手法で、従来の手法（例えばBM25）よりもより効果のあるマッチングを行うことができます。以下の表はマッチング手法ごとの効果を示しています。
評価指標であるNDCGについては予測ランキング評価指標：NDCGの2つの定義と特徴の比較を参照してください。
(図 p.29 https://www.comp.nus.edu.sg/~xiangnan/sigir18-deep.pdf)
2. 機械翻訳を用いたマッチング手法
ここまでは潜在空間への写像（マッピング）によるマッチング手法を見てきましたが、ここからは機械翻訳によるマッチング手法を見ていきたいと思います。
統計的機械翻訳とクエリ-文書マッチング
統計的機械翻訳とは、とある元の言語（原言語）で記述された文書Cが与えられた時に、それを目的の言語（目的言語）で記述された文書Eに変換することために統計的な方法を用いる手法です。
これを検索に応用するために、ここでは文書dをクエリqに翻訳（変換）することを考えます。
ここで、 マッチ度を文書dからクエリqへの翻訳確率 P(q|d) と考えることによって、統計的機械翻訳を用いた検索を行うことができます。
検索における翻訳モデルは、原言語と目的言語が同じ という点で通常の翻訳モデルと異なるところに注意です。
機械翻訳によるマッチングを表した概念図は以下のようになります。
文書を何らかの手法でクエリに翻訳して、クエリとのマッチ度を測ることで両者のマッチングを行います。
(図 p.30 https://www.comp.nus.edu.sg/~xiangnan/sigir18-deep.pdf)
単語ベース翻訳モデルによるマッチング：ベーシックモデル
以下のような式でクエリと文書のマッチ度（＝とある文書について特定のクエリへの翻訳確率）を求めます。
マッチ度を求めるために、クエリごとに 文書からクエリへの翻訳確率 を計算してそれらを掛け合わせた値を最終的なマッチ度とするがこのモデルです。
ここで、特定の文書から特定のクエリへの翻訳確率について、
とある文書からとある単語への翻訳確率 と、とある単語からクエリへの翻訳確率 に分解してそれらを文書に出現する単語分足しあげることで求めています。
詳細な式は以下です。
(図 p.33 https://www.comp.nus.edu.sg/~xiangnan/sigir18-deep.pdf)
なお、 P(q|w)を計算するのに以下のような翻訳表を用います。
(図 p.34 https://www.comp.nus.edu.sg/~xiangnan/sigir18-deep.pdf)
単語ベース翻訳モデルによるマッチング：Smoothing to avoid zero translation probability
上記の方法では、ほとんどの単語についてクエリへの翻訳確率が0になってしまうという問題があります。
BergerとLaffertyによって提案された手法では、そもそもの言語としてのクエリの出現確率について重み付き項を加えます。
このことによって、クエリのマッチ度に関する値が0になることを避けることができ、滑らかなマッチングモデルを作っています。
以下のような式になります。
(図 p.33 https://www.comp.nus.edu.sg/~xiangnan/sigir18-deep.pdf)
なお、P(d|C)について論文では1998 Spoken Document Retreival Trackを用いて構築されています。
単語ベース翻訳モデルによるマッチング：Self-translation
上記、BergerとLaffertyによって提案された手法では、単語→クエリの翻訳確率が低くなってしまう問題について取り組みました。
翻訳モデルでは原言語と目的言語が同じ場合、全ての単語はその単語自身へ変換される確率が0より大きいという特徴があります（自己翻訳問題：self-translation problem）。
自単語への翻訳確率が低ければマッチングにおいて低い関連性の原因となり、逆に高ければ翻訳モデルの恩恵を得られないのです。
この自己翻訳問題に対する一つの解として、Gaoらは従来の検索のマッチングモデルと翻訳モデルをバランスさせる手法を提案しました。
この手法では、とあるクエリについて文書に含まれている確率 P(q|D) をβの重み付き項として追加することによって従来の検索のマッチングモデルと翻訳モデルをバランスさせることを可能にしています。なお、P(q|D) は文書にクエリが含まれていない場合は0になり、β=1のときは単純な文書マッチングモデルになります。
(図 p.33 https://www.comp.nus.edu.sg/~xiangnan/sigir18-deep.pdf)
クエリと文書の意味のギャップ再び（機械翻訳モデル編）
機械翻訳モデルではクエリに含まれる単語と文書に含まれる単語の間の意味のギャップを埋めることができました。
今まで見てきた手法について、実験した結果が以下の表です。
単語ベース翻訳モデル（WTM）はベースライン手法（BM25）より効果的であり、自己翻訳を考慮に入れたモデルの方が良いパフォーマンスを発揮します。
(図 p.35 https://www.comp.nus.edu.sg/~xiangnan/sigir18-deep.pdf)
Part 2: 深層学習を用いる方法
ここからは深層学習を用いたマッチング手法を簡単に紹介します。
深層学習では主に以下の2つを学習します。
1. 表現学習
以下のような図で表現することができます。
(図 p.58 https://www.comp.nus.edu.sg/~xiangnan/sigir18-deep.pdf)
まず、クエリや文書を変換するφ(x)を学習し、その後マッチングを行います。
表現学習の手法はDNN、CNN、RNNに基づく手法に大別されます。
それぞれ、以下のような手法が提案されています。
（詳しくは論文見ていただけると。）
DNN
CNN
RNN
2. マッチング関数の学習
マッチング関数の学習については、以下のような図で表現することができます。
(図 p.59 https://www.comp.nus.edu.sg/~xiangnan/sigir18-deep.pdf)
マッチング関数の学習では、クエリと文書の結合（例えば単純な線形結合やマトリックスの作成）を行い、次にそれらを学習させていきマッチング関数を作ります。
マッチング関数の学習については、以下のような手法があります。
単語レベルの類似マトリクス
アテンションモデル
A Decomposable Attention Model for Natural Language Inference(Parikh et al., EMNLP ‘16)
表現学習とマッチング学習を組み合わせる
表現学習とマッチング学習を組み合わせた手法として以下のようなものがあります。
まとめ
検索手法の変遷を追ってきましたが、重要なこととしては以下のポイントになります。
- 検索と推薦はマッチングという観点で同様に捉えることができる
- 従来手法としては主に「潜在空間モデル」と「機械翻訳モデル」がある
- ディープラーニング手法では主に「表現」と「マッチング関数」の学習が行われる
終わりに
検索の手法の変遷を見てきました。
この記事をきっかけとして情報検索に興味を持っていただければ嬉しいと思います。
結構勢いで書いてしまったので、修正等のご指摘あればありがたく思います。