CoSENT (Part 2): How Big Is the Gap Between Representation-based and Interaction-based Matching?

CoSENT（二）：特征式匹配与交互式匹配有多大差距？ 苏剑林 · 2022-01-12 · Machine Learning semantics semantic similarity contrastive learning

Generally speaking, there are two implementation approaches for text matching: interaction-based and representation-based. Interaction-based methods concatenate the two texts together and treat them as a single text for classification, while representation-based methods encode the two sentences separately into sentence vectors using an encoder, and then perform a simple fusion (computing cosine similarity or feeding them into a shallow network). The usual conclusion is that interaction-based methods, by allowing thorough comparison between the two texts, tend to achieve better accuracy, but their obvious drawback is poor efficiency in retrieval scenarios; representation-based methods, on the other hand, can precompute and cache sentence vectors, giving them high efficiency, but because the interaction between sentences is much shallower, their performance usually falls short of interaction-based methods.

In the previous post, I introduced CoSENT, which is fundamentally a representation-based approach, and one that improves upon previous representation-based schemes. This got my competitive instincts going: can CoSENT match interaction-based methods? How large is the gap between representation-based and interaction-based approaches? This post takes on that comparison.

Automatic Threshold Search

In the article CoSENT (Part 1): A More Effective Sentence Vector Scheme than Sentence-BERT, the metric we used to evaluate CoSENT was the Spearman correlation coefficient, a metric that depends only on the relative ordering of the predictions and not on any threshold — making it well suited to evaluation in retrieval scenarios. But if the evaluation metric is a classification metric such as accuracy or F1, we must first determine a threshold: predictions above this value are treated as positive, and those below as negative, before we can compute the metric. In the binary classification setting, we can use binary search to efficiently determine this threshold. (more)

However, the need to search for a threshold is not actually unique to binary classification — general multi-class classification tasks have the same requirement, so let's expand on this issue here. For instance, for a predicted distribution $[p_1,p_2,\dots,p_n]$ over $n$ classes, we usually take the class with the highest probability, i.e., $\mathop{\text{argmax}}\,(p_1,p_2,\dots,p_n)$, as the predicted class. But in scenarios with class imbalance, this may not actually be optimal. We can instead search for a vector $[t_1,t_2,\cdots,t_n]$ using a validation set, and then use

\begin{equation}\mathop{\text{argmax}}\,(p_1 t_1,p_2 t_2,\dots,p_n t_n)\end{equation}

as the predicted class, where $[t_1,t_2,\cdots,t_n]$ plays the role of a threshold in the multi-class setting.

So how do we search for $[t_1,t_2,\cdots,t_n]$? The search objective is naturally to maximize the metric, but since metrics like accuracy or F1 are non-differentiable, gradient descent is out of the question. And since the parameter to be searched is a multi-dimensional vector, binary search doesn't work well either. Here we introduce a solution called "Powell's method." Powell's method involves a fair amount of mathematical detail that we won't go into here; in brief, it is an algorithm for solving low-dimensional unconstrained optimization problems that requires no gradients and is also relatively efficient — "low-dimensional" here meaning the number of parameters to optimize is typically no more than a hundred (you certainly can't expect it to optimize a neural network). Most importantly, Powell's method has a ready-made implementation in SciPy: just specify method='Powell' in scipy.optimize.minimize to invoke it.

Reference code for the above problem is as follows:

import numpy as np
from scipy.optimize import minimize

def loss(t):
    """这里的y_true.shape=[batch_size],
    y_pred.shape=[batch_size, num_classes]
    """
    t = (np.tanh(t) + 1) / 2
    return -np.mean(y_true == (y_pred * t[None]).argmax(1))

options = {'xtol': 1e-10, 'ftol': 1e-10, 'maxiter': 100000}
result = minimize(
    loss, np.zeros_like(y_pred[:1]), method='Powell', options=options
)
thresholds = (np.tanh(result.x) + 1) / 2

Experimental Results

Now that we have a method for automatically determining the threshold, we can evaluate classification performance. I ran experiments on four datasets — ATEC, BQ, LCQMC, and PAWSX — comparing three approaches: CoSENT, Sentence-BERT, and an interaction-based method (denoted Interact). To be fair, for each method the optimal threshold was determined on the validation set using Powell's method, and this threshold was then used to report the results on the test set — even for the interaction-based method.

Experiment code: https://github.com/bojone/CoSENT/tree/main/accuracy

The experimental results are as follows (the metric is accuracy):

$$\begin{array}{c|cccc|c} \hline & \text{ATEC} & \text{BQ} & \text{LCQMC} & \text{PAWSX} & \text{Avg}\\ \hline \text{BERT+CoSENT} & \textbf{85.81} & 83.24 & 86.67 & 76.30 & 83.00 \\ \text{Sentence-BERT} & 84.93 & 82.46 & 87.42 & 65.33 & 80.04\\ \text{BERT+Interact} & 85.49 & \textbf{83.88} & \textbf{87.80} & \textbf{81.30} & \textbf{84.62} \\ \hline \text{RoBERTa+CoSENT} & 85.93 & 83.42 & 87.63 & 76.55 & 83.38 \\ \text{Sentence-RoBERTa} & 85.34 & 82.52 & 88.14 & 68.35 & 81.09 \\ \text{RoBERTa+Interact} & \textbf{86.04} & \textbf{83.62} & \textbf{88.22} & \textbf{83.33} & \textbf{85.30} \\ \hline \end{array}$$

The results show that, in terms of raw performance, the interaction-based method does indeed hold the "crown," but the gap with representation-based methods (CoSENT and Sentence-BERT/RoBERTa) is not as large as I had imagined. Objectively speaking, on the ATEC and BQ tasks, there is no significant difference between interaction-based Interact and representation-based CoSENT, while on the LCQMC task, there is no significant difference between interaction-based Interact and representation-based Sentence-BERT/RoBERTa.

The only place where a clear gap opens up is PAWSX. In Which Unsupervised Semantic Similarity Method Is Best? A Fairly Comprehensive Evaluation and Is It Still SOTA on Chinese Tasks? We Ran Some Additional Experiments on SimCSE, we found that almost all unsupervised sentence-vector methods fail on PAWSX. Why is that? Because the negative samples in PAWSX are almost all "adversarial samples" — that is, negative pairs with extremely high lexical overlap but different semantics. So, for this kind of "high-difficulty" negative sample that causes unsupervised methods to "collapse across the board," even training with labeled data naturally requires deeper interaction to identify them well.

Theoretical Limit

Some readers might wonder: can we theoretically derive the limit of what representation-based approaches can achieve? Surprisingly, this analysis is actually not hard, and the answer is:

In theory, whatever interaction-based methods can achieve, representation-based methods can "almost" achieve as well.

How do we arrive at this conclusion? In fact, articles we've previously covered on this blog are sufficient. First, let's assume that the similarity of a sample pair lies between 0 and 1, and that sample pairs are unordered, i.e., $\text{sim}(x,y)=\text{sim}(y,x)$. Then, if we have $n$ samples, computing the similarity between every pair of samples (regardless of how the actual similarity is computed) gives us a similarity matrix $S$, which is a "positive definite symmetric matrix" (or, to be strict, positive semi-definite). By results from linear algebra, the SVD decomposition of a positive definite symmetric matrix must take the form $S=U\Lambda U^{\top}$, where $U$ is an orthogonal matrix and $\Lambda$ is a diagonal matrix, so we have $S=U\Lambda U^{\top}=(U\sqrt{\Lambda})(U\sqrt{\Lambda})^{\top}$. This shows that a positive definite symmetric matrix can always be decomposed into the form $S=BB^{\top}$, which is equivalent to saying that each sample $i$ can be represented as a $n$-dimensional vector $v_i$, such that $S_{i,j}=\langle x_i, y_j\rangle$.

At this point, all our results are theoretically guaranteed and exactly equal — the only issue is that the current "$n$-dimensional vector" is far too large, so we should next think in terms of dimensionality reduction. This is where the "JL Lemma" we introduced last year (see The Astonishing Johnson–Lindenstrauss Lemma: Theory) comes into play. It tells us that, regardless of the original dimensionality, $n$ vectors can always be reduced to $\mathcal{O}(\log n)$ dimensions while approximately preserving inner products. In The Astonishing Johnson–Lindenstrauss Lemma: Applications, we also estimated that this order of magnitude should be around $8\log n$, so for BERT-base's 768-dimensional vectors, in theory there should be no problem fitting the pairwise similarities of millions of samples using inner products. So, an inner-product-based "representation-based" approach with a dimensionality of a few hundred should, in theory, be able to achieve interaction-based performance quite precisely.

So why is there such a clear gap between the two on a difficult dataset like PAWSX? My personal view is that this arises from a conflict between "the continuity of neural networks and the cosine metric" and "the inherent adversarial nature of text matching."

A neural network is itself a continuous function, and the encoder's job is to compress a sentence into a sentence vector, so the result is bound to have very good continuity — meaning here that a small change to a sentence leads to only a small change in the sentence vector. Likewise, cosine similarity also has very good continuity, i.e., if $\Delta v$ is small, then the difference between $\cos(u,v)$ and $\cos(u, v+\Delta v)$ is also small. So overall, "representation-based" approaches tend to have very good continuity. The problem is that human language is inherently adversarial — a tiny change in wording can cause a huge change in the annotated label. The classic example is adding the word "not," causing a so-called "semantic inversion" — in other words, continuity is inherently poor here.

As a result, on tasks like this, a "representation-based" approach with very good continuity finds it very difficult to fit a dataset with pronounced adversarial characteristics. Of course, as analyzed above, in theory it can still be fit — and in practice it can indeed be fit — but doing so requires training for quite a few more epochs to "grind away" the inherent continuity of the representation-based approach. However, more epochs also lead to more severe overfitting. This is why CoSENT's training loss can drop close to 0 (indicating its fitting capacity is not the issue), yet its validation performance still falls short of the interaction-based approach. As for the interaction-based approach, the model has access to both samples simultaneously from the very start, and in later layers it can freely learn to fit and amplify the differences between them. As a result, the conflict between continuity and adversariality is far less severe in the interaction-based approach, leading to better performance.

Summary

This post examined the performance gap between representation-based and interaction-based matching from both theoretical and experimental perspectives, and also discussed the problem of automatically searching for a threshold in multi-class classification.