Maximal Closed Set and Half-Space Separations in Finite Closure Systems
This work addresses computational challenges in concept learning problems for researchers in machine learning and discrete mathematics, though it is incremental as it builds on existing closure system theory.
The paper tackles the NP-completeness of half-space separation in finite closure systems by proposing a relaxation to maximal closed set separation, solved by a greedy algorithm with a linear number of closure operator calls, and it shows this bound is sharp. It also characterizes Kakutani closure systems algorithmically and applies the framework to graphs and finite lattices.
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.