« 読了：Naik & Raman (2003) 広告媒体間のシナジー効果をカルマン・フィルタで華麗に推定するぜ | メイン | 読了：「恋は雨上がりのように」「私の少年」「アルテ」「サトコとナダ」「独身OLのすべて」「山賊ダイアリーSS」 »
2017年12月 5日 (火)
Lewis, D.D. (1998) Naive (Bayes) at forty: The independence assumption in information retrieval. ECML-98 (European Conference on Machine Learning), pp.4-15.
40年にも及ぶ長い歴史を持つ、ご存じナイーブベイズ分類器について、(パターン認識じゃなくて)情報検索の文脈でレビューしますという論文。
タイトルからして面白そうで、待ち時間中の時間潰し用に鞄にいれていた論文。読み始めてすぐに関心と違うことに気が付いたのだが(information retrievalって文字通り文書検索とかのことなのね)、フガフガと楽しく読了。
まずはおさらいから。
ベイズの定理によれば、特徴ベクトル$X=x$を持つイベント(ここでは文書)が$C$のどこかのクラス$c_k$に落ちるとして、
$P(C=c_k|X=x) = P(C=c_k) \times \frac{P(X=x|C=c_k)}{P(x)}$
簡略化して
$P(c_k | x) = P(c_k) \times \frac{P(x|c_k)}{P(x)}$
と書きますね。
$P(x|c_k), P(c_k), P(x)$がわかれば$P(c_k|x)$がわかるわけだけど、あいにく$x$がとりうる値は天文学的な数がある。そこで登場するのが、
$P(x | c_k) = \prod_j P(x_j | c_k)$
としようというアイデア。文書タイプ$c_k$のもとで$x$の各要素は互いに独立だと考えるわけだ。こうして出来上がる分類器をナイーブベイズ分類器という。
分類器の性能は、$P(c_k|x)$の推定値の良さではなくて、$\hat{P}(c_k) \times \prod \hat{P}(x_j|c_k)$が正しい$c_k$において最大となるかどうかによって決まる。
ここでちょっと寄り道して、文書をどう表現するかという話。
情報検索システムのために文章の表現を作るための方法は実にたくさん提案されている。しかし、驚くべきことに、そしていささかがっくりすることに[←ほんとにこう書いてある]、言語学的知識や領域知識ぬきの構造的に単純な表現、すなわちbag of wordsをつくっちゃったほうがうまくいく模様である。なので、ここでもそう考えます。
さて。
文書がある単語を持つかどうかを二値変数$x_j$で表すとしよう。この場合、ナイーブベイズはもっと簡単に書けて[...中略...]、結局は下式となる。$p_{jk} = P(x_j = 1 | c_k)$として
$\log P(c_k|x)$
$= \log P(c_k)$
$+ \sum_j x_j \log (p_{jk}/(1-p_{jk}))$
$+ \sum_j \log(1-p_{jk}) $
$- \log P(x)$
最後の$\log P(x)$はどこのクラスでも同じだから、ふつうは無視する。
もし2クラスだったらもっと簡単になって... [数式略]
情報検索ではこのモデルを「二値独立モデル」という。二値独立モデルは、検索結果の上位項目に対して検索ユーザが関連性をフィードバックし、その判断を学習してランキングを改善する際に使えないかというので関心が持たれた。
二値独立モデルはいまではほとんど使われていない。その理由は、語の頻度を無視している点にある。文書の長さを無視しているという問題もある。
そこでいろんなバリエーションが提案された。
- 語の有無じゃなくて頻度を入力するという方向。頻度の統計的分布としては、ポワソン分布、ポワソン混合分布、負の二項分布などが検討された。たくさん研究が出たけど、結局のところ、二値独立モデルよりも優れているとはいいにくい。
- 多項モデル。語彙数を$d$として、長さ$f$の文書は$d$カテゴリの多項分布からの$f$回の独立なドローだと考える。文書の長さをうまく扱っているという長所もある。いっぽう、同じ単語が二回でてくるのを独立なドローと捉えるという奇妙があって、長い文書の事後対数オッズがすごく極端になりやすく、ランキングには向かない。というわけで、文章分類には使われているけど文書検索には用いられていない。
- 分布に頼らないアプローチ。確率的インデキシングというアプローチでは、文書の理想的な二値インデキシングがあると仮定し、観察されたインデクス語の生起はそのエビデンスだと捉えて事後対数オッズの期待値を求める。理想のインデキシングの確率はアドホックに計算する。[←よくわからん...] ほかにも、なんらかのノンパラメトリックなモデルで、特定の長さを持つ文章においてある語の頻度が観察される確率を求めるというアプローチもある。情報検索ではあんまりつかわれていないが今後有望。
さて、ナイーブベイズ分類器における独立性の仮定はそもそも不自然なわけで、これをなんとかしようという研究もある。３つの方向がある。
- 独立性の仮定を緩和する。機械学習ではどうだか知らんが情報検索ではうまくいってない。
- 独立性の仮定が不自然でないような特徴集合をつくる。その成否は判断が難しい。そういう提案はたくさんあるけど(たとえば句の生成)、ふつうは独立性の確保以外になんらかの固有の目的があるからだ。ともあれ、改善されたとしてもたいした効果ではない。
- なぜ独立性の仮定が本当は大事じゃないかを説明する。Cooperという人いわく、2クラスのナイーブベイズモデルでは、独立性の仮定は次の弱い仮定に置き換えることができる。
$\frac{P(x|c_1)}{P(x|c_2)} = \prod_j \frac{P(x_j|c_1)}{P(x_j|c_2)}$
彼はこれを"linked dependence"仮定と呼んでいる。
機械学習の分野では、独立性の仮定が破られているさまざまな状況でも、ナイーブベイズの仮定に基づく訓練手続きによって最適な分類器をつくることができるという理論的・実験的証拠が蓄積されている。Domingos & Pazzani (1997, Machine Learning)をみよ。[←へーそうなんすか]
云々。
論文：データ解析(2015-) - 読了：Lewis (1998) ナイーブベイズ、四十にして惑わず