Kazuyuki Tanaka ECEI Experiment D (2013 Practices)

電気・通信・電子・情報工学実験D
確率的情報処理の基礎技術
Practice (2013年4月)
本実験DのWebpage:
http://www.smapip.is.tohoku.ac.jp/~kazu/ECEI-ExperimentD/2013/
東北大学大学院情報科学研究科
田中和之
[email protected]
http://www.smapip.is.tohoku.ac.jp/~kazu/
April, 2013
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Practice]
1
本講義の参考文献
田中和之著: 確率モデルによる画像処理技術入門, 森北出版, 2006.
田中和之著: ベイジアンネットワークの統計的推論の数理, コロナ社, 2009.
田中和之編著: 臨時別冊・数理科学SGCライブラリ「確率的情報処理と統計
力学 ---様々なアプローチとそのチュートリアル」, サイエンス社，2006.
安田宗樹, 片岡駿，田中和之共著 (分担執筆): ---CVIMチュートリアルシリー
ズ--- コンピュータビジョン最先端ガイド3(八木康史，斎藤英雄編), 第6章．大
規模確率場と確率的画像処理の深化と展開，pp.137-179, アドコム・メディア
株式会社, December 2010.
Kazuyuki Tanaka: Statistical-mechanical approach to image processing
(Topical Review), Journal of Physics A: Mathematical and General, vol.35,
no.37, pp.R81-R150, 2002.
C. M. Bishop: Pattern Recognition and Machine Intelligence, Springer, 2007.
M. Opper and D. Saad: Advanced Mean Field Method, MIT Press, 2001.
H. Nishimori: Statistical Physics of Spin Glasses and Information Processing, --An Introduction---, Oxford University Press, 2001.
M. J. Wainwright and M. Jordan: Graphical Models, Exponential Families, and
Variational Inference (Foundations and Trends® in Machine Learning), Now
Publishers, 2008.
M. Mezard and A. Montanari: Information, Physics, and Computation, Oxford
University Press, 2009.
April, 2013
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Practice]
2
Contents
1.
2.
3.
4.
5.
6.
April, 2013
序論：確率的情報処理とベイジアンネットワーク
確率の基礎知識
確率的計算技法の基礎
---マルコフ連鎖モンテカルロ法と確率伝搬法--確率的画像処理とベイジアンネットワーク
---マルコフ確率場と確率伝搬法--確率推論とベイジアンネットワーク
---グラフィカルモデルと確率伝搬法--まとめ
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Practice]
3
まとめ
不確実さを伴う情報処理と確率
各種確率的情報処理
データのゆらぎをてなずける画像処理フィ
ルター・確率推論システムの設計へ
詳細はhttp://www.smapip.is.tohoku.ac.jp/~kazu/SMAPIP-KazuKazu/
April, 2013
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Practice]
4
確率的情報処理の基礎技術課題
課題レポート提出方法：LaTeX で作成し，
最終版を PDF に変換し，電子メール添
付にて smapip-acstaff [at mark]
smapip.is.tohoku.ac.jp 宛に送付．
April, 2013
電気・通信・電子・情報工学実験D [Kazuyuki
Tanaka Practice]
5
確率的情報処理の基礎技術課題 1
確率変数 X が ±1 の２値のみをとるものとして事象 X が
状態 x をとるという事象 X=x の確率分布が
expax
x  1
P( x) 
2 cosha 
により与えられるとき期待値 E[X] と分散 V[X] の表式を導
出し，その  1  a  1 についての値を C 言語，Java または
MatLab を用いて計算し，グラフを書け．
April, 2013
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Practice]
6
確率的情報処理の基礎技術課題 2
確率変数 X と Y がいずれも ±1 の２値のみをとるものとし
て事象 X が状態 x をとり，かつ事象 Y が状態 y をとり，と
いう事象 (X=x)∩(Y=y) の確率分布 P(x,y) が
expaxy
x  1, y  1
P ( x, y ) 
4 cosha 
により与えられるとき確率変数 X についての周辺確率
P(X) と共分散 Cov[X,Y] の表式を導出せよ．
April, 2013
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Practice]
7
確率的情報処理の基礎技術課題 3
確率変数 X と Y がいずれも ±1 の２値のみをとるものとして事象 Y
が状態 y をとるという条件のもとでの事象 X が状態 x をとるという事
象 X=x の条件付き確率分布が
1 x , y
P( y x )  p
1  p
 x,y
次の表式でも与えられることを示せ．
expaxy
P( y x) 
2 cosha 
ヒント：次の等式を用いる．
p  expln p 
April, 2013
 x, y
1 1 p 

a  ln
2  p 
1
 1  xy 
2
x  1, y  1
cosh(c) は任意の実数 c に対して偶関数
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Practice]
8
確率的情報処理の基礎技術課題 4
ガウス積分の公式を証明せよ．


0

 1 2
exp   d 
2
 2 
ヒント
R
R
 1 2
 1 2
 1 2
exp   d  2 lim  exp   d
 exp  2  d  Rlim
   R
R   0
 2 
 2 

 2 lim
R  
April, 2013
R
R
0
0
 
1 
 1
exp   2   2 d d  2 lim
R  
2 
 2
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Practice]
 1 2 
exp
r 1   2 r dr
9
確率的情報処理の基礎技術課題 5
確率変数 X が任意の実数 X をとる連続確率変数であり，その確率
密度関数が
 1
2
p x  
exp  2 x    
 2

2 2
1
   x  
で与えられるとき，平均 E[X] と分散 V[X] が次の表式で与えられること
をガウス積分の公式を用いて証明せよ．またμ=0, σ=10, 20, 40 のとき
の p(x) の x に対する値を C 言語, Java または MatLabで計算し，グラフ
を書け．
EX   
April, 2013
VX   
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Practice]
2
10
確率的情報処理の基礎技術課題 6
一様分布 U(0,1) に従う乱数（一様乱数）を発生するプ
ログラムを作成せよ．乱数を N 個発生させた場合のヒ
ストグラムを N=10, 20, 50, 100, 1000 のそれぞれの場
合について書け．
1
x
rand()
randmax
C 言語では rand() は0,1,2,…,randmax のなかのい
ずれかの値をランダムに生成される命令である．
randmax の値は rand() の出力の最大値であり，シ
ステムによって異なる場合があるので注意．
April, 2013
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Practice]
11
確率的情報処理の基礎技術課題 7
平均 μ，分散 σ2 のガウス分布 N(μ,σ2) に従う乱数（ガウス乱
数）を発生するプログラムを作成せよ．乱数を N 個発生させた
場合のヒストグラムを N=10, 20, 50, 100, 1000 のそれぞれの
場合について書け．
ヒント：
任意の確率分布に従って生成された n 個の乱数 x1,x2,…,xn に対
して (x1+x2+…+xn )/n はn→+∞ で平均 μ，分散 σ2/n のガウス分
布 N(μ,σ2/n) に従う[中心極限定理]
区間 [0,1] の一様分布 U[0,1] に従う乱数を12個 x1,x2,…,x12 発生させる．
平均 0, 分散 1
のガウス乱数
  x1  x2    x12  6
σξ+μが平均 μ, 分散 σ2 のガウス乱数
April, 2013
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Practice]
12
確率的情報処理の基礎技術課題 8
任意の自然数 d に対して d 行 d 列の正定値の実対称
行列 C に対して次の d 次元ガウス積分の公式を証明
せよ．




T
 1 
1
   exp  2    C   
 
ヒント：


 
d 

2 d det C

ui
行列 C の固有値 λi に対応する固有ベクトル
(i=1,2,…,d) とすると行列 C は次のように対角化される
 1 0

 0 2
C  U 0 0

 
0 0

April, 2013
0

0
3




0

0

0
0 U 1

 
d 
 

U  u1 , u1 ,, ud 
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Practice]
13
確率的情報処理の基礎技術課題 9

確率ベクトル変数 X の各成分がいずれも任意の実数
をとる連続確率変数であり，正定値の実対称行列 C に
対してその確率密度関数が

px  
 1   T 1   
exp    x    C  x   
d

2  det C  2
1


 x 1 


 
   x2 
d 


x




,



  


 
x 


 d



により与えられるとき，その平均ベクトルが  ，共分散
行列が C となることを示せ．
April, 2013
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Practice]
14
確率的情報処理の基礎技術課題 10
非線形方程式 x=tanh(Cx) を反復法を用いて数値的に解く
プログラムを作成し，C=0.5, 1.0, 2.0 に対する解を求めよ．ま
た C=0.5, 1.0, 2.0 のそれぞれに対して y=tanh(Cx) と y=x のグ
ラフを書き，C の値により非線形方程式 x=tanh(Cx) がどのよ
うな解を持ち，初期値 x0 により反復法がどのような解に収束
するかについて議論せよ．
x1  tanhCx0 
x2  tanhCx1 
x3  tanhCx2 

April, 2013
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Practice]
15
確率的情報処理の基礎技術課題 11
詳細釣り合い
および
wx' x P x   wx x'P x'
 wx x   1 を満たすとき
P x    w x x' P x' 
x
x'
が成り立つことを示せ．
April, 2013
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Practice]
16
確率的情報処理の基礎技術課題 12
1 2 1

 により与えられるとき，
W

推移確率行列が
3  1 2
 Pt (0) 
 P(0) 
 を求めよ．
  lim 
その極限分布 
P
(
1
)
P
(
1
)

 t   t 
 Pt (0) 
 Pt 1 (0) 



W
但し， P (1)   P (1) 
 t 
 t 1 
April, 2013
である．
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Practice]
17
確率的情報処理の基礎技術課題 13
確率変数 a, b, c, d, x, y の確率分布 P(a,b,c,d,x,y) を考える．
Pa,b,c,d,x, y   WA a, xWB b, xWXY x, y WC c, y WD d , y 
確率変数 x, y の周辺確率分布 PXY(x,y) が次のように与えられることを示せ．
PXY x, y    Pa,b,c,d,x, y 
a b c d
 M A  X x M B  X x W XY x, y M C  2  y M D  2  y 
M A  X  x    W A a, x 
M B  X  x    W B b, x 
a
b
M C Y  y    WC c, y 
c
April, 2013
M D Y  y    W D d , y 
d
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Practice]
18
確率的情報処理の基礎技術課題 14
以下の形に与えられる２つの周辺確率分布
Q1 x1  
1
M 2 1 x1 M 31 x1 M 4 1 x1 M 5 1 x1 
Z1
Q12 x1 , x2  
を
1
M 31 x1 M 4 1 x1 M 5 1 x1 W12 x1 , x2 M 6  2 x2 M 7  2 x2 M 8  2 x2 
Z12
Q1 x1    Q12 x1 , x2 
を導出せよ．
に代入することにより次の等式
x2
Z1
M 1 2 x 2  
W12  x1 , x 2 M 3 1  x1 M 4 1 x1 M 5 1 x1 

Z12 x
1
April, 2013
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Practice]
19
確率的情報処理の基礎技術課題 15
確率場 F=(F1,F2,…,F|V|)T および G=(G1,G2,…,G|V|)T およびその状態ベクトル変数
f=(f1,f2,…,f|V|)T および g=(g1,g2,…,g|V|)Tから定義される事後確率
PrF  f G  g 
1
Z Posterior
  f , f 
{i , j }
i
j
{i , j }E
に対して PrFi  fi Fi  f1,, Fi 1  fi 1, Fi 1  fi 1,, FL  f L , G  g
PrFi  f i Fi  f1 ,, Fi 1  f i 1 , Fi 1  f i 1 ,, FL  f L , G  g 
PrF  f G  g
 PrF  z G  g
zi
が成り立つことを説明し，その上で次の等式が成り立つことを示せ．
 f , f 

P rF  f G  g

 P rF  z G  g   z , f 
{i , j }
i
j
ji
{i , j }
zi
zi
i
j
ji
ここで ZPosterior は規格化定数，Eはすべての最隣接頂点対の集合，
i は画素 i のすべての最近接画素の集合を表す．
April, 2013
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Practice]
20
確率的情報処理の基礎技術課題 16
以下の図で与えられる正方格子 L=Lx×Ly によるグラフのすべてのリンクからな
る集合を B として各ノードの確率変数 Fi が 0,1,2,…,Q-1 の整数値をとり，結合
確率が
PrF1 , F2 ,, FL  
1
Z Prior
 1
2
exp    Fi  Fj  
 2 {i , j}E

により与えられる無向グラフ上の確率モデルから互いに独立な状態 (f1,f2,…,fL)
をランダムに N 個生成するプログラムをマルコフ連鎖モンテカルロ法により作成
し，様々のαの値に対して数値実験を実行せよ．
Q=256, α=0.0005 に
対して生成されたサン
プルの例
Ly
L=Lx×Ly
April, 2013
Lx
Q=2, α=2 に対して生
成されたサンプルの
例
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Practice]
21
確率的情報処理の基礎技術課題 17
各画素の階調値が 0 ,1,…Q-1 をとるQ階調の画像 f =(f1,f2,…,f|V|)T を読
み込み各画像ごと独立に平均0，分散2の加法的白色ガウスノイズ
PrG  g F  f   
iV
 1
2
exp  2  f i  gi  
 2

2 2
1
により劣化画像 g=(g1,g2,…,g|V|)T を生成するプログラムを作成し，数値
実験を実行せよ．ここで，Vはすべての画素からなる集合である．
April, 2013
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Practice]
22
確率的情報処理の基礎技術課題 18
各画素の階調値が 0 または 1 をとる2階調の画像 g =(g1,g2,…,g|V|)T を
読み込み，これを劣化画像として原画像 f =(f1,f2,…,fL)T の事後確率
PrF  f G  g 
1
Z Posterior
  f , f 
ij
i
j
ijB
1
1
 1
2
2
2
 ij  f i , f j   exp    f i  gi     f j  g j     f i  f j  
8
2
 8

に対する確率伝搬法によりノイズを除去する（画像修復の）プログラム
を作成し，数値実験を実行せよ．ZPosterior は規格化定数である．
具体的なアルゴリズムは
田中和之著: 確率モデルによる画像処理技術入門，森北出版，2006．
田中和之: 統計力学を用いた確率的画像処理アルゴリズムの基礎 -- 確率伝
搬法と統計力学 -- (解説), ミニ特集「ベイズ統計・統計力学と情報処理」, 計測
自動制御学会誌「計測と制御」, Vol.42, No.8 (August 2003), pp.631-636.
などを参照．
April, 2013
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Practice]
23
確率的情報処理の基礎技術課題18のヒント
Step 1: 4L 個のメッセージについての連立非線形方程式
1
３
４
１
２
M 12  f 2  
５
  z , f M z M z M z 
12
z1 0
1
1
1
31
2
41
1
51
1
1
   z , z M z M z M z 
z1 0 z 2 0
12
1
2
31
1
41
1
51
1
を反復法により数値的に解く．
Step 2: 得られたメッセージを
３
４
１
５
２
P1  f1 g,  ,   

1
z 0
M 21 z1 M 31 z1 M 41 z1 M 51 z1 
に代入し，原画像の推定値を
fˆ1  arg max P1 z 
により求める．
April, 2013
M 21  f1 M 31  f1 M 41  f1 M 51  f1 
z 0 ,1
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Practice]
24
確率的情報処理の基礎技術課題 19
各画素の階調値が任意の実数値をとる画像 g =(g1,g2,…,g|V|)T を読み
込み，これを劣化画像として原画像 f =(f1,f2,…,f|V|)T の事後確率
PrF  f G  g 
1
  f , f 
Z Posterior {i , j}E
{i , j }
i
j
1
1
 1
2
2
2
{i , j}  f i , f j   exp    f i  gi     f j  g j     f i  f j  
8
2
 8

に対する確率伝搬法によりノイズを除去する（画像修復の）プログラム
を作成し，数値実験を実行せよ．ZPosterior は規格化定数である．
具体的なアルゴリズムは
田中和之著: 確率モデルによる画像処理技術入門，森北出版，2006．
を参照．
April, 2013
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Practice]
25
確率的情報処理の基礎技術課題 20
以下の図と式の結合確率 Pr{X1,X2,…,X8} により与えられるベ
イジアンネットワークにおける各ノードごとに周辺確率 P(Xi)
(i=1,2,…,8) の厳密な値を C 言語，Java または MatLab を用い
て求めよ．
PrX 1 , X 2 ,, X 8 

 PrX 8 X 5 , X 6 PrX 7 X 6 Pr X 6 X 3 , X 4
 PrX 5 X 2 PrX 4 X 2 PrX 3 X 1

 PrX 1PrX 2 
各条件付き確率表は
田中和之著: ベイジアンネットワー
クの統計的推論の数理, コロナ社,
2009
のp.50の図3.12と表3.11の値を用いよ．
April, 2013
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Practice]
26
確率的情報処理の基礎技術課題 21
以下の図と式の結合確率 Pr{X1,X2,…,X8} により与えられるベ
イジアンネットワークにおける各ノードごとに周辺確率 P(Xi)
(i=1,2,…,8) の値を確率伝搬法により計算するプログラムを C
言語，Java または MatLab を用いて求めよ．
PrX 1 , X 2 ,, X 8 

 PrX 8 X 5 , X 6 PrX 7 X 6 Pr X 6 X 3 , X 4

 PrX 5 X 2 PrX 4 X 2 PrX 3 X 1PrX 1PrX 2 
各条件付き確率表は「田中和之: ベイジアン
ネットワークの統計的推論の数理, コロナ社,
2009」のp.50の図3.12と表3.11の値を用いよ．
ヒント：具体的なアルゴリズムは「田中和之: ベイジ
アンネットワークの統計的推論の数理, コロナ社,
2009」の7.2節参照．
April, 2013
電気・通信・電子・情報工学実験D
[Kazuyuki Tanaka Practice]
27

Download Report