最优化问题的简洁介绍是什么?

点击次数:   更新时间:2020-06-30 00:23     来源:365官网

  因为有人问我,为什么学习机器学习必须要看最优化的书。我没有想到最合适的解答。 从百度百科抄了一段,但是总觉得没讲到核心问题。 最优化方法(也称做运筹学 方法)是近几十年形成的,它主要运用数学方法 研究各种系统的优化途径及方案,为决策者提供科学决策的依据。最优化方法的主要研究对象是各种有组织系统 的管理问题及其生产经营活动。最优化方法的目的在于针对所研究的系统,求得一个合理运用人力、物力和财力的最佳方案,…

  构造一个合适的目标函数,使得这个目标函数取到极值的解就是你所要求的东西;

  你看,计算机的回复往往是“你丫能不能说机话!”这是因为计算机是无法进行抽象思维的,它不懂重建、去噪、清晰这些复杂的概念,它唯一会的东西就是加减乘除这样的基本运算,你只能使用正确的计算机语句让它去执行对应的基本运算,因此就需要首先把去噪问题转化成一个数学问题,一个函数的求解问题。比如可以试着这样想,去噪,就是要把图像变平滑,于是你对计算机说:给爷来张图片,无比光滑。计算机的回答是:

  真的是好光滑,但是且慢!摄像师哪去了?你是想光滑图像,但是也需要保留图像中的有用细节。这就说明你设计的目标不合理。一个好的去噪的目标,应该兼顾两个要求:与原始图像尽量接近,并且尽量光滑。一个合适的目标可以是:寻找一幅图像A,让下面这个目标函数J最小:

  我们要寻找的,就是能让目标函数J最小的图像A,能够兼顾相似和平滑两个要求。因子r用来权衡二者的重要程度。当r取0时,我们得到的最优目标图像就是原始图像自己!因为我们的目标只是相似,而原始图像自己和自己最像,但是这样就没有任何平滑效果;当r取无穷大的时候,为了让整个目标函数J不至于无穷大,我们必须保证A无比平滑,这样就得到上面那张过度平滑,与原始图像毫不相似的无意义图片。因此,为了兼顾两个目标,我们需要把r的值取得不大不小。

  有了一个合适的目标函数,下面就需要构造一种获得它的极小值的算法。在图像去噪领域有一大堆算法:卷积去噪、中值去噪、双边滤波、偏微分方程、小波去噪、随机场去噪......它们的作用或多或少都是相同的——求上面那个混合目标函数的最小值。计算机运算获得的去噪图像是:

  从这个成功去噪的例子中我们可以看出:合理的目标函数是最优化第一个需要精心考虑的问题,需要直觉和理性;而如何求解目标函数,则是一个数学算法问题。二者都是数学家们和工程师们大显身手的地方。

  题主困惑机器学习和最优化之间为什么联系紧密,是因为对机器学习这个领域不太了解,实际上研究最优化方法最多的人都在这个领域。机器学习的目的,就是为了让计算机代替人来发现数据之间隐藏的关系。

  之所以要使用计算机,是因为数据量太大,远远超过人脑的处理能力。比如我们需要从一堆人脸图片里给每个人标上正确的名字,一幅32像素见方的人脸图像有1024颗像素点,你能想象出一百万张这样的照片和1万个人名字之间的关系是什么样吗。再比如给你1万个患者的DNA序列,每个患者的序列由百万级的碱基对构成,你能找到这些天文数字量级的序列和是否患某种疾病之间的联系吗?

  答案是不能!所以研究者退而求其次,建立很多学习模型,这些模型输入是一个样本的数据(头像图片、一个人的DNA序列),输出是样本的标签(人名、是否患病)。模型里有大量可以调整的参数,这些参数通过训练,能够学习到数据和标签之间人类无法直接理解的、复杂的关系。科学家期望当模型训练完成后,再拿来一个样本,喂给这个训练好的机器,它能够吐出一个标签,这个标签恰好就是样本对应的那个正确的标签。

  目前人们已经研究出一大堆学习模型:神经网络、支持向量机、AdaBoost、随机森林、隐马尔科夫链、卷积神经网络等等。它们的结构差异很大,但是共同点都是拥有一大堆参数,就等着你喂给它数据供它学习。这些模型的学习也需要一个目标函数:

  。为了达到目的,模型的训练往往首先给参数赋上随机初值,然后用各种下降法来寻找能让分类错误率更小的参数设置,梯度下降、牛顿法、共轭梯度法和Levenberg—Marquard法都是常见的方法。

  随着研究的深入,问题也越来越多,比如下降法往往只能保证找到目标函数的局部最小值,找不到全局最小值,怎么办呢?答案是不一味下降、也适当爬爬山,说不定能跳出小水沟(局部极小值)找到真正的深井(全局极小值),这种算法叫模拟退火。也可以增大搜索范围,让一群蚂蚁(蚁群算法)或者鸟儿(粒子群算法)一齐搜索,或者让参数巧妙地随机改变(遗传算法)。

  那么多模型,到底该选哪个?研究者又发现了一个定理“天下没有免费的午餐”定理,意思是没有一个模型能一直比其他模型好,对于不同类型的数据,必须要通过实验才能发现哪种学习模型更适合。机器学习领域也就成了学界灌水严重的领域之一——换模型、调参数就能发文章哎。

  下面说到了调参数,问题又来了,到底是参数多了好还是少了好?参数少了模型太笨学不到数据内的复杂关系,参数多了模型太精明又可能会把数据中的随机噪声当作某种关系进行认真学习(过拟合)。最后大家一致认为,确定模型的复杂度时,要保证模型能力足够强,能够学会数据之间的关系,能力又不能太强,以至于耍小聪明乱学习。这种选择模型的思想被称为奥卡姆剃刀:选择有能力的模型中最简单的那个。此外,训练模型的目标并不是为了使训练样本能够被尽量正确分类,更需要对未知新样本有好的分类效果,这样模型才有实用价值,这种能力被称为泛化能力。除了奥卡姆剃刀原理外,训练时引入随机性的模型比确定的模型(比如BP神经网络)具有更好的泛化能力。

  模型的更新也是问题。如果引入了新数据,全部模型都需要重新训练是一笔很大的开销,在线学习模型采用来一个样本学一点的模式,能够不断自我更新;半监督学习利用少量带标签的样本训练一个原始模型,然后利用大量无标签数据再学习。

  咱们来看看一些经典的学习模型能做成啥样。首先随便画点散点图,红色和白色是两类不同的数据,分类器需要对整个空间做分割,让平均分类错误率尽量小。你可以先想想如果让你来分要如何划分。

  如果神经元数目变成10个,学到的模式将会十分怪异,说明模型过于复杂了:

  下面是支持向量机的分类结果,这是这几十年机器学习最重要的成果之一,它的发明是基于结构最小化准则,通俗地讲就是把目标函数设为:

  接下来是随机树,它把空间划分为一系列矩形区域(叶子),所有的叶子区域由一颗树形结构从根节点不断划分而成,随机的意思是树的生长每次划分第一维还是第二维是随机的:

  在机器学习领域,还有很多重要问题被不断讨论,优秀的模型也不断在涌现。这个领域的开山模型是神经元,由其组成的多层神经网络由于训练速度慢、分类效果不佳,在支持向量机出现后很快就失去了热度。大家卯着劲研究怎么面对训练样本不足的窘境,PCA和核方法大行其道,前者致力于减少数据维数,后者致力于从低维数据中学习高维结构。但是近几年随着卷积神经网络的流行,神经网络又焕发出了第二春,研究者发现只要样本量足够大(百万级甚至亿级样本量),网络参数足够多(百万级参数),加上巧妙的防过拟合技术,利用现代并行计算带来的强大计算能力,神经网络能够学得和人类的判别能力一样好。机器学习领域发展了几十年,似乎又回到了出发的地方。

  优化的目的是在选取一个(或一些决策),在满足一定约束情况下,尽可能达到某一目标。在去思考优化问题时,最好的顺寻就是问以下问题:

  事实上,所有的决策问题,小到我们生活中的每一个选择,大到国家的战略,都可以分解为这样的三部分(包括所有的机器学习问题)。因此优化的思想可以说是在人们的生活中无处不在,也是世间万物的一种基本规律。数学家欧拉早在18世纪就说过:

  在实际中,搞清楚实际问题的这三部分分别是什么,并且用合理的方式去表达是最解决问题中最终要的一步。完成了这一步(所谓的建模)通常已经完成了解决问题的绝大部分。后面就需要用到优化的算法。这两部分也是学习运筹优化的核心。

  因为机器学习其实本质是机器进化,通过算法的方式进化出最适应需求(最优化函数)的“模式”。进化的过程和算法就是最优化的核心研究课题,所以刚好这个数学工具能为机器学习提供很好的帮助。

  严格定义是对某个定义域为Q,值域为某个有序集R(一般研究R=实数的情形)的函数f,求x属于Q使得f(x)最小(大)。

  这个东西和机器学习有什么关系呢?机器学习中Q一般是一个函数构成的空间,比如希尔伯特空间。

  然后比如你要学习出一个函数,函数q你希望输入是128*128的图像像素矩阵,输出是判断图像是否代表一个美女。

  然后你要制定一个标准,这个标准可以衡量q这个函数的质量,比如q输出和实际情况相比的误差什么的,不展开讨论,总之这个标准可以定义为一个函数,叫做v。v(q)越大,函数质量越高,越接近你想要的结果

  那么从数学上,你这个问题就转变成了在Q这个空间内寻找v(q)的最大值这个最优化问题。

  当然世纪上,因为Q这个空间的结构可能非常扯淡,因而这个问题基本不可能有解析解。所以要用数值方法:

  还有就是设法取一个Q的性质比较好的子集。比如所有从128*128的图像像素矩阵到0/1这个函数空间性质太差了。那么比如说:

  要理解的其实只有两个概念,函数和约束条件。甚至函数这个概念已经包含了对约束条件的考虑。

  所谓函数,简单理解的话,可以当做一个机器,你给它一个输入,它就给你一个输出,它是一个对应。你通过调节输入,达到最好的输出。它是现实状况的数学语言表达。例如我们要最小化总费用,我们知道单价,我们可以决定数量,于是我们得到的数学表达:总费用=单价乘以数量。我们通过调整数量来最小的总费用。

  至于约束条件,它有很多种,例如等式的约束,不等式的约束,微分方程的约束,概率的约束,等等等等。他们也是对我们现实状况中的约束的数学表达。

  不同的约束配上不同的目标函数就会得到一个不同的问题。例如目标函数和约束都是线性的,这个最优化问题就叫线性规划,如果约束是个常微分方程,就叫最优控制。等等等等。

  这些问题有的好解,有的不好,所以其实数学建模在这里头的作用很大。对于一个现实问题,建立一个简单好解又能较好地描述现实情况的模型,是一种艺术。这是数学界甚至科学界追求的美的原则:

  在机器学习领域有个普遍的观点:所有机器学习的问题最后都转换为了最优化问题。

  拟合,你甚至可以选择更高维的曲线拟合,那么选择哪个? -- 最优化问题

  两堆数据点,你想在中间画一条直线,将其分开,实际上这样的直线很多,选择哪一个?最优化问题。

  任何一个机器学习问题,我们提一个模型来描述问题很简单,所有可能的模型组成了假设空间。

  那么机器学习最后都转化到 在假设空间中找到最优解。 求最优解的策略很多,选择经验风险最小化或结构风险最小化,最后都还是最优化问题。

  当然机器学习的内容肯定不止于此,数据、模型、算法都有很多内容值得探索。

  先吐个槽: 最高票答案用图像去噪等实例来说明, 说得挺好的. 但是其他大部分答案真是不敢恭维, 实在忍不住我也来说几句吧.

  当然, 等式也可以上界下界相等的不等式来表示, 所以, 也有人只用不等式约束来表示一般的最优化问题. 另外, 有些问题的变量可以在整个空间取, 也就变成了无约束的问题.

  ps: 一般来说, 我们都可以将目标函数及约束用数学公式表达出来 (这就是建模), 但对于某些特别的黑箱问题, 可能我们并不知道它们的具体形式, 一般会假设, 给定一个输入, 会产生一个输出. 无导数优化方法 (derivative-free optimization, DFO) 就是一类用来解决此类问题的算法.

  pps: 上面是关于优化问题的简单介绍, 而优化算法, 实在太多, 但跟问题无关, 在此不介绍了.

  比如想从广州去杭州,怎样最快又最经济(目标函数)?你有很多种方法,可以坐火车,飞机,汽车(很多种解,而且可以对这些解进行组合),但总是有个组合最让你满意(最优解),最符合你的期望。怎么去求解这个最优解,由此产生的一系列方法。

  最优化就是对于有n个参量和一个评价函数的问题,转换为对n+1维空间内的n维图形求一个方向上(评价函数)最远点问题。

  首先,从数学上说,所有问题的所有限制都可以转化为参数和约束条件。其次,多个评价函数组成的评价体系最终都可以用一个评价函数来描述(也许不直观但是可行)。

  比方说一个参数一个函数的最优化问题其实就是二维平面上一条曲线的最值点问题;两个函数就是三维空间的一个曲面的最值问题。

  线性规划等非遍历算法的核心都是通过已知条件将问题降维的过程。遍历型算法都是走遍每一个可能的取值点求值然后比较,取最值的过程(当然存在一些优化)。运筹学范畴的最优化问题本质都是如此,只是提出各种常见条件下的简化计算的方法。

  机器学习的核心仍是输入一系列参数,输出一个结果,只不过它实际使用的参数除了显式输入之外还有学习过程中带来的参数积累,本质仍是最优化过程。

  Maximumize utility while minimizing loss,try not break any constraints or model assumptions. If you cant, use a numerical method, run a few scenarios and be prepared for surprises.

  最优化,这个词可以理解成最优化问题,也可以理解成最优化方法。我一般都理解成优化问题及求解的方法。关于优化的学科个人就学过几门:最优化算法、运筹学、计算智能、最优控制、数学分析里也有。

  就优化问题而言,除了形式直接的优化问题,方程和方程组也可以转换成优化问题。从应用来看,常见到的有图像去噪和路径搜索。问题分类的话,就看角度了,可分凸和非凸、离散和连续、无约束和带约束。

  就优化方法而言,以前看一篇论文,有个搜索方法的图谱,其实也就是优化方法,分两大类:随机的方法、微积分的方法。随机的比如遗传算法,微积分的比如梯度法。

  以优化方法中的下降方法(梯度法和牛顿法等)为例谈谈我的认识。实际上就是我们要到一个地方去,但这个地方我们也不知道,于是,离这个地方的远近通过指标来衡量(停止条件),问题知道了,然后我们从一个起点出发(迭代初值),出发前就先要确定迈步子的方向(下降方向)和步子的大小(迭代步长),走完一步检查一下是不是到了,整个过程就是如此的反复…… 这类优化方法主体就是讨论这些走路各个要素的方法。

  Nothing takes place in the world whose meaning is not that of some maximum or minimum. ---- L. Euler

  本科阶段时常用到,但是没系统学过。这是研究生阶段的课程,涉及到泛函等等,好难啃。但是这类问题也有很简单的例子。

  这类问题在我们的控制领域经常遇到。不过为了让小白也可以理解这个问题,我们就不讨论控制领域的问题了,而是以简单的几何问题举例。

  给你100m长的栏杆,让你在广阔的草原上圈地。被栏杆圈起来的闭合区域将属于你,用于放牧。请问如何圈才能获得最大的放牧面积。

  ,这里的约束即为栏杆的长度是固定的,只有100m。如果没有这个约束,则我们的栏杆可以任意长,则只要增大栏杆长度便可以增加圈地面积,优化就没有必要了。

  任何最优化问题,都要有个目标,就是你要最优化什么东西。这个目标要非常准确地表述出来,称为

  。这里,目标函数为所圈的区域的面积。同时,我们期望的极值是极大值,而不是极小指。

  现在,解决上面的问题,就是一个简单的最优化问题了。我们需要制定一个圈地的方案,作为

  在一定约束下(栏杆长度100m),求解输入(围栏设计方案),以使得目标函数(区域面积)取得期望极值(极大值)的的问题。

  题目简单,给出答案,方案为以100m为周长的圆即可。证明略。此时,这种方案是最优的。

365官网
CopyRight 365官网 ALL Rights Reserved