数学建模算法设计简介.ppt

1、算法设计简介,问题求解概述,问题求解的一般步骤：,需求分析,建模,算法设计,程序实现,测试,应用,分析输入输出数据，设计合理的数据结构,设计适当的算法，确立输入输出之间的函数关系。比如，计算参数模型的函数参数，或者函数逼近（神经网络等方法）,建模方法,差分方程、差分方程组：抵押贷款买房问题等 模型拟合：最小二乘法、三阶样条模型等 概率模型：线性回归，随机行为模拟等 线性规划：单纯形法等 图论建模：最短路径问题、最大流问题等 决策论：决策树、序列决策 博弈论：囚徒困境问题 微分方程、微分方程组建模：人口增长模型、传染病模型 ,模型的设计与实现数据结构,数据模型： 数据对象，数据对象之间的关系 数

2、据对象之间的关系： 逻辑结构，物理结构 逻辑结构： 线性结构，树形结构，图形结构，集合结构 物理结构： 顺序存储，链式存储，索引存储，散列存储,算法设计,算法：,输入数据,算法模块,输出结果,对于用户来讲，算法模块就是黑匣子,算法设计方法,算法,确定的,非确定的,传统算法：,近似算法：,随机算法：,智能算法：,以100%成功概率求解问题的最优解,对解的质量让步,对求解成功概率和解的质量让步,遗传算法，模拟退火算法，蚁群算法，神经网络算法等等,算法设计思想,枚举法：也称穷举法。 归纳法：也就是通常的找规律。 递推法：类似归纳，竞赛中的数学题常常需要递推和归纳。 递归法：递归分为直接递归和间接递归

3、，很多问题都需要借助递归思想和方法求解，包括分治、DP的题目。 回溯法：也即试探法。 迭代法：迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。迭代思想是很多问题求解或代码实现的基本方法。,从问题求解基本思路看，算法设计思想有如下几种：,算法设计方法（1）贪心法,（1）贪心法(greedy method),算法思想： 在贪婪算法中采用逐步构造最优解的方法。 在每个阶段，都做出一个看上去最优的决策(在一定的准则下)。决策一旦做出，就不可再更改。 做出贪婪决策的依据称为贪婪准则。,贪心法采用的是局部最优策略，而局部最优有时并不保证全局最优。 当然，有许多应用问题只要近似最优即可，对这些问题

4、的求解贪心法还是非常实用的。,例如，找零钱问题，用贪心法可以求得最优解。,算法设计方法（2）分治法,（2）分治法（Divide and Conquer Method）,算法思想： 把它分成两个或多个更小、更简单的问题； 分别解决每个小问题； 把各个小问题的解答组合起来，即可得出原问题的解。,典型案例： 汉诺塔问题,算法设计方法（3）动态规划,算法思想： 将一个问题的解决方案视为一系列决策的结果，并考察每个最优决策序列中是否包含一个最优子序列。动态规划方法采用最优原则来建立用于计算最优解的递归式。,（3）动态规划(Dynamic Programming),最优原则：即不管前面的策略如何，此后的决

5、策必须是基于当前状态的最优决策。若不能保持最优原则，则不可应用动态规划方法。,动态规划的数学表现是递归、排列组合，在递归过程中会出现重复计算问题，为了解决这个开销，使用二维表格保存已计算出的结果，以便复用。,算法设计方法（4）,算法思想： 回溯是一种系统地搜索问题解的方法。为了实现回溯，首先需要为问题定义一个解空间（solution space），这个空间必须至少包含问题的一个解（可能是最优的）。,（4）回溯法（backtracking Method）,回溯方法的步骤如下： 定义一个解空间，它包含问题的解； 用适合于搜索的方式组织该空间； 用深度优先法搜索该空间，利用限界函数避免移动到不可能产

6、生解的子空间。,算法设计方法（5）分支定界,算法思想： 分支定界是另一种系统地搜索解空间的方法， 回溯法以深度优先的方式搜索解空间树T， 而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树T。 建立一个活节点表。 每个活节点仅有一次机会可以扩充，生成从该节点移动一步即可到达的所有新节点。 在生成的节点中，抛弃那些不可能导出（最优）可行解的节点，其余节点加入活节点表。 直到找到解或活动表为空，扩充过程才结束。,（5）分支限界（branch and bound）,算法设计方法（6）随机算法,算法思想： 在算法中引入随机因素，即通过随机因素选择算法的下一步操作。在许多情况下，一般算法比较复杂

7、，性能较差，很多具有很好平均运行时间的算法，在最坏的情况下，却具有很坏的性能。采用随机算法可以实现“平均情况下的”良好业绩的希望。,（6）随机算法（Randomized Algorithms ）,随机算法对所求解问题的同一个实例用同一随机算法求解两次可能得到完全不同的效果。这两次求解所需要的时间，甚至所得到的结果都可能会有相当大的差别。 随机算法包括： 数值概率算法 蒙特卡罗（Monte Carlo）算法 拉斯维加斯（Las Vegas）算法 舍伍德（Sherwood）算法,分治法,分治策略： 分治法是一种常用的算法技巧， 从字面上的看就是“分而治之”的意思， 把一个复杂的问题分成两个或更多的

8、相同或相似的子问题，再把子问题分成更小的子问题直到最后子问题可以简单的直接求解，将子问题的解的合并就得到原问题的解。,分治法在每一层递归上都有三个步骤： 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题； 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题； 合并：将各个子问题的解合并为原问题的解。,分治法,一、二基本都能满足，三是关键，能否利用分治法完全取决于问题是否具有第三条特征。 不具备第三条特征，则可以考虑用贪心法或动态规划法。 第四条特征涉及到分治法的效率，不能满足时采用动态规划法比用分治法更好。,分治法所能解决的问题一般具有以下几个特征： 该问

9、题的规模缩小到一定的程度就可以容易地解决； 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质； 利用该问题分解出的子问题的解可以合并为该问题的解； 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。,分治法,分治法算法框架 SolutionType DandC(ProblemType P) ProblemType P1,P2,.,Pk; if ( Small(P) ) return S(P); /解决小规模的问题 else Divide ( P,P1,P2,.,Pk ); /将问题分解成子问题P1,P2,.,Pk return Combine ( Da

10、ndC(P1), DandC(P2), ., DandC(Pk) ); /递归的解各子问题,并将各子问题的解合并为原问题的解 ,最近点对问题,问题描述： 在二维平面上的n个点中，如何快速的找出最近的一对点。 最简单的想法是暴力枚举每两个点，计算得出最小距离，需要计算n(n-1)/2次，时间复杂度为O(n2),分治法求最近点对问题,算法描述： 已知集合S中有n个点，分治法的思想就是将S进行拆分，分为2部分求最近点对。 算法每次选择一条垂线L，将S拆分左右两部分为SL和SR， L一般取点集S中所有点的中间点的x坐标来划分，这样可以保证SL和SR中的点数目各为n/2， 依次找出这两部分中的最小点对距

11、离：L和R， 记SL和SR中最小点对距离 = min（L，R）。,分治法求最近点对问题,对于SL虚框范围内的p点，在SR虚框中与p点距离小于的顶多只有六个点，就是下图中的2个正方形的6的顶点。（如果有第7个点则与的定义矛盾） 因此，计算时，只需计算SR中与p点距离最近的6个点，就可以求出最近点对。,以L为中心，为半径划分一个长带，最小点对还有可能存在于SL和SR的交界处， 如右图中的虚线带，p点和q点分别位于SL和SR的虚线范围内，在这个范围内，p点和q点之间的距离才会小于，最小点对计算才有意义。,贪心法,能够使用贪心算法的问题必须满足下面两个性质： 整体的最优解可以通过局部的最优解来求出；

12、一个整体能够被分为多个局部，并且这些局部都能够求出最优解。,贪心算法的基本步骤： 从问题的某个初始解出发； 当可以向求解目标前进一步时，就根据局部最优策略，得到一个部分解，缩小问题的范围或规模； 将所有部分解综合起来，得到问题的最终解。,在一些情况下，即使贪心算法不能得到整体最优解，但其近似最优解在许多情况下已经能满足某些问题的求解要求了。,背包问题,背包问题： 给定 n 种物品和一背包。每种物品 i 的重量是 wi ，其价值为 vi ，背包的容量为 C。 问：应该如何选择装入背包的物品，使得装入背包中物品的总价值最大？ 在选择装入背包的物品时，对每种物品 i 的选择，可以是装入背包或不装入背

13、包或只装入部分的物品 i 。该问题称为 分数背包问题。 如果在选择装入背包的物品时，对每种物品 i 只有两种选择，即装入背包或不装入背包。不能将物品 i 装入背包多次，也不能只装入部分的物品 i 。该问题称为 0-1背包问题。,0-1背包问题,0-1背包问题：对于0-1背包问题，贪心选择可能得不到最优解。因为在这种情况下，它无法保证最终能将背包装满，部分闲置的背包空间，使得每公斤背包空间的平均价值被降低了。 考虑在下面的0-1背包问题实例中，选择贪心策略为尽量装单位价值最大的物品，贪心策略得到的解不是最优的。,多机调度问题,多机调度问题： 某工厂有n个独立的作业，由 m 台相同的机器进行加工处

14、理。 作业 i 所需的加工时间为 ti， 任何作业在被处理时不能中断，也不能进行拆分处理。 要求算出 n 个作业由 m 台机器加工处理的最短时间。,这个问题是NP完全问题，到目前为止还没有有效的解法。,NP完全问题,NP完全问题（多项式复杂程度的非确定性问题）：生成问题的一个解通常比验证一个给定的解时间花费要多得多。 在一个周六的晚上，你参加了一个盛大的晚会。由于感到局促不安，你想知道这一大厅中是否有你已经认识的人。 主人向你提议说，你一定认识那位正在甜点盘附近角落的女士。不费一秒钟，你就能向那里扫视，并且发现你的主人是正确的。 然而，如果没有这样的暗示，你就必须环顾整个大厅，一个个地审视每一

15、个人，看是否有你认识的人。,多机调度问题的近似算法,解题思路： （1）当nm时，首先将n个作业从大到小排序。然后依此顺序分步将作业分配给空闲的处理机，每步分配给一个机器，而且需要考虑分配哪一个作业。 根据这种思想可利用如下贪心原则：从剩下的作业中，选择需要处理时间最长，然后依次选择处理时间次长的作业，直到所有的作业全部处理完毕，或者机器不能再处理其他作业。,采用最长处理时间作业优先的贪心选择策略，可以设计出解多机调度问题的较好的近似算法。,贪心法,很多情况下，贪心算法不能得到整体最优解，尽管如此，贪心算法也是应用最广泛的算法之一。许多时候，其近似最优解已经能满足问题的求解要求了。 贪心算法在计

16、算时最大的缺点是：在迭代时，很多时候会掉入到局部最优解，从而无法得到整体最优解。 改进：模拟退火算法、遗传算法等,回溯法,回溯法实际上是基于穷举的方法。 四个环节： 确定问题的可能解空间，相当于找出进行穷举的搜索范围。 以一种便于搜索的方式组织所有的可能解，一般是生成可能解空间树。 以深度优先搜索方式搜索可能的解空间树（回溯技术）。 在搜索过程中利用判定函数，也称为限界函数，通过“剪枝”来加速搜索过程。,回溯法0-1背包问题,0-1背包问题：n=3，w=16,15,15,p=45,25,25,c=30。 解空间可以用完全二叉树表示，叶子结点如下： (1,1,1),(1,1,0),(1,0,1)

17、,(1,0,0),(0,1,1),(0,1,0),(0,0,1),(0,0,0) 求解过程相当于在树中搜索满足条件的叶结点。 子集树：当所给问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树称为子集树。,回溯法旅行商问题,旅行商问题： 设G是带权图。图中各边的费用（权）为一正数。一条周游路线是包括图中每个顶点的一条回路。其费用就是该路线上所有边的费用总和。 对于该问题，每一个旅行可表示为顶点序列的一个排列。在解空间树中，每一个旅行都由树中的一条从根到叶的路径来表示。 排列树： 当所给问题时确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。,回溯法递归实现,递归回溯：回

18、溯法对解空间作深度优先搜索，因此，在一般情况下用递归方法实现回溯法。 void backtrack (int t) /t表示递归深度 if (tn) output(x); /n表示深度界限 else for (int i=f(n,t);i=g(n,t);i+) / f(n,t)，g(n,t)分别表示 /当前扩展结点未搜索过的子树的起始编号和终止编号 xt=h(i); if (constraint(t) ,回溯法迭代实现,迭代回溯：采用树的非递归深度优先遍历算法，可将回溯法表示为一个非递归迭代过程。 void iterativeBacktrack () int t=1; while (t0) i

19、f (f(n,t)=g(n,t) for (int i=f(n,t);i=g(n,t);i+) xt=h(i); if (constraint(t) ,八皇后问题,八皇后问题：在88格的国际象棋上摆放八个皇后，使其不能互相攻击。 例如，八皇后问题的一个解：可由八元组（4,6,8,2,7,1,3,5)来表示。是1到8共8个数字的全排列。,四皇后问题,为了简化问题，我们讨论四皇后问题。 解空间树是一个完全4叉树，树的根结点表示搜索的初始状态， 从根结点到第2层结点对应皇后1在棋盘中第1行的可能摆放位置， 从第2层结点到第3层结点对应皇后2在棋盘中第2行的可能摆放位置， 依此类推。 回溯法求解4皇后

20、问题，是对完全4叉树的搜索过程,四皇后问题回溯过程 - 1,四皇后问题的回溯算法的搜索过程图示 从结点1到结点2，满足条件，放置皇后x1=1,继续搜索,四皇后问题回溯过程 - 2,结点3不满足条件，回溯到结点2； 再向下搜索到结点8； 满足条件，放置皇后x2=3,继续搜索,四皇后问题回溯过程 - 3,结点9不满足条件， 回溯到结点11，仍不满足条件； 这时经结点8，回溯到结点2,四皇后问题回溯过程 - 4,向下搜索到结点13，满足条件，放置第二个皇后x2=4; 继续向下搜索到结点14，满足条件，放置第三个皇后x3=2;,四皇后问题回溯过程 - 5,向前搜索到结点15，不满足条件（只测试x4=3

21、的情形）， 回溯搜索到结点16，仍不满足条件,四皇后问题回溯过程 - 6,回溯到结点1后，向下搜索到结点18，x1=2,四皇后问题回溯过程 - 7,结点19不满足条件， 回溯到结点24后，也不满足条件； 回溯到结点29之后满足条件，x2=4,四皇后问题回溯过程 - 8,结点30满足条件，x3=1； 再向前搜索到结点31，满足条件，x4=3； 此时，i=4，找到解,0-1背包问题的回溯算法,0-1背包问题： 以n=3，w=16,15,15,p=45,25,25,c=30。为例： 解空间可以用完全二叉树表示 (1,1,1),(1,1,0),(1,0,1),(1,0,0),(0,1,1),(0,1,

22、0),(0,0,1),(0,0,0),0-1背包问题的回溯算法,E-结点和活结点 死结点,R=14 V=45,Rw2 x,16 45,R=30 V=0,R=15 V=25,30 50,Rw3 x,R=0 V=50,15 25,15 25,0 0,随机算法,数值概率算法 常用于数值问题的求解。 将一个问题的计算与某个概率分布已经确定的事件联系起来，求问题的近似解。 这类算法所得到的往往是近似解，且近似解的精度随计算时间的增加而不断提高。 在许多情况下，要计算出问题的精确解是不可能或没有必要的，因此可以用数值随机化算法得到相当满意的解。,随机算法,蒙特卡罗算法 用于求问题的准确解，但得到的解未必是

23、正确的。 蒙特卡罗算法以正的概率给出正解，求得正确解的概率依赖于算法所用的时间。算法所用的时间越多，得到正确解的概率就越高。 一般给定执行步骤的上界，给定一个输入，算法都是在一个固定的步数内停止的。 对于求解最优解问题：采样越多，越近似最优解； 例如，假如筐里有100个苹果，让我每次闭眼拿1个，挑出最大的。于是我随机拿1个，再随机拿1个跟它比，留下大的，再随机拿1个我每拿一次，留下的苹果都至少不比上次的小。拿的次数越多，挑出的苹果就越大，但我除非拿100次，否则无法肯定挑出了最大的。这个挑苹果的算法，就属于蒙特卡罗算法尽量找好的，但不保证是最好的。,随机算法,拉斯维加斯算法 不会得到不正确的解

24、。一旦用拉斯维加斯算法找到一个解，这个解就一定是正确解。但有时可能找不到解。 拉斯维加斯算法找到正确解的概率随着它所用的计算时间的增加而提高。对于所求解问题的任意实例，用同一拉斯维加斯算法反复对它求解，可以使求解失效的概率任意小。 对于求解最优解问题：采样越多，越有机会找到最优解； 例如，有一把锁，给我100把钥匙，只有1把是对的。于是我每次随机拿1把钥匙去试，打不开就再换1把。我试的次数越多，打开（最优解）的机会就越大，但在打开之前，那些错的钥匙都是没有用的。这个试钥匙的算法，就是拉斯维加斯的尽量找最好的，但不保证能找到。,随机算法,舍伍德算法 总能求得问题的一个解，且所求得的解总是正确的。

25、 是对一个确定性算法的改造。 当一个确定性算法在最坏情况下的计算复杂性与其在平均情况下的计算复杂性有较大差别时，可在这个确定性算法中引入随机性将它改造成一个舍伍德算法，消除或减少问题的好坏实例间的这种差别（精髓所在）。,八皇后问题拉斯维加斯算法,对于n皇后问题的任何一个解而言，每一个皇后在棋盘上的位置无任何规律，不具有系统性，而更象是随机放置的。由此容易想到使用拉斯维加斯算法。 拉斯维加斯算法 在棋盘上相继的各行中随机地放置皇后，并注意使新放置的皇后与已放置的皇后互不攻击，直至n个皇后均已相容地放置好，或已没有下一个皇后的可放置位置时为止。 缺点：效率很低 回溯法和拉斯维加斯算法结合 如果将上

26、述随机放置策略与回溯法相结合，可能会获得更好的效果。可以先在棋盘的若干行中随机地放置皇后，然后在后继行中用回溯法继续放置，直至找到一个解或宣告失败。随机放置的皇后越多，后继回溯搜索所需的时间就越少，但失败的概率也就越大,蒙特卡洛算法,问题： 某食品加工厂主要生产即食产品，一般当天生产的产品必须当天售出，否则就会出现不能保质、或变质、造成一定的经济损失，如果市场需求量大而生产量不足，则也会影响工厂的销售收入，该产品的单位成本为1.5元，单位产品售价为4元。工厂为了避免产品滞销存货过多而造成的经济损失，提出了如何制定合理的生产与库存数量的方案问题，能够使得工厂能有尽可能多的收益，经初步考虑拟从以下

27、两种生产与库存方案中选出一个较好的方案： 方案(1)：按前一天的销售量作为当天的生产库存量。 方案(2)：按前两天的平均销售量作为当天的生产库存量。 基本思路： 利用蒙特卡罗方法随机模拟市场对该产品需求量。 假设市场对该产品的每天需求数量是一个随机变量，并且根据实际数据从统计学的角度分析得知，该随机变量服从正态分布。,大数据问题,大数据要求要有相适应的算法 为处理海量数据（数千兆字节），算法必须是可伸缩的 新的数据结构 使用抽样技术或开发并行和分布算法 高维数据 具有数以百计或数以千计属性（维度）的数据集 生物信息学中，涉及数千特征的基因表达数据 为低维数据设计的算法不能很好地处理高维数据 某

28、些算法，随着维度的增加计算复杂性迅速增加，使得不再可行 异种数据和复杂数据 属性类型不同的数据，以及具有时间空间相关性的数据 针对异种数据和复杂数据设计算法 半结构化文本和超链接的Web页面集 具有序列和三维结构的DNA数据,大数据问题应用1：分类问题,欺诈检测 目标: 预测信用卡交易欺诈案件. 方法: 使用信用卡交易及其账户持有人的信息作为属性. 顾客什么时候买，他买什么，他多久付款？ 将过去的交易标记为欺诈或公平交易。这就形成了类属性. 学习交易模型. 使用此模型通过观察帐户上的信用卡交易来检测欺诈行为.,大数据问题应用2：关联规则,超市货架管理. 目标: 识别出来有足够多的顾客会一起购买

29、的物品. 方法: 用条码扫描仪采集销售点数据，查找项目之间的依赖关系. 一个经典的规则- 如果顾客买尿布和牛奶，那么他很可能买啤酒. 所以，不要惊讶，如果你发现六听啤酒堆放在尿布旁边!,大数据问题应用3：文档聚类,聚类点：洛杉矶时报3204篇. 相似性度量: 这些文档中有多少共同的单词（经过一些单词过滤）,大数据问题应用4：异常检测,臭氧层破坏的历史 1985年，三位研究者（Farman、贾地纳和Shanklin）困惑于由英国南极调查收集的数据。数据显示，南极臭氧层已经下降到了低于正常水平的10%。 为什么光轮7卫星，装备有可以记录臭氧水平的仪器，不记录同样低的臭氧浓度？ 卫星记录的臭氧浓度很

30、低，被计算机程序视为异常值，并且被丢弃了！,Sources: .au/ozone.html /ozone/science/hole/size.html,针对大数据问题的算法,分类问题 基于规则（ Ripper， CN2， Holtes 1R等算法）；决策树（ CART， ID3， C4.5等算法）；最近邻算法；贝叶斯算法；神经网络（深度学习）算法；支持向量机；遗传算法；模糊算法；其它算法（Boosting， AdaBoost，随机森林等） 关联分析问题 Apriori算法，FP 增长算法， GSP算法， S

31、PADE算法等 聚类分析问题 K-means， DBSCAN，模糊c均值算法，EM算法，PAM（适应小样本）， CLARANS（适应大样本）， AGNES和DIANA，DENCLUE算法， Chameleon BIRCH，CURE算法（可伸缩） 异常检测问题 Grubbs检验，k-最近邻方法，基于LOF（局部异常因子）方法， CBOD方法等,支持向量机（SVM）,基本思路： 找到一个超平面，使得两个类别样本分别位于这个超平面的两侧。 并且使得决策边界的边缘最大化,SVM(续),EM算法（最大期望算法）,例：20000个数据点，采用高斯混合模型，假定知道了两个分布的标准差都是2.0，并且点以相等

32、的概率由两个分布产生。,EM算法（续）,EM算法： 采用高斯模型，两个分布的标准差2.0，均值取初值1=-2，2=3。 初始参数=(, )： 1=(-2,2)， 2=(3,2) EM期望：计算每个点属于每个分布的概率，由贝叶斯规则计算 最大化：计算1，2 的新估值。 重复计算，直到1，2 的估值不再改变，或变化很小,人工神经网络发展概述,神经网络最早是由心理学家和神经学家提出的，旨在模拟生物学习的计算模型，即大脑怎样学习或为什么能学习的模型 三次浪潮： 20 世纪40年代到 60 年代神经网络和深度学习的雏形出现在控制论（cybernetics）中 线性模型有很多局限性导致了神经网络热潮的第一

33、次大衰退 20 世纪 80 年代到 90 年代表现为联结主义（connectionism） 联结主义的中心思想是，当网络将大量简单的计算单元连接在一起时可以实现智能行为。 在那个时候，人们普遍认为深度网络是难以训练的。现在我们知道，20 世纪 80年代就存在的算法能工作得非常好，但是直到在 2006 年前后都没有体现出来。这可能仅仅由于其计算代价太高，而以当时可用的硬件难以进行足够的实验。 直到 2006 年，才真正以深度学习之名复兴 Georey Hinton 表明名为深度信念网络的神经网络可以使用一种称为贪婪逐层预训练的策略来有效地训练,人工神经元模型,人工神经元模型可以看成是由三种基本元

34、素组成： (1)一组连接： 连接强度由各连接上的权值表示，权值可以取正值也可以取负值，权值为正表示激活，权值为负表示抑制。 (2)一个加法器 用于求输入信号对神经元的相应突触加权之和。 (3)一个激活函数 用来限制神经元输出振幅。激活函数也称为压制函数，因为它将输入信号压制(限制)到允许范围之内的一定值。 另外，可以给一个神经元模型加一个外部偏置，其作用是增加或降低激活函数的网络输入。,人工神经元模型,假定神经元接受 n 个输 入 x = (x1, x2, , xn)， 用状态 z 表示一个神经元所获得的输入信号 x 的加权和， 该神经元的输出为 a。 具体定于如下： z = wT x + b

35、 a = (z) 其中： w 是 n维的权重向量， b 是偏置。 是激活函数。比较典型的有sigmoid 型函数、非线性斜面函数等。,神经网络的激活函数,线性函数,S型函数,双曲正切函数,符号函数,人工神经网络的互联结构,根据神经元的不同连接方式，可将神经网络分为以下类别： 分层网络 前馈网络 反馈网络 层内互联的前向网络 相互连接型网络,分层网络,相互连接型网络,人工神经网络的学习,人工神经网络的学习方式 有导师学习 有监督学习 样本集合中每个样本是：由输入向量与其对应的输出向量构成一个“训练对”。 无导师学习 无监督学习 抽取样本集合中蕴含的统计特性，并以神经元之间的联接权的形式存于网络中

36、。 再励学习 外部环境对系统的输出结果给出评价，学习系统通过强化受奖的动作来改善自身性能。,人工神经网络的学习,学习算法： 学习算法是指针对学习问题的明确规则 不同的学习算法对神经元的权值调整的表达式是不同的。 算法分类 Hebb学习算法 学习算法 随机学习算法 竞争学习算法,人工神经网络的学习,Hebb学习算法 由Donald O. Hebb提出。如果两个神经元同时兴奋，则它们之间的突触连接加强。如果神经元 I 是神经元 j 的上层结点，用 vi, vj 分别表示两神经元的激活值(输出)，wij表示两个神经元之间的连接权，则Hebb学习规则可以表示为: wij=vivj 式中表示学习速率 H

37、ebb学习规则是人工神经网络学习的基本规则，几乎所有神经网络的学习规则都可以看作Hebb学习规则的变形,人工神经网络的学习,人工神经网络的学习,随机学习算法 误差学习算法通常采用梯度下降法，存在局部最小问题，随机学习算法通过引入不稳定因子来处理这种情况。 经典随机学习算法 模拟退火算法 遗传算法。,人工神经网络的学习,竞争学习算法 竞争学习属于无导师算法 神经元通过互相竞争来做出不同的响应 竞争获胜的神经元按规则修正权值 经典竞争学习神经网络 自组织特征映射网络(Self-Organization Map，SOM) 自适应共振网络(Adaptive Resonace Theory，ART),人

38、工神经网络模型,常用的网络模型已有数十种。例如： 传统的感知机模型， 具有误差反向传播功能的反向传播网络模型， 采用多变量插值的径向基函数网络模型， 建立在统计学习理论基础上的支撑向量机网络模型， 采用反馈联接方式的反馈网络模型， 基于模拟退火算法的随机网络模型。,二类感知器,二类感知器,二类感知器学习算法,给定 N 个样本的训练集: (xi, yi), i = 1, , N。我们希望学习到参数 w，使得 wT xi 0 当yi 0 wT xi 0 Rosenblatt 1958首次提出了感知器的学习算法。这个算法是错误驱动的在线学习算法。先初始化一个权重向量w0（通常是全零向量），然后每次分

39、错一个样本时，就用这个样本来更新权重。,二类感知器学习算法,二类感知器学习算法,单层感知器的局限,感知器的输出只能取0或1。 单层感知器只能对线性可分的向量集合进行分类。 明斯基（Minsky）于1969年发表了 Perceptron 一书。 书中指出感知器仅能解决一阶谓词逻辑问题，不能解决高阶谓词逻辑问题,并给出了一个简单的例子，即XOR（异或）问题,BP神经网络,BP网络是在输入层与输出层之间增加若干层(一层或多层)神经元，这些神经元称为隐单元 BP神经网络的计算过程由正向计算过程和反向计算过程组成。 正向传播过程，输入模式从输入层经隐单元层逐层处理，并转向输出层，每一层神经元的状态只影响

40、下一层神经元的状态。 如果在输出层不能得到期望的输出，则转入反向传播，将误差信号沿原来的连接通路返回，通过修改各神经元的权值，使得误差信号最小。 BP网络主要用于以下四个方面 1)函数逼近：用输入向量和相应的输出向量训练一个网络逼近一个函数。 2)模式识别：用一个待定的输出向量将它与输入向量联系起来。 3)分类：把输入向量所定义的合适方式进行分类。 4)数据压缩：减少输出向量维数以便于传输或存储。,BP神经网络,例: 一个多层前馈神经网络 训练样本X = x1 ,x2 ,., xi馈入输入层.每层之间存在加权连接; 其中, wij表示由某层的单元j到前一层的单元i的权,反向传播算法,反向传播算

41、法:例,一个多层前馈神经网络 第一个训练样本X = 1,0,1（其类标号为1）,反向传播算法:例(续),初始输入、权值和偏差值 净输入和输出的计算 计算每个结点的误差,反向传播算法:例(续),计算权和偏置的更新,BP神经网络的几个问题,收敛速度问题 BP神经网络收敛速度相对是比较慢的。 训练ANN是一个很耗时的过程 局部极小点问题 使用的梯度下降方法经常会收敛到局部最小值 逃离/避开局部极小点：修改W、V的初值并不是总有效。 网络瘫痪问题 在训练中，权可能变得很大，这会使神经元的网络输入变得很大，从而又使得其激活函数的导函数在此点上的取值很小。此时的训练步长会变得非常小，进而将导致训练速度降得

42、非常低，最终导致网络停止收敛,BP算法中的梯度消失问题,误差从输出层反向传播时，在每一层都要乘以该层的激活函数的导数。 当我们使用 sigmoid 型函数：logistic 函数 (x) 或 tanh 函数时，其导数为： (x) = (x)(1 (x) 0, 0.25 tanh(x) = 1 (tanh(x)2 0, 1 可以看到，sigmoid 型函数导数的值域都小于 1。 这样误差经过每一层传递都会衰减。当网络层数很深时，梯度就会不停的衰减，甚至消失，使得整个网络很难训练。 这就是所谓的梯度消失问题（Vanishing Gradient Problem），也叫梯度弥散。,深度神经网络,20

43、06年，加拿大多伦多大学教授、机器学习领域的泰斗Geoffrey Hinton在科学上发表论文提出深度学习主要观点： 1）多隐层的人工神经网络具有优异的特征学习能力，学习得到的特征对数据有更本质的刻画，从而有利于可视化或分类； 2）深度神经网络在训练上的难度，可以通过“逐层初始化”（layer-wise pre-training）来有效克服，逐层初始化可通过无监督学习实现的。,深度学习 vs. 神经网络,神经网络 ： 深度学习：,深度学习训练过程,第一步：采用自下而上的无监督学习 1）逐层构建单层神经元。 2）每层采用wake-sleep算法进行调优。每次仅调整一层，逐层调整。 这个过程可以看

44、作是一个feature learning的过程，是和传统神经网络区别最大的部分。,深度学习训练过程,wake-sleep算法: 1）wake阶段： 认知过程，通过下层的输入特征（Input）和向上的认知（Encoder）权重产生每一层的抽象表示（Code），再通过当前的生成（Decoder）权重产生一个重建信息（Reconstruction），计算输入特征和重建信息残差，使用梯度下降修改层间的下行生成（Decoder）权重。也就是“如果现实跟我想象的不一样，改变我的生成权重使得我想象的东西变得与现实一样”。 2）sleep阶段： 生成过程，通过上层概念（Code）和向下的生成（Decoder）

45、权重，生成下层的状态，再利用认知（Encoder）权重产生一个抽象景象。利用初始上层概念和新建抽象景象的残差，利用梯度下降修改层间向上的认知（Encoder）权重。也就是“如果梦中的景象不是我脑中的相应概念，改变我的认知权重使得这种景象在我看来就是这个概念”。,深度学习训练过程,Encoder,Decoder,Input Image,Class label,Features,Encoder,Decoder,Features,Encoder,Decoder,AutoEncoder:,深度学习训练过程,第二步：自顶向下的监督学习 这一步是在第一步学习获得各层参数进的基础上，在最顶的编码层添加一个分

46、类器（例如罗杰斯特回归、SVM等）， 而后通过带标签数据的监督学习，利用梯度下降法去微调整个网络参数。 深度学习的第一步实质上是一个网络参数初始化过程。区别于传统神经网络初值随机初始化，深度学习模型是通过无监督学习输入数据的结构得到的，因而这个初值更接近全局最优，从而能够取得更好的效果。,深度神经网络,卷积网络 循环神经网络 无监督卷积网络 深度玻尔兹曼机 分布式自编码器 回声状态网络 深度信念网络 ,卷积神经网络,CNN（卷积神经网络）的核心出发点有三个 局部感受野。 模仿眼睛看东西的时候，目光是聚焦在一个相对很小的局部。 在卷积神经网络中，每个隐层节点只连接到图像某个足够小局部的像素点上，

47、从而大大减少需要训练的权值参数。 权值共享。 如同某个神经中枢中的神经细胞，它们的结构、功能是相同的，甚至是可以互相替代的。 在卷积神经网中，同一个卷积核内，所有的神经元的权值是相同的，从而大大减少需要训练的参数。 池化 如同人的视觉，先随便看向远方，然后闭上眼睛，你仍然记得看到了些什么，但是你不会完全回忆起每一个细节？ 在卷积神经网络中，没有必要一定就要对原图像做处理，而是可以使用某种“压缩”方法，这就是池化，也就是每次将原图像卷积后，都通过一个下采样的过程，来减小图像的规模。,卷积神经网络,Feature extraction layer Convolution layer,Shift and distortion invariance or Subsampling layer,C,S,Feature maps,卷积神经网络,卷积 假设有二维离散函数 f(x, y), g(x, y) ， 那么它们的卷积定义为 图中神经元的卷积如下,卷积神经网络,卷积层 对数据进行