学习图中 Monophonic 半空间的高效算法

基于摘要分析。本文研究图顶点上的二分类问题，将分类器限制为 Monophonic 半空间，即满足特定抽象凸性条件的顶点划分。核心贡献是为这一概念类在监督、在线和主动学习设置下建立算法与复杂度保证，而非提出神经信号表征模型。 作者报告，借助 Monophonic 半空间的结构性质，并将一致性检查归约到 2-satisfiability，可以构造多项式时间的一致性检查算法。在被动学习设置下，作者证明可用关于顶点数 n=|V(G)| 的多项式时间，以近最优样本复杂度学习目标半空间；摘要未给出该样本复杂度的具体表达式。作者还报告了在线与主动学习设置下的类似结果，但具体保证尚未验证。 此外，作者证明该概念类能够以 poly(n) 的延迟逐一枚举，经验风险最小化可在 2^{ω(G)}poly(n) 时间内完成，其中 ω(G) 是图 G 的团数。因此，该经验风险最小化算法的时间界仍包含对团数的指数依赖，不能概括为对任意图均具有多项式时间保证。作者称这些结果回答了 González 等人于 2020 年提出的开放问题，并与 geodesic 半空间形成对照：后者的部分对应问题已被证明为 NP-hard，而非所有学习问题都不可解。 当前材料仅支持理论贡献分析，定理适用条件、近最优性的比较基准及完整证明尚未验证。摘要未提供 EEG/BCI 应用或明确的机制对应关系，因此不据此提出迁移效果或复现实验建议。