提出首个可证明最优的超树学习算法，适用于广泛场景。
Distance-based Learning of Hypertrees
- 基于最短路径查询，设计在线/离线最优算法
- 在有序超树上实现亚二次查询复杂度
- 适配进化树等距离退化场景，理论完备
我们研究通过最短路径查询（SP-queries）学习超图的问题，提出了首个针对一类广泛且自然的超树——有序超树——的可证明最优在线算法。该在线算法可转化为可证明最优的离线算法。有序超树位于数据库理论中已深入研究的环状超图的Fagin层级中，严格包含该层级中可实现亚二次SP查询复杂度的最广类别。考虑到某些场景（如进化树重建）中距离测量会随距离增大而退化，我们还考察了使用有界距离查询的学习模型，在此模型下，我们展示了对一般超树学习的渐近紧致复杂度界限。
原文摘要 · Abstract (English)
We study the problem of learning hypergraphs with shortest-path queries (SP-queries), and present the first provably optimal online algorithm for a broad and natural class of hypertrees that we call orderly hypertrees. Our online algorithm can be transformed into a provably optimal offline algorithm. Orderly hypertrees can be positioned within the Fagin hierarchy of acyclic hypergraph (well-studied in database theory), and strictly encompass the broadest class in this hierarchy that is learnable with subquadratic SP-query complexity. Recognizing that in some contexts, such as evolutionary tree reconstruction, distance measurements can degrade with increased distance, we also consider a learning model that uses bounded distance queries. In this model, we demonstrate asymptotically tight complexity bounds for learning general hypertrees.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。