Distinguished Women in Mathematics Lecture Series: Smith-Miles -- Footprints in Instance Space: steps towards a free lunch

The Distinguished Women in Mathematics Lecture Series.  

Our series of talks by outstanding female mathematicians continues this Friday with an
expository talk by Professor Kate Smith-Miles.  The talk will be followed by afternoon
tea.  All are welcome, and the talk is designed to be accessible to students.  

Date/time: Friday, 27th of September, 3 PM 

Venue: New Law LT 024 

Speaker: Professor Kate Smith-Miles, School of Mathematical Sciences, Monash University 

Title: Footprints in Instance Space: steps towards a free lunch 

Abstract: The No-Free-Lunch Theorem tells us that, without prior knowledge of the
properties of an instance of a problem, we cannot expect any single algorithm to
outperform all others across all instances.  If an algorithm performs exceptionally well
on a certain class of instances, there will always be some other class of instances
where it is outperformed by another algorithm.  Understanding how the properties of an
instance affect algorithm performance is the key to being able to articulate the
strengths and weaknesses of an algorithm, and to anticipate when it is likely to be
better than others.  In this talk I will present a new methodology for achieving this
goal, and demonstrate its applicability to optimization, although it generalizes to
other problem domains.  The methodology involves: visualizing the set of all possible
instances based on features that correlate with difficulty; statistical generalization
of algorithm performance in this instance space, shown as a footprint where an
algorithm’s performance is deemed to be good; and then measuring the relative area of
the footprint of different algorithms.  The methodology is applied to provide insights
into optimization algorithm performance on the Travelling Salesman Problem and graph
colouring.  



Bio: Kate Smith-Miles is a Professor and Head of the School of Mathematical
Sciences at Monash University.  Prior to commencing this role in January 2009, she held
a Chair in Engineering at Deakin University (where she was Head of the School of
Engineering and Information Technology from 2006-2008) and a Chair in Information
Technology at Monash University, where she worked from 1996-2006.  Kate obtained a
B.Sc(Hons) in Mathematics and a Ph.D.  in Electrical Engineering, both from the
University of Melbourne, Australia.  She has published 2 books on neural networks and
data mining applications, and over 200 refereed journal and international conference
papers in the areas of neural networks, combinatorial optimization, intelligent systems
and data mining.  She has supervised to completion 20 PhD students, and has been awarded
over AUD$10 million in competitive grants, including 10 Australian Research Council
grants and industry awards.  From 2007-2008 she was Chair of the IEEE Technical
Committee on Data Mining (IEEE Computational Intelligence Society).  She was elected
Fellow of the Institute of Engineers Australia (FIEAust) in 2006, and Fellow of the
Australian Mathematical Society (FAustMS) in 2008.  She was awarded the Australian
Mathematical Society Medal in 2010 for distinguished research.  In addition to her
academic activities, she also regularly acts as a consultant to industry in the areas of
optimisation, data mining, and intelligent systems.