提出可大幅降低适应性、同时保持最优查询量的分区学习算法。
Learning Partitions with Optimal Query and Round Complexities
- 通过多轮非自适应查询，实现查询复杂度与轮数的精确权衡。
- 仅用 $O(\log \log n)$ 轮即可达到 $O(nk)$ 最优查询量。
- 适用于减少交互次数的聚类、主动学习与众包场景。
研究将 $n$ 个元素划分为至多 $k$ 个集合的未知分区问题，使用能揭示小子集信息的简单查询。经典成对同集合查询中，非自适应算法需 $Θ(n^2)$ 查询，自适应算法需 $Θ(nk)$，且最佳算法仅需 $k-1$ 轮。本工作给出确定性查询复杂度在轮数 $r$ 下的完整刻画：对任意常数 $r$，查询复杂度为 $Θ(n^{1+\frac{1}{2^r-1}}k^{1-\frac{1}{2^r-1}})$。所提算法仅需 $O(\log \log n)$ 轮即达最优 $O(nk)$ 查询量。进一步推广至大小不超过 $s$ 的子集查询：弱查询返回交集类数，强查询返回子集内完整划分。对于非自适应算法，强查询至少需 $Ω(n^2/s^2)$ 次；而弱查询存在算法在 $s \leq \sqrt{n}$ 时达到该下界（对数因子内）。整体上，对基于子集查询的算法，给出了轮数 $r$ 与查询大小 $s$ 的近似紧界。
原文摘要 · Abstract (English)
We consider the basic problem of learning an unknown partition of $n$ elements into at most $k$ sets using simple queries that reveal information about a small subset of elements. Our starting point is the well-studied pairwise same-set queries which ask if a pair of elements belong to the same class. It is known that non-adaptive algorithms require $Θ(n^2)$ queries, while adaptive algorithms require $Θ(nk)$ queries, and the best known algorithm uses $k-1$ rounds. This problem has been studied extensively over the last two decades in multiple communities due to its fundamental nature and relevance to clustering, active learning, and crowd sourcing. In many applications, it is of high interest to reduce adaptivity while minimizing query complexity. We give a complete characterization of the deterministic query complexity of this problem as a function of the number of rounds, $r$, interpolating between the non-adaptive and adaptive settings: for any constant $r$, the query complexity is $Θ(n^{1+\frac{1}{2^r-1}}k^{1-\frac{1}{2^r-1}})$. Our algorithm only needs $O(\log \log n)$ rounds to attain the optimal $O(nk)$ query complexity. Next, we consider two generalizations of pairwise queries to subsets $S$ of size at most $s$: (1) weak subset queries which return the number of classes intersected by $S$, and (2) strong subset queries which return the entire partition restricted on $S$. Once again in crowd sourcing applications, queries on large sets may be prohibitive. For non-adaptive algorithms, we show $Ω(n^2/s^2)$ strong queries are needed. Perhaps surprisingly, we show that there is a non-adaptive algorithm using weak queries that matches this bound up to log-factors for all $s \leq \sqrt{n}$. More generally, we obtain nearly matching upper and lower bounds for algorithms using subset queries in terms of both the number of rounds, $r$, and the query size bound, $s$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。