# 無向グラフィカルモデル > [!note] 別文脈との違い: 本ページは確率変数の同時分布を表す**無向**グラフ(マルコフ確率場・マルコフネットワーク)を扱う。同じ同時分布の因子分解を**有向**グラフ(ベイズネットワーク)で表す [[有向グラフィカルモデル]]、有向グラフによる因果構造の推定を扱う [[因果発見]]、グラフ構造データ上のニューラルネットワークを扱う [[グラフニューラルネットワーク]]、実体・関係のトリプル表現を扱う [[知識グラフ]]、対象間の関係を推論するニューラルアーキテクチャを扱う [[関係推論]] とは、いずれも「グラフ」という語を共有するが別概念である。特に因果発見が推定する有向グラフは辺に向きと因果的解釈を持つのに対し、本ページの無向グラフは辺の**欠如**だけが意味を持ち、方向を持たない。 ## 定義 無向グラフィカルモデル(undirected graphical model)とは、確率変数の集合を頂点、変数間の依存関係を無向の辺として表現し、**辺の欠如が対応する2変数の条件付き独立を意味する**確率モデルである。統計学ではマルコフ確率場(Markov random field)、マルコフネットワーク(Markov network)とも呼ばれる。グラフ$G=(V,E)$上で、頂点$X$と$Y$の間に辺がなければ、残りすべての変数$\text{rest}$で条件付けたとき$X\perp Y\mid\text{rest}$が成り立つ(対単位マルコフ独立性)。部分グラフ$C$が$A$と$B$を分離するなら$A\perp B\mid C$が成り立つ(大域マルコフ性)。正の確率分布を持つグラフではこの2つの性質は同値であり(Hammersley-Clifford定理)、グラフ上の確率密度は極大クリークごとのポテンシャル関数の積$f(x)=\frac1Z\prod_{C}\psi_C(x_C)$として表現できる。モデルの推定は、グラフ構造の推定(どの辺が存在するか)と辺のパラメータの推定という2つの課題に分かれる。(Source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 17 Undirected Graphical Models]] §17.1-§17.2) ## 連続変数: ガウスグラフィカルモデルと精度行列 変数が多変量正規分布$N(\mu,\Sigma)$に従うとき、逆共分散行列(精度行列)$\Theta=\Sigma^{-1}$の$(i,j)$成分がゼロであることは、変数$i,j$が他の変数で条件付けたとき条件付き独立であることと等価である。したがってガウスグラフィカルモデルでは**グラフ構造の推定が精度行列のスパースパターンの推定に帰着する**。構造が既知のときは、精度行列を1行1列ずつ「結合された」回帰問題として解く反復手続き(修正回帰アルゴリズム)でパラメータを推定できる。(Source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 17 Undirected Graphical Models]] §17.3-§17.3.1) ## 構造推定: graphical lasso 構造が未知のときは、精度行列にL1罰則を課した対数尤度$\log\det\Theta-\mathrm{trace}(S\Theta)-\lambda\|\Theta\|_1$を最大化することで、グラフ構造とパラメータを同時に推定できる(**graphical lasso**、Friedman et al. 2008)。罰則パラメータ$\lambda$を大きくするほどグラフは疎になり、$\lambda\to\infty$は構造既知の場合(全辺を消去)に帰着する。より単純な代替手法として、各変数を目的変数・残りを説明変数とするnode-wiseなlasso回帰を全変数に行い、係数の非零性から辺の有無を判定するneighborhood selection(Meinshausen and Bühlmann, 2006)もある。graphical lassoとの詳しい関係は [[縮小推定]] を参照(lasso罰則を係数ベクトルではなく精度行列という行列パラメータへ適用した変種として位置づけられる)。(Source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 17 Undirected Graphical Models]] §17.3.2) ## 離散変数: イジングモデルと計算困難性 2値変数$X_j\in\{0,1\}$のペア単位マルコフグラフはイジングモデル(統計力学分野の呼称。機械学習分野ではボルツマンマシンと呼ぶ)$p(X,\Theta)=\exp[\sum_{(j,k)\in E}\theta_{jk}X_jX_k-\Phi(\Theta)]$で表される。対数尤度の勾配は周辺期待値$E_\Theta(X_jX_k)$を要求し、この厳密計算は$2^{p-2}$通りの状態にわたる和のため変数数$p$の増加とともに指数的に困難になる($p>30$程度で非現実的)。$p$が大きい場合は平均場近似やギブスサンプリングによる近似が必要になる。(Source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 17 Undirected Graphical Models]] §17.4-§17.4.1) ## 隠れノードと制限ボルツマンマシン(RBM) ガウスモデルでは隠れノード(観測されない頂点)を導入しても、線形性のため周辺化すれば観測ノード上の別のガウスモデルが得られるにすぎずモデルの表現力は実質的に拡張されない。一方、離散モデルでは非線形性のため隠れユニットがモデルの表現力を拡張する強力な手段になる。**制限ボルツマンマシン(RBM)**は可視層と隠れ層からなり層内結合を持たないイジングモデルの一種で、層内結合がないため同一層をまとめてギブスサンプリングできる。**対照的発散法(contrastive divergence、Hinton 2002)**はマルコフ連鎖をデータから開始し少数ステップで打ち切ることで学習を実用化する。RBMは単一隠れ層ニューラルネットワークと同じ一般形を持つが、エッジが無向であり、教師あり誤差ではなく全可視ユニットの同時分布の対数尤度を最大化する点が異なる。(Source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 17 Undirected Graphical Models]] §17.4.4) ## 横断的知見 - **有向グラフの因子分解は局所正規化ずみのため大域的な分配関数を要らず、無向グラフは代償として分配関数の困難な計算を負う**: [[有向グラフィカルモデル]] の因子分解 $p(x)=\prod_k p(x_k\mid\text{Pa}_k)$ は各項が既に正規化された条件付き確率分布であるため積全体が自動的に1に正規化されるのに対し、本ページの因子分解 $f(x)=\frac1Z\prod_C\psi_C(x_C)$(Hammersley-Clifford定理)はポテンシャル関数 $\psi_C$ が確率分布である保証がなく、分配関数 $Z$ による大域的な正規化を別途必要とする。この正規化の要否の違いが、条件付き独立性の判定方法の違い(無向グラフの単純な分離 vs 有向グラフのd分離)にも直結する。一方、本ページのイジングモデル(§17.4)のように変数間にループ状の相互依存を持つ構造は、非巡回性を要求する有向グラフでは表現できず、無向グラフが分配関数の計算困難性という代償のもとで初めて許容する対象である。(Source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 17 Undirected Graphical Models]] §17.1-§17.2, §17.4-§17.4.1, [[@2020__Cambridge__Mathematics for Machine Learning - Chapter 8 When Models Meet Data]] §8.5.1-§8.5.2) ## 未解決の問い - graphical lassoはガウス連続変数に対してΣとΘの両方の推定値を与えるが、イジングモデルの近似手法(Wainwright et al. 2007のnode-wise L1正則化ロジスティック回帰)はΘの推定のみを目的とし逆行列は関心の対象外になる。この非対称性(連続では両方に関心があり、離散ではΘのみに関心がある)は、応用上どのような場面で問題になるか。 - $p>30$の離散グラフィカルモデルで、平均場近似とギブスサンプリングのどちらを選ぶべきかの実用的な判断基準は、本章では明示的に与えられていない。近似誤差と計算コストのトレードオフを定量化する指標はあるか。 - graphical lassoの構造推定における罰則パラメータ$\lambda$の選択(交差検証等)は、[[縮小推定]]で蓄積されているlasso回帰の罰則選択の知見(1標準誤差則等)とどこまで共通し、どこでグラフ構造特有の考慮(疎性パターンの安定性等)が必要になるか。 - RBMの層ごとの貪欲学習(第1RBM→第2RBM→…)がなぜうまく機能するかの理論的正当化は、Hinton et al. (2006)に委ねられ本章では詳述されない。この貪欲学習と、後続の深層学習における層ごとの事前学習の関係はどこまで一般化できるか。 ## 関連 - 概念: [[縮小推定]](graphical lassoはlasso罰則の精度行列への適用) / [[部分集合選択]](グラフ構造推定は辺の部分集合選択と同型) / [[統計的機械学習]] / [[有向グラフィカルモデル]](同じ同時分布の因子分解を有向グラフで表す姉妹概念) - ソース: [[@2009__Springer__The Elements of Statistical Learning - Chapter 17 Undirected Graphical Models]] / [[@2020__Cambridge__Mathematics for Machine Learning - Chapter 8 When Models Meet Data]] - 別概念(要注意): [[因果発見]](有向グラフによる因果構造推定。本ページの無向グラフとは辺の意味論が異なる) / [[グラフニューラルネットワーク]](グラフ構造データ上のニューラルネットワークアーキテクチャ) / [[知識グラフ]](実体・関係のトリプル表現) / [[関係推論]](ニューラルネットワークによる関係推論アーキテクチャ) ## 出典 - Hastie, T., Tibshirani, R., Friedman, J., *The Elements of Statistical Learning*, 2nd Edition, Springer, 2009, Chapter 17.