Support Vector Machines and Boosting

Support Vector Machines In SVMs we are trying to find a decision boundary that maximizes the "margin" or the "width of the road" separating the positives from the negative training data points. To find this we minimize: subject to the constraints The resulting Lagrange multiplier equation we try to optimize is: Solving the above Lagrangian optimization problem will give us w, b, and alphas, parameters that determines a unique maximal margin (road) solution. On the maximum margin "road", the +ve, and -ve points that stride the "gutter" lines are called support vectors. The decision boundary lies at the middle of the road. The definition of the "road" is dependent only on the support vectors, so changing (adding deleting) non-support vector points will not change the solution. Note, that widest "road" is a 2D concept. If the problem is in 3D we want the widest region bounded by two planes; in even higher dimensions, a subspace bounded by two hyperplanes. s in general requires numerical optimization methods that Solving for the Lagrange multiplier are beyond the scope of this class. In practice, you use Quadratic Programming solvers. A popular algorithm for solving SVMs is Platt's SMO (Sequential Minimal Optimization) algorithm. For SVM problems on quizzes, we generally just ask you to solve for the values of w, b and alphas using algebra and/or geometry. Useful Equations for solving SVM questions A. Equations derived from optimizing the Lagrangian: 1. Partial of the Lagrangian wrt to b: From Note that and for non-support vectors. Sum of all alphas (support vector weights) with their signs should add to 0. 2. Partial of the Lagrangian wrt to w: From For when using a linear kernel. The summation only contains support vectors. Support vectors are training data points with For when using a decomposable kernel (see definition below). Sum of alphas, ys of support vectors wrt to vector w. B. Equations from the boundaries and constraints: 3. The Decision boundary: 1 General form, for any kernel. To classify an unknown , we compute the kernel function against each of the support vectors . Support vectors are training data points with For when using a linear kernel 4. Positive gutter: General form, for any kernel. For use when the Kernel is linear. 5. Negative gutter: 6. The width of the margin (or road): where, Alternate formula for the two support vector case: This equation is useful when solving SVM problems in 1D or 2D, where the width of the road can be visually determined. Common SVM Kernels: Linear Kernel In document classification, feature vectors are composed of binary word features: I(word=foo) outputs 1 if the word "foo" appears in the document 0 if it does not. Each document is represented as |vocabulary| length feature vectors. Support vectors found are generally particularly salient documents (documents best at discriminating topics being classified). 2 Decomposable Kernels Idea: Define that transforms input vectors into a different (usually higher) dimensional space where the data is (more easily) linearly separable. Example: n>1 Example: Quadratic Kernel: ● Polynomial Kernel ● In 2D resulting decision boundary can look parabolic, linear or hyperbolic depending on which terms in the expansion dominate. Here is an expansion of the quadratic kernel, with u = [x, y] HW: Try this Kernel using Professor Winston's demo Radial Basis Function (RBF) or Gaussian Kernel ● ● Will fit almost any data. May exhibit overfitting when used improperly. Similar to KNN but with all points having a vote; weight of each vote determined by Gaussian ❍ Points farther away get less of a vote than points In 2D generated decision boundaries resemble contour circles around clusters of +ve and -ve points. Support vectors are generally +ve or ve points that are closest to the opposing cluster. The contour space drawn results from sum of support vector Gaussians. HW: Try this Kernel using Professor Winston's demo is large you get flatter Gaussians. When is small you get When sharper Gaussians. (Hence when using a small contour density will appear closer / denser around support vector points). Here is the Kernel in-2D expanded out, with u = [x, y] As a point gets closer to a support vector it approaches exp(0) = 1. As a point moves far away from a support vector it approaches exp(infinity) = 0. 3 nearby Sigmoidal (tanh) Kernel ● Allows for combination of linear decision boundaries Properties of tanh: ● ● ● ● Similar to the sigmoid function Ranges from -1 to +1. tahn(x) => +1 when x >> 0 tahn(x) => -1 when x << 0 Resulting decision boundaries are logical combinations of linear boundaries. Not too different from second layer neurons in Neural Nets. Like RBF, may exhibit overfitting when improperly used. Linear combination of Kernels Idea: Kernel functions are closed under addition and scaling (by a positive number). Scaling: for a > 0 or Linear combination: a,b>0 Method 1 of Solving SVM parameters by inspection: This is a step-by-step solution to Problem 2.A from 2006 quiz 4: and points on the x-y axis; We are given the following graph with +ve point at x1 (0, 0) and a -ve point x2 at (4, 4). Can a SVM separate this? i.e. is it linearly separable? Heck Yeah! using the line above. Part 2A: Provide a decision boundary: We can find the decision boundary by graphical inspection. 1. The decision boundary lies on the line: y = -x + 4 2. We have a +ve support vector at (0, 0) with line equation y = -x 3. We have a -ve support vector at (4, 4) with line equation y = - x + 8 4 Given the equation for the decision boundary, we next massage the algebra to get the decision boundary to conform with the desired form, namely: 1. 2. (< because +ve is below the line) 3. (multiplied by -1) 4. (writing out the coefficients explicitly) Now we can read the solution from the equation coefficients: w1 = -1 w2 = -1 b=4 Next, using our formula for width of road, we check that these weights gives a road width of: . WAIT! This is clearly not the width of the "widest" road/margin. We remember that any multiple c (c>0) of the boundary equation is still the same decision boundary. So all equations of the form: Strides this decision boundary. w1 = -c or w2 = -c So here is a more general solution: b = 4c and Using The Width of the Road Constraint Graphically we see that the widest width margin should be: and intercept can be solved by solving for c constrained by the The solution weight vector known width-of-the-road. Length of in terms of c: Now plugin all this into the margin width equation and solving for c, we get: => => => This means the true weight vector and intercept for the SVM solution should be: and Next we solve for alphas, using the w vector and equation 1. Plugin in the vector values of support vectors and w: We get two identical equations: 5 or Using Equation 1, now we can solve for the other alpha: Part 2B: Does the boundary change if a +ve point x3 is added at (-1, -1)? No. Support vectors are still at 1, and 2. Decision boundary stays the same. Part 2C: What if point x2 (-ve) is moved to coordinate (k, k)? values change, increase, decrease or stay same? When k = 2? and k = 8? How will Answer: Go back to how we solved for alphas: Plugin in x2 Solving for or Using the fact that , . and width-of-road/margin We express alpha in terms of the margin m: Answer: ● When k changes from 4 to 2. The margin (road width) m is halved and k is also halved. So alpha must increase by a factor of 4. ● When k changes from 4 to 8. The margin m is doubled, k is also doubled. So alpha must decrease by a factor of 4. Though we do not provide a full proof here. Alpha in generally changes inversely with m. Widen road -> lower alpha. Narrowed road -> higher alpha Method 2: Solving for alpha, b, and w without visual inspection (By computing Kernels and solving Constraint equations) Example from 2005 Final Exam. In this problem you are told that you have the following points. -ve points: +ve points: A at (0, 0) C at (2, 0) B at (1, 1) and that these points lie on the gutter in the SVM max-margin solution. Step 1. Compute all kernels function values, which in this case, these are all dot products. K(A, A) = 0*0+0*0 = 0 K(A, B) = 0*1+0*1 = 0 K(A, C) = 0*2+0*0 = 0 K(B, A) = 1*0+1*0 = 0 K(B, B) = 1*1+1*1 = 2 K(B, C) = 1*2+1*0 = 2 K(C, A) = 2*0+0*0 = 2 K(C, B) = 2*1+0*1 = 2 K(C, C) = 2*2+0*0 = 4 6 Step 2: Write out the system of equations, using SVM constraints: Constraint 1: , Constraint 2: positive gutter. Constraint 3: negative gutter. This will yield 4 equations. C1 C3.A C3.B C2.C -1 -1 1 yAK(A, yBK(B, ycK(C, A)=1*0=0 A)=1*0=0 A)= +1*2=2 yAK(A, yBK(B, ycK(C, B)=1*0=0 B)=1*2=-2 B)= +1*2=2 yAK(A, yBK(B, ycK(C, C)=1*0=0 C)=1*2=-2 C)= +1*4=4 0 0 + 1 -1 + 1 -1 + 1 +1 For clarity here are the four equations: C1 C3.A C3.B C2.C Step 3: Use your favorite method of solving linear equations to solve for the 4 unknowns. Answer: This is a more general way to solve SVM parameters, without the help of geometry. This method can be applied to problems where "margin" width or boundary equation can not be derived by inspection. (e.g. > 2D) NOTE: We used the gutter constraints as equalities above because we are told that the given points lie on the "gutter". More realistically, if we were given more points, and not all points lay on the gutters, then we would be solving a system of inequalities (because the gutter equations are really constraints on >= 1 or <= -1). In the quadratic programming solvers used to solve SVMs, we are in fact doing just that, we are minimizing a target function by subjecting it to a system of linear inequality constraints. Example of SVMs with a Non-Linear Kernel From Part 2E of 2006 Q4. You are given the graph below and the following kernel: and you are asked to solve for equation for the decision boundary. 7 Step 1: First, decompose the kernel into a dot product of functions: Answer: Step 2: Convert all our original points into the new space using the transform. (We are going from 2D to 1D). Positive points are at: Negative points are at: Step 3: Plot the points in the new space, this appears as a line from 0 to 8. With positive points at 0, 2, 4 and negative points at 6, 8. The support vectors lie between and (between values of 4 and 6) Hence the decision boundary (maximum margin) should be: The < due to the positive points being all less than 5. Expanding the determined decision boundary in terms of components of x, we get: Square both sides: 8 Convert to (standard form): This is a circle with radius 9 An Abstract Lesson on Support Vector Behavior Suppose you have the above set of points. Let's solve the SVM parameters by inspection. 1. Boundary equation: => => 2. Read off the and b and multiply by c (c>0): 3. Now apply the width of the road/margin constraint: plugging in in length of w, and solving for c: => 4. Now we have the SVM optimal solutions to w and b: 5. Next, solve for the using the two lagrangian equations: and a) From expanding the first equation, we get: which leads to two equations: or and or b) From expanding the second equation , we get: or c) Putting the equations from a) and b) together we can solve for the other two alphas. or and similarly for We see that the two +ve support vector alphas are split based on the ratio of distances determined by s and t. If t = s were equal, then = = Observation A: Q: Suppose we moved point A to the origin at (0, 0). What happens to 10 and ? A: This configuration basically implies s = 0; so we get: and . now becomes the sole primary support vector because point A sits Conceptually, directly across from point B. Point A takes up all the share of the "pressure" in holding up the margin; point C, though still on the gutter, effectively becomes a non-support vector. So this implies that points on the gutter may not always serve the role of being a support vector. Observation B: Q: Suppose we changed k, by moving point B up/or down the y-axis what happens to the alphas? A: All the alphas are proportional to If k decreases, the road narrows, the alphas increases. apply more "pressure" to push the margin tighter. Analogy, the supports need to If k increases, the road widens, the alphas decrease. Analogy: wider road needs less "pressure" on the supports to hold it in place. 11 Boosting The main idea in Boosting is that we are trying to combine (or ensemble) of "weak" classifiers (classifiers that underfit the data) h(x) into a single strong classifier H(x). where: Each data point is weighed. . for . Weights are like probabilities, (0, 1], with But weights are never 0; this implies that all data points will have some vote at all times. Decision stump weights: Definition of Errors: In Boosting we always pick stumps with errors < 1/2. Because stumps with errors > 1/2 can always be flipped. Stumps with error = 1/2 are useless because they are no better than flipping a fair coin. and so => Therefore: . Adaboost Algorithm Input: Training data a weight for each data point. 1. Initialize 2. For s = 1 ... T: a. Train base learner using distribution on training data. Get a base (stump) that achieves the lowest (error). [Note in examples that we classifier are picked from a set of predefined stumps, this procedure of do in class, "picking" the best stump is the same as "training".] b. Compute the stump weight: c. Update weights (there are three ways to do this): ■ Original: (correct pts.) (incorrect pts.) ■ OR more human-friendly: (correct pts.) (incorrect pts.) (see derivation below) OR use numerator-denominator method (see below) 1. Output the final classifier: ■ 12 Possible Termination conditions: 1. Stop after T rounds (we manually set some T.) 2. Stop after H(x) (final classifier) has error = 0 on training data or < some error threshold. 3. Stop when you can't find any more stumps h(x) where weighted error is < 0.5. (i.e. All stumps have E = 0.5). The Numerator-Denominator method A calculator-free method for finding weight updates quickly Replace the Weight Update Step 1c above with these steps. 1. Write all weights in the form of where the denominator d is the same to all weights. 2. Circle the data points that are incorrectly classified. 3. Compute the new denominator for (the circled) incorrectly classified points: which is sum of all the incorrect numerators times two. Compute the new denominator for (uncircled) correct points: sum of all the correct numerators times two. 4. New weights are the old numerator divided by the updated denominators found in step 3. if incorrect if correct. 5. Adjust all the numerators and denominators such that the denominator is again the same for all weights. Optional: Check and make sure correct weights add up to 1/2, and incorrect weights also add up to 1/2. A Shortcut on computing the output of H(x). Quizzes often ask you for the Error of the final H(x) ensemble classifier on the training data. Here is a quick way to compute the output of H(x) without calculating logarithms. Step 1: compute the sign of each of stump h(x) on the given data point. Step 2: compute products of the log arguments of the +ve stumps and -ve stump. If If Example: suppose if is + and is + and is -ve (5 * 2) > 2 H(x) should output +ve 13 if is + and is - and is -ve 5 > (2 * 2) H(x) should output +ve. Step 3: Once you've computed all of the H(x) output values on the training data points, count the number of case where H(x) disagrees with the true output. That is the error. FAQ Dear TA, how do I determine if a stump will "never" be used (such as for part 1.A of 2006 Q4)? Test stumps that are never used are ones that make more errors than some pre-existing test stump. In other words, if the set of mistakes stump X makes is a superset of errors stump Y makes, then Error(X) > Error(Y) is always true, no matter what weight distributions we use. Hence we will always chose Y over X because it makes less errors. So X will never be used! Here is the answer to problem 1A from the 2006 Q4 with explanation. Setup: We are given the tests and the mistakes they make on the training examples, and we are asked to cross out the tests that are never used. Test Misclassified examples Never used? Reason? TRUE 1,2,3,5 Yes, superset of G=Y or U!=N FALSE 4,6 Yes, superset of U=M C=Y 1,6 No, C=N 2,3,4,5 Yes, superset of G=Y or U=M U=Y 1,2,3,6 Yes, superset of U!=N U!=Y 4,5 Yes, superset of G=Y or U=M U=N 4,5,6 Yes, superset of G=Y or U=M U!=N 1,2,3 No, U=M 4 No, U!=M 1,2,3,5,6 Yes, superset of G=Y, C=Y or U!=N G=Y 5 No, G=N 1,2,3,4,6 Yes, superset of U=M, C=Y or U!=N Food For thought: Suppose we were to come up with a strong classifier that is a uniform combination of stumps (equal weights). Q: How many mis-classifications would the following classifier commit? H(x) = h(FALSE) + h(C=Y) + h(U!=Y) A: Combining the misclassification sets of the stumps: {4, 6}, {1, 6}, {4, 5} Points 1, 5 will be misclassified by 1 stump and correctly classified by 2 stumps. So H(x) will be correct on 1, 5. Points 4, 6 will be misclassified by 2 stumps and correctly classified by 1 stump. So H(x) will misclassify 4, 6. Therefore the points H(x) will mis-classify will be {4, 6} 14 How many misclassifications would H(x) = h(U=M) + h(G=Y) + h(C=Y) make? (Optional 1) Derivation of the human-friendly weight update equations Here is how the original weight update equations for Adaboost was derived into the more human friendly version. The original Adaboost weight update equations were For correctly classified samples (we reduce their weight) For incorrectly classified samples (we increase their weight) Plug in alphas and redefine the exponential terms in terms of errors E: For correctly classified examples. For incorrectly classified examples. Next, plug in the normalization factor (derived in Prof. Winston's handout) Then simplifying gives us the: for correctly classified examples. for incorrectly classified samples. To check your answers. Always sum up weights (for correct or wrong weights), they must each add up to 1/2! (Optional 2) Proof of correctness of numerator-denominator method In this proof we use the short hand: In the procedure, we keep the numerator constant, only the denominator is updated during the weight update step from d to d'. Starting from the weight update equations (for correct points): 1. 2. 15 3. 4. 5. The proof for incorrect points will yield the same result. This shows that the denominator update rule used in step 3 can be derived directly from the weight update equations so it is correct. 16