1 Support Vector Machine [20 points) In Figure la and Figure 1b, we are given some data points in 2-D space and we aim to train a hard margin linear SVM classifier. The positive data points (with "+" sign in the figure) are labeled as 1. The negative data points (with "-" sign in the figure) are labeled as-1. The length of each cell in the grid is 1. "(-3,2) x+ To, 21 # -2.0) 162,0) 112,0) (-2,-2) (a) Part A (b) Part B Figure 1: Problem 1: SVM 1) [8 points] For each case in Figure 1, circle the support vectors of your SVM classifier. What is the size of the margin of your SVM classifier in each case? 2) [6 points] Suppose we consider the data points shown in Figure 1a, but point x is moved from (-3,2) to (-2,2). Write down the (convex) primal optimization formulation for this problem. Write down the dual optimization formulation for this problem. 3) [6 points] Consider data points shown in Figure 2a, can you draw the decision boundary of your SVM classifier in this case? Suppose we add a new data sample at position (-3,5) (as shown in Figure 2b). How will the decision boundary change if we add this new data point? Newly added data points 41.4) 2.14) + |(2, 2) (2,211 lp,2) (2, 2) (2.2 p. 2) + + + (3,1) (3,1) 1-2,0) -2,0) (2.0) (2.0) x! 13,-2) (3.2) (a) before adding new data point (b) after adding new data points Figure 2: Problem 1: Adding a new point 1 Support Vector Machine [20 points) In Figure la and Figure 1b, we are given some data points in 2-D space and we aim to train a hard margin linear SVM classifier. The positive data points (with "+" sign in the figure) are labeled as 1. The negative data points (with "-" sign in the figure) are labeled as-1. The length of each cell in the grid is 1. "(-3,2) x+ To, 21 # -2.0) 162,0) 112,0) (-2,-2) (a) Part A (b) Part B Figure 1: Problem 1: SVM 1) [8 points] For each case in Figure 1, circle the support vectors of your SVM classifier. What is the size of the margin of your SVM classifier in each case? 2) [6 points] Suppose we consider the data points shown in Figure 1a, but point x is moved from (-3,2) to (-2,2). Write down the (convex) primal optimization formulation for this problem. Write down the dual optimization formulation for this problem. 3) [6 points] Consider data points shown in Figure 2a, can you draw the decision boundary of your SVM classifier in this case? Suppose we add a new data sample at position (-3,5) (as shown in Figure 2b). How will the decision boundary change if we add this new data point? Newly added data points 41.4) 2.14) + |(2, 2) (2,211 lp,2) (2, 2) (2.2 p. 2) + + + (3,1) (3,1) 1-2,0) -2,0) (2.0) (2.0) x! 13,-2) (3.2) (a) before adding new data point (b) after adding new data points Figure 2: Problem 1: Adding a new point