论文标题
产品分布混合物的来源识别
Source Identification for Mixtures of Product Distributions
论文作者
论文摘要
我们提供了一种算法，用于识别$ n $ bits $ k $产品分布的混合物。这是许多应用程序的机器学习中的一个基本问题。我们的算法使用$ 2^{o（k^2）} n^{o（k）} $ arithmetic Operations识别可识别混合物的源参数（例如输入）多线性矩的近似值（例如，从足够大的样本中得出）。我们的结果是第一个明确绑定了此类混合物源识别的计算复杂性。运行时间改善了Feldman，O'Donnell和Serveio（Focs 2005）和Chen and 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^{O(k^2)} n^{O(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).
