SVM by Sequential Minimal Optimization (SMO)Quick ReviewQuick Review (Continued)Recall Full FormulationIntuitive Introduction to SMOAn Old Slide: Perceptron as ClassifierCorresponding Use in PredictionFrom Perceptron Rule to SMO RuleFirst of Two Other ChangesSecond of Two Other ChangesUpdating Two ’s: One SMO StepKarush-Kuhn-Tucker (KKT) ConditionsSMO AlgorithmAt End of Each Step, Need to Update bDerivation of SMO Update RuleExpressing Objective in Terms of One Lagrange Multiplier OnlyFind Minimum of this ObjectiveFinishing UpSlide 19SVM by Sequential Minimal Optimization (SMO)Algorithm by John PlatLecture by David PageCS 760: Machine LearningQuick Review•Inner product (specifically here the dot product) is defined as •Changing x to w and z to x, we may also write: or or wTx or w x•In our usage, x is feature vector and w is weight (or coefficient) vector•A line (or more generally a hyperplane) is writen as wTx = b, or wTx - b = 0•A linear separator is writen as sign(wTx - b)Quick Review (Continued)•Recall in SVMs we want to maximize margin subject to correctly separating the data… that is, we want to:•Here the y’s are the class values (+1 for positive and -1 for negative), so says xi correctly labeled with room to spare •Recall is just wTwRecall Full Formulation•As last lecture showed us, we can–Solve the dual more efficiently (fewer unknowns)–Add parameter C to allow some misclassifications–Replace xiTxj by more more general kernel termIntuitive Introduction to SMO•Perceptron learning algorithm is essentially doing same thing – find a linear separator by adjusting weights on misclassified examples•Unlike perceptron, SMO has to maintain sum over examples of example weight times example label•Therefore, when SMO adjusts weight of one example, it must also adjust weight of anotherAn Old Slide:Perceptron as Classifier•Output for example x is sign(wTx)•Candidate Hypotheses: real-valued weight vectors w•Training: Update w for each misclassified example x (target class t, predicted o) by:–wi wi + (t-o)xi–Here is learning rate parameter•Let E be the error o-t. The above can be rewriten as w w – x•So final weight vector is a sum of weighted contributions from each example. Predictive model can be rewriten as weighted combination of examples rather than features, where the weight on an example is sum (over iterations) of terms –Corresponding Use in Prediction•To use perceptron, prediction is wTx - b. May treat -b as one more coefficient in w (and omit it here), may take sign of this value•In alternative view of last slide, prediction can be writen as or, revising the weight appropriately, •Prediction in SVM is:b - x)(xTj'ijab - x)(xTiijjayFrom Perceptron Rule to SMO Rule•Recall that SVM optimization problem has the added requirement that:•Therefore if we increase one  by an amount  , in either direction, then we have to change another by an equal amount in the opposite direction (relative to class value). We can accomplish this by changing: w w – x also viewed as:   – y to: 1 1 – y1 or equivalently: 1 1 + y1 We then also adjust 2 so that y11 + y22 stays sameFirst of Two Other Changes•Instead of or some similar constant, we set   or more generally •For a given difference in error between two examples, the step size is larger when the two examples are more similar. When x1 and x2 are similar, K(x1,x2) is larger (for typical kernels, including dot product). Hence the denominator is smaller and step size is larger.201212211 21xxxxxx ),(2),(),(1212211 xxKxxKxxK Second of Two Other Changes•Recall our formulation had an additional constraint:•Therefore, we “clip” any change we make to any  to respect this constraint•This yields the following SMO algorithm. (So far we have motivated it intuitively. Afterward we will show it really minimizes our objective.)Updating Two ’s: One SMO Step•Given examples e1 and e2, set where:•Clip this value in the natural way: if y1 = y2 then:• otherwise:•Set where s = y1y2Karush-Kuhn-Tucker (KKT) Conditions•It is necessary and sufficient for a solution to our objective that all ’s satisfy the following:•An  is 0 iff that example is correctly labeled with room to spare•An  is C iff that example is incorrectly labeled or in the margin•An  is properly between 0 and C (is “unbound”) iff that example is “barely” correctly labeled (is a support vector)•We just check KKT to within some small epsilon, typically 10-3SMO Algorithm•Input: C, kernel, kernel parameters, epsilon•Initialize b and all ’s to 0•Repeat until KKT satisfied (to within epsilon):–Find an example e1 that violates KKT (prefer unbound examples here, choose randomly among those)–Choose a second example e2. Prefer one to maximize step size (in practice, faster to just maximize |E1 – E2|). If that fails to result in change, randomly choose unbound example. If that fails, randomly choose example. If that fails, re-choose e1.–Update α1 and α2 in one step–Compute new threshold bAt End of Each Step, Need to Update b•Compute b1 and b2 as follows•Choose b = (b1 + b2)/2•When α1 and α2 are not at bound, it is in fact guaranteed that b = b1 = b2Derivation of SMO Update Rule•Recall objective function we want to optimize:•Can write objective as: where: Starred values are from end of previous roundα1 with everybody elseα2 with everybody elseall the other α’sExpressing Objective in Terms of One Lagrange Multiplier Only•Because of the constraint , each update has to obey: where w is a constant and s is y1y2•This lets us express the objective function in terms of α2 alone:Find Minimum of this Objective•Find extremum by first derivative wrt α2:•If second derivative positive (usual case), then the minimum is where (by simple Algebra, remembering ss =