Method for optimizing a recognition dictionary to distinguish between patterns that are difficult to distinguish

• US 6,466,926 B1
• Filed: 07/12/1999
• Issued: 10/15/2002
• Est. Priority Date: 03/06/1996
• Status: Expired due to Term

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Kawatani, Takahiko
• Primary Examiner(s): STARKS, WILBERT L
• Application Number:
  US09/142,328
• Time in Patent Office: 1,191 Days
• Field of Search: 706/20, 705/28, 382/156
• US Class Current: 706/20
• CPC Class Codes: G06F 18/2132 based on discrimination criteria, e.g. discriminant analysis
• CPC Class Codes: G06F 18/243 relating to the number of classes
• CPC Class Codes: G06Q 10/087 Inventory or stock management, e.g. order filling, procurement or balancing against orders

Abstract

A discriminant function is defined by conventional learning discriminant analysis (22) and a value of the discriminant function is calculated (23) for all the training patterns in the in-category pattern set of each category and for all the training patterns in the in-category rival pattern set of the category. The incategory pattern set is composed of all the training patterns defined as belonging to the category. The rival pattern set is composed of the training patterns that belong to other categories and that are incorrectly recognized as belonging to the category. An in-category pattern subset and a rival pattern subset are then formed (24) for each category. The in-category pattern subset for the category is formed by selecting a predetermined number of the training patterns that belong to the in-category pattern set and that, among the training patterns that belong to the in-category pattern set, have the largest values of the discriminant function. The rival pattern subset for the category is formed by selecting a predetermined number of the training patterns that belong to the rival pattern set of the category and that, among the training patterns that belong to the rival pattern set, have the smallest values of the discriminant function. A linear discriminant analysis operation is then performed (25) on the in-category pattern subset and the rival pattern subset to obtain parameters defining a new discriminant function. The reference vector and weighting vector stored in the recognition dictionary for the category are then modified using the parameters defining the new discriminant function.

Claims

1. A method of generating a recognition dictionary that stores a reference vector and weighting vector for each of plural categories, the recognition dictionary being for use in a pattern recognition operation, the method optimizing the recognition dictionary to distinguish between patterns that are difficult to distinguish, and comprising steps of:

providing a training pattern set including training patterns;

for each category, performing a Learning by Discriminant Analysis (LDA) operation to define a discriminant function for the category, the LDA operation including;

performing a pattern recognition operation on the training patterns to define a rival pattern set composed of ones of the training patterns that belong to other categories but are misrecognized as belonging to the category,

performing a linear discriminant analysis between the rival pattern set and an in-category pattern set composed of ones of the training patterns defined as belonging to the category to generate the discriminant function, and

performing pattern recognition operations using the discriminant function and different values of a multiplier to determine a value of the multiplier that provides a greatest recognition ratio;

calculating a value of the discriminant function for each of the training patterns belonging to the in-category pattern set and for each of the training patterns belonging to the rival pattern set to generate a respective discriminant function value;

in response to the discriminant function values, selecting training patterns from the in-category pattern set to form an in-category pattern subset, and selecting training patterns from the rival pattern set to form a rival pattern subset, the training patterns selected to form the in-category subset and the rival pattern subset being training patterns that are difficult to distinguish;

performing a linear discriminant analysis between the training patterns belonging to the in-category pattern subset and the training patterns belonging to the rival pattern subset to generate parameters defining a new discriminant function for the category; and

modifying the reference vector and weighting vector stored in the recognition dictionary for the category using the parameters defining the new discriminant function.

2. The method of claim 1, in which the step of selecting training patterns from the in-category pattern set to form an in-category pattern subset, and selecting training patterns from the rival pattern set to form a rival pattern subset includes steps of:

selecting the training patterns having the largest discriminant function values in the in-category pattern set to form the in-category pattern subset; and

selecting the training patterns having the smallest discriminant function values in the rival pattern set to form the rival pattern subset.

3. The method of claim 2, in which:

(a) the step of performing a linear discriminant analysis includes a step of performing a pattern recognition operation on the training pattern set using the parameters defining the new discriminant function;

(b) the method additionally comprises steps of;

(1) identifying the training patterns that were incorrectly recognized by the pattern recognition operation as belonging to each category,

(2) forming a new in-category pattern subset and a new rival pattern subset for the category,

the new in-category pattern subset being formed by adding, to the in-category pattern subset for the category, the training patterns belonging to the category that were incorrectly recognized by the pattern recognition operation as belonging to other categories, and that are not currently members of the in-category pattern subset,

the new rival pattern subset being formed by adding, to the rival pattern subset for the category, the training patterns belonging to other categories that were incorrectly recognized by the pattern recognition operation as belonging to the category, and that are not currently members of the rival pattern subset;

(c) the steps of;

(1) performing the linear discriminant analysis and the pattern recognition operation using the parameters defining the new discriminant function,

(2) identifying the training patterns that were incorrectly recognized, and

(3) forming a new in-category pattern subset and a new rival pattern subset for the category,

constitute a loop; and

(d) the method additionally comprises a step of repetitively executing the loop, the step of performing a linear discriminant analysis being performed in each execution of the loop between the new in-category pattern subset and the new rival pattern subset formed in the previous execution of the loop.

4. The method of claim 3, in which:

the loop additionally includes a step of determining when all of the training patterns incorrectly recognized by the pattern recognition operation are included in the pattern subsets; and

the step of repetitively executing the loop includes repetitively executing the loop until the step of determining when all of the incorrectly recognized training patterns are included in the pattern subsets determines that all of the incorrectly recognized training patterns are included in the pattern subsets.

5. The method of claim 2, in which:

(a) the step of performing a linear discriminant analysis includes steps of;

(1) performing a pattern recognition operation on the training pattern set using the parameters defining the new discriminant function, the pattern recognition operating generating a pattern recognition result, and

(2) determining a recognition ratio for the pattern recognition result generated by the pattern recognition operation;

(b) the steps of;

(1) calculating the value of the discriminant function,

(2) selecting training patterns to form the in-category pattern subset and selecting training patterns to form the rival pattern subset, and

(3) performing a linear discriminant analysis, the pattern recognition operation using the parameters defining the new discriminant function, and determining the recognition ratio,

constitute a loop; and

(c) the method additionally comprises repetitively executing the loop until the recognition ratios determined in consecutive executions of the loop converge, the parameters determined in the step of performing the additional discriminant analysis in each execution of the loop defining the discriminant function whose value is calculated in the step of calculating the value of the discriminant function in the next execution of the loop.

6. The method of claim 5, in which:

(a) the method additionally comprises;

(1) identifying the training patterns that were incorrectly recognized by the pattern recognition operation as belonging to each category,

(2) forming a new in-category pattern subset and a new rival pattern subset for the category,

the new in-category pattern subset being formed by adding, to the in-category pattern subset for the category, the training patterns belonging to the category that were incorrectly recognized by the pattern recognition operation as belonging to other categories, and that are not currently members of the in-category pattern subset,

the new rival pattern subset being formed by adding, to the rival pattern subset for the category, the training patterns belonging to other categories that were incorrectly recognized by the pattern recognition operation as belonging to the category, and that are not currently members of the rival pattern subset;

(b) the steps of;

(1) performing a linear discriminant analysis, and the pattern recognition operation using the parameters defining the new discriminant function,

(2) identifying the training patterns that were incorrectly recognized, and

(3) forming a new in-category pattern subset and a new rival pattern subset for the category,

constitute a second loop, and

(c) the method additionally comprises a step of repetitively executing the second loop, the step of performing a linear discriminant analysis being performed in each execution of the second loop between the new in-category pattern subset and the new rival pattern subset formed in the previous execution of the second loop.

7. The method of claim 6, in which:

the second loop additionally includes a step of determining when all of the training patterns incorrectly recognized by the pattern recognition operation are included in the pattern subsets; and

the step of repetitively executing the second loop includes repetitively executing the second loop until the step of determining when all of the incorrectly-recognized training patterns are included in the pattern subsets determines that all of the incorrectly-recognized training patterns are included in the pattern subsets.

8. The method of claim 2, in which the linear discriminant analyses performed in the step of performing the Learning by Discriminant Analysis operation and in the step of performing a linear discriminant analysis each generate a discriminant function that includes linear and quadratic terms.

9. The method claim 8, in which:

(a) the step of performing a linear discriminant analysis includes a step of performing a pattern recognition operation on the training pattern set using the parameters defining the new discriminant function;

(b) the method additionally comprises steps of;

(1) identifying the training patterns that were incorrectly recognized by the pattern recognition operation as belonging to each category,

(2) forming a new in-category pattern subset and a new rival pattern subset for the category,

the new in-category pattern subset being formed by adding, to the in-category pattern subset for the category, the training patterns belonging to the category that were incorrectly recognized by the pattern recognition operation as belonging to other categories, and that are not currently members of the in-category pattern subset,

the new rival pattern subset being formed by adding, to the rival pattern subset for the category, the training patterns belonging to other categories that were incorrectly recognized by the pattern recognition operation as belonging to the category, and that are not currently members of the rival pattern subset;

(c) the steps of;

(1) performing the linear discriminant analysis and the pattern recognition operation using the parameters defining the new discriminant function,

(2) identifying the training patterns that were incorrectly recognized, and

(3) forming a new in-category pattern subset and a new rival pattern subset for the category,

constitute a loop; and

(d) the method additionally comprises a step of repetitively executing the loop, the step of performing a linear discriminant analysis being performed in each execution of the loop between the new in-category pattern subset and the new rival pattern subset formed in the previous execution of the loop.

10. The method of claim 9, in which,

the loop additionally includes a step of determining when all of the training patterns incorrectly recognized by the pattern recognition operation are included in the pattern subsets;

and

the step of repetitively executing the loop includes repetitively executing the loop until the step of determining when all of the incorrectly recognized training patterns are included in the pattern subsets determines that all of the incorrectly recognized training patterns are included in the pattern subsets.

11. The method of claim 8, in which:

(a) the step of performing a linear discriminant analysis includes steps of;

(1) performing a pattern recognition operation on the training pattern set using the parameters defining the new discriminant function, the pattern recognition operating generating a pattern recognition result, and

(2) determining a recognition ratio for the pattern recognition result generated by the pattern recognition operation;

(b) the steps of;

(1) calculating the value of the discriminant function,

(2) selecting training patterns to form the in-category pattern subset and selecting training patterns to form the rival pattern subset, and

(3) performing a linear discriminant analysis, the pattern recognition operation using the parameters defining the new discriminant function, and determining the recognition ratio,

constitute a loop; and

(c) the method additionally comprises repetitively executing the loop until the recognition ratios determined in consecutive executions of the loop converge, the parameters determined in the step of performing the additional discriminant analysis in each execution of the loop defining the discriminant function whose value is calculated in the step of calculating the value of the discriminant function in the next execution of the loop.

12. The method of claim 11, in which;

(a) the method additionally comprises;

(1) identifying the training patterns that were incorrectly recognized by the pattern recognition operation as belonging to each category,

(2) forming a new in-category pattern subset and a new rival pattern subset for the category,

the new in-category pattern subset being formed by adding, to the in-category pattern subset for the category, the training patterns belonging to the category that were incorrectly recognized by the pattern recognition operation as belonging to other categories, and that are not currently members of the in-category pattern subset,

the new rival pattern subset being formed by adding, to the rival pattern subset for the category, the training patterns belonging to other categories that were incorrectly recognized by the pattern recognition operation as belonging to the category, and that are not currently members of the rival pattern subset;

(b) the steps of;

(1) performing a linear discriminant analysis, and the pattern recognition operation using the parameters defining the new discriminant function,

(2) identifying the training patterns that were incorrectly recognized, and

(3) forming a new in-category pattern subset and a new rival pattern subset for the category,

constitute a second loop, and

(c) the method additionally comprises a step of repetitively executing the second loop, the step of performing a linear discriminant analysis being performed in each execution of the second loop between the new in-category pattern subset and the new rival pattern subset formed in the previous execution of the second loop.

13. The method of claim 12, in which:

the second loop additionally includes a step of determining when all of the training patterns incorrectly recognized by the pattern recognition operation are included in the pattern subsets; and

the step of repetitively executing the second loop includes repetitively executing the second loop until the step of determining when all of the incorrectly-recognized training patterns are included in the pattern subsets determines that all of the incorrectly-recognized training patterns are included in the pattern subsets.

14. The method of claim 1, in which:

(a) the step of performing a linear discriminant analysis includes steps of;

(1) performing a pattern recognition operation on the training pattern set using the parameters defining the new discriminant function, the pattern recognition operating generating a pattern recognition result, and

(2) determining a recognition ratio for the pattern recognition result generated by the pattern recognition operation;

(b) the steps of

(1) calculating the value of the discriminant function,

(2) selecting training patterns to form the in-category pattern subset and selecting training patterns to form the rival pattern subset, and

(3) performing a linear discriminant analysis, the pattern recognition operation using the parameters defining the new discriminant function, and determining the recognition ratio,

constitute a loop; and

(c) the method additionally comprises repetitively executing the loop until the recognition ratios determined in consecutive executions of the loop converge, the parameters determined in the step of performing the additional discriminant analysis in each execution of the loop defining the discriminant function whose value is calculated in the step of calculating the value of the discriminant function in the next execution of the loop.

15. The method of claim 14, in which:

(a) the method additionally comprises;

(1) identifying the training patterns that were incorrectly recognized by the pattern recognition operation as belonging to each category,

(2) forming a new in-category pattern subset and a new rival pattern subset for the category,

the new in-category pattern subset being formed by adding, to the in-category pattern subset for the category, the training patterns belonging to the category that were incorrectly recognized by the pattern recognition operation as belonging to other categories, and that are not currently members of the in-category pattern subset,

the new rival pattern subset being formed by adding, to the rival pattern subset for the category, the training patterns belonging to other categories that were incorrectly recognized by the pattern recognition operation as belonging to the category, and that are not currently members of the rival pattern subset;

(b) the steps of;

(1) performing a linear discriminant analysis, and the pattern recognition operation using the parameters defining the new discriminant function,

(2) identifying the training patterns that were incorrectly recognized, and

(3) forming a new in-category pattern subset and a new rival pattern subset for the category,

constitute a second loop, and

(c) the method additionally comprises a step of repetitively executing the second loop, the step of performing a linear discriminant analysis being performed in each execution of the second loop between the new in-category pattern subset and the new rival pattern subset formed in the previous execution of the second loop.

16. The method of claim 15, in which:

the second loop additionally includes a step of determining when all of the training patterns incorrectly recognized by the pattern recognition operation are included in the pattern subsets; and

the step of repetitively executing the second loop includes repetitively executing the second loop until the step of determining when all of the incorrectly-recognized training patterns are included in the pattern subsets determines that all of the incorrectly-recognized training patterns are included in the pattern subsets.

17. The method of claim 1, in which the linear discriminant analyses performed in the step of performing the Learning by Discriminant Analysis operation and in the step of performing a linear discriminant analysis each generate a discriminant function that includes linear and quadratic terms.

18. The method of claim 17, in which:

(a) the step of performing a linear discriminant analysis includes a step of performing a pattern recognition operation on the training pattern set using the parameters defying the new discriminant function;

(b) the method additionally comprises steps of;

(1) identifying the training patterns that were incorrectly recognized by the pattern recognition operation as belonging to each category,

(2) forming a new in-category pattern subset and a new rival pattern subset for the category,

the new in-category pattern subset being formed by adding, to the in-category pattern subset for the category, the training patterns belonging to the category that were incorrectly recognized by the pattern recognition operation as belonging to other categories, and that are not currently members of the in-category pattern subset,

the new rival pattern subset being formed by adding, to the rival pattern subset for the category, the training patterns belonging to other categories that were incorrectly recognized by the pattern recognition operation as belonging to the category, and that are not currently members of the rival pattern subset;

(c) the steps of;

(1) performing the linear discriminant analysis and the pattern recognition operation using the parameters defining the new discriminant function,

(2) identifying the training patterns that were incorrectly recognized, and

(3) forming a new in-category pattern subset and a new rival pattern subset for the category,

constitute a loop; and

(d) the method additionally comprises a step of repetitively executing the loop, the step of performing a linear discriminant analysis being performed in each execution of the loop between the new in-category pattern subset and the new rival pattern subset formed in the previous execution of the loop.

19. The method of claim 18, in which:

the loop additionally includes a step of determining when all of the training patterns incorrectly recognized by the pattern recognition operation are included in the pattern subsets; and

the step of repetitively executing the loop includes repetitively executing the loop until the step of determining when all of the incorrectly recognized training patterns are included in the pattern subsets determines that all of the incorrectly recognized training patterns are included in the pattern subsets.

20. The method of claim 1, in which:

(a) the step of performing a linear discriminant analysis includes a step of performing a pattern recognition operation on the training pattern set using the parameters defining the new discriminant function;

(b) the method additionally comprises steps of;

(1) identifying the training patterns that were incorrectly recognized by the pattern recognition operation as belonging to each category,

(2) forming a new in-category pattern subset and a new rival pattern subset for the category,

the new in-category pattern subset being formed by adding, to the in-category pattern subset for the category, the training patterns belonging to the category that were incorrectly recognized by the pattern recognition operation as belonging to other categories, and that are not currently members of the in-category pattern subset,

the new rival pattern subset being formed by adding, to the rival pattern subset for the category, the training patterns belonging to other categories that were incorrectly recognized by the pattern recognition operation as belonging to the category, and that are not currently members of the rival pattern subset;

(c) the steps of;

(1) performing the linear discriminant analysis and the pattern recognition operation using the parameters defining the new discriminant function,

(2) identifying the training patterns that were incorrectly recognized, and

(3) forming a new in-category pattern subset and a new rival pattern subset for the category,

constitute a loop; and

(d) the method additionally comprises a step of repetitively executing the loop, the step of performing a linear discriminant analysis being performed in each execution of the loop between the new in-category pattern subset and the new rival pattern subset formed in the previous execution of the loop.

21. The method of claim 20, in which:

the loop additionally includes a step of determining when all of the training patterns incorrectly recognized by the pattern recognition operation are included in the pattern subsets; and

the step of repetitively executing the loop includes repetitively executing the loop until the step of determining when all of the incorrectly recognized training patterns are included in the pattern subsets determines that all of the incorrectly recognized training patterns are included in the pattern subsets.