System and method facilitating pattern recognition

• US 7,016,529 B2
• Filed: 03/15/2002
• Issued: 03/21/2006
• Est. Priority Date: 03/15/2002
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Platt, John C., Simard, Patrice Y., Steinkraus, David Willard
• Primary Examiner(s): Mehta, Bhavesh M.
• Assistant Examiner(s): Strege, John
• Application Number:
  US10/099,388
• Publication Number:
  US 20030174881A1
• Time in Patent Office: 1,467 Days
• Field of Search: 382/155, 382/156, 382/157, 382/159, 382/160, 382/181, 382/182, 382/185, 382/186, 382/187, 382/190, 382/224, 382/161, 700/47, 700/48, 706/15, 706/20, 706/16
• US Class Current: 382/155
• CPC Class Codes: G06V 10/454 Integrating the filters into a hierarchical structure, e.g. convolutional neural networks [CNN]
• CPC Class Codes: G06V 30/287 of Kanji, Hiragana or Katakana characters
• CPC Class Codes: G06V 30/36 Matching; Classification

Abstract

A system and method facilitating pattern recognition is provided. The invention includes a pattern recognition system having a convolutional neural network employing feature extraction layer(s) and classifier layer(s). The feature extraction layer(s) comprises convolutional layers and the classifier layer(s) comprises fully connected layers. The pattern recognition system can be trained utilizing a calculated cross entropy error. The calculated cross entropy error is utilized to update trainable parameters of the pattern recognition system.

Claims

1. A pattern recognition system, comprising:

a preprocessing component that receives an input and provides an output pattern;

at least one convolutional layer that receives the output pattern from the preprocessing component, the convolutional layer comprising a plurality of feature maps, the feature map including a weighted set of trainable parameters, the feature map sub-sampling every other position of at least a portion of the output pattern with the weighted set of trainable parameters utilized for the position sub-sampled and a next two adjacent positions in all dimensions, the at least one convolutional layer providing outputs associated with features extracted from the output pattern; and

,

at least one fully connected layer that receives outputs from the at least one convolutional layer, the at least one fully connected layer classifying the features extracted by the at least one convolutional layer, the at least one fully connected layer providing a plurality of outputs, the output comprising a probability associated with a class, the pattern recognition system trained utilizing cross entropy error minimization based at least in part, upon the equation $E=-\underset{n}{\sum <br><br>}<br><br>\underset{k=1}{\overset{c}{\sum <br><br>}}<br><br>\left\{t_k^n<br><br><br><br>\ln \left(y_k^n\right)+\left(1-t_k^n\right)<br><br><br><br>\ln \left(1-y_k^n\right)\right\}$

where E is the energy to be minimized, n indexes a pattern, t is the target value, y_kⁿ is the pattern recognition output on unit k for pattern n, and k indexes the classes.

2. The pattern recognition system of claim 1, the trainable parameters for the feature map being equal.

3. The pattern recognition system of claim 1 trained using a stochastic gradient descent algorithm.

4. The pattern recognition system of claim 1 trained to recognize one stroke Asian characters.

5. The pattern recognition system of claim 1 trained to recognize two stroke Asian characters.

6. The pattern recognition system of claim 1 trained to recognize one stroke Japanese characters.

7. The pattern recognition system of claim 1 trained to recognize two stroke Japanese characters.

8. The pattern recognition system of claim 1 trained to a plurality of ASCII characters.

9. A pattern recognition system, comprising:

a preprocessing component that receives an input and provides a bitmap output pattern;

a first convolutional layer that receives the bitmap output pattern from the preprocessing component, the first convolutional layer comprising a plurality of first feature maps, the first feature map including a first weighted set of trainable parameters, the first feature map sub-sampling every other position of at least a portion of the bitmap output pattern with the first weighted set of trainable parameters utilized for the position sub-sampled and a next two adjacent positions in all dimensions, the first feature maps providing outputs associated with first features extracted from the bitmap output pattern;

a second convolutional layer that receives the outputs of the first feature maps, the second convolutional layer comprising a plurality of second feature maps, the second feature map including a second weighted set of trainable parameters, the second feature map sub-sampling every other position of at least a portion of the outputs of the first feature map with the second weighted set of trainable parameters utilized for the position sub-sampled and a next two adjacent positions in all dimensions, the second feature maps providing outputs associated with second features;

a first fully connected layer that classifies the outputs of the second feature maps, the first fully connected layer providing outputs; and

a second fully connected layer that classifies the outputs of the first fully connected layer, the second fully connected layer providing a plurality of outputs, the output comprising a probability associated with a class, the pattern recognition system trained utilizing cross entropy error minimization based at least in part, upon the equation $E=-\underset{n}{\sum <br><br>}<br><br>\underset{k=1}{\overset{c}{\sum <br><br>}}<br><br>\left\{t_k^n<br><br><br><br>\ln \left(y_k^n\right)+\left(1-t_k^n\right)<br><br><br><br>\ln \left(1-y_k^n\right)\right\}$

where E is the energy to be minimized, n indexes a pattern, t is the target value, y_kⁿ is the pattern recognition output on unit k for pattern n, and k indexes the classes.

10. The pattern recognition system of claim 9, the first convolutional layer comprising five first feature maps.

11. The pattern recognition system of claim 10, the first feature map receiving 156 inputs.

12. The pattern recognition system of claim 9, the second convolutional layer comprising fifty second feature maps.

14. The pattern recognition system of claim 9, the first fully connected layer comprising one hundred hidden units.

15. The pattern recognition system of claim 9, the first trainable parameters for a first feature map being equal.

16. The pattern recognition system of claim 9 trained using stochastic gradient descent algorithm.

17. The pattern recognition system of claim 9 trained to recognize one stroke Asian characters.

18. The pattern recognition system of claim 9 trained to recognize two stroke Asian characters.

19. The pattern recognition system of claim 9 trained to recognize one stroke Japanese characters.

20. The pattern recognition system of claim 9 trained to recognize two stroke Japanese characters.

21. The pattern recognition system of claim 9 trained to a plurality of ASCII characters.

22. A document scanner employing the pattern recognition system of claim 9.

23. An optical character recognition system employing the pattern recognition system of claim 9.

24. A personal digital assistant employing the pattern recognition system of claim 9.

25. A tablet personal computer employing the pattern recognition system of claim 9.

13. The pattern recognition system of claim 13, the second feature map receiving 25 inputs.

26. A system for training a pattern recognition system, comprising:

a pattern recognition system comprising a preprocessing component that receives an input and provides an output pattern and a convolutional neural network that receives the output pattern from the preprocessing component sub-samples every other position of at least a portion of the output pattern with a weighted set of trainable parameters utilized for the position sub-sampled and a next two adjacent positions in all dimensions, and provides a plurality of class probability outputs;

a cross entropy error calculator that calculates a cross entropy error based, at least in part, upon the plurality of class probability outputs and training class information utilizing the equation $E=-\underset{n}{\sum <br><br>}<br><br>\underset{k=1}{\overset{c}{\sum <br><br>}}<br><br>\left\{t_k^n<br><br><br><br>\ln \left(y_k^n\right)+\left(1-t_k^n\right)<br><br><br><br>\ln \left(1-y_k^n\right)\right\}$

where E is the energy to be minimized, n indexes a pattern, t is the target value, y_kⁿ is the pattern recognition output on unit k for pattern n, and k indexes the classes;

a back propagation gradient descent component that utilizes a stochastic descent algorithm to update the weighted set of trainable parameters of the pattern recognition system based, at least in part, upon the cross entropy error; and

a trainable parameter update component that updates the weighted set of trainable parameters of the pattern recognition system.

27. The system of claim 26, the back propagation gradient descent component utilizing the following equation in updating the trainable parameters:

$W_t=W_{t-1}-\mathrm{\varepsilon <br><br>}<br><br><br><br>\frac{\partial <br><br>E<br><br>\left(W\right)}{\partial <br><br>W}$

where W is a set of trainable parameters and ε

is a scalar constant.

28. A method for training a pattern recognition system, comprising:

preprocessing a training pattern utilizing a preprocessing component;

performing pattern recognition on an output pattern from the preprocessing component utilizing a pattern recognition system based, at least in part, upon a convolutional neural network having a weighted set of trainable parameters;

providing a plurality of class probability outputs based on the training pattern;

calculating a cross entropy error based, at least in part, upon the plurality of class probability outputs and information associated with the training pattern utilizing the equation $E=-\underset{n}{\sum <br><br>}<br><br>\underset{k=1}{\overset{c}{\sum <br><br>}}<br><br>\left\{t_k^n<br><br><br><br>\ln \left(y_k^n\right)+\left(1-t_k^n\right)<br><br><br><br>\ln \left(1-y_k^n\right)\right\}$

where E is the energy to be minimized, n indexes a pattern, t is the target value, y_kⁿ is the pattern recognition output on unit k for pattern n, and k indexes the classes; and

,

updating the weighted set of trainable parameters based, at least in part, upon a gradient descent algorithm utilizing the calculated cross entropy error.

29. A data packet, transmitted between two or more computer components on a computer readable medium, that facilitates training a pattern recognition system, the data packet comprising:

a data field comprising a set of trainable parameters for a pattern recognition system based, at least in part, upon a convolutional neural network, the set of trainable parameters updated based, at least in part, upon a gradient descent algorithm utilizing a calculated cross entropy error utilizing the equation $E=-\underset{n}{\sum <br><br>}<br><br>\underset{k=1}{\overset{c}{\sum <br><br>}}<br><br>\left\{t_k^n<br><br><br><br>\ln \left(y_k^n\right)+\left(1-t_k^n\right)<br><br><br><br>\ln \left(1-y_k^n\right)\right\}$

where E is the energy to be minimized, n indexes a pattern, t is the target value, y_kⁿ is the pattern recognition output on unit k for pattern n, and k indexes the classes.

30. A computer readable medium storing computer executable components of a system facilitating training of a pattern recognition, comprising:

a preprocessing component that receives an input and provides a bitmap output pattern;

a pattern recognition component comprising a convolutional neural network that receives an output pattern from the preprocessing component, sub-samples every other position of at least a portion of the output pattern with a weighted set of trainable parameters utilized for the position sub-sampled and a next two adjacent positions in all dimensions, and provides a plurality of class probability outputs;

a cross entropy error calculator component that calculates a cross entropy error based, at least in part, upon the plurality of class probability outputs and training class information utilizing the equation $E=-\underset{n}{\sum <br><br>}<br><br>\underset{k=1}{\overset{c}{\sum <br><br>}}<br><br>\left\{t_k^n<br><br><br><br>\ln \left(y_k^n\right)+\left(1-t_k^n\right)<br><br><br><br>\ln \left(1-y_k^n\right)\right\}$

where E is the energy to be minimized, n indexes a pattern, t is the target value, y_kⁿ is the pattern recognition output on unit k for pattern n, and k indexes the classes;

a back propagation gradient descent component that utilizes a stochastic gradient descent algorithm to update the weighted set of trainable parameters of the pattern recognition system based, at least in part, upon the cross entropy error; and

a trainable parameter update component that updates the weighted set of trainable parameters of the pattern recognition system.

31. A training system for a pattern recognition system, comprising:

means for accepting an input;

means for preprocessing the input;

means for outputting a preprocessed pattern;

means for performing pattern recognition utilizing a convolutional neural network that receives the preprocessed pattern, sub-samples every other position of at least a portion of the preprocessed pattern with a weighted set of trainable parameters utilized for the position sub-sampled and a next two adjacent positions in all dimensions, and provides a plurality of class probability outputs;

means for calculating a cross entropy error based, at least in part, upon the plurality of class probability outputs and training class information utilizing the equation $E=-\underset{n}{\sum <br><br>}<br><br>\underset{k=1}{\overset{c}{\sum <br><br>}}<br><br>\left\{t_k^n<br><br><br><br>\ln \left(y_k^n\right)+\left(1-t_k^n\right)<br><br><br><br>\ln \left(1-y_k^n\right)\right\}$

where E is the energy to be minimized, n indexes a pattern, t is the target value, y_kⁿ is the pattern recognition output on unit k for pattern n, and k indexes the classes; and

,

means for updating the weighted set of trainable parameters of the means for performing pattern recognition, the means for updating utilizing a stochastic gradient descent algorithm to update the trainable parameters of the pattern recognition system based, at least in part, upon the cross entropy error.