確率モデルによる画像処理技術入門

物理フラクチュオマティクス論
Physical Fluctuomatics
第1回確率的情報処理の概観
1st Review of probabilistic information processing
東北大学大学院情報科学研究科応用情報科学専攻
田中和之(Kazuyuki Tanaka)
[email protected]
http://www.smapip.is.tohoku.ac.jp/~kazu/
本講義のWebpage:
http://www.smapip.is.tohoku.ac.jp/~kazu/PhysicalFluctuomatics/2008/
2008/4/10
物理フラクチュオマティクス論(東北大)
1
本講義の参考図書
田中和之著: 確率モデルによる画像処理技術入門,
森北出版, 2006.
田中和之編著: 臨時別冊・数理科学SGCライブラリ
「確率的情報処理と統計力学 ---様々なアプローチと
そのチュートリアル」, サイエンス社，2006.
2008/4/10
物理フラクチュオマティクス論(東北大)
2
本講義の参考文献
田中和之・樺島祥介編:ミニ特集/ベイズ統計・統計力学と情報処理, 計測と
制御 2003年8月号．
樺島祥介編:小特集/確率を手なづける秘伝の計算技法～古くて新しい確率・
統計モデルのパラダイム～，電子情報通信学会誌 2005年9月号．
K. Tanaka: Statistical-mechanical approach to image processing (Topical
Review), Journal of Physics A: Mathematical and General, vol.35, no.37,
pp.R81-R150, 2002.
H. Nishimori: Statistical Physics of Spin Glasses and Information
Processing, ---An Introduction, Oxford University Press, 2001.
M. Opper and D. Saad D (eds): Advanced Mean Field Methods --- Theory
and Practice, MIT Press, 2001.
C. M. Bishop: Pattern Recognition and Machine Learning, Springer,
2006.
2008/4/10
物理フラクチュオマティクス論(東北大)
3
情報通信技術のもたらした恩恵
コンピュータの家電化（高速化と低価格化）
インターネットの普及（大容量通信）
情報通信技術（Information & Communications
Technology; ICT）の恩恵の実感
より高度な賢さに対する要請
単に安くて高速であればよいというわけではない
2008/4/10
物理フラクチュオマティクス論(東北大)
4
情報処理の守備範囲の推移
数値計算のための情報処理
作業手順が与えられている．
理詰めの情報処理
法則・命題群からの予測
コンピュータの発達により現実化
現実世界の情報処理
現象の起こる要因の多様性
必要なデータが完全に得られるわけではない．
大量のデータは得られるが必要な情報の抽出が難しい．
「すぐ分かること」と「本当に知りたいこと」のギャップからくる
不確実性→何とかして克服したい!!
2008/4/10
物理フラクチュオマティクス論(東北大)
5
これからのコンピュータに対する要請
人並みの能力
ユーザーの意を汲んでくれる能力（知識）
失敗や経験を次に生かす能力（学習）
「すぐ分かること」と「本当に知りたいこと」の
ギャップからくる不確実性を如何に埋めるか？
知識と不確実性を数式化
不確実性をともなうデータにおける情報処理の実現
2008/4/10
物理フラクチュオマティクス論(東北大)
6
不確実性を伴う情報処理の数理モデル
不確実性の数学的表現→確率・統計
モデル化
確率推論
医療診断
故障診断
危険予知
ネットワーク構造をもつ
数理モデル（ベイジアンネットワーク）
ノードは事象，矢印は
条件付き確率に対応
不確実性を伴うデータに耐えうる推論システム
閉路のあるグラフ
単純な機能を持つたくさんの要素が関連し合い，互
いに協力して複雑・高度な機能を生み出す．
重要な概念のひとつ
2008/4/10
物理フラクチュオマティクス論(東北大)
7
確率的情報処理のモデル化とアルゴリズム
ベイズの公式
確率的情報処理
確率モデル
モンテカルロ法
近似アルゴリズム
モンテカルロ法
マルコフ連鎖モンテカルロ法
乱択アルゴリズム
遺伝的アルゴリズム
近似アルゴリズム
確率伝搬法
平均場法
2008/4/10
ポイントは
ランダムネスと近似
物理フラクチュオマティクス論(東北大)
8
確率的画像処理
田中和之著: 確率モデルによる画像処理技術入門，
森北出版，2006．
確率的画像処理手法によるノイズ除去
基本単位は画素
画素上の数字は
ディスプレイの
光の強度
192
202
190
202
219
120
100
218
110
最も簡単な既存のフィルター
192 202 190


Average202 219 120  173
100 218 110


192
202
190
202
173
120
100
218
110
信号処理の知見をもとにした画像処理の確率モデル化
マルコフ確率場モデル
2008/4/10
アルゴリズム化
物理フラクチュオマティクス論(東北大)
確率的画像処理
9
確率的画像処理
田中和之著: 確率モデルによる画像処理技術入門, 森北出版, 2006.
劣化画像（ガウス雑音）
確率的画像処理手法
MSE:520
MSE: 2137
ローパスフィルター
MSE:860
2008/4/10
ウィナーフィルター
MSE:767
物理フラクチュオマティクス論(東北大)
メジアンフィルター
MSE:1040
10
誤り訂正符号
Y. Kabashima and D. Saad: J. Phys. A: vol.37, no.6, 2004.
松嶋，和田山他著:小特集「ターボ符号・LDPC 符号と繰り返し復号の理
論」, 電子情報通信学会誌, vol.88, no.4, 2005.
送信ミス
010
000001111100000
符号化
001001011100001
復号
多数決
最も簡単な誤り訂正符号
0
1
0
010
パリティ検査符号
ターボ符号・低密度パリティ検査符号(LDPC)
高性能の復号アルゴリズムへと進化
2008/4/10
物理フラクチュオマティクス論(東北大)
11
誤り訂正符号
1
１
１
0
0
０
  
J  J0  n
0
1
0
0
J
1
0
0
1
0
1
1
復号
誤り
検出
物理フラクチュオマティクス論(東北大)
0
?
0
0

1
1
0
2008/4/10
0
0
1
J0
０
0
0
０
0
1
0
1
1
0
0
0
0
０

n
1
0
1
１
０
Noise
１
０
1

G  J 0
0
０

1
1
1

1
1
0
0
並べ
替え
1
0
0
100111010
1
100
111
符号化
010
0
1
0
0

G   J

12
CDMA復調法の性能評価
T. Tanaka, IEEE Transactions on Information Theory,
Vol.48, No.11, pp.2888-2910, 2002
移動体通信にスピングラス理論が使える．
ノイズ
話し手の信号

拡散符号系列
2008/4/10
無線
通信
他人の
会話
拡散符号系列

復号処理
基地局の
受信信号
物理フラクチュオマティクス論(東北大)
この復調方式をベイズ
の公式で確率モデル化
すると磁性体の物理モ
デルで表される．
13
人工知能
ベイジアンネット
繁桝算男, 本村陽一, 植野真臣共著：ベイジアンネットワーク概説，培風館, 2006.
AC
AR
AS
AW
確率推論システム
2008/4/10
確率伝搬法
（Belief Propagation）
の提案による実用化の進展
物理フラクチュオマティクス論(東北大)
14
たくさんが関連して集まり構成されたシステム：
情報と物理が扱う対象に共通する概念
ビットが集まってデータを形成し，コトとなる．
主な研究対象
情報工学：コト
データ
物理：モノ
０,1
ビット
101101
110001
01001110111010
10001111100001
10000101000000
11101010111010
1010
コト（データ）
物質・自然現象
並びをきちんと決めることによって意味のある文章になる．
共通点：たくさんが関連
分子が集まって物質を形成し，モノになる．
分子
分子同士は引っ張り合っている．
2008/4/10
物理フラクチュオマティクス論(東北大)
モノ（物質）
15
確率的情報処理における計算の壁
不確実性を確率・統計を用いて表現することの代償
起こりやすいことも起こりづらいこともまじめ
に考慮して計算
計算量的困難
近似アルゴリズムの導入による計算困難の打破
2008/4/10
物理フラクチュオマティクス論(東北大)
16
ポイントは何か
2N 通りの和が計算できるか？
    f x , x ,, x 
x1 T,F x2 T,F
xN T,F
1
2
このプログラムでは
N=10個のノードで1秒かかるとしたら
N=20個で約17分，
N=30個で約12日，
N=40個で約34年かかる．
N
a  0;
for(x1  T or F){
for(x2  T or F){

for(x N  T or F){
a  a  f  x1 , x2 , , xL ;
}

}
}
2008/4/10
物理フラクチュオマティクス論(東北大)
N 重ループ
17
何故，確率的情報処理に物理的視点が有効なのか？
物質はたくさんの分子から構成されている
（1 mol の中に約N=1023個の分子）
分子と分子の間には分子間力が働いている．
 f x , x ,, x 
1
x1
x2
2
N
xN
のような多重和の大規模計算が宿命（厳密計算は断念）
近似理論によるアプローチ
統計科学による情報処理も同じ多重和の計算が要請される．
物理学的計算手法の情報処理への使い回しが可能
2008/4/10
物理フラクチュオマティクス論(東北大)
18
モノの理とコトの技の学術的循環
コトの技を通して
モノの理を鍛える
モノの理による
新たなコトの技の
創出
共通の数理
情報統計力学
確率的情報処理
学術的循環
学術的循環
統計科学
物質の性質・自然現象の理解・予言
データからの情報の抽出・加工
モノの理
物理学
コトの技
情報工学
田中和之編著: 数理科学別冊「確率的情報処理と統計力学 ---様々な
アプローチとそのチュートリアル---」，サイエンス社，2006年9月刊行．
2008/4/10
物理フラクチュオマティクス論(東北大)
19
本日のまとめ
確率的情報処理の意義
確率的情報処理の事例紹介
自然現象とMore is different
More is different の確率的情報処理への転用
次回以降
確率・統計の基礎知識（第2回，第3回）
最尤推定（第4回）
グラフィカルモデル（第５回）
・
・
・
2008/4/10
物理フラクチュオマティクス論(東北大)
20

Download Report