人工智能导论考试背诵

发表于 更新于 Waline： 阅读次数：

这门课我在 XJTU 大三下学期上的，老师是可爱的罗敏楠老师，用的课本是著名的《人工智能——一种现代的方法》

考试回忆

八个题

  1. 填空题，被坑到了，有一个题填的是 \(h(n)\) 可采纳时 树搜索 的 A* 算法最优；\(h(n)\) 可采纳且一致时 图搜索 的 A* 算法最优。下面没整理到，我自然就不会了（这里有一点点小争议，图上 A* 搜索若有 \(h(n)\) 一致则不需要重新访问节点；而且这个题挖空挖得很难想到）
  2. 无信息搜索，让画二叉树，写出深度限制和迭代加深搜索的节点序列
  3. 有信息搜索，画出北京地铁北京站到西四的 A* 搜索树
  4. CSP，写弧相容过程
  5. 概率论，给了所有条件概率，算一些概率（简单）
  6. 概率推理，贝叶斯网络推理，不过是解析的而不是数值的，网络结构很小，挺有意思
  7. 时序推理，一阶马尔可夫，不过证据变量一共有四个值（两个布尔变量），算 \(t=1,2,3\) 滤波和平滑
  8. 决策，默写 Expected Utility 公式，顺便考了理性定义，最后给了个不深的例子让求 EU

考试两个半小时，但我看不到表，所以前五题不紧不慢写了一个半小时，老师提醒的时候还有三个大题，直接绷不住了。写完刚好交卷。

Agent

Agent 通过传感器感知环境并通过执行器对环境产生影响。

  • Agent 函数 \(f:P^*\to A\)，其中 \(P^*\) 为感知序列，\(A\) 为行动；
  • Agent 程序实现 Agent 函数；
  • Agent 程序在 Agent 体系结构上执行。

理性：对每一个可能的感知序列，根据已知的感知序列提供的证据和 Agent 具有的先验知识，理性 Agent 应该选择能够使其性能度量最大化的行动。判断理性依赖于：性能度量、先验知识、行动、感知序列。

任务环境 PEAS (Performance, Environment, Actuators, Sensors)

任务环境的性质：

  • 完全可观察，部分可观察；
  • 单 Agent，多 Agent（其他 Agent 的性能度量依赖于你的行为）；
  • 确定的，随机的；
  • 片段式的（片段之间没有依赖），延续式的；
  • 静态的（环境在计算时不变化），半动态的（性能评价在计算时变化），动态的；
  • 离散的，连续的；
  • 已知的，未知的；

Agent 类型：

  • 简单反射 Agent；
  • 基于模型的 Agent；
  • 基于目标的 Agent；
  • 基于效用的 Agent；
  • 学习 Agent：Critic, Learning element, Problem generator, Performance element.

搜索

无信息搜索

初始状态、行动、转移模型、目标测试、路径消耗

图搜索算法：树搜索算法 + 探索集（closed 表）

最大分支因子 \(b\)，最优解深度 \(d\)，路径最大长度 \(m\)

算法 完备性 最优性 时间复杂度 空间复杂度
宽度优先 是若 \(b\) 有限 是若消耗是深度的非递减函数 \(O(b^{d})\) \(O(b^d)\)
一致代价 是若代价大于零 是 \(O(b^{d^*+1})\) \(O(b^{d^*+1})\)
深度优先 是若空间有限 否 \(O(b^m)\) \(O(bm)\)
深度受限 DLS 是若 \(l>d\) 否 \(O(b^l)\) \(O(bl)\)
迭代加深 IDS 是 是 \(O(b^d)\) \(O(bd)\)
双向搜索 是若 \(b\) 有限 是若消耗是深度的非递减函数 \(O(b^{d/2})\) \(O(b^{d/2})\)

一致代价搜索的最大深度计算：\(d^*=1+\lfloor C^*/\varepsilon\rfloor\)，其中 \(C^*\) 是最优解的代价，每个行动的代价至少为 \(\varepsilon\)

有信息搜索

  • 最佳优先搜索：评估函数 \(f(n)\) 表示节点可取性，启发式
    • 贪婪最佳优先搜索，BFS，对评估函数一致代价，很垃圾，会环
  • A*：评估函数 \(f(n)=h(n)+g(n)\)，\(g(n)\) 是实际代价，\(h(n)\) 是估计代价
    • 保证 \(h(n)\) 可采纳（小于真实代价）且一致（三角不等式）；可以得到 \(f(n)\) 非递减；则最优
    • \(h(n)\) 越大越有优势，两个的 \(\max\) 也是可采纳的
  • 有效分枝因子 \(b^*\) 满足 \(N+1=1+b^*+(b^*)^2+\cdots+(b^*)^d\)，节点总数 \(N\)，解深度 \(d\)

非经典搜索算法

局部搜索算法

  • 爬山法、随机重启爬山法
  • 模拟退火
  • 局部束搜索（记录 \(k\) 个生成所有子状态，选 \(k\) 个最优）
  • 遗传（选择、杂交、变异）

使用不确定性动作的搜索

动作可能导致不同结果，但结果可观察（完全可观察，不确定）

问题的解不是行动序列，而是应急规划：根据感知信息决定行动

与或树搜索：或做选择形成与节点，与节点可以导致多个或节点

与节点需要搜索所有子节点形成规划，或节点需要找到一个成功的子节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
ConditionalPlan andOrSearch(Problem p) {
	return orSearch(p.init_state, p, [])
}
ConditionalPlan orSearch(State s, Problem p, Path pth) {
	if (p.goalTest(s))
		return []
	if (s in pth) # infinity loop
		return fail
	for action in p.actions(s) {
		plan = andSearch(state.results(action), p, s + pth)
		if (plan)
			return action + plan
	}
	return fail
}
ConditionalPlan andSearch(State s, Problem p, Path pth) {
	for (si in s) {
		plani = orSearch(si, p, pth)
		if (!plani)
			return fail
	}
	return [if si plan1 elif s2 plan2 elif ... if sn-1 plann-1 else plann]
}

使用部分可观察信息的搜索

部分可观察问题：使用信念状态（状态的集合）

无观察信息：解是行动序列

部分可观察：感知函数返回状态 \(s\) 的感知信息，可用于更新信念状态，可使用与或树搜索

对抗搜索

即博弈，两人参与的游戏，状态 \(s\) 只有 \(\text{PLAYER}(s)\) 可以行动 \(\text{UTILITY}(s,p)\) 表示玩家 \(p\) 在中止状态 \(s\) 的效用（零和博弈）。 \[ \text{MINMAX}(s)=\begin{cases} \text{UTILITY}(s), & \text{TERMINAL-TEST}(s) \\ \max_{a\in \text{Actions(s)}}\text{MINMAX}(\text{RESULT}(s, a)), & \text{PLAYER}(s) = MAX \\ \min_{a\in \text{Actions(s)}}\text{MINMAX}(\text{RESULT}(s, a)), & \text{PLAYER}(s) = MIN \\ \end{cases} \] 若树有限则完备，若对手最优则最优，时间复杂度 \(O(b^m)\)，空间复杂度 \(O(bm)\)（深搜）

\(\alpha\)-\(\beta\) 剪枝：如果已经有更好的就不搜了，最好情况 \(O(b^{m/2})\)，平均 \(O(b^{4m/3})\)

不完美的实时决策：使用 \(EVAL(s)=\sum_iw_if_i(s)\) 函数，其在设置的最大深度的下一层节点被使用

随机博弈：机会节点（MIN-Chance-MAX-Chance-Min-...），机会节点上做期望

CSP

变量 \(X_i\in X\) 定义，值域 \(D_i\in D\)，约束 \(C_i=\left<scope_i, rel_i\right>\)

状态：对部分（全部）变量的赋值

  • 相容的赋值：不违反条件
  • 完整的赋值（对应不完整的）：每个都赋值

约束：

  • 一元约束：单变量值的约束（使用结点相容消去）
  • 二元约束：两个变量值的约束
  • 高阶约束：多个（使用枚举转换为一元约束）
  • 全局约束：任意个数的变量
  • 偏好约束

约束传播

弧相容：所有满足二元约束

AC-3 算法：队列包含所有弧，每次使一条弧相容，如果有变化，插入所有变化变量的弧

假设有 \(c\) 个弧，复杂度 \(O(cd^3)\)

回溯搜索

具有单变量赋值的 CSP 的深度优先搜索称为回溯搜索

  • 最少剩余值启发式：每次单变量赋值，选择合法值最少的变量

  • 度启发式：选择与未赋值变量约束最多的变量以降低未来分支因子

  • 最少约束值启发式：排除剩余变量中最少的值的那个，试图为剩余变量赋 值留下最大空间

  • 前向检验：跟踪未赋值变量的剩余合法值

问题结构

约束图，可以分解为联通子图，假设每个子图大小 \(c\)，复杂度 \(O(d^c n/c)\)，\(d\) 为值域大小

树结构 CSP（\(O(nd^2)\) 求解）：

  1. 选一个树根做拓扑排序
  2. 倒序做弧相容
  3. 正序赋值

近似树结构：对一个变量赋值删除更新邻居之后就是树

概率推理

先验概率即无条件概率，后验概率即有条件概率

\(P(Weather=sunny)=0.72,\cdots\) 可以这样写概率分布：\(\boldsymbol P(Weather)=\left<0.72,0.1,0.08,0.1\right>\) \[ P(a|b)P(b)=P(a, b) \] 并且对概率分布也成立（枚举所有组合的等式组），还有 \[ P(x_1, \cdots, x_n)=\prod_{i=1}^n P(x_i|x_1, \cdots, x_{i-1}) \] 贝叶斯规则 \[ P(a|b)=\frac{P(a, b)}{P(b)}=\frac{P(b|a)P(a)}{P(b)} \] 枚举推理，其中 \(Y\cup E\cup H=U\) \[ \boldsymbol{P}(Y|E=e)=\boldsymbol{P}(Y,E=e)/P(E=e)=\alpha\boldsymbol{P}(Y,E=e)=\alpha\sum_h\boldsymbol{P}(Y,E=e,H=h) \] 条件独立性：给定 \(A\)，有 \(B\) 和 \(C\) 独立，即 \(P(B|C,A)=P(B|A)\)

朴素贝叶斯： \[ \boldsymbol{P}(Cause,Effect_1,\cdots,Effect_n)=\boldsymbol{P}(Cause)\prod_{i=1}\boldsymbol{P}(Effect_i|Cause) \]

贝叶斯网络

每个节点的条件概率表是所有父节点可能取值组合下的概率

“语法”：网络

“语义”：\(P(x_1,\cdots,x_n)=\prod_{i=1}^{n}P(x_i|parents(X_i))\)，其中 \(parents(X_i)\) 表示 \(X_i\) 的父节点的取值，满足 \(X_1=x_1,\cdots,X_n=x_n\)

构造贝叶斯网络：选择一个变量顺序 \(X_1,\cdots,X_n\)，依次加入网络，父节点选择已经在网络里的最小集合

“拓扑”语义：给定父节点后，变量独立于它的非后代节点

拓扑语义推论：给定马尔科夫覆盖（父节点，子节点，子节点的父节点），变量独立于其他变量

确定性节点：\(X=f(Parents(X))\)

不确定性节点（噪声或关系）：某一个节点为真仅当某一父节点集合中的一个或多个为真，概率为父节点集合中 One-Hot 项 \(q_i\) 的积（\(P(X|U_1,\cdots,U_j,\neg U_{j+1},\cdots,U_k)=1-\prod_{i=1}^j q_i\)）

连续节点：

  • 离散化
  • 参数化（使用概率密度函数）：子变量连续，则定义条件密度函数；父节点连续，则使用概率密度函数（可 Sigmoid）

精确推理

枚举推理 \[ \boldsymbol{P}(Y|E=e)=\alpha\sum_h\boldsymbol{P}(Y,E=e,H=h) \] 上式可以以条件概率表项的乘积重写

变量消元法：按照从右到左的次序求和，存中间因子；因子 \(\boldsymbol f_i\) 是其变量所有取值的值在询问元素上形成的子矩阵，两因子逐点相乘得到的因子，变量是两因子的并集

近似推理

  • 直接采样：从网络按拓扑序采样，没有证据
  • 拒绝采样：拒绝与证据不一致的样本
  • 似然加权：固定证据变量的值，对于证据“依赖”的被采样的事件进行加权，\(w=\prod_{i}P(e_i|parents(E_i))\)
  • 马尔可夫链蒙特卡洛 (MCMC)：从一个随机过程采样，每次通过采样一个非证据变量生成下一个状态，这次采样依赖于马尔可夫覆盖；马尔科夫链趋于稳态分布，在每种状态下花费的时间的长期比例正好与其后验概率成正比

时间上推理

下面都忽略了粗体，假设 \(P(X)\) 表示 \(X\) 的概率分布

\(n\) 阶马尔可夫过程 \(P(X_t|X_{0:t-1})=P(X_t|X_{t-n:t-1})\)

传感器模型 \(P(E_t|X_t)\)（不依赖之前传感），\(n\) 阶传感器马尔可夫过程 \(P(X_t|X_{t-n:t-1}, E_{t-n:t-1})\)

稳态过程：所有的概率分布是固定的

  • 滤波：给证据算信念状态 \(P(X_t|e_{1:t})\)，计算方法类似贝叶斯（\(P(X|e)=P(e|X)P(X)\)，\(P(X)\) 依赖过去）
  • 预测：给证据算未来后验 \(P(X_{t+k}|e_{1:t})\)，计算方法由马尔可夫性 \(P(X_{t+1}|X_t)\) 得
  • 平滑：给证据算过去后验 \(P(X_k|e_{1:t})\)，计算方法是滤波得到的前推后乘马尔可夫得到的后推前
  • 最可能解释：算状态序列 \(\arg\max_{x_{1:t}}P(x_{1:t}|e_{1:t})\)
操作 公式 一阶马尔可夫计算
滤波 \(P(X_{t+1}|e_{1:t+1})=\alpha P(e_{t+1}|X_{t+1})P(X_{t+1}|e_{1:t})\) \(P(X_{t+1}|e_{1:t})=\displaystyle\sum_{x_t}P(X_{t+1}|x_t)P(x_t|e_{1:t})\)
预测 （同上右） （同上）
平滑 \(P(X_k|e_{1:t})=\alpha P(X_k|e_{1:k})P(e_{k+1:t}|X_k)\) \(\begin{aligned}P(e_{k+1:t}|X_k)&=\sum_{x_{k+1}}P(e_{k+1:t}|x_{k+1})P(x_{k+1}|X_k)\\ &=\sum_{x_{k+1}}P(e_{k+1}|x_{k+1})P(x_{k+1}|X_k)\end{aligned}\)
最可能解释 \(m_{1:t}=P(X_{1:t}|e_{1:t})\)，令 \(m_{1:t}^{(x_t)}=P(x_{1:t}|e_{1:t})\) \(m_{1:t+1}=P(e_{t+1}|X_{t+1})\max_{x_t}(P(X_{t+1}|x_t)m^{(x_t)}_{1:t})\)

隐马尔可夫模型，只用一个离散变量 \(X_t\)，但是这个变量有 \(S\) 个值

  • 转移模型 \(T_{ij}=P(X_t=j|X_{t-1}=i)\)，\(T=P(X_t|X_{t-1})\)
  • 传感器模型 \(O_{ii}=P(e_t|X_{t}=i)\)
  • 前向消息 \(f_{1:t+1}=\alpha O_{t+1}T^{T}f_{1:t}\)
  • 后向消息 \(b_{k+1:t}=TO_{k+1}b_{k+2:t}\)

卡尔曼滤波用连续变量建模，使用高斯分布，预测使用积分

动态贝叶斯网络：可以由任意数量状态变量和证据变量构成；隐马尔可夫是各一个离散节点的动态贝叶斯网络；按时间展开再推理

粒子滤波：采样方式进行预测、滤波，每个样本 \(x_t\) 通过似然 \(P(e_t|x_t)\) 加权

制定决策

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

期望效用： \[ EU(A|E)=\sum_{i}P(Result(A)|Do(A),E)U(Result_i(A)) \] 最大期望效用原则（MEU）：\(Action=\arg\max_A EU(A|E)\)

Agent 偏好（遵循下述公理的关系）：

  • 有序：\(\succ,\prec,\sim\) 成立一个
  • 传递：\(A\succ B\succ C \Rightarrow A\succ C\)
  • 连续：有 \(A\succ B\succ C \Rightarrow \exists p,[p,A;1-p,C]\sim B\)
  • 可替换：\(A\sim B\Rightarrow[p,A;1-p,C]\sim[p,B;1-p,C]\)
  • 单调：\(A\sim B\Rightarrow (p\ge q\iff [p,A;1-p, B]\succcurlyeq[q,A;1-1, B])\)
  • 可分解：\([p,A;1-p,[q,B;1-q,C]]\sim[p,A;(1-p)q,B;(1-p)(1-q),C]\)

如果遵守上述公理，那么存在不唯一的实值函数对应偏好（仿射变换保持性质，则可归一化）

生命的价值：微亡，质量调整寿命年

金钱效用，期望货币价值 \(EMV(A)=\sum_i P(Result_i(A))MV(Result_i(A))\)，追求风险 \(U(L)>U(S_{EMV(L)})\)，规避风险 \(U(L)<U(S_{EMV(L)})\)，保险费 \(U(L)-U(S_{EMV(L)})\)

多属性偏好

多属性效用函数 \(U(x_1,\cdots,x_n)=f(f_1(x1),\cdots,f_n(x_n))\)，严格优势 \(\forall i, X_i(B)\ge X_i(A)\)，当行为导致概率分布时有随机优势 \(\forall x,\int_{-\infty}^xp_1(t)dt\le\int_{-\infty}^xp_2(t)dt\)

定性推理确定随机优势：\(X\stackrel{+}{\to}Y\) 表示 \(X\) 对 \(Y\) 有积极影响

确定性偏好：\(X_1\) 和 \(X_2\) 偏好独立于 \(X_3\)，当且仅当结果 \(\left<x_1,x_2,x_3\right>\) 和 \(\left<x_1',x_2',x_3\right>\) 之间的偏好不依赖于 \(x_3\)

相互偏好独立性：如果每个属性都不会影响其它属性之间的权衡方式，那么所有属性显示出相互偏好独立性；如果相互偏好独立，那么 \(f(f_1(x1),\cdots,f_n(x_n))=\sum_i f_i(x_i)\)

效用独立性：如果对 \(X\) 中的属性的抽奖之间的偏好独立于 \(Y\) 中的属性值，则属性集 \(X\) 效用独立于属性集 \(Y\)

相互效用独立性（MUI）：如果一个属性集中的每个子集都效用独立于其余属性，则这个属性集满足相互效用独立性；有 \(U=k_1U_1+k_2U_2+k_1k_2U_1U_2+\cdots\)

序列式决策

  • 回报 \(R\)：对局部效用，状态的实值函数
  • 价值 \(V\)：对全局效用，状态的实值函数
  • 效用 \(U\)：适用于行为、状态、状态序列对通用术语

有限期决策：最优策略非静态（随时间变化）；无限期决策：最优策略静态

序列的效用（假设静态），那么如果初始状态一致，偏好序列也一致：

  • 累加效用：\(U_h([s_0, s_1, s_2,\cdots])=R(S_0)+R(s_i)+R(s_2)+\cdots\)
  • 折扣效用（更重视眼前利益）：\(U_h([s_0, s_1, s_2,\cdots])=R(S_0)+\gamma R(s_i)+\gamma^2 R(s_2)+\cdots\)

马尔可夫决策过程：完全可观察、随机动作、马尔可夫转移模型、折扣或累加回报；转移模型 \(P(s'|s,a)\)

策略 \(\pi(s)\)：在状态 \(s\) 下推荐的行为；无期限折扣效用下对于不同开始状态，策略唯一

状态的真正效用 \(V^{\pi^*}(s)=E[\sum_{t=0}^\infty \gamma^t R(S_t)]\)：当 Agent 执行最优决策时的折扣回报的期望值

贝尔曼方程 \(V(s)=R(s)+\gamma\max_{a\in A(s)}\sum_{s'}P(s'|s,a)V(s')\)：使用该方程迭代是收敛的