電気・通信・電子・情報工学実験D 確率的情報処理の基礎技術 Part 1(2013年4月) 本実験DのWebpage: http://www.smapip.is.tohoku.ac.jp/~kazu/ECEI-ExperimentD/2013/ 東北大学 大学院情報科学研究科 田中 和之 kazu@smapip.is.tohoku.ac.jp http://www.smapip.is.tohoku.ac.jp/~kazu/ April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 1]

電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 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 Part 1]

電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 1] Contents 序論：確率的情報処理とベイジアンネットワーク 確率の基礎知識 確率的計算技法の基礎 ---マルコフ連鎖モンテカルロ法と確率伝搬法--- 確率的画像処理とベイジアンネットワーク ---マルコフ確率場と確率伝搬法--- 確率推論とベイジアンネットワーク---グラフィカルモデルと確率伝搬法--- まとめ April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 1]

電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 1] 理詰めの情報処理と日常生活の情報処理 理詰めの情報処理 物理法則にもとづく，あり得べき結果の予測 命題群からの論理的帰結を演繹 コンピュータに発達により現実化 日常生活の情報処理 非演繹的，膨大な計算量 必要な情報が完全に得られるわけではない． 「分かること」と「知りたいこと」のギャップから くる不確実性→何とかして可能にしたい!! April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 1]

電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 1] 不確実さと確率的情報処理 「分かること」と「知りたいこと」のギャップから くる不確実性の数学的表現→確率・統計 起こりやすいことも起こりづらいこともまじめに考慮して計算 計算量的困難 近似アルゴリズムの導入による計算困難の打破 April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 1]

厳密に計算するのは一部の特殊な例を除いて難しい． ポイントは何か 2N 通りの和が計算できるか？ 厳密に計算するのは一部の特殊な例を除いて難しい． マルコフ連鎖モンテカルロ法 確率伝搬法 April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 1]

確率的情報処理のモデル化と近似アルゴリズム ベイズの公式 確率的情報処理 確率モデル モンテカルロ法 近似アルゴリズム モンテカルロ法 マルコフ連鎖モンテカルロ法 乱択アルゴリズム 遺伝的アルゴリズム 近似アルゴリズム 確率伝搬法 クラスター変分法 April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 1]

電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 1] 確率的画像処理 K. Tanaka: J. Phys. A, vol.35, no.37, 2002. 劣化画像（ガウス雑音） 確率的画像処理手法 MSE: 2137 MSE:520 ローパスフィルター ウィナーフィルター メジアンフィルター MSE:860 MSE:767 MSE:1040 April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 1]

電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 1] 誤り訂正符号 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) 高性能の復号アルゴリズムへと進化 April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 1]

電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 1] 誤り訂正符号での確率伝搬法 April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 1]

電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 1] 誤り訂正符号での確率伝搬法 April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 1]

電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 1] 誤り訂正符号での確率伝搬法 符号語 April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 1]

電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 1] 誤り訂正符号での確率伝搬法 受信語 1 1 2元対称通信路 1 符号語 April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 1]

電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 1] 誤り訂正符号での確率伝搬法 April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 1]

電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 1] 誤り訂正符号での確率伝搬法 April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 1]

電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 1] 誤り訂正符号での確率伝搬法 April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 1]

電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 1] 誤り訂正符号での確率伝搬法 Turbo符号，LDPC符号の基礎となる概念 April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 1]

電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 1] CDMA復調法の性能評価 T. Tanaka, IEEE Trans. Inform. Theory, 2002 移動体通信にスピングラス理論が使える． 拡散符号系列 ノイズ 話し手の信号 復号処理 無線 通信 基地局の 受信信号 この復調方式をベイズの公式で確率モデル化すると磁性体の物理モデルで表される． 拡散符号系列 他人の 会話 April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 1]

公開鍵暗号 エネルギー関数による暗号設計の基本戦略 ゴルフコース問題と情報の秘匿 Y. Kabashima, T. Murayama and D. Saad, Phys. Rev. Lett., 2000. ゴルフコース問題と情報の秘匿 カップが天辺にあれば何度得ってもボールはもどってくる カップが底にあればどこから打ってもボールはカップインする． 鍵 エネルギー関数による暗号設計の基本戦略 April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 1]

佐藤泰介，櫻井彰人編: 特集「ベイジアンネット」, 人工知能学会誌, vol.17, no.5, 2002. そのまま高次相関をもつ物理モデルに対応づけられる 確率推論システム 確率伝搬法（Belief Propagation） の提案による実用化の進展 April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 1]