《Foundation of Machine Learning [Part07]》.pdfVIP

Foundations of Machine Learning Lecture 7 Mehryar Mohri Courant Institute and Google Research mohri@cims.nyu.edu On-Line Learning Mehryar Mohri - Foundations of Machine Learning page 2 Motivation PAC learning: • distribution fixed over time (training and test). • IID assumption. On-line learning: • no distributional assumption. • worst-case analysis (adversarial). • mixed training and test. • Performance measure: mistake model, regret. Mehryar Mohri - Foundations of Machine Learning page 3 This Lecture Prediction with expert advice Linear classification Mehryar Mohri - Foundations of Machine Learning page 4 General On-Line Setting For t =1 to T do • receive instance xt ∈ X. • predict yt ∈ Y. • receive label yt ∈ Y. incur loss L(y , y ). t t • Classification: Y = {0, 1}, L(y, y )= |y −y |. 2 Regression: Y ⊆R, L(y, y )=(y −y) . Objective: minimize total loss T L(y , y ). t=1 t t Mehryar Mohri - Foundations of Machine Learning page 5 Prediction with Expert Advice For t =1 to T do • receive instance xt ∈ X and advice yt,i ∈Y, i ∈ [1, N]. • predict yt ∈ Y. • receive label yt ∈ Y. incur loss L(y , y ). t t • Objective: minimize regret, i.e