PowerLZY's Blog

LSTM和GRU算法简单梳理🍭

前言 - 从反向传播推导到梯度消失and爆炸的原因及解决方案？

• 从反向传播推导到梯度消失and爆炸的原因及解决方案（从DNN到RNN，内附详细反向传播公式推导） - 韦伟的文章 - 知乎 https://zhuanlan.zhihu.com/p/76772734

本质上是因为神经网络的更新方法，梯度消失是因为反向传播过程中对梯度的求解会产生sigmoid导数和参数的连乘，sigmoid导数的最大值为0.25，权重一般初始都在0，1之间，乘积小于1，多层的话就会有多个小于1的值连乘，导致靠近输入层的梯度几乎为0，得不到更新。梯度爆炸是也是同样的原因，只是如果初始权重大于1，或者更大一些，多个大于1的值连乘，将会很大或溢出，导致梯度更新过大，模型无法收敛。其实梯度爆炸和梯度消失问题都是因为网络太深，网络权值更新不稳定造成的，本质上是因为梯度反向传播中的连乘效应。

一、反向传播推导到梯度消失and爆炸的原因及解决方案

1.1 ==反向传播推导：==

以上图为例开始推起来，先说明几点，i1，i2是输入节点，h1，h2为隐藏层节点，o1，o2为输出层节点，除了输入层，其他两层的节点结构为下图所示：

举例说明， 为输出层的输入，也就是隐藏层的输出经过线性变换后的值， 为经过激活函数sigmoid后的值；同理 为隐藏层的输入，也就是输入层经过线性变换后的值， 为经过激活函数sigmoid 的值。只有这两层有激活函数，输入层没有。

定义一下sigmoid的函数： 说一下sigmoid的求导：

定义一下损失函数，这里的损失函数是均方误差函数，即：

具体到上图，就是：

到这里，所有前提就交代清楚了，前向传播就不推了，默认大家都会，下面推反向传播。

• 第一个反向传播（热身）

先来一个简单的热热身，求一下损失函数对W5的偏导，即：

首先根据链式求导法则写出对W5求偏导的总公式，再把图拿下来对照（如上），可以看出，需要计算三部分的求导【损失函数、激活函数、线性函数】，下面就一步一步来：

综上三个步骤，得到总公式：

• 第二个反向传播：

接下来，要求损失函数对w1的偏导，即：

还是把图摆在这，方便看，先写出总公式，对w1求导有个地方要注意，w1的影响不仅来自o1还来自o2，从图上可以一目了然，所以总公式为：

所以总共分为左右两个式子，分别又对应5个步骤，详细写一下左边，右边同理：

右边也是同理，就不详细写了，写一下总的公式：

这个公式只是对如此简单的一个网络结构的一个节点的偏导，就这么复杂。。亲自推完才深深的意识到。。。

为了后面描述方便，把上面的公式化简一下， 记为 ， 记为 ，则：

1.2 ==梯度消失，爆炸产生原因：==

从上式其实已经能看出来，求和操作其实不影响，主要是是看乘法操作就可以说明问题，可以看出，损失函数对w1的偏导，与 ，权重w，sigmoid的导数有关，明明还有输入i为什么不提？因为如果是多层神经网络的中间某层的某个节点，那么就没有输入什么事了。所以产生影响的就是刚刚提的三个因素。

再详细点描述，如图，多层神经网络：

参考：PENG：神经网络训练中的梯度消失与梯度爆炸282 赞同 · 26 评论文章

假设（假设每一层只有一个神经元且对于每一层 ，其中为sigmoid函数），如图：

则：

看一下sigmoid函数的求导之后的样子：

发现sigmoid函数求导后最大最大也只能是0.25。

再来看W，一般我们初始化权重参数W时，通常都小于1，用的最多的应该是0，1正态分布吧。

所以 ，多个小于1的数连乘之后，那将会越来越小，导致靠近输入层的层的权重的偏导几乎为0，也就是说几乎不更新，这就是梯度消失的根本原因。

再来看看梯度爆炸的原因，也就是说如果 时，连乘下来就会导致梯度过大，导致梯度更新幅度特别大，可能会溢出，导致模型无法收敛。sigmoid的函数是不可能大于1了，上图看的很清楚，那只能是w了，这也就是经常看到别人博客里的一句话，初始权重过大，一直不理解为啥。。现在明白了。

但梯度爆炸的情况一般不会发生，对于sigmoid函数来说， 的大小也与w有关，因为 ，除非该层的输入值在一直一个比较小的范围内。

其实梯度爆炸和梯度消失问题都是因为网络太深，网络权值更新不稳定造成的，本质上是因为梯度反向传播中的连乘效应。

==所以，总结一下，为什么会发生梯度爆炸和消失：==

本质上是因为神经网络的更新方法，梯度消失是因为反向传播过程中对梯度的求解会产生sigmoid导数和参数的连乘，sigmoid导数的最大值为0.25，权重一般初始都在0，1之间，乘积小于1，多层的话就会有多个小于1的值连乘，导致靠近输入层的梯度几乎为0，得不到更新。梯度爆炸是也是同样的原因，只是如果初始权重大于1，或者更大一些，多个大于1的值连乘，将会很大或溢出，导致梯度更新过大，模型无法收敛。

1.3 梯度消失、爆炸解决方案？

参考：DoubleV：详解深度学习中的梯度消失、爆炸原因及其解决方法

• 预训练加微调
• 梯度剪切、正则

解决方案一（预训练加微调）：

提出采取无监督逐层训练方法，其基本思想是每次训练一层隐节点，训练时将上一层隐节点的输出作为输入，而本层隐节点的输出作为下一层隐节点的输入，此过程就是逐层“预训练”（pre-training）；在预训练完成后，再对整个网络进行“微调”（fine-tunning）。

Hinton在训练深度信念网络（Deep Belief Networks中，使用了这个方法，在各层预训练完成后，再利用BP算法对整个网络进行训练。此思想相当于是先寻找局部最优，然后整合起来寻找全局最优，此方法有一定的好处，但是目前应用的不是很多了。

解决方案二（梯度剪切、正则）：

梯度剪切这个方案主要是针对梯度爆炸提出的，其思想是设置一个梯度剪切阈值，然后更新梯度的时候，如果梯度超过这个阈值，那么就将其强制限制在这个范围之内。这可以防止梯度爆炸。

正则化是通过对网络权重做正则限制过拟合，仔细看正则项在损失函数的形式：

其中， 是指正则项系数，因此，如果发生梯度爆炸，权值的范数就会变的非常大，通过正则化项，可以部分限制梯度爆炸的发生。

注：事实上，在深度神经网络中，往往是梯度消失出现的更多一些

解决方案三（改变激活函数）：

首先说明一点，tanh激活函数不能有效的改善这个问题，先来看tanh的形式：

再来看tanh的导数图像：

发现虽然比sigmoid的好一点，sigmoid的最大值小于0.25，tanh的最大值小于1，但仍是小于1的，所以并不能解决这个问题。

Relu:思想也很简单，如果激活函数的导数为1，那么就不存在梯度消失爆炸的问题了，每层的网络都可以得到相同的更新速度，relu就这样应运而生。先看一下relu的数学表达式：

从上图中，我们可以很容易看出，relu函数的导数在正数部分是恒等于1的，因此在深层网络中使用relu激活函数就不会导致梯度消失和爆炸的问题。

relu的主要贡献在于：

• 解决了梯度消失、爆炸的问题
• 计算方便，计算速度快
• 加速了网络的训练

同时也存在一些缺点：

• 由于负数部分恒为0，会导致一些神经元无法激活（可通过设置小学习率部分解决）
• 输出不是以0为中心的

leakrelu

leakrelu就是为了解决relu的0区间带来的影响，其数学表达为： 其中k是leak系数，一般选择0.1或者0.2，或者通过学习而来解决死神经元的问题。

leakrelu解决了0区间带来的影响，而且包含了relu的所有优点

elu

elu激活函数也是为了解决relu的0区间带来的影响，其数学表达为：

其函数及其导数数学形式为：

但是elu相对于leakrelu来说，计算要更耗时间一些，因为有e。

解决方案四（batchnorm）：【梯度消失】

Batchnorm是深度学习发展以来提出的最重要的成果之一了，目前已经被广泛的应用到了各大网络中，具有加速网络收敛速度，提升训练稳定性的效果，Batchnorm本质上是解决反向传播过程中的梯度问题。batchnorm全名是batch normalization，简称BN，即批规范化，通过规范化操作将输出信号x规范化到均值为0，方差为1保证网络的稳定性。

具体的batchnorm原理非常复杂，在这里不做详细展开，此部分大概讲一下batchnorm解决梯度的问题上。具体来说就是反向传播中，经过每一层的梯度会乘以该层的权重，举个简单例子： 正向传播中，那么反向传播中，，反向传播式子中有w的存在，所以的大小影响了梯度的消失和爆炸，batchnorm就是通过对每一层的输出做scale和shift的方法，通过一定的规范化手段，把每层神经网络任意神经元这个输入值的分布【假设原始是正态分布】强行拉回到接近均值为0方差为1的标准正太分布，即严重偏离的分布强制拉回比较标准的分布， 这样使得激活输入值落在非线性函数对输入比较敏感的区域，这样输入的小变化就会导致损失函数较大的变化，使得让梯度变大，避免梯度消失问题产生，而且梯度变大意味着学习收敛速度快，能大大加快训练速度。

解决方案五（残差结构）：

如图，把输入加入到某层中，这样求导时，总会有个1在，这样就不会梯度消失了。

式子的第一个因子 表示的损失函数到达 L 的梯度，小括号中的1表明短路机制可以无损地传播梯度，而另外一项残差梯度则需要经过带有weights的层，梯度不是直接传递过来的。残差梯度不会那么巧全为-1，而且就算其比较小，有1的存在也不会导致梯度消失。所以残差学习会更容易。

注：上面的推导并不是严格的证，只为帮助理解

==解决方案六（LSTM）：==

在介绍这个方案之前，有必要来推导一下RNN的反向传播，因为关于梯度消失的含义它跟DNN不一样！不一样！不一样！

先推导再来说，从这copy的：沉默中的思索：RNN梯度消失和爆炸的原因565 赞同

RNN结构如图：

假设我们的时间序列只有三段， 为给定值，神经元没有激活函数，则RNN最简单的前向传播过程如下：

假设在t=3时刻，损失函数为 。

则对于一次训练任务的损失函数为 ，即每一时刻损失值的累加。

使用随机梯度下降法训练RNN其实就是对 、 、 以及 求偏导，并不断调整它们以使L尽可能达到最小的过程。

现在假设我们我们的时间序列只有三段，t1，t2，t3。

我们只对t3时刻的 求偏导（其他时刻类似）：

可以看出对于 求偏导并没有长期依赖，但是对于 求偏导，会随着时间序列产生长期依赖。因为 随着时间序列向前传播，而 又是 的函数。

根据上述求偏导的过程，我们可以得出任意时刻对 求偏导的公式：

任意时刻对 求偏导的公式同上。

如果加上激活函数， ，则 = 激活函数tanh和它的导数图像在上面已经说过了，所以原因在这就不赘述了，还是一样的，激活函数导数小于1。

==现在来解释一下，为什么说RNN和DNN的梯度消失问题含义不一样？==

1. 先来说DNN中的反向传播：在上文的DNN反向传播中，我推导了两个权重的梯度，第一个梯度是直接连接着输出层的梯度，求解起来并没有梯度消失或爆炸的问题，因为它没有连乘，只需要计算一步。第二个梯度出现了连乘，也就是说越靠近输入层的权重，梯度消失或爆炸的问题越严重，可能就会消失会爆炸。一句话总结一下，DNN中各个权重的梯度是独立的，该消失的就会消失，不会消失的就不会消失。
2. 再来说RNN：RNN的特殊性在于，它的权重是共享的。抛开W_o不谈，因为它在某时刻的梯度不会出现问题（某时刻并不依赖于前面的时刻），但是W_s和W_x就不一样了，每一时刻都由前面所有时刻共同决定，是一个相加的过程，这样的话就有个问题，当距离长了，计算最前面的导数时，最前面的导数就会消失或爆炸，但当前时刻整体的梯度并不会消失，因为它是求和的过程，当下的梯度总会在，只是前面的梯度没了，但是更新时，由于权值共享，所以整体的梯度还是会更新，通常人们所说的梯度消失就是指的这个，指的是当下梯度更新时，用不到前面的信息了，因为距离长了，前面的梯度就会消失，也就是没有前面的信息了，但要知道，整体的梯度并不会消失，因为当下的梯度还在，并没有消失。
3. 一句话概括：RNN的梯度不会消失，RNN的梯度消失指的是当下梯度用不到前面的梯度了，但DNN靠近输入的权重的梯度是真的会消失。

说完了RNN的反向传播及梯度消失的含义，终于该说为什么LSTM可以解决这个问题了，这里默认大家都懂LSTM的结构，对结构不做过多的描述。见第三节。【LSTM通过它的“门控装置”有效的缓解了这个问题，这也就是为什么我们现在都在使用LSTM而非普通RNN。】

二、LSTM 框架结构

前言：

LSTM是RNN的一种变体，更高级的RNN，那么它的本质还是一样的，还记得RNN的特点吗，可以有效的处理序列数据，当然LSTM也可以，还记得RNN是如何处理有效数据的吗，是不是每个时刻都会把隐藏层的值存下来，到下一时刻的时候再拿出来用，这样就保证了，每一时刻含有上一时刻的信息，如图，我们把存每一时刻信息的地方叫做Memory Cell，中文就是记忆细胞，可以这么理解。

RNN什么信息它都存下来，因为它没有挑选的能力，而LSTM不一样，它会选择性的存储信息，因为它能力强，它有门控装置，它可以尽情的选择。如下图，普通RNN只有中间的Memory Cell用来存所有的信息，而从下图我们可以看到，LSTM多了三个Gate。

• Input Gate：输入门，在每一时刻从输入层输入的信息会首先经过输入门，输入门的开关会决定这一时刻是否会有信息输入到Memory Cell。
• Output Gate：输出门，每一时刻是否有信息从Memory Cell输出取决于这一道门。
• Forget Gate：遗忘门，每一时刻Memory Cell里的值都会经历一个是否被遗忘的过程，就是由该门控制的，如果打卡，那么将会把Memory Cell里的值清除，也就是遗忘掉。

在了解LSTM的内部结构之前，我们需要先回顾一下普通RNN的结构，以免在这里很多读者被搞懵，如下：

我们可以看到，左边是为了简便描述RNN的工作原理而画的缩略图，右边是展开之后，每个时间点之间的流程图，注意，我们接下来看到的LSTM的结构图，是一个时间点上的内部结构，就是整个工作流程中的其中一个时间点，也就是如下图：

注意，上图是普通RNN的一个时间点的内部结构，上面已经讲过了公式和原理，LSTM的内部结构更为复杂，不过如果这么类比来学习，我认为也没有那么难。

• Cell：memory cell，也就是一个记忆存储的地方，这里就类似于普通RNN的 ，都是用来存储信息的，这里面的信息都会保存到下一时刻，其实标准的叫法应该是 ，因为这里对应神经网络里的隐藏层，所以是hidden的缩写，无论普通RNN还是LSTM其实t时刻的记忆细胞里存的信息，都应该被称为
• 是这一时刻的输出，也就是类似于普通RNN里的
• 四个 ，这四个相辅相成，才造就了中间的Memory Cell里的值，你肯恩要问普通RNN里有个 作为输入，那LSTM的输入在哪？别着急，其实这四个 都有输入向量 的参与。对了，在解释这四个分别是什么之前，我要先解释一下上图的所有这个符号：都代表一个激活函数，LSTM里常用的激活函数有两个，一个是tanh，一个是sigmoid。

• 

• 是最为普通的输入，可以从上图中看到， 是通过该时刻的输入 和上一时刻存在memory cell里的隐藏层信息 向量拼接，再与权重参数向量 点积，得到的值经过激活函数tanh最终会得到一个数值。
• input gate的缩写i，所以也就是输入门的门控装置， 同样也是通过该时刻的输入 和上一时刻隐藏状态，也就是上一时刻存下来的信息 向量拼接，在与权重参数向量 点积（注意每个门的权重向量都不一样，这里的下标i代表input的意思，也就是输入门)。得到的值经过激活函数sigmoid的最终会得到一个0-1之间的一个数值，用来作为输入门的控制信号。
• 以此类推，就不详细讲解 了，分别是缩写forget和output的门控装置，原理与上述输入门的门控装置类似。上面说了，只有 是输入，其他的三个都是门控装置，负责把控每一阶段的信息记录与遗忘，具体是怎样的呢？我们先来看公式：首先解释一下，经过这个sigmod激活函数后，得到的 都是在0到1之间的数值，1表示该门完全打开，0表示该门完全关闭，

==LSTM迭代过程==

LSTM和GRU算法简单梳理🍭: https://zhuanlan.zhihu.com/p/72500407

：当前序列的隐藏状态、 ：当前序列的输入数据、 ：当前序列的细胞状态、 ： 激活函数、 ： 激活函数。

遗忘门：

输入门：

细胞状态更新：

输出门：

2.1 LSTM之遗忘门

遗忘门是控制是否遗忘的，在 中即以一定的概率控制是否遗忘上一层的细胞状态。图中输入的有前一序列的隐藏状态 和当前序列的输入数据 ，通过一个 激活函数得到遗忘门的输出 。因为 函数的取值在 之间，所以 表示的是遗忘前一序列细胞状态的概率，数学表达式为

2.2 LSTM之输入门

输入门是用来决定哪些数据是需要更新的，由 层决定；然后，一个 层为新的候选值创建一个向量 ，这些值能够加入到当前细胞状态中，数学表达式为

2.3 LSTM之细胞状态更新

前面的遗忘门和输入门的结果都会作用于细胞状态 ，在决定需要遗忘和需要加入的记忆之后，就可以更新前一序列的细胞状态 到当前细胞状态 了，前一序列的细胞状态 乘以遗忘门的输出 表示决定遗忘的信息， 表示新的记忆信息，数学表达式为：

2.4 LSTM之输出门

在得到当前序列的细胞状态 后，就可以计算当前序列的输出隐藏状态 了，隐藏状态 的更新由两部分组成，第一部分是 ，它由前一序列的隐藏状态 和当前序列的输入数据 通过激活函数 得到，第二部分由当前序列的细胞状态 经过 激活函数后的结果组成，数学表达式为

三、GRU 框架结构

循环门单元( )，它组合了遗忘门和输入门到一个单独的更新门当中，也合并了细胞状态 和隐藏状态 ，并且还做了一些其他的改变使得其模型比标准 模型更简单，其数学表达式式为：

首先介绍 的两个门，它们分别是重置门 和更新门 ，计算方法与 中门的计算方法是一致的；然后是计算候选隐藏层 ，该候选隐藏层和 中的 类似，都可以看成是当前时刻的新信息，其中 用来控制需要保留多少之前的记忆，如果 为 则表示 只保留当前序列的输入信息；最后 控制需要从前一序列的隐藏层 中遗忘多少信息和需要加入多少当前序列的隐藏层信息 ，从而得到当前序列的输出隐藏层信息 ，而 是没有输出门的。

GRU和LSTM的性能差不多，但GRU参数更少，更简单，所以训练效率更高。但是，如果数据的依赖特别长且数据量很大的话，LSTM的效果可能会稍微好一点，毕竟参数量更多。所以默认推荐使用LSTM。

参考资料⬇️

Understanding LSTM Networks

LSTM Q&A

1、为什么LSTM可以解决梯度消失和梯度爆炸？

参考（这个老哥说的是最好的）：LSTM如何来避免梯度弥散和梯度爆炸？

• ==LSTM 中梯度的传播有很多条路径， 这条路径上只有逐元素相乘和相加的操作，梯度流最稳定==；但是其他路径（例如 )上梯度流与普通 RNN 类似，照样会发生相同的权重矩阵反复连乘。
• LSTM 刚提出时没有遗忘门，或者说相当于 ，这时候在 直接相连的短路路径上， 可以无损地传递给 ，从而这条路径上的梯度畅通无阻，不会消失。类似于 ResNet 中的残差连接。
• 但是在其他路径上，LSTM 的梯度流和普通 RNN 没有太大区别，依然会爆炸或者消失。由于总的远距离梯度 = 各条路径的远距离梯度之和，即便其他远距离路径梯度消失了，只要保证有一条远距离路径（就是上面说的那条高速公路）梯度不消失，总的远距离梯度就不会消失（正常梯度 + 消失梯度 = 正常梯度）。因此 LSTM 通过改善一条路径上的梯度问题拯救了总体的远距离梯度。
• 同样，因为总的远距离梯度 = 各条路径的远距离梯度之和，高速公路上梯度流比较稳定，但其他路径上梯度有可能爆炸，此时总的远距离梯度 = 正常梯度 + 爆炸梯度 = 爆炸梯度，因此 LSTM 仍然有可能发生梯度爆炸。不过，==由于 LSTM 的其他路径非常崎岖，和普通 RNN 相比多经过了很多次激活函数（导数都小于 1），因此 LSTM 发生梯度爆炸的频率要低得多==。实践中梯度爆炸一般通过梯度裁剪来解决。
• 对于现在常用的带遗忘门的 LSTM 来说，4 中的分析依然成立，而 3 分为两种情况：其一是遗忘门接近 1（例如模型初始化时会把 forget bias 设置成较大的正数，让遗忘门饱和），这时候远距离梯度不消失；其二是遗忘门接近 0，但这时模型是故意阻断梯度流的，这不是 bug 而是 feature（例如情感分析任务中有一条样本 “A，但是 B”，模型读到“但是”后选择把遗忘门设置成 0，遗忘掉内容 A，这是合理的）。当然，常常也存在 f 介于 [0, 1] 之间的情况，在这种情况下只能说 LSTM 改善（而非解决）了梯度消失的状况。

2、为什么LSTM模型中既存在sigmoid又存在tanh两种激活函数？

关于激活函数的选取，在LSTM中，遗忘门、输入门和输出门使用 Sigmoid函数作为激活函数;在生成候选记忆时，使用双曲正切函数tanh作为激活函数。值得注意的是，这两个激活函数都是饱和的也就是说在输入达到一定值的情况下，输出就不会发生明显变化了。如果是用非饱和的激活图数，例如ReLU，那么将难以实现门控的效果。

• Sigmoid的输出在0-1之同，符合门控的物理定义，且当输入较大或较小时，其输出会非常接近1或0，从而保证该门开或关，在生成候选记亿时，

• tanh函数，是因为其输出在-1-1之间，这与大多数场景下特征分布是0中心的吻合。此外，tanh函数在输入为0近相比 Sigmoid函数有更大的梯度，通常使模型收敛更快。

激活函数的选择也不是一成不变的。例如在原始的LSTM中，使用的激活函数是 Sigmoid函数的变种，h(x)=2sigmoid(x)-1,g(x)＝4 sigmoid(x)-2，这两个函数的范国分别是[-1，1]和[-2，2]。并且在原始的LSTM中，只有输入门和输出门，没有遗忘门，其中输入经过输入门后是直接与记忆相加的，所以输入门控g(x)的值是0中心的。

后来经过大量的研究和实验，人们发现增加遗忘门对LSTM的性能有很大的提升且h(x)使用tanh比2 sigmoid(x)-1要好，所以现代的LSTM采用 Sigmoid和tanh作为激活函数。事实上在门控中，使用 Sigmoid函数是几乎所有现代神经网络模块的共同选择。例如在门控循环单元和注意力机制中，也广泛使用 Sigmoid i函数作为门控的激活函数。

为什么？

1. 门是控制开闭的，全开时值为1，全闭值为０。用于遗忘和保留信息。
2. 对于求值的激活函数无特殊要求。

能更换吗？

1. 门是控制开闭的，全开时值为1，全闭值为０。用于遗忘和保留信息。门的激活函数只能是值域为０到１的，最常见的就是sigmoid。
2. 对于求值的激活函数无特殊要求。

3、能不能把tanh换成relu？

不行？对于梯度爆炸的问题用梯度裁剪解决就行了。

1. 会造成输出值爆炸。RNN共享参数矩阵，长程的话相当于多个相乘，最后输出类似于 ，其中是 激活函数，如果 有一个大于1的特征值，且使用relu激活函数，那最后的输出值会爆炸。但是使用tanh激活函数，能够把输出值限制在-1和1之间。
2. 这里relu并不能解决梯度消失或梯度爆炸的问题。假设有t=3，最后一项输出反向传播对W求导， 。我们用最后一项做分析，即使使用了relu， ，还是会有两个 相乘，并不能解决梯度消失或梯度爆炸的问题。

CNN-门控卷积网络

• https://zhuanlan.zhihu.com/p/59064623
• 参数估计
• ** 卷积神经网络中用1*1 卷积有什么作用或者好处呢？** - 初识CV的回答 - 知乎 https://www.zhihu.com/question/56024942/answer/1850649283

一、参数估计

卷积操作的本质是稀疏交互和参数共享。

稀疏交互：每个输出神经元仅与前一层特定局部区域内的神经元存在连接权重。物理意义：通常图像，文字、语音等现实世界中的数据都具有局部的特征结构。

参数共享：卷积核中的每一个元素将作用于每一个局部输入的特定位置上。物理意义：平移等变性

池化操作：针对非重叠区域，均值池化、最大池化。除了能显著降低参数外，还能够保持对平移、伸缩、旋转操作的不变性。

1.1 正向传播

这里用输入为 \(3 * 3\) 矩阵 \(A^{l-1}\), 步长为 1 , 卷积核为 \(2 * 2\) 矩阵 \(W^{l}\), 输出为 \(2 * 2\) 矩阵 \(Z^{l}\) 的卷积层为 例。矩阵 \(A^{l-1}\) 可以是整个神经网络的输入, 也可以是池化层的输出。这个模型简化为输入层 \(A^{l-1}\) 经 过卷积计算得到特征图 \(Z^{l}, Z^{l}\) 经过激活函数 \(\sigma(x)\) 得到输出层 \(A^{l}\) (实际上在现实工程中很多时候不用激 活函数)。对于第 \(l\) 层, 有下列表达式: \[ \left[\begin{array}{lll} a_{1} & a_{2} & a_{3} \\ a_{4} & a_{5} & a_{6} \\ a_{7} & a_{8} & a_{9} \end{array}\right]^{l-1} \Rightarrow\left[\begin{array}{cc} \omega_{1} & \omega_{2} \\ \omega_{3} & \omega_{4} \end{array}\right]^{l} \Rightarrow\left[\begin{array}{ll} z_{1} & z_{2} \\ z_{3} & z_{4} \end{array}\right]^{l} \Rightarrow\left[\begin{array}{ll} a_{1} & a_{2} \\ a_{3} & a_{4} \end{array}\right]^{l} \]

\[ \left\{\begin{aligned} a_{1}^{l} &=\sum\left(\left[\begin{array}{ll} a_{1} & a_{2} \\ a_{4} & a_{5} \end{array}\right]^{l-1} \cdot\left[\begin{array}{ll} \omega_{1} & \omega_{2} \\ \omega_{3} & \omega_{4} \end{array}\right]^{l}\right)=\sigma\left(\omega_{1} a_{1}^{l-1}+\omega_{2} a_{2}^{l-1}+\omega_{3} a_{3}^{l-1}+\omega_{4} a_{4}^{l-1}+b^{l}\right) \\ a_{2}^{l} &=\sum\left(\left[\begin{array}{ll} a_{2} & a_{3} \\ a_{5} & a_{6} \end{array}\right]^{l-1} \cdot\left[\begin{array}{ll} \omega_{1} & \omega_{2} \\ \omega_{3} & \omega_{4} \end{array}\right]^{l}\right)=\sigma\left(\omega_{1} a_{2}^{l-1}+\omega_{2} a_{3}^{l-1}+\omega_{3} a_{5}^{l-1}+\omega_{4} a_{6}^{l-1}+b^{l}\right) \\ a_{3}^{l} &=\sum\left(\left[\begin{array}{ll} a_{4} & a_{5} \\ a_{7} & a_{8} \end{array}\right]^{l-1} \cdot\left[\begin{array}{ll} \omega_{1} & \omega_{2} \\ \omega_{3} & \omega_{4} \end{array}\right]^{l}\right)=\sigma\left(\omega_{1} a_{4}^{l-1}+\omega_{2} a_{5}^{l-1}+\omega_{3} a_{7}^{l-1}+\omega_{4} a_{8}^{l-1}+b^{l}\right) \\ a_{4}^{l} &=\sum\left(\left[\begin{array}{ll} a_{5} & a_{6} \\ a_{8} & a_{9} \end{array}\right]^{l-1} \cdot\left[\begin{array}{ll} \omega_{1} & \omega_{2} \\ \omega_{3} & \omega_{4} \end{array}\right]^{l}\right)=\sigma\left(\omega_{1} a_{5}^{l-1}+\omega_{2} a_{6}^{l-1}+\omega_{3} a_{8}^{l-1}+\omega_{4} a_{9}^{l-1}+b^{l}\right) \end{aligned}\right. \]

简单来说, 卷积过程就是对应的位置代入函数之后相加求和, 不同的函数有不同的参数 \(w\) 和 \(b\), 我们需 要训练的是卷积核参数, 所以这个公式还可以写做 \(Z^{l}=W^{l} * A^{l-1}+b^{l}, \sigma(x)\) 是激活函数, 我们假设是ReLU函数, 求导比较好求, 所以我们接下来的计算忽略了对激活层的求导。 \[ \sigma(x)=\left\{\begin{array}{lc} 0 & , \quad x<0 \\ x & , \quad x>=0 \end{array}\right. \]

1.2 反向传播

二、CNN - 李宏毅

三、CNN Q&A

3.1 卷积神经网络的卷积核大小、个数，卷积层数如何确定呢？

• https://cloud.tencent.com/developer/article/1462368

每一层卷积有多少channel数，以及一共有多少层卷积，这些暂时没有理论支撑，一般都是靠感觉去设置几组候选值，然后通过实验挑选出其中的最佳值。这也是现在深度卷积神经网络虽然效果拔群，但是一直为人诟病的原因之一。

3.2 卷积神经网络中用1*1 卷积有什么作用或者好处呢？

• 卷积神经网络中用1*1 卷积有什么作用或者好处呢？ - YJango的回答 - 知乎 https://www.zhihu.com/question/56024942/answer/194997553

降维：Inception结构可以看出，这些1X1的卷积的作用是为了让网络根据需要能够更灵活的控制数据的depth的。

加入非线性。卷积层之后经过激励层，1*1的卷积在前一层的学习表示上添加了非线性激励（ non-linear activation ），提升网络的表达能力；

1 * 1的卷积就是多个feature channels线性叠加，nothing more!只不过这个组合系数恰好可以看成是一个1 * 1的卷积。这种表示的好处是，完全可以回到模型中其他常见N*N的框架下，不用定义新的层。

一、TF-IDF

https://blog.csdn.net/u010417185/article/details/87905899

TF-IDF(Term Frequency-Inverse Document Frequency, 词频-逆文件频率)是一种用于资讯检索与资讯探勘的常用加权技术。TF-IDF是一种统计方法，用以评估一字词对于一个文件集或一个语料库中的其中一份文件的重要程度。字词的重要性随着它在文件中出现的次数成正比增加，但同时会随着它在语料库中出现的频率成反比下降。

上述引用总结就是, 一个词语在一篇文章中出现次数越多, 同时在所有文档中出现次数越少, 越能够代表该文章。这也就是TF-IDF的含义。

1.1 TF

TF(Term Frequency，词频)表示词条在文本中出现的频率，这个数字通常会被归一化(一般是词频除以文章总词 数), 以防止它偏向长的文件（同一个词语在长文件里可能会比短文件有更高的词频, 而不管该词语重要与否）。TF 用公式表示如下: \[ T F_{i, j}=\frac{n_{i, j}}{\sum_k n_{k, j}} \] 其中, \(n_{i, j}\) 表示词条 \(t_i\) 在文档 \(d_j\) 中出现的次数, \(T F_{i, j}\) 就是表示词条 \(t_i\) 在文档 \(d_j\) 中出现的频率。

但是, 需要注意, 一些通用的词语对于主题并没有太大的作用, 反倒是一些出现频率较少的词才能够表达文章的主题, 所以单纯使用是TF不合适的。权重的设计必须满足：一个词预测主题的能力越强, 权重越大, 反之, 权重 越小。所有统计的文章中, 一些词只是在其中很少几篇文章中出现, 那么这样的词对文章的主题的作用很大, 这些 词的权重应该设计的较大。IDF就是在完成这样的工作。

1.2 IDF

IDF(Inverse Document Frequency，逆文件频率)表示关键词的普遍程度。如果包含词条 \(i\) 的文档越少, IDF越 大, 则说明该词条具有很好的类别区分能力。某一特定词语的IDF, 可以由总文件数目除以包含该词语之文件的数 目, 再将得到的商取对数得到: \[ I D F_i=\log \frac{|D|}{1+\left|j: t_i \in d_j\right|} \] 其中, \(|D|\) 表示所有文档的数量, \(\left|j: t_i \in d_j\right|\) 表示包含词条 \(t_i\) 的文档数量, 为什么这里要加 1 呢? 主要是防止包含词条 \(t_i\) 的数量为 0 从而导致运算出错的现象发生。

某一特定文件内的高词语频率, 以及该词语在整个文件集合中的低文件频率, 可以产生出高权重的TF-IDF。因此, TF-IDF倾向于过滤淖常见的词语, 保留重要的词语, 表达为 \[ T F-I D F=T F \cdot I D F \] 最后在计算完文档中每个字符的tfidf之后, 对其进行归一化, 将值保留在0-1之间, 并保存成稀疏矩阵。

二、TF-IDF Q&A

1、究竟应该是对整个语料库进行tf-idf呢？还是先对训练集进行tf-idf，然后再对xtest进行tf-idf呢？两者有什么区别？

fit

• 学习输入的数据有多少个不同的单词，以及每个单词的idf

transform 训练集

• 回我们一个document-term matrix.

transform 测试集

transform的过程也很让人好奇。要知道，他是将测试集的数据中的文档数量纳入进来，重新计算每个词的idf呢，还是直接用训练集学习到的idf去计算测试集里面每一个tf-idf呢？

如果纳入了测试集新词，就等于预先知道测试集中有什么词，影响了idf的权重。这样预知未来的行为，会导致算法丧失了泛化性。

2、TF-IDF 模型加载太慢

https://thiagomarzagao.com/2015/12/08/saving-TfidfVectorizer-without-pickles/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

import scipy.sparse as sp
from idfs import idfs # numpy array with our pre-computed idfs
from sklearn.feature_extraction.text import TfidfVectorizer

# subclass TfidfVectorizer
class MyVectorizer(TfidfVectorizer):
    # plug our pre-computed IDFs
    TfidfVectorizer.idf_ = idfs

# instantiate vectorizer
vectorizer = MyVectorizer(lowercase = False,
                          min_df = 2,
                          norm = 'l2',
                          smooth_idf = True)

# plug _tfidf._idf_diag
vectorizer._tfidf._idf_diag = sp.spdiags(idfs,
                                         diags = 0,
                                         m = len(idfs),
                                         n = len(idfs))

EM——期望最大 [概率模型]

EM 算法通过引入隐含变量，使用 MLE（极大似然估计）进行迭代求解参数。通常引入隐含变量后会有两个参数，EM 算法首先会固定其中的第一个参数，然后使用 MLE 计算第二个变量值；接着通过固定第二个变量，再使用 MLE 估测第一个变量值，依次迭代，直至收敛到局部最优解。

EM 算法，全称 Expectation Maximization Algorithm。期望最大算法是一种迭代算法，用于含有隐变量（Hidden Variable）的概率参数模型的最大似然估计或极大后验概率估计。

本文思路大致如下：先简要介绍其思想，然后举两个例子帮助大家理解，有了感性的认识后再进行严格的数学公式推导。

1. 思想

EM 算法的核心思想非常简单，分为两步：Expection-Step 和 Maximization-Step。E-Step 主要通过观察数据和现有模型来估计参数，然后用这个估计的参数值来计算似然函数的期望值；而 M-Step 是寻找似然函数最大化时对应的参数。由于算法会保证在每次迭代之后似然函数都会增加，所以函数最终会收敛。

\(E M\) 算法一句话总结就是: \(E\) 步固定 \(\theta\) 优化 \(Q, M\) 步固定 \(Q\) 优化 \(\theta\) 。

2 例子

2.1 例子 A

假设有两枚硬币 \(\mathrm{A}\) 和 \(B\), 他们的随机抛郑的结果如下图所示:

我们很容易估计出两枚硬币抛出正面的概率： \[ \begin{aligned} & \theta_A=24 / 30=0.8 \\ & \theta_B=9 / 20=0.45 \end{aligned} \] 现在我们加入隐变量, 抺去每轮投郑的硬币标记:

碰到这种情况, 我们该如何估计 \(\theta_A\) 和 \(\theta_B\) 的值?

我们多了一个隐变量 \(Z=\left(z_1, z_2, z_3, z_4, z_5\right)\), 代表每一轮所使用的硬币, 我们需要知道每一轮抛郑所使用的硬币这样才能估计 \(\theta_A\) 和 \(\theta_B\) 的值, 但是估计隐变量 \(\mathrm{Z}\) 我们又需要知道 \(\theta_A\) 和 \(\theta_B\) 的值, 才能用极大似然估计法去估计出 Z。这就陷入了一个鸡生蛋和蛋生鸡的问题。

其解决方法就是先随机初始化 \(\theta_A\) 和 \(\theta_B\), 然后用去估计 \(Z\), 然后基于 \(Z\) 按照最大似然概率去估计新的 \(\theta_A\) 和 \(\theta_B\) , 循环至收敛。

2.1.2 计算

随机初始化 \(\theta_A=0.6\) 和 \(\theta_B=0.5\)

对于第一轮来说, 如果是硬币 \(A\), 得出的 5 正 5 反的概率为: \(0.6^5 * 0.4^5\); 如果是硬币 \(B\), 得出的 5 正 5 反的概率为: \(0.5^5 * 0.5^5\) 。我们可以算出使用是硬币 \(A\) 和硬币 \(B\) 的概率 分别为: \[ \begin{aligned} & P_A=\frac{0.6^5 * 0.4^5}{\left(0.6^5 * 0.4^5\right)+\left(0.5^5 * 0.5^5\right)}=0.45 \\ & P_B=\frac{0.5^5 * 0.5^5}{\left(0.6^5 * 0.4^5\right)+\left(0.5^5 * 0.5^5\right)}=0.55 \end{aligned} \]

从期望的角度来看, 对于第一轮抛郑, 使用硬币 \(A\) 的概率是 0.45 , 使用硬币 \(B\) 的概率是 0.55。同理其他轮。这一 步我们实际上是估计出了 Z 的概率分布，这部就是 E-Step。

结合硬币 \(A\) 的概率和上一张结果, 我们利用期望可以求出硬币 \(A\) 和硬币 \(B\) 的贡献。以第二轮硬币 \(A\) 为例子, 计算方式为: \[ \begin{aligned} & H: 0.80 * 9=7.2 \\ & T: 0.80 * 1=0.8 \end{aligned} \] 于是我们可以得到：

然后用极大似然估计来估计新的 \(\theta_A\) 和 \(\theta_B\) 。 \[ \begin{aligned} \theta_A & =\frac{21.3}{21.3+8.6}=0.71 \\ \theta_B & =\frac{11.7}{11.7+8.4}=0.58 \end{aligned} \]

这步就对应了 M-Step，重新估计出了参数值。如此反复迭代，我们就可以算出最终的参数值。

上述讲解对应下图：

2.2 例子 B

如果说例子 A 需要计算你可能没那么直观, 那就举更一个简单的例子:

现在一个班里有 50 个男生和 50 个女生，且男女生分开。我们假定男生的身高服从正态分布： \(N\left(\mu_1, \sigma_1^2\right)\) , 女生的身高则服从另一个正态分布： \(N\left(\mu_2, \sigma_2^2\right)\) 。这时候我们可以用 极大似然法 (MLE) , 分别通过这 50 个男生和 50 个女生的样本来估计这两个正态分布的参数。

但现在我们让情况复杂一点, 就是这 50 个男生和 50 个女生混在一起了。我们拥有 100 个人的身高数据, 却不知 道这 100 个人每一个是男生还是女生。

这时候情况就有点箩尬, 因为通常来说, 我们只有知道了精确的男女身高的正态分布参数我们才能知道每一个人更 有可能是男生还是女生。但从另一方面去考量, 我们只有知道了每个人是男生还是女生才能尽可能准确地估计男女 各自身高的正态分布的参数。

这个时候有人就想到我们必须从某一点开始, 并用迭代的办法去解决这个问题：我们先设定男生身高和女生身高分 布的几个参数（初始值）, 然后根据这些参数去判断每一个样本 (人）是男生还是女生, 之后根据标注后的样本再 反过来重新估计参数。之后再多次重复这个过程，直至稳定。这个算法也就是 EM 算法。

3. 推导

给定数据集, 假设样本间相互独立, 我们想要拟合模型 \(p(x ; \theta)\) 到数据的参数。根据分布我们可以 得到如下似然函数: \[ \begin{aligned} L(\theta) & =\sum_{i=1}^n \log p\left(x_i ; \theta\right) \\ & =\sum_{i=1}^n \log \sum_z p\left(x_i, z ; \theta\right) \end{aligned} \]

第一步是对极大似然函数取对数，第二步是对每个样本的每个可能的类别 z 求联合概率分布之和。如果这个 z 是已知的数，那么使用极大似然法会很容易。但如果 z 是隐变量，我们就需要用 EM 算法来求。事实上，隐变量估计问题也可以通过梯度下降等优化算法，但事实由于求和项将随着隐变量的数目以指数级上升，会给梯度计算带来麻烦；而 EM 算法则可看作一种非梯度优化方法。

3.1 求解含有隐变量的概率模型

为了求解含有隐变量 \(z\) 的概率模型 \(\hat{\theta}=\underset{\theta}{\arg \max } \sum_{i=1}^m \log \sum_{z^{(i)}} p\left(x^{(i)}, z^{(i)} ; \theta\right)\) 需要一些特殊的技巧, 通过引入隐变量\(z^{(i)}\) 的概率分布为 \(Q_i\left(z^{(i)}\right)\), 因为 \(\log (x)\) 是凹函数故结合凹函数形式下的詹森不等式进行放缩处理 \[ \begin{aligned} \sum_{i=1}^m \log \sum_{z^{(i)}} p\left(x^{(i)}, z^{(i)} ; \theta\right) & =\sum_{i=1}^m \log \sum_{z^{(i)}} Q_i\left(z^{(i)}\right) \frac{p\left(x^{(i)}, z^{(i)} ; \theta\right)}{Q_i\left(z^{(i)}\right)} \\ & =\sum_{i=1}^m \log \mathbb{E}\left(\frac{p\left(x^{(i)}, z^{(i)} ; \theta\right)}{Q_i\left(z^{(i)}\right)}\right) \\ & \left.\geq \sum_{i=1}^m \mathbb{E}\left[\log \frac{p\left(x^{(i)}, z^{(i)} ; \theta\right)}{Q_i\left(z^{(i)}\right)}\right)\right] \\ & =\sum_{i=1}^m \sum_{z^{(i)}} Q_i\left(z^{(i)}\right) \log \frac{p\left(x^{(i)}, z^{(i)} ; \theta\right)}{Q_i\left(z^{(i)}\right)} \end{aligned} \] 其中由概率分布的充要条件 \(\sum_{z^{(i)}} Q_i\left(z^{(i)}\right)=1 、 Q_i\left(z^{(i)}\right) \geq 0\) 可看成下述关于 \(z\) 函数分布列的形式:

这个过程可以看作是对 \(\mathcal{L}(\theta)\) 求了下界, 假设 \(\theta\) 已经给定那么 \(\mathcal{L}(\theta)\) 的值就取决于 \(Q_i\left(z^{(i)}\right)\) 和 \(p\left(x^{(i)}, z^{(i)}\right)\) 了, 因 此可以通过调整这两个概率使下界不断上升, 以逼近 \(\mathcal{L}(\theta)\) 的真实值, 当不等式变成等式时说明调整后的概率能够 等价于 \(\mathcal{L}(\theta)\) ，所以必须找到使得等式成立的条件, 即寻找 \[ \left.\mathbb{E}\left[\log \frac{p\left(x^{(i)}, z^{(i)} ; \theta\right)}{Q_i\left(z^{(i)}\right)}\right)\right]=\log \mathbb{E}\left[\frac{p\left(x^{(i)}, z^{(i)} ; \theta\right)}{Q_i\left(z^{(i)}\right)}\right] \] 由期望得性质可知当 \[ \frac{p\left(x^{(i)}, z^{(i)} ; \theta\right)}{Q_i\left(z^{(i)}\right)}=C, \quad C \in \mathbb{R} \quad(*) \] 等式成立，对上述等式进行变形处理可得 \[ \begin{aligned} & p\left(x^{(i)}, z^{(i)} ; \theta\right)=C Q_i\left(z^{(i)}\right) \\ & \Leftrightarrow \sum_{z^{(i)}} p\left(x^{(i)}, z^{(i)} ; \theta\right)=C \sum_{z^{(i)}} Q_i\left(z^{(i)}\right)=C \\ & \Leftrightarrow \sum_{z^{(i)}} p\left(x^{(i)}, z^{(i)} ; \theta\right)=C \end{aligned} \] 把 \((* *)\) 式带入 \((*)\) 化简可知 \[ \begin{aligned} Q_i\left(z^{(i)}\right) & =\frac{p\left(x^{(i)}, z^{(i)} ; \theta\right)}{\sum_{z^{(i)}} p\left(x^{(i)}, z^{(i)} ; \theta\right)} \\ & =\frac{p\left(x^{(i)}, z^{(i)} ; \theta\right)}{p\left(x^{(i)} ; \theta\right)} \\ & =p\left(z^{(i)} \mid x^{(i)} ; \theta\right) \end{aligned} \] 至此, 可以推出在固定参数 \(\theta\) 后, \(Q_i\left(z^{(i)}\right)\) 的计算公式就是后验概率, 解决了 \(Q_i\left(z^{(i)}\right)\) 如何选择得问题。这一步 称为 \(E\) 步, 建立 \(\mathcal{L}(\theta)\) 得下界; 接下来得 \(M\) 步, 就是在给定 \(Q_i\left(z^{(i)}\right)\) 后, 调整 \(\theta\) 去极大化 \(\mathcal{L}(\theta)\) 的下界即 \[ \begin{aligned} & \underset{\theta}{\arg \max } \sum_{i=1}^m \log p\left(x^{(i)} ; \theta\right) \\ & \Leftrightarrow \underset{\theta}{\arg \max } \sum_{i=1}^m \sum_{z^{(i)}} Q_i\left(z^{(i)}\right) \log \frac{p\left(x^{(i)}, z^{(i)} ; \theta\right)}{Q_i\left(z^{(i)}\right)} \\ & \Leftrightarrow \underset{\theta}{\arg \max } \sum_{i=1}^m \sum_{z^{(i)}} Q_i\left(z^{(i)}\right)\left[\log p\left(x^{(i)}, z^{(i)} ; \theta\right)-\log Q_i\left(z^{(i)}\right)\right] \\ & \Leftrightarrow \underset{\theta}{\arg \max } \sum_{i=1}^m \sum_{z^{(i)}} Q_i\left(z^{(i)}\right) \log p\left(x^{(i)}, z^{(i)} ; \theta\right) \end{aligned} \] 因此EM算法的迭代形式为：

这张图的意思就是: 首先我们固定 \(\theta\), 调整 \(Q(z)\) 使下界 \(J(z, Q)\) 上升至与 \(L(\theta)\) 在此点 \(\theta\) 处相等 (绿色曲线到 蓝色曲线) , 然后固定 \(Q(z)\), 调整 \(\theta\) 使下界 \(J(z, Q)\) 达到最大值 \(\left(\theta_t\right.\) 到 \(\left.\theta_{t+1}\right)\) ，然后再固定 \(\theta\), 调整 \(Q(z)\) , 一直到收敛到似然函数 \(L(\theta)\) 的最大值处的 \(\theta\) 。

EM 算法通过引入隐含变量，使用 MLE（极大似然估计）进行迭代求解参数。通常引入隐含变量后会有两个参数，EM 算法首先会固定其中的第一个参数，然后使用 MLE 计算第二个变量值；接着通过固定第二个变量，再使用 MLE 估测第一个变量值，依次迭代，直至收敛到局部最优解。

3.2 EM算法的收敛性

不妨假设 \(\theta^{(k)}\) 和 \(\theta^{(k+1)}\) 是EM算法第 \(k\) 次迭代和第 \(k+1\) 次迭代的结果, 要确保 \(E M\) 算法收敛那么等价于证明 \(\mathcal{L}\left(\theta^{(k)}\right) \leq \mathcal{L}\left(\theta^{(k+1)}\right)\) 也就是说极大似然估计单调增加, 那么算法最终会迭代到极大似然估计的最大值。在选定 \(\theta^{(k)}\) 后可以得到 \(E\) 步 \(Q_i^{(k)}\left(z^{(i)}\right)=p\left(z^{(i)} \mid x^{(i)} ; \theta^{(k)}\right)\), 这一步保证了在给定 \(\theta^{(k)}\) 时, 詹森不等式中的等式成立即 \(\mathcal{L}\left(\theta^{(k)}\right)=\sum_{i=1}^m \sum_{z^{(i)}} Q_i^{(k)}\left(z^{(i)}\right) \log \frac{p\left(x^{(i)}, z^{(i)} ; \theta^{(k)}\right)}{Q_i\left(z^{(i)}\right)}\)

然后再进行 \(M\) 步, 固定 \(Q_i^{(k)}\left(z^{(i)}\right)\) 并将 \(\theta^{(k)}\) 视作变量, 对上式 \(\mathcal{L}\left(\theta^{(k)}\right)\) 求导后得到 \(\theta^{(k+1)}\) 因此有如下式子成立 \[ \begin{aligned} \mathcal{L}\left(\theta^{(k)}\right) & =\sum_{i=1}^m \sum_{z^{(i)}} Q_i^{(k)}\left(z^{(i)}\right) \log \frac{p\left(x^{(i)}, z^{(i)} ; \theta^{(k)}\right)}{Q_i\left(z^{(i)}\right)} \\ & \leq \sum_{i=1}^m \sum_{z^{(i)}} Q_i^{(k)}\left(z^{(i)}\right) \log \frac{p\left(x^{(i)}, z^{(i)} ; \theta^{(k)}\right)}{Q_i\left(z^{(i)}\right)} \\ & \leq \mathcal{L}\left(\theta^{(k+1)}\right) \end{aligned} \] 首先 (a) 式是前面 \(E\) 步所保证詹森不等式中的等式成立的条件, (a) 到 (b) 是 \(M\) 步的定义, (b) 到 (c) 对任意 参数都成立, 而其等式的条件是固定 \(\theta\) 并调整好 \(Q\) 时成立, \((b)\) 到 \((c)\) 只是固定 \(Q\) 调整 \(\theta\), 在得到 \(\theta^{(k+1)}\) 时, 只是最大化 \(\mathcal{L}\left(\theta^{(k)}\right)\), 也就是 \(\mathcal{L}\left(\theta^{(k+1)}\right)\) 的一个下界而没有使等式成立。

4. 另一种理解

坐标上升法（Coordinate ascent）：

途中直线为迭代优化路径，因为每次只优化一个变量，所以可以看到它没走一步都是平行与坐标轴的。

EM 算法类似于坐标上升法，E 步：固定参数，优化 Q；M 步：固定 Q，优化参数。交替将极值推向最大。

5. 应用

EM 的应用有很多，比如、混合高斯模型、聚类、HMM 等等。其中 EM 在 K-means 中的用处，我将在介绍 K-means 中的给出。

参考文献

1. 怎么通俗易懂地解释 EM 算法并且举个例子?

2. 从最大似然到 EM 算法浅解

一、什么是KNN【KD树 + SIFT+BBF算法】

1.1 KNN的通俗解释

何谓K近邻算法，即K-Nearest Neighbor algorithm，简称KNN算法，单从名字来猜想，可以简单粗暴的认为是：K个最近的邻居，当K=1时，算法便成了最近邻算法，即寻找最近的那个邻居。

用官方的话来说，所谓K近邻算法，即是给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的K个实例（也就是上面所说的K个邻居），这K个实例的多数属于某个类，就把该输入实例分类到这个类中。

​

​

如上图所示，有两类不同的样本数据，分别用蓝色的小正方形和红色的小三角形表示，而图正中间的那个绿色的圆所标示的数据则是待分类的数据。也就是说，现在，我们不知道中间那个绿色的数据是从属于哪一类（蓝色小正方形or红色小三角形），KNN就是解决这个问题的。

如果K=3，绿色圆点的最近的3个邻居是2个红色小三角形和1个蓝色小正方形，少数从属于多数，基于统计的方法，判定绿色的这个待分类点属于红色的三角形一类。

如果K=5，绿色圆点的最近的5个邻居是2个红色三角形和3个蓝色的正方形，还是少数从属于多数，基于统计的方法，判定绿色的这个待分类点属于蓝色的正方形一类。

于此我们看到，当无法判定当前待分类点是从属于已知分类中的哪一类时，我们可以依据统计学的理论看它所处的位置特征，衡量它周围邻居的权重，而把它归为(或分配)到权重更大的那一类。这就是K近邻算法的核心思想。

1.2 近邻的距离度量

我们看到，K近邻算法的核心在于找到实例点的邻居，这个时候，问题就接踵而至了，如何找到邻居，邻居的判定标准是什么，用什么来度量。这一系列问题便是下面要讲的距离度量表示法。

有哪些距离度量的表示法(普及知识点，可以跳过)：

1.2.1 欧式距离

欧氏距离, 最常见的两点之间或多点之间的距离表示法, 又称之为欧几里得度量, 它定义于欧几里得空间中, 如点 \(x=(x 1, \ldots, x n)\) 和 \(y=(y 1, \ldots, y n)\) 之间的距离为: \[ d(x, y)=\sqrt{\left(x_1-y_1\right)^2+\left(x_2-y_2\right)^2+\ldots+\left(x_n-y_n\right)^2}=\sqrt{\sum_{i=1}^n\left(x_i-y_i\right)^2} \] 二维平面上两点 \(a(x 1, y 1)\) 与 \(b(x 2, y 2)\) 间的欧氏距离: \[ d_{12}=\sqrt{\left(x_1-x_2\right)^2+\left(y_1-y_2\right)^2} \] 三维空间两点 \(a(x 1, y 1, z 1)\) 与 \(b(x 2, y 2, z 2)\) 间的欧氏距离: \[ d_{12}=\sqrt{\left(x_1-x_2\right)^2+\left(y_1-y_2\right)^2+\left(z_1-z_2\right)^2} \] 两个n维向量 \(a(x 11, \times 12, \ldots, x 1 n)\) 与 \(b(\times 21, \times 22, \ldots, \times 2 n)\) 间的欧氏距离: \[ d_{12}=\sqrt{\sum_{k=1}^n\left(x_{1 k}-x_{2 k}\right)^2} \] 也可以用表示成向量运算的形式:

1.2.2 曼哈顿距离

曼哈顿距离, 我们可以定义曼哈顿距离的正式意义为L1-距离或城市区块距离, 也就是在欧几里得空间的固定 直角坐标系上两点所形成的线段对轴产生的投影的距离总和。例如在平面上, 坐标 \((x 1, y 1)\) 的点P1与坐标 \((\mathrm{x} 2, \mathrm{y} 2)\) 的点P2的曼哈顿距离为: \(\left|x_1-x_2\right|+\left|y_1-y_2\right|\), 要注意的是, 曼哈顿距离依赖座标系统的转度, 而非系统在座标轴上的平移或映射。

通俗来讲, 想象你在曼哈顿要从一个十字路口开车到另外一个十字路口, 驾驶距离是两点间的直线距离吗? 显 然不是, 除非你能穿越大楼。而实际驾驶距离就是这个“曼哈顿距离”, 此即曼哈顿距离名称的来源, 同时, 曼 哈顿距离也称为城市街区距离(City Block distance)。

二维平面两点 \(a(x 1, y 1)\) 与 \(b(x 2, y 2)\) 间的曼哈顿距离 \[ d_{12}=\left|x_1-x_2\right|+\left|y_1-y_2\right| \] 两个 \(n\) 维向量 \(a(x 11, x 12, \ldots, x 1 n)\) 与 \(b(x 21, x 22, \ldots, x 2 n)\) 间的曼哈顿距离 \[ d_{12}=\sum_{k=1}^n\left|x_{1 k}-x_{2 k}\right| \]

1.2.3 切比雪夫距离

切比雪夫距离, 若二个向量或二个点 \(\mathrm{p} 、\) and \(\mathrm{q}\), 其座标分别为 \(\mathrm{P}\) 及 \(\mathrm{qi}\), 则两者之间的切比雪夫距离定义如 下: \(D_{C h e b y s h e v}(p, q)=\max _i\left(\left|p_i-q_i\right|\right)\)

这也等于以下Lp度量的极值： \(\lim _{x \rightarrow \infty}\left(\sum_{i=1}^n\left|p_i-q_i\right|^k\right)^{1 / k}\), 因此切比雪夫距离也称为 \(\infty\) 度量。

以数学的观点来看, 切比雪夫距离是由一致范数 (uniform norm) (或称为上确界范数）所衍生的度量, 也 是超凸度量（injective metric space）的一种。

在平面几何中, 若二点 \(\mathrm{p} \mathrm{q}\) 的直角坐标系坐标为 \((x 1, y 1)\) 及 \((x 2, y 2)\), 则切比雪夫距离为: \(D_{C h e s s}=\max \left(\left|x_2-x_1\right|,\left|y_2-y_1\right|\right)\)

玩过国际象棋的朋友或许知道，国王走一步能够移动到相邻的8个方格中的任意一个。那么国王从格子(x1,y1) 走到格子(x2,y2)最少需要多少步? 。你会发现最少步数总是 \(\max (|x 2-x 1| ，|y 2-y 1|)\) 步 。有一种类似的 一种距离度量方法叫切比雪夫距离。

二维平面两点 \(a(x 1, y 1)\) 与 \(b(x 2, y 2)\) 间的切比雪夫距离 : \[ d_{12}=\max \left(\left|x_2-x_1\right|,\left|y_2-y_1\right|\right) \] 两个 \(n\) 维向量 \(a(x 11, x 12, \ldots, x 1 n)\) 与 \(b(x 21, x 22, \ldots, x 2 n)\) 间的切比雪夫距离 : \[ d_{12}=\max _i\left(\left|x_{1 i}-x_{2 i}\right|\right) \]

简单说来，各种“距离”的应用场景简单概括为：

• 空间：欧氏距离，
• 路径：曼哈顿距离，国际象棋国王：切比雪夫距离，
• 以上三种的统一形式:闵可夫斯基距离，
• 加权：标准化欧氏距离，
• 排除量纲和依存：马氏距离，
• 向量差距：夹角余弦，
• 编码差别：汉明距离，
• 集合近似度：杰卡德类似系数与距离，
• 相关：相关系数与相关距离。

1.3 K值选择

1. 如果选择较小的K值，就相当于用较小的领域中的训练实例进行预测，“学习”近似误差会减小，只有与输入实例较近或相似的训练实例才会对预测结果起作用，与此同时带来的问题是“学习”的估计误差会增大，换句话说，K值的减小就意味着整体模型变得复杂，容易发生过拟合；
2. 如果选择较大的K值，就相当于用较大领域中的训练实例进行预测，其优点是可以减少学习的估计误差，但缺点是学习的近似误差会增大。这时候，与输入实例较远（不相似的）训练实例也会对预测器作用，使预测发生错误，且K值的增大就意味着整体的模型变得简单。
3. K=N，则完全不足取，因为此时无论输入实例是什么，都只是简单的预测它属于在训练实例中最多的累，模型过于简单，忽略了训练实例中大量有用信息。

在实际应用中，K值一般取一个比较小的数值，例如采用交叉验证法（简单来说，就是一部分样本做训练集，一部分做测试集）来选择最优的K值。

1.4 KNN最近邻分类算法的过程

1. 计算测试样本和训练样本中每个样本点的距离（常见的距离度量有欧式距离，马氏距离等）；
2. 对上面所有的距离值进行排序；
3. 选前 k 个最小距离的样本；
4. 根据这 k 个样本的标签进行投票，得到最后的分类类别；

关于KNN的一些问题

1. 在k-means或kNN，我们是用欧氏距离来计算最近的邻居之间的距离。为什么不用曼哈顿距离？

   答：我们不用曼哈顿距离，因为它只计算水平或垂直距离，有维度的限制。另一方面，欧式距离可用于任何空间的距离计算问题。因为，数据点可以存在于任何空间，欧氏距离是更可行的选择。例如：想象一下国际象棋棋盘，象或车所做的移动是由曼哈顿距离计算的，因为它们是在各自的水平和垂直方向的运动。

2. KD-Tree相比KNN来进行快速图像特征比对的好处在哪里?

   答：极大的节约了时间成本．点线距离如果 >　最小点，无需回溯上一层，如果<,则再上一层寻找。

参考文献

1. KNN与KD树
2. 【数学】kd 树算法之详细篇 - 椰了的文章 - 知乎
3. KNN是生成式模型还是判别式的，为什么？ - 风控算法小白的回答 - 知乎

数据降维算法: https://www.zhihu.com/column/c_1194552337170214912

一、 PCA

降维问题的优化目标：将一组 \(\mathrm{N}\) 维向量降为 \(\mathrm{K}\) 维，其目标是选择 \(\mathrm{K}\) 个单位正交基，使得原始数据变换到这组基上 后，各变量两两间协方差为 0 ，而变量方差则尽可能大（在正交的约束下，取最大的 \(\mathrm{K}\) 个方差）。

要找的 \(\mathbf{P}\) 是能让原始协方差矩阵对角化的 \(\mathbf{P}\) 。换句话说, 优化目标变成了寻找一个矩阵 \(\mathbf{P}\), 满足 \(P C P^T\) 是一个对 角矩阵，并且对角元素按从大到小依次排列，那么 \(P\) 的前 \(K\) 行就是要寻找的基，用 \(P\) 的前 \(K\) 行组成的矩阵乘以 \(X\) 就使得 X 从 N 维降到了 K 维并满足上述优化条件。

PCA (Principal Component Analysis) 是一种常见的数据分析方式, 常用于高维数据的降维，可用于提取数 据的主要特征分量。PCA 的数学推导可以从最大可分型和最近重构性两方面进行, 前者的优化条件为划分后方差 最大, 后者的优化条件为点到划分平面距离最小，这里我将从最大可分性的角度进行证明。

1. 向量表示与基变换

我们先来介绍些线性代数的基本知识。

1.1.1 内积

两个向量的 A 和 B 内积我们知道形式是这样的： \[ \left(a_1, a_2, \cdots, a_n\right) \cdot\left(b_1, b_2, \cdots, b_n\right)^{\top}=a_1 b_1+a_2 b_2+\cdots+a_n b_n \] 内积运算将两个向量映射为实数，其计算方式非常容易理解，但我们无法看出其物理含义。接下来我们从几何角度 来分析，为了简单起见，我们假设 \(A\) 和 \(B\) 均为二维向量，则： \[ A=\left(x_1, y_1\right), \quad B=\left(x_2, y_2\right) A \cdot B=|A||B| \cos (\alpha) \] 其几何表示见下图：

我们看出 \(A\) 与 \(B\) 的内积等于 \(A\) 到 \(B\) 的投影长度乘以 \(B\) 的模。

如果假设 \(\mathrm{B}\) 的模为 1 ， 即让 \(|B|=1\) ，那么就变成了: \[ A \cdot B=|A| \cos (a) \] 也就是说, A 与 \(B\) 的内积值等于 A 向 \(B\) 所在直线投影的标量大小。

1.2 基

在我们常说的坐标系种, 向量 \((3,2)\) 其实隐式引入了一个定义：以 \(x\) 轴和 \(y\) 轴上正方向长度为 1 的向量为标准。向 量 \((3,2)\) 实际是说在 \(x\) 轴投影为 3 而 \(y\) 轴的投影为 2。注意投影是一个标量, 所以可以为负。

所以, 对于向量 \((3,2)\) 来说, 如果我们想求它在 \((1,0),(0,1)\) 这组基下的坐标的话, 分别内积即可。当然, 内积完 了还是 \((3,2)\) 。

所以, 我们大致可以得到一个结论, 我们要准确描述向量, 首先要确定一组基, 然后给出在基所在的各个直线上的 投影值, 就可以了。为了方便求坐标, 我们希望这组基向量模长为 1。因为向量的内积运算, 当模长为 1 时, 内积 可以直接表示投影。然后还需要这组基是线性无关的, 我们一般用正交基, 非正交的基也是可以的, 不过正交基有 较好的性质。

1.3 基变换的矩阵表示

这里我们先做一个练习：对于向量 \((3,2)\) 这个点来说, 在 \(\left(\frac{1}{\sqrt{2}}, \frac{1}{\sqrt{2}}\right)\) 和 \(\left(-\frac{1}{\sqrt{2}}, \frac{1}{\sqrt{2}}\right)\) 这组基下的坐标是多少? 我们拿 \((3,2)\) 分别与之内积, 得到 \(\left(\frac{5}{\sqrt{2}},-\frac{1}{\sqrt{2}}\right)\) 这个新坐标。

我们可以用矩阵相乘的形式简洁的表示这个变换： \[ \left(\begin{array}{cc} 1 / \sqrt{2} & 1 / \sqrt{2} \\ -1 / \sqrt{2} & 1 / \sqrt{2} \end{array}\right)\left(\begin{array}{l} 3 \\ 2 \end{array}\right)=\left(\begin{array}{c} 5 / \sqrt{2} \\ -1 / \sqrt{2} \end{array}\right) \] 左边矩阵的两行分别为两个基, 乘以原向量, 其结果刚好为新基的坐标。推广一下, 如果我们有 \(m\) 个二维向量, 只要将二维向量按列排成一个两行 \(m\) 列矩阵, 然后用“基矩阵”乘以这个矩阵就可以得到了所有这些向量在新基下 的值。例如对于数据点 \((1,1),(2,2),(3,3)\) 来说, 想变换到刚才那组基上, 则可以这样表示: \[ \left(\begin{array}{cc} 1 / \sqrt{2} & 1 / \sqrt{2} \\ -1 / \sqrt{2} & 1 / \sqrt{2} \end{array}\right)\left(\begin{array}{lll} 1 & 2 & 3 \\ 1 & 2 & 3 \end{array}\right)=\left(\begin{array}{ccc} 2 / \sqrt{2} & 4 / \sqrt{2} & 6 / \sqrt{2} \\ 0 & 0 & 0 \end{array}\right) \] 我们可以把它写成通用的表示形式： \[ \left(\begin{array}{c} p_1 \\ p_2 \\ \vdots \\ p_R \end{array}\right)\left(\begin{array}{llll} a_1 & a_2 & \cdots & a_M \end{array}\right)=\left(\begin{array}{cccc} p_1 a_1 & p_1 a_2 & \cdots & p_1 a_M \\ p_2 a_1 & p_2 a_2 & \cdots & p_2 a_M \\ \vdots & \vdots & \ddots & \vdots \\ p_R a_1 & p_R a_2 & \cdots & p_R a_M \end{array}\right) \] 其中 \(p_i\) 是一个行向量, 表示第 \(\mathrm{i}\) 个基, \(a_j\) 是一个列向量, 表示第 \(\mathrm{j}\) 个原始数据记录。实际上也就是做了一个向 量矩阵化的操作。

上述分析给矩阵相乘找到了一种物理解释: 两个矩阵相乘的意义是将右边矩阵中的每一列向量 \(a_i\) 变换到左边矩阵 中以每一行行向量为基所表示的空间中去。也就是说一个矩阵可以表示一种线性变换。

2. 最大可分性

上面我们讨论了选择不同的基可以对同样一组数据给出不同的表示, 如果基的数量少于向量本身的维数, 则可以达 到降维的效果。

但是我们还没回答一个最关键的问题: 如何选择基才是最优的。或者说, 如果我们有一组 \(\mathbf{N}\) 维向量, 现在要将其 降到 K 维（K 小于 N），那么我们应该如何选择 \(\mathrm{K}\) 个基才能最大程度保留原有的信息？

一种直观的看法是： 希望投影后的投影值尽可能分散, 因为如果重叠就会有样本消失。当然这个也可以从樀的角 度进行理解，樀越大所含信息越多。

2.1 方差

我们知道数值的分散程度, 可以用数学上的方差来表述。一个变量的方差可以看做是每个元素与变量均值的差的平 方和的均值, 即: \[ \operatorname{Var}(a)=\frac{1}{m} \sum_{i=1}^m\left(a_i-\mu\right)^2 \] 为了方便处理，我们将每个变量的均值都化为 0 , 因此方差可以直接用每个元素的平方和除以元素个数表示: \[ \operatorname{Var}(a)=\frac{1}{m} \sum_{i=1}^m a_i^2 \] 于是上面的问题被形式化表述为：寻找一个一维基，使得所有数据变换为这个基上的坐标表示后，方差值最大。

2.2 协方差

在一维空间中我们可以用方差来表示数据的分散程度。而对于高维数据，我们用协方差进行约束，协方差可以表示两个变量的相关性。 为了让两个变量尽可能表示更多的原始信息，我们希望它们之间不存在线性相关性，因为相关性意味着两个变量不是完全独立，必然存在重复表示的信息。

协方差公式为：

\[ \operatorname{Cov}(a, b)=\frac{1}{m-1} \sum_{i=1}^m\left(a_i-\mu_a\right)\left(b_i-\mu_b\right) \]

由于均值为 0，所以我们的协方差公式可以表示为：

\[ \operatorname{Cov}(a, b)=\frac{1}{m} \sum_{i=1}^m a_i b_i \] 当样本数较大时，不必在意其是 m 还是 m-1，为了方便计算，我们分母取 m。

协方差为 0 时，表示两个变量完全不相关。为了让协方差为 0，我们选择第二个基时只能在与第一个基正交的方向上进行选择，因此最终选择的两个方向一定是正交的。

（补充：协方差为 0 时，两个变量只是线性不相关。完全独立是有问题的，才疏学浅，还望见谅。）

至此，我们得到了降维问题的优化目标：将一组 N 维向量降为 K 维，其目标是选择 K 个单位正交基，使得原始数据变换到这组基上后，各变量两两间协方差为 0，而变量方差则尽可能大（在正交的约束下，取最大的 K 个方差）。

2.3 协方差矩阵

针对我们给出的优化目标，接下来我们将从数学的角度来给出优化目标。我们看到，最终要达到的目的与变量内方差及变量间协方差有密切关系。因此我们希望能将两者统一表示，仔细观察发现，两者均可以表示为内积的形式，而内积又与矩阵相乘密切相关。于是我们有：

假设我们只有 \(\mathrm{a}\) 和 \(\mathrm{b}\) 两个变量, 那么我们将它们按行组成矩阵 \(\mathrm{X}\) : \[ X=\left(\begin{array}{cccc} a_1 & a_2 & \cdots & a_m \\ b_1 & b_2 & \cdots & b_m \end{array}\right) \] 然后: \[ \frac{1}{m} X X^{\top}=\left(\begin{array}{cc} \frac{1}{m} \sum_{i=1}^m a_i^2 & \frac{1}{m} \sum_{i=1}^m a_i b_i \\ \frac{1}{m} \sum_{i=1}^m a_i b_i & \frac{1}{m} \sum_{i=1}^m b_i^2 \end{array}\right)=\left(\begin{array}{cc} \operatorname{Cov}(a, a) & \operatorname{Cov}(a, b) \\ \operatorname{Cov}(b, a) & \operatorname{Cov}(b, b) \end{array}\right) \] 我们可以看到这个矩阵对角线上的分别是两个变量的方差, 而其它元素是 \(a\) 和 \(b\) 的协方差。两者被统一到了一个 矩阵里。

设我们有 \(\mathrm{m}\) 个 \(\mathrm{n}\) 维数据记录, 将其排列成矩阵 \(X_{n, m}\), 设 \(C=\frac{1}{m} X X^T\), 则 \(\mathrm{C}\) 是一个对称矩阵, 其对角线分别 对应各个变量的方差, 而第 \(\mathrm{i}\) 行 \(\mathrm{j}\) 列和 \(\mathrm{j}\) 行 \(\mathrm{i}\) 列元素相同, 表示 \(\mathrm{i}\) 和 \(\mathrm{j}\) 两个变量的协方差。

2.4 矩阵对角化

根据我们的优化条件，我们需要将除对角线外的其它元素化为 0，并且在对角线上将元素按大小从上到下排列（变量方差尽可能大），这样我们就达到了优化目的。这样说可能还不是很明晰，我们进一步看下原矩阵与基变换后矩阵协方差矩阵的关系。

设原始数据矩阵 \(X\) 对应的协方差矩阵为 \(C\), 而 \(P\) 是一组基按行组成的矩阵, 设 \(Y=P X\), 则 \(Y\) 为 \(X\) 对 \(P\) 做基变换后的 数据。设 \(Y\) 的协方差矩阵为 \(D\), 我们推导一下 \(D\) 与 \(C\) 的关系: \[ \begin{aligned} D & =\frac{1}{m} Y Y^T \\ & =\frac{1}{m}(P X)(P X)^T \\ & =\frac{1}{m} P X X^T P^T \\ & =P\left(\frac{1}{m} X X^T\right) P^T \\ & =P C P^T \end{aligned} \] 这样我们就看清楚了, 我们要找的 \(\mathrm{P}\) 是能让原始协方差矩阵对角化的 \(\mathrm{P}\) 。换句话说, 优化目标变成了寻找一个矩 阵 \(\mathbf{P}\), 满足 \(P C P^T\) 是一个对角矩阵，并且对角元素按从大到小依次排列，那么 \(\mathbf{P}\) 的前 \(\mathbf{K}\) 行就是要寻找的基, 用 \(\mathbf{P}\) 的前 \(\mathrm{K}\) 行组成的矩阵乘以 \(\mathrm{X}\) 就使得 \(\mathrm{X}\) 从 \(\mathrm{N}\) 维降到了 \(\mathrm{K}\) 维并满足上述优化条件。

至此, 我们离 PCA 还有仅一步之遥, 我们还需要完成对角化。

由上文知道，协方差矩阵 C 是一个是对称矩阵，在线性代数中实对称矩阵有一系列非常好的性质:

1. 实对称矩阵不同特征值对应的特征向量必然正交。
2. 设特征向量 \(\lambda\) 重数为 \(r\), 则必然存在 \(r\) 个线性无关的特征向量对应于 \(\lambda\) ，因此可以将这 \(r\) 个特征向量单位正 交化。

由上面两条可知, 一个 \(\mathrm{n}\) 行 \(\mathrm{n}\) 列的实对称矩阵一定可以找到 \(\mathrm{n}\) 个单位正交特征向量, 设这 \(\mathrm{n}\) 个特征向量为 \(e_1, e_2, \cdots, e_n\), 我们将其按列组成矩阵: \(E=\left(e_1, e_2, \cdots, e_n\right)\) 。

则对协方差矩阵 C 有如下结论: \[ E^T C E=\Lambda=\left(\begin{array}{llll} \lambda_1 & & & \\ & \lambda_2 & & \\ & & \ddots & \\ & & & \lambda_n \end{array}\right) \] 其中 \(\Lambda\) 为对角矩阵, 其对角元素为各特征向量对应的特征值（可能有重复）。到这里, 我们发现我们已经找到了 需要的矩阵 P: \(P=E^{\top}\) 。

\(P\) 是协方差矩阵的特征向量单位化后按行排列出的矩阵，其中每一行都是 \(C\) 的一个特征向量。如果设 \(P\) 按照 \(\Lambda\) 中 特征值的从大到小, 将特征向量从上到下排列, 则用 \(P\) 的前 \(K\) 行组成的矩阵乘以原始数据矩阵 \(X\), 就得到了我们 需要的降维后的数据矩阵 \(Y\) 。

拉格朗日乘子法证明:方差就是协方差矩阵的特征值

2.5 最近重构性-思路

以上的证明思路主要是基于最大可分性的思想，通过一条直线使得样本点投影到该直线上的方差最大。除此之外，我们还可以将其转换为线型回归问题，其目标是求解一个线性函数使得对应直线能够更好地拟合样本点集合。这就使得我们的优化目标从方差最大转化为平方误差最小，因为映射距离越短，丢失的信息也会越小。区别于最大可分性，这是从最近重构性的角度进行论证。

3. 求解步骤

总结一下 PCA 的算法步骤：设有 \(m\) 条 \(n\) 维数据。

3. 将原始数据按列组成 \(\mathbf{n}\) 行 \(\mathbf{m}\) 列矩阵 \(\mathbf{X}\);
4. 将 \(\mathrm{X}\) 的每一行进行零均值化，即减去这一行的均值；【零均值化】【方差、协方差好计算】
5. 求出协方差矩阵 \(C=\frac{1}{m} X X^{\top}\);
6. 求出协方差矩阵的特征值及对应的特征向量;
7. 将特征向量按对应特征值大小从上到下按行排列成矩阵，取前 \(\mathbf{k}\) 行组成矩阵 \(\mathbf{P}\);
8. \(Y=P X\) 即为降维到 \(\mathbf{k}\) 维后的数据。

4. 性质【维度灾难、降噪、过拟合、特征独立】

1. 缓解维度灾难：PCA 算法通过舍去一部分信息之后能使得样本的采样密度增大（因为维数降低了），这是缓解维度灾难的重要手段；
2. 降噪：当数据受到噪声影响时，最小特征值对应的特征向量往往与噪声有关，将它们舍弃能在一定程度上起到降噪的效果；
3. 过拟合：PCA 保留了主要信息，但这个主要信息只是针对训练集的，而且这个主要信息未必是重要信息。有可能舍弃了一些看似无用的信息，但是这些看似无用的信息恰好是重要信息，只是在训练集上没有很大的表现，所以 PCA 也可能加剧了过拟合；
4. 特征独立：PCA 不仅将数据压缩到低维，它也使得降维之后的数据各特征相互独立；

5. 细节

5.1 零均值化

当对训练集进行 PCA 降维时，也需要对验证集、测试集执行同样的降维。而对验证集、测试集执行零均值化操作时，均值必须从训练集计算而来，不能使用验证集或者测试集的中心向量。

其原因也很简单，因为我们的训练集时可观测到的数据，测试集不可观测所以不会知道其均值，而验证集再大部分情况下是在处理完数据后再从训练集中分离出来，一般不会单独处理。如果真的是单独处理了，不能独自求均值的原因是和测试集一样。

另外我们也需要保证一致性，我们拿训练集训练出来的模型用来预测测试集的前提假设就是两者是独立同分布的，如果不能保证一致性的话，会出现 Variance Shift 的问题。

5.2 SVD 的对比

这是两个不同的数学定义。我们先给结论：特征值和特征向量是针对方阵才有的，而对任意形状的矩阵都可以做奇异值分解。

PCA：方阵的特征值分解，对于一个方阵 A。其中，Q 是这个矩阵 A 的特征向量组成的矩阵， \(\Lambda\) 是一个对角矩阵，每一个对角线元素就是一个特征值，里面的特征值是由大到小排列的，这些特征值所对应的特征向量就是描述这个矩阵变化方向（从主要的变化到次要的变化排列)。也就是说矩阵 A 的信息可以由其特征值和特征向量表示。

SVD：矩阵的奇异值分解其实就是对于矩阵 \(\mathrm{A}\) 的协方差矩阵 \(A^T A\) 和 \(A A^T\) 做特征值分解推导出来的: \[ A_{m, n}=U_{m, m} \Lambda_{m, n} V_{n, n}^T \approx U_{m, k} \Lambda_{k, k} V_{k, n}^T \] 其中: \(U，V\) 都是正交矩阵, 有 \(U^T U=I_m, V^T V=I_n\) 。这里的约等于是因为 \(\Lambda\) 中有 \(\mathrm{n}\) 个奇异值, 但是由于排在 后面的很多接近 0, 所以我们可以仅保留比较大的 \(\mathrm{k}\) 个奇异值。 \[ \begin{aligned} & A^T A=\left(U \Lambda V^T\right)^T U \Lambda V^T=V \Lambda^T U^T U \Lambda V^T=V \Lambda^2 V^T \\ & A A^T=U \Lambda V^T\left(U \Lambda V^T\right)^T=U \Lambda V^T V \Lambda^T U^T=U \Lambda^2 U^T \end{aligned} \] 所以, \(V \cup\) 两个矩阵分别是 \(A^T A\) 和 \(A A^T\) 的特征向量, 中间的矩阵对角线的元素是 \(A^T A\) 和 \(A A^T\) 的特征值。我 们也很容易看出 \(\mathrm{A}\) 的奇异值和 \(A^T A\) 的特征值之间的关系。

PCA 需要对协方差矩阵 \(C=\frac{1}{m} X X^T\) 。进行特征值分解; SVD 也是对 \(A^T A\) 进行特征值分解。如果取 \(A=\frac{X^T}{\sqrt{m}}\) 则两者基本等价。所以 PCA 问题可以转换成 SVD 求解。

而实际上 Sklearn 的 PCA 就是用 SVD 进行求解的，原因有以下几点：

1. 当样本维度很高时，协方差矩阵计算太慢；
2. 方阵特征值分解计算效率不高；
3. SVD 除了特征值分解这种求解方式外，还有更高效更准确的迭代求解方式，避免了\(A^T A\)的计算；
4. 其实 PCA 与 SVD 的右奇异向量的压缩效果相同。

参考链接

1. 《机器学习》周志华
2. PCA 的数学原理
3. Singular Value Decomposition (SVD) tutorial
4. 机器学习中的数学（4）——线性判别分析（LDA）, 主成分分析（PCA）
5. 从SVD到PCA——奇妙的数学游戏
6. scikit-learn：降维算法PCA和SVD https://blog.csdn.net/HHG20171226/article/details/102981822

一、线性判别分析（LDA）【监督】

“投影后类内方差最小，类间方差最大”

• https://blog.csdn.net/liuweiyuxiang/article/details/78874106

1.1 概念

线性判别分析（Linear Discriminant Analysis，LDA）是一种经典的降维方法。和主成分分析PCA不考虑样本类别输出的无监督降维技术不同，LDA是一种监督学习的降维技术，数据集的每个样本有类别输出。

LDA分类思想简单总结如下：

1. 多维空间中，数据处理分类问题较为复杂，LDA算法将多维空间中的数据投影到一条直线上，将d维数据转化成1维数据进行处理。
2. 对于训练数据，设法将多维数据投影到一条直线上，同类数据的投影点尽可能接近，异类数据点尽可能远离。
3. 对数据进行分类时，将其投影到同样的这条直线上，再根据投影点的位置来确定样本的类别。

如果用一句话概括LDA思想，即“投影后类内方差最小，类间方差最大”。

假设有红、蓝两类数据，这些数据特征均为二维，如下图所示。我们的目标是将这些数据投影到一维，让每一类相近的数据的投影点尽可能接近，不同类别数据尽可能远，即图中红色和蓝色数据中心之间的距离尽可能大。

从上图直观看出，右图红色数据和蓝色数据在各自的区域来说相对集中，根据数据分布直方图也可看出，所以右图的投影效果好于左图，左图中间直方图部分有明显交集。 以上例子是基于数据是二维的，分类后的投影是一条直线。如果原始数据是多维的，则投影后的分类面是一低维的超平面。

1.2 原理

LDA的原理是，将带上标签的数据（点），通过投影的方法，投影到维度更低的空间中，使得投影后的点，会形成按类别区分，一簇一簇的情况，相同类别的点，将会在投影后的空间中更接近。要说明白LDA，首先得弄明白线性分类器(Linear Classifier)：因为LDA是一种线性分类器。对于K-分类的一个分类问题，会有K个线性函数：

\[ y_k(x)=w_k^T x+w_{k 0} \]

当满足条件：对于所有的j，都有Yk > Yj,的时候，我们就说x属于类别k。对于每一个分类，都有一个公式去算一个分值，在所有的公式得到的分值中，找一个最大的就是所属的分类了。

上式实际上就是一种投影，是将一个高维的点投影到一条高维的直线上，LDA最求的目标是，给出一个标注了类别的数据集，投影到了一条直线之后，能够使得点尽量的按类别区分开，当k=2即二分类问题的时候，如下图所示：

红色的方形的点为0类的原始点、蓝色的方形点为1类的原始点，经过原点的那条线就是投影的直线，从图上可以清楚的看到，红色的点和蓝色的点被原点明显的分开了，这个数据只是随便画的，如果在高维的情况下，看起来会更好一点。下面我来推导一下二分类LDA问题的公式：假设用来区分二分类的直线（投影函数)为： \[ y_k(x)=w_k^T x+w_{k 0} \] 当满足条件：对于所有的j, 都有 \(Y k>Y j\),的时候, 我们就说 \(x\) 属于类别 \(k\) 。对于每一个分类, 都有一个公式去算一个 分值，在所有的公式得到的分值中, 找一个最大的就是所属的分类了。

上式实际上就是一种投影, 是将一个高维的点投影到一条高维的直线上, LDA最求的目标是, 给出一个标注了类别 的数据集, 投影到了一条直线之后, 能够使得点尽量的按类别区分开, 当 \(k=2\) 即二分类问题的时候, 如下图所示:

红色的方形的点为 0 类的原始点、蓝色的方形点为 1 类的原始点，经过原点的那条线就是投影的直线，从图上可以 清楚的看到, 红色的点和蓝色的点被原点明显的分开了, 这个数据只是随便画的, 如果在高维的情况下, 看起来会 更好一点。下面我来推导一下二分类LDA问题的公式：假设用来区分二分类的直线（投影函数)为： \[ y=w^T x \] LDA分类的一个目标是使得不同类别之间的距离越远越好, 同一类别之中的距离越近越好, 所以我们需要定义几 个关键的值。

• 类别的原始中心点为：(Di表示属于类别的点)

\[ m_i=\frac{1}{n_i} \sum_{x \in D_i} x \]

• 类别投影后的中心点为:

\[ \widetilde{m_i}=w^T m_i \]

• 衡量类别i投影后, 类别点之间的分散程度 (方差) 为:

\[ \tilde{s_i}=\sum_{y \in Y_i}\left(y-\tilde{m_i}\right)^2 \]

• 最终我们可以得到一个下面的公式, 表示LDA投影到w后的损失函数:

\[ J(w)=\frac{\left|\widetilde{m_1}-\widetilde{m_2}\right|^2}{\widetilde{s}_1^2+\widetilde{s}_2^2} \]

我们分类的目标是，使得类别内的点距离越近越好（集中），类别间的点越远越好。分母表示每一个类别内的方差之和，方差越大表示一个类别内的点越分散，分子为两个类别各自的中心点的距离的平方，我们最大化J(w)就可以求出最优的w了。想要求出最优的w，可以使用拉格朗日乘子法，但是现在我们得到的J(w)里面，w是不能被单独提出来的，我们就得想办法将w单独提出来。

我们定义一个投影前的各类别分散程度的矩阵，这个矩阵看起来有一点麻烦，其实意思是，如果某一个分类的输入点集Di里面的点距离这个分类的中心店mi越近，则Si里面元素的值就越小，如果分类的点都紧紧地围绕着mi，则Si里面的元素值越更接近0. \[ S_{i}=\sum_{x \in D_{i}}\left(x-m_{i}\right)\left(x-m_{i}\right)^{T} \] 带入 \(\mathrm{Si}\), 将 \(\mathrm{J}(\mathrm{w})\) 分母化为:

\(\tilde{s}_{i}=\sum_{x \in D_{i}}\left(w^{T} x-w^{T} m_{i}\right)^{2}=\sum_{x \in D_{i}} w^{T}\left(x-m_{i}\right)\left(x-m_{i}\right)^{T} w=w^{T} S_{i} w\)

\[{\tilde{S_{1}}}^{2}+{\tilde{S_{2}}}^{2}=w^{T}\left(S_{1}+S_{2}\right) w=w^{T} S_{w} w\]

同样的将 \(\mathrm{J}(\mathrm{w})\) 分子化为: \[ \left|\widetilde{m_{1}}-\widetilde{m_{2}}\right|^{2}=w^{T}\left(m_{1}-m_{2}\right)\left(m_{1}-m_{2}\right)^{T} w=w^{T} S_{B} w \] 这样损失函数可以化成下面的形式: \[ J(w)=\frac{w^{T} S_{B} w}{w^{T} S_{w} w} \] 这样就可以用最喜欢的拉格朗日乘子法了, 但是还有一个问题, 如果分子、分母是都可以取任意值的, 那就会 使得有无穷解, 我们将分母限制为长度为 1, 并作为拉格朗日乘子法的限制条件, 带入得到: \[ \begin{aligned} &c(w)=w^{T} S_{B} w-\lambda\left(w^{T} S_{w} w-1\right) \\ &\Rightarrow \frac{d c}{d w}=2 S_{B} w-2 \lambda S_{w} w=0 \\ &\Rightarrow S_{B} w=\lambda S_{w} w \end{aligned} \] 这样的式子就是一个求特征值的问题了。 对于 \(N(N>2)\) 分类的问题, 我就直接写出下面的结论了: \[ \begin{aligned} &S_{W}=\sum_{i=1}^{c} S_{i} \\ &S_{B}=\sum_{i=1}^{c} n_{i}\left(m_{i}-m\right)\left(m_{i}-m\right)^{T} \\ &S_{B} w_{i}=\lambda S_{w} w_{i} \end{aligned} \] 这同样是一个求特征值的问题，我们求出的第i大的特征向量，就是对应的Wi了。

这里想多谈谈特征值，特征值在纯数学、量子力学、固体力学、计算机等等领域都有广泛的应用，特征值表示的是矩阵的性质，当我们取到矩阵的前N个最大的特征值的时候，我们可以说提取到的矩阵主要的成分（这个和之后的PCA相关，但是不是完全一样的概念）。在机器学习领域，不少的地方都要用到特征值的计算，比如说图像识别、pagerank、LDA、还有之后将会提到的PCA等等。

优缺点

一、t-SNE 高维数据可视化

高维数据可视化之t-SNE算法🌈:https://zhuanlan.zhihu.com/p/57937096

T-SNE算法是用于可视化的算法中效果最好的算法之一，相信大家也对T-SNE算法略有耳闻，本文参考T-SNE作者Laurens van der Maaten给出的源代码自己实现T-SNE算法代码，以此来加深对T-SNE的理解。先简单介绍一下T-SNE算法，T-SNE将数据点变换映射到概率分布上。

1.1 t-SNE数据算法的目的

主要是将数据从高维数据转到低维数据，并在低维空间里也保持其在高维空间里所携带的信息（比如高维空间里有的清晰的分布特征，转到低维度时也依然存在）。

t-SNE将欧氏距离距离转换为条件概率，来表达点与点之间的相似度，再优化两个分布之间的距离-KL散度，从而保证点与点之间的分布概率不变。

1.2 SNE原理

\(S N E\) 是通过仿射变换将数据点映射到相应概率分布上, 主要包括下面两个步骤: 1. 通过在高维空间中构建数据点之间的概率分布 \(P\), 使得相似的数据点有更高的概率被选择, 而 不相似的数据点有较低的概率被选择; 2. 然后在低维空间里重构这些点的概率分布 \(Q\), 使得这两个概率分布尽可能相似。

令输入空间是 \(X \in \mathbb{R}^{n}\), 输出空间为 \(Y \in \mathbb{R}^{t}(t \ll n)\) 。不妨假设含有 \(m\) 个样本数据 \(\left\{x^{(1)}, x^{(2)}, \cdots, x^{(m)}\right\}\), 其中 \(x^{(i)} \in X\), 降维后的数据为 \(\left\{y^{(1)}, y^{(2)}, \cdots, y^{(m)}\right\}, y^{(i)} \in Y\) 。 \(S N E\) 是先将欧几里得距离转化为条件概率来表达点与点之间的相似度, 即首先是计算条件概 率 \(p_{j \mid i}\), 其正比于 \(x^{(i)}\) 和 \(x^{(j)}\) 之间的相似度, \(p_{j \mid i}\) 的计算公式为: \[ p_{j \mid i}=\frac{\exp \left(-\frac{\left\|x^{(i)}-x^{(j)}\right\|^{2}}{2 \sigma_{i}^{2}}\right)}{\sum_{k \neq i} \exp \left(-\frac{\left\|x^{(i)}-x^{(k)}\right\|^{2}}{2 \sigma_{i}^{2}}\right)} \] 在这里引入了一个参数 \(\sigma_{i}\), 对于不同的数据点 \(x^{(i)}\) 取值亦不相同, 因为我们关注的是不同数据 点两两之间的相似度, 故可设置 \(p_{i \mid i}=0\) 。对于低维度下的数据点 \(y^{(i)}\), 通过条件概率 \(q_{j \mid i}\) 来 刻画 \(y^{(i)}\) 与 \(y^{(j)}\) 之间的相似度, \(q_{j \mid i}\) 的计算公式为: \[ q_{j \mid i}=\frac{\exp \left(-\left\|y^{(i)}-y^{(j)}\right\|^{2}\right)}{\sum_{k \neq i} \exp \left(-\left\|y^{(i)}-y^{(k)}\right\|^{2}\right)} \] 同理, 设置 \(q_{i \mid i}=0\) 。 如果降维的效果比较好, 局部特征保留完整, 那么有 \(p_{i \mid j}=q_{i \mid j}\) 成立, 因此通过优化两个分布之 间的 \(K L\) 散度构造出的损失函数为: \[ C\left(y^{(i)}\right)=\sum_{i} K L\left(P_{i} \| Q_{i}\right)=\sum_{i} \sum_{j} p_{j \mid i} \log \frac{p_{j \mid i}}{q_{j \mid i}} \] 这里的 \(P_{i}\) 表示在给定高维数据点 \(x^{(i)}\) 时, 其他所有数据点的条件概率分布; \(Q_{i}\) 则表示在给定 低维数据点 \(y^{(i)}\) 时, 其他所有数据点的条件概率分布。从损失函数可以看出, 当 \(p_{j \mid i}\) 较大 \(q_{j \mid i}\) 较小时, 惩罚较高; 而 \(p_{j \mid i}\) 较小 \(q_{j \mid i}\) 较大时, 惩罚较低。换句话说就是高维空间中两个数据点距 离较近时, 若映射到低维空间后距离较远, 那么将得到一个很高的惩罚; 反之, 高维空间中两个数 据点距离较远时, 若映射到低维空间距离较近, 将得到一个很低的惩罚值。也就是说, \(S N E\) 的 损失函数更关注于局部特征, 而忽视了全局结构。

1.3 目标函数求解

1.4 对称性-SNE

优化 \(K L(P \| Q)\) 的一种替换思路是使用联合概率分布来替换条件概率分布, 即 \(P\) 是高维空间里数据点的联合概 率分布, \(Q\) 是低维空间里数据点的联合概率分布，此时的损失函数为: \[ C\left(y^{(i)}\right)=K L(P \| Q)=\sum_i \sum_j p_{i j} \log \frac{p_{i j}}{q_{i j}} \] 同样的 \(p_{i i}=q_{i i}=0\) ，这种改进下的 \(S N E\) 称为对称 \(S N E\) ，因为它的先验假设为对 \(\forall i\) 有 \(p_{i j}=p_{j i}, q_{i j}=q_{j i}\) 成立，故概率分布可以改写成: \[ p_{i j}=\frac{\exp \left(-\frac{\left\|x^{(i)}-x^{(j)}\right\|^2}{2 \sigma^2}\right)}{\sum_{k \neq l} \exp \left(-\frac{\left\|x^{(k)}-x^{(l)}\right\|^2}{2 \sigma^2}\right)} \quad q_{i j}=\frac{\exp \left(-\left\|y^{(i)}-y^{(j)}\right\|^2\right)}{\sum_{k \neq l} \exp \left(-\left\|y^{(k)}-y^{(l)}\right\|^2\right)} \] 这种改进方法使得表达式简洁很多, 但是容易受到异常点数据的影响, 为了解决这个问题通过对联合概率分布定义修正为： \(p_{i j}=\frac{p_{j \mid i}+p_{i \mid j}}{2}\), 这保证了 \(\sum_j p_{i j}>\frac{1}{2 m}\) ，使得每个点对于损失函数都会有贡献。对称 \(S N E\) 最大的 优点是简化了梯度计算, 梯度公式改写为: \[ \frac{\partial C\left(y^{(i)}\right)}{\partial y^{(i)}}=4 \sum_j\left(p_{i j}-q_{i j}\right)\left(y^{(i)}-y^{(j)}\right) \] 研究表明, 对称 \(S N E\) 和 \(S N E\) 的效果差不多, 有时甚至更好一点。

1.5 t-SNE

\(t-S N E\) 在对称 \(S N E\) 的改进是, 首先通过在高维空间中使用高斯分布将距离转换为概率分布，然后在低维空间 中，使用更加偏重长尾分布的方式来将距离转换为概率分布，使得高维度空间中的中低等距离在映射后能够有一个 较大的距离。

从图中可以看到，在没有异常点时, \(t\) 分布与高斯分布的拟合结果基本一致。而在第二张图中, 出现了部分异常点, 由于高斯分布的尾部较低, 对异常点比较敏感, 为了照顾这些异常点, 高斯分布的拟合结果偏离了大多数样本所在位置, 方差也较大。相比之下, \(t\) 分布的尾部较高, 对异常点不敏感, 保证了其鲁棒性, 因此拟合结果更为合理, 较好的捕获了数据的全局特征。

使用 \(t\) 分布替换高斯分布之后 \(q_{i j}\) 的变化如下: \[ q_{i j}=\frac{\left(1+\left\|y^{(i)}-y^{(j)}\right\|^2\right)^{-1}}{\sum_{k \neq l}\left(1+\left\|y^{(i)}-y^{(j)}\right\|^2\right)^{-1}} \] 此外，随着自由度的逐渐增大, \(t\) 分布的密度函数逐渐接近标准正态分布，因此在计算梯度方面会简单很多, 优 化后的梯度公式如下: \[ \frac{\partial C\left(y^{(i)}\right)}{\partial y^{(i)}}=4 \sum_j\left(p_{i j}-q_{i j}\right)\left(y^{(i)}-y^{(j)}\right)\left(1+\left\|y^{(i)}-y^{(j)}\right\|^2\right)^{-1} \] 总的来说, \(t-S N E\) 的梯度更新具有以下两个优势： - 对于低维空间中不相似的数据点，用一个较小的距离会产生较大的梯度让这些数据点排斥开来; - 这种排斥又不会无限大，因此避免了不相似的数据点距离太远。

\(t-S N E\) 算法其实就是在 \(S N E\) 算法的基础上增加了两个改进:

• 把 \(S N E\) 修正为对称 \(S N E\) ，提高了计算效率, 效果稍有提升;
• 在低维空间中采用了 \(t\) 分布替换原来的高斯分布，解决了高维空间映射到低维空间所产生的拥挤问题, 优化 了 \(S N E\) 过于关注局部特征而忽略全局特征的问题。

AutoEncoder

• 【全】一文带你了解自编码器（AutoEncoder）

理解为：（下图）高维数据（左测蓝色）通过某种网络变成低位数据（中间红色）后，又经过某种网络变回高维数据（右侧蓝色）。数据经过该模型前后没有变化，而中间的低维数据完全具有输入输出的高维数据的全部信息，所以可以用低维数据代表高维数据。

之所以叫AutoEncoder，而不叫AutoEncoderDecoder，是因为训练好之后只有encoder部分有用，decoder部分就不用了。

进入深度学习的思路之后，编码的网络是开放的，可以自由设计的。一个思路是端到端，将网络的输出设为你任务要的结果（如类别、序列等），过程中的某层嵌入都可以作为降维的低维结果。当然，这种低维结果其实是模型的副产品，因为任务已经解决。比如bert模型得到（中文的）字嵌入。

优点：

• 能够学习到非线性特性
• 降低数据维度

缺点：

• 训练的计算成本高
• 可解释性较差
• 背后的数学知识复杂
• 容易产生过度拟合的问题，尽管可以通过引入正则化策略缓解

机器学习优化方法 (Optimization)

机器学习与优化基础（Machine Learning and Optimization）:https://zhuanlan.zhihu.com/p/169835477

最优化方法复习笔记：https://github.com/LSTM-Kirigaya/OptimizeNote

FreeWill：机器学习算法系列（25）：最速下降法、牛顿法、拟牛顿法

一、什么是凸优化

凸函数的严格定义为, 函数 \(L(\cdot)\) 是凸函数当且仅当对定义域中的任意两点 \(x, y\) 和任意实数 \(\lambda \in[0,1]\) 总有: \[ L(\lambda x+(1-\lambda) y) \leq \lambda L(x)+(1-\lambda) L(y) \] 该不等式的一个直观解释是, 凸函数曲面上任意两点连接而成的线段, 其上的任 意一点都不会处于该函数曲面的 下方，如下图所示所示。

该不等式的一个直观解释是，凸函数曲面上任意两点连接而成的线段，其上的任 意一点都不会处于该函数曲面的下方，如下图所示所示。

凸优化问题的例子包括支持向量机、线性回归等 线性模型，非凸优化问题的例子包括低秩模型（如矩阵分解）、深度神经网络模型等。

二、正则化项

使用正则化项，也就是给loss function加上一个参数项，正则化项有L1正则化、L2正则化、ElasticNet。加入这个正则化项好处：

• 控制参数幅度，不让模型“无法无天”。
• 限制参数搜索空间
• 解决欠拟合与过拟合的问题。

三、常见的几种最优化方法

下面以线性模型损失函数为例：

3.1 梯度下降法

梯度下降法是最早最简单，也是最为常用的最优化方法。梯度下降法实现简单，当目标函数是凸函数时，梯度下降法的解是全局解。一般情况下，其解不保证是全局最优解，梯度下降法的速度也未必是最快的。 \[ \begin{gathered}\frac{\partial}{\partial \theta_j} J(\theta)=\frac{\partial}{\partial \theta_j} \frac{1}{2}\left(h_\theta(x)-y\right)^2 \\ =2 \cdot \frac{1}{2}\left(h_\theta(x)-y\right) \frac{\partial}{\partial \theta_j}\left(h_\theta(x)-y\right) \\ =\left(h_\theta(x)-y\right) x_j\end{gathered} \] 梯度下降法的优化思想是用当前位置负梯度方向作为搜索方向，因为该方向为当前位置的最快下降方向，所以也被称为是”最速下降法“。最速下降法越接近目标值，步长越小，前进越慢。梯度下降法的搜索迭代示意图如下图所示：

• 批量梯度下降法（BGD）

参数θ的值每更新一次都要遍历样本集中的所有的样本，得到新的θj，看是否满足阈值要求，若满足，则迭代结束，根据此值就可以得到；否则继续迭代。【易受极小值影响】

• 随机梯度下降算法（SGD）【单样本增量梯度下降】

每次更新只用到一个训练样本，若根据当前严格不能进行迭代得到一个，此时会得到一个，有新样本进来之后，在此基础上继续迭代，又得到一组新的和，以此类推。

缺点：靠近极小值时收敛速度减慢；直线搜索时可能会产生一些问题；可能会“之字形”地下降。

3.2 牛顿法

牛顿法是一种在实数域和复数域上近似求解方程的方法。方法使用函数 \(\mathrm{f}(\mathrm{x})\) 的泰勒级数的前面几项来寻找方程 \((x)=0\) 的根。牛顿法最大的特点就在于它的收敛速度很快。具体步骤：

• 首先, 选择一个接近函数 \(f(x)\) 零点的 \(x 0\), 计算相应的 \(f(x 0)\) 和切线斜率 \(f^{\prime}(x 0)\) (这里 \(f^{\prime}\) 表示函数 \(f\) 的导 数)
• 然后我们计算穿过点 \((x 0, f(x 0))\) 并且斜率为 \(f^{\prime}(x 0)\) 的直线和 \(x\) 轴的交点的 \(x\) 坐标, 也就是求如下方程的解: \(x * f^{\prime}\left(x_0\right)+f\left(x_0\right)-x_0 * f^{\prime}\left(x_0\right)=0\)
• 我们将新求得的点的 \(x\) 坐标命名为 \(x 1\), 通常 \(x 1\) 会比 \(x 0\) 更接近方程 \(f(x)=0\) 的解。因此我们现在可以利用 \(x 1\) 开始下一轮迭代。

由于牛顿法是基于当前位置的切线来确定下一次的位置，所以牛顿法又被很形象地称为是"切线法"。牛顿法搜索动态示例图：

从本质上去看，牛顿法是二阶收敛，梯度下降是一阶收敛，所以牛顿法就更快。缺点：

• 牛顿法是一种迭代算法，每一步都需要求解目标函数的Hessian矩阵的逆矩阵，计算比较复杂。
  • 在高维情况下这个矩阵非常大，计算和存储都是问题。
• 在小批量的情况下，牛顿法对于二阶导数的估计噪声太大。
  • 目标函数非凸的时候，牛顿法容易受到鞍点或者最大值点的吸引。

3.3 拟牛顿法

拟牛顿法是求解非线性优化问题最有效的方法之一，本质思想是改善牛顿法每次需要求解复杂的Hessian矩阵的逆矩阵的缺陷，它使用正定矩阵来近似Hessian矩阵的逆，从而简化了运算的复杂度。拟牛顿法和梯度下降法一样只要求每一步迭代时知道目标函数的梯度。通过测量梯度的变化，构造一个目标函数的模型使之足以产生超线性收敛性。这类方法大大优于梯度下降法，尤其对于困难的问题。另外，因为拟牛顿法不需要二阶导数的信息，所以有时比牛顿法更为有效。如今，优化软件中包含了大量的拟牛顿算法用来解决无约束，约束，和大规模的优化问题。

DFP、BFGS、L-BFGS:

3.4 共轭梯度法

共轭梯度法是介于梯度下降法与牛顿法之间的一个方法，它仅需利用一阶导数信息，但克服了梯度下降法收敛慢的缺点，又避免了牛顿法需要存储和计算Hesse矩阵并求逆的缺点，共轭梯度法不仅是解决大型线性方程组最有用的方法之一，也是解大型非线性最优化最有效的算法之一。 在各种优化算法中，共轭梯度法是非常重要的一种。其优点是所需存储量小，具有步收敛性，稳定性高，而且不需要任何外来参数。

具体的实现步骤请参加wiki百科共轭梯度法。下图为共轭梯度法和梯度下降法搜索最优解的路径对比示意图：