菊池自由エネルギーに対する CCCPアルゴリズムの拡張

Presentation on theme: "菊池自由エネルギーに対する CCCPアルゴリズムの拡張"— Presentation transcript:

1 菊池自由エネルギーに対する CCCPアルゴリズムの拡張
東京工業大学総合理工学研究科 知能システム科学専攻　渡辺研究室 学術振興会特別研究員(DC1) 西山　悠

2 内容 背景(A.L. Yuille, 2002) 菊地自由エネルギーに対するCCCPアルゴリズムの拡張 具体例
菊池自由エネルギー（べーテ自由エネルギーを含む） CCCP-Kikuchiアルゴリズム 菊地自由エネルギーに対するCCCPアルゴリズムの拡張 拡張に利用するポイント（メインアイデア） New CCCP-Kikuchi アルゴリズム 具体例 ガウシアングラフィカルモデル(GGM) MPM推定に基づくCDMAマルチユーザ復調

3 内容 背景(A.L. Yuille, 2002) 菊地自由エネルギーに対するCCCPアルゴリズムの拡張 具体例
菊池自由エネルギー（べーテ自由エネルギーを含む） CCCP-Kikuchiアルゴリズム 菊地自由エネルギーに対するCCCPアルゴリズムの拡張 拡張に利用するポイント（メインアイデア） New CCCP-Kikuchi アルゴリズム 具体例 ガウシアングラフィカルモデル(GGM) MPM推定に基づくCDMAマルチユーザ復調

4 問題 確率推論におけるタスク 高次元確率分布のローカルな周辺分布を効率的に求める． 期待値計算に使う 指数オーダ演算

5 木構造クラスの確率分布 独立 全結合 Belief Propagation，Sum-Product の
閉路を含まない メッセージ更新 隠れマルコフモデル Forward Backward Belief Propagation，Sum-Product の 　　効率的なメッセージパッシングアルゴリズムがある． 尤度計算，EM法におけるE-step計算に利用

6 サイクルを含むグラフでは？ 独立 全結合 近似推論アルゴリズムがある LBP (Loopy Belief Propagation)
閉路を含む 近似推論アルゴリズムがある 収束保証 計算量 LBP × 穏やか TRP CCCP ○ 多い LBP (Loopy Belief Propagation) TRP (Tree ReParametrization) CCCP (Concave Convex Procedure) 　　(評価関数ベースのアルゴリズム)

7 図示 高次元確率分布を以下で表されるとする． 単調減少アルゴリズム 単調減少アルゴリズム CCCP CCCP ベーテ自由エネルギー
グラフ 高次元確率分布を以下で表されるとする． 真の周辺分布ベクトル ただのイメージ ベーテ自由エネルギー 菊池自由エネルギー Generalized BPの固定点 CCCP 単調減少アルゴリズム CCCP 単調減少アルゴリズム Loopy BPの固定点 周辺分布ベクトルの全集合

8 CCCP(A.L. Yuille, 2002) 最適化手法，目的関数が上に凸の関数(Concave 関数)と下に凸の関数（Convex関数）の和で表されるときに，単調減少を保証する離散反復アルゴリズム． 目的関数 反復法 単調減少性 convex concave 反復法 極小解　or　鞍点

9 自由エネルギー ？ 試験分布 から，真の確率分布 へのカルバック距離最小化は，以下の式 を試験分布 について最小化することと等しい．
試験分布　　　　から，真の確率分布 　　へのカルバック距離最小化は，以下の式 　　を試験分布　　　　について最小化することと等しい． エントロピー エネルギー項 大域的なエントロピーを局所エントロピーで近似する． ？ 局所エントロピーの線形結合

10 菊池自由エネルギー Over-counting number 平均場自由エネルギー ベーテ自由エネルギー 菊池自由エネルギー
Region集合 平均場自由エネルギー ベーテ自由エネルギー 菊池自由エネルギー Region集合 Region集合 Over-counting number

11 上に凸，下に凸の部分 平均場自由エネルギー ベーテ自由エネルギー 菊池自由エネルギー convex linear convex
concave linear convex concave linear

12 従来法（A.L.Yuille,2002） 菊池自由エネルギー 従来のConvex関数，Concave関数の構成 CCCPの反復法
linear concave

13 内容 背景(A.L. Yuille, 2002) 菊地自由エネルギーに対するCCCPアルゴリズムの拡張 具体例
菊池自由エネルギー（べーテ自由エネルギーを含む） CCCP-Kikuchiアルゴリズム 菊地自由エネルギーに対するCCCPアルゴリズムの拡張 拡張に利用するポイント（メインアイデア） New CCCP-Kikuchi アルゴリズム 具体例 ガウシアングラフィカルモデル(GGM) MPM推定に基づくCDMAマルチユーザ復調

14 拡張のポイント 菊池自由エネルギー 従来のConvex関数，Concave関数の構成 convex linear concave

15 分解の一般化(1/2) 菊池自由エネルギーに対する一般的な分解 特に，汎関数 の関数族として以下で表す擬菊池自由エネルギー の形を選ぶ．
特に，汎関数　　　　の関数族として以下で表す擬菊池自由エネルギー 　　の形を選ぶ． 分解パラメータを含んだConvex関数，Concave関数の構成 ：菊池自由エネルギー

16 分解の一般化(2/2) 分解パラメータを含んだConvex関数，Concave関数の構成 分解パラメータ の定義域
分解パラメータ　　　　　　　　　の定義域 従来のCCCP-Kikuchiアルゴリズムは， 　　集合　　の中の1点に対応する（拡張）． CCCP-Kikuchi 集合　　内で，分解パラメータ　　の値を 　　動的に変化可能．

17 図示（更新の様子） 従来のCCCP-Kikuchi New CCCP-Kikuchi 分解の仕方が静的な更新 分解の仕方が動的な更新

18 New CCCP-Kikuchiアルゴリズム
NCCCP-Kikuchiアルゴリズムは以下の2重ループアルゴリズムで与えられる． 　　ここで　　は　　　　　　を満たす．

19 NCCCP-Kikuchiアルゴリズムの概要
：ラグランジュ未定乗数 ：ビリーフ Outer loop Inner loop 近似周辺分布 Outer LoopとInner Loopは 分割パラメータ　　に依存して 更新される．

20 ここまでのまとめ 菊池自由エネルギーに対するCCCPアルゴリズムの拡張に，菊池自由エネルギーの分解の不定性の自由度を利用した．
パラメータを導入した数（拡張した次元）は，region集合　　の元の数と等しい． アルゴリズムを高次元に拡げたが，単調減少性は破られない． 更新時刻毎に動的に分解の仕方を変えてもよい． Region集合 菊池自由エネルギー CCCP

21 内容 背景(A.L. Yuille, 2002) 菊地自由エネルギーに対するCCCPアルゴリズムの拡張 具体例
菊池自由エネルギー（べーテ自由エネルギーを含む） CCCP-Kikuchiアルゴリズム 菊地自由エネルギーに対するCCCPアルゴリズムの拡張 拡張に利用するポイント（メインアイデア） New CCCP-Kikuchi アルゴリズム 具体例 ガウシアングラフィカルモデル(GGM) MPM推定に基づくCDMAマルチユーザ復調

22 具体例（１） ガウシアングラフィカルモデル（GGM）

23 ガウシアングラフィカルモデル(GGM) グラフが表す同時確率分布が多次元正規分布の場合． 菊地自由エネルギーの中でもベーテ自由エネルギー．
分解パラメータ　　は時刻に依らず一定値． Inner Loopの更新式 非同期式（直列更新）・・・1時刻に1つのパラメータ（ラグランジュの未定乗数）を更新． 同期式（並列更新）・・・1時刻にすべてのパラメータ（ラグランジュの未定乗数）を更新． Region集合

24 アルゴリズム ガウシアングラフィカルモデルに適用したNCCCP-Betheアルゴリズムは， Outer Loop Inner Loop
ここで分割パラメータは　　　　　　　　　　を満たす．

25 非同期式（直列更新） CCCP-Bethe ＊最適性が観測

26 同期式（並列更新） CCCP-Bethe ＊最適性が観測

27 具体例（２） MPM推定に基づくCDMAマルチユーザ復調 （樺島研究室2007年卒，外崎幸徳氏との共同研究．）

28 MPM推定に基づくCDMAマルチユーザ復調
（樺島研究室2007年卒，外崎幸徳氏との共同研究．） CDMA復調問題 基地局で観測された受信信号から，拡散符号の情報を使って，（多数の）ユーザが送った各送信情報を推定する問題． 拡散符号を一様分布から抽出される無相関ランダム系列とする． 受信信号 送信信号 拡散符号 基地局

29 MPM復調 拡散符号 送信信号 受信信号 基地局 受信信号 事後分布 MPM復調 NCCCP-Bethe

30 NCCCP-Bethe(イジングスピン， )
パラメータ の定義域は，　　　　　　　　　である．ただし　　　は確率分布 　　　　　を とおいたとき，　　　　　　　　　　　　　　　　　で与えられる． 指数オーダ

31 NCCCPに基づくCDMAマルチユーザ復調アルゴリズム
パラメータ の定義域は，　　　　　　　　　である．　　　は で与えられる(Kabashima, 2003)．

32 実験パラメータ 負荷率 （ユーザ数，チップ数） 通信路ノイズ Inner Loopの回数　　1回 分解パラメータ　　の値 従来のCCCP

33 ビット誤り率

34 ベーテ自由エネルギーに対する可約条件の破れ度合い

35 分解パラメータ の役割（経験的） CCCP-Kikuchi Inner Loop Outer Loop 収束するまでの更新回数
分解パラメータ　　の役割（経験的） 収束するまでの更新回数 Inner Loop Outer Loop CCCP-Kikuchi 分解パラメータ 小 大

36 最適な軌跡の存在（予想） 菊池自由エネルギーにはCCCPの意味で計算量が最小になる分解系列がある． CCCP-Kikuchi
最適な分解系列，またはそれを近似する系列，に基づく設計方法は今後の課題である（どなたかご教示ください）． CCCP-Kikuchi

37 まとめ 菊池自由エネルギーに対するCCCPアルゴリズムを拡張し(NCCCP-Kikuchi)，計算量の意味で最適な分解の仕方が存在することを示した． ガウシアングラフィカルモデル，CDMAマルチユーザ復調の2つの具体例の場合に，NCCCP-Kikuchiの有効性を示した． 高次元を対象とするときは(“More is different”)，分解パラメータの違いで計算量に大きく差が開くことから，最適性を考慮して設計した方が良い． ループの入った高次元確率分布について期待値計算を行いたいとき，収束保証を取りたい場合には，拡張されたNCCCP-Kikuchiアルゴリズムも選択肢の1つにお加えください．

38 今後の可能性 CCCPアルゴリズムに対する良い分解系列の設計法は？（菊池自由エネルギーに限らなくても良い．）
LDPC符号の復号アルゴリズムとしては？ EMアルゴリズムに分解パラメータは入るのか？ 情報幾何学による記述は？