Kompressionsbasierte Mustererkennung

Abstract

Seit der Entwicklung der Normalisierten Kompressionsdistanz (in engl. Normalized Compression Distance – NCD) mitsamt ihren beeindruckenden Fähigkeiten, gewann kompressionsbasierte Mustererkennung immer mehr an Anerkennung. Die Arbeit beschäftigt sich daher mit der NCD und den damit verbundenen Theorien und Experimenten um genauer zu verstehen, was wirklich dieses Verfahren ausmacht und was für dessen Ergebnisse verantwortlich ist. Augenblicklich gibt es noch eine große Lücke zwischen der praktischen Anwendung der kompressionsbasierten Mustererkennung und deren Fundament, der Kolmogorovkomplexität. Cilibrasi und Vitanyi haben zwar die NCD erfolgreich mit Hilfe der Kolmogorovkomplexität motiviert, jedoch aufgrund der Unberechenbarkeit dieses Komplexitätsmaßes noch keine echte Verbindung zwischen den beiden Methoden hergestellt. Des weiteren ist die NCD bisher auch weitgehend auf diskrete Daten beschränkt. Jede Anwendung auf kontinuierliche Daten behandelt diese, als wären sie diskret. Im Rahmen dieser Arbeit werden die zugrunde liegenden Prinzipien der NCD untersucht. Dazu wird die Theorie und deren praktische Anwendung betrachtet, um aufbauend auf diesen Erkenntnissen, Mustererkennungsverfahren zu entwickeln, die die Essenz der kompressionsbasiertenMustererkennung darstellen. Dabei wird eine Theorie der kompressionsbasiertenMustererkennung, die die Ergebnisse der NCD erklären kann und auch inhärent kontinuierlicheMethoden erlaubt, entwickelt. Zu dieser Theorie werden auch sowohl die notwendigen mathematischen Beweise als auch praktische Experimente präsentiert. Alles in allem wird der kompressionsbasierten Mustererkennung ein theoretisches Fundament sowie ein neuer Blickwinkel gegeben.

Since the discovery of the Normalized Compression Distance (NCD) and its impressive abilities, Compression Based Pattern recognition has gained widespread recognition. This was sufficient for us to look under the hood of the NCD to gain deep and well founded insights into the area of what is up to now called Compression Based Pattern Recognition. While looking at the NCD and its theoretical foundation, we found that there is a large gap between Kolmogorov complexity and the NCD. Cilibrasi und Vitanyi have successfully motivated the NCD by using the Kolmogorov complexity as a measure of similarity. Due to its incomputability, they failed to actually connect the NCD to its theoretical motivation and, besides that, the NCD largely lacks any support for continuous data. There is work on the NCD for image data but it takes no notice of the actual underlying continuous data. In the course of this work we are researching the underlying principles of the NCD. Based on these findings we are developing algorithms which are focused solely on pattern recognition and represent the essence of Compression Based Pattern Recognition. We are extending these ideas to continuous pattern matching and thereby present an unifying theory which justifies the generallity of the denomination Compression Based Pattern Recognition. For all our findings we are also presenting detailed numerical experiments and formal mathematical proofs. All in all we are giving the area of Compression Based Pattern Recognition a theoretical foundation as well as a new point of view.