2.6.1 Theory of grammar

In Section 1, we reviewed different theories used to formalise the notion of a grammar. We classified all studies describing practical implementation of grammar induction with respect to the underlying grammatical theory. We could identify three classes of theoretical views underlying the implementation. They are

1. A. Formal-generative grammar implementations which explicitly learn a system of rules or constraints that describe how lexical items are arranged in order to form a grammatical sentence.

2. B. Functional-cognitive grammar implementations in which the linguistic capacity is explicitly modelled as an inductive process based on language use in practice.

3. C. Theory-neutral implementations are amenable to be adapted to incorporate functional-cognitive insights.

We distinguished between functional-cognitive and theory-neutral implementations when the latter did not necessarily learn a usage-based representation of grammar as the output. We found that although domain-independent bottom-up methods can be used to extract usage-based schemas, most of these studies learnt a formal grammar with their output represented by the likes of constituency or dependency trees. Recognising such theory-neutral implementations thus becomes important because they can be adapted to learn fully usage-based grammar in an unsupervised fashion.

We found that the vast majority (22 out of 33) of the studies showed the influence of formal-generative school of thought in their parsing models. A top-down dependency grammar model for unsupervised parsing exemplifies this view. Given a sequence of words, the model starts with a head, attaches a sequence of arguments to the left or right and generates a dependency tree in a top-down manner. Here, the dependencies are formal syntactic relations which are defined a priori by linguistic theories and are learned statistically. Klein and Manning’s (Reference Kiperwasser and Yoav2004) corpus-based induction of syntactic structure laid the foundation for a statistical generative model to unsupervised dependency parsing. Overall, we found that there were 11 studies (out of 22) that implemented the top-down dependency model of grammar or its variations (Klein and Manning Reference Kiperwasser and Yoav2004; Headden, Johnson, and McClosky 2009; Sangati Reference Saffran2010; Spitkovsky, Alshawi, and Jurafsky Reference Spitkovsky, Alshawi and Jurafsky2010, Reference Taylor, Marcus and Santorini2011, Reference Taylor, Marcus and Santorini2012; Boonkwan and Steedman Reference Boonkwan and Steedman2011; Dominguez and Infante-Lopez Reference Ellefson and Christiansen2011; Gillenwater et al. Reference Hajic, Hajicová, Panevová, Sgall, Bojar, Cinková, Fucíková, Mikulová, Pajas, Popelka and Semecký2011; Mareček and Žabokrtský Reference Levine and Meurers2012a, Reference Matthiessen and Halliday2012b). The remaining 11 implementations (out of 22) adopted different methods to learn formal grammar. They are described below.

Snyder, Naseem, and Barzilay (Reference Skinner2009) learn constituency trees using an unordered tree alignment model where word alignments from bilingual corpora with their parts of speech (POS) are used as features to loosely bind the parallel trees from different languages. An exemplar-based approach to unsupervised parsing was proposed by Dennis (Reference Dennis2005) where the parse tree of the target sentence is obtained by aligning it with nearest-neighbour exemplar sentences and choosing a constituency tree with minimum cost for alignment. There were three studies that used distributed representations of words in deriving the parsed trees. One was by Brooks (Reference Brooks2006) where distributional representation of words was used to segment text into constituents and heuristics were then applied to reduce the number of possible candidates (Brooks Reference Brooks2006). Seginer’s algorithm (2007) captures the skewness of syntactic trees in its syntactic representation, restricts the search space by processing utterances incrementally (like humans do) and relies on the Zipfian distribution of words to guide its parsing decisions. The other study was Søgaard’s (Reference Solan, Horn, Ruppin and Edelman2011) implementation which presents a very different approach to unsupervised dependency parsing. They explore the view that dependency structure can be treated as a partial order on the nodes in terms of saliency or centrality. Their implementation assigns a dependency structure to a sequence of n words in two stages. In the first stage, they decorate n-nodes with word forms and distributional clusters, construct a directed acyclic graph in O(n ²) and rank the nodes using iterative graph-based ranking (Brin and Page Reference Brin and Page1998). In the second stage, a parse tree is constructed from the ranked list of words (Søgaard Reference Solan, Horn, Ruppin and Edelman2011). Another implementation of Ponvert, Baldridge, and Erk (Reference Pollard and Sag2011) starts with learning chunks using standard probabilistic finite state models and then cascades this chunker to achieve constituent parsing. Two studies used heuristic models (Araujo and Santamaría Reference Araujo and Santamaría2010; Santamaria and Araujo Reference Sangati2010). One study used clustering approach and explicit formal syntactic features to learn constituency trees (Reichart and Rappoport Reference Radford2008). Reichart and Rappoport (Reference Radford2008) propose a labelled grammar induction by starting from POS tags, followed by the induction of initial brackets, subsequently labelling them and finally clustering the label outputs using syntactic features. There were two studies (Adriaans, Trautwein, and Vervoort Reference Adriaans, Trautwein and Vervoort2000; Jin et al. Reference Kaiser and Trueswell2018) that treat parsing as a task of learning the probabilistic CFGs (PCFGs). In summary, these 22 studies exhibit the formal-generative view either implicitly or explicitly.

Only three studies explicitly considered grammar as a usage-based system and modelled the grammar induction process from this theoretical perspective. The use of a construction grammar induction algorithm is an example of this type of implementation (Dunn Reference Dunn2017a, Reference Dunn2017b). Given a corpus of sentences, this method statistically allows all potential linguistic generalisations from the observed sentences and chooses the optimal inventory of construction slots that can generalise them. In one study, Dunn (Reference Dunn2017a) demonstrates the learnability and falsifiability of construction grammar. Learnability is the degree to which the optimum set of constructions can be consistently selected from the large set of potential constructions; falsifiability is the ability to make testable predictions about the constructions present in a dataset. The study evaluates these two by performing an induction task. In another study, the same author describes in detail how a construction grammar learner can be implemented and evaluated (Dunn Reference Dunn2017b). An algorithm that achieves this using frequency and association measures of co-occurrence at multiple levels of analysis (lexical, syntactic and semantic levels) is proposed. Marques and Beuls (Reference Mareček and Žabokrtský2016) propose proof-of-concept evaluation strategies for computational construction grammars. They take inspiration from existing measures in semantic parsing and machine translation and propose two new metrics for this evaluation task. These three studies complete discussion of grammar induction or evaluation from an explicit usage-based view thus showing their compatibility with functional-cognitive school.

Finally, the remaining eight studies proposed methods that can learn significant usage patterns bottom up, but they were explicitly not framed to learn usage-based grammars. These methods were used to learn constituency trees and CFG rules and evaluated against formal syntactic annotated trees. The ideas themselves need not be tied to learning formal syntactic trees and can be easily adapted to incorporate ideas from functional-cognitive theories. We call such studies theory-neutral. In our review, we found two major implementation methods that were theory-neutral. First method was ADIOS algorithm, which incrementally learns a model of morphosyntax from raw input by distilling structural regularities and contextual cues. At the end of learning, a directed multigraph containing an abstraction of patterns, which can in turn be represented as context-free writing rules, is produced. The second method was data-oriented parsing (DOP) where an unsupervised DOP model allows all possible binary trees to be built bottom up and computes the most probable tree from the shortest derivations of sentences. This model can be used to explain both rule-based and exemplar-based properties of a natural language.

There were four studies which used the approach of ADIOS to learn significant syntactic rules from data without any annotation whatsoever (not even POS tags) (Solan et al. Reference Snyder, Naseem and Barzilay2004; Edelman et al. Reference Edelman, Solan, Horn and Ruppin2005; Berant et al. Reference Berant, Gross, Mussel, Sandbank, Ruppin and Edelman2007; Brodsky and Waterfall Reference Brooks2007). One of these implementations by Brodsky and Waterfall (Reference Brooks2007) proposed a method for evaluating the grammar learned by the ADIOS system even in the absence of any gold treebank for quantitative evaluation, or human judgement for qualitative evaluation. Their observation is that when two highly constrained models, which are trained on disjoint corpora, agree very closely on the acceptability of a given test sentence, it cannot be coincidental. An agreement between two such models indicates that the scoring of acceptability based on this agreement is correct. This was the basis of their evaluation method.

For DOP and its variations, we identified four implementations in our review (Bod Reference Bod2006, Reference Bod2009; Zuidema 2006; Post and Gildea Reference Ponvert, Baldridge and Erk2013). The authors point out that their implementation methodology is compatible with the usage-based theoretical views such as construction grammar, but they have used the method to learn constituency trees and evaluate them against a gold treebank. By allowing all possible binary tree substructures that combine to form the final parse tree through a formal operation called labelled substitution, DOP obtains the optimal parse by computing the most probable tree from among the shortest derivations of sentences. We consider these eight studies as theory-neutral implementations.

2.6.2 Representing grammatical productivity

We have previously introduced the notion of grammatical productivity as the speaker’s capacity to produce novel utterances of virtually limitless length using a finite number of linguistic resources at hand. In our review, we noticed that there were two ways to represent grammatical productivity in all studies considered. They are

1. A. Hierarchical arrangement of productive linguistic units, for example, constituency and dependency trees.

2. B. Non-hierarchical representation of productive units, for example, sequence of construction slots.

We found that 31 out of 33 studies represent grammatical productivity hierarchically, whereas the remaining two studies do it non-hierarchically (Table 3). Here, we noticed that the 22 studies that take the generative-formal view of grammar represent this productive capacity of natural language as a constituency tree or a directed dependency tree with either phrasal hierarchy or the head-dependent relations. The three studies on construction grammar implementation and evaluation represent their output as a sequence of construction slots, which is non-hierarchical. The study itself fills the construction slots with phrase structure heads which are indeed hierarchical. This might raise the question as to why this output is considered non-hierarchical. The rationale is that the study indeed allows all types of information, from lexical to semantic, to fill its construction slots and demonstrates the feasibility of learning construction grammar. In the larger scheme of the paper, we recognise that the authors learn the construction grammar with various co-occurrence metrics and therefore the fact that phrase structures are filled as entries in the construction slots does not make it central to the idea of construction slot itself. The construction slot representation is perfectly compatible with any type of assembly of symbols which are non-hierarchical. It is not inherently motivated to be filled with formal phrasal heads, and hence we identify the three studies as showing non-hierarchical approach to representing grammatical productivity. Finally, the eight studies that are theory-neutral in the sense defined in the previous Section 2.6.1 represent their output hierarchically. The four DOP implementations learned how phrases should be attached in a constituency hierarchy. In the four ADIOS implementations, the structural patterns distilled from the data are equivalent to the recursive phrase structure rules.

2.6.3 Processing grammatical productivity

The next aspect that we assessed was how the processing of grammatical structure was treated in each study. We identified two approaches:

1. A. Incremental processing

2. B. Non-incremental processing

In this study, by incremental processing of grammatical productivity, we mean that the analysis of grammatical structure of a sentence is incrementally updated when new sequences of words are observed; not a model which starts with all the n words w1, w2… wn and which treats parsing as establishing or filling the grammatical relations between those n words. As discussed in Section 2.6, in incremental decoding even partial non-sentences can have their parse, not all words of the sentence need be available before parsing begins. When the decoding itself is incremental in an implementation, we call the processing of grammatical productivity incremental. Otherwise, it is non-incremental. Incremental parsing is psycholinguistically motivated. Data synthesis revealed that several experimental and theoretical studies deemed incremental parsing suitable for grammar induction (Cramer Reference Cramer2007; Frank, Bod, and Christiansen Reference Frank, Bod and Christiansen2012). According to functional-cognitive school, grammatical structure of a sentence is almost entirely overt and it does not conceal a deeper level of grammatical organisation (Langacker Reference Lakoff1987 pp.46–47). A sharp distinction between competence (speaker’s mental grammar) and performance (sentence production and processing) is also not maintained (Jensen Reference Jensen2014). Cognitive grammar literature also proposes incremental contribution of components to the holistic conceptual structure of a text (Harrison et al. Reference Harrison, Nuttall, Stockwell and Yuan2014 pp. 22,100). These properties make functional-cognitive school compatible with the psycholinguistic literature. Although generative grammars can also be used to parse a sentence incrementally, the grammar formalism and derivation/parsing strategy are divorced. As mentioned in Section 1, ‘mechanisms for accessing and deriving phrase structure rules require additional computational modules which are quite distinct and divorced from the core competence grammar modules described by the generative grammar frameworks’.

In our review, we found that 32 out of 33 studies were non-incremental in processing the grammatical productivity, whereas one study learned grammar incrementally. The reason to distinguish these two types is to see if an implementation can be extended to incorporate functional-cognitive insights. The incremental parsing algorithm by Seginer (Reference Schabes, Roth and Osborne2007) uses a new link representation for syntactic structure which allows a prefix of an utterance to be parsed before the full utterance has been read.

It should be noted that there could be studies where the unsupervised model that learns significant grammatical patterns could be incrementally trained. Corpus-level incremental training is an important consideration for any scheme of grammar learner. However, we explicitly did not consider it a factor of analysis in this section because its importance is equally relevant for grammar learners of any theoretical persuasion. We wanted to understand what aspects can reveal the influence of one grammatical school or the other. For example, ADIOS method extracts statistical patterns incrementally from a corpus of sentences. When new sentences are observed in the corpus, the algorithm learns new patterns and updates the directed multigraph. However, to decode the parse of a target sentence, the entire sequence of words of the target sentence is considered non-incrementally. We do not count such studies as processing the grammatical productivity in an incremental fashion.

2.6.4 Output representation

The next aspect of analysis is the output representation of the grammatical structure of a sentence. We identified six types of output representations from the 33 studies. They are

1. A. Constituency trees

2. B. Dependency trees

3. C. A directed multigraph

4. D. Construction slots or templates

5. E. Transient structure

6. F. Common cover link set

Let us consider an example sentence and illustrate these output representations. For a sentence ‘The man cut an apple with a knife’, the various output representations after grammar induction are illustrated in Figures 3–6.

Figure 3. Constituency representation.

Figure 4. Dependency representation.

A constituency tree shows the phrase structures that make up the sentence. In this analysis, every sentence is broken down into smaller phrases which combine with other such phrases to form a larger phrase until the entire sentence is analysed as well formed according to the phrase structure rules. This is shown in Figure 3.

In dependency analysis, a sentence is analysed in terms of the words (constituents) and their relationships. A dependency tree is a directed graph where each node is a word (constituent), child nodes are marked as dependents of parent nodes and the edges between the dependents and heads indicate their syntactic relationship. This is shown in Figure 4.

Figure 5. An initial directed multigraph for a simple corpus of three sentences.

Figure 6. Transient structure.

ADIOS implementations learn a directed multigraph where incremental update of usage patterns is done based on structural similarities and statistical information present in the text. In this technique, frequent strings of similar structure are treated as significant patterns and these patterns are treated as ‘Equivalent Classes’ which means members of the same equivalent class are valid alternatives in a usage pattern. ADIOS algorithm repeatedly applies its pattern recognition algorithm on all sentences in a text and outputs one directed multigraph showing both patterns and equivalent classes. A sample directed multigraph with just three sentences is shown below in Figure 5. More details can be obtained from Solan et al. Reference Snyder, Naseem and Barzilay2004, Edelman et al. Reference Edelman, Solan, Horn and Ruppin2005, Berant et al. Reference Berant, Gross, Mussel, Sandbank, Ruppin and Edelman2007 and Brodsky and Waterfall Reference Brooks2007.

Constructions are productive and schematic form-meaning mappings that differ in their size, level of schematicity and their internal complexity. When it comes to construction grammar, the difficulty is not so much about the representation of constructions as much it is about learning and evaluation of these constructions. One representation that we identified in our review is a simple sequence of construction slots. For the given example, a construction slot sequence could be [NN PHRASE – VB PHRASE – NN PHRASE – PREP PHRASE] or [NP < ANIMATE> – VB< TRANSFER> – NP < ANIMATE> – NP ] or [NN – “give” – NP < ANIMATE> – “a piece of” – NP < ANIMATE> – “mind”]. It should be noted that the construction slot can be filled with phrasal heads, semantic information and idioms, lexical information and so on. It is not tied to any particular type of formal linguistic category. These slots can be filled with any type of symbolic assembly with a meaningful form-function mapping. In our review, we found that the implementations adopting this output structure are compatible with functional-cognitive school of thought even though the authors themselves have used syntactic and semantic parse information to demonstrate that construction grammars are indeed learnable. More about the learning method and its relevance for future research is discussed in Section 4.

In computational linguistics, it is common to view both linguistic production and parsing in terms of a chain of consecutive operations over the linguistic structure. This chain of operations is called a transient structure in fluid construction grammar. There was one study in our review which used transient structure as its output representation after parsing (Marques and Beuls Reference Mareček and Žabokrtský2016). An example of a transient structure is shown in Figure 6.

Seginer (Reference Schabes, Roth and Osborne2007) introduced a representation of syntactic structure that is similar to dependency structure but suitable for incremental parsing. It is based on links between a pair of words and it defines the shortest common cover link sets for a given utterance and its bracketing. An example of the shortest common cover link set for a sentence is given in Figure 7. Although it looks like a dependency structure, there are two differences. The first difference is in the linking of the noun phrase ‘the boy’ where the link goes back and forth between the two words, which is not the case in a dependency tree. The second difference is based on the property called adjacency, which makes connection between ‘know’ and ‘the’. Such a connection does not occur in a standard dependency tree.

Figure 7. Shortest common cover link set.

The distribution of the output representations for the 33 studies is shown in Figure 8 and Table 3. It can be seen from this distribution that overwhelmingly 25 studies out of 33 represent their outputs in the form of constituency or dependency trees.

Figure 8. Output representations.

2.6.5 Evaluation strategies

The following evaluation strategies have been extrapolated from the 33 studies considered:

1. A. Comparison against the gold standard.

2. B. Performance of the learner in grammaticality judgement tasks.

3. C. Comparison of models trained on disjoint corpora with respect to sentence acceptability.

4. D. Qualitative evaluation.

5. E. Maximum coverage, minimum size and stability measures for a usage-based grammar.

6. F. Output is compared against an artificial grammar that generated the test corpus.

Comparing the system output against the gold standard is a widely used method for evaluating performance of NLP systems. In the context of formal grammars, this strategy requires a treebank, a parsed corpus in which each sentence is manually annotated with syntactic relations to be used as the gold standard. Here, the treebank annotations need to be compatible with the system output, for example, if the system learns a directed dependency tree as its output representation, then the gold standard also needs to be annotated with the directed dependencies. Manual annotation involves a variety of activities such as defining an annotation schema, writing annotation guidelines, training experts for the annotation task and achieving consensus (Neves and Ševa Reference Moshier2019). Consequently, this time-consuming and labour-intensive process may create a bottleneck in this evaluation strategy when application-specific annotations or data are required. In addition, given the inductive nature of usage-based grammars, the use of a gold standard, which inevitably reflects the theoretical commitments of human annotators, seems counter-intuitive (Clark and Lappin Reference Clark and Lappin2010). Nonetheless, we observed that the majority of practical implementations (25 out of 33) were evaluated against the gold standard treebank. This was facilitated by the fact that most methods considered represented their outputs as either constituency or dependency trees for which the existing treebanks such as Penn Treebank or Prague English Dependency Treebank can be re-used.

Alternatively, a grammar induction system can be evaluated by testing how well it performs in grammaticality judgement tasks. For example, Goteborg multiple choice test consists of 100 sentences, each containing an open slot. There would be three choices for each question and one of them should be filled in the open slot for the sentence to make the sentence grammatical. If a system has learned the grammar of a language, the open slot would be filled with the correct option. Solan et al. (Reference Snyder, Naseem and Barzilay2004) and Edelman et al. (Reference Edelman, Solan, Horn and Ruppin2005) subjected their systems to such tasks in the form of multiple choice questions used in English as Second Language (ESL) classes. The authors demonstrated that as the number of sentences processed by the system increased so did the proportion of multiple choice questions answered correctly. The performance of the system proposed by Solan et al. (Reference Snyder, Naseem and Barzilay2004) was also compared against that of a bigram language model, that is, a language model where probability distribution of every two-word sequences in a text is calculated. The ADIOS model outperformed the bigram model by answering 60% of questions correctly which is equivalent to the average score of 9th grade ESL students. The bigram precision benchmark is 45%. This is an extrinsic evaluation of the grammar induction system by looking at its performance in the context of its application. Unlike the gold standard evaluation, this pragmatic approach does not constrain the system by conformance to the existing theoretical frameworks and in that respect seems to be better aligned with the usage-based nature of grammars considered.

Similarly, in an attempt to remove the constraint of a priori imposed grammatical structures, Brodsky and Waterfall (Reference Brooks2007) base their evaluation on an assumption that it is highly unlikely for two highly constrained models trained on disjoint corpora to coincidentally agree on whether a sentence is grammatically acceptable or not. This idea is similar to that of inter-annotator agreement, where, in the absence of ground truth, high reliability implies validity. In other words, if two independently produced outputs agree, then it is considered to be valid. The authors have proposed a precision-testing scheme based on the above observation. We, however, suggest making use of existing inter-annotator agreement measures, which take into account chance agreement.

Whereas all of the above evaluation strategies use quantitative measures of performance, Dunn (Reference Dunn2017b) proposes a qualitative assessment of representative examples of constructions from various subsets of corpus in addition to the quantitative evaluation metrics. Representative examples of constructions learnt by the system could be as follows: [Wh-Determiner] + [Modal] + “be” + [Past-Participle] is a productive schematic representation generalised from multiple usages in the corpus such as ‘that will be provided’, ‘that can be played’, ‘which will be represented’, ‘that should be made’. Qualitatively, one can verify that this schema covers relative clauses with passive verbs that generalises to many complementisers and modal verbs. However, as we can see, the above schema does not cover relative clauses with various tense forms. In this manner, many other schematic representations, such as “to” + [Verb] + [Determiner] + [Noun], [Noun] + [Preposition] + [Determiner] + <religion>, [Preposition] + “the” + <location>, can be analysed from various subsets of the corpus to see how good are they close to speaker intuitions and what type of generalisations these schemas represent. The problem with qualitative evaluation is obviously the human effort involved in manually checking the representative construction patterns from various subsets of corpus. Also, ascertaining what constitutes a reasonably good number of representative examples for evaluation poses a problem. The question of the psychological validity of the schemas arises when an individual evaluates the constructions.

Subsequently, the same author presented their quantitative evaluation metrics to evaluate the construction learner (Dunn Reference Edelman, Solan, Horn and Ruppin2017a, Reference Edelman, Solan, Horn and Ruppin2017b). They proposed 14 multi-unit association measures whose frequency and association strength can be used to quantify a model of constructions. From many potential construction grammars that could be learnt, they used the degree of coverage and the size of grammar to choose an optimal grammar.

Finally, a Context Free Grammar (CFG) learnt by the system can be compared against the original CFG used to generate the test sentences. Edelman et al. (Reference Edelman, Solan, Horn and Ruppin2005) evaluated their system using this method. A handcrafted CFG was used to generate a corpus of sentences, a large portion of which is used for training and the other smaller portion is used for testing. The system learns a set of patterns which can be equivalently represented as context-free rules. The rules learnt by the system are compared against the manually defined rules. This approach suffers from a similar drawback as the gold standard approach. The idea of developing a grammar to generate a large gold standard automatically avoids the drawbacks of generating gold standard annotations and can measure the degree to which unsupervised approaches can recreate complex models. However, any such grammar will always be an approximation and as such may not be representative of a language studied. Even more so, knowing that natural languages are mildly context-sensitive (Joshi Reference Joshi, Dowty, Karttunen and Zwicky1985), the use of CFGs for this purpose may not be sufficient.

Comparison of systems based on their performance should consider the differences in datasets used for evaluation. There are distinctions between evaluations done on artificial datasets produced with handcrafted CFG rules, sentences used in English as a Second Language (ESL) multiple choice questions, Child Language Data Exchange System (CHILDES) datasets and broad coverage datasets. For grammar induction, this determines how hard the task may be. Table 4 shows the factors that are relevant to apply an evaluation strategy and marks which factors are applicable to which methods. The distribution of the number of papers adopting these different methods of evaluation in their work is shown in Figure 9.

Table 4. Factors relevant for evaluation

E1 – Comparing against gold standard treebank annotation.

E2 – Performance of the learner in grammaticality judgement tasks.

E3 – Train two highly constrained models on disjoint corpora and evaluate how they agree or disagree on sentence acceptability.

E4 – Qualitative evaluation.

E5 – Maximum coverage, minimum size and stability measures for a usage-based grammar.

E6 – Agreement with CFG grammar that generated the learning data.

Figure 9. Evaluation strategies.

2.6.6 Features used for learning

A feature in machine learning is defined as some characteristic of the problem studied. In linguistic applications of machine learning, features can be words themselves or their properties, which can be provided a priori (e.g., gold standard annotations or lexica), engineered by applying domain knowledge (e.g., named entity formation patterns) or inferred automatically (e.g., stem, embedding, etc.). Different studies used various features to learn the grammatical structure. As the focus of this review is on unsupervised approaches, we are interested primarily in those features that can be extracted from the raw data automatically, possibly by external tools, and subsequently utilised by a learning algorithm. For example, POS tags were frequently provided as features for the grammar inducers before learning (Klein and Manning Reference Kiperwasser and Yoav2004; Dennis Reference Dennis2005; Bod Reference Bod2006; Zuidema 2006; Reichart and Rappoport Reference Radford2008; Bod Reference Bod2009; Headden et al. Reference Headden, Johnson and McClosky2009; Snyder et al. Reference Skinner2009; Araujo and Santamaría Reference Araujo and Santamaría2010; Sangati Reference Saffran2010; Santamaria and Araujo Reference Sangati2010; Spitkovsky et al. Reference Spitkovsky, Alshawi and Jurafsky2010; Boonkwan and Steedman Reference Boonkwan and Steedman2011; Dominguez and Infante-Lopez Reference Ellefson and Christiansen2011; Gillenwater et al. Reference Hajic, Hajicová, Panevová, Sgall, Bojar, Cinková, Fucíková, Mikulová, Pajas, Popelka and Semecký2011; Mareček and Žabokrtský Reference Mareček and Žabokrtský2012b; Dunn Reference Dunn2017a; Dunn Reference Dunn2017b). Rarely are such features extracted by the induction model itself. For instance, Jin et al. (Reference Kaiser and Trueswell2018) described a Bayesian Dirichlet model of depth-bounded PCFG induction where the model induces the categories for constituents and tree structures from the raw text provided as input.

Of course, richer linguistic features are likely to result in better grammar induction models. Spitkovsky et al. (Reference Taylor, Marcus and Santorini2011) use punctuation as a feature to improve the standard dependency model with valence (DMV) and in 2012 the same authors (Spitkovsky et al. Reference Yang2012) propose that capitalisation cues can improve dependency grammar induction. The general idea behind these implementations is that orthographic cues and their boundaries can help improve the grammar induction performance. In this way, we have identified eight types of commonly used features:

1. A. POS

2. B. Distributional representation of words

3. C. Head, valence and direction of attachment

4. D. Word alignments in parallel corpora

5. E. Chunks

6. F. Orthographic cues

7. G. Heuristic rules

8. H. Construction association measures

Most features are straightforward and are used in various studies irrespective of other aspects of implementation. POS tags indicate the grammatical category of the words in a text. For example, the sentence ‘The man cut an apple with a knife’ can be tagged as follows: ‘The/DT man/NN cut/VBD an/DT apple/NN with/IN a/DT knife/NN./.', where the POS tags DT, NN, VBD and IN indicate the grammatical categories determiner, noun, verb and preposition, respectively. These tags are taken into account when dividing a sentence into non-overlapping regions of text called chunks, which are typically non-recursive. For example, the same sentence can be chunked as [The man] [cut] [an apple] [with a knife].

Table 5. Features used in various studies

POS tags were used as features in 18 studies (shown in Table 5). Ponvert et al. (Reference Pollard and Sag2011) used chunking based on a probabilistic finite state model such as Hidden Markov model (HMM). The chunker is cascaded to achieve constituent parsing. Head, valence and direction of attachment are the parameters that are used in generative models of dependency parsing introduced by Klein and Manning (Reference Kiperwasser and Yoav2004) and used in nine other studies. Word alignment refers to the task of extracting translation equivalents of words from sentence-aligned bilingual corpora, that is, corpora where the same set of sentences in the source language are aligned with the same sentence in a target language. Word alignments are typically used as features in machine translation. In our review, we observed that this feature is used for grammar induction by Snyder et al. (Reference Skinner2009).

Distributional representation of words gives a probability distribution of a word occurring in a context when a centre word is given. The distributed representation of words is used in five studies (Adriaans et al. Reference Adriaans, Trautwein and Vervoort2000; Klein and Manning Reference Kiperwasser and Yoav2004; Brooks Reference Brooks2006; Seginer Reference Schabes, Roth and Osborne2007; Søgaard Reference Solan, Horn, Ruppin and Edelman2011). Orthographic cues such as capitalisation and punctuation are used as features in two studies (Spitkovsky et al. Reference Taylor, Marcus and Santorini2011, Reference Yang2012).

Features that we have listed as heuristic rules and construction association measures need explanation. There were four studies (Araujo and Santamaría Reference Araujo and Santamaría2010; Santamaria and Araujo Reference Sangati2010; Boonkwan and Steedman Reference Boonkwan and Steedman2011; Marques and Beuls Reference Mareček and Žabokrtský2016) which used different features: (a) identifying a set of POS tags as separator tags and using these separator tags as features to identify phrase structure boundaries, (b) encoding prior linguistic knowledge as a small number of syntactic prototypes and using them as features and (c) use handcrafted rules to learn artificial construction grammar. We see that these different features can be generalised as heuristics exploited by the authors based on their observations of linguistic patterns. We classified these different implementations as using heuristic rules as features of grammar induction. There were two studies (Dunn Reference Dunn2017a, Reference Dunn2017b) which used 14 different association measures to identify what sequence of construction patterns qualify as actual constructions rather than being potential constructions. These two studies use construction association measures as features for their learning in addition to other features.

We noticed that POS tags, morphological and orthographic cues are very generic features that are not tied to any particular implementation methodology. Although a fully unsupervised grammar induction uses no syntactic information, POS tags are typically used in most implementations (18 out of 33 studies). Orthographic cues such as capitalisation and punctuations are easier to obtain from a large corpus which can then be used in conjunction with other features to improve the overall accuracy. However, orthographic cues obtained from English are not readily transferred to languages such as Thai which do not mark punctuations or word boundaries consistently and even sentence boundaries are not indicated by any discernible cue like full stops. Another observation is that a purely distribution-based approach to grammar induction does not generalise to effectively learn syntax from raw text. Brooks (Reference Brooks2006) showed that using a method of attachment to form constituents is more effective than distribution analysis alone. Other features such as valence (number and types of arguments taken by a word linguistically), direction of attachment, word alignments, and chunks are again used to learn constituency and dependency trees. The heuristics such as separator tags and sub-separator tags proposed by Araujo and Santamaría (Reference Araujo and Santamaría2010) can be automatically extracted from the corpus and can improve constituent parsing. Table 5 shows the list of features and the studies which use those features.

2.6.7 Methodologies

Finally, we generalise the methodologies used to support grammar induction into the following categories:

1. A. Top-down dependency grammar models

2. B. Similarity or exemplar-based models

3. C. Distribution-based models

4. D. Clustering

5. E. Heuristic approaches

6. F. ADIOS

7. G. PCFG

8. H. Chunkers and their extensions

9. I. DOP

10. J. Construction grammar induction

Let us first define these categories. Top-down dependency grammar models start with a head and generate a sequence of arguments left and right conditioned on the head, valence and direction of attachment. As already discussed in Section 2.6.1, 10 studies incorporated generative dependency model or its variation in their implementations (Klein and Manning Reference Kiperwasser and Yoav2004; Sangati Reference Saffran2010; Spitkovsky et al. Reference Spitkovsky, Alshawi and Jurafsky2010, Reference Taylor, Marcus and Santorini2011, Reference Yang2012; Boonkwan and Steedman Reference Boonkwan and Steedman2011; Dominguez and Infante-Lopez Reference Ellefson and Christiansen2011; Søgaard Reference Solan, Horn, Ruppin and Edelman2011; Mareček and Žabokrtský Reference Marques and Beuls2012a, Reference Matthiessen and Halliday2012b). One of the successful baselines for unsupervised parsing is the DMV model of Klein and Manning (Reference Kiperwasser and Yoav2004). In exemplar-based approaches, the parse of a sentence is viewed as a set of alignments with exemplars from memory. Approximately nearest-neighbour exemplars and their parse are exploited in identifying the parse of the target sentence. Two studies followed this similarity or exemplar-based implementation methodology (Dennis Reference Dennis2005; Snyder et al. Reference Skinner2009).

Distribution-based models use word vectors to derive the parse. There were three studies which employed these in their implementations (Brooks Reference Brooks2006; Seginer Reference Schabes, Roth and Osborne2007; Søgaard Reference Solan, Horn, Ruppin and Edelman2011). Clustering approaches in general involve dividing the data points into groups where members in each group are more similar to one another than to those in the other group. In NLP, clustering typically involves grouping of grammatical elements of a sentence into groups such as POS clusters, morph clusters, and so on. There are two studies in our review which involved clustering as a part of grammar induction (Adriaans et al. Reference Adriaans, Trautwein and Vervoort2000; Reichart and Rappoport Reference Radford2008).

Heuristic approaches employ practical methods which yield near-optimal solutions to a problem where a perfectly acceptable optimal solution is not available or too difficult to obtain. Examples of heuristic methods are educated guesses, intuitive judgements, rule of thumb, etc. In our review, we identified two studies which involve heuristic methods to recognise phrase boundaries to form bracketed structures (Araujo and Santamaría Reference Araujo and Santamaría2010; Santamaria and Araujo Reference Sangati2010). ADIOS is a method which distils structural regularities and contextual cues from raw text, identifies equivalence classes of usage patterns from these structural regularities and represents this learning as a directed multigraph. This multigraph can be equivalently represented as context-free rules which represent the grammar learnt by the system. This methodology was used in four studies in our review (Solan et al. Reference Snyder, Naseem and Barzilay2004; Edelman et al. Reference Edelman, Solan, Horn and Ruppin2005; Berant et al. Reference Berant, Gross, Mussel, Sandbank, Ruppin and Edelman2007; Brodsky and Waterfall Reference Brooks2007).

PCFGs are context-free production rules that generate valid strings in a language. It is a type of formal grammar which is learnt by three studies in our review (Adriaans et al. Reference Adriaans, Trautwein and Vervoort2000; Headden et al. Reference Headden, Johnson and McClosky2009; Jin et al. Reference Kaiser and Trueswell2018). Chunkers and their extensions begin with learning bracketed structures or shallow parsing and subsequently proceed to use them to induce the full grammar. There was one study in our review that cascades chunkers with HMM to achieve constituent parsing (Ponvert et al. Reference Pollard and Sag2011). Next method is DOP which is an interesting way to approach grammar. Usually, statistical methods of grammar induction start with a predefined grammar and use the corpus to estimate rule probabilities. In DOP, no prior grammar is assumed but uses corpus fragments to induce grammar. DOP models sentence structures based on the observed frequencies of sentence fragments without imposing any constraint on the size of such fragments. There were four studies which implemented grammar induction bottom up using DOP method (Bod 2006, Reference Bod2009; Zuidema 2006; Post and Gildea Reference Ponvert, Baldridge and Erk2013).

Finally construction grammar induction is a fully usage-based approach to grammar which learns form-meaning pairings called constructions. Constructions are mappings between linguistic form and linguistic function which can be from any level of generalisation such as at the lexical level, phrase level, semantic level, and so on. Learning a construction grammar from raw corpus is difficult because constructions can be of any size and they can be internally complex. Dunn (Reference Dunn2017a) demonstrates that construction grammars are learnable and falsifiable by providing a model of learning an optimal construction grammar from a raw corpus. The same author (Dunn Reference Dunn2017b) presents a detailed implementation and evaluation method of the CG implementation. The distribution of these 10 methods from our list of 33 implementations is shown in Figure 10 and Table 3.

Figure 10. Grammar induction methods.

Among these methods, we identified that the top-down dependency grammar models and the PCFGs are used in multiple studies (13 out of 33) to learn formal dependency and constituency trees, respectively. As far as usage-based automatic grammar induction was concerned, we recognised four methodologies as relevant and useful: ADIOS, DOP and construction grammar induction. ADIOS is shown to be successful for inducing patterns from short sentences but exhibits limitations in parsing complex sentences. The ADIOS method can be successfully applied once the complex sentences are split into multiple simple ones. DOP works like an analogy-based pattern-matching technique which analyses a sentence by looking up the nearest-neighbour constituent structure already stored in memory. The nearest-neighbour for a given analysis is defined as the constituency tree derivation which shares the largest number of common nodes. DOP takes a corpus of sentences and allows all possible subtrees to be built from a sentence and chooses an optimal parse by computing the tree which leads to the shortest derivation. DOP is good but it is computationally expensive because it allows all possible subtrees theoretically. Although the subsequent DOP models reduced this computational space significantly in comparison to the general-case DOP, the complexity increases with sentence length. The core idea from DOP that abstract linguistic rules such as movement, agreement and discontiguous phrases can be learnt from recursive tree structures and an analogical match algorithm is powerful. However, the analogical matching that DOP employs starts with the assumption of constituent tree structures whose internal nodes can be substituted with analogous candidates. How to adapt DOP ideas without assuming constituent tree structures a priori is open for future exploration.

Among the studies considered, we noticed that construction grammar induction is the only method which demonstrated a fully usage-based, bottom-up approach to grammar induction successfully. The evaluation strategies are also discussed in detail. Because the outputs are not the usual tree structures, but construction slots, evaluation against a gold standard is not possible. The qualitative and quantitative evaluation measures (construction association measures) discussed in these implementations can be adopted for usage-based implementations. Apart from these 33 implementation papers, there were 7 theoretical and experimental studies and there were 3 studies that provided surveys on grammar induction or parser evaluation. We will present our findings from these studies in the next section.