提出高效算法学习图上单音半空间，解决多个学习难题
Efficient Algorithms for Learning and Compressing Monophonic Halfspaces in Graphs
- 基于2-SAT分解，将单音半空间拆为顶点子集并集
- 实现多项式时间经验风险最小化与近似最优学习算法
- 适用于可实现PAC学习，对初学者友好
图论中的凸性概念及其对应的半空间近年来受到机器学习领域关注。本文研究通过诱导路径闭包定义的单音半空间。主要成果是基于2-SAT的分解定理，可将单音半空间表示为特定顶点子集的不相交并。利用该分解，实现了教学、主动和在线学习等多种学习问题的高效（近乎最优）算法。尤为关键的是，获得了经验风险最小化的多项式时间算法。独立于分解定理，还提出了高效、稳定且正确的样本压缩方案，使单音半空间在可实现PAC设定下能以线性误差率1/ε被正确学习。结果解答了文献中的开放问题，并与测地半空间形成鲜明对比——后者大多数学习问题均为NP难。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。