版权声明：

本文由LeftNotEasy发布于http://leftnoteasy.cnblogs.com, 本文可以被全部的转载或者部分使用，但请注明出处，如果有问题，请联系wheeleast@gmail.com

前言：

上一次写了关于PCA与LDA的文章，PCA的实现一般有两种，一种是用特征值分解去实现的，一种是用奇异值分解去实现的。在上篇文章中便是基于特征值分解的一种解释。特征值和奇异值在大部分人的印象中，往往是停留在纯粹的数学计算中。而且线性代数或者矩阵论里面，也很少讲任何跟特征值与奇异值有关的应用背景。奇异值分解是一个有着很明显的物理意义的一种方法，它可以将一个比较复杂的矩阵用更小更简单的几个子矩阵的相乘来表示，这些小矩阵描述的是矩阵的重要的特性。就像是描述一个人一样，给别人描述说这个人长得浓眉大眼，方脸，络腮胡，而且带个黑框的眼镜，这样寥寥的几个特征，就让别人脑海里面就有一个较为清楚的认识，实际上，人脸上的特征是有着无数种的，之所以能这么描述，是因为人天生就有着非常好的抽取重要特征的能力，让机器学会抽取重要的特征，SVD是一个重要的方法。

在机器学习领域，有相当多的应用与奇异值都可以扯上关系，比如做feature reduction的PCA，做数据压缩（以图像压缩为代表）的算法，还有做搜索引擎语义层次检索的LSI（Latent Semantic Indexing）

另外在这里抱怨一下，之前在百度里面搜索过SVD，出来的结果都是俄罗斯的一种狙击枪（AK47同时代的），是因为穿越火线这个游戏里面有一把狙击枪叫做SVD，而在Google上面搜索的时候，出来的都是奇异值分解（英文资料为主）。想玩玩战争游戏，玩玩COD不是非常好吗，玩山寨的CS有神马意思啊。国内的网页中的话语权也被这些没有太多营养的帖子所占据。真心希望国内的气氛能够更浓一点，搞游戏的人真正是喜欢制作游戏，搞Data Mining的人是真正喜欢挖数据的，都不是仅仅为了混口饭吃，这样谈超越别人才有意义，中文文章中，能踏踏实实谈谈技术的太少了，改变这个状况，从我自己做起吧。

前面说了这么多，本文主要关注奇异值的一些特性，另外还会稍稍提及奇异值的计算，不过本文不准备在如何计算奇异值上展开太多。另外，本文里面有部分不算太深的线性代数的知识，如果完全忘记了线性代数，看本文可能会有些困难。

一、奇异值与特征值基础知识：

特征值分解和奇异值分解在机器学习领域都是属于满地可见的方法。两者有着很紧密的关系，我在接下来会谈到，特征值分解和奇异值分解的目的都是一样，就是提取出一个矩阵最重要的特征。先谈谈特征值分解吧：

1）特征值：

如果说一个向量v是方阵A的特征向量，将一定可以表示成下面的形式：

这时候λ就被称为特征向量v对应的特征值，一个矩阵的一组特征向量是一组正交向量。特征值分解是将一个矩阵分解成下面的形式：

其中Q是这个矩阵A的特征向量组成的矩阵，Σ是一个对角阵，每一个对角线上的元素就是一个特征值。我这里引用了一些参考文献中的内容来说明一下。首先，要明确的是，一个矩阵其实就是一个线性变换，因为一个矩阵乘以一个向量后得到的向量，其实就相当于将这个向量进行了线性变换。比如说下面的一个矩阵：

它其实对应的线性变换是下面的形式：

因为这个矩阵M乘以一个向量(x,y)的结果是：

上面的矩阵是对称的，所以这个变换是一个对x，y轴的方向一个拉伸变换（每一个对角线上的元素将会对一个维度进行拉伸变换，当值>1时，是拉长，当值<1时时缩短），当矩阵不是对称的时候，假如说矩阵是下面的样子：

它所描述的变换是下面的样子：

这其实是在平面上对一个轴进行的拉伸变换（如蓝色的箭头所示），在图中，蓝色的箭头是一个最主要的变化方向（变化方向可能有不止一个），如果我们想要描述好一个变换，那我们就描述好这个变换主要的变化方向就好了。反过头来看看之前特征值分解的式子，分解得到的Σ矩阵是一个对角阵，里面的特征值是由大到小排列的，这些特征值所对应的特征向量就是描述这个矩阵变化方向（从主要的变化到次要的变化排列）

当矩阵是高维的情况下，那么这个矩阵就是高维空间下的一个线性变换，这个线性变化可能没法通过图片来表示，但是可以想象，这个变换也同样有很多的变换方向，我们通过特征值分解得到的前N个特征向量，那么就对应了这个矩阵最主要的N个变化方向。我们利用这前N个变化方向，就可以近似这个矩阵（变换）。也就是之前说的：提取这个矩阵最重要的特征。总结一下，特征值分解可以得到特征值与特征向量，特征值表示的是这个特征到底有多重要，而特征向量表示这个特征是什么，可以将每一个特征向量理解为一个线性的子空间，我们可以利用这些线性的子空间干很多的事情。不过，特征值分解也有很多的局限，比如说变换的矩阵必须是方阵。

（说了这么多特征值变换，不知道有没有说清楚，请各位多提提意见。）

2）奇异值：

下面谈谈奇异值分解。特征值分解是一个提取矩阵特征很不错的方法，但是它只是对方阵而言的，在现实的世界中，我们看到的大部分矩阵都不是方阵，比如说有N个学生，每个学生有M科成绩，这样形成的一个N * M的矩阵就不可能是方阵，我们怎样才能描述这样普通的矩阵呢的重要特征呢？奇异值分解可以用来干这个事情，奇异值分解是一个能适用于任意的矩阵的一种分解的方法：

假设A是一个N * M的矩阵，那么得到的U是一个N * N的方阵（里面的向量是正交的，U里面的向量称为左奇异向量），Σ是一个N * M的矩阵（除了对角线的元素都是0，对角线上的元素称为奇异值），V’(V的转置)是一个N * N的矩阵，里面的向量也是正交的，V里面的向量称为右奇异向量），从图片来反映几个相乘的矩阵的大小可得下面的图片

那么奇异值和特征值是怎么对应起来的呢？首先，我们将一个矩阵A的转置 * A，将会得到一个方阵，我们用这个方阵求特征值可以得到： 这里得到的v，就是我们上面的右奇异向量。此外我们还可以得到：

这里的σ就是上面说的奇异值，u就是上面说的左奇异向量。奇异值σ跟特征值类似，在矩阵Σ中也是从大到小排列，而且σ的减少特别的快，在很多情况下，前10%甚至1%的奇异值的和就占了全部的奇异值之和的99%以上了。也就是说，我们也可以用前r大的奇异值来近似描述矩阵，这里定义一下部分奇异值分解：

r是一个远小于m、n的数，这样矩阵的乘法看起来像是下面的样子：

右边的三个矩阵相乘的结果将会是一个接近于A的矩阵，在这儿，r越接近于n，则相乘的结果越接近于A。而这三个矩阵的面积之和（在存储观点来说，矩阵面积越小，存储量就越小）要远远小于原始的矩阵A，我们如果想要压缩空间来表示原矩阵A，我们存下这里的三个矩阵：U、Σ、V就好了。

二、奇异值的计算：

奇异值的计算是一个难题，是一个O(N^3)的算法。在单机的情况下当然是没问题的，matlab在一秒钟内就可以算出1000 * 1000的矩阵的所有奇异值，但是当矩阵的规模增长的时候，计算的复杂度呈3次方增长，就需要并行计算参与了。Google的吴军老师在数学之美系列谈到SVD的时候，说起Google实现了SVD的并行化算法，说这是对人类的一个贡献，但是也没有给出具体的计算规模，也没有给出太多有价值的信息。

其实SVD还是可以用并行的方式去实现的，在解大规模的矩阵的时候，一般使用迭代的方法，当矩阵的规模很大（比如说上亿）的时候，迭代的次数也可能会上亿次，如果使用Map-Reduce框架去解，则每次Map-Reduce完成的时候，都会涉及到写文件、读文件的操作。个人猜测Google云计算体系中除了Map-Reduce以外应该还有类似于MPI的计算模型，也就是节点之间是保持通信，数据是常驻在内存中的，这种计算模型比Map-Reduce在解决迭代次数非常多的时候，要快了很多倍。

Lanczos迭代就是一种解对称方阵部分特征值的方法（之前谈到了，解A’* A得到的对称方阵的特征值就是解A的右奇异向量），是将一个对称的方程化为一个三对角矩阵再进行求解。按网上的一些文献来看，Google应该是用这种方法去做的奇异值分解的。请见Wikipedia上面的一些引用的论文，如果理解了那些论文，也“几乎”可以做出一个SVD了。

由于奇异值的计算是一个很枯燥，纯数学的过程，而且前人的研究成果（论文中）几乎已经把整个程序的流程图给出来了。更多的关于奇异值计算的部分，将在后面的参考文献中给出，这里不再深入，我还是focus在奇异值的应用中去。

三、奇异值与主成分分析（PCA）：

主成分分析在上一节里面也讲了一些，这里主要谈谈如何用SVD去解PCA的问题。PCA的问题其实是一个基的变换，使得变换后的数据有着最大的方差。方差的大小描述的是一个变量的信息量，我们在讲一个东西的稳定性的时候，往往说要减小方差，如果一个模型的方差很大，那就说明模型不稳定了。但是对于我们用于机器学习的数据（主要是训练数据），方差大才有意义，不然输入的数据都是同一个点，那方差就为0了，这样输入的多个数据就等同于一个数据了。以下面这张图为例子：

这个假设是一个摄像机采集一个物体运动得到的图片，上面的点表示物体运动的位置，假如我们想要用一条直线去拟合这些点，那我们会选择什么方向的线呢？当然是图上标有signal的那条线。如果我们把这些点单纯的投影到x轴或者y轴上，最后在x轴与y轴上得到的方差是相似的（因为这些点的趋势是在45度左右的方向，所以投影到x轴或者y轴上都是类似的），如果我们使用原来的xy坐标系去看这些点，容易看不出来这些点真正的方向是什么。但是如果我们进行坐标系的变化，横轴变成了signal的方向，纵轴变成了noise的方向，则就很容易发现什么方向的方差大，什么方向的方差小了。

一般来说，方差大的方向是信号的方向，方差小的方向是噪声的方向，我们在数据挖掘中或者数字信号处理中，往往要提高信号与噪声的比例，也就是信噪比。对上图来说，如果我们只保留signal方向的数据，也可以对原数据进行不错的近似了。

PCA的全部工作简单点说，就是对原始的空间中顺序地找一组相互正交的坐标轴，第一个轴是使得方差最大的，第二个轴是在与第一个轴正交的平面中使得方差最大的，第三个轴是在与第1、2个轴正交的平面中方差最大的，这样假设在N维空间中，我们可以找到N个这样的坐标轴，我们取前r个去近似这个空间，这样就从一个N维的空间压缩到r维的空间了，但是我们选择的r个坐标轴能够使得空间的压缩使得数据的损失最小。

还是假设我们矩阵每一行表示一个样本，每一列表示一个feature，用矩阵的语言来表示，将一个m * n的矩阵A的进行坐标轴的变化，P就是一个变换的矩阵从一个N维的空间变换到另一个N维的空间，在空间中就会进行一些类似于旋转、拉伸的变化。

而将一个m * n的矩阵A变换成一个m * r的矩阵，这样就会使得本来有n个feature的，变成了有r个feature了（r < n)，这r个其实就是对n个feature的一种提炼，我们就把这个称为feature的压缩。用数学语言表示就是：

但是这个怎么和SVD扯上关系呢？之前谈到，SVD得出的奇异向量也是从奇异值由大到小排列的，按PCA的观点来看，就是方差最大的坐标轴就是第一个奇异向量，方差次大的坐标轴就是第二个奇异向量…我们回忆一下之前得到的SVD式子：

在矩阵的两边同时乘上一个矩阵V，由于V是一个正交的矩阵，所以V转置乘以V得到单位阵I，所以可以化成后面的式子

将后面的式子与A * P那个m * n的矩阵变换为m * r的矩阵的式子对照看看，在这里，其实V就是P，也就是一个变化的向量。这里是将一个m * n 的矩阵压缩到一个m * r的矩阵，也就是对列进行压缩，如果我们想对行进行压缩（在PCA的观点下，对行进行压缩可以理解为，将一些相似的sample合并在一起，或者将一些没有太大价值的sample去掉）怎么办呢？同样我们写出一个通用的行压缩例子：

这样就从一个m行的矩阵压缩到一个r行的矩阵了，对SVD来说也是一样的，我们对SVD分解的式子两边乘以U的转置U’

这样我们就得到了对行进行压缩的式子。可以看出，其实PCA几乎可以说是对SVD的一个包装，如果我们实现了SVD，那也就实现了PCA了，而且更好的地方是，有了SVD，我们就可以得到两个方向的PCA，如果我们对A’A进行特征值的分解，只能得到一个方向的PCA。

四、奇异值与潜在语义索引LSI：

潜在语义索引（Latent Semantic Indexing）与PCA不太一样，至少不是实现了SVD就可以直接用的，不过LSI也是一个严重依赖于SVD的算法，之前吴军老师在矩阵计算与文本处理中的分类问题中谈到：

“三个矩阵有非常清楚的物理含义。第一个矩阵X中的每一行表示意思相关的一类词，其中的每个非零元素表示这类词中每个词的重要性（或者说相关性），数值越大越相关。最后一个矩阵Y中的每一列表示同一主题一类文章，其中每个元素表示这类文章中每篇文章的相关性。中间的矩阵则表示类词和文章雷之间的相关性。因此，我们只要对关联矩阵A进行一次奇异值分解，w 我们就可以同时完成了近义词分类和文章的分类。（同时得到每类文章和每类词的相关性）。”

上面这段话可能不太容易理解，不过这就是LSI的精髓内容，我下面举一个例子来说明一下，下面的例子来自LSA tutorial，具体的网址我将在最后的引用中给出：

这就是一个矩阵，不过不太一样的是，这里的一行表示一个词在哪些title中出现了（一行就是之前说的一维feature），一列表示一个title中有哪些词，（这个矩阵其实是我们之前说的那种一行是一个sample的形式的一种转置，这个会使得我们的左右奇异向量的意义产生变化，但是不会影响我们计算的过程）。比如说T1这个title中就有guide、investing、market、stock四个词，各出现了一次，我们将这个矩阵进行SVD，得到下面的矩阵：

左奇异向量表示词的一些特性，右奇异向量表示文档的一些特性，中间的奇异值矩阵表示左奇异向量的一行与右奇异向量的一列的重要程序，数字越大越重要。

继续看这个矩阵还可以发现一些有意思的东西，首先，左奇异向量的第一列表示每一个词的出现频繁程度，虽然不是线性的，但是可以认为是一个大概的描述，比如book是0.15对应文档中出现的2次，investing是0.74对应了文档中出现了9次，rich是0.36对应文档中出现了3次；

其次，右奇异向量中一的第一行表示每一篇文档中的出现词的个数的近似，比如说，T6是0.49，出现了5个词，T2是0.22，出现了2个词。

然后我们反过头来看，我们可以将左奇异向量和右奇异向量都取后2维（之前是3维的矩阵），投影到一个平面上，可以得到：

在图上，每一个红色的点，都表示一个词，每一个蓝色的点，都表示一篇文档，这样我们可以对这些词和文档进行聚类，比如说stock 和 market可以放在一类，因为他们老是出现在一起，real和estate可以放在一类，dads，guide这种词就看起来有点孤立了，我们就不对他们进行合并了。按这样聚类出现的效果，可以提取文档集合中的近义词，这样当用户检索文档的时候，是用语义级别（近义词集合）去检索了，而不是之前的词的级别。这样一减少我们的检索、存储量，因为这样压缩的文档集合和PCA是异曲同工的，二可以提高我们的用户体验，用户输入一个词，我们可以在这个词的近义词的集合中去找，这是传统的索引无法做到的。

不知道按这样描述，再看看吴军老师的文章，是不是对SVD更清楚了？:-D

参考资料：

1）A Tutorial on Principal Component Analysis, Jonathon Shlens
这是我关于用SVD去做PCA的主要参考资料
2）http://www.ams.org/samplings/feature-column/fcarc-svd
关于svd的一篇概念好文，我开头的几个图就是从这儿截取的
3）http://www.puffinwarellc.com/index.php/news-and-articles/articles/30-singular-value-decomposition-tutorial.html
另一篇关于svd的入门好文
4）http://www.puffinwarellc.com/index.php/news-and-articles/articles/33-latent-semantic-analysis-tutorial.html
svd与LSI的好文，我后面LSI中例子就是来自此
5）http://www.miislita.com/information-retrieval-tutorial/svd-lsi-tutorial-1-understanding.html
另一篇svd与LSI的文章，也还是不错，深一点，也比较长
6）Singular Value Decomposition and Principal Component Analysis, Rasmus Elsborg Madsen, Lars Kai Hansen and Ole Winther, 2004
跟1）里面的文章比较类似

版权声明：

本文由LeftNotEasy发布于http://leftnoteasy.cnblogs.com, 本文可以被全部的转载或者部分使用，但请注明出处，如果有问题，请联系wheeleast@gmail.com

前言：

第二篇的文章中谈到，和部门老大一宁出去outing的时候，他给了我相当多的机器学习的建议，里面涉及到很多的算法的意义、学习方法等等。一宁上次给我提到，如果学习分类算法，最好从线性的入手，线性分类器最简单的就是LDA，它可以看做是简化版的SVM，如果想理解SVM这种分类器，那理解LDA就是很有必要的了。

谈到LDA，就不得不谈谈PCA，PCA是一个和LDA非常相关的算法，从推导、求解、到算法最终的结果，都有着相当的相似。

本次的内容主要是以推导数学公式为主，都是从算法的物理意义出发，然后一步一步最终推导到最终的式子，LDA和PCA最终的表现都是解一个矩阵特征值的问题，但是理解了如何推导，才能更深刻的理解其中的含义。本次内容要求读者有一些基本的线性代数基础，比如说特征值、特征向量的概念，空间投影，点乘等的一些基本知识等。除此之外的其他公式、我都尽量讲得更简单清楚。

LDA：

LDA的全称是Linear Discriminant Analysis（线性判别分析），是一种supervised learning。有些资料上也称为是Fisher’s Linear Discriminant，因为它被Ronald Fisher发明自1936年，Discriminant这次词我个人的理解是，一个模型，不需要去通过概率的方法来训练、预测数据，比如说各种贝叶斯方法，就需要获取数据的先验、后验概率等等。LDA是在目前机器学习、数据挖掘领域经典且热门的一个算法，据我所知，百度的商务搜索部里面就用了不少这方面的算法。

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

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

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

红色的方形的点为0类的原始点、蓝色的方形点为1类的原始点，经过原点的那条线就是投影的直线，从图上可以清楚的看到，红色的点和蓝色的点被原点明显的分开了，这个数据只是随便画的，如果在高维的情况下，看起来会更好一点。下面我来推导一下二分类LDA问题的公式：

假设用来区分二分类的直线（投影函数)为：

LDA分类的一个目标是使得不同类别之间的距离越远越好，同一类别之中的距离越近越好，所以我们需要定义几个关键的值。

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

类别i投影后的中心点为：

衡量类别i投影后，类别点之间的分散程度（方差）为：

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

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

我们定义一个投影前的各类别分散程度的矩阵，这个矩阵看起来有一点麻烦，其实意思是，如果某一个分类的输入点集Di里面的点距离这个分类的中心店mi越近，则Si里面元素的值就越小，如果分类的点都紧紧地围绕着mi，则Si里面的元素值越更接近0.

带入Si，将J(w)分母化为：

同样的将J(w)分子化为：

这样损失函数可以化成下面的形式：

这样就可以用最喜欢的拉格朗日乘子法了，但是还有一个问题，如果分子、分母是都可以取任意值的，那就会使得有无穷解，我们将分母限制为长度为1（这是用拉格朗日乘子法一个很重要的技巧，在下面将说的PCA里面也会用到，如果忘记了，请复习一下高数），并作为拉格朗日乘子法的限制条件，带入得到：

这样的式子就是一个求特征值的问题了。

对于N(N>2)分类的问题，我就直接写出下面的结论了：

这同样是一个求特征值的问题，我们求出的第i大的特征向量，就是对应的Wi了。

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

下图是图像识别中广泛用到的特征脸（eigen face），提取出特征脸有两个目的，首先是为了压缩数据，对于一张图片，只需要保存其最重要的部分就是了，然后是为了使得程序更容易处理，在提取主要特征的时候，很多的噪声都被过滤掉了。跟下面将谈到的PCA的作用非常相关。

特征值的求法有很多，求一个D * D的矩阵的时间复杂度是O(D^3), 也有一些求Top M的方法，比如说power method，它的时间复杂度是O(D^2 * M), 总体来说，求特征值是一个很费时间的操作，如果是单机环境下，是很局限的。

PCA：

主成分分析（PCA）与LDA有着非常近似的意思，LDA的输入数据是带标签的，而PCA的输入数据是不带标签的，所以PCA是一种unsupervised learning。LDA通常来说是作为一个独立的算法存在，给定了训练数据后，将会得到一系列的判别函数（discriminate function），之后对于新的输入，就可以进行预测了。而PCA更像是一个预处理的方法，它可以将原本的数据降低维度，而使得降低了维度的数据之间的方差最大（也可以说投影误差最小，具体在之后的推导里面会谈到）。

方差这个东西是个很有趣的，有些时候我们会考虑减少方差（比如说训练模型的时候，我们会考虑到方差-偏差的均衡），有的时候我们会尽量的增大方差。方差就像是一种信仰（强哥的话），不一定会有很严密的证明，从实践来说，通过尽量增大投影方差的PCA算法，确实可以提高我们的算法质量。

说了这么多，推推公式可以帮助我们理解。我下面将用两种思路来推导出一个同样的表达式。首先是最大化投影后的方差，其次是最小化投影后的损失（投影产生的损失最小）。

最大化方差法：

假设我们还是将一个空间中的点投影到一个向量中去。首先，给出原空间的中心点：

假设u1为投影向量，投影之后的方差为：

上面这个式子如果看懂了之前推导LDA的过程，应该比较容易理解，如果线性代数里面的内容忘记了，可以再温习一下，优化上式等号右边的内容，还是用拉格朗日乘子法：

将上式求导，使之为0，得到：

这是一个标准的特征值表达式了，λ对应的特征值，u对应的特征向量。上式的左边取得最大值的条件就是λ1最大，也就是取得最大的特征值的时候。假设我们是要将一个D维的数据空间投影到M维的数据空间中（M < D)， 那我们取前M个特征向量构成的投影矩阵就是能够使得方差最大的矩阵了。

最小化损失法：

假设输入数据x是在D维空间中的点，那么，我们可以用D个正交的D维向量去完全的表示这个空间（这个空间中所有的向量都可以用这D个向量的线性组合得到）。在D维空间中，有无穷多种可能找这D个正交的D维向量，哪个组合是最合适的呢？

假设我们已经找到了这D个向量，可以得到：

我们可以用近似法来表示投影后的点：

上式表示，得到的新的x是由前M 个基的线性组合加上后D – M个基的线性组合，注意这里的z是对于每个x都不同的，而b对于每个x是相同的，这样我们就可以用M个数来表示空间中的一个点，也就是使得数据降维了。但是这样降维后的数据，必然会产生一些扭曲，我们用J描述这种扭曲，我们的目标是，使得J最小：

上式的意思很直观，就是对于每一个点，将降维后的点与原始的点之间的距离的平方和加起来，求平均值，我们就要使得这个平均值最小。我们令：

将上面得到的z与b带入降维的表达式：

将上式带入J的表达式得到：

再用上拉普拉斯乘子法（此处略），可以得到，取得我们想要的投影基的表达式为：

这里又是一个特征值的表达式，我们想要的前M个向量其实就是这里最大的M个特征值所对应的特征向量。证明这个还可以看看，我们J可以化为：

也就是当误差J是由最小的D – M个特征值组成的时候，J取得最小值。跟上面的意思相同。

下图是PCA的投影的一个表示，黑色的点是原始的点，带箭头的虚线是投影的向量，Pc1表示特征值最大的特征向量，pc2表示特征值次大的特征向量，两者是彼此正交的，因为这原本是一个2维的空间，所以最多有两个投影的向量，如果空间维度更高，则投影的向量会更多。

总结：

本次主要讲了两种方法，PCA与LDA，两者的思想和计算方法非常类似，但是一个是作为独立的算法存在，另一个更多的用于数据的预处理的工作。另外对于PCA和LDA还有核方法，本次的篇幅比较大了，先不说了，以后有时间再谈：

参考资料：

prml bishop，introduce to LDA（对不起，这个真没有查到出处）

版权声明：

    本文由LeftNotEasy发布于http://thinkbot.info, 本文可以被全部的转载或者部分使用，但请注明出处，如果有问题，请联系wheeleast@gmail.com

前言：

    本来上一章的结尾提到，准备写写线性分类的问题，文章都已经写得差不多了，但是突然听说最近Team准备做一套分布式的分类器，可能会使用Random Forest来做，下了几篇论文看了看，简单的random forest还比较容易弄懂，复杂一点的还会与boosting等算法结合（参见iccv09），对于boosting也不甚了解，所以临时抱佛脚的看了看。说起boosting，强哥之前实现过一套Gradient Boosting Descent Tree（GBDT)算法，正好参考一下。

    最近看的一些论文中发现了模型组合的好处，比如GBDT或者rf，都是将简单的模型组合起来，效果比单个更复杂的模型好。组合的方式很多，随机化（比如random forest），Boosting（比如GBDT）都是其中典型的方法，今天主要谈谈Gradient Boosting方法（这个与传统的Boosting还有一些不同）的一些数学基础，有了这个数学基础，上面的应用可以看Freidman的Gradient Boosting Machine。

    本文要求读者学过基本的大学数学，另外对分类、回归等基本的机器学习概念了解。

    本文主要参考资料是prml与Gradient Boosting Machine。

Boosting方法：

    Boosting这其实思想相当的简单，大概是，对一份数据，建立M个模型（比如分类），一般这种模型比较简单，称为弱分类器(weak learner)每次分类都将上一次分错的数据权重提高一点再进行分类，这样最终得到的分类器在测试数据与训练数据上都可以得到比较好的成绩。

    上图（图片来自prml p660）就是一个Boosting的过程，绿色的线表示目前取得的模型（模型是由前m次得到的模型合并得到的），虚线表示当前这次模型。每次分类的时候，会更关注分错的数据，上图中，红色和蓝色的点就是数据，点越大表示权重越高，看看右下角的图片，当m=150的时候，获取的模型已经几乎能够将红色和蓝色的点区分开了。

    Boosting可以用下面的公式来表示：

    训练集中一共有n个点，我们可以为里面的每一个点赋上一个权重Wi(0 <= i < n)，表示这个点的重要程度，通过依次训练模型的过程，我们对点的权重进行修正，如果分类正确了，权重提高，如果分类错了，则权重降低，初始的时候，权重都是一样的。上图中绿色的线就是表示依次训练模型，可以想象得到，程序越往后执行，训练出的模型就越会在意那些容易分错的点。当全部的程序执行完后，会得到M个模型，分别对应上图的y1(x)…yM(x)，通过加权的方式组合成一个最终的模型YM(x)。

    我觉得Boosting更像是一个人学习的过程，开始学一样东西的时候，会去做一些习题，但是常常连一些简单的题目都会弄错，但是越到后面，简单的题目已经难不倒他了，就会去做更复杂的题目，等到他做了很多的题目后，不管是难题还是简单的题都可以解决掉了。

Gradient Boosting方法：

    其实Boosting更像是一种思想，Gradient Boosting是一种Boosting的方法，它主要的思想是，每一次建立模型是在之前建立模型损失函数的梯度下降方向。这句话有一点拗口，损失函数(loss function)描述的是模型的不靠谱程度，损失函数越大，则说明模型越容易出错（其实这里有一个方差、偏差均衡的问题，但是这里就假设损失函数越大，模型越容易出错）。如果我们的模型能够让损失函数持续的下降，则说明我们的模型在不停的改进，而最好的方式就是让损失函数在其梯度（Gradient)的方向上下降。

    下面的内容就是用数学的方式来描述Gradient Boosting，数学上不算太复杂，只要潜下心来看就能看懂：）

    可加的参数的梯度表示：

    假设我们的模型能够用下面的函数来表示，P表示参数，可能有多个参数组成，P = {p0,p1,p2….}，F(x;P)表示以P为参数的x的函数，也就是我们的预测函数。我们的模型是由多个模型加起来的，β表示每个模型的权重，α表示模型里面的参数。为了优化F，我们就可以优化{β,α}也就是P。

    我们还是用P来表示模型的参数，可以得到，Φ(P)表示P的likelihood函数，也就是模型F(x;P)的loss函数，Φ(P)=…后面的一块看起来很复杂，只要理解成是一个损失函数就行了，不要被吓跑了。

   既然模型(F(x;P))是可加的，对于参数P，我们也可以得到下面的式子：   这样优化P的过程，就可以是一个梯度下降的过程了，假设当前已经得到了m-1个模型，想要得到第m个模型的时候，我们首先对前m-1个模型求梯度。得到最快下降的方向，gm就是最快下降的方向。

    这里有一个很重要的假设，对于求出的前m-1个模型，我们认为是已知的了，不要去改变它，而我们的目标是放在之后的模型建立上。就像做事情的时候，之前做错的事就没有后悔药吃了，只有努力在之后的事情上别犯错：

    我们得到的新的模型就是，它就在P似然函数的梯度方向。ρ是在梯度方向上下降的距离。

    我们最终可以通过优化下面的式子来得到最优的ρ：

    可加的函数的梯度表示：

    上面通过参数P的可加性，得到了参数P的似然函数的梯度下降的方法。我们可以将参数P的可加性推广到函数空间，我们可以得到下面的函数，此处的fi(x)类似于上面的h(x;α)，因为作者的文献中这样使用，我这里就用作者的表达方法：

    同样，我们可以得到函数F(x)的梯度下降方向g(x)

    最终可以得到第m个模型fm(x)的表达式:

    通用的Gradient Descent Boosting的框架：

   下面我将推导一下Gradient Descent方法的通用形式，之前讨论过的：

    对于模型的参数{β,α}，我们可以用下面的式子来进行表示，这个式子的意思是，对于N个样本点(xi,yi)计算其在模型F(x;α,β)下的损失函数，最优的{α,β}就是能够使得这个损失函数最小的{α,β}。 表示两个m维的参数：

    写成梯度下降的方式就是下面的形式，也就是我们将要得到的模型fm(x)的参数{αm,βm}能够使得fm的方向是之前得到的模型Fm-1(x)的损失函数下降最快的方向：

    对于每一个数据点xi都可以得到一个gm(xi)，最终我们可以得到一个完整梯度下降方向

    为了使得fm(x)能够在gm(x)的方向上，我们可以优化下面的式子得到，可以使用最小二乘法：

    得到了α的基础上，然后可以得到βm。       最终合并到模型中：

    算法的流程图如下

     之后，作者还说了这个算法在其他的地方的推广，其中，Multi-class logistic regression and classification就是GBDT的一种实现，可以看看，流程图跟上面的算法类似的。这里不打算继续写下去，再写下去就成论文翻译了，请参考文章：Greedy function Approximation – A Gradient Boosting Machine，作者Freidman。

总结：

    本文主要谈了谈Boosting与Gradient Boosting的方法，Boosting主要是一种思想，表示“知错就改”。而Gradient Boosting是在这个思想下的一种函数（也可以说是模型）的优化的方法，首先将函数分解为可加的形式（其实所有的函数都是可加的，只是是否好放在这个框架中，以及最终的效果如何）。然后进行m次迭代，通过使得损失函数在梯度方向上减少，最终得到一个优秀的模型。值得一提的是，每次模型在梯度方向上的减少的部分，可以认为是一个“小”的或者“弱”的模型，最终我们会通过加权(也就是每次在梯度方向上下降的距离）的方式将这些“弱”的模型合并起来，形成一个更好的模型。

    有了这个Gradient Descent这个基础，还可以做很多的事情。也在机器学习的道路上更进一步了：）

版权声明：

本文发布于http://thinkbot.info。如果转载，请注明出处，在未经作者同意下将本文用于商业用途，将追究其法律责任。如果有问题，请联系作者 wheeleast@gmail.com

前言：

距离上次发文章，也快有半个月的时间了，这半个月的时间里又在学习机器学习的道路上摸索着前进，积累了一点心得，以后会慢慢的写写这些心得。写文章是促进自己对知识认识的一个好方法，看书的时候往往不是非常细，所以有些公式、知识点什么的就一带而过，里面的一些具体意义就不容易理解了。而写文章，特别是写科普性的文章，需要对里面的具体意义弄明白，甚至还要能举出更生动的例子，这是一个挑战。为了写文章，往往需要把之前自己认为看明白的内容重新理解一下。

机器学习可不是一个完全的技术性的东西，之前和部门老大在outing的时候一直在聊这个问题，机器学习绝对不是一个一个孤立的算法堆砌起来的，想要像看《算法导论》这样看机器学习是个不可取的方法，机器学习里面有几个东西一直贯穿全书，比如说数据的分布、最大似然（以及求极值的几个方法，不过这个比较数学了），偏差、方差的权衡，还有特征选择，模型选择，混合模型等等知识，这些知识像砖头、水泥一样构成了机器学习里面的一个个的算法。想要真正学好这些算法，一定要静下心来将这些基础知识弄清楚，才能够真正理解、实现好各种机器学习算法。

今天的主题是线性回归，也会提一下偏差、方差的均衡这个主题。

线性回归定义：

在上一个主题中，也是一个与回归相关的，不过上一节更侧重于梯度这个概念，这一节更侧重于回归本身与偏差和方差的概念。

回归最简单的定义是，给出一个点集D，用一个函数去拟合这个点集，并且使得点集与拟合函数间的误差最小。

上图所示，给出一个点集(x,y), 需要用一个函数去拟合这个点集，蓝色的点是点集中的点，而红色的曲线是函数的曲线，第一张图是一个最简单的模型，对应的函数为y = f(x) = ax + b，这个就是一个线性函数，

第二张图是二次曲线，对应的函数是y = f(x) = ax^2 + b。

第三张图我也不知道是什么函数，瞎画的。

第四张图可以认为是一个N次曲线，N = M – 1，M是点集中点的个数，有一个定理是，对于给定的M个点，我们可以用一个M – 1次的函数去完美的经过这个点集。

真正的线性回归，不仅会考虑使得曲线与给定点集的拟合程度最好，还会考虑模型最简单，这个话题我们将在本章后面的偏差、方差的权衡中深入的说，另外这个话题还可以参考我之前的一篇文章：贝叶斯、概率分布与机器学习，里面对模型复杂度的问题也进行了一些讨论。

线性回归(linear regression)，并非是指的线性函数，也就是

（为了方便起见，以后向量我就不在上面加箭头了）

x0,x1…表示一个点不同的维度，比如说上一节中提到的，房子的价钱是由包括面积、房间的个数、房屋的朝向等等因素去决定的。而是用广义的线性函数：

wj是系数，w就是这个系数组成的向量，它影响着不同维度的Φj(x)在回归函数中的影响度，比如说对于房屋的售价来说，房间朝向的w一定比房间面积的w更小。Φ(x)是可以换成不同的函数，不一定要求Φ(x)=x，这样的模型我们认为是广义线性模型。

最小二乘法与最大似然：

这个话题在此处有一个很详细的讨论，我这里主要谈谈这个问题的理解。最小二乘法是线性回归中一个最简单的方法，它的推导有一个假设，就是回归函数的估计值与真实值间的误差假设是一个高斯分布。这个用公式来表示是下面的样子： ，y(x,w)就是给定了w系数向量下的回归函数的估计值，而t就是真实值了，ε表示误差。我们可以接下来推出下面的式子：

这是一个简单的条件概率表达式，表示在给定了x，w，β的情况下，得到真实值t的概率，由于ε服从高斯分布，则从估计值到真实值间的概率也是高斯分布的，看起来像下面的样子：

贝叶斯、概率分布与机器学习这篇文章中对分布影响结果这个话题讨论比较多，可以回过头去看看，由于最小二乘法有这样一个假设，则会导致，如果我们给出的估计函数y(x,w)与真实值t不是高斯分布的，甚至是一个差距很大的分布，那么算出来的模型一定是不正确的，当给定一个新的点x’想要求出一个估计值y’，与真实值t’可能就非常的远了。

概率分布是一个可爱又可恨的东西，当我们能够准确的预知某些数据的分布时，那我们可以做出一个非常精确的模型去预测它，但是在大多数真实的应用场景中，数据的分布是不可知的，我们也很难去用一个分布、甚至多个分布的混合去表示数据的真实分布，比如说给定了1亿篇网页，希望用一个现有的分布（比如说混合高斯分布）去匹配里面词频的分布，是不可能的。在这种情况下，我们只能得到词的出现概率，比如p(的)的概率是0.5，也就是一个网页有1/2的概率出现“的”。如果一个算法，是对里面的分布进行了某些假设，那么可能这个算法在真实的应用中就会表现欠佳。最小二乘法对于类似的一个复杂问题，就很无力了

偏差、方差的权衡(trade-off)：

偏差(bias)和方差(variance)是统计学的概念，刚进公司的时候，看到每个人的嘴里随时蹦出这两个词，觉得很可怕。首先得明确的，方差是多个模型间的比较，而非对一个模型而言的，对于单独的一个模型，比如说:

这样的一个给定了具体系数的估计函数，是不能说f(x)的方差是多少。而偏差可以是单个数据集中的，也可以是多个数据集中的，这个得看具体的定义。

方差和偏差一般来说，是从同一个数据集中，用科学的采样方法得到几个不同的子数据集，用这些子数据集得到的模型，就可以谈他们的方差和偏差的情况了。方差和偏差的变化一般是和模型的复杂程度成正比的，就像本文一开始那四张小图片一样，当我们一味的追求模型精确匹配，则可能会导致同一组数据训练出不同的模型，它们之间的差异非常大。这就叫做方差，不过他们的偏差就很小了，如下图所示：

上图的蓝色和绿色的点是表示一个数据集中采样得到的不同的子数据集，我们有两个N次的曲线去拟合这些点集，则可以得到两条曲线（蓝色和深绿色），它们的差异就很大，但是他们本是由同一个数据集生成的，这个就是模型复杂造成的方差大。模型越复杂，偏差就越小，而模型越简单，偏差就越大，方差和偏差是按下面的方式进行变化的:

当方差和偏差加起来最优的点，就是我们最佳的模型复杂度。

用一个很通俗的例子来说，现在咱们国家一味的追求GDP，GDP就像是模型的偏差，国家希望现有的GDP和目标的GDP差异尽量的小，但是其中使用了很多复杂的手段，比如说倒卖土地、强拆等等，这个增加了模型的复杂度，也会使得偏差（居民的收入分配）变大，穷的人越穷(被赶出城市的人与进入城市买不起房的人），富的人越富（倒卖土地的人与卖房子的人）。其实本来模型不需要这么复杂，能够让居民的收入分配与国家的发展取得一个平衡的模型是最好的模型。

最后还是用数学的语言来描述一下偏差和方差：

E(L)是损失函数，h(x)表示真实值的平均，第一部分是与y（模型的估计函数）有关的，这个部分是由于我们选择不同的估计函数（模型）带来的差异，而第二部分是与y无关的，这个部分可以认为是模型的固有噪声。

对于上面公式的第一部分，我们可以化成下面的形式：

这个部分在PRML的1.5.5推导，前一半是表示偏差，而后一半表示方差，我们可以得出：损失函数=偏差^2+方差+固有噪音。

下图也来自PRML：

这是一个曲线拟合的问题，对同分布的不同的数据集进行了多次的曲线拟合，左边表示方差，右边表示偏差，绿色是真实值函数。ln lambda表示模型的复杂程度，这个值越小，表示模型的复杂程度越高，在第一行，大家的复杂度都很低（每个人都很穷）的时候，方差是很小的，但是偏差同样很小（国家也很穷），但是到了最后一幅图，我们可以得到，每个人的复杂程度都很高的情况下，不同的函数就有着天壤之别了（贫富差异大），但是偏差就很小了（国家很富有）。

预告：

接下来准备谈谈线性分类的一些问题，敬请关注：）

本文由LeftNotEasy原创，可以转载，但请保留此行。如果有问题，请联系作者 wheeleast@gmail.com

一. 简单的说贝叶斯定理：

贝叶斯定理用数学的方法来解释生活中大家都知道的常识

形式最简单的定理往往是最好的定理，比如说中心极限定理，这样的定理往往会成为某一个领域的理论基础。机器学习的各种算法中使用的方法，最常见的就是贝叶斯定理。

贝叶斯定理的发现过程我没有找到相应的资料，不过我相信托马斯.贝叶斯(1702-1761)是通过生活中的一些小问题去发现这个对后世影响深远的定理的，而且我相信贝叶斯发现这个定理的时候，还不知道它居然有这么大的威力呢。下面我用一个小例子来推出贝叶斯定理：

已知：有N个苹果，和M个梨子，苹果为黄色的概率为20%，梨子为黄色的概率为80%，问，假如我在这堆水果中观察到了一个黄色的水果，问这个水果是梨子的概率是多少。

用数学的语言来表达，就是已知P(apple) = N / (N + M), P(pear) = M / (N + M), P(yellow|apple) = 20%, P(yellow|pear) = 80%, 求P(pear|yellow).

要想得到这个答案，我们需要 1. 要求出全部水果中为黄色的水果数目。 2. 求出黄色的梨子数目

对于1) 我们可以得到 P(yellow) * (N + M), P(yellow) = p(apple) * P(yellow|apple) + P(pear) * p(yellow|pear)

对于2) 我们可以得到 P(yellow|pear) * M

2) / 1) 可得：P(pear|yellow) = P(yellow|pear) * p(pear) / [P(apple) * P(yellow|apple) + P(pear) * P(yellow|pear)]

化简可得：P(pear|yellow) = P(yellow,pear) / P(yellow), 用简单的话来表示就是在已知是黄色的，能推出是梨子的概率P(pear|yellow)是黄色的梨子占全部水果的概率P(yellow,pear)除上水果颜色是黄色的概率P(yellow). 这个公式很简单吧。

我们将梨子代换为A，黄色代换为B公式可以写成：P(A|B) = P(A,B) / P(B), 可得：P(A,B) = P(A|B) * P(B).贝叶斯公式就这样推出来了。

本文的一个大概的思路：先讲一讲我概括出的一个基本的贝叶斯学习框架，然后再举几个简单的例子说明这些框架，最后再举出一个复杂一点的例子，也都是以贝叶斯机器学习框架中的模块来讲解

二. 贝叶斯机器学习框架

对于贝叶斯学习，我每本书都有每本书的观点和讲解的方式方法，有些讲得很生动，有些讲得很突兀，对于贝叶斯学习里面到底由几个模块组成的，我一直没有看到很官方的说法，我觉得要理解贝叶斯学习，下面几个模块是必须的：

1) 贝叶斯公式

机器学习问题中有一大类是分类问题，就是在给定观测数据D的情况下，求出其属于类别（也可以称为是假设h，h ∈ {h0, h1, h2…})的概率是多少, 也就是求出:

P(h|D), 可得：

P(h,D) = P(h|D) * P(D) = P(D|h) * P(h), 所以：P(h|D) = P(D|h) * P(h) / P(D), 对于一个数据集下面的所有数据，P(D)，恒定不变。所以可以认为P(D)为常数， 得到：P(h|D) ∝ P(D|h) * P(h)。我们往往不用知道P(h|D)的具体的值，而是知道例如P(h1|D)，P(h2|D)值的大小关系就是了。这个公式就是机器学习中的贝叶斯公 式，一般来说我们称P(h|D)为模型的后验概率，就是从数据来得到假设的概率，P(h)称为先验概率，就是假设空间里面的概率，P(D|h)是模型的 likelihood概率。

Likelihood（似然）这个概率比较容易让人迷惑，可以认为是已知假设的情况下，求出从假设推出数据的概率，在实际的机器学习过程中，往往加入了很多的假设，比如一个英文翻译法文的问题：

给出一个英文句子，问哪一个法文句子是最靠谱的，P(f=法文句子|e=英文句子) = P(e|f) * p(f), p(e|f)就是likelihood函数，P(e|f) 写成下面的更清晰一点：p(e|f∈{f1,f2…})可以认为，从输入的英文句子e，推出了很多种不同的法文句子f，p(e|f)就是从这些法文句子中的某一个推出原句子e的概率。

本文之后的内容也将对文章中没有提到的一些内容，也是贝叶斯学习中容易疑惑、忽略、但是很重要的问题进行一些解释。

2) 先验分布估计，likelihood函数选择

贝叶斯方法中，等号右边有两个部分，先验概率与likelihood函数。先验概率是得到，在假设空间中，某一个假设出现的概率是多少，比如说在街上看到一个动物是长有毛的，问1. 这个动物是哈巴狗的概率是多少，2. 这个动物是爪哇虎的概率是多少, 见下图：

虽然两个假设的likelihood函数都非常的接近于1（除非这个动物病了），但是由于爪哇虎已经灭绝了，所以爪哇虎的先验概率为0，所以P(爪哇虎|有毛的动物)的概率也为0。

先验概率分布估计

在观测的时候，对于变量是连续的情况下，往往需要一个先验分布来得到稀疏数据集中没有出现过的，给出的某一个假设，在假设空间中的概率。比如说有一个很大很大的均匀金属圆盘，问这个金属圆盘抛到空中掉下来，正面朝上的概率，这个实验的成本比较高（金属圆盘又大又重），所以只能进行有限次数的实验，可能出现的是，正面向上4次，反面向上1次，但是我们如果完全根据这个数据集去计算先验概率，可能会出现很大的偏差。不过由于我们已知圆盘是均匀的，我们可以根据这个知识，假设P(X=正面) = 0.5。

我们有的时候，已知了分布的类型，但是不知道分布的参数，还需要根据输入的数据，对分布的参数进行估计、甚至对分布还需要进行一些修正，以满足我们算法的需求：比如说我们已知某一个变量x的分布是在某一个连续区间均匀分布，我们观察了1000次该变量，从小到大排序结果是：1,1.12,1.5 … 199.6, 200, 那我们是否就可以估计变量的分布是从[1,200]均匀分布的？如果出现一个变量是0.995，那我们就能说P(0.995) = 0？如果出现一个200.15怎么办呢？所以我们这个时候可能需要对概率的分布进行一定的调整，可能在x<1,x>200的范围内的概率是一个下降的直线，整个概率密度函数可能是一个梯形的，或者对区域外的值可以给一个很小很小的概率。这个我在之后还将会举出一些例子来说明。

Likelihood函数选择

对于同一个模型，likelihood函数可能有不同的选择，对于这些选择，可能有些比较精确、但是会搜索非常大的空间，可能有些比较粗糙，但是速度会比较快，我们需要选择不同的likelihood函数来计算后验概率。对于这些Likelihood函数，可能还需要加上一些平滑等技巧来使得最大的降低数据中噪声、或者假设的缺陷对结果的影响。

我所理解的用贝叶斯的方法来估计给定数据的假设的后验概率，就是通过prior * likelihood，变换到后验分布。是一个分布变换的过程。

3) loss function(损失函数)

x是输入的数据，y(x)是推测出的结果的模型，t是x对应的真实结果，L(t,y(x))就是loss function，E[L]表示使用模型y进行预测，使用L作为损失函数的情况下，模型的损失时多少。通常来说，衡量一个模型是否能够准确的得到结果，损失函数是最有效的一个办法，最常用、最简单的一种损失函数是：

不过我一直不知道为什么这里用的平方，而不是直接用绝对值，有详细一点的解释吗？:-p

4) Model Selection(模型选择)

前文说到了对于likelihood函数可以有不同的选择，对于先验的概率也可以有不同的选择，不过假设我们一个构造完整的测试集和一个恰当的损失函数，最终的结果将会是确定的，量化的，我们很容易得到两个不同参数、方法的模型的优劣性。不过通常情况下，我们的测试集是不够完整，我们的损失函数也是不那么 的精确，所以对于在这个测试集上表现得非常完美的模型，我们常常可能还需要打一个问号，是否是训练集和测试集过于相像，模型又过于复杂。导致了over- fitting（后文将会详细介绍over-fitting的产生）？

Model Selection本质上来说是对模型的复杂度与模型的准确性做一个平衡，本文后面将有一些类似的例子。

Example 1：Sequential 概率估计

注：此例子来自PRML chapter 2.1.1

对于概率密度的估计，有很多的方法，其中一种方法叫做Sequential 概率估计。

这种方法是一个增量的学习过程，在每看到一个样本的时候都是把之前观测的数据作为先验概率，然后在得到新数据的后验概率后，再把当前的后验概率作为下一次预测时候的先验概率。

传统的二项式分布是：

由于传统的二项式分布的概率μ是完全根据先验概率而得到的，而这个先验分布之前也提到过，可能会由于实验次数不够而有很大的偏差，而且，我们无法得知μ的分布，只知道一个μ的期望，这样对于某些机器学习的方法是不利的。为了减少先验分布对μ的影响，获取μ的分布，我们加入了两个参数，a，b，表示X=0与X=1的出现的次数，这个取值将会改变μ的分布，beta分布的公式如下：

对于不同a，b的取值，将会对μ的概率密度函数产生下面的影响：（图片来自PRML）

在观测数据的过程中，我们可以随时的利用观测数据的结果，改变当前μ的先验分布。我们可以将Beta分布加入两个参数，m，l，表示观测到的X=0，X=1的次数。（之前的a，b是一个先验的次数，不是当前观测到的）

我们令：

a’，b’表示加入了观测结果的新的a，b 。带入原式，可以得到

我们可以利用观测后的μ后验概率更新μ的先验概率，以进行下一次的观测，这样对不时能够得到新的数据，并且需要real-time给出结果的情况下很有用。不过Sequential方法有对数据一个i.i.d（独立同分布）的假设。要求每次处理的数据都是独立同分布的。

Example 2：拼写检查

这篇文章的中心思想来自：怎样写一个拼写检查器，如果有必要，请参见原文，本例子主要谈谈先验分布对结果的影响。

直接给出拼写检查器的贝叶斯公式：

P(c|w) 表示，单词w(wrong)正确的拼写为单词c(correct)的概率，P(w|c)表示likelihood函数，在这里我们就简单的认 为，两个单词的编辑距离就是它们之间的likelihood，P(c)表示，单词c在整体文档集合中的概率，也就是单词c的先验概率。

我们在做单词拼写检查的时候肯定会直观的考虑：如果用户输入的单词如果在字典中没有出现过，则应该将其修正为一个字典中出现了的，而且与用户输入最接近的词；如果用户输入的词在字典中出现过了，但是词频非常的小，则我们可以为用户推荐一个比较接近这个单词，但是词频比较高的词。

先验概率 P(c)的统计是一个很重要的内容，一般来说有两种可行的办法，一种是利用某些比较权威的词频字典，一种是在自己的语料库（也就是待进行拼写检查的语料）中进行统计。我建议是用后面的方法进行统计，这样词的先验概率才会与测试的环境比较匹配。比如说一个游戏垂直搜索网站需要对用户输入的信息进行拼写纠正，那么使用通用环境下统计出的先验概率就不太适用了。

Example 3：奥卡姆剃刀与Model Selection

给出下面的一个图：（来自Mackey的书）

问：大树背后有多少个箱子？

其实，答案肯定是有很多的，一个，两个，乃至N箱子都是有可能的（比如说后面有一连排的箱子，排成一条直线），我们只能看到第一个：

但是，最正确，也是最合理的解释，就是一个箱子，因为如果大树背后有两个乃至多个箱子，为什么从大树正面看起来，两边的高度一样，颜色也一样，这样是不是太巧合了。如果我们的模型根据这张图片，告诉我们大树背后最有可能有两个箱子，这样的模型的泛化能力是不是太差了。

所以说，本质上来说，奥卡姆剃刀，或者模型选择，也是人生活中的一种通常行为的数学表示，是一种化繁为简的过程。数学之美番外篇：平凡而又神奇的贝叶斯方法这篇文章中说的，奥卡姆剃刀工作在likelihood上，对于模型的先验分布并没有什么影响。我这里不太同意这个说法：奥卡姆剃刀是剪掉了复杂的模型，复杂的模型也是不常见的、先验概率比较低的，最终的结果是选择了先验概率比较高的模型。

Example 4: 曲线拟合:

（该例子来自PRML)

问题：给定一些列的点，x = {x1,x2…xn}, t = {t1,t2 .. tn}, 要求用一个模型去拟合这个观测，能够使得给定一个新点x’, 能够给出一个t’.

已知给定的点是由y=2πx加上正态分布的噪声而得到的10个点，如上图。为了简单起见，我们用一个多项式去拟合这条曲线:

为了验证我们的公式是否正确，我们加入了一个loss function：

在loss function最小的情况下，我们绘制了不同维度下多项式生成的曲线：

在M值增高的情况下，曲线变得越来越陡峭，当M=9的时候，该曲线除了可以拟合输入样本点外，对新进来的样本点已经无法预测了。我们可以观测一下多项式的系数：

可以看出，当M（维度）增加的时候，系数也膨胀得很厉害，为了消除这个系数带来的影响，我们需要简化模型，我们为loss function加入一个惩罚因子：

我们把w的L2距离乘上一个系数λ加入新的loss function中，这就是一个奥卡姆剃刀，把原本复杂的系数变为简单的系数（如果要更具体的量化的分析，请见PRML 1.1节）。如果我们要考虑如何选择最合适的维度，我们也可以把维度作为一个loss function的一部分，这就是Model Selection的一种。

但是这个问题还没有解决得很好，目前我们得到的模型只能预测出一个准确的值：输入一个新的x，给出一个t，但是不能描述t有什么样的概率密度函数。概率密度函数是很有用的。假如说我们的任务修正为，给出N个集合，每个集合里面有若干个点，表示一条曲线，给出一个新的点，问这个新的点最可能属于哪一条曲线。如果我们仅仅用新的点到这些曲线的距离作为一个衡量标准，那很难得到一个比较有说服力的结果。为了能够获取t值的一个分布，我们不妨假设t属于一个均值为y(x),方差为 1/β的一个高斯分布：

在之前的E(w)，我们加入了一个w的L2距离，这个看起来有一点突兀的感觉，为什么要加上一个这样的距离呢？为什么不是加入一个其他的东西。我们可以用一个贝叶斯的方法去替代它，得到一个更有说服力的结果。我们令p(w)为一个以0为均值，α为方差的高斯分布，这个分布为w在0点附近密度比较高，作为w的先验概率，这样在计算最大化后验概率的时候，w的绝对值越小，后验概率将会越大。

我们可以得到新的后验概率：

这个式子看起来是不是有点眼熟啊？我们令λ=α/β，可以得到类似于之前损失函数的一个结果了。我们不仅还是可以根据这个函数来计算最优的拟合函数，而且可以得到相应的一个概率分布函数。可以为机器学习的很多其他的任务打下基础。

这里还想再废话一句，其实很多机器学习里面的内容都与本处所说的曲线拟合算法类似，如果我们不用什么概率统计的知识，可以得到一个解决的方案，就像我们的第一个曲线拟合方案一样，而且还可以拟合得很好，不过唯一缺少的就是概率分布，有了概率分布可以做很多的事情。包括分类、回归等等都需要这些东西。从本质上来说，Beta分布和二项式分布，Dirichlet分布和多项式分布，曲线拟合中直接计算w和通过高斯分布估计w，都是类似的关系：Beta分布和 Dirichlet分布提供的是μ的先验分布。有了这个先验分布，我们可以去更好的做贝叶斯相关的事情。

参考资料：

数学之美番外篇：平凡而又神奇的贝叶斯方法, Pongba

Pattern Recognition and Machine Learning, Bishop

一些Wikipedia上面的内容

简介

     网页排名（PageRank或PR）是搜索引擎用户体验的核心成分之一。之前Google的吴军博士曾经在他的《数学之美》系列文章中用一句很通俗的话总结了网页排名的核心思想：“在互联网上，如果一个网页被很多其它网页所链接，说明它受到普遍的承认和信赖，那么它的排名就高”。PR值代表了一个网页的重要程度。而它的重要程度又和与链接到它的网页的重要程度有关，所以网页排名的计算是一个迭代的过程。

PageRank值

      虽然Google不是最早对网页进行排序，归类的公司，但是它的两个创始人Larry Page和Sergey Brin最早提出了现在被广泛用于各大搜索引擎的网页排名算法的原型（见参考文献2）。

      下面我们在互联网这张大图上截取一小部分，如下图所示：

     上图中共有四个节点（Page），其中周围的三个节点的PR值已知，且它们都有到中部节点的链接。现在我们需要计算中间那个网页的排名值。在计算之前，需要说明的是用户在互联网上浏览网页，点击链接的行为我们认为是随机事件。通常认为用户在一个网页选择点击链接继续浏览的概率是一定的，在Larry和Sergey（见参考文献1）的论文中这个概率取的是0.85，也就是说有0.15的概率用户选择留在当前页面不在继续浏览。而一旦用户选择跳转时，其选择跳转到特定页面的概率应当为：1/外部链接总数。  例如上图中左侧节点发生点击，链接到中心节点的概率应为0.25，因为它有4个外部链接。所以，可以用网民最终（直接或者间接）到达某个网页的概率作为该网页排名的基础，即PR值。很容易想到，上图中心节点的PR值应当为：

0.15+0.85(1/4+1/3+1/1) —-（1）

      上面的答案看似不错，但是问题是往往我们需要对来自重要网页（PR值高的网页）的链接要看得重要一些，换句话说，通常认为好网站链接的也是好网站。看来我们需要考虑这些链接中哪些是来自好网站的了，我们需要重要程度高的网页其链接贡献的比重大一些。所以要引入已知节点本身的PR值（即其重要性），所以（1）式变成了：

PR(?) = 0.15+0.85[0.4 * (1/4) + 0.3 * (1/3) + 0.5 * (1/1)] = 0.745

       从这里也可以看到，贡献最大的还是上方的节点，一方面他PR值高，一方面它有且仅有一个到要求节点的链接。可以想象Google在首页链接了（且仅链接了）你的个人网站的效应;-)

      你也许会问，这里周围链接网页的PR值已经知道了，但是实际上互联网上每天都有不计其数的新网页被搜索引擎的爬虫抓取到，不可能都预知其真实的PR值。没错，不过Larry和Sergey已经从理论上证明了，经过多次迭代，不论初始PR值如何选取，这种算法都保证了网页排名的估计值能收敛到他们的真实值。

学习优化

      前面我们假设了用户浏览网页是随机行为，但实际上用户不可能在搜索结果里面随机点选链接，一个神志清醒的用户选择的一定是最满足他要求的结果，可以认为在某关键词下，搜索引擎提供的结果中，被用户选择的次数越多，那么那条结果就越重要，越要排在靠前的位置。所以接下来，我们需要设定一个反馈机制，来跟踪用户的点击行为，分析用户的意图，为以后的查询结果提供更准确的排名。在众多的学习机制中，具有非线性适应性信息处理能力的人工神经网络无疑是一个不错的选择。下面我们以多层感知器（一种多层前向神经网络）为例，看看在这个模型下如何优化网页排名。

      下图是一个多层感知器结构示意图（这里只用到了三层），输入层是所有的查询词汇表，比如“苹果”，“公司”，“iPhone”等等，隐含层是某些词汇的集合，也就是用户键入的关键字组合，比如“苹果公司”，“苹果iPhone”。输出层是返回的URL列表。

      这个网络是如何学习的呢？下面以搜索“苹果 公司”为例，当用户以关键词“苹果 公司”来搜索时，输入层的“苹果”和“公司”两个词被激活，试图作用于隐含层的“苹果公司”，当无数个用户一次又一次把“苹果”和“公司”两个词放一起进行查询的时候，隐含层的“苹果公司”这一项被激活。然后“苹果公司”这一项又会去激活输出层的URL列表，在输出层激活函数的作用下，这些URL会处于不同的激活程度。注意图中的粗线表示连接的强度很高。激活程度越高，就表示该URL和原始查询关键词的关联程度越高。而通过记录用户对最终结果的选择，上述网络会按照某些学习算法如著名的反向传播学习算法(backpropagation)，对激活程度和关联权值进行调节。从而使得该神经网络提供的结果越来越接近用户的真实需求。比如，大多数人在搜索“苹果 公司”之后，会选择位于美国加州的苹果股份有限公司的网站，而不是一家卖苹果的公司。于是从隐含层“苹果公司”到苹果公司URL（www.apple.com）的关联会加强。

      当然，真实的训练算法和学习策略要远比这还要复杂得多，最终的网页排名可能是多个策略混合的结果。不过可以放心，这些算法的复杂性并不会影响到你使用搜索引擎的体验，毫无疑问，在你查询之前，这个网络已经被训练过无数次。查询引擎只需要从缓存的PageRank中读出来前若干条列表即可。搜索引擎会在记录了大量的用户选择的数据之后，定期或者不定期的对上述神经网络进行训练，对网页排名进行更新。

      最后，关于网页排名的未来，我觉得它是和整个搜索引擎的革命分不开的。一方面是永恒的性能，要知道像BP这种训练神经网络的算法，都是非常耗时的消耗型算法。未来可能需要更先进的并行硬件，更庞大的集群和集群间高效稳定的通信机制。去年贺牛在（WWW09）上发表了一篇用GPU做信息检索的文章，很有趣。GPU现在用于各种科学计算和数据挖掘蔚然成风。另一方面，许多现在由计算机集群做的事情，未来可能交给芯片集群和计算网络去做，比如网页解析交给一堆FPGA去做，衍生出更多的搜索引擎硬件从而取代或者部分取代功耗高效率低的服务器集群。毕竟节能也是搜索引擎未来的一大主题。

参考文献

1. S Brin, L Page, The anatomy of a large-scale hypertextual Web search engine, Computer networks and ISDN systems, 1998
2. Page, Lawrence and Brin, Sergey and Motwani, Rajeev and Winograd, Terry, The PageRank Citation Ranking: Bringing Order to the Web. Technical Report. Stanford InfoLab, 1999
3. 吴军, 谈 Page Rank – Google 的民主表决式网页排名技术, 2006
4. http://en.wikipedia.org/wiki/Multilayer_perceptron
5. http://en.wikipedia.org/wiki/Backpropagation

Author: rocky AT thinkbot.info

0.推荐+=服务

      互联网已经不再是一个单单的获取信息的工具，它已经逐渐成为我们生活中很重要的一个成分。所有能在互联网上赚取人们好感的应用都是有意或者不经意地为人们提供各种各样的服务，而且这些服务越来越贴近我们的生活，越来越个性化。一个简单的例子就是推荐服务。比如推荐你可能感兴趣的书籍，推荐和你兴趣相投的朋友和你认识等等。

1.关系衡量

      要做出任何有趣的推荐，首先必须了解某些样本之间的关系，也就是说推荐的内容和推荐的目标对象之间一定是有某种（可能的）关系。这样的关系可能是两个兴趣相投的人，也可以是相关两个商品的价格等等。衡量这样的两组变量（样本）之间的关系有很多种办法，最简单的就是计算两组变量的欧式距离。用Python实现一个嵌套的字典空间内的欧式距离只需要一行代码：

def eudistance(D,p1,p2):
    return 1/(1+sum([pow(D[p1][i]-D[p2][i],2) for i in D[p1] if i in D[p2]]))

      然而，欧式距离计算的是n维空间的绝对距离，它有时候并不是很有效，比如欧式距离不能判断人们的多属性习惯，即使两个人的偏好反映在欧式空间下是平行的两组向量，他们的欧式距离仍然可能很大。这时候，就需要更加general的方法来判断相关性了，计算相关系数是十分流行的一种方法。

2.相关系数

      通常说样本的相关系数全称叫皮尔森积矩相关系数(Pearson product-moment correlation coefficient) ，是一种线性相关系数。在统计学中，常用来描述两组变量的线性相关程度。相关系数通常记做r，是一个位于[-1,1]的区间内的值。r=1时，表示两变量完全线性正相关；r=0的时候，表示两变量间无线性相关关系；r=-1的时候，表示两变量完全线性负相关。更通俗点，就是说|r|=1的时候两组变量之间可以用某个线性方程来描述。通常|r|大于0.75时，认为两个变量有很强的线性相关性。皮尔森相关系数的可用两组样本的协方差（分子）和标准差之积的商来定义：

      为了方便编程计算，将上式的分子分母乘开后化简，可以得到：

      从变换后的式子不难得到一个结论，就是对X，或者Y进行任何线性变换（比如X变成a + bX ）都不会改变相关系数的值，这也是它和前面所说欧式距离的一个显著区别。

      知道了相关系数，似乎我们已经可以做一些简单的推荐服务了，比如推荐一些和你趣味相投的人，你们的品味差不多，比如你们在豆瓣上面的记录显示你们看过很多同样的书，而且你们对这些书的评价标准很接近。经过计算你们对共同目标评价的相关系数，可以选择某几个和你最相近的人（r值较大）作为好友推荐给你。

3.推荐商品

      相对而言，推荐商品在很多情况下要比推荐好友稍微麻烦一点。以豆瓣为例，假设要为rocky推荐一本书，比较简单的做法如下：

      首先，挑出好友们看过，而rocky尚未看过的一些书。假设我们已经按前面提到的方法计算出了rocky的好友们与他的相关系数，为了减少计算量，你也可以只挑相关度较高的一群好友。然后，我们把那些相关系数系数作为权值乘上相应好友们给这些书的评分（1到5星）。然后我们把这里每一本书的评分加起来，按总分高低排序，似乎已经可以给出一个推荐的清单了。

     你很可能已经想到，这样的方式会存在一个问题，就是rocky的好友们看过的书很多，但不是每一本都被所有好友看过，如果按照上面的方法计算总分，那么看过的人多的书得分会比较高。但是有可能少数两个和你相似度很高的朋友看过的一本书其实更适合你。为了解决这个问题，我们可以增加一个分母，它是看过该书的所有好友相似度的和。用一个公式表示就是：           接下来按这个推荐分排序，就可以对rocky给出一个推荐的书籍列表了。不过给出推荐的方法不只一种，还有很多基于统计学习的方法。您有什么独特的想法也可以在留言中与我交流。要说明的是，虽然我这里拿豆瓣作例子，但是并不代表豆瓣的推荐都是按这种方法进行的。

4.联想推荐

      前面提到的给rocky推荐书的方法有个前提，就是必须已知rocky有足够多的朋友看过足够多的书。这很显然，因为如果rocky只有两三个好友，样本太少，推荐的效果是不明显的。如何能在rocky刚加入豆瓣不久就提供一些有用的推荐呢？

      一种办法是让我们回到第一部分提到的相关系数。我们假设用户的品味是大致平稳的，那么如果rocky加入豆瓣不久看了一本书，那么我们可以把与这本书相关系数较高的另一本书推荐给他。而这本书的相关系数则是来自我们对已知的海量数据不断分析的结果。然后这个海量数据集的更新可以不用特别频繁，用户每次访问只需在当前缓存的推荐项列表中查找即可。不必为每个用户都进行一次全数据集遍历。这种方法叫基于项的推荐（item-based recommandation），我习惯称之为联想推荐。

      较好的推荐服务其联想推荐都是会和前面的方法并用的，至少是在了解用户的过程中，在不同阶段分别使用。这样才能多方位的，多层次的提供一些推荐给用户。

5.动动手

      利用豆瓣API你已经可以获取到，用户的朋友，和对某个条目的评分了（你也可以自己编写爬虫进行页面分析）。现在你可以编写一个程序来为自己推荐好友或者电影吗？

提示1.可以查看豆瓣API的文档。上面列举了比较详细的使用方法

提示2.用Python获得某用户的好友列表：

have a nice try

AUTHOR:Rocky @ thinkbot.info

集体智能–从群体行为认知世界  

1.什么是集体智能

         所谓集体智能(collective intelligence,又叫群体智慧，集体智慧)，是指若干独立个体的集合其整体行为表达出的智慧。尽管这个词开始流行是在最近十年互联网兴起的时候，然而远在Internet出现前，人们就开始通过调查问卷，各种普查等手段来了解群体意识，并对数据进行统计，分析和预测。而这些分析往往都是无法通过对单一个体的了解获取的，这是集体智能的本质。这和我们现在在Internet上做的很多事情是一样的，通过对大量用户行为的分析，可以为用户推荐最佳的出行路线，为特定爱好的用户提供最佳的搜索结果，为某种阅读偏好的用户推荐他们可能感兴趣的书籍等等。

         internet的出现使得集体智能比以往更好提取，一个好的网站所拥有的用户群体，可能比以往任何时候的一个城市的居民都要多，甚至比大多数国家的人口还要多。如今因特网已经进入到每一个家庭，甚至许多常用的设备比如手机，游戏机，数码相框等等。而且随着IPV6的普及，物联网时代的到来，越来越多的设备接入到internet，internet和人的关系必然会更加紧密。人们在网上的购物，找乐子，搞科研等行为，会留下许多各不相同的痕迹，如果你不介意把这些痕迹留在互联网上，你就可以享受到更好的服务，因为这些痕迹会帮助服务提供商们更好的理解你的行为，进而提供最符合你这类用户需求的服务给你。这样的服务可能是一次最佳的出行路线，也可能是一本你会喜欢的书，或者是一个符合你口味的梦中情人。下图是集体智能的几种类型和应用（点击看大图）：
2.维基百科和Google

          以下两个经典例子说明了internet上集体智能的两种截然不同的表现形式：
1).维基百科（wikipedia.org）
         维基百科就是一本web版的大百科全书，它的词条完全由成千上万的网友编辑而成。任何一个用户都可以创建或编辑任意的词条。当然，会有少数管理员对词条进行审核，尽量保证词条之间是不重复的，保证用户编辑词条时不存在恶意的篡改或者攻击。虽然少数情况下确实会有恶意的篡改，但是大多数情况下的大多数词条仍然保持了较高的准确率，所以人们通常还是很愿意相信维基百科。因为几乎每个词条背后都有一群用户来维护它，这些用户里面的绝大部分被认为是理智的，非恶意的用户，所以尽管偶尔会发生恶意的修改，但是在管理员和这绝大部分理智用户的共同作用下，系统会很快回到一个稳态。维基百科的准确率正是靠这种人工的集体智能来维护的。
2).Google（google.com）
        google大家再熟悉不过了，全球最大的搜索引擎提供商，硅谷科技创业的成功典范。两个斯坦福的大学生，发明了一种基于链接分析的网页排名（PageRank）机制，通过分析网站被链接的次数，和链接者的排名来确定被链接的网站的排名。对一个网站的拥有者来说，只有对他来说有价值的网站才会出现在自己的网站链接里面，所以google的网页排名机制也是基于对大量用户行为理解的基础上的。只不过google对集体智能的学习是潜在的，由机器（计算机程序）完成的，这和wiki的人工编辑是不同的。wiki需要用户去wiki网站编辑，google是自己通过“爬虫”（web crawler）主动的抓取internet上的内容，并进行分析。除了大体上给出一个网页排名，google还可以根据个人的搜索历史来更加精确的提供搜索结果。

         维基百科把互联网出现以前的集体智能成功的运用到互联网上，它没有google那样的精密的算法，没有任何花哨的技术，但是在internet的时代，它的出现无疑对人类的知识库的普及起到了巨大的推动作用。而作为与人工智能技术密切相关的搜索引擎，将会在更多更广的领域发挥作用，关系到我们生活的方方面面。

3.集体智能与机器学习

        集体智能的挖掘需要（但不限于）用到各种机器学习算法，机器学习是人工智能的一个分支，前面提到的Google就使用了大量的机器学习的算法，顾名思义，就是那些使得计算机可以学习知识的算法。也就是让计算机通过某些算法对现有的数据进行学习（训练），发掘这些数据的某些属性，因为任何非完全随机的数据总有特定的模式和偏好可循。经过学习，计算机可以对新的数据作出预测和推断。举个例子，比如说我每天都会受到一些垃圾邮件，对我来说，那些邮件标题含有“贵公司”+“发票”什么的，几乎可以完全确定是垃圾邮件。同样的事情，也可以通过计算机实现，通过对用户使用过程中标记的垃圾邮件的统计学习。可以发现一些关键词比如“贵公司”“发票”同时出现的频率非常高。在标题同时含有这两个词的邮件中，几乎99.99%的邮件被标记为垃圾邮件，于是我们决定把标题满足上述条件的邮件均视为垃圾邮件，并直接丢入垃圾邮件箱。当然真正运用的垃圾邮件过滤算法要比这个复杂的多。尽管如此，还是难免会有误判，很多情况下误判的发生是由人工智能的一些本质上的羁绊造成的，比如说无法对人的自然语言做出准确的理解，无法在现有条件下产生人一样敏锐的意识。我们对单个个体的意识和感情的物理规律理解尚少，更无法准确的描述一个群体了。好在大多数情况下，这不完美的精确度已经足以改善人们的生活了;-)

参考资料
[1] http://en.wikipedia.org/wiki/Collective_intelligence
[2] http://infolab.stanford.edu/pub/papers/google.pdf