Active learning enables us to reduce the annotation cost by adaptively selecting unlabeled instances to be labeled. For pool-based active learning, several effective methods with theoretical guarantees have been developed through maximizing some utility function satisfying adaptive submodularity. In contrast, there have been few methods for stream-based active learning based on adaptive submodularity. In this paper, we propose a new class of utility functions, policy-adaptive submodular functions, and prove this class includes many existing adaptive submodular functions appearing in real world problems. We provide a general framework based on policy-adaptive submodularity that makes it possible to convert existing pool-based methods to stream-based methods and give theoretical guarantees on their performance. In addition we empirically demonstrate their effectiveness comparing with existing heuristics on common benchmark datasets.

Neural Information Processing Systems http://nips.cc/

Maximization of submodular functions has wide applications in machine learning and artificial intelligence. Adaptive submodular maximization has been traditionally studied under the assumption that the model of the world, the expected gain of choosing an item given previously selected items and their states, is known. In this paper, we study the scenario where the expected gain is initially unknown and it is learned by interacting repeatedly with the optimized function. We propose an efficient algorithm for solving our problem and prove that its expected cumulative regret increases logarithmically with time. Our regret bound captures the inherent property of submodular maximization, earlier mistakes are more costly than later ones. We refer to our approach as Optimistic Adaptive Submodular Maximization (OASM) because it trades off exploration and exploitation based on the optimism in the face of uncertainty principle. We evaluate our method on a preference elicitation problem and show that non-trivial K-step policies can be learned from just a few hundred interactions with the problem.

Pros: The presentation is mostly clear. The paper shows that one can apply the proposed streaming algorithm, without changing the commonly used objective functions used in pool-based active learning setting. Proofs are sound, and experimental results show that the proposed algorithms work reasonably well in comparison with the pool-based setting. Cons: The stream-based adaptive sensor placement application does not appear convincing to me. Is the condition range(\pi) \subseteq V \setminus B in Def 3.1 necessary? Policy-adaptive submodularity is used for providng a lower bound on the expected gain of a policy on a random sequence of data points (Lemma B.7).

Maximization of submodular functions has wide applications in machine learning and artificial intelligence. Adaptive submodular maximization has been traditionally studied under the assumption that the model of the world, the expected gain of choosing an item given previously selected items and their states, is known. In this paper, we study the setting where the expected gain is initially unknown, and it is learned by interacting repeatedly with the optimized function. We propose an efficient algorithm for solving our problem and prove that its expected cumulative regret increases logarithmically with time. Our regret bound captures the inherent property of submodular maximization, earlier mistakes are more costly than later ones. We refer to our approach as Optimistic Adaptive Submodular Maximization (OASM) because it trades off exploration and exploitation based on the optimism in the face of uncertainty principle. We evaluate our method on a preference elicitation problem and show that non-trivial K-step policies can be learned from just a few hundred interactions with the problem.

Active learning enables us to reduce the annotation cost by adaptively selecting unlabeled instances to be labeled. For pool-based active learning, several effective methods with theoretical guarantees have been developed through maximizing some utility function satisfying adaptive submodularity. In contrast, there have been few methods for stream-based active learning based on adaptive submodularity. In this paper, we propose a new class of utility functions, policy-adaptive submodular functions, which includes many existing adaptive submodular functions appearing in real world problems. We provide a general framework based on policy-adaptive submodularity that makes it possible to convert existing poolbased methods to stream-based methods and give theoretical guarantees on their performance. In addition we empirically demonstrate their effectiveness by comparing with existing heuristics on common benchmark datasets.

Many sequential decision making problems, including pool-based active learning and adaptive viral marketing, can be formulated as an adaptive submodular maximization problem. Most of existing studies on adaptive submodular optimization focus on either monotone case or non-monotone case. Specifically, if the utility function is monotone and adaptive submodular, \cite{golovin2011adaptive} developed a greedy policy that achieves a $(1-1/e)$ approximation ratio subject to a cardinality constraint. If the utility function is non-monotone and adaptive submodular, \cite{tang2021beyond} showed that a random greedy policy achieves a $1/e$ approximation ratio subject to a cardinality constraint. In this work, we aim to generalize the above mentioned results by studying the partial-monotone adaptive submodular maximization problem. To this end, we introduce the notation of adaptive monotonicity ratio $m\in[0,1]$ to measure the degree of monotonicity of a function. Our main result is to show that a random greedy policy achieves an approximation ratio of $m(1-1/e)+(1-m)(1/e)$ if the utility function is $m$-adaptive monotone and adaptive submodular. Notably this result recovers the aforementioned $(1-1/e)$ and $1/e$ approximation ratios when $m = 0$ and $m = 1$, respectively. We further extend our results to consider a knapsack constraint. We show that a sampling-based policy achieves an approximation ratio of $(m+1)/10$ if the utility function is $m$-adaptive monotone and adaptive submodular. One important implication of our results is that even for a non-monotone utility function, we still can achieve an approximation ratio close to $(1-1/e)$ if this function is ``close'' to a monotone function. This leads to improved performance bounds for many machine learning applications whose utility functions are almost adaptive monotone.

Many sequential decision making problems can be formulated as an adaptive submodular maximization problem. However, most of existing studies in this field focus on pool-based setting, where one can pick items in any order, and there have been few studies for the stream-based setting where items arrive in an arbitrary order and one must immediately decide whether to select an item or not upon its arrival. In this paper, we introduce a new class of utility functions, semi-policywise submodular functions. We develop a series of effective algorithms to maximize a semi-policywise submodular function under the stream-based setting.

Maximization of submodular functions has wide applications in machine learning and artificial intelligence. Adaptive submodular maximization has been traditionally studied under the assumption that the model of the world, the expected gain of choosing an item given previously selected items and their states, is known. In this paper, we study the scenario where the expected gain is initially unknown and it is learned by interacting repeatedly with the optimized function. We propose an efficient algorithm for solving our problem and prove that its expected cumulative regret increases logarithmically with time. Our regret bound captures the inherent property of submodular maximization, earlier mistakes are more costly than later ones.

Active learning enables us to reduce the annotation cost by adaptively selecting unlabeled instances to be labeled. For pool-based active learning, several effective methods with theoretical guarantees have been developed through maximizing some utility function satisfying adaptive submodularity. In contrast, there have been few methods for stream-based active learning based on adaptive submodularity. In this paper, we propose a new class of utility functions, policy-adaptive submodular functions, and prove this class includes many existing adaptive submodular functions appearing in real world problems. We provide a general framework based on policy-adaptive submodularity that makes it possible to convert existing pool-based methods to stream-based methods and give theoretical guarantees on their performance. In addition we empirically demonstrate their effectiveness comparing with existing heuristics on common benchmark datasets.