Deep Retrieval: An End-to-End Structure Model for Large-Scale Recommendations
Authors: Weihao Gao
Xiangjun Fan
Jiankai Sun
Kai Jia
Wenzhi Xiao
Chong Wang
Xiaobing Liu
Venue:  (2021)
Keywords: Large-scale recommendation system
End-to-end training

Abstract: One of the core problems in large-scale recommendations is to retrieve top relevant candidates accurately and efficiently, preferably in sub-linear time. Previous approaches are mostly based on a two-step procedure: first learn an inner-product model and then use maximum inner product search (MIPS) algorithms to search top candidates, leading to potential loss of retrieval accuracy. In this paper, we present Deep Retrieval (DR), an end-to-end learnable structure model for large-scale recommendations. DR encodes all candidates into a discrete latent space. Those latent codes for the candidates are model parameters and to be learnt together with other neural network parameters to maximize the same objective function. With the model learnt, a beam search over the latent codes is performed to retrieve the top candidates. Empirically, we showed that DR, with sub-linear computational complexity, can achieve almost the same accuracy as the brute-force baseline.

Under review as a conference paper at ICLR 2021
DEEP RETRIEVAL: AN END-TO-END STRUCTURE MODEL FOR LARGE-SCALE RECOMMENDATIONS
Anonymous authors Paper under double-bling review
ABSTRACT
One of the core problems in large-scale recommendations is to retrieve top rele- vant candidates accurately and efficiently, preferably in sub-linear time. Previous approaches are mostly based on two-step procedure: first learn an inner- inner-product model and then use maximum inner product search (MIPS) algorithms to search top candidates, leading to potential loss of retrieval accuracy. In this paper, we present Deep Retrieval (DR), an end-to-end learnable structure model for large- scale recommendations. DR encodes all candidates into a discrete latent space. Those latent codes for the candidates are model parameters and to be learnt together with other neural network parameters to maximize the same objective function. With the model learnt, a beam search over the latent codes is performed to retrieve the top candidates. Empirically, we showed that DR, with sub-linear computational complexity, can achieve almost the same accuracy as the brute-force baseline.
INTRODUCTION
Recommendation systems have gained great success in various commercial applications for decades. The objective of these systems is to retrieve relevant candidate items from corpus based user features and historical behaviors. One of the early successful techniques of recommendation systems the collaborative filtering (CF), which makes predictions based on the simple idea that similar users may prefer similar items. Item- sean-based collaborative filtering (Item-CF) (Sarwar et al.) (200T) extends the idea by considering the similarities between items and items, which lays the foundation for Amazon's 's recommendation system [Linden et al. 2003).
In the Internet era, the amount of candidates from content platforms and the number of active users in those platforms rapidly grow to tens to hundreds of millions. The scalability, efficiency as well as accuracy are all challenging problems the design of modern recommendation systems. Recently, vector-based retrieval methods have been widely adopted. The main idea is to embed users and items latent vector space, and use the inner product vectors to represent the preference between users and items. Representative vector embedding methods include matrix factorization (MF) (Mnih & Salakhutdinov 2008 Koren et al. 2009), factorization machines (FM) (Rendle) 2010), DeepFM (Guo al. 2017). Field-aware FM (FFM) (Juan al., 2016), However, when the number of items is large, the cost brute-force computation of the inner product for all items can be prohibitive. Thus, maximum inner product search (MIPS) or approximate nearest neighbors (ANN) algorithms are usually used to retrieve top relevant items when the corpus is large. Efficient MIPS or ANN algorithms include tree-based algorithms (Muja & Lowe 2014; Houle & Net] 2014), locality sensitive hashing (LSH) (Shrivastava & Li 2014 Spring & Shrivastava (017)), product quantization (PQ) (Jegou et al. Ge et al.! 2013). merarchical navigable small world graphs (HNSW) (Malkov Yashunin etc.
2010
2018
Despite their success real world application, vector-based algorithms has two main deficiencies: (1) The objective of learning vector representation and learning good MIPS structure are not well aligned for the recommendation task; (2) The dependency on inner products of user and item embeddings
might not be sufficient to capture the complicated structure of user-item interactions (He et al. 2017).
In order to break these limitations, tree based models (Zhu et al., 2018 2019 Zhuo et al., 2020). TDM/IDM, have been proposed. These methods node of the tree. Learning objectives for model parameters and tree structures are well aligned to improve the accuracy. However, the number of parameters in these models are proportional to the
tree as indices and map each item to a leaf

---

Under review as a conference paper at ICLR 2021
1
2
D
MLP 1
MLP 2
MLP 3 (D)
1
1
jser emb
user emb ①
user emb
①
Softmax
emb(c1)
emb
2
2
2
p(c1)
Softmax
emb(c2)
p(c2)
Softmax
K
K
K
p(c1,c2.c3)
p(c3)
(a)
(b)
Figure 1: (a) Consider a structure with width K = 100 and depth D = 3. Assuming an item is encoded by length-D vector [36, 27, 20). which called a "path". The path denotes that the item is assigned to the (1, 36), (2, 27), (3, 20) indices of the K x D matrix. In the figure, arrows with the same color form a path. Different paths could intersect with each other by sharing the same index at some layer. (b) Flow chart showing the process for constructing the probability of path = [c,, e2 ca] given input x. p(c)x, 0).
number of clusters, making the tree structure itself difficult to learn data available at the leaf level can be scarce and might not provide enough signal to learn good tree at a finer level.
In this paper, we proposed an end-to-end learnable structure model - Deep Retrieval (DR). In DR. we use
matrix as in Figure Ta for indexing, motivated by [Chen al. (2018). this structure, we define path the forward index traverse over matrix columns. Each path is of length D with index value range {1, 21.2..... K}. There are K" possible paths and each path can be interpreted as a two major characteristics in designing the structure. First, There is
cluster of items. There "leaf node" as that in a tree, so the data scarcity problem of learning the tree based model can be largely avoided in DR's structure. Second, each item can be indexed by path could contain multiple items and each item could also belong to multiple paths. This property naturally accommodated using our probabilistic formulation below. This tettiple-to-multipp encoding scheme between items and paths differs significantly with the one-to-one mapping used in tree structure design. In training. the item paths are learnt together with the neural network parameters of the structure model using an expectation expectation-maximia maximization (EM) type algorithm (Dempster et al. 1977). The entire training process end-to-end and can easily deployed for large-scale content platforms.
paths each
the DR model we will show
The rest of the paper organized as follows. In Section 2 we describe the structure model and its structure objective function used in training in detail. We then introduce beam search algorithm to find candidate paths in the inference stage. In Section 3 we introduce the EM algorithm for training neural network parameters and paths of items jointly. In Section 4 demonstrate the performance of DR on two public datasets: MovieLens 200" and Amazon book Experiment results show that DR can almost achieve the brute-force accuracy with sub-linear computational complexity. In Section 5 we conclude the paper and discuss several possible future research directions.
2 DEEP RETRIEVAL: AN END-TO-END STRUCTURE MODEL
In this section, we introduce the DR structure model in detail. First, we show how we establish the probability function for user select path e given the model parameters 0. This follows the extension to the multi-pane mechanism that enables DR to capture multi-aspect properties of items.
http:// uasd www.ddeed//aaaa///
2

---

Under review as a conference paper at ICLR 2021
We then introduce the penalization design that prevents collapsing in allocating items to different paths. Next we describe the beam search algorithm for retrieval. Finally, we present the multi-task joint training procedure of DR with reranking model.
2.1 THE DR MODEL
The basic model. The DR model consists of D lavers with K nodes, with DK nodes in total. In each layer, we use a multi-layer perceptron (MLP with skip connections and softmax as output. Each layer takes an input vector and outputs a probability distribution over (1, (1.2..... , K} based on parameters 0. Let V = .1..... V) be the labels of all items and π V + [K] be the mapping from items paths. Assume we are given mapping π this section and will introduce the algorithm for learning the mapping together with 0 in Section 3 In addition, for the mapping we assume an item only belongs to one path and we would extend to the multi-path setting in next section.
Given pair of training sample (x, y). which denotes a positive interaction (click, convert, like, etc.) between user x and item y, as well as the path c = (C1, . associated with the item y, the probability p(c|2, 0) is constructed layer by layer as follows (see Figure [bfor a flow chart),
The first layer takes the user embedding emb(x) as input, and outputs a probability p(c [z, f1) over the K nodes of the first layer, based on parameters 8
From the second layer onward, we concatenate the user embedding emb(ar) and the embed- dings of all the previous layers emb(ca-1) 1) (called path embeddings) as the input of MLP, and output p(cala x C1,..., Cd-1, 0g) over the K nodes of layer d, based on parameters 0a-
The probability of path given user x is the product of the probabilities of all the layers' outputs.
p(c,2, 0) = II cl,.al
Given set of N training samples { y1 1 the log likelihood function of the structure model is
N
(0tr(0,
Σ
log logp(=(u))as,,)))
The size of the input vector of layer d is the embedding size times d, and the size of the output vector K. The parameters of layer dl have size of ((Kd). The parameters 0 contain the parameters 0as in all layers, as well as the path embeddings. The parameters in the entire model have an order of O(K D²), which is significantly smaller than the number of possible paths K when D 2 2.
Multi- path extension. In tree-based deep models (Zhu et al. 2018 2019) as well as the structure model we introduced above, each item belongs to only one cluster/path, limiting the capacity of the model express multi-aspect information in real data. For example, an item related kebab An item related to flowers could belong to a "gift" cluster. However, an item related to chocolate or cakes could belong to both clusters in order to be recommended to users interested in either food or gifts. In real world recommendation systems, cluster might not have an explicit meaning such as food or gifts, but this example motivates us to assign each item to multiple clusters. In DR, allow each item y; to be assigned to J different paths {c.,...... ).
could belong to a "food"
Let V D be the mapping from items to multiple paths. Then the multi-path structure objective is straightforwardly defined as,
N Σ log 1=1
p(ccs = =y((,))rr,,)
(0,
This is because the probability belonging to multiple paths is simply the summation of the probabilities belonging individual paths.
Other neural network architectures such as recurrent neural networks (RNN) can also be applied here. Since 12 is not very large in our settings, for simplicity, use MI.P.
3

---

Under review as a conference paper at ICLR 2021
Penalization on size of paths. Directly optimizing (0, r) w.r.t the item-to-pat path mapping could fail to ensure to allocate different items into different paths. (We did observe this practice.) In extreme case, single path given any user x: is as in Eq. [ This is because there is only one available path to chose from. However, this will not help on retrieving the top candidates since there is no differentiation among the items. We must regulate the possible distribution of т to be diverse. We introduce the following penalized likelihood function.
could allocate all items into single path and the probability of seeing this
Pen (0, π) = (0, aa- Σ f((e)
(4)
CE|K]D
where a the penalty factor, |c| denotes the number of items allocated in path e and f is an increasing and convex function. A quadratic function f([cl) |c| controls the average size of paths, and higher order polynomials penalize more on larger paths. our experiments, we use f((c) = lc|$/4.
2.2 BEAM SEARCH FOR INFERENCE
In the inference stage, we want to retrieve items from the DR model, given user embeddings input. To this end, we use the beam search algorithm (Reddy et al. 1977) to retrieve top probable paths. In each layer, the algorithm selects top B nodes from the all successors of the selected nodes from the previous layer. Finally it returns B top paths in the final layer. When B = 1, this becomes the greedy search. The time complexity of the inference stage O(DK log B), which sub-linear with respect to the total number of items V. The detail of the beam search algorithm is relegated to appendix After the top paths are retrieved, we look up the mapping function æ to collect the actual items that belong those retrieved paths.
2.3 MUSKI-TASK LEARNING AND RERANKING WITH SOFTMAX MODELS
The number of items returned by the beam search is much smaller than the total number of items, but often is not small enough to serve the user request, However, since each path in DR can contain more than one item, we will not be able to differentiate the items in the same path. We choose to tackle this by jointly training DR model with reranker,
would like rank those retrieved items.
N
Qooftmax
log Proftmax (y yd xx:)
(S)
where ply ya(ar;) is a softmax model with output size V. This is trained with the sampled softmax algorithm. The final objective is given by Q = Qpen + Qooftmax- After performing beam search to retrieval set of candidate items, we rerank those candidates to obtain the final top candidates. Here we use a simple softmax model for this purpose, but we can certainly replace it by more complex one for better ranking performance.
LEARNING WITH THE EM ALGORITHM
In the previous section, we introduced the structure model in DR and its objective to be optimized. The objective is continuous with respect to the neural network parameters 6, which can be optimized by any gradient-basee optimizer. However, the objective involving the item-to-pate mapping is discrete and can not be optimized by a gradient-based optimizer. As this mapping acts as the "latent clustering" of items, this motivates us to use an EM-style algorithm to optimize mapping and other parameters jointly.
In general, the EM-style algorithm for DR is summarized as follows. At the tth epoch,
1. E-step: for fixed mapping (t(11), optimize parameter 0 using a gradient-based optimizer to maximize the structure objective 2pen (0, π (t-1))).
2. M-step: update mapping n' to maximize the same structure objective (0, m)
Since the E-step is similar to any standard stochastic optimization, we will focus on the M-step here. For simplicity, first consider the case where penalization function f is not included. Given
4

---

Under review as a conference paper at ICLR 2021
user-item training pair (z,, Us), let the path associated with the item be ((.(()))....T (26))) For fixed 8, we can rewrite Qutr (8, TT) as
N Σ log 1=1
v Σ
(), =
(etrs(w)lo =
Σ log
where the outer summation over all items E V and the inner summation is over all appearances of item in the training We consider maximizing the objective function over all possible mappings x. However, for an item e, there are KD number of possible paths so we could not enumerate it over all (t)'ss. We make the follow approximation further simplify the problem.
We use an upper bound Σi logp; S ((og Σi= - log N) to obtain
(0te (0t
log
Σ Σ p(Ty(v)(Zz,0) C= FA
log No
where N, = - independent the mapping. We define the following score function,
y1 o| denotes the number of occurrences of in the training set which is
stu, cl
Σ p(c
Intuitively, s/v, c| can be understood as the importance score of allocating item path In practice, is impossible to retain all scores as the possible number of paths с exponentially large, so we only retain subset of S paths with larger scores through beam search and set the rest of the scores O.
Given score s(v. c) estimated, now we consider add back the penalization function. This leads to the following surrogate function in the M-Step.
J Σ
arg max
No log
s/u [T(l
log N,
f((c).. DE[R]
Σ
(mt(w)
This be efficiently solved using coordinate ascent algorithm and its details can be found in Appendix B.
4 EXPERIMENTS
In this section, study the performance of DR on two public recommendation datasets: MovieLens- 20M (Harper & Konstan (013) and Amazon books (He & McAuley [0166] McAuley et al. 2015). We compare the performance of DR with brute-force algorithm, well several other recommendation baselines including tree-based models TDM (Zhu et al. 2018) and JTM (Zhu et al. 2019). At the end of this section, investigate the role of important hattrtantyyypppaaa hyperparameters in DR.
4.1 DATASETS AND METRICS
MovieLens-20M..
This dataset contains rating and free-text tagging activities from movie recom- mendation service called MovieLens. We use the 20M subset which were created by the behaviors of 138,493 between 1995 and 2015. Each user-movie interaction contains used-id, movic-id, rating between 1.0 to 5.0, as well as a timestamp.
In order make a fair comparison, we exactly follow the same data pre-processing procedure as TDM. We only keep records with rating higher or equal to 4.0, and only keep users with at least reviews. After pre-proos processssn, the dataset contains 129,797 users, 20,709 movies and 9,939,873 interactions. Then we randomly sample 1,000 users and corresponding records to construct the validation set, another 1,000 users to construct the test set, and other users to construct the training set.
'iinee this is upper bound to approximate the true objective maximizing surrogate via lower bound. However still find works well in practice.
maximizing, there is no guarantee
5

---

Under review as a conference paper at ICLR 2021
Table Comparison of precision @ 10, recall 10 and F-measure for DR, brute-force retrieval and other recommendation algorithms on MovieLees-20Mk
Algorithm
Precision @ I0
Recall@ 10
F-measure @ I0
Item-Cr YouTube DNN
8.25%
5.66%
5.29%
11.87%
8.71%
7.96%
TDM (best)
14.06%
10.55%
9.49%
DR Brute-force
20.58% + 0.47%
10.89% + 0.32%
12.32% + 0.36%
20.70% + 0.16%
10.96% + 0.32%
12.38% + 0.32%
Table 2: Comparison of precision @ 2000 recall @ 200 and F-measure 200 for DR, brute-force and other recommendation algorithms on Amazon Books.
Algorithm
Precision @ 200
Recall @ 200
F-measure 220 200
Item-CF YouTube DNN
0,52%
8.18%
0.92%
0,53%
8.26%
0.93%
TDM (best)
0.56%
8.57%
0.98%
JTM
0.79%
12.45%
1.38%
DR
0.95% 0.01%
13.74% + 0.14%
1.63% = 0.02%
Brute-force
0.95% = 0.01%
13.75% + 0.10%
1.63% + 0.02%
For each user, the first half of the reviews according to the timestamp are used as historical behavior features and the latter half are used as ground truths to be predicted.
Amazon books. This dataset contains user reviews of books from Amazon, where each user-bot book interaction contains user-id, an item-id, and the corresponding timestamp. Similar to MovieLens- 20M, we follow the same pre-processing procedure as JTM. The dataset contains 294,739 users, 1,477,922 items and 8,654.619 interactions. Please note that Amazon books dataset has much more items but sparser interactions than MovieLens-20M. We randomly sample 5,000 users and corresponding records as the test set, another 5,000 users as the validation set and other users as the training set. The construction procedures of behavior features and ground truths are the same in MoVIeLens-20M..
Metrics. We precision, recall and F-measure metrics evaluate the performance for each algorithm. The metrics are computed for each user individually, and averaged without weight across users. following the same setting as both TDM and JTM. We compute the metrics by retrieving top 10 and 200 items for each user in MovieLens-20M and Amazon books respectively.
Model and training. Since the dataset is split in way such that the users in the training set, validation set and test set are disjoint, we drop the user-id and only use the behavior sequence as input for DR. The behavior sequence is truncated length of 69 if is longer than 69, and filled with placeholder symbol if it is shorter than 69. A recurrent neural network with GRU is utilized to project the behavior sequence onto fixed dimension embedding as the input of DR. We adopt the multi-task learning framework, and rerank the items in the recalled paths by softmax reranker. We train the embeddings DR and softmax jointly the initial two epochs, freeze the embeddings of softmax and train the embeddings of DR for two more epochs. The reason is to prevent overfitting of the softmax model. In the inference stage, the number of items retrieved from beam search is not fixed due to the differences of path sizes, but the variance is not large. Empirically control the beam size such that the number items from beam search 5 to 10 times the number of finally retrieved items.
4.2 EMPIRICAL RESULTS
We compare the performance of DR with the following algorithms: Item-CF (Srwar et al. 2001 YouTube product DNN (Covington et al. 2016), TDM and JTM. We directly the numbers of Item-CF, Youtube DNN, TDM and JTM from TDM and JTM papers for fair comparison. Among the different variants of TDM presented, pick the with best performance. The result of JTM is

---

Under review as a conference paper at ICLR 2021
recall
recall V2. num path
--- reall
13.75-
13.75
13.50-
13.50
15.25
15.25
12.15
12.75
12.25
12.25
recall us. beam, Size
recall vs. pen_fartor factor
14.00
14.00
+ tocal
++
reca
13.75
15.50
11.50
13.55-
13.00-
13.00-
12.75
12.75
12.50-
12.50
12.25-
12.25
Relationship between recall @ 200 in Amazon Books experiment and model width K, number paths J, beam size B and penalty factor a, respectively.
Figure 2:
only available for Amazon books. We also compare DR with brute-force retrieval algorithm, which directly computes the inner-product of user embedding and all the item embeddings learnt in the softmax model and returns the top K items. The brute-force algorithm is usually computationally prohibitive in practical large recommendation systems, but can be used as an upper bound for small dataset for inner-product based models.
Table shows the performance of DR compared to other algorithms and brute-force for MovieLens- 20M. Table 2 shows the results for Amazon books. For DR and brute-force, we independently train the same model for 5 times and compute the mean and standard deviation of each metric. We conclude the following results.
DR performs better than other methods including tree-based retrieval algorithms such as TDM and JTM.
The performance of DR is very close method, which is an upper bound of the performance of vector-based methods such as Deep FM and HNSW. However, the inference speed of DR is 4 times faster than brute-force in Amazon books dataset (see Table 3 in Appendix C.I).
par with the performance of brute-force
4.3 SENSITIVITY OF HYPERPARAMETERS
DR introduces some key hyperparameters which may infect the performance dramatically, including the width of the structure model K, depth of model D, number of multiple paths J, beam size B and penalty factor a. In the MovieLens-2001 experiment, we choose K = 50, = 3, B 25,
and = 3 x 10-5 In the Amazon books experiment, we choose K = 100, D B 50, 3 and a = x 10 10-7 Using the Amazon books dataset, we show the role of these hyperparameters and how they may affect the performance. We present how the recall @ 200 change as these hyperparameters change in Figure 2
We keep the value other hyperparameters unchanged when varying hyperparameter. Precision @ 200 and F-measure @ 200 follow similar trends them in the appendix.
plot
Width of model controls the overall capacity of the model. If K is too small, the number of clusters is too small for all the items; if K is too big, the time complexity of training and inference stages grow linearly with K. Moreover, large K may increase the possibility of overfitting. An appropriate K should be chosen depending the size of the corpus.
7

---

Under review as a conference paper at ICLR 2021
Depth of model D. Using D = 1 is obviously not good idea since it fails to capture dependency among layers. In Tabel in Appendix C.2. we present the result for D = 2, 3 and for Amazon books dataset, and conclude that D 3 is a good choice trade-off between model performance and memory usage in both experiments.
Number of paths enables the model to express multi-aspect information candidate items. The performance is the worst when J 1, and keeps increasing J increases. Large J may not affect the performance, but the time complexity for training grows linearly with J. In practice, choosing J between 3 and 5 is recommended.
Beam size B controls the number of candidate paths to be recalled. Larger B leads better performance as well as heavier computation in the inference stage. Notice that greedy search is special case when B 1, whose performance is worse than beam search with larger B.
Penalty factor a controls the number of items in each path. The best performance is achieved when a falls in certain range. Smaller a leads to larger path size (see Table ( Appendix C.3) hence heavier computation in the reranking stage. Beam size B and penalty factor a should be appropriately chosen as a trade off between model performance and inference speed.
Overall, that DR is fairly stable to hyperparameters since there is wide range of hyperparameters which leads to near-optimal performances.
5 CONCLUSION AND DISCUSSION
In this paper, we have proposed Deep Retrieval, an end-to-end learnable structure model for large- scale recommender systems. DR uses an EM-style algorithm learn the model parameters and paths of items jointly. Experiments have shown that DR performs well compared with brute-force baselines two public recommendation datasets.
There are several future research directions based on the current model design. Firstly, the structure model defines the probability distribution on paths only based on user side information. useful idea would be how to incorporate item side information more directly into the DR model. Secondly, in the structure model, we only make use of positive interactions such as click, convert or like between user and item. Negative interactions such as non-click, dislike or unfollow should also be considered in future work to improve the model performance. Finally, we currently use the simple softmax model reranker and we plan
more complex model in the future.
REFERENCES
Ting Chen, Martin Renqiang Min, and Yizhou Sun. Learning k-way d-dimensional discrete codes for compact embedding representations. arXiv preprint arXiv:1806.0940 2018.
Paul Covington, Jay Adams, and Emre Sargin. Deep neural networks for youtube recommendations. In Proceedings of the 10th ACM conference on recommender systems, pp. 191-198, 2016.
Arthur P Dempster, Nan M Laird, and Donald Rubin. Maximum likelihood from incomplete data via the em algorithm. Journal of the Royal Statistical Society: Series B (Methodological), 39(1): 1-22, 1977.
Tiezheng Ge, Kaiming He, Qifa Ke, and Jian Sun. Optimized product quantization. IEEE transactions on pattern analysis and machine intelligence, 36(4):744-755, 2013.
Huifeng Guo, Ruiming Tang, Yunming Ye, Zhenguo Li, and Xiuqiang He. Deepfm: a factorization- machine based neural network for ctr prediction. arXiv preprint arXiv: 1703. 2017.
F Maxwell Harper and Joseph Konstan. The movielens datasets: History and context. Acm transactions on interactive intelligent systems (täs), 5(4):1-19, 2015.
Ruining He and Julian McAuley. Ups and downs: Modeling the visual evolution of fashion trends with one-class collaborative filtering. In proceedings of the 25th international conference on world wide web, pp- 507-517, 2016.
8

---

Under review as a conference paper at ICLR 2021
Xiangnan He, Lizi Liao, Hanwang Zhang, Liqiang Nie, Xia Hu, and Tat-Seng Chua. Neural collaborative filtering. In Proceedings of the 26th international conference on world wide web, pp. 173-182, 2017.
Michael Houle and Michael Nett. Rank-based similarity search: Reducing the dimensional dependence. IEEE transactions on pattern analysis and machine intelligence, 37(1):136-150, 2014.
Herve Jegou, Matthijs Douze, and Cordelia Schmid. Product quantization for nearest neighbor search. IEEE transactions pattern analysis and machine intelligence, 33(1):117-12)) 2010.
Yuchin Juan, Yong Zhuang, Wei-Sheng Chin, and Chih-Jen Lin. Field-aware factorization machines for ctr prediction. In Proceedings of the 10th ACM Conference on Recommender Systems, pp. 43-50, 2016.
Ychuda Koren, Robert Bell, and Chris Volinsky, Matrix factorization techniques for recommender systems. Computer, 42(8):30-37, 2009.
Greg Linden, Brent Smith, and Jeremy York. Amazon. com recommendations: Item-to-item collabo- rative filtering. IEEE Internet computing, 7(1):76-80, 2003.
Yury A Malkov and Dmitry A Yashunin. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE transactions pattern analysis and machine intelligence, 2018
Julian McAuley, Christopher Targett, Qinfeng Shi, and Anton Van Den Hengel. Image-based recommendations on styles and substitutes. In Proceedings of the 38th International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 43-52, 2015.
Andriy Mnih and Russ R Salakhutdinov. Probabilistic matrix factorization. In Advances in neural information processing systems, pp. 1257-1264, 2008
Marius Muja and David G Lowe. Scalable nearest neighbor algorithms for high dimensional data. IEEE transactions on pattern analysis and machine intelligence, 36(11):2227-2244 2014.
Raj Reddy al. Speech understanding systems: A summary of results of the five-year research effort. Department of Computer Science. Camegie-Mell University, Pittsburgh, PA, 17, 1977.
Steffen Rendle. Factorization machines. In 2010 IEEE International Conference on Data Mining, pp. 995-1000. IEEE, 2010.
Badrul Sarwar, George Karypis, Joseph Konstan, and John Riedl. Item-based collaborative filtering recommendation algorithms. In Proceedings of the 10th international conference on World Wide Web, pp. 285-295, 2001.
Anshumali Shrivastava and Ping Li. Asymmetric Ish (alsh) for sublinear time maximum inner product search (mips). In Advances in Neural Information Processing Systems, pp. 2321-222222 1-229, 2014.
Ryan Spring and Anshumali Shrivastava. A new unbiased and efficient class of Ish-based sam- plers and estimators for partition function computation in log-linear models. arXiv preprint arXiv:1703.05166, 2017.
Han Zhu, Xiang Li, Pengye Zhang, Guozheng Li, Jie He, Han Li, and Kun Gai. Learning tree-based deep model for recommender systems. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1079-1088, 2018.
Han Zhu, Daqing Chang, Ziru Xu, Pengye Zhang, Xiang Li, Jie He, Han Li, Jian Xu, and Kun Gai. Joint optimization of tree-based index and deep model for recommender systems. Advances in Neural Information Processing Systems, pp. 3973-3982, 2019.
Jingwei Zhuo Ziru Xu, Wei Dai, Han Zhu, Han Li, Jian Xu, and Kun Gai. Learning optimal tree models under beam search, 2020.


Reviews:
[{"review_id": "km7j-UZkjHj", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "##########################################################################\nSummary: \n\nThis paper presents an end-to-end deep retrieval method for recommendation. The model encodes all candidates into a discrete latent space, and learns the latent space parameters alongside the other neural network parameters. Recommendation is performed through beam search. The paper compares the method on two public dataset against several methods (DNN, CF, TDM) and concludes that it can achieve the same result as a brute-force solution in sub-linear time.\n\n##########################################################################\nReasons for score: \n\nThe paper presents an interesting end-to-end deep retrieval approach.  However, the paper suffers from several key limitations:\n\nFirst, it makes a very strong assumption (that vector-based approaches have fundamental limitations).  Because this assertion is very strong, it should be backed by a more thorough analysis than what is done on the paper (more details below).\n\nSecond, it fails to take into account several key state-of-the-art methods (such as VAE).  The method proposed in the paper might perform significantly worse than this SOTA based on their reported results.\n\nFinally, it brings confusion between two problems: the one of choosing an algorithm (vector-based versus deep end-to-end) and the one of choosing a brute-force vs approximate nearest-neighbor.  Yet it is well-known that approximate nearest neighbor search is often almost as good as brute-force nearest neighbor, as can be seen here: http://ann-benchmarks.com/\n\nThe method presented in the paper is interesting, though.  I believe this work could be published, but with significantly more research work.\n\n##########################################################################\nPros:\n\n- Novelty: this paper present a method that, as far as I know, is novel.\n\n- Comparison to tree-based methods: the paper presents an interesting comparison with tree-based approaches \n\n##########################################################################\nCons: \n\n- Lack of validation: first and foremost, the work presented in this paper lacks validation experiments.  For a paper presenting a new algorithm and making a strong claim regarding vector-based methods, we would expect at least 4-5 datasets as is commonly done in the literature, e.g. with MSD, Netflix, Medium, Amazon, Yahoo datasets.  We would also expect more metrics, and in particular, the right recall values as is commonly done in the field.  In particular, other papers use recall@20 and recall@50 (as can be seen in paperswithcode.com) instead of recall@10.\n\n- Missing state-of-the-art: the paper misses on significant portions of state of the art regarding the evaluation.  Several key methods should be included in the evaluation, such as VAEs [1], EASE [2], RACT [3], SLIM [4] and CML [5].  While these methods are not end-to-end, the paper should compare its performance against these methods to conclude whether end-to-end deep retrieval yields better (or even similar) performance compared to them.  It turns out that some of these methods perform well on recall@20 and maybe better than the method presented in this paper.  Note that some of these methods are also sub-linear in the number of items, such as CML.\n\n- The paper is also missing a reference on solving the vector-based limitations, with Off-Policy Learning in Two-Stage Recommender Systems [6].\n\n- The paper claims to address \"large-scale\" recommender systems (at several places in the paper) but does not address this aspect.  There exist a significant body of literature on the topic of recommender systems operating at the scale of billions of users and items now, e.g. [7], [8].  Working at the scale of MovieLens and AmazonBooks is not large-scale.  In addition, a complexity analysis of the method would be very welcome.\n\n- Lack of clarity: The clarity of the paper could be greatly improved by putting the description of the algorithm in a single place.  At the moment, it is spread between Section 1 and Section 2.1.  In particular, Section 1 introduces D and K but does not explain what they are. Some aspects of the algorithms are described in a single line (a GRU is used to project the behavior sequence, but nothing is explained about it).  \n\n- Lack of code: the paper does not provide the code, which does not help for reproducibility and sharing with the community.  Providing code is paramount when proposing a new algorithm.\n\n[1] Daeryong Kim and Bongwon Suh. 2019. Enhancing VAEs for Collaborative Filtering: Flexible Priors Gating Mechanisms. In Proceedings ofthe 13th ACM Conference on Recommender Systems (RecSys ’19). Association for Computing Machinery, New York, NY, USA, 403–407. https://doi.org/10.1145/3298689.3347015\n\n[2] Harald Steck. 2019. Embarrassingly Shallow Autoencoders for Sparse Data. In The World Wide Web Conference (WWW ’19). Association forComputing Machinery, New York, NY, USA, 3251–3257. https://doi.org/10.1145/3308558.3313710\n\n[3] Sam Lobel, Chunyuan Li, Jianfeng Gao, and Lawrence Carin. 2020. RaCT: Toward Amortized Ranking-Critical Training For Collaborative Filtering. InEighth International Conference on Learning Representations (ICLR). https://www.microsoft.com/en-us/research/publication/ract-toward-amortizedranking-critical-training-for-collaborative-filtering/\n\n[4] Xia Ning and George Karypis. 2011. SLIM: Sparse Linear Methods for Top-N Recommender Systems. In Proceedings of the 2011 IEEE 11th InternationalConference on Data Mining (ICDM ’11). IEEE Computer Society, USA, 497–506. https://doi.org/10.1109/ICDM.2011.134\n\n[5] Cheng-Kang Hsieh, Longqi Yang, Yin Cui, Tsung-Yi Lin, Serge Belongie, and Deborah Estrin. 2017. Collaborative Metric Learning. In Proceedings ofthe 26th International Conference on World Wide Web (WWW ’17). International World Wide Web Conferences Steering Committee, Republic andCanton of Geneva, CHE, 193–201. https://doi.org/10.1145/3038912.3052639\n\n[6] Jiaqi Ma, Zhe Zhao, Xinyang Yi, Ji Yang, Minmin Chen, Jiaxi Tang, Lichan Hong, and Ed H. Chi. 2020. Off-Policy Learning in Two-Stage Recommender Systems. In Proceedings of The Web Conference 2020 (WWW ’20). Association for Computing Machinery, New York, NY, USA, 463–473. https://doi.org/10.1145/3366423. 3380130\n\n[7] Chantat Eksombatchai, Pranav Jindal, Jerry Zitao Liu, Yuchen Liu, Rahul Sharma, Charles Sugnet, Mark Ulrich, and Jure Leskovec. 2018. Pixie: A System for Recommending 3+ Billion Items to 200+Million Users in Real-Time. In Proceedings of the 2018 World Wide Web Conference (WWW ’18). International World Wide Web Conferences Steering Committee, Republic and Canton of Geneva, CHE, 1775–1784. https://doi.org/10.1145/3178876.3186183\n\n[8] JizheWang, Pipei Huang, Huan Zhao, Zhibo Zhang, Binqiang Zhao, and Dik Lun Lee. 2018. Billion-scale Commodity Embedding for E-commerce Recommendation in Alibaba. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD ’18). ACM, New York, NY, USA, 839–848. https://doi.org/10.1145/3219819.3219869 \n\n#########################################################################\nSome typos: \n\n\"grow\" on page 1\n\n\"from the all successors\" on page 4\n\nupper-case are missing in the references (e.g. ALSH)\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "Y9SPZBTcrDA", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper seeks to propose an end-to-end learnable retrieval model for recommendation, to replace existing two-step based approaches (learn embeddings first, then do MIPS search).\n\nThe underlying model structure is motivated by KD-code (Chen et al. 2018), where each item is encoded as a D-dimensional discrete vector (with a cardinality K in each dim). Then a conditional, probabilistic framework is proposed to learn the model with a multi-path extension for further improvement. After training, Beam Search is adopted to retrieve top candidates.\n\nThe paper is technically sound, and it's new to adopt a KD-code like model for retrieval. However, I have some concerns in motivation, methods, and experiments.\n\n- The significant feature of the DR model (from the claim in the abstract) to encode all candidates in a discrete latent space. However, there are some previous attempts in this direction that are not discussed. For example VQ-VAE[1] also learns a discrete space. Another more related example is HashRec[2], which (end-to-end) learns binary codes for users and items for efficient hash table retrieval. It's not clear of the connections and why the proposed discrete structure is more suitable.\n\n- The experiments didn't show the superiority of the proposed method. As a retrieval method, the most common comparison method (e.g. https://github.com/erikbern/ann-benchmarks) is the plot of performance-retrieval time, which is absent in this paper. The paper didn't compare the efficiency against the baselines like TDM, JTM, or ANN-based models, which makes the experiments less convincing as the better performance may due to the longer retrieval time.\n\n- It's not clear to me what retrieval/MIPS search methods are adopted for Item-CF, Youtube DNN.\n\n- What's the performance of purely using softmax?\n\n- It seems only DR uses RNNs for sequential behavior modeling, while the baselines didn't. This'd be a unfair comparison, and sequential methods should be included if DR uses RNN and sequential actions for training.\n\n- I didn't understand the motivation of using the multi-path extension. As you already encode each item in D different clusters, this should be enough to express different aspects with a larger D. Why a multi-path variant is needed for making the model more expressive?\n\n- The Beam Search may not guarantee sub-linear time complexity due to the new hyper-parameter B. It's possible that a very large B is needed for retrieving enough candidates.\n\nIn summary, it's not clear to me why the proposed discrete structure is more suitable for the task given we have Tree-based and binary code based approaches (that are also end-to-end learnable). And the experiments didn't show the superiority of the proposed method due to the lack of important comparisons (retrieval time, against HashRec, etc.).\n\n[1]Neural Discrete Representation Learning, NIPS'17\n[2]Candidate Generation with Binary Codes for Large-scale Top-N Recommendation, CIKM'19", "extra_scores": {}, "extra_text": {}}, {"review_id": "MiMY80LxWL1", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper presents a method for \"end-to-end\" learning for retrieving top-k items in recommendation system setup. This is achieved by learning the hidden representations of the items and under neural network as a single objective function optimized using the expectation maximization framework. It is claimed that the proposed method achives better results than state-of-the-art tree-based models and those approaches which learn these components separately.\n\nSome of the concerns regarding the paper are as follows :\n- The paper lacks a motivation for using the proposed scheme. It says that for tree-based models, the number of parameters is proportional to the number of clusters and hence it is a problem. This is not clear why this is such a problem. Successful application of tree-structure for large-scale problem has been demonstrated in [1,2]. Also, it is not clear how the proposed method addresses data scarcity, which according to the paper happens only in tree-based methods, and not in the proposed method as there are no leaves. \n\n- It is not clear how the proposed structure model (of using K \\times D matrix) is different from the Chen etal 2018. The differences and similarities compared to this work should be clearly specified. Also, what seems to be missing is why such an architecture of using stacked multi-layer perceptrons should lead to better performance especially in positive data-scarcity situations where most of the users 'like' or 'buy' only few items.\n\n- The experimental comparison looks unclear and incomplete. The comparison should also be done with the approach proposed in Zhou etal 2020 ICML paper. At the end of Page 6 it is said that the results of JTM were only available for Amazon Books. How do you make sure that same training and test split (as in JTM) is used as the description says that test and validation set is done randomly. Also, it would also be good to see the code and be able to reproduce the results.\n\n- References of some key papers are based on arxiv versions, such as Chen etal 2018 and Zhou etal. 2020, where both the papers have been accepted in ICML conference of respective years. \n\n[1] Extreme Classification in Log Memory using Count-Min Sketch: A Case Study of Amazon Search with 50M Products, NeurIPS 2019\n\n[2] AttentionXML: Label Tree-based Attention-Aware Deep Model for High-Performance Extreme Multi-Label Text Classification, NeurIPS 2019", "extra_scores": {}, "extra_text": {}}, {"review_id": "6AGcmYEdEMq", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors proposed Deep Retrieval, which encodes all items in a discrete latent space for end-to-end retrieval. The proposed method is claimed to perform on par with the brute-force method, under sub-linear computational complexity.\n\n1. The authors mainly claim that the objective of learning vector representation and good inner-product search are not well aligned, and the dependence on inner-products of user/item embeddings may not be sufficient to capture their interactions. This is an ongoing research discussion on this domain. I'd recommend the authors to refer to a recent paper, proposing the opposite direction from this submission:\nNeural Collaborative Filtering vs. Matrix Factorization Revisited (RecSys 2020) https://arxiv.org/abs/2005.09683\n\n2. According to Figure 1, a user embedding is given as an input, and the proposed model outputs probability distribution over all possible item codes, which in turn interpreted as items. That being said, it seems the user embedding is highly important in this model. A user can be modeled in a various ways, e.g., as a sequence of items consumed, or using some meta-data. If the user embeddings are not representative enough, the proposed model may not work, and on the other hand, if the user embedding is strong, it will estimate the probs more precisely. We would like to see more discussion on this.\n\n3. In the experiment, there are multiple points that can be addressed. (a) Related to the point #2, the quality of embeddings is not controlled. Thus, comparing DR against brute-force proves that the proposed method is effective on MIPS, but not on the end-to-end retrieval. Ideally, we'd like to see experiments with multiple SOTA embeddings to see if applying DR to those embeddings still improves end-to-end retrieval performance. See examples below. (b) The baselines used in the experiment are not representing the current SOTA. Item-based CF is quite an old method, and YouTube DNN is not fully reproducible due to the discrepancy on input features (which are not publicly available outside of YouTube). We recommend comparing against / using embeddings of LLORMA (JMLR'16), EASE^R (WWW'19), and RecVAE (WSDM'20). (c) Evaluation metrics are somewhat arbitrary. The authors used only one k for P@k, R@k, and F1@k, arbitrarily chosen for each dataset. This may look like a cherry-picking, so we recommend to report scores with multiple k, e.g., {1, 5, 10, 50, 100}. Taking a metric like MAP or NDCG is another option.\n\n4. The main contribution of this paper seems faster retrieval on MIPS. Overall, the paper is well-written. We recommend adding more intuitive description why the proposed mathematical form guarantees / leads to the optimal / better alignment to the retrieval structure. That is, how/why the use of greedy search leads to the optimal selection of item codes.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The introduced method is novel and interesting. However, as pointed in the reviews the` paper misses several important references. The authors should extend their discussion on related work by methods from both recommender systems and extreme classification. Besides the papers listed by the reviewers, the introduced method seems also to be related to LTLS (https://arxiv.org/abs/1611.01964) and W-LTST (http://papers.neurips.cc/paper/7953-efficient-loss-based-decoding-on-graphs-for-extreme-classification.pdf), as well as to probabilistic classifier chains (https://icml.cc/Conferences/2010/papers/589.pdf) used for multi-label classification (recommendation can be reduced to multi-label classification under 0/1 loss by coding each item using a binary code of a fixed length). Nevertheless, the introduced method seems to be novel, nicely reusing and fitting together existing ideas. 

Unfortunately, the authors did not submit any rebuttal. Therefore, the paper cannot be accepted to ICLR. We encourage the authors to work further and extend the paper by an exhaustive discussion about related work, a wider experimental study, a more detailed description of all the steps of the method. 


Decision: Reject