南京师范大学——人工智能导论复习

人工智能导论期末复习

第一章 绪论

人工智能简介

人工智能定义

人工智能是指研究，模拟人类智能的理论，方法，技术以及应用系统的一门技术科学，使用机器代替人类实现认知，识别，分析，决策等功能，本质上是对人的意识和思想的信息过程的模拟。

人工智能发展的三个阶段

1. AI不如人的阶段（不好用）
2. AI超过普通人（可以用）
3. AI超越专家（很好用）

互联网与人工智能

• 数字化
• 网联化
• 智能化

人工智能发展的三个层次

1. 弱人工智能（专用人工智能）

2. 强人工智能（通用人工智能）

3. 超人工智能

人工智能要素

人工智能三要素——算法、算力和数据

• 算法突破：深度学习

• 算力突破：智能芯片

• 资源突破：大数据

算法

机器学习 = 构建一个映射函数

什么是机器学习？

通过算法使得机器能从大量数据中学习规律从而对新的样本做决策。
规律：决策（预测）函数

机器学习实例

• 图像分类
• 目标检测
• 实例分割
• 垃圾邮件过滤
• 文档归类
• 情感分类

数据集

举例：
VISUAL GNOME
PASCAL Visual Object Classes
MS COCO
Large-scale Celeb Faces Attributes (CelebA) Dataset
The KITTI Vision Benchmark Suite
ChatGPT训练数据集

算力

智能芯片指的是针对人工智能算法做特殊加速设计的芯片。
根据功能分为：

• 训练芯片
• 推断芯片
  根据应用场景分为：
• 服务器端芯片
• 边缘端芯片
  根据技术架构分为：
• 通用类芯片（GPU）
• 基于FPGA的半定制化芯片
• 全定制化ASIC芯片
• 类脑计算芯片
  

人工智能前沿应用现状

• 目标检测
• 图像分割
• 细粒度图像分类
• 人脸识别
• 根据条件生成图像
• 预测未来
• 图像标题生产
• 图像风格化
• 图像转换
• 美颜
• 属性编辑
• 图像去噪去雾去抖动
• 图像增强修复彩色化
• 图像超分辨率
• 跨模态检索自然场景下文字检测识别
• 换脸
• 语音助理
• ChatGPT
• Sora

人工智能发展趋势挑战

• 新时代的电力
• 融入知识
  
  挑战：
• 人的内涵和人的本质
• 法律
• 隐私
• 偏见
• 可解释性
• 诚信体系
• 安全

第二章 知识表示与知识图谱

知识与知识表示

知识：把有关信息关联在一起所形成的信息结构。
知识反映了客观世界中事物之间的关系，不同事物或者相同事物间的不同关系形成了不同的知识。

知识的特性

1. 相对正确性
2. 不确定性
3. 可表示性与可利用性

知识的表示

知识表示（knowledge representation）：将人类知识形式化或者模型化。
知识表示是对知识的一种描述，或者说是一组约定，一种计算机可以接受的用于描述知识的数据结构。

一阶谓词逻辑表示法

详情参照离散数学所讲内容，不再重复。

一阶谓词逻辑表示法的特点

优点：

1. 自然性
2. 精确性
3. 严密性
4. 容易实现

局限性：

1. 不能表示不确定的知识
2. 组合爆炸
3. 效率低

应用：
（1）自动问答系统（Green等人研制的QA3系统）
（2）机器人行动规划系统（Fikes等人研制的STRIPS系统）
（3）机器博弈系统（Filman等人研制的FOL系统）
（4）问题求解系统（Kowalski等设计的PS系统）

产生式表示法

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

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

基本形式：
IF P THEN Q
或者：
P -> Q

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

基本形式：
IF P THEN Q (置信度)
或者：
P -> Q （置信度）

确定性事实性知识的产生式表示

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

不确定性事实性知识的产生式表示

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

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

蕴含式只能表示精确知识，而产生式不仅可以表示精确的知识，还可以表示不精确知识。蕴含式的匹配总要求是精确的。产生式匹配可以是精确的，也可以是不精确的，只要按某种算法求出的相似度落在预先指定的范围内就认为是可匹配的。

产生式的形式描述及语义

巴科斯范式BNF（backus normal form）

• 规则库：用于描述相应领域内知识的产生式集合。
• 综合数据库（事实库，上下文，黑板）：一个用于存放问题求解过程中各种当前信息的数据结构。
• 控制系统（推理机构）：由一组程序组成，负责整个产生式系统的运行，实现对问题的求解。
  控制系统做以下几项工作：

1. 推理
2. 冲突消解
3. 执行规则
4. 检查推理终止条件

产生式系统的例子——动物识别系统

产生式表示法的特点

优点：

1. 自然性
2. 模块性
3. 有效性
4. 清晰性

缺点：

1. 效率不高
2. 不能表达结构性知识

适合产生式表示的知识：
（1）领域知识间关系不密切，不存在结构关系。
（2）经验性及不确定性的知识，且相关领域中对这些知识没有严格、统一的理论。
（3）领域问题的求解过程可被表示为一系列相对独立的操作，且每个操作可被表示为一条或多条产生式规则。

框架表示法

一种结构化的知识表示方法。
框架（frame）：一种描述所论对象（一个事物、事件或概念）属性的数据结构。
一个框架由若干个被称为“槽”（slot）的结构组成，每一个槽又可根据实际情况划分为若干个“侧面”（faced）。
一个槽用于描述所论对象某一方面的属性。
一个侧面用于描述相应属性的一个方面。
槽和侧面所具有的属性值分别被称为槽值和侧面值。

框架表示法的特点

1. 结构性
2. 继承性
3. 自然性

知识图谱

知识图谱是一种互联网环境下的知识表示方法。目的是为了提高搜索引擎的能力，改善用户的搜索质量以及搜索体验。Google、百度和搜狗等搜索引擎公司构建的知识图谱，分别称为知识图谱、知心和知立方。

知识图谱的定义

知识图谱（Knowledge Graph/Vault），又称科学知识图谱，用各种不同的图形等可视化技术描述知识资源及其载体，挖掘、分析、构建、绘制和显示知识及它们之间的相互联系。
知识图谱是由一些相互连接的实体及其属性构成的。
三元组是知识图谱的一种通用表示方式：
（实体1-关系-实体2）
（实体-属性-属性值）
知识图谱可被看作是一张图，图中的节点表示实体或概念，而图中的边则由属性或关系构成。

知识图谱的架构

知识图谱的逻辑架构：模式层与数据层
数据层：主要是由一系列的事实组成，而知识以事实为单位进行存储。
模式层：构建在数据层之上，是知识图谱的核心。

获取知识的资源对象大体可分为：
结构化数据：知识定义和表示都比较完善的数据。
半结构化数据：部分数据是结构化的，但存在大量结构化程度较低的数据。
非结构化数据：没有定义和规范约束的自由数据。

知识图谱的构建

知识图谱的构建是指从最原始数据出发,采用一系列自动或者半自动的技术手段, 提取知识事实,并将其存入知识库的数据层和模式层。
这一过程包含：知识提取、知识表示、知识融合、知识推理四个过程。
主要有两种构造方式：
（1）自顶向下指的是先为知识图谱定义好本体与数据模式，再将实体加入到知识库。
（2）自底向上指的是从一些开放链接数据中提取出实体，选择其中置信度较高的加入到知识库，再构建顶层的本体模式。
经典应用：

• 维基百科
• DBpedia
• YAGO
• XLORE

知识图谱的特点

1. 精确性
2. 多样性
3. 可解释性

第五章 搜索求解策略

搜索的概念

问题求解：

• 问题的表示
• 求解方法（搜素法，归约法，归结法，推理法，产生式）

搜索中需要解决的基本问题：
（1）是否一定能找到一个解。
（2）找到的解是否是最佳解。
（3）时间与空间复杂性如何。
（4）是否终止运行或是否会陷入一个死循环。

搜索的主要过程：
(1) 从初始或目的状态出发，并将它作为当前状态。
(2) 扫描操作算子集，将适用当前状态的一些操作算子作用于当前状态而得到新的状态，并建立指向其父结点的指针 。
(3) 检查所生成的新状态是否满足结束状态，如果满足，则得到问题的一个解，并可沿着有关指针从结束状态反向到达开始状态，给出一解答路径；否则，将新状态作为当前状态，返回第(2)步再进行搜索。

搜索策略的类型

搜索方向

1. 数据驱动：从初始状态出发的正向搜索。
2. 目的驱动：从目的的状态出发的逆向搜索。
3. 双向搜素：同时从目的状态和初始状态搜索。

盲目搜索和启发式搜索

1. 盲目搜索：在不具有对特定问题的任何有关信息的条件下，按固有的步骤（依次或随机调用操作算子）进行的搜索。
2. 启发式搜索：考虑特定问题领域可应用的知识，动态地确定调用操作算子的步骤，优先选择较适合的操作算子，尽量减少不必要的搜索，以求尽快地到达结束状态。

状态空间的搜索策略

状态空间表示法

状态：表示系统状态、事实等叙述型知识的一组变量或数组：

操作：表示引起状态变化的过程型知识的一组关系或函数：

状态空间：利用状态变量和操作符号，表示系统或者问题的有关知识的符号体系，状态空间是一个四元组：

求解路径：从S0结点到G结点的路径。
状态空间解： 一个有限的操作算子序列。

实例

八数码问题
旅行商问题

盲目的图搜索策略

回溯策略

带回溯策略的搜索：
●从初始状态出发，不停地、试探性地寻找路径，直到它到达目的或“不可解结点”，即“死胡同”为止。
●若它遇到不可解结点就回溯到路径中最近的父结点上，查看该结点是否还有其他的子结点未被扩展。若有，则沿这些子结点继续搜索；如果找到目标，就成功退出搜索，返回解题路径。

广度优先策略

以接近起始节点的程度（深度）为依据，进行逐层扩展的节点搜索方法。
特点:

1. 每次选择深度最浅的节点首先扩展，搜索是逐层进行的；
2. 一种高价搜索，但若有解存在，则必能找到它。
   
   
   
   OPEN表（NPS表）：已经生成出来但其子状态未被扩展的状态，特点：先进先出。
   CLOSED表（PS表和NSS表的合并）：记录了已被生成扩展过的状态。

深度优先策略

首先扩展最新产生的节点, 深度相等的节点按生成次序的盲目搜索。
特点：扩展最深的节点的结果使得搜索沿着状态空间某条单一的路径从起始节点向下进行下去；仅当搜索到达一个没有后裔的状态时，才考虑另一条替代的路径。
算法：
防止搜索过程沿着无益的路径扩展下去，往往给出一个节点扩展的最大深度——深度界限；
与宽度优先搜索算法最根本的不同：将扩展的后继节点放在OPEN表的前端。
深度优先搜索算法的OPEN表后进先出。


在深度优先搜索中，当搜索到某一个状态时，它所有的子状态以及子状态的后裔状态都必须先于该状态的兄弟状态被搜索。
为了保证找到解，应选择合适的深度限制值，或采取不断加大深度限制值的办法，反复搜索，直到找到解。
深度优先搜索并不能保证第一次搜索到的某个状态时的路径是到这个状态的最短路径。
对任何状态而言，以后的搜索有可能找到另一条通向它的路径。如果路径的长度对解题很关键的话，当算法多次搜索到同一个状态时，它应该保留最短路径。

启发式图搜索策略

启发式策略

启发式信息

用来简化搜索过程有关具体问题领域的特性的信息叫做启发信息。

启发式图搜索策略

启发式图搜索策略（利用启发信息的搜索方法）的特点：重排OPEN表，选择最有希望的节点加以扩展。
种类：A、A*算法等

运用启发式策略的两种基本情况

（1）一个问题由于存在问题陈述和数据获取的模糊性，可能会使它没有一个确定的解。
（2）虽然一个问题可能有确定解，但是其状态空间特别大，搜索中生成扩展的状态数会随着搜索 的深度呈指数级增长。

启发信息和估价函数

启发信息

在具体求解中，能够利用与该问题有关的信息来简化搜索过程，称此类信息为启发信息。

启发式搜索：利用启发信息的搜索过程。

求解问题中能利用的大多是非完备的启发信息：
（1）求解问题系统不可能知道与实际问题有关的全部信息，因而无法知道该问题的全部状态空间，也不可能用一套算法来求解所有的问题。
（2）有些问题在理论上虽然存在着求解算法，但是在工程实践中，这些算法不是效率太低，就是根本无法实现。

按运用的方法分类：

1. 陈述性启发信息：用于更准确，更精炼地描述状态
2. 过程性启发信息：用于构造操作算子
3. 控制性启发信息：表示控制策略的知识

按作用分类

1. 用于扩展结点的选择：用于决定应先扩展哪一个节点，以免盲目扩展。
2. 用于生成节点的选择：用于决定要生成哪些后继节点，以免盲目生成过多无用的节点。
3. 用于删除节点的选择：用于决定删除哪些无用节点，以免造成进一步的时空浪费。

估价函数

估价函数（evaluation function）：估算节点“希望”程度的量度。
估价函数值 f(n) ：从初始节点经过 n节点到达目标节点的路径的最小代价估计值，其一般形式是

g(n)：从初始节点 S0 到节点 n 的实际代价 ；
h(n)：从节点 n 到目标节点 Sg 的最优路径的估计代价，称为启发函数。
注：
h(n) 比重大：降低搜索工作量，但可能导致找不到最优解；
h(n) 比重小：一般导致工作量加大，极限情况下变为盲目搜索，但可能可以找到最优解。

A搜索算法

使用了估价函数 f 的最佳优先搜索。

A*算法

特点：

1. 可接纳性（当一个搜索算法在最短路径存在时能保证找到它，就称该算法是可采纳的。）
2. 单调性（A*搜索算法中采用单调性启发函数，可以减少比较代价和调整路径的工作量，从而减少搜索代价。）
3. 信息性（在两个 A* 启发策略的h1和h2中，如果对搜索空间中的任一状态n都有h1(n) ≤ h2(n)，就称策略h2比h1具有更多的信息性。如果某一搜索策略的h(n)越大，则 A* 算法搜索的信息性越多，所搜索的状态越少。但更多的信息性需要更多的计算时间，可能抵消减少搜索空间所带来的益处。）
   

第六章 智能计算及其应用

进化算法

进化算法(evolutionary algorithms，EA)是基于自然选择和自然遗传等生物进化机制的一种搜索算法。
生物进化是通过繁殖、变异、竞争和选择实现的；而进化算法则主要通过选择、重组和变异这三种操作实现优化问题的求解。
进化算法是一个“算法簇”，包括遗传算法(GA)、遗传规划、进化策略和进化规划等(区别)。
进化算法的基本框架是遗传算法所描述的框架（简单描述）。
进化算法是高健壮性和广泛适用性的全局优化方法，广泛应用于组合优化、机器学习等领域（优点）。
进化算法的设计原则
（1）适用性原则：一个算法的适用性是指该算法所能适用的问题种类，它取决于算法所需的限制与假定。
（2）可靠性原则：算法的可靠性是指算法对于所设计的问题，以适当的精度求解其中大多数问题的能力。
（3）收敛性原则： 指算法能否收敛到全局最优。在收敛的前提下，希望算法具有较快的收敛速度。
（4）稳定性原则： 指算法对其控制参数及问题的数据的敏感度。
（5）生物类比原则：生物界有效方法及操作可以通过类比的方法引入到算法中，有时会带来较好的结果。

遗传算法

一类借鉴生物界自然选择和自然遗传机制的随机搜索算法,非常适用于处理传统搜索方法难以解决的复杂和非线性优化问题。
不同问题有不同的编码方法来表示问题的可行解,也有不同的遗传算子用来模仿不同环境下的生物遗传。这就构成了各种遗传算法。但它们都是通过对生物遗传和进化过程中选择、交叉、变异机理的模仿,来完成对问题最优解的自适应搜索。基本遗传算法只使用选择、交叉和变异算子三种基本遗传算子。


遗传算法的基本思想：
在求解问题时从多个解开始，然后通过一定的法则进行逐步迭代以产生新的解。

位串编码

位串编码：
一维染色体编码方法：将问题空间的参数编码为一维排列的染色体的方法。

二进制编码

二进制编码：用若干二进制数表示一个个体，将原问题的解空间映射到位串空间 B={0，1}上，然后在位串空间上进行遗传操作。
优点：
类似于生物染色体的组成，算法易于用生物遗传理论解释，遗传操作如交叉、变异等易实现；算法处理的模式数最多。
缺点：
① 相邻整数的二进制编码可能具有较大的Hamming距离，降低了遗传算子的搜索效率。
15：01111 16： 10000
② 要先给出求解的精度。
③ 求解高维优化问题的二进制编码串长，算法的搜索效率低。

Gray编码

Gray编码:将二进制编码通过一个变换进行转换得到的编码。

任意两个相邻的代码只有一位二进制数不同。

实数编码

采用实数表达法不必进行数制转换，可直接在解的表现型上进行遗传操作。
多参数映射编码的基本思想：把每个参数先进行二进制编码得到子串，再把这些子串连成一个完整的染色体。
多参数映射编码中的每个子串对应各自的编码参数，所以，可以有不同的串长度和参数的取值范围。

群体设定

1. 初始种群的产生：
   ●随机产生群体规模数目的个体作为初始群体。
   ●随机产生一定数目的个体，从中挑选最好的个体加到初始群体中。这种过程不断迭代，直到初始群体中个体数目达到了预先确定的规模。
   ●根据问题固有知识，把握最优解所占空间在整个问题空间中的分布范围，然后，在此分布范围内设定初始群体。
2. 种群规模的确定：
   群体规模太小，遗传算法的优化性能不太好，易陷入局部最优解。
   群体规模太大，计算复杂。

适应度函数

选择

• 选择操作也称为复制（reproduction）操作：从当前群体中按照一定概率选出优良的个体，使它们有机会作为父代繁殖下一代子孙。
• 判断个体优良与否的准则是各个个体的适应度值：个体适应度越高，其被选择的机会就越多。（和确定定优化方的区别）

个体选择概率分配方法

适应度比例方法（fitness proportional model）或蒙特卡罗法（Monte Carlo） ：
各个个体被选择的概率和其适应度值成比例。
个体i被选择的概率为：
排序方法 （rank-based model）：

1. 线性排序：J. E. Baker
   
2. 非线性排序： Z. Michalewicz
   
   

选择个体方法

1. 转盘赌选择
   按个体的选择概率产生一个轮盘，轮盘每个区的角度与个体的选择概率成比例。
   产生一个随机数，它落入转盘的哪个区域就选择相应的个体交叉。
2. 锦标赛选择方法（tournament selection model）
   锦标赛选择方法：从群体中随机选择k个个体，将其中适应度最高的个体保存到下一代。这一过程反复执行，直到保存到下一代的个体数达到预先设定的数量为止。
   随机竞争方法（stochastic tournament）：每次按赌轮选择方法选取一对个体，然后让这两个个体进行竞争，适应度高者获胜。如此反复，直到选满为止。
3. 最佳个体保存方法
   最佳个体（elitist model）保存方法：把群体中适应度最高的个体不进行交叉而直接复制到下一代中，保证遗传算法终止时得到的最后结果一定是历代出现过的最高适应度的个体。

交叉

基本的交叉算子

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

修正的交叉方法

部分匹配交叉PMX：Goldberg D. E.和R. Lingle(1985)

变异

●位点变异：群体中的个体码串，随机挑选一个或多个基因座，并对这些基因座的基因值以变异概率作变动。
● 逆转变异：在个体码串中随机选择两点（逆转点），然后将两点之间的基因值以逆向排序插入到原位置中。
● 插入变异：在个体码串中随机选择一个码，然后将此码插入随机选择的插入点中间。
● 互换变异：随机选取染色体的两个基因进行简单互换。
● 移动变异：随机选取一个基因，向左或者向右移动一个随机位数。

遗传算法的一般步骤

遗传算法的改进

双倍体遗传算法

基本思想：
双倍体遗传算法采用显性和隐性两个染色体同时进行进化，提供了一种记忆以前有用的基因块的功能。
双倍体遗传算法采用显性遗传。
双倍体遗传延长了有用基因块的寿命，提高了算法的收敛能力，在变异概率低的情况下能保持一定水平的多样性。
双倍体遗传算法的设计：
（1）编码/解码：两个染色体（显性、隐性）
（2）复制算子：计算显性染色体的适应度，按照显性染色体 的复制概率将个体复制到下一代群体中。
（3）交叉算子：两个个体的显性染色体交叉、隐性染色体也同时交叉。
（4）变异算子：个体的显性染色体按正常的变异概率变异；隐性染色体按较大的变异概率变异。
（5）双倍体遗传算法显隐性重排算子：个体中适应值较大的染色体设为显性染色体，适应值较小的染色体设为隐性染色体。

双种群遗传算法

基本思想：
在遗传算法中使用多种群同时进化，并交换种群之间优秀个体所携带的遗传信息，以打破种群内的平衡态达到更高的平衡态，有利于算法跳出局部最优。
多种群遗传算法：建立两个遗传算法群体，分别独立地运行复制、交叉、变异操作，同时当每一代运行结束以后，选择两个种群中的随机个体及最优个体分别交换。
双种群遗传算法的设计
● 编码/解码设计
● 交叉算子、变异算子
● 杂交算子
设种群A与种群B，当A与B种群都完成了选择、交叉、变异算子后，产生一个随机数num，随机选择A中num个个体与A中最优个体，随机选择B中num个个体与B中最优个体，交换两者，以打破平衡态。

群智能算法

群智能算法（swarm algorithms，SI）：受动物群体智能启发的算法。
群体智能：由简单个体组成的群落与环境以及个体之间的互动行为。
群智能算法包括：粒子群优化算法、蚁群算法、蜂群算法
遗传算法：模拟种群的达尔文主义进化
群智能算法：模拟群体中个体之间的相互作用与分布式协同行为

粒子群优化算法

基本思想：
将每个个体看作n维搜索空间中一个没有体积质量的粒子，在搜索空间中以一定的速度飞行，该速度决定粒子飞行的方向和距离。所有粒子有一个由优化函数决定的适应值。
基本原理：
PSO初始化为一群随机粒子，然后通过迭代（与进化算法不同）找到最优解。在每一次迭代中，粒子通过跟踪两个“极值”来更新自己。第一个就是粒子本身所找到的最优解，这个解称为个体极值。另个一是整个种群目前找到的最优解，这个解称为全局极值。
粒子群优化算法的流程：
（1）初始化每个粒子。在允许范围内随机设置每个粒 子的初始位置和速度。
（2）评价每个粒子的适应度。计算每个粒子的目标函数。
（3）设置每个粒子的 pi。对每个粒子，将其适应度与其经 历过的最好位置pi进行比较，如果优于pi，则将其作为该粒子的最好位置pi 。
（4）设置全局最优值pg。对每个粒子，将其适应度与群体经历过的最好位置pg进行比较，如果优于pg，则将其作为当前群体的最好位置pg 。
（5）更新粒子的速度和位置。根据式（6.20）更新粒子的速度和位置。
（6）检查终止条件。如果未达到设定条件（预设误差或者迭代的次数），则返回第（2）步。

蚁群算法

基本思想：
信息素跟踪：按照一定的概率沿着信息素较强的路径觅食。
信息素遗留：会在走过的路上会释放信息素，使得在一定的范围内的其他蚂蚁能够觉察到并由此影响它们的行为。
（1）环境：有障碍物、有其他蚂蚁、有信息素。
（2）觅食规则：范围内寻找是否有食物，否则看是否有信息素，每只蚂蚁都会以小概率犯错。
（3）移动规则：都朝信息素最多的方向移动，无信息素则继续朝原方向移动，且有随机的小的扰动，有记忆性。
（4）避障规则：移动的方向如有障碍物挡住，蚂蚁会随机选择另一个方向。
（5）信息素规则：越靠近食物播撒的信息素越多，越离开食物播撒的信息素越少。

蚂蚁圈系统（Ant-cycle System）

蚂蚁数量系统（Ant-quantity System）

蚂蚁密度系统（Ant-density System）

三种模型比较

全局信息更新方法

优点：
保证了残留信息素不至于无限累积；
如果路径没有被选中，那么上面的残留信息素会随时间的
推移而逐渐减弱，这使算法能“忘记”不好的路径；
即使路径经常被访问也不至于因为累积，而使期望值的作用无法体现；
充分体现了算法中全局范围内较短路径(较好解)的生存能力；
加强了信息正反馈性能；
提高了系统搜索收敛的速度。

蚁群算法的参数选择

信息素启发因子
反映了蚁群在路径搜索中随机性因素作用的强度；
值越大，蚂蚁选择以前走过的路径的可能性越大，搜索的随机性减弱；
当值过大时会使蚁群的搜索过早陷于局部最优。

期望值启发式因子

反映了蚁群在路径搜索中先验性、确定性因素作用的强度；
值越大，蚂蚁在某个局部点上选择局部最短路径的可能性越大；
虽然搜索的收敛速度得以加快，但蚁群在最优路径的搜索过程中随机性减弱，易于陷入局部最优。

信息素挥发度

当要处理的问题规模比较大时，会使那些从来未被搜索到的路径(可行解)上的信息量减小到接近于0，因而降低了算法的全局搜索能力；
而且当值过大时，以前搜索过的路径被再次选择的可能性过大，也会影响到算法的随机性能和全局搜索能力；
反之，通过减小信息素挥发度值虽然可以提高算法的随机性能和全局搜索能力，但又会使算法的收敛速度降低。

第七章 机器学习

机器学习概论

机器学习是从人工智能中产生的一个重要学科分支，是实现智能化的关键。
机器学习（Machine Learning）是一门多领域交叉学科，涉及概率论、统计学、逼近论、凸分析、算法复杂度理论等多门学科 。专门研究计算机怎样模拟或实现人类的学习行为，以获取新知识或技能，重新组织已有的知识结构使之不断改善自身的性能。
机器学习三要素：模型，策略，算法

机器学习方法

有监督学习

有监督学习（supervised learning）：从给定的有标注的训练数据集中学习出一个函数（模型参数），当新的数据到来时可以根据这个函数预测结果。 常见任务包括分类与回归。

无监督学习

无监督学习（unsupervised learning）：没有标注的训练数据集，需要根据样本间的统计规律对样本集进行分析，常见任务如聚类等。

半监督学习

半监督学习（Semi-supervised learning）：结合（少量的）标注训练数据和（大量的）未标注数据来进行数据的分类学习。

两个基本假设：
• 聚类假设：处在相同聚类中的样本示例有较大的可能拥有相同的标记。
• 流形假设：处于一个很小的局部区域内的样本示例具有相似的性质，因此，其标记也应该相似

增强学习

增强学习（Reinforcement Learning）：外部环境对输出只给出评价信息而非正确答案，学习机通过强化受奖励的动作来改善自身的性能。

多任务学习

**多任务学习（Multi-task Learning）：把多个相关（related）的任务放在一起同时学习。**单任务学习时，各个任务之间的模型空间（Trained Model）是相互独立的，但现实世界中很多问题不能分解为一个一个独立的子问题，且这样忽略了问题之间所包含的丰富的关联信息。多任务学习就是为了解决这个问题而诞生的。多个任务之间共享一些因素，它们可以在学习过程中，共享它们所学到的信息，相关联的多任务学习比单任务学习具备更好的泛化（generalization）效果。

机器学习面临的问题

◆数据稀疏性：训练一个模型，需要大量（标注）数据，但是数据往往比较稀疏。
◆高数量和高质量标注数据需求：获取标定数据需要耗费大量人力和财力。而且，人会出错，有主观性。
◆冷启动问题：对于一个新产品，在初期，要面临数据不足的冷启动问题。
◆泛化能力问题：训练数据不能全面、均衡的代表真实数据。
◆模型抽象困难：总结归纳实际问题中的数学表示非常困难。
◆模型评估困难：在很多实际问题中，很难形式化的、定量的评估一个模型结果的好坏。
◆寻找最优解困难：要解决的实际问题非常复杂，将其形式化后的目标函数也非常复杂，往往在目前还不存在一个有效的算法能找到目标函数的最优值。

机器学习准备

数据预处理

数据清洗

对各种脏数据进行对应方式的处理，得到标准、干净、连续的数据，提供给数据统计、数据挖掘等使用。
数据的完整性
数据的合法性
数据的唯一性
数据的权威性
数据的一致性

数据采样

数据不平衡（imbalance）：指数据集的类别分布不均。比如说一个二分类问题，100个训练样本，比较理想的情况是正类、负类样本的数量相差不多；而如果正类样本有99个、负类样本仅1个，就意味着存在类不平衡。此时预测时就算全部为正，准确率也可以达到99%，这并不能反映模型的好坏。面临不平衡数据集的时候，传统的机器学习模型的评价方法不能精确地衡量模型的性能。
解决方法：
过采样（Over-Sampling）
通过随机复制少数类来增加其中的实例数量，从而可增加样本中少数类的代表性。
欠采样（Under-Sampling）
通过随机地消除占多数的类的样本来平衡类分布；直到多数类和少数类的实例实现平衡。

数据集拆分

机器学习中将数据划分为3份：
① 训练数据集（train dataset）：用来构建机器学习模型
② 验证数据集（validation dataset）：辅助构建模型，用于在构建过程中评估模型，提供无偏估计，进而调整模型参数
③ 测试数据集（test dataset）：用来评估
常用拆分方法：
留出法（Hold-Out）：直接将数据集划分为互斥的集合，如通常选择 70% 数据作为训练集，30% 作为测试集。需要注意的是保持划分后集合数据分布的一致性，避免划分过程中引入额外的偏差而对最终结果产生影响。
K-折交叉验证法：将数据集划分为 k 个大小相似的互斥子集，并且尽量保证每个子集数据分布的一致性。这样，就可以获取 k 组训练 - 测试集，从而进行 k 次训练和测试，k通常取值为10。

特征工程

特征选择

• 过滤法
• 包裹法
• 嵌入法
  

特征降维

特征选择完成后，可能由于特征矩阵过大，导致计算量大、训练时间长，因此降低特征矩阵维度也是必不可少的。
主成分分析(PCA)：
将原始特征空间映射到彼此正交的特征向量空间，在非满秩的情况下使用SVD分解来构建特征向量。
线性判别分析(LDA)：
给出一个标注了类别的数据集，投影到了一条直线之后，能够使得点尽量的按类别区分开。

特征编码

数据集中经常会出现字符串信息，例如男女、高中低等，这类信息不能直接用于算法计算，需要将这些数据转化为数值形式进行编码，便于后期进行建模。

• one-hot编码
• 语义编码
  
  

规范化

不同属性具有不同量级时会导致：
①数量级的差异将导致量级较大的属性占据主导地位；
②数量级的差异将导致迭代收敛速度减慢；
③依赖于样本距离的算法对于数据的数量级非常敏感。

机器学习方法分类

分类问题

分类问题是监督学习的一个核心问题，它从数据中学习一个分类决策函数或分类模型(分类器（classifier）)，对新的输入进行输出预测，输出变量取有限个离散值。

K近邻分类

工作原理：计算待测样本和所有训练样本点距离，用前K个距离最小的样本点进行投票，待测样本点的类别为得票最多的类
优点：

• 简单
• 无需训练
  缺点：
• 对参数选择敏感
• 计算量大
  

决策树

决策树（decision tree）是一个树结构，每个非叶节点表示一个特征属性，每个分支边代表这个
特征属性在某个值域上的输出，每个叶节点存放一个类别。
决策过程：从根节点开始，测试待分类项中相应的特征属性，并按照其值选择输出分支，直到到达
叶子节点，将叶子节点存放的类别作为决策结果。
给定训练数据，如何构建决策树呢？

1. 特征选择：选取对训练数据具有分类能
   力的特征。
2. 决策树生成：在决策树各个点上按照一
   定方法选择特征，递归构建决策树。
3. 决策树剪枝：在已生成的树上减掉一些
   子树或者叶节点，从而简化分类树模型。
   
   

贝叶斯分类

贝叶斯分类是基于贝叶斯定理和属性特征条件独立性的分类方法。

SVM（支持向量机）

支持向量机（Support Vector Machine ）
是一种有监督学习方法，它尝试寻找一个最优决
策边界，使距离两个类别最近的样本最远。



支持向量机（Support Vector Machine ,SVM）是一种有监督学习方法，它尝试寻找一个最优决策边界，使距离两个类别最近的样本最远，从而对分类问题提供良好的泛化能力。
SVM的优点：
✓ 相对于其他训练分类算法不需要过多样本，并且由于
SVM引入了核函数，所以SVM可以处理高维样本
✓ 结构风险最小。这种风险是指分类器对问题真实模型的逼
近与问题真实解之间的累积误差
✓ 非线性，是指SVM擅长应付样本数据线性不可分的情况，
主要通过松弛变量（也叫惩罚变量）和核函数技术来实现，
这一部分也正是SVM的精髓所在。

多分类SVM

一对多法（one-versus-rest,简称OVR SVMs）
训练时依次把某个类别的样本归为一类,其他剩余的样本归为另一类，这样k个类别的样本就构造出了k个SVM。分类时将未知样本分类为具有最大分类函数值的那类。
一对一法（one-versus-one,简称OVO SVMs或者pairwise）
其做法是在任意两类样本之间设计一个SVM，因此k个类别的样本就需要设计k(k-1)/2个SVM。
当对一个未知样本进行分类时，最后得票最多的类别即为该未知样本的类别。
层次支持向量机
层次分类法首先将所有类别分成两个子类，再将子类进一步划分成两个次级子类，如此循环，直到得到一个单独的类别为止。

逻辑回归

logistic回归是一个分类算法，它可以处理二元分类以及多元分类。首先逻辑回归构造广义的线
性回归函数，然后使用sigmoid函数将回归值映射到离散类别。

集成学习

集成学习通过将多个弱分类器集成在一起，使它们共同完成学习任务，构建一个强分类器。潜在哲学思想是“三个臭皮匠赛过诸葛亮”。
理论基础
强可学习：在PAC学习框架中，一个概念，如果存在一个多项式的学习算法能够学习它，并且正确率很高，那么就称这个概念是强可学习的。
弱可学习：如果存在一个多项式的学习算法能够学习它，学习的正确率比随机猜测略好，那么就称这个概念是弱可学习的。Schapire证明强可学习与弱可学习是等价的，也就是说，在PAC学习框架下，一个概念强可学习的充分必要条件是这个概念弱可学习的。
两类集成方法
Bagging(bootstrap aggregating)
Boosting（提升方法）

严格意义上来说，这不算是一种机器学习算法，而更像是一种优化手段或者策略，它通常是结合多个简单的弱机器学习算法，去做更可靠的决策。类似于开会做决策。
优点：
当先最先进的预测几乎都使用了算法集成。它比使用单个模型预测出来的结果要精确的多，在各大竞赛中得到了普遍应用。
缺点：
需要大量的维护工作

回归问题

回归分析用于预测输入变量（自变量）和输出变量（因变量）之间的关系，特别是当输入变量的值发生变化时，输出变量值随之发生变化。

线性回归

线性回归算法假设特征和结果满足线性关系。这就意味着可以将输入项分别乘以一些常量，再将结果加起来得到输出。

岭回归

岭回归应用结构风险最小化的模型选择策略，在经验风险最小化的基础上加入正则化因子。当正
则化因子选择为模型参数的二范数的时候，整个回归的方法就叫做岭回归。

Lasso回归

Lasso回归是一种压缩估计。它通过构造一个惩罚函数得到一个较为精炼的模型，使得它压缩一些
系数，同时设定一些系数为零。因此保留了子集收缩的优点，是一种处理具有复共线性数据的有偏估计。

聚类问题

聚类问题是无监督学习的问题，算法的思想就是“物以类聚，人以群分”。聚类算法感知样本间的相似度，进行类别归纳，对新的输入进行输出预测，输出变量取有限个离散值。
 可以作为一个单独过程，用于寻找数据内在的分布结构
 可以作为分类、稀疏表示等其他学习任务的前驱过程

K-means

K-means（又称k-均值或k-平均）聚类算法。算法思想就是首先随机确定k个中心点作为聚类中
心，然后把每个数据点分配给最邻近的中心点，分配完成后形成k个聚类，计算各个聚类的平均中心点，将其作为该聚类新的类中心点，然后重复迭代上述步骤直到分配过程不再产生变化。

高斯混合模型

高斯混合模型（Gaussian Mixed Model）指的是多个高斯分布函数的线性组合，是一种广泛使用
的聚类算法，该方法使用了高斯分布作为参数模型。


混合高斯和K-means很相似，相似点在于两者的分类受初始值影响；两者可能限于局部最优解；
两者类别的个数都要靠猜测。混合高斯计算复杂度高于K-means。
K-means属于硬聚类，要么属于这类，要么属于那类，而GMM属于混合式软聚类，一个样本
70%属于A，30%属于B

密度聚类

密度聚类算法假设聚类结构能通过样本分布的紧密程度确定，算法从样本密度的角度来考察样本之间的可连接性，并基于可连接样本不断扩展聚类簇以获得最终的聚类结果。

层次聚类

层次聚类算法试图在不同层次对数据集进行划分，从而形成树形的聚类结构。数据集的划
分可采用“自底向上”的聚合策略，也可采用“自顶向下”的分拆策略。

机器学习模型评估

性能评价指标-分类

准确率(Accuracy)是指在分类中，分类正确的记录个数占总记录个数的比。
召回率(Recall)也叫查全率，是指在分类中，样本中的正例有多少被预测正确了。
通常，准确率高时，召回率偏低；召回率高时，准确率偏低。

性能评价指标-回归

性能评价指标-聚类

模型选择

第八章 人工神经网络

神经网络的结构与工作方式

决定人工神经网络性能的三大要素

1. 神经元的特性
2. 神经元之间相互连接的形式：拓扑结构
3. 为适应环境而改善性能的学习规则

神经网络的结构

前馈型（ 前向型）

反馈型

神经网络的工作方式

同步（并行）方式：任一时刻神经网络中所有神经元同时调整状态。
异步（串行）方式：任一时刻只有一个神经元调整状态，而其它神经元的状态保持不变。

神经网络的学习

神经网络方法是一种知识表示方法和推理方法。
神经网络知识表示是一种隐式的表示方法。

1944年赫布（Hebb）提出了改变神经元连接强度的Hebb学习规则。
Hebb学习规则：当某一突触两端的神经元同时处于兴奋状态，那么该连接的权值应该增强。

BP神经网络

工作过程

第一阶段或网络训练阶段：
对网络的连接权进行学习和调整，以使该网络实现给定样本的输入输出映射关系。

第二阶段或称工作阶段：
把实验数据或实际数据输入到网络，网络在误差范围内预测计算出结果。

BP学习算法

BP算法的实现

（1） 隐层数及隐层神经元数的确定：目前尚无理论指导。
（2）初始权值的设置：一般以一个均值为0的随机分布设置网络的初始权值。
（3）训练数据预处理：线性的特征比例变换，将所有的特征变换到[0，1]或者[-1，1]区间内，使得在每个训练集上，每个特征的均值为0，并且具有相同的方差。
（4）后处理过程：当应用神经网络进行分类操作时，通常将输出值编码成所谓的名义变量，具体的值对应类别标号。

BP算法的特点

BP网络：多层前向网络（输入层、隐层、输出层）。
连接权值：通过Delta学习算法进行修正。
神经元传输函数：S形函数。
学习算法：正向传播、反向传播。
层与层的连接是单向的，信息的传播是双向的。

优点：
有很好的逼近特性。
具有较强的泛化能力。
具有较好的容错性。

缺点：
收敛速度慢。
局部极值。
难以确定隐层和隐层节点的数目。

BP神经网络在模式识别中的应用

式识别研究用计算机模拟生物、人的感知，对模式信息，如图像、文字、语音等，进行识别和分类。
传统人工智能的研究部分地显示了人脑的归纳、推理等智能。但是，对于人类底层的智能，如视觉、听觉、触觉等方面，现代计算机系统的信息处理能力还不如一个幼儿园的孩子。
神经网络模型模拟了人脑神经系统的特点：处理单元的广泛连接；并行分布式信息储存、处理；自适应学习能力等。
神经网络模式识别方法具有较强的容错能力、自适应学习能力、并行信息处理能力。

举例：设计一个三层BP网络对数字0至9进行分类。

卷积神经网络（Convolutional Neural Networks，CNN）

CNN是一个多层的神经网络，每层由多个二维平面组成，而每个平面由多个独立神经元组成。
C层为特征提取层（卷积层）
S层是特征映射层（下采样层）。
CNN中的每一个C层都紧跟着一个S层。

特征提取层（卷积层）——C层（Convolution layer）

大部分的特征提取都依赖于卷积运算。
利用卷积算子对图像进行滤波，可以得到显著的边缘特征。

池化

●通过卷积获得了特征之后，如果直接利用这些特征训练分类器，计算量是非常大的。
●对不同位置的特征进行聚合统计,称为池化 (pooling)。
●池化常用方法：平均池化、最大池化。
●卷积神经网络在池化层丢失大量的信息，从而降低了空间分辨率，导致了对于输入微小的变化，其输出几乎是不变的。

卷积神经网络存在问题

CNN中没有可用的空间信息。
CNN没有对空间的推理和理解能力，没有办法“举一反三”，去辨别图像不同姿态、位置。当图像角度发生改变时，CNN的识别变得困难。

解决办法：
对空间信息进行编码同时也计算物体的存在概率
用向量来表示，向量的模表示特征存在的概率，向量的方向表示特征的姿态信息。

针对卷积神经网络训练数据需求大、环境适应能力弱、可解释性差、数据分享难等不足，2017年10月，Geoffrey E. Hinton教授等在 “神经信息处理系统大会上发表论文，提出了新型神经网络结构——胶囊网络（Capsule Networks）。
胶囊是一个包含多个神经元的载体，每个神经元表示了图像中出现的特定实体的各种属性。
胶囊不是传统神经网络中的一个神经元，而是一组神经元。
胶囊网络的核心思想：胶囊里封装的检测特征的相关信息是以向量的形式存在的，胶囊的输入是一个向量，是用一组神经元来表示多个特征。

生成对抗网络

深度学习的模型可大致分为判别式模型和生成式模型。
目前深度学习取得的成果主要集中在判别式模型。
判别模型是将一个高维的感官输入映射为一个类别标签。
生成网络把随机点变成与数据集相似的图片。

如何识别一只羊？
判别式模型：要确定一个羊是山羊还是绵羊，用判别式模型的方法是从历史数据中学习到模型，然后通过提取这只羊的特征来预测出这只羊是山羊的概率，是绵羊的概率。
生成式模型：是根据山羊的特征首先学习出一个山羊的模型，然后根据绵羊的特征学习出一个绵羊的模型，然后从这只羊中提取特征，放到山羊模型中看概率是多少，再放到绵羊模型中看概率是多少，哪个大就是哪个。

生成对抗网络的结构与训练

GAN的两个相互交替的训练阶段：
●固定生成网络，训练判别网络
●固定判别网络，训练生成网络
两个网络相互对抗的过程，就是各自网络参数不断调整的过程，即学习过程。
GAN极大地提高图像生成质量，进一步推动了计算机视觉领域的发展。

GAN在训练中容易出现一些问题，训练过程具有强烈的不稳定性，实验结果随机，具体表现：
● 训练过程难以收敛，经常出现震荡；
● 训练收敛，但是出现模式崩溃(model collapse)。
● 训练收敛，但是GAN还会生成一些没有意义或者现实中不可能出现的图片。

应用：图像处理（图像修复，图像风格迁移，图像翻译），语言处理，视频生成。

第十章 自然语言理解(nlp)

微观角度：从自然语言到机器内部的一个映射。
宏观角度：使机器能够执行人类所期望的某种语言功能。
自然语言处理研究实现人与计算机之间用自然语言进行有效通信的各种理论和方法。
自然语言处理发展经历了：基于规则的方法，基于统计学习的方法，基于深度学习的方法三个阶段。
自然语言处理由浅入深的四个层面：形式，语义，推理和语用。当前正处于由语义向推理的发展阶段。

研究内容

词法(Lexical)学：研究词的词素(morphemes)构成、词性等。
句法(Syntax)学：研究句子结构成分之间的相互关系和组成句子序列的规则 。
语义(Semantics)学：研究如何从一个语句中词的意义，以及这些词在该语句的句法结构中的作用来推导出该语句的意义。
语用(Pragmatics)学：研究在不同上下文中的语句的应用，以及上下文对语句理解所产生的影响。

具体实例

文本分类与聚类

文本分类(Text Classification)根据给定文档的内容或主题，自动分配预先定义的类别标签。
文本聚类(Text Clustering)根据文档之间的内容或主题相似度，将文档集合划分成若干个子集，每个子集内部的文档相似度较高，而子集之间的相似度较低。
文本分类模型：
基于机器学习的分类：朴素贝叶斯 (Naive Bayes)、支持向量机(SVM)、最大熵分类器
基于神经网络的方法：多层感知机(MLP) 、卷积神经网络(CNN) 、循环神经网络(RNN)
文本聚类模型：
基于距离的聚类：通过相似度函数计算语义关联度，然后根据语义关联度进行聚类，如K-means
基于概率模型的聚类：假设每篇文章是所有主题上的概率分布，典型的主题模型包括 PLSA 和 LDA 等

情感分析

情感分析(sentiment analysis)是指根据文本所表达的含义和情感信息将文本划分成褒义、贬义或多种类型，是对文本作者倾向性和观点、态度的划分，有时也称倾向性分析（opinion analysis）。
按粒度可分为词汇级、句子级和篇章级的情感分析，核心任务主要包含观点性及倾向性识别、观点要素抽取等任务。
基于词典的情感分析方法通过制定一系列的情感词典和规则，对文本进行拆句、分析及匹配词典，计算情感值进行文本的情感倾向判断。
基于机器学习的情感分析方法将情感分析作为一个分类问题来处理，基本流程与文本分类一致，采用支持向量机（SVM）、深度学习（CNN，RNN ， LSTM）等模型方法。

信息抽取

信息抽取是指从自然语言文本中抽取指定类型的实体、关系、事件等事实信息，并形成结构化数据输出的文本处理技术。
主要研究内容：
实体识别与抽取
实体消歧
关系抽取
事件抽取
命名实体识别(Named Entity Recognition)是识别文本中具有特定意义的实体，如人名、机构名、地名等专有名词和有意义的时间等，是信息检索、问答系统等技术的基础任务。
实体消歧是在非结构化文档中，由于书写风格和上下文的需要，同一个命名实体实体可能包含多种形式的表达（多对一），同时文档中的一个名词可能从字面意思上对应多种命名实体（一对多）。基本思路：利用实体间的交互、及上下文信息进行消歧，可采用图、概率生成模型，主题模型，深度学习等方法。
关系抽取指检测和识别文本中实体之间的语义关系。关系抽取的输出通常是一个三元组(实体1,关系类别,实体2)，表示实体1 和实体2之间存在特定类别的语义关系。
事件抽取指的是从非结构化文本中抽取事件信息，主要包括时间、地点、事件元素角色等，并将其以结构化形式呈现出来的任务。主要任务包括触发词和事件元素的提取等。

自动文摘

自动文摘是利用计算机按照某类应用自动地将文本（或文本集合）转换生成简短摘要的一种信息压缩技术。

信息推荐

信息推荐是指根据用户的习惯、偏好或兴趣，从不断到来的大规模信息中识别满足用户兴趣的信息的过程。广泛应用在电子商务、电影和视频、音乐、社交网络、阅读、基于位置的服务、个性化邮件和广告等。

自动问答

问答系统(question answering，简称QA)是讨论如何从大规模真实文本中对指定的提问找出正确回答的技术，是集知识表示、信息检索、自然语言处理和智能推理等技术于一身的新一代搜索引擎。Web形式的问答网站、聊天机器人等。
按照答案的生成反馈机制，问答系统可划分为：
基于检索式的问答系统
基于生成式的问答系统
检索式自动问答一般包括问句理解、信息检索、答案抽取三个功能组成部分。

语言处理过程的层次

文字表达句子的层次：词素→词或词形→词组或句子。
声音表达句子的层次：音素→音节→音词→音句。
语言处理过程分为五个层次：语音分析、词法分析、句法分析、语义分析和语用分析。
语用分析：研究语言所存在的外界环境对语言使用产生的影响。
构成单词发音的独立单元是音素。上下文不同而发音不同。
语音分析：根据音位规则，从语言流中区分出一个个独立的音素，再根据音位形态规则找出一个个音节及其对应的词素或词。

词法分析

词是自然语言中能够独立运用的最小单位，是语言信息处理的基本单位。
词法分析是对自然语言的形态(morphology) 进行分析，判断词的结构、类别和性质。
主要任务包括：
自动分词（segmentation）
命名实体识别（Named Entity Recognition）
词性标注（Part-of-Speech tagging, POS tagging）

分词算法

基于规则的分词方法
基本思想：按照一定策略将待分析的汉字串与一个“充分大的”机器词典中的词条进行匹配
主要方法：最大匹配、逆向最大匹配、双向最佳匹配、逐词遍历
基于统计的分词方法
基本思想：上下文中相邻的字同时出现的次数越多，就越有可能构成一个词，字与字相邻出现的概率或频率能较好地反映成词的可信度。
主要方法：N 元文法模型（N-gram）、隐马尔可夫模型（Hiden Markov Model，HMM）、最大熵模型（ME）、条件随机场模型（Conditional Random Fields，CRF）等
基于理解的分词方法
基本思想：在分词的同时进行句法、语义分析，利用句法信息和语义信息来处理歧义现象，让计算机模拟人对句子的理解来进行分词。
主要方法：专家系统分词、神经网络分词（LSTM,CNN）

词性标注

词性标注(Part of speech tagging)是为分词结果中的每个单词标注一个正确的词性，也即确定每个词是名词、动词、形容词或者其他词性的过程；主要任务是消除词性兼类歧义。

词性标注算法

基于规则的方法：
根据词语的结构建立词性标注规则
词缀(前缀、后缀)：绿油油（形容词）、一片片(数量词)
重叠词规则：看看、瞧瞧、高高兴兴、热热闹闹 …
基于机器学习的自动规则提取方法
初始词性赋值；
对比正确标注的句子,自动学习结构转换规则
利用转换规则调整初始赋值
基于统计模型的方法：最大熵、HMM、CRF
综合方法：
统计概率引导，辅以规则消歧

依存句法分析

依存句法分析（dependency parsing）通过分析语言单位内成分之间的依存关系揭示其句法结构。 直观来讲，主要是识别句子中的主谓宾、定状补这些语法成分，并分析各成分之间的关系。
基于图的依存句法分析方法：
将依存句法分析问题看成从完全有向图中寻找最大生成树的问题
通常采用基于动态规划的解码算法，也有一些学者采用柱搜索(beam search)来提高效率。
基于转移的依存句法分析方法：
将依存树的构成过程建模为一个动作序列，将依存分析问题转化为寻找最优动作序列的问题。
多模型融合的依存句法分析方法：
融合以上两种方法，如stacked learning

语义分析

1. 词义消歧。如何自动获悉某个词存在着多种含义，以及假设已知某个词具有多种含义，如何根据上下文确认其含义。
   基于词典的方法：英文词义标注语料库： Semcor(普林斯顿大学)、Senseval 评测语料库等；中文词义标注语料库：哈尔滨工业大学和北京大学分别基于 HowNet 和北大“现代汉语语义词典”标注了词义消歧语料库。
   基于机器学习的方法：综合待消解词的词汇、句法、语义等特征，结合机器学习算法进行。
2. 词表示。如何表示并学习一个词的语义，以便计算机能够有效地计算两个词的相似度。
   目前流行的词义表示方式是词嵌入（Word Embedding, 又称词向量）。基本想法是：通过训练将某种语言中的每一个词映射成一个固定维数的向量，将所有这些向量放在一起形成一个词向量空间，而每一向量则可视为该空间中的一个点，引入“距离”概念，则可以根据词之间的距离来判断它们之间的（词法、语义上的）相似性。
   句子级语义分析试图根据句子的句法结构和句中词的词义等信息，推导出能够反映这个句子意义的某种形式化表示。

• 语义角色标注 (Semantic Role Labeling，简称 SRL)是一种浅层语义分析方法，任务是找出句子中谓词的相应语义角色成分，包括核心语义角色（如施事者、 受事者等）和附属语义角色（如地点、时间、方式、原因等）。
• 句子嵌入表达(Sentence Embedding) 主要研究如何有效地从词嵌入通过不同方式的组合得到句子的向量表示，常用方法有词袋模型、卷积神经网络、循环神经网络、BERT等。

机器翻译

机器翻译 (machine translation, MT) 是用计算机把一种语言(源语言，source language)翻译成另一种语言(目标语言，target language)的一门学科和技术。

1. 直译式翻译系统(direct translation MT systems) ： 通过快速的分析和双语词典，将原文译出。
   
2. 规则式翻译系统(rule-based MT systems)： 先分析原文内容，产生原文的句法结构，再转换成译文的句法结构，最后再生成译文。
3. 中介语式翻译系统(inter-lingual MT systems) ：先生成一种中介的表达方式，而非特定语言的结构；再由中介的表达式，转换成译文。
   
4. 知识库式翻译系统(knowledge-based MT systems) ：翻译经常需要除了词汇之外的各种知识，使用知识获取工具(knowledge acquisition)，以充实知识库的内容。
5. 统计式翻译系统(Statistics-based MT systems ) ：
   1994年，IBM公司A．Berger等用统计方法和各种不同的对齐技术，给出了统计式机器翻译系统Candide。
   统计机器翻译基本思想是通过对大量的平行语料进行统计分析，构建统计翻译模型，进而使用此模型进行翻译。
   目前，基于统计法机器翻译系统有Google翻译、Bing翻译和百度翻译等。
   统计机器翻译的首要任务是为语言的产生构造某种合理的统计模型，并在此统计模型基础上，定义要估计的模型参数，并设计参数估计算法。
   早期的基于词的统计机器翻译采用的是噪声信道模型，采用最大似然准则进行无监督训练，而近年来常用的基于短语的统计机器翻译则采用区分性训练方法，一般来说需要参考语料进行有监督训练。
6. 范例式翻译系统(example-based MT systems ) ：将过去的翻译结果，当成范例，产生一个范例库。
7. 翻译记忆(translation memory, TM )
   基本原理：用户利用已有的原文和译文，建立起一个或多个翻译记忆库，在翻译过程中，系统将自动搜索翻译记忆库中相同或相似的翻译资源（如句子、段落等），给出参考译文，使用户避免重复劳动，只专注于新内容的翻译。翻译记忆库同时在后台不断学习和自动储存新的译文，变得越来越聪明。
8. 神经机器翻译：
   神经机器翻译是模拟人脑的翻译过程，目前已经远远超过统计机器翻译，成为机器翻译的主流技术。
   ●长短期记忆神经网络（LSTM）是一种对序列数据建模的神经网络，适合处理和预测序列数据。而且，LSTM使用“累加”的形式计算状态，这种累加形式导致导数也是累加形式，避免了梯度消失，因此在神经机器翻译中得到了广泛应用。
   ●目前，神经机器翻译领域主要研究如何提升训练效率、编解码能力以及双语对照的大规模数据集。
   ●网络上很多神经机器翻译的开源实现，如Groundhog (https://github.com/lisa-groundhog/GroundHog）。

语音识别

语音识别流程
● 分帧：把一段语音分成若干小段
●状态：把每一帧识别作为一个状态
●音素：把状态组合成音素，即声母亲和韵母。
●声学模型（acoustic model）：把一系列语音帧转换为若干音素的过程利用了语言的声学特性。
●语言模型（language model） ：从音素到文字的过程要利用语言表达的特点，从同音字中挑选正确的文字，组成意义明确的语言。

1.语音信号采集
● 基于单片机，DSP芯片
●基于PC机
2.语音信号预处理
●滤波
（1）抑制输入信号各频域分量中频率超出采样频率的一半的所有分量，以防止混叠干扰。
（2）抑制50Hz的电源工频干扰。
采样：对信号进行量化，量化不可避免地会产生误差。量化后的信号值与原信号值之间的差值为量化误差，又称为量化噪声。
●预加重：提升高频部分，使信号的频谱变得平坦，保持在低频到高频的整个频带中，能用同样的信噪比求频谱，便于频谱分析或声道参数分析。
●端点检测：包含语音的一段信号中确定出语音的起点以及终点。
注：过零率：信号中波形穿越零电平的次数来描述幅度变化的剧烈程度。
3.语音信号的特征参数提取
声波有两个主要特征：振幅和频率。
线性预测编码（LPC)：
基本思想：由于语音样点之间存在相关性，所以可以用过去p个样点值来预测现在或未来的样点值。
4.向量量化
矢量量化（vector quantization，VQ）技术是七十年代后期发展起来的一种数据压缩和编码技术。
在标量量化中整个动态范围被分成若干个小区间，每个小区间有一个代表值，对于一个输入的标题信号，量化时落入小区间的值就用这个代表值代替。
矢量量化的基本原理：将若干个标量数据组成一个矢量在多维空间给予整体量化，从而可以在信息量损失较小的情况下压缩数据量。
5.识别
识别系统的输入是从语音信号中提出的特征参数。
（1）语音识别模板匹配法
在训练阶段，用户将词汇表中的每一个词依次说一遍，将其特征矢量作为模板存入模板库。在识别阶段，将输入语音的特征矢量序列依次与模板库中的每个模板进行相似度比较，将相似度最高者作为识别结果输出。
（2）语音识别随机模型法
如隐马尔可夫模型(HMM)。用HMM的概率参数对似然函数进行估计与判决，从而得到识别结果。
（3）语音识别概率语法分析法
不同的人说同一些语音时，相应的语谱总有一些共同的特点以区分于其他语音。将区别性特征与来自构词、句法、语义等语用约束相互结合，构成由底向上或自顶向下的交互作用知识系统。

需要回答的重要问题

一、人工智能应用现状
人工智能定义、类型、发展现状与应用。
二、知识表示:知识表示的方法、特点和应用。
有哪些知识表示方法，特点是什么，对于一个问题如何用知识表示方法实现？
三、搜索算法有哪些类型?启发式算法和盲目搜索算法包含哪些算法，他们之间的区别是什么？对于一个给定的问题如何设计搜索算法？
基本遗传算法的五个要素，遗传算法的流程。
四、机器学习监督学习和非监督学习包含哪些算法？这些算法的原理是什么？机器学习包含哪些步骤，每个步骤起到什么作用以及如何实现每个步骤?如何评价机器学习方法？对于给定的任务，如何把任务划分到对应的机器学习任务并给出解决方案？
五、神经网络的结构，典型的神经网络有哪些？他们的结构是什么样的?主要应用领域有哪些？重点看卷积神经网络和生成对抗网络的结构、特点。
六、自然语言处理具体是处理什么问题？包含哪些层次，用到哪些技术，每个具体的技术作用是什么？对于给定的任务如何用自然语言处理的技术来解决?