论文标题
哈里斯：算法选择的混合排名和回归森林
HARRIS: Hybrid Ranking and Regression Forests for Algorithm Selection
论文作者
论文摘要
众所周知，在算法问题的实例上，不同的算法的性能有所不同，激发了算法选择（AS）：给定算法问题的实例，哪种算法是最合适的算法？因此，AS问题引起了相当大的关注，导致了各种方法 - 其中许多方法要么解决回归或引擎盖下的排名问题。尽管这两种配方都产生了非常自然的解决方法，但它们具有相当大的弱点。一方面，正确预测在实例上算法的性能是足够的，但不是必需的条件，可以在算法上产生正确的排名，尤其是首先将最佳算法排名。另一方面，经典排名方法通常不会说明培训数据中可用的具体性能值，而仅考虑从此类数据组成的杠杆排名。我们提出了Harris -Hybrid排名和回归森林 - 一种利用特殊森林的新算法选择器，结合了两种方法的优势，同时减轻了它们的弱点。哈里斯的决定基于森林模型，其树是根据对混合排名和回归损失函数进行优化的拆分创建的。正如我们对阿斯利布（Aslib）的初步实验研究所表明的那样，哈里斯（Harris）在某些情况下对标准算法选择方法的改进，表明将树木的排名和回归结合在一起确实是有希望的。
It is well known that different algorithms perform differently well on an instance of an algorithmic problem, motivating algorithm selection (AS): Given an instance of an algorithmic problem, which is the most suitable algorithm to solve it? As such, the AS problem has received considerable attention resulting in various approaches - many of which either solve a regression or ranking problem under the hood. Although both of these formulations yield very natural ways to tackle AS, they have considerable weaknesses. On the one hand, correctly predicting the performance of an algorithm on an instance is a sufficient, but not a necessary condition to produce a correct ranking over algorithms and in particular ranking the best algorithm first. On the other hand, classical ranking approaches often do not account for concrete performance values available in the training data, but only leverage rankings composed from such data. We propose HARRIS- Hybrid rAnking and RegRessIon foreSts - a new algorithm selector leveraging special forests, combining the strengths of both approaches while alleviating their weaknesses. HARRIS' decisions are based on a forest model, whose trees are created based on splits optimized on a hybrid ranking and regression loss function. As our preliminary experimental study on ASLib shows, HARRIS improves over standard algorithm selection approaches on some scenarios showing that combining ranking and regression in trees is indeed promising for AS.
