birdland

README

Birdland is a famous Jazz club. It is also a recommendation library.

Birdland is a collaborative filtering algorithm in two steps: exploration and recommendation. To explore possibilities the algorithm performs a random walk on the (biaised) user-items bipartite graph starting from a list of items provided as an input. This random walk generates a list of (user, item) pairs that are processed by the recommender which returns a list of recommended items.

Birdland has some advantages over other collaborative filtering algorithms:

• It requires no pretraining.
  Most collaborative algorithm come with hidden costs. Not only do you need to maintain an extra service and database, you also need to solve an additional problem: find the N nearest neighbors of a vector (spoiler: it is not an easy problem).
• It is fast.
  We achieved performance of the order of the millisecond on an API serving recommendation of millions of items for a million users.
• It is simple to reason about, thus to customize.
  To build Bird we started from the simple question: how would I look for new music to listen? Back in the LastFM days I would look for users who had listened to similar artists, what they've listened to etc. and trust more users who had very similar tastes. Bird does exactly that, but a million times faster than you would. There is something you do not like about this story? Well, you can adapt Bird, or use Emu.
• It generalizes to a social recommender.
  Weaver uses the social network between users to inform recommendations.
• It recommends both items and users in one pass. No need to find the N nearest neighbors again.
• It solves the long-tail problem for a specific set of parameters.
  (Blog post to come) Now, whether this is desirable or not is another debate.
• It is ready for production.
  Birdland has been tested succesfully in production. Import birdland in the service that implements the recommendation API, plug in the data and you're all set.

The codebase is organized around the following components:

samplers

• tower_sampler.go implements the tower sampling algorithm to sample from a discrete distribution;
• alias_sampler.go implements the alias sampling algorithm to sample from a discrete distribution.

explorers

• bird.go implements a simple recommender engine based on a user-item graph;
• emu.go is a recommender engine based on a user-item weighted graph;
• weaver.go is a recommender engine based on the user-item bipartite graph and the user-user social graph.

recommenders

• recommend.go contains the functions used to produce recommendations from the engines.

Engines

Bird

Named after Charlie "Bird" Parker.

The very first step is to map the users and items to sets of consecutive integers (starting with 0). This avoids working with maps, which substantially improves performance.

Initialize the engine with a list of item weights, and the (user, item) adjacency table:

package main
import "github.com/rlouf/birdland"

artistWeights := make([]float64, numArtists) // global weight attributed to each artist
usersToArtists := make([][]int, numUsers) // for each user the list of artists they listened to (liked, followed, etc.)
cfg := NewBirdCfg()

bird, err := birdland.NewBird(cfg, artistWeights, usersToArtists)

This needs to be done only once (provided your data do not change). The engine processes queries---lists of (artist_id, weight) pairs---and outputs a list of artists and their referrers:

query := []QueryItem{} // QueryItem{Item int, Weight float64}
items, referrers, err := bird.Process(query)

We can then use items and referrers to recommend either artists or referrers (see the "Recommenders" section below). All engines depend on two parameters:

• the depth of the random walk;
• the number of random walks that are performed (number of samples drawn from the query).

they can be tuned by initializing the configuration passed to NewBird by hand:

cfg = BirdCfg{Depth: 2, Draws: 10000}

Emu

The emu is a heavy bird (the 5th heaviest).

Emu works very similarly to Bird. The only difference lies in the initialization; instead of taking a simple bipartite graph [][]int as an input, Emu takes a weighted bipartite graph []map[int]float64. In the context of music recommendation, the weight can for instance be the number of times the user played tracks from an artist.

package main
import "github.com/rlouf/birdland"

artistWeights := make([]float64, numArtists)
usersToWeightedArtists := make([]map[int]float64, numUsers)
cfg := NewBirdCfg() // Default of 1000 draws and depth 1

emu, err := birdland.NewEmu(cfg, artistWeights, usersToWeightedArtists)

Everything else is exactly the same.

Weaver (cleaning)

Weavers are allegedly very sociable birds.

The same way Emu attributes different weighs to each item, Weaver attributes different weights to each user. This follows from the idea that you would not weigh recommendations by strangers and by acquaintances the same way.

package main
import "github.com/rlouf/birdland"

cfg := NewWeaverCfg()
itemWeights := make([]float64, numItems)
usersToItems := make([][]int, numUsers)

weaver, err := birdland.NewWeaver(cfg, itemWeights, usersToItems, socialGraph) 

We give to users who are not connected to the current user a default weight of 1. This default behavior can be changed by initializing the configuration by hand:

cfg := WeaverCfg{DefaultWeight: 0, BirdCfg: NewBirdCfg()}

which would only consider recommendations coming from direct connections.

Recommenders

Since the engines traverse both users and items, we can recommend one or the other (or both) indifferently within the same query. Birdland provides several functions to produce recommendations from the engines' outputs.

Two functions were defined to provide a stable interface for the services that use Birdland and so strategies could be swapped without affecting said services. You can consult recommend.go to see the available strategies.

recommendedArtists := birdland.RecommendItems(items, referrers)

Produces an ordered []int that contains the id of the recommended artists.

recommendedUsers := birdland.RecommendUsers(items, referrers)

Produces an ordered []int that contains the id of the recommended users.

Contribute

Questions, Issues or PRs are very welcome! Please read the CONTRIBUTING.md file first, then happy forking.

Credits

The icon was made by Freepik from www.flaticon.com is licensed by CC 3.0 BY

Documentation

Overview

Package birdland provides algorithms to recommend music. It is also the name of a legendary Jazz Club.

Bird

Most recommenders are based on collaborative filtering. Traditionally, algorithms compute a factorization of the user-item matrix into low-dimension, latent vectors for items and users. Recommendations are based on a proximity measure between these vectors.

Bird (from Charlie "Bird" Parker) is a recommendation algorithm that is based on random walks on the user-item graph. It relies on a (currently unweighted) user-item graph which represents interactions of any kind between each user and some of the items, and on a list of item weights. To initialize Bird with sensible defaults, you can write:

charlie, err := NewBird(NewBirdCfg(), itemWeights, usersToItems) if err !=
nil { log.Errorf("failed to initialize Bird") }

Bird draws `Draws` items from the input query which are starting points for random walks of depth `Depth`. It is possible to specify the values of these variables with

cfg := NewBirdCfg() cfg.Draws = 10000 cfg.Depth = 5

charlie := NewBird(cfg, itemWeights, usersToItems) if err != nil {
log.Errorf("failed to initialize Bird") }

Once Bird initialized you can process a query (a slice of `QueryItem`) with

visitedItems, referrers, err := charlie.Process(query)

the visitedItems and referrers are then used to produce recommendations. Note that Bird does not support empty queries.

It is possible (although not desirable) that an item in the query refers to an item no one has interacted with. We ignore said item for the rest of the calculations.

Use cases are recommendations based on a item/container bipartite graph. For instance: - Recommend new artists/songs based on user-item relationships; - Recommend users based on the same data; - Recommend new songs for a playlist/radio; - Recommend playlists/radio

Emu

The emu is the heaviest bird there is out there. Although Bird is very efficient, it considers that all user-item interactions are created equal. However, users are likely to listen to certain artists more. Liking songs from an artist once is more meaningful than listening to one of their songs once. It is important to take these differences into account in the recommender.

The only difference between Emu and Bird is that Emu relies on a weighted user-item graph. Typically, the weights will be a combination of the number of plays, of shares, and likes. We still need to input a global list of weights for the items. To initialize Emu with sensible defaults you can write:

mingus, err := NewEmu(NewBirdCfg(), itemWeights, usersToItems) if err !=
nil { log.Errorf("failed to initialize Bird") }

where `usersToItems` is now of type `[]map[int]float64`. `mingus` is now of type `*Bird`. The only technical difference between Bird and Emu in the code is the way we initialize samplers for each users; Bird and Emu share everything else.

Index

• func RecommendConsensus(items, referrers []int) []int
• func RecommendItems(items, referrers []int) []int
• func RecommendMostVisited(items []int) []int
• func RecommendTrust(items, referrers []int) []int
• func RecommendUsers(items, referrers []int) []int
• type Bird
  • func NewBird(cfg *BirdCfg, itemWeights []float64, usersToItems [][]int) (*Bird, error)
  • func NewEmu(cfg *BirdCfg, itemWeights []float64, usersToWeightedItems []map[int]float64) (*Bird, error)
  • func (b *Bird) Process(query []QueryItem) ([]int, []int, error)
• type BirdCfg
  • func NewBirdCfg() *BirdCfg
• type Pair
• type PairList
  • func (p PairList) Len() int
  • func (p PairList) Less(i, j int) bool
  • func (p PairList) Swap(i, j int)
• type QueryItem
• type Weaver
  • func NewWeaver(cfg *WeaverCfg, itemWeights []float64, usersToItems [][]int, ...) (*Weaver, error)
  • func (b *Weaver) Process(query []QueryItem, user int) ([]int, []int, error)
• type WeaverCfg
  • func NewWeaverCfg() *WeaverCfg

Functions

func RecommendConsensus

func RecommendConsensus(items, referrers []int) []int

RecommendConsensus recommends the item by descending order of the number of unique referrers. With the data currently available, it is only possible to recommend items this way.

func RecommendItems

func RecommendItems(items, referrers []int) []int

RecommendItems and RecommendUsers contain the current methods that should be used to recommend items and users in production. Used as an interface so backend developpers do not need to worry about the zoology of recommending methods.

func RecommendMostVisited

func RecommendMostVisited(items []int) []int

RecommendMostVisited recommends the items in descending order of the number of visits by the processing algorithm. It is a very naive approach and probably should not be used in production. Works indifferently to recommend users or items.

func RecommendTrust

func RecommendTrust(items, referrers []int) []int

RecommendTrust recommends items based on how much we can trust their referrers. The algorithm begins with attributing a weight to the refferers proportional to the number of times it traversed them. The tracks are recommended by descending order of the cumulated weights.

func RecommendUsers

func RecommendUsers(items, referrers []int) []int

Types

type Bird

type Bird struct {
	Cfg               *BirdCfg
	ItemWeights       []float64              // global weight attributed to items
	UsersToItems      [][]int                // user-item adjacency matrix
	ItemsToUsers      [][]int                // item-user adjacency matrix
	UserItemsSamplers []sampler.AliasSampler // samplers to randomly draw items from a user's collection
	RandSource        *rand.Rand
}

Bird is a recommendation engine that performs random walks on the user-item bipartite graph.

func NewBird

func NewBird(cfg *BirdCfg, itemWeights []float64, usersToItems [][]int) (*Bird, error)

NewBird creates a new recommender from input data.

func NewEmu

func NewEmu(cfg *BirdCfg, itemWeights []float64, usersToWeightedItems []map[int]float64) (*Bird, error)

NewEmu creates a new recommender from input data. Unlike Bird, the user-to-item bipartite graph is a weighted graph.

func (*Bird) Process

func (b *Bird) Process(query []QueryItem) ([]int, []int, error)

Process randomly samples items from the query and performs random walks starting from them. Returns a list of items and a list of users who referred this item in the walk.

type BirdCfg

type BirdCfg struct {
	Depth int `yaml:"depth"`
	Draws int `yaml:"draws"`
}

func NewBirdCfg

func NewBirdCfg() *BirdCfg

type Pair

type Pair struct {
	Object     int
	Occurences int // number of occurences
}

type PairList

type PairList []Pair // necessary evil to sort map by value

func (PairList) Len

func (p PairList) Len() int

func (PairList) Less

func (p PairList) Less(i, j int) bool

func (PairList) Swap

func (p PairList) Swap(i, j int)

type QueryItem

type QueryItem struct {
	Item   int
	Weight float64 // for instance number of past interactions with the item
}

type Weaver

type Weaver struct {
	Cfg         *WeaverCfg
	SocialGraph []map[int]float64
	*Bird
}

Weaver is a combination of a Bird, and a list of maps that represents a weighted user-user matrix. To avoid storing the full social graph, a mostly empty matrix, we store for each user a map that associates each connection to a weight. Each user that is not connected is attributed a DefaultWeight.

func NewWeaver

func NewWeaver(cfg *WeaverCfg, itemWeights []float64, usersToItems [][]int,
	socialGraph []map[int]float64) (*Weaver, error)

NewWeaver creates a new recommender from input data. Unlike Bird, users related to an item are not sampled uniformly, but according to socialCoef[user], making the recommendation dependent on both the query and the user being served.

func (*Weaver) Process

func (b *Weaver) Process(query []QueryItem, user int) ([]int, []int, error)

Process returns a slice of items that were visited during the random walks along with the users that referred these items.

type WeaverCfg

type WeaverCfg struct {
	DefaultWeight float64 `json:"default_weight"`
	*BirdCfg
}

func NewWeaverCfg

func NewWeaverCfg() *WeaverCfg