FASTSUBS: An Efficient and Exact Procedure for Finding the Most Likely Lexical Substitutes Based on an N-Gram Language Model
By Deniz Yuret. 2012
28 citations recorded by the source corpus.
Lexical substitutes have found use in areas such as paraphrasing, text simplification, machine translation, word sense disambiguation, and part of speech induction. However the computational complexity of accurately identifying the most likely substitutes for a word has made large scale experiments difficult. In this letter we introduce a new search algorithm, FASTSUBS, that is guaranteed to find the K most likely lexical substitutes for a given word in a sentence based on an n-gram language model. The computation is sublinear in both K and the vocabulary size V. An implementation of the algorithm and a dataset with the top 100 substitutes of each token in the WSJ section of the Penn Treebank are available at http://goo.gl/jzKH0.
Subfields: Artificial Intelligence, Natural Language Processing
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Ido Dagan
- Jacob Goldberger
- Oren Melamud
- Chris Biemann
- Alexander Panchenko
- José Camacho-Collados
- Stefano Faralli
- Simone Paolo Ponzetto
In Natural Language Processing
- Jacob Goldberger
- Ido Dagan
- Chris Biemann
- Oren Melamud
- José Camacho-Collados
- Mohammad Taher Pilehvar
- Alexander Panchenko
- Stefano Faralli
Citations in the corpus
- context2vec: Learning Generic Context Embedding with Bidirectional LSTM (2016, background): “Substitute vectors (Yuret, 2012) represent contexts as a probabilistic distribution over the potential gap-filler words for the target slot, pruned to its top-k most probable words.”
- Modeling Word Meaning in Context with Substitute Vectors (2015, methodology): “(2012), we used FASTSUBS (Yuret, 2012) with this language model to efficiently generate substitute vectors pruned to their top-n substitutes, v1.”
- Unsupervised Does Not Mean Uninterpretable: The Case for Word Sense Induction and Disambiguation (2017, methodology): “Most notably, we use a word sense inventory based on clustering word similarities (Pantel and Lin, 2002); for disambiguation we rely on syntactic context features, co-occurrences (Hope and Keller, 2013) and language models (Yuret, 2012).”