System and method for using anchor text as training data for classifier-based search systems

A computer implemented information retrieval system is provided. The system includes a user input configured to receive a user query relative to the corpus. A machine learning classifier is trained with a first set of training data comprising anchor text relative to at least some of the documents in the corpus. A processing unit is adapted to interact with the classifier to obtain search results relative to the query using the machine learning classifier. In some aspects, the classifier is also trained with a second set of training data. A method of integrating a new document into a corpus of documents is also provided. A method of training a machine learning classifier for retrieving documents from a corpus using two distinct types of training data is also provided.

FIELD OF THE INVENTION

The present invention relates in general to the field of information technology. More particularly, the present invention relates to a system and method for training classifier-based search systems.

BACKGROUND OF THE INVENTION

Search engines are now commonplace in many software applications. Search engines may be used for searching for text strings in applications such as word processors, for searching for help in sophisticated software as varied as spreadsheets and operating systems, and for searching for uniform resource locators (URLs), references and other documents in web-based search engines. The effectiveness of any one search may be abstractly judged by whether the top few returned documents are the documents actually sought by the user. The returned list should preferably be sorted by relevance to the user in the context of the search terms present in the user query and possibly the state associated with the user query. This ordering of documents makes it easier for a user to select the document that he or she believes has the greatest relevance to the search.

A search engine is generally used to provide a list of documents such that the documents have a relation to the search terms. Since sets of documents can be extremely large, and since any one search engine may have access to multiple document sets, the sheer volume of documents retrieved by search could be large. Ranking the documents according to some relevance criteria is one way to assist the user in finding the preferred document(s).

Recently, search engines have been augmented with machine learning classifiers that are able to help provide search documents with high relevance. Such classifiers are generally based on training data based on user feedback data: click patterns (i.e. “click-throughs”) and/or explicit user satisfaction ratings (i.e. “explicit feedback”) which indicate which documents are most relevant for a user query (and the state associated with the user query). User feedback data also includes, but is not limited to, previous user search history or the entry point of the search. Mappings between user-generated queries and the documents the user visits and/or marks as relevant are recorded. These mappings are then used to train a machine learning classifier model, that takes as input the user query (and the state associated with the user query), and produces as output a list of documents (the “classes”) with associated relevance scores. Classifiers are evaluated with “test sets,” generally collected from click-through and/or explicit user feedback distinct from the data used for the training set.

While this approach represents a significant improvement in the field of information retrieval, it does have one limitation. Namely, as a new document is added to the collection or corpus, it will initially have no user feedback nor click-through data associated with it. Accordingly, the machine learning classifier will not select the new document as having any relevance to a user's search. Thus, the search will either not return the new document, or may return it and place it at the bottom of a vast list of search results. While the machine learning classifier could be retrained using manual methods to better recognize the new document, such methods become prohibitively labor intensive as the number of new documents grows beyond a trivial number.

Thus, there is a continuing need for information retrieval systems that employ machine learning classifiers to automatically recognize and be trained for new documents with minimal manual intervention.

SUMMARY OF THE INVENTION

A computer implemented information retrieval system is provided. The system includes a user input configured to receive a user query relative to the corpus. A machine learning classifier is trained with a first set of training data comprising anchor text relative to at least some of the documents in the corpus. Anchor text is the text of the links or “anchors” in corpus documents to documents in the corpus. A processing unit is adapted to interact with the classifier to obtain search results relative to the query using the machine learning classifier. In some aspects, the classifier is also trained with a second set of training data. A method of integrating a new document into a corpus of documents is also provided. A method of training a machine learning classifier for retrieving documents from a corpus using two distinct types of training data is also provided.

DETAILED DESCRIPTION OF ILLUSTRATIVE EMBODIMENTS

FIG. 2illustrates a block diagram of an exemplary information retrieval system with which embodiments of the present invention are useful. A query210containing a user's search terms is entered into a search engine212. Search engine212processes input query210, and then applies the search terms produced to an available document collection or corpus230by searching for these terms in the documents corresponding to input query210. The returned documents may then be ranked using a ranking algorithm, such as the known OKAPI algorithm, or one of its derivatives, or known vector space-based algorithms. The ranked documents are in turn provided to the result combiner216.

In a parallel activity, the search engine may also use a machine learning classifier214derived from a user feedback data store220to search for documents previously retrieved and selected by a user where similar search terms were used. Classifier214is an implementation of a machine-learning environment where user selections against a list produced in a search are used to tally the document selections against query parameters. Query click-though data is metadata obtained from previous searching sessions with the search engine. Query click-through data represents the actual selection of a document by at least one user under the conditions of a search. User feedback can include explicit feedback received from the user, or feedback that is inferred from what documents the user selects (referred to herein as “clickthrough”). Explicit feedback is generally obtained by recording the selection that a user makes as to which returned document is more relevant to his purposes after viewing his search results. User feedback query logs generally represent relevant sections from multiple users and can be of value in correlating search terms with documents. This correlation may be especially strong if the query logs were generated while different users were using a search tool on the same document set that issued in the document collection in any one implementation. However, this condition is not a requirement. A query log may take the form of a matrix of possible search words versus relevant documents. The intersection of the two parameters is the frequency of occurrence of the search term associated with the document. The frequency of occurrence may be the result of user click-through hits on the respective document and search term. Tabularized query click-through data is a valuable correlation of search terms and documents based on their frequency of association.

Returning toFIG. 2, the terms produced for the classifier by the search engine212for query210may be passed to the classifier214. The classifier214was created offline from the user feedback data store220. The classifier is used to search for documents containing the terms produced for this purpose by the search engine212.

In the information retrieval context, a ranking model is an algorithm that computes the likelihood that a document containing search terms is the single document of interest. Once a likelihood is calculated and assigned to each document in a list, the entire list may be sorted according to the likelihood rankings. The resulting list is an ordered list where the document assigned the highest likelihood generally occurs first. The models used in association with the classifier214may include but are not limited to the maximum entropy probability model and/or the Naïve Bayes probability model. Classifier214then orders the list of returned query log document data according to the ranking where the highest likelihood document appears first. The lists can be combined as indicated at block216.

In accordance with one broad aspect of the present invention, anchor text in a document corpus is extracted from some or all of the documents and used as training data for a machine learning classifier. Embodiments of the present invention are particularly useful in at least two real world situations. First, when a document is created and added to the corpus, it will, by definition, have no associated user feedback data. Anchor text can be used relative to such new documents in order to be a surrogate for the missing user feedback data. So anchor text can be used as an additional source of training data for a machine learning classifier. Accordingly, when a search system that is based on a classifier model on a corpus that includes a link structure to other documents (i.e. anchors) within and outside of the corpus, the anchor text can be leveraged as training data for the search classifier. Thus, anchor text can be used to anchor destination mappings in the same manner that query to visited documents are used.

FIG. 3is a flow diagram of a method300for training a machine classifier with anchor text for new documents. Method300begins at block302when an author creates a new document. As set forth above, one potential problem with classifier-based search systems that are trained on traditional user feedback data is that new documents that are published into the corpus do not have any user feedback data. Thus, they are not likely to be surfaced as a result of subsequent queries, and as such it will be difficult to collect user feedback data on them via the search system. This is a basic dilemma in that user feedback data cannot be gathered without surfacing these documents, and these documents cannot be surfaced without user feedback data. At block306, the document author(s) modify original documents in the corpus to include anchors such as hyperlinks to the new document(s) authored in block302. Generally, blocks302and306are done together before block304, however block304can be executed twice, one time each after block302and block306. At block304, the new document created in block302and the modified original corpus documents from block306are all published into the corpus.

At block308, anchor text is extracted from the modified documents in the corpus. The extraction of anchor text can be done automatically using programmatic algorithms that parse each document in the corpus to search for anchor text. Additionally, the anchor text can be received directly from the document author(s) when the documents are modified for publication into the corpus. In any event, a significant listing of anchor text is extracted from the corpus documents.

At block310, the anchor text to document mappings are added to the classifier training data. This training data can also be supplemented with additional document-specific data such as title-to-document mappings. A method of combining multiple disparate types of training data in an effective manner is described more fully below with respect toFIG. 4.

At block312, the machine learning classifier is retrained with the new training data and published. Accordingly, if the new document is referenced by other documents in the corpus by virtue their anchor text, a search that is relevant to the newly authored document may, in fact, surface the new document by virtue of the modified documents' anchor text. Thus, the new document will be surfaced faster and receive user feedback more quickly thus integrating the document and its associated relevance into the corpus more effectively.

FIG. 4is a flow diagram of a method400of merging two sets of different types of training data into a single training data set for training a machine-learning classifier. For example, one type of training data is the traditional click-through data for existing documents in the corpus. Another, different type of training data is the anchor text described above with respect toFIG. 3. If these two sets of training data were naively merged, they may generate an unbalanced number of one type of data versus the other. Thus, method400sets forth a technique for weighing one type of data relative to the other. More specifically, if C is the set of original click-through data, and A is the set of anchor text training data, method400creates a combined training set T such that: T=C∪λ*A.

In particular, most classifier trainers support specifying weights on the individual training examples. The λ weight on anchor text training is applied to all training examples in that set. Given the flexibility of the λ weight, method400also determines the optimal weight (i.e. finding the optimal value of λ). To do so, method400iteratively creates different classifiers using different values of λ and tests them against a development test set to determine which weighting value of λ provides the highest relevance. A “development test set” is a portion of the test set that is set aside for training instead of testing. A development test set can also be extracted from the training set. When this is done, the data extracted for the development test set is not used for the conventional training. Development test sets are a standard methodology in classification technology that allow for more complex training algorithms. These test sets are usually formed by using a portion of the conventional test set (thus removing it from the conventional test set). Note that the development test set and the actual test can overlap or even be the same, but they should be mutually exclusive to achieve high experimental rigor. Method400begins at blocks402and404where anchor text is gathered from the documents in the corpus, and the click-through data is derived from user behavior.

At block406, an iteration is begun where for all values of λ in the set of λ values, blocks408,410and412are performed. At block408, the training set T is constructed by taking the union of the click-through data gathered at block404with the anchor text data extracted at block402weighted by the selected λ value for the particular iteration. At block410, the classifier is trained with the training set T and at block412, the classifier is tested on the development test, generated at block413and provided to block412, and the relevance, or some other suitable metric of the classifier is recorded. At block414, the method determines whether the particular value of λ for the iteration was the last value of λ in the set of λ values. If not, control returns to block408and the next λ value in the set of λ values is selected for the next iteration. If however, at block414, it is determined that all λ values have been run, control passes to block416where the relevance scores and associated λ values are reviewed. The optimal λ value is then selected and the search classifier is trained with the optimal λ value recorded during the iterative testing of blocks408,410and412. As used herein, “optimal” means the lambda that gives highest relevance on the development test set, by some relevance measure, e.g., precision/recall. Once the search classifier is trained, it is published. While method400has been described with respect to combining click-through data with anchor text data, it is applicable to the combination of any two disparate type of training data for a machine learning classifiers.