Word Representations Concentrate and This is Good News! (2020)

Abstract: This article establishes that, unlike the legacy tf*idf representation, recent natural language representations (word embedding vectors) tend to exhibit a so-called concentration of measure phenomenon , in the sense that, as the representation size p and database size n are both large, their behavior is similar to that of large dimensional Gaussian random vectors. This phenomenon may have important consequences as machine learning algorithms for natural language data could be amenable to improvement, thereby providing new theoretical insights into the field of natural language processing.

## introduction one of the reasons of the success of deep learning (dnn) representations (such as image features or word embeddings) lies in their very high performing and stable behavior, when used for instance as inputs to classification or regression algorithms. we hypothesize that the underlying explanation is that, from the point of view of these learning algorithms, these (usually large dimensional) efficient representations exhibit a behavior "akin" (although formally different) to large dimensional random gaussian vectors. in a sense, one may think of these "compressed raw data" representations as being all the better than they have a large "entropy", i.e., that they are composed of independent and isotropic components (otherwise, according to information theory, one may compress them even more). however, large dimensional "gaussian-like" representation vectors @xmath0, thereby disrupting our standard approach to machine learning. in particular, they naturally suffer from various sources of the curse of dimensionality: for instance, from the law of large numbers, 1 p x 2 = 1 p p @xmath1, so that the representations, rather than occupying all of r p , concentrate at the edges of a sphere. worse, the normalized distance fortunately, these curses of dimensionality can be turned into blessings. again by (advanced versions of) the law of large numbers, the behavior of machine learning algorithms running on gaussianlike data becomes amenable to theoretical analysis, in particular using recent advances in the fields of large dimensional statistics and random matrix theory. therefore, these analyses allow for the performance prediction, improvement, and optimization of machine learning methods on real data. consequently, proving that data representations behave like gaussian vectors implies the possibility to theoretically control the learning algorithms designed to handle these data. in a recent line of works, couillet and co-authors suggest and theoretically support that dnn representations are indeed not gaussian per se, but closely resemble concentrated random vectors. by definition, a concentrated random vector @xmath2: in essence, concentration means that x does not converge (quite the opposite) but any scalar lipschitz observation g(x) ∈ r of x converges around its statistical mean when the size p of x increases; figure 1 schematically illustrates the concentration of measure phenomenon. in particular, a key property to the present article is that the distance between any two concentrated random vectors x 1 and x 2 with "nice properties" converges to a constant value, which only depends on the data statistics, and is in particular independent of their random re-alization. this fundamental phenomenon, not true for small data, is at the core of our present study. in detail, @xcite shows that natural images and their modern representations (such as vgg, resnet embeddings) can be appropriately modelled by concentrated random vectors: they precisely prove that the extremely realistic images produced by modern generative adversarial networks (gans) are by definition concentrated random vectors. besides, in louart and @xcite , the authors establish a universality result which proves that the performance of many machine learning algorithms -from support vector machines to (kernel) spectral clustering -applied to concentrated random data is asymptotically foot_0 the same as if the data had been gaussian random vectors with the same first and second order statistics. these findings have important consequences to modern machine learning: they in particular ensure that even involved algorithms applied to real data are analytically tractable, and that their performances can be anticipated and improved offline (without the need for cross-validation). as (possibly large dimensional) vector representations of words and documents have become a basic building block of many natural language processing methods @xcite , in particular since the success of word embeddings such as word2vec @xcite and glove foot_1 @xcite , two natural questions arise: (i) do word (and document) representations exhibit concentration of measure phenomena?, and (ii) do some of the aforementioned findings on real images extend to words and textual documents? the present article empirically investigates this question and claims to reach a positive answer foot_2 . specifically, the main contributions of the article are as follows: related works. several works similarly tried to reinterpret word embeddings, either in terms of matrix factorization @xcite or latent models @xcite , and to account for the associations and analogies typical of the linear behavior of these embeddings @xcite @xcite @xcite . in a different line of research, many attempts were made to understand the syntactic and semantic generalization capabilities of different deep learning models based on word embeddings, as in dessì and baroni (2019); hewitt and manning (2019); lakretz et al. (2019); chi et al. (2020) to list a few. our approach is however different in its trying to statistically model word embeddings so to grasp the behavior of related machine learning algorithms. to the best of the authors' knowledge, this the first time this approach is being investigated. ## application to supervised learning the concentration of measure phenomenon in real data (equation ( 1 )) has a fundamental advantage: the performance of many learning algorithms become predictable and, consequently, amenable to improvement. the results of the previous section therefore strongly suggest that, for the first time to the authors' knowledge, one can predict to some extent (so long that the non-trivial conditions are met for the processed data) the performance of a host of machine learning algorithms for natural language processing. specifically, we consider here the standard leastsquare kernel support vector machine (lssvm) classifier @xcite for text classification with some refinement), with kernel @xmath3,@xmath4, for some function f to be specified. the lssvm classifier allocates the class of a new datum x based on its position with respect to a hyperplane in kernel space designed from the training set x. although not directly a spectral method (as in the unsupervised spectral clustering algorithm @xcite ), for large n, p, the lssvm classifier inherently exploits the eigenspectrum of the kernel matrix k and its performance is proved in @xcite to be asymptotically predictable (for large enough p, n) and in closed form (which is thus simpler than the margin-based svm, whose asymptotic performances do not admit a closed form). precisely, the class c 1 or c 2 allocated to x is the result of the binary test g(x) in @xcite , the authors precisely show that, for a two-class mixture of concentrated random vectors with means µ 1 , µ 2 and covariances c 1 , c 2 , as n, @xmath5, for x genuinely in class c i , figure 5 reports the performances of lssvm as a function of the ratio f (τ p )/f (τ p ), where τp ≡ 1 n(n-1) 1≤@xmath6, here for two kernels: (a) the second order polynomial kernel such that f (τ p ) = 4, f (τ p ) = 1 and f (τ p ) varying from -2 to 1, and (b) the rbf kernel with bandwidth σ 2 such that -2σ 2 varies from -2 to 0 (of course -2σ 2 cannot be positive). the benchmark dataset are the yahoo answer classes "cult" versus "education", the feature vectors of which are either (ii) tf*idf based weighted averages of glove embedding (@xmath7, (iii) tf*idf based weighted averages of word2vec embeddings (@xmath8. a comparison to (i) gaussian input data vectors is also provided for reference (@xmath9. in each experiment, the number of training data is @xmath10. figure 5 first shows a trend for the performances to converge, as the results for both @xmath11: as such, these performances are not random and then possibly amenable to theoretical analysis. more in detail, figure 5 demonstrates that, for the tf*idf representation, the theoretical equivalent for concentrated vectors (red) and the empirical performance (blue) are quite different, clearly confirming that tf*idf representations are not appropriately modelled by concentrated vectors. this is again no surprise as these vectors are intrinsically sparse, which concentrated vectors cannot be. the case of word2vec and glove is more interesting as figure 5 reports an extremely accurate fit between theory and practice for f (τ p )/f (τ p ) below -1 and above .5. more crucially, in these regions, the performances for both the rfb kernel and the polynomial kernel with f (τ p )/f (τ p ) = -2σ 2 perfectly coincide, so that real data performance corroborates the theory. only the region [-1, .5] shows a severe discrepancy. this is explained by two factors: (a) for any kernel (here for the polynomial kernel), @xcite shows that the region where f (τ p ) 0 is particularly unstable to "strongly mean-discriminative data", i.e., data mixtures strongly identifiable from their statistical means; this is what is observed here with a vanishing performance (dropping to 50%) when f (τ p ) = 0, inducing instability; at this point of our analysis though, we cannot explain the performance increase near 0 -predicted by the theory while the empirical performance monotonously drops; (b) for the rbf kernel, in the vicinity of σ 2 ∼ 0, the entries of k degenerate; k becomes sparse, which goes against concentration; this is already observed for gaussian inputs (top display); this gap can only be covered with larger p, n values. ## concluding remarks the results of this article may scratch the surface of a new mathematical theory for harnessing modern natural language processing representations: recent word and document features (word2vec and glove) were shown here to exhibit some key characteristics of concentrated random vectors, which tf*idf maps do not. this, as a consequence of recent works on the analysis of machine learning algorithms for concentration random vectors, opens the path to theoretical analyses, improved understanding, finetuned and new algorithms for natural language data processing. yet, the preliminary conclusions of the present article are less compelling than similar conclusions drawn for image representations (e.g., in @xcite ; @xcite , where the performance predictions on real images are extremely accurate for wide ranges of hyperparameters). this may be interpreted in two ways: either the document representation (glove and word2vec) need be perfected to be as discriminative and "maximum entropic" foot_10 as vgg or resnet are for images, or the concentration power of document embeddings is intrinsically weaker than image embeddings. if the latter hypothesis is correct, further mathematical efforts are needed to improve our understanding of these "weakly concentrated" data models. we plan to investigate these points in the future.