Introduction

Rank-learning applications for information retrieval (IR) have garnered increasing research attention in recent years. (The benchmark dataset for testing rank-learning methods is Microsoft LETOR [1].) “Learning to rank” involves the use of machine-learning techniques, as well as other related technologies to learn datasets in order to automatically generate optimal ranking functions; ranking function performance essentially depends on the rank-learning algorithm. Rank-learning is widely used in many applications associated with ranking tasks. For example, Yu J et al. [2] propose a novel ranking model for image retrieval based on the rank-learning framework, in which visual features and click features are simultaneously utilized to obtain the ranking model. Liu B et al. [3] propose a new computational method called ProtDec-LTR for protein remote homology detection, which is able to combine various ranking methods in a supervised manner via using the rank-learning algorithm. The results indicate predictive performance improvement can be achieved by combining different ranking approaches in a supervised manner via using rank-learning. Yang X et al. [4] introduce a learning-to-rank approach to construct software defect prediction models by directly optimizing the ranking performance. They empirically demonstrate that directly optimizing the model performance measure can benefit software defect prediction model construction. Chen J et al. [5] propose a rank-learning based framework for assessing the face image quality, because selecting face images with high quality for recognition is a promising stratagem for improving the system performance of automatic face recognition.

Traditional rank-learning algorithms are dependent on loss function optimization. Because the ranking function is evaluated by certain measures such as mean average precision (MAP) or normalized discounted cumulative gain (NDCG), ideally, the loss function is built through evaluation measures. Numerous algorithms have been proposed previously based on such IR evaluation measures [6], in addition to methods based on evolutionary computation. Genetic programming methodology has been particularly successfully applied to the design of rank-learning algorithms [7–8]. The clonal selection algorithm, which is based on the artificial immune system and immune programming, has also been applied to design rank-learning algorithms [9–10].

The traditional rank-learning algorithm is similar to the traditional machine-learning algorithm, where most optimize the loss function to generate a ranking function with minimum loss through iterations [11]. The loss function itself determines which mathematics principia or machine learning techniques are applied for optimization. For ListWise [12] methods, for example, typical loss functions are based on IR evaluation measures such as MAP, NDCG, or P@n. IR evaluation measures are integrated into loss functions, then the learned result naturally shows favorable evaluation measures. Loss functions based on IR evaluation measures are not smooth, however, and thus cannot be optimized via traditional machine-learning techniques–only upper bound functions or similar functions of the original loss function can be optimized by traditional machine learning techniques.

Traditional rank-learning methods based on loss functions utilize the analyticity properties of the loss function and geometric features of the constraint space to gradually shrink the search space in order to find optimal solutions. As the problem size increases, though, the traditional loss-function-based algorithm is no longer able to obtain the optimal solution within an acceptable timeframe. It is necessary (and urgent, considering the current demand) to establish an intelligent optimization method based on IR evaluation measures that can work sufficiently quickly (i.e., at reduced computation time.)

The B cell algorithm [13] is an immune algorithm based on the clonal selection principle which can start from a set of feasible solutions without any loss function to evolve and facilitate efficient searching, eventually returning global optimal solutions. Previous studies have shown that the B cell algorithm is convergent and requires fewer iterations compared to the hybrid genetic algorithm or clonal selection algorithm without affecting the quality of the solution results [14]. The B cell algorithm has natural parallel characteristics and is very well-suited to multi-CPU parallel computing, which not only allows full use of modern computer hardware resources to accelerate the algorithm’s speed, but also reduces the possibility of local optima and improves the quality of optimal solutions by expanding single populations to multiple populations with rich species diversity.

MapReduce is an easy-to-use and general-purpose parallel programming model that is suitable for analyzing large data sets. The Apache Hadoop gives researchers the possibility of achieving scalable, efficient, and reliable computing performance on Linux clusters. The MapReduce model has been applied to parallel computation with large datasets in the bioinformatics field [15–16], but in the field of learning to rank, the dataset size used for training and testing (LETOR, as mentioned above) is only several dozens of megabytes. The core distributed feature of MapReduce cannot be utilized fully to design parallel rank-learning algorithms, and MapReduce is not suitable at all for iterative training in rank learning. Wang S et al. [17] propose a parallel framework called CCRank for learning to rank based on evolutionary algorithms. The method is based on cooperative coevolution (CC), which is a divide-and-conquer framework that has demonstrated high promise in function optimization for problems with large search space and complex structures. In this study, we applied a simple parallel strategy to the B cell algorithm and found that the resulting parallel B cell algorithm can execute rank-learning tasks effectively on a multi-core processor.

This paper presents a parallel B cell algorithm that was developed to improve the precision and speed of rank-learning tasks. The novel algorithm is a type of coarse-grained, master-slave parallel model: An initial population is generated by the master node and then divided into multiple subpopulations to evolve independently. During the evolution process, each clone pool of every individual crosses over to increase the population diversity and enrich the search space. Parallel computing can speed up the evolution of the entire population so as to obtain the global optimal solution rapidly.

Rank Learning

Ranking, as discussed above, is the primary issue in IR applications. “Ranking” in this context involves securing a ranking function that can respond to user query to rank documents based on their relevance within the corpus. The ranking problem can be formalized as follows.

Given a query q_i ∈ Q, |Q| = m as well as a set of documents d_i = associated with q_i, then the degree of relevance between q_i and j-th document d_ij is defined as follows: S1 Equation, where r_i is the degree of relevance, r_n≻r_n−1≻r_n−2≻…≻r₁, ≻ represents preference relations, x is a feature vector, ϕ is a feature extraction function, and n(q_i) is the number of documents associated with q_i. For a given q_i, the evaluation function between π_i and y_i is E(π_i, y_i), where π_i is the sequence generated by the descending order of documents associated with q_i. For document retrieval, the essence of the ranking function is to compute the relevance between the document and the query, then to rank documents by relevance–accordingly, the ranking function usually refers to the relevance calculation function.

Generating a ranking function includes three main factors: First, the representation of the degree of relevance; second, the relevance calculation method; and third, the features of the query-document pair. Different representations of relevance and calculation methods can produce entirely different ranking functions. Most of the traditional ranking functions are based on the “word bag” pattern, that is, the term frequency (TF) and inverse document frequency (IDF) attributes serve to calculate relevance. For example, the vector space model represents relevance degree as the angle between the two vectors in a vector space, where the calculation method is the inner product of the vectors. The probability model represents the relevance degree as the probability a document is relevant with a given query, where calculation is built on the conditional probability model and independent event probability model.

Traditional ranking model design generally takes place in the following steps.

1. Extract features from the query-document pairs (e.g., TF, IDF).
2. Specify the representation of relevance between a query and a document.
3. In accordance with the degree of relevance, use the known relevance calculation method to combine features and obtain the initial ranking function.
4. Adjust the parameters in the ranking function to make the ranking function utile in practice.

The traditional ranking function is simple and easy to calculate, but recent advancements in IR (especially modern search engines,) have left simple ranking functions unable to adapt to highly complex and dynamic user needs. Search engines receive a wealth of user feedback and logs on a daily basis, and new features cannot automatically be added to traditional ranking functions, which makes them difficult to improve as necessary.

Rank learning is a machine-learning technique employed to automatically obtain optimal ranking functions during IR. Machine learning has four main components: input space, output space, hypothesis, and machine-learning algorithms. The historical information supplied for a machine to “learn” commonly refers to training sets (which may include manual labels input for supervision.)

Applying rank-learning techniques to automatically create a ranking function needs the following steps.

1. Prepare training collection D = : The training set contains a collection of queries, a set of documents related to each query, and a relevance judgment for each query-document pair.
2. Design the rank-learning algorithm.
3. Apply the rank-learning algorithm to the training set D and automatically generate the optimal ranking function.
4. Evaluate the generated ranking function and compare it against the existing ranking functions to decide whether the ranking function performs effectively in practice.
5. Apply the favorable ranking function to unseen data sets, where given a set of queries and related documents, the documents are ranked by relevance and the more relevant documents are placed into upper positions.

Among the above five steps, the learning algorithm design step is the key to the entire process. Algorithm design depends on the hypothesis space, the form of the training set, and the loss function. The B cell algorithm, as mentioned above, is an immune algorithm based on the clonal selection mechanism which conducts evolution on the initial solution space to search a group of optimal solutions. It is an effective, “natural” machine-learning algorithm that features relatively rapid search speed by representing the ranking function as the “antibody” in the population, then evaluates it on the specified dataset through an IR evaluation function to guide the learning process into the optimal solution space.

B Cell Algorithm

The B cell algorithm (BCA) is an immune-inspired algorithm which includes a distinguished clonal selection process and mutation mechanism. BCA can be applied to various types of optimization problems and shows better performance than the hybrid genetic algorithm or clonal selection algorithm. An important feature of BCA is its particular mutation operator, continuous region hypermutation, the biological motivation for which is as follows: When a mutation occurs on the B-cell receptors, the system focuses on determining complementary, small regions on the receptor, i.e., sites that are primarily responsible for detecting and binding to their targets. This process basically forms a highly focused search. BCA accordingly forms an interesting contrast with the method employed by CLONALG, whereby although multiple mutations take place, they are uniformly distributed across the vector rather than being targeted at a contiguous region. The contiguous mutation operator, rather than selecting multiple random sites for mutation, chooses a random site (or hotspot) within the vector along with a random length; the vector is then subjected to mutation from the hotspot onward until the length of the contiguous region has been reached. The other most notable feature of BCA is its independence during the antibody evolution process. The father antibody produces a child clone pool in each iteration, then the child clone pool expands the search space through mutation. Finally, the father antibody is replaced by its most fit child to realize the population evolution.

The BCA framework is as follows.

1. Initialize a random individual (antibody) population P.
2. For individual v ∈ P, apply a fitness function g(v) to v.
3. Duplicate v ∈ P and place the clones in clone pool C.
4. Apply the mutation operator to all the individuals in C to get clone pool C′.
5. Compute the fitness of each individual v′ ∈ C′; if g(v′) > g(v), then replace v with v′.
6. Loop from Step 2 to Step 5 until the stop condition is met.

Parallel B Cell Algorithm

There are two important reasons to parallelize the BCA: The first is to increase computational efficiency by using multiple cups to conduct the same learning task, and the second is to research the parallel model of the BCA to ensure its original arithmetic features are maintained, allowing it to be applied to several machine-learning fields. The parallel model of the BCA is shown in Fig 1.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Fig 1. Parallel model of B cell algorithm.

https://doi.org/10.1371/journal.pone.0157994.g001

Multiple execution individuals (such as threads) complete the same task in a parallel manner collaboratively in the proposed algorithm. Each thread completes the same amount of work through the serial method. Apart from speeding up the learning process, the parallel model also introduces a crossover operator to ensure rich diversity of each clone pool. Compared to the original serial algorithm, the proposed algorithm expands the search space of the whole population after each iteration to speed up the convergence rate.

Parallel BCA adopts the following step-wise process.

(1) The master node reads the training dataset as the antigen set G = (Ag₁, Ag₂, …, Ag_g). The initial antibody population size is defined as n, clone pool size as n_c, antibody encoding length as l, processor size as M, and antibody gene set as B = {ab_1, ab₂, …, ab_m}.

The antibody space is defined as:

Then the antibody population space is defined as: The antibody population after the k-th iteration is P(k) = {Ab₁(k), Ab₂(k), …, Ab_n(k)} ∈ Pⁿ, then k = 0 is initialized and iteration number is Gen. The initial population, i.e., master population, is P(0).

(2) An equal division of population P(0) is defined, that is, and the subpopulation size .

(3) Sub₁, …, Sub_M to M processors are assigned; each subpopulation Sub_j processes in parallel.

The affinity of antibody Ab ∈ Sub_j is defined as: where AF is the antibody-antigen affinity function and AVAF is the average affinity on the antigen set.

(4) Antibody population P(k) is cloned, and clone size is n_c. The clone pool of antibody Ab_i(k) ∈ P(k) is Pool(Ab_i(k)), where 1 ≤ i ≤ n.

(5) The antibodies of clone pools cross over; the basic principle of the crossover is to maximize antibody diversity in the clone pools. The crossover operation includes “entire cross” and “partial cross”, and is defined as follows.

In one iteration, put master population into a list L, where L = (Ab₁, Ab₂, …, Ab_n). Divide L into group groups: Then L = (L₁, L₂, …, L_group).

If n> = n_c and n%n_c = 0, and L_i ∈ L, |L_i| = n_c, then , where 1 ≤ i ≤ group,. Antibody forms clone pool , and operation swap(Ab₁, Ab₂) is defined as the exchange between antibody Ab₁ and antibody Ab₂. Then the crossover process of clone pool in L_i is:

for(j = 1; j<n_c; j++)

 for(s = 1, k = j; k<n_c; k++, s++)

  swap(Ab_ijk, Ab_i(j+s)j)

Because each antibody in a clone pool is different after crossover, this kind of crossover is called “entire cross”.

If n > n_c and n%n_c ≠ 0, and L_group ∈ L, |L_group|≠n_c, then the crossover in L_group is as follows:

for(j = 1; j<n%n_c; j++)

 for(s = 1, k = j; k<n%n_c; k++, s++)

  swap(Ab_ijk, Ab_i(j+s)j)

Because there still exists the same antibody in L_group after crossover, this kind of crossover is called “partial cross”.

If n < n_c, group = 1, then the crossover in L_group is as follows:

for(j = 1; j<n; j++)

 for(s = 1, k = j; k<n; k++, s++)

  swap(Ab_ijk, Ab_i(j+s)j)

Because there still exists the same antibody in L_group after crossover, this kind of crossover is also called “partial cross”.

(6) Each processor conducts mutations on antibodies in the clone pool in parallel. When the k-th iteration is reached, clone pool Pool(Ab_i(k)) is changed to Pool′(Ab_i(k)) after mutation. The antibody in Pool'(Ab_i(k)) is represented as PAb′_j ∈ Pool′(Ab_i(k)), 1≤i≤n, 1≤j≤n_c.

(7) Each processor chooses the best antibody in the mutated clone pool to replace its father antibody in parallel. For antibody Ab_i(k) in the master population, the replacement process is as follows:

for(j = 1; j< = n_c; j++)

 if(affinity(PAb′_j, G)> affinity(Ab_i(k), G))

  replace(Ab_i(k), PAb′_j)

where replace(Ab_i(k), PAb′j) represents replacing Ab_i(k) with PAb′j.

(8) Loop Form (3) to (7) until the iteration reaches Gen.

(9) The master node collects the best antibodies from each subpopulation to form the final optimal solutions .

RankBCA: A Rank-learning Algorithm Based on Parallel BCA

RankBCA is parallel BCA application that can be used to solve ranking problems in IR. It treats training example (q_i, d_i, y_i) as the antigen, ranking function r(x) as the antibody, and evaluation measure MAP as the affinity function; the training process is in query units. The ranking function computes a relevance score for each document-query pair and evaluates the performance. The MAP, which reflects how well a ranking function performs on a training dataset, is computed after all the queries have been evaluated. After antibodies in the clone pool have been mutated, the MAP of each ranking function is computed again. If the child’s MAP is larger than its father’s, then the father is replaced by the child. This process refreshes the ranking functions in the initial antibody repository to obtain a collection of optimal ranking functions. In order to secure the best ranking function from the collection, each ranking function computes the MAP on the training dataset and the MAP on the validation dataset, then computes the average MAP between them; the ranking function with the largest average MAP is the final output.

There are three kinds of nodes involved in parallel learning: Master nodes, slave nodes, and cross nodes. The master node is responsible for starting the learning and tail-in work; the slave node is responsible for subpopulation evolution; and the cross node is responsible for cloning and crossover. The RankBCA process is outlined below.

(1) initialization

The master node randomly generates an antibody repository (master population) accompanied by ranking functions. The master population is divided into several subpopulations, each of which is assigned to a single slave node. The slave nodes and cross node are then started and the LETOR training and validation datasets are initialized. The training dataset is used for training, and the validation dataset is used to select the optimal ranking function.

(2) training in parallel

The slave node is responsible for training each subpopulation; each slave node executes the task in parallel and enters a wait state after finishing the replacement. The cross node conducts cloning and crossover on the master population, then notifies all slave nodes after finishing crossover; once the master node is notified, it proceeds to update the master population while the slave nodes finish learning.

(3) choose the optimal ranking function

The master node selects the optimal ranking function from the master population after training. As discussed above, the average MAP is computed between the MAP on the training dataset and that on the validation dataset for each ranking function in the master population, then outputs the ranking function with the largest average MAP value.

Antibody and Antigen

The antigen, antibody, and affinity are the three components of BCA. Using BCA to solve rank-learning problems involves identifying the correspondence between immune components and rank-learning components. During immune modeling, each antigen expresses a problem that is typically represented as a mapping of inputs and outputs. Each antibody candidate in the antibody repository expresses a solution and is randomly generated by a gene pool, and the affinity expresses fitness between the antibody (candidate solution) and the antigen (problem) [18].

Rank learning automatically generates a ranking function that can calculate the relevance score between a query and document. Accordingly, the antigen can be represented as a mapping of an input and output (q_i, d_ij, y_ij). The IR evaluation measure is query-based, so the antigen itself must likewise be query-based: The antigen is defined as (q_i, d_i, y_i), and the antibody is a candidate formed by ranking function r(x). In the LETOR dataset, a query-document pair is represented as a real feature vector x = ϕ(q_i, d_ij), i.e., feature values that are a part of the gene pool. The antigen repository represents the entire training set D = , which is also a collection of multiple antigens.

The affinity, which expresses the goodness of any ranking function, is defined as IR evaluation measure E(π_i, y_i). The correspondence between immune components and rank-learning components is summarized in Table 1.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Table 1. Correspondence between immune components and rank-learning components.

https://doi.org/10.1371/journal.pone.0157994.t001

Gene Pool and Antibody Tree

The “gene pool” defines the antibody structure space. During rank learning, the antibody represents a function computing a score with a real vector; each dimension in the real vector is represented as a variable in a function. A ranking function not only contains variables, however, but also operators and constants, i.e., ranking function r(x) = (3*x₁ + 4*x₂)/(2−x₃), in which x = (x₁, x₂, x₃) is a three-dimensional real vector and operators are the elements in {+, *,/−}; constants are 2, 3, and 4. In short, the gene pool contains a feature set, operator set, and constant set.

The gene pool is defined as I = {F, O, C}, where F is the feature set, O is the operator set, and C is the constant set. The gene pool of RankBCA is defined as follows: where dimension(x) is the dimension of the feature vector x.

An antibody is built of the three distinct components in the gene pool. The initial antibody contains all of the features, then operators and constants are selected at random. The features are selected at random during antibody evaluation. The choice of antibody data structure has a significant effect on the algorithm’s running efficiency and portability. The traditional methodology is built on the tree and s-expression structure, which previous scholars have established via stack-based architecture [18]. Tree representation is more easily understood and calculated, however, which is why we adopted it here. The operator is an internal node of the antibody, and leaf nodes represent constants and features. An antibody is a candidate ranking function, the function expression of which is generated by inorder traversing the tree. Accordingly, the ranking function does not need to cover all available features. As shown in Fig 2, the ranking function is (3 − f₁) + (f₂*0.3) after inorder traversing the tree.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Fig 2. Antibody tree example.

https://doi.org/10.1371/journal.pone.0157994.g002

To construct the antibody tree, an antibody is represented as a full binary tree structure and the nodes in the tree are divided into three types: feature nodes, operator nodes and constant nodes, respectively corresponding to feature set F, operator set O, and constant set C in the gene pool. The size of each node is determined by the height of the tree, and the number of nodes is (2^H−1) given a tree with height H. Each node in the antibody tree has a unique serial number which increases from top to bottom and left to right in the tree. The number of nodes ranges within ID = {id|id ∈ [1,2^H−1] ^ id ∈ Z}.

Again, the tree's height determines the number of leaf nodes in the antibody tree and the number of leaf nodes is 2^(H−1) given an antibody tree with height H. To ensure that the number of leaf nodes in the experiment can override all the different features, it is necessary to calculate S2 Equation, where |F| depends on the dataset, (|F| = 45 in the OHSUMED dataset, and |F| = 46 in the MQ2007 and MQ2008.) In our experiment, H was set 7 to meet S2 Equation. The algorithm’s time complexity increases as H increases, so H is generally kept below 10.

Preordered Antibody Encoding

In order to directly express antibodies, they must be encoded in a linear sequence. Each antibody has a unique encoding sequence which the sequential numbers in the tree are utilized to encode, so the antibody encoding sequence is based on the antibody tree. Contiguous regions in the antibody tree must be in accordance with the contiguous regions of the encoding sequence. Through observation, using the antibody tree shown in Fig 2 as an example, there are the following three kinds of contiguous regions in the tree.

1. Nodes are continuous if they are in a subtree, such as <2, 4, 5>.
2. Nodes are continuous if they are located around several subtrees, such as <5, 3, 6, 7>.
3. Nodes are continuous if they are connected directly by layers, such as <1, 2, 4>.

A preorder encoding sequence is applied to encoding the antibody tree in order to maintain consistency between the antibody tree and encoding sequence. Given an antibody tree with height H, each element in the encoding sequence is uniquely identified by its sequential number in the antibody tree; the sequential number collection of the elements is ID = {id|id ∈ [1,2^H−1] ^ id ∈ Z}. An encoding sequence with length 2^H−1 is acquired from a preordered traversal of the antibody tree, then the numbered encoding sequence is seq = < 1, 2, 4, …, 2^(H−1), 2^(H−1)+1, …, 3, …2^H−1>. This final sequence is the preordered encoding of the antibody (Fig 3).

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Fig 3. Preordered antibody encoding.

https://doi.org/10.1371/journal.pone.0157994.g003

An array is utilized to store the preordered encoding of the antibody. Each element in the sequence is a reference to the node in the antibody tree, a feature which lends the following benefits:

1. It saves memory space. The array elements only store the references to antibodies instead of deep copies of the nodes, so the elements do not contain any additional data.
2. It speeds up mutation. Mutations occur in the linear encoding sequence instead of the antibody trees without traversing the antibody tree.

Mutation Principles and Mutation Operator

Mutation operation includes both mutation principles and the mutation operator. An antibody tree is presented as a ranking function, where internal nodes can only be the operators and leaf nodes can only be constants or features. Node mutation depends on the type of the node. Mutation principles are defined as follows.

1. The operator node mutates to an operator node in O randomly.
2. The constant node mutates to a constant node in C or a feature node in F randomly.
3. The feature node mutates to a constant node in C or a feature node in F randomly.

The mutation operator defines a set of mutation behaviors, i.e., contiguous region mutation on the antibody coding sequence; the contiguous region mutation chooses a contiguous region on the antibody coding sequence. The direction of mutation in the original BCA is singular, but the mutation operator in the proposed algorithm works in two directions to reduce the effects of mutation in the right subtree, which ensures that mutations are not only continuous but also that distribution is balanced in the antibody tree. The continuous region mutation operator is defined as follows.

1. A location is randomly selected in the encoding sequence p ∈ [1,2^H−1] ^ p ∈ Z and defined as a “hotspot”.
2. Mutation direction d ∈ {−1,1} is chosen randomly, where -1 is left and 1 is right.
3. If d = 1, then length l ∈ [1,2^H−p] ^ l ∈ Z is chosen randomly and mutated from p to the right direction until mutated length l (including p);
   else length l ∈ [1, p] ^ l ∈ Z is randomly chosen and mutated from p to the left direction until mutated length l (including p).

For ranking function (3 − f₁) + (f₂*0.3), the mutation process is as shown in Fig 4.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Fig 4. Contiguous region mutation.

https://doi.org/10.1371/journal.pone.0157994.g004

The mutation process in Fig 4 takes place through the following steps:

1. The hotspot is randomly chosen as 5.
2. The mutation direction randomly chosen is left.
3. The mutation length randomly chosen is 3.
4. Nodes are mutated at position 2, 4, 5 according to the mutation principles above; “-” is mutated to “/”, “3” is mutated to “8”, and “f1” is mutated to “0.2” at random.

The mutated ranking function is (8/0.2) + (f₂*0.3).

Experiments

Experiment Setup

We used LETOR3.0 OHSUMED and LETOR4.0 MQ2007 datasets to conduct our verification experiment. The OHSUMED dataset includes 348566 documents, 106 queries, and 16140 query-document pairs and relevance judgments in total. The relevance judgment includes three levels: 2, 1, and 0, respectively representing “relevant”, “possible”, and “not relevant”. To suit the two-value evaluation measure, only “relevant” is considered relevant. The OHSUMED dataset includes 15 features divided into low features and high features: The low features include 10 features and the high features include five features. Each query-document pair includes 45 features in OHSUMED dataset, because the afore-mentioned 15 features are extracted from three fields: title, abstract, and title+abstract. The MQ2007 dataset includes 1700 queries and 69623 query-document pairs and relevance judgments in total. It has the same three-level labeling method as the OHSUMED and includes 14 different features divided into content features, link features, and hybrid features. The content features extract content, anchor text, title, URL, and full five-part documents to form 40 features; the other six features are extracted from the document. Each query-document pair in MQ2007 accordingly includes 46 feature values. Each dataset was subjected to a 5-fold cross validation experiment to avoid over-fitting, and separate experiments were conducted on OHSUMED and MQ2007. The final experimental results were compared with the benchmark algorithms RankBoost, RankSVM, AdaRank, and ListNet.

We used MAP as the affinity function in our experiment, and compared it against benchmarks on MAP, P@1~P@10 and NDCG@1~NDCG@10. The configuration in RankBCA is described in Table 2.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Table 2. Algorithm configuration and parameters.

https://doi.org/10.1371/journal.pone.0157994.t002

T, β and N are the parameters in RankBCA, all of which have important effects on the final results. Different parameters have different adaptive value for different datasets. The parameter values in Table 2 were applied specifically to OHSUMED and MQ2007.

Results

(1) accuracy comparison

In addition to the parameters listed in Table 2, the number of processors was set to eight for the comparison experiment; the eight processors were then run in parallel to obtain the final result as the average of 10 valid experiments. (Several experiments were run and averaged to account for the fact that RankBCA is a random algorithm.) The MAP comparison between RankBCA and the benchmarks is shown in Table 3.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Table 3. MAP comparison on benchmarks.

https://doi.org/10.1371/journal.pone.0157994.t003

P@n and NDCG@n results on the OHSUMED dataset are shown in Figs 5 and 6. P@n and NDCG@n results on the MQ2007 dataset are shown in Figs 7 and 8.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Fig 5. P@n on OHSUMED.

https://doi.org/10.1371/journal.pone.0157994.g005

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Fig 6. NDCG@n on OHSUMED.

https://doi.org/10.1371/journal.pone.0157994.g006

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Fig 7. P@n on MQ2007.

https://doi.org/10.1371/journal.pone.0157994.g007

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Fig 8. NDCG@n on MQ2007.

https://doi.org/10.1371/journal.pone.0157994.g008

As shown above, regardless of n value, the P@n or NDCG@n of RankBCA performed very well compared to the other algorithms (and occasionally outperformed the others.) In respect to precision, RankBCA was more stable than the benchmarks. With the configuration of M = 8, RankBCA took 1212 seconds to finish 5-fold validation learning on the OHSUMED dataset. The performance could be improved further if the clone scale increased properly without exerting excessive impact on running time.

(2) convergence rate

The learning curve of the MAP for RankBCA on OHSUMED fold1 is shown in Fig 9.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Fig 9. Learning curve of RankBCA.

https://doi.org/10.1371/journal.pone.0157994.g009

Fig 9 shows that RankBCA tended to be convergent as the iterations progressed, and that its convergence rate was considerably faster than that of AdaRank.

(3) speed-up ratio

The result of the speed-up ratio experiment (again, based on a 5-fold run) is shown in Table 4.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Table 4. Speed-up ratio comparison on OHSUMED dataset.

https://doi.org/10.1371/journal.pone.0157994.t004

Table 4 shows that the time consumed by the proposed parallel algorithm decreased as the processor number increased, while the speed-up ratio increased linearly. The performance of RankBCA was very favorable.

Conclusion

This paper proposed an innovative parallel BCA designed for rank-learning applications. Compared to similar existing algorithms, RankBCA utilizes population evolution rather than optimizing the loss function to obtain the optimal ranking function. Parallel BCA divides the single population into multiple subpopulations, and then avoids local optima via crossover operation. Each subpopulation occupies an independent processor, which lends very favorable performance. During the evolution procecss, RankBCA utilizes a continuous region mutation on individuals and parallel running to ensure high convergence rate and running speed, while a crossover procedure is applied to the population to enrich its diversity. A comparative experiment confirmed that RankBCA outperforms RankSVM, RankBoost, AdaRank, and ListNet in respect to accuracy and speed on benchmark datasets.

Supporting Information