Thinking in A.I.

      我们大多数人，都有着对我们的世界进行更深刻了解的渴望。因为，如果知道了一些事物的规律，我们就有可能在此基础上，凭借自己的双手使我们的生活变得更加舒适美好。当然，我们并没有必要苛求自己变成科学达人，能够洞悉诸如量子物理这等高深的学问。因为，就算精通了流体力学，我们也可能依然不会游泳。大多数情况下，我们更加希望知道如何在生活上进行一些小小的改变，能够大大提高我们的幸福感。比如如何配比糖、盐和醋的比例，能让鱼香肉丝尝起来更美味，或者在哪几个零件上滴几滴润滑油能使我们心爱的自行车骑起来更省力。至于糖、醋、盐如何在油锅里相互作用，我们就没必要弄个清楚了。        对于如何提升我们的幸福感，我有一个好消息。那就是我们可以通过一些力所能及的实验来得到想要的答案。我们并不需要一个无菌实验室，也不大需要一打精密昂贵的实验设备（大概制备这些设施所带来的心痛，会残忍得吞噬掉我们的实验所带来的幸福感）。我们只需要确定一个研究对象，知道如何评价以及必要的设备。哦，大概还需要一台电脑，能够帮助我们处理一下数据。       如何进行我们的实验呢？这里我们以泡茶为例，来对实验过程进行一个简单的描述。       研究问题：如何泡茶才能够使其味道更加清香甜美。       实验目的：通过实验，找到改变泡茶的质量的方法，从而使我们充分享受绿茶所带来的美好感受。       实验前提：我们只对一种茶叶进行试验，比如同一袋铁观音。       实验步骤：       1. 列出所有可能影响茶水质量的因素。       在这里，我们需要使用头脑风暴，找出所有可能的因素。对于这个泡茶的课题，我能想到的因素有以下几种：水的来源（自来水，纯净水）；水的温度；水的多少；茶叶的多少；容器类别（玻璃杯，搪瓷杯，紫砂）。当然，对于这个问题，不同人会有不同的见解。我们也可以很无厘头地认为让茶水接受日光的照射，能够对其品质产生巨大的影响。不过根据常识，日光这个因素除了使实验变得复杂之外，大概不会带来其他意外的惊喜。所以，在这个步骤中，我们一定要充分运用我们的常识或者专业知识，指导我们筛选所需考虑的因素，力求做到稳、准、狠。这将对实验的效率产生重要的影响。       2. 进行因析设计，找出关键因素。       在这一步骤中，我们需要回答两个问题。（1）步骤1中所列出的因素，对茶水的质量的影响分别有多大？（2）哪些因素的影响可以区别于实验中的噪声，即哪些因素确实产生了影响？       为了回答以上问题，我们需要两种工具： 因析设计与假设检验。       因析设计 是实验设计方法中，一种十分简便并且行而有效的方法。因析设计的目的，是考察每个因素多个水平对结果影响的差异（如1克铁观音与3克铁观音）。通过因析设计，我们可以计算出所有因素主效应的大小，以及因素间交互作用的大小。对于我们的泡茶实验，可以能够得出五个主效应值的大小，分别为水的来源，水的温度，水的多少，茶叶多少以及容器类别。因素间的交互作用也就是因素之间的共同作用。其中两因素的交互作用共有10种，三因素的交互作用共有10种，四因素的交互作用共有5种，五因素交互作用1种。通过相应的计算，这些交互作用的大小也可以得到。看到这里，我们大概会想，对于五因素的因析设计，我们就有2^5-1种作用需要考虑。如果因素多些，那么其作用的总数就会以指数方式上升了！其实，我们并不需要过分担心这个问题。因为根据前人的经验，三因素或者三因素以上的交互作用很少发生，所以我们只需要注意主效应以及两因素交互作用，这将大大减小我们的工作量。另外，我们可以对因析设计进行改进，使得使用较少的实验，依然能够得出我们想要的结果。如果想知道我们该怎么做，我以后会慢慢道来。       假设检验是我们实验过程中，使用的另外一个强有力的工具。它能够从统计学的角度帮助我们判断一个命题是不是可以否定。通过假设检验，我们将能够把产生影响的因素从噪声中挑选出来，从而缩小考虑的范围，使我们的实验更加有的放矢。       3. 应用响应曲面法，寻找最优因子配比。       通过实验步骤2，我们费了许多力气，终于把真正在背后捣鬼的因素给揪了出来。所以，在步骤3中，我们就需要把这些因子研究个真真切切，明明白白。其实，在这里，我们需要做的事情并不复杂。我们需要在因子以及茶的味道之间建立某种数学关系。什么关系呢？当然，一个数学表达式就不错。有什么好方法呢？没错，最小二乘！如果这些因子的交互作用并不明显，我们可以拟合出一个一阶表达式。比如我们知道只有水温、茶叶量以及水量是主要因素。那么我们就可以得到茶的味道y与因子水温x1、茶叶量x2和水量x3的如下表达式：                                                           其中 第一项为常量， x前的希腊字母为因子系数，最后一项为误差。       但是，很多情况下，交互作用是明显的。比如水多茶少，味道就太淡。相反，茶多水少，味道就会过于苦涩。那么， 与 就存在交互作用。此时，我们需要拟合的表达时就会复杂一些，因为需要考虑所有二阶表达量。于是我们可以得到如下表达式：　　　　 　                                         　　       从拟合的公式可以看出，无论是一阶还是二阶（不考虑误差），在空间中都表示一个光滑的曲面。这就好办了，那么在给定的范围内，这个函数必然存在极值。这就是我们要的结果。下面拿起求导这个武器，不费吹灰之力的，我们就能够找到三个因子各取什么值的时候，我们能得到最佳口感。        4. 结果验证。 　　通过步骤３，我们已经知道了当水温为多少，茶叶放多少，水放多少的情况下，我们的茶最为可口。不过，为了保证效果，我们最好再做一些实验来验证效果。这里会出现两种情况。如果最优值所对应的因子在我们因析设计所考虑的范围内，那么一般情况下，结果不会有过大的偏差。但是，如果在考虑的范围外，那么我们得到的表达式就存在失拟的可能。在这种情况下，如果茶水的口感与我们所预期的相差甚远，那么很不幸，大概我们要从步骤２开始，重新把以上过程走一遍了。别灰心，别灰心，我们之前的工作并没有白费。因为我们可以从之前的结果得到了更多关于最优值可能出现的位置的信息。那么重新做实验后，我们就很有可能得到我们想要的结果了。                                         通过以上的描述，我们就大概知道了如何设计以及分析实验，能够使我们的茶更好喝。这里所提到的因析设计，响应曲面法等等方法，也只是众多方法中的几种而已。至于如何实现这些细节，以后的章节中会有具体的交代。各位看官如果有兴趣，就请继续跟踪下去。        [...]

版权声明：     本文由LeftNotEasy发布于 http://leftnoteasy.cnblogs.com, 本文可以被全部的转载或者部分使用，但请注明出处，如果有问题，请联系 wheeleast@gmail.com 前言：     决策树这种算法有着很多良好的特性，比如说训练时间复杂度较低，预测的过程比较快速，模型容易展示（容易将得到的决策树做成图片展示出来）等。但是同时，单决策树又有一些不好的地方，比如说容易over-fitting，虽然有一些方法，如剪枝可以减少这种情况，但是还是不够的。     模型组合（比如说有Boosting，Bagging等）与决策树相关的算法比较多，这些算法最终的结果是生成N(可能会有几百棵以上）棵树，这样可以大大的减少单决策树带来的毛病，有点类似于三个臭皮匠等于一个诸葛亮的做法，虽然这几百棵决策树中的每一棵都很简单（相对于C4.5这种单决策树来说），但是他们组合起来确是很强大。     在最近几年的paper上，如iccv这种重量级的会议， iccv 09 年的里面有不少的文章都是与Boosting与随机森林相关的。模型组合+决策树相关的算法有两种比较基本的形式 – 随机森林与GBDT((Gradient Boost Decision Tree)，其他的比较新的模型组合+决策树的算法都是来自这两种算法的延伸。本文主要侧重于GBDT，对于随机森林只是大概提提，因为它相对比较简单。     在看本文之前，建议先看看 机器学习与数学(3)与其中引用的论文，本文中的GBDT主要基于此，而随机森林相对比较独立。 基础内容：     这里只是准备简单谈谈基础的内容，主要参考一下别人的文章，对于随机森林与GBDT，有两个地方比较重要，首先是information gain，其次是决策树。这里特别推荐Andrew Moore大牛的 Decision Trees Tutorial ，与Information Gain Tutorial 。Moore的Data Mining Tutorial系列 非常赞，看懂了上面说的两个内容之后的文章才能继续读下去。     决策树实际上是将空间用超平面进行划分的一种方法，每次分割的时候，都将 当前的空间一分为二，比如说下面的决策树：     就是将空间划分成下面的样子：     这样使得 每一个叶子节点都是在空间中的一个不相交的区域，在进行决策的时候，会根据输入样本每一维feature的值，一步一步往下，最后使得样本落入N个区域中的一个（假设有N个叶子节点） 随机森林(Random Forest):     随机森林是一个最近比较火的算法，它有很多的优点：     在数据集上表现良好     在当前的很多数据集上，相对其他算法有着很大的优势     它能够处理很高维度（feature很多）的数据，并且不用做特征选择     在训练完后，它能够给出哪些feature比较重要     在创建随机森林的时候，对generlization error使用的是无偏估计     训练速度快     在训练过程中，能够检测到feature间的互相影响     容易做成并行化方法     实现比较简单     随机森林顾名思义，是用随机的方式建立一个森林，森林里面有很多的决策树组成，随机森林的每一棵决策树之间是没有关联的。在得到森林之后，当有一个新的输入样本进入的时候，就让森林中的每一棵决策树分别进行一下判断，看看这个样本应该属于哪一类（对于分类算法），然后看看哪一类被选择最多，就预测这个样本为那一类。     在建立每一棵决策树的过程中，有两点需要注意 – 采样与完全分裂。首先是两个随机采样的过程，random forest对输入的数据要进行行、列的采样。对于行采样，采用有放回的方式，也就是在采样得到的样本集合中，可能有重复的样本。假设输入样本为N个，那么采样的样本也为N个。这样使得在训练的时候，每一棵树的输入样本都不是全部的样本，使得相对不容易出现over-fitting。然后进行列采样，从M个feature中，选择m个(m << M)。之后就是对采样之后的数据使用完全分裂的方式建立出决策树，这样决策树的某一个叶子节点要么是无法继续分裂的，要么里面的所有样本的都是指向的同一个分类。一般很多的决策树算法都一个重要的步骤 – 剪枝，但是这里不这样干，由于之前的两个随机采样的过程保证了随机性，所以就算不剪枝，也不会出现over-fitting。     按这种算法得到的随机森林中的每一棵都是很弱的，但是大家组合起来就很厉害了。我觉得可以这样比喻随机森林算法：每一棵决策树就是一个精通于某一个窄领域的专家（因为我们从M个feature中选择m让每一棵决策树进行学习），这样在随机森林中就有了很多个精通不同领域的专家，对一个新的问题（新的输入数据），可以用不同的角度去看待它，最终由各个专家，投票得到结果。     随机森林的过程请参考 Mahout的random forest 。这个页面上写的比较清楚了，其中可能不明白的就是Information Gain，可以看看之前推荐过的Moore的页面。 Gradient Boost [...]

版权声明： 本文由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维的空间，在空间中就会进行一些类似于旋转、拉伸的变化。 [...]

版权声明： 本文由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，得到： [...]

版权声明：     本文由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，我们也可以得到下面的式子：    [...]

版权声明： 本文发布于 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表示模型的复杂程度，这个值越小，表示模型的复杂程度越高，在第一行，大家的复杂度都很低（每个人都很穷）的时候，方差是很小的，但是偏差同样很小（国家也很穷），但是到了最后一幅图，我们可以得到，每个人的复杂程度都很高的情况下，不同的函数就有着天壤之别了（贫富差异大），但是偏差就很小了（国家很富有）。 预告： [...]

前言: 上次写过一篇关于贝叶斯概率论的数学，最近时间比较紧，coding的任务比较重，不过还是抽空看了一些机器学习的书和视频，其中很推荐两个：一个是stanford的machine learning公开课，在verycd可下载，可惜没有翻译。不过还是可以看。另外一个是prml-pattern recognition and machine learning, Bishop的一部反响不错的书，而且是2008年的，算是比较新的一本书了。 前几天还准备写一个分布式计算的系列，只写了个开头，又换到写这个系列了。以后看哪边的心得更多，就写哪一个系列吧。最近干的事情比较杂，有跟机器学习相关的，有跟数学相关的，也有跟分布式相关的。 这个系列主要想能够用数学去描述机器学习，想要学好机器学习，首先得去理解其中的数学意义，不一定要到能够轻松自如的推导中间的公式，不过至少得认识这些式子吧，不然看一些相关的论文可就看不懂了，这个系列主要将会着重于去机器学习的数学描述这个部分，将会覆盖但不一定局限于回归、聚类、分类等算法。 回归与梯度下降： 回归在数学上来说是给定一个点集，能够用一条曲线去拟合之，如果这个曲线是一条直线，那就被称为线性回归，如果曲线是一条二次曲线，就被称为二次回归，回归还有很多的变种，如locally weighted回归，logistic回归，等等，这个将在后面去讲。 用一个很简单的例子来说明回归，这个例子来自很多的地方，也在很多的open source的软件中看到，比如说weka。大概就是，做一个房屋价值的评估系统，一个房屋的价值来自很多地方，比如说面积、房间的数量（几室几厅）、地段、朝向等等，这些影响房屋价值的变量被称为特征(feature)，feature在机器学习中是一个很重要的概念，有很多的论文专门探讨这个东西。在此处，为了简单，假设我们的房屋就是一个变量影响的，就是房屋的面积。 假设有一个房屋销售的数据如下： 面积(m^2)  销售价钱（万元） 123            250 150            320 87              160 102            220 …               … 这个表类似于帝都5环左右的房屋价钱，我们可以做出一个图，x轴是房屋的面积。y轴是房屋的售价，如下： 如果来了一个新的面积，假设在销售价钱的记录中没有的，我们怎么办呢？ 我们可以用一条曲线去尽量准的拟合这些数据，然后如果有新的输入过来，我们可以在将曲线上这个点对应的值返回。如果用一条直线去拟合，可能是下面的样子： 绿色的点就是我们想要预测的点。 首先给出一些概念和常用的符号，在不同的机器学习书籍中可能有一定的差别。 房屋销售记录表 – 训练集(training set)或者训练数据(training data), 是我们流程中的输入数据，一般称为x 房屋销售价钱 – 输出数据，一般称为y 拟合的函数（或者称为假设或者模型），一般写做 y = h(x) 训练数据的条目数(#training set), 一条训练数据是由一对输入数据和输出数据组成的 输入数据的维度(特征的个数，#features)，n 下面是一个典型的机器学习的过程，首先给出一个输入数据，我们的算法会通过一系列的过程得到一个估计的函数，这个函数有能力对没有见过的新数据给出一个新的估计，也被称为构建一个模型。就如同上面的线性回归函数。 我们用X1，X2..Xn 去描述feature里面的分量，比如x1=房间的面积，x2=房间的朝向，等等，我们可以做出一个估计函数： θ在这儿称为参数，在这儿的意思是调整feature中每个分量的影响力，就是到底是房屋的面积更重要还是房屋的地段更重要。为了如果我们令X0 = 1，就可以用向量的方式来表示了： 我们程序也需要一个机制去评估我们θ是否比较好，所以说需要对我们做出的h函数进行评估，一般这个函数称为损失函数（loss [...]

前言： 云计算以及很多误解 云计算这个概念被炒作得非常的火热，只要跟互联网沾边的公司，都喜欢用上云计算这个词。云计算其实不是一个那样广义的概念，云计算的定义并不是若干台机器用某种方式管理起来，然后用于存储或者计算这么简单，包括很多的云杀毒、云安全、云存储等等，都 不一定是真正的云计算。 上 wikipedia可以看看相对来说比较完备的云计算定义，云计算一个很重要的特性是跟虚拟化相关的，像水、电一样为用户提供计算的资源。另外在key features这个章节上说明了很多云计算的特性，如果某一个系统只具备了里面的一个或者很少的几个特性，那称其为云计算就有点那么勉强了。 云计算一些很重要的特性包括 1）可扩展性，用户能够方便的增加、减少计算和存储的能力，而且有着足够的扩展性。按这个定义、一堆GPU或者CPU组成的网格可能就很难称为云计算了，这种超级计算机有着非常好的计算能力，但是对存储的支持相对较差，据内部人士透露，天河的存储能力就相当的差，做做计算还不错，但是数据大了就只有傻眼了） 2）成本相对低廉，云计算对终端用户而言，消费相对较低，对于公司而言，也能减少管理成本。按这个定义，某些很“高级”的服务器组成的集群就很难称为云计算了，之前听说广东公安局的身份证处理电脑的硬盘是单机320T的磁盘阵列，硬盘这种东西就是，买起来很便宜，但是硬盘架非常的贵，想在单机组成一个大的磁盘阵列，那可能就非常的高了。而且云计算的集群管理成本也不高。以一个极端的例子来说，一般一个大一点（100-200台电脑）的网吧都要配2-3个网管。但是我所在的公司几万台服务器，管理服务器的人就在20个人左右，相对管理成本很低。 3）稳定性，至少在程序运行的时候，错误处理能够做好，比如说N个节点计算，某个节点死机了，那程序是不是一定得重新运行？或者集群中某台电脑的硬盘坏掉了，那这些数据会不会就丢失了？按这个定义，普通的多点存储（简单的将数据备份到2块或者多块硬盘中去），以及那些某个节点出错了，计算任务就需要完全重跑的计算方式可能就不算云计算了（比如说MPI，这儿本章后面将会更详细一点提到） 由此看出，云计算是一个很庞大的系统，并非一般的开源项目（大的开源项目还是可以的，比如说Hadoop）可以完成的。就算能完成，也会有这样那样的问题，比如Hadoop集群就没有实现Service的常驻运行（只能跑job，也就是跑完就结束的那种） 分布式的数据挖掘 另一方面，数据挖掘也是一个很有意思、被很多人看重，也在很多领域上发挥大作用的一门学科，从个人而言，我对数据挖掘的兴趣非常的大。传统的计算机想要用数据挖掘，玩玩简单的算法可以，但是在工业界看来，总体来说是一个玩具。比如说weka，学习算法用它还行，但是想要对大规模的数据进行处理，是不太可能的。为了进行大规模的数据处理，分布式计算就很必要了。 分布式计算分类： 一般来说，现在比较常见的并行计算有下面的方式：OpenMP, CUDA，MPI，MapReduce。 OpenMP： 是对于多核的条件下，也就是一些超级计算机可以使用的方式，一个很重要的特性是共享存储，多个instance的关系是线程与线程的关系，也就限制了OpenMP主要是在单机（可能是超级计算机）中进行科学计算的任务。 CUDA: 这个概念是最近几年的事情，似乎ATI最近也搞了一个通用计算的内容，主要是用GPU并联起来进行计算，由于GPU的架构和CPU不太一样，采用这种方式可以对某些计算为主的任务加速几个数量级。对这一块我不太了解，也不太清楚现在CUDA计算、存储能力，还有稳定性等等做到什么样的程度了。这里就不加以评论 Map-Reduce： 发扬光大从Google的论文-MapReduce: Simplified data processing on large clusters开始的。Map-Reduce将程序的运行分成了Map和Reduce两个步骤，Map是一个读取、处理原始数据的过程，而Reduce是根据Map处理的内容，进行整合、再处理。Reduce可以认为又是一个Map，为下一级的Reduce过程作准备，这样数据的处理可以按这种方式进行迭代。 Map-Reduce的重点在下面的几处： 1）运行程序的方式，Map-Reduce一般是在以GFS（Google文件系统），或者HDFS等类似的系统上面进行的，这个系统一般有诸多的如磁盘负载平衡，数据冗余（replica），数据迁移（比如说集群中的某台硬盘坏了，这个硬盘里面的数据会用某种方式备份到其他的硬盘中去，而且保证每块硬盘的数据量都大致平衡）。不过这里先不谈数据的存储，主要谈谈任务的调度。 一般像这样的集群里面都有一百台以上的电脑，按每个电脑8个核计算，至少会有几百上千个CPU的资源。在运行每一个Map-Reduce的时候，用户会先填写需要多少的资源（CPU与内存），然后集群的负责人（可能被称为JobMaster），会去查看当前集群中的计算资源情况，看看能否成功的运行这个作业。如果不行的话，会排队。举一个Map-Reduce的例子： 对于一个很大的文件（由一堆的浮点数组成的），计算这个文件中Top1000的数是什么。那么程序的运行可能是下面的过程。 a. 先在N个CPU（可能在不同的电脑中的）上运行程序，每个CPU会负责数据的一部分，计算出Top1000的数值，将结果写入一个文件（共N份数据） b. 在M = N/16个CPU上运行程序，每个CPU会负责上面步骤的16个结果文件，计算出这些文件中Top1000的数值，然后将结果写入一个文件（共N / 16份数据） c. 在O = M/16个CPU上运行程序，同样每个CPU负责上面的16个结果文件。（共N / 256份数据） .. 按照这种方式迭代，直到求出真正的Top1000数值。 所以说，Map-Reduce的数据按每次迭代，是一个减少的过程，如果数据处理的时候有这样的特性，那就非常适合于用Map-Reduce去解决。 2）多个进程间的数据传递，对Map-Reduce而言，没有办法进行传统方式的进程间通信（比如说socket通信），进程间的通信纯粹是用文件去联系的，对于一个Map-Reduce任务，是多级组成的，每一级会起若干的进程，每个进程做的事情就是去读取上一级进程生成的数据，然后处理后写入磁盘让下一级进程进行读取。 这个特性使得Map-Reduce有着良好的容错性，当某一级的某一个进程出错了（比如说机器死机了，程序出异常了等等），JobMaster会重新调度这个进程到另外一个机器上，重新运行，如果是由于外部的问题（比如说机器死机了），一般这样的错误不会使得整个任务重复运行。不过真正如果是写程序出的逻辑问题，那程序也不能正常运行的，JobMaster会试着将失败的进程调度几次，如果都失败了，则任务就失败了。 但是用文件来同步机器间的通讯这个特性也有一个坏处，就是每当Map-Reduce的某一个步骤运行完后，需要重新调度下一级任务。如果是程序是一个重复迭代，直至收敛的过程，比如说KMeans算法、矩阵奇异值分解（SVD），则由于调度产生的开销会非常的大，网络传输不仅仅是发送需要的数据，还有一个读取文件、写入文件的磁盘IO过程，在迭代次数很多的时候（在大规模的SVD分解的时候，迭代的次数可能会达到上万次），这样的方式可能是无法忍受的。 目前Map-Reduce已经被很多的公司实现，Map-Reduce并不是一套标准，而是一种编程的方式，所以每个公司提供的API都有很大的区别，这会使得不能让程序比较通用。一般来说，如果想学Map-Reduce，可以在单机配置一个Hadoop。这算是一个非常标准的Map-Reduce过程。 MPI: 全称是Message Passing Interface，也就是定义了一系列的消息传递接口，可以看看 MPI的Wikipedia，里面的内容从了解MPI来说比较好，这里说说重点，就不粘程序了。 MPI其实是一套标准，对C，C++，Fortran，Java，Python等都规定了一系列的接口，MPI的内部有一系列的函数，比如获取当前有多少进程MPI_Comm_size, 进程间同步MPI_Barrier等函数。对每种支持的语言，MPI都定了一个函数接口，也保证了不同的实现下，MPI的程序写出来都是一样的。MPI是一个在学术界和工业界都应用非常广泛的一套接口，目前MPI的实现非常多，开源的有OpenMPI和MPICH比较好，有些MPI实现来自一些大学的实验室，有些MPI的实现来自一流的公司（比如Microsoft就有自己的一套实现，还弄了一个C#版本的）。 MPI相对MapReduce来说，开发、调试也更接近单机，MPI的部署可以在单机上完成，调用的时候也可以制定多线程运行程序，如果有兴趣，可以下载一个OpenMPI或者MPICH，在自己的linux机器上进行部署，写写简单的代码是足够了。在单机保证逻辑正确的情况下，再上集群上面跑，就容易多了。 MPI的优点是，程序的调度是一次性的，就是比如开始申请了50个进程，那这50个进程就会一起跑，同生同死，在程序中指定的同步等操作，也会让这些进程进行同步，也可以在互相之间发送数据，通过MPI的封装，让发数据更操作变得非常的方便（MPI有100多个函数）。也就是从程序开始到结束，每个进程只会调度一次，如果有迭代的操作，就用下面的语句，加上必要的同步就行了：while (condition) { [...]

本文由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) = [...]