Improving zero-shot learning by mitigating the hubness problem

Introduction

Extensive research in computational linguistics and neural language modeling has shown that contextual co-occurrence patterns of words in corpora can be effectively exploited to learn high-quality vector-based representations of their meaning in an unsupervised manner (Collobert et al., 2011; Clark, 2015; Turney & Pantel, 2010). This has in turn led to the development of the so-called zero-shot learning paradigm as a way to address the manual annotation bottleneck in domains where other vector-based representations (e.g., images or brain signals) must be associated to word labels (Palatucci et al., 2009). The idea is to use the limited training data available to learn a general mapping function from vectors in the domain of interest to word vectors, and then apply the induced function to map vectors representing new entities (that were not seen in training) onto word space, retrieving the nearest neighbour words as their labels. This approach has originally been tested in neural decoding (Mitchell et al., 2008; Palatucci et al., 2009), where the task consists in learning a regression function from fMRI activation vectors to word representations, and then applying it to the brain signal of a concept outside the training set, in order to “read the mind” of subjects. In computer vision, zero-shot mapping of image vectors onto word space has been applied to the task of retrieving words to label images of objects outside the training inventory (Frome et al., 2013; Socher et al., 2013), as well as using the inverse language-to-vision mapping for image retrieval (Lazaridou et al., 2014a). Finally, the same approach has been applied in a multilingual context, using translation pair vectors to learn a cross-language mapping, that is then exploited to translate new words (Mikolov et al., 2013b).

Zero-shot learning is a very promising and general technique to reduce manual supervision. However, while all experiments above report very encouraging results, performance is generally quite low in absolute terms. For example, the system of Frome et al. (2013) returns the correct image label as top hit in less than 1% of cases in all zero-shot experiments (see their Table 2). Performance is always above chance, but clearly not of practical utility.

In this paper, we study one specific problem affecting the quality of zero-shot labeling, following up on an observation that we made, qualitatively, in our experiments: The neighbourhoods surrounding mapped vectors contain many items that are “universal” neighbours, that is, they are neighbours of a large number of different mapped vectors. The presence of such vectors, known as hubs, is an intrinsic problem of high-dimensional spaces (Radovanović et al., 2010b). Hubness has already been shown to be an issue for word-based vectors (Radovanović et al., 2010a).Radovanović et al. (2010a) propose a supervised hubness-reducing method for document vectors that is not extensible to the zero-shot scenario, as it assumes a binary relevance classification setup. However, as we show in Section 2, the problem is much more severe for neighbourhoods of vectors that are mapped onto a high-dimensional space from elsewhere through a regression algorithm. We leave a theoretical understanding of why hubness affects regression-based mappings to further work. Our current contributions are to demonstrate the hubness problem in the zero-shot setup, to present a simple and efficient method to get rid of it by adjusting the similarity matrix after mapping, and to show how this brings consistent performance improvements across different tasks. While one could address the problem by directly designing hubness-repellent mapping functions, we find our post-processing solution more attractive as it allows us to use very simple and general least-squares regression methods to train and perform the mapping.

We use use the term pivots to stand for a set of vectors we retrieve neighbours for (these comprise at least, in our setting, the zero-shot-mapped vectors) and targets for the subspace of vectors we retrieve the neighbours from (often, corresponding to the whole space of interest). Then, we can phrase our proposal as follows. Standard nearest neighbour queries rank the targets independently for each pivot. A single target is allowed to be the nearest neighbour, or among the top $k$ nearest neighbours, of a large proportion of pivots: and this is exactly what happens empirically (the hubness problem). We can greatly mitigate the problem by taking the global distribution of targets across pivots into account. In particular, we use the very straightforward and effective strategy of inverting the query: we convert the similarity scores of a target with all pivots to the corresponding ranks, and then retrieve the nearest neighbours of a pivot based on such ranks, instead of the original similarity scores. We will empirically show that with this method high-hubness targets are down-ranked for many pivots, and will kept as neighbours only when semantically appropriate.

Hubness in zero-shot mapping

where X and Y are matrices obtained through the concatenation of train source vectors and the target vectors of the corresponding labels.

Target space label retrieval

Given a source element $x\in S$ and its vector $\bm{\mathbf{x}}$, the standard way to retrieve a target space label ($T$) is by returning the nearest neighbour (according to some similarity measure) of mapped $\bm{\mathbf{x}}$ from the set of vector representations of $T$. Following common practice, we use the cosine as our similarity measure.

Hubness

We can measure how hubby an item $y\in T$ is with respect to a set of pivot vectors $P$ (where $T$ is the search space) by counting the number of times it occurs in the $k$-nearest neighbour lists of elements in $P$:

Hubness has been shown to be an intrinsic problem of high-dimensional spaces: as we increase the dimensionality of the space, a number of elements, which are, by all means, not similar to all other items, become hubs. As a results nearest neighbour queries return the hubs at top 1, harming accuracy. It is known that the problem of hubness is related to concentration, the tendency of pairwise similarities between elements in a set to converge to a constant as the dimensionality of the space increases (Radovanović et al., 2010b). Radovanović et al. (2010a) show that this also holds for cosine similarity (which is used almost exclusively in linguistic applications): the expectation of pairwise similarities becomes constant and the standard deviation converges to 0. This, in turn, is known to cause an increase in hubness.

Original vs. mapped vectors

In previous work we have (qualitatively) observed a tendency of the hubness problem to become worse when we query a target space in which some elements have been mapped from a different source space. In order to investigate this more closely, we compare the properties of mapped elements versus original ones. We consider word translation as an application and use 300-dimensional vectors of English words as source and vectors of Italian words as target. We have, in total, vocabularies of 200,000 English and Italian words, which we denote $S$ and $T$. We use a set of 5,000 translation pairs as training data and learn a linear map.

A globally corrected neighbour retrieval method

We first test our methods on bilingual lexicon induction. As the amount of parallel data is limited, there has been a lot of work on acquiring translation dictionaries by using vector-space methods on monolingual corpora, together with a small seed lexicon (Haghighi et al., 2008; Klementiev et al., 2012; Koehn & Knight, 2002; Rapp, 1999). One of the most straightforward and effective methods is to represent words as high-dimensional vectors that encode co-occurrence only with the words in the seed lexicon and are therefore comparable cross-lingually (Klementiev et al., 2012; Rapp, 1999). However, this method is limited to vector spaces that use words as context features, and does not extend to vector-based word representations relying on other kinds of dimensions, such as those neural language models that have recently been shown to greatly outperform context-word-based representations (Baroni et al., 2014). The zero-shot approach, that induces a function from one space to the other based on paired seed element vectors, and then applies it to new data, works irrespective of the choice of vector representation. This method has been shown to be effective for bilingual lexicon construction by Mikolov et al. (2013b), with Dinu & Baroni (2014) reporting overall better performance than with the seed-word-dimension method. We set up a similar evaluation on the task of finding Italian translations of English words.

The cbow method introduced by Mikolov et al. (2013a) induces vector-based word representations by trying to predict a target word from the words surrounding it within a neural network architecture. We use the word2vec toolkithttps://code.google.com/p/word2vec/ to learn 300-dimensional representations of 200,000 words with cbow. We consider a context window of 5 words to either side of the target, we set the sub-sampling option to 1e-05 and estimate the probability of a target word with the negative sampling method, drawing 10 samples from the noise distribution (Mikolov et al., 2013a). We use 2.8 billion tokens as input (ukWaC + Wikipedia + BNC) for English and the 1.6 billion itWaC tokens for Italian.Corpus sources: http://wacky.sslmit.unibo.it, http://en.wikipedia.org, http://www.natcorp.ox.ac.uk

Training and testing

Both train and test translation pairs are extracted from a dictionary built from Europarl, available at http://opus.lingfil.uu.se/ (Europarl, en-it) (Tiedemann, 2012). We use 1,500 English words split into 5 frequency bins as test set (300 randomly chosen in each bin). The bins are defined in terms of rank in the (frequency-sorted) lexicon: [1-5K], [5K-20K], [20K-50K], [50K-100K] and [100K-200K]. The bilingual lexicon acquisition literature generally tests on very frequent words only. Translating medium or low frequency words is however both more challenging and useful. We also sample the training translation pairs by frequency, using the top $1K$, $5K$, $10K$ and $20K$ most frequent translation pairs from our dictionary (by English frequency), while making sure there is no overlap with test elements.

Results

The elements with the largest hub score are shown in Figure 3 (left). As can be seen, they tend to be “garbage” low-frequency words. However, in any realistic setting such low-frequency terms should not be filtered out, as good translations might also have low frequency. As pointed out by Radovanović et al. (2010b), hubness correlates with proximity to the test-set mean vector (the average of all test vectors). Hubness level is plotted against cosine-to-mean in Figure 3 (right).

2 Zero-shot image labeling and retrieving

In this section we test our proposed method in a cross-modal setting, mapping images to word labels and vice-versa.

We use the data set of Lazaridou et al. (2014b) containing 5,000 word labels, each associated to 100 ImageNet pictures (Deng et al., 2009). Word representations are extracted from Wikipedia with word2vec in skip-gram mode. Images are represented by 4096-dimensional vectors extracted using the Caffe toolkit (Jia et al., 2014) together with the pre-trained convolutional neural network of Krizhevsky et al. (2012). We use a random 4/1 train/test split.

Results

conclusion

In this paper we have shown that the basic setup in zero-shot experiments (use multivariate linear regression with a regularized least-squares error objective to learn a mapping across representational vectors spaces) is negatively affected by strong hubness effects. We proposed a simple way to correct for this by replacing the traditional nearest neighbour queries with globally adjusted ones. The method only requires the availability of more, unlabeled source space data, in addition to the test instances. While more advanced ways for learning the mapping could be employed (e.g., incorporating hubness avoidance strategies into non-linear functions or different learning objectives), we have shown that consistent improvements can be obtained, in very different domains, already with our query-time correction of the basic learning setup, which is a popular and attractive one, given its simplicity, generality and high performance. In future work we plan to investigate whether the hubness effect carries through to other setups: For example, to what extent different kinds of word representations and other learning objectives are affected by it. This empirical work should pose a solid basis for a better theoretical understanding of the causes of hubness increase in cross-space mapping.

acknowledgments

This work was supported by the ERC 2011 Starting Independent Research Grant n. 283554 (COMPOSES).

References