単純ベイズ分類器の最大の謎は何がどう Bayes なのか？というところだと 思った事のある人は居ませんか。 居ないすか。まぁ居なくてもいいです。わしは全然解らなかったので、 そこんところをちょっと追いかけてみました。 まず Bayes の定理です。ベイズ氏の名前の綴りって 非常に憶えにくいですね。毎回 web 引いて確認してますが、 それでも間違えます。 $$P(A|B) = \frac{P(B|A) P(A)}{P(B)}$$
おなじみのベイズの定理です。 \(P(B)\) は事象\(B\)の確率測度であって、 かつ、(当り前ですが)正の値をとります。 定理の証明ですが、右辺分母の \(P(B)\) を両辺にかければ どちらも \(P(A\cap B)\) となることで示せます。
一方、単純ベイズ分類器で使われる結合確率は、単語 \(w_i\) が 分類したいドキュメントのクラスタに出現する確率を \(P(W_i)\) とすると $$ \frac {\prod P(W_i)} {\prod P(W_i) + \prod (1-P(W_i))} $$
まぁ大概こんな式です。\(\prod\) は全部の積をとる操作で エクセルでもおなじみな \(\sum\) のカケ算版です。
みてのとおり、明らかにベイズの定理の体裁をしてない。 事前確率も尤度も影も形もないけんね。 一体どうなってんの？ どこらへんがベイズなの？ ここまでが問題提起、つまりこの記事が持つ非自明性の主張です。
以下 \(A\) の補集合を \(\bar{A}\) と書くことにします。 ベイズの定理の分母のところは
\(P(B) = P(B \cap A) + P(B \cap \bar{A}) = P(B|A)P(A) + P(B|\bar{A})P(\bar{A}) \)
と書けるので定理の右辺は
$$ \frac{ P(B|A)P(A)} {P(B|A)P(A) + P(B|\bar{A})P(\bar{A}) } $$
と書けます。\(P(B|A)\) はドキュメントが分類対象クラスタに属する時に 検査対象語彙 \(w_i\) が当該ドキュメントに出現する、という条件付き確率なので これはすなわち結合確率の式の方の項で言えば \(P(W_i)\) です。 一方 \(P(B|\bar{A})\) は \(P(\bar{W_i})\) です
$$ \frac{ P(\cap^i W_i)P(A)} {P(\cap^i W_i)P(A) + P(\cap^i \bar{W_i})P(\bar{A}) } $$
ここまでは全て自明な推論でした。 さて、ここからは残念ながら、あまり自明ではありません。 自明ではないことを自明であるように説明できれば値打ちがありますが、 今回はどうですかね。 読んだ全員が解るようにはならないかもしれません。 今のうちに謝っとくわ。ごめんよ。
まず、全ての \(W_i\) が互いに独立であると仮定します。 実際には自然言語のドキュメントにおける語彙の出現は独立ではないのですが そう仮定するのです。 なぜそういう仮定をするかというと、
からです。違う言い方をすればプログラムを書く手間の割りにうまく動くから、 という事です。 独立性の定義は \( P(\cap^i W_i) = \prod_i{P(W_i)} \) こうです。 補集合側は \(\prod_i (1-P(W_i))\) ですな。 これで、ベイズの定理の右辺はこうなります。
$$ \frac {\prod_i P(W_i) P(A)} {\prod_i P(W_i)P(A) + \prod_i (1-P(W_i)) P(\bar{A})} $$
さらに追加して \(P(A) = P(\bar{A})\) も仮定します。 これは、分類対象ドキュメントである確率はそうでない確率と半々という事です。 分母、分子を \(P(A)\) と \(P(\bar{A})\) で約分すれば、確かに単純ベイズ分類器で使うアルゴリズムと ベイズの定理が同じ式になります。 おお。 確かに単純ベイズ分類器はベイズの定理を使っているよ！ めでたしめでたし。
あんまし解ってませんが、以下ちょっと能書きをたれておきます。
この、結合確率を計算するアルゴリズムのどこがどうベイズかというと、 特定の語彙が分類対象となるドキュメントに出現している場合の 条件付き確率を出すのに、 条件なし確率を予め仮定したところに、 引いて来た手札を加味して計算する、という流儀が Bayesian というわけです。
ところが、アルゴリズムの中に入っていた条件無し確率(事前確率という用語を ベイズ統計では使うようです)は、同じ値が分母分子に出て来るために除されて(約分されて？)消滅してしまい、 ベイズなプロセスが隠蔽されてしまっているわけです。 この記事はそこを再び見えるようにする、という意図をもって書かれています。
この \(P(A)\) はたとえばスパムの判定であれば予め判っている場合もありますが、 一般にはかならずしもそうではないので、 場合が二つなら確率は半々、みたいなええかげんな(無理にかっこつけて 言えば一様分布を仮定する)方法で計算開始します。 そうすると、上で説明したとおり計算式が簡単になるという利点があります。 これで支障はないのか？という疑問があると思いますが、 多くの文書にはたくさんの語彙が出て来るわけで、 その結合確率は ほぼ 0 か ほぼ 1 に分布してしまい、 初期値である \(P(A)\) については、 0 とか 1 とかの極端な(まぁ0を選ぶとエラーですがw)値を選ばない限り 多少値をいじくっても、結果に大きな影響はありません。 式では全部まとめてかけざんする事になっていますが、 語彙が出て来るたびに、逐次ループをまわして計算し、出て来た \( P(A|B)\) を次のループの初期値に使う、という段取りで 考えると、より Bayesian な味わいが出るでしょう。
同時分布が(つまり結合確率が)初期値に大きく影響されるような場合はこのアルゴリズムを 採用するのは難しいかもしれない、とも言えるかもしれません。 実はこんなややこしい計算なんかせず Bayes の定理も使わんでも、 結合確率は簡単に計算できますが、 それではベイズ的味わいと 展望が全然ないし計算も自明で記事になりませんし。
[参考文献] 結合確率について http://www.mathpages.com/home/kmath267.htm
個人的には、レキシカルスコープなクロージャ(っていうんですか？ 用語良く知らないで使ってますがw)になってるところが最高です。 これは、かなり考える手間が省けます。 1.9 なら
irb(main):015:0> a=0
=> 0
irb(main):016:0> (0..100).gen{|a|a}
=> [0, 1, 2, 3, 4, 5, ..., 100]
irb(main):017:0> a
=> 0
aの値は変化しません。しかし 1.8では
irb(main):001:0> a=0
=> 0
irb(main):002:0> (0..100).gen{|a|a}
=> [0, 1, 2, 3, 4, 5, 6, 7, ..., 100]
irb(main):003:0> a
=> 100
1.8 ではブロック変数 a がブロック外部の a を 上書きして値が変わっています。
どちらが直観的であるか、というとわざわざ a はブロック内部の変数ですよ、 と宣言しているのに上書きしちゃうのは具合悪いでしょうし、 わざわざブロック変数ですよ、と断ってるのに、ブロックの外の値にアクセス できてほしい、と願う人は居ないでしょう。 そもそも初期化時にブロック内部の処理が値を入れてしまうので、 外部の値にはアクセスできないし。
ちなみにscheme なんかも1.9と同様に振るまいます。 この仕様が2.0では1.8の時代に戻ったりしたら、 自作ライブラリを全部 scheme に引っ越して、 Ruby 使うの止めると思います。
input method との通信方式には幾つかあって、最近は ibus というのが良いらしい
update したら今まで動いてた日本語入力が止まってしまったのだが、 何が動いていて入力できていたのか、そもそも把握していなかったので 直しようもない。 という事で最近の環境に引っ越してみた。
yuji@dedepo:~%sudo aptitude install ibus-anthy ibus-gtk ibus-qt4 yuji@dedepo:~%sudo update-alternatives --config xinput-ja_JP yuji@dedepo:~%im-switch -c
一回 logout して入り直して、 あとは gnome とかの設定メニューに ibus が出て来るので、 それをつついてキーバインドとかを変更するよろし。
この情報はむっちに教わりました。いつもありがとうございます。
正規表現と某オートマトンは同値、というような話を学部の頃勉強したことがある方も 居られると思いますが、 これは要するに、 「正規表現とはせいぜい文字列をちょちょいといじくりまわすのに便利なツール」 という程度の認識は間違っており、 案外深くて強力なのだという事でしょう。
それはそれとして、 「パターン某に合致したら、その合致した文字列をどうこうする」 みたいな処理はよくでてきます。 ワープロでいう「置換、検索」の置換のほうです。 ワープロの置換は条件として一致する文字列を指定するぐらいですが、 もっといろいろできるのが正規表現パワーの力なのです。 この、「条件に合う文字列」を 使った作業、というのはいまいちどう書けばいいのか判らず、 これまでは、その場凌ぎの変なコードを書いてごかましてきました。
str.gsub(/([0-9][0-9]\:[0-9][0-9])/, '\1'+"\n")
このほど、ようやくどう書けばいいのか判ったのでメモがわりに書いときます。 この処理では xx:yy のあとに改行を入れています。変数 \1 が一つめの 正規表現と一致した文字列 xx:yy を保持しています。 \1 を quote するのと、正規表現を () に入れておくのがコツみたいです。
なぜこう書けば動くのはよく判りません。 私はこの正規表現というやつが、かなり苦手です。