Method for producing a binary tree, pattern recognition and binary vector classification method using binary trees, and system for classifying binary vectors
First Claim
1. In a method for producing a binary tree for pattern recognition use, or the like, steps comprisinga) obtaining a set of binary training pattern vectors some of which are associated with a first pattern and the remainder of which are not associated with said first pattern, those training pattern vectors associated with the first pattern being identified as category 1 training pattern vectors and the remainder of the training pattern vectors which are not associated with said first pattern being identified as category 0 training pattern vectors, each said binary training pattern vector including the same number, N, of vector elements, andb) using the set of binary training pattern vectors as inputs to a computer, generating a binary tree having at least N levels and storing the tree in computer memory, which binary tree comprises a sequence of binary two-bit doublets each of which doublets comprises a tree node of one of four types including "no branch", "branch only left", "branch only right" and "branch both left and right" node.
1 Assignment
0 Petitions
Accused Products
Abstract
A binary tree and method of producing a binary tree are shown, together with artificial neural networks which include processing units of binary trees. The binary tree-producing method includes obtaining a set of binary training pattern vectors some of which are associated with a first pattern to be recognized, and the remainder of which are not associated with the first pattern. Those associated with the first pattern and the remainder are identified as category 1 and category 0 vectors, respectively. The set of vectors is used to generate a binary tree in computer memory, which tree includes a sequence of binary doublets each of which represents a tree node. One of four branch conditions is identified by each doublet including no branches, branch only left, branch only right or branch both left and right. The sequence of binary doublets is used to classify binary vectors. A hardware version of the tree may be implemented which includes a plurality of AND gates (1L, 1R, 2L, 2R, 3L and 5L) interconnected in an N-level binary tree (FIG. 3) to which N binary inputs (X1, X2 and X3) are connected to separate levels of the tree. Leaf nodes of the AND gate binary tree are connected to an OR gate (20), and a start signal (S) is supplied to the root node (1) of the tree.
45 Citations
28 Claims
-
1. In a method for producing a binary tree for pattern recognition use, or the like, steps comprising
a) obtaining a set of binary training pattern vectors some of which are associated with a first pattern and the remainder of which are not associated with said first pattern, those training pattern vectors associated with the first pattern being identified as category 1 training pattern vectors and the remainder of the training pattern vectors which are not associated with said first pattern being identified as category 0 training pattern vectors, each said binary training pattern vector including the same number, N, of vector elements, and b) using the set of binary training pattern vectors as inputs to a computer, generating a binary tree having at least N levels and storing the tree in computer memory, which binary tree comprises a sequence of binary two-bit doublets each of which doublets comprises a tree node of one of four types including "no branch", "branch only left", "branch only right" and "branch both left and right" node.
- 8. In a method as defined in claim including reordering vector elements of all of the binary training vectors before generating a binary tree for reducing the number of nodes in the generated binary tree.
-
13. In a pattern recognition method, or the like, employing a set of training pattern vectors which set includes a plurality of groups of vectors, each of which groups is associated with a pattern to be recognized, steps during a training mode including,
using training pattern vectors from every group thereof, producing one first binary tree for each pattern to be recognized, each said first binary tree being adapted for recognizing a different one of said patterns to be recognized, and using training pattern vectors from every group thereof, producing an associated second binary tree for each said first binary tree, each said second binary tree being adapted for recognizing every pattern except the pattern recognized by the associated first binary tree, each said binary tree having N input levels where N is a whole number.
-
14. In a pattern recognition method, or the like, employing a set of training pattern vectors which set includes a plurality of groups of vectors, each of which groups is associated with a pattern to be recognized, steps during a training mode including,
using training pattern vectors from every group thereof, producing one first binary tree for each pattern to be recognized, each said first binary tree being adapted for recognizing a different one of said patterns to be recognized, and using training pattern vectors from every group thereof, producing an associated second binary tree for each said first binary tree, each said second binary tree being adapted for recognizing every pattern except the pattern recognized by the associated first binary tree, each said binary tree having N input levels where N is a whole number, the steps of producing first and second binary trees includes generating in computer memory a sequence of binary two-bit doublets for each of said trees, each of which doublets comprises a tree node of one of four types including "no branch", "branch only left", "branch only right" and "branch both left and right".
-
19. In a pattern recognition method, or the like, employing a set of binary training pattern vectors, a vector element reordering method including,
a) obtaining a measure of variability for each vector element of at least some binary training pattern vectors included in said set, and b) reordering the vector elements of the binary training pattern vectors dependent upon the measure of variability obtained in step a).
-
24. In a pattern recognition method, or the like, employing a set of training pattern vectors which set includes a group of vectors associated with a pattern category to be recognized, the remainder of which vectors are not associated with said pattern category,
steps during a training mode including, a. using said set of training pattern vectors, producing a first binary tree for recognizing pattern category vectors, b. using said set of training pattern vectors, producing a second binary tree adapted for recognizing vectors not included in said group associated with the pattern category, steps during pattern vector classification mode including, c. supplying a vector to be classified to said first and second binary trees, d. in the presence of a 1 output from said first binary tree, identifying the vector as belonging to the pattern category, and in the presence of a 1 output from said second binary tree, identifying the vector as not belonging to the pattern category, e. in the presence of a 0 output from both of the first and second binary trees, changing the vector element of the vector at the tree level at which the path in the trees traversed by the vector terminates, and f. repeating steps d and e until the vector is identified as either belonging to the pattern category or not belonging to the pattern category.
-
25. A method of classifying binary vectors by use of a binary tree which tree comprises a sequence of binary two-bit doublets each of which doublets comprises a node of one of four types including no branch, branch only left, branch only right, and branch both left and right, and wherein the binary vector specifies a path to be followed in the binary tree, binary vector elements 0 and 1 identifying branch left and branch right paths, respectively, said method comprising:
-
sequentially shifting binary doublets from the binary tree starting at the root node of the tree, identifying those binary tree doublets in the path specified by the vector to be classified, if the identified binary tree doublet identifies a no branch node, classifying the vector as one to be identified by the binary tree, and if the identified binary tree doublet identifies a node which does not include a branch in the direction indicated by the associated vector element, then classifying the vector as one which is not identified by the binary tree. - View Dependent Claims (26)
-
-
27. A system for classifying binary vectors which produces a first signal when the binary vector is identified as belonging to a class to be identified and produces a second signal when the binary vector is one which is identified as not belonging to said class, said system comprising,
tree memory means containing a binary tree comprising a sequence of binary two-bit doublets each of which doublets comprises a node of one of four types including no branch, branch only left, branch only right, and branch both left and right, input memory means containing a binary vector which specifies a path to be followed in the binary tree, logic means, means for supplying binary doublets from said tree memory means and vector elements from said input memory means to said logic means, said logic means in response to binary doublets and vector elements supplied thereto producing a first signal when the binary vector supplied thereto from said input memory means belongs to the class to be identified and producing a second signal when the binary vector does not belong to said class.
Specification