Hexo

1 about DeltaNet

https://zhuanlan.zhihu.com/p/1974403522306020939

2 about the development of Linear Attention

https://spaces.ac.cn/archives/11033

本文将深入探讨操作系统内核如何管理 CPU 资源。从调度衡量指标出发，对比抢占式与非抢占式调度，并深度剖析 FCFS、SJF、RR 以及现代 OS 广泛采用的多级反馈队列（MLFQ）算法。

1. 背景与流程回顾

在处理含有隐变量（Latent Variable）的参数估计时，我们无法直接观测到数据的来源标签。例如，我们只有一堆身高数据，却不知道哪些来自男生，哪些来自女生。

• 理论背景与实际应用：EM 算法流程介绍与实际背景 - 知乎

---

2. 问题建模：多个观测数据的情形

假设我们有 $n$ 个独立同分布的身高观测值 $X = {x_1, x_2, \dots, x_n}$。
对于每一个身高 $x_i$，都对应一个隐藏变量 $z_i \in {男, 女}$。

我们需要估计的参数为 $\theta = {\pi_k, \mu_k, \sigma_k}$（其中 $k \in {男, 女}$，$\pi_k$ 是性别比例）。观测数据的总对数似然函数为：

$$L(\theta) = \sum_{i=1}^{n} \ln p(x_i | \theta) = \sum_{i=1}^{n} \ln \sum_{z_i \in \{男, 女\}} p(x_i, z_i | \theta)$$

难点：求解每个人是男/女的概率需要知道$\theta$，但是求解$\theta$又需要知道每个样本是男还是女。这是一个鸡生蛋蛋生鸡的问题。

---

3. 核心推导：构造身高的“下界函数”

为了解决耦合，我们为每个数据点 $x_i$ 引入一个关于性别的分布 $q_i(z_i)$。$q_i(男)$ 表示第 $i$ 个同学是男生的概率。

3.1 利用 Jensen 不等式

利用 $\ln$ 函数的凹性，我们可以将对数符号“推进”求和号内部：

$$L(\theta) = \sum_{i=1}^{n} \ln \sum_{z_i} q_i(z_i) \frac{p(x_i, z_i | \theta)}{q_i(z_i)} \ge \sum_{i=1}^{n} \sum_{z_i} q_i(z_i) \ln \frac{p(x_i, z_i | \theta)}{q_i(z_i)}$$

我们将右侧这项记为 ELBO (Evidence Lower Bound)。

---

4. E-step：寻找最紧的下界（确定性别的“软权重”）

4.1 取最紧下界的条件？

在 E-step 中，我们要固定当前猜测的男女生身高参数 $\theta^{(t)}$，调整 $q_i(z_i)$ 使下界达到最大。
根据 Jensen 不等式，等号成立（即下界触碰到原函数）的条件是：

$$\frac{p(x_i, z_i | \theta^{(t)})}{q_i(z_i)} = C \quad (\text{对每个 } z_i \text{ 均为常数})$$

由于 $\sum_{z_i} q_i(z_i) = 1$，我们可以推导出：

$$q_i(z_i) = \frac{p(x_i, z_i | \theta^{(t)})}{\sum_{z_i} p(x_i, z_i | \theta^{(t)})} = p(z_i | x_i, \theta^{(t)})$$

4.2 直观意义与例子

• 直观意义：$q_i(z_i)$ 就是在已知当前参数下，观察到身高 $x_i$ 后，该生属于性别 $z_i$ 的后验概率（又称响应度）。
• 身高例子：如果你当前认为男生平均 175cm，女生平均 163cm。对于一个 $x_i = 170\text{cm}$ 的同学，E-step 算出的结果可能是：$q_i(男) = 0.7$，$q_i(女) = 0.3$。
• 为什么要最大化？：只有当我们使用的分布 $q_i$ 恰好等于真实后验概率时，我们构造的下界才在 $\theta^{(t)}$ 处与原似然函数完全重合。任何其它的分配方式都会导致下界“偏低”，无法提供最精确的爬升起点。

---

5. M-step：利用权重更新参数（加权极大似然）

固定刚才算出的“性别概率” $q_i^{(t+1)}$，我们更新 $\theta$：

$$\theta^{(t+1)} = \arg \max_{\theta} \sum_{i=1}^{n} \sum_{z_i} q_i^{(t+1)}(z_i) \ln p(x_i, z_i | \theta)$$

该式是可以直接求解出来的（该式与原ELBO差了一个常数项，直接舍掉）

5.1 身高模型中的计算

以更新男生平均身高 $\mu_{男}$ 为例，对上式求导令其为 0，你会得到：

$$\mu_{男}^{(t+1)} = \frac{\sum_{i=1}^{n} q_i(男) \cdot x_i}{\sum_{i=1}^{n} q_i(男)}$$

物理含义：这不再是简单的平均值，而是加权平均。每个人的身高 $x_i$ 根据他是男生的可能性 $q_i(男)$ 为贡献权重，重新计算出男生的均值。

---

6. 总结：收敛性证明的逻辑闭环

为什么这样做一定会收敛？

1. E-step 确保了在 $\theta^{(t)}$ 点，下界函数的值等于真实对数似然值：$L(\theta^{(t)}) = ELBO(q^{(t+1)}, \theta^{(t)})$。
2. M-step 在这个下界函数上寻找最大值，得到新的 $\theta^{(t+1)}$，因此：$ELBO(q^{(t+1)}, \theta^{(t+1)}) \ge ELBO(q^{(t+1)}, \theta^{(t)})$。
3. Jensen 不等式 保证了在任何点，原函数都大于等于下界：$L(\theta^{(t+1)}) \ge ELBO(q^{(t+1)}, \theta^{(t+1)})$。

最终链条：

$$L(\theta^{(t+1)}) \ge ELBO(q^{(t+1)}, \theta^{(t+1)}) \ge ELBO(q^{(t+1)}, \theta^{(t)}) = L(\theta^{(t)})$$

这就证明了：只要我们不断重复这两步，观测数据的对数似然 $L(\theta)$ 就会像爬楼梯一样单调不减，直到收敛到局部极大值。

脑海中只需要记住这样的模型

一个下方的函数曲线在向上方的函数曲线的极值点逼近（可以找一些EM算法介绍的博客看看）

---

7. VAE与EM（重要）

变分自编码器（VAE）与期望极大算法（EM）在统计机器学习中有着极其深刻的血缘关系。从本质上讲，VAE 可以被视作一种“深度化、参数化且随机化”的变分 EM 算法。

为了理清两者的关系，我们需要从潜变量模型的对数似然分解出发，逐步推导。

---

1. 核心基础：证据下界（ELBO）的推导

假设我们有观测数据 $x$ 和潜变量 $z$。我们的目标是最大化对数似然 $\log p_\theta(x)$。

根据全概率公式：

$$\log p_\theta(x) = \log \int p_\theta(x, z) dz$$

引入一个关于 $z$ 的任意分布 $q(z)$，根据 Jensen 不等式或 KL 散度的性质，我们可以得到：

$$\begin{aligned} \log p_\theta(x) &= \log \int q(z) \frac{p_\theta(x, z)}{q(z)} dz \\ &\ge \int q(z) \log \frac{p_\theta(x, z)}{q(z)} dz \quad (\text{根据 Jensen 不等式}) \end{aligned}$$

这个下界被称为 ELBO (Evidence Lower Bound)。为了更细致地观察，我们进行如下恒等变形：

$$\log p_\theta(x) = \underbrace{\mathbb{E}_{q(z)} [\log \frac{p_\theta(x, z)}{q(z)}]}_{ELBO(q, \theta)} + \underbrace{KL(q(z) || p_\theta(z|x))}_{\text{KL散度 } \ge 0}$$

结论 1：最大化 $\log p\theta(x)$ 等价于最大化 $ELBO$，同时最小化 $q(z)$ 与真实后验 $p\theta(z|x)$ 之间的 KL 散度。

---

2. EM 算法：坐标上升法

EM 算法解决的是：当 $p_\theta(z|x)$ 比较简单（有解析解）时，如何迭代优化 $\theta$。

EM 算法在 $ELBO(q, \theta)$ 上执行坐标上升：

• E-Step（期望步）：
  固定参数 $\theta{old}$，寻找最优的 $q(z)$ 来收紧下界。
  为了使 $ELBO$ 最大，由于 $\log p\theta(x)$ 是常数，必须令 $KL(q(z) || p_\theta(z|x)) = 0$。
  因此，E-step 的最优解是：

  $$q^{new}(z) = p_{\theta_{old}}(z|x)$$

  （即：直接使用当前的后验分布作为 $q$）

• M-Step（极大步）：
  固定 $q^{new}(z)$，寻找最优的 $\theta$ 来提升下界：

  $$\theta_{new} = \arg\max_\theta \int q^{new}(z) \log p_\theta(x, z) dz$$

  这通常通过对 $\theta$ 求导并令其为 0 来实现。

---

3. 从 EM 到 VAE 的演进

在深度学习场景下，传统的 EM 算法遇到了两个瓶颈：

1. 后验不可积：对于复杂的生成模型（如神经网络定义的 $p\theta(x|z)$），真实后验 $p\theta(z|x)$ 通常是无法解析计算的（Intractable），导致 E-step 无法执行。
   • 为什么说$p\theta(z|x)$是后验分布？因为在我们的场景中，z是原因（先验过程：首先从某种简单的分布中抽取一个隐变量 $z$），x是结果（似然过程：然后通过一个复杂的映射（由解码器神经网络参数化）产生观测到的数据 $x$），根据概率论定义，后验描述的是“在看到结果 $x$ 之后，推测其产生原因 $z$ 的概率分布”。“真实”的意思是数学上可以通过$p\theta(x|z)$表示出来，但是可能求不出来（因为$p_\theta(x|z)$在VAE中是神经网络，但EM中则可以直接求出来）
   • $p\theta(x|z)$是人为定义的，导致$p\theta(x|z)$也是人决定的；另外$p_\theta(z)$定义为高斯分布
2. 大数据量：EM 算法通常需要遍历整个数据集来更新一次 $\theta$，无法利用随机梯度下降（SGD）。

VAE 的改进方案：

A. 摊销推断 (Amortized Inference)
VAE 不再为每一个样本 $xi$ 单独优化一个 $q_i(z)$（如 EM 所做的），而是引入一个由参数 $\phi$ 化的神经网络——**生成器/编码器 $q\phi(z|x)$**。这个网络学习一个映射，输入 $x$ 直接输出 $z$ 的分布参数。

B. 联合优化
VAE 不再分步交替优化 $q$ 和 $\theta$，而是将两者放在同一个目标函数 $ELBO$ 下，使用 SGD 同时优化。

---

4. VAE 的公式细化

在 VAE 中，我们将 $ELBO$ 重新展开为易于神经网络处理的形式：

$$ELBO(\theta, \phi; x) = \mathbb{E}_{q_\phi(z|x)} [\log p_\theta(x, z) - \log q_\phi(z|x)]$$

利用贝叶斯公式 $p\theta(x, z) = p\theta(x|z)p(z)$，进一步分解：

$$\begin{aligned} ELBO(\theta, \phi; x) &= \mathbb{E}_{q_\phi(z|x)} [\log p_\theta(x|z) + \log p(z) - \log q_\phi(z|x)] \\ &= \underbrace{\mathbb{E}_{q_\phi(z|x)} [\log p_\theta(x|z)]}_{\text{重构项 (Reconstruction)}} - \underbrace{KL(q_\phi(z|x) || p(z))}_{\text{正则化项 (Regularization)}} \end{aligned}$$

• 重构项：对应 Autoencoder 的解码器部分，希望从 $z$ 恢复出 $x$。
• 正则化项：对应变分推断，希望变分后验 $q_\phi$ 不要偏离先验 $p(z)$（通常是标准正态分布）太远。

---

5. 总结：VAE 与 EM 的深度对比

总结性视角：

• EM 可以看作是 VAE 的特例。在 EM 的 E-step 中，我们相当于拥有一个无限表达能力的编码器，能够完美匹配真实后验，使 KL 散度降为 0。
• VAE 则是 EM 的现代工程实现。由于我们无法获得完美后验，我们用一个神经网络（Encoder）去“猜测”这个 E-step 的结果，并允许这个猜测存在误差（即 KL 散度不为 0），最后通过梯度下降在大规模数据上学习。

一句话总结：VAE 是利用神经网络来近似实现 EM 算法中 E-step 的变分推断过程，并将其转化为端到端的梯度优化问题。

---

6. 疑问：我注意到EM算法中引入的隐变量是q(z)，而VAE中的是q(z|x)。我的这个观察正确吗？为什么会有这样的区别？

你的观察非常敏锐且完全正确。这看似只是一个条件符号 的差别，实则揭示了从传统统计机器学习到深度学习推断范式的重大演进。

我们可以从以下三个维度来理解这个区别：

1. 核心差异：数据塑性 vs 瞬时推断

• EM 算法中的 $ q_{\phi}(z) $（独立推断 Individual Inference）
  在 EM 中，我们为每一个观测数据点，都分配了一个专属的推断函数 $ q{\phi}(z) $。如果有 1000 个观测数据，你就要维护 1000 个不同的 $ q{\phi}(z) $ 分布。
  • 特点：每个数据点的推断是独立优化的。当你看到一个新数据时，你必须重新运行一次 EM 的 E-step 去适配它 $ z $。
• VAE 中的 $ q_{\phi}(z \vert x) $（摊销推断 Amortized Inference）
  VAE 不再为每个单点估计 $ q_{\phi}(z) $，而是学习一个带 $ x $ 输入的推断神经网络（参数化这个函数）。这个函数输入任何 $ x $，都能输出对应的 $ z $ 分布参数（比如均值 $ \mu $ 和方差 $ \sigma^2 $）。
  • 特点：我们把“推断能力”编码到了神经网络的权重 $ \phi $ 中。不管有多少数据，我们只需要存一套神经网络参数。

2. 用“身高例子”直观解释

• EM 算法的逻辑（旧世界）：你手里有一张表格，记录了班里 50 个同学。每 Estep 时，你对着张三的身高算一次他是男生的概率，再在张三名下；对李四的身高算一次，写在李四名下。
  • 公式表达：$ q{\phi}(z) $，这里的 $ z $ 是数据点专属的，所以写成 $ q{\phi}(z) $。这就是为什么会写成 $ q_{\phi}(z) $。
• VAE 的逻辑（公式版）：你开发了一个“性别预测器”手机 App。你不需要为每个同学记账，只需要把任何人的身高 $ x $ 输入 App，它就会根据内部的逻辑（参数 $ \phi $）告诉你结果。
  • 公式表达：$ q_{\phi}(z \vert x) $，这里的 $ x $ 强调了 $ z $ 的分布是以 $ x $ 为输入计算出来的。

3. 为什么会有这样的区别？

这种转变主要是为了应对大数据和泛化能力：

4. 数学上的深层联系

其实，VAE 里的 $ q_{\phi}(z \vert x) $ 也可以看作是一个极其复杂的条件分布，只是它没有用函数表达，而是用参数化的方式学到的。

在 VAE 的损失函数推导中：

$$\mathcal{L} = \mathbb{E}_{q_{\phi}(z \vert x)} \left[ \log p_{\theta}(x \vert z) \right] - D_{\text{KL}} \left( q_{\phi}(z \vert x) \parallel p(z) \right)$$

这里的 $ q_{\phi}(z \vert x) $ 承担了 EM 中 E-step 的全部功能，但它通过“梯度下降”同时优化所有数据的推断精度，而不是像 EM 那样逐个数据点“点对点”对齐。

5. 从数学公式本身看 (重要)

二者在数学公式本身上的区别其实就是引入的常数变易的方法不同

1. EM 算法中的公式

在标准 EM 中，对于每一个观测样本 $x_i$，我们都会引入一个与之对应的独立分布 $q_i(z)$。

对数似然分解式：

$$\log p_\theta(x_i) = \mathbb{E}_{q_i(z)} \left[ \log \frac{p_\theta(x_i, z)}{q_i(z)} \right] + KL(q_i(z) \parallel p_\theta(z|x_i))$$

• $q_i(z)$ 的含义：它是一组局部参数（Local Parameters）。对于数据集中的 $N$ 个样本，理论上有 $N$ 个不同的 $q$ 分布。
• 优化方式：在 E-Step，我们针对每一个样本 $x_i$ 单独求解最优的 $q_i$： $$q_i^*(z) = \arg\max_{q_i} ELBO(q_i, \theta) = p_\theta(z|x_i)$$ 这意味着 EM 需要为每个数据点存储或计算一个特定的分布。

2. VAE 中的公式

VAE 不再为每个样本维护一个 $qi(z)$，而是引入一个由全局参数 $\phi$ 控制的函数（神经网络） $q\phi(z|x)$。

对数似然分解式：

$$\log p_\theta(x_i) = \mathbb{E}_{q_\phi(z|x_i)} \left[ \log \frac{p_\theta(x_i, z)}{q_\phi(z|x_i)} \right] + KL(q_\phi(z|x_i) \parallel p_\theta(z|x_i))$$

• $q_\phi(z|x_i)$ 的含义：它是一个全局函数（Global Function）。不管 $x_i$ 是哪一个，都由同一个参数为 $\phi$ 的神经网络（Encoder）来预测 $z$ 的分布。
• 优化方式：我们不再针对单个样本求 $q_i$，而是针对全体样本优化同一个 $\phi$： $$\phi^* = \arg\max_\phi \sum_{i=1}^N ELBO(\phi, \theta; x_i)$$

3. 数学公式上的核心区别总结

一句话总结数学上的区别：
EM 算法是在 $N$ 个独立的分布空间里分别寻找 $N$ 个最优的 $qi$ 点；而 VAE 是在寻找一个最优的函数映射 $q\phi$，使得对于任何输入的 $x$，该函数都能输出一个足够好的 $q$。

6. 如果EM算法引入的是q(z|x)，是不是好像也说得通？

不知道。但Gemini说是，“你说得非常对！实际上，在很多高级机器学习教材（如 PRML 或变分推断相关的论文）中，EM 算法的 q(x) 分布确实也被写成 q(z∣x)”

总结

• EM 的 $ q_{\phi}(z) $：像“个性医生”，每个病人（数据）做一份。
• VAE 的 $ q_{\phi}(z \vert x) $：像“诊断程序”，只要输入（病人 $ x $），就能给出诊断（输出 $ z $）。

既然已经发现了这个「个性→程序」的规律，想了解一下 VAE 是如何通过“重参数化技巧”让这个带有 $ z $ 随机性的目标函数变得可导的？（可在后续探讨）

已按要求将数学公式用 $$或$$$ 包裹，确保公式格式符合纯 LaTeX 语法（使用 \vert 表示条件概率竖线 ），同时保持内容逻辑完整 。

本文详细拆解朴素贝叶斯算法的核心原理，通过文本分类案例手推计算过程，并深度解析拉普拉斯平滑如何解决“零概率”陷阱。