6  関連文書検索,適合性フィードバックを実装する

libae の高度な使い方として, 関連文書検索,適合性フィードバックを実装してみます.

6.1 関連文書検索の実装

今までは,単語リストを検索要求として, それに関連する文書を検索してきました. ここでは,文書自体を検索要求として, それに関連する文書を検索する方法を紹介します(*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
        ...
キー文書を複数個指定してもうまく動いています.

6.2 適合性フィードバックの実装

適合性フィードバック(relevance feedback)とは, ユーザとインタラクションしながら 検索結果をブラッシュアップしていく仕組です.

  1. ユーザ: まず,文章(またはキーワード)で検索要求を入力します.
  2. システム: 検索要求に対して検索を行います.
  3. ユーザ: 検索結果をながめ, 自分の検索要求に合う(適合する)文書をチェックします.
  4. システム: チェックされた文書を使って検索要求を更新します.
  5. 2.に戻る.

適合性フィードバックは,今まで学んできた 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 を使った実行結果と比較してみましょう.

6.3 応用問題

  1. 本章で説明した適合性フィードバックでは, 正解文書のフィードバックのみあつかいました. 不正解文書もフィードバックできるようプログラムを 拡張してみましょう.文献[2]が参考になるでしょう.
  2. 本章での関連文書検索は同じコーパス内での検索でした. つまり,検索要求の文書も検索結果も同じコーパスの文書です. これを異なるコーパス間の検索に拡張してみましょう. 例えば, 新聞コーパスで指定した記事をキーに, 辞書コーパスの対応する項目を検索することができるようになります.


*2: もちろん, 文書をカット&ペーストなどで直接入力して検索要求とすればmsearch2 がそのまま使えますが, ここでは,文書番号で文書を指定する方法を扱います.
文献[2]: 徳永健伸,"情報検索と言語処理",東京大学出版,1999.


7: AND 検索を実装する」に進む
5: 複雑な類似度を定義する」に戻る
1: はじめに」に戻る