照合関数が線型である検索モデル一般に適用可能な
レレバンスフィードバック手法
岸田和明
駿河台大学文化情報学部
kishida@surugadai.ac.jp
1.はじめに
情報検索におけるレレバンスフィードバックの手法としてはベクトル空間型モデルにおける Rocchio の手法がよく知られている。これは元の質問ベクトルに適合文献集合中の語の重みの平均を加え，さらに不適合文献集合中の語の重みの平均を差し引くことによって，元のベクトルを修正する方法である[1]。この方法は，原理的には，ベクトル空間モデルにのみ適用可能であり，なおかつ適合／不適合の 2 値での判定にのみ対応している。
それに対して，岸田[2]によって提案されたフィードバック手法は，ベクトル空間型モデルをはじめとする照合関数が線型である検索モデル一般に適用可能であり，なおかつ，文献の適合度が連続的な数値によって与えられた場合に対応した手法である。
この手法の検索性能は Rocchio の手法をわずかに上回ることが実証的に示されている[2]。
本稿の目的は岸田[2]による提案手法の有効性を別の角度から再度検証することにある。すなわち，この手法が確率型検索モデ
ルの一種である Okapi の方法[3]に対しても適用可能であることを日本語テストコレク
ション NTCIR-1 を使用して実証的に確認する。

M 次元空間から si によって構成される N
M ×1次元空間への写像 f : R→ R N ×1 ということになる。特に f を線形写像に限定し，(1)s = f (b) = Ab
Tと す る 。 こ こ で s = ( s1 ,..., sN ) お よ び
b = (b1 ,..., b M ) T で あ り ， A = (aij ) は
N × M の行列である。

2.テイラー展開に基づくレレバンスフィー
ドバック手法2.1 線形写像としての検索モデル
ここでは岸田[2]の提案手法を簡単に説明する。まず，適合度順出力のために検索モデ ル が 文 献 di に 対 し て 与 え る 得 点 を siて(1)式に帰着する[2]。
2.2 フィードバックの目的
得点 si は検索モデルによる文献 di の適合度についての一種の推定値であるが，これに対する真の値を ri と表記する。この値はもちろん未知であるが，レレバンスフィードバックを活用して，ある部分集合 X における ri の値を知ることは可能である。例えば，何らかの方法による第 1 段階の検索結果に対してその利用者が上位 10 件の文献（ i = 1,..., N ），検索質問における語 t j の重みを b j とする（ j = 1,..., M ）。この記号を使えば，検索モデルは b j から構成される

Okapi での検索モデル[3]は，

aij =2.2 xij
12. (0.25 + 0.75 li l ) + xij

および，

b j = x qj log

N − n j + 0.5n j + 0.5(2)(3)と設定した場合の(1)式に相当する。ここで，xij ： di における t j の出現頻度

li = ∑ j =1 xij ：文献長
M

l = N −1 ∑i =1 li ：文献長の平均
Nxqj ：質問における t j の出現頻度
n j ： t j の出現文献数である。なお，Okapi ではパラメータ設定
方法にいくつかの変種があり，(2)式はその1 つである。ベクトル空間モデルも同様に，
aij および b j を適当に設定することによっの適合度を回答したとすれば，この上位 10件を X ，回答された各値を ri として考えることができる。これに対応して(1)式を，(4)
s X = f X (b) = A X bのように書き直す。 A X は X に含まれる n件の文献に関する行ベクトルを A から抽出した n × M 行列であり，同様に s X は X に含まれる文献の得点のみから成る n 次元ベクトルである。
結局，フィードバックの目的とは，~(5)b = arg min φ (r X , f X (b))
b~となるベクトル b を求めることにほかならない。ここで φ は 2 つのベクトル間の距離を測る何らかの関数であり， rX は n 件の文献集合 X に対して利用者が与えた適合度の値から成るベクトルである。
2.3 テイラー展開による解法~(5)式を解くために，まず， f X ( b ) を初期質問ベクトル b のまわりでテイラー展開し，∂ f (b) ~~f X (b ) = f X (b) + X T (b − b) + K∂bとする。次に，(5)式が満たされるように，~f X (b ) が rX に等しくなると仮定する。この仮定の下に(4)式を使うと，結果的に，~(6)
b = b + A −X1 (r X − s X )−1を得る[2]。ここで A X は A X の逆行列を意味するが， A X は正方行列ではないので普A TX = UΛV Tと分解すれば，(6)式を~
b = b + UΛ−1 V T (r X − s X )(7)とかくことができる[2]。これが岸田[2]による提案手法の最終形である。
3.検索実験による実証分析
3.1 分析の目的と使用データ分析の主目的は，岸田[2]による手法が確率型検索モデルの例である Okapi の手法の検索性能を実際に向上させることを確認することにある。同時に，ベクトル空間型モデルに対する適用も試みる。

変換前

変換後

上位ｘ件の文献リスト

通の逆行列ではない。このために特異値分解を利用する。つまり，使用するデータは日本語テストコレクシ
ョン NTCIR-1[4]である。これは学会発表の標題や抄録から成る約 33 万件のレコードから構成されている。今回は No.31〜83 までの 53 件の検索課題を使う。なお，検索課
題は<title>と<description>フィールドのみを用いる（すなわち，「短い検索質問」）。
3.2 実験の手順
実験の手順は次のとおり。
①第 1 次の検索を Okapi(1)〜(3)式と，ベクトル空間モデルで実行する。実行結果をそれぞれ ORGPRB，ORGVEC と表記する。
②各実行結果の上位 n 件の適合／不適合の情報を適合判定ファイルから抽出し，提案手法を実行する。それらの結果をOkapi については TYLPRB，ベクトル空間型については TYLVEC とかく。また，ベクトル空間型に対しては Rocchioの方法も実行し，ROCCHI と表記する。
なお，②でのフィードバックに利用する文
献数は n = 10 ， n = 20 の 2 通りとする。
また，日本語テキストからの語句の自動識別方法は岸田[2]での実験と同じである。
すなわち，機械可読辞書との最長一致で語句を切り出し，その上で隣接する 2 つの語句を複合語として機械的に組み合わせた。
さらに，ベクトル空間型モデルおよびRocchio の方法の詳細についても，岸田[2]での実験と同様である。

マージン

適合文献

不適合文献

図 1 rX の計算方法
3.3 適合判定結果の変換
NTCIR-1 では，適合判定結果を最終的には適合／不適合の 2 値に直して，適合判定ファイルを提供している。したがって，岸田[2]の手法を適用するには，2 値での判定結果を rX に変換しなければならない。その変換法の基本的な考え方を図 1 に示す。
図 1 の左側は変換前の上位 x 件の文献リストであり，第 1 次検索の得点 si の順序で並べられている。このリストを一次関数(8)r$i = Asi + Bによって計算される r$i で並べ替え，すべての適合文献が不適合文献よりも上位に位置づけられるようにする。この r$i を ri の推定値とする。
(8)式のパラメータ A と B は，
11rmax= Asmax+B 11 rmin = Asmin + B(9)の連立方程式の解として求めることができ11る。ここで，rmax と rmin はそれぞれ適合文献集合における ri の最大値と最小値， s1max と1は適合文献集合中における si の最大値
sminと最小値である。(9)式を解くと，111(10)− rmin− s1min )A$ = (rmax) ( smax
111111$B = ( smax rmin − rmax smin ) ( smax − smin ) (11)である。
以上の(9)〜(11)式は適合文献についてのr$i を求めるための方程式にすぎないが，不適合文献に対しても同様に方程式を設定することができる。すなわち，各最大値・最小値をそれぞれ不適合文献における値に置0000換すればよい。これを rmax ，rmin ，smax sminと表記する。
(10)，(11)式中の si についての最大値と最小値は第 1 次の検索結果から自動的に決まる。一方， ri についてはあらかじめ設定しておく必要がある。

まず，ベクトル空間モデルの場合には，照合関数として利用される余弦の性質から，10rmax= 10. および rmin= 0.0 とするのが合理的であろう。次に，例えば「マージン」（図1 参照） rmin − rmax を 0.2 に設定すれば，自10

動的に， rmin = 0.6 および rmax = 0.4 のように決まる。本稿ではこの数値を用いる。
一方，Okapi の場合には， ri の上限と下限を設定するのが難しく，本稿では，101110， rminrmax= 2 × s1max ， rmin= smax= 0.0 とする。Okapi による si は負になる可能性もあるが，ここでは 0.0 を最小値と考えた。
0については第１次の検索結果の si のレrmin
インジ（範囲）の 1/2 を si の最小値に加算したものとする。つまり，
00rmin= min( s1min , smin)
1010+ [max( smax , smax ) − min( smin, smin)] 2である。
3.4 実験結果
NTCIR-1 の 日 本 語 レ コ ー ド の 総 数 は332,918 件，平均文献長（ l ）は 118.0 であった。
各 実 行 結 果 の 平 均 精 度 の 平 均 （ meanaverage precision）を表 1 に示す。まず，第 1 次検索については，Okapi の方法で0.268，ベクトル空間型で 0.228 であり，Okapi の方がわずかに上回った。表 1 では
これらをベースライン（基準）として，フィードバックの各手法が平均精度の平均を増加させた割合を示してある。
全般的には，上位 10 件よりも，上位 20件の適合／不適合の情報を使ったほうが平均精度が高い。次に，Okapi に着目すると，上位 10 件で 0.396，上位 20 件で 0.450 と表 1 各実行結果の Mean Average Precision (53 検索課題)
確率型（Okapi）
ベクトル空間型
ORGPRBTYLPRBORGVECROCCHITYLVEC
第一次検索.268.228(ベースライン).396.376.378
フィードバック(+48.0%)(+65.2%)(+66.3%)
上位 10 文献
.450.434.459
フィードバック(+68.1%)(+90.4%)(+101.6%)
上位 20 文献

いう数値が得られている。これは，ベクトル空間型モデルでの Rocchio の手法をわずかに上回る数値である。このことから岸田[2]の手法を確率型検索モデルに適用する試みはいちおう成功したといえる。
しかしベースラインからの増加率は，Okapi の場合，48.0%と 68.1%にすぎず，ベクトル空間型に岸田[2]の手法を適用した場合の 66.3%，101.6%に劣る。この結果，ベースラインは Okapi のほうが高いにもかかわらず，上位 20 件のフィードバックの結果はベクトル空間型が上回ることになっている。
4.考察とまとめ
今回の実験では 2 値的な適合判定のデータを使って，岸田[2]の提案手法が確率型検索モデルに実際に適用可能であることを示した。しかし，その増加率は，ベクトル空間型モデルに適用した場合に比べて，それほど高くはなかった。この原因としては，r$i の設定方法の問題が考えられる。
もし，利用者から各文献の適合の程度が数値によって与えられれば， ri の推定という操作は不要である。今回の実験では 2 値の適合判定結果のみが使用可能という状況から，この推定が必要になったのにすぎない。しかし，現実的には，適合の程度を合理的に数値に置き換える作業はそれほど容易ではなく，2 値での適合判定のほうがむしろ現実的という状況も多いであろう。とすれば，本稿における ri の推定方法はむしろ本質的な役割を果たすことになる。
本稿のこの方法の重要な点は ri の推定に第一次検索での得点 si を利用していることにある。この結果として si がフィードバック情報の中に含まれてくる。Rocchio の方法では si は使われないので，使用するフィードバック情報という観点からは，この点が岸田[2]の手法と Rocchio の方法との大きな相違ということになる。直感的には，得点 si を使用したほうが望ましい。例えば，適合文献集合中で同程度の重みの平均を持
つ 2 つの語 A，B があったとして，もし語A のほうが得点の高い適合文献により多く出現していたならば，語 A は語 B よりも重要であると予想される。
このように考えると，岸田[2]の方法における ri の推定は，決して便宜的なものではなく，むしろ本質的な役割を担っていることになる。すでに述べたように，今回，Okapi での改善の程度が低かったということはこの ri の推定方法が不十分だった可能性がある。この点の改善が今後の大きな課題である。
謝辞 貴重なテストコレクションを準備され，研究上の使用を許可された学術情報センター（現：国立情報学研究所）の皆様に感謝します。
参照文献[1] Rocchio, J.J. Jr. “Relevance feedback
in information retrieval”. The SMART
Retrieval System: Experiments in
Automatic Document Processing. G.
Salton ed., Englewood Cliffs, New Jersey, Prentice-Hall, 1971, p.313-323.
[2] 岸田和明. “文献の適合度に関する目標値に基づくフィードバック手法”. 『情報処理学会研究報告（2001-FI-61,2001-NL142）』 Vol.2001，No.21，p.189-196(2001).
[3] Robertson, et al. “Okapi at TERC-3”.
Overview of the Third Text Retrieval
Conference (TREC-3) D.K. Harmaned., Gaithersburg, MD, National Institute of Standards and Technology,
1995, p.109-126.
[4] http://research.nii.ac.jp/~ntcadm/index-ja.html