2. 逻辑回归

Logistic回归主要用于二分类任务，其本质是假设数据服从某个分布，然后使用极大似然估计做参数估计。

2.1 对比线性回归

逻辑回归和线性回归都是一种广义线性模型。看下面这个例子：

对于Tumor的良性和恶性这个二分类问题，0表示负类为良性，1表示正类为恶性。下图展示了在这8个训练样本下，使用线性回归模型$h_\theta(x)=\Theta^Tx$可能拟合出下图中的红线。

此时我们可以正确判别肿瘤是良性还是恶性的：根据这条直线可以找到一个阈值，比如 $h_\theta(x)=0.5$，当$h_\theta(x)\geq0.5$时预测$y=1$为恶性，当$h_\theta(x)<0.5$时预测$y=0$为良性。

现在如果我们添加一个训练样本，线性回归可能拟合出下面的蓝线：

此时如果我们任然选取$h_\theta(x)=0.5$作为阈值，此时线性回归模型表现十分差劲，它会把正类样本错误分类成负类。这是因为：对于分类任务$y=0\ or\ 1$，但是线性回归的假设函数$h_\theta(x)$可能远远大于1或者小于0，这回导致线性回归模型在分类任务中表现很差。

2.2 假设函数

在逻辑回归中，我们选取的假设函数满足$0\leq h_\theta(x)\leq 1$。我们对线性回归模型做如下改变：

\begin{equation} h_\theta(x)=g(\theta^Tx)\\ g(z)=\frac{1}{1+e^{-z}} \end{equation}

其中$g(z)$就是我们常说的Sigmoid函数或者称之为Logistic函数。Sigmoid函数如下如下图所示，可以保证假设函数$0\leq h_\theta(x)\leq 1$。

对于Logistic回归模型，给定输入x和拟合的参数$\theta$，模型会输出该样本为正例的概率$h_\theta(1|x;\theta)$。以肿瘤分类问题为例，$x=[x_0,x_1]^T=[1,tumorSize]^T$，$h_\theta(x)=0.7$，表示该肿瘤有70%的概率为恶性肿瘤。

2.3 决策边界

上面介绍了逻辑回归的假设函数，那么这个假设函数到底在计算什么呢？模型是如何完成分类任务的呢？下面就介绍一下逻辑回归的分类原理——决策边界。

在逻辑回归中$h_\theta(x)=g(\theta^Tx)$，$g(z)=\frac{1}{1+e^{-z}}$。假设$h_\theta(x)\ge0.5$时预测$y=1$，$h_\theta(x)<0.5$时预测$y=0$，也就是：

• 当$z\ge0$时，$g(z)\ge0.5$，$h_\theta(x)\ge0.5$，预测$y=1$
• 当$z<0$时，$g(z)<0.5$，$h_\theta(x)<0.5$，预测$y=0$

可以发现：决策边界只取决于我们拟合出的参数和特征维度，和训练集无关。换句话说，一旦我们拟合出了模型参数，我们就唯一确定了模型的决策边界，模型也就训练成功了。那么我们如何拟合模型参数$\theta$呢？

2.4 如何拟合参数$\theta$

首先我们重新梳理下逻辑回归模型的主体：

• 训练集：$\{(x^{(1)},y^{(1)}),(x^{(2)},y^{(2)}),...,(x^{(m)},y^{(m)})\}$m个训练样本
• 特征：$x\in[x_0,x_1,...,x_n]^T$，$x_0=1,y\in\{0,1\}$
• 假设函数：$h_\theta(x)=\frac{1}{1+e^{-\theta^Tx}}$
• **学习目标：**拟合出最优的模型参数$\theta$

2.4.1 代价函数

首先回顾下线性回归中的代价函数：J(\theta)=\frac{1}{m}\sum_\limits{i+1}^m\frac{1}{2}(h_\theta(x^{i})-y^{(i)})^2。我们令$Cost(h_\theta(x),y)=\frac{1}{2}(h_\theta(x)-y)^2$，则$J(\theta)=\frac{1}{m}\sum\limits_{i+1}^mCost(h_\theta(x^{(i)}),y^{(i)})$，这个代价函数在线性回归中很好用。但是在逻辑回归中，$h_\theta(x)$是非线性的Sigmoid函数，这会如下图所示，导致代价函数是非凸的，使用梯度下降优化模型时无法保证收敛到全局最优点：

所以，在我们需要改进代价函数，设计如下代价函数：

$f(x)=\left\{ \begin{aligned} -log(h_\theta(x))\quad if\ y=1\\ -log(1-h_\theta(x))\quad if\ y=0 \end{aligned} \right.$

我们可以绘制出$y=-log(z)$和$y=-log(1-h_\theta(x))$的函数图像：

此时我们可以发现这样的代价函数具有很好地性质，以y=1为例：

• 在$z=h_\theta(x)=1$时，表明我们的预测完全正确，代价函数值为0
• 在$z=h_\theta(x)$趋向于0时，表明我们的预测完全错误，代价函数值趋向于无穷大

这和我们的逻辑是相符合的。

2.4.2 梯度下降

为了求代价函数的导数，我们可以将上面的代价函数变形为：$Cost(h_\theta(x),y)=-ylog(h_\theta(x))-(1-y)log(1-h_\theta(x))$，不难验证这和上面的分段函数是等价的。所以我们的整体代价函数为：

$\begin{aligned} J(\theta)&=\frac{1}{m}\sum\limits_{i=1}^mCost(h_\theta(x^{(i)},y^{(i)})\\ &=-\frac{1}{m}[\sum\limits_{i=1}^my^{(i)}logh_\theta(x^{(i)})+(1-y^{(i)})log(1-h_\theta(x^{(i)}))] \end{aligned}$

为了拟合最优的参数$\theta$，我们需要最小化代价函数，即$\mathop{min}\limits_\theta J(\theta)$。最小化代价函数的方法就是梯度下降，不断执行下面的操作，直到收敛：

\begin{equation} \theta_j:=\theta_j-\alpha\frac{\partial J(\theta)}{\partial \theta_j}\\ \frac{\partial J(\theta)}{\partial \theta_j}=\sum\limits_{i=1}^m(h_\theta(x^{i})-y^{(i)})x_j^{i} \end{equation}

3. Softmax

上面的逻辑回归通常用于二分类问题，对于多分类问题，比如将动物分成猫、狗、其他三个类别，此时要想完成该分类任务需要两个逻辑回归分类器，首先使用一个分类器将其分成猫和其他两个类别，如果分类结果为其他，再使用另外一个分类器将“其他”分类成狗和其他两个类别。如果分类的类别很多，这样分类会非常麻烦，所以大家就提出了Softmax用于多分类任务。

3.1 计算方法

Softmax用于多分类过程，通常是神经网络的最后一层，它将前一层神经元的输出映射到（0,1）区间内，将其看成属于某个类别的概率来进行多分类。因此，Softmax层的神经元个数就等于类别数，其计算方法如下：

$S_i=\frac{e^{z^i}}{\sum_je^{z^j}}$

其中$z^i$表示第i个元素的值，$S_i$表示该元素计算出的Softmax值，更形象的如下图所示：

不难验证计算出的所有的Softmax值得和为1，我么可以将这些softmax值视为概率，我们选取其中值最大的（也就是概率最大）的节点作为我们的预测类别。

Softmax具有一些比较好的性质：

• 单调性，如果$z_i$增大，那么$y_i$增大，$y_j,i\neq j$减小（可以通过导数进行验证）
• 非局部性，任何输出的$y_i$都依赖所有带权输入，因为计算公式的分母为$\sum_ke^{z_k}$
• 归一化，所有输出之和为1，可以将输出看做概率

3.2 在神经网络中的应用

用于分类任务的深度神经网络最后一层往往都是Softmax层，其通常由全连接层+Softmax组成，如下图所示：

其计算过程$\hat y=softmax(z)=softmax(W^Tx+b)$包含两步，其中$softmax(z_j)=\frac{e^{z_j}}{\sum_Ke^{z_j}}$：

• 第一步：全连接层将权重矩阵与输入向量想乘再加上偏置，即$z=w·x+b$，将n个$(-\infty,+\infty)$的实数映射为K个$(-\infty,+\infty)$的实数
• 第二步：Softmax将K个$(-\infty,+\infty)$的实数映射为K个$(0,1)$的实数，且K个数之和为1

3.3 理解Softmax

3.3.1 加权角度

通常把网络最后一个全连接层（Softmax层）的输入x看作网络提取到的特征：

$z_j=w_j·x+b_j=w_{j1}x_1+w_{j2}x_2+...+w_{jn}x_n+b_j$

其中$z_j$可以看做该样本属于类别$j$的得分，然后通过$softmax(z_j)$对分数进行归一化，将其映射为属于类别$j$的概率。从这个角度可以这样理解上式：特征x的每一个维度$x_i$都对该样本是否属于j类别有一定的影响，我们对所有维度进行加权求和就能够得到该样本属于j类的总分，而其中$w_{ji}$表示加权求和时特征第i个维度的值的权重。

3.3.2 模板匹配角度

如下图所示，我们可以将$w_j$视为第j类的特征模板，Softmax层的计算可以看做是特征与每个模板进行模板匹配，计算样本特征和每个类别特征模板之间的相似度，最后再通过softmax计算将其映射成概率。

如果只有一个全连接层的神经网络（等价于线性分类器），我们可以将每个类别的特征模板直接可视化如下：

如果是多层神经网络，最后一个全连接层的模板是特征空间的模板，可视化需要映射回输入空间。

3.3.3 几何角度

将最后一个全连接层的输入x看做特征，一个特征对应多维空间中的一个点。

对于二分类问题，使用线性分类器$\hat y=w·x+b$，若$\hat y\ge0$即位于超平面上方为正类，若$\hat y<0$位于超平面下方为负类。

对于多分类问题，我们就需要为每个类别都设置一个超平面，通过空间中特征点到各个超平面的距离判断样本所属类别。$w_j$为每个超平面的法向量，指向正值方向，特征点到各个超平面的距离为：

$d_j=\frac{w_j·x+b_j}{||w_j||}$

softmax层计算的得分$z_j=||w_j||d_j$，再通过softmax将$z_j$映射为概率。如下图所示：

3.4 Softmax的反向传播

3.4.1 损失函数

多分类问题中通常采用交叉熵作为损失函数：

$L = -\sum\limits_{i=1}^{m}y_iloga_i^L$

其中$a=[a_1^L,a_2^L,...,a_m^L]^T$，$y=[y_1,y_2,...,y_m]^m$。

在分类任务中y通常为one-hot向量，所以损失函数可以简化为：

$L=-loga_o^L$

其中$o$为目标类赌赢的维度，即one-hot向量中1对应的维度。

3.4.2 反向传播

要进行反向传播，我们首先需要计算下面这个偏导向量（梯度）：

$\delta^L=\frac{\partial C}{\partial z^L}$

然后根据这个梯度$\delta^L$更新相应的参数。下面我们来计算上面公式具体等于什么：

1. 首先根据链式法则，有$\delta^L=\frac{\partial C}{\partial z^L}=\frac{\partial C}{\partial a^L}\frac{\partial a^L}{\partial z^L}$

2. C为交叉熵损失函数$C=-loga_o^L$，下面计算$\frac{\partial C}{\partial a^L}$

   • 如果$i=o$，那么$\frac{\partial C}{\partial a_i^L}=-\frac{1}{a_i^L}$

     注：这里的log的底数默认是e，信息论理交叉熵使用的底数是2。这里使用什么底数并不重要，只是导致最终的损失相差一个常数倍而已。

   • 如果$i\neq o$，那么$\frac{\partial C}{\partial a_i^L}=0$

   所以$\frac{\partial C}{\partial a^L}=[0,0,...,\frac{1}{a_o^L},...,0]$，其中o是目标类对应的维度。

3. $\frac{\partial a^L}{\partial z^L}$对应全连接层，$a^L$是一个向量，$z^L$也是一个向量，$\frac{\partial a^L}{\partial z^L}$得到的是一个雅克比矩阵：

   $\frac{\partial a^L}{\partial z^L}=\left[ \begin{matrix} \frac{\partial a_1^L}{\partial z_1^L} & \frac{\partial a_1^L}{\partial z_2^L} & ... &\frac{\partial a_1^L}{\partial z_m^L} \\ \frac{\partial a_2^L}{\partial z_1^L} & \frac{\partial a_2^L}{\partial z_2^L} & ... &\frac{\partial a_2^L}{\partial z_m^L} \\ ... & ...& ...& ...&\\ \frac{\partial a_m^L}{\partial z_1^L} & \frac{\partial a_m^L}{\partial z_2^L} & ... &\frac{\partial a_m^L}{\partial z_m^L} \end{matrix} \right]$

   softmax公式为：$a_i^L=\frac{e^{z_i^L}}{\sum_{j=1}^me^{z_j^L}}$，根据求导公式有：

   $\frac{\partial a_i^L}{\partial z_j^L}=\frac{\frac{\partial e^{z_i^L}}{\partial z_j^L}\sum_{k=1}^me^{z_k^L}-e^{z_i^L}\frac{\partial \sum_{k=1}^me^{z_k^L}}{\partial z_j^L}}{(\sum_{k=1}^me^{z_k^L})^2}=\frac{\frac{\partial e^{z_i^L}}{\partial z_j^L}\sum_{k=1}^me^{z_k^L}-e^{z_i^L}e^{z_j^L}}{(\sum_{k=1}^me^{z_k^L})^2}$

   其中$\frac{\partial e^{z_i^L}}{\partial z_j^L}$需要讨论i和j的关系：

   • 当$i=j$时，$\frac{\partial e^{z_i^L}}{\partial z_j^L}=e^{z_i^L}=e^{z_j^L}$

     $\begin{aligned} \frac{\partial a_i^L}{\partial z_j^L}&=\frac{\frac{\partial e^{z_i^L}}{\partial z_j^L}\sum_{k=1}^me^{z_k^L}-e^{z_i^L}e^{z_j^L}}{(\sum_{k=1}^me^{z_k^L})^2}\\ &=\frac{e^{z_i^L}\sum_{k=1}^me^{z_k^L}-e^{z_i^L}e^{z_j^L}}{(\sum_{k=1}^me^{z_k^L})^2}\\ &=\frac{e^{z_i^L}\sum_{k=1}^me^{z_k^L}-e^{z_i^L}e^{z_j^L}}{(\sum_{k=1}^me^{z_k^L})^2}-\frac{e^{z_i^L}}{\sum_{k=1}^me^{z_k^L}}\frac{e^{z_j^L}}{\sum_{k=1}^me^{z_k^L}}\\ &=a_i^L-a_i^La_j^L\\ &=a_i^L(1-a_i^L) \end{aligned}$

   • 当$i\neq j$时，$\frac{\partial e^{z_i^L}}{\partial z_j^L}=0$

     $\begin{aligned} \frac{\partial a_i^L}{\partial z_j^L}&=\frac{\frac{\partial e^{z_i^L}}{\partial z_j^L}\sum_{k=1}^me^{z_k^L}-e^{z_i^L}e^{z_j^L}}{(\sum_{k=1}^me^{z_k^L})^2}\\ &=\frac{0\sum_{k=1}^me^{z_k^L}-e^{z_i^L}e^{z_j^L}}{(\sum_{k=1}^me^{z_k^L})^2}\\ &=-\frac{e^{z_i^L}}{\sum_{k=1}^me^{z_k^L}}\frac{e^{z_j^L}}{\sum_{k=1}^me^{z_k^L}}\\ &=-a_i^La_j^L \end{aligned}$

   最终我们可以得到：

   $\frac{\partial a^L}{\partial z^L}=\left[ \begin{matrix} a_1^L(1-a_1^L) & -a_2^La_1^L & ... &-a_m^La_1^L \\ -a_1^La_2^L & a_2^L(1-a_2^L) & ... &-a_m^La_2^L \\ ... & ...& ...& ...&\\ -a_1^La_m^L & -a_2^La_m^L & ... &a_m^L(1-a_m^L) \end{matrix} \right]$

4. 我们对上面2、3步的推导结果合并后可得：

   $\begin{aligned} \delta^L&=\frac{\partial C}{\partial z^L}=\frac{\partial C}{\partial a^L}\frac{\partial a^L}{\partial z^L}\\ &=\left[ \begin{matrix} a_1^L(1-a_1^L) & -a_2^La_1^L & ... &-a_m^La_1^L \\ -a_1^La_2^L & a_2^L(1-a_2^L) & ... &-a_m^La_2^L \\ ... & ...& ...& ...&\\ -a_1^La_m^L & -a_2^La_m^L & ... &a_m^L(1-a_m^L) \end{matrix} \right]\left[\begin{matrix}0\\0\\0\\·\\-\frac{1}{a_o}\\0\\·\\0\end{matrix}\right]\\ &=[a_1^L,a_2^L,...,a_o^L-1,...,a_m^L]^T\\ &=[a_1^L-0,a_2^L-0,...,a_o^L-1,...,a_m^L-0]^T\\ &=a^L-y \end{aligned}$

   我们可以发现softmax的梯度十分简洁，就是预测概率$a^L$和目标类别y的onehot向量之间的差，实现起来十分简单。

3.5 参考资料

https://zhuanlan.zhihu.com/p/40135042

https://zhuanlan.zhihu.com/p/25723112

https://www.cnblogs.com/shine-lee/p/10077961.html

4. 层次Softmax

4.1 简介

层次Softmax方法最先在word2vector模型中提出。word2vector模型有两种：一种是基于上下文预测某个单词的词袋模型CBOW，另一种是基于单词预测其可能的上下文的skip-gram模型。这两种方法在优化过程中都存在一个问题：

• 问题：从隐藏层到输出 的Softmax层计算量很大，因为词汇表中的每个单词都可以看成一个类别，类别总数等于词汇表大小。
• 解决方案：一种是负采样技术，另一种就是本文介绍的Hierachical Softmax

层次Softmax根据类别及其出现频率构建霍夫曼树（类别出现频率越高，树的路径越短），树的叶子节点代表类别标签，非叶子节点代表神经元，这样具有以下好处：

• 假设有N个类别，使用softmax计算类别标签计算量为V，使用层次softmax计算量为$logV$（N个类别相当于有N个叶子节点，树高度为$logV$）
• 使用Huffman树，出现频率高的类别在树上端，这样高频类别标签计算的时间会更短

4.2 计算原理

假设有$C1\sim C8$8个类别的数据构成了上图所示的一棵Huffman树，每个叶子节点表示一个类别标签，非叶子节点类似神经元。新来一个节点$X_i$后，从根节点开始，每个非叶子节点处都要执行一次二分类，计算走左边的概率（负类）和走右边的概率（正类），直到叶子节点：

$\begin{aligned} P(右)&=\sigma(X_i\theta)=\frac{1}{1+e^{x_i\theta}}\\ P(左)&=1-\sigma(X_i\theta) \end{aligned}$

新节点$X_i$所走路径的最后一个叶子节点代表的类别即模型的预测结果$Y_i$，预测$X_i$的标签为$Y_i$的概率为：

$P(Y_i|X_i)=\prod_{j=2}^lP(d_j|X_i,\theta_{j-1})$

其中:

$P(d_j|X_i,\theta_{j-1})=\left\{ \begin{aligned} &\sigma(X_i\theta_{j-1})\quad &if\ d_j=1\\ &1-\sigma(X_i\theta_{j-1})\quad &if\ d_j=0 \end{aligned} \right.$

主要我们可以得到：

$P(Y_i|X_i)=\prod_{j=2}^lP(d_j|X_i,\theta_{j-1})=\prod_{j=2}^l[\sigma(X_i\theta_{j-1})]^{d_j}[1-\sigma(X_i\theta_{j-1})]^{1-d_j}$

假设$p$为预测$X_i$类别的路径，路径$p$包含$l$个节点$\{p_1,p_2,...,p_l\}$，路径中每个非叶子节点执行二分类对应的参数为$\{\theta_1,\theta_2,...,\theta_{l-1}\}$（因为最后节点为叶子节点，不需要执行二分类）。

4.3 梯度

如果我们和逻辑回归一样，采用交叉熵作为损失函数，则模型损失函数定义如下：

$L=-\frac{1}{n}\sum_{i=1}^nlog(P(Y_i|X_i))$

注：word2vector中采用的是对数似然函数作为损失函数，即$L=\frac{1}{n}\sum_{i=1}^nlog(P(Y_i|X_i))$，使用梯度上升法进行优化。

假设我们每次只采用一个样本进行梯度更新，则有：

$\begin{aligned} L &= -log(P(Y_i|X_i))\\ &=-log\Big(\prod_{j=2}^l[\sigma(X_i\theta_{j-1})]^{d_j}[1-\sigma(X_i\theta_{j-1})]^{1-d_j}\Big)\\ &=-\sum_{j=2}^llog\Big([\sigma(X_i\theta_{j-1})]^{d_j}[1-\sigma(X_i\theta_{j-1})]^{1-d_j}\Big)\\ &=-\sum_{j=2}^l(d_jlog[\sigma(X_i\theta_{j-1})]+(1-d_j)log[1-\sigma(X_i\theta_{j-1})]) \end{aligned}$

这样我们可以求解L对X和$\theta$的梯度：

$\begin{aligned} \frac{\partial L}{\partial\theta_{j-1}}&=-\frac{\partial({d_jlog[\sigma(X_i\theta_{j-1})]+(1-d_j)log[1-\sigma(X_i\theta_{j-1})])}}{\theta_{j-1}}\\ &=-(1-d_j-\sigma(X_i\theta_{j-1}))X_i \end{aligned}$

$\frac{\partial L}{\partial X_i}=-\sum_{j=2}^{l}(1-d_j-\sigma(X_i\theta_{j-1}))\theta_{j-1}$

这样我们可以采用梯度下降法更新$\theta$和$X$。