Consistent Unsupervised Estimators for Anchored PCFG s (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. We show that if the grammar is anchored and satisfies additional restrictions on its ambiguity, then the parameters can be directly related to distributional properties of the anchoring strings; we show the asymptotic correctness of a naive estimator and present some simulations using synthetic data that show that algorithms based on this approach have good finite sample behavior.

## introduction this paper presents an approach for strongly learning a linguistically interesting subclass of probabilistic context-free grammars (pcfgs) from strings in the realizable case. unpacking this, we assume that we have some pcfg that we are interested in learning and that we have access only to a sample of strings generated by the pcfg (i.e., sampled from the distribution defined by the context-free grammar). crucially, we do not observe the derivation trees-the hierarchical latent structure. strong learning means that we want the learned grammar to define the same distribution over labeled trees as the original grammar and not just the same distribution over strings. clearly, there can be many structurally different pcfgs that define the same distribution over strings. consider for example the distribution that generates a single string of length 3 with prob-ability one and the various pcfgs that give rise to that same distribution; for these obvious reasons, that we discuss in more detail later, we cannot have an algorithm that does this for all pcfgs. accordingly, we define some sufficient conditions on pcfgs for this algorithm to perform correctly. more precisely, we define some simple structural conditions on the underlying cfgs (in section 3), and we will show that the resulting class of pcfgs is identifiable from strings, in the sense that any two pcfgs that define the same distribution over strings will be isomorphic. we then provide a computationally trivial learning algorithm in section 4, together with a proof that it will strongly learn every grammar in this class. the algorithm is not intended to be a realistic algorithm, but merely to illustrate the fundamental correctness of this general approach. we then show that general pcfgs in chomsky normal form (cnf) that approximate the observable properties of natural language syntax are efficiently learnable using some simulations with synthetic data in section 5. our primary scientific motivation is to understand the process of first-language acquisition, in particular the early phases of the acquisition of syntactic structure. importantly, the grammar is not just a decision procedure that classifies strings as being grammatical or ungrammatical, but additionally assigns a tree structure to the grammatical sentences, a structure the primary role of which is to support semantic interpretation. the standard view is that children learn the syntactic structure of their languages not by purely syntactic means, but rather by using information about the range of available interpretations, derived from the situational context of the sentences they hear and inferences about the intentions and goals of the speaker (e.g., @xcite . indeed there is ample direct evidence from the developmental psycholinguistics literature that this does in fact happen at certain stages of language acquisition: 409 transactions of the association for computational linguistics, vol. 8, pp. 409-422, 2020. https://doi.org/10.1162/tacl a 00323 action editor: mark-jan nederhof. submission batch: 11/2019; revision batch: 4/2020; published 7/2020. c 2020 association for computational linguistics. distributed under a cc-by 4.0 license. for example, @xcite showed that the acquisition of argument structure of verbs exploits semantic information about the verb and the arguments. however, the children in these experiments-the youngest cohort being nearly 4 years old-have already acquired a great deal of knowledge about english syntax. here, we are exploring an alternative or perhaps complementary hypothesis: namely, that the acquisition of the syntactic categories and rules of the language can to a certain extent be learned using only information derived from the surface strings without any appeal to external information about the hierarchical structure of the language that is being learned. in other words, the initial phases of language acquisition are based on purely syntactic information rather than the semantic bootstrapping discussed above. the contributions of this paper are as follows. first, we provide a reparameterization of pcfgs within the space of weighted context-free grammars (wcfgs) that we call bottom-up wcfgs. next, we define three structural conditions on cfgs and show that they imply the identifiability of the class of all pcfgs based on those grammars. we then present a naive computationally trivial estimator and prove its asymptotic consistency for that class of pcfgs. we present some experiments on synthetic grammars that show that a variant of this algorithm has good finite sample behavior. finally, we examine the extent to which these conditions are plausible, using a corpus of child-directed speech. ## definitions we assume we have a finite set of atomic symbols σ. the set of finite strings over this set is written σ * , nonempty finite strings are denoted by σ + , and the empty string is λ. we will typically write a, b, c, . . . for elements of σ and u, v, w, . . . for elements of σ * . a (formal) language l is a subset of σ * . a context is an ordered pair of strings, that is, an element of σ * × σ * that we write as l, r. if u, v are languages, then their concatenation is u v defined in the normal way, and we will also write uv where u is a string instead of {u}v and so on. given a fixed language l, we define for a set of strings u a set of contexts u ⊲ as if @xmath0. a stochastic language is a function p from σ * → [0, 1], such that @xmath1. note that the support of this distribution is a formal language as defined above. we assume for the rest of the paper that the expected length of strings drawn from this distribution is finite. we can define for some @xmath2, the expected number of times that u will occur as a substring in a string distributed according to p. we can also define, for a string u, its context distribution, which is a probability distribution over its contexts written d(u), whose support will be u ⊲ , given for l, @xmath3 ## identifiability we assume that we have a sequence of strings generated independently and identically distributed (i.i.d.) from some distribution generated by an unknown pcfg or wcfg, which we call the target grammar. we are interested in the problem of producing a pcfg from this input data that is close to the target pcfg; namely, the underlying cfg is isomorphic to the underlying cfg of the target grammar and additionally the parameters are within ǫ of the corresponding parameters of the target grammar: we call this being ǫ-close. two cfgs are isomorphic if they are identical apart from the labels of the nonterminals; the isomorphism is just a bijection between the nonterminals and productions in the natural way. definition 3.1. two wcfgs, g; θ and g ′ ; θ ′ , are ǫ-close if there is an cfg-isomorphism φ from g to g ′ such that for all @xmath4, more precisely, we say that a learning algorithm a is a consistent estimator for a class of globally normalized wcfgs, g, if for every wcfg, g * , θ * in the class, for every ǫ, δ > 0, there is an n such that if the algorithm receives a sample of m strings, sampled i.i.d. where @xmath5, θ such that with probability at least 1δ we have that ĝ, θ is ǫ-close to g * , θ * . ## naive estimators we now analyze the properties of a particular estimator that we call the naive plugin estimator, which we will show can learn all grammars in w a and p a . this approach uses a trivial manner of estimating the ρ values, and from this we derive a consistent estimator for the class. this approach has poor sample complexity but is algorithmically trivial. we will need to estimate the ρ divergences from a sample of strings drawn i.i.d. from the distribution defined by the grammar. given a sample of strings, the most naive approach is to estimate p(w) and e(a) by the empirical distribution, to estimate the ratio as the ratio of these estimates, and to take the supremum over the frequent contexts of a rather than over the infinite set a ⊲ . we are interested in convergence in probability, which we will write as xn @xmath6; in other words, for any ǫ, δ > 0, there is an n such that for all @xmath7, with probability greater than 1δ we have | xn -x| < ǫ. let w 1 , . . . , w n be the sample of n strings drawn i.i.d from a target pcfg, and let n(w) be the number of times that w occurs in the sample (as a whole string), and let m(w) be the number of times substring occurs as a substring; clearly, l,r n(lwr) = m(w). define p(w) = n(w)/n to be the empirical probability of w and ê(u) = m(w)/n to be the empirical expectation of u. clearly, for any string w we have p(w) note that ρn (@xmath8, r such that n(lar) > √ n , and n(lbcr) = 0. we can show the convergence of the estimators when one side is anchored, starting with the case when the divergence is infinite. lemma 4.1. for some g; θ ∈ w a suppose that a is an anchor for a nonterminal a and suppose that for some @xmath9, ρ(@xmath10. then for every δ > 0, there is an n such that with probability at least 1δ, ρn (@xmath11. similarly, if there is a c if ρ(@xmath12, there is an n such that with probability at least 1δ, ρn (@xmath13. lemma 4.2. for some g; θ ∈ w a suppose that a is an anchor for a nonterminal a, b for b, and c for c. if ρ(@xmath14, then for every δ > 0, there is an n such that with probability at least 1δ ρn (@xmath15. proof. if @xmath16. so @xmath17. by condition 3.3, there must be some context l * , r * in a ⊲ but not in (bc) ⊲ , and so for sufficiently large n , l * ar * will occur more than √ n times. lemma 4.3. for some g; θ ∈ w a suppose that a is an anchor for a nonterminal a. suppose ρ(@xmath18; then ρn (@xmath19 lemma 4.4. for some g; θ ∈ w a suppose that a is an anchor for a nonterminal a, b for b, and c for c; if ρ(@xmath20, then ρn (@xmath21 n and so we can use chernoff bounds in a standard way. ## applicability to natural language corpora an important question is whether this approach is directly applicable to natural language corpora either of transcribed child-directed speech or of 7 full code for reproducing these experiments is available at https://github.com/alexc17/locallearner . when we consider phrasal categories, the question of whether such nonterminals are anchored requires asking two questions: first, whether such nonterminals generate single words at all, and secondly whether among those words we can find anchors. the existence of pro-forms, such as pronouns in the case of noun phrases, guarantees this for at least some categories. clearly, this is genre-dependent, because it is sensitive to sentence length. here we look at the adam corpus of child-directed speech in english as syntactically annotated in the penn treebank style by @xcite . most fundamentally, simple pcfgs of the type that we consider here are very poor models of natural language syntax. in order to obtain reasonable results, such grammars need to be lexicalized because otherwise the independence assumptions of the pcfg are violated because of semantic relations, for example, between a verb and its subject. thus the realizability assumption the approach relies on is dramatically false. ## discussion and conclusion there are two ways of thinking about pcfgs: one is as a nontrivial cfg with parameters attached, where the support of the distribution is the language generated by the cfg, and the other is where the cfg is trivial, containing all possible productions, and where the support is the set of all strings; we can call these sparse and dense pcfgs, respectively. @xcite show that in the dense case the class of pcfgs is not identifiable without additional constraints, even when one can exclude a set of grammars of measure approach is only guaranteed to converge to a local maximum of the likelihood, and does not work well in practice. a related problem that we do not discuss in this paper is learning when the labeled tree structures are observed-essentially that of estimating a pcfg from a treebank, a problem which is algorithmically trivial and statistically well behaved, as @xcite show. the approach we take is most closely related to the work by @xcite and work on weakly learning cfgs from samples generated by pcfgs developed by @xcite . however, there are very few approaches to learning pcfgs with any nontrivial theoretical guarantees. the approach here is essentially an exemplarbased model: the syntactic categories are based on single strings of length 1. this can be naturally extended, mutatis mutandis, to sets of exemplars, and to exemplars with length greater than 1. the extension beyond cfgs to mildly context sensitive grammars such as mcfgs @xcite seems to present some problems that do not occur in the nonprobabilistic case @xcite ; although the same bounds on the bottom up parameters can be derived, identifying the set of anchors seems to be challenging. the variant of algorithm a discussed in section 5 is also interesting because it only uses local information in the initial phase: indeed, it only uses the bigram and trigram counts, and it is only in the use of the io algorithm that a pass through the data using the full sentence is used; this is compatible with psycholinguistic evidence about infants' abilities to track transitional probabilities (e.g., work following @xcite . of course the original version in section 4 uses complete sentences and not just the low-order counts. note that equation 10 provides some theoretical justification for the long literature @xcite on using mutual information as a heuristic for unsupervised chunking. although it is intuitively reasonable that chunks should correspond to subsequences that have high pointwise mutual information, it is gratifying to finally have some mathematical basis for these intuitions.