Learning tradeoffs between discriminative power and invariance of classifiers
Systems and methods are described for learning the discriminative power-invariance tradeoffs for classification of input data (“tradeoff learning system”). In various embodiments, the tradeoff learning system receives multiple classifiers (“base classifiers”) and employs a learning technique to produce a combined classifier. Each received base classifier achieves a different level of tradeoff. The learning technique then decreases a function of kernel weights associated with each of the received classifiers to produce the combined classifier. By decreasing the function of kernel weights, the tradeoff learning system computes a combined classifier that classifies input data more accurately than the received multiple classifiers.
1. A method performed by a computing system for learning tradeoffs between discriminative power and invariance of classifiers, comprising:
receiving two or more classifiers, each classifier for classifying data and having associated therewith a kernel with corresponding kernel weight, the kernel specifying an attribute for its associated classifier;
employing a learning technique to produce a combined classifier based on the two or more received classifiers by decreasing a function of the kernel weights to learn tradeoffs between discriminative power and invariance;
generating by the computing system a base kernel for each of the received two or more classifiers; and
selecting one of the generated base kernels by solving a convex optimization problem having a linear objective and quadratic inequality constraints.
2. The method of claim 1 wherein the employing the learning technique includes:
producing a linear combination of the generated base kernels that corresponds to the combined classifier.
3. The method of claim 1 , further comprising:
receiving an input; and
classifying the received input using the combined classifier to produce a classification for the received input wherein the produced classification produces a smaller Euclidian distance than a Euclidian distance produced by employing any of the received two or more classifiers.
4. The method of claim 1 , further comprising determining a proportion in which at least one of the received two or more classifiers should be combined.
5. The method of claim 1 wherein the employing of the learning technique minimizes a first equation subject to a second equation and a third equation, wherein the equations can be expressed as:
Minimize
w
,
d
,
ξ
1
2
w
t
w
+
C
1
t
ξ
+
σ
t
d
subject
to
y
i
(
w
t
ϕ
(
x
i
)
+
b
)
≥
1
-
ξ
i
ξ
≥
0
,
d
≥
0
,
Ad
≥
p
where
ϕ
t
(
x
i
)
ϕ
(
x
j
)
=
∑
k
d
k
ϕ
k
t
(
x
i
)
ϕ
k
(
x
j
)
.
6. The method of claim 1 wherein the employing of the learning technique includes accounting for a preference weight provided by a user.
7. The method of claim 1 , further comprising optimizing base kernel weights.
8. The method of claim 1 , further comprising determining a minimal set of invariances for the combined classifier.
9. A system for learning tradeoffs between discriminative power and invariance of classifiers, comprising:
a processor and memory;
two or more classifiers, each classifier for classifying input and having associated therewith a kernel with a corresponding kernel weight, the kernel specifying an attribute for its associated classifier;
a tradeoff learning component configured to combine the two or more classifiers to produce a combined classifier by decreasing a function of the kernel weights, wherein each classifier is a support vector machine incorporating a first tradeoff between discriminative power and invariance, and the produced combined classifier incorporates a second tradeoff between discriminative power that is different from the first tradeoff between discriminative power; and
a classifier component configured to receive an input and classifies the received input using the produced combined classifier.
10. The system of claim 9 wherein the tradeoff learning component employs a dual formulation to produce the combined classifier.
11. The system of claim 9 wherein the tradeoff learning component employs a dual formulation to produce the combined classifier, wherein the dual formulation maximizes:
Maximize
α
,
δ
1
t
α
+
p
t
δ
.
12. The system of claim 9 wherein the tradeoff learning component employs a numerical optimization package to solve a quadratic equation.
13. The system of claim 9 wherein the function of the kernel weights is an objective function.
14. The system of claim wherein the function of the kernel weights can be expressed as:
T
(
d
)
=
Min
w
,
ξ
1
2
w
t
w
+
C
1
t
ξ
+
σ
t
d
.
15. The system of claim 9 wherein the function of the kernel weights is decreased subject to a constraint and the tradeoff learning component computes a dual formulation subject to a quadratic inequality.
16. A computer-readable storage device storing computer-readable instructions that, when executed, perform a method for learning tradeoffs between discriminative power and invariance for classifiers, the method comprising:
receiving two or more classifiers, each classifier for classifying input and having associated therewith an attribute;
generating a base kernel for each of the received classifiers, the base kernel specifying a function of the attribute, each base kernel having one or more weights; and
producing a combined classifier based on at least the generated base kernels wherein the produced combined classifier classifies the input with greater precision than the received classifiers, wherein the combined classifier incorporates a tradeoff between discriminative power and invariance that is different from at least one of the received two or more classifiers.
17. The computer-readable storage device of claim 16 wherein at least one of the two or more classifiers is a support vector machine.