Handwriting and speech recognizer using neural network with separate start and continuation output scores

• US 6,393,395 B1
• Filed: 01/07/1999
• Issued: 05/21/2002
• Est. Priority Date: 01/07/1999
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Pittman, James A., Guha, Angshuman, Haluptzok, Patrick M.
• Primary Examiner(s): {haeck over (S)}mits, Ta̅livaldis Ivars
• Application Number:
  US09/227,170
• Time in Patent Office: 1,230 Days
• Field of Search: 704/232, 704/254, 704/253, 382/186, 382/187
• US Class Current: 704/232
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/1423 the instrument generating sequences of position coordinates corresponding to handwriting preprocessing or recognising digital ink G06V30/32
• CPC Class Codes: G06V 30/2272 with lexical matching
• CPC Class Codes: G06V 30/268 Lexical context

Abstract

A method and system for recognizing user input information including cursive handwriting and spoken words. A time-delayed neural network having an improved architecture is trained at the word level with an improved method, which, along with preprocessing improvements, results in a recognizer with greater recognition accuracy. Preprocessing is performed on the input data and, for example, may include resampling the data with sample points based on the second derivative to focus the recognizer on areas of the input data where the slope change per time is greatest. The input data is segmented, featurized and fed to the time-delayed neural network which outputs a matrix of character scores per segment. The neural network architecture outputs a separate score for the start and the continuation of a character. A dynamic time warp (DTW) is run against dictionary words to find the most probable path through the output matrix for that word, and each word is assigned a score based on the least costly path that can be traversed through the output matrix. The word (or words) with the overall lowest score (or scores) are returned. A DTW is similarly used in training, whereby the sample ink only need be labeled at the word level.

Claims

1. A method for recognizing user input data, comprising:

segmenting the user input data into a plurality of segments;

for each segment, inputting segment information corresponding to the user input data into a neural network, the neural network outputting, for each character of a plurality of possible characters, a first score corresponding to a probability that the segment information represents the start of the character and a second score corresponding to a probability that the segment information represents the continuation of the character from a previous segment;

generating an output matrix from first and second sets of scores for the plurality of segments; and

using the first and second sets of scores in the matrix for the segments to determine paths therethrough corresponding to words and scores for the words, and returning at least one word based on a determined score thereof.

2. The method of claim 1 wherein the user input data is phoneme information representing speech.

3. The method of claim 1 further comprising partitioning the user data into proposed words.

4. The method of claim 1 wherein the output matrix further includes at least one set of scores for a space character.

5. The method of claim 1 further comprising smoothing the user data.

6. The method of claim 1 further comprising resampling the user data.

7. The method of claim 5 wherein resampling the user data comprises separating the input data into a number of sections, and selecting a number of sample points to represent the input data in each section based on the second derivative of the input data in that section.

8. The method of claim 1 further comprising featurizing the user input data into feature values.

9. The method of claim 8 wherein inputting segment information corresponding to the user input data into the neural network includes inputting the feature values into the neural network.

10. The method of claim 8 wherein featurizing the user input data into feature values includes identifying delayed strokes.

11. The method of claim 1 wherein the user input data is electronic ink representing cursive handwriting.

12. The method of claim 11 wherein segmenting the user input data into a plurality of segments includes segmenting electronic ink information into distinct segments based on the y-coordinate minima thereof.

13. The method of claim 12 further comprising featurizing the electronic ink information for each segment based on characteristics thereof.

14. The method of claim 13 wherein the ink is featurized into a number of feature values including values based on coefficients of a Chebyshev polynomial representing ink information in the segment.

15. The method of claim 13 wherein inputting segment information corresponding to the user input data into the neural network includes inputting the feature values into the neural network.

16. The method of claim 1 wherein using the first and second sets of scores comprises, finding a path through the first and second sets of scores for the segments corresponding to a lowest cost.

17. The method of claim 1 wherein using the first and second sets of scores comprises, selecting a word from a dictionary, and determining a path through the first and second sets of scores for the segments corresponding to a lowest cost for the word.

18. The method of claim 17 further comprising assigning a score to the word based on the lowest cost path through the first and second sets of scores for the segments.

19. The method of claim 1 wherein using the first and second sets of scores comprises, selecting words from a dictionary, determining a path through the first and second sets of scores for the segments corresponding to a lowest cost for each word, assigning a score to each word based on the lowest cost path through the first and second sets of scores for the segments for that word, and returning at least one word based on the score assigned thereto relative to the scores assigned to other words.

20. The method of claim 1 wherein inputting segment information comprises inputting a plurality of segmented words into the neural network, and wherein returning at least one word comprises returning a plurality of words.

21. A computer-readable medium having computer-executable instructions for performing the method of claim 1.

22. The method of claim 1 wherein the output matrix is generated by the neural network.

23. The method of claim 1 wherein using the first and second sets of scores comprises, mathematically combining at least some of the first and second sets of scores for one segment with at least some of the first and second sets of scores for another segment.

24. A method for training a neural network to convert user input to strings of characters, comprising, setting the neural network with initially random weights, receiving ink for at least one sample word, each sample word having a word label associated therewith, featurizing the ink into a number of features values, inputting the feature values into the neural network, computing a dynamic time warp matrix for each word based on the characters in its word label, finding an optimal path back through the dynamic time warp matrix, and setting the neural network output to a first value for each output that corresponds to the path and to a second value for each output that does not correspond to the path, the neural network output including character start and character continuation values.

25. A computer-readable medium having computer-executable instructions for performing the method of claim 24.

26. A system for recognizing user input data, comprising:

a neural network configured to receive information corresponding to segments of user input data and to output scores for a plurality of possible characters for each segment, including for each possible character a first score corresponding to a probability that the information of that segment represents the start of the character and a second score corresponding to a probability that the information of that segment represents the continuation of the character from a previous segment;

an output matrix of the scores for the segments; and

a mechanism that uses the output matrix to determine paths therethrough corresponding to words and scores for the words, and returns at least one word based on the determined score thereof.

27. The system of claim 26 wherein the mechanism that uses the output matrix comprises a dynamic time warp.

28. The system of claim 26 wherein the user input data is phoneme information representing speech.

29. The system of claim 26 wherein the user input data comprises a plurality of words.

30. The system of claim 26 wherein the output matrix includes at least one set of scores for a space character.

31. The system of claim 26 further comprising a mechanism for smoothing the user data and a mechanism for resampling the user data.

32. The system of claim 31 wherein the mechanism for resampling the user data comprises means for separating the input data into the segments, and for selecting a number of sample points to represent the input data in each segment based on the second derivative of the input data in that segment.

33. The system of claim 26 further comprising a mechanism for segmenting the user input data into the segments, and a mechanism for featurizing the user input data into feature values.

34. The system of claim 33 wherein the information received by the neural network includes the feature values.

35. The system of claim 26 further comprising a dictionary, wherein the mechanism that uses the output matrix selects a word from the dictionary, and determines a path through the output matrix corresponding to a lowest cost for the word.

36. The system of claim 26 wherein the mechanism that uses the output matrix mathematically combines at least one score in the first and second sets of scores for one segment with at least one score in the first and second sets of scores for another segment.