School of Computer Science, University of St Andrews, CS5011, 2022-2023
CS5011: A4 - Learning
Automated Algorithm Selection using Neural Networks
Assignment: A4 - Assignment 4
Deadline: 9th of May 2022
Weighting: 25% of module mark
Please note that MMS is the definitive source for deadline and credit details. You
are expected to have read and understood all the information in this specification
and any accompanying documents at least a week before the deadline. You must
contact the lecturer regarding any queries well in advance of the deadline.
1 Introduction
The Automated Algorithm Selection (AS) problem has been extensively studied for more than
a decade due to its wide range of applications across various domains. Given a portfolio of n
algorithms A = {a1, a2, ..., an}, an instance distribution DI where each instance i ∼ DI can
be described as a feature vector v(i), a cost metric c(i, ak) that measures the cost of solving
instance i using algorithm ak ∈ A, the AS problem involves building an automated selector
f(v(i)) that can select the best algorithm a ∈ A for an instance i. More formally, we want to
find f such that Ei∼DI [c(i, f(v(i))] is minimised. For a brief overview of the AS problem, see,
e.g., https://en.wikipedia.org/wiki/Algorithm_selection. Extensive literature reviews
on the topic can be found at [1, 2].
In this practical, you will tackle a simplified AS problem using artificial neural networks
(ANNs). You will try various ways to approach the problem and compare those approaches.
2 Practical Requirements
2.1 Part 1
In this part, you will model the AS problem as a regression task. The idea is to build an ANN
that can predict the cost of every algorithm in the portfolio based on instance features. Given
an instance, we will then choose the algorithm with the lowest predicted cost. Your task is to
construct an AS system using the described approach and analyse the results.
2.2 Part 2
In this part, you will model the AS problem as a multi-class classification task. The idea is to
build a classification model that can predict which algorithm is the best one for a given instance.
Basic: A basic multi-class classification approach is to represent each algorithm as an output
class and build an ANN for this classification task using the typical loss function.
Advanced: Our true aim is not about optimising classification accuracy, but rather about
optimising the average cost metric across the given instance set. Therefore, a more advanced
approach should take into account the true objective that we want to optimise. The idea is as
follows. Given an instance i, we denote the predicted and the truly best algorithms for i as
aˆ and a, respectively. We can then quantify the “regret” of our prediction as c(aˆ, i) - c(a, i).
1
By incorporating such regret into the training process, we are potentially giving more accurate
information about the true performance metric that we want to optimise for. We will call this
approach cost-sensitive classification-based algorithm selection.
Your task is to construct AS systems using both approaches (basic and advanced) and
discuss the results. You should also compare and contrast the results with the ones obtained in
Part 1.
2.3 Part 3 (Extensions)
In this part, you will look into implementing two extensions for the practical. You must finish
Part 1 and Part 2 before attempting this part.
• Extension 1: another classification approach for solving AS problem is to construct a
binary classifier for every pair of algorithms, i.e., each classifier will tell us which algorithm
in the pair is the better choice for a given instance. The best predicted algorithm will then
be the one with the highest number of votes across all classifiers. We can also employ the
idea of incorporating “prediction regret” as described in Part 2 into our classifiers. This
AS approach is called cost-sensitive pairwise classification and has been shown to work
very well for several AS problems (see, e.g., [3, 4]). In this extension, you will implement
this approach and compare it with the ones in previous parts.
• Extension 2: neural networks are not the only option for modelling an AS system. In
fact, traditional AS systems often make use of “classical” machine learning methods,
such as tree-based models (for doing cost-sensitive pairwise classification, see, e.g., [3,
4]) or clustering-based approaches (see, e.g., [5]). In this extension, you will base your
prediction on Random Forest models. You should think about various ways to tackle the
AS problem with random forests, and compare your approaches with the ones based on
neural networks.
2.4 Notes on implementation and evaluation
You should consider the following points in your implementation and evaluation:
• For all parts, you should consider different design choices of your system. You should
clearly describe those choices and discuss the results thoroughly in your evaluation part.
• In your analysis, you should consider discussing the results based on different performance
measures (see the lectures and submission/evaluate.py for a description of those mea-
sures). Remember that the ultimate aim is to minimise the average cost metric on unseen
data, or minimise the SBS_VBS gap.
• You should make sure your code satisfies the requirements described in 3.
Data: training and test datasets are provided in the submission template (submission.zip)
(see data/train/ and data/test/). Each dataset includes two files:
• instance-features.txt: a text file containing instance features, each row is the feature
vector of an instance.
• performance-data.txt: a text file containing the cost values of all algorithms on all
instances. Each row corresponds to an instance (sorted in the same order as in
instance-features.txt), and each column corresponds to an algorithm in the portfolio.
2
The given datasets come from a dedicated library for Algorithm Selection called ASLib 1.
The chosen datasets are from the scenario CSP-MZN-2013. We already simplify the data
for you. For a description of the scenario and the full data in original format, see: https:
//github.com/coseal/aslib_data/tree/master/CSP-MZN-2013.
Libraries: for all parts, you are allowed to use the following Python libraries: numpy 2, py-
torch 3, any plotting libraries (e.g., matplotlib 4, seaborn 5), scipy 6 (for doing statistical
tests, if you wish), any libraries for hyper-parameter tuning (if needed, some example libraries
are optuna 7, SMAC 8). For extension 2 (part 3), you are allowed to use scikit-learn 9 as
an extra library for building random forest models.
3 Submission
Please use the provided submission template (submission.zip) for your submission. You should
replace the name submission with your student martriculation number and submit everything
as a single ZIP file. Make sure that your submission has the following components (you can
also include more things if relevant):
• requirements.txt: modify this file to include the Python libraries required by your
program (see the list of allowed libraries above).
• install.sh: a bash script for creating a Python virtual environment in your submission
folder, and installing all packages listed in requirements.txt into the environment.
• scripts/: all your Python scripts should be located in this folder.
• For each part, your code should provide at least the following two scripts:
– scripts/train.py: Train an AS system given a training set, and save the trained
model (together with any extra information required for the test phase) into a .pt file
(readable by pytorch). Remember: only save a trained model via state_dict(),
please do NOT save the whole model. 10
– scripts/evaluate.py: Load a trained AS model, evaluate it on a test set, and print
out statistics (see the provided template for a list of what to print).
• run.sh: a bash script for running your submission. Note that for part 3, you should add
the necessary commands using the same templates as the ones provided for part 1 and
part 2.
• report.pdf: your report in PDF format, following the structure and requirements pre-
sented in the additional document CS5011_A_Reports found on studres.
Important: you must make sure that your code can run properly on a school lab machine
using the provided bash scripts (install.sh and run.sh).
1https://github.com/coseal/aslib_data
2https://numpy.org/
3https://pytorch.org/
4https://matplotlib.org/
5https://seaborn.pydata.org/
6https://scipy.org/
7https://optuna.org/
8https://github.com/automl/SMAC3
9https://scikit-learn.org/
10see, e.g., https://pytorch.org/tutorials/beginner/saving_loading_models.html#what-is-a-state-
dict
3
4 Assessment Criteria
Marking will follow the guidelines given in the school student handbook. The following factors
will be considered:
• Achieved requirements and quality of the implementations provided.
• Quality of the report, including analysis and insights into the proposed solutions and
results.
Some guideline descriptors for this assignment are given below:
• For a mark up to 11: the submission implement Part 1 correctly, with well-structured
code, the results should be adequately analysed and reported.
• For a mark up to 13: the submission implement Part 1 and the basic approach of Part 2
correctly, with well-structured code, good analysis and a well-written report.
• For a mark up to 16: the submission fully implement Part 1 and Part 2, with excellent
code, analysis and report.
• For a mark of 17 and higher: the submission implement fully Part 1, Part 2 and the
extensions (Part 3), with excellent code, analysis and report.
5 Policies and Guidelines
Marking: See the standard mark descriptors in the School Student Handbook
https://info.cs.st-andrews.ac.uk/student-handbook/learning-teaching/feedback.html#
Mark_-Descriptors
Lateness Penalty: The standard penalty for late submission applies:
https://info.cs.st-andrews.ac.uk/student-handbook/learning-teaching/assessment.html#
latenesspenalties
Good Academic Practice: The University policy on Good Academic Practice applies:
https://www.st-andrews.ac.uk/students/rules/academicpractice/
Nguyen Dang, Lei Fang, Fahrurrozi Rahman, Mun See Chang
cs5011.staff@st-andrews.ac.uk
March 28, 2023
4
References
[1] Pascal Kerschke, Holger H Hoos, Frank Neumann, and Heike Trautmann. Automated algo-
rithm selection: Survey and perspectives. Evolutionary computation, 27(1):3–45, 2019.
[2] Lars Kotthoff. Algorithm selection for combinatorial search problems: A survey. Data
mining and constraint programming: Foundations of a cross-disciplinary approach, pages
149–190, 2016.
[3] Lin Xu, Frank Hutter, Jonathan Shen, Holger H Hoos, and Kevin Leyton-Brown.
Satzilla2012: Improved algorithm selection based on cost-sensitive classification models.
Proceedings of SAT Challenge, pages 57–58, 2012.
[4] Marius Lindauer, Holger H Hoos, Frank Hutter, and Torsten Schaub. Autofolio: An auto-
matically configured algorithm selector. Journal of Artificial Intelligence Research, 53:745–
778, 2015.
[5] Roberto Amadini, Maurizio Gabbrielli, and Jacopo Mauro. Sunny-cp: a sequential cp
portfolio solver. In Proceedings of the 30th Annual ACM Symposium on Applied Computing,
pages 1861–1867, 2015.
5

学霸联盟