tag:blogger.com,1999:blog-8664528597652630272011-08-02T12:04:56.118-07:00Arizona BayesBrian McFeehttp://www.blogger.com/profile/02807470540740721645noreply@blogger.comBlogger31100tag:blogger.com,1999:blog-866452859765263027.post-34560316955374637742009-11-22T12:10:00.000-08:002009-11-23T21:23:44.561-08:00The Traveling Salesmix<span style="font-weight: bold;">THE WIND-UP</span><br /><br />Imagine that you're throwing a <a href="http://nips.cc/">party</a>, 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.<br /><br />What's more, your guests are <a href="http://en.wikipedia.org/wiki/David_Hasselhoff">remorseless party machines</a> 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, <a href="http://apps.facebook.com/quiztape">the mix</a> <a href="http://icanhascheezburger.com/2007/01/28/spice-must-flow/">must flow</a>. What do you do?<br /><br /><br /><a name='more'></a><br /><br /><span style="font-weight: bold;">THE PITCH</span><br /><br />This can be modeled as a <a href="http://en.wikipedia.org/wiki/Traveling_salesman_problem">Traveling Salesman Problem</a>:<br /><ol><li>Define a complete graph G where each node is a song in your collection</li><li>Edge weights correspond to some notion of distance between songs</li><li>Find a simple path touching all nodes in G with minimal total weight</li></ol><br /><span style="font-weight: bold;">THE DETAILS</span><br /><br /><ol><li>The first step is to analyze the content of each song. <a href="http://echonest.com/">The Echo Nest</a> makes this incredibly easy with <a href="http://code.google.com/p/pyechonest/">pyEchoNest</a>. From this, we can model the timbral features of each song by a multivariate Gaussian. <a href="http://numpy.scipy.org/">NumPy</a> to the rescue!</li><li>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 <a href="http://jmlr.csail.mit.edu/papers/volume5/jebara04a/jebara04a.pdf">Probability Product Kernel</a>. Some people might prefer <a href="http://en.wikipedia.org/wiki/KL_divergence">KL divergence</a>, but PPK induces a metric, which will allow for more accurate TSP approximations.</li><li>Given the kernel matrix K, we can compute its corresponding distance matrix, which then forms the weights of the graph.</li><li>Run your <a href="http://en.wikipedia.org/wiki/Christofides_algorithm">favorite TSP approximator</a> on the graph, and you're set!</li></ol><span style="font-weight: bold;"><br />THE RESULTS</span><br /><br />Exhibit A, an alphabetized playlist:<span style="font-size: 78%;"><br /></span><br /><ol style="font-family: courier new;"><li><span style="font-size: 78%;">Avalanches_-_Since_I_Left_You/(13) Frontier Psychiatrist</span></li><li><span style="font-size: 78%;">Banyan_-_Anytime_At_All/(11) Sputnik</span></li><li><span style="font-size: 78%;">Cake_-_Prolonging_the_Magic/(07) Sheep Go to Heaven</span></li><li><span style="font-size: 78%;">Curtis_Mayfield_-_Superfly/(03) Freddie's Dead</span></li><li><span style="font-size: 78%;">Elvis_Costello_-_Best_Of/(07) Elvis Costello & The Attractions - Pump It Up</span></li><li><span style="font-size: 78%;">Madame_Blavatsky_Overdrive_-_Idiot_Jones_Will_Have_His_Day/07 MBO</span></li><li><span style="font-size: 78%;">MC_Chris_-_Life's_A_Bitch_and_I'm_Her_Pimp/(07) Fett's Vette</span></li><li><span style="font-size: 78%;">Parliament_-_Mothership_Connection/(03) Unfunky UFO</span></li><li><span style="font-size: 78%;">Propellerheads_-_Decksanddrumsandrockandroll/(10) Propellerheads & David Arnold - On Her Majesty's Secret Service</span></li><li><span style="font-size: 78%;">Red_Elvises_-_Surfing_in_Siberia/(05) Hungarian Dance #5</span></li><li><span style="font-size: 78%;">Soundtrack_-_Lock_Stock_and_Two_Smoking_Barrels/(16) James Brown - The Payback</span></li><li><span style="font-size: 78%;">Soundtrack_-_The_Big_Lebowski/(03) Elvis Costello - My Mood Swings</span></li><li><span style="font-size: 78%;">Squirrel_Nut_Zippers_-_Hot/(07) Hell</span></li><li><span style="font-size: 78%;">The_J.B.'s_-_Funky_Good_Time:_The_Anthology_[1]/(12) Watermelon Man</span></li><li><span style="font-size: 78%;">Thievery_Corporation_-_The_Mirror_Conspiracy/(04) Lebanese Blonde</span></li></ol><br />Exhibit B, the ordered mix:<span style="font-size: 78%;"><br /></span><br /><ol><li style="font-family: courier new;"><span style="font-family: courier new; font-size: 78%;">Avalanches_-_Since_I_Left_You/(13) Frontier Psychiatrist</span></li><li style="font-family: courier new;"><span style="font-family: courier new; font-size: 78%;">Banyan_-_Anytime_At_All/(11) Sputnik</span></li><li style="font-family: courier new;"><span style="font-family: courier new; font-size: 78%;">Propellerheads_-_Decksanddrumsandrockandroll/(10) Propellerheads & David Arnold - On Her Majesty's Secret Service</span></li><li style="font-family: courier new;"><span style="font-family: courier new; font-size: 78%;">Elvis_Costello_-_Best_Of/(07) Elvis Costello & The Attractions - Pump It Up</span></li><li style="font-family: courier new;"><span style="font-family: courier new; font-size: 78%;">Cake_-_Prolonging_the_Magic/(07) Sheep Go to Heaven</span></li><li style="font-family: courier new;"><span style="font-family: courier new; font-size: 78%;">Parliament_-_Mothership_Connection/(03) Unfunky UFO</span></li><li style="font-family: courier new;"><span style="font-family: courier new; font-size: 78%;">The_J.B.'s_-_Funky_Good_Time:_The_Anthology_[1]/(12) Watermelon Man</span></li><li style="font-family: courier new;"><span style="font-family: courier new; font-size: 78%;">Thievery_Corporation_-_The_Mirror_Conspiracy/(04) Lebanese Blonde</span></li><li style="font-family: courier new;"><span style="font-family: courier new; font-size: 78%;">Curtis_Mayfield_-_Superfly/(03) Freddie's Dead</span></li><li style="font-family: courier new;"><span style="font-family: courier new; font-size: 78%;">Red_Elvises_-_Surfing_in_Siberia/(05) Hungarian Dance #5</span></li><li style="font-family: courier new;"><span style="font-family: courier new; font-size: 78%;">Soundtrack_-_The_Big_Lebowski/(03) Elvis Costello - My Mood Swings</span></li><li style="font-family: courier new;"><span style="font-family: courier new; font-size: 78%;">Madame_Blavatsky_Overdrive_-_Idiot_Jones_Will_Have_His_Day/07 MBO</span></li><li style="font-family: courier new;"><span style="font-family: courier new; font-size: 78%;">MC_Chris_-_Life's_A_Bitch_and_I'm_Her_Pimp/(07) Fett's Vette</span></li><li style="font-family: courier new;"><span style="font-family: courier new; font-size: 78%;">Soundtrack_-_Lock_Stock_and_Two_Smoking_Barrels/(16) James Brown - The Payback</span></li><li style="font-family: courier new;"><span style="font-family: courier new; font-size: 78%;">Squirrel_Nut_Zippers_-_Hot/(07) Hell<br /><br /></span><br /></li></ol><br /><span style="font-weight: bold;">THE CODE</span><br /><br />Try it out. You can download python code for this <a href="http://www.cse.ucsd.edu/%7Ebmcfee/code/tsmix.py">here</a>. You will need the following:<br /><ul><li>An Echo Nest <a href="http://developer.echonest.com/">API key</a></li><li><a href="http://code.google.com/p/pyechonest/">pyEchoNEst</a></li><li><a href="http://numpy.scipy.org/">NumPy</a></li><li><a href="http://code.google.com/p/python-graph/">python-graph</a></li><li>Some mp3s...</li></ul>Note: for simplicity, the code above implements the 2-approximate metric TSP, not the 1.5-approximate Christofides' algorithm.<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/866452859765263027-3456031695537463774?l=arizonabayes.blogspot.com' alt='' /></div>Brian McFeehttp://www.blogger.com/profile/02807470540740721645noreply@blogger.com0tag:blogger.com,1999:blog-866452859765263027.post-46159005565132339842008-12-11T17:51:00.000-08:002008-12-12T18:47:15.123-08:00Deep thoughtsFor all for alls, there exist there exists, but not without not.<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/866452859765263027-4615900556513233984?l=arizonabayes.blogspot.com' alt='' /></div>Brian McFeehttp://www.blogger.com/profile/02807470540740721645noreply@blogger.com0tag:blogger.com,1999:blog-866452859765263027.post-7560265066535907362008-11-28T18:48:00.001-08:002009-11-23T21:24:13.683-08:00ProcessingThanks to popular demand, I'm starting a new blog. It will overflow with technical nuggets of joy. Oh yes.<br /><br />To celebrate the <a href="http://blog.makezine.com/archive/2008/11/processing_10_officially.html?CMP=OTC-0D6B48984890">release</a> of <a href="http://processing.org/">Processing</a> 1.0, I decided to give it a spin. Matlab's visualization tools, while functional, sorely lack in the aesthetics department. The applet below is the result of a lazy Thanksgiving afternoon of hacking to display the results of some ontological embedding code I've been working on.<br /><br /><a name='more'></a><br /><br /><iframe height="300" scrolling="no" src="http://morrison.ucsd.edu/blog/processing1128/embed.html" style="border: medium none; margin: 0pt; padding: 0pt;" width="460"></iframe><br /><br />(Controls: <, > to scale images, 'r' to reset, 't' to toggle text, and shift-click to drag.)<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/866452859765263027-756026506653590736?l=arizonabayes.blogspot.com' alt='' /></div>Brian McFeehttp://www.blogger.com/profile/02807470540740721645noreply@blogger.com1