算法学习 10.概率分治机器学习.pdf

《算法学习 10.概率分治机器学习.pdf》由会员分享，可在线阅读，更多相关《算法学习 10.概率分治机器学习.pdf（79页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、概率、分治、机器学习七月算法邹博2015年5月7日4月算法在线班2/动态规划总结相对于前面使用存储结构来划分章节：“数组”、“字符串”、“树”、“图”(它们是世界观)，动态规划是方法论，是解决一大类问题的通用思路。事实上，前面章节论述的很多内容都可以归结为动态规划的思想。如：KMP中求next数组的过程：已知next0i-1，求nexti；何时可以考虑使用动态规划：初始规模下能够方便的得出结论空串、长度为0的数组、自身等能够得到问题规模增大导致的变化递推式状态转移方程事实上，动态规划还有“无后效性”的要求一旦计算得到了A0i-1，那么，计算Ai时只可能读取A0i-1，而不会更改它们的值过去发生

2、的，只能承认，不能改变；一旦计算得到了A0i-1，那么，计算Ai时只需要读取A0i-1的值即可，不需要事先知道Ai+1n-1的值未来的事情，完全未知。在实践中往往忽略无后效性这一要求：要么问题本身决定了它是成立的：格子取数问题；要么通过更改计算次序，可以达到该要求：矩阵连乘I问题。4月算法在线班3/卡塔兰数 Catalan n个矩阵连乘，可以分解成i个矩阵连乘和(n-i)个矩阵连乘，最后，再将这两个矩阵相乘。故：1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845,35357670,129644790

3、,477638700,1767263190,6564120420,24466267020,91482563640,343059613650,1289904147324,4861946401452 CnnnnP1221)()(11)()(1)(2/3114nnnknPnnknPkPnP4月算法在线班4/卡塔兰数 Catalan 有N个节点的二叉树共有多少种情形？一个栈(无穷大)的进栈序列为1,2,3,.n,有多少个不同的出栈序列？凸多边形三角化：将一个凸多边形划分成三角形区域的方法有多少种？由左而右扫描由n个1和n个0组成的2n位二进制数，要求在任何时刻，1的累计数不小于0的累计数。求满足这样条

4、件的二进制数的个数。CnnnnH2114月算法在线班5/计算机中的概率计算 伪随机数 选择方便获取的“随机”事件 读取当前系统时间？读取某经常变化的系统文件长度？数学公式 Hash杂凑？可以获得几乎和均匀分布性质相当的实践结果。4月算法在线班6/Code4月算法在线班7/辅助结构4月算法在线班8/产生二维随机数 给定区间ax,bxay,by，使得二维随机点(x,y)落在等概率落在区间的某个点上。分析：因为两个维度是独立的，分别生成两个随机数即可。4月算法在线班9/代码与效果4月算法在线班10/圆内均匀取点 给定定点O(x0,y0)和半径r，使得二维随机点(x,y)等概率落在圆内。分析 因为均匀

5、分布的数据是具有平移不变性，生成半径为r，定点为圆心的随机数(x1,y1)，然后平移得到(x1+x0,y1+y0)即可。直接使用x=r*cos，y=r*sin是否可以呢？具体试验一下。4月算法在线班11/代码与效果4月算法在线班12/代码与效果 显然上述做法是不对的。但可以使用二维随机点的做法，若落在圆外，则重新生成点。结果如下。4月算法在线班13/代码与效果4月算法在线班14/思考 不是每次生成随机数都能退出该算法 有一定的接受率。请问：以多大的概率1次退出：接受率是多少？得到随机数的需要的平均次数(期望)是多少？这个做法简洁、有效，值得推荐；许多相关问题，往往可以如此解决。4月算法在线班1

6、5/例题 已知有个rand7()的函数，返回1到7随机自然数，让利用这个rand7()构造rand10()随机110。4月算法在线班16/分析 因为rand7仅能返回17的数字，少于rand10的数目。因此，多调用一次，从而得到49种组合。超过10的整数倍部分，直接丢弃。4月算法在线班17/Code4月算法在线班18/圆内均匀取点的1次成功算法 问题分析：把随机点看做面积很小的区域，圆内均匀取点意味着随机点P的面积与圆的面积成正比。Sp=kS S=r2，与半径的平方成正比 从而，Sp(r)=kr2 将均匀生成的随机数x取平方根赋值给r；则Sp(r)即为均匀分布。同时，是与角度无关的，即：取均匀

7、分布的随机数作为旋转角即可。4月算法在线班19/代码与效果4月算法在线班20/三角形内的均匀点4月算法在线班21/实践效果4月算法在线班22/多边形内均匀取点 使用圆内取点的思想：计算多边形的外包围盒，生成外包围盒(矩形)内的二维点，若点在多边形内，则退出；否则，继续探测。将多边形剖分成三角形集合，然后调用三角形内均匀取点算法。按照面积为权重，选择某个三角形；生成该三角形内的随机点。思考：如何将多边形快速剖分成三角形？Delaunay三角剖分4月算法在线班23/思考题 若某函数rand()以概率p(p0.5)返回数字0，以概率1-p返回数字1，如何利用该函数返回等概率的0和1？4月算法在线班2

8、4/古典概型 将n个不同的球放入N(Nn)个盒子中，假设盒子容量无限，求事件A=每个盒子至多有1个球的概率。4月算法在线班25/解 基本事件总数：第1个球，有N种放法；第2个球，有N种放法；共：Nn种放法。每个盒子至多放1个球的事件数：第1个球，有N种放法；第2个球，有N-1种放法；第3个球，有N-2种放法；共：nNP1n-N2-N1-NN nnNNPAP4月算法在线班26/实际问题 某班上有50位同学，至少有2人生日相同的概率是多少？0.970.940.890.810.710.570.410.250.12P504540353025201510n4月算法在线班27/装箱问题 将12件正品和3件

9、次品随机装在3个箱子中。每箱中恰有1件次品的概率是多少？4月算法在线班28/解 将15件产品装入3个箱子，每箱装5件，共有15!/(5!5!5!)种装法；先把3件次品放入3个箱子，有3!种装法。对于这样的每一种装法，把其余12件产品装入3个箱子，每箱装4件，共有12!/(4!4!4!)种装法；P(A)=(3!*12!/(4!4!4!)/(15!/(5!5!5!)=25/914月算法在线班29/与组合数的关系 把n个物品分成k组，使得每组物品的个数分别为n1,n2nk，(n=n1+n2+nk)，则不同的分组方法有种。上述问题的简化版本，即n个物品分成2组，第一组m个，第二组n-m个，则分组方法有

10、，即：。!321knnnnn!mnmnmnC4月算法在线班30/走棋盘 给定m*n的矩阵，从左上角开始行走，每次只能朝右和下走，走到右下角，求一共有多少种走法？4月算法在线班31/分析 数学公式：一共要走m+n2步，其中(m1)步向右，(n-1)步向下。即：在m+n2个步数中，选择m1个作为“右行”，即：题目的解为：令dp(x,y)为当前位于(x,y)时有多少种可行路径，则：dp(x,y)=dp(x-1,y)+dp(x,y-1)1212nnmmnmCCN4月算法在线班32/通过动态规划递推式，可以得到什么？mnmnmnxmtnxtxtxtyxtCCCCCCxtdpxtdpxtdpxyxdpxy

11、xdpxyxdpyxyxdpyxyxdpyxyxdpyxdpyxdpyxdp111,111,11,1,11,1,1,1,1,1,1,1,令换个表达方式令删除最后一维”增加“两个坐标值加和4月算法在线班33/分治法 给定实数x和整数n，求xn。分析：令pow(x,n)=xn，如果能够求出y=pow(x,n/2)，只需要返回y*y即可，节省一半的时间。因此，可以递归下去。时间复杂度O(NlogN)需要考虑的：如果n是奇数呢？如果n是负数呢？4月算法在线班34/Code4月算法在线班35/矩阵的乘法 A为ms阶的矩阵，B为sn阶的矩阵，那么，C=AB是mn阶的矩阵，其中，根据定义来计算 C=AB，需

12、要m*n*s次乘法。即：若A、B都是n阶方阵，C的计算时间复杂度为O(n3)问：可否设计更快的算法？skkjikijbac14月算法在线班36/分治 矩阵分块 按照定义：计算n/2阶矩阵的乘积：O(n3/8)这里需要计算8个：总时间复杂度：O(n3)没有任何效果。222112112221121122211211CCCCBBBBAAAA2222122122212211212122121211122112111111BABACBABACBABACBABAC4月算法在线班37/Strassen矩阵乘法：由8到7 目标2222122122212211212122121211122112111111BA

13、BACBABACBABACBABAC222122121211112122121111212222121111222122112211BBAAVBBAAUBAATBBASBBARBAAQBBAAPUQSPCSQCTRCVTSPC222112114月算法在线班38/说明 时间复杂度降为O(nlog7)=O(n2.81)理论意义：由定义出发直接得出的算法未必是最好的。Hopcroft与Kerr已经证明，两个22矩阵相乘必须要用7次乘法，如果需要进一步改进，应考虑33、44或者更高阶数的分块子矩阵或者采用其他设计策略。当n很大时，实际效果比直接定义求解的O(n3)好。根据矩阵乘法的定义可知，Cij只与

14、A的第i行、B的第j列相关，在实践中若遇到大矩阵，应考虑并行计算。skkjikijbac14月算法在线班39/思考 将矩阵分治乘法的思想，用于两个大整数的乘法呢？根据定义，两个大整数A、B相乘，应该遍历B从低到高的数字，依次与大整数A相乘，最后将这些值相加。时间复杂度O(n2)。可否将A、B写成两个规模小一半的整数A1,A2,B1,B2，然后计算它们的积呢？4月算法在线班40/大整数乘法 取大整数x和y的长度较大者的一般，记为k，则有：计算长度为n/2的两个数的积，需要乘法次数为O(n2/4)，而上面的式子需要4次乘法，总时间复杂度为O(n2)，没有效果。因此，需要考虑改进。001001211

15、01010101yxMyxyxMyxyMyxMxxyyMyyxMxxkkkkkk4月算法在线班41/大整数乘法：Karatsuba算法 事实上：上式只需要3次乘法(配合若干次加法和移位)即可完成，时间复杂度为O(nlog3)=O(n1.585)。000011010121100100121101010101yxMyxyxyyxxMyxyxMyxyxMyxxyyMyxMxxyyMyyxMxxkkkkkkkk4月算法在线班42/机器学习若干概念 交叉验证 泛化能力 监督学习 无监督学习 强化学习4月算法在线班43/机器学习算法的分类 监督K近邻回归SVM决策树朴素贝叶斯BP神经网络 非监督聚类Apr

16、ioriFP-growth4月算法在线班44/交叉验证 交叉验证(Cross-validation)也称为交叉比对，主要用于建模应用中。在给定的建模样本中，拿出大部分样本进行建模型，留小部分样本用刚建立的模型进行预报，并求这小部分样本的预报误差，记录它们的平方加和。这个过程一直进行，直到所有的样本都被预报了一次而且仅被预报一次。把每个样本的预报误差平方加和，称为PRESS(predicted Error Sum of Squares)。交叉验证是常用的精度测试方法，其目的是为了得到可靠稳定的模型。例如10折交叉验证(10-fold cross validation)，将数据集分成十份，轮流将其

17、中9份做训练1份做测试，10次的结果的均值作为对算法精度的估计，一般还需要进行多次10折交叉验证求均值，例如：10次10折交叉验证，以求更精确一点。4月算法在线班45/交叉验证的形式Holdout 验证通常来说，Holdout 验证并非一种交叉验证，因为数据并没有交叉使用。随机从最初的样本中选出部分，形成交叉验证数据，而剩余的就当做训练数据。一般来说，少于原本样本三分之一的数据被选做验证数据。K-fold cross-validationK折交叉验证，初始采样分割成K个子样本，一个单独的子样本被保留作为验证模型的数据，其他K-1个样本用来训练。交叉验证重复K次，每个子样本验证一次，平均K次的结

18、果或者使用其它结合方式，最终得到一个单一估测。这个方法的优势在于，同时重复运用随机产生的子样本进行训练和验证，每次的结果验证一次，10折交叉验证是最常用的。留一验证意指只使用原本样本中的一项来当做验证资料，而剩余的则留下来当做训练资料。这个步骤一直持续到每个样本都被当做一次验证资料。事实上，这等同于 K-fold 交叉验证是一样的，其中K为原本样本个数。4月算法在线班46/泛化能力 概括地说，所谓泛化能力（generalization ability）是指机器学习算法对新鲜样本的适应能力。学习的目的是学到隐含在数据对背后的规律，对具有同一规律的学习集以外的数据，经过训练的算法也能给出合适的输出

19、，该能力称为泛化能力。通常期望经训练样本训练的算法具有较强的泛化能力，也就是对新输入给出合理响应的能力。应当指出并非训练的次数越多越能得到正确的输入输出映射关系。算法的性能主要用它的泛化能力来衡量。4月算法在线班47/从下面几个问题入手机器学习 k近邻 向量距离 聚类 线性回归 朴素贝叶斯4月算法在线班48/k近邻分类(属于有监督学习)4月算法在线班49/相似度/距离计算方法总结闵可夫斯基距离Minkowski/欧式距离杰卡德相似系数(Jaccard)余弦相似度(cosine similarity)Pearson相似系数相对熵(K-L距离)pnipiiyxYXdist11,BABABAJ,ba

20、baTcosniYiniXiniYiXiYXYXYXXYYXYXYXEYX12121,cov xqxpExqxpxpqpDxpxloglog|4月算法在线班50/k-均值聚类(属于无监督学习)创建k个点作为起始质心(如：随机选择起始质心)当任意一个点的簇分配结果发生改变时 对数据集中的每个数据点 对每个质心 计算质心与数据点之间的距离 将数据点分配到距其最近的簇 对每个簇，计算簇中所有点的均值并作为质心4月算法在线班51/K-means过程4月算法在线班52/对K-Means的思考 K-Means将簇中所有点的均值作为新质心，若簇中含有异常点，将导致均值偏离严重。以一维数据为例：数组1、2、3

21、、4、100的均值为22，显然距离“大多数”数据1、2、3、4比较远改成求数组的中位数3，在该实例中更为稳妥。这种聚类方式即K-Mediods聚类(K中值距离)点的簇分配结果发生改变的标准如何判断？实践中可以选择误差的平方和最小 初值的选择，对聚类结果有影响吗？如何避免？4月算法在线班53/利用SSE进行聚类后处理 SSE:Sum of Squared Error 误差平方和4月算法在线班54/二分k-均值聚类后的结果4月算法在线班55/线性回归 y=ax+b4月算法在线班56/多个变量的情形 考虑两个变量4月算法在线班57/多个变量的情形4月算法在线班58/最小二乘的目标函数 m为样本个数，

22、则一个比较“符合常理”的误差函数为：思考：如何解释和定义“符合常理”？4月算法在线班59/使用极大似然估计解释最小二乘4月算法在线班60/似然函数4月算法在线班61/对数似然4月算法在线班62/计算极大似然函数的最优解4月算法在线班63/“简便”方法记忆结论yXXXyXXXyXTTTT14月算法在线班64/最小二乘意义下的参数最优解 参数的解析式 若XTX不可逆，上式不可使用yXIXXTT1yXXXTT14月算法在线班65/加入扰动后 XTX半正定：对于任意的非零向量u 所以，对于任意的实数0，正定，从而可逆。保证回归公式一定有意义。0vvXuXuXuuXTXuvTT令IXXTyXIXXTT1

23、4月算法在线班66/对线性回归的思考 若目标y与观测向量X不是线性关系，怎么处理？局部线性回归 非参数方法 广义线性回归 对数线性回归 Logistic回归4月算法在线班67/概率 条件概率：全概率公式：贝叶斯(Bayes)公式：BPABPBAP iiiBPBAPAP|jjjiiiBPBAPBPBAPABP)()|()()|(4月算法在线班68/贝叶斯公式的应用 8支步枪中有5支已校准过，3支未校准。一名射手用校准过的枪射击，中靶概率为0.8；用未校准的枪射击，中靶概率为0.3；现从8支枪中随机取一支射击，结果中靶。求该枪是已校准过的概率。解：?117.0003.0012.0108.01183

24、0851AGPGAPGAPGAPGAPGPGP8163.0833.0858.0858.0111111GiiGPiGAPGPGAPAGP4月算法在线班69/贝叶斯准则 条件概率公式 P(x|y)=P(x,y)/P(y)P(x,y)=P(x|y)*P(y)P(y|x)=P(x,y)/P(x)P(x,y)=P(y|x)*P(x)则P(x|y)*P(y)=P(y|x)*P(x)从而：P(x|y)=P(y|x)*P(x)/P(y)分类原则：在给定的条件下，哪种分类发生的概率大，则属于那种分类。4月算法在线班70/朴素贝叶斯的假设 一个特征出现的概率，与其他特征(条件)独立(特征独立性)其实是：对于给定分

25、类的条件下，特征独立 每个特征同等重要(特征均衡性)4月算法在线班71/以文本分类为例 样本：1000封邮件，每个邮件被标记为垃圾邮件或者非垃圾邮件 分类目标：给定第1001封邮件，确定它是垃圾邮件还是非垃圾邮件 方法：朴素贝叶斯4月算法在线班72/分析 类别c：垃圾邮件c1，非垃圾邮件c2 词汇表，两种建立方法：使用现成的单词词典；将所有邮件中出现的单词都统计出来，得到词典。记单词数目为N 将每个邮件m映射成维度为N的向量x若单词wi在邮件m中出现过，则xi=1，否则，xi=0。即邮件的向量化：m(x1,x2xN)贝叶斯公式：P(c|x)=P(x|c)*P(c)/P(x)P(c1|x)=P(

26、x|c1)*P(c1)/P(x)P(c2|x)=P(x|c2)*P(c2)/P(x)注意这里x是向量4月算法在线班73/分解P(c|x)=P(x|c)*P(c)/P(x)P(x|c)=P(x1,x2xN|c)=P(x1|c)*P(x2|c)P(xN|c)特征条件独立假设P(x)=P(x1,x2xN)=P(x1)*P(x2)P(xN)特征独立假设带入公式：P(c|x)=P(x|c)*P(c)/P(x)等式右侧各项的含义：P(xi|cj)：在cj(此题目，cj要么为垃圾邮件1，要么为非垃圾邮件2)的前提下，第i个单词xi出现的概率P(xi)：在所有样本中，单词xi出现的概率P(cj)：在所有样本中

27、，邮件类别cj出现的概率4月算法在线班74/拉普拉斯平滑p(x1|c1)是指的:在垃圾邮件c1这个类别中，单词x1出现的概率。x1是待考察的邮件中的某个单词定义符号n1：在所有垃圾邮件中单词x1出现的次数。如果x1没有出现过，则n1=0。n：属于c1类的所有文档的出现过的单词总数目。得到公式：拉普拉斯平滑：其中，N是所有单词的数目。修正分母是为了保证概率和为1同理，以同样的平滑方案处理p(x1)nncxp111Nnncxp11114月算法在线班75/对朴素贝叶斯的思考遇到生词怎么办？拉普拉斯平滑编程的限制：小数乘积怎么办？问题：一个词在样本中出现多次，和一个词在样本中出现一次，形成的词向量相同

28、由0/1改成计数如何判断两个文档的距离夹角余弦如何判定该分类器的正确率样本中：K个生成分类器，1000-K个作为测试集交叉验证若对象特征之间不独立，会演化成何种形式？4月算法在线班76/贝叶斯网络背景知识：Serum Calcium(血清钙浓度)高于2.75mmo1/L即为高钙血症。许多恶性肿瘤可并发高钙血症。阴影部分的结点集合，称为Cancer的“马尔科夫毯”(Markov Blanket)4月算法在线班77/参考文献 Prof.Andrew Ng,Machine Learning,Stanford University Pattern Recognition and Machine Learning Chapter 8,M.Jordan,J.Kleinberg,ect,2006http:/ 更多算法面试题在http:/ 直播课程 问答社区 contact us：微博研究者July七月问答邹博_机器学习4月算法在线班79/感谢大家！恳请大家批评指正！