华南理工大学《人工智能》复习资料.doc

华南理工大学人工智能复习资料Ch 2.【状态空间表示】S：初始状态的集合F：操作的集合G：目标状态的集合例如：【状态空间图】【状态空间图搜索使用的数据结构】OPEN表：已生成但没考察的节点(待考察节点)CLOSED表：考察过的节点及节点间关系(搜索树)【广度/深度优先搜索特点】广度优先：完备的(一定能找到最优解)，搜索效率低，OPEN表为队列结构深度优先：不能保证找到最优解，OPEN表为堆栈结构有界深度优先搜索：即使能求出解，也不一定是最优可变界深度优先搜索算法：深度可变，每次深度超过阈值的点，都被当作待考察点(在CLOSED表中)【启发式搜索算法分类】按选择范围分类：全局择优搜索：考虑所有待考察节点局部择优搜索：只考虑当前节点的子节点【A*算法】f（x） g（x）h（x）g(x)为当前点的代价h(x)为距离目标的距离A*对A算法的改进：对h(x)作限制，使其总是小于实际最小距离h（x） h* （x），具有完备性【与或图】Q与Q1，Q2与等价（即Q可以分解为Q1+Q2）Q1与Q1i,Q1i或等价（即Q1可以转换为Q1i或Q1i）【与或图中的概念】本原问题：直接可解的问题。终止节点：本原问题对应的节点端节点： 无子节点的节点与节点： 子节点为与关系或节点： 子节点为或关系【与或图的广度/深度搜索】Step1:S0放入OPEN表Step2:OPEN表第一个点（记为N）取出放入CLOSED表，冠以编号n。Step3:若n可扩展：(1)扩展N，其子节点放入OPEN表(深度:尾部，广度:首部)(2)考查这些节点是否终止节点。若是，放入CLOSED表，标为可解节点，并对先辈点标示。若S0被标可解，得解。(3)从OPEN表删除具有可解先辈的节点。转Step2。Step4:若N不可扩展：(1)标示N为不可解。(2)标示先辈节。若S0被标不可解，失败。(3)从OPEN表删除具有不可解先辈的节点。转Step2。【与或图启发式搜索】由下往上更新函数值，函数值=子节点价值+子节点与父节点距离。例子见PP3 Ch3.P117-120【博弈树】与结点：对手(MIN)力图干扰MAX的选择。因此站在我方（MAX）的立场，由MIN出棋的结点具有与结点的性质。或结点：我方（MAX）力图通往取胜。MAX出棋的结点具有或结点的性质。【剪枝,剪枝】剪枝：对MIN节点,若其倒推上确界不大于MIN的父节点倒推下确界,即,则不必扩展该MIN节点其余子节点剪枝：对MAX节点,若其倒推下确界不小于MAX的父节点倒推上确界,即,则不必扩展该MAX节点其余子节点Ch 3.【离散数学相关定义】命题（proposition）：具有真假意义的语句谓词(predicate)：刻画个体的性质、状态或个体间的关系，例如P(x,y): x是y的父亲个体域：个体变元的变化范围。(如P(x,y)中，x,y是变元)全总个体域:包揽一切事物的集合函数：个体之间的对应关系,例如father(x): 值为x的父亲项：个体常元和变元都是项。若t1，t2，tn是项，则f（ t1，t2， tn ）是项原子公式：若t1，t2，tn为项，P（t1，t2，tn）称为原子谓词公式，简称原子或原子公式谓词公式：原子公式是谓词公式。若A、B是谓词公式，则 A，AB等都是谓词公式辖域：紧接于量词之后被量词作用的谓词公式指导变量：量词后的变量约束变量：量词辖域中，与该量词的指导变元相同的变量自由变量：除了约束变量之外的变量一阶谓词：仅个体变元被量化的谓词二阶谓词：个体变元、函数符号、谓词符号被量化从谓词公式得到命题：(1)把谓词中的个体变元代入个体常元(2)把谓词中的个体变元全部量化如P(x)表示x是素数, 则x P(x)，P(a)都是命题合取范式：B1 B2 Bn，如8析取范式：B1 B2 Bn，如谓词公式永真性：P对个体域D全部成立，则P在D上永真。P在全总个体集成立，则P永真谓词公式可满足性：P对个体域D至少有一个个体成立，则P在D上可满足。【常用逻辑等价式】 【常用推理定律】【子句集】文字：原子谓词公式及其否定子句：任何文字的析取【子句集特点】1. 没有蕴含词、等值词2. “”作用原子谓词3. 没有量词( 、$ )4. 合取范式5. 元素之间变元不同6. 集合形式【由谓词公式得到子句集】(对应子句集特点的序号)1. 根据蕴含等价式消去蕴含关系2. 根据量词转换律、双重否定律、摩根定律转换3. 存在量词：受x约束，则定义f(x)替换y (Skolem函数) 不受x约束，常量代替y (Skolem常量) 全称量词：直接消去4. 根据分配率合取5. 各个合取子句变量改名6. 把合取符号替换为逗号，组成集合【Skolem标准型】消去存在量词，把全称量词移到最左，右式为合取，如x P(x，f(x) R(x,g(x) Skolem标准型与原公式一般并不等价【命题逻辑中的归结原理定义】逻辑结论与前提：G是F1、F2 、 、Fn的逻辑结论，当且仅当对每个解释I，如果F1、F2 、 、Fn都为真，则G也为真。F1、F2 、 、Fn为G的前提。 互补文字：L与L归结式：C1包含L1，C2包含L2，L1与L2互补。把L1和L2删除，并把剩余部分析取，得到C12亲本子句：上例中C1与C2消解基：上例中L1与L2例如：【归结原理定理】1. 谓词公式A不可满足当且仅当其子句集S不可满足。2. G是公式F1、F2、Fn的逻辑结论，当且仅当F1 F2 Fn = G3. G是公式F1、F2、Fn的逻辑结论，当且仅当F1 F2 Fn G不可满足4. 归结式是其亲本子句的逻辑结果5. 子句集S的C1，C2替换为C12得到S1，则S1不满足=S不满足6. 子句集S添加C12得到S2，则S2不满足=S不满足【归结反演法】否定目标公式G， G加入到F1 F2 Fn中，得到子句集S。对S进行归结，并把归结结果并入S，直到得到空子句，原问题得证。【替换定义】替换：t1/x1, t2/x2, , tn/xn替换的分子：t1, t2, , tn是项替换的分母：x1, x2, , xn是互不相同的个体变元(ti,xi不同,xi不循环出现在tj中,如f(x)/y,g(y)/x不是替换)基替换：t1, t2, , tn是不含变元的项（称为基项）空替换：没有元素的替换，记作表达式：项、原子公式、文字、子句的统称基表达式：没有变元的表达式例/特例：对公式E实施替换，记为E，所得结果称为E在下的例复合/乘积： t1/x1, t2/x2, , tm/xm， u1/y1, u2/y2, , un/yn，删除t1/x1,t2/x2,tm/xm ,u1/y1,u2/y2,un/yn中：(1)ti/xi 当ti xi(2)ui/yi 当yi x1, xn得到 与 的复合或乘积，记为 例如：= a/x, f(u)/y ,y/z, =b/u,z/y,g(x)/z从 a/x，f(b)/y ，z/z，b/u，z/y，g(x)/z,删去：z/z，z/y，g(x)/z得到：= a/x， f(b)/y ，b/u【合一定义】合一：F1=F2=Fn则为F的合一，F为可合一的 （一个公式的合一一般不唯一）最一般合一：为F的一个合一，如果对F任何合一都存在使得 ，则为F的最一般合一，极为MGU（一个公式集的MGU不唯一）差异集：S是具有相同谓词名的原子公式集，从各公式左边开始，同时向右比较，直到发现第一个不都相同的项为止，用这些项的差异部分组成的集合【合一算法】Step1：置k0，FkF， k ；Step2：若Fk只含有一个谓词公式，则算法停止， k就是最一般合一；Step3：求Fk的差异集Dk；Step4：若Dk中存在元素xk和tk ，其中xk是变元， tk是项且xk不在tk中出现，则置Sk 1Fktk/ xk ,k+1= k tk/ xk ，kk+1然后转Step2；Step5：算法停止，F的最一般合一不存在。对任一非空有限可合一的公式集，一定存在最一般合一，而且用合一算法一定能找到最一般合一【合一算法例子】求公式集FQ(a,x,f(g(y),Q(z,h(z,u),f(u)的最一般合一解：解k0；F0F，0，D0a,z1 0a/z= a/zF1= F0a/z= Q(a,x,f(g(y),Q(a,h(a,u),f(u)k1；D1=x, h(a,u)2= 1h(a,u) /x a/z,h(a,u) /xF2= F1a/z, h(a,u) /x= P(a, h(a,u) ,f(g(y),P(a,h(a,u),f(u)k2；D2g(y),u3 a/z ,h(a, g(y) /x ,g(y)/uF3= F2g(y)/u= P(a,h(a,g(y),f(g(y) S3单元素集 ， 3为MGU。 【谓词逻辑中的归结原理定义】二元归结式（二元消解式）: （C1 L1 ） （ C2 L2 ）,其中：亲本子句：C1，C2为无相同变元的子句消解文字：L1，L2为L1和L2的最一般合一因子：C 。其中为C的子句文字的最一般合一单因子：C 为单元句子【归结式】子句的C1，C2归结式，是下列二元归结式之一:（1） C1和C2的二元归结式；（2） C1和C2的因子的二元归结式；（3） C1因子和C2的二元归结式；（4） C1的因子和C2的因子的二元归结式。归结注意事项：(1) 两个子句不能含有相同的变元(2) 归结的子句内部含有可合一的文字，则需进行简化【谓词逻辑的消解原理/归结原理】谓词逻辑中的消解（归结）式是它的亲本子句的逻辑结果：C1 C2 （C1 L1 ） （ C2 L2 ）【谓词逻辑的定理】如果子句集S是不可满足的，那么必存在一个由S推出空子句的消解序列。【应用归结原理求取问题答案】Step1：前提化为子句集SStep2：确定目标谓词，化为子句，并析取助谓词新子句，并入到S形成S。Step3：对S应用归结原理。Step4：当只剩辅助谓词时，归结结束。(例子见CH3 P105 )【归结策略】Step1：子句集S置入CLAUSES表Step2：若Nil在CLAUSES，归结成功Step3：若CLAUSES存在可归结子句对，则归结，并将归结式并入CLAUSES表，step2Step4：归结失败【广度优先搜索归结策略】用于确定归结策略step3的搜索次序第一轮：0层（原子句集S）两两进行归结，产生1层下一轮：1层与0、1层两两进行归结，得到2层再一轮：2层与0、1、2层两两进行归结，得到3层如此类推，直至出现Nil【归结策略完备性】一个归结策略是完备的，如果对于不可满足的子句集，使用该策略进行归结，最终必导出空子句Nil。（广度优先是完备的，亦称水平浸透法）【归结策略出发点】（1）简化性策略。（2）限制性策略。（3）有序性策略（包含排序策略）【归结策略类型】删除策略支持集策略线性归结策略单元归结策略语义归结策略祖先过滤型策略【正向演绎推理-初始事实F0】l 任意谓词公式l 前束范式表示；消去量词，改名l 与或图表示：析取部分用与节点表示 合取部分用或节点表示【正向演绎推理- F规则】l 形如 L=W，L为单一文字l W为任意与或型谓词公式；(消去量词，改名)【正向演绎推理目标谓词】l 文字的析取式(消去量词，改名)【正向演绎推理图解】【代换集一致性】设有代换集u1,u2,，un，其中每个ui都是代换ti1/ vi1, ti2/ vi2,， tim(i)/ vim(i)U1v11, , vim(1),， vn1, , vnm(n)（所有下边的变量）U2t11, , tim(1),， tn1, , tnm(n) （所有上边的项）u1,u2,，un是一致的，当且仅当U1和U2是可合一合一复合：U1和U2的最一般合一解树上所有代换是一致的，则该问题有解，最后的代换是合一复合U【反向演绎推理-目标公式】任意谓词公式(消去量词，改名)与或图表示：与节点对应合取；或节点对应析取【反向演绎推理-B规则】l W=L；l L为单一文字；l W为任意与或型谓词公式(消去量词，改名)【反向演绎推理图解】【正向/反向演绎对比】【双向演绎推理】l 分别从基于事实的F-规则正向推理出发，也从基于目标的B-规则逆向推理出发，同时进行双向演绎推理。l 终止的条件：正向推理和逆向推理互相完全匹配。即所有得到的正向推理与或树的叶节点，正好与逆向推理得到的与或图的叶节点一一对应匹配【不确定性知识分类】随机不确定性(概率)模糊不确定性(软概念)不完全性(事物了解不充分)不一致性(时间推移)【逆概率方法公式】【逆概率多个证据】其实就是bayes公式。严格要求各证据独立。【修正因子】方括号内为修正因子： 【可信度法不确定性度量】If E then H (CF(H, E)其中CF(H, E)为可信度因子/规则强度CF(H,E)=MB(H,E) - MD(H,E)【MB和MD】MB（Measure Belief）：信任增长度，因证据E的出现使结论H为真的信任增长度：MD（Measure Disbelief）：不信任增长度，因E的出现使H为真的不信任增长度：因此，CF(H,E)为：【可信度法-不确定性传播】组合证据：E=E1 E2 En ：CF(E)=minCF(E1) ,CF(E2) , CF(En)E=E1 E2 En ：CF(E)=maxCF(E1) ,CF(E2) , CF(En)E= E1 ：CF(E)=-CF(E1)推理结论的CF值：CF(H) = CF(H,E) max 0, CF(E) 重复结论的CF值：【主观贝叶斯法】表示形式：if E then (LS, LN) H ( P(H) )【LS和LN】LS：充分性量度，E 对H支持程度，范围为 0， ）：LN：必要性量度， E对H支持程度，范围为 0， ）：LS、LN0,不独立，有如下约束关系：当LS1时，LN1；当LS1；当LS=1时，LN=1；通过LN,LS把先验概率转化为后验概率：l LS= O(H|E)/ O(H)P(H|E) 越大，O(H|E)越大，则LS越大，表明E对H为真的支持越强，当 LS ，P(H|E) 1，E 的存在对 H 为真是充分的l LN=O(H| E) /O(H)P(H| E )越大，O(H| E)越大，则LN越大，表明 E 对 H 为真的支持越强。当 LN = 0 ，P(H| E) = 0，E 的不存在导致 H 为假，说明E对H是必要的【几率函数】【P(E|S)与P(H|S)】其中C(E|S)由题目给出，用于刻画不确定性，值越大，证明在观察S下，E存在的可能性越大。将两式结合，和得到CP公式：【贝叶斯网络图示】l 以随机变量为节点，以条件概率为节点间关系强度的有向无环图（Directed Acyclic Graph，DAG）l 每个节点旁的条件概率表(简称CPT)中的值对应一个条件事件的概率【条件独立关系】贝叶斯网络中节点相互独立：(1)给定父节点，一个节点与它的非后代节点是条件独立的(2)给定一个节点的父节点、子节点以及子节点的父节点(Markov blanket)，这个节点对于其它节点都是条件独立的【条件独立关系的判定】d-分离（d-separation)：给定y，x和z条件独立：给定y，x和z条件独立：给定y，x和z不条件独立：【贝叶斯网络推理】概率推理可分为：因果推理、诊断推理、辩解推理、混合推理【因果推理】由原因到结果的推理，自上而下的推理，例如已知L成立时，求P(M|L)【诊断推理】由结果到原因的推理,自下而上的推理。例如已知M成立，求P(L|M)【辩解推理】仅仅给定B，求P(L)。这种情况下，可以说B解释M，使L不确定。Ch 5.【FIND-S算法】候选假设：“?”：可接受任何值“f”：不接受任何值算法流程：1.将h初始化为H中最特殊假设2.对每个正例x（循环） 对h的每个属性约束ai 如果x满足ai 那么不做任何处理 否则将h中ai替换为x满足的更一般的约束3.输出假设h【候选消除算法】【BP算法误差项】更新规则:【BP算法权值更新】The learning rule for the hidden-to-output units :The learning rule for the input-to-hidden units: Summary:Ch 6.【遗传算法的基本操作】(1) 复制从旧种群选择生命力强的个体进行复制。实现方法：根据个体适应度/总适应度，为每个个体分配概率范围(01)，产生随机数，选择匹配的个体：(2) 交叉在匹配池中任选两个染色体，随机选择一点或多点交换点位置；交换双亲染色体交换点右边的部分，即可得到两个新的染色体数字串(3) 变异在染色体以二进制编码的系统中，它随机地将染色体的某一个基因由1变为0，或由0变为1。【遗传算法的特点】(1) 对参数的编码进行操作，而非参数本身(因此可模仿自然界进化机制)(2) 同时使用多个搜索点的搜索信息(搜索效率高、并行、不陷入局部最优)(3) 直接以目标函数作为搜索信息(不需导数和其他辅助信息)(4) 使用概率搜索技术(复制交叉变异基于概率，有很好灵活性)(5) 在解空间进行高效启发式搜索(而非盲目搜索、完全随机搜索)(6) 对待寻优的函数基本无限制(不要求连续、可微)(7) 具有并行计算的特点(适合大规模复杂问题的优化)【遗传算法的构成要素】(1) 染色体编码方法使用固定长度的二进制符号来表示群体中的个体(2) 个体适应度评价目标函数值J到个体适应度f之间的转换规则(3) 遗传算子 选择运算:使用比例选择算子； 交叉运算:使用单点交叉算子； 变异运算:使用基本位变异算子或均匀变异算子(4) 基本遗传算法的运行参数下述4个运行参数需要提前设定： M：群体大小，即群体中所含个体的数量，一般取为20100； G：遗传算法的终止进化代数，一般取为100500； Pc：交叉概率，一般取为0.40.99； Pm：变异概率，一般取为0.00010.1。十大算法1.【C4.5】【信息增益的计算】期望信息:设样本集合s含有si 个类为Ci 的元组, i = 1, , m，则对一个给定的样本分类所需的期望信息是：熵:具有值 a1,a2,av的属性A的熵E(A)为属性A导致的s的划分的期望信息的加权平均和：信息增益:例子:【信息增益比】【C4.5算法】1.创建根节点2.若所有样本为类x，标记为类x3.若Attribute为空，标记为最普遍的类4.选择信息增益比最大的属性，每个可能值建立子节点，递归解决2.【k-means】【聚类目标】聚类内部距离平方之和的最小化：【k-means算法】定义:k-means算法以k为输入参数，把n个对象的集合分为k个集，使得结果簇内的相似度高，而簇间的相似度低。簇的相似度是关于簇中对象的均值度量，可以看做簇的质心或重心。算法：1. 把对象划分成k 个非空子集；2. 计算当前的每个聚类的质心作为每个聚类的种子点；3. 把每一个对象分配到与它最近的种子点所在的聚类4. 返回到第2步, 当满足某种停止条件时停止。停止条件:1. 当分配不再发生变化时停止；2. 当前后两次迭代的目标函数值小于某一给定的阈值；3. 当达到给定的迭代次数时。时间复杂性：计算复杂度为O(nkt)，其中n是对象的总数，k是簇的个数，t是迭代的次数3.【SVM】【Margin】* Margin is defined as the width that the boundary could be increased by before hitting a data point* The linear discriminant function (classifier) with the maximum margin is the best.* Data closest to the hyper plane are support vectors.【Maximum Margin Classification】* Maximizing the margin is good according to intuition and theory.* Implies that only support vectors are important; other training examples are ignorable.【Kernels】* We may use Kernel functions to implicitly map to a new feature space* Kernel must be equivalent to an inner product in some feature space【Solving of SVM】* Solving SVM is a quadratic programming problemTarget: maximum margin - = Such that 【Nonlinear SVM】The original feature space can always be mapped to some higher-dimensional feature space where the training set is separable【Optimization Problem】Dual Problem for (ai is Lagrange multiplier):Solution(Each non-zero ai indicates that corresponding xi is a support vector.):Classifying function (relies on an inner product between the test point x and the support vectors xi. involved computing the inner products xi * xj between all training points):【Slack variables】Target：Dual Problem of the soft margin is the same for hard.Solution:Classifying function of the soft margin is the same.【Kernel Trick】* Map data points to higher dimensional space in order to make them linearly separable.* Since only dot product is used, we do not need to represent the mapping explicitly.Discriminant function: (No need to know this mapping explicitly, because we only use the dot product of feature vectors in both the training and test.)Kernel function: dot product of two feature vectors in some expanded feature spce : 【Nonlinear SVM optimization】4.【Apriori】【支持度与置信度】规则AC：【用Apriori算法挖掘强关联规则】连接操作: A B C X 和 A B C Y可连接，生成A B C X Y(个数相同，只有最后一个元素不同)生成频繁k-项集Lk的算法：根据k-1项集Lk-1，连接生成候选集Ck筛选出Ck中支持度大于min_sup的元素，构成Lk例子：从频繁项集产生关联规则根据频繁项集I，生成全部非空子集。对于每个子集m, 若sup(m( I-m ) min_sup，输出此规其中sup(m( I-m ) = 事务mI-m计数事务m计数 = 事务 I 计数事务 m 计数5.【EM】在概率模型中寻找参数最大似然估计或者最大后验估计的算法，其中概率模型依赖于无法观测的隐藏变量。最大期望算法经过两个步骤交替进行计算：l 第一步是计算期望（E），利用对隐藏变量的现有估计值，计算其最大似然估计值；l 第二步是最大化（M），最大化在 E 步上求得的最大似然值来计算参数的值。M 步上找到的参数估计值被用于下一个 E 步计算中，这个过程不断交替进行。总体来说，EM的算法流程如下：1.初始化分布参数2.重复直到收敛：E步骤：估计未知参数的期望值，给出当前的参数估计。M步骤：重新估计分布参数，以使得数据的似然性最大，给出未知变量的期望估计。6.【PageRank】【基本思想】* PageRank将 网页x指向网页y的链接视为x给y的一张投票。 * 然而PageRank 不仅仅考虑网页得票的绝对数目，它还分析投票者本身的权威性. - 来自权威网页的投票能够提升被投票网页的权威性【更具基本思想】* 链接是源网页对目标网页权威性的隐含表达. - 网页i入边（in-links）越多，表示i的权威性值越高。* 指向网页i的网页本身也有自己的权威性值- 对于网页i的权威性得分而言，一个具有高分值的源网页比一个低分值的源网页更加重要。 - 换言之，若其它权威性网页指向网页i，则i也可能是权威性网页。 【PageRank优点与缺点】优点：(1) 防欺骗 网页所有者难以设置其它重要网页指向自己的网页. (2) ageRank 值独立于查询，是一种全局度量. PageRank 值是通过所有网页计算得到并加以存储，而不是提交查询时才计算. 缺点：不能区分全局重要性网页和查询主题重要性网页【Web图】把Web视为有向图 G = (V, E)，V表示顶点（网页），一条边(i, j) E当且仅当网页i指向网页j，n为总的网页数。 网页P(i)定义为:Oj 是网页j的出边数A 是Web图的邻接矩阵表示：通过使用幂法可以求解，但是Web图不符合求解条件。【转移概率矩阵】Aij 表示用户在状态i（网页i）转移到状态j（网页j）的概率。（公式和web图一致）k步转移后的概率分布：【稳态概率分布】对于任意初始概率向量P0, Pk 将收敛于一个稳定的概率向量p, 即, p 可作为PageRank 值向量，其合理性：- 它反映了随机冲浪的长期概率. - 一个网页被访问的概率越高，其权威性越高. 【收敛性】一个有限马尔可夫链收敛于一个唯一的稳态概率分布：如果矩阵A是不可约（irreducible）和非周期的（aperiodic）。条件1：随机矩阵A不是一个随机矩阵，因为很多网页没有出边，导致A中某些行全为0.解决方案1：删除没有出边的网页. 解决方案2：将没有出边的网页指向网络中所有其它网页条件2：不可约不可约意味着强连通(所有点对都有双向路径)，A不符合。条件3：非周期从i到i的所有路径都是K的倍数(k1)，则成为周期的。一个马尔科夫链所有状态都是非周期的，则为非周期。解决方案：指定一个参数d，将每一个网页（状