Minimum message length grouping of ordered data

Leigh J Fitzgibbon; Lloyd Allison; David L Dowe

doi:10.1007/3-540-40992-0_5

Minimum message length grouping of ordered data

Leigh J Fitzgibbon, Lloyd Allison, David L Dowe

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

22 Citations (Scopus)

Abstract

Explicit segmentation is the partitioning of data into homogeneous regions by specifying cut-points. W. D. Fisher (1958) gave an early example of explicit segmentation based on the minimisation of squared error. Fisher called this the grouping problem and came up with a polynomial time Dynamic Programming Algorithm (DPA). Oliver, Baxter and colleagues (1996, 1997, 1998) have applied the informationtheoretic Minimum Message Length (MML) principle to explicit segmentation. They have derived formulas for specifying cut-points imprecisely and have empirically shown their criterion to be superior to other segmentation methods (AIC, MDL and BIC). We use a simple MML criterion and Fisher’s DPA to perform numerical Bayesian (summing and) integration (using message lengths) over the cut-point location parameters. This gives an estimate of the number of segments, which we then use to estimate the cut-point positions and segment parameters by minimising the MML criterion. This is shown to have lower Kullback-Leibler distances on generated data.

Original language	English
Title of host publication	Algorithmic Learning Theory
Subtitle of host publication	11th International Conference, ALT 2000 Sydney, Australia, December 11-13, 2000 Proceedings
Editors	Hiroki Arimura, Sanjay Jain, Arun Sharma
Place of Publication	Berlin Germany
Publisher	Springer
Pages	56-70
Number of pages	15
ISBN (Print)	3540412379
DOIs	https://doi.org/10.1007/3-540-40992-0_5
Publication status	Published - 2000
Event	Algorithmic Learning Theory 2000 - Sydney, Australia Duration: 11 Dec 2000 → 13 Dec 2000 Conference number: 11th https://link-springer-com.ezproxy.lib.monash.edu.au/book/10.1007/3-540-40992-0 (Proceedings)

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	1968
ISSN (Print)	0302-9743

Conference

Conference	Algorithmic Learning Theory 2000
Abbreviated title	ALT 2000
Country/Territory	Australia
City	Sydney
Period	11/12/00 → 13/12/00
Internet address	https://link-springer-com.ezproxy.lib.monash.edu.au/book/10.1007/3-540-40992-0 (Proceedings)

Access to Document

10.1007/3-540-40992-0_5

Cite this

Fitzgibbon, L. J., Allison, L., & Dowe, D. L. (2000). Minimum message length grouping of ordered data. In H. Arimura, S. Jain, & A. Sharma (Eds.), Algorithmic Learning Theory: 11th International Conference, ALT 2000 Sydney, Australia, December 11-13, 2000 Proceedings (pp. 56-70). (Lecture Notes in Computer Science; Vol. 1968). Springer. https://doi.org/10.1007/3-540-40992-0_5

@inproceedings{8912ecb967a545a681608928de9f4b95,

title = "Minimum message length grouping of ordered data",

abstract = "Explicit segmentation is the partitioning of data into homogeneous regions by specifying cut-points. W. D. Fisher (1958) gave an early example of explicit segmentation based on the minimisation of squared error. Fisher called this the grouping problem and came up with a polynomial time Dynamic Programming Algorithm (DPA). Oliver, Baxter and colleagues (1996, 1997, 1998) have applied the informationtheoretic Minimum Message Length (MML) principle to explicit segmentation. They have derived formulas for specifying cut-points imprecisely and have empirically shown their criterion to be superior to other segmentation methods (AIC, MDL and BIC). We use a simple MML criterion and Fisher{\textquoteright}s DPA to perform numerical Bayesian (summing and) integration (using message lengths) over the cut-point location parameters. This gives an estimate of the number of segments, which we then use to estimate the cut-point positions and segment parameters by minimising the MML criterion. This is shown to have lower Kullback-Leibler distances on generated data.",

author = "Fitzgibbon, \{Leigh J\} and Lloyd Allison and Dowe, \{David L\}",

year = "2000",

doi = "10.1007/3-540-40992-0\_5",

language = "English",

isbn = "3540412379",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "56--70",

editor = "Hiroki Arimura and Sanjay Jain and Arun Sharma",

booktitle = "Algorithmic Learning Theory",

address = "Switzerland",

note = "Algorithmic Learning Theory 2000, ALT 2000 ; Conference date: 11-12-2000 Through 13-12-2000",

url = "https://link-springer-com.ezproxy.lib.monash.edu.au/book/10.1007/3-540-40992-0",

}

Fitzgibbon, LJ, Allison, L & Dowe, DL 2000, Minimum message length grouping of ordered data. in H Arimura, S Jain & A Sharma (eds), Algorithmic Learning Theory: 11th International Conference, ALT 2000 Sydney, Australia, December 11-13, 2000 Proceedings. Lecture Notes in Computer Science, vol. 1968, Springer, Berlin Germany, pp. 56-70, Algorithmic Learning Theory 2000, Sydney, New South Wales, Australia, 11/12/00. https://doi.org/10.1007/3-540-40992-0_5

Minimum message length grouping of ordered data. / Fitzgibbon, Leigh J; Allison, Lloyd; Dowe, David L.
Algorithmic Learning Theory: 11th International Conference, ALT 2000 Sydney, Australia, December 11-13, 2000 Proceedings. ed. / Hiroki Arimura; Sanjay Jain; Arun Sharma. Berlin Germany: Springer, 2000. p. 56-70 (Lecture Notes in Computer Science; Vol. 1968).

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

TY - GEN

T1 - Minimum message length grouping of ordered data

AU - Fitzgibbon, Leigh J

AU - Allison, Lloyd

AU - Dowe, David L

N1 - Conference code: 11th

PY - 2000

Y1 - 2000

N2 - Explicit segmentation is the partitioning of data into homogeneous regions by specifying cut-points. W. D. Fisher (1958) gave an early example of explicit segmentation based on the minimisation of squared error. Fisher called this the grouping problem and came up with a polynomial time Dynamic Programming Algorithm (DPA). Oliver, Baxter and colleagues (1996, 1997, 1998) have applied the informationtheoretic Minimum Message Length (MML) principle to explicit segmentation. They have derived formulas for specifying cut-points imprecisely and have empirically shown their criterion to be superior to other segmentation methods (AIC, MDL and BIC). We use a simple MML criterion and Fisher’s DPA to perform numerical Bayesian (summing and) integration (using message lengths) over the cut-point location parameters. This gives an estimate of the number of segments, which we then use to estimate the cut-point positions and segment parameters by minimising the MML criterion. This is shown to have lower Kullback-Leibler distances on generated data.

AB - Explicit segmentation is the partitioning of data into homogeneous regions by specifying cut-points. W. D. Fisher (1958) gave an early example of explicit segmentation based on the minimisation of squared error. Fisher called this the grouping problem and came up with a polynomial time Dynamic Programming Algorithm (DPA). Oliver, Baxter and colleagues (1996, 1997, 1998) have applied the informationtheoretic Minimum Message Length (MML) principle to explicit segmentation. They have derived formulas for specifying cut-points imprecisely and have empirically shown their criterion to be superior to other segmentation methods (AIC, MDL and BIC). We use a simple MML criterion and Fisher’s DPA to perform numerical Bayesian (summing and) integration (using message lengths) over the cut-point location parameters. This gives an estimate of the number of segments, which we then use to estimate the cut-point positions and segment parameters by minimising the MML criterion. This is shown to have lower Kullback-Leibler distances on generated data.

UR - https://www.scopus.com/pages/publications/84974694581

U2 - 10.1007/3-540-40992-0_5

DO - 10.1007/3-540-40992-0_5

M3 - Conference Paper

SN - 3540412379

T3 - Lecture Notes in Computer Science

SP - 56

EP - 70

BT - Algorithmic Learning Theory

A2 - Arimura, Hiroki

A2 - Jain, Sanjay

A2 - Sharma, Arun

PB - Springer

CY - Berlin Germany

T2 - Algorithmic Learning Theory 2000

Y2 - 11 December 2000 through 13 December 2000

ER -

Minimum message length grouping of ordered data

Abstract

Publication series

Conference

Access to Document

Other files and links

Cite this