Patent US5819247A successfully refreshed from Google Patents.
US5819247A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Apparatus and methods for machine learning hypotheses
Assignee: Nokia of America Corp
•
Filing: 1997-07-29
•
Granted: 1998-10-06
•
Expires: 2017-07-29
Abstract
Abstract Apparatus and methods for machine learning the hypotheses used in the classifier component of pattern classification devices such as OCRs, other image analysis systems, and and text retrieval systems. The apparatus and methods employ machine learning techniques for generating weak hypotheses from a set of examples of the patterns to be recognized and then evaluate the resulting hypothesis against example patterns. The results of the evaluation are used to increase the probability that the examples used to generate the next weak hypothesis are ones which the previous weak hypothesis did not correctly classify. The results of the evaluation are also used to give a weight to each weak hypothesis. A strong hypothesis is then made by combining the weak hypotheses according to their weights.
Inventors
- 👤 Yoav Freund
- 👤 Robert Elias Schapire
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 10:53
CPC Classifications
G; G06; G06N; G06N3/00; G06N3/02; G06N3/08; G06F; G06F18/00; G06F18/20; G06F18/21; G06F18/214; G06N20/00; G06N3/04; G06N3/0499; G06N3/09; G06V; G06V30/00; G06V30/10; G06V30/19; G06V30/191; G06V30/19147
Claims Analysis
Total Claims: 31
Claim 1
Independent Claim
150 words
Apparatus for automatically generating a hypothesis to classify a set of examples for pattern recognition, the apparatus comprising: input means for receiving the set of examples to be classified, the set of examples comprising machine-readable symbols; learning means for receiving a subset of the set of examples and generating weak hypotheses therefrom; evaluation means for evaluating the weak hypotheses during generation of the weak hypotheses and providing a selection feedback based on the evaluation, the evaluation means outputting a weighting feedback to the learning means based on the evaluation, the learning means assigning weights to the weak hypotheses in response to the weighting feedback and generating the hypothesis by combining the weak hypotheses according to the weights assigned thereto; subset selection means responsive to the selection feedback for selecting a next subset of the set of examples; and determination means for classifying the set of examples based on the hypothesis.
Claim 2
Dependent Claim
150 words
Apparatus for automatically generating a hypothesis to classify a set of examples for pattern recognition, the apparatus comprising: input means for receiving the set of examples to be classified, the set of examples comprising machine-readable symbols; learning means for receiving a subset of the set of examples and generating weak hypotheses therefrom; evaluation means for evaluating the weak hypotheses during generation of the weak hypotheses and providing a selection feedback based on the evaluation, the evaluation means outputting a weighting feedback to the learning means based on the evaluation, the learning means assigning weights to the weak hypotheses in response to the weighting feedback and generating the hypothesis by combining the weak hypotheses according to the weights assigned thereto; subset selection means responsive to the selection feedback for selecting a next subset of the set of examples; and determination means for classifying the set of examples based on the hypothesis.
Claim 3
Dependent Claim
28 words
The apparatus set forth in claim 1 wherein: the evaluation means receives evaluation examples of the examples to be classified and evaluates the hypothesis against the evaluation examples.
Claim 4
Dependent Claim
49 words
The apparatus set forth in claim 1 wherein: the subset selection means responds to the feedback by selecting subsequent examples from the subset such that there is an increased probability that the hypothesis will not correctly classify the subsequent examples at the time the subset selection means selects them.
Claim 5
Independent Claim
45 words
The apparatus set forth in any of claims 1, 2, or 3 wherein: the hypothesis includes a plurality of hypothesis examples from the set of examples; and the learning means generates the hypothesis by adding selected ones of the hypothesis examples from the subset thereto.
Claim 6
Dependent Claim
41 words
The apparatus set forth in claim 4 wherein: the evaluation means determines whether addition of each of the examples to the hypothesis improves the hypothesis, and the learning means selects the examples to add to the hypothesis which improve the hypothesis.
Claim 7
Independent Claim
36 words
The apparatus set forth in any of claims 1, 2, or 3, further comprising a neural network, and wherein: the neural network generates the hypothesis; and the learning means trains the neural network on the subset.
Claim 8
Dependent Claim
118 words
Apparatus for automatically generating a hypothesis to classify a set of examples of items for pattern recognition, the apparatus comprising: input means for receiving the set of examples to be classified, the set of examples comprising machine-readable symbols; learning means for receiving a subset of the set of examples and generating weak hypotheses therefrom; evaluation means for evaluating the weak hypotheses during generation of the weak hypotheses and providing a weighting feedback based on the evaluation; means responsive to the weighting feedback for assigning a weight to each of the weak hypotheses; subset selection means for selecting a next subset of the set of examples; and determination means for classifying the set of examples based on the hypothesis.
Claim 9
Dependent Claim
118 words
Apparatus for automatically generating a hypothesis to classify a set of examples of items for pattern recognition, the apparatus comprising: input means for receiving the set of examples to be classified, the set of examples comprising machine-readable symbols; learning means for receiving a subset of the set of examples and generating weak hypotheses therefrom; evaluation means for evaluating the weak hypotheses during generation of the weak hypotheses and providing a weighting feedback based on the evaluation; means responsive to the weighting feedback for assigning a weight to each of the weak hypotheses; subset selection means for selecting a next subset of the set of examples; and determination means for classifying the set of examples based on the hypothesis.
Claim 10
Independent Claim
124 words
A method of automatically generating a hypothesis to classify a set of examples for pattern recognition, the method comprising the steps of: inputting the set of examples to be classified, the set of examples comprising machine-readable symbols; receiving a subset of the set of examples and generating weak hypotheses therefrom; evaluating the weak hypotheses during generation of the weak hypotheses and providing a selection feedback based on the evaluation, and outputting a weighting feedback based on the evaluation; assigning weights to the weak hypotheses in response to the weighting feedback; generating the hypotheses by combining the weak hypotheses according to the weights assigned thereto; selecting a next subset in response to the selection feedback; and classifying the set of examples based on the hypotheses.
Claim 11
Independent Claim
124 words
A method of automatically generating a hypothesis to classify a set of examples for pattern recognition, the method comprising the steps of: inputting the set of examples to be classified, the set of examples comprising machine-readable symbols; receiving a subset of the set of examples and generating weak hypotheses therefrom; evaluating the weak hypotheses during generation of the weak hypotheses and providing a selection feedback based on the evaluation, and outputting a weighting feedback based on the evaluation; assigning weights to the weak hypotheses in response to the weighting feedback; generating the hypotheses by combining the weak hypotheses according to the weights assigned thereto; selecting a next subset in response to the selection feedback; and classifying the set of examples based on the hypotheses.
Claim 12
Independent Claim
112 words
A method of automatically generating a hypothesis to classify a set of examples for pattern recognition, the method comprising the steps of: inputting the set of examples to be classified, the set of examples comprising machine-readable symbols; receiving a subset of the set of examples and generating weak hypotheses therefrom; evaluating the weak hypotheses during generation of the weak hypotheses and providing a weighting feedback based on the evaluation; assigning a weight to each of the weak hypotheses in response to the weighting feedback; generating the hypotheses by combining the weak hypotheses according to the weights assigned thereto; selecting a next subtext; and classifying the set of examples based on the hypothesis.
Claim 13
Independent Claim
112 words
A method of automatically generating a hypothesis to classify a set of examples for pattern recognition, the method comprising the steps of: inputting the set of examples to be classified, the set of examples comprising machine-readable symbols; receiving a subset of the set of examples and generating weak hypotheses therefrom; evaluating the weak hypotheses during generation of the weak hypotheses and providing a weighting feedback based on the evaluation; assigning a weight to each of the weak hypotheses in response to the weighting feedback; generating the hypotheses by combining the weak hypotheses according to the weights assigned thereto; selecting a next subtext; and classifying the set of examples based on the hypothesis.
Claim 14
Dependent Claim
31 words
Apparatus for classifying items of data using a hypothesis, the apparatus having the improvement wherein: the hypothesis is made by the method of claim 8 or the method of claim 9.
Claim 15
Dependent Claim
19 words
The apparatus set forth in claim 1 wherein the machine-readable symbols comprise symbols reproduced from pattern-bearing signals or media.
Claim 16
Dependent Claim
28 words
The apparatus set forth in claim 11 wherein the examples comprise scanned alphanumeric images, and the classification assigns an alphanumeric character for each image according to the hypothesis.
Claim 17
Dependent Claim
19 words
The apparatus set forth in claim 7 wherein the machine-readable symbols comprise symbols reproduced from pattern-bearing signals or media.
Claim 18
Dependent Claim
28 words
The apparatus set forth in claim 13 wherein the examples comprise scanned alphanumeric images, and the classification assigns an alphanumeric character for each image according to the hypothesis.
Claim 19
Dependent Claim
19 words
The method set forth in claim 8 wherein the machine-readable symbols comprise symbols reproduced from pattern-bearing signals or media.
Claim 20
Dependent Claim
30 words
The method set forth in claim 15 further comprising the steps of: scanning alphanumeric images as the examples; and assigning an alphanumeric character for each image, according to the hypothesis.
Claim 21
Dependent Claim
19 words
The method set forth in claim 9 wherein the machine-readable symbols comprise symbols reproduced from pattern-bearing signals or media.
Claim 22
Dependent Claim
30 words
The method set forth in claim 17 further comprising the steps of: scanning alphanumeric images as the examples; and assigning an alphanumeric character for each image, according to the hypothesis.
Claim 23
Dependent Claim
129 words
An optical character recognition apparatus, comprising: optical input means for receiving a set of examples to be classified, the set of examples comprising machine-readable symbols; processing means, the processing means being programmed to execute character recognition, and comprising; learning means for receiving a subset of the set of examples and generating weak hypotheses therefrom; evaluation means for evaluating the weak hypotheses during generation of the weak hypotheses and providing a selection feedback based on the evaluation, and generating a weighting feedback, the evaluation means generating the hypotheses by combining the weak hypotheses according to the weights assigned thereto; subset selection means responsive to the selection feedback for selecting a next subset of the set of examples; and determination means for classifying the set of examples according to the hypothesis.
Claim 24
Dependent Claim
129 words
An optical character recognition apparatus, comprising: optical input means for receiving a set of examples to be classified, the set of examples comprising machine-readable symbols; processing means, the processing means being programmed to execute character recognition, and comprising; learning means for receiving a subset of the set of examples and generating weak hypotheses therefrom; evaluation means for evaluating the weak hypotheses during generation of the weak hypotheses and providing a selection feedback based on the evaluation, and generating a weighting feedback, the evaluation means generating the hypotheses by combining the weak hypotheses according to the weights assigned thereto; subset selection means responsive to the selection feedback for selecting a next subset of the set of examples; and determination means for classifying the set of examples according to the hypothesis.
Claim 25
Dependent Claim
26 words
The apparatus of claim 19 wherein: the evaluation means receives evaluation examples of the examples to be classified and evaluates the hypothesis against the evaluation examples.
Claim 26
Dependent Claim
48 words
The apparatus of claim 20 wherein: the subset selection means responds to the selection feedback by selecting subsequent examples from the subset such as there is an increased probability that the hypothesis will not correctly classify the subsequent examples at the time the subset selection means selects them.
Claim 27
Dependent Claim
39 words
The apparatus of claim 19 wherein: the hypothesis includes a plurality of hypotheses examples from the subset of the examples; and the learning means generates the hypothesis by adding selected ones of the hypothesis examples from the subset thereto.
Claim 28
Dependent Claim
39 words
The apparatus of claim 22 wherein: the evaluation means determines whether the addition of each of the examples to the hypothesis improves the hypothesis; and the learning means selects the examples to add the hypothesis to improve the hypothesis.
Claim 29
Dependent Claim
22 words
The apparatus of claim 19, further comprising memory means, the memory means storing the hypothesis and the set of examples during generation.
Claim 30
Dependent Claim
28 words
The apparatus of claim 24, wherein the memory means comprises a read-only memory imbedded in the optical character recognition apparatus; and the read-only memory stores predetermined hypothesis information.
Claim 31
Dependent Claim
29 words
The apparatus of claim 19 further comprising a neural network, and wherein: the neural network generates the hypothesis; and the learning means trains the neural network on the subsets.
References Cited (Backward Citations)
US5479575A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-10-05 | 2002-04-06 | 2002-10-06 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-10-05 | 2006-04-06 | 2006-10-06 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-10-05 | 2010-04-06 | 2010-10-06 | $7700.00 | Window Closed / Lapsed |