THE COMPLEXITY OF STRICT MINIMUM MESSAGE LENGTH INFERENCE
Dr Graham Farr, School of Computer Science and Software Engineering, Monash University, Victoria, Australia

Abstract: Strict Minimum Message Length (SMML) inference is an information-theoretic criterion for inductive inference introduced by Wallace and Boulton, and is known to possess several desirable statistical properties, although it is of interest more for theoretical than practical reasons. In this talk we examine its computational complexity. We give an efficient algorithm for the binomial case, and show that the problem in general is NP-hard. A heuristic is discussed which gives good results for binomial and trinomial SMML inference. The complexity of the trinomial case remains open.

This is joint work with Chris Wallace, Monash University.

This seminar was held at the Department of Computer Science, Royal Holloway, University of London on 14 May 2001.

back