2.1 Solving for Two Lagrange Multipliers In order to solve for the two Lagrange multipliers,SMO first computes the constraints on these multipliers and then solves for the constrained minimum.For convenience,all quantities that refer to the first multiplier will have a subscript 1,while all quantities that refer to the second multiplier will have a subscript 2.Because there are only two multipliers,the constraints can be easily be displayed in two dimensions(see figure 3).The bound constraints(9)cause the Lagrange multipliers to lie within a box,while the linear equality constraint(6)causes the Lagrange multipliers to lie on a diagonal line.Thus,the constrained minimum of the objective function must lie on a diagonal line segment(as shown in figure 3).This constraint explains why two is the minimum number of Lagrange multipliers that can be optimized:if SMO optimized only one multiplier,it could not fulfill the linear equality constraint at every step. The ends of the diagonal line segment can be expressed quite simply.Without loss of generality, the algorithm first computes the second Lagrange multiplier o and computes the ends of the diagonal line segment in terms of o2.If the target yi does not equal the target y2,then the following bounds apply to L=max(0,a,-a),H=min(C,C+a2). (13) If the target y equals the target y2,then the following bounds apply to L=max(0,a,+a-C),H=min(C,a,+a) (14) The second derivative of the objective function along the diagonal line can be expressed as: n=K(1,x1)+K(2,x2)-2K(1,x2) (15) Under normal circumstances,the objective function will be positive definite,there will be a minimum along the direction of the linear equality constraint,and n will be greater than zero.In this case,SMO computes the minimum along the direction of the constraint: "=g+2(E-E2) (16) n where E,=u,-y,is the error on the ith training example.As a next step,the constrained minimum is found by clipping the unconstrained minimum to the ends of the line segment: H if anew≥H; w.clipped if L<ag<H (17) L if ew≤L. Now,let s=yy2.The value of o is computed from the new,clipped,2: aew=a+s(a-awcipped ) (18) Under unusual circumstances,n will not be positive.A negative n will occur if the kernel K does not obey Mercer's condition,which can cause the objective function to become indefinite.A zero n can occur even with a correct kernel,if more than one training example has the same input >7 2.1 Solving for Two Lagrange Multipliers In order to solve for the two Lagrange multipliers, SMO first computes the constraints on these multipliers and then solves for the constrained minimum. For convenience, all quantities that refer to the first multiplier will have a subscript 1, while all quantities that refer to the second multiplier will have a subscript 2. Because there are only two multipliers, the constraints can be easily be displayed in two dimensions (see figure 3). The bound constraints (9) cause the Lagrange multipliers to lie within a box, while the linear equality constraint (6) causes the Lagrange multipliers to lie on a diagonal line. Thus, the constrained minimum of the objective function must lie on a diagonal line segment (as shown in figure 3). This constraint explains why two is the minimum number of Lagrange multipliers that can be optimized: if SMO optimized only one multiplier, it could not fulfill the linear equality constraint at every step. The ends of the diagonal line segment can be expressed quite simply. Without loss of generality, the algorithm first computes the second Lagrange multiplier α2 and computes the ends of the diagonal line segment in terms of α2. If the target y1 does not equal the target y2, then the following bounds apply to α2: L H = − = +− max( , ), 0 α 21 21 α min(C, ). C α α (13) If the target y1 equals the target y2, then the following bounds apply to α2: L = +− = + max( , ), min( , ). 0 α 21 21 α C H C α α (14) The second derivative of the objective function along the diagonal line can be expressed as: η =+− Kx x Kx x Kx x ( , ) ( , ) ( , ). rr rr rr 11 2 2 12 2 (15) Under normal circumstances, the objective function will be positive definite, there will be a minimum along the direction of the linear equality constraint, and η will be greater than zero. In this case, SMO computes the minimum along the direction of the constraint : α α η 2 2 new 21 2 = + yE E ( ) − , (16) where E u y iii = - is the error on the ith training example. As a next step, the constrained minimum is found by clipping the unconstrained minimum to the ends of the line segment: α α α α α 2 2 2 2 2 new,clipped new new new new if if L if = ≥ < < ≤ % & K ' K H H L H L ; ; . (17) Now, let s yy = 1 2 . The value of α1 is computed from the new, clipped, α2: α 1 1 22 α α α new new,clipped =+ − s( ). (18) Under unusual circumstances, η will not be positive. A negative η will occur if the kernel K does not obey Mercer’s condition, which can cause the objective function to become indefinite. A zero η can occur even with a correct kernel, if more than one training example has the same input