A Preliminary Evaluation of Machine Learning in Algorithm Selection for Search Problems

Machine learning is an established method of selecting algorithms to solve hard search problems. Despite this, to date no systematic comparison and evaluation of the different techniques has been performed and the performance of existing systems has not been critically compared to other approaches. We compare machine learning techniques for algorithm selection on real-world data sets of hard search problems. In addition to well-established approaches, for the first time we also apply statistical relational learning to this problem. We demonstrate that most machine learning techniques and existing systems perform less well than one might expect. To guide practitioners, we close by giving clear recommendations as to which machine learning techniques are likely to perform well based on our experiments.

• Publication year

  2011

• Venue

  Symposium on Combinatorial Search

• Publication date

  2011-07-05

• Fields of study

  Computer Science

• Identifiers
  DOI 10.1609/socs.v2i1.18184
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Learning When to Use Lazy Learning in Constraint Solving

  2010influential reference
• Ensemble Classification for Constraint Solver Configuration

  2010cited by this paper
• A Portfolio Approach to Algorithm Selection

  2009cited by this paper
• Cross-disciplinary perspectives on meta-learning for algorithm selection

  2009cited by this paper
• A self-adaptive multi-engine solver for quantified Boolean formulas

  2009influential reference
• The WEKA data mining software: an update

  2009influential reference
• Using Case-based Reasoning in an Algorithm Portfolio for Constraint Solving ?

  2008cited by this paper
• SATzilla: Portfolio-based Algorithm Selection for SAT

  2008influential reference
• New Techniques for Algorithm Portfolio Design

  2008cited by this paper
• Introduction to Statistical Relational Learning

  2007cited by this paper
• Training linear SVMs in linear time

  2006influential reference
• Learning Techniques for Automatic Algorithm Portfolio Selection

  2004cited by this paper
• A portfolio approach to algorithm select

  2003cited by this paper
• Hyper-Heuristics: An Emerging Direction in Modern Search Technology

  2003cited by this paper
• Algorithm portfolios

  2001cited by this paper
• Algorithm Selection using Reinforcement Learning

  2000cited by this paper
• Branch and Bound Algorithm Selection by Performance Prediction

  1998cited by this paper
• How to Solve It Automatically: Selection Among Problem Solving Methods

  1998cited by this paper
• No free lunch theorems for optimization

  1997cited by this paper
• PYTHIA

  1996cited by this paper
• Adaptive Constraint Satisfaction: The Quickest First Principle

  1996cited by this paper
• A Study of Cross-Validation and Bootstrap for Accuracy Estimation and Model Selection

  1995cited by this paper
• PRODIGY: an integrated architecture for planning and learning

  1991cited by this paper
• Inside Case-Based Reasoning

  1989cited by this paper
• An algorithm for the selection problem

  1986influential reference

• Improving the quality evaluation process of machine learning algorithms applied to landslide time series analysis

  2024cites this paper
• POCASUM: policy categorizer and summarizer based on text mining and machine learning

  2021cites this paper
• A Novel Framework for Recommending Data Mining Algorithm in Dynamic IoT Environment

  2020cites this paper
• Siamese Algorithm Selection: A Novel Approach to Automated Algorithm Selection

  2020cites this paper
• Best practices for artificial intelligence in life sciences research.

  2020cites this paper
• Using Item Response Theory for Explainable Machine Learning in Predicting Mortality in the Intensive Care Unit: Case-Based Approach

  2020cites this paper
• An Efficient Botnet Detection Methodology using Hyper-parameter Optimization Trough Grid-Search Techniques

  2019cites this paper
• BestSF

  2018cites this paper
• Comparison of Machine Learning Algorithms to Build a Model for Predicting Defects in Sheet Metal Forming Processes

  2018cites this paper
• I Read but Don't Agree: Privacy Policy Benchmarking using Machine Learning and the EU GDPR

  2018cites this paper
• Model Prediction of Defects in Sheet Metal Forming Processes

  2018cites this paper
• Personalized thermal comfort modeling based on Support Vector Classification

  2017cites this paper
• Estimating Dynamics of Honeybee Population Densities with Machine Learning Algorithms

  2017cites this paper
• Assessment of an Adaptive Load Forecasting Methodology in a Smart Grid Demonstration Project

  2017cites this paper
• Exploiting machine learning for combinatorial problem solving and optimisation

  2016cites this paper
• Support vector machine based classification of seafloor rock types measured underwater using Laser Induced Breakdown Spectroscopy

  2016cites this paper
• Sparse Matrix Format Selection with Multiclass SVM for SpMV on GPU

  2016cites this paper
• Machine Learning Approach for the Predicting Performance of SpMV on GPU

  2016cites this paper
• Introduction to Combinatorial Optimisation in Numberjack

  2016cites this paper
• Algorithm selection for power flow management

  2016influential citation
• Explorer Automatically Selecting Inference Algorithms for Discrete Energy Minimisation

  2016cites this paper
• Abstractions and Strategies for Adaptive Programming

  2016cites this paper
• Automatically Selecting Inference Algorithms for Discrete Energy Minimisation

  2015cites this paper
• Privacy throughout the data cycle

  2015cites this paper
• Network State-Based Algorithm Selection for Power Flow Management Using Machine Learning

  2015cites this paper
• FAST: A Fast Stencil Autotuning Framework Based On An Optimal-solution Space Model

  2015cites this paper
• Datasets meta-feature description for recommending feature selection algorithm

  2015cites this paper
• The potential of network state-based algorithm selection to improve power flow management

  2014cites this paper
• Nitro: A Framework for Adaptive Code Variant Tuning

  2014cites this paper
• Search-Space Characterization for Real-time Heuristic Search

  2013cites this paper
• Towards making autotuning mainstream

  2013cites this paper
• Algorithm Selection for the Graph Coloring Problem

  2013cites this paper
• Personalized Medicine: Development of a Predictive Computational Model for Personalized Therapeutic Interventions

  2013cites this paper
• Hybrid Regression-Classification Models for Algorithm Selection

  2012cites this paper
• Quantifying Homogeneity of Instance Sets for Algorithm Configuration

  2012cites this paper
• A machine learning solution to assess privacy policy completeness: (short paper)

  2012cites this paper
• Algorithm Selection: From Meta-Learning to Hyper-Heuristics

  2012cites this paper
• Learning and Intelligent Optimization

  2012cites this paper