Skip to main content
Top

Hint

Swipe to navigate through the chapters of this book

Published in:
Cover of the book

2017 | OriginalPaper | Chapter

An Importance Sampling Approach to the Estimation of Algorithm Performance in Automated Algorithm Design

Authors : Steven Adriaensen, Filip Moons, Ann Nowé

Published in: Learning and Intelligent Optimization

Publisher: Springer International Publishing

share
SHARE

Abstract

In this paper we consider the problem of estimating the relative performance of a given set of related algorithms. The predominant, general approach of doing so involves executing each algorithm instance multiple times, and computing independent estimates based on the performance observations made for each of them. A single execution might be expensive, making this a time-consuming process. We show how an algorithm in general can be viewed as a distribution over executions; and its performance as the expectation of some measure of desirability of an execution, over this distribution. Subsequently, we describe how Importance Sampling can be used to generalize performance observations across algorithms with partially overlapping distributions, amortizing the cost of obtaining them. Finally, we implement the proposed approach as a Proof of Concept and validate it experimentally.
Footnotes
1
However, it is not a necessary one. It can be shown (proof in [1]) that the ability to compute only the relative likelihood \(\frac{Pr(e|c)}{Pr(e|c')}\) (\(\forall e \in E\) \(\forall c, c' \in C\)) suffices.
 
2
In a deterministic setting \(\varPsi (e) = 1\).
 
4
As this input may be a “random input generator” (e.g. \(\mathcal {D}\)) we in essence do not lose any generality here.
 
5
As WB-PURS does not support stochastic policies it was not be included as baseline.
 
Literature
2.
go back to reference Adriaensen, S., Nowé, A.: Towards a white box approach to automated algorithm design. In: International Joint Conference on Artificial Intelligence (IJCAI), pp. 554–560 (2016) Adriaensen, S., Nowé, A.: Towards a white box approach to automated algorithm design. In: International Joint Conference on Artificial Intelligence (IJCAI), pp. 554–560 (2016)
3.
4.
go back to reference Bhattacharyya, A.: On a measure of divergence between two multinomial populations. Sankhyā Indian J. Stat. 7, 401–406 (1946) MATHMathSciNet Bhattacharyya, A.: On a measure of divergence between two multinomial populations. Sankhyā Indian J. Stat. 7, 401–406 (1946) MATHMathSciNet
6.
go back to reference Denny, M.: Introduction to importance sampling in rare-event simulations. Eur. J. Phys. 22(4), 403 (2001) CrossRef Denny, M.: Introduction to importance sampling in rare-event simulations. Eur. J. Phys. 22(4), 403 (2001) CrossRef
7.
8.
go back to reference Hoos, H.H.: Programming by optimization. Commun. ACM 55(2), 70–80 (2012) CrossRef Hoos, H.H.: Programming by optimization. Commun. ACM 55(2), 70–80 (2012) CrossRef
9.
10.
go back to reference Hutter, F., Hoos, H.H., Leyton-Brown, K., Stützle, T.: ParamILS: an automatic algorithm configuration framework. J. Artif. Intell. Res. 36(1), 267–306 (2009) MATH Hutter, F., Hoos, H.H., Leyton-Brown, K., Stützle, T.: ParamILS: an automatic algorithm configuration framework. J. Artif. Intell. Res. 36(1), 267–306 (2009) MATH
11.
go back to reference Jones, D.R., Schonlau, M., Welch, W.J.: Efficient global optimization of expensive black-box functions. J. Glob. Optim. 13(4), 455–492 (1998) CrossRefMATHMathSciNet Jones, D.R., Schonlau, M., Welch, W.J.: Efficient global optimization of expensive black-box functions. J. Glob. Optim. 13(4), 455–492 (1998) CrossRefMATHMathSciNet
12.
go back to reference López-Ibánez, M., Dubois-Lacoste, J., Stützle, T., Birattari, M.: The irace package, iterated race for automatic algorithm configuration. Technical report, Universit Libre de Bruxelles (2011) López-Ibánez, M., Dubois-Lacoste, J., Stützle, T., Birattari, M.: The irace package, iterated race for automatic algorithm configuration. Technical report, Universit Libre de Bruxelles (2011)
13.
go back to reference Rasmussen, C.E.: Gaussian Processes for Machine Learning. MIT Press, Cambridge (2006) MATH Rasmussen, C.E.: Gaussian Processes for Machine Learning. MIT Press, Cambridge (2006) MATH
14.
go back to reference Rice, J.R.: The algorithm selection problem. Adv. Comput. 15, 65–118 (1976) CrossRef Rice, J.R.: The algorithm selection problem. Adv. Comput. 15, 65–118 (1976) CrossRef
Metadata
Title
An Importance Sampling Approach to the Estimation of Algorithm Performance in Automated Algorithm Design
Authors
Steven Adriaensen
Filip Moons
Ann Nowé
Copyright Year
2017
DOI
https://doi.org/10.1007/978-3-319-69404-7_1

Premium Partner