Spectral Clustering of a skipgram model

Question

I have a model where I'm applying Spectral Clustering to frequencies of words. My pipeline consists in TF-IDF, followed by a LSA to 100 dimensions, and finally a Spectral Clustering, all of these operations using sklearn.

I'm trying to replace TF-IDF and LSA by a skipgram model.

With the LSA model, the vectors had only positive values, hence a cosine similarity that is also positive. However, using the skipgram model the word vectors also contain negative values, resulting in negative cosine similarities when words are antonyms.

The problem is that the Spectral Clustering in sklearn uses a normalized Laplacian of the cosine similarities, where the root square of the sum over rows is used to normalize. This results in inf or nan, and the Spectral Clustering does not work.

What is the correct way to handle this problem :

• compute the pairwise_kernels and then set the matrix in the [0; 1] range by doing (matrix + 1) / 2. In this case, antonyms would have a 0 similarity, and synonyms 1. Words without any relation would have a 0.5 value
• use the absolute value of the similarity. Antonyms would be similar, but it would make some sense for clustering.
• use another similarity. But from what I read, cosine is the best similarity for skipgram.
• use another clustering algorithm. But from my trials, Spectral Clustering gives the best clusters.

Answer 1

Choice of clustering algorithm

Although you've found spectral clustering to work best with TF-IDF and LSA, it sounds like you haven't tried it yet with skip-gram models. The results may be different, so you might want to explore. On the other hand, if spectral clustering has some desirable interpretation in the context of your problem, or you have strong reason to believe it will work well, stick with it. There's no particular need to abandon it on account of the inf/nan issue, since the similarities can be transformed to work with it.

Choice of similarity measure

A good choice of similarity measure depends on the data and what you're trying to learn. In general, cosine similarity (or some transformation of it) makes sense if you care about the angles between vectors and you don't care about their lengths. The fact that angle relates to semantic similarity in your problem suggests that this is a good option. On the other hand, length may carry relevant information as well in some contexts. For example, if you're using word2vec embeddings, have a look here and here. If you care about both length and angle, it would be more natural to use a similarity measure based on Euclidean distance. Recall that the cosine distance between two vectors ($1-\text{cosine similarity}$) is equal to two times the squared Euclidean distance after normalizing the vectors, since $\|a-b\|^2 = \|a\|^2 + \|b\|^2 - 2 a \cdot b$.

Nonnegative similarity measures for spectral clustering

If you want to stick with spectral clustering and cosine similarity, then you'll have to transform the cosine similarities to make them nonnegative. There are various ways to do this. As above, the important question is what you want the similarities to mean. For example, it sounds like you've identified a key issue: do you want antonyms to be considered similar (and be clustered together) or dissimilar (and end up in different clusters)?

1. If you want antonyms to be considered dissimilar, then the first option you mentioned $\frac{1}{2}(\text{cosine similarity} + 1)$ seems very reasonable, as similarity decreases monotonically with angle. It should behave analogously to cosine similarity, since it's a simple shift to make the minimum value equal to zero (scaling by $\frac{1}{2}$ doesn't actually matter).

2. Another, related option is the angular similarity $1 - \frac{\cos^{-1}(\text{cosine similarity})}{\pi}$. Here, the similarity decreases linearly with angle.

3. A further possibility is to compute distances, then transform them into similarities using the radial basis function kernel (a.k.a. heat kernel, as scikit-learn recommends):

$$s(a, b) = \exp \left[ -\frac{d(a,b)^2}{2 \sigma^2} \right]$$

where $d(a,b)$ denotes the distance between vectors $a$ and $b$, and $\sigma^2$ is a scale parameter that controls the kernel width (similarity decays more rapidly as $\sigma^2$ shrinks). One option for $d$ is to use the angular distance $\cos^{-1}(\text{cosine similarity})$, which measures the angle between $a$ and $b$ in radians. As in (1) and (2), the resulting similarity measure would decrease monotonically with angle. But, $\sigma^2$ can be used to control the rate of decay. If $\sigma^2$ is set to a small value, only closely related words will be considered similar, and both unrelated words and antonyms will be near-maximally dissimilar.

4. Same as (3), but use Euclidean distance for $d$. This would take both length and angle into account, as discussed above.