2

人工智能-期末复习

 1 year ago
source link: https://mengzelev.github.io/2021/01/08/artificial-intelligence/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

人工智能课程期末复习笔记

我宣布课程ppt写的都是$hit

  • 不会考概念和证明
  • 会给一个游戏（拼图游戏、九宫格等）

状态空间搜索

  • 状态空间图
    • 结点$N$和连接（弧）$A$
    • 初始状态$S$: $N$的非空子集
    • 目标状态$G$: $N$的非空子集
    • 状态空间搜索：从初始状态到目标状态的解路径
    • 图搜索：需要检测和消解循环；树搜索可以免除检测开销；
    • 根节点：初始状态
    • 连接：父节点上的合法动作
    • 后继：在父节点上采用合法动作到达的结点
    • 搜索树：删除后继结点中已经出现的等价状态，所形成的树

  • 数据驱动与目标驱动

    • 数据驱动：从输入数据出发，前向搜索
    • 目标驱动：从预期结果出发，后向搜索
      | 目标表示形式 | 潜在目标数目 | 问题初始事实 | 匹配规则数目
      ——– | ———— | ———— | ———— | ————
      数据驱动 | 难 | 多 | 多 |
      目标驱动 | 易 | | 少 | 多
  • BFS/DFS
  • 迭代加深深度优先：在找到之前不断增加最大允许迭代深度
  • 最佳优先搜索：
    • 如果能预先计算出每个点到终点的距离，每次移动就可以选取离终点最近的结点，这样能比BFS更快地到达终点
    • 为每个点到终点的距离定义一个启发式函数，每次移动选择启发距离值最小的结点
    • 但如果存在障碍物，找到的不一定是最短路径

启发式搜索

参考文章

  • 爬山搜索
    • 扩展当前节点的所有子节点，选择“最优”子节点作为下一步，如果所有子节点都不如当前结点优，则停止搜索
    • 没有回溯，容易陷入局部最优解
  • A*算法
    • 用$f(n)=h(n)+g(n)$作为排序依据，$g(n)$表示起点到当前结点的已移动开销, $h(n)$为当前结点到终点的估计开销（启发函数）,$h$需要根据经验、直觉、研究才能确定，可以采用如曼哈顿距离
    • 每次从open_list（待检测结点队列）选取$f(n)$值最小的结点；
      • 如果该节点为终点，则搜索终止，沿着父节点一路摸回起点作为结果路径
      • 如果非终点，则遍历该结点的所有临近结点；不在open_list中的邻近结点加入open_list，并修改他们的父节点为当前结点；已经在open_list中的检查当前路径是否更近，更近的话进行更新；
    • 如果open_list空了但是没有找到终点，则搜索失败
    • 用$f(n)$替代了Dijkstra里的路径函数
    • 性质：可采纳性、最优性、单调性
  • 简易理解：爬山搜索+回溯=最佳优先；最佳优先+启发式排序依据=A*
  • 一些例子
    • 井字棋：取胜线路数目
    • 8-puzzle：错位牌距离和/错位牌数/距离+2*颠倒牌数

博弈树搜索

  • 极小极大过程MIN-MAX
    • MAX：我方，最大化收益；MIN：对手，最小化收益；
    • 将启发值（利益值）自底向上传播：父结点为MAX就将子结点中的最大值传给它；MIN结点就将最小值传给它
  • 极大极小搜索
    • 对每一步都DFS计算所有可能的结果与利益值，选择能使利益最大化的那个结点；为了防止开销过大一般会限制搜索深度；
  • $\alpha-\beta$剪枝
    • $\alpha$：我方的最优解
    • $\beta$：对手的最优解
    • 主旨：当我知道情况肯定会变坏时，我就不需要知道具体会变得有多坏
    • 当处理我方结点时，如果从该我方结点开始的某一条路径最终到达的叶子结点的利益值（该结点的子结点的$\beta$值）小于当前的$\alpha$值，那么从该结点开始的其他路径都无需再考虑（剪枝）；
    • 当处理敌方结点时，如果从该敌方结点开始的某一条路径最终到达的叶子结点的利益值（该结点的子节点的$\alpha$值）大于当前的$\beta$值，那么从该结点开始的其他路径都无需再考虑（剪枝）
    • 对结点排序非常敏感

参考文章

  • 从文字描述中抽象出形式化的命题表示（目标命题采用否定形式加入集合）
  • 所有命题之间是合取关系，因此命题内部要转化成析取形式（子句）
  • 将所有命题拆成多个子句
    1. 消去所有$P\to Q$，写成$\neg P\vee Q$
    2. 将否定$\neg$移到最内最右
    3. 改名，使得没有同名的约束变量
    4. 消去$\exists$，用约束变元的函数替代
    5. 消去$\forall$，直接去掉
    6. 用公式化为合取范式形式
    7. 改名，使不同子句变量不同名
  • 如果两个子句分别为$\neg P\vee Q$和$P\vee R$的形式，则该两个子句可以进行消解，变成$R\vee Q$ （变元不同时要进行替代）
  • 消解最后得到空命题，则说明该命题组是不可证明的

  • 自动求解策略

    • 宽度优先策略
      • 先穷举所有组合归结出所有能生成的归结式，称为第一给归结式；把第一归结式加入集合再穷举一遍得到第二归结式；以此类推。
      • 完备，但效率低
    • 支持集策略
      • 每一次归结时，其母子句中，至少有一个是与目标公式否定式有关的子句
    • 单元子句优先策略
      • 每次归结时优先选取单文字的子句（称单元子句）为母子句进行归结

  • 在谓词逻辑中应用消解原理，一般需要对个体变元作适当替换

  • 对于一个原子谓词公式集，如果存在一种替换，使得集合中所有公式相等，那么该替换称为该集合的一个合一
    • 合一不唯一，但存在唯一的最一般合一（MGU）。任意一个合一都能由对最一般合一进行替换得到。
  • 差异集：从原子谓词公式集$S$的第一项开始，同时向右比较，直到发现第一个不同的项为止。这些项的差异部分组成一个差异集。e.g. $P(x, y, g(z))$和$P(x, f(a), b)$有两个差异集$D_1={y,f(a)}$和$D_2={g(z), b}$
  • 合一算法：求最一般合一
    • 从左侧开始迭代每一个差异集，进行替换。如果差异集是一个项和一个变元，且变元不在项中出现，则用项替代变元。如果不满足要求则无法合一，算法终止。迭代到仅剩集合$S$只剩一个元素时，算法终止。
    • 注意：每进行一次替换时，谓词公式的所有项都要进行同步替换。

4. 知识表示

语义网络、框架表示、产生系统

一阶谓词表示

  • 状态谓词+操作谓词
  • 用状态谓词表示初始状态和目标状态
  • 为操作谓词定义语义：执行条件+执行效果
  • 合一+搜素完成规划求解

产生式表示法

  • 长得像逻辑蕴涵式，但不一样：产生式表示的推理关系可以是不精确的（可信度）
  • 把产生式看成边，推理过程类似DFS
  • 产生式系统
    • 一堆产生式，某一个产生式的结果可以作为另一个产生式的前提使用
    • 数据库：工作内存，内容在推理过程中动态变化，包括：初始状态、原始证据、中间结论、最终结论
    • 规则库：顾名思义
    • 控制系统：跑算法的
  • 正向推理：数据驱动
  • 反向推理：目标驱动
  • 冲突消解（当有多个可以采用的产生式时）

语义网络表示法

  • 有向图，结点表示概念，边表示概念间的语义关系
  • 基本语义关系
    • 类属关系、包含或聚类关系、属性关系、时间关系、位置关系、相似关系、推论关系、二元关系/多元关系
  • 继承：把事物的描述从抽象结点传递到具体结点，通常沿着类属关系ISA等具有继承关系的边进行
  • 匹配：把待求解问题构造为网络片段，其中某些结点或边的标识是空的，称为询问点；将网络片段与知识库中的某个语义网络片段进行匹配，则与询问点相匹配的事实就是该问题的解
  • 框架：描述对象属性的一种数据结构。框架表示法中知识表示的最基本单元。
    • 槽：描述某一方面的属性
    • 侧面：属性的某一方面
    • e.g. 咒术师框架，咒力槽，侧面：咒力量，咒力操作精度
  • 框架网路系统：将多个相互关联的框架连接起来组织的知识表示和推理系统
    • 纵向联系：框架中增加继承槽，e.g. 特级咒术师框架继承咒术师框架
    • 横向联系：槽值或侧面值为另一个框架名，e.g. 咒术师框架中包含术式槽

5. 不确定性推理

确信度理论

（听说没什么人用了所以不会考）

  • IF E THEN H (CF(H|E))
    • E为前提，H为结论，CF(H|E)是确信度，表示E成立时H成立的概率

DS证据理论

参考文章

  • 辨识框架$\Omega$：一个集合，包含$n$个两两互斥事件

  • 概率密度函数：$m: 2^\Omega\to [0,1]$，$m(A), A\subseteq\Omega$表示$A$中事件发生的概率

  • 信任函数：$Bel: 2^\Omega\to [0,1]$，$Bel(A)=\sum\limits_{B\subseteq A}m(B)$，即该事件（事实集合）所有子集的概率密度之和；下限函数，表示对$A$的总信任度

  • 似然函数：$Pl: 2^\Omega\to [0,1]$, $Pl(A)=1-Bel(\neg A)$；即与该事件交集不为空的概率之和；上限函数，表示对$A$非假的信任度

  • $A$非假$\neq$真，存在不知道的情况，因此有$Pl(A)\ge Bel(A)$

    • $[Bel(A), Pl(A)]$构成对$A$的信任度区间

  • Dempster证据合并规则
    $$
    m_1\oplus m_2(A)=\frac{1}{K}\sum\limits_{B\cap C=A}m_1(B)\cdot m_2(C)\
    K=\sum\limits_{B\cap C\neq\emptyset}m_1(B)\cdot m_2(C)=1-\sum\limits_{B\cap C=\emptyset}m_1(B)\cdot m_2(C)
    $$

    • 计算$K$第二个公式更好用，不容易漏掉
    • 计算时用穷举，一定要注意不重不漏！！！

6. 贝叶斯网络

贝叶斯网络的推理（知因问果、知果问因）

参考文章

  • 贝叶斯定理：已知B发生，A的后验概率$P(A\mid B)=\frac{P(B\mid A)\cdot P(A)}{P(B)}$

  • 贝叶斯网络：

    • DAG，结点为随机变量，边$X\to Y$表示$X, Y$具有因果关系（非条件独立），$X$为因，$Y$为果
    • 联合概率$P(X_1X_2\ldots X_n)=\prod\limits_{i=1}^{n}P(X_i\mid \pi(X_i))$, $\pi(X_i)$表示$X_i$在图中所有的前驱

  • d-可分（D-separation）

    | 连接类型 | 中间结点未知 | 中间结点已知 |
    | ———————- | ————– | ————– |
    | head-to-head(汇合连接) | 两头结点独立 | 两头结点不独立 |
    | tail-to-tail(分支连接) | 两头结点不独立 | 两头结点独立 |
    | head-to-tail(顺序连接) | 两头结点不独立 | 两头结点独立 |

    • 判断贝叶斯网络中两个结点是否独立：看两个结点之间的所有路径是否都被阻塞（只要有一个阻塞结点就可以）：
      • head-to-head连接：路径上未知结点阻塞路径
      • head-to-tail/tail-to-tail连接：路径上已知结点阻塞路径
      • 后继结点的已知/未知状态可以传导，e.g.如果路径上存在head-to-head连接处结点的后继结点已知，那么该汇合连接也会被阻塞
    • 利用独立性可以化简条件概率：若$A, B$独立，则$P(A\mid B)=P(A)$

  • 贝叶斯网络的构建

    • 变量的序会影响最终的构建结果

  • 贝叶斯网络推理

    • 因果推理：知道原因，推出结果的概率
      • 拿出结果结点的所有原因结点进行重新表述，化简使得计算所用的概率都是已知的
    • 诊断推理：知道结果，推出原因的概率
      • 先用贝叶斯公式转化为因果推理
    • 支持推理：分析原因间的相互影响——这个没讲

7. 马尔可夫逻辑网络

马尔可夫网

参考文章

  • 在贝叶斯网的基础上，随机变量间不一定是因果关系，可能只是单纯的有关联，因此将有向图改为无向图就得到了马尔可夫网
  • 马尔可夫网中，亲密关系用因子$\phi(D)$来表示
    • 联合分布函数（吉布斯测度）$P(x)=\frac{1}{Z}\prod\limits_{Q\in cliques(H)}\phi(Q)x_Q$. 其中，$cliques(H)$表示无向图$H$中所有clique的集合；$x_Q$为团簇$Q$中所有的随机变量，$\phi(Q)$为团簇$Q$的因子
    • $Z$为归一化常数，为了确保结果是概率，定义为$Z=\sum\limits_{x\in H}\prod\limits_{Q\in cliques(H)}\phi(Q)x_Q$
  • 对数线性模型
    • 为了让乘积变成求和，因此一般采用对数形式
  • 独立性
    • 马尔可夫网中的独立性有3种表示方式，互相等价
    • 成对马尔可夫独立性：对于任意两个不相邻变量，给定其他所有变量，这两个变量条件独立
    • 局部马尔可夫独立性：对于任意一个变量，给定与它相邻的所有变量，这个变量和与他不相邻的所有变量独立
    • 全局马尔可夫独立性：对于A，B两个变量子集，给定能把A，B分开的结点集合C中的所有变量，A、B两个集合的变量独立
  • 构建马尔可夫网络：根据独立性

8. 符号学习

据说：本章完整版

ID3算法

直接看🍉书

  • 一般路过决策树算法

    • 输入：训练集$D={(x_1, y_1), (x_2,y_2), \ldots, (x_m, y_m)}$； 属性集$A={a_1,a_2,\ldots a_d}$
    TreeGenerate(D, A):
    	生成结点 node
    	if D中样本全属于统一类别C 
    		将node标记为C类叶结点
    		return
    	if A = \emptyset or D中样本在A上取值相同
    		将node标记为叶结点，类别标记为D中样本数最多的类
    		return
    	从A中选择最优划分属性a_*
    	for a_*的每一个值a_*^v
    		为node生成一个分支；
    		令D_v表示D中在a_*上取值为a_*^v的样本子集
    		if D_v为空
    			将分支结点标记为叶结点，其类别标记为D中样本最多的类
    			return
    		else
    			以TreeGenerate(D_v, A\{a_*})为分支结点

  • ID3算法选择最优划分属性——信息增益

    • 信息熵$Ent(D)=-\sum\limits_{k=1}^{n}p_k\log_2~p_k$.
      • $p_k$: 当前样本集合$D$中第$k$类样本所占的比例
    • 信息增益$Gain(D,a) = Ent(D)-\sum\limits_{v=1}^{V}\frac{|D_v|}{|D|}Ent(D_v)$
      • 用属性$a$作为划分后的信息增益，就是划分之后混乱度的降低程度
      • 划分后样本的熵值为划分完各类的熵值按比例加权平均，再与原来的熵值作差

9. 神经网络

  1. BP学习（如何通过梯度下降调整权重）
  2. Delta学习
  3. 单个神经元、感知机到神经网络

神经元-感知机-神经网络

参考文章

    • 输入+权值+偏置单元+激励函数（单个神经元一般使用sgn）+输出

    • 多个神经元

    • 学习规则($d$为期望输出， $c$为学习率)
      $$
      \Delta W_i = c(d-sgn(\sum\limits_{i} w_i*x_i))X_i
      $$

      • 实际输出=期望输出，权值不变
      • 期望输出=1，实际输出=-1，权值增加，$w_i +=2c X_i$
      • 期望输出=1，实际输出=1，权值减少，$w_i-=2cX_i$

    • 学习算法：对输入的每一对样本对调整权值，直到实际输出=期望输出

    • 不能解决非线性可分问题（e.g.异或

  • 多层神经网络

    • 多层感知机，前一层的输出作为后一层的输入
    • 输入层-若干隐藏层-输出层

Delta规则

  • 定义误差$E=\frac{1}{2}\sum\limits_{i}(d_i-o_i)^2$

  • 梯度下降：
    $$
    \Delta W =-c\nabla E\
    \Delta w_k = -c\frac{\partial E}{\partial w_k}=-c\frac{\partial E}{\partial o_i}\frac{\partial o_i}{\partial w_k}=c((d_i-o_i)-f’(\sum\limits_{i}w_ix_i))X_k
    $$

  • 多层神经网络+梯度下降
  • 可以预先算出每一个权值的梯度项计算公式
  • 对于每一组输入样本数据，用梯度下降法修改权值
  • 总之就是求导，除了求导还是求导

（有时间的话再自己全部求导一遍）

10. 遗传算法

  • 算法主体
    • 首先随机选出一些初代个体，计算每个个体的适应度
    • 通过某种选择方式筛选出若干存活个体；对存活个体进行交叉、变异产生后代，使种群数目扩张到与原来相同；
    • 重复上一步直到满足终止条件
  • 编码
    • 把解空间中的点表示成染色体，常用为二进制编码
    • 一个有$n$种取值的属性可以用$n$个二进制位来表示，这样可以表达合取；决策属性只需要一位，因为不会发生合取。
    • 编码要保证交叉和变异之后得到的依然是合法个体
    • TSP问题的编码方法：顺序表示、近邻表示、矩阵表示、路径表示
  • 选择
    • 轮盘赌：按面积比划分的抽奖转盘，个体选择的概率与适应度成正比。
    • 锦标赛选择：按预定概率$p$选择适应度较大的假设，按概率$1-p$选择其他假设
    • 排序选择：选择适应度最大的若干个体
  • 交叉
    • 单点交叉：交换两条染色体从某一点开始的部分
  • 变异
    • 随机选择某条染色体的某一位取反
    • 变异概率一般非常小

11. 强化学习

模型构造、值函数表达、更新迭代

参考：西瓜书

  • 马尔可夫决策过程（MDP）
    • 具有马尔可夫性质：下一个状态仅取决于当前状态
  • 强化学习任务对应四元组$E=\langle X,A,P,R\rangle$
    • $E$: 环境
    • $X$: 状态空间，状态$x\in X$是机器感知到的环境的描述
    • $A$: 动作空间，动作$a\in A$可以作用在当前状态上
    • $P$: 转移函数$X\times A\times X\mapsto\mathbb{R}$，使环境从当前状态按某种概率转移到另一个状态
    • $R$: 奖赏函数$X\times A\times A\mapsto\mathbb{R}$，指定了从某个状态采取某个动作到达另一个状态的奖赏，也可能和动作无关
    • 注意环境与机器的界限：环境中的状态转移和奖赏返回都是不受机器控制的
  • 机器需要通过在环境中不断尝试学得一个策略$\pi$
    • 确定性策略$\pi: X\to A$
    • 随机性策略$\pi: X\times A\to \mathbb{R}$，表示在某种状态下采取某个动作的概率
  • 策略优劣的评估：累计奖赏
    • $T$步累积奖赏
    • $\gamma$累积奖赏

K-摇臂老虎机

（ppt上未详细提到，暂略）

  • 有模型学习，模型的$P,R$已知

  • 状态值函数$V^{\pi}(x)$: 从状态$x$出发，使用策略$\pi$所带来的累积奖赏

    • $T$步累积奖赏：$V^{\pi}T(x)=\mathbb{E}[\frac{1}{T}\sum\limits{t=1}^{T}r_t\mid x_0=x]$

    • $\gamma$折扣累积奖赏: $V^{\pi}{\gamma}(x)=\mathbb{E}[\sum\limits{t=0}^{+\infty}\gamma^tr_{t+1}\mid x_0=x]$

    • 通过计算可以写出递归形式——最优子结构，动态规划
      $$
      V^{\pi}T(x)=\sum\limits{a\in A}\pi(x,a)\sum\limits_{x’\in X}P^a_{x\to x’}(\frac{1}{T}R^a_{x\to x’}+\frac{T-1}{T}V^{\pi}{T-1}(x’))\
      V^{\pi}      \gamma(x)=\sum\limits_{a\in A}\pi(x,a)\sum\limits_{x’\in X}P^a_{x\to x’}(R^{a}{x\to x’}+\gamma V^{\pi}\gamma (x’))\
      $$

  • 状态-动作值函数$Q_{T}^{\pi}(x,a)$: 在状态$x$采取动作$a$带来的累积奖励
    $$
    Q_{T}^{\pi}(x,a)
    =\mathbb{E}[\frac{1}{T}\sum\limits_{t=1}^{T}r_t\mid x_0=x, a_0=a]
    =\sum\limits_{x’\in X}P^a_{x\to x’}(\frac{1}{T}R^a_{x\to x’}+\frac{T-1}{T}V^{\pi}{T-1}(x’))\
    Q    {\gamma}^{\pi}(x,a)
    =\mathbb{E}[\sum\limits_{t=0}^{+\infty}\gamma^tr_{t+1}\mid x_0=x, a_0=a]
    =\sum\limits_{x’\in X}P^a_{x\to x’}(R^{a}{x\to x’}+\gamma V^{\pi}\gamma (x’))
    $$

    • 最优策略：
      • 西瓜书版：$\pi^*=\text{arg}\max\limits_{\pi}\sum\limits_{x\in X} V^{\pi}(x)$， 选择让所有状态的值函数之和（累积奖赏）最大的策略
      • ppt版：$\pi(x)=\text{arg}\max\limits_{a\in A}Q^\pi(x,a)$
    • 最优值函数：最优策略所对应的值函数，$\forall x\in X: V^(x)=V^{\pi^}(x)$
    • 线性规划：列出一堆$V^{\pi}(x)$相关的式子进行求解
    • 策略迭代：先用递推公式计算出$V^{\pi}(x)$，然后对任意$x\in X$, 求能使$Q^{\pi}(x,a)$最大化的$a$作为$\pi’(x)$，用$\pi’$去更新$\pi$，准备开始下一轮计算迭代；不停重复这两个步骤直到$\pi$与$\pi’$重合，$\pi$不再更新（算$V$和改$\pi$交替进行）
    • 值迭代：先求出最优值函数$V^(x)$，然后得到最优策略$\pi^(x)=\text{arg}\max\limits_{a\in A}Q(x,a)$（疯狂算$V$最后算$\pi$）

12. 博弈

  • 几种均衡
    • 社会福利：最大化所有参与者的收益和
    • 纳什均衡：其他参与者都保持不动的情况下，你没办法靠改变自己的策略获得更大的收益
    • 帕里托最优：在所有参与者都不变坏的前提下，你没办法靠改变自己的策略变好
      • 社会福利是帕里托最优的子集
      • 帕里托优：表示一种序关系；而帕里托最优是一种均衡状态
    • 优超：别人管我P事，我自己取最大收益
  • 混合策略纳什均衡
    • 列方程：其他参与者混合策略（概率分布）不变的情况下，我获得的期望利益是相同的

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK