解决高阶学习中非分块非广义可学习的判定问题
A packing lemma for VCN${}_k$-dimension and learning high-dimensional data
- 通过直接证明高阶版本的Haussler打包性质，建立学习性与组合维数的关系
- 证明非分块非广义高阶学习可实现当且仅当VCN_k维数有限
- 为图、超图等复杂结构的学习提供理论支撑，适合学习理论研究者
近期，作者提出了高阶PAC学习理论，适用于图、超图及关系结构的学习。在初始工作中，作者建立了高阶学习与组合维数——即Vapnik-Chervonenkis-Natarajan (VCN_k) k-维数之间的几乎完全对应关系，仅留下非分块、非广义高阶学习的刻画作为未解问题。本文通过证明非分块非广义高阶学习蕴含高阶版Haussler打包性质，进而推出VCN_k-维数的有限性，从而完成该问题的解答。这一结果基于经典PAC学习中经典打包性质可导出有限Natarajan维数的直接证明，并发现这些证明可自然推广至高阶情形。
原文摘要 · Abstract (English)
Recently, the authors introduced the theory of high-arity PAC learning, which is well-suited for learning graphs, hypergraphs and relational structures. In the same initial work, the authors proved a high-arity analogue of the Fundamental Theorem of Statistical Learning that almost completely characterizes all notions of high-arity PAC learning in terms of a combinatorial dimension, called the Vapnik--Chervonenkis--Natarajan (VCN${}_k$) $k$-dimension, leaving as an open problem only the characterization of non-partite, non-agnostic high-arity PAC learnability. In this work, we complete this characterization by proving that non-partite non-agnostic high-arity PAC learnability implies a high-arity version of the Haussler packing property, which in turn implies finiteness of VCN${}_k$-dimension. This is done by obtaining direct proofs that classic PAC learnability implies classic Haussler packing property, which in turn implies finite Natarajan dimension and noticing that these direct proofs nicely lift to high-arity.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。