Graph Model Message Passing vs. Nerual Net BackProp vs. Variational Inference

by allenlu2007

前文介紹 Gaussian message.   主要的缺點是如果通過某一些 block (非 +, =, gain) Gaussian 就會被破壞。

解決的方法是 variational inference, 其實就是 approxmiation, 假設還是 Gaussian.

但在 neural network 也有 forward path 和 error backward propagation.  似乎更 general.

也是只 pass variational message (dE/dW, or dE/dX) back prop.  但只用 1st order statistics.  因為經過 nonlinear block (e.g. sigmoid), cost function 已經非 convex.  即使用 2nd order statistics 也沒用?

 

Gaussian message –> 2nd order statistics,  fast but limited use (not Gaussian)

Variation inference –> 2nd order or 1st order statistics? 2nd order

Neural back prop –> 1st order statistics

 

–> 這些觀念應該可以 combine 在一起。雖然一個是 Bayesian, 另一個是 neural network.

 

 

前文介紹 Forney factor graph (FFG) 的基本型。FFG 可以用在更複雜的 case.

介紹完 FFG 進階型之後,討論最重要的 continuous message: Gaussian message.

主要是 Gaussian message 可以得到 close form, 同時可用為其他 continuous message 的近似。

再來應用 Gaussian message 在 Kalman filter.

 

FFG 進階型  

1. variable X 出現在兩個以上的 factor, 可以用 “=” factor, 代表 delta function.

NewImage

 

2. 可以 generalize “=” factor to block diagram factor 如下

NewImage

 Let  U = x3,  X = x3′, Z = x3”;  g(u,w) = U;  h(X,Y) = X 就可化簡為 1.

 

Discrete and Continuous

Discrete message passing (from factor to variable)

NewImage

Continuous message passing (from factor to variable)

NewImage

Special case, if Y = h(X1) is a delta function;  u(y) = u(X1) as expected

 

對於 continuous message passing 的幾種近似法

NewImage

 

Gaussian Message (reference)

故名思義,Gaussian message 的 message 的型式就是 Gaussian distribution 如下。

NewImage

 

接下來就是 Gaussian message 在 sum-product 以積分代替 summation:

NewImage

 

  • Gaussian message 的 products 還是 Gaussian message
  • (7) 的 integration (marginalization) 也是 Gaussian form
  • 更進一步,上述的 u(x1), u(x2), .. u(xm) 以及 h(y, x1…, xm) 如果是 Gaussian form, u(y) 也是 Gaussian message!!!

先考慮簡單的 case if q(x, y) is the quadratic form: 

NewImage

  • 注意原來的 integration 變成 minimization !!
更重要的是 delta function 可以變為 Gaussian function 如下:
NewImage

因此原來的

NewImage

or 

NewImage 

就變成:

 NewImage

同時比較 max-product rule:

NewImage 

如果f, u1, … un are Gaussian,  (16) 和上述公式會得到同樣的結果t!!

  • 如果 factor 和所有 input message 都是 Gaussian form, output message 也是 Gaussian form!
  • 以上,sum-product 和 min-sum 在 Gaussian message 和 Gaussian factor 是等價!!
  • 所謂的 Gaussian factor 最簡單就是 linear combination, (“=”, “+”, scaling, etc.) 可以用 delta function 表示。delta function 可以用 Gaussian function 表示。
  • 如果 factor 不是 Gaussian form, output message 就不是 Gaussian message (e.g. Extended Kalman filter, Unscented Kalman filter).  當然 sum-product 和 max-product 的結果也不同。
  • Exponential family message passing (variational message passing): if input message and factor are exponential family, output message is also exponential family?  (Yes?)  sum-product and max-product are equivalent? (No?)

 

Example

Equality constraint 如下圖 1:

NewImage 

非常漂亮簡潔的推導!  Brute force 推導如下下圖,非常 dirty 也沒有太多 insight. 

 

NewImage

NewImage 

 

NewImage

NewImage

其他的推導請參考 reference.   Some composite blocks 結果如下

 NewImage

Rule 6: Vx = A-1Vy A-H 是錯的。正確如下:

NewImage

NewImage

NewImage

Rule 5 是 Rule 6 duality. 

NewImage

 

In more details (Gaussian assumption may be relaxed for some rules)

NewImage 

NewImage

NewImage

NewImage

 

Kalman Filter (Gaussian Message + HMM)

Kalman filter 的 model 如下 (similar to HMM)

NewImage

重新看 Kalman filter 和以上公式的關係

NewImage

 

正好用到 Rule 3/4, Rule 6, and Rule5.   “+” 相當 variance/covariance 串聯; “=” 相當 variance/covariance 並聯。對於 variance/covariance^(-1) 剛好相反。

更細來說 Rule 3/4 和 Rule 6 對所有 message (distribution) 都適用 (A is invertible); 只有 Rule 5 需要 Gaussian message.  Practically speaking, 當有夠多的 Uk and Wk, Xk 最後趨近 Gaussian message (central limit theorem).

推導 Kalman Filter

Step 1:  Entry6 的 output, denoted Xk_hat (Kalman filter 的 estimation stage) and assuming mean Uk and covariance = Q, b = 1

          Xk_hat 的 forward Gaussian message

          mean = A m(k-1) + Uk

          covariance = A V(k-1) A^H + Q

Step 2: Entry 5 的 output Xk (Kalman filter 的 update stage) and assuming Wk zero mean and covariance R.

Xk 的 forward Gaussian message  如下

NewImage

 

Eq. (35) 即是 Kalman filter 中的 mean.  (Xk 的 mean) = (xk_hat 的 mean) + (Kalman gain) * innovation

 innovation = (observation – prediction) 

 Kalman gain = Vinx A^H ( VinY + AVinxA^H)-1 = Vinx A^H (R + A Vinx A^H)-1

 

Eq. (36) 則是 Kalman filter 中的 covariance

Voutz = (I – Vinx A^H G A) Vinx = ( I – Kg * A) (xk_hat 的 covariance)

 

In summary:  Eq (35) 和 Eq (36) 就是熟知的 Kalman filter = Forward Gaussian message

 

推導 Kalman Smoother

Kalman filter:  就是找 Gaussian conditional pdf: P(xk | y1, y2, …yk) given current observables (real-time)

Kalman smoother: 就是找 Gaussian conditional pdf: P(xk | y1, y2, … yT) given all observables (non real-time)

 

Q: Kalman filter 是 forward message.  那 Kalman smoother 是 backward message? 

A: No.  smoother 是 (forward message) * (backward message), i.e. product of forward and backward message.

也就是 P(x(k)) | all observed y)

 

如何推導? TBD.  以下是 high level 的說明,不是証明。

Kalman filter 是 alpha (forward message); Kalman smoother 是 alpha * beta, i.e. (forward message)*(backward message).  如果真的用 (forward message)*(backward message) 來推導 Kalman smoother 的 close form.  應該會非常 messy.  Reference 只用 forward message 來推導 Kalman filter.  同樣方法應可用在 Kalman smoother.

實際上 Kalman smoother 是用 conditional PDF 來推導 recursive close form,參考 reference.

 

下圖是用 HMM 來看 Kalman smoother (Z 是 state variable, X 是 observable)

f(zn, zn-1) 是濃縮的 factor = (transition probability) * (emission probability)

NewImage

NewImage

NewImage 

NewImage

 

Q&A

Q: 在 Gaussian message 時,Marginalization (sum product) and Maximization (max product, MAP) 得到的 message 剛好相同 

A: Yes. 但必須包含 factor.  Factor 也必須是 Gaussian form, 如 delta function 或 linear combination.

 

Q: 在 Kalman filter 中,sum-product 代表 P(xk | y1, … yk) 的 mean and variance (minimum mean square error); max-product 則是 ML estimator (most likely).  這兩個結果一樣。HMM 有同樣結果嗎?

A:  No,  HMM 非 Gaussian message.  HMM 是 discrete PMF.  Sum-product algorithm 對應 forward-backward message (alpha-beta).   類似的 Baum-Welch algorithm belongs to sum product algorithm (EM algorithm)!

Max-product algorithm 在 HMM 對應的是 Viterbi family algorithm (VA, SOVA, hard-decision VA).  

 

Viterbi in Gaussian Messge

Q: 在 HMM model, most probable sequence 和 most probable values 是不同的。

most probable sequence: Viterbi algorithm

most probable value: forward-backward algorithm (alpha * beta)

在 Gaussian message (continuous HMM) 也有類似的 algorithm 嗎?


A: No.  在 Continuous HMM Gaussian message both 

most probable value: forward-backward algorithm (i.e. Kalman smoother)

most probable sequence: forward-backward algorithm (i.e. Kalman smoother)

原因 sum-product (forward-backward) and max-product (VA) 在 Gaussian message 等價!!

 

NewImage 

Or 

 NewImage

 

 

NewImage

 

 

Advertisements