CPSC 633: Machine Learning (Spring 2008)

Professor: Dr. Thomas R. Ioerger
Office: 322C HRBB
Phone: 845-0161
Email: ioerger@cs.tamu.edu
Office hours: by appt. (set up via email)

Class Time: MWF, 3:00-3:50
Room: TBA
Course WWW page: http://www.cs.tamu.edu/faculty/ioerger/cs633-spring08/index.html

Textbook: Machine Learning. Tom Mitchell (1997). McGraw-Hill.

Goals of the Course:

Machine learning is an important sub-area within AI, and is broadly applicable to many application areas within Computer Science. Machine learning can be viewed as methods for making systems adaptive (improving performance with experience), or alternatively, for augmenting the intelligence of knowledge-based systems via rule acquisition. In this course, we will examine and compare several different abstract models of learning, from hypothesis-space search, to function approximation (such as by gradient descent), to statistical inference (e.g. Bayesian), to the minimum description-length principle. Both theoretical issues (e.g. algorithmic complexity, hypothesis space bias) as well as practical issues (e.g. feature selection; dealing with noise and preventing overfit) will be covered.

Topics to be Covered: 

  Symbolic learning
    version spaces, decision trees, rule induction
    explanation-based learning, inductive-logic programming
  Nearest-neighbor (non-parametric) algorithms
  Feature selection and feature weighting
    filters and wrappers, entropy
    principle-component analysis
    constructive induction
  Linear classifiers (covered lightly)
    neural networks, multi-layer perceptrons, and gradient descent
    support vector machines, maximum-margin optimization
  Bayesian classifiers
  Computational learning theory
    inductive bias, hypothesis space search
    PAC model (probably-approximately correct)
    algorithmic complexity, sample complexity
  Unsupervised learning (data mining)
    clustering, association rules
(Note: The material on Linear Classifiers will only be covered lightly, as these subjects are covered in more detail in Dr. Gutierrez-Osuna's CPSC 689 course on Statistical Pattern Recognition, and Dr. Yoonsuck Choe's CPSC 636 course on Neural Networks.)

Additional topics, such as genetic algorithms or reinforcement learning, may be covered, depending on the interests of the students in the class.

Prerequisites

CPSC 420/625 - Introduction to Artificial Intelligence

We will be relying on standard concepts in AI, especially heuristic search algorithms, propositional logic, and first-order predicate calculus. Either the graduate or undergraduate AI class (or a similar course at another university) will count as satisfying this prerequisite.

In addition, the course will require some background in analysis of algorithms (big-O notation), and some familiarity with probability and statistics (e.g. standard deviation, confidence intervals, linear regression, Binomial distribution).

Homeworks, Projects, and Exams

There will be occasional homeworks and exams (probably 1 mid-term and a final). However, the main work for the class will consist of several programming projects in which you will implement and test your own versions of several learning algorithms. These will not be group projects, so you will be expected to do your own work. Several databases will be provided for testing your algorithms (e.g. for accuracy). A written report describing your implementation and results will be required for each project.

The late-assignment policy for homeworks and projects will be incremental: -5%/per day, down to a maximum of -50%. If the project is turned in anytime by the end of the semester, you can still get up to 50% (minus points marked off).

The overall grade for the course will consist of a weighted average of scores achieved (roughly 33% homeworks, 33% projects, and 33% exams), though the final weights will be adjusted at the end to reflect the actual effort expended over the course of the semester.

Schedule

Mon, Jan 14: Perspectives on Machine Learning
Wed, Jan 16: Ch. 1 - choices in designing a learning system
Fri, Jan 18: Ch. 2 - Searching Hypothesis Space
Mon, Jan 21: (class cancelled - MLK day)
Wed, Jan 23: Candidate Elimination, bias
Fri, Jan 25: Ch. 3 - Decision Trees (ID3)
Mon, Jan 28: pruning, overfit
Wed, Jan 30: handling continuous attributes

Fri, Feb 1: Perceptrons (read Ch. 4)
Mon, Feb 4: Back-propagation
Wed, Feb 6: (class cancelled)
Fri, Feb 8: (class cancelled)
Mon, Feb 11: Empirical methods (read Ch. 5) - estimating hypothesis accuracy, confidence intervals, significance tests
Wed, Feb 13: cross-validation and bootstrapping (Efron and Tibshirani, 1997)
Fri, Feb 15: Support Vector Machines
Mon, Feb 18: Project #1 due
Wed, Feb 20: kernel functions, non-linear boundaries
Fri, Feb 22: Bayesian methods (read Ch. 6)
Mon, Feb 25: ** mid-term exam **
Wed, Feb 27: likelihood calculations
Fri, Feb 29: Bayes-Optimal classifer, Naive Bayes Algorithm

Mon, Mar 3: Bayesian networks
Wed, Mar 5:
Fri, Mar 7:
Mon, Mar 10: (spring break)
Wed, Mar 12: (spring break)
Fri, Mar 14: (spring break)
Mon, Mar 17: Nearest Neighbor (Ch. 8); NTGrowth; Project #2 due
Wed, Mar 19: RELIEF (Kononenko, 1994), FRINGE (Pagallo, 1989)
Fri, Mar 21: (class cancelled - Good Friday)
Mon, Mar 24: LFC (Ragavan, Rendell, Shaw, and Tessmer, 1993), concept complexity(Nazar and Bramer, 1998)
Wed, Mar 26: wrapper methods (John, Kokavi, and Pfleger, 1994), FOCUS (Allmualim and Dietterich, 1991)
Fri, Mar 28: feature interactions: Jakulin and Bratko, 2003, Zhao and Liu, 2007
Mon, Mar 31: feature weighting Wettschereck and Aha, 1995


Wed, Apr 2: PCA, ICA, SVD, LDA (see links below)
Fri, Apr 4: PCA cont'd
Mon, Apr 7: LDA
Wed, Apr 9: Computational Learning Theory (Ch. 7); PAC model
Fri, Apr 11: VC dimension
Mon, Apr 14: mistake-bounded model
Wed, Apr 16: boosting: Freund and Schapire, Maclin and Optiz
Fri, Apr 18: ensemble classifers, Dietterich
Mon, Apr 21: Reinforcement Learning (Ch. 13)
Wed, Apr 23: (additional resources: Barto and Sutton, Kaelbling, Littman, and Moore)
Fri, Apr 25: Exam #2
Mon, Apr 28: value-function approximation, least-squares policy iteration (Lagoudakis and Parr)
Tues, Apr 29: (last day of class); Project #3 due

Resources on Bayesian Networks

Notes on PCA, SVD, ICA, LDA...