|
|
摘要：基于样本的优化研究的是如何通过用于学习目标函数的样本数据直接优化目标函数。首先介绍这一问题的数学模型——样本优化模型，以及这个模型下的不可近似性结果；然后介绍若干方法和样本优化模型的变种，以绕过这个模型下的不可近似性结果，使得优化成为可能；接着着重介绍其中一个变种——结构化样本优化模型，并详细阐述该模型下的最大覆盖问题和影响力最大化问题的优化算法；最后总结全文，并展望这一问题的未来研究方向。
关键词：基于样本的优化 ; 数据驱动的优化 ; 结构化样本 ; 最大覆盖问题 ; 影响力最大化问题
基于样本的优化
张智杰1,2, 孙晓明1,2, 张家琳1,2, 陈卫3
1 中国科学院计算技术研究所，北京 100086
2 中国科学院大学，北京 100049
3 微软亚洲研究院，北京 100080
论文引用格式：
张智杰, 孙晓明, 张家琳, 等. 基于样本的优化[J]. 大数据, 2021, 7(5): 100-110.
ZHANG Z J, SUN X M, ZHANG J L, et al. Optimization from samples[J]. Big Data Research, 2021, 7(5): 100-110.
为了解决实际生活中遇到的统筹优化问题，人们通常要建立一个问题模型，并确定模型的参数和优化目标函数，然后设计算法进行求解。然而，在大数据时代，许多应用场景无法提供足够的信息来确定模型参数和目标函数。人们只能通过观察到的历史样本数据来获取模型的信息，并进行优化。在这类场景下，人们通常使用机器学习的方法进行处理：首先近似地学习一个替代的目标函数，然后优化这个替代的函数。尽管这个方法在实际应用中获得了巨大的成功，但是在很多实际问题中，这个方法缺乏理论上的保证。事实上，它可能存在如下两个问题：① 即使针对原函数的优化问题是可求解或者可近似求解的，但是针对替代函数的优化问题也可能是不可近似的，这是因为替代函数可能丢失了一些原函数所具有的良好性质（如次模性）；② 即使替代函数是可近似的，而且从整体上看和原函数很接近，但是它的最优解相较于原函数的最优解也可能是一个很差的近似。这些担忧自然地引出了如下问题：人们是否真的能从一系列样本数据中求解目标函数的优化问题？
论文详见：
作者简介：
张智杰（1995-），男，中国科学院计算技术研究所博士生，主要研究方向为次模优化、公平分配等。
孙晓明（1978-），男，中国科学院计算技术研究所研究员，主要研究方向为量子计算、算法复杂性、社会网络近似算法、通信复杂性、判定树复杂性、组合数学等。
张家琳（1983-），女，中国科学院计算技术研究所研究员，主要研究方向为理论计算机科学、量子计算、近似算法、在线算法、算法博弈论。
陈卫（1968-），男，博士，微软亚洲研究院高级研究员，中国科学院计算技术研究所客座研究员，中国计算机学会大数据专家委员会和理论计算机科学专业委员会委员，IEEEFellow，《大数据》期刊编委。主要研究方向为在线学习和优化、社交和信息网络、网络博奕论和经济学、分布式计算、容错等。
<hr/>欢迎关注（公众号） @运筹OR帷幄 ，了解更多运筹学、人工智能及相关学科的干货资讯。
知乎专栏：
『运筹OR帷幄』大数据时代的运筹学
『运筹AI帷幄』大数据时代的人工智能
获得最新运筹学及其相关学科的干货资料、行业前沿信息、学术动态、硕博offer信息等。特别适合你~
欢迎大家交流。
也欢迎大佬们投稿和商业合作，学术信息、会议通讯、征稿启事、硕博招生信息等免费推广。 |
|
窥视卡
雷达卡
发表于 2021-11-30 10:31
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
千斤顶
显身卡