人工智能复习.docx
- 文档编号:17884045
- 上传时间:2023-08-04
- 格式:DOCX
- 页数:11
- 大小:349.29KB
人工智能复习.docx
《人工智能复习.docx》由会员分享,可在线阅读,更多相关《人工智能复习.docx(11页珍藏版)》请在冰点文库上搜索。
人工智能复习
人工智能复习
1.状态空间搜索
问题P=(I,G,O),其中I:
初态集G:
目标态集O:
算法集
解题步骤:
问题表示->搜索->结论
例如:
四皇后问题:
在4×4的国际象棋棋盘上放置4个皇后,要求4个皇后在横、竖和斜线上都相互不能攻击.
解:
(1)问题表示:
P=(I,G,O)
I:
G:
I上有四个皇后,相互不攻击,皇后(*)
O:
一行放一个皇后,使得与已有皇后互相不攻击
(2)搜索:
(3)答案:
有一个对称同构解
2.博弈问题证明
解题步骤:
问题表示->搜索->标准->结论
3.博弈树的搜索
1.盲目搜索:
搜索效率太低,解决实际问题一般不予考虑。
2.启发式搜索:
极大极小搜索法和α-β剪枝技术
极大极小搜索法:
极大极小搜索过程将搜索树的产生和位置评估完全分开,只有生成规定深度的博弈搜索树后,才利用估价函数对位置进行评估,算法的效率比较低。
α-β剪枝技术:
如果在生成博弈搜索树的过程中就对位置评估(到达了规定的深度,但博弈搜索树还没有完全生成),从而剪去一些没用的分枝,提高算法效率,这种技术称为α-β剪枝过程。
在搜索过程中,首先使搜索树的某一部分达到最大深度,计算出或节点的估价函数值(称为α值)或者是与节点的估计值(估价函数值称为β值)。
对任意一个节点,当其某一个后继节点的最终值给定时,就可以确定该节点的上界(对与节点而言)或者下界(对或节点而言)。
随着搜索的深入,按照或节点的α值永不下降,与节点的β值永不上升的规则。
不断修改个别节点的α值或β值。
搜索过程中α-β剪枝的规则如下,剪枝过程如图1所示:
(1)任何或节点n的α值大于或等于它先辈节点的β值,则n以下的分枝可停止搜索,并令节点n的倒推值为α。
这种剪枝称为β剪枝。
(2)任何与节点n的β值小于或等于它先辈节点的α值,则n以下的分枝可停止搜索,并令节点n的倒推值为β。
这种剪枝称为α剪枝。
例如:
4.归结原理
1.基本归结
2.强归结
3.合式公式(wff)化成子句集
(1)去掉->(A->B<=>┐A∨B)
(2)将┐作用到原子
原子:
如果P是n元谓词,t1,t2,...,tn是项,则P(t1,t2,...,tn)是一个原子。
┐(A∧B)<=>┐A∨B
┐(A∨B)<=>┐A∧B
┐((
x)p(x))<=>(
x)(┐p(x))
┐((
x)p(x))<=>(
x)(┐p(x))
(3)标准化变量:
换名,使每个量词的变量都不同。
(4)化成前束范式
(5)去掉存在量词skolern化
例如:
把(
x)(
y)(P(x,y)∨(Q(x,y)→R(x,y)))化为子句集
解:
对谓词公式(
x)(
y)(P(x,y)∨(Q(x,y)→R(x,y))),先消去连接词“→”得:
(
x)(
y)(P(x,y)∨(¬Q(x,y)∨R(x,y)))
此公式已为前束范式。
再消去存在量词,即用Skolem函数f(x)替换y得:
(
x)(P(x,f(x))∨¬Q(x,f(x))∨R(x,f(x)))
此公式已为Skolem标准型。
最后消去全称量词得子句集:
S={P(x,f(x))∨¬Q(x,f(x))∨R(x,f(x))}
(6)将前束范式的形式化为合取范式。
(7)去掉全称量词
(8)去掉∧,得到子句集。
(9)换名,一个变量只出现在一个子句中。
4.归结反演
5.知识表示
6.机器学习
1.机器学习是研究agent(s)
(a)增加知识
(b)提高性能
(c)学习学习
的一般原理和计算模型的学科。
2.机器学习的分类
按映射类型分类,机器学习可分为
归纳;演绎;类比;转导
按反馈类型分类,机器学习可分为
有监督学习;无监督学习;再励学习;半监督学习
3.极大似然假设与极大后验估计
1.贝叶斯法则
机器学习的任务:
在给定训练数据D时,确定假设空间H中的最佳假设。
最佳假设:
一种方法是把它定义为在给定数据D以及H中不同假设的先验概率的有关知识下的最可能假设。
贝叶斯理论提供了一种计算假设概率的方法,基于假设的先验概率、给定假设下观察到不同数据的概率以及观察到的数据本身。
2.先验概率和后验概率
用P(h)表示在没有训练数据前假设h拥有的初始概率。
P(h)被称为h的先验概率。
先验概率反映了关于h是一正确假设的机会的背景知识如果没有这一先验知识,可以简单地将每一候选假设赋予相同的先验概率。
类似地,P(D)表示训练数据D的先验概率,P(D|h)表示假设h成立时D的概率。
机器学习中,我们关心的是P(h|D),即给定D时h的成立的概率,称为h的后验概率。
3.贝叶斯公式
贝叶斯公式提供了从先验概率P(h)、P(D)和P(D|h)计算后验概率P(h|D)的方法
p(h|D)=P(D|h)*P(h)/P(D)
P(h|D)随着P(h)和P(D|h)的增长而增长,随着P(D)的增长而减少,即如果D独立于h时被观察到的可能性越大,那么D对h的支持度越小。
4.极大后验假设(MAP)
学习器在候选假设集合H中寻找给定数据D时可能性最大的假设h,h被称为极大后验假设(MAP),确定MAP的方法是用贝叶斯公式计算每个候选假设的后验概率,更精确地说当下式成立时,称 h MAP 为—MAP假设:
h_map=argmaxP(h|D)=argmax(P(D|h)*P(h))/P(D)=argmaxP(D|h)*p(h)(h属于集合H)
最后一步,去掉了P(D),因为它是不依赖于h的常量。
5.极大似然假设(ML)
在某些情况下,可假定H中每个假设有相同的先验概率,这样式子可以进一步简化,只需考虑P(D|h)来寻找极大可能假设。
h_ml=argmaxp(D|h)h属于集合H
P(D|h)常被称为给定h时数据D的似然度,而使P(D|h)最大的假设被称为极大似然假设(maximumlikelihood,ML)假设 h ML 。
例如:
1.
因而,当观察的训练值是真实的目标值加上均值为零的正态分布的随机噪声情况下,最小二乘法就是最大似然。
2.
解:
最小描述长度核心是代码长度函数和机率分布之间的一对一且映成(牵涉到的引理为克拉夫特不等式)。
对于任意机率分布,去建造一代码,其长度为等于是可行的;这代码最小化预期的码长。
反过来说,给予一个编码,则可以建造一个机率分布,保持同样的结果。
7.Agents
1.agent的界定:
agent为达到目的,能够做出独立的或自主的行动的实体
Agent是具有BDI的对象。
Belief信息
Deisre愿望
Intertion意图
2.基本属性:
自主性,社会性,反应性,能动性。
3.一收益矩阵如下所示。
则
(1)不存在优势策略。
对个人而言,d是优势策略,但(d,d)不是问题的优势策略。
(2)存在唯一的Nash平衡点(d,d)。
(3)除(d,d)之外都是佩瑞多(Pareto)最优的。
(4)(c,c)可使社会福利最大
(5)不是零和的博弈,但决策过程类似于零和博弈。
纳什均衡,又称为非合作博弈均衡,是博弈论的一个重要术语,以约翰·纳什命名。
在一个博弈过程中,无论对方的策略选择如何,当事人一方都会选择某个确定的策略,则该策略被称作支配性策略。
如果两个博弈的当事人的策略组合分别构成各自的支配性策略,那么这个组合就被定义为纳什均衡。
一个策略组合被称为纳什均衡,当每个博弈者的均衡策略都是为了达到自己期望收益的最大值,与此同时,其他所有博弈者也遵循这样的策略。
纳什均衡例子
博弈论中一个著名的例子就是囚徒困境。
囚徒困境是一个非零和博弈,说的是两个嫌疑犯甲和乙私入民宅联手作案,被警方逮住但未获证据。
警方于是将两个嫌疑犯分开审讯。
警官分别告诉两个囚犯,如果你招供,而对方不招供,则你将被判刑3个月,对方将被判刑10年;若两人都不招供则因未获证据但私入民宅将各拘留1年;如果两人均招供,每人将被判刑5年。
于是,两个人同时陷入招供还是不招供的两难处境。
结果是,尽管甲不知乙是否招供,但他认为自己选择“招供”最好,因而甲会选择“招供”,同样乙也会选择“招供”,两人各判5年。
而两人都选择不招供,虽证据不足但因私入民宅将各拘留1年的结果是不会出现的。
博弈矩阵
囚犯甲
招供
不招供
囚犯乙
招供
判刑五年
甲判刑十年;乙判刑三个月
不招供
甲判刑三个月;乙判刑十年
判刑一年
在一个博弈过程中,无论对方的策略选择如何,当事人一方都会选择某个确定的策略,则该策略被称作支配性策略。
如果两个博弈的当事人的策略组合分别构成各自的支配性策略,那么这个组合就被定义为纳什均衡。
纳什均衡又称为非合作博弈均衡。
在上述囚徒困境例子中,两个囚犯符合自己利益的选择是坦白招供。
这种两人都选择坦白的策略以及因此被判刑五年的结局就是“纳什均衡”。
非零和博弈中,帕累托最优和纳什均衡是相冲突的。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 人工智能 复习