本文與 Claude AI 共同編輯

Receptive field (感受野, 以下簡稱 RF) 大概是 CNN 教科書裡最早出現、也最容易被當成「知道就好」的概念之一: 某一個輸出元素, 是由多少個輸入元素決定的?
但如果你試過把一個離線訓練好的模型搬到邊緣裝置上做串流推論, 就會發現 RF 從「知道就好」的常識, 變成整個轉換流程的地基, 它直接決定每個 node 要留多大的 buffer、以及整條 pipeline 會有多少 latency.
這篇筆記想把 RF 的計算講清楚, 並且對照兩種看起來方向完全相反、實際上等價的算法: 一種是正向地把三元組 $[S, a, b]$ 一層一層往下帶, 另一種是 Distill 那篇 Computing Receptive Fields of Convolutional Neural Networks 的反向遞迴.

近期回頭讀 GPTQ (針對 LLM 的 PTQ) 論文, 同時想認真理解其背後數學精隨, 才發現以前理解的太淺薄了.
當我理解 Schur 互補 (Complement) 和 Cholesky 分解之間的關聯裡, 突然有種直擊核心的感覺, 因此決定做比較詳細的數學筆記.
最後會用一個簡單的情境來說明 GPTQ 怎麼應用 Cholesky 分解.

不打算長篇大論, 精簡聊一下 SpinQuant 這篇論文, 來杯咖啡 ☕ 開始吧.

從前面一篇 blog “隨機旋轉的量化魔法: 去去極值走” 我們知道隨機旋轉可以把 outlier 去除, 或甚至旋轉矩陣直接針對 loss 用學的 (本篇 SpinQuant 的作法, 使用 Cayley SGD 去學)
針對一個簡單的線性層 $Y=XW$ (這裡使用右乘), 我們使用一個正交矩陣 $R$ 同時對 input activation $X$ 和 weight $W$ 旋轉, 讓他們同時好量化:
$$\begin{align} Y &=XW=(XR)(R^TW) \\ &\approx Q(XR)Q(R^TW) \end{align}$$ 其中 $Q(\cdot)$ 表示量化 op. 對照參考下圖應該不難理解

那麼接著來看看 SpinQuant 全架構的旋轉量化圖

Motivation

矩陣相乘 $y=Wx$ 是神經網路的基本單元, 其中 $W\in\mathbb{R}^{m\times n}$, $x\in\mathbb{R}^{n\times1}$, $y\in\mathbb{R}^{m\times 1}$.
試想一下如果 $W$ 裡面的值存在 outliers, 則對整個 matrix 量化時, 為了能覆蓋 outlier 則會犧牲精度, 這正是現今 LLM 極致量化時的魔王關卡.
考慮旋轉矩陣 $U\in\mathbb{R}^{m\times m}$, $V\in\mathbb{R}^{n\times n}$, 如果先對 $W$ 和 $x$ 作如下座標旋轉操作:
$$\begin{align} \tilde{W}\leftarrow UWV^T \\ \tilde{x}\leftarrow Vx \end{align}$$ 則我們觀察一下 $\tilde{W}\tilde{x}$ 與原來的 $Wx$ 差異在哪
$$\begin{align} \tilde{W}\tilde{x} &= (UWV^T)(Vx) =UWx \end{align}$$ 所以如果再多乘上 $U^T$ 旋轉一下, 則就能還原出原本的 output activation $y=Wx$ 了.
那為什麼要套這些旋轉矩陣? 反正最後又要還原回去, 不是多此一舉嗎?
其實不是白做, 旋轉有很大的好處
這是因為透過旋轉矩陣, 我們能夠把 outlier 消除, 進而能夠很好的量化

$\tilde{W}$ 比 $W$, $\tilde{x}$ 比 $x$ 好量化很多! 👍🏻

⚠️ 這部份屬於我的知識盲區, 如有不嚴謹/錯誤之處還請見諒/指正
又再一次體會到數學的美
正交矩陣 $X\in\mathbb{R}^{n\times p}$ 形成的集合稱為 Stiefel manifold
$$\begin{align} \mathcal{M}=\{X\in\mathbb{R}^{n\times p}:X^TX=I\} \end{align}$$ 以下用方陣方便解釋, i.e. $X\in\mathbb{R}^{n\times n}$.
讓我們發揮點想像力, 把 Stiefel manifold 想像成在 $n^2$ 維度歐式空間中的一個集合形成的 “流形”.
閱讀本文你將了解到:

1. 正交矩陣的幾何結構: 了解 Stiefel Manifold 的定義, 以及為什麼我們將正交矩陣視為高維空間中一塊「彎曲」的流形
2. 瞬時旋轉的本質: 透過泰勒展開式推導出切空間 (Tangent Space) 的約束條件, 並揭示為什麼 反對稱矩陣 (Skew-symmetric matrix) 本質上就是單位矩陣 $I$ 處的「瞬時旋轉方向」
3. Cayley 轉換的橋樑作用: 掌握如何利用 Cayley Transform 在反對稱矩陣與正交矩陣之間進行無損轉換, 並理解其作為「微小步長旋轉」的物理意義
4. Cayley SGD 的運作邏輯: 學習如何將普通的歐幾里得梯度投影至流形切空間, 並透過迭代式更新 (Iterative Update) 在不計算矩陣 inverse 的情況下, 維持矩陣的正交性

向量的 norm 我們很熟悉了, 但對於一個矩陣的 norm 又該怎麼定義呢?
最直覺的想法就是把矩陣 flatten 成一個向量, 套用向量的 norm 即可. 這引導出了 Frobenius norm.
但是矩陣還包含了將向量做線性轉換的作用, 所以向量經過矩陣轉換後的 norm 變化是不是可以用來當作矩陣 norm 的度量方式呢? 這樣的想法引導出了 operator norm 或 spectral norm.
先給出 take away 總結:

• Frobenius norm: 開根號的 “singular value 平方和”

  $$\begin{aligned} \|A\|_F := \sqrt{\sum_{i,j}|a_{ij}|^2} =\mathrm{Tr}(A^HA)=\sqrt{\sum_i^{\min\{m,n\}}\sigma_i^2(A)} \end{aligned}$$

• Spectral norm: 最大的 singular value

  $$\begin{aligned} \|A\|_2 :=\sup_{\|x\|_2\leq1}\{\|Ax\|_2\}=\sqrt{\lambda_{\max}(A^HA)}=\sigma_{\max}(A) \end{aligned}$$

💡 為什麼 spectral norm 這麼定義?
推薦閱讀周老師的文章, 矩陣範數, 非常具有啟發性！更多延伸：譜半徑與矩陣範數

• 兩者的關係: $$\begin{aligned} \|A\|_2 \leq \|A\|_F \end{aligned}$$

接著詳細記錄定義和推導證明 (參考自黃子嘉線性代數講義)

這是初探最優傳輸 OT (Optimal Transport) 的第三篇, 聊一下應用和 toy example
OT 在 Machine learning 已有許多重要的應用, 例如大名鼎鼎的 “WGAN“ 就使用 EMD (Earth Mover’s Distance) 當 loss 來衡量 generator 產生的分布與目標資料分布兩者間的距離 (JSD 會有 support sets 無交集時的問題, 參考 “WGAN Part 2: 主角 W 登場“ 一文的說明)
還有 flow matching 裡針對一個 batch 可用 OT 找出訓練 conditional probability path 的配對, 這使得訓練更穩定. [筆記連結]
當然在 CV 領域, 已有許多成功的應用, 包含 point cloud mapping, graph 同構/對應, 等等.

更多範例可參考 POT 庫的 Examples gallery 頁面

不過文章前半段想先用另一個例子來說明 OT 的應用: 有關 doubly stochastic matrix (雙隨機矩陣)
再來簡單解釋一下, 求解 EOT 問題用的 Sinkhorn 迭代算法該怎麼微分. 如果是可微的 loss, 那就能結合到神經網路訓練中, 自然就打開了許多應用的可能.
最後本文會用一個 toy example 展示如何使用 EOT 當 loss, 讓 NN 模型學習從一個初始分布對應到目標分布.

這是初探最優傳輸 OT (Optimal Transport) 的第二篇, 聊一下背後的數學理論
接續上一篇引導出 EMD 是什麼以及什麼情況下我們需要 EMD 而非 KL or JSD 距離後, 我們最後說到 EMD 的兩個缺點: 不夠有效率以及無法微分

本篇我們介紹 EOT (Entorpic Optimal Transport)
EOT 將 EMD 問題 relax 後, 雖然只能找到逼近解, 但卻能利用一個更有效率且可微分的 Sinkhorn 演算法來求解.
我們將著重在數學理論部分, 從而理解 EOT 及 Sinkhorn 演算法的本質內涵.
最後再介紹一個重要的變形, Partial OT, 可以不用所有的 “土堆” 都要搬運, 只匹配部分.
[備註]：在離散情況下 Earth Mover’s Distance (EMD) / Optimal Transport / Wasserstein distance 指同一件事情, 文章在不混淆情況下有時會混用

這是初探最優傳輸 OT (Optimal Transport) 的第一篇, 聊一下這是什麼問題以及傳統利用 Linear Programming 的解法

[備註 1]：圖片改自此 jupyter notebook: wasserstein-notebook/Wasserstein_Kantorovich.ipynb
[備註 2]：在離散情況下 Earth Mover’s Distance (EMD) / Optimal Transport / Wasserstein distance 指同一件事情, 文章在不混淆情況下有時會混用

什麼是 Earth Mover’s Distance (EMD) 推土機距離?

Earth Mover’s Distance (EMD) 有一個很形象的描述叫做推土機距離.
想像兩個機率分布 ($P_s$, $P_t$) 是形狀不同的兩個土堆. 將源分布 $P_s$ 改造成目標分布 $P_t$ 所需的最小搬運代價即為 EMD.

DPO 捨棄 RLHF 中笨重的 reward model, 並將 RL 問題直接轉換成對好壞兩個 responses 的 supervised training. [圖片產生自 ChatGPT]

Pre-trained model 經過 SFT (Supervised Fine-Tuning) 再經過 RLHF (Reinforcement Learning from Human Feedback) 的這一套組合拳在 2023 年堪稱顯學
網路上甚至產生了一個很有名的修格斯(Shoggoth)怪物梗圖. (wiki: 形態無定的原生質生物，是克蘇魯神話中最駭人的存在之一)