HIERARCHICAL CONDITIONAL RANDOM FIELDS FOR WEB EXTRACTION

• US 20080027969A1
• Filed: 07/31/2006
• Published: 01/31/2008
• Est. Priority Date: 07/31/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ma, Wei-Ying, Nie, Zaiqing, Zhu, Jun, Wen, Ji-Rong
• Granted Patent: US 7,720,830 B2
• Time in Patent Office: Days
• US Class Current: 707/102
• 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 for labeling observations, the method comprising:

receiving observations having hierarchical relationships; and

determining a labeling for the observations using a conditional random fields technique that factors in the hierarchical relationships.

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 system for identifying object records and object elements of a page, comprising:

a component that identifies blocks of the page; and

a component that labels object records and object elements based on a probability of a label for a block being correct that is based on probabilities of labels for blocks within the block being correct.

11. The system of claim 10 wherein the blocks are represented as a tree of blocks and the component that labels identifies a hierarchy of cliques of blocks within the tree and calculates a probability for sets of labels based on probabilities derived from features of components of the cliques that contain the blocks.

12. The system of claim 11 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.

13. The system of claim 10 including a component that derives weights for feature functions based on training data and wherein the component that labels calculates a probability for a set of labels based on the training data.

14. The system of claim 13 wherein the component that derives the weights optimizes a log-likelihood function based on the training data.

15. The system of claim 13 wherein the component that derives the weights uses a gradient-based L-BFGS technique.

16. The system of claim 10 wherein the component that labels propagates probability-related calculations from block to block.

17. A computer-readable 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; 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.

18. The computer-readable medium of claim 17 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.

19. The computer-readable medium of claim 17 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.

20. The computer-readable medium of claim 19 wherein the applying uses a gradient-based L-BFGS technique.