论文标题
最差的自适应下覆盖
Worst-Case Adaptive Submodular Cover
论文作者
论文摘要
在本文中，我们研究了最坏情况下的自适应下覆盖问题。这个问题概括了许多先前研究的问题，即基于池的主动学习和随机的下套装盖。我们问题的输入是一组项目（例如，医学测试），每个项目都有一个随机状态（例如，医学测试的结果），其实现最初是未知的。必须以固定成本选择一个项目才能观察其实现。有一个效用函数将项目及其状态的子集映射到非负实际数字。我们的目标是依次选择一组项目以实现``目标值''，同时最大程度地减少实现范围内的最高成本（又称最差的成本）。为了促进我们的研究，我们假设效用函数是\ emph {糟糕的case supodular}，这是在许多机器学习应用中常见的属性。有了这个假设，我们开发了一个紧密的$（\ log（q/η）+1）$ - 近似策略，其中$ q $是``目标value''，而$η$是$ q $和任何可实现的实用程序value $ \ hat {q} <q $之间的最小差异。我们还研究了最严重的最大覆盖范围问题，这是最低成本问题的双重问题，其目标是选择一组项目，以最大程度地利用其最坏情况下的效用，但要受到预算约束。为了解决此问题，我们开发了$（1-1/e）/2 $ - approximation解决方案。
In this paper, we study the adaptive submodular cover problem under the worst-case setting. This problem generalizes many previously studied problems, namely, the pool-based active learning and the stochastic submodular set cover. The input of our problem is a set of items (e.g., medical tests) and each item has a random state (e.g., the outcome of a medical test), whose realization is initially unknown. One must select an item at a fixed cost in order to observe its realization. There is an utility function which maps a subset of items and their states to a non-negative real number. We aim to sequentially select a group of items to achieve a ``target value'' while minimizing the maximum cost across realizations (a.k.a. worst-case cost). To facilitate our study, we assume that the utility function is \emph{worst-case submodular}, a property that is commonly found in many machine learning applications. With this assumption, we develop a tight $(\log (Q/η)+1)$-approximation policy, where $Q$ is the ``target value'' and $η$ is the smallest difference between $Q$ and any achievable utility value $\hat{Q}<Q$. We also study a worst-case maximum-coverage problem, a dual problem of the minimum-cost-cover problem, whose goal is to select a group of items to maximize its worst-case utility subject to a budget constraint. To solve this problem, we develop a $(1-1/e)/2$-approximation solution.
