人工智能导论

1 绪论

1.1 人工智能的起源与发展

1.1.1 孕育期

• 数理逻辑-符号主义学派

  • 亚里士多德-三段论
  • 莱布尼茨-形式逻辑符号化
  • 启发式算法➡专家系统➡知识工程理论与技术

• 人工神经网络-连接主义学派

  • 麦克洛奇和皮兹-第一个神经网络模型MP模型
  • 赫布-改变神经网络连接强度的Hebb规则

• 行为主义学派

  • 维纳-控制论，其影响导致形成了行为主义学派

• 人工智能的载体

  • 计算机-1946年，第一台通用计算机ENIAC

• 人工智能之父

  • 图灵

  • 图灵试验

• AI的诞生

  • 1956年的一次会议，麦卡锡提议正式采用了Artificial Intelligence这一术语

1.1.2 形成期

1.1.3 第一次低谷

1.1.4 黄金时代

1.1.5 第二次低谷

1.1.6 平稳发展期

1.1.7 蓬勃发展期

• 发展现状

  • 专用人工智能-让人工智能专门去做一件事

1.2 人工智能的三大学派

1.2.1 图灵测试

• 通过让机器模仿人回答某些问题
• 判断它是否具备智能
  • 核心：不是“计算机能否和人对话”，而是“计算机能否在智力行为上表现得和人无法区分”
  • Turing测试第一次给出了检验计算机是否具有智能的哲学说法

1.2.2 符号主义Symbolicism

• 逻辑主义、心理学派和计算机派
• 其原理主要为物理符号系统（即符号操作系统）假设和有限合理性原理
• 人是一个物理符号系统，计算机也是一个物理符号系统，因此，能够用计算机来模拟人的智能行为
• 基于逻辑推理的智能模拟方法，源于数学逻辑
• 主要成果：机器定理程序（LT、GTM、GPS….）、启发式算法、专家系统
• 可以解决逻辑思维,但对于形象思维难于模拟，信息表示成符号后，并在处理或转换时,信息有丢失的情况

1.2.3 连接主义Connectionism

• 又称为仿生学派或生理学派
• 其原理主要为神经网络及神经网络间的连接机制与学习算法
• 核心思想：认为人的智能归结为人脑的高层活动的结果，强调智能活动是由大量简单的单元通过复杂链接后，并行运行的结果。
• 代表成果：人工神经网络，深度神经网络
• 不适合于解决逻辑思维，体现结构固定和组成方案， 单一的系统也不适合多种知识的开发

1.2.4 行为主义Actionism

• 又称进化主义和控制论学派

• 其原理为控制论及感知——动作型控制系统

• 控制学论

  • 认为智能取决于感知和行为，取决于对外界复杂环境的适应，而不是表示和推理

• 进化学论

  • 认为人的智能归根结底是从生物进化中得到

1.2.5 人工智能三种主流方法区别

• 用规则教

  • 优势：与人类逻辑推理相似，解释性强
  • 不足：难以构建完备的知识规则库

• 用数据学

  • 优势：直接从数据中学
  • 不足：依赖于数据、解释性不强

• 用问题引导

  • 优势：从经验中进行能力的持续学习
  • 不足：非穷举式搜索而需更好策略

2 知识表示

2.1 知识层次

• 数据

  • 一些无关联的事实

• 信息

  • 建立了事实间的联系后形成的信息

• 知识

  • 当能建立模式之间的联系后便涌现出了知识

• 智慧

  • 能描述模式之间关系的规律

2.2 知识表示的过程

• 非形式化的自然语言描述➡形式化的易于被计算机理解的表示

2.3 知识的特性

• 相对正确性
• 不确定性
• 可表示性和可利用性

2.4 知识的表示

• 将人类知识形式化或者模型化

2.4.1 目的

• 让机器存储和运用人类的知识

2.4.2 选择知识表示方法的原则

• 充分表示领域知识
• 有利于对知识的利用
• 便于对知识的组织、维护与管理
• 便于理解和实现

2.4.3 几种知识表示的方法

• 符号主义

  • 谓词逻辑

    • 逻辑学之父：亚里士多德-三段论

    • 命题逻辑：研究命题和命题之间关系的符号逻辑系统

      • 命题：一个非真即假的陈述句

      • 联接词：诸如“没有”、“如果…那么…”等连词

        • 与，命题合取，p且q

        • 或，命题析取，p或q

        • 非，命题否定，非p

        • 条件，命题蕴含，如果p则q

          • 仅p为true且q为false时，结果为false

        • 双向条件，命题双向蕴含，p当且仅当q

          • p和q同为true或同为false时，结果为true

    • 复合命题：由联结词和命题连接而成的更加复杂的命题称为复合命题

      • 逻辑等价的例子

  

• 谓词逻辑

  • 用于刻画个体的性质、状态和个体之间关系的语言成分就是谓词

    • 分类

    • 一元谓词A(x)

      • 二元谓词B(x,y)

      • 多元谓词P(x1,x2,x3,…,xn)

      • x1,x2,x3,…,xn为客体变量或变元

  • 语法元素

    • 常量（个体符号）

      • 变量符号

      • 函数符号

      • 习惯上用小写英文字母或小写英文字母串表示

    • 谓词符号

      • 习惯上用大写英文字母或者首字母大写的英文字母串表示

    • 联结词

  • 量词

    • 全称量词

      • 存在量词

      • 全程量词与存在量词的组合

      • ∀𝑥¬𝑃(𝑥) ≡ ¬∃𝑥𝑃(𝑥)
        - ¬∀𝑥𝑃(𝑥) ≡ ∃𝑥¬𝑃(𝑥)
        - ∀𝑥𝑃(𝑥) ≡¬∃𝑥¬𝑃(𝑥)
        - ∃𝑥𝑃(𝑥) ≡ ¬∀𝑥¬𝑃(𝑥)

  • 函数与谓词的区别

    • 函数时从定义域到值域的映射，结果仍为个体
      • 谓词时从定义域到{True, False}的映射，结果为命题

  • 推理规则

    • 全称量词消去UI

      • (∀𝑥)𝐴(𝑥) → 𝐴(𝑦)

    • 全称量词引入UG

      • 𝐴(𝑦) → (∀𝑥)𝐴(𝑥)

    • 存在量词消去EI

      • (∃𝑥)𝐴(𝑥) → 𝐴(𝑐)

    • 存在量词引入EG

      • 𝐴(c) → (∃𝑥)𝐴(𝑥)

  • 优点

    • 自然性
      • 精确性
      • 容易实现

  • 不足

    • 不能表示不确定性知识
      • 形式过于自由，兼容性差

• 产生式系统

  • 通常用于表示事实、规则以及它们的不确定性度量，适合于表示事实性知识和规则性知识

  • 确定性规则知识的产生式表示

    • IF P THEN Q 或者 P➡Q

      • 三元组表示：（对象，属性，值）或者（关系，对象1，对象2）

        • （Li，age，40）
          • （friend，Li，Wang）

  • 不确定规则知识的产生式表示

    • IF P THEN Q（置信度） 或者 P➡Q（置信度）

      • 四元组表示：（对象，属性，值，置信度）或者 （关系，对象1，对象2，置信度）

        • （Li，age，40, 0.8）
          • （friend，Li，Wang, 0.1）

  • 产生式和谓词逻辑中的蕴含式的区别

    • 产生式与谓词逻辑中的蕴涵式的基本形式相同，但蕴涵式只是产生式的一种特殊情况。
      • 除逻辑蕴含外，产生式还包括各种操作、规则、变换、算子、函数等。
      • 蕴含式只能表示精确知识，而产生式不仅可以表示精确的知识，还可以表示不精确知识。

  • 基本结构

    

    • 规则库

      • 综合数据库

      • 控制系统（推理机）

        • 推理
          • 冲突消解
          • 执行规则
          • 检查推理终止条件
          • 长颈鹿的例子

  

  • 优点

    • 自然性
      • 模块性
      • 有效性
      • 清晰性

  • 缺点

    • 效率不高
      • 不能表达结构性知识

  • 专家系统

    • 专家系统可以模拟某个领域专家的决策能力。

• 框架系统

  • 一种结构化的知识表示方法，已在多种系统中得到应用。

    • 一般结构

      • 框架
        • 一个槽用于描述所论对象某一方面的属性
        • 一个侧面用于描述相应属性的一个方面
        • 槽和侧面所具有的属性值分别被称为槽值和侧面值
        • 计算机主机的框架描述示例

      

  • 典型的框架知识库FrameNet

  • 特点

    • 结构性
    • 继承性
    • 自然性

• 经验主义

  • 状态表示（状态空间表示法）

    • 用来表示问题及其搜索过程的一种方法，它是以状态和算符(操作)为基础来表示和求解问题的

    • 主要元素

      • 状态

        • 状态变量

      • 操作

      • 状态空间

        • 状态空间用一个三元组表示：（S, F, G）
        • 状态空间图

    • 二阶梵塔难题求解过程

    • 猴子与香蕉问题求解过程

    • 传教士问题求解过程

  • 特征表示

• 连接主义

  • 网络权重
  • 语义向量

3 搜索求解策略

3.1 内容

• 早期搜索技术，如图搜索、盲目搜索、启发式搜索
• 高级搜索技术，如规则演绎系统、产生式系统
• 给定待求解问题→搜索算法按事先设定的逻辑自动寻找答案

3.2 概念

• 根据问题的实际情况不断寻找可利用的知识，构造出一条代价较少的推理路线，使问题得到圆满解决的过程。

3.3 标准

• 搜索空间小
• 解最佳

3.4 图搜索策略

3.4.1 基本概念

• 图的搜索

  • 一种在图中寻找路径的方法，图中每个节点对应一个状态，每条连线对应一个操作符

• 分类

  • 无信息搜索（盲目搜索）
  • 有信息搜索（启发式搜索）

3.4.2 状态图搜索

• 记录搜索轨迹

  • OPEN表（存放待扩展的节点表）
  • CLOSED表（存放已扩展的节点）
  • 从目标返回的路径
  • 注：每个表示状态的节点结构中必须有指向父节点的指针

• 图的一般搜索策略

  

  • 状态图搜索-例题一

3.4.3 盲目式搜索

3.4.3.1 概念

• 对特定问题不具有任何相关信息的条件下，按照固定的步骤（依次或者随机）进行搜索，搜索过程中获得的中间信息不用来改进控制策略。

3.4.3.2 宽度优先搜索

• OPEN表采用先进先出的队列结构，先生成的节点先扩展
• 宽度优先搜索策略

• 宽度优先搜索示例

• 八数码难题-BFS

• 特点

  • 新扩展的节点排在open表的末端
  • 当问题有解时，一定能找到解
  • 方法与问题无关，具有通用性

3.4.3.3 深度优先搜索

• OPEN表采用先进后出的堆栈结构，先扩展最新产生的（即最深的）节点
• 深度优先搜索策略

• 深度优先搜索示例

• 深度界限

  • 防止搜索过程沿着无益的路径扩展下去，往往给出一个节点扩展的最大深度——深度界限

• 节点深度

  • 起始节点的深度为0，任何其他节点的深度等于其父辈节点的深度加1。

• 八数码难题-DFS

• 特点

  • 一般不能保证找到最优解
  • 当深度限制不合理时，可能找不到解，可以将算法改为可变深度限制
  • 最坏情况时，搜索空间等同于穷举

3.4.3.4 等代价搜索

• Dijkstra提出——Dijkstra算法

• 是宽度优先搜索的一种推广，不是沿着等长度路径断层进行扩展，而是沿着等代价路径断层进行扩展。状态图中每条连接弧线上的有关代价，表示时间、距离等开销。

• 节点代价

  • g (n)： 表示从初始节点 S。到节点n的代价；
  • c (n1, n2) : 表示从父节点 n1 到其子节点 n2 的代价；
  • g (n2) = g (n1) + c ( n1 ,n2)

• 等代价搜索策略

• 等代价搜索示例

3.4.3.5 盲目式搜索特点

• 搜索过程中不使用与问题有关的经验信息
• 搜索效率低
• 不适合大空间的实际问题求解

3.4.4 启发式搜索

• 启发性信息是指那种与具体问题求解过程有关的，并可指导搜索过程朝着最有希望方向前进的控制信息。

3.4.4.1 核心思想

• 需定义一个评价函数，对当前的搜索状态进行评估， 找出一个最有希望的节点来扩展。即根据评价函数重排OPEN表， 选择最有希望的节点加以扩展。
• 估价函数：f(n) = g(n) + h(n)，g(n)表示从起始状态到当前状态n的实际代价，h(n)表示从当前状态到目标状态的估计代价（启发式函数）

3.4.4.2 A算法

• 有序搜索，也称优先搜索/全局择优， 选择OPEN表上具有最小 f 值的节点作为下一个要扩展的节点。
• 有序搜索算法框图

• A算法求解八数码问题过程

• 特征

  • 对h(n)无限制，虽提高了算法效率，但不能保证找到最优解
  • 不合适的h(n)定义会导致算法找到不解

3.4.4.3 A*算法

• 彼得.哈特对A算法进行了很小的修改，并证明了当估价函数满足一定的限制条件时，算法一定可以找到最优解。

• 隶属于A算法，估价函数满足一定限制条件的算法称为A*算法

• f (n) = g (n) + h (n), g(n)大于0，h(n)不大于n到目标节点的实际代价

  • g (n) >=g* (n)，g*(n)是从初始节点S0到任意节点n的一条最佳路径的代价
  • h (n) <=h* (n)，h*(n)是从节点n到目标节点的一条最佳路径的代价
  • f(n)可视为经过节点n，具有最小开销代价值的路径。

• 根据h(n)区分几种算法

  • 如果第8步的重排OPEN表是依据f(n)=g(n)+h(n) 进行的,则称该过程为A算法
  • 在A算法中,如果对所有的n存在h(n)≤h*(n) ,则称h(n)为h*(n)的下界,它表示某种偏于保守的估计，采用h*(n)的下界h(n)为启发函数的A算法，称为A*算法。
  • h(n)=0 时，A*算法就变为等代价搜索算法

• A*算法流程图

• A*算法求解八数码问题

• A*算法的搜索效率很大程度上取决于h(n), 在满足h(n)<=h*(n)的前提下，h(n)的值越大越好,h(n)的比重越大表示启发性越强。

• 如果算法有解， A*算法一定能够找到最优的解答。

• 特点

  • 在f(n)中，g(n)的比重越大，越倾向于宽度优先搜索，而h(n)的比重越大，表示启发性越强。
  • g(n)的作用一般是不可忽略的，保持g(n)项就保持了搜索的宽度优先成分，这有利于搜索的完备性，但会影响搜索的效率。

4 智能计算及其应用

4.1 遗传算法

4.1.1 定义

• 通过生物遗传和进化过程中选择、交叉、变异机理的模仿，完成对问题求解的自适应搜索过程。

4.1.2 与生物进化对比

4.1.3 基本思想

• 把问题的解表示成“染色体”，在算法中即是以一定方式编码的串，在执行遗传算法之前，给定一群“染色体”——即假设解。
• 把这些假设解置于问题的“环境”中，并按适者生存的原则：从中选择出较适应环境的“染色体”进行复制，再通过交叉、变异过程产生更适合环境的新一代“染色体”群。
• 这样一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上——它就是问题的最优解
• 5个基本要素
  • 参数编码
  • 初始群体设定
  • 适应度函数设定
  • 遗传操作设计
  • 控制参数设定

4.1.4 主要操作

• 编码

  • 将问题结构变换为位串形式编码表示的过程叫编码(Encoding)
  • 将位串形式编码表示变换为原问题结构的过程叫解码或译码(Decoding)
  • GA中的编码方式：二进制编码、浮点数编码、格雷码编码、符号编码等

• 群体设定

  • 初始种群的产生

    • 根据问题固有知识，把握最优解所占空间在整个问题空间中的分布范围，然后，在此分布范围内设定初始群体。
    • 随机产生一定数目的个体，从中挑选最好的个体加到初始群体中。这种过程不断迭代，直到初始群体中个体数目达到了预先确定的规模。

  • 种群规模的确定

    • 规模太小：遗传算法的优化性能不太好，易陷入局部最优解
    • 规模太大：计算复杂

• 适应度函数

  • 表示个体的优劣并作为遗传操作的依据

    • 个体适应度高：被选择的概率大；反之就小

  • 直接将待求解优化问题的目标函数变换而得到

    • 最大化问题直接为目标函数，最小化问题则为目标函数的倒数

  • 在遗传算法中，将所有妨碍适应度值高的个体产生、从而影响算法正常工作的问题统称为欺骗问题（Deceptive Problem）

    • 过早收敛：缩小这些个体的适应度，以降低这些超级个体的竞争力

    • 停滞现象：改变原始适应值的比例关系，以提高个体之间的竞争力

    • 适应度函数的尺度变换（Fitness Scaling）或者定标：对适应度函数值域的某种映射变换

      • 线性变换

        • 变换的时候希望满足变换前后它的平均值或者什么保持不变，所以可以加上约束，也可以不加

      • 幂函数变换

      • 指数变换

• 选择

  • 个体选择概率分配方法

    • 适应度比例方法/蒙特卡洛法

    • 排序方法

      • 线性排序
      • 非线性排序

  • 选择个体的方法

    • 轮盘赌选择：适应度➡选择概率➡累积概率，若r<q[1]，选择个体1，否则选择个体k，满足q[k-1]<r≤q[k]。
    • 最佳个体保存方法
      • 把群体中适应度最高的个体直接复制到下一代中，保证遗传算法终止时得到的最后结果一定是历代出现过的最高适应度的个体。
    • 锦标赛选择
    • 从群体中随机选择一些个体，将其中适应度最高的个体保存到下一代。这一过程反复执行，直到保存到下一代的个体数达到预先设定的数量为止。
      • 二元锦标赛：每个选择的个体数为2。

• 交叉

  • 一点交叉：在个体串中随机设定一个交叉点，实行交叉时，两个个体的该点前或后的部分结构进行互换，并生成两个新的个体。
  • 二点交叉：随机设置两个交叉点，将两个交叉点之间的码串相互交换。

• 变异

  • 交叉只能对现有基因池进行重组，变异可以生成新的基因

  • 变异概率pm ：控制算法中变异操作的使用频率，变异算法的变异率应该控制在较低的频率

  • 方式

    • 位点变异

      • 群体中的个体码串，随机挑选一个或多个基因座，并对这些基因座的基因值以变异概率作变动
      • 如果对于某个基因位，产生的随机数小于pm,则改变该基因的取值。否则该基因不发生变异，保持不变。

    • 逆转变异

      • 在个体码串中随机选择两点（逆转点），然后将两点之间的基因值以逆向排序插入到原位置中

    • 插入变异

      • 在个体码串中随机选择一个码，然后将此码插入随机选择的插入点中间

    • 互换变异

      • 随机选取染色体的两个基因进行简单互换

    • 移动变异

      • 随机选取一个基因，向左或者向右移动一个随机位数

4.1.5 一般步骤

4.1.6 遗传算法与搜索技术的比较

• 从形式上：遗传算法与状态空间搜索法非常类似

  • 状态表示为向量 = 状态表示为个体
  • 状态转移 = 个体繁殖

• 在应用中，两种方法略有差别

  • 状态空间搜索适合于问题清晰、优化目标清晰，容易设想“怎样会更好”，这时设计启发函数，采用状态空间搜索效率很高；若使用遗传算法，往往效率不佳。
  • 但对于一些限制条件非常多的问题，此时设计启发函数很难，因为很难证明所设计的启发函数是A*的，从而就无法保证搜索总是有效的。这种情形，使用遗传算法反而更有优势。

4.2 粒子群优化算法

4.2.1 粒子速度和位置的更新

• 惯性部分
• 认知部分
• 社会部分

4.2.2 流程图

4.2.3 PSO算法参数分析

• 参数

  • 群体规模

  • 惯性权重

    • 保持运动惯性，使其有1扩展搜索空间的趋势

  • 加速度

    • 代表将粒子推向个体最优位置和群体最优位置的统计加速项的权重

  • 最大速度

    • 限制粒子的在某维的速度不超过最大速度

  • 最大代数

• 各部分的影响

  • 只有惯性部分

    • 粒子将一直以当前速度飞行，直到边界。由于只能搜索有限区域，所以很难找到好解。

  • 没有惯性部分

    • 速度只取决于例子当前位置和其历史最好位置，速度本身没有记忆性。

  • 没有认知部分

    • 粒子没有认知能力，也就是”只有社会“模型。在粒子的相互作用下，有能力达到新的搜索空间。但对复杂问题，容易陷入局部最优点。

  • 没有社会部分

    • 粒子间没有社会共享信息，也就是”只有认知“模型。因为个体间没有交互，一个规模为m的群体等价于m个单个粒子的运行，因而得到最优解的机率非常小。

4.2.4 特点

• 优点

  • 简单易实现
  • 收敛速度快
  • 粒子具有记忆性

• 缺点

  • 缺乏速度的自适应调节，容易陷入局部最优，可能导致收敛精度低或者不收敛
  • 标准粒子群算法不能有效求解离散及组合优化问题
  • 参数难以确定，对不同的问题，需选择合适的参数来达到最优效果

4.3 蚁群算法

4.3.1 基本原理

• 信息素

  • 信息素是一种由蚂蚁自身释放的易挥发的物质，信息素的浓度越高，对应的路径越短

• 正反馈

  • 蚂蚁会以较大的概率选择信息素浓度较高的路径，并释放一定量的信息素，从而使距离较短路径的信息素被加强，形成一个正反馈。

4.3.2 基本框架

• 模拟蚂蚁

  • 每只蚂蚁都有相同的目标，以相同速度运动
  • 蚂蚁在行走过程中，在达到目的地前，不走回头路，不转圈
  • 每只蚂蚁都根据相同的原则释放信息素、选择路径
  • 每只蚂蚁都记得自己经历路径的长度和过程
  • 种群中蚂蚁的数量不会发生变化

• 模拟环境”地图“

  • 我们将蚂蚁觅食的环境抽象成“具有N个节点的全连通图”

    • 图上一共有n个节点，每个节点都与其他所有节点直接相连
    • 任意两点X、Y之间的距离记为：dxy 均为已知
    • 具有明确的起点和终点

• 模拟蚂蚁选择路线

  • 第一种：不考虑信息素的影响，选择距离最短的路线行动，符合贪心原则

  • 第二种：不考虑各点之间的距离，选择信息素值最大的路线行动

  • 由于蚂蚁智力有限，上面的准则应该概率化

    • 与该路线的长度成反比
    • 与该路线上信息素浓度成正比

• 蚂蚁选择路线的概率计算式

• 模拟信息素的释放与消散

  • 信息素随着时间推移而消散

• 一种常见策略：将时间“片段化”，以“cycle”为单位来模拟时间

    -  一个cycle：表示蚁群中所有蚂蚁均从出发点成功达到目标点
  

  • 信息素：在一个cycle结束之后统一更新，不考虑cycle期间的消散和累积

• 信息素的消散公式

• 走最短路径的蚂蚁，其留下的信息素值越高，成反比

4.3.3 参数选择

• 信息素启发因子

  • 反映了蚁群在路径搜索种随机性因素作用的强度

• 期望值启发因子

  • 反映了蚁群在路径搜索种先验性、确定性因素作用的强度

• 信息素挥发度1-p

  • 当处理的问题规模比较大时，会使那些从未被搜索到的路径（可行解）上的信息量减少到接近于0，因而降低了算法的全局搜索能力

4.3.4 旅行商问题求解过程

• 解决TSP问题的基本流程

4.3.5 特点

• 优点

  • 在求解性能上具有很强的鲁棒性，搜索能力较强
  • 一种基于种群的算法，具有本质并行性，易于并行实现
  • 很容易与其他算法，如：遗传算法、粒子群算法结合，以改善算法性能

• 不足

  • 如果初始化参数设置不当，会导致求解速度很慢且所得解的质量特别差
  • 基本蚁群算法即无改进的蚁群算法，计算量大，求解所需时间较长

5 机器学习

5.1 概述

• 研究如何使用机器来模拟人类学习活动

5.1.1 研究内容

• 任务-T
• 方法-A
• 经验-E
• 性能-P

5.1.2 基本过程

• 计算机从给定的数据中学习规律，即从观测数据（样本）中寻找规律、建立模型，并利用学习到的规律（模型）对未知或无法观测的数据进行预测。

5.1.3 分类

• 监督学习

• 无监督学习

• 半监督学习

  • 数据没有标签，机器学习出的模型是从数据中提取出来的模式（提取决定性特征或者聚类等），一般是分类或回归等任务。

• 强化学习

  • 外部环境对输入只给出评价信息而非正确答案，学习机通过强化受奖励的动作来改善自身的性能。常见的应用场景包括动态系统以及机器人控制等。

5.1.4 基本概念

• 训练集
• 测试集
• 样本/观测
• 标签

5.1.5 数据划分

• 训练集

• 测试集

• 验证集

  • 用来做模型选择（model selection），即做模型的最终优化及确定的

5.1.6 误差与精度

• 误差

  • 学习器（Learner）的实际预测输出与样本的真实输出之间的差异

• 错误率

  • 被错误分类的样本在总样本中的比例。

• 精度

  • 被正确分类的样本在总样本中的比例，即1 – error rate

• 训练误差

  • 学习器在训练集上的误差，也称作经验误差（empirical error）

• 测试误差

  • 学习器在测试集上的误差，用来近似泛化误差。

• 泛化误差

  • 在新样本的误差，实际误差！

5.1.7 监督学习与无监督学习的区别

5.1.8 分类与回归

• 分类技术：预测分类响应；分类模型将输入数据分为不同类别
• 回归技术：预测连续的响应

5.1.9 机器学习内容

5.2 监督学习-分类KNN

5.2.1 核心思想：近朱者赤近墨者黑

• 给定训练集，对于新输入样本，则在与其最邻近前K个训练样本中某个类居多，就认为新样本属于该类别。
• 不需要使用训练集进行训练，靠周围有限的邻近样本属性多少判断

5.2.2 缺点

• 对参数选择很敏感

  • 较小k值→陷入局部，易发生过拟合

  • 较大k值→较大邻域，预测易错误

  • 选取一个较小的数值，通常采取交叉验证法来选取最优的k值

    • 在给定的建模样本中，拿出大部分样本进行建模型，留小部分样本用刚建立的模型进行预报，并求这小部分样本的预报误差，记录它们的平方加和。

• 计算量大

5.2.3 距离度量

• 欧几里得距离、曼哈顿距离、切比雪夫距离等
• 距离函数的选择应该根据数据的特性和分析的需要而定
• 距离计算

5.2.4 特征属性归一化的必要性

• 各特征量纲不同
• 归一化处理

5.3 监督学习-分类决策树

5.3.1 决策树定义

• 决策树是一种树型结构，由结点和有向边组成

• 结点

  • 内部结点表示一个属性或特征
  • 叶结点代表一种类别，对应于决策结果

• 有向边/分支

  • 分支代表一个测试输出

5.3.2 决策树算法

• 基本思想

  • 采用自顶向下的递归方法，以信息熵为度量构造一棵熵值下降最快的树，到叶子结点处的熵值为零，此时每个叶结点中的实例都属于同一类
  • 决策树可以看成一个if-then的规则集合
  • 一个决策树将特征空间划分为不相交的单元(Cell)或区域(Region)

• 算法流程

  • 训练

    • 利用训练集建立一棵决策树，构建决策树模型。

  • 测试

    • 利用生成的模型对输入数据进行分类

• 主要算法

  • ID3：信息增益

    • 以信息论为基础，以信息熵和信息增益度作为衡量标准，从而实现对数据的归纳分类

      • ID3算法是以信息增益为准则，对每次递归的结点属性进行选择的

    • 信息熵

      • 信息熵越小，信息量越大，不确定性越小，样本纯度越高

    • 信息增益

      • 信息增益越大，用属性a划分所获得纯度提升越大

    • 优点

      • 只需对训练实例进行较好地标注，就能进行学习，从一类无序、无规则事物(概念)中推理出分类规则。
      • 分类模型是树状结构，简单直观，可将决策树中到达每个叶结点的路径转换为IF-THEN形式的分类规则，比较符合人类的理解方式。

    • 缺点

      • 信息增益偏好取值多的属性
      • 可能会受噪声或小样本影响，易出现过拟合问题
      • 无法处理连续值的属性
      • 无法处理属性值不完整的训练数据

  • C4.5：信息增益率

  • CART：基尼指数

5.4 监督学习-线性回归

5.4.1 回归分析

• 学习得到一函数将输入变量映射到连续输出空间，即值域是连续空间。

5.4.2 相关概念

• 回归分析

  • 分析不同变量之间存在关系

  • 回归模型

    • 刻画不同变量之间关系的模型

  • 线性回归模型

    • 如果这个模型是线性的

5.4.3 参数学习

• 最小二乘法

• 最小二乘法示例

5.5 无监督学习-K均值

5.5.4 无监督学习的重要因素

• 数据特征

• 相似度函数

  • 定义一个相似度计算函数，基于所提取的特征来计算数据之间的相似性

5.5.5 K均值聚类（K-means）

• 目的

  • 将𝑛个数据聚类到𝑘个集合（也称为类簇）

• 算法步骤

1. 随机选取K个对象作为初始聚类中心

2. 将数据样本集合中的样本按照最小距离原则分配到最近邻聚类

3. 根据聚类的结果，重新计算K个聚类的中心，并作为新的聚类中心

   • 平均值法求聚类中心，不一定是样本点

4. 重复步骤2、3直到聚类中心不再变化

• 小结

  • 需事先确定聚类数K——很多时候并不知道应被聚类的数目
  • 需初始化聚类质心——其对聚类结果有较大的影响
  • 算法是迭代执行——时间开销非常大
  • 采用欧氏距离——假设数据每个维度之间的重要性是一样的

6 人工神经网络

6.1 概述及感知机

6.1.1 神经元模型

6.1.2 人工神经网络（ANN）特性

• 并行分布处理
• 非线性映射
• 通过训练进行学习
• 适应与集成
• 硬件实现

6.1.3 人工神经网络发展历史

• 萌芽期

  • MP模型
  • Hebb提出著名的Hebb学习规则

• 第一次高潮期

  • Rosenblatt提出感知机模型

• 反思期

  • Minsky和Papert从数学上深入分析了感知器的原理，指出其局限性

• 第二次高潮期

  • Rumelhart及Hinton等学者提出了多层感知器的反向传播算法，解决了多层前向神经网络的学习问题

6.1.4 第一个神经元模型

• McCulloch和Pitts提出首个神经元模型，该模型是一个简单的二元分类器，它接受n维的输入： (x1, x2, ┄ xn ) , x∈ {0,1} ，随后对这个n维的输入进行加权求和，并将其与阈值θ进行比较， 若大于阈值输出1，否则输出0。

• 原始神经元的缺点

  • 输入输出都是二元的
  • 不能训练也没有学习能力

6.1.5 激活函数

• 线性函数

• 非线性斜面函数

• 阈值函数

• S形函数

6.1.6 感知机

• 感知机与神经元模型相似，主要有以下几点改进

  • 输入为一个实数向量；
  • 有多种激活函数可以选择；
  • 属于一个可学习模型。

• 感知机由两层神经元组成，是最简单的神经网络。

  • 输入层神经元

  

  • 输出层神经元

  

• 单层感知机模型

• 感知机模型的数学原理

  • 输入向量为二元向量时，方程确定了二维平面上的一条分界线
  • 输入向量为三元向量时，方程确定了三维平面上的分界面
  • 逻辑运算的实现

• 单层感知机模型的缺点

  • 仅能解决一阶谓词逻辑，即只能完成线性划分，对于非线性或者其他分类会遇到很多困难，就连简单的XOR（异或）问题都解决不了（无法找到一个超平面将两类样本区分开）。

• 多层感知机

  

  • 异或问题无法用一个超平面将两类样本分割开，于是人们考虑对多个感知机模型进行组合，即采用多个超平面去分割——多层感知机

  • 多层感知机求解异或问题

    

    • 当中间层的神经元的激励函数分别采用二值和双极时，其结果是不一样的。激励函数：中间是双极+输出是二值时，可以解异或；中间及输出均为二值时，则无解。

      • 即使网络结构及参数完全一样，但因激励函数的选取差异会导致不同的求解结果。

    • 多层网络虽然很好地解决了线性不可分问题，但是，由于无法知道网络隐藏层的神经元的理想输出，所以，感知器的训练算法是难以直接用于多层网的训练。

  • 多层感知机曲线拟合问题

• 感知机小结

  • 其学习过程与求线性判决函数(单样本感知器算法)的过程是等价的
  • 单层感知器只能解决线性可分的问题
  • 可以证明，只要隐层和隐层单元数足够多，多层感知器网络可实现任何模式分类
  • 但是，多层感知器网络的权值如何确定，即网络如何进行学习，没有得到解决（多层感知器是一个黑箱，结果不可解释）

6.1.7 梯度下降思想

• 导数的方向为误差e上升最快的方向，我们只需将w, b 向着导数的相反方向进行调整，即可使误差e减小——梯度下降。

6.2 BP神经网络

6.2.1 基本思想

• 从后向前反向逐层传播输出层的误差，以间接计算隐层的误差。

  • 正向过程：从输入层经隐藏层逐层正向计算各单元的输出。
  • 反向过程：由输出误差逐层反向计算隐层各单元的误差，并用此误差修正前层的权重。

6.2.2 多层前馈神经网络

• 每层神经元与下一层神经元完全相连，神经元之间不存在同层连接，也不存在跨层连接。
• BP神经网络模型拓扑结构

6.2.3 BP网络及算法中的变量符号

6.2.4 反向传播算法的学习过程/基本思想

• 选择一组训练样本，每一个样本由输入信息和期望的输出结果两部分组成。
• 从训练样本集中取一样本，把输入信息输入到网络中。
• 分别计算经神经元处理后的各层结点的输出。
• 计算网络的实际输出和期望输出的误差。
• 从输出层反向计算到第一个隐层，并按照某种能使误差向减小方向发展的原则，调整网络中各神经元的连接权值。
• 对训练样本集中的每一个样本重复(3)-(5)的步骤，直到对整个训练样本集的误差达到要求为止。

6.2.5 如何设计一个多层前馈神经网络

• 网络的输入对应于每个训练元组测量的属性。
• 输入同时提供给称作输入层的单元层。
• 这些输入通过输入层，然后加权给隐藏层。
• 隐藏层的数量是任意的，尽管实践中通常只用一层。
• 最后一个隐藏层的加权输出作为输出层的单元的输入，输出层发布给定元组的网络预测。
• 网络是前馈的：如果其权重都不回送到输入单元，或者前一层的输出单元。
• 从统计学观点来讲，网络进行非线性回归：给定足够多的隐藏单元和足够的训练样本，多层前馈网络可以逼近任何函数。与多层感知器类似：融合不同的曲线来拟合毫无规律可循的复杂曲线

6.2.6 如何设计网络拓扑结构

• 设计网络拓扑结构: 在训练之前，用户必须说明输入层的单元数、隐藏层数、每个隐藏层的单元数和输出层的单元数
• 规一化（Normalize）训练元组的每个属性的测量输入值至 [0.0-1.0]
• 一个输入单元每个值阈值权重或偏置）初始化为0
• 一个输出单元可以用来表示两个类，如果输出单元大于两个类，则每个类使用一个输出单元。一旦网络经过训练，并且其准确度不能接受，通常用不同的网络拓扑或使用不同的初始权重集

6.2.7 如何后向传播

• 原理

  • 后向传播迭代地处理训练元组数据集，将每个元组的网络预测和实际已知的目标值比较。
  • 对于每个训练样本，修改权重使网络预测和实际目标值之间的均方误差最小。
  • 修改“后向”进行：从输出层经每个隐藏层，到第一个隐藏层（因此称作后向传播）

• 算法步骤

  • 初始化权重为很小的随机数，每个单元有一个关联的偏倚
  • 向前传播输入（通过运用激励函数）
  • 向后传播误差（通过更新权重和偏倚）
  • 终止条件（当误差很小等）

6.2.8 BP学习算法流程图

6.2.9 BP算法小结

• 核心思想：利用前向传播，计算第n层输出值
• 优化目标：输出值和实际值的残差
• 计算方法：将残差按影响逐步传递回第n-1, n-2,…, 2层，以修正各层连接权值（误差逆传播）
• 主要工具：链式法则（复合函数求偏导）

6.2.10 BP算法局限性

• 容易过拟合

  • 早停、正则化

• 容易陷入局部最优

  • 选取多次初值、随机梯度下降法

• 难以设置隐层个数

  • 试错法