人工智能算法（Python语言版）课件 第10-18章-异常检测算法- 图分析算法

第10章

异常检测《人工智能算法》提纲引例异常检测概述异常检测算法分类局部异常因子算法（LOF）基于聚类的局部异常因子算法（CBLOF）总结引例异常数据是指不符合预期行为的数据ID012345678910score808587826971069737772可以直观地从这组一维数据中找出id=6的分数为异常数据，因为其值与其他数据相差很大。但是，现实生活中的数据可能很多并且不止一维，此时我们就需要更有效算法来找出异常数据。提纲引例异常检测概述异常检测算法分类局部异常因子算法（LOF）基于聚类的局部异常因子算法（CBLOF）总结异常检测（AnomalyDetection）——检测数据中不符合预期行为的数据，其基本思想通过数据挖掘方法找出显著不同于其他数据的异常点，并发现潜在的、有意义的知识异常检测的应用异常检测概述(1)欺诈识别数据清理网络入侵检测故障检测异常检测概述(2)异常点类型单点异常——某个点与全局大多数点都不一样，该点构成了单点异常上下文异常——一个点只有在特定的上下文下才叫做异常，如果没有这个上下文，该点就是正常的集体异常——由多个对象组合构成，即单独看某个个体可能并不存在异常，但这些个体同时出现，则构成了一种异常冬天这里的气温是35℃，不看冬天这个上下文，35℃是正常的，但是加上冬天这个条件，35℃就是异常的提纲引例异常检测概述异常检测算法分类局部异常因子算法（LOF）基于聚类的局部异常因子算法（CBLOF）总结异常检测算法分类(1)异常检测算法基于统计学的算法基于距离的算法基于聚类的算法基于密度的算法……基于统计（Statistics-based）的方法正常的数据是遵循特定分布形式的，并且占了很大比例，而异常点的位置和正常点相比存在比较大的偏移。该方法需假定大部分数据服从一定的分布，而这样的分布在现实中往往很难获取，从而限制了该类算法的发展和应用。

异常检测算法分类(2)

基于聚类（Cluster-based）的方法将数据样本划分为不同的簇，选择小簇中的样本作为候选异常点，以非候选点构成的簇和候选点之间的距离作为是否存在异常的依据异常检测算法分类(3)

提纲引例异常检测概述异常检测算法分类局部异常因子算法（LOF）基于聚类的局部异常因子算法（CBLOF）总结局部异常因子算法

(1)LOF的基本思想通过比较每个样本和其邻域样本的密度来判断该样本是否为异常。样本的密度越低，越有可能是异常点。LOF算法中样本的密度通过样本的k距离邻域计算得到，而不是通过全局计算得到，这里的“k距离邻域”即为该算法中“局部”的概念。局部异常因子算法

(2)

局部异常因子算法

(3)（2）k距离领域（k-distanceNeighborhood）到样本O的距离小于O的k距离的所有样本构成的集合k=3时，O的k距离邻域为{A,B,C}k=4时，O的k距离邻域为{A,B,C,E,G}

局部异常因子算法

(4)

局部异常因子算法

(5)

局部异常因子算法

(6)计算样本点间距离计算k距离04.245.6654.2401.4115.661.4101511051.411.411055.6654.2401.411.415.661.4101.415110计算样本点间可达距离设置k=2，阈值

=1.5局部异常因子算法

(7)0.2160.8280.8280.707计算局部可达密度3.5490.9260.9261.172计算局部异常因子与阈值（1.5）进行比较异常正常正常正常算法

局部异常因子算法

(8)

局部异常因子算法

(9)

时间复杂度:O(n2)空间复杂度:

O(n2)局部异常因子算法

(10)

提纲引例异常检测概述异常检测算法分类局部异常因子算法（LOF）基于聚类的局部异常因子算法（CBLOF）总结基于聚类的局部异常因子算法(1)基本概念

聚类：将数据分为多个簇，尽可能使簇内相似度大、簇间相似度小

异常检测：检测数据中不符合预期行为的异常数据

联系：常见的聚类算法扩展后都能应用于异常检测基本思想(1)对数据样本进行聚类得到簇集合(2)由每个簇中样本的数量将簇分为大簇和小簇(3)计算异常得分，也就是一个样本到最近的大簇中心的距离(4)按各样本的异常得分判断该样本是否属于异常点基于聚类的局部异常因子算法(2)

基于聚类的局部异常因子算法(3)

基于聚类的局部异常因子算法(4)ID1234567891011121314151617sales613630831284754430146277409308159255141188profit116-166521429163445685-1359-3102-950

簇号ID01,2,4,5,6,7,8,9,10,11,12,14,15,1613,13217绝对多数突降大簇小簇01,2基于聚类的局部异常因子算法(5)ID12345678异常得分0.1020.15818.5910.2060.0770.2120.7680.170ID91011121314151617异常得分0.1470.2670.5220.17415.2570.2760.1230.20610.711异常样本的比例（一般为1%，此例样本较少，可调节为15%）分类ID正常样本1,2,4,5,6,7,8,9,10,11,12,14,15,16异常样本3,13,17基于聚类的局部异常因子算法(6)算法

时间复杂度:O(n)空间复杂度:

O(n)

基于聚类的局部异常因子算法

(7)优点缺点不需要监督，易适应在线或增量模式，适用于时空数据的异常检测。若选择聚类算法的时间和空间复杂度是线性的或接近线性的，基于这类算法的异常检测技术对大规模数据集也是有效的。没有任何一种聚类算法适用于所有数据集，不同数据集需要采用不同的聚类算法。当聚类算法的选取不合适时，样本不能创建任何有意义的簇，那么该方法可能会失败。针对高维空间中的稀疏数据，任意两个样本间的距离可能会非常相似，聚类算法可能不会得到有意义的簇。提纲引例异常检测的概述异常检测的分类局部异常因子算法（LOF）基于聚类的局部异常因子算法（CBLOF）总结总结异常检测的基本思想、分类方法，所解决的主要问题异常检测算法解决问题的一般方法和步骤、及其优缺点异常检测的重要算法实例：-基于密度的LOF算法

-基于聚类的CBLOF算法结语谢谢！第11章

频繁模式挖掘算法《人工智能算法》提纲频繁模式挖掘概述Apriori算法Apriori算法示例总结频繁模式挖掘概述什么是频繁模式（FrequentPattern）频繁地出现在数据集中的模式。例如，频繁地同时出现在新冠肺炎患者临床数据中的症状集合（发热，咳嗽，乏力），交易数据集中的商品集合（篮球、球鞋、运动裤），也称频繁项集（FrequentItemset）。频繁模式挖掘的重要性旨在发现数据之间隐含的关联关系，是关联规则挖掘、相关性分析、因果关系挖掘、局部周期性分析等数据挖掘任务的基础，广泛用于推荐系统、异常检测、医疗诊断等领域。关联规则简介是形如X→Y的逻辑蕴涵式，表示“通过X可推导得到Y”，X和Y为数据集中两个互不相交的事务数据集。经典的挖掘算法有Apriori、FP-Growth和Eclat等。提纲频繁模式挖掘概述Apriori算法Apriori算法示例总结Apriori算法(1)Transaction_IDItems1A,B,C2A,C,D3A,D,E4B,E,F5B,C,D,E,F基本概念

目标是找到所有支持度和置信度不小于指定的规则：最小支持度（MinimumSupport）min_sup，最小置信度（MinimumConfidence）min_conf如果项集的支持度超过最小支持度阈值，称为频繁项集Apriori算法(2)基本步骤Step1：寻找到所有的频繁项集，即大于或等于最小支持度阈值的项集Step2：由频繁项集产生关联规则，且这些规则的置信度与支持度均大于或等于最小置信度阈值和最小支持度阈值基本思想Apriori算法利用如下两个性质：1）若一个集合是频繁项集，则其所有非空子集都是频繁项集。2）若某一集合为非频繁项集，则其所有超集都是非频繁项集。基本步骤（1）连接步：频繁项集间的并运算，将Lk−1中前k−2个项相同的k−1项集合并，产生候选k-项集的集合Ck。（2）剪枝步：删除Ck中非频繁候选项集的过程，用于快速减小Ck所包含项集的数目。Apriori算法(3)Apriori算法思想频繁项集的产生，需对数据集进行多步处理。第一步，统计所有包含一个元素的项集出现的频数，并筛选出不小于最小支持度的项集；从第二步开始循环处理，直到再没有频繁项集生成。循环过程的第k步，根据第k−1步生成的频繁(k−1)-项集产生k维侯选项集，然后搜索数据集D，得到侯选项集的支持度，并与最小支持度进行比较，从而找到频繁k-项集。Apriori算法(4)

Apriori算法(5)

连接步

Apriori算法(4)Has_infrequent_subset(c,Lk−1)//判断c是否为候选集的函数Foreachs

c(k−1)Do//用c(k−1)表示c的(k−1)-子集的集合IfsLk−1ThenReturnTrueElseReturnFalseEndIfEndFor

剪枝步提纲频繁模式挖掘概述Apriori算法Apriori算法示例总结Apriori算法示例(1)TIDT1T2T3T4T5T6T7T8T9项IDABEBDBCABDACBCACABCEABCApriori算法示例(2)

非空子集置信度关联规则{A}2/6=0.33{B}2/7=0.29{E}2/2=1基于挖掘得到的频繁项集L={A,B,E}，生成关联规则：（1）根据频繁项集L={A,B,E}，得到非空子集为{A},{B},{E},{A,B},{A,E},{B,E}；（2）对每一个非空子集，计算频繁项集L在数据集D中出现的次数与非空子集出现次数的比值，若min_conf=0.7，则规则E→A∧B、A∧E→B和B∧E→A为强规则。Apriori算法示例(3){A,B}2/4=0.5{A,E}2/2=1{B,E}2/2=1基于频繁项集产生关联规则：提纲频繁模式挖掘概述Apriori算法Apriori算法示例总结总结Apriori算法的优缺点：

优点：简单、易理解、数据要求低，对稀疏的、短的频繁模式挖掘具有较高的效率，且扩展性好、可并行计算。缺点：在每一步产生侯选项集时循环产生的组合过多，没有排除不应参与组合的元素；每次计算项集的支持度时，都对数据集D中的全部记录进行一遍扫描比较，对于大型的数据集，这种扫描比较将大大增加计算时间开销，且这种代价随着数据集中记录数的增加呈现出几何级数增加。结语谢谢！第12章

链接分析算法《人工智能算法》提纲引例链接分析概述PageRank算法基于MapReduce的PageRank算法总结引例(1)有向图表示网页之间的联系，如何衡量各网页的重要程度？ABCD基于以下两个假设：数量：入链数量越多，页面越重要。质量：质量越高的页面指向某一页面，则该页面越重要。引例(2)

引例(3)

引例(4)

提纲引例链接分析概述PageRank算法基于MapReduce的PageRank算法总结链接分析概述链接分析：运用数学分析和情报学等方法对图结构中的网络链接进行分析，以揭示图中节点的重要性，节点之间的关联信息及规律。分类与应用分类应用领域情报链接分析（ISLA）基于文献计量学的引文分析计算机科学链接分析（CSLA）网络动力学、链接与内容的关系、链接与信息检索、网络挖掘社会科学链接分析（SSLA）网络空间分析与超链接网络分析主要的链接分析模型随机游走（RandomWalk）：以PageRank及其改进算法为代表，对节点之间直接链接与远程链接两种方式进行分析。子集传播（SubsetPropagation）：以Hilltop和HITS算法为代表，将图结构划分为子集并对特殊子集初始化，利用特殊子集与其他节点的链接关系将权值传递到其他节点。根集(rootset)扩展网页集合HITS算法提纲引例链接分析概述PageRank算法基于MapReduce的PageRank算法总结PageRank算法(1)以网页排序为例，PageRank算法可对所有网页进行重要性排序。随机游走模型就是针对浏览网页的用户行为建立的抽象概念模型。PageRank基本思想：在给定有向图上初始化PageRank值及转移矩阵，定义随机游走模型，迭代更新节点状态值直至趋于稳定，每个节点的值为最终的PageRank值。ABCD节点表示状态有向边表示状态之间的转义PageRank算法(2)

PageRank算法(3)增加d的动机？转移矩阵访问各个节点的概率完全随机访问各个节点的概率

PageRank算法(4)PageRank算法(5)幂法求PageRank值的步骤

PageRank算法(6)幂法求解网页的PageRank值示例

PageRank算法(7)

PageRank算法(8)

PageRank算法(9)PageRank优点：PageRank缺点：快速找出图中占主导地位的节点；计算过程可离线，提升检索效率，有利于快速响应。转移矩阵某一列为0时，排序失效；新加入节点的链接较少时，迭代过程中PageRank值会不断减少；对图中节点进行全局PageRank值计算，难以应对推荐系统类场景。提纲引例链接分析概述PageRank算法基于MapReduce的PageRank算法总结基于MapReduce的PageRank算法(1)问题：实际链接分析任务中，图中的节点规模往往比较大，如何高效的计算节点的PageRank值？并行计算？MapReduce？基于MapReduce的PageRank算法(2)基本思想预先统计各网页之间的链接信息，并记录成<网页ID,(网页PageRank值,网页链接列表)>，再通过Map和ReDuce函数进行迭代计算。

Map

ReduceShuffle基于MapReduce的PageRank算法(3)Map阶段的任务与思想

思想：计算每个链出网页被源网页“贡献”的PageRank值并生成<链出网页，PageRank贡献值>，由<网页，链出网页列表>和链出列表确定网页之间的链接情况。任务：根据形如<网页ID，（网页PageRank值，网页链出列表）>的输入信息产生两种键值对（<key,value>）Map阶段算法步骤

基于MapReduce的PageRank算法(4)Reduce阶段的任务与步骤

Reduce任务：计算每个网页的PageRank值思想：由key从Map输出中找到所有对应的键值对并得到<key,链出网页列表>；利用<key,PageRank贡献值>更新当前的PageRank值。基于MapReduce的PageRank算法(5)Reduce阶段算法步骤

基于MapReduce的PageRank算法(6)

基于MapReduce的PageRank算法(7)提纲引例链接分析概述PageRank算法基于MapReduce的PageRank算法总结总结分析对象和潜在链接关系的多样化，人们对链接分析算法的效率、精度和鲁棒性等指标提出更高的要求。针对不同的链接分析任务和性能要求，人们基于不同模型和架构对PageRank进行改进和扩展。例如，基于Spark框架的PageRank算法，从内存管理、减少内存I/O开销的角度进一步提高了计算效率。PageRank算法为基于链接关系的权重计算提供了可供参考的思路，具有通用性和普遍性，在学界和业界都得到广泛的应用。结语谢谢！第13章

概率推理《人工智能算法》提纲引例贝叶斯网概念贝叶斯网参数学习贝叶斯网结构学习基于贝叶斯网的概率推理总结引例哪些事件可能导致患者呼吸困难？长期吸烟？感染COVID-19？

P(呼吸困难=T)=0.01

P(呼吸困难=T|长期吸烟=T)=0.6

P(呼吸困难=T|长期吸烟=T,感染COVID-19=T)=0.9已知患者长期吸烟已知患者长期吸烟，且感染了COVID-19患者无不良生活习惯遗传、长期吸烟、长期接触致癌物、感染COVID-19、其他因素…产生呼吸困难(T)无呼吸困难症状(F)患者知识不完整信息来源不准确测试手段的局限性……现实世界的推理存在不确定性引例概率推理（ProbabilisticInference）基于概率论描述随机事件带来的不确定性常用模型：贝叶斯网(BayesianNetwork)马尔科夫网(MarkovNetwork)条件随机场(ConditionalRandomField)概率图模型（ProbabilisticGraphicalModel）基于专家经验推理的局限性数据和知识来源多不同领域知识学习成本高昂实际问题日益复杂

用户需求提高步骤：将随机事件视为变量构建变量间复杂依赖关系设计概率推理算法应用场景：金融分析、故障检测、医疗诊断···提纲引例贝叶斯网概念贝叶斯网参数学习贝叶斯网结构学习基于贝叶斯网的概率推理总结贝叶斯网（BayesianNetwork,BN）贝叶斯网的基本概念(1)有向无环图（DirectedAcyclicGraph,DAG）条件概率表（ConditionalProbabilityTable,CPT）

BN定义

简单的贝叶斯网实例贝叶斯网的基本概念(2)S：“吸烟”A

：“发烧”B

：“呼吸困难”L

：“肺癌”C

：“感染COVID-19”所有变量为二值变量（取值为T和F）变量含义：贝叶斯网的构建方法贝叶斯网的基本概念(3)手工构建贝叶斯网的应用故障诊断因果推断机器学习推荐系统通过数据分析构建BN模型可解释性高需要领域专家知识工作量大通过算法学习与数据尽可能吻合的模型模型构建工作量小模型构建速度相对快得到的结构可能需要专家进一步优化提纲引例贝叶斯网概念贝叶斯网参数学习贝叶斯网结构学习基于贝叶斯网的概率推理总结BN参数学习参数学习(1)基于样本数据计算变量节点的条件概率参数

BN的参数学习参数学习(2)

最大似然估计（MaximumLikelihoodEstimation）参数学习(3)

步骤：最大似然估计（MaximumLikelihoodEstimation）参数学习(4)

其中，P(da|𝜃)为给定𝜃时样本da出现的概率，记为：

最大似然估计（MaximumLikelihoodEstimation）参数学习(5)

基于最大似然估计的参数学习示例参数学习(6)

FFFTTTTTFFFF

所有变量为二值变量（取值为T和F）

基于最大似然估计的参数学习实例参数学习(7)

FFFTTTTTFFFF

基于最大似然估计的参数学习实例参数学习(8)FFFTTTTTFFFF

基于最大似然估计的参数学习实例参数学习(9)FFFTTTTTFFFF2/42/4

计算所有节点的CPT：

2/2002/2

1/21/202/2

提纲引例贝叶斯网概念贝叶斯网参数学习贝叶斯网结构学习基于贝叶斯网的概率推理总结BN的结构学习结构学习(1)在给定数据集的前提下寻找一个与训练样本集匹配最好的网络结构结构学习主要包括以下两类方法：卡方测试（Chi-SquareTest）条件互信息测试（ConditionalMutualInformationTest）条件独立测试（ConditionalIndependenceTest）将BN视为描述变量之间条件独立性关系的网络模型贝叶斯信息准则（BayesianInformationCriterion,BIC）＋爬山算法评分搜索（ScoringandSearch）将BN结构学习视为组合优化问题基于BIC评分和爬山法的BN结构学习结构学习(2)BIC评分：在大样本前提下对边缘似然函数的一种近似

基于BIC评分和爬山法的BN结构学习结构学习(3)BIC评分的分解：用于减小搜索过程中的计算开销

基于BIC评分和爬山法的BN结构学习结构学习(4)基于爬山法找到BIC评分最高的模型步骤：（1）初始结构为无边模型，或基于领域知识设置初始结构（2）通过加边、减边、反转边三种算子对当前结构局部进行修改，

得到一系列候选模型（3）计算不同候选模型参数的最大似然估计及相应的BIC评分（4）迭代选出当前BIC评分最高的候选结构，直至收敛基于BIC评分和爬山法的BN结构学习结构学习(5)初始结构

三种算子：

基于爬山法的BN结构学习算法结构学习(6)

提纲引例贝叶斯网概念贝叶斯网参数学习贝叶斯网结构学习基于贝叶斯网的概率推理总结基于BN的概率推理算法基于贝叶斯网的概率推理(1)精确推理算法已知Ę取值为e的条件下，利用联合概率和边缘概率来计算查询变量Q取值为ɋ的后验概率，得到精确的P(Q=ɋ|Ę=e)近似推理算法通过降低对精度的要求，在限定时间内得到一个近似解-重要性采样（ImportanceSampling）-马尔科夫链蒙特卡洛（MarkovChainMonteCarlo,MCMC）Ę：证据变量集合；Q：查询变量集合基于BN的精确推理算法基于贝叶斯网的概率推理(2)

一般联合概率分布推理步骤：

整个联合概率分布包含25

1个独立参数，方法具有极高的复杂度基于贝叶斯网的概率推理(3)利用变量间的条件独立性，分解联合概率分布

计算步骤乘法（次）加法（次）4/8/16/32//16/8/4/2总计6030需要60次乘法和30次加法基于贝叶斯网的概率推理(4)利用变量间的条件独立性，分解联合概率分布

计算步骤数字乘法（次）数字加法（次）8//44//24//24//2总计2010仅需要20次乘法和10次加法VE算法基于贝叶斯网的概率推理(5)变量消元法（VariableElimination,VE）：通过分解联合分布简化推理步骤：

VE算法基于贝叶斯网的概率推理(6)（2）消元（Elimination）：

VE算法基于贝叶斯网的概率推理(7)Ɓ：BN；Ę：证据变量；e：证据变量取值，Q：查询变量；ρ：待消元变量顺序，包括所有不在Ę∪Q中的变量

VE算法示例基于贝叶斯网的概率推理(8)基于VE算法计算P(S|L=F)

VE算法示例基于贝叶斯网的概率推理(9)

近似推理算法基于贝叶斯网的概率推理(10)Gibbs采样：随机产生一个与证据Ę=e一致的样本Ɗ1作为初始样本，每一步都从当前样本出发产生下一个样本。步骤：

基于贝叶斯网的概率推理(11)

基于贝叶斯网的概率推理(12)基于Gibbs采样算法近似计算P(S|L=F)基于Gibbs采样的概率推理示例随机生成一个与证据L=F一致的样本，假设为Ɗ1={S=T,A=F,B=T,L=F,C=F}由Ɗ1生成样本Ɗ2算法从Ɗ2=Ɗ1={S=T,A=F,B=T,L=F}出发，对非证据变量逐个采样采样顺序为<S,A,B,L,C>基于贝叶斯网的概率推理(13)基于Gibbs采样的概率推理示例采样过程如下：①

对S进行采样，mb(S)包含节点A和B，计算S的概率分布P(S|A=F,B=T)，假设采样结果为S=F，则有Ɗ2={S=F,A=F,B=T,L=F,C=F}②对A进行采样，此时S=F，mb(A)包含节点S和B，计算F的概率分布P(A|S=F,B=T)。假设采样结果为A=T，则有Ɗ2={S=F,A=T,B=T,L=F,C=F}基于贝叶斯网的概率推理(14)基于Gibbs采样的概率推理示例③对B进行采样，此时A=T，mb(B)包含节点S、A、L和C，因此，计算B的概率分布P(B|S=F,A=T,L=F,C=F)，假设采样结果为B=T，则有Ɗ2={S=F,A=T,B=T,L=F,C=F}④对L进行采样，此时B=T，mb(L)包含节点B和C，计算L的概率分布P(L|B=T,C=F)，假设采样结果为L=T，则有Ɗ2={S=F,A=T,B=T,L=T,C=F}基于贝叶斯网的概率推理(15)基于Gibbs采样的概率推理示例⑤对C进行采样，此时L=T，mb(C)包含节点B和L，计算C的概率分布P(C|B=T,L=T)，假设采样结果为C=F，则有Ɗ2={S=F,A=T,B=y,L=T,C=F}，即为Ɗ2的最终值。

提纲引例贝叶斯网概念贝叶斯网参数学习贝叶斯网结构学习贝叶斯网概率推理总结总结不确定性知识表示和处理能力，是智能系统走向实用的重要要求概率图模型：图模型的概率性质，概率论+图论

概率推理基本思想和分类贝叶斯网的概念、参数学习和结构学习基于贝叶斯网的概率推理（精确推理，近似推理）结语谢谢！第14章

人工神经网络和深度学习

概述《人工智能算法》提纲人工神经网络神经元模型感知机多层神经网络深度学习总结人工神经网络(1)人工神经网络（ArtificialNeuralNetwork,ANN）抽象人脑神经元→构建人工神经元。连接人工神经元→模拟人脑神经网络。数学模型应用广泛自然语言处理目标检测图分析人工神经网络(2)神经元模型接收d个输入信号x=[x1;x2;…;xd]。对信号加权求和，再通过激活函数输出。激活函数𝜎为阶跃函数MP神经元模型1：神经元兴奋0：神经元抑制人工神经网络(3)MP神经元模型的数学表示权重参数：w=[w1;w2;…;wd]，偏置：b

MP神经元模型的数学理解对复杂函数y=f(x1,…,xd)的一阶泰勒近似

偏置b权重参数wi人工神经网络(4)感知机（Perceptron）输入：实例的特征向量x=[x1;…;xd]输出：+1或−1

w和b为模型参数sign为符号函数被广泛使用的二分类模型输入：数据集D={(x1,y1),…,(xn,yn)}D超平面wTx+b学习算法yi

=+1yi

=−1wTxi+b>0wTxi+b≤0找到参数w和b人工神经网络(5)感知机学习算法求解参数w和b的损失函数：梯度下降求解：

M为误分类的样本集合随机初始化w和bRepeat

在训练集中随机选取一个样本(xi,yi)

If

yi(wTxi+b)≤0Then

w←w+ηyixi,b←b+ηyi

EndIfUntil没有误分类的样本Return

w和b

复杂度为O(td)t：迭代次数人工神经网络(6)感知机的主要贡献提供了一个通用的机器学习框架给定数据集D，寻找函数y=f(x,θ)，预测新样本x’对应的y’=f(x’,θ)感知机：θ

=(w,b)，f(x,θ)=sign(wTx+b)占用计算和存储资源较少仅存储参数w和b每次更新只选择一小部分训练样本进行计算人工神经网络(7)多层神经网络按一定结构连接多个神经元，可处理非线性可分问题多层前馈神经网络（Multi-layerFeedforwardNeuralNetwork）1个输入层、1个隐藏层、1个输出层每层包含多个神经元每层神经元与下一层神经元全连接

输出：y=v3训练网络：确定参数w=[w11;w12;w21;w22;w2]和b=[b1;b2;b3]人工神经网络(8)多层神经网络的特点激活函数σ必须是非线性函数能以任意精度逼近任意复杂的连续函数训练神经网络的步骤（1）设计神经网络的结构（多少层？每层多少神经元？如何连接？）

简单问题/训练数据少→简单结构；复杂问题/训练数据多→复杂结构（2）求解网络中的待求参数

调整参数w和b，使网络输出ŷ与样本标签y尽可能接近（n为样本数量）

表示能力强随机初始化w和b迭代更新：学习率：0<η<1人工神经网络(9)训练神经网络的步骤（2）求解网络中的待求参数

梯度下降求解：

反向传播：根据网络结构简化偏导数计算随机初始化w和bRepeat

反向传播计算各参数的偏导数Until

且Return

w

和b

人工神经网络(10)基于反向传播的神经网络学习算法输入：训练数据集D，学习率η输出：w和b

时间复杂度：O(tm)t：迭代次数m：参数数量

人工神经网络(11)神经网络学习算法的改进（1）激活函数

使用Sigmoid、ReLU等函数（2）损失函数

交叉熵损失（Cross-entropy）：（3）随机梯度下降

输入一批样本（Batch），利用这批样本的梯度平均值更新参数

将训练数据按BatchSize划分为多个Batch

模型训练需要多个Epoch，每个Epoch都随机划分训练样本

更新参数与训练集大小无关提纲人工神经网络神经元模型感知机多层神经网络深度学习总结深度学习(1)多层神经网络存在许多不足梯度下降法只能获取局部最优值，而非全局最优模型可解释性差需调整的参数太多，训练模型的工作量太大需大量的训练数据……深度学习发展背景计算能力得到了显著提升（GPU等硬件加速设备普及）海量数据被采集和存储充足的训练数据和计算资源深度学习(2)深度学习的产生及发展2006年，Hinton通过“预训练+微调”训练出超过7层的神经网络，并将这类学习方法称为深度学习（DeepLearning）2009年，微软将深度神经网络引入语音识别系统，大幅提升了连续词汇的语音识别率2013年，Hinton的学生使用深度神经网络AlexNet在图像识别比赛ImageNet上夺冠2016年，Google利用基于深度学习的AlphaGo打败了围棋世界冠军李世石……深度学习(3)深度学习的关键构建“深度”神经网络模型（层数多、每层的神经元也多）利用学习算法从数据中自动产生较好的特征常用的深度学习算法自编码器（Autoencoder）：高维数据降维卷积神经网络（ConvolutionalNeuralNetwork）：图像特征提取循环神经网络（RecurrentNeuralNetwork）：文本特征提取图神经网络（GraphNeutralNetwork）：图数据分析……提纲人工神经网络神经元模型感知机多层神经网络深度学习总结总结人工神经网络MP神经元模型：模拟生物神经元的结构和功能感知机：二分类模型，为机器学习提供了一个通用框架多层神经网络：表示能力强，基于反向传播进行训练深度学习深度神经网络模型能提取输入数据更好的特征结语谢谢！第15章

降维算法《人工智能算法》提纲引例降维算法概述自编码器自编码器的改进变分自编码器生成对抗网络总结引例(1)MNIST数据集：60000个训练样本和10000个测试样本

28

28像素手写数字图片的MNIST数据集手写数字“1”的图片及相应的像素矩阵完成数据分类

数据维度高，计算复杂度高

可视化程度不高手写数字“1”的图片识别模型训练过程

引例(2)对MNIST数据集降维

手写数字“1”的图片识别模型训练过程（假设降维后维度为2）完成数据分类

压缩数据

降低计算复杂度

提高可视化程度降低数据维度，保证其有效信息不丢失提纲引例降维算法概述自编码器自编码器的改进变分自编码器生成对抗网络总结什么是降维降维算法概述降低数据维度，保证其有效信息不丢失

为什么要降维缓解高维数据维数灾难问题提高数据可视化程度数据压缩减少存储空间主成分分析，奇异值分解，线性判别分析不能较好地保持数据集的非线性特性

基于深度学习的降维方法自编码器，变分自编码器（生成模型），对抗神经网络（生成模型）传统的降维方法提纲引例降维算法概述自编码器自编码器的改进变分自编码器生成对抗网络总结自编码器(1)基本思想

（1）编码阶段编码器将原始输入映射为低维数据，实现对输入数据的降维

自编码器(2)

（2）解码阶段解码器则将低维数据映射成高维数据，实现对输入数据的重构。

自编码器(3)（3）损失函数

自编码器(4)

时间复杂度分析：

提纲引例降维算法概述自编码器自编码器的改进变分自编码器生成对抗网络总结降噪自编码器(1)

自编码器降噪自编码器降噪自编码器(2)

问题：为了让模型不受噪声的影响

改进:

优点：提高模型鲁棒性缺点：加入噪声，增加模型计算开销

稀疏自编码器(1)

自编码器稀疏自编码器稀疏自编码器将隐藏层数据稀疏化表示，得到更健壮的隐层表示稀疏自编码器(2)

问题：从无类别标签的数据学习到数据的稀疏表示

改进:

在自编码器基础上增加稀疏性限制损失函数增加稀疏惩罚项在隐藏层加入稀疏性限制，减少隐藏层“活跃”的神经元个数，获得隐藏层的稀疏表示稀疏自编码器(3)

优点：学习隐藏层的稀疏表示，对数据过拟合具有泛化能力，降低数据维度，提升性能缺点：无法指定抑制哪些隐藏层神经元，学习到的隐藏层的稀疏表示的物理意义不明确

损失函数

收缩自编码器(1)自编码器收缩自编码器

收缩自编码器(2)

问题：数据传播过程中受噪声干扰

改进：

抑制训练样本在所有方向上的扰动在自编码器的损失函数上增加正则化项

噪声会影响图像的视觉效果、掩盖图像细节优点：学习到的隐藏层表示对输入数据的微小变化不敏感，会提高模型对输入噪声数据的鲁棒性缺点：含有多层隐藏层时，计算时间复杂度较高收缩自编码器通过对损失函数添加正则化项，去噪自编码器通过对输入样本添加噪声与去噪自编码器的区别：

提纲引例降维算法概述自编码器自编码器的改进变分自编码器生成对抗网络总结变分自编码器(1)概述

自编码器编码解码结构简单自编码器中学习到的隐变量（例如h1、h2）为一个特定的向量，不能学习到服从隐变量的数据分布自编码器中不能生成和原始输入相似的数据变分自编码器(2)变分自编码器是一个生成模型变分自编码器能学习隐变量所服从的概率分布，并通过概率分布采样生成和原始数据相似的数据，即支持新样本的生成变分自编码器(3)模型训练

（1）编码阶段

（2）采样阶段从高斯分布中生成隐变量的随机采样样本z

（3）解码阶段

变分自编码器(4)优化目标假设z服从多元高斯分布Q(z|x)：编码过程学习到的概率分P(x|z)

：解码过程学习到的概率分布变分自编码器(5)优化目标

变分自编码器(6)

时间复杂度分析

提纲引例降维算法概述自编码器自编码器的改进变分自编码器生成对抗网络总结越接近越好生成对抗网络(1)引例解码器≈生成器随机生成一个向量作为解码器输入随机向量自编码器不能生成数据，且解码器的输出与原来的输入相比是有损的生成对抗网络(2)传统的生成模型-根据训练集估计样本分布P(x)，之后根据P(x)采样，生成和训练集“类似”的新样本

-对于低维数据，可以使用简单的，只有少量参数的概率模型（如高斯分布）拟合P(x)，但对于高维数据（例如图像）处理比较困难需要大量先验知识对潜在分布建模

需要大量先验知识对潜在分布建模

计算复杂

生成对抗网络(3)基于深度学习的生成模型变分自编码器-

将输入编码为低维空间中的概率分布（如高斯分布）-低维空间中的两个相邻取值解码后呈现相似的内容生成对抗网络（GenerativeAdversarialNetwork,GAN）-GAN没有变分下界（即变化的下限），是渐进一致的，理论上能完美恢复真实数据的分布-相比变分自编码器，GAN训练时不需要对隐变量分布做推断，即无需确定样本的概率模型，不用显式地定义概率密度函数生成对抗网络(4)

174越接近越好基本思想生成对抗网络(5)

采样

噪声向量真实数据

基本思想

采样生成数据

生成分布生成对抗网络(6)弱强弱强伪装能力判别能力生成器：判别器：基本思想每一个GAN框架都包含一对生成器和判别器

源于博弈论中的二人零和博弈（Zero-SumGame）思想生成对抗网络(7)通过一个参数化的概率生成模型（通常为神经网络）进行概率分布的逆变换采样，得到生成概率分布，并生成样本通过判别器（也为神经网络）判断样本来自真实数据还是生成数据高斯分布基本思想生成对抗网络(8)

z采样

高斯分布

生成对抗网络(9)

采样0.25生成数据

采样1

真实数据生成对抗网络(10)

生成器的优化目标将生成数据分布与真实数据分布相近让判别器难以区分生成器的目标函数

𝑉(𝒟,𝒢)的第一项与𝒢无关生成对抗网络(11)训练

生成数据真实数据判别器的优化目标

尽可能区分生成数据和真实数据判别器的目标函数生成对抗网络(12)训练

真实数据生成数据二分类器

生成对抗网络(13)训练过程

𝒟输出各样本为真实数据的概率采样

更新1噪声向量真实数据固定1110000

生成数据

生成对抗网络(14)训练过程

噪声向量0.13更新固定

z

生成对抗网络(15)GAN训练效果展示手写数字生成迭代次数150100150200250生成对抗网络(16)

生成对抗网络(17)

提纲引例降维算法概述自编码器自编码器的改进变分自编码器生成对抗网络总结总结降维算法的基本思想与常见方法典型的降维算法：-自编码器的主要思想、模型结构及训练算法-改进的自编码器

-变分自编码器的主要思想、模型结构及训练算法-生成对抗网络的主要思想、模型结构及训练算法结语谢谢！第16章

目标检测算法《人工智能算法》提纲引例目标检测算法概述卷积神经网络概述YOLO算法总结引例为保证施工人员安全，需确保其正确佩戴各类安全护具如何自动、快速、准确识别是否正确佩戴安全护具（如安全帽）-节省人力资源-每秒检测上百张图像-识别快速准确-可7×24小时实时监控-需大量人力资源-检测效率低-准确率受主观因素影响-无法保证监督的有效性提纲引例目标检测算法概述卷积神经网络概述YOLO算法总结目标检测（ObjectDetection）

-利用矩形边界框来确定图像中目标所在的位置及大小，识别目标所属

的种类，并给出相应的置信度应用场景

-

交通领域：交通违法事件检测-医学领域：病变细胞检测-工程领域：安全帽佩戴检测-工业领域：绝缘子检测-农业领域：农作物病虫害检测目标检测算法概述(1)目标检测算法分类目标检测算法概述(2)目标检测算法传统的目标检测算法HOG，DPM一阶段目标检测算法SSD，YOLO两阶段目标检测算法R-CNN,

FastR-CNN,

FasterR-CNN,CascadeR-CNN,MaskR-CNN基于深度学习的目标检测算法目标检测算法概述(3)传统目标检测算法

-采用滑动窗口的方式遍历整幅图像，选择候选区域-逐个提取候选区域的特征-利用支持向量机(SVM)、随机森林等分类器判定目标类别优点-训练时间短、硬件要求较低缺点-针对特定检测任务，需人工选择和设计不同特征，可移植性差-特征提取和分类任务分离，无法完成端到端的训练SVMSVMSVMSVM…目标检测算法概述(4)两阶段目标检测算法-第一阶段：对输入的图像提取候选区域特征信息-第二阶段：利用卷积神经网络对候选区域进行分类和位置精修-优点：基于候选区域做二次修正，相较于一阶段目标检测算法精度更高…输入图像提取特征生成候选区域检测卷积神经网络输出图像目标检测算法概述(5)一阶段目标检测算法-不需要产生候选区域阶段-可直接计算目标物体的类别和检测框坐标优点一阶段目标检测算法不需要产生候选区域阶段，直接对图像进行计算得到检测结果，相较于两阶段目标检测算法，检测速度更快…输入图像提取特征检测卷积神经网络输出图像提纲引例目标检测算法概述卷积神经网络概述YOLO算法总结卷积神经网络概述(1)卷积神经网络（ConvolutionalNeuralNetwork,CNN）卷积神经网络的层级结构主要包含输入层、卷积层、池化层、全连接层等，通过层级的组合可构建不同的卷积神经网络优点-与全连接神经网络相比，层与层之间稀疏的局部连接减少了参数数量-共享的卷积核参数有助于捕捉图像的局部特征卷积层池化层全连接层···多个卷积层、池化层交叉堆叠预测结果卷积层池化层输入层卷积神经网络概述(2)卷积层-对输入的图像进行特征提取，生成特征图-每个卷积层包含一个或多个卷积核，以滑动窗口的形式在输入图像或特征图上进行卷积操作卷积核大小为3×3，步长为2，填充值为0卷积神经网络概述(3)卷积计算卷积核上的参数和窗口对应区域内的像素值进行乘法求和运算并加上偏置项，得到输出特征图对应位置的特征值03228121330423236525332142193卷积+偏置项卷积核卷积结果0×5+3×3+2×3+1×2+2×1+1×4+3×2+3×1+0×9+3=353532卷积神经网络概述(4)

输出

输入卷积神经网络概述(5)池化层

-对输入特征图进行下采样

，将子区域内的特征值压缩成一个能表示

该区域的特征值，整合邻域特征，减少参数和计算量-常见的池化操作包括最大池化和平均池化21415003185603055486最大池化平均池化原特征图池化结果2234卷积神经网络概述(6)

F为2×2S为2112×112×6456×56×641121125656卷积神经网络概述(7)全连接层将高维特征图映射为低维数据输入图像CNN

7×7×256

1×1×12544FC

10241024个7×7卷积核

1×1×1024···传统全连接操作卷积替代全连接卷积神经网络概述(8)模型训练步骤开始训练将训练集输入网络模型,

输出预测值准备训练数据集,构建网络模型根据预测值和真实标签,计算损失函数值误差是否在范围内根据损失函数值,计算误差梯度采用梯度下降法,更新网络模型参数训练结束,保存网络模型参数前向传播反向传播是否提纲引例目标检测算法概述卷积神经网络YOLO算法总结由JosephRedmon和AliFarhadi等于2015年提出与R-CNN等二阶段算法不同仅基于单个CNN，并将特征提取和检测框定位两个步骤相结合可直接从完整的图像中预测检测框、得到分类置信度YOLO算法概述YOLO算法训练(1)图像预处理-标注检测框训练数据集包括原始图像和标注信息两个部分标注信息包含任意多个检测框的位置信息、置信度及类别信息训练数据集

1620376(0,0)YOLO算法训练(2)图像缩放基于YOLO的网络结构，需将输入图像的长宽像素缩放为固定值448×448先将图片中最长的边缩放到448像素再对短边的空白位置补上灰色1620376448256448448缩放填充像素YOLO算法训练步骤(3)-设置网格及网格中检测框个数把经缩放的图像划分为S×S个网格（Grid）每个网格中设置B个检测框例如：将S和B分别设置为7和2，即将图像划分为7×7个网格，每个网格有2个检测框S为7，将图像划分为7×7的网格448B为2，有2个检测框负责检测目标物体448YOLO算法训练(4)网络模型构建s表示步长,p表示填充值YOLO算法训练(5)

输入层448*448*3S卷积层最大池化层全连接层…YOLO网络模型…输出特征图S×S×(B×5+C)S…B×5+CYOLO算法训练(6)非极大值抑制根据预测检测框的坐标值、置信度及类别概率，利用非极大值抑制（Non-MaximumSuppression,NMS）方法进行筛选，得到包含目标物体的检测框IoU(IntersectionoverUnion)：两个检测框的交集面积与并集面积的比值称为交互比，用于度量两个检测框的交叠程度IoU=交集面积并集面积YOLO算法训练(7)非极大值抑制过程从检测框集合中取出最大置信度对应的检测框A并作为结果输出逐一计算其余检测框与检测框A的IoU，将IoU大于给定阈值（阈值一般设为0.5）的检测框从检测框集合中移除重复上述2个步骤直至检测框集合为空catB：0.6C：0.65A：0.75A取出置信度最大的检测框A作为结果输出分别计算A与B、C的IoU把IoU大于阈值的检测框从检测集合中移除重复上诉步骤直至检测框集合为空YOLO算法损失函数(1)计算损失函数目标检测算法中的损失误差，通常包括检测框定位损失、检测框目标损失和分类损失检测框定位损失反映了检测框位置的误差

YOLO算法的损失函数：中心坐标的定位损失项：

该损失项的系数，越大表示该误差项对损失函数的影响越大，YOLO算法设

第i个网格存在目标物体且第j个检测框负责预测该目标物体

高与宽的定位损失项：

该损失项的系数，越大表示该误差项对损失函数的影响越大，YOLO算法设

第i个单元格存在目标且第j个检测框负责预测该目标物体YOLO算法损失函数(2)损失函数—计算检测框定位损失检测框定位损失反映了检测框位置的误差YOLO算法损失函数(3)损失函数—计算检测框目标损失检测框目标损失反映了检测框中是否包含目标的置信度损失

该损失项的系数，YOLO算法设

第i个单元格不存在目标物体且第j个检测框负责预测不存在的目标

YOLO算法损失函数(4)损失函数—计算分类损失分类损失反映了检测框中的目标物体分类是否准确

表示第i个网格中是否存在物体表示第i个网格所包含目标物体是否属于类别c

YOLO预测的第i个网格所包含目标物体属于类别c的概率YOLO算法示例(1)示例以基于YOLO算法预测图像中的鸟类为例，将输入图像缩放448×448×3，设S=7，即划分为(7×7)个网格448448S为7，将图像划分为7×7的网格YOLO算法示例(2)将处理后的图像输入经过训练的YOLO网络模型中进行前向传播每个网格采用2个检测框检测目标物体（B=2）由于目标物体仅有鸟类，因此C=1，最终输出特征图的维度为7×7×(2×5+1)输入448×448×3图像输入YOLO网络模型进行预测输出7×7×(2×5+1)的特征图

网格1-1对应的检测框网格4-5对应的检测框YOLO算法示例(3)输出特征图共预测出7×7×2(98)个检测框及相应置信度将98个检测框通过NMS方法进行筛选最终得到网格4-5所对应的检测框为最终结果输入448×448×3图像输入YOLO网络模型进行预测NMS方法筛选出最匹配的检测框网格1-1对应的检测框网格4-5对应的检测框提纲引例目标检测算法概述卷积神经网络YOLO算法总结总结目标检测的基本思想、应用场景和常见方法CNN的基本操作、模型结构与训练步骤目标检测的重要算法实例：一阶段目标检测方法YOLO的基本思想、模型结构与训练步骤基于YOLO算法预测图像中的鸟类结语谢谢！第17章

问答系统算法《人工智能算法》提纲引例问答系统的基本思想循环神经网络长短期记忆网络基于LSTM的问答系统构建总结引例(1)典型的问答系统场景

客户客服我当前使用的是多少的套餐？您当前使用的是七十八套餐，包含20GB流量和300分钟通话时间。q1客户客服我每个月使用多少流量？平均每个月使用25GB流量。q2客户客服目前最适合我的套餐是什么？九十八套餐，它包含30GB流量和500分钟通话时间。q3引例(2)q1和q2可直接查询知识库获得答案q3需利用问答系统求解（1）提取q1和q2的上下文语义信息。（2）识别实体“七十八套餐”。（3）链接知识库，确定与该实体对应的子集，生成候选答案集矩阵。（4）计算候选答案中与问题相似度最高的实体。提纲引例问答系统的基本思想循环神经网络长短期记忆网络基于LSTM的问答系统构建总结问答系统（QuestionAnsweringSystem）是信息检索系统的一种高级形式，它通过理解用户意图和问题语义而获取相关的知识，通过推理计算得到答案并返回给用户。问答系统主要由问题分析、信息检索和答案抽取三部分组成。

问答系统的基本思想问题分析传统方法：词性分析、句法分析、语义分析等。新方法：深度神经网络模型，如RNN，LSTM等。信息检索：表征答案候选集答案抽取：计算问题与答案的最佳得分问答系统提纲引例问答系统的基本思想循环神经网络长短期记忆网络基于LSTM的问答系统构建总结循环神经网络(1)循环神经网络（RecurrentNeuralNetwork,

RNN）RNN可对时序信息进行建模，包括输入层、输出层和隐藏层。循环神经网络(2)

循环神经网络(3)

循环神经网络(4)

循环神经网络

(5)

循环神经网络(6)

时间复杂度：O(nRNNTd2h)提纲引例问答系统的基本思想循环神经网络长短期记忆网络基于LSTM的问答系统构建总结长短期记忆网络(1)长短期记忆网络（LongShort-TermMemory,LSTM）当需处理长文档的提取问题与答案的表征时，传统的RNN具有“梯度爆炸”或“梯度消失”的局限性。LSTM运用门控机制，可很好地处理长序列之间的依赖关系。传统的RNN存在什么问题长短期记忆网络(2)模型结构LSTM引入遗忘门（ForgetGate）、输入门（InputGate）、记忆细胞和输出门（OutputGate），记录额外信息，避免RNN梯度消失和梯度爆炸问题。长短期记忆网络(3)

长短期记忆网络(4)

长短期记忆网络(5)

长短期记忆网络(6)

长短期记忆网络(7)

长短期记忆网络(8)模型训练（6）使用梯度下降法，给定学习率η(0<η<1)，以目标的负梯度方向调整参数，更新权重矩阵和偏置：

长短期记忆网络(9)

时间复杂度：O(nLSTMTd2h5)长短期记忆网络(10)例：问答对q=“世界最高峰”、a=“珠穆朗玛峰”，LSTM提取文本序列特征的过程如下：

提纲引例问答系统的基本思想循环神经网络长短期记忆网络基于LSTM的问答系统构建总结基于LSTM的问答系统构建(1)基于LSTM构建问答系统的总体思路（1）分析问题：链接知识库生成候选答案集。（2）利用LSTM表征问题和答案。（3）训练模型，使得问题与正确答案的表征向量相似度得分最高。如何利用LSTM构建问答系统基于LSTM的问答系统构建(2)

基于LSTM的问答系统构建(3)

基于LSTM的问答系统构建(4)

基于LSTM的问答系统构建(5)

基于LSTM的问答系统构建(5)基于LSTM的问答系统构建示例设长序列复杂问题q为“在遥远的东方有个国家叫做中国，美丽富饶、山川壮丽，其最高的山峰叫什么?”。执行过程：

（1）使用LSTM对问题编码，得到问题的编码矩阵。

（3）从主题实体“中国”开始，在G中选取邻域2跳以内的所有实体进行拓扑排序，得到如图所示的推理子图（不包含图中实体旁的数字）。基于LSTM的问答系统构建(6)基于LSTM的问答系统构建(7)（4）由实体“中国”对应的推理子图中任一实体的向量表示，计算推理子图中的实体为最终答案的概率。

提纲引例问答系统的基本思想循环神经网络长短期记忆网络基于LSTM的问答系统构建总结总结问答系统任务的主要思想问答系统任务的特殊性-与检索系统性质的区别

-主要的输入数据源面向问答系统的深度学习算法的特点-深度学习在问答系统中起到的关键性作用基于LST