Consider a binary classification problem in one-dimensional space where the sample contains four data points S=...

 

Transcribed Image Text:

Consider a binary classification problem in one-dimensional space where the sample contains four data points S= {(1,-1), (-1,-1), (2, 1), (-2,1)} as shown in Fig. 1. -3 I Figure 1: Red points represent instances from class +1 and blue points represent instances from class -1. a) Define H, = [t, o). Consider a class of linear separators H= {H: t R}, i.e., for VH H, H (x) = 1 if x t otherwise - 1. Is there any linear separator H EH that achieves O classification error on this sample? If yes, show one of the linear separators that achieves 0 classification error on this example. If not, briefly explain why there cannot be such linear separator. (10 points) b) Now consider a feature map : R R where p(x) = (x,x). Apply the feature map to all the instances in sample S to generate a transformed sample = {((x), y): (x,y) E S}. Let H = {ax + ax +c 0: a +b #03 be a collection of half-spaces in R. More specifically, Hab.c((x,x)) = 1 if ax + ax2 + c 0 otherwise -1. Is there any half-space that achieves 0 classification error on the transformed sample ? If yes, give the equation of the maxmargin linear separator and compute the corresponding margin. (10 points) c) What is the kernel corresponding to the feature map (.) in the last question, i.e., give the kernel function K(x,z): Rx R R. (10 points) Consider a binary classification problem in one-dimensional space where the sample contains four data points S= {(1,-1), (-1,-1), (2, 1), (-2,1)} as shown in Fig. 1. -3 I Figure 1: Red points represent instances from class +1 and blue points represent instances from class -1. a) Define H, = [t, o). Consider a class of linear separators H= {H: t R}, i.e., for VH H, H (x) = 1 if x t otherwise - 1. Is there any linear separator H EH that achieves O classification error on this sample? If yes, show one of the linear separators that achieves 0 classification error on this example. If not, briefly explain why there cannot be such linear separator. (10 points) b) Now consider a feature map : R R where p(x) = (x,x). Apply the feature map to all the instances in sample S to generate a transformed sample = {((x), y): (x,y) E S}. Let H = {ax + ax +c 0: a +b #03 be a collection of half-spaces in R. More specifically, Hab.c((x,x)) = 1 if ax + ax2 + c 0 otherwise -1. Is there any half-space that achieves 0 classification error on the transformed sample ? If yes, give the equation of the maxmargin linear separator and compute the corresponding margin. (10 points) c) What is the kernel corresponding to the feature map (.) in the last question, i.e., give the kernel function K(x,z): Rx R R. (10 points)