Maximum Margin Separations in Finite Closure Systems

Monotone linkage functions provide a measure for proximities between elements and subsets of a ground set. Combining this notion with Vapnik’s idea of support vector machines, we extend the concepts of maximal closed set and half-space separation in finite closure systems to those with maximum margin. In particular, we define the notion of margin for finite closure systems by means of monotone linkage functions and give a greedy algorithm computing a maximum margin closed set separation for two sets efficiently. The output closed sets are maximum margin half-spaces, i.e., form a partitioning of the ground set if the closure system is Kakutani. We have empirically evaluated our approach on different synthetic datasets. The experiments concerning binary classification of finite point sets of the Euclidean space clearly show that the predictive performance of our algorithm is comparable to that of ordinary support vector machines. In addition to this classification task, we considered also the problem of vertex classification in graphs. Our results obtained for random trees and graphs provide clear evidence that maximal closed set separation with maximum margin results in a much better predictive performance than that with arbitrary maximal closed sets.