The MegsRadio Playlist Algorithm

Google+ Pinterest LinkedIn Tumblr +

Hey everyone! My name is Danny, I’m a junior from Ithaca College working on the algorithm for MegsRadio that picks what song to play for you next, and I thought I would give you a quick summary of how it all works. If you have any questions or comments, please comment below!

-Danny

 

LittleWing

Summary

The current playlist algorithm being used by MegsRadio, known as LittleWing Gamma, is a perceptron learning algorithm utilizing 981 unique binary features. When a user requests a new track for a given station, which is defined by a set of influences––tracks, artists, or tags that a user has specified as a seed or given a “thumbs up” or “thumbs down” preference––and a set of settings––options such as tempo, how much local music to include, and how often to allow repeats––the algorithm initiates a multi-step process which aggregates a set of candidate tracks, sorts the set based on the 981 binary features, prunes the list to fit our restrictions, promotes tracks that fit specified criteria, demotes tracks that fit specified criteria, and samples the sorted set of candidates.

Candidate Aggregation

The very first step of the algorithm is to aggregate a set of potential tracks to play for a user’s station. To do this, we utilize a pre-computed score index that holds scores for connections between artists, tracks, and tags. During this step, each of the station influences are iterated through. Any track that has a connection to any of the station influences and fits the station settings is included in the set of candidates. Any track whose artist has a connection to the station influences and fits the station settings is also included.

Candidate Feature Expansion, Scoring and Sorting

After the candidate tracks are aggregated, they must be sorted into a ranked list. To begin this process, the binary features for each candidate must be set. These features include connections such as artist locality to the user, if a track or artist is a station seed, and also how strongly a track ranks for a certain type of connection for a specific data source.

After the binary features are all set, all candidates are given a score. This score is the linear combination of the binary features and the weight vector. The weight vector is a vector full of the weights learned by the algorithm. These weights can be considered “trust values”––if a binary feature has proven to be very accurate in predicting a good track it will have a high weight, and if it has proven inaccurate, its weight will be relatively low. The candidates are then sorted based on their scores: the higher the score, the earlier it appears in the list.

Candidate Pruning

As a music streaming service, MegsRadio is held to certain restrictions by the Digital Millennium Copyright Act (DMCA). For example, we can repeat an artist no more than four times in a row and no more than five times in three hours. It is in this step that we remove, or prune, all tracks that break any DMCA rule.

This step also includes the pruning of tracks that do not fit a user’s repeat preferences. Users have the ability to specify whether to allow a track to be repeated after 4 hours, 8 hours, or 12 hours. If a track has been played within this time period, it will be removed from the list.

Candidate Promotion

The algorithm next promotes tracks that fit certain criteria. In this iteration of the algorithm, the only tracks we promote are tracks whose artists are local to the user. All local tracks are promoted proportional to 2n where n is the number of tracks played since the last local track played. We do this because our goal at MegsRadio is to introduce our listeners to local musicians. Locality is determined using a precomputed index connecting every artist to any region which they are from.

Candidate Demotion

LittleWing Gamma also has functionality built-in to demote any tracks that fit certain criteria similar to the promoter, but we do not currently utilize demotion. For example, we might demote tracks for which we have a low maximum bit rate (e.g., 64 Mbps) so that we play more higher quality audio tracks.

Candidate Sampling

The final step of the algorithm is to sample from the sorted, pruned, promoted, and demoted list of candidates. LittleWing Gamma utilizes a Zipf Sampler, which samples the list using Zipf’s Law. Zipf Samplers strongly favor indices in the list closest to 0 (the track with the highest score), but have the potential to select any candidate.

User Feedback and Parameter Learning with Gradient Descent

Every time a track plays on MegsRadio, we give the user the option of rating that track with a “thumbs up” or a “thumbs down.” A thumbs up suggests that the track was a good suggestion and a thumbs down suggests that the track was a bad suggestion.  This feedback is how the algorithm learns the weights used in the sorting process. When a user thumbs up a track, the weights of features which were accurately “turned on” are increased, and there is no penalty for a feature being “turned off.” When a user thumbs down a track, the weights of features which were inaccurately “turned on” are decreased, and there is no reward for a feature being “turned off.” It is possible for a weight to become negative. To increase efficiency, LittleWing uses a mini-batch system for weight updates. In its current state, the weights used by the algorithm are updated after every 100 pieces of feedback.

 

Share.

About Author

Chief playlist creator and all-around fixer of difficult things.

Leave A Reply