Maximum Margin Separations in Finite Closure Systems

Author: F. Seiffarth, T. Horvath, S. Wrobel
Journal: ECML PKDD 2020: Machine Learning and Knowledge Discovery in Databases
Year: 2020

Citation information

F. Seiffarth, T. Horvath, S. Wrobel,
ECML PKDD 2020: Machine Learning and Knowledge Discovery in Databases,
Springer, Cham,

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.