AI Qualifying Exam Reading List Associated with CS 760 - MACHINE LEARNING

For Fall 2009 and Later Exams

Note that all of the items in the bibliography are linked to on-line versions active as of May 2009. For some textbooks, this is not a complete copy.

Basic Topics

  1. Supervised Learning: Inductive learning, inductive bias, Occam's razor. Feature space and feature selection. Handling noisy and incomplete data. Overfitting reduction, regularization. Ensemble methods (Bagging and Boosting). Minimal description length (MDL) methods. ID3. Naive Bayes. Perceptrons, delta rule, backpropagation, hidden units, early stopping. Support vector machines, margins, slack variables, kernels. Genetic algorithms.
    [CRISS00, Chapters 1-3; DIET97a, section on ensembles; MITC97, Chapters 2, 3, 4, and 9, Sections 6.6 and 6.9]
  2. Case-Based Learning: Instance-based models, kernel functions.
    [MITC97, Chapter 8]
  3. Inductive Logic Programming: Relational learning. Going beyond fixed-length feature vectors.
    [MIT97, Chapter 10]
  4. Reinforcement Learning: Q-learning, SARSA. Exploration-exploitation tradeoff. Generalization across state.
    [MITC97, Chapter 13; SUTT99, Sections 6.4 and 6.5]
  5. Learning Theory: The PAC model, the VC dimension, the mistake-bound model.
    [MITC97, Chapter 7]
  6. Experimental Methodology: Training/tuning/testing sets, N-fold cross-validation, ROC and precision-recall curves, t-tests.
    [MITC97, Chapter 5; PROV98]

Advanced Topics

  1. Unsupervised Learning Methods: Principal components analysis. K-means clustering. Expectation maximization.
    [BILM98; MACK03, Chapter 20; SHLE09]
  2. Semi-Supervised Learning Methods: Mixture models. Multiview models (including co-training). Graph-based and margin-based approaches.
    [ZHU09, Chapters 2-6]
  3. Supervised Learning Methods: Advanced aspects of Boosting and Bagging. Learning in graphical models. Discriminative vs. generative learning.
    [BREI96; FREU96; FRIE98; TASK02]
  4. Alternative Learning Settings: Co-training. Multiple-instance learning. Collective inference. Active learning, active-learning scenarios, uncertainty sampling, query by committee. [BLUM98; DIET97b; SETT09; TASK02]
  5. Reinforcement Learning: Temporal difference learning. Options and hierarchical reinforcement learning.
    [SUTT88; SUTT99]
  6. Statistical Relational Learning: Combining logical and probabilistic methods. Probabilistic relational models, Markov logic networks.
    [GETO01; RICH06]
  7. Using Prior Knowledge: Using both existing knowledge and training examples to learn. Theory refinement in symbolic and numeric models. Learning in Markov logic networks.
    [MITC97, Chapter 12; PAZZ92; RICH06; TOWE94]
  8. Learning Theory: The bias-variance tradeoff.
    [GEMA92]

References

[BILM98]
Bilmes, J. A Gentle Tutorial of the EM Algorithm and its Application to Parameter Estimation for Gaussian Mixture and Hidden Markov Models, Department of Electrical Engineering and Computer Science Technical Report 97-021, University of California - Berkeley, 1998.

[BLUM98]
Blum, A. and Mitchell, T., Combining labeled and unlabeled data with co-training. Proc. 11th Annual Conf. on Computational Learning Theory, 1998, 92-100.

[BREI96]
Breiman, L., Bagging predictors, Machine Learning 24, 1996, 123-140.

[CRIS00]
Cristiani, N. and Shawe-Taylor, J., An Introduction to Support Vector Machines, Cambridge University Press, Cambirdge, England, 2000.

[DIET97a]
Dietterich, T., Machine learning research: Four current directions, AI Magazine 18, 1997, 97-136.

[DIET97b]
Dietterich, T., Lathrop, R., and Lozano-Perez, T, Solving the multiple-instance problem with axis-parallel rectangles. Artificial Intelligence, 89, 1997, 31-71.

[FREU96]
Freund, Y. and Schapire, R., Experiments with a new boosting algorithm, in Proc. 13th Intl. Conf. on Machine Learning, 1996, 148-156.

[FRIE98]
Friedman, N. and Goldszmidt, M., Learning Bayesian networks with local structure, in Learning Graphical Models, Jordan, M. (ed.), 1998.

[GEMA92]
Geman, S., Bienenstock, E., and Doursat, R. Neural networks and the bias/variance dilemma, Neural Computation 4, 1992, 1-58.

[GETO01]
Getoor, L., Friedman, N., Koller, D., and Pfeffer, A., Learning probabilistic relational models. Relational Data Mining, S. Dzeroski and N. Lavrac (eds.), pp. 307-337, Springer, 2001.

[MACK03]
MacKay, D., Information Theory, Inference, and Learning Algorithms, Cambridge University Press, 2003.

[MITC97]
Mitchell, T., Machine Learning, McGraw-Hill, New York, 1997.

[PAZZ92]
Pazzani, M. and Kibler, D., The utility of knowledge in inductive learning, Machine Learning 9, 1992, 57-94.

[PROV98]
Provost, F., Fawcett, T., and Kohavi, R., The case against accuracy estimation for comparing induction algorithms, Proc. 15th Intl. Conf. on Machine Learning, 1998, 445-453.

[RICH06]
Richardson, M. and Domingos, P., Markov logic networks, Machine Learning 62, 2006, 107-136.

[SETT09]
Settles, B., Active Learning Literature Survey, Computer Sciences Technical Report 1648, University of Wisconsin-Madison, 2009.

[SHLE09]
Shlens, J., A Tutorial on Principal Component Analysis, 2009.

[SUTT88]
Sutton, R., Learning to predict by the methods of temporal differences, Machine Learning 3, 1988, 9-44.

[SUTT99]
Sutton, R., Precup, D., and Singh, S., Between MDPs and semi-MDPs: A framework for temporal abstraction in reinforcement learning, Artificial Intelligence 112, 1999, 181-211.

[TASK02]
Taskar, B., Abbeel, P., and Koller, D., Discriminative probabilistic models for relational data, Proc. 18th Intl. Conf. on Uncertainty in AI (UAI), 2002.

[TOWE94]
Towell, G. and Shavlik, J., Knowledge-based neural networks, Artificial Intelligence 70, 1994, 119-165.

[ZHU09]
Zhu, X. and Goldberg, A., Introduction to Semi-Supervised Learning, Morgan and Claypool, 2009. (Access from UW machines)