DF22400
Machine Learning (3p)
Introduction and Application for Automated Performance Tuning

HT/2012

Recommended for
Graduate (CUGS, CIS, ...) students interested in the application of machine learning techniques to advanced system performance optimization, as in compiler construction, library generation, runtime systems, parallel computing, software engineering, system simulation and optimization.
Interested undergraduate students are also welcome, as long as there are free seats left.

Organization
Lectures (ca. 15h), optional theoretical exercises for self-assessment, student projects and/or presentations. Written exam.

The course was last given
This is a new course.

Goals
The course introduces fundamental techniques of machine learning and considers case studies for its application in automated system performance tuning, such as auto-tuning library generators, compilers, and runtime systems.

Prerequisites
Linear algebra. Discrete mathematics. Data structures and algorithms. Some basic knowledge of computer architecture is assumed. For the case study presentations, some background in at least one application area, such as compiler construction, library generation, signal processing software, runtime systems, or software composition, is required.

Contents
"[Machine] learning is the process of [automatically] constructing, from training data, a fast and/or compact surrogate function that heuristically solves a decision, prediction or classification problem for which only expensive or no algorithmic solutions are known. It automatically abstracts from sample data to a total decision function."
- [Danylenko et al., Comparing Machine Learning Approaches..., SC'2011, LNCS 6708]

Schedule
Lecture block (2.5 days, room Donald Knuth), presentation session (0.5 days, room Donald Knuth) and exam (0.5 days, room von Neumann) in Linköping.

• Monday 22 october 2012 13:15-17:00 (Lectures by Christoph Kessler)
• Tuesday 23 october 2012 09:15-16:00 (Lectures by Christoph Kessler)
• Friday 26 october 2012 10:15-16:00 (Guest lecture by Welf Löwe)
• Monday 26 november 2012 13:00-17:00 Student presentations
• Tuesday 4 december 2012 13:00-17:00 Exam

Lecture notes

Exercises collection

Literature

If you prefer working with a textbook, you may e.g. use the ones mentioned below as additional reading. Note that most books cover much more than what we can go through in our introductory course.

As a good introductory textbook we recommend

• E. Alpaydin: Introduction to Machine Learning. MIT Press, Second Edition, 2010.

Other useful books: (e.g. for further reading)

• Christopher Bishop: Pattern Recognition and Machine Learning. Springer, 2007.
• Han, J., Kamber, M.: Data Mining: Concepts and Techniques, 2nd ed. The Morgan Kaufmann Series in Data Management Systems. Morgan Kaufmann, San Francisco (2000)
• Nilsson, N.J.: Introduction to machine learning: An early draft of proposed text book. Stanford University, Stanford (1996)
• Tom Mitchell: Machine Learning. McGraw-Hill, New York, 1997.
• Raul Rojas: Neural Networks. Springer, 1996.
• Russell, Norvig: Artificial Intelligence, second edition.
  Only partly applicable.
• David MacKay: Information theory, inference and learning algorithms. Cambridge Univ. Press, 2006.

• P. Domingos: A few useful things to know about machine learning. Comm. ACM 55(10):78-87, oct. 2012.

• Moshkov, M.: Algorithms for constructing of decision trees. In: Komorowski, J., Zytkow, J.M. (eds.) PKDD 1997. LNCS vol. 1263, pp. 335-342. Springer, Heidelberg (1997)

• Bryant, R.E.: Symbolic boolean manipulation with ordered binary-decision diagrams. ACM Computing Surveys 24, 293-318 (1992)
• Bryant, R.E.: Graph-based algorithms for boolean function manipulation. IEEE Transactions on Computers 35, 677-691 (1986)
• Johnson, S.: Branching programs and binary decision diagrams: theory and applications by Ingo-Wegener society for industrial and applied mathematics, vol. 41, pp. 36-38. ACM, New York (2010)

• Cortes, C., Vapnik, V.: Support-vector networks. Mach. Learn. 20, 273-297 (1995)
• Chang, C.-C., Lin, C.-J.: Libsvm - a library for support vector machines. National Taiwan University, Dep. of Comp. Science and Inf. Eng. (2001)
• Hsu, C.-W., Chang, C.-C., Lin, C.-J.: A practical guide to support vector classification. National Taiwan University, Dep. of Comp. Science, Tech. Rep. (2003)
• Kramer, K.A., Hall, L.O., Goldgof, D.B., Remsen, A., Luo, T.: Fast support vector machines for continuous data. Trans. Sys. Man Cyber. 39, 989-1001 (2009)

• Keogh, E.J., Pazzani, M.J.: Learning augmented bayesian classifiers: A comparison of distribution-based and classification-based approaches (1999)

Further literature references will be added later.

Teachers

• Christoph Kessler, Linköpings universitet (course leader, lecturer, examiner)
• Welf Löwe, Univ. Växjö (lecturer, examiner)
• Lu Li or Usman Dastgeer (lesson assistant)
• Further guest lecturers?

Examination

TEN1: Written exam (Welf, Christoph) 1.5p.

• Allowed aids: pocket calculator, English dictionary. No books, no slides, no papers.

Credit
3p if both examination moments are fulfilled. Admission to the exam requires attendance in 50% of the lectures and lessons.

Comments
New course 2012.

Related Courses
Machine Learning course at Control Engineering, ISY, Linköping University, given every other year. More mathematically than algorithmically oriented, and more details compared to our more light-weight course.
... list to be continued ...