标题： 图中单音半空间的学习与压缩的高效算法 显示英文标题

标题： Efficient Algorithms for Learning and Compressing Monophonic Halfspaces in Graphs

摘要： 抽象的凸性概念在图的顶点上，以及相应的半空间概念，最近引起了机器学习社区的关注。 在本工作中，我们研究了单路径半空间，这是一种通过诱导路径下的闭包定义的图半空间概念。 我们的主要结果是一个基于$2$可满足性的分解定理，该定理允许将单路径半空间表示为某些顶点子集的不相交并集。 利用此分解，我们实现了各种学习问题的高效且（几乎）最优的算法，例如教学、主动学习和在线学习。 最显著的是，我们得到了一个经验风险最小化的多项式时间算法。 独立于分解定理，我们得到了一个高效、稳定且正确的样本压缩方案。 这使得在可实现的 PAC 设置中，单路径半空间能够被正确学习器以线性误差率$1/\varepsilon$高效学习。 我们的结果回答了文献中的开放问题，并与测地线半空间形成了鲜明对比，因为对于测地线半空间来说，上述大部分学习问题都是 NP 难的。 显示英文摘要

摘要： Abstract notions of convexity over the vertices of a graph, and corresponding notions of halfspaces, have recently gained attention from the machine learning community. In this work we study monophonic halfspaces, a notion of graph halfspaces defined through closure under induced paths. Our main result is a $2$-satisfiability based decomposition theorem, which allows one to represent monophonic halfspaces as a disjoint union of certain vertex subsets. Using this decomposition, we achieve efficient and (nearly) optimal algorithms for various learning problems, such as teaching, active, and online learning. Most notably, we obtain a polynomial-time algorithm for empirical risk minimization. Independently of the decomposition theorem, we obtain an efficient, stable, and proper sample compression scheme. This makes monophonic halfspaces efficiently learnable with proper learners and linear error rate $1/\varepsilon$ in the realizable PAC setting. Our results answer open questions from the literature, and show a stark contrast with geodesic halfspaces, for which most of the said learning problems are NP-hard.