交互式次模集覆盖
本文研究自适应子模块覆盖问题,在最坏情况下进行研究。该问题推广了许多以前研究过的问题,对于固定成本下观察每个医学测试的结果的效用函数,我们目的是选择一组物品以实现 “目标值”,并在最小化实现代价(最大较差情况下成本)的同时逐步选择这些物品。同时研究了最坏情况下的最大覆盖问题。
Oct, 2022
本文提出自适应子模性的概念,将子模集函数推广到自适应策略,并使用自适应贪心算法解决具有不确定性结果的随机优化问题,通过使用懒惰评估方法显著加快了算法。通过提供子模目标的几个示例,包括传感器放置,病毒营销和主动学习,证明了自适应子模性的实用性。
Mar, 2010
本文研究两个新的优化问题 —— 在满足子模下限的约束条件下最小化子模函数(子模覆盖)和在满足子模上限的约束条件下最大化子模函数(子模背包)。我们将这些问题表述为约束优化问题,并获得许多有界逼近保证。此外,我们证明了这两个问题的紧密关联,并提供了一种解决一个问题的逼近算法用于获得另一个问题的逼近保证。最后,我们通过实验证明了本文算法的效果和良好的可扩展性。
Nov, 2013
我们在离线转导的半监督场景中考虑主动学习,通过替换图割(graph cut)为任意对称子模函数来泛化以前提出的主动学习的误差界。在对称化之后,可以使用任意非对称子模函数。不同的子模函数选择提供了适用于不同问题的误差限制的不同版本。此外,该限制是确定性的,并适用于对手所选择的标签。我们在任意子模函数中引入了一种相关的主动半监督学习方法,该方法可以近似最小化相应的误差限制。我们证明了误差界是紧致的,这意味着没有其他同形式的误差界比它更好。我们的理论结果得到了真实数据实验的支持。
Feb, 2012
本文提出了一种对标准主动学习模型进行延伸的模型,其中允许一种更一般类型的查询,即类条件查询。本文研究了这样的查询在两种已知噪声模型下的表现,给出了对于一般性不可知设置和有界噪声模型下的查询量的近乎严格的上下界,并表明我们的方法可以针对(未知的)噪声率进行自适应调整,而只有忽略不计的查询复杂度损失。
Nov, 2011
该文针对主动覆盖问题,借助支持向量估计器等算法在无标签数据集上提出了在少量标签查询即可完成标记所有阳性样本的主动学习方法,并证明该方法在图像数据集等基准测试中取得了相对优于离线方法和基线算法的效果。
Jun, 2021
贪婪算法的自适应子模块覆盖近似比率至少为 1.3 *(1 + ln Q),这篇论文否定了 Golovin-Krause 在 `` 自适应子模块性:主动学习和随机优化的新方法 '' 中宣称相同算法具有(1 + ln Q)^2 近似比率的先前结果。
May, 2024
提出了 SIMILAR (Submodular Information Measures based actIve LeARning)—— 利用最近提出的子模信息度量 (SIM) 作为获取函数的统一主动学习框架,既能在标准主动学习中工作,也可以轻松扩展到考虑上述实际情况,并作为可伸缩到大型实际数据集的主动学习一站式解决方案。
Jul, 2021