Analysing differences between algorithm configurations through ablation

作者：Fawcett Chris^*; Hoos Holger H

来源：Journal of Heuristics, 2016, 22(4): 431-458.

DOI：10.1007/s10732-014-9275-9

• Ablation analysis
• Parameter importance
• Automated algorithm configuration
• Empirical analysis

Developers of high-performance algorithms for hard computational problems increasingly take advantage of automated parameter tuning and algorithm configuration tools, and consequently often create solvers with many parameters and vast configuration spaces. However, there has been very little work to help these algorithm developers answer questions about the high-quality configurations produced by these tools, specifically about which parameter changes contribute most to improved performance. In this work, we present an automated technique for answering such questions by performing ablation analysis between two algorithm configurations. We perform an extensive empirical analysis of our technique on five scenarios from propositional satisfiability, mixed-integer programming and AI planning, and show that in all of these scenarios more than 95 % of the performance gains between default configurations and optimised configurations obtained from automated configuration tools can be explained by modifying the values of a small number of parameters (1-4 in the scenarios we studied). We also investigate the use of our ablation analysis procedure for producing configurations that generalise well to previously-unseen problem domains, as well as for analysing the structure of the algorithm parameter response surface near and between high-performance configurations.

• 出版日期2016-8