Apple Tree

Part 1:

• Support Vector Machines and Related Methods: Perceptron, optimal hyperplane and maximum-margin separation, soft-margin, SVMs for regression, Gaussian Processes, Boosting, regularized regression methods
• Learning with Kernels: properties, real-valued feature vectors, sequences and other structured data, Fisher kernels
• Statistical Learning Theory: no free lunch, VC theory, PAC-Bayesian, bias/variance, error bounds, leave-one-out bounds
• Error Estimation and Model Selection: leave-one-out and cross-validation, holdout testing, bootstrap estimation

• Transductive Learning: How can one use unlabeled data to improve performance in supervised learning? What is the information contained in unlabeled data? What assumptions do we need to make? How can we design efficient algorithms?
• Learning Complex Structures: What if the target function is more complex than in classification or regression? For example, the goal could be not a binary classification function, but an ordering (i.e. retrieval) function for information retrieval. Or, what if the input to the learning is not a classification, but merely pair-wise preferences like "A is preferred over B"?
• Learning Kernels: The kernel defines the inductive bias of the learning algorithm and is key to achieving good performance. This makes selecting a kernel one of the most crucial design decisions. How can we automate the selection process? In particular, how can one construct a good kernel from data? What are the situations where this might work? What are the assumptions?

Methods and theory will be illustrated with practical examples, in particular from the areas of information retrieval and language technology.

• 01/23: Linear Classifiers and Perceptron (PDF slides)
• 01/30: Optimal Hyperplane (PDF slides)
• 02/04: Optimization Theory and Duality for SVMs (PDF slides)
• 02/13: Training  SVMs (PDF slides) (demo slides)
• 02/20: Leave-one-Out and Expected Error (PDF slides)
• 02/27: Kernels (PDF slides)
• 03/06: Statistical Learning Theory (PDF slides)

• Datasets: earn.zip, earn.tar.gz, adult.zip, adult.tar.gz
• Support Vector Machine Software: SVM-light

• Filip's data access code

Homework 2: Training SVMs and Leave-One-Out

Homework 3: Kernels and Statistical Learning Theory

• Dataset: liver.tar

Learning Rankings:

1. William W. Cohen, Robert E. Schapire, Yoram Singer, Learning to order things, Journal of Artificial Intelligence Research, 10, 1999. (Steven, 4/15)
2. Y. Freund, R. Iyer, R. Schapire, and Y. Singer, An efficient boosting algorithm for combining preferences, ICML, 1998. (Scott, 4/17)
3. T. Joachims, Optimzing Search Engines using Clickthrough Data, KDD Conference, 2002. (Thorsten, 4/10)
4. R. Herbrich, T. Graepel, and K. Obermayer. Large Margin Rank Boundaries for Ordinal Regression. Advances in Large Margin Classifiers , pages 115-132, 2000. (Thorsten, 4/8)
5. R. Caruana, S. Baluja, and T. Mitchell, Using the Future to `Sort Out' the Present: Rankprop and Multitask Learning for Medical Risk Evaluation, NIPS, 1995. (Rich, 4/10)

Transductive Learning / Learning from Labeled and Unlabeled Data:

1. K. Nigam, A. McCallum, S. Thrun, and T. Mitchell. Text Classification from Labeled and Unlabeled Documents using EM. Machine Learning, 39(2/3). pp. 103-134. 2000. (Mark, 4/22)
2. T. Joachims, Transductive Inference for Text Classification using Support Vector Machines. ICML, 1999. (Thorsten, 4/17)
3. A. Blum and T. Mitchell. Combining Labeled and Unlabeled Data with Co-Training, COLT, 1998. (Andy, 4/24)
4. O. Chapelle, J. Weston and B. Schölkopf, Cluster Kernels for Semi-Supervised Learning. NIPS, 2003. (Phil, 4/22)
5. M. Szummer and T. Jaakkola, Partially labeled classification with Markov random walks, NIPS, 2001. (Filip, 4/22)
6. A. Blum, S. Chawla, Learning from Labeled and Unlabeled Data using Graph Mincuts. ICML, 2001. (Alan, 4/24)

Learning to Learn / Learning Kernels:

1. R. Caruana, Multitask Learning. Machine Learning 28(1): 41-75, 1997. (Rich, 4/29)
2. Sebastian Thrun and Joseph O'Sullivan, Discovering Structure in Multiple Learning Tasks: The TC Algorithm, ICML, 1996. (Stefan, 4/29)
3. N. Cristianini, J. Kandola, A. Elisseeff, and J. Shawe-Taylor, On Kernel Target Alignment, JMLR. (Thorsten, 5/1)
4. T. Jaakkola and D. Haussler. Exploiting generative models in discriminative classifiers, NIPS, 1998. (Joshua, 5/1)

Other topics:

1. B. Schölkopf, J. Platt, J. Shawe-Taylor, A. J. Smola, and R. C. Williamson. Estimating the support of a high-dimensional distribution. Technical Report 99-87, Microsoft Research, 1999. To appear in Neural Computation, 2001.
   and  
   Ben-Hur et al., Support Vector Clustering. JMLR, 2, 2001.
2. A. J. Smola and B. Schölkopf. A tutorial on support vector regression. NeuroCOLT Technical Report NC-TR-98-030, Royal Holloway College, University of London, UK, 1998. To appear in Statistics and Computing, 2001. (pages 1-14 only) (Jingbo, 4/24)
3. B. Schölkopf, A. Smola, K. Müller, Kernel Principal Component Analysis, in:  B. Scholkopf, C. Burges, and A. Smola, editors, Advances in Kernel Methods --- Support Vector Learning. MIT Press, Cambridge, MA, 1999. 327 -- 352. Short version or chapter in Support Vector Learning  for background. (Liviu, 4/17)
4. John Platt, Large-Margin DAGs for Multi-Class Classification, NIPS 2000. (Alex, 4/15)