stop-the-world

takuya-a のブログ

Information Retrieval and Web Search まとめ(18): テキスト分類(2)

前回は、テキスト分類タスクとナイーブベイズについて説明した。今回は決定木によるテキスト分類についてまとめる。

この記事は Information Retrieval and Web Search Advent Calendar 2020 の18日目の記事です。

adventar.org

テキスト分類の評価用データセット

決定木によるテキスト分類

  • 内部ノード (internal node) には、タームがラベルとしてついている
  • 枝 (branch) にはタームの重み(もしくは単に存在するかしないか)がラベルづけられている
    • 重みがある値以上なら右、それ未満なら左、というように
  • 葉 (leaf) にはカテゴリがラベルづけられている
  • 決定木による分類器は、木を下にたどりながら、文書をカテゴライズする
    • 葉についているラベルをその文書のカテゴリとする
  • ほとんどの決定木は二分木

f:id:takuya-a:20201218215128p:plain
決定木の例

  • 決定木はナイーブベイズと同様に、人間にとって解釈が容易
    • 決定木からルールを取り出すこともできる

決定木の学習

  • トップダウンに貪欲的にノードの分岐を学習していく
    • まだ使われていない特徴量のうち、もっとも情報利得 (information gain) が大きいものを選ぶ
  • 葉にはカテゴリの二値 (yes/no) かカテゴリの確率 P(class) を置く

f:id:takuya-a:20201218215059p:plain
決定木の学習

  • k 個の特徴量がある場合、最大で 2k 個のノードをもつかもしれない
  • もっと小さい木で表現したい
  • 各ノードで、再帰的にもっともよい分割を選択する、というのを貪欲的に繰り返すことによってこれを実現する
  • 分割のよさをどのように計算するか?
    • 以下で説明する情報利得が最大になるような特徴量 f を選ぶ

情報利得

  • クラスのエントロピー (entropy) は以下のように定義される
    •  p_i を、クラス i のサンプルの割合とする
 E = - \displaystyle\sum_{i=1}^{m} p_i \log p_i
  • 次に、各ノードにおける、クラス i の特徴量 f による分割を考える
    •  p_{i}^{f} を、クラス i の特徴量 f をもつサンプルの割合とする
    •  p_{i}^{\lnot f} を、クラス i の特徴量 f をもたないサンプルの割合とする
  • f でのノード分割のあと、エントロピーは以下のようになる
 E_f = - p^f \displaystyle\sum_{i=1}^{m} p_i^f \log p_i^f - p^{\lnot f} \displaystyle\sum_{i=1}^{m} p_i^{\lnot f} \log p_i^{\lnot f}

数値特徴量

  • TF-IDF のような数値の特徴量の場合、どの値で分割するか?
  • ビン (bin) に離散化する
    • k 個のビンに入れ、カテゴリ特徴量のように扱う
    • ビンはデータセット全体の統計量をもとに決める (k-means でのクラスタリングなど)

ノード分割の停止

  • 以下の場合、分割を止める
    • あるノードにおいてサンプルがすべて同じクラスになった場合
    • 木があらかじめ決められた深さ d に達した時
    • 分割による差分が統計的に有意でなくなった時
      • カイ二乗検定 (chi-square)フィッシャーの正確確率検定 (Fisher's exact) など
  • 検証セットを使って木を最適化する
    • まずは大きい木を作る(深さの閾値 d によって止まる)
    • 検証セットを使い、ボトムアップでノードを枝刈りする
      • 葉のほうのノードから始めて、検証セットのデータで分類精度が(統計的に有意に)上がらないノードは除去
    • 木が深くなるとバイアスは減り、バリアンスは増える

クラスごとの評価指標

  • 再現率 (recall)
  • 精度 (precision)
  • 正解率 (accuracy)
  • マイクロ平均 (microaverage)
  • マクロ平均 (macroaverage)

アンサンブル

  • シンプルで弱い (weak) 学習器を集め、その結果をまとめて1つのもっとよい学習器として利用する
  • アンサンブルの種類
    • バギング (bagging)
    • スタッキング (stacking)
    • ブースティング (boosting)

ランダムフォレスト

  • 元のデータセットからサンプリングされたデータセット (bootstrap sample) を使い、 K 本の木をつくる

Boosted Decision Tree

  • ランダムフォレストとは別の方法(こちらのほうがより新しい)

文書のテキスト分類の諸問題

データ量

カテゴリ数

概念ドリフト

  • カテゴリは時間の経過とともに変わっていく
  • 例:「アメリカの大統領」
    • 1998 年には "clinton" はいい特徴量だったが、2018 年ではそうではない
  • 概念ドリフトに対する頑健性もテキスト分類システムにとっては重要
  • 特徴選択をすると、概念ドリフトに弱くなる可能性がある

講義資料

参考資料

Information Retrieval and Web Search まとめ(17): テキスト分類(1)

前回は、様々なプルーニングアルゴリズムによって検索システムを高速化する方法について説明した。今回から、文書のテキスト分類について解説していく。

この記事は Information Retrieval and Web Search Advent Calendar 2020 の17日目の記事です。

adventar.org

テキスト分類の概要

継続クエリ

  • ここまでは、主にアドホック検索を対象としていた
    • ユーザは一過性の情報ニーズをもっていて、ユーザが検索システムにクエリを入力する、というケース
  • しかし、多くのユーザはもっと継続的な (ongoing) 情報ニーズも持っている
  • 毎朝ユーザがクエリを発行する代わりに、これを自動化することでユーザをサポートできる
    • そのクエリと適合する文書が新しく追加されたら、これを通知するようにできる
  • このようなクエリを継続クエリ (standing query) と呼ぶ
    • 専門家 ("information proofessinals") によって長らく使われてきた
    • 例:Google Alerts
  • 継続クエリは、(手で書かれた)テキスト分類器である
    • 情報ニーズに適合する文書 (relevant) か、適合しない文書 (not relevant) かを分類 (classification/categorization) している
  • 他にも、スパムフィルタなどのテキスト分類タスクがある

テキスト分類タスク

  • 入力 (given)
    • 文書 d の表現(BOW など)
    • 決められたクラス集合  C = \{ c_1, c_2, ..., c_J \}
  • 出力 (determine)
    • d のカテゴリ  \gamma(d) \in C
      •  \gamma(d)分類関数 (classification function)
      • この分類関数(分類器 (classifier))を構築したい

テキスト分類の方法

  • マニュアル分類
  • 手で作られたルールベース分類器
    • 広く使われているが、メンテナンスが大変
  • 教師あり学習 (supervised learning)

教師あり学習

  • 入力 (given)
    • 文書 d の表現
    • 決められたクラス集合  C = \{ c_1, c_2, ..., c_J \}
    • 訓練セット D
      • 訓練セット内の文書には C のラベルが1つついている
  • 出力 (determine)
    • テスト文書 d に対して、カテゴリ  \gamma(d) \in C を割り当てる

f:id:takuya-a:20201218023615p:plain
(IIR p.257 Figre 13.1) テキスト分類におけるクラスと訓練セット、テストセット

  • 教師あり学習の手法
    • ナイーブベイズ (naive bayes) (simple, common)
    • k 近傍法 (k-Nearest Neighbors) (simple, powerful)
    • サポートベクタマシン (support-vector machines; SVM) (newer, generally more powerful)
    • 決定木 (decision trees) --> ランダムフォレスト (random forest) --> 勾配ブースティング決定木 (gradient-boosted decision tree) (e.g., xgboost)
    • 他にもたくさんある

特徴量

  • 教師あり学習の分類器はさまざまな特徴量を扱える
    • URL、メールアドレス、辞書など
  • テキストに含まれる単語の特徴量を使う
    • BOW (bag of words)

特徴選択

  • コレクションには大量のユニークな単語がある(1万〜100万)
  • 特徴量(の次元)を減らすことで、学習時間を短くし、モデルを小さく速くし、過学習 (overfitting) を避けられる
  • モデルによってはそもそも100万個の特徴量を扱えないものもある
  • 特徴選択 (feature selection):単語の頻度を使って特徴量となる単語を選択できる
    • 単純に common な単語だけを使うなど
    • 他にもカイ二乗法などのスマートな方法もある

評価指標

  • 精度 (precision)
  • 再現率 (recall)
  • F1スコア (F1 score)
  • 正解率 (classification accuracy)

ナイーブベイズ

  • Ref. IIR chapter 13
  • SpamAssassin などに応用されている
  • 学習も予測も非常に速い
  • モデルのストレージ上のサイズが小さい
  • 特徴量(単語)がそれぞれ同程度に重要であるようなコレクションには非常に適している
  • ノイズのような特徴量に対してもロバスト
  • 概念ドリフト (concept drift)(時間経過でクラスの意味が変化すること)に対してもロバスト
  • KDD CUP 97 で1位と2位になっている
  • テキスト分類におけるよいベースライン(ベストではないが)

WebKB 実験

f:id:takuya-a:20201218023707p:plain
([Craven et al. 1998] Table 1) WebKB データセットでのナイーブベイズ分類器の正解率

講義資料

参考資料

Information Retrieval and Web Search まとめ(16): 検索システムの効率性

前回は、多値適合性に基づくランクつき検索評価指標である nDCG と、クリックデータの活用に際しての注意点やテクニックについて解説した。今回は、検索システムの効率性 (efficiency) について議論する。

この記事は Information Retrieval and Web Search Advent Calendar 2020 の16日目の記事です。

adventar.org

背景

  • クエリ実行時、スコア計算が CPU 全体の数十%を使っている
    • 一般的に、レイテンシに関して厳しい制限がある(250ミリ秒とか)
    • すべてのクエリですべての文書を網羅的にスコア計算することは許されない
  • 検索結果のクオリティは(大きくは)下げずに CPU 使用率を下げる方法をみていく
  • 基本的なアイデア:top K に入らない文書のスコア計算を避ける
  • 安全なランキング (safe ranking)」と「安全でないランキング (non-safe ranking)」
    • 安全 = top K の文書を正確に返す手法
    • 安全ではない = top K の文書に近い K 個の文書が得られれば OK
    • 両方の手法を紹介する

効率的なスコア計算とランキング

  • 復習:ベクトルとしてのクエリ
    • クエリをベクトルとして表現する
    • ベクトル空間上の近さで文書をランク付けする
      • 近さ = コサイン類似度で定義されるベクトル間の類似度
  • 効率的なコサイン類似度でのランキング
    • タスク:クエリ-文書間のコサイン類似度が最も大きい K 個の文書を探す
    • 1.各々のコサイン類似度を効率的に計算する
    • 2.コサイン類似度が最も大きい K 個の文書を選択する

ヒープを使った Top K の選択

  • 通常、検索では top K の文書のみが必要で、全文書の順番は不要
  • コサイン類似度が 0 ではない文書が J 個あるとする
    • J 個の文書のなかから、大きいもの K 個を探す
  • ヒープ (heap) というデータ構造を使う
    • 二分木の一種
    • 各ノードの値が、そのノードの子孫よりも大きくなっているという制約がある
    • ヒープの構築は 2J 回の操作でできる
    • そのなかから値が大きい K 個のノードを取り出すのは 2 log J ステップでできる
    • たとえば J = 1MK = 100 だったとき、ソートするコストの約 10%

f:id:takuya-a:20201217003840p:plain
ヒープの例。点線より上のノードは、top 3 の値をもつ

  • コサイン類似度の計算がボトルネック
    • 全文書のコサイン類似度を計算せずにできるだろうか?

安全でない top K ランキング

プルーニングによるスコア計算の高速化

  • インデックス除去 (index elimination)
    • IDF がある一定の閾値を超えたタームのみを考慮する
      • IDF が低いポスティングリストは通常長いので有効
      • ストップワードのようなタームのスコア計算をせずにすむ
    • クエリタームの多くを含む文書だけを考慮する
    • ref. IIR 7.1.2
  • チャンピオンリスト (champion list)
    • 各ターム t のポスティングリストごとに、そのなかで最も重みが大きい r 個のポスティングを事前に計算しておく
      • このポスティングを t のチャンピオンリストと呼ぶ
      • インデックス構築時に計算される
    • クエリ処理ではこのチャンピオンリストにある文書だけをスコア計算する

静的スコア

  • 静的なクオリティスコア
  • ポスティングを事前にこの静的スコアでソートしておく
  • クエリ処理時にはこの順番で処理し、top K を計算する
  • チャンピオンリストの方法と組み合わせられる

クラスタプルーニング

  • クラスタプルーニング (cluster pruning) は、文書を事前にクラスタリングしておいてそれを利用する高速化手法
  •  \sqrt{N} 文書を事前にランダムに選択
    • これらの文書をリーダー (leader) と呼ぶ
  • 他の全ての文書に対して、最も近いリーダーを事前計算しておく
    • それらをフォロワー (follower) と呼ぶ
    • リーダーはおおよそ  \sqrt{N} 個のフォロワーをもつ

f:id:takuya-a:20201217004223p:plain
(IIR p.142 Figure 7.3) クラスタプルーニングを使ったクエリ処理

  • クエリ処理
    • 与えられたクエリに対して、もっとも近いリーダー L を見つける
    • LL のフォロワーの中からもっとも近い K 個の文書を探す
  • ランダムに選ぶ理由
    • 高速
    • データの分布を反映したリーダー選択ができる

層化インデックス

  • 層化インデックス (tiered indexes) は、転置インデックスを複数の層 (tier) に分けて管理する方法

f:id:takuya-a:20201217232750p:plain
(IIR p.144 Figure 7.4) 層化インデックスの例

インパクト順ポスティング

  • インパクト順ポスティング (impact-ordered postings)
    •  wf_{t,d} が大きい文書のみスコア計算したい
    •  wf_{t,d} によってポスティングリストをソートしておく
  • 早期終了 (early termination)
    • 固定された数 r だけ文書を見たら終了、もしくは  wf_{t,d} がある閾値を下回ったら終了
    • それらの和集合のみスコア計算する
  • IDF-ordered terms
    • IDF の降順でタームを見ていく
      • IDF が高いタームはスコアへの寄与も大きい
    • 各クエリタームのスコアへの寄与が相対的に変わらなくなったら終了

安全な top K ランキング:WAND

  • 安全なランキング (safe ranking)
    • スコアが top K の文書を正確に返す手法
    • スコアはコサイン類似度に限らない
  • 一部の文書のスコア計算をしない
    • プルーニング (pruning) = 枝刈りを行う

WAND

  • DAAT スコアリング手法の一つ
  • クエリ処理の実行中、スコアの閾値 (threshold) を管理する
    • 閾値は K 番目に高いスコア
  • スコアがこの閾値より高くならないことがわかった文書は枝刈り (prune) する
  • 枝刈りされなかった文書のみスコアを計算する
  • [Broder et al. Efficient Query Evaluation using a Two-Level Retrieval Process.]

参考:Research Paper Introduction in IR Reading 2020 Fall

WAND のインデックス構造

  • ポスティングは docID によってソートされている
  • クエリ処理の実行中、各クエリタームのポスティングリストごとに、一つのポインタ ("finger") をもつ
    • それぞれのポインタは右にのみ(つまり docID が大きくなる方向にのみ)動く
  • 不変条件
    • 各ポインタより左にある docID はすでに「処理された」ことを意味する
      • 枝刈りされたか、もしくはスコアが計算されたか

上限

  • 各クエリターム t ごとに、常に上限 (upper bound)  UB_t を保持する
    • ポインタより右にある文書の、スコアへの貢献 (contribution)  w_t(doc) の最大
    • ポインタが右に動くことで、  UB_t は下がることがある

f:id:takuya-a:20201217230024p:plain
ポインタ (finger) と上限 (upper bound) の概念図。ポインタより右にある文書のうち、最大のスコアへの寄与をもつのは docID 38 の文書であり、その値が上限となっている

WAND によるクエリ処理

  • クエリ "catcher in the rye" を処理しているある時点での各ポインタと上限  UB_t を以下に示す
    • クエリタームはポインタの位置でソートされている
    • 現在の閾値(いままで計算したなかで K 番目のスコア)は 6.8

f:id:takuya-a:20201217230145p:plain
クエリを処理しているある時点での各ポインタ (finger) と上限 (upper bound)。現在の尾閾値 (threshold) は 6.8

  • 上から順番に上限  UB_t を足していき、閾値 6.8 を超えるクエリタームを探す
    • この場合は "in"
    • そのタームをピボット (pivot) と呼ぶ
  • ピボットのポインタが指している docID までは安全にスキップできる

f:id:takuya-a:20201217004041p:plain
ピボットを使ったプルーニング

  • もしピボット位置の文書が閾値を超えそうなら、そのコサイン類似度全体を計算する
    • そうでない場合、いくつかのポインタがそれより右にある
  • さらにピボットの再計算を行う(繰り返し)

WAND のまとめ

  • 90% 以上のスコア計算を削減できることが実験で確かめられている
    • より長いクエリではそれ以上
  • コサイン類似度によるスコアリングに限らない
    • タームに対してスコアが加法的 (additive) であればよい
  • WAND とその亜種は安全なランキングである

講義資料

参考資料

Information Retrieval and Web Search まとめ(15): 評価(2)

前回は、ランクなしの(二値)評価指標である精度と再現率、そして二値適合性に基づくランクつき指標である Precision@K、MAP について解説した。今回は多値適合性に基づく nDCG、そしてクリックデータの活用について説明する。

この記事は Information Retrieval and Web Search Advent Calendar 2020 の15日目の記事です。

adventar.org

多値適合性に基づく検索評価指標

減損累積利得 (DCG) の概要

  • DCG (discounted cumulative gain) は Web 検索などの評価に用いられるポピュラーな指標
  • 2つの仮定を置いている
    • 関連性が高い文書は、より低い文書よりも有用性が高い
    • 文書の順位(ランク)が低いほど、見られる可能性が低いため、ユーザにとって有用性が低い
  • 文書の有用性あるいは利得 (gain) の指標として、グレードつきの適合性を使う
    • 多値適合性
  • 利得はランキングの上位から累積されるが、下位の文書ではそれが減損 (discount) される可能性がある
  • 典型的な減損は  1/\log (rank)
    • log の底が2のとき、ランキングが4位の減損は 1/2、8位の減損は 1/3 になる

累積利得 (CG)

  • 適合性判定の値が  [0, r (r < 2)] の範囲だとする
  • 第k位までの文書の判定がそれぞれ  r_1, r_2, ..., r_k だったとすると、累積利得 (cumulative gain; CG)
 CG_k = r_1 + r_2 + r_3 + ... + r_k

減損累積利得 (DCG)

  • 前述したように、DCG では順位が下がるごとに利得を減損させていく
  • 減損として  1/\log_2 (rank) を使ったとき、
\begin{eqnarray}
DCG_k &=& r_1 + \dfrac{r_2}{\log_2 2} + \dfrac{r_3}{\log_2 3} + ... + \dfrac{r_k}{\log_2 k} \\
      &=& r_1 + \sum_{i=2}^p \dfrac{r_i}{\log_2 i} \\
      &=& \sum_{i=1}^p \dfrac{2^{r_i} - 1}{\log_2 (1+i)}
\end{eqnarray}
  • log の底には任意のものが使える
  • Web 検索の企業で使われている

f:id:takuya-a:20201216011045p:plain
nDCG の例。Ground Truth が理想的なランキング(nDCGは1)

nDCG

  • nDCG (normalized discounted cumulative gain) は、理想的なランキングだったときの DCG によって正規化したもの
    • DCG を最大値が 1 になるように正規化
    • 理想的なランキングというのは、第1位に最も適合性の高い文書、第2位に2番目にい適合性の高い文書……という順番になっているもの
  • 正規化は、検索結果の件数が異なるクエリで指標を比較するときに有用
  • nDCG は、Web 検索で現在最も使われている評価指標

クリックデータの活用

人間による判定の問題点

  • 高価である
  • 一貫性がない
    • 評価をつける人の間で、もしくは同じ人でも時間が経つと
  • いつも「本当のユーザ」を代表しているわけではない
    • クエリを見ても実際の情報ニーズはわからない
    • タームの意味がわからないこともある

ポジションバイアス

  • 検索結果の位置によって強いバイアスがかかる
    • 1位の文書は下位のものよりクリックされやすい
  • アイトラッキングシステムを使った実験でも実証されている [Joachims+07]
    • 高い位置のものはユーザの注意をよりひきつけ(視線が固定される)、クリックもされる
    • 検索結果の順位を逆順にしてもこの傾向は変わらない
  • クリックデータは有用ではあるが、バイアスがあるので注意が必要

相対評価絶対評価

  • 第1位の検索結果 (R1) と、第3位の検索結果 (R3) がクリックされたとき、
    • R1 > R3 と結論づけるのは難しい
    • R3 > R2 は言えるかもしれない
  • ペアワイズによる相対的な評価
    • これまでにやってきた評価(クエリと文書に対して絶対値の適合性判定がついていた)とは違う
    • 過去のクリックデータからペアワイズの評価

インターリービング

  • 2つのランキングアルゴリズム A, B を比較するために、それぞれから得られたランキングを互い違いに混ぜたものを検索結果ページ (SERP) として返す (interleave)
    • A から始めるか B から始めるかはランダムに選択(表示バイアスを除くため)
    • 重複した検索結果を含む場合は、下位のほうを取り除く
  • クリックデータから、A, B それぞれのクリック数をカウント
  • より良いランキングアルゴリズムがより多いクリックを獲得するはず

Web 検索における A/B テスト

  • 目的:1つの変更の効果をテストすること
  • 事前条件:すでに大規模な検索エンジンをもっていて、それが動いていること
  • 小さな比率のトラフィック(たとえば 0.1%)を変更したバージョンに向ける
    • インターリービングしてもいいし、ページ全体を使ってもいい

講義資料

参考資料

Information Retrieval and Web Search まとめ(14): 評価(1)

前回は、確率的生成モデルから導出された重み付け手法である Okapi BM25 について解説した。今回から検索システムの評価について説明する。

この記事は Information Retrieval and Web Search Advent Calendar 2020 の14日目の記事です。

adventar.org

適合性判定

適合性を評価するためには、以下の3つを含むデータが必要:

  • 1 . 文書コレクション
  • 2 . クエリ集合
    • 文書に関連するものであること
    • 実際のユーザの情報ニーズを表現していること
    • 文書からタームをランダムに抜き出してクエリとするのはよくない
    • クエリログからサンプリングする(もし可能なら)
      • クエリログが十分に得られない場合は、エキスパートが手で「ユーザの情報ニーズ」を作る
  • 3 . クエリと文書の各ペアについて、適合しているかしていないかの判定データ
    • 通常は二値で評価
    • (0, 1, 2, 3, ...) のように段階的なものも使われる
    • 文書数 500 万、5万クエリのデータあったとき、2500億の判定が必要になる
      • 2.5 秒で 1 つの判定をしたとしても、 1011 秒かかる
      • 時間あたり 10 ドル支払うとすると 3 億ドルかかる

f:id:takuya-a:20201215044305p:plain
古典的なデータセットの一覧。典型的には TREC が使われる。

  • 近年のデータセット(GOV, ClueWeb 等)には、数億の Web ページが含まれる

(参考: IIR 8.1, 8.5)

検索システムの評価

  • ユーザの情報ニーズは、クエリに翻訳される
  • 適合性はクエリに対してではなく、ユーザの情報ニーズに対して判定される
    • 情報ニーズ: "My swimming pool bottom is becoming black and needs to be cleaned."
    • クエリ: "pool cleaner"
    • 文書が根本的な情報ニーズに対応しているかどうかによって判定する
      • 単語が含まれているかどうかは見ない

(参考: IIR 8.1)

ランクなし検索の評価:精度と再現率

  • 精度 (precision)
    • 検索された文書のうち、適合するものの割合
    •  P(\text{relevant}|\text{})
  • 再現率 (recall)
    • 適合する文書のうち、適合するものの割合
    •  P(\text{retrieved}|\text{relevant})
  • 以下の分割表を使うときれいに整理できる:

f:id:takuya-a:20201215044651p:plain
(IIR p.155 8.3) 分割表

  • 精度  P = \dfrac{tp}{tp + fp}
  • 再現率  R = \dfrac{tp}{tp + fn}

(参考: IIR 8.3)

ランクつき検索評価指標

  • 二値適合性
    • Precision@K
    • Mean Average Precision (MAP)
    • Mean Reciprocal Rank (MRR)
  • 多値適合性
    • Normalized Discounted Cumulative Gain (NDCG)

再現率-精度曲線

f:id:takuya-a:20201214235205p:plain
(IIR p.158 Figure 8.2) 再現率-精度曲線

Precision@K

  • 順位(ランク)の閾値を K とし、上位 K 件までの文書で適合するものの割合
    • K より下の文書は無視する
  • 以下のような Top-4 の検索結果があったとすると
    • 1: relevant
    • 2: nonrelevant
    • 3: relevant
    • 4: nonrelevant
  • Precision@K は以下の通り
    • P@3 = 2/3
    • P@4 = 2/4
    • P@5 = 3/5
  • 同様に Recall@K も定義できる

Mean Average Precision (MAP)

  • 適合している各文書の順位を考慮する
  • その順位に対して Precision@K をそれぞれ計算する
  • 平均精度 (Average Precision; AP) は、計算されたすべての P@K の平均 (average)
  • Mean Average Precision (MAP) は、複数のクエリに対して Average Precision を計算し、その平均 (mean) をとったもの

f:id:takuya-a:20201215044420p:plain
Mean Average Precision (MAP) の例

  • 適合する文書がなかった場合、精度は 0 と仮定する
  • MAP はマクロ平均
    • 各クエリは等しくカウントされる
  • MAP は研究論文でおそらくもっとも一般的に使用されている評価指標
  • MAP は、ユーザが多くの適合文書を見つけたいと考えていることを想定している
  • MAP は非常に多くの適合性判定を必要とする

講義資料

参考資料

Information Retrieval and Web Search まとめ(13): 確率的情報検索(2) BM25

前回は、確率的情報検索の基本となる確率的ランキング原理とバイナリ独立モデルについて説明した。今回は確率的モデルによる重み付け手法である Okapi BM25 について解説する。

この記事は Information Retrieval and Web Search Advent Calendar 2020 の13日目の記事です。

adventar.org

ベクトル空間モデルの復習

  • クエリに含まれる単語が多く出てくる文書の順位は高くすべき
    • また、それは文書長などによって調整される
  • バイナリ独立モデル(BIM)ではだめなのか?
    • 初期の情報検索のモデルの多くは、タイトルや概要(長さがほぼ同じ)を対象にしており、全文検索はあまり意識されていなかった
    • ターム頻度を入れたモデルを作りたい
  • ベクトル空間モデル(復習)
    • クエリと文書を TF-IDF によって重み付けされたベクトルとして表現する
    • クエリベクトルと文書ベクトルのコサイン類似度スコアを計算
    • 文書をそのスコアによってランク付けする
    • 上位 K 件(例えば K = 10)をユーザに返す

Okapi BM25 の概要

  • Okapi BM25 は、検索システム Okapi を開発するなかで 25 番目に生まれた、タームの重み付け方法
  • BM25 は "Best Match 25" の意味
    • TREC で BM25 を採用するチームが増え始めた
    • 性能がよい
  • BM25 のゴール:パラメータを多く足さずに、ターム頻度や文書長をよく反映すること
    • [Robertson and Zaragoza 2009; Spärck Jones et al. 2000]
  • BM25 は文書の生成モデル
    • 単語(ターム)は多項分布 (multinominal distribution) から独立して生成されると仮定する

Poisson モデル

  • 文書のターム頻度の分布が、ポアソン分布で近似した二項分布に従う、と仮定するモデル
    •  \lambda = Tp とすることで、二項分布をポアソン分布で近似できる
    •  T は二項分布の試行回数、  p は試行の成功確率
  • Poisson モデルの問題点
    • ポアソン分布は(時間もしくは空間の)固定した区間内で事象が発生する回数をモデル化する
      • BM25 のモデルでは、文書から生成される単語がポアソン分布から発生していると仮定している
      • つまり、区間が固定されているというのは、文書長も固定されていることを意味している
      • これは後ほど修正する
    • 特定のトピックに関係する単語ではあまりフィットしない
      • 一般的な単語についてはよく当てはまる

f:id:takuya-a:20201214042240p:plain
λ = 53/650 の単語についての、文書内の単語出現回数の分布。"cathexis"(医学用語?)や "comic" のような単語は、特定の文書に集中して出現している。 [Harter, “A Probabilistic Approach to Automatic Keyword Indexing”, JASIST, 1975]

エリートネス

  • ターム頻度をエリートネス (eliteness) という概念を使ってモデル化する
  • エリートネスとは、文書とタームの組における隠れ変数であり、ターム  i に対して  E_i と書くことにする
  • 文書中のタームについて、文書がある意味でそのタームで示される概念についての文書であるとき、そのタームはエリート (elite) であるという
    • エリートネスは2値で表現する( E_i = elite or  E_i = \overline{elite}
  • NFL draft に関する Wikipedia 記事内の、エリートなタームの例(太字)を以下に示す

The National Football League Draft is an annual event in which the National Football League (NFL) teams select eligible college football players. It serves as the league’s most common source of player recruitment. The basic design of the draft is that each team is given a position in the draft order in reverse order relative to its record ...

  • タームの出現はエリートネスに依存する
  • エリートネスは適合度に依存する

f:id:takuya-a:20201214042854p:plain
エリートネス(Ei)を追加したグラフィカルモデル

Poisson モデルの Retrieval Status Value

  • BIM のときと同様に、Retrieval Status Value (RSV) を考える

RSV^{elite} = \displaystyle\sum_{i \in q, tf_i > 0} c_i^{elite} (tf_i); \;
c_i^{elite} (tf_i) = \log \frac{ p( TF_i = tf_i \mid R=1 ) p( TF_i = 0 \mid R=0 ) }{ p( TF_i = 0 \mid R=1 ) p( TF_i = tf_i \mid R=0 ) }
  • エリートネスを使って  p\left( TF_i = tf_i \mid R \right) は以下のように展開できる
\begin{eqnarray}
p\left( TF_i = tf_i \mid R \right)
&=& p(TF_i = tf_i \mid E_i = elite) p(E_i = elite \mid R) \\
&+& p(TF_i = tf_i \mid E_i = \overline{elite}) \left( 1 - p(E_i = elite \mid R) \right)
\end{eqnarray}

2-Poisson モデル

  • 前述した Poisson モデル(1-Poisson モデルと呼ぶ)の問題を解決するため、2つのポアソン分布でフィッティングする
  • 2-Poisson モデルでは、タームがエリートかどうかによって分布が変わる

p \left( TF_i = k_i \mid R \right) =
\pi \frac{\lambda^k}{k!} e^{-\lambda} +
(1 - \pi) \frac{\mu^k}{k!} e^{-\mu}
  •  \pi は文書がタームに対してエリートである確率
  •  \pi \lambda \mu の値はわからない

2-Poisson モデルの Retrieval Status Value

  •  c_i^{elite} (tf_i) が満たすべき性質
    •  c_i^{elite} (0) = 0
    •  c_i^{elite} (tf_i) tf_i によって単調に増加
    •  tf_i \to \infty で最大値に漸近的に近づく
      • 単に tf をスケーリングするだけではこの性質を満たせない
    • 漸近的な極限は  c_i^{BIM}
      • エリートネスの重み
  • 2-Poisson モデルのパラメータ(tex: \pi]、 \lambda \mu)を推定するのは容易ではない
  • --> 上記の性質を満たす、以下の飽和関数で近似する
 \dfrac{tf}{k_1 + tf}

f:id:takuya-a:20201214142641p:plain

  • パラメータが1つしかなくシンプル
  •  k_1 が大きいとき (例: k_1 = 10) でも  tf_i はスコアにちゃんと寄与する
  •  k_1 が小さいとき (例: k_1 = 0.2) には関数はすぐに飽和し、  tf_i からの寄与は小さくなっていく

Okapi BM25

BM25 の原形

  • Version 1
    • 上記の飽和関数をそのまま使ったバージョン
    • バイナリ独立モデル (BIM) に飽和関数をかませる
 c_i^{BM25v1} (tf_i) = c_i^{BIM} \dfrac{tf_i}{k_1 + tf_i}
  • Version 2
    • BIM を IDF に置き換えて簡略化
    •  (k_1 + 1) は、ランキングを変化させずに  tf_i = 1 のときにスコアを 1 にするための項
    • TF-IDF に似ているが、タームによるスコアは上限がある
 c_i^{BM25v2} (tf_i) = \log \dfrac{N}{df_i} \cdot \dfrac{(k_1 + 1) tf_i}{k_1 + tf_i}

文書長による正規化

  • 長い文書では  tf_i が大きくなる傾向がある
  • 文書が長くなっている可能性
    • 冗長性:観測された  tf_i が大きすぎる
    • 大きいスコープ:観測された  tf_i は適正
  • 実際の文書では両方の影響がある
    • 部分的になんらかの正規化をする必要がある
  • 文書長  dl = \displaystyle\sum_{i \in V} tf_i
    • コレクションでの文書長の平均を  avdl とする
  • 文書長の正規化を以下で行う
 B = \left( (1-b) + b \frac{dl}{avdl} \right), \; 0 \leq b \leq 1
  • 正規化の強さをパラメータ b で調整する
    • b = 1: 文書長で完全に正規化
    • b = 0: 文書長による正規化をしない

BM25

  • ターム頻度  tf_i を文書長で正規化する
    •  tf_i' = \dfrac{tf_i}{B}
    •  tf_i が元の tf、正規化後の tf が  tf_i'
  • これを使って  c_i^{BM25}(tf_i) を以下のようにする
\begin{eqnarray}
c_i^{BM25}(tf_i)
&=& \log \frac{N}{df_i} \cdot \frac{ (k_1 + 1) tf_i' }{ k_1 + tf_i' } \\
&=& \log \frac{N}{df_i} \cdot \frac{ (k_1 + 1) tf_i }{ k_1 \left( (1-b) + b \frac{dl}{avdl} \right) + tf_i }
\end{eqnarray}
  • よって、BM25 のランキング関数は
\begin{eqnarray}
RSV^{BM25}
&=&
\displaystyle\sum_{i \in q} c_i^{BM25}(tf_i) \\

&=&
\displaystyle\sum_{i \in q}
\log \frac{N}{df_i} \cdot
\frac{ (k_1 + 1) tf_i }{ k_1 \left( \left( 1-b \right) + b \frac{dl}{avdl} \right) + tf_i }
\end{eqnarray}
  •  k_1 はターム頻度の寄与をスケーリングする
    •  k_1 = 0 のときはバイナリモデルになり、 k_1 = 1 のときはターム頻度そのものを使うことになる
  •  b は文書長の正規化の強さを調整する
    •  b = 0 のときは正規化なし、 b = 1 のときは完全に文書長でスケーリングする(相対的なターム頻度を使う)
  • 典型的なパラメータ
    •  k_11.2-2
    •  b はおよそ 0.75
  • BM25 のほうがベクトル空間モデルの TF-IDF よりよくなる例
    • クエリが machine learning だったとする
    • 以下のような文書があったとする
      • 文書1: learning の tf が 1024、machine が 1
      • 文書2: learning の tf が 16、machine が 8
      • 文書2 のほうが適合度が高いと思われる
    • TF-IDF:  \log_2 tf \cdot \log_2 (N/df)
      • 文書1: 11 * 7 + 1 * 10 = 87
      • 文書2: 5 * 7 + 4 * 10 = 75
    • BM25( k_1 = 2 のとき)
      • 文書1: 7 * 3 + 10 * 1 = 31
      • 文書2: 7 * 2.67 + 10 * 2.4 = 42.7

講義資料

参考資料

Information Retrieval and Web Search まとめ(12): 確率的情報検索(1) 確率ランキング原理とバイナリ独立モデル

前回は、TF-IDF とコサイン類似度による文書のスコアリングについて解説した。今回からは確率的モデルを取り入れた情報検索である、確率論的情報検索について紹介する。

この記事は Information Retrieval and Web Search Advent Calendar 2020 の12日目の記事です。

adventar.org

確率的情報検索の必要性

  • ランク付き検索において、通常のブーリアン検索 (クエリを AND, OR, NOT で組み立てる検索) には、検索結果がしばしば非常に少なくなる(= 0)か、非常に多くなる(> 1000)という問題があった
    • 前回は、各文書とクエリ間の類似度を計算してランク付けする(一種の "soft AND")という解決策を示した
  • しかし、ユーザが入力したクエリ表現も、それと文書との適合性も、いずれも不確かなものである
    • 古典的な情報検索システムでは、タームを使ってクエリと各文書とをマッチさせているが、それらの適合性は不正確な予測によるものである
  • 確率論は、不確かな推論に関する基礎を提供する
    • 上で述べた検索の不正確さを定量化するために確率論を使う

確率ランキング原理

  • 文書のランキングは、現代的な情報検索システムのコアである
  • 確率論的情報検索のアイデア:情報ニーズを考慮した適合確率によって文書をランキングする
    •  p\left(R=1 \mid d,q \right)
      • クエリ  q に対して文書  d が適合している確率
      •  R は、文書がクエリに適合しているかどうかを示す確率変数
      • まずは確率変数  R が 1/0 の2値のどちらかをとる場合について考える
  • 確率論的情報検索は、以下の 確率ランキング原理 (probability ranking principle; PRP) を出発点にしている

If a reference retrieval system’s response to each request is a ranking of the documents in the collection in order of decreasing probability of relevance to the user who submitted the request, where the probabilities are estimated as accurately as possible on the basis of whatever data have been made available to the system for this purpose, the overall effectiveness of the system to its user will be the best that is obtainable on the basis of those data.

[1960s/1970s] S. Robertson, W.S. Cooper, M.E. Maron; van Rijsbergen (1979:113); Manning & Schütze (1999:538)

  • 「検索システムが、ユーザのリクエストに対して、データに基づいて文書の適合度の確率を可能な限り正確に推定し、その確率の降順で文書をランキングするなら、システム全体の有効性は、これらのデータに基づいて得られる最高のものとなるだろう」

確率的情報検索の戦略

  • 各タームが適合度にどのくらい寄与するかを推定
    • 他の要素、例えばターム頻度 (TF) や文書長は文書の適合性にどのくらい影響するか?
      • BIM(後述)ではまったく関係ない
      • BM25 (後述)で議論
  • 文書の適合確率を結合(?)
  • 適合確率の降順で並べ替え
  • 「1/0 の損失のもとで損失(ベイズリスク)を最小化するには、確率的ランキング定理 (PRP) を使用するのが最適」という定理がある [Ripley 1996]

バイナリ独立モデル

  • バイナリ独立モデル (Binary Independence Model; BIM) は、古典的に PRP と併用されているモデル
  • バイナリ (binary) = ブーリアン (bolean)
    • 文書はタームの2値生起ベクトル (binary incidence vector) として表現される (参考:IIR chapter 1):
    •  \vec{x} = (x_1,...,x_M)
    •  x_i = 1 iff ターム i が文書 x に存在するとき
  • 独立 (independence)
    • タームは文書中に独立に生起する
  • 異なる文書でも同じベクトルとして表現されることがある
  • クエリも2値生起ベクトルとして表現する
  • 与えられたクエリ q に対して、各文書 d に対して  p\left(R \mid d,q \right) を計算したい
    • d を2値生起ベクトルで表現した x で d を置き換えた  p\left(R \mid x,q \right) の計算で代替する
      • ランキングのみに興味がある
  • ベイズの定理を使えば、 p\left(R=1 \mid x,q \right) は以下のように変形できる
    •  p\left(R=1 \mid q \right) は、クエリ q に対して適合している文書の事前確率
    •  p\left( x \mid R=1, q \right) は、クエリ q に対する適合文書が取得されたときに、それが  x である確率
 p\left(R=1 \mid x,q \right) = \dfrac{ p\left( x \mid R=1, q \right) p\left( R=1 \mid q \right) }{ p\left( x \mid q \right)}
  • 文書が適合しているオッズ (odds) は以下の通り
\begin{eqnarray}
O\left(R \mid q,x \right)

&=&
\dfrac{
  p\left(R=1 \mid x,q \right)
}{
  p\left(R=0 \mid x,q \right)
} \\

&=&
\dfrac{
  \frac{
    p\left(R=1 \mid q \right) p\left(x \mid R=1, q \right)
  }{
    p\left( x \mid q \right)
  }
}{
  \frac{
    p\left(R=0 \mid q \right) p\left(x \mid R=0, q \right)
  }{
    p\left( x \mid q \right)
  }
} \\

&=&
\dfrac{
  p\left(R=1 \mid q \right)
}{
  p\left(R=0 \mid q \right)
}
\cdot
\dfrac{
  p\left(x \mid R=1, q \right)
}{
  p\left(x \mid R=0, q \right)
}
\end{eqnarray}
  • 最後の式の左の項は、与えられたクエリ q に対しては定数になる
    • いまはランキングにのみ興味があるので、推定しなくてよい(計算しない)
  • 右の項は推定しなければならないが、難しい
    • そこで、上述した独立性の仮定を使う
  • 最終的に以下の形になる(途中の計算は省略: IIR pp.224-225 を参照)
    •  p_i = p \left( x_i = 1 \mid R=1, q \right)
    •  r_i = p \left( x_i = 1 \mid R=0, q \right)
    •  i はタームのインデックス

O\left(R \mid x,q \right) =

O\left(R \mid q \right)
\cdot
\displaystyle\prod_{x_i = q_i = 1}
  \frac{ p_i \left( 1 - r_i \right) }{ r_i \left( 1 - p_i \right) }
\cdot
\displaystyle\prod_{q_i = 1}
  \frac{ 1 - p_i }{ 1 - r_i }
  • 第1項と第3項はクエリに対しては定数になる
    • ランキングのためには第2項のみを推定すればよい
  • この第2項の対数をとったものを Retrieval Status Value (RSV) と呼ぶ
\begin{eqnarray}
RSV

&=&
\log \displaystyle\prod_{x_i = q_i = 1}
  \frac{ p_i \left( 1 - r_i \right) }{ r_i \left( 1 - p_i \right) }

=
\displaystyle\sum_{x_i = q_i = 1}
  \log \frac{ p_i \left( 1 - r_i \right) }{ r_i \left( 1 - p_i \right) } \\

&=&
\displaystyle\sum_{x_i = q_i = 1} c_i; \;
c_i = \log \frac{ p_i \left( 1 - r_i \right) }{ r_i \left( 1 - p_i \right) }
\end{eqnarray}
  •  \sum の中身を  c_i と置いた

講義資料

参考資料