Deep Item-based Collaborative Filtering for Sparse Implicit Feedback
Daniel A. Galron Yuri M. Brovman Jin Chung Michal Wieja Paul Wang












  eBay Inc.
  
  New York 
  New York 
  10011

dgalron@ebay.com



  eBay Inc.
  
  New York 
  New York 
  10011

ybrovman@ebay.com



  eBay Inc.
  
  New York 
  New York 
  10011

jinchung@ebay.com



  eBay Inc.
  New York
  New York
  10011

michal.wieja@gmail.com



  eBay Inc.
  
  New York 
  New York 
  10011

pauwang@ebay.com









Recommender systems are ubiquitous in the domain of e-commerce, used to improve the
user experience and to market inventory, thereby increasing revenue for the site.  Techniques such
as item-based collaborative filtering are used to model users' behavioral interactions with items
and make recommendations from items that have similar behavioral patterns.  However, there are
challenges when applying these techniques on extremely sparse and volatile datasets.  On some
e-commerce sites, such as , the volatile inventory and minimal structured information about
items make it very difficult to aggregate user interactions with an item. In this work, we describe
a novel deep learning-based method to address the challenges.
We propose an objective function that optimizes a similarity measure
between binary implicit feedback vectors between two items.  We demonstrate formally and empirically
that a model trained to optimize this function estimates the log of the cosine similarity between
the feedback vectors.  We also propose a neural network architecture optimized on this objective.
We present the results of experiments
comparing the output of the neural network with traditional item-based collaborative filtering
models on an implicit-feedback dataset, as well as results of experiments comparing different neural
network architectures on user purchase behavior on .  Finally, we discuss the results of an
A/B test that show marked improvement of the proposed technique over 's existing
collaborative filtering recommender system.









<ccs2012>
<concept>
<concept_id>10002951.10003317.10003347.10003350</concept_id>
<concept_desc>Information systems 
Recommender systems</concept_desc>
<concept_significance>500</concept_significance>2
</concept>
<concept>
<concept_id>10002951.10003260.10003261.10003269</concept_id>
<concept_desc>Information systems Collaborative filtering</concept_desc>
<concept_significance>300</concept_significance>
</concept>
<concept> 
<concept_id>10010147.10010257.10010258.10010259.10010263</concept_id>
<concept_desc>Computing methodologies Supervised learning by classification</concept_desc>
<concept_significance>300</concept_significance>
</concept>
</ccs2012>


[500]Information systems Recommender systems
[300]Information systems Collaborative filtering
[300]Computing methodologies Supervised learning by classification




Deep Item-based Collaborative Filtering for Sparse Implicit Feedback
    Paul Wang
    Received: date / Accepted: date
====================================================================





§ INTRODUCTION

Recommender systems have become an integral part of many online services, improving their users' experience by exposing them to content they may find relevant but of which they are not yet aware.  On e-commerce sites, recommender systems are utilized to help buyers quickly filter through potentially enormous inventories to allow them to easily find items they would like to purchase.  These systems do so by constructing models of user behavior that are used to predict whether a user is likely to engage with an item.

Two widely used techniques for modeling user affinity for items are content-based filtering and collaborative filtering.  In content-based filtering, the items to be recommended are represented by characteristic features of the entities.  These may include textual features (e.g. structured tags describing the items) <cit.>, learned image representations <cit.>, and audio signals <cit.>.  Users' preference for characteristic features are then modeled as a user profile, and at the recommendation stage, items whose content matches a user's profile are then surfaced to the user. 

In collaborative filtering (CF) methods, recommendations are made by aggregating many users' preferences for items, and then using the aggregated preferences to make predictions for individual users.  A common method for doing so, popularized by <cit.>, is item-based collaborative filtering.  In item-based CF, items are represented by vectors indicating each user's preference for that item.  These preferences might be explicit (e.g., a rating of 1-5 indicating the degree of a user's preference), or implicit (e.g., a binary vector indicating whether a user has purchased an item or not).  A similarity measure, such as cosine similarity or the Pearson correlation coefficient is used to measure the similarity of user preferences between the items.  To provide the top-N recommendations for a user, the similarity measure of user preferences between items is used to find the N most similar items to those for which a given user has already expressed a preference.  
This results in an N-best list of items that a user has not yet engaged with, that have similar aggregate user preferences to those items that the user has engaged with.

While having shown superior performance to content-based methods, there can be challenges in applying collaborative filtering methods.  First, they have difficulty when modeling sparse user preference data.  An item must have a sufficient number of user interactions before it can be meaningfully compared with other items.  For item-based CF in particular, the general assumption is that there are more users than items.  The problem of sparsity can lead to the cold-start problem, where items new to the system cannot be used for recommendation.  Model-based approaches to collaborative filtering (e.g. <cit.>) oftentimes help recommendation quality on sparse datasets by learning latent representations of items only on the existing rating, while ignoring the missing data.  However, these systems still suffer from the cold-start problem, and while they are better at handling sparse data than item-based CF, there still need to be a sufficient number of ratings for an item.



While effective for e-commerce sites with fixed inventory and large user bases, the challenges suffered by item-based and model-based CF approaches can limit their applications in several recommendation settings.  At some e-commerce sites, like , the inventory consists of approximately one billion live listings at any given time, with 160 million active users.  Much of the inventory is volatile – most items are live on site for a few weeks before they are purchased.  Furthermore, over half of the live listings are single quantity, that is, they can be purchased by at most one buyer, making the implicit user preference data (i.e., clicks and purchases) extremely sparse.  With millions of items listed daily, the cold start problem affects a substantial portion of the inventory.

Although most listings are single quantity, oftentimes they have content descriptions and metadata that may allow us to map listings to static entities, where the listings that map to a single static entity are deemed to be equivalent.  If, for example, a listing's seller provides a UPC or other manufacturer's identifier, we can map the item to a unique product ID associated with the identifier.  Item-based CF can then be applied on the product IDs to find products with similar user purchase patterns.  While this technique is effective for the top 20% most popular purchased products on , the implicit user preferences on the product ID level are still very sparse.  Due to the heavy-tailed nature of the distribution of purchases, recommendation quality (as evaluated by user judgment and operational metrics) on the remaining 80% of user-purchased products is low.  For the remaining listings, we can map them to other types of static entities and perform CF on them.  For example, we can use sets of aspects, or key-value properties of items, to construct static entities, and assign listings to the entity corresponding to the set of aspects for that listing.  While the static entities constructed in this manner are very granular, and one can have a high degree of confidence that the listings that fall within an entity are equivalent items, the resulting behavioral signal is still too sparse.  The majority of entities constructed in this manner still only have one purchase for each static entity.  One can reduce the granularity of the static entities, by selecting subsets of aspects or single aspects for constructing entities.  While this approach causes the purchase signal to be more dense, it comes at the expense of the specificity of the static entities; not all items within a static entity are truly equivalent.  Another approach is to cluster listings based on the titles, and use CF on the clusters.  However, applying clustering to 's data is a challenge, both because of the scale and the need to tune the granularity of the clusters appropriately for the collaborative filtering objective.

The primary challenge in all these approaches is that the mapping of listings to static entities must be constructed to optimize the recommendation quality.  The technique of constructing static entities first and then performing CF on the entities makes it difficult because the construction phase is removed from the measure of recommendation quality.  Constructing static entities can be very time consuming, and it is often not feasible to try all combinations of aspects or item clustering hyper-parameters and evaluate recommendation quality for each entity.  Instead, in this work we propose an end-to-end method that jointly learns representations of listings and uses them to predict a similarity measure of user preferences on items.  The representations, which are based on embeddings of the content features of the listings, can be thought of as mapping items to implicit entities, and estimating the user preference similarity between items based on the representations.  Formally, this model takes the form of a smooth function h: (ϕ(s), ϕ(r)) →sim(s, r) that embeds a seed item s (e.g. a recently purchased item) and a recommendation candidate r into a latent continuous-valued vector space based on their content features ϕ.  The function h estimates a proxy for the cosine similarity between the implicit user preference vectors between representations ϕ(s) and ϕ(r). 

The primary contributions of this work are:

	
  * An objective function whose optimal value is a monotonic transformation of the cosine similarity of implicit feedback vectors of two items
	
  * A neural network architecture that embeds items into a real-valued vector space based on their content features, and optimizes the latent vectors on the cosine similarity objective
	
  * A quantitative evaluation of the effectiveness of the objective function and the neural network architecture


The rest of the paper is organized as follows: in Section <ref> we describe our objective function, demonstrate that it optimizes the cosine similarity of implicit feedback vectors, and present a Monte Carlo method for optimizing the function; Section <ref> presents our neural network architecture and some variants that allow us to learn a latent representation of items; in Section <ref> we present some related work on applying neural networks for recommendation system and information retrieval tasks; in Section <ref> we present empirical evaluations of our objective function and neural network architecture, including empirical evidence that the objective function in Section <ref> converges to the cosine similarity; Section <ref> describes some qualitative properties of the learned latent item representations; and in Section <ref> we describe some open questions and on-going work.






	
	
	

	
	

	
	
	
	
	
	



§ OBJECTIVE FUNCTION

We consider a common technique for item-based collaborative filtering <cit.>.  First, a model is built that captures the similarity of implicit feedback between the entities to be recommended.  Then, the model is applied to generate the top-N recommendations for an active user or for a seed item.  One common method of capturing the similarity is by computing the pair-wise cosine similarity of implicit feedback vectors.
Consider two items s and r.  Let s⃗ and r⃗ be vectors of dimensionality |U|, where U is the set of users in the system. s⃗ and r⃗ are vectors of user feedback.  A common way of measuring behavioral similarity is by computing the cosine similarity between these two vectors:

    sim(s⃗,r⃗) = cos(s⃗, r⃗) =
    ∑_i=1^|U| s_i · r_i√(∑_i=1^|U|s_i^2)·√(∑_i=1^|U|r_i^2)

In the case where the user feedback is implicit, and the vectors s⃗ and r⃗ are represented as bit vectors, the cosine similarity is equivalent to the Ochiai coefficient:

    cos(s⃗, r⃗) =
    ∑_i 1_s_i ∧ r_i√(∑_i s_i)·√(∑_i r_i)

Our goal is to learn a function that can estimate the cosine similarity between the implicit feedback vectors of items, based on content properties of those items. 

First, we define some of our notation.  Let ℐ denote the set of all items, t ∈ℐ.  Our training set consists of two sets: a set of item pair co-purchase transactions (s_j, r_j) ∈ CP, and a set of purchased items t_j ∈ D. The set CP represents the set of transaction pairs (s_j, r_j), where each pair represents an event where the same user j purchased both items s ∈ℐ, r ∈ℐ. Similarly, let the set D represent the set of transactions t_j ∈ D, which is the event that a user j purchased an item t ∈ℐ. Without loss of generality, assume each user will purchase an item t ∈ℐ, or a pair of items (s, r) ∈ℐ×ℐ no more than once.  We define the number of times a pair of items (s, r) ∈ℐ×ℐ has been purchased by the same user as

    (s, r) = ∑_(x,y) ∈ CP(1_x=s ∧ y=r)

The total number of co-purchased pairs is then given by |CP| = ∑_s,r((s,r)).  Similarly, the number of times an item t ∈ℐ has been purchased is given by 

    (t) = ∑_x ∈ D(1_x=t)

and the total number of purchases |D| is given by |D| = ∑_s((s)).

Let h(s, r) be a be a parameterized function (i.e. a model) that estimates the cosine similarity of implicit feedback of items s, r ∈ℐ.  Given a training set of co-purchased item pairs and purchased items 𝒯 = (CP, D), we define the following cost function over the training set:

    ℓ = ∑_(s, r) ∈ CP   (s, r) logσ(h(s, r)) 
        + ∑_s' ∈ℐ∑_r' ∈ℐ[ √((s'))√((r'))log[1 - σ(h(s', r')) ] ]

where σ is the sigmoid function

    σ(x) = 11 + e^-x

Note that Equation <ref> is the well-known binary cross-entropy loss applied to 𝒯 with a particular distribution of positive and negative labels.  This loss function resembles negative sampling approaches used in word2vec and in other approaches to recommendation, such as <cit.>.

We demonstrate that the value of h(s, r) that minimizes this cost function for a given pair (s, r) is the log of the cosine similarity expressed in Equation <ref>.  Assuming the capacity of the model h is large enough to allow exact prediction on (s, r) without deviation from the optimum, each h(s, r) can assume a value independently of other (s, r) pairs.
Decomposing the loss and calculating it on a single pair of items (s, r), we get the following function for a pair:

    ℓ(s, r) = (s, r) logσ(h(s, r)) + √((s))√((r))logσ(-h(s, r))

Note that for convenience, here we use the fact that 1 - σ(x) = σ(-x).  To find the value of h(s,r) that optimizes Equation <ref>, we take the partial derivative of ℓ(s, r) with respect to h(s,r):

    ∂ℓ(s,r)/∂ h(s,r) =  (s, r) σ(-h(s,r)) - √((s))√((r))σ(h(s,r))

Setting this equal to 0 and solving for h(s, r), we get

    0 = (s, r) σ(-h(s,r)) - √((s))√((r))σ(h(s,r)) 
    ⇒    0 = (s, r) 1/1 + e^h(s,r) - √((s))√((r))1/1 + e^-h(s,r)
    ⇒   (s, r)1/1 + e^h(s,r) = √((s))√((r))1/1 + e^-h(s,r)
    ⇒   (s,r)/√((s))√((r)) = 1+e^h(s,r)/1+e^-h(s,r)

Using the fact that 1+e^x/1+e^-x = e^x, we find that the value of h(s,r) that minimizes Equation <ref> is

    h(s,r) = log[(s, r)/√((s))√((r))]

This is the log of Equation <ref>.  We will validate this result empirically in Section <ref>.

Oftentimes, the cardinality of the set ℐ×ℐ is too large to be able to explicitly enumerate.  As an alternative to optimizing Equation <ref>, we can optimize a Monte Carlo estimate.  We can define the normalization factor 𝒵≡∑_t∈ℐ√((t)).  Let k_CP be the number of co-purchased item pairs we sample according to the distribution (s,r) = (s,r)/|CP|.  Let k_s be the number of seed items we sample as negative examples according to the distribution (s) = √((s))/𝒵, and let k_r be the number of candidate items we sample as negative examples for each negative seed item according to the distribution (r). Note that we draw s and r independently from the distribution .  We can then define the Monte Carlo estimate of the cost function in Equation <ref> as

    ℓ_MC =    𝔼_(s, r) ∼[k_CP·logσ(h(s, r))] 
       + 𝔼_s' ∼𝔼_r' ∼[k_s · k_r ·logσ(-h(s', r'))]

We explicitly express the expectations as follows:

    ℓ_MC =    ∑_(s,r) ∈ CP[(s,r)/|CP|· k_CP·logσ(h(s,r))] 
        + ∑_s' ∈ℐ∑_r' ∈ℐ[√((s'))/𝒵·√((r'))/𝒵· k_s · k_r ·logσ(-h(s', r'))]

Then, for a specific pair of items (s, r):

    ℓ_MC(s, r) =    (s, r) ·k_CP/|CP|·logσ(h(s, r)) 
        + √((s))·√((r))·k_s/𝒵·k_r/𝒵·logσ(-h(s, r))

Using the same methods we used to derive Equation <ref> above, we can compute the derivative of ℓ_MC(s,r) with respect to h(s,r) and solve for h(s,r):

    ∂ℓ_MC(s, r)/∂ h(s,r) =    (s, r) ·k_CP/|CP|·σ(-h(s,r)) 
        - √((s))·√((r))·k_s · k_r/𝒵^2·σ(h(s,r))

Solving this for h(s, r) gives us

    h(s,r) = log[(s, r)/√((s))√((r))] + log[k_CP/k_s· k_r] + log[𝒵^2/|CP|]


Equation <ref> indicates that the output of the model h(s,r) that optimizes the cost function in Equation <ref> is the cosine similarity shifted by a constant proportional to the ratio of the sampling mixture of positive and negative examples, and the ratio of the number of co-purchases in the training set and the number of purchases.  In Section <ref>, we empirically demonstrate the effects of different sampling ratios k_CP / k_s · k_r.



§ MODEL ARCHITECTURES

In this section, we describe two neural network architectures that we experiment with.  These architectures define the function h(s,r) whose cost function in Section <ref> we optimize.  The networks take two items as input, encoded as sparse feature vectors.  The neural network architecture can be decomposed into three sub-networks - one that computes a representation of item s, one that computes a representation of item r, and one that makes a prediction based on the embeddings of items s and r.  We first describe the architecture of the sub-networks responsible for constructing embeddings for items s and r, and then discuss how we combine the two embeddings to make a prediction.



 §.§ Item Embedding Network


For each item t ∈ℐ, we assume we have k sets of tokens associated with item t.  One set of tokens might be a title of an item t; another set might consist of aspect tokens; another might consist of category information; etc.  We make no a-priori assumptions about the nature of the features in each set, other than a constraint that they are text tokens.  We denote each set as t_k, and a token index i in the set t_k as t_ki.  Note that each item s, r ∈ℐ that serve as input to h might have separate sets of token features s_k, r_k.

Inspired by work on word embeddings <cit.>, we first embed each token into a lookup table, where we define a separate lookup table for each set of tokens t_k.  A pooling layer then aggregates together the embedding vectors for each token t_ki present in an item t for each set t_k, yielding an embedding for each t_k.  The aggregated vectors are then concatenated together for each t, and fed through a non-linear activation function.  We then use a feed-forward layer to combine information between the different pooled vectors t_k, and finally pass the resulting vector through a non-linear activation function.  A schematic of this approach, using a mean-pooling mechanism to pool together the token embeddings, can be seen in Figure <ref>.  Note that in this work, we use tanh as the activation function.  We experimented with ReLU activations as well, but found that they gave similar performance to tanh.


The choice of vector pooling mechanism can depend on the nature of the set t_k.  We experiment with two methods.  When we have non-sequential text features, such as tags or aspects, we apply an element-wise mean pooling layer for the vectors associated with each token t_ki.  When we have sequential text features, such as titles, where the order of tokens may be relevant, we experiment with a few options – treating each sequence as a bag of words and applying element-wise mean pooling; or applying a recurrent neural network (RNN) to learn a representation of the title.  We refer to the mean-pooling architecture as DCF-Mean (where DCF is an abbreviation for deep collaborative filtering), and the RNN architecture as DCF-RNN.  When applying a recurrent neural network to aggregate the tokens in a text sequence, we treat the RNN as an encoder <cit.> and use the hidden state of the last time step as the embedding of the token sequence.  The end-to-end neural network shown in Figure <ref> shows the DCF-RNN variant of the item embedders.  In Section <ref>, we present results on both approaches.



 §.§ Prediction Network

The component of the neural network that takes the embeddings of the two items and outputs an estimate of a similarity measure is shown in Figure <ref>.  This part of the network concatenates the latent vector representations of items s and r, applies a fully-connected hidden layer to the concatenated vectors, applies a non-linear activation function, and finally outputs a scalar value.  The dimensionality of the token embeddings, RNN hidden state, and fully-connected layers are all hyper-parameters that must be tuned.  Note that the end-to-end architecture can be designed to be symmetric or asymmetric – one can tie the parameters of the two subnetworks that embed the items s and r so that they have the same values.  Similarly, one can tie the parameters of the two halves of the matrix corresponding to the hidden layer that combines the item embeddings.




§ RELATED WORKS


Hybrid Recommender Systems   There have been many works on incorporating content into collaborative filtering approaches.  These hybrid recommender systems (refer to <cit.> for a survey of the subject) use additional metadata features to augment implicit and explicit feedback signals on items.  Basilico & Hofmann <cit.> propose a kernel-based method that constructs feature maps of users and items, and then use perceptron learning to optimize the kernels.  Melville et al. <cit.> propose a method that, given a sparse user-item explicit feedback matrix, first imputes the missing ratings using a content-based recommender system, and then performs collaborative filtering using this imputed matrix.  Li & Kim <cit.> first cluster items based on content features to create an item group matrix, and then perform collaborative filtering on the item groups, finally applying a linear combination of the results of item-based and group-based CF. Popescul et al. <cit.> describe a generative probabilistic model that models a three-way co-occurrence between users, items, and item content.  This model estimates the parameters of a latent variable based on the users, that the items and content are then conditioned on.  Our approach is similar in spirit to these works.  All these works implicitly or explicitly map items or users to representations that encode information on their content, and perform collaborative filtering on these representations.  Our approach falls within this same setting, in that we learn latent representations of items based on their content features, and then condition our predictions of the distribution of co-purchases on these latent representations.  

Deep Learning in Information Retrieval   In recent years, there has been a lot of attention paid to applying deep learning for different IR tasks, including recommender systems.  In the context of recommender systems, several works have used deep learning to solve a variety of problems, including retweet prediction <cit.>, tag-aware recommendation <cit.>, personalized recommendations <cit.>, and video recommendations <cit.>.  Deep learning systems have also been used for IR tasks including web search <cit.> and text matching <cit.>.  Our work is most similar to <cit.> and <cit.>.  Both works use a negative sampling scheme similar to <cit.> to allow their model to scale.  In our work, we also use a negative sampling scheme, but design our sampling distributions so that we converge to an estimate of the cosine similarity between implicit feedback vectors of items. 




§ EXPERIMENTAL STUDIES

We designed two sets of experiments to allow us to empirically study the properties of our objective function and our neural network architectures.  In the first set of experiments, we empirically validate that optimizing the cost function in Equation <ref> converges to the log of the cosine distance between the implicit feedback vectors.  We also study the effects of the sampling ratios when optimizing the Monte Carlo estimate in Equation <ref>.  In our second set of experiments, discussed in Section <ref>, we compare the performance of DCF-Mean and DCF-RNN on 's user behavioral data, and present the results of an A/B test comparing the new approach with 's existing CF-based recommender system.



 §.§ Synthetic Experiments

Synthetic Dataset   To validate that a model trained to optimize the cost function in Equation <ref> optimizes the cosine similarity between implicit feedback vectors, we generated a synthetic dataset of purchases and trained a model to predict the cosine distances between the implicit vectors.  We used the following procedure to generate a dataset.  Let N_u be the number of users in a system, and let N_i be the number of items.  For each item i = 1 … N_i, we draw a random variable p_i ∼Uniform(0.2, 0.8).  Then, for each user u = 1 … N_u and for each item i, we draw a random variable r_ui∼Bernoulli(p=p_i) indicating whether u has purchased item i.  This gives us an implicit feedback matrix of dimensionality N_u × N_i.  We then construct a set of training examples from this user-item feedback matrix.  For each pair of items i, j, we construct a feature vector of dimensionality N_i · N_i, where all entries are set to 0 except for the entry k=i*N_i + j, which is set to 1.  This has the effect of creating a feature for each pair of items (i, j).  For all the experiments in this section, the synthesized dataset consisted of 100 items and 10,000 users.  There were 25,355,794 total co-purchases in the synthesized dataset, with a sparsity ratio of 25.35%.  We experimented with several different values for the number of items, number of users and sparsity, but they made little difference in the results of the experiments described below.  The only difference was in training time.

Validating Full Cost Function   To empirically validate the cost function presented in Equation <ref>, we trained a model on the synthetic dataset previously described.  We then compared the model's estimates of the cosine similarity between each pair of items (i, j) against the true calculated cosine similarity between i and j, using both RMSE and Spearman's rank correlation coefficient.  The training set consisted of a feature vector for each pair of items (i, j), along with their co-occurrence frequencies (i, j) and the square root of their individual frequencies (i).  We trained a linear model of the following form


    h(s,r) = θ⃗ x_sr

to optimize Equation <ref>.  In this case, each parameter θ_k in the parameter vector will correspond to the similarity of the items (i, j) (since we designed our feature vectors to be indicator variables for each pair k=i*N_i + j).  We trained the model for 200 epochs with learning rate 0.1 using stochastic gradient descent.  As the purpose of this experiment was to empirically validate the convergence properties, we compared the model's output against the cosine similarity on the training set. At the conclusion of the training run, the RMSE between the calculation of the true cosine similarities on the training set and our model's estimates was 1.0461 × 10^-4, and the Spearman rank correlation coefficient was 0.9999, with p < 0.01.  Additionally, we also tracked the convergence of the model.  Those results can be found in the heavy-lined curve in Figure <ref>.

Effect of Sampling Ratios   With very large inventories, it is often infeasible to do a full pass over all item pairs, which is a requirement for optimizing the cost function in Equation <ref>.  As an alternative, one can use a Monte Carlo technique to approximate the expectations in the cost function in Equation <ref>.  As demonstrated in Section <ref>, the value of the model output that minimizes Equation <ref> is the log of the cosine similarity of the implicit feedback vectors shifted by a constant:

    h(s,r) = log[(s, r)/√((s))√((r))] + log[k_CP/k_s· k_r] + log[𝒵^2/|CP|]

where k_CP is the number of true co-purchases to sample, k_s is the number of seed items to sample, and k_r is the number of candidate items to sample.  To converge to the optimal value of Equation <ref> when using Monte Carlo techniques, this result suggests that k_CP, k_s, and k_r ought to be selected so that the ratio of samples k_CP/k_s · k_r is set to |CP|/𝒵^2, where |CP| denotes the number of co-purchased item pairs, and 𝒵 denotes the sum of square roots of the number of purchases of each item.  Oftentimes, however, we are more interested in the ranking of similar items produced by the cosine distance rather than the values themselves. To understand the effect of the selection of k_CP, k_s, and k_r on the convergence rate of the training algorithm, we experimented with different ratio values of k_CP/k_s · k_r. We fixed k_CP = 100000, and tried several values of k_s and k_r, training the model for a fixed 200 epochs, where on each epoch we sampled examples from the distributions  and .  Note that for this synthetic experiment, the ratio |CP|/𝒵^2 = 0.516.  The convergence rates of different ratios are shown in Figure <ref>.   We ran several such experiments with a variety of sparsity levels (and therefore different ratios |CP|/𝒵^2), and the convergence results were comparable.



As expected, setting the ratio to |CP|/𝒵^2 yielded the lowest RMSE compared to the true cosine distances at convergence.  The result in Section <ref> indicates that setting the ratio to |CP|/𝒵^2 in Equation <ref> gives the optimal value in Equation <ref>.  Interestingly, oversampling items from  (giving a lower ratio k_CP/k_s · k_r) caused the Spearman rank correlation coefficient between the model output and the true cosine distance to converge more quickly, although they yielded worse RMSE values.  This suggests that if one is training a model for a fixed number of epochs, oversampling k_s and k_r would allow the model to reach a good value more quickly than setting the ratio to |CP|/𝒵^2. Under-sampling k_s and k_r, so that k_CP/k_s · k_r > |CP|/𝒵^2, caused the RMSE to diverge, and the Spearman Rank coefficient to converge significantly more slowly.



 §.§ Experiments on  Data

Setting    has several recommender systems in use for different recommendation settings.  We concern ourselves with the setting of post-purchase recommendations, recommendations that are made after a user purchases an item (referred to as the seed item).  The current post-purchase recommender system constructs a recall set of recommendation candidates for the seed item using item-based collaborative filtering on a few levels of static entities, and then applies a set of business rules to select the top N recommendations among the recall sets.  Note that these results are not personalized to a user based on their entire purchase history.

Data   's inventory is segmented into a hierarchy of categories.  For both our off-line experiments and for the user-facing recommender system, we trained one model for each high-level category.  In this work, we present results on five of those categories: women's fashion, electronics, skin care, outdoor sporting goods, and collectibles. These categories were selected to highlight a variety of inventory.  We define the implicit feedback signals we train on as purchases – we sample pairs of listings from  that were co-purchased by the same user, and we sample purchased listings from the listing distribution .  We constructed our training sets for the five models as follows.  For each of the five categories, we collected all purchases made on  between January 1st 2015 and May 31st 2016 under those categories.  For each category, we constructed a set of co-purchased item pairs CP by taking all pairs of items (t_1, t_2) under the category purchased by the same user u, with the constraint that t_2 was purchased after t_1.  We construct the set of purchased listings D by including all purchased items under the category.  Statistics about this dataset are summarized in Table <ref>.


Note that this method of constructing our training set, along with the fact that we have independent parameters for the three sub-networks in Figure <ref>, means that our models will be asymmetric – the output of the model will not be the same if we invert the seed and candidate items.

Evaluation Methodology   To construct our test set, we sampled listings from the set of purchases made in June 2016, ensuring that the sets of test and training items were completely disjoint.  From the set of June 2016 purchases, we randomly sampled 250 purchased items from each category. For each of those purchased items, we randomly sampled a subsequent purchase by the same user under the same high-level category.  We refer to these 250 pairs as the set of true co-purchases.  When generating recommendations on , we are typically going to consider approximately 1 million recommendation candidates for each seed item.  To reflect this in our evaluation setting, we require a very large recall set of candidate items, from which we will select the top 30 recommendations.  Specifically, we randomly sampled 200,000 random items from the high-level category to serve as the recall set of candidates.  Thus, there will be 200,001 recommendation candidates for each seed item, with one of them being a true co-purchase.  The model is applied to rank this set of candidates for each seed.  Because our evaluation set contains only one true co-purchased item for every seed, we evaluate our models by measuring the rank of the true co-purchased item in the list.

We evaluate our results using two measures: mean recall at k and mean reciprocal rank.  In information retrieval, recall at k is the mean of the number of relevant results in the top k of a ranked list divided by the total number of relevant results:

    rec_k(s) = 1/n∑_i=1^n #(relevant results at position > k)#(total number of relevant results)

In our case, we have one relevant (co-purchased) item for each seed, so recall at k measures the percentage of seed items for which the true co-purchase is in the top k of the ranked list.  On , 30 recommendations are surfaced for a seed.  We evaluate our models in the same setting, fixing k=30.  To understand the performance of our model on the entire recall set and not just the top 30, we also evaluate the mean reciprocal rank of the true co-purchased item, namely:

    MRR = 1/n∑_i=1^n 1/rank(i)





Training Details   We demonstrated in Section <ref> that the ideal ratio k_CP/k_s · k_r should be set to |CP|/𝒵^2.  However, the degree of sparsity in the training data makes it impractical to follow this guideline.  As implied by the results in Section <ref>, and the statistics of the size of |CP| and 𝒵^2 in Table <ref>, we would need to sample several thousand items from  for each s and r for every sample from .  Instead of directly optimizing Equation <ref>, we note that our sampling of items s from  make no difference in the ranking order of candidates for a given seed item s.  Inspired by <cit.>, we instead sample a fixed number of r items for each seed s from .  The cost function we end up optimizing for these experiments is given by:


    ℓ =  𝔼_(s, r) ∼[k_CP·logσ(h(s, r)) 
    + 𝔼_r' ∼[k_r ·logσ(-h(s, r'))]]

Note the similarity between this approximation and the objective function in <cit.>.

We compare the performance of two neural network architectures for this task – one that uses mean pooling on the title token embeddings and the key-value property embeddings (DCF-Mean), shown in Figure <ref>, and one that uses a vanilla recurrent neural network to embed the title, while using mean pooling to aggregate the aspect embeddings (DCF-RNN), shown in Figure <ref>.  We implemented our models and training algorithms in Theano <cit.>, and trained the models on an NVIDIA Tesla M40 card, for a maximum of 1000 epochs.  In practice, training time ranged between three and five days.  In DCF-Mean, we fixed the token embeddings to have 200 dimensions, the hidden layer in the item embedders to have 400 dimensions, and the hidden layer in the top layer with 1200.  DCF-RNN had the same setting, with the hidden state of the RNN set to 200 dimensions as well.

We compare the performance of these two neural networks against two baselines – a linear model baseline (i.e. a logistic regression model) trained to minimize Equation <ref>, and the current collaborative filtering method employed by .  The training examples for the linear model consist of binary vector representations of listings, where each item is represented by a |V|-dimensional vector, where |V| is the size of the vocabulary for the model.  If a feature is present in the listing, its corresponding entry in the feature vector is set to 1, otherwise, it is set to 0.  As described in the introduction, the  collaborative filtering algorithm maps items to static entities and then computes the cosine similarity between implicit feedback vectors of static entities.  The highest quality static entity is a product, which we derive from the UPC or other manufacturer's identifier for an item.  The fallback static entity is an aspect, of which an item may have more than one.  For a given seed item s and a set of candidate items {r_1, …, r_k}, if s maps onto a product ID, then we rank the subset of {r_1, …, r_k} that also map onto products by the cosine distance on purchase vectors between the products.  The ranked list of products is at the top of the N-best list.  For the remaining subset of {r_1, …, r_k} that is not mapped to a product, we fetch all the aspects for each item in the list and compute the cosine similarity between all aspects of the seed and all aspects of the candidate.  The score for a pair (s, r_i) is then the sum of the similarities between all property pairs.  The candidates are ranked according to these scores and are appended to the list after the items mapped to products.

Quantitative Results   The results of our experiments can be found in Tables <ref> and <ref>.  We ran two sets of experiments.  First, we compared the performance of different model architectures trained on the same objective function on the five categories.  We compared the performance of the baseline linear model, DCF-Mean, and DCF-RNN on each of the five high-level categories.  For all of these experiments, we fixed k_cp = 200000 and k_r=4 for each epoch of training.  We fixed the maximum number of epochs to 1000, and used early stopping on a held out validation set to stop training when the loss on the validation set stopped decreasing.  The results on the test set are found in Table <ref>.  Results in bold are statistically significant at p < 0.01, and results in italics are statistically significant at p < 0.05.  Statistical significance was estimated using Student's paired t-test.


The results indicate that with k_r=4, DCF-Mean achieves the best ranking performance over the baseline.  DCF-Mean achieves statistically significant improvement over the CF-based baseline in three of the five categories.  Interestingly, DCF-RNN did not achieve statistically significant improvements over the baseline, despite the fact that it is able to account for token ordering in the titles.  We conjecture that our use of vanilla RNNs hampered our model's ability to learn due to the vanishing gradient problem (we also noticed that the loss plateaued earlier for the RNN models than for DCF-Mean).  In future work, we will experiment with alternative RNN formulations, such as LSTMs <cit.> or GRUs <cit.>, as well as convolutional methods (e.g., <cit.>).  Additionally, for two of the categories, DCF-Mean was unable to gain a statistically significant advantage over the collaborative filtering baseline.  As we show below, DCF-Mean will outperform the baseline for higher values of k_r.

The second set of experiments we ran compared the effect of different selections of k_r on the ranking performance of DCF-Mean.  Generally speaking, the more items r sampled from , the larger the gain over the CF baseline.  Interestingly, the strongest results were in the Women's Fashion, Skin Care, and Collectibles categories.  Purchases in these categories tend to better reflect a user's taste (for example, collectors' interest in certain sports memorabilia, or buyers with particular sartorial preferences) than in the more utilitarian categories of electronics or outdoor sporting goods.  We conjecture that these categories are harder to learn because users' stylistic or thematic preferences are not as often reflected in the co-purchase data.  Additionally, it is important to note that the recall at k and MRR measures only measure the position of the true co-purchased item in the ranked list.  Given the nature of the inventory on , in many settings there may be functionally equivalent items to the true co-purchased item ranked higher in the list than the true co-purchase.  It is possible that given two models with equal recall at k or MRR measures on the test set, one model might rank more relevant recommendations ranked above the true co-purchase than another model, but the evaluation measures do not reflect this property.





A/B Test Results   As is common on e-commerce sites, we ran an A/B test comparing our approach versus the production baseline variant to evaluate the performance of the model in an on-line setting.  The A/B test ran for two weeks on , testing the DCF-Mean model variant against the current production variant.  Table <ref> lists the results, indicating an improvement of two critical metrics: click-through rate (CTR) and purchase-through rate (PTR).  DCF-Mean demonstrated a 79.7% increase in CTR over the baseline and a 51.8% increase in PTR over the baseline.





§ DISCUSSION

To understand why our method seems to work well in the setting of extreme sparsity and cold-start items, we can examine the representations the model learns for items.  We conjecture that the reason the model is able to perform well is due to the semantic similarities between items with similar purchase patterns.  We posit that seed items that are similar in content with each other (e.g., have similar thematic and functional semantics) are more likely to be co-purchased with candidate items that are similar in content to each other.   If true, then the item representations learned by the model ought to reflect these semantics.  While we currently do not have a quantitative measure of semantic similarity, we can examine a few examples of the representational similarity of items.

The listings are sorted by the distance between their vector embeddings (i.e., the hidden layer in Figure <ref>) from the listing whose title is in bold.  For each item whose title is in bold, we computed the Euclidean distance between that item and every other item in our recall set.  We then sorted the list according to distance and selected the listings at the 10th, 100th, 1000th, 10000th, 20000th, 50000th, and 100000th positions.  We present the item titles in Table <ref> to depict their semantic similarities.



These examples suggest that the semantics of the items are represented in the distances between the vectors.  Consider the first example in Table <ref>: “1992 Chicago Bulls world champions drinking glasses set of 3 NBA Michael Jordan”.  The item in the tenth position is another NBA commemorative cup, one for the Boston Celtics.  This is despite the fact that the only shared token between the two is the token “NBA”;  the network seems to have learned to model the relationship between basketball, championships, and glasses & mugs.  As one descends in the list, one gets baseball memorabilia, followed by football memorabilia, followed by a wrestling collectible card, followed by a collectible action figure.  One can see similar patterns for the other items.




§ CONCLUSIONS & FUTURE WORK

In this work, we have described a machine learning objective that converges to the cosine distance between implicit feedback vectors, allowing us to train collaborative filtering models that take into account the content similarity of the items to be recommended. We have presented two neural network architectures and demonstrated that they are more effective in the context of volatile inventory and sparse behavioral implicit feedback matrices than item-based CF, in both off-line evaluation and in an on-line A/B test.  There is substantial room for improvement however.  Finding better methods for combining the information across token vectors, such as LSTMs or convolutional neural networks, would allow us to better model the relationships between the tokens.  Additionally, we would like to extend our objective function to model the similarity in explicit feedback vectors.  Finally, we believe we can improve the model performance by exploring alternative optimization methods and item sampling strategies.

ACM-Reference-Format
 

