We consider the problem of selecting an optimal subset of information sources
for a hypothesis testing/classification task where the goal is to identify the
true state of the world from a finite set of hypotheses, based on finite
observation samples from the sources. In order to characterize the learning
performance, we propose a misclassification penalty framework, which enables
non-uniform treatment of different misclassification errors. In a centralized
Bayesian learning setting, we study two variants of the subset selection
problem: (i) selecting a minimum cost information set to ensure that the
maximum penalty of misclassifying the true hypothesis remains bounded and (ii)
selecting an optimal information set under a limited budget to minimize the
maximum penalty of misclassifying the true hypothesis. Under mild assumptions,
we prove that the objective (or constraints) of these combinatorial
optimization problems are weak (or approximate) submodular, and establish
high-probability performance guarantees for greedy algorithms. Further, we
propose an alternate metric for information set selection which is based on the
total penalty of misclassification. We prove that this metric is submodular and
establish near-optimal guarantees for the greedy algorithms for both the
information set selection problems. Finally, we present numerical simulations
to validate our theoretical results over several randomly generated instances.

选择最佳的信息源子集，以便在有限假设集合上，基于有限样本观察结果，从事实世界的真实状态中识别出正确的假设。使用误分类惩罚框架来描述学习性能，并研究了两种情况下的子集选择问题：（一）选择最小成本的信息集合以保证在将真实假设错误分类的最大惩罚保持有界的情况下；（二）在有限的预算下选择最佳信息集合以最小化将真实假设错误分类的最大惩罚。通过渐进性的贪心算法建立了近似优化性能保证。