- 一，流形学习（Manifold Learning）
- 二，The LE Algorithm based On Manifold Learning
- 1，论文简介
- 2，主要思想
- 特征流形（feature mainfold）
- 标签流形（label mainfold）
流形（manifold）是对一般几何对象的总称，包括各种维度的曲线与曲面等。
流形学习（mainfold learning）则是把我们在高维空间中所观察到的数据在低维空间中重新表示。
一般的由于数据内部特征的限制，在高维空间中表示的数据会产生一些维度上得冗余，比如在平面直角坐标系中表示的单位圆，实际上就是由一堆二维点构成的。
(
1
,
0
)
(1,0)
(1,0)点在圆上，
(
0
,
1
)
(0,1)
(0,1)点也在圆上，但
(
0
,
0
)
(0,0)
(0,0)及很多点是不在这个圆上的。显然如果用二维坐标来表示，我们没有办法让这个二维坐标系的所有点都是这个圆上的点。也就是说，用二维坐标来表示这个圆其实是有冗余的。
而在极坐标的表示方法下，圆心在原点的圆，只需要一个参数就能确定：半径。
当你连续改变半径的大小，就能产生连续不断的“能被转换成二维坐标表示”的圆。所以说，实际上二维空间中的圆就是一个一维流形。
根据流形学习的特点，高维空间有冗余，低维空间没冗余，因此流形可以作为一种数据降维的方式。
传统很多算法都是用欧氏距离作为评价两个点之间的距离函数。但是仔细想想这种欧氏距离直觉上并不靠谱。比如我们想测量中国到美国有多远，可以用软尺测量地球仪上中国到美国的距离再通过比例算出距离，这时我们肯定是测量地球仪表面中国到美国的距离，而不是用一根直线，将地球仪从中国到美国洞穿，测量出一个更短的距离。流型空间上可以用欧氏距离，不代表低维流型所展开的高维空间中也可以使用欧氏距离进行衡量。只有在流型空间，用欧氏距离才有意义。
但实际上很多时候，尽管是高维空间，但出于简便，我们仍然近似使用欧氏距离。但通常来说效果都不会太好。不过我们通过一些变换，将原始的高维空间的数据映射到低维流型空间然后再用欧氏距离衡量。或者干脆用一种能够在高维空间更准确地度量距离的距离函数来替代欧氏距离。这样能取得更加合理的距离度量结果。
对于降维算法来说，如果使用传统的欧氏距离来作为距离尺度，显然会抛弃“数据的内部特征”。如果测量球面两点距离采用空间欧氏距离，那就会忽略掉“这是个球面”这个信息。
基于流形学习的标签增强技术是根据《Multi-Label Manifold Learning》这篇文章中的利用特征流形转移的局部拓扑结构和现有的逻辑标签重建得到标签流形这一部分转化而来的。
1，论文简介1，论文题目：《Multi-Label Manifold Learning》
2，论文链接：http://palm.seu.edu.cn/xgeng/files/aaai16.pdf
3，论文代码：http://palm.seu.edu.cn/xgeng/files/ML2.rar
文章提出了一种有效的多标签方法，称为ML 2 ^2 2，即多标签流形学习。特征流形用图表示，并用重叠的局部线性邻域块近似。每个块中的边权值可以用最小二乘规划过程来求得。然后利用特征流形转移的局部拓扑结构和现有的逻辑标签重构标签流形。重构标签流形可以通过二次规划过程来实现。
特征流形（feature mainfold）多标签学习的训练集可以表示为
D
=
{
(
x
i
，
y
i
)
∣
1
≤
i
≤
n
}
mathcal{D}={(pmb{x}_i，pmb{y}_i)|1≤i≤n}
D={(xxxi，yyyi)∣1≤i≤n}。给定任何实例
x
i
∈
R
d
pmb{x}_i∈mathbb{R}^d
xxxi∈Rd和逻辑标签向量
y
i
∈
{
+
1
，
−
1
}
q
pmb{y}_i∈{+1，−1}^q
yyyi∈{+1，−1}q，使用
μ
i
∈
R
d
pmb{mu}_i∈mathbb{R}^d
μμμi∈Rd来表示数字标签向量。注意，这里在逻辑标签向量中使用−1而不是0来表示与示例无关的内容。
这里采用图的方式表示特征流形，与许多基于图的学习方法一样，拓扑结构可以用图
G
=
<
V
、
E
、
W
>
mathcal{G}=
所谓局部线性，即认为在整个数据集的某个小范围内，数据是线性的，就比如虽然地球是圆的，但我们还是可以认为我们的篮球场是个平面；而这个“小范围”，最直接的办法就是k-近邻原则。
假设所有数据点的邻域都是线性的，即每个数据点可以使用其邻居的线性组合进行最优重建。因此，最小化损失函数为：
ε
(
W
)
=
∑
i
=
1
n
∣
∣
x
i
−
∑
j
≠
1
W
i
j
x
j
∣
∣
2
varepsilon(pmb{W}) = sum^n_{i = 1}||pmb{x}_i - sum_{jnot=1}W^j_ipmb{x}_j||^2
ε(WWW)=i=1∑n∣∣xxxi−j=1∑Wijxxxj∣∣2
其中
x
j
pmb{x}_j
xxxj 表示
x
i
pmb{x}_i
xxxi 的第 j 个邻居点，
∑
j
≠
1
W
i
j
x
j
sum_{jnot=1}W^j_ipmb{x}_j
∑j=1Wijxxxj 则是
x
i
pmb{x}_i
xxxi 的K近邻数据点的线性组。在大多数情况下
W
i
j
≠
W
j
i
W^j_inot=W^i_j
Wij=Wji，且对于不在
x
i
pmb{x}_i
xxxi 邻域内的
x
j
pmb{x}_j
xxxj，令其对应的
W
j
i
=
0
W^i_j = 0
Wji=0，因此
x
i
pmb{x}_i
xxxi 与
x
j
pmb{x}_j
xxxj越相似，
W
j
i
W^i_j
Wji 越大。同时对于权重系数
W
j
i
W^i_j
Wji 要进行归一化限制：
1
T
W
i
=
1
pmb{1}^mathrm{T}pmb{W}_i = 1
111TWWWi=1，其中
W
i
=
[
W
i
1
,
.
.
.
,
W
i
n
]
T
pmb{W}_i = [W_i^1, . . . , W_i^n]^mathrm{T}
WWWi=[Wi1,...,Win]T。
对上式进行格拉姆矩阵化：
ε
i
=
1
=
∣
∣
x
i
−
∑
j
≠
1
W
i
j
x
j
∣
∣
2
=
∣
∣
∑
j
≠
1
W
i
j
(
x
i
−
x
j
)
∣
∣
2
=
∑
j
≠
1
,
k
≠
1
,
j
≠
k
W
i
j
W
i
k
(
x
i
−
x
j
)
T
(
x
i
−
x
k
)
=
∑
j
≠
1
,
k
≠
1
,
j
≠
k
W
i
j
G
i
j
k
W
i
k
begin{aligned} varepsilon_{i=1} =& ||pmb{x}_i -sum_{jnot=1}W^j_ipmb{x}_j||^2\ =&||sum_{jnot=1}W^j_i(pmb{x}_i - pmb{x}_j)||^2\ =& sum_{jnot=1,knot = 1, jnot=k}W^j_iW^k_i(pmb{x}_i-pmb{x}_j)^mathrm{T}(pmb{x}_i-pmb{x}_k) \ =& sum_{jnot=1,knot = 1, jnot=k}W^j_iG_i^{jk}W^k_i end{aligned}
εi=1====∣∣xxxi−j=1∑Wijxxxj∣∣2∣∣j=1∑Wij(xxxi−xxxj)∣∣2j=1,k=1,j=k∑WijWik(xxxi−xxxj)T(xxxi−xxxk)j=1,k=1,j=k∑WijGijkWik
其中
G
i
G_i
Gi 是点
x
i
pmb{x}_i
xxxi 的局部格拉姆矩阵：
[
(
x
i
−
x
1
)
T
(
x
i
−
x
1
)
.
.
.
(
x
i
−
x
1
)
T
(
x
i
−
x
k
)
(
x
i
−
x
2
)
T
(
x
i
−
x
1
)
.
.
.
(
x
i
−
x
2
)
T
(
x
i
−
x
k
)
⋮
⋱
⋮
(
x
i
−
x
k
)
T
(
x
i
−
x
1
)
.
.
.
(
x
i
−
x
k
)
T
(
x
i
−
x
k
)
]
left[ begin{matrix} (pmb{x}_i-pmb{x}_1)^mathrm{T}(pmb{x}_i-pmb{x}_1)& . . . & (pmb{x}_i-pmb{x}_1)^mathrm{T}(pmb{x}_i-pmb{x}_k)\ (pmb{x}_i-pmb{x}_2)^mathrm{T}(pmb{x}_i-pmb{x}_1) & . . . & (pmb{x}_i-pmb{x}_2)^mathrm{T}(pmb{x}_i-pmb{x}_k)\ vdots & ddots & vdots\ (pmb{x}_i-pmb{x}_k)^mathrm{T}(pmb{x}_i-pmb{x}_1) & . . . & (pmb{x}_i-pmb{x}_k)^mathrm{T}(pmb{x}_i-pmb{x}_k) end{matrix} right]
⎣⎢⎢⎢⎡(xxxi−xxx1)T(xxxi−xxx1)(xxxi−xxx2)T(xxxi−xxx1)⋮(xxxi−xxxk)T(xxxi−xxx1)......⋱...(xxxi−xxx1)T(xxxi−xxxk)(xxxi−xxx2)T(xxxi−xxxk)⋮(xxxi−xxxk)T(xxxi−xxxk)⎦⎥⎥⎥⎤
因此，可以用最小二乘规划来求解近似值：
W
i
m
i
n
W
i
T
G
i
W
i
s
.
t
.
1
T
W
i
=
1
^{min}_{pmb{W}_i} space pmb{W}_i^mathrm{T}pmb{G}_ipmb{W}_i\ s.t.space pmb{1}^mathrm{T}pmb{W}_i = 1
WWWimin WWWiTGGGiWWWis.t. 111TWWWi=1
在计算出所有重构权值后，可以得到一个矩阵：
W
(
i
,
j
)
=
W
i
j
pmb{W}(i, j) = W_i^j
WWW(i,j)=Wij
平滑假设（Smoothness Assumption）基本思路是“近朱者赤近墨者黑”，即相似的
x
x
x 具有相同的
y
^
hat{y}
y^，其具体定义为：
1，
x
x
x 的分布不平均，在某些地方(high density region)很集中，在某些地方很分散
2，如果
x
1
x^1
x1 和
x
2
x^2
x2 在一个high density region中距离非常近，则
x
1
x^1
x1 和
x
2
x^2
x2 通过1个high density path相连、
y
^
1
=
y
^
2
hat{y}^1=hat{y}^2
y^1=y^2。
根据平滑假设，特征空间的拓扑结构可以通过局部转移到局部标签空间。因此，重构标签流形的最小化损失函数为：
Φ
(
μ
)
=
∑
i
=
1
n
∣
∣
μ
i
−
∑
j
≠
1
W
i
j
μ
j
∣
∣
2
Phi(pmb{mu}) = sum^n_{i = 1}||pmb{mu}_i - sum_{jnot=1}W^j_ipmb{mu}_j||^2
Φ(μμμ)=i=1∑n∣∣μμμi−j=1∑Wijμμμj∣∣2
并且，在这里添加了一个约束，表示数值标签符号对应的标签是否与该示例相关：
∀
1
≤
i
≤
n
,
1
≤
l
≤
q
,
y
i
l
μ
i
l
≥
λ
{forall} 1 leq i leq n, 1 leq l leq q , y_i^lmu_i^l geq lambda
∀1≤i≤n,1≤l≤q,yilμil≥λ
其中
λ
>
0
lambda > 0
λ>0。
标签分布通过使用带约束的二次规划过程进行优化生成。
在标签增强技术中，最后使用softmax对
μ
i
mu_i
μi 进行归一化。
