A Phase Transition-Based Perspective on Multiple Instance Kernels

Romaric Gaudel, LRI; Univ. Paris-Sud, CNRS; F-91405 Orsay / ENS Cachan, France
Michèle Sebag, LRI; Univ. Paris-Sud, CNRS; F-91405 Orsay / INRIA Futurs; projet TAO, Bât. 490, F-91405 Orsay, France
Antoine Cornuéjols, AgroParisTech; UMR MIA 518; F-75005 Paris, France

This paper is concerned with Relational Support Vector Machines, at the intersection of Support Vector Machines (SVM) and Inductive Logic Programming or Relational Learning. The so-called phase transition framework, primarily developed for constraint satisfaction problems (CSP), has been extended to relational learning, providing relevant insights into the limitations and difficulties thereof. The goal of this paper is to examine relational SVMs and specifically Multiple Instance Kernels along the phase transition framework; a specific CSP formalization for multiple instance problems, inspired by chemometry applications, is proposed. Ample empirical evidence based on a set of order parameters shows the existence of an unsatisfiability region for standard MIP-SVM approaches. A statistical analysis for these findings is proposed, establishing a lower bound of the generalization error depending on the satisfiability probability.