Deconstructing syntactic generalizations with minimalist grammars (2021)

Abstract: Within the currently dominant Minimalist framework for syntax (Chomsky, 1995, 2000), it is not uncommon to encounter multiple proposals for the same natural language pattern in the literature. We investigate the possibility of evaluating and comparing analyses of syntax phenomena, implemented as minimalist grammars (Stabler, 1997), from a quantitative point of view. This paper introduces a principled way of making linguistic generalizations by detecting and eliminating syntactic and phonological redundancies in the data. As proof of concept, we first provide a small step-by-step example transforming a naive grammar over unsegmented words into a linguistically motivated grammar over morphemes, and then discuss a description of the English auxiliary system, passives, and raising verbs produced by a prototype implementation of a procedure for automated grammar optimization.

## introduction marr's @xcite approach to understanding complex cognitive systems, including natural language, distinguishes between three levels of description: computational (abstract specification of what the system computes), algorithmic (structures representing the data and algorithms that manipulate them), and implementational (concrete realization of the algorithms in the hardware or wetware). linguistic theories are considered to be at the computational level @xcite or between the computational and algorithmic level @xcite . in particular, syntactic literature often omits lower-level details such as full descriptions of units and operations involved. this allows for a bird'seye view of the problem but leads to a lack of explicitness. while the body of work in this field holds tremendous empirical and theoretical value, there is no straightforward way to extract from it a ˚this paper is based on a chapter of the author's dissertation @xcite . how can one choose between various structures that could underlie the same linguistic construction based on some robust quantitative metric and in a way compatible with the insights of theoretical syntax? first, this task requires translating the data into an explicit formal representation. for this purpose, minimalist grammars @xcite are a natural choice. designed as a formalization of the minimalist program @xcite , they are compatible with analyses of syntax phenomena found in theoretical literature and provide a way to implement them as grammar fragments, explicitly defining syntactic units and operations. there exists a substantial amount of work on learning formal grammars from unstructured strings; see e.g. @xcite @xcite . these techniques are based on the notion of distributional similarity: in short, words found in the same contexts are assigned the same syntactic category. resulting algorithms can make plausible generalizations based on observable data; however, they are of limited applicability if the goal is to produce results similar to those of theoretical syntax, which is heavily reliant on highly abstract concepts. two broad considerations are particularly illustrative in this respect: ‚ empty categories. null dps of various flavors, null heads such as complementizers, traces/unpronounced copies are commonplace in the literature, even though none of them are directly visible in the raw data. however, works on grammar induction tend to avoid silent elements altogether. for example, classical categorial grammars in @xcite are defined over an alphabet of constant symbols and cannot derive the empty string, and @xcite ) explicitly prohibit rules with empty right-hand sides. in order to focus on these and similar issues, rather than use unstructured sentences as input, we start with a grammar defined over unsegmented words and in a maximally theory-neutral way. the goal is to refine it, producing an intuitively correct description accounting for the original data. unlike grammar induction, the focus is on capturing generalizations within the grammar rather than generalizing beyond the corpus; in fact, the output grammar is expected to generate the same string language as the input. to highlight this distinction, we refer to this task as grammar optimization. ## minimalist grammars we use a version of minimalist grammars (mgs) primarily based on @xcite . in order to define an mg, one has to fix an alphabet of phonological segments σ and a set of feature names base and to define a lexicon lex -a finite set of lexical items (lis). an li is a pair consisting of a phonological exponent and a sequence of syntactic features. 1 each syntactic feature is characterized by its name (drawn from base) and type, as shown in (1). selectors and licensors together are called attractors, and categories and licensees are attractees. the first feature of each li is accessible to the structure building operations, merge and move, that consume features with matching names to generate complex expressions from lex: the expression with the attractor becomes the head of the new expression; and the one with the attractee becomes its dependent. we label the parent node with ă if the head is on the left or ą if the head is on the right. matched features (indicated as x ) are deleted, making the next feature in the sequence accessible for syntactic operations. the dependent introduced by the first attractor of an li is its complement, and all subsequent dependents are specifiers. a complete expression of category x has no unchecked features left, except for x on its head. we will be primarily concerned with complete expressions of category t (for tense) and their string yields (sentences). note that, in order to arrive at a complete expression via merge and move, all lis involved must have feature sequences where all licensors and selectors precede the (unique) category feature, and all licensees follow it. consider two toy grammars (2), which generate the same set of sentences: in linguistic terms, (2a) treats each sentence as a single tp headed by an unsegmented verb (3a). in (2b) finite verbs are complex heads formed by head movement. the lexical verb directly selects its argument and forms a vp, while the suffix takes the vp as its complement and is responsible for moving the subject into its specifier position (3b). a convenient way to visualize head-complement relations within a lexicon is a directed multigraph where vertices are category features, and each edge corresponds to an li and connects the category of its complement to its own category. it ignores specifiers formed by merge and move, focusing on the subset of relations which are relevant for morphologically complex words. intuitively, ( 2b ) is an improvement over (2a). by recognizing internal structure within verbs, it captures similarities found within verbal paradigms (laughs, laughed vs. jumps, jumped) and across paradigms (laughs, jumps vs. laughed, jumped). on the other hand, (2a) misses all these generalizations. to account for a new verbal paradigm (e.g. smiles, smiled), we would need to add two new lis to ( 2a ), but only one to ( 2b ). how to express this intuition in quantitative terms? one common approach is based on the minimum description length principle @xcite . within linguistics, mdl has been used, among other examples, for induction of phonological constraints @xcite and ordered rules @xcite , morphological segmentation @xcite , and inferring syntactic categories given known morphological patterns @xcite . in this framework, the best grammar to describe a data corpus is the one that minimizes the sum of the following, both measured in bits: (i) size of the grammar and (ii) size of the corpus, as encoded by the grammar. an overfitting grammar, which makes few (or no) generalizations on the data, would have a very large grammar size and small (or zero) corpus size. at the other end of the spectrum, an overgenerating grammar, capable of producing any string at all, would itself be very small but require a lengthy encoding of the corpus. mdl strikes a balance by taking both considerations into account. we focus on grammar size here and will return to corpus size and the problem of overgeneration in section 5. to encode a minimalist lexicon, we use a straightforward encoding scheme (adapted from katzir 2014) which treats each li as a sequence of symbols followed by a separator. each syntactic feature is considered two symbols (corresponding to its type and name). letting t denote the set of syntactic feature types, the size of a lexicon lex over a set of categories base is given by we fix σ and t, with |t| " 7 and |σ| " 26 (σ being the set of english letters). then the above is a function of the number of lis and the following three metrics: ‚ |base|, the number of unique category features in lex; ‚ ř syn " ř s::δ p lex `|δ| ˘, the total count of syntactic features in lex; ‚ ř phon " ř s::δ p lex `|s| ˘, the total length of all string components in lex. separating roots and suffixes in (2b) comes at the cost of an extra category feature. however, this pays off by eliminating redundant strings, which reduces ř phon . moreover, four instances of +k are collapsed into two, yielding a small reduction of ř syn . these differences would be even more noticeable with a larger dataset, especially with respect to open-class words, since adding a new verb to ( 2a ) would have a higher cost (in both syntactic features and string components) compared to ( 2b ). ## decomposing lexical items how can we transition from a grammar over words such as (2a) to a grammar over morphemes such as (2b)? one way is to directly modify lis while keeping track of how the changes affect all structures that use them. for example, we can split the string component of laughed : : =d +k t (6a) into two substrings, laugh and ed, and its feature sequence @xmath0. we then assemble two useful lis from these elements by introducing x, a category feature that is fresh (i.e. not used before in the grammar), with head movement to combine them into a morphological word (6b). the same operation can be applied even if some or all of the splits result in empty sequences. for instance, we can split laugh : : =d x by assigning its entire string component to one li, and its feature sequence to another (6c). this creates a root with only the new feature y and shifts its selectional properties to an empty head. in each case, the new lis generate the same strings as the original ones. following (kobele, 2018, to appear), we define the operation of lexical item decomposition as a generalization of this idea. consider an arbitrary li w : : αβxγ, where w p σ ˚, α and β are sequences of licensors and selectors, x p base, and γ is a sequence of licensees. then it can be decomposed as follows: since the resulting structure has to behave as a single unit with respect to move, the split must take place to the left of the category feature. the original li is replaced with two new items, whose string components are u and v, along with a morphological rule generating w from u and v via some operation '. lexical item decomposition formalizes discovering structure within words. however, it cannot transform a grammar like (2a) into one like (2b) on its own. first, every split creates a fresh feature name, so each newly formed affix is only compatible with a single stem. second, decomposing lis in isolation is very permissive, and whether a given step is reasonable depends on other items in the lexicon. to recognize useful steps, decomposition needs to process multiple lis simultaneously, using similarities between them to inform its decisions. we will refer to this strategy as batch decomposition. in the rest of this section we build and expand on kobele's work to define a toolkit of operations over mgs. we adopt a simple model of morphology that defines ' as string concatenation, which renders morphological rules trivial. it is sufficient for cases like (6b), where w is cleanly separated into a stem and a suffix, or (6c), where the string component is not split at all, but not for irregular forms such as was or ran. consider the transition in (7). it starts with a batch of four lis and factors out the elements they have in common: the prefix laughand the syntac-tic @xmath1. these repeated elements are then expressed as a single new li, laugh : : =d x, adding only one new feature to base. this is an example of left decomposition, as the shared part of both the string component and feature sequence is on the left-hand side. similarly, right decomposition factors out right-hand side commonalities. in a (primarily) suffixal language such as english, left decomposition can be used to identify stems, and right decomposition to identify affixes. lis of the form -: : =>x y for any x, y p base, which we will refer to as category changers, are of special interest. in the general case, -: : =>x y represents the idea that expressions of category y have a more limited distribution than those of category x; that is, any x can freely become an y, but not necessarily the other way around. that said, some category changers can be eliminated while still allowing the grammar to generate all sentences it did before. for example, the distinction between x and v in (7) can be safely collapsed, essentially reversing the effects of decomposition for laugh : : =d v. another redundant configuration involves alternative paths through the grammar multigraph consisting exclusively of category changers. in order to deal with these, we introduce two auxiliary operations that target and delete category changers and are convenient to describe in (multi)graph terms: contraction, which removes an edge and merges the two vertices it previously joined, and deletion, which removes an edge as long as there is another path of category changers from its origin to its destination vertex. ## towards a grammar over morphemes the following example shows how the operations introduced in the previous section can be used to transform a naive word-based grammar into one over morphemes by making generalizations about word structure. we start with a small lexicon of unsegmented words encoding a fragment of the english auxiliary system (8). focusing on syntax and morphotactics, we abstract away from morphological irregularities of english and replace each word with a sequence of morphemes formed by string concatenation; in particular, is is rendered as bes, and will as wills. we continue using |base|, ř syn , and ř phon , along with grammar size in bits, to keep track of how each transition changes the complexity of the lexicon. we begin by decomposing lexical verbs. the three lis targeted in (9) share the prefix laughand the first syntactic @xmath2. batch decomposition factors out these commonalities, associating them with the fresh feature f1 (highlighted in boldface). similarly, (10) decomposes the forms of jump, introducing another fresh feature, f2. the lexicon now contains two copies each of -s, -, and -ing. the two instances of -ing share the entire string component, and we can associate their syntactic differences, =>f1 vs. =>f2, with empty heads (11). each decomposition step made so far immediately pays off in terms of ř phon , but adds a new category to base and increases ř syn . note that contraction in general has a potential for overgeneration. for example, contracting -: : =>f1 v in (11) instead would have created a path from v back to f3, generating the infinite set of ungrammatical sentences *mary wills be pbeingq laughing. the lis targeted in (13) share the suffix -s and the sequence of syntactic features +k t. by factoring out these commonalities, we create what is essentially a dedicated tense projection. since the batch shares more than one syntactic feature, this decomposition step immediately reduces ř syn and keeps ř phon the same. mary : : d -k -s : : =>f5 +k t be : : =g f5 will : : =v f5 be : : =g v -: : =>f4 f5 -ing : : =>f4 g -: : =>f4 v laugh : : =d f4 jump : : =d f4 this grammar still contains two partially redundant instances of be. we decompose them in ( 14 ). ( 14 ) left decomposition of be : : =g f5, be : : =g v mary : : d -k -s : : =>f5 +k t -: : =>f6 f5 be : : =g f6 will : : =v f5 -: : =>f6 v -: : =>f4 f5 -ing : : =>f4 g -: : =>f4 v laugh : : =d f4 jump : : =d f4 collapsing f6 and v into f7 in (15) has created a path of category changers from f4 to f5, which opens the path for deletion (16) of the empty li directly connecting these two categories, -: : =>f4 f5. this last step finally pushes ř syn below the value it had in (13). the decision to decompose the two instances of be rather than leave them intact took two more steps to fully pay off. mary : : d -k -s : : =>f5 +k t -: : =>f7 f5 be : : =g f7 will : : =f7 f5 -ing : : =>f4 g -: : =>f4 f7 laugh : : =d f4 jump : : =d f4 the final lexicon (16) produces more complex structures, treating each verb as a multimorphemic word. it captures a number of correct generalizations: the roots in both verbal paradigms have been identified and separated from inflectional morphology, and they share the same syntactic category. a lexical verb can be selected (directly or via category changers) by -ing, will, or -s, whereas a phrase headed by will can only be selected by -s. these improvements are reflected in the metrics ( 17 ): the new lexicon beats the original in terms of both ř syn and ř phon , at the expense of two features added to base. (17) |base| ř syn ř phon grammar original (8) 5 24 49 565.54 final (16) 7 19 23 375.03 ## automated decomposition in the previous section we has shown how a linguistically plausible grammar over morphemes can, in principle, be obtained from a naive one over unsegmented words -or, in other words, that the desired output is in the search space defined by the operations introduced in section 2. the next logical step is to automate the process of finding it. to this end, we have developed a prototype python implementation of an optimization procedure for mgs. foot_2 it starts with a grammar over words, similar to the one in (8), and uses beam search to navigate the space of grammars. while mdl is a natural choice for a cost function to evaluate candidate grammars, we have found that this metric as typically defined does not perform as expected on smaller grammars generating finite languages (due to its sensitivity to relative sizes of the grammar and corpus), and its variations that put additional emphasis on corpus cost lead to under-generalization and worse overall results. 3 because of this, our implementation uses grammar size in bits as the cost function. to control overgeneration, instead of corpus size, it utilizes a heuristic constraining the application of contraction. 4 when applied to the lexicon in ( 8 ), the procedure does converge exactly to a grammar identical to ( 16 ) up to feature names. this is both expected and encouraging, as it indicates a connection between conciseness (as defined by grammar size) and naturalness of a grammar. a larger sample input and output are given as multigraphs in figures 1 and 2 , respectively. the output compresses the auxiliary system, making use of category changers to implement hierarchical relations between categories. it collapses each verbal paradigm into a single lexical verb assigned a feature sequence according to its distribution: intransitive (dance, laugh...), transitive (praise, like...), verb with a clausal complement (declare, think...), or raising verb (seem, appear). all proper nouns and most lexical verbs carry a single category feature, and their syntactic requirements are supplied by lis that select them. this is consistent with the idea of acategorial roots having to merge with a categorizing head, which is a general assumption in distributed morphology @xcite and, from the quantitative perspective, a beneficial strategy especially for open-class items. in general, we observe a tendency to push syntactic differences between lis into empty functional heads. as a concrete illustration, consider the raising verb seem. the input includes a separate li for each of its forms; moreover, seem in constructions with raising and expletive it is treated as unrelated lis. for instance, the derivations of mary seems to smile (3a) and it seems that mary smiles (3b) involve, respectively, seems : : =to +k t and seems : : =c1 +k t. after optimization (4) both paradigms are collapsed into a single root li carrying just the category feature: seem : : 6. the distinction between the the verbs' selection requirements (=to vs. =c1) is now carried by empty categorizing heads which take the root as their complement: ## conclusion this paper outlines an approach to formalizing and automating the intuition behind generalizations in natural language syntax. building upon the idea of lexical item decomposition, we have defined a set of basic operations over minimalist lexica and demonstrated how complex, intuitively correct and quantitatively optimal analyses arise through repeated application of easily interpretable steps. from a broader perspective, the intent of this project is twofold. on the one hand, it seeks to enable computational learning of natural language to make use of the insights and theoretical devices developed in the linguistic literature. the second goal is to show how mainstream syntax can benefit from a formally explicit approach. in this paper we have taken a step towards both by capturing some aspects of intuitive goodness of syntactic descriptions and connecting it to the more easily definable notion of quantitative goodness.