情報の扱いのける 数学的基礎 確率 エントロピー 統計 確率分布 形式言語理論 計算量の理論.

Presentation on theme: "情報の扱いのける 数学的基礎 確率 エントロピー 統計 確率分布 形式言語理論 計算量の理論."— Presentation transcript:

1 情報の扱いのける 数学的基礎 確率 エントロピー 統計 確率分布 形式言語理論 計算量の理論

2 確率論 事象 e とは、ある確率変数 X の値が x であること： e: X=x
事象 e 　の確率を　p(e), p(X=x), p(x) 　などと書く。 全事象 e1, e2, ….. , eN 　（つまり事象数）とすると X=a とX=b　が同時に起こった場合の確率を同時確率といい、p(a,b)と書く。 条件付確率 ベイズの定理 従属性　p(A,B)>p(A)p(B) が普通だが、これはAが起こればある確からしさでBが起こるような場合もあるから。　 ←→ 排反性 　　　仮にAは起これば必ずBも起こるならBはAに従属するといい、 p(A,B)=p(A)=p(B) 独立性　Aが起こっても次にBが起こるかどうかは影響されない場合、AとBは独立といい、。 　　 p(A,B)=p(A)p(B)

3 条件付確率 C+A+B+AB=N C a a A AB B b

4 ベイズの定理の使い方（文書分類への応用 その１）
ベイズの定理の使い方（文書分類への応用　その１） インターネット上の文書（原理的には無限個ある）がいくつかの集合に分類されている。ターム t を含む文書が　C1とC2のどちらの分類に属するかどうかを予測したい。つまり確率 p(C1|t) と　p(C2|t)を求めたい。 しかし、相手が無限なので、数えて確率を出すわけにはいかない。 そこで、サンプルとして集めた文書集合における確率を使う。まず、文書集合を分類し、分類 C1,C2 に属する文書がターム t を含む確率 p(t|C1)， p(t|C2) は数えれば求まる。また、文書が分類 C に属する確率p(C)は、 　　（分類Cの文書数）/（サンプル文書集合の全文書数） 　　により求められる。そこでベイズの定理により 右辺の分子はサンプルの文書集合から分かっている。問題は分母のp(t)であり、これはインターネット上の全部の文書を見ないと分からない。しかし、近似として、インターネット上でターム t が現れる確率は一定値としてもよい。もっとも問題は　p(C1|t) と p(C2|t) のどちらが大きいかを知りたいのだから、分母は等しいので、分子だけで比較すればよい。

5 ベイズの定理の使い方（文書分類への応用 その２）
ベイズの定理の使い方（文書分類への応用　その２） インターネット上の文書（原理的には無限個ある）がいくつかの集合に分類されている。ターム t を含む文書が　C1とC2のどちらの分類に属するかどうかを予測したい。すでに確率 p(C1|t) と　p(C2|t)を求めたので、次にすることは、 p(C1|t) と p(C2|t)　うち最大のほうの分類を求めることである。 これは簡単なことだが、次のように書く。 C1,C2 のうち t によって分類される確率の高い分類 C-max argmax f(x) とは、f(x)を最大にする x を意味する

6 ベイズの定理の使い方（文書分類への応用 その３）
ベイズの定理の使い方（文書分類への応用　その３） 今まではターム１個による分類だったが、複数のタームt1,t2,…,tn　による分類に拡張しよう。 C-max=argmax p(Ci|t1,t2,.…,tn) ターム数が多いと t1,t2,.…,tn　がすべて含まれる文書がサンプル文書集合中に存在しないかもしれない。そこで、 argmax p(Ci|t1,t2,.…,tn)=argmax p(t1,t2,…,tn|Ci)p(Ci) しかし、このままでは事態は同じ。そこで、各タームの出現が独立であるとすると　argmax p(t1|Ci)p(t2|Ci)…p(tn|Ci)p(Ci) 各 p(tj|Ci)　はサンプル文書集合から容易に計算できる。

7 母集団と大数の法則 標本と母集団：　我々が観測により得たデータはあくまでも背後にある膨大な確率的集合すなわち母集団の標本 (sample)である。 確率や統計は観測により得られたデータから母集団の統計的性質を推測することである。 大数の法則 　　標本数が増えると、標本の平均値が母集団の平均値に近づく（確率収束する） 問題：もし、ふたつの事象が完全に従属（例えば、姉が選んだ服を１年後にかならず妹も選ぶから、姉の服Xと妹の１年後の服Yは従属）の場合、p(X)とp(Y)はどうような関係になるか？

8 平均と分散 サンプル集合における平均：母集団の期待値　 （母集団の）分散 サンプル集合における変動 サンプル集合における分散： 標準偏差：　

9 確率分布 正規分布：最もよく使われる分布 いろんな分布の変数Xを多数足し合わせた分布は正規分布に近づく。 （中心極限定理という）
　　（中心極限定理という） 二項分布（binominal distribution) 二項分布は、赤と白の玉が適当な割合　ｐ：１－ｐ　で入っている壷からn回玉を取り出したとき、赤がr回、白が残りn-r回取り出される確率。 二項分布の平均値は np　　、分散は np(1-p) である。 二項分布およびその極限であるPoisson分布は頻繁に使われる確立分布である。

10 エントロピー 事象の散らばり方あるいは random さの尺度
個々の事象（ある確率変数の個別の値）ではなく、ある確率変数の挙動全体を測る尺度。これをビットを単位とする情報量と呼ぶ。 こうみてもよい。 問題１：　裏表が等確率ででるコインを投げる場合のエントロピーは？ 問題２：　次の図のような通信路の受信側のエントロピーは？ただし、送られる０，１は等確率 p 1-p 1-q 1 1 q

11 相互情報量（エントロピー） 複数の確率変数の間にどれだけ相関（あるいは依存関係）があるかを測るために相互情報量が定義される。
　　１．まったく相似な振る舞いをするなら相互情報量＝０ 　　２．まったく独立なら各々のエントロピーの和 結合エントロピー　 条件付エントロピー（Xの値が与えられたという条件下でのYのエントロピー） 相互情報量 問題 ３：問題２の通信路の相互情報量を計算せよ。

12 確率分布 正規分布：最もよく使われる分布 いろんな分布の変数Xを多数足し合わせた分布は正規分布に近づく。 （中心極限定理という）
　　（中心極限定理という） 二項分布（binominal distribution) 二項分布は、赤と白の玉が適当な割合　ｐ：１－ｐ　で入っている壷からn回玉を取り出したとき、赤がr回、白が残りn-r回取り出される確率。 問題：　二項分布の平均値と分散を求めよ。 二項分布およびその極限であるPoisson分布は頻繁に使われる確立分布である。つまり、np=λという一定値にしたまま、nを無限大にした分布。式は、 問題：Poisson分布の平均と分散を求めよ。

13 不偏推定、一致性、有効性 確率や統計は観測により得られたデータから母集団の統計的性質を推測することである。 ある確率変数 x の母集団における統計量を t とする。 一致性：サンプル数を大きくすると、サンプル集合から得られる t の推定値が 真の（つまり母集団の）t に収束する。 不偏性：このとき、サンプル集合における x の値の平均が　 t に等しいことを不偏性という。 　　E(x)=t 　　また、 この性質を満たすE(x)　を不偏推定量という。 有効性：いかなる不偏推定量よりも分散が小さい推定量を有効推定量という。

14 最尤推定法 確率変数Xのサンプル観測値x1,x2,…,xnが与えられたとき、Xの母集団における尤もらしい推定値 t を求める。
サンプルの値が独立だとすると、同時確率は次のようになる。 最尤推定法とは、L(t)　（これを尤度と呼ぶ）を最大にするような t の値として最も尤もらしい t の値 t’ とする。つまり t’= argmax L(t)　 実際は、尤度のlogをとって、 t で微分し０とおいて解く。 問題：コインの表がn回中x回でた場合の二項分布の表が出る確率を最尤推定せよ。 問題：正規分布　　　　　　　　でサンプル観測値x1,x2,…,xnが与えられたときの母集団の正規分布の平均値と分散を最尤推定せよ。

15 尤度比 （likeli hood) ふたつの仮説のうちどちらがより尤もらしいかを調べる。例えば、ある文書 d がある分類のクラス c に属するか、属さないか ~c はその確率の比（これを尤度比という）が予め決められた閾値より大きいか小さいかで決める。実際は、尤度比の対数をとって計算することが多い。 この式の右辺の確率をさらにベイズの定理で書き換え、計算しやすくする場合もあり。

16 EMアルゴリズム　その１ 観測されたサンプルデータから内部状態が一意に特定できない場合には、最尤推定で母集団のパラメタ－を推定できない。そのような場合には Expectation & Maximization: 「期待値最大化」,略して 　　　EMアルゴリズム　と呼ばれる枠組みを用いる。 基本アイデア：観測データ　xi　について母集団のパラメタ－θをθ’に更新したときの対数尤度の差を最も大きく増加させる。

17 EMアルゴリズム　その２ 次の式が成り立つので、第２項は常に正。よって、第１項を最大化すればよい。 そこで 　　とおくと、第１項は 　　　Q(θ,θ’)-Q(θ,θ) となるので、結局、Q(θ,θ’)　を最大化するようにθ’を選べばよい。

18 EMアルゴリズム　その３　定式化 θに適当な初期値を与える θが収束するまで次のＥステップとＭステップを繰り返す。 　　Ｅステップ：Q(θ,θ’)を計算する。 　　Ｍステップ：　 　　　　　　　　によってθを更新する。

19 EMアルゴリズム その４ 例 混合分布モデルの推定
これを最大化する。ラグランジュ未定乗数法という簡単な方法を用いると、ｓつぎのような結果が得られる。