人工智能基础
人工智能发展概述
从人工智能的计算性和智能性角度可以将人工智能定义为：
- 三大学派：
符号学派、连接学派、行为学派 - 人工智能的分类：
领域人工智能、通用人工智能、混合增强人工智能 - 人工智能的发展————三次低谷
- 符号主义人工智能：
用规则教，与人类逻辑推理类似，但是难以构建完整的知识规则库 - 联结主义人工智能
用数据教，直接从数据中进行学习，依赖于数据，解释性不强 - 行为主义
用问题引导，从经验中进行能力的持续学习，非穷举式搜索而需要更好的策略
逻辑推理
推理按照由难到易的程度可以分为三个层次: 关联，干预，反事实
命题逻辑
命题逻辑的局限性：在命题逻辑中，每个陈述句是最基本的单位(即原子命题)，无法对原子命题进行分解。
因此在命题逻辑中，不能表达局部与整体、一般与个别的关系。
谓词逻辑
在谓词逻辑中，将原子命题进一步细化，分解出个体、谓词和量词，来表达个体与总体的内在联系和数量关系，这就是谓词逻辑研究内容。
- 谓词和函数的区别
函数是从定义域到值域的映射；
谓词是从定义域到{𝑇𝑟𝑢𝑒,𝐹𝑎𝑙𝑠𝑒} 的映射
知识图谱
-
知识图谱的组成
概念：层次化组织
实体：概念的示例化描述
属性：对概念或实体的描述信息
关系：概念或实体之间的关联
推理规则：可产生语义网络中上述新的元素 -
知识图谱推理:FOIL
因果推理
-
结构因果模型
-
因果图
有向无环图(directed acyclic graphs, DAG)
一个无回路的有向图，即从图中任意一个节点出发经过任意条边，均无法回到该节点。刻画了图中所有节点之间的依赖关系。
DAG 可用于描述数据的生成机制
这样描述变量联合分布或者数据生成机制的模型，被称为 “贝叶斯网络”（Bayesian network） -
阻塞
𝑋是链结构或分连结构节点, 且𝑋∈𝐶
𝑋是汇连结构节点，并且𝑋或𝑋 后代不包含在 C中
-
𝑫-分离：如果𝑨和𝑩 之间所有路径都是阻塞的，那么𝑨和𝑩 就是关于 𝑪 条件独立的；否则𝑨和𝑩不是关于 C 条件独立
-
do算子
干预指的是固定系统中某个变量，观察其他变量的变化
为了与自然取值进行区分，在对𝑋进行干预时，引入𝒅𝒐算子
因此，𝑃(𝑌=𝑦|𝑋=𝑥)表示当𝑋取值为𝑥 时，𝑌=𝑦的概率；
而𝑃(𝑌=𝑦|𝑑𝑜(𝑋=𝑥))表示对𝑋取值进行了干预，固定其取值为𝑥时，𝑌=𝑦的概率。
𝑃(𝑌=𝑦|𝑋=𝑥)反映了在取值为𝑥的个体𝑋上，𝑌的总体分布；
𝑃(𝑌=𝑦|𝑑𝑜(𝑋=𝑥))反映的是如果将𝑋每一个取值都固定为𝑥时，𝑌的总体分布。 -
调整公式
因果效应𝑃(𝑌=𝑦│𝑑𝑜(𝑋=𝑥) )有：
𝑃(𝑌=𝑦│𝑑𝑜(𝑋=𝑥) )=∑𝑃(𝑌=𝑦│𝑋=𝑥, 𝑍=𝑧)𝑃(𝑍=𝑧)
推理总结
| 推理方法 | 推理方式 | 说明 |
|---|---|---|
| 归纳推理 | 如果Ai(i为若干取值)那么B | 从若干属性出发推出一般规律 |
| 演绎推理 | 如果A那么B | A是B的前提，但不是唯一前提，A是B的充分条件 |
| 因果推理 | 因为A所以B | A是B的唯一前提，“如果没有A，那么没有B成立”但A不发生B也可能发生 |
人工智能算法
搜索求解
启发式搜索
贪婪最佳优先搜索
求从城市A到城市K之间的最短路线
贪婪最佳优先搜索：评价函数𝒇(𝒏)=启发函数𝒉(𝒏)
A*搜索
评价函数：𝐟(𝒏)=𝐠(𝒏)(起始结点到结点𝒏代价(当前最小代价))+𝒉(𝒏)(结点𝒏到目标结点代价(后续估计最小代价))
𝐠(𝒏)表示从起始结点到结点𝒏的开销代价值
𝒉(𝒏)表示从结点𝒏到目标结点路径中所估算的最小开销代价值
𝐟(𝒏)可视为经过结点𝒏 、具有最小开销代价值的路径。
对抗搜索
Minmax搜索
最小最大搜索是在对抗搜索中最为基本的一种让玩家来计算最优策略的方法
AlphaBeta减枝搜索
一种对最小最大搜索进行改进的算法，即在搜索过程中可剪除无需搜索的分支节点，且不影响搜索结果。
更新方法
- 子节点继承父亲节点的α、β值
- 对于MIN节点，子节点值小于贝塔则更新
- 对于MAX节点，子节点值大于阿尔法则更新
- 当α>β时，节点直接写入阿尔法或贝塔值，不在探索其余节点
特点
- 剪枝本身不影响算法输出结果
- 节点先后次序会影响剪枝效率
- 如果节点次序“恰到好处”，Alpha-Beta剪枝的时间复杂度为𝑂(𝑏^(𝑚/2))，最- 小最大搜索的时间复杂度为𝑂(𝑏^𝑚 )
蒙特卡洛树搜索
通过采样而非穷举方法来实现搜索。
单一状态蒙特卡洛规划：多臂赌博机
- 过度探索
- 过度利用
上限置信区间策略：UCB
蒙特卡洛树搜索
- 选择
从根节点 R 开始，递归选择子节点，直至到达叶节点或到达具有还未被扩展过的子节点的节点L。 - 拓展
如果 L 不是一个终止节点，则随机创建其后的一个未被访问节点，选择该节点作为后续子节点C。 - 模拟
从节点 C出发，对游戏进行模拟，直到博弈游戏结束。 - 反向传播
用模拟所得结果来回溯更新导致这个结果的每个节点中获胜次数和访问次数。
例题
机器学习
有监督学习
-
训练集共有𝑛个标注数据，第𝑖个记为
-
从训练数据中学习映射函数
-
损失函数就是真值𝑦_𝑖与预测值之间差值的函数。
-
在训练过程中希望映射函数在训练数据集上得到 “损失”最小
即。 -
经验风险
-
期望风险
-
结构风险最小化(structural risk minimization)
为了防止过拟合，在经验风险上加上表示模型复杂度的正则化项(regularizer)或惩罚项(penalty term ) ：
min_{𝑓∈𝛷}1/𝑛 ∑_{𝑖=1}^𝑛𝐿𝑜𝑠𝑠(𝑦_𝑖,𝑓(𝑥_𝑖 )) +𝜆 𝐽(𝑓)
常用的正则项方法包括L1正则项和L2正则项：其中L1使权重稀疏，L2使权重平滑。一句话总结就是：L1会趋向于产生少量的特征，而其他的特征都是0，而L2会选择更多的特征，这些特征都会接近于0。
回归分析
- 一元线性回归
- 最小二乘法
- 多元线性回归
- 逻辑回归/对数几率回归
决策树
- 信息熵：假设有𝐾个信息，其组成了集合样本𝐷，记第𝑘个信息发生的概率为𝑝_𝑘 (1≤𝑘≤𝐾)”。如下定义这𝐾个信息的信息熵：
𝐸(𝐷)值越小，表示𝐷包含的信息越确定，也称𝐷的纯度越高。需要指出，所有𝑝_𝑘累加起来的和为1。
