Large margin perceptrons for document categorization
View Patent ↗A modified large margin perceptron learning algorithm (LMPLA) uses asymmetric margin variables for relevant training documents (i.e., referred to as “positive examples”) and non-relevant training documents (i.e., referred to as “negative examples”) to accommodate biased training sets. In addition, positive examples are initialized to force at least one update to the initial weighting vector. A noise parameter is also introduced to force convergence of the algorithm.
1. One or more computer-readable media having executable instructions stored thereon that, when executed, implement a method comprising:
receiving a plurality of training documents;
for each training document:
determining if the training document is a relevant document or a non-relevant document;
if the training document is a relevant training document, determining whether the relevant training document introduces an error within a first margin relative to an inner product associated with the relevant training document;
if the training document is a non-relevant training document,
determining whether the non-relevant training document introduces an error within a second margin relative to an inner product associated with the non-relevant training document;
updating a classification weighting vector based on a document vector of the training document, if the training document introduces an error; and
storing the updated classification weighting vector.
2. The one or more computer-readable media as recited in claim 1 wherein the first margin and the second margin are unequal.
3. The one or more computer-readable media as recited in claim 1 further comprising initializing the classification weighting vector based on one or more document vectors of relevant training documents from the plurality of training documents.
4. The one or more computer-readable media as recited in claim 1 further comprising introducing a noise parameter into the inner product.
5. A method comprising:
receiving a set of training documents;
if a training document is a relevant training document and the training document introduces an error within a first margin relative to an inner product associated with the training document, updating a classification weighting vector based on a document vector of the training document;
if a training document is a non-relevant training document and the training document introduces an error within a second margin relative to an inner product associated with the training document, updating the classification weighting vector based on a document vector of the training document; and
storing the updated classification weighting vector.
6. The method of claim 5 wherein the first margin and the second margin are unequal.
7. The method of claim 5 further comprising:
initializing the classification weighting vector based on one or more document vectors of relevant training documents from the training set.
8. The method of claim 5 further comprising:
introducing a noise parameter into the inner product.
9. A classification system for computing a classification weighting vector associated with a given category from a training set of training documents, the system comprising:
a training module generating document vectors from the training set and generating the classification weighting vector based at least two asymmetric margins; and
wherein the at least two asymmetric margins further comprise a first margin that is applied to relevant training documents and a second margin that is applied to non-relevant training documents.
10. The classification system of claim 9 further comprising:
a categorization module classifying an input document based on the classification weighting vector and a document vector of the input document.
11. One or more computer-readable media having executable instructions stored thereon that, when executed, implement a method comprising:
initializing a classification weighting vector based on one or more document vectors of relevant training documents;
determining whether a relevant training document introduces an error within a first margin relative to a perturbed inner product associated with the relevant training document;
determining whether a non-relevant training document introduces an error within a second margin relative to a perturbed inner product associated with the non-relevant training document; and
for each training document that introduces an error, updating the classification weighting vector based on a document vector of the training document.
12. The one or more computer-readable media as recited in claim 11 , further comprising: introducing a noise parameter into the perturbed inner product.
13. A method comprising:
receiving a set of training documents;
initializing a classification weighting vector based on one or more document vectors of relevant training documents from the training set;
for each training document in the training set:
determining if the training document is a relevant training document or a non-relevant training document;
if the training document is a relevant training document, determining whether the relevant training document introduces an error within a first margin relative to a perturbed inner product associated with the relevant training document;
if the training document is a non-relevant training document, determining whether the non-relevant training document introduces an error within a second margin relative to a perturbed inner product associated with the non-relevant training document; and
if the training document introduces an error relative to the first or second margin, updating the classification weighting vector based on a document vector of the training document.
14. The method of claim 13 further comprising:
introducing a noise parameter into the perturbed inner product.
15. A classification system for computing a classification weighting vector associated with a given category from a training set of training documents, the system comprising:
a training module configured to:
initialize the classification weighting vector based on one or more document vectors of relevant training documents from the training set;
for each training document:
determine, if the training document introduces an error within a margin relative to a perturbed inner product associated with the training document;
updating the classification weighting vector based on a document vector of the training document if the training document introduces an error within the margin; and
wherein the margin is a first margin if the training document is a relevant training document, the margin is a second margin if the training document is a non-relevant training document, and the first margin is not equal to the second margin.
16. The classification system of claim 15 further comprising:
a categorization module configured to classify an input training document based on the classification weighting vector and a document vector of the input training document.