从2015年11月左右开始写订阅号的文章，至今也有大半年的时光了。其中得到了很多朋友的帮助和建议，也有朋友在后台留言，在此感谢大家。不过在看到一些问题的时候，有一些想法，在此写出来和大家一起分享。

PS：自己踏入社会也没多长的时间，可能其中也会有一些偏见，希望大家多多指教。

1. 范例思维

在写《博士生涯》系列文章的时候，有的朋友会在后台留言咨询这类问题：“在NUS读完PHD之后能否去美国或者欧洲做博士后？能否回国去985，211高校？”

关于这一类的问题，可能和大家在中学，大学所受到的教育有关系。在中学的时候，大家只有一个目标，那就是高考，所有事情和所有人都必须围绕着这件事情转，沿着这条路走下去。但是到了大学之后，就会明显的发现身边的同学不再只围绕着学习这一件事情，比方说有很多同学会去参加社团活动，有不少同学会去做社会实践，当然也有一批同学依旧以学习为主业，持续着中学的生活。其实，这几种生活方式都是可以接受的，毕竟在18岁之后，很多事情就需要自己亲自做决定。这个时候就会带来一个问题，如果学生明确知道自己想做什么事情，那就不会产生迷茫，肯定就一股脑的做下去了。但是，很多学生是不清楚自己该做什么，不该做什么的。那么在大学里面就会有老师，辅导员甚至学长学姐来给大家提供经验，告诉大家应该做什么，只有做什么能够带来最大的收益。

到了国外攻读博士学位的阶段，这种环境就会产生巨大的变化。不再有老师的就业辅导，不再有辅导员这个职位，甚至没有学长学姐的经验总结。用常见的话说就是：一切皆有可能。比如，在NUS读PHD的过程中，自己亲眼见过自己的朋友遇到过各种各样的悲剧。有的是导师辞职离开学校，把学生留在学校不闻不问的；有的是即使导师在学校，也对学生的科研不关心的；有的是拖着学生长期不给毕业的。身边的朋友也做过各种各样的选择，包括读博期间换导师的，转专业的，甚至退学的。至于毕业的去向，不仅有去欧美做博士后的，有去大学做助理教授的，也有去投行的，甚至有去互联网公司的。每个人都有着自己的生活，除了特别亲密的朋友，你不再会去关心别人做什么样的工作，过什么样的生活了。每个人根据自己的情况，走着完全不同的路，根本就没有模板一样的人可以模仿。每个人都需要为自己的选择负责，为自己的未来做着准备。

2. 线性思维

还有一些经常碰到的问题就是：“在NUS读完PHD，能够去投行工作吗？”，“在读博士期间需要去考CFA吗？”，“博士毕业工资能够拿多少？”，“这个硕士生或者博士生的项目竞争力如何，值得去读么？”

这些就是典型的线性思维，就是做了事件A，必然会导致事件B的发生。在现实生活中，人的发展不仅要考虑自身的情况，还需要考虑历史的进程。也就是说，很多时候并不是因果关系而是某种相关性导致了事件的发生。首先，读PHD，没有人能够保证博士生一定能毕业。其次，学生也不知道自己要读几年才能够毕业，只能够根据师兄师姐的毕业年限计算一个期望值。再次，导师给学生的推荐信质量也是不同的，师兄能够去985，说不定由于导师不喜欢某学生导致该学生只能够去二本教书，即使这个学生的论文发的水平远远高于师兄。并且跟一些厉害老板的学生的出路也不见得比一些普通老板的学生出路好。最后，能不能够去投行，能拿到多少工资基本上都是因人而异。曾经见过纯数学的同学去投行做quant，去互联网公司写代码，做着和博士论文基本上没有关系的工作。真正厉害的人，不在于多读了一个学位或者考了一个CFA，而在于那些让他们厉害的背后因素，一些其他人根本不具备的素质，比如性格，意志力等。

3. 学生思维

之前某天写过一篇转行的文章，有人在后台留言：“这些技术能不能进了企业再开始学？”，“转行到底要花多少时间？”，“在公司有没有人带着干活？”

在学校的时候，无论是本科，硕士，还是博士阶段，学生都可以告诉老师，虽然我不会，但是我愿意学。但是按照普通企业的招聘标准，一般都是观察这个人能否胜任该岗位的需求（或者说有潜力胜任这个岗位），而不是看这个人愿不愿意学。在企业工作，是需要时刻有产出的，无论是成功的项目还是失败的项目，都需要给出一个交代。企业是一个商业机构，需要员工有产出，然后从中获取利润的，而不是像学校一样的培训机构。

至于转行的时间肯定是因人而异的，不同的人有着不同的思维方式，不同的知识结构，所能够做的事情也会有所不同。不过如果想好了要转行的话，早准备肯定胜过不准备。还有的人会问如何快速的学习HIVE，C++之类的，这一类问题实在是不知道怎么回答。不过如果有一个人问我，如何在十天内快速学会实变函数，我一定会告诉他这是一件不可能的事情。

刚进公司的时候，一般来说会企业都会指定一位导师，给新人划定工作的范围，甚至有明确的deadline，看上去其实和学生时代没有什么两样。但是如果只是抱着完成任务的心态来工作，那这个项目基本上就完蛋了。上级一般来说会希望员工主动去思考一些问题，主动做一些事情，甚至有一个较为长远的规划。做这些事情都是希望员工能够成长起来，能够在工作中独当一面，能够和别的团队甚至和其它公司竞争。在学校中，一般来说老师都会主动教学生很多知识，希望学生学会这些技能。但是在工作中，有人主动传授知识和技能，绝对一种可遇而不可求的事情，很多技能都需要自己主动地去学习。别人出于援手帮助是由于他们的好心，如果没有出手也不必苛责。每个人在公司里面都有着做不完的业务，忙不完的事情，实在是没有多余的时间去指导其他人。既然在别人都可以自学成才，为何不自己动手主动学习，丰衣足食？在大多数情况下，一定要放弃“老师教才会学”的学习方法，企业雇佣一个人是用来产生价值的，而不是不是消耗公司资源的。

4. 不独立的思维

在学校的生活中，除了读PHD期间课题的未知性，在中学，本科，硕士的作业甚至论文几乎都有标准答案，考试也有规定的范围。在学生生涯中，除了读博士阶段，一般来说老师都会告诉学生该怎么做，不该怎么做。但是到了工作中，处处都是未知，每一天都是一种“考试”，没有固定的答案可以参考，没有现成的模版可以参考。学生思维的人一般都会以一种被动的方式去接受任务并完成任务，当然这并没有错。不过以职场的角度来说，这样就会处于一种非常被动的方式，一般都会在做一些繁重而没有多少技术含量的任务。在职场混，不但要学习，还需要主动给业务方甚至自己的团队出谋划策，想各种方案应对当前的问题。

在实际工作中，不仅需要提升自己的技能点，亲自动手做调研的工作，还需要学会和业务方沟通，想办法从其它地方获取资源供自己调用，甚至知道如何管理项目。如果独立负责一个小项目的话，不仅需要自己把控项目的进度，积极反馈产品的不足之处，还要推动项目其余成员去做该做的事情，一起把项目做好做大。在项目的进展中，不仅需要把具体的任务落实到每一个人身上，还需要实时地与大家沟通，了解项目的困难点和关键时间点，更好的完成项目。

前面一篇文章《异常点检测算法（一）》简要的介绍了如何使用概率统计的方法来计算异常点，本文将会介绍一种基于矩阵分解的异常点检测方法。在介绍这种方法之前，先回顾一下主成分分析（Principle Component Analysis）这一基本的降维方法。

（一）主成分分析（Principle Component Analysis）

对高维数据集合的简化有各种各样的原因，例如：

（1）使得数据集合更容易使用；

（2）降低很多算法的计算开销；

（3）去除噪声；

（4）更加容易的描述结果。

在主成分分析（PCA）这种降维方法中，数据从原来的坐标系转换到新的坐标系，新坐标系的选择是由数据集本身所决定的。第一个新坐标轴的方向选择的是原始数据集中方差最大的方向，第二个新坐标轴的选择是和第一个坐标轴正交并且具有最大方差的方向。该过程一直重复，重复的次数就是原始数据中特征的数目。如此操作下去，将会发现，大部分方差都包含在最前面的几个新坐标轴之中。因此，我们可以忽略余下的坐标轴，也就是对数据进行了降维的处理。

为了提取到第一个主成分（数据差异性最大）的方向，进而提取到第二个主成分（数据差异性次大）的方向，并且该方向需要和第一个主成分方向正交，那么我们就需要对数据集的协方差矩阵进行特征值的分析，从而获得这些主成分的方向。一旦我们计算出了协方差矩阵的特征向量，我们就可以保留最大的 N 个值。正是这 N 个值反映了 N 个最重要特征的真实信息，可以把原始数据集合映射到 N 维的低维空间。

提取 N 个主成分的伪代码如下：

去除平均值

计算协方差矩阵

计算协方差矩阵的特征值和特征向量

将特征值从大到小排序

保留最大的N个特征值以及它们的特征向量

将数据映射到上述N个特征向量构造的新空间中

通过 Python 的 numpy 库和 matplotlib 库可以计算出某个二维数据集合的第一主成分如下：原始数据集使用蓝色的三角形表示，第一主成分使用黄色的圆点表示。

Principle Component Analysis 的基本性质：

Principle component analysis provides a set of eigenvectors satisfying the following properties:

（1）If the top-k eigenvectors are picked (by largest eigenvalue), then the k-dimensional hyperplane defined by these eigenvectors, and passing through the mean of the data, is a plane for which the mean square distance of all data points to it is as small as possible among all hyperplanes of dimensionality k.

（2）If the data is transformed to the axis-system corresponding to the orthogonal eigenvectors, the variance of the transformed data along each eigenvector dimension is equal to the corresponding eigenvalue. The covariances of the transformed data in this new representation are 0.

（3）Since the variances of the transformed data along the eigenvectors with small eigenvalues are low, significant deviations of the transformed data from the mean values along these directions may represent outliers.

（二）基于矩阵分解的异常点检测方法

基于矩阵分解的异常点检测方法的关键思想是利用主成分分析去寻找那些违背了数据之间相关性的异常点。为了发现这些异常点，基于主成分分析（PCA）的算法会把原始数据从原始的空间投影到主成分空间，然后再把投影拉回到原始的空间。如果只使用第一主成分来进行投影和重构，对于大多数的数据而言，重构之后的误差是小的；但是对于异常点而言，重构之后的误差依然相对大。这是因为第一主成分反映了正常值的方差，最后一个主成分反映了异常点的方差。

假设 dataMat 是一个 p 维的数据集合，有 N 个样本，它的协方差矩阵是 X。那么协方差矩阵就通过奇异值分解写成：

其中 P 是一个 (p,p) 维的正交矩阵，它的每一列都是 X 的特征向量。D 是一个 (p,p) 维的对角矩阵，包含了特征值 。从图像上看，一个特征向量可以看成 2 维平面上面的一条线，或者高维空间里面的一个超平面。特征向量所对应的特征值反映了这批数据在这个方向上的拉伸程度。通常情况下，可以把对角矩阵 D 中的特征值进行从大到小的排序，矩阵 P 的每一列也进行相应的调整，保证 P 的第 i 列对应的是 D 的第 i 个对角值。

这个数据集 dataMat 在主成分空间的投影可以写成

需要注意的是做投影可以只在部分的维度上进行，如果使用 top-j 的主成分的话，那么投影之后的数据集是

其中 是矩阵 P 的前 j 列，也就是说 是一个 (p,j) 维的矩阵， 是一个 (N,j) 维的矩阵。如果考虑拉回映射的话（也就是从主成分空间映射到原始空间），重构之后的数据集合是

其中 是使用 top-j 的主成分进行重构之后形成的数据集，是一个 (N,p) 维的矩阵。

下面可以定义数据 的异常值分数（outlier score）如下：

注意到 指的是 Euclidean 范数， ev(j) 表示的是 top-j 的主成分在所有主成分中所占的比例，并且特征值是按照从大到小的顺序排列的。因此，ev(j) 是递增的序列，这就表示 j 越高，越多的方差就会被考虑在 ev(j) 中，因为是从 1 到 j 的求和。在这个定义下，偏差最大的第一个主成分获得最小的权重，偏差最小的最后一个主成分获得了最大的权重 1。根据 PCA 的性质，异常点在最后一个主成分上有着较大的偏差，因此可以获得更高的分数。

整个算法的结构如图所示：

（三）效果展示

下面两幅图使用了同一批数据集，分别采用了基于矩阵分解的异常点检测算法和基于高斯分布的概率模型的异常点算法。

基于矩阵分解的异常点检测

基于高斯分布的概率模型的异常点检测

根据图像可以看出，如果使用基于矩阵分解的异常点检测算法的话，偏离第一主成分较多的点都被标记为异常点，其中包括部分左下角的点。需要注意的是如果使用基于高斯分布的概率模型的话，是不太可能标记出左下角的点的，两者形成鲜明对比。

异常点检测（又称为离群点检测）是找出其行为很不同于预期对象的一个检测过程。这些对象被称为异常点或者离群点。异常点检测在很多实际的生产生活中都有着具体的应用，比如信用卡欺诈，工业损毁检测，图像检测等。

异常点（outlier）是一个数据对象，它明显不同于其他的数据对象，就好像它是被不同的机制产生的一样。例如下图红色的点，就明显区别于蓝色的点。相对于蓝色的点而言，红色的点就是异常点。

一般来说，进行异常点检测的方法有很多，最常见的就是基于统计学的方法。

（一）基于正态分布的一元离群点检测方法

假设有 n 个点 ，那么可以计算出这 n 个点的均值 和方差 。均值和方差分别被定义为：

在正态分布的假设下，区域 包含了99.7% 的数据，如果某个值距离分布的均值 超过了 ，那么这个值就可以被简单的标记为一个异常点（outlier）。

（二）多元离群点的检测方法

涉及两个或者两个以上变量的数据称为多元数据，很多一元离群点的检测方法都可以扩展到高维空间中，从而处理多元数据。

（1）基于一元正态分布的离群点检测方法

假设 n 维的数据集合形如 ，那么可以计算每个维度的均值和方差 具体来说，对于 ，可以计算

在正态分布的假设下，如果有一个新的数据 ，可以计算概率 如下：

根据概率值的大小就可以判断 x 是否属于异常值。运用该方法检测到的异常点如图，红色标记为异常点，蓝色表示原始的数据点。

（2）多元高斯分布的异常点检测

假设 n 维的数据集合 ，可以计算 n 维的均值向量

和 的协方差矩阵：

如果有一个新的数据 ，可以计算

根据概率值的大小就可以判断 是否属于异常值。

（3）使用 Mahalanobis 距离检测多元离群点

对于一个多维的数据集合 D，假设 是均值向量，那么对于数据集 D 中的其他对象 ，从 到 的 Mahalanobis 距离是

其中 是协方差矩阵。

在这里， 是数值，可以对这个数值进行排序，如果数值过大，那么就可以认为点 是离群点。或者对一元实数集合 进行离群点检测，如果 被检测为异常点，那么就认为 在多维的数据集合 D 中就是离群点。

运用 Mahalanobis 距离方法检测到的异常点如图，红色标记为异常点，蓝色表示原始的数据点。

（4）使用 统计量检测多元离群点

在正态分布的假设下， 统计量可以用来检测多元离群点。对于某个对象 ， 统计量是

其中， 是 在第 i 维上的取值， 是所有对象在第 i 维的均值，n 是维度。如果对象 的 统计量很大，那么该对象就可以认为是离群点。

运用  统计量检测到的异常点如图，红色标记为异常点，蓝色表示原始的数据点。

异常值检测算法在数据挖掘的诸多领域有着应用场景，例如金融领域，信息传输领域，图像领域等。在研究过程中，有学者给出了异常点的一个定义：

An outlier is an observation that deviates so much from other observations as as to arouse suspicion that it was generated by a different mechanism.

RNN 算法的主要思想

在这篇文章中，我们将会介绍一个多层的前馈神经网络，该神经网络可以用来进行异常值的检测。这个神经网络模拟的是一个恒等映射，输入层的神经元个数和输出层的神经元个数是一样的。这类的神经网络被称为 Replicator Neural Networks (RNNs)，请注意这里的 RNN 算法指的并不是 Recurrent Neural Networks（RNNs），而是 Replicator Neural Networks，尽管它们拥有着同样的缩写名字 RNNs。具体来说， Replicator Neural Networks (RNNs)，或者说自编码器，是一个多层前馈的神经网络 (multi-layer feed-forward neural networks)。在 Replicator Neural Networks 中，输入的变量也是输出的变量，模型中间层节点的个数少于输入层和输出层节点的个数。这样的话，模型就起到了压缩数据和恢复数据的作用。

如图所示，这里的 RNNs 有三个隐藏层，输入层和输出层的节点个数都是6，第一个隐藏层和第三个隐藏层的节点个数（图中是4个节点）少于输入层，第二个隐藏层的节点个数是最少的（图中是2个节点）。在神经网络传输的时候，中间使用了 tanh 函数和 sigmoid 函数。这个神经网络是训练一个从输入层到输出层的恒等函数（identity mapping），传输的时候从输入层开始压缩数据，然后到了第二个隐藏层的时候开始解压数据。训练的目标就是使得整体的输出误差足够小，整体的误差是由所有的样本误差之和除以样本的个数得到的。由于图中只画出了6个特征，因此第 i 个样本的误差是

如果使用已经训练好的 RNN 模型，异常值的分数就可以定义为重构误差（reconstruction error）。

下面简要介绍一下 RNN 模型是如何构建的：

根据上图所示，左边的是输入层，右边的输出层。假设第 k 层中第 i 个神经元的输出是 ，其中 表示第 k 层中第 i 个神经元的输入， 表示第 k 层使用的激活函数。那么

其中 是第 k 层中第 j 个神经元的输出， 是第 k 层神经元的个数。对于第二层和第四层而言 (k=2,4)，激活函数选择为

这里的 是一个参数，通常假设为1。对于中间层 (k=3) 而言，激活函数是一个类阶梯 (step-like) 函数。有两个参数 N 和 ，N 表示阶梯的个数， 表示从这一层到下一层的提升率 (transition rate)：

+.

在这里可以假设 ，. 那么 就如下图所示。

第三层的激活函数的输出就变成了 N 个离散的变量：0, 1/(N-1), 2/(N-1),…,1。这个阶梯型的激活函数是把第三层的连续输入值变成了一批离散的值。也就意味着把样本映射到了 N 个簇，那么 RNN 就可以计算出单个的异常点和一小簇的异常点。

备注：

根据上面的分析，可以看出如果按照以上算法，则不能使用反向传播算法来训练模型，原因是 的导数不能够通过它的取值来表示。这一点与 tanh 函数， 函数是不一致的，因为 和 。因此有学者指出 [1]，使用三个隐藏层是没有必要的，使用1个或者2个隐藏层的神经网络也能够得到类似的结果；同样，没有必要使用 这样类型的阶梯函数，使用传统的 激活函数也能够得到类似的结果。并且 是一个 step-like 函数，很多地方的导数取值都是接近于零的。

后向传播算法：

一般来说，为了训练神经网络模型，需要使用后向传播算法（back propagation），也简称为 BP 算法，或者误差逆传播算法（error back propagation）。在本文中，仅针对最简单的 RNN 模型介绍如何使用 BP 算法进行模型训练，至于多层的神经网络模型或者其他的神经网络模型，方法则是完全类似的。

给定训练集合 ，其中有 m 个样本，并且输入和输出是一样的值。换句话说，也就是 n 维向量

.

换句话说，输入样例是由 n 个属性描述，输出的结果也是 n 个属性。隐藏层只有一个，隐藏层的神经元个数是 ，这里的 [] 表示 Gauss 取整函数。输出层第 j 个神经元的阈值使用 表示，隐藏层第 h 个神经元的阈值使用 表示。输入层第 i 个神经元与隐藏层第 h 个神经元之间的连接权重是 , 隐藏层第 h 个神经元与输出层第 j 个神经元之间的连接权重是 其中

记隐藏层第 h 个神经元接收到的输入为

写成矩阵形式就是：

记输出层第 j 个神经元接收到的输入为

其中 是隐藏层第 h 个神经元的输出， 是激活函数。写成矩阵形式就是：

输出层第 j 个神经元的输出是 其中

下面可以假定激活函数都使用 那么直接通过导数计算可以得到

对于训练集 通过神经网络得到的输出是 并且 对于 都成立。那么神经网络在训练集 的均方误差是

其中 整体的误差是

标准 BP 算法：

网络中有 个参数需要确定：输入层到隐藏层的 n*q 个权重值，隐藏层到输出层的 n*q 个权重值，q个隐层神经元的阈值，n 个输出层神经元的阈值。BP 算法是一个迭代学习算法，在迭代的每一轮采用了梯度下降法来进行参数的更新。任意参数的更新规则是

+

标准 BP 算法是根据每一个 来获得更新规则，下面来推导每一个参数的更新规则。对于 计算梯度

注意到 先影响到第 j 个输出层神经元的输入值 再影响到第 j 个输出层神经元的输出值 ，最后影响到 ，根据高等数学的链式法则可以得到

根据定义 可以得到 对于 都成立。

根据定义 可以得到 .

根据定义 和 可以得到

所以可以计算出对于 有

如果假设

那么可以得到

因此对于 可以得到

根据类似的想法，有

.

逐个计算：

由于

所以，

其中

整理之后，任意参数 v 的更新式子是 + 并且更新的规则如下：

其中学习率 控制着算法每一轮迭代中的更新步长，若步长太大则容易振荡，太小则收敛速度过慢，需要人工调整学习率。 对每个训练样例，BP 算法执行下面的步骤：先把输入样例提供给输入层神经元，然后逐层将信号往前传，直到计算出输出层的结果；然后根据输出层的误差，再将误差逆向传播至隐藏层的神经元，根据隐藏层的神经元误差来对连接权和阈值进行迭代（梯度下降法）。该迭代过程循环进行，直到达到某个停止条件为止。

标准 BP 算法的训练流程：
输入：训练集合 和学习率
过程：
1. 在 (0,1) 范围内随机神经网络中的所有连接权重和阈值
2. repeat
for all do
根据当前参数，计算出当前的样本输出
计算输出层神经元的梯度项
计算隐藏层神经元的梯度项
更新连接权重 与阈值
end for
3. 达到停止条件
输出：链接权与阈值都确定的神经网络模型

累积 BP 算法：

BP 算法的目的是最小化训练集上的累计误差 其中 m 是训练集合中样本的个数。不过，标准的 BP 算法每次仅针对一个训练样例更新连接权重和阈值，也就是说，标准 BP 算法的更新规则是基于单个的 推导而得到的。通过类似的计算方法可以推导出累计误差的最小化更新规则，那就得到了累计误差逆传播（accumulate error backpropagation）算法。标准 BP 算法需要进行更多次的迭代，并且参数的更新速度快，累积 BP 算法必须扫描一次训练集合才会进行一次参数的更新，而且累计误差下降到一定的程度以后 ，进一步下降就会明显变慢，此时标准 BP 算法往往会更快的得到较好的解，尤其是训练集合大的时候。

训练方法：

（1）把数据集合的每一列都进行归一化；

（2）选择 70% 的数据集合作为训练集合，30% 的数据集合作为验证集合。或者 训练集合 : 验证集合 = 8 : 2，这个需要根据情况而定。

（3）随机生成一个三层的神经网络结构，里面的权重都是随机生成，范围在 [0,1] 内。输入层的数据和输出层的数据保持一致，并且神经网络中间层的节点个数是输入层的一半。

（4）使用后向传播算法（back-propagation）来训练模型。为了防止神经网络的过拟合，通常有两种策略来防止这个问题。（i）第一种策略是“早停”（early stopping）：当训练集合的误差降低，但是验证集合的误差增加时，则停止训练，同时返回具有最小验证集合误差的神经网络；（ii）第二种策略是“正则化”（regularization）：基本思想是在误差目标函数中增加一个用于描述网络复杂度的部分，例如链接权和阀值的平方和。

测试效果：

其中蓝色的点表示正常点，红色的点表示被 RNN 算法标记的异常点。

参考文献：

[1] Anomaly Detection Using Replicator Neural Networks Trained on Examples of One Class, Hoang Anh Dau, Vic Ciesielski, Andy Song

[2] Replicator Neural Networks for Outlier Modeling in Segmental Speech Recognition, Laszlo Toth and Gabor Gosztolya

[3] Outlier Detection Using Replicator Neural Networks, Simon Hawkins, Honxing He, Graham Williams and Rohan Baxter

聚类是一种无监督学习（无监督学习是指事先并不知道要寻找的内容，没有固定的目标变量）的算法，它将相似的一批对象划归到一个簇，簇里面的对象越相似，聚类的效果越好。聚类的目标是在保持簇数目不变的情况下提高簇的质量。给定一个 n 个对象的集合。把这 n 个对象划分到 K 个区域，每个对象只属于一个区域。所遵守的一般准则是：同一个簇的对象尽可能的相互接近或者相关，而不同簇的对象尽可能的区分开。最常见的一种聚类算法则是 K-均值 算法。

K-均值（K-Means）聚类算法

K 均值聚类算法是用来发现给定数据集的 K 个簇的一种无监督学习算法，簇的个数是由人工给定的，每个簇使用质心（Centroid）和相应的半径（Radius）来描述。需要量化的误差指标有误差平方和（sum of squared error）等。

K-均值算法是一种启发式的算法。它会渐近地提高聚类的质量，达到局部的最优解，但是就是因为这样，才容易陷入局部最优解，而没有达到全局最优解，所有有人提出了二分 K-均值算法。启发式的聚类算法很适合发现中小规模的簇，对于大数据集合，从计算量来说成本则会很高。K-均值算法也有着自己的不足之处，通过下面算法可以发现 K-均值算法对离群点特别敏感，离群点的存在会直接影响着 K-均值算法的效果。

K 均值算法的流程是这样的。首先，随机确定 K 个初始点作为质心。然后将数据集中的每个点分配到每一个簇中，具体来讲，为每一个数据点找距离其最近的质心，并将其分配给该质心所对应的簇。这一步完成之后，每个簇的质心更新为该簇所有点的平均值。

K-Means 的伪代码：

创建K个点作为初始的质心（经常是随机选择数据点中的K个点，而不是平面上随机的K个点）

当任意一个点的簇分配结果发生变化时：

    对数据集中每个数据点

        对每个质心，计算质心与数据点之间的距离

        将数据点分配到距离其最近的簇

    对每一个簇，计算簇中所有点的均值并将均值作为质心

注：K 均值算法在某些时候容易收敛到局部最小值。

使用一批二维数据集合，进行 4 均值聚类算法可以得到下图：’+’ 表示的是质心的位置，其余就是数据点的位置。

效果评估：

SSE 指的是 Sum of Squared Error（误差平方和）越小表示数据点越接近它们的质心，聚类的效果也就越好。质心使用 c[i] 表示，质心 c[i] 所包含的对象集合使用 C[i] 表示。如果用 p 表示 C[i] 中的某个对象，dist(p,c[i]) 表示的就是对象和质心 c[i] 的距离。那么误差平方和则定义为

二分 K 均值聚类（Bisecting K-Means）

为了解决 K 均值算法可能会收敛到局部最小值的情况，有人提出了二分 K 均值算法（bisecting K-means）。该算法首先将所有点作为一个簇，然后将该簇一分为二，之后选择其中的一个簇继续进行划分，选择哪一个簇进行划分取决于对其划分是否可以最大程度降低 SSE 的值。上述基于SSE的划分过程不断重复，直到得到用户指定的簇的数目为止。

二分 K-Means 的伪代码如下：

将所有的点看成一个簇

当簇的数量小于K时

    对于每一个簇

        计算总误差

        在给定的簇上面进行2均值聚类

        计算将该簇一分为二之后的总误差（指的是这两个簇的误差与其他剩余集的误差之和）

    选择使得总误差最小的那个簇进行划分操作

另一种做法就是：每次进行下一步划分的时候，选择误差平方和最大的簇进行划分，直到簇的数目达到用户指定的数目为止。这样的启发式算法就使得整体的误差平方和尽可能的小，也就是簇的划分更加精确。

使用一批二维数据集合，进行 3 均值聚类算法可以得到下图：’+’ 表示的是质心的位置，其余就是数据点的位置。

（一）FTRL 的算法原理：

FTRL 算法综合考虑了 FOBOS 和 RDA 对于梯度和正则项的优势和不足，其特征权重的更新公式是：

上面的公式出现了 L2 范数，不过这一项的引入不会影响 FTRL 的稀疏性，只是使得求解结果更加“平滑”。通过数学计算并且放弃常数项可以得到上面的优化问题相当于求使得下面式子的最小的参数 W：

如果假设 上式等价于

写成分量的形式就是：

通过计算可以直接得到：

由此可以证明：引入 L2 正则化并没有对 FTRL 的稀疏性产生影响。

（二）学习率

在 SGD 的算法里面使用的是一个全局的学习率 ，意味着学习率是一个正数并且逐渐递减，对每一个维度都是一样的。而在 FTRL 算法里面，每个维度的学习率是不一样的。如果特征 A 比特征 B变化快，那么在维度 A 上面的学习率应该比维度 B 上面的学习率下降得更快。在 FTRL 中，维度 i 的学习率是这样定义的：

按照之前的定义 , 所以

（三）FTRL 算法

FTRL Algorithm

（1）输入 ，初始化 

（2）for 
        
        for 
         
          // equals to 
         
         
         
         
        end
     end

（四）Logistic Regression 的 FTRL 形式

在 Logistic Regression 中，假设 是 sigmoid 函数，，需要预估 ，那么 LogLoss 函数是

，

直接计算可得 ，所以 Logistic Regression 的 FTRL 算法就是：

FTRL Algorithm (Logistic Regression)

（1）输入 ，初始化 

（2）for 
        for 
          // gradient of loss function
         
          // equals to 
         
         
         
         
        end
     end

进入公司之后第一次听到“量子计算”这个概念，一直觉得十分神秘。从维基百科或者知乎上看来说什么量子计算机利用量子来提升效率，有极强的并行能力，可以加速很多算法等。但是个人还是对这个方向了解甚少。直到前几天听完组里面大神的讲座，并用《Quantum Computing: From Linear Algebra to Physical Realizations》一书的作为量子计算的入门读物。读后豁然开朗，虽然也对这个方向了解也不够深入，不过还是略做笔记作为分享。作为一个量子计算的初学者，还是有很多理解不够到位之处，希望大家指正。

普通计算机一个比特（bit）可以表示 0 或者 1。而量子具有不确定性，这使得一个量子比特（qubit）需要描述成 α0|0⟩+α1|1⟩（量子比特的 0 状态记作 |0⟩，1 状态记作 |1⟩），其中 |α0|^2+|α1|^2=1。也就是表示了这个量子比特有 |α0|^2 的概率是 |0⟩，有 |α1|^2 的概率是 |1⟩。这里面的 α0 和 α1 都是复数，所以要先取模再平方才是其概率。可以记作 p(0)=|α0|^2, p(1)=|α1|^2, p(0)+p(1)=1。举例说明：

如果某个量子的状态是 , 那么 p(0)=1/3，p(1)=2/3。如果测量的结果是0，那么这个 qubit 的状态就是0，换言之，；如果测量的结果是1，那么这个 qubit 的状态也就变成了1，换言之， 。

总之，量子状态有很多的可能性，因为复数 α0 和 α1 只有一个限制条件，那就是它们模的平方和是1。测量一个 qubit 只会给出 0 或者 1 的结果，这一点和传统的 bit 是一样的。同时，如果再次测量的话，只会给出和前一次一样的结果，结果并不会再次改变。除此之外，我们还可以把单个量子比特推广到两个量子比特为： α0|00⟩+α1|01⟩+α2|10⟩+α3|11⟩。同样的，系数的模的平方和为 1。换言之，α0，α1，α2，α3 这几个复数的模的平方和是1。

这里就能看出量子计算的厉害之处了，普通计算机 n 比特可以描述 2^n 个整数之一，而 n 个量子比特可以同时描述 2^n 个复数（一个 2^n 维的复数向量）。

如果仅仅是有表达向量的能力，传统的计算机就可以搞定。量子计算机之所以能成为量子计算机，更在于其对于量子比特的特殊计算操作。那么这里就需要引入量子逻辑门（Quantum Logic Gates）的概念。每一个 Quantum Logic Gate 都对应了一个数学上面的一个酉矩阵（Unitary Matrix）。如果 n*n 的矩阵 U 满足 UU^{T}=U^{T}U=I，这里的 I 指的是 n*n 的单位矩阵，U^{T} 指的是矩阵 U 的转置，那么 U 就被成为酉矩阵。

（1）量子非门（Quantum NOT Gate）是把 α0|0⟩+α1|1⟩ 映射成 α1|0⟩+α0|1⟩，也就是把 α0 和 α1 交换顺序。

（2）Quantum Controlled NOT Gate 是把 α0|00⟩+α1|01⟩+α2|10⟩+α3|11⟩ 映射成 α0|00⟩+α1|01⟩+α3|10⟩+α2|11⟩，也就是把 α2 和 α3 交换顺序。

（3）一个很著名的计算单元是 Hadamard Gate，输入 α0|0⟩+α1|1⟩，输出 2^{-1/2}(α0+α1)|0⟩+2^{-1/2}(α0-α1)|1⟩ 。Hadamard Gate 就是把经典的状态 |0⟩ 和 |1⟩ 转换成 |0⟩ 和 |1⟩ 的“halfway” 状态。不要小看这个操作，即使仅仅对 n 个量子比特中的第一位进行了 Hadamard gate 运算，所有的 2^{n} 个系数都会改变，证明如下：

假设我们有一个在 n 个 qubits 的量子状态 ，如果我们对第一个 qubit 使用 Hadamard Gate，那么状态就会变成，其中, 。也就是说每一对 和 都会被映射成  和 。因此就证明了，仅仅对 n 个量子比特中的第一位进行了 Hadamard gate 运算，所有的 2^n 个系数都会改变。这个就是在 quantum fourier transform 算法中达到指数级别加速的基础。

最后，薛定谔的猫要出场了。怎么把计算结果从混沌的量子态变成我们可理解的结果呢？这就需要“观测”。每次观测，量子就会按照 |α0|^2、|α1|^2 的概率塌缩到 |0⟩ 或者 |1⟩。量子存在一个 No-Cloning Theorem，这就导致了我们不能简单地“反复观测”量子计算的结果了，而需要反复计算+观测。通过 No-Cloning Theorem，我们可以得出一个观点：We can not copy a genderal quantum state. 为了能够加深读者对定理的理解，No-Cloning Theorem 的证明采取了数学上经典的反证法，先假设存在一个系统能够完全的拷贝任意量子比特，从而推导出矛盾。细节如下：

Theorem. (No-Cloning Theorem, Wootters and Zurek, Dieks) An unknown quantum system cannot be cloned by unitary transformations.

Proof. By contradiction, there exists a unitary transformation U that makes a clone of a quantum system. That means for any state ,

.

Consider two linear independent states and . Then we have , from the assumption of U. Let , we get

.

However,

which contradicts the previous result. Therefore, there does not exist a unitary cloning transformation.

借助量子计算机，FFT 的复杂度可以降低到 O((log(n))^2)，甚至连读一遍数据的 O(n) 时间都不用，因为只要 log(n) 个量子比特就可以描述 n 维向量了。利用高性能的 FFT，因子分解的复杂度可以达到 sub-exponential time [Shor’s Algorithm]，RSA 加密就失效了。而且目前量子计算机已经第一次以可扩展的方式，使用 Shor’s Algorithm 完成了对15的素数分解。有人表示：用 Shor 算法实现素数分解这一件事情，可以与经典计算机中的 “Hello World!” 相提并论。

总结一下，从我目前理解来看，借助更快的 FFT 算法，量子计算的优势主要在素数分解上，可以把原来指数复杂度的算法减少至多项式复杂度的算法。对于传统的一些问题，量子计算机和传统计算机相比目前还是不具备绝对的优势。当然量子计算机这种强大的表达能力和计算能力还是非常有潜力和令人期待的。

在机器学习，数据挖掘和推荐系统这几个大领域中，用支持向量机模型（Support Vector Machines）或者逻辑回归模型（Logistic Regression）做模型的预估是十分常见的事情。既然是分类模型，那么就需要确定正负样本，以便模型进行合理而有效的分类，因此如何根据具体的业务来确定正负样本就是一个十分关键的问题。

点击率预测的正负样本如何产生：

对于视频或者音频节目而言，分成几个种类：

喜欢的节目：用户当天播放过的节目；

历史的节目：用户在过去的一段时间内播放过所有节目；

曝光的节目：一段时间内对用户曝光的节目。

由此，正样本可以定义为用户当天播放过的节目，也就是“喜欢”。负样本则有两种选择方案：

（1）负样本指的是对用户曝光过的节目，但是用户至始至终都没有播放过，也就是说该节目并不在“历史”和“喜欢”两个分类里面。

（2）负样本指的是在整个抽样的池子里面，但是用户至始至终都没有播放过，也就是说该节目并不在“历史”和“喜欢”这两个分类里面。

此时还需注意抽样比例，一般来说 负样本的个数/正样本的个数 = 1：1 或者 2：1。

但是视频类节目和广告有区别，有可能该节目只是因为标题取得好或者图片配的好，才会吸引用户进去点击，但是用户观看了很短的时间就发现不喜欢该节目。所以在选择正样本的时候，从某种层面上来说需要考虑用户的观看时间，设定一定的阀值或者一定的观看比例才能够反映用户是否喜欢该节目。比如YouTube的视频节目，不止有“订阅”，“添加到”，“分享”，还有能够反映用户喜好的“like”（顶一下），“dislike”（踩一下）。有的时候顶一下可能不足以反映用户是否喜欢，但是踩一下基本上可以确定该用户不喜欢这个视频节目。除了“like”和“dislike”，对于其余的一些APP或者视频网站，还会有其余的操作，比方说评论，分享，收藏，下载等操作。这些操作从某些层面上也会看出用户是否喜欢该节目。

转化数据，使之成为有效的特征。常用的方法是标准化，归一化，特征的离散化等。

（4.1）标准化（Standardization）：

比方说有一些数字的单位是千克，有一些数字的单位是克，这个时候需要统一单位。如果没有标准化，两个变量混在一起搞，那么肯定就会不合适。

（4.2）归一化（Normalization）：

归一化是因为在特征会在不同的尺度下有不同的表现形式，归一化会使得各个特征能够同时以恰当的方式表现。比方说某个专辑的点击播放率一般不会超过0.2，但是专辑的播放次数可能会达到几千次，所以说为了能够在模型里面得到更合适结果，需要先把一些特征在尺度上进行归一化，然后进行模型训练。进行比例缩放或者归一化的时候，通常采取的方案有线性（linearization）最大最小归一化，对数（logarithm）归一化，或者 z-score 的归一化。其中 z-score 的归一化指的是 ，这里 是这个特征的均值， 是这个特征的方差。这里的归一化的关键之处在于数据的变化（Data Transforming）。对于处理一些大尺度数据（比方说某个视频被所有用户观看的次数之类的），一般会使用对数来处理数据，或者双曲线函数。例如：

或者

  [5] 选择特征的常用方法：

（5.1）过滤（Filter）：

过滤这种方法是选定一个指标来评估这个特征的可行性，根据指标值来对已经构造的特征进行排序工作，去掉无法达到要求的特征。这个时候，选择一个合适的指标来判断特征是否有效就是关键所在。从统计学的角度来看，相关系数（Correlation Coefficient）是一个评价两个随机变量 X 和 Y 是否线性相关的一个重要指标。

就是相关系数的计算方法。如果 ，那么说明两个变量是线性反相关的；如果 ，那么说明两个变量是线性相关的。不过需要主要的是，即使 ，也只是说明两个变量是线性无关的，并不能推出它们之间是独立的。此时知道的就是一个线性分类器并不能把这个特征的正负样本分开，需要把该特征和其他特征交叉或者做其余的特征运算，形成一个或者多个新的特征，让这些新的特征发挥新的价值，做好进一步的分类工作。

（5.2）包装（Wrapper）：

包装这种方法和前面的过滤方法不一样。包装方法需要首先选定一种评估模型效果的方法，比方说 AUC（Area Under the Curve），MAE（Mean Absolute Error），Mean Squared Error（MSE）等。此时有两个不同的方案，分别是前向特征选择（Forward Feature Selection）和后向特征选择（Backward Feature Selection）。前向特征选择是从空集（Empty Set）开始，使用一种贪心算法，每次在现有特征的基础上逐渐添加一个使得模型效果更好的特征。反之，后向特征选择是从（Full Set）开始，每次去掉一个让模型效果提升最多的特征。或者可以使用增 L 去 R 算法（Plus-L Minus-R Selection），也就是说从空集开始，每次增加 L 个，同时减去 R 个，选择最优的特征，其中 L>R。或者从全集开始，每次减去 R 个，同时增加 L 个，选择最优的特征，其中 L<R。

（5.3）嵌入（Embedding）：

嵌入特征选择方法和算法本身紧密结合，在模型训练的过程中完成特征的选择。例如：决策树（Decision Tree）算法每次都是优先选择分类能力最强的特征；逻辑回归（Logistic Regression）算法加上 L1 和 L2 等惩罚项之后，也会使得某些信号比较弱的特征权重很小甚至为 0。至于 Logistic Regression 的一些算法，可以参考 TG（Truncated Gradient Algorithm），FOBOS（Forward and Backward Splitting），RDA（Regularized Dual Averaging Algorithm）， FTRL（Follow-the-Regularized-Leader Algorithm） 算法，参考文献：Ad Click Prediction: a View from the Trenches。

［7］上线的效果：

现在做在线学习和 CTR 常常会用到逻辑回归（ Logistic Regression），而传统的批量（batch）算法无法有效地处理超大规模的数据集和在线数据流，美国的 Google 公司先后三年时间（2010年-2013年）从理论研究到实际工程化实现的 FTRL（Follow-the-regularized-Leader）算法，在处理诸如逻辑回归之类的带非光滑正则化项（例如 L1 范数，做模型复杂度控制和稀疏化）的凸优化问题上性能非常出色。

通常，优化算法中的 gradient descent 等解法，是对一批样本进行一次求解，得到一个全局最优解。但是，实际的互联网广告应用需要的是快速地进行模型的更新。为了保证快速的更新，训练样本是一条一条地过来的，每来一个样本，模型的参数对这个样本进行一次迭代，从而保证了模型的及时更新，这种方法叫做在线梯度下降法（Online gradient descent）。

在应用的时候，线上来的每一个广告请求，都提取出相应的特征，再根据模型的参数，计算一个点击某广告的概率。在线学习的任务就是学习模型的参数。所谓的模型的参数，其实可以认为是一个目标函数的解。跟之前说的根据批量的样本计算一个全局最优解的方法的不同是，解这个问题只能扫描一次样本，而且样本是一条一条地过来的。

当然这会有误差，所以为了避免这种误差，又为了增加稀疏性，有人又想到了多个版本的算法，Google 公司有人总结了其中几种比较优秀的，例如 FOBOS，AOGD 和微软的 RDA，同时提出了Google自己的算法 FTRL-Proximal。其中，FTRL-Proximal 在稀疏性和精确度等方面表现都比较好。

问题描述（最小化目标函数）

等价条件：

（1）约束优化（convex constraint formulation）：

subject to

（2）无约束优化描述（soft regularization formulation）：

注：当选择合适的常数 时，这两种描述是等价的。

损失函数：

Linear Regression：

Logistic Regression：

传统算法（Gradient Descent）

Batch Gradient Descent: Repeat Until Convergence

{ }

这里的 Gradient Descent 是一种批量处理的方式（Batch），每次更新 W 的时候都需要扫描所有样本来计算一个全局梯度

传统算法（Stochastic Gradient Descent）

Stochastic Gradient Descent 是另外一种权重更新方法：

Loop{

for j=1 to M {  }

}

这里每次迭代仅仅根据单个样本更新权重 W，这种算法称为随机梯度下降法（Stochastic Gradient Descent）。

Truncated Gradient 算法简介

为了得到稀疏的特征权重 W，最简单粗暴的方式就是设定一个阈值，当 W 的某维度上系数小于这个阈值时将其设置为 0（称作简单截断）。这种方法实现起来很简单，也容易理解。但实际中（尤其在OGD里面）W 的某个系数比较小可能是因为该维度训练不足引起的，简单进行截断会造成这部分特征的丢失。

截断梯度法（TG, Truncated Gradient）是由John Langford，Lihong Li 和 Tong Zhang 在2009年提出，实际上是对简单截断的一种改进。下面首先描述一下 L1 正则化和简单截断的方法，然后我们再来看TG对简单截断的改进以及这三种方法在特定条件下的转化。

（1）L1 正则化法

由于 L1 正则项在 0 处不可导，往往会造成平滑的凸优化问题变成非平滑凸优化问题，因此在每次迭代中采用次梯度计算 L1 正则项的梯度。权重更新方式为：

注意，这里  是一个标量，且 ，为 L1 正则化参数。 是符号函数，如果 是一个向量，那么 。是学习率，通常假设为 的函数。 代表了第 t 次迭代中损失函数的梯度，由于 OGD 每次仅根据观测到的一个样本进行权重更新，因此也不再使用区分样本的下标 j。

（2）简单截断法

以 k 为窗口，当 t/k 不为整数时采用标准的SGD进行迭代，当 t/k 为整数时，采用如下权重更新方式：这里的 是分段函数，

这里 并且 。如果 是一个向量，那么 。

（3）截断梯度法（Truncated Gradient）

上面的简单截断法看上去十分 aggressive，因此截断梯度法在此基础上进行了改进工作。

 这里的方程 定义为：

其中 ，并且 。Truncated Gradient 方法同样是以 k 作为窗口，每进行 k 步就进行一次截断操作。当 t/k 不是整数时，，当 t/k 是整数时，。从上面的公式可以看出， 决定了 W 的稀疏程度，如果 和 都很大，那么稀疏性就会越强。特别的，当 时，此时只需要控制一个参数就可以控制稀疏性。

Truncated Gradient 的算法：

输入 ，初始化 
for t = 1,2,3,... 计算 
按照下面规则更新 W,

    （i）当 t/k 不是整数时，采用标准的 SGD (Stochastic Gradient Descent) 进行迭代。，并且  for all .

    （ii）当 t/k 是整数时，采取截断技术。

     , if 

     , else if 

     , otherwise
return W.

（4）Truncated Gradient，简单截断法，L1 正则化之间的关系。

简单截断法和截断梯度法的区别在于选择了不同的截断公式 和 。如下图所示：

Truncated Gradient -> 简单截断法

从上图可以直接看出：选择 ，截断梯度法就可以变成简单截断法。从公式上也可以通过计算直接得出。

Truncated Gradient -> L1 正则化

貌似有一点问题，需要重新推导。

FOBOS 算法简介

（1）FOBOS（Forward Backward Splitting）算法原理

前向后向切分（FOBOS，Forward Backward Splitting）是 John Duchi 和 Yoran Singer 提出的。在该算法中，权重的更新分成两个步骤：

第一个步骤实际上是一个标准的梯度下降（SGD），第二个步骤是对第一个步骤的结果进行局部调整。写成一个公式那就是：

假设 ，如果 存在一个最优解，那么可以推断 0 向量一定属于 的次梯度集合：

.

因为 , 那么可以得到权重更新的另外一种形式：

从上面的公式可以看出，更新后的 不仅和 有关，还和自己 有关。这也许就是”前向后向切分”这个名称的由来。

（2）FOBOS（Forward Backward Splitting）的 L1 正则化

假设 是 L1 范数，中间向量是 , 并且参数 ，那么公式就可以展开得到

所以，可以对特征权重 W 的每一个维度进行单独求解：

for all $latex 1\leq i \leq N$.

Claim. 如果 是 的最优解，那么 .

证明：反证法，如果 ，那么 ， 这与条件矛盾。

通过数学计算可以证明：在 L1 正则化下，FOBOS 的特征权重的各个维度的更新公式是：

for all

其中 是梯度 在第 i 个维度的分量。

从公式上看，

如果 ， 则有 意思就是如果这次训练产生梯度的变化不足以令权重值发生足够大的变化时，就认为在这次训练中该维度不够重要，应该强制其权重是0.

如果 ，那么则有

L1-FOBOS 的算法：

（1）输入 ，初始化 
（2）for , 计算 
     按照公式更新 ， 
     for all 
（3）Return W

（3）L1-FOBOS 与 Truncated Gradient 的关系

令 ，可以得到 L1-FOBOS 与 Truncated Gradient 完全一致，换句话说 L1-FOBOS 是 Truncated Gradient 在一些特定条件下的形式。

Regularized Dual Averaging Algorithm 算法介绍

（一）RDA（Regularized Dual Averaging Algorithm）算法原理

RDA（Regularized Dual Averaging Algorithm）叫做正则对偶平均算法，特征权重的更新策略是：

其中 指的是向量 和 的内积， 是正则项， 是一个严格凸函数， 是一个非负递增序列。

从公式中可以看出：

1. 包括了之前所有梯度的平均值。
2. 具有正则项 。
3. 额外项 。

 （二）RDA 的 L1 正则化

假设 ；，i.e. 是一个严格凸函数； 是一个非负递增序列。那么 RDA 算法就可以写成：

此时可以采取同样的策略，把各个维度拆分成 N 个独立的问题来处理。也就是：

其中，  

通过数学推导可以证明：

if

otherwise

意思就是：当某个维度的累加平均值 小于 时，该维度的权重被设置成零，此时就可以产生特征权重的稀疏性。

RDA 的算法

（1）输入 ，初始化 
（2）for  
         
         更新 ：
         
     end
     return W

（三）L1-RDA 与 L1-FOBOS 的对比

从截断方式来看，在 RDA 的算法中，只要梯度的累加平均值小于参数 ，就直接进行截断，说明 RDA 更容易产生稀疏性；同时，RDA 中截断的条件是考虑梯度的累加平均值，可以避免因为某些维度训练不足而导致截断的问题，这一点与 TG，FOBOS 不一样。通过调节参数 可以在精度和稀疏性上进行权衡。

（四）L1-RDA 与 L1-FOBOS 形式上的统一

在 L1-FOBOS 中，假设 ，可以得到：

通过计算可以把 L1-FOBOS 写成：

同时 L1-RDA 可以写成：

其中 。如果令 上面的公式可以写成：

L1-FOBOS：

L1-RDA ：

可以看出：

1. L1-FOBOS 考虑了梯度和当前模的 L1 正则项，L1-RDA 考虑的是累积梯度。
2. L1-FOBOS 的第三项限制 W 不能够距离已经迭代过的 值太远，L1-RDA 的第三项限制的是 W 不能够距离 0 太远。

在信息论和概率论里面，Kullback-Leibler 散度（简称KL散度，KL divergence）是两个概率分布 和 的一个非对称的度量公式。这个概念是由 Solomon Kullback 和 Richard Leibler 在 1951 年引入的。从概率分布 到概率分布 的 KL 散度用 来表示。尽管从直觉上看 KL 散度是一个度量或者是一个距离，但是它却不满足度量或者距离的定义。例如，从 到 的 KL 散度就不一定等于从 到 的 KL 散度。

KL 散度的数学定义：

对于离散空间的两个概率分布 和 而言，从 到 的KL散度被定义为

换句话说，它是两个概率分布 和 的对数差的期望，这里的期望是以概率 来描述的。KL散度有定义当且 对于所有的 都成立。如果 那么可以假设KL散度的第 项是零，因为

对于连续空间 的两个概率分布 和 而言，从 到 的 KL 散度被定义为：

这里的 和 是概率分布 和 的概率密度。

KL 散度的基本性质：

（1）KL 散度总是非负的，并且只有 几乎处处成立的时候，才会有

证明：利用Jensen’s Inequality。

（2）如果 是独立分布，并且联合分布是 是独立分布并且联合分布是 那么

+

（3）如果定义分布 和 的交叉墒是

分布的熵是

那么

（4）KL 散度是两个概率分布 和 差别的非对称性的度量。 KL 散度是用来度量使用基于 的编码来编码来自 的样本平均所需的额外的位元数。典型情况下， 表示数据的真实分布， 表示数据的理论分布，模型分布，或 的近似分布。

（5）从KL散度的定义可以得出

所以 KL 散度不满足距离的对称性。当然，如果需要把它弄成对称的，可以定义

+

简单例子：

比如有四个类别，一个方法 P 得到四个类别的概率分别是0.1，0.2，0.3，0.4。另一种方法 Q（或者说是事实情况）是得到四个类别的概率分别是0.4，0.3，0.2，0.1,那么这两个分布的 KL 散度就是

+ + +

案例分析：

在实际的工作中，我们通常会有某个网页或者app被用户点击或者播放的数据，同时，我们会拥有用户画像（personas），此刻我们关心的问题就是如何计算网页里面的某个新闻或者app里面的某个专辑受到不同维度的用户画像的喜好程度。比如，如何判断该新闻是受到各个年龄层的用户的喜爱还是只是受到某个年龄层的用户的喜爱？如何判断某个电台节目是受到大众的喜爱还是更加受到男性或者女性的喜爱？此时，怎么计算物品被用户的喜欢程度就成为了一个重要的关键。

通常的方案就是，比方说：某个电台专辑被66.7%的男性用户播放过，被33.3%的女性用户播放过，那么该物品是不是真的就是更加受到男性用户的青睐呢？答案是否定的。如果使用这款app的用户的男女比例恰好是1：1，那么根据以上数据，该电台专辑显然更加受到男性用户的喜爱。但是，实际的情况，使用这款app的用户的男女比例不完全是1：1。如果男性用户：女性用户=2：1的话，如果某个电台专辑被66.7%的男性用户播放过，被33.3%的女性用户播放过，那么说明该专辑深受男女喜欢，两者对该专辑的喜好程度是一样的。因为基础的男女比例是2：1，该专辑被男女播放的比例是2：1，所以，该专辑对男女的喜爱程度恰好是1：1。

那么如何计算该专辑的喜好程度呢？首先我们会使用KL散度来描述这件事情。

机器学习的各种算法在于如何使用特定函数与已知的数据集相匹配，从而达到训练和测试的目的。本篇文章对一些近似的模型做一些相应的介绍。

线性模型

一维输入变量

假设学习对象函数的输入是一组实数，那么对该函数进行近似的时候，最简单的方案就是。在这里，是这个函数的斜率，也就是这个函数的参数。机器学习就是通过对这个参数的学习，完成函数的近似计算。这个模型对于而言是一个线性函数，操作起来十分方便，但是对于实际的情况来说，该模型过于简单，没有太大的使用价值。 由于上面这个模型过于简单，那么在实际应用中，会对上述的模型进行必要的扩展，使得函数变成参数的线性模型，这样这个模型就可以用来表示非线性的输入和输出了。可以把扩展成如下形式：

在这个式子中，是基函数向量的第个分量，是的第个分量，是基函数的维数。根据上面的定义，可以得到该函数是参数向量的线性函数。也就是说对于维参数和，满足

那么这个时候如何选择基函数就成为了一个关键所在。

数学分析里面有一个经典定理叫做Weierstrass定理，陈述如下：

Weierstrass第一逼近定理：假设是闭区间上的连续函数，对于任意的，则存在多项式使得对于所有的，有。 

根据Weierstrass第一逼近定理，对于任何一个闭区间上面的连续函数，都可以用多项式去逼近。所以联系到机器学习，就可以把基函数的分量设置为多项式，换句话说

那么上述的的线性函数却是关于自变量的非线性函数，而且可以逼近关于的闭区间上任何一个连续函数。

与Weierstrass逼近定理类似，用Fourier级数也可以逼近Lipchitz连续函数。所以也可以选择基函数

 其中 

简单来说就是令  根据这些模型，就可以表示复杂的非线性模型了。

高维输入变量

对于高维的变量 函数依旧可以扩展成如下模式：

对于多维的输入向量，可以用一维的基函数来构造多维基函数的乘法模型和加法模型。

乘法模型指的是把一维的基函数作为因子，通过使其相乘而获得多维基函数的方法。表达式如下：

在上面的式子中，是各个维数的参数个数。对于这个模型而言，它的表现力十分丰富，但是不足之处在于所有的参数个数是 是一个非常巨大的数字，导致的维数灾难，所以在实际运用中，不主张用这个模型。

加法模型指的是把一维的基函数作为因子，通过相加而活得高维基函数的方法。表达式如下：

加法模型中所有参数的个数是 它是一个关于维数的线性函数，复杂度没有乘法模型大，但是表现力和乘法模型比起来则差很多。

核模型

在线性模型中，多项式或三角函数等基函数的选择都是与训练样本无关的，核模型则与之相反，会在进行基函数构造的时候使用输入样本  在核模型中，会使用核函数

其中指的是欧几里德2-范数，表示核函数的带宽，指的是核函数的均值。 从核函数的定义可以可以延伸出模型

在这个模型中，关于而言仍然满足线性关系。换句话说，对于 有 和 对于核函数来说，无论输入的是一维变量还是高维变量，核函数都可以容易的进行扩展。

层级模型

对参数来说是非线性的模型，都称为非线性模型。下面要介绍的就是非线性模型中的层级模型，它在很多领域都有应用。假设模型是

上式中，是关于参数向量的基函数，层级模型是基于参数向量的线性形式。同时也包含参数向量 所以层级模型是基于参数向量的非线性形式。 基函数通常采用S型函数

其中

或者高斯函数

其中

其中S函数模仿的是人类脑细胞的输入输出函数，因此使用S函数的层级模型也被称为人工神经网络模型。

针对像人工神经网络这样的层级模型，采用贝叶斯学习的方法是不错的选择。人工神经网络也以学习过程艰难异常而著称。