《Foundation of Machine Learning [Part05]》.pdf

Foundations of Machine Learning Lecture 5 Mehryar Mohri Courant Institute and Google Research mohri@cims.nyu.edu Kernel Methods Motivation Non-linear decision boundary. Efficient computation of inner products in high dimension. Flexible selection of more complex features. Mehryar Mohri - Foundations of Machine Learning page 3 This Lecture Definitions SVMs with kernels Closure properties Sequence Kernels Negative kernels Mehryar Mohri - Foundations of Machine Learning page 4 Non-Linear Separation Linear separation impossible in most problems. Non-linear mapping from input space to high- dimensional feature space: Φ : X → F . Generalization ability: independent of dim(F ), depends only on ρ and m . Mehryar Mohri - Foundations of Machine Learning page 5 Kernel Methods Idea: • DefineK : X ×X →R , called kernel, such that: Φ(x) · Φ(y) = K (x, y). • K often interpreted as a similarity measure. Benefits: • Efficiency: K is often more efficient to compute than Φ and the dot product. • Flexibility:K can be chosen arbitrarily so long as the existence of Φ is guaranteed (Mercer’s condition). Mehryar Mohri - Foundations of Machine Learning page 6 Mercer’s Condition (Mercer, 1909) Theorem: Let X ×X be a compact subset of RN and letK : X ×X →R be in L∞ (X ×X ) and symmetric. Then, K admits a uniformly convergent expansion ∞ K (x, y) = an φn (x)φn (y),