Improving Unsupervised Constituency Parsing via Maximizing Semantic Information

Authors: Junjie Chen, Xiangheng He, Yusuke Miyao, Danushka Bollegala
Primary area: applications to computer vision, audio, language, and other modalities
Keywords: unsupervised constituency parsing, information theory, semantic information

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.

Decision: accept (spotlight)
Reviewer scores: 8, 8, 6, 8

Reviews and discussion:
<thread>
creation date:
1730574231436

thread_type:
official_review

<thread_object>
creator: reviewer_t1cd

<content>
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.

This 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.

strengths:
* Demonstrates the effectiveness of utilizing semantic information in parsing.
* Proposes a novel approach for measuring semantic information through paraphrasing.
* Exhibits significant performance improvements across various setups (different PCFG variants as base models and multiple languages).
* Includes experiments in four languages: English, French, Chinese, and German.
* Focuses on model optimization, making it complementary to other efforts in the field.
* 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.**

* **[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.

    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.

    **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.”

* 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.

    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.

    **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.

* Regarding the paraphrasing model, several important questions and concerns should be addressed:
    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?
    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.
    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.

    Each of the above points warrants at least some discussion in the paper.

* 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.
* 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).
* 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.
* **[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.
* **[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.
* 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.
    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).
    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.
    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.

    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.

    **Suggestions:**
    * 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.
    * 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.

questions:
* All the questions in the 3rd point in weaknesses.
* Why is the IDF term included in the SemInfo definition? Is there a specific reason for incorporating this term?
* In Section 5.3.1, why was 30k steps chosen as the evaluation point? Is there a particular rationale behind this choice?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730651130713

thread_type:
official_review

<thread_object>
creator: reviewer_m3gk

<content>
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.

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.

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.

Can you say a bit more about how the Tree CRF is parameterized? What are the features and grammar?

How stable are the results of changes in the paraphrasing model? 

At 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?

Please 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).
</content>
</thread_object>

</thread>
<thread>
creation date:
1730661987366

thread_type:
official_review

<thread_object>
creator: reviewer_pqlp

<content>
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.

strengths:
- Clear description of background knowledge and related work needed to understand the proposed method.  
- 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.

questions:
Please address the following questions during the rebuttal:

- Does the proposed model produce different parse trees over multiple runs?  Could the uncertainty impact the performance of the model?
- 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? 
- 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
</content>
</thread_object>

</thread>
<thread>
creation date:
1730715963844

thread_type:
official_review

<thread_object>
creator: reviewer_5tgk

<content>
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.

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.

(2) The evaluation is very thorough, with 5 PCFG variants and 4 languages, and the method produces very large gains.

(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.

(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).

(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.

(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.

questions:
Potential typo: Equation 13: t \in P(t | x) -> t ~ P(t | x)
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper presents a novel method for learning constituency parsers in an unsupervised fashion.  The reviewers are overwhelmingly supportive of acceptance as the consensus is that the paper presents a substantial improvement in this area beyond what exists in the literature.  There are no explicit large weaknesses given the discussion.