Inducing Syntactic Trees from BERT Representations
Rudolf Rosa David Mareček

Improved Distributed Approximations for Maximum-Weight Independent Set
    Ken-ichi KawarabayashiNII, Japan, 
		Seri KhouryUniversity of California, Berkeley,  seri_khoury@berkeley.eduAaron SchildUniversity of California, Berkeley, Gregory SchwartzmanNII, Japan, 
    
================================================================================================================================================================================================































§ INTRODUCTION


One of the traditional linguistic criteria for recognizing dependency relations
in a sentence is that a head of a syntactic construction determines its syntactic category and can often replace it without any damage of syntactic correctness <cit.>.


<cit.> use similar principle for unsupervised dependency parsing. They estimate “reducibility”, a property describing how easily a word may be omitted from sentence without damaging it. Their hypothesis is that reducible words are more likely to occur as leaves in dependency trees. 


They simply declare a word reducible if the same sentence without this word appears elsewhere in the corpus. This very sparse method showed that reducibility of adjectives and adverbs is high, whereas reducibility of verbs is quite low.

With the advance of neural-network language models, e.g. BERT <cit.> or ELMo <cit.>,
there are new ways how to estimate reducibilities of words. In this paper, we use English model of BERT and explore how a deletion of one word in a sentence changes representations of other words.
Our hypothesis is that removing a reducible word (e.g. an adjective) does not affect representation of other words so much as removing e.g. the main verb, which makes the sentence ungrammatical and of “high surprise” for the language model.



We estimate reducibilities of individual words and also of longer phrases (word n-grams), study their syntax-related properties, and then also use them to induce full dependency trees.

A significant difference between our work and most previous works <cit.> is that we estimate the reducibilities and dependency trees directly from the models, without any training on syntactically annotated data.





§ REDUCIBILITY SCORES FROM BERT


TODO obrázek by byl supr

We use the pretrained English model (BERT-Large, uncased)[<https://storage.googleapis.com/BERT_models/2018_10_18/uncased_L-24_H-1024_A-16.zip>], and sentences from the development part of the EWT English treebank from Universal Dependencies 2.3 <cit.>; we subselect sentences containing only words included in the vocabulary of the BERT model.

We compute the reducibility r_p,s of each phrase p (any word or continuous sequence of words) in each sentence s as the average change of BERT representations of the words in the sentence when the phrase p is removed. By a BERT representation of a word we mean the state on the last layer of the BERT encoder on the position corresponding to the word.

    r_p,s = 1/|s_-p|∑_w ∈ s_-p ||b_w, s - b_w, s_-p||_2

where s_-p is the sentence s with phrase p removed, b_w, s is the BERT representation of word w in sentence s, and the distance of the BERT representations is the Euclidean distance.
The b_w, s_-p representations are obtained by simply running BERT on the sentence s with phrase p deleted. 

poznamenat že tohle je spíš sémantická reducibilita, zatimco my "chceme" spíš syntaktickou reducibiklitu?










§ LINGUISTIC PROPERTIES OF REDUCIBILITIES


vyhodit nějaký nebo všechny obrázky?

In Figure <ref>, we show reducibility scores of all the words in our testing data
and average reducibility scores for individual part-of-speech tags.
To visualise how the word reducibility correlates with being a leaf in the dependency tree, we color all the leaf instances by yellow and all the non-leaf by blue. It is apparent that in the right side of the graph, the blue instances prevail.

The absolute word reducibilities are different in each sentence, but we have found that the threshold separating leafs and non-leaves in a given sentence is around 1.2× the average word reducibility in that sentence. This allows us to separate leafs from non-leaves with an accuracy of 74.5%, compared to the baseline of 66.4% (assuming everything is a leaf).



The syntactic root of the sentence tends to be the least reducible word. It is so in 34% of the sentences; or in 46% if we ignore punctuation, which tends to be very irreducible.
The random baseline here is 13%.








The dependency edge direction can be identified with a 70.6% accuracy, assuming that the parent

should be less reducible than the child node.
The right-chain baseline, assuming that parent is to the right of the child, has a 65.8% accuracy.








§ BUILDING DEPENDENCY TREES


We now examine to which extent the reducibilities extracted from BERT can be used to build dependency trees. We propose two algorithms, and compare them to an uninformed baseline, which
is the right chain, attaching each node to its right neighbor;

the rightmost node becomes the root.
For English, this is quite a strong baseline.



Algorithm D:
In Algorithm D, we construct a projective dependency tree based on phrase reducibilities.


We use the recursive headed brackets encoding, where each subtree is enclosed in one pair of brackets, containing subtrees (phrases in brackets) and just one head (word without brackets), e.g.:
( (subtree) head (subtree) (subtree) ).


In each step, we greedily insert a new pair of brackets corresponding to the most reducible phrase such that
the resulting structure still satisfies the following conditions:




(a) brackets do not cross each other
(b) each subtree has a head.
Table <ref> shows that the resulting structures only slightly surpass the uninformed baseline (this can be improved by explicitly setting a low reducibility for punctuation).







    
    





Algorithm R:
Algorithm R directly builds upon the right-chain baseline, modifying it by introducing a constraint that the parent of each node must be less reducible than the child node; the least reducible node becomes the root.
Each node is thus attached to the nearest subsequent more reducible node; or to the root if all subsequent nodes are less reducible.


Table <ref> shows that this outperforms the baseline by 7 (or 11) percentage points.































§ CONCLUSIONS


We examine to what extent reducibility, which underlies dependency syntactic structures, can be estimated from BERT representations.
We devise a method based on measuring the differences in the representations when a word or phrase is removed from the sentence, and denoting this difference as the reducibility score of that word or phrase.
We find that such scores partially correspond to the notion of reducibility in dependency trees, seeing a tendency of child nodes and leaf nodes to be more reducible than parent nodes and the root.
We also show that these scores can be used in a simple parsing algorithm to construct dependency trees which are more accurate than an uninformed baseline.






§ ACKNOWLEDGEMENTS

This work has been supported by the grant 18-02196S of the Czech
Science Foundation and uses language resources and tools developed and
stored by the LINDAT/CLARIN project
(LM2015071).



acl_natbib

