Title: Approximate Profile Maximum Likelihood,
Abstract: We propose an efficient algorithm for approximate computation of the profile
maximum likelihood (PML), a variant of maximum likelihood maximizing the
probability of observing a sufficient statistic rather than the empirical
sample. The PML has appealing theoretical properties, but is difficult to
compute exactly. Inspired by observations gleaned from exactly solvable cases,
we look for an approximate PML solution, which, intuitively, clumps comparably
frequent symbols into one symbol. This amounts to lower-bounding a certain
matrix permanent by summing over a subgroup of the symmetric group rather than
the whole group during the computation. We extensively experiment with the
approximate solution, and find the empirical performance of our approach is
competitive and sometimes significantly better than state-of-the-art
performance for various estimation problems.