UTCS Artificial Intelligence
courses
talks/events
demos
people
projects
publications
software/data
labs
areas
admin
Latent Class Models for Algorithm Portfolio Methods (2010)
Bryan Silverthorn
and
Risto Miikkulainen
Different solvers for computationally difficult problems such as satisfiability (SAT) perform best on different instances. Algorithm portfolios exploit this phenomenon by predicting solvers' performance on specific problem instances, then shifting computational resources to the solvers that appear best suited. This paper develops a new approach to the problem of making such performance predictions: natural generative models of solver behavior. Two are proposed, both following from an assumption that problem instances cluster into latent classes: a mixture of multinomial distributions, and a mixture of Dirichlet compound multinomial distributions. The latter model extends the former to capture burstiness, the tendency of solver outcomes to recur. These models are integrated into an algorithm portfolio architecture and used to run standard SAT solvers on competition benchmarks. This approach is found competitive with the most prominent existing portfolio, SATzilla, which relies on domain-specific, hand-selected problem features; the latent class models, in contrast, use minimal domain knowledge. Their success suggests that these models can lead to more powerful and more general algorithm portfolio methods.
View:
PDF
Citation:
In
Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence
2010.
Bibtex:
@InProceedings{silverthorn:aaai2010, title={Latent Class Models for Algorithm Portfolio Methods}, author={Bryan Silverthorn and Risto Miikkulainen}, booktitle={Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence}, url="http://www.cs.utexas.edu/users/ai-lab?silverthorn:aaai2010", year={2010} }
Presentation:
Slides (PDF)
People
Risto Miikkulainen
Faculty
risto [at] cs utexas edu
Bryan Silverthorn
Ph.D. Alumni
bsilvert [at] cs utexas edu
Projects
Borg: A General-Purpose Algorithm Portfolio System
2009 - 2013
Learning Strategic Behavior in Sequential Decision Tasks
2009 - 2014
Areas of Interest
Algorithm Portfolios
Learning for Planning and Problem Solving
Satisfiability
Unsupervised Learning, Clustering, and Self-Organization
Software/Data
Borg
The borg project
includes a practical algorithm...
2011
Demos
Model-Based Visualization of Solver Performance Data
Bryan Silverthorn
2011
Labs
Neural Networks