2020/01/13 by Florian Seiffarth, Tamás L. Horváth, Seiffarth, Florian +3 · 2 citations
Computer Science · #Advanced Algebra and Logic #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Rough Sets and Fuzzy Logic
paper · pdf · doi:10.48550/arxiv.2001.04417
openalex publication_date 2020/01/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.