前言

基本概览了人工智能领域的基础知识，从Agent入手，经过搜索，逻辑等。

但对于领域前沿以及一些科研相关的内容没有过多涉及，还是比较浅显。

我准备分笔记、备考两个页面来讲清楚这门课程怎么收获知识+成绩。这里先放笔记。

人工智能笔记

第1章 绪论

人工智能的4种观点

像人一样思考

像人一样行动

合理地思考

合理地行动：★理性Agent：能够实现最佳期望结果而行动的Agent

第2章 智能Agent

2.1 Agent和环境

【2024期中】Agent：可以感知环境并在环境中行动的事物

Agent函数：描述Agent行为，将感知序列映射为行动

Agent程序：实现Agent函数

2.2 理性Agent

【2024期中】理性Agent：对每一个可能的感知序列，根据已知的感知序列和Agent具有的先验知识，理性Agent应该采取能使其性能度量最大化的行动。

或：理性 Agent 为合理行动的 Agent，Agent 根据它所知道的做了“正确的事情”。

2.3 环境PEAS

【2024期中】一个 Agent 包含 4 个部分，性能、环境、执行器、感知器

任务环境：PEAS

性能：Performance

环境：Environment

执行器：Actuators

传感器：Sensors

任务环境的性质

完全可观察<>部分可观察（完全可观察：每个时间点上都能获取环境的完整状态）

单Agent<>多Agent

确定的<>随机的<>不确定的（确定的：下一状态完全取决于当前状态和Agent执行的动作）【举例：真空吸尘器世界<>自动驾驶<>】

片段式的<>延续式的（下一片段不依赖于之前片段中采取的行动）【举例：流水线上的分类任务<>自动驾驶和国际象棋】

静态的<>动态的<>半动态的（环境在Agent计算时是否会发生变化。若Agent性能评价随时间流逝而变化，为半动态）【举例：字谜游戏<>自动驾驶<>国际象棋（计时）】

离散的<>连续的（环境的状态，时间；Agent的感知信息和行动）【举例：国际象棋<>自动驾驶】

已知的<>未知的（Agent的知识状态，即Agent了解环境的“物理法则”）环境的部分/完全可观察<>环境已知/未知【举例：翻牌游戏（已知环境部分可观察）<>视频游戏（未知环境完全可观察）】

2.4 Agent结构

Agent=体系结构+程序

★Agent程序（基础4个+转化为学习Agent）

（每张对应的图要能画出来，下图由前向后每次迭代增加功能）

简单反射Agent：基于当前感知选择行动，不关注感知历史

基于模型的反射Agent：Agent根据感知历史维持内部状态，Agent随时更新内部状态信息

基于目标的Agent：除了感知信息之外，还需要根据目标信息来选择行动

基于效用的Agent：当达到目标的行为有多种时，基于效用进行决策

【2020期中】学习Agent：由性能元件，评判元件，学习元件，问题产生器构成

评判元件：根据固定的性能标准告诉学习元件Agent的运转情况

学习元件：学习部件根据评判部件反馈的评价Agent的表现，确定如何修改执行部件

性能元件：接受感知，选择外部行动

问题产生器：负责得到新的和有信息的经验的行动提议

第3章 通过搜索进行问题求解

3.1 问题求解Agent

搜索问题求解Agent步骤：形式化，搜索，执行

问题的定义

初始状态：In(A)

行动：对于状态s，ACTION(s)={GO(B), GO(C), GO(D)}

转移模型：RESULT(IN(A), GO(B))=IN(B)

目标测试：测试当前状态是否目标状态{IN(TARGET)}

路径耗散：反应性能度量

3.2 问题实例

真空吸尘器世界

状态：机器人的位置和灰尘的位置

行动：向左，向右，吸灰尘

转移模型：状态+行动->新状态

目标测试：检查所有位置是否都干净

路径耗散：1/行动

八数码问题

状态：8个棋子以及空格在棋盘9个方格上的分布

行动：空格向左，向右，向上，向下

转移模型：状态+行动->新状态

目标测试：检查状态是否匹配目标

路径耗散：1/行动

八皇后问题（原版）

状态：棋盘上0-8个皇后的任一摆放都是一个状态

行动：任意空格增加1个皇后

转移模型：将增加了皇后的棋盘返回

目标测试：8个皇后都在棋盘上，且无法互相攻击

路径耗散：无

八皇后问题（改进）

状态：n（0<=n<=8）皇后在棋盘上的任意摆放，满足左边起n列的皇后位置都合法

行动：在最左侧的空列中选择一格摆放皇后，要求该格子未受攻击

转移模型：将增加了皇后的棋盘返回

目标测试：8个皇后都在棋盘上，且无法互相攻击

路径耗散：无

3.3 通过搜索求解

▲搜索树<>搜索图

【图搜索集特有】探索集（closed表）：记录每个已扩展的节点。新节点若在探索集/边缘集中，它将被丢弃而不是被加入边缘集中

【区别】搜索树会将与之相连的每个节点都作为待扩展结点（即使刚刚由A->B，A还是会称为B的扩展结点），搜索图则会保存所有已经被扩展的结点（不是待扩展，而是已经扩展）保存在closed表中，这些结点不会再作为被扩展结点。

节点数据结构：

n.state 状态空间中的状态

n.parent 父节点

n.action 父节点扩展时采取的行动

n.path-cost 代价，初始状态到达该节点的路径损耗

搜索顺序：FIFO队列，LIFO队列，优先级队列

哈希表：快速有效检测重复状态

问题求解算法性能

完备性：问题有解时，算法是否能保证找到解

最优性：搜索策略是否能找到最优解

时间复杂度：搜索过程中产生结点的数目

空间复杂度：内存中同一时间存储的最多节点数

3.4 ★无信息搜索（盲目搜索）

【特点】除了问题定义中提供的状态信息外没有任何附加信息，算法只能区分状态是不是目标状态，无法比较非目标状态的好坏

宽度优先搜索：FIFO队列实现【完备性√】

一致代价搜索：扩展路径消耗最小的节点（宽搜+优先队列），【若不存在0代价行动，则是完备的】

深度优先搜索：

深度受限搜索：规定到了深度d就不再继续搜索，【可能是不完备的】

迭代加深的深度优先搜索：若到了深度d无结果，则扩展深度到d+1，【不一定最优，但完备】

3.5 ★有信息（启发式）的搜索策略

定义：

评估函数：f(n)

启发函数：h(n) = 节点n到目标节点的最小代价路径的代价估计值（只依赖于节点状态）

当前实际代价：g(n)

案例：

（一致代价搜索：f(n) = g(n)）（这个不是有信息搜索，放这里只是方便比较）

贪婪最佳优先搜索：f(n) = h(n)

A*搜索：f(n) = g(n) + h(n)

保证最优性的条件：可采纳性 & 一致性 （一致性更难满足，有一致性则必是可采纳的）

可采纳性：h(n)不会高估到达目标的代价，即h(x)<h*(x)

一致性/单调性（只作用于图搜索）：满足三角不等式 h(n) <= c(n,a,n') + h(n')

（可证明A*算法：若具有可采纳性，则有树搜索最优性；若具有一致性，则具有图搜索最优性）

【证明过程】PPT上有

【作业题】证明若一致，必是可采纳

证明：给定一个启发式函数满足h(G)=0,其中G是目标状态，证明如果h是一致的，那么它是可采纳的。

假设n为任意状态, G为某目标状态, 且从状态n到状态G的一条最优路径为n, n1, n2, ……, nm

根据一致性条件，h(n) <= c(n, a1, n1) + h(n1)

<= c(n, a1, n1) + c(n1, a2, n2) + h(n2)

<= c(n, a1, n1) + c(n1, a2, n2) + …… + c(nm, am+1, G) + h(G)

又 h(G) == 0，故 h(n) <= c(n, a1, n1) + c(n1, a2, n2) + …… + c(nm, am+1, G)

根据实际意义，h*(n) = c(n, a1, n1) + c(n1, a2, n2) + …… + c(nm, am+1, G)，因为这是从n到G的实际距离。

综上，h(n) <= h*(n)

3.6 启发式函数

评价：对于启发式搜索策略，关键在于启发式函数，启发式函搜索的性能分析可以使用有效分支因子。假设有N个结点，解的深度为d，N+1 = 1+(b*)+(b*)^2+(b*)^3+……+(b*)^n。b*即为有效分支因子。有效分支因子越小，算法性能越好，h(n)越大，有效分支因子越小。有效分支因子越小，算法性能越好。

优势：若h2(n) > h1(n) 且均可采纳，则h2(n)有优势。（更倚重引导了，有效分支就减少了）

第3章总结

算法	完备性	最优性	TIME	SPACE
宽搜	√（分支有限时）	√（单步代价相同时）	0(b^d)，b分支因子	0(b^d)
一致代价	√（分支有限且代价不为0）	√	O(b^(1+lowbound(C*/ε)))	O(b^(1+lowbound(C*/ε)))
深搜	×	×	0(b^m),m最大深度	0(b*m)
深度受限	×	×
迭代加深	√（分支有限时）	√（单步代价相同时）	0(b^d)	0(b*d)
双向	√（都为宽搜且分支有限）	√（都为宽搜且单步代价相同）
贪婪最佳优先	×	×
A*	√	√

【某年期末+2020期中】经典题

注意画图与实现

其中，一致代价：

队列，每次出队（即为扩展）代价最小的节点，并入队与它相连的且未经扩展过的节点，更新其在队列中的代价，直到扩展到终点节点。

第4章 超越经典搜索

4.1局部搜索算法与最优化问题

智能优化算法（属于启发式算法）：遗传算法，模拟退火算法，禁忌搜索算法，粒子群算法，蚁群算法，爬山法

局部搜索算法：从单个当前结点出发，通常只移动到它的邻近状态而不保留搜索路径

①爬山法

（内存消耗小，能在很大的或者无限的状态空间中找到合理的解。属于局部搜索算法，）

爬山法的缺陷：

局部极大值：【主要缺点】会陷入局部最优解，而不一定能搜索到全局最优解

山脊：一个不直接相连的局部极大值序列，从每个局部极大点出发都是下山方向（搜索可能会在山脊的两面来回震荡，前进步伐很小。）

高原：一块平的区域，可能会迷路

②模拟退火算法

（允许下山的随机爬山算法）：温度T控制以小于1的概率exp(-Δe/T)接受非最佳的移动

在迭代更新可行解时，以一定的概率来接受一个比当前解要差的解，因此有可能会跳出局部最优解，达到全局的最优解。随着时间的推移，允许算法向坏的方向移动的概率逐步下降。

③局部束搜索（未讲）

局部束搜索（记录k个状态，各自搜索但信息传递，通知更好的状态）

随机束搜索（解决局部束搜索可能的k个状态很快聚集问题，随机选择后继的k个状态，即在topk中随机选择，而不是选择最好的那个）

④遗传算法

编码方案：怎样把优化问题的解进行编码（二进制编码、浮点数编码方法、格雷码、符号编码方法、多参数编码方法）

适应度函数：怎样根据目标函数构建适应度函数

选择策略：优胜劣汰、适者生存

控制参数：种群的规模、算法执行的最大代数、执行不同遗传操作的概率等

遗传算子：【重要】选择，交叉，变异

算法终止准则：最大演化代数，或算法在连续多少代以后解的适应值没有改进

【遗传算法补充（2024期中考试20分）】

轮盘赌算法：又称比例选择方法，其基本思想：各个个体被选中的概率与其适应度大小成正比。

1.产生初始种群 s1= 13 (01101) s2= 24 (11000) s3= 8 (01000) s4= 19 (10011)

2.计算适应度 假定适应度为f(s)=s^2 ，则 f (s1) = f(13) = 13^2 = 169 f (s2) = f(24) = 24^2 = 576 f (s3) = f(8) = 8^2 = 64 f (s4) = f(19) = 19^2 = 361

3.选择概率

4.累计概率

平铺图

例如设从区间［0, 1］中产生4个随机数: r1 = 0.450126, r2 = 0.110347 r3 = 0.572496, r4 = 0.98503

【2024期中】（TODO）

轮盘赌算法

4.2 连续空间中的局部搜索（没讲）

4.3 使用不确定动作的搜索（没讲）

实例：不稳定的吸尘器世界

不确定性问题的解是嵌套if-then-else语句，是树而非序列

与或搜索树：

确定性环境，或节点，在或节点上规范一个活动

不确定性环境：与节点，在与节点上包含所有可能的后果（画图时有连接标记）

4.4 部分可观察信息的搜索

①无观察信息的搜素（也称：无传感问题/相容问题）【无传感问题可解，不是无解】

物理状态：对于物理问题P，P有n个物理状态{s1,s2,s3,……,sn}

信念状态：包含物理状态的每个可能集合（最多2^n个信念状态，其中可能很多不可达）

初始状态：P这n个物理状态的集合{s1,s2,s3,……,sn}

行动序列：ACTIONS(b) = ∪对任意(s∈b) ACTIONSp(s)

转移模型：（有点像编译原理LR文法的DFA项集图的感觉，简单来说就是对信念状态内的每个物理状态都做一遍ACTION，所得的为新信念状态）

确定行动：b' = RESULT(b,a) = {s' | s' = RESULTp(s,a) 且 s∈b}

不确定行动：b' = RESULT(b,a) = {s' | s' ∈ RESULTp(s,a) 且 s∈b}

目标测试：信念状态中的所有物理状态都满足目标状态

路径开销：假定所有状态下一个行动的开销相同

结论：如果一个行动序列是信念状态b的解，那么该行动序列是信念状态任何子集的解

②有观察信息的搜索

在无观察信息的基础上多加一步对结果可能感知的预测，再多加一个合并

③求解部分可观察环境中的问题

④部分可观察环境中的问题求解Agent

形式化，搜索算法，执行解行动

解是一个条件规划不是一个序列 if-then-else

Agent在完成行动和接收感知信息时维护自身的信念状态

4.5 联机搜索Agent和未知环境（没讲）

第5章 对抗搜索（博弈）

定义

S0 初始状态

Player 谁行动

Actions 状态下的合法行动集合

Result(s,a) 状态转移模型

Terminal-test(s) 终止测试

Utility(s,p) 效用函数

★MIN-MAX算法

时间复杂度O(b^m)，空间复杂度O(bm)

MIN层，MAX层

★αβ剪枝

剪枝条件（6分）

对于maximizer的子节点，如果取值大于等于beta，则进行剪枝；

对于minimizer的子节点，如果取值小于等于alpha，则进行剪枝。

机会博弈

扩展极小极大算法：添加chance层

多人博弈

用向量值取代单一值

通常选择使自己效用值最大的行为

联盟与破坏联盟

不完整信息游戏

不完美时的决策

截断测试，评估函数，向前剪枝，搜索表

【2017期末】

提高博弈问题的搜索效率有什么方法并分析每种方法对算法最优性的影响：

（1）α-β剪枝，不影响算法的最优性 （2分）

（2）采用评估函数和截断测试的方式，影响算法的最优性（2分）

（3）向前剪枝策略只考虑最优的部分分支，影响算法的最优性（2分）

（4）采用搜索表的方式，不影响算法的最优性（2分）

第6章 CSP约束满足问题

6.1 约束满足问题的定义：

约束满足问题（CSP，Constraint Satisfaction Problem）由一个变量集合和一个约束集合组成。

每个变量有自己的值域，当每个变量都有自己的赋值同时满足所有关于变量的约束时，问题就得到了解决，这类问题就叫做约束满足问题。

三元组{X, D, C}

X 是变量的集合：{X1, X2, X3, ……, Xn}

D 是值域的集合，每个变量都有自己的值域。：对于Xi有{ D1, D2, D3, ……, Dn} （D即Domain）

C 是描述变量取值的约束集合（C即Constraint）

问题的状态定义：对部分/全部状态的一个赋值

相容的：一个不违反任何约束条件的赋值

完整的：每个变量都已经赋值

CSP的解是相容的、完整的部分赋值：只有部分变量赋值（通常作为中间状态）

约束：一元约束、二元约束、高阶约束、全局约束（即这个约束条件涉及几个变量）

6.2 约束传播：CSP中的推理

结点相容：单个变量值域中所有取值满足它的一元约束，该变量节点相容。若网络中所有变量都节点相容，该网络节点相容。

弧相容：某变量值域中所有取值满足它的所有二元约束，该变量弧相容。若网络中所有变量都弧相容，该网络弧相容。

通用弧相容：扩展“弧相容”的概念至n元约束，例如对于Xi的{0,1,2,3}，满足约束X<Y<Z，需要删去2和3

AC-3算法：维护弧相容队列，每次弹出一组弧(Xi,Xj)，首先使Xi对Xj弧相容。若其值域Di无变化，则处理下一条弧；若Di变小，则每个指向Xi的弧(Xk,Xi)都必须重新进入队列中等待检验。若Di变为空集，直接返回失败；否则继续检验。

路径相容：两个变量的集合{Xi,Xj}对于第三个变量Xm是相容的，指对{Xi,Xj}的每一个相容赋值{Xi=a,Xj=b}，Xm都有合适的取值使得{Xi,Xm}和{Xm,Xj}是相容的。（即）

PC-2算法

K相容：对于任何k-1个变量的相容赋值，第k个变量总能被赋予一个和前k-1个变量相容的值，那么这个CSP为k相容

1-相容 -> 结点相容

2-相容 -> 弧相容

3-相容 -> 路径相容

强k相容：从k-相容一直到1-相容都成立

全局约束：

alldiff约束

资源约束：atmost约束

6.3 CSP的回溯搜索

变量和取值顺序：下一步给哪个变量赋值？按什么顺序赋值？

最少剩余值（MRV）/最受约束变量/失败优先启发式

约束最多变量：优先选择最能约束其他变量的变量进行赋值

（取值顺序）最少约束值启发式：选择使得剩余变量赋值空间更大的值

搜索与推理交错进行：每步应该怎样的推理？

前向检验：只要变量X被赋值了，前向检验对它进行弧相容检查，从与它弧相容的未赋值变量Y的值域中删掉与X不相容的值。若值域为空集，直接回溯。（前向检测从赋值变量向未赋值变量传播信息，但不能对失败提供早期检测）

MAC（维护弧相容）：Xi被赋值后，调用AC-3对与Xi弧相容的变量Xj出发进行正常的约束传播。若某变量值域为空，直接回溯。

MAC传递传播约束，而前向检验只读不改

智能回溯：向后看：收获到达某赋值违反约束时，搜索本身能否避免重复这样的失败？

建立冲突集，回溯到冲突集中时间最近的赋值（冲突集可以由前向检验算法提供）

冲突引导的回跳：直接回溯到导致问题的根源

6.4 CSP局部搜索（没讲）

6.5 问题的结构

应用拓扑排序来求解树结构的CSP

割集调整

（1）从CSP的变量中选择子集S，使得约束图在删除S之后成为一棵树。S称为环割集

（2）对于满足S所有约束的S中的变量的每个可能赋值

（a）从CSP剩余变量的值域中删除与S赋值不相容的值，

（b）若去掉S后的剩余CSP有解，把解和S的赋值一起返回

树分解

原始问题的每个变量至少在一个子问题出现

如果两个变量在原问题中由约束相连，那么它们至少同时出现在一个子问题中（连同它们的约束）

吐过一个变量出现在树中的两个子问题中，那么它必须出现在连接这两个子问题的路径上的所有子问题里

期中考试（另附）

1.Agent是什么，理性Agent是什么，一个足球运动员Agent有哪些组件构成

2.初始状态BBWWE，移动方式有两种：①W或B移动到相邻的E，代价1 ②W或B跳到相隔一个W或B的E，代价2。定义评估函数f(x)=d(x)+3*h(x)，d(x)为搜索树深度，h(x)为启发函数，定义为W左侧的B个数之和。要画出搜索树，并问这个启发函数是否具有可采纳性。

3.轮盘赌算法（见遗传补充部分）这里不知道适应度函数代表概率，全错了。

4.min-max和αβ剪枝

5.给了一份数独。问约束满足问题的定义，三个组成构件，以及怎么定义这个数独问题的约束满足问题，最后让写出算法。

第7章-第9章 逻辑Agent

【参考《离散数学》】

命题逻辑

假定世界由一个个的事实组成

基于知识的Agent

知识库(KB)=一种正式语言的语句集合

预先给定的而不是推导的语句称为公理

知识库的添加:Tell

知识库的查询:Ask

逻辑蕴含关系：α |= β， M(α) ⊆ M(β)

模型检验

可靠性：KB |-i α

完备性：任意 KB |= α，都有 KB |-i α

命题逻辑

命题联结词

复合命题

真值表

语法

语义

逻辑等价

如果两个语句α,β在同样的模型集合中为真，则它们是逻辑等价的,记为α ≡ β

α ≡ β当且仅当 α |= β 且β |= α

语句：

有效的（所有模型中都为真）

可满足的（在某一个模型中为真）

不可满足的（每个模型中都不为真）

推理规则

假言推理规则/分离规则（M.P.）

与消解

与导入

双重否定

单项消解/单项归结

★消解/归结

命题逻辑推理算法

DPLL算法：是一种完备的、以回溯为基础的算法，用于解决在合取范式（CNF）中命题逻辑的布尔可满足性问题。

WalkSAT算法：用于求解布尔可满足性问题（确定是否存在满足给定布尔公式）的局部搜索算法

WalkSAT算法：

每次迭代时选择一个未得到满足的子句并从该子句中选择一个符号对其进行翻转，翻转符号的选择方法：

1）最小化新状态下未满足语句的数量

2）随机挑选符号

评估函数：最小化不满足的子句数量

一阶逻辑/谓词逻辑

命题逻辑假定世界由一个个的事实组成

命题逻辑的局限性

在命题逻辑中，每个陈述句是最基本的单位——原子命题，无法对原子命题进行分解。

命题逻辑中，不能表达局部与整体、一般与个别的关系。

一阶逻辑/谓词逻辑（First Order Logic, FOL）假定世界包含对象、关系、函数

原子命题被细化为个体、谓词和量词。

基本元素

谓词

量词

函词

谓词<>函词（谓词提供由个体到True/False的映射，函词提供由个体域中的个体到个体的映射）

全称量词与存在量词

主要逻辑连接符：

任意 对应 ->

存在 对应 合取符号

全称量词和存在量词同时存在时不能随意交换顺序，同一类别单独存在时可以全称

全称/存在量词的引入/消去

全称量词实例化（用任何常数置换）

合一置换（使不同的逻辑表示变得相同的置换）Unify

一般化假言推理规则（GMP）

归结：通过合一置换θ={ u/G(x), v/x}进行归结

【用一阶逻辑描述集合论】

【用一阶逻辑描述电路领域】

【某年期末考题：建立亲属关系的公理系统】

【很多年的考题】★★★转换为合取范式（CNF）

消去等价词（双向蕴含改单向蕴含）

消去蕴含词

否定内移

变量标准化

Skolem化（注意三种情况的变化什么是斯科伦范式（Skloem norm），如何化简 - 知乎）

删除全称量词

等价变换为合取范式（将合取分配到析取中）

Skolem化补充：

【很多年的考题】使用归结算法证明

欲证明KB=|α，

只要证明(KB∧﹁α)是不可满足的

【经典示例：West贩卖导弹给敌国是犯罪的】

第13章 不确定性的量化

【参考《概率论》内容】

13.1 不确定环境下的行动

信念度：Agent拥有的知识不能保证实现其中任何一个目标，但可以提供它们在某种程度上将被实现。

逻辑Agent<>概率Agent

（相同点，都认为）世界由成立或者不成立的事实组成

逻辑Agent相信每个语句是正确的或者错误的

概率Agent为每个语句赋予一个0到1之间的数值作为其信念度

一个Agent是理性的，当且仅当它选择能产生最高期望效用的行动，称为期望效用最大化

效用理论：Agent会偏好效用（utility）更高的状态

决策理论=概率理论+效用理论

期望效用最大化（MEU）原则

逻辑断言与概率断言

逻辑断言考虑的是要排除所有那些断言不成立的世界。

概率断言考虑的是各种可能世界的可能性有多大。

13.2 基本概率符号

样本空间( Ω，omega的大写)：所有可能世界组成的集合，是互斥的，完备的

ω（omega的小写）表示样本空间中的一个样本，即ω是一个特定的可能世界

★公式1：概率基本公理：样本空间中的可能世界的总概率为1：ΣP(w)=1

★公式2：事件/命题：对任意命题f，P(f)=Σ(w∈f) P(w)

★公式3：条件概率：P(a|b)=P(a∪b)/P(b)，注意可以使用链式规则

★概率密度函数 P(X=x)=lim(x->0) P(x<=X<=x+dx) / dx

★公式4：概率公理：包含-排斥原理： P(A∩B) + P(A∪B) = P(A) + P(B)

★全概率公式：

柯尔莫哥洛夫公理：公式1+公式4

无条件概率/先验概率：不知道其它信息的情况下对命题的信念度

要素化表示，随机变量，概率分布

概率分布：所有可能的随机变量赋予概率值

联合概率分布：对多个随机变量中的每个变量发生的可能性进行概率赋值

使用完全联合概率分布作为“知识库”

归一化α

独立性

独立性/边缘独立性/绝对独立性（a⊥b）【这个⊥符号有问题，应该两条竖线】

P(a|b)=P(a)

P(b|a)=P(b)

P(a∪b)=P(a)P(b)

条件独立性（a⊥b | Z）定义如下

任意x,y,z P(x,y | z) = P(x | z) * P(y | z)

任意x,y,z P(x | y,z) = P(x | z)

联合概率规则

P(a∪b) = P(a|b) * P(b) = P(b|a) * P(a)

贝叶斯规则

贝叶斯公式：P(b|a) = P(a|b) * P(b) / P(a)

朴素贝叶斯：假设所有Effecti各自独立，公式如下：

P(Cause,Effect1,……,Effectn) = P(Cause) * Π P(Effecti | Cause)

第14章 概率推理

★详细教程：

https://www.cnblogs.com/USTC-ZCC/p/12786860.html

贝叶斯网络（信度网/概率网络/因果网络/知识图）

条件概率表（CPT）

链式规则：

P(x1,x2,……,xn)

= P(xn | x1,x2,……,xn-1) * P(xn-1 | x1,x2,……,xn-2) * …… * P(x3 | x1,x2) * P(x2 | x1) * P(x1)

= Π P(Xi | Xi-1 Xi-2 …… X1)

贝叶斯网络构建：由原因指向结果

贝叶斯网络计算公式：

P(x1,x2,……,xn) = Π P (xi | parents(xi))

【很多年考题】贝叶斯网络计算

计算联合概率分布，

计算先验概率，

计算条件概率，

计算枚举精确推理（有查询变量，有隐藏变量，有证据变量）

近似推理（直接采样法）【我没掌握，似乎不重要？】

【2020期末】贝叶斯网络中的条件独立性

（小班）经典的三种结构（同父，v型，顺序结构）

moral图只能确认独立性，不能排除非独立性

D-seperation适用（D-Separation：一种概率图结构独立性的判断方法 - 知乎）

D-seperation划分方法

碰撞点，观测集合

第十五章 时间上的概率推理

马尔科夫假设：当前状态只依赖于有限的固定数量的过去状态

平稳性假设：转移概率相同

马尔可夫过程（一阶，二阶）

马尔科夫链（转移模型）

隐马尔科夫链（转移模型，传感器模型）

马尔可夫链的独立性：对于一阶马尔可夫链，不相邻即有独立

稳定分布：初始分布的影响随着时间的推移，变得越来越少

【怎么求稳态分布的概率？第∞天和第∞+1天，列二元方程】

应用：web链接分析，应用内程序的平稳分布

【2019，2020期末】隐马尔可夫链，序列概率，最可能的隐藏层

第十八章 机器学习

机器学习：从数据中自动分析获得规律，并利用规律对未知数据进行预测的算法。

机器学习的分类：

监督学习（有输入和输出，分类/回归）

无监督学习（没有输出）

强化学习

线性回归-参数学习

损失函数

训练集，测试集，k折交叉验证

判别方法/生成方法

判别方法直接学习判别函数𝑓(𝑋) 或者条件概率分布𝑃(𝑌|𝑋) 作为预测的模型，即判别模型。典型判别模型包括回归模型、神经网络、支持向量机和Ada boosting等。

生成模型从数据中学习联合概率分布𝑃(𝑋, 𝑌)（通过似然概率𝑃(𝑋|𝑌) 和类概率𝑃(𝑌) 的乘积来求取）。典型方法为贝叶斯方法、隐马尔可夫链

过拟合/欠拟合

early stopping

数据集扩增

正则化方法

Dropout

KNN（K近邻算法）

★【】朴素贝叶斯分类器

★【】决策树

【期末考试题】

熵：

信息增益：

第十八章 人工神经网络

感知器算法

前向传播，反向传播

多层神经网络

前向传播，反向传播

【考题】

深度学习

卷积神经网络，卷积核

【猜测考题】

计算卷积

卷积核，步长，卷积运算，特征图

计算池化

最大池化，平均池化，总和池化

强化学习