Licensed listening based on the habits of pirates or lessons from sloppy item resolution

from flickr user nozoomii, CC by-nc-sa

So I spent Thursday and Friday a couple weeks ago at the Barcelona Music Hackday, part of the Sónar Music Festival. There were loads of excellent hacks (full list), including my own, Legalize It!. In this post I'm going to go into a bit more depth about the hack, lessons learned and teasers for things I might do.

Motivation

The core idea is a simple one – straightforward listening to things that are popular on Bittorrent (note that popular on Bittorrent is a slightly fuzzy concept, since Bittorrent is protocol for ad-hoc distribution, but we'll get back to that in a bit), without all the nastiness (and DNS blocking!) of looking at, say, The Pirate Bay's top music torrents (that's a proxy of tpb btw).  And of course this removes any legal trouble that would be associated with gather and listening to music via those torrent charts.

How it all works

tl;dr - It's a torrent chart metadata-based content resolver, written in python and JS, you can fork the code.

Legalize It! has two parts, client and server. The server is a fairly simple pyramid webserver with two main tasks (it's deployed on heroku). The first involves fetching the torrent charts and resolving torrent release groups to legal streaming albums (Spotify, currently).  This is simply a matter of fetching the daily torrent releasegroup chart from the Musicmetric API (full disclosure, they're my employer and I wrote most of the chart endpoints...) then walking through the top N items that look like albums and matching them to spotify albums. The matching is done through a fantastically naive string title + artist search on spotify's metadata API via the very useful Spotimeta python wrapper. This album resolution process has a simple web interface (if it returns an error try a refresh, heroku workers on the free tier sleep a bit too much), that I mostly built for testing, but can be quite useful without the commitment of installing the Spotify App. In addition to the human readable page, you can get the response back as JSON, which is handy on the client side.

The second job for the server is necessary to help select which songs from the top albums we'll be listening to. The final Spotify app will only select on song per album, so users can get a taste of every album in the top N without having to listen to N complete albums.  But this should be done with care and grace to enhance the listening experience.  Thankfully, with the assistance of The Echo Nest's searchable audio summary song-level features this is quite easy.  Using their API we can search for a song by title and artist name (see a pattern of terrible id matching forming? What can I say, it's a hack.) and get back a set of descriptors that looks like this:

Once we have the set of song-level descriptors for every song in the neighbouring albums, it's simply a matter of minimizing the step size.  I've done a bit of work on playlists before, and this seemed like a reasonable approach.  While there are a number of approaches to step-size minimization, for this particular application we're doing a greedy sort of optimization that goes something like:

1.  Select the song a in album A and the song b in album B, such that for a given audio descriptor (we'll use dancibility by default, but it could just as easily be a different measure, eg. tempo, loudness) the absolute value of the descriptor of a less the descriptor of b is minimized.  That is to say we're looking for the song-pair from these two albums that are closest in terms of whatever descriptor is being used.
2. Select song c from album C such that the absolute difference from it's audio descriptor to song b's  is similarly minimized.
3. Repeat (2) for remaining albums, using the last chosen song against the next album.

It's worth noting that this is not the globally optimal shortest path from the first album to the last album, but it comes with a tremendous advantage -- the first two songs are selected without any need to deal with the rest of the playlist, which can be worked on overtime.  This allows for pseudo real time playlist creation, since we just need to know the next song before the current one is done playing.

To facilitate this algorithm the server has a hook that performs step (1) or (2) on on either a pair of albums or a song and album (specified as spotify URIs) can be accessed via a url that looks like  

http://legalize-it.herokuapp.com/paired/[spotify URI of track or album]/[spotify URI of album]

For example, http://legalize-it.herokuapp.com/paired/spotify:album:6LBiuhK7PZKjVXyMfPxPoh/spotify:album:5nVUqrdkEMlWTm9sqjrYBt which returns a bit of JSON showing the closest (by dancability) song pair between My Beautiful Dark Twisted Fantasy by Kanye West and Up All Night by One Direction.  This method also supports using any other audio summary feature being used for distance by adding it to the end of the URI.  For example http://legalize-it.herokuapp.com/paired/spotify:album:6LBiuhK7PZKjVXyMfPxPoh/spotify:album:5nVUqrdkEMlWTm9sqjrYBt/tempo find the closest song pair from the same two records, but by tempo rather than by dancebility.

These two features are laced together in the client, which is a simple spotify app, that's basically just a small bit of jQuery that grabs the list of the top 25 albums then asynchronously gets the selected track for each album updating the playlist as each track is selected.

The Legalize It! app, as demo'd at the Music Hack Day

If you'd like to install the App, here are some instructions for installation in developer mode.  I'll be cleaning up the UI to conform to Spotify's app guidelines and submitting the app to their App finder thing, but that will take a while.

Going Forward

While this is mostly complete for what it does there are a number of feature adds that I'll be slowly dealing with as time goes on. Highest among these is taking the same idea and applying it to different resolvers (maybe use tomahawk rather than picking one...). There are also some smaller feature adds to the app, things like autoplay once the first track has loaded and switching between different echonest summary features or musicmetric charts (eg. P2P release groups by acceleration).

Also, thanks very much to Spotify, who awarded me a prize for my hack!

So what do you think?  Should we care about the taste of a bunch of peers on Bittorrent? Or am I doing it wrong?

Viva passed, corrections approved, blog barely updated...

The last couple months have proven me to be a terrible blogger, as I haven't posted at all.

Anyway, that aside, I'm pleased to announce that I have passed my viva with minor corrections (back on march 2nd) and as of about an hour ago, had my submitted corrections approved, which means I'm totally done!

Hoorah!

So before I run off for a bit of celebratory drinking, I thought I'd post the soft copy in the the series of tubes (here's the full pdf) and here is a brief chapter-by-chapter summary:

• Chapter 1: Introduction. We present the set of problems this thesis will address, through a discussion of relevant contexts, including changing patterns in music consumption and listening. The core terms are defined. Constraints imposed on this work are laid out along with our aims. Finally, we provide this outline to expose the structure of the document itself.
• Chapter 2: Playlists and Program Direction. We survey the state of the art in playlist tools and playlist generation. A framework for types of playlists is presented. We then give a brief history of playlist creation. This is followed by a discussion of music similarity, the current state of the art and how playlist generation depends on music similarity. The re- mainder of the chapter covers a representative survey of all things playlist. This includes commercially available tools to make and manage playlists, research into playlist generation and analysis of playlists from a selection of available playlist generators. Having reviewed existing tools and gen- eration methods, we aim to demonstrate that a better understanding of song-to-song relationships than currently exists is a necessary underpin- ning for a robust playlist generation system, and this motivates much of the work in this thesis.
• Chapter 3: Multimodal Social Network Analysis. We present an exten- sive analysis of a sample of a social network of musicians. First we analyse the network sample using standard complex network techniques to verify that it has similar properties to other web-derived complex networks. We then compute content-based pairwise dissimilarity values using the musical data associated with the network sample, and the relationship between those content-based distances and distances from network the- ory are explored. Following this exploration, hybrid graphs and distance measures are constructed and used to examine the community structure of the artist network. We close the chapter by presenting the results of these investigations and consider the recommendation and discovery applications these hybrid measures improve.
• Chapter 4: Steerable Optimizing Self-Organized Radio. Using request radio shows as a base interactive model, we present the Steerable Opti- mizing Self-Organized Radio system as a prototypical music recommender system along side robust automatic playlist generation. This work builds directly on the hybrid models of similarity described in Chapter 3 through the creation of a web-based radio system that interacts with current lis- teners through the selection of periodic requests songs from a pool of nominees. We describe the interactive model behind the request system. The system itself is then described in detail. We detail the evaluation process, though note that the inability to rigorously compare playlists creates some difficulty for a complete study.
• Chapter 5: A Method to Describe and Compare Playlists. In this chapter we survey current means of evaluating playlists. We present a means of comparing playlists in a reduced dimensional space through the use of aggregated tag clouds and topic models. To evaluate the fitness of this measure, we perform prototypical retrieval tasks on playlists taken from radio station logs gathered from Radio Paradise and Yes.com, using tags from Last.fm with the result showing better than random performance when using the query playlist’s station as ground truth, while failing to do so when using time of day as ground truth. We then discuss possible applications for this measurement technique as well as ways it might be improved.
• Chapter 6: Conclusions. We discuss the findings of this thesis in their to- tality. After summarizing the conclusions we discuss possible future work and directions implied by these findings.

Enjoy!

(Also, if you find any deep hiding typos, I'd love to know about them. Not sending it to the printer/binder till Monday...)

woooo!

I finally submitted my phd thesis. I'll post some bits of it over the next few weeks, and the whole thing after my viva. To start, here's the abstract:

---

It is not hyperbole to note that a revolution has occurred in the way that we as a society distribute data and information. This revolution has come about through the confluence of Web-related technologies and the approaching- universal adoption of internet connectivity. Add to this mix the normalised use of lossy compression in digital music and the uptick in digital music download and streaming services; the result is an environment where nearly anyone can listen to nearly any piece of music nearly anywhere. This is in many respects the pinnacle in music access and availability. Yet, a listener is now faced with a dilemma of choice. Without being familiar with the ever-expanding millions of songs available, how does a listener know what to listen to? If a near-complete collection of recorded music is available what does one listen to next? While the world of music distribution underwent a revolution, the ubiquitous access and availability it created brought new problems in recommendation and discovery.

In this thesis, a solution to these problems of recommendation and discovery is presented. We begin with an introduction to the core concepts around the playlist (i.e. sequential ordering of musical works). Next, we examine the history of the playlist as a recommendation technique, starting from before the invention of audio recording and moving through to modern automatic methods. This leads to an awareness that the creation of suitable playlists requires a high degree of knowledge of the relation between songs in a collection (e.g. song similarity). To better inform our base of knowledge of the relationships between songs we explore the use of social network analysis in combination with content-based music information retrieval. In an effort to show the promise of this more complex relational space, a fully automatic interactive radio system is proposed, using audio-content and social network data as a backbone. The implementation of the system is detailed. The creation of this system presents another problem in the area of evaluation. To that end, a novel distance metric between playlists is specified and tested. This distance method is then applied as a mean of evaluation to our interactive radio system. We then conclude with a discussion of what has been shown and what future work remains.

Roomba Recon - A musichackday brain dump

So this past weekend I attended the 2nd (annual?) London Music Hackday at the Guardian's offices at King's Cross. For the hack I created an algorithm that generates playlists between arbitrary start and end songs on soundcloud. It does this with almost no pre-indexing, allowing for playlists to cover the entire network and always use an up-to-date graph. It's (mostly) running live if you'd like to play with it.

Briefly, it performs a sort of bastardized A* search, bilaterially from both the start and the end song to form the playlist. There's a parameter to limit the length of the two playlist segments, by default this is 4 so the max playlistlength is 10 (2*4+2 for the end points).

The search algorithm collects social links of the artist corresponding to the given song. For each of these connections (you know, 'friends' or in soundcloud jargon 'followings') a determination of the cost of adding that song is calculated in the following way (for the half built from the start song):

where is the cost to add song m to list after song n, is some measure of distance from song n to song m and is the same measure of distance from song m to song e. Song e is the end song for the whole playlist. So basically the idea is that the cost of moving to a node is a ratio of how far away it is from where you were to how far it is to where you're trying to get. The whole thing is reversed for the other half, so the cost function makes it cheap to move toward the start song. If you simply want to randomly traverse social links the cost can be set to an arbitrary equal value (I used 1) for all links.

This leaves the matter of distance.

Starting with what I know best, I decided to try a content-based distance first. I should say that from the onset I figured this would be insanely slow, but none the less, I gave it a go. I implemented (available directly as well) a little object that will grab the echonest timbre features for any two soundcloud songs, summarize the features into a single multidimensional gaussian (mean and std) then take the cosine distance between the two tracks (other distance metrics could be computed as well, but cosine seemed reasonable). That takes something on the order of 45 seconds to do for every pair of tracks. When using it in the above playlister the whole thing would take maybe 4 hours (I think, I never actually let it complete). Clearly way too slow.

So taking inspiration from my about to be published work at WOMRAD, I thought some NLP could save the day. So the other distance measure I implemented (no direct access yet) is based on a tracks tags and comments. First I tokenize the comments and combine them with the tags to create a vector space model of a track's descriptive text. I then weighted everything using tfidf (the idf was populated with a random sample of tracks from across soundcloud that I gathered over the weekend, about 41,000 tracks in total. This is the only indexing that is done in advance). From the tfidf weighted terms in a vector space, I took the cosine distance. This is both quite quick and gives pretty good results.

Everything was built in python, the app is running in cherrypy, using numpy and scipy for the data handling and gensim for the tfidf related bits. Soundcloud and echonest interaction is all via their respective python wrappers. Also there's a more terse write up over at the musichackday wiki. I'll stick the code on my repository on github once it's cleaned up a bit (though that might be a little while as I seem to be rather busy with something at the moment...)

Right. Back to writing my thesis.

A bit about playlists and similarity

Sorry about the general radio silence of late. Many things going on, most of them interesting.

Lately I've been spending quite a bit of time considering various aspects of playlist generation and how they all fit together. Here are some of my lines of thought:

1. Evaluation of a playlist. How? Along which dimension? (Good v. Bad, Appropriate v. Offensive, Interesting v. Boring)
2. How do people in various functions create playlists? How does this process and its output compare to common (or state of the art) methods employed in automatic playlist construction. This is to say, are we doing it right? Are the correct questions even being asked?
3. What is the relationship between notions of music similarity (or pairwise relationship in the generic) and playlist construction?

While all these ideas are interrelated, for now I'm going to pick at point (3) a bit. I'm coming to believe this is central in understanding the other two points as well, at least to an extent. There are many ways to consider how two songs are related. In music informatics this similarity is almost always content-based, even if it isn't content derived. This can include methods based on timbral or harmonic features or most tags or similar labels (though these sometimes get away from content descriptors). This paints some kind of picture but leaves out something that can be critical to manual playlist construct as it is commonly understood (e.g. in radio or the creation of a 'mixtape'), socio-cultural context. In order to have the widest array of possible playlist constructions, it is necessary to have as complete an understanding of the relationship between member songs (not just neighbors...). Put another way, the complexity of your playlist is maximally bound by the complexity of your similarity measure.

M<=Cs

Where M is some not yet existant measure of the possible semantic complexity of a playlist and s is a similar measure of the semantic complexity of the similarity measure used in the construction of that playlist. C is our fudge factor constant. Now, obviously there are plenty of situations where complex structure isn't required. But if the goal is to make playlists for a wide range of functions and settings, it will be required some times.

In practice what this means is that you can make a bag of songs from a bag of features. However, imparting long form structure is at a minimum dependant on a much more complex understanding of the relationships (eg. sim) between songs (say from social networks or radio logs...)

Anyway, this is all a bit vague right now. I'm working on some better formalization, we'll see how that goes. Anyone have any thoughts?

musichackday

So I spent the weekend holed up in the Guardian offices at the musichackday. I went in with some perhaps overly ambition plans to generate playlists across the SoundCloud user graph, with song selection optimization done with features via theechonest. This might have been barely possible if I had been working with a couple other people of similar background, but circumstances led to me hacking mostly solo at this particular event.

In the end I spent a substantial amount of time beating the SoundCloud python wrapper into being more helpful for what I wanted it to do (which is perhaps not what it's envisioned use was, but hey, that's what hacks are for), namely walking the user (artist) space and creating a Complex Network so I can move the playlist generation tools we've created around myspace crawls over to SoundCloud.

So, to that end, I've created some bits of python that walk through the user graph on the SoundCloud and build a graph using iGraph. This code base is living over at a new github repository I've created called pySomethingClever. Included over there are diff files documenting the changes I made to official SoundCloud-api-wrapper, which will enable any willing victims to grab and run the hacky bits of code I have up.

Once I got the api wrapper in a place where it could do a bit of what I wanted I fired off a crawl. I got through about 4,000 users (of a complete user network of about 170k nodes for ~2.3% of the network) in SoundCloud's network before the presentations started on Sunday. To clarify slightly, the network contains all the users of SoundCloud, but only the outlinks (users a given user follows) from 4,000 nodes. This is to say I had a (mostly) complete vertex list and a very incomplete edge list. With the super great help of kurtjx this sampled network was pushed through the lanet k-core decomposition visualization to draw out some of the community structure and related forms of the sample graph. Here's that graph:

The size of each node is tied to the number of links (either direction) touching that node. The color and placement have to do with how critical the node is to the rest of the network maintaining its current state of connectedness.

Since the hack I've continued gather edges toward a complete representation of SoundCloud. I currently have the out link edges from more than 17,000 SoundCloud users (about 10% of the user base) and should have a full capture in the next few days. Below you can see the same visualization with the edges from 16,000 users (the graph is set to write every 2k):

As the crawl continues, my guess is the middle bits will continue to fill in, which would be expected if the SoundCloud behaves in the usual Power Law fashion (as most of The Internet's networks, social or otherwise, tend to).

It should be noted that these visualizations, while very interesting, are just the beginning of what is possible once the whole user network is captured. I'm going to be building some playlist generators and recommenders around this in the coming weeks. If things look good (and from here I'm quite excited) I'll push some of it to the ISMIR late breaking demos and possibly to AdMIRe. More to come!

back to playlisting

After a brief tangent into the wide world of mixing (of which I'll post some more in a bit from my proposed SMC paper in a bit) I'm back into playlist generation and related topics.  Along those lines it occurs to me that readers of my little blog may be interested in perusing my recently completed (Dec 2008 actually) M.Phil to PhD upgrade document.  For those of you unfamiliar with the British PhD system, PhD students start as a Master's of Philosophy by research student, then after about 24 months of independent research go through a process of summarizing and defending their work so far and what they intend to accomplish in the coming 18 - 24 months.  The outcome of this process is one of three things:

1. Your work is deemed interesting, rigorous and sufficiently likely to succeed in the next couple of years.  As a result, you upgrade to a PhD student and continue on with your research (this is what happened in my case)
2. You graduate at that point with a M.Phil.
3. You completely fail your upgrade process.

So that happened back in mid december.  Here's the abstract from my upgrade:

A framework is described to consider various real world playlist use cases.  Automatic playlist generation is introduced as a means to improve music recommendation.  Literature in related topics is discussed.

A sample of the Myspace artist network is examined to investigate the relationship between social connectivity and audio-based similarity.  Audio data from the Myspace artist pages is analyzed using well-established signal-based music information retrieval techniques.  In addition to showing that the Myspace artist network exhibits many of the properties common to social networks, it is seen that there is an ambiguous relationship between audio-based similarity and the social connectivity. Further the Myspace sample is examined with the pairwise relational connectivity measure Minimum cut/Maximum flow.  These values are then compared to a pairwise acoustic Earth Mover's Distance measure and the relationship is discussed.  A means of constructing playlists using the maximum flow value to exploit both the social and acoustic distances is realized.

Two playlist generation methods are proposed for development and experimentation.  The first is a direct extension of the myspace dataset analysis into a robust playlist system for interactive internet radio broadcast.  The second is content based system which uses expert constructed playlists to construct transition models which can then be used on new material.  This is followed by a discussion of evaluation needs and strategies. 

 If you're interested in reading the whole thing (comments welcome and encouraged) download the pdf.

On an unrelated note, I'll be a Yahoo Open Hackday 09 in Covent Garden in a couple weekends.  It's free and I believe there are still some tickets if anyone is interested.  It should be rad.