DLSYS2 机器学习基础 / Softmax 回归

1. ML System 的三大要素

• 假设模型：模型如何被参数化，如何构建从输入到输出的映射关系
• 损失函数：用来衡量一个假设在任务上表现好不好，其值越小代表表现越好
• 优化方法：寻找能让损失最小化的参数的过程

2. Softmax 回归

考虑一个多分类问题，数据集满足：

$$x^{(i)} \in \mathbb{R}^n,\quad y^{(i)} \in \{1,\dots,k\},\quad i=1,\dots,m.$$

• $n$ ：输入数据集的维度，表示输入集的特征
• $k$ ：标签类别数，亦即输出空间的维度
• $m$：训练样本数

2.1 Linear Hypothesis Function

线性分类器首先将输入向量映射为每个类别的一个分数（logit），再通过 Softmax 将这些分数转换为类别概率。其中

$$h_\theta: \mathbb{R}^n \to \mathbb{R}^k.$$

我们一般按照 batch 形式分批处理数据，将样本按行堆叠为如下的矩阵。其中，按行看，每一行为一份样本的数据；按列看，每列代表一种输入特征。下式将整个训练集表示为矩阵形式：

$$X \in \mathbb{R}^{m\times n},\quad y \in \{1,\dots,k\}^m.$$

针对 $h_\theta: \mathbb{R}^n \to \mathbb{R}^k$ 这样的变换，其标准矩阵表示为 $\mathbb{A}^{k \times n}$ 。不过我们一般选择把模型参数存为 $\theta \in \mathbb{R}^{n \times k}$ ，具体如下式，其中每一列是第 $j$ 个类别的参数向量。这样存储使得 batch 处理时比较方便。

$$\theta = \begin{bmatrix} \mid & \mid & & \mid \\ \theta_1 & \theta_2 & \cdots & \theta_k \\ \mid & \mid & & \mid \end{bmatrix} \in \mathbb{R}^{n\times k}$$

于是

• 对于单样本 $x$（sample），其预测为 $h_\theta(x) = \theta^T x$。
• 对于一批样本 $X \in \mathbb{R}^{b \times n}$ （batch），其预测为 $h_\theta(X) = X \theta$。

2.2 Loss Function

对于多分类问题，损失函数比较直接的做法是统计分类错误的情况，即

$$\ell_{\text{err}}(h(x),y) = \begin{cases} 0 & \text{if } \arg\max_i h_i(x) = y,\\ 1 & \text{otherwise}. \end{cases}$$

它对于评估是有用的，但作为一个优化目标却很糟糕，因为它不可微。因此此处的做法是使用交叉熵损失。

借助 softmax 函数，可以将其我们前述线性分类器得到的打分转化为概率，做到多分类归一化（关于下列形式的由来，可参见CS229广义线性回归模型中的相关推导）：

$$z_i = p(\text{label}=i) = \frac{\exp\left(h_i(x)\right)}{\sum_{j=1}^k \exp\left(h_j(x)\right)}$$

那么，单个样本对于正确类别 𝑦 的交叉熵损失为：

$$\ell_{\text{ce}}(h(x),y) = -\log p(\text{label}=y) = -h_y(x) + \log\sum_{j=1}^k \exp\big(h_j(x)\big)$$

上式的 log-sum-exp 形式简化了原式中的 softmax 计算。

2.3 Optimization

优化的目标就是让平均训练损失降到最低。我们需要在所有可能的参数 $\theta$ 中，找到一组参数，使训练集上的平均损失最小：

$$\min_{\theta}\frac{1}{m}\sum_{i=1}^m \ell\left(h_{\theta}(x^{(i)}),y^{(i)}\right)$$

对于 softmax 回归，即

$$\min_{\theta} \frac{1}{m} \sum_{i=1}^{m} \ell_{ce}\left(\theta^T x^{(i)}, y^{(i)}\right)$$

此优化问题可以借助梯度下降法以解决，可参见此处。

接下来演示 softmax 回归下处理优化问题时的梯度计算。

在单样本情形下，设 $z = \theta^T x$，$p = softmax(z)$，其中 $x \in \mathbb{R}^n$，$\theta \in \mathbb{R}^{n \times k}$，$p \in \mathbb{R}^k$，那么有

$$\begin{aligned} \ell(x,y) &= -\log p_y\\ &= -\log \frac{e^{z_y}} {\sum_{j=1}^{k}e^{z_j}}\\ &= -z_y+\log\sum_{j=1}^{k}e^{z_j}. \end{aligned}$$

交叉熵损失关于某个得分分量 $z_j$ 的导数为

$$\begin{aligned} \frac{\partial \ell}{\partial z_j} &= \frac{\partial}{\partial z_j} \left( -z_y+\log\sum_{r=1}^{k}e^{z_r} \right)\\ &= -\mathbf{1}(j=y) + \frac{e^{z_j}} {\sum_{r=1}^{k}e^{z_r}}\\ &= p_j-\mathbf{1}(j=y). \end{aligned}$$

那么转换为向量形式（使用 one-hot 向量表示真实标签 $e_y$，由于 $z, p \in \mathbb{R}^{k \times 1}$，所以 $e_y$ 跟它们形状相同，也是列向量），得到：

$$\boxed{ \nabla_z \ell = p-e_y }$$

但是我们所求的应该是交叉熵损失对参数 $\theta$ 的导数，这应该如何得出呢？

2.3.1 矩阵微分求解

$$\theta = \begin{bmatrix} \mid & \mid & & \mid \\ \theta_1 & \theta_2 & \cdots & \theta_k \\ \mid & \mid & & \mid \end{bmatrix} \in \mathbb{R}^{n\times k}$$

将 $\theta$ 视为 $k$ 个列向量组成的矩阵，这样可以避免直接处理向量对矩阵求导。
那么，第 $j$ 个得分为：

$$z_j=\theta_j^Tx$$

而参数 $\theta_j$ 只直接影响对应的 $z_j$，得到 $\frac{\partial z_j}{\partial \theta_j} = x$ 。

于是利用链式法则，可以得到：

$$\begin{aligned} \frac{\partial \ell}{\partial \theta_j} &= \frac{\partial \ell}{\partial z_j}\frac{\partial z_j}{\partial \theta_j} \\ &= \big(p_j - \mathbf{1}(j = y)\big)\,x \\ &= \big(p_j - e_{y,j}\big)\,x. \end{aligned}$$

因此整个参数矩阵的梯度可以写成

$$\begin{aligned} \nabla_\theta \ell &= \left[\frac{\partial \ell}{\partial \theta_1}\quad \frac{\partial \ell}{\partial \theta_2}\quad \cdots \quad \frac{\partial \ell}{\partial \theta_k}\right] \\ &= \left[(p_1 - e_{y,1})x \quad (p_2 - e_{y,2})x \quad \cdots \quad (p_k - e_{y,k})x\right] \\ &= x\left[\,p_1 - e_{y,1}\quad p_2 - e_{y,2}\quad \cdots \quad p_k - e_{y,k}\,\right] \\ &= \boxed{x\,(p - e_y)^T}. \end{aligned}$$

2.3.2 快速链式法则

我们可以按标量链式法则得到组成部分，再根据我们知道最终梯度必须和 $\theta$ 一样是 $n \times k$，人为调整转置和乘法顺序。

于是有

$$\begin{aligned} \nabla_\theta \ell_{\text{ce}}(\theta^T x,y) &\to \frac{\partial \ell_{\text{ce}}}{\partial(\theta^T x)} \frac{\partial(\theta^T x)}{\partial\theta}\\ &= (p - e_y)\cdot x \\ &\xrightarrow{\text{调整乘法顺序与转置}} x(p - e_y)^T. \end{aligned}$$

对于 batch，有 $L = \frac{1}{B}\sum_{i=1}^{B}\ell_i$ ，那么

$$\begin{aligned} \nabla_\theta L &\rightarrow \frac{\partial L}{\partial(X\theta)}\frac{\partial(X\theta)}{\partial\theta}\\ &= \frac{1}{B}(P - Y)\cdot X \\ &\xrightarrow{\text{调整乘法顺序与转置}} \boxed{\frac{1}{B}X^T(P - Y)}. \end{aligned}$$

参考

1. https://ickma2311.github.io/ML/DLSys/cmu-dlsys-lecture-2-ml-refresher-softmax-regression.html