Elamur Research
☰
home / papers / 2019 / Submodular Optimization-based Diverse Paraphrasing and its Effectiveness in Data Augmentation

Submodular Optimization-based Diverse Paraphrasing and its Effectiveness in Data Augmentation

Written for the Research library (claude-opus-5-5) from the paper text. Original — aclanthology.org/N19-1363.pdf

Summary

Paraphrase generators usually produce multiple outputs by taking the top-k beams. These candidates tend to be near-duplicates that differ only in a word or punctuation mark. Kumar et al. present DiPS (Diverse Paraphraser using Submodularity), which changes only the decoding stage of a standard SEQ2SEQ model. At each decoding step, the decoder proposes 3k candidate subsequences. A greedy algorithm then keeps k of them by maximizing a monotone submodular objective. This objective balances two kinds of components:

  • Fidelity terms: n-gram overlap and embedding similarity with the source.
  • Diversity terms: rewarding unique n-grams and structural coverage.

A weight λ controls the trade-off between the two. Because the objective is monotone submodular, the greedy selection is provably near-optimal.

On Quora and Twitter data, DiPS produced more lexically varied paraphrases than beam search, diverse beam search, DPP- and SSR-based selection, and a VAE model, while keeping fidelity competitive. When used to augment training data, its paraphrases improved intent, question and paraphrase classifiers more than the alternatives. This suggests paraphrasing is a practical augmentation tool for NLP.

Key points

  • Theoretical guarantee: the greedy selection (Nemhauser et al.) gets within a 0.632 factor of the optimal subset. Submodular maximization is applied stochastically, and only once roughly half the source length has been generated, to save computation.
  • Diversity results (distinct n-gram scores): DiPS scored highest on both Quora-Div and Twitter. For example, the highest-order score shown was 65.3 on Quora-Div versus 62.6 for DPP. Fidelity was measured with BLEU, METEOR and TERp.
  • Choice of λ: diversity levels off at λ ≈ 0.2–0.5, so λ is tuned to avoid giving up fidelity.
  • Intent and question classification (YahooL31, TREC, SNIPS): DiPS augmentation gave the best accuracy for both LogReg and LSTM classifiers. For example, LSTM on SNIPS rose from 94.7 to 97.1, and LogReg on TREC from 82.2 to 86.6. The table layout in the extracted text is garbled, so these column assignments are inferred.
  • Paraphrase recognition (Quora-PR): LogReg and SiameseLSTM gained the most with DiPS augmentation.
  • Code: available at github.com/malllabiisc/DiPS.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

Fields: Machine translation · Natural language processing

Cited by

58 papers of our library cite it (of the 140673 whose bibliographies we read); 6 of them have a page here, 52 not yet.

Cite

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/n19-1363

@inproceedings{kumar2019submodular,
  title = {{Submodular Optimization-based Diverse Paraphrasing and its Effectiveness in Data Augmentation}},
  author = {Kumar, Ashutosh and Bhattamishra, Satwik and Bhandari, Manik and Talukdar, Partha},
  booktitle = {Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)},
  year = {2019},
  doi = {10.18653/v1/n19-1363},
  url = {https://doi.org/10.18653/v1/n19-1363}
}

References

52 references, 13 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Peter G Anick and Suresh Tipirneni. 1999. The paraphrase search assistant: terminological feedback for iterative information seeking. In Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, pages 153–159. ACM. find
  2. Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. 2014. Neural machine translation by jointly learning to align and translate. arXiv preprint arXiv:1409.0473. ↗ our card
  3. Satanjeev Banerjee and Alon Lavie. 2005. Meteor: An automatic metric for mt evaluation with improved correlation with human judgments. In Proceedings of the acl workshop on intrinsic and extrinsic evaluation measures for machine translation and/or summarization, pages 65–72. find our card
  4. Delphine Bernhard and Iryna Gurevych. 2008. Answering learners’ questions by retrieving question paraphrases from social q&a sites. In Proceedings of the third workshop on innovative use of NLP for building educational applications, pages 44–52. Association for Computational Linguistics. find
  5. Ziqiang Cao, Chuwei Luo, Wenjie Li, and Sujian Li. 2017. Joint copying and restricted generation for paraphrase. find
  6. Alice Coucke, Alaa Saade, Adrien Ball, Théodore Bluche, Alexandre Caulier, David Leroy, Clément Doumouro, Thibault Gisselbrecht, Francesco Caltagirone, Thibaut Lavril, Maël Primet, and Joseph Dureau. 2018. Snips voice platform: an embedded spoken language understanding system for private-by-design voice interfaces. CoRR, abs/1805.10190. ↗ our card
  7. Mladen Dimovski, Claudiu Musat, Vladimir Ilievski, Andreea Hossman, and Michael Baeriswyl. 2018. Submodularity-inspired data selection for goal-oriented chatbot training based on sentence embeddings. In Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI-18, pages 4019–4025. International Joint Conferences on Artificial Intelligence Organization. find
  8. Ehsan Elhamifar, Guillermo Sapiro, and S Shankar Sastry. 2016. Dissimilarity-based sparse subset selection. IEEE transactions on pattern analysis and machine intelligence, 38(11):2182–2197. find
  9. Ehsan Elhamifar, Guillermo Sapiro, and Rene Vidal. 2012. Finding exemplars from pairwise dissimilarities via simultaneous sparse recovery. In Advances in Neural Information Processing Systems, pages 19–27. find
  10. Anthony Fader, Luke Zettlemoyer, and Oren Etzioni. 2013. Paraphrase-driven learning for open question answering. In Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), volume 1, pages 1608– 1618. find
  11. Jenny Rose Finkel, Christopher D Manning, and Andrew Y Ng. 2006. Solving the problem of cascading errors: Approximate bayesian inference for linguistic annotation pipelines. In Proceedings of the 2006 Conference on Empirical Methods in Natural Language Processing, pages 618–626. Association for Computational Linguistics. find
  12. S Fujishige. 2005. Submodular functions and optimization. Annals of Discrete Mathematics, 58. find
  13. Kevin Gimpel, Dhruv Batra, Chris Dyer, and Gregory Shakhnarovich. 2013. A systematic exploration of diversity in machine translation. In Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, pages 1100–1111. find
  14. Ankush Gupta, Arvind Agarwal, Prawaan Singh, and Piyush Rai. 2018. A deep generative framework for paraphrase generation. In AAAI Conference on Artificial Intelligence. find
  15. Rishabh K Iyer and Jeff A Bilmes. 2013. Submodular optimization with submodular cover and submodular knapsack constraints. In Advances in Neural Information Processing Systems, pages 2436–2444. find
  16. Mohit Iyyer, John Wieting, Kevin Gimpel, and Luke Zettlemoyer. 2018. Adversarial example generation with syntactically controlled paraphrase networks. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers), volume 1, pages 1875– 1885. find our card
  17. Stefanie Jegelka and Jeff Bilmes. 2011. Submodularity beyond submodular energies: coupling edges in graph cuts. find
  18. Diederik P Kingma and Jimmy Ba. 2014. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980. ↗
  19. Diederik P Kingma and Max Welling. 2013. Autoencoding variational bayes. arXiv preprint arXiv:1312.6114. ↗ our card
  20. Katrin Kirchhoff and Jeff Bilmes. 2014. Submodularity for data selection in machine translation. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 131–141. find
  21. Sosuke Kobayashi. 2018. Contextual augmentation: Data augmentation by words with paradigmatic relations. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short Papers), volume 2, pages 452–457. find our card
  22. Vladimir Kolmogorov and Ramin Zabih. 2002. What energy functions can be minimized via graph cuts? In European conference on computer vision, pages 65–81. Springer. Andreas Krause and Daniel Golovin. function maximization. find
  23. Submodular Andreas Krause and Carlos Guestrin. 2011. Submodularity and its applications in optimized information gathering. ACM Transactions on Intelligent Systems and Technology (TIST), 2(4):32. find
  24. Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. 2012. Imagenet classification with deep convolutional neural networks. In Advances in neural information processing systems, pages 1097–1105. find
  25. Alex Kulesza, Ben Taskar, et al. 2012. Determinantal point processes for machine learning. Foundations and Trends R in Machine Learning, 5(2–3):123– 286. find
  26. Wuwei Lan, Siyu Qiu, Hua He, and Wei Xu. 2017. A continuously growing dataset of sentential paraphrases. In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pages 1224–1234. find
  27. Jiwei Li, Michel Galley, Chris Brockett, Jianfeng Gao, and Bill Dolan. 2015. A diversity-promoting objective function for neural conversation models. arXiv preprint arXiv:1510.03055. ↗ our card
  28. Jiwei Li, Michel Galley, Chris Brockett, Jianfeng Gao, and Bill Dolan. 2016. A diversity-promoting objective function for neural conversation models. In Proceedings of the 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 110–119. find our card
  29. Jiwei Li and Dan Jurafsky. 2016. Mutual information and diverse decoding improve neural machine translation. arXiv preprint arXiv:1601.00372. ↗
  30. Liangda Li, Ke Zhou, Gui-Rong Xue, Hongyuan Zha, and Yong Yu. 2009. Enhancing diversity, coverage and balance for summarization through structure learning. In Proceedings of the 18th international conference on World wide web, pages 71–80. ACM. find
  31. Xin Li and Dan Roth. 2002. Learning question classifiers. In Proceedings of the 19th international conference on Computational linguistics-Volume 1, pages 1–7. Association for Computational Linguistics. find
  32. Alexander J Ratner, Henry Ehrenberg, Zeshan Hussain, Jared Dunnmon, and Christopher Ré. 2017. Learning to compose domain-specific transformations for data augmentation. In Advances in Neural Information Processing Systems, pages 3239–3249. find
  33. Zichao Li, Xin Jiang, Lifeng Shang, and Hang Li. 2018. Paraphrase generation with deep reinforcement learning. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pages 3865–3878. Association for Computational Linguistics. find our card
  34. Alan Ritter, Colin Cherry, and William B Dolan. 2011. Data-driven response generation in social media. In Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing, pages 583–593. find
  35. Hui Lin and Jeff Bilmes. 2011. A class of submodular functions for document summarization. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies-Volume 1, pages 510–520. Association for Computational Linguistics. find
  36. Kathleen R McKeown. 1983. Paraphrasing questions using given and new information. Computational Linguistics, 9(1):1–10. find
  37. Jonas Mueller and Aditya Thyagarajan. 2016. Siamese recurrent architectures for learning sentence similarity. find
  38. Preksha Nema, Mitesh M Khapra, Anirban Laha, and Balaraman Ravindran. 2017. Diversity driven attention model for query-based abstractive summarization. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), volume 1, pages 1063–1072. find
  39. George L Nemhauser, Laurence A Wolsey, and Marshall L Fisher. 1978. An analysis of approximations for maximizing submodular set functionsi. Mathematical programming, 14(1):265–294. find
  40. Sergiu Nisioi, Sanja Štajner, Simone Paolo Ponzetto, and Liviu P Dinu. 2017. Exploring neural text simplification models. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), volume 2, pages 85–91. find
  41. Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. 2002. Bleu: a method for automatic evaluation of machine translation. In Proceedings of the 40th annual meeting on association for computational linguistics, pages 311–318. Association for Computational Linguistics. find our card
  42. Ankur Parikh, Oscar Täckström, Dipanjan Das, and Jakob Uszkoreit. 2016. A decomposable attention model for natural language inference. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pages 2249–2255. find our card
  43. Aaditya Prakash, Sadid A Hasan, Kathy Lee, Vivek Datla, Ashequl Qadir, Joey Liu, and Oladimeji Farri. 2016. Neural paraphrase generation with stacked residual lstm networks. arXiv preprint arXiv:1610.03098. ↗
  44. Abigail See, Peter J Liu, and Christopher D Manning. 2017. Get to the point: Summarization with pointer-generator networks. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), volume 1, pages 1073–1083. find
  45. Matthew Snover, Nitin Madnani, Bonnie J Dorr, and Richard Schwartz. 2009. Fluency, adequacy, or hter?: exploring different human judgments with a tunable mt metric. In Proceedings of the Fourth Workshop on Statistical Machine Translation, pages 259–268. Association for Computational Linguistics. find
  46. Yiping Song, Rui Yan, Yansong Feng, Yaoyuan Zhang, Dongyan Zhao, and Ming Zhang. 2018. Towards a neural conversation model with diversity net using determinantal point processes. In AAAI. find
  47. Peter Stobbe and Andreas Krause. 2010. Efficient minimization of decomposable submodular functions. In Advances in Neural Information Processing Systems, pages 2208–2216. find
  48. Ashwin Vijayakumar, Michael Cogswell, Ramprasaath Selvaraju, Qing Sun, Stefan Lee, David Crandall, and Dhruv Batra. 2018. Diverse beam search for improved description of complex scenes. AAAI Conference on Artificial Intelligence. find
  49. William Yang Wang and Diyi Yang. 2015. That’s so annoying!!!: A lexical and frame-semantic embedding based data augmentation approach to automatic categorization of annoying behaviors using# petpeeve tweets. In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, pages 2557–2563. find
  50. Sander Wubben, Antal Van Den Bosch, and Emiel Krahmer. 2010. Paraphrase generation as monolingual translation: Data and evaluation. In INLGC, pages 203–207. ACL. find
  51. Wei Xu, Chris Callison-Burch, and Courtney Napoles. 2015. Problems in current text simplification research: New data can help. Transactions of the Association of Computational Linguistics, 3(1):283– 297. find our card
  52. Xiang Zhang, Junbo Zhao, and Yann LeCun. 2015. Character-level convolutional networks for text classification. In Advances in neural information processing systems, pages 649–657. find our card