华南理工大学人工智能复习资料讲解

1、华南理工大学人工智能复习资料 Ch2. 【状态空间表示】 S：初始状态的集合 F:操作的集合 G:目标状态的集合 例如：二Qab,cQo,Q7 【A*算法】 f(x)=g(x)+h(x) g(x)为当前点的代价 h(x)为距离目标的距离 A*对A算法的改进： 对h(x)作限制，使其总是小于实际最小距离h(x)3，则不必扩展该MIN节点其余子节点 3剪枝： 对MAX节点， 若其倒推下确界a不小于MAX的父节点倒推上确界3,即a3，则不必扩展该MAX节点其余子节点 Ch3. 【离散数学相关定义】 命题(proposition):具有真假意义的语句 谓词(predicate)：刻画个体的性质、状态或

2、个体间的关系， 例如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,AUB等都是谓词公式 辖域：紧接于量词之后被量词作用的谓词公式 指导变量：量词后的变量 约束变量：量词辖域中，与该量词的指导变元相同的变量自由变量：除了约束变

3、量之外的变量 一阶谓词：仅个体变元被量化的谓词 二阶谓词：个体变元、函数符号、谓词符号被量化 从谓词公式得到命题： (1)把谓词中的个体变元代入个体常元 (2)把谓词中的个体变元全部量化 如P(x底示x是素数，则寸xP(x),P(aFB是命题合取范式：BI八B?八八Bn,如 (P(x)Q(x)(-Q(y)R(y)(一P(z)S(z)o 析取范式：B1vB27VBn,如 (-D(y)八L(a,y)v(Fx)八C(z)v(-P(u)八-L(u,v)谓词公式永真性：P对个体域D全部成立，则P在D上永真。P在全总个体集成立，则P永真 谓词公式可满足性：P对个体域D至少有一个个体成立， 则P在D上可满足

4、。 【常用逻辑等价式】(1)交换律：MB=873AfB=B/A 结合律 m (,AAB)AC=3八(八(7)*(3)分配律12=5 玲*7。 双重否定他1。人 等品律上山 Q AtAQi/ 摩根律,= ifj4AE)vrB (7)吸收伴：HR(4 纣 8)oH J4v(J4A) (8) 同一律：ArT 用HNB总。 (9零格AM=Fu Nv=FJ (1Q)却冲律；/vf=FJ (II)矛盾律：MrAo 严 (i2薄含表达式：RSOTME- (13) 加表这出 R刀 05t 国八T#“ (14)输出律；HTfETEoHABTC* (15)砺律：JifSOrBT 必 (等价否定叫 1 武：用HEO

5、-BTTI， (17)归留律：(AT&NAr 软 cYa (13)量词分配律 rVKE 力九次力 oVx&c)八城际功 3x(A。7B(JCD0三政冷次8)* (19)量词转换律：中政工)=*YO -I3L4(IOVr-U(r) (20)量词辖域扩张及收缩律: 早收。八 PoVX(AX)AP) VzXOzFoVr(A)7 力口 3ry/V或&力丫 3rl(x,/)=#34(工,力 4 W/V)fP0池直工).D“三时QtPWVXA)rF)UPfM)=VICPTO)VFT3t 双冷 03r 伊 7刃川 【常用推理定律】 1)附加律：用=村入 2)同化南 MEn 人 Arx

6、B=EQ 用/8=川， (5)析取三段论J飙口国八 MnBy f力假言三段出 UlT/U3TGn 工TC， HTb=(ETGRaT。(X-*JB)A(C-J5)=4AC-*B/tD. f7)等价三段论：(小 iB八 0=C山 O金僦司立规则:十尴 2=蠢Cy是个体域中任一藻定元素).(力存在指定规则：/=用)行是个体尊申某一确定:元素)”门。)全称推广规则,刚WnVM(力(y是个体域中任一限定元素)UD全称乎靛规a藉卬是个体等中某一箫定元素) 【子句集】 文字：原子谓词公式及其否定 子句：任何文字的析取 【子句集特点】 1 .没有蕴含词、等值词 2 .，”作用原子谓词 3 .没有量词(V、3)

7、 4 .合取范式 5 .元素之间变元不同 6 .集合形式 【由谓词公式得到子句集】 (对应子句集特点的序号) 1 .根据蕴含等价式消去蕴含关系 2 .根据量词转换律、双重否定律、摩根定律转换 3 .存在量词：受X/x约束，则定义f(x)替换y(Skolem函数)不受Vx约束，常量代替y(Skolem常量) 全称量词：直接消去 4 .根据分配率合取 5 .各个合取子句变量改名 6 .把合取符号替换为逗号，组成集合 【Skolem标准型】 消去存在量词，把全称量词移到最左，右式为合取，如 xP(x,f(x)?R(x,g(x) Skolem标准型与原公式一般并不等价 【命题逻辑中的归结原理定义】 逻

8、辑结论与前提：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 例如： Ci二1PvQ= C12=-PSR 【归结原理定理】 1. 谓词公式A不可满足当且仅当其子句集S不可满足。 2. G是公式F1、F2、-、Fn的逻辑结论，当且仅当 F1八F2八八Fn=G 3. G是公式F1、F2、-、Fn的逻辑结论，当且仅当F1八F2八八FnA?G不可满足

9、4. 归结式是其亲本子句的逻辑结果 5. 子句集S的C1,C2替换为C12得到S1,则 S1不满足=S不满足 6. 子句集S添加C12得到S2,则 S2不满足=S不满足 【归结反演法】 否定目标公式G,?G加入到F1八F2八八Fn中，得到子句集SoS进行归结，并把D3结结果并入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是不含变元的项(称为基项)空替换：没有元

10、素的替换，记作表达式：项、原子公式、文字、子句的统称基表达式：没有变元的表达式 例/特例：对公式E实施替换。，记为E0,所得结果称为E在0下的例 复合/乘积： 0=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当yiCx1,xn 得到0与入的复合或乘积，记为。？入 例如： 9=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

11、)/z 得到：0入=a/x,f(b)/y,b/u 合一：F1X=F2X=Fn入贝U入为F的合一，F为可合一的(一个公式的合一一般不唯一) 最一般合一： b 为F的一个合一， 如果对F任何合一。 都存在入使得0=(7?入，则(7为5的最一般合一,极为MGU(一个公式集的MGU不唯一) 差异集：S是具有相同谓词名的原子公式集，从各公式左边开始，同时向右比较，直到发现第一个不都相同的项为止，用这些项的差异部分组成的集合 【合一算法】 Stepl:置k=0,Fk=F,k=e; Step2：若Fk只含有一个谓词公式，则算法停止，bk就 是最般合; Step3:求Fk的差异集Dk; Step4：若Dk中存

12、在元素xk和tk,其中xk是变元，tk是项且xk不在tk中出现，则置Sk+1=Fktk/xk,(rk+1=bk?tk/xk,k=k+1然后转Step2; Step5:算法停止，F的最一般合一不存在。 对任一非空有限可合一的公式集，一定存在最一般合一，而且用合一算法一定能找到最一般合一 【合一算法例子】 求公式集F=Q(a,x,f(g(y),Q(z,h(z,u),f(u)的最一般合一解： 解 k=0; F0=F,(T0=,D0=a,z o-1=o-0a/z=a/z F1=F0a/z=Q(a,x,f(g(y),Q(a,h(a,u),f(u) k=1； D1=x,h(a,u) o-2=o-1h(a,

13、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)k=2; D2=g(y),u b3=a/z,h(a,g(y)/x,g(y)/u F3=F2g(y)/u=P(a,h(a,g(y),f(g(y) S3单元素集,b3为MGU。 【谓词逻辑中的归结原理定义】 二元归结式(二元消解式)： (G(T-LI(T)U(C20-L2(T)淇中: 亲本子句：CI,C2为无相同变元的子句 消解文字：LI,L2 (T为L1和？L2的最一般合一 因子：C(7。其中(T为C的子句文字的最一般合一 单因子：C(T为单元句子 【合一定义

14、】【归结式】 子句的Ci,Q归结式，是下列二元归结式之一： (1) G和G的二元归结式； (2) G和G的因子的二元归结式； (3) G因子和G的二元归结式； (4) G的因子和G的因子的二元归结式。 归结注意事项： (1)两个子句不能含有相同的变元 (2)归结的子句内部含有可合一的文字，则需进行简化 【谓词逻辑的消解原理/归结原理】谓词逻辑中的消解(归结)式是它的亲本子句的逻辑结果： CiAQ=(Cl(TLi(T)U(C2(TL2(T) 【谓词逻辑的定理】 如果子句集S是不可满足的， 那么必存在一个由S推出空子句的消解序列。 (3)有序性策略(包含排序策略) 【归结策略类型】 删除策略 支持

15、集策略 线性归结策略 单元归结策略 语义归结策略 祖先过滤型策略 【正向演绎推理-初始事实匕】 任意谓词公式 前束范式表示；消去量词，改名 与或图表示：析取部分用与节点表示 合取部分用或节点表示 【正向演绎推理-F-规则】 形如L=W,L为单一文字 W为任意与或型谓词公式；(消去量词，改名) 【应用归结原理求取问题答案】 Stepi:前提化为子句集S Step2：确定目标谓词，化为子句，并析取助谓词新子句， 并入到S形成S。 Step3:对S应用归结原理。 Step4：当只剩辅助谓词时，归结结束。 (例子见CH3P105) 【归结策略】 Stepi:子句集S置入CLAUSE法 Step2：若N

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

17、绎推理一目标谓词】文字的析取式(消去量词，改名) 【正向演绎推理图解】 F。：一P(x)(Q(x)R(x) FI：P(y)=S(y) F2:Q(z)=N(z) G:一S(a)N(a) 【代换集一致一】 设有代换集U1,U2,一；Un,其中每个Ui都是代换ti1/Vi1,ti2/ vi2,tim(i)/vim(i) U1=V11,m(1),Vn1,nV(n)(所有下边的变量) U2=til,imtl),tn1,r,nt(n)(所有上边的项) U1,U2,Un是一致的，当且仅当U1和U2是可合一 合一复合：U1和U2的最一般合一 解树上所有代换是一致的，则该问题有解，最后的代换是 合一复合U 【反

18、向演绎推理-目标公式】任意谓t公式(消去量词，改名)与或图表示：与节点对应合取； 或节点对应析取 【反向演绎推理-B-规则】 W=L; L为单一文字； W为任意与或型谓词公式(消去量词，改名) 对比项目 F系统系统 B系统系统 使用条件 1、小丈谓词时为任尊形式： 2,规则的膨式L=W; 3、目标谓词公式是文字的折鞋. 1、 界实谓词公式是史字的合取式工 2、堀期的形式1W=L； 3、日标谓词公式是任意形式. 预处理 用函数消去里实利规则谓词公式中的存在情W;略生全称量词.JHSkolem函数消去目标谓词公式中的全称盘词;略去存在量词. JHSK。伯m的政消云目标谓司公式中的全藕量词:嘴去在在

19、址同。fflSkolemiSf消去巾文和规则谓诃公式中的存在谓词;略去全称段词. 初始数据麻 里录谓词公式,川与或树 表示 目标11词公式r用与或树表示 推理过程 事实一 A 目标 即配时注意：变帝代换，以W代替L 目标一 A 事实 网配时注意；变址代换. 以W代怦L 终生条件 得到目标的-轨解M 剁到措丈的致解树 子句 文字的析取 文字的合取 子句集 子句的合取 千句的析取 【正向/反向演绎对比】 【双向演绎推理】 分别从基于事实的F-规则正向推理出发， 也从基于目标白B-规则逆向推理出发，同时进行双向演绎推理。终止的条件：正向推理和逆向推理互相完全匹配。即所有得到的正向推理与或树的叶节点，

20、正好与逆向推理得到的与或图的叶节点一一对应匹配 【不确定性知识分类】 随机不确定性(概率)模糊不确定性例概念)不完全性(事物了解不充分)不一致性(时间推移) 【逆概率方法公式】 PH|E一P(E|HJP(HJP(HiIE)n P(E|Hj)P(Hj) j1 【逆概率一多个证据】 P(Ei/Hi)P(E2/Hi)l|lP(Em/Hi)P(Hi)P(Hi/E1E2WEm)n P(Ei/Hj)P(E2/Hj)|P(Em/Hj)P(Hj)jm 其实就是bayes公式。严格要求各证据独立。 【修正因子】 方括号内为修正因子：P(H1E-)便H) 【可信度法一不确定性度量】 IfEthenH(CF(H,E

21、) 其中CF(H,E为可信度因子/规则强度 CF(H,E)=MB(H,E)-MD(H,E) 【反向演绎推理一图解】 【MBffiMD MB(MeasureBelief): 信任增长度，因证据E的出现使结论H为真的信任增长度: 当P(H)=1通过LN,LS把先验概率转化为后验概率： LS=O(H|E)/O(H) P(H|E)越大，O(H|E)越大，则LS越大，表明E对H为真的支持越强，当LST00,P(H|E)t1,E的存在对H为真是充分的 MBH,E)=maxRH|E),RH)一P(H)否则 1_P(H) 【可信度法-不确定性传播】组合证据： 【P(E|S)与P(H|S)】 CfE|Sj+P

22、向的 E 母) E=E1AE2八AEn: CF(E)=minCF(E),CF(E!),CF(E) E=EVE27VEn： CF(E)=maxCF(E),CF(),CF(E) E二日： CF(E尸-CF(E 推理结论的CF值： CF(H)=CF(H,E)max0,CF(E) 重复结论的CF值： P(E|S) lr-5C(E|S)E)=0,E的不存在导致H为假，说明E对H是必要的 因此，CF(H,E的： P(H|E)_P(H) CRH,E)= 1-P(H) 0 P(H)P(H|E) -P(H) 当P(H| 当RH| 当P(H| E).P(H) E)=P(H) E):二P(H) P(HHEJ= LN

23、xP(H) (LN-1)xP(H)+1 【几率函数】 P(x) 。叱 ，CF1(H)+CF2JH)-CF1(H)KCF2(H) CF- 11=DKCF1(H)0 表木形式: if 【主观贝叶斯法】 Ethen(LS,LNH(P(H) E(LS,LN)H(P(H) 以随机变量为节点，以条件概率为节点间关系强度的 有向无环图(DirectedAcyclicGraph,DAG) 每个节点旁的条件概率表(简称CPT井的值对应一个条件事件的概率 LS充分性量度, 【LS和LN! E对H支持程度，范围为0,8)： LS二P回H) LN:必要性量度，E对H支持程度，范围为0,8)： PSE|H) -pEjn

24、) LSLN0不独立，有如下约束关系: 当LS1时,当LS1时,当LS=1时, LN1; LN=1; 日白ryry Eanhgk E P(E)I 0.002I 0.S981 Alarm John 叩网叩网 +a +j D.9 +a j 01 +i 口.05 T -ii 0.95 A +a +ni 0.7 +a -m 0.3 T +ni D01 T -ilTI 。，狗 AMP(M|A MaiYcal值 +b +9 +a 0.95 +b +e 君 0.05 +b 必 +a 0.94 +b 0.06 ib +e +a 。，蓍 -.b +e 0.71 b +a 0.001 ib O.%9 A 呐&am

25、p;E) P(H|E!= (LS-1)xP(H)+1 +叫”一叫/xp 代若。三 P(E|S) AfAfTK*h h) )ii .2 maximize- = R(wrx. Suchthat 【NonlinearSVM】 Theoriginalfeaturespacecanalwaysbemappedtosomehigher-dimensionalfeaturespacewherethetrainingsetisseparable c_cr_minimize-llwll,. DualProblemfor211(aiisLagrange multiplier): FindfAy,Pfivsucht

26、hat Q(U)=工%-%也凸左;，；牛ismaximizedand (1) 2%坤=0 (2) af0forallat Solution(Eachnon-zeroaiindicatesthatcorrespondingxiisasupportvector.): w浸ib=%工k砧ranyxksuchthatn产口 Classifyingfunction(reliesonaninnerproductbetweenthetestpointxandthesupportvectorsxi.involvedcomputingtheinnerproductsxi*xjbetweenalltraining

27、points): -x)=+b 【Slackvariables】 Target: minimize|w|2+ suchthat 力(wTXj+b)1-forall(x；,%) 0forall/ TheparameterCcanbeviewedasawaytocontroloverfitting. DualProblemofthesoftmarginisthesameforhard. Solution: w=.再 b=】-盘)-wTxkwherek=argmaxak Classifyingfunctionofthesoftmarginisthesame. KernelTrick * Mapdat

28、apointstohigherdimensionalspaceinordertomakethemlinearlyseparable. * Sinceonlydotproductisused,wedonotneedtorepresentthemappingexplicitly. Discriminantfunction:(Noneedtoknowthismappingexplicitly,becauseweonlyusethedotproductoffeaturevectorsinboththetrainingandtest.) 二+S=Z比麻了丽卜6 JEJESVSV Kernelfuncti

29、on:dotproductoftwofeaturevectorsin someexpandedfeaturespce: 【OptimizationProblem】minimize b)l 4.【Apriori】 【支持度与置信度】 on-id Item/bought 10 A,B.C 20 A,C 30 A,D 40 R.E,F 规则A-C: support=support(JjC)=50% confidence=support(-4)kJC)/support(4)=66.6% 【用Apriori算法挖掘强关联规则】 连接操作:ABCX口ABC何连接，生成 ABCX丫 (个数相同，只有最后一个

30、元素不同) 生成频繁k-项集口的算法： 根据k-1项集Lk-1,连接生成候选集a 筛选出Ck中支持度大于min_sup的元素，构成Lk 例子： 5.【EM 在概率模型中寻找参数最大似然估计或者最大后验估计的算法，其中概率模型依赖于无法观测的隐藏变量。 最大期望算法经过两个步骤交替进行计算： 第一步是计算期望(E),利用对隐藏变量的现有估 计值，计算其最大似然估计值； 第二步是最大化(M),最大化在E步上求得的最大似然值来计算参数的值。 M步上找到的参数估计值被用于下一个E步计算中，这 个过程不断交替进行。 总体来说，EM的算法流程如下： 1 .初始化分布参数 2 .重复直到收敛： E步骤:估计

31、未知参数的期望值，给出当前的参数估计。M步骤:重新估计分布参数，以使得数据的似然性最大，给出未知变量的期望估计。 一张投票。 *然而PageRank不仅仅考虑网页得票的绝对数目，它还分析投票者本身的权威性. -来自权威网页的投票能够提升被投票网页的权威 性 【更具基本思想】 *链接是源网页对目标网页权威性的隐含表达. -iin-linksi的权威性值越高。 *指向网页i的网页本身也有自己的权威性值 Linearkernel:K(,x,)=x；x, 5Polynomialkernel:凡(5，X,)=(1+*：X /Gaussian(Radisl-BastsFlmctlon(RBF)kernel

32、 卜X小 W)=exp(J)2(7 /Sigmoid： /C(x.1x.)=tanh(yx；+#J 【NonlinearSVMoptimization Formulation:(LagrangianDualProblem) n妙出 iiiEixiinizc i=ll2r=lJ=l suchthat0a.min_sup输出此规 其中sup(m-(I-m)= 事务时数 事务小数 6.【PageRank 【基本思想】 *PageRank将网页x指向网页y的链接视为x给y的 1stscan HEID帛Gscan leniSLtleniSLtA11V -i的权威性得分而言，一个具有高分值的源 网页比一个

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

34、用哥法可以求解P=ATP,但是Web图不符合求解条件。 【转移概率矩阵】 414上MJ 月2121,&相 A-y,. 4AA Aij表示用户在状态i(网页i)转移到状态j(网页j)的概率。(公式和web图一致) k步转移后的概率分布：匕=即 【稳态概率分布】 对于任意初始概率向量P0,Pk将收敛于一个稳定的概 limM=JT 率向量JI,即， 兀可作为PageRank值向量，其合理性： -它反映了随机冲浪的长期概率. -一个网页被访问的概率越高，其权威性越高 【收敛性】 一个有限马尔可夫链收敛于一个唯一的稳态概率分布： 如果矩阵A是不可约(irreducible)和非周期的(aperi

35、odic)。 条件1：随机矩阵 A不是一个随机矩阵，因为很多网页没有出边，导致A中某些行全为0. 解决方案1:删除没有出边的网页. 解决方案2:将没有出边的网页指向网络中所有其它网 页 条件2:不可约 不可约意味着强连通(所有点对都有双向路径)，A不符合。 条件3:非周期 从i到i的所有路径都是K的倍数(k1),则成为周期的。 一个马尔科夫链所有状态都是非周期的，则为非周期。 解决方案： 指定一个参数d,将每一个网页(状态)都以概率d指向其它所有网页。此方法顺便解决了不可约问题，处理后(原始文献阻尼因子d=0.85): C Pmd)+乩4bp 其中E=eeT(E=ones(n),令eTP=n:

36、 P=(l-d)edATP 1n 产w4X月方产(力 因此，每个网页 【naiveBayes 9 【StrengthandweaknessofAdaBoost Bayesformula 川小即：,心1 thetrainingset On源“hrfinal匚la： p；(吗Added 【Reweighting DfHkrp(-%y加也) BayesError 心。心外曲 pOM)p3i)t/x Nd wrongly 【Lostfunction Conditionalrisk(expectedlossoftakingactionai) RQ M/网)P(巧 Overallrisk(expected

37、loss) /?(a(x)|x)p(x)dx zero-onelossfunctionisusedtominimizetheerrorrate MinimumRiskDecisionRule typically where; Geebaseel3isifi.trJ”ChooseatEft一 匚黑卬 likelihoodprior P(H3)P(S) Ifd 电七 i 坦白外poirerrorachneved Thefundamentalruleistodecide5仪的出M秋劭以) maxlpx)tp(a)2|x)一p(匚|幻 Error=BayesError+AddedError /Itis

38、fast,simpleandeasytoprogram /Itcomeswithasetoftheoreticalproperties /Insteadoftryingtodesignalearningalgorithmthatisaccurateovertheentirespace,wecanfocusonfindingbaselearningalgorithmsthatonlyneedtobebetterthanrandom. WeaknessofAdaBoost /Theactualperformanceofboostingdependsonthedataandthebaselearne

39、r. dBoostingseemstobeespeciallysusceptibletonoise. 孑Whenthenumberofoutlinersisverylarge,theemphasisplacedonthehardexamplescanhurttheperformante. 8.【KNN 7.【Adaboost】 theweightsofinjcorrEctlyclassifiudoxmplesareirKn?,isedsothtthetwseBe.imerisfoaedIofocut后 【Erroranalysiserrorformulti-classproblems Qreq

40、uivalentto /DecideWifp(x|w1)pCw1)修(侬之) /Decideiwzifp(x|tu2)p(wz) Probabilityofperrorx)= iT(x)=喻卬 0 仙 G) Decideifp(x|a)i)p(x|co2) Decide6j2ifp(|pOd侬i) MaximumLikelihood(ML)Rule Whenp(w1)=p(w2),thedecisionisbasedentirelyonthelikelihoodp(x|wj)-p(x|w)0cp(x|w) sMirrcZta】皿口QizMiuiif:tiOflL Pstehorevidence

41、 Increase(decrease)weight(correctly)classifiedexample BayesDecisionRule Decide%ifI蜜)p(3.K) Decide3之ifp(也|x) Thus#ifeachbaseclassifierisslightlybetterthanrandomthat7farsame7。，thenthetrainingerordropsexponentiallyfastinTsincetheaboveboundisatmost(StrertgthsofAdaBoost 【AdaBoostAlgorithm MJhnrr, 1 二拓EV=

42、 MultivariateNormalDensityinddimensions: 【与ID3区别】 CART中用于选择变量的不纯性度量是Gini指数； 如果目标变量是标称的，并且是具有两个以上的类别，则CART可能考虑将目标类别合并成两个超类别(双化)； 如果目标变量是连续的，则CART算法找出一组基于树的回归方程来预测目标变量。 【CART分析步骤】 1、从根节点t=1开始，从所有可能候选S集合中搜索使 不纯性降低最大的划分S*,然后，使用划分S*将节点1 (t=1)划分成两个节点t=2和t=3; 2、在t=2和t=3上分别重复划分搜索过程。 11.【Deeplearning】 【核心思想】

43、 把学习结构看作一个网络，则深度学习的核心思路如下： 无监督学习用于每一层网络的pre-train； 每次用无监督学习只训练一层，将其训练结果作为其高 一层的输入； 用自顶而下的监督算法去调整所有层 【需要使用深度学习解决的问题的特征】 深度不足会出现问题。 人脑具有一个深度结构。 认知过程逐层进行，逐步抽象。【NormalDistribution 【基尼系数】 r=ift Calculateimpurity: Where x=x2，,川川) )T K=51，劭劭,，Md)7 S=f(x-n)(x-t)Tp(x)dx |andI-1aredeterminantandinverseespectN

44、Hy 【MLParameterEstimation Discriminantfunction Thediscriminantfunction 9i(x)=xTWiX+wix+ Where 也=f；的， 吗o-彳/q”十m 鼠硒) gt(x)=一,工一的-内) +i”孤矶) 10.【CAR1 【概念】 分类回归树是二叉树，且每个非叶子节点都有两个孩子， 所以对于第一棵子树其叶子节点数比非叶子节点数多i feature D.18 D.1S Buildtree: IndeNIndeN. . 岫 hw&ehw&e credit da&sda&s 1 1 因。 NONO

45、FairFair NaNa 2 2 NoNo N N0 0 ENTClIlffENTClIlffltlt HoHo 3 3 NaNa FrcrllpFrcrllpntnt 4 4 旭 VtEVtE ftt YtiYti S S NoNo H6 F*lrF*lr HaHa 白 N N。 hlahla FairFair 蛔 7 7 NoNo NeNe EmwllcntEmwllcnt MQ WsWs EmlllcntEmlllcnt VK 9 9 VtSVtS EktelleMEktelleM vesves 1010 N4N4 LutiltmLutiltm vv GiniDJub)=-Gini+-Gini) =0.2857 Gini汕仪口如use)=0.1667 例子: 【BP例子】 Giventhefollowing3-layerneur