Source Identification for Mixtures of Product Distributions
Source Identification for Mixtures of Product Distributions
复制标题
DOI：
--
复制
发表时间：
2020-12
期刊：
影响因子：
--
通讯作者：
Spencer Gordon;Bijan Mazaheri;Y. Rabani;L. Schulman
中科院分区：
文献类型：
--
作者：
Spencer Gordon;Bijan Mazaheri;Y. Rabani;L. Schulman
我们给出了一种算法，用于对 n 位上的 k 个乘积分布的混合进行源识别。这是具有许多应用的机器学习中的一个基本问题。我们的算法使用 2 2)nO(k) 算术运算，识别可识别混合物的源参数，给定多线性矩的近似值（例如，从足够大的样本中导出）作为输入。我们的结果是对此类混合物源识别的计算复杂性的第一个明确限制。运行时间改进了 Feldman、O’Donnell 和 Servedio (FOCS 2005) 以及 Chen 和 Moitra (STOC 2019) 之前的结果，保证只学习混合物（没有源的参数识别）。我们的分析给出了 Tahmasebi、Motahari 和 Maddah-Ali (ISIT 2018) 可识别来源的定性特征的定量版本。
We give an algorithm for source identification of a mixture of k product distributions on n bits. This is a fundamental problem in machine learning with many applications. Our algorithm identifies the source parameters of an identifiable mixture, given, as input, approximate values of multilinear moments (derived, for instance, from a sufficiently large sample), using 2 2)nO(k) arithmetic operations. Our result is the first explicit bound on the computational complexity of source identification of such mixtures. The running time improves previous results by Feldman, O’Donnell, and Servedio (FOCS 2005) and Chen and Moitra (STOC 2019) that guaranteed only learning the mixture (without parametric identification of the source). Our analysis gives a quantitative version of a qualitative characterization of identifiable sources that is due to Tahmasebi, Motahari, and Maddah-Ali (ISIT 2018).