物理フラクチュオマティクス論 応用確率過程論 (2006年5月9日)

Presentation on theme: "物理フラクチュオマティクス論 応用確率過程論 (2006年5月9日)"— Presentation transcript:

1 物理フラクチュオマティクス論 応用確率過程論 (2006年5月9日)
東北大学 大学院情報科学研究科 田中 和之 本講義の田中和之助教授担当分のWebpage: 2006/5/9 物理フラクチュオマティクス論(東北大)

2 本講義の参考資料 参考資料 田中和之，樺島祥介，田中利幸: 序文 --確率・統計モデルが切り開く推論と学習の新しいパラダイム--，電子情報通信学会誌，Vol.88, No.9, pp , September 2005. 田中和之: 大規模確率場における予測と推論，電子情報通信学会誌，Vol.88, No.9, pp , September 2005. 田中和之: ［チュートリアル講演］確率的情報処理と確率伝搬アルゴリズムの基礎, 電子情報通信学会技術研究報告，Vol.104, No.338, pp.25-32, October 2004. 田中和之: ［チュートリアル講演］ベイジアンネットと確率推論 ---変分原理からの再帰的確率推論アルゴリズムの解説---, 電子情報通信学会技術研究報告, Vol.104, No.348, pp.35-42, October 2004. 2006/5/9 物理フラクチュオマティクス論(東北大)

3 本講義の参考文献 田中和之・樺島祥介編, ミニ特集/ベイズ統計・統計力学と情報処理, 計測と制御 2003年8月号．
田中和之，村田昇，赤穂昭太郎他著，小特集/確率を手なづける秘伝の計算技法～古くて新しい確率・統計モデルのパラダイム～，電子情報通信学会誌 2005年9月号． 人工知能学会編：人工知能学事典，共立出版, 2005年12月 (田中和之，樺島祥介，岡田真人他分担執筆)． 田中和之編著: 数理科学臨時別冊 SCG ライブラリ「確率的情報処理と統計力学　---様々なアプローチとそのチュートリアル---」，サイエンス社，2006年9月刊行． 2006/5/9 物理フラクチュオマティクス論(東北大)

4 ベイジアンネットワークと確率的情報処理の応用事例 確率的画像処理 確率推論
前回（５月２日）のまとめ 確率的情報処理とベイジアンネットワーク 確率的計算技法の基礎 マルコフ連鎖モンテカルロ法 確率伝搬法 今回の話題（５月９日） ベイジアンネットワークと確率的情報処理の応用事例 確率的画像処理 確率推論 2006/5/9 物理フラクチュオマティクス論(東北大)

5 Contents 序論：確率的情報処理とベイジアンネットワーク（５月２日）
確率的計算技法の基礎 ---マルコフ連鎖モンテカルロ法と確率伝搬法---（５月２日） 確率的画像処理とベイジアンネットワーク ---マルコフ確率場と確率伝搬法--- （５月９日） 確率推論とベイジアンネットワーク---グラフィカルモデルと確率伝搬法--- （５月９日） 2006/5/9 物理フラクチュオマティクス論(東北大)

6 アプリケーション：Photo Shop, Paint Shop, etc.
画像処理 画像処理の基本操作 画像の移動，回転，コピー，貼付け ノイズの除去 ぼけた画像からの輪郭線強調 画像の拡大 画像をコンピュータで加工 アプリケーション：Photo Shop, Paint Shop, etc. 2006/5/9 物理フラクチュオマティクス論(東北大)

7 コンピュータは数値は扱えるが光そのものは扱えない．
画像の基礎知識 画像を使いこなすには画像がどのような形式で数値データとして保存されているかを理解することが必要!!→画像表示 P3 255 ……………… コンピュータは数値は扱えるが光そのものは扱えない． 2006/5/9 物理フラクチュオマティクス論(東北大)

8 画像表示の基礎 画素の場所→位置ベクトル 約３０万画素 基本単位は画素（ピクセル） 2006/5/9 物理フラクチュオマティクス論(東北大)

9 画像表示の基礎（モノクロ画像） 基本単位は画素（ピクセル） 画像は各画素ごとの強さの異なる光により表される．
光の強さは０から２５５までの２５６段階 基本単位は画素（ピクセル） ０が真っ黒，２５５が真っ白 各画素にその光の強さに応じて整数値（0,1,2,…,255）を割り当て， データとして保存し，加工する． 2006/5/9 物理フラクチュオマティクス論(東北大)

10 画像表示の基礎（モノクロ画像） PGM 形式 2006/5/9 物理フラクチュオマティクス論(東北大)

11 画像表示の基礎 (モノクロ画像） PGM 形式 P2 # kazu 8 8 255 0 200 50 125 56 255 255 0
2006/5/9 物理フラクチュオマティクス論(東北大)

12 画像を手なずけるための確率の基礎知識（１）
事象 B の周辺確率 A B C D 周辺化 2006/5/9 物理フラクチュオマティクス論(東北大)

13 画像を手なずけるための確率の基礎知識（２）
ベイズの公式 (Bayes Formula) 事前確率 (A Priori Probability) A B 事後確率 (A Posteriori Probability) Bayes 規則 (Bayes Rule) とも言う． ベイジアンネットワーク 2006/5/9 物理フラクチュオマティクス論(東北大)

14 画像修復の確率モデル 雑音 通信路 原画像 劣化画像 2006/5/9 物理フラクチュオマティクス論(東北大)

15 画像修復の事前確率分布 ２値画像の例 (fi=0,1) B：すべての最近接画素対の集合 α=1.76… 付近で ゆらぎが大きくなる．
マルコフ連鎖モンテカルロ法によるサンプリング B：すべての最近接画素対の集合 Paramagnetic Ferromagnetic α=1.76… 付近で ゆらぎが大きくなる． Ω：すべての画素の集合 2006/5/9 物理フラクチュオマティクス論(東北大)

16 ２元対称通信路 (Binary Symmetric Channel)
劣化過程 ２元対称通信路 (Binary Symmetric Channel) 2006/5/9 物理フラクチュオマティクス論(東北大)

17 加法的白色ガウス雑音 (Additive White Gaussian Noise)
劣化過程 加法的白色ガウス雑音 (Additive White Gaussian Noise) 2006/5/9 物理フラクチュオマティクス論(東北大)

18 計算困難 ベイズ統計・最尤推定と画像処理 事前確率 原画像 劣化画像 事後確率 加法的白色ガウス雑音 または２元対称通信路 画素
各画素ごとの周辺事後確率 2006/5/9 物理フラクチュオマティクス論(東北大)

19 画像処理とベイズ統計の事後確率 2元対称通信路 加法的白色ガウス雑音 2006/5/9 物理フラクチュオマティクス論(東北大)

20 B：すべての最近接画素対の集合 Ω：すべての画素の集合 確率的画像処理とベイジアンネットワーク 事後確率 ベイジアンネットワーク
閉路のあるグラフ上の確率モデル Ω：すべての画素の集合 B：すべての最近接画素対の集合 2006/5/9 物理フラクチュオマティクス論(東北大)

21 マルコフ確率場 マルコフ確率場 ci：画素 i のすべての最近接画素の集合 2006/5/9 物理フラクチュオマティクス論(東北大)

22 B：すべての最近接画素対の集合 Ω：すべての画素の集合 確率伝搬法 閉路のあるグラフ上の確率モデル ３ ４ １ ２ ５ 2006/5/9
物理フラクチュオマティクス論(東北大)

23 閉路のあるグラフ上の確率モデル 閉路のあるグラフ上でも局所的な構造だけに着目してアルゴリムを構成することは可能．
２ １ ３ ４ ５ 閉路のあるグラフ上でも局所的な構造だけに着目してアルゴリムを構成することは可能． ただし，得られる結果は厳密ではなく近似アルゴリズム メッセージに対する固定点方程式 2006/5/9 物理フラクチュオマティクス論(東北大)

24 確率伝搬法による２値画像の画像修復アルゴリズム
Step 1: 8L 個のメッセージについての連立非線形方程式 を反復法により数値的に解く． ２ １ ３ ４ ５ ２ １ ３ ４ ５ Step 2: 得られたメッセージを に代入し，原画像の推定値を により求める． 具体的なアルゴリズムは 田中和之: 統計力学を用いた確率的画像処理アルゴリズムの基礎 -- 確率伝搬法と統計力学 --, ミニ特集「ベイズ統計・統計力学と情報処理」, 計測と制御, vol.42, no.8, pp , 2003. などを参照． 2006/5/9 物理フラクチュオマティクス論(東北大)

25 Binary Image Restoration by Gaussian Graphical Model
MSE p=0.1 p=0.2 Finally, we show only the results for the gray-level image restoration. For each numerical experiments, the loopy belief propagation ca give us better results than the ones by conventional filters. MSE p=0.1 p=0.2 2006/5/9 物理フラクチュオマティクス論(東北大)

26 Binary Image Restoration by Gaussian Graphical Model
原画像 劣化画像 修復画像 2006/5/9 物理フラクチュオマティクス論(東北大)

27 Image Restoration by Gaussian Graphical Model
(α,σ) の推定値 は統計的学習理論により劣化画像から決定 MSE Belief Propagation 327 36.302 Finally, we show only the results for the gray-level image restoration. For each numerical experiments, the loopy belief propagation ca give us better results than the ones by conventional filters. MSE Belief Propagation 260 33.998 2006/5/9 物理フラクチュオマティクス論(東北大)

28 Image Restoration by Gaussian Graphical Model and Conventional Filters
Degraded Image MSE Belief Propagation 327 Lowpass Filter (3x3) 388 (5x5) 413 Median Filter 486 445 Original Image Finally, we show only the results for the gray-level image restoration. For each numerical experiments, the loopy belief propagation ca give us better results than the ones by conventional filters. Belief Propagation (3x3) Lowpass (5x5) Median 2006/5/9 物理フラクチュオマティクス論(東北大)

29 Image Restoration by Gaussian Graphical Model and Conventional Filters
Degraded Image MSE Belief Propagation 260 Lowpass Filter (3x3) 241 (5x5) 224 Median Filter 331 244 Original Image Finally, we show only the results for the gray-level image restoration. For each numerical experiments, the loopy belief propagation ca give us better results than the ones by conventional filters. Belief Propagation (5x5) Lowpass (5x5) Median 2006/5/9 物理フラクチュオマティクス論(東北大)

30 Gray-Level Image Restoration (Spike Noise)
Original Image Degraded Image Belief Propagation Lowpass Filter Median Filter Finally, we show only the results for the gray-level image restoration. For each numerical experiments, the loopy belief propagation ca give us better results than the ones by conventional filters. MSE: 2075 MSE: 244 MSE: 217 MSE:135 MSE: 3469 MSE: 371 MSE: 523 MSE: 395 2006/5/9 物理フラクチュオマティクス論(東北大)

31 確率的画像処理としてのベイジアンネットワーク 確率伝搬法によるアルゴリズム化
まとめ 画像処理の基礎 確率的画像処理としてのベイジアンネットワーク 確率伝搬法によるアルゴリズム化 2006/5/9 物理フラクチュオマティクス論(東北大)

32 Contents 序論：確率的情報処理とベイジアンネットワーク（５月２日）
確率的計算技法の基礎 ---マルコフ連鎖モンテカルロ法と確率伝搬法---（５月２日） 確率的画像処理とベイジアンネットワーク ---マルコフ確率場と確率伝搬法--- （５月９日） 確率推論とベイジアンネットワーク---グラフィカルモデルと確率伝搬法--- （５月９日） 2006/5/9 物理フラクチュオマティクス論(東北大)

33 不確実性を伴うデータに耐えうる推論システム
ベイジアンネットと確率推論 ベイズの公式 確率モデル グラフィカルモデル 確率推論 医療診断 故障診断 ベイジアンネット 不確実性を伴うデータに耐えうる推論システム たくさんのノードが関連しあって集まっている． 計算困難を打破する高性能の近似アルゴリズムの必要性 2006/5/9 物理フラクチュオマティクス論(東北大)

34 確率の知識（１） 事象Ａの起こる確率 事象Aと事象Bの結合確率 条件付き確率と結合確率 A B 2006/5/9
物理フラクチュオマティクス論(東北大)

35 確率の知識（２） 事象 B の周辺確率 A B C D 周辺化 2006/5/9 物理フラクチュオマティクス論(東北大)

36 確率推論に使う数学 A B C 因果独立の仮定 2006/5/9 物理フラクチュオマティクス論(東北大)

37 簡単なベイジアンネットの例 問題 芝生がぬれているのは何故でしょうか？雨が降ったせいでしょうか？
それともスプリンクラーを動かしたせいでしょうか？ 2006/5/9 物理フラクチュオマティクス論(東北大)

38 簡単なベイジアンネットの例 2006/5/9 物理フラクチュオマティクス論(東北大)

39 簡単なベイジアンネットの例 2006/5/9 物理フラクチュオマティクス論(東北大)

40 簡単なベイジアンネットの例 2006/5/9 物理フラクチュオマティクス論(東北大)

41 簡単なベイジアンネットの例 回答：芝生がぬれているのは雨が降ったせいだと考えられます． 2006/5/9
物理フラクチュオマティクス論(東北大)

42 ノード数とともに指数関数的に計算量が増加
より複雑なベイジアンネット L 重の for 文 定義に基づいて厳密に計算するプログラム ノード数とともに指数関数的に計算量が増加 このプログラムでは L=10個のノードで1秒かかるとしたら L=20個で約17分，L=30個で約12日，L=40個で約34年かかる． 2006/5/9 物理フラクチュオマティクス論(東北大)

43 確率伝搬法 閉路を持たないグラフ上の確率モデルに対して厳密な結果を与える． 閉路を持つグラフ上の確率モデルでは近似アルゴリズムとなる．
８個程度のノードの簡単ではあるが閉路を含むグラフ上の確率モデルで確率伝搬法の構造を説明し，得られる近似結果と厳密な結果を比較してみる． 2006/5/9 物理フラクチュオマティクス論(東北大)

44 閉路を持つグラフ上の確率モデルの結合確率
無向グラフ 有向 グラフ 2006/5/9 物理フラクチュオマティクス論(東北大)

45 周辺確率分布 2006/5/9 物理フラクチュオマティクス論(東北大)

46 この場合の確率伝搬法の基本方針 2006/5/9 物理フラクチュオマティクス論(東北大)

47 確率伝搬法の固定点方程式 確率伝搬アルゴリズム 2006/5/9 物理フラクチュオマティクス論(東北大)

48 Message を用いた周辺確率分布の近似表式
2006/5/9 物理フラクチュオマティクス論(東北大)

49 Message Passing Algorithm
2006/5/9 物理フラクチュオマティクス論(東北大)

50 繰り返し出力を入力に入れることにより，固定点方程式の解が数値的に得られる． 反復法
固定点方程式と反復法 固定点方程式 繰り返し出力を入力に入れることにより，固定点方程式の解が数値的に得られる． 反復法 2006/5/9 物理フラクチュオマティクス論(東北大)

51 数値実験 Belief Propagation Exact 2006/5/9 物理フラクチュオマティクス論(東北大)

52 数値実験 確率伝搬法 2006/5/9 物理フラクチュオマティクス論(東北大)

53 線形応答理論 （人為的に小さなゆらぎを与えてその応答を見ることで詳細を知ることができる．） 2006/5/9
物理フラクチュオマティクス論(東北大)

54 数値実験 2006/5/9 物理フラクチュオマティクス論(東北大)

55 ベイジアンネットと確率伝搬法を用いた確率推論の概説 線形応答定理を用いた高次の推論システムへの発展
確率推論のまとめ ベイジアンネットと確率伝搬法を用いた確率推論の概説 線形応答定理を用いた高次の推論システムへの発展 ベイジアンネットの最近の動向 佐藤泰介，櫻井彰人編：特集「ベイジアンネット」, 人工知能学会誌, vol.17, no.5, pp , 2002. 松嶋敏泰他著：小特集「ターボ符号・LDPC 符号と繰り返し復号の理論」，電子情報通信学会, vol.88, no.4, pp , 2004. Microsoft社，Intel社，Nokia社などが実用化への研究 2006/5/9 物理フラクチュオマティクス論(東北大)

56 まとめ 不確実さを伴う情報処理と確率 各種確率的情報処理 データのゆらぎをてなずける画像処理フィルター・確率推論システムの設計へ
詳細は チュートリアル講義ノート，お試し用の基本プログラムも公開中 2006/5/9 物理フラクチュオマティクス論(東北大)