投影非负矩阵分解算法研究及其应用

摘要

投影非负矩阵分解可学习投影矩阵将高维数据投影到低维子空间，也可直接学习高维数据的表达系数。前者用于分类，而后者用于聚类。不同于传统分解方法如特征值分解，投影非负矩阵分解专用于非负数据分解，且保持数据的非负性。由于它的加性运算和非减操作即单纯的叠加运算，投影非负矩阵分解获得稀疏表达，这与人类大脑认知事物由部分构成整体的直观认识相一致，且数据表达的非负性具有真实的物理含义。不同于非负矩阵分解(Non-negative Matrix Factorization, NMF)，投影非负矩阵分解使用基矩阵的转置作为投影矩阵，保证训练集和测试集的系数皆为非负的，而非负矩阵分解并不能保证这点，存在所谓的“Out-of-the-sample”问题。此外，投影非负矩阵分解保证稀疏表达，可直接习得天然的类指示矩阵。因而，投影非负矩阵分解已广泛应用于图像分类、图像匹配、图像分割、文本聚类、视频跟踪等领域。因此，研究投影非负矩阵分解不仅丰富了非负矩阵分解的理论内容，而且前景应用广泛，具有重要的现实意义。
　　本文研究投影非负矩阵分解算法及其应用。鉴于传统算法忽略标签信息，提出判别投影非负矩阵分解(Discriminant Projective Non-negative Matrix Factorization, DPNMF)，提高分类性能。为扩展其在线应用，提出在线判别投影非负矩阵分解(Online DPNMF, ODPNMF)，增量更新类内散度和类间散度，在线学习判别投影矩阵。针对目前难以证明投影非负矩阵分解优化算法收敛到极值这一问题，提出了盒约束投影非负矩阵分解模型(Box-constrained PNMF, BPNMF)。为扩展其在图像分类和图像检索中的应用，分别提出了盒约束判别投影非负矩阵分解(BDPNMF)和基于相关反馈(Relevance Feedback)的有偏盒约束投影非负矩阵分解(Biased BDPNMF, B2DPNMF)，并证明规范化项为有界凸集时才能保证模型优化算法收敛到极小值。由于投影非负矩阵分解应用于聚类时，忽略标签和无标签样本信息，提出了半监督投影非负矩阵分解模型(Semi-supervised PNMF, Semi-PNMF)。为处理多模数据，提高视觉跟踪性能，提出了在线多模鲁棒非负字典学习(Online Multi-modal Robust Non-negative Dictionary Learning, OMRNDL)。本文创新点分别为：
　　1.判别投影非负矩阵分解投影非负矩阵分解由于完全忽略标签信息致使分类效果不佳。判别非负矩阵分解(Discriminant Non-negative Matrix Factorization, DNMF)结合Fisher判别规则克服这一缺陷。类似于NMF，DNMF存在“Out-of-the-sample”问题。这就违背了NMF的非负性假设。另基于图嵌入框架提出的非负投影图嵌入，因其投影子空间难以划分，分类性能同样受到限制。于是，本文提出了基于Fisher判别规则的DPNMF。它采用权策略保证Fisher规则的凸性，同时避免线性判别分析的奇异问题。为求解DPNMF，本文开发了基于乘法更新规则的优化算法，并给出收敛性证明。在四个流行数据库上的实验结果表明，与DNMF和PNGE相比，DPNMF获得较好的分类性能。
　　2.在线判别投影非负矩阵分解由于NMF和PNMF无法处理大规模数据或流数据，因而出现了以增量方式学习基矩阵的在线NMF和PNMF算法。但是，它们的分类效果不佳。为此，本文提出了在线判别投影非负矩阵分解(ODPNMF)算法来提高在线NMF和PNMF的分类性能。ODPNMF实现在线乘法更新规则，采用如下两个策略：1)以增量的方式保留历史信息并同时更新类内散度和类间散度；2)使用随机算法近似求解Fisher判别规则为正定的权重，减少SVD分解的计算开销。实验表明，ODPNMF在四个数据库的上一致优于在线NMF和PNMF算法。为说明ODPNMF的潜在应用能力，提出了ODPNMF的跟踪器。ODPNMF与大多数跟踪器一样，基于粒子滤波框架(Particle Filter Framework)实现判别跟踪。为消除背景模板对目标模板的影响，ODPNMF跟踪器仅更新类内散度，保证同类样本投影后更近。在四个常用视频序列上的跟踪实验结果表明，与传统跟踪器相比，ODPNMF性能更加稳定。
　　3.盒约束投影非负矩阵分解理论上，PNMF乘法更新法则无法收敛的缘由是， PNMF目标函数包含非凸四阶项。因而，PNMF更新法则必须使用归一化步骤来保证其收敛。据此，出现了收敛PNMF(Convergent PNMF, CPNMF)和快速自适应PNMF(Fast PNMF, FPNMF)。前者使用泰勒高阶展开PNMF目标函数，去除目标函数的非凸性，提出了收敛的乘法更新规则。而后者调整乘法更新法则的步长，避免归一化步骤。但是，它们都没给出极值收敛性证明。为此，本文提出盒约束非负矩阵分解(BPNMF)。BPNMF结合两类约束：1)盒约束保证基矩阵的收敛性；2）引入系数矩阵和等式约束来保证BPNMF等价于PNMF的目标函数。为优化BPNMF，提出了基于增广拉格朗日算法的优化框架，并证明它收敛到BPNMF的极小值。实验结果表明，无论在识别精度上还是在时间效率上，BPNMF都优于代表性算法。
　　4.盒约束判别投影非负矩阵分解PNMF完全忽略标签信息致使分类效果欠佳，而DPNMF提高PNMF分类性能，但其时间开销却较大，同时无法证明其乘法更新规则收敛于DPNMF的极值。尽管BPNMF能够保证这点，但其分类性能不佳。为此，本文提出盒约束判别投影非负矩阵分解(BDPNMF)集成两者的优点来避免DPNMF和BPNMF的各自缺陷。为保证优化算法的收敛性，BDPNMF保证Fisher判别规则为半正定的。在四个人脸数据集上的实验结果表明，无论分类性能还是时间开销，BDPNMF都优于DPNMF。为扩展BDPNMF应用于图像检索，本文开发了基于相关反馈的有偏BDPNMF(B2DPNMF)。由于图像检索问题是并非是“1+1”问题而是所谓的“1+x”问题，因而需要区别对待类内和类间样本，实现有偏判别能力。扩展性实验结果表明，B2DPNMF的检索精度优于NMF、biased DNMF、PNMF和BDPNMF。
　　5.半监督投影非负矩阵分解投影非负矩阵分解可直接学习类指示矩阵用于癌症分类。但是，它完全忽略标签信息，于是，提高PNMF的分类性能余地较大。目前提出的半监督非负矩阵分解算法已成功应用于图像和文本聚类，其分类效果仍然不佳。为此，本文为提高PNMF的分类性能，有效结合标签和无标签样本，提出了半监督投影非负矩阵分解(Semi-PNMF)。为优化Semi-PNMF，本文提出了乘法更新规则并证明其收敛性。癌症分类实验结果表明，Semi-PNMF在两个癌症基因序列数据集上的分类精度都一致优于其他代表性算法。
　　6.在线多模鲁棒非负字典学习字典学习获得一组字典能够有效表达任意向量，在稀疏表达(Sparse Representation)中尤为重要。字典学习已广泛应用于分类和信号识别中，其中的大多算法结合判别信息来提高分类性能。但它们都不能用于在线学习。为此，在线判别字典学习、在线鲁棒字典学习和在线鲁棒非负字典学习分别被提出，以增量方式来处理大规模或流数据。但它们并不能处理多模数据。因而，本文提出在线多模鲁棒非负字典学习(OMRNDL)来克服上述在线算法的这一缺陷。为实现视觉跟踪，多模非负字典学习为每个模态学习单个字典表达每个模态的内容，并共享语义系数表达，更新目标模板。这是因为每个模态都是样本的某个方面，因而假设它们具有相同的语义表达是完全合理的。为实现在线学习，引入多个辅助变量，由于它们空间开销不变，不随样本数目增多而增大，因而，OMRNDL可处理大规模数据第iii页或流数据。在流行视频基准上的定性和定量实验结果表明，与典型的跟踪器相比，OMRNDL展示了它的有效跟踪能力。

目录

声明

第一章 绪 论

1.1 研究背景及其意义

1.2 研究现状

1.3 论文工作

1.4 论文组织结构

第二章 判别投影非负矩阵分解

2.1 引言

2.2 相关工作

2.3 判别投影非负矩阵分解

2.4 实验结果

2.5 小结

第三章 在线判别投影非负矩阵分解

3.1 引 言

3.2 相关工作

3.3 在线判别投影非负矩阵分解

3.4 ODPNMF的乘法更新规则

3.5 实验结果

3.6 小结

第四章 基于增广Lagrangian的盒约束投影非负矩阵分解

4.1 引 言

4.2 盒约束投影非负矩阵分解

4.3 优化BPNMF

4.4 实验结果

4.5 小 结

第五章 盒约束判别非负投影矩阵分解

5.1 引 言

5.2 算法模型

5.3 实验结果

5.4 小 结

第六章 用于癌症分类的半监督投影非负矩阵分解

6.1 引 言

6.2 算法模型

6.3 实验结果

6.4 小 结

第七章 基于在线多模鲁棒非负字典学习的视觉跟踪

7.1 引言

7.2 相关工作

7.3 在线多模非负字典学习算法

7.4 实验结果

7.5 小 结

第八章 总结与展望

8.1 工作总结

8.2 工作不足与展望

致谢

参考文献

作者在学期间取得的学术成果

附录A

A.1 矩阵Ψl+1的近似计算