Unsupervised hierarchical probabilistic segmentation of discrete events1
| Autor: | Guy Shani, Christopher Meek, Asela Gunawardana |
|---|---|
| Rok vydání: | 2011 |
| Předmět: |
Conditional entropy
business.industry Segmentation-based object categorization Computer science Probabilistic logic Scale-space segmentation Pattern recognition Image segmentation Machine learning computer.software_genre Theoretical Computer Science Market segmentation Artificial Intelligence Segmentation Computer Vision and Pattern Recognition Artificial intelligence business Categorical variable computer |
| Zdroj: | Intelligent Data Analysis. 15:483-501 |
| ISSN: | 1571-4128 1088-467X |
| Popis: | Segmentation, the task of splitting a long sequence of symbols into chunks, can provide important information about the nature of the sequence that is understandable to humans. We focus on unsupervised segmentation, where the algorithm never sees examples of successful segmentation, but still needs to discover meaningful segments. In this paper we present an unsupervised learning algorithm for segmenting sequences of symbols or categorical events. Our algorithm hierarchically builds a lexicon of segments and computes a maximum likelihood segmentation given the current lexicon. Thus, our algorithm is most appropriate to hierarchical sequences, where smaller segments are grouped into larger segments. Our probabilistic approach also allows us to suggest conditional entropy as a measure of the quality of a segmentation in the absence of labeled data. We compare our algorithm to two previous approaches from the unsupervised segmentation literature, showing it to provide superior segmentation over a number of benchmarks. Our specific motivation for developing this general algorithm is to understand the behavior of software programs after deployment by analyzing their traces. We explain and motivate the importance of this problem, and present segmentation results from the interactions of a web service and its clients. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|