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

摘要

In rejection sampling of a function or distribution p over a space X, a proposal distribution q⁽ⁿ⁾ is refined responsive to rejection of a sample x*εX to generate a refined proposal distribution q⁽ⁿ⁺¹⁾ selected to satisfy the criteria p(x)≦q⁽ⁿ⁺¹⁾(x)≦q⁽ⁿ⁾(x) and q⁽ⁿ⁺¹⁾(x*)q⁽ⁿ⁾(x*). In a sampling mode, the sample x* is obtained by random sampling of the space X, the rejection sampling accepts or rejects x* based on comparison of a ratio p(x*)/q(x*) with a random draw, and the refined proposal distribution q⁽ⁿ⁺¹⁾ is selected to minimize a norm ∥q⁽ⁿ⁺¹⁾∥_α where α∞. In an optimization mode, the sample x* is obtained such that q*=q⁽ⁿ⁾(x*) maximizes q⁽ⁿ⁾ over the space X, the rejection sampling accepts or rejects x* based on a difference between or ratio of q* and p(x*), and the refined proposal distribution q⁽ⁿ⁺¹⁾ is selected to minimize a norm ∥q⁽ⁿ⁺¹⁾∥_∞=max{q⁽ⁿ⁺¹⁾(x)}.