Recent work has improved our ability to detect linguistic knowledge in word representations. However, current methods for detecting syntactic knowledge do not test whether syntax trees are represented in their entirety. In this work, we propose a structural probe , which evaluates whether syntax trees are embedded in a linear transformation of a neural network's word representation space. The probe identifies a linear transformation under which squared L2 distance encodes the distance between words in the parse tree, and one in which squared L2 norm encodes depth in the parse tree. Using our probe, we show that such transformations exist for both ELMo and BERT but not in baselines, providing evidence that entire syntax trees are embedded implicitly in deep models' vector geometry. As pretrained deep models that build contextualized representations of language continue to provide gains on NLP benchmarks, understanding what they learn is increasingly important. To this end, probing methods are designed to evaluate the extent to which representations of language encode particular knowledge of interest, like part-of-speech (Belinkov et al., 2017), morphology (Peters et al., 2018a), or sentence length (Adi et al., 2017). Such methods work by specifying a probe (Con-neau et al., 2018; Hupkes et al., 2018), a supervised model for finding information in a representation. Of particular interest, both for linguistics and for building better models, is whether deep models' representations encode syntax (Linzen, 2018). Despite recent work (Kuncoro et al., 2018; Peters et al., 2018b; Tenney et al., 2019), open questions remain as to whether deep contextual models encode entire parse trees in their word representations. In this work, we propose a structural probe , a simple model which tests whether syntax trees are consistently embedded in a linear transformation of a neural network's word representation space. Tree structure is embedded if the transformed space has the property that squared L2 distance between two words' vectors corresponds to the number of edges between the words in the parse tree. To reconstruct edge directions, we hypothesize a linear transformation under which the squared L2 norm corresponds to the depth of the word in the parse tree. Our probe uses supervision to find the transformations under which these properties are best approximated for each model. If such transformations exist, they define inner products on the original space under which squared distances and norms encode syntax trees  even though the models being probed were never given trees as input or supervised to reconstruct them. This is a structural property of the word representation space, akin to vector offsets encoding word analogies (Mikolov et al., 2013). Using our probe, we conduct a targeted case study, showing that ELMo (Peters et al., 2018a) and BERT (Devlin et al., 2019) representations embed parse trees with high consistency in contrast to baselines, and in a low-rank space. 1 In summary, we contribute a simple structural probe for finding syntax in word representations (  2), and experiments providing insights into and examples of how a low-rank transformation recovers parse trees from ELMo and BERT representations (  3,4). Finally, we discuss our probe and limitations in the context of recent work (  5). Our goal is to design a simple method for testing whether a neural network embeds each sentence's 1 We release our code at https://github.com/ john-hewitt/structural-probes . dependency parse tree in its contextual word representations  a structural hypothesis. Under a reasonable definition, to embed a graph is to learn a vector representation of each node such that geometry in the vector spacedistances and norms approximates geometry in the graph (Hamilton et al., 2017). Intuitively, why do parse tree distances and depths matter to syntax? The distance metricthe path length between each pair of wordsrecovers the tree T simply by identifying that nodes u, v with distance d T ( u, v ) = 1 are neighbors. The node with greater normdepth in the treeis the child. Beyond this identity, the distance metric explains hierarchical behavior. For example, the ability to perform the classic hierarchy test of subject-verb number agreeement (Linzen et al., 2016) in the presence of attractors can be explained as the verb (V) being closer in the tree to its subject (S) than to any of the attactor nouns: S ... Intuitively, if a neural network embeds parse trees, it likely will not use its entire representation space to do so, since it needs to encode many kinds of information. Our probe learns a linear transformation of a word representation space such that the transformed space embeds parse trees across all sentences. This can be interpreted as finding the part of the representation space that is used to encode syntax; equivalently, it is finding the distance on the original space that best fits the tree metrics. In this section we provide a description of our proposed structural probe, first discussing the distance formulation. Let M be a model that takes in a sequence of n words w (cid:96) 1: n and produces a sequence of vector representations h (cid:96) 1: n , where (cid:96) identifies the sentence. Starting with the dot product, recall that we can define a family of inner products, h TA h , parameterized by any positive semi-definite, symmetric matrix A  S m  m + . Equivalently, we can view this as specifying a linear transformation B  R k  m , such that A = BTB . The inner product is then ( B h ) T ( B h ) , the norm of h once transformed by B . Every inner product corresponds to a distance metric. Thus, our family of squared distances is defined as: d B ( h (cid:96)i , h (cid:96)j ) 2 = (cid:0) B ( h (cid:96)i  h (cid:96)j ) (cid:1) T (cid:0) B ( h (cid:96)i  h (cid:96)j ) (cid:1) (1) where i, j index the word in the sentence. 2 The parameters of our probe are exactly the matrix B , which we train to recreate the tree distance between all pairs of words ( w (cid:96)i , w (cid:96)j ) in all sentences T (cid:96) in the training set of a parsed corpus. Specifically, we approximate through gradient descent: min B (cid:88) (cid:96) 1 | s (cid:96) | 2 (cid:88) i,j (cid:12)(cid:12) d T (cid:96) ( w (cid:96)i , w (cid:96)j )  d B ( h (cid:96)i , h (cid:96)j ) 2 (cid:12)(cid:12) where | s (cid:96) | is the length of the sentence; we normalize by the square since each sentence has | s (cid:96) | 2 word pairs. Because our structural probe defines a valid distance metric, we get a few nice properties for free. The simplest is that distances are guaranteed nonnegative and symmetric, which fits our probing task. Perhaps most importantly, the probe tests the concrete claim that there exists an inner product on the representation space whose squared distance a global property of the spaceencodes syntax tree distance. This means that the model not only encodes which word is governed by which other word, but each word's proximity to every other word in the syntax tree. 3 This is a claim about the structure of the representation space, akin to the claim that analogies are encoded as vector-offsets in uncontextualized word embeddings (Mikolov et al., 2013). One benefit of this is the ability to query the nature of this structure: for example, the dimensionality of the transformed space (  4.1). The second tree property we consider is the parse depth (cid:107) w i (cid:107) of a word w i , defined as the number of edges in the parse tree between w i and the root of the tree. This property is naturally represented as a norm  it imposes a total order on the words in the sentence. We wish to probe to see if there exists a squared norm on the word representation 2 As noted in Eqn 1, in practice, we find that approximating the parse tree distance and norms with the squared vector distances and norms consistently performs better. Because a distance metric and its square encode exactly the same parse trees, we use the squared distance throughout this paper. Also strictly, since A is not positive definite, the inner product is indefinite, and the distance a pseudometric. Further discussion can be found in our appendix. 3 Probing for distance instead of headedness also helps avoid somewhat arbitrary decisions regarding PP headedness, the DP hypothesis, and auxiliaries, letting the representation disagree on these while still encoding roughly the same global structure. See Section 5 for more discussion. Table 1 : Results of structural probes on the PTB WSJ test set; baselines in the top half, models hypothesized to encode syntax in the bottom half. For the distance probes, we show the Undirected Unlabeled Attachment Score (UUAS) as well as the average Spearman correlation of true to predicted distances, DSpr. For the norm probes, we show the root prediction accuracy and the average Spearman correlation of true to predicted norms, NSpr. Figure 1 : Parse distance UUAS and distance Spearman correlation across the BERT and ELMo model layers. space that encodes this tree norm. We replace the vector distance function d B ( h i , h j ) with the squared vector norm (cid:107) h i (cid:107) 2 B , replacing Equation 1 with (cid:107) h i (cid:107) A = ( B h i ) T ( B h i ) and training B to recreate (cid:107) w i (cid:107) . Like the distance probe, this norm formulation makes a concrete claim about the structure of the vector space. Using our probe, we evaluate whether representations from ELMo and BERT, two popular English models pre-trained on language modeling-like objectives, embed parse trees according to our structural hypothesis. Unless otherwise specified, we permit the linear transformation B to be potentially full-rank (i.e., B is square.) Later, we explore what rank of transformation is actually necessary for encoding syntax (  4.1). Representation models We use the 5.5B-word pre-trained ELMo weights for all ELMo representations, and both BERT-base (cased) and BERT-large (cased). The representations we evaluate are denoted ELMOK, BERTBASEK, BERTLARGEK, where K indexes the hidden layer of the corresponding model. All ELMo and BERT-large layers are dimensionality 1024; BERT-base layers are dimensionality 768. Data We probe models for their ability to capture the Stanford Dependencies formalism (de Marn-effe et al., 2006), claiming that capturing most aspects of the formalism implies an understanding of English syntactic structure. To this end, we obtain fixed word representations for sentences of the parsing train/dev/test splits of the Penn Treebank (Marcus et al., 1993), with no pre-processing. 4 Baselines Our baselines should encode features useful for training a parser, but not be capable of parsing themselves, to provide points of comparison against ELMo and BERT. They are as follows: LINEAR : The tree resulting from the assumption that English parse trees form a left-to-right chain. A model that encodes the positions of words should be able to meet this baseline. ELMO 0 : Strong character-level word embeddings with no contextual information. As these representations lack even position information, we should be completely unable to find syntax trees embedded. DECAY 0 : Assigns each word a weighted average of all ELMO 0 embeddings in the sentence. The weight assigned to each word decays exponentially as 12 d , where d is the linear distance between the words. PROJ 0 : Contextualizes the ELMO 0 embeddings with a randomly initialized BiLSTM layer of dimensionality identical to ELMo (1024), a surprisingly strong baseline for contextualiza-tion (Conneau et al., 2018). We evaluate models on how well the predicted distances between all pairs of words reconstruct gold parse trees and correlate with the parse trees' distance metrics. To evaluate tree reconstruction, we take each test sentence's predicted parse tree distances and compute the minimum spanning tree. We evaluate the predicted tree on undirected 4 Since BERT constructs subword representations, we align subword vectors with gold Penn Treebank tokens, and assign each token the average of its subword representation. This thus represents a lower-bound on BERT's performance. Figure 2 : Minimum spanning trees resultant from predicted squared distances on BERTLARGE 16 and ELMO 1 compared to the best baseline, PROJ 0. Black edges are the gold parse, above each sentence; blue are BERTLARGE 16, red are ELMO 1, and purple are PROJ 0. attachment score (UUAS)the percent of undirected edges placed correctlyagainst the gold tree. For distance correlation, we compute the Spearman correlation between true and predicted distances for each word in each sentence. We average these correlations between all sentences of a fixed length, and report the macro average across sentence lengths 550 as the distance Spearman (DSpr.) metric. 5 3.2 Tree depth evaluation metrics We evaluate models on their ability to recreate the order of words specified by their depth in the parse tree. We report the Spearman correlation betwen the true depth ordering and the predicted ordering, averaging first between sentences of the same length, and then across sentence lengths 550, as the norm Spearman (NSpr.). We also evaluate models' ability to identify the root of the sentence as the least deep, as the root%. 6 4 Results We report the results of parse distance probes and parse depth probes in Table 1. We first confirm that our probe can't simply learn to parse on top of any informative representation, unlike parser-based probes (Peters et al., 2018b). In particular, ELMO 0 and DECAY 0 fail to substantially outperform a right-branching-tree oracle that encodes the linear sequence of words. PROJ 0, which has all of the representational capacity of ELMO 1 but none of the training, performs the best among the baselines. Upon inspection, we found that our probe on PROJ 0 improves over the linear hypothesis with 5 The 550 range is chosen to avoid simple short sentences as well as sentences so long as to be rare in the test data. 6 In UUAS and root% evaluations, we ignore all punctuation tokens, as is standard. Figure 3 : Parse tree depth according to the gold tree (black, circle) and the norm probes (squared) on ELMO 1 (red, triangle) and BERTLARGE 16 (blue, square). mostly simple deviations from linearity, as visualized in Figure 2. We find surprisingly robust syntax embedded in each of ELMo and BERT according to our probes. Figure 2 shows the surprising extent to which a minimum spanning tree on predicted distances recovers the dependency parse structure in both ELMo and BERT. As we note however, the distance metric itself is a global notion; all pairs of words are trained to know their distance  not just which word is their head; Figure 4 demonstrates the rich structure of the true parse distance metric recovered by the predicted distances. Figure 3 demonstrates the surprising extent to which the depth in the tree is encoded by vector norm after the probe transformation. Between models, we find consistently that BERTLARGE performs better than BERTBASE , which performs better than ELMO . 7 We also find, as in Peters et al. (2018b), a clear difference in syntactic information between layers; Figure 1 reports the performance 7 It is worthwhile to note that our hypotheses were developed while analyzing LSTM models like ELMo, and applied without modification on the self-attention based BERT models. Figure 4 : (left) Matrix representing gold tree distances between all pairs of words in a sentence, whose linear order runs top-to-bottom and left-to-right. Darker colors indicate close words, lighter indicate far. (right) The same distances as embedded by BERTLARGE 16 (squared). More detailed graphs available in the Appendix. Figure 5 : Parse distance tree reconstruction accuracy when the linear transformation is constrained to varying maximum dimensionality. With the result that there exists syntax-encoding vector structure in both ELMo and BERT, it is natural to ask how compactly syntactic information is encoded in the vector space. We find that in both models, the effective rank of linear transformation required is surprisingly low. We train structural probes of varying k , that is, specifying a matrix B  R k  m such that the transformed vector B h is in R k . As shown in Figure 5, increasing k beyond 64 or 128 leads to no further gains in parsing accuracy. Intuitively, larger k means a more expressive probing model, and a larger fraction of the representational capacity of the model being devoted to syntax. We also note with curiosity that the three models we consider all seem to require transformations of approximately the same rank; we leave exploration of this to exciting future work. Recent work has analyzed model behavior to determine if a model understands hierarchy and other linguistic phenomena (Linzen, 2018; Gulordava et al., 2018; Kuncoro et al., 2018; Linzen and Leonard, 2018; van Schijndel and Linzen, 2018; Tang et al., 2018; Futrell et al., 2018). Our work extends the literature on linguistic probes, found at least in (Pe-ters et al., 2018b; Belinkov et al., 2017; Blevins et al., 2018; Hupkes et al., 2018). Conneau et al. (2018) present a task similar to our parse depth prediction, where a sentence representation vector is asked to classify the maximum parse depth ever achieved in the sentence. Tenney et al. (2019) evaluates a complementary task to ours, training probes to learn the labels on structures when the gold structures themselves are given. Peters et al. (2018b) evaluates the extent to which constituency trees can be extracted from hidden states, but uses a probe of considerable complexity, making less concrete hypotheses about how the information is encoded. Probing tasks and limitations Our reviewers rightfully noted that one might just probe for headedness, as in a bilinear graph-based dependency parser. More broadly, a deep neural network probe of some kind is almost certain to achieve higher parsing accuracies than our method. Our task and probe construction are designed not to test for some notion of syntactic knowledge broadly construed, but instead for an extremely strict notion where all pairs of words know their syntactic distance, and this information is a global structural property of the vector space. However, this study is limited to testing that hypothesis, and we foresee future probing tasks which make other tradeoffs between probe complexity, probe task, and hypotheses tested. In summary, through our structural probes we demonstrate that the structure of syntax trees emerges through properly defined distances and norms on two deep models' word representation spaces. Beyond this actionable insight, we suggest our probe may be useful for testing the existence of different types of graph structures on any neural representation of language, an exciting avenue for future work. We would like to acknowledge Urvashi Khandel-wal and Tatsunori B. Hashimoto for formative advice in early stages, Abigail See, Kevin Clark, Siva Reddy, Drew A. Hudson, and Roma Patel for helpful comments on drafts, and Percy Liang, for guidance on rank experiments. We would also like to thank the reviewers, whose helpful comments led to increased clarity and extra experiments. This research was supported by a gift from Tencent.
result abstain objective abstain result abstain abstain abstain abstain abstain objective abstain objective result abstain abstain abstain objective abstain method other abstain abstain abstain abstain abstain abstain abstain abstain method abstain method abstain method method abstain abstain method method method method method abstain abstain abstain abstain method abstain method method abstain method abstain abstain abstain method method abstain abstain method abstain abstain abstain abstain abstain abstain abstain result abstain abstain abstain abstain result abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain result abstain abstain abstain result abstain abstain abstain result abstain abstain abstain result abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain method abstain abstain result abstain abstain abstain result method method objective abstain other other other