📄 Minimum Cut Model for Spoken Lecture Segmentation

Summary

The paper addresses unsupervised topic segmentation of spoken lectures. This is hard because lecture topics shift gradually, speech is disfluent and digressive, and ASR output contains many errors. Malioutov and Barzilay treat a transcript as a weighted undirected graph: nodes are sentences (word blocks), and edges carry exponentiated cosine similarities. Segmentation becomes a k-way partition that minimizes the normalized-cut criterion of Shi and Malik. This objective rewards cohesion inside segments and penalizes similarity between them, so it captures long-range lexical relations, not just neighbouring comparisons. Segments must be contiguous, and this constraint allows an exact dynamic-programming solution instead of an approximation of an NP-complete problem. The method was evaluated on Physics and AI lecture corpora and on Choi's synthetic dataset. On real lectures it beats Choi's similarity-based segmenter and is competitive with the UI language-model segmenter. It degrades less on ASR transcripts than UI. The main lesson is that global analysis helps when boundaries are subtle.

Key points

• Corpora:
  • 33 Physics lectures, about 5.9 segments per lecture and 232K tokens, with ASR transcripts at 19.4% WER.
  • 22 AI lectures, about 12.3 segments per lecture and 182K tokens.
  • Choi's (2000) synthetic set, built from Brown corpus excerpts.
• Decoding: Exact DP over linear segmentations runs in O(KN²), where K is the number of segments and N the number of sentences.
• Results on manual Physics transcripts (Pk): MinCut 0.298, UI 0.310, Choi 0.372.
  • On AI lectures, UI is slightly better by Pk (0.374 vs 0.383), while MinCut is slightly better by WindowDiff (0.417 vs 0.420).
  • On the synthetic set, MinCut loses to Choi (0.212 vs 0.110).
• Effect of edge distance on Physics: Keeping edges up to 10 sentences apart gives Pk 0.394. Extending the cutoff to about 100 sentences lowers Pk by roughly 25%. Pushing the cutoff further eventually hurts.
• ASR robustness: Moving to ASR transcripts raised Pk by only 7.8% relative (0.298 → 0.322). The same change raised UI's Pk by 13.5%.

Interesting ideas

• I1. Exact search through a structural constraint. Requiring segments to be contiguous turns an intractable graph-partitioning objective into one solvable exactly by dynamic programming. The same trick could apply to any sequence-chunking task, such as speech, logs, or time series.
• I2. Per-document tf-idf. Each transcript is split into uniform chunks that play the role of "documents" for tf-idf. This makes term weights specific to one lecture, so domain words that are rare in general language get appropriate weight. It is useful for long, single-topic texts like Ukrainian lectures or parliamentary records.
• I3. Distance-weighted neighbourhood smoothing. Word counts from adjacent sentences are added to each sentence vector, with weights that decay exponentially with distance. This reduces sparsity in short, noisy utterances.
• I4. Distance cutoff as a diagnostic. Varying the maximum edge distance directly tests whether long-range context helps, and shows where it starts adding spurious links. This kind of ablation transfers easily to other models that claim to use global context.
• I5. Testing beyond synthetic benchmarks. The method performs well on real lectures but poorly on concatenated synthetic text. This is a reminder to evaluate on natural data with gradual topic shifts.