Complexity Preserving Functions
Jan Lemeire · VUBIR (Vrije Universiteit Brussel) · 2003
It’s widely recognized that compression is useful and even necessary for inductive learning, where a short description will capture the ‘regularities’. We introduce complexitypreserving functions that preserve these regularities of the concept. They are based on the universal information distance [Bennett et al. ‘97] and define for an instance a set of elements sharing the same complexity type. This corresponds to the two-part code [Rissanen ‘89] of the MDL principle, when it is interpreted as the first term describing the set and the second term the element in the set [Rissanen 99]. We investigate its importance in inductive learning.