The Traveling Salesmix

THE WIND-UP

Imagine that you're throwing a party, and your friends have elected you Music Czar. Your task is to provide continuous background music throughout the night. Each guest has provided you with a list of songs they would like to hear, but the order of the tracks is random, and styles vary wildly from one guest to another.

What's more, your guests are remorseless party machines who will undoubtedly stay up well into the next morning, so your mix will have to be several hours long. If the ordering of songs is too jumpy, the guests may revolt and trash your place. Since you would like to see your security deposit again, the mix must flow. What do you do?




THE PITCH

This can be modeled as a Traveling Salesman Problem:

1. Define a complete graph G where each node is a song in your collection
2. Edge weights correspond to some notion of distance between songs
3. Find a simple path touching all nodes in G with minimal total weight

THE DETAILS

1. The first step is to analyze the content of each song. The Echo Nest makes this incredibly easy with pyEchoNest. From this, we can model the timbral features of each song by a multivariate Gaussian. NumPy to the rescue!
2. Now we have a bunch of statistical models, but we need some notion of distance between these models. The notion I'll use here is the Euclidean metric applied to a Probability Product Kernel. Some people might prefer KL divergence, but PPK induces a metric, which will allow for more accurate TSP approximations.
3. Given the kernel matrix K, we can compute its corresponding distance matrix, which then forms the weights of the graph.
4. Run your favorite TSP approximator on the graph, and you're set!

THE RESULTS

Exhibit A, an alphabetized playlist:

1. Avalanches_-_Since_I_Left_You/(13) Frontier Psychiatrist
2. Banyan_-_Anytime_At_All/(11) Sputnik
3. Cake_-_Prolonging_the_Magic/(07) Sheep Go to Heaven
4. Curtis_Mayfield_-_Superfly/(03) Freddie's Dead
5. Elvis_Costello_-_Best_Of/(07) Elvis Costello & The Attractions - Pump It Up
6. Madame_Blavatsky_Overdrive_-_Idiot_Jones_Will_Have_His_Day/07 MBO
7. MC_Chris_-_Life's_A_Bitch_and_I'm_Her_Pimp/(07) Fett's Vette
8. Parliament_-_Mothership_Connection/(03) Unfunky UFO
9. Propellerheads_-_Decksanddrumsandrockandroll/(10) Propellerheads & David Arnold - On Her Majesty's Secret Service
10. Red_Elvises_-_Surfing_in_Siberia/(05) Hungarian Dance #5
11. Soundtrack_-_Lock_Stock_and_Two_Smoking_Barrels/(16) James Brown - The Payback
12. Soundtrack_-_The_Big_Lebowski/(03) Elvis Costello - My Mood Swings
13. Squirrel_Nut_Zippers_-_Hot/(07) Hell
14. The_J.B.'s_-_Funky_Good_Time:_The_Anthology_[1]/(12) Watermelon Man
15. Thievery_Corporation_-_The_Mirror_Conspiracy/(04) Lebanese Blonde

Exhibit B, the ordered mix:

1. Avalanches_-_Since_I_Left_You/(13) Frontier Psychiatrist
2. Banyan_-_Anytime_At_All/(11) Sputnik
3. Propellerheads_-_Decksanddrumsandrockandroll/(10) Propellerheads & David Arnold - On Her Majesty's Secret Service
4. Elvis_Costello_-_Best_Of/(07) Elvis Costello & The Attractions - Pump It Up
5. Cake_-_Prolonging_the_Magic/(07) Sheep Go to Heaven
6. Parliament_-_Mothership_Connection/(03) Unfunky UFO
7. The_J.B.'s_-_Funky_Good_Time:_The_Anthology_[1]/(12) Watermelon Man
8. Thievery_Corporation_-_The_Mirror_Conspiracy/(04) Lebanese Blonde
9. Curtis_Mayfield_-_Superfly/(03) Freddie's Dead
10. Red_Elvises_-_Surfing_in_Siberia/(05) Hungarian Dance #5
11. Soundtrack_-_The_Big_Lebowski/(03) Elvis Costello - My Mood Swings
12. Madame_Blavatsky_Overdrive_-_Idiot_Jones_Will_Have_His_Day/07 MBO
13. MC_Chris_-_Life's_A_Bitch_and_I'm_Her_Pimp/(07) Fett's Vette
14. Soundtrack_-_Lock_Stock_and_Two_Smoking_Barrels/(16) James Brown - The Payback
15. Squirrel_Nut_Zippers_-_Hot/(07) Hell
    
    
    

THE CODE

Try it out. You can download python code for this here. You will need the following:

• An Echo Nest API key
• pyEchoNEst
• NumPy
• python-graph
• Some mp3s...

Note: for simplicity, the code above implements the 2-approximate metric TSP, not the 1.5-approximate Christofides' algorithm.