Year: 2018

Abstract:
We propose a simple and robust non-parameterized approach for building sentence representations. Inspired by the Gram-Schmidt Process in geometric theory, we build an orthogonal basis of the subspace spanned by a word and its surrounding context in a sentence. We model the semantic meaning of a word in a sentence based on two aspects. One is its relatedness to the word vector subspace already spanned by its contextual words. The other is the word’s novel semantic meaning which shall be introduced as a new basis vector perpendicular to this existing subspace. Following this motivation, we develop an innovative method based on orthogonal basis to combine pre-trained word embeddings into sentence representations. This approach requires zero training and zero parameters, along with efficient inference performance. We evaluate our approach on 11 downstream NLP tasks. Experimental results show that our model outperforms all existing zero-training alternatives in all the tasks and it is competitive to other approaches relying on either large amounts of labelled data or prolonged training time.

heading: 1 INTRODUCTION
text: The concept of word embeddings has been prevalent in NLP community in recent years, as they can characterize semantic similarity between any pair of words, achieving promising results in a large number of NLP tasks (Mikolov et al., 2013; Pennington et al., 2014; Salle et al., 2016). However, due to the hierarchical nature of human language, it is not sufficient to comprehend text solely based on isolated understanding of each word. This has prompted a recent rise in search for semantically robust embeddings for longer pieces of text, such as sentences and paragraphs.
Based on learning paradigms, the existing approaches to sentence embeddings can be categorized into two categories: i) parameterized methods and ii) non-parameterized methods.
Parameterized sentence embeddings. These models are parameterized and require training to optimize their parameters. SkipThought (Kiros et al., 2015) is an encoder-decoder model that predicts adjacent sentences. Pagliardini et al. (2018) proposes an unsupervised model, Sent2Vec, to learn an n-gram feature in a sentence to predict the center word from the surrounding context. Quick thoughts (QT) (Logeswaran & Lee, 2018) replaces the encoder with a classifier to predict context sentences from candidate sequences. Khodak et al. (2018) proposes à la carte to learn a linear mapping to reconstruct the center word from its context. Conneau et al. (2017) generates the sentence encoder InferSent using Natural Language Inference (NLI) dataset. Universal Sentence Encoder (Yang et al., 2018; Cer et al., 2018) utilizes the transformer (Vaswani et al., 2017) for sentence embeddings. The model is first trained on large scale of unsupervised data from Wikipedia and forums, and then trained on the Stanford Natural Language Inference (SNLI) dataset. Wieting & Gimpel (2017) propose the gated recurrent averaging network (GRAN), which is trained on Paraphrase Database (PPDB) and English Wikipedia. Subramanian et al. (2018) leverages a multi-task learning framework to generate sentence embeddings. Wieting et al. (2015a) learns the paraphrastic sentence representations as the simple average of updated word embeddings.
Non-parameterized sentence embedding. Recent work (Arora et al., 2017) shows that, surprisingly, a weighted sum or transformation of word representations can outperform many sophisticated neural network structures in sentence embedding tasks. These methods are parameter-free and require no further training upon pre-trained word vectors. Arora et al. (2017) constructs a sentence embedding called SIF as a sum of pre-trained word embeddings, weighted by reverse document
frequency. Rücklé et al. (2018) concatenates different power mean word embeddings as a sentence vector in p-mean. As these methods do not have a parameterized model, they can be easily adapted to novel text domains with both fast inference speed and high-quality sentence embeddings. In view of this trend, our work aims to further advance the frontier of this group and make its new state-of-the-art.
In this paper, we propose a novel sentence embedding algorithm, Geometric Embedding (GEM), based entirely on the geometric structure of word embedding space. Given a d-dim word embedding matrix A ∈ Rd×n for a sentence with n words, any linear combination of the sentence’s word embeddings lies in the subspace spanned by the n word vectors. We analyze the geometric structure of this subspace in Rd. When we consider the words in a sentence one-by-one in order, each word may bring in a novel orthogonal basis to the existing subspace. This new basis can be considered as the new semantic meaning brought in by this word, while the length of projection in this direction can indicate the intensity of this new meaning. It follows that a word with a strong intensity should have a larger influence in the sentence’s meaning. Thus, these intensities can be converted into weights to linearly combine all word embeddings to obtain the sentence embedding. In this paper, we theoretically frame the above approach in a QR factorization of the word embedding matrix A. Furthermore, since the meaning and importance of a word largely depends on its close neighborhood, we propose the sliding-window QR factorization method to capture the context of a word and characterize its significance within the context.
In the last step, we adapt a similar approach as Arora et al. (2017) to remove top principal vectors before generating the final sentence embedding. This step is to ensure commonly shared background components, e.g. stop words, do not bias sentence similarity comparison. As we build a new orthogonal basis for each sentence, we propose to have disparate background components for each sentence. This motivates us to put forward a sentence-specific principal vector removal method, leading to better empirical results.
We evaluate our algorithm on 11 NLP tasks. In all of these tasks, our algorithm outperforms all non-parameterized methods and many parameterized approaches. For example, compared to SIF (Arora et al., 2017), the performance is boosted by 5.5% on STS benchmark dataset, and by 2.5% on SST dataset. Plus, the running time of our model compares favorably with existing models.
The rest of this paper is organized as following. In Section 2, we describe our sentence embedding algorithm GEM. We evaluate our model on various tasks in Section 3 and Section 4. Finally, we summarize our work in Section 5.

heading: 2 APPROACH

heading: 2.1 QUANTIFY NEW SEMANTIC MEANING
text: Let us consider the idea of word embeddings (Mikolov et al., 2013), where a word wi is projected as a vector vwi ∈ Rd. Any sequence of words can be viewed as a subspace in Rd spanned by its word vectors. Before the appearance of the ith word, S is a subspace in Rd spanned by {vw1 ,vw2 , ...,vwi−1}. Its orthonormal basis is {q1, q2, ..., qi−1}. The embedding vwi of the ith word wi can be decomposed into
vwi = i−1∑ j=1 rjqj + riqi
rj = q T j vwi
ri = ‖vwi − i−1∑ j=1 rjqj‖2
(1)
where ∑i−1 j=1 rjqj is the part in vwi that resides in subspace S, and qi is orthogonal to S and is to be added to S. The above algorithm is also known as Gram-Schmidt Process. In the case of rank deficiency, i.e., vwi is already a linear combination of {q1, q2, ...qi−1}, qi is a zero vector and ri = 0. In matrix form, this process is also known as QR factorization, defined as follows.
QR factorization. Define an embedding matrix of n words as A = [A:,1,A:,2, ...,A:,n] ∈ Rd×n, where A:,i is the embedding of the ith word wi in a word sequence (w1, . . . , wi, . . . , wn). A ∈ Rd×n can be factorized intoA = QR, where the non-zero columns inQ ∈ Rd×n are the orthonormal basis, andR ∈ Rn×n is an upper triangular matrix. The process above computes the novel semantic meaning of a word w.r.t all preceding words. As the meaning of a word influences and is influenced by its close neighbors, we now calculate the novel orthogonal basis vector qi of each word wi in its neighborhood, rather than only w.r.t the preceding words.
Definition 1 (Contextual Window Matrix) Given a word wi, and its m-neighborhood window inside the sentence (wi−m, . . . , wi−1, wi, wi+1, . . . , wi+m) , define the contextual window matrix of word wi as:
Si = [vwi−m , . . . ,vwi−1 ,vwi+1 , . . . ,vwi+m ,vwi ] ∈ Rd×(2m+1) (2)
Here we shuffle vwi to the end of S i to compute its novel semantic information compared with its context. Now the QR factorization of Si is
Si = QiRi (3)
Note that qi is the last column ofQi, which is also the new orthogonal basis vector to this contextual window matrix.
Next, in order to generate the embedding for a sentence, we will assign a weight to each of its words. This weight should characterize how much new and important information a word brings to the sentence. The previous process yields the orthogonal basis vector qi. We propose that qi represents the novel semantic meaning brought by word wi. We will now discuss how to quantify i) the novelty of qi to other meanings in wi, ii) the significance of qi to its context, and iii) the corpus-wise uniqueness of qi w.r.t the whole corpus.

heading: 2.2 NOVELTY
text: We propose that a word wi is more important to a sentence if its novel orthogonal basis vector qi is a large component in vwi . This can be quantified as a novelty score:
αn = exp(r−1/‖vwi‖2) = exp(r−1/‖r‖2) (4) where r is the last column ofRi, and r−1 is the last element of r.
Connection to least square. From QR factorization theory, the novel orthogonal basis qi is also the normalized residual in the least square problem min ‖Cx − vwi‖2, i.e. qTi vwi = r−1 = min ‖Cx − vwi‖2, where C = Si:,1:2m. And qTi vwi = r−1 is the minimum distance from word vector vwi to the hyper-plane spanned by wi’s context words wi−m, . . . , wi−1, wi+1, . . . , wi+m.
It follows that αn is the exponential of the normalized distance between vwi and the subspace spanned by its context.

heading: 2.3 SIGNIFICANCE
text: The significance of a word is related to how semantically aligned it is to the meaning of its context. To identify principal directions, i.e. meanings, in the contextual window matrix Si, we employ Singular Value Decomposition.
Singular Value Decomposition. Given a matrix A ∈ Rd×n, there exists U ∈ Rd×n with orthogonal columns, diagonal matrix Σ = diag(σ1, ..., σn), σ1 ≥ σ2 ≥ ... ≥ σn ≥ 0, and orthogonal matrix V ∈ Rn×n, such thatA = UΣV T . The columns of U , {U:,j}nj=1, are an orthonormal basis of A’s columns subspace and we propose that they represent a set of semantic meanings from the context. Their corresponding singular values {σj}nj=1, denoted by σ(A), represent the importance associated with {U:,j}nj=1. The SVD of wi’s contextual window matrix is Si = U iΣiV iT ∈ Rd×(2m+1). It follows that qTi U i is the coordinate of qi in the basis of {U i:,j} 2m+1 j=1 .
Intuitively, a word is more important if its novel semantic meaning has a better alignment with more principal meanings in its contextual window. This can be quantified as ‖σ(Si) (qTi U i)‖2, where denotes element-wise product. Therefore, we define the significance of wi in its context to be:
αs = ‖σ(Si) (qTi U i)‖2
2m+ 1 (5)
It turns out αs can be rewritten as
αs = ‖qTi U iΣi‖2 2m+ 1 = ‖qTi U iΣiV i‖2 2m+ 1 = ‖qTi Si‖2 2m+ 1 = qTi vwi 2m+ 1 = r−1 2m+ 1 (6)
We use the fact that V i is an orthogonal matrix and qi is orthogonal to all but the last column of Si, vwi . Therefore, αs is essentially the distance between wi and the context hyper-plane, normalized by the context size.

heading: 2.4 CORPUS-WISE UNIQUENESS
text: Similar to the idea of inverse document frequency (IDF) (Sparck Jones, 1972), a word that is commonly present in the corpus is likely to be a stop word, thus its corpus-wise uniqueness is small. In our solution, we compute the principal directions of the corpus and then measure their alignment with the novel orthogonal basis vector qi. If there is a high alignment, wi will be assigned a relatively low corpus-wise uniqueness score, and vice versa.

heading: 2.4.1 COMPUTE PRINCIPAL DIRECTIONS OF CORPUS
text: As proposed in Arora et al. (2017), given a corpus containing a set of sentences, each sentence embedding is first computed as a linear combination of its word embeddings, thus generating a sentence embedding matrix X = [c1, c2, . . . , cN ] ∈ Rd×N for a corpus S with N sentences. Then principal vectors ofX are computed.
In comparison, we do not form the sentence embedding matrix X after we finalize the sentence embedding. Instead, we obtain an intermediate coarse-grained sentence embedding matrix Xc = [g1, . . . , gN ] as follows. Suppose the SVD of the sentence matrix of the ith sentence is S = [vw1 , . . . ,vwn ] = UΣV
T . Then the coarse-grained embedding for the ith sentence is defined as:
gi = n∑ j=1 f(σj)U:,j (7)
where f(σj) is a monotonically increasing function. We then compute the top K principal vectors {d1, ...,dK} ofXc, with singular values σ1 ≥ σ2 ≥ ... ≥ σK .

heading: 2.4.2 UNIQUENESS SCORE
text: In contrast to Arora et al. (2017), we select different principal vectors of Xc for each sentence, as different sentences may have disparate alignments with the corpus. For each sentence, {d1, ...,dK} are re-ranked in descending order of their correlation with sentence matrix S. The correlation is defined as oi = σi‖STdi‖2, 1 ≤ i ≤ K. Next, the top h principal vectors after re-ranking based on oi are selected: D = {dt1 , ...,dth}, with ot1 ≥ ot2 ≥ ... ≥ oth and their singular values in Xc are σd = [σt1 , ..., σth ] ∈ Rh. Finally, a word wi with new semantic meaning vector qi in this sentence will be assigned a corpuswise uniqueness score:
αu = exp (−‖σd (qTi D)‖2/h) (8)
This ensures that common stop words will have their effect diminished since their embeddings are closely aligned with the corpus’ principal directions.

heading: 2.5 SENTENCE VECTOR
text: A sentence vector cs is computed as a weighted sum of its word embeddings, where the weights come from three scores: a novelty score (αn), a significance score (αs) and a corpus-wise uniqueness score (αu).
αi = αn + αs + αu cs = ∑ i αivwi (9)
We provide a theoretical explanation of Equation (9) in Appendix.
Sentence-Dependent Removal of Principal Components. Arora et al. (2017) shows that given a set of sentence vectors, removing projections onto the principal components of the spanned subspace can significantly enhance the performance on semantic similarity task. However, as each sentence may have a different semantic meaning, it could be sub-optimal to remove the same set of principal components from all sentences.
Therefore, we propose the sentence-dependent principal component removal (SDR), where we rerank top principal vectors based on correlation with each sentence. Using the method from Section 2.4.2, we obtain D = {dt1 , ...,dtr} for a sentence s. The final embedding of this sentence is then computed as:
cs ← cs − r∑ j=1 (dTtjcs)dtj (10)
Ablation experiments show that sentence-dependent principal component removal can achieve better result. The complete algorithm is summarized in Algorithm 1 with an illustration in Figure 1.

heading: 3 EXPERIMENTS

heading: 3.1 SEMANTIC SIMILARITY TASKS: STS BENCHMARK
text: We evaluate our model on the STS Benchmark (Cer et al., 2017), a sentence-level semantic similarity dataset from SemEval and SEM STS. The goal for a model is to predict a similarity score of two sentences given a sentence pair. The evaluation is by the Pearson’s coefficient r between humanlabeled similarity (0 - 5 points) and predictions.
Experimental settings. We report two versions of our model, one only using GloVe word vectors (GEM + GloVe), and the other using word vectors concatenated from LexVec, fastText and PSL (Wieting et al., 2015b) (GEM + L.F.P). The final similarity score is computed as an inner product of
Algorithm 1 Geometric Embedding (GEM) 1: Inputs:
A set of sentences S, vocabulary V , word embeddings {vw ∈ Rd |w ∈ V} 2: Outputs: Sentence embeddings {cs ∈ Rd | s ∈ S} 3: for ith sentence s in S do 4: Form matrix S ∈ Rd×n, S:,j = vwj and wj is the jth word in s 5: The SVD is S = UΣV T 6: The ith column of the coarse-grained sentence embedding matrixXc:,i is U(σ(S)) 3 7: end for 8: Take first K singular vectors {d1, ...,dK} and singular values σ1 ≥ σ2 ≥ ... ≥ σK ofXc 9: for sentence s in S do
10: Re-rank {d1, ...,dK} in descending order by oi = σi‖STdi‖2, 1 ≤ i ≤ K. 11: Select top h principal vectors asD = [dt1 , ...,dth ], with singular values σd = [σt1 ...., σth ]. 12: for word wi in s do 13: Si = [vwi−m , ...,vwi−1 ,vwi+1 , ...,vwi+m ,vwi ] is the contextual window matrix of wi. 14: Do QR decomposition Si = QiRi, let qi and r denote the last column ofQi andRi 15: αn = exp(r−1/‖r‖2), αs = r−1/(2m+ 1), αu = exp (−‖σd (qTi D)‖2/h) 16: αi = αn + αs + αu 17: end for 18: cs = ∑ vi∈s αivwi 19: Principal vectors removal: cs ← cs −DDT cs 20: end for
Non-parameterized models dev test
GEM + L.F.P 82.1 77.5 GEM + LexVec 81.9 76.5
SIF (Arora et al., 2017) 80.1 72.0 LexVec 58.78 50.43 L.F.P 62.4 52.0
word2vec skipgram 70.0 56.5 Glove 52.4 40.6 ELMo 64.6 55.9
Parameterized models
Reddit + SNLI (Yang et al., 2018) 81.4 78.2 GRAN (Wieting & Gimpel, 2017) 81.8 76.4 InferSent (Conneau et al., 2017) 80.1 75.8
Sent2Vec (Pagliardini et al., 2018) 78.7 75.5 Paragram-Phrase (Wieting et al., 2015a) 73.9 73.2
Table 1: Pearson’s r× 100 on STSB
GEM + L.F.P 48.97 Reddit + SNLI tuned 47.44
KeLP-contrastive1 49.00 SimBow-contrastive2 47.87
SimBow-primary 47.22
Table 2: MAP on CQA subtask B
normalized sentence vectors. Since our model is non-parameterized, it does not utilize any information from the dev set when evaluating on the test set and vice versa. Hyper-parameters are chosen at m = 7, h = 17, K = 45, and t = 3 by conducing hyper-parameters search on dev set. Results on the dev and test set are reported in Table 1. As shown, on the test set, our model has a 5.5% higher score compared with another non-parameterized model SIF, and 25.5% higher than the baseline of averaging L.F.P word vectors. It also outperforms most parameterized models including GRAN, InferSent, and Sent2Vec. Of all evaluated models, our model only ranks second to Reddit + SNLI, which is trained on the Reddit conversations dataset (600 million sentence pairs) and SNLI (570k sentence pairs). In comparison, our proposed method requires no external data and no training.

heading: 3.2 SEMANTIC SIMILARITY TASKS: CQA
text: We evaluate our model on subtask B of the SemEval Community Question Answering (CQA) task, another semantic similarity dataset. Given an original question Qo and a set of the first ten related questions (Q1, ..., Q10) retrieved by a search engine, the model is expected to re-rank the related questions according to their similarity with respect to the original question. Each retrieved question Qi is labelled “PerfectMatch”, “Relevant” or “Irrelevant”, with respect to Qo. Mean average precision (MAP) is used as the evaluation measure.
We encode each question text into a unit vectoru. Retrieved questions {Qi}10i=1 are ranked according to their cosine similarity with Qo. Results are shown in Table 2. For comparison, we include results from the best models in 2017 competition: SimBow (Charlet & Damnati, 2017), KeLP (Filice et al., 2017), and Reddit + SNLI tuned. Note that all three benchmark models require training, and SimBow and KeLP leverage optional features including usage of comments and user profiles. In comparison, our model only uses the question text without any training. Our model clearly outperforms both Reddit + SNLI tuned and SimBow-primary, and on par with KeLP model.

heading: 3.3 SUPERVISED TASKS
text: We further test our model on nine supervised tasks, including seven classification tasks: movie review (MR) (Pang & Lee, 2005), Stanford Sentiment Treebank (SST) (Socher et al., 2013), questiontype classification (TREC) (Voorhees & Dang, 2003), opinion polarity (MPQA) (Wiebe et al., 2005), product reviews (CR) (Hu & Liu, 2004), subjectivity/objectivity classification (SUBJ) (Pang & Lee, 2004) and paraphrase identification (MRPC) (Dolan et al., 2004). We also evaluate on SICK similarity (SICK-R), the SICK entailment (SICK-E) (Marelli et al., 2014). The sentence embeddings generated are fixed and only the downstream task-specific neural structure is learned. The four hyper-parameters are chosen the same as in STS benchmark experiment. Results are in Table 3.
GEM outperforms all non-parameterized sentence embedding models, including SIF, p-mean (Rücklé et al., 2018), and BOW on GloVe. It also compares favorably with most of parameterized models, including à la carte (Khodak et al., 2018), FastSent (Hill et al., 2016), InferSent, QT, Sent2Vec, SkipThought-LN (with layer normalization) (Kiros et al., 2015), SDAE (Hill et al., 2016), STN (Subramanian et al., 2018) and USE (Yang et al., 2018). Note that sentence representations generated by GEM have much smaller dimension compared to most of benchmark models, and the subsequent neural structure has fewer learnable parameters. The fact that GEM does well on several classification tasks (e.g. TREC and SUBJ) indicates that the proposed weight scheme is able to recognize important words in the sentence. Also, GEM’s competitive performance on sentiment tasks shows that exploiting the geometric structures of two sentence subspaces is beneficial.

heading: 4 DISCUSSION
text: Ablation Study. As shown in in Table 4, every GEM weight (αn, αs, αu) and proposed principal components removal methods contribute to the performance. As listed on the left, adding GEM weights improves the score by 8.6% on STS dataset compared with averaging three concatenated word vectors. The sentence-dependent principal component removal (SDR) proposed in GEM improves 0.3% compared to directly removing the top h corpus principal components (SIR). Using GEM weights and SDR together yields an overall improvement of 19.7%. As shown on the right in Table 4, every weight contributes to the performance of our model. For example, three weights altogether improve the score in SUBJ task by 0.38% compared with only using αn.
Sensitivity Study. We evaluate the effect of all four hyper-parameters in our model: the window size m in the contextual window matrix, the number of candidate principal components K, the number of principal components to remove h, and the power of the singular value in coarse sentence embedding, i.e. the power t in f(σj) = σtj in Equation (7). We sweep the hyper-parameters and test on STSB dev set, SUBJ, and MPQA. Unspecified parameters are fixed at m = 7, K = 45, h = 17 and t = 3. As shown in Figure 2, our model is quite robust with respect to hyper-parameters.
Inference speed. We also compare the inference speed of our algorithm on the STSB test set with the benchmark models SkipThought and InferSent. SkipThought and InferSent are run on a NVIDIA Tesla P100, and our model is run on a CPU (Intel R© Xeon R© CPU E5-2690 v4 @2.60GHz). For fair comparison, batch size in InferSent and SkipThought is set to be 1. The results are shown in Table 5. It shows that without acceleration from GPU, our model is still faster than InferSent and is 54% faster than SkipThought.

heading: 5 CONCLUSIONS
text: We proposed a simple non-parameterized method 1 to generate sentence embeddings, based entirely on the geometric structure of the subspace spanned by word embeddings. Our sentence embedding evolves from the new orthogonal basis vector brought in by each word, which represents novel semantic meaning. The evaluation shows that our method not only sets up the new state-of-the-art of non-parameterized models but also performs competitively when compared with models requiring either large amount of training data or prolonged training time. In future work, we plan to consider multi-characters, i.e. subwords, into the model and explore other geometric structures in sentences.

heading: A PROOF
text: The novelty score (αn), significance score (αs) and corpus-wise uniqueness score (αu) are larger when a word w has relatively rare appearance in the corpus and can bring in new and important semantic meaning to the sentence.
Following the section 3 in Arora et al. (2017), we can use the probability of a word w emitted from sentence s in a dynamic process to explain eq. (9) and put this as following Theorem with its proof provided below.
Theorem 1. Suppose the probability that word wi is emitted from sentence s is2:
p[wi|cs] ∝ ( exp(〈cs,vwi〉)
Z + exp(−(αn + αs + αu))) (11) where cs is the sentence embedding, Z = ∑ wi∈V exp(〈cs,vwi〉) and V denotes the vocabulary. Then when Z is sufficiently large, the MLE for cs is:
cs ∝ ∑ wi∈s (αn + αs + αu)vwi (12)
Proof: According to Equation (11),
p[wi|cs] = 1 N ( exp(〈cs,vwi〉) Z + exp(−(αn + αs + αu))) (13)
Where N and Z are two partition functions defined as N = 1 + ∑ wi∈V exp(−(αn(wi) + αs(wi) + αu(wi)))
Z = ∑ wi∈V exp(〈cs,vwi〉) (14)
The joint probability of sentence s is then p[s|cs] = ∏ wi∈s p(wi|cs) (15)
To simplify the notation, let α = αn +αs +αu. It follows that the log likelihood f(wi) of word wi emitted from sentence s is given by
fwi(cs) = log( exp(〈cs,vwi〉)
Z + e−α)− log(N) (16)
∇fwi(cs) = exp(〈cs,vwi〉)vwi
exp(〈cs,vwi〉) + Ze−α (17)
By Taylor expansion, we have
fwi(cs) ≈ fwi(0) +∇fwi(0)T cs
= constant + 〈cs,vwi〉 Ze−α + 1
(18)
Again by Taylor expansion on Z,
1 Ze−α + 1 ≈ 1 1 + Z +
Z
(1 + Z)2 α
≈ Z (1 + Z)2 α
≈ 1 1 + Z α
(19)
2The first term is adapted from Arora et al. (2017), where words near the sentence vector cs has higher probability to be generated. The second term is introduced so that words similar to the context in the sentence or close to common words in the corpus are also likely to occur.
The approximation is based on the assumption that Z is sufficiently large. It follows that,
fwi(cs) ≈ constant + α
1 + Z 〈cs,vwi〉 (20)
Then the maximum log likelihood estimation of cs is: cs ≈ ∑ wi∈s α 1 + Z vwi
∝ ∑ wi∈s (αn + αs + αu)vwi
(21)

heading: B EXPERIMENTAL SETTINGS
text: For all experiments, sentences are tokenized using the NLTK tokenizer (Bird et al., 2009) wordpunct tokenize, and all punctuation is skipped. f(σj) = σtj in Equation (7). In the STS benchmark dataset, our hyper-parameters are chosen by conducting parameters search on STSB dev set at m = 7, h = 17, K = 45, and t = 3. And we use the same values for all supervised tasks. The integer interval of parameters search are m ∈ [5, 9], h ∈ [8, 20], L ∈ [35, 75] (at stride of 5), and t ∈ [1, 5]. In CQA dataset, m and h are changed to 6 and 15, the correlation term in section 2.4.2 is changed to oi = ‖STdi‖2 empirically. In supervised tasks, same as Arora et al. (2017), we do not perform principal components in supervised tasks.

heading: C ENCODE A LONG SEQUENCE OF WORDS
text: We would like to give a clarification on encoding a long sequence of words, for example, a paragraph or a article. Specifically, the length n of the sequence is larger than the dimension d of pre-trained word vectors in this case. The only part in GEM relevant to the the length of the sequence n is the coarse embedding in Equation (7). The SVD of the sentence matrix of the ith sentence is still S ∈ Rd×n = [vw1 , . . . ,vwn ] = UΣV T , where now U ∈ Rd×d, Σ ∈ Rd×n, and V ∈ Rn×n. Note that the d + 1th column to nth column in Σ are all zero. And Equation (7) becomes gi =∑d j=1 f(σj)U:,j . The rest of the algorithm works as usual.

Review summaries:
Paper overview: This paper proposes a new geometry-based method for sentence embedding from word embedding vectors, inspired by Arora et al (2017). The idea is to quantify the novelty,significance and corpus-wise uniqueness of each word. In order to do so, they analyze geometrically how the word vector of the target word relates to 1) the subspace created by the word-vectors in its context 2) its alignment with the meanings in its context (using SVD) 3) its presence in the all the corpus. For each of these aspects, they output a score or weight. The final sentence representation is a weighted average, using these scores, of the word vectors of the sentence.