通过精确线性代数实现更浅的ReLU网络表示

# 通过精确线性代数实现更浅的ReLU网络表示  
来源：https://arxiv.org/html/2607.21651  

Kilian Rueß（第一作者；其他作者按字母顺序排列）  
纽伦堡工业大学 \{kilian.ruess, christoph.hertrich, moritz.stargalla\}@utn.de  

Florestan Brunck  
哥本哈根大学 \{flbr, jast\}@di.ku.dk  

Moritz Grillo  
马克斯·普朗克数学科学研究所 \{moritz.grillo, martin.winter\}@mis.mpg.de  

Christoph Hertrich  
纽伦堡工业大学 \{kilian.ruess, christoph.hertrich, moritz.stargalla\}@utn.de  

Georg Loho  
柏林自由大学 [email protected]  

Jack Stade  
哥本哈根大学 \{flbr, jast\}@di.ku.dk  

Moritz Stargalla  
纽伦堡工业大学 \{kilian.ruess, christoph.hertrich, moritz.stargalla\}@utn.de  

Matthew Sun [email protected]  

Martin Winter  
马克斯·普朗克数学科学研究所 \{moritz.grillo, martin.winter\}@mis.mpg.de  

###### 摘要  

我们证明，对于每个 \(n \le 10\)，实数 \(n\) 元最大值函数 \(\max_n\) 都可以通过一个具有两个隐藏层的 ReLU 网络精确表示。这些构造是通过将问题简化为精确有理线性代数得到的：在对称约化之后，必要的抵消被编码为关于 \(\mathbb{Q}\) 的有限线性系统，我们通过计算求解并验证了这些系统。\(\max_{10}\) 的表示具有结构化的第一隐藏层，该层仅由成对最大值组成，这一特性使其可以递归地代入更大的网络中。利用这一点，我们证明对于每个 \(n > 10\)，函数 \(\max_n\) 可以被精确表示，所需隐藏层数不超过 \(\lceil \log_5 (n/2) \rceil + 10\)。  

## 2 通过支撑函数与多面体恒等式进行表示  

一个函数 \(f:\mathbb{R}^d \to \mathbb{R}\) 被称为**分段线性**，如果存在一个多面体扇 \(\Sigma\)（即 \(\mathbb{R}^d\) 的一个划分，由以原点为顶点的多面体锥组成），使得 \(f\) 在每个锥 \(\tau \in \Sigma\) 上是线性的。特别地，ReLU 网络计算这样的分段线性函数，并且可以用支撑函数来表示，而支撑函数通过公式  

\[
h_P(y) = \max_{x \in P} \langle x, y \rangle
\]  

与凸多面体 \(P\) 相关联（参见 [6]）。  
一个关键的观察结果是：用支撑函数来表示，通过将问题转化为多面体的符号闵可夫斯基组合，可以将分段线性函数的恒等式系统化。对于多面体 \(P, Q_1, \ldots, Q_r\)，如果存在实数系数 \(c_1, \ldots, c_r\) 使得  

\[
P + \sum_{c_i < 0} (-c_i) Q_i = \sum_{c_i > 0} c_i Q_i,
\]  

则将其称为**符号闵可夫斯基恒等式**。这里的加法是通常的闵可夫斯基和，而减法是通过符号中的负数隐含地表示的：上述等式断言左侧的多面体（作为闵可夫斯基和）等于右侧的多面体。该恒等式意味着一个两隐藏层 ReLU 网络可以计算 \(h_P\)（参见 [7]）。具体来说，如果每个 \(Q_i\) 本身又是一个多面体，并且其支撑函数可以由一个两隐藏层网络表示（例如，\(Q_i\) 是单纯形），那么 \(h_P\) 也可以由一个具有相同隐藏层数的网络表示。  

为了通过符号闵可夫斯基恒等式系统地搜索两隐藏层表示，我们首先将其简化为一个有限线性系统。考虑多面体 \(P, Q_1, \ldots, Q_r\)。符号闵可夫斯基恒等式  

\[
P + \sum_{c_i < 0} (-c_i) Q_i = \sum_{c_i > 0} c_i Q_i
\]  

通过支撑函数转化为函数 \(\mathbb{R}^d \to \mathbb{R}\) 的恒等式  

\[
h_P = \sum_{i=1}^r c_i h_{Q_i}.
\]  

由于所有涉及的支撑函数都是分段线性的，这个恒等式可以通过在一个合适的有限点集上求值来简化为一个有限线性系统。这种简化由以下命题保证。  

一个**完全多面体扇**在 \(\mathbb{R}^n\) 中是指一组以原点为顶点的多面体锥的有限集合，该集合对取面封闭，任意两个锥的交集是每个锥的一个面，并且这些锥的并集覆盖整个 \(\mathbb{R}^n\)。  

###### 命题 2.1。  
设 \(\Sigma\) 是一个完全多面体扇，并考虑多面体 \(P, Q_1, \ldots, Q_r\)，使得每个支撑函数 \(h_P, h_{Q_1}, \ldots, h_{Q_r}\) 在 \(\Sigma\) 的每个锥上是线性的。对于每个锥 \(\tau \in \Sigma\)，令 \(U_\tau\) 为其生成极射线的集合。设  

\[
U = \bigcup_{\tau \in \Sigma} U_\tau.
\]  

定义  

\[
A_{ui} = h_{Q_i}(u), \qquad b_u = h_P(u) \quad (u \in U).
\]  

那么  

\[
h_P = \sum_{i=1}^r c_i h_{Q_i} \quad \Longleftrightarrow \quad Ac = b.
\]  

###### 证明。  
函数 \(h_P - \sum_i c_i h_{Q_i}\) 在 \(\Sigma\) 的每个锥上是线性的。一个锥上的线性函数在该锥上恒为零当且仅当它在锥的极射线上为零。由于 \(\Sigma\) 覆盖 \(\mathbb{R}^d\)，全局恒等式因此等价于有限系统 \(Ac = b\)。∎  

命题 2.1 建议采用以下过程来寻找 \(\max_n\) 的神经网络表示。令 \(P\) 为标准单纯形 \(\operatorname{conv}\{e_1, \ldots, e_n\}\)，它是 \(\max_n\) 的牛顿多面体。选择有前景的候选多面体 \(Q_1, \ldots, Q_r\)，我们已知这些多面体具有两隐藏层表示。利用命题 2.1 将符号闵可夫斯基恒等式简化为有限线性系统，并使用精确有理算术检查该系统是否有解。如果找到解，则意味着 \(\max_n\) 具有两隐藏层表示。如果系统无解，则说明候选多面体集不足以表示 \(\max_n\)。  

## 3 对称化  

设对称群 \(S_n\) 通过坐标置换作用在 \(\mathbb{R}^n\) 上。具体地，对于 \(x \in \mathbb{R}^n\) 和 \(\sigma \in S_n\)，定义  

\[
(\sigma x)_i \coloneqq x_{\sigma^{-1}(i)} \quad \text{对于 } i \in \{1,\ldots,n\}.
\]  

对于任意函数 \(f:\mathbb{R}^n \to \mathbb{R}\)，定义其**对称化**为  

\[
f^{\operatorname{sym}}(x) = \frac{1}{n!} \sum_{\sigma \in S_n} f(\sigma x).
\]  

我们称函数 \(f:\mathbb{R}^n \to \mathbb{R}\) 为**对称的**，如果 \(f^{\operatorname{sym}} = f\)。  

###### 命题 3.1。  
设 \(g:\mathbb{R}^n \to \mathbb{R}\) 是对称的。如果 \(g = \sum_{i=1}^n c_i f_i\)，那么  

\[
g = \sum_{i=1}^n c_i f_i^{\operatorname{sym}}.
\]  

此外，如果 \(f, h:\mathbb{R}^n \to \mathbb{R}\) 是对称的，那么 \(f = h\) 在 \(\mathbb{R}^n\) 上成立当且仅当 \(f = h\) 在 \(\mathcal{C} = \{x \in \mathbb{R}^n : x_1 \le x_2 \le \cdots \le x_n\}\) 上成立。  

###### 证明。  
对称化是线性的，并且固定对称函数，从而得到第一个结论。对于第二个结论，\(\mathbb{R}^n\) 中的每个点都可以通过坐标置换被映到 \(\mathcal{C}\) 中。∎  

因此，为了检查对称候选函数是否等于 \(\max_n\)，只需检查它是否在 \(\mathcal{C}\) 上等于 \(x_n\)。注意，\(\mathcal{C}\) 是辫子排列的一个胞腔，参见 [5]。  

## 4 两隐藏层恒等式的精确搜索  

本节描述用于寻找两隐藏层表示的有限搜索空间。搜索分为三步。首先，我们选择一个受限的两隐藏层 ReLU 块族，其第一隐藏层仅由成对最大值组成。然后，我们取这些块在所有坐标置换上的平均，从而只需在有序锥上测试它们。最后，我们将得到的函数展开为线性项和 hinge 项，并求解相应的有理线性系统。  

### 4.1 两层 ansatz  

令 \(\mathcal{E}_n \coloneqq \{(i,j) \mid 1 \le i \le j \le n\}\) 表示无序索引对的集合，通过列出较小索引来呈现。按照定义，对角元素 \((i,i)\) 也被包含在内。对于 \((i,j) \in \mathcal{E}_n\)，定义  

\[
m_{ij}(x) = \max\{x_i, x_j\}.
\]  

固定 \(k \in \mathbb{N}\)，并令 \(\mathcal{M}_{n,k}\) 表示 \(\mathcal{E}_n\) 中元素的多重集（基数为 \(k\)）的集合。因此，\(\mathcal{M}_{n,k}\) 中的一个元素 \(A\) 是来自 \(\mathcal{E}_n\) 的 \(k\) 个对的集合，按重数计数，因此同一个对可能出现多次。由于 \(\mathcal{E}_n\) 是有限的，集合 \(\mathcal{M}_{n,k}\) 以及由此得到的 \(\mathcal{M}_{n,k} \times \mathcal{M}_{n,k}\) 是有限的。对于每个 \((A,B) \in \mathcal{M}_{n,k} \times \mathcal{M}_{n,k}\)，定义  

\[
\Phi_{A,B}(x) = \max\left\{ \sum_{(i,j) \in A} m_{ij}(x), \sum_{(i,j) \in B} m_{ij}(x) \right\},
\]  

其中每个求和按重数计算。这个函数可以用一个两隐藏层网络表示：第一隐藏层计算成对最大值 \(m_{ij}\)，第二隐藏层计算两个线性组合的最大值。我们询问 \(\max_n\) 是否位于所有对称化函数  

\[
F_{A,B}(x) = n! \, \Phi_{A,B}^{\operatorname{sym}}(x) = \sum_{\sigma \in S_n} \Phi_{A,B}(\sigma x), \qquad (A,B) \in \mathcal{M}_{n,k} \times \mathcal{M}_{n,k}
\]  

的线性张成空间中。在群平均中出现的因子 \(1/n!\) 被省略，因为它只会缩放解系数。出于计算或结构目的，可以将系统限制为所选子族的对 \((A,B)\)；然而，除非另有说明，ansatz 包括 \(\mathcal{M}_{n,k} \times \mathcal{M}_{n,k}\) 中的所有对。  

根据命题 3.1，只需在有序锥 \(\mathcal{C} = \{ x \in \mathbb{R}^n \mid x_1 \le x_2 \le \cdots \le x_n \}\) 上处理。在 \(\mathcal{C}\) 上，第一层函数 \(m_{ij}\) 坍缩为对具有较大索引变量的坐标投影：即，  

\[
m_{ij}(\sigma x) = m_{ij}(x_{\sigma^{-1}(1)}, \ldots, x_{\sigma^{-1}(n)}) = x_{\max\{\sigma^{-1}(i), \sigma^{-1}(j)\}}.
\]  

因此，限制到 \(\mathcal{C}\) 后，第一层是线性的，不会引入额外的断点。对于多重集 \(A \in \mathcal{M}_{n,k}\) 和 \(\sigma \in S_n\)，令  

\[
\ell_{\sigma,A}(x) \coloneqq \sum_{(i,j) \in A} x_{\max\{\sigma^{-1}(i), \sigma^{-1}(j)\}}.
\]  

那么，在 \(\mathcal{C}\) 上，  

\[
F_{A,B}(x) = \sum_{\sigma \in S_n} \max\{ \ell_{\sigma,A}(x), \ell_{\sigma,B}(x) \}.
\]  

利用 \(\max\{u,v\} = u + \operatorname{ReLU}(v-u)\) 并收集相同的差分向量，我们得到  

\[
F_{A,B}(x) = L_{A,B}(x) + \sum_{d \in D_{A,B}} c_{A,B,d} \operatorname{ReLU}\left(d^\top x\right),
\]  

其中 \(L_{A,B}\) 是线性的，\(D_{A,B} \subset \mathbb{Z}^n\) 是有限的，且 \(c_{A,B,d} \in \mathbb{Z}\)。因此，表示 \(\max_n = \sum_{A,B} \lambda_{A,B} F_{A,B}\) 由以下精确方程保证：  

\[
\sum_{A,B} \lambda_{A,B} c_{A,B,d} = 0 \quad \text{对于所有 } d \in \bigcup_{A,B} D_{A,B} \tag{2}
\]  
\[
\sum_{A,B} \lambda_{A,B} L_{A,B}(x) = x_n. \tag{3}
\]  

第一组方程 (2) 表示每个非线性 hinge 项都抵消了。第二个方程 (3) 表示剩下的线性函数是 \(x_n\)，它在有序锥 \(\mathcal{C}\) 上等于 \(\max_n\)。  

#### 4.1.1 模置换枚举  

函数 \(F_{A,B}\) 在交换 \(A\) 和 \(B\) 以及同时重新标记两个多重集中的所有索引下是不变的。因此，只需考虑对 \((A,B)\) 模等价关系  

\[
(A,B) \sim (B,A) \sim (\tau A, \tau B) \sim (\tau B, \tau A), \qquad \tau \in S_n.
\]  

我们用 \(\{\!\!\{\cdots\}\!\!\}\) 表示多重集，重复表示重数。这里，\(\tau A \coloneqq \{\!\!\{ (\min\{\tau(i),\tau(j)\}, \max\{\tau(i),\tau(j)\}) : (i,j) \in A \}\!\!\}\)，保留重数。我们称此关系下的一个等价类为**模板**。等价地，对 \((A,B)\) 可以被视为在顶点集 \(\{1,\ldots,n\}\) 上的双色边重数图：\(A\) 中的对形成一种颜色的边，\(B\) 中的对形成另一种颜色的边，所有边重数被保留。如果 ansatz 允许对角对，则它们由自环表示。交换 \(A\) 和 \(B\) 对应于交换两种边颜色，而对索引的同时置换则对应于重新标记顶点。因此，模板枚举是一个有色多重图同构问题，其中两种颜色本身被视为可互换的。在实现中，每个同构类被替换为一个规范标记的代表。在组装有限线性系统之前，所有证书系数都根据这个规范无序对进行聚合。所需的同构类可以使用标准图同构软件（如 *nauty* [10]）高效枚举。  

### 4.2 最小的有用 \(k\) 值  

参数 \(k\) 控制表达能力和计算 ansatz 的大小。\(\Phi_{A,B}\) 的每个参数确实包含 \(k\) 个成对最大值的和，因此增加 \(k\) 会扩大 ansatz 所能表示的函数类。同时，多重集对 \((A,B)\) 的数量随着 \(k\) 迅速增长。因此，很自然要问，不被理论障碍排除的最小 \(k\) 值是多少。  

###### 命题 4.2。  
令 \(\Delta_k = \operatorname{conv}\{0, e_1, \ldots, e_k\}\)。不存在多面体 \(P_1, \ldots, P_m\) 满足 \(\dim P_r \le 1\)，使得 \(\Delta_{k+1}\) 可以通过一个符号闵可夫斯基恒等式从这些 \(P_r\) 得到。  

（注：命题 4.2 的完整证明被省略？实际上原文中并没有给出证明，只有陈述。根据上下文，该命题表明当 \(k\) 太小时，无法表示某些多面体。）  

## 5 递归放大  

通过锦标赛式的构造，任何针对较小输入数量的表示都可以放大到更大的输入数量：将 \(n\) 个输入分成若干组，每组最多 \(l\) 个输入，对所有组并行应用网络，然后对得到的组最大值重复该过程。如果原始网络有 \(D\) 个隐藏层，那么这种锦标赛式构造加上对不完整组的重复坐标填充，可以以 \(D \lceil \log_l n \rceil\) 个隐藏层表示 \(\max_n\)。  

本文构造的表示具有附加结构：其第一隐藏层完全由成对比较组成。利用这一结构可以实现更高效的放大。每个这样的比较都可以被替换为原始两隐藏层表示的副本，从而使隐藏层数仅增加一层，同时将输入元数乘以 \(\lfloor l/2 \rfloor\)。以下定理形式化了这种代入及其迭代。  

###### 定理 5.1。  
假设 \(\max_l\) 有一个两隐藏层表示 \(\mathcal{B}_l\)，其第一隐藏层仅由成对比较 \(\max\{x_i, x_j\}\) 组成，并且设 \(r = \lfloor l/2 \rfloor \ge 2\)。那么，对于每个整数 \(s \ge 0\)，函数 \(\max_{lr^s}\) 都有一个具有 \(2+s\) 个隐藏层的精确表示，且其第一隐藏层再次仅由成对比较组成。因此，对于每个 \(n \ge 1\)，函数 \(\max_n\) 有至少一个精确表示，其隐藏层数最多为  

\[
2 + \max\left\{0, \left\lceil \log_r \frac{n}{l} \right\rceil \right\}.
\]  

###### 证明。  
我们通过对 \(s\) 归纳构造表示，并保持第一隐藏层的形式作为不变量。对于 \(s=0\)，所需的表示就是 \(\mathcal{B}_l\)。假设该论断对某个 \(s \ge 0\) 成立，并设 \(M = l r^s\)。将 \(rM\) 个输入分成不相交的块 \(S_1, \ldots, S_M\)，每个块大小为 \(r\)，并设  

\[
y_p = \max_{i \in S_p} x_i.
\]  

将 \(\max_M\) 的表示应用于 \((y_1, \ldots, y_M)\) 得到 \(\max_p y_p = \max_i x_i\)。在这个求值中，每个第一层比较变为  

\[
\max\{y_p, y_q\} = \max_{i \in S_p \cup S_q} x_i,
\]