求流模型下带比率的集函数最大值问题求解研究.pdf

第 卷哈尔滨师范大学自然科学学报，第 期 求流模型下带比率的集函数最大值问题求解研究耿红梅（扬州工业职业技术学院）【摘 要】为了从数据流中抽取满足某些条件的子集，使得其目标函数的值尽可能的大，提高多项式更新时间，研究了从大规模数据集（称为基集）中选择一个子集 来表示整个数据集的问题通过提前设置阀值改进原有算法的系数，分别设计了更新近似最优值候选集的算法、已知最大单例值的算法和已知最优值的算法，在流模型下求解单调非次模集函数的函数最大值及其近似比结果表明，改进了 种利用递减收益率的算法在理论上得到了更好的近似比【关键词】流模型；近似算法；基数约束；集函数【中图分类号】【文献标识码】【文章编号】（）收稿日期：基金项目：国家自然科学基金项目（）引言近几十年来，数据以流模型的方式传输的情况受到了大量的关注在提取海量数据信息的过程中，出现了受基数约束的非次模集函数最大化问题然而，事实上，对于非次模函数的最大值，要想求解其精确值是非常困难的，很难在多项式时间内得到它的精确解但是这些非次模优化问题的广泛应用又使其求解成为必须因此，往往通过牺牲精度来换取时间，即在多项式时间内得到问题的一个近似解，这便是近似算法在流模型下，如果收益函数是次模函数，则称该模型为流次模函数最大化问题对于流次模优化的问题，引入衡量其算法性能的 个指标，分别为：（）数据流被读取（访问）的次数；（）空间复杂性，指存储数据的规模；（）运行时间，一般指计函数值的调用（查询）次数；（）近似比，指流结束时算法输出解的值与当前流下最优值的比 与传统离线模型的近似算法相比，流算法更加注重存储空间的有效性，学者们提出许多适用于流模型次模最大化问题的算法，比如基数约束流次模最大化问题、背包约束流次模最大化问题、独立系统约束的流次模最大化问题、带滑动窗口的次模最大化问题和在线次模最大化问题等 对于大规模流数据的次模优化问题，由于之前的次模优化算法需要反复访问完整的数据集，人们不能将它们直接应用于海量流数据，因此 团队在 ：一文中提出了一种求解在基数约束下的次模极大化问题的有效方法在大规模机器学习应用中，除了流算法，还有其他一些关于次模集函数最大化的算法，包括在线算法、随机贪婪算法、分散式演算法等该文主要通过构造一个满足流模型下条件的带比率集函数，改进之前已有的算法，并进行分析和证明，以获得相应的近似比，更快速更精确地解决在提取海量流数据信息的过程中出现的受基数约束的哈尔滨师范大学自然科学学报 年 第 卷非次模集函数最大化问题 相关理论概述 问题提出该文研究了从大规模数据集（称为基集）中选择一个子集 来表示整个数据集的问题这个问题可以表示为在具有基数约束的子集 上最大化一个非负单调集函数：，即（），其中 ，为非次模函数，其定义为：，对于任意 ，有（）（），即 ，（）（）基本定义定义 （多项式时间算法）称一个算法是多项式时间可解的，如果该算法对于问题输入占有空间大小为 的时间复杂度为（），其中 是一个非负整数定义 （类）所有可以用确定型图灵机在多项式时间内求解的判定问题定义 （类）所有可以用非确定型图灵机在多项式时间内接受的判定问题实例定义 （近似比）一个 近似算法 定义如下：对于实例，可以证明算法 的近似解（）的值不会比最优值 的 倍更多（或更少，这取决于具体问题）（），如果 （），如果 ，系数 称为算法 的近似比定义（次模函数）如果对于任意子集，有（）（）（）（），则称集合函数 是次模函数定义（边际增益）对于任意 和，（，）（）（）（）表示数据 加到集合 中产生的边际增益定义（单调性）如果对于任意 ，都有（）（），则称集合函数 单调不减定义（归一化）如果（），则称集合函数 是归一化的定义（次模最大化）一般来说，次模函数的最大化问题可以定义为：（）（）其中集合函数：在具有基数约束的子集 上，即 定义（非次模）非次模集函数 的定义：对于任意 ，有（）（）即：，（）（）算法设计该文改进了在流模型下满足基数约束的求解非次模函数最大化问题的 种算法算法的主要思想是提前设置一个阈值，这些算法的结果从一个空集开始，即，如果新元素同时满足阈值条件和基数约束，就将其添加到解集 中已知最优值的算法在经典的次模极大化贪婪算法中，会在每次迭代中选择具有高边际值的元素，但是在流模型中决定当前元素是否具有足够的边际增益是一个挑战一般的想法是以某种方式将其与最优值 进行比较如果能够知道所有的数据信息，就可以利用二分法找到最优值但在流模型中，要找到最优值并不容易，因此，在该文中假设了为式（）的最佳值此外，还需要设置一个直观的值来模拟满足 的最优值，其中 ，将递减收益率 与 相结合，改进了之前已有算法的系数，重新构造一个特定的阈值 （）来计算新的来源元素算法 给定一个基集，令 ，整数 ，一个集合函数，的递减收益率为 ，参数，实数，令 ，步骤 如 果（）（）（），则将 加入到解集 当中，其中 ，设 步骤 如果 ，输出；否则，令 ，再回到步骤 传递次数、存储元素的内存和每个元素的更第 期求流模型下带比率的集函数最大值问题求解研究新时间（读取新元素时的 调用次数）可以通过以下引理来估计引理 只扫描一次数据流，存储最多 个元素，每个元素有（）更新时间为了分析算法的性能保证，提出以下技术引理来判断子集 在每一个循环中的平均质量水平引理 在子集为 的算法的每一个循环中，有（）（）（）证明 可以通过数学归纳法来证明式（）首先，通过归一化集函数的定义，对于 ，得到了式（）其次，假设（）对于集合 是成立的假设算法将 加入到 中，由算法中的步骤，可以得到（）（）（）（）（），综上，得到了（）（）（）根据引理，可以得到以下定理：定理对于任意给定的实数，和具有递减收益率 ，的非次模函数，算法产生一个集合，使得 ，且（），其中 是式（）的最优值证明 考虑以下关于约束算法输出的解集 的基数的 种情况第 种情况：当 时，由引理，得到（）（）第种情况：当 时，设，为式（）的最优解于是有（）假设集合，中的元素按照算法的顺序依次到达为不失一般性假设 ，当算法中考虑时，对于每一个，注意对于每一个 ，不会加到 中结合算法的步骤 和引理，得到（）（）（）（）通过递减收益率的定义，结合（）和 的选择，因为 是单调不减的集合函数，所以有（）（），因 此，（）（）（）（）（），即（）由于 ，结合上述 种情况，可以得到（）已知最大单例值的算法算法给定（，），基集，令 ，整数，具有递减收益率（，）的集合函数 设：（），：（）（），：对于每个，设：步骤对于每个，如果（）（）（），则将元素 加入到解集中其中 ，步骤 如果 ，输出 （）和 ；否则，令 ，再回到步骤 引理 算法扫描数据流两次，最多存储（）个元素，每个元素的更新时间为（）下面的引理表明最优值候选集包含一个接近真正最优值的值引理 存在一个值 ，使得（）证明 使用与定理 证明中相同的符号 和（，），由 和 的定义，结合 的单调性，有 ，令 ，（），有 （）和 （），由引理得到的 的范围，结合定理 的理论分析，可以得到定理 定理 算法对于任意 ，输出解集，使得 ，且有（）哈尔滨师范大学自然科学学报 年 第 卷（）证明 同样考虑两种情况第 种情况，当 ，由引理 得（）（）（）第 种 情 况，当 ，有（）有以下不等式：对于任意 ，有（）结合上述两种情况，可以得到：对于任意 ，有（）（），（）更新近似最优值候选集的算法算法 给定一个基集，令 ，整数，一个带有递减收率，的集合函数，设：，：，：，：（）对于每一个 ，设：步骤 更新：，（），设：（）（）（），对于每一个 ，如果（）（）（），（）其中 ，则设 ，删除所有，使 步骤 如果 ，输出 （）和 ，否则，设 ，再回到步骤 引理 算法只扫描一次数据流，最多存储（）个 元 素，每 个 元 素 有（）更新时间对于任意 ，设（），为最小的指数使得 （）因为最初时 ，（），所以式（）可以归结为（）（）（）下面的引理 表明了阈值在（）之前不满足因此，可以假设从一开始就检查每一个 引理对于任意 ，当 ，（）时，有（）（）证明 使用反证法，假设存在 ，（），使得（）（）对于每一个，设 为每一次迭代中元素的最大单例值可得（）（）（），又因为 （），所以有 （），结合 的定义，发现当（）为最小的指数时 和 （）是相互矛盾的，因此完成了引理的证明引理 对于任意 （，），算法产生了满足（）（）的解集，其中是 的递减收益率证明 由引理 可知，存在一个值 满足（）从引理 可知，假设从一开始就检查每一个，现在考虑 的质量类似于定理 的证明，有（）（），由于 ，（），所以对于任意的 ，必然存在（）（）由已经证明的（）（），可以得到：对于任意，有（）（）（）完成了引理 的证明结论该文研究了流模型下受基数约束的非次模集函数的最大化问题，主要改进了三种利用递减收益率的算法算法 只扫描一次数据流存储元素的内存为，每个元素的更新时间为（），近似比为 ，其中，为参数，为集合函数的递减收益率算法 要求知道最优值，但实际上这通常是不可能的，而算法 构造第 期求流模型下带比率的集函数最大值问题求解研究了一组数字，其中至少有一个数字接近最优值为此，算法 必须扫描数据流两次 并 存 储（）个元素 算法 的近似比为（），每 个 元 素 的 更 新 时 间 为（）在算法 中，当每次扫描数据流中的新元素时，就会更新近似最优值的候选集因此，它只需要扫描一次数据流就可以保持相同的近似比率、储存元素的内存以及算法 中每个元素的更新时间其实，除了利用递减收益率，还有一些其他方法也可以用来研究非次模函数，比如次模比和曲率现有工作中关于次模最大化的研究有很多，但是对于非次模最大化的问题有待更加深入的研究和探讨参 考 文 献 郝自军，何尚录最大化非减次模集函数问题的近似算法及其性能保证西南民族大学学报：自然科学版，（）：邓素娟基于次模函数极小化的最优化问题内江师范学院学报，（）：王义晶 近似次模函数优化问题的算法研究北京工业大学，：，：连月芳，张真宁，赵中睿，等带基数约束的次模超模（）函数最大化问题的流算法运筹学学报，（）：王浩，刘沁玲，李伟东带背包约束的基数公平分配问题云南大学学报：自然科学版，（）：杨瑞琪，徐大川，杜东雷，等次模函数最大化的流算法综述运筹学学报，（）：冉颖丽 若干覆盖问题的近似算法设计与分析新疆大学，徐楚楚 两阶段次模最大化问题的近似算法研究南京师范大学，（）：（）：，（），：；（责任编辑：于达）