8. Assume our hypothesis class is the set of lines, and we use a line to separate the positive and negative examples, instead of bounding the positive exam- ples as in a rectangle, leaving the negatives outside (see figure 2.13). Show that the VC dimension of a line is 3. D Œ X1 Figure 2.13 A line separating positive and negative instances. 9. Show that the VC dimension of the triangle hypothesis class is 7 in two di- mensions. (Hint: For best separation, it is best to place the seven points equidistant on a circle.) 10. Assume as in exercise 8 that our hypothesis class is the set of lines. Write down an error function that not only minimizes the number of misclassifica- tions but also maximizes the margin. 11. One source of noise is error in the labels. Can you propose a method to find data points that are highly likely to be mislabeled?

8. Assume our hypothesis class is the set of lines, and we use a line to separate the positive and negative examples, instead of bounding the positive exam- ples as in a rectangle, leaving the negatives outside (see figure 2.13). Show that the VC dimension of a line is 3. D Œ X1 Figure 2.13 A line separating positive and negative instances. 9. Show that the VC dimension of the triangle hypothesis class is 7 in two di- mensions. (Hint: For best separation, it is best to place the seven points equidistant on a circle.) 10. Assume as in exercise 8 that our hypothesis class is the set of lines. Write down an error function that not only minimizes the number of misclassifica- tions but also maximizes the margin. 11. One source of noise is error in the labels. Can you propose a method to find data points that are highly likely to be mislabeled?