Distance Metric Learning for Large Margin Nearest Neighbor Classification
Distance Metric Learning for Large Margin Nearest Neighbor Classification
Nearest Neighbor Classification)
假设
首先作者基于了以下的假设:对于输入的任意样本 x i x_i xi 对于其相邻的K个样本,应该让与其相同类别的样本尽量靠近,而与其不同类别的样本尽量远离。根据这个假设来训练出一个模型,泛化数据的这种分布特性。
根据以上的思想,目标函数中需要定义两个惩罚项:一个用于惩罚邻近的相同类别之间的距离;一个用于惩罚邻近的不同类别之间样本的距离。
假设在训练过程中,不应该改变样本之间的这种“相邻”的关系。每个样本对应该存在一条虚拟的“Margin”与其相同的样本可以进入此“Margin”而与其不同类别的样本则应该“远离”此Margin。注意:这里的所有问题仅考虑“邻近”的场合,他是一种局部的思想而非局的考虑。
作者基于正定矩阵的凸优化问题(类似MMC); 参考了类似POLA算法,最大化margin的思想又参考了NCA能够提升KNN算法的精确度。最后提出了自己的模型:
Large margin nearest neighbor classification (LMNN)
其目标函数定义如下:
∥
L
(
x
⃗
i
−
x
⃗
l
)
∥
2
≤
∥
L
(
x
⃗
i
−
x
⃗
j
)
∥
2
+
1
\left\|\mathbf{L}\left(\vec{x}_{i}-\vec{x}_{l}\right)\right\|^{2} \leq\left\|\mathbf{L}\left(\vec{x}_{i}-\vec{x}_{j}\right)\right\|^{2}+1
∥L(x
i−x
l)∥2≤∥L(x
i−x
j)∥2+1
x ⃗ i \vec{x}_{i} x i是任意输入的样本, x ⃗ l \vec{x}_{l} x l是入侵了输入样本的“margin”的不同类别的样本。而 x ⃗ j \vec{x}_{j} x j 是和输入样本相同类别的“邻近”样本。
一个直观的理解参考下图:
从图上可以直观的看出,对于侵入“margin”的不同类别样本,会被“推”到“margin”外,而属于相同类别的邻近样本会被“拉”到“margin”内。
最后定义的损失函数:
动作“拉”所对应的损失函数:
ε
pull
(
L
)
=
∑
j
∼
i
∥
L
(
x
⃗
i
−
x
⃗
j
)
∥
2
\varepsilon_{\text {pull }}(\mathbf{L})=\sum_{j \sim i}\left\|\mathbf{L}\left(\vec{x}_{i}-\vec{x}_{j}\right)\right\|^{2}
εpull (L)=j∼i∑∥L(x
i−x
j)∥2
动作“推”所对应的损失函数:
ε
push
(
L
)
=
∑
i
,
j
∼
i
∑
l
(
1
−
y
i
l
)
[
1
+
∥
L
(
x
⃗
i
−
x
⃗
j
)
∥
2
−
∥
L
(
x
⃗
i
−
x
⃗
l
)
∥
2
]
+
\varepsilon_{\text {push }}(\mathbf{L})=\sum_{i, j \sim i} \sum_{l}\left(1-y_{i l}\right)\left[1+\left\|\mathbf{L}\left(\vec{x}_{i}-\vec{x}_{j}\right)\right\|^{2}-\left\|\mathbf{L}\left(\vec{x}_{i}-\vec{x}_{l}\right)\right\|^{2}\right]_{+}
εpush (L)=i,j∼i∑l∑(1−yil)[1+∥L(x
i−x
j)∥2−∥L(x
i−x
l)∥2]+
最后合并的损失函数:
ε
(
L
)
=
(
1
−
μ
)
ε
pull
(
L
)
+
μ
ε
push
(
L
)
\varepsilon(\mathbf{L})=(1-\mu) \varepsilon_{\text {pull}}(\mathbf{L})+\mu \varepsilon_{\text {push}}(\mathbf{L})
ε(L)=(1−μ)εpull(L)+μεpush(L)
凸优化问题
观察一下目标函数:
ε
(
M
)
=
(
1
−
μ
)
∑
i
,
j
∼
i
D
M
(
x
⃗
i
,
x
⃗
j
)
+
μ
∑
i
,
j
∼
i
∑
l
(
1
−
y
i
l
)
[
1
+
D
M
(
x
⃗
i
,
x
⃗
j
)
−
D
M
(
x
⃗
i
,
x
⃗
l
)
]
+
\varepsilon(\mathbf{M})=(1-\mu) \sum_{i, j \sim i} \mathcal{D}_{\mathbf{M}}\left(\vec{x}_{i}, \vec{x}_{j}\right)+\mu \sum_{i, j \sim i} \sum_{l}\left(1-y_{i l}\right)\left[1+\mathcal{D}_{\mathbf{M}}\left(\vec{x}_{i}, \vec{x}_{j}\right)-\mathcal{D}_{\mathbf{M}}\left(\vec{x}_{i}, \vec{x}_{l}\right)\right]_{+}
ε(M)=(1−μ)i,j∼i∑DM(x
i,x
j)+μi,j∼i∑l∑(1−yil)[1+DM(x
i,x
j)−DM(x
i,x
l)]+
很显然他是一个基于半正定矩阵限制条件的凸优化问题(semidefinite programming SDP)
因为有时候不一定能严格满足上述的那种条件,因此引入一个松弛变量 ξ i j l \xi_{i j l} ξijl,可以得到:
Minimize
(
1
−
μ
)
∑
i
,
j
∼
i
(
x
⃗
i
−
x
⃗
j
)
⊤
M
(
x
⃗
i
−
x
⃗
j
)
+
μ
∑
i
,
j
→
i
,
l
(
1
−
y
i
l
)
ξ
i
j
l
(1-\mu) \sum_{i, j \sim i}\left(\vec{x}_{i}-\vec{x}_{j}\right)^{\top} \mathbf{M}\left(\vec{x}_{i}-\vec{x}_{j}\right)+\mu \sum_{i, j \rightarrow i, l}\left(1-y_{i l}\right) \xi_{i j l}
(1−μ)∑i,j∼i(x
i−x
j)⊤M(x
i−x
j)+μ∑i,j→i,l(1−yil)ξijl subject to:
(1)
(
x
⃗
i
−
x
⃗
l
)
⊤
M
(
x
⃗
i
−
x
⃗
l
)
−
(
x
⃗
i
−
x
⃗
j
)
⊤
M
(
x
⃗
i
−
x
⃗
j
)
≥
1
−
ξ
i
j
l
\left(\vec{x}_{i}-\vec{x}_{l}\right)^{\top} \mathbf{M}\left(\vec{x}_{i}-\vec{x}_{l}\right)-\left(\vec{x}_{i}-\vec{x}_{j}\right)^{\top} \mathbf{M}\left(\vec{x}_{i}-\vec{x}_{j}\right) \geq 1-\xi_{i j l}
(x
i−x
l)⊤M(x
i−x
l)−(x
i−x
j)⊤M(x
i−x
j)≥1−ξijl
(2)
ξ
i
j
l
≥
0
\xi_{i j l} \geq 0
ξijl≥0
(3)
M
⪰
0
\mathbf{M} \succeq 0
M⪰0
通常可以使用标准的SDP solver解决。
然而因为松弛变量 ξ i j l \xi_{i j l} ξijl 是一个很稀疏的矩阵,作者提出了一个自己优化实现的solver 。
能量分类器(energy-based classifier)
基于Mahalabonis Metric的矩阵M可用于KNN算法来解决分类问题,然而也可以使用3小节中的等式来作为分类问题,也叫作“能量分类器”。
对于一个测试样本
x
⃗
t
\vec{x}_{t}
x
t 和它所对应的标签
y
t
{y}_{t}
yt ,选取其K个邻近的样本(这里可以根据初始的欧几里得距离来选择)对于一个给定的mahalanobis metric矩阵M计算3小节的损失函数中的第一项;接着再对第二项计算测试样本的所有impostor(和它不同类别切距离在margin内的邻近样本)的hinge loss。最后测试样本的类别能根据以下等式得到:
y
t
=
argmin
y
t
{
(
1
−
μ
)
∑
j
∼
t
D
M
(
x
⃗
t
,
x
⃗
j
)
+
μ
∑
j
∼
t
,
l
(
1
−
y
t
l
)
[
1
+
D
M
(
x
⃗
t
,
x
⃗
j
)
−
D
M
(
x
⃗
t
,
x
⃗
l
)
]
+
+
μ
∑
i
,
j
∼
i
(
1
−
y
i
t
)
[
1
+
D
M
(
x
⃗
i
,
x
⃗
j
)
−
D
M
(
x
⃗
i
,
x
⃗
t
)
]
+
}
\left.\begin{array}{rl} y_{t}=\operatorname{argmin}_{y_{t}}\left\{(1-\mu) \sum_{j \sim t} \mathcal{D}_{\mathrm{M}}\left(\vec{x}_{t}, \vec{x}_{j}\right)\right. & +\mu \sum_{j \sim t, l}\left(1-y_{t l}\right)\left[1+\mathcal{D}_{\mathrm{M}}\left(\vec{x}_{t}, \vec{x}_{j}\right)-\mathcal{D}_{\mathrm{M}}\left(\vec{x}_{t}, \vec{x}_{l}\right)\right]_{+} \\ & +\mu \sum_{i, j \sim i}\left(1-y_{i t}\right)\left[1+\mathcal{D}_{\mathrm{M}}\left(\vec{x}_{i}, \vec{x}_{j}\right)-\mathcal{D}_{\mathrm{M}}\left(\vec{x}_{i}, \vec{x}_{t}\right)\right]_{+} \end{array}\right\}
yt=argminyt{(1−μ)∑j∼tDM(x
t,x
j)+μ∑j∼t,l(1−ytl)[1+DM(x
t,x
j)−DM(x
t,x
l)]++μ∑i,j∼i(1−yit)[1+DM(x
i,x
j)−DM(x
i,x
t)]+}
Reference
[1] Kilian Q. Weinberger, Lawrence K. Saul, Distance Metric Learning for Large Margin Nearest Neighbor Classification, Journal of Machine Learning Reserach 10 207-244