用少量二分类器实现多分类，揭示分布式分类的理论极限
Fundamental limits of distributed multiclass classification from simple binary decisions
- 用O(log K)个超平面二分类器构建K类分类器
- 在高斯设定下给出性能上下界，验证了理论有效性
- 适合研究分布式学习与低维决策的学者参考
我们研究从O(log K)个简单二分类器组合构建K类分类器的根本性能极限，这是一种在分布式场景下通过各参与方执行简单任务来实现复杂分类的自然范式。当这些二分类器为超平面时，在一个简化高斯模型中——即K个类别中心是R^d中的独立高斯点，观测受高斯噪声污染——我们推导出多个解码和维度配置下的显式性能边界。大量模拟实验为所提出的理论结果提供了强有力的实证支持。
原文摘要 · Abstract (English)
We consider the problem of constructing a $K$-class classifier from the combination of $O(\log K)$ simple binary classifiers -- this is a natural paradigm to construct a sophisticated classifier in a distributed manner with each agent performing a relatively straightforward task. We study the fundamental performance limits of such a classifier when the corresponding binary classifiers are hyperplanes. For a stylized Gaussian setting where the $K$ class centers are independent Gaussian points in $\mathbb R^d$ and the observations are corrupted by Gaussian noise, we derive explicit performance bounds across several decoding and dimensional regimes. Extensive simulation experiments provide strong empirical validation of the presented theoretical results.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。