Introduction

图灵测试

图灵测试(The Turing test)由艾伦·麦席森·图灵提出,指测试者与被测试者(一个人和一台机器)隔开的情况下,通过一些装置(如键盘)向被测试者随意提问

进行多次测试后,如果机器让平均每个参与者做出超过30%的误判,那么这台机器就通过了测试,并被认为具有人类智能。图灵测试一词来源于计算机科学密码学的先驱艾伦·麦席森·图灵写于1950年的一篇论文《计算机器与智能》,其中30%是图灵对2000年时的机器思考能力的一个预测,我们已远远落后于这个预测

当超过30%的测试者误以为在和自己说话的是人而非计算机,这台计算机就通过了图灵测试

人工智能三大流派

  • 符号主义(Symbolism):数理逻辑
    • 逻辑主义(Logicism)、心理学派(Psychlogism)或计算机主义(Computerism)
    • 基本思想:物理符号系统(符号操作系统)假设和有限合理性原理
  • 连接主义(Connectionism):人脑模型 - 神经网络
    • 又称仿生学派(Bionicsism)或生理学派(Physiologism)
    • 基本思想:神经网络及其连接机制和学习算法
  • 行为主义(Actionism):控制论 - 自动机
    • 又称进化主义(Evolutionism)或控制论学派(Cybernecticsism)
    • 基本思想:控制论及感知-动作系统

人工智能与机器学习

严格意义上说,人工智能和机器学习没有直接关系,只不过目前机器学习的方法被大量的应用于解决人工智能的问题而已

1

Search

Introduction

对于一个搜索算法应满足下面四个条件

  • 可能到达的状态,包括初始状态,搜索过程中的状态以及目标状态
  • 对于每一个非终态,有一系列可进行的操作,不同的操作可能到达不同的状态,通常由后继函数来定义
  • 消耗函数,决定了每一步操作所耗费的资源
  • 解决方法,从初态到终态的一条路径,其中最佳解决方法是消耗最少的解决方法

评判搜索算法的性能有以下四个标准

  • 完备性:当问题有解决方法时,算法总能找到该方法;当问题没有解决方法时,算法会告诉你解决方法不存在
  • 成本最优性:算法是否能找到成本最优的解决方法
  • 时间复杂度:算法运行所消耗的时间的数量级
  • 空间复杂度:算法运行时所占用内存的数量级

无信息搜索,也就是俗称的盲搜,例如BFS与DFS

对于BFS而言,frontier集合使用队列来实现,先进先出,设b为每个节点的后继子节点个数,d为深度,则其复杂度为(bd-1)*b=bd+1-b,在某一个节点其frontier集合中的元素个数至少为bd,是一个完备的搜索算法,可以找到深度最小的解决方法

对于DFS而言,frontier集合使用栈来实现,先进后出,设b为每个节点的后继子节点个数,m为深度最大值,则frontier集合中的元素个数最多为bm,是一个不完备的搜索算法,可能会遇到不包括终态的环路

可以使用深度受限的DFS搜索算法,算法思想与DFS相同,此外要规定一个深度,不会搜索到大于此深度的节点。深度可由使用者规定,也可通过迭代的方式来增加深度。是一个完备的算法,同样可以找到深度最小的解决方法,此算法融合了BFS与DFS的优点

此外,在算法中的每一步还需要考虑成本,BSF算法能找到深度最小的解决方法是因为总是从最浅的节点开始搜索,同理每次都从成本最低的节点开始搜索可能会找到最佳成本路径

除了从根节点开始搜索之外,还可以从目标节点开始搜索,前提是要事先知道目标节点的状态且目标节点的个数不能过多

双向搜索,即从根节点开始执行搜索算法的同时,从目标节点向根节点搜索,复杂度降低至O(bd/2)

有信息搜索,也叫启发式搜索(Heuristic Search),通过启发函数来衡量哪个状态更接近目标状态,例如最佳优先搜索、贪婪搜索以及A*搜索

对于最佳优先搜索(Best-first Search),是一般的树搜索和图搜索,根据启发函数来判断应该扩展哪一个节点。启发函数估计了从n节点到目标节点的距离和成本,用h(n)表示

贪婪的最佳优先搜索(Greedy)很快就能找到问题的最优解,但是不一定总能找到最优解,是一个不完备的算法,也不具有成本最优性,时间和空间复杂度为O(bm)

对于A*搜素,使用g(n)表示从初始节点到n节点的成本,使用g(n)+h(n)代替h(n)来决定下一次要扩展的节点。f(n)=g(n)+h(n)。如果每个节点的启发函数值都为0或都相同,那么就可以统一使用成本搜索算法

在A*搜索中,如果启发函数没有过高的估计到目标节点的成本,即当n是由m出发的最优路径cost(m,n)≥h(m),那么就可以接受这个启发函数。接受启发式函数表明此A*算法总是乐观的

假设m节点连接目标节点n,若g(n)≥g(m)+h(m)即两点之间预测值小于等于实际值,则启发函数是可接受的,如下图所示

4

假设某个步骤是从m节点到n节点,并且符合h(m)≤h(n)+cost(m,n),说明此启发函数具有一致性,也表明此启发函数是可接受的

可以用三角不等式来理解,两边之和大于第三边,如下图所示

2

由于cost(m,n)=g(n)-g(m),上式也可表示为h(m)≤h(n)+g(n)-g(m),即h(m)+g(m)≤h(n)+g(n)

对于迭代加深的A*搜索算法,结合了A*搜索算法以及DFS搜索算法,规定一个阈值c,当g(n)+h(n)≤c时采用A*搜索算法,g(n)+h(n)>c时使用DFS搜索算法

这里来讨论一些与搜索路径无关只关心问题的解的搜索算法

对于局部搜索算法(Local Search),从一个节点出发,之寻找与它相邻的节点,占用内存少,可以找到系统化算法无法解决的问题的一个合理的解,是一个非系统化的算法,可以用来解决纯优化问题(pure optimization problem),例如目标函数。在局部搜索中不一定总能找到问题的最优解,经常会找到问题的局部最优解,是一个不完备的算法

3

爬山搜索算法(Hill-Climbing),就是一种典型的局部搜索算法,也常被称为贪婪局部搜索算法

模拟退火算法(Simulated Annealing),由于得到的解可能不是最优解,所以也是一种不完备的算法。通过在局部概率性的跳出局部最优解而逐渐趋于问题的全局最优解

局部束搜索算法(Local Beam Search),是对局部搜索算法的一种改进算法,以多个节点出发,并行使用局部搜索算法寻找问题的解

遗传算法(Genetic Algorithm),与局部束算法相似,同样以多个节点出发,通过选择、杂交、突变来选择下一代子节点

Constraint Satisfaction Problem

约束满足问题,简称CSP

Definition

  • 变量集合:x1, x2, … xn
  • 每个变量的定义域:xi的定义域为Di
  • 满足的约束:c1, c2, … cn

一个约束通常涉及到单个或多个变量,用键值对<scope, rel>表示,其中scope为涉及到的变量集合,rel表示变量间的关系。目标是找到一个完备的满足所有约束的解。需要注意的是,变量可能是离散的也可能是连续的

Example

N-Queens

5

在现实生活中也常常会遇到约束满足问题,例如老师与班级的分配,课程时间安排,硬件配置,运输调度安排,工厂安排,电路布局,错误诊断等

Constraint Propagation

在约束满足问题问题中,当一个变量确定了一个合法值后,可能会影响其他变量的取值范围

节点一致性:当一个变量的定义域中的值全都满足问题所描述的单值约束时,就称其满足节点一致性

弧一致性:当一个变量的定义域中的值全都满足问题所描述的二元约束时,就称其满足弧一致性

Solving CSP

使用遗传方法可以解决CSP,用任何方法给一个没有赋值的节点赋值后,都会产生一个子节点,在扩展时应随时检查是否满足一致性

使用DFS可以解决CSP,在DFS的基础上,每次仅给一个节点赋值,并且在扩展时要随时检查是否满足一致性,则为回溯搜索算法

在回溯搜索算法中,需要思考下一次给哪一个节点赋值?赋定义域中哪一个值?能否预知不可避免的失败?能否利用问题的结构性?

过滤:监控未赋值变量取值范围的变化,去掉不好的选择

向前检查:当取值加入到已存在的分配当中时,若违反约束,则去掉这些取值。向前检查只能传递部分信息,并不能提前检测到所有的失败

在选择下一个将要赋值的节点时,应选择当前取值范围最小的节点

选择完节点后,在选择定义域中的值时,应选择其中受到约束最少的值,给其余节点留下更大的取值范围

Game Playing

Game

与搜索相似,很多游戏都是涉及到两个玩家,零和(分胜负,无平局)的,并且游戏状态是公开的

例如井字棋。还有一些不公开游戏状态的游戏,例如扑克牌等需要概率论或其他游戏理论

Mini-Max

6

其中上三角代表MAX,下三角代表MIN

7

其算法复杂性与DFS相似,时间复杂度为O(bm),空间复杂度为O(bm)

α-β Pruning

不需要查看每个节点,有些节点可根据当前的状态去掉

8

以上图为例

对于A节点来说,需要从子节点中选择最小值,即为3

对于B节点来说,同样需要从子节点中选择最小值,需要注意的是,因为B节点的子节点中包含2,说明B节点的值不可能比2大,即B节点的值一定比A节点的值要小。对于ROOT节点来说,需要找到子节点中的最大值,所以B节点的其他两个子节点就不需要再考虑了

剪枝后的结果如下图所示

9