《Foundation of Machine Learning [Part09]》.pdf

Foundations of Machine Learning Lecture 9 Mehryar Mohri Courant Institute and Google Research mohri@cims.nyu.edu Multi-Class Classification Mehryar Mohri - Foundations of Machine Learning page 2 Motivation Real-world problems often have multiple classes: text, speech, image, biological sequences. Algorithms studied so far: designed for binary classification problems. How do we design multi-class classification algorithms? • can the algorithms used for binary classification be generalized to multi-class classification? • can we reduce multi-class classification to binary classification? Mehryar Mohri - Foundations of Machine Learning page 3 Multi-Class Classification Problem Training data: sample drawn i.i.d. from set X according to some distribution D, S =((x , y ), . . . , (x , y )) ∈X ×Y, 1 1 m m • mono-label case: Card(Y )= k . • multi-label case:Y = {−1, +1}k. Problem: find classifier h : X → Y in H with small generalization error, • mono-label case:RD (h)=Ex∼D [1h(x)= f (x)] . multi-label case:RD (h)=Ex∼D 1 k 1[h(x)]k=[ f (x)]k . k l=1 • Mehryar Mohri - Foundations of Machine Learning page 4 Notes In most tasks, number of classes k ≤ 100. Fork large or infinite, problem often not treated as a multi-class classification problem, e.g., automatic speech recognition. Computational efficiency issues arise for larger ks. In general, classes not balanced. Mehryar Mohri - Foundations of Machine Learning page 5