# US 2010/0169250 A1 · Methods and systems for transductive data classification

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2010/0169250 A1
- Document ID: US20100169250A1
- Status: Published application
- Kind: A1
- Application number: 12/721,393
- Filed: 2010-03-10
- Published: 2010-07-01
- Earliest claimed: 2006-07-12
- Assignees: Kofax, Inc.
- Inventors: Mauritius A.R. Schmidtler; Christopher K. Harris
- Web page: https://patentgrep.com/patent/US20100169250A1

## CPC

- G06N 20/00: Machine learning
- G06N 20/10: using kernel methods, e.g. support vector machines [SVM]
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS

## Abstract

A system, method, data processing apparatus, and article of manufacture are provided for classifying data. Labeled data points are received, each of the labeled data points having at least one label indicating whether the data point is a training example for data points for being included in a designated category or a training example for data points being excluded from a designated category; receiving unlabeled data points; receiving at least one predetermined cost factor of the labeled data points and unlabeled data points; training a transductive classifier using MED through iterative calculation using the at least one cost factor and the labeled data points and the unlabeled data points as training examples; applying the trained classifier to classify at least one of the unlabeled data points, the labeled data points, and input data points; and outputting a classification of the classified data points, or derivative thereof.

## Claims

### Claim 1

In a computer-based system, a method for classification of data comprising:
receiving labeled data points, each of said labeled data points having at least one label indicating whether the data point is a training example for data points for being included in a designated category or a training example for data points being excluded from a designated category;
receiving unlabeled data points;
receiving at least one predetermined cost factor of the labeled data points and unlabeled data points;
training a transductive classifier using Maximum Entropy Discrimination (MED) through iterative calculation using said at least one cost factor and the labeled data points and the unlabeled data points as training examples, wherein for each iteration of the calculations the unlabeled data point cost factor is adjusted as a function of an expected label value and a data point label prior probability is adjusted according to an estimate of a data point class membership probability;
applying the trained classifier to classify at least one of the unlabeled data points, the labeled data points, and input data points; and
outputting a classification of the classified data points, or derivative thereof, to at least one of a user, another system, and another process.

### Claim 2 (depends on 1)

The method of claim 1 wherein said function is the absolute value of the expected label of a data point.

### Claim 3 (depends on 1)

The method of claim 1 further comprising the step of receiving prior probability information of labeled and unlabeled data points.

### Claim 4 (depends on 3)

The method of claim 3 wherein said transductive classifier learns using prior probability information of the labeled and unlabeled data.

### Claim 5 (depends on 1)

The method of claim 1 comprising the further step of determining the decision function with minimal KL divergence using a Gaussian prior for the decision function parameters given the included and excluded training examples utilizing the labeled as well as the unlabeled data as learning examples according to their expected label.

### Claim 6 (depends on 1)

The method of claim 1 comprising the further step of determining the decision function with minimal KL divergence using a multinomial prior distribution for the decision function parameters.

### Claim 7 (depends on 1)

The method of claim 1 wherein the iterative step of training a transductive classifier is repeated until the convergence of data values is reached.

### Claim 8 (depends on 7)

The method of claim 7 wherein convergence is reached when the change of the decision function of the transductive classifier falls below a predetermined threshold value.

### Claim 9 (depends on 7)

The method of claim 7 wherein convergence is reached when the change of the determined expected label value falls below a predetermined threshold value.

### Claim 10 (depends on 1)

The method of claim 1 wherein the label of the included training example has a value of +1 and the label of the excluded training example has a value of −1.

### Claim 11 (depends on 1)

The method of claim 1 wherein the label of the included example is mapped to a first numeric value and the label of the excluded example to a second numeric value.

### Claim 12 (depends on 1)

The method of claim 1 further comprising:
storing the labeled data points in a memory of a computer;
storing the unlabeled data points in a memory of a computer;
storing the input data points in a memory of a computer; and
storing the at least one predetermined cost factor of the labeled data points and unlabeled data points in a memory of a computer.

### Claim 13

An article of manufacture comprising a program storage medium readable by a computer, the medium tangibly embodying one or more programs of instructions executable by a computer to perform a method of data classification comprising:
receiving labeled data points, each of said labeled data points having at least one label indicating whether the data point is a training example for data points for being included in a designated category or a training example for data points being excluded from a designated category;
receiving unlabeled data points;
receiving at least one predetermined cost factor of the labeled data points and unlabeled data points;
training a transductive classifier with iterative Maximum Entropy Discrimination (MED) calculation using said at least one stored cost factor and stored labeled data points and stored unlabeled data points as training examples wherein at each iteration of the MED calculation the unlabeled data point cost factor is adjusted as a function of an expected label value and a data point prior probability is adjusted according to an estimate of a data point class membership probability;
applying the trained classifier to classify at least one of the unlabeled data points, the labeled data points, and input data points; and
outputting a classification of the classified data points, or derivative thereof, to at least one of a user, another system, and another process.

### Claim 14 (depends on 13)

The article of manufacture of claim 13 wherein said function is the absolute value the expected label of a data point.

### Claim 15 (depends on 13)

The article of manufacture of claim 13 further comprising the step of storing prior probability information of labeled and unlabeled data points in a memory of a computer.

### Claim 16 (depends on 15)

The article of manufacture of claim 15 wherein at each iteration of the MED calculation, the prior probability information is adjusted according to an estimate of a data point class membership probability.

### Claim 17 (depends on 13)

The article of manufacture of claim 13 comprising the further step of determining the decision function with minimal KL divergence to the prior distribution of the decision function parameters given the included and excluded training examples utilizing the labeled as well as the unlabeled data as learning examples according to their expected label.

### Claim 18 (depends on 13)

The article of manufacture of claim 13 wherein the iterative step of training a transductive classifier is repeated until the convergence of data values is reached.

### Claim 19 (depends on 18)

The article of manufacture of claim 18 wherein convergence is reached when the change of the decision function of the transductive classification falls below a predetermined threshold value.

### Claim 20 (depends on 18)

The article of manufacture of claim 18 wherein convergence is reached when the change of the determined expected label value falls below a predetermined threshold value.

### Claim 21 (depends on 13)

The article of manufacture of claim 13 wherein the label of the included training example has a value of +1 and the label of the excluded training example has a value of −1.

### Claim 22 (depends on 13)

The article of manufacture of claim 13 wherein the label of the included example is mapped to a first numeric value and the label of the excluded example is a second numeric value.

### Claim 23

In a computer-based system, a method for classification of data comprising:
receiving labeled data points;
receiving unlabeled data points;
receiving at least one predetermined cost factor of the labeled data points and unlabeled data points;
training a transductive classifier using Maximum Entropy Discrimination (MED) through iterative calculation using said at least one cost factor and using the labeled data points and the unlabeled data points as training examples, wherein for each iteration of the calculations the unlabeled data point cost factor is adjusted as a function of an absolute value of an expected label value of a data point;
applying the trained classifier to classify at least one of the unlabeled data points, the labeled data points, and input data points; and
outputting a classification of the classified data points, or derivative thereof, to at least one of a user, another system, and another process.

### Claim 24 (depends on 23)

The method of claim 23, wherein a data point label prior probability is adjusted according to an estimate of a data point class membership probability.

### Claim 25 (depends on 23)

The method of claim 23, wherein the unlabeled data point cost factor is adjusted as a function of the absolute value of the expected label value of a data point according to:
|y|c
where |y| is the absolute value of an expected label value of a data point, and
c is the cost factor prior to adjustment thereof.

### Claim 26 (depends on 23)

The method of claim 23 comprising the further step of determining the decision function with minimal KL divergence using a Gaussian prior for the decision function parameters given the included and excluded training examples utilizing the labeled as well as the unlabeled data as learning examples according to their expected label.

### Claim 27 (depends on 23)

The method of claim 23 comprising the further step of determining the decision function with minimal KL divergence using a multinomial prior distribution for the decision function parameters.

### Claim 28 (depends on 23)

The method of claim 23 wherein the iterative step of training a transductive classifier is repeated until the convergence of data values is reached.

### Claim 29 (depends on 23)

The method of claim 23 wherein the label of the included example is mapped to a first numeric value and the label of the excluded example to a second numeric value.

### Claim 30 (depends on 23)

The method of claim 23 further comprising:
storing the labeled data points in a memory of a computer;
storing the unlabeled data points in a memory of a computer;
storing the input data points in a memory of a computer; and
storing the at least one predetermined cost factor of the labeled data points and unlabeled data points in a memory of a computer.
