We propose a new method for estimating the density, or probability mass function (pmf), of a discrete random variable from a small sample. We focus on the observed counts - the number of times each value appears in the sample - and define the Maximum Likelihood Set (MLS) as the set of pmf's that put more mass on the observed counts than on any other set of counts possible for the same sample size. The MLS is a "diamond" - shaped subset of the probability simplex [0,1]k bounded by at most k x (k-1) hyper-planes, where k is the number of possible values of the random variable. The MLS contains the empirical distribution, as well as the family of add-. estimators for . < 1, obtained by adding the constant . to each count. In particular, the MLS contains the popular Laplace estimator (.=1).

We then select from the MLS the pmf that is "closest" to a fixed pmf that encodes prior knowledge. When using Kullback-Leibler distance for this selection, the optimization problem comprises .nding the minimum of a convex function over a domain de.ned by linear inequal-ities, for which standard numerical procedures are available. We instantiate this method in language modeling using Zipf's law to encode prior knowledge, (see figure). State-of-the-art results are then demonstrated.