Calculating a Distributional Similarity Kernel using the Nyström Extension

The analysis of distributional similarities induced by word co-occurrences is an established tool for extracting semantically related words from a large text corpus. Based on the co-occurrence matrix C the basic kernel matrix K = CC ^T reflects word–word similarities. In order to considerably improve the results, a similarity kernel matrix is expressed as \(G\,=\,{U}_{k}{U}_{k}^{T}\), where U _k are the first k eigenvectors of the eigendecomposition K = UΣU ^T . Clearly, the bottleneck of this technique is the high computational demand for calculating the eigendecomposition. In our study we speed up the calculation of the low-rank similarity kernel by means of the Nyström extension. We address in detail the inherent challenge of the Nyström method, namely selecting appropriate kernel matrix columns in such a way that the fast approximation process yields satisfactory results. To illustrate the effectiveness of our method, we have built a thesaurus containing 32,000 entries based on 0.5 billion corpus words (nouns, verbs, adjectives and adverbs) extracted from the Project Gutenberg text collection.