Multiple sequence alignment

Barzilay and Lee^[5] proposed a method to generate paraphrases through the usage of monolingual parallel corpora, namely news articles covering the same event on the same day. Training consists of using multi-sequence alignment to generate sentence-level paraphrases from an unannotated corpus. This is done by

• finding recurring patterns in each individual corpus, i.e. "X (injured/wounded) Y people, Z seriously" where X, Y, Z are variables
• finding pairings between such patterns the represent paraphrases, i.e. "X (injured/wounded) Y people, Z seriously" and "Y were (wounded/hurt) by X, among them Z were in serious condition"

This is achieved by first clustering similar sentences together using n-gram overlap. Recurring patterns are found within clusters by using multi-sequence alignment. Then the position of argument words is determined by finding areas of high variability within each cluster, aka between words shared by more than 50% of a cluster's sentences. Pairings between patterns are then found by comparing similar variable words between different corpora. Finally, new paraphrases can be generated by choosing a matching cluster for a source sentence, then substituting the source sentence's argument into any number of patterns in the cluster.

Phrase-based Machine Translation

Paraphrase can also be generated through the use of phrase-based translation as proposed by Bannard and Callison-Burch.^[6] The chief concept consists of aligning phrases in a pivot language to produce potential paraphrases in the original language. For example, the phrase "under control" in an English sentence is aligned with the phrase "unter kontrolle" in its German counterpart. The phrase "unter kontrolle" is then found in another German sentence with the aligned English phrase being "in check," a paraphrase of "under control."

The probability distribution can be modeled as ${\displaystyle \Pr(e_{2}|e_{1})}$, the probability phrase ${\displaystyle e_{2}}$ is a paraphrase of ${\displaystyle e_{1}}$, which is equivalent to ${\displaystyle \Pr(e_{2}|f)\Pr(f|e_{1})}$ summed over all ${\displaystyle f}$, a potential phrase translation in the pivot language. Additionally, the sentence ${\displaystyle e_{1}}$ is added as a prior to add context to the paraphrase. Thus the optimal paraphrase, ${\displaystyle {\hat {e_{2}}}}$ can be modeled as:

${\displaystyle {\hat {e_{2}}}={\text{arg}}\max _{e_{2}\neq e_{1}}\Pr(e_{2}|e_{1},S)={\text{arg}}\max _{e_{2}\neq e_{1}}\sum _{f}\Pr(e_{2}|f,S)\Pr(f|e_{1},S)}$

${\displaystyle \Pr(e_{2}|f)}$ and ${\displaystyle \Pr(f|e_{1})}$ can be approximated by simply taking their frequencies. Adding ${\displaystyle S}$ as a prior is modeled by calculating the probability of forming the ${\displaystyle S}$ when ${\displaystyle e_{1}}$ is substituted with ${\displaystyle e_{2}}$.

Long short-term memory

There has been success in using long short-term memory (LSTM) models to generate paraphrases.^[7] In short, the model consists of an encoder and decoder component, both implemented using variations of a stacked residual LSTM. First, the encoding LSTM takes a one-hot encoding of all the words in a sentence as input and produces a final hidden vector, which can represent the input sentence. The decoding LSTM takes the hidden vector as input and generates a new sentence, terminating in an end-of-sentence token. The encoder and decoder are trained to take a phrase and reproduce the one-hot distribution of a corresponding paraphrase by minimizing perplexity using simple stochastic gradient descent. New paraphrases are generated by inputting a new phrase to the encoder and passing the output to the decoder.

Transformers

With the introduction of Transformer models, paraphrase generation approaches improved their ability to generate text by scaling neural network parameters and heavily parallelizing training through feed-forward layers.^[8] These models are so fluent in generating text that human experts cannot identify if an example was human-authored or machine-generated.^[9] Transformer-based paraphrase generation relies on autoencoding, autoregressive, or sequence-to-sequence methods. Autoencoder models predict word replacement candidates with a one-hot distribution over the vocabulary, while autoregressive and seq2seq models generate new text based on the source predicting one word at a time.^[10][11] More advanced efforts also exist to make paraphrasing controllable according to predefined quality dimensions, such as semantic preservation or lexical diversity.^[12] Many Transformer-based paraphrase generation methods rely on unsupervised learning to leverage large amounts of training data and scale their methods.^[13][14]

Recursive Autoencoders

Paraphrase recognition has been attempted by Socher et al^[1] through the use of recursive autoencoders. The main concept is to produce a vector representation of a sentence and its components by recursively using an autoencoder. The vector representations of paraphrases should have similar vector representations; they are processed, then fed as input into a neural network for classification.

Given a sentence ${\displaystyle W}$ with ${\displaystyle m}$ words, the autoencoder is designed to take 2 ${\displaystyle n}$-dimensional word embeddings as input and produce an ${\displaystyle n}$-dimensional vector as output. The same autoencoder is applied to every pair of words in ${\displaystyle S}$ to produce ${\displaystyle \lfloor m/2\rfloor }$ vectors. The autoencoder is then applied recursively with the new vectors as inputs until a single vector is produced. Given an odd number of inputs, the first vector is forwarded as-is to the next level of recursion. The autoencoder is trained to reproduce every vector in the full recursion tree, including the initial word embeddings.

Given two sentences ${\displaystyle W_{1}}$ and ${\displaystyle W_{2}}$ of length 4 and 3 respectively, the autoencoders would produce 7 and 5 vector representations including the initial word embeddings. The euclidean distance is then taken between every combination of vectors in ${\displaystyle W_{1}}$ and ${\displaystyle W_{2}}$ to produce a similarity matrix ${\displaystyle S\in \mathbb {R} ^{7\times 5}}$. ${\displaystyle S}$ is then subject to a dynamic min-pooling layer to produce a fixed size ${\displaystyle n_{p}\times n_{p}}$ matrix. Since ${\displaystyle S}$ are not uniform in size among all potential sentences, ${\displaystyle S}$ is split into ${\displaystyle n_{p}}$ roughly even sections. The output is then normalized to have mean 0 and standard deviation 1 and is fed into a fully connected layer with a softmax output. The dynamic pooling to softmax model is trained using pairs of known paraphrases.

Skip-thought vectors

Skip-thought vectors are an attempt to create a vector representation of the semantic meaning of a sentence, similarly to the skip gram model.^[15] Skip-thought vectors are produced through the use of a skip-thought model which consists of three key components, an encoder and two decoders. Given a corpus of documents, the skip-thought model is trained to take a sentence as input and encode it into a skip-thought vector. The skip-thought vector is used as input for both decoders; one attempts to reproduce the previous sentence and the other the following sentence in its entirety. The encoder and decoder can be implemented through the use of a recursive neural network (RNN) or an LSTM.

Since paraphrases carry the same semantic meaning between one another, they should have similar skip-thought vectors. Thus a simple logistic regression can be trained to good performance with the absolute difference and component-wise product of two skip-thought vectors as input.

Transformers

Similar to how Transformer models influenced paraphrase generation, their application in identifying paraphrases showed great success. Models such as BERT can be adapted with a binary classification layer and trained end-to-end on identification tasks.^[16][17] Transformers achieve strong results when transferring between domains and paraphrasing techniques compared to more traditional machine learning methods such as logistic regression. Other successful methods based on the Transformer architecture include using adversarial learning and meta-learning.^[18][19]