当前位置:文档之家› 华南理工大学《人工智能》复习资料

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

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

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

Ch 2.

【状态空间表示】

S F G

<>

,,

S:初始状态的集合

F:操作的集合

G:目标状态的集合

例如:507

{}{}{}

Q a b c Q Q

<>

,,,,,

【状态空间图】

【状态空间图搜索使用的数据结构】

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,A∪B等都是谓词公式

辖域:紧接于量词之后被量词作用的谓词公式

指导变量:量词后的变量

约束变量:量词辖域中,与该量词的指导变元相同的变量自由变量:除了约束变量之外的变量

一阶谓词:仅个体变元被量化的谓词

二阶谓词:个体变元、函数符号、谓词符号被量化

从谓词公式得到命题:

(1)把谓词中的个体变元代入个体常元

(2)把谓词中的个体变元全部量化

如P(x)表示"x是素数", 则?x P(x),P(a)都是命题

合取范式:B1 ∧ B2 ∧…∧B n,如

(()())(()())(()())

P x Q x Q y R y P z S z

∨∧?∨∧?∨8

析取范式:B1 ∨B2 ∨…∨B n,如

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

(()())(

D y L a y P x C z P u L u v

?∧∨?∧∨?∧?

,(()())())(,))

谓词公式永真性: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 、…、F n的逻辑结论,当且仅当对每个解释I,如果F1、F2 、…、F n都为真,则G也为真。F1、F2 、…、F n为G的前提。

互补文字:L与?L

归结式:C1包含L1,C2包含L2,L1与L2互补。把L1和L2删除,并把剩余部分析取,得到C12

亲本子句:上例中C1与C2

消解基:上例中L1与L2

例如:

【归结原理定理】

1.谓词公式A不可满足当且仅当其子句集S不可满足。

2.G是公式F1、F2、…、F n的逻辑结论,当且仅当

F1 ∧F2 ∧…∧F n => G

3.G是公式F1、F2、…、F n的逻辑结论,当且仅当

F1 ∧F2 ∧…∧F n ∧ ? G不可满足

4.归结式是其亲本子句的逻辑结果

5.子句集S的C1,C2替换为C12得到S1,则

S1不满足=>S不满足

6.子句集S添加C12得到S2,则

S2不满足=>S不满足

【归结反演法】

否定目标公式G,? G加入到F1 ∧F2 ∧…∧F n中,得到子句集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:置k=0,Fk=F,σk =ε;

Step2:若Fk只含有一个谓词公式,则算法停止,σk就是最一般合一;

Step3:求Fk的差异集Dk;

Step4:若Dk中存在元素xk和tk ,其中xk是变元,tk 是项且xk不在tk中出现,则置Sk +1=Fk{tk/ xk} ,σk+1= σk ?{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,σ0=ε,D0={a,z}

R

S

P

C∨

?

=

12

σ1=σ0·{a/z}= {a/z}

F1= F0{a/z}= {Q(a,x,f(g(y))),Q(a,h(a,u),f(u))}

k=1;

D1={x, h(a,u)}

σ2= σ1·{h(a,u) /x}={a/z,h(a,u) /x}

F2= F1{a/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}

σ3={a/z ,h(a, g(y)) /x ,g(y)/u}

F3= F2{g(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:前提化为子句集S

Step2:确定目标谓词,化为子句,并析取助谓词新子句,并入到S形成S’。Step3:对S’应用归结原理。

Step4:当只剩辅助谓词时,归结结束。

(例子见CH3 P105 )

【归结策略】

Step1:子句集S置入CLAUSES表

Step2:若Nil在CLAUSES,归结成功

Step3:若CLAUSES存在可归结子句对,则归结,并将归结式并入CLAUSES表,step2

Step4:归结失败

【广度优先搜索归结策略】

用于确定归结策略step3的搜索次序

第一轮:0层(原子句集S)两两进行归结,产生1层

下一轮:1层与0、1层两两进行归结,得到2层

再一轮:2层与0、1、2层两两进行归结,得到3层

如此类推,直至出现Nil

【归结策略完备性】

一个归结策略是完备的,如果对于不可满足的子句集,使用该策略进行归结,最终必导出空子句Nil。

(广度优先是完备的,亦称水平浸透法)

【归结策略出发点】

(1)简化性策略。

(2)限制性策略。

(3)有序性策略(包含排序策略)

【归结策略类型】

删除策略

支持集策略

线性归结策略

单元归结策略

语义归结策略

祖先过滤型策略

【正向演绎推理--初始事实F0】

●任意谓词公式

●前束范式表示;消去量词,改名

●与或图表示:析取部分用与节点表示

合取部分用或节点表示

【正向演绎推理--F-规则】

●形如L=>W,L为单一文字

●W为任意与或型谓词公式;(消去量词,改名)

【正向演绎推理—目标谓词】

● 文字的析取式(消去量词,改名)

【正向演绎推理图解】

012':()(()())':()()':()()':()()

F P x Q x R x F P y S y F Q z N z

G S a N 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 )

F 0

F 1 {x/z }

F 2 {x/y }

{a/x }

{a/x }

N (a )

? S (a )

【代换集一致性】

设有代换集{u 1,u 2,…,u n },其中每个u i 都是代换{t i1/ v i1, t i2/ v i2,…, t im (i)/ v im (i)}

U1={v 11, …, v im(1),…, v n1, …, v nm(n)}(所有下边的变量) U2={t 11, …, t im(1),…, t n1, …, t nm(n)} (所有上边的项) {u 1,u 2,…,u n }是一致的,当且仅当U1和U2是可合一 合一复合:U1和U2的最一般合一

解树上所有代换是一致的,则该问题有解,最后的代换是合一复合U

【反向演绎推理--目标公式】

任意谓词公式(消去量词,改名) 与或图表示:与节点对应合取;

或节点对应析取

【反向演绎推理--B -规则】

● W=>L ;

● L 为单一文字;

● W 为任意与或型谓词公式(消去量词,改名)

【反向演绎推理—图解】

()

MEOWS MYERTLE {x /x 5}

{MYRTLE /x }

{FIDO /y }

{y /x 1}

{FIDO /y }

R 1

{FIDO /y }

{x /y 2,y /x 2}

()()(,)

CAT x DOG y AFRAID x y ∧∧?()CAT x ()DOG y (,)

AFRAID x y ?22(,)

AFRAID y x ?5()

CAT x ()

MEOWS x ()

BARKS y ?()

FRIENDLY y 1()

FRIENDLY x ()WAGS TAIL y -()

DOG y R 2

R 5

()

BARKS FIDO ?()WAGS TAIL FEDO -()

DOG FIDO ()

DOG FIDO {FIDO /y }

【正向/反向演绎对比】

【双向演绎推理】

● 分别从基于事实的F-规则正向推理出发,也从基于目

标的B-规则逆向推理出发,同时进行双向演绎推理。 ● 终止的条件:正向推理和逆向推理互相完全匹配。即

所有得到的正向推理与或树的叶节点,正好与逆向推理得到的与或图的叶节点一一对应匹配

【不确定性知识分类】

随机不确定性(概率) 模糊不确定性(软概念) 不完全性(事物了解不充分) 不一致性(时间推移)

【逆概率方法公式】

1

(|)()

(|)(|)()

i i i n

j

j j P E H P H P H E P E H

P H ==

【逆概率—多个证据】

12121

21

(/)(/)(/)()

(/)

(/)(/)(/)()

i i m i i i m n

j

j m j j j P E H P E H P E H P H P H E E E P E H

P E H P E H P H =∑L L L

其实就是bayes 公式。严格要求各证据独立。

【修正因子】

方括号内为修正因子:

)

(])()

|([

)|(H P E P H E P E H P =

【可信度法—不确定性度量】

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),(H P H P H P E H P H P E H MB

MD (Measure Disbelief ):

不信任增长度,因E 的出现使H 为真的不信任增长度:

???

??--=否则)()

()}(),|(min{0=)(当1),(H P H P H P E H P H P E H MD

因此,CF(H,E)为:

??

??

?

????<-->--=)

()|(当)()|()()(=)|(当0

)()|(当)(1)

()|(),(H P E H P H P E H P H P H P E H P H P E H P H P H P E H P E H CF

【可信度法--不确定性传播】

组合证据:

E=E 1∧ E 2 ∧… ∧ E n :

CF(E)=min{CF(E 1) ,CF(E 2) , … CF(E n )}

E=E 1 ∨ E 2 ∨ … ∨ E n :

CF(E)=max{CF(E 1) ,CF(E 2) , … CF(E n )}

E=? E 1 :

CF(E)=-CF(E 1)

推理结论的CF 值:

CF(H) = CF(H,E) ? max { 0, CF(E) }

重复结论的CF 值:

【主观贝叶斯法】

表示形式:

if E then (LS, LN ) H ( P(H) )

))(()

,(H P H E LN LS ????→?

【LS 和LN 】

LS :充分性量度,E 对H 支持程度,范围为[ 0, ∞ ):

LN :必要性量度,? E 对H 支持程度,范围为[ 0, ∞ ):

LS 、LN>0,不独立,有如下约束关系:

当LS>1时,LN<1; 当LS<1时,LN>1; 当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 为真是充分的

● 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 公式:

【贝叶斯网络图示】

● 以随机变量为节点,以条件概率为节点间关系强度的

有向无环图(Directed Acyclic Graph ,DAG )

● 每个节点旁的条件概率表(简称CPT)中的值对应一个

条件事件的概率

【条件独立关系】

贝叶斯网络中节点相互独立: (1)给定父节点,一个节点与它的非后代节点是条件独立的 (2)给定一个节点的父节点、子节点以及子节点的父节点(Markov blanket),这个节点对于其它节点都是条件独立的

【条件独立关系的判定】

d-分离(d-separation):

给定y ,x 和z 条件独立:(|,)(|)P z x y P z y =

给定y ,x 和z 条件独立:(|,)(|)P z x y P z y =

给定y ,x 和z 不条件独立:(,)()()P x z P x P z =

【贝叶斯网络推理】

概率推理可分为:

因果推理、诊断推理、辩解推理、混合推理

【因果推理】

由原因到结果的推理,自上而下的推理,例如已知L 成立时,求P(M|L) (|)(,|)(,|)P M L P M B L P M B L =+?

【诊断推理】

由结果到原因的推理,自下而上的推理。例如已知?M 成立,求P(?L |?M )

(|)()

(|)()P M L P L P L M P M ?????=

?

【辩解推理】

仅仅给定?B ,求P(?L)。这种情况下,可以说?B 解释?M ,使?L 不确定。

(,|)()

(|,)(,)P M B L P L P L B M P M B ???????=

??

Ch 5.

【FIND-S 算法】

候选假设: “?”:可接受任何值 “φ”:不接受任何值 算法流程:

1.将h 初始化为H 中最特殊假设

2.对每个正例x (循环) 对h 的每个属性约束a i 如果x 满足a i

那么不做任何处理 否则

将h 中a i 替换为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)复制

从旧种群选择生命力强的个体进行复制。

实现方法:根据个体适应度/总适应度,为每个个体分配概率范围(0~1),产生随机数,选择匹配的个体:

(2)交叉

在匹配池中任选两个染色体,随机选择一点或多点交换点位置;交换双亲染色体交换点右边的部分,即可得到两个新的染色体数字串

(3)变异

在染色体以二进制编码的系统中,它随机地将染色体的某一个基因由1变为0,或由0变为1。

【遗传算法的特点】

(1)对参数的编码进行操作,而非参数本身

(因此可模仿自然界进化机制)

(2)同时使用多个搜索点的搜索信息

(搜索效率高、并行、不陷入局部最优)

(3)直接以目标函数作为搜索信息

(不需导数和其他辅助信息)

(4)使用概率搜索技术

(复制交叉变异基于概率,有很好灵活性)

(5)在解空间进行高效启发式搜索

(而非盲目搜索、完全随机搜索)

(6)对待寻优的函数基本无限制

(不要求连续、可微)

(7)具有并行计算的特点

(适合大规模复杂问题的优化)

【遗传算法的构成要素】

(1)染色体编码方法

使用固定长度的二进制符号来表示群体中的个体(2)个体适应度评价

目标函数值J到个体适应度f之间的转换规则

(3)遗传算子

①选择运算:使用比例选择算子;

②交叉运算:使用单点交叉算子;

③变异运算:使用基本位变异算子或均匀变异算子

(4)基本遗传算法的运行参数

下述4个运行参数需要提前设定:

①M:群体大小,即群体中所含个体的数量,一般取

为20~100;

②G:遗传算法的终止进化代数,一般取为100~500;

③Pc:交叉概率,一般取为0.4~0.99;

④ Pm:变异概率,一般取为0.0001~0.1。

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

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

十大算法

1.【C4.5】

【信息增益的计算】

期望信息:

设样本集合s含有si 个类为Ci 的元组, i = {1, …, m},则对

一个给定的样本分类所需的期望信息是:

熵:

具有值{a1,a2,…,a v}的属性A的熵E(A)为属性A导致的s

的划分的期望信息的加权平均和:

信息增益:

例子:

【信息增益比】

【C4.5算法】

1.创建根节点

2.若所有样本为类x,标记为类x

3.若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 problem

Target: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 (a i is Lagrange

multiplier):

Solution(Each non-zero a i indicates that corresponding

x i 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 i‘ * x j 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】

【支持度与置信度】

规则A→C:

【用Apriori算法挖掘强关联规则】

连接操作: {A B C …X} 和{A B C …Y}可连接,生成

{A B C … X Y}

(个数相同,只有最后一个元素不同)

生成频繁k-项集L k的算法:

·根据k-1项集L k-1,连接生成候选集C k

·筛选出C k中支持度大于min_sup的元素,构成L k

例子:

从频繁项集产生关联规则

根据频繁项集I,生成全部非空子集。

对于每个子集m, 若sup(m→( I-m )) ≥ min_sup,输出此规其中sup(m→( I-m )) = 错误!未找到引用源。= 错误!未找到引用源。

5.【EM】

在概率模型中寻找参数最大似然估计或者最大后验估计的算法,其中概率模型依赖于无法观测的隐藏变量。

最大期望算法经过两个步骤交替进行计算:

●第一步是计算期望(E),利用对隐藏变量的现有估

计值,计算其最大似然估计值;

●第二步是最大化(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图的邻接矩阵表示:

通过使用幂法可以求解P

A

P T

=,但是Web图不符合求解条件。

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

【转移概率矩阵】

Aij 表示用户在状态i(网页i)转移到状态j(网页j)

的概率。(公式和web图一致)

k步转移后的概率分布:

【稳态概率分布】

对于任意初始概率向量P0, P k将收敛于一个稳定的概

率向量π, 即,

π可作为PageRank 值向量,其合理性:

- 它反映了随机冲浪的长期概率.

- 一个网页被访问的概率越高,其权威性越高.

【收敛性】

一个有限马尔可夫链收敛于一个唯一的稳态概率分布:

如果矩阵A是不可约(irreducible)和非周期的

(aperiodic)。

条件1:随机矩阵

A不是一个随机矩阵,因为很多网页没有出边,导致A

中某些行全为0.

解决方案1:删除没有出边的网页.

解决方案2:将没有出边的网页指向网络中所有其它网

条件2:不可约

不可约意味着强连通(所有点对都有双向路径),A不符

合。

条件3:非周期

从i到i的所有路径都是K的倍数(k>1),则成为周期的。

一个马尔科夫链所有状态都是非周期的,则为非周期。

解决方案:指定一个参数d,将每一个网页(状态)都

以概率d指向其它所有网页。此方法顺便解决了不可约

问题,处理后(原始文献阻尼因子d=0.85):

其中E = ee T(E=ones(n)),令e T P= 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

likelihood p(x|w j) --> 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 Risk 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 impurity:

Build tree:

11.【Deep learning】

【核心思想】

把学习结构看作一个网络,则深度学习的核心思路如下:

①无监督学习用于每一层网络的pre-train;

②每次用无监督学习只训练一层,将其训练结果作为其高

一层的输入;

③用自顶而下的监督算法去调整所有层

【需要使用深度学习解决的问题的特征】

深度不足会出现问题。

人脑具有一个深度结构。

认知过程逐层进行,逐步抽象。

【BP例子】

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

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

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

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

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

下载文档原格式(Word原格式,共17页)
相关文档
  • 重庆大学人工智能作业

  • 高级人工智能

  • 中国传媒大学软件工程

  • 西电人工智能大作业

  • 清华大学人工智能导论

  • 人工智能期末大作业

相关文档推荐: