梯度求解学习小结1

问题

在机器学习中，设计合理、有效的目标函数是为人所津津乐道的技能（本小学生尚无此功力）。倘若设计出来的目标函数连自己都不会求解(优化)那就很尴尬了。像我这种小学生瞎鼓捣出来的目标函数,想知道究竟能不能work,不求解一下写成代码在数据集上跑一跑又如何知晓？

纵观求解方法，有贪心的，动态规划的，蒙特卡洛的，期望最大的，梯度的等等（小学生无责任乱分）。前途无限的深度学习其求解方法全都依赖于梯度，在可以预计的将来极有可能成为大一统的求解方法。因此，如何求解损失函数（这里的目标函数可以称作损失函数）的梯度成了小学生心中最关键的一环。本小节将把叙述重心放在微分部分，也一并给出python编码。

如何求解梯度建议先看看cs231n lecture 4 的ppt或者vidio(cs231n的其他学习资料在这里)。

一些表达上的技巧可以帮助我们后面更好地计算梯度.

梯度推导过程中的trick

逻辑判断

把一些分段函数化为便于求导的乘积形式，多少有点用吧。

二值选择

$$\min(x^2, e^y)=1\{x^2 < e^y\}x^2 + 1\{x^2 \geq e^y\}e^y$$ $$\max(0, x^3)=1\{x^3 \geq 0\}x^3$$

多值选择

$$Y_7=\sum_i1\{i=7\} Y_i$$ $$\sum_x 1\{x=2\}f(x)=f(2)$$

分组讨论：

$$\begin{aligned}\frac{\partial(2s_1-3s_2+e^{s_3})}{\partial s_i} &= \Bigg\{\begin{matrix} 2, & i=1 \\ -3, & i=2 \\ e^{s_3}, & i=3\end{matrix} \\ &= 1\{i=1\}2 - 1\{i=2\}3 + 1\{i=3\}e^{s_3} \end{aligned}$$

逻辑运算

1. 与运算
   

   $$1\{x > 5 \land x < 10\} = 1\{x > 5\} \cdot 1\{x < 10\}$$

2. 或运算
   

   $$1\{x > 5 \lor x < 10\} = 1\{x > 5\} + 1\{x < 10\}$$

打分向量与打分矩阵

对于分类问题，损失函数的输出是实数，输入是打分向量，该向量的分量为样本属于各类别的打分；而batch的平均损失的输入则是打分矩阵S(scores)，如下图所示，这个batch中只有3个样本。

实际中的例子

Multiclass SVM loss

$$L=\sum_{k\neq y}^K\max(0, s_k-s_y+1)$$

其中s为某样本属于各类别的打分，若是k分类，s为长度为K的数组，为了表达它是一个行向量，以下标记为$s^T$, $s_k$为该样本属于第j类的打分，y为真实类别，详情请参见该ppt。

求$\partial L/\partial s_j$

把L中的二值选择用逻辑判断代替

$$\begin{aligned}L &= \sum_{m \neq y}^K \max(0, s_m-s_y+1)\\ &=\sum_{m \neq y}^K1\{s_m-s_y+1 \geq 0\}(s_j-s_y+1) \\ &=\sum_{m \neq y}^K q_{m,y} (s_m-s_y+1) \end{aligned}$$
其中$q_{m,y}=1\{s_m-s_y+1 \geq 0\}$, 则
$$\begin{aligned} \frac{\partial L}{\partial s_j} &= \frac{\partial}{\partial s_j}\sum_{m \neq y} q_{m,y}(s_m-s_y+1)\\ &= \sum_{m \neq y} q_{m,y}\frac{\partial (s_m-s_y+1)}{\partial s_j} \\ &= \sum_{m \neq y} q_{m,y}\Big(1\{j \neq y \land m=j\}- 1\{j=y\}\Big) \\ &= 1\{j \neq y\}\sum_{m \neq y} q_{m,y}1\{m=j\}- 1\{j=y\}\sum_{m \neq y} q_{m,y} \\ &= 1\{j \neq y\}q_{j,y}- 1\{j=y\}\sum_{m \neq y} q_{m,y} \end{aligned}$$

注意： 上面逆用了多值选择的情况

$$\sum_m q_{m,y}1\{m=j\}=q_{j,y}$$

因为有$j \neq y$的保证，为$\sum$加上$m \neq y$的限制不会有任何影响

在矩阵分析中，学习过，实数函数对向量或矩阵求导就是实数函数对向量或矩阵中的每个分量求偏导，若打分向量s是一个$1 \times K$的行向量，则单样本损失对打分向量的梯度有：

$$\frac{\partial L}{\partial s}=\bigg(\frac{\partial L}{\partial s_1}, \frac{\partial L}{\partial s_2}, ..., \frac{\partial L}{\partial s_K}\bigg)$$

求平均损失对打分矩阵的梯度

我们所谓的损失指的都是期望损失，也就是平均损失。若第i条样本的损失为$L^{(i)}$，则N条样本的平均损失为

$$\bar L= \frac{1}{N}\sum_{i=1}^N L^{(i)}$$

注意前面那张图片，打分矩阵各行为各样本的打分向量，因此打分矩阵为

$$S =\left(\begin{matrix} s^{(1)} \\ s^{(2)} \\ \vdots \\ s^{(N)} \end{matrix}\right) = \left(\begin{matrix} s^{(1)}_1 & \cdots & s^{(1)}_K \\ \vdots & \ddots & \vdots \\ s^{(N)}_1 & \cdots & s^{(N)}_K\end{matrix}\right)$$

因此平均损失对打分矩阵S的梯度为

$$\begin{aligned}\frac{d \bar L}{d S} &= \frac{1}{N}\sum_{i=1}^N \frac{d L^{(i)}}{d S} \\ &= \frac{1}{N}\sum_{i=1}^N \left(\begin{matrix} \frac{d L^{(i)}}{d s^{(1)}} \\ \vdots \\ \frac{d L^{(i)}}{d s^{(i)}} \\ \vdots \\ \frac{d L^{(i)}}{d s^{(N)}} \end{matrix}\right) = \frac{1}{N}\sum_{i=1}^N \left(\begin{matrix} 0 \\ \vdots \\ \frac{d L^{(i)}}{d s^{(i)}} \\ \vdots \\ 0 \end{matrix}\right) = \frac{1}{N} \left(\begin{matrix} \frac{d L^{(1)}}{d s^{(1)}} \\ \vdots \\ \frac{d L^{(N)}}{d s^{(N)}} \end{matrix}\right) \\ &= \frac{1}{N}\left(\begin{matrix}\frac{\partial L^{(1)}}{\partial s^{(1)}_1} & \cdots & \frac{\partial L^{(1)}}{\partial s^{(1)}_K} \\ \vdots & \ddots & \vdots \\ \frac{\partial L^{(N)}}{\partial s^{(N)}_1} & \cdots & \frac{\partial L^{(N)}}{\partial s^{(N)}_K}\end{matrix}\right) := dS \end{aligned}$$
定义了一个矩阵dS，其中的元素为
$$\begin{aligned}(dS)_{ij} &= \frac{1}{N}\frac{\partial L^{(i)}}{\partial s_j^{(i)}} \\ &= \frac{1}{N}(1\{j \neq y^{(i)}\}q_{j,y^{(i)}}- 1\{j=y^{(i)}\}\sum_{m \neq y^{(i)}}^K q_{m,y^{(i)}}) \end{aligned}$$

编码实现

def svm_loss(S, y):
  """
  Computes the loss and gradient using for multiclass SVM classification.

  Inputs:
  - S: Input data, of shape (N, C) where S[i, j] is the score for the jth
    class for the ith input.
  - y: Vector of labels, of shape (N,) where y[i] is the label for S[i] and
    0 <= y[i] < C

  Returns a tuple of:
  - loss: Scalar giving the loss
  - dS: Gradient of the loss with respect to S
  """
  N = S.shape[0]
  i = np.arange(N)

  # 求svm loss
  margins = np.maximum(S - S[i, y][:, np.newaxis] + 1, 0)
  margins[i, y] = 0
  loss = np.sum(margins) / N

  # 求dS
  dS = (S - S[i, y][:, np.newaxis] + 1 >= 0).astype('int')
  dS[i, y] = 0
  dS[i, y] = -dS.sum(axis=1)
  dS /= N

  return loss, dS

Softmax loss

$$L=-\log\bigg(\frac{e^{s_y}}{\sum_me^{s_m}}\bigg)$$

除了loss外，其他设定与Multiclass SVM loss一样，求解梯度一样需要以下四个步骤：

1. 求$\partial L/\partial s_j$
2. 求平均损失对打分矩阵的梯度
3. 编码实现

因为只有loss不同，其他都是一样的，因此只有求$\partial L/\partial s_j$和编码实现不同。

求$\partial L/\partial s_j$(方法1)

$$L=-\log\bigg(\frac{e^{s_y}}{\sum_me^{s_m}}\bigg)=\log\sum_me^{s_m}-s_y$$ $$\begin{aligned}\frac{\partial L}{\partial s_j} &= \frac{1}{\sum_me^{s_m}}\frac{\partial (\sum_me^{s_m})}{\partial s_j}-\frac{\partial s_y}{\partial s_j}\\ &= \frac{1}{\sum_me^{s_m}}\cdot \sum_m\frac{\partial e^{s_m}}{\partial s_j}-\frac{\partial s_y}{\partial s_j} \\ &= \frac{1}{\sum_me^{s_m}}\cdot \sum_m 1\{m=j\}e^{s_m}-1\{j=y\} \\ &= \frac{e^{s_j}}{\sum_me^{s_m}}-1\{y=j\} \\ &= p_j - 1\{j=y\} \end{aligned}$$

其中

$$p_j = \frac{e^{s_j}}{\sum_m e^{s_m}}$$

求$\partial L/\partial s_j$(方法2)

之所以要再多写个方法二，是为了增加对这种逻辑求导运算的熟练度。

$$L=-\log\bigg(\frac{e^{s_y}}{\sum_me^{s_m}}\bigg)=-\log(p_y)$$
则
$$\frac{\partial L}{\partial s_j}=-\frac{1}{p_y} \cdot \frac{\partial p_y}{\partial s_j}$$
其中
$$\begin{aligned}\frac{\partial p_y}{\partial s_j} &= \frac{\partial}{\partial s_j} \bigg( \frac{e^{s_y}}{\sum_m e^{s_m}}\bigg)\\ &= 1\{j=y\}\frac{e^{s_y}(\sum_m e^{s_m})-e^{s_y}e^{s_j}}{\big(\sum_m e^{s_m}\big)^2} - 1\{j \neq y\}\frac{e^{s_y}e^{s_j}}{\big(\sum_m e^{s_m}\big)^2} \end{aligned}$$

将其带入$\partial L/\partial s_j$得，

$$\begin{aligned}\frac{\partial L}{\partial s_j} &= -\frac{\sum_me^{s_m}}{e^{s_y}}\bigg(1\{j=y\}\frac{e^{s_y}(\sum_m e^{s_m})-e^{s_y}e^{s_j}}{\big(\sum_m e^{s_m}\big)^2} - 1\{j \neq y\}\frac{e^{s_y}e^{s_j}}{\big(\sum_m e^{s_m}\big)^2}\bigg) \\ &= -\bigg(1\{j=y\}\frac{(\sum_m e^{s_m})-e^{s_j}}{\sum_m e^{s_m}} - 1\{j \neq y\}\frac{e^{s_j}}{\sum_m e^{s_m}}\bigg) \\ &= 1\{j \neq y\}\frac{e^{s_j}}{\sum_m e^{s_m}} -1\{j=y\}\frac{(\sum_m e^{s_m})-e^{s_j}}{\sum_m e^{s_m}} \\ &= 1\{j \neq y\}p_j-1\{j=y\}(1-p_j) \\ &= 1\{j \neq y\}p_j-1\{j=y\} + 1\{j=y\}p_j \\ &= p_j - 1\{j=y\} \end{aligned}$$

注意： 上式最后一步用了一个很简单的或运算

$$1\{j \neq y\}p_j + 1\{j=y\}p_j = 1\{j \neq y \lor j=y\}p_j=p_j$$

编码实现

def softmax_loss(S, y):
  N = X.shape[0]
  i = np.arange(N)

  # 避免数值问题
  Smax = S.max(axis=1).reshape((N, 1))
  Sexp = np.exp(S - Smax) 

  # 求loss
  p = Sexp / Sexp.sum(axis=1, keepdims=True)
  loss = -np.sum(p[i, y]) / N

  # 求dS
  p[i, y] -= 1.0
  dS = p / N

  return loss, dS

注意： 避免数值问题

$$\begin{aligned}\frac{e^{s_j-s_{max}}}{\sum_m e^{s_m-s_{max}}}&= \frac{e^{s_j}/e^{s_{max}}}{\sum_m (e^{s_m}/e^{s_{max}})} \\&= \frac{e^{s_j}/e^{s_{max}}}{(\sum_m e^{s_m})/e^{s_{max}}} \\&= \frac{e^{s_j}}{\sum_m e^{s_m}}\end{aligned}$$
这么做的好处是避免指数运算出现特别大的数而产生溢出

总结

通过上面两个例子，求损失对打分的梯度，关键在于对打分下标的考虑，将选择取值和分组讨论问题转化为逻辑运算，可以简化求导过程，最终简化编码实现。