机器学习笔记

第一章 机器学习简介
第二章 感知机
第三章 支持向量机
第四章 朴素贝叶斯分类器
第五章 Logistic回归
第六章 线性回归和岭回归
第七章 多层感知机与反向传播【Python实例】
第八章 主成分分析【PCA降维】
第九章 隐马尔可夫模型
第十章 奇异值分解

---

提示：写完文章后，目录可以自动生成，如何生成可参考右边的帮助文档

---

一、熵

1 定义

熵是信息论中最基本、最核心的一个概念，它衡量了一个概率分布的随机程度，或者说包含的信息量的大小。首先来看离散型随机变量，考虑随机变量取某一个特定值时包含的信息量的大小：

1. 假设随机变量取值为 x，对应的概率为 p(x)。直观来看，取这个值的可能性越小，而它又发生了，则包含的信息量就越大。也就是说，概率越小，信息量越大。例如，一年之内人类登陆火星，包含的信息量显然比广州明天要下雨大，因为前者的概率明显小于后者。
2. 因此如果定义一个函数 h(x)来描述随机变量取值为的信息量的大小的话，则h(x)应该是 p ( x )的单调减函数。

满足单调递减要求的函数太多了,该选择哪个函数呢? 接着考虑。假设有两个相互独立的随机变量, 它们的取值分别为x和y, 取该值的概率为 $p(x)$ 和 $p(y)$ 。根据随机变量的独立性, 它们的联合概率为:
$$p(x,y)=p(x)p(y).$$由于这两个随机变量是相互独立的, 因此它们各自取某一值时包含的信息量应该是两个随机变量分别取这些值的时候包含的信息量之和
$$h(x,y)=h(x)+h(y).$$
这要求 $h(x)$ 能把 $p(x)$ 的乘法转化为加法, 在数学上, 满足此要求的是对数函数。因此, 可以把信息量定义为：

$$h(x)=-\log p(x)$$这个对数的底数是多少并没有太大关系, 根据换底公式, 最后计算出来的结果就差了一个倍数, 信息论中通常以 2 为底, 在机器学习中通常以 $e$ 为底, 在后面的计算中为了方便起见我们用 10 为底。需要强调的对数函数前面加上了负号, 这是因为对数函数是增函数, 而我们要求 $h(x)$ 是 $p(x)$ 的减函 数。另外, 由于 $0\le p(x)\le 1$, 因此 $\log p(x)<0$, 加上负号之后刚好可以保证这个信息量为正。

上面只是考虑了随机变量取某一个值时包含的信息量, 而随机变量的取值是随机的, 有各种可能, 那又怎么计算它取所有各种取值时所包含的信息量呢? 既然随机变量取值有各种情况，而且取每个值有一个概率, 那计算它取各个值时的信息量的均值即数学期望即可, 这个信息量的均值, 就是熵。

对于离散型随机变量, 熵定义为
$$\begin{array}{rl}H(p)& =E_x[-\log p(x)]\\ & =-\sum _i{p}_i\log p_i\end{array}$$这里约定 $p_i=p\left(x_i\right)$ 。

例：

假设$x$概率分布如下：

它的熵为
$$\begin{array}{rl}H(p)& =-0.9\times \log 0.9-0.05\times \log 0.05-0.02\times \log 0.02-0.03\times \log 0.03\\ & =0.041+0.065+0.034+0.046\\ & =\mathrm{0.186.}\end{array}$$

2 熵函数性质

根据熵的定义，把熵看做关于p的函数，有如下性质：

1. 熵函数为凹函数
2. 随机变量取各个值的概率相等(均匀分布)时有极大值
3. 在取某一个值的概率为1，取其他所有值的概率为0时有极小值（此时随机变量退化成某一必然事件或者说确定的变量）。

熵函数求极大极小值，是一个带约束的优化问题，可以用拉格朗日乘子法进行求解。对于离散型随机变量, 熵定义的是如下函数：
$$H(p)=-\sum _{i=1}^n{x}_i\log x_i$$其中 $x_i$ 为随机变量取第 $i$ 个值的概率。约束条件为：
$$\begin{array}{r}{\sum }_{i=1}^n{x}_i=1\\ x_i\ge 0\end{array}$$由于对数函数的定义域是非负的, 因此可以去掉不等式约束。构造拉格朗日乘子函数：
$$L(x,\lambda )=-\sum _{i=1}^n{x}_i\log x_i+\lambda \left(\sum _{i=1}^n{x}_i-1\right)$$对 $x_i$ 求偏导数并令其为 0 , 可以得到:
$$\begin{gathered} \frac{\partial L}{\partial x_i}=-\log x_i-1+\lambda =0 \\ \Rightarrow \log x_i=\lambda -1 \end{gathered}$$这意味着在极值点处所有的 $x_i$ 必须相等。对 $\lambda$ 求偏导数并令其为 0 , 可以得到:
$$\sum _{i=1}^n{x}_i=1$$因此当 $x_i=1/n$ 时函数取得极值。此时熵的值为:
$$\begin{array}{rl}H(p)& =-\sum _{i=1}^n\frac{1}{n}\log \frac{1}{n}\\ & =\log n\end{array}$$进一步的可以证明该值是极大值。熵的二阶偏导数为:
$$\begin{array}{rl}\frac{{\partial }^{2}H}{\partial x_i^2}& =-1/x_i\\ \frac{{\partial }^{2}H}{\partial x_i\partial x_j}& =0,j\ne i\end{array}$$因此Hessian矩阵为
$$\left[\begin{array}{ccc}-1/x_1& \cdots & 0\\ \cdots & .\cdot & \cdots \\ 0& \cdots & -1/x_n\end{array}\right]$$由于 $x_i>0$, 该矩阵负定, 熵是凹函数, 有极大值。因此当 $x_i=1/n$ 时熵有极大值。如果定义:
$$0\log 0=0$$显然它与下面的极限是一致的:
$$\underset{x\to 0}{\lim }x\log x=0$$则当某一个 $x_i=1$, 其他 $x_j=0,j\ne i$ 的时熵有极小值 0
$$\begin{array}{rl}H& =0\log 0+\dots +1\log 1+\dots +0\log 0\\ & =0\end{array}$$除此情况之外, 只要满足$0<x_i<1$, 则 $\log x_i<0$ , 因此
$$-x_i\log x_i>0$$上面这些结果说明熵是非负的，当且仅当随机变量取某一值的概率为 1 , 取其他值的概率为 0 时熵有极小值 0 。此时随机变量退化成普通的变量, 取值固定。而当随机变量取所有值的概率相等时即均匀分布时熵有极大值。故熵的范围为：
$$0\le H(p)\le \log n$$

二、交叉熵

1 定义

交叉熵的定义与熵类似, 不同的是定义在两个概率分布而不是一个概率分布之上。

对于离散型随机变量, 交叉熵定义为：
$$H(p,g)=-\sum _{x}p(x)\log q(x)$$其中 $x$ 为离散型随机变量, $p(x)$ 和 $q(x)$ 是它的两个概率分布。

对于连续型概率分布, 交叉熵定义为：
$${\int }_{x}p(x)\log q(x)dx=E_p[-\log q]$$如果两个概率分布完全相等, 则交叉熵退化成熵。交叉熵衡量了两个概率分布的差异：

1. 其值越大, 两个概率分布相差越大.
2. 其值越小，则两个概率分布的差异越小.

2 性质

交叉熵函数有如下性质：

1. 交叉熵损失函数是凸函数
2. 当两个分布相等的时候, 交叉熵有极小值。

证明同样用拉格朗日乘子法，并验证函数凹凸性即可。

假设第一个概率分布固定即 $p(x)$ 为常数$a_i$, 此时交叉熵为如下形式的函数：
$$H(x)=-\sum _{i=1}^n{a}_i\log x_i$$约束条件为：
$$-\sum _{i=1}^n{x}_i=1$$构造拉格朗日乘子函数
$$L(x,\lambda )=-\sum _{i=1}^n{a}_i\log x_i+\lambda \left(\sum _{i=1}^n{x}_i-1\right)$$

对所有变量求偏导数, 并令偏导数为 0 , 有
$$\begin{array}{c}-\frac{a_i}{x_i}+\lambda =0\\ \sum _{i=1}^n{x}_i=1\\ \sum _{i=1}^n{a}_i=1\end{array}$$最后可以解得
$$\begin{array}{rl}\lambda & =1\\ x_i& =a_i\end{array}$$交叉熵函数的Hessian矩阵为:
$$\left[\begin{array}{ccc}{a}_1/x_1^2& \cdots & 0\\ \cdots & \cdots & \cdots \\ 0& \cdots & a_n/x_n^2\end{array}\right]$$
该矩阵正定, 因此交叉熵损失函数是凸函数, 上面的极值点是极小值点。

三、 应用：logistics回归

1 交叉熵损失函数

在Logistics回归中，交叉熵损失函数定义为：
$$\mathrm{Loss}=-\sum _{i=1}^n{y}_i\log y_i^{\prime }$$其中: $y_i$ 为标签值概率分布(取值为0或1)，$y{i}^{\prime }$ 为预值测概率分布，所以最小化Loss函数，等价于最小化交叉熵，而交叉熵取得最小时，预测值的概率分布与标签值的概率分布最接近！

事实上可以将$y_i^{\prime }=\frac{1}{1+e^{-W^{T}X}}$,代入Loss函数，通过和上面类似的证明，可以证明：

1. Loss函数的Hessian矩阵半正定，目标函数是凸函数。
2. logistic回归求解的优化问题是不带约束条件的凸优化问题。
3. 可以证明，如果使用欧氏距离作为目标函数则无法保证目标函数是凸函数。

这是使用交叉熵而不使用欧氏距离作为logistic回归的目标函数的主要原因。

2 计算实例

假设有一个3分类问题, 某个样例的正确答案是 $(1,0,0)$：

1. 甲模型经过softmax回归之后的预测答案是 $(0.5,0.2,0.3)$
2. 乙模型经过softmax回归之后的预测答案是 $(0.7,0.1,0.2)$

$$\begin{array}{rl}由交叉熵定义：& \\ & \mathbf{H}(\mathbf{p},\mathbf{q})=-\sum _{\mathbf{x}}\mathbf{p}(\mathbf{x})\log \mathbf{q}(\mathbf{x})\\ 可得：& \\ & \mathbf{H}((1,0,0),(0.5,0.2,0.3))=-\log 0.5\approx 0.301\\ & \mathbf{H}((1,0,0),(0.7,0.1,0.2))=-\log 0.7\approx 0.155\end{array}$$

四、 应用：softmax

softmax回归经常被用作神经网络的最后一层，完成多分类任务，现在在分类任务训练时采用的损失函数一般为交叉熵，原因如下：

1. 在神经网络的早期，更多的使用了欧氏距离损失函数，后来对分类任务交叉熵使用的更多
2. 对于分类问题，交叉熵一般比欧氏距离有更好的效果，可以收敛到更好的局部最优解。

假设神经网络的原始输出为 $y_1,y_2,\dots .，y_n$, 那么经过Softmax回归处理之后的输出为:
$$y^{\prime }=\mathrm{softmax}\left(y_i\right)=\frac{e^{y_i}}{{\sum }_{j=1}^n{e}^{y_j}}$$
以上可以看出： $\sum y^{\prime }=1$。这也是为什么softmax层的每个节点的输出值成为了概率和为1的概率分布。

1. 标签是 $[0,0,1,0,\dots .0,0]$ 这种形式
2. 通过softmax实际的输出是 $[0.01,0.01,0.6,\dots .0.02,0.01]$ 这种形式

所以可以用交叉熵作为损失函数，当交叉熵最小时，两个概率分布最相近，实际输出越接近标签！

五、KL散度

有了以上信息论中的相关知识后, 可以进一步引出KL散度。

$\mathrm{KL}$ 散度又可称为相对熵，描述两个概率分布 $\mathrm{P}$ 和 $\mathrm{Q}$ 的差异或相似性, 用 $D_{KL}(P\Vert Q)$ 表示：$$\begin{array}{rl}{D}_{KL}(P\Vert Q)& =H(P,Q)-H(P)\\ & =\sum _{i}P\left(x_i\right)\log \frac{1}{Q\left(x_i\right)}-\sum _{i}P\left(x_i\right)\log \frac{1}{P\left(x_i\right)}\\ & =\sum _{i}P\left(x_i\right)\log \frac{P\left(x_i\right)}{Q\left(x_i\right)}\end{array}$$

很显然, 散度越小, 说明概率 $Q$ 与概率 $P$ 之间越接近, 那么估计的概率分布与真实的概率分布也就越接近。$\mathrm{KL}$ 散度的性质：

1. 非对称性: $D_{KL}(P\Vert Q)\ne D_{KL}(Q\Vert P)$
2. $D_{KL}(P\Vert Q)⩾0$, 仅在 $P=Q$ 时等于0

证明性质2：
$$D_{KL}(P\Vert Q)=\sum _{i}P\left(x_i\right)\log \frac{P\left(x_i\right)}{Q\left(x_i\right)}=-\sum _{i}P\left(x_i\right)\log \frac{Q\left(x_i\right)}{P\left(x_i\right)}$$
由于 $\log$ 函数是凹的, 由 Jensen 不等式可得：
$$\sum _i{\lambda }_{i}f\left(x_i\right)⩽f\left(\sum _i{\lambda }_i{x}_i\right)$$那么：
$$\sum _{i}P\left(x_i\right)\log \frac{Q\left(x_i\right)}{P\left(x_i\right)}⩽\log \left(\sum _{i}P\left(x_i\right)\frac{Q\left(x_i\right)}{P\left(x_i\right)}\right)=\log \left(\sum _{i}Q\left(x_i\right)\right)=\log 1=0$$
因此：
$$D_{KL}(P\Vert Q)=-\sum _{i}P\left(x_i\right)\log \frac{Q\left(x_i\right)}{P\left(x_i\right)}⩾0$$

六、参考资料

1. 理解熵和交叉熵