Hierarchical conditional random fields for web extraction

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.

1 - 20 . (canceled) 
     
     
         21 . 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 of a label for a given observation being based on feature functions for a vertex clique, an edge clique, and a triangle clique for the label; and   storing by the computing device the labeling for the observations.   
     
     
         22 . The method of  claim 21  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. 
     
     
         23 . The method of  claim 22  wherein the components of a clique include the edges and vertices of the clique. 
     
     
         24 . The method of  claim 22  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. 
     
     
         25 . The method of  claim 24  wherein the beliefs are propagated using a collection phase and a distribution phase. 
     
     
         26 . The method of  claim 21  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. 
     
     
         27 . The method of  claim 26  wherein the deriving includes optimizing a log-likelihood function based on the training data. 
     
     
         28 . The method of  claim 26  wherein the optimizing uses a gradient-based L-BFGS technique. 
     
     
         29 . The method of  claim 21  wherein the determining of the labeling includes propagating probability-related calculations from observation to observation. 
     
     
         30 . A computer-readable storage medium containing instructions for controlling a computing device to identify object records and object elements of a web page, by a method comprising:
 receiving 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 of a label for a given observation being based on feature functions for a vertex clique, an edge clique, and a triangle clique for the label.   
     
     
         31 . The computer-readable storage medium of  claim 30  wherein the observations are represented as a tree of observation vertices and the identifying 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. 
     
     
         32 . The computer-readable storage medium of  claim 31  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. 
     
     
         33 . The computer-readable storage medium of  claim 32  wherein the beliefs are propagated using a collection phase and a distribution phase. 
     
     
         34 . The computer-readable storage medium of  claim 30  including deriving weights for feature functions based on training data and wherein the identifying includes calculating a probability for a set of labels based on the training data. 
     
     
         35 . The computer-readable storage medium of  claim 30  wherein the identifying of the labeling includes propagating probability-related calculations from observation to observation. 
     
     
         36 . A computing device for labeling observations, comprising:
 a memory storing computer-executable instructions that:
 receive observations having hierarchical relationships represented by a graph having vertices representing observations and edges representing relationships, a collection of related vertices being a clique; 
 determine a labeling for the observations using a conditional random fields technique that factors in the hierarchical relationships, a conditional probability of a label for a given observation being based on feature functions for a vertex clique, an edge clique, and a triangle clique for the label; and 
   a processor for executing the computer-executable instructions stored in the memory.   
     
     
         37 . The computing device of  claim 36  wherein the observations are represented as a tree of observation vertices and the determination includes identification of a hierarchy of cliques of observation vertices within the tree and calculation of a probability for sets of labels based on probabilities derived from features of components of the cliques that contain the observation vertices. 
     
     
         38 . The computing device of  claim 37  wherein the components of a clique include the edges and vertices of the clique. 
     
     
         39 . The computing device of  claim 36  wherein a clique is a subset of vertices of the graph in which each pair of distinct vertices in the subset is joined by an edge. 
     
     
         40 . The computing device of  claim 36  including deriving weights for feature functions based on training data and wherein the determination includes calculation of a probability for a set of labels based on the training data.