---

Stochastic Gradient Descent (SGD) 算法:

$$\begin{align*} \quad w_{k+1}=w_k-\alpha_k\nabla_wf(w_k,x_k) \end{align*}$$ 其中 $f$ 是要 minimized 的目標函數, $x_k$, $w_k$ 是 $k$-th iteration 的 data 和 weight.
以前在學的時候都會提到 step size $\alpha_k$ 有這樣一個神奇的條件:
$$\sum_{k=1}^\infty \alpha_k^2<\infty,\quad \sum_{k=1}^\infty \alpha_k=\infty;$$ 左邊的條件希望 step size 要愈來愈小, 而右邊的條件又說也不能太小.
聽起來就有點神奇, 不知道藏了什麼秘密在裡面.
直到許多年後, 在我學赵世钰老師的 RL 課程第 6 章的時候才解開了以前不懂的地方.

鄭重介紹 Robbins-Monro (RM) 算法!

RM 可說十分重要, 除了可以證明 SGD 是 RM 算法的一個 special case. (因此只要保證滿足 RM 收斂的條件, SGD 就會收斂)
同時 RL (強化學習) 裡經典的 Temporal Difference (TD), Q-Learning 等的方法也依賴 RM 算法的觀念.
所以 RM 算法可說是 RL 的基石之一! 知道 RM 算法還是相當有好處的.
以下特別筆記赵世钰老師的 RL 課程第 6 章 內容.

---

故事的開始從想看懂生成式模型的 flow matching 方法.
搜尋一下需要的數學知識, 大概還需要補 ordinary/partial differential equations, vector calculus (Gauss divergence theorem, Continuity equation), numerical methods for solving PDEs.
這些知識正好就是 Coursera 這門專項課的內容: Mathematics for Engineers Specialization by Prof. Jeffrey R. Chasnov
用了四個月的時間很充實又愉快的學習了四門課程

好啦我承認也花了點上班時間來學習 😆, 主要假日盡量投入, 確實有點辛苦

說一下四門課的心得內容:

---

筆記來源 [DeepBayes2019]: Day 5, Lecture 3. Langevin dynamics for sampling and global optimization 前半小時. 非常精彩!

粒子 $x$ follow Langevin dynamics 的話 ($x’$ 為此時的位置, $x$ 為經過無窮小的時間, $dt$, 後的位置): $$x-x'=-\nabla U(x')dt+\sigma\sqrt{dt}\mathcal{N}(0,I)$$ 則 $x$ 隨時間的機率分布 $p_t(x)$ 會滿足 Fokker-Planck equation 這種 Stochastic Differential Equation (SDE) 的形式:
$$\frac{\partial }{\partial t}p_t(x)=\nabla p_t(x)^T\nabla U(x)+p_t(x)\text{div}\nabla U(x)+\frac{1}{2}\sigma^2\nabla^2p_t(x)$$ 其中 $\nabla^2$ 是 Laplacian operator, 定義是 $\nabla^2 f := \sum_i {(\partial^2f / \partial x_i^2})$, 而 $\text{div}$ 是 divergence 定義是 $\nabla^2 F := \sum_i {(\partial F_i / \partial x_i})$.
或這麼寫也可以 (用 $\text{div}(p\vec u)=\nabla p^T\vec u+p\text{div}(\vec u)$ 公式, 更多 divergence/curl 的微分[參考這, or YouTube]):
$$\frac{\partial }{\partial t}p_t(x)=\text{div}(p_t(x)\nabla U(x))+\frac{1}{2}\sigma^2\nabla^2p_t(x)$$ 而從 F-P equation 我們可以發現最後 $t\rightarrow\infty$ 時某種設定下會有 stationary 分佈.
而如果將要採樣的目標分佈 $p(x)$ 設定成這種 stationary 分佈的話.
由於是 stationary 表示就算繼續 follow Langevin dynamics 讓粒子 $x$ 移動 (更新), 更新後的值仍然滿足目標分佈 $p(x)$, 因此達到採樣效果!
而這也是 Denoising Diffusion Probabilistic Models (DDPM) 做採樣時的方法.

接著詳細記錄 Langevin dynamics, Fokker-Planck equation 推導, 以及 stationary 分佈和採樣方法.

如果讀者知道 Continuity equation 的話, 應該會發現與 F-P equation 非常相似. 它們的關聯可以參考 “Flow Matching for Generative Modeling” 論文的 Appendix D.

---

接續上一篇: 讀 Flow Matching 前要先理解的東西 (建議先閱讀)

Flow matching 模型在時間 $t=0$ 的時候從常態分佈出發 $p_0(x)=\mathcal{N}(0,I)$, 隨著時間變化其 pdf, 例如時間 $t$ 時的 pdf 變化成為 $p_t(x)$, 直到時間 $t=1$ 時希望變成接近目標分佈 $q(x)$, 即希望 $p_1(x)\approx q(x)$.
概念是頭尾 pdf 確定後, 中間這無限多種可能的 $p_t(x)$ 變化經過作者的巧妙設定, 讓學 vector field $u_t(x)$ 變的可能! (不學 pdf 而是學 vector field)
結果就是用 NN 學到的 $u_t(x)$ 可以讓 pdf 從開頭的常態分佈一路變化到最後的資料目標分佈 $q(x)$.

---

Maximum likelihood estimation (MLE) 是機器學習 (ML) 中許多模型優化的目標函式
應該是大家學習 ML 一開始就接觸的內容, 但其實它可能比你想的還複雜
本文分兩大段落:
 A. Maximum Likelihood Estimation (MLE):
  簡單說明 MLE 後, 點出實務上會遇到的問題, 然後與 mean square error (MSE) 和 KL divergence 的關聯
 B. 生成模型想學什麼:
  先說明生成模型的設定, 然後帶到有隱變量的 MLE
  最後點出 VAE, Diffusion (DDPM), GAN, Flow-based 和 Continuous Normalizing Flow (CNF) 這些生成模型與 MLE 的關聯

---

下一篇: 嘗試理解 Flow Matching

如果你跟我一樣看 flow matching 論文時, 在還在說明預備知識的地方就陣亡了, 別擔心你不孤單! 我也死在那裡.
論文裡很多地方用到了 Continuity Equation 來推導. 這個定理也相當於是一個核心概念.
抱持一定要了解清楚的想法, 結果是學習到了美妙的 Gauss’s Divergence Theorem 和 Continuity Equation!
通了! 通暢了! …. 我指任督二脈
🎉 也剛好這是本部落格第 100 篇的文章, 就決定用這個主題了! 🎉
讓我們進入這美妙的 “物理 feat 機器學習 (Physics x ML)” 的世界吧!
(本文用的圖檔: div_fig.drawio)

我們分成幾大段落來說明:
 A. Vector Field
 B. Divergence (散度)
 C. Gauss’s Divergence Theorem
 D. Mass Conservation or Continuity Equation
 E. 跟 Flow Matching 有啥關聯?

---

隱變量的內插

還記得經典的 word embedding 特性嗎? 在當時 Mikolov 這篇經典的 word2vec 論文可讓人震驚了
$$\mathbf{e}_{king}+(\mathbf{e}_{man}-\mathbf{e}_{woman})\approx\mathbf{e}_{queen}$$ 這樣看起來 embedding space 似乎滿足某些線性特性, 使得我們後來在做 embedding 的內插往往採用線性內插:
$$\mathbf{e}_{new}=t\mathbf{e}_1+(1-t)\mathbf{e}_2$$ 讓我們把話題轉到 generative model 上面
不管是 VAE, GAN, flow-based, diffusion-based or flow matching models 都是利用 NN 學習如何從一個”簡單容易採樣”的分布, e.g. standard normal distribution $\mathcal{N}(\mathbf{0},\mathbf{I})$, 到資料分布 $p_{data}$ 的一個過程.
$$\mathbf{x}=\text{Decoder}_\theta(\mathbf{z}),\quad \mathbf{z}\sim\mathcal{N}(\mathbf{0},\mathbf{I})$$

Lil’Log “What are Diffusion Models?” Fig. 1. 的 variable $\mathbf{z}$ 實務上大多使用 $\mathcal{N}(\mathbf{0},\mathbf{I})$ 的設定

(借用 Jia-Bin Huang 影片的圖 How I Understand Diffusion Models 來舉例)

因此如果我們想產生狗和牛的混合體, 是不是可以這樣作?
$$\text{Decoder}_\theta(t\mathbf{z}_{dog}+(1-t)\mathbf{z}_{cow}), \quad t\in[0,1]$$ 答案是不行, 效果不好. 那具體怎麼做呢? 其實應該這麼做 [1]
$$\text{Decoder}_\theta(\cos(t\pi/2)\mathbf{z}_{dog}+\sin(t\pi/2)\mathbf{z}_{cow}), \quad t\in[0,1]$$ 要使用 spherical linear interpolation [2] 這種內插方式

---

Coursera Stochastic Processes 課程筆記, 共十篇:

• Week 0: 一些預備知識
• Week 1: Introduction & Renewal processes
• Week 2: Poisson Processes
• Week3: Markov Chains
• Week 4: Gaussian Processes
• Week 5: Stationarity and Linear filters
• Week 6: Ergodicity, differentiability, continuity
• Week 7: Stochastic integration & Itô formula
• Week 8: Lévy processes
• 整理隨機過程的連續性、微分、積分和Brownian Motion (本文)

根據之前上的 Stochastic processes 課程, 針對以下幾點整理出各自的定義、充分或充要條件:
 - 隨機過程的連續性 (Stochastic continuity)
 - 隨機過程的微分 (Stochastic differentiability)
 - 隨機過程的積分 (Stochasitc Integral)
 - Brownian Motion

每次過段時間都忘記, 查找起來也麻煩, 因此整理一篇

---

Maximal Log-likelihood 是很多模型訓練時目標函式. 在訓練時除了 observed data $x$ (蒐集到的 training data) 還會有無法觀測的 hidden variable $z$ (例如 VAE 中 encoder 的結果).
如何在有隱變量情況下做 MLE, Evidence Lower BOund (ELBO) 就是關鍵. 一般來說, 因為 ELBO 是 MLE 目標函式的 lower bound, 所以藉由最大化 ELBO 來盡可能最大化 likelihood. 另外這個過程也可以用來找出逼近後驗概率 $p(z|x)$ 的函式. 本文記錄了 ELBO 在 Variational Inference (VI), Expectation Maximization (EM) algorithm, 以及 Diffusion Model 三種設定下的不同用法.
數學比較多, 開始吧!

開頭先賞一頓數學操作吃粗飽一下
Let $p,q$ 都是 distributions, 則下面數學式子成立

$$KL(q(z)\|p(z|x))=-\sum_z q(z)\log\frac{p(x|z)}{q(z)} \\ =-\sum_z q(z)\left[\log\frac{p(x,z)}{q(z)}-\log p(x)\right] \\ =-\sum_z q(z)\log\frac{p(x,z)}{q(z)}+\log p(x)$$ $x$ 是代表什麼意思? $z$ 又代表什麼? 什麼都不管繼續整理:
$$\log p(x)= KL(q(z)\|p(z|x))+ {\color{orange}{ \mathbb{E}_{z\sim q}\left[\log \frac{p(x,z)}{q(z)}\right]} }\\ =KL(q(z)\|p(z|x))+{\color{orange}{ \mathbb{E}_{z\sim q}\left[\log p(x,z) - \log q(z)\right]} } \\ =KL(q(z)\|p(z|x))+\color{orange}{\mathcal{L}(q)}$$ 因為 $KL(\cdot)\geq0$ 所以 $\mathcal{L(q)}\leq\log p(x)$

基本上 $p,q$ 只要是 distribution 上面式子就成立

---

借用 MicroSoft NNI [1] 的分類, NAS 分成:
 $\circ$ Multi-trail NAS
 $\circ$ One-shot NAS (著重點)
我們著重在每個方法的介紹, 要解決什麼問題, 而實驗結果就不記錄
註: NAS 一直是很活躍的領域, 個人能力有限只能記錄自己的 study 現況