Document

情報の扱いのける
数学的基礎
確率
エントロピー
統計
確率分布
形式言語理論
計算量の理論
確率論
 事象 e とは、ある確率変数 X の値が x であること： e: X=x
 事象 e の確率を p(e), p(X=x), p(x) などと書く。
N
 全事象 e1, e2, ….. , eN （つまり事象数）とすると
 p( e i ) 1
i1
 X=a とX=b が同時に起こった場合の確率を同時確率といい、p(a,b)と書く。
 条件付確率
 ベイズの定理
p(a | b) 
p(b j | a) 
p(a,b)
p(b)
p(a | b j ) p(b j )
p(a)

p(a | b j ) p(b j )
iN1p(a | b i )p(bi )
 従属性 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)
条件付確率
p(a | b) 
p(a,b)
p(b)
C+A+B+AB=N
a
A
C
a
B
AB
b
AB
AB
p(a, b)
p(a | b) 
 N 
B  AB B  AB
p(b)
N
ベイズの定理の使い方（文書分類への応用その１）
 インターネット上の文書（原理的には無限個ある）がいくつかの集合に分類さ
れている。ターム t を含む文書が C1とC2のどちらの分類に属するかどうか
を予測したい。つまり確率 p(C1|t) と p(C2|t)を求めたい。しかし、相手が無
限なので、数えて確率を出すわけにはいかない。
 そこで、サンプルとして集めた文書集合における確率を使う。まず、文書集
合を分類し、分類 C1,C2 に属する文書がターム t を含む確率 p(t|C1)，
p(t|C2) は数えれば求まる。また、文書が分類 C に属する確率p(C)は、
（分類Cの文書数）/（サンプル文書集合の全文書数）
p(t | C)p(C)
p(C | t) 
により求められる。そこでベイズの定理により
p(t)
 右辺の分子はサンプルの文書集合から分かっている。問題は分母のp(t)で
あり、これはインターネット上の全部の文書を見ないと分からない。しかし、
近似として、インターネット上でターム t が現れる確率は一定値としてもよい。
もっとも問題は p(C1|t) と p(C2|t) のどちらが大きいかを知りたいのだから、
分母は等しいので、分子だけで比較すればよい。
ベイズの定理の使い方（文書分類への応用その２）
 インターネット上の文書（原理的には無限個ある）がいくつかの集合
に分類されている。ターム t を含む文書が C1とC2のどちらの分類
に属するかどうかを予測したい。すでに確率 p(C1|t) と p(C2|t)を求
めたので、次にすることは、
 p(C1|t) と p(C2|t) うち最大のほうの分類を求めることである。
 これは簡単なことだが、次のように書く。
 C1,C2 のうち t によって分類される確率の高い分類
 C-max  argmax p(Ci| t)  argmax p(t | Ci)p(Ci)
i
i
 argmax f(x) とは、f(x)を最大にする x を意味する
ベイズの定理の使い方（文書分類への応用その３）
 今まではターム１個による分類だったが、複数のターム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) はサンプル文書集合から容易に計算できる。
母集団と大数の法則
 標本と母集団：我々が観測により得たデータはあくまでも背後にあ
る膨大な確率的集合すなわち母集団の標本 (sample)である。
 確率や統計は観測により得られたデータから母集団の統計的性質
を推測することである。
 大数の法則
標本数が増えると、標本の平均値が母集団の平均値に近づく（確率
収束する）
 問題：もし、ふたつの事象が完全に従属（例えば、姉が選んだ服を１
年後にかならず妹も選ぶから、姉の服Xと妹の１年後の服Yは従属）
の場合、p(X)とp(Y)はどうような関係になるか？
平均と分散
 サンプル集合における平均：母集団の期待値
E(X)   xp(X  x)   xp(x)
xX
 （母集団の）分散
V(X)  E( (x - E(X)) )  E(X 2 ) - E(X) 2
 サンプル集合における変動
 サンプル集合における分散：
 標準偏差：
xX
2
分散
S(X) 
N

i 1
p(x i )( x i -
V(x) 
S(x)
N -1
1 N
2
 x p(x ))
i
i
N i 1
確率分布
 正規分布：最もよく使われる分布
1 ( x ) 2 /(2 2 )
n(x;  , ) 
e
2 
 いろんな分布の変数Xを多数足し合わせた分布は正規分布に近づく。
（中心極限定理という）
 二項分布（binominal distribution)
b(r; n, p) 
r
n-r
C
p
(
1

p)
n r
 二項分布は、赤と白の玉が適当な割合ｐ：１－ｐで入っている壷からn回玉を取り出
したとき、赤がr回、白が残りn-r回取り出される確率。
 二項分布の平均値は np 、分散は np(1-p) である。
 二項分布およびその極限であるPoisson分布は頻繁に使われる確立分布である。
エントロピー
 事象の散らばり方あるいは random さの尺度
 個々の事象（ある確率変数の個別の値）ではなく、ある確率変数の挙動全体
を測る尺度。これをビットを単位とする情報量と呼ぶ。
H(X)   p(x) log 2
xX
1
p(x)
 こうみてもよい。
H(X)  E(log 2
1
)
p(X)
 問題１：裏表が等確率ででるコインを投げる場合のエントロピーは？
 問題２：次の図のような通信路の受信側のエントロピーは？ただし、送られ
p
る０，１は等確率
0
0
0
1
1-p
1-q
1
q
相互情報量（エントロピー）
 複数の確率変数の間にどれだけ相関（あるいは依存関係）があるかを測るために相
互情報量が定義される。
１．まったく相似な振る舞いをするなら相互情報量＝０
２．まったく独立なら各々のエントロピーの和
 結合エントロピー
H(X,Y)     p(x, y)log 2 p(x, y)
xX yY
 条件付エントロピー（Xの値が与えられたという条件下でのYのエントロピー）
H(Y| X)   p(x)H(Y| X  x)   p(x)[   p(y| x)log 2 p(y| x) ]
xX
xX
    p(y,x)log 2 p(y| x)
yY
xX yY
H(X,Y)  H(X) H(Y| X)
 相互情報量
I(Y;X)  H(Y) H(Y| X)  H(X) H(Y) H(X,Y)
p(x, y)

 p(x, y)log 2
p(x)p(y)
xX, yY
 問題３：問題２の通信路の相互情報量を計算せよ。
確率分布
 正規分布：最もよく使われる分布
1 ( x )2 /( 2 2 )
P( X  x)  n(x;  , ) 
e
2 
 いろんな分布の変数Xを多数足し合わせた分布は正規分布に近づく。
（中心極限定理という）
 二項分布（binominal distribution)
P( X  x )  b(x; n, p)  n C x p x (1 p) n-x
 二項分布は、赤と白の玉が適当な割合ｐ：１－ｐで入っている壷からn回玉を取り出
したとき、赤がr回、白が残りn-r回取り出される確率。
 問題：二項分布の平均値と分散を求めよ。
 二項分布およびその極限であるPoisson分布は頻繁に使われる確立分布である。つま
り、np=λという一定値にしたまま、nを無限大にした分布。式は、
 x 
P( X  x)  e
x!
 問題：Poisson分布の平均と分散を求めよ。
不偏推定、一致性、有効性
 確率や統計は観測により得られたデータから母集団の統計的性質
を推測することである。
 ある確率変数 x の母集団における統計量を t とする。
 一致性：サンプル数を大きくすると、サンプル集合から得られる t の
推定値が真の（つまり母集団の）t に収束する。
 不偏性：このとき、サンプル集合における x の値の平均が t に等し
いことを不偏性という。
E(x)=t
また、この性質を満たすE(x) を不偏推定量という。
 有効性：いかなる不偏推定量よりも分散が小さい推定量を有効推定
量という。
最尤推定法
 確率変数Xのサンプル観測値x1,x2,…,xnが与えられたとき、Xの母集団に
おける尤もらしい推定値 t を求める。
 サンプルの値が独立だとすると、同時確率は次のようになる。
n
p t ( x1, x 2 ,.....,x n )   p t ( x i )  L(t)
i1
 最尤推定法とは、L(t) （これを尤度と呼ぶ）を最大にするような t の値として
最も尤もらしい t の値 t’ とする。つまり t’= argmax L(t)
 実際は、尤度のlogをとって、 t で微分し０とおいて解く。
n 

log L(t)   log p t ( x i )  0
t
i1t
 問題：コインの表がn回中x回でた場合の二項分布の表が出る確率を最尤推
定せよ。
 問題：正規分布 N (  , 2 ) でサンプル観測値x1,x2,…,xnが与えられたとき
の母集団の正規分布の平均値と分散を最尤推定せよ。
尤度比（likeli hood)
 ふたつの仮説のうちどちらがより尤もらしいかを調べる。例えば、あ
る文書 d がある分類のクラス c に属するか、属さないか ~c はその
確率の比（これを尤度比という）が予め決められた閾値より大きいか
小さいかで決める。実際は、尤度比の対数をとって計算することが多
い。
  or  L(d)  log
p(c | d)
p(c | d)
 この式の右辺の確率をさらにベイズの定理で書き換え、計算しやす
くする場合もあり。
EMアルゴリズムその１
 観測されたサンプルデータから内部状態が一意に特定できない場合
には、最尤推定で母集団のパラメタ－を推定できない。そのような場
合には Expectation & Maximization: 「期待値最大化」,略して
EMアルゴリズムと呼ばれる枠組みを用いる。
 基本アイデア：観測データ xi について母集団のパラメタ－θをθ’に
更新したときの対数尤度の差を最も大きく増加させる。
P (x )
log P ( x i )  log P ( x i )  log  i
P ' '( x i )
P ( y, x i )P ( y | x i )
  P ( y | x i ) log[  '
]
P ( y, x i )P '( y | x i )
y
P ( y, x i )
P ( y| x i )
  P ( y | x i ) log[  '
]  P ( y | x i ) log[ 
]
P ( y, x i ) y
P '( y | x i )
y
EMアルゴリズムその２
 次の式が成り立つので、第２項は常に正。よって、第１項を最大化す
ればよい。
Q(x)
P(x)log
0

P(x)
x
 そこで
Q( , ')   P ( y | x i ) log P '( y | x i )
y
とおくと、第１項は
Q(θ,θ’)-Q(θ,θ) となるので、結局、Q(θ,θ’) を最大化するようにθ’を
選べばよい。
EMアルゴリズムその３定式化
1.
2.
θに適当な初期値を与える
θが収束するまで次のＥステップとＭステップを繰り返す。
Ｅステップ：Q(θ,θ’)を計算する。
Ｍステップ：   argmax Q( , ')

によってθを更新する。
EMアルゴリズムその４例
混合分布モデルの推定
M
P(x)   i Pi ( x )
j1
NM
Q( , ')    P ( j| x i ) log P '( j, x i )
i1j1
これを最大化する。ラグランジュ未定乗数法という簡単な方法を用いると、ｓ
つぎのような結果が得られる。
1
'
j
N

 jP j ( x i )
N i1M  jPj ( x i )
j1

Download Report