A Maximum Entropy Approach to Natural Language Processing

5.3 Segmentation

1. What is a rift, and why did Candide need safe segmentations?
   Candide’s processing time was exponential in input length, so long French sentences had to be split. A rift is a position \(j\) where all French words to the left align to English words left of \(y_j\)’s English word and all to the right align to the right; splitting only at rifts means no English word must account for French words in two segments.
   • Berger et al., 1996, A Maximum Entropy Approach to Natural Language Processing (Computational Linguistics), §5.3
2. How was the rift model used to segment sentences?
   A maximum entropy model scored \(p(\text{rift} \mid x)\) at each position from a six-word window, POS tags and word classes; dynamic programming then chose segment boundaries with no segment longer than 10 words. Segments needn’t be semantically coherent, only translatable left to right.
   • Berger et al., 1996, A Maximum Entropy Approach to Natural Language Processing (Computational Linguistics), §5.3