TL;DR
This paper tackles the challenge of automatically segmenting spoken language into meaningful sentences, a crucial step for many speech processing applications. They introduce a novel "Maximum-Entropy-Weighted Bi-directional N-gram" (MEBN) approach that combines left-to-right and right-to-left language models, weighted by a maximum entropy model, to significantly improve segmentation accuracy over traditional methods.
What Problem Does This Paper Address?
Spoken language user interfaces, dialogue systems, and translation systems often receive input from speech recognition systems that lack punctuation. This raw, unsegmented output, like the Chinese example "这边请您坐电梯到9 楼服务生将在那里等您并将您带到913 号房间," is difficult for subsequent language analysis modules to parse. While humans can often infer sentence boundaries, even they disagree, making automatic segmentation a significant challenge. Existing methods often rely on acoustic cues (like pauses) or linguistic clues. However, traditional N-gram language models primarily consider the left context of a potential boundary, leading to errors like splitting long sentences incorrectly. This paper aims to overcome this limitation by incorporating both left and right contextual information for more robust utterance segmentation.
Methods
The core of this paper is the development of the Maximum-Entropy-Weighted Bi-directional N-gram (MEBN) algorithm. It builds upon two foundational approaches:
- Normal N-gram (NN) Algorithm: This standard method segments utterances by considering the probability of word sequences from left to right. It evaluates a potential boundary based on the left context.
- Reverse N-gram (RN) Algorithm: This novel approach, introduced by the authors, mirrors the NN algorithm but processes word sequences from right to left, thus leveraging the right context.
The MEBN algorithm then combines the strengths of NN and RN. It doesn't simply average their outputs; instead, it uses a maximum entropy model to learn optimal weights for combining the NN and RN results. This maximum entropy model considers features derived from the lexical context (words to the left and right of a potential boundary) to determine how much influence each model should have. The paper also details the feature functions and parameter estimation (using Generalized Iterative Scaling) for the maximum entropy component.
Datasets
The authors trained and evaluated their models on both Chinese and English corpora.
- Training Corpora: These covered domains like hotel reservation, flight booking, traffic information, and daily life. Punctuation was removed, and full stops were replaced with "SB" (sentence boundary). Chinese characters and English words were used as units, without part-of-speech tags.
- Testing Corpora: Similar to the training data, these were also domain-specific and had punctuation removed.
The paper provides tables summarizing the size and characteristics of these corpora.
Key Insights and Ideas
- The Importance of Bidirectional Context: The paper strongly argues that relying solely on left-to-right context for utterance segmentation is insufficient. Incorporating right-to-left context significantly improves accuracy.
- Maximum Entropy for Adaptive Weighting: Using a maximum entropy model to dynamically weight the contributions of left-to-right and right-to-left models based on local lexical context is a key innovation. This allows the system to adapt to different linguistic situations.
- MEBN's Error Skipping Prowess: The MEBN approach not only identifies correct boundaries but also effectively "skips" or avoids incorrect boundaries identified by the simpler N-gram methods. This is a crucial aspect of its improved performance.
- Human Performance as a Benchmark: The paper acknowledges that even human annotators struggle with consistent utterance segmentation, highlighting the inherent difficulty of the task and the need for robust computational methods.
Key Results
The MEBN algorithm demonstrated superior performance compared to the normal N-gram (NN), reverse N-gram (RN), and a simple bi-directional N-gram (BN) approach.
- Chinese Utterance Segmentation: MEBN achieved the highest F-score (86.3%), outperforming NN (81.9%), RN (83.0%), and BN (84.9%). It improved precision by 7.3% and recall by 1.5% over NN.
- English Utterance Segmentation: MEBN also led in English, with an F-score of 81.7%, compared to NN (77.9%), RN (78.8%), and BN (80.2%). It improved precision by 5.4% and recall by 1.9% over NN.
- Qualitative Analysis: The results showed that MEBN effectively skipped incorrect segments identified by NN and introduced fewer new errors compared to BN. The learned weights from the maximum entropy model were shown to have a direct beneficial effect on segmentation.
Limitations and Future Work
- Technical Challenge with Maximum Entropy: The paper notes a technical challenge in the maximum entropy approach: when a "Matching String" (a feature used in the model) contains a sentence boundary mark ("SB"), it's unclear whether it belongs to the prefix or suffix of the candidate site until segmentation proceeds. This creates uncertainty, especially when segmenting from left to right or right to left. The MEBN approach is presented as a pragmatic solution to this.
- Domain Specificity: While the models were trained on specific domains (hotel, flight, etc.), the generalizability to entirely different domains or more spontaneous speech might be a future area of exploration.
- Further Refinement of Weights: The paper suggests that the weights learned by the maximum entropy model not only modify NN and RN but also have a direct beneficial effect, hinting at potential further research into optimizing these weighting mechanisms.
Summary updated