Word Representations Concentrate and This is Good News!

Proceedings of the 24th Conference on Computational Natural Language Learning, pages 325–334 Online, November 19-20, 2020. c⃝2020 Association for Computational Linguistics https://doi.org/10.18653/v1/P17 325 Word Representations Concentrate and This is Good News! Romain Couillet1, Yagmur Gizem Cinar2, Eric Gaussier2 and Muhammad Imran2 1LargeDATA chair, GIPSA-lab, University Grenoble-Alpes, Grenoble, France 2University Grenoble-Alpes, CNRS, LIG-Lab, Grenoble, France 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 conse- quences as machine learning algorithms for natural language data could be amenable to im- provement, thereby providing new theoretical insights into the field of natural language pro- cessing. 1 Introduction One of the reasons of the success of deep learn- ing (DNN) representations (such as image features or word embeddings) lies in their very high per- forming and stable behavior, when used for in- stance as inputs to classification or regression al- gorithms. We hypothesize that the underlying ex- planation is that, from the point of view of these learning algorithms, these (usually large dimen- sional) efficient representations exhibit a behavior “akin” (although formally different) to large dimen- sional random Gaussian vectors. In a sense, one may think of these “compressed raw data” repre- sentations 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 x ∈ Rp dis- play quite counter-intuitive behavior when com- pared to small dimensional data, thereby disrupting our standard approach to machine learning. In par- ticular, 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 i=1 x2 i tends to converge as p → ∞, so that the representations, rather than occupying all of Rp, concentrate at the 1edges of a sphere. Worse, the normalized distance p∥x1 − x2∥2 = 1 p∥x1∥2 + 1 p∥x2∥2 − 2 pxT 1 x2 ≃ 1 p∥x1∥2 + 1 p∥x2∥2 (due to 1 pxT 1 x2 → 0 for vectors of independent entries) loses the information of correlation between x1 and x2. Fortunately, these curses of dimensionality can be turned into blessings. Again by (advanced ver- sions of) the law of large numbers, the behavior of machine learning algorithms running on Gaussian- like data becomes amenable to theoretical analysis, in particular using recent advances in the fields of large dimensional statistics and random matrix the- ory. Therefore, these analyses allow for the perfor- mance prediction, improvement, and optimization of machine learning methods on real data. Conse- quently, proving that data representations behave like Gaussian vectors implies the possibility to the- oretically control the learning algorithms designed to handle these data. In …

Content truncated to 500 words