Using Optimal Dependency-Trees for Combinatorial Optimization: Learning the Structure of the Search Space

July 1997

Using Optimal Dependency-Trees for Combinatorial Optimization: Learning the Structure of the Search Space

Authors:

Shumeet Baluja and Scott Davies
Conference Paper
Proceedings of (ICML) International Conference on Machine Learning

Abstract:

Many combinatorial optimization algorithms have no mechanism for capturing inter-parameter dependencies. However, modeling such dependencies may allow an algorithm to concentrate its sampling more effectively on regions of the search space which have appeared promising in the past. We present an algorithm which incrementally learns pairwise probability distributions from good solutions seen so far, uses these statistics to generate optimal (in terms of maximum likelihood) dependency trees to model these distributions, and then stochastically generates new candidate solutions from these trees. We test this algorithm on a variety of optimization problems. Our results indicate superior performance over other tested algorithms that either (1) do not explicitly use these dependencies, or (2) use these dependencies to generate a more restricted class of dependency graphs.
@conference{Baluja-1997-16482,
author = {Shumeet Baluja And Scott Davies},
title = {Using Optimal Dependency-Trees for Combinatorial Optimization: Learning the Structure of the Search Space},
booktitle = {Proceedings of (ICML) International Conference on Machine Learning},
year = {1997},
month = {July},
pages = {30 - 38},
}
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.