1

I have a Pandora-like piece of software where the user can thumb up a song or thumb down a song. The software, called Chavah, is Silverlight + C#, but this is a language- and platform-neutral question.

My software needs to choose a song based on the user's preferences. I need a good algorithm for this.

I want my software to choose a song to play given the following requirements:

  1. Thumbed up songs should be favored, and played regularly.

  2. Unrated songs (neither thumbed up nor down) should still be played; after all, the user may only have 2 total thumbed up songs.

  3. Thumbed down songs should be played rarely.

  4. Whatever the algorithm, songs should not repeat often.

Given these design decisions, is there some good algorithm here?

I have some code that grabs all songs, liked songs, and disliked songs:

var allSongs = ...
var likedSongs = allSongs.Where(s => s.LikedByUser(...));
var dislikedSongs = allSongs.Where(s => s.DislikedByUser(...));

Any simple ideas for picking a good song for the user?

3
  • Other users' preferences are not taken into account at all, correct?
    – grossvogel
    Jul 27, 2010 at 16:37
  • just for clarification... this is C#? Jul 27, 2010 at 16:37
  • Yes to both: other users' preferences are irrelevant, and yes, this C# + Silverlight. You can see the project live at: bit.ly/chavah Jul 27, 2010 at 17:09

4 Answers 4

2

You can weight songs; say every song has a score of 1.0 in the beginning, 0.5 if thumbed down and 1.5 if thumbed up. Then you pick a random element from the set of all scores, with its probability however weighed by its, um, weight. The fast and dirty approach I'd think of here would be to sum over all weights. Pick a random number smaller than that sum. Loop over all songs until CurrentWeight+SongWeight > RandomNumber (else CurrentWeight+=SongWeight)

Of course you can make this arbitrarily more complex by introducing collaborative filtering :)

Imagine five songs. First two thumbed up, next one thumbed down, two neutral.

{1: 1.5, 2: 1.5, 3:0.5, 4: 1, 5:1}

The sum of this is 5.5. Now we pick a random number < 5.5 and see: It's 2.43789

Now let's find the song this random number belongs to.

Start with CurrentWeight = 0. First song's weight = 1.5. CurrentWeight+1.5 < 2.43789 -> we continue, but increase CurrentWeight by this song's weight.

So CurrentWeight = 1.5 now. Next song's weight: again 1.5. But now, CurrentWeight+1.5 == 3 > 2.43789. This means we chose the second song!

What you do here is to basically pick a random spot on a line, but increase the "territory" on that line that would choose a song if the song is thumbed up.

Whether this creates many repetitions or not basically depends on how strongly you increase/decrease the songs' weights.

8
  • I'm not sure I understand. Could you provide a small sample that shows the concept? I got lost towards the end. Jul 27, 2010 at 16:47
  • One question: will this method introduce many repeats if there are only a few (say, 5) liked songs? Jul 27, 2010 at 16:48
  • 1
    I extended my answer by an example, hope this helps
    – Nicolas78
    Jul 27, 2010 at 16:58
  • 1
    cool :) well I've been thinking a bit, and something I don't like about my approach is that it's comparatively slow, forcing you to loop over, in average sumOfWeights/2 songs for each choice. If you can live with even-numbered ratios between the weights, you could also just put the songs into a list and choose a single one - just put the unthumbed ones twice (for example), the upthumbed three times and the downthumbed once (this would result in the same distribution as in the example above, you're just not quite as flexible if you'd want to change those weights)
    – Nicolas78
    Jul 28, 2010 at 9:47
  • 1
    I think you could employ a Fenwick Tree to implement the lookup faster. Dec 6, 2011 at 18:14
1

i assume that Pandora uses a tagging system to categorize their songs. In this way, you devlop a profile of a user's musical tastes by sampling the highest frequency of tags "thumbed up". Unfortunately for you, they draw from a vast database of tagged music to offer their users, which is probably harder to develop than the algorithm to pick them.

1
  • Yeah, I'm not interested in basing my choices off of the type of music, like Pandora does with tagging. I'm looking for a simpler method of "mostly liked songs, some unrated, few unliked, with few repeats". Jul 27, 2010 at 16:45
1

You could also create a rating system for the band/singer and genre, and based on each "thumb up", you could add 1 (or whatever value you decide) to both the band/singer and the genre. Then, when it's time to decide the next song to play, you can weight the decision based on said user's interest in a band/singer and/or genre. And the reverse for "thumbed down" songs.

1
  • Yes, I plan on that, but later on down the road. For now, I want to use just the thumb up/down on a single song to base my decision. Jul 27, 2010 at 16:45
1

Maybe something like this:

1) Create three streams (or playlists) of randomly-ordered songs like your code snippet, but make them mutually-exclusive: Liked, Not Liked, Not Rated. Based on the size of these groups, they'll each have a duration before they repeat.

2) Create a function that merges the streams into a single stream, while obeying certain rules. The main rule would be the desired mix of the streams, say 60% liked, 38% not rated, 2% disliked, or whatever. You'd have to deviated from the desired mix only when the duration of the Liked stream is too short to follow the 'minimum time between song repetition' rule.

3) You probably also want to periodically re-calculate all of the streams. The tricky part here might be to avoid repetitions caused by the recalculation. Maybe your random sort in (1) could also take into account some kind of weight or offset attached to recently-played songs.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.