Computational Data Analysis:
FOUNDATIONS OF MACHINE LEARNING & DATA MINING
Spring 2008 graduate course
CSE 6740 A, 26897

Alexander Gray
College of Computing, Georgia Tech
What's this course about?
This course covers the fundamental theoretical concepts needed to answer the practical questions which quickly arise in real data analysis and is a PhD-level course which prepares students to do research in machine learning. Machine learning, or pattern recognition, or computational statistics, or data mining, is a huge field with thousands of methods and mountains of theoretical ideas - in fact statistics, the mathematics of data analysis, is by far the largest area of mathematics. I will attempt to organize the many ideas in ways that reveal the true underlying repeating themes and separate issues which are truly separate. This course will pull together many of the ideas I feel are most helpful in practice based on my experience, a number of which lie outside the current culture of "machine learning" and are not described in any existing machine learning course, to my knowledge.

The course is designed to answer the most fundamental questions about machine learning. Each lecture treats one main question, and several cross-cutting questions will be answered along the way: How can we conceptually organize the zoo of available methods, not to mention the several different fields which all seem to be about data? What are the most important methods to know about, and why? How can we sometimes answer the question 'is this method better than this one' using asymptotic theory? How can we sometimes answer the question 'is this method better than this one' for a specific dataset of interest? What can we say about the errors our method will make on future data? What's the 'right' objective function? What does it mean to be statistically rigorous? What are some ML people missing by not knowing much about statistical theory? Should I be a Bayesian? What is the source of certain 'religious' divides? What computer science ideas can make ML methods tractable on modern large or complex datasets? What are some questions that need answering in the field?

Syllabus
Title Topics Reading
1 What is Machine Learning? (Overview) Examples of ML; the parts of ML, tasks of ML, "Machine learning" (ML) vs. "computational statistics" vs. "data mining" vs. "pattern recognition", course overview, main themes
Basic concepts of ML, illustrated by 10 ML methods
2 How Do I Learn Simple Models? (Probability and Inference) Probability, random variables, distributions; estimation, convergence and asymptotics, confidence intervals
3 How Do I Learn a Mixture of Gaussians? (Parametric Estimation) Likelihood, mixture of Gaussians (MoG), the EM algorithm for MoG (i); generalization, model selection, cross-validation
4 How Do I Learn Any Density? (Nonparametric Estimation) Parametric vs. nonparametric estimation, Sobolev and other spaces; L2 error, kernel density estimation (KDE) (ii), optimal kernels, KDE theory
5 How Do I Predict a Continuous Variable? (Regression) Conditional density estimation; linear regression (iii), regularization, ridge regression and LASSO (iv); Nadaraya-Watson and local linear regression (v)
6 How Do I Predict a Discrete Variable? (Classification) Bayes classifier, naive Bayes (vi), generative vs. discriminative; perceptron (vii), weight decay, linear support vector machine (SVM) (viii); nearest-neighbor classifier (ix) and theory; decision tree (x)
7 How Do I Start Doing Machine Learning? (The Georgia Tech Machine Learning Project) Machine learning code, how the course project works
General theory and model frameworks of ML
8 What Loss Function Should I Use? (Maximum Likelihood and Bayesian Inference) Maximum likelihood estimation theory; Bayesian estimation, Bayesianism vs. frequentism
9 What Loss Function Should I Use? (Estimation Theory) Robustness, L2 estimation, L2 MoG; decision theory
10 What Model (Parameters) Should I Use? (Learning Theory and Generalization) Vapnik-Chervonenkis theory; the bootstrap; ensemble methods: bagging, stacking, boosting
11 How Can I Learn Fancier (Nonlinear) Models? (Kernelization) Kernelization, regularization theory, reproducing kernel Hilbert spaces, nonlinear SVM
12 How Can I Learn Fancier (Compositional) Models? (Trees, Networks, and Graphical Models) Decision trees; neural networks; graphical models
Further common ML problems and solutions
13 How Do I Reduce/Relate the Features? (Dimension Reduction) Principal component analysis (PCA), ICA, multidimensional scaling, manifold learning
14 How Do I Reduce/Relate The Data Points? (Association and Clustering) Association rules and market basket analysis; parametric and nonparametric clustering
15 How Do I Treat Temporal Data? (Time Series Analysis) Stationarity, seasonality, ARMA, Kalman filters and state-space models
16 How Do I Learn Actions From Data? (Reinforcement Learning) Markov decision processes, policy and value iteration, Q-learning, prioritized sweeping
General computational frameworks for ML
17 How Do I Optimize The Parameters? (Unconstrained Optimization) Unconstrained vs. constrained/convex optimization, derivative-free methods, first- and second-order methods, sum-of-squares methods
18 How Do I Optimize Convex/Linear Functions? (Unconstrained Linear Optimization) Convexity, computational linear algebra as optimization, matrix inversion for regression, singular value decomposition (SVD) for dimensionality reduction, stochastic gradient descent
19 How Do I Optimize With Constraints? (Constrained Optimization) Lagrange multipliers, the KKT conditions, interior point method, SMO algorithm for SVM's
20 How Do I Evaluate High-Dimensional Integrals? (Sampling) Monte Carlo integration, importance sampling, Markov Chain Monte Carlo
21 How Do I Evaluate Deeply-Nested Sums? (Graphical Model Inference) Elimination, belief propagation / sum-product algorithm, junction-tree algorithm, variational methods
22 How Do I Evaluate Large Sums And Searches? Generalized N-body problems (GNPs), hierarchical data structures, nearest-neighbor search, fast multipole methods
Real-world application of ML
23 How Do I Apply All This In The Real World? Exploratory data analysis and information visualization; modeling choices; prior knowledge and assumptions; non-ideal data; evaluation and interpretation; where the research problems in ML are
Where and when
TuTh 3:05-4:25pm, 1456 Klaus (no longer 2447). First class: Tuesday 1/8/08. My office hours: Fridays 10-12, 1305 Klaus. Course mailing list: http://www2.isye.gatech.edu/mailman/listinfo/isye6740a .

Books
Required: All of Statistics by Wasserman ("AOS"), The Elements of Statistical Learning by Hastie, Tibshirani, and Friedman ("ESL"), Pattern Recognition and Machine Learning by Bishop ("PRML"). (Sorry -- these are all good books, but the scope of the course requires all three. Good books are worth their weight in gold - you shouldn't be cheap about buying technical books.)

Guest lectures
To help give you a complete picture all the way to professional research practice, I will invite about 5 esteemed machine learning researchers to give talks on their research during the class period, as part of the Yahoo-sponsored Georgia Tech machine learning seminar which I'll be organizing. These will count as course lectures, including easy quiz questions (see below)!

How is the course graded?
1. Quizzes on theory: 20%. There will be a 5-minute multiple-choice quiz at the end of each lecture on the material in that lecture, consisting of about 3 questions. These questions will be easy if you were not asleep in lecture. Your lowest 5 quiz scores (including zeros for not attending class on quiz days) will be thrown out.

2. Final exam on theory: 30%. This will cover the entire course and contain short-answer and multiple-choice questions. The course will not require that you prove theorems, though the questions may get at whether you understand the proofs of some of the key theorems in the class.

3. Implementations/experiments: 50%. Beginning somewhere after the 8th lecture (once you have the necesssary background), you will start implementing machine learning methods in Matlab and/or C++, testing your implementations and those of other students in the class, and comparing them on reference datasets. Which methods you implement will be according to your interests. A large list of pre-approved methods will be given, though you may also propose methods which may not be on the list. Getting an A on this part of the course roughly requires implementing at least two methods well. All the work done by the class, including source code, will be organized on an internal wiki, and will finally be put on a big webpage which will be useful to other researchers and PhD students in the field, with links from the appropriate wikipedia pages. Exact details regarding the logistics will be announced later in the class.

Should you take this course?
What is the intended audience of this course? Anyone who wants to competently apply statistical and machine learning methods to real-world datasets, or design new methods, can benefit from understanding the tools I will describe. For anyone who wants to do research in machine learning, these are the foundations you need to understand. It will satisfy both the CSE requirement and the Intelligent Systems requirement of the CoC PhD program, and is one of the core courses of the CSE PhD program.

How does this course relate to other course offerings? In general, it focuses on laying comprehensive mathematical foundations; it has the largest scope in terms of topical coverage, and is thus somewhat intensive. It could have been called "All of Machine Learning" and follows the same spirit as Wasserman's "All of Statistics". This course can be thought of as extending the CoC undergraduate/graduate Intro to Machine Learning course, although it is not strictly necessary to take that course first. It will be helpful though - machine learning is a big subject with many concepts, so seeing some of the same material twice will not hurt at all. That course is a gentler introduction covering a subset of the material in this course without being as mathematical, but also covers some AI-related topics not covered in this course, most notably reinforcement learning and game theory. If AI is your main interest in machine learning rather than data analysis, that course's perspective is going to be what you want. In ISYE there are several courses which also cover a subset of the methods covered in this course in more depth, from the point of view of the culture of statistics, including courses called computational statistics and data mining, and a brand new course on spatial statistics which will be of interest for many applications. More generally, this course gives a crash overview of fundamental statistical theory, which is covered over many courses in ISYE. In CoC there is a course called pattern recognition, which also covers a subset of the methods covered in this course in more depth, from the point of view of the culture of computer vision and electrical engineering. Again, seeing some of the same material more than once will not hurt you. There is a course on text mining -- this will be useful for applying machine learning to text data. This course, by contrast, is of a more general nature and does not discuss the special aspects of text data. In CoC there is a theoretical course on spectral methods, which includes discusson of some linear algebraic machine learning methods. In the Math department there is a class on Learning Theory, a sub-topic of machine learning which focuses on theoretical bounds, mainly for the classification problem. In this class I will briefly cover learning theory but will only hit the highlights which inform practice - the Math course is for you if you want to master proving those kinds of theorems (and you have a background in Real Analysis). All of the aforementioned courses are valuable, so I encourage checking them out.

How hard is this course? This course is designed for the PhD level. MS students and advanced undergraduate students (who generally have a heavy courseload) are warned of the time commitment required by this course, due to the mathematical nature of the material as well as the time it takes to read about and implement many machine learning methods in the experimental part of the course. Otherwise, if you have the time to put in and the true desire to gain expertise in this topic, students of any level and in any discipline are welcome. Auditing is fine with me but I don't recommend it, due to the pace of the technical concepts.

What background is needed for this course? I will assume very little specific prior knowledge, aside from basic math familiarity (calculus, matrices, probability) and general principles of computer science (algorithms, data structures); however since this is a PhD-level course I'll assume a certain level of general technical maturity (in other words don't expect the material to be trivial). Familiarity with machine learning will be helpful but is not necessary.