引论

人工智能概述¶

可计算思想¶

费马猜想与费马定理
地方太小，写不下（费马大定理）
英国的数学家怀尔斯证明了这个定理是成立的

如何判断一个问题是否可以计算
证明算术公理的相容性

• 完备性
• 一致性
• 可判定性

图灵机的模型：程序
任何可以计算的函数都可以使用图灵机计算

习题：

智能计算方法¶

• 领域人工智能：
  • 照葫芦画瓢、任务导向（alphago）
• 通用人工智能
  • 举一反三、从经验中学习
• 混合增强人工智能（多种智能体的混合形式）（人类是智能的总开关）
  • 外骨骼机器人
  • 人类智能＋机器智能（达芬奇外科手术机器人）
  • 人、机、物联网

主流的方法：

• 符号主义人工智能为核心的逻辑推理
  • IBM“沃森”的推理
• 数据驱动的机器学习：
  • 采集海量的人脸的数据，基于学习到的数据完成人脸分辨的任务（像素点的分布）
• 探索与利用为核心的强化学习
  • 用问题牵引——>从经验中学习

人工智能的历史进展¶

人工智能发展的三次低谷
人工智能的目的，是使机器能够具有（模拟、延伸和扩展人类智能的能力，具体可细分为感知、理解、推理、学习、决策等与人类智能相关的核心功能）。

逻辑与推理¶

命题逻辑¶

• 定义：命题是一个能确定是真或者是假的陈述句
  • 原子命题：最简单的基本的命题
  • 复合命题：由原子命题组成的命题

通过命题连接词：

• 条件命题前者为假时，无论后者是真假，命题一定为真
  • 如果 p，那么 q 是一种蕴含的关系（充分条件），也就是 p 是 q 的子集
  • p 不成立说明其是一个空集，是任何集合的子集，所以一定为真

例题：

V 是或，反过来是和，——>为条件推理

范式¶

• 重要的概念，将命题公式化归为一种标准的形式，可以进行两个命题的等价判定
  • 析去范式：\(\text{假设}\alpha_\mathrm{i(i=1,2,\cdots,k)}\text{为简单的合取式,则}\alpha=\alpha_1\lor\alpha_2\lor\cdots\lor\alpha_\text{k为析取范式}\)
  • 合取范式：\(假设\alpha_i(i=1,2,\cdots,k)为简单的析取式,则\alpha=\alpha_1\wedge\alpha_2\wedge\cdots\wedge\alpha_k为合取范式\)
  • 两者合称范式
  • 析取范式由合取范式组成，合取范式由析取范式组成
• 析取范式不成立当且仅当每个简单的合取都不成立
• 合取范式是成立的，当且仅当每个简单的析取式是成立的
• 任一命题的公式都有等值的析取范式和合取范式（不唯一的）

谓词逻辑¶

命题逻辑——>谓词逻辑

谓词逻辑中：个体、谓词和量词

• 个体：可以独立存在的具体或者抽象的概念（x 的变元）
• 谓词：刻画个体属性或者是描述个体之间关系存在性的元素，其值为真或者是假
  • 与函数的不同
    • 函数使用之后为因变量
    • 谓词使用之后变成了命题
• 事实符号化：
• 量词的引入：
  • 全称量词：所有的
  • 存在量词：存在
  • 两者统称为量词

• 约束变元：有量词的约束 (x)
• 自由变元：没有量词的约束
• 自由变元既可以存在于量词的约束范围之内，也可以存在量词的约束范围之外

下面的公式是成立的：

在约束变元相同的情况下，量词的运算满足分配率

• 公式中存在多个量词时，多个量词都是同类型的，那么量词的顺序是可以互换的
• 反之是不可以互换的

项与原子谓词公式¶

• 项是描述对象的逻辑表达式
  • 常量符号和变量符号是项
  • 项组成的函数是项：\(\mathrm{f(t1,t2,\cdots,tn)}\)
  • 有限次使用上述的规则产生的符号串是项
• 原子谓词公式：项数目等于对象的命题吗
• 合式公式：
  • 命题常项、命题变项、原子谓词公式为合式公式
  • A 为合式公式，则非 A 也是合式公式
  • A、B 是合式公式，则 \(A\land B、A\lor B、A\to B、B\to A、A\leftrightarrow B\) 是合式公式
  • A 为合式公式，x 为个体变项、\((\exists x)A(x)\neq0(\forall x)A(x)\) 也是合式公式
  • 有限次使用上述的法则构成的表达式组成的是合式公式

推理规则¶

• 全称量词消去：
• 全称量词引入：
• 存在量词消去：
• 存在量词引入：

自然语言的形式化¶

专家系统的构成¶

flowchart LR
    A["问题逻辑化<br/>(机器可理解)"] --> B["推理机<br/>(专家系统)"]
    C["对某个领域的自然语言、<br/>文本语句等信息进行逻辑化<br/>(machine readable knowledge)"] --> B
    B --> D["答案输出"]

知识图谱推理¶

基本概念¶

• 是包含多种关系的图
• 每个节点是一个实体，任意两个节点之间的边表示两个节点间存在的关系
• 实体中存在的关系进行推理，可以得到新的知识

归纳¶

归纳逻辑程序设计算法：使用一阶谓词逻辑进行知识表示
将目标谓词作为推理的规则

• 目标谓词：
• 目标谓词只有一个正例
• 反例：不会显式给出，而是从知识图谱中构建出来
• 背景知识：

推理的思路：逐步给目标的谓词添加前提约束谓词，使得经过目标谓词之后不覆盖任何的反例
通过信息增益的方式来评判前提约束谓词的好坏
FOIL 算法

信息增益

习题¶

因果推理¶

因果推理基本概念¶

先有鸡还是先有蛋的问题
辛普森悖论

主要模型¶

• 结构因果模型
• 因果图：一个无回路的有向图
  • DAG 称为贝叶斯网络

联合概率密度

这就是 d 个变量的联合概率密度

因果图结构¶

链结构¶

• 是一种基本结构
• 包含三个节点两条边，其中一条由第一个节点指向第二个节点，另外一条由第二个节点指向第三个节点
• 
• X，Y 在给定 Z 时条件独立
• 所以有链中的条件独立性定理：
  若 X 和 Y 之间只有一条单向的路径，变量 Z 是截断 (intercept) 该路径的集合中的任一变量，则在给定 Z 时，X 和 Y 条件独立。

分连¶

• 三个节点，两条边
• 两条边分别由第一个点指向第二三个

• 

  \[ \begin{aligned}&P(X,Y|Z)=\frac{P(X,Y,Z)}{P(Z)}=\frac{P(Z)P(X|Z)P(Y|Z)}{P(Z)}\\&=P(X|Z)P(Y|Z)\end{aligned} \]

• 定理：Z 是 X, Y 的共同原因，且 X->Y 只有一条路径，则在给定 Z 的条件, XY 条件独立

汇连图¶

• 
• 此时的 X, Y 是相关的，没有上面的条件独立的性质
• 定理：上面，X, Y 是相互独立的，但是在给定 Z 和 Z 的后代时，X, Y 是相关的

D 分离¶

• 定义 2.18 D - 分离：路径 p 被限定集 Z 阻塞 (block) 当且仅当：
  • (1) 路径 p 含有链结构 A→B→C 或分连结构 A←B→C 且中间节点 B 在 Z 中，或
  • (2) 路径 p 含有汇连结构 A→B←C 且汇连节点 B 及其后代都不在 Z 中。
    若 Z 阻塞了节点 X 和节点 Y 之间的每一条路径，则称给定 Z 时，X 和 Y 是 D - 分离，即给定 Z 时，X 和 Y 条件独立。（分离则独立）

因果反事实模型¶

• 干预：固定系统中的变量，然后改变系统，观察其他变量的变化
• 引入了 do 算子（并表示固定不变，而不是条件概率）

因果效应差

• 在操纵图中，X 和 Z 是 D 分离的，可以得到因果消音的表达式：

得到最后的使用正常的条件表示的因果效应：

右端只包含正常的情况下的概率

反事实模型
反事实描述的是个体的行为

搜索求解¶

搜索算法基础¶

找到最短的路线搜索

每次解决的时候，算法会从已经探索过的路径中选择一条，在末尾进行一次状态转移，可以写成搜索树的形式

常见的搜索算法的评价指标¶

完备性和最优性刻画了找到解的能力以及质量，时间复杂度空间复杂度衡量了算法的资源消耗，常用 O 来描述

在树搜索算法中，集合 F 用于保存搜索树中用于下一步搜索的所有候选节点，这个集合称为边缘集合，有时叫做开表

剪枝搜索：不是所有的后继结点都值得被搜索
图搜索：不允许环路的存在

通过剪枝的方式防止闭环存在

启发式搜索¶

也叫有信息搜索
利用与所搜索的信息相关的信息

贪婪最佳优先搜索：评价函数=启发函数的搜索算法
贪婪最佳优先搜索算法时间和空间复杂度均为 O (bᵐ)，b 是搜索树分支因子，m 是最大深度

\(A^*\) 算法：
评价函数：

• 代价函数 g 表示从起始到节点 n 的开销代价
• 启发函数 h 表示从节点 n 到目标节点的路径中所估算的最小开销代价值（之后的）
• 评价函数 f 为经过节点 n 具有最小开销代价值的路径（已经有的）

贪婪最佳优先搜索¶

• 深度优先搜索：沿着一条路径尽可能深地探索，直到无法继续或者达到目标节点，然后回溯到上一个未完全探索的节点，继续探索其他分支。可以想象成在迷宫中，每次都选择一条路走到尽头，不行再回头换路。
• 广度优先搜索：逐层地探索节点，先访问起始节点的所有邻居节点，然后再访问这些邻居节点的邻居节点，以此类推，就像在池塘中扔一块石头，波纹从中心向四周一层一层扩散。

最短路径的问题
已知每个节点的相邻节点及其距离
辅助信息：每个节点与目标节点间的直线距离（启发函数）

用更快到达目标节点的节点作为下一步的选择
不过这条路径不一定是最优的路径
这里将启发函数作为评价函数

启发函数与评价函数¶

贪婪最佳优先搜索 (Greedy best-first search): 评价函数 f (n)（决定下一步选择的节点）= 启发函数 h (n)

辅助信息（启发函数）：任意城市与终点城市 K 之间的直线距离，由于启发函数就是评价函数，所以只看这个

要将已经发生的历史与未来相结合

对抗搜索¶

零和博弈：一方的收益意味着另一个的损失，不能合作的

在两人的零和博弈时，两人的得分之后是固定的
所以要最大化自己的得分，也就是要最小化对方的分数

在 Minimax（一方使分数最大，一方使得分数最小） 算法中可使用剪枝搜索算法减少被搜索的节点数

剪枝不影响搜索的结果

为什么是这么画的？

1
2
3
4
5

 MAX
 / \ 
MIN MIN 
/ \ / \ 
3 5 2 4

• 首先评估叶子节点，值分别为 3、5、2、4 。
• 然后计算 MIN 节点（取子节点的最小的）的值，左侧 MIN 节点的子节点值为 3 和 5，取最小值 3；右侧 MIN 节点的子节点值为 2 和 4，取最小值 2 。
• 最后计算 MAX 节点的值，它的子节点（两个 MIN 节点）值为 3 和 2，取最大值 3 。所以对于 MAX 方来说，选择左侧 MIN 节点对应的决策就是最优决策。
• 所以可以看出是从下往上倒着推的，max 和 min 是要决定选择哪个子节点

蒙特卡树搜索¶

• 状态：
• 动作：
• 状态转移：
• 奖励：假设从第i个赌博机获得收益分数的分布为\(D_i\)，其均值为\(\mu_i\)。如果智能体在第t次行动中选择转动了第\(l_t\)个赌博机臂膀，那么智能体在第t次行动中所得收益分数\(\hat{r}_t\) 服从分布\(D_{l_t}\)，\(\hat{r}_t\)被称为第t次行动的奖励。为了方便对多臂赌博机问题的理论研究，一般假定奖励是有界的，进一步可假设奖励的取值范围为\([0,1]\)。
• 悔值函数：根据智能体的前 T 次动作，可以定义如下的悔值函数

• 贪心算法：利用已有的尝试中得到的估计来指导后续的动作，需要用机制来平衡算法

• \(\varepsilon\) 贪心算法

  \[ l_t=\begin{cases}\operatorname{argmax}_i\bar{x}_{i,T_{(i,t-1)}},&\text{以}1-\epsilon\text{的概率}\\\text{随机的}i\in\{1,2,\cdots,K\},&\text{以}\epsilon\text{的概率}&\end{cases} \]

  即以 1-E 的概率选择在过去 t-1 次摇动赌博机臂膀行动中所得平均收益分数最高的赌博机进行摇动；以 E 的概率随机选择一个赌博机进行摇动

总结上面的想法：优先估计不确定度大的，但是对于奖励极端偏小的，不应该多计算

上限置信区间算法¶

为每个动作的奖励期望计算一个估计范围，优先采用估计范围上限高的动作

如图，优先计算动作 2（1 的奖励太小，3 的不确定度小）

根据霍夫丁不等式
期望的上限为

在 t 次时选择使得式子取值最大的动作

算法起初是不知道选择节点的奖励的，只能通过选择的均值来决定选择扩展哪些节点，放弃哪些节点等等

机器学习——监督学习¶

基本概念¶

• 分类任务中，监督学习的输出通常是名义变量
• 回归任务中，输出通常是真实数值

分类问题¶

• 标注数据
• 学习模型
• 损失函数

映射函数——预测的函数；损失函数是真实值与预测值之间的差值

从标签数据出发，得到一个使得损失函数最小的映射函数

在最小化经验风险和防止过拟合之间寻找一个平衡

前面的项为经验风险的计算，后面的为降低模型复杂度的修正

两种方法¶

线性回归¶

身高的回归分析
回归模型中的参数求取方法

决策树¶

银行是否借贷的决策树
使用属性值对样本进行划分，使得得到的子样本都是同一类型的

衡量样本划分结果的好坏的方式：
使用信息熵增益

所有的概率的和为 1
对划分之后的样本集的信息熵进行计算
对子样本集分别进行计算，之后原样本集的信息熵为：

其中的 D 为样本集，A 为选择划分的属性，\(D_i\) 为根据属性划分的子样本集，所以计算的公式为划分之后的信息熵乘以在总样本中的占比

线性判别分析¶

让同一类别的数据抱团

• 定义：
  是一种基于监督学习的降维方法，对于具有标签信息的高纬样本数据，利用其类别信息，将其线性投影在一个低维空间上，在低纬空间中同一类别的尽量靠近，不同类别的尽量远离

二分类问题¶

矩阵
投影的方向：
降维的结果

Ada Boosting 算法¶

弱分类器构建强分类器
对于复杂的分类任务，分解为若干子任务，完成方法综合，最终完成复杂的任务

数据样本权重初始化¶

1. 先将 n 个训练物体的权重均分
2. 分类误差：
   1. 误差函数，为没有正确分类的误差的累计\(err_{m}=\sum_{i=1}^{N}w_{m,i}I(G_{m}(x_{i})\neq y_{i})\)
   2. 根据分类误差计算弱分类器的权重：
   3. 该分类器的权重为 \(\alpha_{m}=\frac{1}{2}\mathrm{ln}\frac{1-err_{m}}{err_{m}}\)
   4. 错误率为 ½ 的分类器的权重是 0，相当于随机分类器的行能

3. 更新下一个分类器分类时，某一个分类数据的权重

   1. 计算公式为：\(D_{m+1}=w_{m+1,i}=\frac{w_{m,i}}{z_{m}}e^{-\alpha_{m}y_{i}G_{m}(x_{i})}\)

   2. 在上一个弱分类器中错误的话，权重高一点

      \[ w_{m+1,i}=\begin{cases}\frac{W_{m,i}}{Z_m}e^{-a_m},&G_m(x_i)=y_i\\\frac{W_{m,i}}{Z_m}e^{a_m},&G_m(x_i)\neq y_i&\end{cases} \]

4. 以线性加权的方式组合弱分类器

   \[ f(x)=\sum_{i=1}^M\alpha_mG_m(x) \]

   得到的就是强分类器

   \[ G(x)=sign(f(x))=sign(\sum_{i=1}^M\alpha_mG_m(x)) \]

   决定正负样本的值