電気・通信・電子・情報工学実験D 確率的情報処理の基礎 第１部講義(2008年4月15日，4月22日，5月6日) 本実験DのWebpage: http://www.smapip.is.tohoku.ac.jp/~kazu/ECEI-ExperimentD/2008/ 東北大学 大学院情報科学研究科 田中 和之 kazu@smapip.is.tohoku.ac.jp http://www.smapip.is.tohoku.ac.jp/~kazu/ 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
田中和之著: 確率モデルによる画像処理技術入門, 森北出版, 2006. 本講義の参考文献 田中和之著: 確率モデルによる画像処理技術入門, 森北出版, 2006. 田中和之編著: 臨時別冊・数理科学SGCライブラリ「確率的情報処理と統計力学 ---様々なアプローチとそのチュートリアル」, サイエンス社，2006. 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. 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
Contents 序論：確率的情報処理とベイジアンネットワーク 確率の基礎知識 確率的計算技法の基礎 ---マルコフ連鎖モンテカルロ法と確率伝搬法--- 確率的画像処理とベイジアンネットワーク ---マルコフ確率場と確率伝搬法--- 確率推論とベイジアンネットワーク---グラフィカルモデルと確率伝搬法--- まとめ 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
物理法則にもとづく，あり得べき結果の予測 命題群からの論理的帰結を演繹 コンピュータに発達により現実化 理詰めの情報処理と日常生活の情報処理 理詰めの情報処理 物理法則にもとづく，あり得べき結果の予測 命題群からの論理的帰結を演繹 コンピュータに発達により現実化 日常生活の情報処理 非演繹的，膨大な計算量 必要な情報が完全に得られるわけではない． 「分かること」と「知りたいこと」のギャップから くる不確実性→何とかして可能にしたい!! 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
「分かること」と「知りたいこと」のギャップから くる不確実性の数学的表現→確率・統計 不確実さと確率的情報処理 「分かること」と「知りたいこと」のギャップから くる不確実性の数学的表現→確率・統計 起こりやすいことも起こりづらいこともまじめに考慮して計算 計算量的困難 近似アルゴリズムの導入による計算困難の打破 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
厳密に計算するのは一部の特殊な例を除いて難しい． ポイントは何か 2N 通りの和が計算できるか？ 厳密に計算するのは一部の特殊な例を除いて難しい． マルコフ連鎖モンテカルロ法 確率伝搬法 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
確率的情報処理のモデル化と近似アルゴリズム ベイズの公式 確率的情報処理 確率モデル モンテカルロ法 近似アルゴリズム モンテカルロ法 マルコフ連鎖モンテカルロ法 乱択アルゴリズム 遺伝的アルゴリズム 近似アルゴリズム 確率伝搬法 クラスター変分法 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
確率的画像処理 MSE: 2137 MSE:520 ローパスフィルター ウィナーフィルター メジアンフィルター MSE:860 K. Tanaka: J. Phys. A, vol.35, no.37, 2002. 劣化画像（ガウス雑音） 確率的画像処理手法 MSE: 2137 MSE:520 ローパスフィルター ウィナーフィルター メジアンフィルター MSE:860 MSE:767 MSE:1040 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
誤り訂正符号 Y. Kabashima and D. Saad: J. Phys. A: Vol.37, No.6, 2004. 松嶋，和田山他著:小特集「ターボ符号・LDPC 符号と繰り返し復号の理論」, 電子情報通信学会誌, vol.88, no.4, 2005. 符号化 伝送路 復号化 ノイズ 磁性体の物理モデルに対応 復号に確率伝搬法を用いると高性能の復号アルゴリズムができる． 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
100 111 100111010 010 Noise 誤り訂正符号 符号化 ? 復号 誤り検出 1 並べ替え 1 ０ １ 0 1 100 111 010 100111010 符号化 並べ替え 1 ? Noise ０ １ 1 ０ ０ １ １ ０ １ ０ ０ ０ 0 1 1 0 0 1 0 0 1 0 0 0 復号 誤り検出 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
T. Tanaka, IEEE Trans. Inform. Theory, 2002 CDMA復調法の性能評価 T. Tanaka, IEEE Trans. Inform. Theory, 2002 移動体通信にスピングラス理論が使える． 拡散符号系列 ノイズ 話し手の信号 復号処理 無線 通信 基地局の 受信信号 この復調方式をベイズの公式で確率モデル化すると磁性体の物理モデルで表される． 拡散符号系列 他人の 会話 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
公開鍵暗号 エネルギー関数による暗号設計の基本戦略 ゴルフコース問題と情報の秘匿 Y. Kabashima, T. Murayama and D. Saad, Phys. Rev. Lett., 2000. ゴルフコース問題と情報の秘匿 カップが天辺にあれば何度得ってもボールはもどってくる カップが底にあればどこから打ってもボールはカップインする． 鍵 エネルギー関数による暗号設計の基本戦略 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
佐藤泰介，櫻井彰人編: 特集「ベイジアンネット」, 人工知能学会誌, vol.17, no.5, 2002. そのまま高次相関をもつ物理モデルに対応づけられる 確率推論システム 確率伝搬法（Belief Propagation） の提案による実用化の進展 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
確率モデルがインターネットのパケット流制御に使える． 情報通信トラフィック 堀口剛, 電子情報通信学会誌2005年9月号. 確率モデルがインターネットのパケット流制御に使える． 物理モデルのある種のダイナミックスとして書き換えられる． どの経路を通ってパケットが届けられるかはその経路の距離と途中のルーターの混みぐあいによって決まる． 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
Contents 序論：確率的情報処理とベイジアンネットワーク 確率の基礎知識 確率的計算技法の基礎 ---マルコフ連鎖モンテカルロ法と確率伝搬法--- 確率的画像処理とベイジアンネットワーク ---マルコフ確率場と確率伝搬法--- 確率推論とベイジアンネットワーク---グラフィカルモデルと確率伝搬法--- まとめ 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
試行と標本空間と事象 試行 (Experiment) ：ある操作を行って得られる可能性のある結果の全体はわかっているが，そのうちのいずれかが得られるかは予知できない操作 標本点 (Sample Point)：試行の結果得られる可能性のある個々の結果 標本空間 (Sample Space)：標本点の全体集合 事象 (Event)：標本空間の部分集合 根元事象 (Elementary Event)：１個の標本点だけからなる事象 空事象 (Empty Event)：標本点がない事象 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
試行と標本空間と事象 「サイコロを１回振る」という試行の例 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
全事象・余事象と差事象 「３の目がでない」 という事象は 「３の目がでる」 という事象の余事象 「３の目がでない」 という事象は 全事象と「３の目がでる」 という事象の差事象 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
和事象 「奇数の目がでる」 という事象は 「１の目がでる」 という事象と 「３または５の目がでる」という事象の和事象 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
積事象 「３または４の目がでる」 という事象は 「４以下の目がでる」 という事象と 「３以上の目がでる」という事象の積事象 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
空事象 「３以下の目がでる」 という事象と 「４以上の目がでる」という事象の積事象は空事象である． 「３以下の目がでる」 という事象と 「４以上の目がでる」という事象は互いに排反であるという． 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
様々の事象のまとめ 全事象: W 事象 A の余事象(Complementary Event): Ac=W╲A 事象 A と B の差事象: A╲B 事象 A と B の和事象 (Union of Event): A∪B 事象 A と B の積事象 (Intersection of Event): A∩B 事象 A と B が互いに排反 (Disjoint): A∩B=f 事象 A, B, C が互いに排反 (Disjoint): [A∩B=f]Λ[B∩C=f]Λ[C∩A=f] 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
確率の定義 Laplace による定義: 起こりうる標本点の総数が N 個あり，それらは同様に確からしい(Equally Likely)と仮定する．ある事象Aの標本点の個数が n 個であれば事象 A の起こる確率(Probability) は p=n/N と定義する． 統計的定義: ある試行を R 回繰り返し行う．事象 Aの起こる回数を r とする．試行の回数 R を増やしていくとき，r/R が一定の値 p に近づくならば，事象 A の起こる確率(Probability) を p と定義する． 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
確率の定義 Kolmogorov による定義: 標本空間Ωから定義される任意の事象 A に対して確率 (Probability) Pr{A} は次の３つの公理を満たすものとして定義される． 確率の公理1. 任意の事象 A に対して 確率の公理2. 全事象Ωに対して 確率の公理3. 任意の2つの互いに排反な事象 A, B に対して 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
確率の定義 公理2. 全事象Ωに対して 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
確率の定義 公理3. 任意の2つの互いに排反な事象 A, B に対して 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
結合確率と条件付き確率 事象Aの起こる確率 事象 A と事象 B の結合確率 条件付き確率と結合確率 A B 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
結合確率と事象の独立性 事象 A と事象 B が互いに独立である 事象 A と事象 B が互いに独立であるときの 条件付き確率 A B A 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
周辺確率 標本空間Ωが互いに排反である M 個の事象 A1,A2,…,AM によって Ω=A1∪A2∪…∪AM と表されるとき Ai B 結合確率 Pr{Ai,B} における事象 B の周辺確率 (Marginal Probability) 周辺化 簡略表記 A B 事象 A の取り得るすべての互いに排反な事象についての和 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
周辺化 結合確率と周辺確率 事象 B の周辺確率 A B C D 15 April - 19 May, 2008
ベイズの公式 (Bayes Formula) 事前確率 (A Priori Probability) A B 事後確率 (A Posteriori Probability) Bayes 規則 (Bayes Rule) とも言う． ベイジアンネットワーク 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
ベイズの公式の導出 A B 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
ベイズの公式による確率的推論の例 A 教授はたいへん謹厳でこわい人で，機嫌の悪いときが 3/4 を占め，機嫌のよい期間はわずかの 1/4 にすぎない． 教授には美人の秘書がいるが，よく観察してみると，教授の機嫌のよいときは，8 回のうち 7 回までは彼女も機嫌がよく，悪いのは 8 回中 1 回にすぎない． 教授の機嫌の悪いときで，彼女の機嫌のよいときは 4 回に 1 回である． 秘書の機嫌からベイズの公式を使って教授の機嫌を確率的に推論することができる. 甘利俊一：情報理論 (ダイヤモンド社，1970) より 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
確率と確率変数 各事象に番号を割り当て，その番号に対する変数を導入する．この変数を確率変数 (Random Variable)という． 「奇数の目がでる」という事象に「X=1」という等式を対応させることができる． 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
確率と確率変数 標本空間から構成されたすべての事象 A に実数値 X(A) を１対１対応させる写像を考える．この写像 X(A) を事象 A の確率変数 (Random Variable) という．通常, 確率変数 X(A) は A を省略し，単に X と表される． 確率変数 X が実数値 x をとる事象 X=x の確率を Pr{X=x} と表す．このとき x をその確率変数の実現値または状態 (State)という．起こりうる状態の集合を状態空間 (State Space)という． ２つの事象X=x および X=x’ が互いに排反であるとき状態 x と状態 x’ は互いに排反であるという． 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
離散確率変数と連続確率変数 離散確率変数 (Discrete Random Variable): 離散的な状態空間をもつ確率変数 離散的な状態空間をもつ確率変数 例：{x1,x2,…,xM} 連続確率変数 (Continuous Random Variable): 連続的な状態空間をもつ確率変数 例：(−∞,+∞) 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
すべて事象 X=x1, X=x2,…, X=xM の起こる確率 が変数 x の関数 P(x) を用いて 離散確率変数と確率分布 標本空間Ωが互いに排反である M 個の事象 A1,A2,…,AM によって Ω=A1∪A2∪…∪AM と表され，確率変数 X がM 個の状態 x1,x2,…,xM を用いて1対1対応の写像 X(Ai)=xi (i=1,2,…,M) により定義されるとき すべて事象 X=x1, X=x2,…, X=xM の起こる確率 が変数 x の関数 P(x) を用いて 確率変数 状態変数 状態 と表されるとき, P(x) を確率変数 X の確率分布 (Probability Distribution) ，x を状態変数 (State Variable) という． 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
規格化条件(Normalization Condition) 離散確率変数の確率分布の性質 いずれも確率の公理１，２，３から導かれる． 規格化条件(Normalization Condition) 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
確率変数 X の期待値 (Expected Value，平均: Average)μ 離散確率変数の期待値と分散 確率変数 X の期待値 (Expected Value，平均: Average)μ 確率変数 X の分散 (Variance) σ2 σ：標準偏差 (Standard Deviation) 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
離散確率変数の結合確率分布 ２種類の確率変数 X, Y に対して，事象 X=x と事象 Y=y 結合事象 (X=x)∩(Y=y)の起こる確率 Pr{(X=x)∩(Y=y)}= Pr{X=x,Y=y} が関数 P(x,y) を用いて と表されるとき, P(x,y) を確率変数 X と Y の結合確率分布 (Joint Probability Distribution) という． 確率ベクトル変数 状態ベクトル変数 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
周辺確率分布 (Marginal Probability Distribution) 離散確率変数の周辺確率分布 標本空間Ωが互いに排反である M 個の事象 A1,A2,…,AM によって Ω=A1∪A2∪…∪AM と表され，離散確率変数 X がM 個の実数値 x1,x2,…,xM を用いて1対1対応の写像 X(Ai)=xi (i=1,2,…,M) により定義されるとき 確率変数 Y の 周辺確率分布 (Marginal Probability Distribution) 簡略表記 状態空間における互いに排反な取り得るすべての状態 x についての和 規格化条件 (Normalization Condition) 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
X Y Z U 離散確率変数の周辺確率分布 より高次元への拡張 確率変数 Y の周辺確率分布 (Marginal Probability Distribution) X Y Z U 周辺化 (Marginalize) 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
離散確率変数の独立性 確率変数 X と Y が互いに独立である： 確率変数 Y の確率分布 確率変数 X と Y の結合確率分布 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
確率変数 X と Y の共分散 (Covariance) 離散確率変数の共分散 確率変数 X と Y の共分散 (Covariance) 共分散行列 (Covariance Matrix) 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
離散確率変数の確率分布の例 a E[X] 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
離散確率変数の結合確率分布の例 a Cov[X,Y] 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
離散確率変数の条件付き確率分布の例 ２元対称通信路の 条件付き確率分布 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
確率変数 X の状態空間 (−∞,+∞) において状態 x が区間 (a,b) にある確率 連続確率変数の確率 確率変数 X の状態空間 (−∞,+∞) において状態 x が区間 (a,b) にある確率 確率変数 X の分布関数(Distribution Function) 確率変数 X の確率密度関数 (Probability Density Function) 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
規格化条件(Normalization Condition) 連続確率変数の確率密度関数の性質 規格化条件(Normalization Condition) 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
連続確率変数の期待値と分散 確率変数 X の期待値 (平均) 確率変数 X の分散 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
確率変数 X と Y の状態空間 (−∞,+∞) において状態 x と y が区間 (a,b)×(c,d) にある確率 連続確率変数の結合確率密度関数 確率変数 X と Y の状態空間 (−∞,+∞) において状態 x と y が区間 (a,b)×(c,d) にある確率 結合確率密度関数 (Joint Probability Density Function) 規格化条件 (Normalization Condition) 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
周辺確率密度関数 (Marginal Probability Density Function) 連続確率変数の周辺確率密度関数 確率変数 Y の 周辺確率密度関数 (Marginal Probability Density Function) 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
連続確率変数の独立性 確率変数 X と Y が互いに独立である： 確率変数 Y の確率密度関数 確率変数 X と Y の 結合確率密度関数 周辺確率密度関数 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
確率変数 X と Y の共分散 (Covariance) 連続確率変数の共分散 確率変数 X と Y の共分散 (Covariance) 共分散行列 (Covariance Matrix) 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
p(x) x a b 一様分布 U(a,b) 一様分布 (Uniform Distribution) の確率密度関数 (b-a)-1 a b (b-a)-1 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
平均μ，分散σ2 のガウス分布 (Gaussian Distribution) の確率密度関数 s>0 p(x) μ x 平均と分散はガウス積分の公式 (Gaussian Integral Formula) から導かれる 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
２次元ガウス分布 (Two-Dimensional Gaussian Distribution) の確率密度関数 多次元ガウス分布 ２次元ガウス分布 (Two-Dimensional Gaussian Distribution) の確率密度関数 行列 C が共分散行列になる． 行列 C は正定値の実対称行列 d 次元ガウス積分の公式から導かれる 一般の次元への拡張も同様 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
X1,X2,...,Xn は平均 m, 分散 s2 の互いに独立な同一の確率変数であるとき 大数の法則 X1,X2,...,Xn は平均 m, 分散 s2 の互いに独立な同一の確率変数であるとき 中心極限定理 X1,X2,...,Xn は平均 m, 分散 s2 の互いに独立な同一の確率変数であるとき は n が大きいとき平均 m, 分散 s2/n の正規分布に従う． 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
確率の基礎知識のまとめ 事象と確率 結合確率と条件付き確率 ベイズの公式と事前確率，事後確率 離散確率変数と確率分布 連続確率変数と確率密度関数 期待値，分散，共分散 一様分布 ガウス分布 大数の法則と中心極限定理 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
Contents 序論：確率的情報処理とベイジアンネットワーク 確率の基礎知識 確率的計算技法の基礎 ---マルコフ連鎖モンテカルロ法と確率伝搬法--- 確率的画像処理とベイジアンネットワーク ---マルコフ確率場と確率伝搬法--- 確率推論とベイジアンネットワーク---グラフィカルモデルと確率伝搬法--- まとめ 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
計算困難のポイントは何か 2L 通りの和が計算できるか？ L 重ループ マルコフ連鎖モンテカルロ法 確率伝搬法 このプログラムでは L=10個のノードで1秒かかるとしたら L=20個で約17分， L=30個で約12日， L=40個で約34年かかる． 厳密に計算するのは一部の特殊な例を除いて難しい． L 重ループ マルコフ連鎖モンテカルロ法 確率伝搬法 今回 次回 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
乱数による円周率の計算（モンテカルロ法） 1 n0 m0 nn+1 -1 1 区間[-1,1]において2個の 一様乱数a,bを発生 -1 緑の四角の枠の中に ランダムに点をプロットし， 赤い円の内部の点の個数 をカウントする． a2+b2≤1 No Yes 円周率 mm+1 試行回数 n が大きいほど 精度が上がる 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
乱数による円周率の計算（モンテカルロ法） 1 1個1個の点をランダムにプロットするという試行を行った時の x 座標，y 座標の平均 0, 分散は 1/2． -1 1 ランダムに n 個プロットした標本平均は平均が 0, 分散が 1/2n (中心極限定理)なので，その確率密度関数の幅は 1/n1/2 で減少する． -1 緑の四角の枠の中に ランダムに点を n 個プロットし， 赤い円の内部の点の個数 m を カウントする． 円周率 円周率の推定誤差は O(1/n1/2) 試行回数 n が大きいほど 精度が上がる 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
積分の計算（モンテカルロ法） 推定誤差は O(1/n1/2) 区間[-1,1]において2個の 一様乱数a,bを発生 1 n0 m0 nn+1 -1 1 区間[-1,1]において2個の 一様乱数a,bを発生 -1 緑の四角の枠の中に ランダムに点をプロットし， その点の被積分関数の 値を求める操作を繰り返す． mm + f(a,b) 推定誤差は O(1/n1/2) 試行回数 n が大きいほど 精度が上がる 積分が高次元でも同様 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
確率推論でよく必要となる計算 周辺確率 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
計算のポイントは 与えられた確率分布 に従うN個の独立なサンプル x を生成するアルゴリズムが作れるか? 但し，1個のサンプルを生成するための計算量は L の多項式オーダーでなければならない． 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
簡単な確率過程：マルコフ連鎖 推移確率 w(x|y)≥0 (x,y=0,1) が与えられたとき 任意の P0(x) を初期値として 推移確率行列 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
簡単な確率過程：マルコフ連鎖 遷移確率行列は と対角化可能 極限分布 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
簡単な確率過程：マルコフ連鎖 定常分布または平衡分布 極限分布 が存在すれば定常分布は存在する 定常分布が存在しても極限分布が存在するとは限らない． Example は定常分布 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
P1(x), P2(x), P3(x),…: マルコフ連鎖 マルコフ連鎖の定常分布と詳細釣り合い ただし P1(x), P2(x), P3(x),…: マルコフ連鎖 詳細釣り合い を満たすように推移確率 w(x|y) を選ぶと その定常分布は P(x) になる． マルコフ連鎖の定常分布 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
マルコフ連鎖モンテカルロ法 確率分布 が与えられたとき 任意の を初期値として を繰り返し計算して， となるように 任意の を初期値として を繰り返し計算して， となるように を選ぶにはどうしたらよいか？ 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
P1(x), P2(x), P3(x),…: マルコフ連鎖 マルコフ連鎖モンテカルロ法 ただし P1(x), P2(x), P3(x),…: マルコフ連鎖 詳細釣り合い を満たすように推移確率 を選ぶとその推移確率 の定常分布は になる． 推移確率 の マルコフ連鎖の定常分布 極限分布がただ一つ存在するとしたら定常分布のひとつが極限分布である． 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
マルコフ連鎖モンテカルロ法 からのサンプリングとみなすことができる 精度は O(1/t1/2) ランダムに生成 τ が十分大きいときサンプルx[t], x[2t], x[3t], …, x[Nt] は独立 無駄弾 独立とみなせるか t をどれだけ大きくとるべきか→緩和時間 からのサンプリングとみなすことができる 精度は O(1/t1/2) 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
マルコフ連鎖モンテカルロ法 Xi 頻度 ヒストグラムから周辺確率も計算できる 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
マルコフ連鎖モンテカルロ法 Xi 頻度 ヒストグラムから周辺確率も計算できる 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
B：すべてのリンクの集合 Ω：すべてのノードの集合 マルコフ連鎖モンテカルロ法 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
ci：ノード i とリンクで結ばれたすべてノードの集合 マルコフ連鎖モンテカルロ法 マルコフ確率場 B：すべての リンクの集合 ci：ノード i とリンクで結ばれたすべてノードの集合 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
x(t) x(t+1) w(x(t+1)|x(t)) マルコフ連鎖モンテカルロ法 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
x(t) x(t+1) x x’ w(x(t+1)|x(t)) xi = ○ or ● マルコフ連鎖モンテカルロ法 True False １回の更新にかかる計算量は変数の次元 L に対してO(1) 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
伊庭幸人, 種村正美: 統計科学のフロンティア/計算統計 II ---マルコフ連鎖モンテカルロ法とその周辺, 岩波書店, 2005. 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
確率伝搬法 (Belief Propagation) を厳密に計算するのは一部の特殊な例を除いて難しい． 一部の特殊な例とは何か？ 一部の特殊な例に適用できるアルゴリズムを一般 の場合に近似アルゴリズムとして適用できるか． → アルゴリズム化できるか？動くか？ 精度はどの程度か？ 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
確率伝搬法 (Belief Propagation) 閉路のないグラフ上の確率モデル どの枝もそれぞれで独立に和がとれる． x 閉路のあるグラフ上の確率モデル それぞれで独立に和をとることが困難． x 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
確率伝搬法 (Belief Propagation) 閉路のないグラフ上の確率モデル 1 2 3 4 5 6 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
確率伝搬法 (Belief Propagation) 閉路のないグラフ上の確率モデル 1 2 3 4 5 6 1 2 4 3 6 5 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
それぞれ隣接するノードから伝搬されるメッセージの積により表される． 閉路のないグラフ上の確率モデル 1 2 3 4 5 6 ノード１と２の周辺確率分布は それぞれ隣接するノードから伝搬されるメッセージの積により表される． 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
確率伝搬法 (Belief Propagation) 閉路のないグラフ上の確率モデル ノード１から隣接ノード２に伝搬するメッセージは（ノード２を除く）ノード１の隣接ノードからノード１に伝搬されるメッセージの積により表される． 1 2 3 4 5 6 メッセージに対する固定点方程式 (Message Passing Rule) 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
B：すべてのリンクの集合 Ω：すべてのノードの集合 確率伝搬法 閉路のあるグラフ上の確率モデル ３ ４ １ ２ ５ 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
閉路のあるグラフ上の確率モデル 閉路のあるグラフ上でも局所的な構造だけに着目してアルゴリムを構成することは可能． ２ 閉路のあるグラフ上でも局所的な構造だけに着目してアルゴリムを構成することは可能． ただし，得られる結果は厳密ではなく近似アルゴリズム ３ ４ １ ５ メッセージに対する固定点方程式 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
繰り返し出力を入力に入れることにより，固定点方程式の解が数値的に得られる． 反復法 固定点方程式と反復法 固定点方程式 繰り返し出力を入力に入れることにより，固定点方程式の解が数値的に得られる． 反復法 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
確率伝搬法の参考文献 J. Pearl: Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference, Morgan Kaufmann, 1988. 汪金芳, 田栗正章, 手塚集, 樺島祥介, 上田修功: 統計科学のフロンティア/計算統計 I ---確率計算の新しい手法, 岩波書店, 2003. 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
まとめ 確率的計算技法の基礎 マルコフ連鎖モンテカルロ法 確率伝搬法 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
Contents 序論：確率的情報処理とベイジアンネットワーク 確率の基礎知識 確率的計算技法の基礎 ---マルコフ連鎖モンテカルロ法と確率伝搬法--- 確率的画像処理とベイジアンネットワーク ---マルコフ確率場と確率伝搬法--- 確率推論とベイジアンネットワーク---グラフィカルモデルと確率伝搬法--- まとめ 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
アプリケーション：Photo Shop, Paint Shop, etc. 画像処理 画像処理の基本操作 ノイズの除去 ぼけた画像からの輪郭線強調 画像の拡大 画像をコンピュータで加工 アプリケーション：Photo Shop, Paint Shop, etc. 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
コンピュータは数値は扱えるが光そのものは扱えない． 画像の基礎知識 画像を使いこなすには画像がどのような形式で数値データとして保存されているかを理解することが必要!!→画像表示 P3 640 480 255 192 209 190 202 219 200 213 201 221 218 206 226 210 209 215 211 210 216 211 208 217 211 208 217 210 203 210 217 210 217 216 210 220 217 211 221 218 213 219 218 ……………… コンピュータは数値は扱えるが光そのものは扱えない． 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
画像表示の基礎 基本単位は画素（ピクセル） 画素の場所→位置ベクトル 約３０万画素 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
画像表示の基礎（モノクロ画像） 基本単位は画素（ピクセル） 画像は各画素ごとの強さの異なる光により表される． 光の強さは０から２５５までの２５６段階 基本単位は画素（ピクセル） ０が真っ黒，２５５が真っ白 各画素にその光の強さに応じて整数値（0,1,2,…,255）を割り当て， データとして保存し，加工する． 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
画像表示の基礎（モノクロ画像） PGM 形式 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
画像表示の基礎 (モノクロ画像） PGM 形式 P2 # kazu 8 8 255 0 200 50 125 56 255 255 0 0 200 50 125 56 255 255 0 220 210 100 25 255 156 125 125 125 125 105 30 215 100 135 75 105 125 256 200 125 56 255 255 34 210 230 125 56 125 255 125 0 145 145 105 126 30 215 67 125 100 200 25 156 0 225 45 0 126 60 0 56 47 155 160 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
画像表示の基礎（カラー画像） 基本単位は 画素（ピクセル） 画像は各画素ごとの赤、緑、青の光の３原色のそれぞれの 強さの異なる光により表される． 赤の光の強度 緑の光の強度 青の光の強度 基本単位は 画素（ピクセル） 各画素に各色の光の強さに応じて３つの整数値を割り当て， データとして保存し，加工する． 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
画像表示の基礎(カラー画像） PPM 形式 P3 # kazu 3 3 255 赤の光の強度 緑の光の強度 青の光の強度 PPM 形式 P3 # kazu 3 3 255 220 210 100 25 255 156 125 125 25 125 125 105 30 215 80 135 75 54 105 125 256 200 125 56 55 255 156 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
g(x,y) モノクロ画像の加工（１） 平滑化フィルター f(x-1,y-1) f(x,y-1) f(x+1,y-1) f(x-1,y) 平均値 g(x,y) 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
モノクロ画像の加工（１） 1/9 平滑化フィルター f(x-1,y-1) f(x,y-1) f(x+1,y-1) f(x-1,y) 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
1/9 モノクロ画像の加工（１） 平滑化フィルター 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
モノクロ画像の加工（１） 1/9 平滑化フィルター 1/25 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
モノクロ画像の加工（２） 微分は差分に置き換える ラプラシアン 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
モノクロ画像の加工（２） ラプラシアンフィルター f(x-1,y-1) f(x,y-1) f(x+1,y-1) f(x-1,y) 1 -4 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
モノクロ画像の加工（２） 1 -4 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
モノクロ画像の加工（２） 1 1 -4 -1 5 - ー 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
モノクロ画像の加工（線形フィルター） 様々の線形フィルター の設計が可能 f(x-1,y-1) f(x,y-1) f(x+1,y-1) a(x-1,y-1) a(x,y-1) a(x+1,y-1) a(x-1,y) a(x,y) a(x+1,y) a(x-1,y+1) a(x,y+1) a(x+1,y+1) 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
= モノクロ画像の加工（３） 192 209 190 202 219 120 100 218 110 f(x-1,y-1) f(x,y-1) 100 110 120 190 192 202 209 218 219 ソーティング 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
モノクロ画像の加工（３） (3x3) メジアンフィルター 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
モノクロ画像の加工（３） (3x3) メジアンフィルター (5x5) メジアンフィルター 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
メジアンフィルター モノクロ画像の加工（３） (3x3) メジアン フィルター (5x5) メジアン フィルター 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
カラー画像の加工 平滑化フィルター f(x-1,y-1) f(x,y-1) f(x+1,y-1) f(x-1,y) f(x,y) 1/9 f(x-1,y-1) f(x,y-1) f(x+1,y-1) f(x-1,y) f(x,y) f(x+1,y) f(x-1,y+1) f(x,y+1) f(x+1,y+1) 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
カラー画像の加工 平滑化フィルター 1/9 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
画像の様々の加工技術 ベクトルメジアンフィルター ウィナーフィルター 拘束条件付き最小自乗フィルター その他 各自インターネットで調べてみよう 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
ノイズ（モノクロ画像） 加法的ノイズ ノイズ 劣化画像 原画像 乱数 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
ノイズ（カラー画像） 加法的ノイズ ノイズ 劣化画像 原画像 乱数 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
モノクロ画像のノイズ除去（１） 平滑化フィルター 1/25 1/9 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
(3x3) メジアン フィルター (5x5) メジアン フィルター モノクロ画像のノイズ除去（２） メジアンフィルター (3x3) メジアン フィルター (5x5) メジアン フィルター 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
カラー画像のノイズ除去 平滑化フィルター 1/9 1/25 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
画像修復の確率モデル 雑音 通信路 原画像 劣化画像 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
画像修復の事前確率分布 ２値画像の例 (fi=0,1) B：すべての最近接画素の集合 α=1.76… 付近でゆらぎがおおきくなる． マルコフ連鎖モンテカルロ法によるサンプリング B：すべての最近接画素の集合 Paramagnetic Ferromagnetic α=1.76… 付近でゆらぎがおおきくなる． Ω：すべての画素の集合 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
２元対称通信路 (Binary Symmetric Channel) 劣化過程 ２元対称通信路 (Binary Symmetric Channel) 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
加法的白色ガウス雑音 (Additive White Gaussian Noise) 劣化過程 加法的白色ガウス雑音 (Additive White Gaussian Noise) 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
計算困難 ベイズ統計・最尤推定と画像処理 事前確率 劣化画像 原画像 事後確率 加法的白色ガウス雑音 または２元対称通信路 画素 各画素ごとの周辺事後確率 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
画像処理とベイズ統計の事後確率 2元対称通信路 加法的白色ガウス雑音 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
B：すべての最近接画素対の集合 Ω：すべての画素の集合 確率的画像処理と ベイジアンネットワーク 事後確率 ベイジアンネットワーク 閉路のあるグラフ上の確率モデル Ω：すべての画素の集合 B：すべての最近接画素対の集合 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
ci：画素 i のすべての最近接画素の集合 マルコフ確率場 マルコフ確率場 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
B：すべての最近接画素対の集合 Ω：すべての画素の集合 確率伝搬法 閉路のあるグラフ上の確率モデル ３ ４ １ ２ ５ 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
閉路のあるグラフ上の確率モデル 閉路のあるグラフ上でも局所的な構造だけに着目してアルゴリムを構成することは可能． ２ １ ３ ４ ５ 閉路のあるグラフ上でも局所的な構造だけに着目してアルゴリムを構成することは可能． ただし，得られる結果は厳密ではなく近似アルゴリズム メッセージに対する固定点方程式 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
確率伝搬法による２値画像の 画像修復アルゴリズム Step 1: 8L 個のメッセージについての連立非線形方程式 を反復法により数値的に解く． ２ １ ３ ４ ５ ２ １ ３ ４ ５ Step 2: 得られたメッセージを に代入し，原画像の推定値を により求める． 具体的なアルゴリズムは 田中和之: 統計力学を用いた確率的画像処理アルゴリズムの基礎 -- 確率伝搬法と統計力学 --, ミニ特集「ベイズ統計・統計力学と情報処理」, 計測と制御, vol.42, no.8, pp.631-636, 2003. などを参照． 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
Binary Image Restoration by Gaussian Graphical Model MSE p=0.1 0.07072 0.28981 0.07902 p=0.2 0.11864 0.38206 0.17184 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 0.04761 0.41097 0.04857 p=0.2 0.08319 0.39216 0.13290 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
Binary Image Restoration by Gaussian Graphical Model 原画像 劣化画像 修復画像 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
Image Restoration by Gaussian Graphical Model (α,σ) の推定値 は統計的学習理論により劣化画像から決定 MSE Belief Propagation 327 0.000611 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 0.000574 33.998 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
Image Restoration by Gaussian Graphical Model and Conventional Filters Original Image Degraded Image MSE Belief Propagation 327 Lowpass Filter (3x3) 388 (5x5) 413 Median Filter 486 445 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 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
Image Restoration by Gaussian Graphical Model and Conventional Filters MSE Belief Propagation 260 Lowpass Filter (3x3) 241 (5x5) 224 Median Filter 331 244 Original Image Degraded 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 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
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 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
確率的画像処理としてのベイジアンネットワーク 確率伝搬法によるアルゴリズム化 まとめ 画像処理の基礎 確率的画像処理としてのベイジアンネットワーク 確率伝搬法によるアルゴリズム化 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
Contents 序論：確率的情報処理とベイジアンネットワーク 確率の基礎知識 確率的計算技法の基礎 ---マルコフ連鎖モンテカルロ法と確率伝搬法--- 確率的画像処理とベイジアンネットワーク ---マルコフ確率場と確率伝搬法--- 確率推論とベイジアンネットワーク---グラフィカルモデルと確率伝搬法--- まとめ 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
不確実性を伴うデータに耐えうる推論システム ベイジアンネットと確率推論 ベイズの公式 確率モデル グラフィカルモデル 確率推論 医療診断 故障診断 ベイジアンネット 不確実性を伴うデータに耐えうる推論システム たくさんのノードが関連しあって集まっている． 計算困難を打破する高性能の近似アルゴリズムの必要性 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
確率の知識（１） 事象Ａの起こる確率 事象Aと事象Bの結合確率 条件付き確率と結合確率 A B 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
A B C D 確率の知識（２） 事象 B の周辺確率 周辺化 15 April - 19 May, 2008
確率推論に使う数学 A B C 因果独立の仮定 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
簡単なベイジアンネットの例 問題 芝生がぬれているのは何故でしょうか？雨が降ったせいでしょうか？ それともスプリンクラーを動かしたせいでしょうか？ 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
簡単なベイジアンネットの例 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
簡単なベイジアンネットの例 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
簡単なベイジアンネットの例 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
簡単なベイジアンネットの例 回答：芝生がぬれているのは雨が降ったせいだと考えられます． 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
ノード数とともに指数関数的に計算量が増加 より複雑なベイジアンネット 重ループ 定義に基づいて厳密に計算するプログラム ノード数とともに指数関数的に計算量が増加 このプログラムでは L=10個のノードで1秒かかるとしたら L=20個で約17分，L=30個で約12日，L=40個で約34年かかる． 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
確率伝搬法 閉路を持たないグラフ上の確率モデルに対して厳密な結果を与える． 閉路を持つグラフ上の確率モデルでは近似アルゴリズムとなる． ８個程度のノードの簡単ではあるが閉路を含むグラフ上の確率モデルで確率伝搬法の構造を説明し，得られる近似結果と厳密な結果を比較してみる． 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
閉路を持つグラフ上の 確率モデルの結合確率 無向グラフ 有向 グラフ 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
周辺確率分布 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
この場合の確率伝搬法の基本方針 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
確率伝搬法の固定点方程式 確率伝搬アルゴリズム 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
Message を用いた周辺確率分布の近似表式 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
Message Passing Algorithm 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
繰り返し出力を入力に入れることにより，固定点方程式の解が数値的に得られる． 反復法 固定点方程式と反復法 固定点方程式 繰り返し出力を入力に入れることにより，固定点方程式の解が数値的に得られる． 反復法 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
数値実験 Belief Propagation Exact 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
数値実験 確率伝搬法 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
線形応答理論 （人為的に小さなゆらぎを与えてその応答を見ることで詳細を知ることができる．） 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
数値実験 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
ベイジアンネットと確率伝搬法を用いた確率推論の概説 線形応答定理を用いた高次の推論システムへの発展 確率推論のまとめ ベイジアンネットと確率伝搬法を用いた確率推論の概説 線形応答定理を用いた高次の推論システムへの発展 ベイジアンネットの最近の動向 佐藤泰介，櫻井彰人編：特集「ベイジアンネット」, 人工知能学会誌, vol.17, no.5, pp.539-565, 2002. 松嶋敏泰他著：小特集「ターボ符号・LDPC 符号と繰り返し復号の理論」，電子情報通信学会, vol.88, no.4, pp.243-265, 2004. Microsoft社，Intel社，Nokia社などが実用化への研究 http://excalibur.brc.uconn.edu/~baynet/ http://www.research.microsoft.com/research/dtg/ 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
Contents 序論：確率的情報処理とベイジアンネットワーク 確率の基礎知識 確率的計算技法の基礎 ---マルコフ連鎖モンテカルロ法と確率伝搬法--- 確率的画像処理とベイジアンネットワーク ---マルコフ確率場と確率伝搬法--- 確率推論とベイジアンネットワーク ---グラフィカルモデルと確率伝搬法--- まとめ 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
まとめ 不確実さを伴う情報処理と確率 各種確率的情報処理 データのゆらぎをてなずける画像処理フィルター・確率推論システムの設計へ 詳細はhttp://www.smapip.is.tohoku.ac.jp/~kazu/SMAPIP-KazuKazu/ チュートリアル講義ノート，お試し用の基本プログラムも公開中 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
確率的情報処理の基礎技術課題 課題レポート提出期限：2008年5月26日 課題レポート提出方法：LaTeX で作成し，最終版を PDF に変換し，電子メール添付にて kazu@smapip.is.tohoku.ac.jp 宛に送付． 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
確率変数 X が ±1 の２値のみをとるものとして事象 X が状態 x をとるという事象 X=x の確率分布が 確率的情報処理の基礎技術 課題 1 確率変数 X が ±1 の２値のみをとるものとして事象 X が状態 x をとるという事象 X=x の確率分布が により与えられるとき期待値 E[X] と分散 V[X] の表式を導出し，その についての値を C 言語，Java またはMatLab を用いて計算し，グラフを書け． 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
により与えられるとき確率変数 X についての周辺確率 P(X) と共分散 Cov[X,Y] の表式を導出せよ． 確率的情報処理の基礎技術 課題 2 確率変数 X と Y がいずれも ±1 の２値のみをとるものとして事象 X が状態 x をとり，かつ事象 Y が状態 y をとり，という事象 (X=x)∩(Y=y) の確率分布 P(x,y) が により与えられるとき確率変数 X についての周辺確率 P(X) と共分散 Cov[X,Y] の表式を導出せよ． 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
確率的情報処理の基礎技術 課題 3 確率変数 X と Y がいずれも ±1 の２値のみをとるものとして事象 Y が状態 y をとるという条件のもとでの事象 X が状態 x をとるという事象 X=x の条件付き確率分布が 次の表式でも与えられることを示せ． ヒント：次の等式を用いる． cosh(c) は任意の実数 c に対して偶関数 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
確率的情報処理の基礎技術 課題 4 ガウス積分の公式を証明せよ． ヒント 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
確率的情報処理の基礎技術 課題 5 確率変数 X が任意の実数 X をとる連続確率変数であり，その確率密度関数が で与えられるとき，平均 E[X] と分散 V[X] が次の表式で与えられることをガウス積分の公式を用いて証明せよ．またμ=0, σ=10, 20, 40 のときの p(x) の x に対する値を C 言語, Java または MatLabで計算し，グラフを書け． 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
確率的情報処理の基礎技術 課題 6 一様分布 U(0,1) に従う乱数（一様乱数）を発生するプログラムを作成せよ．乱数を N 個発生させた場合のヒストグラムを N=10, 20, 50, 100, 1000 のそれぞれの場合について書け． C 言語では rand() は0,1,2,…,randmax のなかのいずれかの値をランダムに生成される命令である．randmax の値は rand() の出力の最大値であり，システムによって異なる場合があるので注意． 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
確率的情報処理の基礎技術 課題 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 のガウス乱数 σξ+μが平均 μ, 分散 σ2 のガウス乱数 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
任意の自然数 d に対して d 行 d 列の正定値の実対称行列 C に対して次の d 次元ガウス積分の公式を証明せよ． 確率的情報処理の基礎技術 課題 8 任意の自然数 d に対して d 行 d 列の正定値の実対称行列 C に対して次の d 次元ガウス積分の公式を証明せよ． 行列 C の固有値 λi に対応する固有ベクトル (i=1,2,…,d) とすると行列 C は次のように対角化される ヒント： 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
確率ベクトル変数 の各成分がいずれも任意の実数 をとる連続確率変数であり，正定値の実対称行列 C に対してその確率密度関数が 確率的情報処理の基礎技術 課題 9 確率ベクトル変数 の各成分がいずれも任意の実数 をとる連続確率変数であり，正定値の実対称行列 C に対してその確率密度関数が により与えられるとき，その平均ベクトルが ，共分散行列 が C となることを示せ． 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
確率的情報処理の基礎技術 課題 10 以下の図と式の結合確率 Pr{X1,X2,…,X8} により与えられるベイジアンネットワークにおける各ノードごとに周辺確率 P(Xi) (i=1,2,…,8) の厳密な値を C 言語，Java または MatLab を用いて求めよ． 各条件付き確率表は 田中和之：ベインジアンネットワークと確率推論の数理, 数理科学 2005 年 9 月号, pp.77-83 の表１の値を用いよ． 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
確率的情報処理の基礎技術 課題 11 以下の図で与えられる正方格子 L=Lx×Ly によるグラフのすべてのリンクからなる集合を B として各ノードの確率変数 Fi が 0,1,2,…,Q-1 の整数値をとり，結合確率が により与えられる無向グラフ上のベイジアンネットワークから互いに独立な状態 (f1,f2,…,fL) をランダムに N 個生成するプログラムをマルコフ連鎖モンテカルロ法により作成し，α=0.2, 0.5, 1.0 に対してそれぞれに対して求めよ． Q=256, α=0.0005 に対して生成されたサンプルの例 Q=2, α=2 に対して生成されたサンプルの例 L=Lx×Ly 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
確率的情報処理の基礎技術 課題 12 非線形方程式 x=tanh(Cx) を反復法を用いて数値的に解くプログラムを作成し，C=0.5, 1.0, 2.0 に対する解を求めよ．また C=0.2, 0.5, 1.0 のそれぞれに対して y=tanh(Cx) と y=x のグラフを書き，C の値により非線形方程式 x=tanh(Cx) がどのような解を持ち，初期値 x0 により反復法がどのような解に収束するかについて議論せよ． 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
確率的情報処理の基礎技術 課題 13 各画素の階調値が 0 または 1 をとる２階調の画像 f ={f1,f2,…,fL} を読み込み各画像ごと独立に確率 p （0<p<0.5）の２元対称通信路 により劣化画像 g={g1,g2,…,gL} を生成するプログラムを作成し，数値実験を実行せよ． p=0.2 の数値実験例 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
確率的情報処理の基礎技術 課題 14 各画素の階調値が 0 または 1 をとる２階調の画像 g ={g1,g2,…,gL} を読み込み，これを劣化画像として原画像 f ={f1,f2,…,fL} の事後確率 に対する確率伝搬法によりノイズを除去する（画像修復の）プログラムを作成し，数値実験を実行せよ．ZPosterior は規格化定数である． 具体的なアルゴリズムは 田中和之: 統計力学を用いた確率的画像処理アルゴリズムの基礎 -- 確率伝搬法と統計力学 -- (解説), ミニ特集「ベイズ統計・統計力学と情報処理」, 計測自動制御学会誌「計測と制御」, Vol.42, No.8 (August 2003), pp.631-636. などを参照． 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D
確率的情報処理の基礎技術 課題 14 のヒント Step 1: 4L 個のメッセージについての連立非線形方程式 を反復法により数値的に解く． ２ １ ３ ４ ５ ２ １ ３ ４ ５ Step 2: 得られたメッセージを に代入し，原画像の推定値を により求める． 15 April - 19 May, 2008 電気・通信・電子・情報工学実験D