知识点是通过老师上课ppt整理,对于期末复习的基本考点都有涉及,以及计算题部分都有例题进行讲解,希望能帮助大家更好的复习。
人工智能期末复习
- 人工智能
- 一、绪论
- 二、知识表示与知识图谱
- 三、确定性推理
- 四、不确定性推理方法
- 五、搜索求解策略
- 六、机器学习
人工智能
一、绪论
- 智能的主要流派:
- 思维理论:智能的核心是思维
- 知识阈值理论:智能取决于知识的数量及一般化程度
- 进化理论:用控制取代知识的表示
- 智能的特征:
- 感知能力
- 记忆与思维能力
- 逻辑思维(抽象思维)
- 依靠逻辑进行思维。
思维过程是串行的。
容易形式化。
思维过程具有严密性、可靠性。
- 依靠逻辑进行思维。
- 形象思维(直感思维)
- 依据直觉。
思维过程是并行协同式的。
形式化困难。
在信息变形或缺少的情况下仍有可能得到比较满意的结果
- 依据直觉。
- 顿悟思维(灵感思维)
- 不定期的突发性。
非线性的独创性及模糊性。
穿插于形象思维与逻辑思维之中
- 不定期的突发性。
- 逻辑思维(抽象思维)
- 学习能力
- 行为能力
二、知识表示与知识图谱
知识的特性:
- 相对正确性
- 不确定性
- 可表示性与可利用性
知识的分类:
- 按知识的范围:
- 常识性知识
- 领域性知识
- 按知识的作用以表示划分:
- 事实性知识
- 过程性知识
- 控制性知识
- 按知识的确定性:
- 确定性
- 不确定性
- 按人类的思维:
- 逻辑性知识
- 形象性知识
- 按知识的获取方式:
- 显性知识
- 隐性知识
- 按知识的范围:
知识表示:就是把知识用计算机可接受的符号并以某种形式描述出来。
状态空间表示法(后续会有详细展开)
一阶谓词逻辑表示法(离散学过,就不再整理)
产生式表示法
- 确定性规则知识的产生式表示
- 不确定性规则知识的产生式表示
- 确定性事实性知识的产生式表示
- 不确定性事实性知识的产生式表示
- 确定性规则知识的产生式表示
产生式系统
规则库RB(Rule Base):用于描述相应领域内知识的产生式集合【也称知识库KB:用于存放与求解问题有关的所有规则的集合】
- 作用:是产生式系统问题求解的基础
- 要求:知识的完整性、一致性、准确性、灵活性和知识组织的合理性
综合数据库DB(Data Base):一个用于存放问题求解过程中各种当前信息的数据结构。
推理机:由一组程序组成,负责整个产生式系统的运行,实现对问题的求解。
推理:将规则与事实进行匹配,所谓匹配就是将规则的前提与综合数据库中的已知事实进行比较
冲突消解:匹配成功的规则可能不止一条,发送冲突,推理机必须按照某种策略选择其中一条执行。
执行规则:执行某一规则时,如果其右部是一个或多个结论,则把这些结论加入到综合数据库中:如果其右部是一个或多个操作,则执行这些操作。对于不确定性知识,在执行每一条规则时还要按一定的算法计算结论的不确定性。
终止推理:检查综合数据库中是否包含了最终结论,决定是否停止系统的运行。
产生式系统的例子(为了解产生式如何表示,为后面的计算做铺垫)
产生式表示法的特点
- 优点:自然性;模块性;有效性;清晰性;
- 缺点:效率不高;不能表达结构性知识;
- 适合产生式表示的知识:
- 领域知识间关系不密切,不存在结构关系。
- 经验性及不确定性的知识,且相关领域中对这些知识没有严格、统一的理论。
- 领域问题的求解过程可被表示为一系列相对独立的操作,且每个操作可被表示为一条或多条产生式规则。
语义网络表示法
语义网络:语义网络是一种用实体及其语义关系来表达知识的有向图。一个语义网络主要包括了两个部分:事件,以及事件之间的关系。
可以表示的知识关系:类属关系(常用的属性:Is-a;A-Kind-of;A-Member-of;Instance-of);包含关系(Part-of);属性关系(Have;Can);时间关系(Before;After;At);位置关系(Located-at,Located-on,under,inside,outside);相近关系(Similar-to;Near-to);因果关系;组成关系
语义网络表示例子
例题:
答案:
特点:
- 结构性
- 联想性
- 自索引性
- 自然性
- 非严格性
知识图谱
知识图谱是用图谱的形式表示知识
- 是一种揭示实体之间关系的语义网络
- 多关系图,由多种类型的节点和多种类型的边来组成
相关概念:
- 知识库(Knowledge Base)是人工智能的经典概念之一。 最早作为专家系统(Expert System)的组成部分,用于实现决策推理。知识库中的知识有很多种不同的形式,例如本体知识、关联性知识、规则库和案例知识等
- 链接数据(Linked Data)是由Tim Berners Lee 于2006年提出,为了强调语义互联网的目的建立数据之间的链接,而非仅仅把结构化的数据发布到网上。链接数据最接近于知识图谱的概念
- 语义网络(Semantic Network) 最早是1960年由认知科学家Allan M. Collins 作为知识表示的一种方法提出。其中WordNet是最典型的语义网络。与知识图谱相比,早期的语义网络更加侧重描述概念及其之间的关系,而知识图谱更加强调数据或事物之间的链接
知识图谱的逻辑结构
- 模式层:数据模型是按照本体论的思想,勾画出来的数据组织模式,数据模型可以展示数据的组织方式和相互关系。例如:创建动植物的数据模型,可以按照动植物的通用分类标准,使用七个主要级别:界、门、纲、目、科、属、种 。数据模型除了确定对象之间的分类、关系,还要明确对象的属性。其中分类、关系反映了数据之间的关系特征,属性反映了数据的内在特征。不同类型的知识图谱,组织数据的方式也有所不同,涉及到具体数据的内容也有差别。比如对于一个人物来说,如果是历史知识图谱,可能人物数据的内容主要侧重于人物的生平,主要事迹,人物关系等,如果是文学知识图谱,人物数据的内容则会主要侧重人物的主要作品,师承关系,作品流派等。
- 数据层:数据层中就是具体一条条的数据,它是依据数据模型组织起来的。我们可以把数据模型看作是骨架,把具体数据看作是肌肉,两部分共同组成了一个健壮的整体。知识以事实(fact)为单位存储在图数据库,通常以“实体-关系-实体”或者“实体-属性-值”三元组作为事实(fact)的基本表达方式。存储在图数据库中的所有数据将构成庞大的实体关系网络,形成知识的“图谱”
知识图谱的两种构建方式
- 自顶向下:自顶向下的构建方式,是指先确定知识图谱的数据模型,再根据模型去填充具体数据。数据模型的设计,是知识图谱的顶层设计,根据知识图谱的特点确定数据模型,就相当于确定了知识图谱收集数据的范围,以及数据的组织方式。这种构建方式,一般适用于行业知识图谱的构建,对于一个行业来说,数据内容,数据组织方式相对来说比较容易确定。比如对于法律领域的知识图谱,可能会以法律分类,法律条文,法律案例等等的方式组织。
- 自下向上:自下向上的构建方式,是指先按照三元组的方式收集具体数据,然后根据数据内容来提炼数据模型。 采用这种方式构建知识图谱,是因为在开始构建知识图谱的时候,还不清楚收集数据的范围,也不清楚数据怎么使用,就是先把所有的数据收集起来,形成一个庞大的数据集,然后再根据数据内容,总结数据的特点,将数据进行整理、分析、归纳、总结,形成一个框架,也就是数据模型。一般公共领域的知识图谱采用这种方式
知识图谱的数据存储
原始数据类型:
结构化数据(Structed Data):如关系数据库
半结构化数据(Semi-Structed Data):如XML、JSON、百科
非结构化数据(UnStructed Data):如图片、音频、视频、文本存储方式
RDF(Resource Description Framework)存储
RDF本质是一个数据模型(Data Model),它提供了一个统一的标准,用于描述实体/资源。RDF形式上表示为SPO三元组。三元组被用来表示实体与实体间的关系,或者实体的某个属性的值是什么。从内容上其结构为 “资源-属性-属性值” ,资源实体由URI表示,属性值可以是另一个资源实体的URI,也可以是某种数据类型的值
RDF序列化的方式主要有:RDF/XML,N-Triples,Turtle,RDFa,JSON-LD等几种
图数据库存储
- 图数据库的结构定义相比RDF数据库更为通用,实现了图结构中的节点,边以及属性来进行图数据的存储,典型的开源图数据库就是Neo4j。
- 图数据库源于图理论,它包含节点和关系,具有如下几个特征:
- 节点(node):通常表示实体,例如人员、账户、事件等,节点可以有属性和标签。
- 边(edge):又被称为关系(relationships),具有名字和方向,并有开始节点和一个结束节点,边是图数据库中最显著的一个特征,在RDBMS中没有对应实现。
- 属性(properties):类似KV数据库中的键值对,节点和边都可以有属性。
知识图谱的构建过程
- 知识抽取:知识抽取即从不同来源、不同结构的数据中进行知识提取,形成知识(结构化数据)存入到知识图谱
- 知识融合:多个来源的关于同一个实体或概念的描述信息融合起来
- 知识加工:通过信息抽取,从原始语料中提取出了实体、关系与属性等知识要素,并且经过知识融合,消除实体指称项与实体对象之间的歧义,得到一系列基本的事实表达。
三、确定性推理
推理
推理方式及其分类
演绎推理:一般 → 个别(也就是我们常说的三段论的推理)
归纳推理:个别 → 一般
- 完全归纳推理(必然性推理)
- 不完全归纳推理(非必然性推理)
默认推理(default reasoning,缺省推理):知识不完全的情况下假设某些条件已经具备所进行的推理
确定性推理、不确定性推理
- 确定性推理:推理时所用的知识与证据都是确定的,推出的结论也是确定的,其真值或者为真或者为假。
- 不确定性推理:推理时所用的知识与证据不都是确定的,推出的结论也是不确定的。
单调推理、非单调推理(按推出的结论是否越来越接近目标来划分)
- 单调推理:随着推理向前推进及新知识的加入,推出的结论越来越接近最终目标
- 非单调推理:由于新知识的加入,不仅没有加强已推出的结论,反而要否定它,使推理退回到前面的某一步,重新开始。
启发式推理、非启发式推理(按推理过程中是否运用与问题有关的启发性知识来划分)
PS:启发性知识:与问题有关且能加快推理过程、提高搜索效率的知识。
推理的方向
- 正向推理
- 反向推理
- 混合推理
- 双向推理
冲突消解策略
- 已知事实与知识的三种匹配情况:
- 恰好匹配成功(一对一)
- 不能匹配成功
- 多种匹配成功(一对多、多对一、多对多)【这个时候需要进行冲突消解】
- 多种冲突消解策略:
- 按针对性排序
- 按已知事实的新鲜性排序
- 按匹配度排序
- 按条件个数排序
- 已知事实与知识的三种匹配情况:
自然演绎推理(就是离散中谓词逻辑推理规则,这里不再赘述)
归结演绎推理⭐⭐⭐
定理:Q 为 P1,P2,…,Pn的逻辑结论,当且仅当(P1∧P2∧…1∧Pn)∧﹃Q是不可满足的。
谓词公式化为子句集的方法
- 消去谓词公式中的“→”和“ ↔”符号
- 把否定符号”﹃”移到紧靠谓词的位置上
- 变量标准化
- 消去存在量词
- 化为前束形
- 化为标准形
- 略去全称量词
- 消去合取词,把母式用子句集表示
- 子句变量标准化
例子:
鲁宾逊归结原理(消解原理)的基本思想:
检查子句集 S 中是否包含空子句,若包含,则 S 不可满足;若不包含,在 S 中选择合适的子句进行归结,一旦归结出空子句,就说明 S 是不可满足的
归结:设C1与C2是子句集中的任意两个子句,如果 C1中的文字L1与 C2中的文字L2互补,那么从C1和 C2中分别消去L1和L2,并将二个子句中余下的部分析取,构成一个新子句C12 。
置换:置换可简单的理解为是在一个谓词公式中用置换项去替换变量。例如, {a/x, c/y, f(b)/z} 是一个置换。
合一:合一可理解为是寻找项对变量的置换,使两个谓词公式一致。可定义为:设有公式集F={F1, F2,…,Fn},若存在一个置换θ,可使F1θ=F2θ=…=Fnθ,则称θ是F的一个合一。称F1,F2,…,Fn是可合一的。一般来说,一个公式集的合一不是唯一的。
最一般合一:设σ是公式集F的一个合一,如果对F的任一个合一θ都存在一个置换λ,使得θ=σ°λ,则称σ是一个最一般合一(MGU)。一个公式集的最一般合一是唯一的。
例题:
归结反演
步骤:
- 将已知前提表示为谓词公式F
- 将待证明的结论表示为谓词公式Q,并否定得到﹁ Q
- 把谓词公式集{F,﹁Q} 化为子句集
- 应用归结原理对子句集S中的子句进行归结,并把每次 归结得到的归结式都并入到S中。如此反复进行,若出 现了空子句,则停止归结,此时就证明了Q为真
例题:
应用归结原理求解问题
步骤:
- 已知前提 F 用谓词公式表示,并化为子句集 S
- 把待求解的问题 Q 用谓词公式表示,并否定 Q,再与 ANSWER 构成析取式(﹁ Q ∨ ANSWER )
- 把(﹁ Q∨ ANSWER) 化为子句集,并入到子句集 S中,得到子句集 S’
- 对 S’应用归结原理进行归结
- 若得到归结式 ANSWER ,则答案就在 ANSWER 中
例题:
证据理论
信任函数
似然函数
概率分配函数的正交和(证据的组合)
信任函数 Bel(A)和似然函数Pl(A)分别来表示命题A的信任度的下限和上限。同样,也可用它来表述知识强度的下限和上限。这样,就可在此表示的基础上建立相应的不确定性推理模型。
基于证据理论的不确定性推理的步骤:
- 建立问题的样本空间D
- 由经验给出,或者由随机性规则和事实的信任度计算基本概率分配函数
- 计算所关心的子集的信任函数值、似然函数值。
- 由信任函数值、似然函数值得出结论
例题:
四、不确定性推理方法
出现不确定性的原因和特征:证据的不确定性;规则的不确定性;方法的不确定性
不确定性推理:从不确定性的初始证据出发,通过运用不确定性的知识,最终推出具有一定程度的不确定性但却是合理或者近乎合理的结论的思维过程。
可信度方法⭐⭐⭐
它是不确定性推理中非常简单且又十分有效的一种推理方法,优点:直观、简单,且效果好
- 可信度:根据经验对一个事物或现象为真的相信程度
- C-F模型:基于可信度表示的不确定性推理的基本方法。其它可信度方法都是在此基础上发展起来的
知识不确定性的表示
- CF(H,E)的取值范围: [-1,1]。
若由于相应证据的出现增加结论 H 为真的可信度,则 CF(H,E)> 0,证据的出现越是支持 H 为真,就使CF(H,E) 的值越大。
反之,CF(H,E)< 0,证据的出现越是支持 H 为假,CF(H,E)的值就越小。
若证据的出现与否与 H 无关,则 CF(H,E)= 0
- CF(H,E)的取值范围: [-1,1]。
证据不确定性的表示
- 证据E的可信度取值范围:[-1,1] 。
对于初始证据,若所有观察S能肯定它为真,则CF(E)= 1。
若肯定它为假,则 CF(E) = –1。
若以某种程度为真,则 0 < CF(E) < 1。
若以某种程度为假,则 -1 < CF(E) < 0 。
若未获得任何相关的观察,则 CF(E) = 0
- 证据E的可信度取值范围:[-1,1] 。
组合证据不确定性的算法
多个单一证据的合取
E = E1 AND E2 AND … AND En
则CF(E) = min{CF(E1), CF(E2), … , CF(En)}
多个单一证据的析取
E = E1 OR E2 OR … OR En
则CF(E) = max{CF(E1), CF(E2), … , CF(En)}
不确定性的传递算法
结论不确定性的合成算法
例题:
五、搜索求解策略
状态空间表示法
- 用状态空间方法表示问题,首先必须定义状态的描述形式,把问题的一切状态都表示出来。其次要定义一组操作
盲目的图搜索策略
符号说明:
- s-初始状态节点;G-搜索图
- OPEN表:存放刚生成的节点。对于不同的搜索策略,节点在OPEN表中的排列顺序是不同的
- CLOSE表:存放已被扩展的节点
- MOVE-FIRST操作:取OPEN表首的节点作为当前要被扩展的节点n,同时将节点n移至CLOSE表
搜索的一般过程:
- 初始化
- 建立只包含初始状态节点s的搜索图G:={s}
- OPEN:={s}
- CLOSE:={}
- 搜索循环
- MOVE-FIRST(OPEN)-取出OPEN表首的节点n作为扩展的节点,同时将其移到close表
- 扩展出n的子节点,插入搜索图G和OPEN表
- 适当的标记和修改指针
- 排序OPEN表
- 通过循环地执行该算法,搜索图G会因不断有新节点加入而逐步长大,直到搜索到目标节点。
- 初始化
宽度优先
OPEN表中节点简单的排序方式:
宽度优先——扩展当前节点后生成的子节点总是置于OPEN表的后端,即OPEN表作为队列,先进先出,使搜索优先向横向方向发展。
深度优先
- OPEN表中节点简单的排序方式:
深度优先——扩展当前节点后生成的子节点总是置于OPEN表的前端,即OPEN表作为栈,后进先出,使搜索优先向纵深方向发展。
- OPEN表中节点简单的排序方式:
盲目的搜索在白白搜索了大量无关的状态节点后才碰到解答,效率低;
提高一般图搜索效率的关键:优化OPEN表中节点的排序方式
启发式的图搜索策略
全局排序——对OPEN表中的所有节点排序,使最有希望的节点排在表首
A算法, A*算法
局部排序——仅对新扩展出来的子节点排序,使这些新节点中最有希望者能优先取出考察和扩展(只需要了解)
A算法
A*算法
带*的是理想中的状态,正常情况下还是使用f(n),g(n),h(n)来进行判断
启发式函数的强弱及其影响
六、机器学习
基本的机器学习术语
- 数据集(Dataset):数据是进行机器学习的基础,所有数据的集合称为数据集
- 样本(Sample):数据集中每条记录是关于一个事件或对象的描述,称为样本
- 属性(Attribute)或特征(Feature):每个样本在某方面的表现或性质
- 特征向量(Feature Vector):每个样本的特征对应的特征空间中的一个坐标向量
- 学习(Learning)或者训练(Training):从数据中学得模型的过程,这个过程通过执行某个学习算法来完成
- 训练数据(Training Data):训练过程中使用的数据
- 训练样本(Training Sample):训练数据的每个样本
- 训练集:训练样本组成的集合
- 标记(Label):训练数据中可能会指出训练结果的信息
机器学习算法
- 监督学习:在建立预测模型的过程中将预测结果与训练数据的实际结果进行比较,不断的调整预测模型,直到模型的预测结果达到一个预期的准确率
- 无监督式学习:数据并不被特别标识,计算机自行学习分析数据内部的规律、特征等,进而得出一定的结果(如内部结构、主要成分等)
- 半监督学习:半监督学习介于监督学习和非监督学习之间,输入数据部分被标识,部分没有被标识,没标识数据的数量常常远远大于有标识数据数量。这种学习模型可以用来进行预测,但是模型首先需要学习数据的内在结构以便合理的组织数据来进行预测
- 强化学习:根据反馈信息来调整机器行为以实现自动决策的一种机器学习方式
机器学习工作流程
数据采集:爬虫,API,数据库
数据处理:数据清洗;数据预处理;数据归一化
特征工程:一般认为括特征构建、特征提取、特征选择三个部分
构建模型
模型评估
混淆矩阵
模型评估指标
准确率
精确率
召回率
F1-Score(F1得分)
模型评估方法
- 留出法(Holdout检验):它将原始的样本随机划分为训练集S和验证集T两部分。在S上训练出模型后,用T来评估其测试误差,作为对泛化误差的估计。
- 交叉验证:首先将全部样本划分成K个大小相等的样本子集,每个子集都尽可能保持数据分布的一致性,即从D中通过分层采样得到,然后每次用K-1个子集的并集作为训练集,余下的那个子集作为测试集,这样就可以获得K组训练集/测试集,从而可进行K次训练和测试,最终返回的是K个测试结果的均值。显然,交叉验证法评估结果的稳定性和保真性在很大程度上取决于K的取值,为强调这一点,通常把交叉验证称为“K折交叉验证”,K的最常取值为10,称为10折交叉验证,其它常取的K值有5,20等
- 留一法:留一法是交叉验证法的一个特例,是将数据集D中包含的m个样本分为m份,留一法不受随机样本划分方式的影响,因为m个样本划分为m份只有一种划分方法,留一法使用的训练集与初始数据集相比只少了一个样本,这使得在绝大多数情况下,留一法中被实际评估的模型与期望评估的用D训练出的模型很相似,因此留一法的评估结果往往被认为比较准确。然而,留一法也有其缺点:在数据集大时,训练m个模型的计算开销可能是难以忍受的,另外,留一法的评估结果也未必永远比其他评估方法准确。
- 自助法:不管是留出法还是交叉验证,都是基于划分训练集和测试集的方法进行模型评估的,然而,当样本规模较小时,将样本集进行划分会让训练集进一步减少,这可能会影响模型训练效果,自助法是可以维持训练集样本规模的验证方法
优化过拟合与欠拟合
- 降低欠拟合风险方法
- 增加新的特征,当特征不足或现有特征与样本标签的相关性不强时,模型容易出现不拟合。
- 增加模型复杂度,简单模型的学习能力较差,通过增加模型的复杂度可以使模型拥有更强的拟合能力。
- 减少正则化系数。正则化是用来防止过拟合的,但当模型出现欠拟合现象时,则需要针对性地减少正则化系数
- 降低过拟合风险方法
- 从数据入手,获得更多的训练数据。使用更多的训练数据是解决过拟合问题最有效的手段,因为更多的样本能够让模型学习到更多更有效的特征,减少噪音的影响,当然,直接增加实验数据一般是很困难的,但是可以通过一定的规则来扩充训练数据。
- 降低模型复杂度。在数据较少时,模型过于复杂是产生过拟合的主要因素
- 正则化方法
- 集成学习方法。集成学习是把多个模型集成在一起,来降低单一模型的过拟合风险
- 降低欠拟合风险方法
调参和最终模型