Lecture outline• Support vector machinesSupport Vector Machines• Find a linear hyperplane (decision boundary) that will separate the dataSupport Vector Machines• One Possible SolutionB1Support Vector Machines• Another possible solutionB2Support Vector Machines• Other possible solutionsB2Support Vector Machines• Which one is better? B1 or B2?• How do you define better?B1B2Support Vector Machines• Find hyperplane maximizes the margin => B1 is better than B2B1B2b11b12b21b22marginSupport Vector MachinesB1b11b120bxw1bxw1bxw1bxw if11bxw if1)(xf2||||2 MarginwSupport Vector Machines• We want to maximize:– Which is equivalent to minimizing:– But subjected to the following constraints:• This is a constrained optimization problem– Numerical approaches to solve it (e.g., quadratic programming)2||||2 Marginw1bxw if11bxw if1)(iiixf2||||)(2wwLSupport Vector Machines• What if the problem is not linearly separable?Support Vector Machines• What if the problem is not linearly separable?– Introduce slack variables• Need to minimize:• Subject to: iiii1bxw if1-1bxw if1)(ixfNikiCwwL122||||)(Nonlinear Support Vector Machines• What if decision boundary is not linear?Nonlinear Support Vector Machines• Transform data into higher dimensional
View Full Document