SYSTEMS AND METHODS OF PREDICTING RESOURCE USEFULNESS USING UNIVERSAL RESOURCE LOCATORS

• US 20090210369A1
• Filed: 02/15/2008
• Published: 08/20/2009
• Est. Priority Date: 02/15/2008
• Status: Active Grant

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Shao, Zheng, Fu, Wenjie
• Granted Patent: US 7,908,234 B2
• Time in Patent Office: Days
• US Class Current: 706/21
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks

Abstract

A method, system and apparatus are provided to train a usefulness prediction model to generate a usefulness prediction in connection with a given universal resource locator (URL), the training of the usefulness prediction model being based on a training set of URLs and a count of negative URLs and a count of positive URLs identified by the training set, and for each feature extacted from the URLs in the training set, a count of the positive URLs in the training set that include the feature and a count of the negative URLs in the training set that include the feature. One or more features of the given URL are extracted, and the extracted features are used together with the usefulness prediction model to generate a usefulness prediction for the given URL.

Claims

1. A method comprising:

training a usefulness prediction model to generate a usefulness prediction in connection with a given universal resource locator (URL), the training of the usefulness prediction model being based on a training set of URLs, a count of negative URLs and a count of positive URLs identified by the training set, and for each feature extracted from the URLs in the training set, a count of the positive URLs in the training set that include the feature and a count of the negative URLs in the training set that include the feature;

extracting one or more features of the given URL; and

using the one or more features extracted from the given URL and the usefulness prediction model to generate the usefulness prediction in connection with the given URL.

2. The method of claim 1, further comprising:

determining a usefulness of a resource associated with the given URL based on the usefulness prediction for the given URL.

3. The method of claim 1, using the one or more features extracted from the given URL and the usefulness prediction model to generate the usefulness prediction in connection with the given URL further comprising:

generating a positive usefulness prediction value in connection with the given URL using the one or more features extracted from the given URL and the usefulness prediction model;

generating a negative usefulness prediction value in connection with the given URL using the one or more features extracted from the given URL and the usefulness prediction model; and

comparing the positive usefulness prediction value with the negative usefulness prediction value to generate the usefulness prediction in connection with the given URL.

4. The method of claim 3, further comprising:

identifying a resource associated with the given URL as useful in a case that the positive usefulness prediction value is equal to or greater than the negative usefulness prediction value.

5. The method of claim 3, further comprising:

identifying a resource associated with the given URL as not useful in a case that the positive usefulness prediction value is less than the negative usefulness prediction value.

6. The method of claim 3, the generating a positive usefulness prediction value further comprising:

determining the positive usefulness prediction value to be a ratio of a positive probability to a sum of the positive probability and a negative probability, the positive probability being a product of a positive URL probability and a positive feature probability for each feature extracted from the given URL, the negative probability being a product of a negative URL probability and a negative feature probability for each feature extracted from the given URL, the positive URL probability being a ratio of a number of URLs classified as positive in the training set to a total number of URLs in the training set, the negative URL probability being a ratio of a number of URLs classified as negative in the training set to the total number of URLs in the training set, the positive feature probability for each feature being a ratio of a number of URLs in the training set that are classified as positive that include the feature to the number of URLs classified as positive in the training set, and the negative feature probability for each feature being a number of URLs in the training set that are classified as negative that include the feature to the number of URLs classified as negative in the training set.

7. The method of claim 3, the generating a negative usefulness prediction value further comprising:

determining the negative usefulness prediction value to be a ratio of a negative probability to a sum of the negative probability and a positive probability, the positive probability being a product of a positive URL probability and a positive feature probability for each feature extracted from the given URL, the negative probability being a product of a negative URL probability and a negative feature probability for each feature extracted from the given URL, the positive URL probability being a ratio of a number of URLs classified as positive in the training set to a total number of URLs in the training set, the negative URL probability being a ratio of a number of URLs classified as negative in the training set to the total number of URLs in the training set, the positive feature probability for each feature being a ratio of a number of URLs in the training set that are classified as positive that include the feature to the number of URLs classified as positive in the training set, and the negative feature probability for each feature being a number of URLs in the training set that are classified as negative that include the feature to the number of URLs classified as negative in the training set.

8. The method of claim 3, the generating a positive usefulness prediction value further comprising:

determining the positive usefulness prediction value using a product, P, of a feature vector that identifies the features extracted from the given URL and a weighting vector that includes a weighting for each of the features extracted from the given URL to generate the positive usefulness prediction value using a formula;

1/(1+e<sup>−

P</sup>).

9. The method of claim 8, the weighting vector including an intercept weighting that corresponds to the count of the positive URLs in the training set.

10. The method of claim 3, the generating a negative usefulness prediction value further comprising:

determining the negative usefulness prediction value using a product, P, of a feature vector that identifies the features extracted from the given URL and a weighting vector that includes a weighting for each of the features extracted from the given URL to generate the negative usefulness prediction value using a formula;

1−

[1/(1+e<sup>−

P</sup>)].

11. The method of claim 10, the weighting vector including an intercept weighting that corresponds to the count of the positive URLs in the training set.

12. The method of claim 1, further comprising:

requesting the usefulness prediction in connection with a crawling operation prior to retrieving a resource associated with the given URL; and

determining whether or not to retrieve the resource associated with the given URL using the usefulness prediction generated in connection with the given URL.

13. The method of claim 1, the given URL being a part of a set of search results, the method further comprising:

requesting the usefulness prediction in connection with the given URL;

determining whether or not to remove the given URL from the set of search results using the usefulness prediction generated in connection with the given URL.

14. The method of claim 1, the given URL being a part of a set of URLs, the method further comprising:

requesting the usefulness prediction in connection with the given URL;

determining an order of the given URL in the set of URLs based on the usefulness prediction generated in connection with the given URL and usefulness predictions generated in connection with one or more other URLs in the set.

15. The method of claim 1, using the one or more features extracted from the given URL and the usefulness prediction model to generate the usefulness prediction in connection with the given URL further comprising:

using a decision tree to generate the usefulness prediction in connection with the given URL, the nodes of the decision tree being identified using the negative and positive URLs count and the negative and positive feature counts identified by the training set.

25. The computer-readable medium of claim 1S, the program code to configure the one or more processor to generate a negative usefulness prediction value further comprising program code to configure the one or more processors to:

determine the negative usefulness prediction value using a product, P, of a feature vector that identifies the features extracted from the given URL and a weighting vector that includes a weighting for each of the features extracted from the given URL to generate the negative usefulness prediction value using a formula;

1'"'"'1[1/(1+e<sup>−

P</sup>)].

26. The computer-readable medium of claim 25, the weighting vector including an intercept weighting that corresponds to the count of the positive URLs in the training set.

33. The system of claim 31, said search engine further comprising a search component and the given URL is a part of a set of search results generated by the search component, the search component configured to:

request the usefulness prediction in connection with the given URL;

determine whether or not to remove the given URL from the set of search results using the usefulness prediction requested in connection with the given URL.

16. A computer-readable medium storing computer-executable program code comprising code to configure at least one processor to:

train a usefulness prediction model to generate a usefulness prediction in connection with a given universal resource locator (URL), the training of the usefulness prediction model being based on a training set of URLs, a count of negative URLs and a count of positive URLs identified by the training sets and for each feature extracted from the URLs in the training set, a count of the positive URLs in the training set that include the feature and a count of the negative URLs in the training set that include the feature;

extract one or more features of the given URL; and

use the one or more features extracted from the given URL and the usefulness prediction model to generate the usefulness prediction in connection with the given URL.

17. The computer-readable medium of claim 16, further comprising program code to configure the at least one processor to:

determine a usefulness of a resource associated with the given URL based on the usefulness prediction for the given URL.

18. The computer-readable medium of claim 16, the program code to configure the one or more processors to use the one or more features extracted from the given URL and the usefulness prediction model to generate the usefulness prediction in connection with the given URL further comprising program code to cause the one or more processors to:

generate a positive usefulness prediction value in connection with the given URL using the one or more features extracted from the given URL and the usefulness prediction model;

generate a negative usefulness prediction value in connection with the given URL using the one or more features extracted from the given URL and the usefulness prediction model; and

compare the positive usefulness prediction value with the negative usefulness prediction value to generate the usefulness prediction in connection with the given URL.

19. The computer-readable medium of claim 18, further comprising program code to configure the one or more processors to:

identify a resource associated with the given URL as useful in a case that the positive usefulness prediction value is equal to or greater than the negative usefulness prediction value.

20. The computer-readable medium of claim 18, further comprising program code to configure the one or more processors to:

identify a resource associated with the given URL as not useful in a case that the positive usefulness prediction value is less than the negative usefulness prediction value.

21. The computer readable medium of claim 18, the program code to configure the one or more processors to generate a positive usefulness prediction value further comprising program code to configure the one or more processors to:

determine the positive usefulness prediction value to be a ratio of a positive probability to a sum of the positive probability and a negative probability, the positive probability being a product of a positive URL probability and a positive feature probability for each feature extracted from the given URL, the negative probability being a product of a negative URL probability and a negative feature probability for each feature extracted from the given URL, the positive URL probability being a ratio of a number of URLs classified as positive in the training set to a total number of URLs in the training set, the negative URL probability being a ratio of a number of URLs classified as negative in the training set to the total number of URLs in the training set, the positive feature probability for each feature being a ratio of a number of URLs in the training set that are classified as positive that include the feature to the number of URLs classified as positive in the training set, and the negative feature probability for each feature being a number of URLs in the training set that are classified as negative that include the feature to the number of URLs classified as negative in the training set.

22. The computer-readable medium of claim 18, the program code to configure the one or more processors to generate a negative usefulness prediction value further comprising program code to configure the one or more processors to:

determine the negative usefulness prediction value to be a ratio of a negative probability to a sum of the negative probability and a positive probability, the positive probability being a product of a positive URL probability and a positive feature probability for each feature extracted from the given URL, the negative probability being a product of a negative URL probability and a negative feature probability for each feature extracted from the given URL, the positive URL probability being a ratio of a number of URLs classified as positive in the training set to a total number of URLs in the training set, the negative URL probability being a ratio of a number of URLs classified as negative in the training set to the total number of URLs in the training set, the positive feature probability for each feature being a ratio of a number of URLs in the training set that are classified as positive that include the feature to the number of URLs classified as positive in the training set, and the negative feature probability for each feature being a number of URLs in the training set that are classified as negative that include the feature to the number of URLs classified as negative in the training set.

23. The computer-readable medium of claim 18, the program code to configure one or more processors to generate a positive usefulness prediction value further comprising program code to configure the one or more processors to:

determine the positive usefulness prediction value using a product, P, of a feature vector that identifies the features extracted from the given URL and a weighting vector that includes a weighting for each of the features extracted from the given URL to generate the positive usefulness prediction value using a formula;

1/(1+e<sup>−

P</sup>).

24. The computer-readable medium of claim 23, the weighting vector including an intercept weighting that corresponds to the count of the positive URLs in the training set.

27. The computer-readable medium of claim 16, further comprising computer code to configure the one or more processors to:

request the usefulness prediction in connection with a crawling operation prior to retrieving a resource associated with the given URL; and

determine whether or not to retrieve the resource associated with the given URL using the usefulness prediction generated in connection with the given URL.

28. The computer-readable medium of claim 16, the given URL being a part of a set of search results, the program code further comprising program code to configure the one or more processors to:

request the usefulness prediction in connection with the given URL;

determine whether or not to remove the given URL from the set of search results using the usefulness prediction generated in connection with the given URL.

29. The computer-readable of claim 16, the given URL being a part of a set of URLs, the program code further comprising program code to configure the one or more processors to:

request the usefulness prediction in connection with the given URL;

determine an order of the given URL in the set of URLs based on the usefulness prediction generated in connection with the given URL and usefulness predictions generated in connection with one or more other URLs in the set.

30. The computer-readable medium of claim 16, the program code to configure the one or more processors to use the one or more features extracted from the given URL and the usefulness prediction model to generate the usefulness prediction in connection with the given URL further comprising program code to configure the one or more processors to:

use a decision tree to generate the usefulness prediction in connection with the given URL, the nodes of the decision tree being identified using the negative and positive URLs count and the negative and positive feature counts identified by the training set.

31. A system comprising:

a search engine configured to use a usefulness prediction generated from a given universal resource locator (URL) as a part of an operation performed by the search engine involving the given URL;

a usefulness predictor configured to generate a usefulness predictor configured to generate the usefulness prediction from the given URL using a usefulness model by;

obtaining a positive usefulness prediction value in connection with the given URL using the one or more features extracted from the given URL and the usefulness prediction model;

obtaining a negative usefulness prediction value in connection with the given URL using the one or more features extracted from the given URL and the usefulness prediction model; and

comparing the positive usefulness prediction value with the negative usefulness prediction value to generate the usefulness prediction in connection with the given URL.

32. The system of claim 31, said search engine further comprising a crawler component, said crawler component configured to:

request the usefulness prediction in connection with a crawling operation prior to retrieving a resource associated with the given URL; and

determine whether or not to retrieve the resource associated with the given URL using the usefulness prediction requested in connection with the given URL.

34. The system of claim 31, said search engine further comprising a ranking component and the given URL is a part of a set of URLs to be ranked, the ranking component configured to:

request the usefulness prediction in connection with the given URL;

determine an order of the given URL in the set of URLs based on the usefulness prediction generated in connection with the given URL and usefulness predictions requested in connection with one more other URLs in the set.