ADMM驱动的多标签学习：流形规范化矩阵完成方法
需积分: 10 23 浏览量
更新于2024-08-26
收藏 913KB PDF 举报
本文探讨了在多标签学习领域中利用交替方向乘子法(Alternating Direction Method of Multipliers, ADMM)实现流形正规化矩阵完成的理论与应用。多标签学习是一种广泛应用在自然语言处理、生物信息学、信息检索等多个领域的机器学习问题，目标是处理一个实例可能关联多个类别的标签情况。矩阵完成方法作为一种潜在有效的转化性多标签学习策略，通过构建一个联合矩阵来捕捉数据之间的内在关系。
矩阵完成技术的核心思想是根据部分观察到的标签对整个标签矩阵进行填充或预测，以便更好地理解数据的结构和模式。ADMM作为一种强大的优化工具，它能够将复杂的优化问题分解成更易于管理的小问题，并在求解过程中保持全局收敛性。在这篇研究论文中，作者Bin Li, Yingming Li, 和 Zenglin Xu来自中国电子科技大学和浙江大学的SMILE实验室，他们提出了一种新的方法，即结合多标签学习的需求和流形假设，利用ADMM来执行矩阵完成任务。
论文的关键点包括：
1. **流形假设**：论文假设数据分布遵循低维流形结构，即数据点在高维空间中紧密地聚类在一起，但其实质上只在低维空间中具有显著变化。这有助于减少噪声和提高模型的泛化能力。
2. **矩阵完成**：作者通过ADMM算法设计了一个优化框架，该框架能利用部分标签信息推断出完整的标签矩阵，同时考虑数据点之间的局部相似性，从而更好地适应多标签数据的复杂性。
3. **多标签学习方法**：论文提出的方法不仅解决了标签矩阵的填充问题，而且还能通过矩阵结构学习到不同类别之间的潜在关联，这在实际应用中具有重要的价值。
4. **接收与修订**：论文于2016年5月首次接收，经过多次修订后于2018年1月接受，同年2月在线发表，展示了作者们对该问题持续的研究和完善过程。
这篇研究论文提供了深入理解多标签学习中流形正规化和ADMM结合的重要见解，为实际问题中的多标签数据处理提供了一种有效的数学工具，有望推动相关领域的发展。对于那些对机器学习、矩阵优化和流形分析感兴趣的研究人员和工程师来说，这是不可或缺的一份参考资料。
B. Liu et al. / Neural Networks 101 (2018) 57–67 59
to be predicted. Given the whole set of examples and partial label
information, we hope to complete the Y
U
.
In the following, we will first model the multi-label learning
as a matrix completion problem, then enhance it with manifold
regularization for better exploiting the intrinsic manifold structure
of data, followed by the optimization process with ADMM.
3.1. Matrix completion for multilabel learning
We first introduce an intermediate instance matrix (X
0
L
, X
0
U
),
such that the observed instance matrix (X
L
, X
U
) is sampled from
(X
0
L
, X
0
U
) with i.i.d Gaussian noises: (X
L
, X
U
) = (X
0
L
+ ϵ, X
0
U
+ ϵ),
where ϵ
ij
∼ N(0, σ
2
). Correspondingly, the intermediate label
matrix (Y
0
L
, Y
0
U
) ∈ R
t×n
can be represented as a linear combination
of instance matrix under a weight matrix W ∈ R
t×d
: (Y
0
L
, Y
0
U
) =
W(X
0
L
, X
0
U
).
The joint matrix is denoted by Z = (Y
0
L
, Y
0
U
; X
0
L
, X
0
U
). Given the
linear projection W, the ranks of these two matrices (X
0
L
, X
0
U
) and Z
satisfy (Goldberg et al., 2010),
rank
(
Z
)
≤ rank((X
0
L
, X
0
U
)) + 1. (1)
Further, we construct an observed matrix M with partition of
four blocks M
L
x
, M
U
x
, M
L
y
, and M
U
y
as follows,
M =
Y
L
Y
U
X
L
X
U
=
M
L
y
M
U
y
M
L
x
M
U
x
. (2)
where the blocks X
L
= M
L
x
, X
U
= M
U
x
, Y
L
= M
L
y
, and Y
U
= M
U
y
= 0.
Obviously, matrix M has same size with Z.
According to Eq. (1), the rank of Z should be much smaller
than its attribution dimensionalities. Specifically, the estimation
of unobserved part of Z can be treated as a matrix completion
problem, which relies on minimizing the rank of Z. However, it
is very difficult to directly solve a rank minimization problem.
Fortunately, rank minimization can be relaxed as minimization of
the nuclear norm of Z, that is ∥Z∥
∗
=
k
σ
k
(Z) where σ
k
(Z) is the
kth singular value of Z (Candès & Recht, 2009; Candès & Tao, 2010).
Now with the consideration of the noises on (X
0
L
, X
0
U
) and (Y
0
L
), the
optimization problem can be formulated as follows (Cabral et al.,
2011; Goldberg et al., 2010),
min
Z
µ∥Z∥
∗
+
1
|Ω
X
|
(i,j)∈Ω
X
c
x
(z
t+i,j
, x
ij
)
+
λ
|Ω
Y
|
(i,j)∈Ω
Y
c
y
(z
ij
, y
ij
)
s. t. z
m
= 1
⊤
, m = t + d + 1,
where Ω
X
denotes the index set of observed data entries of
(X
L
, X
U
), i.e., 1 ≤ i ≤ d and 1 ≤ j ≤ n for any x
ij
, and Ω
Y
denotes the index set of known label entries of Y
L
. Note that in
the transduction setting, since all the instances are observed, Ω
X
actually refers to the indices of rows and columns of the whole
data. Here c
x
(z
t+i,j
, x
ij
) is the loss between elements of (X
L
, X
U
) and
(X
0
L
, X
0
U
), and c
y
(z
ij
, y
ij
) is the loss between the soft labels Y
0
L
and
actual labels Y
L
. In this paper, we choose the squared loss for c
x
(.),
namely c
x
(z
t+i,j
, x
ij
) =
1
2
(z
t+i,j
− x
ij
)
2
as in Goldberg et al. (2010).
For the label noise (from continuous z
ij
∈ R to y
ij
∈ {−1, +1}), we
choose c
y
(z
ij
, y
ij
) =
1
α
log(1 + exp(−αz
ij
y
ij
)) as in Eq. (14) to model
the loss (Cabral et al., 2011). This loss between soft and binary
labels is little different from the definition in Goldberg et al. (2010).
In contrast to Goldberg et al. (2010), we use the loss c
y
(.) with
an additional parameter α because it has been reported a better
performance than the sigmoid function (Cabral et al., 2011). There
are many possible ways to implement the general mapping from
the predicted soft label Z
y
to the binary label. We will state one of
the possible solution in Section 5.
3.2. Manifold regularized matrix completion
Under the setting of semi-supervised learning, a natural as-
sumption is that if two instances x
i
and x
j
are close in the in-
trinsic geometry of the data distribution, then the corresponding
predicted labels Z
i
y
and Z
j
y
are also similar to each other. This
assumption is usually referred as smoothness (or manifold) as-
sumption (Belkin & Niyogi, 2001; Bengio, Delalleau, & Le Roux,
2006; Chapelle, Schölkopf, Zien, et al., 2006; Liu, Xu, Wu, & Wang,
2016).
Suppose the mapping from the instance x
i
to its label Z
i
y
can be
denoted by a function f (x
i
) = Z
i
y
, then the smoothness of f along
the geodesics in the compact manifold of the data can be measured
as ∥f ∥
2
M
.
In reality, the data manifold is usually unknown. A symmetric
weight matrix W was defined in (Zhu, Ghahramani, Lafferty, et al.,
2003),
W
ij
= exp(−
d
m=1
(x
m
i
− x
m
j
)
2
σ
2
)
can be approximated to measure the smoothness ∥f ∥
2
M
. We further
define L = D − W , where D = diag(d
i
) is a diagonal matrix with
the d
i
=
j
W
ij
. L ∈ R
n×n
is called graph Laplacian matrix (Chung,
1997).
Therefore, we hope the prediction for Y
0
U
should keep consis-
tency with their neighbors, which motivates the choice of the
quadratic loss (Cai, He, Wu, & Han, 2008; Zhu, 2005; Zhu et al.,
2003),
E(Z
y
) =
1
2
i,j
W
ij
∥f (x
i
) − f (x
j
)∥
2
2
(3)
=
1
2
i,j
W
ij
∥Z
i
y
− Z
j
y
∥
2
2
=
i
d
i
(Z
i
y
)
2
−
i,j
W
ij
Z
i
y
Z
j
y
= Z
⊤
y
LZ
y
where ∥ · ∥
2
indicates L2 norm operation. Suppose that Z
y
=
argmin
Z
y
E(Z
y
), we find that LZ
y
= 0. The LZ
y
= (D − W)Z
y
= 0
called harmonic property, it suggests that the value of predicted
label is the average of its neighbors’ value,
Z
i
y
=
i,j
W
ij
Z
j
y
d
i
=
i,j
W
ij
Z
j
y
j
W
ij
(4)
which satisfy the manifold assumption we mentioned at the begin-
ning of this section.
The matrix form of energy term of Eq. (3) is E(Z
y
) = Tr(Z
⊤
y
LZ
y
).
In this paper, we exploit the geometrical structure of the whole
data to regularize the multi-label learning problem and transform
it as a regularization term, as shown in Eq. (5):
min
Z
∥Z∥
∗
+ Tr(Z
⊤
y
LZ
y
) (5)
s.t. C
x
(Z
x
, M
x
) = 0,
C
y
(Z
L
y
, M
L
y
) = 0.
It is used to ensure the label prediction among each class in Z
y
to
satisfy the local consistency, where Z
y
= (Y
0
L
, Y
0
U
).
Here in Eq. (5), the manifold term seems to be a ‘‘hard’’ regular-
ization over the nuclear loss, but apparently it is not. Actually, it is
a soft constraint that can be controlled by a parameter introduced
by ADMM during optimization. The details will be explained in
Section 4.3.
剩余10页未读，继续阅读
2022-09-23 上传
2021-05-23 上传
2021-03-07 上传
2021-03-08 上传
2021-03-10 上传
2020-03-31 上传
2022-07-14 上传
点击了解资源详情
weixin_38686041
- 粉丝: 2
- 资源: 952
我的内容管理
展开
最新资源
- 平尾装配工作平台运输支撑系统设计与应用
- MAX-MIN Ant System：用MATLAB解决旅行商问题
- Flutter状态管理新秀：sealed_flutter_bloc包整合seal_unions
- Pong²开源游戏：双人对战图形化的经典竞技体验
- jQuery spriteAnimator插件：创建精灵动画的利器
- 广播媒体对象传输方法与设备的技术分析
- MATLAB HDF5数据提取工具：深层结构化数据处理
- 适用于arm64的Valgrind交叉编译包发布
- 基于canvas和Java后端的小程序“飞翔的小鸟”完整示例
- 全面升级STM32F7 Discovery LCD BSP驱动程序
- React Router v4 入门教程与示例代码解析
- 下载OpenCV各版本安装包，全面覆盖2.4至4.5
- 手写笔画分割技术的新突破：智能分割方法与装置
- 基于Koplowitz & Bruckstein算法的MATLAB周长估计方法
- Modbus4j-3.0.3版本免费下载指南
- PoqetPresenter：Sharp Zaurus上的开源OpenOffice演示查看器
