Fast methods of learning distance metric for classification and retrieval
View Patent ↗A nearest-neighbor-based distance metric learning process includes applying an exponential-based loss function to provide a smooth objective; and determining an objective and a gradient of both hinge-based and exponential-based loss function in a quadratic time of the number of instances using a computer.
1. A nearest-neighbor-based distance metric learning process implemented by a computer, comprising:
applying an exponential-based loss function to provide a smooth objective; and
determining an objective and a gradient of both hinge-based and exponential-based loss function in a quadratic time of the number of instances using a computer;
wherein the loss function and its gradient comprises:
l
=
E
x
,
y
∼
x
1
N
x
-
[
(
1
+
d
2
(
y
,
x
)
)
Z
x
,
y
-
∑
z
∈
Z
x
,
y
d
2
(
z
,
x
)
]
l
.
=
E
x
,
y
∼
x
1
N
x
-
∑
z
∈
Z
x
,
y
{
(
y
-
x
)
(
y
-
x
)
-
(
z
-
x
)
(
z
-
x
)
}
=
∑
x
,
v
w
x
,
v
(
v
-
x
)
(
v
-
x
)
=
X
(
S
-
W
-
W
)
X
where d is distance, x and y are data points, z is sampled from a class which x does not belong to, Z x,y is the set of data not belonging to the class of x and satifying 1+d 2 (y,x)≧d 2 (z,x), w x,v is
Z
x
,
v
NN
x
+
N
x
-
if v in the same class of x, w x,v is
-
Y
x
,
v
NN
x
+
N
x
-
if v is not in the same class as x, X is an p×N matrix whose j-th column is the feature vector of x j , W is an N×N matrix whose i,j-th element is w x i ,x j , S is an N×N diagonal matrix whose i-th diagonal element is Σ j (w ij +w ji ), NN x+ is the size of class of x, N x− is the size of data not in the class of x, and E is the expection over values x,y ˜x .
2. The method of claim 1 , using an ordered list of instances sorted by distance to determine the objective and gradient of a hinge-based loss function.
3. The method of claim 1 , comprising using a sorted order to determine the objective and gradient.
4. The method of claim 1 , comprising applying an exponential-based loss function for learning metrics.
5. The method of claim 4 , comprising using a class soft-max distance and between-class soft-min distance to determine the objective and gradient.
6. The method of claim 1 , comprising using the learned distance metric to classify, recognize or retrieve data.
7. The method of claim 1 , wherein regularization terms and constraint terms control generalization error and reduce overall error.
8. The method of claim 1 , comprising determining an exponential type of surrogate function
ψ(ξ)=ξ ρ , where ρε(0,1] where the gradient with respect to the squared distance is
∂
l
~
∂
d
ij
2
=
ρ
exp
{
(
1
-
ρ
)
δ
±
(
x
i
)
}
exp
{
ρ
(
d
ij
2
-
δ
-
(
x
i
)
)
}
NN
x
i
+
=
w
ij
,
∀
j
:
x
j
∼
x
i
∂
l
~
∂
d
ik
2
=
ρ
exp
{
(
1
-
ρ
)
δ
±
(
x
i
)
}
-
exp
{
ρ
(
δ
+
(
x
i
)
-
d
ik
2
)
}
NN
x
i
-
=
w
ik
,
∀
k
:
x
k
∖
∼
x
i
where δ + (x) is the soft-max of the square distances of all instances similar to x, and δ − (x) is the soft-min of the square distances of all instances not similar to x, ψ is a concave function, and i,j are matrix elements.
9. The method of claim 1 , comprising determining a gradient matrix as
l
∼
.
=
∑
x
i
,
x
j
w
ij
(
x
i
-
x
j
)
(
x
i
-
x
j
)
T
=
X
(
S
-
W
-
W
)
X
where X is a p×N matrix whose j-th column is the feature vector of x j , W is an N×N matrix whose i,j-th element is w ij , S is an N×N diagonal matrix whose i-th diagonal element is Σ j w ij +w ji .
10. A system to perform nearest-neighbor-based distance metric learning implemented with a computer, comprising:
means for applying an exponential-based loss function to provide a smooth objective; and
means for determining an objective and a gradient of both hinge-based and exponential-based loss function in a quadratic time of the number of instances using a computer;
wherein the loss function and its gradient comprises:
l
=
E
x
,
y
∼
x
1
N
x
-
[
(
1
+
d
2
(
y
,
x
)
)
Z
x
,
y
-
∑
z
∈
Z
x
,
y
d
2
(
z
,
x
)
]
l
.
=
E
x
,
y
∼
x
1
N
x
-
∑
z
∈
Z
x
,
y
{
(
y
-
x
)
(
y
-
x
)
-
(
z
-
x
)
(
z
-
x
)
}
=
∑
x
,
v
w
x
,
v
(
v
-
x
)
(
v
-
x
)
=
X
(
S
-
W
-
W
)
X
where d is distance, x and y are data points, z is sampled from a class which x does not belong to, Z x,y is the set of data not belonging to the class of x and satifying 1+d 2 (y,x)≧d 2 (z,x), w x,v is
Z
x
,
v
NN
x
+
N
x
-
if v in the same class of x, w x,v is
-
Y
x
,
v
NN
x
+
N
x
-
if v is not in the same class as x, X is an p×N matrix whose j-th column is the feature vector of x j , W is an N×N matrix whose i,j-th element is w x i x j , S is an N×N diagonal matrix whose i-th diagonal element is Σ j (w ij +w ji ), NN x+ is the size of class of x, N x− is the size of data not in the class of x, and E is the expection over values x, y ˜x .
11. The system of claim 10 , comprising:
means for adding regularization term to ensure the generalization error; and
means for adding trace norm constraints to ensure the generalization error.
12. The system of claim 10 , comprising means for learning metric with an exponential-based loss function and means for using class soft-max distance and between-class soft-min distance to determine the objective and gradient.
13. The system of claim 10 , comprising means for using the learned distance metric to classify, recognize or retrieve data.