講義の計画 確率計算のための 漸化式と動的プログラミング（１） 統計数理研究所 伊庭幸人 A.確率計算のための漸化式と動的プログラミング 転送行列，backward-forward, sum-product, viterbiなどの逐次的な アルゴリズムのまとめとさまざまな一般化，応用について述べる． B. 情報理論再入門 情報理論のうち最も基本となる可逆な情報源圧縮について， 初歩から，MDL原理，ベイズ統計との関連まで． 今年の中央大学での講義３日目の再編集版． C.大数の法則，大偏差，カノニカル分布 確率論の初歩から統計力学との関連まで． 全体のテーマ 学んだはず？のこと，これから学ぶはずのこ と， をより高度かつ総合的な立場からみなおす ⇒ ほぼ独立な３テーマを選んだ 今日のテーマ A.確率計算のための漸化式と動的プログラミング 転送行列，backward-forward, sum-product, viterbiなどの逐次的な アルゴリズムのまとめとさまざまな一般化，応用について述べる． 絵で考えたのと，式で考えたのが， ぴったり対応させられるようになればよい ＭＣＭＣ モンテカルロ関係の講義は今年度は ここではやらない 総合研究大学院大学 「計算推論科学ＩＩ」 統計数理研究所（広尾） 聴講希望は伊庭まで １月１５日（月） ２２日（月） ２９日（月） ２月５日（月） 参考書（１） C M Bishop Pattern Recognition and Machine Learning Springer-Verlag 主に Chap.8とChap.13 グラフィカルモデル（Chap.8）はサンプルとして はじめて聞くひとはやさしいところだけ理解すればよい 著者のサイトからダウンロード可能．おすすめ． 大体知っているひとは全体のつながりを再確認しよう 1 参考書（２） ベイズ統計＝生成過程からのモデル化 S M Aji and R J McEliece (2000) 一般化分配則による統一的視点 The generalized distributive law IEEE Transactions on Information Theory, 46 pp. 325-343. ↓ 北川源四郎 連続値変数，逐次モンテカルロ法 時系列解析入門 岩波書店 樺島・上田 BPからloopy BPへ 統計科学のフロンティア１１ 計算統計１ 伊庭ほか 逐次モンテカルロ法，マルコフ連鎖モンテカルロ法 統計科学のフロンティア１２ 計算統計２ 浅井 ＨＭＭによるゲノム解析，確率文脈自由文法（ＰＣＦＧ） 統計科学のフロンティア９ 生物配列の統計 ＭＣＭＣなどの位置づけ ベイズの公式でひっくりかえす 好きな変数に既知の値（データ）を入れて， 残りを確率変数だと思ってよい ＨＭＭ（隠れマルコフ模型） xとyを反転 Xi X i+1 ベイズの公式でひっくり返す計算のために ＭＣＭＣ，逐次モンテカルロ，変分ベイズ ビリーフプロパゲーション viterbi などが使われる HMMを式で書くと A. データ全体を与えたときの状態推定 Smoothing（平滑化） 同時確率 事後分布 2 B. 時刻nまでのデータを与えたときの状態推定 C.周辺尤度の計算 Filtering（フィルタリング） likelihood（尤度） これから，遷移確率などのパラメータ を推定する オンライン推定として重要 問題C（尤度の計算）から考える 漸化式（前向き） 計算の量∼ (状態の数）のＮ乗 計算の量∼ (状態の数）掛けるＮ 行列記法 状態数をD ⇒ D次元行列をベクトルに演算 1 2 3 4 5 6 D=2 1 2 1 2 3 転送行列法 （統計物理の用語） 1 2 3 4 3 問題Ｂも同時に解けている 問題Ａをどうするか 1 2 3 4 1 2 3 漸化式（後向き） ↑時系列から入った人は注意 後向き漸化式の別表現 4 4 5 5 前と同じ 6 新しい部分 6 グラフと式で説明すると・・ 赤丸は共通 時系列解析で好まれる書き方 北川 「時系列解析入門」 岩波書店 4 統計物理 対応 １次元スピン系（１次元イジング鎖など） 1 2 3 4 4 5 6 無向グラフの描き方１ 人間の目と蛸の目（並行進化） タコには盲点が無い 1 2 3 4 1 無向グラフの描き方2 2 3 4 5 各因子（ファクター） ごとに出てくる変数を全部 繋いで完全グラフ（クリーク） にする 確率分布に限定しない 規格化を考えない ほうが便利 参考： ファクターグラフ 緑を全部固定したとき 1 2 4 1 2 3 一意に因子分解の形を決めない ⇒ アルゴリズムを論じるためには より正確な表現が必要 3 4 赤の対が独立でない 赤の対が独立 1 2 3 描き方１ ⇒ 描き方２ ほぼ自明 描き方２ ⇒ 描き方１ Hammersley Cliffordの定理 条件が必要： 任意の状態について確率の値＞０ 4 この講義では普通の無向グラフだけですますの でやや怪しいところも出てくるかも 5 グラフ表現の意味 高次マルコフ，第２隣接以上の相互作用 ある種の条件を満たす 「式の集合」「分布の集合」「モデルの集合」 を抜き出すフィルター Q 次マルコフ Q 隣接 状態数 D ↓ 状態数 条件式のようなもの メタモデル マルコフ場，２次元イジング 計算の手間： 「帯」が有利 断面の大きさ K 次数 D 家系図(ループなし）： ツリー 家系図 母 父 子 確率 ⇒ メンデルの法則 母 父 子 詳細は「ベイズ統計と統計物理」 伊庭幸人 岩波書店 2003 参照 6 root root sum-product algorithm 葉から根 root 根から葉 行ったり来たり root ★ ★★ 「帰り」で「行き」の結果を再利用する 所は似ているけれど，★★とは 違うと思う．sum-productは ＨＭＭで普通使われる★の型に近い 7 家系図（ループあり） 他の方法との関係 ループが多くても使える 漸化式の方法 （この講義） 有限回で終わる 厳密（数値誤差以外） 変分的手法 loopy belief prop. マルコフ連鎖 モンテカルロ （MCMC） ある値に収束 収束しても近似 動き続ける 無限回平均で厳密 平均場近似 漸化式の方法 ⇒ 近似分布 Ｄ. 全部のデータを与えたときの状態のサンプリング 漸化式の方法 条件付き分布からの サンプリングに使う 状態が連続値をとる場合 システム方程式 システム雑音 観測方程式 観測雑音 のサンプルを生成 宿題 一般化 状態空間 モデル 8 問題点 状態が連続値をとる場合の漸化式 積分の計算がたいへん 和を積分で 確率を確率密度でおきかえる 積分を近似するより「モデル全体をHMMで近似する」 と考えたほうがよいが，いずれにせよ大変 ２変数 ∞ ∞状態 ⇒ ２重積分 ２変数，２次マルコフ ∞ ∞ ×∞ ∞状態 ⇒ ４重積分 １２次マルコフ ⇒ １２重積分 ４重を１００状態ずつ １００の４乗 ⇒ １憶状態 ２変数 or １変数で２次マルコフ くらいまでなら可能 北川 「時系列解析入門」 岩波書店 より実際的な方法 がとれる状態を離散化 がとれる状態を離散化 １．ガウス and 線形 ２変数 or １変数 ２次 解析的に積分（ガウス積分） ⇒平均と共分散行列の漸化式 カルマンフィルタ ２．非ガウス or 非線形 １変数 逐次モンテカルロ法 （パーティクル・フィルタ， GAの特殊形） マルコフ連鎖モンテカルロ法 などを使う 統計科学のフロンティア１２ 計算統計II 線形ガウス状態空間モデル 岩波書店 注意１ カルマンフィルタにも B.フィルタリング カルマンサンプラー のほかに， A.平滑化，C.尤度計算，D.サンプリング が全部揃っている（原理同じ，A,Dは導出面倒） を状態変数に使うなどでARモデルなど さまざまなモデルを表現できる． オンラインでBを使うことが一番多いので 「カルマンフィルタ」で全部を代表することが多い 9 注意２ ２変数の線形ガウス状態空間モデル， それを解く カルマンフィルタ 各式は，２つの式を連立させたものになる ２状態の隠れマルコフモデル 各式は２変数の線形の式 まったく違うので注意！ ２変数 ⇔ ∞ ∞状態！ （たとえば共分散の時間発展は非線形） 10
© Copyright 2024 ExpyDoc
