Classification method of labeled ordered trees using support vector machines
First Claim
Patent Images
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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
23 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. - View Dependent Claims (2, 3, 4)
-
-
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. - View Dependent Claims (6)
-
-
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. - View Dependent Claims (8)
-
-
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. - View Dependent Claims (10)
-
-
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. - View Dependent Claims (12)
-
-
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. - View Dependent Claims (14, 15)
-
-
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. - View Dependent Claims (17)
-
-
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. - View Dependent Claims (19, 20, 21)
-
-
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.
-
Specification