Points (2, 2) and (3, 3) are labelled positive, points (0, 1) and (1, 0) negative. Give the maximum margin separating hyperplane, the width of its margin, and name the support vectors.

Points (2, 2) and (3, 3) are labelled positive, points (0, 1) and (1, 0) negative. Give the maximum margin separating hyperplane, the width of its margin, and name the support vectors.

Approach: The maximum margin separator is the perpendicular bisector of the shortest segment between the two convex hulls, so find the closest pair of hull points first and use the symmetry of the configuration.

The hyperplane is x_1 + x_2 = 2.5 with margin width 3/sqrt(2) = 2.121, and the support vectors are (2, 2), (0, 1) and (1, 0). The convex hull of the negatives is the segment joining (0, 1) and (1, 0), which lies on x_1 + x_2 = 1, and the hull of the positives is the segment joining (2, 2) and (3, 3), whose nearest point is (2, 2) on x_1 + x_2 = 4. The direction (1, 1)/sqrt(2) is normal to both supporting lines, so the gap between them along that normal is (4 - 1)/sqrt(2) = 2.121, and the maximum margin separating hyperplane bisects it at x_1 + x_2 = 2.5. The point (3, 3) is not a support vector because moving it further out changes nothing. Scaling to the canonical form w^T x + b with functional margin 1 gives w = (2/3, 2/3) and b = -5/3, since the margin equals 2/||w||.

Follow-up: Add a positive point at (0.5, 0.5) so the sets are no longer separable. What does the soft margin solution do, and how does the penalty C decide it?

Key concepts: separating hyperplane, margin, support vectors, convex hull.