In this paper, we introduce an Augmented Lagrangian based method in a search relevance ranking algorithm to incorporate the multidimensional nature of relevance and business constraints, both of which are the requirements for building relevance ranking models in production. The of-the-shelf solutions cannot handle such complex objectives and therefore, modelers are left hand-tuning of parameters that have only indirect impact to the objectives, attempting to incorporate multiple objectives (MO) in a model. This process is time-consuming and tends to face sub-optimality. The proposed method is designed to systematically solve the MO problem in a constrained optimization framework, which is integrated with a popular Boosting algorithm and is, by all means, a novel contribution. Furthermore, we propose a procedure to specify the constraints to achieve business goals and the exploration scales linearly in the number of constraints, while existing methodology can scale exponentially. The experimental results show that the method successfully builds models that achieve MO criteria much more eficiently th an existing me thods. The po tential im pact includes significant reduction in model development time and allows for automation of model refresh even with presence of several MO criteria, in real world production system scale with hundreds of millions of records.
Relevance in information retrieval (IR) has been extensively studied
and applied to various areas such as web search, product search and
recommendation, etc. The concept of relevance is
multidimensional, dynamic and evolutional [
Business constraints are additional requirements in production
modeling. Some are derived from existing relevance metrics proven
to be efective over time and are sought to retain in model refresh to
ensure avoiding churn [
As discussed above, relevance ranking modeling faces challenges
of dealing with multiple metrics of relevance and / or business
constraints, i.e., multiple-objectives (MO). Of-the-shelf machine
learning solutions [
To address the issue, we propose a constrained optimization
method applied to the Gradient Boosting Tree (GBT). Specifically,
we introduce a constraint optimization in the LambdaMART
algorithm, the most prominent method for relevance modeling today.
LambdaMART is based on GBT [
In order to meet the requirements and limitations, adaptation
of the Augmented Lagrangian (AL) method [
Our code is currently incorporated in GBM in R. We plan to implement the algorithm into XGBoost and / or LightGBM and make them publicly available.
Section 2 introduces existing work in multi-objective optimization in relevance ranking. Section 3 gives formulations and algorithm of our proposed method. Section 4 illustrates experimental results and Section 5 concludes this paper. 2
The MO problem in search relevance literature has been a popular
research topic and there have been two major directions: combining
multiple objectives in a single model and aggregate multiple models
tuned for each objective. As for the single model approach, Dong et
al. [
Another popular approach is to use aggregation of multiple
rankers. Dai et al. [
Most of the existing algorithms rely on heuristics, such as weighting or linear combination of objectives / models, and require manual tuning of hyper-parameters, which becomes prohibitive as the number of objectives becomes large. Our approach, in contrast, automatically yields a model that satisfies minimal requirements over MO’s, alleviating the efort of hand-tuning of hyper-parameters, which makes a clear distinction from the existing methods. cpm sq =
Õ (i, j)∈P q
cpm siq , sqj
In terms of application of constrained optimization to more
generic problems, Bayesian Optimization (BO) with constraints
[
FORMULATION AND ALGORITHM In this section, we provide formulation and an algorithm of the proposed method in details. As a method for production modeling, there are some requirements in design: latency in scoring and the computational cost in training. For the former, we should avoid constructing large number of trees and complex structure of each individual tree as it translates into latency degradation. For the latter, we should avoid large number of iterations, or nested iterations, as the objective function evaluation can be expensive in search application. 3.1
LambdaMART objective and gradient First, let us review the LambdaMART formulation. Suppose we have a set of queries Q = {q} and an index set of documents (products in product search) associated with each query I q . A document is denoted by di with an index i ∈ I q . A set of pairs of document indices by Pq = {(i, j)} with the relation Ri ▷q Rj : di is more relevant than dj for a given query q. Suppose also we have a single cost function to optimize, referred to as primary cost. Given a relevance model f , for a query and a document, a score of the document is computed as a function of its input features that could be query dependent: siq = f (xiq ). A probability of the relevance relationship is modeled by a sigmoid function:
Prob(Ri ▷q Rj ) = Prob (i, j) ∈ Pq
= 1 + e−σ siq −sjq −
1
where σ is a parameter to determine the shape of the sigmoid
function. LambdaMART [
pm,q log 1 + e−σ siq −sjq = ∆ Zi, j pm,q is the diference of a metric such as NDCG between where ∆ Zi, j the (i, j) pair in one order and one that is flipped. For a metric like NDCG, relevant documents in higher ranked position gets a high pm,q value and that in lower a low value. Therefore, the weight ∆ Zi, j tends to be large when a high ranked position is involved in the pair. For a query, the total cost c(sq ) with sq being a vector containing all documents for the query, i.e., sq = [s1, .., sI q ], is given by
(1) (2) (3) The primary objective function of LambdaMART is a sum over all queries:
Cpm (s) = Õ cpm (siq , sqj ) = Õ cpm (sq ) (4) q ∈Q (i, j)∈P q q ∈Q where s is a concatenated vector containing scores for all queries: {sq |q ∈ Q }.
Boosting in LambdaMART is based on the GBT, which generates a linear combination of base functions that are the decision trees, which are learned to fit the gradient. Typically, in GBT, once a tree is constructed, the function value of each leaf is computed by an estimate of the Newton step for the node. More formally, at an nth iteration, leaf nodes {Rnl }lL=1, where L is the number of leaves of a tree, are generated by CART for given input features of a query and documents, and the gradient as a target: {(xiq , дn (f (xiq )))}q ∈Q, i ∈I q , with дn being the gradient with respect to a score. The function value for each node is given as: γnl = q 2 −1 − Íxiq ∈Rnl ∂2Cpm /∂siq Íxiq ∈Rnl ∂Cpm /∂ si . Therefore, the score, or the prediction function is given as follows: siq = f (xiq ) = f0(xiq ) + q γnl δ (xi ∈ Rnl ) ÕN ÕL n=1 l =1 where f0(xiq ) is an initial base function that could be provided by prior knowledge and δ is the Kronecker delta. To derive the gradient, it is handy to rewrite the query cost as follows: cpm (sq ) = Õ cpm (siq )
i ∈I q = Õ © Õ i ∈I q «j:(i, j)∈P q cpm (siq , sqj ) +
Õ
j:(j,i)∈P q
cpm (sqj , siq )®ª
¬
with cpm (siq ) ≡ Íj:(i, j)∈P q cpm (siq , sqj ) + Íj:(j,i)∈P q cpm (sqj , siq ).
The first term computes the pairwise cost between di and
others that are less relevant than di . The second term computes that
between di and others that are more relevant than di . The
gradient used in LambdaMART [
Õ λpm,q = i λpm,q i j − 1 + eσ siq −sj
q Õ j:(j,i)∈P q λpm,q ji , we have j:(i, j)∈P q where we define ρipjm,q ≡ 1 + e
Similarly, the second order derivative, defined as ρipm,q ≡ ∂2cpm /∂ si is given as follows: ρpm,q = σ 2 i − σ 2
pm,q ρpm,q 1 − ρipjm,q ∆ Zi, j i j
pm,q ρpm,q 1 − ρpjim,q ∆ Zi, j ji 3.2 Incorporating Augmented Lagrangian method in Boosting Suppose all objectives are given in terms of cost functions. Just like the primary objective function reviewed in 3.1, we use surrogated cost functions to optimize the metrics we desire. For example, suppose we want to set minimum criteria in NDCG. In this case, we use LambdaMART costs for NDCG and set the cost no greater than the given upper-bound (UB) b, i.e., C ( ) ≤ bt , t = 1, . . . , T . Given t s the constraints represented in terms of cost functions, we have the following constraint optimization problem: min Cpm (s) s .t . Ct (s) ≤ bt , t = 1, ..., T .
s The Lagrangian is written by
L (s, α ) = Cpm (s) +
T Õ α t Ct (s) − bt where α = α 1, ..., αT is a vector of dual variables. The Lagrangian is solved by minimizing with respect to the primal variables s and maximizing with respect to the dual variables α . AL iteratively solves the constraint optimization while alleviating nonsmoothness in α arising in the dual. In our problem, the Lagrangian at iteration k is written as follows: (9) (10) (11) (5) (6) (7) (8) − ÕT 1 t 2µ k α t − α kt−1 2 where α kt−1 is a solution in the previous iteration and a constant in the current iteration k. µ kt is a suficiently large constant associated with each dual variable α t . Note that the last term is newly added as compared with Eq. (10) and it gives proximal minimization with iterates α t 1, to make the optimization smooth.
We makxi−mize the Lagrangian with respect to α ≥ 0 and minimize with respect to s.
max min Lk (s, α ) (12) α ≥0 s From the stationary condition ∂Lk /∂α t = 0, we obtain the update formula for α : α kt = max 0, µ kt Ct (s) − bt + α kt−1 . (13) At an iteration k, if the constraint t is not satisfied, i.e., Ct (s) > bt , we have α kt > α kt−1, which means the Lagrange multiplier α t increases unless the constraint is already satisfied. Intuitively, we can consider it as weighting that is adjusted each iteration to q 2 overweight an unsatisfied constraint that is associated the cost we want to improve. Note if a constraint should be strictly satisfied at optimality, α t should take value 0 to maximize the Lagrangian. If a constraint should be satisfied with equality, α t can take a finite value. By restricting the solution to the former case, we can push the dual variable to 0 whenever the constraint is satisfied: ( 0, α kt = µ kt Ct (s) − bt + α kt−1, ioftChetr(ws)is−e bt < 0 (14) Intuitively, we can avoid unnecessary iterations to find out α = 0 by simply pushing α to zero whenever the constraint is met. Our preliminary study shows the update Eq. (14) works better than that in Eq. (13) in both primary and sub-objectives. Throughout this paper, we adopt Eq. (14) as the update scheme for dual variables.
As for the primal variables, the first order derivatives are given as follows: ∂∂Lsqk = i wρtqhe≡reρipwme,qde+fineÍt λαqit ρ≡it,qλ,pitmh,eqs+ecÍontdαotrλdtie,qr.dSeirmivialatirvlye,wbiythderefinsipnegct to a score is simply given as follows: ∂2Lk
q 2 = ∂ si It is evident that it penalizes constraint violations associated with α t > 0 with quadratic function. Therefore, setting a high value of µ t imposes the constraint more strictly but on the other hand, k setting a too high value may introduce a non-smoothness behavior which AL tries to avoid. 3.3
An approach to Augmented Lagrangian with LambdaMART Both AL and LambdaMART algorithms run by iterations. We propose a simple approach to integrate the two; Conduct an AL step calculation to update α at each Boosting iteration, which means the AL iteration index k is set equal to the Boosting iteration index n. As for the AL parameter µ t , we take a fixed policy on iterak tion: µ kt = µ t . A variant of algorithm would increase the value as iterations proceeds. Algorithm 1 shows the steps of the algorithm.
Most notably, the additional component to the original
LambdaMART at the n-th iteration step is the gradient computation:
λqi ,ρiq and the update of α nt . The modification to existing solvers
such as GBM in R [
In this section, we analyze the algorithm by a numerical study. The dataset we use is a product search data collected and generated in an e-commerce service. We first study how to set the optimization parameter µ and the cost upper-bounds to ultimately achieve modeling goals using smaller sampled dataset. Then we apply the settings to the full dataset for building a production-ready model. Our prototyping code for AL-LM is currently incorporated in GBM in R and used throughout of this section.
Input: Number of trees N , number of leaves per tree L, learning rate η, AL parameter µ t . Initial Lagrange multiplier estimate α 0t = 0, t = 1, .., T . Given initial
BaseModel foreach q ∈ Q do f0(xiq ) = BaseModel (xiq ), i ∈ I q /* If BaseModel is empty, set f0(xiq ) = 0 */ end end for n=1 to N do foreach q ∈ Q, i ∈ I q do λqiρiq==λpiρmipm,q,q++ÍÍTt=T1 α nt−t 1λtiρ,tq,q,
t =1 αn−1 i {Rnl }lL=1 /* Create an L leaf tree on {(xiq , λqi )}q ∈Q,i ∈I q */
Íq∈Q,xiq ∈Rnl λiqq γnl = − Íq∈Q,xiq ∈Rnl ρi /* Assign leaf values on Newton step estimate */ foreach q ∈ Q, i ∈ I q do fn (xiq ) = fn−1(xiq ) + η Íl γnl δ xiq ∈ Rnl /* Take step with learning rate η */ for t=1 to T do
Compute cost Ct (s) with {siq = fn xiq }q ∈Q,i ∈I q
Update α nt via Eq. (13) or Eq. (14) end end end
Algorithm 1: AL-LambdaMART (AL-LM) 4.1
The dataset consists of search queries, input features (e.g., query,
product, and query-product dependent features such as product
sales, customer review, textual matches between a query and
products), as well as customer’s purchase decision. We follow the basic
modeling practice described in [
As for sub-objectives, we identify four. The first one ( t 1) is to surface set of products that have relatively good quality and popular to a certain customer segment (e.g., customers with subscriptions or customers who are more interested in trending products.); the insight being promoting popular products of high quality for such a segment while others still have the impressions on such products. The 2nd – 4th ones are products that contain additional benefit/service to such a customer segment; 2 nd (t 2) ofers some lowest benefit to the customer of the three and 3 rd (t 3) and 4th (t 4) ofer superior benefits in an increasing order. Generally, benefits are hierarchical and coverage is inversely proportional to it. C_t1
C_t2 (a) Costs w.r.t. #iterations b_t1 b_t2 C_t1
C_t2
C_pr 11 21 31 41 51 61 71 81 91
Iteration (b) AL update: alpha_t1 alpha_t2 First, we show how the algorithm progresses by iterations. In this study, we use two constraints for simplicity. We randomly sample 20K search impressions from the dataset and split into 50% for training and validation sets. We run the algorithm up to 100 iterations for illustration purpose. The UB bt are set based on the unconstrained baseline; we run the unconstraint problem first, which is exactly the same as the original LambdaMART algorithm. Table 1 shows cost and NDCG for the purchase, t 1 and t 2. Then the UB values are set based on a cost reduction rate, such as 5, 10, . . . , 50%, from the unconstrained baselines. Table 2 shows actual values of UB’s used in the experiments. 4.2.1 Cost curve illustration. Figure 1 (a) illustrates curves of costs that are the objectives in the problem. The value of α nt is also shown in Figure 1 (b). We set UB for 20% cost reduction against the unconstrained baseline and set µ = 10K , which is a setting that is found to be large enough as studied in next subsection. In cost curves, solid curves correspond to the cost values on the training data and dotted curves those on the validation data. Note solid lines represent the UB’s. As seen in the Figure 1 (a), the initial few iterations try to satisfy constraints aggressively. Then spend a number of iterations in the over-satisfied region, gradually challenging the UB’s. The behavior of α can be seen in (b). α is pushed to zero when the constraint is met during the iterations. Then when a constraint violation occurs, a finite value of α kicks in again. At iteration 80, α t 2 actually gets 0.79, as seen in Figure 1 (b). Validation results are also shown as dotted curves in Figure 1 (a). Constraint satisfaction in training tend to be generalizable to that in validation set. 4.2.2 Optimization parameter µ . In AL, the optimization parameter µ t can be any suficiently large value. In our experiments, we set k µ nt to be a constant across all iterations and constraint. We vary the value from (10, 100, 1K, 10K ) and see how the constraints are satisfied, over diferent cost UB reduction rates that ranges from 5% through 50%, see Table 1 for the values used for each objective. As a metric to measure constrained satisfaction, we use relative margin that is defined as (bt − Ct )/bt . Negative value means constraint violation. In Table 4 and 3, obviously, the more UB values are set aggressively, the less chance the constraints can be satisfied. For both constraints, when UB’s are set 5%, all constraints are met even for µ is as small as 10. However, as UB is set up to 30%, only larger value of µ , i.e., µ = 1K or 10K can satisfy the constraints. For above 40% reduction, even µ = 10K sufers from infeasibility. As µ = 10K satisfies most constraints for the cost reduction rate for the training data, a sensible choice for the value of µ would be at least 10K . 4.2.3 Cost reduction and NDCG gain. Now, we look at the cost reduction rates and NDCG gains over the unconstrained cases as baseline. Table 5 shows for each objective, how the attained cost reduction rates and NDCG gains vary with diferent UB settings. Note for the constraints, the cost values are consistent with Table 4 and 3, as they are computed based on values in Table 5.
As we have tighter UB values, cost associated with the constraint is reduced, which improves the NDCG gain. For the primary objective, purchase, the behavior is opposite, which is all expected as we are tightening constraints. An important observation is the validation results are consistent with those of training, which means the constraint satisfaction in training generalizes well at least for the dataset examined. Note constraint t 2 is over-satisfied with large margin in cost. This is due to the correlation between the target values associated with t 1 and t 2, as that of t 1 is available only if the target value of t 2 is positive, which partially explains t 1 is a tighter constraint to be satisfied than t 2.
The relationship between the cost reduction and the NDCG gains is illustrated in Figure 2. The two metrics are quite consistent and ift well by linear lines. This means, we can estimate cost reduction value for a given NDCG gain requirement, by using the approximately liner relationship. Once we have the cost reduction rate, we can set it as the UB. This observation is quite useful in practice where NDCG gain values would likely be the criteria for ofline modeling. 4.3.1 Applying AL-ML in the full dataset. In this subsection, we show results on a larger sampled data to simulate a production modeling with more sub-objectives. To this end, we increase the samples to ∼1MM search impressions for the training and ∼500K search impressions for the hold-out evaluation data sets and use the full four sub-objectives. Each sub-objective is computed by a binary target value, just like the purchase target. The goal of the modeling is to achieve at least 1% gain in the number of products with the positive sub-objective value, i.e., presence of products eligible for some customer benefit in top-5 and 22 ranks, while minimizing the impact on the purchase NDCG. We use relationship between the metrics (top-K ) and cost as illustrated in Figure 2 to estimate the values of UB’s by using smaller number of samples. In other words, as long as we know the relationship between the metric value and cost value, we can achieve the goal of +1% gain by just setting the UB’s. Namely, we choose 14% reduction for bt 1 and 1/0.181 = 5.5% reduction for bt 2 and adjust if the constraint is too tight to satisfy, or over-satisfied. Note as we find t 3 and t 4 follows very similar pattern as t 2, we use the same setting as t 2 to them. 4.3.2 OW method as a baseline. As a baseline method to compare against, we tune models by over-weighting (OW) over the sub-objectives. Basically, in the OW method, we identify search impressions that contain products with the positive sub-objective value for applying over-weightings. We introduce weights on the pairwise cost computation so that we can influence the cost function depending on products that matches a query. For example, if a product has a value one in the target t 1, i.e., the product is eligible for some benefit, and we want to optimize t 1 over other sub-objectives, we put high weight on the cost associated with t 1 so the ranking is more likely to optimized for the search impressions containing products with t 1 as a feature. When there are multiple sub-objectives, we need to combinatorially tune multiple weighting schemes to concurrently achieve multiple objectives.
The weight values are tuned first by manually finding a reasonably good weighting parameter ranges and run grid search to fine tune. As there are four dimensional space to explore and too time consuming for the problem size, we only search weighting parameters for t 1 and t 2; we rely on correlation between t 2 and t 3 or t 4 to optimize overall metrics. Despite the search space reduction, we end up building 144+ models.
Results. Table 6 shows the results on the evaluation set from OW and AL-LM, which are measured by %-gain with respect to the unconstrained baseline. For OW, only 7 out of 144 trials over the grid are found as feasible solutions. We report min, max and avд among the solutions. For AL-LM, we already have estimates of each constraint from Figure 2. A similar preliminary experiment gives estimate of other cost UB’s.
Both methods achieve the 1% gain criteria for all metrics. While AL-LM achieves higher gains for t 2 – t 4 and purchase NDCG is lfat, the model shows slight over satisfaction and we apply some adjustment (relax UB’s by 20%: 14% reduction for bt 1 to 11% and 4%), yielding slight improvement on purchase (insignificant) with less margin on t 1. In terms of eficiency, AL-LM is a clear win as it requires only two model builds, one for getting the baseline cost value and the other by applying cost reduction UB’s estimated by smaller sample. We could put eforts on adjustment if the oneshot model has issues, which can be resolved slight tightening or relaxing constraints. OW, on the other hand, requires exploration of the weighting schemes and the success rate is 7/144 = 4.8%, which requires 21 trials on average and 61 trials at 95% confidence.
Addition of further sub-objectives, such as search defect and adult products tend to be much less correlated with the constraints we studied in this paper, which means more combinatorial exploration (exponential in T ) is needed for existing methodologies. ALLM is the choice for MO modeling, as it only requires setting UB’s and some adjustment around the one-shot model: (linear in T ). 5
CONCLUSION AND FURTHER WORK In this paper, we introduced an Augmented Lagrangian based method to address challenges with the multi-objective optimization in relevance modeling. Specifically, we incorporated a constraint optimization method into Boosting so that modelers can use it very easily as an extension to the LambdaMART, one of the most popular Boosting methods in this domain. The explicit introduction of constrained optimization is a novel contribution of this paper and thus its application to relevance ranking is novel. Experimental results showed the proposed AL-LM can indeed eficiently resolve the MO problem. The impact of the outcome would be not limited to reducing the model development lead time; modelers can make more efort in developing new features by using the time saved and an automated model refresh can be realizable by incorporating various constraints automatically. In fact, we have been quite successful in apply the multiple objective models built with AL-LM to modeling projects in production.
Our code is currently incorporated in GBM in R. We plan to implement the algorithm into XGBoost and / or LightGBM and make it publicly available.
Although we applied the method on relevance modeling, it is applicable to wider problem domains, i.e., classification and regressions, and other machine learning methods such as neural networks, etc. Extension to wider application and methodology is a future work as well.