IIT-cs480
2020-11-27 14:54:09 0 举报AI智能生成
登录查看完整内容
IIT CS480 课程 学习笔记 人工智能
作者其他创作
大纲/内容
人工智能导论 （第三版）一种现代的方法 CS480 IIT
chapter13
不确定的典型例子
牙齿疾病问题
Toothache ==>cavity 不成立
不是所有牙痛都能推导 牙齿有洞
cavity ==>toothache
也不成立，不是所有牙齿有洞，必然牙痛
这种情况的三个原因
laziness
永远不可能列举无限多的规则
Theoretical ignorance
有的领域，并没有完整的理论
practical ignorance
并不能完整的实验，都得出结果
random variable
definition
event
所有可能产生这个命题的，的世界的概率的和
probability model
逻辑断言考虑的事严格的排除哪些可能的世界
概率断言考虑的事是各种可能的世界的可能性有多大
所有可能的总概率是1
无条件概率 unconditional probabilities 或者 先验概率 prior probabilities
在没有其他信息的时候，对命题已知的情况
证据 evidence
比如当事件P（total=11）的事情，当已经得到一个骰子是5，在等第二个骰子
条件概率 or 后验概率 conditional probabilities or posterior probabilities
P（doubles | die1=5）
概率密度函数
本质是事件在一个区间内发生的概率
联合概率分布 joint probability distribution
完全联合概率分布
概率公理
厄尔莫哥洛夫公里
P(¬α）=1 - P(α）
P（aUb）=P（a）+P（b）-P（a∩b）
需要保证信念度一致，不然的话，对方是有方案永远获胜的
基于完全联合分布进行推理
边缘化 marginalization
归一化（nomalization）
边缘概率
求某单个变量的概率分布
比如求P(cavity）=0.108+0.012+0.072+0.008=0.2
理解&说明
marginalization
本质是将同一变量的在不同其他变量前提下的概率求和
与给定的条件无关
conditioning
将公式转为条件概率
normalization
概率来源哪儿里
客观主义者
主观主义者
基于知识领域，有时候会有独立性
比如判断，天气和牙疼没关系，就可以近似认为P（A|B）=/P(B)
如果全部独立
如果独立
2的n次方个参数，就变成n个参数（2-1+2-1+2-1...n）
conditional independence
A ⊥B|C
B ⊥ A|C
当给定条件C的时候，AB互相独立，只和C有关
MARGINAL INDEPENDENCE
贝叶斯定理
slides上的 参数部分
chain Rule
常见符号的含义
P(x|y）
已知证据Y前提下，x的概率
xy的联合概率分布
应该有4条
X=T，Y=T 的概率
X=F，Y=T 的概率
X=T，Y=F 的概率
X=F，Y=F 的概率
已知z的前提下，xy的联合分布
？
P(x|y=F)
已知y=F的前提下，x的概率
P(Y)在Z的维度上求和消元
P(X| x∩y）
当已知x且y的情况下，求X的联合分布
朴素贝叶斯
一个已知的确定的原因，就可以是的需要因素之间条件独立
P(E1|C)+P(E2|C)+P(E3|C)....所以总共需要参数2n+1个
而已知C的前提下，所有E之间就独立了
Participation
人工智能的短期和长期风险
长期风险
高级通用性人工智能，最终发展还会不会和人类的行为有因果关系
缺乏价值学习，获得知识比获得价值要容易，目前几乎所有系统的目标/效用部分都是硬编码
网络攻击
因为物联网带来了太多硬件的连接
网络攻击已经可以达到用物质干涉现实世界的地步了
自动化武器
Mis-optimization
牺牲大量的能量达到极小的优化，最终可能带来对人类价值的伤害
大量人员失业的风险
大量自动系统的不透明，最终带来失控
认为人工智能除了像其他工程常规该有的风险防范以外，还需要防范全球灾难性的特殊风险
建议的解决方案
反向强化学习
提高对价值学习的研究
弱监督学习
人类的价值观和行为往往是多变，且不一致的
Formal specification / verification 正式验证
正式指定行为，并验证行为得到满足
提高推理的透明化
针对策略进行评估和计划
比如尽早的预测，某些人工智能方式带来的失业率
Research Priorities forRobust and BenefcialArtifcial Intelligence
一些方向
劳动力市场监测
带来的不平等
低收入工作的消失
自动化会更多的提高分配的幂律
由此带来的性别、种族、阶级问题的会更大
对一些市场（比如金融）的影响
失业等问题
法律与伦理的研究
比如自动驾驶带来的车祸的问题
自动武器
agent在社会中不断运用，如何保证其健壮性
价值和效用之间的问题
子主题
chapter14
贝叶斯推理
完全概率分布的有效表示方式
条件概率表 CPTS
P(xi|parents（Xi））
确定性节点
为什么要有这要的表示
降低计算的所需内存
有效表示的最终样子
贝叶斯网络是一个DAG，有向无环图
推理分类
精确推理
这课程只讲精确推理
变量消元计算
近似推理
这门课不讲，但是感觉很有用要补书
chapter16
决策网络
https://blog.csdn.net/weixin_44340586/article/details/109224994
效用函数
P 理解为 给定可观察e的前提下，做动作a，得到s’的概率
U（s）理解为给定的产生s结果的效用
EU （a|e）表达 当已知e的前提下，做了行动a，得到的所有可能的s的概率*它的效用的求和，相当对所有结果做一次数学期望
MEU 等于要选取EU里最优的行动a，不同的a 可能带来不同的EU
chapter1 人工智能的定义
lecture1
主要是都是课程学业、考试、范围等说明
lecture2
AI 无处不在
电子邮件过滤
图像识别
推荐系统
语音助手
医疗
自动驾驶
游戏
什么是智能
拿着计算器回到15世纪的欧洲，那么它算不算智能？
意识、情绪、幽默感、爱、善良、创造性、学习、知觉这些算不算智能？
can machine think
并不重要，就像AI诊断，我们只关心他诊断的准不准，并不关心它是不是像医生一样思考
问机器是不是能思考，就像问潜水艇是不是能游泳一样没意义
关注解决问题
AI is whatever hasn't been done yet
人工智能定义
Rationally 的定义
各类对应的测试
弱AI和强AI
弱AI
针对单一任务
强AI
通用AI，结合各方面知识
机器学习
给定的任务，通过经验提高表现
Deep learning 属于 machine learning 属于AI
AI的历史
卷积神经网络是什么？CNN？
participation
COMPUTING MACHINERY AND INTELLIGENCE
https://academic.oup.com/mind/article/LIX/236/433/986238
译文：https://cloud.tencent.com/developer/article/1508387
章节摘要
5数字计算机
离散状态机
9个反对意见
syllabus
chapter2 agent的分类
agent
定义
percept
percept sequence
agent function
agent program
通过一个扫地机器人的例子，演示上述定义
什么是rational 的行动
有depends
PEAS
performance
Environment
Actuators
Sensors
合理的度量是从实际在环境中希望得到的结果，而不是根据agent的行为
举例：对扫地机器人的度量应该是 得到多少个清洁的地面，而不是总计清理了多少尘土，不然机器人可能反复吸土，倾倒
不可能全知信息、需要自主从环境中收集信息，不仅仅依赖设计人员的先验知识，而是依据感知的信息来完善先验知识
环境特征区分
完全可观察和部分可观察
国际象棋和扑克牌的例子
单agent和多agent
是否有其他竞争者
确定(Deterministic)和随机的（stochastic）
环境是否受完全取决于当前状态和agent的执行
片段(episodic)或者连续的(sequential)
片段的，主要指的当前的行动，不影响下一个片段
连续的，指当前行动影响后续所有决策
静态 （static）或 动态的（dynamic））
环境是否在agent计算的过程中会变化
离线（discrete）和连续（continuous）
指的环境的变化
已知和未知
指的规则都不清晰
简单的agent类型（现实世界中，这些类型是混合的，几乎不存在单一类型的）
简单反射的agent
有土就扫、前方车辆刹车，我也刹车等
只根据当前情况，不考虑历史
基于模型的agent
应对部分可见的环境，有效的方式是记录现在看不到的历史世界
基于抽象的环境如何元转
基于目的的agent
与简单反射的区别，是它需要考虑未来
基于简单--前方亮刹车灯，我就刹车
基于目的--看到亮刹车灯，考虑运行规则，如何做不撞车
基于效用的agent
chapter3 搜索
problem solving agent
为达到目标，寻找行动序列的过程定义为搜索
搜索算的输入是问题，输出的解
问题的良定义
初始状态
可能的行动
对行动的描述
抽象
如果我们能够把任务抽象解扩展成为更细节的世界中的解，那么这种抽象就是有效的
如果执行解中的每个行动比原始问题中的容易，那么这种抽象是有用的
好的抽象是重要的
如何定义一个问题
状态
行动
转移模型
目标测试
路径消耗
NP完全问题
需要做习题
真实世界的问题
search
tree search
不记录遍历过的节点
不占内存
graph search
记录遍历过的节点
占内存
算法例子
α–βA*B*回溯集丛贝尔曼-福特最佳优先双向Sollin分支限界BFS大英博物馆D*DFS深度限制迪杰斯特拉EdmondsFloyd–Warshall边缘搜索爬山IDA*迭代加深Johnson跳点克鲁斯克尔字典序BFS普里姆 SMA*
不同search
深度优先搜索（DFS）
LIFO
Last in first out
主要降低了空间复杂度
深度优先搜索需要多项式的内存，但是它是不完备的，也不是最优的
是可能出现死循环的
广度优先搜索（BFS）
first in frist out
指数级的内存要求
什么叫做行动代价一致的时候？（对应有信息的启发式函数的搜搜，启发式函数表示可以有额外的信息知道不同节点的行动代价）
行动代价一致的时候，广度优先算法是最优的
uniform -cost search 一致代价搜索
不断选择累计代价最小的路径
广度优先搜索找到答案便会终止
而一致代价搜索，找到答案后，还会检查目标的深度所有节点，看谁的代价最小
只关心总代价，不关心步数，所以是不能有代价是0的步骤，不然会有死循环
IDS 迭代加深的深度优先搜索
主要是解决了完备性的问题
深度受限搜索
depth-limited search
无信息搜索对比
有信息搜索
GBFS 贪婪最佳优先搜索
f(n) = h(n)
因为总是试图扩展距离目标最近的节点
不一定是最优的
A*搜索
f(n)=g(n)+h(n)
评价函数f(n) = h(n)[节点n到目标节点的最小代价的代价估计值] + g(n)[到达n已经确切花费了代价]
可采纳性
可采纳的启发式，指的是预估的比实际的代价要小
比如城市路径问题，用直线距离代替实际距离
一致性
问题求解的性能
完备性
是否能找到解
最优性
是否能确定最优解
时间复杂度
空间复杂度
启发式函数
h1 是错位的数字数
h2 Manhattan distance
忽略阻塞，每个数字到正确的位置所需要的cost和
好的启发式函数 分支因子几乎是1
tree search 和graph search 区别
graph search 是有存储的，搜索过的节点可以不再搜索
admissible 和 Consistent
乐观估计的意义，忽略了必须存在的阻塞，所以乐观估计总是小于真实的
admissible 可接受性，意味着它永远小于真实的情况
Consistent 一致性，意味着服从三角不等式
A* 和UCS 的对比
UCS
A*
dominates（最主要的，具备支配的）
hi(n）>= hj(n) Vn
hi(n)<=hucs(n)
ncs是真实成本，如果超过了就失去可接受性了
chapter5
零和博弈
minmax 算法
对于max而言，a1是最优策略，因为其最小的返回可能是3，是所BCD里最大的
深度优先算法
行棋排序会影响剪裁效率
剪裁
α-β pruning
向上传递是 beta，alpha
向下传递是 alpha，beta
评估函数
cutting off and Horizon effect
截断搜索
因为时效的要求，会是搜索到一定程度，开始返回近似评估函数
地平线效应
截断后的固定搜索深度的问题，在于在优先的深度内，决策会相信一些只能【延缓】不能改变结果的行动，认为可以改变结果
蒙特卡洛树搜索
部分可观察的博弈、随机博弈
作业和考试不做要求
chapter6
约束满足问题
使用了状态结构
是通用策略而非问题专用启发式来解决复杂问题
CSP形式化
绝对约束和偏好约束
约束类型
一元约束
二元约束
全局约束
举例：alldiff
CSP的推理
节点相容
弧相容
AC3算法
路径相容
通过搜索求解
回溯搜索算法
取值排序
取最小的剩余价值（MRV）
Degree heuristic
先取邻居最多的
LCV？
搜索和推理交替进行
forward checking
MAC？
MAC和FC的区别
MAC检查全部约束图
FC只检查和他相关的
局部搜索（不重要）
chapter7
KB-agent
tell
ask
wumpus实例
逻辑定义
模型定义
知识库由语句构成
语法为所有合法语句给出规范
语义定义了每个语句在每个可能世界的真值
举例 : 算数的语义规定了 语句 x+y=4 在x=2 和y=2的世界中为真
蕴含关系
α|=β
举例： x=0 |= xy=0
导出
可靠性和完备性
可以导出蕴含句的 称之为可靠
推理算法可以生成任一蕴含句，就是完备的
命题逻辑 Propostitonal logic
原子语句由单个命题词组成
复合句由简单语句用括号和逻辑连接词构成
常用逻辑连接词
¬
非
∧
与
∨
或
⇒
蕴含
⇔
当且仅当
only if
真值表
蕴含： 如果P为真，那么我主张Q为真，Q为假责明确是伪命题，其他不知道
命题逻辑定理的证明
逻辑等价表
语句的有效性
如果所有模型中，它都是真--重言式 P∨¬P
语句的可满足性
存在一些情况（模型）使得它是真
要证明 α|=β 实际证明等效于 证明（α=>β） 等于 证明 ¬α∨β
反证法： 证明 α|=β ，只需证明 ¬（¬α∨β）为True，等于证明α ∧ ¬β
推导和证明
单调性
归结证明（resolution）
将 A or B or C or ...的多个 or的语句合并，然后将 Aor 非A ，化简 因为A or 非A 等于 True
一次只能消除一个Paris
举例：P 和 非P 结论是 空 contribution
而 PVQ 和 非PV非Q 结论是 True
合取范式（CNF）（Conjuctive normal form）
CNF的标准
没有 ⇔
没有 ⇒
¬只能在单词之前，不能在括号前
用 且 来间隔 或
A ∧ B
A ∧ （B∨ C）
A∨ B is ok
等于 （A∨ B）∧True
归结算法
为了证明 KB |=α ，只需要证明 KB∧¬α 是不可满足的
将KB∧¬α 转化为CNF
不断归结
最终 如果归结出 空子句 ，等于出现了矛盾，那么证明 KB|=α 是对的
最终如果没有可以添加的新语句了，那么 KB 不蕴含α
归结的完备性
如果子句集是不可满足的，那么这些子句的归结闭包包含空子句
horn子句和限定子句
hron子句
含有0 or 1个正文字
¬A∧B 是
¬A 是
限定子句
只含有1个正文字的析取式
¬A∧B∧C 不是
前向和反向链接算法
用已知的KB，判断某个单命题的true false
反向链接
first -order logic
chapter8
一阶逻辑
命题逻辑无法表达 ： 如果 有微风，它的旁边有陷阱
只能表达：B1.1 ⇔ （P12 v P21） B2.1 ⇔ （P11 v P22 v p31） ......
Quantifier
universal quantification
often with ==》
existential quantification
often with ∧
0 条评论
回复 删除
下一页
