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

 The Delphion Integrated View

  Buy Now:   Buy PDF- 14pp  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: US6049767: Method for estimation of feature gain and training starting point for maximum entropy/minimum divergence probability models

Country: US United States of America

View Images High


14 pages

Inventor: Printz, Harry W.; New York, 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-04-11 / 1998-04-30

Application Number: US1998000070692

IPC Code: Advanced: G10L 15/06; G10L 15/18;
IPC-7: G10L 11/00;

ECLA Code: G10L15/063; S10L15/197;

U.S. Class: Current: 704/240; 704/243; 704/255; 704/E15.008;
Original: 704/240; 704/243; 704/255;

Field of Search: 704/240,243,255,257

Government Interest:     The U.S. Government has a paid-up license in this invention and the right in the limited circumstances to require the patent owner to license others on reasonable terms as provided for by the terms of Contract No. IRI-9314969 awarded by the National Science Foundation.

Priority Number:
1998-04-30  US1998000070692

Abstract:     A method and apparatus for efficiently determining the gain of a feature function in a maximum entropy/minimum divergence probability model in a single pass through a training corpus. A method for determining the gain of a feature in such a model includes the steps of a selecting a set of evaluation points and determining the value of a function referred to as the gainsum derivative at each of the evaluation points. An approximation function which can be evaluated at substantially any point in a continuous domain is then selected based upon the discrete values of the gainsum derivative at the evaluation points. The approximation function is then employed to determine the argument value that maximizes an approximated gain function. The approximate gain value is then determined by evaluating the approximated gain function at this argument value. The apparatus of the present invention includes means for performing the steps of the disclosed method.

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

Primary / Asst. Examiners: Hudspeth, David R.; Wieland, Susan

Maintenance Status: E2 Expired  Check current status

INPADOC Legal Status: Show legal status actions

Family: None

First Claim:
Show all 17 claims
What is claimed is:     1. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for determining a gain value of a feature in an MEMD (maximum entropy/minimum divergence) probability model, the method comprising the steps of:
  • receiving as input, a corpus comprising a plurality of words, a list of features representing one of grammatical and semantic relationships among words, and a set of evaluation points;
  • for each feature;
    • determining a value of a gainsum derivative function at each of said evaluation points, resulting in a gainsum derivative vector;
    • selecting a continuous approximation function based upon said gainsum derivative vector;
    • determining the argument value that maximizes the value of an approximated gain function from said approximation function; and
    • determining the approximate gain value by evaluating the approximated gain function at said argument value; and
    • outputting for use in constructing an MEMD model one of (1) the features and corresponding argument values, for those features having an approximate gain value that exceeds a predetermined threshold value and (2) all the features and corresponding approximate gain values and argument values.

Background / Summary: Show background / summary

Drawing Descriptions: Show drawing descriptions

Description: Show description

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

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

Patent  Pub.Date  Inventor Assignee   Title
Get PDF - 21pp US5467425  1995-11 Lau et al.  International Business Machines Corporation Building scalable N-gram language models using maximum likelihood maximum entropy N-gram models
Get PDF - 17pp US5640487  1997-06 Lau et al.  International Business Machines Corporation Building scalable n-gram language models using maximum likelihood maximum entropy n-gram models
Foreign References: None

Other References:
  • A Maximum Entropy Approach to Natural Language Processing, Berger et al., Computational Linguistics, 22(1): 39-71, Mar. 1996. (33 pages) Cited by 8 patents [ISI abstract]
  • Inducing Features of Random Fields, Dell Pietra et al., Technical Report CMU-CS-95-144, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA, May 1995.

  • 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