Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

Maximum Margin Separations in Finite Closure Systems

: Seiffahrt, Florian; Horvárth, Tamás; Wrobel, Stefan


Hutter, Frank:
Machine Learning and Knowledge Discovery in Databases. European Conference, ECML PKDD 2020. Proceedings. Pt.I : Ghent, Belgium, September 14-18, 2020
Cham: Springer Nature, 2021 (Lecture Notes in Artificial Intelligence 12457)
ISBN: 978-3-030-67657-5 (Print)
ISBN: 978-3-030-67658-2 (Online)
European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD) <2020, Online>
Bundesministerium für Bildung und Forschung BMBF (Deutschland)
01/S18038C; ML2R
Deutsche Forschungsgemeinschaft DFG
Germany's Excellence Strategy; EXC 2070 - 390732324
Fraunhofer IAIS ()
closure systems; maximum margin separations; Monotone linkages; binary classification

Monotone linkage functions provide a measure for proximities between elements and subsets of a ground set. Combining this notion with Vapniks 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. In addition to binary classification of finite subsets of the Euclidean space, we considered also the problem of vertex classification in graphs. Our experimental results 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.