CPSC 536H - Empirical Algorithmics (Spring 2016)
Latest news (16/01/08):
- As announced in class, the reading assignment and reading questions have been posted
on Piazza at
https://piazza.com/ubc.ca/winterterm22015/cpsc536h/home.
From here on, all announcements will be posted there. If you have not enrolled yet,
please do so ASAP. (If you have any difficulties, contact help@cs.ubc.ca.)
Classes:
Tue+Thu,9:30-11:00
in DMP 101
First class: Tue, 2016/01/05
Instructor:
Holger H. Hoos
E-mail: hoos "at" cs.ubc.ca
Office: ICICS/CS complex, Room X541
What this course is about and why you might want to take it:
In a nutshell, it is about principled empirical methods for studying the performance
and behaviour of algorithms that cannot be analysed using techniques from computational theory, and for building algorithms that perform well
in practically interesting situations.
These empirical methods are
firmly grounded in established techniques
from statistics, optimisation and machine learning,
and they are being used increasingly widely and with great success in many areas of computing science and its
applications.
In particular, they play an increasingly prominent role in the development of state-of-the-art algorithms
for solving a wide range of so-called NP-hard problems, which arise in many
areas of computing science and its applications, including artificial intelligence (notably machine learning),
hardware design, software engineering, electronic commerce, manufacturing, genome sequencing and molecular structure prediction.
So ... you want to conduct proper computational experiments for your thesis, for a paper or for a real-world application? You want to leverage computational power
to build automatically better algorithms? You want to improve the state of the art
in solving a difficult computational problem? Then this course if for you.
Furthermore, if you are interested in pursuing your MSc or PhD project under my supervision, you should take this course.
I currently have openings for 1-2 new graduate students and will preferentially
consider students who have taken and and shown outstanding performance in this course.
Course objectives:
- To understand basic issues related to Computer Science as an empirical science.
- To be capable of using the scientific method for the empirical analysis of algorithms.
- To be capable of explaining and applying basic and advanced empirical methods
for the design and analysis
of algorithms (with an emphasis on high-performance heuristic algorithms
that are inaccessible to analytical methods).
- To be capable of critically assessing empirical methods for the analysis and
design of algorithms and their use as found in the research literature.
Prerequisite knowledge:
Algorithms, basic knowledge of statistics, high proficiency in programming.
Students from outside computer science are welcome to take the course,
if they have the prerequisite knowledge.
Topics covered in this course include:
- goals and challenges of empirical analysis of algorithms
- design of computational experiments
- benchmark selection
- statistical analysis and significance tests
- decision and optimisation problems
- deterministic and randomized algorithms (with and without error)
- analysis and performance optimisation of machine learning algorithms
- run-time vs solution quality / error trade-off
- scaling and robustness analysis
- parallelisation and restart techniques
- algorithm portfolios and ensemble techniques
- automated algorithm configuration and parameter tuning
- automated algorithm selection
- self-tuning mechanisms
Preliminary course outline
- Introduction
- Module 1: General considerations for empirical analysis
- Module 2: Deterministic Decision Procedures
- Module 3: Randomised Decision Procedures
- Module 4: Decision Procedures with Error
- Module 5: Optimisation Procedures
- Module 6: General considerations for empirical design methods
- Module 7: Automated Parameter Tuning and Algorithm Configuration
- Module 8: Restart Strategies and Multiple Independent Runs
- Module 9: Automated Algorithm Selection
- Module 10: Algorithm Portfolios
Note:
The course will be based on my forthcoming book "Empirical Algorithmics"
(Cambridge University Press, in preparation); students enrolled in this
course will get access to the latest draft and have a chance to earn
an acknowledgement in the printed version.
The course will consist of three components: (1) pre-class reading assignments
and exercises intended for initial familiarisation with key concepts and techniques;
(2) in-class presentations, discussions and exercises, designed to reinforce and
expand knowledge and skills; and (3) a sizeable course project.
Discussion of advanced topics will be based in part on primary research literature
selected based on the interests of the participants.
Course projects can be related to the student's research interests / thesis topic
and are determined in consultation with the instructor.
More information will be given in the first class (see above), and students interested
in taking the course are highly encouraged to attend this class.
If you have any questions regarding the course, please contact
Holger (hoos@cs.ubc.ca).
Last update: 16/01/03 [hh]