Title 



Fast sequence segmentation using loglinear models
 
Author 


  
Abstract 



Sequence segmentation is a wellstudied problem, where given a sequence of elements, an integer K, and some measure of homogeneity, the task is to split the sequence into K contiguous segments that are maximally homogeneous. A classic approach to find the optimal solution is by using a dynamic program. Unfortunately, the execution time of this program is quadratic with respect to the length of the input sequence. This makes the algorithm slow for a sequence of nontrivial length. In this paper we study segmentations whose measure of goodness is based on loglinear models, a rich family that contains many of the standard distributions. We present a theoretical result allowing us to prune many suboptimal segmentations. Using this result, we modify the standard dynamic program for 1D loglinear models, and by doing so reduce the computational time. We demonstrate empirically, that this approach can significantly reduce the computational burden of finding the optimal segmentation.   
Language 



English
 
Source (journal) 



Data mining and knowledge discovery.  Boston, Mass.  
Publication 



Boston, Mass. : 2013
 
ISSN 



13845810
 
Volume/pages 



27:3(2013), p. 421441
 
ISI 



000322454200007
 
Full text (Publishers DOI) 


  
Full text (publishers version  intranet only) 


  
