论文标题
有限闭合系统中的最大闭合套件和半空间间隔
Maximal Closed Set and Half-Space Separations in Finite Closure Systems
论文作者
论文摘要
几个概念学习问题可以被视为在有限的地面组合中抽象封闭系统中半空间分离的特殊情况。对于典型的情况，即通过闭合操作员隐式给出闭合系统，我们表明半空间分离问题是NP完整的。作为克服这一负面结果的第一种方法，我们放宽了最大封闭设置分离的问题，通过线性闭合操作员调用，给出了一种通用的贪婪算法来解决此问题，并证明该界限很清晰。在第二个方向上，我们考虑了kakutani闭合系统，并证明它们是通过贪婪算法来表征的。作为一般问题设置的第一个特殊情况，我们将Kakutani封闭系统视为图表，并根据禁止的图形未成年人为这种封闭系统提供足够的条件。对于第二种特殊情况，我们将重点放在有限晶格上的封闭系统上，对通用贪婪算法进行改进的适应性，并提出有关集合晶格的应用程序。
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.
