Maximal closed set and half-space separations in finite closure systems

DOI10.1016/J.TCS.2023.114105MaRDI QIDQ6093588zbMATH OpenOpenAlexFDO

Authors Florian Seiffarth, T. Horváth, Stefan Wrobel

Publication date 7 September 2023

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2001.04417

zbMATH Keywords

closure systemshalf-space separationmachine learning

Mathematics Subject Classification ID

Galois correspondences, closure operators (in relation to ordered sets) (06A15) Learning and adaptive systems in artificial intelligence (68T05)

Abstract: Several concept learning problems can be regarded as special cases of half-space separation in abstract closure systems over finite ground sets. For the typical scenario that the closure system is implicitly given via a closure operator, we show that the half-space separation problem is NP-complete. As a first approach to overcome this negative result, we relax the problem to maximal closed set separation, give a generic greedy algorithm solving this problem with a linear number of closure operator calls, and show that this bound is sharp. For a second direction, we consider Kakutani closure systems and prove that they are algorithmically characterized by the greedy algorithm. As a first special case of the general problem setting, we consider Kakutani closure systems over graphs and give a sufficient condition for this kind of closure systems in terms of forbidden graph minors. For a second special case, we then focus on closure systems over finite lattices, give an improved adaptation of the generic greedy algorithm, and present an application concerning subsumption lattices.

Recommendations

• Two basic algorithms in concept analysis
• Listing closed sets of strongly accessible set systems with applications to data mining
• Quasi-concave functions on meet-semilattices
• Closure systems and their structure
• On implicational bases of closure systems with unique critical sets.

Cites work

• A general set-separation theorem
• A Selection Theorem for Topological Convex Structures
• Axiomatic characterization of the interval function of a graph
• Binary Convexities and Distributive Lattices
• Convexity in graphs
• Convexity in Graphs and Hypergraphs
• Ein Beweis des Satzes von M. Eidelheit über konvexe Mengen
• Formal concept analysis. Foundations and applications.
• Foundations of inductive logic programming
• Geodesic Convexity in Graphs
• Graph theory
• scientific article; zbMATH DE number 5287125 (Why is no real title available?)
• scientific article; zbMATH DE number 1748069 (Why is no real title available?)
• scientific article; zbMATH DE number 1391397 (Why is no real title available?)
• scientific article; zbMATH DE number 3259770 (Why is no real title available?)
• scientific article; zbMATH DE number 3349329 (Why is no real title available?)
• scientific article; zbMATH DE number 3044485 (Why is no real title available?)
• Large margin classification using the perceptron algorithm
• Learning logic programs with structured background knowledge
• Maximal closed set and half-space separations in finite closure systems
• Monotone linkage clustering and quasi-concave set functions
• On maximal frequent and minimal infrequent sets in binary matrices
• On the computation of the hull number of a graph
• Partitioning a graph into convex sets
• Separation of two convex sets in convexity structures
• Separation properties of convexity spaces.
• Some Elementary Properties of Interval Convexities
• The duality between the anti-exchange closure operators and the path independent choice operators on a finite set
• The geodesic classification problem on graphs

Cited in

(8)

• Maximal point spaces of closed interval posets
• Enumeration of support-closed subsets in confluent systems
• scientific article; zbMATH DE number 4070867 (Why is no real title available?)
• scientific article; zbMATH DE number 6805978 (Why is no real title available?)
• On maximal weakly separated set-systems
• Maximal closed set and half-space separations in finite closure systems
• Half-space separation in monophonic convexity
• Learning weakly convex sets in metric spaces

This page was built for publication: Maximal closed set and half-space separations in finite closure systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6093588)