多項分布(重要)

性質

ベルヌーイ試行は得られる結果が2通りだと仮定したが、これがm通りだとすると得られる結果はm個となる。 この試行(隠された試行)をN回繰り返す、という試行の結果を近似するのが多項分布である。
隠された試行において、得られる事象をE_{1}, \ldots, E_{m}とすると、その発生確率ベクトル{\bf \theta} = [\theta_{1}, \ldots, \theta_{m}](ただしpiはEiの発生確率)がパラメータとなる。
試行の結果はどうとでも書くことができるが、ここではE_{1}, \ldots, E_{m}の発生回数のベクトル{\bf n}=[n_{1}, \ldots, n_{m}](ただし、niはEiの発生回数)とする。この{\bf n}はぱっと見m!通りあるのかな?
これを確率変数と見なす。当然この確率変数は\sum^{m}_{i=1}n_{i}=1, n_{i} \geq 0 \forall i をみたす。
試行回数をN、パラメータを{\bf \theta}とした多項分布の確率関数は以下となる。

\displaystyle  Multinominal({\bf n};{\bf \theta}) = \frac{N!}{\prod^{m}_{i=1}n_{i}!}\prod^{m}_{i=1}\theta_{i}^{n_{i}}

係数部の考え方はn1回E1が発生して、N-n1回それ以外が発生する、というのを繰り返して行く、というものなので式に表してみました。

\displaystyle  {}_{N} C_{n_{1}} \times  {}_{N-n_{1}} C_{n_{2}} \times  {}_{N-n_{1}-n_{2}} C_{n_{3}} \times \ldots \times {}_{N-\ldots -n_{i-1}} C_{n_{i}} \times \ldots \times {}_{N-\ldots -n_{m-1}} C_{n_{m}}\\ =  \frac{N!}{n_{1}!(N-n_{1})!} \times \frac{(N-n_{1})!}{n_{2}!(N-n_{1}-n_{2})!} \times \ldots \times \frac{(N-\ldots -n_{i-1})!}{n_{i}!(N-\ldots -n_{i})!} \times \ldots \times \frac{(N-\ldots -n_{m-2})!}{n_{m-1}!(N-\ldots -n_{m-1}!)} \times \frac{(N-\ldots -n_{m-1})!}{n_{m}!(N-\ldots -n_{m}!)} \times \\ =\frac{N!}{n_{1} \times \ldots \times n_{m} \times 0!} \\ =\frac{N!}{\prod^{m}_{i=1}n_{i}!}

多項分布はいろいろな例を考えることができる。これは楽しい。
例として、

を挙げておく。 他にもおもしろい例があれば何か書きたい。

ひとりごと

非常に重要な分布である多項分布について書いた。言語処理では多項分布は頻出であるが、暗黙のうち仮定されていることが多く、僕も最近まで軽視していた。が、ほとんど多項分布を仮定しているので、これを理解すると読書などがはかどりそうだ。次はなにを書こう。気になるのはベクトルの勾配の話かなぁ。勾配上ったら局所的最適解にたどり着くらしいけど、なんで?って感じなんですよね笑。そんな魔法みたいな話、まだ信じられないんです笑。

二項分布

性質

試行:ベルヌーイ試行をN回行う
隠された事象:ベルヌーイ試行の結果、得られる 二つ の事象ETRUE, EFALSE
(これが、二項分布の二)
根元事象:N回のうち、n回ETRUE(つまりN+1個の根元事象)
標本空間:\Omega = \{0, 1, \ldots, N\}
パラメータ:試行回数N、ベルヌーイ試行においてETRUEが発生する確率p
確率関数:

\displaystyle  Binominal(x;p) = {}_N C_x p^{x} (1-p)^{N-x}

ベルヌーイ試行をN回行うような実験において適用される。
聞き飽きた例題かもしれないが、例としてコイントスをN回行う実験をとりあげる。 p=\frac{1}{2}である。 このとき、x回表が出たときの確率は、

\displaystyle  Binominal(x;p=\frac{1}{2}) = {}_N C_x \frac{1}{2}^{x} \frac{1}{2}^{N-x} \\ \phantom{Binominal(x;p=\frac{1}{2})} = \frac{N!}{x!(N-x)!} \frac{1}{2^{N}}

ひとりごと

うーん、解釈が微妙な気がする。 次はいよいよ多項分布なのだけれど、ここの解釈しっかりしておきたいな。 ベルヌーイ分布は根元事象が2つだけれど、これがm個になった分布ってなんなんだろう。 N=1の二項分布はベルヌーイ分布だろうから、N=1の多項分布ってとこかな。

ベルヌーイ分布

確率変数Xがパラメータpのベルヌーイに従う。

根元事象は2つ。
試行においてある条件を満たす(TRUE), 満たさない(FALSE)
X={TRUE, FALSE}
p: x ∈ X がTRUEとなる確率
確率密度関数:

\displaystyle  Bernoulli(x;p) = \delta(x, TRUE)p + \delta(x, FALSE)(1-p) \\ \phantom{Bernoulli(x;p)} = \delta(x, TRUE)p + (1-\delta(x, TRUE))(1-p) \\ \phantom{Bernoulli(x;p)} = p^{\delta(x, TRUE)}(1-p)^{(1-\delta(x, TRUE))}

例.コイントス
聞き飽きたであろう例。
コイン1枚をトスして表か裏かを見る試行を、ベルヌーイ試行とみなす。
発生する事象は
ETRUE:表が出る(TRUE)
EFALSE:裏が出る(FALSE)
の二つである。
X={ETRUE, EFALSE},
p:x=ETRUEとなる確率(ただし、x ∈ X)
とし、Xをベルヌーイ分布に従うみなす。

さて、今コイン1枚をトスして(試行を行い)表が出たとする。
この確率は、先ほどの仮定により、以下のようになる。

\displaystyle  Bernoulli(x;p) = p

どうように裏が出たとしたとき、この確率は以下のようになる。

\displaystyle  Bernoulli(x;p) = 1-p

なんともシンプルである。
今回記述するにあたり、「仮定」や「みなす」という言葉をあえて使った。 これが自分なりの解釈だ。次は二項分布。

単語の出現確率を求める(理論編)

これ、最近やっと概観がつかめてきた気がするので、頭の整理もかねて書きたいと思います。

さて、あまり抽象的な話だと何をやってるんだ? となってしまうので目的を定めました。

目的:単語の出現確率を求める

ということで以下の3ステップで行います。

  1. 現実に直面
  2. モデルの選択
  3. 推定

現実に直面

イメージ

現実は容赦がありません。 カイジ風に言うならば、圧倒的な現実! 我々は圧倒的な現実に直面すると、 「どんな確率だよ…」 とぼやいたりします。 これが今回の話の本質です。

さて、コーパスからどの単語が何回出現した、という標本が得られたとします。 これが現実です。そして先ほどの疑問をぶつけてみましょう。 「どんな確率だよ…」 言葉を変えると、

疑問:その現実、どんな確率で発生したものなのですか?

整理

コーパス中の総単語数をN、総異なり語数をKとします。
コーパス中で出現した単語集合をV=\{w_{1}, \ldots, w_{K}\}とし、 単語w_{i}の出現回数をn_{i}とします。 そうすると、
事象:Ei:単語wiが生起する(K個、総異なり語数)
試行:N回(総単語数のこと、総異なり語数ではない)
と整理できます。

つまりコーパスが構築されるまでにこの確率空間において、N回の試行が行われたと考えるわけです。 そして、この結果得られた標本を{\bf n}^{(sample)} = [n_{1}, \ldots, n_{K}]とします。 次に、この標本が従う確率分布を 仮定 します。

モデルの選択

イメージ

先ほど標本をベクトルで表現しましたが、 そもそもその標本はどうやって生成されたのでしょうか? 言い換えるとどんなモデルから生成されたのでしょうか? ここで、

得られた標本は、ある確率分布によって生成された

と解釈します。 この確率分布を生成モデルなんて呼んだりするのかなぁ?

整理

今回は多項分布を 仮定 します。 (この多項分布、非常に重要なので別記事にまとめます。この仮定というのが非常に重要です。なぜなら、何を仮定してもよいからです。ここ、大事です。) 確率変数{\bf n}が試行回数Nの多項分布Multi({\bf n};{\bf p})に従うとします。 ここで、{\bf p} = [p_{1}, \ldots, p_{K}]はパラメータであり、 piは事象Eiの発生確率とします。 多項分布の確率関数は以下です。

\displaystyle  Multi(n;{\bf p}) = \frac{N!}{\prod^{K}_{i=1}n_{i}!}\prod^{K}_{i=1}p^{n_{i}}_{i}

推定

最適化問題として定式化

さて、パラメータを適当に{\bf p} = [p_{1}, \ldots, p_{K}]と定めた時に、 {\bf n}^{(sample)} = [n_{1}, \ldots, n_{K}]が得られる確率(尤度)Likelihood({\bf p})はいくらでしょうか?

\displaystyle  Likelihood({\bf p}) = Multi(n^{(sample)};{\bf p}) \\ \phantom{Likelihood({\bf p})} = \frac{N!}{\prod^{K}_{i=1}n_{i}!}\prod^{K}_{i=1}p^{n_{i}}_{i}

これで我々の目的は達成されました。 疑問を再掲しておきます。

疑問:その現実、どんな確率で発生したものなのですか?

しかしながら、求めた確率はパラメータ{\bf p}に依存しています。(尤度は{\bf p}の関数とも見える) そこで、今ある標本が生起する確率を最大化するパラメータを決め、モデルを完成させます。 つまり尤度を最大化するパラメータ{\bf p}を求めます。 これは対数をとっても同じなので、対数尤度を最大化するパラメータをもとめることにします。 ここからは最適化の話です。以下の最適化問題を解きます。

\displaystyle  max. \hspace{0.5cm} \log{Likelihood({\bf p})} \\ s.t. \hspace{0.5cm} \sum^{K}_{i=1}p_{i} = 1 \\ \phantom{s.t. \hspace{0.5cm}} p_{i} \geq 0 \hspace{0.2cm} \forall i

最適化問題を解く

ラグランジュの未定乗数法(Lagrange Multipliers)で解きます。 ラグランジュ乗数α を導入し、ラグランジュ関数L(\bf{p}, \alpha)は以下のようになる。

\displaystyle  L({\bf p}, \alpha) = \log{Likelihood({\bf p})} + \alpha (\sum^{K}_{i=1}p_{i} - 1) \\ \phantom{L({\bf p}, \alpha)} = \log{\frac{N!}{\prod^{K}_{i=1}n_{i}!}\prod^{K}_{i=1}p^{n_{i}}_{i}} + \alpha (\sum^{K}_{i=1}p_{i} - 1) \\ \phantom{L({\bf p}, \alpha)} = \log{N!} - \sum^{k}_{i=1}\log{n_{i}!} + \sum^{K}_{i=1} n_{i} \log{p_{i}} + \alpha (\sum^{K}_{i=1}p_{i} - 1) \\

パラメータpi及びαで微分して、以下の連立方程式を得る。

\displaystyle  \frac{\partial L({\bf p}, \alpha)}{\partial p_{i}} = \frac{n_{i}}{p_{i}} + \alpha = 0 \\ \frac{\partial L({\bf p}, \alpha)}{\partial \alpha} = \sum^{K}_{i=1}p_{i} - 1 = 0

これを解いて、

\displaystyle  \alpha = - \sum^{K}_{i=1}n_{i}, \hspace{0.5cm} p_{i} = \frac{n_{i}}{\sum^{K}_{i=1}n_{i}}

まとめ

単語の出現確率を多項分布を仮定して最尤推定しました。 その結果は、単語の出現確率は単語の頻度と一致することが示せました。 大事なのは多項分布を仮定しているということ。 何を仮定しているか、というのは常に意識したいですね。

nltkのソースを読む | (1) nltk.probability

こんばんは。
眠れないのでnltkのソースを読もうと思います。

今回のターゲットはnltk.probabiltyです。
本で学んでいると何かと謎の多い確率分布ですが、実際どう使ってるのか、というのを少しでもかいま見れたら成功です。
まぁ寝る前のちょっとしたお楽しみということで固くならずに読もうと思います。

さて、いずれは全部読むつもりですが、今回はFreqDistとMLEProbDistを読もうと思います。
基本的に使うのがこの二つだと思うからです。
そして使うコーパスはnltk.corpus.brownです。

まぁipythonを起動してこんな感じでことを進めましょう。

import nltk
fd = nltk.FreqDist(nltk.corpus.brown.words())

これで単語数なんかが出せちゃいます。
便利なものです。
ここは別に読むべきソースもないので、割愛します。
次に

mlefd = nltk.MLEProbDist(fd)

これで最尤推定したことになります。
便利なものですねぇ。
MLEProbDistのソース(以下)を読むとわかるのですが、こいつ、実はなにもしていません。

749: def prob(self, sample): 
750:     return self._freqdist.freq(sample)   

最尤推定はそのsampleの出現回数を総単語数で割ってやればいいので(後日書けたらいいなぁ)、結局いわゆる単語の頻度と同じなのです。
なのでMLEさんは指定されたsampleの頻度を返しています。実際

In [23]: fd.freq("The")
Out[23]: 0.006250473651213581
In [25]: mlefd.prob("The")
Out[25]: 0.006250473651213581

次はELEですかね。今から読もうかな。

Pythonでgoogle検索

この、ありふれたテーマについて書きましょう。
方法がいろいろありすぎて、1日ほど費やしてしまった。
そして、まだ完全な方法は見つけることができていない。
とりあえず現状は以下。

google.pyを使う(とても楽

APIを使うためのKEYとかを取得しなくていいので楽。
作者様に感謝。
↑からgoogle-1.04.zipをDownloadして

unzip google-1.04
cd google-1.04

インストールする前に、以下のプログラムでテストしてみた。

1:  from google import search
2:  from BeautifulSoup import BeautifulSoup
3:  import urllib
4:  
5:  for url in search("nktmemo", stop=20, lang="en"):
6:      soup = BeautifulSoup(urllib.urlopen(url))
7:      print soup.find("title").text

実際にnktmemoでGoogleで検索するとTOP4は以下のようになった。
これが理想的。

1:  nktmemo
2:  前のページ - nktmemo
3:  nktmemo java_swingでマインスイーパ
4:  nktmemo | Programming, Statistics, NLP, Python, and so on.

実際の結果は以下。

1:  change the theme of nktmemo | nktmemo
2:  various way to read files(Python tips) | nktmemo
3:  About | nktmemo
4:  org2blogでWordPressに投稿 | nktmemo

実際の結果と違いますが、Googleの検索結果は時々刻々と変化しているのでまぁいいでしょう。
というわけでこのままインストールしました。(以下

python setup.py build
sudo python setup.py install

Macでの日本語入力時のキー操作

Windowsユーザが他OS例えば、Macで日本語入力を行うときに必ず思うのが
F10がない!だと思う。
F7~10を使う方法はありますが、せっかくMacにしたんだから
Macライクなキー操作になれようじゃありませんか。
いろいろあるみたいですけど、僕が気に入ったのは以下です。
日本語入力時に以下のキーを押すことで、ひらがな→英数、ひらがな→カタカナの変換を可能にします。

Control + a or Control + ; ひらがな→英数
Control + l ひらがな→全角英数
Control + k ひらがな→カタカナ

半角カタカナが見つからなかった。
これ使ってる人あんまりいないっぽいなぁ。