基于样本的优化(Optimization from Samples)

  • Zhijie Zhang ,
  • Xiaoming Sun ,
  • Jialin Zhang ,

大数据(Big Data Research) | , Vol 7(5): pp. 100-110

基于样本的优化研究的是如何通过用于学习目标函数的样本数据直接优化目标函数。首先介绍这一问题的数学模型——样本优化模型,以及这个模型下的不可近似性结果;然后介绍若干方法和样本优化模型的变种,以绕过这个模型下的不可近似性结果,使得优化成为可能;接着着重介绍其中一个变种——结构化样本优化模型,并详细阐述该模型下的最大覆盖问题和影响力最大化问题的优化算法;最后总结全文,并展望这一问题的未来研究方向。

Optimization from samples studies how one can optimize objective functions from the sample data that one uses to learn them. Firstly, the mathematical model of this problem-optimization from samples model, as well as the inapproximability results under this model, was introduced. Secondly, some approaches and variants of OPS were introduced, in order to circumvent the impossibility results and make optimization possible. Thirdly, one of the variants-the optimization from structured samples model was focused on, and the algorithms for maximum coverage and influence maximization problem under it were introduced in details. Finally, the paper was concluded, and some future research directions for the problem were proposed.