1.3　本书主要工作

针对非负数据降维算法研究存在的问题，本书主要从以下5个方面进行研究：

（1）算法框架设计。提出基于块配准的非负矩阵分解框架，即：非负块配准框架。从块配准框架入手，建立非负块配准框架，从统一的角度分析已有非负矩阵分解模型，揭示其内在差异和共同特性，指导工程人员选择模型，帮助研究人员开发新的非负数据降维模型。该算法用对应两类常用分布的KL和欧几里得距离度量近似误差，它们分别对应数据的泊松分布和误差的高斯分布。同时该算法利用拉格朗日乘子法，开发乘法更新规则算法优化非负块配准框架，并用辅助函数技术证明算法的收敛性。该算法可用于求解非负块配准框架的所有派生模型，包括标准的非负矩阵分解模型。

（2）高效优化算法。对于基于KL距离的非负块配准框架，从梯度下降的角度改进非负块配准框架乘法更新规则算法，利用牛顿法实现单步长快速线搜索。单步长快速线搜索沿着调整负梯度方向搜索最优步长，在不超出第一象限边界的情况下更新矩阵因子，大大提高乘法更新规则的收敛速度。为矩阵因子的列（或行）设置步长，用多变量牛顿法搜索步长向量，提出多步长快速线搜索方法，弥补了矩阵因子整体的单个最优步长可能为1的缺点。改进步长设置策略，提出平衡多步长快速线搜索，降低多变量牛顿法计算复杂度。利用单步长、多步长和平衡多步长快速线搜索，本书提出单步长、多步长和平衡多步长快速梯度下降算法，并利用凸函数的Jesen不等式证明它们的收敛性。对于基于欧氏距离的非负块配准模型，通过分析子问题的性质，利用最优梯度法交替更新矩阵因子，提出非负块配准框架最优梯度法。从数学上证明了两个子问题都是凸问题且其梯度是Lipschitz连续的，从而利用最优梯度法以的收敛速度求解每个子问题，从而提出基于欧氏距离的非负块配准框架高效优化算法。

（3）派生模型设计。根据非负块配准框架的分析结果，开发新的非负数据降维模型，即：非负判别局部块配准模型。非负判别局部块配准模型为每个样本建立两类样本块：类内块由同类样本中有限最近邻组成，局部优化过程保持数据局部几何结构，放宽高斯分布假设；类间块由不同类样本中有限最近邻组成，局部优化过程最大化类间边界，从而保持数据判别信息。因此，非负判别局部块配准框架弥补了已有非负数据降维的缺点，其分类准确率较高、健壮性较强。利用全局配准技术把两种局部优化过程映射到全局坐标系进行，把二者结合，并套用非负块配准框架的乘法更新规则算法、快速梯度下降和最优梯度下降算法优化提出的非负判别局部块配准模型。

（4）在线优化算法。提出非负矩阵分解在线优化算法，利用健壮随机近似算法以在线的方式更新基矩阵。传统非负矩阵分解优化算法的空间复杂度与样本维数和样本规模成正比，由于计算机存储器容量的限制，难以满足流数据处理的需求。本书提出在新样本到达时利用健壮随机近似算法以的收敛速度更新基矩阵，提高在线非负矩阵分解的健壮性。利用准鞅理论，证明了所提算法的收敛性。为了解决空间复杂度过高的问题，提出用缓冲池存储有限量的历史样本，用新样本替换缓冲池中的旧样本，以保证基矩阵引入最新的样本统计信息。

本书主要工作[1]及相互关系概括如图1.2所示，围绕非负块配准框架，开发了乘法更新规则、快速梯度下降和最优梯度下降算法，并用该框架设计了新的非负数据降维模型，即：非负判别局部块配准。为了处理流数据，开发了非负块配准框架的在线优化算法。各优化算法是相互独立的，且各自的适用范围不同。乘法更新规则算法适用于大多数非负块配准框架派生模型，要求配准矩阵对称；快速梯度下降算法适用于大多数非负块配准框架派生模型，尤其适用于基于KL距离的非负块配准框架派生模型，要求配准矩阵半正定；最优梯度下降算法适用于基于欧式距离的非负块配准框架派生模型，要求配准矩阵半正定。非负块配准框架派生标准的非负矩阵分解。

图1.2　本书主要工作及相互关系