人工智能基础复习
绪论
人工智能的内涵与研究内容
- 人工智能: 用人工的方法在机器(计算机)上实现的智能;或者说是人们使机器具有类似于人的智能.
- 人工智能学科: 一门研究如何构造智能机器(智能计算机)或智能系统,使它能模拟, 延伸, 扩展人类智能的学科.
- 研究内容:
- 知识表示
- 机器感知
- 机器思维
- 机器学习
- 机器行为
三大学派及其代表工作
- 符号主义学派: 知识表示, 启发式算法
- 联结主义学派: 人工神经网络
- 行为主义学派: Agent智能体
问题求解
搜索与状态空间
- 状态: 表示系统状态, 事实等叙述性知识的一组变量或数组.
Q = [$q_{1}, q_2, …, q_n$$]^T$ - 操作: 表示引起状态变化的过程性知识的一组关系或函数:
F = ${f_{1}, f_{2}, …, f_{m} }$ - 状态空间: 利用状态变量和操作符号, 表示系统或问题的有关知识的符号体系, 状态空间是一个四元组:
$(S, O, S_{0}, G)$- S: 状态集合.
- O: 操作算子的集合.
- $S_{0}$: 包含问题的初始状态, 是S的非空子集.
- G: 若干具体状态或满足某些性质的路径信息描述.
- 例: 八数码问题的状态空间.
启发式搜索
启发式策略
- 启发式信息: 用来简化搜索过程有关具体问题领域的特性的信息叫做启发信息.
- 启发式图搜索策略: 重排OPEN表, 选择最优希望的节点加以扩展.
- 启发式搜索: 利用启发信息的搜索过程.
- 种类: $A, A^*$算法.
A算法
A算法: 使用了估价函数f的最佳优先搜索.
- 估价函数 $f(n)= g(n)+ h(n)$.
- $g(n)$: 状态n的实际代价,例如搜索的深度.
- $h(n)$: 对状态n与目标"接近程度"的某种启发式估计.
- 八数码问题的A搜索算法:
- $g(n)$: 节点n的深度, 如$g(S_0)=0$.
- $h(n)$: 节点n与目标状态不相同的位数(包括空格), 简称"不在位数", 如$h(S_0)=5$.
$A^*$算法
$A^$算法: A算法满足$h(n)<= h^(n)$, 其中$h^*(n)$是状态n到目的状态的最优路径代价.
知识表示和知识图谱
三段论
所有的人都是会死的, 因为诸葛亮是人, 所以诸葛亮是会死的.
$(1) \forall x(Human(x) \rightarrow Die(x)) P规则$
$(2)Human(Zhugeliang) P规则$
$(3)Die(Zhugeliang) T规则$
产生式规则
产生式系统
- 规则库: 用于描述相应领域内知识的产生式集合.
- 综合数据库(事实库、上下文、黑板等): 一个用于存放问题求解过程中各种当前信息的数据结构.
- 控制系统(推理机构): 由一组程序组成, 负责整个产生式系统的运行，实现对问题的求解.
流程
从规则库中取出$r1$, 检查其前提是否可与综合数据库中的已知事实匹配. 匹配失败则$r1$不能被用于推理. 然后取$r2$进行同样的工作。匹配成功则$r2$被执行.
知识图谱及其应用
- 知识图谱(Knowledge Graph/Vault): 用各种不同的图形等可视化技术描述知识资源及其载体, 挖掘, 分析, 构建, 绘制和显示知识及它们之间的相互联系.
- 知识图谱三要素: 实体, 关系, 属性.
- 应用: 维基百科, DBpedia, YAGO, XLORE, 搜索引擎.
专家系统
专家系统产生的标志性事件: 1968年斯坦福大学费根鲍姆等人研制成功分析化合物分子结构的专家系统——DENDRAL系统.
1977年第五次IJCAI国际人工智能联合会议, 费根鲍姆系统性地提出了专家系统的概念.
费根鲍姆(E. A. Feigenbaum):
“专家系统是一种智能的计算机程序，它运用知识和推理来解决只有专家才能解决的复杂问题。”
- 专家系统: 一类包含知识和推理的智能计算机程序.
机器学习
机器学习：机器学习使计算机能模拟人的学习行为, 自动地通过学习来获取知识和技能, 不断改善性能, 实现自我完善.
数据挖掘
- 知识发现: 从数据库中发现知识(KDD).
- 数据挖掘(DM): 从数据库中挖掘知识.
人工神经网络
神经网络如何表示与或逻辑
BP神经网络
前向计算方法
$ u_{i}^{k} = \sum_{j}w_{ij}^{k-1}y_{j}^{k-1}$
$ y_{i}^{k} = f_{k}(u_{i}^{k}) $
反向调整方法
$\Delta w_{ij}^{k-1} = - \varepsilon d_{i}^{k} y_{j}^{k-1}$
$d_{i}^{m} = y_{i}^{m}(1-y_{i}^{m})(y_{i}^{m} - y_{si}) = (y_{i}^{m} - y_{si})f_{m}^{'}(u_{i}^{m})$
$d_{i}^{k} = y_{i}^{k}(1-y_{i}^{k})\Sigma_{i}d_{l}^{k+1}w_{li}^{k} = f_{k}^{'}(u_{i}^{k})\Sigma_{l}d_{l}^{k+1}w_{li}^{k} (k = m-1, …, 2)$
卷积神经网络
计算智能
遗传算法
- 遗传算法(genetic algorithms, GA): 一类借鉴生物界自然选择和自然遗传机制的随机搜索算法, 非常适用于处理传统搜索方法难以解决的复杂和非线性优化问题.
- 设计流程:
轮盘赌
(考代码)
int RouletteWheelSelection(){
srand(0);//定义rand触发随机值得初始值
double m=rand()/double(RAND_MAX); //产生一个[0,1)的随机值；
int Probability_Total=0;
int Selection=0;
for(int i=0;i<SIZE;i++) //SIZE是个体数量的大小
{
Probability_Total=Probability_Total+Probability[i];
if(Probability_Total>=m){
Selection=i;
break;
}
}
return Selection;
}多智能体系统
Agent和多Agent系统
- Agent可以看做是一个程序或者一个实体, 它嵌入在环境中, 通过传感器(sensors)感知环境, 通过效应器(effectors)自治地作用于环境并满足设计要求.
- 多智能体系统(MAS): 一个应用系统中包含多个智能体, 其中的智能体不仅具备自身的问题求解能力和行为目标, 而且能够互相协作, 达到共同的整体目标, 这样的系统成为多智能体系统.
- 其中每个智能体具有独立性和自主性.
- MAS支持分布式应用，具有良好的模块性.
- MAS按面向对象的方法构造多层次、多元化的智能体.
- MAS是一个协调式的系统，也是一个集成系统.
- 在MAS中，智能体之间相互通讯，彼此协调，并行地求解问题，提高了问题求解效率.
- 同一个MAS中各个智能体可以是异构的.
- 在MAS中，不同领域的专家系统、同一领域不同的专家系统可以协作求解单一专家系统难以解决的问题.
- 四要素: 通信, 协调, 协作, 协商.
Agent设计方案
以火星车为例：
- 问题：
- 火星探测器在火星上收集岩石样本并把样本运回基地.
- 岩石的位置未知.
- 探测器可以接收到基地发出的无线电信号.
- 解决方案:
- 如果发现障碍物,则改变方向.
- 如果处于基地并且携带着样本,则放下样本.
- 如果携带着样本且不在基地, 则往无线电信号增强的方向移动.
- 如果检测到样本, 则采集样本.
- 随机移动.