Parsing hierarchical lists and outlines

Abstract

A system and method for determining hierarchical information is described. Aspects include using the Collins model for parsing non-textual information into hierarchical content. The system and process assign labels to lines that indicate how the lines relate to one another.

1 . A process for recognizing hierarchical content of received non-textual information comprising the steps of: 
 receiving non-textual information;    determining raw features information;    determining additional features from the raw features information; and    computing a label for each line in said received information.    
   
   
       2 . The process according to  claim 1 , wherein said determining additional features step further includes the step of: 
 determining primary line features.    
   
   
       3 . The process according to  claim 1 , further including the step of: 
 preprocessing the received information.    
   
   
       4 . The process according to  claim 1 , wherein said preprocessing step further includes the step of: 
 rotating the received information.    
   
   
       5 . The process of  claim 1 , wherein said computing step includes application of a Collins model.  
   
   
       6 . The process of  claim 1 , wherein said computing step includes application of a Collins model having been trained with training data.  
   
   
       7 . A process for determining a hierarchical structure of non-textual information comprising the steps of: 
 receiving non-textual information;    processing lines of non-textual information as an observation sequence s t ;    processing the observation sequence s t  to find a sequence of labels l t  such that a cost of the label sequence is:              C   ⁡     (     L   ,   s     )       =       ∑   t     ⁢           ⁢       ∑   i     ⁢           ⁢       λ   i     ⁢       f   i     ⁡     (       l   t     ,     l     t   -   1       ,   s   ,   t     )                     where L is a sequence of labels in time, s is the sequence of observations, t is the position in the seqeuence, and {l t } and λ i  are model parameters.    
   
   
       8 . The process according to  claim 7 , wherein the model parameters are determined by adjusting the model parameters to converge with labels in training examples.  
   
   
       9 . The process according to  claim 7 , further including the step of: 
 determining model parameters using training examples {L k , s k } by finding a set of weights {λ i } such that        {circumflex over (L)}   k =arg L min  C ( L,s   k )= L   k .    
   
   
       10 . The process according to  claim 7 , wherein each line is determined to include a number of features and where the features are used to assign a label to the line.  
   
   
       11 . The process according to  claim 10 , further comprising the step of: 
 estimating an indent level for each line, said indent level being a feature.    
   
   
       12 . The process according to  claim 10 , further comprising the step of: 
 determining if a bullet is present in a line, the existence of said bullet being a feature.    
   
   
       13 . A system for recognizing hierarchical content of received non-textual information comprising: 
 means for receiving non-textual information;    means for determining raw features information;    means for determining additional features from the raw features information; and    means for computing a label for each line in said received information.    
   
   
       14 . The system according to  claim 13 , wherein said means for determining additional features further comprises: 
 means for determining primary line features.    
   
   
       15 . The system according to  claim 13 , further comprising: 
 means for preprocessing the received information.    
   
   
       16 . The system according to  claim 13 , wherein said means for preprocessing further comprises: 
 means for rotating the received information.    
   
   
       17 . The system of  claim 13 , wherein said means for computing includes application of a Collins model.  
   
   
       18 . The system of  claim 13 , wherein said means for computing includes application of a Collins model having been trained with training data.  
   
   
       19 . A system for determining a hierarchical structure of non-textual information comprising: 
 means for receiving non-textual information;    means for processing lines of non-textual information as an observation sequence s t ;    means for processing the observation sequence s t  to find a sequence of labels l t  such that a cost of the label sequence is:              C   ⁡     (     L   ,   s     )       =       ∑   t     ⁢           ⁢       ∑   i     ⁢           ⁢       λ   i     ⁢         f   i     ⁡     (       l   t     ,     l     t   -   1       ,   s   ,   t     )       .                   where L is a sequence of labels in time, s is the sequence of observations, t is the position in the sequence, and {l t } and λ i  are model parameters.    
   
   
       20 . The system according to  claim 19 , wherein the model parameters are determined by adjusting the model parameters to converge with labels in training examples.  
   
   
       21 . The system according to  claim 19 , further comprising: 
 means for determining model parameters using training examples {L k , s k } by finding a set of weights {λ i } such that        {circumflex over (L)}   k =arg L min  C ( L,s   k )= L   k .    
   
   
       22 . A system for parsing non-textual information into hierarchical form comprising: 
 an input that receives non-textual information;    a processor that uses conditional random fields to apply labels to lines of said non-textual information;    an output that outputs labels associated with lines of said non-textual information where said labels describe the hierarchical form of said non-textual information.    
   
   
       23 . The system according to  claim 22 , wherein the conditional random fields used to determine the labels is:  
     
       
         
           
             
               C 
               ⁡ 
               
                 ( 
                 
                   L 
                   , 
                   s 
                 
                 ) 
               
             
             = 
             
               
                 ∑ 
                 t 
               
               ⁢ 
               
                   
               
               ⁢ 
               
                 
                   ∑ 
                   i 
                 
                 ⁢ 
                 
                     
                 
                 ⁢ 
                 
                   
                     λ 
                     i 
                   
                   ⁢ 
                   
                     
                       
                         f 
                         i 
                       
                       ⁡ 
                       
                         ( 
                         
                           
                             l 
                             t 
                           
                           , 
                           
                             l 
                             
                               t 
                               - 
                               1 
                             
                           
                           , 
                           s 
                           , 
                           t 
                         
                         ) 
                       
                     
                     . 
                   
                 
               
             
           
         
       
       where L is a sequence of labels in time, s is the sequence of observations, t is the position in the sequence, and {l t } and λ i  are model parameters.  
     
   
   
       24 . The system according to  claim 23 , wherein the processor uses model parameters that have been determined by model parameters using training examples {L k , s k } by finding a set of weights {λ i } such that  
         {circumflex over (L)}   k =arg L min  C ( L,s   k )= L   k .  
   
   
       25 . A computer-readable medium having a program stored thereon, said program for recognizing hierarchical content of received non-textual information, said program comprising the steps of: 
 receiving non-textual information;    determining raw features information;    determining additional features from the raw features information; and    computing a label for each line in said received information.    
   
   
       26 . The computer-readable medium according to  claim 25 , wherein said determining additional features step further includes the step of: 
 determining primary line features.    
   
   
       27 . The computer-readable medium according to  claim 25 , wherein said program further includes the step of: 
 preprocessing the received information.    
   
   
       28 . The computer-readable medium according to  claim 25 , wherein said preprocessing step further includes the step of: 
 rotating the received information.    
   
   
       29 . The computer-readable medium of  claim 25 , wherein said computing step includes application of a Collins model.  
   
   
       30 . The computer-readable medium of  claim 25 , wherein said computing step includes application of a Collins model having been trained with training data.  
   
   
       31 . A computer-readable medium having a program stored thereon, said program for determining a hierarchical structure of non-textual information, said program comprising the steps of: 
 receiving non-textual information;    processing lines of non-textual information as an observation sequence s t ;    processing the observation sequence s t  to find a sequence of labels l t  such that a cost of the label sequence is:              C   ⁡     (     L   ,   s     )       =       ∑   t     ⁢           ⁢       ∑   i     ⁢           ⁢       λ   i     ⁢       f   i     ⁡     (       l   t     ,     l     t   -   1       ,   s   ,   t     )                     where L is a sequence of labels in time, s is the sequence of observations, t is the position in the sequence, and {l t } and λ i  are model parameters.    
   
   
       32 . The computer-readable medium according to  claim 31 , wherein the model parameters are determined by adjusting the model parameters to converge with labels in training examples.  
   
   
       33 . The computer-readable medium according to  claim 31 , said program further comprising the step of: 
 determining model parameters using training examples {L k , s k } by finding a set of weights {λ i } such that        {circumflex over (L)}   k =arg L min  C ( L,s   k )= L   k .    
   
   
       34 . The computer-readable medium according to  claim 31 , wherein each line is determined to include a number of features and where the features are used to assign a label to the line.  
   
   
       35 . The computer-readable medium according to  claim 34 , said program further comprising the step of: 
 estimating an indent level for each line, said indent level being a feature.    
   
   
       36 . The computer-readable medium according to  claim 34 , wherein said program further comprises the step of: 
 determining if a bullet is present in a line, the existence of said bullet being a feature.    
   
   
       37 - 72 . (canceled)