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

 The Delphion Integrated View

  Buy Now:   Buy PDF- 10pp  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: US4852173: Design and construction of a binary-tree system for language modelling
[ Derwent Title ]

Country: US United States of America

View Images High


10 pages

Inventor: Bahl, Lalit R.; Amawalk, NY
Brown, Peter F.; New York, NY
deSouza, Peter V.; Yorktown Heights, NY
Mercer, Robert L.; Yorktown Heights, 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: 1989-07-25 / 1987-10-29

Application Number: US1987000114892

IPC Code: Advanced: G06F 15/18; G06F 17/18; G10L 11/00; G10L 15/00; G10L 15/10; G10L 15/18;
IPC-7: G10L 9/06;

ECLA Code: G06N99/00L; G06F17/18; G10L15/00; T05K999/99;

U.S. Class: Current: 704/240; 382/226; 704/255;
Original: 381/043; 382/037; 364/513.5;

Field of Search: 381/041-43 364/513,513.5 382/037-40

Priority Number:
1987-10-29  US1987000114892

Abstract:     In order to determine a next event based upon available data, a binary decision tree is constructed having true or false questions at each node and a probability distribution of the unknown next event based upon available data at each leaf. Starting at the root of the tree, the construction process proceeds from node-to-node towards a leaf by answering the question at each node encountered and following either the true or false path depending upon the answer. The questions are phrased in terms of the available data and are designed to provide as much information as possible about the next unknown event. The process is particularly useful in speech recognition when the next word to be spoken is determined on the basis of the previously spoken words.

Attorney, Agent or Firm: Feig, Philip J. ; Schechter, Marc D. ;

Primary / Asst. Examiners: Salce, Patrick R.; Voeltz, Emanuel Todd

Maintenance Status: E3 Expired  Check current status

INPADOC Legal Status: Show legal status actions          Buy Now: Family Legal Status Report

Designated Country: DE FR GB 

Family: Show 7 known family members

First Claim:
Show all 12 claims
Having thus described our invention, what we claim as new, and desire to secure by Letters Patent is:     1. In a data processing system for determining an unknown event Y, given input data X(1), X(2) . . . X(N), a method of constructing a binary decision tree comprising the steps of:
  • defining at least one decision node whereat each decision node has two paths each extending to a succeeding node;
  • determining a set S(i) for each input datum X(i) by starting with an empty set and adding or deleting one datum item at a time to said set S(i) whenever the changed set reduces the entropy of the unknown event Y;
  • structuring a decision question at each decision node based upon the input data and in the form "is X(i) a member of set S(i)"; and
  • creating two additional paths if the entropy of the unknown event Y is reduced, or terminating at the decision node if the entropy is not reduced, whereby each terminated decision node is a leaf of the binary decision tree.

Background / Summary: Show background / summary

Drawing Descriptions: Show drawing descriptions

Description: Show description

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

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

Patent  Pub.Date  Inventor Assignee   Title
Get PDF - 17pp US3883847  1975-05 Frank  Bell Telephone Laboratories, Incorporated Uniform decoding of minimum-redundancy codes
Get PDF - 8pp US3918047  1975-11 Denes  Bell Telephone Laboratories, Incorporated Decoding circuit for variable length codes
Get PDF - 26pp US4466060  1984-08 Riddle  AT&T Bell Telephone Laboratories, Incorporated Message routing in a computer network
Get PDF - 13pp US4468728  1984-08 Wang  AT&T Bell Laboratories Data structure and search method for a data base management system
Get PDF - 9pp US4589142  1986-05 Bednar  International Business Machines Corp. (IBM) Method and apparatus for character recognition based upon the frequency of occurrence of said characters
Get PDF - 28pp US4593367  1986-06 Slack et al.  ITT Corporation Probabilistic learning element
Get PDF - 6pp US4654875  1987-03 Srihari et al.  The Research Foundation of State University of New York System to achieve automatic recognition of linguistic strings
Foreign References: None

Other Abstract Info: DERABS G89-131542

Other References:
  • IBM TDB "Probalistic Character Recognition Decision Trees with Style Variations" vol. 22, No. 10, Mar. 1980, pp. 4420-4422.
  • IBM TDB "Two-Level Character Recognition Logic" vol. 22, No. 10, Mar. 1980, pp. 4429.
  • IBM TDB "Two-Level Character Recognition", vol. 23, No. 8, Jan. 1981, pp. 3663-3664.
  • IBM TDB "Fast Algorithm for Computing the Optimal Linear Combinations of Probability Distributions", vol. 29, No. 5, Oct. 1986, pp. 2347-2348.
  • Proceeding of the IEEE, Nov. 1985, pp. 1549, 1571, 1572, 1610, 1611, 1633, 1639, 1644 and 1645.
  • Bahl, L. R. et al., "Method for Improving the Fast Match in Continuous Speech," IBM Technical Disclosure Bulletin, vol. 27, No. 11, Apr. 1985, pp. 6659-6660.
  • Barr, A. et al., The Handbook of Artificial Intelligence, vol. 1, pp. 80-83 and 349-352, 1981.
  • Kirkpatrick, S. et al., "Optimization by Simulated Annealing." Science, vol. 220, No. 4598, May 13, 1983, pp. 671-680. (10 pages) Cited by 87 patents
  • Lucassen, J. M. et al., "An Information Theoretic Approach to the Automatic Determination of Phonemic Baseforms." Proc. International Conf. on Acoustics, Speech and Signal Processing, 1984, pp. 42.5.1-42.5.4.
  • Tremblay, J. P. et al., An Introduction to Data Structures with Applications, McGraw-Hill, Inc., 1976, pp. 351-357.

  • 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