Work Files Saved Searches
   My Account                                                  Search:   Quick/Number   Boolean   Advanced       Help   

 The Delphion Integrated View

  Buy Now:   Buy PDF- 9pp  PDF  |   File History  |   Other choices   
  Tools:  Citation Link  |  Add to Work File:    
  View:  Expand Details   |  INPADOC   |  Jump to: 
 Email this to a friend  Email this to a friend 
Title: US6058205: System and method for partitioning the feature space of a classifier in a pattern classification system
[ Derwent Title ]

Country: US United States of America

View Images High


9 pages

Inventor: Bahl, Lalit Rai; Amawalk, NY
deSouza, Peter Vincent; San Jose, CA
Nahamoo, David; White Plains, NY
Padmanabhan, Mukund; Ossining, NY

Assignee: International Business Machines Corporation, Armonk, NY
other patents from INTERNATIONAL BUSINESS MACHINES CORPORATION (280070) (approx. 44,393)
 News, Profiles, Stocks and More about this company

Published / Filed: 2000-05-02 / 1997-01-09

Application Number: US1997000781574

IPC Code: Advanced: G06K 9/62;
IPC-7: G06F 17/20; G06K 9/62;

ECLA Code: G06K9/62C2M2A;

U.S. Class: Current: 382/159; 382/225; 704/231; 706/020;
Original: 382/159; 382/225; 706/020; 704/231;

Field of Search: 382/159,225,156,228,157,160,227 706/020,25 704/254,231,232,236,240,222

Priority Number:
1997-01-09  US1997000781574

Abstract:     A system and method are provided which partition the feature space of a classifier by using hyperplanes to construct a binary decision tree or hierarchical data structure for obtaining the class probabilities for a particular feature vector. One objective in the construction of the decision tree is to minimize the average entropy of the empirical class distributions at each successive node or subset, such that the average entropy of the class distributions at the terminal nodes is minimized. First, a linear discriminant vector is computed that maximally separates the classes at any particular node. A threshold is then chosen that can be applied on the value of the projection onto the hyperplane such that all feature vectors that have a projection onto the hyperplane that is less than the threshold are assigned to a child node (say, left child node) and the feature vectors that have a projection greater than or equal to the threshold are assigned to a right child node. The above two steps are then repeated for each child node until the data at a node falls below a predetermined threshold and the node is classified as a terminal node (leaf of the decision tree). After all non-terminal nodes have been processed, the final step is to store a class distribution associated with each terminal node. The class probabilities for a particular feature vector can then be obtained by traversing the decision tree in a top-down fashion until a terminal node is identified which corresponds to the particular feature vector. The information provided by the decision tree is that, in computing the class probabilities for the particular feature vector, only the small number of classes associated with that particular terminal node need be considered. Alternatively, the required class probabilities can be obtained simply by taking the stored distribution of the terminal node associated with the particular feature vector.

Attorney, Agent or Firm: F. Chau & Associates, LLP ;

Primary / Asst. Examiners: Lee, Thomas D.; Chen, Wenpeng

Maintenance Status: E2 Expired  Check current status

INPADOC Legal Status: Show legal status actions

Family: None

First Claim:
Show all 16 claims
What is claimed is:     1. A system of pattern recognition using feature vectors representing corresponding portions of a physical pattern, said system comprising:
  • means for assigning a class to every training feature vector within a set of training feature vectors;
  • means for nonlinearly mapping the set of feature vectors to a higher dimensional space;
  • means for separating the classes by computing a projection which maximally separates the classes in the higher dimensional space and projecting each of the training feature vectors;
  • means for assigning the training feature vectors having projections less than a first threshold to a first memory segment and remaining training feature vectors into a second memory segment;
  • means for storing the hyperplane and the first threshold within the first and second memory segments;
  • means for separating the classes within the first and/or second memory segments if the classes are associated with a number of training feature vectors greater than a second threshold;
  • means for designating in a memory the first and/or second memory segments as terminal memory segments if said first and/or second memory segments contain classes associated with a number of training feature vectors less than the second threshold;
  • means for storing information about the classes associated with the number of training feature vectors less than the second threshold within corresponding terminal memory segments; and
  • means for recognizing a portion of the physical pattern by retrieving stored information from one or more terminal memory segments corresponding to one or more feature vectors representing said portion.

Background / Summary: Show background / summary

Drawing Descriptions: Show drawing descriptions

Description: Show description

Forward References: Show 28 U.S. patent(s) that reference this one

U.S. References: Go to Result Set: All U.S. references   |  Forward references (28)   |   Backward references (2)   |   Citation Link

Patent  Pub.Date  Inventor Assignee   Title
Get PDF - 17pp US5522011  1996-05 Epstein et al.  International Business Machines Corporation Speech coding apparatus and method using classification rules
Get PDF - 11pp US5680509  1997-10 Gopalakrishnan et al.  International Business Machines Corporation Method and apparatus for estimating phone class probabilities a-posteriori using a decision tree
Foreign References: None

Other Abstract Info: DERABS G2000-364353 DERABS G2000-364353

Inquire Regarding Licensing

Powered by Verity

Plaques from Patent Awards      Gallery of Obscure PatentsNominate this for the Gallery...

Thomson Reuters Copyright © 1997-2014 Thomson Reuters 
Subscriptions  |  Web Seminars  |  Privacy  |  Terms & Conditions  |  Site Map  |  Contact Us  |  Help