MicroNAS：面向MCU的零样本神经架构搜索

Qiao Y, Xu H, Zhang Y, et al. Micronas: Zero-shot neural architecture search for mcus[C]//2024 Design, Automation & Test in Europe Conference & Exhibition (DATE). IEEE, 2024: 1-2.

第一章 引言与研究动机

在深度学习快速发展的今天，卷积神经网络（CNN）已经成为计算机视觉、语音识别和目标检测等领域的核心技术。然而，设计高性能的CNN架构是一项极具挑战性的任务，需要深厚的专业知识和大量的试错过程。传统的手工设计方法不仅耗时耗力，而且很难在精度和效率之间找到最优平衡点。特别是在边缘计算场景中，微控制器单元（MCU）的严格资源约束使得模型设计变得更加困难。

神经架构搜索（NAS）技术的出现为这一问题提供了自动化解决方案。然而，现有的NAS方法大多需要训练大量的候选网络或构建计算密集的超网络，这使得搜索过程极其耗时。例如，早期的NAS方法需要数千个GPU小时才能完成一次搜索，这在实际应用中是不可接受的。即使是近期提出的高效NAS方法，如ENAS和DARTS，仍然需要大量的计算资源来训练超网络或评估架构性能。

在这样的背景下，加州大学尔湾分校的研究团队提出了MicroNAS，这是一个革命性的零样本NAS框架，专门针对MCU等资源受限的边缘设备设计。MicroNAS的核心创新在于它完全避免了训练过程，通过理论驱动的性能指标来评估网络架构的质量。这种方法不仅大幅降低了搜索成本，还能够在搜索过程中直接考虑硬件约束，确保找到的架构在目标设备上具有优异的实际性能。

第二章 理论基础与相关工作

2.1 神经架构搜索的演进历程

神经架构搜索的发展经历了三个主要阶段。第一代NAS方法基于强化学习或进化算法，通过完整训练每个候选架构来评估其性能。这类方法虽然能够找到高质量的架构，但搜索成本极高，通常需要数百到数千个GPU天。第二代NAS方法引入了权重共享机制，通过训练一个包含所有候选架构的超网络来加速搜索过程。代表性的工作包括ENAS和DARTS，它们将搜索时间从数千GPU小时降低到几个GPU天。第三代NAS方法，也就是零样本NAS，完全避免了训练过程，通过分析网络的固有属性来预测其性能。

零样本NAS的理论基础主要来自深度学习理论的最新进展。研究人员发现，网络在初始化时的某些属性与其训练后的性能存在强相关性。这些属性包括网络的条件数、雅可比矩阵的秩、线性区域的数量等。通过分析这些属性，可以在不进行任何训练的情况下预测网络的潜在性能。

2.2 边缘计算与MCU部署挑战

微控制器单元作为边缘计算的核心硬件平台，具有独特的特点和限制。典型的MCU如STM32系列，其主频通常在几十到几百MHz之间，内存容量从几十KB到几MB不等，存储空间也非常有限。这些硬件约束对深度学习模型的部署提出了严峻挑战。

首先是计算能力的限制。MCU的计算能力通常只有服务器GPU的万分之一甚至更少，这意味着即使是轻量级的模型也可能需要数秒甚至数十秒才能完成一次推理。其次是内存限制，MCU的RAM通常无法容纳完整的模型参数和中间激活值，需要精心设计内存管理策略。最后是能耗约束，许多MCU应用场景需要电池供电，因此模型的能耗效率至关重要。

第三章 MicroNAS框架详解

3.1 整体架构设计

MicroNAS采用了模块化的设计思想，整个框架由四个核心组件构成：性能指标计算模块、硬件指标评估模块、搜索算法模块和部署优化模块。这种设计使得框架具有良好的可扩展性，可以方便地添加新的性能指标或支持新的硬件平台。

框架的工作流程始于定义搜索空间。MicroNAS采用基于单元格（cell）的搜索空间，这是NAS领域的标准做法。每个架构由多个相同的单元格堆叠而成，而每个单元格的内部结构通过有向无环图（DAG）表示。在DAG中，节点代表特征图，边代表操作（如卷积、池化等）。这种表示方法既灵活又高效，能够表达丰富的架构模式。

搜索空间定义完成后，框架会对每个候选架构计算一系列性能指标。这些指标包括反映网络可训练性的神经切线核（NTK）条件数、衡量表达能力的线性区域数量，以及评估硬件性能的FLOPs和延迟估计。通过将这些指标组合成一个统一的目标函数，框架能够快速识别出在精度和效率之间达到最佳平衡的架构。

3.2 神经切线核理论的深入分析

神经切线核是理解神经网络训练动态的强大工具。在无限宽度极限下，神经网络的行为可以通过一个固定的核函数来描述，这个核函数就是NTK。对于一个$L$层的全连接网络，其NTK可以递归地定义为：

$$\Theta^{(0)}(x, x') = \Sigma^{(0)}(x, x') = x^T x'$$

$$\Sigma^{(l)}(x, x') = \mathbb{E}_{(u,v) \sim \mathcal{N}(0, \Lambda^{(l-1)})} [\sigma(u)\sigma(v)]$$

$$\Theta^{(l)}(x, x') = \Theta^{(l-1)}(x, x') \cdot \dot{\Sigma}^{(l)}(x, x') + \Sigma^{(l)}(x, x')$$

其中$\Lambda^{(l-1)} = \begin{pmatrix} \Sigma^{(l-1)}(x,x) & \Sigma^{(l-1)}(x,x') \\ \Sigma^{(l-1)}(x',x) & \Sigma^{(l-1)}(x',x') \end{pmatrix}$，$\sigma$是激活函数，$\dot{\Sigma}^{(l)}$是$\Sigma^{(l)}$关于激活函数的导数期望。

NTK的条件数直接影响网络的训练速度和最终性能。条件数过大意味着梯度下降的收敛速度会很慢，而且容易陷入局部最优。MicroNAS通过计算小批量数据上的NTK条件数来快速评估网络的可训练性。实验表明，这个指标与网络的最终精度存在显著的相关性。

3.3 线性区域计数的理论与实现

ReLU网络的表达能力可以通过其能够产生的线性区域数量来衡量。对于一个$L$层的ReLU网络，每层有$n_l$个神经元，理论上的线性区域数量上界为：

$$\mathcal{R}_{max} = \prod_{l=1}^{L} \left\lfloor \frac{n_l}{n_0} \right\rfloor^{n_0}$$

其中$n_0$是输入维度。然而，实际的线性区域数量通常远小于这个理论上界，因为许多区域可能是空的或者重叠的。

MicroNAS采用了一种高效的采样方法来估计线性区域数量。具体来说，框架在输入空间中随机采样多条路径，沿着每条路径追踪激活模式的变化。当激活模式发生变化时，就意味着穿越了一个线性区域的边界。通过统计所有路径上遇到的不同激活模式，可以得到线性区域数量的估计值。

这种方法的计算复杂度为$O(N \cdot L \cdot n_{max})$，其中$N$是采样路径数，$L$是网络层数，$n_{max}$是最大层宽。相比于精确计算线性区域数量的指数复杂度，这种近似方法在实践中非常高效。

3.4 硬件感知的延迟建模

准确的延迟建模是实现硬件感知NAS的关键。MicroNAS的延迟模型考虑了MCU硬件的多个特性，包括计算单元的并行度、内存访问模式、缓存行为等。对于卷积操作，延迟可以分解为计算延迟和内存访问延迟：

$$L_{conv} = L_{comp} + L_{mem}$$

计算延迟主要取决于乘加运算的数量和硬件的计算能力：

$$L_{comp} = \frac{2 \cdot H_{out} \cdot W_{out} \cdot C_{in} \cdot C_{out} \cdot K_h \cdot K_w}{f_{MAC} \cdot p}$$

其中$f_{MAC}$是硬件的乘加运算频率，$p$是并行度。

内存访问延迟则更加复杂，需要考虑数据重用和缓存命中率：

$$L_{mem} = T_{read} \cdot (S_{input} + S_{weight}) \cdot (1 - h_{cache}) + T_{write} \cdot S_{output}$$

其中$T_{read}$和$T_{write}$是内存读写延迟，$S_{input}$、$S_{weight}$和$S_{output}$分别是输入、权重和输出的数据量，$h_{cache}$是缓存命中率。

第四章 搜索算法与优化策略

4.1 基于剪枝的高效搜索算法

MicroNAS采用了一种创新的基于剪枝的搜索算法，能够在庞大的搜索空间中高效地找到最优架构。算法的核心思想是通过逐步剪枝来缩小搜索空间，同时保证不会错过潜在的优秀架构。

算法首先对搜索空间进行粗粒度的采样，计算每个样本的性能指标。然后，根据这些指标将搜索空间划分为多个子空间，并识别出最有希望的子空间。在后续的迭代中，算法会在有希望的子空间中进行更密集的采样，同时剪枝掉性能较差的子空间。这个过程持续进行，直到找到满足所有约束条件的最优架构。

剪枝策略基于统计学的置信区间理论。对于每个子空间，算法维护一个性能估计的置信区间。当某个子空间的置信区间上界低于当前最优解时，该子空间就会被剪枝。这种方法能够在保证找到近似最优解的同时，大幅减少需要评估的架构数量。

4.2 多目标优化与帕累托前沿

在实际应用中，我们通常需要在多个相互冲突的目标之间进行权衡，如精度、延迟、能耗和模型大小。MicroNAS将这个问题建模为多目标优化问题，寻找帕累托最优的架构集合。

框架使用加权和方法将多个目标组合成单一的标量目标函数：

$$\mathcal{O}(\alpha) = \sum_{i=1}^{K} w_i \cdot f_i(\alpha)$$

其中$\alpha$表示架构，$f_i$是第$i$个目标函数，$w_i$是对应的权重。通过调整权重，可以探索整个帕累托前沿，为不同的应用场景找到合适的架构。

为了高效地探索帕累托前沿，MicroNAS采用了自适应权重调整策略。算法会根据当前找到的解的分布，动态调整权重以填补帕累托前沿上的空白区域。这种方法能够用较少的搜索次数获得均匀分布的帕累托最优解。

第五章 实验设置与结果分析

5.1 实验环境与基准测试

研究团队在多个层面对MicroNAS进行了全面的评估。硬件平台选择了STM32 NUCLEO-F746ZG开发板，这是一款典型的高性能MCU，配备了ARM Cortex-M7内核，主频216MHz，具有1MB Flash和340KB RAM。这个平台在工业物联网和智能设备中广泛应用，具有很好的代表性。

软件环境包括STM32CubeAI工具链用于模型部署和优化，TensorFlow Lite用于模型量化，以及自定义的性能分析工具用于精确测量推理延迟和能耗。所有的搜索实验都在配备NVIDIA V100 GPU的服务器上进行，以便与其他NAS方法进行公平比较。

基准测试选择了NAS-Bench-201，这是一个标准化的NAS评测平台，包含了15,625个预训练的架构及其在CIFAR-10、CIFAR-100和ImageNet-16-120上的性能数据。这使得研究人员能够快速验证搜索算法的有效性，而无需实际训练网络。

5.2 搜索效率的突破性提升

实验结果显示，MicroNAS在搜索效率方面取得了革命性的突破。与需要552 GPU小时的μNAS相比，MicroNAS仅需0.5 GPU小时就能完成搜索，效率提升达到1104倍。这个巨大的改进主要归功于零样本评估策略，完全避免了耗时的网络训练过程。

更重要的是，搜索效率的提升并没有以牺牲架构质量为代价。MicroNAS找到的架构在CIFAR-10上达到了93.88%的准确率，比μNAS高出6.2个百分点。同时，模型的推理延迟降低了3.23倍，FLOPs减少了73%。这些结果充分证明了零样本NAS方法的有效性。

搜索过程的收敛性分析也很有启发性。MicroNAS通常在评估不到100个架构后就能找到接近最优的解，而传统的基于训练的方法需要评估数千个架构。这种快速收敛得益于理论指标的强预测能力和高效的搜索算法。

5.3 硬件性能的显著改善

在MCU部署方面，MicroNAS展现出了卓越的硬件感知能力。通过对比不同搜索策略得到的架构，研究发现延迟引导的搜索比FLOPs引导的搜索更适合MCU平台。这是因为MCU的内存带宽限制和缓存结构使得某些理论上FLOPs较低的操作实际执行时间反而更长。

具体的性能测试显示，MicroNAS找到的最优架构在STM32F746上的单次推理时间为47ms，功耗为0.23W，峰值内存使用为178KB。相比之下，手工设计的MobileNetV2需要152ms的推理时间和0.41W的功耗。这种性能优势在实际应用中意义重大，意味着更长的电池寿命和更好的用户体验。

延迟模型的准确性验证也是实验的重要部分。通过对比预测延迟和实际测量延迟，发现模型的平均预测误差仅为8.3%，最大误差不超过15%。这种高精度的延迟预测确保了搜索过程能够找到真正在硬件上高效的架构。

第六章 图表详细分析

6.1 图1：MicroNAS工作流程的深入解读

图1展示了MicroNAS框架的完整工作流程，这是一个精心设计的四阶段流水线。图的最左侧是性能指标模块，其中上方展示了NTK谱的可视化。这个热力图使用颜色编码表示不同架构的NTK特征值分布，深红色区域表示较大的特征值，深蓝色表示较小的特征值。通过这种可视化，可以直观地看出不同架构的训练动态特性。紧接着下方是线性区域计数的可视化，用三维曲面展示了网络输入空间被划分成的线性区域，不同颜色代表不同的线性区域，区域的密度反映了网络的局部表达能力。

图的中央部分是架构搜索模块，展示了基于单元格的搜索空间。每个单元格用一个小的有向无环图表示，包含4个节点（用圆圈表示）和多条有向边（用箭头表示）。边上的标签如"conv3×3"、"skip-connect"等表示不同的操作选择。搜索算法通过剪枝策略逐步缩小候选操作集合，最终确定每条边的操作。图中还展示了剪枝过程的数学表达式$S = \bigcup_{i=1}^{n} S_i$，其中$S_i$表示第$i$次迭代后的搜索空间。

图的右侧展示了模型部署和优化流程。上方的循环图表示迭代优化过程，包括四个步骤：(1)输入原始模型，(2)TensorFlow Lite量化，(3)STM32 CubeAI编译，(4)性能评估和反馈。下方展示了实际的MCU硬件平台STM32 NUCLEO板，以及不同搜索策略（基线、FLOPs引导、延迟引导）在实际硬件上的性能对比柱状图。

6.2 图2：性能指标相关性的统计分析

图2包含两个子图，提供了关键性能指标的统计分析。左图（图2a）展示了Kendall-τ相关性与条件数$K_i$的关系。横轴表示条件数的索引（从1到16），纵轴表示Kendall-τ相关性系数（范围0到0.6）。三条曲线分别代表在CIFAR-10（橙色圆点）、CIFAR-100（绿色方块）和ImageNet16-120（蓝色三角）数据集上的结果。

从图中可以观察到几个重要现象：首先，所有三条曲线都呈现下降趋势，说明随着条件数的增加，其作为性能预测指标的可靠性下降。其次，CIFAR-10上的相关性始终最高，这可能是因为CIFAR-10相对简单，网络的初始状态与最终性能的关联更强。第三，在条件数较小时（$K_i < 5$），相关性系数都在0.4以上，表明NTK条件数是一个有效的性能指标。

右图（图2b）分析了批量大小对Kendall-τ相关性的影响。横轴使用对数尺度表示批量大小（从5到100），纵轴是Kendall-τ相关性系数。图中展示了四条曲线：前三条分别表示搜索过程中第1次、第2次和第3次迭代的结果，第四条是平均值。关键观察包括：批量大小在16-32范围内时，相关性达到峰值约0.5；继续增加批量大小到64或128，相关性略有下降但趋于稳定；批量大小小于16时，相关性急剧下降，这是因为小批量无法准确估计NTK谱。

第七章 深入讨论与未来展望

7.1 零样本NAS的理论意义

MicroNAS的成功不仅在于其实用价值，更重要的是它验证了一个重要的理论假设：神经网络的最终性能在很大程度上可以通过其初始化时的属性来预测。这个发现对深度学习理论具有深远的影响。

从优化理论的角度来看，NTK条件数反映了损失函数景观的几何特性。条件数较小的网络具有更平滑的损失函数，更容易通过梯度下降找到好的最小值。从表达能力的角度来看，线性区域数量决定了网络能够表示的函数复杂度上界。这两个指标共同决定了网络的学习能力。

这种理论理解为设计更好的网络架构提供了指导原则。例如，我们可以通过调整网络的初始化方案、激活函数的选择、或者架构的拓扑结构来改善这些指标，从而提高网络的性能。这开启了一个新的研究方向：基于理论指导的架构设计。

7.2 边缘AI的实际应用前景

MicroNAS为边缘AI应用开辟了新的可能性。在智能物联网、可穿戴设备、工业监控等领域，MCU是最常用的计算平台。然而，由于资源限制，这些设备通常只能运行简单的规则基础算法，无法充分利用深度学习的强大能力。

MicroNAS找到的高效架构使得在MCU上部署复杂的视觉识别、语音处理等AI应用成为可能。例如，在智能家居场景中，配备MicroNAS优化模型的门铃摄像头可以在本地进行人脸识别，无需将视频流上传到云端，既保护了隐私又降低了延迟。在工业4.0应用中，部署在生产线上的MCU可以实时进行缺陷检测和质量控制，提高生产效率。

更重要的是，MicroNAS的搜索效率使得为特定应用定制模型成为可能。不同的应用场景有不同的精度要求和资源约束，MicroNAS可以快速找到最适合的架构，实现真正的AI民主化。

7.3 技术挑战与改进方向

尽管MicroNAS取得了显著的成功，但仍有一些技术挑战需要解决。首先是搜索空间的设计问题。当前的基于单元格的搜索空间虽然有效，但可能限制了架构的多样性。未来的研究可以探索更灵活的搜索空间，如允许不同类型的单元格组合，或者直接搜索整个网络的拓扑结构。其次是性能指标的完备性问题。虽然NTK条件数和线性区域数量是有效的指标，但它们可能无法完全捕捉网络的所有重要属性。例如，网络的鲁棒性、泛化能力、对噪声的敏感度等都是重要的考虑因素。开发更全面的性能指标体系是一个重要的研究方向。最后是硬件模型的准确性和泛化能力。当前的延迟模型是针对特定的MCU平台开发的，推广到其他硬件平台需要重新建模。开发通用的硬件性能模型，能够准确预测不同硬件平台上的性能，是实现真正硬件感知NAS的关键。

第八章 结论

MicroNAS代表了神经架构搜索领域的一个重要里程碑。通过巧妙地结合深度学习理论和硬件约束，它实现了前所未有的搜索效率，同时保持了架构质量。1104倍的效率提升不仅仅是一个数字，它意味着NAS技术从实验室走向实际应用的可能性大大增加。从技术创新的角度来看，MicroNAS的贡献是多方面的。它提出了一套完整的零样本评估指标体系，开发了高效的硬件感知搜索算法，并在实际MCU平台上验证了方法的有效性。这些创新不仅推动了NAS技术的发展，也为边缘AI的普及奠定了基础。

展望未来，随着物联网和边缘计算的快速发展，对高效AI模型的需求将持续增长。MicroNAS及其后续改进将在这个过程中发挥重要作用，帮助将AI的力量带到每一个边缘设备。我们期待看到更多基于MicroNAS的实际应用，以及在其启发下产生的新一代NAS技术。

附录A：神经切线核的推导

A.1 NTK的定义与性质

考虑一个$L$层的全连接神经网络，第$l$层的前向传播可以表示为：

$$h^{(l+1)}(x) = \frac{1}{\sqrt{n_l}} W^{(l)} \sigma(h^{(l)}(x)) + b^{(l)}$$

其中$W^{(l)} \in \mathbb{R}^{n_{l+1} \times n_l}$是权重矩阵，$b^{(l)} \in \mathbb{R}^{n_{l+1}}$是偏置向量，$\sigma$是逐元素的激活函数，$n_l$是第$l$层的宽度。权重和偏置使用标准高斯分布初始化：$W_{ij}^{(l)} \sim \mathcal{N}(0, 1)$，$b_i^{(l)} \sim \mathcal{N}(0, 1)$。

网络的输出可以写成：

$$f(x; \theta) = h^{(L)}(x)$$

其中$\theta = \{W^{(l)}, b^{(l)}\}_{l=0}^{L-1}$表示所有参数。

神经切线核定义为：

$$\Theta(x, x') = \left\langle \nabla_\theta f(x; \theta), \nabla_\theta f(x'; \theta) \right\rangle$$

在无限宽度极限$n_1, ..., n_{L-1} \to \infty$下，NTK收敛到一个确定性的核函数，可以递归计算。

A.2 NTK的递归计算

定义辅助核函数：

$$\Sigma^{(0)}(x, x') = x^T x'$$

对于$l = 1, ..., L$：

$$\Lambda^{(l-1)} = \begin{pmatrix} \Sigma^{(l-1)}(x,x) & \Sigma^{(l-1)}(x,x') \\ \Sigma^{(l-1)}(x',x) & \Sigma^{(l-1)}(x',x') \end{pmatrix}$$

$$\Sigma^{(l)}(x, x') = \mathbb{E}_{(u,v) \sim \mathcal{N}(0, \Lambda^{(l-1)})} [\sigma(u)\sigma(v)]$$

对于ReLU激活函数$\sigma(x) = \max(0, x)$，可以得到闭式解：

$$\Sigma^{(l)}(x, x') = \frac{1}{2\pi} \sqrt{\Sigma^{(l-1)}(x,x) \Sigma^{(l-1)}(x',x')} \left(\sin\theta + (\pi - \theta)\cos\theta\right)$$

其中$\theta = \arccos\left(\frac{\Sigma^{(l-1)}(x,x')}{\sqrt{\Sigma^{(l-1)}(x,x) \Sigma^{(l-1)}(x',x')}}\right)$。

NTK的递归公式为：

$$\Theta^{(1)}(x, x') = \Sigma^{(1)}(x, x')$$

$$\Theta^{(l)}(x, x') = \Theta^{(l-1)}(x, x') \cdot \dot{\Sigma}^{(l)}(x, x') + \Sigma^{(l)}(x, x')$$

其中$\dot{\Sigma}^{(l)}(x, x') = \mathbb{E}_{(u,v) \sim \mathcal{N}(0, \Lambda^{(l-1)})} [\sigma'(u)\sigma'(v)]$。

对于ReLU，导数的期望为：

$$\dot{\Sigma}^{(l)}(x, x') = \frac{1}{2\pi} (\pi - \theta)$$

A.3 条件数与训练动态

给定训练数据$\{(x_i, y_i)\}_{i=1}^n$，NTK矩阵定义为：

$$\Theta_{ij} = \Theta(x_i, x_j)$$

在无限宽度和梯度流极限下，网络输出的演化遵循：

$$\frac{d}{dt} f(X; \theta_t) = -\Theta \cdot (f(X; \theta_t) - Y)$$

其中$X = [x_1, ..., x_n]^T$，$Y = [y_1, ..., y_n]^T$。

这个线性ODE的解为：

$$f(X; \theta_t) = Y + e^{-\Theta t}(f(X; \theta_0) - Y)$$

收敛速度由$\Theta$的最小特征值$\lambda_{min}$决定。条件数$\kappa = \lambda_{max}/\lambda_{min}$越小，收敛越快且越稳定。

附录B：线性区域计数的理论分析

B.1 ReLU网络的分段线性性质

考虑一个$L$层的ReLU网络：

$$f(x) = W^{(L)} \sigma(W^{(L-1)} \sigma(...\sigma(W^{(1)} x + b^{(1)})...) + b^{(L-1)}) + b^{(L)}$$

对于固定的输入$x$，定义激活模式：

$$\alpha^{(l)}(x) = \mathbb{1}[W^{(l-1)} h^{(l-1)}(x) + b^{(l-1)} > 0]$$

其中$\mathbb{1}[\cdot]$是指示函数，$h^{(l-1)}(x)$是第$l-1$层的激活输出。

给定激活模式$\{\alpha^{(l)}\}_{l=1}^L$，网络在对应的线性区域内可以表示为：

$$f(x) = A(\alpha) x + b(\alpha)$$

其中：

$$A(\alpha) = W^{(L)} \text{diag}(\alpha^{(L-1)}) W^{(L-1)} ... \text{diag}(\alpha^{(1)}) W^{(1)}$$

$$b(\alpha) = W^{(L)} \text{diag}(\alpha^{(L-1)}) ... \text{diag}(\alpha^{(2)}) b^{(1)} + ... + b^{(L)}$$

B.2 线性区域数量的上界

定理：对于一个$L$层的ReLU网络，第$l$层有$n_l$个神经元，输入维度为$n_0$，线性区域数量的上界为：

$$\mathcal{R} \leq \sum_{j_1 + ... + j_L = n_0} \prod_{l=1}^{L} \binom{n_l}{j_l}$$

证明概要：每个线性区域由一组超平面的交集定义。第$l$层的每个神经元贡献一个超平面。要在$n_0$维空间中定义一个区域，至少需要$n_0$个线性独立的超平面。通过组合论分析，可以得到上述上界。

对于深度网络（$L \gg 1$），当每层宽度相等$n_l = n$时，上界可以近似为：

$$\mathcal{R} \lesssim \left(\frac{e \cdot n \cdot L}{n_0}\right)^{n_0}$$

这表明深度对线性区域数量的贡献是多项式的，而宽度的贡献是指数的。

B.3 有效线性区域的估计

实际网络中，许多理论上的线性区域可能是空的或者测度为零。有效线性区域的数量通常通过蒙特卡洛采样估计：

1. 在输入空间中随机采样$N$条路径：$\gamma_i : [0, 1] \to \mathbb{R}^{n_0}$
2. 沿每条路径离散采样$M$个点：$x_{ij} = \gamma_i(j/M)$，$j = 0, ..., M$
3. 计算每个点的激活模式：$\alpha_{ij} = \{\alpha^{(l)}(x_{ij})\}_{l=1}^L$
4. 统计不同激活模式的数量：$\hat{\mathcal{R}} = |\{\alpha_{ij} : i = 1, ..., N, j = 0, ..., M\}|$

这个估计的方差为：

$$\text{Var}[\hat{\mathcal{R}}] \approx \frac{\mathcal{R}^2}{N \cdot M} \left(1 - \frac{1}{\mathcal{R}}\right)$$

附录C：硬件延迟模型的推导

C.1 计算延迟的精确建模

对于卷积操作，考虑循环展开和向量化的影响：

$$L_{comp} = \frac{1}{f_{clock}} \sum_{h=0}^{H_{out}-1} \sum_{w=0}^{W_{out}-1} \sum_{c_{out}=0}^{C_{out}-1} L_{pixel}(h, w, c_{out})$$

其中单个输出像素的计算延迟为：

$$L_{pixel} = \left\lceil \frac{C_{in}}{V_{in}} \right\rceil \cdot \left\lceil \frac{K_h \cdot K_w}{U} \right\rceil \cdot (L_{MAC} + L_{overhead})$$

这里$V_{in}$是输入通道的向量化宽度，$U$是循环展开因子，$L_{MAC}$是单个乘加运算的周期数，$L_{overhead}$是循环开销。

C.2 内存访问模式分析

MCU的内存层次结构通常包括寄存器、L1缓存和主存。数据重用模式决定了内存访问效率：

输入重用：每个输入像素被$K_h \times K_w \times C_{out}$个输出像素使用
权重重用：每个权重被$H_{out} \times W_{out}$个输出像素使用
输出累加：每个输出像素需要$C_{in} \times K_h \times K_w$次累加

最优的数据分块策略需要最小化总的内存访问：

$$\min_{T_h, T_w, T_c} \left( \frac{S_{input}}{R_{input}(T_h, T_w, T_c)} + \frac{S_{weight}}{R_{weight}(T_h, T_w, T_c)} \right)$$

受限于缓存大小约束：

$$T_h \cdot T_w \cdot C_{in} + T_c \cdot C_{in} \cdot K_h \cdot K_w + T_h \cdot T_w \cdot T_c \leq S_{cache}$$

C.3 能耗模型

MCU的能耗包括动态能耗和静态能耗：

$$E_{total} = E_{dynamic} + E_{static}$$

动态能耗主要来自计算和内存访问：

$$E_{dynamic} = n_{MAC} \cdot E_{MAC} + n_{mem} \cdot E_{mem}$$

其中$n_{MAC}$是乘加运算次数，$n_{mem}$是内存访问次数，$E_{MAC}$和$E_{mem}$是单位操作的能耗。

静态能耗与执行时间成正比：

$$E_{static} = P_{idle} \cdot L_{total} / f_{clock}$$

通过优化架构降低计算复杂度和内存访问，可以同时减少动态和静态能耗。