Joint algorithm for sampling and optimization and natural language processing applications of same

A non-transitory storage medium storing instructions executable by an electronic data processing device to perform a method comprising:

• performing rejection sampling to acquire at least one accepted sample of a function or distribution p over a space X;
• during the rejection sampling, refining a proposal distribution q(n) used in the rejection sampling responsive to rejection of a sample x*εX obtained in a current iteration of the rejection sampling to generate a refined proposal distribution q(n+1) for use in a next iteration of the rejection sampling wherein the refined proposal distribution q(n+1) is selected to satisfy the criteria:
• p(x)≦q(n+1)(x)≦q(n)(x) for all xεX;
• and
• q(n+1)(x*)<q(n)(x*)
• wherein the method performed by executing the stored instructions further includes:
• initializing the proposal distribution q(0)=G for the first iteration of the rejection sampling where G denotes a probabilistic context-free grammar and the space X is a space of natural language derivations;
• and
• generating the function or distribution p as an intersection of G and a weighted finite state automaton (WFSA) representing a language model so that the performed rejection sampling acquires at least one accepted sample of a weighted context-free grammar comprising the intersection of the probabilistic context-free grammar G and the WFSA representing the language model.