Instance Based Approximations to Profile Maximum Likelihood
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
The Bethe and Sinkhorn Permanents of Low Rank Matrices and Implications for Profile Maximum Likelihood
In this paper we consider the problem of computing the likelihood of the profile of a discrete distribution, i.e., the probability of observing the multiset of element frequencies, and computing a profile maximum likelih…
A Unified Maximum Likelihood Approach for Estimating Symmetric Properties of Discrete Distributions
Symmetric distribution properties such as support size, support coverage, entropy, and proximity to uniformity, arise in many applications. Recently, researchers applied different estimators and analysis tools to de…
AllComposite Likelihood Estimation for Restricted Boltzmann machines
Learning the parameters of graphical models using the maximum likelihood estimation is generally hard which requires an approximation. Maximum composite likelihood estimations are statistical approximations of the maximu…
A new adjusted maximum likelihood method for the Fay–Herriot small area model
In the context of the Fay–Herriot model, a mixed regression model routinely used to combine information from various sources in small area estimation, certain adjustments to a standard likelihood (e.g., profile, residu…
regressionDeterministic Approximate EM Algorithm; Application to the Riemann Approximation EM and the Tempered EM
The Expectation Maximisation (EM) algorithm is widely used to optimise non-convex likelihood functions with latent variables. Many authors modified its simple design to fit more specific situations. For instance, the Exp…