DISCO : efficient unsupervised decoding for discrete natural language problems via convex relaxation

Abstract

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 $\epsilon$ 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.

References in corpus (5)

• Distributed Representations of Words and Phrases and their Compositionality
• word2vec Explained: deriving Mikolov et al.'s negative-sampling word-embedding method
• Convolutional Neural Networks for Sentence Classification
• Near-optimal Nonmyopic Value of Information in Graphical Models
• Deep Submodular Functions