Graph-Cut Consistency for Document-Level Word Segmentation

Chinese and Japanese text has no spaces, so a segmenter must decide where every word ends. A sentence of $N$ characters has $2^{N-1}$ possible segmentations, and the number of joint analyses grows further once each word also receives a part-of-speech tag. Today's segmenters handle this by working one sentence at a time. That choice discards a strong cue. Inside a single news article, a new name or technical term usually appears several times, and the segmenter should split it the same way each time. A sentence-level model that is confident about the term in one sentence and confused in the next cannot carry its confidence across. Adding "segment the same string the same way" as a soft rule across a whole document links every sentence to every other one. Exact dynamic programming then becomes impossible, and the problem joins the familiar class where added structure makes search explode.

This note proposes a decoder that keeps the sentence models exact and adds a document-wide consistency term, while still producing a certificate that the returned answer is optimal. The cross-sentence term is an attractive two-label Markov random field: a grid-like graph of yes/no variables in which neighbours are penalised for disagreeing. Here the variables are the "is there a word boundary here?" decisions. Energies of this kind are solved exactly by a single minimum s-t cut, the max-flow computation used throughout computer vision labeling (Zabih et al., Karim et al.). We join the per-sentence Viterbi decoders to this graph-cut subproblem through Lagrangian relaxation, also called dual decomposition. In this method, separately solvable pieces of a problem are pushed toward agreement by adjustable penalties. When the pieces agree, the joint answer is provably optimal.

Core Claim

Document-level boundary consistency is the part of the joint segmentation problem that breaks dynamic programming. With non-negative consistency weights it is also exactly the part that graph cuts solve in polynomial time. Splitting the problem along this line has two consequences. First, recurring out-of-vocabulary words get segmented correctly more often than with any sentence-level decoder. Second, the decoder returns certified-optimal document analyses on most documents, with fewer dual iterations than splitting the same consistency terms into independent pairwise pieces.

The objective is a document energy over joint tag sequences $y_s$ for each sentence $s$, where $b_g(y) \in \{0,1\}$ indicates a word boundary at character gap $g$:

$$E(y) = -\sum_s \mathrm{score}_s(y_s) + \sum_{(g,g') \in \mathcal{C}} w_{gg'}\,[\,b_g(y) \neq b_{g'}(y)\,].$$

Here $\mathrm{score}_s$ is a trained sentence model's score for the full joint segmentation-and-tag sequence. The set $\mathcal{C}$ links aligned gaps (the start, end and interior gaps) of repeated occurrences of the same candidate string anywhere in the document. Each weight $w_{gg'} \ge 0$ is a learned function of features such as string length, frequency and dictionary status. Because the weights are non-negative, the second term is submodular and can be minimised exactly by min-cut. The first term is not submodular, since tag transition potentials are arbitrary, but it decomposes into chains that Viterbi solves exactly.

We introduce copy variables $z_g$ for the boundaries and multipliers $u_g$ on the constraint $b_g(y) = z_g$. Each dual step then solves two pieces. One is every sentence's Viterbi decode with boundary scores shifted by $u$. The other is one min-cut over $z$ with unaries $-u_g$. Agreement certifies the global optimum.

Relation to Prior Work

The method comes most directly from Rush and Collins. They decompose syntactic translation decoding into a hypergraph parser and a sequence model joined by multipliers. They certify 97.7% of NIST sentences and show that cube pruning with beam 50 makes search errors on 50.5% of them. We reuse their subgradient updates and incremental tightening, but our second subproblem is a graph cut rather than a shortest path. The closest existing work is Two Knives Cut Better Than One, which uses dual decomposition to make a character CRF and a word-based segmenter agree within each sentence, reaching agreement on 99.1% of sentences within 100 iterations. That decomposition runs across models and inside a sentence. Ours runs across sentences inside a document, and its new piece is an exact graph-cut subproblem that no sentence decoder can represent.

Malioutov and Barzilay motivate the global view. Their normalized-cut topic segmenter beats local methods on lecture transcripts, scoring $P_k$ 0.298 against 0.372 and 0.310, and degrades less under speech-recognition noise. Their cut, however, depends on 1D contiguity to run dynamic programming. Our cut graph is loopy because occurrences of the same string overlap and chain across sentences.

The sentence-level joint decoders of Zhang and Clark and Sun supply the inner decoders and the evidence that joint segmentation-and-tagging beats pipelines. Higashiyama et al. supply the strongest neural sentence model and the observation that motivates us: lexicon-based models degrade on out-of-vocabulary words, which are exactly the strings that recur within a document.

Two works constrain the design. Lang, Sontag and Vijayaraghavan and their follow-up show that α-expansion, the standard multi-label graph-cut method, is exact only on stable ferromagnetic Potts instances. Its certificates are expensive and specific to that model. We therefore restrict the cut subproblem to binary boundary variables, where min-cut is exact without any stability assumption, and leave multi-label tag consistency to a later, explicitly approximate extension.

Accelerated dual decomposition speeds convergence by smoothing the subproblems into marginal computations. That smoothing would turn our exact min-cut into marginal inference on a loopy model, which is no longer exact, so we keep subgradient updates and treat smoothing as a comparison point. Burkett, Hall and Klein use "graph cuts" in a different sense, as expanding search frontiers for A*, and are not part of the mechanism.

Research Program

We first train a sentence-level joint segmentation-and-POS model on BIES×POS character labels, using the encoder of the WCON-style model of Higashiyama et al.. This model is frozen and provides $\mathrm{score}_s$.

We then build the consistency graph. Candidate strings are spans of length two or more that occur at least twice in a document and receive non-trivial probability under the sentence model. Their aligned gaps are linked into $\mathcal{C}$. The weights $w$ come from a softplus over a handful of features, fitted on development data by structured perceptron with the full decoder in the loop. The softplus keeps every weight non-negative, which keeps the cut subproblem submodular.

The decoder alternates Viterbi and min-cut under subgradient updates. When agreement stalls, it applies Rush–Collins-style tightening by adding exact pairwise agreement terms to the gaps that keep disagreeing. Documents that still fail are decoded by fixing the cut solution and re-running Viterbi, and are reported as uncertified.

For analysis, we solve the same energy exactly with an integer program offline on a sample of documents. This tells us whether any errors in the final output come from the search procedure or from the model itself.

Baselines

The naive reference point is the frozen sentence-level model decoded independently per sentence with exact Viterbi. Every gain must be measured against it, using identical unaries.

The strongest published sentence-level system in the file is the word-attention BiLSTM-CRF of Higashiyama et al.. It reports segmentation F1 of 96.38 on CTB6, 97.79 on MSR and 98.93 on BCCWJ. Because our unaries come from a reimplementation of this model, we first verify that our naive baseline reproduces these figures within noise. Beating it means a statistically significant F1 gain on at least two of the three corpora, together with a larger gain on recurring out-of-vocabulary recall. For joint segmentation and tagging on CTB5, the reference figures are 93.67 joint F-score for Zhang and Clark and 94.02 for Sun. The dual-decomposition segmenter of Wang et al. reports results on SIGHAN, but no per-dataset F1 figure was found on Lacuna for it, so we rerun it ourselves on the same splits.

A document-context neural model is the most serious learned competitor. It is the same encoder given the neighbouring sentences, or a sliding window of the document, as extra input, trained with the same data and tuning budget. It tests whether consistency can simply be learned rather than enforced at decoding time.

Post-hoc majority voting is the most serious cheap competitor. It segments every sentence, then forces each repeated string to its most frequent or most confident segmentation.

Iterated conditional modes is a greedy local-update approximate inference method. Run on exactly our energy, it shows the cost of not solving the coupled problem properly.

Two ablations isolate the key ingredient. In the first, we replace the single min-cut subproblem with an edge-wise decomposition in which each consistency pair is its own subproblem with its own multipliers, and run it under the same iteration budget. This is the natural generalisation of the Wang et al. style of decomposition. Our claim is not a tighter relaxation, because for attractive binary terms both relaxations coincide. The claim is that far fewer multipliers means faster agreement. In the second ablation, we keep the graph but link random non-matching occurrences. This control shows whether gains come from linguistic consistency or from smoothing alone.

All systems share data, unaries and development-set tuning budgets. Wall-clock time is reported on the same hardware.

Why not just…?

Why not just give the neural model the whole document as context? This is the real threat. A long-context encoder can in principle learn that recurring strings segment alike. The literature in the file gives no evidence either way, since every cited segmenter is sentence-level. We settle the question directly by comparing the document-context model to our decoder, and also by stacking our consistency layer on top of the document-context model. If the stacked gain falls to zero, we will report that explicit consistency is redundant with long-context training. The remaining contribution would then be certified decoding for weaker or lexicon-constrained models, which is a smaller claim.

Why not just take a majority vote over repeated strings? Voting ignores confidence. It also cannot resolve overlapping candidates, such as one string being a substring of another with a conflicting boundary, and it cannot handle legitimate context-dependent splits. The min-cut weighs every occurrence's evidence against every link at once. The decisive measurement is the gap between the two methods on documents whose consistency graph contains overlapping candidate strings. If voting matches the graph cut there, the graph cut is unnecessary.

Why not just widen the beam or use a general integer-program solver on the joint energy? Zhang and Clark found accuracy plateaus at beam 16. Rush and Collins report that general integer-program solvers were far slower than Lagrangian relaxation and failed to terminate on long inputs. Document energies are larger still. We run the integer program only offline, as the source of exact optima, and report its runtime alongside ours.

Proposed Experiments

The corpora are CTB5 for joint segmentation and tagging, CTB6 and BCCWJ, which have native document structure, and MSR. For SIGHAN-style test sets without document markup, contiguous blocks of the test file are treated as pseudo-documents, and this is reported separately. The metrics are segmentation F1, joint F-score, overall out-of-vocabulary recall, and recall on out-of-vocabulary types that occur at least twice in their document. We also report the certification rate, mean dual iterations, and decoding time per document.

The first decisive check is the target subset. The method must raise recurring out-of-vocabulary recall over both the naive decoder and majority voting while leaving accuracy on non-recurring words unchanged. A drop on non-recurring words would mean that consistency is overriding legitimate context.

The second check is search quality. On the integer-program-verified sample, our decoder should match the exact optimum on all certified documents and come within a measured margin on the rest. Iterated conditional modes should show a measurable search-error rate on the same documents.

The third check is efficiency. The single-cut decomposition should certify at least as many documents as the edge-wise decomposition in fewer iterations. If it does not, the graph cut contributes nothing beyond the energy itself, and we will say so.

The fourth check is the random-link control, which should erase the gains. Finally, the document-context comparison described above determines whether the method's value lies in modelling or only in decoding.