Predictive search distributions

ABSTRACT

Estimation of Distribution Algorithms (EDAs) are a popular approach to learn a probability distribution over the "good" solutions to a combinatorial optimization problem. Here we consider the case where there is a collection of such optimization problems with learned distributions, and where each problem can be characterized by some vector of features. Now we can define a machine learning problem to predict the distribution of good solutions q(s|x) for a new problem with features x, where s denotes a solution. This predictive distribution is then used to focus the search. We demonstrate the utility of our method on a compiler optimization task where the goal is to find a sequence of code transformations to make the code run fastest. Results on a set of 12 different benchmarks on two distinct architectures show that our approach consistently leads to significant improvements in performance.

REFERENCES

• 1: Rich Caruana, Multitask Learning, Machine Learning, v.28 n.1, p.41-75, July 1997 [doi>10.1023/A:1007379606734 ]
• 2: de Bonet, J., Isbell, C., & Viola, P. (1997). MIMIC: Finding Optima by Estimating Probability Densities. Advances in Neural Information Processing Systems (p. 424). The MIT Press.
• 3: Björn Franke , Michael O'Boyle , John Thomson , Grigori Fursin, Probabilistic source-level optimisation of embedded programs, Proceedings of the 2005 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems, June 15-17, 2005, Chicago, Illinois, USA
• 4: Mary W. Hall , Jennifer M. Anderson , Saman P. Amarasinghe , Brian R. Murphy , Shih-Wei Liao , Edouard Bugnion , Monica S. Lam, Maximizing Multiprocessor Performance with the SUIF Compiler, Computer, v.29 n.12, p.84-89, December 1996 [doi>10.1109/2.546613 ]
• 5: John D. Lafferty , Andrew McCallum , Fernando C. N. Pereira, Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data, Proceedings of the Eighteenth International Conference on Machine Learning, p.282-289, June 28-July 01, 2001
• 6: Pat Langley, Elements of machine learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1995
• 7: Pedro Larraanaga , Jose A. Lozano, Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation, Kluwer Academic Publishers, Norwell, MA, 2001
• 8: Lee, C. (1997). UTDSP benchmark suite. http://www.eecg.toronto.edu/~corinna/.
• 9: Pelikan, M., Goldberg, D. E., & Lobo, F. (1999). A survey of optimization by building and using probabilistic models (Technical Report IlliGAL-99018). Illinois Genetic Algorithms Laboratory.
• 10: Thrun, S., & O'Sullivan, J. (1996). Discovering structure in multiple learning tasks: The TC algorithm. Proc. 13th International Conference on Machine Learning (pp. 489--497). Morgan Kaufmann.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Distribution functions

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

General Terms:
Theory