DISCO : efficient unsupervised decoding for discrete natural language problems via convex relaxation
This addresses a fundamental bottleneck in NLP for researchers and practitioners, though it appears incremental as it builds on existing relaxation methods.
The paper tackles the NP-hard decoding problem in sequential text generation by developing a continuous relaxation framework and the Disco algorithm, which linearly converges to an ε neighborhood of the optimum and shows superior performance in adversarial text generation experiments.
In this paper we study test time decoding; an ubiquitous step in almost all sequential text generation task spanning across a wide array of natural language processing (NLP) problems. Our main contribution is to develop a continuous relaxation framework for the combinatorial NP-hard decoding problem and propose Disco - an efficient algorithm based on standard first order gradient based. We provide tight analysis and show that our proposed algorithm linearly converges to within $ε$ neighborhood of the optima. Finally, we perform preliminary experiments on the task of adversarial text generation and show superior performance of Disco over several popular decoding approaches.