Ablation Analysis

Developers of high-performance algorithms for hard computational problems are increasingly taking advantage of tools for automated parameter tuning and algorithm configuration, such as ParamILS and SMAC. Consequently, solvers are being designed with many parameters and vast configuration spaces.

However, these configuration tools sample many configurations, and developers are often left wondering why their algorithm parameters were set to specific values by the automated configuration process, or whether the modification of some parameters from their default settings was truly necessary to achieve substantially improved performance.

Given a highly parameteric algorithm, after making many parameter changes as a result of automated configuration, how can an algorithm developer know which of the parameter changes were actually important? The ability to answer questions like these allows developers to focus their efforts on the aspects of their solvers that are providing the most performance gains (or losses), in an iterative algorithm development process.

To make progress in answering such questions, we introduce the concept of Ablation Analysis, a procedure investigating the path of configurations obtained by iteratively modifying parameter settings from a source configuration (e.g., an expert-defined default) to those from a target configuration (e.g., one obtained from an automatic configurator).

Releases

Release package

ablationAnalysis-0.9.3.tar.gz

Changelog

  • Fixed occasional issue with the brute-force ablation mode with mean10 or mean100 overall objective.
  • Upgraded to the newest version of the AEATK library

Package contents

  • ablationAnalysis - A shell script to run the ablation analysis procedure
  • ablationValidation - A shell script to perform empirical analysis on an ablation path
  • ablationAnalysis.jar - The Java class files for the ablation analysis procedure
  • README.txt - Detailed demo instructions and further documentation
  • example_spear_small/ - Required files for a small demonstration scenario
  • conf/ - logging configuration
  • lib/ - dependencies

Release package

ablationAnalysis-0.9.2.tar.gz

Changelog

  • AEATK bug fix for conditional constraints on interval parameters
  • Upgraded to the newest version of the AEATK library
  • Some output has been made more aesthetically pleasing
  • Parameters becoming inactive in the target configuration are no longer considered to be flippable, as their state is completely determined by that of their parent parameters
  • Users can now limit the number of ablation rounds performed, with the 'maximumAblationRounds' option
  • The target configuration is now explicitly included when performing validation

Package contents

  • ablationAnalysis - A shell script to run the ablation analysis procedure
  • ablationValidation - A shell script to perform empirical analysis on an ablation path
  • ablationAnalysis.jar - The Java class files for the ablation analysis procedure
  • README.txt - Detailed demo instructions and further documentation
  • example_spear_small/ - Required files for a small demonstration scenario
  • conf/ - logging configuration
  • lib/ - dependencies

Release package

ablationAnalysis-0.9.1.tar.gz

Changelog

  • useRacing=false is now usable if you want to try the brute-force ablation approach.
  • Additional TargetAlgorithmEvaluator support on the execution backend.
  • Some readability changes to the README and example structure.

Package contents

  • ablationAnalysis - A shell script to run the ablation analysis procedure
  • ablationValidation - A shell script to perform empirical analysis on an ablation path
  • ablationAnalysis.jar - The Java class files for the ablation analysis procedure
  • README.txt - Detailed demo instructions and further documentation
  • example_spear_small/ - Required files for a small demonstration scenario
  • conf/ - logging configuration
  • lib/ - dependencies

Release package

ablationAnalysis-0.9.0.tar.gz

Package contents

  • ablationAnalysis - A shell script to run the ablation analysis procedure
  • ablationValidation - A shell script to perform empirical analysis on an ablation path
  • ablationAnalysis.jar - The Java class files for the ablation analysis procedure
  • README.txt - Detailed demo instructions and further documentation
  • example_spear_small/ - Required files for a small demonstration scenario
  • conf/ - logging configuration
  • lib/ - dependencies

Usage

We provide a trivial example scenario for testing ablation analysis on your system, located in the example_spear_small/ directory after unarchiving.

This scenario performs ablation analysis using the SPEAR theorem prover as a target algorithm, on a small set of easy quasi-group completion (QCP) problems. For more detailed instructions, please see the README.txt included in the distribution.

First, verify that the package was unarchived correctly:


$ ls
ablationAnalysis  ablationAnalysis.jar  ablationValidation  conf  example_spear_small  lib  README.txt
                

Next, run the ablation analysis procedure using the included scenario file:


$ ./ablationAnalysis --optionFile example_spear_small/ablation_spear_small.txt
                

This will produce various logs, contained in the (newly-created) log/ subdirectory:


$ ls log/
ablation-run1234.txt  ablation-validation-run1234.txt  log-err1234.txt  log-run1234.txt  log-warn1234.txt  racing-run1234.txt  runhashes-run1234.txt
                

The ablation path found is very human-readable, and is contained in log/ablation-run<seed>.txt

In order to analyse the performance of each configuration on the ablation path, potentially on a held-out test set, we copy the ablation path file and use the ablationValidation command:


$ cp log/ablation-run1234.txt ./ablationPath.txt
$ ./ablationValidation --optionFile example_spear_small/ablation_spear_small.txt --ablationLogFile ./ablationPath.txt --targetRunsPerInstance 1
                

The result of the analysis run should be visible on the console, and can also be found in log/ablation-validation-run<seed>.txt

From here, please experiment with your own target algorithms! Contact us if you have any problems getting your scenario working.

People

  • Chris Fawcett ( webpage | email ), University of British Columbia

  • Holger H. Hoos ( webpage | email ), University of British Columbia

Publications

  • [Fawcett and Hoos, 2016] Chris Fawcett and Holger H. Hoos. Analysing differences between algorithm configurations through ablation.
    Journal of Heuristics, Volume 22, Issue 4, pp 431-458, 2016.
  • [Fawcett and Hoos, 2013] Chris Fawcett and Holger H. Hoos. Analysing differences between algorithm configurations through ablation.
    Proceedings of the 10th Metaheuristics International Conference (MIC 2013), pp. 123-132, 2013.