Some languages are written without spaces, or are transcribed only as continuous phoneme strings. One way to find word boundaries in such text is to use a translation into a space-delimited language as supervision. Characters that keep co-occurring with the same English word probably form a word. Models that do this treat the segmentation as a hidden choice and learn it together with a translation table, summing over all possible splits of each sentence. The objective they optimize is non-convex, meaning it has many local optima, so different starting points can end in different places. The best-known result in this area is that such models give better translations but agree less with human-annotated word boundaries than supervised segmenters. Two explanations fit that result. The objective may genuinely prefer non-linguistic units. Alternatively, the training procedure may simply settle in whichever local optimum is nearest its starting point.
This note proposes to tell those two explanations apart. It also proposes a cheap initializer built from the co-occurrence matrix of source substrings and target words, borrowing the "spectral warm start" idea from non-convex matrix estimation. If the gap between translation quality and linguistic boundary accuracy is partly caused by where training starts, a better start could deliver both. If the gap is not caused by the start, that settles an open tension in the literature and tells practitioners that tuning the initialization cannot buy linguistic plausibility.
Core Claim
Unsupervised Tokenization for Machine Translation folds source segmentation into IBM Model 1 alignment and uses dynamic programming to sum over all character segmentations. To stop the model from memorizing whole sentences as single tokens, it adds length penalties and Variational Bayes with a sparse Dirichlet prior. It reports 22.31 BLEU on NIST 2002 Chinese–English, which beats the supervised LDC segmenter (20.03) and nearly matches the Stanford segmenter (22.45), yet its F-score against the Chinese Treebank is lower than the supervised segmenters'. Dynamic Programming Encoding for Subword Segmentation in Neural Machine Translation points the other way. Its neural latent-segmentation model recovers morpheme-like splits (cart+s rather than BPE's car+ts). These two results are in tension, and neither paper tests whether the starting point is responsible.
Our claim has two parts. The first is a measurable hypothesis: in a Chung–Gildea-style joint model, both the final segmentation and its treebank F-score depend strongly on how the translation table is initialized. Initializations that lead to equal training objectives can still yield segmentations that differ substantially in linguistic accuracy. The second part is constructive. Take a low-rank approximation of the substring–target-word association matrix and use it to set the initial translation table. We predict this start will reach segmentations at least as good in translation quality and closer to the gold standard than the standard uniform start. We also predict it will be competitive with seeding from a monolingual tokenizer, which is the obvious cheap alternative.
We do not claim provable basin guarantees. The low-rank estimation results, such as A Unified Computational and Statistical Framework for Nonconvex Low-rank Matrix Estimation and Finding Low-rank Solutions to Matrix Problems, Efficiently and Provably, rely on restricted strong convexity in a factorized parameterization. EM over a segmentation lattice does not satisfy those conditions. Those papers supply the design pattern: estimate a cheap spectral anchor from the observations, then run local refinement from it. They are not the source of our guarantees.
Research Program
The base model. We reimplement the joint model of Chung and Gildea. Training runs Variational Bayes over a translation table $t(w \mid s)$, which gives the probability of target word $w$ given source substring $s$. Its expectation step sums over all segmentations of each sentence up to a maximum substring length, and it keeps their length factors. Holding the model and its hyperparameters fixed, we vary only the initial table.
The spectral initializer. We follow the substring-counting idea of Sub-Sentential Alignment Using Substring Co-Occurrence Counts. Over all sentence pairs, we count how often each source substring $s$ (up to length $K$, frequency-filtered) appears in the same pair as each target word $w$. We then form the positive pointwise mutual information matrix $M$, whose entry $M_{s,w}$ is how much more often $s$ and $w$ co-occur than chance would predict, clipped at zero. We compute its rank-$r$ truncated SVD, $M_r = U_r \Sigma_r V_r^\top$, and set
$$t_0(w \mid s) \propto \max\big(0, [M_r]_{s,w}\big) + \epsilon,$$
where $\epsilon$ is a small floor that keeps every entry nonzero. The low-rank step plays the same role as spectral initialization in phase retrieval and deconvolution (Regularized gradient descent: a non-convex recipe for fast joint blind deconvolution and demixing). It suppresses noisy, sparse counts that would otherwise attract EM toward spurious long substrings. The cost is one sparse SVD, which is small compared with a single pass of lattice summation.
The dependence-on-start study. For each initializer, we run many seeds, perturbing the initial table with multiplicative noise. We record four quantities: the final variational objective, boundary F-score against the Chinese Treebank, BLEU after the downstream translation pipeline, and agreement of boundaries across seeds. The diagnostic run is to seed training from the gold treebank segmentation itself, by initializing $t_0$ from alignments computed on gold-segmented text. If that run stays near gold boundaries and ends at an objective no worse than the uniform-start run, then the objective does not prefer non-linguistic units. In that case the gold-standard gap is a local-optimum effect. If instead the gold-seeded run drifts toward the unsupervised solution, the gap belongs to the objective.
A diagnostic that predicts where boundaries are stable. Fast Stochastic Algorithms for SVD and PCA: Convergence Properties and Convexity shows that the region where local refinement behaves well shrinks with the eigengap, the separation between the leading singular value and the next one. By analogy, we compute a per-target-word margin: the gap between the best and second-best competing substrings in $M_r$. We then test whether this margin predicts which words get stable boundaries across seeds. This tests, in a concrete measured form, the speculation that failures on rare words track weak spectral separation. The motivating evidence is the large disagreement between BPE and latent segmentation on low-frequency words reported by He et al., up to 64%.
Baselines
The naive reference point is the base model with the uniform or near-uniform initial table that is standard for IBM Model 1. It is trained with exactly the same priors, length factors, iteration count, and data as every other condition. The question being asked is whether initialization alone changes the outcome, so this is the comparison that isolates the key ingredient.
The strongest existing method on our benchmark is the Chung–Gildea system itself. The cited paper reports 22.31 BLEU on NIST 2002 Chinese–English and 7.46 BLEU on Korean–English, compared with 22.45 for the Stanford segmenter and 20.03 for the LDC segmenter. No CTB F-score number is reported on Lacuna for this system; the paper gives only the direction of the gap. Our reimplementation will not match their original pipeline exactly, so we report our reproduced numbers next to theirs and compute every comparison within our own pipeline. Beating this baseline means one of two things. Either we raise CTB F-score by a margin larger than the spread across seeds of the uniform start, while BLEU stays within that spread. Or we raise both. A BLEU gain alone would not count.
The most dangerous competitor is tokenizer seeding. Here $t_0$ is initialized from alignments computed on text segmented by a monolingual Unigram language model, or by an unsupervised segmental language model (Unsupervised Neural Word Segmentation for Chinese via Segmental Language Modeling). That segmental model reports 79.2 F1 on PKU unsupervised and 87.5 F1 with 1,024 annotated sentences. We also run a multi-start baseline. It uses the same total compute as the spectral run plus its SVD, spent on random restarts, and selects the restart with the best objective. Finally, we run seeding from a supervised segmenter and from gold segmentation. These two are upper references, not competitors, because no such segmenter exists in the low-resource settings that motivate the work. A rank ablation, from $r$ equal to raw PMI with no truncation down to small $r$, checks that the low-rank step matters and not merely the use of association statistics.
Why not just…?
Why not just initialize from BPE or a Unigram tokenizer? This is a real threat. It is cheap, standard, and already encodes frequent units. The objection to it is that monolingual compression is blind to the target language. Deguchi et al. (Bilingual Subword Segmentation for Neural Machine Translation) show that it produces source–target length mismatches, which their bilingual filtering repairs for gains of +0.81 BLEU on ASPEC Japanese–English. We run tokenizer seeding head to head. If it matches spectral seeding on both F-score and BLEU, we will say so. The contribution then narrows to the dependence-on-start finding and the margin diagnostic, which still answer the open question.
Why not just run random restarts and keep the best objective? Restarts are included at matched compute. The deeper problem is that the best objective might not pick the best segmentation, since the Chung–Gildea result already shows likelihood-driven training departing from gold. Our gold-seeded run tests directly whether objective value and linguistic accuracy come apart at local optima. If they do come apart, picking the best restart cannot fix the problem, whatever the compute budget.
Why not just retune the Dirichlet prior and length penalties? Hyperparameters and initialization interact, so a tuned prior might erase the effect of the start. We give the uniform-start baseline a hyperparameter search of the same size as the search used for spectral rank $r$. We report whether the dependence on the start persists under the best prior for each initializer.
Why not just use a supervised segmenter? Where one exists, it is a strong choice for boundary accuracy. Chung and Gildea's numbers show it is not better for translation. The endangered-language settings in Inducing bilingual lexicons from small quantities of sentence-aligned phonemic transcriptions and Vorm: Translations and a constrained hypothesis space support unsupervised morphological segmentation across languages have no annotated data at all. We use supervised seeding only as a ceiling.
Proposed Experiments and Decisive Checks
The primary testbed is FBIS Chinese–English. We measure translation on NIST 2002 with BLEU and boundaries against the Penn Chinese Treebank with precision, recall, and F-score, following Chung and Gildea's protocol. Korean–English is a secondary replication if a comparable corpus can be assembled; the original corpus is custom. To test the low-resource case, we subsample FBIS to a few thousand sentence pairs. In that regime co-occurrence counts are sparse and the margin diagnostic should matter most. Where DORECO-MORPH languages come with free translations, we run the same study on phonemic transcriptions and report the boundary precision and recall metric used by the morphology benchmarks.
There are three decisive checks. The first is the gold-seeded run. If it ends at an objective no worse than the uniform start while keeping higher F-score, the "gold standard fallacy" is at least partly a local-optimum effect. The second is the comparison between spectral and tokenizer seeding. Spectral seeding must improve F-score beyond the spread across seeds without losing BLEU; otherwise the initializer is not worth having. The third tests whether the per-word margin predicts boundary stability across seeds, measured by rank correlation that holds after controlling for word frequency. If the margin adds nothing beyond frequency, the eigengap analogy fails and we will report that.
A neural extension starting the latent-segmentation model of He et al. from spectral substring embeddings is a natural follow-up. That model trains about 8× slower, so we leave it until the cheaper model shows a clear effect.
References
- Unsupervised Tokenization for Machine Translation
- Dynamic Programming Encoding for Subword Segmentation in Neural Machine Translation
- A Unified Computational and Statistical Framework for Nonconvex Low-rank Matrix Estimation
- Finding Low-rank Solutions to Matrix Problems, Efficiently and Provably
- Sub-Sentential Alignment Using Substring Co-Occurrence Counts
- Regularized gradient descent: a non-convex recipe for fast joint blind deconvolution and demixing
- Fast Stochastic Algorithms for SVD and PCA: Convergence Properties and Convexity
- Unsupervised Neural Word Segmentation for Chinese via Segmental Language Modeling
- Bilingual Subword Segmentation for Neural Machine Translation
- Inducing bilingual lexicons from small quantities of sentence-aligned phonemic transcriptions
- Vorm: Translations and a constrained hypothesis space support unsupervised morphological segmentation across languages