A Phase TRansition-Based Perspective on Multiple Instance Kernels

Romaric Gaudel 1, 2 Michèle Sebag 1, 2 Antoine Cornuéjols 3
2 TANC - Algorithmic number theory for cryptology
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France, X - École polytechnique, CNRS - Centre National de la Recherche Scientifique : UMR7161
Abstract : 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, originally developed for constraint satisfaction problems, has been extended to relational learning and it has provided relevant insights into the limitations and difficulties hereof. The goal of this paper is to examine relational SVMs and specifically Multiple Instance (MI) Kernels along the phase transition framework. A relaxation of the MI-SVM problem formalized as a linear programming problem (LPP) is defined and we show that the LPP satisfiability rate induces a lower bound on the MI-SVM generalization error. An extensive experimental study shows the existence of a critical region, where both LPP unsatisfiability and MI-SVM error rates are high. An interpretation for these results is proposed.
Type de document :
Communication dans un congrès
ILP 2007, Jun 2007, Corvallis, United States. 2007
Liste complète des métadonnées

Contributeur : Romaric Gaudel <>
Soumis le : jeudi 27 septembre 2007 - 15:37:58
Dernière modification le : jeudi 10 mai 2018 - 02:06:00
Document(s) archivé(s) le : jeudi 8 avril 2010 - 22:16:09


Fichiers produits par l'(les) auteur(s)


  • HAL Id : inria-00175300, version 1


Romaric Gaudel, Michèle Sebag, Antoine Cornuéjols. A Phase TRansition-Based Perspective on Multiple Instance Kernels. ILP 2007, Jun 2007, Corvallis, United States. 2007. 〈inria-00175300〉



Consultations de la notice


Téléchargements de fichiers