Title: ENCODING WORD ORDER IN COMPLEX EMBEDDINGS

Abstract: Sequential word order is important when processing text. Currently, neural networks (NNs) address this by modeling word position using position embeddings. The problem is that position embeddings capture the position of individual words, but not the ordered relationship (e.g., adjacency or precedence) between individual word positions. We present a novel and principled solution for modeling both the global absolute positions of words and their order relationships. Our solution generalizes word embeddings, previously defined as independent vectors, to continuous word functions over a variable (position). The benefit of continuous functions over variable positions is that word representations shift smoothly with increasing positions. Hence, word representations in different positions can correlate with each other in a continuous function. The general solution of these functions is extended to complex-valued domain due to richer representations. We extend CNN, RNN and Transformer NNs to complex-valued versions to incorporate our complex embedding (we make all code available). Experiments 1 on text classification, machine translation and language modeling show gains over both classical word embeddings and position-enriched word embeddings. To our knowledge, this is the first work in NLP to link imaginary numbers in complexvalued representations to concrete meanings (i.e., word order).

1. INTRODUCTION:

When processing text, the sequential structure of language is important, but can be computationally costly to model with neural networks (NNs) (Socher et al., 2011) due to the difficulty in parallelization. This has been alleviated by modeling word sequence not on the NN architecture level, but by adding position embeddings on the feature level. This has been done by the convolutional sequence model (ConvSeq) (Gehring et al., 2017) and the Transformer model (Vaswani et al., 2017) that replaces recurrent and convolution operations with purely attention mechanisms. More generally, vanilla position embeddings (Gehring et al., 2017) assume that individual word positions are independent and do not consider relations between neighbouring word positions. We posit that both the global absolute positions of words and their inner sequential and adjacent relationships are crucial in language. This is supported by recent empirical findings by Shaw et al. (2018) and Dai et al. (2019) who show the importance of modeling distance between sequential elements, and explicitly use extra relative position encodings to capture the relative-distance relationship of words.

We present a novel and principled approach to model both the global absolute positions of words and their inner sequential and adjacent relationships as follows: we extend each word embedding, previously defined as an independent vector, as a continuous function over an independent variable i.e., position. The benefit of continuous functions over variable positions is that word representations shift smoothly with increasing positions. Hence, word representations in different positions show the real part of the embedding; the imaginary part has a π 2 phase difference and shows the same curves with its real-valued counterpart. The x-axis denotes the absolute position of a word and the y-axis denotes the value of each element in its word vector. Colours mark different dimensions of the embedding. The three cross points between the functions and each vertical line (corresponding to a specific position pos) represent the embedding for this word in the pos-th position.

can correlate with each other in a continuous function. Fig. 1 illustrates this type of word representation with a three-dimensional complex-valued embedding, where the amplitudes {r 1 , r 2 , r 3 } denote semantic aspects corresponding to classical word vectors, and periods {p 1 , p 2 , p 3 } denote how sensitive the word is to positional information. We further discuss the necessary properties of these functions to model sequential information and obtain a general solution in the form of a complexvalued embedding. Interestingly, there is a direct connection between a specific case of our general embedding and the well-known positional encoding in Vaswani et al. (2017) (see App. A).

We contribute (i) a novel paradigm that extends word vectors as continuous functions over changing variables like word position, and (ii) a general word embedding that models word order in a mathematically-sound manner. We integrate our complex word embeddings in state-of-the-art (SOTA) NN architectures (CNN, RNN, Transformer and experimentally find that it yields gains over both classical word embeddings and position-enriched word embeddings in text classification, machine translation and language modeling. Note that this is the first work in NLP to link imaginary numbers in complex-valued representation to concrete meanings (i.e., word order).

2. MODELLING WORD ORDER IN EMBEDDING SPACE:

A Word Embedding (WE) generally defines a map f we : N → R D from a discrete word index to a D-dimensional real-valued vector and N = {0, 1, 2, . . .}. Similarly, a Position Embedding (PE) (Gehring et al., 2017; Vaswani et al., 2017) defines another map f pe : N → R D from a discrete position index to a vector. The final embedding for word w j (w j ∈ W with index j in a given vocabulary W) in the pos-th position in a sentence is usually constructed by the sum

EQUATION

and f (j, pos) ∈ R D . Since both the word embedding map f w and the position embedding map f p only take integer values as word indexes or position indexes, embedding vectors for individual words or positions are trained independently. The independent training for each word vector is reasonable, since a word index is based on the order of a given arbitrary vocabulary and does not capture any specific sequential relationship with its neighboring words. However, the position index captures an ordered relationship, for instance adjacency or precedence, leading to the problem that position embeddings in individual positions (Gehring et al., 2017) are independent of each other; the ordered relationship between positions is not modelled. We refer to this as the position independence problem. This problem becomes more crucial when position embeddings are used in position-insensitive NNs, e.g., FastText (Mikolov et al., 2013b) , ConvSeq (Gehring et al., 2017) and Transformer (Vaswani et al., 2017) , because it is hard for such position-insensitive NNs with vanilla position embeddings (Gehring et al., 2017) to infer that w j1 in the pos-th position is close to w j2 in the pos + 1-th position, or that w j1 precedes w j2 ; instead, it is only inferred that w j1 and w j2 are in different positions, while the relative distance between them is almost unknown. Thus vanilla position embeddings (Gehring et al., 2017) cannot fully capture the sequential aspect of language.

Next, we first introduce the necessary properties to model word order in embeddings, and then give a unique solution to meet such properties.

2.1. EXTENDING VECTORS TO FUNCTIONS:

In the general definition in Eq. 1, each dimension of the position embedding is obtained based on the discrete position indexes {0, 1, 2, ..., pos, ...}. This makes it difficult to model the ordered relationship between the positions. One solution to this problem is to build continuous functions over a variable (i.e., position index) to represent a specific word in an individual dimension. Formally, we define a general embedding as

EQUATION

where g j is short for g we (j) ∈ (F) D , indicating D functions over position index pos, and g we (•) : N → (F) D is a mapping from a word index to D functions. By expanding the D dimension of g j , a word w j in the pos-th position can be represented as a D-dimensional vector as shown in

[g j,1 (pos), g j,2 (pos), ..., g j,D (pos)] ∈ R D , (3) in which ∀g j,d (•) ∈ F : N → R, d ∈ {1, 2, .

.., D} is a function over the position index pos. To move the word w j from the current position pos to another one pos , it needs only replace the variable pos to pos without changing g j .

Functions for words, especially continuous functions, are expected to capture smooth transformation from a position to its adjacent position therefore modeling word order. The position-independent position embedding (Gehring et al., 2017) can be considered as a special case of our definition when it only takes independent values for individual positions in the embedding function.

2.2. PROPERTIES FOR THE FUNCTIONS TO CAPTURE WORD ORDER:

Relative distance is hard to compute because position indices are not visible in NNs after vector embedding (discrete position indices are necessarily embedded as vectors like words to be backpropagated with the gradient). Hence, we claim that the modeling of relative distance in NNs should be position-free: absolute position indices cannot be directly accessed in intermediate layers. Instead of processing position-free operations in NNs to capture relative distance between words, prior work (Shaw et al., 2018; Dai et al., 2019) first calculates the relative distance between words, and then feeds the relative distance as an additional feature or as embeddings/weights to NNs, instead of directly feeding with the raw position indices.

Assume that words are embedded into R D , and let, for 1 ≤ d ≤ D, the function g j,d : N → R be the embedding function giving the d-th coordinate of the representation of word w j (i.e., g j,d (pos) is the d-th coordinate of the embedding of w j if it occurs at position pos. In the following, we simply write g instead of g j,d when there is no risk of confusion. Ideally, one would like there to exist a function Transform n : R → R that transforms the embedding of any word at some position pos to the embedding of a word at position pos + n such that Transform n is only dependent on the embedded value itself, but independent of the position pos, that is ∀pos : g(pos + n) = Transform n (g(pos)).

Prior work in NLP (Li et al., 2019 ), Information Retrieval (Van Rijsbergen, 2004) and Machine Learning (Trabelsi et al., 2017) has shown the usefulness of complex numbers as richer representations. Complex word embeddings (Wang et al., 2019; Li et al., 2019; Li et al., 2018) have been used to model language. To investigate the potential of complex-valued representation, we extend the target domains of g(•) from R D to C D without losing generality, since real-valued numbers are specific complex numbers with their imaginary part being zero. This property regarding "position-free offset transformation" in complex-valued domains is formally defined in Property 1 below.

Property 1. Position-free offset transformation: An embedding function g : N → C is said to be a position-free offset transformation if there exists a function Transform : N × C → C (called the witness) such that for all n ≥ 1, the function Transform n (•) = Transform(n, •) satisfies ∀pos ∈ N : g(pos + n) = Transform n (g(pos)). A position-free offset transformation g is said to be linearly witnessed if there is a function w : N → C such that g has a witness Transform satisfying, for all n, Transform(n, pos) = Transform n (pos) = w(n) (i.e., each Transform n is a linear function).

Additionally, a boundedness property is necessary to ensure that the position embedding can deal with text of any length (pos could be large in a long document).

Property 2. Boundedness: The function over the variable position should be bounded, i.e. ∃δ ∈

R + , ∀pos ∈ N, |g(pos)| ≤ δ.

Formally, we prove the following claim that there is a unique solution that meets Properties 1 and 2 under the condition that the embedding function is linearly witnessed. We use linear functions because they are well-understood and simple with a single floating-point operation in NNs. Claim 1. A function g : N → C is a bounded and linearly witnessed position-free offset transformation iff it is on the form g(pos

) = z 2 z pos 1 for z 1 , z 2 ∈ C with |z 1 | ≤ 1.

Proof. Assume that g is a bounded and linearly witnessed position-free offset transformation. Then, by linear witnessing, we have for all pos, n 1 , n 2 ∈ N:

w(n 1 )w(n 2 )g(pos) = w(n 2 )g(pos + n 1 ) = g(pos + n 1 + n 2 ) = Transform n1+n2 (g(pos)) = w(n 1 + n 2 )g(pos) whence w(n 1 +n 2 ) = w(n 1 )w(n 2 ). Write w(1) = z 1 and g(0) = z 2 . As n 1 , n 2 ∈ N were arbitrary, we have w(n) = (w(1)) n = z n 1 for all n ∈ N. But then g(pos + n) = w(n)g(pos) = z n 1 g(pos). Furthermore, observe that for pos ≥ 1, we have g(pos) = g(1 + pos -1) = w(pos)g(0) = z pos 1 z 2 = z 2 z pos 1 . For pos = 0, g(0) = z 2 = z 2 z 0 1 , whence g(pos) = z 2 z pos 1 , as desired. Observe that if |z 1 | > 1, then g(pos) is unbounded, whence we have |z 1 | ≤ 1. Conversely, assume that g is on the form g(pos) = z 2 z pos 1 with |z 1 | ≤ 1. Then, |g(pos)| ≤ |z 2 z pos 1 | ≤ |z 2 ||z pos 1 | ≤ |z 2 |, whence g is bounded. Define, for each n ∈ N, w(n) = z n 1 and Transform n (pos) = w(n)pos.

Then, for all pos, n ∈ N,

g(pos + n) = z 2 z pos+n 1 = z 2 z pos 1 z n 1 = g(pos)z n 1 = Transform n (g(pos)

) showing that g is a linearly witnessed position-free offset transformation.

For any z ∈ C, we may write z = re iθ = r(cos θ + i sin θ). Thus, for the general form of the embedding g from Theorem 1, we have:

EQUATION

In implementations, the above definition of g will lead to an optimization problem due to the constraint |r 1 | ≤ 1. A natural and simple way to avoid this is to fix r 1 = 1; note that |e ix | ≡ 1, thus automatically satisfying the constraint, in contrast to a real-valued embedding where one would need to explicitly devise functions satisfying the constraint. Finally, Eq. 4 can be written in the simplified form: g(pos) = re i(ωpos+θ) . Thus, one can think of g as embedding positions counterclockwise on a complex circle of radius r with a fixed period (r is the amplitude term, θ is the initial phase term, ω 2π is the frequency, and 2π ω is the period term).

2.3. COMPLEX-VALUED WORD EMBEDDING:

We now define our complex-valued word embedding g as a map taking a word index j and position word index pos to C D . For a word w j in position pos, our general complex-valued embedding is defined as f (j, pos) = g j (pos) = r j e i(ω j pos+θj ) . Therefore, f (j, pos) is defined as:

[r j,1 e i(ωj,1pos+θj,1) , ..., r j,2 e i(ωj,2pos+θj,2) , • • • , r j,D e i(ω j,D pos+θ j,D ) ] (5)

Note that each coordinate d (1 ≤ d ≤ D) has a separate amplitude r j,d , period p j,d = 2π ω j,d , and initial phase θ j,d . In Fig. 1 each dimension is represented as a wave which is parameterized by an amplitude, a period/frequency, and an initial phase. The trainable parameters of the embedding are the amplitudes vector r j = [r j,1 , ..., r j,D ], the period/frequency related weights ω j = [ω j,1 , ..., ω j,D ], and the initial phase vector θ j = [θ j,1 , ..., θ j,D ]. Note that the mean values of f (j, •) over all positions are linearly dependent on the amplitude. Observe that the period/frequency determines to what degree the word is sensitive to the position. With an extremely long period (i.e., ω j very small), the complex-valued embedding is approximately constant for all possible values of pos, and hence approximates a standard word embedding. Conversely, if the period is short, the embedding will be highly sensitive to the position argument.

In our embedding, the mean vectors of f (j, •) taken over all positions are linearly correlated to the amplitude embedding r j = [r j,1 , ..., r j,K ] with a coefficient 2 π . The amplitude r j,d of our embedding depends only on the word w j (and coordinate d), not on the position of the word, whence one can (Pang & Lee, 2005) 11.9k CV 20k movie reviews 2 SST (Socher et al., 2013) 67k 2.2k 18k movie reviews 2 TREC (Li & Roth, 2002) 5.4k 0.5k 10k Question 6

Table 1 : Dataset Statistics. CV means 10-fold cross validation. The last 2 datasets come with train/dev/test splits.

think of the vector g pe (j, pos) = [e i(ωj,1pos+θj,1) , • • • , e i(ω j,D pos+θ j,D ) ] as a "purely" positional embedding. Consequently, our complex embedding can be considered an element-wise multiplication between the word embedding g we (j) = [r j,1 , ..., r j,K ] and position embedding g pe .

f (j, pos) = g we (j) g pe (j, pos) (6)

Prior work (Gehring et al., 2017; Vaswani et al., 2017) uses mean-weight addition between word embeddings f we and position embeddings f pe (all words share the weights). In our work, word embeddings and position embeddings are decoupled to some extent by element-wise multiplication and therefore the frequency/period terms (related to ω j,d ) can adaptively adjust the importance between semantic and position information for each word and each dimension. In particular, with higher frequency (i.e., large ω j,d ), the final embedding will change dramatically with the changing positions, while it can be fixed for any positions with an extremely-small frequency (i.e., small ω j,d ).

Interestingly, the well-known position embedding in Transformer (Vaswani et al., 2017) can be seen as a degraded version of one of our specific complex word embeddings (see the Appendix A).

3. EXPERIMENTAL EVALUATION:

We evaluate our embeddings in text classification, machine translation and language modeling.

3.1. TEXT CLASSIFICATION:

Experimental Setup. We use six popular text classification datasets: CR, MPQA, SUBJ, MR, SST, and TREC (see Tab. 1). We use accuracy as evaluation measure based on fixed train/dev/test splits or cross validation, as per prior work. We use Fasttext (Joulin et al., 2016) , CNN (Kim, 2014) , LSTM and Transformer (Vaswani et al., 2017) as NN baselines2 . We use each of them: (1) without positional information;

(2) with Vanilla Position Embeddings (PE) (randomly initialized and updated during training using the sum between word and position vectors (Gehring et al., 2017) ;

(3) with Trigonometric Position Embeddings (TPE) (defining position embeddings as trigonometric functions as per Eq. 7); (4) with Complex-vanilla word embeddings (where the amplitude embedding is initialized by the pre-trained word vectors, and the phrase embedding is randomly initialized in a range from -π to π without considering word order (Wang et al., 2019 )); and (5) with our order-aware complex-valued word embeddings, Complex-order (which encode position in the phase parts, train the periods, and where the amplitude embedding is also initialized by pretrained word vectors). For more details on the complex-valued extensions of NNs, see App. B and App. C.

Our embedding generally has 3 × D × |W| parameters with D-dimensional word vectors and |W| words, while previous work (Mikolov et al., 2013b; Pennington et al., 2014) (Pagliardini et al., 2017) 0.763 0.912 0.791 0.872 0.802 0.858 QuickThoughts (Logeswaran & Lee, 2018) 0.824 0.948 0.860 0.902 -0.928 InferSent (Conneau et al., 2017) 0.811 0.924 0.863 0.902 0.846 0.882 QPDN (Wang et al., 2019) 0.801 0.927 0.810 0.870 0.839 0.882

We search the hyper parameters from a parameter pool, with batch size in {32, 64, 128}, learning rate in {0.001, 0.0001, 0.00001}, L2-regularization rate in {0, 0.001, 0.0001}, and number of hidden layer units in {120, 128}. We use pre-trained 300-dimensional vectors from word2vec (Mikolov et al., 2013a ) in all models except for Transformers. The models with trainable trigonometric position embedding produce nearly identical results compared to the non-trainable version, therefore we report the result of fixed position embeddings as per Vaswani et al. (2017) . We adopt narrow convolution and max pooling in CNN, with number of filters in {64, 128}, and size of filters in {3, 4, 5}.

In all Transformer models, we only use the encoder layer to extract feature information, where the layer is 1, dimension of word and inner hidden are 256 and 512 respectively, and head number is 8.

Results. The results are shown in Tab. 2. Our complex-order embeddings outperform all other variations at all times. This gain in effectiveness comes at a negligible (or non-existent) cost in efficiency (it varies per NN architecture -see Fig. 2 ). CNNs are the best performing NN as expected following Bai et al. (2018) . Tranformer NNs benefit the most from our complex-order embeddings, most likely because they are our weakest baseline. To contextualise these results, Tab. 3 shows classification accuracy of five typical approaches on the same datasets (as reported in the original papers). Our complex-order embeddings outperform all methods, except for the CR dataset, where InferSent is marginally better. Overall, our approach is on a par with the SOTA in embeddings.

We perform an ablation test (Tab. 4) on Transformer because it is the most common NN to be used with position embeddings. The two period-sharing schemas (dimension-sharing and word-sharing) Table 4 : Ablation test for Transformer, showing the effect of (i) the definition of embedding layer(f d (j, pos)), and (ii) whether the real-part and imaginary transition share the weights, i.e.,

(W Q/K/V ) = (W Q/K/V ). Method Setting Params Accuracy ∆ f d (j, pos) share in W Q/K/V

Transformer-complex-order r j,d e i(ω j,d pos) × 8.33M 0.813 adding initial phases r j,d e i(ω j,d pos+θ j,d ) × 11.89M 0.785 -0.028 dimension-sharing period schema r j,d e iω j,• pos × 5.82M 0.797 -0.016 word-sharing period schema r j,d e iω slightly drop performance, because fewer parameters limit the representative power. Adding initial phases also hurts performance, although we observed that the loss could decrease faster in early epochs compared to the setting without offset. The negative effect of initial phases may be due to periodicity, and ω cannot be directly regularized with L2-norm penalties. The sharing schemes slightly decrease the performance with less parameters. More details of the learned periods/frequencies (e.g. the distributions of periods/frequencies and case studies) are shown in App. D.

Note that the word-sharing schema outperform the Vanilla Transformer, (both have a comparable number of parameters). If we choose

(W Q/K/V ) = (W Q/K/V

), the additional parameters in the embedding layers will affect much less the whole parameter scale in the multiple-layer Transformer, since a embedding layer is only used in the first layer instead of the following Transformer layers.

3.2. MACHINE TRANSLATION:

Experimental Setup. We use the standard WMT 2016 English-German dataset (Sennrich et al., 2016) , whose training set consists of 29,000 sentence pairs. We use four baselines: basic Attentional encoder-decoder (AED) (Bahdanau et al., 2014) ; AED with Byte-pair encoding (BPE) subword segmentation for open-vocabulary translation (Sennrich et al., 2016) ; AED with extra linguistic features (morphological, part-of-speech, and syntactic dependency labels) (Sennrich & Haddow, 2016) ; and a 6-layer Transformer. Our approach (Transformer Complex-order) uses a batch size of 64, a head of 8, 6 layers, the rate of dropout is 0.1, and the dimension of the word embedding is 512. The embedding layer does not use initial phases, i.e., following f (j, pos) = r j e i(ω j pos) . We evaluate MT performance with the Bilingual Evaluation Understudy (BLEU) measure. Method BLEU AED (Bahdanau et al., 2014) 26.8 AED+Linguistic (Sennrich & Haddow, 2016) 28.4 AED+BPE (Sennrich et al., 2016) 34.2 Transformer (Ma et al., 2019) 34.5 Transformer complex vanilla 34.7 Transformer Complex-order 35.8

Table 6 : Language modeling results. marks scores reported from other papers.

Method BPC BN-LSTM (Cooijmans et al., 2016) 1.36 LN HM-LSTM (Chung et al., 2016) 1.29 RHN (Zilly et al., 2017) 1.27 Large mLSTM (Krause et al., 2016) 1.27 Transformer XL 6L (Dai et al., 2019) 1.29 Transformer complex vanilla 1.30 Transformer XL Complex-order 6L 1.26 Results Tab. 5 shows the MT results. Our approach outperforms all baselines. Two things are worth noting: (1) Both the vanilla Transformer and our Transformer Complex-order outperform the three Attentional encoder-decoder baselines which are based on an LSTM encoder and decoder, even when AED uses additional features. (2) Our Transformer Complex-Order outperforms the Vanilla Transformer and complex-vanilla Transformer by 1.3 and 1.1 in absolute BLEU score respectively.

3.3. LANGUAGE MODELING:

Experimental Setup. We use the text8 (Mahoney, 2011) dataset, consisting of English Wikipedia articles. The text is lowercased from a to z, and space. The dataset contains 100M characters (90M for training, 5M for dev, and 5M for testing, as per Mikolov et al. (2012) ). We use as baselines BN-LSTM, LN HM-LSTM RHN and Large mLSTM, which are typical recurrent NNs for language modeling in this dataset. We evaluate performance with the Bits Per Character (BPC) measure, (the lower, the better). We run the coder in Dai et al. (2019) with 6 layers for Transformer XL 6L; our model, named Transformer XL complex-order, directly replaces the word embedding with our proposed embedding under the same setting. We choose 6 layers due to limitations in computing resources. For Transformer XL Complex-order, all other parameter settings are as for Transformer XL (Dai et al., 2019) . Our complex-order model does not use initial phases.

Results. We see in Tab. 6 that our method outperforms all baselines. The first four baselines (BN-LSTM, LN HM-LSTM, RHN and Large mLSTM) are based on recurrent NNs and rely on different regulation methods to become applicable in multiple-layer recurrent architectures. Transformerbased architectures can easily be stacked with multiple layers due to their advantages in parallelization, however the vanilla Transformer does not outperform the multiple-layer recurrent baselines, most likely due to its limitation of 6 layers. Our Transformer XL Complex-order outperforms its vanilla counterpart under the 6-layer setting (and also strong recurrent network baselines), demonstrating that our embedding also generalizes well in tasks with long-term dependency. With limited resources, slightly increasing the parameters in the feature layer like our proposed embedding could be more beneficial than stacking more layers with linearly increasing parameters.

4. RELATED WORK:

Complex-valued NNs are not new (Georgiou & Koutsougeras, 1992; Kim & Adalı, 2003; Hirose, 2003) . Complex-valued weights have been used in NNs, motivated by biology (Reichert & Serre, 2013) , and also as signal processing in speech recognition (Shi et al., 2006) . More recently, Arjovsky et al. (2016) shifted RNNs into the complex domain and Wolter & Yao (2018) proposed a novel complex gated recurrent cell. Trabelsi et al. (2017) also developped a complex-valued NN for computer vision and audio processing.

Complex numbers have also been applied to text processing like (Van Rijsbergen, 2004; Melucci, 2015; Blacoe et al., 2013) . Trouillon et al. (2016) adopt complex embedding for entities in Knowledge Graph Completion to represent antisymmetric relations with Hermitian dot product. Li et al. (2019) ; Wang et al. (2019) extend word embeddings to complex-valued fashion in quantum probability driven NNs, seeing the overview in Wang et al. (2019) . However, the physical meaning of both the complex-valued entity and word embeddings is unknown, since a complex number was considered as two real numbers in a black-box learning paradigm. Our work first links the phase in complex numbers to word position to define concrete physical meaning in document representations.

5. CONCLUSIONS:

We extended word vectors to word functions with a variable i.e. position, to model the smooth shift among sequential word positions and therefore implicitly capture relative distances between words. These functions are well-defined to model the relative distances, therefore we derive a general solution in complex-valued fashion. Interestingly, the position embedding in Vaswani et al. (2017) can be considered a simplified version of our approach. We extend CNN, RNN and Transformer NNs to complex-valued versions to incorporate our complex embedding. Experiments on text classification, machine translation and language modeling show that our embeddings are more effective than vanilla position embeddings (Vaswani et al., 2017) .

Complex-valued CNN For the complex-valued version of the convolution operation Trabelsi et al. (2017) , we similarly define a complex-valued convolution with separate real and imaginary kernels A and B, to compute convolutions on the real and imaginary parts of the input in Eq. 10. A complex-valued CNN network is constructed by stacking the operations based on a complex-valued convolution kernel, adding a complex dense layer in (10), and taking their norm as the final prediction in the last layer.

Complex-valued RNN The basic complex RNN formulation is:

EQUATION

where z t and h t represent the complex-valued input and complex-value hidden state vectors at time t, b is a complex-valued bias, W h and W z are complex-valued weight transitions for hidden state and input state, and f (z) = σ ( (z)) + iσ ( (z)) is the activation function. The multiplication W h h t-1 and W z z t is computed as defined in (10) above. Similarly, the complex-valued gates are used in LSTM via operations as in ( 12). In the final layer, a l2-norm operation is adopted to obtain a real-valued loss for backpropagation.

Complex-valued Transformer:

The main components in the Transformer are self-attention sublayers and position-wise feed-forward (FFN) sublayers. A self-attention sublayer employs h attention heads and the concatenation of all heads is used as the output followed by a parameterized linear transformation. For a sequence embedded as complex-valued vector input = {w 1 , w 2 , ..., w n }, the output of each head is computed as a weighted sum of a linear transformation of the input sequence itself, namely

EQUATION

where w j is a complex-valued vector and W V is a complex linear transformation; therefore output i is also complex. Hence, output is a sequence of complex-valued vectors with the same shape as input. The weight coefficient, a i,j , which is defined as in real-valued domain, is calculated as the softmax of the product between complex-valued query vectors and key vectors: a i,j = softmax ei,j n i=1 ei,j , and

EQUATION

z is a complex number since w i and w j are complex-valued vectors and W Q , W K are complexvalued transformation. To extend another variant of Transformer called Transformer XL, we keep its original relative position embedding and additionally replace its word embedding with our proposed embedding.

Correspondingly, the FFN sublayer can easily be extended to a complex-valued version by replacing the real-valued layers with complex-valued ones. We use batch-normalization separately for the real and imaginary parts.

C IMPLEMENTATION OF THE PROPOSED EMBEDDING:

Words functions are implemented in neural networks by storing the function parameters {r, ω, θ} and then construct the values based on the arguments. Based on the definition, the implementation of the proposed embedding can easily be implemented with only modifying the embedding layer.

We list the basic code to construct our general embedding as below: a m p l i t u d e = s e l f . word emb ( x ) f r e q u e n c y = s e l f . f r e q u e n c y e m b ( x ) s e l f . i n i t i a l p h a s e e m b . w e i g h t = t o r c h . nn . P a r a m e t e r ( s e l f . i n i t i a l p h a s e e m b . w e i g h t % ( 2 * math . p i ) )

s e n t l e n =x . s i z e ( -1) p o s s e q = t o r c h . a r a n g e ( 1 , s e n t l e n + 1 , 1 . 0 , d e v i c e = a m p l i t u d e . d e v i c e ) p o s s e q = p o s s e q . u n s q u e e z e ( 0 ) . u n s q u e e z e ( -1) p o s s e q = p o s s e q . r e p e a t ( [ x . s i z e ( 0 ) , 1 , a m p l i t u d e . Note that both the frequency vectors ω and initial-phase vectors θ can be shared between words or dimensions, to save parameters. The proposed embedding can be also used in real-valued neural networks if one directly concatenates the real-part numbers and imaginary-part numbers as a doublesize real-valued vector; therefore it could easily be extended in any existing networks without any complex-valued components. For instance, it could be a good extension for Transformer based pretrained models like (Devlin et al., 2018) by enriching the feature layer.

D VISUALIZATION OF FREQUENCIES/PERIODS:

After training, we obtain the frequency vector ω for each word. For each word, the mean value of the absolute frequency values, i.e., δ j = 1 |D| D d=1 |ω j,d | is considered as a metric to test the positional sensitivities of the word, since a period value could be negative during training. The density of the δ j is shown in Fig. 3 .

Words with the 50 greatest, and the 50 smallest, frequencies in the SST dataset are shown in Tab. 7. For the words with greatest frequencies, most of them are strong sentiment words like "worst" ,"stupid" and "powerful"; a reason for this may be that such words appear in many positions in many documents during training, and thus they are more sensitive to the positions. Conversely, there are fewer words expressing strong sentiment among words with smaller frequencies, as shown in the second row. words greatest frequencies in descending order worst solid stupid powerful mess wonderful remarkable suffers intoxicating thoughtful rare captures portrait gem frontal terrific unique wannabe witty lousy pointless contrived none worse refreshingly charming inventive amazing junk incoherent refreshing mediocre unfunny thinks enjoyed heartbreaking delightfully crisp brilliant heart spirit perfectly nowhere mistake engrossing fashioned excellent unexpected wonderfully means smallest frequencies in ascending order slowly proposal schemes roiling juliette titles fabric superstar ah wow choreographed tastelessness beg fabulous muccino jacobi legendary jae rate example code sensation counter deaths hall eun drug mctiernan storylines cellophane wild motion ups trick comedy entertained mission frightening witnesses snoots liners african groan satisfaction calm saturday estranged holm refuses inquisitive Table 7 : Words with greatest frequencies and frequencies periods (based on δ j ) in SST (a sentiment classification task), all words are converted to lower-case. The strong sentiment words are bold based on manual labeling.

:

Graph convolutional networks (GCNs)(Beck et al., 2018;Sahu et al., 2019) also encode positional information. We do not compare against them because they encode positional information inherently as part of the model, which makes redundant any additional encoding of positional information at the embedding level.

Figures and Tables:

Figure 1: 3-dimensional complex embedding for a single word in different positions. The three wave functions (setting the initial phases as zero)show the real part of the embedding; the imaginary part has a π 2 phase difference and shows the same curves with its real-valued counterpart. The x-axis denotes the absolute position of a word and the y-axis denotes the value of each element in its word vector. Colours mark different dimensions of the embedding. The three cross points between the functions and each vertical line (corresponding to a specific position pos) represent the embedding for this word in the pos-th position.

usually employs only D × |W| parameters for embedding lookup tables. To increase efficiency and facilitate fair comparison with previous work we set initial phases θ j = [θ j,1 , ..., θ j,D ] to a shared constant value (such as zero). Furthermore, the period vectors ω j,d depend on word index j with length |W| and the coordinate index d with length D. To decrease the number of parameters, one can either use a word-sharing scheme (i.e., ω j,d = ω •,d ), or a dimension-sharing scheme (ω j,d = ω j,• ), leading to |W| * D + |W| and |W| * D + D parameters in total for the embedding layer.

Figure 2: Computation time (seconds) per epoch in Tensorflow on TITAN X GPU.

Figure 3: The distribution of the δ j . Higher values mean that the word representations are more sensitive to the word positions.

d e f g e t e m b e d d i n g ( s e l f , x ) :

s i z e ( -1 ) ] ) d i m e n s i o n b a i s = s e l f . i n i t i a l p h a s e e m b ( x ) e n c o u t p u t p h a s e = t o r c h . mul ( p o s s e q , f r e q u e n c y ) + d i m e n s i o n b a i s e n c o u t p u t r e a l = a m p l i t u d e * t o r c h . c o s ( e n c o u t p u t p h a s e ) e n c o u t p u t i m a g e = a m p l i t u d e * t o r c h . s i n ( e n c o u t p u t p h a s e ) # r e t u r n t o r c h . c a t ( [ e n c o u t p u t r e a l , e n c o u t p u t i m a g e ] , -1) r e t u r n e n c o u t p u t r e a l , e n c o u t p u t i m a g e d e f f o r w a r d ( s e l f , x ) : r e t u r n s e l f . g e t e m b e d d i n g ( x ) . . .

Text classification accuracy without position embeddings, with random position embeddings (PE), with trigonometric position embeddings (TPE), with complex-valued NNs without position embeddings (complex-vanilla), and with our complex-order embeddings. Superscripts §, †, ‡ and * mean a significant improvement over a baseline without position embeddings § , PE † , TPE ‡ and Complex-vanilla * using Wilcoxon's signed-rank test p<0.05.

Table content: <table><tr><td>Method</td><td>MR</td><td>SUBJ</td><td>CR</td><td>MPQA</td><td>SST</td><td>TREC</td></tr><tr><td>Fasttext</td><td>0.765</td><td>0.916</td><td>0.789</td><td>0.874</td><td>0.788</td><td>0.874</td></tr><tr><td>Fasttext-PE</td><td>0.774</td><td>0.922</td><td>0.789</td><td>0.882</td><td>0.791</td><td>0.874</td></tr><tr><td>Fasttext-TPE</td><td>0.776</td><td>0.921</td><td>0.796</td><td>0.884</td><td>0.792</td><td>0.88</td></tr><tr><td>Fasttext-Complex-vanilla</td><td>0.773</td><td>0.918</td><td>0.79</td><td>0.867</td><td>0.803</td><td>0.872</td></tr><tr><td>Fasttext-Complex-order</td><td colspan="6">0.787  § † ‡ *  0.929  § † ‡ *  0.800  § † ‡ *  0.889  § † ‡ *  0.809  § † ‡ *  0.892  § † ‡ *</td></tr><tr><td>LSTM</td><td>0.775</td><td>0.896</td><td>0.813</td><td>0.887</td><td>0.807</td><td>0.858</td></tr><tr><td>LSTM-PE</td><td>0.778</td><td>0.915</td><td>0.822</td><td>0.889</td><td>0.811</td><td>0.858</td></tr><tr><td>LSTM-TPE</td><td>0.776</td><td>0.912</td><td>0.814</td><td>0.888</td><td>0.813</td><td>0.865</td></tr><tr><td>LSTM-Complex-vanilla</td><td>0.765</td><td>0.907</td><td>0.810</td><td>0.823</td><td>0.784</td><td>0.784</td></tr><tr><td>LSTM-Complex-order</td><td colspan="6">0.790  § † ‡ *  0.926  § † ‡ *  0.828  § † ‡ *  0.897  § † ‡ *  0.819  § † ‡ *  0.869  § † ‡ *</td></tr><tr><td>CNN</td><td>0.809</td><td>0.928</td><td>0.830</td><td>0.894</td><td>0.856</td><td>0.898</td></tr><tr><td>CNN-PE</td><td>0.816</td><td>0.938</td><td>0.831</td><td>0.897</td><td>0.856</td><td>0.890</td></tr><tr><td>CNN-TPE</td><td>0.815</td><td>0.938</td><td>0.836</td><td>0.896</td><td>0.838</td><td>0.918</td></tr><tr><td>CNN-Complex-vanilla</td><td>0.811</td><td>0.937</td><td>0.825</td><td>0.878</td><td>0.823</td><td>0.900</td></tr><tr><td>CNN-Complex-order</td><td colspan="6">0.825  § † ‡ *  0.951  § † ‡ *  0.852  § † ‡ *  0.906  § † ‡ *  0.864  § † ‡ *  0.939  § † ‡ *</td></tr><tr><td>Transformer w/o position embedding</td><td>0.669</td><td>0.847</td><td>0.735</td><td>0.716</td><td>0.736</td><td>0.802</td></tr><tr><td>Transformer-PE</td><td>0.737</td><td>0.859</td><td>0.751</td><td>0.722</td><td>0.753</td><td>0.820</td></tr><tr><td colspan="2">Transformer-TPE (Vaswani et al., 2017) 0.731</td><td>0.863</td><td>0.762</td><td>0.723</td><td>0.761</td><td>0.834</td></tr><tr><td>Transformer-Complex-vanilla</td><td>0.715</td><td>0.848</td><td>0.753</td><td>0.786</td><td>0.742</td><td>0.856</td></tr><tr><td colspan="2">Transformer-Complex-order Method Word2vec Bow (Conneau et al., 2017) 0.746  . Sent2Vec</td><td colspan="5">MR 0.777 0.909 0.798 0.883 0.797 0.836 SUBJ CR MPQA SST TREC</td></tr></table>

Machine translation results. marks scores reported from other papers.

Table content: <table/>

Peer review (iclr2020):
### Summary The authors present a *natural* way of encoding position information into word embeddings and present extensive empirical evidence to support their method. I believe that paper meets the bar for acceptance. ### Details The paper *Encoding word order in complex embeddings* presents a method for making word embeddings position dependent. The idea in a nutshell is to map each discrete position , n, to a value ` A exp( freq_{word, dim} × n )` . So a word embedding is a collection of complex valued signals sampled at discrete points. The frequency is dependent on each word and each dimension in general. The authors motivate/justify this particular formulation via their Claim 1, which argues that their particular formulation uniquely satisfies two intuitive constraints. Although one of those constraints (i.e. linearly witnessed Position-free offset) almost completely specifies the solution. The experiments in the paper are fairly thorough and cover text classification, machine translation and language modeling. Through the comparative experiments the complex embeddings we can see that the formulation in this paper outperforms existing SOTA methods, sometimes with significantly difference such as a difference of 1.3 BLEU point on the MT task. I would have liked to say that the ablation are similarly conclusive but there seem to be a problem in the table, which eroded my confidence: 1. The number of parameters in rows 5 and 8 (w/t encoding positions, share / not-share respectively) are reported to be 9.38M and 8.33M which has to be wrong. Similar problem happens with other pairs. And now I am not sure whether the results were also swapped or not. Still the results in general trend in the right direction. ### Possible improvements to the paper 1. The main weakness of the paper is that the authors repeatedly mention that encoding the position as a multiplicative factor which is multiplied to the frequency gives leads to a more decoupled/interpretable embedding but their experiments are solely focused on accuracy measurement. I would have liked to see the authors carry out more experiments to see whether the frequency parameters really are interpretable? For example, - What is the histogram of the frequencies ? Are some of them negative? - Which word has the highest frequencies (pooled over all dimensions) in absolute term? Does it make sense that that word*s meaning is so position dependent? For example, positions can capture subjects versus objects in english, but they will more reliably reflect the subject versus verb distinction in hindi. - Are the word frequencies by themselves predictive of anything? For example, what happens if the word embedding amplitudes are tied across words or dimensions? We expect the performance to be bad but how bad? These kinds of ablations / qualitative analysis will really make the paper more informative and interesting. Right now it just seems like yet another paper where the capacity of the model is increased and the accuracy increases. Specially because the delta improvement over the fixed positional embeddings of (Transformer-TPE Vaswani et al. 2017) is so limited. ### Edit after the author response The authors have made the required corrections and added the necessary analysis. One interesting outcome was that the *word-sharing amplitude schema* seems to drop so little in performance, it*s almost like all the information can be coded in just the phase vectors alone. It will be nice if the authors release their trained phase embeddings as well, for the words.