Improving Unsupervised Constituency Parsing via Maximizing Semantic Information
Authors: Junjie Chen
Xiangheng He
Yusuke Miyao
Danushka Bollegala
Venue: ICLR 2025 Spotlight (2025)
Keywords: unsupervised constituency parsing
information theory
semantic information
Primary area: applications to computer vision, audio, language, and other modalities

Abstract: Unsupervised constituency parsers organize phrases within a sentence into a tree-shaped syntactic constituent structure that reflects the organization of sentence semantics. 
However, the traditional objective of maximizing sentence log-likelihood (LL) does not explicitly account for the close relationship between the constituent structure and the semantics, resulting in a weak correlation between LL values and parsing accuracy.
In this paper, we introduce a novel objective that trains parsers by maximizing SemInfo, the semantic information encoded in constituent structures.
We introduce a bag-of-substrings model to represent the semantics and estimate the SemInfo value using the probability-weighted information metric.
We apply the SemInfo maximization objective to training Probabilistic Context-Free Grammar (PCFG) parsers and develop a Tree Conditional Random Field (TreeCRF)-based model to facilitate the training. 
Experiments show that SemInfo correlates more strongly with parsing accuracy than LL, establishing SemInfo as a better unsupervised parsing objective.
As a result, our algorithm significantly improves parsing accuracy by an average of 7.85 sentence-F1 scores across five PCFG variants and in four languages, achieving state-of-the-art level results in three of the four languages.

Published as a conference paper at ICLR 2025
IMPROVING UNSUPERVISED CONSTITUENCY PARSING VIA MAXIMIZING SEMANTIC INFORMATION
Junjie Chen', Xiangheng He², Yusuke Miyao', Danushka Bollegala" 3 Department of Computer Science, the University of Tokyo'
GLAM Group on Language, Audio, & Music, Imperial College London Department of Computer Science, the University of Liverpool
christopher w.w.sssuuutte s.u.tokoo..... ac. jp, x. www.hee@meeertee allalll.. accuu uk yusukelis is. s. s.u-tottoee totokoo acc. jp, danushka iverpool. acc uk
ABSTRACT
Unsupervised constituency parsers organize phrases within sentence into tree- shaped syntactic constituent structure that reflects the organization of sentence se- mantics. However, the traditional objective of maximizing sentence log-likelihood (LL) does not explicitly account for the close relationship between the constituent structure and the semantics, resulting in weak correlation between LL values and parsing accuracy. In this paper, we introduce a novel objective that trains parsers by maximizing SemInfo, the semantic information encoded in constituent structures, We introduce a bag-of-substring estimate the SemInfo value using the probahillty-weighhed information metric. We apply the SemInfo maximization objective to training Probabilistic Context- Free Grammar (PCFG) parsers and develop Tree Conditional Random Field (TreeCRF)-basedd model to facilitate the training. Experiments show that SemInfo correlates more strongly with parsing accuracy than LL, establishing SemInfo as a better unsupervised parsing objective. As a result, our algorithm significantly improves parsing aceuracy by an average 7.85 sentence-Fi scores across five PCFG variants and in four languages, achieving state-of-the-art level results in three of the four languages.
model to represent the semantics and
INTRODUCTION
Unsupervised constituency parsing is syntactic task of organizing phrases of sentence into a tree- shaped constituent structure without relying on linguistic annotations (Klein & Manning, 2002). The constituent structure is fundamental tool in analyzing sentence semantics (i.e., the meaning) (Carnie) 2007 Steedman 2000). It can significantly improve performance for downstream Natural Language Processing systems, such as natural language inference (He et al. 2020), machine trans- lation Xie & Xing 2017) and semantic role labeling (Chen et al., 2022) systems. It guides the progressive construction of the sentence semanties, illustrated in Figure I Each constituent in the structure corresponds to a meaningful substring, forming partial representations of the sentence semantics. One can easily recover the full sentence semantics by gradually constructing the seman- tic representation of those constituent substrings. Following the observation, we hypothesize that constituent substrings in the sentence carry significant semantic information.
Maximizing sentence log-likelihood has traditionally been the primary training objective for training unsupervised constituency parsers (Eisner 2016 Kim et al. 2019a). However, the Likelihood (LL) function does not explicitly factor in the vyntax-semantin alignment. This leads to a poor cor- relation between the I.I. value and the parsing accuracy. We will further discuss this poor correlation in Section 5.3] As pointed out in previous research, it is challenging to train Probabilistic Context- Free Grammar (PCFG) parser that outperforms trivial baselines with the LL maximization objective
Carroll & Charniak 1992, Kim et al. 2019a). Successful training commonly involves altering the
LL maximization objective, such as imposing sparsity constraints (Cohen et al. 2008 Johnson et al.
2007) heuristically estimating the LL value (Spitkovsky et al. 2010). Theses evidence suggests
that the LL function might not provide robust information to distinguish between constituents and
non-constituents, rendering I.I. an insufficient objective function for unsupervised parsing.

---

Published as a conference paper at ICLR 2025
John has been working on theory until late night
Sentence:
John has been warking on theory until late night
John
has been working theory undil lato night
Consiitunt tree bracket form: (John (has working theory)) night])
has been working on theory
night
hol
been
working
on
thiory
until
night
On, we have theory
someone working
Oh, he is working until night
Oh, the man
(a theory)
(has been working on theory))
(has been working theory)) (until late night)
(John (has been working on (a theory)) (until late night))
An illustration of the progressive semantics build-up in accordance with the constituent structure. The tree structure in the top-right shows the simplified constituent structure for illustration purposes. Constituent substrings are highlighted in blue.
Figure 1:
In this paper, we propose novel objective for training unsupervised parsers: maximizing SemInfo (the semantic information encoded in constituent structures). Specifically, we introduce a bag-of- substrings model to represent the sentence semantics with substring statisties, in parallel how -oodds models represent document topics with word statistics. Next, we estimate the semantic information encoded in substrings (i.e., aabbstring-semanti information) by applying the Probability- Weighted Information (PWI) metric (Aizawa 2003) developed for the bag-of- words model to our ofg-of-substrings model. Finally, we calculate the SemInfo value of constituent structure by sum- ming up the substring-semanne information associated with the structure. Experiments show much stronger correlation between SemInfo and parsing accuracy than the correlation between L.I. and parsing accuracy. The improved correlation suggests SemInfo is an effective objective function for unsupervised constituency parsing. In addition, we develop a Tree Conditional Random Field (TreeCRF)- model to apply the mean-field SemInfo maximization training to PCFG parsers (the state-of- fi-the-art non-ensemble method for unsupervised constituency parsing (Liu et al.) 2023 ).
bag-of-words
Experiments demonstrate that the SemInfo maximization objective improves the PCFG's parsing accuracy by 7.85 sentence-Fl scores across five latest PCFG variants and in four languages.
Our main contributions information encoded in constituent structures. (2) Demonstrating strong correlation between Sem- Info values and parsing accuracy. (3) Developing a TreeCRF model to apply mean-field SemInfo maximization training to PCFG parsers, significantly improving parsing accuracy and achieving state-of-the thr level results as non-ensemble parsers.
(1) Proposing novel method for estimating SemInfo, the semantic
BACKGROUND
The idea that constituent structures reflect the organization of sentence semanties is central mod- linguistic studies (Steedman] 2000 Pollard & Sag 1987). A constituent is substring in a sentence x that can function independently (Carnic 2007) and carries self-contained meanings (Heim & Kratzer 1998). A collection of constituents forms tree-shaped structure t, which represent as collection of its constituent substrings t = {s1, s2..... For example, the constituent structure in the top right of Figure I can be represented ("a theory". "until late night"....), ...ht"...... Previ- ous research (Shen et al. 2017 Yang et al. (2021b) measures the accuracy of the parsing prediction by instance level sentence-Fi (SF1') score. Aggregating the SF1' score over the corpus gives the corpus-level sentence-F1 score (SF1)), which previous research used to evaluate the parser quality.
2

---

Published as a conference paper at ICLR 2025
In this paper, will apply the Probability- trobabllit-Weiihtted Information (PWI) Aizawa 2003) designed
to measure word-topic information in bag-of-words models (Figure 2a measuring substring- semantic information in our bag-of-substrings model. PWI is an information-theorete interpretation of the term frequency-invers document frequency (tf-idf) statistic. The tf-idf statistic is an effective feature in finding keywords in documents (Li et al. (007) or in locating documents based on the given keyword (Mishra & Vishwakarma 2013). Let D denote a document corpus, d, the i-th docu- ment in the corpus, and Wiy the 3-th word in dę The bag-of-words model represents the document d, as an unordered collection of words occurring in the document (i.e., d, = {wi,, (..,...).. Tf-idf, as shown Equation | is the product of the term frequency F(wij, di) (i.c. the frequency of wii occurring in d.) and the inverse document frequency (i.e. the inverse log-frequency of documents containing Wij). PWI interprets the term frequency as the word generation probability and the in- verse document frequency as the piecewise word-document information (Equation 2). The PWI value estimates the information that Wij carries with regard to d, A high value indicates that wij is both frequent in de and strongly associated with d₁. In other words, wij is a keyword of dz.
D Id' d' E DA way d'
tf-idf (.y, d,) F(wiy de) log
(I)
frequeey
inveme dovument frequeacy
P(de Wey
P(wes (de)
log P(d.)
(2)
word gesemation probability
piecewise word information
PPW[(wyys ds)
Our method is developed upon the finding of [Chen et al. (2024): constituent structures can be predicted by searching for frequent substrings among semantically similar paraphrases. We extend their findings, interpreting the substring frequency statistic as a dominating term in our proposed substring-semantice information metric and applying to improve unsupervised PCFG training- As we will see in Section 5.2 our method significantly outperforms theirs in three out of the four languages tested.
PCFG is currently the state-of-the-art non-ensemble model for unsupervised constituency parsing (Liu et al. 2023; Yang et al.] 2021a). Previous research trains binary PCFG parsers on a text cor- pus by maximizing the average ILI of the corpus. PCFG is generative model defined by tuple (NT,T, T, R, S. x)) where NT is the set of non-terminal symbols, T is the set of terminal symbols, is the set of production rules, S is the start symbol, and æ is the probability distribution over the rules. The generation process starts with the start symbol S and iteratively applies non termermminll expansion rules (A - BC A. B, C' E NT) or terminal rewriting rules (A + A E NT, w T)) until it produces complete sentence x. We can represent the generation process with a tree-shaped struc- ture I. The PCFG assigns a probability for each distinct way of generating x; defining a distribution ((x, The
algorithm (Baker) 1979) provides an efficient solution for computing the total sentence probability P(x) -, P(x,, I). It constructs a B(ss A) table that records the total probability of generating a substring & of x from the non-terminal A. The sentence probability can be calculated as P(z)= = B(x, S). the probability of x being generated from the start symbol S. The 3(x, S) quantity is commonly referred to as Z (XX) (Eisner, 2016). Besides the total sentence proba- bility, the 3 table can also be used to calculate the span-posterior probability of being constituent
Eisner 2016) (Equation 3
a log Z(x) AENT alog 3(,, A)
P(s is a constituent)
(3)
Span-based TreeCRF model is widely adopted in constituency parsers (Kim et al.) 2019b Stern ee al. 2017). It models the parser distribution P(t]x), the probability of constituent structure i given x. It determines the probability of t by evaluating whether all substrings involved in the structure are constituents. It assigns a high score to substring in its potential function Φ(s,z) x)) if is likely a constituent and a low score 8 is unlikely a constituent. Subsequently, It can represent the parser distribution as P(t|z) x ILee Ø(s, In previous research, a(s. 2) has been parameterized differ- ently, such as using the span posterior probability for decoding (ø(s, P(s is constituent (z)) (Yang et al.) 202Tb) or using the exponentiated output from Long-Short Term Memory model (Ø(s, (0 x)
exp (LST s))) (im et al. 2019b).
We explain the derivation in more detail in Section A.2
3

---

Published as a conference paper at ICLR 2025
Bag-of-words Model
Paraphrasing
Sem(s)
Topic
Paraphrases
Document di
Bag-of-words representation for
subbit rspresentat Sem(
(a) Bag-of words model.
(b) Bag-of-Subsstings model.
Figure 2: Parallel structure between the traditional bag-of-worrd representation of topics and the
proposed bag-of- of-ssusttssnngs representation of semantics.
3. SEMINFO: A METRIC OF SEMANTIC INFORMATION ENCODED IN CONSTITUENT STRUCTURES
In this section, introduce estimation method of SemInfo, the semantic information encoded constituent structures. We first propose a bag-of-substrings model (Figure 2b). representing the semantics of sentence by examining how substrings in the sentence phrasing process. We assume the paraphrasing process is capable of generating natural language paraphrases (i.e., the paraphrases should both be acceptable natural language sentences and have similar semantics to the original sentence). We use instruction followiinnn large language models (LLMs) for the paraphrasing model, exploiting their outstanding zero-shot learning capability (Chia et al. 2023). Next, we apply the PWI metric (Aizawa 2003) to measure the substring-semantics semantics in- formation, utilizing the parallel structure between the bag-of-words model and our -fg-os-subssriinss model (Figure 2). Finally, estimate the SemInfo value for constituent structures by summing the substring-semant information associated with the structure.
regenerated during para-
3.1 DEFINING SUBSTRING- -EMANNIIC INFORMATION USING BAG-OF- SUN---R-IUSSSSNGS MODEL
Our -fgoss-uubsss model shares parallel structure with the traditional bag-of-words model. As discussed in S the bag-of-words model can model the word-topic information using the PWI metric. Exploiting the structural parallelism, we can apply the PWI metric our bag-of-substrings model to estimate the information between substrings and sentence semantics (Equation
The Sag-of-subsstrngg model is based on the paraphrasing model
shown Fig- 2b) The paraphrasing model takes source sentence as input, internally analyzes its semantics Sem(z), and generates paraphrase z". We can repeatedly sample from the process, collecting paraphrase set X² = {>f[.- ........ We define the lag-of-substring model by examining whether substring s of æ appears XP. We consider the appearance of in X² as heing generated by the -ubstrruusss model. The generation modeling establishes a relationship between the semantics Sem((x and substring s, which we will use to estimate the substring- semanti information.
The PWI metric requires two components to calculate the substring-semantic information: P(Sem(z)]s)
((s)Sem(z)). the substring generation probability, and log P(Sem(x)] the piecewise mutual in- formation between s and Sem(z). Similar the bag-of-words model, we will calculate the two components using the frequency of s in XP and the inverse frequency of in the corpus D.
P(Sem(())s)
(em)))(()) = P(s]Sem(z)) log P(Sem(z))
(4)
3.2 CALCULATING PWI USING MAXIMAL SUBSTRINGS
Naively measuring substring frequency among paraphrases X² will yield misleading estimate of ((s]Sem(z)) The reason that one substring can be nested in another substring. If a substring is generated to convey semantic information, will observe occurrence of along with an
4

---

Published as a conference paper at ICLR 2025
occurrence of all its substrings. Hence, the naive substring frequency will wrongly count substring occurrences caused by the generation of larger substrings as occurrences caused by P(s ({)(m)())) Let consider the example illustrated in Figure All three substrings in the example have frequency of 2, yet only the first substring carries significant semantic information. This is because the occurrence of the first substring causes the occurrence of the second and third substrings. The true frequency of the second and third substrings should be 0 instead of 2.
We introduce the notion of maximal substring to counter this problem. Given souree tence z and a paraphrase xº, the maximal sub- string between the two is defined in Equation Intuitively, maximal substring is the largest
John has been
Naive/Maximal Substring Frequency working theory: 2/2
Paraphrasing
working theory
John is working on a theory
substring that occurs in both z and zf. For- mally, denote the partial order relationship of string a being a substring in string by a S 3. and denote the set of maximal sub- strings by MS(x, >².). Using maximal sub- strings, we avoid over-counting substring occurrences caused by the generation of larger substrings.
working on: 2/0
John was working on theory
on a: 2/0
Figure 3: An example for naive substring fre- quency among paraphrases failing estimate P(s]Sem(z)).
MS(r,=)) aalaaaaaaaaaSS 2 Av'(as< = aa' {aك))
(S)
We are now ready to define P(s[Sem(z) using the paraphrasing distribution P(x (ee(()) and the notion of maximal substrings. We define P(s (e)(m))() to be proportional to s's probability of being generated maximal substring in paraphrases (Fquation (). The probability can then be approximated using the maximal substring frequency Fss, KP), shown in Equation
P(s]Sem(z)) x
E
1(s E MS(2..))
(6)
(em
= F(s,X")
(7)
Similarly, define the inverse document frequency for maximal substrings (Equation g) The inverse document frequency can serve as an estimate the piecewise substring-semantics informa- tion, quantifying how frequency implies that only a few Sem(z) zz) in the corpus generate as their maximal substring. In other words, we can easily identify the target semantics by examining whether appears as maximal substrings.
a substring is to convey semantic information. A high inverse document
P(Sem(())ss) se log log P(Sem(z))
D
(8)
[r' : E D AASE MS(r,I')
3.3 ESTIMATING SEMINFO
A constituent structure & can be represented as set of constituent substrings. We define SemInfo, the information between & and Sem(x), as the cumulative gubstring-semantcc information associated with (Equation D) We estimate the bubstring-semanties information with the maximal substring frequency-inverse document frequency developed the above section.
[t,, Sem(z)) = Σ ((s, Sem(z))
(9)
D F(s. X²) log 1 E DASE MS(x,
(10)
set
masimal substring fiquenog-inveee document frequency
4 SEMINFO MAXIMIZATION VIA TREECRF MODEL
We train our PCFG models on Equation 12 using the pipeline shown in Figure 4 The pipeline consists of three steps: (1) We compute the log( (xx)) by applying the inside algorithm on the PCFG model. This step yields the leading likelihodoo term in Equation [2 More im- portantly, it constructs the computation graph needed to calculate the
probabil- (2) We extract the span-posterior probability via back-propagating
ity P(s s constituentio).
5

---

Published as a conference paper at ICLR 2025
term
TreeCRF
Sentence
d(a) P(* constituent x)
Constituent
Computc (()):
REINFORCE J(
PCFG Model
lx)(2(x))
Figure 4: Pipeline of our SemInfo maximization training
log( [(x)) and parameterize TreeCRF model by setting 6(s. = [(s is constituentjz) (Equa- tion 11 This parametrization leads
distribution peR (t|z) that functions as an one-step Reinforcement Learning agent. (3) We train the PCFG model by applying the SemInfo maximization on PORF (t)z). This TreeCRF-based training method is equivalent to applying mean-field SemInfo maximization to the PCFG model. We choose the TreeCRF model because it enables efficient sam- pling from PCRF (4|x)) and entropy calculation for the distribution. As discussed in Appendix [A.] the TreeCRF-based training method performs equivalently applying SemInfo maxinization on the PCFG model directly. Yet, the TreeCRF-basee basee method runs 4x faster and uses the memory compared to the direct PCFG optimization method.
We apply the REINFORCE algorithm with average baseline (Williams 1992) ing. We include the maximum entropy regularization (Ziebart et al. (008)) and the traditional LLL term log (x) in the training. Notably, the LL term significantly stabilizes the training process. This stabilization effect may be related to the strong correlation between LL values and parsing accuracy at the early training stage, as discussed in Section 5.3.2
facilitate the train-
PCRF (f|x)
II
P(s is constituent)
set
aog ((x)
II NEA AENT bog ((s
Σ
(1I)
J(D) E [log ((x) aND
B t-pORf (1)a)
[log PCRF (em()))(
(12)
I(t,Sem(z)) + (H(())
5 EXPERIMENT
5.1 EXPERIMENT SETUP
We evaluate the effect of the SemInfo maximization objective on five latest PCFG variants: Neural- PCFG (NPCFG), Compound-PCFG (CPCFG) (Kim et al. 2019a). TNPCFG (Yng et al. 2021 Simple-NPCFG (SNPCFG), and Simple-CPCFG (SCPCFG) (Liu et al. 2023 F SNPCFG and SCPCFG represent the current state-of-the-art for non-ensemble unsupervised constituency pars- ing. We use 60 NTs for NPCFG and CPCFG, and 1024 NTs for TNPCFG, SNPCFG, and SCPCFG in our experiment. We conduct the evaluations in three datasets and four languages, namely Penn TreeBank (PTB) (Marcus et al. 1999) for English, Chinese Treebank 5.1 (CTB) (Palmer et al. 2005) for Chinese, and SPMRL (Seddah al. 2013) for German and French. We adopt the standard data split for the PTB dataset (Sections 02-21 for training, Section 22 for validation, and Section 23 for testing) Kim al. 2019a). We adopt the official data split for the CTB and SPMRL datasets.
Following Shen et al. (207)), we train the PCFG model on raw text without punctuations and eval- uate its parsing performance using the SF1 scores. When computing the SF1 score, we aggregate SF1 only for sentences longer than two words and drop trivial spans (i.e., sentence-level spans
"Our implementation is based the code of Yang et al. (021b) and
Liu et al. 2023

---

Published as a conference paper at ICLR 2025
English
Chinese
French
German
Seminto (Ours)
LL
SemInio
LL
Seminlo
LL
Seminfo
LLC
CPCFG
65.74.0.11
53.75
50.392as7
51,45
52.15.0.5
47.50
49.80
45 45.64a0.73
NPCRG
64.45-
50.964.132
53,30ga42
42.12-300
52.36.042
47.95gm0
50.74
45.85.045
SCPCEG
27.27
49,42-2.42
51.762054
46,20
22.7920.30
45.03
47.97
45.50
SNPCRG
67.15
58.1941.33
51.55
33.79
25.21
49.64
49.65
40.5
TNPCFG
66.55.0.96
53.37
a1.79
45.14:
54.11 m966
39.97
49.26
44.94
Average
+13.09
+6.02
+7.31
+4.92
MaxTreeDeooding
58,28
49.03
52.03
50.82
GPT4o-mini
36.16
11.82
30.01
33.56
Table 1: SF1 scores of five PCFG variants trained with SemInfo and LL. Each cell in the upper section reports the mean score and the standard deviation across three identical and indepen- dently trained PCFG models. Average A indicates average improvements in the training with SemInfo compared to LL. Improvements that are statistically significant (p < 0.05) highlighted in bold.
when
and spans with only one word). We use both the SF1 and SF1 scores to evaluate the correlation between the SemInfo value and parsing accuracy.
We use the gpt do-mini 2024 2024-07-222 07-18 model as our paraphrasing model and apply the same word normalization techniques as in Chen et al.) (2024) The average paraphrasing cost is about 5 USD using OpenAI's batch API. We use eight semantic- preemttcippeeervingg prompts for the paraphrasing model P We apply the snowball stemmer (Bird & Loper 2004) normalize the source sentence and its paraphrases before calculating the maximal substring frequency and the inverse document frequency. We apply the normaaaaazztinnn (Sparek Jones 1972) the maximal substring frequency to avoid some high-frequency substrings dominating the SemInfo value. The log- oog-normalization is compatible with the PWI framework, which treats the normalization as an optional step estimate S(m]Semm( In preliminary experiments, the log- nogronaaaiiation variant performs marginally but consistently better than the unnormalized variant.
5.2 SEMINFO MAXIMIZATION SIGNIFICANTLY IMPROVES PARSING ACCURACY
Table[[compare: SemInfo-trained PCFGs and LL-trained PCFGs on five contemporary PCFG vari- ants and four languages. For each variant, we independently train three PCFG models on the Sem- Info and LL objectives and report the mean and standard deviation of their scores. We can observe that most SemInfo-trained PCFGs achieve significantly higher parsing accuracy than their LL-trained counterparts. The average improvements are 13.09, 6.02. 7.31, and 4.92 SF1 scores in English, Chinese, French, and German, respectively. Two-tailed t-tests indicate the improvement to be statistically significant (p<0.05) in 17 out of 20 combinations. Two of the three insignificant results are due to the high score variance of the LL-trained PCFGs. The significant improvement demonstrates the benefit of the SemInfo maximization objective in the unsupervised constituency parsing task. The result also confirms the importance of semantic factors in identifying the syntactic constituent structure.
Table 1 also compares the SemInfo trained PCFG with two baseline parsers: Maximum Tree De- coding (MTD) parser, which predicts the structure with maximum SemInfo value, and GPT40-mini parser that asks the GPT4o-mini model to predict the structure in bracket form directly. Among the two baselines, we see that the MTD parser has significantly higher SF1 scores than the GPT40-mini parser across the four languages. The accuracy gap indicates that SemInfo is discovering non-trivial information about the constituent structure. Comparing the Seminfo-trained PCFG and the MTD parser, we that all Seminfo-trained PCFG variants outperform the MTD parser in English, Chi- nese, and French. The accuracy improvement indicates that the constituent information provided by the SemInfo value is noisy, and the grammar learns to mitigate the noises. We can again con- firm PCFG's 's de-noising effect in an experiment investigating how paraphrasing noise affects parsing performance (Appendix (..)..
In German, SemInfo-traiee that the German validation/testing set has significantly different word vocabulary compared to the training set, unlike the datasets in the other three languages. The out-of-vocabulary rate in the German dataset 14%, while the rate is 5%, 6%, and 7% in the English, Chinese, and French
PCFGs perform worse than the MTD parser. One possible reason is
Detailed prompts are listed in Section A.8
7

---

Published as a conference paper at ICLR 2025
8
Seminnto Rank
SemInfo-SFI'
LL-SFI'
SemInfo-LL
CPCFG
0.6518
0.0223
0.0196
-
NPCFG
0.6347
-0.0074
-0.0045
SCPCPG
0.6431
-0.0013
0.0505
SNPCEG
0,9289
0.0102
0.0182
SF1 Rank
SF1 Rank
TNPCFG
0.6449
0.1077
0.1426
Figure 5: Spearman rank analysis of (SemInfo, LL, SF1') pairs obtained from eight independently trained NPCFG models. The values are measured on two sentences in the English dataset. Please refer to Figure for more examples.
Table Spearman correlation coefficient among (SemInfo, LL., SF1*), and LL over the English validation set. Correlations are ag- gregated at the corpus-level.
datasets. This shift in word distribution might be significant factor in German PCFGs poor parsing accuracy.
5.3 SEMINFO STRONGLY CORRELATES WITH PARSING ACCURACY
In this section, we investigate how the SemInfo and LL functions contribute to obtaining high-quality PCFG parsers from two aspects: (1) Whether the function accurately evaluate the model's pre- diction (measured by SFI'). (2) Whether the function can approximately rank PCFG parsers in accordance with parsing performance (measured by SF1 Our experiments indicate that SemInfo can serve as an accurate estimate of parsing accuracy and that SemInfo is better training objec- tive for unsupervised parsers than LL. We evaluate the two aspects using the Spearman correlation Spearman 1904) between the SemInfo/L.L values and the SFI scoooss We refer to the cor- relation analysis using the SF1 score sentence-level analysis and the analysis using the SF1 score corpus-level analysis.
5.3.1 SEMINFO ESTIMATES PARSING ACCURACY
The sentence-level analysis assesses the SemInfo/LL's capability to evaluate the model prediction accurately. We independently train eight identical PCFG models using the LL maximization objec- tive. Each model is trained with a unique random seed for 30k steps. These eight models produce eight (SF1', SemInfo, LL) tuples for any given sentence, which we use to calculate the sentence- level Spearman correlation coefficient.
Figure illustrates the correlation gap between SemInfo-SF1' and LL-SF1' pairs using tences in the English validation set. Between the two sentences, the SemInfo-SFI pairs exhibit positive correlations while the LL-SFI' pairs exhibit no apparent correlations. Table 2 confirms the correlation gap using the correlation coefficient aggregated in the corpus level. We perform aggreggtinnnn using Fisher's Z transformation (Fisher 1915). The transformation converts the coefficient to a uni-variance distribution and reduces the negative impact of the aggregation caused by the coefficient's skewed distribution (Silver & Dunlap 1987). In the table, we observe that the aggregated coefficients for the SemInfo-SFII pairs range from 0.6-0.9, whereas the aggregated coef- ficients for the LL-SFI' correlation center around O. We can also consistently observe the correlation gap across multiple training stages, as further discussed in Appendix A.3] The consistent correlation gap, the hand, suggests that SemInfo serve and that SemInfo a better training objective for unsupervised parsers than LL. On the other hand, highlights SemInfo's s ability capture constituent information, reaffirming close relationship between constituent structure and sentence semantics.
accurate estimate of parsing accuracy
5.3.2 SEMINFO RANKS PCFG MODELS BETTER THAN LL
The corpus-level analysis evaluates the SemInfo/LL's capability to rank PCFG parsers by their pars- ing performance. We examine the correlation using model checkpoints collected over different training stages of the above eight PCFG models. Each stage is represented by a window over the amount of training steps. For example, stage [1k, 10k] contains checkpoints from Ik to 10k steps.
8

---

Published as a conference paper at ICLR 2025
English
Chinese
French
German
NPCFG (6ÜNT)
63.62 13.67
53.92
51.884.73
47.77
SCPCFG (1024NT)
66.92.0.6
52.26s0.1
52.29
45.32+0.67
SNPCEG (1024NT)
66 20.53
52.0420.93
54.3710.10
47.2710.16
Spanoverlap (Cen al. 2024
52.9
48.7
48.5
49.5
SCPCFG (2048NT)
2023
60.6
42,9
49.9
49.1
SNPCFG (4096NT) Liu et
2023
65.1
39.9
46.7
URNNG (Kim ct al.
2019b
40.7
29.1
NBI--PCFG Yang et al. 2021
60.4
S-DIORA [uu
1221
57.6
Constituency Test (Cao
2020
62.8
Table 3: SF1 English, Chinese, French, and German test sets. The top section shows the score for SemInfo-trained PCFGs while the bottom section shows the result from previous work.
These checkpoints produce set of (SF1 corpus-averaged SemInfo, corpus-averaged LL) tuples, which we use to calculate the corpus-level coefficient at that training stage.
Figure illustrates the SemInfo-SF1 and LL-SFI correlation curves for NPCFG We can observe that LL does have strong corpus-level correlation with SFI at the early stage of training despite having a cea--onn-eiisee sentence-leve correlation. How- ever, LL's coefficient quickly diminishes training progresses, dropping below 0.4 at the late training stage. This result indicates that LL identifies rea- sonable PCFG parser among a set of poorly perform- ing parsers in the carly training stage, explaining why the LL-ttrining can result in non-trivial PCFG parsers despite having negligible correlation in the sentence-level analysis. Yet, this ability quickly de- grades the training progresses. In comparison, SemInfo maintains strong correlation across the whole training process. which indicates SemInfo's s superior capability in ranking PCFG parsers by their performance.
0.8
spearman
0.6
0.4
SemInfo-SF1
LL-FF1
0.2
[1k. 10k]
[6k, 15k]
111k. 20k]
[16k. 25k)
121k, 30k
steps
Figure Spearman p with SF1 in different
training stages of NPCFG.
5.4 COMPARING WITH STATE- SAATE-OFTHEEARTTE
Comperes three SemInfo-trained PCFG variants with the state-of-the-art non-ensemble meth- ods for unsupervised constituency parsing. The Seminfo-trained PCFGs achieved state-of-the-ar level parsing accuracy in English, Chinese, and French, outperforming the second- besd-beettee algorithm by 1.82, 11.02, and 4.47 SF1 scores,,, respectively. The SemInfo-trained PCFGs, while using less than half the parameters, perform on par or significantly better than the larger SCPCFG and SNPCFG ported by [iu et al. (2023). The comparison showcases the strong parsing accuracy of the SemInfo- trained PCFGs, confirming the usefulness of semantic information in discovering the constituent structure.
compares
RELATED WORKS
Parsing with PCFG Unsupervised PCFG training is a long-established (Klein & Manning, 2002)
and state-of-the-ar (Liu et al.) 2023) approach for non-ensemble unsupervised constituency parsing. Much research has been dedicated to improving PCFG training from the model perspective, such scaling up the PCFG model (Yang et al. 2021b Liu al. 2023). integrating lexical information Yann et al. 2021a). and allowing PCFG rule probabilities to condition on sentence embeddings through variational inference (Kim al. 2019a). Our improvement from the model optimization perspective and can be combined with the above efforts. Our experiments validate the effectiveness
"We include the correlation for the other four PCFG variants in Appendix A.4

---

Published as a conference paper at ICLR 2025
of the SemInfo maximization objective in improving unlexicalized PCFGs. The SemInfo maximiza- tion objective is also applicable to lexicalized PCFGs, which we leave to future work.
Parsing with Semanties Zhao & Titov (2020) and Zhang al. 2021 have sought to improve PCFG training by learning to identify visual features, maximizing the association between con- stituent structures and these visual features. If we consider the visual features as semantic rep- resentations, their approach effectively maximizing the semantic information of the constituent structure. In comparison, our method shares the same underlying principle but represents the mantics with textual features. Our method leverages large language models as semantic processors, utilizing their outstanding semantic processing capabilities (Minaee et al. 2024). We believe that combining both textual and visual semantic representations presents significant research direction for unsupervised parsing tasks.
Improving Parsing with Ensemble Models Ensembling unsupervised parsers (Shayegh et al,, 2024) significantly improves aceuracy for unsupervised parsing by aggregating predictions from various base parsers. They show that those base parsers predict the constituent structure differently and utilize the difference to obtain a more accurate parsing result. Our method can be combined with the ensemble method for better parsing accuracy. We conduct parser agreement analysis in Appendix [A.6 to show the potential. The agreement analysis shows an agreement score of 80 among our Geminfo-trained PCFG parsers using various paraphrasing models. The agreement score similar to that of homogeneous parsers reported in Shayegh et al.) (024).. The analysis also shows that parsers have agreement score of 50 with other base parsers, similar to the reported score between heterogeneous parsers. The similarity in agreement score suggests that our parsers should be able serve useful component in the ensemble method.
7 CONCLUSION
In this paper, we proposed and validated SemInfo maximization as a novel objective for unsuper- vised constituency parsing. We developed bag-of-substrings model represent the sentence semantics and applied the probability-weighte information metric to estimate the SemInfo. We applied the SemInfo maximization objective to training PCFG parsers. Experiments showed that SemInfo has a strong sentence-level correlation with parsing accuracy and that SemInfo maintains consistent corpus-level correlation throughout the PCFG training process. These correlation analy- ses indicate that SemInfo is an accurate estimate of parsing accuracy and that it is reliable training objective for unsupervised parsers. As result, SemInfo-trained PCFGs significantly outperformed LL-trained PCFGs across four languages, achieving state-of-the-art level performance in three of them. Our findings highlight the effectiveness of leveraging semantic information in unsupervised constituency parsing, paving the way for semanticallyinfommee informed unsupervised parsing methods.
REPRODUCIBILITY
We provide detailed explanation of our method in Sections and We outline further im- plementation details, such the data source, model architecture, and pyper-parameter settings, in Section 5.1 We release the source code at httpss/gittbb.com/ujjiccehn cttp:iiiccheeeiiiiiimoorriggg Semantie- Somantie-Inoommatinnggil
ACKNOWLEDGMENT
This research was funded by the Japan Society for the Promotion of Science through the Research Fellowships for Young Scientists (Grant No. JP23KJ0565) and by the KAKEN project (Grant No. 24H00087). We sincerely thank them for their financial support of the research. We also appreciate the reviewer's thorough evaluation and valuable suggestions during the review process.
REFERENCES
Akiko Aizawa. An information-theereet perspective of if-idf measures. Information Pro- cessing & Management, 39(1):45-65, January 2003. ISSN 03064573. doi: 10.1016/
10

---

Published as a conference paper at ICLR 2025
50306-4573(020000222 pL1/803041573200222
URL
J. K. Baker. Trainable grammars for speech recognition. The Journal of the Acoustical Soci- ery of America, (5($1):S132-5 -132, June 1979. ISSN 0001-4966, 1520-8524, doi: 10.1121/ 1.2017061. URL http://s..ppaaa...ooooo//aaa///a trainable e grammars w-r--foo-------ee
Steven Bird and Edward Loper. NLTK: The natural language toolkit. In Proceedings of the ACL Interactive Poster and Demonstration Sessions, pp. 214-217, Barcelona, Spain, July 2004. URL
303-3031
Steven Cao, Nikita Kitaev, and Dan Klein. Unsupervised parsing via constituency tests. In Bonnie Webber, Trevor Cohn, Yulan He, and Yang Liu (eds.), Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 4798-4808, Online, Novem- ber 2020. Association for Computational I Linguistics. doi: 10. https////1122000mm//mmmma...... URL htt.:httts/cccllloo antho o 2020 emnlp-ma n. 389
Andrew Carnie. Syntax: a generative introduction. Introducing linguistics. Blackwell Pub, Malden, MA, 2nd ed edition, 2007. ISBN
Glenn Carroll and Eugene Chamiik. Two experiments on learning probabilistic dependency gram- mars from corpora. Technical report, Brown University, USA, 1992.
Junjie Chen, Xiangheng He, and Yusuke Miyao. Modeling syntactic- syntactic-semantic dependency corre- lations in semantic role labeling using mixture models. In Smaranda Muresan, Preslav Nakov, and Aline Villavicencio (eds.), Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 7959-7969, Dublin, Ireland, May URL
2022. Association for Computational Linguistics. doi: 18.18/ 1/20222acl-ooooo.....oom ht Mttps::/aclanthooooo wrg. 201.//2222.221100 548
Junjie Chen, Xiangheng He, Danushka Bollegala, and Yusuke Miyao. Unsupervised parsing by searching for frequent word sequences among sentences with equivalent predicate-argument structures. In Lun-Wei Ku, Andre Martins, and Vivek Srikumar (eds.), Findings of the Association for Computational Linguistics ACL 2024, pp- 3760-3772, Bangkok, Thailand and virtual meeting, August 2024. Association for Computational Linguisties. URL rttps://aclanthon org/2024, 2024. findings ac1.225
Yew Ken Chia, Pengfei Hong. Lidong Bing, and Soujanya Poria. INSTRUCTEVAL: towards holis- tic evaluation of instruction-tunet large language models. CoRR, abs/2306.04757, 2023, doi: 10. 3S350/ARXIVV2330..47755
htth:tss::///// http::://ooooooooo..
48550/ www.v.iiivv.... www.wwwwwwww........ 04757
Shay Cohen, Kevin Gimpel, and Noah Smith. Logistic normal priors for unsupervised prob- abilistic grammar induction. In D. Koller, D. Schuurmans, Y. Bengio, and L. Bottou (eds.), Advances in Neural Information Processing Systems, volume 21. Curran Associates, Inc., 2008. URL https::/pprcceedinggs www.ine.uuucc...oo new.resssc cwpppper.eppppppeeeeppeeeeee...p fi www.fieepppppeeee /tllee//pppe/000// file/ fi htt.///eeee1110000///66666553333 Paw.ro.--pppppppp pcff
Chris Dyer, Adhigunaa Kuncoro, Miguel Ballesteros, and Noah A. Smith. Recurrent neural network grammars. In Kevin Knight, Ani Nenkova, and Owen Rambow (eds.), Proceedings of the 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp. 199-209, San Diego, California, June 2016. doi: 10.18653/
MIN16-10244 URI. 6- 1024
Jason Eisner. Inside-outside and Barward-backaand algorithms are just backprop (tutorial paper). In Kai-Wei Chang, Ming-Wei Chang, Alexander Rush, and Vivek Srikumar (eds.), Proceedings of the Workshop on Structured Prediction for NLP, pp. 1-17, Austin, TX. November 2016. doi: 11863//1//1165000
URL W16 5901
R. A. Fisher. Frequency distribution of the values of the correlation coefficient in samples from an indefinitely large population. Biometrika, 10(4):507, May 1915. ISSN 00063444. doi: 10.2307/ 2331838. URL /htttt:tpss.............tp..t... ://www//wwww jstor wtw.:

---

Published as a conference paper at ICLR 2025
Qi He, Han Wang, and Yue Zhang. Enhancing generalization in natural language inference by syntax. In Trevor Cohn, Yulan He, and Yang Liu (eds.), Findings of the Association for Com- putatiional Linguisties: EMNLP 2020, pp. 4973-4978, Online, November 2020. Association for Computational Linguistics. doi: 10.18633/ 121//33/1/220..11m htw.:///00..nninnnnnnn.......... findiiiingiine findingsnnnnnnneenne .4.
URL. https:
Irene Heim and Angelika Kratzer. Semantics in generative grammar. Blackwell textbooks in lin- guistics. Blackwell, Malden, MA, 1998. ISBN 9780631197126.
Mark Johnson, Thomas Griffiths, and Sharon Goldwater. Bayesian inference for PCFGs via Markov chain Monte Carlo. In Candace Sidner, Tanja Schultz, Matthew Stone, and ChengXiang Zhai
(eds.), Human Language Technologies 2007: The Conference of the North American Chapter of the Association for Computational Linguistics; Proceedings of the Main Conference, pp. 139- 146, Rochester, New York, April 2007. UCL-N07-00
Yoon Kim, Chris Dyer, and Alexander Rush. Compound probabilistic context-free grammars for grammar induction. In Anna Korhonen, David Traum, and Lluís Märquez (eds.). Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pp. 2369-2385,
Florence, Italy, July 2019a. doi: 10.18653/11/19- 1228. URI 1228
Yoon Kim, Alexander Rush, Lei Yu, Adhigunaa Kuncoro, Chris Dyer, and Gábor Melis. Unsuper- vised recurrent neural network grammars. In Jill Burstein, Christy Doran, and Thamar Solorio (eds.), Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguisties: Human Language Technologies, Volume I (Long and Short Pa- pers), pp. 1105-1117, Minneapolis, Minnesota, June 2019b. doi: 00.1853//1/N19-111 URL
Dan Klein and Christopher D. Manning. A generative constiuentt-conexx model for improved gram- mar induction. In Pierre Isabelle, Eugene Charniak, and Dekang Lin (eds.). Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics, pp. 135, Philadel- phia, Pennsylvania, USA, July 2002. doi: 10.31 1..3115/173003310077 106. URL P02-1017
Juanzi Li, Qi' na Fan, and Kuo Zhang. Keyword extraction based tf/idf for chinese news doc- ument. Wuhaan University Journal of Natural Sciences, 177799117- September 2007. ISSN 1007-1202, 1993-4998 doi: 10.1007/s11850 1870-900700008-44 com
URL http::ttp:/nnittt itgp///nnr.................
Wei Liu, Songlin Yang, Yoon Kim, and Kewei Tu. Simple hardware-efficiee PCFGs with indepen- dent left and right productions. In Houda Bouamor, Juan Pino, and Kalika Bali (eds.), Findings of the Association for Computational Linguisties: EMNIPP 2023, pp. 1662-1669, Singapore, De- cember 2023, Association for Computational Linguistics. doi: 10. 18.138 htt.://........neeemmm.mmm 113. Uttpsttss:///ccaattttt
org 202// 2ttp://222....nnn... findingsiinn. emnlp. 113
Mitchell P. Marcus, Beatrice Santorini, Mary Ann Marcinkiewicz, and Ann Taylor. Treebank-3, 1999. URL
ldc. upenn. wtt.://..ueee...eeeeeeee.e.
Shervin Minaee, Tom Mikolov, Narjes Nikzad, Meysam Asgari Chenaghlu, Richard Socher, Xavier Amatriain, and Jianfeng Gao. Large language models: A survey. ArXiv, abs/2402.061966 2024.
URL https::///// //api.:://.p.... www.ntiisscchttoo ar www.orr///rrrsslooooo 676770322
Apra Mishra and Santosh Vishwakarma. Analysis of tf-idf model and its variant for document retrieval. In 2015 international conference on computational intelligence and communication networks (cien), pp. 772-776. IEEE, 2015.
Martha Palmer, Fu-Dong Chiou, Nianwen Xue, and Tsan- Lee. Chinese treebank 5.0, January 2005. URL /RL/stttss//caaaalgg www. www.ataa..............e.mmmmm wpw.. httpa//l......uuuueeeeeeee/////o
Carl Jesse Pollard and Ivan A. Sag. Information- based syntax and semantics. CSLI lecture notes. Center for the Study of Language and Information, Stanford, CA. 1987. ISBN 9780937073230.
John Schulman, Philipp Moritz, Sergey Levine, Michael I. Jordan, and Pieter Abbeel. High- dimensional continuous control using generalized advantage estimation. In Yoshua Bengio and Yann LeCun (eds.), 4th International Conference Learning Representations, ICLR 2016,
12

---

Published as a conference paper at ICLR 2025
San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings, 2016. URL http:
// //arxiv.org/////oo. awaaaaaa5555 02438
Djamé Seddah, Reut Tsarfaty, Sandra Kübler, Marie Candito, Jinho D. Choi, Richárd Farkas, Jen- nifer Foster, lakes Goenaga, Koldo Gojenola Galletebeitia, Yoav Goldberg, Spence Green, Nizar Habash, Marco Kuhlmann, Wolfgang Maier, Joakim Nivre, Adam Przepiórkowski, Ryan Roth, Wolfgang Seeker, Yannick Versley, Veronika Vineze, Marein Wolinski, Alina Wróblewska, and Eric Villemonte de la Clergerie. Overview of the SPMRL 2013 shared task: A cross-framewee evaluation of parsing morphologically rich languages. In Yoav Goldberg, Yuval Marton, Ines Re- hbein, and Yannick Versley (eds.), Proceedings of the Fourth Workshop Statistical Parsing of Morphologically- Rich Languages, pp. 146-182, Seattle, Washington, USA, October 2013. URL
W13-4917
Behzad Shayegh, Yanshuai Cao, Xiaodan Zhu, Jackie C. Cheung, and Lili Mou. Ensemble distillation for unsupervised constituency parsing. In The Twelfth International Conference on Learning Reprexentations, ICLR 2024, Vienna, Austria, May 7-11, 2024. OpenReview.net, 2024.
URL WRKLittpps///peeeeeviee net/ Eorum (oorumm21d=RRByOWWEET
Yikang Shen, Zhouhan Lin, Chin-Wei Huang, and Aaron C. Courville. Neural language modeling by jointly learning syntax and lexicon. ArXiv, abs/1711.00011,, 2017. URL https://apl.
semanticscholar
3347806
N. Clayton Silver and William P. Dunlap. Averaging correlation coefficients: Should fisher's z transformation be used? Journal of Applied Psychology, 72(1):146-148, February 1987. ISSN doi: 10.
1939-1854, 0021-9010.
URL http:://di..ap
getdoi (at.:oi..cfmdoo--110. 1037 0001 9010.0000000 72.
Karen Sparck Jones. A statistical interpretation of term specificity and its application in re- trieval. Journal of Documentation, 28(1):11-21, January 1972. ISSN 0022-0418. doi:
10.1108/eb026526. URL BRL/https:// /ttp:::://wwww..////.. www..ww.oo emerald. wtt.///iiigggtctteee///oo/ 1108/eb02656/ftl
C. Spearman. The proof and measurement of association between two things. The American Journal
of Psychology, 15(1):72, January 1904. ISSN 00029556. doi: 10.2307/1412159, URL https:
// /www. jstor wtt.ooo.......tto.e//aaa/////nnr
Valentin I. Spitkovsky, Hiyan Alshawi, Daniel Jurafsky, and Christopher D. Manning, Viterbi train- ing improves unsupervised dependency parsing. In Mirella Lapata and Anoop Sarkar (eds.), Proceedings of the Fourteenth Conference on Computational Natural Language Learning, pp- 9-17, Uppsala, Sweden, July 2010. URL W10-2902
Mark Steedman. The syntactic process. Language, speech, and communication. MIT Press, Cam- bridge, Mass, 2000. ISBN 9780262194204.
Mitchell Stern, Jacob Andreas, and Dan Klein. minimal span-based neural constituency parser. In Regina Barzilay and Min-Yen Kan (eds.), Proceedings of the 55th Annual Meeting of the Association for Computational Linguisties (Volume 1: Long Papers), pp. 818-827, Vancouver. Canada, July 2017. doi: 10.18653/v1/11-1000 FRT
Ronald Williams. Simple statistical gradient-following algorithms for connectionistrrenforreeee learning. Mach. Learn., 8:229 256, 1992. doi: 10. 10.1007/BF009992666. URL https::/doi. org 10. 20.1007/BF009330
Pengtao Xie and Eric Xing. A constituent-centrcc neural architecture for reading comprehension. In Regina Barzilay and Min-Yen Kan (eds.), Proceedings of the 55th Annual Meeting of the Association for Compulational Linguistics (Volume 1: Long Papers), pp. 1405-1414, Vancouver. Canada, July 2017. doi: 10.18653/v1/117- 1129. URL P17-1129
Zhiyang Xu, Andrew Drozdov, Jay Yoon Lee, Tim O'Gorman, Subendhu Rongali, Dylan Finkbeiner, Shilpa Suresh, Mohit lyyer, and Andrew McCallum. Improved latent tree induc- tion with distant supervision via span constraints. In Marie- Francine Moens, Xuanjing Huang, Lucia Specia, and Scott Wen-tau Yih (eds.), Proceedings of the 2021 Conference on Empirical
13

---

Published as a conference paper at ICLR 2025
Methods in Natural Language Processing, pp. 4818 4831, Online and Punta Cana, Dominican Republic, November 2021. Association for Computational Linguistics. doi: 10.18653/1/2021. emnlp- m9i..39.. URL RRLLAttps///ccaamaoolooo
org/2021 www.p-mmannnneeee 395
Songlin Yang, Yanpeng Zhao, and Kewei Tu. Neural bi-lexicalized PCFG induction. In Chengqing Zong, Fei Xia, Wenjie Li, and Roberto Navigli (eds.), Proceedings of the 59th Anmual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing ( (Volume 1: Long Papers), pp. 2688-20088 2699, Online, August 2021a. Association for Computational I Linguistics. doi: 10. 18653/v1/2021 acl-lcng.2000) 209.
URL https:
//aclanthologe 2ttg aww.llalllog....
Songlin Yang, Yanpeng Zhao, and Kewei Tu. PCFGs do better: Inducing probabilistic context- free grammars with many symbols. In Kristina Toutanova, Anna Rumshisky, Luke Zettlemoyer, Dilek Hakkani-Tur, Iz Beltagy, Steven Bethard, Ryan Cotterell, Tanmoy Chakraborty, and Yichao Zhou (eds.), Proceedings of the 2021 Conference of the North American Chapter of the Asso- ciation for Computational Linguistics: Human Language Technologies, pp. 1487-1498, Online, June 2021b. Association for Computational Linguistics. doi: 10.18653/v 1/202 1aa.lll.aaammmmmma mnaccl-main.
URL https: stttps//aclaathooopgeooooooo orgg..rgg///.. 2021 naacl main. 117
Songyang Zhang, Linfeng Song, Lifeng Jin, Kun Xu, Dong Yu, and Jiebo Luo. Video-aided unsu- pervised grammar induction. In Kristina Toutanova, Anna Rumshisky, Luke Zettlemoyer, Dilek Hakkani-Tur, Tur, Iz Beltagy, Steven Bethard, Ryan Cotterell, Tanmoy Chakraborty, and Yichao Zhou (eds.), Proceedingy of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp. 1513-1524, Online, June 2021. Association for Computational Linguistics. doi: 10.18653/v1/20 1/252/ 1aaallnaacl--ao maincl-main. 119. URL http:://wwcaaatttooo.o.ooooo////
orgpyoorgg22211 waw.:o/g./....llllleee.......... naacl-ma in. 119
Yanpeng Zhao and Ivan Titov. Visually grounded compound PCFGs. In Bonnie Webber, Trevor Cohn, Yulan He, and Yang Liu (eds.). Proceedings of the 2020 Conference on Empirical Methods
in Natural Language Processing (EMNLP), pp. wttp/////222o.oom maa20-mmmlp-m ation for Computational Linguistics. doi: 8653/v
Online, November 2020. Associ-
URL https:
Facclanthology.oree org/2020 emn p- m in..inn... 354
Brian D. Ziebart, Andrew L. Maas, J. Andrew Bagnell, and Anind K. Dey. Maximum entropy inverse reinforcement learning. In AAAI Conference on Artificial Intelligence, 2008. URL https:
/ //api. semant cachol a hrtaacoooaa.rrr//oopssss:::::::
14

---

Published as a conference paper at ICLR 2025
Strategy
RL. Baseline
Sampling distribution
Learning Strategy
Action-V V
V-function
Action distribution
SemInfo maximization
Posterior- V
V-function
Tree posterior distribution
SemInfo maximization
Posterior-Avg
Sample average
Tree posterior distribution
SemInfo maximization
Supervised
Supervised learning
L.L
Likelihood maximization
Table Lookup table for optimization strategies and detailed descriptions
Algorithm TreeCRF Sampler
I: function CRF-Sampler(i, J,
2: j = ? then
Return leaf node (i.j)
4: else
5: Sample split index k ~ T (I: (i,j)) following Equation 14 Johnson et al.
2007
6: Than f- CCRF-Sampler(i.cc 2))
Taght CRF-Sampler(ke j,
Return node (i. with children Tin Tigl
9: end
10: end function
A APPENDIX
A.1 ADVANCED SEMINFO MAXIMIZATION
In Section 4 we presented SemInfo maximization method that performs mean-field optimization through a TreeCRF model. This method parameterizes a TreeCRF model using the span-poster posterioo probability and maximizes the expected SemInfo value of the TreeCRF distribution. While study demonstrated significant accuracy improvement by the TreeCRF-based SemInfo maximiza- tion training, it raises through the TreeCRF model compared to optimizing those parameters directly? In the experiment presented in this section, found no significant difference between the TreeCRF-based and PCFG- based optimizations. It shows that the demonstrated accuracy improvement does not depend on par- ticular optimization methods, highlighting the contribution of the SemInfo maximization objective to accurate unsupervised parsing. In addition, we found that the TreeCRF-based optimization is more time and space-efficient than the PCFG-based optimization, which makes the TreeCRF-based optimization preferable.
question: What is the advantage of optimizing the PCFG parameters
As shown Table 4 we compare three SemInfo maximization strategies combined with two op- timization methods (TreeCRF-based and PCFG-based methods). We include an LL-trained parser and supervised parser as baselines. The two baselines serve as the lower and upper bounds for comparison, respectively.
A.1.1 TREE POSTERIOR AND SAMPLING DISTRIBUTIONS
Both the TreeCRF-based and PCFG-based optimizations aim maximize the expected SemInfo with on-policy Reinforcement Learning (RL., but they operate on two policy distributions: the TreeCRF-based posterior distribution pCRF (t|zr) (Equation 11 and the PCFG-based posterior dis- tribution PrcF& (t)22) (Equation (3). Sampling from both distributions involves multiple span- splitting steps (Algorithm for the TreeCRF model and Algorithm 2 for the PCFG model). The sampler starts with the sentence-level span ((1,n) for the TreeCRF model; (S, 1, for the PCFG model) and recursively makes splitting decisions (ii,) + (i, (k:,) for the TreeCRF model: (A, (B, i, (C, j) for the PCFG model). The sampler repeats this span-splitting process until it reaches single-word spans (j = 1).
pPCFO
(lx,t)
(13)
Σ, P(x,t)
15

---

Published as a conference paper at ICLR 2025
Algorithm 2 PCFG Sampler
1: function PCFG-Sampler(4,, a)
2:
j = 1 then
3: Return leaf node (A, i,
5: Sample split index B, C, ~ PCFG C, (A, following Equation
6: Tha f PCFG-Sammlllr
k.)
7: Trght PCFG-Sampler(( j.
8: Return node () with children Tich and right
end
10: end function
expl E ((,A)) log P(s is a const./2) + E (k(,) log P(s is a const.(z))
CRR (R((()()
(14)
Σ, exp( (e(()))) log ((s is const. 2:) Σ E.s(..)) log P(s is const.
PCPG (B, (,(,,,)) P(A - (C))(BB,,
(15)
((,,
A. A.1.2 THREE SEMINFO MAXIMIZATION STRATEGIES
In this subsection, introduce two RL optimization methods: posterior and action optimizations. We further combine the optimization methods with two RL baseline estimations: average baseline and V-function baselines. Since the average baseline cannot be applied the action optimization, the combination of the optimizations and baselines gives three optimization strategies (Table
The posterior optimization similar to the method explained in the main text: (1) sampling tree from either pC (t|z) or PPCFF (f|ær); and (2) perform policy gradient optimization in accordance with Equation 12 In contrast, the action optimization considers the tree sampling process as an RL trajectory and applies the SemInfo maximization through π CC or π PCFG The two optimizations differ in how the RL agent is defined. The posterior optimization defines the RL agent as a one- step agent and seeks to maximize the SemInfo values for the parser-predicted trees. The action optimization defines the agent as span-splitting agent and seeks to maximize the SemInfo for the tree resulting from the span-splitting decision.
A.1.3 V-FUNCTION COMPUTATION
In the PCFG setting, the V-function can be computed precisely and efficiently using dynamic pro- gramming. The V-function estimates the expected return of visiting a state s (s (i,j) for the TreeCRF model and (A, i. for the PCFG model) using policy π (Equation 16 It enables the estimation of the advantage function A(s, a), which evaluates how effective a is in maximiz- ing the SemInfo value of the sampled tree (Equation 17). Algorithm and Algorithm details the V V-function computation for both the TreeCRF and PCFG-based optimizations. The two algorithms
share the same backbone but differ in the span-splitiing agent
V(s)=
Σ r(st, a:)
(16)
(s0.00.e1 Jour
(a..00)
A(s,a) = r(( V(8') V(s)
(17)
A.1.4 TREECRF-BASEE OPTIMIZATIONS
(restatement of Equation 12 19 and 20 details the training objective for the TreeCRF- based Posterior- Posterior-V V, and Action- V strategies, respectively. Comparing Equation I8 and Equation 19 the Posterior-V V improves over the Posterior-Avg by substituting the sample-average baseline with the V-function baseline. Our preliminary experiments indicate that the substitution results in faster convergence and slightly higher parsing accuracy. The Action-V strategy directly
Equation 18
16

---

Published as a conference paper at ICLR 2025
Algorithm 3 TreeCRF-based V-Function Computation
Require: Subtree-sclection agent CC (i,j) governing all possible split decisions of span (4,5)
(k.
Require: SemInfo function r(i.j) = [(zuj, ((
Ensure: V(t,j) for all spans.
I: Initialize ji, for all spans (i,
w
3: repeat
4: for each span of length w do
w =
V(8)
r(i,j)
w = 2
(FC (V(i,) v(k,))) +r(1,))
w >
6: end for
w 4-
8: until w = n
9:
return V
Algorithm PCFG-based V-Function Computation
Require: Subtrce-sclection agent π PCFG (A,i, governing all possible split decisions of span (A, i, + (B, i, i,C) j)
Require: SemInfo function r(A, [[rej, Sem(z)).
Ensure: V,
I: Initialize V(A,i,j) = 0 for all (A,
2: 2-2
3: repeat
each span length
5: V(s) r(A,
6: end for
7:
4- +
8: until
return
optimizes n CRE using the advantage function A, which we further augment with the Generalized
Advantage Estimation Schulman al. (0116).
J(D) EE log 7(z) +
E
log PCRF (e)())))
PNPR (e)x)
(18)
E pCRF (M|x)
T(t,Sem(z)) + (H
J(D) = Dog 7(z) +
Dlog PCRF Sem(())
PF (1]=)
(19)
Va(1,n) 3H((P (1[=))]]
J(D) = E [log 2(x) +
E
log ग ORF (A(..))
anD
((..). ORF
(k.5).
(20)
+ ( CRF (MI)))
A.1.5 PCFG-BASED OPTIMIZATIONS
Equation 21 22 and 23 details the training objective for the PCFG-based Posterior-Avg Posterior- V, and Action- strategies, respectively. These strategies are defined similarly to the TreeCRF-base strategies but replace the TreeCRF-base distributions with the PCFG-based distributions.
17

---

Published as a conference paper at ICLR 2025
NPCFG
SNPCRG
TreeCKF
PCPG
TreeCRF
PCFG
Action-V V
65.16.1.15
62.66#1.76
67.2120.33
66.0420.38
Posterior-
66.82+0.32
66.37+1.71
67.8720.54
66.3221.39
Posterior-Avg
65.55=0.75
6..64+1.34
66.77=0.14
66.85=0.32
Supervised 69.0520,55
73.5420.11
71.8320.21
74.78=0.23
LL
53.3440.59
57,8442.61
Table 5: SF1 scores of two PCFG variants trained combined with three SemInfo maximization strategies. We retrained the TreeCRF-based Posterior-Avg model and the LL model in this experi- ment.
J(D)=
E I>D
blog 7(z) +
T ([))
log PPCFo (1t)
(21)
(PCF Set,Sem(z)))]]
J(D) B [log (2)) +
E
(log p PCFG ((e))(() (a.)),,,
(22)
anD
J(D) E [log ((x) +
E (B...). PerFe
ZND
Σ
log PCFG (B.CCAAA
(23)
(A
A.1.6 RESULT
Table 5 evaluates the TreeCRF and PCFG-based optimization methods using two PCFG variants. Both methods yield parsers similar performance. The TreeCRF-basee method yields higher mean parsing accuracy than the PCFG-based method, yet the difference is within the margin of error. All combinations yield parsers with 65 67SF1 scores, except for the NPCFG+Action BEEFG*AAttoo-V-PPCG--bbb V+PCFG-based optimization combination. This combination results in parsers with 62.66 mean SF1 score, mas- sively underperforming other combinations. The underperformance might be related to the low model capacity of the PCFG model, we did not observe similar performance degradation in the SNPCFG model and other high-capacity models tested in our preliminary experiment, Overall, the comparison disentangled the high accuracy of the SemInfo-trained PCFGs from specific optimiza- tion algorithms. It highlights the contribution of the SemInfo maximization objective to accurate unsupervised parsing.
In comparison with the supervised baseline, all combinations yield parsers with accuracy within SF1 scores from the supervised baseline. The small gap, on the one hand, showcases the strong performance of the model might limit further development of semantic-aware unsupervised parsers. more expressive parsing model (e.g., the Recurrent Neural Network Model D et al. (2016) might be necessary in future studies.
comInfo-trrined PCFG parsers. On the other hand, it indicates that the PCFG
While the TreeCRF-based and PCFG-based methods yield parsers of similar accuracies, found the TreeCRF-based optimization more time and space-efficient than the PCFG-based optimization. The TreeCRF-base optimization trains NPCFG parsers at 4x the speed and uses only à the memory. also trains SNPCFG parsers 8x the speed and uses the memory. The improved training efficiency enables the further scaling of the PCFG model.
A.2 COMPUTING SPAN-POSTERIOR PROBABILITY VIA BACK-PROPAGATION
This section explains how the span- apan-posterior probability ((s a constituent].)) is computed using back- prok-propagttion.
1og ((x)
P(s constituent]
(24)
Oog (s, A)
AENT
18

---

Published as a conference paper at ICLR 2025
CPCFG
NPCFG
SNPCFG
0.6
0.6
1.0
Spearman
Spearman
Spearman
0.4
0.4
0.5
0.2
0.2
0.0
0.0
0.0
10000
20000
30000
10000
20000
30000
10000
20000 steps
30000
steps
steps
SCPCFG
TNPCFG
Spearman p
0.6
0.6
mpeaman
0.4
0.4
(Seminfo, SF1
(LL, SF1
0.2
0.2
0.0
10000
20000
30000
10000
20000
30000
steps
steps
Figure 7: Sentence-level Spearman correlations for models trained for 10k steps, 20k steps, and 30k steps.
Proof. Firstly, we define the span-posterior probability as Equation 25 Here is a substring of r, spanning from the i-th word to the j-th word (i.e., = (I,,..,, I.)). Intuitively, 8 is a constituent there exists non-terminal A that expands into
P(s is constituent|z) = ExENT P(S + +
(25)
P(x)
We split P(S ~ 8i.s) into two parts in Equation 26
P(S 31, Xi-1, A, +1
the probability of generating words outside 8, and P(A 8), the probability generating words
inside The outside probability can be computed using pack-propagation (Eisner) (016). The
inside probability is already computed by the 3 table. Exploiting algebraic translormations shown in Equation 28 we can derive the formula shown Equation 24
((s is a constituent x:)
Σ AENT
P(S - I1, 21-1, 3,11 .P((A - 8)
(26)
((x)
Σ 0Z(x)
((s
(27)
((x)
05(s, A)
AENT
Σ (zx) θ log ((x)
1
Ölog B(s, A) B(s, A) B(s, A)
(28)
(xx)
AENT
Olg (X)
Σ AENT
(29)
Olog B A)
A.3 SENTENCE-LEVEL CORRELATION IN DIFFERENT TRAINING STAGES
In Table 2 we showed a strong sentence-level correlation between SemInfo and SF1' but a weak correlation between LL and SF1'. Nevertheless, it remains unclear whether the correlation gap is related to the number of training steps Figure excludes the number of training steps as a factor in the correlation gap. In this experiment, we calculate the correlation coefficient for models trained for 10k steps, 20k steps, and 30k steps. We can observe that, for all PCFG variants, the correlation coefficients for (SemInfo, SF1') are consistently over 0.6, while the coefficients for (LL, SF1') are consistently below 0.1. This result underscores our conclusion that SemInfo can serve as an accurate estimate of parsing accuracy.
19

---

Published as a conference paper at ICLR 2025
Seminfo Rank
Seminfo Rank
LL Rank
Rank
LL Rank
Seminfo
4-
2-
2
4
SF1' Rank
SF1 Rank
SF1 Rank
8
8
8
8
8
8
Seminfo Rank
Seminfo Rank
Seminfo Rank
6
Rank
6
6
Rank
4
4-
4
2
4
8
SF1'
Rank
SF1
Figure 8: Sentence-level correlation on six random sentences.
CPCFG
NPCFG
SCPCFG
Spearman
0.8
Spearman
0.5
0.4
0.25
0.0
[1k. 10k] [11k, 20k][2kk, 30k]
[1k, 10k] [11k, 20k] 30k]
[1k,
10k] [11k, 20k] (21K, 30k] steps
steps
steps
SNPCFG
TNPCFG
1.0
Spearman
0.75
0.5
Seminfo-SF1-
0.50
LL-SF1
0.0
0.25
[1k. 10k] [11k, [2k] 30k]
[1k, 10k] [L1k. 20k] 30k]
steps
steps
Figure 9: Corpus-level Spearman correlation different training stages.
A.4 MORE DETAILED ANALYSIS FOR CORPUS-LEVED CORRELATION
Figure shows the corpus-level correlation in different training stages for all five PCFG variants. We observe the same phenomenon explained in Section [5..2 for CPCFG, NPCFG, SNPCFG, and TNPCFG. The correlation coefficients for (SemInfo, SF1 " consistently above 0.75, whereas the coefficients for (LL., SF1)) drop quickly as the training progresses. We can observe the stronger correlation between SemInfo and SFI in Figure 10 The figure plots the training curves of the corpus-level SFI score, the average SemInfo value, and the average LL value over the English validation set. For example,
see that SemInfo ranks the NPCFG models represented by the green and grey lines as the lowest and those represented by the purple and blue lines as the highest. This largely agrees with the scors, where the NPCFG models represented by the green and grey lines are among the bottom three worst-performing models, and the models represented by the blue and purple lines are among the top three best-performing models. comparison, we see that all models have similar LL scores, which indicates LL's inability to rank models in accordance with their parsing performance. These results underscore our conclusion that SemInfo ranks PCFG models better than LL.
In Figure 9 we observe that the correlation strength for (SemInfo, SFI") also drops as training progresses in SCPCFG. One reason is that SCPCFG fails to explore constituent structures with high SemInfo values. As shown Figure [0] the average SemInfo value across the eight models is around 42 for SCPCFG, while the average SemInfo value is greater equal to 45 for the other
20

---

Published as a conference paper at ICLR 2025
Paraphrasing Model Variations
Large Models
Medium Models
Small Models
gpL35
gpl4o 65.1940.54 59.45
gpt4omini
Hlmaa3.2-38
qwen2.5-3b
Ilama3.2 2. lb
qwen2.5-0.56
Semlafo-NPCFS
66.85+0.25
64.45+1.13
63.7840.55
63.5840.13
10=0.0070 48.5
59.01
SemInfo-MTD
55.56
58.28
55.17
55.03
43.3
LL-NPCFG
1..9621.82
Right Branching
38.4
Table SFI the NPCFG and MaxTreeDecoding (MTD) parsers using SemInfo values obtained from seven paraphrasing models. LL-NPCFG indicates the SF1 score of the LL-trained NPCFG parser.
four PCFG variants. This result indicates that the constituent information provided low SemInfo regions might contain more noise than the information provided in high SemInfo regions.
A.5 ROBUSTNESS AGAINST PARAPHRASING NOISES
Table 6 compares the parsing accuracy of NPCFG models trained using seven paraphrasing mod- els. These models are split into three groups: large models (got4o, spt-4o-mini. gpt-3.50 5), medium models (1lama3, 2- and qwen2. 5-3b), and small models (1lamaa 3-2-1b and qwen2. 5-0 0. 5b), each representing paraphrasing models with different levels of noises. The table also includes a MaximunTTreeDecodingg (MTD) parser, an LL-trained NPCFG parser, and a trivial branhbbrnnchig parser for reference. We use the MTD parser to reflect the paraphrasing quality because its parsing accuracy depends solely on the paraphrasing quality.
We can observe that the SemInfo-trained NPCFG parsers robust against paraphrasing noises. The accuracy gap between the best (gpt4o) and the worst (qwen2. 5-0 0. 5b) performing MTD parser is 16.15 SF1 score. In comparison, the gap between the best and worst performing SemInfo- trained NPCEG parser is 7.84 SFI score, less than half of the gap in the MTD parser. In addition, observe that the PCFG parser benefit from the SemInfo maximization training, even when using noisy paraphrases. All SemInfo-trained PCFG parsers significantly outperform their LL-trained counterparts by a large margin. When trained with the most noisy paraphrasing model (qwen2. 5-0 5b), the Heminfo-trainee PCFG parser outperforms its LL-trained counterpart by points. The result suggests that the PCFG model effectively suppresses the paraphrasing noise, leading to robust PCFG parsers.
A.6 POTENTIAL FOR ENSEMBLING
Figure 12 and Figure 13 suggests that the SemInfo-trained PCFG would benefit from parser bling (Shayegh et al. 2024). [Shayegh et al. (2024) shows that homogeneous unsupervised parsers (same parser model, different initializations) make mildly distinetive predictions, and heterogeneous parsers (different parser models) make considerably distinctive predictions. Ensembling the parsing results from those parsers effectively suppresses parsing errors made by individual parsers, leading to significant accuracy improvement.
In this section, we evaluate whether our Ceminfo-trainee PCFGs can benefit from parser ensembling by examining the parser agreement scores for our parser and comparing the score with those reported in [Saaeegh et al. 2024). If our parser exhibits similar agreement scores, we can consider that our parser would beneñt from the parser ensembling. We evaluate the agreement score of our parser and six previous heterogeneous parsers (CPCEG, Constest, ContextDistort DIORA, NPCFG, and SDIORA).
Figure illustrates the agreement score among parsers using different paraphrasing models. The agreement scores (70-83) are similar to the reported score between homogeneous parsers (74-75 (Shayegh et al. 2024)). This similarity in score suggests that the SemInfo-trained PCFG parsers would benefit from ensembling parsers using various paraphrasing models.
Figure 13 illustrates the agreement score among SemInfo-traie trained PCFG parsers and previous het- erogeneous parsers. We can observe that the agreement score between our SemInfo-trained PCFG parsers and previous parsers ranges from 54-58 (shown in the top-right corner of Figure [3]. The score falls in the same range the score among those previous parsers (46-61, shown in the top-left
21

---

Published as a conference paper at ICLR 2025
CPCFG
55
-12
Log Likelhoodd
-114
50
Seminfo
116
45
1118
40
38
-122
10
Steps
NPCFG
57.5
48
55.0
-118
Log Likellhood
Sominfo
-120
112
42-
45.0
42.5
10
20
10
20
30
40
Steps
SCPCFG
52.5
-105
50.0
42
Log Likellhood
-115
42.5
40.0
34
-120
37.5
10
20
30
10
20
20
30
40
Steps
SNPCFG
55
Likelihoad
-110.0
50
Seminfo
-112.5
45
-115.0
40
-117.5
10
20
30
40
Steps
TNPCFG
60
55
Seminto
42.5
Log Likelhhood
40.0
37.5
-130
40
35.0
-135
35
32.5
-140
10
20
30
40
10
20
30
40
10
20
30
40
Steps
Figure 10: Training curves of SemInfo, LL, and SF1 Each line represents the curve for a single PCFG model.
22

---

Published as a conference paper at ICLR 2025
0.82
0.81
0.86
0.86
0.82
0.81
0.95
0.95
0.95
0.82
0.82
0.90
0.86
1
0.86
0.82
0.82
0.90
0.51
0.52
0.85
0.86
0.86
1
0.81
0.82
1
0.85
0
2
(a) NPCFG
(b) SNPCFG
(c) CPCFG
0.87
0.86
0.85
0.95
0.95
0.87
0.65
0.90
0.90
0.85
2
(d) SCPCFG
(e) TNPCFG
Figure 11: PCFG agreements between independent training runs.
GPT35-NPCFG
100
61
79
79
74
79
GPT40-NPCFG
100
75
77
72
76
.95
GPT4OMIN--NCCG
83
82
100
78
80
77
75
78
90
LLAMAIB-NPCER
LLAMA3B-NPCFG
79
77
80
62
100
80
73
8.3
85
OLMO7B-NPCFG
75
OWENO.5B-NFF 5B-NPCFG
72
73
73
100
74
QWEN3B-NPCFG
76
83
83
74
100
GPT35-NPCFG
GPT4O-NPCFG
GPT4OMINI-APPE
LLAMA1B-NA NPFFF
LLAMA3B-APCFG
GLMO7BI GLMO7B-NPEC NPCFG
OWENO 5B NPCFG
OWEN3B-NPCR NPCCG
Figure 12: NPCFG parser agreement when trained with different paraphrasing models
corner of Figure 13 Both scores are similar to the reported heterogeneous agreement score (55-63 (Shayegh et al. 2024)). This similarity in score suggests that the SemInfo-trained PCFG parsers would benefit from being ensembled with previous heterogeneous parsers.
A.7 RECALL ON SIX MOST-FREQUENT CONSTITUENT TYPES
Table 7 shows the recall of the six most frequent constituent types the English test set, following Yang et al. 2021b). We see that PCFGs trained with SemInfo achieve significant improvement in Noun Phrases (NP), Verb Phrases (VP), and Subordinate Clauses (SBAR). These three constituents are the most typical constituents that carry semantic information. The significant improvement underscores the importance of semantic information in identifying the constituent structure.
23

---

Published as a conference paper at ICLR 2025
Semiafo (Curs)
CPCRG
11.
Sentafo
NPCRG
11.
Semfato
SCPCRG
11.
Semtafo
SNPCEG
11.
Semfafo
INPCHG
LT.
A by Type
85, 15
79:774
301654..0
No.31muus
8730
77.75mm72
-1030
VP
28.294:
73.80
18.534:
76.35
50.212:31
72.234a.1x
45.822rs
-36.65
42.274u47
70.15
75.15kus
79.25
73.855
78.51
71,0raue
+2.09
62.18
80.37
56.
84.16
40 40.81m
82.17
51.28+
67:45t
54.46m.u
+22.67
ADVP
91.57
91.88
19
92.22210
92.11
90.92119
88.07mmm
ADIP
71,828
63.08
75.185gu
61.066
78
60.40t
75.77
75.55
72.90ta
65.40mm0
+7.93
by Model
+12.22
+33.05
200.14
+3.90
+12.76
Table 7: Recall on six most frequent constiment types. The recall data is calculated over the English test set. A by Type indicates the average recall improvement for the constituent type. A by Model indicates the average recall improvement for the PCFG variant.
A.8 PARAPHRASING PROMPTS
We use the below prompts to generate paraphrases from the gpt - 1o00-44-miii22244077- model. {lang) is placeholder for languages. For example, we [lang]=""nghe when collecting En- glish paraphrases.
Create grammatical sentences by shuffling the phrases in the below sentence. The generated sentences must be in [lang). Use the same word as in the original sentence
Create grammatical sentences by changing the tense the below sentence. The generated sentences must be in (lang). Use the same word as in the original sentence.
Create grammatical sentences by restating the below sentences in passive voice. The gen- erated sentences must be in (lang). Use the
word as in the original sentence.
Create grammatical sentences by restating the below sentences in active voice. The gener- ated sentences must be [lang). Use the same word as in the original sentence.
Create grammatical clefting sentences based on the below sentence. The generated sen- tences must be in {lang]. Use the same word as in the original sentence.
Create pairs of interrogative and its answers based on the below sentence. The generated sentences must be grammatically correct and be explicit. The sentences must be in flang). } Use the same word as in the original sentence. The answer to the questions should be substring of the given sentence.
Create pairs of confirmatory questions and its answers based on the below sentence. The generated sentences must be grammatically correct and textually diverse. The sentences must be in (lang)- Use the same word as in the original sentence. The answer to the questions should be a substring of the given sentence.
Create grammatical sentences by performing the topicalization transformation to the below sentence. The sentences must in (lang). Use the same word as in the original sentence.
Create grammatical sentences by performing the heavy NP shift transformation the be- low sentence. The sentences must be in (lang)- Use the same word as in the original sentence.
A.9 EXAMPLES OF THE COLLECTED PARAPHRASES
The below list contains examples of our collected paraphrases for Such agency 'self-help borrow- ing unauthorized and expensive. far more expensive than direct Treasury borrowing. said Rep. Foriney Stark -LRB- D), Calif. -RRB-, the bill 's chief sponsor..
hSelf- borrowing by such agency unauthorized and expensive, far more expensive than direct Treasury borrowing," said Rep. Fortney Stark -LRB- D., Calif. -RRB-, the bill's chief sponsor.
Far expensive than direct Treasury borrowing is such agency" self-help borrowing, unauthorized and expensive, said Rep. Fortney Stark -IRB- D., Calif. -RRB- the bill chief sponsor.
Yes, he said it is far more expensive than direct Treasury borrowing.
What is unauthorized and expensive such agency 'self-help' borrowing, far more expen- sive than direct Treasury borrowing, according to Rep. Fortney Stark.
24

---

Published as a conference paper at ICLR 2025
'Self-help' borrowing by such agency is considered unauthorized and is regarded expen- sive, far more expensive than direct Treasury borrowing," said Rep. Fortney Stark -LRB- D., Calif. -RRB-, who is the chief sponsor of the bill.
According to Rep. Fortney Stark -LRB- D. Calif, -RRB- the bill 's chief sponsor such agency 'self-help" borrowing unauthorized and far more expensive than direct Treasury borrowing.
25

---

Published as a conference paper at ICLR 2025
CPCFG
55
Constast
57
49
53
46
50
ContextDistort
100
48
46
44
48
47
44
45
45
52
53
51
DIORA
52
56
46
100
51
64
48
55
46
50
43
56
58
58
58
NPCFG
61
51
46
51
100
51
S8
45
52
62
54
55
52
51
55
52
SDIORA
55
57
44
64
51
100
43
53
43
50
43
56
58
58
58
59
80
LL-NPCRG
51
49
48
48
58
43
100
53
56
60
51
63
62
6D
61
61
LLSPCC
50
53
47
55
45
53
53
100
48
533
41
62
74
72
66
72
70
LL-TNCCGG
54
46
44
46
52
43
56
49
100
64
55
54
55
54
55
55
LL-CPCFG
64
50
45
50
62
50
60
53
64
100
60
62
60
59
63
61
LL-SCPCFG
54
44
45
43
54
43
51
41
55
60
100
53
50
49
53
50
Seminfo-NPCFG
53
55
52
58
55
56
63
62
54
62
53
100
75
73
80
77
Seminfa
56
59
53
5B
52
58
62
74
5.5
60
50
75
100
83
80
85
Seminfo-TNPPCG
55
57
51
5B
51
58
60
72
54
59
49
73
83
100
78
50
Seminfo-CPCFG
56
57
52
59
55
58
61
66
55
63
53
80
80
78
100
82
SemInfo-SCPCFG
55
59
72
55
50
CPCPG
Constest
Contexitsttort
DIORA
NPCRG
SDIORA
LLNNPFG
IL-SNPCKG
iL-TNPORG
LLCPPRG
1L-SCPORG
Saminfo NPCRG
Seminfo Seminto-SAPCrG SAPCPG
Seminfe-TNPCC TNPCFG
SeMInfo-CPCTG
Seminfo SCPCPG
Figure 13: Agreement between heterogencous parsers
26


Reviews:
[{"review_id": "ZWq81aL9mn", "reviewer": "Reviewer_5TGk", "summary": "Unsupervised parsing methods typically involve maximizing sentence log likelihood, which does not correlate well with parsing accuracy. In contrast, this paper uses a paraphrase model to define SemInfo, an alternate objective that involves maximizing a mutual information metric between tree spans and sentence paraphrases. This alternate objective can then be used as a replacement for log likelihood when doing PCFG induction. Experiments show that this objective produces substantially better F1 scores than log likelihood maximization across a wide range of PCFG variants and languages.", "questions": "Potential typo: Equation 13: t \\in P(t | x) -> t ~ P(t | x)", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "(1) Overall, the paper is strong, and the proposed method is a fundamental improvement in unsupervised parsing. In addition to providing strong results, it provides insight into what is missing in log likelihood maximization and how one might augment log likelihood with other objectives.\n\n(2) The evaluation is very thorough, with 5 PCFG variants and 4 languages, and the method produces very large gains.\n\n(3) The paper is well-written: it is well-organized, does a good job of motivating and explaining the method, and provides useful analysis.", "weaknesses": "No major weaknesses; some minor weaknesses are discussed below. I support the acceptance of this paper regardless of whether the additional experiments mentioned below are run or not.\n\n(1) From what I can tell, the paper builds upon Chen et al. (2024), which is a simpler instantiation of the idea that spans are likely to be constituents if they tend to be regenerated by paraphrase models. While this is acknowledged in the related works section, perhaps it is also worth acknowledging the influence of their paper in Sections 2 and/or 3 (unless this paper was concurrent).\n\n(2) I would be curious about ablations for each of the additional components of the method (naive substrings -> maximal substrings, the average baseline and entropy regularization in REINFORCE, the addition of the LL term in SemInfo), for both SemInfo as a training objective and when used for MaxTreeDecoding.\n\n(3) While the paper is motivated as an alternate objective for unsupervised parsing, it instead sort of feels like a method for distilling the grammatical knowledge of a large model (in this case, gpt-4o-mini) into a PCFG. From that perspective, the experiments are not that surprising given that we know that large models have mastery of grammar. The promise of the motivation would be better met if the method used a weaker paraphrase method (e.g., something hand-coded) that does not require already \"knowing\" the grammar of the language.", "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": "jdinoAWy3A", "reviewer": "Reviewer_PqLp", "summary": "The authors propose a novel method for unsupervised constituency parsing. The method is based on semantic information from text statistics (e.g. tf-idf, and bag-of-words). The main contributions are: i) novel metric to measure the information between syntactic structures and semantic, and ii) grammar induction model based on the semantic metric as a learning objective. The method shows a high correlation between the proposed metric and parsing performance, and the proposed model shows competitive performance compared to the state-of-the-art.", "questions": "Please address the following questions during the rebuttal:\n\n- Does the proposed model produce different parse trees over multiple runs?  Could the uncertainty impact the performance of the model?\n- Could the method use similar sentences (e.g. nearest neighbours) instead of synthetic data? or other sources of data (e.g. translations, multi-lingual). Could this change have a strong effect on performance? \n- Please speculate on the combination of the proposed semantic metric with contextual embeddings for taking into account paraphrasing. For example: https://aclanthology.org/P15-1030.pdf", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Clear description of background knowledge and related work needed to understand the proposed method.  \n- The authors perform a  comprehensive comparison of the proposed metric with different models and languages.", "weaknesses": "- Dependence of the model on synthetic data (e.g. gpt) for paraphrasing.", "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": "Ns4eG5W5W7", "reviewer": "Reviewer_M3gk", "summary": "This paper presents a new approach to learning an unsupervised constituency parser.  The approach works by a novel distillation procedure that leverages an LLM-based paraphrasing model.  The connection between paraphrasing and syntax is nicely motivated by linguistic theory.  Their approach combines a nice mix of old (keyword extraction, conditional random fields) and new (LLMs).  They provide strong empirical results in five languages over state-of-the-art methods.", "questions": "What is the tree probability (line 152) proportional to the sum of potentials? Normally, it is proportional to the product (or exponentiated sum) of potentials.\n\nCan you say a bit more about how the Tree CRF is parameterized? What are the features and grammar?\n\nHow stable are the results of changes in the paraphrasing model? \n\nAt the top of page 6, you suggest that adding log Z term to the objective stabilizes during *early* training; you could better support that claim if you dropped the log Z term after pre-training. Have you considered trying this?\n\nPlease explain in section 3 that the paraphrasing model is taken as a given.  I was confused about that until I got to the experiments section (page 6).", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper presents a new approach to learning an unsupervised constituency parser.  The approach works by a novel distillation procedure that leverages an LLM-based paraphrasing model.  It is a very clever idea!  The connection between paraphrasing and syntax is nicely motivated by linguistic theory.  Their approach combines a nice mix of old (keyword extraction, conditional random fields) and new (LLMs).  They provide strong empirical results in five languages over state-of-the-art methods.", "weaknesses": "I found the mathematical exposition imprecise and hard to follow. This paper would benefit significantly from iteration with colleagues to identify and address these issues.  This is my main hesitation about this paper and why I gave it an overall score of 6 instead of 8.", "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": "AH9U3EQ3a4", "reviewer": "Reviewer_t1cD", "summary": "This work investigates enhancing the performance of Probabilistic Context-Free Grammar (PCFG) parsers in the Unsupervised Constituency Parsing task by incorporating semantic information into the training objective. To achieve this, the authors use the `gpt-4o-mini-2024-07-18` model as an external paraphrasing tool to generate paraphrases for input sentences, assigning semantic scores to individual phrases based on these paraphrases. The parser is then trained with the Reinforce algorithm to maximize the expected total semantic scores of the induced constituents.\n\nThis work demonstrates non-ensemble non-distilled state-of-the-art (SOTA) unsupervised parsing performance for English, Chinese, and French, along with substantial performance on German. The authors also conduct additional experiments to show strong correlations between the proposed objective and parsing performance, motivating further investigation of this objective function for non-PCFG models in future work.", "questions": "* All the questions in the 3rd point in weaknesses.\n* Why is the IDF term included in the SemInfo definition? Is there a specific reason for incorporating this term?\n* In Section 5.3.1, why was 30k steps chosen as the evaluation point? Is there a particular rationale behind this choice?", "limitations": "", "rating": 8, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "* Demonstrates the effectiveness of utilizing semantic information in parsing.\n* Proposes a novel approach for measuring semantic information through paraphrasing.\n* Exhibits significant performance improvements across various setups (different PCFG variants as base models and multiple languages).\n* Includes experiments in four languages: English, French, Chinese, and German.\n* Focuses on model optimization, making it complementary to other efforts in the field.\n* The paper is well-written and easy to follow.", "weaknesses": "**I would be happy and am strongly willing to increase my rating if most of the following issues, especially the last one, are fixed.**\n\n* **[Minor Weakness]** The authors frequently use “sentence-F1,” “corpus-level sentence-F1,” and “mean sentence-F1” interchangeably, which may lead to confusion. If I understand correctly, each of these terms refers to the “corpus-level sentence-F1” defined on line 299: “The corpus-level score is computed by averaging the sentence-F1 score across the entire corpus.” In prior research, this metric is commonly referred to as the sentence-level F1 score.\n\n    The commonly accepted distinction, as stated in Footnote 8 of [Kim et al. (2019)](https://aclanthology.org/P19-1228/), is as follows: Corpus-level F1 calculates precision and recall at the corpus level to derive the F1 score, whereas sentence-level F1 calculates F1 for each sentence and then averages across the corpus.\n\n    **Suggestions:** Although this paper defines its terminology, it is recommended to (1) avoid using multiple terms for the same concept, and (2) adopt standard terminology to prevent confusion. If the intent is to differentiate between sentence-level F1 scores used in correlation analysis and the average score used in main experiments, a preferable approach might be to use “sentence-level F1” and “mean sentence-level F1.”\n\n* The paper claims to be “unsupervised” and compares its results with other “unsupervised” models. However, it relies on an external paraphrasing model that may involve either supervised or unsupervised methods of paraphrasing supervision. If this paraphrasing model is supervised, then the entire approach would more accurately be considered an “indirectly” or “distantly supervised” method, which is not directly comparable to fully unsupervised baselines. Specifically, the paraphrasing model used here, `gpt-4o-mini-2024-07-18`, incorporates reinforcement learning from human feedback (RLHF; [OpenAI source](https://openai.com/index/gpt-4o-mini-advancing-cost-efficient-intelligence/)), which makes it a supervised model due to its reliance on human feedback/labels.\n\n    Additionally, one key motivation for claiming an “unsupervised” approach is applicability to low-resource languages or other structure-prediction tasks where GPT models may not be available. This limitation should be more clearly addressed in the paper.\n\n    **Suggestions:** To support the “unsupervised” claim, I suggest conducting experiments with an unsupervised paraphrasing model. A comparable approach is found in [He et al. (2018)](https://arxiv.org/pdf/1808.09111), where their dependency parser model, which requires POS labels, reports two sets of results: one using gold POS tags and the other using induced unsupervised POS tags. This dual-setup approach acknowledges the compounded error introduced by unsupervised POS tagging, providing a clearer comparison.\n\n* Regarding the paraphrasing model, several important questions and concerns should be addressed:\n    1. Quality Requirements: What level of performance is required from the paraphrasing model to effectively support the proposed method? Is there a minimum paraphrasing accuracy or quality that significantly impacts the results, and how is this threshold determined?\n    2. Robustness to Model Choice: How robust is the proposed model to variations in the paraphrasing model used? For example, would different paraphrasing models (with varying architectures, training datasets, or language capabilities) yield comparable outcomes, or are the results highly sensitive to the choice of the paraphrasing model? This could be demonstrated through experiments with multiple paraphrasing models, both high- and low-performing, to understand the potential variability in results.\n    3. Efficiency in Training: How efficient is the training process, given that it requires multiple calls to the paraphrasing model? Discussing any optimizations or alternatives could strengthen the method’s practicality.\n\n    Each of the above points warrants at least some discussion in the paper.\n\n* There is no need for probability notation in Equation (7); the `P` notation can be safely replaced with an indicator function. It is recommended to avoid probability notation here, as `s ∈ MS(x^p, x)` is not a random variable, given that `x^p` serves as the expectation argument.\n* In Table 1, the statistical test is conducted using only three samples, which affects its reliability. Since training multiple model instances is resource-intensive, I suggest performing the test at the sentence level. Specifically, consider each sentence’s F1 score as a separate sample, following [Shayegh et al. (2024)](https://aclanthology.org/2024.acl-long.808.pdf).\n* The final argument in Section 5.2, which discusses the performance on the German dataset, could benefit from further elaboration. Currently, the claim lacks sufficient support.\n* **[Minor Weakness]** In Appendix A.2, the correlation is reported at 10k, 20k, and 30k steps. However, Figure 5 shows that LL-SF1 diminishes significantly after 10k steps, while achieving better correlation at earlier stages. Although this does not affect the conclusion that SemInfo-SF1 maintains a higher correlation throughout the entire training process, it would be beneficial to include results for earlier steps in Appendix A.2 for completeness.\n* **[Minor Weakness]** Figure 4 appears to depict a worst-case scenario for LL-SF1 correlation, showing a large negative value. However, Table 2 shows that the correlation is nearly zero for all models and slightly positive on average, which may make Figure 4’s presentation somewhat misleading.\n* The paper introduces PCFG models as the state-of-the-art (SOTA) in the task five times, yet only twice (and neither in the Approach nor Introduction sections) specifies that this refers to non-ensemble SOTA. Additionally, the authors claim to achieve new SOTA results four times without clarifying that this pertains only to non-ensemble models.\n    1. Transparency of Setup: This approach somewhat obscures the actual setup. It should be clearly stated as non-ensemble, and more importantly, **non-distilled** SOTA, especially as works like [Kim et al. (2019)](https://aclanthology.org/P19-1228/), [Cao et al. (2020)](https://aclanthology.org/2020.emnlp-main.389.pdf), and [Shayegh et al. (2024b)](https://arxiv.org/pdf/2310.01717) demonstrate significant performance improvements by distilling induced knowledge into a URNNG model ([Kim et al.; 2019b](https://arxiv.org/abs/1904.03746)), all of which outperform the best results in this paper. The first two works achieve this by distilling the best model (which requires a validation set), and the latter by distilling ensemble knowledge (non-best, thus without a validation set).\n    2. Comparison Justification: It is unclear why the authors chose to compare only with non-ensemble and non-distilled models. This choice is not discussed in the paper. Since distilled models have demonstrated efficiency during inference (Table 5 in [Shayegh et al.; 2024b](https://arxiv.org/pdf/2310.01717)), inference efficiency cannot be the reason. If training efficiency is the concern, then an efficiency analysis on the paraphrasing models is warranted.\n    3. Discussion of Related Work: Even if the authors choose not to compare directly with the mentioned works, these studies are significant enough to merit discussion.\n\n    In general, there is an overemphasis on claiming SOTA. This is unnecessary, as the paper’s novelty and valuable contributions stand on their own and are beneficial to the field. Notably, [Shayegh et al. (2024b)](https://arxiv.org/pdf/2310.01717) show that each individual model with specialized expertise can contribute substantially to final parsing performance when part of an ensemble. Specifically, they take advantage from [Li & Lu (2024)](https://scholar.google.com/scholar_url?url=https://arxiv.org/abs/2306.00645&hl=en&sa=T&oi=gsr-r&ct=res&cd=0&d=15034760626359817941&ei=bG4mZ7CxJuG86rQPgN2emQk&scisig=AFWwaeZgwSDS3qGcVtN0rBG9whiK) despite their lower standalone performance, because of its unique approach to Unsupervised Constituency Parsing.\n\n    **Suggestions:**\n    * Instead of heavily emphasizing standalone SOTA status, consider including a correlation analysis with other baselines to demonstrate the unique insights offered by the new model, particularly due to the proposed new objective.\n    * Incorporating the model into the ensemble approach from [Shayegh et al. (2024b)](https://arxiv.org/pdf/2310.01717) and measuring any resulting performance boost could also provide strong support for the model’s contribution.", "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 (Spotlight)