Classification method of labeled ordered trees using support vector machines
AssigneeInternational Business Machines Corporation
InventorsHisashi Kashima, Teruo Koyanagi
Life of this patent
Estimating the term…
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.
Claims23
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
Dependencies are inferred from the claim text.