树张量网络秩的最小性

《Linear Algebra and its Applications》：Minimality of Tree Tensor Network Ranks

　　

摘要：给定一个树状张量网络 G，若存在一个张量 T，它能由该网络表示，但在相同的树拓扑结构下不能用严格更小的键维度表示，则称这一组键维度是极小的。我们建立了树状张量网络的键维度为极小的充要条件，推广了 Carlini 和 Kleppe 关于具有给定多线性秩的张量存在性的刻画。我们还证明了在极小树状张量网络中，非极小张量构成一个 Zariski 闭集，因此在此意义下极小性是一个泛性质。

引言：张量分解是现代机器学习中强大的工具，尤其是在深度学习中，它使得高维数据和模型参数能够被紧凑表示。张量列和 Tucker 格式等结构化分解方法在保持表达能力的前提下减少了可学习参数的数量 [23], [24]。这些方法将大张量分解为由中间维度（称为键维度）连接的小型核心张量网络，键维度作为超参数约束了可表示张量的类别。如果键维度 r 不是极小的，则参数化是冗余的，导致存储和计算浪费。在实际算法中，如基于秩的截断过程 [10]、密度矩阵重正化群（DMRG）方法 [21]，或在固定秩流形上的黎曼优化 [16], [19]，键维度决定了局部优化问题的规模和中间收缩的代价，因此非极小的选择会增加计算复杂度而不扩大所表示的张量类。

一个自然的问题是：精确表示给定张量类且无冗余所需的极小键维度是什么？这组极小键维度被称为树状张量网络秩。

例 1.1 作为一个常见的冗余或过参数化基本例子，考虑一个矩阵 $M \in \mathbb{R}^{m \times n}$，它可以分解为 $M = XYZ$，其中 $X \in \mathbb{R}^{m \times r_1}$，$Y \in \mathbb{R}^{r_1 \times r_2}$，$Z \in \mathbb{R}^{r_2 \times n}$，且 $r_1, r_2 \ll m, n$。该矩阵对应图 1 中所示的线性张量网络。如果 M 可以用 $q_1 < r_1$ 或 $q_2 < r_2$ 替代 $r_1, r_2$ 来精确表示，则原始分解是过参数化的。

矩阵的行秩和列秩总是相等的，因此如果 $r_1 \neq r_2$，则线性张量网络模型不是极小的，相同的矩阵集合可以用 $r'_1 = r'_2 = \min\{r_1, r_2\}$ 来表示。换句话说：$(r_1, r_2)$ 是张量网络秩当且仅当 $r_1 = r_2$。

虽然不同的分解方式是可能的，例如 $M = AB$，其中 $A \in \mathbb{R}^{m \times r}$，$B \in \mathbb{R}^{r \times n}$，$r \ll m, n$，但本文关注的是在固定张量网络结构内优化键维度，而非比较分解方案。此外，我们的目标不是近似或分析某个特定张量，而是刻画当固定拓扑和键维度的张量网络定义了一个张量类，且没有严格更小的键维度足以表示该类张量。

例 1.2 考虑图 2 中的树及其两组不同的键维度。我们的主要结果定理 3.9 表明，所有用 (1) 可表示的张量也可以用 (2) 表示。由于后者每个分量上的键维度都小于前者，左侧树的标注不是极小的。因此，用 (1) 表示张量包含冗余。定理 3.9 将表明左侧面板不是极小的，因为键 $(v_0, v_1)$ 和 $(v_0, v_2)$ 上的维度超过了相邻键上维度的乘积，而右侧面板是极小的，因为所有键维度都是容许的（定义 3.3）。

张量网络起源于量子物理，作为一种表示多体系统的手段，纠缠编码在底层图中 [8], [20], [22], [26]。在此背景下，Shi、Duan 和 Vidal 建立了基于奇异值分解（SVD）的树状张量网络的典范形式，其中每条边与通过截断该边获得的树二划分上的 Schmidt 分解相关联。在此形式下，一条边上的极小键维度等于该割处的（Schmidt）秩 [22]。

在应用数学中，矩阵乘积态/张量列和树状张量网络/层次 Tucker 张量的微分几何描述逐渐兴起，一旦固定了秩并施加了某些满秩（或"极小"）条件，它们就形成了光滑嵌入流形 [15], [16], [25]。这些流形构造描述了固定秩模型类在模内部规范对称性下的几何结构。关键的是，所有这些工作都假设键维度元组是极小的，即树状张量网络秩。然而，这一文献并未提供验证极小性的显式准则。在图 2 中，两组键维度都可能看似有效，但 (1) 不是极小的。由于流形维度由极小键维度决定，非极小的元组仅产生冗余参数化。因此，验证极小性对于微分几何图像至关重要。

在应用代数几何中，具有有界键维度的张量集合被研究为由多项式方程定义的代数簇。在此设定下，固定张量网络拓扑与键维度元组确定了一个参数化的张量族，其 Zariski 闭包形成一个张量网络簇。先前的工作研究了这些簇的结构性质，包括维度和几何特征 [3], [4], [18], [27]。特别是，在 [3] 中表明，过剩的键维度可以在不影响关联张量网络簇维度的前提下被减少。我们的结果自然地融入这一框架：极小性成为了关于关联张量网络簇中泛张量是否不允许用任何严格更小的键维度表示的陈述。

已有工作通过将树诱导的二划分展平来刻画树状张量网络秩。Hackbusch 和 Kühn 引入了层次 Tucker 格式以及一个递归的基于 SVD 的截断过程，该过程能够可控地减少键维度 [13]。Grasedyck 和 Hackbusch 随后通过维度树正式化了层次秩和 TT 秩，并将其与边诱导展平的矩阵秩联系起来，建立了两种格式之间的结构关系 [10]。Bachmayr、Schneider 和 Uschmajew 通过这些展平秩刻画了层次张量格式中的可表示性，这是层次 SVD 方法的基础 [2, 定理 3.3]。Ye 和 Lim 证明了张量的树状张量网络秩是唯一的，并且可以计算为全局边割展平秩的元组 [27, 定理 8.3 和 8.8]。

与本文最密切相关的作品是 Carlini 和 Kleppe [5] 以及 Buczyńska、Buczyński 和 Micha?ek [4] 的工作。前者确定了确保星形图键维度元组极小的显式不等式。后者确定了确保二叉树键维度元组极小的必要条件，通过一个辅助函数递归地表述了这些条件，但未证明充分性。

为了精确陈述我们的贡献，我们现在回顾 Ye 和 Lim [27] 中关于任意域上张量网络的正式定义。在本文中，我们特别关注树状张量网络，其底层收缩图是连通无环图。设 $G = (V, E)$ 是一棵树，其中 $V = \{1, \ldots, d\}$ 是顶点，$E \subseteq \{(i,j) : i,j \in V, i \neq j\}$ 是有向边。排序 $(i,j)$ 表示该边从顶点 i 指向顶点 j。每条（无向）边对应一个非零键维度 $r_{ij} \in \mathbb{N}$。每个顶点 $i \in V$ 关联一个"物理"向量空间 $\mathbb{V}_i$，它是有限域的某个域 $\mathbb{k}$ 上的有限维空间。

注记 1.3 物理空间 $\mathbb{V}_i$ 将以"悬挂"边来可视化，如图 3 所示，但它们与编码网络收缩结构的键边 E 是不同的。在文献中，通常允许一个顶点关联多个物理输出或没有物理输出。限制每个顶点恰好有一个物理空间不会限制一般性：在具有多个物理输出的顶点处，我们定义 $\mathbb{V}_i$ 为组成向量空间的张量积。在没有物理输出的顶点处，可以取 $\mathbb{V}_i = \mathbb{k}$。由于 $\mathbb{k} \otimes W \cong W$，这些 1 维物理空间对网络没有影响。

张量网络将隐式地表示张量积空间 $\mathbb{V}_1 \otimes \cdots \otimes \mathbb{V}_d$ 中的一个张量，作为按收缩图指定的网络收缩结果。为此，每条边 $(i,j)$ 关联一个"收缩"向量空间和余向量空间 $\mathbb{E}_{ij}$ 和 $\mathbb{E}^*_{ji}$，其维度等于键维度 $r_{ij}$。这里 $\mathbb{E}^*_{ji}$ 表示 $\mathbb{E}_{ij}$ 的对偶空间，即从 $\mathbb{E}_{ij}$ 到 $\mathbb{k}$ 的所有线性映射的空间。每个映射 $\phi^* \in \mathbb{E}^*_{ji}$ 通过 $\phi^*(\psi)$ 对向量 $\psi \in \mathbb{E}_{ij}$ 求值，其中 $\phi^*(\psi)$ 表示 $\phi^*$ 对 $\psi$ 的作用。这一配对构成了网络中使用的收缩操作的基础。

例 1.4 为了说明收缩过程，考虑图 3 中两个连通顶点 i 和 j，分别关联向量空间 $\mathbb{V}_i^*$ 和 $\mathbb{V}_j$。顶部图示表示沿共享边 $(i,j)$ 的收缩，可以解释为矩阵乘法：左侧节点编码张量 $A \in \mathbb{V}_i^* \otimes \mathbb{E}_{ij} = \text{Hom}(\mathbb{V}_i, \mathbb{E}_{ij})$，右侧节点编码 $B \in \mathbb{E}^*_{ji} \otimes \mathbb{V}_j = \text{Hom}(\mathbb{E}_{ij}, \mathbb{V}_j)$，其中 $\text{Hom}(\mathbb{V}, \mathbb{W})$ 是从 $\mathbb{V}$ 到 $\mathbb{W}$ 的线性映射空间。沿共享边收缩对应于组合这两个映射：$C = BA \in \text{Hom}(\mathbb{V}_i, \mathbb{V}_j)$。底部图示中的结果节点 k 继承了物理向量空间 $\mathbb{V}_i^*$ 和 $\mathbb{V}_j$，对应的张量 C 编码了 A 和 B 的组合，即 $\mathbb{E}_{ij}$ 与 $\mathbb{E}^*_{ji}$ 收缩的结果。

上述例子可以推广到树状张量网络中的任意张量收缩，如下所述。回忆张量 $v \in \mathbb{V}_1 \otimes \cdots \otimes \mathbb{V}_d$ 是初等的，如果它可以写成 $v_1 \otimes \cdots \otimes v_d$ 的形式，其中 $v_i \in \mathbb{V}_i$。任何张量都可以表示为初等张量的有限和 $T = \sum_{j=1}^s v^{(j)}_1 \otimes \cdots \otimes v^{(j)}_d$ [12, 第 3 节]。对于每个顶点 $i \in V$，令 $\text{in}(i)$ 和 $\text{out}(i)$ 分别表示入射到 i 的入边和出边的集合。令入空间和出空间分别为 $\mathbb{I}_i^* = \bigotimes_{j \in \text{in}(i)} \mathbb{E}^*_{ji}$ 和 $\mathbb{O}_i = \bigotimes_{j \in \text{out}(i)} \mathbb{E}_{ij}$。然后，树 G 通过收缩映射 $g: \bigotimes_{i=1}^d (\mathbb{I}_i^* \otimes \mathbb{V}_i \otimes \mathbb{O}_i) \to \mathbb{V}_1 \otimes \cdots \otimes \mathbb{V}_d$ 表示张量 T，该映射沿有向边 $(i,j) \in E$ 收缩每一对对偶向量空间 $\mathbb{E}^*_{ji} \otimes \mathbb{E}_{ij}$。映射 g 是线性的，由其对初等张量的作用定义：当 $v_i \in \mathbb{V}_i$，$\phi_i^* = \bigotimes_{j \in \text{in}(i)} \phi_{ij}^*$，$\phi_{ij}^* \in \mathbb{E}^*_{ji}$，以及 $\psi_i = \bigotimes_{j \in \text{out}(i)} \psi_{ij}$，$\psi_{ij} \in \mathbb{E}_{ij}$ 时，通过求值每条边 $(i,j)$ 上的配对 $\phi_{ij}^*(\psi_{ij})$ 来完成收缩。

由收缩图 G 和键维度元组 $r = (r_{ij} = \dim \mathbb{E}_{ij})_{(i,j) \in E}$ 可表示的所有 $\mathbb{V}_1 \otimes \cdots \otimes \mathbb{V}_d$ 中的张量集合记为 $\text{TN}(G, r)$。即 $\text{TN}(G, r)$ 包含可以写为收缩 $g(T_1 \otimes \cdots \otimes T_d)$ 的张量，其中每个局部张量 $T_i \in \mathbb{I}_i^* \otimes \mathbb{V}_i \otimes \mathbb{O}_i$，即
$$\text{TN}(G, r) = \{g(T_1 \otimes \cdots \otimes T_d) \mid T_i \in \mathbb{I}_i^* \otimes \mathbb{V}_i \otimes \mathbb{O}_i\}$$

本工作考虑键维度的极小性。该概念定义如下。对于两个键维度元组 $r = (r_{ij})_{(i,j) \in E}$ 和 $s = (s_{ij})_{(i,j) \in E}$，我们记 $s \leq r$ 表示逐分量不等式 $s_{ij} \leq r_{ij}$ 对所有 $(i,j) \in E$ 成立。

定义 1.5 极小键维度 固定一棵树 G 和一个键维度元组 r。
- 给定 $T \in \text{TN}(G, r)$，若 $T \in \text{TN}(G, r)$，但对于任意 $s \leq r$ 且 $s \neq r$，都有 $T \notin \text{TN}(G, s)$，则称 r 对 T 是极小的，或 T 的一个张量网络秩。
- 若存在某个 $T \in \text{TN}(G, r)$ 使得 r 对 T 是极小的，则称 r 对 G 是极小的，或 G 的一个张量网络秩。

考虑集合
$$\text{TN}^\circ(G, r) = \text{TN}(G, r) \setminus \bigcup_{\substack{s \leq r \\ s \neq r}} \text{TN}(G, s)$$
由定义，$\text{TN}^\circ(G, r)$ 由所有使 r 对 T 极小的张量 T 组成。因此，r 对 G 极小当且仅当 $\text{TN}^\circ(G, r)$ 非空。注意 $\text{TN}^\circ(G, r)$ 可以是空集，如例 1.1 中 $r_1 \neq r_2$ 时所示。

本文要解决的主要问题是：

Q1 极小性：何时 $\text{TN}^\circ(G, r)$ 非空，即何时 r 是 G 的张量网络秩？

Q2 泛性：若 $\text{TN}^\circ(G, r) \neq \emptyset$，它是否是 $\text{TN}(G, r)$ 的 Zariski 开稠密子集？即极小性是否意味着 $\text{TN}^\circ(G, r)$ 包含 $\text{TN}(G, r)$ 中几乎所有的张量？

大量文献（如 [15], [16], [25]）在假设 r 是树状张量网络秩的前提下证明结果。

本工作的主要结果，定理3.9，为r成为G的树张量网络秩提供了关于(G,r)的充要条件，将Carlini和Kleppe[5]的主要结果推广到任意树张量网络。当此条件成立时，我们在下面的定理3.11中证明，张量集TN°(G,r)甚至构成TN(G,r)的一个Zariski开且稠密的子集。我们的论证是纯代数的，不依赖于正交性或奇异值分解，并且适用于任意无穷域。以此方式，我们的工作为树张量网络簇贡献了精确的局部到整体最小性刻画和通用性陈述，其条件仅涉及键维数元组中的数值，且易于验证。本文的其余部分结构如下。我们在第2节中回顾Carlini和Kleppe对星形图情形的刻画（对应于Tucker分解），并建立推广到任意树所依赖的代数几何基础。之后，在第3节中，我们将讨论扩展到任意树，并给出这些树上最小性的充要条件。然后我们建立了这些极小模型在环境张量网络簇中的通用性，最后讨论了非极小树张量网络的实用化简。Section snippetsCarlini和Kleppe对星形图的刻画Tucker图（或星形图）是一个具有单一中心节点连接到d个叶节点的张量网络，其中d是张量的阶数（见图4）。形式上，Tucker图G_Tucker具有顶点集V = {0, 1, …, d}，其中0是中心节点，边集E = {(0, i) : i = 1, …, d} [27]。我们要求顶点0关联的空间为平凡空间：V_0 = k。则所得的张量网络表示d阶张量的Tucker分解。Carlini和Kleppe[5]提供了关于……的完整刻画任意树图上的主要结果星形图是一种特殊的树。现在我们更一般地询问哪些约束决定了树张量网络全类的最小性。本节的目的是证明，最小性的充要条件来自于对图中每个局部张量T_i施加相同类型的键维数约束。我们现在固定一些符号。我们说G的子树G' = (V', E')以a ∈ V为根，如果每条边(i, j) ∈ E'的定向使得j更接近a。则每个顶点……将键维数实际化简为树张量网络秩在通过秩截断获得数据稀疏的树张量网络近似时，知道一组键维数是否极小是相关的。给定张量T、树图G = (V, E)和键维数r，这些方法将用树张量网络T? ∈ TN(G, r)来近似T。然而，如果键维数r不是极小的，那么T?将具有严格小于r的树张量网络秩，这与这些方法的用户可能预期的相反，因为TN°(G, r) = ?。这……致谢J.J.和N.V.得到了FWO Weave项目"群不变神经网络张量列车网络"（编号G011624N）的支持。T.S.得到了FWO青年博士后奖学金（编号1219723N）的支持。我们感谢两位审稿人的仔细阅读和建设性意见，这些意见有助于提高本手稿的清晰度和范围。特别是，我们扩展了第4节，以更好地阐述我们结果的实用意义，并澄清了与现有……的关系Jana Jovcheva | Tim Seynnaeve | Nick Vannieuwenhoven