Course Content by Lecture (Syllabus)

• Bayesian Decision Theory: Bayes rule, Bayes decision principle, maximum-likelihood (ML), maximum-a-posteriori (MAP), independence constraints, density estimation, incremental Bayes.
• Maximum Likelihood/ Maximum Entropy Duality: ML and empirical distribution, relative entropy, Boltzmann-Gibbs distribution, Maximum Entropy and ML/MaxEnt Duality.
• The EM Algorithm - ML over Mixture of Distributions: mixture of binomial distributions, derivation of EM for general data, the EM rule for i.i.d. data, the coins example, mixture of normal distributions, the "bag of words" application.
• Support Vector Machines and Kernel Functions: 2-class classification, separating hyperplane with maximal margin, derivation of SVM, SVM with Kernels, primer on constrained optimization.
• Spectral Analysis I: PCA, LDA, CCA. Principle Component Analysis (PCA), multi-class learning using Linear Discriminant Analysis (LDA) and Canonical Correlation Analysis (CCA).
• Spectral Analysis II: Clustering. K-means, Min-cut, Ratio-cut, Normalized-cut.
• The Formal (PAC) Learning Model: The formal learning model, the "rectangle learning problem", Learnability of Finite Concept Classes (realizable and unrealizable cases).
• VC Dimension: definition and examples of VC-dimension, VC-dim and PAC learning, growth function Sauer's lemma.
• Generalization theorems: A Polynomial Bound on the Sample Size m for PAC Learning, the double-sampling theorem.