- 【Updated on May 12, 2025】 Integration of CiNii Dissertations and CiNii Books into CiNii Research
- Trial version of CiNii Research Knowledge Graph Search feature is available on CiNii Labs
- Suspension and deletion of data provided by Nikkei BP
- Regarding the recording of “Research Data” and “Evidence Data”
An MDL-based change-detection algorithm with its applications to learning piecewise stationary memoryless sources
Description
Kleinberg has proposed an algorithm for detecting bursts from a data sequence, which has turned out to be effective in the scenario of data mining, such as topic detection, change-detection. In this paper we extend Kleinberg's algorithm in an information-theoretic fashion to obtain a new class of algorithms and apply it into learning of piecewise stationary memoryless sources (PSMSs). The keys of the proposed algorithm are; 1) the parameter space is discretized so that discretization scale depends on the Fisher information, and 2) the optimal path over the discretized parameter space is efficiently computed using the dynamic programming method so that the sum of the data and parameter description lengths is minimized on the basis of the MDL principle. We prove that an upper bound on the total code-length for the proposed algorithm asymptotically matches Merhav's lower bound.
Journal
-
- 2012 IEEE Information Theory Workshop
-
2012 IEEE Information Theory Workshop 557-561, 2012-09-01
IEEE