Introduction
Dependency parsing—the process of mapping the syntactic "family tree" of a sentence—is a cornerstone of natural language processing. Traditionally, training these parsers requires massive amounts of expensive, human-annotated data. Unsupervised dependency parsing seeks to bypass this requirement by inducing structure directly from raw text. While Large Language Models (LLMs) have shown promise in this area, previous approaches often relied on "black-box" metrics (such as Euclidean distance between internal vectors) that lack statistical interpretability and struggle to incorporate fundamental linguistic rules.
Methodology
This research introduces a novel framework that combines the statistical power of LLMs with the rigor of information theory and traditional grammar. The core of the approach is the use of Conditional Mutual Information (CMI) as a metric for word dependency. CMI measures how much knowing one word changes the probability of seeing another in a specific context; a high CMI suggests a strong syntactic bond.
To estimate CMI, the authors utilize a Multi-Try Metropolis-Hastings (MTMH) sampler. A key innovation in this process is the Part-of-Speech (POS) Constraint: during sampling, the model is forced to swap words only with others of the same category (e.g., replacing a noun with another noun). This ensures the sentence's underlying structure remains stable while measuring dependencies.
Furthermore, the model applies two "old-school" grammatical constraints during the final decoding stage:
- Adjacent-Connect (AC): Encourages words to connect to their immediate neighbors if no stronger global dependency is found.
- Function Word UnHeading (FNUH): Prevents "function words" (like the, of, at) from being the head of a dependency, reflecting universal linguistic patterns.
Key Insights and Results
The researchers found that CMI is exceptionally effective at identifying "lexical-interaction-rich" relations, such as the bond between a subject and its verb. Statistical analysis confirms that CMI scores are significantly higher for actual dependencies than for non-dependencies across various sentence lengths.
Key performance highlights include:
- State-of-the-Art Accuracy: On 10-word benchmarks, the model achieved an average Unlabelled Undirected Attachment Score (UUAS) of 0.615, outperforming the previous best LLM-based method (0.575).
- Cross-Lingual Robustness: The method proved effective across English, German, French, Spanish, and Russian, suggesting that the combination of CMI and basic grammar is a universal "sweet spot."
- Impact of Constraints: Adding linguistic constraints (AC and FNUH) boosted performance by 6.2 percentage points, proving that traditional linguistic rules remain vital even in the age of LLMs.
Limitations and Future Work
The primary challenge for this method is computational cost; estimating CMI via sampling is slow, requiring roughly 40 GPU hours for a single 10-word dataset. Additionally, the current model produces undirected trees, identifying that a relationship exists but not which word is the "parent." Future research will focus on scaling these methods to longer sentences and inducing directionality in the induced trees.
Summary updated