Hierarchical conditional random fields for web extraction

• US 7,720,830 B2
• Filed: 07/31/2006
• Issued: 05/18/2010
• Est. Priority Date: 07/31/2006
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ma, Wei-Ying, Nie, Zaiqing, Zhu, Jun, Wen, Ji-Rong
• Primary Examiner(s): Jalil; Neveen Abel
• Assistant Examiner(s): MINCEY, JERMAINE A
• Application Number:
  US11/461,400
• Publication Number:
  US 20080027969A1
• Time in Patent Office: 1,387 Days
• Field of Search: 707/102
• US Class Current: 707/705
• CPC Class Codes: G06F 16/904 Browsing; Visualisation therefor for navigating the web G06F16/954; browsing optimisation for the web G06F16/957
• CPC Class Codes: G06F 16/958 Organisation or management of web site content, e.g. publishing, maintaining pages or automatic linking

Abstract

A method and system for labeling object information of an information page is provided. A labeling system identifies an object record of an information page based on the labeling of object elements within an object record and labels object elements based on the identification of an object record that contains the object elements. To identify the records and label the elements, the labeling system generates a hierarchical representation of blocks of an information page. The labeling system identifies records and elements within the records by propagating probability-related information of record labels and element labels through the hierarchy of the blocks. The labeling system generates a feature vector for each block to represent the block and calculates a probability of a label for a block being correct based on a score derived from the feature vectors associated with related blocks. The labeling system searches for the labeling of records and elements that has the highest probability of being correct.

Claims

1. A method performed by a computing device with a processor and memory for labeling observations, the method comprising:

receiving observations having hierarchical relationships represented by a graph having vertices representing observations and edges representing relationships, a collection of related vertices being a clique, a clique being a subset of vertices of the graph in which each pair of distinct vertices in the subset is joined by an edge;

storing the received observations in the memory

determining by the computing device a labeling for the observations using a conditional random fields technique that factors in the hierarchical relationships, a conditional probability p of label y given observation x of the conditional random fields technique being represented as follows;

$p(y<br><br><br><br>x)=\frac{1}{Z<br><br>\left(x\right)}<br><br>\exp <br><br>\left(\begin{array}{c}\underset{v,k}{\overset{}{\sum <br><br>}}<br><br><br><br>{\mathrm{\mu <br><br>}}_k<br><br>{g_k(v,y<br><br>}_v,x)+\\ \underset{e,k}{\overset{}{\sum <br><br>}}<br><br><br><br>{\mathrm{\lambda <br><br>}}_k<br><br>{f_k(e,y<br><br>}_e,x)+\\ \underset{t,k}{\overset{}{\sum <br><br>}}<br><br><br><br>{\mathrm{\gamma <br><br>}}_k<br><br>{h_k(t,y<br><br>}_t,x)\end{array}\right)$

 

where v represents a vertex clique, e represents an edge clique, and t represents a triangle clique, y|_v, y|_e, and y|_t represent components of label y, Z is a normalization factor, g_k, f_k, and h_k represent feature functions, and μ

_k, λ

_k, and γ

_k represent weights of the feature functions; and

storing by the computing device the labeling for the observations.

2. The method of claim 1 wherein the observations are represented as a tree of observation vertices and the determining includes identifying a hierarchy of cliques of observation vertices within the tree and calculating a probability for sets of labels based on probabilities derived from features of components of the cliques that contain the observation vertices.

3. The method of claim 2 wherein the components of a clique include the edges and vertices of the clique.

4. The method of claim 2 wherein the calculating of the probability for a set of labels includes generating a junction tree of the cliques and propagating a belief to the cliques of the junction tree.

5. The method of claim 4 wherein the beliefs are propagated using a collection phase and a distribution phase.

6. The method of claim 1 including deriving weights for feature functions based on training data and wherein the determining includes calculating a probability for a set of labels based on the training data.

7. The method of claim 6 wherein the deriving includes optimizing a log-likelihood function based on the training data.

8. The method of claim 6 wherein the optimizing uses a gradient-based L-BFGS technique.

9. The method of claim 1 wherein the determining of the labeling includes propagating probability-related calculations from observation to observation.

10. A computer-readable storage medium containing instructions for controlling a computer system to identify object records and object elements of a web page, by a method comprising:

providing a hierarchical representation of blocks of the web page, each block representing an object record or an object element, the blocks represented by observations having hierarchical relationships represented by a graph having vertices representing observations and edges representing relationships, a collection of related vertices being a clique, a clique being a subset of vertices of the graph in which each pair of distinct vertices in the subset is joined by an edge; and

applying a hierarchical conditional random fields technique to jointly identify a set of record labels and element labels for the blocks based on the hierarchical relationship of the blocks of the web page, the applying including identifying the labels uses a conditional random fields technique that factors in the hierarchical relationships, a conditional probability p of label y given observation x of the conditional random fields technique being represented as follows;

$p(y<br><br><br><br>x)=\frac{1}{Z<br><br>\left(x\right)}<br><br>\exp <br><br>\left(\begin{array}{c}\underset{v,k}{\overset{}{\sum <br><br>}}<br><br><br><br>{\mathrm{\mu <br><br>}}_k<br><br>{g_k(v,y<br><br>}_v,x)+\\ \underset{e,k}{\overset{}{\sum <br><br>}}<br><br><br><br>{\mathrm{\lambda <br><br>}}_k<br><br>{f_k(e,y<br><br>}_e,x)+\\ \underset{t,k}{\overset{}{\sum <br><br>}}<br><br><br><br>{\mathrm{\gamma <br><br>}}_k<br><br>{h_k(t,y<br><br>}_t,x)\end{array}\right)$

 

where v represents a vertex clique, e represents an edge clique, and t represents a triangle clique, y|_v, y|_e, and y|_t represent components of label y, Z is a normalization factor, g_k, f_k, and h_k represent feature functions, and μ

_k, λ

_k, and γ

_k represent weights of the feature functions.

11. The computer-readable storage medium of claim 10 wherein the blocks are represented as a tree of blocks and the applying of a hierarchical conditional random fields technique includes identifying a hierarchy of cliques of blocks within the tree and calculating a probability for sets of labels based on probabilities derived from features of components of the cliques that contain the blocks.

12. The computer-readable storage medium of claim 10 including deriving weights for feature functions based on training data of object records, object elements, and labels and wherein the applying calculates a probability for a set of labels based on the derived weights.

13. The computer-readable storage medium of claim 12 wherein the applying uses a gradient-based L-BFGS technique.