Sentence Similarity Learning by Lexical Decomposition and Composition

In plain words

When you compare two sentences, most methods look only at the words they share. This paper argues that the words that differ also carry information. Each word is turned into a vector, and every word is checked against the whole other sentence to see how much of its meaning that sentence already covers. The part that is covered counts as "similar", and the rest counts as "different". Both parts are kept.

A small convolutional network then reads the two parts side by side and looks for short phrases in each. A final layer turns those features into one score between 0 and 1 for how alike the two sentences are. The model is aimed at answer ranking and paraphrase checking.

TL;DR

• Each word vector is split into a similar part and a dissimilar part, using a soft match against the other sentence §2 eq. 6 eq. 9.
• A two-channel CNN with unigram, bigram and trigram filters and max-pooling turns both parts into features §3.3 eq. 10.
• Author-reported: best MAP on QASent and WikiQA, accuracy close to the best on MSRP without extra resources §4.3 tab. 2 tab. 3 tab. 4.
• No official code was found, so the exact training recipe is not recoverable.

Problem

Sentence similarity has to bridge a lexical gap, match phrases of different granularity, and account for what differs between two sentences §1. The authors say earlier work on paraphrase identification handled the dissimilar parts only in a limited way, and needed human annotation to train a classifier for them §1. The question is answer sentence selection (ranking candidate answers for a question) and paraphrase identification §1 §4.1.

Method

The model has four stages: word representation, semantic matching, decomposition, composition, then a similarity score §2.

1. Word representation. Each token is a d-dimensional word2vec vector, with d = 300. Sentences S (m words) and T (n words) become matrices §2 §4.1.
2. Semantic matching. For every word in one sentence, build a vector that is a weighted mix of word vectors from the other sentence, using cosine similarity as the weight eq. 5 eq. 6. Three variants are defined: global (weighted average over all words), max (the single most similar word), and local-w (weighted average over a window of 2w+1 words centred on the most similar word) §3.1. The authors choose local-3 §4.2.
3. Decomposition. Each word vector s_i is split against its matching vector into a similar part s_i+ and a dissimilar part s_i-. Three ways are defined: rigid (exact match decides everything) eq. 7, linear (scale by the cosine) eq. 8, and orthogonal (projection onto the matching vector, with the remainder as dissimilar) eq. 9 §3.2. The authors choose orthogonal §4.2.
4. Composition. The similar and dissimilar matrices of one sentence pass through a CNN. Each filter of shape d×h is applied to the same window in both matrices, the two responses are added, a bias is added, and tanh is applied eq. 10 §3.3. Max-pooling over positions leaves one feature per filter §3.3. Filter types are unigram, bigram and trigram, 500 filters each (the configuration called win-3) §4.2.
5. Similarity. The features of both sentences are concatenated and passed through a linear function and a sigmoid, giving a score in [0, 1] eq. 4 §3.4.

Training maximises the likelihood of binary labels over (S, T, L) triples. L is 1 for a paraphrase or a correct answer, and 0 otherwise §3.5. The model is implemented in Theano and optimised with Adam §3.5.

# Lexical decomposition and composition similarity  [§2] [§3]
# Input:  sentences S (m tokens), T (n tokens), word vectors of size d = 300
# Output: similarity score in [0, 1]

def similarity(S, T):
    # 1. Word vectors, one per token  [§2] [§4.1]
    s_vecs = embed(S)                           # (m, d)
    t_vecs = embed(T)                           # (n, d)

    # 2. Cosine similarity between every pair of words  [eq. 5]
    sims = cosine_matrix(s_vecs, t_vecs)        # (m, n)

    # 3. Matching vectors using local-w with w = 3  [eq. 6] [§4.2]
    s_match = local_match(sims, t_vecs, w=3)    # (m, d)
    t_match = local_match(sims.T, s_vecs, w=3)  # (n, d)

    # 4. Orthogonal split into similar and dissimilar parts  [eq. 9] [§4.2]
    s_plus, s_minus = orthogonal_split(s_vecs, s_match)
    t_plus, t_minus = orthogonal_split(t_vecs, t_match)

    # 5. Two-channel CNN, one feature per filter, 500 filters for each of
    #    unigram, bigram and trigram windows  [eq. 10] [§3.3] [§4.2]
    s_feat = compose(s_plus, s_minus)           # (1500,)
    t_feat = compose(t_plus, t_minus)           # (1500,)

    # 6. Score from the concatenated features  [eq. 4] [§3.4]
    return sigmoid(linear(concat(s_feat, t_feat)))

Key equations, as written in the paper:

a_{i,j} = \frac{s_i^T t_j}{\|s_i\|\,\|t_j\|} eq. 5

\hat{s}_i = \begin{cases} \frac{\sum_j a_{i,j} t_j}{\sum_j a_{i,j}} & \text{global} \\ \frac{\sum_{j=k-w}^{k+w} a_{i,j} t_j}{\sum_{j=k-w}^{k+w} a_{i,j}} & \text{local-}w \\ t_k & \text{max} \end{cases},\quad k = \arg\max_j a_{i,j} eq. 6

s_i^+ = \frac{s_i \cdot \hat{s}_i}{\hat{s}_i \cdot \hat{s}_i}\,\hat{s}_i, \qquad s_i^- = s_i - s_i^+ eq. 9

c_{o,i} = \tanh\!\big(w_o \ast S^+_{[i:i+h]} + w_o \ast S^-_{[i:i+h]} + b_o\big) eq. 10

Hyperparameters

Results

Author-reported. Setup: QASent and WikiQA answer sentence selection (MAP and MRR), MSRP paraphrase identification (accuracy and F1), word2vec 300-d embeddings, test sets §4.1 §4.3. Model choices were made on the QASent development set §4.2. The table numbers below come from the LaTeX source; the table environment that holds QASent and WikiQA has two captions, so the numbers are 2 and 3. Check the rendered PDF if they look off.

Answer sentence selection, QASent tab. 2:

Answer sentence selection, WikiQA tab. 3:

Paraphrase identification, MSRP tab. 4:

Model-property experiments on QASent dev fig. 2 are shown only as plots. The text reports trends: max beat global on MAP and MRR; local-3 gave the best MAP among local windows; rigid was worst; orthogonal matched linear on MAP and was better on MRR; trigram filters (win-3) peaked, and adding 4-gram or 5-gram filters lowered the score §4.2. Exact values are not stated in the text.

Paper vs code

No official code.

Searched: the abstract, introduction and body name no repository. The raw arXiv metadata has no comments field. A GitHub repository search returned one hit, mcrisc/lexdecomp, which is a third-party Python reimplementation with no license; it was not used. A GitHub user search for the first author returned several unrelated accounts that could not be tied to the authors, so none were used. A search of the IBM organisation for "answer selection" returned no repositories. A web search was not run because the tool was not permitted in this session.

No code is cited, so the points below are open questions that the paper does not answer, not checked differences.

Pitfalls

• Window notation. Equation 6 names the window size w, but the Model Properties text calls the same thing local-l and then picks local-3 §4.2. Reading "local-3" as w = 3 gives a window from k-3 to k+3, which is seven words eq. 6.
• Indexing. The global sum in equation 6 starts at j = 0, but the sentence is indexed from 1 in §2. The index base is not stated; use 1..n.
• Window edges. How the local window is cut at the sentence start and end, and whether it can overrun, is not stated eq. 6.
• Negative cosines. Weights are a_{i,j} divided by their sum eq. 6. A negative cosine gives a negative weight and possibly a near-zero or negative denominator. The paper does not say whether negative similarities are clipped or how a zero denominator is handled.
• Negative alpha. Only the linear decomposition uses a cosine as a scale eq. 8; a negative cosine would flip the sign of the similar part. Not addressed.
• Zero matching vector. The orthogonal projection divides by the squared norm of the matching vector eq. 9. A zero matching vector is possible when all weights are zero, and no guard is described.
• Shared filters in the "two channels". Equation 10 applies one filter w_o and one bias b_o to both the similar and the dissimilar window, then adds the responses. The two channels therefore share weights and are merged before the nonlinearity. This is the literal reading; the text uses the phrase "two-channel CNN" without saying otherwise §3.3.
• Feature count. Derived, not stated: with 500 filters for each of three window sizes, one sentence gives 1500 features, and the pair gives 3000 inputs to the output layer §4.2 §3.4.
• Output layer. The text says "a linear function to sum up all the features" followed by a sigmoid §3.4. It does not say whether the weights are learned, or whether there is a bias. Treating it as a learned affine layer is an assumption.
• Loss and training. Training maximises likelihood over binary labels §3.5. The exact loss form, learning rate, batch size, epochs, regularisation, initialisation, early stopping, and whether word vectors are updated are not stated.
• Development set. The MSRP development split is built §4.1, but the text does not say whether it was used for early stopping or model selection there.
• Claims. The abstract says the model reaches state-of-the-art performance on answer selection. On QASent it has the best MAP, but its MRR (0.8447) is below the attention-based CNN (0.8511) tab. 2. On WikiQA it is best on both metrics tab. 3. On MSRP the best reported result is a hand-crafted SVM at 80.4 accuracy, and this work reaches 78.4 tab. 4 §4.3.
• Cost. The matching step is a full word-by-word cosine matrix plus a weighted sum per word, so cost grows with the product of the two sentence lengths. The paper gives no runtime figures.

Lineage

• Builds on: the attention idea in neural machine translation, which the matching step is said to adapt to CNNs §5; the two-channel CNN with n-gram filters is credited to Kim (2014) §3.3; word2vec embeddings §2.
• Changed from the closest prior attention-CNN: ABCNN (Yin et al.) takes the attention matrix as an extra input channel, while this model uses it to split each word vector before the CNN §5.
• Compared against: Severyn and Moschitti (2015), Wang and Ittycheriah (2015), dos Santos et al. (2016), Yang et al. (2015), Miao et al. (2015), Yin et al. (2015) for ABCNN, Yin and Schütze (2015) for the multi-granularity CNN, He et al. (2015), and Ji and Eisenstein (2013) §4.3.
• Superseded by: not stated.