Representation Theorems for Matrix Product States¶
作者: Erdong Guo, David Draper
来源: SIAM Journal on Mathematics of Data Science
主题: 统计计算 / 算法
相关性: 6/10
机构绿灯: University of California, Santa Cruz(US News 前 50,免分进入精读)
链接: https://doi.org/10.1137/24m172010x
一、领域脉络与小综述¶
这个方向是什么¶
本文所处的子方向是张量网络(tensor networks)的表示能力(representational capacity)理论。根本问题是:一类特定的张量网络结构(本文聚焦矩阵乘积态 MPS,即一维张量网络)能够精确或近似表示哪一类函数?这个问题横跨量子物理(MPS 源于一维量子自旋系统的基态表示)、机器学习理论(张量网络作为函数逼近器)与统计计算(张量缩并的复杂度)。该方向的成熟度处于"基础理论仍在搭建"阶段——表示能力的刻画远不如神经网络理论那样系统,且缺乏统一的框架来比较不同张量网络结构的表达力。
发展脉络(history)¶
从 introduction 与参考文献可以梳理出三条交织的线索:
线索一:MPS 作为量子态表示。 奠基工作是 Fannes, Nachtergaele, Werner (1992) 与 Östlund, Rommer (1995) 提出的密度矩阵重整化群(DMRG)框架,确立了 MPS 作为一维纠缠态的有效参数化。这一支的核心关切是:哪些量子态可以被 MPS 高效表示?答案与纠缠熵(entanglement entropy)的面积律(area law)紧密相关——这是 MPS 表示能力的第一个"已知边界"。
线索二:MPS 作为机器学习模型。 更近的进展将 MPS 引入监督学习。Stoudenmire, Schwab (2016) 提出用 MPS 做图像分类,展示了张量网络在特征学习中的潜力。Novikov et al. (2015) 将张量列(tensor train,与 MPS 同构)用于压缩全连接层。这一支的关切是:MPS 能表达什么样的函数类?但早期工作多为实证,缺乏严格的表示定理。作者在引言中指出,已有工作(如 Cohen, Sharir, Shashua 2016 关于卷积算术电路的表示能力)虽触及张量网络,但"没有系统性地刻画 MPS 的函数空间"。
线索三:神经网络与核方法的等价性。 这是本文借力的关键工具。经典结果是 Neal (1996) 证明无限宽单隐层神经网络收敛到高斯过程;Cho, Saul (2009) 建立了核函数与激活函数之间的对应关系(如 arc-cosine 核)。本文作者将这一等价性反向利用:不是从 NN 到核,而是从 MPS 构造出核,再证明带核的单隐层 NN 与 MPS 等价。
本文的位置:作者将 MPS 的表示能力问题拆成三个层次——布尔函数的精确表示、连续函数的稠密性、以及通过 NN 等价性获得的核函数视角。这填补的缺口是:MPS 的表示能力缺乏构造性证明与函数空间刻画。作者明确说:"我们提供了一种构造性方法,用于设计布尔门的 MPS 表示"——这是对已有"存在性"或"实证性"讨论的升级。
子线索聚类¶
- 精确表示(布尔函数):这一簇关心"哪些离散函数可以被张量网络精确实现"。代表:Cohen, Sharir, Shashua (2016) 的卷积算术电路;本文的布尔门构造。
- 近似表示(连续函数):这一簇关心"张量网络函数空间在什么拓扑下稠密"。代表:本文的稠密性定理;更广义的万能逼近定理文献(Cybenko 1989 的 sigmoid 逼近定理是直接参照)。
- 与 NN/核方法的桥接:这一簇将张量网络翻译成更熟悉的机器学习对象。代表:本文的 NN 等价性定理;Stoudenmire, Schwab (2016) 的实证工作。
这个方向在追问的核心问题¶
- Q1:MPS 能精确表示哪些函数?(本文回答:所有布尔函数,通过门构造。)
- Q2:MPS 函数空间在连续函数空间中的稠密性如何?(本文回答:在尺度不变 sigmoid 激活下稠密。)
- Q3:MPS 的归纳偏置(inductive bias)是什么?即它天然偏好哪类函数?(本文回答:核函数编码输入分量间的相关性,核的设计决定表示能力。)
- Q4:MPS 与 NN 的表达力如何换算?(本文回答:带尺度不变 sigmoid 的 MPS ≡ 带核的单隐层 NN。)
已知瓶颈:MPS 的表示能力受限于其"低纠缠"结构——高维纠缠态需要指数级大的 bond dimension。这一瓶颈在本文中体现为:稠密性定理要求 bond dimension 无界增长,且激活函数必须满足特定条件(尺度不变 sigmoid)。
⚠️ 作者的 framing(必须明确标注为作者的说法)¶
作者把缺口 frame 成:"MPS 的表示能力缺乏严格的、构造性的刻画,且与 NN 的联系未被系统建立。" 这使得本文成为"显然的下一步"——先给布尔构造,再给稠密性,最后给 NN 桥接,逻辑上层层递进。
被淡化或回避的竞争路线: - 张量网络的精确复杂度刻画(如 MPS 的 bond dimension 与函数复杂度的精确关系)——作者只给了存在性,未给最优性。 - 与其他张量网络结构(如树张量网络、投影纠缠对态 PEPS)的比较——作者只聚焦 MPS,未讨论更高维结构的表示能力差异。 - 计算可行性:作者证明了表示的存在性,但未讨论构造出的 MPS 是否在计算上可高效训练或采样。
值得研究者去查的问题:引言中是否遗漏了关于 MPS 表示能力的负面结果(如某些函数类需要指数级 bond dimension)?作者没有引用关于张量网络表达力下界的工作(如 Glasser et al. 2019 关于张量网络与电路复杂度的讨论)——这是否是刻意回避?
张力¶
未见明显对立引用。但存在一个微妙的张力:稠密性定理(近似任意连续函数)与 MPS 的低纠缠限制(只能高效表示低纠缠态)之间的张力。作者通过允许 bond dimension 无界增长来化解,但这意味着"稠密性"在实践中的意义有限——需要多大的 bond dimension 才能达到给定精度?作者未给出定量界。
二、最核心、最简单的例子 / 数学问题¶
第一步:符号、模型、可观测数据¶
在展开技术细节之前,先立清记号。本文的核心对象如下:
- 输入:\(\mathbf{x} = (x_1, \ldots, x_d) \in \mathcal{X}^d\),其中 \(\mathcal{X}\) 是输入域。布尔情形 \(\mathcal{X} = \{0,1\}\);连续情形 \(\mathcal{X} \subset \mathbb{R}\)(紧集)。
- MPS 函数:\(f_{\text{MPS}}(\mathbf{x}) = \sum_{\alpha_1, \ldots, \alpha_{d-1}} A_1[x_1]_{\alpha_1} A_2[x_2]_{\alpha_1, \alpha_2} \cdots A_d[x_d]_{\alpha_{d-1}}\),其中 \(A_i[x_i]\) 是 \(D_{i-1} \times D_i\) 矩阵(\(D_0 = D_d = 1\)),\(D_i\) 是 bond dimension。这是参数/estimand——要构造或逼近的对象。
- 激活函数:\(\sigma: \mathbb{R} \to \mathbb{R}\),如尺度不变 sigmoid(满足 \(\sigma(\lambda t) = \sigma(t)\) 对 \(\lambda > 0\),即齐次零度函数)。这是已知的模型组件。
- 核函数:\(K(\mathbf{u}, \mathbf{v})\),由激活函数诱导(如 \(K(\mathbf{u}, \mathbf{v}) = \mathbb{E}_{w \sim \mathcal{N}(0,I)}[\sigma(w^\top \mathbf{u}) \sigma(w^\top \mathbf{v})]\))。这是衍生对象,连接 MPS 与 NN。
- 目标函数类:\(C(\mathcal{K})\)——紧集 \(\mathcal{K} \subset \mathbb{R}^d\) 上的连续函数空间。这是要逼近的目标。
- 布尔函数:\(g: \{0,1\}^d \to \{0,1\}\)。这是离散目标。
- 可观测数据:本文是纯理论,无数据。但概念上,若用于监督学习,可观测数据是 \((\mathbf{x}_i, y_i)\) 对,\(y_i = f^*(\mathbf{x}_i) + \varepsilon_i\),其中 \(f^*\) 是未知目标函数。MPS 作为估计量 \(\hat{f}_{\text{MPS}}\)。
- 潜在/不可观测量:本文无因果推断意义上的潜在结果。但"最优 bond dimension"(给定精度下所需的最小 \(D\))是隐含的、未直接刻画的量——它决定 MPS 的统计效率与计算成本。
第二步:最小内核¶
剥掉所有一般性设定后,本文的核心数学命题可以浓缩为一个构造 + 一个稠密性:
最小内核(布尔情形):证明任意布尔函数 \(g: \{0,1\}^d \to \{0,1\}\) 都可以被一个 MPS 精确表示。剥掉所有技术细节后,这等价于证明:NAND 门(或任何通用门集)可以被 MPS 实现。因为 NAND 门是布尔电路的全功能基(functional complete),一旦 NAND 可被 MPS 实现,任意布尔函数(作为 NAND 门的组合)也可被实现——只需将 MPS 的 bond dimension 设为与电路规模相关的值。
为什么这是最小内核?因为布尔函数的精确表示是连续函数逼近的"离散骨架"——如果连离散情形都无法精确实现,连续情形的稠密性就无从谈起。作者的构造策略是:先给出 AND、OR、NOT 门的 MPS 表示,再组合成 NAND,最后归纳出任意布尔函数。
最小内核(连续情形):证明带尺度不变 sigmoid 激活的 MPS 函数空间在 \(C(\mathcal{K})\) 中稠密。剥掉一般性后,这等价于证明:MPS 可以逼近"单变量函数乘积的和",即形如 \(\sum_{k=1}^r \prod_{i=1}^d \phi_{k,i}(x_i)\) 的函数。因为 Stone-Weierstrass 定理告诉我们:如果 MPS 函数空间构成一个包含常数、分离点、且在逐点乘法下封闭的代数,则它在 \(C(\mathcal{K})\) 中稠密。作者的证明路线正是验证这三条。
为什么这个内核"一看就懂":布尔构造是"搭积木"——用基本门拼出任意函数;连续稠密性是"用代数逼近"——验证 Stone-Weierstrass 的三个条件。两者都不需要读者预先掌握张量网络的深层理论。
这个内核难在哪:布尔构造的难点在于 MPS 的"局部张量"只能看到相邻位置的输入——如何用局部信息实现全局的布尔逻辑?作者的技巧是让 bond dimension 携带"中间计算结果",类似于电路中的"线"传递信号。连续情形的难点在于尺度不变 sigmoid 不是多项式——Stone-Weierstrass 要求代数封闭性,而 sigmoid 的乘积不一定是 sigmoid 的线性组合。作者的技巧是利用尺度不变性(齐次零度)将 sigmoid 的乘积转化为"同一函数在不同缩放下的和",从而保持代数封闭。
三、这篇论文做了什么¶
三句话¶
① 研究了什么问题:MPS 作为函数逼近器的表示能力——能否精确实现任意布尔函数、能否稠密逼近连续函数、以及这种能力如何通过核函数/NN 等价性来理解。 ② 核心工具/方法:构造性布尔门设计(AND/OR/NOT → 任意布尔函数)、Stone-Weierstrass 定理(验证 MPS 函数空间是闭代数)、以及 MPS-NN 等价性(将 MPS 映射为带核的单隐层 NN)。 ③ 主要结论:任意布尔函数可被 MPS 精确实现;带尺度不变 sigmoid 激活的 MPS 函数空间在紧集连续函数空间中稠密;MPS 等价于带特定核(如多项式核)的单隐层 NN;无限宽 MPS 实现高斯过程。
关键设定与假设¶
- MPS 结构:\(d\) 个张量 \(A_i[x_i]\) 的缩并,bond dimension \(D_i\) 可随 \(d\) 增长。这是标准设定,无额外假设。
- 布尔情形:输入 \(\mathbf{x} \in \{0,1\}^d\),输出标量。假设:MPS 的 bond dimension 可以随函数复杂度增长(无预算约束)。
- 连续情形:输入 \(\mathbf{x} \in \mathcal{K} \subset \mathbb{R}^d\)(紧集)。假设:激活函数 \(\sigma\) 是尺度不变 sigmoid,即 \(\sigma(\lambda t) = \sigma(t)\) 对所有 \(\lambda > 0\)。这个假设比一般 sigmoid(如 logistic)更强——它排除了 \(\sigma(t) = 1/(1+e^{-t})\),因为后者不满足齐次零度。作者用这个假设来保证 MPS 函数空间的代数封闭性。
- NN 等价性:单隐层 NN 的隐层宽度 \(m\) 对应 MPS 的 bond dimension \(D\)。核函数 \(K(\mathbf{u}, \mathbf{v})\) 由激活函数诱导,具体形式取决于 \(\sigma\) 的选择。
- 相比已有文献:作者放宽了对 MPS 结构的限制(允许任意 bond dimension),但强化了对激活函数的限制(尺度不变 sigmoid)。相比 Cybenko (1989) 的通用逼近定理(只需 sigmoid 有界且非常数),本文的激活函数条件更严,但结论更具体——给出了 MPS 特有的构造。
主要结果¶
结果 1(布尔精确表示):任意布尔函数 \(g: \{0,1\}^d \to \{0,1\}\) 可被 MPS 精确实现。证明是构造性的:先给出 NOT、AND、OR 的 MPS 表示(每个门的 bond dimension 为常数),再组合成 NAND 门,最后用 NAND 的全功能性归纳出任意布尔函数。关键点:MPS 的 bond dimension 随电路深度增长,但每个门的局部张量是稀疏的(大部分元素为零),因此表示是高效的。
结果 2(连续稠密性):设 \(\sigma\) 为尺度不变 sigmoid,则 MPS 函数空间 \(\mathcal{F}_{\text{MPS}}\) 在 \((C(\mathcal{K}), \|\cdot\|_\infty)\) 中稠密。证明分三步: 1. 常数函数:选择适当的 bond dimension 和权重,MPS 可以输出常数。 2. 分离点:对任意 \(\mathbf{u} \neq \mathbf{v}\),存在 MPS 函数 \(f\) 使得 \(f(\mathbf{u}) \neq f(\mathbf{v})\)。 3. 代数封闭:两个 MPS 函数的逐点乘积仍是 MPS 函数(通过增加 bond dimension 实现)。 然后应用 Stone-Weierstrass 定理。
结果 3(NN 等价性):带尺度不变 sigmoid 激活的 MPS 等价于带核函数 \(K\) 的单隐层 NN。具体地,MPS 的缩并过程可以重写为 \(\sum_{k=1}^D \sigma(w_k^\top \mathbf{x} + b_k)\) 的形式,其中 \(w_k\) 由 MPS 张量编码,\(D\) 是 bond dimension。核函数 \(K(\mathbf{u}, \mathbf{v}) = \sum_{k=1}^D \sigma(w_k^\top \mathbf{u}) \sigma(w_k^\top \mathbf{v})\) 自然出现,且当 \(D \to \infty\) 时收敛到连续核。
结果 4(高斯过程):无限宽 MPS(\(D \to \infty\))实现高斯过程,其协方差核由激活函数和输入分布决定。这是 Neal (1996) 结果的 MPS 类比。
证明路线与技术技巧¶
整体路线(3-5 步主干):
- 布尔构造:从基本门出发,逐步组合。每一步验证 MPS 的缩并规则可以模拟电路的信号传递。
- 连续逼近:将连续函数问题转化为布尔函数问题的"极限"——先用阶梯函数逼近连续函数,再用 MPS 精确表示阶梯函数(通过布尔构造),最后取极限。
- 代数验证:直接验证 Stone-Weierstrass 的三个条件。这是最技术性的一步,需要构造性地证明 MPS 函数空间的乘法封闭性。
- NN 映射:将 MPS 的缩并重写为 NN 的前向传播,识别出核函数。
- 极限分析:取 \(D \to \infty\),证明 MPS 的随机初始化(权重服从特定分布)诱导出高斯过程。
关键跳跃点:
- 乘法封闭性:两个 MPS 函数的乘积需要 bond dimension 从 \(D_1, D_2\) 增长到 \(D_1 \times D_2\)。证明的关键是构造新的局部张量 \(C_i[x_i] = A_i[x_i] \otimes B_i[x_i]\)(Kronecker 积),使得缩并结果等于两个 MPS 函数的乘积。这个技巧在张量网络文献中称为"tensor product of MPS",但作者给出了自包含的证明。
- 尺度不变 sigmoid 的作用:齐次零度性质 \(\sigma(\lambda t) = \sigma(t)\) 保证了 \(\sigma(w^\top \mathbf{x})\) 在缩放 \(w\) 时不变,这使得 MPS 的局部张量可以吸收缩放因子而不改变函数值。没有这个性质,乘法封闭性会失败。
- 布尔到连续的桥梁:作者用"指示函数"作为中间层——先证明 MPS 可以实现 \(\mathbb{1}\{x_i \in [a,b]\}\) 形式的函数,再通过 Stone-Weierstrass 推广到任意连续函数。
技术技巧点名:
- Kronecker 积构造:用于乘法封闭性证明。
- Stone-Weierstrass 定理:核心逼近工具。
- 随机特征映射:用于 NN 等价性和高斯过程分析。
- 稀疏张量设计:布尔门的 MPS 表示中,局部张量大部分为零,这保证了构造的效率。
真实例子与应用¶
本文为纯理论,无实证例子。 但作者在讨论部分给出了两个说明性构造: - 布尔例子:显式构造了 AND 门的 MPS 表示(bond dimension 2),展示了如何用局部张量编码逻辑运算。 - 连续例子:构造了 \(f(x_1, x_2) = x_1 x_2\) 的 MPS 表示(bond dimension 2),说明多项式函数可以高效表示。
这些例子用于验证理论构造的正确性,而非实际应用。
🔎 结论是否比证明窄¶
需要指出的几个点:
- 稠密性定理的激活函数限制:作者只证明了尺度不变 sigmoid 的情形。在讨论中,作者声称"类似结果对更一般的激活函数也成立",但未给出证明。这是一个 conjecture 被表述为 claim 的地方。
- bond dimension 的增长速率:作者证明了存在性,但未给出逼近速率(如达到 \(\epsilon\) 精度所需的 bond dimension 下界)。在 Stone-Weierstrass 证明中,逼近速率取决于阶梯近似的层数,但作者未量化。
- 高斯过程的协方差核:作者指出无限宽 MPS 实现高斯过程,但未给出协方差核的显式形式(除非激活函数和输入分布给定)。这比 Neal (1996) 的经典结果更弱——后者给出了核的积分表达式。
- NN 等价性的方向:作者证明了 MPS → NN 的方向,但未证明 NN → MPS 的方向(即任意单隐层 NN 是否可被 MPS 表示)。这使得"等价性"的表述略强于实际证明。
四、开放问题¶
以下开放问题均扎根于本文的具体语句:
-
逼近速率的刻画:本文证明了稠密性,但未给出"给定精度 \(\epsilon\) 和 bond dimension \(D\),逼近误差的上界"。作者在 Stone-Weierstrass 证明中隐含了存在性,但未量化。要确认这是否为真 gap,可查阅近期关于张量网络逼近速率的工作(如 Bach 2017 关于 tensor train 逼近的 Sobolev 空间结果)。
-
一般激活函数的稠密性:作者在讨论中声称"类似结果对更一般的激活函数也成立",但未证明。这是一个明确的 conjecture。要确认,可尝试将 Stone-Weierstrass 的代数封闭性验证推广到其他激活函数(如 ReLU——但 ReLU 不满足齐次零度,可能需要不同的证明策略)。
-
NN → MPS 的逆向等价:作者证明了 MPS → NN,但未证明 NN → MPS。如果逆向成立,则 MPS 与单隐层 NN 的表示能力完全等价;如果不成立,则 MPS 是 NN 的真子集。这是一个可检验的开放问题。
-
bond dimension 与函数复杂度的精确关系:布尔构造中,bond dimension 随电路深度增长,但作者未给出最优性下界。是否存在需要指数级 bond dimension 的布尔函数?这与量子信息中的"纠缠熵面积律"有潜在联系。
-
计算复杂度的桥接:本文的构造是存在性的,但构造出的 MPS 是否可在多项式时间内训练或采样?作者未讨论。这与您熟悉的 einsum/treewidth 视角直接相关——MPS 的缩并成本由 bond dimension 和拓扑决定,本文的构造是否保持了低缩并成本?
提醒:要确认上述哪条是真 gap,建议查阅近 5 年关于张量网络表示能力的文献(如 Journal of Machine Learning Research 与 SIAM Journal on Mathematics of Data Science 上的相关工作),看它们的 introduction 是否都指向同一问题——若都指向,则为共识性 gap;若互相打架,则为机会。
Maintained by 陈星宇 · Homepage · Source on GitHub