📄 Contextual Dependencies in Unsupervised Word Segmentation

Summary

The paper asks whether modeling relations between neighboring words helps unsupervised word segmentation, the task of finding word boundaries in unsegmented text or phonemically transcribed speech. Earlier explicit probabilistic systems, Brent's MBDP and Venkataraman's NGS, showed almost no difference between unigram, bigram and trigram variants, which suggested that context does not matter. The authors argue that this finding was an artifact of approximate search. For each older model they exhibit a segmentation that the model scores higher but that is less accurate. They also show that the true maximum-likelihood NGS solution leaves utterances unsegmented. As an alternative, they build Bayesian nonparametric models: a Dirichlet process (DP) unigram model and a hierarchical Dirichlet process (HDP) bigram model. Both use Gibbs sampling, which converges to the posterior over segmentations. The bigram HDP model clearly beats the unigram DP model and the bigram NGS. It reached the best published token and lexicon accuracy on the corpus used. The work shows that bigram dependencies are important, mainly for avoiding under-segmentation of frequent collocations. It also shows why model and search should be evaluated separately.

Key points

• The baselines are Brent's MBDP, which uses a unigram distribution with a prior favoring smaller lexicons, and Venkataraman's NGS (unigram, bigram and trigram). Both rely on online approximate search that fixes each utterance's segmentation before moving to the next.
• Because NGS uses a uniform prior, its optimum is the corpus with no utterance-internal boundaries, where each utterance is treated as one "word".
• The unigram model is based on a DP(α0, P0). It is understood through the Chinese restaurant process, which acts like a cache: a word is either reused in proportion to its count or newly generated from P0. P0 is a simple unigram phoneme model with stop probability p#.
• The bigram HDP model on the bigram setup reached P/R/F of 79.4/74.0/76.6 and LP/LR/LF of 67.9/58.9/63.1. The bigram NGS scored 68.1/68.6/68.3 and 54.5/57.0/55.7. The HDP settings were p# = .5, α0 = 1000 and α1 = 10.
• In the bigram model, the negative relationship between lexicon and token accuracy seen in the unigram model disappears. Only a small number of collocations are still listed as lexical entries, and the errors that persist mostly concern infrequent words.

Interesting ideas

• I1. Separate the model from the search. Show that a less accurate segmentation receives a higher score than the one the search returned. This test reveals whether reported results come from the model's assumptions or from quirks of the search, and it applies to any system that relies on heuristic decoding.
• I2. Prefer sparse solutions with a prior. A uniform prior rewards simply memorizing the training data. A prior that favors fewer parameters or lexical items prevents this degenerate outcome, which is a useful safeguard for any unsupervised lexicon or vocabulary induction.
• I3. Keep the word generator and the frequency model separate. The base distribution P0 (what new words look like) is defined apart from the CRP adaptor (how often words recur). Each part can therefore be changed independently, for example by adding phonotactics or morphology for a specific language such as Ukrainian.
• I4. Back off hierarchically by sharing table labels. In the HDP bigram model, all context-specific restaurants draw from a shared unigram process. This acts as smoothing that is learned from the data rather than tuned by hand, and the same pattern works for other sparse conditional distributions.
• I5. Score both tokens and lexicon. Reporting precision, recall and F-score for word tokens and for lexicon types exposes trade-offs that a single metric hides, such as the unigram model merging collocations. This makes it a sound evaluation practice for segmentation and tokenization tools.