G22-2565-001, Fall 2010:
Machine Learning and Pattern Recognition

Machine Learning and Pattern Recognition methods are at the core of many recent advances in "intelligent computing". Current applications include machine perception (vision, audition, speech recognition), control (process control, robotics), data mining, time-series prediction (e.g. in finance), natural language processing, text mining and text classification, bio-informatics, neural modeling, computational models of biological processes, and many other areas.

The only formal pre-requisites are familiarity with computer programming and linear algebra, but the course relies heavily on such mathematical tools as probability and statistics, multi-variate calculus, and function optimization. The basic mathematical concepts will be introduced when needed, but students will be expected to assimilate a non-trivial amount of mathematical concepts in a fairly short time.

Although this is a graduate-level course, highly motivated undergraduates at the senior level with a good math background can take this class. A few juniors have even taken this class successfully in the past.

• the basics of inductive inference, learning, and generalization.
• linear classifiers: perceptron, LMS, logistic regression.
• non-linear classifiers with linear parameterizations: basis-function methods, boosting, support vector machines.
• multilayer neural networks, backpropagation
• heterogeneous learning systems
• graph-based models for sequences: hidden Markov models, finite-state transducers, recurrent networks.
• unsupervised learning: density estimation, clustering, and dimensionality reduction methods.
• introduction to graphical models and factor graphs
• approximate inference, sampling.
• optimization methods in learning: gradient-based methods, second-order methods, Expectation-Maximization.
• objective functions: maximum likelihood, maximum a-posteriori, discriminative criteria, maximum margin.
• the bias-variance dilemma, regularization, model selection.
• applications in vision, speech, language, forecasting, and biological modeling.

Software for the homeworks

Skeleton code for the homework will be provided in a simple-to-learn numerical programming language called Lush.

Lush is available on the CIMS servers and workstations that are available for student use (remotely through ssh or in the computer labs).

Lush only runs on Linux, so you must have a version of Linux installed on your machine. If you don't already have Linux, you should install Ubuntu Linux on your machine (instructions below).

Installing Ubuntu Linux

There are several options for installing Ubuntu Linux on a Windows machine:

• Install Ubuntu on your Windows machine without repartitioning your harddrive using Wubi. Wubi is a Windows app that installs Ubuntu in a file on your Windows partition (the file is a virtual hardrive from Linux's point of view). Wubi is not an emulator, so you have to boot your machine in either Linux or Windows. You can't run them at the same time.
• download and install Ubuntu. The Ubuntu installer offers you the option of shrinking your Windows partition non-destructively so as to make space for Linux. The installation is very simple and takes about 20 minutes. It can be done from a CD/DVD or from a USB flash drive.
• Install Ubuntu through VMWare so you can run Window and Ubuntu at the same time.

You can also dispense with installing Ubuntu Linux altogether and simply use the Linux machines at the Courant Institute computer labs.

Installing Lush

After you have installed Ubuntu Linux, you must install a number of packages using the shell commands below (type your password when prompted):

sudo apt-get install gcc g++ libx11-dev binutils-dev indent libreadline5 libreadline5-dev 
sudo apt-get install emacs cvs libgsl0-dev imagemagick

then, at the shell, do:

cd
cvs -d:pserver:anonymous@lush.cvs.sourceforge.net:/cvsroot/lush login 
[type enter when prompted for a password]
cvs -z3 -d:pserver:anonymous@lush.cvs.sourceforge.net:/cvsroot/lush co lush
cd lush
./configure
make

cd
mkdir bin 
cd bin
ln -s ../lush/bin/i686-pc-linux-gnu/lush .

cd
cd lush
sudo make install

The course will include a short tutorial on the Lush language, a simple interpreted language for numerical applications.

Alternatives to Lush

If you really want, you can implement the homeworks in another language, (C, C++, Java, Matlab, Lisp, Python,...) but the use of a high-level interpreted language with good numerical support and good support for vector/matrix algebra is highly recommended (Lush, Matlab, Octave...). Some assignments require the use of an object-oriented language, which rules out

If you decide to use another language than Lush, you will be doing a lot more work than necessary (particularly for homework 2).

NOTES: 13) The publisher just released the first edition of this book on August 28, 2006, so you might have to wait a few days before getting it. (2) this is a different book from past years; (3) This is not Bishop's previous book called Neural Networks and Pattern Recognition;

The textbook can be used for reference, but I will not follow it very closely.

The following books can also be used for complementary material (you can get copies from the library):

• Richard O. Duda, Peter E. Hart, David G. Stork: "Pattern Classification" Wiley-Interscience; 2nd edition, October 2000.
• T. Hastie, R. Tibshirani, and J. Friedman: "Elements of Statistical Learning", Springer-Verlag, 2001.
• Ethem Alpaydin: Introduction to Machine Learning, MIT Press, October 2004.

Other Books of Interest

• C. Bishop: "Neural Networks for Pattern Recognition", Oxford University Press, 1996. Pretty much superseded by Bishop's lates book.
• S. Haykin: "Neural Networks, a comprehensive foundation", Prentice Hall, 1999 (second edition).
• Tom Mitchell: "Machine Learning", McGraw Hill, 1997.