Modelling function words improves unsupervised word segmentation

Traditional descriptive linguistics distinguishes function words, such as determiners and prepositions, from content words, such as nouns and verbs, corresponding roughly to the distinction between functional categories and lexical categories of modern generative linguistics [].

Function words differ from content words in at least the following ways:

1. 1.

   there are usually far fewer function word types than content word types in a language

2. 2.

   function word types typically have much higher token frequency than content word types

3. 3.

   function words are typically morphologically and phonologically simple (e.g., they are typically monosyllabic)

4. 4.

   function words typically appear in peripheral positions of phrases (e.g., prepositions typically appear at the beginning of prepositional phrases)

5. 5.

   each function word class is associated with specific content word classes (e.g., determiners and prepositions are associated with nouns, auxiliary verbs and complementisers are associated with main verbs)

6. 6.

   semantically, content words denote sets of objects or events, while function words denote more complex relationships over the entities denoted by content words

7. 7.

   historically, the rate of innovation of function words is much lower than the rate of innovation of content words (i.e., function words are typically “closed class”, while content words are “open class”)

Properties 1–4 suggest that function words might play a special role in language acquisition because they are especially easy to identify, while property 5 suggests that they might be useful for identifying lexical categories. The models we study here focus on properties 3 and 4, in that they are capable of learning specific sequences of monosyllabic words in peripheral (i.e., initial or final) positions of phrase-like units.

A number of psychological experiments have shown that infants are sensitive to the function words of their language within their first year of life [], often before they have experienced the “word learning spurt”. Crucially for our purpose, infants of this age were shown to exploit frequent function words to segment neighboring content words []. In addition, 14 to 18-month-old children were shown to exploit function words to constrain lexical access to known words –- for instance, they expect a noun after a determiner []. In addition, it is plausible that function words play a crucial role in children’s acquisition of more complex syntactic phenomena [], so it is interesting to investigate the roles they might play in computational models of language acquisition.

Adaptor grammars are a framework for Bayesian inference of a certain class of hierarchical non-parametric models []. They define distributions over the trees specified by a context-free grammar, but unlike probabilistic context-free grammars, they “learn” distributions over the possible subtrees of a user-specified set of “adapted” nonterminals. (Adaptor grammars are non-parametric, i.e., not characterisable by a finite set of parameters, if the set of possible subtrees of the adapted nonterminals is infinite). Adaptor grammars are useful when the goal is to learn a potentially unbounded set of entities that need to satisfy hierarchical constraints. As section 2 explains in more detail, word segmentation is such a case: words are composed of syllables and belong to phrases or collocations, and modelling this structure improves word segmentation accuracy.

Adaptor Grammars are formally defined in , which should be consulted for technical details. Adaptor Grammars (AGs) are an extension of Probabilistic Context-Free Grammars (PCFGs), which we describe first. A Context-Free Grammar (CFG) $G=\left(N,W,R,S\right)$ consists of disjoint finite sets of nonterminal symbols $N$ and terminal symbols $W$, a finite set of rules $R$ of the form $A\to \alpha$ where $A\in N$ and $\alpha \in {\left(N\cup W\right)}^{\star }$, and a start symbol $S\in N$. (We assume there are no “$ϵ$-rules” in $R$, i.e., we require that $\left|\alpha \right|\ge 1$ for each $A\to \alpha \in R$).

A Probabilistic Context-Free Grammar (PCFG) is a quintuple $\left(N,W,R,S,𝜽\right)$ where $N$, $W$, $R$ and $S$ are the nonterminals, terminals, rules and start symbol of a CFG respectively, and $𝜽$ is a vector of non-negative reals indexed by $R$ that satisfy ${\sum }_{\alpha \in R_A}{\theta }_{A\to \alpha }=1$ for each $A\in N$, where $R_A=\left\{A\to \alpha :A\to \alpha \in R\right\}$ is the set of rules expanding $A$.

Informally, ${\theta }_{A\to \alpha }$ is the probability of a node labelled $A$ expanding to a sequence of nodes labelled $\alpha$, and the probability of a tree is the product of the probabilities of the rules used to construct each non-leaf node in it. More precisely, for each $X\in N\cup W$ a PCFG associates distributions $G_X$ over the set of trees ${𝒯}_X$ generated by $X$ as follows:

If $X\in W$ (i.e., if $X$ is a terminal) then $G_X$ is the distribution that puts probability 1 on the single-node tree labelled $X$.

If $X\in N$ (i.e., if $X$ is a nonterminal) then:

where $R_X$ is the subset of rules in $R$ expanding nonterminal $X\in N$, and:

That is, ${\mathrm{\text{TD}}}_X\left(G_1,\mathrm{\dots },G_n\right)$ is a distribution over the set of trees ${𝒯}_X$ generated by nonterminal $X$, where each subtree $t_i$ is generated independently from $G_i$. The PCFG generates the distribution $G_S$ over the set of trees ${𝒯}_S$ generated by the start symbol $S$; the distribution over the strings it generates is obtained by marginalising over the trees.

In a Bayesian PCFG one puts Dirichlet priors $\mathrm{Dir}\left(𝜶\right)$ on the rule probability vector $𝜽$, such that there is one Dirichlet parameter ${\alpha }_{A\to \alpha }$ for each rule $A\to \alpha \in R$. There are Markov Chain Monte Carlo (MCMC) and Variational Bayes procedures for estimating the posterior distribution over rule probabilities $𝜽$ and parse trees given data consisting of terminal strings alone [].

PCFGs can be viewed as recursive mixture models over trees. While PCFGs are expressive enough to describe a range of linguistically-interesting phenomena, PCFGs are parametric models, which limits their ability to describe phenomena where the set of basic units, as well as their properties, are the target of learning. Lexical acqusition is an example of a phenomenon that is naturally viewed as non-parametric inference, where the number of lexical entries (i.e., words) as well as their properties must be learnt from the data.

It turns out there is a straight-forward modification to the PCFG distribution (1) that makes it suitably non-parametric. As explain, by inserting a Dirichlet Process (DP) or Pitman-Yor Process (PYP) into the generative mechanism (1) the model “concentrates” mass on a subset of trees []. Specifically, an Adaptor Grammar identifies a subset $A\subseteq N$ of adapted nonterminals. In an Adaptor Grammar the unadapted nonterminals $N\setminus A$ expand via (1), just as in a PCFG, but the distributions of the adapted nonterminals $A$ are “concentrated” by passing them through a DP or PYP:

Here $a_X$ and $b_X$ are parameters of the PYP associated with the adapted nonterminal $X$. As explain, such Pitman-Yor Processes naturally generate power-law distributed data.

Informally, Adaptor Grammars can be viewed as caching entire subtrees of the adapted nonterminals. Roughly speaking, the probability of generating a particular subtree of an adapted nonterminal is proportional to the number of times that subtree has been generated before. This “rich get richer” behaviour causes the distribution of subtrees to follow a power-law (the power is specified by the $a_X$ parameter of the PYP). The PCFG rules expanding an adapted nonterminal $X$ define the “base distribution” of the associated DP or PYP, and the $a_X$ and $b_X$ parameters determine how much mass is reserved for “new” trees.

There are several different procedures for inferring the parse trees and the rule probabilities given a corpus of strings: describe a MCMC sampler and describe a Variational Bayes procedure. We use the MCMC procedure here since this has been successfully applied to word segmentation problems in previous work [].

The rule (3) models words as sequences of independently generated phones: this is what called the “monkey model” of word generation (it instantiates the metaphor that word types are generated by a monkey randomly banging on the keys of a typewriter). However, the words of a language are typically composed of one or more syllables, and explicitly modelling the internal structure of words typically improves word segmentation considerably.

suggested replacing (3) with the following model of word structure:

Here and below superscripts indicate iteration (e.g., a $\mathrm{𝖶𝗈𝗋𝖽}$ consists of 1 to 4 $\mathrm{𝖲𝗒𝗅𝗅𝖺𝖻𝗅𝖾}$s), while an $\mathrm{𝖮𝗇𝗌𝖾𝗍}$ consists of an unbounded number of $\mathrm{𝖢𝗈𝗇𝗌𝗈𝗇𝖺𝗇𝗍}$s), while parentheses indicate optionality (e.g., a $\mathrm{𝖱𝗁𝗒𝗆𝖾}$ consists of an obligatory $\mathrm{𝖭𝗎𝖼𝗅𝖾𝗎𝗌}$ followed by an optional $\mathrm{𝖢𝗈𝖽𝖺}$). We assume that there are rules expanding $\mathrm{𝖢𝗈𝗇𝗌𝗈𝗇𝖺𝗇𝗍}$ and $\mathrm{𝖵𝗈𝗐𝖾𝗅}$ to the set of all consonants and vowels respectively (this amounts to assuming that the learner can distinguish consonants from vowels). Because $\mathrm{𝖮𝗇𝗌𝖾𝗍}$, $\mathrm{𝖭𝗎𝖼𝗅𝖾𝗎𝗌}$ and $\mathrm{𝖢𝗈𝖽𝖺}$ are adapted, this model learns the possible syllable onsets, nucleii and coda of the language, even though neither syllable structure nor word boundaries are explicitly indicated in the input to the model.

The model just described assumes that word-internal syllables have the same structure as word-peripheral syllables, but in languages such as English word-peripheral onsets and codas can be more complex than the corresponding word-internal onsets and codas. For example, the word “string” begins with the onset cluster str, which is relatively rare word-internally. showed that word segmentation accuracy improves if the model can learn different consonant sequences for word-inital onsets and word-final codas. It is easy to express this as an Adaptor Grammar: (4) is replaced with (10–11) and (12–17) are added to the grammar.

In this grammar the suffix “$𝖨$” indicates a word-initial element, and “$𝖥$” indicates a word-final element. Note that the model simply has the ability to learn that different clusters can occur word-peripherally and word-internally; it is not given any information about the relative complexity of these clusters.

point out the detrimental effect that inter-word dependencies can have on word segmentation models that assume that the words of an utterance are independently generated. Informally, a model that generates words independently is likely to incorrectly segment multi-word expressions such as “the doggie” as single words because the model has no way to capture word-to-word dependencies, e.g., that “doggie” is typically preceded by “the”. Goldwater et al show that word segmentation accuracy improves when the model is extended to capture bigram dependencies.

Adaptor grammar models cannot express bigram dependencies, but they can capture similiar inter-word dependencies using phrase-like units that calls collocations. showed that word segmentation accuracy improves further if the model learns a nested hierarchy of collocations. This can be achieved by replacing (2) with (18–21).

Informally, $\mathrm{𝖢𝗈𝗅𝗅𝗈𝖼𝟣}$, $\mathrm{𝖢𝗈𝗅𝗅𝗈𝖼𝟤}$ and $\mathrm{𝖢𝗈𝗅𝗅𝗈𝖼𝟥}$ define a nested hierarchy of phrase-like units. While not designed to correspond to syntactic phrases, by examining the sample parses induced by the Adaptor Grammar we noticed that the collocations often correspond to noun phrases, prepositional phrases or verb phrases. This motivates the extension to the Adaptor Grammar discussed below.

The starting point and baseline for our extension is the adaptor grammar with syllable structure phonotactic constraints and three levels of collocational structure (5-21), as prior work has found that this yields the highest word segmentation token f-score [].

Our extension assumes that the $\mathrm{𝖢𝗈𝗅𝗅𝗈𝖼𝟣}-\mathrm{𝖢𝗈𝗅𝗅𝗈𝖼𝟥}$ constituents are in fact phrase-like, so we extend the rules (19–21) to permit an optional sequence of monosyllabic words at the left edge of each of these constituents. Our model thus captures two of the properties of function words discussed in section 1.1: they are monosyllabic (and thus phonologically simple), and they appear on the periphery of phrases. (We put “function words” in scare quotes below because our model only approximately captures the linguistic properties of function words).

Specifically, we replace rules (19–21) with the following sequence of rules:

This model memoises (i.e., learns) both the individual “function words” and the sequences of “function words” that modify the $\mathrm{𝖢𝗈𝗅𝗅𝗈𝖼𝟣}-\mathrm{𝖢𝗈𝗅𝗅𝗈𝖼𝟥}$ constituents. Note also that “function words” expand directly to $\mathrm{𝖲𝗒𝗅𝗅𝖺𝖻𝗅𝖾𝖨𝖥}$, which in turn expands to a monosyllable with a word-initial onset and word-final coda. This means that “function words” are memoised independently of the “content words” that $\mathrm{𝖶𝗈𝗋𝖽}$ expands to; i.e., the model learns distinct “function word” and “content word” vocabularies. Figure 1 depicts a sample parse generated by this grammar.

This grammar builds in the fact that function words appear on the left periphery of phrases. This is true of languages such as English, but is not true cross-linguistically. For comparison purposes we also include results for a mirror-image model that permits “function words” on the right periphery, a model which permits “function words” on both the left and right periphery (achieved by changing rules 22–24), as well as a model that analyses all words as monosyllabic.

Section 4 explains how a learner could use Bayesian model selection to determine that function words appear on the left periphery in English by comparing the posterior probability of the data under our “function word” Adaptor Grammar to that obtained using a grammar which is identical except that rules (22–24) are replaced with the mirror-image rules in which “function words” are attached to the right periphery.

Here we evaluate the word segmentations found by the “function word” Adaptor Grammar model described in section 2.3 and compare it to the baseline grammar with collocations and phonotactics from . Figure 2 presents the standard token and lexicon (i.e., type) f-score evaluations for word segmentations proposed by these models [], and Table 1 summarises the token and lexicon f-scores for the major models discussed in this paper. It is interesting to note that adding “function words” improves token f-score by more than 4%, corresponding to a 40% reduction in overall error rate.

When the training data is very small the Monosyllabic grammar produces the highest accuracy results, presumably because a large proportion of the words in child-directed speech are monosyllabic. However, at around 25 sentences the more complex models that are capable of finding multisyllabic words start to become more accurate.

It’s interesting that after about 1,000 sentences the model that allows “function words” only on the right periphery is considerably less accurate than the baseline model. Presumably this is because it tends to misanalyse multi-syllabic words on the right periphery as sequences of monosyllabic words.

The model that allows “function words” only on the left periphery is more accurate than the model that allows them on both the left and right periphery when the input data ranges from about 100 to about 1,000 sentences, but when the training data is larger than about 1,000 sentences both models are equally accurate.

As noted earlier, the “function word” model generates function words via adapted nonterminals other than the $\mathrm{𝖶𝗈𝗋𝖽}$ category. In order to better understand just how the model works, we give the 5 most frequent words in each word category found during 8 MCMC runs of the left-peripheral “function word” grammar above:

$\mathrm{𝖶𝗈𝗋𝖽}:$

book, doggy, house, want, I

$\mathrm{𝖥𝗎𝗇𝖼𝖶𝗈𝗋𝖽𝟣}:$

a, the, your, little¹¹ The phone ‘l’ is generated by both $\mathrm{Consonant}$ and $\mathrm{Vowel}$, so “little” can be (incorrectly) analysed as one syllable., in

$\mathrm{𝖥𝗎𝗇𝖼𝖶𝗈𝗋𝖽𝟤}:$

to, in, you, what, put

$\mathrm{𝖥𝗎𝗇𝖼𝖶𝗈𝗋𝖽𝟥}:$

you, a, what, no, can

Interestingly, these categories seem fairly reasonable. The $\mathrm{𝖶𝗈𝗋𝖽}$ category includes open-class nouns and verbs, the $\mathrm{𝖥𝗎𝗇𝖼𝖶𝗈𝗋𝖽𝟣}$ category includes noun modifiers such as determiners, while the $\mathrm{𝖥𝗎𝗇𝖼𝖶𝗈𝗋𝖽𝟤}$ and $\mathrm{𝖥𝗎𝗇𝖼𝖶𝗈𝗋𝖽𝟥}$ categories include prepositions, pronouns and auxiliary verbs.

Thus, the present model, initially aimed at segmenting words from continuous speech, shows three interesting characteristics that are also exhibited by human infants: it distinguishes between function words and content words [], it allows learners to acquire at least some of the function words of their language (e.g. []); and furthermore, it may also allow them to start grouping together function words according to their category [].