论文标题
学习低度超图
Learning Low Degree Hypergraphs
论文作者
论文摘要
我们研究了通过边缘检测查询学习超图的问题。在此问题中，学习者查询隐藏超图的顶点的子集，并观察这些子集是否包含边缘。通常，学习具有最大尺寸$ d $的$ m $边缘的超图需要$ω（（2m/d）^{d/2}）$查询。在本文中，我们旨在确定可以在不遭受查询复杂性的情况下学习的超图的家庭，该查询复杂性在边缘的大小上呈指数增长。 我们表明，使用Poly $（n）$ Queries可以学习高度匹配和低度近均匀的超图。对于学习超匹配（最大程度的超图$ 1 $），我们给出了$ O（\ log^3 n）$ - 圆形算法，并使用$ O（n \ log^5 n）$查询。我们通过表明没有算法的poly $（n）$查询来补充这种上限，这些算法在$ o（\ log \ log n）$自适应回合中学习超匹配。对于具有最高度$δ$和边缘尺寸比率$ρ$的超图，我们给出了一种非自适应算法，并使用$ o（（（2n）^{ρδ+1} \ log log^2 n）$查询。据我们所知，这些是使用Poly $（n，m）$查询复杂性的第一批算法，用于学习超恒定数量超恒定尺寸边缘的非平凡家族。
We study the problem of learning a hypergraph via edge detecting queries. In this problem, a learner queries subsets of vertices of a hidden hypergraph and observes whether these subsets contain an edge or not. In general, learning a hypergraph with $m$ edges of maximum size $d$ requires $Ω((2m/d)^{d/2})$ queries. In this paper, we aim to identify families of hypergraphs that can be learned without suffering from a query complexity that grows exponentially in the size of the edges. We show that hypermatchings and low-degree near-uniform hypergraphs with $n$ vertices are learnable with poly$(n)$ queries. For learning hypermatchings (hypergraphs of maximum degree $ 1$), we give an $O(\log^3 n)$-round algorithm with $O(n \log^5 n)$ queries. We complement this upper bound by showing that there are no algorithms with poly$(n)$ queries that learn hypermatchings in $o(\log \log n)$ adaptive rounds. For hypergraphs with maximum degree $Δ$ and edge size ratio $ρ$, we give a non-adaptive algorithm with $O((2n)^{ρΔ+1}\log^2 n)$ queries. To the best of our knowledge, these are the first algorithms with poly$(n, m)$ query complexity for learning non-trivial families of hypergraphs that have a super-constant number of edges of super-constant size.
