基于子模函数构建优化商空间链

Constructing optimized quotient space chain based on submodular function

通过商空间链,可得到特定目标求解的逼近方法,由此可完成处理复杂信息,发现隐含知识,揭示事物和事件的内在规律的任务.但随着数据环境的变化,商逼近近似求解开始遇到挑战,由此引发的关键问题就是怎样构建满足求解精度的商空间链,逼近过程中误差界是多少.结合子模函数优化理论来构建商空间链,并对商逼近过程的逼近精度问题展开研究,证明了商空间可保持目标函数的子模性,可利用简单的贪心策略构建最优商空间链,逼近过程中最大误差界≤[1-(1-1/e)-1].

Quotient space chain can be used to find an approximation method for a specific problem.It is efficient to reveal the inherent laws of hidden knowledge in dealing with complex problem.However,in this era of big data, quotient space based problem solving has confronted with some new challenges.One of the crucial issues is to construct quotient space chain which satisfies a given precision and to find out the error boundary during the approxi-mation process.In this paper,we first construct the quotient space chain based on submodular function optimization. And then we explore the error boundary during the approximation process.Finally,we prove that quotient space can holds the submodularity of target function,and the optimal quotient space chain can be obtained by using greedy strategy with error less than[1-（1-1/e）-1 ].