| 【人工智能导论】概念整理 | 您所在的位置：网站首页 › 人工智能导论章节笔记整理 › 【人工智能导论】概念整理 |
【人工智能导论】概念整理
|
人工智能概念
强人工智能：比人类更聪明的机器 弱人工智能：包含基础的，特定场景下的角色型任务 如何看待我们现在出现的人工智能产品？ 近期目标：研究如何使计算机去做那些靠人智力才能做的工作 最终目标：探讨智能形成的基本机理，研究利用自动机模拟人的思维过程 你觉得人工智能未来重点方向或研究内容是什么？怎么达到？ 图灵测试：测试机器能否表现出与人一样的智力水准 通过了如何？ 三大学派，成果： 符号主义 认知的基元是符号，认知过程就是符号运算/推理，智能行为是充要条件是物理符号系统。 成果：人工定理证明、人工智能语言LISP、鲁滨逊归结原理、专家系统连接主义 思维的基元是神经元，思维过程是神经元的连接活动。 成果：Hopfield网络模型、BP网络行为主义 它认为人工智能起源于控制论，智能取决于感知与行为，取决于对外部复杂环境的适应。 成果：布鲁克斯研制的六脚机器虫 确定性知识系统有格式的数据经过处理、解释过程会形成信息，有关的信息关联到一起，经过处理过程形成知识 谓词逻辑基于断言：一个陈述句就是一个断言 命题由谓词表示，它由谓词名和个体组成。一般形式为： P ( x1,x2,…,xn ) 若xi都是个体常量、变元或函数，则称P为一阶谓词，若xi又是一阶谓词，则称P为二阶谓词。 优缺点优点：自然、明确、精确、灵活、模块化 缺点：知识表示能力差、知识库管理困难、存在组合爆炸、系统效率低 自然演绎推理从一组已知为真的事实出发，直接运用经典逻辑的推理规则推出结论。 可表示的知识种类 事实规则上述两者的不确定性度量 基本形式P—>Q 或者 IF P THEN QP是产生式前提，Q是一组结论和操作 规则的表示方法确定性规则 P—>QIF P THEN Q 不确定性规则P—>Q（可信度）IF P THEN Q （可信度） 事实的表示方法确定性事实 断言一个语句变量的值或是多个语言变量间关系的陈述句三元组 （对象，属性，值） （关系，对象1，对象2） 例：老李年龄是40岁 （Li,Age,40） 老李和老张是朋友 （Friend,Li,Zhang） 不确定性事实四元组 （对象，属性，值，可信度） （关系，对象1，对象2，可信度） 例（Li,Age,40，0.8） （Friend,Li,Zhang,0.1） 产生式系统把一组产生式放在一起,一个产生式的结论可以供另一个产生式作为已知事实使用,以求得问题的解,这种系统称为产生式系统 优点：清晰性、模块性、自然性 缺点：效率不高、不能表示结构化知识 例题
语义网是通过概念及其语义关系来表达知识的一种网络图。 它是一个代标注的有向图 节点用来表示各种概念、事物、属性、动作、状态等。弧是有方向，用来体现节点间的主次关系。弧上的标注用来表示节点间的语义联系或语义关系。 基本网元语义网络中最基本的语义单元称为语义基元,可由一个三元组表示：（节点1，弧，节点2）基本网元是一个语义基元对应的有向图，是语义网络中最基本的结构单元
语义关系
实例关系： ISA 体现的是“具体与抽象”的概念，含义为“是一个”，表示一件事物是另一件事物的一个实例。分类关系： AKO 也称泛化关系，体现的是“子类与超类”的概念，含义为“是一种”，表示一个事物是另一个事物的一种类型。成员关系：A-Member-of 体现的是“个体与集体”的关系，含义为“是一员”，表示一个事物是另一个事物的一个成员属性关系：Have Can 指事物和其属性之间的关系。常用的有： Have：含义为“有”，表示一个结点具有另一个结点所描述的属性 Can：含义为 “能”、“会”，表示一个结点能做另一个结点的事情包含关系（聚类关系） 指具有组织或结构特征的“部分与整体”之间的关系 Part-of ：含义为“是一部分”，表示一个事物是另一个事物的一部分。时间关系 指不同事件在其发生时间方面的先后次序关系。常用的时间关系有： Before：含义为“在前” After: 含义为“在后位置关系 指不同事物在位置方面的关系。常用的有： Located-on：含义为“在…上面” Located-under：含义为“在…下面” Located-at：含义为“在…”相近关系 指不同事物在形状、内容等方面相似或接近。常用的相近关系有： Similar-to：含义为“相似” Near-to：含义为“接近”
示例
增加情况和动作结点的描述方法 事件节点由一些向外引出的弧来指出事件行为及发出者与接受者 动作结点由一些向外引出的弧来指出动作的主体与客体 常河给江涛一个优盘 优点：结构性、自然性、联想性 缺点：非严格性、复杂性 框架表示框架是人们认识事物的一种通用的数据结构形式 对于一个框架，当人们把观察或认识到的具体细节填入后，就得到了该框架的一个具体实例 框架由若干个槽组成，槽可以由若干个侧面组成。一个侧面用来描述相应属性的一个方面。槽和侧面所具有的属性值称为槽值和侧面值。
优点：结构性、自然性、深层性、继承性 缺点：缺乏框架的形式理论、缺乏过程性知识表示、请晰性难以保证 归结原理使用反证法，欲证明P →Q，只要证明P∧~Q F 前束形范式：一个谓词公式的所有量词均非否定地出现在公式的最前面,且它的辖域一直延伸到公式之末,同时公式中不出现连接词→及 ↔ 。
利用连接词化归律消去谓词公式中的条件和双条件连接词。 利用等价关系把“~”移到紧靠谓词的位置上。 重新命名，使不同量词的约束变元名字不同 消去存在量词 把全称量词移到公式最左边 利用等价关系将公式化为Skolem标准形 去掉全称量词 对变元更名，使不同子句的变元不同名 消去合取词，即得子句集 由谓词公式转化为子句集的过程可以看出，在子句集中子句之间是合取关系，其中只要一个子句不可满足，则子句集不可满足 归结式
置换是一个形如{ t1/x1, t2/x2, …, tn/xn }的有限集合 ti是项，xi是变元，ti/xi表示用ti替换xi。 ti≠xi，xi≠ xj(i ≠ j),i,j=1,2,3…,n xi不可循环出现在tj中。 不含任何元素的置换称为空置换，以ε表示 eg：{ a/x, f(b)/y, w/z }、{ g(a)/x, f(b)/y }是一个置换，但{ g(y)/x, f(x)/y }不是置换。 合一设有公式集：F={ F1, F2, …, Fn }，若存在一个置换θ，使得 F1θ= F2θ= … =Fnθ 则称θ为F的一个合一置换，且称F1, F2, …, Fn 是可合一的。 最一般合一设σ是公式集F的一个合一，如果对于F的任何一个合一θ，都存在替换λ，使得：θ=σ·λ 则称σ是F的最一般合一 定理证明使用反证法，合取上~G。证明思路见归结原理 例题任何通过历史考试并获得奖学全的人是快乐的。任何肯学习或幸运的人可以通过所有考试。John不学习但很幸运。任何人只要是幸运的就能获得奖学金。求证：John是快乐的。 写出问题P() 子句集中引入~PVANSWER(),归结后的ANSWER中的值即为解 例题任何兄弟都有同一个父亲，John和Peter是兄弟，且John的父亲是David,问Peter的父亲是谁？
搜索：依靠经验，利用已有知识，根据问题的实际情况，不断寻找可利用知识，从而构造一条代价最小的推理路线，使问题得以解决的过程称为搜索 智能搜索：是指可以利用搜索过程得到的中间信息来引导搜索项最优方向发展的算法、 状态：表示问题解法中每一步问题状况的数据结构 算符：把问题从一种状态变换为另一种状态的手段 状态空间方法：基于解答空间的问题表示和求解方法，它是以状态和算符为基础来表示和求解问题的。 问题的状态空间：是一个表示该问题全部可能状态可用算符的集合，它包含三种说明的集合，即三元状态（S，F，G）。 问题的解：从问题的初始状态集，经过一系统列的算符运算，到达目标状态，所经过算符的序列构成一个问题的解 OPEN/CLOSE表OPEN表用于存储尚未探索的状态。这些状态是已知的，但尚未经过评估或扩展（即未检查这些状态是否为目标状态或未探索其可达的下一状态）。 CLOSE表用于存储已经探索过的状态。一旦一个状态从OPEN表中移除并进行了扩展，它就会被加入到CLOSE表中。 启发式搜索启发信息：用于指导搜索过程且与具体问题求解有关的控制信息称为启发信息 估价函数：用来描述节点重要程度的函数f(x)=g(x)+h(x) g(x)为初始节点S0到节点x已实际付出的代价，h(x)是从节点x到目标节点Sg的最优路径的估计代价。h(x)被称为启发函数 A算法在状态空间搜索中，如果每一步都利用估价函数f(n)=g(n)+h(n)对Open表中的节点进行排序，则称A算法。 全局择优将新扩展的节点放进OPEN表后对OPEN表内全部节点进行排序选出下一个节点 局部择优只对新扩展的节点进行排序选择下一个节点 A*算法定义最优路径f*(x)=g*(x)+h*(x)，存在估价函数f(x)=g(x)+h(x) g是g*的估计 ，h是h*的估计 g(x)是对最小代价g*(x)的估计，且g(x)>0,g(x)>=g*(x) h(x)为h*(x)的下界，即对所有的x存在h(x)≤h*(x) 例题有一农夫带一条狼，一只羊和一框青菜与从河的左岸乘船倒右岸，但受到下列条件的限制： (1) 船太小，农夫每次只能带一样东西过河； (2) 如果没有农夫看管，则狼要吃羊，羊要吃菜。 请设计一个过河方案，使得农夫、浪、羊都能不受损失的过河，画出相应的状态空间图
问题归约：把一个复杂问题分解或变换为一组本原问题的过程称作问题归约。 本原问题：不能（或不需要）再进行分解或变换，且可以直接解答的子问题。 将一个复杂的问题分解为几个子问题的过程称为分解。可用与树表示 将一个复杂的问题变换成若干个等价的问题的过程称为等价变换。可用或树表示 与或树
在有序搜索中，应选择那些最有希望成为最优解树一部分的节点进行扩展。我们称这节点构成的树为希望树。 初始节点S0在希望树中。如果节点x在希望树中，则：如果x是或节点，且其子节点依次为y1,y2,…,yn，则具有下述值的子节点也在希望树中： min{c(x,yi)+g(yi)} 1≤i≤n若x是与节点，则其所有子节点都在希望树中。扩展到某个节点时如果是或，则生成左右两个子节点后再继续考虑。 有序搜索 博弈树己方的各种攻击方案为“或”关系，而对方的应着方案为“与”关系。描述博弈过程的“与/或”树称为博弈树。 极大极小分析法根据所求解问题的特殊信息设计合适的估价函数，计算当前博弈树中所有端节点的得分，该分数称为静态估价值。根据端节点的估值推算出其父节点的分数。 若父节点为“或”节点，则其分数等于其所有子节点分数的最大值若父节点为“与”节点，则其分数等于其所有子节点分数的最小值。计算出的父节点的分数值称为倒推值。如果一个方案能获得较大的倒推值，则它就是当前最好的行动方案。
α-β剪枝
α：或节点下的最大值 β：与节点下的最小值 β剪枝：如果“或”节点x的α值不能降低其父节点的β值，则停止搜索x的其余子节点，使x的倒推值为α
选择 从根节点R开始，选择子节点的过程，该过程基于某些规则，例如UCB 节点中的信息为胜利次数/总的访问次数 扩展 一旦到达某个节点后无法再根据已知信息选择子节点时，创建一个或多个可能的未探索的子节点，并选择其中之一 模拟 从新的子节点开始，使用随机的方式进行模拟或玩一场“快速游戏”直到游戏结束，然后更新新节点中的状态 回溯 更新从选中的子节点到根节点路径上的所有节点的信息 MCTS不断重复这四个步骤，通过这种方式可以逐渐构建出一棵以统计信息为基础的搜索树，最终选择最优的移动。 UCB 上限置信区间策略
种群：初始给定的解集 个体：单个解 染色体：单个解的编码 适应度函数：对种群的所有个体应用适应度函数，用于选择 遗传操作：从旧种群迭代到新种群的操作 遗传操作包括以下三步： 选择交叉变异 算法描述 选择编码策略：将问题搜索空间中每个可能的点用相应的编码策略表示出来，形成染色体定义遗传策略：包括种群规模N，交叉、变异方法，以及选择概率Pr、交叉概率Pc、变异概率Pm等遗传参数 选择：轮盘赌算法 交叉：根据给定的点将染色体截段，将两条染色体部分交换 突变：根据给定的突变位点，将编码中的该位点转换，如二进制则取反，十进制取随机数
例题
用概率，在[0,1]区间取值，越接近于0越假，越接近于1越真 用可信度，在[-1,1]区间取值，大于0接近于真，小于0接近于假,等于0为无关 用隶属度，在[0,1]区间取值，越接近于0隶属度越低，反之越高 证据不确定性的表示证据的类型：基本证据，组合证据 表示方法：概率，可信度，隶属度等 基本证据：常与知识表示方法一致，如概率，可信度，隶属度等 组合证据： 组合方式：析取的关系，合取的关系。计算方法：基于基本证据最大最小方法，概率方法，有界方法等。 可信度推理可信度是指人们根据以往经验对某个事物或现象为真的程度的一个判断，或者说是人们对某个事物或现象为真的相信程度。 C-F模型知识是用产生式规则表示的，其一般形式为： IF E THEN H (CF(H, E)) 其中，E是知识的前提条件；H是知识的结论；CF(H, E)是知识的可信度[-1,1]。 eg：IF 发烧 AND 流鼻涕 THEN 感冒(0.8) 对同一前提E，若支持若干个不同的结论Hi(i=1,2,…,n)，则 CF(E)＝0.6： E的可信度为0.6 证据E的可信度取值范围：[-1，1] 。 静态强度CF(H，E)：知识的强度，即当 E 所对应的证据为真时对 H 的影响程度。 动态强度 CF(E)：证据 E 当前的不确定性程度。 组合证据合取 E=E1 AND E2 AND … En时， 若已知CF(E1)，CF(E2)，…， 则CF(E)=min{CF(E1), CF(E2), … ,CF(En)} 析取 E=E1 OR E2 OR … En时， 若已知CF(E1)，CF(E2)，…， 则CF(E)=max{CF(E1), CF(E2), … ,CF(En)} 不确定性的更新公式CF(H)=CF(H, E)×max{0, CF(E)} 若CF(E) |
综合数据库：用于存放输入的事实、从外部数据库输入的事实、中间结果、最后结果 规则库：描述某领域内知识的产生式集合 控制系统：包含推理方式和控制策略
槽值可以是数值、字符串、布尔值或是动作、过程甚至是框架名
斯克林范式：在前束范式的首标中不出现存在量词，即从前束范式中消去全部存在量词所得的公式 
当x在y前面时，认为x约束y，可以将y换位f(x)，无约束时可以换成常量
设有如下结构的移动将牌游戏：
在与或树中没有子节点的节点称为端节点，本原问题所对应的节点称为终叶节点。显然，终叶节点一定是端节点，但端节点不一定是终止节点。
α剪枝：如果“与”节点x的β值不能升高其父节点的α值，则停止搜索节点x的其余子节点，并使x的倒推值为β 
vi 是节点的估计值，ni 是节点被访问的次数，N 是其父节点已经被访问的总次数，C 是可调整参数。 或 
Xj 是节点的估计值，这是为胜利次数/总的访问次数（如3/6），nj 是节点被访问的次数，而 n 则是其父节点已经被访问的总次数。C 是可调整参数 C是平衡因子，其决定着在选择时偏重探索还是利用。C 越大就越偏向于探索（随机效果），C 越小就越偏向于利用（目前胜率效果）。
【本文地址】