  Segmental structure is a common pattern in many types of sequences such as
phrases in human languages. In this paper, we present a probabilistic model for
sequences via their segmentations. The probability of a segmented sequence is
calculated as the product of the probabilities of all its segments, where each
segment is modeled using existing tools such as recurrent neural networks.
Since the segmentation of a sequence is usually unknown in advance, we sum over
all valid segmentations to obtain the final probability for the sequence. An
efficient dynamic programming algorithm is developed for forward and backward
computations without resorting to any approximation. We demonstrate our
approach on text segmentation and speech recognition tasks. In addition to
quantitative results, we also show that our approach can discover meaningful
segments in their respective application contexts.
