搜索与人工智能

前言

第一：通过博弈树搜索和启发式搜索的例子

了解基于搜索的通用问题求解方法

第二：了解人工智能发展的历程和社会影响

第三：了解机器学习的基本思想和典型应用

第四：了解人工智能应用开发的基本模式

内容

1.博弈树与剪纸、

零和博弈，极大极小策略

博弈树与搜索，α与β剪枝

以及著名的计算机博弈的例子

2.启发式搜索

启发式函数，启发式搜索过程，

3.人工智能与机器学习

人工智能发展历程，专家系统，机器学习，神经网络与深度学习。

4.人工智能典型应用

包括在，工业，金融，农业，艺术等领域的应用以及人工智能的社会影响。

5.人工智能开发平台，包括人工智能开发的基本过程

基于MindSport的开发平台

我们求解问题的最基本的一种方法就是设计算法。比方说我们想求解两个数的最大公约数。我们会想到一种方法。就是叫辗转相除法。但是我们有一类问题，我们一下很难想出他的算法来，比方说我们在计算机界很有名的一类问题。就是叫NP Hard的问题?

这类问题到目前为止，我们还找不着一种多项式的算法。来有效的解决它。还有一类问题。

比方说博弈问题。涉及到双方的决策。所以从单方面的角度来讲。你很难设计出一种方法来，他一定能够获胜。那么像这类问题。我们叫非平凡问题，怎么求解呢。一种简单的思路。就是我们通过某种策略去试探各种可能。从而找到解决问题的方法。或者达到我们所需要的状态。那么这样的一种方法呢我们就叫搜索。搜索是我们人工智能早期的一种方法。包括到现在我们机器学习的很多方法。他的基本思路实际上也是一种搜索。这个专题要给大家介绍的内容。主要是包括这五个方面。

第一个，博弈树与剪枝。

第二个，启发式搜索。

第三个，人工智能与机器学习。

第四个，人工智能典型应用。

第五个，人工智能开发平台

那么这个专题的一个主要目标。我们是希望通过一些例子，来了解博弈搜索，启发式搜索的基本思想。从而了解基于搜索的问题求解的基本方法。另外一方面，了解人工智能发展的历程。以及他的社会影响。

第三个，了解机器学习的基本思想。和典型的应用。

第四个，了解人工智能开发的基本模式。

首先我们来谈谈第一个问题

第一个，博弈树与剪枝。

设有一个三行三列的棋盘，两个棋手轮流走步，往空格上摆一个自己的棋子，谁先使自己的棋子成三子一线为赢。

设MAX方的棋子用X标记，MIN方的棋子用O标记，并对顶MAX方先走步。

也就是井字棋

这个问题怎么解，就是零和博弈，就是指参与博弈的各方，在严格竞争下，一方的收益必然意味着另一方的损失，博弈各方的收益和损失相加总和永远为‘’零‘’。

也就是你死我活的一种博弈。

要么我赚了要么你亏了

还有剪刀锤子布，我们可以画一个收益矩阵。

可以观察到，三种决策效果是等同的，不存在严格的最优应对。

因为是三个随机的决策。他的效果是对称的。那好我们在看另外一个例子

可能存在最优应对。

先考虑最坏的情况。

左右手收益矩阵，存在都赚钱的情况

双方平衡点（鞍点），零和博弈的决策原理（极大极小策略Minimax Strategy）

在最坏可能的基础上做出最好的选择。

核心思想就是在最坏的情况的基础面上，去做出最好的选择。

博弈树与搜索

对于刚才这样的一个问题我们是用矩阵表示出来的，是一步的决策，那么这样的一个决策过程。我们也可以用树来进行表示。树怎么表示呢？就是决策的起点，假如说我们甲乙双方甲先做一个决策。

左手还是右手。那么乙也会决定左手还是右手。我们把这个图先以甲方为主作为起点，那么甲可能是出左手也可能出右手。那么甲方出左手，乙方有可能出左手，也可能出右手。所以我们整个就以甲方作为起点他的决策称为下一层的分支。然后乙方在这个基础上面，对于甲方的每一个决策，他在产生下面的分支。这就形成了我们所谓的加树。最起点的地方我们叫树根。最下面的地方叫树的叶子。有点像我们家的家谱树。一个老祖宗生了N个孩子。每个孩子又生了N个孩子。所以甲方做了左右两个选择。生了两个孩子。然后每一个乙方又可以做两个选择。所以就往下衍生。。所以这个我们叫做博弈树。那么对于刚才这样一个博弈树来讲，他的终局就是下面的叶节点，这里的值就是他的收益。

井字第一步就是三种状态

博弈目标：从初始状态（树根）出发，寻找一条“路径”到达能赢的状态。本质上就是一个搜索问题。

什么是搜索过程呢。就是树从上到下的搜索。

所以搜索的基础是遍历，对每个节点访问一次。搜索是在树遍历的基础上面的一种寻找最有利的状态的过程。

第一种方法，按层次遍历实际上是把二维结构变成一维序列化的过程。

树是一个二维的结构，而我们的遍历是一个一维的序列。

还有什么方法。按照深度遍历。?

二叉树：

就是有一个根节点，然后有左子树，右子树

左边也是个树，右边也是个树，怎么进行遍历

也是层次遍历，实际上是一种宽度优先的思路。

深度遍历。先遍历所有的左边，再遍历所有的右边，先左后右的顺序遍历。

根什么时候遍历。可以是一种信息的处理。可以是一种print打印出来。

前序遍历：根--左子树--右子树

中序遍历：左子树--根--右子树

后序遍历：左子树--右子树--根

遍历不只是看一下，它更变现为是一个信息处理的先后顺序。

所以简单来讲就是print。

这种顺序是对整个树的顺序

博弈树搜索与α-β+剪枝

如果19*19的一个围棋格子，会遍历一个天文数字10^170。比宇宙的粒子还要多10^80。

解决博弈的核心思路，

第一个，要设计一个棋局的评价函数。对棋局进行（节点）进行评价，供决策分析用。

算出棋局对我的效益。

第二个：有限深度搜索。采用有限深度的搜索方法，往前探索可能的棋局。形成max和min交替决策的博弈树。不可能把整个博弈树都找出来，各往前看一两步来找出有限的搜索树。最优策略计算。按照极大极小策略自底往上计算博弈树中各节点的评价值。

从而算出我当前往那边走比较好。

那么怎么来进行有效的一种计算呢？

先知道各个子树，子节点的评价值，再算出我的评价值。就是极大值或者极小值。

那么如何给井字棋写一个函数

如果第一步下中间。

f(P)=6-4=2

概率最小值，根选最大值

剪枝：

Max层节点的α值

取当前子节点中的最大倒推值作为它倒推值的下界。

Min层节点的β值：

取当前子节点中国的最小倒推值作为它倒推值的上界。比较小就直接剪掉、

β剪枝就是反过来，比较。

就是说第一个节点算出一个数。第二个节点往下的第一个节点直接不匹配，后面的节点全部剪掉。

边搜索生成结点，边计算结点倒推值。：α值??β值

α剪枝：任何min层结点n的β值小于或等于它先辈节点的α值。则n以下的分支可以停止搜索。并令节点n的倒推值为β

β剪枝：任何max层结点n的α值大于或等于它先辈节点的β值，则n以下的分支可停止搜索。并令节点n的倒推值为α。

α-β剪枝可将搜索减少到（N^1/2）个结点，N是博弈树结点规模。

著名计算机博弈

西洋跳棋（Checkers）AI程序

ai击败了当时全美最强的西洋棋选手之一的尼雷。

核心技术是α-β剪枝搜索+自我对弈来学习评价函数。

国际象棋。IBM深蓝战胜了卡斯帕罗夫。

为什么时隔35年才再次成功，因为硬件的限制，算力不够。

他们是为了显示深蓝计算机的性能。

AIphaGo战胜围棋世界冠军

数据量依然很大，这个计算机采用了深度神经网络来训练两个模型。

一个叫策略网络。一个叫价值网络。

价值网络用来判断他的围棋的棋局的价值。

与评价函数是一样的道理，策略网络是干啥呢。我们搜索的时候用α-β剪枝

那么AI用的是蒙特卡洛搜索的策略。

是一种按照概率随机选择的策略。。学习了3000万个棋局

还用到了一种方法叫强化学习。

2017年AIphaGo Zero无监督学习，不需要人类经验，击溃AIphaGo100:0.

自己和自己下。结果反馈强化评估值

根据环境的反馈来获得最后的一种评价值。

然后来修正前面的一系列动作。

后者一系列决策的一个评估值。

三天就达到了Go的水平。

18年通杀

19年运用到基因工程

启发式搜索

之前都是博弈的对手的环境

比如一个重拍九宫的问题

给你一个初始状态，如何找到目标状态

这种状态实际上蕴含了一种关系。我们可以用图的形式来表示。

所谓图他的要素就是两个东西。

一个图当中有节点。然后节点和节点之间有边的连接，

边代表什么意思呢

在我们这里就代表了如果我这个状态通过移动一个棋子可以变成你那个状态。我们之间就连城一条边。、

所以这样的一个问题

他背后实际上就蕴含了一个状态图

那同样类似问题来讲，比方说我们互联网里面有很多网页。

每个网页他都有链接。那么我们是不是可以这么理解每个网页是一个节点。

他的链接就形成了一条边。所以从我这个网页这个节点，就连到了你那个节点。所以互联网的网页之间，就变成了一个巨大的图。那我们搜索引擎干什么，就是要在这个图里面去找到我需要的网页。所以搜索引擎里面核心的问题也是图搜索的问题。

那么对于我们刚才的问题来讲，他就变成了我们有一个巨大的状态的空间。状态之间有关联，那么我的问题如何从初始状态出发。经过一系列的路径来达到目标状态。

所以这是另外一类搜索问题。

那么这种搜索问题这么解决，一种最简单的解决方法就是用宽度优先的方法。

因为我们要找出最佳的路径。也就是锁我们用尽量少的移动次数来达到目标状态所以这是一个要求解最优的问题。比如顶上有一个初始状态。但是宽度优先搜索是一种盲目搜索。

效率及其低下。

那么我们设计一个评价函数对我们当前这个节点下面所有可能的节点，算一算分数是多少。

就是每次都扩展，不是一层一层的扩展而是每次选最小值的节点往下扩展。，这就是启发式搜索的一个基本思想方法。为什么叫启发式搜索，因为我们需要设计一个函数,这个函数里面包含这个问题的某种特征的一种值。它告诉我往那边走比较好。启发式的信息，那么这个评价函数，一般的设计方法，就是由两个值构成的。这个评价函数叫f（n）是由g（n）跟h（n）构成的。g（n）是我们假定搜索到了某个地方了（节点n），表示从初始节点s到当前节点n的路径代价。

h（n）：表示从节点n到目标节点g的预估路径代价。又叫启发式函数。

f（n）：表示从s经过n到g的路径代价估计值。

评价函数f（n）：f（n）=g（n）+h（n）

搜索方法，利用评价函数f（n）值决定扩展节点顺序。优先扩展当前f（n）值最小的节点

n。

如果h（n）是零的话，那就意味着我们的评价函数完全靠g（n）

这样的搜索其实又退回到宽度搜索。一层一层来。

如果h（n）取得非常大，比g（n）大得多。

启发式搜索：利用问题的特征，设计评估结点价值的启发式函数，可以省略大量无谓的搜索路径。提高了效率。

A*算法：启发式函数h（n）满足特定的条件，可以保证能够获得最优解。

每次扩展的时候，只扩展当前也节点里面。

最下面的节点里面。评价值最少的那个节点进行扩展。

这样的方法是不是能保证我找到我所需要的最优解。

当然不能，但是如果启发式函数满足一定的条件。

什么条件？就是评估的值比他实际的最优值要小。

我就能找到最优解。

典型应用：

优化问题（调度，布局，路线规划）

应用类似思路的算法。蚁群算法。遗传算法。

人工智能发展的一些历程

1956年8月起源

模拟人工智能的计算。启发式对复杂的问题难以有好的效果。

人类是解决问题的，是采用了一个很好地策略。

我们人类解决问题很大程度上依赖于我们常年积累的经验。

这个经验的表现形式就是知识。

专家系统，就是把人类的经验变成知识。然后在知识的基础上进行不断的推演。

来产生我们新的结论。也带来了一些核心的问题。瓶颈问题。知识获取的瓶颈问题。

就是很多经验，专家知道怎么做事情。但是你要他表述出来它背后所蕴含的知识跟经验，他讲不清楚。所以这个时候专家系统也陷入了困境。既然专家知识讲不清楚。那你能做事情你就给我多做几遍。我就在旁边看，我就慢慢的从专家的经验中去总结去提炼。这就导致了一个新的技术。叫机器学习的产生。机器学习一个很重要的思路就是从过去的经验当中去总结。去提炼我们的一些知识跟经验。

机器学习的基础，一个要求他要从例子当中归纳总结。那么如何表述这个例子。也就是我们用什么特征来表述这个例子。那就很关键。所以特征的抽取成了机器学习的一个关键。如果你找不准特征。这机器学习的效果就不是很好。那有没有可能让计算机自己去找特征，深度学习。从大量的例子当中去总结去提炼我们所需要的特征。

那么这就使人工智能得到了快速的发展。

从专家的一些例子当中就可以总结。

所以是的人工智能的应用变得更加的方便。

七个方面：

1.自然语言的理解。

机器翻译，语音识别。（让计算机理解我们的文章，让计算机听懂我们的声音）

2.计算机视觉

像人脸识别（模式识别的任务）

3机器人和智能控制（外形上面模仿人的行为动作）

4机器定理证明（数学定理的机械化证明）

5专家系统：利用我们人类所掌握的经验知识，来构造更加复杂，更加智能的系统。（知识工程）

6博弈：下棋问题：怎么样让我们计算机跟人下棋。

7机器学习。

专家系统：

核心是两个部分：1.知识库2.推理机

知识库它代表了我们人类经验的一种积累。

用规则的形式。推理机就是在知识上面不断的推导，产生新的结论。

那么计算机为什么能够进行推理。

关键就是要讲清楚规则，然后把规则列出来。

构建常识系统cyc，目前还很难。

机器学习

机器学习是研究如何从经验和数据中，获取新的知识或技能，使系统做些适应性的变化。

学习的类型：

归纳学习，分析学习，发现学习，遗传学习，连接学习，统计学习。

机器学习很重要的就是特征抽取，你用什么特征来表述这个例子还有一个叫分析学习。就是说我给你一个例子。

你根据以往的经验对这个例子进行解读。从而总结出一般规律来。

发现学习：我给你一些数据。天体的数据，比方说椭圆形的一种运行轨迹。有长轴，有短轴。运转的周期告诉你。你来看看他有什么规律。半长轴的三次方，跟周期的平方，是有线性关系。这就是开普勒第三定律。

遗传和连接是从自然界中的一些现象来进行学习。

统计学习：就是为我们的数据，从概率数理统计的角度来构造一些模型。

所谓学习就是你在某些地方指点它，它自己从中获得一些知识。自己进行领悟。那么我到底要告诉它什么东西。所以这里面就有几种学习的方式。

一个叫

监督学习

比如说有好多照片，植物的照片，让你识别什么是玫瑰花。什么是月季，什么是菊花。告诉你这些分类信息，然后你再去学习。这个叫监督学习。

无监督学习

给你一堆东西，什么都不告诉你，那么这种常见的就是聚类。比如告诉你一些人的数据。然后你把它能分为几个人群。聚类的一个核心要点。把我们的对象都当成空间中的某些点。n维空间当中的某些点。所谓聚类就是在这些n维空间当中的这些点。把它划分成若干块，然后跟别人距离比较远所以这就是典型的无监督学习。是一种聚类。

强化学习

就是我人类告诉你一些信息。不是每一个数据我告诉你分类。有可能是你做一系列的动作。也就是说一系列的决策之后。我告诉你对还是不对。我告诉你你这一系列的决策的效果是怎么样。

那么我们的目的是什么，想学我的每一个动作。在什么场景下去做比较好，或者说遇到了一个场景。我到底这n个动作里面。哪个动作比较好。但是我给你的信息不是你每个动作我就给你评价。

而是你做了若干动作之后我再给你评价。然后你自己把这些反馈信息回到路上的每一个决策步骤当中。这种学习方法就是强化学习。所以有不同的学习形式。

那么机器学习应用场景很多

1.数据挖掘：发现数据之间的关系（超市里啤酒与尿布）

2.计算机视觉：看懂世界（人脸识别，植物识别）

3.自然语言处理：看懂文字，听懂语言。

4，机器人决策：具有决策和行动能力。

在大数据的场景中，去发现数据之间的一种关系。

连接学习（神经网络）

那么下面简单给大家解释一下。典型的方法神经网络。神经网络（Neural Network）:由节点（或称神经元）以及节点之间的互相联接所构成，分输入层，隐含层（若干），输出层

每个节点对应有个特定的输出函数，称为激励函数（activation function）

前后层两个节点的连接对应有个加权值Wij，称之为权重。

核心：神经元，神经元之间的连接

一般神经网络是分若干层的。神经网络本质上来讲是想做一个映射。是想实现一个函数计算，给你一个x能够给我对应的产生一个y

损失函数：度量模型预测的好坏，即衡量预测值（Y）与实际值的差异程度。

你怎么衡量我算出来的结果跟你的目标有差距。

参数优化：反向传播，调整Wij

有差距，那怎么去调整呢？使得这个差距最小化。这里可以用梯度递降法。

学习过程：通过不断训练（迭代），逼近函数关系F(X)->Y.

每训练一次就计算一下跟我目标的差距是多少。然后根据这个差距去调整参数。所以这整个过程，就是不断训练的过程。也就不断迭代的过程。来逐步的逼近我们所期望的哪个函数。

需要输入的是最原始的数据。逐步去总结他的特征。他的规律出来，而不需要你一开始就告诉我的x就是某种特征。

大量的训练产生一个模型，然后有了这个模型，就可以用了。后面就是推断过程。

人工智能典型的应用

在工业制造领域它涉及到设计生产。物流。销售，服务等

在设计环节，我们可以通过大量的数据跟以往的产品的设计的案例。辅助我们进行新产品的设计。

使得我们设计的过程更加的自动化。

甚至我们可以积累某些产品库。

宝库一些知识库。提出一个概念性的东西。你马上从原有的一些产品。成功的一些案例里面提取出相关的要素出来。加速产品的设计的过程。

1，数据驱动的产品优化。

2，工业设计优化

3，产品调试过程优化。

4，用户需求预测

5，基于只是图谱的智能

6，设计模块

生产环节

1，视觉分拣

2，视觉检测

3，生产参数的自动优化。

4，生产安全监控

5，生产人力优化与工单优化

6，生产预测。

自动的发现哪些产品是不合格的，能够自动发现我们生产过程的某些工艺。他的参数可以进一步优化。

物流环节

1，仓储自主优化

2，基于视觉身份认证的安全管理。

3，仓库选址优化

4，自动物品归类拣选

5，运输成本的预测

6，基于预测的智能库存管理

7，物流路线的优化。

实现仓储的优化，节约我们的成本来实现很好地运输的物流的调度。

销售环节

1，智能营销

2，销量预测驱动的智能生产优化

3，舆情监控

4，产品智能定价

5，广告精准投放

6，促销时机决策

我能知道我的客户他喜欢什么。来促进我的营销，我能通过用户对这些产品的反馈。来捕捉用户喜欢我这个产品的哪一些优点。他换发现用户希望我们的产品怎么进行改进。

服务环节

1，整机的预测性维护

2，零部件的预测性维修

3，远程运维

4，智能客服

比如新能源汽车发现用了一段时间之后，电池不好用了。所以在整个制造过程当中。

最广的应用就是产品检验。我们在生产过程当中。我们的产品检验很多是靠人来目检验的。

那人的目检，他的这种劳动强度是非常大的。比方说在动力电池的生产过程中。一个动力电池是有好多电芯所构成的。，那么电芯实际上我们把正极材料和负极材料涂在两个模上。然后把两个模加起来卷起来。然后注上电解液。然后电焊封口

那么这个电芯出品的时候，我们就要看电芯的焊点有没有问题。

扣子焊点覆盖面大不大。有没有针孔等等这个问题。

那么在一系列的功能里

他的劳动强度很大

他基本两秒钟要判别，他这个电芯合格不合格。

就拿起来滴答，拿走。

劳动强度很大，没有办法八个小时工作，可能两个小时就要轮岗了。

那么如果有人工智能方法。它做自动检验。那就提高我们的效率。那么这个图给大家显示的是膜生产的过程当中。如果有缺陷。类似这里所列的这些缺陷。那么它将来在用的过程当中。电解液可能就漏出来了。那么就会发生燃烧，所以就在生产过程中，要发现这样一个问题。那么从计算机图像处理的角度来讲。这样的一个问题不难发现。难点就在生产过程当中、。

生产的速度妇产块，一般速度达到2m/s。

所以拍了照传到云，在穿回来就赶不上了所以在工位上就要装一个高性能的计算机。当场识别，当场控制。

在金融领域

应用业务：

1，支付

2，个人信贷

3，企业信贷

4，财富管理

5，资产管理

6，保险

痛点问题

1，安全

2，风控

3，获客

4.效率。

典型应用场景

1，只能投顾

2，风险防控

3，量化交易

4，流失预测

5，智能客服

6，舆情分析

7，流量自动化

风险控制分为四个流程

数据采集。行动建模，用户画像，风险核定

网络行为数据

第三方合作机构数据

公开数据

授权数据

用户交易数据

用户偏好数据

其他数据

文本挖掘

机器学习

聚类分析

自然语言处理

预测算法

目的是要找出这个客户，他的一个最基本的特征这就是所谓的用户画像，我通过数据，我通过计算机模型。大概就猜出来了，你这个人是很有钱，高消费，花钱谨慎。

基本信息

购买能力

消费习惯

消费倾向

社交网络

行为特征

知道你适合不适合这个业务

做风险核定

生成对抗网络

相互对抗并持续改进的两个网络模型--生成器。判别器。

aiva创作音乐人工智能

图灵测试

：就是测试机器和人一样聪明

你在这头拉一个布帘子，布帘子的那头可能是人，可能是机器，你搞不清楚对方是人还是计算机

验证码就是为了防止计算机冒充人

最大的冲击就是人力资源，因为人工智能的广泛采用，很多岗位会被人工智能替代

基金经理，交易员，会计、

律师助理：零售售货员。仓库保管员，专职司机。快递员。呼叫中心、工厂装配工人

同声翻译，建筑工人。

法律问题：

数据隐私保护。

人工智能算法歧视。

智能系统的责任

人工智能作品的知识产权归属。

人工智能的法律人格

人工智能与劳动者劳动权保障

信息垄断

人工智能的开发

确定目标

训练一个模型可以像人一样识别花卉的种类。

准备数据：通过各种渠道准备数据采集（开源网站，手动收集）

依赖的三要素，数据算力算法

那么我们要准备很多数据

训练模型

利用开发框架（MindSpore 。Pythorch。TensorFlow。飞浆等）

便捷构建神经网络，并利用收集到的数据训练网络。

评估模型：用测试集样本（不参与训练过程）评估模型表现

部署模型：将模型文件部署在任意设备上，通过被调用实现花卉识别的功能。

本地PC开发

1，小数据，小模型，或者代码验证阶段

2，存储空间取决于本地硬盘大小

3，算力基于GPU性能

4，运行环境自己搭建

5，所有模型自己搭建

6，部署过程复杂，需要自己搭建软硬件平台。

云平台开发

1，大数据，大模型情况下的首选

2，海量数据存储空间

3，更强算力支持。

4，云端提供配置好的环境

5，云端提供与之模型，可以直接使用

6，云端提供部署环境，生成接口以便调用。