libae の高度な使い方として, 関連文書検索,適合性フィードバックを実装してみます.
今までは,単語リストを検索要求として, それに関連する文書を検索してきました. ここでは,文書自体を検索要求として, それに関連する文書を検索する方法を紹介します(*2). キーとなる文書はいくつあっても構いませんので, 文書リストから文書リストを検索することに相当します.
このためには wsh を二度呼ぶ必要があります. 最初の wsh では, キーとなる文書リスト *f に含まれている単語を集計(検索)して 単語リスト *fw を得ます. ここで,検索要求中の単語の重みも計算しておきます. 次の wsh で,単語リスト *fw から文書リスト *r を検索します. これは,今までに説明した wsh の使い方と同じです.
それでは,それぞれの wsh について距離計算式を定義していきましょう. 基本的には,前章で説明した WT_SMART を使います.WT_SMART を,一段目の wsh で使う WT_SMARTAW と, 二段目の wsh で使う WT_SMARTWA に分割します.
一段目用の WT_SMARTAW では, 各々のキー文書中での単語の重みを計算し集計します.
name: WT_SMARTAW 0: 1: 2: wq(t|q) = (1.0 / (1.0 + log(TF(t)/DF(t)))); 3: wd(t|d) = (1.0 + log(TF(t|d))); 4: norm(d) = qlen / log((double)N_wam_d / (double)DF(.|d)); 5:q は単語ではなく文書ですので注意してください. まずパート 2 で,各文書特有のスコアを計算しておきます. ここでは,単語の平均頻度に関するスコアを計算します.
1 + log(TF(t|q)) tf_n(t|q) = --------------------- 1 + log(ave(TF(.|q)))の分母です. パート 3 で, 分子を計算します. 最後にパート 4 で, キーとなる文書数で正規化して, 更に IDF も計算しておきます. 最終的には,単語リスト *fw の各要素の weight には, 対応する単語の検索要求中での重みが計算されています.
二段目の wsh では, 一段目で集計した単語リスト *fw から文書を検索しますから, 今までの wsh の使い方と同じです. ただし,既に検索要求中の単語の重みが計算されていますので, その重みを使うような定義ファイルを作ります.
name: WT_SMARTWA 0: globals double avelen_wa = 0.0; double Slope_wa = 0.0; 1: loop constants { avelen_wa = wam_total_elem_num(wam, dir_d) / (double)N_wam_d; Slope_wa = 0.2; } 2: wq(t|q) = qp->weight; 3: wd(t|d) = (1.0 + log(TF(t|d))); 4: norm(d) = (avelen_wa + Slope_wa * (DF(.|d) - avelen_wa)) * (1.0 + log(TF(.|d)/DF(.|d))); 5:元の WT_SMART と比べると,パート 2 が変更されています.
関連文書検索のプログラム expand.c では,引数にハンドル(コーパス名)とキー 文書列を指定することにします.
for (i = 0; i < flen; i++) { f[i].id = atoi(argv[i+2]); }で検索要求 *f を設定します.
fw = wsh(f, flen, w, WAM_ROW, WT_SMARTAW, &fwlen, NULL, NULL, NULL);で一段目の wsh を呼びます. キーは文書ですので WAM の向きは WAM_ROW となります.
r = wsh(fw, fwlen, w, WAM_COL, WT_SMARTWA, &rlen, NULL, NULL, NULL);で二段目の wsh を呼びます.あとは *r を weight でソートして終わりです. コンパイルして実行してみましょう.
% expand mai94e 12 5.850228 12 txt/94/01/10/044 1.316575 5 txt/94/01/06/059 1.175032 47 txt/94/01/27/063 1.130201 593 txt/94/11/22/044 1.117408 417 txt/94/08/12/042 ...キーとなる文書 12 がちゃんと一位で検索できています.
% expand mai94e 12 15 200 1 2.151449 1 txt/94/01/01/022 1.795000 12 txt/94/01/10/044 1.667835 200 txt/94/04/18/092 1.528860 15 txt/94/01/11/060 0.922251 228 txt/94/05/03/070 0.911233 422 txt/94/08/16/041 0.909685 52 txt/94/01/30/026 ...キー文書を複数個指定してもうまく動いています.
適合性フィードバック(relevance feedback)とは, ユーザとインタラクションしながら 検索結果をブラッシュアップしていく仕組です.
適合性フィードバックは,今まで学んできた msearch2 と expand を組み あわせることで簡単に実装できます.
システムとしては,2. と 4. を実装すればよいわけですが, 4. が少しやっかいです.ここではユーザからの情報は以下の二つになります.
初期検索要求に含まれる単語tの重みをw(t|q)とします. また,正解文書relでのtの重みをw(t|rel)とします. 新たな検索要求q'でのtの重みw(t|q')は, 以下の式で計算するのが一般的です. これは Rocchio の式と呼ばれています[2].
1 w(t|q') = A * w(t|q) + B * --------- \sum_{rel} w(t|rel) relの数A と B は適当な定数です. この式の後半部は,上で学んだ関連文書の検索と全く同じです. 第一段の wsh 呼び出し部がそのまま使えます. 前半部は,msearch2 で既にやりました,と言いたいところですが,msearch2 では文書の検索までやってしまいます. ここで欲しいのは,検索する前の単語リストで, かつ各単語に対して重み weight が計算されたものです. 都合が良いことに, libae にはこのための関数 wsq が用意されています.
wsq(q, *qlen, w, WAM_COL, WT_SMART, NULL);ここで,q は検索単語リストへのポインタで, ユーザが入力した初期検索要求から作られたものです. 詳しくは msearch2.c を参照すると良いでしょう. wsq は指定した類似度定義式のパート 2 までを計算して 結果を *q の各要素の weight に代入します.
あとは前半部の単語リストと後半部の単語リストをマージすれば良いだけです. Rocchioの式を使って weight を合成してください. マージしてできた検索単語リストをキーに第二段の wsh を呼べば検索終了です. 適当なインターフェイスを作って使いやすくしてみましょう.
出来あがった適合性フィードバックプログラムは, キーワード検索(msearch2), 関連文書検索(expand)の機能を含むものになっているはずです. キーワード検索はユーザからのフィードバック(正解文書)がない場合に相当しますし, 関連文書検索はユーザからの初期検索要求が無い場合に相当します. それぞれ試してみて,msearch2 と expand を使った実行結果と比較してみましょう.
「7: AND 検索を実装する」に進む
「5: 複雑な類似度を定義する」に戻る
「1: はじめに」に戻る