算法节公开课-面试算法机器学习

面试算法与机器学习七月算法邹博2015年7月7日算法节公开课2/42julyedu.com即将进行的…7月算法基础班7月11日起每周六、周日下午2-4点，一周双课。8月面试求职班7月25日起每周六、周日上午10-12点，一周双课算法节公开课3/42julyedu.com正在进行与已经完成的6月机器学习班6月27日正式开课，共计20次课。已经进行了前4次数学知识的回顾和总结，本周末开始第5次：线性回归。已经结束的3月机器学习班4月算法班5月算法班算法节公开课4/42julyedu.com内容提要算法：三字母字符串组合最短路径条数问题分割词汇问题机器学习：贝叶斯网络算法节公开课5/42julyedu.com三字母字符串组合仅由三个字符A、B、C构成字符串，且字符串任意三个相邻元素不能完全相同。如“ACCCAB”不合法，“ABBCBCA”合法。求满足条件的长度为n的字符串个数。假定不考虑整数溢出要求时间和空间复杂度不高于O(N)。算法节公开课6/42julyedu.com问题分析若当前已经有了所有长度为n-1的合法字符串，如何在末端增加一个字符，形成长度为n的字符串呢？将长度为n-1字符串分成“末尾两个字符不相等”和“末尾两个字符相等”两种情况，各自数目记做dp[n-1][0],dp[n-1][1]：算法节公开课7/42julyedu.comdp[n][0]结尾不相等/dp[n][1]结尾相等××……×AB/××……×AAdp[n][0]=2*dp[n-1][0]+2*dp[n-1][1]××……×ABA，××……×ABC××……×AAB，××……×AACdp[n][1]=dp[n-1][0]××……×ABB初始条件dp[1][0]=3dp[1][1]=0算法节公开课8/42julyedu.com状态转移方程总结与改进状态转移方程：滚动数组：使用滚动数组，将空间复杂度由O(N)降到O(1)]0][1[]1][[]1][1[*2]0][1[*2]0][[ndpndpndpndpndp]0[]1[]1[*2]0[*2]0[dpdpdpdpdp算法节公开课9/42julyedu.comCode]0[]1[]1[*2]0[*2]0[dpdpdpdpdp算法节公开课10/42julyedu.com矩阵表示与O(logN)时间复杂度由状态转移方程：得矩阵形式：从而：]0[]1[]1[*2]0[*2]0[dpdpdpdpdp0212]1[]0[]1[]0[oldnewdpdpdpdp1113210212030212]1[]0[021202120212]1[]0[02120212]1[]0[0212]1[]0[]1[]0[nnnnnndpdpdpdpdpdpdpdpdpdp算法节公开课11/42julyedu.comCode2算法节公开课12/42julyedu.com最短路径条数问题给定如图所示的无向连通图，假定图中所有边的权值都为1，显然，从源点A到终点T的最短路径有多条，求不同的最短路径的数目。算法节公开课13/42julyedu.com算法分析权值相同的最短路径问题，则单源点Dijkstra算法退化成BFS广度优先搜索，假定起点为0，终点为N：结点步数step[0…N-1]初始化为0路径数目pathNum[0…N-1]初始化为0pathNum[0]=1若从当前结点i扩展到邻接点j时：若step[j]为0，则step[j]=step[i]+1，pathN[j]=pathN[i]若step[j]==step[i+1]，则pathN[j]+=pathN[i]可考虑一旦扩展到结点N，则提前终止算法。算法节公开课14/42julyedu.comCode12算法节公开课15/42julyedu.comWordBreak分割词汇给定一组字符串构成的字典dict和某字符串str，将str增加若干空格构成句子，使得str被分割后的每个词都在字典dict中。返回满足要求的分割str后的所有句子。如：str=catsanddog,dict=[cat,cats,and,sand,dog]返回：[catsanddog,catsanddog]。算法节公开课16/42julyedu.com分割词汇问题分析记长度为i的前缀串str[0…i-1]有至少一个可行划分，用布尔变量dp[i]表示，则：catsanddog初始条件dp[0]=true；若划分到最后是空串，则说明该划分是有效的；即默认空串即在字典中。若只需要计算str是否可以划分成句子，直接返回dp[size]即可；该题目还需要返回所有的划分，所以，需要保存“前驱”。代码中将其记录为棋盘chess。10,]1[&&][][ijdictijstrjdpjidp算法节公开课17/42julyedu.comCode1DP算法节公开课18/42julyedu.comCode2算法节公开课19/42julyedu.comCode3算法节公开课20/42julyedu.comLastCode算法节公开课21/42julyedu.comMainCode算法节公开课22/42julyedu.comAuxCode下雨天.留客.天留.我不留下雨天.留客天.留.我不留下雨天.留客天.留我不.留算法节公开课23/42julyedu.com思考与小结通过递推关系，可以完成递归或动态规划代码。一般的说，动态规划即利用空间存放小规模问题的解，以便于得到总问题的解。递归的过程中，可以借鉴这种方案，保存中间解的结果，避免重复计算。因为递归计算的中间结果必然是最终结果所需要的，有些情况下，可以避免动态规划中计算所有小规模解造成的浪费。思考：走迷宫问题，往往是从出口回溯。如果需要计算具体解，则需要回溯。如果需要计算所有解，则需要深度/广度优先搜索。算法节公开课24/42julyedu.com贝叶斯网络把某个研究系统中涉及的随机变量，根据是否条件独立绘制在一个有向图中，就形成了贝叶斯网络。贝叶斯网络(BayesianNetwork)，又称有向无环图模型(directedacyclicgraphicalmodel,DAG)，是一种概率图模型，根据概率图的拓扑结构，考察一组随机变量{X1,X2...Xn}及其n组条件概率分布(ConditionalProbabilityDistributions,CPD)的性质。算法节公开课25/42julyedu.com对一个实际贝叶斯网络的分析1+2+2+4+4=13vs25算法节公开课26/42julyedu.com特殊的贝叶斯网络结点形成一条链式网络，称作马尔科夫模型Ai+1只与Ai有关，与A1,…,Ai-1无关思考：伪随机数发生器pLSA主题模型算法节公开课27/42julyedu.com通过贝叶斯网络判定条件独立—1P(a,b,c)=P(c)*P(a|c)*P(b|c)则：P(a,b|c)=P(a,b,c)/P(c)带入，得到：P(a,b|c)=P(a|c)*P(b|c)即：在c给定的条件下，a，b被阻断(blocked)，是独立的。条件独立：tail-to-tail算法节公开课28/42julyedu.com通过贝叶斯网络判定条件独立—2P(a,b,c)=P(a)*P(c|a)*P(b|c)即：在c给定的条件下，a，b被阻断(blocked)，是独立的。条件独立：head-to-tail算法节公开课29/42julyedu.com通过贝叶斯网络判定条件独立—3P(a,b,c)=P(a)*P(b)*P(c|a,b)在c未知的条件下，a，b被阻断(blocked)，是独立的：head-to-headP(b)*P(a)),(b)a,|P(c*P(b)*P(a)=c)b,P(a,cbaPc算法节公开课30/42julyedu.com举例说明这三种情况算法节公开课31/42julyedu.com将上述结点推广到结点集D-separation：有向分离对于任意的结点集A，B，C，考察所有通过A中任意结点到B中任意结点的路径，若要求A，B条件独立，则需要所有的路径都被阻断(blocked)，即满足下列两个前提之一：A和B的“head-to-tail型”和“tail-to-tail型”路径都通过C；A和B的“head-to-head型”路径不通过C以及C的子孙；如果A,B不满足D-separation，A,B有时被称为D-connected.算法节公开课32/42julyedu.com贝叶斯网络背景知识：SerumCalcium(血清钙浓度)高于2.75mmo1/L即为高钙血症。许多恶性肿瘤可并发高钙血症。恶性肿瘤病人离子钙增高的百分比大于总钙，也许可用于肿瘤的过筛试验。当高钙血症的原因难于确定时，必须考虑到恶性肿瘤的存在。阴影部分的结点集合，是Cancer的“马尔科夫毯”(MarkovBlanket)条件独立：P(S,L|C)=P(S|C)*P(L|C)算法节公开课33/42julyedu.com贝叶斯网络的计算算法节公开课34/42julyedu.com贝叶斯网络算法节公开课35/42julyedu.comHMM隐马尔科夫模型(HMM,HiddenMarkovModel)可用标注问题，在语音识别、NLP、生物信息、模式识别等领域被实践证明是有效的算法。HMM是关于时序的概率模型，描述由一个隐藏的马尔科夫链随机生成不可观测的状态随机序列，再由各个状态生成一个观测而产生观测随机序列的过程。空间序列也可以使用该模型：如分析DNA。算法节公开课36/42julyedu.comHMM的两个基本性质齐次假设：观测独立性假设：1112211,,,,tttttttiiPoioioiiPttTTTTtioPoioioioP1111,,,,算法节公开课37/42julyedu.com理解HMM框架概率计算问题给定模型和观测序列，计算模型λ下观测序列O出现的概率P(O|λ)前向-后向算法——动态规划学习问题已知观测序列，估计模型的参数，使得在该模型下观测序列P(O|λ)最大极大似然估计(给定状态序列)，Baum-Welch算法(状态序列未知)——EM算法预测问题即解码问题：已知模型和观测序列求对给定观测序列条件概率P(I|O)最大的状态序列IViterbi算法——动态规划,,BAToooO,,21,,BAToooO,,21,,BAToooO,,21算法节公开课38/42julyedu.com前向算法定义：给定λ，定义到时刻t部分观测序列为o1,o2…ot且状态为qi的概率称为前向概率，记做：可以递推计算前向概率αt(i)及观测序列概率P(O|λ)itttqioooPi,,,21算法节公开课39/42julyedu.com前向算法定义：给定λ，在时刻t部分观测序列为o1,o2…ot且状态为qi的概率为前向概率。初值：递推：对于t=1,2…T-1最终：思考：前向概率算法的时间复杂度是O(TN2)考察最耗时的递推步骤的时间复杂度。111tioNjjittbajiNiTiOP111ioibiitttqioooPi,,,21算法节公开课40/42julyedu.com其他机器学习重要内容最大熵