We propose a new learning to rank algorithm, named Weighted Margin-Rank Batch loss (WMRB), to extend the popular Weighted Approximate-Rank Pairwise loss (WARP). WMRB uses a new rank estimator and an eficient batch training algorithm. The approach allows more accurate item rank approximation and explicit utilization of parallel computation to accelerate training. In three item recommendation tasks, WMRB consistently outperforms WARP and other baselines. Moreover, WMRB shows clear time eficiency advantages as data scale increases.
Rank based learning algorithms have been widely applied to recommendation problems. One prominent example is Weighted ApproximateRank Pairwise loss [2]. It achieves a high precision on the top of a predicted ranked list instead of an averaged high precision over the entire list. However, it is not scalable to large item set in practice due to its intrinsic online learning fashion. In this work, we address the limitation by proposing a novel algorithm and empirically demonstrate its advantages in both accuracy and time eficiency.
Notation. Let x denote a user, y an item, and Y the entire item set. yx denotes items interacted by user x. y¯x ≡ Y \ yx is the irrelevant item set. We omit subscript x when there is no ambiguity. fy (x ) denotes the model score. The rank of item y is defined as Õ ry = ranky (f , x, y) =
I[fy (x ) ≤ fy¯(x )],
(
Weighted Approximate-Rank Pairwise loss (WARP)
develops an online approximation of item ranks. Its critical component
is an iterative sampling approximation procedure: For each
user-item pair (x, y) , sample y′ ∈ Y uniformly with replacement
until 1 + fy′ (x ) < fy (x ) is violated. It estimates item ranks by
ry ≈ rankywar p (f , x, y) = ⌊ |Y|N− 1 ⌋ (
Relative STDs of rank estimators
warp
sampled-wmrb 0.001
sampled-wmrb 0.01
sampled-wmrb 0.1
10-2 10-1
Rank position p (p = r/N)
100
Φowa (ry ) =
ry
Õ
αj
α1 ≥ α2 ≥ .. ≥ 0,
(
Limitations of WARP. We first point out several limitations of
WARP. 1) Rank estimator in (
We address the limitations by combining a rank-sensitive loss and
batch training. We first define (sampled) margin rank as
rankywmr b (f , x, y) = ||YZ|| yÕ′∈Z |1 − fy (x ) + fy′ (x )|+I(y′ ∈ y¯), (4)
where Z is a subset of Y randomly sampled (without replacement).
1Suppose an item has a rank r in a population N. Let p = r /N . Expectation of the
estimator in (
While margin rank defined in (4) is not the rank in (
We then design a rank-sensitive loss function. Note the
margin rank ry = rankywmr b (f , x, y) is a non-negative real number
rather than an integer as in (
Lwmr b (x, y) = Φwmr b (ry ) = log(ry + 1).
(
By noting Φ′′(r ) = − (1+r )2 < 0, the loss is more sensitive with
small r, thus mimicking the property as in (
Compared to WARP. , WMRB replaces the sequential sampling procedure with batch computations. It results in a diferent rank approximation and loss function. Per user-item pair, WMRB involves more computation and is compensated with easy utilization of parallel computing. WMRB updates model parameters much more frequently than WARP – which only updates the parameters of one user-item after many sampling.
WMRB has an unbiased estimator of margin rank. Its diferent sampling scheme results in smaller variances. Simulation in Fig.1 shows sampled-wmrb has much smaller variance than warp as long as |Z|/|Y| is not too small.
We validate WMRB on three datasets: XING2, Yelp3, and MovieLens20m4. The tasks are to recommend to users job posts, Yelp business, and movies, respectively. We assess the quality of recommendation by comparing models’ recommendation to ground truth interactions split from the datasets. We report recommendation accuracies under metrics Precsion@5, Recall@30, and NDCG@30 as well as training time. The datasets statistics are listed in Table 2.
We compare WMRB to diferent methods. POP recommends items purely based on popularity. WARP and A-WARP are implemented in LightFM [1]. A-WARP difers from vanilla WARP by incorporating available attributes. CE uses Cross-Entropy loss
1.2h 5.0 h 31.2h
3.3 h 3.9 h 20.7h function and is a batch training based algorithm implemented by ourselves. CE and WMRB incorporate attributes as in A-WARP.
Accuracy. Table 1 reports accuracy comparisons of diferent models. We highlight two observations. First, WMRB consistently outperforms WARP and A-WARP. For instance, the relative improvements are 8.6%, 18.6%, and 9.8% on Recall@30. Second, with both being batch based methods, WMRB wins over CE clearly, indicating the efectiveness of the rank-sensitive loss.
Time eficiency. Table 3 reports dataset complexity and training time of diferent models. To measure complexity, we report the total number of model parameters and the average number of attributes per user-item pair. While we make an efort to speed up each method,5 we are most interested in how running time changes with diferent data scales given fixed models and configurations.
From Table 3, WMRB is slower than LightFM on ML-20m. It catches up quickly on Yelp, where data scale increases. On XING, which has the largest model size and complexity, WMRB is much faster. The trend clearly shows scalability advantages of batch training based WMRB.
In this work, we propose a simple yet efective approach to scale up learning to rank algorithm. It implements the idea of ordered weighted average loss in a batch training algorithm. Our preliminary empirical study shows its efectiveness.