第5回

知識処理論（第５回）
２０１５年５月１３日
ノンパラメトリック法
杉山将
[email protected]
http://www.ms.k.u-tokyo.ac.jp
パターン認識
2
入力パターンをカテゴリに割り当てる
識別関数を構成する問題
問題に合わせて人間が識別関数を設計
 データから自動的に識別関数を学習

パターン
カテゴリ
識別関数
y  f (x )
xR
d
3
y {1,2,, c}
統計的パターン認識
3
訓練標本：属するカテゴリが既知のパターン
d
xi  R
n
{( xi , yi )}i 1
yi {1,2,, c}
統計的パターン認識：訓練標本の統計的な
性質を利用して識別関数を学習する
仮定：
( xi , yi )
i.i.d.
p( x, y)
i.i.d. (independent and identically distributed)
独立に同一の分布に従う
理想的なパターン分類法
事後確率 p ( y | x ) ：与えられたパターン x が
a
クラス y に属する確率
b
c
事後確率を最大にするカテゴリにパターンを
分類すれば，パターンの誤識別率が最小に
なる．
f ( x)  arg max p( y | x)
y
実際には事後確率は未知なので，訓練標本
から推定しなければならない．
4
生成モデルに基づいたパターン認識
5
ベイズの定理を用いれば，
p( x | y ) p( y )
p( y | x ) 
 p( x | y ) p( y )
p( x )
事後確率
条件付き確率事前確率
条件付き確率：クラス y に属するパターン xの分布
事前確率：クラス y の存在確率
事後確率を直接推定するのは
x
y
難しいので，代わりに条件付き
a
確率と事前確率を推定し，識別
b
c
関数を構成することにする．
事前確率の推定
p( y | x )  p( x | y ) p( y )
事後確率
条件付き確率事前確率
事前確率は離散的な確率分布なので，
単純にそのカテゴリに含まれる標本の
割合で推定する．
pˆ ( y ) 
ny
n y ：カテゴリ y に属する
訓練標本の数
n
大数の法則より，一致性が保証される．
p
ˆp( y ) 
 p( y )
(n  )
6
条件付き確率の推定
7
p( y | x )  p( x | y ) p( y )
事後確率
条件付き確率事前確率
条件付き確率は連続的な確率分布なので，
事前確率のように単純には推定できない．
以後，簡単のため，条件付きでない確率密度
n
関数 p (x ) を全訓練標本 {xi }i 1から推定する
問題を考える．
カテゴリ y に関する条件付き確率 p ( x | y ) を
推定するときは， y に属する n y 個の標本のみ
を用いればよい．
確率密度関数の推定法
8
パラメトリック法：有限次元のパラメータを持つ
パラメトリックモデルを用いて確率密度関数を
推定する
最尤推定法
 ベイズ推定法

q( x; )
ノンパラメトリック法：それ以外の方法
カーネル密度推定法
 最近傍密度推定法

注意：無限次元のパラメータを持つモデルを
用いる方法はノンパラメトリック法に分類される．
パラメトリック法
9
モデルが真の分布と（大体）合っていれば，
パラメトリック法は少ない標本でも精度が良い．
しかし，モデルが大きく外れていたら，いくら
標本数を増やしても精度は向上しない．
標本数：５
標本数：１００００
対処法：モデルを変える／モデルを使わない
講義の流れ
1.
2.
3.
4.
ノンパラメトリック法の基礎（第12章）
カーネル密度推定法（第12章）
最近傍密度推定法（第13章）
最近傍識別器（第13章）
10
ベルヌーイ試行
11
 ベルヌーイ試行(Bernoulli trials)：成功する確率，
失敗する確率が
の実験を同じ条件で独立
に繰り返す
成功
実験
失敗
 例：コインを投げて表が出るか裏が出るか
二項分布
 二項分布(binomial distribution)：
回のベルヌーイ試行に対して，実験が回
成功する確率
 回成功・
回失敗：
 順番を入れ替えたときの組み合わせ数：
12
二項分布の期待値と分散
 期待値：
成功確率が
成功回数が
で回実験を行ったとき，平均
であることは直感的にもわかる
 分散：
分散は
のとき最大になる．これは，
成功と失敗の確率が五分五分のときに予想が
難しいという直感と合っている
13
二項分布の例
14
 実験の成功率を変えたとき
成功率が低い
五分五分
成功率が高い
最も単純なノンパラメトリック法：
ヒストグラム法
15
 ヒストグラム法(histogram method):単純にヒストグラ
ムを用いて確率密度関数を推定する方法
 パターン空間を適当に分割する
（必ずしも同じ形に分割する必要はない）．
 各分割内に入る訓練標本を数える．
 積分が１になるように正規化する．
 非常に単純な方法なので
便利であるが・・・
ヒストグラム法の問題点
 領域間で不連続
 領域の分割の仕方を決めるのが難しい
もう少し工夫した方法が必要
16
ノンパラメトリック法の表記
17
ある注目点 x での確率密度 p (x) を推定する
 R ：xを含むパターン空間 D 内のある領域(region)
 V ： R の体積(volume)
V   dx
R
 P：あるパターン x が R に入る確率
p (x )
P   p( x )dx
R
R
 k ： n 個の訓練標本のうち
R に入っている個数
P
V
D
ノンパラメトリック法の基礎
18
 確率 P を二つの方法で近似する．
A) k, n を用いれば，
Pk n
B) 注目点 x を用いれば，
P  Vp(x)
 これらより
積分の長方形近似
p ( x )
k
p( x' ) 
nV
P
x
V
D
近似Ａの良さ
19
Pk n
 n 個の訓練標本のうち k 個が R に入る確率は
二項分布に従う．
確率： n Ck P (1  P )
k
P  0.1
n k
期待値： nP
分散： nP (1  P )
P  0.5
P  0.9
近似Ａの良さ（続き）
Pk n
 平均的にはぴったり P  k n ．分散は？
 相対的な分散が重要なので期待値を１に
揃える．
k
z
nP
1 P
E z   1, V z  
nP
 P が大きい方が分散が小さくなり，近似の
精度が良い
領域 R は大きい方が良い！
20
近似Ｂの良さ
21
P  Vp(x)
積分の長方形近似は，p (x ) が R 内でほぼ
一定値をとるとき，精度が良い．
領域 R は小さい方が良い！
p ( x )
P
x
V
D
領域の決め方（続き）
22
k
p( x ) 
nV
全体の近似精度を上げるためには，領域 R を
程よい大きさに決める必要がある．
訓練標本を用いて領域 R を決める．
パーゼン窓法，カーネル密度推定法：
R の形を決め V を固定したもとで k を標本から決定
 最近傍密度推定法：
R の形を決め k を固定したもとで V を標本から決定

講義の流れ
1.
2.
3.
4.
ノンパラメトリック法の基礎（第12章）
カーネル密度推定法（第12章）
最近傍密度推定法（第13章）
最近傍識別器（第13章）
23
パーゼン窓法
24
領域 R として，ある点 x を中心とする一辺の
長さが h の超立方体(hypercube)を用いる．
 体積 V  h d
x
R
 R に入る標本数
n
D
 x  xi 
h/2 h/2
k  W 

 h 
i 1
1 max | x (i ) | 12
W ( x)  
otherwise
0
パーゼン窓関数
(Parzen window function)
x  ( x , x , x )
(1)
(2)
(d ) T
 x  xi 
W

 h 
1
xi
h/2 h/2
R
D
パーゼン窓法
25
パーゼン窓法(Parzen window method):
1
pˆ ( x )  d
nh
 x  xi 
W


 h 
i 1
n
k
p( x ) 
nV
パーゼン窓法の特徴
与えられた標本からパターン領域の分割を
適応的に決定できるため，ヒストグラム法の
ようにあらかじめ領域の分割の仕方を決定
しておく必要が無い．
領域間での不連続性は未解決．
領域の分割の仕方を決める必要は無いが，
パーゼン窓関数のバンド幅 h を適切に
決める必要がある．
26
カーネル密度推定法
27
パーゼン窓法の不連続性を解決したい
カーネル関数(kernel function) K (x ) ：

D
K ( x )dx  1
K ( x )  0 for all x  D
カーネル密度推定法(kernel density estimation):
1
pˆ ( x )  d
nh
 x  xi 
K


 h 
i 1
n
h :バンド幅(bandwidth)
カーネル密度推定法の例
ガウスカーネル関数：
1
1 T
K ( x) 
exp(

2 x x)
d /2
( 2 )
28
一般化
1
pˆ ( x )  d
nh
 x  xi 
K


 h 
i 1
n
バンド幅を一つのパラメータ h で制御すると
自由度が小さい．
バンド幅行列(bandwidth matrix) H ：
正値対称行列
1 n
1

pˆ ( x ) 
K
H
( x  xi ) 

n | H | i 1
29
例
h
H
30
実行例
31
myrand.m
clear all
n=10000; x=myrand(n);
バンド幅
h  0 .1
function x=myrand(n)
x=zeros(1,n); u=rand(1,n);
flag=(0<=u & u<1/8);
x(flag)=sqrt(8*u(flag));
flag=(1/8<=u & u<1/4);
x(flag)=2-sqrt(2-8*u(flag));
flag=(1/4<=u & u<1/2);
x(flag)=1+4*u(flag);
flag=(1/2<=u & u<3/4);
x(flag)=3+sqrt(4*u(flag)-2);
flag=(3/4<=u & u<=1);
x(flag)=5-sqrt(4-4*u(flag));
モデル選択
32
カーネル密度推定法の推定結果は，
バンド幅 h の選び方に依存する．
実際にはバンド幅を程よい値に設定
しなければならない！
尤度交差確認法で選択する
バンド幅：小さすぎ
h  0 .01
バンド幅：適切
h  0 .1
バンド幅：大きすぎ
h  0 .5
尤度交差確認法
訓練標本 {xi }in1 を t 個の重なりの無い
t
部分集合 {Ti }i 1 に分ける．
T1
…
推定用
T j 1
Tj
確認用
T j 1
…
Tt
推定用
 j 番目の部分集合 T j に含まれる訓練標本
を使わずに確率密度関数を推定する．
pˆ T j ( x )
33
尤度交差確認法（続き）
T1
…
推定用
T j 1
Tj
T j 1
確認用
…
34
Tt
推定用
 T j に含まれる標本の対数尤度を計算する．
1
LCV j 
log pˆ T ( x )

| T j | xT
j
j
これを全ての j に対して行ない，平均する．
1 t
LCV   LCV j
t j 1
尤度交差確認法(likelihood cross validation)
実行例
35
５分尤度割交差確認：
h
バンド幅：小さすぎ
h  0 .01
バンド幅：適切
h  0 .1
バンド幅：大きすぎ
h  0 .5
カーネル密度推定法：まとめ
ノンパラメトリック法：パラメトリックモデル
を用いない確率密度関数の推定法
ノンパラメトリック法では，領域の大きさを
適当に決める必要がある．
パーゼン窓法：領域の形と体積を固定し，
標本数をデータから決定する
カーネル密度推定法：パーゼン窓を
滑らかなカーネル関数に置き換えた方法
36
講義の流れ
1.
2.
3.
4.
ノンパラメトリック法の基礎（第12章）
カーネル密度推定法（第12章）
最近傍密度推定法（第13章）
最近傍識別器（第13章）
37
ノンパラメトリック法の表記
38
ある注目点 x での確率密度 p (x) を推定する
 R ：xを含むパターン空間 D 内のある領域(region)
 V ： R の体積(volume)
V   dx
R
 P：あるパターン x が R に入る確率
p (x )
P   p( x )dx
R
R
 k ： n 個の訓練標本のうち
R に入っている個数
P
V
D
ノンパラメトリック法の基礎
39
 確率 P を二つの方法で近似する．
A) k, n を用いれば，
Pk n
B) 領域 R 内のある点 x を用いれば，
P  Vp(x)
積分の長方形近似
 これらより
k
p( x ) 

p
(
x
)
nV
P
x
V
D
ノンパラメトリック法
40
k
p( x ) 
nV
訓練標本を用いて領域 R を決める．
パーゼン窓法，カーネル密度推定法：
R の形を決め V を固定したもとで k を標本から決定
 最近傍密度推定法：
R の形を決め k を固定したもとで V を標本から決定

最近傍密度推定法
41
k-最近傍密度推定法（k-nearest neighbor
density estimation)：
 領域 R として，ある点 x を中心とする超球
(hypersphere)を用いる．
 超球の半径 r ：訓練標本が k 個含まれる
最小の大きさに設定
d
 超球の体積：
 2rd
V

pˆ ( x) 
( d2  1)
k 4
k( d2  1)
n r d
d
2
x
k
p( x ) 
nV
ガンマ関数
ガンマ関数(gamma function)：

(  )   x e d x
 1  x
0
( )

42
ガンマ関数の性質

 ( )   x
43
 1  x
0
e dx
階乗の一般化：正の整数 n に対して
(n  1)  n!
その他の性質：
 (t )  (t  1)(t  1), t  R

( 12 )  
演習：
2
 d  2 のとき V   r
 d  3 のとき V  4  r 3
3
V
 rd
d
2
( d2  1)
実行例
近傍数 k は尤度交差確認に
よって決定できる
近傍数：小さすぎ
k  10
近傍数：適切
k  500
44
n  10000
近傍数：大きすぎ
k  2000
ノンパラメトリック法：まとめ
45
カーネル密度推定法
滑らかなカーネルを使えば，滑らかな確率密度推定量
が得られる
 計算が簡単

最近傍密度推定法
近傍の標本を見つけるためには距離をソートする必要
があり，大規模データに対しては計算時間がかかる
 得られる確率密度推定量は比較的ギザギザしている？
 パターン認識との相性がよい（後述）

講義の流れ
1.
2.
3.
4.
ノンパラメトリック法の基礎（第12章）
カーネル密度推定法（第12章）
最近傍密度推定法（第13章）
最近傍識別器（第13章）
46
条件付き確率の推定
47
各カテゴリに対して，条件付き確率 p ( x | y ) を
1-最近傍密度推定法により推定．
( d2  1)
pˆ ( x | y ) 
ry ：カテゴリ y に属する標本のうち
d
n y ry
xに最も近いものと，xとの距離
 p ( y )  n y / n と事後確率 p ( y | x) は，
( d2  1) n y
1
p( y | x)  p( x | y ) p( y ) 

d
d
n
r
n y ry
y
d
2
d
2
ry が小さいほうが
事後確率が大きい！
最近傍識別器
48
事後確率が最大のカテゴリ
＝ x に一番近い訓練標本が属するカテゴリ
このような識別法を，最近傍識別器(nearest
neighbor classifier)とよぶ．
k-最近傍識別器
49
実用的には，x の近傍 k 個の訓練標本が属
するカテゴリの多数決で，x の属するカテゴリ
を決める k -最近傍識別器(k-nearest
neighbor classifier)がよく用いられる．
注：k -最近傍密度推定法で確率密度関数を
推定するのと少し異なる
手書き文字認識
50
ＵＳＰＳデータセット（16×16画素）
訓練標本：0～9まで各500文字ずつ計5000文字
テスト標本：各200文字ずつ計2000文字
解答例
51
１９３２／２０００＝９６．６％の正解率
k 1
予測したカテゴリ
1
正解のカテゴリ
1
2
200
3
4
5
6
7
8
9
0
0
0
0
0
0
0
0
0
0
2
0 193
1
0
0
0
1
4
1
0
3
0
0 195
0
3
0
0
1
1
0
4
0
0
0 191
1
2
0
0
6
0
5
0
3
4
0 187
0
1
1
2
2
6
0
2
0
0
2 195
0
0
0
1
7
0
0
1
2
0
0 192
2
3
0
8
0
1
4
1
3
0
0 186
2
3
9
0
0
0
3
0
0
1
1 195
0
0
0
1
1
0
0
0
0
0
0 198
近傍数ｋの決め方
52
 k -最近傍識別器では近傍数 k を適切に決める
必要がある．
1. 値の候補を用意する．例えば， k  1,2,  ,10
2. それぞれのモデルに対して，パターンの誤認識率
を推定する．
3. 誤認識率の推定値を最小にするモデルを選ぶ．
 どうやってパターンの誤認識率を推定するか？
交差確認法
53
交差確認法(cross validation)
訓練標本 {xi }in1 を t 個の重なりの無い，
t
{
T
}
（ほぼ）同じ大きさの部分集合 i i 1 に分ける．
 j 番目の部分集合 T j に含まれる訓練標本を
使わずに識別器を学習する．
 T j に含まれる標本の誤認識率を計算する
（訓練標本なので答えを知っている！）．
 これを全ての j に対して繰り返し平均する．

T1
…
推定用
T j 1
Tj
確認用
T j 1
…
推定用
Tt
手書き文字認識
54
 k -最近傍識別器の近傍数 k を交差確認法により
決定せよ．
先の例では
k 1
が選ばれた
最近傍識別器：まとめ
55
一番近い訓練標本が属するカテゴリを選ぶ
単純だが，非線形な分離境界を扱える
一番近い訓練標本を探索するのに時間がかかる
講義の流れ
1.
2.
3.
4.
ノンパラメトリック法の基礎（第12章）
カーネル密度推定法（第12章）
最近傍密度推定法（第13章）
最近傍識別器（第13章）
56
まとめ
ノンパラメトリック法：モデルを用いずに直接
確率密度関数を推定
カーネル密度推定法：滑らかなカーネル関数の
線形和で推定
 最近傍密度推定法：近傍の標本を含む超球を
用いて推定

カーネル関数の幅や近傍数は尤度交差確
認法で決定
最近傍密度推定法から，非線形な
決定境界を持つ最近傍識別器が
得られる
57
次回の予告
パラメトリック法：ベイズ推定
枠組み
 近似計算法
 モデル選択

58
宿題１
59
 以下のデータを用いて，ガウス
myrand.m
カーネルに対するカーネル密度 function x=myrand(n)
推定法を実行せよ
x=zeros(1,n); u=rand(1,n);
 バンド幅は尤度交差確認
により決定せよ
clear all
n=10000;
x=myrand(n);
flag=(0<=u & u<1/8);
x(flag)=sqrt(8*u(flag));
flag=(1/8<=u & u<1/4);
x(flag)=2-sqrt(2-8*u(flag));
flag=(1/4<=u & u<1/2);
x(flag)=1+4*u(flag);
flag=(1/2<=u & u<3/4);
x(flag)=3+sqrt(4*u(flag)-2);
flag=(3/4<=u & u<=1);
x(flag)=5-sqrt(4-4*u(flag));
宿題１（続き）
60
実行例
h
バンド幅：小さすぎ
h  0 .01
バンド幅：適切
h  0 .1
バンド幅：大きすぎ
h  0 .5
宿題２
61
最近傍識別器によって手書き文字認識を行え
訓練標本：0～9まで各500文字ずつ計5000文字
 テスト標本：各200文字ずつ計2000文字
 近傍数 k は識別誤差に関する交差確認により決定せよ

宿題２（続き）
訓練入出力データ(X,Y)をもとに
テスト入力データTのラベルの推定Uを
k最近傍分類によって求める
knn.m
function U=knn(X,Y,T,ks)
m=size(T,2); D2=repmat(sum(T.^2,1),[size(X,2) 1]);
D2=D2+repmat(sum(X.^2,1)',[1 m])-2*X'*T;
[dum,z]=sort(D2,1);
for i=1:length(ks)
k=ks(i);
for j=1:m
Z=sort(Y(z(1:k,j))); g=find([1 Z(1:end-1)~=Z(2:end)]);
[dum,a]= max([g(2:end) k+1]-g); U(i,j)=Z(g(a));
end, end
62

Download Report