COLT

Note: Slides will be updated every week

Final Exam: January 12^th

Assignment 2: Deadline December 29^th

· What is learning? What is Learning? Learning from examples, Proper Learning, Non-Proper Learning, Rays, Halfspace, Threshold

· Learning From Examples, Term, Duality, DNF, CNF, Monotone-DNF, k-DNF, k-term DNF, Compressed hypothesis, Polygon.

· Composition Theorem, RO-DNF, Formula, MFormula, DFA, Decision List, k-DL, Decision Tree, Quasi-polynomial time and Sub-exponential time learning.

· Online Learning, Exact learning, Term, Duality, Composition, WINNOW, Decision List, Decision Tree, Halving, Perceptron, Text Classification, Expert Advice.

· PAC Learning, Definitions, Rays, OCCAM, Term, k-DNF, k-term DNF

· PAC learning, Markov, Chebychev, Sauer, Shatter Coefficient, VCdim, epsilon-net, OCCAM

· Boosting, Chernoff, applications, Weak learning, Boosting, Ada Boost.

Lecture Notes

Lecture Notes

Books and Lecture Notes

Preliminaries

Introduction to Probability

Advance Probability

VCdim and Sauer Lemma, Net and Sample (under construction)

COLT Models

Our COLT Story.

What is COLT for me?

Learning Models

Classes of Functions

Boolean Functions, DNF, CNF, Decision Tree (DT), Decision List (DL)

DT DNF and DL, DFAutomata (DFA), Multiplicity Automata (MA)

Online Learning

Online Learning

Online, Halving, MTerm, Composition Thm., k-CNF, k-term DNF

XOR, Decision List, Decision Tree, DNF, WINNOW

Results in other Online Learning Models (under construction)

PAC Learning

The PAC Model (under construction)

Simple Learning Algorithms

Learning using Divide and Conquer (under construction)

Exact Learning from Membership and Equivalence Queries

Monotone Theory

Learning CDNF, Decision Tree, O(log n)-term DNF

Multiplicity Automata (under construction)

Exact Learning from Membership Queries

Learning From Membership Queries (under construction)

Relationship between Models

CH=PAC (under construction)

Hardness Results

Learning Read Thrice DNF (under construction)

References (under construction)

Advance Course of COLT

• Exact Learning Decision Tree and CDNF
• Nader H. Bshouty: Exact Learning Boolean Function via the Monotone Theory. Information and Computation 123(1): 146-153 (1995)
• Exact Learning Decision Tree and Multivariate Polynomial and Disjoint DNF
• Amos Beimel, Francesco Bergadano, Nader H. Bshouty, Eyal Kushilevitz, Stefano Varricchio: Learning functions represented as multiplicity automata. JACM 47(3): 506-530 (2000)
• Nader H. Bshouty, Christino Tamon, David K. Wilson: Learning Matrix Functions over Rings. Algorithmica 22(1/2): 91-111 (1998)
• PAC learning with Membership queries Decision Tree with Fourier
• Eyal Kushilevitz, Yishay Mansour: Learning Decision Trees Using the Fourier Spectrum. SIAM J. Comput. 22(6): 1331-1348 (1993). Presentation.
• Nathan Linial, Yishay Mansour, Noam Nisan: Constant Depth Circuits, Fourier Transform, and Learnability. JACM 40(3): 607-620 (1993)
• Y. Mansour. Learning Boolean Functions via the Fourier Transform. In ``Theoretical Advances in Neural Computation and Learning", (V.P. Roychodhury and K-Y. Siu and A. Orlitsky, ed.), 391--424 (1994).
• Boosting and PAC learning with Membership queries DNF
• Jeffrey C. Jackson: An Efficient Membership-Query Algorithm for Learning DNF with Respect to the Uniform Distribution. JCSS 55(3): 414-440 (1997). Presentation on Learnin, Presentation on Boosting, Summary on Learning and Boosting.

The Seminar

Latex

Example of Latex file, How to change it to .ps and .pdf file, The pdf file

Using Chernoff

Papers

Papers