人工智能
2021-01-06

搜索

简单游戏画图

DFS

BFS

启发式搜索

爬山搜索

• 从当前结点开始, 与周围的邻接点比较
• 若当前结点是最大的, 则返回当前结点(作为最大值)
• 否则选择最大的邻接点作为下一结点
• 局部最优解

最佳优先搜索

• $f(n) = g(n) + h(n)$
  • $g(n)$: 从起始点到$n$的实际代价
  • $h(n)$: 从$n$到目标点的估计代价(启发式评估函数)
• BFS: $f(n) = h(n)$
• Dijkstra: $f(n) = g(n)$

A*算法

• 可采纳性
  • 当存在一个解路径时, 算法总是终止在此解路径上
• 最优性
  • 若
    • $A_1*: f_1(n) = g_1(n) + h_1(n)$
    • $A_2*: f_2(n) = g_2(n) + h_2(n)$
  • 如果$h_1(n) < h_2(n)$, 则$A_2*$展开的结点数小于$A_1*$
• 单调性
  • 启发函数$h$是单调的
    • $n_j$是$n_i$的后继结点, 则$0 \le h(n_i) - h(n_j) \le cost(n_i, n_j)$
    • $h(goal) = 0$

极小极大搜索

• max: 代表我方玩家, 最大化收益
• min: 代表对手, 最小化收益

将启发值自底向上传播

• 如果父状态是max结点, 将子结点中的最大值传给它
• 如果父状态是min结点, 将子结点中的最小值传给它

极小极大过程

• 在预判层应用启发式评估
• 展开所有的后继分支
• 沿树向上传播评估值

$\alpha,\beta$剪枝

• 当确定是一个dead end时, 停止展开其后继结点
• 对博弈树DFS, 且维护
  • $\alpha$: 与max结点关联, 从不减小
  • $\beta$: 与min结点关联, 从不增大

剪枝规则

• $\alpha$剪枝: 任一min结点, 如果其$\beta$值小于等于祖先结点的$\alpha$值, 则停止搜索
• $\beta$剪枝: 任一max节点, 如果其$\alpha$值大于等于祖先结点的$\beta$值, 则停止搜索

推理

证明 树状图, 推导过程

• 谓词演算
  • 语法
  • 语义
  • 推理规则

合一

参考:cnblogs

替换

• 一个替换(Substitution)是形如$\{t_1/x_1, \cdots, t_n/x_n\}$的有限集合, 其中
  • $t_1, t_2 \cdots, t_n$是项, 称为替换的分子
  • $x_1, x_2, \cdots, x_n$是互不相同的个体变元, 称为替换的分母
  • $t_i$不同于$x_i$, $x_i$也不循环地出现在$t_j$中
  • $t_i/x_i$表示用$t_i$替换$x_i$
  • 没有元素的替换称为空替换, 记作$\varepsilon$
• 设$\theta = \{t_1/x_1, \cdots, t_n/x_n\}, \lambda = \{u_1/y_1, \cdots, u_m/y_m\}$是两个替换, 则将集合$\{t_1 \lambda x_1, \cdots, t_n \lambda x_n, u_1/y_1, \cdots, u_m/y_m\}$中符合下列条件的元素删除, 得到替换$\theta \cdot \lambda$
  1. $t_i \lambda / x_i$, $(t_i \lambda = x_i)$
  2. $u_i/y_i$, $(y_i \in x_1, \cdots, x_n)$

合一算法

1. 令$k = 0, S_0 = S, \sigma_0 = \varepsilon$
2. 若$S_k$只含有一个谓词公式, 则算法停止, $\sigma_k$就是所求的最一般合一
3. 求$S_k$的差异集$D_k$
4. 若$D_k$中存在元素$x_k$和$t_k$, 其中$x_k$是变元, $t_k$是项且$x_k$不在$t_k$中出现, 则置$S_{k + 1} = S_k\{t_k/x_k\}, \sigma_{k + 1} = \sigma_k \cdot \{t_k/x_k\}$, 然后回到2
5. 算法停止, $S$的最一般合一不存在

归结(消解)

消解否证的步骤

• 把前提或公理转换成子句形式
• 把求证目标的否定形式子句加到公理集合中
• 对所有子句进行消解, 产生它们的逻辑结果子句
• 用产生空子句的方法来得出矛盾

转换子句

• 消去蕴含
• 将否定式将至原子式
• 将所有量词左移
• 消除存在量词
• 去掉所有全称量词
• 将表达式转换为析取子句的合取形式

知识表示

不太会专门出题

不确定性推理

DS证据理论(%50, 实例理解)

参考:CSDN

概率密度函数(mass函数)

$m: 2^{\Omega} \to [0, 1]$, 且$m(\emptyset) = 0, \sum_{A \subseteq \Omega} m(A) = 1$

信任函数(信度函数)

$Bel: 2^{\Omega} \to [0, 1], Bel(A) = \sum_{B \subseteq A} m(B)$, 其中$A \subseteq \Omega$

$Bel$为下限函数, $Bel(A)$表示对$A$的总信任度

似然函数

$Pl: 2^{\Omega} \to [0, 1], Pl(A) = 1 - Bel(\lnot A)$, 其中$A \subseteq \Omega, \lnot A = \Omega - A$

$Pl$为上限函数, $Pl(A)$表示对$A$非假的信任度

信任区间

$[Bel(A), Pl(A)], (Pl(A) \ge Bel(A))$

证据的合并

• 证据相同情况下的证据合并
• 证据相左情况下的证据合并

Dempster证据合并规则

对于$\forall A \subseteq \Omega, \Omega$上的两个mass函数$m_1, m_2$, 其Dempster合成规则为:

$$ m_1 \oplus m_2(A) = \dfrac{1}{K} \sum_{B \cap C = A} m_1(B) \times m_2(C) $$
$$ K = \sum_{B \cap C \not= \emptyset} m_1(B) \times m_2(C) = 1 - \sum_{B \cap C = \emptyset} m_1(B) \times m_2(C) $$

• $K$为冲突因子
• 前提: 证据是相互独立的

贝叶斯网络

贝叶斯网络的推理(%50)

贝叶斯公式

$$ P(A_i | B) = \dfrac{P(A_i B)}{P(B)} = \dfrac{P(A_i)P(B | A_i)}{\sum_{i = 1}^{n}P(A_i)P(B | A_i)} $$

条件概率的链式法则

$$ P(\alpha_1 \cap \cdots \cap \alpha_k) = P(\alpha_1)P(\alpha_2 | \alpha_1) \cdots P(\alpha_k | \alpha_1 \cap \cdots \cap \alpha_{k - 1}) $$

贝叶斯网络中的独立性

参考:cnblogs

• 随机变量条件独立性
  若$P(\alpha | \beta \cap \gamma) = P(\alpha | \gamma)$或者$P(\beta \cap \gamma) = 0$, 则称事件$\alpha$在给定事件$\gamma$时, 在分布$P$中条件独立于事件$\beta$, 记作$P \models (\alpha \perp \beta | \gamma)$

顺序连接	分支连接	汇合连接
$a \to c \to b$	$a \gets c \to b$	$a \to c \gets b$
$(a \perp b \mid c)$	$(a \perp b \mid c)$	$(a \not\perp b \mid c)$

d-分离

参考:cnblogs

因果推理

诊断推理(证据推理)

马尔科夫逻辑网络

简答题

和贝叶斯网络性质差别(< %50)

• 贝叶斯网络

  • 随机变量作为结点, 有向(无环)图: 用于模拟具有明确方向性的变量之间的概率影响
  • 独立性

• 马尔科夫网络

  • 随机变量作为结点, 无向图
  • 独立性
    • 成对马尔科夫性(Pairwise Markov Property): 给定两个变量子集的分离集, 则这两个变量子集条件独立
    • 局部马尔科夫性(Local Markov Property): 给定变量的所有邻接变量, 那么变量条件独立与所有其他变量条件独立
    • 全局马尔科夫性(Global Markov Property): 对于任意两个变量, 非邻接变量条件独立

符号学习

用于学习布尔函数的ID3算法(设计和实现 $\star$)

信息熵

加入一个随机变量$X$的取值为$X = \{x_1, x_2, \cdots, x_n\}$, 每一种取到的概率分别是$\{p_1, p_2, \cdots, p_n\}$, 那么$X$的熵定义为

$$ Entroypy(X) = -\sum_{i = 1}^{n} p_i \log_2 p_i $$

在$X$的条件下$Y$的条件熵, 是指在$X$的信息之后, $Y$这个变量的信息量的大小

$$ Entropy(Y | X) = \sum_{i = 1}^{n} p(x_i)Entropy(Y | x_i) $$

信息增益

属性$A$对数据集$D$的信息增益为$infoGain(D | A)$

$$ infoGain(D | A) = Entropy(D) - Entropy(D | A) $$

ID3算法步骤

1. 从根节点开始, 计算所有可能的特征的信息增益, 选择信息增益最大的特征作为结点的划分特征
2. 由该特征的不同取值建立子节点
3. 对子节点递归1, 2步, 构建决策树
4. 直到没有特征可以选择或类别完全相同为止, 得到最终的决策树

例子:cnblogs

神经网络

参考:cnblogs

BP学习算法(设计简单例子, 数值计算)

前向传播

• sigmoid(logistic)函数
  • $f(x) = \dfrac{1}{1 + e^{-x}}$
  • $f’(x) = f(x)(1 - f(x))$

反向传播

• 误差计算

  • $Error(n) = \dfrac{1}{2}\sum_{j}(d_j(n) - y_j(n))^2 = \dfrac{1}{2}\sum_{j}e_{j}(n)^2$

• 梯度计算:CSDN

  • 输出层
  • 隐藏层

• 权值更新

  • $w_{new} = w_{old} - \eta\dfrac{\partial E}{\partial w}$

遗传算法

概览:CSDN

使用遗传算法GA进行编码和模拟(< %40)

强化学习

与遗传算法必考其一

MDP运行过程

参考:CSDN

马尔科夫过程(Markov Process)

马尔科夫报酬过程(Markov Reward Process)

• 报酬函数: $ R_{s} = E[R_{t + 1} | S_t = s] $

• 折扣因子: $\gamma$

• 回报
  $$ G_{t} = R_{t + 1} + \gamma R_{t + 2} + \cdots = \sum_{k = 0}^{\infty} \gamma^k R_{t + k + 1} $$

马尔科夫决策过程(Markov Decision Process)

• 状态值函数:
  $$ v_{\pi}(s) = E_{\pi}[G_t | S_t = s] = E_{\pi}[\sum_{k = 0}^{\infty}\gamma^k R_{t + k + 1} | S_t = s] $$

• 状态-动作值函数:
  $$ q_{pi}(s, a) = E_{pi}[G_t | S_t = s, A_t = a] = E_{\pi}[\sum_{k = 0}^{\infty}\gamma^k R_{t + k + 1} | S_t = s, A_t = a] $$

博弈

可能和搜索联动

博弈

• 策略式博弈$G$:

  • $N$: 玩家集
  • $A_i$: 每个玩家$i$的策略集
  • $u_i$: 每个玩家$i$的收益函数
    $$ G = \{ N, \{ A_i \}_{i = 1}^N, \{ u_i \}_{i = 1}^N \} $$

• 纯策略

• 混合策略

帕累托最优(Pareto Efficiency)

NASH均衡(Nash Equilibrium)

• 混合策略纳什均衡: 玩家$i$选任意一种纯策略的期望收益是相同的