Polynomial Semantic Indexing - tsubosakaの日記

NIPS 2009で発表された論文"Polynomial Semantic Indexing" [1]を読んだ。これは低ランク近似を用いた教師ありの情報検索に関する手法である。

情報検索について

与えられたクエリに関して適当な重みづけをおこなって順位づけして、適切な文章を返却するという問題は古くから研究されている。

オーソドックスな方法としては文章をbag-of-wordsで表して各単語の重みをtf-idfで正規化し、クエリに関しても同様な処理を行いコサイン類似度などの距離尺度を使って最も近い何件かを返すというものがある。この方法の欠点としてはクエリの単語を含まない文章はヒットしないという問題がある。これは各単語が独立であるという仮定を行っているためであり、明らかに誤っている仮定である。

もう一つの方法としては文章-単語行列が低次元の特徴量によって近似する方法である。代表的な方法としてLSI(Latent Semantic Indexing)，pLSA(probabilistic latent semantic analysis)，LDA(Latent Dirichlet Allocation)がある。この手法では各単語は低次元の特徴量によって相互に結びつけられており、独立ではなくなるため単語の関連性などを表すことができる。しかしながら、これらの手法は基本的に教師なし学習による手法であり、ユーザのクリックログなどを用いてフィードバックを行うなどのことはできない。

そこで論文[1]ではLSIの低ランク近似と教師あり学習を合わせた方法について提案している。

Polynomial Semantic Indexing (PSI)

まず、PSIでは文章dとクエリqがR^D上のベクトルとして表現できるとする。ここでDはユニークな単語の数である。クエリと文章の関連性を表す関数をf(q,d)と書く、この値が大きいほど与えられたqに対して文章dが関連性を持つことを意味する。ここでf(q,d)として線形モデルf(q,d)=w^T [q,d]を考える。ここで[q,d]はベクトルq,dを連結したものを表す。このままではクエリと文章に何の関係もないため任意のクエリに対して同じ順序しか得ることができない。そこで多項式表現
$f(q,d) = w^T \Phi^{k} ([q,d])$
を考える。 $\Phi^k(\cdot)$ は任意のk次の項に関するベクトルに対する写像である。これはたとえばk=2のとき
$f(q,d) = \sum_{ij} w_{ij}^1 q_i q_j + \sum_{ij} w_{ij}^2 d_i q_j + \sum_{ij} w_{ij}^3 d_i d_j$
と書ける。ここでq,dのみの項はクエリを固定したときに順位に影響しないため真ん中の項のみを用いた関数を行列形式で書くと
$f(q,d) = q^T W d$
となる。論文[1]ではk=3に関しても議論されているが、この記事ではk=2の場合のみを述べる。k=3のときの重みWの意味は例えば("jagger", "rolling", "stones")のような単語の組には+の重みを与えるが("jagger", "gems" , "stones")には-の重みを与えることを意味する*1。

しかしながら、単純に考えると重み行列WはD*Dの大きさとなり、単語数30000のときに3.4GBのメモリが必要となり、k=3に至っては非現実的な量となる。そこでWを低ランクな2つの行列を用いて近似しようというのが本論文の味噌となっている。具体的にはWをN * D(N << D)行列U,Vを用いて
$\bar{W} = U^T V + I$
と近似する。これをf(q,d)の式に代入すると
$\sum_{i=1}^N (Uq)_i (Vd)_i + q^T d$
となる。ここで第二項のみのときはベクトル空間モデルとなっている。この方法を用いることによるLSIに対する優位性としては

教師あり学習となっているため、事前のデータを用いることが出来る。
クエリと文章を別に扱っているため、クエリと文章が生成される確率分布が違うときにも利用できる。一般にクエリと文章の性質は異なり、極端な例としてはクエリと文章の言語が違うという場合があげられる。
q^T dという項が入っているため低ランクによる近似の結果とベクトル空間モデルの結果をどのような割合で用いるかを自動的に学習することができる。

があげられている。

学習方法

学習方法としては(q(クエリ)、d^+(関連する文章)、d^-(関連しない文章) )の3つ組を教師データとして用い、 $f(q,d^+) > f(q,d^-)$ がなるべく成立するようなパラメータを選ぶ。このことを表す目的関数としてmargin ranking lossを用いる。これは
$\sum_{(q,d^+,d^-)} \max(0 , 1 - f(q,d^+) + f(q,d^-)$
を最小化することに相当する。この関数を最小化する方法としてはSGDを用いる。更新式については論文を参照されたい。

実験

実験ではWikepediaの文章を用いて実験を行っている。文章の関連性としては文章から出ているリンクを用いて評価している。

一つ目の実験では約200万個の英語版のWikipediaの文章に対して、文章-文章検索を行っている。これは文章qに対して、qからリンクが張られている文章を関連するとみなして、与えられた文章に対して関連する文章を見つけられるかという性能を評価している。実験結果としてはTFIDF, QE(Query Expansion), LSI, Margin Ranking Perceptron, Hash Kernelsに対してPSIが高い性能を示している。
また、クエリを文章の一部だけを用いた実験に関してはTF-IDFが大幅に性能が悪くなるのに対し、PSIは高い性能を示している。

二つ目の実験としては約80万文章の日本語Wikipediaを用いた多言語文章検索に関する実験を行っている。具体的には英語版の記事に対して、日本語で検索を行うというタスクである。ひとつの方法としてはクエリの単語を英語に翻訳して、それを用いて検索を行うという方法がある。しかしPSIの場合はqの分布とdの分布を別々に扱えるためクエリ集合は日本語、文章集合は英語というようなデータセットでも扱うことができる。実験の結果では翻訳を介する方法よりもクエリと文章の言語を別のまま扱ったものの方が高い性能を示している。

参考文献

[1] Bing Bai, Jason Weston, David Grangier, Ronan Collobert, Kunihiko Sadamasa, Yanjun Qi and Corinna Cortes, Mehryar Mohri : Polynomial Semantic Indexing , In NIPS 22 , 2009

*1:例えばjaggerというクエリに対して、"rolling", "stones"という単語を含む文章ば関連性が高いと見なせるが"gems", "stones"を含む文章は同じ"stones"を含んでも関連性はおそらく薄い