Machine Learning
Department of Computer Science
Iowa State University

Study Guide

Week 1 (January 10, 2005)

Overview of the course. Overview of machine learning. Why should machines learn? Operational definition of learning. Taxonomy of machine learning. Specification of a computational model of learning. Example: specification and analysis of a model for conjunctive concept learning. Role of representational and inferential bias in learning.

Review of probability theory and random variables. Probability spaces. Ontological and epistemological commitments of probabilistic representations of knowledge. Bayesian (subjective view of probability) -- Probabilities as measures of belief conditioned on the agent's knowledge. Possible world interpretation of probability. Axioms of probability. Conditional probability. Bayes theorem. Random Variables. Discrete Random Variables as functions from event spaces to Value sets. Possible world interpretation of random variables. Joint Probability distributions. Conditional Probability Distributions. Conditional Independence of Random variables. Pair-wise independence and independence. Entropy of random variables, Information, Mutual Information. Measures of distance between probability distributions -- Kullback-Liebler divergence.

Required readings

Recommended Readings

Strongly Recommended Java Readings for those unfamiliar with Java.

Week 2 (Beginning January 17, 2005)

Bayesian Decision Theory. Optimal Bayes Classifier. Minimum Risk Bayes Classifier. Naive Bayes Classifier. Maximum Likelihood Probability Estimation. Properties of Maximum Likelihood Estimators. Limitations of Maximum Likelihood Estimators. Bayesian Estimation. Conjugate Priors. Detailed treatment of Bayesian estimation in the multinomial case using Dirichlet priors. Maximum A posteriori Estimation. Representative applications of Naive Bayes classifiers - e.g., text classification.

Required readings

Recommended Readings

Week 3 (Beginning Jan 24, 2005)

More on Bayesian estimation of probabilities from Data. Learning Decision Tree Classifiers from Data. Occam's razor. Brief digression into information theory. Entropy of random variables, Information, Mutual Information. Measures of distance between probability distributions -- Kullback-Liebler divergence. Bayesian Learning of Classifiers. Learning Maximum a-posteriori (MAP) and Maximum Likelihood (ML) hypothesis from data. The relationship between MAP hypothesis learning, minimum description length principle (Occam's razor) and the role of priors. Equivalence of ML hypothesis learner and consistent learner for classification tasks. Algorithm for learning decision tree classifiers from data. Evaluation of classifiers. Accuracy, Precision, Recall, Correlation Coefficient, ROC curves.

Required Readings

Recommended Readings

Week 4 (Jan 31, 2004)

Evaluation of classifiers -- estimation of performance measures; confidence interval calculation for estimates; cross-validation based estimates of hypothesis performance; leave-one-out and bootstrap estimates of performance; comparing two hypotheses; hypothesis testing; comparing two learning algorithms.

Algorithms for Learning Decision Trees (Continued). Overfitting and methods to avoid overfitting -- dealing with small sample sizes; prepruning and post-pruning. Pitfalls of entropy as a splitting criterion for multi-valued splits. Alternative splitting strategies -- two-way versus multi-way splits; Alternative split criteria: Gini impurity, Entropy, etc. Cost-sensitive decision tree induction -- incorporating attribute measurement costs and misclassification costs into decision tree induction. Dealing with categorical, numeric, and ordinal attributes. Dealing with missing attribute values during tree induction and instance classification;

Required readings

Recommended Readings

Week 5 (Beginning February 7, 2005)

Introduction to Artificial Neural Networks. Threshold logic unit (perceptron) and the associated hypothesis space. Connection with Logic and Geometry. Weight space and pattern space representations of perceptrons. Linear separability and related concepts. Perceptron Learning algorithm and its variants. Convergence properties of perceptron algorithm. Winner-Take-All Networks.

Dual representation of Perceptrons. A learning algorithm using dual representation of perceptrons. Advantages of working with dual representation. Nonlinear feature space mappings for learning non linear decision boundaries. Challenges of learning non linear decision boundaries using feature space mappings - computational problem of handling high dimensional feature spaces and the curse of dimensionality (with implications for generalization).

The Support Vector Machine (SVM) solution - Kernel functions for dealing with the computational problem. Kernel Matrices. Kernel Functions. Properties of Kernel Matrices and Kernel Functions. How to tell a good kernel from a bad one. How to construct kernels.

Required Readings

Recommended Readings

Week 6 (beginning February 14, 2005)

From Kernel Machines to Support Vector Machines. Maximal Margin Separating Hyperplanes -- Why?

Digression: Vapnik-Chervonenkis (VC) Dimesion and its properties. VC dimension of the hypothesis space of hyperplanes.

Vapnik's bounds on Misclassification rate (error rate). Minimizing misclassification risk by maximizing margin. Formulation of the problem of finding margin maximizing separating hyperplane as an optimization problem.

Digression: Unconstrained Optimization. Review of Relevant Mathematics (Limits, Continuity and Differentiablity of Functions, Local Minima and Maxima, Derivatives, Partial Derivatives, Taylor Series Approximation, Multi-Variate Taylor Series Approximation).

Introduction to Lagrange/Karush-Kuhn-Tucker Optimization Theory. Optimization problems. Linear, quadratic, and convex optimization problems. Primal and dual representations of optimization problems. Convex Quadratic programming formulation of the maximal margin separating hyperplane finding problem. Characteristics of the maximal margin separating hyperplane. Implementation of Support Vector Machines.

Required readings

Recommended readings

Week 7 (Beginning February 21, 2005).

Bayesian Framework for classification revisited. Naive Bayes classifier as a generative model. Relationship between generative models and linear classifiers. Additional examples of generative models. Generative models from the exponential family of distributions. Generative models versus discriminative models for classification. Derivation of gradient-based discriminative models directly for classification.

Required readings

Recommended Readings

Week 8 (Beginning February 28 2004)

Bayesian Networks. Conditional Independence Revisited, d-separation, and compact representation of joint probability distribution functions in Bayes Networks. Reasoning with Bayes Networks, Some algorithms for Exact Inference, and Approximate Inference of relevant probabilities from a Bayesian network using stochastic simulation (Sampling).

Required readings

Recommended Readings

Week 9 (Beginning March 7, 2005)

Learning Bayesian Networks from Data. Learning of parameters (conditional probability tables) from fully specified instances (when no attribute values are missing) in a network of known structure (review).

Learning Bayesian networks with unknown structure -- scoring functions for structure discovery, searching the space of network topologies using scoring functions to guide the search, structure learning in practice, Bayesian approach to structure discovery, examples.

Learning Bayesian network parameters in the presence of missing attribute values (using Expectation Maximization) when the structure is known; Learning networks of unknown structure in the presence of missing attribute values.

Required readings

Recommended Readings

SPRING BREAK

Week 10 (Beginning March 21 2004)

Topics in Computational Learning Theory

Mistake bound analysis of learning algorithms. Mistake bound analysis of online algorithms for learning Conjunctive Concepts. Optimal Mistake Bounds. Version Space Halving Algorithm. Randomized Halving Algorithm. Learning monotone disjunctions in the presence of irrelevant attributes -- the Winnow and Balanced Winnow Algorithms. Multiplicative Update Algorithms for concept learning and function approximation. Weighted majority algorithm. Applications.

Probably Approximately Correct (PAC) Learning Model. Efficient PAC learnability. Sample Complexity of PAC Learning in terms of cardinality of hypothesis space (for finite hypothesis classes). Some Concept Classes that are easy to learn within the PAC setting.

Required readings

Recommended Readings

Week 11 (Beginning March 28 2005)

Efficiently PAC learnable concept classes. Sufficient conditions for efficient PAC learnability. Some concept classes that are not efficiently learnable in the PAC setting. Making hard-to-learn concept classes efficiently learnable -- transforming instance representation and hypothesis representation. Occam Learning Algorithms. PAC Learnability of infinite concept classes. Vapnik-Chervonenkis (VC) dimension. Properties of VC dimension, VC dimension and learnability, Learning from Noisy examples, Transforming weak learners into PAC learners through accuracy and confidence boosting, Learning under helpful distributions - Kolmogorov Complexity, Conditional Kolmogorov Complexity, Universal distributions, Learning Simple Concepts, Learning from Simple Examples

Required readings

Recommended Readings

Week 12 (Beginning April 4 2005)

Ensemble Classifiers. Techniques for generating base classifiers; techniques for combining classifiers. Committee Machines and Bagging. Boosting. The Adaboost Algorithm. Theoretical performance of Adaboost. Boosting in practice. When does boosting help? Why does boosting work? Boosting and additive models. Loss function analysis. Boosting of multi-class classifiers. Boosting using classifiers that produce confidence estimates for class labels. Boosting and margin. Variants of boosting - generating classifiers by changing instance distribution; generating classifiers by using subsets of features; generating classifiers by changing the output code. Further insights into boosting.

Required readings

Recommended Readings

Week 13 (beginning April 11, 2005)

Bayesian Recipe for function approximation and Least Mean Squared (LMS) Error Criterion. Introduction to neural networks as trainable function approximators. Function approximation from examples. Minimization of Error Functions. Review of Relevant Mathematics (Limits, Continuity and Differentiablity of Functions, Local Minima and Maxima, Derivatives, Partial Derivatives, Taylor Series Approximation, Multi-Variate Taylor Series Approximation) Derivation of a Learning Rule for Minimizing Mean Squared Error Function for a Simple Linear Neuron. Momentum modification for speeding up learning. Introduction to neural networks for nonlinear function approximation. Nonlinear function approximation using multi-layer neural networks. Universal function approximation theorem. Derivation of the generalized delta rule (GDR) (the backpropagation learning algorithm). Generalized delta rule (backpropagation algorithm) in practice - avoiding overfitting, choosing neuron activation functions, choosing learning rate, choosing initial weights, speeding up learning, improving generalization, circumventing local minima, using domain-specific constraints (e.g., translation invariance in visual pattern recognition), exploiting hints, using neural networks for function approximation and pattern classification. Relationship between neural networks and Bayesian pattern classification. Variations -- Radial basis function networks. Learning non linear functions by searching the space of network topologies as well as weights.

Required readings

Recommended Readings

Week 14 (Beginning April 18, 2005)

Lazy Learning Algorithms. Instance based Learning, K-nearest neighbor classifiers, distance functions, locally weighted regression, sample application to document classification using TFIDF representation. Relative advantages and disadvantages of lazy learning and eager learning.

Unsupervised or self-supervised learning. Clustering. Learning Mixture Models from Data; Identifiability of Mixture Models; Maximum Likelihood approach to Mixture Model Learning -- Expectation Maximization (EM) algorithms. K-means clustering algorithm and variants. Adaptive Resonance Theory (ART) family of clustering algorithms. Distance measures, Clustering Criteria -- Intra-Cluster and Inter-Cluster distances. Hierarchical Agglomerative Clustering Algorithm. Distributional Clustering, Applications to Learning Attribute Value Taxonomies from Data, Phylogeny Construction. Latent Semantic Indexing, Principal Component Analysis and related methods.

Required readings

Recommended Readings

Week 15 (April 25, 2004)

Reinforcement Learning. Agents that learn by exploration of environments, using environmental reward and punishment. Examples of reinforcement learning problems. Credit assignment problem and its implications. Exploration-exploitation dilemma. Some approaches to exploration-exploitation tradeoffs. Markov decision processes. Learning optimal policies from interaction with the environment -- determistic, stochastic, stationary and non-stationary environments. Value functions and Action-Value functions. Bellman equations and dynamic programming approach to learning optimal policies when the transition function and reward functions are known (i.e., the agent has a model of the environment). Q learning algorithm for learning optimal policies when an accurate model of the environment is not known. Temporal difference methods. Scaling up reinforcement learning to large state spaces -- function approximation methods for compact representation of actio-value functions; state abstraction methods for hierarchical reinforcement learning. Multi-agent reinforcement learning. Applications.

Review, Summary of the Course, and Discussion of Some Current Research Problems

Required readings

Recommended readings

Additional Information

If you would like to be alerted by email when this page is updated, please register with Changedetect.

Copyright © 1999-2005, Vasant Honavar, Department of Computer Science, Iowa State University. All rights reserved.

Dr. Vasant Honavar
Professor Department of Computer Science
Iowa State University
Atanasoff Hall, Ames, IA 50011-1040 USA
phone: +1-515-294-4377, fax: +1-515-294-0258