The following relates to the statistical sampling arts, Monte Carlo sampling arts, Markov Chain Monte Carlo sampling arts, computational design and analysis arts, and so forth, and to arts employing same such as machine translation, natural language processing, and so forth.
Statistical or Monte Carlo sampling employs random sampling of a domain to estimate a distribution, to obtain samples in (approximate) accordance with a distribution, to compute an integral, or to generate some other result of interest. In Markov Chain Monte Carlo (MCMC) approaches, a Markov chain of samples is constructed over a chain length sufficient to converge to an equilibrium result. For example, in a “random walk” MCMC approach, the chain is constructed by moving in a random direction from a currently accepted sample to a next sample. The result generated by a random walk MCMC approach can be adversely impacted by the choice of starting point for the random walk, which can lead to slow convergence or to convergence to a local extremum.
In Metropolis-Hasting (MH) MCMC approaches, the random walk is replaced by sampling in accordance with a normalized “proposal” distribution that is chosen such that the domain is readily sampled in accordance with the proposal distribution. In MH sampling, the Markov chain is constructed as follows: given a currently accepted sample, a new sample is chosen in accordance with the proposal distribution. If the new sample satisfies an acceptance criterion then it becomes the next accepted sample in the chain; otherwise, the currently accepted sample is repeated in the chain. In probabilistic sampling applications, the acceptance criterion is suitably embodied as a target distribution (not necessarily normalized) and the acceptance or rejection is performed on a statistical basis in accordance with the target distribution, for example by comparing the target distribution value at the node with a value drawn from a uniform probability. The MH approach eliminates dependence on the starting point of the sampling and, for a suitable choice of the proposal distribution, can ensure convergence to the globally optimal result in the limit. However, a poor choice for the proposal distribution can still lead to slow convergence, and there may be no suitable basis for choosing a “good” proposal distribution that ensures suitably fast convergence.
For example, consider MH sampling guided by an unnormalized target distribution that determines whether a sample is accepted or rejected. (Said another way, the acceptance criterion is statistical in nature and is defined by the unnormalized target distribution). Here, the convergence rate is typically controlled by the similarity (or dissimilarity) of the proposal distribution to the target distribution, as this determines how frequently samples generated by the proposal distribution are accepted by the target distribution. If the proposal distribution differs significantly from the target distribution then the MH sampling may become “trapped” for extended periods at a currently accepted sample, as the proposal distribution has difficulty proposing a new sample that is “acceptable” to the target distribution. In practice, however, it can be difficult to design a normalized proposal distribution that is sufficiently similar to the unnormalized target distribution to provide fast convergence.
In independent MH sampling, the proposal distribution is independent of the last accepted sample. In generalized MH sampling, the proposal distribution is conditioned on the last accepted sample. The generalized MH sampling is thus in a sense “closer” to the random walk MCMC approach, insofar as the next sample has some dependency on the last accepted sample. Accordingly, generalized MH sampling is also sometimes referred to as random walk MH sampling. The generalized MH sampling approach can improve convergence since the conditioning upon the last accepted sample tends to increase similarity between the conditional proposal distribution and the unnormalized target distribution. However, as with random walk MCMC, conditioning the proposal distribution on the last accepted sample can lead to undesirable dependence of the result on the starting point. Moreover, even with conditioning on the last accepted sample, the proposal distribution may still have substantial dissimilarity from the target distribution leading to slow convergence of the generalized MH sampling.
The following sets forth improved methods and apparatuses.