Beyond {Chomsky} Normal Form: Extending Strong Learning Algorithms for {PCFGs}

 Posted on Fri, Jan 1, 2021  |  Alexander Clark

Authors Clark, Alexander Year 2021 Abstract We extend a recent consistent strong learning algorithm for a subclass of probabilistic context-free grammars in Chomsky normal form, (Clark and Fijalkow, 2020) to a much larger class of grammars by weakening the normal form constraints to allow for a richer class of derivation structures that are not necessarily binary branching, including among other possibilities unary branching trees which introduce some technical difficulties. By modifying the structural conditions appropriately we obtain an algorithm which is computationally efficient, and a consistent estimator for the class of grammars defined. [Read More]
Context-free  Strong learning  Probabilistic 

Strong Learning of Probabilistic Tree Adjoining Grammars

 Posted on Fri, Jan 1, 2021  |  Alexander Clark

Authors Alexander Clark Year 2021 Abstract The problem of learning syntactic structure is notoriously difficult, especially with mildly context-sensitive grammars. Existing approaches to learning these types of grammars are limited – they are not guaranteed to learn the correct grammars or structures, only the correct derived structures whether these are trees or strings. Here we present some progress towards strong learning of these formalisms, extending a recent result on strong learning of probabilistic context-free grammars to a class of probabilistic context-free tree grammars that is weakly equivalent to Tree-Adjoining Grammars. [Read More]
Mildly context-sensitive  Strong learning  Probabilistic 

Strong learning of some Probabilistic Multiple Context-Free Grammars

 Posted on Fri, Jan 1, 2021  |  Alexander Clark

Authors Alexander Clark Year 2021 Abstract This paper presents an algorithm for strong learning of probabilistic multiple context free grammars from a positive sample of strings generated by the grammars. The algorithm is shown to be a consistent estimator for a class of well-nested grammars, given by explicit structural conditions on the underlying grammar, and for grammars in this class is guaranteed to converge to a grammar which is isomorphic to the original, not just one that generates the same set of strings. [Read More]
Mildly context-sensitive  Strong learning  Probabilistic 

Consistent Unsupervised Estimators for Anchored {PCFG}s

 Posted on Wed, Jan 1, 2020  |  Alexander Clark

Authors Clark, Alexander and Fijalkow, Nathana"el Year 2020 Abstract Learning probabilistic context-free grammars (PCFGs) from strings is a classic problem in computational linguistics since Horning (1969). Here we present an algorithm based on distributional learning that is a consistent estimator for a large class of PCFGs that satisfy certain natural conditions including being anchored (Stratos et al., 2016). We proceed via a reparameterization of (top-down) PCFGs that we call a bottom-up weighted context-free grammar. [Read More]
Mildly context-sensitive  Strong learning  Probabilistic 

Computational Learning of Syntax

 Posted on Sun, Jan 1, 2017  |  Alexander Clark

Authors Clark, Alexander Year 2017 Abstract Learnability has traditionally been considered to be a crucial constraint on theoretical syntax; however, the issues involved have been poorly understood, partly as a result of the lack of simple learning algorithms for various types of formal grammars. Here I discuss the computational issues involved in learning hierarchically structured grammars from strings of symbols alone. The methods involved are based on an abstract notion of the derivational context of a syntactic category, which in the most elementary case of context-free grammars leads to learning algorithms based on a form of traditional distributional analysis. [Read More]
Tutorial 

Grammaticality, Acceptability, and Probability: A Probabilistic View of Linguistic Knowledge

 Posted on Sun, Jan 1, 2017  |  Alexander Clark

Authors Lau, Jey Han and Clark, Alexander and Lappin, Shalom Year 2017 Abstract The question of whether humans represent grammatical knowledge as a binary condition on membership in a set of well-formed sentences, or as a probabilistic property has been the subject of debate among linguists, psychologists, and cognitive scientists for many decades. Acceptability judgments present a serious problem for both classical binary and probabilistic theories of grammaticality. These judgements are gradient in nature, and so cannot be directly accommodated in a binary formal grammar. [Read More]
Grammaticality  Syntactic knowledge  Probabilistic modeling 

Testing Distributional Properties of Context-Free Grammars

 Posted on Sun, Jan 1, 2017  |  Alexander Clark

Authors Alexander Clark Year 2017 Abstract Recent algorithms for distributional learning of context-free grammars can learn all languages defined by grammars that have certain distributional properties: the finite kernel property (FKP) and the finite context property (FCP). In this paper we present some algorithms for approximately determining whether a given grammar has one of these properties. We then present the results of some experiments that indicate that with randomly generated context-free grammars in Chomsky normal form, which generate infinite languages and are derivationally sparse, nearly all grammars have the finite kernel property, whereas the finite context property is much less common. [Read More]

Distributional Learning of Context-Free and Multiple Context-Free Grammars

 Posted on Fri, Jan 1, 2016  |  Alexander Clark

Authors Clark, Alexander and Yoshinaka, Ryo Year 2016 Abstract Natural languages require grammars beyond context-free for their description. Here we extend a family of distributional learning algorithms for context-free grammars to the class of Parallel Multiple Context-Free Grammars (PMCFGs). These grammars have two additional operations beyond the simple context-free operation of concatenation: the ability to interleave strings of symbols, and the ability to copy or duplicate strings. This allows the grammars to generate some non-semilinear languages, which are outside the class of mildly context-sensitive grammars. [Read More]
Mildly context-sensitive  Context-free  Tutorial 

Distributional Learning of Some Nonlinear Tree Grammars

 Posted on Fri, Jan 1, 2016  |  Alexander Clark

Authors Clark, Alexander and Kanazawa, Makoto and Kobele, Gregory M. and Yoshinaka, Ryo Year 2016 Abstract A key component of Clark and Yoshinaka’s distributional learning algorithms is the extraction of substructures and contexts contained in the input data. This problem often becomes intractable with nonlinear grammar formalisms due to the fact that more than polynomially many substructures and/or contexts may be contained in each object. Previous works on distributional learning of nonlinear grammars avoided this difficulty by restricting the substructures or contexts that are made available to the learner. [Read More]
Mildly context-sensitive  Copying 

Canonical Context-Free Grammars and Strong Learning: Two Approaches

 Posted on Thu, Jan 1, 2015  |  Alexander Clark

Authors Clark, Alexander Year 2015 Abstract Strong learning of context-free grammars is the problem of learning a grammar which is not just weakly equivalent to a target grammar but isomorphic or structurally equivalent to it. This is closely related to the problem of defining a canonical grammar for the language. The current proposal for strong learning of a small class of CFGs uses grammars whose nonterminals correspond to congruence classes of the language, in particular to a subset of those that satisfy a primality condition. [Read More]