Although Transformer has achieved great successes on many NLP tasks, its heavy structure with fully-connected attention connections leads to dependencies on large training data. In this paper, we present Star-Transformer , a lightweight alternative by careful sparsification. To reduce model complexity, we replace the fully-connected structure with a star-shaped topology, in which every two non-adjacent nodes are connected through a shared relay node. Thus, complexity is reduced from quadratic to linear, while preserving the capacity to capture both local composition and long-range dependency. The experiments on four tasks (22 datasets) show that Star-Transformer achieved significant improvements against the standard Transformer for the modestly sized datasets. Recently, the fully-connected attention-based models, like Transformer (Vaswani et al., 2017), become popular in natural language processing (NLP) applications, notably machine translation (Vaswani et al., 2017) and language modeling (Radford et al., 2018). Some recent work also suggest that Transformer can be an alternative to recurrent neural networks (RNNs) and convolutional neural networks (CNNs) in many NLP tasks, such as GPT (Radford et al., 2018), BERT (Devlin et al., 2018), Transformer-XL (Dai et al., 2019) and Universal Transformer (Dehghani et al., 2018). More specifically, there are two limitations of the Transformer. First, the computation and memCorresponding Author. ory overhead of the Transformer are quadratic to the sequence length. This is especially problematic with long sentences. Transformer-XL (Dai et al., 2019) provides a solution which achieves the acceleration and performance improvement, but it is specifically designed for the language modeling task. Second, studies indicate that Transformer would fail on many tasks if the training data is limited, unless it is pre-trained on a large corpus. (Radford et al., 2018; Devlin et al., 2018). A key observation is that Transformer does not exploit prior knowledge well. For example, the local compositionality is already a robust inductive bias for modeling the text sequence. However, the Transformer learns this bias from scratch, along with non-local compositionality, thereby increasing the learning cost. The key insight is then whether leveraging strong prior knowledge can help to lighten up the architecture. architecture by moving the fully-connected topology into a star-shaped structure. Fig-1 gives an overview. Star-Transformer has two kinds of connections. The radical connections preserve the non-local communication and remove the redundancy in fully-connected network. The ring connections embody the local-compositionality prior, which has the same role as in CNNs/RNNs. The direct outcome of our design is the improvement of both efficiency and learning cost: the computation cost is reduced from quadratic to linear as a function of input sequence length. An inherent advantage is that the ring connections can effectively reduce the burden of the unbias learning of local and non-local compositionality and improve the generalization ability of the model. What remains to be tested is whether one shared relay node is capable of capturing the long-range dependencies. We evaluate the Star-Transformer on three NLP tasks including Text Classification, Natural Language Inference, and Sequence Labelling. Experimental results show that Star-Transformer outperforms the standard Transformer consistently and has less computation complexity. An additional analysis on a simulation task indicates that Star-Transformer preserve the ability to handle with long-range dependencies which is a crucial feature of the standard Transformer. In this paper, we claim three contributions as the following and our code is available on Github 1 :  Compared to the standard Transformer, Star-Transformer has a lightweight structure but with an approximate ability to model the long-range dependencies. It reduces the number of connections from n 2 to 2 n , where n is the sequence length. The Star-Transformer divides the labor of semantic compositions between the radical and the ring connections. The radical connections focus on the non-local compositions and the ring connections focus on the local composition. Therefore, Star-Transformer works for modestly sized datasets and does not rely on heavy pre-training. we verify that both Transformer and Star-Transformer are good at handling long-range dependencies compared to the LSTM and BiLSTM. Recently, neural networks have proved very successful in learning text representation and have achieved state-of-the-art results in many different tasks. Modelling Local Compositionality A popular approach is to represent each word as a low-dimensional vector and then learn the local semantic composition functions over the given sentence structures. For example, Kim (2014); Kalchbren-ner et al. (2014) used CNNs to capture the semantic representation of sentences, whereas Cho et al. (2014) used RNNs. These methods are biased for learning local compositional functions and are hard to capture the long-term dependencies in a text sequence. In order to augment the ability to model the nonlocal compositionality, a class of improved methods utilizes various self-attention mechanisms to aggregate the weighted information of each word, which can be used to get sentence-level representations for classification tasks (Yang et al., 2016; Lin et al., 2017; Shen et al., 2018a). Another class of improved methods augments neural networks with a re-reading ability or global state while processing each word (Cheng et al., 2016; Zhang et al., 2018). One class of models incorporate syntactic tree into the network structure for learning sentence representations (Tai et al., 2015; Zhu et al., 2015). Another type of models learns the dependencies between words based entirely on self-attention without any recurrent or convolutional layers, such as Transformer (Vaswani et al., 2017), which has achieved state-of-the-art results on a machine translation task. The success of Transformer has raised a large body of follow-up work. Therefore, some Transformer variations are also proposed, such as GPT (Radford et al., 2018), BERT (Devlin et al., 2018), Transformer-XL (Dai et al., 2019) , Universal Transformer (Dehghani et al., 2018) and CN 3 (Liu et al., 2018a). However, those Transformer-based methods usually require a large training corpus. When applying them on modestly sized datasets, we need the help of semi-supervised learning and unsupervised pretraining techniques (Radford et al., 2018). Graph Neural Networks Star-Transformer is also inspired by the recent graph networks (Gilmer et al., 2017; Kipf and Welling, 2016; Battaglia et al., 2018; Liu et al., 2018b), in which the information fusion progresses via message-passing across the whole graph. The graph structure of the Star-Transformer is star-shaped by introducing a virtual relay node. The radical and ring connections give a better bal-ance between the local and non-local compositionality. Compared to the previous augmented models (Yang et al., 2016; Lin et al., 2017; Shen et al., 2018a; Cheng et al., 2016; Zhang et al., 2018), the implementation of Star-Transform is purely based on the attention mechanism similar to the standard Transformer, which is simpler and well suited for parallel computation. Due to its better parallel capacity and lower complexity, the Star-Transformer is faster than RNNs or Transformer, especially on modeling long sequences. The Star-Transformer consists of one relay node and n satellite nodes. The state of i -th satellite node represents the features of the i -th token in a text sequence. The relay node acts as a virtual hub to gather and scatter information from and to all the satellite nodes. Star-Transformer has a star-shaped structure, with two kinds of connections in the: the radical connections and the ring connections. Radical Connections For a network of n satellite nodes, there are n radical connections. Each connection links a satellite node to the shared relay node. With the radical connections, every two non-adjacent satellite nodes are two-hop neighbors and can receive non-local information with a two-step update. Ring Connections Since text input is a sequence, we bake such prior as an inductive bias. Therefore, we connect the adjacent satellite nodes to capture the relationship of local compositions. The first and last nodes are also connected. Thus, all these local connections constitute a ring-shaped structure. Note that the ring connections allow each satellite node to gather information from its neighbors and plays the same role to CNNs or bidirectional RNNs. With the radical and ring connections, Star-Transformer can capture both the non-local and local compositions simultaneously. Different from the standard Transformer, we make a division of labor, where the radical connections capture nonlocal compositions, whereas the ring connections attend to local compositions. The implementation of the Star-Transformer is very similar to the standard Transformer, in which the information exchange is based on the attention mechanism (Vaswani et al., 2017). Multi-head Attention Just as in the standard Transformer, we use the scaled dot-product attention (Vaswani et al., 2017). Given a sequence of vectors H  R n  d , we can use a query vector q  R 1  d to soft select the relevant information with attention. where K = HWK , V = HWV , and WK , WV are learnable parameters. To gather more useful information from H , similar to multi-channels in CNNs, we can use multihead attention with k heads. MultiAtt( q , H ) = ( a 1      a k ) WO , (2) a i = Att( qW Q i , HWK i , HWV i ) , i  [1 , k ] (3) where  denotes the concatenation operation, and W Qi , W Ki , W Vi , WO are learnable parameters. Update Let s t  R 1  d and H t  R n  d denote the states for the relay node and all the n satellite nodes at step t . When using the Star-Transformer to encode a text sequence of length n , we start from its embedding E = [ e 1 ;    ; e n ] , where e i  R 1  d is the embedding of the i-th token. We initialize the state with H 0 = E and s 0 = average ( E ) . The update of the Star-Transformer at step t can be divided into two alternative phases: (1) the update of the satellite nodes and (2) the update of the relay node. At the first phase, the state of each satellite node h i are updated from its adjacent nodes, including the neighbor nodes h i  1 , h i +1 in the sequence, the relay node s t , its previous state, and its corresponding token embedding. where C ti denotes the context information for the i -th satellite node. Thus, the update of each satellite node is similar to the recurrent network, except that the update fashion is based on attention mechanism. After the information exchange, a layer normalization operation (Ba et al., 2016) is used. At the second phase, the relay node s t summarizes the information of all the satellite nodes and its previous state. By alternatively updating update the satellite and relay nodes, the Star-Transformer finally captures all the local and non-local compositions for an input text sequence. Position Embeddings To incorporate the sequence information, we also add the learnable position embeddings, which are added with the token embeddings at the first layer. The overall update algorithm of the Star-Transformer is shown in the Alg-1. After T rounds of update, the final states of HT and s T can be used for various tasks such as sequence labeling and classification. For different tasks, we feed them to different task-specific modules. For classification, we generate the fix-length sentence-level vector representation by applying a max-pooling across the final layer and mixing it with s T , this vector is fed into a Multiple Layer Perceptron (MLP) classifier. For the sequence labeling task, the HT provides features corresponding to all the input tokens. Since our goal is making the Transformer lightweight and easy to train with modestly sized dataset, we have removed many connections compared with the standard Transformer (see Fig-1). If the sequence length is n and the dimension of hidden states is d , the computation complexity of one layer in the standard Transformer is O ( n 2 d ) . The Star-Transformer has two phases, the update of ring connections costs O (5 nd ) (the constant 5 comes from the size of context information C ), and the update of radical connections costs O ( nd ) , so the total cost of one layer in the Star-Transformer is O (6 nd ) . In theory, Star-Transformer can cover all the possible relationships in the standard Transformer. For example, any relationship h i  h j in the standard Transformer can be simulated by h i  s  h j . The experiment on the simulation task in Sec-5.1 provides some evidence to show the virtual node s could handle long-range dependencies. Following this aspect, we can give a rough analysis of the path length of dependencies in these models. As discussed in the Transformer paper (Vaswani et al., 2017), the maximum dependency path length of RNN and Transformer are O ( n ) , O (1) , respectively. Star-Transformer can pass the message from one node to another node via the relay node so that the maximum dependency path length is also O (1) , with a constant two comparing to Transformer. Compare with the standard Transformer, all positions are processed in parallel, pair-wise connec-Dataset Train Dev. tions are replaced with a gather and dispatch mechanism. As a result, we accelerate the Transformer 10 times on the simulation task and 4.5 times on real tasks. The model also preserves the ability to handle long input sequences. Besides the acceleration, the Star-Transformer achieves significant improvement on some modestly sized datasets. We evaluate Star-Transformer on one simulation task to probe its behavior when challenged with long-range dependency problem, and three real tasks (Text Classification, Natural Language Inference, and Sequence Labelling). All experiments are ran on a NVIDIA Titan X card. Datasets used in this paper are listed in the Tab-1. We use the Adam (Kingma and Ba, 2014) as our optimizer. On the real task, we set the embedding size to 300 and initialized with GloVe (Pennington et al., 2014). And the symbol Ours + Char means an additional character-level pre-trained embedding JMT (Hashimoto et al., 2017) is used. Therefore, the total size of embedding should be 400 which as a result of the concatenation of GloVe and JMT. We also fix the embedding layer of the Star-Transformer in all experiments. Since semior unsupervised model is also a feasible solution to improve the model in a parallel direction, such as the ELMo (Peters et al., 2018) and BERT (Devlin et al., 2018), we exclude these models in the comparison and focus on the relevant architectures. In this section, we introduce a simulation task on the synthetic data to probe the efficiency and non-local/long-range dependencies of LSTM, Transformer, and the Star-Transformer. As mentioned in (Vaswani et al., 2017), the maximum path length of long-range dependencies of LSTM and Transformer are O ( n ) and O (1) , where n is the sequence length. The maximum dependency path length of Star-Transformer is O (1) with a constant two via the relay node. To validate the ability to deal with long-range dependencies, we design a simulation task named Masked Summation. The input of this task is a matrix X  R n  d , it has n columns and each column has d elements. The first dimension indicates the mask value X i 0  { 0 , 1 } , 0 means the column is ignored in summation. The rest d  1 elements are real numbers in drawn uniformly from the range [0 , 1) . The target is a d  1 dimensional vector which equals the summation of all the columns with the mask value 1 . There is an implicit variable k to control the number of 1 in the input. Note that a simple baseline is always guessing the value k/ 2 . The evaluation metric is the Mean Square Error (MSE), and the generated dataset has (10k/10k/10k) samples in (train/dev/test) sets. The Fig-2 show a case of the masked summation task. The mask summation task asks the model to recognize the mask value and gather columns in different positions. When the sequence length n is significantly higher than the number of the columns k , the model will face the long-range dependencies problem. The Fig-3a shows the per-Input 1 0.3 0.4 0 0.5 0.7 0 0.1 0.2 1 0.5 0.9 0 0.4 0.2 0 0.6 0.8 0 0.1 0.3 1 0.1 0.6 0.9 1.9 Target Figure 2: An example of the masked summation task, the input is a sequence of n vectors, each vector has d dimension, and there are total k vectors which have the mask value equals 1 . (a) MSE loss on the masked summation when n = 200 , k = 10 , d = 10 . The k/ 2 line means the MSE loss when the model always guess the exception value k/ 2 . formance curves of models on various lengths. Although the task is easy, the performance of LSTM and BiLSTM dropped quickly when the sequence length increased. However, both Transformer and Star-Transformer performed consistently on various lengths. The result indicates the Star-Transformer preserves the ability to deal with the non-local/long-range dependencies. Besides the performance comparison, we also study the speed with this simulation task since we could ignore the affection of padding, masking, and data processing. We also report the inference time in the Fig-3b, which shows that Transformer is faster than LSTM and BiLSTM a lot, and Star-Transformer is faster than Transformer, especially on the long sequence. Text classification is a basic NLP task, and we select two datasets to observe the performance of our model in different conditions, Stanford Sentiment Treebank(SST) dataset (Socher et al., 2013) and MTL-16 (Liu et al., 2017) consists of 16 small datasets on various domains. We truncate the sequence which its length higher than 256 to ensure the standard Transformer can run on a single GPU card. For classification tasks, we use the state of the relay node s T plus the feature of max pooling on satellite nodes max( HT ) as the final representation and feed it into the softmax classifier. The description of hyper-parameters is listed in Tab-1 and Appendix. Results on SST and MTL-16 datasets are listed in Tab-2,3, respectively. On the SST, the Star-Transformer achieves 2.5 points improvement against the standard Transformer and beat the most models. Also, on the MTL-16, the Star-Transformer outperform the standard Transformer in all 16 datasets, the improvement of the average accuracy is 4.2. The Star-Transformer also gets better results compared with existing works. As we mentioned in the introduction, the standard Transformer requires large training set to reveal its power. Our experiments show the Star-Dataset Acc (%) Test Time (ms) Len. Transformer could work well on the small dataset which only has 1400 training samples. Results of the time-consuming show the Star-Transformer could be 4.5 times fast than the standard Transformer on average. Natural Language Inference (NLI) asks the model to identify the semantic relationship between a premise sentence and a corresponding hypothesis sentence. In this paper, we use the Stanford Natural Language Inference (SNLI) (Bowman et al., 2015) for evaluation. Since we want to study how the model encodes the sentence as a vector representation, we set Star-Transformer as a sentence vector-based model and compared it with sentence vector-based models. In this experiment, we follow the previous work (Bowman et al., 2016) to use concat ( r 1 , r 2 , (cid:107) r 1  r 2 (cid:107) , r 1  r 2 ) as the classification feature. The r 1 , r 2 are representations of premise and hypothesis sentence, it is calculated by s T + max( HT ) which is same with the classification task. See Appendix for the detail of hyper-parameters. As shown in Tab-4, the Star-Transformer outperforms most typical baselines (DiSAN, SPINN) and achieves comparable results compared with the state-of-the-art model. Notably, our model beats standard Transformer by a large margin, which is easy to overfit although we have made a careful hyper-parameters' searching for Transformer. The SNLI dataset is not a small dataset in NLP area, so improving the generalization ability of the Transformer is a significant topic. The best result in Tab-4 (Yoon et al., 2018) using a large network and fine-tuned hyper-parameters, they get the best result on SNLI but an undistinguished result on SST, see Tab-2. To verify the ability of our model in sequence labeling, we choose two classic sequence labeling tasks: Part-of-Speech (POS) tagging and Named Entity Recognition (NER) task. Three datasets are used as our benchmark: one POS tagging dataset from Penn Treebank (PTB) (Marcus et al., 1993), and two NER datasets from CoNLL2003 (Sang and Meulder, 2003), CoNLL2012 (Pradhan et al., 2012). We use the fi-Model Adv Tech POS NER PTB CoNLL2003 CoNLL2012 char CRF Acc F1 F1 (Ling et al., 2015) (cid:88) (cid:88) 97.78 -(Collobert et al., 2011) (cid:88) (cid:88) 97.29 89.59 (Huang et al., 2015) (cid:88) (cid:88) 97.55 90.10 (Chiu and Nichols, 2016a) (cid:88) (cid:88) -90.69 86.35 (Ma and Hovy, 2016) (cid:88) (cid:88) 97.55 91.06 (Nguyen et al., 2016) (cid:88) (cid:88) -91.2 (Chiu and Nichols, 2016b) (cid:88) (cid:88) -91.62 86.28 (Zhang et al., 2018) (cid:88) (cid:88) 97.55 91.57 (Akhundov et al., 2018) (cid:88) (cid:88) 97.43 91.11 87.84 Transformer 96.31 86.48 83.57 Transformer + Char (cid:88) 97.04 88.26 85.14 Star-Transformer 97.14 90.93 86.30 Star-Transformer + Char (cid:88) 97.64 91.89 87.64 Star-Transformer + Char + CRF (cid:88) (cid:88) 97.68 91.98 87.88 Table 5: Results on sequence labeling tasks. nal state of satellite nodes HT to classify the label in each position. Since we believe that the complex neural network could be an alternative of the CRF, we also report the result without CRF layer. As shown in Tab-5, Star-Transformer achieves the state-of-the-art performance on sequence labeling tasks. The Star-Transformer + Char has already beat most of the competitors. Star-Transformer could achieve such results without CRF, suggesting that the model has enough capability to capture the partial ability of the CRF. The Star-Transformer also outperforms the standard Transformer on sequence labeling tasks with a significant gap. In this section, we perform an ablation study to test the effectiveness of the radical and ring connections. We test two variants of our models, the first variants (a) remove the radical connections and only keep the ring connections. Without the radical connections, the maximum path length of this variant becomes O ( n ) . The second variant (b) removes the ring connections and remains the radical connections. Results in Tab-6 give some insights, the variant (a) loses the ability to handle long-range dependencies, so it performs worse on both the simulation and real tasks. However, the performance drops on SNLI and CoNLL03 is moderate since the remained ring connections still capture the local features. The variant (b) still works on the simulation task since the maximum path length stays unchanged. Without the ring connections, it loses its performance heavily on real tasks. Therefore, both the radical and ring connections are necessary to our model. In this paper, we present Star-Transformer which reduce the computation complexity of the standard Transformer by carefully sparsifying the topology. We compare the standard Transformer with other models on one toy dataset and 21 real datasets and find Star-Transformer outperforms the standard Transformer and achieves comparable results with state-of-the-art models. This work verifies the ability of Star-Transformer by excluding the factor of unsupervised pre-training. In the future work, we will investigate the ability of Star-Transformer by unsupervised pre-training on the large corpus. Moreover, we also want to introduce more NLP prior knowledge into the model. We would like to thank the anonymous reviewers for their valuable comments. The research work is supported by Shanghai Municipal Science and Technology Commission (No. 17JC1404100 and 16JC1420401), National Key Research and Development Program of China (No. 2017YFB1002104), and National Natural Science Foundation of China (No. 61672162 and 61751201).
abstain method method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain method abstain abstain objective objective objective objective objective result other other other other other other abstain abstain abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method method abstain abstain method abstain abstain method method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain result abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain result result abstain abstain abstain abstain abstain abstain abstain result result abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain result abstain result abstain result abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method result result objective abstain other other