Course Web Page (this page):
http://www.eecs.tufts.edu/comp/150CLT/
Syllabus:
Description:
Can machines learn? And what exactly do we mean by this question? This
course is concerned with formal models of machine learning, the
computational problems associated with such models, their feasibility and
complexity, and efficient algorithms for them. Several aspects and models
will be studied including: learning as on-line prediction, learning in
probabilistic settings, learning from noisy (corrupted) data, and learning
by asking questions. For each of these we will have well defined criteria
of A successful learning, and study the algorithmic questions: can this be
done? And what are good algorithms for the task? Topics will include
foundational results as well as recent developments and their impact in
applications thereby providing a good grounding in the field.
Prerequisites:
Math 22 and Comp 160 or similar background. Some knowledge
of probability theory (e.g. from math 161). Comp 170 is also helpful but
not required. the course requires an aptitude for mathematical analysis,
writing proofs etc.; where needed additional relevant background will be
introduced.
Class Times:
Tuesday, Thursday 4:00-5:15 Halligan H-106
Instructor:
Roni Khardon
Office: Halligan 230
Office Hours: Tuesday 1:15-2:55, Thursday 9:30-10:50 or by appointment
Phone: 1-617-627-5290
Fax: 1-617-627-3220
Dept.: 1-617-627-3217
Email: roni@cs.tufts.edu
Teaching Assistant:
Julie Weber
Email: jweber@cs.tufts.edu
Office Hours: Tue, Thu 3-4 in Halligan 127 (Conference room)
Course Work and Marking
The course mark will be determined as follows:
-
Homework assignments (50%): we will have 4-6 assignments each will
include several problems and will typically have a 2 week deadline.
Assignments involve problem solving and/or mathematical analysis and
typically require more than one session to complete. It is highly
recommended to start early on these so that you have sufficient time
to think about the problems.
-
Presentations (20%): each student will pick 1-3 articles from a set of
options, read those, give a presentation in class (about 25 minutes),
and write a 1-2 page report/summary/evaluation.
More information will be available around the middle of the semester.
-
Class Participation (10%)
-
Mini-exams/Quizzes (20%): we will have 3 quizzes in class, each about 25
minutes. The dates are: 2/12, 3/16, 4/29. Quizzes will test for
general understanding and familiarity with concepts and techniques
rather than problem solving.
Collaboration:
Please consult the University guidelines on plagiarism for general
information. The problems assigned in this course typically require a
good amount of thought and typically cannot be done in one sitting. In
this process you are allowed to dicsuss ideas and approches with other
students and well as the instructor and TA.
You should not share complete solutions with other students or obtain
such solutions in any other way.
Additionally, any such level of
exchange of ideas should be clearly stated on the assignment.
In any case
I expect you to do your own work and write it up yourself.
Textbooks and Material Covered
Much of the material will be taken from the first text and I recommend
purchasing it.
Some material from the second text will be covered.
Other material will be taken from article and notes that will be provided.
The other books may give you a slightly different perspective on the
same material so it may be useful to have a look.
All the texts are on reserve in the library.
-
M.J. Kearns and U.V. Vazirani.
An Introduction to Computational Learning Theory ,
MIT Press, Cambridge, MA, 1994.
-
N. Cristianini and J. Shawe-Taylor.
An introduction to support vector machines : and other kernel-based
learning methods. Cambridge University Press, 2000.
-
M. Anthony and N. Biggs.
Computational Learning Theory,
Cambridge University Press, 1992.
-
B. K. Natarajan.
Machine Learning: A Theoretical Approach ,
Morgan Kaufmann, San Mateo, CA, 1991.
Class Handouts
Additional Articles and Pointers
-
Many resources, papers, pointers for
Computational Learning Theory
-
Many resources, papers, pointers for
Kernel Methods and SVM
-
Many resources, papers, pointers for
Boosting
-
Papers from COLT 2003
-
Papers from COLT 2002
-
Efficiency versus Convergence of Boolean Kernels for On-Line
Learning Algorithms
Khardon, Roth Servedio.
Neural Information Processing Systems (NIPS) 2001.
-
Yoav Freund and Robert E. Schapire. A decision-theoretic
generalization of on-line learning and an application to boosting.
Journal of Computer and System Sciences, 55(1):119-139, 1997.
Available on
Schapire's Boosting site.
-
Learning Conjunctions of Horn Clauses ,
D. Angluin, M. Frazier and L. Pitt,
Machine Learning Vol. 9, pp. 147-164, 1992.
Homework Assignments