---
title: "Minimum Cut Model for Spoken Lecture Segmentation (2006)"
description: "The paper addresses unsupervised topic segmentation of spoken lectures. 19.4% WER. 19 references, cited by 62 papers here."
authors: ["Igor Malioutov", "Regina Barzilay"]
year: 2006
venue: "Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the Association for Computational Linguistics"
source: "https://aclanthology.org/P06-1004/"
doi: "10.3115/1220175.1220179"
licence: "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)"
licence_url: "https://creativecommons.org/licenses/by-nc-sa/3.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/en/papers/malioutov-2006-minimum-cut-model-spoken-lecture/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/malioutov-2006-minimum-cut-model-spoken-lecture/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2006](https://md.research.elamur.ai/free/en/papers/2006/) / Minimum Cut Model for Spoken Lecture Segmentation

# Minimum Cut Model for Spoken Lecture Segmentation

**Authors:** [Igor Malioutov](https://md.research.elamur.ai/free/en/authors/igor-malioutov/) and [Regina Barzilay](https://md.research.elamur.ai/free/en/authors/regina-barzilay/) · **Year:** 2006 · **Venue:** [Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the Association for Computational Linguistics](https://md.research.elamur.ai/free/en/venues/acl/) ([ACL 2006](https://md.research.elamur.ai/free/en/venues/acl/2006/)) · **Publisher:** [Association for Computational Linguistics](https://md.research.elamur.ai/free/en/publishers/association-for-computational-linguistics/) · **Licence:** [CC BY-NC-SA 3.0 (ACL Anthology, before 2016)](https://creativecommons.org/licenses/by-nc-sa/3.0/)

**Links:** [Publisher's page](https://aclanthology.org/P06-1004/) · [PDF](https://aclanthology.org/P06-1004.pdf) · [DOI 10.3115/1220175.1220179](https://doi.org/10.3115/1220175.1220179) · [OpenAlex](https://openalex.org/W2118612506)

**Citations:** 208 citations (OpenAlex, 2026-10-14) · [62](https://md.research.elamur.ai/free/en/papers/malioutov-2006-minimum-cut-model-spoken-lecture/cited-by/) in our library, of the 141,840 papers whose bibliographies we read

## 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
- **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.
- **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.
- **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.
- **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.
- **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.

*Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.*

## Institutions

- [Massachusetts Institute of Technology](https://md.research.elamur.ai/free/en/universities/massachusetts-institute-of-technology/) — University, Cambridge, United States · 159 works · 65,157 citations

📚 Shelves (6): [🖥️ Computer Science](https://md.research.elamur.ai/free/en/shelves/computer-science/) · 9,085 works · [🤖 Artificial Intelligence](https://md.research.elamur.ai/free/en/shelves/computer-science/artificial-intelligence/) · 8,888 works · [🎭 Arts and Humanities](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/) · 9,296 works · [🗣️ Language and Linguistics](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/language-and-linguistics/) · 9,206 works · [👁️ Computer Vision and Pattern Recognition](https://md.research.elamur.ai/free/en/shelves/computer-science/computer-vision-and-pattern-recognition/) · 1,282 works · [🔊 Signal Processing](https://md.research.elamur.ai/free/en/shelves/computer-science/signal-processing/) · 213 works

🧭 Topics (1): [🎙️ Speech & spoken language](https://md.research.elamur.ai/free/en/topics/speech/) · 233 works

## Cite

Cite as: Igor Malioutov and Regina Barzilay. 2006. Minimum Cut Model for Spoken Lecture Segmentation. Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the Association for Computational Linguistics.

The paper itself, not this page. BibTeX from the library's record of the work.

```bibtex
@inproceedings{malioutov2006minimum,
  title = {{Minimum Cut Model for Spoken Lecture Segmentation}},
  author = {Igor Malioutov and Regina Barzilay},
  booktitle = {Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the Association for Computational Linguistics},
  year = {2006},
  doi = {10.3115/1220175.1220179},
  url = {https://doi.org/10.3115/1220175.1220179}
}
```

- [← previous Statistical Syntax-Directed Translation with Extended Domain of Locality](https://md.research.elamur.ai/free/en/papers/huang-2006-statistical-syntax-directed-translation-extended/)
- [next → Experiments on the Automatic Induction of German Semantic Verb Classes](https://md.research.elamur.ai/free/en/papers/walde-2006-experiments-automatic-induction-german-semantic/)
- [↑ back to papers of 2006](https://md.research.elamur.ai/free/en/papers/2006/)

## References

19 references, 4 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

1. D. Beeferman, A. Berger, J. D. Lafferty. 1999. Statistical models for text segmentation. Machine Learning, 34(1-3):177–210. [find](https://scholar.google.com/scholar?q=D%2E+Beeferman%2C+A%2E+Berger%2C+J%2E+D%2E+Lafferty%2E+1999%2E+Statistical+models+for+text+segmentation%2E+Machine+Learning%2C+34%281%2D3%29%3A177%E2%80%93210%2E)
2. F. Choi, P. Wiemer-Hastings, J. Moore. 2001. Latent semantic analysis for text segmentation. In Proceedings of EMNLP, 109–117. [find](https://scholar.google.com/scholar?q=F%2E+Choi%2C+P%2E+Wiemer%2DHastings%2C+J%2E+Moore%2E+2001%2E+Latent+semantic+analysis+for+text+segmentation%2E+In+Proceedings+of+EMNLP%2C+109%E2%80%93117%2E)
3. F. Y. Y. Choi. 2000. [Advances in domain independent linear text segmentation](https://md.research.elamur.ai/free/en/papers/choi-2000-advances-domain-independent-linear-text/). In Proceedings of the NAACL, 26–33.
4. K. W. Church. 1993. Char align: A program for aligning parallel texts at the character level. In Proceedings of the ACL, 1–8. [find](https://scholar.google.com/scholar?q=K%2E+W%2E+Church%2E+1993%2E+Char+align%3A+A+program+for+aligning+parallel+texts+at+the+character+level%2E+In+Proceedings+of+the+ACL%2C+1%E2%80%938%2E)
5. M. Galley, K. McKeown, E. Fosler-Lussier, H. Jing. 2003. [Discourse segmentation of multi-party conversation](https://md.research.elamur.ai/free/en/papers/galley-2003-discourse-segmentation-multi-party-conversation/). In Proceedings of the ACL, 562–569.
6. J. R. Glass. 2003. A probabilistic framework for segment-based speech recognition. Computer Speech and Language, 17(2–3):137–152. [find](https://scholar.google.com/scholar?q=J%2E+R%2E+Glass%2E+2003%2E+A+probabilistic+framework+for+segment%2Dbased+speech+recognition%2E+Computer+Speech+and+Language%2C+17%282%E2%80%933%29%3A137%E2%80%93152%2E)
7. A. Gruenstein, J. Niekrasz, M. Purver. 2005. Meeting structure annotation: Data and tools. In Proceedings of the SIGdial Workshop on Discourse and Dialogue, 117–127. [find](https://scholar.google.com/scholar?q=A%2E+Gruenstein%2C+J%2E+Niekrasz%2C+M%2E+Purver%2E+2005%2E+Meeting+structure+annotation%3A+Data+and+tools%2E+In+Proceedings+of+the+SIGdial+Workshop+on+Discourse+and+Dialogue%2C+117%E2%80%93127%2E)
8. M. A. K. Halliday, R. Hasan. 1976. Cohesion in English. Longman, London. [find](https://scholar.google.com/scholar?q=M%2E+A%2E+K%2E+Halliday%2C+R%2E+Hasan%2E+1976%2E+Cohesion+in+English%2E+Longman%2C+London%2E)
9. M. Hearst. 1994. Multi-paragraph segmentation of expository text. In Proceedings of the ACL, 9–16. [find](https://scholar.google.com/scholar?q=M%2E+Hearst%2E+1994%2E+Multi%2Dparagraph+segmentation+of+expository+text%2E+In+Proceedings+of+the+ACL%2C+9%E2%80%9316%2E)
10. X. Ji, H. Zha. 2003. Domain-independent text segmentation using anisotropic diffusion and dynamic programming. In Proceedings of SIGIR, 322–329. [find](https://scholar.google.com/scholar?q=X%2E+Ji%2C+H%2E+Zha%2E+2003%2E+Domain%2Dindependent+text+segmentation+using+anisotropic+diffusion+and+dynamic+programming%2E+In+Proceedings+of+SIGIR%2C+322%E2%80%93329%2E)
11. A. Kehagias, P. Fragkou, V. Petridis. 2003. Linear text segmentation using a dynamic programming algorithm. In Proceedings of the EACL, 171–178. [find](https://scholar.google.com/scholar?q=A%2E+Kehagias%2C+P%2E+Fragkou%2C+V%2E+Petridis%2E+2003%2E+Linear+text+segmentation+using+a+dynamic+programming+algorithm%2E+In+Proceedings+of+the+EACL%2C+171%E2%80%93178%2E)
12. E. Leeuwis, M. Federico, M. Cettolo. 2003. Language modeling and transcription of the ted corpus lectures. In Proceedings of ICASSP, 232–235. [find](https://scholar.google.com/scholar?q=E%2E+Leeuwis%2C+M%2E+Federico%2C+M%2E+Cettolo%2E+2003%2E+Language+modeling+and+transcription+of+the+ted+corpus+lectures%2E+In+Proceedings+of+ICASSP%2C+232%E2%80%93235%2E)
13. L. Pevzner, M. Hearst. 2002. [A critique and improvement of an evaluation metric for text segmentation](https://md.research.elamur.ai/free/en/papers/pevzner-2002-critique-improvement-evaluation-metric-text/). Computational Linguistics, 28(1):pp. 19–36.
14. M. F. Porter. 1980. An algorithm for suffix stripping. Program, 14(3):130–137. [find](https://scholar.google.com/scholar?q=M%2E+F%2E+Porter%2E+1980%2E+An+algorithm+for+suffix+stripping%2E+Program%2C+14%283%29%3A130%E2%80%93137%2E)
15. J. Reynar. 1998. Topic segmentation: Algorithms and applications. Ph.D. thesis, University of Pennsylvania. [find](https://scholar.google.com/scholar?q=J%2E+Reynar%2E+1998%2E+Topic+segmentation%3A+Algorithms+and+applications%2E+Ph%2ED%2E+thesis%2C+University+of+Pennsylvania%2E)
16. G. Salton, C. Buckley. 1988. Term weighting approaches in automatic text retrieval. Information Processing and Management, 24(5):513–523. [find](https://scholar.google.com/scholar?q=G%2E+Salton%2C+C%2E+Buckley%2E+1988%2E+Term+weighting+approaches+in+automatic+text+retrieval%2E+Information+Processing+and+Management%2C+24%285%29%3A513%E2%80%93523%2E)
17. J. Shi, J. Malik. 2000. Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(8):888–905. [find](https://scholar.google.com/scholar?q=J%2E+Shi%2C+J%2E+Malik%2E+2000%2E+Normalized+cuts+and+image+segmentation%2E+IEEE+Transactions+on+Pattern+Analysis+and+Machine+Intelligence%2C+22%288%29%3A888%E2%80%93905%2E)
18. J. Swets. 1988. Measuring the accuracy of diagnostic systems. Science, 240(4857):1285–1293. [find](https://scholar.google.com/scholar?q=J%2E+Swets%2E+1988%2E+Measuring+the+accuracy+of+diagnostic+systems%2E+Science%2C+240%284857%29%3A1285%E2%80%931293%2E)
19. M. Utiyama, H. Isahara. 2001. [A statistical model for domain-independent text segmentation](https://md.research.elamur.ai/free/en/papers/utiyama-2001-statistical-model-domain-independent-text/). In Proceedings of the ACL, 499–506.

*Updated 24 October 2026*