条件付き确率场の推论と学习
- 2. 目次 1. コンピュータビジョンと条件付き確率場 2. マルコフ確率場 3. 最適化手法 1. 平均場近似 2. 確率伝搬法(max-product, sum-product) 4. 条件付き確率場とその学習 参考文献 Conditional Random Fields(CVPR2011 Tutorial) http://www.nowozin.net/sebastian/cvpr2011tutorial/slides/talk-crf.pdf Understanding Belief Propagation and Its Generalizations http://www.merl.com/papers/docs/TR2001-22.pdf
- 3. 目次 1. コンピュータビジョンと条件付き確率場 2. マルコフ確率場 3. 最適化手法 1. 平均場近似 2. 確率伝搬法(max-product, sum-product) 4. 条件付き確率場とその学習
- 4. 条件付き確率場 ? 最も多く使われている確率モデルの一つ – 多くの論文に直接/間接的に現れる ? サイト間の隣接関係を考えた確率モデル 入力 条件付き確率 出力 (マルコフ確率場の構造をもつ)
- 5. 例1: 二値セグメンテーション(GrabCut) ? ブラシで指定された情報を元に，領域を2つに分割 ? 入力: 画像とブラシ情報 ? 出力: 分割された領域の画像
- 6. 例2: ステレオマッチング ? 左右2枚の画像を元に，各画素ごとの深度を推定 ? 入力: 左右2枚の画像 ? 出力: 各画素の深度を表す画像
- 7. 例3: ノイズ除去 ? ノイズを含む画像を元に，ノイズの無い画像を推定 ? 入力: ノイズを含む画像 ? 出力: ノイズが含まれない画像
- 8. Face Detection, Pose Estimation, and Landmark Zhu et. al. CVPR2012 Localization in the Wild ? 写真から複数の顔の位置， 表情を認識 ? 顔のパーツ位置同士の関係 を平滑化項として指定 ? 木構造のGaussian MRFを 利用，ピーク位置をExact に求めている
- 9. Efficient Inference in Fully-Connected CRFs Krahenbuhl et. al. NIPS2010 with Gaussian Edge Potentials ? ? ? ? ピクセル毎の一般物体認識 すべての画素がすべての画素に接続(Fully-Connected CRF) 平均場近似を用いて畳み込み積分の形に変形，高速に推論可能 学習は平均場近似を用いた近似学習
- 10. 条件付き確率場の学習と推論 ? 推論: 入力が与えられた際の出力の条件付き確率を使う ? (教師あり)学習: データを元に，分布を定めるパラメータを決定 フィッティング
- 11. 目次 1. コンピュータビジョンと条件付き確率場 2. マルコフ確率場 3. 最適化手法 1. 平均場近似 2. 確率伝搬法(max-product, sum-product) 4. 条件付き確率場とその学習
- 12. Pairwise Markov Random Field MRFの多くは，全体の結合確率分布を以下で表現する: エネルギー関数 ボルツマン分布 分配関数(partition function) (エネルギーが低いほど 確率は高くなる) ここで，E(x)は次の形をとる: データ項 平滑化項
- 13. 例: 二値ラベルセグメンテーション ? 対象のサイトが{0, 1}の二値しかとりえない問題 – それでも，取りうる状態数は2Nと指数的に増加！ データ項 平滑化項 データ項だけで 最適化 平滑化項を 加えて最適化
- 14. 確率モデルにとって重要な2つの操作 ? MAP推定 – 推定値を求める目的で，p(x)が最大となるxを求める – ボルツマン分布ではエネルギーの最小化問題と等価 ? 周辺分布の推定 – 確率分布を周辺化した周辺分布pi(xi)を求める – 推定値を求めたり，パラメータ学習の際に使用(後述) どちらも，そのまま計算することは非常に困難 →確率伝搬法などの最適化手法を用いる
- 16. 目次 1. コンピュータビジョンと条件付き確率場 2. マルコフ確率場 3. 最適化手法 1. 平均場近似 2. 確率伝搬法(max-product, sum-product) 4. 条件付き確率場とその学習
- 17. 平均場近似 ? MRFの周辺分布を近似的に求めるための手法 – 物理学がそのルーツ ? 確率伝搬法(LBP)よりも精度は悪い分，計算速度が早い ? 機械学習では変分ベイズなどの別名でよく用いられる マルコフ 確率場 ベーテ 近似 = CS?CV 平均場 近似 イジング 模型 = ワイス 理論 = 物理学 確率 伝播法
- 23. 確率伝搬法(1) ? MAP推定解や周辺分布解を求めるための有名な手法 – Max-product, Sum-productとも呼ばれる ? グラフ上でメッセージをやりとりして，解を求める Judea Pearl(1936-) 1982年に確率伝搬法を提唱 2011年にチューリング賞受賞
- 24. 確率伝搬法(1) ? MAP推定解や周辺分布解を求めるための有名な手法 – Max-product, Sum-productとも呼ばれる ? 対象のグラフィカルモデルが木構造である場合は どちらも必ず厳密解が求められる！ – 木構造でない場合でも，比較的精度の高い結果が 得られることが知られている (Loopy Belief Propagation, LBP) 厳密解を 求められる 近似解のみ
- 34. 確率伝搬法(4) ? 対象のグラフが鎖状である場合の確率伝搬法は Forward-Backwardアルゴリズムと等価 ? ループを含む場合は，適当に初期化したメッセージを 反復させることで更新する(Loopy Belief Propagation)． – メッセージが収束する保証はない – 得られる解も推定解で，厳密解でない …
- 35. 目次 1. コンピュータビジョンと条件付き確率場 2. マルコフ確率場 3. 最適化手法 1. 平均場近似 2. 確率伝搬法(max-product, sum-product) 4. 条件付き確率場とその学習
- 36. 最尤推定によるCRFのパラメータ学習 ? (教師あり)学習: データを元に，分布を定めるパラメータを決定 フィッティング ? 具体的には，観測されたND個のデータを用いて， パラメータによって変化する確率分布から最も尤もらしい 分布を推定する(最尤推定)
- 37. 例: 1次元ガウス分布 ? 例として，1次元ガウス分布の最尤推定を行う: ? Lをそれぞれのパラメータで微分，停留点を求めることで 最終的に以下の推定値を得る: 平均 標準偏差
- 38. Kullback-Leibler距離(1) ? Kullback-Leibler距離を次のように定義する: ? KL距離は確率分布間の近さを測る距離のようなもの (厳密には距離でない) Q P ?
- 39. Kullback-Leibler距離(2) ? KL距離を用いて，最尤推定を拡張 – 様々な分布の最適化問題を統一的に理解できる ? 『経験分布』qを，次で定義する: 経験分布: 観測データを表す分布 ? 次に，条件付き分布間の近さを次のKL距離で定義する:
- 42. Kullback-Leibler距離(5) ? CRFのKL距離をパラメータで微分し，次を得る: データ項 モデル項 観測データで定まる分布 モデルの形で定まる分布 ? 勾配を評価し，パラメータを繰り返し更新していく – モデル项の计算には周辺分布の计算が必要
- 43. 最適解の一意性 ? エネルギー分布が以下の形をとる場合に対して， 前述の更新則で求めるパラメータは一意の解をもつ: – KL距離を二階微分，半正定値の共分散行列となる ? このような分布族を『指数型分布族』という – 最適なパラメータが必ず学習できる ? 学習にはモデル分布の周辺分布が必要 – 変分原理(平均場近似，確率伝搬法)で求める方法と， Gibbs Samplingなどを用いて解く方法の二通りがある
- 44. CRF学習の一例(1) ? 以下の離散的なエネルギー分布をもつCRFを学習する: – 各サイト，エッジ毎の重みが変わってくるモデル パラメータ 既知 ? 碍尝距离をそれぞれのパラメータで微分し，次を得る:
- 46. CRF学習の一例(2) ? 以下の離散的なエネルギー分布をもつCRFを学習する: – データ項，平滑化項それ自体を学習で求める パラメータ 既知 ? 碍尝距离をそれぞれのパラメータで微分，解を求める