tillerinobot
patreon
How do recommendations work?
🕑 Added 2020-08-28 14:49:56 +0000 UTCThere are a couple of questions which I get asked a lot: Can I get a mutual? Can you ask yourself for recommendations? OMG a bot can play osu!? Are you actually peppy? (the latter ones usually come up when I’m playing on the Tillerino account).
There is this quote which I can’t cite correctly, but it goes a little something like this: “Point out a single person and I won’t have any idea what they’ll do. Show me a crowd and I’ll tell you exactly what they’ll do.” It’s about the fact that once crowds get large enough, the individual apparent randomness disappears into statistical effects.
This is one of the (many) aspects which I imagine to suck about being famous. Every person that you meet thinks of something clever to say or deems themself the biggest fan, but from your perspective, they all turn into one large statistical blob. Every fan is the biggest fan. Every clever line is just one sample from a statistical distribution of clever lines which are generated based not on your person, but on your role to the public. Just imagine the isolation…
One question that also comes up now and then is: how do recommendations even work? Actually, more often than the question itself, I encounter misconceptions about how Tillerinobot recommendations specifically work. So I thought, I’d clear up the basic principle without getting too technical.
How they don’t work
There are a bunch of very simple methods how you could generate recommendations. First idea: star difficulty. What’s the average star difficulty of your top plays? Just play other maps with that star difficulty! Done. Well, no. The problem is that difficulty in osu! doesn’t just have a single dimension.
You probably have heard of the general terms “jump map” or “stream map” and this is difficulty in a nutshell. There are many more words to describe things that can be difficult: “stream spacing”, “strain”, “square jumps”, and more. Right, so then let’s adjust for that, shall we? Just include the average BPM and map length or something. That’ll balance out some of the difficulty aspects and we’ll get good recommendations.
Honestly, I haven’t pursued this path any further in the past, but I expect that this wouldn’t really work. High BPM doesn’t really equate to a fast or streamy map. Long maps can be relatively strain-free if they include well-placed breaks. Just looking at the meta-data will at most give hints at the actual difficulty of a map. However…
How they could have worked
Back when I implemented the first version of recommendations, osu! still looked a bit different. ppv2 hadn’t been around for long. That’s right kids, this is v2 of the pp system. v1 basically ignored actual difficulty and before pp, people were just ranked by total score. Looking back, that seems just insane, but like most things, pp needed some time to develop.
Nowadays, the ppv2 system, which is based on tp, works by quantifying the difficulty of beatmaps. It all boils down to an “aim” and a “speed” parameter in the end, but the underlying implementation involves more granular properties. oppai is an open-source implementation of the system. With koohii, there is even a Java-port available.
I imagine that one could build a recommendation system based on the more granular properties involved in the ppv2 calculations which would yield fairly good results. One benefit is that it would be very efficient to generate recommendations since there is very little data involved and a lot can be precomputed. Hold on, some hundred thousand beatmaps is little data? Yes, yes it is. We’re gonna be in a different ball park soon.
If I were to build a recommendation system right now, I would probably try this approach first. Although I can imagine limitations, it seems simple, efficient, and robust against some problems that the current system unfortunately has.
How they actually work
Shift your attention from beatmap recommendations to recommendations on Amazon, Netflix, or Spotify. The first realization that will hit you is how completely insane the meta-data approach is. Imagine recommending movies based on the average length of the movies that you have watched. Imagine recommending items based on the average price of your past purchases or based on color. Even recommending movies based on IMDB rating is pretty useless. Of course using meta-data isn’t always absurd. Recommending songs by an artist that you listen to frequently will probably work quite well. Recommending movies by a director whose movies you have watched is probably also an approach that has very solid performance measured by the effort that you need to put in. But obviously, you will need more than meta-data.
What makes movie and music recommendations good is figuring out the taste of the user. This is where things get interesting… if you like math and stuff. I won’t go into any detail here. If you are generally interested in this, this text is brought to you by Skillsh... Just kidding. If you are generally interested in this, take a look at these two Wikipedia articles: Cluster Analysis and PCA. I want to stress that this is not how recommendations on those big sites work. These two articles barely scratch the surface of an entire field of science which is in part driven by these companies. But maybe these articles will inspire you to learn more.
What we’re venturing into now is the field of machine learning. Machine learning, in general, is the opposite of writing algorithms. An algorithm is a fixed set of instructions that you perform on any input. A common (although vague) example of an algorithm is a cooking recipe: Take this ingredient, put it in the pan, stir, let it sit, and so on.
I don’t like this example, because it still depends on your varying interpretation of the instructions (how much is a “cup” supposed to be) and unfortunately has no varying input. A better example might be Dijkstra's Algorithm for finding shortest paths in a network. A good indicator for it being a good algorithm is the fact that you can prove that it always finds the shortest path, whereas you will find it hard to prove that anything remotely edible will come out when you follow that weird muffin recipe that you found on YouTube.
The thing about algorithms is that they’re precise. Taste is not precise. Taste is fluid and statistical. How you figure out taste is by giving a machine a blank statistical model and millions of observations from the real world and have the machine tweak (or “learn”) the model until it matches what you see in the real world.
Forgive me a little side-rant here. You have probably heard the terms “Youtube algorithm”, “Google algorithm”, or more recently “TikTok algorithm” when they’re talking about how certain websites generate recommendations or rank search results. Underlying these is usually a statistical model which has been learned. Do you remember how I said that machine learning is the opposite of an algorithm? How an algorithm is precise and predictable to the point that properties about it can be proven? How people are complaining that these “algorithms” are unpredictable? Can you see how they should not be called algorithms? Get your heck together, world. Also: Machine learning is not AI. Stop calling it that. REEEEEEE
How they actually work, really
I think you know where this is going. Tillerinobot’s recommendations are learned by observing the top scores of millions of players. The best analogy in my opinion are the recommendations on Amazon. Based on what you have bought, what could you also want to buy? How could Amazon probably become good at making those recommendations? Only by looking at what other people who bought the same items as you, also bought.
In a nutshell, that’s what it is: Tillerinobot looks at other people who have similar top scores and recommends maps that they have played which you haven’t played.
Of course, that is far from the whole truth. One general question is: how do you make this efficient? Crawling through all the data only when a recommendation is requested will be to slow. You will probably want to precompute some parts of the model. For the interested, I’ll leave two more Wikipedia links here: Stochastic Matrix and Reinforcement Learning.
Again, this is not exactly how it works. There are several kinks which need to be worked out as well which relate directly to osu! plays. Most importantly: what is a beatmap? It is fairly obvious that mods can be treated as turning a beatmap into a new beatmap. But what about pp? How similar are two plays which completed the same beatmap with vastly different accuracies? If these are the top plays of both players, should they really be considered when generating recommendations for each other.
Outside the nutshell, the recommendations are more messy than the description above implies. I’ve been able to iron out some kinks over the last years, but am still working on others.
Some related answers
So one question that I also get asked a lot is: I haven’t played in ages and I can’t even beat the maps in my top scores let alone with descent accuracy. Can I somehow get easier recommendations?
Well, the answer is mostly no. Since the recommendations are based on your top plays, there is little that can be done. A small effect could be reaped from basing the recommendations just on the lower-rated ones of your top plays, but this is quite limited. For strongly varying the difficulty within your play-style, a different recommendation approach would have to be chosen.
What does “future you” mean? Well, now that we’ve already gone into statistics, we can easily answer this: it’s the statistical expectation for your score. Cool, right? While this is of doubtful meaning, I like it as an indicator for the accuracy that the player should shoot for. As I said before: a beatmap with high accuracy can feel like a different map.
What about other modes? As we’ve covered, the model underlying the recommendations requires data to be learned. Getting data for the standard mode is easy, since almost every player plays standard. This means that I can basically pick a number at random, pull the top scores for that player and there will be something useful. The same goes for maintaining the top scores.
For the other modes, this is not as easy. Pick a number at random and pull that user’s Taiko scores. There’s a good chance that there are no scores at all or that they consist of only a couple of completely unrelated plays which reflect more which beatmaps the player has rather than what they are capable of playing. In this case, there is little information to be learned. In theory, the same approach would work just fine for the other modes, but I simply don’t have the data and I don’t have a good way of getting it.
Conclusion
Weirdly-bent statistics and machine learning.
Also read the first couple of paragraphs again. Cool foreshadowing, right?
And thanks again to our sponsor Skillsh... No. No! Stop that. Whoa, I need to watch less YouTube. But their model (see? not "algorithm") is just so good and keeps me hella engaged. I think it would be hard to use the term "YouTube model", because people would just expect a skinny, tall person with a play button tattooed onto their forehead instead of... you know, mathematics. I think I'm going to start saying "YouTube logarithm" just to mess with people.
