# An Improved LambdaMART Algorithm Based on the Matthew Effect

Authors: Jinzhong Li; Guanjun Liu
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

Matthew effect is a desirable phenomenon for a ranking model in search engines and recommendation systems. However, most of algorithms of learning to rank (LTR) do not pay attention to Matthew effect. LambdaMART is a well-known LTR algorithm that can be further optimized based on Matthew effect. Inspired by Matthew effect, we distinguish queries with different effectiveness and then assign a higher weight to a query with higher effectiveness. We improve the gradient in the LambdaMART algorithm to optimize the queries with high effectiveness, that is, to highlight the Matthew effect of the produced ranking models. In addition, we propose strategies of evaluating a ranking model and dynamically decreasing the learning rate to both strengthen the Matthew effect of ranking models and improve the effectiveness of ranking models. We use Gini coefficient, mean-variance, quantity statistics, and winning number to measure the performances of the ranking models. Experimental results on multiple benchmark datasets show that the ranking models produced by our improved LambdaMART algorithm can exhibit a stronger Matthew effect and achieve higher effectiveness compared to the original one and other state-of-the-art LTR algorithms.


---

## Body

## 1. Introduction

Ranking is an important component that directly affects the performances of information retrieval systems such as search engines, recommendation systems, and electronic commerce platforms. For instance, the PageRank algorithm [1, 2] of the Google search engine computes the Web page scores based on a graph inferred from the link structure of the Web. This algorithm assigns a Web page with a higher score if the sum of its backlinks is high. In addition, this algorithm also considers the cast votes of pages. A page has an important weight if it casts votes for itself, and the reason is that it can help enhance the importance of other pages [3]. The PageRank algorithm exhibits the Matthew effect [4], which refers to the phenomenon that the rich get richer and the poor get poorer. This is valuable and reasonable in a search service, since people prefer to click on the links to some high-quality pages from other high-quality ones.In some application scenarios, for examples of the search of hot words for search engines and the recommendation of popular products for recommendation systems, their ranking methods usually expect a Matthew effect. That is, Matthew effect is a desirable phenomenon for their ranking models, which can make their ranking results more effective and can meet the users’ requirements better. Therefore, it has a practical significance to develop a ranking model with a strong Matthew effect in these ranking scenarios. However, the existing LTR methods do not pay attention to the Matthew effect and thus this becomes the motivation of our work.In this paper, we improve the LambdaMART [5, 6] algorithm via some new strategies in order to strengthen the Matthew effect. Our improvements can not only strengthen the Matthew effect of a ranking model but also enhance the effectiveness of the ranking model. To the best of our knowledge, this is the first attempt to improve the algorithm of learning to rank under considering Matthew effect.The main contributions of this work are summarized as follows:(1) We present a new function of the gradient in the LambdaMART algorithm that can highlight Matthew effect and prove that the function satisfies the consistency property.(2) We propose two strategies to evaluate the ranking models and dynamically decrease the learning rate, respectively. They can not only strengthen the Matthew effect but also improve the effectiveness of the final ranking model.(3) Experiments on multiple benchmark datasets are done to show the advantages of our improved LambdaMART algorithm compared to the original one and other state-of-the-art LTR algorithms.The remainder of this paper is organized as follows. Section2 reviews some related work. Section 3 describes the improvements of the LambdaMART algorithm via the idea of Matthew effect and some strategies. Section 4 presents the evaluation measures of the Matthew effect. Our experimental results are illustrated in Section 5. Section 6 concludes this paper.


## 2. Related Work

An algorithm of learning to rank (LTR) in the field of information retrieval is to use a machine learning technique to train a ranking model for solving ranking problem. A large number of LTR algorithms have been proposed [5–19]. For example, RankNet [7] is a neural-network-based LTR algorithm that optimizes a cross-entropy cost function using gradient descent algorithm to train a neural network model for ranking. LambdaRank [8] improves RankNet by defining the gradients of a given cost function only at the points of interest. It directly optimizes a cost function of effectiveness measures while avoiding the difficulties of working with nondifferentiable measures of information retrieval. LambdaMART [5, 6], denoted as λ-MART, improves LambdaRank by using multiple additive regression trees (MART) rather than neural network and thus exhibits better effectiveness of a generated model. λ-MART [5, 6] is the boosted regression tree version of LambdaRank. It models the gradients using the ranked positions of those documents with relation to a given query and utilizes the gradients to compute the optimal weights for combining the weak learners in a boosting model. λ-MART treats the force of upward or downward movement of each document unequally by the gradient of the document but treats effectiveness of each query equally, which results in not only a relatively lower ratio of queries with low effectiveness (i.e., poor queries) but also a relatively lower ratio of queries with high effectiveness (i.e., rich queries). Therefore, the λ-MART algorithm cannot highlight the Matthew effect. To solve this problem, we improve λ-MART based on the Matthew effect. In other words, queries with different effectiveness are distinguished and those with higher effectiveness are given higher weights, and the differences of moving forces between different document-pairs are enhanced.There are some studies improving theλ-MART algorithm. Ganjisaffar et al. [9] combine bagging and boosting for bagged λ-MART to achieve the high prediction accuracy and low variance. Asadi et al. [10] explore the topology of tree-based ensembles and modify the λ-MART algorithm to perform the stage-wise pruning for improving efficiency. Ferov et al. [19] propose a modification of the λ-MART algorithm, which utilises oblivious trees instead of standard regression trees in the learning process in order to improve the effectiveness. This paper differs from them. We not only improve the gradient but also propose two strategies: one is to evaluate the current ranking models and the other is to dynamically decrease the learning rate. These improvements can both strengthen the Matthew effect and improve the effectiveness of the λ-MART algorithm.There are some studies such as RankBoost [11] and AdaRank [12] that are also based on boosting algorithm. In the two LTR approaches, the document-pairs are reweighted by decreasing the weights of those document-pairs that are correctly ranked and increasing the weights of those document-pairs that are incorrectly ranked. Then, the weak rankers are repeatedly constructed by reweighting the training data, and the learning at the next iteration will focus on the training of a weak ranker that can work on the ranking of those poor queries. Our work also differs from RankBoost [11] and AdaRank [12] because we strengthen the differences of the gradients of different document-pairs at each boosting iteration and highlight the importance of rich queries based on the Matthew effect.Some approaches of LTR treat the queries in the training dataset equally while ignoring the differences of any two queries in the training process of the ranking models. In general, for two different queries, their effectiveness scores are different in a ranking model. Therefore, they should not be treated equally if we expect that a ranking model can make a query with high effectiveness (i.e., rich query) to have higher effectiveness and make a query with low effectiveness (i.e., poor query) to have lower effectiveness. Notice that there are some studies that consider the differences of queries. Geng et al. [20] propose a K-Nearest Neighbor approach for query-dependent ranking which employs different ranking models for different queries to improve the effectiveness of ranking model. Cai et al. [21] propose two methods of query weighting to measure the query importance for ranking model adaptation. Li et al. [22] make a comprehensive examination of different query-level weighting strategies for two unsupervised ranking frameworks. Their aim of considering the differences of queries is to improve the effectiveness of ranking models, while our aim is to improve not only the effectiveness but also the Matthew effect of ranking models.Most of the existing LTR algorithms focus on improving the effectiveness of the ranking model, while they rarely pursue the Matthew effect of the ranking model. We know that different queries usually have different effectiveness in a ranking model. Therefore, if a ranking model can guarantee that a rich query has higher effectiveness, then the rich query should be given a greater weight so that it is focused on optimization in the training process of the ranking models.


## 3. The Improvements of theλ-MART Algorithm via the Idea of Matthew Effect and Some Strategies

We first recallλ-MART algorithm and then improve its gradient and propose a strategy of evaluating the current ranking model to characterize the Matthew effect. In addition, we propose a strategy of dynamically decreasing the learning rate. Finally, we analyze the computational complexity.


### 3.1. The Gradient ofλ-MART Algorithm

The basic idea ofλ-MART [5, 6] is to train an ensemble of weak learners by using MART and approximate Newton step and linearly combining their predictions into a stronger and more effective learner. λ-MART tunes the gradients of the regression trees based on a gradient-based optimization method. The gradient function is calculated according to the selected evaluation metric of effectiveness, and this metric is optimized directly in the training process of a ranking model.The key of theλ-MART algorithm is the gradient function λ which is defined as a smooth approximation to the gradient of a target cost with respect to the score of a document. The gradient function quantifies the adjusted direction (up or down) and the force of a “to-be-sorted” document in the next iteration. The two documents of any given document-pair have the equal gradient values but opposite moving directions. The gradient of the document in the positive direction pushes it toward the higher rank position of the sorted list, while the gradient of the document in the negative direction pushes it toward the lower rank position of the sorted list.λ - M A R T algorithm optimizes the gradient λi of each document di for each query q. For a given query q, if the relevance grade ri between di and q is higher, and the ranked position of di is more closed to the bottom of the ranked list, then the positive value of λi indicates a push toward the top of the ranked list, and a bigger value of λi represents a stronger force. Similarly, we can understand the opposite case.λ - M A R T algorithm integrates the evaluation criteria of information retrieval (such as NDCG [23]) into the gradient computation. The gradient λi for each document di is obtained by the summation of all λij over all pairs of di,dj that di participates in for query q; that is, λi is computed as follows:(1)λi=∑j:i,j∈Iλij-∑j:j,i∈IλijIn (1), λij denotes the gradient of the document-pair di,dj and is calculated as follows:(2)λij=-β1+eβ×si-sj×ΔMijwhere β is a shape parameter for the sigmoid function, si and sj represent the score assigned to di and dj by the ranking model, respectively, and ΔMij represents the change on the effectiveness measure M by swapping the two documents di and dj at the rank positions i and j accordingly (while keeping the rank positions of all other documents unchanged). The effectiveness evaluation criteria can be measured by any common information retrieval metrics such as NDCG [23] and ERR [24]. ΔMij is calculated as follows:(3)ΔMij=Mq-Mq∗where Mq denotes the effectiveness of the query q for a ranked list of all documents with respect to q and Mq∗ denotes the effectiveness of q after swapping di and dj at the rank positions i and j for the ranked list. λ-MART algorithm incorporates an effectiveness evaluation criterion into the gradient function in the training process of the ranking models, and thus it optimizes both the loss function and the effectiveness evaluation criterion.


### 3.2. Improvement of the Gradient Function

In theλ-MART algorithm, we treat all queries unequally in the training process of the ranking models. We discriminate the effectiveness score of each query and assign different weights to different queries. In order to highlight the gradients of rich queries and enhance the effectiveness of rich queries, the weights of rich queries should be given a higher value based on the idea of the Matthew effect. Therefore, we define the weight of a query as the (t-1)-th power of the original effectiveness score of the query, where t is an integer and is bigger than 1. The greater the value of t, the greater the difference between the assigned weights of the rich query and the poor query. Therefore, our method can reflect the importance of rich query in the ranking model, and thus the Matthew effect of the ranking model is highlighted to a certain extent. Thus, the new effectiveness score of a query is defined as the t-th power of the original effectiveness score of the query, and the original effectiveness M of the gradient is replaced by Mt to optimize the rich ranking model as a new objective. Therefore, ΔMij is replaced by ΔMij∗ that is defined as follows:(4)ΔMij∗=Mqt-Mq∗tΔMij∗ denotes the difference of the t-th power value of the effectiveness of q after swapping di and dj at the rank positions i and j (while fixing the rank positions of all other documents). For example, when t=2, we have that ΔMij∗=(Mq)2-(Mq∗)2, and when t=3, we have that ΔMij∗=(Mq)3-(Mq∗)3. When the hyperparameter t> 1, the power operation enhances Matthew effect. Because the ranking effectiveness measure M is changed into Mt, the difference of effectiveness Mt becomes more prominent with the increase of t, and then the effectiveness of Matthew effect is more obvious in the learning process.Meanwhile, we incorporate theGini coefficient into the gradient in order to highlight the difference in effectiveness for different queries in the ranking model. Consequently, λijnew is defined as follows:(5)λijnew=-β×k×eGini1+eβ×si-sj×ΔMij∗where the positive constant k is used to adjust the value of λijnew in order to make λijnew and λij in the same order of magnitude. Gini measures the degree of difference in effectiveness among all queries and will be introduced in the next section. The different document-pair di,dj for each query is optimized according to the new gradient λijnew in the learning process of ranking models, which strengthens the differences of upward or downward ranking force among the document-pairs for different queries in the next iteration and thus enhances the optimization of rich queries and weakens the optimization of poor queries and highlights the effectiveness of Matthew effect.The gradient function ofλ-MART is changed and we must prove its consistency, which guarantees that our improved λ-MART algorithm can be used to produce the ranking models. Now, we prove that the new objective Mt satisfies a desirable consistency property proposed in [5, 6]: when swapping the ranked positions of two documents di and dj in a ranked list of documents where di is more relevant than dj but di is ranked after dj, the optimization objective should be increased. In other words, for any document-pairs, the pairwise swap between the correctly ranked documents di and dj for the same query q must lead to a decrease of Mt, and the pairwise swap between the incorrectly ranked documents di and dj for the same query q must lead to an increase of Mt.Theorem 1.
The new optimization objective functionMt satisfies the consistency property.Proof.
According to the previous analysis, we know thatMq is the effectiveness of q for a ranked list of all documents with respect to q, Mq∗ is the effectiveness of q after swapping di and dj for the ranked list such that Mq≥0 and Mq∗≥0, and ΔMij∗ is the changed effectiveness on the new optimization objective Mt by swapping di and dj at the rank positions i and j while leaving all other ranks unchanged in the ranked list. Furthermore, ΔMij∗ can be expanded according to n variance formula in factorization; namely, an-bn=(a-b)(an-1+an-2b+⋯+abn-2+bn-1). Therefore, (4) becomes(6)ΔMij∗=Mq-Mq∗×Mqt-1+Mqt-2×Mq∗+⋯+Mq×Mq∗t-2+Mq∗t-1Let P(t)=Mq(t-1)+Mq(t-2)×Mq∗+⋯+Mq×(Mq∗)(t-2)+(Mq∗)(t-1). Then (6) is rewritten according to (3) as follows:(7)ΔMij∗=ΔMij×Pt
To demonstrate thatMt satisfies the consistency property, we only need to show that the change in ΔMij∗ tends to move in the same direction with the change in ΔMij of the original optimization objective M if the positions of di and dj are swapped. This is because the original optimization objective M satisfies the consistency property and can be directly optimized by the λ-MART algorithm.
We know that no matter which kind of commonly used measure of effectivenessMq and Mq∗ is taken in the information retrieval field, their values are both greater than or equal to 0; that is, Mq≥0 and Mq∗≥0. Therefore, P(t)≥0 when t>1. Hence, the directions of changes of ΔMij∗ and ΔMij are the same according to (7). The bigger value of M indicates that it has better effectiveness in the original λ-MART algorithm, and the bigger value of Mt indicates that it has also better effectiveness in our improved λ-MART algorithm. Therefore, the optimization directions of M and Mt are also the same. Therefore, the new optimization objective Mt with the improved gradient satisfies the required consistency property, and it can also be optimized by using the improved λ-MART algorithm.


### 3.3. A Strategy of Evaluating the Current Ranking Model

In the traditional algorithms of LTR, the strategy of evaluating the current ranking models is directly calculated by the effectiveness measureM, such as NDCG [23] and ERR [24], at each learning iteration, which is difficult to reflect the Matthew effect of ranking models. To reflect the Matthew effect, we propose a strategy of evaluating the current ranking models by integrating the Gini coefficient and the new optimization objective Mt. The strategy is that we use k×eGini×Mt to compute the scores of the current ranking model on the training and validation datasets and evaluate the total score of the current ranking model to measure its performance in each iteration of training ranking models. After the end of training, an optimal ranking model is chosen by using the training and validation datasets. The ranking model with the maximum value of the sum of k×eGini×Mt on the training and validation datasets is selected as our final one.


### 3.4. A Strategy of Dynamically Decreasing the Learning Rate

How to choose a learning rate is a critical issue. The fixed learning rate may lead to a slow convergence for a gradient decent algorithm [25]. Generally, the value of learning rate (i.e., shrinkage coefficient) has an influence on the speed of convergence for some LTR algorithms with shrinkage coefficient, which directly affects their efficiency and effectiveness to a certain extent. In the λ-MART algorithm, the learning rate η is unchanged during the gradient boosting process; that is, the learning rate is a constant over training iterations. This fixed learning rate is not conducive to the acceleration of convergence when the optimization result has not yet reached the convergence in a given number of iterations. Therefore, the performance of ranking model is decreased at the case of the fixed learning rate if the iteration is not sufficient. In order to overcome the shortcoming, we propose a strategy of dynamically decreasing learning rate to update the weights. The fixed learning rate η in the λ-MART algorithm is replaced by a dynamical learning rate ηiter∗:(8)ηiter∗=ηmax-ηmax-ηmin×iterntrees-1where ηmax and ηmin denote the maximum and minimum learning rates, respectively, ntrees represents the total number of trees or boosting iterations, and iter∈[0,ntrees-1] represents the current number of iterations or the iter-th tree. ηiter∗ represents the learning rate at iteration iter-th. From the definition of ηiter∗, we can know that this strategy starts the training process with the given maximum learning rate ηmax, and the learning rate is being shrunk gradually, while these trees are being established. When the learning rate decreases to the given minimum value ηmin, the training process terminates.η i t e r ∗ is asymptotically decreased throughout the whole training. It is beneficial to speed up the convergence and improves the effectiveness of the ranking model. Because the produced ranking models are rough in the early stages of the training process, using a relatively high learning rate to train ranking models can speed up the convergence and avoid a local minima. A large value of the shrinkage coefficient can speed up the initial improvement when the algorithm does not converge. Because the produced ranking models are fine in the late stage of the training process, using a relatively low learning rate to refine ranking models can improve a local search and help it converge to a better optimizing point. A small value of the shrinkage coefficient can lead to a better performance when the algorithm is gradually close to convergence.


### 3.5. Complexity Analysis

In the originalλ-MART algorithm, the time complexity of the algorithm is O(m∗(ntrees+L)), where m represents the number of training samples, ntrees represents the total number of trees, and L represents the number of leaves per tree. In our improved λ-MART algorithm, we have improved the gradient and proposed strategies of evaluating a ranking model and dynamically decreasing the learning rate, but these improvements only modify the related computing methods, which do not affect the time complexity of the algorithm; that is, the time complexity of our improved λ-MART algorithm is also O(m∗(ntrees+L)).In addition, if no performance gain on the validation data is observed in the set number of rounds during the process of learning, then the training process terminates in the originalλ-MART algorithm. Our strategy of dynamically decreasing the learning rate may lead to an early stop with a greater probability and then accelerate the convergence of the algorithm. Therefore, the total number of iterations or computational time cost of our improved λ-MART algorithm is reduced in most cases, as shown in Figure 12.


## 3.1. The Gradient ofλ-MART Algorithm

The basic idea ofλ-MART [5, 6] is to train an ensemble of weak learners by using MART and approximate Newton step and linearly combining their predictions into a stronger and more effective learner. λ-MART tunes the gradients of the regression trees based on a gradient-based optimization method. The gradient function is calculated according to the selected evaluation metric of effectiveness, and this metric is optimized directly in the training process of a ranking model.The key of theλ-MART algorithm is the gradient function λ which is defined as a smooth approximation to the gradient of a target cost with respect to the score of a document. The gradient function quantifies the adjusted direction (up or down) and the force of a “to-be-sorted” document in the next iteration. The two documents of any given document-pair have the equal gradient values but opposite moving directions. The gradient of the document in the positive direction pushes it toward the higher rank position of the sorted list, while the gradient of the document in the negative direction pushes it toward the lower rank position of the sorted list.λ - M A R T algorithm optimizes the gradient λi of each document di for each query q. For a given query q, if the relevance grade ri between di and q is higher, and the ranked position of di is more closed to the bottom of the ranked list, then the positive value of λi indicates a push toward the top of the ranked list, and a bigger value of λi represents a stronger force. Similarly, we can understand the opposite case.λ - M A R T algorithm integrates the evaluation criteria of information retrieval (such as NDCG [23]) into the gradient computation. The gradient λi for each document di is obtained by the summation of all λij over all pairs of di,dj that di participates in for query q; that is, λi is computed as follows:(1)λi=∑j:i,j∈Iλij-∑j:j,i∈IλijIn (1), λij denotes the gradient of the document-pair di,dj and is calculated as follows:(2)λij=-β1+eβ×si-sj×ΔMijwhere β is a shape parameter for the sigmoid function, si and sj represent the score assigned to di and dj by the ranking model, respectively, and ΔMij represents the change on the effectiveness measure M by swapping the two documents di and dj at the rank positions i and j accordingly (while keeping the rank positions of all other documents unchanged). The effectiveness evaluation criteria can be measured by any common information retrieval metrics such as NDCG [23] and ERR [24]. ΔMij is calculated as follows:(3)ΔMij=Mq-Mq∗where Mq denotes the effectiveness of the query q for a ranked list of all documents with respect to q and Mq∗ denotes the effectiveness of q after swapping di and dj at the rank positions i and j for the ranked list. λ-MART algorithm incorporates an effectiveness evaluation criterion into the gradient function in the training process of the ranking models, and thus it optimizes both the loss function and the effectiveness evaluation criterion.


## 3.2. Improvement of the Gradient Function

In theλ-MART algorithm, we treat all queries unequally in the training process of the ranking models. We discriminate the effectiveness score of each query and assign different weights to different queries. In order to highlight the gradients of rich queries and enhance the effectiveness of rich queries, the weights of rich queries should be given a higher value based on the idea of the Matthew effect. Therefore, we define the weight of a query as the (t-1)-th power of the original effectiveness score of the query, where t is an integer and is bigger than 1. The greater the value of t, the greater the difference between the assigned weights of the rich query and the poor query. Therefore, our method can reflect the importance of rich query in the ranking model, and thus the Matthew effect of the ranking model is highlighted to a certain extent. Thus, the new effectiveness score of a query is defined as the t-th power of the original effectiveness score of the query, and the original effectiveness M of the gradient is replaced by Mt to optimize the rich ranking model as a new objective. Therefore, ΔMij is replaced by ΔMij∗ that is defined as follows:(4)ΔMij∗=Mqt-Mq∗tΔMij∗ denotes the difference of the t-th power value of the effectiveness of q after swapping di and dj at the rank positions i and j (while fixing the rank positions of all other documents). For example, when t=2, we have that ΔMij∗=(Mq)2-(Mq∗)2, and when t=3, we have that ΔMij∗=(Mq)3-(Mq∗)3. When the hyperparameter t> 1, the power operation enhances Matthew effect. Because the ranking effectiveness measure M is changed into Mt, the difference of effectiveness Mt becomes more prominent with the increase of t, and then the effectiveness of Matthew effect is more obvious in the learning process.Meanwhile, we incorporate theGini coefficient into the gradient in order to highlight the difference in effectiveness for different queries in the ranking model. Consequently, λijnew is defined as follows:(5)λijnew=-β×k×eGini1+eβ×si-sj×ΔMij∗where the positive constant k is used to adjust the value of λijnew in order to make λijnew and λij in the same order of magnitude. Gini measures the degree of difference in effectiveness among all queries and will be introduced in the next section. The different document-pair di,dj for each query is optimized according to the new gradient λijnew in the learning process of ranking models, which strengthens the differences of upward or downward ranking force among the document-pairs for different queries in the next iteration and thus enhances the optimization of rich queries and weakens the optimization of poor queries and highlights the effectiveness of Matthew effect.The gradient function ofλ-MART is changed and we must prove its consistency, which guarantees that our improved λ-MART algorithm can be used to produce the ranking models. Now, we prove that the new objective Mt satisfies a desirable consistency property proposed in [5, 6]: when swapping the ranked positions of two documents di and dj in a ranked list of documents where di is more relevant than dj but di is ranked after dj, the optimization objective should be increased. In other words, for any document-pairs, the pairwise swap between the correctly ranked documents di and dj for the same query q must lead to a decrease of Mt, and the pairwise swap between the incorrectly ranked documents di and dj for the same query q must lead to an increase of Mt.Theorem 1.
The new optimization objective functionMt satisfies the consistency property.Proof.
According to the previous analysis, we know thatMq is the effectiveness of q for a ranked list of all documents with respect to q, Mq∗ is the effectiveness of q after swapping di and dj for the ranked list such that Mq≥0 and Mq∗≥0, and ΔMij∗ is the changed effectiveness on the new optimization objective Mt by swapping di and dj at the rank positions i and j while leaving all other ranks unchanged in the ranked list. Furthermore, ΔMij∗ can be expanded according to n variance formula in factorization; namely, an-bn=(a-b)(an-1+an-2b+⋯+abn-2+bn-1). Therefore, (4) becomes(6)ΔMij∗=Mq-Mq∗×Mqt-1+Mqt-2×Mq∗+⋯+Mq×Mq∗t-2+Mq∗t-1Let P(t)=Mq(t-1)+Mq(t-2)×Mq∗+⋯+Mq×(Mq∗)(t-2)+(Mq∗)(t-1). Then (6) is rewritten according to (3) as follows:(7)ΔMij∗=ΔMij×Pt
To demonstrate thatMt satisfies the consistency property, we only need to show that the change in ΔMij∗ tends to move in the same direction with the change in ΔMij of the original optimization objective M if the positions of di and dj are swapped. This is because the original optimization objective M satisfies the consistency property and can be directly optimized by the λ-MART algorithm.
We know that no matter which kind of commonly used measure of effectivenessMq and Mq∗ is taken in the information retrieval field, their values are both greater than or equal to 0; that is, Mq≥0 and Mq∗≥0. Therefore, P(t)≥0 when t>1. Hence, the directions of changes of ΔMij∗ and ΔMij are the same according to (7). The bigger value of M indicates that it has better effectiveness in the original λ-MART algorithm, and the bigger value of Mt indicates that it has also better effectiveness in our improved λ-MART algorithm. Therefore, the optimization directions of M and Mt are also the same. Therefore, the new optimization objective Mt with the improved gradient satisfies the required consistency property, and it can also be optimized by using the improved λ-MART algorithm.


## 3.3. A Strategy of Evaluating the Current Ranking Model

In the traditional algorithms of LTR, the strategy of evaluating the current ranking models is directly calculated by the effectiveness measureM, such as NDCG [23] and ERR [24], at each learning iteration, which is difficult to reflect the Matthew effect of ranking models. To reflect the Matthew effect, we propose a strategy of evaluating the current ranking models by integrating the Gini coefficient and the new optimization objective Mt. The strategy is that we use k×eGini×Mt to compute the scores of the current ranking model on the training and validation datasets and evaluate the total score of the current ranking model to measure its performance in each iteration of training ranking models. After the end of training, an optimal ranking model is chosen by using the training and validation datasets. The ranking model with the maximum value of the sum of k×eGini×Mt on the training and validation datasets is selected as our final one.


## 3.4. A Strategy of Dynamically Decreasing the Learning Rate

How to choose a learning rate is a critical issue. The fixed learning rate may lead to a slow convergence for a gradient decent algorithm [25]. Generally, the value of learning rate (i.e., shrinkage coefficient) has an influence on the speed of convergence for some LTR algorithms with shrinkage coefficient, which directly affects their efficiency and effectiveness to a certain extent. In the λ-MART algorithm, the learning rate η is unchanged during the gradient boosting process; that is, the learning rate is a constant over training iterations. This fixed learning rate is not conducive to the acceleration of convergence when the optimization result has not yet reached the convergence in a given number of iterations. Therefore, the performance of ranking model is decreased at the case of the fixed learning rate if the iteration is not sufficient. In order to overcome the shortcoming, we propose a strategy of dynamically decreasing learning rate to update the weights. The fixed learning rate η in the λ-MART algorithm is replaced by a dynamical learning rate ηiter∗:(8)ηiter∗=ηmax-ηmax-ηmin×iterntrees-1where ηmax and ηmin denote the maximum and minimum learning rates, respectively, ntrees represents the total number of trees or boosting iterations, and iter∈[0,ntrees-1] represents the current number of iterations or the iter-th tree. ηiter∗ represents the learning rate at iteration iter-th. From the definition of ηiter∗, we can know that this strategy starts the training process with the given maximum learning rate ηmax, and the learning rate is being shrunk gradually, while these trees are being established. When the learning rate decreases to the given minimum value ηmin, the training process terminates.η i t e r ∗ is asymptotically decreased throughout the whole training. It is beneficial to speed up the convergence and improves the effectiveness of the ranking model. Because the produced ranking models are rough in the early stages of the training process, using a relatively high learning rate to train ranking models can speed up the convergence and avoid a local minima. A large value of the shrinkage coefficient can speed up the initial improvement when the algorithm does not converge. Because the produced ranking models are fine in the late stage of the training process, using a relatively low learning rate to refine ranking models can improve a local search and help it converge to a better optimizing point. A small value of the shrinkage coefficient can lead to a better performance when the algorithm is gradually close to convergence.


## 3.5. Complexity Analysis

In the originalλ-MART algorithm, the time complexity of the algorithm is O(m∗(ntrees+L)), where m represents the number of training samples, ntrees represents the total number of trees, and L represents the number of leaves per tree. In our improved λ-MART algorithm, we have improved the gradient and proposed strategies of evaluating a ranking model and dynamically decreasing the learning rate, but these improvements only modify the related computing methods, which do not affect the time complexity of the algorithm; that is, the time complexity of our improved λ-MART algorithm is also O(m∗(ntrees+L)).In addition, if no performance gain on the validation data is observed in the set number of rounds during the process of learning, then the training process terminates in the originalλ-MART algorithm. Our strategy of dynamically decreasing the learning rate may lead to an early stop with a greater probability and then accelerate the convergence of the algorithm. Therefore, the total number of iterations or computational time cost of our improved λ-MART algorithm is reduced in most cases, as shown in Figure 12.


## 4. Evaluation Measures of Matthew Effect

A ranking model is richer than another model if (1) the former has both more rich queries and more poor queries than the latter, or (2) the distribution of the effectiveness of queries of the former is more discrete than the latter. A richer model is of a stronger Matthew effect. In order to measure the performances of the ranking model yielded by our improved method, we introduce the following utility metrics to characterize the Matthew effect of ranking models from different perspectives. Based on the effectiveness evaluation criteria for information retrieval, we introduce Gini coefficient, mean-variance, and quantity statistics to measure the performances.


### 4.1. Gini Coefficient

The Gini coefficient [26, 27] is a measure of the statistical dispersion that represents the income distribution of the residents in a nation. It was developed by the Italian statistician and sociologist Corrado Gini in 1912. The Gini coefficient is usually defined mathematically based on the Lorenz curve and is most easily calculated from unordered size data as the “relative mean difference” divided by the mean size μ. The “relative mean difference” is the mean of the difference between every possible pair of individuals. The Gini coefficient is calculated using the following formula: (9)G=∑i=1n∑j=1nxi-xj2n2μwhere xi denotes the income of individual i, xi-xj denotes the absolute value of the difference between xi and xj, μ denotes the mean value of all individuals’ incomes, and n denotes the total number of individuals. The smaller the inequality of income, the smaller the value of the Gini coefficient, and vice versa.Matthew effect is reflected by using Gini coefficients for the measurement in many economic areas. Gini coefficient can capture the Matthew Effect, which can be used to measure the performance of the ranking model. If we make an analogy with the distribution of the national income in the field of finance, the query in the LTR task resembles the individual in the distribution of the national income, and the effectiveness of the query resembles the income of the individual. Therefore, the Gini coefficient of LTR can be defined as follows:(10)Gini=∑i=1Q∑j=1QMqi-Mqj2Q∑k=1QMqkwhere qi∈Q denotes the i-th query, Q represents the total number of queries in query set Q, and Mqi represents the effectiveness of qi. Gini is used to measure the degree of difference in effectiveness among all the queries in a ranking model and reflects the Matthew effect. If the value of Gini obtained by a ranking model is larger, then the ranking model has a stronger Matthew effect.


### 4.2. Mean-Variance

Mean is the average value of all random variables. In order to observe the effectiveness of a ranking model, the meanμ of a ranking model is defined as follows:(11)μ=1Q∑q∈QMqFor a ranking model,μ measures the average effectiveness (such as NDCG [23] and ERR [24]) of all queries in the query set; that is, it refers to the average effectiveness of the ranking model. The greater μ, the better the average effectiveness of the ranking model, and vice versa.Variance is used to measure the degree of deviation between a set of random variables and their mean, and thus it is an important and common metric for calculating the discrete trend. The greater the variance, the greater the degree of deviation, and vice versa.In a ranking model, some queries are of high effectiveness but some queries are of low effectiveness. Therefore, in order to observe the degrees of their deviation, we divide the variance into the upside semivariance and the downside semivariance. The upside semivarianceVup and the downside semivariance Vdown of a ranking model are defined as follows:(12)Vup=1Q+∑q∈Q+Mq-μ2(13)Vdown=1Q-∑q∈Q-Mq-μ2where Q+ and Q- denote the set of queries with above-mean effectiveness and below-mean effectiveness in the query set Q, respectively, and Q+ and Q- denote the number of sets of queries Q+ and Q-, respectively.For a ranking model,Vup measures the discrete degree of effectiveness of the queries that are over the value of μ, and Vdown measures the discrete degree of effectiveness of the queries that are under the value of μ. The Matthew effect of a ranking model can be reflected by its Vup and Vdown. The higher the values of both Vup and Vdown of a ranking model, the stronger the Matthew effect of the ranking model, and vice versa.


### 4.3. Quantity Statistics

Generally, for most of the effectiveness metrics in information retrieval, the range of their values is between 0 and 1, such asNDCG [23] and ERR [24]. To compute the effectiveness distribution of all queries in a query set, the range of values of the effectiveness is divided into 4 intervals: [0.0,0.1], (0.1,0.4], (0.4,0.7], and (0.7,1.0]. We compute the number of queries in these different intervals according to the effectiveness values of the queries in a given query set for different ranking models, and the purpose is to evaluate the strengths of their Matthew effects. We use an array count to express the quantity statistics of different intervals for the effectiveness of queries, and count is defined as follows:(14)counti=∑Mq∈0.0,0.1,q∈Q1i=0∑Mq∈0.1,0.4,q∈Q1i=1∑Mq∈0.4,0.7,q∈Q1i=2∑Mq∈0.7,1.0,q∈Q1i=3If the values ofcount[0] and count[3] of a ranking model are larger, then the ranking model has a stronger Matthew effect.


## 4.1. Gini Coefficient

The Gini coefficient [26, 27] is a measure of the statistical dispersion that represents the income distribution of the residents in a nation. It was developed by the Italian statistician and sociologist Corrado Gini in 1912. The Gini coefficient is usually defined mathematically based on the Lorenz curve and is most easily calculated from unordered size data as the “relative mean difference” divided by the mean size μ. The “relative mean difference” is the mean of the difference between every possible pair of individuals. The Gini coefficient is calculated using the following formula: (9)G=∑i=1n∑j=1nxi-xj2n2μwhere xi denotes the income of individual i, xi-xj denotes the absolute value of the difference between xi and xj, μ denotes the mean value of all individuals’ incomes, and n denotes the total number of individuals. The smaller the inequality of income, the smaller the value of the Gini coefficient, and vice versa.Matthew effect is reflected by using Gini coefficients for the measurement in many economic areas. Gini coefficient can capture the Matthew Effect, which can be used to measure the performance of the ranking model. If we make an analogy with the distribution of the national income in the field of finance, the query in the LTR task resembles the individual in the distribution of the national income, and the effectiveness of the query resembles the income of the individual. Therefore, the Gini coefficient of LTR can be defined as follows:(10)Gini=∑i=1Q∑j=1QMqi-Mqj2Q∑k=1QMqkwhere qi∈Q denotes the i-th query, Q represents the total number of queries in query set Q, and Mqi represents the effectiveness of qi. Gini is used to measure the degree of difference in effectiveness among all the queries in a ranking model and reflects the Matthew effect. If the value of Gini obtained by a ranking model is larger, then the ranking model has a stronger Matthew effect.


## 4.2. Mean-Variance

Mean is the average value of all random variables. In order to observe the effectiveness of a ranking model, the meanμ of a ranking model is defined as follows:(11)μ=1Q∑q∈QMqFor a ranking model,μ measures the average effectiveness (such as NDCG [23] and ERR [24]) of all queries in the query set; that is, it refers to the average effectiveness of the ranking model. The greater μ, the better the average effectiveness of the ranking model, and vice versa.Variance is used to measure the degree of deviation between a set of random variables and their mean, and thus it is an important and common metric for calculating the discrete trend. The greater the variance, the greater the degree of deviation, and vice versa.In a ranking model, some queries are of high effectiveness but some queries are of low effectiveness. Therefore, in order to observe the degrees of their deviation, we divide the variance into the upside semivariance and the downside semivariance. The upside semivarianceVup and the downside semivariance Vdown of a ranking model are defined as follows:(12)Vup=1Q+∑q∈Q+Mq-μ2(13)Vdown=1Q-∑q∈Q-Mq-μ2where Q+ and Q- denote the set of queries with above-mean effectiveness and below-mean effectiveness in the query set Q, respectively, and Q+ and Q- denote the number of sets of queries Q+ and Q-, respectively.For a ranking model,Vup measures the discrete degree of effectiveness of the queries that are over the value of μ, and Vdown measures the discrete degree of effectiveness of the queries that are under the value of μ. The Matthew effect of a ranking model can be reflected by its Vup and Vdown. The higher the values of both Vup and Vdown of a ranking model, the stronger the Matthew effect of the ranking model, and vice versa.


## 4.3. Quantity Statistics

Generally, for most of the effectiveness metrics in information retrieval, the range of their values is between 0 and 1, such asNDCG [23] and ERR [24]. To compute the effectiveness distribution of all queries in a query set, the range of values of the effectiveness is divided into 4 intervals: [0.0,0.1], (0.1,0.4], (0.4,0.7], and (0.7,1.0]. We compute the number of queries in these different intervals according to the effectiveness values of the queries in a given query set for different ranking models, and the purpose is to evaluate the strengths of their Matthew effects. We use an array count to express the quantity statistics of different intervals for the effectiveness of queries, and count is defined as follows:(14)counti=∑Mq∈0.0,0.1,q∈Q1i=0∑Mq∈0.1,0.4,q∈Q1i=1∑Mq∈0.4,0.7,q∈Q1i=2∑Mq∈0.7,1.0,q∈Q1i=3If the values ofcount[0] and count[3] of a ranking model are larger, then the ranking model has a stronger Matthew effect.


## 5. Experiments

In order to illustrate the advantages of our improvedλ-MART algorithm (named as Matthew-λ-MART), we implement the algorithm based on the open-source RankLib library of LTR algorithms developed by Van Dang et al. (http://sourceforge.net/p/lemur/code/HEAD/tree/RankLib/trunk/). We conduct extensive experiments to evaluate and compare the ranking performance of Matthew-λ-MART with three well-known LTR algorithms, λ-MART [5, 6], RankBoost [11], and AdaRank [12], over three standard benchmark LTR datasets (including one large scale LTR dataset: MSLR-WEB30K (http://research.microsoft.com/en-us/projects/mslr/download.aspx), with 30000 queries and a total of 136 features in the Microsoft LTR datasets and two small LTR datasets, MQ2007 (http://research.microsoft.com/en-us/um/beijing/projects/letor/letor4dataset.aspx), with 1692 queries and a total of 46 features in the LETOR 4.0 datasets, and WCL2R with 79 queries and a total of 29 features released by Alcântara et al. [28], which includes click-through features. In order to make the order of magnitude of the gradient’s value and the learning rate in Matthew-λ-MART be the same as λ-MART’s, we set parameters for Matthew-λ-MART as follows: t=2 or 3, k=100, ηmax=0.3, and ηmin=0.1, where k, t, ηmax, and ηmin are introduced in Section 3. We denote Matthew-λ-MART as Matthew2-λ-MART and Matthew3-λ-MART when t=2 and t=3, respectively. The values of other parameters of Matthew-λ-MART are the same as λ-MART’s. We use NDCG [23] as the effectiveness optimization criterion during the training process for each LTR algorithm and each dataset. Based on the produced ranking models, we calculate the effectiveness measures μ (including NDCG and ERR) and our introduced Matthew effect measures (including Gini, Vup, Vdown, count[0], and count[3] according to (10), (12), (13), and (14)). These results are shown in Figures 1–9. All experimental results are summed on these five folds for the test dataset. Meanwhile, the comprehensive evaluations are conducted and the performance of the strategy of dynamically decreasing the learning rate is also evaluated. These results are shown in Figures 10–12.Figure 1
μ of each algorithm on MSLR-WEB30K dataset.Figure 2
G i n i of each algorithm on MSLR-WEB30K dataset.Figure 3
V u p of each algorithm on MSLR-WEB30K dataset.Figure 4
V d o w n of each algorithm on MSLR-WEB30K dataset.Figure 5
c o u n t [ 0 ] of each algorithm on MSLR-WEB30K dataset.Figure 6
c o u n t [ 3 ] of each algorithm on MSLR-WEB30K dataset.Figure 7
μ, Gini, Vup, and Vdown of each algorithm on WCL2R dataset.Figure 8
μ, Gini, Vup, and Vdown of each algorithm on MQ2007 dataset.Figure 9
c o u n t [ 0 ] and count[3] of each algorithm on WCL2R and MQ2007 datasets.Figure 10
W N p of each algorithm on effectiveness and Matthew effect.Figure 11
μ for different strategies of learning rate in λ-MART.Figure 12
The total number of iterations for different strategies of learning rate inλ-MART.


### 5.1. Experiments on Large Dataset: MSLR-WEB30K

Figures1–6 provide the total results of five folds on MSLR-WEB30K dataset in terms of μ, Gini, Vup, Vdown, count[0], and count[3] for different LTR algorithms, respectively.From meanμ (including NDCG@20, NDCG@10, NDCG@5, ERR@20, ERR@10, and ERR@5) in Figure 1, we can see that the values of μ obtained by Matthew2-λ-MART are bigger than Matthew3-λ-MART, λ-MART, RankBoost, and AdaRank. These results show that Matthew2-λ-MART obtains the highest and best effectiveness. There are two main reasons. One is that Matthew-λ-MART incorporates the effectiveness evaluation measures Mt into the gradient and combines the overall scores k×eGini×Mt on training and validation datasets to choose a ranking model as the final ranking model. The other one is that Matthew-λ-MART uses the strategy of dynamically decreasing a learning rate to obtain an optimal tree. The main reason why the effectiveness of Matthew2-λ-MART outperforms Matthew3-λ-MART is that the enhancement of the Matthew effect of a ranking model usually reduces its effectiveness of the ranking model, while Matthew3-λ-MART with t=3 is more able to strengthen the differences of the gradients and the differences of the effectiveness of queries than Matthew2-λ-MART with t=2. Therefore, Matthew3-λ-MART strengthens the optimization of Matthew effect more than Matthew2-λ-MART does.From Gini coefficientGini in Figure 2, Matthew2-λ-MART and Matthew3-λ-MART both obtain a bigger value than λ-MART. These results show that the effectiveness across different individual queries in Matthew-λ-MART has a greater difference and thus indicates that the ranking model trained by Matthew-λ-MART has a stronger Matthew effect than λ-MART. Figure 2 also indicates that the values of Gini of Matthew3-λ-MART are bigger than the one of Matthew2-λ-MART. The main reason is that the value of t in Matthew3-λ-MART is bigger than that in Matthew2-λ-MART. The bigger the value of t, the greater the difference between the assigned weights of the rich query and the poor query. Therefore, the rich query can get more optimization than the poor query in the process of learning a ranking model. Therefore, Matthew3-λ-MART strengthens the optimization of Matthew effect compared to Matthew2-λ-MART, and the Matthew effect of Matthew3-λ-MART is highlighted to a certain extent.From Figures3 and 4, the values of variances Vup and Vdown generated by Matthew2-λ-MART and Matthew3-λ-MART are bigger than λ-MART, RankBoost, and AdaRank in most of cases (except that the values of Vup generated by Matthew2-λ-MART and Matthew3-λ-MART are smaller than RankBoost and AdaRank in terms of NDCG@20, NDCG@10, and NDCG@5, and the value of Vup generated by Matthew3-λ-MART is smaller than λ-MART in terms of ERR@5). These results demonstrate that the effectiveness across different individual queries in Matthew-λ-MART has also a greater difference generally. Therefore, the ranking model trained by Matthew-λ-MART usually exhibits a stronger Matthew effect than λ-MART, RankBoost, and AdaRank.From Figures5 and 6, the values of count[3] with regard to rich queries and count[0] with regard to poor queries obtained by Matthew2-λ-MART and Matthew3-λ-MART are bigger than λ-MART, RankBoost, and AdaRank in most of cases. These results show that Matthew-λ-MART leads to a relative polarization, thereby further exhibiting a stronger Matthew effect than λ-MART in general.SinceMatthew-λ-MART highlights the corresponding differences of upward or downward ranking force between documents with regard to rich queries with high effectiveness and documents with regard to poor queries with low effectiveness, it strengthens the optimization of rich queries and weakens the optimization of poor queries in the training process of the ranking models. Consequently, more forces are used to optimize the ranked positions of the documents in the rich queries and less for the poor queries. Finally, Matthew-λ-MART increases the degree of difference or dispersion in the effectiveness across all the queries. Therefore, the ranking model trained by Matthew-λ-MART shows a stronger Matthew effect than λ-MART.


### 5.2. Experiments on Small Datasets: WCL2R and MQ2007

Wu et.al. [5] have pointed out that smaller trees and shrinkage may be used if the training dataset is smaller. WCL2R with 79 queries and MQ2007 with 1692 queries are small datasets, so we set parameters for Matthew-λ-MART as follows: ntrees=200, ηmax=0.1, and ηmin=0.05, where ntrees represents the number of trees. We use NDCG@5 as the effectiveness optimization criterion during the training process on WCL2R and MQ2007 for these LTR algorithms. Figures 7–9 provide the overall results of five folds on the two datasets in terms of measures μ, Gini, Vup, Vdown, count[0], and count[3] for these LTR algorithms, respectively. These results also show that the Matthew-λ-MART algorithm performs better than others in most cases.


### 5.3. The Comprehensive Evaluation: Winning Number

We use the winning numberWNp to comprehensively evaluate the effectiveness and Matthew effect of LTR algorithms. WNp is introduced by Liu [29], which counts the times a method beats other ones over all datasets. We extend WNp to a cross-measure for each LTR algorithm, which counts the times a method beats other ones over all measures and datasets. We redefine WNP as follows: (15)WNP=∑i=1R∑j=1S∑k=1,k≠PNIMeasjPi>Measjkiwhere N is the number of the compared methods, P and k are the indices of the compared methods, R is the number of LTR datasets, i is the index of an LTR dataset, S is the number of measures, j is the index of a measure, Measjk(i) is the performance of the k-th method on the i-th dataset in terms of the j-th measure, and I(·) is an indicator function such that (16)IMeasjPi>Measjki=1ifMeasjPi>Measjki,0otherwise.WNP is a comprehensive evaluation of ranking performance. The larger WNP is, the better the P-th method performs.Figure10 shows WNp for these LTR algorithms on the three datasets in terms of the effectiveness (i.e., μ, including NDCG@20, NDCG@10, NDCG@5, ERR@20, ERR@10, and ERR@5) and Matthew effect (including Gini, Vup, Vdown, count[0], and count[3]). From this figure, we can observe the following facts:(1) In terms ofWNp of effectiveness, Matthew2-λ-MART and Matthew3-λ-MART are better than λ-MART, RankBoost, and AdaRank, and λ-MART is better than RankBoost and AdaRank.(2) In terms ofWNp of Matthew effect, Matthew2-λ-MART and Matthew3-λ-MART are also better than λ-MART, RankBoost, and AdaRank, but λ-MART is worse than RankBoost and AdaRank.


### 5.4. Performance of the Strategy of Dynamically Decreasing the Learning Rate

We conduct experiments on the MSLR-WEB30K dataset to evaluate the advantage of the strategy of dynamically decreasing the learning rate; that is, the effectiveness and convergence efficiency are indeed enhanced when the dynamically decreasing learning rate replaces a fixed one. The fixed learning rateηmax=0.1 in the λ-MART algorithm is replaced with the dynamical learning rate ηiter∗ in (8). For the large-scale dataset, in order to keep the consistency of values of parameters of the λ-MART algorithm with the fixed learning rate, we set parameters of the λ-MART algorithm with the dynamically decreasing learning rate as follows: ηmax=0.3, ηmin=0.1, and other parameters are unchanged. We use ERR and NDCG as the effectiveness optimization criteria during the training process of the ranking models, respectively. Figure 11 reports the overall results of μ including ERR@5, ERR@10, ERR@20, NDCG@5, NDCG@10, and NDCG@20 on the five folds, respectively. Figure 12 reports the total number of iterations accordingly. Obviously, the strategy of dynamically decreasing the learning rate not only improves the effectiveness of the ranking models but also enhances the convergence efficiency of our improved λ-MART.In summary, experimental results on three benchmark datasets demonstrate thatMatthew-λ-MART can achieve a better performance on both Matthew effect and effectiveness compared with the state-of-the-art LTR algorithms. In addition, the experiments prove that our proposed strategy of dynamically decreasing the learning rate is better than the fixed learning rate in the λ-MART algorithm.


## 5.1. Experiments on Large Dataset: MSLR-WEB30K

Figures1–6 provide the total results of five folds on MSLR-WEB30K dataset in terms of μ, Gini, Vup, Vdown, count[0], and count[3] for different LTR algorithms, respectively.From meanμ (including NDCG@20, NDCG@10, NDCG@5, ERR@20, ERR@10, and ERR@5) in Figure 1, we can see that the values of μ obtained by Matthew2-λ-MART are bigger than Matthew3-λ-MART, λ-MART, RankBoost, and AdaRank. These results show that Matthew2-λ-MART obtains the highest and best effectiveness. There are two main reasons. One is that Matthew-λ-MART incorporates the effectiveness evaluation measures Mt into the gradient and combines the overall scores k×eGini×Mt on training and validation datasets to choose a ranking model as the final ranking model. The other one is that Matthew-λ-MART uses the strategy of dynamically decreasing a learning rate to obtain an optimal tree. The main reason why the effectiveness of Matthew2-λ-MART outperforms Matthew3-λ-MART is that the enhancement of the Matthew effect of a ranking model usually reduces its effectiveness of the ranking model, while Matthew3-λ-MART with t=3 is more able to strengthen the differences of the gradients and the differences of the effectiveness of queries than Matthew2-λ-MART with t=2. Therefore, Matthew3-λ-MART strengthens the optimization of Matthew effect more than Matthew2-λ-MART does.From Gini coefficientGini in Figure 2, Matthew2-λ-MART and Matthew3-λ-MART both obtain a bigger value than λ-MART. These results show that the effectiveness across different individual queries in Matthew-λ-MART has a greater difference and thus indicates that the ranking model trained by Matthew-λ-MART has a stronger Matthew effect than λ-MART. Figure 2 also indicates that the values of Gini of Matthew3-λ-MART are bigger than the one of Matthew2-λ-MART. The main reason is that the value of t in Matthew3-λ-MART is bigger than that in Matthew2-λ-MART. The bigger the value of t, the greater the difference between the assigned weights of the rich query and the poor query. Therefore, the rich query can get more optimization than the poor query in the process of learning a ranking model. Therefore, Matthew3-λ-MART strengthens the optimization of Matthew effect compared to Matthew2-λ-MART, and the Matthew effect of Matthew3-λ-MART is highlighted to a certain extent.From Figures3 and 4, the values of variances Vup and Vdown generated by Matthew2-λ-MART and Matthew3-λ-MART are bigger than λ-MART, RankBoost, and AdaRank in most of cases (except that the values of Vup generated by Matthew2-λ-MART and Matthew3-λ-MART are smaller than RankBoost and AdaRank in terms of NDCG@20, NDCG@10, and NDCG@5, and the value of Vup generated by Matthew3-λ-MART is smaller than λ-MART in terms of ERR@5). These results demonstrate that the effectiveness across different individual queries in Matthew-λ-MART has also a greater difference generally. Therefore, the ranking model trained by Matthew-λ-MART usually exhibits a stronger Matthew effect than λ-MART, RankBoost, and AdaRank.From Figures5 and 6, the values of count[3] with regard to rich queries and count[0] with regard to poor queries obtained by Matthew2-λ-MART and Matthew3-λ-MART are bigger than λ-MART, RankBoost, and AdaRank in most of cases. These results show that Matthew-λ-MART leads to a relative polarization, thereby further exhibiting a stronger Matthew effect than λ-MART in general.SinceMatthew-λ-MART highlights the corresponding differences of upward or downward ranking force between documents with regard to rich queries with high effectiveness and documents with regard to poor queries with low effectiveness, it strengthens the optimization of rich queries and weakens the optimization of poor queries in the training process of the ranking models. Consequently, more forces are used to optimize the ranked positions of the documents in the rich queries and less for the poor queries. Finally, Matthew-λ-MART increases the degree of difference or dispersion in the effectiveness across all the queries. Therefore, the ranking model trained by Matthew-λ-MART shows a stronger Matthew effect than λ-MART.


## 5.2. Experiments on Small Datasets: WCL2R and MQ2007

Wu et.al. [5] have pointed out that smaller trees and shrinkage may be used if the training dataset is smaller. WCL2R with 79 queries and MQ2007 with 1692 queries are small datasets, so we set parameters for Matthew-λ-MART as follows: ntrees=200, ηmax=0.1, and ηmin=0.05, where ntrees represents the number of trees. We use NDCG@5 as the effectiveness optimization criterion during the training process on WCL2R and MQ2007 for these LTR algorithms. Figures 7–9 provide the overall results of five folds on the two datasets in terms of measures μ, Gini, Vup, Vdown, count[0], and count[3] for these LTR algorithms, respectively. These results also show that the Matthew-λ-MART algorithm performs better than others in most cases.


## 5.3. The Comprehensive Evaluation: Winning Number

We use the winning numberWNp to comprehensively evaluate the effectiveness and Matthew effect of LTR algorithms. WNp is introduced by Liu [29], which counts the times a method beats other ones over all datasets. We extend WNp to a cross-measure for each LTR algorithm, which counts the times a method beats other ones over all measures and datasets. We redefine WNP as follows: (15)WNP=∑i=1R∑j=1S∑k=1,k≠PNIMeasjPi>Measjkiwhere N is the number of the compared methods, P and k are the indices of the compared methods, R is the number of LTR datasets, i is the index of an LTR dataset, S is the number of measures, j is the index of a measure, Measjk(i) is the performance of the k-th method on the i-th dataset in terms of the j-th measure, and I(·) is an indicator function such that (16)IMeasjPi>Measjki=1ifMeasjPi>Measjki,0otherwise.WNP is a comprehensive evaluation of ranking performance. The larger WNP is, the better the P-th method performs.Figure10 shows WNp for these LTR algorithms on the three datasets in terms of the effectiveness (i.e., μ, including NDCG@20, NDCG@10, NDCG@5, ERR@20, ERR@10, and ERR@5) and Matthew effect (including Gini, Vup, Vdown, count[0], and count[3]). From this figure, we can observe the following facts:(1) In terms ofWNp of effectiveness, Matthew2-λ-MART and Matthew3-λ-MART are better than λ-MART, RankBoost, and AdaRank, and λ-MART is better than RankBoost and AdaRank.(2) In terms ofWNp of Matthew effect, Matthew2-λ-MART and Matthew3-λ-MART are also better than λ-MART, RankBoost, and AdaRank, but λ-MART is worse than RankBoost and AdaRank.


## 5.4. Performance of the Strategy of Dynamically Decreasing the Learning Rate

We conduct experiments on the MSLR-WEB30K dataset to evaluate the advantage of the strategy of dynamically decreasing the learning rate; that is, the effectiveness and convergence efficiency are indeed enhanced when the dynamically decreasing learning rate replaces a fixed one. The fixed learning rateηmax=0.1 in the λ-MART algorithm is replaced with the dynamical learning rate ηiter∗ in (8). For the large-scale dataset, in order to keep the consistency of values of parameters of the λ-MART algorithm with the fixed learning rate, we set parameters of the λ-MART algorithm with the dynamically decreasing learning rate as follows: ηmax=0.3, ηmin=0.1, and other parameters are unchanged. We use ERR and NDCG as the effectiveness optimization criteria during the training process of the ranking models, respectively. Figure 11 reports the overall results of μ including ERR@5, ERR@10, ERR@20, NDCG@5, NDCG@10, and NDCG@20 on the five folds, respectively. Figure 12 reports the total number of iterations accordingly. Obviously, the strategy of dynamically decreasing the learning rate not only improves the effectiveness of the ranking models but also enhances the convergence efficiency of our improved λ-MART.In summary, experimental results on three benchmark datasets demonstrate thatMatthew-λ-MART can achieve a better performance on both Matthew effect and effectiveness compared with the state-of-the-art LTR algorithms. In addition, the experiments prove that our proposed strategy of dynamically decreasing the learning rate is better than the fixed learning rate in the λ-MART algorithm.


## 6. Conclusion

In this paper, we integrate the idea of Matthew effect into the algorithm of LTR and present a new function of the gradient in theλ-MART algorithm which can highlight Matthew effect and prove that the function satisfies the consistency property. In addition, we propose two strategies to evaluate the ranking models and dynamically decrease the learning rate, respectively. They can not only strengthen Matthew effect but also improve the effectiveness of the produced ranking model. Experiments do prove that our improvements work.Some interesting issues can be explored in the future research.(1) Other learning rates such as optimal learning rate and adaptive learning rate can be considered in LTR.(2) It is obvious that different information has different popularity in different time periods, which leads to the users’ queries always changing their popularity over time. Some queries (hot queries) gain a huge popularity with numerous searchers, while some queries (cold queries) are just the opposite. We plan to integrate the hot and cold queries into an LTR algorithm.(3) The multiobjective evolutionary algorithms and reinforcement learning techniques can be incorporated into LTR to develop a multiobjective and online LTR algorithm.



---

*Source: 3082970-2018-11-06.xml*