東北大学 大学院情報科学研究科 応用情報科学専攻 田中 和之(Kazuyuki Tanaka) 物理フラクチュオマティクス論 Physical Fluctuomatics 第1回 確率的情報処理の概観 1st Review of probabilistic information processing 東北大学 大学院情報科学研究科 応用情報科学専攻 田中 和之(Kazuyuki Tanaka) kazu@smapip.is.tohoku.ac.jp http://www.smapip.is.tohoku.ac.jp/~kazu/ 本講義のWebpage: http://www.smapip.is.tohoku.ac.jp/~kazu/PhysicalFluctuomatics/2007/ 2007/4/17 物理フラクチュオマティクス論(東北大)

田中和之著: 確率モデルによる画像処理技術入門, 森北出版, 2006. 本講義の参考図書 田中和之著: 確率モデルによる画像処理技術入門, 森北出版, 2006. 田中和之編著: 臨時別冊・数理科学SGCライブラリ「確率的情報処理と統計力学 ---様々なアプローチとそのチュートリアル」, サイエンス社，2006. 2007/4/17 物理フラクチュオマティクス論(東北大)

本講義の参考文献 田中和之・樺島祥介編:ミニ特集/ベイズ統計・統計力学と情報処理, 計測と制御 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. 2007/4/17 物理フラクチュオマティクス論(東北大)

情報通信技術（Information & Communications Technology; ICT）の恩恵の実感 情報通信技術のもたらした恩恵 コンピュータの家電化（高速化と低価格化） インターネットの普及（大容量通信） 情報通信技術（Information & Communications Technology; ICT）の恩恵の実感 より高度な賢さに対する要請 単に安くて高速であればよいというわけではない 2007/4/17 物理フラクチュオマティクス論(東北大)

必要なデータが完全に得られるわけではない． 大量のデータは得られるが必要な情報の抽出が難しい． 情報処理の守備範囲の推移 数値計算のための情報処理 作業手順が与えられている． 理詰めの情報処理 法則・命題群からの予測 コンピュータの発達により現実化 現実世界の情報処理 現象の起こる要因の多様性 必要なデータが完全に得られるわけではない． 大量のデータは得られるが必要な情報の抽出が難しい． 「すぐ分かること」と「本当に知りたいこと」のギャップからくる不確実性→何とかして克服したい!! 2007/4/17 物理フラクチュオマティクス論(東北大)

「すぐ分かること」と「本当に知りたいこと」のギャップからくる不確実性を如何に埋めるか？ これからのコンピュータに対する要請 人並みの能力 ユーザーの意を汲んでくれる能力（知識） 失敗や経験を次に生かす能力（学習） 「すぐ分かること」と「本当に知りたいこと」のギャップからくる不確実性を如何に埋めるか？ 知識と不確実性を数式化 不確実性をともなうデータにおける情報処理の実現 2007/4/17 物理フラクチュオマティクス論(東北大)

不確実性を伴うデータに耐えうる推論システム 不確実性を伴う情報処理の数理モデル 不確実性の数学的表現→確率・統計 モデル化 ネットワーク構造をもつ 数理モデル（ベイジアンネットワーク） 確率推論 医療診断 故障診断 危険予知 ノードは事象，矢印は 条件付き確率に対応 閉路のあるグラフ 不確実性を伴うデータに耐えうる推論システム 単純な機能を持つたくさんの要素が関連し合い，互いに協力して複雑・高度な機能を生み出す． 重要な概念のひとつ 2007/4/17 物理フラクチュオマティクス論(東北大)

確率的情報処理のモデル化とアルゴリズム 確率的情報処理 確率モデル モンテカルロ法 マルコフ連鎖モンテカルロ法 乱択アルゴリズム ベイズの公式 確率的情報処理 確率モデル モンテカルロ法 近似アルゴリズム モンテカルロ法 マルコフ連鎖モンテカルロ法 乱択アルゴリズム 遺伝的アルゴリズム 近似アルゴリズム 確率伝搬法 平均場法 ポイントは ランダムネスと近似 2007/4/17 物理フラクチュオマティクス論(東北大)

確率的画像処理 確率的画像処理手法によるノイズ除去 田中和之著: 確率モデルによる画像処理技術入門， 森北出版，2006． 基本単位は画素 画素上の数字は ディスプレイの 光の強度 最も簡単な既存のフィルター 192 202 190 192 202 190 202 219 120 202 173 120 100 218 110 100 218 110 信号処理の知見をもとにした画像処理の確率モデル化 マルコフ確率場モデル 確率的画像処理 アルゴリズム化 2007/4/17 物理フラクチュオマティクス論(東北大)

確率的画像処理 MSE: 2137 MSE:520 ローパスフィルター ウィナーフィルター メジアンフィルター MSE:860 田中和之著: 確率モデルによる画像処理技術入門, 森北出版, 2006. 劣化画像（ガウス雑音） 確率的画像処理手法 MSE: 2137 MSE:520 ローパスフィルター ウィナーフィルター メジアンフィルター MSE:860 MSE:767 MSE:1040 2007/4/17 物理フラクチュオマティクス論(東北大)

誤り訂正符号 Y. Kabashima and D. Saad: J. Phys. A: Vol.37, No.6, 2004. 松嶋，和田山他著:小特集「ターボ符号・LDPC 符号と繰り返し復号の理論」, 電子情報通信学会誌, vol.88, no.4, 2005. 符号化 伝送路 復号化 ノイズ ターボ符号，低密度パリティ検査符号（LDPC）と呼ばれる繰り返し計算型の高性能の復号アルゴリズムができる． 2007/4/17 物理フラクチュオマティクス論(東北大)

誤り訂正符号 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) 高性能の復号アルゴリズムへと進化 2007/4/17 物理フラクチュオマティクス論(東北大)

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 復号 誤り検出 2007/4/17 物理フラクチュオマティクス論(東北大)

CDMA復調法の性能評価 T. Tanaka, IEEE Transactions on Information Theory, Vol.48, No.11, pp.2888-2910, 2002 移動体通信にスピングラス理論が使える． 拡散符号系列 ノイズ 話し手の信号 復号処理 無線 通信 基地局の 受信信号 この復調方式をベイズの公式で確率モデル化すると磁性体の物理モデルで表される． 拡散符号系列 他人の 会話 2007/4/17 物理フラクチュオマティクス論(東北大)

公開鍵暗号 エネルギー関数による暗号設計の基本戦略 ゴルフコース問題と情報の秘匿 Y. Kabashima, T. Murayama and D. Saad, Phys. Rev. Lett., 2000. ゴルフコース問題と情報の秘匿 カップが天辺にあれば何度得ってもボールはもどってくる カップが底にあればどこから打ってもボールはカップインする． 鍵 エネルギー関数による暗号設計の基本戦略 2007/4/17 物理フラクチュオマティクス論(東北大)

繁桝算男, 本村陽一, 植野真臣共著：ベイジアンネットワーク概説，培風館, 2006. 人工知能 ベイジアンネット 繁桝算男, 本村陽一, 植野真臣共著：ベイジアンネットワーク概説，培風館, 2006. 確率伝搬法 （Belief Propagation） の提案による実用化の進展 確率推論システム 2007/4/17 物理フラクチュオマティクス論(東北大)

確率モデルがインターネットのパケット流制御に使える． 情報通信トラフィック 堀口剛, 電子情報通信学会誌2005年9月号. 確率モデルがインターネットのパケット流制御に使える． 物理モデルのある種のダイナミックスとして書き換えられる． どの経路を通ってパケットが届けられるかはその経路の距離と途中のルーターの混みぐあいによって決まる． 2007/4/17 物理フラクチュオマティクス論(東北大)

ネットワークにおけるハブの役割の統計解析 例：仙台からベネチアまで飛行機で移動したいとしたら ジェノバ ハブ空港のおかげで世界的距離が短くなる （スモールワールド）． 新潟 仙台 東京成田 ミラノ ベネチア 札幌 フィレンツェ もしすぐ近くの空港としか航空便がなければ何回乗り継ぎをしなければならなくなるだろう． もしすべての空港間で航空便が運行していたら何台飛行機が必要だろう． ハブの役割を果たす空港は多い必要はないが，ある程度の数は必要． ハブの役割にも種類がある（日本のハブ空港，アジアのハブ空港，世界のハブ空港）． 空港間・航空会社間の競争の原理から生み出され，最適化されている． 空港のネットワークに階層構造が生まれる． さまざまのネットワークにおける共通の数理の存在 2007/4/17 物理フラクチュオマティクス論(東北大)

低温になると電気抵抗がなくなる物質があるらしい!! 高温になると鉄は磁石にならなくなるらしい!! ・ 自然現象と物理モデル 水はなぜ氷になるのだろう？ 冬になると何故，結露が起こるのだろう？ 鉄は何故，磁石になるのだろう? 鉄や銅は何故，電流は流すのだろう? 低温になると電気抵抗がなくなる物質があるらしい!! 高温になると鉄は磁石にならなくなるらしい!! ・ 2007/4/17 物理フラクチュオマティクス論(東北大)

強磁性体と確率モデル 線分で結ばれたノード対のスピン同士が同じ向きを向くほど確率が高くなるように確率モデルを設計 スピンがいくつか集まると周りのスピンの状態をよく見ながら自分の状態を決めないといけなくなる もっとたくさん集まったらどうなるか? 2007/4/17 物理フラクチュオマティクス論(東北大)

強磁性体の確率モデルと More is different p が小さい p が大きい マルコフ連鎖モンテカルロ法によるサンプリング 秩序状態 無秩序状態 More is different. ある p の値の付近で ゆらぎが大きくなる． 量が増えれば質が変わる 2007/4/17 物理フラクチュオマティクス論(東北大)

たくさんが関連して集まり構成されたシステム： 情報と物理が扱う対象に共通する概念 ビットが集まってデータを形成し，コトとなる． 主な研究対象 情報工学：コト データ 物理：モノ 物質・自然現象 010011101110101000111110000110000101000000111010101110101010 101101110001 ０,1 ビット コト（データ） 並びをきちんと決めることによって意味のある文章になる． 共通点：たくさんが関連 分子が集まって物質を形成し，モノになる． 分子 モノ（物質） 分子同士は引っ張り合っている． 2007/4/17 物理フラクチュオマティクス論(東北大)

不確実性を確率・統計を用いて表現することの代償 確率的情報処理における計算の壁 不確実性を確率・統計を用いて表現することの代償 起こりやすいことも起こりづらいこともまじめに考慮して計算 計算量的困難 近似アルゴリズムの導入による計算困難の打破 2007/4/17 物理フラクチュオマティクス論(東北大)

ポイントは何か 2N 通りの和が計算できるか？ N 重ループ このプログラムでは N=10個のノードで1秒かかるとしたら 2007/4/17 物理フラクチュオマティクス論(東北大)

何故，確率的情報処理に物理的視点が有効なのか？ 物質はたくさんの分子から構成されている （1 mol の中に 約N=1023個の分子） 分子と分子の間には分子間力が働いている． のような多重和の大規模計算が宿命（厳密計算は断念） 近似理論によるアプローチ 統計科学による情報処理も同じ多重和の計算が要請される． 物理学的計算手法の情報処理への使い回しが可能 2007/4/17 物理フラクチュオマティクス論(東北大)

性能評価：できれば統計的かつ解析的に行いたい!! 性能限界の導出 アルゴリズム動作の統計的解析 確率的情報処理の要約 問題設定：社会的・工学的要請 情報通信技術，像情報処理，人工知能 モデル化：統計科学にもとづく定式化 評価関数，事後確率としての確率モデル化 アルゴリズム設計：物理的計算技法の転用 平均場理論をはじめとする近似理論の活用 性能評価：できれば統計的かつ解析的に行いたい!! 性能限界の導出 アルゴリズム動作の統計的解析 物理的手法の転用が可能 2007/4/17 物理フラクチュオマティクス論(東北大)

モノの理とコトの技の学術的循環 共通の数理 統計科学 物理学 情報工学 データからの情報の抽出・加工 物質の性質・自然現象の理解・予言 モノの理による 新たなコトの技の創出 コトの技を通して モノの理を鍛える 共通の数理 情報統計力学 確率的情報処理 学術的循環 学術的循環 統計科学 データからの情報の抽出・加工 物質の性質・自然現象の理解・予言 モノの理 コトの技 物理学 情報工学 田中和之編著: 数理科学別冊「確率的情報処理と統計力学　---様々なアプローチとそのチュートリアル---」，サイエンス社，2006年9月刊行． 2007/4/17 物理フラクチュオマティクス論(東北大)

確率的情報処理 (Probabilistic Information Processing) のWebを介しての更なる拡大 ポイントはやはり「たくさんが関連」 ICT 技術の要請に耐えうる統計科学 通信理論・像情報処理・確率推論 データマイニング 統計科学 複雑ネットワーク科学 統計的学習理論 計算理論 情報統計力学 確率的情報処理のこれからの数理的基盤 コトの物理学としての定着 2007/4/17 物理フラクチュオマティクス論(東北大)

自然現象とMore is different More is different の確率的情報処理への転用 本日のまとめ 確率的情報処理の意義 確率的情報処理の事例紹介 自然現象とMore is different More is different の確率的情報処理への転用 次回以降 確率・統計の基礎知識（第2回，第3回） 確率過程（第4回） 線型モデル（第５回） ・ 2007/4/17 物理フラクチュオマティクス論(東北大)