《华南理工大学《人工智能》复习资料.docx》由会员分享，可在线阅读，更多相关《华南理工大学《人工智能》复习资料.docx（24页珍藏版）》请在三一办公上搜索。
1、华南理工大学人工智能复习资料华南理工大学人工智能复习资料 Ch 2. f gh g(x)为当前点的代价 h(x)为距离目标的距离 A*对A算法的改进： 对h(x)作限制，使其总是小于实际最小距离h h* ，具有完备性 S：初始状态的集合 F：操作的集合 G：目标状态的集合 ，ab，c，Q0，Q7 例如： G 3. 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
2、Fn中，得到子句集S。对S进行归结，并把归结结果并入S，直到得到空子句，原问题得证。 求公式集FQ(a,x,f(g(y),Q(z,h(z,u),f(u)的最一般合一 解： 解 k0； F0F，0，D0a,z 1 0a/z= a/z F1= 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) /x F2= F1a/z, h(a,u) /x= P(a, h(a,u) ,f(g(y),P(a,h(a,u),f(u) k2； D2g(y),u 3 a/z ,h(a, g(y) /x ,g(y)/u
3、F3= F2g(y)/u= P(a,h(a,g(y),f(g(y) S3单元素集 ， 3为MGU。 替换：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， u
4、1/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 二元归结式: ,其中： 亲本子句：C1，C2为无相同变元的子句 消解文字：L1，L2 为L1和L2的最一般合一 因子：C 。其中为C的子句文字的
5、最一般合一 单因子：C 为单元句子 子句的C1，C2归结式，是下列二元归结式之一: C1和C2的二元归结式； C1和C2的因子的二元归结式； C1因子和C2的二元归结式； C1的因子和C2的因子的二元归结式。 归结注意事项： (1) 两个子句不能含有相同的变元 (2) 归结的子句内部含有可合一的文字，则需进行简化 有序性策略 删除策略 支持集策略 线性归结策略 单元归结策略 语义归结策略 祖先过滤型策略 谓词逻辑中的消解式是它的亲本子句的逻辑结果： C1 C2 l 任意谓词公式 l 前束范式表示；消去量词，改名 l 与或图表示：析取部分用与节点表示 合取部分用或节点表示 如果子句集S是不可满足
6、的，那么必存在一个由S推出空子句的消解序列。 l 形如 L=W，L为单一文字 l W为任意与或型谓词公式；(消去量词，改名) Step1：前提化为子句集S Step2：确定目标谓词，化为子句，并析取助谓词新子句，并入到S形成S。 Step3：对S应用归结原理。 Step4：当只剩辅助谓词时，归结结束。 (例子见CH3 P105 ) l 文字的析取式(消去量词，改名) F0:P(x)(Q(x)R(x)F1:P(y)S(y)F2:Q(z)N(z)G:S(a)N(a)N(a)a/x S(a)a/x S(x)Q(z)F1 x/z P(y)F2 x/y P(x)F0 P(x)(Q(x)R(x)Q(x)R
7、(x)Q(x)R(x)N(x)Step1：子句集S置入CLAUSES表 Step2：若Nil在CLAUSES，归结成功 Step3：若CLAUSES存在可归结子句对，则归结，并将归结式并入CLAUSES表，step2 Step4：归结失败 用于确定归结策略step3的搜索次序 第一轮：0层两两进行归结，产生1层 下一轮：1层与0、1层两两进行归结，得到2层 再一轮：2层与0、1、2层两两进行归结，得到3层 如此类推，直至出现Nil 一个归结策略是完备的，如果对于不可满足的子句集，使用该策略进行归结，最终必导出空子句Nil。 设有代换集u1,u2,，un，其中每个ui都是代换ti1/ vi1,
8、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 任意谓词公式(消去量词，改名) 与或图表示：与节点对应合取； 或节点对应析取 l W=L； l L为单一文字； l W为任意与或型谓词公式(消去量词，改名) l 分别从基于事实的F-规则正向推理出发，也从基于目标的B-规则逆向推理出发，同时
9、进行双向演绎推理。 l 终止的条件：正向推理和逆向推理互相完全匹配。即所有得到的正向推理与或树的叶节点，正好与逆向推理得到的与或图的叶节点一一对应匹配 CAT(x)DOG(y)AFRAID(x,y)CAT(x)DOG(y)AFRAID(x,y)x/y2,y/x2R2x/x5CAT(x5)FIDO/yDOG(FIDO)AFRAID(y2,x2)R5MEOWS(x)BARKS(y)FRIENDLY(y)MYRTLE/xMEOWS(MYERTLE)FIDO/yBARKS(FIDO)y/x1FRIENDLY(x1)R1随机不确定性(概率) 模糊不确定性(软概念) 不完全性(事物了解不充分) 不一致性(
10、时间推移) FIDO/yWAGS-TAIL(y)FIDO/yDOG(y)P(Hi|E)=P(E|Hi)P(Hi)WAGS-TAIL(FEDO)DOG(FIDO)P(E|Hj=1nj)P(Hj)P(Hi/E1E2LEm)P(E1/Hi)P(E2/Hi)LP(Em/Hi)P(Hi)P(E/H1j=1nj)P(E2/Hj)LP(Em/Hj)P(Hj)其实就是bayes公式。严格要求各证据独立。 方括号内为修正因子： P(H|E)=P(E|H)P(H)P(E) If E then H (CF(H, E) 其中CF(H, E)为可信度因子/规则强度 CF(H,E)=MB(H,E) - MD(H,E) M
11、B： 信任增长度，因证据E的出现使结论H为真的信任增长度： 1当P(H)1MB(H,E)=maxP(H|E),P(H)-P(H)否则1-P(H) 通过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是必要的 MD： 不信任增长
12、度，因E的出现使H为真的不信任增长度： 1当P(H)0MD(H,E)=minP(H|E),P(H)-P(H)否则-P(H) 因此，CF(H,E)为： P(H|E)-P(H)1-P(H)CF(H,E)=0P(H)-P(H|E)-P(H)当P(H|E)P(H)当P(H|E)P(H)当P(H|E)0,不独立，有如下约束关系： 当LS1时，LN1； 当LS1； 当LS=1时，LN=1； 贝叶斯网络中节点相互独立： (1)给定父节点，一个节点与它的非后代节点是条件独立的 (2)给定一个节点的父节点、子节点以及子节点的父节点(Markov blanket)，这个节点对于其它节点都是条件独立的 d-分离 对
13、h的每个属性约束ai Summary: Ch 6. (1) 复制 从旧种群选择生命力强的个体进行复制。 实现方法：根据个体适应度/总适应度，为每个个体分配概率范围(01)，产生随机数，选择匹配的个体： 十大算法 1. 期望信息: 设样本集合s含有si 个类为Ci 的元组, i = 1, , m，则对一个给定的样本分类所需的期望信息是： (2) 交叉 在匹配池中任选两个染色体，随机选择一点或多点交换点位置；交换双亲染色体交换点右边的部分，即可得到两个新的染色体数字串 (3) 变异 在染色体以二进制编码的系统中，它随机地将染色体的某一个基因由1变为0，或由0变为1。 熵: 具有值 a1,a2,av
14、的属性A的熵E(A)为属性A导致的s的划分的期望信息的加权平均和： 信息增益: 例子: (1) 对参数的编码进行操作，而非参数本身 (因此可模仿自然界进化机制) (2) 同时使用多个搜索点的搜索信息 (搜索效率高、并行、不陷入局部最优) (3) 直接以目标函数作为搜索信息 (不需导数和其他辅助信息) (4) 使用概率搜索技术 (复制交叉变异基于概率，有很好灵活性) (5) 在解空间进行高效启发式搜索 (而非盲目搜索、完全随机搜索) (6) 对待寻优的函数基本无限制 (不要求连续、可微) (7) 具有并行计算的特点 (适合大规模复杂问题的优化) 1.创建根节点 2.若所有样本为类x，标记为类x
15、3.若Attribute为空，标记为最普遍的类 4.选择信息增益比最大的属性，每个可能值建立子节点，递归解决 (1) 染色体编码方法 使用固定长度的二进制符号来表示群体中的个体 (2) 个体适应度评价 目标函数值J到个体适应度f之间的转换规则 (3) 遗传算子 选择运算:使用比例选择算子； 交叉运算:使用单点交叉算子； 变异运算:使用基本位变异算子或均匀变异算子 (4) 基本遗传算法的运行参数 下述4个运行参数需要提前设定： M：群体大小，即群体中所含个体的数量，一般取为20100； G：遗传算法的终止进化代数，一般取为100500； Pc：交叉概率，一般取为0.40.99； Pm：变异概率，
16、一般取为0.00010.1。 2. 聚类内部距离平方之和的最小化： 定义: k-means算法以k为输入参数，把n个对象的集合分为k个集，使得结果簇内的相似度高，而簇间的相似度低。簇的相似度是关于簇中对象的均值度量，可以看做簇的质心或重心。 算法： 1. 把对象划分成k 个非空子集； 2. 计算当前的每个聚类的质心作为每个聚类的种子点； 3. 把每一个对象分配到与它最近的种子点所在的聚类 4. 返回到第2步, 当满足某种停止条件时停止。 停止条件: 1. 当分配不再发生变化时停止； 2. 当前后两次迭代的目标函数值小于某一给定的阈值； 3. 当达到给定的迭代次数时。 时间复杂性： 计算复杂度为
17、O(nkt)，其中n是对象的总数，k是簇的个数，t是迭代的次数 Dual Problem for multiplier): (ai is Lagrange 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 x
18、i * xj between all training points): 3. * 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. Target： * Maximizin
19、g the margin is good according to intuition and theory. * Implies that only support vectors are important; other training examples are ignorable. Dual Problem of the soft margin is the same for hard. Solution: * We may use Kernel functions to implicitly map to a new feature space * Kernel must be eq
20、uivalent to an inner product in some feature space Classifying function of the soft margin is the same. * Solving SVM is a quadratic programming problem Target: maximum margin - * Map data points to higher dimensional space in order to make them linearly separable. * Since only dot product is used,
21、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 : = Such that
22、The original feature space can always be mapped to some higher-dimensional feature space where the training set is separable 从频繁项集产生关联规则 根据频繁项集I，生成全部非空子集。 对于每个子集m, 若sup(m( I-m ) min_sup，输出此规 其中sup(m( I-m ) = = 4. 5. 在概率模型中寻找参数最大似然估计或者最大后验估计的算法，其中概率模型依赖于无法观测的隐藏变量。 最大期望算法经过两个步骤交替进行计算： l 第一步是计算期望，利用对隐藏
23、变量的现有估计值，计算其最大似然估计值； l 第二步是最大化，最大化在 E 步上求得的最 大似然值来计算参数的值。 M 步上找到的参数估计值被用于下一个 E 步计算中，这个过程不断交替进行。 总体来说，EM的算法流程如下： 1.初始化分布参数 2.重复直到收敛： E步骤：估计未知参数的期望值，给出当前的参数估计。 M步骤：重新估计分布参数，以使得数据的似然性最大，给出未知变量的期望估计。 规则AC： 连接操作: A B C X 和 A B C Y可连接，生成 A B C X Y (个数相同，只有最后一个元素不同) 生成频繁k-项集Lk的算法： 根据k-1项集Lk-1，连接生成候选集Ck 筛选出
24、Ck中支持度大于min_sup的元素，构成Lk 例子： 6. * PageRank将 网页x指向网页y的链接视为x给y的一张投票。 * 然而PageRank 不仅仅考虑网页得票的绝对数目，它还分析投票者本身的权威性. - 来自权威网页的投票能够提升被投票网页的权威性 * 链接是源网页对目标网页权威性的隐含表达. - 网页i入边越多，表示i的权威性值越高。 * 指向网页i的网页本身也有自己的权威性值 - 对于网页i的权威性得分而言，一个具有高分值的源网页比一个低分值的源网页更加重要。 - 换言之，若其它权威性网页指向网页i，则i也可能是权威性网页。 优点： (1) 防欺骗 网页所有者难以设置其它
25、重要网页指向自己的网页. (2) ageRank 值独立于查询，是一种全局度量. PageRank 值是通过所有网页计算得到并加以存储，而不是提交查询时才计算. 缺点： 不能区分全局重要性网页和查询主题重要性网页 把Web视为有向图 G = (V, E)，V表示顶点，一条边(i, j) E当且仅当网页i指向网页j，n为总的网页数。 网页P(i)定义为: Aij 表示用户在状态i转移到状态j的概率。 k步转移后的概率分布： 对于任意初始概率向量P0, Pk 将收敛于一个稳定的概率向量p, 即, p 可作为PageRank 值向量，其合理性： - 它反映了随机冲浪的长期概率. - 一个网页被访问的
26、概率越高，其权威性越高. 一个有限马尔可夫链收敛于一个唯一的稳态概率分布：如果矩阵A是不可约和非周期的。 条件1：随机矩阵 A不是一个随机矩阵，因为很多网页没有出边，导致A中某些行全为0. 解决方案1：删除没有出边的网页. 解决方案2：将没有出边的网页指向网络中所有其它网页 条件2：不可约 不可约意味着强连通(所有点对都有双向路径)，A不符合。 条件3：非周期 从i到i的所有路径都是K的倍数(k1)，则成为周期的。 一个马尔科夫链所有状态都是非周期的，则为非周期。 解决方案：指定一个参数d，将每一个网页都以概率d指向其它所有网页。此方法顺便解决了不可约问题，处理后： 其中E = eeT(E=o
27、nes(n)，令 eTP = n: Oj 是网页j的出边数 A 是Web图的邻接矩阵表示： 通过使用幂法可以求解P=AP，但是Web图不符合求解条件。 T因此，每个网页 7. 9. When p(w1)=p(w2),the decision is based entirely on the likelihood p(x|wj) - p(x|w)p(x|w) Probability of error for multi-class problems: Error = Bayes Error + Added Error: 8. Conditional risk (expected loss of
28、taking action ai): Overall risk (expected loss): zero-one loss function is used to minimize the error rate 别，则CART可能考虑将目标类别合并成两个超类别； l 如果目标变量是连续的，则CART算法找出一组基于树的回归方程来预测目标变量。 1、从根节点t=1开始，从所有可能候选S集合中搜索使不纯性降低最大的划分S*，然后，使用划分S*将节点1划分成两个节点t=2和t=3； 2、在t=2和t=3上分别重复划分搜索过程。 Multivariate Normal Density in d dimensions: 例子： Calculate impurity: Build tree: 10. 分类回归树是二叉树，且每个非叶子节点都有两个孩子，所以对于第一棵子树其叶子节点数比非叶子节点数多1 11. 把学习结构看作一个网络，则深度学习的核心思路如下： 无监督学习用于每一层网络的pre-train； l CART中用于选择变量的不纯性度量是Gini指数； l 如果目标变量是标称的，并且是具有两个以上的类每次用无监督学习只训练一层，将其训练结果作为其高一层的输入； 用自顶而下的监督算法去调整所有层 深度不足会出现问题。 人脑具有一个深度结构。 认知过程逐层进行，逐步抽象。
