论文标题
在创建合奏时处理背包问题的随机方法
A stochastic approach to handle knapsack problems in the creation of ensembles
论文作者
论文摘要
基于合奏的方法是非常流行的方法，可以通过汇总个人选民的意见来提高决定的准确性。共同点是最大化精度。但是，如果还将逐步成本分配给各个选民，则会发生自然限制。因此，我们调查在成员总成本附加限制下创建合奏。可以将此任务作为背包问题提出，其中能量是某些聚合规则形成的集合精度。但是，普遍应用的聚合规则导致了不可分割的能量函数，该功能将常见的解决方案工具（例如动态编程）淘汰。我们引入了一种新型的随机方法，将能量视为成员精度的关节概率函数。可以将这种类型的知识有效地纳入随机搜索过程中，因为我们拥有有关预期准确性的信息，或者是找到更准确的合奏的概率。对模式分类器和对象检测器创建的集合的实验分析证实了我们方法的效率。此外，与模拟退火等一般方法相比，我们提出了一种新型的随机搜索策略，该策略更适合能量。
Ensemble-based methods are highly popular approaches that increase the accuracy of a decision by aggregating the opinions of individual voters. The common point is to maximize accuracy; however, a natural limitation occurs if incremental costs are also assigned to the individual voters. Consequently, we investigate creating ensembles under an additional constraint on the total cost of the members. This task can be formulated as a knapsack problem, where the energy is the ensemble accuracy formed by some aggregation rules. However, the generally applied aggregation rules lead to a nonseparable energy function, which takes the common solution tools -- such as dynamic programming -- out of action. We introduce a novel stochastic approach that considers the energy as the joint probability function of the member accuracies. This type of knowledge can be efficiently incorporated in a stochastic search process as a stopping rule, since we have the information on the expected accuracy or, alternatively, the probability of finding more accurate ensembles. Experimental analyses of the created ensembles of pattern classifiers and object detectors confirm the efficiency of our approach. Moreover, we propose a novel stochastic search strategy that better fits the energy, compared with general approaches such as simulated annealing.
