Minimax Gaussian Classification & Clustering
Minimax Gaussian Classification & Clustering
复制标题
极小极大高斯分类
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Pradeep Ravikumar
中科院分区：
文献类型：
--
作者：
Tianyang Li;Xinyang Yi;C. Caramanis;Pradeep Ravikumar
在协变量取自两个各向同性高斯分布的情况下，我们给出了分类和聚类误差的极小极大界。在这里，我们以区别的方式定义了聚类误差，展示了分类(有监督)和聚类(无监督)之间的基本联系。对于分类和聚类，我们的下界表明，在没有足够的样本的情况下，任何分类器或聚类规则所能做的最好的事情就是接近随机猜测。对于分类，作为我们上界分析的一部分，我们证明了Fiser线性判别式在足够样本n的情况下达到了快速的极小极大比率Θ(1/n)。对于聚类，作为我们上界分析的一部分，我们证明了利用主成分分析构造的聚类规则在足够样本的情况下达到了极小极大比率。我们还给出了高维稀疏设置的下界和上界，在高维稀疏设置中，协变量p的维度可能大于样本数n，但高斯均值之间的差异是稀疏的。
We present minimax bounds for classification and clustering error in the setting where covariates are drawn from a mixture of two isotropic Gaussian distributions. Here, we define clustering error in a discriminative fashion, demonstrating fundamental connections between classification (supervised) and clustering (unsupervised). For both classification and clustering, our lower bounds show that without enough samples, the best any classifier or clustering rule can do is close to random guessing. For classification, as part of our upper bound analysis, we show that Fisher’s linear discriminant achieves a fast minimax rate Θ(1/n) with enough samples n. For clustering, as part of our upper bound analysis, we show that a clustering rule constructed using principal component analysis achieves the minimax rate with enough samples. We also provide lower and upper bounds for the high-dimensional sparse setting where the dimensionality of the covariates p is potentially larger than the number of samples n, but where the difference between the Gaussian means is sparse.