Maximum margin classification based on flexible convex hulls

• A flexible convex hull is defined in this work for the class region approximation.
• Maximum margin classification based on flexible convex hulls (MMC-FCH) is proposed in this work.
• MMC-FCH approximates each class region with a flexible convex hull.
• MMC-FCH finds an optimal separating hyperplane by solving a closest pair of points problem.

Based on defining a flexible convex hull, a maximum margin classification based on flexible convex hulls (MMC-FCH) is presented in this work. The flexible convex hull defined in our work is a class region approximation looser than a convex hull but tighter than an affine hull. MMC-FCH approximates each class region with a flexible convex hull of its training samples, and then finds a linear separating hyperplane that maximizes the margin between flexible convex hulls by solving a closest pair of points problem. The method can be extended to nonlinear case by using the kernel trick, and multi-class classification problems are dealt with by constructing binary pairwise classifiers as in support vector machine (SVM). The experiments on several databases show that the proposed method compares favorably to the maximum margin classification based on convex hulls (MMC-CH) or affine hulls (MMC-AH).