CN103530321B - A kind of ordering system based on machine learning - Google Patents

Abstract

The invention provides a sorting system based on machine learning, wherein: the data collection and data preprocessing module collects the data required for sorting learning; the training set construction module includes: in the initial stage, from the stored massive unlabeled query-text data, Randomly select some samples and manually mark them according to their correlations to build an initial training set; in the iterative stage, call the ranking learning module and execute the sampling algorithm based on the built ranking model to select the most informative samples from the unlabeled data for correlation label. Store the marked data in the storage module; the ranking learning module builds the ranking model; the training set building module and the ranking learning module interact iteratively; the predictive ranking module invokes the sorting model to retrieve the corresponding text prediction correlation for the query input by the user , and sorted according to the magnitude of the correlation. The invention can improve the sorting accuracy of the retrieval results by the sorting system, better display the retrieval results, and meet the needs of users.

Description

A sorting system based on machine learning

technical field

The present invention relates to the fields of machine learning and information retrieval, in particular to a sorting system based on machine learning.

Background technique

Today's society is an information society. With the development of modern science and technology, information has grown explosively. How to quickly and accurately find the information you need from the massive amount of information is the core problem that information retrieval technology needs to solve. Whether information retrieval can better meet the needs of users is directly related to whether the massive information is fully utilized, which is of great significance to economic and social development.

As a core technical problem in the field of information retrieval, ranking has been widely used in information retrieval problems such as web search, recommendation, and online advertisement. Taking web search as an example, such as Google, Baidu, Bing, Yahoo, etc., the task of the ranking system is to build a ranking model and sort the searched web pages according to the predicted relevance. In the ranking system based on machine learning, training the ranking model is the core part of the ranking system. The performance of the ranking model is highly related to the quality of the training set. Due to the huge cost of data labeling, it is impossible to manually label the massive data collected. At present, the method widely used in sorting systems is to randomly select a part of data from massive data for labeling, so as to maintain the characteristics of data distribution. However, the disadvantage is that due to ignoring the relationship between the ranking model and the training set, the selected training set is difficult to guarantee the performance of the ranking model, which leads to the low ranking accuracy of the ranking system and is difficult to meet the needs of users. .

Contents of the invention

Aiming at the deficiencies of the prior art, the object of the present invention is to provide a sorting system based on machine learning, which aims to make full use of the relationship between the sorting model and the training set, improve the sorting accuracy of the sorting system for retrieval results, and better Display search results to meet user needs.

To achieve the above object, the present invention adopts the following technical solutions:

The invention provides a sorting system based on machine learning, the system includes: data collection and data preprocessing module, training set construction module, sorting learning module, predictive sorting module and data storage module, wherein:

The data collection and data preprocessing module collects the data required for sorting learning, obtains the query and its text, which is unlabeled text, and performs feature processing and data normalization on the collected query-text data Operation, stored in the data storage module;

The training set construction module, the training set construction includes two stages: the initial stage, from the stored massive unlabeled query-text data, randomly select some data according to the correlation manual labeling, construct the initial training set; the iterative stage, call the sorting learning The module executes the Sampling algorithm based on the sorting model that has been built, selects the most informative samples from the unlabeled data, performs query-text correlation labeling, and expands the existing training set; the labeled The data is stored in the data storage module;

The sorting learning module calls the marked data in the data storage module to train the sorting model and build the sorting model;

The training set building module and the sorting learning module are carried out interactively and iteratively, so as to make full use of the relationship between the training set and the sorting model, and improve the sorting accuracy of the sorting system for the retrieval results. Iteration termination conditions include a variety of: manually set the number of iterations, the performance of the sorting system meets user needs, etc.; the sampling algorithm first adds Gaussian noise to the stored unlabeled data, and then calls the sorting model to perform correlation prediction to obtain the predicted score distribution, and then Transform the predicted score distribution into a predicted rank distribution, and finally select the sample data with the least certain rank predictions.

The predictive sorting module, after the iteration, invokes the sorting model established by the sorting learning module, searches for the user's query, retrieves its corresponding text, performs correlation prediction, sorts according to the correlation size, and presents it to the user;

The data storage module stores two parts of data: one part stores unmarked data, and the other part stores marked data. Among them, the unlabeled data is called by the training set building module for sample selection, and when it is selected and labeled, it is transferred to labeled data. The labeled data is called by the ranking learning module to train the ranking model.

Compared with the prior art, the sorting system based on machine learning of the present invention makes full use of the relationship between the sorting model and the training set, and can select the most informative samples, thereby training a high-performance sorting model and realizing The purpose of accurate sorting in the sorting system can better meet the needs of users and has important application value.

Description of drawings

Other characteristics, objects and advantages of the present invention will become more apparent by reading the detailed description of non-limiting embodiments made with reference to the following drawings:

Fig. 1 is a frame diagram of a sorting system based on machine learning in the present invention.

Fig. 2 is a flow chart of the sampling algorithm in the present invention.

Fig. 3 is a performance comparison diagram between the sorting system based on machine learning in the present invention and the prior art.

detailed description

The present invention will be described in detail below in conjunction with specific embodiments. The following examples will help those skilled in the art to further understand the present invention, but do not limit the present invention in any form. It should be noted that those skilled in the art can make several modifications and improvements without departing from the concept of the present invention. These all belong to the protection scope of the present invention.

In this embodiment, a ranking system based on machine learning is constructed, and the commercial search ranking data provided by Baidu is used for testing. In this embodiment, the two most important evaluation criteria for measuring sorting accuracy in the current information retrieval field, DCG@10 and MAP (Mean Average Precision), are selected for effect evaluation, and compared with existing representative technologies compared. The invention has more accurate sorting accuracy and can better display search results to users.

The system described in this embodiment includes:

Data collection and data preprocessing module: responsible for collecting data for ranking learning. In a ranking system, queries and their corresponding texts are collected, and a query generally corresponds to multiple texts. For example: the query word is Sina, and the corresponding texts include: Sina Homepage, Sina Mailbox, Sina Baidu Encyclopedia, etc. Afterwards, corresponding features are extracted for each query-text pair data, and there are three types of features for ranking data: query features, text features, and query-text features. For example: the frequency of query words appearing in the text, the PageRank value of the text, etc. After feature extraction, each query-text pair data can be represented by a feature vector. All text features contained in each query are normalized and stored in the storage module.

Training set building block: responsible for building the training data required for ranking learning. Due to the huge cost of manual labeling of data, it is impossible to label all the massive data stored. The construction of the training set in the present invention includes the following two stages. In the initial stage, that is, without any training data, some data is randomly selected from the stored massive data for manual labeling as the initial training set, and the ranking learning module is called to start training the initial ranking model. After that, the training set is constructed iteratively. In the iterative phase, the sample selection algorithm is executed, and the sample selection algorithm described in this embodiment includes the following steps:

1) Add Gaussian noise to stored unlabeled data: For each stored query-text pair data sample, add Gaussian noise independently to its features. After adding, each sample will have m noise samples, which surround the original sample in the feature space and have a Gaussian distribution.

2) Call the ranking model for correlation prediction and obtain the distribution of prediction scores: After obtaining the noise samples, call the ranking model in the ranking learning module to predict the correlation of the noise samples. And the predicted scores of m noise samples around the original sample are used as the predicted score distribution of the original sample under the current ranking model.

3) Convert the predicted score distribution to the predicted ranking distribution: According to the query-text structure, convert the obtained predicted score distribution into the predicted ranking distribution, assuming that a query contains n texts.

■The conversion process of the predicted ranking distribution of the query is:

(a) Randomly sample a prediction score for each text according to the prediction score distribution of n texts contained in the query, and n prediction scores can be obtained;

(b) Sort the n prediction scores according to their size, and a prediction ranking can be obtained;

(c) Repeat the steps (a) and (b) above several times to obtain the predicted ranking distribution of the query under the current ranking model.

■The conversion process of the predicted ranking distribution of the text is:

(a) Fix the prediction scores of the remaining n-1 texts of the query to which the text belongs to the prediction value of the original sample;

(b) Randomly select a score from the predicted score distribution of the current text, and add the remaining n-1 predicted scores to obtain n predicted scores;

(c) Sorting the n prediction scores according to size can obtain a prediction ranking;

(d) Repeat the above steps (b) and (c) multiple times to obtain the predicted ranking distribution of the text.

4) Select the most uncertain sample data for sorting prediction: After obtaining the predicted sorting distribution of the query and text, sample from the sorting distribution, and use the DCG-like gain function to calculate the gain value of each sampling sort:

$\mathrm{<span\; class="notranslate">\; g</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; r</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; no</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; 2</span>}}^{\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; /</span>{\mathrm{<span\; class="notranslate">\; log</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; )</span>$

where s( _{ri) denotes the predicted relevance of the text at position r i to} the query. r indicates a sort. N sorts are sampled from the sort distribution, correspondingly, N gain values can be calculated, and the variance can be calculated. According to the above algorithm steps, under the current ranking model, for samples with uncertain ranking predictions, the corresponding N gain values change greatly, resulting in larger variance. According to the calculated variance value, the training samples for constructing the ranking model are actively selected. According to the query-text structure, there are three sample selection methods.

■ Query-based: Select K queries with the largest variance from the stored unlabeled data.

■ Text-based: Select K texts with the largest variance from the stored unlabeled data.

■Based on query-text two-stage: first select K ₁ queries with the largest variance from the stored unlabeled data, and then select K ₂ texts with the largest variance among the selected queries.

After executing the above sampling algorithm, mark the selected sample data. In the data of ranking learning, it needs to be marked according to the query-text correlation. The query-text correlation is divided into 5 levels: {very relevant, relatively relevant, relevant, irrelevant, and extremely irrelevant}, which are respectively marked as { 4,3,2,1,0}. Table 1 gives an example of labeling:

Table 1 Query-Text Relevance Annotation Example

After the data is marked with relevance, it is stored in the data storage module.

Sorting learning module: call the marked training data in the data storage module, and train the sorting model. In the present invention, a representative sorting model is used: gradient lifting decision tree, as the sorting equation:

$\mathrm{<span\; class="notranslate">\; f</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\underset{\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; no</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}{\mathrm{<span\; class="notranslate">\; \&lambda;</span>}}_{\mathrm{<span\; class="notranslate">\; t</span>}}{\mathrm{<span\; class="notranslate">\; T</span>}}_{\mathrm{<span\; class="notranslate">\; t</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; )</span>$

Wherein, each tree model T _t (x) is constructed by dividing the feature space by training data. The parameter λ _t is searched through the gradient direction of the function gradient of the prediction error of the sample data in the training set to obtain the optimal value. In this embodiment, a total of 100 tree models are constructed, T=100.

The above-mentioned training set construction module and ranking learning module are carried out interactively and iteratively, so that the relationship between the training set and the ranking model can be fully utilized to achieve the purpose of accurate ranking by the ranking system. The iteration termination condition can be in the following ways: manually setting the number of iterations, sorting system performance to meet user needs, and so on. In this embodiment, the iteration termination condition is: the number of iterations is manually set: 10 times.

Predictive ranking module: After the above iterative process is over, for the user's newly input query, the system retrieves the corresponding text, calls the sorting model trained in the ranking learning module to predict the query-text correlation, and predicts the relevance score according to the prediction The values are sorted by size, and finally the sorted results are returned to the user.

Data storage module: store two parts of data, according to the query-text structure, one part sequentially stores unmarked query-text pair data, and the other part sequentially stores query-text pair data and their correlation annotations. Among them, the unlabeled data is called by the training set building block to perform the sampling in the initial stage and the sampling algorithm in the iterative stage. When it is selected to mark the correlation, it will be saved as marked data. The labeled data is called by the ranking learning module to train the ranking model.

Implementation Effect

According to the above technical solution, the commercial search ranking data provided by Baidu is used. In the ranking system, DCG@10 and MAP, two most important evaluation criteria for measuring ranking accuracy in the field of information retrieval, are selected, and compared with the existing representative technologies.

In order to fully test the technical effect brought by the present invention and reduce the random error of the system. Each performance comparison test of the sorting system is independently tested 10 times and the average result is calculated, and the average value is used as the final performance index. Among them, RBSS is the sorting system of the present invention, and RAND is a technique widely used in commercial sorting systems at present. For the convenience of description, the suffix mark -Q indicates that the query-based sampling algorithm is implemented in the training set building block of the ranking system, -D indicates that the text-based sampling algorithm is implemented in the training set building block of the ranking system, and -QD indicates that the sampling algorithm is implemented in the ranking system training set The query-text two-stage sampling algorithm is implemented in the training set building block.

Table 2 shows the performance comparison results. It can be seen that the performance of the sorting system of the present invention is significantly better than that of the existing technology RAND in terms of the two performance evaluation indexes of DCG@10 and MAP.

Table 2 Sorting system performance comparison

In order to further verify the performance improvement brought by the present invention, in the iterative process of executing the sample selection algorithm of the training set building block, a sorting system performance comparison test was carried out after each step of iteration. Figure 3 shows the system performance during the iterative process. comparison results. The abscissa indicates the number of iterations of the sampling algorithm in the sorting system, and the ordinate is the performance evaluation index of the sorting system. The higher the score, the more accurate the sorting system is. It can be seen that, in the process of iteratively constructing the training set, the sorting system of the present invention is consistently better than the currently widely used technology RAND.

It can be seen from the above tests that the machine learning-based sorting system of the present invention can effectively improve the sorting accuracy, thereby better displaying retrieval results and meeting user needs. The invention brings obvious technical effects in Baidu commercial search sorting, and has important application value.

Specific embodiments of the present invention have been described above. It should be understood that the present invention is not limited to the specific embodiments described above, and those skilled in the art may make various changes or modifications within the scope of the claims, which do not affect the essence of the present invention.

Claims (4)

1. A sorting system based on machine learning, characterized in that the system includes: data collection and data preprocessing module, training set building module, sorting learning module, predictive sorting module and data storage module, wherein: The data collection and data preprocessing module collects the data required for sorting learning, obtains the query and its text, which is unlabeled text, and performs feature processing and data normalization on the collected query-text data Operation, stored in the data storage module; The training set construction module, the training set construction includes two stages: the initial stage, from the stored massive unlabeled query-text data, randomly select some data according to the correlation manual labeling, construct the initial training set; the iterative stage, call the sorting learning The module executes the sample selection algorithm based on the sorting model that has been built, selects the most informative samples from the unlabeled data, performs query-text correlation labeling, and expands the existing training set; stores the labeled data in data storage module; The sorting learning module calls the marked data in the data storage module to train the sorting model and build the sorting model; The above-mentioned training set construction module and the sorting learning module are carried out interactively and iteratively, and the iteration termination conditions include manually setting the number of iterations or the performance of the sorting system to meet user needs; the sampling algorithm first adds Gaussian noise to the stored unlabeled data, Then call the sorting model to perform correlation prediction to obtain the predicted score distribution, then convert the predicted score distribution into a predicted ranking distribution, and finally select the sample data with the most uncertain sorting prediction; the selection of the most uncertain sample data for sorting prediction refers to: get After querying and predicting the sorting distribution of text, sample from the sorting distribution, use the DCG-likegain function to calculate the gain value of each sampling sort, calculate N gain values, and calculate the variance, and use the calculated variance to measure the sorting prediction. Determine, select the sample data, where N is the number of samples for predicting sorting; The predictive sorting module, after the iteration, invokes the sorting model established by the sorting learning module, searches for the user's query, retrieves its corresponding text, performs correlation prediction, sorts according to the correlation size, and presents it to the user; The data storage module stores two parts of data: one part stores unlabeled data, and the other part stores labeled data, wherein the unlabeled data is called by the training set construction module for sample selection, and when selected and labeled, transfer to It is stored as labeled data, and the labeled data is called by the ranking learning module to train the ranking model. 2. The sorting system based on machine learning according to claim 1, characterized in that, said data collection and data preprocessing module: responsible for collecting data for sorting learning, collecting queries and their corresponding texts, and one query can correspond to Multiple texts, and then extract corresponding features for each query-text pair data. There are three types of features for sorting data: query features, text features, and query-text features. After extracting features, each query-text pair data is used A feature vector representation, all text features contained in each query are normalized and stored in the storage module. 3. The sorting system based on machine learning according to claim 1 or 2, wherein the training set construction module executes a sample selection algorithm in an iterative phase, and the sample selection algorithm comprises the following steps: 1) Add Gaussian noise to the stored unlabeled data: For each stored query-text pair data sample, add Gaussian noise independently to its features. After adding, each sample will have m noise samples. These noise samples are in The feature space surrounds the original sample and has a Gaussian distribution; 2) Call the ranking model for correlation prediction and obtain the prediction score distribution: After obtaining the noise samples, call the ranking model in the ranking learning module to predict the correlation of the noise samples, and use the prediction scores of m noise samples around the original sample as The predicted score distribution of the original sample under the current ranking model; 3) Transform the predicted score distribution into a predicted ranking distribution: according to the query-text structure, convert the resulting predicted score distribution into a predicted ranking distribution; 4) Select the most uncertain sample data for sorting prediction: After obtaining the predicted sorting distribution of the query and text, sample from the sorting distribution, and use the DCG-like gain function to calculate the gain value of each sampling sort: $\mathrm{<span\; class="notranslate">\; g</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; r</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; no</span>}}{<span\; class="notranslate">\; \&Sigma;</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; 2</span>}}^{\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; /</span>{\mathrm{<span\; class="notranslate">\; log</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; )</span>$ Among them, n is the number of texts; s(r _i ) represents the predicted correlation between the text at position r _i and the query, and r represents a ranking; N rankings are sampled from the ranking distribution, and N gain values are calculated accordingly , and calculate the variance; actively select the training samples for constructing the ranking model according to the calculated variance; after executing the above sampling algorithm, mark the selected sample data, and in the data for sorting learning, it is necessary to follow the query-text correlation For labeling, the query-text correlation is divided into five levels: {very relevant, relatively relevant, relevant, irrelevant, and extremely irrelevant}, which are marked as {4, 3, 2, 1, 0} respectively. 4. The sorting system based on machine learning according to claim 3, wherein the sorting learning module calls the marked training data in the data storage module, trains the sorting model, and uses the gradient boosting decision tree model as the sorting equation : $\mathrm{<span\; class="notranslate">\; f</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\underset{\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; T</span>}}{<span\; class="notranslate">\; \&Sigma;</span>}}{\mathrm{<span\; class="notranslate">\; \&lambda;</span>}}_{\mathrm{<span\; class="notranslate">\; t</span>}}{\mathrm{<span\; class="notranslate">\; T</span>}}_{\mathrm{<span\; class="notranslate">\; t</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; )</span>$ Among them, each tree model T _t (x) is constructed by dividing the feature space from the training data, and the parameter λ _t is searched to obtain the optimal value through the function gradient direction of the prediction error of the sample data in the training set, and T represents the number of tree models.