Apparatus and method for rejecting out-of-class inputs for pattern classification

• US 6,438,519 B1
• Filed: 05/31/2000
• Issued: 08/20/2002
• Est. Priority Date: 05/31/2000
• Status: Expired due to Term

• Current Assignee: Google Technology Holdings LLC (Alphabet Inc.)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Broun, Charles Conway, Campbell, William Michael
• Primary Examiner(s): Dorvil, Richemond
• Assistant Examiner(s): Opsasnick, Michael N.
• Application Number:
  US09/584,062
• Time in Patent Office: 811 Days
• Field of Search: 704/243, 704/231, 704/10, 707/2.6, 707/103-104, 707/200-206
• US Class Current: 704/243
• CPC Class Codes: G06F 18/2433 Single-class perspective, e.g. one-against-all classification; Novelty detection; Outlier detection
• CPC Class Codes: G06F 18/2453 non-linear, e.g. polynomial classifier
• CPC Class Codes: G10L 15/08 Speech classification or search

Abstract

Method and apparatus rejecting out-of-class inputs for pattern classification including a list of patterns with at least one in-context pattern and a rank tolerance. An input pattern is used to generate a classifier score for each pattern in the list and the classifier scores are ranked in decreasing order. The highest ranking score for an in-context pattern is determined and if the highest ranking score is 1 the in-context pattern is selected. If the highest ranking score is not 1 it is compared to the rank tolerance. When the highest ranking score is less than the rank tolerance the in-context pattern is selected and when the highest ranking score is greater than the rank tolerance the in-context pattern is rejected. Cohorts of the highest ranking pattern are removed from the list prior to the comparison.

Claims

1. A method of rejecting out-of-class inputs for pattern classification comprising the steps of:

providing a list of patterns including at least one in-context pattern;

providing a rank tolerance;

obtaining a pattern to be classified;

generating a classifier score for each pattern in the list of patterns;

ranking the classifier scores in decreasing order;

determining the highest ranking score for an in-context pattern; and

when the highest ranking score for the in-context pattern is one selecting the in-context pattern, when the highest ranking score for the in-context pattern is not one comparing the highest ranking score to the rank tolerance, when the highest ranking score for the in-context pattern is less than the rank tolerance selecting the in-context pattern, and when the highest ranking score for the in-context pattern is greater than the rank tolerance rejecting the in-context pattern.

2. A method of rejecting out-of-class inputs for pattern classification as claimed in claim 1 wherein the step of providing the rank tolerance includes providing a rank tolerance of at most 10% of the list of patterns.

3. A method of rejecting out-of-class inputs for pattern classification as claimed in claim 1 including in addition a step of discarding from the list of patterns all cohorts for the in-context pattern with the highest ranking score prior to the step of comparing the highest ranking score to the rank tolerance.

4. A method of rejecting out-of-class inputs for pattern classification as claimed in claim 3 further including a step of adjusting the number of cohorts and the rank tolerance so as to trade off false rejections and false acceptance.

5. A method of rejecting out-of-class inputs for pattern classification as claimed in claim 1 wherein the step of generating the classifier score for each pattern includes generating a plurality of feature vectors for the pattern to be classified and averaging the plurality of feature vectors to produce an average command structure.

6. A method of rejecting out-of-class inputs for pattern classification as claimed in claim 5 wherein the step of generating the classifier score for each pattern includes storing each pattern of the list of patterns as a model vector.

7. A method of rejecting out-of-class inputs for pattern classification as claimed in claim 6 wherein the step of generating the classifier score for each pattern includes using a polynomial discriminant function including the average command structure and each model vector to generate an inner product.

8. A method of rejecting out-of-class inputs for pattern classification comprising the steps of:

providing a list of classes including a plurality of in-vocabulary items;

providing a rank tolerance;

obtaining a speech utterance;

performing feature extraction on the speech utterance;

generating from the feature extraction a classifier score for each item in the list of classes;

ranking the classifier scores in decreasing order;

determining the in-vocabulary item with the highest ranking score; and

when the highest ranking score for the in-vocabulary item is one selecting the in-vocabulary item, when the highest ranking score for the in-vocabulary item is not one comparing the highest ranking score to the rank tolerance, when the highest ranking score for the in-vocabulary item is less than the rank tolerance selecting the in-vocabulary item, and when the highest ranking score for the in-vocabulary item is greater than the rank tolerance rejecting the in-vocabulary item.

9. A method of rejecting out-of-class inputs for pattern classification as claimed in claim 8 wherein the step of providing the rank tolerance includes providing a rank tolerance of at most 10% of the list of classes.

10. A method of rejecting out-of-class inputs for pattern classification as claimed in claim 8 including in addition a step of discarding from the list of classes all cohorts for the in-vocabulary item with the highest ranking score prior to the step of comparing the highest ranking score to the rank tolerance.

11. A method of rejecting out-of-class inputs for pattern classification as claimed in claim 10 further including a step of adjusting the number of cohorts and the rank tolerance so as to trade off false rejections and false acceptance.

12. A method of rejecting out-of-class inputs for pattern classification as claimed in claim 8 wherein the step of generating the classifier score for each item includes generating a plurality of feature vectors for the speech utterance and averaging the plurality of feature vectors to produce an average command structure.

13. A method of rejecting out-of-class inputs for pattern classification as claimed in claim 12 wherein the step of generating the classifier score for each item includes storing each item of the list of classes as a model vector.

14. A method of rejecting out-of-class inputs for pattern classification as claimed in claim 13 wherein the step of generating the classifier score for each item includes using a polynomial discriminant function including the average command structure and each model vector to generate an inner product.

15. Apparatus for rejecting out-of-class inputs in pattern classification systems comprising:

a feature extractor coupled to receive an input pattern to be classified and to output features of the input pattern;

a models memory having a plurality of models stored therein;

a classifier coupled to the feature extractor and to the models memory, the classifier being designed to receive the features of the input pattern from the feature extractor and to receive each of the plurality of models from the models memory and provide a classifier score for each of the plurality of models;

rank circuitry coupled to the classifier, the rank circuitry ranking the classifier score for each of the plurality of models; and

decision circuitry coupled to receive the ranking of the classifier scores from the rank circuitry, the decision circuitry including an adjustable rank tolerance and in-context memory, the decision circuitry being designed to select the highest in-context score from the ranking, compare the highest in-context score to the rank tolerance and determine one of accepting and rejecting the highest in-context score.

16. Apparatus for rejecting out-of-class inputs in pattern classification systems as claimed in claim 15 wherein the feature extractor, the models memory, the classifier, the rank circuitry, and the decision circuitry are included in a semiconductor chip.

17. Apparatus for rejecting out-of-class inputs in pattern classification systems as claimed in claim 15 wherein the feature extractor includes apparatus for converting the input pattern to a plurality of feature vectors.

18. Apparatus for rejecting out-of-class inputs in pattern classification systems as claimed in claim 17 wherein the models stored in the models memory are stored as model vectors.

19. Apparatus for rejecting out-of-class inputs in pattern classification systems as claimed in claim 18 wherein the classifier includes apparatus using a polynomial discriminant function including the average command structure and each model vector to generate an inner product.

20. Apparatus for rejecting out-of-class inputs in pattern classification systems as claimed in claim 15 including a stored list of cohorts coupled to one of the rank circuitry and the decision circuitry, the one of the rank circuitry and the decision circuitry discarding from the list of classes all cohorts for the in-vocabulary item with the highest ranking score prior to comparing the highest ranking in-context score to the rank tolerance.

21. Apparatus for rejecting out-of-class inputs in pattern classification systems as claimed in claim 20 wherein the stored list of cohorts and the rank tolerance are adjustable so as to trade off false rejections and false acceptance.