• English
  • Deutsch
  • Log In
    Password Login
    Research Outputs
    Fundings & Projects
    Researchers
    Institutes
    Statistics
Repository logo
Fraunhofer-Gesellschaft
  1. Home
  2. Fraunhofer-Gesellschaft
  3. Konferenzschrift
  4. Learning Weakly Convex Sets in Metric Spaces
 
  • Details
  • Full
Options
September 10, 2021
Conference Paper
Title

Learning Weakly Convex Sets in Metric Spaces

Abstract
We introduce the notion of weak convexity in metric spaces, a generalization of ordinary convexity commonly used in machine learning. It is shown that weakly convex sets can be characterized by a closure operator and have a unique decomposition into a set of pairwise disjoint connected blocks. We give two generic efficient algorithms, an extensional and an intensional one for learning weakly convex concepts and study their formal properties. Our experimental results concerning vertex classification clearly demonstrate the excellent predictive performance of the extensional algorithm. Two non-trivial applications of the intensional algorithm to polynomial PAC-learnability are presented. The first one deals with learning k-convex Boolean functions, which are already known to be efficiently PAC-learnable. It is shown how to derive this positive result in a fairly easy way by the generic intensional algorithm. The second one is concerned with the Euclidean space equipped with the Manhattan distance. For this metric space, weakly convex sets form a union of pairwise disjoint axis-aligned hyperrectangles. We show that a weakly convex set that is consistent with a set of examples and contains a minimum number of hyperrectangles can be found in polynomial time. In contrast, this problem is known to be NP-complete if the hyperrectangles may be overlapping.
Author(s)
Stadtländer, Eike
Universität Bonn
Horvath, Tamas  
Fraunhofer-Institut für Intelligente Analyse- und Informationssysteme IAIS  
Wrobel, Stefan  
Fraunhofer-Institut für Intelligente Analyse- und Informationssysteme IAIS  
Mainwork
Machine Learning and Knowledge Discovery in Databases. Research Track. European Conference, ECML PKDD 2021. Proceedings. Pt.II  
Project(s)
ML2R  
PhenoRob - Robotik und Phänotypisierung für Nachhaltige Nutzpflanzenproduktion  
Funding(s)
Exzellenzcluster (ExStra)
Funder
Bundesministerium für Bildung und Forschung -BMBF-
Deutsche Forschungsgemeinschaft -DFG-, Bonn  
Conference
European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD) 2021  
DOI
10.24406/publica-r-412787
10.1007/978-3-030-86520-7_13
File(s)
Download (660.9 KB)
Language
English
Fraunhofer-Institut für Intelligente Analyse- und Informationssysteme IAIS  
Keyword(s)
  • abstract convexity

  • Concept learning

  • vertex classification

  • Cookie settings
  • Imprint
  • Privacy policy
  • Api
  • Contact
© 2024