Melody Classification using a Similarity Metric based on Kolmogorov Complexity

Vitanyi and his co-workers [5] have reported some success using a universal similarity metric based on Kolmogorov complexity for a variety of classification tasks, including music genre recognition. This paper describes new experiments in this direction, and compares the results with some alternative approaches. Somewhat to our surprise given its non-specific universal nature, the Kolmogorov complexity similarity based technique outperformed the others. The task used for our experiments involved classification of MIDI files into one of 4 groups. Two of the categories were western classical music composed by Beethoven (302 files) and Haydn (261 files). The remaining categories were Chinese music (80 files) and Jazz (128 files). Melody contours (i.e. pitch sequences without timing details) were extracted from the MIDI file tracks. Both relative and absolute and pitch contours were used. The best performance of 92.35% was achieved by a 1-nearest neighbour classifier with normalized information distance based on Kolmogorov complexity estimates over pitch interval contours. A notable feature of our work is the use of the number of blocks in a pure Lempel-Zip parse of a string to estimate its Kolmogorov complexity.