人工智能复习总结

一、约束推理1.概述约束满足问题(ConstraintSatisfactionProblem,简称CSP)包含一组变量与一组变量间的约束。变量表示领域参数，每个变量都有一个固定的值域。约束满足问题的目标就是找到所有变量的一个（或多个）赋值，使所有约束都得到满足。目前约束推理的研究主要集中在两个方面:约束搜索,约束语言2.回溯算法Backtracking-Top(P)1f:=thenullassignment2returnBacktracking(f,P)Backtracking(f,P)1iffisatotalassignmentofthevariablesinP2answer:=f3else4v:=somevariableinPthatisnotyetassignedavaluebyf5answer:=Unsat6foreachvaluexwhileanswer=Unsat7f(v):=x8iffsatisfiestheconstraintsinP9answer:=Backtracking(f,P)10returnanswer提高回溯算法的效率受约束最多的变量:选择合法值最少的变量选择产生约束最多的变量:约束产生最多的变量—选择使其他变量受到约束最多的变量给定一个变量,选择产生约束最少的值:选择使剩余的变量不合法值最少的值前置检测：追踪没有赋值变量的剩余合法值当有变量没有任何合法值的时候则停止搜索约束传播Constraintpropagation提前检测可以将信息从已经赋值变量传递到没有赋值的变量,但是不能提前检测所有的失败约束传播可以反复地强制局部约束简单的约束传播方式,可以保证每条弧具有一致性弧vivj是一致的当且仅当,对于vi当前域中的每个值x存在vj的当前域中的某值y使得弧vivj满足约束如果vi失去了一个值，那么vi的邻居需要重新检测弧一致性可以在提前检测之前发现失败可以作为赋值的前处理或者后处理3.约束传播修改算法REVISE(vi,vj)1DELETEfalse;2foreachxDido3ifthereisnosuchyDj4suchthat(x,y)isconsistent,5then6deletexfromDi;7DELETEtrue;8endif9endfor10returnDELETE;11endREVISEAC-112repeat3CHANGEfalse;4foreach(vi,vj)Qdo5CHANGEREVISE(vi,vj)CHANGE;6endfor;7untilnot(CHANGE);8endAC-1AC-31;2WhileQnotempty3Selectanddeleteanyarc(vi,vj)fromQ;4If(REVISE(vi,vj))5ThenQ{(vs,vi)suchthat(vs,vi)arcs(G),6si,sj};6endfor;7endwhile;8endAC-34..局部搜索求解CSPs爬山算法Hill-climbing(vi,vj)arcs,QGij(vi,vj)arcs,QGij模拟退火SimulatedAnnealing5.回跳法Backjumping-Top(P)1f:=thenullassignment2answer,conflict-set:=Backjumping(f,P)3returnanswerBackjumping(f,P)1iffisatotalassignmentofthevariablesinP2answer:=f,3else4v:=somevariableinPthatisnotyetassignedavaluebyf5answer:=Unsat6conflict-set:=7foreachvalue8f(v):=x9iffsatisfiestheconstraintsinP10answer,new-conflicts:=Backjumping(f,P)11else12new-conflicts:=thesetofvariablesinaviolatedconstraint13ifanswerUnsat14returnanswer,15elseifvnew-conflicts16returnUnsat,new-conflicts17else18conflict-set:=conflict-set(new-conflicts{v})19returnUnsat,conflict-set二、案例推理1.概述在基于案例推理(Case-BasedReasoning,简称CBR)中，把当前所面临的问题或情况称为目标案例(targetcase)，而把记忆的问题或情况称为源案例(basecase)。粗略地说，基于案例推理就是由目标案例的提示而获得记忆中的源案例，并由源案例来指导目标案例求解的一种策略。2.流程3.案例问题求解4.案例表示网络上的每一节点表示一语义记忆单元，形式地描述为下例结构：SMU={SMU_NAMEslotconstraintslotstaxonomyslotscausalityslotssimilarityslotspartonomyslotscaseslotstheoryslots}5.案例检索a.相似性度量1）数值性属性的相似度sim(Vi,Vj)＝1－d(Vi,Vj)＝1－dijdij＝∣Vi－Vj∣其中，Vi、Vj是某个属性V的两个属性值。2)枚举性属性的相似度①只要两个属性值不同，就认为两者之间的相似度为0，否则为1；（质上/定义通用）②针对不同的属性值间不同的关系给以具体的定义。（量上/人来预定义，与领域知识相关）3)有序属性的相似度有序属性介于数值和枚举型属性之间，也介于定性和定量之间。属性值有序，可以赋予不同等级值间有不同的相似度。绝对值距离(Manhattan):欧氏距离(Euclidean)麦考斯基距离b.案例检索方法1)最近邻居2)决策树决策树（DecisionTree）是一种简单但是广泛使用的分类器。通过训练数据构建决策树，可以高效的对未知的数据进行分类。3)CBR使用模糊逻辑将模糊语言值的符号处理过程形式化，语言值与属性描述特性的差异有关6.案例的复用替换法、转换法、特定目标驱动法、派生重演法。7.基于案例的学习1NijikjkkdVV21()NijikjkkdVV1/1qNqijikjkkdVVkxfxfkiiq1)(:)(211),(1where)(:)(iqikiikiiiqdwwfwfxxxx三、概率推理1.贝叶斯概率论基础先验概率：先验概率是指根据历史的资料或主观判断所确定的各事件发生的概率，该类概率没能经过实验证实，属于检验前的概率，所以称之为先验概率。后验概率：后验概率一般是指利用贝叶斯公式，结合调查等方式获取了新的附加信息，对先验概率进行修正后得到的更符合实际的概率。联合概率：联合概率也叫乘法公式，是指两个任意事件的乘积的概率，或称之为交事件的概率。全概率公式设A1,A2,…,An是两两互斥的事件，且P(Ai)0，i=1,2,…,n,A1+A2+…,+An=Ω；另有一事件B：称满足上述条件的A1,A2,…,An为完备事件组.贝叶斯公式设A1,A2,…,An是样本空间中的完备事件组且P(Ai)0，i=1,2,…,n,另有一事件B，则有2.贝叶斯规则基于条件概率的定义p(Ai|E)是在给定证据下的后验概率p(Ai)是先验概率P(E|Ai)是在给定Ai下的证据似然p(E)是证据的预定义后验概率niiiABPAPBP1)()()(｜njjjiiiABPAPABPAPBAP1)()()()()|(｜｜分解联合分布为几个局部分布的乘积：P(xi)=ΣπiP(xi|πi)P(πi)P(B|j,m)=P(B,j,m)=eaP(B,e,a,j,m)=eaP(b)P(e)P(a|b,e)P(j|a)P(m|a)=P(b)eP(e)aP(a|b,e)P(j|a)P(m|a)3.变量剔除12(,,)(|())niiiPxxxPxparentsx4.Clustering算法（JointTree算法）单独节点联合起来形成Cluster节点，使得BN结构成为一棵多树（Polytree）多树——单连通网络，即任何两节点间至多只有一条路径相连5.贝叶斯网络的近似推理马尔可夫链蒙特卡罗（MCMC）算法执行过程示例：MCMC算法执行步骤：证据变量Sprinkler,WetGrass固定为true隐变量Cloudy和查询变量Rain随机初始化，例如，Cloudy=true,Rain=false，初始状态为：[C=true,S=true,R=false,W=true]反复执行如下步骤：（1）根据Cloudy的马尔可夫覆盖(MB)变量的当前值，对Cloudy采样，即根据P(Cloudy|Sprinkler=true,Rain=false)（即转移概率）来采样。即：P(C|S,~R)=P(C,S,~R)/P(S,~R)=P(C)P(S|C)P(~R|C)/[P(C)P(S|C)P(~R|C)+P(~C)P(S|~C)P(~R|~C)]=(0.50.10.2)/[0.50.10.2+0.50.50.8]=0.04762再由计算机生成一个随机数q[0,1]。比较转移概率值与随机数q的大小，以决定是继续停留在原状态，还是转移到下一个新的状态。判别方法如下：ifqP(C|S,~R)then转移到下一个新状态；otherwise停留在原状态.对于本例子，假设生成的随机数q=0.0389，可知，转移概率P(Cloudy|Sprinkler=true,Rain=false)=0.04762q=0.0389，所以，Cloudy由true状态转移到新状态false，即采样结果为：Cloudy=false。故新的当前状态为：[C=false,S=true,R=false,W=true]（2）根据Rain节点的马尔可夫覆盖(MB)变量的当前值，对Rain采样，即根据P(Rain|Cloudy=false,Sprinkler=true,WetGrass=true)来采样。假设采样结果为：Rain=true。故新的当前状态为：[C=false,S=true,R=true,W=true]【注】：上述过程中所访问的每一个状态都是一个样本，能对查询变量Rain的估计有贡献。（3）重复上述步骤，直到所要求的访问次数N。若为true,false的次数分别为n1,n2，则查询解为：Normalize(n1,n2)=n1/N,n1/N若上述过程访问了20个Rain=true的状态和60个Rain=false的状态，则所求查询的解为0.25,0.75。算法描述：functionMCMC-Ask(X,e,bn,N)returnP(X|e)localvariables:N[X],//关于查询变量X的向量计数，初值0Z，//bn中的非证据变量集x，//bn的当前状态利用Z中变量的随机值来初始化x；forj=1toNdoN(x)N(x)+1;//x是当前状态x中的查询变量X的值foreachZiinZdo给出Zi的马尔可夫覆盖MB(Zi)，并根据P(Zi|mb(Zi))来采样的Zi值;returnNormalize(N[X])//对N[X]进行归一化四、决策树1.概念决策树是一个预测模型；他代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象，而每个分叉路径则代表的某个可能的属性值，而每个叶结点则对应从根节点到该叶节点所经历的路径所表示的对象的值。一个决策树包含三种类型的节点：1.决策节点——通常用矩形框来表式2.机会节点——通常用圆圈来表式3.终结点——通常用三角形来表示2.信息论熵：表示了概率分布的不