基于块坐标下降法的非负矩阵与张量分解算法综述
需积分: 9 77 浏览量
更新于2024-07-19
收藏 798KB PDF 举报
非负矩阵和张量分解（Nonnegative Matrix and Tensor Factorizations, NMF 和 NTF）是近年来在数据挖掘、机器学习和信号处理等领域中备受关注的方法，尤其在文本分析、计算机视觉和生物信息学等应用中，它们的非负约束使得结果更易于解释且性能优良。本文《Algorithms for nonnegative matrix and tensor factorizations: a unified view based on block coordinate descent framework》由 Kim、He 和 Park 于 2014 年发表在《Journal of Global Optimization》上，论文编号为58(2):285-319，doi:10.1007/s10898-013-0035-4。
文章的主要焦点在于将非负矩阵分解和非负张量分解的算法发展进行了一次统一的视角审视，通过块坐标下降（Block Coordinate Descent, BCD）框架来整合这些方法。BCD框架是一种迭代优化策略，它将优化问题分解成多个小的子问题，每个子问题独立求解，然后汇总结果。这种方法的优势在于可以处理大规模数据集，并在满足非负约束的同时提高计算效率。
在NMF中，给定一个矩阵，该方法试图找到两个非负因子矩阵，使得原始矩阵可以近似为这两个因子的乘积，同时保持低秩特性。在NTF中，这种思想被扩展到多维数据，即寻找一组非负张量分解为若干个低秩非负张量的乘积。然而，由于非负约束的存在，传统的优化算法在求解过程中可能会遇到困难，导致计算复杂度增加。
文中概述了多种针对NMF和NTF设计的算法策略，包括但不限于交替最小二乘法（Alternating Least Squares, ALS）、投影梯度下降（Projected Gradient Descent, PGD）、以及各种变种和改进版本。这些算法旨在通过不同的策略如贪婪搜索、随机化策略或自适应学习率调整来减轻非负约束带来的计算负担，同时保证收敛性和优化效果。
作者们对这些算法进行了深入比较和分析，强调了BCD框架下的算法在理论和实践上的优势，例如局部最优与全局最优之间的平衡、处理大规模数据的效率提升以及对模型解释性的增强。此外，文章还讨论了如何处理潜在的数值不稳定性和过拟合问题，以及在实际应用中如何选择合适的算法参数。
总结来说，这篇论文提供了非负矩阵和张量分解算法的一个全面综述，通过BCD框架将其统一，这对于理解和改进这两种重要的数据处理技术具有重要意义。对于从事相关领域研究的学者和工程师来说，这篇文献为理解如何高效地解决非负约束优化问题提供了宝贵参考。
J Glob Optim (2014) 58:285–319 291
Using Theorem 2, the solutions of (10) can be stated as
w
k
←
[R
k
h
k
]
+
h
k
2
2
and h
k
←
[R
T
k
w
k
]
+
w
k
2
2
. (13)
This 2K -block BCD algorithm has been studied under the name of the hierarchical alternating
least squares (HALS) method by Cichocki et al. [19,20] and the rank-one residue iteration
(RRI) independently by Ho [44]. According to Theorem 1, the convergence property of the
HALS/RRI algorithm can be written as follows.
Corollary 2 If the columns of W and H remain nonzero throughout all the iterations and
the minimums in (13) are attained at each step, every limit point of the sequence
(
W, H
)
(i)
generated by the HALS/RRI algorithm is a stationary point of (2).
In practice, a zero column could occur in W or H during the HALS/RRI algorithm. This
happens if h
k
∈ null(R
k
), w
k
∈ null(R
T
k
), R
k
h
k
≤ 0, or R
T
k
w
k
≤ 0. To prevent zero
columns, a small positive number could be used for the maximum operator in (13): That is,
max(·,)with a small positive number such as 10
−16
is used instead of max(·, 0) [20,35].
The HALS/RRI algorithm with this modification often shows faster convergence compared to
other BCD methods or previously developed methods [37,59]. See Sect. 3.1 for acceleration
techniques for the HALS/RRI method and Sect. 6.2 for more discussion on experimental
comparisons.
For an efficient implementation, it is not necessary to explicitly compute R
k
. Replacing
R
k
in (13) with the expression in (11), the solutions can be rewritten as
w
k
←
w
k
+
(AH)
·k
−(WH
T
H)
·k
(H
T
H)
kk
+
and (14a )
h
k
←
h
k
+
(A
T
W)
·k
−(HW
T
W)
·k
(W
T
W)
kk
+
. (14b)
The choice of update formulae is related with the choice of an update order. Two versions of
an update order can be considered:
w
1
→ h
1
→···→w
K
→ h
K
(15)
and
w
1
→···→w
K
→ h
1
→···→h
K
. (16)
When using (13), update order (15) is more efficient because R
k
is explicitly computed and
then used to update both w
k
and h
k
. When using (14), although either (15)or(16) can be used,
update order (16) tends to be more efficient in environments such as MATLAB based on our
experience. To update all the elements in W and H, update formulae (13) with ordering (15)
require 8KMN+3K (M +N) floating point operations, whereas update formulae (14) with
either choice of ordering require 4KMN+ (4K
2
+6K )(M + N) floating point operations.
When K min(M, N), the latter is more efficient. Moreover, the memory requirement of
(14) is smaller because R
k
need not be stored. For more details, see Cichocki and Phan [19].
2.3 BCD with K (M + N) scalar blocks
In one extreme, the unknowns can be partitioned into K (M +N) blocks of scalars, as shown
in Fig. 1c. In this case, every element of W and H is considered as a block in the context
123
剩余34页未读，继续阅读
2016-07-11 上传
2023-03-29 上传
2023-09-18 上传
2023-04-27 上传
2023-04-05 上传
2023-10-04 上传
2023-06-11 上传
2024-01-23 上传
puppet_love
- 粉丝: 22
- 资源: 42
我的内容管理
展开
最新资源
- 磁性吸附笔筒设计创新，行业文档精选
- Java Swing实现的俄罗斯方块游戏代码分享
- 骨折生长的二维与三维模型比较分析
- 水彩花卉与羽毛无缝背景矢量素材
- 设计一种高效的袋料分离装置
- 探索4.20图包.zip的奥秘
- RabbitMQ 3.7.x延时消息交换插件安装与操作指南
- 解决NLTK下载停用词失败的问题
- 多系统平台的并行处理技术研究
- Jekyll项目实战：网页设计作业的入门练习
- discord.js v13按钮分页包实现教程与应用
- SpringBoot与Uniapp结合开发短视频APP实战教程
- Tensorflow学习笔记深度解析：人工智能实践指南
- 无服务器部署管理器：防止错误部署AWS帐户
- 医疗图标矢量素材合集：扁平风格16图标(PNG/EPS/PSD)
- 人工智能基础课程汇报PPT模板下载
