Categorial grammar induction from raw data (2023)

Abstract: Grammar induction, the task of learning a set of grammatical rules from raw or minimally labeled text data, can provide clues about what kinds of syntactic structures are learnable without prior knowledge. Recent work (e.g., Kim et al., 2019; Zhu et al., 2020; Jin et al., 2021a) has achieved advances in unsupervised induction of probabilistic context-free grammars (PCFGs). However, categorial grammar induction has received less recent attention, despite allowing inducers to support a larger set of syntactic categories—due to restrictions on how categories can combine—and providing a transparent interface with compositional semantics, opening up possibilities for models that jointly learn form and meaning. Motivated by this, we propose a new model for inducing a basic (Ajdukiewicz, 1935; Bar-Hillel, 1953) categorial grammar. In contrast to earlier categorial grammar induction systems (e.g., Bisk and Hockenmaier, 2012), our model learns from raw data without any part-of-speech information. Experiments on child-directed speech show that our model attains a recall-homogeneity of 0.33 on average, which dramatically increases to 0.59 when a bias toward forward function application is added to the model.

## introduction one of the core motivating questions of modern linguistics relates to language acquisition: how can a child pick up complex linguistic rules from limited exposure to language? @xcite introduced the well-known argument from the poverty of the stimulus, which claims that the linguistic input received by children is insufficiently rich to account for the knowledge they acquire-and therefore that humans must be born with prior knowledge about language. in contrast, empiricist accounts of language acquisition argue that statistical cues @xcite or other factors such as social interaction @xcite may pro-vide enough information on their own to support language acquisition. computational modeling provides one useful tool for judging between these competing accounts. questions about the learnability of linguistic structures can be tested empirically by seeing if a model with minimal prior knowledge can learn these structures from corpus data @xcite . along these lines, a range of studies over several decades have tested whether induction models can acquire probabilistic context-free grammars (pcfgs) from text data @xcite . although pcfg induction is considered a difficult problem @xcite , recent systems have achieved performance improvements thanks to new types of bayesian and neural network models. recent systems have been able to induce grammars with accuracy levels (measured by recall-homogeneity) approaching fifty percent on corpora of child-directed speech @xcite . although pcfgs are a convenient formalism for computational modeling, they are not the only viable option. a second line of research-albeit one less currently active than pcfg modeling-has examined the learnability of categorial grammar formalisms @xcite , particularly combinatory categorial grammar (ccg; @xcite . a notable advantage of categorial grammars over pcfgs is their clean mapping between syntactic and semantic composition, which allows them to be used as a tool for predicting lambda calculus encodings of meaning @xcite . categorial grammars also impose constraints regarding which syntactic categories can combine, providing a practical advantage for designing induction systems that support a large set of categories. motivated by these advantages, this work presents a neural network-based system that adapts a state-of-the-art pcfg induction model @xcite to instead learn a basic categorial grammar. 1 unlike the previously mentioned categorial grammar induction systems, our model learns from entirely unlabeled data. an initial version of the model attains an average recall-homogeneity (rh) score of 0.33 on an english corpus of child-directed speech (experiment 1). a high variance across randomly initialized runs is observed, with a cluster of runs achieving rh on par with state-of-the-art pcfg inducers and another cluster achieving poor rh. in experiment 2, we test a modified version of the model with a bias term encouraging forward function application, which appeared more often in the better-performing runs in experiment 1. the modified model reaches an average rh of 0.59, surpassing results reported from @xcite and other pcfg inducers. a somewhat earlier line of research established the potential for learning an alternative type of grammar, a ccg, from data with a small set of broadly defined part-of-speech categories (noun, verb, etc.) @xcite @xcite . @xcite showed that only a small number of labeled data points with pos tags are needed to induce a ccg. however, induction of ccgs (or other categorial grammars) has received less recent attention, with ccg research more focused on tasks such as supertagging @xcite or incremental parsing @xcite . a third relevant area of research is work focused on mapping a sentence to its logical form via ccg parsing (zettlemoyer and collins, 2005; 1 the code for the categorial grammar inducer is available at https://github.com/christian-clark/ cginduction . @xcite . these studies reveal that categorial grammar induction may be useful not only as a method of testing the learnability of syntactic rules, but also as a tool for semantic parsing. ## induction model the model introduced in this paper extends the jin et al. (2021a) model from section 3.2 to induce a categorial grammar. this section details how categories and expansion rule probabilities are defined in the new model. ## experiment 2: induction model with forward function application bias to try to produce more consistent induction results with english-like branching behavior, our second experiment biased the induction model toward using forward function applications (i.e., the / operator). while in principle it is possible for rightbranching structures to use backward function application and left-branching structures to use forward function application, this did not often occur in the results from experiment 1 and seems less likely in general given the available categories in c. ## discussion and conclusion we introduce an induction model that learns a basic categorial grammar from unlabeled data. the original version of the model, tested in experiment 1, shows promising results in several runs, but inconsistent performance in general. a modified version of the model that consistently uses forward func-tion application far outperforms the original model. in general, the experimental results appear to support the empiricist claim that syntactic structure is learnable with relatively simple prior knowledge. while results from the biased model achieve an impressive rh compared to @xcite , they leave open several questions. one obvious question is whether it is possible to consistently achieve comparable results to the biased runs without removing the model's ability to do backward function application, since this operation is a core ingredient of basic categorial grammars and is regularly used in hand-labeled parses of english sentences, e.g., to combine the np and n\np in figure 1 . although the log likelihood objective on its own appears to be insufficient to ensure stable behavior (similar to behavior reported in earlier pcfg studies such as @xcite , it may be possible to find a middle ground between experiments 1 and 2 with a modified objective function or a weaker form of bias. another question is whether the induction model can support more complex operations, such as the forward and backward composition operations defined by ccg. this seems possible in principle; additional weight matrices could be added to equation (12), so that probabilities for additional operations could be learned. we are excited to explore this possibility in future work.