Whale's Blog

极大似然估计

假设数据集 $X = \{x^{(1)},x^{(2)} \ldots, x^{(m)}\}$，每个样本独立同分布地由未知的真实数据生成分布 $p_{\text{data}}(x)$ 生成.

设 $p_{\text{model}}(x; \theta)$ 是一个用来估计真实概率 $p_{\text{data}}(x)$ 的映射。

对参数 $\theta$ 的最大似然估计定义如下

$$\begin{aligned} \hat{\theta} &= \arg \max_{\theta} p_{\text{model}}(X; \theta) \\\\ &= \arg \max_{\theta} \prod_{i=1}^{m} p_{\text{model}}(x^{(i)}; \theta) \end{aligned}$$

由于乘积可能会导致数值溢出等问题，不便于计算。为了得到一个便于计算的等价优化问题，通过取对数转化成便于计算的求和形式：

$$\hat{\theta} = \arg \max_{\theta} \sum_{i=1}^{m} \log p_{\text{model}}(x^{(i)}; \theta)$$

假设每个数据等概率地从数据集 $X$ 中抽样得到， 除以 $m$ 得到训练数据经验分布 $\hat{p}_{\text{data}}$ 的期望形式：

$$\hat{\theta} = \arg \max_{\theta} \mathbb{E}_{x \sim \hat{p}_{\text{data}}} [\log p_{\text{model}}(x; \theta)]$$

另一种视角下的最大似然估计是将它看作最小化训练集上的经验分布 $\hat{p}_{\text{data}}$ 和模型分布 $p_{\text{model}}$ 之间的差异，两个概率分布之间的差异程度可以通过 KL 散度度量：

$$D_{\text{KL}}(\hat{p}_{\text{data}} \parallel p_{\text{model}}) = \mathbb{E}_{x \sim \hat{p}_{\text{data}}} [\log \hat{p}_{\text{data}}(x) - \log p_{\text{model}}(x)]$$

左边一项仅涉及到训练集上的数据抽样过程，和模型无关，故上式等价于最小化

$$\mathbb{E}_{x \sim \hat{p}_{\text{data}}} [\log p_{\text{model}}(x)].$$

显然这和极大似然估计得到的结果是相同的，同时从该式也可以看出最小化 KL 散度与最小化交叉熵等价。

实例

均方误差 $MSE$ 等价于经验分布和高斯模型之间的交叉熵，考虑下面这样一个线性回归模型：

将线性回归作为学习从输入 $x$ 映射到输出 $y$ 的算法，以最大似然估计的视角来看线性回归，现在希望我们的模型能够拟合得到条件概率分布 $p(y | x)$ ，而不是得到一个单独的预测 $\hat{y}$，定义 $p(y | x) = \mathcal{N}(y; \hat{y}(x), \sigma^2)$，即函数 $\hat{y}(x; w)$ 预测高斯的均值，方差是常量。假设样本是独立同分布的，条件对数似然如下：

$$\begin{aligned} &\sum_{i=1}^{m} \log p(y^{(i)} | x^{(i)}; \theta) \\\\ = &-m \log \sigma - \frac{m}{2} \log (2\pi) - \frac{m}{2} \sum_{i=1}^{m} \frac{|y^{(i)} - \hat{y}(x^{(i)})|^2}{2\sigma^2} \end{aligned}$$

其中 $\hat{y}^{(i)}$ 是线性回归在第 $i$ 个输入 $x^{(i)}$ 上的输出，$m$ 是训练样本的数目。对比 $MSE$ 和对数似然，

$$\text{MSE} = \frac{1}{m} \sum_{i=1}^{m} |\hat{y}^{(i)} - y^{(i)}|^2$$

可以看出最大化关于 $w$ 的对数似然和最小化均方误差会得到相同的参数估计 $w$.

总结

理想情况下，我们希望用经验分布 $\hat{p}_{\text{data}}$ 匹配真实的数据生成分布 $p_{\text{data}}$，但由于我们没法直接知道这个分布，因此使用极大似然估计的思想，用经验分布 $\hat{p}_{\text{data}}$ 去匹配模型分布 $p_{\text{model}}$.

今天分享2024年阿里巴巴数学竞赛决赛（应用与计算赛道）第 4 题的个人解答.

T4. 考虑如下两个优化问题：

$$\begin{aligned} \text{(A)} \quad &\mathop{\min}\limits_{x} f(x),\\\\ &\text{s.t.} \quad \mathbf{g}(x) = 0,\\\\ &x_i \in \mathcal{F}_i, i = 1, \cdots, n \end{aligned}$$

和

$$\begin{aligned} \text{(B)} \quad & \mathop{\min}\limits_{x} f(x) + \beta {g}(x)^\top \mathbf{1}_p,\\\\ &x_i \in \mathcal{F}_i, i = 1, \cdots, n \end{aligned}$$

其中 $ x := [x_1^T, \cdots, x_n^T]^T \in \mathbb{R}^m (m, n \in \mathbb{N}) $，且对于 $ i = 1, \cdots, n $，$ x_i \in \mathbb{R}^{m_i} (m_i \in \mathbb{N}) $，满足 $\sum_{i=1}^n m_i = m$. 函数 $ f : \mathbb{R}^m \rightarrow \mathbb{R} $ 和 $ \mathbf{g} : \mathbb{R}^m \rightarrow \mathbb{R}^p (p \in \mathbb{N}) $ 是多仿射的，即对任意 $ i \in \{1, \cdots, n\} $，在固定下标在 $\{1, \cdots, N\} \setminus \{i\} $ 中的块后，它们对 $ x_i $ 是仿射函数。这里，我们称一个函数 $ h : \mathbb{R}^q \rightarrow \mathbb{R}^r (q, r \in \mathbb{N}) $ 是仿射的，若对任意 $ a \in \mathbb{R} $ 以及 $ y^{(1)}, y^{(2)} \in \mathbb{R}^q $，有

$$h(ay^{(1)} + (1 - a)y^{(2)}) = ah(y^{(1)}) + (1 - a)h(y^{(2)}).$$

对任意 $ i \in \{1, \cdots, n\} $，集合 $ \mathcal{F}_i \subseteq \mathbb{R}^{m_i} $ 是一个有界多面体。函数 $ \mathbf{g} $ 在 $ \times_{i=1}^n \mathcal{F}_i $ 上非负，其中 “$\times$” 表示集合的笛卡尔积. 此外，在问题 (B) 中，标量 $ \beta $ 是一个实数，$\mathbf{1}_p $ 代表 $ p $ 维全一向量.

请证明如下三个结论：

(1) 对任意 $ \beta \in \mathbb{R} $，问题 (B) 至少有一个最优解是可行的极点（即极点最优解）.

(2) 存在 $ \bar{\beta} \in \mathbb{R} $，使得对任意 $ \beta \geq \bar{\beta} $，问题 (B) 的极点最优解都是问题 (A) 的最优解.

(3) 存在 $ \tilde{\beta} \in \mathbb{R} $，使得对任意 $ \beta \geq \tilde{\beta} $，问题 (A) 和 (B) 的最优解集合相同.

今天写一下第二题我的个人解答，这道题源自NIPS2022的一篇论文《The alignment property of SGD noise and how it helps select flat minima: A stability analysis》，问题的背景是与梯度下降(GD)相比，随机梯度下降(SGD)在过参数化的神经网络训练过程当中可以收敛到一个更加平缓(flat)的极值点，而且平缓程度与神经网络的参数量无关。

T2. 假设 $ F(x; w) $ 是一个输出标量的深度神经网络，其中 $ x $ 是输入，$ w $ 表示权重。假设 $ F $ 关于 $ w $ 连续可微，并且对于训练数据 $\{ x_j, y_j \}_{j=1}^n $ 过参数化，即存在 $ w^\ast $ 使得对所有 $ j $ 满足 $ F(x_j; w^\ast) = y_j $。为了研究训练神经网络时 $ w^* $ 的局部优化行为，我们考虑线性化神经网络 $ \widetilde{F}(x; w) = F(x; w^\ast) + (w - w^\ast)^T \nabla F(x; w^\ast) $，其损失函数为

$$\text{Loss}(w) := \frac{1}{2m} \sum_{j=1}^m (y_j - \widetilde{F}(x_j; w))^2$$

令 $ s $ 表示学习率，梯度下降法为

$$w_{i+1} = w_i - s \nabla \text{Loss}(w_i)$$

而随机梯度下降法为

$$w_{i+1} = w_i - s (\nabla \text{Loss}(w_i) + \epsilon_i)$$

其中噪声项满足 $ \mathbb{E} \epsilon_i = 0 $ 和 $ \mathbb{E} \epsilon_i \epsilon_i^\top = M(w_i)/b $，$ b $ 是 mini-batch 的大小。假设协方差矩阵 $ \Sigma $ 为

$$\Sigma = \frac{1}{m} \sum_{j=1}^m \nabla F(x_j; w^\ast) \nabla F(x_j; w^\ast)^T$$

在以下意义上对齐：

$$\frac{\text{Tr}(M(w) \Sigma)}{2 \text{Loss}(w) \| \Sigma \|_F^2} \geq \delta$$

对于 $ s > 0 $ 和所有 $ w $ 成立。这里 $| \cdot |_F$ 表示 Frobenius 范数。

(1) 对于梯度下降，证明如果 $ \Sigma $ 的谱范数满足

$$\| \Sigma \|_2 \leq \frac{2}{s}$$

则梯度下降是局部稳定的(即对于所有 $ i $，$\text{Loss}(w_i)$ 是有界的)。(注意，这蕴含了一个依赖维度的 $\Vert \Sigma \Vert_F \leq \frac{2\sqrt{d}}{s} $，其中 $ d $ 是 $w$ 的维度)。

(2) 对于随机梯度下降，如果 $\mathbb{E}\text{Loss}(w_i)$ 对于所有 $ i $ 都有界，则以下独立于维度的不等式必须成立

$$\| \Sigma \|_F \leq \frac{\sqrt{b \delta}}{s}$$

后续补上…

最近在做 Mirror Descent 相关的一个项目的收敛性分析，需要用到 Pinsker 不等式，这里简单记录一下它的证明，文中的 $log$ 均是以 $e$ 为底的。

Pinsker 不等式证明

(Pinsker’s inequality)设 $P$ 和 $Q$ 是定义在论域 $U$ 上的两个概率分布，那么

$$D_{KL}(P||Q) \ge \frac{1}{2}||P-Q||_1^2 \tag{1}$$

由 Pinsker 不等式可以得到负熵函数关于$1$-范数是强凸的，下面先给出 Pinsker 不等式的证明。

$Proof.$
首先我们给出 KL 散度的链式法则：

$$\begin{aligned} D_{KL}(P(X, Y)||Q(X, Y)) &= \sum_{x,y} p(x, y) \log \frac{p(x, y)}{q(x, y)} \\\\ &= \sum_{x,y} p(x)p(y|x) \log \frac{p(x)p(y|x)}{q(x)q(y|x)} \\\\ &= \sum_{x} p(x) \log \frac{p(x)}{q(x)} \sum_{y} p(y|x) + \sum_{x} p(x) \sum_{y} p(y|x) \log \frac{p(y|x)}{q(y|x)} \\\\ &= D_{KL}(P(X)||Q(X)) + \sum_{x} p(x) D_{KL}(P||Q|X=x) \\\\ &= D_{KL}(P(X)||Q(X)) + \mathbb{E}_{X \thicksim P(X)}[D_{\text{KL}}(P(Y|X) \| Q(Y|X))] \end{aligned} \tag{2}$$

特别地，若$P(X,Y)=P_1(X)P_2(Y),Q(X,Y)=Q_1(X)Q_2(Y)$，那么有

$$D_{KL}(P(X, Y)||Q(X, Y)) = D_{KL}(P_1(X)||Q_1(X)) + D_{KL}(P_2(X)||Q_2(X))$$