Optimization and Machine Learning

Instructor: Chih-Jen Lin, Room 413, CSIE building.
The best way to contact me is via e-mails.
TA: Wei-Sheng Chin d01944006 at csie and Chien-Chih Wang d98922007 at ntu.edu.tw (TA hour: Tuesday 9am-12pm in lab 528)
Your HW/exam scores
Time: Monday 10:20-13:10, room 104, CSIE building
We have a 20-minute break at around 11:30. So we will finish at 13:00.
No course on Sep 14 and and Nov 16 (out of the country). To make it up, starting on Sep 21, we will reduce the 20-minute break to 10 minutes
This course will be taught in English. We will use slides as well as the blackboard. You are assumed to take notes.
Textbook:
- First part: Convex Optimization by Boyd and Vandenberghe
  Slides are available at the book web site.
  We will cover the following slides. This may be tentative. Please check this web page before printing your slides.
  - Chap 1: 1-2, 4-8, 14-15
  - Chap 2: 1-14, 16-20
  - Chap 3: 1-4, 7-10, 12-16, 19, 21-23, 26-27
  - Chap 4: 1-13, 17-18, 22-25, 35-43
  - Chap 5: 1-5, 8-13, 15-19, 24-30
  - Chap 7: 1-6
  - Chap 8: 8-14. We will also use some SVM slides here
  - Chap 10: 1-23
  - Chap 11: 1-3, 6-8
  - Slides here for implementing large-scale logistic regression. See also HW descriptions in this set of slides
FAQ of this course is here

Course Outline

Optimization techniques are used in all kinds of machine learning problems because in general we would like to minimize the testing error. This course will contain two parts. The first part focuses on convex optimization techniques. We discuss methods for least-squares, linear and quadratic programs, semidefinite programming, and others. We also touch theory behind these methods (e.g., optimality conditions and duality theory). In the second part of this course we will investigate how optimization techniques are applied to various machine learning problems (e.g., SVM, maximum entropy, conditional random fields, sparse reconstruction for signal processing applications). We further discuss that for different machine learning applications how to choose right optimization methods.

Course Objective

Learn how to use optimization techniques for solving machine learning problems.
Convex set, Convex function
Linear, quadratic programming
Convex optimization
Duality
Unconstrained minimization
Equality constrained minimization
SVM
Maximum entropy, CRF
Applications

Homework

Once every two weeks. Please write your homework/reports in English. For late homework, the score will be exponentially decreased. See FAQ about how to submit your homework.

HW1: 2.3, 2.10, 2.12, due on Oct 5.
HW2: 2.17(b), 3.1(a), 3.7, due on Oct 19.
HW3: 3.29, 3.44, 4.5, due on Nov 2.
HW4: 4.13, 4.38, due on Nov 23.
HW5: 5.1, 5.19(a)-(b), 5.22(a)-(b), due on Dec 7
HW6: 7.1, 8.23, 9.1, due on Dec 28
HW7: large-scale logistic regression implementation. See slides. Due on Jan 11.

Exams

You can bring notes and the textbook. Other books or electronic devices are not allowed. Please note that the mid-term exam will take 2 hours. We will then have a 1-hr lecture on the same day

Midterm 1: Oct 26 (week 7)
Midterm 2: Dec 7 (week 13)
Final: Jan 11 (week 18)

Sample exams in the past: exam1, exam2, exam3.

For midterms, discussions will be in the following week. For the Final exam, it will be at 12pm on January 15 (room 104, CSIE building).

Grading

30% homework, 70% Exam. (tentative)

Some (usually 10%) may fail if they don't work hard.

FAQ

Last modified: