张量CP分解的详细数学推导以及Python实现! |
文章目录
- 一. 张量的基本概念
- 1.1 张量定义以及张量空间
- 1.2 阶和纤维(fiber)及切片
- 1.3 内积和范数及秩一张量/可合张量
- 1.4 超对称和超对角及展开(unfolding/flattening)
- 1.5 n-mode(矩阵)乘积和n-mode(向量)乘积
- 1.6 矩阵的Kronecker乘积及Khatri-Rao乘积
- 1.7 矩阵的Hadamard乘积
- 二. 张量的CP分解
- 2.1. CP分解的表示
- 2.2. 交替最小二乘法求解
- 2.3. 交替最小二乘法Python代码
- 2.4. 梯度下降法求解
- 2.5. 梯度下降法Python代码
- 三. 拓展应用-数据修补
- 3.1. 矩阵分解(Matrix factorization)
- 3.2. 张量分解(Tensor factorization)
- 四. 参考文献
- 强烈推荐该PPT(特详细):张量分解_张量CP分解_张量Tucker分解_详细介绍:javascript:void(0)
- 本文使用Python实现(欢迎各位朋友star,接下来还会继续更新项目!),代码地址:https://github.com/zhangkaifang/cp_decomposition
一. 张量的基本概念
1.1 张量定义以及张量空间
- 张量(tensor)?简单地说,就是个多维数组。在本研究范围内,不考虑任何物理和工学领域内的张量定义,而仅仅考虑其数学领域。正式的说,应该叫张量域(tensor fields)。第一阶张量(first-order tensor)是个向量(vector),第二阶张量(second-order tensor)是矩阵(matrix),更多阶的张量我们称之为高阶张量(higher-order tensor)。
- 由若干个向量空间中的基底的外积张成的空间。
1.2 阶和纤维(fiber)及切片
- 阶
(order/ways/modes/rank)
;- 张成所属张量空间的向量空间的个数;
;
;
;
;
- 纤维(fiber)表示从张量中抽取向量的操作, 规定其它维度只保持一个维度变化。
- 左前上角索引起始点。
1.3 内积和范数及秩一张量/可合张量
。
- 内积:
![]()
- (Frobenius)范数:
![]()
阶张量
是一个
秩一张量
,如果它能被写成个向量的外积,即:
![]()
- 例子: 给定如下的两个张量
![]()
![]()
- 内积:
![]()
- 张量
![]()
1.4 超对称和超对角及展开(unfolding/flattening)
- 立方张量:各个
mode
的长度相等;- 对称: 一个立方张量是对称的,如果其元素在下标的任意排列下是常数。如一个三阶立方张量是超对称的,如果
![]()
- 对角: 仅当
时,
;
- 将
阶张量
沿
mode-n
展开成一个矩阵。 (
mode-1
, 对应着张量的第一阶;mode-2,
对应着张量的第二阶;mode-3
对应着张量的第三阶)。
- 例子: 如何简单地理解和实现「张量展开」?
1.5 n-mode(矩阵)乘积和n-mode(向量)乘积
- 张量与矩阵相乘(又称为模态积)相比矩阵与矩阵之间的相乘更为抽象,如何理解呢?
- 一个张量
和一个矩阵
,则张量和矩阵的
模态积(
-mode product)记为
,其大小为
。对于每个元素而言,有:
其中
,我们可以看出,模态积是张量、矩阵和模态(mode)的一种“组合”运算。另外
![]()
- 例子:上述给出张量与矩阵相乘的定义,为了方便理解,下面来看一个简单的示例,若给定张量
为:
其大小为
。另外给定矩阵
试想一下:张量
和矩阵
相乘会得到什么呢?
,则张量
任意索引位置
上的值为:
这一运算规则也不难发现,张量
的大小为
,以
位置为例:
再以
位置为例:
![]()
![]()
- 也就是如下:
![]()
(会得到大小为
的张量)或
(会得到大小为
![]()
- 需要注意的是,
有一个恒等的计算公式,即
,由于
则
满足
,即采用张量矩阵化的形式进行运算可以使问题变得更加简单,从这里也可以看出高阶张量进行矩阵化的优点。
- 性质:
![]()
![]()
- 例子:利用上一小节中的张量乘以矩阵
最终组合成张量就是如下:
![]()
- 因此,乘法过程可用下图表示:先将张量矩阵化,再将张量和矩阵相乘。不同的mode-n矩阵化会使得相乘结果不同。
- 一个张量
和一个向量
的
n-mode
乘积,其元素定义为:
![]()
- 性质:
![]()
- 例子:利用上一小节中的张量乘以向量
最终组合成张量就是如下:
![]()
- 很好的一篇文章:浅谈张量分解(二):张量分解的数学基础
1.6 矩阵的Kronecker乘积及Khatri-Rao乘积
- 好文章推荐:代数基础 | Kronecker积
- 矩阵的
Kronecker
乘积- 矩阵
,则
其中
![]()
- 性质:
![]()
![]()
- 性质: 矩阵的
Kronecker
积还和张量和矩阵的n-mode
乘积有如下关系![]()
- 例子:
![]()
矩阵的
Khatri-Rao
乘积
(保证列相同),则
![]()
- 其中:
都是列向量。 注意: 如果
都是向量,那么
Khatri-Rao
乘积和Kronecker
乘积相等,即:。
- 性质: 矩阵的
Kronecker
积还和张量和矩阵的n-mode
乘积有如下关系![]()
- 例子:
![]()
- 程序例子:
1.7 矩阵的Hadamard乘积
- 矩阵
,则
![]()
- 性质:
![]()
二. 张量的CP分解
2.1. CP分解的表示
- CP分解的张量形式:
- 设
。将一个张量表示成有限个秩一张量之和,比如一个
三阶张量
可以分解为:![]()
表示向量的外积,其中向量
是因子矩阵
的第
列,并且向量
和
有相同的定义因子矩阵
和
中。 事实上,这些向量的外积是一个秩一张量,因此,我们可以用
![]()
- 元素方面,对于张量
中的任何第
元素,我们有:
![]()
,
, and
。
- CP组合示例:
- 给定矩阵
,
以及
。如果
,我们有如下:
![]()
![]()
![]()
![]()
- 注意是近似:
![]()
![]()
- CP分解的矩阵形式:
- 因子矩阵: 秩一张量中对应的向量组成的矩阵,如
![]()
- 利用因子矩阵,一个三阶张量的CP分解可以写成展开形式:
![]()
- 也就是得到如下近似:
![]()
- 与矩阵类似,
张量也存在秩
的概念,使时最小的
值,或者说能够完美拟合原始张量所需的最少秩1张量数量,即为张量
![]()
- 在实际进行
CP分解
时,通常还会对按列归一化,并将其范数作为权重存储为向量
,则新的公式为:
![]()
- 对于更高阶的张量
其中
, diag表示对角矩阵。
2.2. 交替最小二乘法求解
- 交替最小二乘法(alternating least squares,ALS)
- 下面以三阶张量
为例介绍如何使用
ALS
计算CP分解
的因子矩阵。首先我们的最终目标是让由
估计得到的张量张量
尽可能的接近原始张量
,即:
![]()
- 首先固定
矩阵,来更新
矩阵,首先得到因子矩阵
:
![]()
- 其中
表示张量
的模式 1 展开为矩阵,依此类推。 (????⊙????)???? 表示将 B 和 C 组合成单个矩阵的 Khatri-Rao 乘积。 一般来说,这是一个非凸问题; 然而,当我们当时优化一个矩阵时,这是一个凸问题。
这样可以得到,这里
表示矩阵
的
广义逆(Moore–Penrose pseudoinverse)
。- 根据
Khatri-Rao的性质
,这里就是参考公式。最终可以得到:
![]()
- 类似地可以更新
![]()
- 对高阶张量
以及参数矩阵集合
![]()
- 这里参考一些这篇博客:张量CP分解原理及Python实现!
2.3. 交替最小二乘法Python代码
- 解释
np.moveaxis
函数:
2.4. 梯度下降法求解
- 反向传播(Back Propagation,BP),利用梯度下降法求解CP参数
。
估计得到的张量
尽可能的接近原始张量
,因此将损失/目标函数设置为:
![]()
- 乘以
是为了方便求导,为了简化表达式,设
,则公式
中的
,则对矩阵
求偏导数可以得到:
![]()
- 同理可以算出
,然后用梯度下降法更新参数即可,下式中
表示学习率:
![]()
- 综上所述,高阶张量的通用公式如下,损失函数为:
![]()
- 同样令
偏导为:
![]()
- 参数更新公式为:
![]()
- 采用梯度下降法的思想也可以参考本篇文章:浅谈张量分解(五):稀疏张量的CP分解
2.5. 梯度下降法Python代码
- 实现方式1: 逐个元素进行更新
- 实现方式2: 矩阵形式进行更新
三. 拓展应用-数据修补
3.1. 矩阵分解(Matrix factorization)
- 在
MF
中,观测到的维时间序列数据被组织在矩阵
中,矩阵
由维度特性矩阵
的与时间特性矩阵
的组合进行
低秩逼近
,从而修补缺失数据:![]()
- 使用
最小二乘法、梯度下降
等方法求解下述最小化问题,从而对矩阵与矩阵
进行逼近:
![]()
,
,
是原矩阵
中非零元所处位置的集合;
为残差矩阵
F范数
的平方,用来描述矩阵 与原矩阵
的差异;
与
分别是
与
的正则项,用来防止过拟合。
![]()
以及
的过程。更新
需要最小化:
![]()
表示两个向量的内积。使用最小二乘法求解上述规划问题,推导
迭代式 ,首先将上式对
求导:
![]()
- 需要注意的是:
表示
。令该导数为零,即
![]()
- 又由:
![]()
- 变为:
![]()
的更新迭代式为:
![]()
- 可以参考这个Github:Transportation data online Prediction And Imputation(TransPAI).
- 下面代码部分的一些测试,为了方便理解:
- 对比下面的梯度下降法实现:
3.2. 张量分解(Tensor factorization)
- 事实上,
CP分解
公式是Tucker分解
的特例。在数学上,对于给定三阶张量的任何
项,
CP分解
的形式可以写成:![]()
- 其中核心张量
的超对角线项为1。换句话说, 对于任意的
可以知
,否则
。
- 将CP分解作为一个机器学习问题,我们可以通过最小化因子矩阵上的损失函数来执行学习任务,即:
![]()
- 其中
表示一组 3 元组索引。在这个优化问题中,三个因子矩阵之间的乘法(作为参数)使这个问题变得困难。因此,我们将 ALS算法应用于CP分解。
- 特别地,固定矩阵
,针对因子矩阵
中的每一行
,对应的优化问题为(这里可以参考公式
:
![]()
- 需要注意的是:
,
以及
分别表示矩阵
,
以及
位置上 所有非零元素的位置索引构成的集合 。
- 具体推导为: 令损失函数对
求偏导数,令偏导数为0。最终可以得到这个优化的最小二乘是:
![]()
- 同理,可以得到
and
的最小二乘为:
![]()
![]()
- 定理 2:假设矩阵
为
。 如果张量
有这样的CP模型:
![]()
- 可以得到:
![]()
- 补充:
np.einsum('ir, jr -> ijr', a, b)
- 补充:向量的外积。这里参考的是作者:矩阵乘法核心思想(5):内积与外积
- 矩阵乘法也可看成是向量外积之和。外积对于数据科学非常重要,因为它能帮助我们发现矩阵中最重要的东西。
,如:
![]()
的列空间是
维的,向量方向都与
相同; 行空间也是
维,向量方向都与
相同。所有非零
都是秩
矩阵,它们是构建任何矩阵完美的基础砖块。上图体现了:矩阵乘法可看成为
个秩
![]()
四. 参考文献
文章参考以下文献,这里表示感谢!
- 浅谈张量分解(一):如何简单地进行张量分解?
- Low-Rank Tensor Networks for Dimensionality Reduction and Large-Scale Optimization Problems: Perspectives and Challenges PART 1
- 隐语义模型(Latent Factor Model, LFM)原理以及代码实现
- Tensor Learning (张量学习)
- 重要参考:tensor-decomposition-in-python
- 重要参考:https://github.com/YuxuanLongBeyond/Low_rank_tensor_approx
- GitHub项目tensor-learning新增内容 (1):基于交替最小二乘法的张量分解技术
- NumPy中的维度(dimension)、轴(axis)、秩(rank)的含义
- np.dot()、np.multiply()、np.matmul()方法以及*和@运算符的用法总结
- 张量CP分解原理及Python实现
- Python中的张量分解!
- 重要参考: GitHub项目tensor-learning新增内容 (1):基于交替最小二乘法的张量分解技术
- 矩阵乘法核心思想(5):内积与外积
- 向量、矩阵、张量基础知识