ベイズ統計学と統計物理学
スパース符号の復元を題材として
誤り訂正符号を題材にして
司馬博文
6/23/2024
6/28/2024
A Blog Entry on Bayesian Computation by an Applied Mathematician
$$
$$
上掲稿で扱ったスパース符号の復元の問題をさらに押し進め,より実用的な誤り訂正符号の設定を考える.
モデルにハイパーパラメータが増え,厳密に証明できる事項は大きく減る.(逆)温度パラメータ
有限体
このクラスの符号については,Hamming 距離
加えて,この線型符号は次の構造を持つ:任意の符号語
1ビットの誤りまでなら,
前掲の例(第 1.1 節)のように,情報ビットと組織ビットが完全に分離している符号を 組織符号 という.
これは,ある行列
このとき,パリティ検査行列
実際,
こうして定まる
パリティ検査行列における誤り訂正では,次の逆問題を考えることになる.
対称通信路が加法的ノイズを印加するならば,受信符号
すると,パリティ検査方程式より,
シンドロームは誤りベクトル
一般に,パリティ検査方程式
しかし,例えばパリティ検査行列が
スピングラスとの類似性を最初に指摘したのは (Sourlas, 1989) であり,すぐに西森ラインとの関連性も知られた (Hidetoshi Nishimori, 2001).
現在ではこの対応は誤り訂正符号に限らず,極めて広範な統計的推定問題に渡っていることが認識されている.
実際,スピングラス理論で開発されたレプリカ法,cavity method, 信念伝搬法は盛んに統計的推定問題に応用されている (Zdeborová and Krzakala, 2016).
Perhaps the most important message we want to pass in this review is that many calculations that physics uses to understand the world can be translated into algorithms that machine learning uses to understand data. (Zdeborová and Krzakala, 2016, p. 457)
スピングラス系にベイズ推定を紐づけることができる.
その際,伝統的にスピングラス理論で扱われた quenched ensemble とも annealed ensemble とも違う第三のアンサンブル planted ensemble を扱うことになる.
配置空間を
この系を絶対零度まで冷却した際,
そうでない場合でも,ファクターグラフ
なお,あるファクターグラフがフラストレーションを持たないかどうかは,クラス P に属する問題である.すなわち,多項式時間で判定可能である.5
相互作用項
スピングラス理論で代表的な (Edwards and Anderson, 1975) モデルでは,
一方でここでは,確率変数
統計的な手続きは,スピングラス系を特殊な方法で生成し,その基底状態を探る逆問題として理解できる.8 こうして生成されたスピングラスを planted ensemble と呼ぶ.
具体的には,前稿 で扱った信号推定の問題で,情報源の分布
最初に設定される Ising スピンの配置
そして信号推定とは,この
二元対称通信路における誤り訂正符号のスピングラス的解釈(第 1.3 節)はこの例の1つに過ぎない.
さらに,
以上,Bayes 推定の文脈でスピングラスの planted ensemble を定義したが,同様にしてスピングラス系の中に情報を隠すことは,よく見られるモデリング法である.
The authors find that making the connection between planting and inference very explicitly brings a lot of insight into a generic inference problem and for this reason we built the present review around this connection. (Zdeborová and Krzakala, 2016, p. 469)
従来の統計学における漸近理論では,パラメータの次元
現代では,モデルのサイズも大きくする
しかしこの場合でも,統計力学のツールボックスはこれを可能にする.
特に,比
一般に,
実際に,比例的高次元極限では,前稿でみた閾値現象が普遍的に生じることが知られている.これが,スピングラスの相転移に対応するのである.
前節 2.2 の解釈では,観測
ただし,ここで,観測者の立てたモデルにおいて,パラメータ
仮に観測者の用いたパラメータが真のパラメータと一致していた
中でも特に,次の性質は 西森対称性 と呼ばれている:14
この西森対称性を通じて,自由エネルギー(= KL 乖離度)をはじめとした厳密解が求まるのである.そのことを簡単なモデルで確認したのが 前稿 である.
西森対称性とは,planted ensemble において,元々の配置
西森対称性を用いた厳密解は,前稿で多く紹介している:
前稿では信号推定の問題を扱ったが,情報源分布
すなわち,信号推定の問題は,自然に西森ライン上で議論している場合に当たるのである.
一般に,事後平均推定量
一般にこの値は不可知であるが,西森ライン上では=モデルの特定が成功している場合,
これが 命題
換言すれば,Boltzmann 分布のうち,
スピングラスでは,ランダムに定まる相互作用項
後者に関する平均は
従来のスピングラス理論では,disorder
系が大きくなるほど,
従ってこの quenched average を求めることが中心問題とされる:
しかしこれに解決が難しく,値を計算するヒューリスティックとしてレプリカトリックが用いられる:
一方で,次の値は計算が簡単であり,quenched average の下からの評価として用いられることがある:
こうして,quenched ensemble, average ensemble の両方が用いられることがあるが,この両方に共通していたのが
しかし,planted ensemble ではこのアプローチをとっていない.
This notion of averaging over disorder is so well engraved into a physicist’s mind that going away from this framework and starting to use the related (replica and cavity) calculations for a single realization of the disorder has lead to a major paradigm shift and to the development of revolutionary algorithms such as the survey propagation (M. Mézard et al., 2002).
なお,この要約伝搬法は Bethe 近似に関係がある (Kabashima, 2005).
一方で,planted ensemble では,スピンの配置を決めてから,
それだけでなく,スピングラス転移などの物理現象に関しても示唆を与える対象だとわかりつつある.18
レプリカ対称性は大雑把に,平衡状態のダイナミクスの緩和過程によって表現できる.
事後分布
RSB 下では,
平衡状態から開始する Glauber 動力学を考えると,例えば
特に,ある自発磁化密度
この「準平衡状態」と言える状態にとらわれる現象は普遍的であるが,この「準平衡状態」が,初期位置の関数として,時間にも空間にも不変性が存在しないときが,スピングラスである.
誤り訂正符号を例に取り,censored block model (Abbe et al., 2014) とも呼ばれる具体的な planted ensemble を考える.22
この設定下では,事後分布は
これは,Hamiltonian
この設定下では,
まず,二元対称通信路における誤り訂正符号としての見方ができる (Iba, 1999, pp. 3879 3節)
次に,teacher-student sinario としての見方もできる (Zdeborová and Krzakala, 2016, pp. 473–2.1節)
生徒は,人物
そこで,前節の計算に基づき,事後分布を分布族
ただし,この真のハイパーパラメータの値
このとき例えば,平均正解個数を最大化した MMO (Maximum Mean Overlap) 復号をしたいならば,26
こうして,推定の問題が,スピングラスの planted ensemble の平衡状態のシミュレーションや基底状態の探索の問題に翻訳されたことになる.
特に,
西森ラインは元々,純粋に Hamiltonian
(H. Nishimori, 1980) では,この Hamiltonian (3) が,任意の点
この変換を真の配置
続いて,相互作用項
こうして,今回の設定 3.1 も Edwards-Anderson モデルに帰着され,この設定の中で全てのスピンが揃った強磁性状態を探索する問題に変換される.
この
このとき,Edwards-Anderson モデルは
この条件
西森ラインは,相転移点
そして何より,途中でスピングラス相を通過しない.32
一般の模型に対してこのようなゲージ変換が見つかるわけでもなければ,その変換の物理的な意味が定かでない.
しかし,西森ラインとは,今回の設定 3.1,または一般の planted spin glass model (第 2.2 節)において,モデルが正しく特定されていること
西森ラインの存在は長らく謎であったが,ベイズ推論の文脈では明確な意味を持つのである.特に,ゲージ対称性が存在しないモデルであっても,第 2.2 節の teacher-student scenario に当てはまる統計問題である限り,対応するスピングラス系に西森ラインは考えられる.33
西森条件とは,モデルが正しく特定されている場合に成り立つ魅力的な性質の数々であると理解できる.
モデルの特定が正しかったとする:
高温領域
一方で,低温領域
これら2つの領域の中間に「推定可能だが,計算が困難」という状態(スピングラス相)は存在せず,2つの領域の間には二次の相転移が見られる.34
モデルの真のハイパーパラメータ
スピングラス相,過学習,いずれの現象も,西森ライン上では見られない.スピングラス系の不可知な性質は,真のモデルが不明な場合の推定問題の困難さと同根なのである.
以上の,Edwards-Anderson 模型の相図は,統計推測において「ハイパーパラメータ
実際,EM アルゴリズム (Dempster et al., 1977) はこれを考慮した MAP 推定と捉えられる.
EM アルゴリズムは,エビデンス
具体的には,温度
スピングラスで西森ラインから外れた状態では物理量の正確な計算が困難であるように,EM アルゴリズムでも一般に
また,自由エネルギーの代わりに内部エネルギーを用い,最大値点
即ち,西森条件を「成り立ってほしい条件」として,ハイパーパラメータの最大化に用いる方法が EM アルゴリズムであるとも捉えられるのである.
モデルの誤特定
この「泥沼」とは,物理的に正確な意味で,スピングラスであったわけだ.
逆に,モデルを正しく特定できているとき.通信の問題において,encoding と channel のモデルが正しく理解されているとき,復号難易度は大きく下がるはずである.これが,西森ライン上で物理量の計算が一気に簡単になる理由である.
西森ライン ともいう.(Iba, 1999),(西森秀稔, 1999, p. 55)など参照.↩︎
(横尾英俊, 2004, p. 106) も参照.↩︎
(樺島祥介 and 杉浦正康, 2008, p. 28) も参照.↩︎
充足可能性問題と違い,3項以上の相互作用を考えてもクラス P のままである.(Marc Mézard and Montanari, 2009, p. 246) や (樺島祥介 and 杉浦正康, 2008) も参照.↩︎
例えば (Talagrand, 2011) など.↩︎
従って,planted ensemble における
特に,信号処理などの情報科学的な設定で,この対応がつけやすい.というのも,一般の統計的な問題では,「スピングラスを生成する」部分に相当するような,データ生成過程に対する事前知識を持っていることが稀であり,モデル選択も重要なトピックに入るためである.一方で,スピングラス系と対応づけるとき,モデル選択は一般に射程には入らない.(Zdeborová and Krzakala, 2016, p. 456) も参照.一般の統計的問題を,どのようにしてスピングラスの planted ensemble と対応づけられるかについては,(Zdeborová and Krzakala, 2016, p. 468) 1.3.2 節を参照.↩︎
こうして生成されたスピングラス系を,planted ensemble と呼び,このシナリオを機械学習の訓練過程に準えて teacher-student scenario とも呼ぶのが (Zdeborová and Krzakala, 2016, p. 462) の用語である.これを (Iba, 1999, p. 3881) は符号理論に準えて,encoding-decoding scenario と呼ぶべき設定で解説している.(Marc Mézard and Montanari, 2009, p. 249) にも同様の通信に準えた記述がある.なお,最後の2つの文献では,事前分布
前稿 では,この
この
(Zdeborová and Krzakala, 2016, p. 468) に多くの関連文献がまとめられている.↩︎
(Zdeborová and Krzakala, 2016, p. 475) 2.1 節も参照.(Krzakala et al., 2015, p. 13) の
(Marc Mézard and Montanari, 2009, p. 249) では
(Zdeborová and Krzakala, 2016, pp. 480–2.5節),(Marc Mézard and Montanari, 2009, pp. 102 5.4節) が詳しい.↩︎
数学的な説明としては (Talagrand, 2011, p. 7) も参照.↩︎
このことは物理学にも進展を与えており,従来考えられなかった解析が進むことがあるという. (Krzakala et al., 2015, pp. 10 2.3節) や (Zdeborová and Krzakala, 2016, p. 483) 2.5.3 節 Quiet Planing を参照ください.↩︎
(Zdeborová and Krzakala, 2016, p. 483) 2.6 節,(Marc Mézard and Montanari, 2009, p. 253) 12.3.3 節.↩︎
(Zdeborová and Krzakala, 2016, p. 483) 2.6 節の興味深い説明方法.↩︎
(Marc Mézard and Montanari, 2009, p. 250) 12.3.1 節参照.↩︎
(Mattis, 1976) のモデルとも深い関連があるという.(Zdeborová and Krzakala, 2016, p. 474) も参照.ここでは planted SG model と呼ばれている.↩︎
すなわち,
従って,各
(Zdeborová and Krzakala, 2016, p. 475),(Iba, 1999, p. 3879).↩︎
(Krzakala et al., 2015, p. 6) では MARG (Minimal Error Assignments Estimator) と呼ばれている.↩︎
また,平均場の設定では cavity method によって解ける.(Zdeborová and Krzakala, 2016, p. 475) も参照.↩︎
この同一視は,Nishimori ensemble と planted ensemble との同一視と論じることもできる (Krzakala et al., 2015, p. 12) 2.6 節.↩︎
(H. Nishimori, 1980) の報告である.(西森秀稔, 1999, pp. 53–),(Iba, 1999, p. 3879) 式 (25),(Marc Mézard and Montanari, 2009, p. 248) 式 (12.15) も参照.平均次数
(西森秀稔, 1999, p. 55) も参照.↩︎
これは静的な RSB 相が存在しないことを言う.1次の相転移,動的な one-step RSB (d1RSB) 相などは見られることがある (Zdeborová and Krzakala, 2016, pp. 484 2.7節).↩︎
(Iba, 1999, p. 3882) の時点で示唆されていた考え方である.↩︎
(Zdeborová and Krzakala, 2016, p. 479) 2.4節による素晴らしい洞察!↩︎