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, Polytechnique - X, 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 relational learning or Inductive Logic Programming (ILP). The so-called phase transition framework, primarily developed for constraint satisfaction problems (CSP), has been extended to ILP, providing relevant insights into the limitations and difficulties thereof. The goal of this paper is to examine relational SVMs and specifically Multiple Instance-SVMs in the phase transition perspective. Introducing a relaxed CSP formalization of MI-SVMs, we first derive a lower bound on the MI-SVM generalization error in terms of the CSP satisfiability probability. Further, ample empirical evidence based on systematic experimentations demonstrates the existence of a unsatisfiability region, entailing the failure of MI-SVM approaches.
Type de document :
Communication dans un congrès
Conférence francophone sur l'apprentissage automatique, Jul 2007, Grenoble, France. pp.173--186, 2007
Liste complète des métadonnées

https://hal.inria.fr/inria-00171406
Contributeur : Romaric Gaudel <>
Soumis le : mercredi 12 septembre 2007 - 12:38:59
Dernière modification le : jeudi 11 janvier 2018 - 06:22:14
Document(s) archivé(s) le : vendredi 9 avril 2010 - 02:02:38

Fichiers

CAP_07.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00171406, version 1

Citation

Romaric Gaudel, Michèle Sebag, Antoine Cornuéjols. A Phase Transition-based Perspective on Multiple Instance Kernels. Conférence francophone sur l'apprentissage automatique, Jul 2007, Grenoble, France. pp.173--186, 2007. 〈inria-00171406〉

Partager

Métriques

Consultations de la notice

567

Téléchargements de fichiers

180