Ensemble Distillation for Unsupervised Constituency Parsing
Authors: Behzad Shayegh
Yanshuai Cao
Xiaodan Zhu
Jackie CK Cheung
Lili Mou
Venue: ICLR 2024 poster (2024)
Keywords: Constituency Parsing
Unsupervised Grammar Induction
Knowledge Distillation
Primary area: representation learning for computer vision, audio, language, and other modalities
TL;DR: The paper proposes an ensemble method and multi-teacher distillation approach for unsupervised constituency parsing, demonstrating robustness and effectiveness.

Abstract: We investigate the unsupervised constituency parsing task, which organizes words and phrases of a sentence into a hierarchical structure without using linguistically annotated data. We observe that existing unsupervised parsers capture different aspects of parsing structures, which can be leveraged to enhance unsupervised parsing performance.
To this end, we propose a notion of "tree averaging," based on which we further propose a novel ensemble method for unsupervised parsing.
To improve inference efficiency, we further distill the ensemble knowledge into a student model; such an ensemble-then-distill process is an effective approach to mitigate the over-smoothing problem existing in common multi-teacher distilling methods.
Experiments show that our method surpasses all previous approaches, consistently demonstrating its effectiveness and robustness across various runs, with different ensemble components, and under domain-shift conditions.

Published as a conference paper at ICLR 2024
ENSEMBLE DISTILLATION FOR UNSUPERVISED CONSTITUENCY PARSING
Behzad Shayegh Yanshuai Cao² Xiaodan Zhu Jackie C.K. Cheung Lili Mou
Dept. Computing Science, Alberta Machine Intelligence Institute (Amii), University of Alberta 2 Borealis AI Dept. Electrical and Computer Engineering, Queen's University 'Ingenuity Labs Research Institute, Queen's 's University
5 QQeebec Artificial Intelligence Institute (MILA), McGill University
CCnada CIFAR Al Chair
the. , whayechh@mai...com
yanshuai. www.shaaacccooooralaaaaaa.. com.
xiaodan zhu@queensuuuuur
jcheungecs megill..a
doublepower moul gma.l.m......... com com
ABSTRACT
We investigate the unsupervised constituency parsing task, which organizes words and phrases of sentence into a hierarchical structure without using linguistically annotated data. We observe that existing unsupervised parsers capture different aspects of parsing structures, which can be leveraged to enhance unsupervised parsing performance. To this end, we propose a notion of "tree averaging." based on which we further propose a novel ensemble method for unsupervised parsing. To improve inference efficiency, student model; such an ensemble-then-disee mitigate the over-smoothing problem existing in common multi-teacher distilling methods. Experiments show that our method surpasses all previous approaches, consistently demonstrating its effectiveness and robustness across various runs, with different ensemble components, and under domain-shift conditions
further distill the ensemble knowledge into process is an effective approach to
INTRODUCTION
Constituency parsing is well-established task in natural language processing (NLP), which inter- prets a sentence and induces its constituency tree, syntactic structure representation that organizes words and phrases into a hierarchy (Chomsky) 1967). ). It has wide applications in various downstream tasks, including semantic role labeling (Mohammadshahi & Henderson 2023) and explainability of AI models (Tenney al.) 2019 Wu et al.] (022). Traditionally, parsing accomplished by super- vised models trained with linguistically annotated treebanks (Charniak) 2000), which are expensive to obtain and may not be available for low-resource scenarios. Also, these supervised parsers often underperform when encountering domain shifts. This motivates researchers to explore unsupervised methods as they eliminate the need for annotated data.
To address unsupervised parsing, researchers have proposed various heuristics and indirect pervision signals. Clark (200T) employs context distribution clustering to induce a probabilistic context-free grammar (PCFG; Booth 1969). Klein & Manning (2002) define joint distribution for sentences and parse structures, the latter learned by expectation maximization (EM) algorithms. Snyder al. (2009) further extend unsupervised parsing the multilingual setting with bilingual supervision.
In the deep learning era, unsupervised parsing techniques keep advancing. Cao et al. (2020) uti- lize linguistic constituency tests (Chomsky) 1967) as heuristics, evaluating all spans as potential constituents for selection. [i & Lu (2023) modify each span based on linguistic perturbations and observe changes in the contextual representations of masked language model; according to the level of distortion, they determine how likely the span is constituent. Maveli Cohen (2022) use rules to train two classifiers with local features and contextual features, respectively, which are fur- ther refined in a co-training fashion. Another way to obtain the parsing structure an unsupervised
Work partially done during Mitacs intersship at Borealis AI. Code available whtttps:// / thub. cwm/coo//aaaoooo WOo./MAAGA--AA UOGAAAAUUOOAAAAAA KDUUCP

---

Published as a conference paper at ICLR 2024
Compound PCFG
100
DIORA
DIORA
55.8
100
S-DIORA
58.1
63.6
100
DIORA
74.1
100
Compound PCFG
DIORA
S-DIORA
DIORA
14.3
74.3
100
DIORA
DIORA
DIORA#
Table 1: Correlation analysis of unsupervised parsers. Numbers are the Fi score of one model against another the Penn Treebank dataset (Marcus al. [993). The left table considers three heterogeneous models (Compound PCFG, DIORA, and S-DIORA), whereas the right table consid- ers three runs (xz, 4, and *) of the same model. All their F' scores against the groundtruth fall within the range of 59-61, thus providing a controlled experimental setting.
way is to treat it as a latent variable and train it in downstream tasks, such as text classification (Li et al. 2019), language modeling (Shen et al. 2019 Kim et al. 2019b), and sentence reconstruc-
tion Drozdov et al.) 2019; Kim et al. 2019a). Overall, unsupervised parsing is made feasible by such heuristies and indirect supervisions, and has become curious research direction in NLP.
In our work, we uncover an intriguing phenomenon of low correlation among different unsupervised parsers, despite their similar overall F1 scores (the main evaluation metric for parsing), shown in [ While Williams et al. (2018) have shown low self-consistency in early latent-tree models, go further and show the correlation among different models is even lower than restarts of the same model. This suggests that existing unsupervised parsers capture different aspects of the structures, and our insight is that combining these parsers may leverage their different expertise to achieve higher performance for unsupervised parsing.
To this end, we propose an ensemble method for unsupervised parsing. We first introduce notion of "tree averaging" based on the similarity of two constituency trees. Given a few existing unsupervised parsers, referred to as teachers? 2 we then propose to use CYK-like algorithm (Kasami 1966, Younger 1967, Manacher 1978; Sennrich] 2014) that utilizes dynamic programming to search for the tree that is most similar to all teachers' outputs. In this way, we are able to obtain an "average" parse tree, taking advantage of different existing unsupervised parsers.
To improve the inference efficiency, we distill our ensemble knowledge into a student model. In particular, choose the recurrent neural network grammar (RNNG; Dyer et al. 2016) with an unsupervised self-training procedure (URNNG; Kim et al. 2019b), following the common practice in unsupervised parsing (Kim et al., 2019a Cao et al. 2020). Our mnsmmblethhnn-ditill process is able to mitigate the over-smoothing problem, where the standard cross-entropy loss encourages the student learn an overly smooth distribution (Wen et al.) (023b)). Such a problem exists in common multi-teacher distilling methods (Wu et al. 2021). and would be especially severe when the teachers are heterogeneous, sigmifying the importance of our approach.
We evaluated our ensemble method on the Penn Treebank (PTB; Marcus et al. 1993) and SU- SANNE (Sampson 2002) corpora. Results show that our approach outperforms existing unsuper- vised parsers by large margin in terms of Fi scores, and that it achieves results comparable to the supervised counterpart in the domain-shift setting. Overall, our paper largely bridges the gap between supervised and unsupervised constituency parsing.
In short, the main contributions of this paper include: We reveal an intriguing phenomenon that existing unsupervised parsers have diverse expertise, which may be leveraged by model ensembles; 2) We propose a notion of tree averaging and utilize a CYK-like algorithm that searches for the av- erage tree of existing unsupervised parsers; and 3) We propose an ensemble-then-disti approach to improve inference efficiency and to alleviate the over-smoothing problem in common multi-teacher distilling approaches.
2
APPROACH
2.1
UNSUPERVISED CONSTITUENCY PARSING
In linguistics, a constituent refers to a word or a group of words that function as a single unit in a hierarchical tree structure (Chomsky 1967). In the sentence "The quick brown fox jumps over
?Our full approach involves training student model from the ensemble; thus, it is appropriate to use the term teacher for ensemble component.
2

---

Published as a conference paper at ICLR 2024
the lazy dog," for example, the phrase "the lazy dog" serves "jumps over the lazy dog" is a verb phrase constituent. In this study, we address unsupervised constituency parsing, where no linguistie annotations are used for training. This reduces human labor and is potentially useful for low-resource languages. Following most previous work this direction (Cao et al. 2020 Maveli & Cohen 2022 Li & Lu (023), we focus on unlabeled, binary parse trees, in which each constituent has a binary branching and is not labeled with its syntactic role (such noun phrase verb phrase).
phrase constituent, whereas
The standard evaluation metric for constituency parsing is the Pi score, which is the harmonic mean of precision and recall (Shen al., 2018 Zhang al., (02I]:
P = (repp)) n (Teee) C((pred)
R C(T n C(Tier) Fi = P P R [C((Te)
PR
(1)
where pred and Teet are predicted and reference trees, respectively, and C(T) the set of con- stituents in a tree T.
2.2 NOTION OF AVERAGING CONSTITUENCY TREES
In our study, we propose ensemble approach to combine the expertise of existing unsupervised parsers (called teachers), as we observe they have low correlation among themselves despite their similar overall F1 scores [T.
To accomplish ensemble binary constituency parsing, we need to define a notion of tree averaging: that is, our ensemble output is the average tree that is most similar to all teachers' outputs. Inspired by the evaluation metric, we suggest the average tree should have the highest total Fi score compared with different teachers. Let be sentence and Tj be the kth teacher parser. Given K teachers, define the average tree to be
K
AvgTreo(s, (T&) arg max TET(s)
Σ (T()TT(())
where T(s) is all possible unlabeled binary trees sentence s, and (s)(s) is the kth teacher's output.
is emphasized that only the trees of the same sentence can be averaged. This simplifies the F1 score of binary trees, as the denominators for both precision and recall are 2|s| for sentence can be rewritten as:
with |s| words, i.c., [C(Tpoa) = |C(Taa) 2|s - 1. Thus, Eqn.
2
K
I(TT)
AvgTroo(s, (Ta)K
arg max TET(()
Σ F((.TT((S))
arg max TET(#)
(3)
2|s -1
k=1
arg max TET(s) eEC(T)
Σ
Σ Ice C(T((s))
(4)
(T
Here, we define the HitCount function to be the number of times that a constituent appears in the teachers' outputs. other words, Eqn. (4) suggests that the average tree should be the one that hits the teachers' predicted constituents most.
Discussion on MBR decoding. Our work can be seen as minimum Bayes risk (MBR) decod- ing (Bickel & Doksum 2013). In general, MBR yields an output that minimizes an expected error (called Bayes risk), denned according to the task of interest. In our case, the error function can be thought of as EeEc(ry HilCount(e, { ). and minimizing such-defined Bayes risk is equivalent to maximizing the total hit count in Eqn.
However, our MBR approach significantly differs from prior MBR studies in NLP. In fact, MBR has been widely applied to text generation (Kumar& & Byrne 2004 Freitag et al. 2022 Suzgun et al.) 2023). where a set candidate output sentences are obtained by sampling or beam search, and the best one is selected based MBR method is selective, meaning that the output can only be selected from a candidate set. On the contrary, our MBR is generative, as the sentence's 's entire parse space T(s) will be considered
given error function, e.g., the dissimilarity against others; such an
3

---

Published as a conference paper at ICLR 2024
during the arg max process in 44. This follows Petrov & Klein (2007) who search for the global lowest-risk tree in the task of supervised constituency parsing. Here, the global search is feasible
because the nature of tree structures facilitates efficient exact decoding with dynamic programming, discussed in the next subsection.
2.3 OUR CYK VARIANT
As indicated by Eqn. our method searches for the constituency tree with the highest total hit count of its constituents in the teachers' outputs. We can achieve this by CYK (Kasami 1966 Younger 1967) -lik dynamic programming algorithm, because an optimal constituency parse struc- ture of span continuous subsequence of sentence- independent of the rest of the sentence.
Given a sentence s, we denote by Sh.e a span starting from the bth word and ending right before the eth word. Considering a set of teachers {Th k= we define recursion variable
Hore
maX
Σ
HitCount(c, (Ta(s))
(5)
(
CEC(T)
which is the best total hit count for this span We also define Lise to be the corresponding, locally best parse structure, unambiguously represented by the set of constituents in
The base cases are H5.+11 K and Tas+11 = {88++1} for b = 1. |s], suggesting that the best parse tree of a single-word span is the word itself, which appears in all teachers' outputs and has a hit count of K.
For recursion, we see a span Sh.e will be split into two subspans sby and 8ize for some split position j. because work focuses binary constituency parsing. Given j. the total hit count for the span Sb.e is the summation over those of the two subspans Sb.j and Sytes plus its own hit count. To obtain the best split, we need to vary j from b to (exclusive), given by
Thee arg max [Hhi + Hise + HitCount(shes (Ti(s)) bejce
where the hit count is a constant for arg max and can be omitted implementation. Then, we have
Hire = Hu:ss.. + Hsj. + HitCount (s)
(7)
Live = Losst.. U Lig. {
(8)
Eqn. (8) essentially groups two sub-parse structures Lest. and Lyg for the span St:e. This can be represented as the union operation on the sets of constituents.
The recursion terminates when we have computed L1:1+++1. which the best parse tree for the sentence s, maximizing overall similarity to the teachers' predictions and being our ensemble output. In Appendix A we summarize our ensemble procedure in pseudocode and provide an illustration.
2.4 ENSEMBLE DISTILLATION
In work, we further propose ensemble distilling approach that trains student parser from an ensemble of teachers. This is motivated by the fact that the ensemble requires performing infer- ence for all teacher models and may be slow. Specifically, we choose the recurrent neural network grammar (RNNG; Dyer et al.) 2016) as the student model, which learns shift-reduce parsing op- erations (Aho & Johnson 1974) along with language modeling using recurrent neural networks. The choice of RNNG is due to its unsupervised refinement procedure (URNNG; Kim et al. 2019b), which treats syntactic structures as latent variables and uses variational inference to optimize the joint probability of syntax and language modeling, given some unlabeled text. Such a self-training process enables URNNG to significantly boost parsing performance.
Concretely, we treat the ensemble outputs pseudo-grome groundtruth parse trees and use them to train RNNG with cross-entropy loss. Then, we apply URNNG for refinement, following previous work (Kim al. 2019a Cao et al. 2020).
Note that, in Eqns. sentence-level parsing.
8 (s( should not he Tx (s(ce)),, because the hit count is based on the teachers'
4

---

Published as a conference paper at ICLR 2024
Discussion union distillation. An alternative way of distilling knowledge from multiple teachers to perform cross-entropy training based on the union of the teachers' outputs (Wu et al. (021), which we call union distillation. Specifically, the cross-entropy loss between target distribution
and a learned distribution p is >n (xx) ) p(r), which tends to suffer from an over-smoothing
problem (Wei al. 2019; Wen al. 2023a b): the machine learning model will predict overly smooth distribution to cover the support of f; if otherwise p(z) is zero but f(x) is non-zero for
some 2, the cross-entropy loss would be infinity. Such an over-smoothing problem is especially severe in our scenario, as will be shown in Section 3.4 because our multiple teachers are hetero- geneous and have different expertise (Table I.. By contrast, our proposed method is an ensemble- then-distill approach, which first synthesizes best parse tree by model ensemble and then learns from the single best tree given an input sentence.
EXPERIMENTS
3.1 DATASETS
We evaluated our approach the widely used Penn Treebank (PTB;
Marcus 1993) dataset,
following most previous work (Shen et al. 2019 Kim et al.] 2019a Cao et al. 2020 Maveli &
Cohen 2022 Li & Lu 2023). We adopted the standard split: 39,701 samples in Sections 02-21 for training, 1,690 samples in Section 22 for validation, and 2,412 samples in Section 23 for test. It emphasized that did use linguistic annotations in the training set, but took the unlabeled sentences to train teacher unsupervised parsers and to distill knowledge into the student.
In addition, we used the SUSANNE dataset (Sampson 2002 to evaluate model performance in domain-shift setting. Since it is small, test-only dataset containing 6,424 samples in total, it is not possible to train unsupervised parsers directly on SUSANNE, which on the other hand provides an ideal opportunity for domain-shift evaluation.
We adopted the standard evaluation metric, the F1 score of unlabeled constituents, as has been explained in Section 2.1 We used the same evaluation setup as Kim al. (2019a), ignoring punctu- ation and trivial constituents, i.e., single words and the whole sentence. We reported the average of sentence-level F2 scores over the corpus.
3.2 COMPETING METHODS
Our ensemble approach involves the following classic or state-of-the-art unsupervised parsers as our teachers, which are also baselines for comparison.
Ordered Neurons (Shen et al., 2019), neural language model that learns syntactic structures
with a gated attention mechanism;
Neural PCFG (Kim et al. 2019a), which utilizes neural networks to learn a latent probabilistic context- free grammar;
Compound PCFG (Kim et al. 2019a), which improves the Neural PCFG by adding addi-
tional sentence- latent representation;
DIORA (Drozdov al.) 2019), a deep inside-outside recursive auto-encoder that marginalizes
latent parse structures during encoder-decoder training;
S-DIORA (Drozdov al. 2020), variant of DIORA that only considers the single most probable tree during unsupervised training;
Con'Test (Cao al. 2020). which induces parse trees by rules and heuristics inspired by con- stituency tests (McCawley 1998); and
ContexDistort (Li & Lu 2023), which induces parsing structures from pretrained masked lan- guage models in particular, the BERT-base model (Devlin et al. 2019) in our experiments- based on contextual representation changes caused by linguistic perturbations.
To combine multiple teachers, we consider several alternatives:
Selective MBR, which selects the lowest-risk constituency tree among a given candidate set (Section 2.2) In particular, consider teachers' outputs as the candidates, and we have
MelsctiveMBR(s. (Ta)k=)) arg maxTe(TT Σk_ (T, (T)). This differs from
5

---

Published as a conference paper at ICLR 2024
Method
Mean
Run
+RNNG +URNNG
1
Left branching
8.7
2
Right branching
39.5
Ordered Neurons (Shen
2019
44.3.660
44.8
45.4
45.3
Neural PCFG (Kim al.
51.0+1.7
48.4
48.9
51.1
Compound PCFG [Kmm
2019a
55.5
60.1
60.5
67.4
6
DIORA Drozdov èt al. 2019
18.9
55.4
58.6
62.3
7
S-DIORA (Drozdov et al.
2020
57.0
56.3
59.4
62.2
8
Con'Test CCoo ct al. 2020
62.9
65.9
61.6
68.5
9
ContexDistor (LI & Lu 2023
47.810.9
48.8
48.5
50.8
Union distillation
65.6
65.4
11
Selective MBR
66.3
66.7
68.6
71.5
12
Our ensemble (corresponding run)
70.440.6
70.5
69.7
71.7
13
Our ensemble (worst teacher across rums)
69.1
69.1
70.0
14
Our ensemble (best teacher across runs)
71.9
71.1
72.8
15
Oracle
83.3
76.0
76.0
Table 2: F1 scores on PTB. Teacher models' results are given by our five runs of replication (de- tailed in Appendix [E) for fair comparison. Due to the limit of computing resources, trained RNNG/URNNG with the first run only. The oracle refers to the highest possible Fi score of a binary tree, as the groundtruth may not be binary.
our MBR approach, which is generative and performs the arg max the entire binary tree space, shown in Eqn. (2).
Union distillation, which trains student from the union of the teachers' outputs (Section 2.4
For hyperparameters and other setups of previous methods (all teacher and student models), we used default values mentioned in either papers or codebases. should be emphasized that our proposed ensemble approach does not have any hyperparameters, thus not requiring any tuning.
3.3
MAIN RESULTS
Results PTB. Table 2 presents the main results on the PTB dataset, where performed five runs of replication either by loading original authors' checkpoints or by rerunning released code- bases. Our replication results comparable those reported in previous papers, inventoried in Appendix E showing that we have successfully established a foundation for our ensemble research.
We first evaluate our ensembles of corresponding runs (Row 12), which is fair comparison against teacher models (Rows 3-9). Without RNNG/URNNG distillation, our method outperforms the best teacher (Row 8) by 7.5 points in terms of scores, showing that ensemble approach is highly effective and justifying the proposed notion of tree averaging for unsupervised parsing.
also possible have an ensemble of the best (or worst) teachers, one per each model across different runs, as the teacher models are all validated by a labeled development set. We observe that the ensemble of the best worst) teachers achieves slightly higher (or lower) scores than the ensemble of the teachers in corresponding runs, which is intuitive. However, the gap between the best-teachers ensemble and worst-teachers ensemble small (Rows 13 vs. 14), showing that our approach is not sensitive to the variance of teachers. Interestingly, the ensemble of the worst teachers still outperforms the best single teacher by a large margin of 6.5 F1 points.
We compare ensemble approach with selective MBR (Row 11), which selects minimum-risk tree from the teachers' predictions. As shown, selective MBR outperforms all the teachers too, again verifying the effectiveness of tree-averaging formulation. However, its performance is worse than our method (Row 12), which can be thought of as generative MBR that searches the entire tree space using CYK-like algorithm.
Then, we evaluate the distillation stage of our approach, which is based on Run of each model. We observe RNNG and URRNG follow the same trend in previous work that RNNG may slightly

---

Published as a conference paper at ICLR 2024
hurt the performance, but its URNNG refinemen yields performance boost. It is also noted that URNNG's boosting effect on our approach is less significant than that on previous models, which is reasonable because ensemble (w/o RNNG or URNNG) has already achieved high performance. Overall, we achieve an Fi score of 72.8 in Row 14, being a new state of the art of unsupervised parsing and largely bridging the gap between supervised and unsupervised constituency parsing.
We compare our mnsemble-then-diiee approach with union distillation (Row 10), which trains from the union of the teachers' first-run outputs. As expected in Section 2.4 union distillation does not work well; its performance is worse than that of the best teacher (Run of Row 8), suggesting that multiple teachers may confuse the student and hurt the performance. Rather, our approach requires all teachers to negotiate most agreed tree, thus avoiding confusion during the distilling process.
Results on SUSANNE. Table presents parsing performance under domain shift from PTB to SU- SANNE. We directly ran unsupervised PTB-trrined models the test-only SUSANNE corpus without finetuning. This is realistic experiment to examine the models' performance in unseen low-resource domain.
Method
Run
+RNNG +URNNG
Left branching
6,9
Right branching
Ordered Neurons
32.4
33.1
33.1
Neural PCFG
44.2
46.1
48.6
Compound PCFG
43.0
43.4
46.5
DIORA
35.9
12.2
11.0
S-DIORA
37.5
42.4
ConTest
38.8
46.9
47.3
We see both selective MBR (Row 10) and our method (Row 11) outperform all teachers (Rows 3- 9) in the domain-shift setting, and that our approach outperforms selective MBR by 3 points. The results consistent with the PTB experiment.
Contex
41.2
39.7
41.1
10
Selective MBR
47.4
48.4
48.5
11
Our ensemble
50.3
49.1
48.8
12
PTB-supervised
50.1
49.8
13
SUSANNE oracle
69.8
Table 3: F1 scores in the domain-shift setting from PTB to SUSANNE. Note that all mod- els were trained PTB, including RNNGs and URNNGs. Since our approach is highly robust, only considered the models of the first run on PTB in this experiment.
For the ensemble-distilled RNNG and URNNG (Row 11), the performance drops slightly, proba- bly because the performance of our ensemble ap- proach without RNNG/URNNG is saturating and close to the PTB-supervised model (Row 12), whose RNNG/URNNG distillation also yields slight per- formance drop. Nevertheless, our RNNG and URNNG (Row 11) outperform all the baselines in all settings. Moreover, the inference of our student model does not require querying the teachers, and is 18x faster than the ensemble method (Appendix B. Thus, the ensemble-distilled model is useful as achieves competitive performance and high efficiency.
3.4 IN-DEPTH ANALYSIS
Denoising vs. utilizing different expertise. A curious question raised from the main results is why our ensemble approach yields such a substantial improvement. We have two plausible hypotheses: 1) The ensemble approach merely smooths out the teachers' noise, and 2) The ensemble approach is able to utilize different expertise of heterogeneous teachers.
We conducted the following experiment to verify the above hypotheses. Specifically, compare two settings: the ensemble of three runs of the same model and the ensemble of three heterogeneous models. We picked the runs and models such that the two settings have similar performance. This sets up controlled experiment, as the gain obtained by the ensemble of multiple runs suggests a denoising effect, whereas further gain obtained by the ensemble of heterogeneous models suggests the effect of utilizing different expertise.
We repeated the experiment for seven groups with different choices of models and show results in Figure [ As seen, the ensemble of different runs always outperforms single run, showing that the denoising effect does play a role the ensemble process. Moreover, the ensemble of heterogeneous models consistently leads to large add-on improvement compared with the ensemble of multiple runs; the results convincingly verify that different unsupervised parsers learn different aspects of the language structures, and that ensemble approach is able to utilize such different expertise.
*URNNG is traditionally used refinement procedure following a noisily trained RNNG Kim et al. 2019a Cao al. (2020). If URNNG is trained from scratch, it does not yield meaningful performance and may he than right-branching (Kim et al. 20196). Thus, we excluded URNNG from teachers.
7

---

Published as a conference paper at ICLR 2024
Additional boost
70
Ensemble of different runs Ensemble of different models
66.3
63.7
65.0
67.4
65.0
solizing
experthv
Genelann effect
63.6
60
57.3
601
66.0
59.4
540
5E3
60.0
58.3
59.4
63.6
61.8
62.1
66.0
53.9
554
5333
55.4
5544
53.9
5544
52
52.8
46.0
46
48.8
48
48
50
48
48.4
48.3
50
44
44
40
Orderee Nearsns
Ordered No con
Neurens
Ordered le Rearoes
Dr Dederen lo oo
Cam compodard PCG
parpoaad rund
Compound PCP2
Compoaad PCPG
Compoant RCG
Compour PCFS
Com paragiaaa PCRG
Ordined Ne ano
Conter
Contin Diitort
Netral RCFS
Netuaal PCRS
Neunal PCrD
Noual PCG
PCr
Contactiaton
Lorken
DYORA
5-RO0A
DIORA
DIONA
DIORA
BYORA
5-0IGA
S-00000
S.00
ConTeet
ConTect
Conteet
Contest
20
Group 1
Group 2
Group 3
Group 4
Group
Group 6
Group 7
Figure 1: Effect of denoising vs, utilizing different expertise. Results are the F1 scores on the PTB
test set. The italic blue annotation an interpretation of the plot.
Distillation Approach
Mean Entropy
Std
Union distillation
11.42
0.09
Our ensemble distillation
4.93
0.12
Binarized- -ronmduuut distillation
2.26
0.12
Table 4: The mean and standard deviation (std) of the prediction entropy for distilled RNNGs.
Over-smoothing in multi-teacher knowledge distillation. As discussed in Section 2.4 union distillation prone to the over-smoothing problem, where the student learns an overly smooth, wide-spreading distribution. This is especially severe in our setting, our student learns from multiple heterogeneous teachers.
The over-smoothing problem can be verified by checking the entropy. - -. p(x) ) log p(z), of a 65
70
model's predicted distribution p. In Table 4 report the mean and standard deviation of the en- tropy across five runs. Results clearly show that the union distillation leads to a very smooth distri- bution (very high entropy), which also explains its low performance (Table 2). On the contrary, our
60
55
50
Ensemble
ensemble-thers then-distill approach yields much lower
mest-performing combination
entropy. providing strong evidence of the alleviation of the over-smoothing problem.
Average combinations
Worst-performing combination
Analyzing the number of teachers. In our main
Number of teachers in ensemble
experiment (Table 2]. we perform an ensemble of seven popular unsupervised parsers. We would like to analyze the performance of ensemble models with different numbers of teachers and results are shown in Figure]
Figure 2: Ensemble performance with differ- ent numbers of teachers. The lines are best- performing, average, and porst-performing combinations. These results are averaged over five runs available in the experiments conducted for Table [ The gray shades are the best and worst runs.
We consistent trend that more teachers lead to higher performance. Profoundly, the top dashed line suggests that, even if we start with strong teacher, least does not hurt, the performance. Further, the decrease in the width of gray shades (deviations of best and worst runs) suggests that more teachers also lead lower variance. Overall, this anal- ysis conclusively shows that, with growing number of teachers, our ensemble approach not only improves performance, but also makes unsupervised parsing more robust.
adding weaker teachers also improves,
Additional results. We present supplementary analyses in the appendix. B.I Inference efficiency; B.2 Performance by sentence lengths; and B.3 Performance by different constituency types.
'The entropy each run averaged over 2,412 samples. The calculation of entropy is based on the codebase of Kim et (0019))). available at fihhtpps: / thub. com/harva hww./rrrvaannnn www.rdal//plii 1p/urnng We have 2 combinations, which tractable hecause CYK algorithm is efficient.
8

---

Published as a conference paper at ICLR 2024
4 RELATED WORK
Unsupervised syntactic structure discovery carries a long history and has attracted much attention in different ages (Klein, Shen et al.]|2221111 2019; Li & Lu 2023). Its significance lies in the potential to help low-resource domains (Kann et al. 2019 9 and its important role in cognitive science, such as understanding how children learn language (Bod 2009). Peng et al. (20TT) show unsupervised constituency parsing methods are not limited to linguistics but can also be used to parse motion- sensor data by treating it as a language. This approach finds abstraction of motion data and leads to better understanding of the signal semantics.
Unsupervised syntactic structure discovery can be divided into different tasks: unsupervised con- stituency parsing, which organizes the phrases of a sentence in a hierarchical manner (Chomsky) 1967;; unsupervised dependency parsing (Nivre) 2010; Naseem et al. 2010) Han al. 20200) which determines the syntactic relation between the words in sentence; and unsupervised chunk- ing, which aims at segmenting text into groups of syntactically related words in flattened struc-
ture (Desmmukh et al. 2021 Wu et al. 2023).
Our work falls in the category of unsupervised constituency parsing, Previous work has proposed various heuristics and indirect supervisions to tackle this task (Snyder et al. (2009) Kim et al. 22019, Drozdov et al., 2019; Shi et al. 2019). as mentioned in Section an ensemble model to utilize the expertise of different unsupervised parsers.
our work, we propose to build
Minimum Bayes risk (MBR) decoding minimizes Bayes risk (i.e., expected loss) during infer- ence (Bickel & Doksum 2015). For example, machine translation systems may generate set of candidate outputs, and define the risk as the dissimilarity between one candidate output and the rest; MBR decoding selects the lowest-risk candidate translation that is most similar to others (Kumar & Byrne 2004| Freitag et al., (2022). Similar approaches are applied to other decoding tasks, such as speech recogmition (Gibson & Hain 2006), text summarization (Suzgun al. 2023). text-to-code translation (hh et al., 2022), and dependency parsing (Smith & Smith 2007). ). For constituency parsing, Titov & Henderson (2006) formulate the task under the MBR framework, and Petrov & Klein (007)) extend it to state-split PCFGs.
In this work, we develop a novel generative MBR method for ensemble constituency parsing that searches the entire binary tree space by an efficient CYK-like dynamic programming. significantly differing from common MBR approaches that perform selection on a candidate set.
Knowledge distillation (KD) is commonly used to train small student model from large teacher model (Sun et al. 2019 Jiao al., 2020). Evidence show that the teacher's predicted probability contains more knowledge than groundtruth label and can better train the student model (Hinton ct al.
2015 Wen et al. 2023b).
Interestingly, KD is originally proposed to train a small model from an ensemble of teachers (Buciluă et al., 2006 Hinton et al. 2015). They address simple classification tasks and use either voting or average ensembles to train the student. A voting ensemble is similar to MBR, but only works for classification tasks; it cannot be applied to structure prediction (e-g., sequences or trees). An average ensemble takes the average of probabilities; thus, it resembles union distillation, which is the predominant approach for multi-teacher distillation in recent years (Wu et al.] 2021 Yang et al.) 2020). However, these approaches may suffer from the over-smoothing problem when teachers heterogeneous (Section (.4). In our work, we propose a novel MBR-based ensemble method for multi-teacher distillation, which largely alleviates the over-smoothing problem and is able utilize different teachers' expertise.
CONCLUSION
In this work, we reveal an interesting phenomenon that different unsupervised parsers learn dif- ferent expertise, and we propose novel ensemble approach by introducing new notion of "tree averaging" to leverage such heterogeneous expertise. Further, we distill the ensemble knowledge into a student model to improve inference efficiency; the proposed ensemble-then-distill approach also addresses the over-smoothing problem in multi-teacher distillation. Overall, our method shows consistent effectiveness with various teacher models and is robust in the domain-shift setting, largely bridging the gap between supervised and unsupervised constituency parsing. We will discuss future work in Appendix D

---

Published as a conference paper at ICLR 2024
REFERENCES
Alfred V. Aho and Stephen C. Johnson. LR parsing. CSUR, 6(2):99-124, 1974.
Peter Bickel and Kjell Doksum. Mathematical Statistics: Basic Ideas and Selected Topics. CRC Press, 2015.
Rens Bod. From exemplar to grammar: A probabilistic analogy-based model of language learning. Cognitive Science, 33(5)755--79,, 2009.
Taylor L. Booth. Probabilistic representation of formal languages. Scandinavian Workshop on Algorithm Theory, 1969.
Cristian Buciluä, Rich Caruana, and Alexandru Niculescu-Mizii. Model compression. In KDD, pp- 535-541, 2006.
Steven Cao, Nikita Kitaev, and Dan Klein. Unsupervised parsing via constituency tests. In EMNLP, pp. 4798 4808, 2020.
Eugene Charniak. A maximum-entere enttopy--erooooee -inspired parser. In NAACL, pp. 132-139, 2000.
Noam Chomsky. Syntactic Structures. The Hague: Mouton, 1967.
Alexander Clark. Unsupervised induction of stochastic context-free grammars using distributional clustering. In CoNLL, 2001.
Anup Anand Deshmukh, Qianqiu Zhang, Ming Li, Jimmy Lin, and Lili Mou. Unsupervised chunk- ing as syntactic structure induction with knowledge-trand transfer approach. In Findings of EMNLP, pp. 3626-3634, 2021.
Jacob Devlin, Ming-Wei Wei Chang, Kenton Lee, and Kristina Toutanova. BERT; Pre-training of deep bidirectional transformers for language understanding. In NAACL-HLT, pp. 4171-4186, 2019.
Andrew Drozdov, Patrick Verga, Mohit Yadav, Mohit Iyyer, and Andrew McCallum. Unsupervised latent tree induction with deep inside-outside recursive auto-encoders. In NAACL-HLT, pp. 1129- 1141, 2019.
Andrew Drozdov, Subendhu Rongali, Yi-Pei Chen, Tim O'Gorman, Mohit Iyyer, and Andrew Mc- Callum. Unsupervised parsing with S-DIORA: Single tree encoding for deep inside-outside re- cursive autoencoders. In EMNLP, pp. 4832 4845, 2020.
Chris Dyer, Adhiguna Kuncoro, Miguel Ballesteros, and Noah A. Smith. Recurrent neural network grammars. In NAACI-HI.T, pp. 199-209, 2016.
Markus Freitag, David Grangier, Qijun Tan, and Bowen Liang. High quality rather than high model probability: Minimum Bayes risk decoding with neural metrics. TACL, 10:811-825, 2022.
Matthew Gibson and Thomas Hain. Hypothesis spaces for minimum Bayes risk training in large vocabulary speech recognition. In INTERSPEECH, pp. 2406-2409, 2006.
Wenjuan Han, Yong Jiang, Hwee Tou Ng. and Kewei Tu. survey of unsupervised dependency parsing. In COLING, pp. 2522-2533, 2020.
Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge in neural network. arXiv preprint arXiv:1503.025: 2015.
Xiaoqi Jiao, Yichun Yin, Lifeng Shang, Xin Jiang, Xiao Chen, Linlin Li, Fang Wang, and Qun Liu. TinyBERT: Distilling BERT for natural language understanding. In Findings of EMNLP, pp- 4163 4174, 2020.
Katharina Kann, Anhad Mohananey, Samuel R. Bowman, and Kyunghyun Cho. Neural unsuper- vised parsing beyond English. In Proceedings Workshop Deep Learming for Low-Resource Natural Language Processing, pp. 209-218, 2019.
Tadao Kasami. An efficient recognition and syntax-annan analysis algorithm for context-free languages. Coordinated Science Laboratory Report, 1966.
10

---

Published as a conference paper at ICLR 2024
Yoon Kim, Chris Dyer, and Alexander Rush. Compound probabilistic context-free grammars for grammar induction. ACL, pp. 2369-2385, 2019a.
Yoon Kim, Alexander Rush, Lei Yu, Adhiguna Kuncoro, Chris Dyer, and Gábor Melis. Unsuper- vised recurrent neural network grammars. In NAACL-IILI, pp. 1105-1117, 2019b.
Dan Klein. The Unsupervised Learning of Natural Language Structure. Stanford University, 2005.
Dan Klein and Christopher D. Manning. A generative constituent-contex model for improved gram- mar induction. In ACI, pp. 128-135, 2002.
Shankar Kumar and William Byme. Minimum Bayes-risk decoding for statistical machine transla- tion. In HLT-NAACL, pp. 169-176, 2004.
Bowen Li, Lili Mou, and Frank Keller. An imitation learning approach to unsupervised parsing. In ACL, pp. 3485-3492, 2019.
Jiaxi Li and Wei Lu. Contextual distortion reveals constituency: Masked language models are implicit parsers. In ACL, pp. 5208-5222, 2023.
Glenn K. Manacher. An improved version of the Cocke- Bocke-Younggr-Kasamme algorithm. Computer
Languages, 3(2):127-133, 1978.
Mitchell P. Marcus, Beatrice Santorini. and Mary Ann Marcinkiewicz. Building large annotated corpus of English: The Penn Treebank. Computational Linguistics, 19(2):31-330, 1993.
Nickil Maveli and Shay Cohen. Co-training an unsupervised constituency parser with weak super- vision. In Findings of ACL, pp. 1274-1291, 2022.
James D. McCawley. The Syntactic Phenomena of English. University of Chicago Press, 1998.
Alireza Mohammadshahi and James Henderson. Syntax-aware graph-to-graph transformer for se- mantic role labelling. In RepLANLP, pp. 174-186, 2023.
Tahira Nascem, Harr Chen, Regina Barzilay, and Mark Johnson. Using universal linguistic knowl- edge to guide grammar induction. In EMNLP, pp. 1234-1244, 2010.
Joakim Nivre. Dependency parsing. Language and Linguistics Compass, 4(3):138-152) 2010.
Huan-Kai Peng. Pang Wu, Jiang Zhu, and Joy Ying Zhang. Helix: Unsupervised grammar induction for structured activity recognition. In JCDM, pp. 1194-1199, 2011.
Slav Petrov and Dan Klein. Improved inference for unlexicalized parsing. In HLT-NAACL, pp. 404 411, 2007.
Geoffrey Sampson. English for the computer: The SUSANNE corpus and analytic scheme. Com- putational Linguistics, 28(1):102-103, 2002.
Rico Sennrich. A CYK+ variant for SCFG decoding without dot chart. In Proceedings of the Workshop on Syntax, Semantics and Structure in Statistical Translation, pp. 94-102, 2014.
Behzad Shayegh, Yuqiao Wen, and Lili Mou. Ensemble- unsupervised discontinuous con- stituency parsing by tree averaging. arXiv preprint arXivv2403.00144, 2024.
Yikang Shen, Zhouhan Lin, Chin Huang, and Aaron Courville, Neural language modeling by jointly learning syntax and lexicon. In ICLR, 2018.
Yikang Shen, Shawn Tan, Alessandro Sordoni, and Aaron Courville. Ordered neurons: Integrating tree structures into recurrent neural networks. In ICLR, 2019.
Freda Shi, Daniel Fried, Marjan Ghazvininejad, Luke Zeullemoeer, and Sida I. Wang. Natural language to code translation with execution. In EMNLP, pp. 3533-3546, 2022.
Haoyue Shi, Jiayuan Mao, Kevin Gimpel, and Karen Livescu. Visually grounded neural syntax acquisition. In ACI., pp. 1842-1861, 2019.

---

Published as a conference paper at ICLR 2024
David A. Smith and Noah A. Smith. Probabilistic models of nonprojective dependency trees. In EMNLP-CONLL. pp. 132-140, 2007.
Benjamin Snyder, Tahira Naseem, and Regina Barzilay. Unsupervised multilingual grammar induc- tion. In ACL, pp. 73-81, 2009.
Siqi Sun, Yu Cheng. Zhe Gan, and Jingjing Liu. Patient knowledge distillation for BERT model compression. In EMNLP-IJCNLP, pp.
2019.
Mirac Suzgun, Luke Melas-Kyriaze and Dan Jurafsky. Follow the wisdom of the crowd: Effective text generation via minimum Bayes risk decoding. In Findings of ACL, pp. 4265-4293, 2023.
Ian Tenney, Dipanjan Das, and Ellie Pavlick. BERT rediscovers the classical NLP pipeline. In ACL,
pp. 4593-4601, 2019.
Ivan Titov and James Henderson. Loss minimization in parse reranking. In EMNLP, pp- 560-567, 2006.
Bolin Wei, Shuai Lu, Lili Mou, Hao Zhou, Pascal Poupart, Ge Li, and Zhi Jin. Why do neural dialog systems generate short and meaningless replies? comparison between dialog and translation. In ICASSP, pp. 7290-7294, 2019.
Yuqiao Wen, Yongchang Hao, Yanshuai Cao, and Lili Mou. An equal-size hard EM algorithm for diverse dialogue generation. In ICLR, 2023a.
Yuqiao Wen, Zichao Li, Wenyu Du, and Lili Mou. f-divergence minimization for sequence-level knowledge distillation. ACI. pp. 10817-10834, 2023b.
Yuqiao Wen, Behzad Shayegh, Chenyang Huang, Yanshuai Cao, and Lili Mou. Ebbs: ensemble with bi-level beam search for zero-shot machine translation. arXiv preprint arXiv:2403.00144, 2024.
Adina Williams, Andrew Drozdov, and Samuel R. Bowman. Do latent tree learning models identify meaningful structure in sentences? TACL, 6:253-267, 2018.
Chuhan Wu, Fangzhao Wu, and Yongfeng Huang. One teacher enough? Pre-trained language model distillation from multiple teachers. In Findings of ACL-IJCNLP, pp. 4408 44184,41,1100 2021.
Zijun Wu, Zi Xuan Zhang, Atharva Naik, Zhijian Mei, Mauajama Firdaus, and Lili Mou. Weakly supervised explainable phrasal reasoning with neural fuzzy logic. In ICLR, 2022.
Zijun Wu, Anup Anand Deshmukh, Yongkang Wu, Jimmy Lin, and Lili Mou. Unsupervised chunk- ing with hierarchical RNN. arXiv preprint arXiv:2309.04919, 2023.
Ze Yang, Linjun Shou, Ming Gong, Wutao Lin, and Daxin Jiang. Model compression with two-stage multi-teacher knowledge distillation for web question answering system. In WSDM, pp. 690-698, 2020.
Daniel H. Younger. Recognition and parsing of context-free languages time ne3 Information and Control, 10(2):189-200 200099000111100000 1967.
Yu Zhang, Houquan Zhou, and Zhenghua Li. Fast and accurate neural CRF constituency parsing. In IJCAI, pp. 4046-4053, 2021.
12

---

Published as a conference paper at ICLR 2024
A OUR CYK VARIANT
In this appendix, we provide a step-by-ster illustration our CYK-based ensemble algorithm in- troduced in Section [..
Consider four teachers predicting the trees in the first row of Figure The hit count of each span is shown in the second row. For example, the span (WIw2) w2) hits 3 times, namely, Teachers 1-3.
The initialization of the algorithm is to obtain the total hit count for single word, which is simply the same as the number of teachers because every word appears intact in every teacher's prediction. The initialization has five cells in row, and is omitted in the figure to fit the page width.
For recursion, first consider the constituents of two words, denoted by 1 2. A constituent's total hit count, denoted by Hb in Eqn. (5). inherits those its children, plus its own hit count. In 11, where 3 is the hit count of the span
the cell of ( 2,6 1, for example, H 1:3 4 + (w) w2), shown before.
For the step of recursion, we consider three-word constituents, i.e., 3. For example, the span wi t2g has two possible tree structures (W1 (wzwy)) and (Wwwy)))) The former leads to
Teacher
Teacher 2
Teacher
Teacher
Tree
022
103
1
11
W0g
W
W1
1/22
W3
W1
W3
11
Wgg
W33
Hit Hount
1
4
4
4
112
6
3
b
08
08
08
09
4
4
4
4
4
4
4
4
4
4
4
4
022
103
W0
W1
102
103
1/4
W0
10h
112
103
004
W6
W1
W/4
W0
16
16
16
08
09
08
4
4
4
4
11/2
W1
W/3
W1
W/3
W3
16
16
6
08
09
08
09
4
4
4
4
01
W12
U/3
W11
WE
W1
W2
W/3
W1s
16
09
4
4
W04
Figure 3: Step- illustration of our CYK algorithm, showing the dynamic changes in the H along with the construction of the corresponding optimal binary constituency tree.
13

---

Published as a conference paper at ICLR 2024
Algorithm Our CYK Variant
1: input: [
2: for b 1 to do
Base cases
3:
Ha:b+1 = K
4: Lb:b+1 (8b.b+1}
5:
end for
6:
for < 20
|s| do for b f- to 1+ do
>> Iterate over different lengths of constituents
7:
<> Iterate over different possible constituents of length /
8:
e b+b
9:
arg maxx(Hos + Hij HitCount (Ti(s))
bejse
The gray term need not be implemented is constant in j
10:
Haw - Husio + Hij + HitCount {T{(s)
J
11: Lbc Lucii U Liggi U {sbce}
12:
end for
13:
end for
14:
return /1:1s|+1
total hit count of 13, whereas the latter leads to 16. Therefore, ((w1w2)ws) chosen, with the best total hit count H1:4 16.
The process is repeated until we have the best parse tree of the whole sentence, which / 5 for the 5-word sentence in Figure
We provide the pseudocode for the process in Algorithm !
B SUPPLEMENTARY ANALYSES
INFERENCE EFFICIENCY
We propose to distill the ensemble knowledge into student model to increase the inference efficiency. We conducted
Inference Time (ms)
Model
GPU
GPU
analysis the inference time
Teachers
of different approaches, where we measured the time using 28 Intel(R) Core(TM) 19-9940X ( (33.30GHz) CPUs with or without GPU (Nvidia RTX Titan). rrepors the average time elapsed for performing inference on one sampld of the PTB test set, ignoring loading models, reading inputs, and writing outputs.
ON
35
130
Neural PCFG
610
630
Compound PCFG
560
590
DIORA
S-DIORA
110
140
ConTest
4,300
59,500
ContexDestort
1,890
11,110
Our ensemble
In the table, the total inference time of our ensem- ble model is the summation of all the teachers and the CYK algorithm. As expected, an ensemble ap- proach is slow because it has to perform inference for every teacher. However, our CYK-based ensem- ble algorithm is extremely efficient and its inference time is negligible compared with the teacher models.
CYK part
6
6
Total
7,541
72,136
Student
RNNG
410
410
Table Per-sample inference time (in mil- liseconds) on the PTB test.
The RNNG student model learns the knowledge from the cumbersome ensemble, and is able to perform inference efficiently with an 18x and 175x speedup with and without GPU, respectively. This shows the necessity of having knowledge distillation on top of the ensemble. Overall, RNNG achieves comparable performance to its ensemble teacher (Tables and 3) but drastically speeds up the inference, being useful model in practice.
The average time was computed on 100 samples of the PTB test set, due to the slow inference of certain teachers without GPU.
14

---

Published as a conference paper at ICLR 2024
OrderedNeurans
Average F; score on PTB test
NeuraiPCFG
CompoundPCFG
DIORA
S-DIORA
Con Test
ContexDistort
Ensemble
1-10
11-20
21-30
31-40
41-50
51-60
length words)
Figure 4: Performance by sentence lengths. Fi scores averaged over five different runs.
B.2 PERFORMANCE SENTENCE LENGTHS
Figure illustrates the parsing performance sentences of varying lengths. The result shows that existing unsupervised parsers have different levels of susceptibility to long sentences. For example, ContexDistort shows notable robustness the length, whereas the performance of Ordered Neu- rons drops significantly when the sentences are longer. Our ensemble method achieves both high performance and robustness across different lengths.
B.3 PERFORMANCE BY CONSTITUENCY LABELS
In this work, we see different unsupervised parsers learn different patterns (Table [ and their ex- pertise can be utilized by an ensemble approach (Section 3.4). From the linguistic point of view, we are curious about whether there is relation between such different expertise and the linguistic constituent labels (e.g., noun phrases and verb phrases).
With this motivation, we report in Figure 5 the breakdown performance by constituency labels, where the most common five labels-namely noun phrases, propositional phrases, verb phrases, simple declarative clauses, and subordinating conjunction clauses-are are considered, covering 95%
40
Ordered Neurons
Congoune PCFG
Ordered Neurons
Compound PC-G
Ordered Neurens
Compound PCFG
Ordered Neurons
PCFG
Ordered Neurons
Compound PCFG
20
Neural PCFG
ContoxOistor
ensemble
Neural PCFG
Contoxbistort
Our ensemble
ContexGistort
Our ensemble e
Neural PCFG PCFG
ContexBistort
Our ensembe
Neural PCFG PCFG
ContexDistort
ensemble
S-DIORA
Con Fest
DIORA
S-DIORA
Contest
DIORA
5-DIDRA
ConTest
DIORA
S.DIORA
last
DIORA
S DIORA
Contoct
NP
VP
SBAR
Figure 5: Performance by constituency labels on the PTB test set. Results are measured by re-
call, because the predicted parse trees are unlabeled; thus, precision and Fi scores cannot be com- puted (Drozdov et al., 2019). Bars and gray intervals are the mean and standard deviation, respec- tively, over five runs.
15

---

Published as a conference paper at ICLR 2024
Teachers:
A. Neural PCFG, DIORA, ContexDistort
Compound PCFG, S-DIORA, Ordered Neurons, ConTest
A Our ensemble
Groundiruth constituents
It
huge
's
huge
Figure 6: A case study, which shows that voting selects more commonly agreed structures.
Teachers:
Compound PCFG
DIORA
TConTest
At Agreed among all teachers
Some
dispet
tallovvr
Groundtruth constiluents
Our ensemble
Some
analyts
the
paymont
3n
offrt
355
dispel
taloover
speculation
Figure 7: A case study, where the ensemble outperforms all the teachers and achieves 100% recall over the groundtruth constituents.
of the cases in the PTB test set. Notice that the predicted constituency parse trees are still unla- beled (without tags like noun phrases), whereas the groundtruth constituency labels are used for collecting the statistics. Consequently, only recall scores can be calculated in per-label performance
analysis (Drozdov et al. 2019 Kim et al. 2019a Cao et al. 2020).
As seen, existing unsupervised parsers indeed exhibit variations in the performance of different constituency labels. For example, ConTest achieves high performance of prepositional phrases, whereas DIORA works well for clauses (including simple declarative clauses and subordinating conjunction clauses); for noun phrases, most models perform similarly. By contrast, our ensemble model achieves outstanding performance similar to higher than the best teacher in each category. This provides further evidence that our ensemble model utilizes different teachers' expertise.
C CASE STUDIES
In this section, we present case studies to show how the ensemble improves the performance. In particular, Figure illustrates Fillstatilsssratess teachers' performance, their ensemble output, and groundtruth for sentence "It's huge." This example represents how voting over local structures may result in correct structure detection. True constituents have a higher chance to appear in the majority of the teach- ers' outputs. This phenomenon extends to longer sentences and more complex structures. Figure presents an example where the ensemble outperforms all its teachers, hitting all the groundtruth con- stituents, which never happens in any teacher. Note that in this example, every constituent captured by the ensemble appears in at least two out of three teachers.
Figure illustrates more interesting behavior of the ensemble, where it recovers true constituent never seen in any teacher's output, drawn in dotted purple in the bottom figure. happens in complex structures when teachers agree on some local structures but do not agree the entire sentence. In that case, the ensemble eventually picks the agreed structures and fills the gaps with the remaining options.
D FUTURE WORK
Future work may be considered from both linguistic and machine learning perspectives. The pro- posed ensemble method largely bridges the gap between supervised and unsupervised parsing of the English language. future direction is to address unsupervised linguistic structure discovery in low- resource and multilingual settings (Shayegh et al., 2024). Regarding the machine learning aspect, our work demonstrates the importance of addressing the over-smoothing problem in multi-teacher distillation, and expect ensemble-then-distill approach be extended to different data
16

---

Published as a conference paper at ICLR 2024
Teachers:
A Neural PCFG
Ordered Neurons
A ContexDistort
n Agreed among all teachers
Futures traders
the
S&P
was
signaling
that the dow could fall
much
200
points
enserblee
Recovered groundtruth
Missed groundtruth
Discovered groundtruth
Futures traders
the
S&P
was signaling
that
dow
could
much
200
points
Figure 8: case study, where the ensemble recovers a true constituent never seen in any teacher's output.
types, such as sequences and graphs, with proper design of data-specific ensemble methods (Wen al. 2024
ACKNOWLEDGMENTS
We would like to thank all reviewers and chairs for their valuable and constructive comments. The research is supported in part by the Natural Sciences and Engineering Research Council Canada (NSERC), Mitacs Accelerate project, the Amii Fellow Program, the Canada CIFAR AI Chair Pro- gram, an Alberta Innovates Program, and the Digital Research Alliance of Canada (alliancecan.ca) We also thank Yongchang Hao for providing advice the algorithms.
17

---

Published as a conference paper at ICLR 2024
E INVENTORY OF TEACHER MODELS
Our experiments involve seven existing unsupervised parsers as teachers, each of which has five runs either based on authors' checkpoints by our replication using authors' codebases. We show the details in Table 6, where we also quote the mean Fj scores and, if available, max Fi scores reported in respective papers. Overall, we have achieved similar performance to previous work, which shows the success of our replication and establishes solid foundation for our ensemble research.
Source
Ordered Neurons
F1
47.7, Fj 49.4 reported in Shen al. 2019
Our replication using original codehase
seed 0017)
44.8
Our replication using the original codebase
seed 0031)
32.9
Parsed data available in Kim al. 2019a
50.0
Our replication using the original codcbasd
sccd
7214)
Our replication using the original codebase
1111)
45.9
mcan Fi
50.8, max Fi 52.6 reported in Kim 2019a]
Neural PCFG
Our replication using the original codebasa
sced 3435)
48.4
Parsed data available in the original codebasd
Our replication using the original codebase
seed 1234)
52.1
Our replication using the original codebase
seed 1313)
Our replication using the original codebase
seed
5555)
49.8
Compound PCFC
mean F1
50.8, max Fl 52.6 reported in Kim
2019a]
Parsed data available in the original codebasd
60.1
Our replication using the original codebase
F seed 3435)
53.9
Our replication using the original codebase
seed 1234)
55.4
Our replication using the original codebase
sced (887)
Our replication using the original codebase
sced 0778)
55.0
mean Fi
56.8 reported in Druzdov el al. 20119
DIORA
The mip-softmax checkpoint availahle on the original codehas
55.4
Our replication using the original codebase
10 ssed 0035)
59.4
Our replication using the original codebase
1 scod 0074)
60.3
Our replication using the original codebase
seed 1313)
60.5
Our replication using the original codebas seed 5555)
58.9
mean Fi
57.6, max F; 64.0 reported in Druzdov el 2020
S- S-DIORA
Our replication using the original codebase
11
seed 19435911771)
56.3
Our replication using the original codebasd
11 seed 0315)
60.0
Our replication using the original codebase
seed 0075)
58.5 .
Our replication using the original codebase seed 1313)
54.7
Our replication using the original codebase
seed 442597220)
54.9
mean Fi
62.8, max Fi 65.9 reported in cl al. 2020
TenTest
A checkpoint provided by authors through personal email
65.9
Our replication using original codebase Fid
Parsed data provided by authors through nersonal email
62.3
Our replication using the original codebasd id
63.0
Our replication using the original codebase id
61.8
49.0 reported Ln 22023
Distor
Our replication using original codebase c
10th layer "bert-buse-cam base-cased"
Our replication using original vodebase 14
12th layer wbber-buueeccar
Our replication using the original codcbase 11th layer "bert- basebbase-d"""
Our replication using the original codebase 8th layer of "bert-base-cn basc-cased"
46.9
Our replication using the original codebase 9th layer bert-buse-cased"
48.1
Table 6: Fi scores are on PTB test for different teachers in different runs. Note that the runs were randomly shuffled for the randomized experiment.
httpptt//ittuub.coo//ss//////
Given a pretrained language model, Contex is deterministic
detemmitntt algorithm. Therefore, we used differ-
ent layers of the language model as runs to obtain different results.
18


Reviews:
[{"review_id": "3OYlDg4HCP", "reviewer": "Reviewer_yYrJ", "summary": "This work proposes a method for combining the outputs from unsupervised parsers in the manner similar to MBR decoding, but different in considering all possible trees. The proposed method simply assigns score to every span, a hit count that is the number of constituency appearing in outputs from multiple unsupervised parser. Then, it runs CKY to derive the maximum scored tree using the hit count score. Experiments on PTB and SUSANNE presents gains over SOTA baselines.", "questions": "- I'd like to know the impact of length of inputs, e.g., whether the proposed method is better in lengthy input or not.", "limitations": "", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The proposed method is very simple to combine multiple outputs from unsupervised parsing, and the method might have an impact to other system combination method, e.g., NER with CRF. The ensemble by hit-count is sound and the merit is proved effective in the experiments especially when comparing MBR which can consider only spans in the multiple system outputs.\n\n- Experiments are well designed and the effect of the proposed method is proved empirically. This work also presents knowledge distillation using RNNG and URNNG so that it might have a potential for a practical application. Analysis is also convincing by comparing multiple diverse systems.", "weaknesses": "- It is comparing only for English, and it would be better to compare the model with other languages, e.g., Chinese, for further strengthening this submission.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7O8N18WngL", "reviewer": "Reviewer_QZms", "summary": "This paper proposes a novel strategy following an ensemble-then-distill paradigm to deal with the unsupervised constituency parsing task that aims to hierarchically structure sentences without relying on linguistically annotated data. The proposed approach firstly ensembles existing unsupervised parsers based on the notion of “tree averaging” and then conducts distillation to create a student model. This technique efficiently alleviates the over-smoothing issue that frequently arises in multi-teacher distillation. Experimental results indicate that such an ensemble-then-distill method outperforms existing approaches with superior effectiveness and robustness.", "questions": "Despite these merits, there are some points which need further clarification, and some suggestions.\n\n1.      The ensemble method demonstrates its effectiveness on PTB. However, in 2020, the F1 score of CRF parser on PTB variants had already been above 90 (Zhang et al., 2020). There is indeed a performance boost in comparison to oracle score (the highest possible F1 score of binarize groundtruth trees). But it is not appropriate to claim that “largly bridging the gap between supervised and unsupervised constituency parsing” on Page 6.\n\n2.      In Results on SUSANNE, the authors claim that “This is a realistic experiment to examine the models’ performance in an unseen low-resource domain.” However, SUSANNE is an English dataset. In CoNLL Shared task, there are tree-banks on low-resource languages (Zeman et al., 2017). It’s better that the authors can demonstrate the effectiveness of the approach on some of these low-resource language datasets.\n\nReferences:\n\nZeman, D., Popel, M., Straka, M., Hajic, J., Nivre, J., Ginter, F., Luotolahti, J., Pyysalo, S., Petrov, S., Potthast, M., Tyers, F., Badmaeva, E., Gokirmak, M., Nedoluzhko, A., Cinkova, S., Hajic Jr., J., Hlavacova, J., Kettnerová, V., Uresova, Z., … Li, J. (2017). CoNLL 2017 Shared Task: Multilingual Parsing from Raw Text to Universal Dependencies. Proceedings of the CoNLL 2017 Shared Task: Multilingual Parsing from           Raw Text to Universal Dependencies, 1–19. https://doi.org/10.18653/v1/K17-3001\n\nZhang, Y., Zhou, H., & Li, Z. (2020). Fast and Accurate Neural CRF Constituency Parsing. Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, 4046–4053. https://doi.org/10.24963/ijcai.2020/560\n\n3.      In Table 3 on Page 7, PTB-supervised model is used for comparison. Which PTB-supervised model is used?", "limitations": "", "rating": 3, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The major contributions include:\n\n1.      A new notion of tree averaging and the corresponding search algorithm: CYK variant\n\n2.      Ensemble-then-distill approach that trains a student parser from an ensemble of teachers.\n\n3.      The inference time of the student model is 18x faster than the ensemble method.\n\n4.      A hypothesis that different unsupervised parsers capture different aspects of the language structures and the verification with experiments.", "weaknesses": "1. Lack of clarification regarding the methodology design.\n\n- The averaging tree is derived with the highest total F1 score compared with different teachers. Have the authors tried other methods of calculating the similarities between trees? Perhaps a fair comparison is needed to further indicate the effectiveness of the proposed tree averaging method.\n- The authors did not provide a detailed explanation for choosing the seven unsupervised parsers introduced in Section 3.2 as teacher models. For instance, why did the authors select ContextDistort as one of the teachers despite its relatively inferior performance and inference efficiency?\n\n2. The authors state in Introduction that combining the different parsers may leverage their different expertise. The authors attempt to verify this statement in Section 3.4 by comparing two settings: the ensemble of three runs of the same model and that of three heterogeneous models. I wonder if it is more appropriate to choose the model with highest performance in the former setting so that it can be further validated there exists additional boost due to different expertise (e.g., Neural PCFG for Group 2).\n3. The writing can be improved. There are some typos and unclear descriptions. Please refer to comments for detail.\n\n\nComments\n\n1. Minor comments on writing:\n(1)\tParagraph #1 in Introduction: ...to explore unsupervised methods as it eliminates... -> ...to explore unsupervised methods as they eliminate...\n(2)\tParagraph #1 in Section 3.1: ... on the widely used the Penn Treebank -> ... on the widely-used Penn Treebank", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QWoDiESOd1", "reviewer": "Reviewer_ZbQV", "summary": "This paper proposes an ensembling approach for the task of unsupervised constituency parsing. Having trained a group of various prior models, they use a dynamic program to find the “average tree” of their predictions. While this approach works well, it can then be further used for distillation into an RNNG which works more efficiently and in some settings more accurately. They also analyze to what extent the improvements in performance from ensembling are down to smoothing vs. combining expertise.", "questions": "- How does regular RNNG perform, and why not use it as a teacher?\n- Regarding the experiment in Figure 1, do you see similar results if you measure the gains from the *distilled* ensemble? That would be useful to see alongside", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The insight that different models are weakly correlated despite similar F1 is interesting and well motivates the approach\n- The proposed dynamic program is intuitive and well explained\n- Experiments are strong and thorough\n- The analysis of gains from denoising vs. difference in expertise is well conducted", "weaknesses": "- The fact that the F1 gains from distillation do not carry over to the out of domain setting is a drawback and somewhat underexplored\n- There is a lack of qualitative analysis of the types of behaviors that different model types exhibit, and how ensembling actually combines those. Some of this is done in the Appendix but it would be nice to see specific examples in the main paper, especially since that analysis is wrt constituency labels which the model isn’t actually being evaluated on.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1cn0NA9fev", "reviewer": "Reviewer_mYw3", "summary": "This paper proposes a consistency-based decoding method for unsupervised constituency parsing, which can also be formulated as minimum Bayes risk decoding.\nExperiments demonstrate significant improvement over existing methods.", "questions": "- Which split of PTB did you use to generate the statistics in Table 1?\n- Table 2: why are the +RNNG/+URNNG oracle performance different from the basic one (83.3)?", "limitations": "", "rating": 8, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- Significant contribution to unsupervised constituency parsing, including a generative MBR process and consistently improved results.\n\n- Comprehensive analyses are carefully conducted and presented.\n\n- The paper is very well written and easy to follow.\n\nI also wanted to note the statements and conclusions in this paper are remarkably honest. \nMost of the claims are very well supported by related work and experimental results. \nWhile this is generally not considered as a strength, such a presentation style should be commended and encouraged in recent years.", "weaknesses": "- MBR-style or consistency-based methods have also been applied to parsing for decoding or model selection, but the authors failed to recognize and discuss them. To name a few, [Smith and Smith, 2007](https://aclanthology.org/D07-1014.pdf) and [Zhang et al., 2020](https://aclanthology.org/2020.acl-main.302.pdf) used MBR-decoding to improve dependency parsing; [Shi et al., 2019](https://aclanthology.org/P19-1180.pdf) adapted an agreement-based model selection process for distantly supervised constituency parsing.\n\n- The motivation is not completely convincing. Recent trends in NLP demonstrate that explicit parses might not be crucial or even necessary to many user-facing applications (e.g., GPT models do not really use explicit language structures), which contradicts the first sentence in this paper (*Constituency parsing is a core task in natural language processing*). Traditionally, such structures served as a backbone for many NLP models, and the prediction of them was therefore referred to as *core NLP*. I am not sure if the parsing is as important as what I receive from this paper. Please consider revising or including more justification. \n\n\n**Minor points on weaknesses**\n\n- The references in this paper, especially to conventional linguistic literature, need some work:\n    - Section 1: Carnie (2007) and Fromkin et al. (2003) are introductory books. Both should be changed to Chomsky (1957). Syntactic Structures.\n    - [Spitkovsky et al. (2013)](https://aclanthology.org/D13-1204.pdf) is worth a mention in the related work section.\n\n- Page 1: low correlation among different unsupervised parsers: [Williams et al. (2018)](https://direct.mit.edu/tacl/article/doi/10.1162/tacl_a_00019/43445/Do-latent-tree-learning-models-identify-meaningful) discovered a similar issue within the same model architectures (Table 1, right settings).\nThis is worth a discussion.\n\n- Not really a weakness for a machine learning conference submission: since the topic of this paper is highly linguistic, I am willing to see a detailed analysis of what patterns are fixed. For example, do NPs/PPs with rare words receive more fixes than those with frequent words, or the opposite, or not significant? Do VPs with transitive verb heads receive more fixes than those with intransitive verb heads, or the opposite, or insignificant? Does the student extract any constituent that does not receive any vote from teacher models, due to fixes on shorter spans and CYK?\n\nI am being conservative in my initial evaluation and am happy to increase my rating if most of the above issues are fixed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DqVUerbaeF", "reviewer": "Reviewer_BQVw", "summary": "The paper considers ensembling unsupervised (unlabled binary) constituency parsers. The main technical piece is an MBR decoding algorithm that finds the highest-F1 tree with respect to a set of candidate trees. Experiments show that this ensembling method is more effective than simply selecting a max-intra-F1 candidate tree or training a student model on the union of candidate trees (union distillation).", "questions": "Would \"Our ensemble (X teacher across runs)\" in Table 2 use candidate trees from different models, or do they all end up from the same model (e.g., ConTest for X=\"best\")? It's good to know the answer to this question because one of the main claims of the paper is that it's important to exploit the large qualitative differences between different methods (Table 1). The fact that we get the best result by just using outputs from the same model seems to refute that claim (i.e., it's all variance reduction).", "limitations": "", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- Simple but insightful observation that it is possible to \"generate\" a tree from candidate trees\n- Derivation of the hit-count maximization algorithm \n- Strong results", "weaknesses": "- Somewhat narrow scope (ensembling constituency trees)\n- Some details missing (see the questions)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)