∎

11institutetext: Cedric De Boom, Thomas Demeester, Bart Dhoedt
22institutetext: Ghent University, imec, IDLab
Technologiepark 15
9052 Ghent, Belgium
22email: $\\{$cedric.deboom, thomas.demeester<EMAIL_ADDRESS>33institutetext: Rohan Agrawal, Samantha Hansen, Esh Kumar, Romain Yon, Ching-
Wei Chen 44institutetext: Spotify, Inc.
45 W 18th St
10011 New York, NY, USA
44email: $\\{$rohanag, slhansen, eshvk, romain, vidhya<EMAIL_ADDRESS>
# Large-Scale User Modeling with Recurrent Neural Networks for Music Discovery
on Multiple Time Scales

Cedric De Boom  Rohan Agrawal  Samantha Hansen  Esh Kumar  Romain Yon  Ching-
Wei Chen  Thomas Demeester  Bart Dhoedt

###### Abstract

The amount of content on online music streaming platforms is immense, and most
users only access a tiny fraction of this content. Recommender systems are the
application of choice to open up the collection to these users. Collaborative
filtering has the disadvantage that it relies on explicit ratings, which are
often unavailable, and generally disregards the temporal nature of music
consumption. On the other hand, item co-occurrence algorithms, such as the
recently introduced word2vec-based recommenders, are typically left without an
effective user representation. In this paper, we present a new approach to
model users through recurrent neural networks by sequentially processing
consumed items, represented by any type of embeddings and other context
features. This way we obtain semantically rich user representations, which
capture a user’s musical taste over time. Our experimental analysis on large-
scale user data shows that our model can be used to predict future songs a
user will likely listen to, both in the short and long term.

###### Keywords:

Recommender systems machine learning recurrent neural networks deep learning
word2vec music information retrieval representation learning

††journal: Multimedia Tools and Applications

##  1 Introduction

Online digital content providers, such as media streaming services and
e-commerce websites, usually have immense catalogs of items. To prevent users
from having to search manually through the entire catalog, recommender systems
help to filter out items users might like to watch, listen to, buy… and are
often based on characteristics of both users and items. One type of
recommendation algorithms is collaborative filtering, which is generally based
on ratings for items given by users. However, such explicit ratings are not
always available. For example, in what way does clicking on an item represent
how much the user likes this item? Implicit feedback models are therefore used
here, but they require careful parameter tuning. Next to this, systems that
model users based on aggregate historical consumption will often ignore the
notion of sequentiality. In the case of music consumption, for example, it has
been investigated that a user’s listening behavior can be described by a
trajectory in time along different artists and genres with periods of
fixations and transitions Figueiredo:2016ut .

Recently, recommenders have also been built on top of item embeddings
Barkan:2016wm ; Liang:2016wj . Such embeddings, or vector representations, are
generally learned using item co-occurrence measures inspired by recent
advances in language modeling, e.g. word2vec and related algorithms
Mikolov:2013uz . The problem with this approach is that we are left without an
adequate user representation, and the question remains how to derive such a
representation based on the given item embeddings.

In this work we focus on creating user representations in the context of new
music discovery on online streaming platforms. We start from given latent
embeddings of the items in the catalog and we represent users as a function of
their item consumption. For this, we propose that a user’s listening behavior
is a sequential process and is therefore governed by an underlying time-based
model. For example, think of a user listening to an artist’s album for some
time and then transitioning to the next album, or to a compilation playlist of
the same musical genre. To model the dynamics of a user’s listening pattern we
use recurrent neural networks, which are currently among the state-of-the-art
in many data series processing tasks, such as natural language
Sutskever:2014ty ; Bahdanau:2015vz  and speech processing Graves:2014vz . We
do not presuppose any of the item embedding properties, such that our model is
generally applicable to any type of item representation. In the next section
we will explain the problem setting and highlight related work regarding music
recommendation and deep learning. In Section 3 we will describe our
methodology, after which we perform an initial data analysis in Section 4. We
conclude with the results of our experiments in Section 5. A complete table
with the used symbols in this article is given in Appendix A.

##  2 Motivation and Related Work

Ever since the launch of the Netflix Prize competition in 2006 Bennett:2007uv
, research in recommender systems, and a particular subset called
collaborative filtering, has spiked. The basis of modern collaborative
filtering lies in latent-factor models, such as matrix factorization
Koren:2009jg . Herein, a low-dimensional latent vector is learned for each
item and user based on rating similarities, and in the most basic scheme the
dot product between a user vector $\bm{v}_{u}$ and item vector $\bm{v}_{i}$ is
learned to represent the rating $r_{ui}$ of item $i$ by user $u$:

$\displaystyle r_{ui}=\bm{v}_{u}^{T}\bm{v}_{i}.$ (1)

This setting is based on the entire user and item history, and does not take
into account that a user’s taste might shift over time. Koren et al.
Koren:2009jg  mention that such temporal effects can easily be brought into
the model by adding time-dependent biases for each item and user:

$\displaystyle r_{ui}(t)=\mu+b_{u}(t)+b_{i}(t)+\bm{v}_{u}^{T}\bm{v}_{i}(t).$
(2)

Dror et al. Dror:2011bb  extend on this work by introducing additional biases
for albums, artists, genres and user sessions, but these biases now represent
a global rather than a temporal effect of a user’s preference towards an item.
This way we can for example model to what extent the average rating for a
specific album is higher or lower compared to other albums. Although the
models of Koren et al. and Dror et al. are capable of representing a user’s
overall preference towards an item and how this preference shifts in time, it
cannot immediately explain why a user would rate item $w$ higher or lower
after having consumed items $x$, $y$ and $z$. That is, a user’s preference can
depend on what he or she has consumed in the immediate past. Basic
collaborative filtering techniques do not explicitly model this sequential
aspect of item consumption and the effect on what future items will be chosen.

Next to this, standard collaborative filtering and matrix factorization
techniques are mostly fit for explicit feedback settings, i.e. they are based
on positive as well as negative item ratings provided by the users. In more
general cases where we deal with views, purchases, clicks… we only have
positive feedback signals, which are binary, non-discriminative, sparse, and
are inherently noisy Hu:2008el . Standard and tested techniques to factorize a
sparse matrix of user-item interactions are singular value decomposition (SVD)
and non-negative matrix factorization (NMF) Anonymous:H3H5BbuI ; Lee:2000ti .
In the context of implicit feedback, however, missing values do not
necessarily imply negative samples. Pan et al. Pan:2008kb  therefore formulate
this as a so-called one class classification problem, in which observed
interactions are attributed higher importance than non-observed ones through
different weighting schemes, or through careful negative sampling. Hu et al.
Hu:2008el  on the other hand construct an implicit matrix factorization
algorithm, based on the singular value decomposition of the user-item matrix,
which differs from the standard algorithm by attaching higher confidence on
items with a large number of interactions during optimization. Johnson
Johnson:2014tf  uses the ideas from Hu et al. and devises a probabilistic
framework to model the probability of a user consuming an item using logistic
functions.

The implicit-feedback models calculate global recommendations and do not
exploit temporal information to decide which items the user might be
interested in. Recently, Figueiredo et al. Figueiredo:2016ut  have shown that
users on online music streaming services follow a trajectory through the
catalog, thereby focusing their attention to a particular artist for a certain
time span before continuing to the next artist. For this they use a
combination of different Markov models to describe the inter- (‘switch’) and
intra-artist (‘fixation’) transitions. In other work, Moore et al.
Moore:2013tj  learn user and song embeddings in a latent vector space and
model playlists using a first-order Markov model, for which they allow the
user and song vectors to drift over time in the latent space.

Compared to Markov models, which inherently obey the Markov property, recent
work has shown that recurrent neural networks (RNNs) are able to learn long-
term data dependencies, can process variable-length time series, have great
representational power, and can be learned through gradient-based
optimization. They can effectively model the non-linear temporal dynamics of
text, speech and audio VanDenOord:2016uo ; Sercu:2016ub ; Karpathy:2015wu , so
they are ideal candidates for sequential item recommendation. In a general
RNN, at each time step $t$ a new input sample $x_{t}$ is taken to update the
hidden state $h_{t}$:

$\displaystyle h_{t}=\mathcal{F}(Ux_{t}+Wh_{t-1}),$ (3)

in which $\mathcal{F}(\cdot)$ is a non-linear function, e.g. sigmoid
$\sigma(\cdot)$, $\tanh$ or a rectifier (ReLU and variants) Maas:2013tn . To
counter vanishing gradients during backpropagation and to be able to learn
long-term dependencies, recurrent architectures such as long short-term
memories (LSTMs) and gated recurrent units (GRUs) have been proposed, both
with comparable performances Hochreiter:1997fq ; Greff:2015wv ; Chung:2014wf .
These models use a gating mechanism, e.g. an LSTM introduces input ($i_{t}$)
and forget ($f_{t}$) gates that calculate how much of the input is taken in
and to what extent the hidden state should be updated, and an output gate
($o_{t}$) that leaks bits of the internal cell state ($c_{t}$) to the output:

$\displaystyle i_{t}$
$\displaystyle=\sigma\left(U_{i}x_{t}+W_{i}h_{t-1}+w_{i}\odot
c_{t-1}+b_{i}\right),$ $\displaystyle f_{t}$
$\displaystyle=\sigma\left(U_{f}x_{t}+W_{f}h_{t-1}+w_{f}\odot
c_{t-1}+b_{f}\right),$ $\displaystyle c_{t}$ $\displaystyle=f_{t}\odot
c_{t-1}+i_{t}\odot\tanh\left(U_{c}x_{t}+W_{c}h_{t-1}+b_{c}\right),$
$\displaystyle o_{t}$
$\displaystyle=\sigma\left(U_{o}x_{t}+W_{o}h_{t-1}+w_{o}\odot
c_{t-1}+b_{o}\right),$ $\displaystyle h_{t}$
$\displaystyle=o_{t}\odot\tanh\left(c_{t}\right),$ (4)

in which $\odot$ is the element-wise vector multiplication. GRUs only have a
reset ($r_{t}$) and update ($u_{t}$) gate, get rid of the cell state, and have
less parameters overall:

$\displaystyle r_{t}$
$\displaystyle=\sigma\left(U_{r}x_{t}+W_{r}h_{t-1}+b_{r}\right),$
$\displaystyle u_{t}$
$\displaystyle=\sigma\left(U_{u}x_{t}+W_{u}h_{t-1}+b_{u}\right),$
$\displaystyle g_{t}$ $\displaystyle=\tanh\left(U_{g}x_{t}+r_{t}\odot
W_{g}h_{t-1}+b_{g}\right),$ $\displaystyle h_{t}$
$\displaystyle=(1-u_{t})\odot h_{t-1}+u_{t}\odot g_{t}.$ (5)

Very recently there have been research efforts in using RNNs for item
recommendation. Hidasi et al. Hidasi:2015uq  use RNNs to recommend items by
predicting the next item interaction. The authors use one-hot item encodings
as input and produce scores for every item in the catalog, on which a ranking
loss is defined. The task can thus be compared to a classification problem.
For millions of items, this quickly leads to scalability issues, and the
authors resort to popularity-based sampling schemes to resolve this. Such
models typically take a long time to converge, and special care needs to be
taken not to introduce a popularity bias, since popular items will occur more
frequently in the training data. The work by Tan et al. Tan:2016vy  is closely
related to the previous approach, and they also state that making a prediction
for each item in the catalog is slow and intractable for many items. Instead,
low-dimensional item embeddings can be predicted at the output in a regression
task, a notion we will extend on in Section 3.

A popular method to learn item embeddings is the word2vec suite by Mikolov et
al. Mikolov:2013uz  with both Continuous Bag-of-Words and Skip-Gram variants.
In this, a corpus of item lists is fed into the model, which learns
distributed, low-dimensional vector embeddings for each item in the corpus.
Word2vec and variants have already been applied to item recommendation, e.g.
Barkan et al. Barkan:2016wm  formulate a word2vec variant to learn item
vectors in a set consumed by a user, Liang Liang:2016wj  devise a word2vec-
based CoFactor model that unifies both matrix factorization and item embedding
learning, and Ozsoy Ozsoy:2016tm  learns embeddings for places visited by
users on Foursquare to recommend new sites to visit. These works show that a
word2vec-based recommender system can outperform traditional matrix
factorization and collaborative filtering techniques on a variety of tasks. In
the work by Tan et al. item embeddings are predicted and at the same time
learned by the model itself, a practice that generally deteriorates the
embedding quality: in the limit, the embeddings will all collapse to a
degenerate, non-informative solution, since in this case the loss will be
minimal. Also, they minimize the cosine distance during training, which we
found to decrease performance a lot.

In the coming sections, we will train RNNs to predict songs a user might
listen to in the future as a tool to model users on online music streaming
platforms. For this, we will predict preexisting item embeddings—about which
we will not make any assumptions in the model—and our task is therefore a
regression rather than a classification problem. This approach is closely
related to the work by van den Oord et al. VanDenOord:2013tp  in which
collaborative latent vectors are predicted based on raw audio signals, and
also related to the work by Hill et al. Hill:2016wg  who learn to project
dictionary definition representations onto existing word embeddings. Regarding
sequential item recommendation, the related works by Hidasi et al. and Tan et
al. mentioned above both perform item recommendation within user sessions,
i.e. uninterrupted and coherent sequences of item interactions, which can last
from ca. 10 minutes to over an hour. Here, the prediction time scale is very
short-term, and since consumed items within a user session are usually more
similar than across user sessions, it is generally easier perform item
recommendation on this short time scale. In this work we will explore
recommending songs for short-term as well as long-term consumption. To
recommend songs on the long term, we will need to be able to model a user’s
behavior across session boundaries.

##  3 RNNs for Music Discovery

In this section we will explain the details of our approach to use RNNs as a
means to model users on online music streaming platforms and to recommend new
songs in a music discovery context. Since we aim towards models that can be
used efficiently in large-scale recommendation pipelines, we require the
models to be trained within a reasonable time frame. Furthermore, sampling
from the model should be efficient. Small models with little parameters are
typically wanted to satisfy both requirements.

Figure 1: The entire song recommendation pipeline for a specific user; we
start with the user’s listening history of $N$ songs, and we end the pipeline
with $k$ song recommendations.

The entire recommendation pipeline for one specific user is given in Figure 1.
The basic building blocks of the pipeline are song vectors, which have been
learned using the songs in the catalog. The general idea is then to capture
and predict a taste vector for each user. These taste vectors are the output
of an RNN that sequentially aggregates song vectors from the user’s listening
history, and can therefore be regarded as a representation of the user’s
musical taste. The taste vector can subsequently be used to generate song
recommendations by querying a tree data structure for the nearby song vectors.

Since we construct real-valued taste vectors, the RNN solves a regression task
rather than a classification task, as argued in Section 2. Directly predicting
item embeddings is a regression problem that requires predicting a limited set
of real-valued outputs, as opposed to a classifier with as many outputs as the
number of items. The computational footprint of these models is typically
smaller than the classifiers. They are usually learned faster, and are not per
se biased towards popular items. One of the main advantages is that any type
of item embeddings and embedding combinations, along with other features, can
be used to learn the regression model.

We break the recommendation pipeline into three separate stages which we will
cover below. First, we learn low-dimensional embeddings for each song in the
streaming catalog using word2vec (§3.1). Then, we use an RNN to generate taste
vectors for all users in the song embedding space (§3.2). Finally, we use the
taste vector to query songs in the nearby space to generate recommendations
for all users (§3.3).

###  3.1 Learning song embeddings

In the first stage of the recommendation pipeline we learn latent vector
representations for the top $N$ most popular songs in the catalog. For this,
we use Google’s word2vec suite as explained in Section 2; more specifically we
use the Continuous Bag-of-Words (CBoW) algorithm with negative sampling. As
input to the word2vec algorithm we take user-created playlists of songs. In
this, each playlist is considered as an ordered ‘document’ of songs. By
scanning all playlists in a windowed fashion, word2vec will learn a
distributed vector representation $\bm{s}$ with dimensionality $D$ for every
song $s$. Details regarding training data for word2vec will be highlighted in
Section 4.

###  3.2 Learning user taste vectors

In the second pipeline stage we use RNNs to produce user taste vectors based
on song listening history. The network takes a sequence of song vectors of
dimensionality $D$ as input and produces a single taste vector with the same
dimensionality $D$. Let’s denote the set of all users by $U$, the ordered
sequence of song vectors user $u$ listened to by $\left(\bm{s}^{u}\right)$,
and the predicted taste vector by $\bm{t}^{u}$. The RNN then produces:

$\forall u\in
U\colon\bm{t}^{u}=\mathcal{R}\left(\left(\bm{s}^{u}\right);\mathbf{W}\right),$
(6)

in which $\mathcal{R}(\cdot\;;\mathbf{W})$ represents the function the RNN
computes with parameters $\mathbf{W}$.

To learn a semantically rich user taste vector that is able to generate
adequate recommendations, ideally this taste vector should be able to capture
how a user’s listening behavior is evolving over time. We therefore train the
RNN to predict a song the user is going to listen to in the future. More
specifically, for a particular user $u$, we take the first $n$ consecutive
songs $\bm{s}^{u}_{1:n}$ this user has listened to, and we try to predict a
future song vector $\bm{s}^{u}_{n+\ell}$, for some strictly positive value of
$\ell$. As a loss function, we use the $L_{2}$ distance between the predicted
taste vector and the true future song vector:

$\displaystyle\mathcal{L}\left(\bm{s}^{u}_{n+\ell},\mathcal{R}\left(\bm{s}^{u}_{1:n};\mathbf{W}\right)\right)=\left\lVert\bm{s}^{u}_{n+\ell}-\mathcal{R}\left(\bm{s}^{u}_{1:n};\mathbf{W}\right)\right\rVert_{2}.$
(7)

We experimented with other distance functions, such as cosine distance and a
weighted mixture of cosine and $L_{2}$ distance. The cosine distance
$L_{\cos}(\cdot)$ between two vectors $\vec{x}$ and $\vec{y}$ is given by:

$\displaystyle
L_{\cos}\left(\vec{x},\vec{y}\right)=1-\frac{\vec{x}\cdot\vec{y}}{\left\lVert\vec{x}\right\rVert_{2}\left\lVert\vec{y}\right\rVert_{2}}.$
(8)

The $L_{2}$ distance, nevertheless, gave the best results in the experiments.

To determine the best value of the prediction offset $\ell$ we consider two
separate prediction tasks: short-term and long-term prediction. The idea is
that it is generally easier to predict a song a user is going to listen to
next—e.g. think of a user shuffling an artist album, or listening to a rock
playlist—than it is to predict the 50th song he is going to listen to in the
future. The underlying dynamics of a short-term and long-term prediction model
will therefore be different. For example, the short-term model will
intuitively be more focused on the last few tracks that were played, while the
long-term model will generally look at a bigger timeframe. During training we
sample a value of $\ell$ for every input sequence from a discrete uniform
distribution. More specifically, for the short-term model, $\ell$ is sampled
from $\mathrm{unif}\\!\left\\{1,10\right\\}$, and $\ell$ is sampled from
$\mathrm{unif}\\!\left\\{25,50\right\\}$ for the long-term model. Random
sampling of the prediction offset for every new input sequence reduces chances
of overfitting and also increases model generalization. The entire training
procedure is sketched in Algorithm 1. In here, we use a stochastic minibatch
version of the gradient-based Adam algorithm to update the RNN weights
Kingma:2015ku . We have also experimented with setting $\ell$ fixed to 1 for
the short-term model, but this leads to very near-sighted models that make
predictions almost solely based on the last played song. For example, first
listening to 100 classical songs and then to 1 pop song would lead to pop song
predictions by the RNN.

input : dataset $\mathcal{D}$ of song sequences, initial RNN parameters
$\mathbf{W}$

parameter : sequence length $n$, offsets $\ell_{\min}$ and $\ell_{\max}$,
learning rate $\eta$

1 repeat

2 shuffle(_$\mathcal{D}$_)

3 foreach  _batch $B\in\mathcal{D}$_ do

4 loss $\leftarrow 0$

5 foreach  _sequence $(\bm{s})\in B$_ do

6 $\ell\sim\mathrm{unif}\\!\left\\{\ell_{\min},\ell_{\max}\right\\}$

7 loss $\leftarrow$ loss
$+\;\mathcal{L}\left(\bm{s}_{n+\ell},\mathcal{R}\left(\bm{s}_{1:n};\mathbf{W}\right)\right)$

8

9 $\mathbf{W}\leftarrow$ adam_update(_$\mathbf{W}$ , loss, $\eta$_)

10

11

12until  _convergence_

Algorithm 1 RNN training procedure

###  3.3 Recommending songs

The output of the RNN is a user taste vector that resides in the same vector
space as all songs in the catalog. Since we trained the RNN to produce these
taste vectors to lie close to future songs a user might play—in terms of
$L_{2}$ distance—we can query for nearby songs in that vector space to
generate new song recommendations. To scale the search for nearby songs in
practice, we construct an Annoy111github.com/spotify/annoy tree datastructure
with all song vectors. The Annoy tree will iteratively divide the vector space
in regions using a locality-sensitive hashing random projection technique
Charikar:2002km , which facilitates approximate nearest neighbor querying. To
generate suggested recommendations for a particular user, we query the Annoy
tree using the user’s taste vector to find the top $k$ closest catalog songs
in the vector space.

###  3.4 Incorporating play context

In general we do not only know the order in which a user plays particular
songs, but we also know the context in which the songs have been played. By
context we mean a playlist, an album page, whether the user deliberately
clicked on the song, etc. This additional information can be very useful, e.g.
we can imagine that a user clicking on a song is a stronger indicator of the
user’s taste than when the song is played automatically in an album or
playlist after the previous song has finished playing. Since the RNN can
process any combination of arbitrary embeddings and features, we can supply a
context vector $\bm{c}^{u}$ as extra input. The context vector is in this case
concatenated with the song vector at each time step to produce the user taste
vector:

$\forall u\in
U\colon\bm{t}^{u}=\mathcal{R}\left(\left(\bm{s}^{u}\oplus\bm{c}^{u}\right);\mathbf{W}\right),$
(9)

in which we use the symbol $\oplus$ to denote vector concatenation. To
construct a context vector we consider the ordered set
$C=(\text{album},\text{playlist},\text{artist},\text{click},\dots)$ of all
possible contexts, denote $C_{i}$ as the $i$’th context in $C$, and $c(s)$ as
the play context for a particular song $s$, e.g.
$c(s)=\left\\{\text{playlist},\text{click}\right\\}$. The context vector for a
song $s$ is then constructed using a one-hot encoding scheme:

$\displaystyle\bm{c}=\sum_{i=1}^{|C|}\mathrm{onehot}(i,|C|)\cdot\mathbf{1}_{c(s)}(C_{i}),$
(10)

in which $\mathrm{onehot}(i,|C|)$ is a one-hot vector of length $|C|$ with a
single $1$ at position $i$, and in which $\mathbf{1}_{A}(x)$ is the indicator
function that evaluates to $1$ if $x\in A$ and to $0$ otherwise. We also
include the time difference between playing the current song and the last
played song. The final context vector $\bm{c}^{u}_{j}$ for the $j$’th song
$s^{u}_{j}$ played by user $u$ then becomes:

$\displaystyle\bm{c}^{u}_{j}=\Delta(s^{u}_{j},s^{u}_{j-1})\oplus\sum_{i=1}^{|C|}\mathrm{onehot}(i,|C|)\cdot\mathbf{1}_{c\left(s^{u}_{j}\right)}(C_{i}),$
(11)

in which $\Delta(s_{j},s_{j-1})$ is the time difference in seconds between
playing song $s_{j}$ and $s_{j-1}$, evaluating to $0$ if $s_{j-1}$ does not
exist.

###  3.5 User and model updates

The recommendation pipeline we described in this section can be used in both
static and dynamic contexts. In dynamic contexts, the model should be updated
frequently so that recommendations can immediately reflect the user’s current
listening behavior. This is easily done in our model: for every song the user
listens to we retrieve its song vector that we use to update the hidden state
of the RNN, after which we calculate a new taste vector to generate
recommendations. This requires that we keep track of the current RNN states
for every user in the system, which is a small overhead. In more static
contexts, in which recommendations are generated on a regular basis for all
users (every day, week…), there is no need to update the RNN for every song a
user listens to. Here, we retrieve the entire user listening history–or the
last $n$ songs–which we feed to a newly initialized RNN. We therefore do not
need to remember the RNN states for every user.

All recommendation modules that are deployed in practical environments have to
be updated regularly in order to reflect changes in the item catalog and user
behavior. This is no different for the framework we present here. In order to
perform a full model update, we subsequently train word2vec on the playlists
in the catalog, retrain the RNN model on the new song vectors, and populate
the Annoy tree with the same song vectors. Only retraining word2vec is not
sufficient since we almost never end up in the same song embedding space. If
we use dynamic user updates, note that we also have to do one static update
after retraining word2vec and the RNN, since the remembered RNN states will
have become invalid.

##  4 Data Gathering and Analysis

The first stage in the recommendation pipeline considers the learning of
semantically rich song vectors, for which we use the word2vec algorithm. In
this section we explain how we gather data to train this word2vec model, and
we perform a preliminary analysis on the song vectors. Finally we detail the
construction of the train and test data for the RNNs.

###  4.1 Training word2vec

To create training data for the word2vec model we treat user-created playlists
as documents and songs within these playlists as individual words, as
mentioned in Section 3. For this, we gather all user-created playlists on the
Spotify music streaming platform. In these playlists we only consider the top
$N$ most popular tracks; the other tracks are removed. In our experiments we
set $N$ to 6 million, which makes up for most of the streams on the Spotify
platform. After filtering out unpopular tracks, we further only consider
playlists with a length larger than 10 and smaller than 5000. We also restrict
ourselves to playlists which contain songs from at least 3 different artists
and 3 different albums, to make sure there is enough variation and diversity
in the playlists. After applying the filtering above, we arrive at a corpus of
$276.5$ million playlists in total. In the following step, the playlists are
fed to the word2vec suite, where we use the CBoW algorithm with negative
sampling. We go through the entire playlist corpus once during execution of
the algorithm in order to produce vectors with dimensionality $D=40$, a number
that we empirically determined and produces good results.

###  4.2 Data processing and filtering

In Section 5 we will train different RNN versions, for which we will use both
playlist and user listening data. Playlists are usually more contained
regarding artists and musical genres compared to listening data. Modeling
playlist song sequences with RNNs will therefore be easier, but we can miss
out important patterns that appear in actual listening data, especially if a
user listens to a wide variety of genres.

For the playlist data we extract chunks of 110 consecutive songs, i.e. 60
songs to feed to the RNN and the next 50 songs are used as ground truth for
the prediction. Regarding the user listening, which is captured in the first
half of 2016 on the Spotify platform, we only keep songs which have a song
vector associated with them; other songs are removed from the user’s history.
We also save context information for every played song; for this, we consider
the following 13 Spotify-related contexts: collection, library, radio, own
playlist, shared playlist, curated playlist, search, browse, artist, album,
chart, track, clicked, and unknown for missing context information. To extract
RNN training sequences we take chunks of 150 consecutive songs, for which the
first 100 songs are again used as input to the RNN and the last 50 as ground
truth. We allow more songs as input to the RNN compared to the playlist
training data since user listening data is generally more diverse than
playlist data, as mentioned before.

Since users often return to the same songs or artists over and over again, we
apply additional filtering to eliminate those songs. This will greatly improve
the RNN’s generalization, and will counter what we call the ‘easy prediction
bias’, as it is too easy to predict songs a user has already listened to. This
filtering is not needed for playlist data, since a song only appears once in a
playlist most of the times. The filtering rules we include, are:

  1. 1.

The last 50 songs should be unique;

  2. 2.

The last 50 songs should not appear in the first 100 songs;

  3. 3.

The last 50 artists should be unique;

  4. 4.

The last 50 artists should not appear in the first 100 artists.

Note that we only remove similar songs and artists from the ground truth
labels in the dataset, and that we leave the first 100 songs in the user’s
history intact. That is, the same song can still appear multiple times in
these first 100 songs, thereby steering the user’s preference towards this
particular song and influencing the predictions made by the RNN. For both
playlist and listening data we gather 300,000 train sequences, 5,000
validation sequences and 5,000 test sequences.

All pairsSubsequent pairs

Cosine distance

$0.0$$1.8$ Figure 2: Box plots of pairwise distances between songs in all test
set listening histories. $0$$10$$20$$30$$40$$50$$60$$70$$80$$\\#$transitions
with cos distance $>1$

$\\#$songs

$0$$200$$400$$600$$800$$1000$ Figure 3: Histogram of the number of song
transitions with cosine distance larger than 1.

###  4.3 User data analysis

To analyze the gathered data, we take all 5,000 listening history sequences in
the test set, and we calculate pairwise cosine distances between the song
vectors in these sequences. We measure both the vector distance between all
possible song pairs in a listening sequence, as well as the distance only
between subsequent songs. The distances are given as box plots in Figure 2, in
which the whiskers are drawn at 1.5 times the interquartile range. We see that
the all pairs median distance is larger than the subsequent pairs median
distance by around 0.25, indeed confirming the higher correlation between
subsequent songs. We also plot the number of song transitions within each
user’s listening history that have a cosine distance larger than 1, meaning
that the next song is more different from the current song than it is similar
to it. The histogram for this is shown in Figure 3. Most listening histories
have little such song transitions. The median number is seven, which points,
on average, to listening periods of 21 similar songs before transitioning to a
more different region in the song space, which in turn corresponds to coherent
listening sessions of about 1 to 1.5 hours long.

##  5 Experiments

In this section we discuss the results of various experiments and we show
examples of song recommendations produced by different RNN models. In the
following we first design the best RNN architecture by experimentation, after
which we explain the baselines against which the RNN models will be tested.
All experiments are run on an Amazon AWS instance, 32-core Intel Xeon 2.60GHz
CPU, 64GB RAM and Nvidia GRID K520 GPU with cuDNN v4. The RNN models are
implemented in Lasagne222github.com/Lasagne/Lasagne and Theano AlRfou:2016uc .

###  5.1 Network architecture

The neural network architecture we propose consists of a number of recurrent
layers followed by a number of dense layers. The number of input dimensions is
$D=40$, which is the dimensionality of a single song vector. For the recurrent
layers we consider both LSTMs and GRUs, since such models are state-of-the-art
in various NLP applications and can handle long-term dependencies. We use
standard implementations of these layers as described in Section 2, with a
hidden state dimensionality of all layers equal to $D_{hid}$. We will describe
how the optimal number of recurrent layers and the optimal value of $D_{hid}$
are chosen.

After the recurrent layers we consider two dense layers. We empirically set
the dimensionality of the first dense layer to $4\cdot D_{hid}$, and we use a
leaky ReLU nonlinearity with a leakiness of 0.01 Maas:2013tn . Since we are
predicting a user taste vector in the same song space, the output
dimensionality of the last dense layer is $D=40$, which is the same as the
input dimensionality. In the last layer we use a linear activation function,
since we are predicting raw vector values.

In a first experiment we set $D_{hid}$ to 50, we switch the recurrent layer
type between LSTM and GRU, and we also vary the number of recurrent layers
from 1 up to 3. We record train loss, validation loss, average gradient update
time for a single batch and average prediction time for a single sequence. For
this experiment we use the gathered playlist data, and we train a short-term
model for which we report the best values across 15 epochs of training. The
results are shown in Table 1. We see that both models are very comparable in
terms of validation loss, and that the optimal number of recurrent layers is
two. The LSTM model performs slightly better than the GRU model in this case,
but the GRU model predicts more than 50% faster than the LSTM model, which can
be important in large-scale commercial production environments. We observe
comparable results for listening history prediction as well as long-term
prediction. We therefore pick the two-layer GRU model as the optimal
architecture.

Table 1: Comparing recurrent layer type and number of layers on short-term playlist prediction. | Train loss | Validation loss | Update [ms] | Prediction [ms]
---|---|---|---|---
LSTM, 1 layer | 258.8 | 271.2 | 20 | 4.4
LSTM, 2 layers | 257.3 | 270.2 | 39 | 8.7
LSTM, 3 layers | 258.1 | 271.0 | 58 | 13.0
GRU, 1 layer | 259.0 | 271.0 | 16 | 2.2
GRU, 2 layers | 257.3 | 270.5 | 30 | 4.1
GRU, 3 layers | 257.5 | 270.6 | 45 | 6.1
Table 2: Comparing performance with varying hidden layer size $D_{hid}$ on short-term playlist prediction. $D_{hid}$ |  $L_{2}$ validation loss | Cosine validation loss
---|---|---
20 | 287.3 | 0.464
30 | 276.4 | 0.425
40 | 271.5 | 0.408
50 | 270.5 | 0.406
60 | 270.0 | 0.406
70 | 270.4 | 0.406
80 | 270.5 | 0.407
90 | 270.1 | 0.405
100 | 270.4 | 0.406

Next we perform experiments to determine the optimal hidden state size
$D_{hid}$. We train the two-layer GRU architecture from above for a short-term
playlist prediction, and we vary $D_{hid}$ from 20 to 100 in steps of 10. The
results are shown in Table 2. The validation loss is the highest at 20, and is
minimal at $D_{hid}$ values of 50 and 60. The loss remains more or less stable
if we increasing the hidden state size to 100. Since larger hidden state sizes
imply slower prediction and train times, we choose $D_{hid}=50$ as the optimal
hidden state size. These observations are also valid for long-term prediction
and for listening history data. The final architecture is displayed in Table
3. It turns out that this architecture is also near-optimal for long-term
playlist prediction as well as for user listening data. Since the number of
network parameters is low and given the large amount of training data, we do
not need additional regularization.

We also train short-term user listening RNNs with additional play context
information at the input, as described in Section 3.4, and with the same
configurations as in Tables 1 and 2. The optimal configuration is a 2-layer
architecture with $D_{hid}$ equal to 100, but the differences in performance
for $50\leq D_{hid}<100$ are minimal. Furthermore, the performance gain
compared to the same model without context information is non-significant. We
will therefore disregard play context models in the rest of the experiments.

###  5.2 Baselines

We will compare the performance of different RNN models against several
baseline models. The general idea here is again that a user’s listening
behavior is governed by underlying temporal dynamics. We consider three types
of baseline models: an exponential discount model, a weight-based model, and a
classification model. The first two types are aggregation models, which means
that they take an arbitrary number of song vectors as input and produce one
output vector by mathematically combining the song vectors, e.g. through
summing or taking a maximum across dimensions. Aggregation of distributed
vectors is a popular practice in NLP applications and deep learning in general
since it does not require any training when the vector space changes
dosSantos:2014tr ; Collobert:2011tk . In our case however, the danger of
aggregation is that sometimes songs from different genres are summed together,
so that we can end up in ‘wrong’ parts of the song space. For example, if we
aggregate the song vectors of a user listening to a mix of classical and pop
music, we might arrive in a space where the majority of songs is jazz, which
in turn will lead to bad recommendations. The third type of baseline is based
on the work by Hidasi et al. Hidasi:2015uq  as mentioned in Section 2. In
this, we will not predict an output vector to query the Annoy LSH tree, but we
will output probability scores for all $N$ items in the catalog. The top $k$
items can then immediately be recommended.

Table 3: The final neural network architecture. | Layer type (no. of dimensions) and non-linearity
---|---
| Input (40)
1 | GRU (50)
|  sigmoid (gates); tanh (hidden update)
2 | GRU (50)
|  sigmoid (gates); tanh (hidden update)
3 | Fully connected dense (200)
|  Leaky ReLU, leakiness $=0.01$
4 | Fully connected dense (40)
|  Linear activation

#### Exponential discount model

In the exponential discount model we make the assumption that a user’s taste
is better reflected by the recent songs he has listened to than by songs he
has listened to a while ago. We model this type of temporal dynamics by the
following exponentially decaying weight model:

$\forall u\in
U\colon\bm{t}^{u}=\sum_{j=1}^{k}\bm{s}^{u}_{j}\cdot\gamma^{k-j}.$ (12)

In this, we consider the song history of user $u$ which has length $k$, and we
weigh every vector by a power of $\gamma$, the discount factor. Setting
$\gamma=1$ results in no discounting and leads to a simple sum of the song
vectors, while setting $\gamma<1$ focuses more attention on recently played
songs. The smaller $\gamma$, the more substantial this contribution becomes
compared to songs played a longer time ago. If $\gamma=0$, the user taste
vector is essentially the vector of the last played song.

#### Weight-based model

This model is based on the weighted word embedding aggregation technique by De
Boom et al. DeBoom:2016gm . As in the exponential discount model, we will
multiply each song vector $\bm{s}_{j}$ by a weight $w_{j}$:

$\forall u\in
U\colon\bm{t}^{u}=\mathcal{W}\left(\left(\bm{s}^{u}\right);\bm{w}\right)=\sum_{j=1}^{k}\bm{s}^{u}_{j}\cdot
w_{j},$ (13)

in which we gather all weights $w_{j}$ in a $k$-dimensional vector $\bm{w}$.
Now, instead of fixing the weights to an exponential regime, we will learn the
weights through the same gradient descent procedure as in Algorithm 1. In this
algorithm we replace the RNN loss by the following weight-based loss:

$\displaystyle\mathcal{L}\left(\bm{s}^{u}_{k+\ell},\mathcal{W}\left(\left(\bm{s}^{u}\right);\bm{w}\right)\right)$
$\displaystyle\qquad\qquad\qquad\quad=\left\lVert\bm{s}^{u}_{k+\ell}-\mathcal{W}\left(\left(\bm{s}^{u}\right);\bm{w}\right)\right\rVert_{2}+\lambda\left\lVert\bm{w}\right\rVert_{2}.$
(14)

We include the last term as weight regularization, and we empirically set
$\lambda$ to 0.001. Apart from this regularization term, we do not imply any
restrictions on or relations between the weights. We train a weight-based
model on user listening data for both short- and long-term predictions, and
the resulting weights are plotted in Figure 4. For the short-term prediction
the weights are largest for more recent tracks and decrease the further we go
back in the past. This confirms the hypothesis that current listening behavior
is largely dependent on recent listening history.For the long-term model we
largely observe the same trend, but the weights are noisier and generally
larger than the short-term weights. Also, the weights increase again in
magnitude for the first 10 tracks in the sequence. This may signify that a
portion of a user’s long-term listening behavior can be explained by looking
at songs, genres or artists he has listened to in the past and returns to
after a while.

$1$$20$${40}$${60}$${80}$Weight index $j$

Weight magnitude $w_{j}$

$-0.2$$1$Short-termLong-term Figure 4: Normalized weight magnitudes for long-
and short-term prediction.

#### Classification model

As mentioned above, we loosely rely on the work by Hidasi et al. Hidasi:2015uq
to construct a classification baseline model. In this work, the items are
encoded as a one-hot representation, and the output of the model is a
probability score for every item in the catalog. To be able to fairly compare
between all other baselines, and to help scale the model, we slightly adapt it
and use the word2vec vectors as input instead of the one-hot item encodings.
We employ the same neural network model as in Table 3 and at the output we add
an additional dense layer with output dimensionality $N=6{,}000{,}000$ and
softmax activation function. The memory footprint of this softmax model thus
substantially increases by around 938MiB, compared to the model in Table 3.
Given the large output dimensionality, we also experimented with a two-stage
hierarchical softmax layer Goodman:2001dp , but the computational improvements
were only marginal and the model performed worse.

We train the softmax classification model with two different loss functions.
First, we consider the categorical cross-entropy loss in the case there is
only one target:

$\displaystyle\mathcal{L}\left(i,\mathcal{R}\left(\bm{s}^{u}_{1:k};\mathbf{W}\right)\right)=-\mathrm{onehot}\left(s^{u}_{k+\ell},N\right)\cdot\log\left[\mathrm{softmax}\left(\mathcal{R}\left(\bm{s}^{u}_{1:k};\mathbf{W}\right)\right)\right]^{\top}.$
(15)

In this loss function, $i$ is the RNN output index of the target song to be
predicted, and
$\mathrm{softmax}\left(\mathcal{R}\left(\bm{s}^{u}_{1:k};\mathbf{W}\right)\right)$
is the output of the RNN after a softmax nonlinearity given the input vectors
$\bm{s}^{u}_{1:k}$. The second loss function is a pairwise ranking loss used
in the Bayesian Personalized Ranking (BPR) scheme by Rendle et
al.Rendle:2009wp . This loss function evaluates the score of the positive
target against randomly sampled negative targets:

$\displaystyle\mathcal{L}\left(i,\mathcal{R}\left(\bm{s}^{u}_{1:k};\mathbf{W}\right)\right)=-\frac{1}{N_{S}}\sum_{j=1}^{N_{S}}\log\left[\sigma\left(\mathcal{R}\left(\bm{s}^{u}_{1:k};\mathbf{W}\right)_{i}-\mathcal{R}\left(\bm{s}^{u}_{1:k};\mathbf{W}\right)_{j}\right)\right].$
(16)

In this, $N_{S}$ is the number of negative samples that we set fixed to 100,
$\sigma(\cdot)$ is the sigmoid function, and $i$ is again the output index of
the positive sample. Note that we use a sigmoid nonlinearity rather than a
softmax. In practice we also add an $L2$ regularization term on the sum of the
positive output value and negative sample values. To generate negative
samples, we sample song IDs from a Zeta or Zipf distribution with parameter
$z=1.05$, which we checked empirically on the song unigram distribution:

$\displaystyle\mathrm{Zipf}_{z}(k)=\frac{k^{-z}}{\zeta(z)},$ (17)

in which $\zeta(\cdot)$ is the Riemann zeta function. We resample whenever a
song appears in a user’s listening data to make sure the sample is truly
negative.

Hidasi et al. reported better stability using BPR loss compared to cross-
entropy loss, but our sampling-based training procedure from Algorithm 1 did
not produce any unstable networks for both loss functions. We trained short-
term and long-term networks on the filtered listening history data using both
cross-entropy and BPR, and all models took around 2.5 days to converge. By
comparison, training until convergence on the same hardware only took 1.5
hours for the models presented in this work.

###  5.3 Results

In this section we will display several performance metrics on the test set of
user listening histories. After all, the music recommendations will be based
on what a user has listened to in the past. We have trained four RNN models: a
playlist short-term (rPST) and long-term (rPLT) RNN, and a user history short-
term (rHST) and long-term (rHLT) RNN. We also report metrics for five
baselines: a short-term (bWST) and long-term (bWLT) weight-based model, and
exponential discount models with $\gamma\in\left\\{1.0,0.97,0.85\right\\}$. In
the following we will perform a forward analysis to evaluate how well a taste
vector is related to future song vectors, which will show the predictive
capacity of the different models. We will also do a backwards analysis to
study on what part of the listening history sequences the different models
tend to focus. We conclude with results on a song prediction task.

#### Forward analysis

In the forward analysis we take the first 100 songs of a user’s listening
history, which we use to generate the taste vector. This taste vector is then
compared to the next 50 song vectors in the listening history in terms of
cosine distance. That is, for each user $u$ in the test set we calculate the
sequence $\left(L_{\cos}(\bm{t}^{u},\bm{s}^{u}_{100+j})\right)$, for
$j\in\left\\{1,2,\dots,50\right\\}$. Figure 5 shows a plot of these sequences
averaged over all users in the test set. The overall trend of every model is
that the cosine distance increases if we compare the taste vector to songs
further in the future. This is not surprising since it is generally easier to
predict nearby songs than it is to predict songs in the far future, because
the former are usually more related to the last played songs. We see that the
$\gamma=0.85$ and rPST model have comparable performance. They have low cosine
distance for the first few tracks, but this quickly starts to rise, and they
both become the worst performing models for long-term prediction. All other
models, apart from rHST and rHLT, behave similarly, with rPLT being slightly
better and the $\gamma=0.97$ model slightly worse than all others. The two
best performing models are rHST and rHLT. Until future track 20, the rHST
model gives the lowest cosine distance, and rHLT is significantly the best
model after that. Since playlists are typically more coherent than listening
histories—e.g. they often contain entire albums or sometimes only songs by the
same artist—this can explain why the playlist-trained RNNs, and especially
rPST, perform not that well in this analysis. Another general trend is that ST
models typically perform better than their LT counterparts in the very near
future. And at some point the LT model becomes better than the ST model and is
a better predictor on the long term. Finally, among all baselines, we also
observe that bWST is the best performing short-term model, and bWLT performs
best to predict on the long term, which is not surprising since the weight-
based models are a generalization of the discounting models. Note that the
classification models remain absent, because in this case the output of the
RNN is not a user taste vector.

$0$$10$${20}$${30}$${40}$${50}$Future song index $j$

Cosine distance $(\bm{t}^{u},\bm{s}^{u}_{100+j})$

$0.55$$0.6$$0.65$$0.7$rPSTrPLTrHSTrHLTbWSTbWLT$0.85$$0.97$$1.0$ Figure 5:
Forward analysis of the taste vector models on filtered listening history
data.

#### Backwards analysis

In this analysis we again take the first 100 songs of a user’ listening
history, which we use to generate a taste vector. We then compare this taste
vector to these first 100 songs, i.e. the songs that generated the taste
vector. We thus look back in time to gain insights as to what parts of the
listening history contribute most or least to the taste vector. For this we
calculate the sequence $\left(L_{\cos}(\bm{t}^{u},\bm{s}^{u}_{j})\right)$, for
$j\in\left\\{1,2,\dots,100\right\\}$, and Figure 6 plots this sequence for
each model averaged over all users in the test set. We see that the rPST and
$\gamma=0.85$ models are very focused on the last songs that were played, and
the average cosine distance increases rapidly the further we go back in
history: for songs 1 until 80 they are the worst performing. These models will
typically be very near-sighted in their predictions, that is, the song
recommendations will mostly be based on the last 10 played tracks. This is
again due to the fact that playlists are very coherent, and predicting a near-
future track can be done by looking at the last tracks alone. The rHST and
bWST models also show a similar behavior, but the difference in cosine
distance for tracks in the near and far history is not as large compared to
rPST. The listening history RNNs, both rHST and rHLT, produce an overall high
cosine distance. These models are therefore not really tied to or focused on
particular songs in the user’s history. It is interesting to note that the
plot for rHLT and bWLT is a near-flat line, so that the produced taste vector
lies equally far from all songs in terms of cosine distance. In comparison,
the $\gamma=1.0$ taste vector, which is actually just a sum of all songs,
produces a U-shaped plot, which is a behavior similar to the long-term weights
in Figure 4. If we would attribute more weight to the first and last few
tracks, we would end up with a flatter line. The $\gamma=0.97$ plot also has a
U-shape, but the minimum is shifted more towards the recent listening history.
Note again that the classification models are absent in this analysis for the
same reason as specified above.

$0$$20$${40}$${60}$${80}$${100}$Song index $j$

Cosine distance $(\bm{t}^{u},\bm{s}^{u}_{j})$

$0.3$$0.4$$0.5$$0.6$rPSTrPLTrHSTrHLTbWSTbWLT$0.85$$0.97$$1.0$ Figure 6:
Backwards analysis of the taste vector models on filtered listening history
data.

#### Precision@k

In this section we calculate the precision of actual song recommendations. We
again take 100 songs from a user’s history which we use to generate a taste
vector. Then, as described in Section 3.3, we query the word2vec space for the
$k$ nearest songs in the catalog in terms of cosine distance. We will denote
the resulting set as $\Omega\left(\bm{t}^{u},k\right)$. The $precision@k$
value is then the fraction of how many songs in
$\Omega\left(\bm{t}^{u},k\right)$ actually appear in the user’s next $k$
tracks:

$\displaystyle precision@k=$ (18) $\displaystyle\qquad\frac{1}{|U|}\sum_{u\in
U}\frac{\left|\left\\{s\colon s\in\Omega\left(\bm{t}^{u},k\right)\wedge
s\in(s^{u}_{101:100+k})\right\\}\right|}{k}.$

We can also generalize this to $precision@[j:k]$:

$\displaystyle precision@[j:k]=$ (19)
$\displaystyle\quad\frac{1}{|U|}\sum_{u\in U}\frac{\left|\left\\{s\colon
s\in\Omega\left(\bm{t}^{u},k-j+1\right)\wedge
s\in(s^{u}_{100+j:100+k})\right\\}\right|}{k-j+1}.$

Here we disregard the user’s first next $j-1$ tracks, since it is often easier
to predict the immediate next tracks than it is to predict tracks further in
the future. For the next results, we also slightly alter the definition of
$\Omega\left(\bm{t}^{u},k\right)$: given the fact that no song in
$(s^{u}_{101:150})$ occurs in $(s^{u}_{1:100})$ for all users $u$, as
described in Section 4.2, we only regard the $k$ nearest songs of $\bm{t}^{u}$
that do not appear in $(s^{u}_{1:100})$. For the classification models, we
simply take the top $k$ songs with the highest scores, and compare them to the
ground truth. If we denote these top $k$ songs by
$\Omega\left(\mathcal{R}\left(\bm{s}^{u}_{1:k};\mathbf{W}\right),k\right)$, we
can reuse the same definition of $precision@k$ from above.

The results of the experiments are shown in Table 4. In bold we mark the best
performing model for each task, and the second best model is underlined. The
overall precisions are quite low, but given that we aggressively filtered the
listening data (Section 4.2), the task is rather difficult. The history-based
RNNs clearly perform best in all tasks. Generally, for $precision@10$, $@25$
and $@50$ all short-term models outperform the long-term models. But once we
skip the first 25 songs, which are easier to predict, the long-term models
take over, which shows that listening behavior indeed changes over time. The
performance of the playlist RNNs and weight-based models are comparable to the
exponential discount models, which we already saw in Figure 5.

All four classification models that we trained achieved the same precision
score of 0 percent, so we listed them as one entry in Table 4. They were not
able to correctly guess any of the 50 future songs a user might listen to. We
can think of many reasons why we see this result. First, the output
dimensionality of 6 million is extremely large, which makes it difficult to
discriminate between different but comparable items. The RecSys Challenge 2015
dataset, used in both the works of Hidasi et al. and Tan et al., only has
around 37,500 items to predict, which is 160 times less than 6 million.
Second, the number of weights in the classification model is orders of
magnitudes larger than for the regression model, which causes learning to be
much harder. And third, the data in the works by Hidasi et al. and Tan et al.
comes from user sessions, which are mostly contained and coherent sequences of
songs a user listens to within a certain time span, see also Section 2. The
listening history dataset in our work goes across user sessions to be able to
recommend on the long term, which makes it much more difficult to model the
temporal dynamics. This is reflected in the overall low precision accuracies.

#### A note on scalability

As indicated in the title of this article, our methodology should allow for
scalable music discovery. The training procedure—i.e. training word2vec and
the RNN—is not time-critical and can be trained offline. Despite the fact that
these procedures could be parallelized when needed Ji:2016va , we will focus
on the recommendation part of the system itself, which is more time-critical.

Since every user can be treated independently, the entire pipeline we have
proposed in Figure 1 is ’embarrassingly parallel’ and can therefore be scaled
up to as many computational nodes as available. Retrieving song vectors comes
down to a dictionary lookup in constant time
$\operatorname{O}\\!\left(1\right)$. Calculating user taste vectors through
the RNN is linear $\operatorname{O}\\!\left(n\right)$ in the number of
historical song vectors $n$ we consider. An extensive study of the scalability
of Annoy, the last part in the pipeline, is beyond the scope of this paper,
and poses a trade-off between accuracy and performance: more tree nodes
inspected leads generally to more accurate nearest neighbors, but a slower
retrieval time (approximately linear in the number of inspected nodes)333There
is an excellent web article by Radim Rehurek from 2014 which studies this in
depth, see rare-technologies.com/performance-shootout-of-nearest-neighbours-
querying. Retrieving $1{,}000$ nearest neighbors using 10 trees and $10{,}000$
inspected nodes only takes on average 2.6ms on our system, which is in same
order of magnitude compared to the RNN prediction times given in Table 1.

Combining all the above, sampling a taste vector from the rHLT RNN and
retrieving the top 50 closest songs from the Annoy LSH tree over 1,000 runs
takes on average 58ms on our system, while retrieving the top 50 songs from
the BPR RNN takes on average 754ms, which is 13 times slower.

Table 4: Results for the $\mathbf{precision@k}$ experiments on filtered listening history data. | Precision (%)
---|---
| $@10$ | $@25$ | $@50$ | $@[25:50]$ | $@[30:50]$
rPST | 1.64 | 2.39 | 2.81 | 1.15 | 0.94
rPLT | 1.27 | 1.98 | 2.64 | 1.30 | 1.06
rHST | 2.03 | 2.95 | 3.72 | 1.85 | 1.53
rHLT | 1.40 | 2.31 | 3.25 | 1.89 | 1.63
bWST | 1.67 | 2.37 | 2.94 | 1.28 | 1.04
bWLT | 1.32 | 1.95 | 2.62 | 1.31 | 1.06
$\gamma=0.85$ | 1.94 | 2.63 | 3.00 | 1.20 | 0.96
$\gamma=0.97$ | 1.56 | 2.20 | 2.77 | 1.30 | 1.05
$\gamma=1.0$ | 1.16 | 1.78 | 2.41 | 1.24 | 1.02
Classification | 0.00 | 0.00 | 0.00 | 0.00 | 0.00

##  6 Conclusions

We modeled users on large-scale online music streaming platforms for the
purpose of new music discovery. We sequentially processed a user’s listening
history using recurrent neural networks in order to predict a song he or she
will listen to in the future. For this we treated the problem as a regression
rather than classification task, in which we predict continuous-valued vectors
instead of distinct classes. We designed a short-term and long-term prediction
model, and we trained both versions on playlist data as well as filtered user
listening history data. The best performing models were chosen to be as small
and efficient as possible in order to fit in large-scale production
environments. Incorporating extra play context features did not significantly
improve the models. We performed a set of experimental analyses for which we
conclude that the history-based models outperform the playlist-based and all
baseline models, and we especially pointed out the advantages of using the
regression approach over the classification baseline models. We also saw that
there is indeed a difference between short-term and long-term listening
behavior. In this work we modeled these with different models. One possible
line of future work would be to design a single sequence-to-sequence model
that captures both short and long term time dependencies to predict the entire
future listening sequence Sutskever:2014ty .

## Acknowledgments

Cedric De Boom is funded by a PhD grant of the Research Foundation - Flanders
(FWO). We greatly thank Nvidia for its donation of a Tesla K40 and Titan X GPU
to support the research of the IDLab group at Ghent University.

## References

  * (1) Al-Rfou, R., Alain, G., Almahairi, A., al, e.: Theano - A Python framework for fast computation of mathematical expressions.  arXiv.org (2016)
  * (2) Bahdanau, D., Cho, K., Bengio, Y.: Neural Machine Translation by Jointly Learning to Align and Translate.  In: ICLR (2015)
  * (3) Barkan, O., Koenigstein, N.: Item2vec - Neural Item Embedding for Collaborative Filtering.  RecSys Posters (2016)
  * (4) Bennett, J., Lanning, S.: The Netflix Prize.  In: Proceedings of KDD cup and workshop (2007)
  * (5) Charikar, M.: Similarity estimation techniques from rounding algorithms.  In: STOC (2002)
  * (6) Chung, J., Gülçehre, Ç., Cho, K., Bengio, Y.: Empirical Evaluation of Gated Recurrent Neural Networks on Sequence Modeling.  arXiv.org (2014)
  * (7) Collobert, R., Weston, J., Bottou, L., Karlen, M., Kavukcuoglu, K., Kuksa, P.: Natural Language Processing (Almost) from Scratch.  The Journal of Machine Learning Research (2011)
  * (8) De Boom, C., Van Canneyt, S., Demeester, T., Dhoedt, B.: Representation learning for very short texts using weighted word embedding aggregation.  Pattern Recognition Letters (2016)
  * (9) Dror, G., Koenigstein, N., Koren, Y.: Yahoo! music recommendations - modeling music ratings with temporal dynamics and item taxonomy.  In: RecSys (2011)
  * (10) Figueiredo, F., Ribeiro, B., Faloutsos, C., Andrade, N., Almeida, J.M.: Mining Online Music Listening Trajectories.  In: ISMIR (2016)
  * (11) Goodman, J.: Classes for fast maximum entropy training.  In: 2001 IEEE International Conference on Acoustics, Speech, and Signal Processing. Proceedings (Cat. No.01CH37221 (2001)
  * (12) Graves, A., Jaitly, N.: Towards End-To-End Speech Recognition with Recurrent Neural Networks.  In: ICML (2014)
  * (13) Greff, K., Srivastava, R.K., Koutník, J., Steunebrink, B.R., Schmidhuber, J.: LSTM: A Search Space Odyssey.  arXiv.org (2015)
  * (14) Hidasi, B., Karatzoglou, A., Baltrunas, L., Tikk, D.: Session-based Recommendations with Recurrent Neural Networks.  arXiv.org (2016)
  * (15) Hill, F., Cho, K., Korhonen, A., Bengio, Y.: Learning to Understand Phrases by Embedding the Dictionary.  TACL (2016)
  * (16) Hochreiter, S., Schmidhuber, J.: Long short-term memory.  Neural Computation (1997)
  * (17) Hu, Y., Koren, Y., Volinsky, C.: Collaborative filtering for implicit feedback datasets.  2008 Eighth IEEE International … (2008)
  * (18) Ji, S., Satish, N., Li, S., Dubey, P.: Parallelizing Word2Vec in Multi-Core and Many-Core Architectures.  CoRR (2016)
  * (19) Johnson, C.C.: Logistic matrix factorization for implicit feedback data.  In: NIPS 2014 Workshop on Distributed Machine Learning … (2014)
  * (20) Karpathy, A., Johnson, J., Fei-Fei, L.: Visualizing and Understanding Recurrent Networks.  arXiv.org (2015)
  * (21) Kingma, D., Ba, J.: Adam: A Method for Stochastic Optimization.  In: ICLR (2015)
  * (22) Koren, Y., Bell, R., Volinsky, C.: Matrix Factorization Techniques for Recommender Systems.  Computer (2009)
  * (23) Lee, D.D., Seung, H.S.: Algorithms for Non-negative Matrix Factorization.  NIPS 2000 (2000)
  * (24) Liang, D., Altosaar, J., Charlin, L.: Factorization Meets the Item Embedding: Regularizing Matrix Factorization with Item Co-occurrence.  In: ICML Workshop (2016)
  * (25) Maas, A.L., Hannun, A.Y., Ng, A.Y.: Rectifier nonlinearities improve neural network acoustic models.  In: ICML (2013)
  * (26) Mikolov, T., Sutskever, I., Chen, K., Corrado, G., Dean, J.: Distributed Representations of Words and Phrases and their Compositionality.  In: NIPS 2013: Advances in neural information processing systems (2013)
  * (27) Moore, J.L., Chen, S., Turnbull, D., Joachims, T.: Taste Over Time - The Temporal Dynamics of User Preferences.  In: ISMIR (2013)
  * (28) Ozsoy, M.G.: From Word Embeddings to Item Recommendation  arXiv.org (2016)
  * (29) Pan, R., Zhou, Y., Cao, B., Liu, N.N., Lukose, R., Scholz, M., Yang, Q.: One-Class Collaborative Filtering.  In: 2008 Eighth IEEE International Conference on Data Mining (2008)
  * (30) Paterek, A.: Improving regularized singular value decomposition for collaborative filtering.  In: KDDCup 2007 (2007)
  * (31) Rendle, S., Freudenthaler, C., Gantner, Z., Schmidt-Thieme, L.: BPR - Bayesian Personalized Ranking from Implicit Feedback.  UAI (2009)
  * (32) dos Santos, C.N., Gatti, M.: Deep Convolutional Neural Networks for Sentiment Analysis of Short Texts.  In: COLING 2014, the 25th International Conference on Computational Linguistics (2014)
  * (33) Sercu, T., Goel, V.: Advances in Very Deep Convolutional Neural Networks for LVCSR.  In: Interspeech (2016)
  * (34) Sutskever, I., Vinyals, O., Le, Q.V.: Sequence to Sequence Learning with Neural Networks.  In: NIPS 2014 (2014)
  * (35) Tan, Y.K., Xu, X., Liu, Y.: Improved Recurrent Neural Networks for Session-based Recommendations.  arXiv.org (2016)
  * (36) Van Den Oord, A., Dieleman, S., Schrauwen, B.: Deep content-based music recommendation.  In: NIPS (2013)
  * (37) Van Den Oord, A., Dieleman, S., Zen, H., Simonyan, K., Vinyals, O., Graves, A., Kalchbrenner, N., Senior, A., Kavukcuoglu, K.: WaveNet: A Generative Model for Raw Audio.  arXiv.org (2016)

##  Appendix A Table of Symbols

In order of appearance:
$\vec{v}_{u}(t)$ User vector for user $u$ at time $t$ $\vec{v}_{i}(t)$ Item
vector for item $i$ at time $t$ $r_{ui}$ rating of item $i$ by user $u$ $\mu$
Global average rating $b_{u}(t)$ Rating bias of user $u$ at time $t$
$b_{i}(t)$ Rating bias of item $i$ at time $t$ $h_{t}$ Hidden state at time
$t$ $c_{t}$ Cell state at time $t$ $f_{t}$ Forget gate at time $t$ $o_{t}$
Output gate at time $t$ $r_{t}$ Reset gate at time $t$ $u_{t}$ Update gate at
time $t$ $U_{x},W_{x}$ Weight matrices for gate $x$ $w_{x}$ Weight vector for
gate $x$ $b_{x}$ Bias for gate $x$ $\mathcal{F}(\cdot)$ Non-linear function
$\sigma(\cdot)$ Sigmoid function $\odot$ Element-wise multiplication operator
$N$ Number of songs in the catalog $D$ Embedding dimensionality $U$ Set of all
users on the platform $\left(\vec{s}^{u}\right)$ Ordered sequence of song
vectors user $u$ listened to $\vec{t}^{u}$ Taste vector of user $u$
$\mathcal{R}\left(\cdot;\mathbf{W}\right)$ RNN function with parameters
$\mathbf{W}$ $\mathcal{L}(\cdot)$ Loss function
$\left\lVert\cdot\right\rVert_{2}$ L2 norm $L_{\cos}(\cdot)$ Cosine distance
$\mathrm{unif}\left\\{x,y\right\\}$ Uniform distribution between $x$ and $y$
$\mathcal{D}$ Dataset of song sequences $\ell_{\min},\ell_{\max}$ Minimum and
maximum sampling offsets $\eta$ Learning rate $\vec{c}^{u}$ Context vector for
user $u$ $\oplus$ Vector concatenation operator $C$ Ordered set of contexts on
the Spotify platform $C_{i}$ $i$’th context in $C$ $c(s)$ set of contexts for
song $s$ $\mathrm{onehot}(i,L)$ One-hot vector of length $L$ with a 1 at
position $i$ $\mathbf{1}_{A}(x)$ Indicator function: 1 if $x\in A$, else 0
$\Delta(x,y)$ Time difference between playing songs $x$ and $y$ $D_{hid}$
Hidden dimensionality $\gamma$ Discount factor $\mathcal{W}(\cdot;\vec{w})$
Weight-based model function with weights $\vec{w}$ $\lambda$ Regularization
term $\zeta(\cdot)$ Riemann zeta function $\mathrm{Zipf}_{z}(\cdot)$ Zipf
probability density function with parameter $z$ $rPST,\;rPLT$ Short- and long-
term playlist RNN $rHST,\;rHLT$ Short- and long-term user listening history
RNN $bWST,\;bWLT$ Short- and long-term weight-based model


# Throughput metrics and packet delay in TCP/IP networks

[Work in progress]

Andrei M. Sukhov

Timur Sultanov

Mikhail V. Strizhov

Samara State Aerospace University  Moskovskoe sh., 34  Samara, 443086, Russia
<EMAIL_ADDRESS>Samara State Aerospace University, Togliatti branch
Voskresenskaya st., 1  Togliatti, 445000, Russia<EMAIL_ADDRESS>Samara
State Aerospace University  Moskovskoe sh., 34  Samara, 443086, Russia
<EMAIL_ADDRESS>Alexey P. Platonov

Russian Institute for Public Networks  Kurchatova sq. 1  Moscow, 123182,
Russia<EMAIL_ADDRESS>
(20 April 2009)

###### Abstract

In the paper the method for estimation of throughput metrics like available
bandwidth and end-t-end capacity is supposed. This method is based on
measurement of network delay $D_{i}$ for packets of different sizes $W_{i}$.
The simple expression for available bandwidth
$B_{av}=(W_{2}-W_{1})/(D_{2}-D_{1})$ is substantiated. The number of
experiments on matching of the results received new and traditional methods is
spent. The received results testify to possibility of application of new
model.

###### category:

C.2.3 Computer-communication networks Network Operations

###### keywords:

network monitoring

###### category:

C.4 Performance of systems Measurement techniques

###### keywords:

new model for available bandwidth, end-to-end capacity, delay for packets of
different sizes, RIPE Test Box

††titlenote: corresponding author

##  1 Introduction

Measurement of throughput metrics like available bandwidth and capacity gives
a great chance to predict the end-to-end performance of applications, for
dynamic path selection and traffic engineering, and select among numbers of
differentiated classes of service. The throughput metric is an important
metric for several applications, such as grid, video and voice streaming,
overlay routing, p2p file transfers, server selection, and interdomain path
monitoring.

Various real-time applications in Internet, first of all, transmission audio
and video information become more and more popular, however for their
qualitative transmission high-speed networks are required. The major factors
defining quality of the service are: quality of the equipment (the codec and a
video server) and an available bandwidth of the channel. Providers and their
customers should provide a demanded available bandwidth for voice and video
applications to guarantee presence of demanded services in a global network.

In this paper we define a network path as the sequence of links that forward
packets from the path sender to the receiver. There are various definitions
for the throughput metrics, but we will adhere to the approaches accepted in a
series of papers by Dovrolis et al [5, 10, 18].

Two bandwidth metrics that are commonly associated with a path are the
capacity $C$ and the available bandwidth $B_{av}$. The capacity $C$ is the
maximum IP-layer throughput that the path can provide to a flow, when there is
no competing traffic load (cross traffic). The available bandwidth $B_{av}$,
on the other hand, is the maximum IP-layer throughput that the path can
provide to a flow, given the path’s current cross traffic load. The link with
the minimum transmission rate determines the capacity of the path, while the
link with the minimum unused capacity limits the available bandwidth.
Measuring available bandwidth is not only for knowing the network status, but
also to provide information to network applications on how to control their
outgoing traffic and fairly share the network bandwidth.

Another related throughput metric is the Bulk-Transfer-Capacity (BTC). The BTC
of a path in a certain time period is the throughput of a bulk TCP transfer,
when the transfer is only limited by the network resources and not by
limitations at the end-systems. The intuitive definition of BTC is the
expected long-term average data rate (bits per second) of a single ideal TCP
implementation over the path in question.

In order to measure different capacity metrics, the installation of special
utilities [12] is required at both ends of path. This is uncomfortable process
especially for usual Internet users who try to install modern network
applications like videoconference service.

For today also there are the various systems, allowing defining an available
bandwidth, but they have the disadvantages, therefore search of new solutions
is claimed. Among them, such as iperf, netperf, pathrate, pathload and abget,
and also a number of little-known programs ncs, netest, pipechar. We will
consider the cores from the above described products.

Each of the products set forth above has disadvantages. Utilities Iperf,
netperf, pathrate have one feature which is their essential disadvantage. To
estimate capacity of a network it is required to instal client and server
parts of the program. The utility abget demands HTTP a server on the remote
server and the privilege of the superuser, and as to programs ncs, netest,
pipechar so they are not adapted for operation with network screens that in
modern conditions does their a little used.

At the same time these programs use algorithms of an estimation of available
bandwidth, grounded on transmission the considerable quantity of packages on a
data link that reduces capacity of a network suffices and demands considerable
time.

In order to construct a perfect picture of a global network (monitoring and
bottlenecks troubleshooting) and develop the standards describing new
appendices, the modern measuring infrastructure should be installed. In Russia
different measurement projects are realized in the area of networking, for
example, PingER [16] in Institute of Theoretical and Experimental Physics
(ITEP), but full access to the collected data is limited for researchers.
Unfortunately, current measuring area do not reflect structure of the Russian
segment of a global network.

At present time powerful measurement system like RIPE Test Box is expanded
[7]. Unfortunately, this system doesn’t measure the available bandwidth, but
it collects the numerical values characterized the network heals like delay,
jitter, routing path, etc. This data allows us to investigate the basic
interdependencies of available bandwidth from basic network parameters. Our
aim is to estimate the available bandwidth from the delay value, received from
one point of path.

In our work we try to present the uniform model, allowing measuring all known
throughput metrics. Our method is based on testing of a network by packages of
the different size. Earlier such technique called Variable Packet Size (VPS)
was applied in work [6]. The VPS technique can estimate the capacity of a hop
$i$ based on the relation between the Round-Trip Time (RTT) up to hop $i$ and
the probing packet size $W$.

##  2 Model

The well-known expression for throughput metric describing a ratio between a
network delay and the packet size is a version of the Little’s Law [13].

$B=W/D$ (1)

Here $W$ is the size of transmitted packet and $D$ is the networking packet
delay. This formula is ideally for calculation of available bandwidth between
two network points that are connected immediately (in other words for
distantion in one hop). In general case the delay value is caused by such
constant network factors as propagation delay, transmission delay, per-packet
router processing time, etc [18].

In 1999 Downey [6] for the first time has detected linear dependence of the
minimum possible round trip time on the size of transferred packets. In 2004
precise experiments by Choi et al [2] proved that the minimum fixed delay
component for a packet of size $W$ is a linear (or precisely, an affine)
function of its size,

$D^{fixed}(W)=W\sum_{i=1}^{h}1/C_{i}+\sum_{i=1}^{h}\delta_{i}$ (2)

where $C_{i}$ is each link of capacity of $h$ hops and $\delta_{i}$ is
propagation delay. To validate this assumption, they check the minimum delay
of packets of the same size for three path, and plot the minimum delay against
the packet size.

Let $D(W)$ represents the point-to-point delay of a packet. Here we refer to
it as the minimum path transit time for the given packet size $W$, denoted by
$D^{fixed}(W)=\min D(W)$. With the fixed delay component $D^{fixed}(W)$
identified, we can now substract it from the point-to-point delay of each
packet to study the variable delay component $d^{var}$. The variable delay
component of the packet, $d^{var}$, is given by

$D(W)=D^{fixed}(W)+d^{var}$ (3)

Figure 1: Packet Size vs Delay

On the Fig. 1 the graphic shows the linear dependence between average network
delay $D_{av}(W)=\mathbb{E}[D(W)]$ and packet size $W$ like it is constructed
in paper [2]. Slope angle concerning $Y$ axe could be considered as available
bandwidth $B_{av}$ in contrast to bottleneck capacity $C$ (maximum throughput)
for computed minimal delay $D^{fixed}(W)$:

$D^{fixed}(W)=D_{min}+W/C,$ (4)

where

$D_{min}=\lim_{W\rightarrow 0}D^{fixed}(W)$ (5)

Prolongation of line $D(W)$ from Fig. 1 to $Y$ axe gives the intercept value
$a=\sum_{i=1}^{h}\delta_{i}$. Then the Equation (1) for the throughput metric
which path consists of two or more hops should be modernized to the following
view:

$B_{av}=W/(D_{av}-a)$ (6)

The value $a$ is related to the distance between the sites (i.e. propagation
delay) and per-packet router processing time at each hop along the path
between the sites [3, 4]. This value represents as the minimum delay $D_{min}$
for which the very small package can be transmitted on a network from one
point in another. In the general case $a(n,l)$ could be considered as the
linear function depended on $n$ and $l$,

$a=f(n,l)\approx\alpha n+\beta l$ (7)

where $n$ is the number of hops (routers) that is measured by the traceroute
utility and $l=\sum_{n}l_{n}$ is the sum of single length of routing path.

The Equation (6) gives us the simple way for estimation of throughput metrics
including active bandwidth $B_{av}$ and capacity $C$. Our method supposes the
variation of packet size on the same path for measurement of the throughput
metrics. If the testing process between two fixed points is organized by
packets with different sizes $W_{1}$ and $W_{2}$ then the delay times $D_{i}$
get two different values. Experiments should show the identical value for
available bandwidth $B_{av}$ independently from packet size $W_{i}$. The
system from two equations with different values of variables
$D_{i}=\mathbb{E}[D(W_{i})]$ and $W_{i}$ is easy solved to find $B_{av}$ and
$a$:

$B_{av}=\frac{W_{2}-W_{1}}{D_{2}-D_{1}}$ (8)

It should be noted that similar result was first time received for bandwidth-
dominated path in classical paper of Jacobson [9] dedicated congestion and
avoidance control.

Fig. 2 illustrates a schematic representation of transfer of packages of the
different sizes on the slowest link in the path (the bottleneck). The vertical
dimension is bandwidth, the horizontal dimension is time.

Another result for capacity $C$ will turn out, if instead of the average value
$D_{av}(W)$ in an analogue of the equation (6)

$C=\frac{W}{D^{fixed}(W)-D_{min}}$ (9)

the minimum fixed delay component $D^{fixed}(W)$ is used

$C=\frac{W_{2}-W_{1}}{D^{fixed}(W_{2})-D^{fixed}(W_{1})}$ (10)

Figure 2: Available Bandwidth Illustration

It is necessary to notice that experimental definition of any throughput
metrics demands carrying out of several measurements for a network delay.
After these measurements are spent for packages of the different sizes, it is
necessary to choose from them the minimum and average values. The minimum
value will be used for calculation of available bandwidth $B_{av}$, and
average value for capacity $C$. Even in work of Downey [6] it was noticed that
are many data points near the minimum and we can find the minimum delay
$D_{min}$ with a small number of probes at each packet size. It should be
noted that the method presented in given work allows measuring the available
bandwidth and capacity of the outgoing channel.

The minimal delay of datagram transmission $D_{min}$ may be calculated as

$D_{min}=\frac{W_{2}D_{1}-W_{1}D_{2}}{W_{2}-W_{1}}$ (11)

This value as well as the methods of its measurement has a important
significance in applied tasks of control theory [19]. The second significant
question of networking control theory is the distribution type for variable
delay component $d^{var}$ which should be studied. To know the expression for
this parameter we may easy calculate the duration of buffer for streaming
aplication on receiving side.

##  3 Precise Experiments

A number of measurements in a global network have been spent for
acknowledgement of our method. In this work the very first results which are
already processed are presented only.

For practical realization of our method the sizes $W_{1}$ and $W_{2}$ should
different in several times, it is reasonable to choose 64 and 1064 bytes for
Linux based systems, 32 and 1032 bytes for Windows correspondingly. The basic
problem of experimental testing is the precise of delay measurements that is
necessary for accurate result. The exact metering demands micro second
precision for delay measurements; we are reaching such accuracy with help of
RIPE Test Box mechanism [17]. In order to prepare the experiments three Test
Boxes have been installed in Moscow, Samara and Rostov on Don during 2006-2008
years in framework of RFBR grant 06-07-89074. Each RIPE Test Box represents a
server under management of an FreeBSD operating system with the GPS receiver
connected to it.

Characteristic times of investigated processes (a packet delay, jitter) have
the order from 10 $ms$ to 1 $sec$, therefore is quite enough accuracy of
system hours of a RIPE Test Box for their reliable measurement. At the first
stage experiment between tt01.ripe.net (RIPE NCC at AMS-IX, Amsterdam) and
tt143.ripe.net (Samara, SSAU) have been made which included

  * •

Precision measurement of packet delay in the size 100 and 1100 bytes with
accuracy 2-12 $\mu s$

  * •

Measurement of available bandwidth by means of utility iperf [12]

  * •

Measurement of bandwidth by a method of downloading of a file on FTP

Thus, at us it will be generated alternatively measured three sizes of
throughput metrics for the subsequent comparative analysis.

It is necessary to notice that the utility iperf is started with an option -u
and measures speed of a stream between two points that precisely enough
corresponds to available bandwidth. Speed of downloading on ftp measures a
Bulk-Transfer-Capacity (BTC) and gives strongly underestimated value.
Unfortunately, at the given stage we could not spend more exact measurements,
but further we assume to find partners for installation of exact utilities.

The design of the RIPE TTM system meets all requirements shown by our method,
namely it allows to change the size of a testing package and to find network
delay with a split-hair accuracy.

By default, testing is conducted by packages in the size of 100 byte, but
there is a page corresponding to point of the menu Configuration of local Test
Box. On which it is possible to add testing packages to RIPE Box up to 1500
byte in size with demanded frequency.

In our case it is reasonable to add testing 1100 (1024) byte packages with
frequency of 60 times in a minute. It is necessary to notice that the results
of tests will be available on next day.

Testing results are available in telnet to RIPE Test Box on port 9142. It is
important to come and write down simultaneously the data on both ends of the
investigated channel, in the case presented here it is tt01.ripe.net and
tt143.ripe.net. Obtained data will contain required delay of packages of the
different sizes. Also, we need to distinguish packages.

Therefore at first it is reversible to sending Box and we will find lines, see
Table 1.

SNDP | 9 | 1240234684 | -h | tt01.ripe.net | -p | 6000 | -n | 1024 | -s | 1039148464
---|---|---|---|---|---|---|---|---|---|---
SNDP | 9 | 1240234685 | -h | tt164.ripe.net | -p | 6000 | -n | 100 | -s | 1039148548
SNDP | 9 | 1240234685 | -h | tt01.ripe.net | -p | 6000 | -n | 100 | -s | 1039148557
Table 1: The data of sending box

Last value in string is sequence number of the packet. It is necessary to us
to find this number on the receiving side at the channel. The string example
on the receiving side is lower resulted, see Table 2.

RCDP 12 2 89.186.245.200 60322 193.0.0.228 6000 | 1240234684.785799 | 0.044084 0X2107 0X2107 1039148464 0.000002 0.000008
---|---|---
RCDP 12 2 89.186.245.200 53571 193.0.0.228 6000 | 1240234685.788367 | 0.043591 0X2107 0X2107 1039148557 0.000002 0.000008
Table 2: The data of receivig box

For set number of a package it is easy to find network delay, in our case it
makes 0.044084 seconds. The following package 1039148557 has the size of 100
bytes and its delay makes 0.043591 seconds. Thus, the difference will make
0.000493 second.

Our model assumes operations with minimal and average values; therefore we
should note average values, not less than five pairs for the delay, going
consistently. In our case, average difference
$\mathbb{E}[D(1024)-\mathbb{E}[D(100)$ is 0.000571 seconds. (tt143 -> tt01).
Then the required bandwidth of the link (tt143 -> tt01) can be calculated as

$B_{av}(tt143\rightarrow tt01)=\frac{924\times 8}{0.000571}=12.9[Mbps]$ (12)

The minimal and average values of the return link (tt01 -> tt143) are
$\mathbb{E}[D(1024)]-\mathbb{E}[D(100)]=0.000511$ second and
$D^{fixed}(1024)-D^{fixed}(100)=0.000492$ second/ Then available bandwidth and
capacity can be calculated as

$\displaystyle C(tt01\rightarrow tt143)=\frac{924\times
8}{0.000492}=15.0[Mbps]$ (13) $\displaystyle B_{av}(tt01\rightarrow
tt143)=\frac{924\times 8}{0.000511}=14.7[Mbps]$ (14)

The main problem of the offered method consists in understanding, what value
is measured. Actually, it can be bulk transport capacity or available
bandwidth. Alternative measurements of the given values are necessary for
specification.

It is ideal to compare the width received by our method to the values measured
by alternative methods, first of all by means of the utility iperf.
Unfortunately, such tests are not spent yet, we allocate only in the speed of
FTP downloading. It makes 3.04 - 3.20 Mbps in a direction from tt143.ripe.net
to tt01.ripe.net and 3.2-3.3 Mbps in the opposite direction. That is
additional researches for which carrying out partners are required are
necessary.

It should be noted that Table II from paper [2] gives us these values;
calculated slope is inverse value to end-to-end capacity. The corresponding
capacities for data set 1, 2, 3 (path 1 and 2) are 285 Mbps, 128 Mbps, 222
Mbps and 205 Mbps.

##  4 AvBand Utility

Routinely the special utilities could be used for delay measurements; we tried
to test traditional ping, the new UDPping and other utility. In result of test
the simplest utility ping was found to be a best choice for delay
measurements.

Utility AvBand (Available Bandwidth) has been developed, realizing the above
described method, using in the basis algorithm ping. This algorithm has been
developed by Mike Muus in 1983 in the USA for operating system BSD [14]. Its
advantage consists that it is possible to work with any router or the host
which responds to packages of inquiries ICMP Echo. The given version of the
utility is developed for platform Windows and uses library ICMP Windows API.
In the near future we plan working out of the utility for Unix systems, first
of all for family Linux.

The given utility defines available bandwidth of outgoing channel between host
from which measurement and a remote server interesting us is spent. For this
purpose the program measures RTT (Round Trip Time) that is the time between
sending of inquiry and answer reception. Thus at first packages in 32 bytes
(standard Windows size) are generated and their RTT is defined, and the
following step forms packages of the size in 1032 bytes and is measured their
RTT. On Fig. 3 the screenshot of the program is presented.

Figure 3: The AvBand Screenshot

In the field “Host” it is entered a host name, available bandwidth to which we
are going to measure. In the field “Retries” the quantity of the echo-
inquiries which will be sent on a remote host is underlined. After that enough
to press button“Start” and the utility will send the set quantity of packages
of the size of 32 bytes, further the same quantity of packages in the size of
1032 bytes. The collected values of the received delays on each of groups of
packages are averaged, and then by means of our model the available bandwidth
of the channel pays off and is displayed. It is necessary to notice that the
available bandwidth of the outgoing channel is measured.

Hosts | Available bandwidth
---|---
testing | remote |  ping or | FTP | Iperf
server | host | AvBand |  |
SSAU | IOC RAS | 20-20.6 | 17.6-27.4 |
|  | Mbps | Mbps |
SSAU | server2.hosting.reg.ru | 1150 | 1140 |
|  | Kbps | Kbps |
OSU | SSAU | 2500 |  | 2450
|  | Kbps |  | Kbps
AIST | SSAU | 536 | 600 | 659
|  | Kbps | Kbps | Kbps
Infolada | SSAU | 346 | 374 |
|  | Kbps | Kbps |
VolgaTelecom | SSAU | 274 |  | 283
|  | Kbps |  | Kbps
Table 3: Experimental results

For check of utility AvBand a series of experiences with use of following
measuring mechanisms also has been spent:

  * •

Utility AvBand

  * •

Standard ping

  * •

Iperf

  * •

FTP

Measurements with Samara State Aerospace University (SSAU), Institute of
Organic Chemistry of the Russian Academy of Sciences (IOC RAS), control centre
RIPE in Amsterdam (RIPE), Ohio State University (OSU), and also a number of
local experiments with use of networks of various Internet Service Providers
of the Samara region (Infolada, AIST, VolgaTelecom, etc.) have been currently
spent. All data on experiments is resulted in the table more low.

As a case in point ADSL connection in Samara region could be chosen for
illustration of our approach. The delay measurements give $D_{1}=18$ $ms$,
$D_{2}=42$ $ms$, that corresponds to 350 Kbps of available bandwidth. During
FTP session the delay grows to 300 ms and 425 ms that corresponds
approximately to 60 Kbps of available bandwidth. This is very rough
computation, but it could be made quickly and independently.

##  5 Conclusion

Now measurements are not completed yet, is planned to type the data from not
less than 50 points scattered on territory of a planet. From these
measurements not less than 10 should be fulfilled with application of RIPE
Test Boxes. Thus, summing up to the done operation, it is possible to draw the
main output: the theoretical model of calculation of an available bandwidth
proves to be true.

Further it is planned to continue researches to establish type of distribution
for a network delay. At definition of type of distribution it is supposed to
use analogy to molecular physics, namely about distribution of molecules in
the speeds Maxswell. Probably, in our case required distribution should be
presented in the form of product of normally (Gaussian) distribution and the
inverse function defined by the Equation 6. The knowledge of density of
distribution in TCP/IP networks will help to find a new class the decision in
the networked control systems.

In summary we would like to express special gratitude of Prasad Calyam and
Gregg Trueb from Ohio State University for the invaluable help at carrying out
of measurements. Also it would be desirable to thank all collective of
technical service RIPE ncc and especially Ruben van Staveren and Roman
Kalyakin for constant assistance in comprehension of subtleties of a measuring
infrastructure.

## References

  * [1] Ben Fredj, S., Bonald, T., Proutiere, A., Regnie, G., Roberts, J.: Statistical Bandwidth Sharing: A Study of Congestion at Flow Level. In: ACM SIGCOMM (2001)
  * [2] Choi, B.-Y., Moon, S., Zhang, Z.-L., Papagiannaki, K. and Diot, C.: Analysis of Point-To-Point Packet Delay In an Operational Network. In: Infocom 2004, Hong Kong, pp. 1797-1807 (2004)
  * [3] Cottrell, L., Matthews, W. and Logg C.: Tutorial on Internet Monitoring $\&$ PingER at SLAC. http://www.slac.stanford.edu/comp/net/wan-mon/tutorial.html
  * [4] Crovella, M.E. and Carter, R.L.: Dynamic Server Selection in the Internet. In: Proc. of the Third IEEE Workshop on the Architecture and Implementation of High Performance Communication Subsystems (1995)
  * [5] Dovrolis C., Ramanathan P., and Moore D., Packet-Dispersion Techniques and a Capacity-Estimation Methodology, IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 12, NO. 6, DECEMBER 2004, p. 963-977
  * [6] Downey A.B., Using Pathchar to estimate internet link characteristics, in Proc. ACM SICCOMM, Sept. 1999, pp. 222 223.
  * [7] Georgatos, F., Gruber, F., Karrenberg, D., Santcroos, M., Susanj, A., Uijterwaal, H. and Wilhelm R., Providing active measurements as a regular service for ISP’s. In: PAM2001
  * [8] Guojun, J.: Available Bandwidth Measurement and Sampling, http://www.caida.org/workshops/isma/0312/abstracts/guojun.pdf
  * [9] Jacobson, V. Congestion avoidance and control. In Proceedings of SIGCOMM 88 (Stanford, CA, Aug. 1988), ACM
  * [10] Jain, M., Dovrolis, K.: End-to-end Estimation of the Available Bandwidth Variation Range. In: SIGMETRICS’05, Banff, Alberta, Canada (2005)
  * [11] H.323 Beacon Tool, http://www.osc.edu/networking/itecohio.net/beacon/
  * [12] Iperf, dast.nlanr.net/Projects/Iperf/
  * [13] Kleinrock, L. Queueing Systems, vol. II. John Wiley & Sons, 1976.
  * [14] Mike Muus, Ping documentation, http://ftp.arl.mil/ mike/ping.html
  * [15] Padhye, J., Firoiu, V., Towsley, D., Kurose, J.: Modeling TCP Throughput: A Simple Model and its Empirical Validation. In: Proc. SIGCOMM Symp. Communications Architectures and Protocols, pp. 304-314 (1998)
  * [16] PingER, http://www-iepm.slac.stanford.edu/pinger/
  * [17] Ripe Test Box, http://ripe.net/projects/ttm/
  * [18] Prasad R.S., Dovrolis C., and B. A. Mah B.A., The effect of layer-2 storeand-forward devices on per-hop capacity estimation, in Proc. IEEE INFOCOM, Mar. 2003, pp. 2090 2100.
  * [19] Zhang, W., Branicky, M.S., Phillips S.M.: Stability of Networked Control Systems. In: IEEE Control System Magazine, 21(1), pp. 84-99 (2001)