机器学习方法(八)：Softmax Regression

2019-08-27

Softmax Regression 可以看做是 LR 算法在多分类上的推广，即类标签 y 的取值大于或者等于 2。

假设数据样本集为$\left\{\left(X^{(1)}, y^{(1)}\right),\left(X^{(2)}, y^{(2)}\right),\left(X^{(3)}, y^{(3)}\right), \ldots,\left(X^{(m)}, y^{(m)}\right)\right\}$

对于 SR 算法, 其输入特征为: $X^{(i)} \in \mathbb{R}^{n+1},$ 类别标记为: $y^{(i)} \in\{0,1,2, \ldots, k\},$ 假设函数为每一个样本估计其所属类别的概率 $P(y=j \mid X),$ 具体的假设函数为：

$h_{\theta}\left(X^{(i)}\right)=\left[\begin{array}{c}P\left(y^{(i)}=1 \mid X^{(i)} ; \theta\right) \\P\left(y^{(i)}=2 \mid X^{(i)} ; \theta\right) \\\ldots \\P\left(y^{(i)}=k \mid X^{(i)} ; \theta\right)\end{array}\right]=\frac{1}{\sum_{j=1}^{k} e^{\theta^{T} X^{(i)}}}\left[\begin{array}{c}e^{\theta_{1}^{T} X^{(i)}} \\e^{\theta_{2}^{T} X^{(i)}} \\\ldots \\e^{\theta_{k}^{T} X^{(i)}}\end{array}\right]$

其中，$\theta_i \in \mathbb{R}^{n+1}$，则对于每一个样本估计其所属的类别的概率为

$P\left(y^{(i)}=j \mid X^{(i)} ; \theta\right)=\frac{e^{\theta_{j}^{T} X^{(i)}}}{\sum_{l=1}^{k} e^{\theta_{l}^{T} X^{(i)}}}$

交叉熵损失函数：我们可以像线性回归那样使用平方损失函数$||\hat{y}^{(i)}-{y}^{(i)}||^2 / 2$。然而，想要预测分类结果正确，我们其实并不需要预测概率完全等于标签概率。例如，在图像分类的例子里，如果$y^{(i)}=3$，那么我们只需要$\hat{y_3}^{(i)}$比其他两个的预测值$\hat{y_1}^{(i)}$和$\hat{y_2}^{(i)}$大就行了。即使$\hat{y_3}^{(i)}$值为0.6，不管其他两个预测值为多少，类别预测均正确。而平方损失过于严格，例如$\hat{y_1}^{(i)}=\hat{y_2}^{(i)}=0.2$比$\hat{y_1}^{(i)}=\hat{y_2}^{(i)}=0.4$的损失要小很多，虽然两者都有同样正确的分类结果。

改善以上问题的一个方法就是使用更适合衡量两个概率分布差异的测量函数。其中，交叉熵(cross entropy)是一个常用的衡量方法：
$H(\pmb y^{(i)},\hat{\pmb y}^{(i)}) = -\sum_{j=1}^{q}y_j^{(i)}\log\hat{y}_j^{(i)}$
上式中向量$\pmb y^{(i)}$中只有第$y^{(i)}$个元素的$y_{y^{(i)}}^{(i)}$为1，其余全为0。也就是说，交叉熵只关心对正确分类的预测概率，因为只要其值足够大，就可以确保分类结果正确。

因此，Softmax Regression的损失函数为：

$J(\theta)=-\frac{1}{m}\left[\sum_{i=1}^{m} \sum_{j=1}^{k} I\left\{y^{(i)}=j\right\} \log \frac{e^{\theta_j^T{X}(i)}}{\sum_{l=1}^{k} e^{\theta_l^T{X}(i)}}\right]$

其中$I(x)=\left\{\begin{array}{ll}0 & \text { if } x=\text { false } \\1 & \text { if } x=\text { true }\end{array}\right.$表示指示函数。

对于上述的损失函数，可以使用梯度下降法求解。首先求参数的梯度：

$\begin{aligned} \frac{\partial J(\theta)}{\partial \theta_{j}} &=-\frac{1}{m}\left[\sum_{i=1}^{m} \frac{\partial}{\partial \theta_{j}} \left\{ \sum_{j=1}^{k} I\left(y^{(i)}=j\right) \log \frac{e^{\theta_{j}^{T} x^{(i)}}}{\sum_{l=1}^{k} e^{\theta_{l}^{T} x^{(i)}}}\right\}\right] \\ &=-\frac{1}{m} \left[\sum_{i=1}^{m} \frac{\partial}{\partial \theta_{j}} \left\{ \sum_{j=1}^{k} I\left\{y^{(i)}=j\right\}\left(\theta_{j}^{T} x^{(i)}-\log \sum_{l=1}^{k} e^{\theta_{l}^{T} x^{(i)}}\right)\right\}\right] \\ &=-\frac{1}{m}\left[\sum_{i=1}^{m} I\left\{y^{(i)}=j\right\}\left(x^{(i)}-\sum_{j=1}^{k} \frac{e^{\theta_{j}^{T} x^{(i)}} \cdot x^{(i)}}{\sum_{l=1}^{k} e^{\theta_{l}^{T} x^{(i)}}}\right)\right] \\ &=-\frac{1}{m}\left[\sum_{i=1}^{m} I\left\{y^{(i)}=j\right\}\left(1-\sum_{j=1}^{k} \frac{e^{\theta_{j}^{T} x^{(i)}}}{\sum_{l=1}^{k} e^{\theta_{l}^{T} x^{(i)}}}\right) x^{(i)} \right] \\ &=-\frac{1}{m}\left[\sum_{i=1}^{m} \left(I\left\{y^{(i)}=j\right\}-\sum_{j=1}^{k} I\left\{y^{(i)}=j\right\} \frac{e^{\theta_{j}^{T} x^{(i)}}}{\sum_{l=1}^{k} e^{\theta_{l}^{T} x^{(i)}}}\right) x^{(i)} \right] \\ &=-\frac{1}{m}\left[\sum_{i=1}^{m} \left(I\left\{y^{(i)}=j\right\}-\frac{e^{\theta_{j}^{T} x^{(i)}}}{\sum_{l=1}^{k} e^{\theta_{l}^{T} x^{(i)}}}\right) x^{(i)} \right] \\ \end{aligned}$

当 $ y^{(i)}=j $ 时：

$\quad \frac{\partial J(\theta)}{\partial \theta_{j}}=-\frac{1}{m} \sum_{i=1}^{m}\left[\left(1-\frac{e^{\theta_{j}^{T} X^{(i)}}}{\sum_{l=1}^{k} e^{\theta_{l}^T{(i)}}}\right) X^{(i)}\right]$

当 $ y^{(i)} \neq j $ 时：

$\frac{\partial J(\theta)}{\partial \theta_{j}}=-\frac{1}{m} \sum_{i=1}^{m}\left[\left(-\frac{e^{\theta_{j}^{T} X^{(i)}}}{\sum_{l=1}^{k} e^{\theta_{l}^{T} X^{(i)}}}\right) X^{(i)}\right]$

最终结果：

$g\left(\theta_{j}\right)=\frac{\partial J(\theta)}{\partial \theta_{j}}=-\frac{1}{m} \sum_{i=1}^{m}\left[X^{(i)} \cdot\left(I\left\{y^{(i)}=j\right\}-P\left(y^{(i)}=j \mid X^{(i)} ; \theta\right)\right)\right]$

梯度下降法的迭代更新公式为：

$\theta_j = \theta_j - \alpha \cdot g(\theta_j)$

for i in range(N):
    x = X[i]  # 第i条数据
    score = x.dot(W)  # 计算预测输出
    # 计算概率
    p = np.exp(score) / np.sum(np.exp(score))
    c = y[i]
    # 计算损失
    loss += - np.log(p[c])
    # 计算梯度第一项
    dW[:, y[i]] -= x
    # 计算梯度第二项
    dW += x.reshape(-1, 1).dot(p.reshape(1, -1))
    
# 计算最终损失
loss /= N
loss += reg * np.sum(W * W)
# 计算最终梯度
dW /= N
dW += 2 * reg * W

N, D = X.shape
S = X.dot(W)
# 计算概率
p1 = np.exp(S[np.arange(N), y])
p2 = np.sum(np.exp(S), axis=1)
p = p1 / p2
# 损失
loss = np.sum(-np.log(p)) / N + reg * np.sum(W * W)
# 梯度
p3 = np.exp(S) / p2.reshape(-1, 1)
p3[np.arange(N), y] -= 1
dW = X.T.dot(p3) / N + 2 * reg * W

HowardWang

机器学习方法(八)：Softmax Regression

Reference