Classification method of labeled ordered trees using support vector machines

• US 20030172352A1
• Filed: 03/10/2003
• Published: 09/11/2003
• Est. Priority Date: 03/08/2002
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Kashima, Hisashi, Koyanagi, Teruo
• Granted Patent: US 7,130,833 B2
• Time in Patent Office: Days
• US Class Current: 715/513
• CPC Class Codes: G06F 18/24323 Tree-organised classifiers

Abstract

To achieve classification of semistructured data with a Kernel method for labeled ordered trees, instances having a labeled ordered tree structure are input and their inner product is computed, the result of which is used for classification learning of the instances. In the inner product computation, a sum of matches is computed for descendant nodes of non-leaf nodes of the labeled ordered trees by applying dynamic programming based on correspondence in which order of the nodes is maintained.

Claims

1. A data processing method for controlling a computer to learn classification of instances having a structure, the method comprising:

a first step of inputting the instances to compute their inner product and storing the computation result in memory, the structure of the instances being vector-representable with its substructures as attributes; and

a second step of learning classification of the instances based on the computation result stored in the memory;

wherein the first step comprises, if the given substructures includes lower substructures, computing a sum of matches for the lower substructure.

2. The data processing method according to claim 1, wherein the first step comprises, if the given substructures includes lower substructures, computing a sum of complete matches for the lower substructure by applying dynamic programming based on information specific to the lower substructure.

3. The data processing method according to claim 1, wherein the first step comprises, if the given substructures includes lower substructures, computing a sum of matches for the lower substructure according to correspondence in which order in the lower substructures is maintained.

4. The data processing method according to claim 1, wherein the second step comprises inputting instances having a labeled ordered tree structure.

5. A data processing method for controlling a computer to indicate a desired node in a labeled ordered tree, the method comprising the steps of:

based on structures of positive instances and structures of negative instances stored in memory, obtaining a classification rule for classifying the positive instances and the negative instances and storing the rule in memory, each structure of the positive instances being the labeled ordered tree in which a node indication mark is added to a node to be indicated, and each structure of the negative instances being the labeled ordered tree in which a node indication mark is added to a node not to be indicated;

adding a node indication mark to a node in the labeled ordered tree to be processed and classify the labeled ordered tree as positive or negative based on the classification rule stored in the memory; and

in response to the classification result, outputting a processing result of the labeled ordered tree with the node indication mark added to a node.

6. The data processing method according to claim 5, wherein the step of obtaining the classification rule and storing it in the memory comprises the steps of:

inputting the labeled ordered trees to compute their inner product and storing the computation result in memory; and

obtaining the classification rule for the labeled ordered trees with the computation result stored in the memory.

7. A data processing method for controlling a computer to compute an inner product of labeled ordered trees, the method comprising:

a first step of matching leaf nodes of the labeled ordered trees and storing the result in memory;

a second step of matching non-leaf nodes of the labeled ordered trees by computing a sum of matches for descendant nodes of the non-leaf nodes and storing the result in memory; and

a third step of computing the inner product of the labeled ordered trees based on the matching results of the first and second steps stored in the memory.

8. The data processing method according to claim 7, wherein the second step comprises computing a sum of matches for the descendant nodes by applying dynamic programming according to correspondence in which order of the descendant nodes is maintained.

9. An information processing system for classifying data having a labeled ordered tree structure, the system comprising:

an instance storage unit that stores instances of the data classified as positive instances and negative instances based on the tree structure;

a processing unit that reads the instances from the instance storage unit to perform classification and classification learning of the instances with a Kernel method;

wherein the processing unit comprises an inner product computing unit that computes a sum of matches for descendant nodes of non-leaf nodes of the trees when computing an inner product of the instances.

10. The information processing system according to claim 9, wherein the inner product computing unit computes a sum of matches for the descendant nodes by applying dynamic programming according to correspondence in which order of the descendant nodes is maintained.

11. A program for controlling a computer to learn classification of instances having a structure, the program causing the computer to execute:

a first processing of inputting the instances to compute their inner product and storing the computation result in memory, the structure of the instances being vector-representable with its substructures as attributes; and

a second processing of learning classification of the instances based on the computation result stored in the memory;

wherein the first processing executed by the computer comprises, if the given substructures includes lower substructures, computing a sum of matches for the lower substructure.

12. The program according to claim 11, wherein the first processing executed by the computer comprises, if the given substructures includes lower substructures, computing a sum of complete matches for the lower substructures by applying dynamic programming based on order in the lower substructures according to correspondence in which the order is maintained.

13. A program for controlling a computer to learn classification of instances having a labeled ordered tree structure, the program causing the computer to execute:

a first processing of inputting the instances to compute their inner product and storing the computation result in memory; and

a second processing of learning classification of the instances based on the computation result stored in the memory;

wherein the first processing executed by the computer comprises, if a node in the tree is not a leaf node, computing a sum of matches for descendant nodes of the node.

14. The program according to claim 13, wherein the first processing executed by the computer comprises, when computing the sum of matches for the descendant nodes of the node, determining that the descendant nodes match even if their labels are different from corresponding nodes.

15. The program according to claim 13, wherein the first processing executed by the computer comprises determining that the descendant nodes match if relative positions between corresponding nodes are maintained.

16. A program for controlling a computer to indicate a desired node in a labeled ordered tree, the program causes the computer to execute the processing of:

based on structures of positive instances and structures of negative instances stored in memory, obtaining a classification rule for classifying the positive instances and the negative instances and storing the rule in memory, each structure of the positive instances being the labeled ordered tree in which a node indication mark is added to a node to be indicated, and each structure of the negative instances being the labeled ordered tree in which a node indication mark is added to a node not to be indicated;

adding a node indication mark to a node in the labeled ordered tree to be processed and classify the labeled ordered tree as positive or negative based on the classification rule stored in the memory; and

in response to the classification result, outputting as a processing result the labeled ordered tree with the node indication mark added to a node.

17. The program according to claim 16, wherein the processing of obtaining the classification rule executed by the computer comprises the processing of:

inputting the labeled ordered trees to compute their inner product and storing the computation result in memory; and

obtaining the classification rule for the labeled ordered trees with the computation result stored in the memory.

18. A program for controlling a computer to compute an inner product of labeled ordered trees, the program causes the computer to execute:

a first processing of matching leaf nodes of the labeled ordered trees and storing the result in memory;

a second processing of matching non-leaf nodes of the labeled ordered trees by computing a sum of matches for descendant nodes of the non-leaf nodes and storing the result in memory; and

a third processing of computing the inner product of the labeled ordered trees based on the matching results of the first and second steps stored in the memory.

19. The program according to claim 18, wherein the second processing executed by the computer comprises computing a sum of matches for the descendant nodes by applying dynamic programming according to correspondence in which order of the descendant nodes is maintained.

20. The program according to claim 18, wherein the second processing executed by the computer comprises, when computing the sum of matches for the descendant nodes of the node, determining that the descendant nodes match even if their labels are different from corresponding nodes.

21. The program according to claim 18, wherein the second processing executed by the computer comprises determining that the descendant nodes match if relative positions between corresponding nodes are maintained.

22. A computer-readable recording medium in which a program for controlling a computer to learn classification of instances having a structure is recorded, the program causing the computer to execute:

a first processing of inputting the instances to compute their inner product and storing the computation result in memory, the structure of the instances being vector-representable with its substructures as attributes; and

a second processing of learning classification of the instances based on the computation result stored in the memory;

wherein the first processing comprises, if the given substructures includes lower substructures, computing a sum of matches for the lower substructure.

23. A computer-readable recording medium in which a program for controlling a computer to indicate a desired node in a labeled ordered tree is recorded, the program causing the computer to execute:

based on structures of positive instances and structures of negative instances stored in memory, obtaining a classification rule for classifying the positive instances and the negative instances and storing the rule in memory, each structure of the positive instances being the labeled ordered tree in which a node indication mark is added to a node to be indicated, and each structure of the negative instances being the labeled ordered tree in which a node indication mark is added to a node not to be indicated;

adding a node indication mark to a node in the labeled ordered tree to be processed and classify the labeled ordered tree as positive or negative based on the classification rule stored in the memory; and

in response to the classification result, outputting as a processing result the labeled ordered tree with the node indication mark added to a node.