# US 8,280,828 B2 · Fast and efficient nonlinear classifier generated from a trained linear classifier

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

- Number: US 8,280,828 B2
- Document ID: US8280828B2
- Status: Granted
- Kind: B2
- Application number: 12/483,391
- Filed: 2009-06-12
- Published: 2010-12-16
- Granted: 2012-10-02
- Earliest claimed: 2009-06-12
- Assignees: Xerox Corporation
- Inventors: Florent Perronnin; Jorge Sanchez
- Web page: https://patentgrep.com/patent/US8280828B2

## CPC

- G06N 20/00: Machine learning
- G06F 18/24133: {Distances to prototypes}
- G06N 20/10: using kernel methods, e.g. support vector machines [SVM]
- G06V 10/764: using classification, e.g. of video objects
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06V: IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING

## Abstract

A classifier method comprises: projecting a set of training vectors in a vector space to a comparison space defined by a set of reference vectors using a comparison function to generate a corresponding set of projected training vectors in the comparison space; training a linear classifier on the set of projected training vectors to generate a trained linear classifier operative in the comparison space; and transforming the trained linear classifier operative in the comparison space into a trained nonlinear classifier that is operative in the vector space to classify an input vector.

## Claims

### Claim 1

A method comprising:
projecting a set of training vectors in a vector space to a comparison space defined by a set of reference vectors using a comparison function to generate a corresponding set of projected training vectors in the comparison space wherein the comparison function comprises a vector element comparison for each dimension of the vector space summed over the dimensions of the vector space;
training a linear classifier on the set of projected training vectors to generate a trained linear classifier operative in the comparison space; and
transforming the trained linear classifier operative in the comparison space into a trained nonlinear classifier operative in the vector space;
wherein the projecting, the training, and the transforming are performed by a digital processing device.

### Claim 2 (depends on 1)

The method as set forth in claim 1, wherein the comparison function is selected from a group consisting of an L1 distance, a squared L2 distance, and a chi-squared distance.

### Claim 3 (depends on 1)

The method as set forth in claim 1, wherein the transforming comprises:
for a first dimension of the vector space, determining a one-dimensional function based on (i) the vector element comparison of the comparison function for the first dimension of the vector space and (ii) trained parameters of the trained linear classifier; and
repeating the determining for the remaining dimensions of the vector space.

### Claim 4 (depends on 3)

The method as set forth in claim 3, wherein the determining comprises:
for the first dimension of the vector space, determining the one-dimensional function φd as
ϕ
d
⁡
(
x
i
⁡
(
d
)
)
=
∑
m
=
1
M
⁢
w
m
·
f
d
⁡
(
x
i
⁡
(
d
)
,
r
m
⁡
(
d
)
)
where d denotes the first dimension of the vector space, xi denotes an ith training vector of the set of training vectors, M denotes the number of reference vectors in the set of reference vectors defining the comparison space, rm denotes the mth reference vector of the set of reference vectors, and ƒd denotes the vector element comparison of the comparison function for the first dimension of the vector space.

### Claim 5 (depends on 4)

The method as set forth in claim 4, wherein the determining further comprises:
constructing the trained nonlinear classifier s(xinput) operative in the vector space as
s
⁡
(
x
input
)
=
∑
d
=
1
D
⁢
ϕ
d
⁡
(
x
input
)
+
b
where xinput is an input vector to be classified, D is the dimensionality of the vector space, and b is a trained scalar parameter of the trained linear classifier.

### Claim 6 (depends on 3)

The method as set forth in claim 3, wherein the determining further comprises:
for the first dimension of the vector space, approximating the one-dimensional function by a piecewise combination of one-dimensional analytical functions; and
repeating the approximating for the one-dimensional functions of the remaining dimensions of the vector space.

### Claim 7 (depends on 6)

The method as set forth in claim 6, wherein the one-dimensional analytical functions are selected from a group consisting of (i) constant functions, (ii) linear functions, and (iii) polynomial functions.

### Claim 8 (depends on 6)

The method as set forth in claim 6, wherein the one-dimensional analytical functions define bins, and the method further comprises:
classifying an input vector in the vector space using the trained nonlinear classifier operative in the vector space, the classifying including for each dimension of the vector space evaluating only the one-dimensional analytical function defining the bin containing the input vector element, wherein the classifying is performed by the digital processing device.

### Claim 9 (depends on 1)

A computer programmed to classify an input vector using a trained nonlinear classifier operative in a vector space and generated by a method as set forth in claim 1.

### Claim 10

A method comprising:
projecting a set of training vectors in a vector space to a comparison space defined by a set of reference vectors using a comparison function to generate a corresponding set of projected training vectors in the comparison space;
training a linear classifier on the set of projected training vectors to generate a trained linear classifier operative in the comparison space; and
transforming the trained linear classifier operative in the comparison space into a trained nonlinear classifier operative in the vector space;
wherein the projecting, the training, and the transforming are performed by a digital processing device; and
wherein the set of reference vectors is selected from a group consisting of:
the set of training vectors,
the set of training vectors plus additional vectors in the vector space,
a subset of the set of training vectors plus additional vectors in the vector space, and
a set of vectors in the vector space that is disjoint from the set of training vectors.

### Claim 11 (depends on 10)

A computer programmed to classify an input vector using a trained nonlinear classifier operative in a vector space and generated by a method as set forth in claim 10.

### Claim 12

A method comprising:
projecting a set of training vectors in a vector space to a comparison space defined by a set of reference vectors using a comparison function to generate a corresponding set of projected training vectors in the comparison space;
training a linear classifier on the set of projected training vectors to generate a trained linear classifier operative in the comparison space;
transforming the trained linear classifier operative in the comparison space into a trained nonlinear classifier operative in the vector space; and
classifying an input vector in the vector space using the trained nonlinear classifier operative in the vector space;
wherein the projecting, the training, the transforming, and the classifying are performed by a digital processing device.

### Claim 13 (depends on 12)

The method as set forth in claim 12, wherein the classifying does not include projecting the input vector to the comparison space.

### Claim 14 (depends on 12)

The method as set forth in claim 12, further comprising:
generating the set of training vectors, the set of reference vectors, and the input vector from images, wherein the generating is performed by the digital processing device.

### Claim 15 (depends on 14)

The method as set forth in claim 14, wherein the set of training vectors, the set of reference vectors, and the input vector are Fisher vectors.

### Claim 16 (depends on 12)

A computer programmed to classify an input vector using a trained nonlinear classifier operative in a vector space and generated by a method as set forth in claim 12.

### Claim 17

A non-transitory computer-readable storage medium encoded with instructions executable by a digital processor to perform a method comprising (i) projecting a set of training vectors in a vector space to a comparison space defined by a set of reference vectors using a comparison function comprising a vector element comparison for each dimension of the vector space summed over the dimensions of the vector space to generate a corresponding set of projected training vectors in the comparison space, (ii) training a linear classifier on the set of projected training vectors to generate a trained linear classifier operative in the comparison space, and (iii) transforming the trained linear classifier operative in the comparison space into a trained nonlinear classifier operative in the vector space, wherein the comparison function is selected from a group consisting of an L1 distance, a squared L2 distance, and a chi-squared distance.

### Claim 18

A non-transitory computer-readable storage medium encoded with instructions executable by a digital processor to perform a method comprising (i) projecting a set of training vectors in a vector space to a comparison space defined by a set of reference vectors using a comparison function comprising a vector element comparison for each dimension of the vector space summed over the dimensions of the vector space to generate a corresponding set of projected training vectors in the comparison space, (ii) training a linear classifier on the set of projected training vectors to generate a trained linear classifier operative in the comparison space, and (iii) transforming the trained linear classifier operative in the comparison space into a trained nonlinear classifier operative in the vector space, wherein the transforming comprises determining for each dimension of the vector space a one-dimensional function based on the corresponding vector element comparison of the comparison function and trained parameters of the trained linear classifier.

### Claim 19

A system comprising:
a classifier training sub-system comprising a computer configured to perform a method including:
projecting a set of training vectors in a vector space to a comparison space defined by a set of reference vectors using a comparison function comprising a vector element comparison for each dimension of the vector space summed over the dimensions of the vector space to generate a corresponding set of projected training vectors in the comparison space,
training a linear classifier on the set of projected training vectors to generate a trained linear classifier operative in the comparison space, and
transforming the trained linear classifier operative in the comparison space into a trained nonlinear classifier operative in the vector space by determining for each dimension of the vector space a one-dimensional function based on the corresponding vector element comparison of the comparison function and trained parameters of the trained linear classifier, wherein the transforming further includes approximating each one-dimensional function by a piecewise combination of analytical functions, the outputting applying the trained linear classifier using the approximated one-dimensional functions; and
a classifier sub-system comprising a computer configured to perform a method including:
outputting a classification based on applying the trained linear classifier to a received input vector defined in the vector space;
wherein the system comprises one or more digital processors programmed to perform the projecting, training, transforming, and outputting operations.
