CN110046713A - Robustness sequence learning method and its application based on multi-objective particle swarm optimization - Google Patents

Abstract

The invention relates to a robust ranking learning method based on multi-objective particle swarm optimization and its application, comprising the following steps: Step 1, based on the deviation-variance equilibrium theory, design the validity deviation function and the robustness variance function of the ranking model , construct two optimization performance indicators of ranking learning; step 2, on the ranking learning data set, based on the multi-objective particle swarm optimization algorithm framework, iteratively optimize the two objectives of the validity deviation function and robustness variance function of the ranking model to The sorting model is trained to generate the sorting model archive solution set; step 3, based on the idea of PROMETHEE II, the preference order structure evaluation method in the multi-attribute decision-making theory, from the sorting model archive solution set generated in the previous step, select the one with the largest "net" value. The Pareto-optimal ranking model of the "flow" ranking value is used as the final ranking model trained. Compared with the prior art, the present invention has the advantages of improving overall user satisfaction, enhancing user experience and the like.

Description

Robust ranking learning method based on multi-objective particle swarm optimization and its application

technical field

The invention relates to the fields of information retrieval and machine learning, in particular to a robust sorting learning method based on multi-objective particle swarm optimization and its application.

Background technique

Ranking learning is to use machine learning technology to automatically train a ranking model to solve the ranking problem. It is a hot research topic in the field of information retrieval and machine learning, and has broad application prospects in information retrieval, search engines, recommender systems and question answering systems.

Due to the dynamic nature of the Web and the diversity of user information requirements, the performance of some Web search queries may change greatly under different ranking models, and may suffer significant loss, thereby reducing user experience. A robust retrieval system should ensure that the user experience is not compromised by the presence of poorly performing queries. Therefore, in order to improve the overall user experience as much as possible, in addition to the traditional relevance and importance criteria, how to ensure the robustness of the ranking model, that is, relative to the simple benchmark, although an average gain is obtained overall, the new Ranking models usually suffer from performance losses on many queries, which is an important problem faced by learning to rank research in recent years. Therefore, it is necessary to develop robust ranking learning methods to train robustness-aware ranking models to improve the overall satisfaction of all users as much as possible.

Currently, researchers in learning to rank mainly compare and evaluate multiple ranking models by designing advanced ranking features and/or by developing advanced learning methods to rank, based on some effectiveness metrics such as normalized discounted cumulative gain (Normalized Discounted Cumulative Gain, NDCG) and Expected Reciprocal rank (Expected reciprocal rank, ERR), etc., choose a ranking model with the best effectiveness, and its goal is to focus on improving the average effectiveness of the ranking model. These methods often ignore the robustness of the ranking model. Awesome. A ranking model with poor robustness will lead to instability of the ranking system, that is, the performance of some queries is good, while the performance of other queries is poor, resulting in unstable ranking results presented to users, which are difficult to satisfy as much as possible. The information needs of different users make it difficult to bring a satisfactory experience to users. For this reason, in the training process of the ranking model, it is necessary to establish an optimization objective that meets the actual needs, and consider the effectiveness and robustness of optimizing the ranking model at the same time.

SUMMARY OF THE INVENTION

The purpose of the present invention is to provide a robust ranking learning method based on multi-objective particle swarm optimization and its application in order to overcome the above-mentioned defects of the prior art.

The object of the present invention can be realized through the following technical solutions:

A robust ranking learning method based on multi-objective particle swarm optimization, including the following steps:

Step 1, based on the bias-variance equilibrium theory, design the validity bias function and robust variance function of the ranking model, and construct two optimal performance indicators for ranking learning;

Step 2: On the ranking learning data set, based on the multi-objective particle swarm optimization algorithm framework, iteratively optimizes the two objectives of the validity deviation function and the robustness variance function of the ranking model to train the ranking model, thereby generating the ranking model archive solution set. ;

Step 3: Based on the idea of PROMETHEE II, a preference order structure evaluation method in multiple attribute decision theory, a Pareto-optimal ranking model with the largest "net flow" ranking value is selected from the ranking model archive solution set generated in the previous step. This is the final ranking model trained.

Preferably, the validity deviation function and the robustness variance function of the designed ranking model, and the two optimized performance indicators for constructing ranking learning are specifically:

The validity bias function and robustness variance function of query and query set under the ranking model are respectively defined as follows:

Definition 1. The validity bias function Bias ^R (q _{i )} of query qi is defined as:

in, _{represents the best effectiveness obtained by all documents D i under} the query qi under the ideal sorting model I, that is, all documents are correctly sorted, Represents the actual validity of all documents D _i under the query qi under the ranking model R, and Bias ^R (q _i ) _{represents the actual validity of the query q i under} the ranking model R relative to the ideal ranking model I is the best Validity bias;

Definition 2. The validity bias function Bias ^R (Q) of the query set Q is defined as:

Among them, Bias ^R (Q) represents the average of the validity deviations of all queries _qi in the query set Q under the sorting model R, and |Q| represents the total number of queries _qi in the query set Q;

Definition 3. The robustness variance function _Variance ^R ( _qi ) of query qi is defined as:

Variance ^R (q _i )=[Bias ^R (q _i )-Bias ^R (Q)] ² …(3)

Among them, Variance ^R (q _i ) represents the dispersion degree of the validity bias Bias ^R (q _i ) of the query qi under the ranking model R from the validity bias Bias ^R (Q ₎ of the query set Q;

Definition 4. The robustness variance function Variance ^R (Q) of the query set Q is defined as:

Among them, Variance ^R (Q) represents the average of the robustness variances of all queries _qi in the query set Q under the ranking model R;

The robust ranking learning problem is transformed into a multi-objective optimization problem that considers both effectiveness and robustness. According to the above definitions of the effectiveness bias function and the robustness variance function, the robust ranking learning problem can be formally described for:

Utility(Q)={min Bias ^R (Q),min Variance ^R (Q)}…(5)

That is, in the process of ranking learning, the effectiveness bias function Bias ^R (Q) and the robustness variance function Variance ^R (Q) are simultaneously minimized to train the ranking model. Bias ^R (Q) and Variance ^R (Q), multi-objective intelligent optimization algorithms, such as multi-objective particle swarm optimization algorithm, can be used to minimize the values of Bias ^R (Q) and Variance ^R (Q) to achieve a balanced optimization sorting model for the purpose of validity and robustness.

Preferably, based on the multi-objective particle swarm optimization algorithm framework, iteratively optimizes the two objectives of the effectiveness deviation function and the robustness variance function of the sorting model to train the sorting model, thereby generating the sorting model archive solution set is specifically:

Step 1. Initialize the relevant parameters of the particle swarm;

Step 2. Based on the given ranking learning dataset, under the ideal ranking model I, calculate the best effectiveness of each query _qi

Step 3. Initialize the relevant information of each particle to generate an initial sorting model set P;

Step 4. Initialize iteration counter t=0;

Step 5. Create the initial sorting model archive solution set Archive, in the initial sorting model P, select a non-dominated sorting model, and store it in the sorting model archive solution set Archive;

Step 6. Calculate the crowding distance of each non-dominated solution in the archive solution set Archive of the sorting model;

Step 7. Arrange the non-dominated solutions in the Archive in descending order according to the crowding distance;

Step 8. Perform operations on each particle to update the particle's position and velocity information;

Step 9. Update the sorting model archive solution Archive;

Step 10. Update the individual extreme value Pbest[i] of each particle in the particle swarm P;

Step 11. t=t+1, if t<MAXT, go to step 6, otherwise, output the sorting model to archive each sorting model in the solution set Archive, that is, generate the final sorting model set.

Preferably, the relevant parameters of the step 1 include population size Pop, acceleration factors c1 and c2, initial inertia weight ω ₀ , final inertia weight ω ₁ , maximum iteration number MAXT, objective function number N and mutation probability Mu.

Preferably, the step 3 of initializing the relevant information of each particle to generate the initial sorting model set P is specifically:

31) Randomly initialize the position P[i] of each particle;

Using real number coding, in the feasible ranking model domain of the ranking learning problem, the initial position P[i] of each particle is randomly generated, that is, the weight corresponding to each ranking feature, where 1≤i≤Pop;

32) Initialize the velocity V[i]=0 of each particle;

33) Calculate the validity deviation function and the robustness variance function value of the ranking model;

According to the position P[i] of each particle and the linear sorting scoring function Calculate the score of each document d _ij under each query q _i , where f _ijm (q _i ,d _ij ) represents the M-th dimension sorting feature of the query-document pair (q _i ,d _ij ), according to different Score(q _i , d _ij ) value from large to small, perform top-n quick sort on each document d _ij under each query q _i , and then mark Y _i according to the sorting position of the document and its relevance, and combine the ideal sorting model I, according to the formula ( 1) To formula (4), calculate the validity bias functions Bias ^R (q _i ) and Bias ^R (Q) and the robustness variance functions Variance ^R (q _i ) and Variance ^R (Q ) of the query qi and the query set Q, respectively _. ) to obtain the target value of the effectiveness bias function and the robustness variance function of the ranking model;

34) Initialize the individual extreme value of the particle Pbest[i]=P[i];

35) Determine the global extreme value Gbest of the initial population according to Pbest[i] of each particle.

Preferably, the step 8 performs an operation on each particle to update the position and velocity information of the particle as follows:

81) Randomly select a certain particle i from the non-inferior solution set of the front end with a larger crowding distance in the sorted sorting model archive solution set Archive, and set its position as the global extreme value Gbest;

82) Update the velocity V[i] of particle i according to formula (6):

V _im (t+1)=ω _t *V _im (t)+c1*rand()*[X _im (t)-P _im (t)]+c2*rand()*[X _Gm (t)- P _im (t)]…(6)

Among them, the inertia weight at the t-th iteration c1 and c2 are acceleration constant factors, rand() is a random number between [0, 1], X _im (t) and X _Gm (t) respectively represent the individual extreme value Pbest[i] of particle i at the t-th iteration The mth dimension component of and the mth dimension component of the global extreme value Gbest, the integer i is the particle number, and the value is 1, 2, ..., Pop;

83) Update the position P[i] of particle i according to formula (7):

P _im (t+1)=P _im (t)+V _im (t+1)…(7)

84) Check whether P[i] is within the limit given by the variable, if it exceeds its position range, set the corresponding dimension variable in P[i] to the corresponding boundary value, and set the speed to the reverse direction, ie -V [i];

85) If t<MAXT*Mu, use Mu as the mutation rate to perform the mutation operation on the position P[i] of the particle;

86) Calculate the objective function value of the particle;

Scoring function according to particle position P[i] and linear ordering Calculate the score of each document d _ij under each query q _i , where f _ijm (q _i ,d _ij ) represents the M-th dimension sorting feature of the query-document pair (q _i ,d _ij ), according to different Score(q _i , d _ij ) value from large to small, perform top-n quick sort on each document d _ij under each query q _i , and then mark Y _i according to the sorting position of the document and its relevance, and combine the ideal sorting model I, according to the formula ( 1) To formula (4), calculate the validity bias functions Bias ^R (q _i ) and Bias ^R (Q) and the robustness variance functions Variance ^R (q _i ) and Variance ^R (Q ) of the query qi and the query set Q, respectively _. ) to obtain the target values of the effectiveness bias function and robustness variance function of the ranking model.

Preferably, the step 9 updating the sorting model archive solution set Archive is specifically:

If the particles in the population P are not dominated by any particles in the sorted model archive solution Archive, insert all new non-dominated particles into the sorted model archive solution Archive, and delete all new non-dominated particles in the sorted model archive solution Archive Particles dominated by particles, if the sorting model archive is full, the particles are replaced as follows:

Step 1. Calculate the crowding distance of each non-dominated solution in the archive solution set Archive of the sorting model, and arrange them in descending order of crowding distance;

Step 2. Randomly select a particle in the non-dominated solution of the front with a smaller crowding distance from the bottom of the sorted model archive solution Archive, and replace it with a new particle.

Preferably, the step 10 to update the individual extreme value Pbest[i] of each particle in the particle swarm P is specifically:

According to the dominance relationship, compare the new position of particle P[i] and the pros and cons of Pbest[i], when P[i] is dominant, update the individual best, namely Pbest[i]=P[i].

Preferably, in the third step, based on the idea of PROMETHEEII, a preference order structure evaluation method in the multi-attribute decision-making theory, a Pareto-best Pareto with the largest "net flow" sorting value is selected from the sorting model archive solution set generated in the previous step. The optimal sorting model uses this as the final sorting model trained as follows:

Step 1. Calculate the "outflow" function of each sorting model;

For the sorting model archive solution set Archive finally generated in step 2, calculate the "outflow" function Out(R _i ) value of each sorting model, and define Out(R _i ) as:

Among them, |A| represents the total number of Pareto optimization solutions in the archive solution set Archive of the sorting model;

Step 2. Calculate the "inflow" function of each sorting model;

For the sorting model archive solution set Archive finally generated in step 2, calculate the "inflow" function In(R _i ) value of each sorting model, and define In(R _i ) as:

Step 3. Calculate the "net flow" function for each ranking model;

For the sorting model archive solution set Archive finally generated in step 2, calculate the "net flow" function Net(R _i ) value of each sorting model, and define Net(R _i ) as:

Net(R _i )=Out(R _i )-In(R _i )

Step 4. Obtain the "net flow" sorting value of each sorting model R _i in the sorting model archive solution set Archive according to the "net flow" function Net(R _i ), and select a Pareto optimal solution with the largest "net flow" sorting value as the final ranking model R.

An application of the robust sorting learning method based on multi-objective particle swarm optimization, applying the robust sorting learning method based on multi-objective particle swarm optimization to search engines, wherein the search engines include Baidu Baidu, Google Google, Bing, Sogou, and Yahoo, embed the ranking model trained by this method into the ranking system of the search engine, and use the ranking model to predict the ranking results of the query words that users need to search, thereby improving the overall performance. User satisfaction and enhance user experience, the specific application process is as follows:

Step 1. Integrate the robust ranking learning method based on multi-objective particle swarm optimization into the search engine;

Firstly, data preprocessing is performed on some web pages in the search engine web page index database, and the ranking features of the web pages are extracted and marked to construct a search engine ranking learning data set;

Secondly, on the constructed ranking learning data set, the robust ranking learning method based on multi-objective particle swarm optimization is used to iteratively train the ranking model to generate a robustness-aware ranking model;

Finally, the resulting robustness-aware ranking model is embedded in the ranking system of the search engine;

Step 2. Perform a web search and present the sorted results;

In a search engine that incorporates a robust ranking learning method based on multi-objective particle swarm optimization, users can perform web page searches multiple times in a loop;

First, the user enters the query word they want to search in the search box of the search engine, and clicks search;

Secondly, the ranking system of the search engine calls the search engine web page index database to find out all the web pages that contain the query word, and calculates which web pages should be ranked first and which pages should be ranked at the back to predict the ranking results of web page search. ;

Finally, the sorting results of the web page search are returned to the "Search" page in a predetermined manner to be presented to the search user.

Compared with the prior art, the present invention has the following advantages:

1) The multi-objective optimization model of ranking learning is new.

A multi-objective ranking learning model that considers both effectiveness and robustness is constructed, the bias-variance equilibrium theory is introduced into the ranking learning task, and the corresponding effectiveness bias function and robustness variance function are given to measure the ranking model respectively. The effectiveness and robustness of each of them independently design the objective function without considering the weight assignment of multiple objectives.

2) The method of sorting learning is new.

Based on the multi-objective particle swarm optimization framework and the idea of the preference order structure evaluation method PROMETHEE II in multi-attribute decision theory, a robust ranking learning method based on multi-objective particle swarm optimization is designed to simultaneously optimize the effectiveness and efficiency of the ranking model. Robustness, so that the trained ranking model has a good balance between effectiveness and robustness, thereby improving the overall user experience.

Description of drawings

Fig. 1 is the flow chart of the robust sorting learning method based on multi-objective particle swarm optimization of the present invention;

Fig. 2 is the construction flow chart of the optimization performance index of the sorting model of the present invention;

Fig. 3 is the specific implementation flow chart of the training of the sorting model of the present invention;

Fig. 4 is the preferred specific implementation flow chart of the sorting model of the present invention;

5 is a schematic diagram of a specific embodiment of the present invention;

FIG. 6 is a schematic diagram of a specific embodiment 2 of the present invention.

Detailed ways

The technical solutions in the embodiments of the present invention will be clearly and completely described below with reference to the accompanying drawings in the embodiments of the present invention. Obviously, the described embodiments are part of the embodiments of the present invention, but not all of the embodiments. Based on the embodiments of the present invention, all other embodiments obtained by those of ordinary skill in the art without creative work shall fall within the protection scope of the present invention.

Aiming at the robust ranking learning problem, this patent considers the validity and robustness of the ranking model and optimizes them separately. The robust ranking learning problem is modeled as a multi-objective optimization problem. Based on the bias-variance equilibrium theory, a The corresponding effectiveness bias function and robustness variance function are used to measure the effectiveness and robustness of the ranking model respectively, and are based on the multi-objective particle swarm optimization algorithm framework and the idea of PROMETHEE II, the preference order structure evaluation method in the multi-attribute decision theory. , a robust ranking learning method based on multi-objective particle swarm optimization is designed, which is a robustness-aware multi-objective ranking learning method.

The existing ranking learning methods mainly model the ranking learning problem as classification, regression, ordinal regression and convex optimization. Genetic programming, etc., these techniques are difficult to optimize multiple performance indicators at the same time. Compared with the existing ranking learning method, the present invention is a robust ranking learning method based on multi-objective particle swarm optimization designed for robust ranking learning. The ranking learning method models the ranking learning problem as a multi-objective optimization problem, and the technology adopted is the multi-objective particle swarm optimization technology. The method independently designs multiple objective functions without assigning weights of multiple objectives, and can simultaneously optimize the effectiveness and robustness of the sorting model during the training process of the sorting model, so that the trained sorting model has better performance. Balance between effectiveness and robustness, thereby improving overall user satisfaction experience.

The robust sorting learning method based on multi-objective particle swarm optimization of the present invention considers the effectiveness and robustness of the sorting model at the same time, and constructs the sorting learning task as a multi-objective optimization problem; based on the deviation-variance equilibrium theory, a corresponding The validity bias function and the robustness variance function are used to measure the validity and robustness of the ranking model, respectively, where the validity bias function is used to measure the validity of the ranking model, and the robustness variance function is used to measure the robustness of the ranking model. Robustness; designed based on the multi-objective particle swarm optimization algorithm framework and the idea of PROMETHEE II, the preference order structure evaluation method in multi-attribute decision theory.

The process framework of the robust ranking learning method based on multi-objective particle swarm optimization of the present invention is shown in FIG. First, based on the deviation-variance equilibrium theory, the effectiveness deviation function and robustness variance function of the ranking model are designed, and two optimization performance indicators of ranking learning are constructed; secondly, on the ranking learning data set, based on the multi-objective particle swarm optimization algorithm The framework, iteratively optimizes the two objectives of the validity bias function and the robust variance function of the ranking model to train the ranking model, thereby generating the ranking model archive solution set; Finally, based on the preference order structure evaluation method PROMETHEE II in the multi-attribute decision-making theory The idea is to select a Pareto-optimal sorting model with the largest "net flow" sorting value from the sorting model archive solution set generated in the previous stage as the final sorting model trained.

The robust ranking learning method based on multi-objective particle swarm optimization of the present invention mainly includes three stages: the construction of the ranking model optimization performance index, the training of the ranking model, and the optimization of the ranking model. The specific steps of each stage are as follows:

Stage 1: The construction of the ranking model to optimize the performance indicators.

Based on the bias-variance equilibrium theory, the validity bias function and robustness variance function of the ranking model are designed to construct two optimal performance indicators for ranking learning: validity and robustness, thereby characterizing the validity and robustness of the ranking model index.

The steps of constructing the optimization performance index of the ranking model are shown in Figure 2. The validity deviation function and the robustness variance function of the query and the query set under the ranking model are respectively defined in each step, and are described as follows:

Step 1. Build a validity bias function for the query.

Definition 1. The validity bias function Bias ^R (q _{i )} of query qi is defined as:

in, _{represents the best effectiveness obtained by all documents D i under} the query qi under the ideal sorting model I, that is, all documents are correctly sorted, Represents the actual validity of all documents D _i under the query qi under the ranking model R, and Bias ^R (q _i ) _{represents the actual validity of the query q i under} the ranking model R relative to the ideal ranking model I is the best Validity bias. Here, effectiveness may refer to some commonly used performance indicators in the field of information retrieval, such as Normalized Discounted Cumulative Gain (NDCG) and Expected Reciprocal Rank (ERR), etc. The calculation of each effectiveness indicator The formula is ignored here.

Step 2. Construct the validity bias function of the query set.

Definition 2. The validity bias function Bias ^R (Q) of the query set Q is defined as:

Among them, Bias ^R (Q) represents the average of the validity deviations of all queries _qi in the query set Q under the ranking model R, and |Q| represents the total number of queries _qi in the query set Q.

Step 3. Build a robust variance function for the query.

Definition 3. The robustness variance function _Variance ^R ( _qi ) of query qi is defined as:

Variance ^R (q _i )=[Bias ^R (q _i )-Bias ^R (Q)] ² …(3)

Among them, Variance ^R (q _i ) represents the discrete degree of the validity bias Bias ^R (q _i ) of the query qi under the ranking model R from the validity bias Bias ^R (Q ₎ of the query set Q.

Step 4. Build a robust variance function for the query set.

Definition 4. The robustness variance function Variance ^R (Q) of the query set Q is defined as:

where Variance ^R (Q) represents the mean of the robustness variances of all queries _qi in the query set Q under the ranking model R.

The robust ranking learning problem is transformed into a multi-objective optimization problem that considers both effectiveness and robustness. According to the above definitions of the effectiveness bias function and the robustness variance function, the robust ranking learning problem can be formally described for:

Utility(Q)={min Bias ^R (Q),min Variance ^R (Q)}…(5)

That is, in the process of ranking learning, the validity bias function Bias ^R (Q) and the robustness variance function Variance ^R (Q) are simultaneously minimized to train the ranking model. To this end, based on the optimization performance indicators Bias ^R (Q) and Variance ^R (Q) of the ranking model constructed above, a multi-objective intelligent optimization algorithm, such as a multi-objective particle swarm optimization algorithm, can be used to simultaneously minimize Bias ^R (Q) and Variance R (Q). The value of Variance ^R (Q) is used to balance the effectiveness and robustness of the optimal ranking model.

Stage 2: Training of the ranking model.

Based on the multi-objective particle swarm optimization algorithm framework, the two objective functions of the validity deviation and robustness variance of the ranking model designed in the previous stage are optimized on the ranking learning data set to iteratively train the ranking model, thereby generating the ranking model archive solution. set.

In the specific implementation, for the sorting learning problem, real-number coding is used to represent particles, one particle represents a sorting model, and the search space of particles is M-dimensional (that is, each particle is composed of M-dimensions, and M represents the needs to be considered in the sorting model. the total dimension of the sorted features). The position P and velocity V of the particle can be represented by an M-dimensional vector, the position P of the particle represents the weight corresponding to each sorting feature in the sorting model, and the position P[i] of the particle i is sorted by the M-dimensional sorting in the ith sorting model. The weights corresponding to the features are composed, that is, represented by a vector P[i]=(P _i1 ,P _i2 ,P _i3 ,...,P _im ,...,P _iM ) ^T , where P _im represents the i-th sorting model The weight corresponding to the m-th dimension sorting feature in the middle, and the integer i=1,2,...,Pop, the integer m=1,2,...,M, the integer Pop represents the total size of the particle population, and the integer M represents the sorting in the sorting model. The total dimension of the feature; the velocity V of the particle is used to change the position P of the particle, that is, it is used to adjust the weight of each sorting feature in the sorting model. Similar to the definition of the particle position, the velocity V[i] of the particle i uses a vector V[i]=(v _i1 ,v _i2 ,v _i3 ,..., _{vim ,...,v iM )} ^T to represent.

In the robust ranking learning method based on multi-objective particle swarm optimization, the specific implementation process of the training of the ranking model is shown in Figure 3, and the detailed steps are as follows:

Step 1. Initialize the relevant parameters of the particle swarm.

Relevant parameters include population size Pop, acceleration factors c1 and c2, initial inertia weight ω ₀ , final inertia weight ω ₁ , maximum number of iterations MAXT, number of objective functions N and mutation probability Mu and other parameters.

Step 2. Based on the given ranking learning dataset, under the ideal ranking model I, calculate the best effectiveness of each query _qi

Step 3. Initialize the relevant information of each particle to generate an initial set of ranking models P.

①Randomly initialize the position P[i] of each particle.

Using real number coding, in the feasible ranking model domain of the ranking learning problem, the initial position P[i] of each particle is randomly generated, that is, the weight corresponding to each ranking feature, where 1≤i≤Pop.

②Initialize the velocity V[i]=0 of each particle.

③ Calculate the effectiveness bias function and robustness variance function values of the ranking model.

According to the position P[i] of each particle and the linear sorting scoring function Calculate the score of each document d _ij under each query q _i , where f _ijm (q _i ,d _ij ) represents the M-th dimension ranking feature of the query-document pair (q _i ,d _ij ). _{Perform top-n quick sort on each document d ij under each query qi according to different Score(qi , d ij )} values from large to small, and then mark Y _i according to the sorting position of the document and its relevance _, and combine the ideal sorting Model I, according to formula (1) to formula (4), respectively calculate the validity deviation function Bias ^R (q _i ) and Bias ^R (Q) of query qi and query set Q and the robustness variance function Variance ^R (q _{i )} ) and the various values of Variance ^R (Q) to obtain the target values of the validity bias function and robustness variance function of the ranking model.

④ Initialize the individual extreme value of the particle Pbest[i]=P[i].

⑤ Determine the global extremum Gbest of the initial population according to Pbest[i] of each particle.

Step 4. Initialize iteration counter t=0.

Step 5. Create the initial sorting model archive to resolve the Archive.

In the initial ranking model P, a non-dominated ranking model is selected and stored in the ranking model archive solution set Archive.

Step 6. Calculate the crowding distance for each non-dominated solution in the Archive of the sorted model archive solutions.

Step 7. Arrange the non-dominated solutions in the Archive in descending order by crowding distance.

Step 8. Do the following for each particle to update information such as the particle's position and velocity.

①Randomly select a certain particle i from the non-inferior solution set of the front end with a larger crowding distance in the sorted sorting model archive solution set Archive, and set its position as the global extreme value Gbest.

②Update the velocity V[i] of particle i according to formula (6):

V _im (t+1)=ω _t *V _im (t)+c1*rand()*[X _im (t)-P _im (t)]+c2*rand()*[X _Gm (t)- P _im (t)]…(6) Among them, the inertia weight at the t-th iteration c1 and c2 are acceleration constant factors, rand() is a random number between [0, 1], X _im (t) and X _Gm (t) respectively represent the individual extreme value Pbest[i] of particle i at the t-th iteration The mth dimension component of and the mth dimension component of the global extreme value Gbest, the integer i is the particle number, and the value is 1, 2, ..., Pop.

③ Update the position P[i] of particle i according to formula (7):

P _im (t+1)=P _im (t)+V _im (t+1)…(7)

④ Check whether P[i] is within the limit given by the variable. If it exceeds its position range, set the corresponding dimension variable in P[i] to the corresponding boundary value, and set the speed to the reverse direction, ie -V[ i].

⑤ If t<MAXT*Mu, the mutation operation is performed on the position P[i] of the particle with Mu as the mutation rate.

⑥ Calculate the objective function value of the particle.

Scoring function according to particle position P[i] and linear ordering Calculate the score of each document d _ij under each query qi , where f _ijm (q _i ,d _ij ) represents the M- _th dimension ranking feature of the query-document pair (q _i ,d _ij ). _{Perform top-n quick sort on each document d ij under each query qi according to different Score(qi , d ij )} values from large to small, and then mark Y _i according to the sorting position of the document and its relevance _, and combine the ideal sorting Model I, according to formula (1) to formula (4), respectively calculate the validity deviation function Bias ^R (q _i ) and Bias ^R (Q) of query qi and query set Q and the robustness variance function Variance ^R (q _{i )} ) and the various values of Variance ^R (Q) to obtain the target values of the validity bias function and robustness variance function of the ranking model.

Step 9. Update the sorting model archive to resolve the Archive.

If the particles in the population P are not dominated by any particles in the sorted model archive solution Archive, insert all new non-dominated particles into the sorted model archive solution Archive, and delete all new non-dominated particles in the sorted model archive solution Archive Particles dominated by particles. If the Sorted Model Archive is full, replace the particles as follows:

① Calculate the crowding distance of each non-dominated solution in the archive solution set Archive of the sorting model, and arrange them in descending order of crowding distance.

② randomly select a particle in the non-dominated solution of the front end with a smaller crowding distance from the bottom end of the sorted model archive solution set Archive, and replace it with a new particle.

Step 10. Update the individual extreme value Pbest[i] of each particle in the particle swarm P.

According to the dominance relationship, compare the new position of particle P[i] and the pros and cons of Pbest[i], when P[i] is dominant, update the individual best, namely Pbest[i]=P[i].

Step 11. t=t+1, if t<MAXT, go to step 6, otherwise, output the sorting model to archive each sorting model in the solution set Archive, that is, generate the final sorting model set.

Stage 3: Optimizing the ranking model.

Based on the idea of PROMETHEE II, a preference order structure evaluation method in multiple attribute decision theory, combined with the validity bias function Bias ^R (Q) and the robustness variance function Variance ^R (Q) of each ranking model, the results from the previous stage are generated. The sorting model archived solution set selects a Pareto optimization solution with the largest net flow sorting value, that is, the optimal sorting model, as the final sorting model trained. The preferred specific implementation process of the sorting model is shown in Figure 4, and the specific implementation steps are as follows:

Step 1. Calculate the "outflow" function for each ranking model.

For the sorting model archive solution set Archive finally generated in the second stage, calculate the "outflow" function Out(R _i ) value of each sorting model, and define Out(R _i ) as:

where |A| represents the total number of Pareto-optimized solutions in the sorted model archive solution set Archive.

Step 2. Calculate the "inflow" function for each ranking model.

For the sorting model archive solution set Archive finally generated in the second stage, calculate the "inflow" function In(R _i ) value of each sorting model, and define In(R _i ) as:

Step 3. Calculate the "net flow" function for each ranking model.

For the sorting model archive solution set Archive finally generated in the second stage, calculate the "net flow" function Net(R _i ) value of each sorting model, and define Net(R _i ) as:

Net(R _i )=Out(R _i )-In(R _i )

Step 4. Obtain the "net flow" sorting value of each sorting model R _i in the sorting model archive solution set Archive according to the "net flow" function Net(R _i ), and select a Pareto optimal solution with the largest "net flow" sorting value as the final ranking model R.

Specific embodiment one is as follows:

As shown in Figure 5, it is assumed that there is a standard sorting learning dataset L2Rdataset, which is expressed as a set: L2Rdataset={(<q _i ,d _ij >,y _ij )|q _i ∈Q,d _ij ∈D _i ,y _ij ∈Y _i ,1≤i≤|Q|,1≤j≤|D _i |}, where q _i denotes the ith query, Q denotes the finite query set in the ranking learning dataset, and |Q| denotes the query The total number of centralized queries, d _ij represents the _jth document in the document set Di, _Di represents the document set associated with the query qi, |D _i | _represents the total number of documents in the document set _Di , y _ij represents the relevance label, which reflects the degree of _{relevance between the query qi and the document d ij ,} and can take some level values, such as {1, 2, 3, 4, 5}, Y _i ={y _i1 , y _i2 ,…,y _i|Di| } represents the set of labels associated with the query. The query-document pair <q _i ,d _ij > is described by the M-dimensional sorting feature f, which can be expressed as <q _i ,d _ij >={q _i ,f _ij1 ,f _ij1 ,...,f _ijm ,...,f _ijM }. Through the first stage of the "Order Model Optimization Performance Metrics Construction", four performance metrics were generated: Bias ^R (qi ), Bias R (Q), Variance ^R (qi ) and Variance ^R (Q), where Bias R (q _i ), Bias ^R (Q i ), and Variance R (Q _i ) ^R (Q) and Variance ^R (Q) are the objective functions to be optimized by the multi-objective particle swarm optimization algorithm in the second stage. In the second stage "training of the ranking model", for the given ranking learning dataset L2Rdataset, read the eigenvalues {q _i ,f _ij1 ,f of the query-document pair <q _i ,d _ij > in the L2R dataset _ij1 ,...,f _{ijm ,...,f ijM }} and the correlation label y _ij and other data, under the initial ranking model R, calculate Bias ^R (q _i ), Bias ^R (Q), Variance ^R (q _i ) and Variance The value of ^R (Q), based on the multi-objective particle swarm optimization algorithm framework, iteratively optimizes the validity bias function Bias ^R (Q) and robustness variance function Variance ^R (Q) of the ranking model to continuously update the ranking model, and finally generate a ranking The archived solution set Archive for the model. In the third stage, "Optimization of Ranking Models", for the ranking model generated in the previous stage, the solution set Archive is based on the idea of PROMETHEE II, which is based on the preference order structure evaluation method in the multi-attribute decision-making theory. The "outflow" function value, "inflow" function value and "net flow" function value of each sorting model, and then select a Pareto optimal solution with the largest net flow sorting value from the Archive solution set, that is, the optimal sorting model. As the final ranking model R trained, the ranking model is a robustness-aware ranking model that can be used to predict the document ranking of new queries. When a new query q needs to retrieve documents, the corresponding document set is filtered in the document database D through the sorting system, and the feedback document set is scored based on the generated sorting model R, and then the document set is ranked according to the size of the score. Sort in descending order, generate the sorted results of the predicted documents of the new query q, and output them for display.

The second specific embodiment is as follows:

As shown in FIG. 6 , a robust ranking learning method based on multi-objective particle swarm optimization can be applied to application scenarios such as information retrieval, search engines, recommendation systems, and question answering systems that require actual ranking. Here, the robust ranking learning method based on multi-objective particle swarm optimization is applied to search engines such as Baidu (Baidu), Google (Google), Bing (Bing), Sogou (Sogou) and Yahoo (Yahoo), etc. as an application example. The ranking model trained by the method is embedded in the ranking system of the search engine, and the ranking model is used to predict the ranking results of the query words that the user needs to search, thereby improving the overall user satisfaction and enhancing the user's sense of experience.

The operation implementation process of the robust ranking learning method based on multi-objective particle swarm optimization applied to the search engine is shown in Figure 6, and the implementation steps are as follows:

Step 1. Integrate the robust ranking learning method based on multi-objective particle swarm optimization into the search engine.

Firstly, data preprocessing is performed on some web pages in the search engine web page index database, and the ranking features of the web pages are extracted and marked to construct a search engine ranking learning data set.

Secondly, on the constructed ranking learning dataset, a robust ranking learning method based on multi-objective particle swarm optimization is used to iteratively train the ranking model to generate a robustness-aware ranking model.

Finally, the resulting robustness-aware ranking model is embedded in the ranking system of the search engine.

Step 2. Perform a web search and present the sorted results.

In a search engine that incorporates a robust ranking learning method based on multi-objective particle swarm optimization, users can perform web page searches multiple times in a loop.

First, the user enters the query word they want to search in the search box of the search engine, and clicks search.

Secondly, the ranking system of the search engine calls the search engine web page index database to find out all the web pages that contain the query word, and calculates which web pages should be ranked first and which pages should be ranked at the back to predict the ranking results of web page search. .

Finally, the web search ranking results are returned to the "search" page in a certain manner to be presented to the search user.

The above are only specific embodiments of the present invention, but the protection scope of the present invention is not limited to this. Any person skilled in the art can easily think of various equivalents within the technical scope disclosed by the present invention. Modifications or substitutions should be included within the protection scope of the present invention. Therefore, the protection scope of the present invention should be subject to the protection scope of the claims.

Claims (10)

1. A robustness sequencing learning method based on multi-objective particle swarm optimization is characterized by comprising the following steps:

designing an effective deviation function and a robust variance function of a ranking model based on a deviation-variance balance theory, and constructing two optimization performance indexes of ranking learning;

secondly, training a ranking model by using two targets of an effectiveness deviation function and a robustness variance function of an iterative optimization ranking model on a ranking learning data set based on a multi-target particle swarm optimization algorithm framework, so as to generate a ranking model filing solution set;

and thirdly, based on the idea of a preference order structure evaluation method PROMETHEE II in the multi-attribute decision theory, selecting a Pareto optimal sorting model with the maximum 'net flow' sorting value from the sorting model filing solution set generated in the last step to serve as a trained final sorting model.

2. The method for robustness ranking learning based on multi-objective particle swarm optimization according to claim 1, wherein the effectiveness deviation function and the robustness variance function of the design ranking model are used to construct two optimization performance indexes of ranking learning, specifically:

the effectiveness deviation function and the robustness variance function of the query and the query set under the ranking model are respectively defined as follows:

definitions 1 query q_iOf the validity deviation function Bias^R(q_i) Is defined as:

wherein ,representing a query q_iAll documents D under_iThe best effectiveness achieved under the ideal ranking model I, i.e. all documents correctly ranked,representing all documents D under a query qi_iActual effectiveness, Bias, obtained under the ranking model R^R(q_i) Representing a query q_iDeviation of actual effectiveness under the ranking model R from the optimal effectiveness of the ideal ranking model I;

definition 2. validity deviation function Bias of query set Q^R(Q) is defined as:

among them, Bias^R(Q) represents all queries Q in a set Q under a ranking model R_iIs the average of the validity deviations, | Q | represents the query Q in the query set Q_iThe total number of (2);

definitions 3 query q_iRobust Variance function Variance of (1)^R(q_i) Is defined as:

Variance^R(q_i)＝[Bias^R(q_i)-Bias^R(Q)]²…(3)

wherein, Variance^R(q_i) Representing queries q under a ranking model R_iIs of validity Bias^R(q_i) Validity deviation Bias from query set Q^RA degree of dispersion of (Q);

definition 4. robust Variance function Variance of query set Q^R(Q) is defined as:

wherein, Variance^R(Q) represents all queries Q in a set Q under a ranking model R_iThe mean of the robust variance of (a);

converting the robustness ranking learning problem into a multi-objective optimization problem considering both effectiveness and robustness, and formally describing the robustness ranking learning problem as follows according to the definition of the effectiveness deviation function and the robustness variance function:

Utility(Q)＝{min Bias^R(Q),min Variance^R(Q)}…(5)

namely, in the process of sequencing learning, the effectiveness deviation function Bias is minimized at the same time^R(Q) and the robust Variance function Variance^R(Q) to train a ranking model, for which purpose the optimization performance index Bias based on the above-constructed ranking model^R(Q) and Variance^R(Q) a multi-objective intelligent optimization algorithm, such as a multi-objective particle swarm optimization algorithm, can be used while minimizing the Bias^R(Q) and Variance^RThe value of (Q) is used for achieving the purpose of balancing the effectiveness and the robustness of the optimized sequencing model.

3. The method for learning robust ranking based on multi-objective particle swarm optimization according to claim 2, wherein the framework based on multi-objective particle swarm optimization algorithm trains the ranking model according to two objectives of an effectiveness deviation function and a robust variance function of an iterative optimization ranking model, so as to generate a ranking model filing solution set, specifically:

step 1, initializing relevant parameters of a particle swarm;

step 2, based on the given sequencing learning data set, under the ideal sequencing model I, calculating each query q_iBest effectiveness of

Step 3, initializing the relevant information of each particle to generate an initial sequencing model set P;

step 4, initializing an iteration counter t to be 0;

step 5, establishing an initial sequencing model filing solution set Archive, selecting a non-dominant sequencing model from the initial sequencing model P, and storing the non-dominant sequencing model in the sequencing model filing solution set Archive;

step 6, calculating the congestion distance of each non-dominant solution in the archiving solution set Archive of the sequencing model;

step 7, arranging the non-dominant solutions in Archive in a descending order according to the magnitude of the congestion distance;

step 8, performing operation on each particle to update the position and speed information of the particle;

step 9, updating the archiving solution set Archive of the sequencing model;

step 10, updating individual extreme values Pbest [ i ] of each particle in the particle swarm P;

and 11, if t is t +1, if t is less than MAXT, turning to the step 6, otherwise, outputting each sequencing model in the sequencing model Archive solution set Archive, namely generating a final sequencing model set.

4. The method as claimed in claim 3, wherein the relevant parameters of step 1 include population size Pop, acceleration factors c1 and c2, and initial inertial weight ω₀Final inertial weight ω₁Maximum iteration times MAXT, the number N of objective functions and the variation probability Mu.

5. The method according to claim 3, wherein the initializing the relevant information of each particle to generate the initial ranking model set P in step 3 is specifically:

31) randomly initializing the position P [ i ] of each particle;

real number coding is adopted, and in a feasible ordering model domain of an ordering learning problem, an initial position P [ i ] of each particle is randomly generated, namely a weight corresponding to each ordering characteristic, wherein i is more than or equal to 1 and is less than or equal to Pop;

32) initializing the speed V [ i ] of each particle as 0;

33) calculating an effectiveness deviation function and a robustness variance function value of the sequencing model;

according to the position P [ i ] of each particle]And a linear ranking scoring functionComputing queries q_iEach document d of_ijWherein f is_ijm(q_i,d_ij) Representing query-document pairs (q)_i,d_ij) According to different Score (q)_i,d_ij) Value-from-big to-little for each query q_iLower documents d_ijCarrying out top-n rapid sequencing, and marking Y according to the sequencing position and the relevance of the document_iCombining the ideal ordering model I, respectively calculating the query q according to the formula (1) to the formula (4)_iAnd the validity deviation function Bias of the query set Q^R(q_i) and Bias^R(Q) and a robust Variance function Variance^R(q_i) And Variance^R(Q) to obtain target values for an effectiveness bias function and a robustness variance function of the ranking model;

34) initializing an individual extreme value Pbest [ i ] ═ P [ i ] of the particle;

35) and determining the global extreme value Gbest of the initial population according to the Pbest [ i ] of each particle.

6. The method for robustness ranking learning based on multi-objective particle swarm optimization according to claim 3, wherein the step 8 of performing an operation on each particle to update the position and velocity information of the particle is specifically as follows:

81) randomly selecting a certain particle i from a non-dominant solution set at the front end with a larger crowding distance in the ordered sequencing model filing solution set Archive, and setting the position of the certain particle i as a global extremum Gbest;

82) updating the velocity V [ i ] of particle i according to equation (6):

V_im(t+1)＝ω_t*V_im(t)+c1*rand()*[X_im(t)-P_im(t)]+c2*rand()*[X_Gm(t)-P_im(t)]…(6)

wherein the inertia weight at the t-th iterationc1 and c2 are acceleration constant factors, and rand () is [0, 1 ]]Random number of cells, X_im(t) and X_Gm(t) respectively representing individual extreme values Pbest [ i ] of the particle i at the t-th iteration]The m-th dimension component of Gbest and the m-th dimension component of the global extreme value Gbest, wherein the integer i is the particle number and takes the values of 1,2, … … and Pop;

83) updating the position P [ i ] of the particle i according to equation (7):

P_im(t+1)＝P_im(t)+V_im(t+1)…(7)

84) checking whether P [ i ] is within the limits given by the variables, and if the position range of P [ i ] is exceeded, setting the corresponding dimensional variable in P [ i ] as the corresponding boundary value and setting the speed as the reverse direction, namely-V [ i ];

85) if t < MAXT Mu, then executing variation operation on the position P [ i ] of the particle by taking Mu as variation rate;

86) calculating an objective function value of the particle;

according to the position P [ i ] of the particle]And a linear ranking scoring functionComputing queries q_iEach document d of_ijWherein f is_ijm(q_i,d_ij) Representing query-document pairs (q)_i,d_ij) According to different Score (q)_i,d_ij) Value-from-big to-little for each query q_iLower documents d_ijCarrying out top-n rapid sequencing, and marking Y according to the sequencing position and the relevance of the document_iCombining the ideal ordering model I, respectively calculating the query q according to the formula (1) to the formula (4)_iAnd the validity deviation function Bias of the query set Q^R(q_i) and Bias^R(Q) and a robust Variance function Variance^R(q_i) And Variance^R(Q) to obtain target values for a validity deviation function and a robustness variance function of the ranking model.

7. The method for robustness ranking learning based on multi-objective particle swarm optimization according to claim 3, wherein the step 9 of updating the ranking model Archive solution set Archive specifically comprises:

if the particles in the population P are not dominated by any particle in the order model Archive solution set Archive, inserting all new non-dominated particles in the order model Archive solution set Archive and deleting all particles dominated by the new particles in the order model Archive solution set Archive, if the order model Archive solution set Archive is full, replacing the particles by the following steps:

step 1, calculating the congestion distance of each non-dominant solution in an Archive solution set Archive of a sequencing model, and arranging the congestion distances in a descending order according to the size of the congestion distance;

and 2, randomly selecting one particle in the non-dominant solution at the front end with smaller crowding distance from the bottom end of the sequencing model Archive solution set Archive, and replacing the particle with a new particle.

8. The method for robustness ranking learning based on multi-objective particle swarm optimization according to claim 3, wherein the step 10 of updating the individual extremum Pbest [ i ] of each particle in the particle swarm P is specifically as follows:

and comparing the new position of the particle P [ i ] with the advantages and disadvantages of the Pbest [ i ] according to the dominance relation, and updating the individual optimum when the P [ i ] is dominant, namely Pbest [ i ] ═ P [ i ].

9. The method for learning robustness ranking based on multi-objective particle swarm optimization according to claim 1, wherein in the third step, based on an idea of a preference order structure assessment method promethe II in a multi-attribute decision theory, a Pareto optimal ranking model with a maximum "net flow" ranking value is selected from the ranking model filing solution set generated in the previous step, and the selected ranking model is specifically:

step 1, calculating an outflow function of each sequencing model;

respectively calculating the 'outflow' function Out (R) of each sequencing model for the sequencing model filing solution set Archive finally generated in the step two_i) Value, will Out (R)_i) Is defined as:

wherein, | A | represents the total number of Pareto optimized solutions in the ranking model Archive solution set Archive;

step 2, calculating an inflow function of each sequencing model;

respectively calculating the 'inflow' function In (R) of each sequencing model for the sequencing model filing solution set Archive finally generated In the step two_i) Value In (R)_i) Is defined as:

step 3, calculating a net flow function of each sequencing model;

respectively calculating the Net flow function Net (R) of each sequencing model for the sequencing model filing solution set Archive finally generated in the step two_i) Value, will Net (R)_i) Is defined as:

Net(R_i)＝Out(R_i)-In(R_i)

step 4. according to the Net flow function Net (R)_i) Obtaining each sequencing model R in the sequencing model filing solution set Archive_iThe "net flow" ranking value of (a) and a Pareto optimization solution with the largest "net flow" ranking value is selected as the final ranking model R.

10. The application of the robustness ranking learning method based on multi-objective particle swarm optimization is characterized in that the robustness ranking learning method based on multi-objective particle swarm optimization is applied to a search engine, wherein the search engine comprises Baidu, Google, Bing, Saogouu and Yahoo, a ranking model trained by the method is embedded into a ranking system of the search engine, and the ranking model is used for predicting a webpage ranking result of query words required to be searched by a user, so that the satisfaction degree of the whole user can be improved, and the experience of the user is enhanced, and the specific application process is as follows:

step 1, integrating a robustness sequencing learning method based on multi-objective particle swarm optimization into a search engine;

firstly, performing data preprocessing on partial webpages in a search engine webpage index database, and extracting and labeling ranking features of the webpages to construct a search engine ranking learning data set;

secondly, iteratively training a ranking model to generate a robustness-perceived ranking model by using a robustness ranking learning method based on multi-objective particle swarm optimization on the constructed ranking learning data set;

finally, embedding the generated robustness sensing sequencing model into a sequencing system of a search engine;

step 2, executing web page search and presenting a sequencing result;

in a search engine integrated with a robustness ranking learning method based on multi-objective particle swarm optimization, a user can circularly execute webpage search for multiple times;

firstly, a user inputs a query word to be searched in a search box of a search engine and clicks for searching;

secondly, a search engine webpage index database is called by a search engine ranking system, all webpages containing the query word are found out from the database, and the ranking results of webpage search are predicted by calculating which webpages should be ranked in front and which should be ranked behind;

and finally, returning the webpage search sorting result to a search page according to a set mode for presenting to a search user.