Whale's Blog

矩阵求导

矩阵变量函数的导数

定义 (Fréchet 可微) 设 $f(X)$ 为矩阵变量函数，如果存在矩阵 $G \in \mathbb{R}^{m \times n}$，

$$\underset{V \rightarrow 0}{lim} \dfrac{f(X + V) − f(X) − ⟨G,V⟩}{\|V\|} = 0$$

则称 $f$ 关于 $X$ 是 Fréchet 可微的．满足上式的 $G$ 称为 $f$ 在 $X$ 处在 Fréchet 可微意义下的梯度．

定义 (Gâteaux 可微) 设 $f(X)$ 为矩阵变量函数，如果存在矩阵 $G \in \mathbb{R}^{m \times n}$，对任意方向 $V \in \mathbb{R}^{m \times n}$ 满足

$$\underset{t \rightarrow 0}{lim} \dfrac{f(X + tV) − f(X) − t⟨G,V⟩}{t} = 0$$

则称 $f$ 关于 $X$ 是 Gâteaux 可微的．满足上式的 $G$ 称为 $f$ 在 $X$ 处在 Gâteaux 可微意义下的梯度．

若 $f$ 是 Fréchet 可微的， 则 $f$ 也是 Gâteaux 可微的，且二者意义下的梯度相等，通常情况下，由于 Gâteaux 可微定义式更容易操作，因此通常是利用 Gâteaux 梯度的定义来计算矩阵变量函数的导数(向量情况类似).

计算实例

例1. $f(X) = \text{Tr}(AX^\text{T}B)$

$$\begin{aligned} \underset{t \rightarrow 0}{lim} \dfrac{f(X+tV)-f(V)}{t} &= \underset{t \rightarrow 0}{lim} \dfrac{\text{Tr}(A(X+tV)^\text{T}B)-\text{Tr}(AX^\text{T}B)}{t} \\ &= \text{Tr}(AV^\text{T}B) = \langle BA,V\rangle \end{aligned}$$

因此，$\nabla f(X) = BA$.

Motivation

1.将数据维度降低到二维或者三维以便将其可视化.

2.去噪，如果数据中存在噪声，用更少的解释变量来表示，舍弃某些变量有时可以起到去噪的效果.

3.降低数据的多重共线性的影响，考虑下面这样一组数据，其中一列表示用户的工作，另一列表示用户的薪水。但工作和薪水这样两个变量之间可能存在高度的相关性，可能会导致模型参数估计不准确，而PCA是通过对解释变量进行线性变换形成新的一组基，并使新的基之间的相关系数为0，因此PCA可以有效的降低多重共线性的影响.

4.维度灾难，涉及到向量的计算的问题中，随着维数的增加，计算量呈指数倍增长的一种现象，在很多机器学习问题中，训练集中的每条数据经常伴随着上千、甚至上万个特征，因此降维是比较有效的一种数据预处理方法.

另一种说法的维度灾难是指，高维空间中数据的分布更加稀疏，想要对数据进行有效地分类更加困难，考虑下面这个例子：

考虑这样一个球壳，外部球体的半径为 $r_{out}=1$，内部球体的半径为 $r_{in}=1-\varepsilon$.

考虑维度 $\text{dim}=2$ 的情形，此时有 $V_{out}=\pi r_{out}^2$，$V_{in}=\pi r_{in}^2$.

考虑维度 $\text{dim}=n$ 的情形，此时的体积表达式如下：

$$\begin{cases} V_{out}=k r_{out}^n\\ V_{in}=k r_{in}^n \end{cases}$$

其中 $k$ 为一个常数，考虑

$$\begin{aligned} &\lim_{n \to +\infty} \dfrac{V_{out}-V_{in}}{V_{out}} \\ = &\lim_{n \to +\infty} \dfrac{k(1-(1-\varepsilon)^n)}{k} \\ = & 1 \end{aligned}$$

可以发现当维度很高的时候，球壳的几乎占据了整个球体，意味着无论这个 $\varepsilon$ 有多小，数据几乎都分布在这个球壳当中，而中间空着的部分分布着极少的数据，因此高维空间中数据的分布通常更加稀疏.

极大似然估计

假设数据集 $X = \{x^{(1)}, x^{(2)}, \dots, 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)]$$

今天写一下第二题我的个人解答，这道题源自 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}^m$ 过参数化, 即存在 $w^\ast$ 使得对于所有 $j$ 满足 $F(x_j;w^\ast) = y_j$.为了研究训练神经网络时 $w^\ast$ 的局部优化行为，我们考虑线性化神经网络 $\tilde{F}(x;w) = F(x;w^\ast) + (w - w^\ast)^\text{T} \nabla F(x;w^\ast)$，其损失函数为

$$\text{Loss}(w) := \frac{1}{2m} \sum_{j=1}^m (y_j - \tilde{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^*)^\text{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)$ 是有界的).(注意，这蕴含了一个依赖维度的 $|\Sigma|_F \leq \dfrac{2\sqrt{d}}{s}$，其中 $d$ 是 $w$ 的维度).

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

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

分享一下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 \to \mathbb{R}$ 和 $\mathbf{g}: \mathbb{R}^m \to \mathbb{R}^p (p \in \mathbb{N})$ 是多仿射的，即对任意 $i \in \{1, \cdots, n\}$，在固定下标在 $\{1, \cdots, N\} \setminus \{i\}$ 中的块后，它们对 $x_i$ 是仿射函数。这里，我们称一个函数 $h: \mathbb{R}^q \to \mathbb{R}^r (q, r \in \mathbb{N})$ 为仿射的，若对任意 $a \in \mathbb{R}$ 以及 $y^{(1)}, y^{(2)} \in \mathbb{R}^q$，有

$$h(a y^{(1)} + (1-a) y^{(2)}) = a h(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) 的最优解集合相同.

最近在做 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))$$