submodular function | BriefGPT

关键词submodular function

搜索结果 - 24

MM子模型多任务子集选择中的本地分布鲁棒性
在本研究中，我们通过引入基于本地分布鲁棒性的参考分布邻域，提出了一种多任务子模块优化问题的方法。我们首先建议引入一个正则化项，利用相对熵与标准多任务目标之间的关系。然后通过对偶性证明这个新的公式本身等同于最大化一个子模块函数，这可以通过标准
PDF3 months ago
SMART：指令调优的子模数据混合策略
SMART 是一种基于子模函数的数据混合策略，用于在有限的预算情况下改进指令调优，通过选择代表性子集中的任务来分配预算，以实现更好的性能。
PDF4 months ago
使用 Coreset 和归一化值预测学习编译器通行证顺序
本文提出了一种用于代码大小缩减的新型管道来寻找与程序相关的通行证序列，该管道通过贪婪优化次模函数识别 50 个通行证序列，并使用图神经网络 (GNN) 学习策略以预测核损毁的值，在 14 个数据集上，我们的管道比默认的 -Oz 标志表现得更
PDFa year ago
ICML基于单调性不稳定的麦特罗伊德上的非单调子模最大化
该研究探讨基于经典拟阵约束下的删除鲁棒版本的子模函数最大化问题，在此问题中，目标是提取一个小型数据集的摘要，即使在对手删除一些元素后也包含高价值独立集，该研究提供了具有常数因子逼近比的近似算法，其中空间复杂度取决于拟阵的秩 k 和已删除元素
PDF2 years ago
基于拟阵的删除鲁棒子模型最大化
本文研究在传统的拟阵约束下，单调子模函数的删除鲁棒版本的最大化问题，提出了空间复杂度依赖于拟阵的秩和删除元素数量的常数因子逼近算法，在中心化、流式环境下均获得了好的结果。
PDF2 years ago
决策、反事实解释与战略行为
本文旨在在战略环境下寻找最优的政策和对策解释，包括 NP 难的问题，非降性和子模性，用标准贪心算法获得近似保证。最后，我们表明通过将拟阵约束加入问题的制定中，我们可以提高对策解释的最优集合的多样性，并激励整个人口谱上的个体自我改进。
PDF4 years ago
子模量极大化的 FAST 算法
本篇论文介绍了一种新算法 FAST，旨在通过最大化满足劣模性的子模函数，使逼近比例任意接近 1-1 /e，由 O (log（n）log^2 (log k)) 次适应，总共使用 O（nloglog (k)) 次查询，在处理大数据集方面，该算法
PDF5 years ago
NIPS基于分区阈值算法的流式鲁棒次模最大化
本文研究在流式场景下，求解具有基数限制 k 的单调子模函数最大化问题，提出了一种基于 STAR-T 算法的新型分区结构和指数递减阈值规则，这种算法只需要一次遍历数据，即可保留简短而健壮的总结性概括，还证明了在删除汇总得到的任何 m 个元素后
PDF7 years ago
贪心是美德：通过贪心优化实现近似最优子模函数最大化
本文介绍了针对具有限制条件的子模函数进行最大化的两种算法 ——Repeated Greedy 和 Sample Greedy，并比较了这两种算法在电影推荐方面的表现。结果表明，Sample Greedy 在保证效用相同的情况下，性能至少比最
PDF7 years ago
约束子模最大化问题：超越 1/e
本研究提出了一种新的算法，用于在普遍限制条件下最大化非单调子模函数。该算法在下闭多面体上找到了一个函数的多线性扩展的近似分数解，其近似保证是 0.372，这是在 1/e 近似之上的首次改进，由连续贪心算法 [Feldman 等，FOCS20
PDF8 years ago
在背包约束下最大化有界曲率的单调次模函数
提出一种用于最大化满足背包限制下单调子模函数的算法，并且该算法的多项式时间复杂度为一个取决于输入函数曲率 c 的比率，该算法的近似度为 1-c/e-ε，这一近似度对于任何处于区间 [0,1] 中的 c 值均是紧确的。此外，该研究提供了用于预
PDF8 years ago
COLING面向查询的用户生成内容的观点摘要
本文介绍一个基于子模函数的查询聚焦意见摘要框架，其中，相关性排序由统计排名器产生，并且涵盖了涉及主题分布和多样视角的信息覆盖，同时利用离散函数来最小化冗余。本文是第一个为基于子模性的摘要方法评估不同文本相似性度量的方法。通过在社区 QA 和
PDF8 years ago
AAAI自适应采样的噪声子模型最大化及其在众包图像集摘要中的应用
提出了一种用于最大化未知子模函数的通用算法，该函数只能通过嘈杂的数据来访问，并利用探索模块建议好的元素以适应不同观察模型，解决覆盖率和多样性最大化的内容概括问题。
PDF9 years ago
多领域语音识别的数据选择性迁移学习
本论文提出一种通过有效选择训练语音数据来克服负迁移的新技术，该方法利用基于可能性比率的子模块函数为特定目标的相关言语数据进行选择。在广泛领域数据集上进行的实验表明，该技术可以找到相关数据并限制负迁移。使用这种数据选择技术，基于 PLP 特征
PDF9 years ago
从海量数据中发现有价值的物品
本文提出一种基于核函数、高斯过程预测和子模函数的算法 GP-Select，用于在考虑物品相似性和利用率的基础上从一个成本累计预算中选出最大价值的子集以及同时具有高效和多样性并将其应用于三个真实世界的案例，并在无需逼近的情况下，通过利用模型更
PDF9 years ago
子模函数最大化的流式算法
该研究主要针对单次流式处理的情况下，最大化一个非负子模集函数 f 编制一些确定性和随机算法，以实现对 p 匹配约束条件的大约 1 /p 的逼近，假设具有时间和资源约束。
PDF9 years ago
受限曲率下次模优化和超模优化的最优逼近
论文设计了一种新的逼近算法来解决在单一拟阵约束下优化子模和超模函数的问题，特别地，当目标函数有闭合总曲率时，获得了一个 (1-c/e)- 近似的结果；该算法基于连续贪心算法和非随机局部搜索的修改，并进行了扩展以包括在一些特定场景下的应用，例
PDF11 years ago
NIPS学习和最小化子模函数的曲率和最优算法
本文探究了三个相关且重要的机器学习问题。我们展示了这三个问题的复杂度都依赖于子模函数的 ' 曲率 '，并提供了改进旧有结果的上下界。我们证明了曲率对于子模函数的近似、最小化和学习有影响，并通过实验结果支持了我们的理论结论。
PDF11 years ago
NIPS带有子模块覆盖和子模块背包约束的子模块优化
本文研究两个新的优化问题 —— 在满足子模下限的约束条件下最小化子模函数（子模覆盖）和在满足子模上限的约束条件下最大化子模函数（子模背包）。我们将这些问题表述为约束优化问题，并获得许多有界逼近保证。此外，我们证明了这两个问题的紧密关联，并提
PDF11 years ago
最大和差异化，单调子模函数和动态更新
研究了一类问题，该问题的距离是一个度量，约束是一个 matroid 中的独立性，质量则由单调子模函数确定，多样性定义为 S 中物体之间的距离之和，提出了两种算法：基于基数约束的贪心算法和基于任意 matroid 约束的局部搜索算法，并证明了
PDF12 years ago