Efficient Algorithms for Learning and Compressing Monophonic Halfspaces in Graphs
This solves open problems in graph-based machine learning by providing efficient learning methods for monophonic halfspaces, contrasting with NP-hard results for geodesic halfspaces, benefiting researchers in computational learning theory.
The paper tackles the problem of learning monophonic halfspaces in graphs by developing a decomposition theorem based on 2-satisfiability, enabling efficient algorithms for teaching, active, online learning, and empirical risk minimization in polynomial time, with a linear error rate of 1/ε in the PAC setting.
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.