人工智能原理学习笔记

人工智能原理笔记

第一章：绪论

---

什么是人工智能

• 左侧的定义根据与人类表现的逼真度来衡量成功，而右侧的定义依靠一个称为合理性(rationality)的理性的表现量来衡量。
• 一个系统若能基于已知条件“正确行事”则它是合理的。

像人一样行动–图灵测试的途径

计算机需要具有的能力：

• 自然语言处理(natural language processing)
• 知识表示(knowledge representation)
• 自动推理(automated reasoning)
• 机器学习(machine learning)
• 计算机视觉(computer vision)
• 机器人学(robotics)

第二章：智能Agent

---

2.1 Agent和环境

Agent通过传感器感知环境并通过执行器堆所处环境产生影响。

• 感知：任何给定时刻Agent的感知输入
• 感知序列：该Agent所收到的所有输入数据的完整历史

Agent函数描述了Agent的行为，将任意给定感知序列映射为行动

2.2 好的行为：理性的概念

理性：

• 定义成功标准的性能度量
• Agent堆环境的先验知识
• Agent可以完成的行动
• Agent截止到此时的感知序列

理性Agent：对每一个可能的感知序列，根据已知的感知序列提供的证据和Agent具有的先验知识，理性Agent应该选择能使其性能度量最大化的行动。

• 理性是使期望的性能最大化，而完美是使实际的性能最大化。

• 信息收集是理性的重要部分

• Agent依赖于设计人员的先验知识而不是它自身的感知信息，这种情况我们说该Agent缺乏自主性。

2.3 环境的性质

任务环境： 性能度量(Performance)、环境(Environment)、执行器(Actuators)、传感器(Sensors)。

性质：

• 完全可观察的：Agent传感器在每个时间点上都能获取环境的完整状态
• 有效完全可观察：传感器能检测所有与行动决策相关的信息
• 无法观察：Agent没有传感器
• 单Agent与多Agent
• 确定的与随机的：如果环境的下一个状态完全取决于当前状态和Agent执行的动作，那么该环境是确定的；否则它是随机的
• 片段式与延续式：在片段式任务环境中，Agent的经历被分成一个个原子片段，每个片段中Agent感知信息并完成单个行动。下一个片段不依赖于以前的片段中采取的行动。在延续式环境中，当前的决策会影响到所有未来的决策。
• 静态的与动态的：如果环境在Agent计算的时候会变化，那么是动态的，否则是静态的。
• 离散的与连续的。
• 已知的与未知的：指的是Agent(或设计人员)的知识状态。在已知环境中，所有行动的后果(如果环境是随机的，则是指后果的概率)是给定的。若环境是位置的，Agent需要学习环境是如何工作的，以便做出好的决策。

2.4 Agent的结构

AI的任务是设计Agent程序，实现把感知信息映射到行动的Agent函数。假设该程序要在某个具备物理传感器和执行器的计算装置上运行–称为体系结构。

###### Agent程序

• 简单反射Agent：基于当前的感知选择行动，不关注感知历史。
• 基于模型的反射Agent
  • 模型：关于“世界如何运转”的知识。
• 基于目标的Agent
  • 把目标信息与模型相结合，以选择能达到目标的行动。
  • 通过搜索和规划实现。
• 基于效用的Agent
  • 在基于目标的前提下，选择最优的路径。

第三章：通过搜索进行问题求解

---

3.1 问题求解Agent

​**形式化、搜索、执行 **

• 基于当前的情形和Agent的性能度量进行目标形式化(goal formulation)是问题求解的第一步。

• 问题形式化(problem formulation)：是在给定目标下确定需要考虑哪些行动和状态的过程。

• 为达到目标，寻找这样的行动序列的过程被称为搜索。

  • 搜索算法的输入是问题，输出是问题的解，以行动序列的形式返回问题的解。解一旦被找到，便会被付诸实施，被称为执行阶段。

良定义的问题及解：

• Agent 的初始状态

• 描述Agent的可能行动：给定一个特殊状态s，ACTIONS(s)返回在状态s下可以执行的动作集合

• 对每个行动的描述：正式的名称是转移模型，用函数RESULT(s,a)描述：在状态s下执行行动a后达到的状态(后继状态)。

  • RESULT(In(Arad), Go(Zerind)) = In(Zerind)

• 初始状态In(Arad)、行动、转移模型定义了问题的状态空间。

• 目标测试：确定给定的状态是不是目标状态。

• 路径耗散函数：为每条路径赋的一个耗散值。

3.3 通过搜索求解

​ 可能的行动序列从搜索树中根节点的初始状态出发，连线表示行动，结点对应问题的状态空间中的状态。

• 边缘：在任一给定时间点，所有待扩展的叶节点的集合。
• 搜索策略：如何选择将要扩展的状态。

搜索算法基础：

• n.STATE：对应状态空间中的状态
• n.PARENT：父结点
• n.ACTION：父结点生成该结点时所采取的行动
• n.PATH-COST：代价，一般用g(n)表示，指从初始状态到达该结点的路径消耗。
• 结点是用来表示搜索树的数据结构，状态则对应于世界的一个配置情况。 结点是一种由PARENT指针定义的特定路径，但状态不是。

3.4 无信息搜索策略(blind-search)

1. **宽度优先搜索(breadth-first search) **

• 简单搜索策略，先扩展根节点，接着扩展根节点的所有后继，然后再扩展它们的后继，依此类推。一般地，在下一层的任何结点扩展之前，搜索树上本层深度的所有结点都应该已经扩展过。

  每次总是扩展深度最浅的结点。

• 假设搜索一致树(uniform tree) 的状态空间中每个状态都有b个后继。搜索树的根结点生成第一层的b个子结点，每个子结点又生成b个子结点，第二层则有b个结点。第三层则得到b个结点。假设解的深度为d。在最坏的情况下，结点总数为：

  ​b + b + b + … + b = O(b) – 时间复杂度

  空间按复杂度：O(b)

1. 一致代价搜索(uniform-cost search)

   扩展的是路径消耗g(n)最小的结点n。通过将边缘结点集组织成按g值排序的队列来实现。

   一致代价搜索与宽度优先搜索有两个不同：

   • 目标检测应用于结点被选择扩展时，而不是在结点生成的时候进行。
   • 如果边缘中的结点有更好的路径到达该结点那么会引入一个测试

   一致代价搜索堆解路径的步数并不关心，只关心路径总代价。

2. 深度优先搜索(depth-first search)

   总是扩展搜索树当前边缘结点集中最深的结点。

   深度优先搜索算法的效率严重依赖于使用的图搜索还是树搜索。

   时间复杂度：O(b) m是指任一结点的最大深度。

   空间复杂度：对于图搜索，深度优先搜索只需要存储一条从根结点到叶结点的路径，以及该路径上每个结点的所有未被扩展的兄弟结点即可。一旦一个结点被扩展，当它的所有后代都被探索过后该结点就从内存中删除。所以分支因子为b,最大深度为m，只需存储O(bm)个结点。

3. 深度受限搜索(depth-limited search)

   在无限状态空间深度优先搜索会失败，可以通过设置界限l来避免。深度为l的结点被当做没有后继对待。

   深度受限搜索解决了无穷路径的问题，但是如果选了 l < d，即，最浅的目标结点的深度超过了深度限制，这种搜索算法是不完备的。

   时间复杂度为O(b)，空间复杂度为O(bl)。

4. 迭代加深的深度优先搜索(iterative deepening search)

   迭代加深的深度优先搜索(iterative deepening search)是一种常用策略，它常和深度优先搜索结合使用来确定最好的深度界限。做法是不断地增大深度限制——首先为0，接着为1，然后为2，依此类推——直到找到目标。

   空间复杂度为: O(bd)

   时间复杂度为：O(b)——与宽度优先搜索相近。

5. 双向搜索(bidirectional search)

   同时运行2个搜索，一个从初始状态向前搜索搜索，同时另一个从目标状态向后搜索，希望它们在中间某点相遇，此时搜索终止。

   理由是：b + b << b

   时间复杂度与空间复杂度都为：O(b)

3.5 有信息(启发式)的搜索策略

**有信息搜索(informed search)**策略：使用问题本身的定义之外的特定知识。

最佳优先搜索(best-first search) 是一般TREE-SEARCH和GRAPH-SEARCH算法的一个实例，结点是基于**评价函数f(n)**值被选择扩展的。

大多数最佳优先搜索算法的f由**启发函数(heuristic function)**构成：

​h(n) = 结点 n 到目标结点的最小代价路径的代价估计值

1. **贪婪最佳优先搜索 **

   **贪婪最佳优先搜索(greedy best-first search)**试图扩展离目标最近的结点。它只用启发式信息，即 f(n) = h(n)。

   贪婪最佳优先搜索与深度优先搜索类似，即使是有限状态空间，它也是不完备的。

2. A搜索：缩小总评估代价

   它对结点的评估结合了g(n)，即到达此结点已经花费的代价，和h(n)，从该结点到目标结点所花代价：

假设启发式函数h(n)满足特定的条件，A搜索既是完备的也是最优的。

• 保证最优的条件：可采纳性和一致性

  • h(n)是一个可采纳启发式—指它从不会过高估计到达目标的代价。

  • 一致性(单调性)：如果对于每个结点n和通过任一行动a生成的n的每个后继结点n，从结点n到达目标的估计代价不大于从n到n的单步代价与从n到达目标的估计代价之和：

    ​h(n) <= c(n, a, n) + h(n)

A算法的最优性

​如果h(n)是可采纳的，那么A的树搜索版本是最优的；如果h(n)是一致的，那么图搜索的A算法是最优的。

​对于一致代价搜索(A*搜索中令h(n) = 0 )，同心带是以起始状态为圆心的“圆”。如果采用更精确的启发式，同心带将向目标节点方向拉伸，并在最优解路径的周围收敛变窄。若C*是最优解路径的代价值，可以得到：

• A*算法扩展的是所有f(n) < C*的结点。
• A*算法在扩展目标结点前可能会扩展一些正好处于“目标等值线”(f(n) = C*)上的结点。

完备性要求代价小于等于C*的结点都是有穷的，前提条件是每步代价超过e并且b是又穷的。

A*算法不会扩展f(n)>C*的结点。

剪枝：无需检验就直接把他们从考虑中排除。

1. 存储受限的启发式搜索

   • 迭代加深A*算法(IDA*)，IDA*与典型的迭代加深算法的主要区别是所用的截断值是f代价(g+h)，而不是搜索深度。每次迭代截断值取超过上一次迭代截断值结点中最小的f代价值。

   • 递归最佳优先搜索(RBFS) ，是一个简单的递归算法，只使用西安行的存储空间，与递归深度优先搜类似。但它不会不确定地沿着当前路径继续，它用变量f_limit跟踪记录从当前结点的祖先可得到的最佳可选路径的f值，如果结点超过这个限制，将回到可选路径上。递归回溯对当前的每个结点用其子结点的最佳f值代替其f值。

     ​RBFS算法有时比IDA*算法效率高，但是它同样需要重复生成大量结点。

   IDA*和RBFS的问题在于它们使用的内存过于小了。在两次迭代之间，IDA*只保留一个数字：当前的f代价界限值。RBFS在内存中保留的信息多一些，但也只用到线性空间。

第五章 对抗搜索

---

5.1 博弈

在多Agent环境中， 每个Agent的目标之间是有冲突的，这就引出了对抗搜索的问题，称为博弈。

在人工智能的“博弈”称为有完整信息的、确定性的、轮流行动的、两个游戏者的零和游戏。

零和博弈是指在同样的棋局实例中所有人的总收益都一样的情况。

初始状态、ACTIONS函数、和RESULT函数定义了游戏的博弈树，其结点是状态，边是移动。

5.2 博弈中的优化决策

给定一颗博弈树，最优策略可以通过检查每个结点的极小极大值来决定，记为MINMAX(n)。假设2个游戏者始终按照最优策略行棋，那么结点的极小极大值就是对应状态的效用值。显然，终止状态的极小极大值是他的效用值自身。MAX喜欢移动到极大值状态，MIN喜欢移动到有极小值的状态。

1. 绩效极大算法

​使用了简单的递归算法计算每个后继的极小极大值，直接实现上面定义的公式。递归算法自上而下一直前进到树的叶结点，然后随着递归回溯通过搜索树吧极小极大值回传。

​极小极大算法对博弈树执行完整的深度优先探索。如果树的最大深度是m，每个结点合法的行棋有b个，那么极小极大算法的时间复杂度是O(b)。一次性生成所有后继结点的算法，空间复杂度是O(bm)，二每次生成一个后记的算法，空间复杂度是O(m)。

2. a-b剪枝

​如图所示，每一结点上标出了可能的取值范围。

• B下面的第一个叶结点值是3，因此作为MIN结点的B值最多为3。
• B下面第二个叶节点值为12，MIN不会选这个，B依然为3 。
• B下面第三个叶节点为8；此时已经观察了B的所有后继，所以B值为3。现在可以推断根节点的值至少为3，因为MAX在根节点有值为3的后继。
• C下面的第一个叶结点值为2，因此C这个MIN结点的值最多为2，不过已经知道B的值是3，MAX不会选择C。这是不会再考虑C的其他后继，这就是a-b剪枝的实例。
• D下面的第一个叶结点为14，所以D的值至多为14，比MAX的最佳选择3要大，所以继续探索D。
• D的第二个后继结点为5，继续探索，第三个后继值为2，所以在D中，MIN会选择2，D值为2。
• 最终MAX在根节点的抉择是走到值为3的B结点。

注意：极小极大搜索是深度优先的，所以任何时候只需考虑树中某条单一路径上的结点。

​a = 到目前为止路径上发现的MAX的最佳选择(极大值)。

​b = 到目前为止路径上发现的MIN的最佳选择(极小值)。

第六章 约束满足问题

---

本章讨论的是如何更有效的求解更多种类的问题。使用成分表示来描述状态：即一组变量，每个变量有自己的值。当每个变量都有自己复制的同时满足的所有关于变量的约束时，问题就得到了解决。这类问题称为约束性满足问题，简称CSP。

第18章 样例学习

---

本章首先给出各类学习形式的概述，在第3节描述决策树学习，接下来结束奥学习的理论分析：线性模型、非线性模型(神经网络)、非参数模型和支持向量机。

1. 学习形式

​Agent任何部件的性能都可通过从数据中进行学习来改进。改进机器改进所有的技术依赖于四个主要因素：

• 要改进哪一个部件；

• Agent具备什么杨的预备知识；

• 数据和部件使用什么样的表示法；

• 对学习可用的反馈是什么。

  表示法和先验知识：

  要素化表示法：属性值向量，输出的是连续数字值或是离散值。

  归纳学习：从特定“输入-输出”对学习通用函数或规则。

  分析或演绎学习：从已知通用规则走线被其逻辑蕴含的新规则，由于有助于更高效的处理，这种规则是有用的。

  用于学习的反馈：

  无监督学习：在不提供显示反馈的情况下，Agent学习输入中的模式。

  ​最常见的无监督学习任务是聚类：在输入样例中发行有用的类集。

  强化学习：Agent在强化序列——奖赏和惩罚组合的序列——中学习。

  ​奖惩之前的哪些动作需要为结果负主要责任。

  监督学习：Agent观察某些”输入-输出“对，学习从输入到输出的映射函数。

  ​在半监督学习中，给定少数标注样例，而要充分利用大量未标注样例。

2. 监督学习

• 监督学习的任务是:

​给定由N个”输入-输出“对样例组成的训练集：

​(x,y),(x,y),…,( x , y )

​其中，每个 y 由未知函数 y = f(x) 生成。

​生成一个函数h，它逼近真实函数f。

• 函数h是一个假说，学习是一个搜索过程，它在可能假说空间寻找一个不仅在训练集上，而且在新样例里上具有高精度的假说。为了测量假说的精确度，一般给学习系统一个由样例组成的测试集，它不同于训练集。所谓一个假说泛化的好，是指它能正确预测新样例的y值。

• 当输出y的值集是有限集合时，学习问题称为分类，若值集仅含2个元素，称为bool或二元分类。

• 若假设空间包含真实函数，学习问题是可实现的。但由于真实函数未知，一个给定的学习问题是否是可实现的不总是可判定的。

• 通过选择在给定数据下具有最大可能性的假说h*，能够实现监督学习。 h*的定义如下：

  • h* = arg max P( h | data )

  由贝叶斯公式，上式等价于：

  • h* = arg max P( data | h )P(h)

3. 学习决策树

3.1 基本流程

​决策树归纳是一类最简单也最成功的机器学习形式。

• 一般的，一颗决策树包含一个根结点、若干个内部结点和若个叶结点；叶结点对于也决策结果，其他每个结点则对应于一个属性测试；每个结点包含的样本集合根据属性测试的结构被划分到子结点中；根节点包含样本全集。
• 从根结点到每个叶结点的路径对应了一个判定测试序列。
• 决策树学习的目的是为了产生一颗泛化能力强，即处理未见实例能力强的决策树，其基本流程遵循简单而直观的“分而治之”(divide-and-conquer)策略。
  
• 显然决策树的生成是一个递归过程，在决策树基本算法中，有3中情况会使递归返回：
  • 1. 当前结点包含的样本权属于同一类别，无需划分；
    2. 当前属性集为空，或所有样本在所有属性上取值相同，无法划分；
    3. 当前结点包含的样本集为空，不能划分。
  • 在第2种情形下，把当前结点标记为叶结点，并将其类别设定为该结点所含样本最多的类别；在第3中情况，同样把当且结点标记为叶结点，但将其类别设定为其父结点所含样本最多的类别。
  • 情况2是在利用当前结点的后验分布(后剪枝)，而情形3是把父结点的样本分布作为当前结点的先验分布(预剪枝)。

3.2 划分选择

​由算法图可看出，决策树学习的关键是第8行，即如何选择最优划分属性。一般来说，随着划分过程的不断进行，我们希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的“纯度”(purity)越来越高。

信息增益

• “信息熵”(information entropy)是度量样本集合纯度最常用的一种指标。
• 假定当前样本集合D中第k类样本所占的比例为p(k= 1, 2, …, |y|)，则D的信息熵定义为：

Ent(D)=−i=1∑∣y∣​pk​log2​pk​(4.1)

​Ent(D)的值越小，则D的纯度越高。最小值为0，最大值为log|y|。

• 假定离散属性a有V个可能的取值{a,a,…,a }，若使用a对样本集D进行划分，则会产生V个分支结点，其中第V个分支结点包含了D中所有在属性a上取值为a的样本，记为D 。
• 信息增益为：

Gain(D,a)=Ent(D)−v=1∑V​∣D∣∣Dv∣​Ent(Dv)(4.2)

​一般来说，信息增益越大，则意味着使用属性a来进行划分所获得的“纯度提升”越大。因此我们可用信息增益来进行决策树的划分属性选择。

增益率

• 信息增益准则对可取值数目较多的属性有所偏好，为减少这种偏好可能带来的不利影响。于是使用“增益率”(gain ratio)来选择最有划分属性。
• 增益率定义为：

Gain_ratio(D,a)=IV(a)Gain(D,a)​(4.3)

其中：
IV(a)=−v=1∑V​∣D∣∣Dv∣​log2​∣D∣∣Dv∣​(4.4)
称为属性a的“固有值”(intrinsic value)。属性a的可能取值数目越大(即V越大)，则IV(a)的值越大。

• 增益率准则对可取值数目较少的属性有所偏好。因此，C4.5算法不是直接选择增益率最大的候选划分属性，而是使用了一个启发式：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。

基尼指数

• CART决策树使用“基尼指数”(Gini index)来选择划分属性，基尼值的定义为：

Gini(D)=k=1∑∣y∣​k̸​=1∑​pk​pk‘​=1−k=1∑∣y∣​pk2​(4.5)

• Gini(D)反映了从数据集D中随机抽取2个样本，其类别标记不一致的概率，因此，Gini(D)越小，数据集的纯度越高。

• 属性a的基尼指数定义为：

Gini_index(D,a)=v=1∑V​∣D∣∣Dv∣​Gini(Dv)(4.6)

基尼指数越大，数据集的不确定性就越大。

我们在候选属性集合A中，选择哪个使得2划分后基尼指数最小的属性作为最优划分属性。即 $a_* = arg_{a\in{A}}min\ Gini_index(D,a) $。

剪枝处理

• 剪枝(pruning)是决策树学习算法对付“过拟合”的主要手段。在决策树学习中，为了尽可能正确分类训练样本，结点划分过程将不断重复，有时会造成决策树分支过多，这时可能因为训练样本学的“太好了”，以致于把训练集自身的一些特点当作所有数据都具有的一般性质而导致过拟合。
• 决策树剪枝的基本策略有“预剪枝”(prepruning)和“后剪枝”(postpruning)。
• 预剪枝：指在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点。
• 后剪枝：先从训练集中生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点。

4.评估和选择最佳假说

5. 学习理论

6. 带线形模型的回归和分类

7. 感知机

1. 感知机模型

• 2类分类的线性分类模型，其输入为实例的特征向量，输出为实例的类别，取+1和-1二值。对应于输入空间（特征空间）中将实例划分为正负两类的分离超平面，属于判别模型。旨在求出将训练数据进行线性划分的分离超平面，为此导入基于误分类的损失函数，利用梯度下降法对损失函数进行极小化，求得感知机模型。

• 定义：

  • 输入空间(特征空间)是 𝝌 ⊆ 𝑹 ，输出空间是𝑦 = {+1,−1} ，输入𝒙 ∈ 𝝌表示实例的特征向量，对应输入空间(特征空间)的点；输出 𝑦𝜖𝒚 表示实例的类别。由输入空间到输出空间的函数：

    ​f(x)=sign(w∙x+b)

  称为感知机。

​其中w和b为感知机模型参数。𝑤 ∈ 𝐑叫做权值 （weight）或权值向量（weight vector），𝑏 ∈ 𝐑叫 做偏置（bias）， w∙x+b 表示w和x的内积。

• 感知机是一种线性分类模型，属于判别模型；感知机模型的假设空间是定义在特征空间中的所有线性分类模型( linear classification model )或线性分类器( linear classifier)，即函数集合:{f∣f(x)=w∙x+b}

• 感知机有如下几何解释：线性方程 : w∙x+b=0

  对应于特征空间𝐑中的一个超平面S，其中w是超平面 的法向量，b是超平面的截距。

  超平面将特征空间划分为两个部分，位于两部分的点 （特征向量）分别被分为正、负两类。因此该平面S成为分离超平面（separating hyperplane）。

1. 感知机学习策略

• 数据集的线性可分性

  • 给定数据集 T={(x1​,y1​),(x2​,y2​),...,(xn​,yn​)}

  其中$x_i\in 𝝌 = 𝑹^𝑛, y_i \in Y ={+1,-1}, i=1,2,3,…,N $,

  如果存在某个超平面S:

  ​w∙x+b=0

  能将数据集的正实例点和负实例点完全正确的划分到超平面的两侧，则称数据集T为线性可分数据集（linearly separable data set);

• 感知机学习策略

  • 损失函数为误分类点的总数，不易优化。

  • 损失函数为误分类点到超平面S的总距离。

  • 输入空间𝐑𝑛中任一点𝑥0到超平面S的距离：

    ​∣∣w∣∣1​∣w∙x+b∣

    ∣∣w∣∣是w的L 范数。

1. 感知机学习算法

   输入：训练数据集T={(x1​,y1​),(x2​,y2​),...,(xn​,yn​)}

   其中$x_i\in 𝝌 = 𝑹^𝑛, y_i \in Y ={+1,-1}, i=1,2,3,…,N $,

   学习率 β(0<β≤1); 一般为1。

   输出：w，b；感知机模型：f(x)=sign(w∙x+b)。

   1. 选取初值𝑤,𝑏。

   2. 在训练集中选取数据(𝑥,𝑦)

   3. 如果$𝑦_𝑖 (𝑤 ∙ 𝑥_𝑖) + 𝑏 ≤ 0 $:
      w←w+βyi​xi​

      ​b←b+βyi​

   4. 转到2，直至训练集中没有误分类点。

• 输入空间𝐑𝑛中任一点𝑥0到超平面S的距离：

  ​∣∣w∣∣1​∣w∙x+b∣

  ∣∣w∣∣是w的L 范数。

1. 感知机学习算法

   输入：训练数据集T={(x1​,y1​),(x2​,y2​),...,(xn​,yn​)}

   其中xi​∈X=Rn,yi​∈Y={+1,−1},i=1,2,3,...,N,

   学习率 𝜂(0 < 𝜂 ≤ 1); 一般为1。

   输出：w，b；感知机模型：f(x)=sign(w∙x+b)。

   1. 选取初值𝑤,𝑏。

   2. 在训练集中选取数据(𝑥,𝑦)

   3. 如果yi​(w∙xi​)+b≤0:

      ​w←w+βyi​xi​

      ​b←b+βyi​

   4. 转到2，直至训练集中没有误分类点。