研究无限图的统计学习，揭示了可学习性的核心条件。
On statistical learning of graphs
- 通过有限顶点置换构造图类，分析其学习性质
- 证明有限支持图类可学习等价于自同构平凡性
- 将无限图分为四类，用集合论与计算理论刻画复杂度
我们研究由可数无限图 G 的顶点置换生成的假设类在 PAC 学习和在线学习下的可学习性。这些假设类对应于已知结构和标签集的图标记学习问题。考虑仅移动有限个顶点的置换所生成的类。主要结果表明：所有此类有限支持图类的 PAC 可学习性，蕴含整个同构类型 G 的在线可学习性，且等价于自同构平凡性条件。我们还利用无限随机图扩展性质的弱化形式，刻画了仅交换两个顶点所生成的图类不可学习的情形。此外，对任意图 G 及 k>2，k-顶点置换情形的可学习性等价于 2-顶点置换情形，由此得到无限图的四类划分，并借助描述集合论与可计算性理论工具确定了其复杂度。
原文摘要 · Abstract (English)
We study PAC and online learnability of hypothesis classes formed by copies of a countably infinite graph G, where each copy is induced by permuting G's vertices. This corresponds to learning a graph's labeling, knowing its structure and label set. We consider classes where permutations move only finitely many vertices. Our main result shows that PAC learnability of all such finite-support copies implies online learnability of the full isomorphism type of G, and is equivalent to the condition of automorphic triviality. We also characterize graphs where copies induced by swapping two vertices are not learnable, using a relaxation of the extension property of the infinite random graph. Finally, we show that, for all G and k>2, learnability for k-vertex permutations is equivalent to that for 2-vertex permutations, yielding a four-class partition of infinite graphs, whose complexity we also determine using tools coming from both descriptive set theory and computability theory.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。