Normalized Information Distance

DOI10.1007/978-0-387-84816-7_3MaRDI QIDQ3613556zbMATH OpenOpenAlexFDO

Authors Paul M. B. Vitányi, Frank J. Balbach, Rudi L. Cilibrasi, Ming Li

Publication date 12 March 2009

Published in Information Theory and Statistical Learning (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0809.2553

zbMATH Keywords

Kolmogorov complexity

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Abstract: The normalized information distance is a universal distance measure for objects of all kinds. It is based on Kolmogorov complexity and thus uncomputable, but there are ways to utilize it. First, compression algorithms can be used to approximate the Kolmogorov complexity if the objects have a string representation. Second, for names and abstract concepts, page count statistics from the World Wide Web can be used. These practical realizations of the normalized information distance can then be applied to machine learning tasks, expecially clustering, to perform feature-free and parameter-free data mining. This chapter discusses the theoretical foundations of the normalized information distance and both practical realizations. It presents numerous examples of successful real-world applications based on these distance measures, ranging from bioinformatics to music clustering to machine translation.

Recommendations

• Nonapproximability of the normalized information distance
• INFORMATION DISTANCE AND ITS APPLICATIONS
• Information Distance and Its Applications
• Common pitfalls using the normalized compression distance: what to watch out for in a compressor
• Evaluating the Impact of Information Distortion on Normalized Compression Distance

Cited in

(4)

• A confidence-set approach to signal denoising
• Normalized information distance and the oscillation hierarchy
• Compression-based distance between string data and its application to literary work classification based on authorship
• Nonapproximability of the normalized information distance

This page was built for publication: Normalized Information Distance

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3613556)