# Ensemble-Based Unsupervised Discontinuous Constituency Parsing by Tree
Averaging

Behzad Shayegh1 Yuqiao Wen1 Lili Mou1,2
1Dept. Computing Science, Alberta Machine Intelligence Institute (Amii),
University of Alberta
2Canada CIFAR AI Chair
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

We address unsupervised discontinuous constituency parsing, where we observe a
high variance in the performance of the only previous model. We propose to
build an ensemble of different runs of the existing discontinuous parser by
averaging the predicted trees, to stabilize and boost performance. To begin
with, we provide comprehensive computational complexity analysis (in terms of
P and NP-complete) for tree averaging under different setups of binarity and
continuity. We then develop an efficient exact algorithm to tackle the task,
which runs in a reasonable time for all samples in our experiments. Results on
three datasets show our method outperforms all baselines in all metrics; we
also provide in-depth analyses of our approach.

##  1 Introduction

Unsupervised parsing has been attracting the interest of researchers over
decades (Klein and Manning, 2002; Klein, 2005; Snyder et al., 2009; Shen et
al., 2019; Cao et al., 2020). Compared with supervised methods, unsupervised
parsing has its own importance: (1) It reduces the reliance on linguistically
annotated data, and is beneficial for low-resource languages and domains (Kann
et al., 2019). (2) Discovering language structures in an unsupervised way
helps to verify theories in linguistics (Goldsmith, 2001) and cognitive
science (Bod, 2009). (3) Unsupervised parsing methods are applicable to other
types of streaming data, such as motion-sensor signals (Peng et al., 2011).

The constituency tree, a hierarchy of words and phrases shown in Figure 1, is
an important parse structure (Carnie, 2007). Researchers have proposed various
approaches to address unsupervised constituency parsing, such as latent-
variable methods (Clark, 2001; Petrov and Klein, 2007; Kim et al., 2019a) and
rule-based systems (Cao et al., 2020; Li and Lu, 2023). Shayegh et al. (2023)
reveal that different unsupervised parsers have low correlations with each
other. They further propose an ensemble approach based on dynamic programming
to boost performance.

(a) |  |  |  ✧ |  |  |  |  |  |  |  |  |  ✧ |  |  | (b) |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
|  ✧ |  |  |  ✧ $\rightarrow$ non-binary |  fan-out 2 $\leftarrow$ ✧ |  |  |  ✧ |  ✧ |  |
✧ |  |  ✧ |  |  ✧ |  |  ✧ |  |  |  ✧ |  |  ✧ |  |  ✧ |  |  ✧ |
Buy |  |  the |  |  pretty |  |  book |  |  |  Wake |  |  your |  |  friend |  |  up |

(c) |  |  |  |  ✧ $\rightarrow$ non-binary fan-out 1 |
---|---|---|---|---|---
binary fan-out 3 $\leftarrow$ ✧ |  |  |
fan-out 3 $\leftarrow$ ✧ |  |  |  |
|  |  |  ✧ $\rightarrow$ fan-out 1 |  |
& ✧ |  ✧ |  ✧ |  ✧ |  ✧ |  ✧ |
Damit |  sollen |  den |  Kassen |  Beitragserhöhungen |  erschwert |  werden

Figure 1: (a) A continuous parse structure in English. (b) An arguably
discontinuous parse structure in English. (c) A discontinuous parse structure
in German. Interesting structures (binarity and fan-out) are illustrated.

One limitation of most existing studies is that they only address continuous
constituency parsing, that is, a constituent can only be a continuous span of
words (Figure 1a). However, a constituent may be discontinuous (McCawley,
1982).111In the literature, a continuous parse structure is also known to be
projective, and a discontinuous parse structure is non-projective (Versley,
2014). In Figure 1b, for example, it is linguistically arguable that wake and
up form a constituent in the sentence “Wake your friend up.” Such
discontinuous constituents are more common in certain languages (such as
German shown in Figure 1c) than in English (Skut et al., 1997), but they have
been less tackled in the literature. Very recently, Yang et al. (2023)
proposed an unsupervised parsing method based on a mildly context-sensitive
grammar (Joshi, 1985) that allows discontinuous parse structures, known as
discontinuous trees (Tomita, 1990). As an early attempt, their performance
appears to be low, and we find that their approach is noisy and exhibits low
correlation in different runs with random seeds.

In this work, we propose an ensemble method to discontinuous constituency
parsing by tree averaging, inspired by Shayegh et al. (2023), who address the
ensemble of continuous constituency parsing by CYK-like dynamic programming
(Younger, 1967). However, the previous approach is not directly applicable to
our scenario because of the discontinuous structures in our setup.
Consequently, the seemingly small change in the setting (continuous vs.
discontinuous) leads to a completely different landscape of problems,
requiring advanced algorithmic analysis and development.

Specifically, we first analyze the computational complexity of tree averaging
under different setups, such as binarity and continuity. We show certain
problems are in the P category, whereas general tree averaging is NP-complete.
Then, we develop an algorithm utilizing the meet-in-the-middle technique
(Horowitz and Sahni, 1974) with effective pruning strategies, making our
search practical despite its exponential time complexity.

Our experiments on German and Dutch show that our approach largely outperforms
previous work in terms of continuous, discontinuous, and overall $F_{1}$
scores. To the best of our knowledge, our algorithm is the first that can
handle non-binary constituents in the setting of unsupervised constituency
parsing.

##  2 Approach

###  2.1 Unsupervised Discontinuous Constituency Parsing

In linguistics, a constituent is one or more words that act as a semantic unit
in a hierarchical tree structure (Carnie, 2007). Discontinuous constituents
are intriguing, where a constituent is split into two or more components by
other words (Figure 1; McCawley, 1982; Tomita, 1990).

Unsupervised discontinuous constituency parsing aims to induce—without using
linguistically annotated data for training—a parse structure that may contain
discontinuous constituents. As mentioned in §1, unsupervised parsing is an
important research topic, as it potentially helps low-resource languages, the
development of linguistic and cognitive theory, as well as the processing of
non-textual streaming data.

Yang et al. (2023) propose the only known unsupervised discontinuous parsing
approach, based on linear context-free rewriting systems (LCFRS; Vijay-Shanker
et al., 1987), a type of mildly context-sensitive grammars (Joshi, 1985),
which can model certain discontinuous constituents. They focus on binary LCFRS
and limit the fan-out of their grammar to be at most $2$, known as LCFRS-2
(Stanojević and Steedman, 2020), meaning that each constituent can contain up
to two nonadjacent components222A component refers to a span of one or more
consecutive words in a sentence. (illustrated in Figure 1). Maier et al.
(2012) observe such structures cover most cases in common treebanks.
Essentially, the LCFRS-2 grammar used in Yang et al. (2023) is a 6-tuple
$\mathcal{G}=(S,\mathcal{N}_{1},\mathcal{N}_{2},\mathcal{P},\Sigma,\mathcal{R})$,
where $S$ is the start symbol, $\mathcal{N}_{1}$ a finite set of non-terminal
symbols with fan-out being $1$, $\mathcal{N}_{2}$ fan-out being $2$,
$\mathcal{P}$ preterminals, and $\Sigma$ terminals. $\mathcal{R}$ is a finite
set of rules, following one of the forms:

$\displaystyle R_{1}:S(x)\rightarrow A(x)$ $\displaystyle A\in\mathcal{N}_{1}$
$\displaystyle R_{2}:A(xy)\rightarrow U(x)U^{\prime}(y)$ $\displaystyle
A\in\mathcal{N}_{1}$ $\displaystyle R_{3}:A(xyz)\rightarrow U(y)B(x,z)$
$\displaystyle A\in\mathcal{N}_{1}$ $\displaystyle R_{4}:A(x,y)\rightarrow
U(x)U^{\prime}(y)$ $\displaystyle A\in\mathcal{N}_{2}$ $\displaystyle
R_{5}:A(xy,z)\rightarrow U(x)B(y,z)$ $\displaystyle A\in\mathcal{N}_{2}$
$\displaystyle R_{6}:A(xy,z)\rightarrow U(y)B(x,z)$ $\displaystyle
A\in\mathcal{N}_{2}$ $\displaystyle R_{7}:A(x,yz)\rightarrow U(y)B(x,z)$
$\displaystyle A\in\mathcal{N}_{2}$ $\displaystyle R_{8}:A(x,yz)\rightarrow
U(z)B(x,y)$ $\displaystyle A\in\mathcal{N}_{2}$ $\displaystyle
R_{9}:T(w)\rightarrow w$ $\displaystyle T\in\mathcal{P},w\in\Sigma$

for $B\in\mathcal{N}_{2}$, and
$U,U^{\prime}\in\mathcal{N}_{1}\cup\mathcal{P}$. Note that $x$ in a rewriting
rule $A(x)$ is not an input string. Instead, it is a placeholder suggesting
that $A(x)$ has a fan-out $1$. Likewise, $A(x,y)$ has a fan-out $2$, with $x$
and $y$ being the two nonadjacent components.

Such a grammar may handle certain types of discontinuous constituents. Take
$R_{3}$ as an example. The left-hand side $A(xyz)$ implies the placeholder
string $xyz$ is a constituent that can be split into three adjacent
components: $x$, $y$, and $z$ in order. The notation $B(x,z)$ in the rule
asserts that $x$ and $z$ form a constituent, although they are not adjacent in
the original string $xyz$.

We follow Yang et al. (2023) and train a probabilistic LCFRS-2, parametrized
by a tensor decomposition-based neural network (TN-LCFRS). The objective is to
maximize the likelihood of sentence reconstruction by marginalizing the
grammar rules. Compared with general context-sensitive grammar, LCFRS-2
balances the modeling capacity and polynomial-time inference efficiency; thus,
it is also used in supervised discontinuous parsing (Maier, 2010; Cranenburgh
et al., 2016). We refer interested readers to Yang et al. (2023) for the
details of TN-LCFRS training and inference.

Figure 2: $F_{1}$ scores on continuous and discontinuous constituents in the
NEGRA test set (Skut et al., 1997), where each point is a random run of TN-
LCFRS (Yang et al., 2023).

In our work, we observe that TN-LCFRS exhibits high variance in performance,
especially for discontinuous constituents (Figure 2). In addition, there is a
negative correlation between continuous and discontinuous performance among
different runs: some are better at continuous constituents, while others are
better at discontinuous ones.

Recently, Shayegh et al. (2023) show that an ensemble model can utilize
different expertise of existing continuous parsers and smooth out their noise.
A natural question in our scenario is: Can we build an ensemble of
discontinuous parsers?

In the rest of this section, we perform in-depth theoretical analysis of the
problem, and show that with seemingly harmless alteration of setups, the
problem may belong to either P or NP-complete complexity categories. We
further develop a meet-in-the-middle search algorithm with efficient pruning
to solve our problem efficiently in practice.

###  2.2 Averaging over Constituency Trees

We adopt the tree-averaging notion in Shayegh et al. (2023), which suggests
the ensemble output should be the tree with the highest average $F_{1}$-score
against the ensemble components (referred to as individuals):

$\displaystyle
T^{*}=\operatorname*{argmax}_{T\in\mathcal{T}}\sum_{k=1}^{K}F_{1}(T,T_{k})$
(1)

where $\mathcal{T}$ is search space given an input sentence, and $T_{k}$ is
the parse tree predicted by the $k$th individual. The $F_{1}$ score is
commonly used for evaluating constituency parsers, and is also our ensemble
objective, given by
$F_{1}(T_{\text{prd}},T_{\text{ref}})=\frac{2|C(T_{\text{prd}})\cap
C(T_{\text{ref}})|}{|C(T_{\text{prd}})|+|C(T_{\text{ref}})|}$, where
$T_{\text{prd}}$ and $T_{\text{ref}}$ denote the predicted and reference
trees, respectively, while $C(T)$ represents the set of constituents in a tree
$T$.

It is noted that existing unsupervised parsers can only produce binary trees
in both continuous and discontinuous settings (Shen et al., 2018a; Kim et al.,
2019a; Yang et al., 2023). The binary property asserts that, given a
length-$n$ sentence, $|C(T_{k})|=2n-1$ for every individual $k$, thus
simplifying Eqn. (1) to

$\displaystyle T^{*}=\operatorname*{argmax}_{T\in\mathcal{T}}\frac{\sum_{c\in
C(T)}{\mathpzc h}(c)}{|C(T)|+2n-1}$ (2)

Here, ${\mathpzc h}(c)$ counts the occurrences of a constituent $c$ in the
trees predicted by the individuals. We call ${\mathpzc h(c)}$ the hit count of
$c$.

We point out that the output of our approach does not have to be a binary
tree, and we will empirically analyze the output binarity in §3.2.

We would like to examine the computational complexity for tree averaging, such
as P and NP categories. To begin with, we consider the decision problem (i.e.,
whether there exists a tree satisfying some conditions) corresponding to the
search problem (i.e., finding the best tree), which is standard in complexity
analysis (Arora and Barak, 2009).

######  Problem 1 (Averaging binary trees with bounded fan-out).

Consider a number $z$ and constituency trees $T_{1},\cdots,$ $T_{K}$ with the
same leave nodes, where the trees are binary and have a fan-out of at most
$F$. Is there a constituency tree $T$ such that
$\sum_{k=1}^{K}F_{1}(T,T_{k})\geq z$?

######  Theorem 1.

Problem 1 belongs to P.

###### Proof sketch.

Shayegh et al. (2023) present a polynomial-time dynamic programming (DP)
algorithm to average continuous binary trees, where the outputs are restricted
to binary trees as well; here, continuous trees can be seen as having max fan-
out $1$. For non-binary outputs, the DP table can be augmented by an
additional axis whose size is bounded by the sentence length $n$. To handle
discontinuity, we may augment the DP table with additional axes based on the
maximum fan-out $F$. Overall, the time complexity of the DP algorithm is
$\mathcal{O}(n^{4F+1})$; thus, Problem 1 is in P. See Appendix A.1 for the
detailed proof. ∎

A curious question then is whether we have polynomial-time algorithms if
dropping the assumptions of input being binary and having bounded fan-out.
Having non-binary inputs is intriguing since the above DP relies on Eqn. (2),
which only holds for binary inputs.

######  Problem 2 (Averaging trees with bounded fan-out).

Consider a number $z$ and constituency trees $T_{1},\cdots,$ $T_{K}$ with the
same leave nodes, where the fan-out is at most $F$ but the trees may be non-
binary. Is there a constituency tree $T$ such that
$\sum_{k=1}^{K}F_{1}(T,T_{k})\geq z$?

######  Theorem 2.

Problem 2 belongs to P.

###### Proof sketch.

If we fix the number of nodes $\tau$ of the output tree, the above DP can be
reused to solve this problem. We may enumerate all possible values of $\tau$,
which must satisfy $n<\tau<2n$. Thus, Problem 2 can be solved in
$\mathcal{O}(n^{4F+2})$ time and belongs to P. See Appendix A.2 for the proof.
∎

However, if the fan-out is unbounded, the difficulty is that the above DP
table grows exponentially with respect to $F$. Since the problem is
polynomial-time verifiable, it surely belongs to NP, but whether it belongs to
P, NP-complete, or both remains unknown for binary inputs.

######  Open Problem 1 (Averaging binary trees).

What is the exact complexity category of averaging binary trees with unbounded
fan-out?

For averaging general trees (non-binary inputs with unbounded fan-out), we can
show that it belongs to NP-complete.

######  Problem 3 (Averaging trees).

Consider a number $z$ and constituency trees $T_{1},\cdots,$ $T_{K}$ with the
same leave nodes, where the fan-out is unbounded and the trees may be non-
binary. Is there a constituency tree $T$ such that
$\sum_{k=1}^{K}F_{1}(T,T_{k})\geq z$?

######  Theorem 3.

Problem 3 belongs to NP-complete.

###### Proof sketch.

It is easy to show that, given a certificate, Problem 3 is polynomial-time
verifiable. For the completeness, we reduce the max clique problem, a known
NP-complete problem, to Problem 3. See Appendix A.3 for the detailed proof. ∎

Binary [-3pt]individuals? Bounded [-3pt] fan-out? [-11pt] | Bounded | Unbounded
---|---|---
Binary | P | Unknown
Non-binary | P |  NP-complete

Table 1: Summary of the complexity categories of tree-averaging problems.

The above theoretical analysis provides a deep understanding of building tree
ensembles, summarized in Table 1. In our experiments, the task falls into
Problem 1 because the only existing unsupervised discontinuous parser (Yang et
al., 2023) produces binary trees with fan-out at most $2$. The problem belongs
to P.

That being said, a practical approach should consider not only algorithmic
complexity, but also the specific properties of the task at hand. A DP
algorithm that one may develop for our task has a complexity of
$\mathcal{O}(n^{9})$, as discussed in the proof of Theorem 1, which appears
impractical despite its polynomial time complexity.

In the rest of this section, we develop a more general search algorithm that
works at the level of Open Problem 1 but also solves Problem 1 more
efficiently than high-order polynomial DP.

###  2.3 Our Search Algorithm

Our work concerns building an ensemble of binary, bounded-fan-out,
discontinuous trees generated by the unsupervised parser in Yang et al.
(2023).

We will develop a general search algorithm (regardless of fan-out) with strong
pruning that only needs to consider a few candidate constituents, bringing
down the $\mathcal{O}(2^{2^{n}})$ complexity of exhaustive search333For a
length-$n$ sentence, there are $2^{n}-1$ possible constituents because an
arbitrary non-empty set of words can be a constituent. To build a constituency
tree, the exhaustive search needs to look into any combination of
constituents. to $\mathcal{O}(2^{n})$. We will further halve the exponent
using a meet-in-the-middle technique, resulting in an overall complexity of
$\mathcal{O}(2^{\frac{n}{2}}n^{2})$. As a result, our algorithm remains exact
search while being efficient for all samples in the dataset; when a sentence
is short, our algorithm is even much faster than the DP with
$\mathcal{O}(n^{9})$ complexity.

To solve the tree-averaging problem, we first convert it into an equivalent
graph problem for clarity. Specifically, we construct an undirected graph $G$
with vertices being all possible constituents (although they can be largely
pruned), weighted by corresponding hit counts, as defined after Eqn. (2). We
put an edge between two vertices if and only if their corresponding
constituents can coexist within a constituency tree, that is to say, they are
either disjoint or inclusive of one another. Then, we formulate the below
graph-search problem, which can solve the original tree-search problem for
ensemble discontinuous parsing.

######  Problem 4 (Normalized Max Weighted Clique).

Consider a weighted undirected graph $G=\langle V,E\rangle$ and an objective
function $f(Q;\alpha_{1},\alpha_{2})=\frac{\sum_{v\in
Q}w(v)+\alpha_{1}}{|Q|+\alpha_{2}}$, where
$\alpha_{1},\alpha_{2}\in\mathbb{R}$, $Q\subseteq V$, and $w(v)$ is the weight
of $v$. What is the clique $Q$ that maximizes $f(Q;\alpha_{1},\alpha_{2})$?

######  Lemma 1.

Given $G$ as described above, the clique $Q^{*}$ maximizing
$f(Q;\alpha_{1},\alpha_{2})$ corresponds to a constituency tree, if
$\alpha_{1}\leq K\alpha_{2}$ where $K$ is the number of individuals.

######  Theorem 4.

The average constituency tree $T^{*}$ in Eqn. (2) is polynomial-time reducible
from $Q^{*}$ in Problem 4 with $\alpha_{1}=0$ and $\alpha_{2}=2n-1$, if $G$ is
built as above.

###### Proof.

Suppose the constituents corresponding to a clique $Q$ in the graph $G$ form a
constituency tree, denoted by $T_{Q}$. We have $\sum_{v\in Q}w(v)=\sum_{c\in
T_{Q}}{\mathpzc h}(c)$ by the construction of $G$. Thus, the objective
function of Problem 4 is

$\displaystyle f(Q;0,2n-1)$ $\displaystyle=\frac{\sum_{v\in
Q}w(v)+0}{|Q|+2n-1}$ (3) $\displaystyle=\frac{\sum_{c\in C(T_{Q})}{\mathpzc
h}(c)}{|C(T_{Q})|+2n-1}$ (4)

which is the same as the $\operatorname{argmax}$ objective in Eqn. (2). It is
easy to see that each constituency tree corresponds to a clique in $G$.
Therefore, the corresponding constituency tree to $Q^{*}$, guaranteed by Lemma
1, maximizes Eqn. (2). In other words, we have $T^{*}=T_{Q^{*}}$. ∎

Problem 4 generalizes a standard max clique problem (Arora and Barak, 2009),
which may be solved in $\mathcal{O}(2^{|V|})$ time complexity by exhaustive
search. The meet-in-the-middle technique (Horowitz and Sahni, 1974) can be
used to address the max clique problem, reducing the complexity from
$\mathcal{O}(2^{|V|})$ to $\mathcal{O}(2^{\frac{|V|}{2}}|V|^{2})$. In Appendix
B, we develop a variant of the meet-in-the-middle algorithm to solve Problem
4.

###  2.4 Candidate Constituents Pruning

The efficiency of our algorithm for Problem 4 depends on the number of
vertices in the graph. In our construction, the vertices in $G$ correspond to
possible constituents, which we call candidates.

A naïve approach may consider all $\mathcal{O}(2^{n})$ possible constituents,
which are non-empty combinations of words in a length-$n$ sentence. Thus, our
meet-in-the-middle algorithm has an overall complexity of
$\mathcal{O}(2^{2^{n-1}+2n})$ for tree averaging.

In this part, we theoretically derive lower and upper bounds for a candidate’s
hit count. If a constituent has a lower hit count than the lower bound, it is
guaranteed not to appear in the average tree. On the other hand, a constituent
must appear in the average tree, if it has a higher hit count than the upper
bound. We may exclude both cases from our search process, and directly add the
must-appear candidates to the solution in a post hoc fashion.

Let $P$ be a set of constituents that are known to be in the average tree
$T^{*}$. Here, $P$ may even be an empty set. We may derive a hit-count lower
bound for other constituents (not in $P$), as stated in the following theorem.

######  Theorem 5 (Lower bound).

For every constituent $c\in C(T^{*})\backslash P$, where $P\subseteq
C(T^{*})$, we have

$\displaystyle{\mathpzc h}(c)>\min_{|P|\leq j\leq
2n-2}\frac{\sum_{i=1}^{j-|P|}\lambda^{+}_{i}\;+\;\sum_{c^{\prime}\in
P}{\mathpzc h}(c^{\prime})}{j+2n-1}$ (5)

where $\lambda^{+}_{i}$ is the $i$th smallest positive hit count.

The theorem suggests that constituents having a hit count lower than the above
threshold can be removed from the search. If we set $P=\emptyset$, we have
$\mathpzc h(c)>0$, immediately pruning all zero-hit constituents. In other
words, we may only consider the constituents appearing in at least one
individual, which largely reduces the graph size from $\mathcal{O}(2^{n})$ to
$\mathcal{O}(nK)$ for $K$ individuals. In fact, the graph can be further
pruned with the below theorem.

######  Theorem 6 (Upper bound).

Let $c$ be a constituent with a hit count of $K$, where $K$ is the number of
individuals. (a) The constituent $c$ is compatible—i.e., may occur in the same
constituency tree—with every constituent in the average tree. (b) The
constituent $c$ appears in the average tree.

Theorem 6b suggests that the search process may exclude the constituents that
occur in all individuals, denoted by $P=\\{c:\mathpzc h(c)=K\\}$. In this
case, we may solve a reduced version of Problem 4 with the pruned graph and
$\alpha_{1}=\sum_{c^{\prime}\in P}{\mathpzc h}(c^{\prime})$,
$\alpha_{2}=|P|+2n-1$. The $\alpha_{1}$ and $\alpha_{2}$ in Theorem 4 can be
modified accordingly.444The proof is parallel to that of the original version
of Theorem 4, and we leave it as an exercise for readers. When we add $P$ back
to the solution, the connectivity of $P$ is guaranteed by Theorem 6a, forming
the solution (guaranteed to be a clique) for the original Problem 4.

To analyze the worst-case complexity, we notice that single words are
constituents that must occur in all individuals. At least, we may set
$P=\\{c:c\text{ is a single word}\\}$, and Theorem 5 yields a lower bound of

$\displaystyle{\mathpzc h}(c)>\min_{n\leq j\leq
2n-2}\;\frac{0+nK}{j+2n-1}>\frac{nK}{4n}=\frac{K}{4}$ (6)

Then, we can find an upper bound for the number of candidates kept for the
search process. Since the sum of all hit counts is always $(2n-1)K$, the
number of candidates with a higher hit count than the threshold in Eqn. (6) is
bounded by

$\displaystyle|V|\leq\Big{\lfloor}\frac{(2n-1)K}{K/4}\Big{\rfloor}<8n$ (7)

This shows that our pruning mechanism, profoundly, reduces the graph size from
$\mathcal{O}(2^{n})$ to $\mathcal{O}(n)$, which in turn reduces the overall
time complexity of our tree averaging from $\mathcal{O}(2^{2^{n-1}+2n})$ to
$\mathcal{O}(2^{\frac{n}{2}}n^{2})$ in the worst-case scenario.

In practice, the pruning is even more effective when the individuals either
largely agree or largely disagree with each other. In the former case, we will
have more all-hit constituents excluded from the search and consequently the
lower bound increases, whereas in the latter case, many constituents will fall
short of the lower bound. Empirically, our algorithm is efficient for all
samples in our experiments.

##  3 Experiments

###  3.1 Settings

Datasets. We evaluated our method on Dutch and German datasets, where
discontinuous constituents are relatively common. In particular, we used the
LASSY treebank (Van Noord et al., 2013) for Dutch. For German, we trained our
individuals on the union of NEGRA (Skut et al., 1997) and TIGER (Brants et
al., 2002) treebanks, while testing and reporting the performance on their
test sets respectively. Our settings strictly followed Yang et al. (2023) for
fair comparison.

Evaluation Metrics. $F_{1}$ scores are commonly used for evaluating
constituency parsing performance (Klein, 2005; Shen et al., 2018a, 2019; Kim
et al., 2019a, b). In our work of unsupervised discontinuous constituency
parsing, we report corpus-level $F_{1}$ scores of all constituents, continuous
constituents, and discontinuous constituents, denoted by
$F_{1}^{\text{overall}}$, $F_{1}^{\text{cont}}$, and $F_{1}^{\text{disco}}$,
respectively. We followed the previous work (Yang et al., 2023), which
discards punctuation and excludes trivial constituents (the whole sentence and
single words) when calculating the $F_{1}$ scores.

Setups of Our Ensemble. As mentioned in §2.1, we used different runs of the
tensor decomposition-based neural LCFRS (TN-LCFRS; Yang et al., 2023) as our
individual models. Our experiment was based on the released
code555https://github.com/sustcsonglin/TN-LCFRS with default training
hyperparameters. However, we find the TN-LCFRS is highly unstable, with a very
high variance and lower overall performance than Yang et al. (2023). As a
remedy, we trained the model $10$ times and selected the top five based on
validation $F_{1}^{\text{overall}}$, and this yields performance close to Yang
et al. (2023). In addition, we observe that random weight initializations lead
to near-zero correlation of the predicted discontinuous constituents, but our
ensemble method expects the individuals to at least agree with each other to
some extent. Therefore, our different runs started with the same weight
initialization666Our pilot study shows the proposed ensemble method is not
sensitive to the initialization, as long as it is shared among different runs.
This is also supported by the evidence that our approach performs well
consistently on three datasets. but randomly shuffled the order of training
samples to achieve stochasticity.

Our ensemble method does not have hyperparameters. However,
$F_{1}^{\text{overall}}$ and $F_{1}^{\text{disco}}$ may not correlate well.
Since our ensemble objective is solely based on $F_{1}^{\text{overall}}$, we
may enhance $F_{1}^{\text{disco}}$ by weighting the individuals with
validation $F_{1}^{\text{disco}}$ scores in hopes of achieving high
performance in all aspects. Note that weighting individuals does not hurt our
theoretical analysis and algorithm, because weighting is equivalent to
duplicating individuals (since all the weights are rational numbers) and can
be implemented by modifying hit counts without actual duplication.

|  | NEGRA | TIGER | LASSY
---|---|---|---|---
Method${}^{(\\#\text{ preterminal symbols})}$ | $F_{1}^{\text{overall}}$ | $F_{1}^{\text{cont}}$ | $F_{1}^{\text{disco}}$ | $F_{1}^{\text{overall}}$ | $F_{1}^{\text{cont}}$ | $F_{1}^{\text{disco}}$ | $F_{1}^{\text{overall}}$ | $F_{1}^{\text{cont}}$ | $F_{1}^{\text{disco}}$
Baselines (four runs each)† |  |  |  |  |  |  |  |  |
1 | Left branching | $\ \ 7.8$ |  – | $\ \ 0.0$ | $\ \ 7.9$ |  – | $\ \ 0.0$ | $\ \ 7.2$ |  – | $\ \ 0.0$
2 | Right branching | $12.9$ |  – | $\ \ 0.0$ | $14.5$ |  – | $\ \ 0.0$ | $24.1$ |  – | $\ \ 0.0$
3 | N-PCFG(45) | $40.8_{\pm 0.5}$ |  – | $\ \ 0.0$ | $39.5_{\pm 0.4}$ |  – | $\ \ 0.0$ | $40.1_{\pm 3.9}$ |  – | $\ \ 0.0$
4 | C-PCFG(45) | $39.1_{\pm 1.9}$ |  – | $\ \ 0.0$ | $38.8_{\pm 1.3}$ |  – | $\ \ 0.0$ | $37.9_{\pm 3.4}$ |  – | $\ \ 0.0$
5 | TN-PCFG(4500) | $45.4_{\pm 0.5}$ |  – | $\ \ 0.0$ | $44.7_{\pm 0.6}$ |  – | $\ \ 0.0$ | $44.3_{\pm 6.4}$ |  – | $\ \ 0.0$
6 | N-LCFRS(45) | $33.7_{\pm 2.8}$ |  – | $\ \ 2.0_{\pm 0.8}$ | $32.7_{\pm 1.8}$ |  – | $\ \ 1.2_{\pm 0.8}$ | $36.9_{\pm 1.5}$ |  – | $\ \ 0.9_{\pm 0.8}$
7 | C-LCFRS(45) | $36.7_{\pm 1.5}$ |  – | $\ \ 2.7_{\pm 1.4}$ | $35.2_{\pm 1.2}$ |  – | $\ \ 1.7_{\pm 1.1}$ | $36.9_{\pm 3.7}$ |  – | $\ \ 2.2_{\pm 1.0}$
8 | TN-LCFRS(4500) | $46.1_{\pm 1.1}$ |  – | $\ \ 8.0_{\pm 1.1}$ | $45.4_{\pm 0.9}$ |  – | $\ \ 6.1_{\pm 0.8}$ | $45.6_{\pm 2.3}$ |  – | $\ \ 8.9_{\pm 1.5}$
Individuals: TN-LCFRS(4500) |  |  |  |  |  |  |  |  |
9 | Five runs | $46.4_{\pm 0.5}$ | $49.8_{\pm 1.3}$ | $\ \ 6.0_{\pm 4.0}$ | $45.8_{\pm 1.3}$ | $49.9_{\pm 1.1}$ | $\ \ 4.0_{\pm 3.2}$ | $46.7_{\pm 2.0}$ | $50.9_{\pm 1.7}$ | $\ \ 6.2_{\pm 1.9}$
10 |  $F_{1}^{\text{overall}}$-best run | $\underline{46.9}$ | $50.2$ | $\ \ 1.3$ | $\underline{47.2}$ | $51.1$ | $\ \ 5.9$ | $\underline{48.2}$ | $52.4$ | $\ \ 5.8$
11 |  $F_{1}^{\text{cont}}$-best run | $46.7$ | $\underline{51.3}$ | $\ \ 7.3$ | $47.2$ | $\underline{51.1}$ | $\ \ 5.9$ | $48.2$ | $\underline{52.4}$ | $\ \ 5.8$
12 |  $F_{1}^{\text{disco}}$-best run | $46.0$ | $48.3$ | $\underline{10.4}$ | $45.4$ | $48.8$ | $\ \ \underline{6.6}$ | $48.0$ | $52.1$ | $\ \ \underline{8.6}$
13 | Binary ensemble | ${47.6}^{*}$ | ${50.1}$ | $\ \ {9.9}$ | ${47.8}^{**}$ | ${51.5}$ | $\ \ {6.5}$ | ${50.9}^{**}$ | ${54.6}^{**}$ | $\ \ {9.7}^{**}$
14 | Non-binary ensemble | $\textbf{49.1}^{**}$ | 51.5 | 10.6 | $\textbf{48.7}^{**}$ | $\textbf{52.4}^{**}$ |  6.6 | $\textbf{51.4}^{**}$ | $\textbf{55.0}^{**}$ | $\textbf{10.2}^{*}$

Table 2: Main results. †Quoted from Yang et al. (2023). ∗$p$-value $<0.05$ in
an Improved Nonrandomized Sign test (Starks, 1979) against the best ensemble
individual in each metric, indicated by underline. ∗∗$p$-value $<0.01$.

Baselines. Our ensemble individual, TN-LCFRS (Yang et al., 2023), is naturally
included as a baseline. In addition, we consider different variants of
continuous PCFG parsers and discontinuous LCFRS parsers, based on vanilla
neural networks, compound prior (Kim et al., 2019a), and tensor decomposition-
based neural networks (Yang et al., 2021), denoted by
$[$N$|$C$|$TN$]$-$[$PCFG$|$LCFRS$]$.

###  3.2 Results and Analyses

Main Results. Tabel 2 presents the main results on three datasets. We
replicated TN-LCFRS with five runs as our ensemble individuals; our results
are similar to Yang et al. (2023), showing the success of our replication
(Rows 9 vs. 8).

In our study, we observe TN-LCFRS behaves inconsistently in different runs:
some runs are good at continuous constituents (Row 11), while others are good
at discontinuous ones (Row 12); both may disagree with the
$F_{1}^{\text{overall}}$-best run (Row 10).

Our ensemble approach (Rows 14) achieves $F_{1}^{\text{cont}}$ and
$F_{1}^{\text{disco}}$ scores comparable to, or higher than, all ensemble
individuals. This eventually leads to a much higher $F_{1}^{\text{overall}}$
score, with a $p$-value $<0.01$ in an Improved Nonrandomized Sign (INS) test
(Starks, 1979) with the binomial comparison over sentence-level
performance.777We chose INS test because it can properly handle a large number
of ties (neutral cases), when they do not necessarily suggest the equivalency
of the models but the inadequacy of test samples (e.g., no discontinuous
constituents in a sentence). Results are consistent on all three datasets.

| Overall | Cont | Disco
---|---|---|---
Model | TP | FP | TP | FP | TP | FP
Binary ensemble | $6392$ | $9318$ | $6290$ | $7934$ | $102$ | $1384$
Non-binary ensemble | $6321$ | $8858$ | $6221$ | $7605$ | $100$ | $1253$
Difference | $71$ | $460$ | $69$ | $329$ | $2$ | $131$

Table 3: Number of true positive (TP) and false positive (FP) constituents on
LASSY.

Binary vs. Non-Binary Ensemble. To the best of our knowledge, we are the first
to address non-binary unsupervised constituency parsing. A natural question is
whether and how non-binarity in the output improves the performance, given
that all individuals are binary. To this end, we conducted an experiment by
restricting the output to binary trees.888For binary outputs, we may still
perform the meet-in-the-middle search for non-binary trees, with the hit count
as the objective, and binarize them by post-processing. Note that Theorem 5
for pruning does not hold in this case, but we may still safely ignore zero-
hit constituents, making the algorithm affordable (although it is not as
efficient as the non-binary setting where Theorem 5 can be applied). We
compare the results with the non-binary setting in Rows 13–14, Table 2,
showing the consistent superiority of our non-binary ensemble in all metrics
and datasets. To further understand the effect of non-binarity, we report in
Table 3 true positive and false positive counts on the LASSY dataset.999We
chose LASSY as the testbed for all our analyses due to the limit of space and
time, because it is relatively more stable in terms of $F_{1}^{\text{disco}}$
than other datasets. Results suggest that the non-binary setting largely
eliminates false positive constituents, as the model may opt to predict fewer
constituents than that in the binary setting.

Figure 3: Effect of the number of ensemble individuals on LASSY. (a) Averaged
over $30$ trials with error bars indicating standard derivations. (b) Best-to-
worst incremental ensemble.

Number of Ensemble Individuals. We varied the number of individuals in the
ensemble to analyze its effect. In Figure 3a, we picked a random subset of
individuals from a pool of $10$ and averaged the results over $30$ trials.
Overall, more individuals lead to higher performance and lower variance in all
$F_{1}$ scores, although the performance may be saturated if there are already
a large number of individuals.

In addition, we present an analysis of the best-to-worst incremental ensembles
in Figure 3b, where we add individuals to the ensemble from the best to worst
based on $F_{1}^{\text{overall}}$. As seen, adding weak individuals to the
ensemble does not hurt, if not help, the performance in our experiments,
demonstrating that our ensemble approach is robust to the quality of
individuals.

Figure 4: Wall clock run time of tree-averaging algorithms on LASSY for
different sentence lengths.

Figure 5: Effectiveness of pruning on LASSY for (a) different sentence
lengths, and (b) different numbers of ensemble individuals. Note that the
orange dashed line does not fit the range of $y$-axis in (b).

Efficiency Analysis. We analyze the effect of our pruning mechanism and the
meet-in-the-middle algorithm. Pruning serves as preprocessing for our search,
and we show the number of remaining candidate constituents in Figure 5. The
empirical results confirm Theorem 5 bounding the number of candidates linear
in both sentence length and the number of individuals, as well as Theorem 6
further bounding it by a constant with respect to the number of individuals.

We further analyze wall clock run time in Figure 5, as the actual execution
time may be different from algorithmic complexity. In §A.1, we provide a
dynamic programming (DP) algorithm with time complexity of
$\mathcal{O}(n^{9})$ for a length-$n$ sentence. As shown in the figure, the DP
fails to serve as a practical algorithm due to the high-order polynomial. By
contrast, our exponential-time search algorithm, even without the meet-in-the-
middle technique, is able to run in a reasonable time for many samples
(especially short ones) because of the strong pruning mechanism. Our meet-in-
the-middle technique further speeds up the search, making our algorithm
efficient and faster than DP for all the data samples.

It is emphasized that this experiment also empirically verifies the
correctness of all our algorithms, as they perform exact inference and we have
obtained exact results by using different algorithms.

Additional Results. We provide additional results in the appendix. C:
Performance by constituency types; and D: Case study.

##  4 Related Work

Constituency parsing carries a long history in natural language processing
research (Charniak, 2000; Klein, 2005; Kallmeyer and Maier, 2010; Li et al.,
2019). Different setups of the task have been introduced and explored,
including supervised and unsupervised, continuous and discontinuous
constituency parsing (Shen et al., 2018a, b, 2019; Fernández-González and
Gómez-Rodríguez, 2020, 2021, 2023; Yang et al., 2023). In the unsupervised
setup, researchers typically define a joint distribution over the parse
structure and an observable variable, e.g., the sentence itself, and maximize
the observable variable’s likelihood through marginalization (Kim et al.,
2019a, b). To the best of our knowledge, previous unsupervised parsing studies
are all restricted to binary structures to squeeze the marginalization space,
and we are the first to address non-binary unsupervised parsing and show non-
binarity is beneficial to parsing performance.

Ensemble methods strategically combine multiple models to improve performance,
rooted in the bagging concept where different data portions are used to train
multiple models (Breiman, 1996a; Hastie et al., 2009). To build an ensemble,
straightforward methods include averaging and voting (Breiman, 1996a, b). For
outputs with internal structures, minimum Bayes risk decoding (MBR; Bickel and
Doksum, 2015) can be used to build an ensemble, where the vote is the negative
risk in MBR. However, existing MBR approaches are mostly selective, where the
output is selected from a candidate set (Kumar and Byrne, 2004; Titov and
Henderson, 2006; Shi et al., 2022). Shayegh et al. (2023) develop a generative
MBR that searches for a binary continuous tree. This work extends the Shayegh
et al. (2023) and searches in the space of discontinuous constituency trees,
leading to significant algorithmic design and theoretical analysis.

##  5 Conclusion

In this work, we address ensemble-based unsupervised discontinuous
constituency parsing by tree averaging, where we provide comprehensive
complexity analysis and develop an efficient search algorithm to obtain the
average tree. Our experiments on Dutch and German demonstrate the
effectiveness of our ensemble unsupervised method. To the best of our
knowledge, we are also the first to address, and show the importance of, non-
binary structures in unsupervised constituency parsing.

##  6 Limitations

Our work demonstrates both theoretical depth and empirical effectiveness, but
may also have limitations.

First, our work is rooted in a parsing project. We provide a series of
theoretical analyses and algorithmic designs for averaging constituency trees
under different setups. Following the trajectory, our ensemble approach may be
extended to trees or graphs beyond the parsing domain. We are happy to explore
this direction as future work.

Second, our model is only tested on Dutch and German datasets. This is
partially because of the established setups in previous work (Yang et al.,
2023) and the lack of annotated treebanks. Notice that English is usually
excluded from the study of unsupervised discontinuous parsing, because English
discontinuous structures are too rare for any model to discover. A potential
future direction is multilingual linguistic structure discovery, perhaps, with
ensembles of different languages.

Third, our theoretical analysis leaves an open problem about averaging binary
trees. However, pointing to open problems is usually considered a contribution
(instead of a weakness) in theoretical computer science. Our theoretical
analysis is also crucial to the understanding of our algorithms, because we
now know that our proposed method works at the level of Open Problem 1.

## References

  * Arora and Barak (2009) Sanjeev Arora and Boaz Barak.  _Computational Complexity: A Modern Approach_.  Cambridge University Press, 2009.  URL https://www.cambridge.org/us/catalogue/catalogue.asp?isbn=9780521424264.
  * Bickel and Doksum (2015) Peter J Bickel and Kjell A Doksum.  _Mathematical Statistics: Basic Ideas and Selected Topics_.  CRC Press, 2015.  URL https://bickel.stat.berkeley.edu/teaching.
  * Bod (2009) Rens Bod.  From exemplar to grammar: A probabilistic analogy-based model of language learning.  _Cognitive Science_ , 33(5):752–793, 2009.  URL https://onlinelibrary.wiley.com/doi/10.1111/j.1551-6709.2009.01031.x.
  * Brants et al. (2002) Sabine Brants, Stefanie Dipper, Silvia Hansen, Wolfgang Lezius, and George Smith.  The TIGER treebank.  In _Proceedings of the Workshop on Treebanks and Linguistic Theories_ , pages 24–41, 2002.  URL https://api.semanticscholar.org/CorpusID:6209052.
  * Breiman (1996a) Leo Breiman.  Bagging predictors.  _Machine Learning_ , 24:123–140, 1996a.  URL https://link.springer.com/article/10.1007/BF00058655.
  * Breiman (1996b) Leo Breiman.  Heuristics of instability and stabilization in model selection.  _The Annals of Statistics_ , 24(6):2350–2383, 1996b.  URL https://projecteuclid.org/journals/annals-of-statistics/volume-24/issue-6/Heuristics-of-instability-and-stabilization-in-model-selection/10.1214/aos/1032181158.full.
  * Cao et al. (2020) Steven Cao, Nikita Kitaev, and Dan Klein.  Unsupervised parsing via constituency tests.  In _Proceedings of the Conference on Empirical Methods in Natural Language Processing_ , pages 4798–4808, 2020.  URL https://aclanthology.org/2020.emnlp-main.389.
  * Carnie (2007) Andrew Carnie.  _Syntax: A Generative Introduction_.  Wiley Blackwell, 2 edition, 2007.  URL https://www.wiley.com/en-ca/Syntax:+A+Generative+Introduction,+4th+Edition-p-9781119569237.
  * Charniak (2000) Eugene Charniak.  A maximum-entropy-inspired parser.  In _the North American Chapter of the Annual Meeting of the Association for Computational Linguistics_ , pages 132–139, 2000.  URL https://aclanthology.org/A00-2018.
  * Clark (2001) Alexander Clark.  Unsupervised induction of stochastic context-free grammars using distributional clustering.  In _Proceedings of the Annual Meeting of the Association for Computational Linguistics Workshop on Computational Natural Language Learning_ , 2001.  URL https://aclanthology.org/W01-0713.
  * Cranenburgh et al. (2016) Andreas Cranenburgh, Remko Scha, and Rens Bod.  Data-oriented parsing with discontinuous constituents and function tags.  _Journal of Language Modelling_ , 4(1):57–111, 2016.  URL https://jlm.ipipan.waw.pl/index.php/JLM/article/view/100.
  * Fernández-González and Gómez-Rodríguez (2020) Daniel Fernández-González and Carlos Gómez-Rodríguez.  Discontinuous constituent parsing with pointer networks.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , pages 7724–7731, 2020.  URL https://ojs.aaai.org/index.php/AAAI/article/view/6275.
  * Fernández-González and Gómez-Rodríguez (2021) Daniel Fernández-González and Carlos Gómez-Rodríguez.  Reducing discontinuous to continuous parsing with pointer network reordering.  In _Proceedings of the Conference on Empirical Methods in Natural Language Processing_ , pages 10570–10578, 2021.  URL https://aclanthology.org/2021.emnlp-main.825.
  * Fernández-González and Gómez-Rodríguez (2023) Daniel Fernández-González and Carlos Gómez-Rodríguez.  Discontinuous grammar as a foreign language.  _Neurocomputing_ , 524:43–58, 2023.  URL https://www.sciencedirect.com/science/article/pii/S092523122201551X?via%3Dihub.
  * Goldsmith (2001) John Goldsmith.  Unsupervised learning of the morphology of a natural language.  _Computational Linguistics_ , 27(2):153–198, 2001.  URL https://direct.mit.edu/coli/article/27/2/153/1711/Unsupervised-Learning-of-the-Morphology-of-a.
  * Hastie et al. (2009) Trevor Hastie, Robert Tibshirani, Jerome Friedman, Trevor Hastie, Robert Tibshirani, and Jerome Friedman.  _The Elements of Statistical Learning: Data Mining, Inference, and Prediction_.  Springer, 2009.  URL https://link.springer.com/content/pdf/10.1007/978-0-387-84858-7_10.pdf.
  * Horowitz and Sahni (1974) Ellis Horowitz and Sartaj Sahni.  Computing partitions with applications to the knapsack problem.  _Journal of the Association for Computing Machinery_ , 21(2):277–292, 1974.  URL https://dl.acm.org/doi/10.1145/321812.321823.
  * Joshi (1985) Aravind K Joshi.  Tree adjoining grammars: How much context-sensitivity is required to provide reasonable structural descriptions?  In _Natural Language Parsing_ , pages 206–250. 1985.  URL https://www.cambridge.org/core/books/natural-language-parsing/tree-adjoining-grammars-how-much-contextsensitivity-is-required-to-provide-reasonable-structural-descriptions/81BFD6DAC6B0CB24A3042A06E964F2E1.
  * Kallmeyer and Maier (2010) Laura Kallmeyer and Wolfgang Maier.  Data-driven parsing with probabilistic linear context-free rewriting systems.  In _Proceedings of the International Conference on Computational Linguistics_ , pages 537–545, 2010.  URL https://aclanthology.org/C10-1061.
  * Kann et al. (2019) Katharina Kann, Anhad Mohananey, Samuel R. Bowman, and Kyunghyun Cho.  Neural unsupervised parsing beyond English.  In _Proceedings of the Workshop on Deep Learning Approaches for Low-Resource Natural Language Processing_ , pages 209–218, 2019.  URL https://aclanthology.org/D19-6123.
  * Kim et al. (2019a) Yoon Kim, Chris Dyer, and Alexander Rush.  Compound probabilistic context-free grammars for grammar induction.  In _Proceedings of the Annual Meeting of the Association for Computational Linguistics_ , pages 2369–2385, 2019a.  URL https://aclanthology.org/P19-1228.
  * Kim et al. (2019b) Yoon Kim, Alexander Rush, Lei Yu, Adhiguna Kuncoro, Chris Dyer, and Gábor Melis.  Unsupervised recurrent neural network grammars.  In _Proceedings of the North American Chapter of the Annual Meeting of the Association for Computational Linguistics: Human Language Technologies_ , pages 1105–1117, 2019b.  URL https://aclanthology.org/N19-1114.
  * Klein (2005) Dan Klein.  _The Unsupervised Learning of Natural Language Structure_.  Stanford University, 2005.  URL https://www.proquest.com/openview/4a4c32a46d9fab258d8114cede8311ed/1?pq-origsite=gscholar&cbl=18750&diss=y.
  * Klein and Manning (2002) Dan Klein and Christopher D. Manning.  A generative constituent-context model for improved grammar induction.  In _Proceedings of the Annual Meeting of the Association for Computational Linguistics_ , page 128–135, 2002.  URL https://dl.acm.org/doi/10.3115/1073083.1073106.
  * Kumar and Byrne (2004) Shankar Kumar and William Byrne.  Minimum Bayes-risk decoding for statistical machine translation.  In _Proceedings of the Human Language Technology Conference of the North American Chapter of the Association for Computational Linguistics_ , pages 169–176, 2004.  URL https://aclanthology.org/N04-1022.
  * Li et al. (2019) Bowen Li, Lili Mou, and Frank Keller.  An imitation learning approach to unsupervised parsing.  In _Proceedings of the Annual Meeting of the Association for Computational Linguistics_ , pages 3485–3492, 2019.  URL https://aclanthology.org/P19-1338.
  * Li and Lu (2023) Jiaxi Li and Wei Lu.  Contextual distortion reveals constituency: Masked language models are implicit parsers.  In _Proceedings of the Annual Meeting of the Association for Computational Linguistics_ , pages 5208–5222, 2023.  URL https://aclanthology.org/2023.acl-long.285.
  * Maier (2010) Wolfgang Maier.  Direct parsing of discontinuous constituents in German.  In _Proceedings of the NAACL HLT Workshop on Statistical Parsing of Morphologically-Rich Languages_ , pages 58–66, 2010.  URL https://aclanthology.org/W10-1407.
  * Maier et al. (2012) Wolfgang Maier, Miriam Kaeshammer, and Laura Kallmeyer.  PLCFRS parsing revisited: Restricting the fan-out to two.  In _Proceedings of the International Workshop on Tree Adjoining Grammars and Related Formalisms_ , pages 126–134, 2012.  URL https://aclanthology.org/W12-4615.
  * McCawley (1982) James D. McCawley.  Parentheticals and discontinuous constituent structure.  _Linguistic Inquiry_ , 13(1):91–106, 1982.  URL http://www.jstor.org/stable/4178261.
  * Peng et al. (2011) Huan-Kai Peng, Pang Wu, Jiang Zhu, and Joy Ying Zhang.  Helix: Unsupervised grammar induction for structured activity recognition.  In _Proceedings of the International Conference on Data Mining_ , pages 1194–1199, 2011.  URL https://ieeexplore.ieee.org/abstract/document/6137337.
  * Petrov and Klein (2007) Slav Petrov and Dan Klein.  Improved inference for unlexicalized parsing.  In _Proceedings of Human Language Technologies: The Conference of the North American Chapter of the Association for Computational Linguistics_ , pages 404–411, 2007.  URL https://aclanthology.org/N07-1051.
  * Shayegh et al. (2023) Behzad Shayegh, Yanshuai Cao, Xiaodan Zhu, Jackie CK Cheung, and Lili Mou.  Ensemble distillation for unsupervised constituency parsing.  _arXiv preprint arXiv:2310.01717_ , 2023.  URL https://arxiv.org/abs/2310.01717.
  * Shen et al. (2018a) Yikang Shen, Zhouhan Lin, Chin-Wei Huang, and Aaron Courville.  Neural language modeling by jointly learning syntax and lexicon.  In _International Conference on Representation Learning_ , 2018a.  URL https://openreview.net/forum?id=rkgOLb-0W.
  * Shen et al. (2018b) Yikang Shen, Zhouhan Lin, Athul Paul Jacob, Alessandro Sordoni, Aaron Courville, and Yoshua Bengio.  Straight to the tree: Constituency parsing with neural syntactic distance.  In _Proceedings of the Annual Meeting of the Association for Computational Linguistics_ , pages 1171–1180, 2018b.  URL https://aclanthology.org/P18-1108.
  * Shen et al. (2019) Yikang Shen, Shawn Tan, Alessandro Sordoni, and Aaron Courville.  Ordered neurons: Integrating tree structures into recurrent neural networks.  In _International Conference on Representation Learning_ , 2019.  URL https://openreview.net/forum?id=B1l6qiR5F7.
  * Shi et al. (2022) Freda Shi, Daniel Fried, Marjan Ghazvininejad, Luke Zettlemoyer, and Sida I. Wang.  Natural language to code translation with execution.  In _Proceedings of the Conference on Empirical Methods in Natural Language Processing_ , pages 3533–3546, 2022.  URL https://aclanthology.org/2022.emnlp-main.231.
  * Skut et al. (1997) Wojciech Skut, Brigitte Krenn, Thorsten Brants, and Hans Uszkoreit.  An annotation scheme for free word order languages.  In _Proceedings of the Applied Natural Language Processing_ , page 88–95, 1997.  URL https://dl.acm.org/doi/10.3115/974557.974571.
  * Snyder et al. (2009) Benjamin Snyder, Tahira Naseem, and Regina Barzilay.  Unsupervised multilingual grammar induction.  In _Proceedings of the Joint Conference of the Annual Meeting of the Association for Computational Linguistics and the International Joint Conference on Natural Language Processing of the Asian Federation of Natural Language Processing_ , pages 73–81, 2009.  URL https://aclanthology.org/P09-1009.
  * Stanojević and Steedman (2020) Miloš Stanojević and Mark Steedman.  Span-based LCFRS-2 parsing.  In _Proceedings of the International Conference on Parsing Technologies and the International Workshop on Parsing Technologies Shared Task on Parsing into Enhanced Universal Dependencies_ , pages 111–121, 2020.  URL https://aclanthology.org/2020.iwpt-1.12.
  * Starks (1979) Thomas H Starks.  An improved sign test for experiments in which neutral responses are possible.  _Technometrics_ , 21(4):525–530, 1979.  URL http://www.jstor.org/stable/1268292.
  * Titov and Henderson (2006) Ivan Titov and James Henderson.  Loss minimization in parse reranking.  In _Proceedings of the Conference on Empirical Methods in Natural Language Processing_ , pages 560–567, 2006.  URL https://aclanthology.org/W06-1666.
  * Tomita (1990) Masaru Tomita.  _Current Issues in Parsing Technology_.  Kluwer Academic Publishers, 1990.  URL https://link.springer.com/book/10.1007/978-1-4615-3986-5.
  * Van Noord et al. (2013) Gertjan Van Noord, Gosse Bouma, Frank Van Eynde, Daniel De Kok, Jelmer Van der Linde, Ineke Schuurman, Erik Tjong Kim Sang, and Vincent Vandeghinste.  Large scale syntactic annotation of written dutch: Lassy.  In _Essential Speech and Language Technology for Dutch_ , pages 147–164. 2013.  URL https://link.springer.com/chapter/10.1007/978-3-642-30910-6_9.
  * Versley (2014) Yannick Versley.  Experiments with easy-first nonprojective constituent parsing.  In _Proceedings of the Joint Workshop on Statistical Parsing of Morphologically Rich Languages and Syntactic Analysis of Non-Canonical Languages_ , pages 39–53, 2014.  URL https://aclanthology.org/W14-6104.
  * Vijay-Shanker et al. (1987) K. Vijay-Shanker, David J. Weir, and Aravind K. Joshi.  Characterizing structural descriptions produced by various grammatical formalisms.  In _Proceedings of the Annual Meeting of the Association for Computational Linguistics_ , page 104–111, 1987.  URL https://dl.acm.org/doi/10.3115/981175.981190.
  * Yang et al. (2021) Songlin Yang, Yanpeng Zhao, and Kewei Tu.  PCFGs can do better: Inducing probabilistic context-free grammars with many symbols.  In _Proceedings of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 1487–1498, 2021.  URL https://aclanthology.org/2021.naacl-main.117.
  * Yang et al. (2023) Songlin Yang, Roger Levy, and Yoon Kim.  Unsupervised discontinuous constituency parsing with mildly context-sensitive grammars.  In _Proceedings of the Annual Meeting of the Association for Computational Linguistics_ , pages 5747–5766, 2023.  URL https://aclanthology.org/2023.acl-long.316.
  * Younger (1967) Daniel H. Younger.  Recognition and parsing of context-free languages in time $n^{3}$.  _Information and Control_ , 10(2):189–208, 1967.  URL https://www.sciencedirect.com/science/article/pii/S001999586780007X?via%3Dihub.

##  Appendix A Proofs

###  A.1 Proof of Theorem 1

See 1

See 1

###### Proof.

Following the spirit of Shayegh et al. (2023), we may design a DP table with
two axes being the start and end of every component of a constituent, thus
$2F$-axes for fan-out $F$. For outputs being non-binary, our DP algorithm
requires one additional axis to indicate the number of nodes in a
subtree.101010If the output is restricted to binary trees, we do not need to
track the number of nodes in a subtree, because it is always $2n-1$ for $n$
leaves.

We define a DP variable $H(c,\tau)$ as the best total hit count for a
$\tau$-node constituency substree over a constituent $c$, which may be
discontinuous. A constituent with fan-out $f$ has $f$ components, each being a
span of consecutive words. Therefore, $c$ can be represented by $2F$ numbers
indicating the beginnings and ends of the components, as the fan-out is
bounded by $F$. For $\tau$, it is upper-bounded by $2n-1$ for a length-$n$
sentence. Overall, the DP table has a size of $\mathcal{O}(n^{2F+1})$.
Specially, we further define $H(c,0)=0$ for every $c$.

For initialization, we consider every single-word constituent $c$ and set
$H(c,1)=\mathpzc h(c)$, where $\mathpzc h(c)$ is the hit count of $c$ in
$T_{1},\cdots,T_{K}$. We also set $H(c,i)=-\infty$ for every $i>1$.

For recursion, we divide a constituent $c$ into smaller sub-constituents based
on breaking points $\bm{j}=(0,j_{1},j_{2},\cdots,j_{2F-1},|c|)$, where $|c|$
is the number of words in $c$, shown in Figure 6. We further join sub-
constituents based on the parity (even or odd) of their indexes.

$\displaystyle o_{\bm{j}}$
$\displaystyle=\bigoplus_{i=1,3,\cdots,2F-1}c[j_{i-1}:j_{i}]$ (8)
$\displaystyle e_{\bm{j}}$
$\displaystyle=\bigoplus_{i=2,4,\cdots,2F}c[j_{i-1}:j_{i}]$ (9)

where $c[b:e]$ denotes a constituent containing $b$th to $e$th words in $c$,
and $\oplus$ symbol is the joint of constituents. We also distribute the
capacity of the number of nodes into $e_{\bm{j}}$ and $o_{\bm{j}}$ branches by
setting $s$ as the $o_{\bm{j}}$’s share and assigning the rest to
$e_{\bm{j}}$.

To find the best breaking points and shares, we iterate over all possible
values for them:

$\displaystyle\bm{j}^{*}_{\tau},s^{*}_{\tau}=\operatorname*{argmax}_{\bm{j},\;\;0\leq\mathpzc
s\leq\tau}\;\Big{[}H(o_{\bm{j}},s)+H(e_{\bm{j}},\tau-s)\Big{]}$ (10)

where $\bm{j}=(0,j_{1},\cdots,j_{2F-1},|c|)$ must satisfy $j_{i}\leq
j_{i+1}\leq|c|$, $j_{1}\neq|c|$, and if $j_{i}\neq|c|$, then $j_{i}<j_{i+1}$.
We discard the cases that $o_{\bm{j}}$ or $e_{\bm{j}}$ have a fan-out greater
than $F$, because they are guaranteed not to appear in the output (Theorem 5,
whose proof does not rely on this theorem).

Our tree-building search processing first assumes a node is binary and then
decides whether to join its parent and children to achieve non-binarity.
Therefore, we calculate the best hit count when $c$ itself is excluded,
denoted by $H_{\text{excl}}$, or included, denoted by $H_{\text{incl}}$. We
have

$\displaystyle H_{\text{excl}}(c,\tau)$
$\displaystyle=H(o_{\bm{j}^{*}_{\tau}},s^{*}_{\tau})+H(e_{\bm{j}^{*}_{\tau}},\tau-s^{*}_{\tau})$
(11) $\displaystyle H_{\text{incl}}(c,\tau)$
$\displaystyle=H_{\text{excl}}(c,\tau-1)+\mathpzc h(c)$ (12)

Finally, the recursion is

$\displaystyle H(c,\tau)$
$\displaystyle=\max\\{H_{\text{excl}}(c,\tau),H_{\text{incl}}(c,\tau)\\}$ (13)

The best score of $\sum_{k=1}^{K}F_{1}(T,T_{k})$ for the sentence $S$ is

$\displaystyle\operatorname*{argmax}_{n<\tau<2n}\frac{H(S,\tau)}{\tau+2n-1}$
(14)

according to Eqn. (2). Problem 1, as a decision problem, can then be solved
trivially by checking whether the score in (14) is greater than or equal to
$z$.

Overall, the time complexity for a recursion step is $\mathcal{O}(n^{2F})$ to
find $\bm{j}^{*}_{\tau}$ and $s^{*}_{\tau}$. With an
$\mathcal{O}(n^{2F+1})$-sized DP table, the complexity of the entire DP
algorithm is $\mathcal{O}(n^{4F+1})$, which is polynomial. Therefore, Problem
1 belongs to P. ∎

The above proof concerns the decision problem (whether the score reaches or
exceeds a threshold). To search for the average constituency tree, we may
backtrack the best corresponding constituency subtrees during the recursion.

Notice that restricting output to be binary tree simplifies the algorithm by
always setting $s_{\tau}^{*}=2|o_{\bm{j}}|-1$,
$H(c,\tau)=H_{\text{incl}}(c,\tau)$, and only considering the computation of
$H(c,\tau)$ if $\tau=2|c|-1$. It reduces the complexity of a recursion step to
$\mathcal{O}(n^{2F-1})$ and that of the DP-table size to
$\mathcal{O}(n^{2F})$, resulting in an overall complexity of
$\mathcal{O}(n^{4F-1})$.

The soundness of the DP can be cross-validated by our meet-in-the-middle
search (§2.3 and §B). As both are exact algorithms, they should output exactly
the same results. This is what we observed in our experiments, providing
strong empirical evidence that both of our algorithms are sound.

Figure 6: An example of the recursion step. The yellow hachures indicate the
discontinuity in the constituent $c$.

###  A.2 Proof of Theorem 2

See 2

See 2

###### Proof.

In §A.1, we provide a DP algorithm and by backtracking we can easily obtain,
for any $\tau$, the constituency tree $T$ that maximizes $\sum_{c\in
T}\mathpzc h(c)$ such that $|C(T)|=\tau$ (i.e., the tree having $\tau$ nodes).
The DP algorithm, in fact, works for any scoring function $\mathpzc h$ over
constituents. Therefore, we have a polynomial-time solver for the following
problem:

Fixed-Size Maximization. Given a scoring function $\mathpzc h$ over
constituents of a length-$n$ sentence and a natural number $\tau$ such that
$n<\tau<2n$, what is the tree $T$ that maximizes $\sum_{c\in T}\mathpzc h(c)$
with $|C(T)|=\tau$?

For Problem 2, we may enumerate all possible values of $\tau$, i.e.,
$n<\tau<2n$. Given a fixed $\tau$, we have

$\displaystyle T^{(\tau)}$
$\displaystyle=\operatorname*{argmax}_{T:|T|=\tau}\sum_{k=1}^{K}F_{1}(T,T_{k})$
(15)
$\displaystyle=\operatorname*{argmax}_{T:|T|=\tau}\sum_{k=1}^{K}\frac{|C(T)\cap
C(T_{k})|}{|C(T)|+|C(T_{k})|}$ (16)
$\displaystyle=\operatorname*{argmax}_{T:|T|=\tau}\sum_{c\in
C(T)}\underbrace{\sum_{k=1}^{K}\frac{\mathds{1}[c\in
C(T_{k}(s))]}{\tau+|C(T_{k})|}}_{\hat{\mathpzc h}(c)}$ (17)
$\displaystyle=\operatorname*{argmax}_{T:|T|=\tau}\sum_{c\in
C(T)}\hat{\mathpzc h}(c)$ (18)

In Eqn. (18), we define a generalized scoring function $\hat{\mathpzc h}$,
which can be thought of as a weighted hit count. In other words, the
overall-$F_{1}$ maximization in Eqn. (15) can be reduced to the above fixed-
size maximization problem where the number of nodes is given, which can be
solved in polynomial time. We may repeatedly solve the problem for
$(n-2)$-many values of $\tau$ and find the best answer among them:

$\displaystyle\tau^{*}$
$\displaystyle=\operatorname*{argmax}_{n<\tau<{2n}}\quad\sum_{k=1}^{K}F_{1}(T^{(\tau)},T_{k})$
(19) $\displaystyle T^{*}$ $\displaystyle=T^{(\tau^{*})}$ (20)

This does not push the complexity beyond polynomial. Finally, we can answer
Problem 2 by checking whether $\sum_{k=1}^{K}F_{1}(T^{*},T_{k})\geq z$. ∎

###  A.3 Proof of Theorem 3

See 3

See 3

###### Proof.

To show a problem is NP-complete, we need to first show it is an NP problem,
i.e., polynomial-time solvable with a non-deterministic Turing machine. Then,
we need to show its completeness, i.e., any NP problem, or a known NP-complete
problem, can be reduced to this problem in polynomial time.

[Being NP] Being non-deterministic polynomial-time solvable is equivalent to
the ability to be verified with a certificate in polynomial time (Arora and
Barak, 2009). In our case, verifying the score of any candidate tree (which
may serve as the certificate) can be done in polynomial time, proving the NP
part.

[Being complete] To show the completeness, it suffices to reduce a known NP-
complete problem to the problem at hand. In particular, we would reduce the
max clique problem, known to be NP-complete (Arora and Barak, 2009), to our
problem.

Max Clique. Consider a number $z$ and a graph $G$. Is there a clique in $G$
having at least $z$ vertices?

For reduction, we use our problem to solve the max clique problem with
$G=\langle V,E\rangle$ and $z$ being given.

Without loss of generality, we may assume that $G$ does not contain any vertex
that is connected to all other vertices for the rest of this proof. This is
because such a vertex is guaranteed to appear in any maximal clique and can be
pruned. Then the original problem is equivalent to determining whether the
pruned graph has $(z-a)$-many vertices, where $a$ is the number of pruned
vertices. Notice that such pruning can be accomplished in polynomial time,
thus not changing the complexity category.

Figure 7: An example of reduction.

We construct an instantiation of Problem 3 as follows. For every
$u_{i}\in{V}$, construct a set $S_{i}$ initialized by a special symbol
$t_{i}$. For every disconnected vertex pair $(u_{i},u_{j})$ such that $i<j$,
place a special symbol $t_{i}^{j}$ in both $S_{i}$ and $S_{j}$, shown in
Figure 7. We can view each $t_{i}$ and $t_{i}^{j}$ as words in a sentence.
Each $S_{i}$ represents a possible constituent containing the words
corresponding to its elements.

For each $S_{i}$, construct a constituency tree $T_{i}$ by all the single
words, the whole-sentence constituent, and $S_{i}$. Note that $S_{i}$ cannot
be a single word because there is no vertex in $G$ connected to all other
vertices. Moreover, $S_{i}$ cannot be the whole-sentence constituent either,
because $S_{i}$ does not contain the word $t_{i^{\prime}}$ for $i^{\prime}\neq
i$. Therefore, $|C(T_{i})|=n+2$ where $n$ is the number of words.

We next show that Problem 3 given $\\{T_{i}\\}_{i:u_{i}\in{V}}$ and the value
$\tilde{z}=\frac{2{z}+2|{V}|(n+1)}{{z}+n+2}$ is equivalent to the max clique
problem given the graph $G$ and the number ${z}$.

For every $u_{i},u_{j}\in{V}$ with $i<j$, $u_{i}$ and $u_{j}$ are connected if
and only if $S_{i}\cap S_{j}=\emptyset$; otherwise $t_{i}^{j}$ is in both
$S_{i}$ and $S_{j}$. In addition, $S_{i}\not\subseteq S_{j}$ for $i\neq j$
because there is a special symbol $t_{i}$ in each $S_{i}$. In other words,
$S_{i}$ and $S_{j}$ are compatible constituents if and only if $u_{i}$ and
$u_{j}$ are connected in $G$. As a result, every constituency tree—constructed
by single words, the whole-sentence constituent, and a subset of
$\\{S_{i}\\}_{i:u_{i}\in{V}}$—corresponds to a clique in $G$. We refer to such
a tree as a clique tree.

We can further find the correspondence of the scores between Problem 3 and the
max clique problem. For every clique tree $T$, we have

$\displaystyle\sum_{i:\,u_{i}\in{V}}F_{1}({T},{T}_{i})$
$\displaystyle=\sum_{i:\,u_{i}\in{V}}\frac{2(\mathds{1}[C({T}_{i})\subseteq
C({T})]+n+1)}{|C({T})|+n+2}$ (21)
$\displaystyle=\frac{2|C(T)|+2|{V}|(n+1)}{|C({T})|+n+2}$ (22)

where $|C({T})|$ is the same as the number of vertices in the corresponding
clique. This shows a clique tree ${T}$ with a score of
$\tilde{z}=\frac{2{z}+2|{V}|(n+1)}{{z}+n+2}$ corresponds to a clique with
${z}$ vertices.

Now, let us consider using a solver for Problem 3 to solve the max clique
problem. This is discussed by cases.

[Case 1] If the answer to Problem 3 is “no,” it means that there does not
exist a tree (either a clique tree or a general tree) $T$ satisfying
$\sum_{u_{i}\in{V}}F_{1}({T},{T}_{i})\geq\tilde{z}$. Thus, there does not
exist a clique $Q$ satisfying $|Q|\geq z$.

[Case 2] If the answer to Problem 3 is “yes,” there must exist a tree $T$
satisfying the condition $\sum_{u_{i}\in{V}}F_{1}({T},{T}_{i})\geq\tilde{z}$.
Notice that such a tree is not guaranteed to be a clique tree, but in this
case, we can show there must also exist a clique tree satisfying the
condition.

In general, a tree is a clique tree if and only if it does not include any
zero-hit constituents (zero hit means not appearing in any $T_{i}$). This is
because, other than single words and the whole-sentence constituent, a clique
tree selects a subset of $\\{S_{i}\\}_{i:u_{i}\in{V}}$, whereas each $T_{i}$
only selects one element of this set. Let $C_{0}(T)$ denote zero-hit
constituents in $T$. We construct $T^{\prime}$ by removing $C_{0}(T)$ from
$T$. We have

$\displaystyle\tilde{z}$ $\displaystyle\leq\sum_{k=1}^{K}F_{1}(T,T_{k})$ (23)
$\displaystyle=\sum_{k=1}^{K}\frac{2\sum_{c\in C(T)}\mathpzc
h(c)}{|C(T)|+|C(T_{k})|}$ (24)
$\displaystyle\leq\sum_{k=1}^{K}\frac{2\sum_{c\in C(T)\backslash
C_{0}(T)}\mathpzc h(c)}{|C(T)|-|C_{0}(T)|+|C(T_{k})|}$ (25)
$\displaystyle=\sum_{k=1}^{K}\frac{2\sum_{c\in C(T^{\prime})}\mathpzc
h(c)}{|C(T^{\prime})|+|C(T_{k})|}$ (26)
$\displaystyle=\sum_{k=1}^{K}F_{1}(T^{\prime},T_{k})$ (27)

Here, Inequality (23) is due to the assumption of Case 2 that the answer to
Problem 3 is “yes.” Inequality (25) is because $|C_{0}(T)|\geq 0$ and $h(c)=0$
for $c\in C_{0}(T)$, potentially increasing the denominator while the
numerator is the same.

Since $T^{\prime}$ is a clique tree that satisfies
$\sum_{k=1}^{K}F_{1}(T^{\prime},T_{k})\geq\tilde{z}$, we find the solution to
the max clique problem is also “yes.”

The given reduction can be done in polynomial time, as it iterates over all
vertices and vertex pairs. This concludes that Problem 3 belongs to NP-
complete. ∎

###  A.4 Proof of Lemma 1

Lemma 1. Given a graph $G$ as described in §2.3, the clique $Q^{*}$ maximizing
$f(Q;\alpha_{1},\alpha_{2})$ corresponds to a constituency tree, if
$\alpha_{1}\leq K\alpha_{2}$ where $K$ is the number of individuals.

###### Proof.

A selection of constituents corresponds to a constituency tree over a sentence
if and only if (1) it includes all the single words and the whole-sentence
constituent, referred to as trivial constituents, and (2) all of its
constituents are compatible with each other (already satisfied by clique the
definition).

Trivial constituents are compatible with any possible constituent, and thus
their corresponding vertices are connected to all vertices in $G$. Moreover,
the hit count of such a constituent equals $K$, the number of individual
trees, because trivial constituents appear in all constituency trees.

We assume by way of contradiction that a trivial constituent does not appear
in the constituency tree corresponding to $Q^{*}$. This is equivalent to
having a vertex $u$—connected to every vertex in $G$ with $w(u)=K$, i.e.,
having a weight of $K$—not appearing in $Q^{*}$; that is,

$\displaystyle f({Q}^{*}\cup\\{u\\};\alpha_{1},\alpha_{2})$
$\displaystyle<f({Q}^{*};\alpha_{1},\alpha_{2})$ (28)

With the definition of $f$, we have

$\displaystyle\frac{\sum_{v\in{Q}^{*}}w(v){+}w(u){+}\alpha_{1}}{|{Q}^{*}|+1+\alpha_{2}}$
$\displaystyle<\frac{\sum_{v\in{Q}^{*}}w(v)+\alpha_{1}}{|{Q}^{*}|+\alpha_{2}}$
(29)
$\displaystyle\frac{\sum_{v\in{Q}^{*}}w(v){+}w(u){+}\alpha_{1}}{\sum_{v\in{Q}^{*}}w(v)+\alpha_{1}}$
$\displaystyle<\frac{|{Q}^{*}|+1+\alpha_{2}}{|{Q}^{*}|+\alpha_{2}}$ (30)
$\displaystyle 1+\frac{w(u)}{\sum_{v\in{Q}^{*}}w(v)+\alpha_{1}}$
$\displaystyle<1+\frac{1}{|{Q}^{*}|+\alpha_{2}}$ (31) $\displaystyle w(u)$
$\displaystyle<\frac{\sum_{v\in{Q}^{*}}w(v)+\alpha_{1}}{|{Q}^{*}|+\alpha_{2}}$
(32) $\displaystyle w(u)$
$\displaystyle<\frac{K|{Q}^{*}|+K\alpha_{2}}{|{Q}^{*}|+\alpha_{2}}=K$ (33)

Here, the last inequality is due to $\alpha_{1}<K\alpha_{2}$ and $w(v)\leq K$
for every $v$. But this inequality contradicts our assumption that $w(u)=K$. ∎

###  A.5 Proof of Theorem 5

See 5

###### Proof.

Consider any constituent $c_{0}\in C(T^{*})\backslash P$. We construct
$T^{\prime}$ by removing $c_{0}$ from $T^{*}$, i.e.,
$C(T^{*})=C(T^{\prime})\cup\\{c_{0}\\}$. Based on Eqn. (2), we have

$\displaystyle\frac{\sum_{c\in C(T^{*})}{\mathpzc h}(c)}{|C(T^{*})|+2n-1}$
$\displaystyle>\frac{\sum_{c\in C(T^{\prime})}{\mathpzc
h}(c)}{|C(T^{\prime})|+2n-1}$ (34) $\displaystyle\frac{\sum_{c\in
C(T^{*})}{\mathpzc h}(c)}{\sum_{c\in C(T^{\prime})}{\mathpzc h}(c)}$
$\displaystyle>\frac{|C(T^{*})|+2n-1}{|C(T^{\prime})|+2n-1}$ (35)
$\displaystyle 1+\frac{{\mathpzc h}(c_{0})}{\sum_{c\in C(T^{\prime})}{\mathpzc
h}(c)}$ $\displaystyle>1+\frac{1}{|C(T^{\prime})|+2n-1}$ (36)
$\displaystyle{\mathpzc h}(c_{0})$ $\displaystyle>\frac{\sum_{c\in
C(T^{\prime})}{\mathpzc h}(c)}{|C(T^{\prime})|+2n-1}$ (37)

Since the right-hand side is non-negative, we must have $h(c_{0})>0$. In other
words, zero-hit constituents do not appear in $C(T^{*})\backslash P$. Thus,
$m$-many constituents in $C(T^{*})\backslash P$ have a total of hit count
greater than or equal to $\sum_{i=1}^{m}\lambda_{i}^{(+)}$, because
$\lambda_{i}^{(+)}$ is the $i$th smallest positive hit count.

On the other hand, we have $c_{0}\notin P$, implying that $P\subseteq
C(T^{\prime})$. Since a constituent $c\in C(T^{\prime})$ is either in $P$ or
not, we can lower-bound the total hit count of $T^{\prime}$ by

$\displaystyle\sum_{c\in C(T^{\prime})}{\mathpzc h}(c)\geq\sum_{c^{\prime}\in
P}{\mathpzc h}(c^{\prime})+\sum_{i=1}^{|C(T^{\prime})\backslash
P|}\lambda^{+}_{i}$ (38)

Putting (38) into (37), we have

$\displaystyle{\mathpzc h}(c_{0})$
$\displaystyle>\frac{\sum_{i=1}^{|C(T^{\prime})|-|P|}\lambda^{+}_{i}+\sum_{c^{\prime}\in
P}{\mathpzc h}(c^{\prime})}{|C(T^{\prime})|+2n-1}$ (39)

Moreover, $P\subseteq C(T^{\prime})$ also implies

$\displaystyle|P|\leq|C(T^{\prime})|=|C(T^{*})|-1\leq 2n-2$ (40)

which derives (39) to a $T^{\prime}$-independent lower bound for $h(c_{0})$ if
we consider all the values $|C(T^{\prime})|$ can take, given by

$\displaystyle h(c_{0})>\min_{|P|\leq j\leq
2n-2}\frac{\sum_{i=1}^{j-|P|}\lambda^{+}_{i}+\sum_{c^{\prime}\in P}{\mathpzc
h}(c^{\prime})}{j+2n-1}$ (41)

concluding the proof. ∎

The lower bound can be applied for pruning the search. We may immediately
prune zero-hit constituents by setting $P=\emptyset$, and more importantly, it
yields a much tighter lower bound together with Theorem 6.

###  A.6 Proof of Theorem 6

See 6

###### .

[Part (a)] A hit count of $K$ indicates that the constituent appears in all
the individuals. Therefore, $c$ is compatible with every constituent in every
individual. On the other hand, Theorem 5 shows that every constituent in the
average tree has a positive hit count (appears in at least one individual) and
thus is compatible with $c$.

[Part (b)] We assume by way of contradiction that a constituent $c_{0}$ with a
hit count of $K$ does not appear in the average tree $T^{*}$. As shown in (a),
$c_{0}$ is compatible with every constituent in $T^{*}$; hence, there exists a
constituency tree $\hat{T}$ such that $C(\hat{T})=C(T^{*})\cup\\{c_{0}\\}$.
Based on Eqn. (2), we have

$\displaystyle\frac{\sum_{c\in C(\hat{T})}{\mathpzc h}(c)}{|C(\hat{T})|+2n-1}$
$\displaystyle<\frac{\sum_{c\in C({T^{*}})}{\mathpzc h}(c)}{|C(T^{*})|+2n-1}$
(42) $\displaystyle\frac{\sum_{c\in C(\hat{T})}{\mathpzc h}(c)}{\sum_{c\in
C({T^{*}})}{\mathpzc h}(c)}$
$\displaystyle<\frac{|C(\hat{T})|+2n-1}{|C(T^{*})|+2n-1}$ (43) $\displaystyle
1+\frac{{\mathpzc h}(c_{0})}{\sum_{c\in C({T^{*}})}{\mathpzc h}(c)}$
$\displaystyle<1+\frac{1}{|C(T^{*})|+2n-1}$ (44) $\displaystyle{\mathpzc
h}(c_{0})$ $\displaystyle<\frac{\sum_{c\in C({T^{*}})}{\mathpzc
h}(c)}{|C(T^{*})|+2n-1}$ (45) $\displaystyle{\mathpzc h}(c_{0})$
$\displaystyle<\frac{K|C(T^{*})|}{|C(T^{*})|+2n-1}\leq K$ (46)

Here, the last inequality is due to $\mathpzc h(c)\leq K$ for every $c$. But
this contradicts our assumption that $\mathpzc h(c_{0})=K$. ∎

##  Appendix B Our Meet-in-the-Middle Algorithm

The meet-in-the-middle technique (Horowitz and Sahni, 1974) has been used to
tackle the max clique problem. This method halves the exponent of the time
complexity of exhaustive search, cutting it down from $\mathcal{O}(2^{|V|})$
to $\mathcal{O}(2^{\frac{|V|}{2}}|V|^{2})$ given a graph with $|V|$ vertices.
However, the exact same algorithm is not sufficient for our needs, because
Problem 4 is a generalization of the max clique problem and requires
additional consideration. In this section, we develop an extended version of
the algorithm that solves Problem 4 within the same time complexity.

See 4

To find the solution to Problem 4, we utilize the meet-in-the-middle
technique, which splits the vertex set $V$ into two parts $V_{1}$ and $V_{2}$,
whose sizes are as equal as possible.

For every $V^{\prime}_{1}\subseteq V_{1}$ and every $0\leq
j\leq|V^{\prime}_{1}|$, we define

$\displaystyle\operatorname{best}(V^{\prime}_{1},j)=\operatorname*{argmax}\limits_{\begin{subarray}{c}V_{1}^{\prime\prime}:\
V_{1}^{\prime\prime}\subseteq V^{\prime}_{1},|V^{\prime\prime}_{1}|=j,\\\
\text{$V^{\prime\prime}_{1}$ is a clique}\end{subarray}}\quad\sum_{v\in
V^{\prime\prime}_{1}}w(v)$ (47)

which is the best $j$-vertex clique in $V_{1}^{\prime}$, and can be computed
recursively.

For initialization, we have $\operatorname{best}(V^{\prime}_{1},0)=\emptyset$
for every $V^{\prime}_{1}\subseteq V_{1}$ and
$\operatorname{best}(\\{u\\},1)=\\{u\\}$ for every $u\in V_{1}$.

The recursion is to compute the $\operatorname{best}$ set for any multi-vertex
$V^{\prime}_{1}$ assuming we have the $\operatorname{best}$ set for every
subset of $V_{1}$, whose size is smaller than $V^{\prime}_{1}$. To achieve
this, we pick any $u\in V^{\prime}_{1}$, and the
$\operatorname{best}(V^{\prime}_{1},j)$ may or may not include $u$, which is
discussed by cases.

If $u\not\in\operatorname{best}(V^{\prime}_{1},j)$, we have

$\displaystyle\operatorname{best}(V^{\prime}_{1},j)=\operatorname{best}(V^{\prime}_{1}\backslash\\{u\\},j)$
(48)

If otherwise $u\in\operatorname{best}(V^{\prime}_{1},j)$, then the other $j-1$
vertices must be the neighbors of $u$ in $V^{\prime}_{1}$, because
$\operatorname{best}(\cdot,\cdot)$ must be a clique. Denoting by
$A_{V^{\prime}_{1}}^{(u)}$ all the vertices in $V^{\prime}_{1}$ connected to
$u$, we have

$\displaystyle\operatorname{best}(V^{\prime}_{1},j)=\\{u\\}\cup\operatorname{best}(A_{V^{\prime}_{1}}^{(u)},j-1)$
(49)

Combining the two cases, we have $\operatorname{best}(V^{\prime}_{1},j)$ be
either Eqn. (48) or Eqn. (49), depending on which yields a higher weight.

For the $V_{2}$ part, we would like to evaluate every clique
$V^{\prime}_{2}\subseteq V_{2}$ and its corresponding best match in $V_{1}$ to
obtain $Q^{*}\subseteq V=V_{1}\cup V_{2}$ that maximizes our scoring function
$f(Q;\alpha_{1},\alpha_{2})$.

We enumerate all the subsets of $V_{2}$. For every clique
$V^{\prime}_{2}\subseteq V_{2}$, we denote by $A_{V_{1}}^{(V^{\prime}_{2})}$
the vertices in $V_{1}$ that are connected to every vertex in
$V^{\prime}_{2}$. We compute

$\displaystyle\operatorname{val}(V^{\prime}_{2},j)=\sum_{v\ \in\
V^{\prime}_{2}\;\cup\;\operatorname{best}\\!\big{(}A_{V_{1}}^{(V^{\prime}_{2})},j\big{)}}w(v)\quad$
(50)

being the weight of the best clique, which in $V_{1}$ has $j$ vertices and in
$V_{2}$ involves $V^{\prime}_{2}$ only.

Since the $V=V_{1}\cup V_{2}$, we can find the vertices of $Q^{*}$ in $V_{1}$
and $V_{2}$ separately:

$\displaystyle Q^{*}_{2},\;j^{*}=$
$\displaystyle\operatorname*{argmax}_{V^{\prime}_{2},\;j}\frac{\operatorname{val}(V^{\prime}_{2},j)+\alpha_{1}}{|V^{\prime}_{2}|+j+\alpha_{2}}$
(51) $\displaystyle Q^{*}_{1}=$
$\displaystyle\operatorname{best}\\!\big{(}A_{V_{1}}^{(Q^{*}_{2})},j^{*}\big{)}$
(52)

The final answer is $Q^{*}=Q^{*}_{1}\cup Q^{*}_{2}$.

We analyze the time complexity of our algorithm. For the $V_{1}$ part, our
algorithm enumerates $\mathcal{O}(2^{\frac{|V|}{2}})$-many subsets
$V_{1}^{\prime}$ and $\mathcal{O}(|V|)$-many $j$ values; in each iteration,
$\mathcal{O}(|V|)$-many vertices are visited for $A^{(u)}_{V^{\prime}_{1}}$.
For the $V_{2}$ part, we enumerate $\mathcal{O}(2^{\frac{|V|}{2}})$-many
subsets of $V_{2}$, each verified for being a clique in $\mathcal{O}(|V|^{2})$
time; after that, $A_{V_{1}}^{(V_{2}^{\prime})}$ is retrieved with complexity
$\mathcal{O}(|V_{1}|\cdot|V_{2}^{\prime}|)=\mathcal{O}(|V|^{2})$, which can be
absorbed in the $\mathcal{O}$-notation. Finally, retrieving $Q^{*}$ happens in
$\mathcal{O}(2^{\frac{|V|}{2}}|V|)$ time, and the overall time complexity of
our algorithm is $\mathcal{O}(2^{\frac{|V|}{2}}|V|^{2})$.

Figure 8: Recall scores of 10 most frequent constituent types on LASSY: (a)
among all constituents, and (b) among discontinuous constituents. The
percentages under the types indicate their occurrences in the dataset. Error
bars are the standard deviation for five individuals.

##  Appendix C Performance by Constituency Types

We would like to analyze our ensemble method’s performance from a linguistic
point of view. We provide a performance breakdown by constituency types, e.g.,
noun phrases (NP) and verb phrases (VP). Note that our unsupervised models
offer unlabeled constituency structures, and thus we can only compute recall
scores for different constituency types.

In Figures 8a and 8b, we report the recall scores for all constituents and
discontinuous constituents, respectively. We can see for most of the types,
the ensemble can retain the best individual’s performance in that type,
suggesting that the ensemble is able to leverage the diverse strengths of
different individuals.

##  Appendix D Case Studies

In Figure 9, we present a case study on the LASSY dataset to show how the
ensemble can take advantage of different individuals. In the figure, a
groundtruth constituent is annotated by its type (e.g., CONJ representing
conjunction). However, our unsupervised parsing is untyped, and we use “o” to
denote a constituent. A skipped line “-|-” indicates discontinuity.

Consider the last three words “moeten worden opgesteld” (must be
established)111111We provide English interpretations by ChatGPT-4 with the
prompt: “Translate the following Dutch sentence. Give word-by-word literal
translation.’’. We see the ensemble output follows the majority votes (three
out of five, namely Individuals $2$, $4$, and $5$) and detects the correct
structure of this phrase. Moreover, the ensemble is able to detect the
discontinuous constituent “in sommige gevallen … niet toereikend zijn” (in
some cases … not sufficient be), suggested by Individuals $4$ and $5$. On the
other hand, we also notice that every individual produces incorrect
discontinuous constituents, but our ensemble is able to smooth out such noise
and achieve high $F_{1}$ scores.

Figure 9: Case studies with an example in Dutch from the LASSY dataset.