基于样本的优化

2021-09-22 01:55:28张智杰孙晓明张家琳陈卫
大数据 2021年5期
关键词:定义优化模型

张智杰,孙晓明,张家琳,陈卫

1. 中国科学院计算技术研究所,北京 100086;2. 中国科学院大学,北京 100049;3. 微软亚洲研究院,北京 100080

1 引言

为了解决实际生活中遇到的统筹优化问题,人们通常要建立一个问题模型,并确定模型的参数和优化目标函数,然后设计算法进行求解。然而,在大数据时代,许多应用场景无法提供足够的信息来确定模型参数和目标函数。人们只能通过观察到的历史样本数据来获取模型的信息,并进行优化。在这类场景下,人们通常使用机器学习的方法进行处理:首先近似地学习一个替代的目标函数,然后优化这个替代的函数。尽管这个方法在实际应用中获得了巨大的成功,但是在很多实际问题中,这个方法缺乏理论上的保证。事实上,它可能存在如下两个问题:① 即使针对原函数的优化问题是可求解或者可近似求解的,但是针对替代函数的优化问题也可能是不可近似的,这是因为替代函数可能丢失了一些原函数所具有的良好性质(如次模性);② 即使替代函数是可近似的,而且从整体上看和原函数很接近,但是它的最优解相较于原函数的最优解也可能是一个很差的近似。这些担忧自然地引出了如下问题:人们是否真的能从一系列样本数据中求解目标函数的优化问题?

1.1 样本优化模型

为了回答基于样本的组合优化是否可能的问题,Balkanski E等人[1]定义了另一种计算模型——样本优化(optimization from samples,OPS)模型。

定义1(OPS模型)给定参数如果存在算法A(不一定是多项式时间的),给定参数并将样本集作为输入,其中,Si独立同分布于D,,算法A返回S∈M,并满足

登录APP查看全文

猜你喜欢
定义优化模型
一半模型
超限高层建筑结构设计与优化思考
房地产导刊(2022年5期)2022-06-01 06:20:14
民用建筑防烟排烟设计优化探讨
关于优化消防安全告知承诺的一些思考
一道优化题的几何解法
重尾非线性自回归模型自加权M-估计的渐近分布
3D打印中的模型分割与打包
成功的定义
山东青年(2016年1期)2016-02-28 14:25:25
修辞学的重大定义
当代修辞学(2014年3期)2014-01-21 02:30:44
山的定义
公务员文萃(2013年5期)2013-03-11 16:08:37