System and method for determining web page quality using collective inference based on local and global information

• US 7,809,705 B2
• Filed: 02/13/2007
• Issued: 10/05/2010
• Est. Priority Date: 02/13/2007
• Status: Expired due to Fees

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Zhang, Tong, Dom, Byron Edward, Popescul, Alexandrin
• Primary Examiner(s): Lu; Kuen S
• Assistant Examiner(s): PHAM, TUAN A
• Application Number:
  US11/706,025
• Publication Number:
  US 20080195631A1
• Time in Patent Office: 1,330 Days
• Field of Search: 707/10
• US Class Current: 707/706
• CPC Class Codes: G06F 16/954 Navigation, e.g. using categorised browsing

Abstract

An improved system and method is provided for determining web page quality using collective inference based on local and global web page information. A classification engine may be provided for classifying a web page using local features of a seed set of web pages and global web graph information about the seed set of web pages. A dual algorithm based on graph regularization formulated as a well-formed optimization solution may be used in an embodiment for applying collective inference for binary classification of the web page using the local web page information and global web graph information of a web page, the local web page information and global web graph information of an authoritative set of web pages, and the local web page information and global web graph information of a non-authoritative set of web pages.

Claims

1. A computer system for classifying a web page, comprising:

one or more processors to execute instructions;

a classification engine for determining a quality of the web page using local features of a seed set of web pages and global web graph information about the seed set of web pages, wherein;

each web page of the seed set of web pages is a web page of a known quality, the local features of the seed set of web pages comprises text, clicking, domain, or time stamp information concerning the seed set of web pages, and

the global web graph information about the seed set of web pages comprises hyperlink or co-citation relationships among the seed set of web pages;

a binary classifier coupled to the classification engine for performing binary classification to provide a binary score for the web page; and

a collective inference engine coupled to the binary classifier for performing collective inference by applying collective inference for binary classification using the local features of the seed set of web pages and the global web graph information about the seed set of web pages, comprising finding a minimum value of a regularized convex dual of a logistic regression loss function for a node of a graph.

2. The system of claim 1 further comprising a storage coupled to the classification engine for storing the local features of the seed set of web pages and the global web graph information about the seed set of web pages.

3. The system of claim 2 wherein the storage is for further storing local web page information of a second seed set of web pages and global web graph information about the second seed set of web pages.

4. A computer-readable non-transitory storage medium having computer-executable components comprising the system of claim 1.

5. A computer-implemented method for classifying a web page, comprising:

accessing, by one or more computing devices,

local web page information of and global web graph information about a plurality of authoritative web pages,

local web page information of and global web graph information about a plurality of non-authoritative web pages, and

local web page information of and global web graph information about the web page,

wherein;

each authoritative web page of the plurality of authoritative web pages is a web page of known high quality,

each non-authoritative web page of the plurality of non-authoritative web pages is a web page of known low quality,

the local web page information of the web pages comprises text, clicking, domain, or time stamp information concerning the web pages, and

the global web graph information about the web pages comprises hyperlink or co-citation relationships among the web pages;

determining, by the one or more computing devices, a quality of the web page using collective inference by applying collective inference for binary classification of the web page using the local web page information of the web page and the global web graph information about the web page, the local web page information of the plurality of authoritative web pages and the global web graph information about the plurality of authoritative web pages, and the local web page information of the plurality of non-authoritative web pages and the global web graph information about the plurality of non-authoritative web pages, comprising finding a minimum value of a regularized convex dual of a logistic regression loss function for a node of a graph; and

outputting, by the one or more computing devices, an indication of the quality of the web page.

6. The method of claim 5 further comprising receiving the local web page information of and the global web graph information about the plurality of the authoritative web pages.

7. The method of claim 5 further comprising receiving the local web page information of and the global web graph information about the plurality of the non-authoritative web pages.

8. The method of claim 5 further comprising obtaining the local web page information of the web page.

9. The method of claim 5 further comprising obtaining the global web graph information about the web page.

10. The method of claim 5 wherein outputting the indication of the quality of the web page comprises outputting an indication of the binary classification of the web page.

11. The method of claim 5 wherein applying collective inference for binary classification of the web page using the local web page information of the web page and the global web graph information about the web page, the local web page information of the plurality of authoritative web pages and global web graph information about the plurality of authoritative web pages, and the local web page information of the plurality of non-authoritative web pages and global web graph information about the plurality of non-authoritative web pages further comprises incrementing a value of a dual variable for the node of the graph by the minimum value of the regularized convex dual of the logistic regression loss function for the node of the graph.

12. A computer-readable non-transitory storage medium having computer-executable instructions for performing the method of claim 5.

13. A computer-implemented method for classifying a web page, comprising:

accessing, by one or more computing devices,

local web page information of and global web graph information about a plurality of authoritative web pages,

local web page information of and global web graph information about a plurality of non-authoritative web pages, and

local web page information of and global web graph information about the web page,

wherein;

each authoritative web page of the plurality of authoritative web pages is a web page of known high quality,

each non-authoritative web page of the plurality of non-authoritative web pages is a web page of known low quality,

the local web page information of the web pages comprises text, clicking, domain, or time stamp information concerning the web pages, and

the global web graph information about the web pages comprises hyperlink or co-citation relationships among the web pages;

determining, by the one or more computing devices, a quality of the web page using collective inference by applying collective inference for binary classification of the web page using the local web page information of the web page and the global web graph information about the web page, the local web page information of the plurality of authoritative web pages and global web graph information about the plurality of authoritative web pages, and the local web page information of the plurality of non-authoritative web pages and global web graph information about the plurality of non-authoritative web pages, comprising finding a minimum value of a regularization function associated with an edge of a graph; and

outputting, by the one or more computing devices, an indication of the quality of the web page.

14. The method of claim 13 wherein applying collective inference for binary classification of the web page using the local web page information of the web page and the global web graph information about the web page, the local web page information of the plurality of authoritative web pages and global web graph information about the plurality of authoritative web pages, and the local web page information of the plurality of non-authoritative web pages and global web graph information about the plurality of non-authoritative web pages further comprises incrementing a value of a dual variable for the edge of the graph by the minimum value of the regularization function associated with the edge of the graph.

15. A computer system for classifying a web page, comprising:

means for accessing

local web page information of and global web graph information about a plurality of first web pages,

local web page information of and global web graph information about the web page,

wherein;

each first web page of the plurality of first web pages is a web page of known first quality,

the local web page information of the web pages comprises text, clicking, domain, or time stamp information concerning the web pages, and

the global web graph information about the web pages comprises hyperlink or co-citation relationships among the web pages;

means for determining a quality of the web page using collective inference by applying collective inference for binary classification of the web page using the local web page information of the web page and the global web graph information about the web page and the local web page information of the plurality of first web pages and the global web graph information about the plurality of first web pages, comprising;

means for finding a minimum value of a regularized convex dual of a logistic regression loss function for a node of a graph; and

means for outputting an indication of the classification of the web page.

16. The computer system of claim 15 further comprising:

means for accessing local web page information of and global web graph information about a plurality of second web pages, wherein each second web page of the plurality of second web pages is a web page of known second quality;

wherein determining the quality of the web page using collective inference is further based on the local web page information of the plurality of second web pages and the global web graph information about the plurality of second web pages.

17. The computer system of claim 16 further comprising:

means for receiving the local web page information of and the global web graph information about the plurality of first web pages; and

means for receiving the local web page information of and the global web graph information about the plurality of second web pages.

18. A method comprising:

accessing, by one or more computing devices,

local web page information of and global web graph information about a plurality of first web pages,

local web page information of and global web graph information about a plurality of second web pages, and

local web page information of and global web graph information about a third web page,

wherein;

each first web page of the plurality of first web pages is of a known first quality;

each second web page of the plurality of second web pages is of a known second quality;

the local web page information of the web pages comprises text contained in the web pages, and

the global web graph information about the web pages comprises hyperlink relationships among the web pages;

determining, by the one or more computing devices, a quality of the third web page using collective inference by applying collective inference for binary classification of the third web page using the local web page information of and the global web graph information about the plurality of first web pages, the local web page information of and the global web graph information about the plurality of second web pages, and the local web page information of and the global web graph information about the third web page, wherein;

the collective inference is used to infer a quality score for the third web page; and

applying collective inference for binary classification of the third web page comprises;

computing at least one linear weight using a regularized linear prediction model based on the at least one dimensional vector of words;

determining a graph regularization condition for the graph;

deriving a regularization parameter from the graph regularization condition; and

estimating the quality of the third web page based on the at least one linear weight and the regularization parameter; and

outputting, by the one or more computing devices, an indication of the quality of the third web page.

19. The method recited in claim 18, wherein:

each first web page of the plurality of first web pages is of a known high quality;

each second web page of the plurality of second web pages is of a known low quality;

each first web page of the plurality of first web pages and the third web page are directly or indirectly linked via at least one first hyperlinks; and

each second web page of the plurality of second web pages and the third web page are directly or indirectly linked via at least one second hyperlinks.

20. The method recited in claim 19, further comprising:

representing the text of the local web page information of the plurality of first web pages, the plurality of second web pages, and the third web page using at least one dimensional vector of words; and

representing the hyperlink relationships of the global web graph information about the plurality of first web pages, the plurality of second web pages, and the third web page using a graph that comprises a plurality of nodes and a plurality of edges, wherein each node of the graph represents one of the web pages, and each edge of the graph connects two of the nodes where the corresponding two web pages are linked.

21. The method recited in claim 20, wherein determining the quality of the third web page using collective inference comprises applying a dual algorithm for binary classification of the third web page based on the local web page information of and the global web graph information about the plurality of first web pages, the local web page information of and the global web graph information about the plurality of second web pages, and the local web page information of and the global web graph information about the third web page.

22. The method recited in claim 21, wherein applying the dual algorithm for binary classification of the third web page comprises:

initializing a primal weight vector, a plurality of node variables corresponding to the plurality of nodes of the graph, and a plurality of edge variables corresponding to the plurality of edges of the graph; and

iteratively updating the primal weight vector, the plurality of node variables, and the plurality of edge variables.

23. The method recited in claim 22, wherein:

updating the node variable of a node of the graph during an iteration comprises;

determining a first minimum value of a regularized convex dual of a logistic regression loss function for the node based on a current value of the primal weight vector; and

incrementing a current value of the node variable by the first minimum value; and

updating the edge variable of an edge of the graph during an iteration comprises;

determining a second minimum value of a regularization function associated with the edge; and

incrementing a current value of the edge variable by the second minimum value.

24. The method recited in claim 18, wherein:

the local web page information of the web pages further comprises clicking, domain, and time-stamp information; and

the global web graph information about the web pages further comprises co-citation relationships among the web pages.