张量补充 2 （补充ing）
文章目录
- 数学概念
- 1. 张量 (Tensor)
- 2. CANDECOMP/PARAFAC (CP) 分解
- 3. 外积 (Outer Product)
- 4. Khatri-Rao 积 (Khatri-Rao Product)
- 5. 秩 (Rank)
- 6. 边界秩 (Border Rank)
- 7. 交替最小二乘法 (Alternating Least Squares, ALS)
- CANDECOMP/PARAFAC (CP) 分解
- 张量秩
- 边界秩（Border Rank）
- ALS算法计算CP分解
- 参考
数学概念
1. 张量 (Tensor)
- 定义: 张量是多维数组的通用表示，表示为 X ∈ R I 1 × I 2 × ⋯ × I N \mathcal{X} \in \mathbb{R}^{I_1 \times I_2 \times \cdots \times I_N} X∈RI1×I2×⋯×IN，其中 I 1 , I 2 , … , I N I_1, I_2, \dots, I_N I1,I2,…,IN 是各个维度的大小。
- 阶数 (Order): 张量的阶数是它的维度数，例如一阶张量是向量，二阶张量是矩阵，三阶或更高阶的张量则称为高阶张量。
2. CANDECOMP/PARAFAC (CP) 分解
-
定义: CP分解是一种将张量分解为秩为一的张量之和的分解方式。
-
秩 (Rank): 张量的秩是分解成秩为一张量之和所需的最小数量。
-
表示: 对于三阶张量 X ∈ R I × J × K \mathcal{X} \in \mathbb{R}^{I \times J \times K} X∈RI×J×K，CP分解表示为
X ≈ ∑ r = 1 R λ r a r ∘ b r ∘ c r \mathcal{X} \approx \sum_{r=1}^R \lambda_r \, \mathbf{a}_r \circ \mathbf{b}_r \circ \mathbf{c}_r X≈r=1∑Rλrar∘br∘cr
其中， R R R 是秩， λ r \lambda_r λr 是标量， a r \mathbf{a}_r ar， b r \mathbf{b}_r br， c r \mathbf{c}_r cr 分别是列向量。
3. 外积 (Outer Product)
- 定义: 外积是两个向量之间的操作，结果是一个张量。例如，两个向量 a \mathbf{a} a 和 b \mathbf{b} b 的外积 a ∘ b \mathbf{a} \circ \mathbf{b} a∘b 是一个矩阵，其中每个元素是 a \mathbf{a} a 和 b \mathbf{b} b 的对应元素的乘积。
4. Khatri-Rao 积 (Khatri-Rao Product)
-
定义: Khatri-Rao积是两个矩阵的列间Kronecker积。例如，矩阵 A ∈ R I × K \mathbf{A} \in \mathbb{R}^{I \times K} A∈RI×K 和 B ∈ R J × K \mathbf{B} \in \mathbb{R}^{J \times K} B∈RJ×K 的Khatri-Rao积定义为
A ⊙ B = [ a 1 ⊗ b 1 , a 2 ⊗ b 2 , … , a K ⊗ b K ] \mathbf{A} \odot \mathbf{B} = [\mathbf{a}_1 \otimes \mathbf{b}_1, \mathbf{a}_2 \otimes \mathbf{b}_2, \dots, \mathbf{a}_K \otimes \mathbf{b}_K] A⊙B=[a1⊗b1,a2⊗b2,…,aK⊗bK]
其中 ⊗ \otimes ⊗ 表示Kronecker积， a i \mathbf{a}_i ai 和 b i \mathbf{b}_i bi 是 A \mathbf{A} A 和 B \mathbf{B} B 的第 i i i 列。
5. 秩 (Rank)
-
定义: 张量的秩是可以表示该张量的秩为一的张量个数的最小值。对于矩阵，这是行或列的最大线性无关数。
-
公式:
rank ( X ) = min { R : X = ∑ r = 1 R a r ∘ b r ∘ c r } \text{rank}(\mathcal{X}) = \min \left\{ R : \mathcal{X} = \sum_{r=1}^R \mathbf{a}_r \circ \mathbf{b}_r \circ \mathbf{c}_r \right\} rank(X)=min{R:X=r=1∑Rar∘br∘cr}
6. 边界秩 (Border Rank)
-
定义: 边界秩是通过近似表示一个张量的秩的最小值。换句话说，它是通过对张量进行近似得到的最小秩。
-
公式:
rank ~ ( X ) = min { r ∣ 对于任意 ϵ > 0 , 存在张量 E , 使得 ∥ E ∥ < ϵ 且 rank ( X + E ) = r } \tilde{\text{rank}}(\mathcal{X}) = \min \left\{ r \mid \text{对于任意 } \epsilon > 0, \text{ 存在张量 } \mathcal{E}, \text{使得 } \|\mathcal{E}\| < \epsilon \text{ 且 } \text{rank}(\mathcal{X} + \mathcal{E}) = r \right\} rank~(X)=min{r∣对于任意 ϵ>0, 存在张量 E,使得 ∥E∥<ϵ 且 rank(X+E)=r}
7. 交替最小二乘法 (Alternating Least Squares, ALS)
- 定义: ALS是一种迭代算法，通过固定其他因子矩阵，逐步优化某一个因子矩阵，使得损失函数逐渐减小，从而逼近最优解。
- 算法步骤:
-
固定矩阵 B , C \mathbf{B}, \mathbf{C} B,C，求解 A \mathbf{A} A：
A ← X ( 1 ) ( C ⊙ B ) [ ( C T C ) ∗ ( B T B ) ] − 1 \mathbf{A} \leftarrow \mathbf{X}_{(1)} (\mathbf{C} \odot \mathbf{B}) \left[ (\mathbf{C}^T \mathbf{C}) \ast (\mathbf{B}^T \mathbf{B}) \right]^{-1} A←X(1)(C⊙B)[(CTC)∗(BTB)]−1
-
固定矩阵 A , C \mathbf{A}, \mathbf{C} A,C，求解 B \mathbf{B} B：
B ← X ( 2 ) ( C ⊙ A ) [ ( C T C ) ∗ ( A T A ) ] − 1 \mathbf{B} \leftarrow \mathbf{X}_{(2)} (\mathbf{C} \odot \mathbf{A}) \left[ (\mathbf{C}^T \mathbf{C}) \ast (\mathbf{A}^T \mathbf{A}) \right]^{-1} B←X(2)(C⊙A)[(CTC)∗(ATA)]−1
-
固定矩阵 A , B \mathbf{A}, \mathbf{B} A,B，求解 C \mathbf{C} C：
C ← X ( 3 ) ( B ⊙ A ) [ ( B T B ) ∗ ( A T A ) ] − 1 \mathbf{C} \leftarrow \mathbf{X}_{(3)} (\mathbf{B} \odot \mathbf{A}) \left[ (\mathbf{B}^T \mathbf{B}) \ast (\mathbf{A}^T \mathbf{A}) \right]^{-1} C←X(3)(B⊙A)[(BTB)∗(ATA)]−1
-
CANDECOMP/PARAFAC (CP) 分解
CP分解是一种将张量表示为多个秩为一的张量的和的分解方式。对于一个三阶张量 X ∈ R I × J × K \mathcal{X} \in \mathbb{R}^{I \times J \times K} X∈RI×J×K，CP分解的形式如下：
X ≈ ∑ r = 1 R λ r a r ∘ b r ∘ c r \mathcal{X} \approx \sum_{r=1}^R \lambda_r \, \mathbf{a}_r \circ \mathbf{b}_r \circ \mathbf{c}_r X≈r=1∑Rλrar∘br∘cr
其中， R R R 是分解的秩， λ r \lambda_r λr 是标量， a r ∈ R I \mathbf{a}_r \in \mathbb{R}^I ar∈RI， b r ∈ R J \mathbf{b}_r \in \mathbb{R}^J br∈RJ， c r ∈ R K \mathbf{c}_r \in \mathbb{R}^K cr∈RK 是对应的因子矩阵， ∘ \circ ∘ 表示外积。
矩阵化的形式为：
X ( 1 ) ≈ A ( C ⊙ B ) T \mathbf{X}_{(1)} \approx \mathbf{A} (\mathbf{C} \odot \mathbf{B})^T X(1)≈A(C⊙B)T
X ( 2 ) ≈ B ( C ⊙ A ) T \mathbf{X}_{(2)} \approx \mathbf{B} (\mathbf{C} \odot \mathbf{A})^T X(2)≈B(C⊙A)T
X ( 3 ) ≈ C ( B ⊙ A ) T \mathbf{X}_{(3)} \approx \mathbf{C} (\mathbf{B} \odot \mathbf{A})^T X(3)≈C(B⊙A)T
这里 ⊙ \odot ⊙ 表示Khatri-Rao积。
张量秩
张量的秩（Rank）定义为能将张量表示为秩为一的张量之和的最小数量。具体而言，对于张量 X \mathcal{X} X，其秩为：
rank ( X ) = min { R : X = ∑ r = 1 R a r ∘ b r ∘ c r } \text{rank}(\mathcal{X}) = \min \left\{ R : \mathcal{X} = \sum_{r=1}^R \mathbf{a}_r \circ \mathbf{b}_r \circ \mathbf{c}_r \right\} rank(X)=min{R:X=r=1∑Rar∘br∘cr}
张量秩的计算非常复杂，一般无法通过简单算法确定。
边界秩（Border Rank）
边界秩是指通过一定的近似误差将张量表示为秩为 r r r 的张量的最小秩。定义为：
rank ~ ( X ) = min { r ∣ 对于任意 ϵ > 0 , 存在张量 E , 使得 ∥ E ∥ < ϵ 且 rank ( X + E ) = r } \tilde{\text{rank}}(\mathcal{X}) = \min \left\{ r \mid \text{对于任意 } \epsilon > 0, \text{ 存在张量 } \mathcal{E}, \text{使得 } \|\mathcal{E}\| < \epsilon \text{ 且 } \text{rank}(\mathcal{X} + \mathcal{E}) = r \right\} rank~(X)=min{r∣对于任意 ϵ>0, 存在张量 E,使得 ∥E∥<ϵ 且 rank(X+E)=r}
显然，有 rank ~ ( X ) ≤ rank ( X ) \tilde{\text{rank}}(\mathcal{X}) \leq \text{rank}(\mathcal{X}) rank~(X)≤rank(X)。
ALS算法计算CP分解
交替最小二乘法（ALS）是计算CP分解的常用方法。ALS算法通过固定其他矩阵，交替求解每个因子矩阵的最小二乘解。具体算法步骤如下：
A ← X ( 1 ) ( C ⊙ B ) [ ( C T C ) ∗ ( B T B ) ] − 1 \mathbf{A} \leftarrow \mathbf{X}_{(1)} (\mathbf{C} \odot \mathbf{B}) \left[ (\mathbf{C}^T \mathbf{C}) \ast (\mathbf{B}^T \mathbf{B}) \right]^{-1} A←X(1)(C⊙B)[(CTC)∗(BTB)]−1
B ← X ( 2 ) ( C ⊙ A ) [ ( C T C ) ∗ ( A T A ) ] − 1 \mathbf{B} \leftarrow \mathbf{X}_{(2)} (\mathbf{C} \odot \mathbf{A}) \left[ (\mathbf{C}^T \mathbf{C}) \ast (\mathbf{A}^T \mathbf{A}) \right]^{-1} B←X(2)(C⊙A)[(CTC)∗(ATA)]−1
C ← X ( 3 ) ( B ⊙ A ) [ ( B T B ) ∗ ( A T A ) ] − 1 \mathbf{C} \leftarrow \mathbf{X}_{(3)} (\mathbf{B} \odot \mathbf{A}) \left[ (\mathbf{B}^T \mathbf{B}) \ast (\mathbf{A}^T \mathbf{A}) \right]^{-1} C←X(3)(B⊙A)[(BTB)∗(ATA)]−1
该过程不断迭代，直到收敛。
参考
- https://www.kolda.net/publication/TensorReview.pdf