Topic-Word Selection Based on Combinatorial Probability Toru Hisamitsu Yoshiki Niwa In Proceedings of the Sixth Natural Language Processing Pacific Rim Symposium (NLPRS), pp. 289-296, 2001.

この論文のポイント 文書集合から部分文書集合を得たとき，その部分文書集合の中で「特徴的な」語に重みを付ける方法を探求する 超幾何分布を応用した単語重み付け方法について考える TF*IDFやカイ二乗検定など，いくつかの重み付け方法を比較し，おのおのの傾向について考察する

文書集合を特徴づける語を見出す 情報検索，文書分類，文書クラスタリング，情報抽出において基本的なタスク 例）重要でない単語を除いて文書の類似度を計算したほうが高精度 (Sebastiani, 1999)

DualNaviの例

問題設定 全体文書集合から，語wを含む文書を検索して，部分文書集合Dwを得たとする この部分文書集合Dwに含まれる語vが，どのくらい特徴的に出現しているのか，測りたい D v Dw v v v v v v v v v v v v v v v v

従来手法 tf tf/TF tf*idf SMART Log likelihood ratio (LLR) Chi-square test (CS) Chi-square test with Yetes’ correction (CS2)

tf: 総出現頻度 部分文書集合Dw内の語vの総出現頻度 Dw内でたくさん出現する語vは， Dwを特徴づけるであろう 用語抽出では良い性能を示す (Daile et al., 1994; Caraballo et al., 1999; Hisamitsu et al., 2001)

tf/TF: 相対出現頻度 全体文書集合に対する，部分文書集合Dw内の語vの相対出現頻度 全体部分集合で１回しか出現せず，部分文書集合でも１回しか出現しないような語に，最大値１が与えられてしまう 低頻度語を過大評価してしまう

tf*idf: お馴染みの重み付け法 部分文書集合Dw内の語vの総出現頻度に，語vが全体文書集合内でどのくらい珍しいのか考慮したもの 計算が簡単であるが，いろいろなケースで，経験的によく効くと言われている 問題点: tfが大きくなると，idfが効かなくなる (Hisamitsu et al., 2000)

tf*idf2: tf*idfのtfの影響を少なくする OKAPI (Robertson et al., 2000) の簡略版 高頻度のtfの影響は，かなり削減されている

SMART: tf*idfの改良 部分文書集合Dwに含まれるそれぞれの文書dに対し，単語vの頻度をその文書d内の語の出現頻度の平均で正規化して和をとる (Singhal et al., 1996) 平均をとるため計算コストは高め

2×2分割表 a b a+b c d c+d a+c b+d n 語vが出現する回数 語v以外が出現する回数 合計 Dw中 （語wが出現）

対数尤度比 (Log likelihood ratio)

カイ二乗検定 観測された値Oが，その期待値Eからどのくらい離れているかを示す 得られたカイ二乗値に対して，「語vの出現頻度はDwに依存しない」という帰無仮説が何%の確率で成立するのか，カイ二乗分布から求めることができる．

カイ二乗検定（イェイツの修正） カイ二乗検定は，a < 5, b < 5, c < 5, d < 5のいずれかが成立するとき，以下の修正を行って，精度を改善する

超幾何分布による方法 n (= a + b + c + d)枚のカードが箱の中にある 箱の中のカードのうち，(a+c)枚のカードには「v」と書かれており，残りの(b+d)枚のカードには「v」以外の文字（何でも良い）が書かれている このとき，(a+b)枚のカードを無作為に比復元抽出（取り出したカードは戻さない）したとき，「v」と書かれたカードがa枚になる確率はどのくらいだろうか？ 実際には，「単語wを含む文書に含まれていた」という条件でカードを選別して，(a+b)枚のカードを選んだ訳であるが…

問題の確率を求める

超幾何分布の解釈 「フィッシャーの直接確率検定」もしくは「フィッシャーの正確確率検定」と呼ばれるものと同じ 値は確率なので，小さいほどvが特異に出現することを示す カイ二乗検定と異なり，観測変数の独立性さえ保障されていれば，どんな分布で発生する事象にも適用できる 問題点: a枚のカードが特異に多かったのか，少なかったのか区別できない 両方とも求まる確率pが 　　非常に小さくなる

HGSの定義 (a+b)枚のカードを無作為に非復元抽出（取り出したカードは戻さない）したとき，「v」と書かれたカードがa枚以上になる確率の対数

和をとる必然性？ 筆者は，「a枚のカードが特異に多かったのか，少なかったのか区別できない」ため，和を取っているが，以下の判別式を用いれば済むはず

超幾何分布を高速に計算する 対数を取って積和変換を行う Stirlingの近似式を使って階乗を計算する

評価方法 1998年の日経新聞の中から以下のクエリでDwを作成 エリツィン (947), オリンピック (934), オウム (265), AIDS (202), イントラネット (152), プリペイドカード (126), オゾン (52), テポドン (50) それぞれの部分文書集合に含まれる語を正例 (P), 負例 (N), どちらにも属さない (U)に手作業で分類する P: D(w)&D(v)がwに関する特定のトピックの文書集合であり，かつvがそのトピックの中心的役割を果たす N: D(w)&D(v)の中で，vとwはたまたま共起しているか，ストップワードに指定すべき語（例えば「する」「持つ」など）の場合 それぞれの手法が抽出した上位50語を評価する

正例を認識できた数

負例を認識してしまった数

正例の認識数ー負例の認識数

各指標を用いたときの順位相関 高い相関: tf*idfとSMART; tfとtf*idf HGSはtfとの相関が低く，tf*idfともそれほど似ていない

結論 CSよりもCS2の方が良い性能を示した HGSはCS2と同程度か，よい性能を示した Recallを同程度になるように閾値を設定した場合，precisionはHGSの方が２倍くらい良い 試したクエリー語に対しては，性能が安定している