论文标题
基于实例的概述最大可能性的近似值
Instance Based Approximations to Profile Maximum Likelihood
论文作者
论文摘要
在本文中，我们提供了一种新的有效算法，用于近似计算曲线最大似然（PML）分布，这是对称属性估计中的突出数量。我们提供了一种算法，该算法匹配以前已知的有效算法，用于计算近似PML分布并改善当给定实例中不同观察到的频率的数量很小。我们通过在近似PML分布中利用新的稀疏结构并提供独立关注的新矩阵圆形算法来实现这一结果。利用这一结果，我们获得了伪模的第一个可证明的计算有效实现，这是估计一类广泛的对称属性的一般框架。此外，我们为具有小剖面熵的分布（一种基于自然实例的复杂度度量）获得了有效的基于PML的估计器。此外，我们提供了一种更简单，更实用的伪ML实现，该实现与此类估计量最著名的理论保证相匹配，并通过经验评估该方法。
In this paper we provide a new efficient algorithm for approximately computing the profile maximum likelihood (PML) distribution, a prominent quantity in symmetric property estimation. We provide an algorithm which matches the previous best known efficient algorithms for computing approximate PML distributions and improves when the number of distinct observed frequencies in the given instance is small. We achieve this result by exploiting new sparsity structure in approximate PML distributions and providing a new matrix rounding algorithm, of independent interest. Leveraging this result, we obtain the first provable computationally efficient implementation of PseudoPML, a general framework for estimating a broad class of symmetric properties. Additionally, we obtain efficient PML-based estimators for distributions with small profile entropy, a natural instance-based complexity measure. Further, we provide a simpler and more practical PseudoPML implementation that matches the best-known theoretical guarantees of such an estimator and evaluate this method empirically.
