Contextual Dependencies in Unsupervised Word Segmentation
Sharon Goldwater and Thomas L. Griffiths and Mark Johnson Department of Cognitive and Linguistic Sciences Brown University Providence, RI 02912 {Sharon Goldwater,Tom Griffiths,Mark Johnson}@brown.edu

Abstract
Developing better methods for segmenting continuous text into words is important for improving the processing of Asian languages, and may shed light on how humans learn to segment speech. We propose two new Bayesian word segmentation methods that assume unigram and bigram models of word dependencies respectively. The bigram model greatly outperforms the unigram model (and previous probabilistic models), demonstrating the importance of such dependencies for word segmentation. We also show that previous probabilistic models rely crucially on suboptimal search procedures.

1 Introduction
Word segmentation, i.e., discovering word boundaries in continuous text or speech, is of interest for both practical and theoretical reasons. It is the first step of processing orthographies without explicit word boundaries, such as Chinese. It is also one of the key problems that human language learners must solve as they are learning language. Many previous methods for unsupervised word segmentation are based on the observation that transitions between units (characters, phonemes, or syllables) within words are generally more predictable than transitions across word boundaries. Statistics that have been proposed for measuring these differences include "successor frequency" (Harris, 1954), "transitional probabilities" (Saffran et al., 1996), mutual information (Sun et al.,
This work was partially supported by the following grants: NIH 1R01-MH60922, NIH RO1-DC000314, NSF IGERT-DGE-9870676, and the DARPA CALO project.


1998), "accessor variety" (Feng et al., 2004), and boundary entropy (Cohen and Adams, 2001). While methods based on local statistics are quite successful, here we focus on approaches based on explicit probabilistic models. Formulating an explicit probabilistic model permits us to cleanly separate assumptions about the input and properties of likely segmentations from details of algorithms used to find such solutions. Specifically, this paper demonstrates the importance of contextual dependencies for word segmentation by comparing two probabilistic models that differ only in that the first assumes that the probability of a word is independent of its local context, while the second incorporates bigram dependencies between adjacent words. The algorithms we use to search for likely segmentations do differ, but so long as the segmentations they produce are close to optimal we can be confident that any differences in the segmentations reflect differences in the probabilistic models, i.e., in the kinds of dependencies between words. We are not the first to propose explicit probabilistic models of word segmentation. Two successful word segmentation systems based on explicit probabilistic models are those of Brent (1999) and Venkataraman (2001). Brent's ModelBased Dynamic Programming (MBDP) system assumes a unigram word distribution. Venkataraman uses standard unigram, bigram, and trigram language models in three versions of his system, which we refer to as n-gram Segmentation (NGS). Despite their rather different generative structure, the MBDP and NGS segmentation accuracies are very similar. Moreover, the segmentation accuracy of the NGS unigram, bigram, and trigram models hardly differ, suggesting that contextual dependencies are irrelevant to word segmentation. How673

Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the ACL, pages 673­680, Sydney, July 2006. c 2006 Association for Computational Linguistics


ever, the segmentations produced by both these methods depend crucially on properties of the search procedures they employ. We show this by exhibiting for each model a segmentation that is less accurate but more probable under that model. In this paper, we present an alternative framework for word segmentation based on the Dirichlet process, a distribution used in nonparametric Bayesian statistics. This framework allows us to develop extensible models that are amenable to standard inference procedures. We present two such models incorporating unigram and bigram word dependencies, respectively. We use Gibbs sampling to sample from the posterior distribution of possible segmentations under these models. The plan of the paper is as follows. In the next section, we describe MBDP and NGS in detail. In Section 3 we present the unigram version of our own model, the Gibbs sampling procedure we use for inference, and experimental results. Section 4 extends that model to incorporate bigram dependencies, and Section 5 concludes the paper.

1 - p$ U  W U p$ U  W P (w) W w

w  

Figure 1: The unigram NGS grammar. where u consists of the words w1 . . . wn and p$ is the probability of the utterance boundary marker $. This model can be used to find the highest probability segmentation hypothesis h given the data d by using Bayes' rule: P (h|d)  P (d|h)P (h) NGS assumes a uniform prior P (h) over hypotheses, so its goal is to find the solution that maximizes the likelihood P (d|h). Using this model, NGS's approximate search technique delivers competitive results. However, the true maximum likelihood solution is not competitive, since it contains no utterance-internal word boundaries. To see why not, consider the solution in which p$ = 1 and each utterance is a single `word', with probability equal to the empirical probability of that utterance. Any other solution will match the empirical distribution of the data less well. In particular, a solution with additional word boundaries must have 1 - p$ > 0, which means it wastes probability mass modeling unseen data (which can now be generated by concatenating observed utterances together). Intuitively, the NGS model considers the unsegmented solution to be optimal because it ranks all hypotheses equally probable a priori. We know, however, that hypotheses that memorize the input data are unlikely to generalize to unseen data, and are therefore poor solutions. To prevent memorization, we could restrict our hypothesis space to models with fewer parameters than the number of utterances in the data. A more general and mathematically satisfactory solution is to assume a nonuniform prior, assigning higher probability to hypotheses with fewer parameters. This is in fact the route taken by Brent in his MBDP model, as we shall see in the following section. 2.2 MBDP MBDP assumes a corpus of utterances is generated as a single probabilistic event with four steps: 1. Generate L, the number of lexical types. 2. Generate a phonemic representation for each type (except the utterance boundary type, $).
674

2 NGS and MBDP
The NGS and MBDP systems are similar in some ways: both are designed to find utterance boundaries in a corpus of phonemically transcribed utterances, with known utterance boundaries. Both also use approximate online search procedures, choosing and fixing a segmentation for each utterance before moving onto the next. In this section, we focus on the very different probabilistic models underlying the two systems. We show that the optimal solution under the NGS model is the unsegmented corpus, and suggest that this problem stems from the fact that the model assumes a uniform prior over hypotheses. We then present the MBDP model, which uses a non-uniform prior but is difficult to extend beyond the unigram case. 2.1 N GS

NGS assumes that each utterance is generated independently via a standard n-gram model. For simplicity, we will discuss the unigram version of the model here, although our argument is equally applicable to the bigram and trigram versions. The unigram model generates an utterance u according to the grammar in Figure 1, so P (u) = p$ (1 - p$ )n-1 jn P (wj ) (1)

=1


3. Generate a token frequency for each type. 4. Generate an ordering for the set of tokens. In a final deterministic step, the ordered tokens are concatenated to create an unsegmented corpus. This means that certain segmented corpora will produce the observed data with probability 1, and all others will produce it with probability 0. The posterior probability of a segmentation given the data is thus proportional to its prior probability under the generative model, and the best segmentation is that with the highest prior probability. There are two important points to note about the MBDP model. First, the distribution over L assigns higher probability to models with fewer lexical items. We have argued that this is necessary to avoid memorization, and indeed the unsegmented corpus is not the optimal solution under this model, as we will show in Section 3. Second, the factorization into four separate steps makes it theoretically possible to modify each step independently in order to investigate the effects of the various modeling assumptions. However, the mathematical statement of the model and the approximations necessary for the search procedure make it unclear how to modify the model in any interesting way. In particular, the fourth step uses a uniform distribution, which creates a unigram constraint that cannot easily be changed. Since our research aims to investigate the effects of different modeling assumptions on lexical acquisition, we develop in the following sections a far more flexible model that also incorporates a preference for sparse solutions.

distribution G, which consists of a set of possible words (the lexicon) and probabilities associated with those words. G is generated from a DP(0 , P0 ) distribution, with the items in the lexicon being sampled from P0 and their probabilities being determined by 0 , which acts like the parameter of an infinite-dimensional symmetric Dirichlet distribution. We provide some intuition for the roles of 0 and P0 below. Although the DP model makes the distribution G explicit, we never deal with G directly. We take a Bayesian approach and integrate over all possible values of G. The conditional probability of choosing to generate a word from a particular lexical entry is then given by a simple stochastic process known as the Chinese restaurant process (CRP) (Aldous, 1985). Imagine a restaurant with an infinite number of tables, each with infinite seating capacity. Customers enter the restaurant and seat themselves. Let zi be the table chosen by the ith customer. Then  (z )  n k -i i-1+0 0  k < K (z-i ) (2) P (zi | z-i ) =  0 i-1+0 k = K (z-i ) where z-i = z1 . . . zi-1 , nk -i is the number of customers already sitting at table k, and K (z-i ) is the total number of occupied tables. In our model, the tables correspond to (possibly repeated) lexical entries, having labels generated from the distribution P0 . The seating arrangement thus specifies a distribution over word tokens, with each customer representing one token. This model is an instance of the two-stage modeling framework described by Goldwater et al. (2006), with P0 as the generator and the CRP as the adaptor. Our model can be viewed intuitively as a cache model: each word in the corpus is either retrieved from a cache or generated anew. Summing over all the tables labeled with the same word yields the probability distribution for the ith word given previously observed words w-i : P (wi | w-i ) =
(w ) (z )

3 Unigram Model
3.1 The Dirichlet Process Model

Our goal is a model of language that prefers sparse solutions, allows independent modification of components, and is amenable to standard search procedures. We achieve this goal by basing our model on the Dirichlet process (DP), a distribution used in nonparametric Bayesian statistics. Our unigram model of word frequencies is defined as wi | G G

0 P0 (wi ) n w i -i + i - 1 + 0 i - 1 + 0

(w

)

(3)

G| 0 , P0  DP(0 , P0 ) where the concentration parameter 0 and the base distribution P0 are parameters of the model. Each word wi in the corpus is drawn from a
675

where nw -i is the number of instances of w observed in w-i . The first term is the probability of generating w from the cache (i.e., sitting at an occupied table), and the second term is the probability of generating it anew (sitting at an unoccupied table). The actual table assignments z-i only become important later, in the bigram model.


There are several important points to note about this model. First, the probability of generating a particular word from the cache increases as more instances of that word are observed. This richget-richer process creates a power-law distribution on word frequencies (Goldwater et al., 2006), the same sort of distribution found empirically in natural language. Second, the parameter 0 can be used to control how sparse the solutions found by the model are. This parameter determines the total probability of generating any novel word, a probability that decreases as more data is observed, but never disappears. Finally, the parameter P0 can be used to encode expectations about the nature of the lexicon, since it defines a probability distribution across different novel words. The fact that this distribution is defined separately from the distribution on word frequencies gives the model additional flexibility, since either distribution can be modified independently of the other. Since the goal of this paper is to investigate the role of context in word segmentation, we chose the simplest possible model for P0 , i.e. a unigram phoneme distribution: P0 (w) = p# (1 - p# )n-1 in P (mi ) (4)

h1 : W

U

h2 : W

U U w2 W w3

w1 = w2 .w3

Figure 2: The two hypotheses considered by the unigram sampler. Dashed lines indicate possible additional structure. All rules except those in bold are part of h- . sampled from their conditional posterior distribution given the current values of all other variables in the model. The sampler defines a Markov chain whose stationary distribution is P (h|d), so after convergence samples are from this distribution. Our Gibbs sampler considers a single possible boundary point at a time, so each sample is from a set of two hypotheses, h1 and h2 . These hypotheses contain all the same boundaries except at the one position under consideration, where h2 has a boundary and h1 does not. The structures are shown in Figure 2. In order to sample a hypothesis, we need only calculate the relative probabilities of h1 and h2 . Since h1 and h2 are the same except for a few rules, this is straightforward. Let h- be all of the structure shared by the two hypotheses, including n- words, and let d be the observed data. Then P (h1 | h-, d) = P (w1 | h-, d) = nw1 + 0 P0 (w1 ) n- + 0
(h- )

=1

where word w consists of the phonemes m1 . . . mn , and p# is the probability of the word boundary #. For simplicity we used a uniform distribution over phonemes, and experimented with different fixed values of p# .1 A final detail of our model is the distribution on utterance lengths, which is geometric. That is, we assume a grammar similar to the one shown in Figure 1, with the addition of a symmetric Beta(  ) 2 prior over the probability of the U productions,2 and the substitution of the DP for the standard multinomial distribution over the W productions. 3.2 Gibbs Sampling

(5)

where the second line follows from Equation 3 and the properties of the CRP (in particular, that it is exchangeable, with the probability of a seating configuration not depending on the order in which customers arrive (Aldous, 1985)). Also, P (h2 | h-, d) = P (r, w2 , w3 | h-, d) = P (r | h-, d)P (w2 | h-, d)P (w3 | w2 , h-, d) =
(h ) nr +  nw2 + 0 P0 (w2 ) 2 · n- + 1 +  n- + 0
-

Having defined our generative model, we are left with the problem of inference: we must determine the posterior distribution of hypotheses given our input corpus. To do so, we use Gibbs sampling, a standard Markov chain Monte Carlo method (Gilks et al., 1996). Gibbs sampling is an iterative procedure in which variables are repeatedly
1 Note, however, that our model could be extended to learn both p# and the distribution over phonemes. 2 The Beta distribution is a Dirichlet distribution over two outcomes.

nw + I (w2 = w3 ) + 0 P0 (w3 ) (6) ·3 n- + 1 + 0 where nr is the number of branching rules r = U  W U in h- , and I (.) is an indicator function taking on the value 1 when its argument is
676

(h- )


true, and 0 otherwise. The nr term is derived by integrating over all possible values of p$ , and noting that the total number of U productions in h- is n- + 1. Using these equations we can simply proceed through the data, sampling each potential boundary point in turn. Once the Gibbs sampler converges, these samples will be drawn from the posterior distribution P (h|d). 3.3 Experiments

(a) Varying P(#)
60 55 50 LF F 0.1 0.3 0.5 0.7
0

0.9

(b) Varying 
60 55 50 1 2 LF F 5 10 20 50

In our experiments, we used the same corpus that NGS and MBDP were tested on. The corpus, supplied to us by Brent, consists of 9790 transcribed utterances (33399 words) of childdirected speech from the Bernstein-Ratner corpus (Bernstein-Ratner, 1987) in the CHILDES database (MacWhinney and Snow, 1985). The utterances have been converted to a phonemic representation using a phonemic dictionary, so that each occurrence of a word has the same phonemic transcription. Utterance boundaries are given in the input to the system; other word boundaries are not. Because our Gibbs sampler is slow to converge, we used annealing to speed inference. We began with a temperature of  = 10 and decreased  in 10 increments to a final value of 1. A temperature of  corresponds to raising the probabilities of h1 1 and h2 to the power of  prior to sampling. We ran our Gibbs sampler for 20,000 iterations through the corpus (with  = 1 for the final 2000) and evaluated our results on a single sample at that point. We calculated precision (P), recall (R), and F-score (F) on the word tokens in the corpus, where both boundaries of a word must be correct to count the word as correct. The induced lexicon was also scored for accuracy using these metrics (LP, LR, LF). Recall that our DP model has three parameters:  , p# , and 0 . Given the large number of known utterance boundaries, we expect the value of  to have little effect on our results, so we simply fixed  = 2 for all experiments. Figure 3 shows the effects of varying of p# and 0 .3 Lower values of p# cause longer words, which tends to improve recall (and thus F-score) in the lexicon, but decrease token accuracy. Higher values of 0 allow more novel words, which also improves lexicon recall,
It is worth noting that all these parameters could be inferred. We leave this for future work.
3

100 200

500

Figure 3: Word (F) and lexicon (LF) F-score (a) as a function of p# , with 0 = 20 and (b) as a function of 0 , with p# = .5. but begins to degrade precision after a point. Due to the negative correlation between token accuracy and lexicon accuracy, there is no single best value for either p# or 0 ; further discussion refers to the solution for p# = .5, 0 = 20 (though others are qualitatively similar). In Table 1(a), we compare the results of our system to those of MBDP and NGS.4 Although our system has higher lexicon accuracy than the others, its token accuracy is much worse. This result occurs because our system often mis-analyzes frequently occurring words. In particular, many of these words occur in common collocations such as what's that and do you, which the system interprets as a single words. It turns out that a full 31% of the proposed lexicon and nearly 30% of tokens consist of these kinds of errors. Upon reflection, it is not surprising that a unigram language model would segment words in this way. Collocations violate the unigram assumption in the model, since they exhibit strong word-toword dependencies. The only way the model can capture these dependencies is by assuming that these collocations are in fact words themselves. Why don't the MBDP and NGS unigram models exhibit these problems? We have already shown that NGS's results are due to its search procedure rather than its model. The same turns out to be true for MBDP. Table 2 shows the probabiliWe used the implementations of MBDP and NGS available at http://www.speech.sri.com/people/anand/ to obtain results for those systems.
4

677


(a) P R F LP LR LF NGS 67.7 70.2 68.9 52.9 51.3 52.0 MBDP 67.0 69.4 68.2 53.6 51.3 52.4 DP 61.9 47.6 53.8 57.0 57.5 57.2 (b) P R F LP LR LF NGS 76.6 85.8 81.0 60.0 52.4 55.9 MBDP 77.0 86.1 81.3 60.8 53.0 56.6 DP 94.2 97.1 95.6 86.5 62.2 72.4 Table 1: Accuracy of the various systems, with best scores in bold. The unigram version of NGS is shown. DP results are with p# = .5 and 0 = 20. (a) Results on the true corpus. (b) Results on the permuted corpus. Seg: True None MBDP NGS DP NGS 204.5 90.9 210.7 210.8 183.0 MBDP 208.2 321.7 217.0 218.0 189.8 DP 222.4 393.6 231.2 231.6 200.6 Table 2: Negative log probabilities (x 1000) under each model of the true solution, the solution with no utterance-internal boundaries, and the solutions found by each algorithm. Best solutions under each model are bold. ties under each model of various segmentations of the corpus. From these figures, we can see that the MBDP model assigns higher probability to the solution found by our Gibbs sampler than to the solution found by Brent's own incremental search algorithm. In other words, Brent's model does prefer the lower-accuracy collocation solution, but his search algorithm instead finds a higher-accuracy but lower-probability solution. We performed two experiments suggesting that our own inference procedure does not suffer from similar problems. First, we initialized our Gibbs sampler in three different ways: with no utteranceinternal boundaries, with a boundary after every character, and with random boundaries. Our results were virtually the same regardless of initialization. Second, we created an artificial corpus by randomly permuting the words in the true corpus, leaving the utterance lengths the same. The artificial corpus adheres to the unigram assumption of our model, so if our inference procedure works correctly, we should be able to correctly identify the words in the permuted corpus. This is exactly what we found, as shown in Table 1(b). While all three models perform better on the artificial cor678

pus, the improvements of the DP model are by far the most striking.

4 Bigram Model
4.1 The Hierarchical Dirichlet Process Model The results of our unigram experiments suggested that word segmentation could be improved by taking into account dependencies between words. To test this hypothesis, we extended our model to incorporate bigram dependencies using a hierarchical Dirichlet process (HDP) (Teh et al., 2005). Our approach is similar to previous n-gram models using hierarchical Pitman-Yor processes (Goldwater et al., 2006; Teh, 2006). The HDP is appropriate for situations in which there are multiple distributions over similar sets of outcomes, and the distributions are believed to be similar. In our case, we define a bigram model by assuming each word has a different distribution over the words that follow it, but all these distributions are linked. The definition of our bigram language model as an HDP is wi | wi-1 = w, Hw  Hw Hw | 1 , G G| 0 , P0  DP(1 , G)  DP(0 , P0 ) w w

That is, P (wi | wi-1 = w) is distributed according to Hw , a DP specific to word w. Hw is linked to the DPs for all other words by the fact that they share a common base distribution G, which is generated from another DP.5 As in the unigram model, we never deal with Hw or G directly. By integrating over them, we get a distribution over bigram frequencies that can be understood in terms of the CRP. Now, each word type w is associated with its own restaurant, which represents the distribution over words that follow w. Different restaurants are not completely independent, however: the labels on the tables in the restaurants are all chosen from a common base distribution, which is another CRP. To understand the HDP model in terms of a grammar, we consider $ as a special word type, so that wi ranges over   {$}. After observing w-i , the HDP grammar is as shown in Figure 4,
This HDP formulation is an oversimplification, since it does not account for utterance boundaries properly. The grammar formulation (see below) does.
5


P2 (wi | w-i , z-i ) P2 ($| w-i , z-i ) 1

Uwi-1 Wwi Uwi Uwi-1 $ Wwi  wi

wi   , wi-1    {$} wi-1   wi  

(a) Varying 
80

0

60

Figure 4: The HDP grammar after observing w-i . with n(w ,w ) + 1 P1 (wi | h-i ) P2 (wi | h-i ) = i-1 i (7) nwi-1 + 1 t +    2 · twi +0 P0 (wi ) wi   t+ t +0 P1 (wi | h-i ) =   t$ + 2 wi = $ t+ where h-i = (w-i , z-i ); t$ , t , and twi are the total number of tables (across all words) labeled with $, non-$, and wi , respectively; t = t$ + t is the total number of tables; and n(wi-1 ,wi ) is the number of occurrences of the bigram (wi-1 , wi ). We have suppressed the superscript (w-i ) notation in all cases. The base distribution shared by all bigrams is given by P1 , which can be viewed as a unigram backoff where the unigram probabilities are learned from the bigram table labels. We can perform inference on this HDP bigram model using a Gibbs sampler similar to our unigram sampler. Details appear in the Appendix. 4.2 Experiments
40 100 80

F LF 200 500 1000
1

2000

(b) Varying 

60 F LF 40 5 10 20 50 100 200 500

Figure 5: Word (F) and lexicon (LF) F-score (a) as a function of 0 , with 1 = 10 and (b) as a function of 1 , with 0 = 1000. P R F LP LR LF NGS 68.1 68.6 68.3 54.5 57.0 55.7 HDP 79.4 74.0 76.6 67.9 58.9 63.1 Table 3: Bigram system accuracy, with best scores in bold. HDP results are with p# = .5, 0 = 1000, and 1 = 10. contrast, our HDP model performs far better than our DP model, leading to the highest published accuracy for this corpus on both tokens and lexical items. Overall, these results strongly support our hypothesis that modeling bigram dependencies is important for accurate word segmentation.

We used the same basic setup for our experiments with the HDP model as we used for the DP model. We experimented with different values of 0 and 1 , keeping p# = .5 throughout. Some results of these experiments are plotted in Figure 5. With appropriate parameter settings, both lexicon and token accuracy are higher than in the unigram model (dramatically so, for tokens), and there is no longer a negative correlation between the two. Only a few collocations remain in the lexicon, and most lexicon errors are on low-frequency words. The best values of 0 are much larger than in the unigram model, presumably because all unique word types must be generated via P0 , but in the bigram model there is an additional level of discounting (the unigram process) before reaching P0 . Smaller values of 0 lead to fewer word types with fewer characters on average. Table 3 compares the optimal results of the HDP model to the only previous model incorporating bigram dependencies, NGS. Due to search, the performance of the bigram NGS model is not much different from that of the unigram model. In
679

5 Conclusion
In this paper, we have introduced a new modelbased approach to word segmentation that draws on techniques from Bayesian statistics, and we have developed models incorporating unigram and bigram dependencies. The use of the Dirichlet process as the basis of our approach yields sparse solutions and allows us the flexibility to modify individual components of the models. We have presented a method of inference using Gibbs sampling, which is guaranteed to converge to the posterior distribution over possible segmentations of a corpus. Our approach to word segmentation allows us to investigate questions that could not be addressed satisfactorily in earlier work. We have shown that the search algorithms used with previous models of word segmentation do not achieve their ob-


P (h1 | h , d) = P (h2 | h-, d) =

-

n(wl ,w1 ) + 1 P1 (w1 | h-, d) n(w1 ,wr ) + I (wl = w1 = wr ) + 1 P1 (wr | h-, d) · nwl + 1 nw1 + 1 + 1 - -, d) n n(wl ,w2 ) + 1 P1 (w2 | h (w2 ,w3 ) + I (wl = w2 = w3 ) + 1 P1 (w3 | h , d) · · nwl + 1 nw2 + 1 + 1 n(w3 ,wr ) + I (wl = w3 , w2 = wr ) + I (w2 = w3 = wr ) + 1 P1 (wr | h-, d) nw3 + 1 + I (w2 = w4 ) + 1

Figure 6: Gibbs sampling equations for the bigram model. All counts are with respect to h- . jectives, which has led to misleading results. In particular, previous work suggested that the use of word-to-word dependencies has little effect on word segmentation. Our experiments indicate instead that bigram dependencies can be crucial for avoiding under-segmentation of frequent collocations. Incorporating these dependencies into our model greatly improved segmentation accuracy, and led to better performance than previous approaches on all measures.
J. Saffran, E. Newport, and R. Aslin. 1996. Word segmentation: The role of distributional cues. Journal of Memory and Language, 35:606­621. M. Sun, D. Shen, and B. Tsou. 1998. Chinese word segmentation without using lexicon and hand-crafted training data. In Proceedings of COLING-ACL. Y. Teh, M. Jordan, M. Beal, and D. Blei. 2005. Hierarchical Dirichlet processes. In Advances in Neural Information Processing Systems 17. MIT Press, Cambridge, MA. Y. Teh. 2006. A Bayesian interpretation of interpolated kneser-ney. Technical Report TRA2/06, National University of Singapore, School of Computing. A. Venkataraman. 2001. A statistical model for word discovery in transcribed speech. Computational Linguistics, 27(3):351­372.

References
D. Aldous. 1985. Exchangeability and related topics. In ´ Ecole d'ete de probabilites de Saint-Flour, XIII--1983, ´´ ´ pages 1­198. Springer, Berlin. C. Antoniak. 1974. Mixtures of Dirichlet processes with applications to Bayesian nonparametric problems. The Annals of Statistics, 2:1152­1174. N. Bernstein-Ratner. 1987. The phonology of parent-child speech. In K. Nelson and A. van Kleeck, editors, Children's Language, volume 6. Erlbaum, Hillsdale, NJ. M. Brent. 1999. An efficient, probabilistically sound algorithm for segmentation and word discovery. Machine Learning, 34:71­105. P. Cohen and N. Adams. 2001. An algorithm for segmenting categorical timeseries into meaningful episodes. In Proceedings of the Fourth Symposium on Intelligent Data Analysis. H. Feng, K. Chen, X. Deng, and W. Zheng. 2004. Accessor variety criteria for chinese word extraction. Computational Lingustics, 30(1). W.R. Gilks, S. Richardson, and D. J. Spiegelhalter, editors. 1996. Markov Chain Monte Carlo in Practice. Chapman and Hall, Suffolk. S. Goldwater, T. Griffiths, and M. Johnson. 2006. Interpolating between types and tokens by estimating power-law generators. In Advances in Neural Information Processing Systems 18, Cambridge, MA. MIT Press. Z. Harris. 1954. Distributional structure. Word, 10:146­162. B. MacWhinney and C. Snow. 1985. The child language data exchange system. Journal of Child Language, 12:271­ 296.

Appendix
To sample from the posterior distribution over segmentations in the bigram model, we define h1 and h2 as we did in the unigram sampler so that for the corpus substring s, h1 has a single word (s = w1 ) where h2 has two (s = w2 .w3 ). Let wl and wr be the words (or $) preceding and following s. Then the posterior probabilities of h1 and h2 are given in Figure 6. P1 (.) can be calculated exactly using the equation in Section 4.1, but this requires explicitly tracking and sampling the assignment of words to tables. For easier and more efficient implementation, we use an approximation, replacing each table count twi by its expected value E [twi ]. In a DP(, P ), the expected number of CRP tables for an item occurring n times is  log n+ (Anto niak, 1974), so E [twi ] = 1 j log n(wj ,wi ) + 1 1

This approximation requires only the bigram counts, which we must track anyway.

680