Continuous reference adaptation in a pattern recognition system

• US 5,617,486 A
• Filed: 11/27/1995
• Issued: 04/01/1997
• Est. Priority Date: 09/30/1993
• Status: Expired due to Term

• Current Assignee: Apple Inc.
• Original Assignee: Apple Computer Incorporated (Apple Inc.)
• Inventors: deSouza, Peter V., Hon, Hsiao-Wuen, Chow, Yen-Lu, Fineberg, Adam B.
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): Tran, Phuoc
• Application Number:
  US08/563,256
• Time in Patent Office: 491 Days
• Field of Search: 382/115, 382/119, 382/159, 382/160, 382/161, 382/181, 382/187, 382/215, 382/225, 382/228, 395/2, 395/2.53, 395/2.54, 395/2.59, 395/2.64, 395/2.65, 381/41, 381/42, 381/43
• US Class Current: 382/181
• CPC Class Codes: G06V 40/30 Writer recognition; Reading and verifying signatures
• CPC Class Codes: G10L 15/063 Training
• CPC Class Codes: G10L 15/07 to the speaker
• CPC Class Codes: G10L 15/144 Training of HMMs
• CPC Class Codes: G10L 2015/0635 updating or merging of old and new templates; Mean values; Weighting

Abstract

A pattern recognition system which continuously adapts reference patterns to more effectively recognize input data from a given source. The input data is converted to a set or series of observed vectors and is compared to a set of Markov Models. The closest matching Model is determined and is recognized as being the input data. Reference vectors which are associated with the selected Model are compared to the observed vectors and updated ("adapted") to better represent or match the observed vectors. This updating method retains the value of these observed vectors in a set of accumulation vectors in order to base future adaptations on a broader data set. When updating, the system also may factor in the values corresponding to neighboring reference vectors that are acoustically similar if the data set from the single reference vector is insufficient for an accurate calculation. Every reference vector is updated after every input; thus reference vectors neighboring an updated reference vector may also be updated. The updated reference vectors are then stored by the computer system for use in recognizing subsequent inputs.

Claims

1. An apparatus for pattern recognition of data input comprising:

means for representing said data input as a set of observed vectors, wherein individual observed vectors of said set of observed vectors represent said data input at a different point in time;

means for comparing a first subset of said set of observed vectors to a set of models by comparing a set of reference vectors associated with said set of models to said set of observed vectors and identifying a resultant model which most closely matches said first subset, wherein said resultant model is one of said set of models;

means for creating a set of accumulation vectors wherein individual accumulation vectors of said set of accumulation vectors correspond to individual reference vectors of said set of reference vectors, and wherein a first accumulation vector of said set of accumulation vectors stores a first observed vector, and wherein said first observed vector was previously associated with a first reference vector of said set of reference vectors;

means for updating said set of reference vectors to create an updated set of reference vectors associated with said set of models to more accurately represent said data input, wherein said means for updating combines said first accumulation vector with said first reference vector; and

means for utilizing said updated set of reference vectors in comparing subsequent data input streams to said set of models.

2. An apparatus for pattern recognition as claimed in claim 1 wherein said set of models consists of a set of Markov Models.

3. An apparatus for pattern recognition as claimed in claim 1 wherein said means for updating further comprises:

means for creating a set of counters such that individual counters of said set of counters correspond to individual reference vectors of said set of reference vectors;

means for comparing each observed vector of said first subset of said set of observed vectors to said set of reference vectors;

means for determining a closest reference vector to each of said observed vectors wherein said closest reference vector is more similar to said observed vector than any other reference vector in said set of reference vectors;

means for incrementing an individual counter corresponding to said closest reference vector, said individual counter indicating the number of observed vectors which have been added to the accumulation vector corresponding to said closest reference vector; and

means for adding said observed vector to the accumulation vector corresponding to said closest reference vector.

4. An apparatus for pattern recognition as claimed in claim 3 wherein said means for updating further comprises:

means for determining a subset of said set of reference vectors such that said subset of reference vectors is closer to said closest reference vector than other reference vectors of said set of reference vectors which are not within said subset;

means for determining the number of said reference vectors in said subset;

means for constructing a correction vector based on said number of said reference vectors in said subset and said accumulation vectors corresponding to said reference vectors in said subset; and

means for summing said correction vector and said closest reference vector.

5. An apparatus for pattern recognition as claimed in claim 3 wherein said means for adding said observed vector to said accumulation vector further comprises means for assigning said observed vector a larger proportion of the sum than prior additions of observed vectors to said accumulation vector.

6. An apparatus for pattern recognition as claimed in claim 1 wherein said means for updating further comprises:

means for creating a set of counters such that individual counters of said set of counters correspond to individual reference vectors of said set of reference vectors;

means for comparing each observed vector of said first subset of said set of observed vectors to said set of reference vectors;

means for determining a first subset of said set of reference vectors which are more similar to said observed vector than other reference vectors in said set of reference vectors;

means for incrementing the individual counters corresponding to the individual reference vectors of said subset of said set of reference vectors, each of said individual counters indicating the number of observed vectors which have been added to the accumulation vector of the corresponding reference vector;

means for multiplying said observed vector by a fraction to generate a portion of said observed vector, wherein said fraction is determined by a similarity between said observed vector and an individual reference vector in said subset; and

means for summing said portion of said observed vector to individual reference vectors in said first subset.

7. An apparatus for pattern recognition as claimed in claim 6 wherein said means for updating further comprises:

means for determining a particular reference vector in said first subset of said set of reference vectors;

means for determining a second subset of said set of reference vectors such that said second subset of reference vectors is closer to said particular reference vector than other reference vectors of said set of reference vectors which are not within said second subset;

means for determining the number of said reference vectors in said second subset;

means for constructing a correction vector based on said number of said reference vectors in said second subset and said accumulation vectors corresponding to said reference vectors in said second subset; and

means for summing said correction vector and said particular reference vector.

8. An apparatus for pattern recognition as claimed in claim 6 wherein said means for summing said portion further comprises means for assigning said portion of said observed vector a larger proportion of the sum than prior additions of portions of observed vectors to said accumulation vector.

9. An apparatus for pattern recognition as claimed in claim 1 wherein each vector of said set of reference vectors consists of a Gaussian distribution.

10. An apparatus for pattern recognition as claimed in claim 1 further comprising:

means for long-term storage of said updated reference vectors;

means for associating said updated reference vectors with a particular input source; and

means for recovering said updated reference vectors from said means for long-term storage.

11. An apparatus for pattern recognition as claimed in claim 1 further comprising:

means for requesting user-acknowledgment of said resultant model;

means for receiving said user-acknowledgment as input to the system; and

means for receiving a repeated data input.

12. An apparatus for pattern recognition as claimed in claim 1 wherein said data input comprises speech input.

13. A computerized method for pattern recognition of data input, wherein said data input represents one or more unknown patterns, said method comprising the computer-implemented steps of:

a) transforming said data input into a set of observed vectors, wherein individual observed vectors of said set of observed vectors represent said data input at a different point in time;

b) comparing a first subset of said set of observed vectors to a set of models utilizing a set of reference vectors associated with said set of models and identifying a resultant model which most closely matches said first subset, wherein said resultant model is one of said set of models;

c) creating a set of accumulation vectors wherein individual accumulation vectors of said set of accumulation vectors correspond to individual reference vectors of said set of reference vectors, and wherein a first accumulation vector of said set of accumulation vectors stores a first observed vector, and wherein said first observed vector was previously associated with a first reference vector of said set of reference vectors;

d) updating said set of reference vectors to create a set of updated reference vectors associated with said set of models to more accurately represent said data input, wherein said updating includes combining said first accumulation vector with said first reference vector; and

e) utilizing said set of updated reference vectors in comparing subsequent data input streams to said set of models.

14. A method for pattern recognition as claimed in claim 13 wherein said set of models consists of a set of Markov Models.

15. A method for pattern recognition as claimed in claim 13 wherein said step c) further comprises:

creating a set of counters such that individual counters of said set of counters correspond to individual reference vectors of said set of reference vectors;

comparing each of said observed vectors to said set of reference vectors;

determining a closest reference vector to each of said observed vectors wherein said closest reference vector is more similar to said observed vector than any other reference vector in said set of reference vectors;

incrementing an individual counter corresponding to said closest reference vector, said individual counter indicating the number of observed vectors which have been added to the accumulation vector corresponding to said closest reference vector; and

adding said observed vector to the accumulation vector corresponding to said closest reference vector.

16. A method for pattern recognition as claimed in claim 15 wherein said step c) further comprises:

determining a subset of said set of reference vectors such that said subset of reference vectors is closer to said closest reference vector than other reference vectors of said set of reference vectors which are not within said subset;

determining the number of said reference vectors in said subset;

constructing a correction vector based on said number of said reference vectors in said subset and said accumulation vectors corresponding to said reference vectors in said subset; and

summing said correction vector and said closest reference vector.

17. A method for pattern recognition as claimed in claim 15 wherein said step of adding further comprises the step of assigning said observed vector a larger proportion of the sum than prior additions of observed vectors to said accumulation vector.

18. A method for pattern recognition as claimed in claim 13 wherein said step c) further comprises:

creating a set of counters such that individual counters correspond to individual reference vectors in said set of reference vectors;

comparing each of said observed vectors to said set of reference vectors;

determining a first subset of said set of reference vectors which are more similar to said observed vector than other reference vectors in said set of reference vectors;

incrementing the individual counters corresponding to the individual reference vectors of said subset of said set of reference vectors, each of said individual counters indicating the number of observed vectors which have been added to the accumulation vector of the corresponding reference vector;

multiplying said observed vector by a fraction to generate a portion of said observed vector, wherein said fraction is determined by a similarity between said observed vector and an individual reference vector in said subset; and

summing said portion of said observed vector to individual reference vectors in said first subset wherein said portion of said observed vector is determined by a similarity between said observed vector and an individual reference vector in said subset.

19. A method for pattern recognition as claimed in claim 18 wherein said step c) further comprises:

determining a particular reference vector in said first subset of said set of reference vectors;

determining a second subset of said set of reference vectors such that said second subset of reference vectors is closer to said particular reference vector than other reference vectors of said set of reference vectors which are not within said second subset;

determining the number of said reference vectors in said second subset;

constructing a correction vector based on said number of said reference vectors in said second subset and said accumulation vectors corresponding to said reference vectors in said second subset; and

summing said correction vector and said particular reference vector.

20. A method for pattern recognition as claimed in claim 18 wherein said step of summing said portion further comprises assigning said portion of said observed vector a larger proportion of the sum than prior additions of portions of observed vectors to said accumulation vector.

21. A method for pattern recognition as claimed in claim 13 wherein each vector of said set of reference vectors consists of a Gaussian distribution.

22. A method for pattern recognition as claimed in claim 13 further comprising:

storing said updated reference vectors in a storage means;

associating said updated reference vectors with a particular input source; and

recovering said updated reference vectors from said storage means.

23. A method for pattern recognition as claimed in claim 13 further comprising the steps of:

requesting user-acknowledgment of said resultant model;

receiving said user-acknowledgment; and

receiving a repeated data input.

24. A method for pattern recognition as claimed in claim 13 wherein said data input comprises speech input.

25. In a computer system, an apparatus for speech recognition of data input utilizing Markov Models comprising:

an input device;

a memory unit, said memory unit storing a set of Markov Models and a set of reference vectors associated with said set of Markov Models;

a digital processor, said digital processor being coupled to said input device and said memory unit, said digital processor converting said data input to a set of observed vectors wherein individual observed vectors represent said data input at a different point in time, said digital processor comparing a first subset of said set of observed vectors to said set of Markov Models utilizing said set of reference vectors and identifying a resultant Markov Model of said set of Markov Models which most closely resembles said data input, said digital processor comparing said set of observed vectors to said set of reference vectors associated with said resultant Markov Model, said digital processor creating a set of accumulation vectors wherein individual accumulation vectors of said set of accumulation vectors respond to individual reference vectors of said set of reference vectors, and wherein a first accumulation vector of said set of accumulation vectors stores a first observed vector, and wherein said first observed vector was previously associated with a first reference vector of said set of reference vectors, said digital processor updating said set of reference vectors to create an updated set of reference vectors associated with said set of Markov Models to more accurately represent said observed vectors by combining said first accumulation vector with the first reference vector, said memory unit storing said updated set of reference vectors, and said digital processor utilizing said updated set of reference vectors in comparing subsequent input data to said set of Markov Models.

26. An apparatus for speech recognition as claimed in claim 25 wherein each vector of said set of reference vectors consists of a Gaussian distribution.

27. An apparatus for speech recognition as claimed in claim 25 further comprising:

a storage unit coupled to said input device, said memory unit and said digital processor.

28. An apparatus for speech recognition is claimed in claim 27 further comprising said digital processor associating said updated reference vectors with a particular input source, said digital processor storing said updated reference vectors in said storage unit, and said digital processor recovering said updated reference vectors from said storage unit.

29. An apparatus for speech recognition as claimed in claim 25 further comprising:

an output unit coupled to said digital processor, and

a command input unit coupled to said digital processor.

30. In a computer system, an apparatus for speech recognition of data input utilizing Markov Models comprising:

an input device;

a memory unit, said memory unit storing a set of Markov Models and a set of reference vectors associated with said set of Markov Models;

a digital processor, said digital processor being coupled to said input device and said memory unit, said digital processor converting said data input to a set of observed vectors wherein individual observed vectors represent said data input at a different point in time, said digital processor comparing a first subset of said set of observed vectors to said set of Markov Models utilizing said set of reference vectors and identifying a resultant Markov Model of said set of Markov Models which most closely resembles said data input, said digital processor comparing said set of observed vectors to said set of reference vectors associated with said resultant Markov Model, said digital processor updating said set of reference vectors to create an updated set of reference vectors associated with said set of Markov Models to more accurately represent said set of observed vectors by combining a first observed vector or said first subset of said set of observed vectors with a first reference vector of said set of reference vectors, said memory unit storing said updated set of reference vectors, said digital processor utilizing said updated set of reference vectors in comparing subsequent input data to said set of Markov Models, said digital processor creating a set of accumulation vectors wherein individual accumulation vectors correspond to individual reference vectors in said set of reference vectors, said memory unit storing said set of accumulation vectors, said digital processor creating a set of counters wherein individual counters of said set of counters correspond to individual reference vectors of said set of reference vectors, each of said individual counters indicating the number of observed vectors which have been added to the accumulation vector of the corresponding reference vector, said memory unit storing said set of counters, said digital processor comparing each of said first subset of observed vectors to said set of reference vectors, said digital processor determining a closest reference vector to each of said first subset of observed vectors wherein said closest reference vector is more similar to said observed vector than any other reference vector in said set of reference vectors, said digital processor incrementing the counter corresponding to said closest reference vector, and said digital processor adding said observed vector to the accumulation vector corresponding to said closest reference vector.

31. An apparatus for speech recognition as claimed in claim 30 further comprising said digital processor determining a subset of said set of reference vectors such that said subset of reference vectors is closer to said closest reference vector than other reference vectors of said set of reference vectors which are not within said subset, said digital processor determining the number of said reference vectors in said subset, said digital processor constructing a correction vector based on said number of said reference vectors in said subset and said accumulation vectors corresponding to said reference vectors in said subset, and said digital processor summing said correction vector and said closest reference vector.

32. An apparatus for speech recognition as claimed in claim 30 wherein said digital processor adding said observed vector to said accumulation vector assigns said observed vector a larger proportion of the sum than prior additions of observed vectors to said accumulation vector.

33. A computer system for pattern recognition of data input utilizing Markov Models comprising:

a bus;

a memory unit coupled to said bus;

a storage unit coupled to said bus which contains a set of models and a set of reference vectors associated with said set of models;

a data input unit coupled to said bus which receives said data input;

a signal processor which represents said data input as a set of observed vectors, wherein individual observed vectors of said set of observed vectors represent said data input at a different point in time; and

a central processing unit (CPU) coupled to said bus which compares a first subset of said set of observed vectors to said set of models utilizing said set of reference vectors and identifies a resultant model which most closely matches said first subset, said resultant model being one of said set of models, wherein said CPU further creates an updated set of reference vectors associated with said set of models to more accurately represent said data input by combining a first observed vector of said first subset of said set of observed vectors with a first reference vector of said set of reference vectors, and utilizes said updated set of reference vectors in comparing subsequent data input streams to said set of models, and wherein said CPU includes,

means for creating a set of accumulation vectors wherein individual accumulation vectors of said set of accumulation vectors correspond to individual reference vectors of said set of reference vectors,

means for creating a set of counters such that individual counters of said set of counters correspond to individual reference vectors of said set of reference vectors,

means for comparing each of said first subset of observed vectors to said set of reference vectors,

means for determining a closest reference vector to each of said first subset of observed vectors wherein said closest reference vector is more similar to said observed vector than any other reference vector in said set of reference vectors,

means for incrementing an individual counter corresponding to said closest reference vector, said individual counter indicating the number of observed vectors which have been added to the accumulation vector corresponding to said closest reference vector, and

means for adding said observed vector to an accumulation vector corresponding to said closest reference vector.

34. A computer system as claimed in claim 33 wherein said CPU further comprises:

means for determining a subset of said set of reference vectors such that said subset of reference vectors is closer to said closest reference vector than other reference vectors of said set of reference vectors which are not within said subset;

means for determining the number of said reference vectors in said subset;

means for constructing a correction vector based on said number of said reference vectors in said subset and said accumulation vectors corresponding to said reference vectors in said subset; and

means for summing said correction vector and said closest reference vector.

35. A computer system as claimed in claim 33 wherein said means for adding said observed vector to said accumulation vector further comprises means for assigning said observed vector a larger proportion of the sum than prior additions of observed vectors to said accumulation vector.

36. A computer system for pattern recognition of data input utilizing Markov Models comprising:

a bus;

a memory unit coupled to said bus;

a storage unit coupled to said bus which contains a set of models and a set of reference vectors associated with said set of models;

a data input unit coupled to said bus which receives said data input;

a signal processor which represents said data input as a set of observed vectors, wherein individual observed vectors of said set of observed vectors represent said data input at a different point in time; and

a central processing unit (CPU) coupled to said bus which compares a first subset of said set of observed vectors to said set of models utilizing said set of reference vectors and identifies a resultant model which most closely matches said first subset, said resultant model being one of said set of models, wherein said CPU further creates a set of accumulation vectors wherein individual accumulation vectors of said set of accumulation vectors correspond to individual reference vectors of said set of reference vectors, wherein a first accumulation vector of said set of accumulation vectors stores a first observed vector, and wherein said first observed vector was previously associated with a first reference vector of said set of reference vectors, and wherein said CPU further creates an updated set of reference vectors associated with said set of models to more accurately represent said data input by combining said first accumulation vector with said first reference vector, and utilizes said updated set of reference vectors in comparing subsequent data input streams to said set of models.

37. A computer system as claimed in claim 36 wherein said set of models consists of a set of Markov Models.

38. A computer system as claimed in claim 36 wherein each vector of said set of reference vectors consists of a Gaussian distribution.

39. A computer system as claimed in claim 36, wherein:

said storage unit also provides long-term storage of said updated reference vectors; and

said CPU also associates said updated reference vectors with a particular input source, and

recovers said updated reference vectors from said storage unit.

40. A computer system as claimed in claim 36 further comprising:

means for requesting user-acknowledgment of said resultant model;

means for receiving said user-acknowledgment as input to the system; and

means for receiving a repeated data input.

41. A computer system as claimed in claim 36 wherein said data input comprises an audio input.