Language Model Based Unsupervised Dependency Parsing with Conditional Mutual Information and Grammatical Constraints (2024)

Abstract: Previous methods based on Large Language Models (LLM) perform unsupervised dependency parsing by maximizing bi-lexical dependence scores. However, these previous methods adopt dependence scores that are difficult to interpret. These methods cannot incorporate grammatical constraints that previous grammar-based parsing research has shown beneficial to improving parsing performance. In this work, we apply Conditional Mutual Information (CMI), an interpretable metric, to measure the bi-lexical dependence and incorporate grammatical constraints into LLM-based unsupervised parsing. We incorporate Part-Of-Speech information as a grammatical constraint at the CMI estimation stage and integrate two additional grammatical constraints at the subsequent tree decoding stage. We find that the CMI score positively correlates with syntactic dependencies and has a stronger correlation with the syntactic dependencies than baseline scores. Our experiment confirms the benefits and applicability of the proposed grammatical constraints across five languages and eight datasets. The CMI parsing model outperforms state-of-the-art LLM-based models and similarly constrained grammar-based models. Our analysis reveals that the CMI model is strong in retrieving dependency relations with rich lexical interactions but is weak in retrieving relations with sparse lexical interactions, indicating a potential limitation in CMI-based unsupervised parsing methods.

## introduction syntactic dependency structures provide important information to downstream natural language processing tasks, such as information extraction @xcite , machine translation @xcite , and question answering @xcite . however, extracting the dependency structure using supervised methods requires expensive humanannotated dependency structures, which are only available for limited languages and domains. large language model (llm) based unsupervised parsing methods @xcite @xcite circumvent the problem by directly extracting the dependency structure from llms. these methods estimate bi-lexical dependence scores from the llms and identify the dependency structure as the tree with maximum bi-lexical dependence scores. figure 1 illustrates the motivation using our proposed bi-lexical dependence score. we can observe a positive correlation that syntactically dependent words (i.e., syntactic dependencies) tend to have a higher-than-average dependence score. with the positive correlation, we can factor the unsupervised parsing problem into two subproblems:(1) devising a dependence score that correlates well with the syntactic dependency and (2) performing a maximum spanning tree (mst) decoding. the strength of the correlation between the dependence score and the syntactic dependency directly impacts the we release our code in the github repository. however, some llm-based methods @xcite adopt dependence scores that lack a statistical interpretation of why some word pairs are more dependent than others. other methods @xcite suffer from significant estimation issues. additionally, no llm-based method can incorporate grammatical constraints that previous grammar-based parsing research @xcite @xcite has shown beneficial to parsing performance. in this paper, we apply conditional mutual information (cmi) @xcite , an interpretable metric, for measuring the bi-lexical dependence relation. cmi reveals the statistical correlation of two words under a given context, with a high cmi score indicating a strong correlation. we apply the metropolis-hasting sampling method @xcite to obtain an unbiased cmi estimate. we incorporate part-of-speech (pos) information into the cmi estimation process as the pos constraint and further integrate two grammatical constraints (i.e., adjacent-connect (ac) constraint and function word unheading (fnuh) constraint) in the dependency tree decoding stage. our main contributions are three-fold. (1) we found a positive correlation that syntactically dependent words tend to have a high cmi (i.e., they are more likely to correlate). (2) we found the grammatical constraints effective in improving parsing performance and generally applicable across five languages. (3) we found that the cmi model performs strongly in dependency relations with rich lexical interactions while performing weakly in relations with sparse lexical interactions. our study confirms the benefit of grammatical constraints in llm-based unsupervised dependency parsing while suggesting a limit of cmi-based methods in the unsupervised parsing task. ## method in this section, we propose a grammatically constrained cmi-based unsupervised parsing method. we apply cmi as the bi-lexical dependence metric and use the sentence distribution derived from a causal llm as cmi's probability measure. we derive a reliable mh-based cmi estimator incorporating pos information through the pos constraint. we implement a multi-try mh (mtmh) sampler @xcite to achieve a higher sampling efficiency and a better sample quality. we heuristically incorporate the ac and the fnuh constraint during the mst decoding stage. ## discussion in section 5, we saw grammar-based models outperforming the cmi model after applying all three grammatical constraints. nonetheless, we believe the grammar-based models are not superior substitutes for the cmi-based models. the two models are on opposite ends of a spectrum. our experi-ments have pointed out the strong performance of the cmi model in retrieving dependency relations with rich lexical interactions, which is in line with yuret (1998)'s finding. although grammar-based models can benefit from lexical information @xcite , they struggle to utilize the rich lexical interaction encoded in llms @xcite . the cmi-based models and the grammar-based models are complementary. we believe that combining the strength of the cmi and grammar-based models can lead to a more robust unsupervised parsing method. ## conclusion in this paper, we applied cmi, an interpretable bi-lexical dependence metric, to unsupervised dependency parsing and proposed a reliable mtmhbased cmi estimator. we incorporated pos information into the cmi estimation process through the pos constraint and further integrated the ac and fnuh constraints at the decoding stage. the correlation analysis suggests that the cmi score positively correlates with the syntactic dependency and has a stronger correlation with the syntactic dependency than baseline scores. the comparison with the baseline models and the ablation analysis confirmed the effectiveness and applicability of the three grammatical constraints in llm-based unsupervised dependency parsing across five languages. analysis by dependency relations indicates that the cmi model performs strongly on relations involving rich lexical interactions but performs poorly on relations involving sparse lexical interactions. the weakness in retrieving lexical-interaction-sparse relations suggests a limitation in cmi-based unsupervised parsing methods. the comparison with state-of-the-art models establishes the cmi model as a strong llm-based model, which outperforms llm-based and similarly constrained grammarbased models but underperforms the more strongly constrained model.