讲座题目：A Learning-based Approach to Algorithm Selection

主讲人: 郭海鹏博士

时   间: 2008. 03. 05, 15:00-16:00

地   点: E308A

摘   要: The algorithm selection problem aims at selecting the best algorithm for a given computational problem instance according to some characteristics of the instance. In this talk we will look at a machine learning-based inductive approach to solve the algorithm selection problem. Algorithm selection for sorting and the MPE (Most Probable Explanation) problem are used as cases studies. In sorting, instances with an existing order are easier for some algorithms. We have studied different presortedness measures, designed algorithms to generate permutations with a specified existing order uniformly at random, and applied various learning algorithms to induce sorting algorithm selection models from runtime experimental results. In the MPE problem, the instance characteristics we have studied include size and topological type of the network, network connectedness, skewness of the distributions in Conditional Probability Tables (CPTs), and the proportion and distribution of evidence variables. The MPE algorithms considered include an exact algorithm (clique-tree propagation), two stochastic sampling algorithms (MCMC Gibbs sampling and importance forward sampling), two search-based algorithms (multi-restart hill-climbing and tabu search), and one hybrid algorithm combining both sampling and search (ant colony optimization).