System and method for determining confidence levels for the results of a categorization system

• US 6,003,027 A
• Filed: 11/21/1997
• Issued: 12/14/1999
• Est. Priority Date: 11/21/1997
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Prager, John Martin
• Primary Examiner(s): AMSBURY, WAYNE P
• Application Number:
  US08/976,349
• Time in Patent Office: 753 Days
• Field of Search: 707/5, 707/6
• US Class Current: 1/1
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

After a categorization process has been run, the scores of the top-two ranking categories along with the size or number of features in the object being categorized, are passed to a confidence assignment process. This determines a value for the confidence in the top category based on the evidence afforded by the input parameters. The magnitude of this confidence value will determine whether the system can accept the automatic categorization results, or whether human involvement is required. This invention also describes the process of determining the optimal value of an internal scaling parameter in the confidence assignment process. The construction of a threshold table based on this parameter is also described. The threshold table matches confidence values against error levels. For a given error rate the previously assigned confidence determines whether the categorization results can be accepted without need for human intervention. This invention maximizes the number of objects that can be automatically processed, for a given error rate.

Claims

1. A computer system for determining a confidence level of a category of one or more documents, comprising:

a memory and a central processing unit (CPU);

a categorization process executed by the CPU and generating a results table, one or more documents being categorized into one or more categories, each category corresponding to a score in said results table and each document having a size and one or more features; and

a confidence process executed by the CPU on said results table to generate a threshold table, said confidence process determining a confidence level for said each category by taking a product of a first credibility that a highest scoring category of said categories is correct with a second credibility that a next highest scoring category of said categories is incorrect and normalizing the product by a third credibility that at least one of the highest and second-highest scoring categories is incorrect.

2. A system, as in claim 1, where the first and second credibilities are weighted by a raising each of the first and second credibilities to a power that is a function of the size of the document.

3. A system, as in claim 2, where the function is log(1+N/k), where N is the size of the document and k is a constant.

4. A system, as in claim 3, where k is greater than 1 but less than N.

5. A system, as in claim 3, where an optimum value of k is empirically determined for one or more of the following:

a set of documents and a set of features.

6. A system, as in claim 3, where N is measured by the number of features of the document.

7. A system, as in claim 6, where the document contains text and one or more of the features is the frequency of occurence of any one of the following:

an individual word, an individual phrase, and an N-gram that is a sequence of one or more characters.

8. A system, as in claim 6, where the document contains audio and one or more of the features is the frequency of occurence of any one of the following:

a pitch, an amplitude, and a duration of a note.

9. A system, as in claim 6, where the document contains still images and one or more of the features is the frequency of occurence of any one of the following:

a color, a texture, and a shape.

10. A system, as in claim 1, where one of the confidence levels is correlated to a correctness level of a set of one or more correctness levels of the categorization process.

11. A system, as in claim 10, where each of the confidence levels is determined at an optimal empirical value of k.

12. A system, as in claim 1, where the documents can be any one or more of the following types:

electronic mail, scientific articles, news stories, business information, sports information, requests to a service organization, a claim, a letter, and transcription of telephone calls.

13. A system, as in claim 12, where the documents are tagged with one or more of the types as determined by the category with the highest confidence level.

14. A system, as in claim 12, where the documents are routed to a location as determined by the category with the highest confidence level.

15. A method of verifying categorization of one or more documents, the method comprising the steps of:

taking a product of the credibility that a highest scoring document category is correct with a second credibility that a next highest scoring document category is incorrect;

normalizing the product by the credibility that at least one of the highest and second-highest scoring document categories is incorrect to create a confidence score; and

assigning the document to the highest scoring document category if the confidence score is above a threshold.

16. A method as in claim 15, further comprising before the step of taking the product of credibilities, the step of:

generating intermediate values for the highest and next highest scoring categories, the intermediate value being generated according to (1-S)^log(1+N/k) and wherein, S is the score of a corresponding category, N is determined by a corresponding document being scored and k is a scaling constant.

17. A method as in claim 15, wherein scaling constant k is initially set to the square root of an average number of categorized features and adjusted to increase the number of correctly categorized documents.

18. A system for verifying categorization of one or more documents, the system comprising:

means for taking a product of the credibility that a highest scoring document category is correct with a second credibility that a next highest scoring document category is incorrect;

means for normalizing the product by the credibility that at least one of the highest and second-highest document scoring categories is incorrect to create a confidence score; and

means for assigning the document in the highest scoring document category if the confidence score is above a threshold.

19. A system as in claim 18, further comprising:

means for generating intermediate values for the highest and next highest scoring categories, the intermediate value being generated according to (1-S)^log(1+N/k) and wherein, S is the score of a corresponding category, N is determined by a corresponding document being scored and k is a scaling constant.

20. A method as in claim 19, wherein scaling constant k is initially set to the square root of an average number of categorized features and further comprising:

means for adjusting k to increase the number of correctly categorized documents.