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

资源描述

《华南理工大学《人工智能》复习资料汇总.pdf》由会员分享，可在线阅读，更多相关《华南理工大学《人工智能》复习资料汇总.pdf（17页珍藏版）》请在三一文库上搜索。

1、华南理工大学人工智能复习资料 Ch 2. 【状态空间表示】 SFG，， S ：初始状态的集合 F：操作的集合 G：目标状态的集合例如： 507 QabcQQ，，，【状态空间图】【状态空间图搜索使用的数据结构】 OPEN表：已生成但没考察的节点(待考察节点 ) CLOSED 表：考察过的节点及节点间关系(搜索树 ) 【广度 / 深度优先搜索特点】广度优先：完备的 (一定能找到最优解)，搜索效率低， OPEN 表为队列结构深度优先：不能保证找到最优解，OPEN表为堆栈结构有界深度优先搜索：即使能求出解，也不一定是最优可变界深度优先搜索算法：深度可变，每次深度超过阈值

2、的点，都被当作待考察点(在 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 ）【与或图中的概念】本原问题：直接可解的问题。终止节点：本原问题对

3、应的节点端节点：无子节点的节点与节点：子节点为与关系或节点：子节点为或关系【与或图的广度 / 深度搜索】 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

4、被标不可解，失败。 (3)从 OPEN表删除具有不可解先辈的节点。转Step2。【与或图启发式搜索】由下往上更新函数值，函数值 =子节点价值 +子节点与父节点距离。例子见PP3 Ch3.P117-120 【博弈树】与结点：对手 (MIN) 力图干扰 MAX 的选择。因此站在我方（MAX）的立场，由MIN 出棋的结点具有与结点的性质。或结点：我方（ MAX）力图通往取胜。MAX 出棋的结点具有或结点的性质。【剪枝 , 剪枝】剪枝：对 MIN 节点 ,若其倒推上确界不大于 MIN 的父节点倒推下确界,即 ,则不必扩展该MIN 节点其余子节点剪枝：对 MAX 节点

5、,若其倒推下确界不小于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，

6、t2，, ，tn 为项， P（t1，t2，, ，tn）称为原子谓词公式，简称原子或原子公式谓词公式：原子公式是谓词公式。若A、B 是谓词公式，则? A，AB等都是谓词公式辖域：紧接于量词之后被量词作用的谓词公式指导变量：量词后的变量约束变量：量词辖域中，与该量词的指导变元相同的变量自由变量：除了约束变量之外的变量一阶谓词：仅个体变元被量化的谓词二阶谓词：个体变元、函数符号、谓词符号被量化从谓词公式得到命题： (1)把谓词中的个体变元代入个体常元 (2)把谓词中的个体变元全部量化如 P(x)表示 “x 是素数 “, 则x P(x)，P(a)都是命题合取范式

7、： B1 B2 Bn，如 ( ( )( )( )( )( )( )P xQ xQ yR yP zS z 8 析取范式：B1 B2 Bn，如 ( )()(D yL ayP xC zP uL uv，（( )( )( )( ， ) 谓词公式永真性：P对个体域D 全部成立，则 P在 D 上永真。 P在全总个体集成立，则P永真谓词公式可满足性：P对个体域D 至少有一个个体成立，则 P在 D 上可满足。【常用逻辑等价式】【常用推理定律】【子句集】文字：原子谓词公式及其否定子句：任何文字的析取【子句集特点】 1.没有蕴含词、等值词 2. “ ?” 作用原子谓词 3.没有量词 ( 、

8、 ) 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 标准型与原公式一般并不等价【命题逻辑中的归结原

9、理定义】逻辑结论与前提：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 = G 3.G 是公式 F1、F2、、

10、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 不同

11、 ,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, ,

12、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是具有相同谓词名的原子公式集，从各公式左边开始，同时向右比较，

13、直到发现第一个不都相同的项为止，用这些项的差异部分组成的集合【合一算法】 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的最一般合一不存在。对任一非空有限可合一的公式集，一定存在最一般合一，而且用合一算法一定能找到最一般合一【合一算法例子】求

14、公式集FQ(a,x,f(g(y),Q(z,h(z,u),f(u)的最一般合一解：解 k0； F0F，0，D0a,z 1 0 a/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= 1 h(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； D2 g(y),u 3 a/z ,h(a, g(y) /x ,g(y)/u F3= F2g(y)/u= P(a,h(a,g(y),f(g(y) S3单元素集，

15、 3 为 MGU。【谓词逻辑中的归结原理定义】二元归结式（二元消解式）: （C1 L1）（ C2 L2 ）,其中：亲本子句：C1，C2为无相同变元的子句消解文字：L1，L2 为 L1和?L2的最一般合一因子： C 。其中为 C的子句文字的最一般合一单因子：C 为单元句子 RSPC12 【归结式】子句的 C1，C2归结式，是下列二元归结式之一: （1） C1和 C2的二元归结式；（2） C1和 C2的因子的二元归结式；（3） C1因子和 C2的二元归结式；（4） C1的因子和C2的因子的二元归结式。归结注意事项： (1) 两个子句不能含有相同的变元 (2) 归结

16、的子句内部含有可合一的文字，则需进行简化【谓词逻辑的消解原理/ 归结原理】谓词逻辑中的消解（归结）式是它的亲本子句的逻辑结果： C1 C2 （C1 L1）（ C2 L2）【谓词逻辑的定理】如果子句集S是不可满足的，那么必存在一个由S推出空子句的消解序列。【应用归结原理求取问题答案】 Step1：前提化为子句集S Step2：确定目标谓词，化为子句，并析取助谓词新子句，并入到 S形成 S 。 Step3：对 S 应用归结原理。 Step4：当只剩辅助谓词时，归结结束。 (例子见 CH3 P105 ) 【归结策略】 Step1：子句集 S置入 CLAUSES 表 Step2：若

17、 Nil 在 CLAUSES ，归结成功 Step3：若 CLAUSES 存在可归结子句对，则归结，并将归结式并入 CLAUSES 表， step2 Step4：归结失败【广度优先搜索归结策略】用于确定归结策略step3的搜索次序第一轮：0 层（原子句集S）两两进行归结，产生1 层下一轮：1 层与 0、1 层两两进行归结，得到2 层再一轮：2 层与 0、1、2 层两两进行归结，得到3 层如此类推，直至出现Nil 【归结策略完备性】一个归结策略是完备的，如果对于不可满足的子句集，使用该策略进行归结，最终必导出空子句Nil。（广度优先是完备的，亦称水平浸透法）【归结策略

18、出发点】（1）简化性策略。（2）限制性策略。（3）有序性策略（包含排序策略）【归结策略类型】删除策略支持集策略线性归结策略单元归结策略语义归结策略祖先过滤型策略【正向演绎推理 -初始事实 F0】任意谓词公式前束范式表示；消去量词，改名与或图表示：析取部分用与节点表示合取部分用或节点表示【正向演绎推理 -F规则】形如L=W，L 为单一文字 W 为任意与或型谓词公式；(消去量词，改名) 【正向演绎推理目标谓词】文字的析取式(消去量词，改名) 【正向演绎推理图解】 0 1 2 :( )( ( )( ) :( )( ) :( )( ) :( )( ) FP xQ x

19、R x FP yS y FQ zN z GS aN a ? P(x)(Q(x)R(x) Q(x)R(x)? P(x) Q(x)R(x) Q(z) ? P(y) N(x) ? S(x) F0 F1 x/z F2 x/y a/x a/x N(a) ? S(a) 【代换集一致性】设有代换集 u1,u2, ，un，其中每个ui都是代换 ti1/ vi1, ti2/ vi2, ， tim(i)/ v im(i) U1 v11, , vim(1), ， vn1, , vnm(n)（所有下边的变量） U2t11, , tim(1), ， tn1, , tnm(n) （所有上边的项） u1,u2, ， un

20、是一致的，当且仅当U1 和 U2 是可合一合一复合：U1 和 U2 的最一般合一解树上所有代换是一致的，则该问题有解，最后的代换是合一复合 U 【反向演绎推理 - 目标公式】任意谓词公式 (消去量词，改名) 与或图表示：与节点对应合取；或节点对应析取【反向演绎推理 -B规则】 W=L； L为单一文字； W 为任意与或型谓词公式(消去量词，改名) 【反向演绎推理图解】 ()MEOWSMYERTLE x/x5 MYRTLE /xFIDO /yy/x1 FIDO /y R1 FIDO /y x/ y2, y/ x2 ( )( )( , )CAT xDOG yAFRAID x y (

21、)CATx ( )DOGy( ,)AFRAIDx y 22 (,)AFRAIDyx 5 ()CATx ( )MEOWSx()BARKSy()FRIENDLYy 1 ()FRIENDLYx ( )WAGSTAILy()DOGy R2 R5 ()BARKS FIDO ()WAGSTAIL FEDO()DOGFIDO ()DOGFIDO FIDO /y 【正向 / 反向演绎对比】【双向演绎推理】分别从基于事实的F-规则正向推理出发，也从基于目标的 B-规则逆向推理出发，同时进行双向演绎推理。终止的条件：正向推理和逆向推理互相完全匹配。即所有得到的正向推理与或树的叶节点，正好与逆向推理得到

22、的与或图的叶节点一一对应匹配【不确定性知识分类】随机不确定性(概率 ) 模糊不确定性(软概念 ) 不完全性 (事物了解不充分) 不一致性 (时间推移 ) 【逆概率方法公式】 1 (|)() (|) (|) () ii i n jj j P E HP H P HE P E HP H 【逆概率多个证据】 12 12 12 1 (/) (/)(/) () (/) (/) (/)(/) () iimii im n jjmjj j P EH P EHP EHP H P HE EE P EHP EHP EHP H 其实就是bayes公式。严格要求各证据独立。【修正因子】方括号内为修正因子： )(

23、)( )|( )|(HP EP HEP EHP 【可信度法不确定性度量】 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为真的信任增长度：否则 )(1 )()(),|(max 1)(当1 ),( HP HPHPEHP HP EHMB MD（Measure Disbelief）：不信任增长度，因E的出现使H 为真的不信任增长度：否则 )( )()(),|(min 0)(当1 ),( HP

24、HPHPEHP HP EHMD 因此， CF(H,E) 为： )()|(当 )( )|()( )()|(当0 )()|(当 )(1 )()|( ),( HPEHP HP EHPHP HPEHP HPEHP HP HPEHP EHCF 【可信度法 - 不确定性传播】组合证据： 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

25、值：【主观贝叶斯法】表示形式： if E then (LS, LN ) H( P(H) ) )( ),( HPHE LNLS 【LS和 LN 】 LS ：充分性量度，E 对 H 支持程度，范围为 0，）： LN：必要性量度， E 对 H 支持程度，范围为 0，）： LS 、LN0,不独立，有如下约束关系：当 LS1时， LN1；当 LS=1时， LN=1；通过 LN,LS把先验概率转化为后验概率： LS= O(H|E)/ O(H) P(H|E) 越大， O(H|E)越大，则LS越大，表明E对 H 为真的支持越强，当 LS ， P(H|E) 1， E 的存在对H 为真是充

27、条件事件的概率【条件独立关系】贝叶斯网络中节点相互独立： (1)给定父节点，一个节点与它的非后代节点是条件独立的 (2)给定一个节点的父节点、子节点以及子节点的父节点 (Markov blanket) ，这个节点对于其它节点都是条件独立的【条件独立关系的判定】 d-分离（ d-separation)：给定 y， x 和 z 条件独立： (| , )( |)P z x yP z y 给定 y，x 和 z 条件独立： ( | , )( | )P z x yP z y 给定 y，x 和 z 不条件独立： ( , )( ) ( )P x zP x P z 【贝叶斯网络推理】概率推理可分为

28、：因果推理、诊断推理、辩解推理、混合推理【因果推理】由原因到结果的推理，自上而下的推理，例如已知L 成立时，求 P(M|L) (|)(,|)(,|)P MLP M B LP MB L 【诊断推理】由结果到原因的推理,自下而上的推理。例如已知?M 成立，求 P(?L| ?M) (|)() (|) () PML PL PLM PM 【辩解推理】仅仅给定 ?B，求 P(?L) 。这种情况下，可以说?B 解释 ?M，使?L不确定。 (,|)() (|,) (,) PMBL PL PLBM PMB Ch 5. 【FIND-S 算法】候选假设： “?” ：可接受任何值 “ ” ：不接受

29、任何值算法流程： 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) 复制从旧种群选择生命力强的个体进行复制。

30、实现方法：根据个体适应度/ 总适应度，为每个个体分配概率范围 (01)，产生随机数，选择匹配的个体： (2) 交叉在匹配池中任选两个染色体，随机选择一点或多点交换点位置；交换双亲染色体交换点右边的部分，即可得到两个新的染色体数字串 (3) 变异在染色体以二进制编码的系统中，它随机地将染色体的某一个基因由1 变为 0，或由 0 变为 1。【遗传算法的特点】 (1) 对参数的编码进行操作，而非参数本身 (因此可模仿自然界进化机制) (2) 同时使用多个搜索点的搜索信息 (搜索效率高、并行、不陷入局部最优) (3) 直接以目标函数作为搜索信息 (不需导数和其他辅助信息) (4)

31、使用概率搜索技术 (复制交叉变异基于概率，有很好灵活性) (5) 在解空间进行高效启发式搜索 (而非盲目搜索、完全随机搜索) (6) 对待寻优的函数基本无限制 (不要求连续、可微) (7) 具有并行计算的特点 (适合大规模复杂问题的优化) 【遗传算法的构成要素】 (1) 染色体编码方法使用固定长度的二进制符号来表示群体中的个体 (2) 个体适应度评价目标函数值J到个体适应度f 之间的转换规则 (3) 遗传算子选择运算 :使用比例选择算子；交叉运算 :使用单点交叉算子；变异运算 :使用基本位变异算子或均匀变异算子 (4) 基本遗传算法的运行参数下述 4 个运行参数需要提前设定： M：

32、群体大小，即群体中所含个体的数量，一般取为 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，标记

33、为类x 3.若 Attribute 为空，标记为最普遍的类 4.选择信息增益比最大的属性，每个可能值建立子节点，递归解决 2. 【k-means】【聚类目标】聚类内部距离平方之和的最小化：【k-means 算法】定义 : k-means 算法以 k 为输入参数，把n 个对象的集合分为 k 个集，使得结果簇内的相似度高，而簇间的相似度低。簇的相似度是关于簇中对象的均值度量，可以看做簇的质心或重心。算法： 1. 把对象划分成k 个非空子集； 2. 计算当前的每个聚类的质心作为每个聚类的种子点； 3. 把每一个对象分配到与它最近的种子点所在的聚类 4. 返回到第2 步, 当满足某

34、种停止条件时停止。停止条件 : 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

35、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

36、Kernel functions to implicitly map to a new feature space * Kernel must be equivalent to an inner productin some feature space 【Solving of SVM 】 * Solving SVM is a quadratic programming problem Target:maximum margin - = Such that 【Nonlinear SVM 】 The original feature space can always be mapped to so

37、me higher-dimensional feature space where the training set is separable 【Optimization Problem】 Dual Problemfor (aiis 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 th

38、e 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 spa

39、ce 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 productof feature vectors in both the training and test.) Kernel function: d

40、ot 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，

41、生成全部非空子集。对于每个子集m, 若 sup(m ( I-m ) min_sup，输出此规其中 sup(m( I-m ) = = 5. 【EM】在概率模型中寻找参数最大似然估计或者最大后验估计的算法，其中概率模型依赖于无法观测的隐藏变量。最大期望算法经过两个步骤交替进行计算：第一步是计算期望（E），利用对隐藏变量的现有估计值，计算其最大似然估计值；第二步是最大化（M），最大化在E 步上求得的最大似然值来计算参数的值。 M 步上找到的参数估计值被用于下一个E 步计算中，这个过程不断交替进行。总体来说， EM 的算法流程如下： 1.初始化分布参数 2.重复直到收敛： E

42、步骤：估计未知参数的期望值，给出当前的参数估计。 M 步骤：重新估计分布参数，以使得数据的似然性最大，给出未知变量的期望估计。 6. 【PageRank】【基本思想】 * PageRank将网页 x 指向网页y 的链接视为x 给 y 的一张投票。 * 然而 PageRank 不仅仅考虑网页得票的绝对数目，它还分析投票者本身的权威性. - 来自权威网页的投票能够提升被投票网页的权威性【更具基本思想】 * 链接是源网页对目标网页权威性的隐含表达. - 网页 i 入边（ in-links）越多，表示i 的权威性值越高。 * 指向网页i 的网页本身也有自己的权威性值 - 对于网页i 的

43、权威性得分而言，一个具有高分值的源网页比一个低分值的源网页更加重要。 - 换言之，若其它权威性网页指向网页i，则 i 也可能是权威性网页。【PageRank优点与缺点】优点： (1) 防欺骗网页所有者难以设置其它重要网页指向自己的网页. (2) ageRank 值独立于查询，是一种全局度量. PageRank 值是通过所有网页计算得到并加以存储，而不是提交查询时才计算. 缺点：不能区分全局重要性网页和查询主题重要性网页【Web 图】把 Web 视为有向图G = (V, E) ，V 表示顶点（网页），一条边 (i, j) E当且仅当网页i 指向网页j，n 为总的网页数

44、。网页 P(i)定义为 : Oj 是网页 j 的出边数 A 是 Web 图的邻接矩阵表示：通过使用幂法可以求解PAP T ，但是Web 图不符合求解条件。【转移概率矩阵】 Aij 表示用户在状态i（网页 i）转移到状态j（网页 j）的概率。（公式和web 图一致） k 步转移后的概率分布：【稳态概率分布】对于任意初始概率向量P0, Pk将收敛于一个稳定的概率向量, 即, 可作为 PageRank 值向量，其合理性： - 它反映了随机冲浪的长期概率. - 一个网页被访问的概率越高，其权威性越高. 【收敛性】一个有限马尔可夫链收敛于一个唯一的稳态概率分布：如果矩阵A 是不

45、可约（ irreducible ）和非周期的（aperiodic ）。条件 1：随机矩阵 A 不是一个随机矩阵，因为很多网页没有出边，导致A 中某些行全为0. 解决方案1：删除没有出边的网页. 解决方案2：将没有出边的网页指向网络中所有其它网页条件 2：不可约不可约意味着强连通(所有点对都有双向路径)，A 不符合。条件 3：非周期从 i 到 i 的所有路径都是K的倍数 (k1)，则成为周期的。一个马尔科夫链所有状态都是非周期的，则为非周期。解决方案：指定一个参数d，将每一个网页（状态）都以概率 d 指向其它所有网页。此方法顺便解决了不可约问题，处理

46、后（原始文献阻尼因子d=0.85）：其中 E = eeT(E=ones(n)，令 e TP= n: 因此，每个网页 7. 【Adaboost】【Strength and weakness of AdaBoost 】【 AdaBoost Algorithm】【 Reweighting】 8. 【KNN 】 9. 【naive Bayes】【Bayes formula】【Bayes Decision Rule】【Maximum Likelihood (ML) Rule】 When p(w1)=p(w2),the decision is based entirely on the l

47、ikelihood p(x|wj) p(x|w) p(x|w) 【Error analysis】 Probability of error for multi-class problems: Error = Bayes Error + Added Error: 【Lost function】 Conditional risk(expected loss of taking action ai): Overall risk (expected loss): zero-one loss function is used to minimize the error rate 【Minimum Ris

48、k Decision Rule 】【 Normal Distribution 】 Multivariate Normal Density in d dimensions: 【ML Parameter Estimation 】【Discriminant function 】 10. 【CART】【概念】分类回归树是二叉树，且每个非叶子节点都有两个孩子，所以对于第一棵子树其叶子节点数比非叶子节点数多1 【与 ID3 区别】 CART中用于选择变量的不纯性度量是Gini 指数；如果目标变量是标称的，并且是具有两个以上的类别，则 CART可能考虑将目标类别合并成两个超类别（双化）；如果目标变量是连续的，则CART算法找出一组基于树的回归方程来预测目标变量。【CART分析步骤】 1、从根节点t=1 开始，从所有可能候选S 集合中搜索使不纯性降低最大的划分S*，然后，使用划分S*将节点1 （t=1）划分成两个节点t=2 和 t=3； 2、在 t=2 和 t=3 上分别重复划分搜索过程。【基尼系数】例子： Calculate impurit

展开阅读全文