On Eliciting Syntax from Language Models via Hashing (2024)

Abstract: Unsupervised parsing, also known as grammar induction, aims to infer syntactic structure from raw text. Recently, binary representation has exhibited remarkable information-preserving capabilities at both lexicon and syntax levels. In this paper, we explore the possibility of leveraging this capability to deduce parsing trees from raw text, relying solely on the implicitly induced grammars within models. To achieve this, we upgrade the bit-level CKY from zero-order to first-order to encode the lexicon and syntax in a unified binary representation space, switch training from supervised to unsupervised under the contrastive hashing framework, and introduce a novel loss function to impose stronger yet balanced alignment signals. Our model shows competitive performance on various datasets, therefore, we claim that our method is effective and efficient enough to acquire high-quality parsing trees from pre-trained language models at a low cost.

## introduction grammars form the backbone of languages, providing the essential framework that dictates how lexicons are arranged to convey meaning. understanding and generating language heavily relies on grasping these latent structures. unsupervised parsing, which aims to deduce sentence structure without relying on costly manually annotated treebanks, has been widely studied in academia. however, despite its importance, advancements have been slow due to the intrinsic complexity of this task. nowadays, addressing these challenges becomes even more crucial for further exploring the capabilities of large language models. word embedding and language model techniques @xcite @xcite have shown that training models to predict tokens in specific contexts is remark5a00 @xmath0 figure 1 : the model architecture. the hash layer produces scores of all spans, and the following first-order bit-level cky ( §3.1) returns marginal probabilities µ and predicts the most probable trees t. sentences are fed into the network twice, we select span marginal probabilities from one pass according to the predicted trees from the other pass, and perform contrastive hashing ( §3.2, §3.3) on their corresponding score and code vectors. the purple cells represent the marginal probabilities, and the dark purple indicate the selected ones. fortunately, the recently proposed binary representation meets these requirements perfectly. @xcite proposed a binary representation that bridges the gap between the continuous nature of deep learning and the discrete intrinsic property of natural languages. instead of directly applying contrastive learning on the high-dimensional continuous hidden states of pre-trained language models, @xcite project them as k-dimensional score vectors. these scores can easily be binarized into k-bit codes, and token-level contrastive learning is applied among these scores and their binarized codes. they demonstrate that lexical information can be properly preserved within only 24 bits. following this, wang and utiyama (2024) additionally take spans on the target parsing trees into consideration. they use marginal probabilities to construct a novel similarity function that reflects not only lexical information but also the boundary of each span, and then perform contrastive hashing across spans rather than tokens. in their supervised parsing experiments, they show the effectiveness of the structured binary representation by achieving comparable performance to conventional parsers. although in the supervised settings, wang and utiyama (2024) achieves satisfactory results, we found that for unsupervised settings, their model is insufficient to induce meaningful parsing trees. in this paper, we aim to elicit constituency parsers from pre-trained language models without training them on annotated treebanks. we analyze the existing issues of their structured binary representation and explore the possibility of further enhancing the unified information-preserving capability. to achieve this, we upgrade the bit-level cky module from zero-order ( §2.1) to first-order ( §3.1) to integrate lexicon and syntax in a unified format, convert parsing from supervised ( §2.2) to unsupervised ( §3.2), and propose a novel objective function ( §3.3) to impose stronger yet balanced alignment signals. besides, we also discuss how the learning objective of contrastive hashing aligns with the target of parsing. this provides an explanation ( §3.2) different from the distributional hypothesis and explains why our training leads to syntactic structures rather than other structures. experiments show that our models achieve competitive performance and indicate that acquiring high-quality syntactic annotations at a low cost is becoming practicable. we refer to our parser as parserker2, following the original parserker (wang and utiyama, 2024). ## related work syntactic language models, as a historical and important field of language models, had been widely studied even before the deep learning era @xcite @xcite @xcite . after that, @xcite added syntactic inductive bias to lstm by introducing master gates to control the information flow in hierarchical directions, thereby enabling the model to learn syntactic distance. under this framework, by training recurrent language models in the usual way, they can obtain parsers that implicitly structure sentences according to the learned syntactic distances. they have also successfully applied this method to transformers @xcite . implicit grammar models induce grammar during the training process by incrementally constructing larger span representations. @xcite were the first to extend the recurrent neural network grammar (rnng) @xcite from supervised to unsupervised settings. they build parsing trees through continuously shifting and reducing, without introducing explicit production rules. additionally, diora @xcite construct span representations and update charts in both inside and outside passes, and then encourage consistency between them. similarly, r2d2 @xcite is trained in a similar manner, but with gumbel-softmax @xcite introduced during the tree construction. apart from implicit grammar models, explicitly inducing probabilistic context-free grammar (pcfg) is also widely focused. @xcite first brought pcfg approaches back with a neural parameterization technique and trained language models to reconstruct entire input sentences token by token. @xcite shows that additionally modeling lexical dependencies @xcite is effective, and @xcite ; @xcite further confirmed extending to bilexical dependencies is even more beneficial. besides, @xcite ; @xcite claimed that the limited number of symbols is a bottleneck of pcfg induction, and proposed to introduce more symbols by applying tensor decomposition to overcome the cubic computational complexity. how much syntactic knowledge is preserved within the ordinary language model is also a question worth considering. @xcite noticed the value of attention scores first. they defined distance functions similar to our equation 17 for probing. however, they did not consider splitting positions, and relied only on fixed attention heads without having them fine-tuned. as a result, their methods resulted in limited accuracy. @xcite ; @xcite ; @xcite ; @xcite ; @xcite then introduced parameterized functions to prob syntactic distances on hidden states and attention scores, and then fine-tuned the entire models. cao et al. (2020); maveli and cohen (2022) fine-tuned pre-trained language models with an additional classifier to distinguish manually generated constituents and distituents, and utilized predictions from this classifier to determine splitting positions on parsing trees during the evaluation stage. in various senses, our approach confirmed the conclusions of many previous works and further pushed their limits. first, by switching the language models from token-level to span-level, we confirmed that modeling lexical dependencies is beneficial and extending this modeling to all tokens in children is more effective. additionally, by introducing binary representation, we confirmed that employing more symbols is advantageous and further scaling up to 2 k can help parsers do further better. third, we confirmed that constructing span representations and updating the chart is helpful, and unifying the representation of lexicon and syntax leads to more competitive results. finally, we confirmed the multi-head attention scores already preserve syntactic information, and finetuning them can help probe for more insightful features. ## conclusions in this paper, we confirmed that the informationpreserving capability of binary representation is effective at both lexicon and syntax levels, and we demonstrated that it is feasible to elicit parsers from pre-trained language models by leveraging this capability. we achieved this by upgrading bitlevel cky from zero-order to first-order, extending contrastive hashing from supervised to unsupervised, and proposing a novel objective function to impose stronger yet balanced alignment signals. experiments show our model achieves competitive performance, and also indicate that the technique for acquiring high-quality syntactic annotations at low cost has now reached a practical stage.