Friday, August 8, 2008

Introducing: Fuzzy Biases

Suppose you're really into music created around the "summer of love" in 1967. Its easy enough it create a filter so you only get music from 1967. We could do that in Amarok 1, but that excludes a lot of music around that period that's just as significant.

Maybe you could do something like asking for everything that's recorded after 1960 but before 1973. That's better, but it's still not really what you mean when you say around 1967. You would prefer tracks closer to 1967 than farther away.

This is where "fuzzy biases" come in. The goal with fuzzy biases, is create a playlists that approximately match a value. Generating biased playlists, is always a question of probability distributions. What we are really trying to do here is generate a playlist that fits normal distribution bell-curve.

Like this:

The horizontal axis is the year, the vertical axis is the probability of getting track of that particular. So the nearer to 1967 the track is, the better chance of it ending up in our playlist it has.

Ok, another example.

I really just want to listen to some good straight up pop right now. No eleven minute epic folk ballads, no classical, no post-rock, just tight catchy songs. So I make a fuzzy bias to find songs that are about three minutes long.

Great. That's a pretty good mix, and I can refine it later with other biases.

The fairly vague "Strictness" slider indirectly controls the standard deviation of of the distribution.

It looks a little like this:

How is this different than the old fashion method, just specifying a pair of strict biases?

To get all mathematical on you, that creates a playlist that matches a uniform distribution.

If you've never taken a statistics class and didn't follow any of this, let me summarize:

  1. pretty curves > boring rectangles.
  2. Apparently a math degree is actually good for something.
  3. Mom, you owe me an apology.

Saturday, July 26, 2008

GSoC Update

It's been a pretty laid back week or two for me. Google paid up, and I bought myself a microKorg (to compliment my circuit-bent Casio Sk-1), and I don't have buy my potatoes on credit anymore, which feels good, but a little un-American.

I spent most of these couple weeks just wandering the code, putting an end to bugs that stumbled across my path, but there are couple noteworthy items.

First, I have saving playlists more or less working. Which was something I was putting off writing, because it was a hassle, and not the kind of hassle I find very interesting.

The other good news is that the solver is about to become much much faster. I switched from hash table sets (QSet) to bit array sets, which are much better suited for the obscene number of intersect and subtract operations I have to do. The result is the solver should be nearly instantaneous. No more 20 second waits when you put in a bunch of biases.

I have a pretty expansive todo list, but I'm eager to implement some new types of biases to see what the solver can really do. I've gotten some good suggestions for biases that hadn't occurred to me. Let me know if you have an idea for one, and I may write it up.

Tuesday, July 15, 2008

Roll Video

I always loved in grade school when the teacher was too depressed or hung-over to teach the class and just put on a VHS of Raiders of the Lost Ark, or something.

As promised, I made a little demonstration for those not daring enough for the svn or nightly (you can admit it, we won't think less of you).

(thats:, for the embeded video challenged.)

Sorry about the pixelation, it's hard to make out how ridiculously hip my music collection is.

It's still a little slow for a lot a biases. Expecially on my aging thinkpad, while trying to record video. That's something I will be working on. The algorithm is gradually growing faster and more complicated. I suppose that's how that works sometimes.

For next week, I hope to get saving and loading ironed out, as well as putting more work into the solver. After that I have the much more interesting task of writing news types of biases and making sure they don't take forever to solve. I've already got a lot of interesting suggestions which hadn't occurred to me. It's going to be fun to see what this can really do.

Monday, July 7, 2008

Weekly Update: Unhidden Biases

Now that dynamic playlists are working, what's missing is a way to actually use them. That's what most of this weeks work went towards.

In Amarok 1, dynamic playlists are one of those great hidden features. They are terrifically powerful and usefull, but a lot casual users don't know about them, or just don't understand how to use them. I had been using Amarok for a while before I discovered them.

One of the problems I've been working on is how to present Amarok 2.0 dynamic playlists in a way in which it's more or less obvious what they do. I want it to be an exhibitionist feature, with the functionality all exposed and out in the open, no dialog boxes or menu hierarchies.

This week I spent some quality time working on the bias editor (and reminding myself why I don't like gui programming). Since every blog post needs a picture, here's the latest version of the bias editor from just a few minutes ago (not even in svn yet). It's a bit rough arround the edges, but comming along nicely. 

That screenshot is slightly faked, but in the next few days the bias editor will start to become functional. I'm pretty excited to see my work actually usable. 

I also did some important work behind the scenes. This sort of playlist generation can't really be done efficiently in general (it's an NP-hard problem). If you give it a really tough set of biases, it won't break down or freeze up, but it may give you playlist that isn't perfect. Making the solver work well is a matter of heuristics, trial and error, and tweaking. I did a little of that this week, but the real testing and tweaking will happen when the bias editor is up and running.

I'll be back here in a week, hopefully demonstrating how to use the new dynamic playlists.

Monday, June 30, 2008

Weekly Update, Secret Plans Divulged, &c

I've been struggling with how to describe what I've been working on succinctly in conversation. I figure I can get about two sentences in before I start getting blank stares and eye rolls. I've been using something like this:

You know how when you put your ipod on shuffle, it magically knows what you want to listen to next? It's a little like that, but completely customizable, and instead of magic it uses a stochastic optimization algorithm.

Then they say something like "Hmm", or "Interesting," and then there's a long uncomfortable silence until someone changes the subject. "Can you believe this weather we're having?"

This is Week 2 or so for me, and forgoing things like "sleep" and "food", I've made some significant progress. The core of the bias code is written and more or less works. Random mode in working just dandy and if you're running the nightly or svn of Amarok 2, you can find it under the Playlists tab hiding out at the bottom.

Since the bias code is written and works, this is a good time to talk about my secret plan.

When a I first proposed biased playlists, I described biases as the chance that track has a certain property. Like "30% chance the next track is Jazz". I even made an aesthetically appalling mockup to show what I meant:

The secret is, that I've designed it to be much more general than that. A bias is any function that maps a playlist to a value in [0,1]. The solver will then try to find a playlist where all the biases are at 0.

Blank stares, eye rolls. "Can you believe this weather we're having?"

The point is: biases can do a lot more that what I described previously. Really, they can impose any kind of restriction on the random playlist being generated. For instance, Suggestion Mode, where the next track is from a similar artist as the previous, can be implemented as a bias. If Suggestion Mode is just a bias, it can be combined with other biases.

We could do Suggestion Mode + 30% Metal + 70% pre-1990, and it will do its best to find a playlist that matches fits. It there is no such playlist, it will just give you the best it can come up with.

This also really important because it lets us use fuzzy biases like: "arround 1976", "about 3 minutes", or "hasn't been played in a while".

Presumably, users could script their own biases, doing wacky things so playlists are random but tracks have increasing lengths, follow an obscure integer sequence, or their titles spell out a secret message.

The next few weeks i will mostly be concentrated on tweaking and optimizing the solver and working on an easy way to create biased playlists. There's a lot of work ahead, but I'm very excited with how it's gone so far.