第 5 章 算子网络

连续复合与按域分段可以交错进行，使不同输入经过不同的局域作用。本章引入算子网络，明确每个输入的求值如何唯一终止，并把网络作用分解到各条实际路径上。在此基础上，将局部距离界与零化判据应用于实际发生域，并区分网络所表示的算子与实现它的节点、路径结构，研究保持外延的表示变换及前接算子形成的复合。

5.1 算子转移图与有限算子网络

在 § 4.4 的分段构造中，不同输入可以进入不同的局域算子。当各步输出继续参与后续作用时，我们还需记录局域算子之间的连接关系，以及哪些输出可以沿相应连接进入下一步。

同一点值可能出现在不同的计算位置，并在那里接受不同的后续作用。因此，我们用节点标记这些位置，将所在节点与当前点值共同记录为计算状态。下面先定义记录局域算子及其连接条件的算子转移图，再在此基础上定义有限算子网络。

定义（算子转移图）：一个有限算子转移图 $\mathcal T$ 由以下数据构成。

(i) 给定有限有向图

(ii) 对每个节点 $\beta\in V_{\mathcal T}$，给定局域算子 $f_\beta\in\mathcal{X}_{\mathrm{op}}$，并要求其定义域非空。记

不同节点的定义域可以重叠，局域算子在重叠处也可以取不同的值。

(iii) 对每条边 $(\beta,\gamma)\in E_{\mathcal T}$，给定非空转移域

同一源节点的不同转移域可以相交。带节点标签的一步转移关系定义为：

图 5.1（算子转移图的结构）：节点携带局域算子，边携带转移域。分支、汇合与回边可以同时出现；每一步能否沿边继续，仍由局域输出是否落入该边的转移域决定。

定义（转移图求值轨迹）：设 $\mathcal{T}$ 为算子转移图，$\beta_1\in V_{\mathcal{T}}$，$x_1\in U_{\beta_1}$，且 $n\geq 1$。若序列

满足：对每个 $s=1,\ldots,n-1$，有 $(\beta_s,\beta_{s+1})\in E_{\mathcal{T}}$，且

则称它为 $\mathcal{T}$ 中从 $(\beta_1,x_1)$ 开始的长度 $n$ 的求值轨迹。这里长度按节点发生次数计数；$n=1$ 时仅含初始状态，不含节点间转移。

底层图中的节点序列 $\beta_1\to\cdots\to\beta_n$ 只给出候选轨迹；它能否实际发生，还取决于各步输出是否落入对应的转移域。

定义（终止域与终止求值轨迹）：设 $\mathcal T$ 为算子转移图。对节点 $\beta\in V_{\mathcal T}$，记

并定义 $\beta$ 的终止域

终止域由不能沿任何出边继续的局域输出组成。若 $\mathrm{Succ}_{\mathcal T}(\beta)=\emptyset$，则 $T^{\mathcal T}_\beta=f_\beta(U_\beta)$。当 $\mathcal T$ 固定时，简记为 $T_\beta$。

若求值轨迹

满足

则称它为终止求值轨迹，其终止输出为 $f_{\beta_n}(x_n)$。算子转移图本身不要求从给定状态出发的后继唯一，也不要求求值过程必定终止。

例（转移图中的求值）：以带吸收元的实直线为底空间，取五个节点 $\beta_1,\ldots,\beta_5$。各局域算子的定义域均为 $\mathbb R$，作用公式与转移域标在下图中；边旁的条件均施加于源节点的输出 $y$。

图 5.2（算子转移图中的求值）：图中绘出从 $(\beta_1,1)$ 出发、沿 $\beta_3$ 到达 $\beta_4$ 后重复经过回边的一段轨迹。

在 $\beta_1$ 处，输出 $1$ 同时属于通往 $\beta_2$ 与 $\beta_3$ 的转移域，因而有两个合法后继。在 $\beta_4$ 处连续选择回边时，点值每次减 $1$，始终满足该边的转移条件，可以无限继续；当输出不大于 $0$ 时，也可以转入 $\beta_5$ 并终止。

定义（有限算子网络）：设 $U\subseteq\mathcal{X}$（按 第 1 章 的约定不含 $\bot$）。一个定义在 $U$ 上的有限算子网络 $\mathcal{N}$ 是一个底层图为 $G=(V,E)$ 的有限算子转移图，加上入口节点集合 $V_{\mathrm{in}}\subseteq V$ 与入口输入片

并满足以下四条条件。

(i)（入口输入分划）：对每个 $\beta\in V_{\mathrm{in}}$，$U_\beta^{\mathrm{in}}$ 非空，且

(ii)（出边转移域互斥）：对每个节点 $\beta\in V$ 与任意两个不同后继 $\gamma_1\neq\gamma_2$，要求

(iii)（统一有限终止）：存在 $N\in\mathbb N$，使每个 $x\in U$ 都有一条长度不超过 $N$ 的终止求值轨迹，其初始状态为 $(\beta,x)$，其中 $\beta$ 是满足 $x\in U_\beta^{\mathrm{in}}$ 的入口节点。

(iv)（无冗余节点）：对每个 $\beta\in V$，存在 $x\in U$，使从 $x$ 的入口状态出发的终止求值轨迹经过 $\beta$。

由 (i)，每个输入的入口节点唯一；由 (ii)，各步输出要么落入终止域，要么落入唯一出边的转移域。因此，同一输入的终止求值轨迹唯一。下文所说的输入 $x$ 的求值轨迹，均指这条完整的终止求值轨迹。

入口片 $U_\beta^{\mathrm{in}}$ 只规定初始输入的分配，可以是节点定义域 $U_\beta$ 的真子集。入口节点也可以有入边，从而既接收初始输入，也接收前序节点的输出。

条件 (iii) 要求所有输入共用一个有限长度界，逐点有限终止尚不足够。当 $U=\emptyset$ 时，由 (i)、(iv)，入口节点集与节点集均为空，因而边集也为空，各数据族均为空族。因此，空输入域上的网络唯一，称为空网络。下文将有限算子网络简称为算子网络。

定义（网络外延算子与求值深度）：设 $\mathcal N$ 为定义在 $U$ 上的算子网络。定义其外延算子

末端输入属于相应局域算子的定义域，因此终止输出不为 $\bot$，故 $\phi_{\mathcal N}\in\mathcal X_{\mathrm{op}}$，且 $\operatorname{dom}(\phi_{\mathcal N})=U$。域外输入不产生求值轨迹，$\bot$ 是对外延算子的补全。

当 $U\neq\emptyset$ 时，定义 $\mathcal N$ 的求值深度

统一有限长度界保证这个最大值存在；它也是最小的统一长度界。对空网络，约定 $\operatorname{Depth}(\mathcal N)=0$。

例（同一底层图上的有限算子网络）：保持前例的底层图与局域算子，按下图设置出边转移域，并取入口片

它们分划输入域 $U=\{-2,-1,1,2,3\}$。节点 $\beta_4$ 既可接收初始输入，也可接收前序节点的输出。

图 5.3（有限算子网络中的求值）：图中绘出输入 $-2$ 的完整求值轨迹。同一节点可以重复经过，连续调用仍按点值与边域逐步判定。

各节点的出边转移域互斥。对上述五个输入逐步求值，轨迹长度依次为 $6,5,4,3,4$，且这些轨迹经过全部五个节点。因此，这组数据构成求值深度为 $6$ 的有限算子网络。图中的回边得以保留，而入口求值具有统一有限长度界。

引理 5.1（删去冗余节点保持求值）：设一组算子转移图与入口数据满足有限算子网络定义中的 (i)—(iii)。删除不被任何输入的终止求值轨迹经过的节点及其关联边，保留其余局域算子、转移域和入口片，则所得数据构成 $U$ 上的有限算子网络。每个输入的终止求值轨迹及其输出均保持不变，因而按上述方式定义的外延算子在删除前后相等。

证明：记原转移图为 $\mathcal T$，底层图为 $G=(V,E)$。取 (iii) 中的统一长度界 $N$，将输入 $x\in U$ 的唯一终止求值轨迹记为

令

在诱导子图 $G_R=(R,E_R)$ 上保留原局域算子与转移域，得到 $\mathcal T_R$。由各入口片非空，$V_{\mathrm{in}}\subseteq R$，故入口分划不变；保留的转移域仍满足包含关系与出边互斥条件。因此 (i)、(ii) 仍成立。

对 $x\in U$，$\tau_x$ 的每个节点均属于 $R$，故每次转移所用的边都属于 $E_R$，相应转移域未变。另一方面，对任意 $\beta\in R$，

因此 $\tau_x$ 的末端输出仍落入终止域。由入口与后继的唯一性，删除后输入 $x$ 的终止求值轨迹 $\tau_x^R$ 满足

这给出 (iii)；按 $R$ 的定义及上述轨迹等式，(iv) 也成立，故所得数据构成有限算子网络。

记删除前后的外延算子分别为 $\phi$ 与 $\phi_R$。轨迹与局域算子均保持不变，故

于是 $\phi_R=\phi$。$\square$

5.2 网络对象空间与外延读出

为了在网络之间定义读出、伪度量与商，先将有限网络统一编码，并据此构造网络对象空间。

引理 5.2（有限网络的编号编码）：设 $\mathcal N$ 为节点集 $V$ 有限的算子网络。令 $n=|V|$，并记

给定双射 $e:V\to[n]$，将节点、边、局域算子、入口片和转移域统一重编号：

所得 $\widetilde{\mathcal N}$ 是同一输入域 $U$ 上、节点集为 $[n]$ 的有限算子网络。每个输入的中间点与终端输出不变，路径标签逐项经 $e$ 变换；相应路径域相同，求值深度相同，并且

重编号保留节点共享：两个发生原来具有相同节点标签，当且仅当重编号后具有相同标签。

证明：取双射 $e:V\to[n]$。若原边集为 $E$，则重编号后的边集为 $\widetilde E=\{(e(\beta),e(\gamma)):(\beta,\gamma)\in E\}$，入口集为 $\widetilde V_{\mathrm{in}}=e(V_{\mathrm{in}})$。各入口片与转移域仅更换下标，故入口分划、转移域包含关系及出边互斥条件保持。

定义状态之间的双射

由 $\widetilde f_{e(\beta)}=f_\beta$ 与 $\widetilde D_{e(\beta)\to e(\gamma)}=D_{\beta\to\gamma}$，单步转移满足

在终止域公式中将后继节点按 $e$ 换元，得到

因此，对每个 $x\in U$，逐步应用单步转移的等价关系及终止域等式，原终止求值轨迹与重编号后的轨迹对应为

反向沿 $e^{-1}$ 得到逆对应。于是 $|\widetilde\tau_x|=|\tau_x|$，原统一长度界仍适用；每个新节点 $e(\beta)$ 也被原来经过 $\beta$ 的输入轨迹访问，故无冗余节点条件保持。由此，$\widetilde{\mathcal N}$ 是有限算子网络。上述对应保留初始输入，故每条路径与其重编号路径具有同一输入域。

当 $U\neq\emptyset$ 时，取轨迹长度的最大值；当 $U=\emptyset$ 时，两侧深度均为 $0$。又因各中间点及末端局域算子的输出不变，域外两侧均取 $\bot$，可得

最后，由 $e$ 的单射性，

故节点共享关系保持。$\square$

引理 5.3（有限编号网络构成集合）：对给定底集 $\mathcal X$，节点集为某个 $[n]$（$n\in\mathbb N$）、输入域非空的所有有限算子网络，连同唯一空网络，构成一个集合。该集合在配备扩展规范结构后，可再次作为算子空间或网络对象空间构造的底集。

证明：固定 $n$ 后，边集属于 $\mathcal P([n]\times[n])$，节点算子族属于 $(\mathcal X_{\mathrm{op}})^{[n]}$，入口片与边域族分别属于 $\mathcal P(\mathcal X)^{[n]}$ 与 $\mathcal P(\mathcal X)^{[n]\times[n]}$，输入域属于 $\mathcal P(\mathcal X)$。这些都是集合，满足网络条件的数据组成其有限乘积的子集。对 $n\in\mathbb N$ 取不交并，再加入一个空网络，仍为集合。同一论证适用于任何给定底集，因而也适用于上述集合。$\square$

定义（算子网络对象空间）：称 引理 5.3 中的集合为 $\mathcal X$ 上的算子网络对象空间，记为 $\mathcal X_{\mathrm{net}}$。

任意有限标签网络进入该对象空间前，须给定 引理 5.2 中的编号编码。具体计算仍可使用原标签，并保留它与编号之间的双射。

这一约定不对网络取同构商。不同编号给出的数据仍分别作为对象，只有数据本身相同时才是同一对象；节点共享始终由同一网络内的标签相等关系记录。域加细、代数加细、前缀扩展或无环展开若先用有限乘积、不交并或发生位置作标签，则在作为对象空间元素使用时再作编号编码。

空网络记为

其输入域、节点集、入口节点集均为空，外延算子为全未定义算子：

除 $\bot_{\mathrm{net}}$ 外，$\mathcal{X}_{\mathrm{net}}$ 中的每个网络对象均按本章定义具有非空输入域。因而若 $\mathcal N\neq\bot_{\mathrm{net}}$，则 $\mathrm{dom}(\phi_{\mathcal N})\neq\emptyset$。

后文凡对网络输入域使用局部等价记号 $\equiv_U$，均默认 $U\neq\emptyset$；空网络只对应 $\bot_{\mathrm{op}}$，其外延关系按 $\mathcal{X}_{\mathrm{op}}$ 中的等式理解。

定义（网络读出映射）：设 $A\subseteq\mathcal{X}_{\mathrm{net}}$，$P$ 为集合。一个映射

称为 $A$ 上的网络读出映射。它只把网络对象送到某类指定数据，不要求由该数据恢复网络对象。当 $A=\mathcal{X}_{\mathrm{net}}$ 时，称为全网络对象空间上的网络读出映射。

若 $P$ 带有限分量伪度量族 $\mathcal G_P$，则称 $(P,\mathcal G_P,\Gamma)$ 为一个规范网络读出。

定义（算子读出映射）：对每个 $\mathcal N\in\mathcal X_{\mathrm{net}}$，记其外延算子为 $\phi_{\mathcal N}$。称映射

为算子读出映射。

若网络读出映射 $\Gamma:A\to P$ 满足对任意 $\mathcal N_1,\mathcal N_2\in A$，

则称 $\Gamma$ 为外延不变读出。此时 $\Gamma$ 只依赖网络对象的算子读出值。若该条件不成立，则 $\Gamma$ 是表示层读出，只能与具体网络对象一起使用。

算子读出 $\Gamma_{\mathrm{op}}$ 本身是外延不变读出。

对每个 $i\in I$，定义 $\mathcal{X}_{\mathrm{net}}$ 上的外延网络伪度量

记

命题 5.4（有限算子网络的外延规范空间）：$(\mathcal{X}_{\mathrm{net}},\mathcal{G}_{\mathrm{net}}^{\mathrm{op}},\bot_{\mathrm{net}})$ 构成扩展规范空间。

证明：对每个 $i\in I$，$d_{\mathrm{net},i}^{\mathrm{op}}$ 是 $d_{\mathrm{op},i}$ 沿算子读出 $\Gamma_{\mathrm{op}}$ 的拉回，因此自距零、对称性和三角不等式由 $d_{\mathrm{op},i}$ 逐项继承。

若 $\mathcal N\neq\bot_{\mathrm{net}}$，则 $\mathcal N$ 的输入域非空，故

而 $\phi_{\bot_{\mathrm{net}}}=\bot_{\mathrm{op}}$。由 命题 1.2 中算子规范空间的吸收元隔离性，

从而

另一方面，由扩展规范空间公理取 $z\neq\bot$。取入口域为 $\{z\}$、局域算子为 $\mathrm{id}_{\mathcal X}$ 的单节点网络，得到一个不同于 $\bot_{\mathrm{net}}$ 的网络对象，故非吸收元部分非空。于是 $\mathcal{G}_{\mathrm{net}}^{\mathrm{op}}$ 满足扩展规范空间公理。$\square$

注（外延网络伪度量的分辨范围）：外延网络伪度量只比较 $\phi_{\mathcal N_1}$ 与 $\phi_{\mathcal N_2}$。有效结构、路径结构与节点共享关系属于表示层信息，不由 $\mathcal{G}_{\mathrm{net}}^{\mathrm{op}}$ 读取。

命题 5.5（外延商与算子空间）：在 $\mathcal{X}_{\mathrm{net}}$ 上定义关系

则 $\sim_{\mathrm{op}}$ 是等价关系。记 $[\mathcal N]$ 为 $\mathcal N$ 关于 $\sim_{\mathrm{op}}$ 的等价类，则 $\Gamma_{\mathrm{op}}$ 诱导双射

此外，对任意代表元 $\mathcal N_1,\mathcal N_2$ 与任意 $i\in I$，

证明：$\sim_{\mathrm{op}}$ 是等价关系，因为它是映射

的纤维关系。算子读出 $\Gamma_{\mathrm{op}}$ 在商集上给出良定义映射 $\overline{\Gamma}_{\mathrm{op}}$。该映射单射由商关系定义直接得到。

下面证明满射。对 $\bot_{\mathrm{op}}$，空网络 $\bot_{\mathrm{net}}$ 满足 $\phi_{\bot_{\mathrm{net}}}=\bot_{\mathrm{op}}$。

对任意 $\phi\in\mathcal{X}_{\mathrm{op}}$ 且 $\phi\neq\bot_{\mathrm{op}}$，取

构造单节点网络：节点集为 $\{\beta\}$，无边，入口节点为 $\beta$，入口输入片 $U_\beta^{\mathrm{in}}=U$，局域算子 $f_\beta=\phi$。该网络的外延算子等于 $\phi$。故 $\Gamma_{\mathrm{op}}$ 满射，进而 $\overline{\Gamma}_{\mathrm{op}}$ 为双射。

最后一个等式由 $d_{\mathrm{net},i}^{\mathrm{op}}$ 的定义和 $\overline{\Gamma}_{\mathrm{op}}([\mathcal N_a])=\phi_{\mathcal N_a}$（$a=1,2$）直接给出。$\square$

上述外延商也可用于其他外延不变读出。

推论 5.6（外延不变读出的商因子化）：设 $A\subseteq\mathcal X_{\mathrm{net}}$，$\Gamma:A\to P$ 为外延不变读出，$\pi:A\to A/{\sim_{\mathrm{op}}}$ 为限制等价关系的商映射。则存在唯一映射 $\overline\Gamma:A/{\sim_{\mathrm{op}}}\to P$，使

证明：对 $\mathcal N\in A$，以 $[\mathcal N]_A=[\mathcal N]\cap A$ 记其在 $A$ 中的等价类，定义 $\overline\Gamma([\mathcal N]_A)=\Gamma(\mathcal N)$。外延不变性保证该值与代表元选择无关，并给出所需等式；唯一性由 $\pi$ 的满射性得到。$\square$

注（外延相等与零距离）：外延相等必然使所有分量的外延网络伪度量为零，但零距离一般不能反推出外延算子相等。上述外延商按算子相等划分等价类；零距离商则可能进一步合并不同的外延算子。

定义（网络表示）：设 $\phi \in \mathcal{X}_{\mathrm{op}}$，$\emptyset\neq U \subseteq \mathrm{dom}(\phi)$。若输入域为 $U$ 的算子网络 $\mathcal{N}$ 的外延算子 $\phi_{\mathcal{N}}$ 满足

则称 $\mathcal{N}$ 是 $\phi$ 在 $U$ 上的一个网络表示。这里 $\equiv_U$ 为 § 4.5 中的局部等价关系。网络表示不声明唯一性。

注（节点数不是外延不变量）：存在外延算子相同但节点数不同的有限算子网络。

证明：取 $\mathcal X=\{\bot,a\}$，其中 $a\ne\bot$，并令两网的输入域均为 $U=\{a\}$。

单节点网络 $\mathcal N_1$ 取 $V_1=\{\beta\}$、$E_1=\emptyset$，唯一节点 $\beta$ 为入口，且

$$f_\beta=\mathrm{id}_{\mathcal X}, \qquad U_\beta^{\mathrm{in}}=\{a\}.$$

二节点网络 $\mathcal N_2$ 取两个不同节点 $V_2=\{\beta_1,\beta_2\}$、唯一边 $E_2=\{(\beta_1,\beta_2)\}$，唯一入口为 $\beta_1$，且

$$f_{\beta_1}=f_{\beta_2}=\mathrm{id}_{\mathcal X}, \qquad U_{\beta_1}^{\mathrm{in}}=\{a\}, \qquad D_{\beta_1\to\beta_2}=\{a\}.$$

输入 $a$ 在两网中的求值轨迹均唯一终止，长度分别为 $1$ 与 $2$，并经过各自的全部节点，故两者均为有限算子网络。对任意 $x\in\mathcal X$，

$$\phi_{\mathcal N_1}(x)=\phi_{\mathcal N_2}(x) =\begin{cases} a,&x=a,\\ \bot,&x=\bot, \end{cases} =\mathrm{id}_{\mathcal X}(x).$$

但 $|V_1|=1$、$|V_2|=2$，故节点数不能由外延算子唯一决定。$\square$

5.3 路径分解与前缀发生

设 $\mathcal N\in\mathcal X_{\mathrm{net}}$，其输入域为 $U$。对 $x\in U$，由有限算子网络定义得到唯一有限终止轨迹，记其节点标签序列为路径映射

固定网络 $\mathcal{N}$ 时，简写为 $p(x)$。称 $p_{\mathcal{N}}(x)$ 为 $x$ 的网络路径。对应路径链为

对任意有限节点序列 $p=(\beta_1,\ldots,\beta_r)$，定义路径域

固定 $\mathcal{N}$ 时，简写为 $U_p$。

定义可达路径集

将 图 5.3 中输入 $-2$ 对应的路径展开，可直接看出网络节点与路径链中各次调用的对应关系。

图 5.4（从网络路径到算子链）：上方标出输入 $-2$ 在网络中经过的节点和边，下方按调用次序展开为算子链，箭头旁标出传递的点值。节点 $\beta_4$ 在网络中只有一个，在这条路径中被调用三次；路径链的复合表达式按算子作用顺序从右向左书写。

命题 5.7（路径分解与可达路径有限性）：

(i)（路径分解） $\{U_p\}_{p\in\mathcal{P}(\mathcal{N})}$ 构成 $U$ 的分划，且对任意 $x\in U$，

当 $U=\emptyset$ 时，可达路径族为空；这里将空族视为空集的分划。

(ii)（可达路径族有限性） 设 $n=|V|$。则 $\mathcal{P}(\mathcal{N})$ 为有限集，且

空网络满足 $n=\operatorname{Depth}(\mathcal N)=0$，此时右侧为空和，取值为 $0$。

证明：

(i) 由有限算子网络定义，每个 $x\in U$ 存在唯一终止轨迹，其节点标签序列有限，记为 $p(x)$。路径域是映射

的非空原像族，因此两两不交并覆盖 $U$。若 $p(x)=(\beta_1,\ldots,\beta_r)$，求值定义逐步给出

(ii) 由求值深度定义，每条可达路径长度不超过 $\operatorname{Depth}(\mathcal N)$。长度为 $r$ 的节点序列数至多为 $n^r$，因此可达路径数不超过所有长度 $1\leq r\leq\operatorname{Depth}(\mathcal N)$ 的节点序列总数。若 $n=0$，则只能是空网络，路径族为空，右侧空和为 $0$。$\square$

定义（路径分段表达与读出）：$\mathcal{N}$ 在 $U$ 上的路径分段表达定义为

这里的下标 $p$ 只用于枚举路径片，不作为表达的数据保留；表达记录各路径域及其复合算子，不记录节点标签序列。以 $\mathcal X_{\mathrm{net}}$ 为定义域、全部路径分段表达构成的集合为值域，映射 $\mathcal N\mapsto\Gamma_{\mathrm{path}}(\mathcal N)$ 称为路径分段读出。遗忘分段结构后得到外延算子在 $U$ 上的限制；再连同域外取吸收元的约定，得到算子读出 $\Gamma_{\mathrm{op}}$。

注（路径分段表达与分段算子）：当 $U\ne\varnothing$ 时，命题 5.7(i) 表明 $\phi_{\mathcal{N}}$ 在 $U$ 上局部等价于路径分段表达 $\Gamma_{\mathrm{path}}(\mathcal N)$ 所给出的分段算子。路径内部由 第 4 章 的链代数处理；路径之间的比较由 § 4.4 的分段算子工具处理。

为记录路径中的中间调用，下面引入可达路径前缀及其对应的输入、输出域。

定义（可达前缀与发生域）：有限算子网络 $\mathcal N$ 的可达路径前缀集为

可达路径有限且各自长度有限，故该集合有限。同一节点可以在一个前缀中重复出现。

对 $q=(\beta_1,\ldots,\beta_s)\in\operatorname{Pref}(\mathcal N)$，记以 $q$ 为前缀的完整路径族及其初始输入集合为

方括号表示路径筛选，$\ast$ 表示任意有限节点序列，允许为空。记 $c_q=f_{\beta_s}\circ\cdots\circ f_{\beta_1}$。该前缀发生的当前输入域与当前输出域分别为

$U[q\ast]$ 记录产生该前缀的初始输入，$D_q^{\mathrm{in}}$ 与 $D_q^{\mathrm{out}}$ 记录末节点作用前后的点值。同一节点在不同前缀中出现时，对应的当前输入、输出域可以不同。

注（节点标签与身份）：在网络表示中，求值状态由当前节点和当前点共同决定，而不是由点值 $y\in\mathcal{X}$ 单独决定。节点身份由网络结构中的顶点给出；共享局部计算应在网络数据中表现为同一个顶点被多条路径经过。

由 § 5.1 的无冗余节点条件，每个节点 $\beta\in V$ 都出现在某条 $p\in\mathcal{P}(\mathcal{N})$ 中。节点层面的数据以 $V$ 为索引；同一节点的不同路径发生则由相应的可达前缀区分。

5.4 有效约化与有效等价

沿各条可达路径收集节点的实际输入，可以把局域算子限制到求值真正使用的区域。节点 $\beta$ 的实际输入集合由所有到达它的前缀的当前输入域取并得到。

定义（节点实际输入域）：设 $\mathcal N$ 为算子网络。对节点 $\beta\in V$，定义

上标 $\mathrm{eff}$ 表示网络从输入域 $U$ 出发实际到达或实际使用的有效层数据。

由无冗余节点约定，$U_\beta^{\mathrm{eff}}\neq\emptyset$，且

节点算子在 $U_\beta\setminus U_\beta^{\mathrm{eff}}$ 上的取值不会被网络从输入域 $U$ 出发的任何求值过程调用。

定义（有效约化网络）：$\mathcal{N}$ 的有效约化 $\mathcal{N}^{\mathrm{eff}}$ 是按如下方式得到的网络：保留节点集，将节点 $\beta$ 的局域算子替换为限制算子

入口节点集合不变，入口输入片取

将原边域与终止域限制到节点实际产生的输出上，得到有效边域与有效终止域：

若有效边域为空，则不记录该边。

命题 5.8（有效约化保持外延）：对任意定义在非空输入域 $U$ 上的算子网络 $\mathcal{N}$，上述有效约化数据构成同一输入域上的有限算子网络 $\mathcal N^{\mathrm{eff}}$，且

证明：先核对局域算子与转移域。由 $U_\beta^{\mathrm{eff}}\neq\emptyset$，$f_\beta^{\mathrm{eff}}\in\mathcal{X}_{\mathrm{op}}$ 且

入口输入片满足 $U_\beta^{\mathrm{in},\mathrm{eff}}\subseteq U_\beta^{\mathrm{eff}}$。对有效边 $(\beta,\gamma)$，有

若 $y\in f_\beta(U_\beta^{\mathrm{eff}})$，则某个初始输入的求值轨迹在节点 $\beta$ 实际产生输出 $y$。当 $y\in D_{\beta\to\gamma}$ 时，该轨迹下一步进入 $\gamma$；当 $y\in T_\beta$ 时，该轨迹在 $\beta$ 终止。反之，实际经过该边或在该节点终止的输出都属于相应交集。因此，上述有效边域与有效终止域恰好记录实际经过的边输出与终止输出。

由原网络的出边互斥性与终止域定义，这些域两两不交，且

其中空有效边域不记录为边。

取任意 $x\in U$，设其在 $\mathcal{N}$ 中的路径为

对每个 $s$，第 $s$ 步当前输入属于对应前缀发生的 $D_q^{\mathrm{in}}$，因而属于 $U_{\beta_s}^{\mathrm{eff}}$。有效约化在该点上使用的限制算子与原 $f_{\beta_s}$ 取值相同。

原路径中实际经过的边输出属于对应的 $D_{\beta_s\to\beta_{s+1}}^{\mathrm{eff}}$；最终输出属于 $T_{\beta_r}^{\mathrm{eff}}$。故 $\mathcal{N}^{\mathrm{eff}}$ 对 $x$ 经过同一节点序列并得到同一输出。

原统一长度界与无冗余节点条件因此仍然成立，故上述数据满足有限算子网络的全部条件。又因每个输入的输出相同，两者外延算子在 $U$ 上局部等价。$\square$

路径分段表达只记录各路径域及相应的复合算子。若进一步保留各路径中有序的节点标签与局域算子因子，则可恢复有效网络的分段结构。

定义（标记分段算子表达与读出）：$\mathcal{N}$ 在 $U$ 上的标记分段算子表达为路径域分划下的有序标记因子族

每个有序对 $(\beta_n,f_{\beta_n})$ 同时记录第 $n$ 个因子的节点身份与局域算子。标签不参与函数求值；标签相同表示对应因子来自同一个节点，标签不同则即使两个局域算子外延相同，也不视为同一个节点。对每个路径片按顺序复合所记录的局域算子，并遗忘因子标签，便得到 $\Gamma_{\mathrm{path}}(\mathcal N)$。

以 $\mathcal X_{\mathrm{net}}$ 为定义域、全部标记分段算子表达构成的集合为值域，映射 $\mathcal N\mapsto\Gamma_{\mathrm{tag}}(\mathcal N)$ 称为标记分段读出。逐片求取有序因子复合并遗忘因子标签，得到路径分段读出；再遗忘分段结构并按域外吸收元约定求值，得到算子读出：

注（路径分段不由外延决定）：存在外延算子相同而路径分段读出不同的有限算子网络，因而标记分段读出也一般不由外延算子决定。

证明：取 $\mathcal X=\{\bot,a,b\}$，其中三点互异，并令输入域为 $U=\{a,b\}$。单节点网络 $\mathcal N_1$ 的局域算子为 $\mathrm{id}_{\mathcal X}$，入口片为 $U$，无边。网络 $\mathcal N_2$ 取两个无边的入口节点，局域算子均为 $\mathrm{id}_{\mathcal X}$，入口片分别为 $\{a\}$ 与 $\{b\}$。两网的每个输入均经一步终止，各节点均被经过，且外延算子都是 $\mathrm{id}_{\mathcal X}$。但

$$\Gamma_{\mathrm{path}}(\mathcal N_1)=\{U:\mathrm{id}_{\mathcal X}\}, \qquad \Gamma_{\mathrm{path}}(\mathcal N_2)=\{\{a\}:\mathrm{id}_{\mathcal X},\ \{b\}:\mathrm{id}_{\mathcal X}\}.$$

两者的路径域分划不同，故路径分段读出不同。若标记分段读出相同，遗忘标签并逐片复合后，路径分段读出也应相同，矛盾。$\square$

当若干因子具有同一标签时，它们记录同一个节点算子。标记分段算子表达的同构必须同时保持路径域分划、各片内因子顺序、因子标签、各因子在相应实际输入域上的局部等价关系，以及同标签因子的共享关系。

命题 5.9（标记分段算子表达决定有效网络）：标记分段算子表达 $\Gamma_{\mathrm{tag}}(\mathcal N)$ 决定 $\mathcal{N}^{\mathrm{eff}}$ 的节点实际输入域、入口输入片、有效边域、有效终止域与外延算子，至多差一个节点重命名。

证明：对路径 $p=(p_1,\ldots,p_{|p|})$，在本证明中记

有效节点由因子标签给出。由于有序因子列被保留，每个前缀复合 $c_{p,n}$ 均由表达本身确定。若标签 $\beta$ 对应有效节点，则其实际输入域由

给出，对应有效节点算子为 $f_\beta|_{U_\beta^{\mathrm{eff}}}$。对入口标签 $\beta$，入口输入片由路径首位给出：

对所有相邻因子标签为 $\beta,\gamma$ 的路径取并，得到对应有效边域

对终止标签 $\beta$，终止域由路径末位给出：

外延算子由路径分段表达

给出。上述恢复只依赖路径域分划与有序标记因子列；不同的节点标签命名不改变恢复出的有效网络同构类。$\square$

定义（外延等价与有效等价）：设 $\mathcal{N}_1$ 与 $\mathcal{N}_2$ 是定义在同一非空输入域 $U$ 上的算子网络。

称 $\mathcal{N}_1$ 与 $\mathcal{N}_2$ 外延等价，记作

若

两网络在 $U$ 外均取 $\bot$，故这里的局部等价等价于外延算子相等，与前面外延商使用的记号一致。

称 $\mathcal{N}_1$ 与 $\mathcal{N}_2$ 有效等价，记作

若二者的标记分段算子表达同构。这里的同构指存在路径重命名与节点标签重命名，使对应路径片相同、对应路径长度相同、片内因子顺序相同、因子标签对应相同，并且对应因子在由对应路径片推出的实际输入域上局部等价。有效等价忽略节点算子在未被实际调用的定义域上的任意延拓。

命题 5.10（有效等价推出外延等价）：若

则

反向一般不成立。

证明：有效等价给出同构的标记分段算子表达，因此对应路径片上的逐因子复合逐点相同。于是

与

在 $U$ 上逐片相同，故外延算子在 $U$ 上局部等价。

反向不成立。取 注 中的单节点恒等网络与二节点恒等链网络。二者外延算子相同，故外延等价；但各自的唯一可达路径长度分别为 $1$ 与 $2$，标记分段算子表达不可能同构，故不有效等价。$\square$

5.5 路径估计、零化与输出覆盖

路径分解把网络在各路径域上的作用写为局域算子的复合。本节在这些实际使用的域上应用前面的算子界与零化工具，考察沿路径的距离估计、阈值分类和输出覆盖。

路径矩阵界

命题 5.11（路径链的矩阵乘积界）：设 $p=(\beta_1,\ldots,\beta_r)\in\mathcal{P}(\mathcal{N})$，并记路径链为

(i)（L 证书继承） 若对每个 $s$ 取

则

(ii)（K 证书继承） 若对每个 $s$ 取

则

在相应前提下，对任意 $x,y\in U_p$ 与 $j\in I$，