try ai
科普
编辑
分享
反馈
  • 可验证鲁棒性

可验证鲁棒性

SciencePedia玻尔百科
核心要点
  • 鲁棒性证书是一份数学证明,它能证明一个系统在确定的干扰集合下是可靠的,但其有效性完全取决于底层不确定性模型的准确性。
  • 验证神经网络的关键机制包括:要么限制函数的变化率(其 Lipschitz 常数),要么通过网络传播可能值的区间(区间边界传播)。
  • 可验证鲁棒性的原则不仅限于人工智能,它为确保基因组学、合成生物学和资源管理等不同领域的可靠性提供了一个统一的框架。
  • 鲁棒性设计通常涉及系统峰值性能与其可验证可靠性之间的根本性权衡,这需要深思熟虑的工程选择。

引言

在一个日益复杂和不确定的世界里,从我们手机中的人工智能到管理环境的模型,对可靠系统的需求从未如此强烈。但我们如何信任这些系统呢?简单的测试只能确认我们在已经设想到的场景下的行为。可验证鲁棒性则提供了一个更强大的承诺:一个数学上的保证,即系统在一整套潜在的干扰范围内都将正确运行。本文旨在解决如何为那些无法进行穷尽测试的复杂、通常是非线性的系统构建此类保证的根本性挑战。

本次探索分为两部分。首先,在“原理与机制”部分,我们将深入探讨验证的数学基础。我们将揭示控制理论中的概念(如小增益定理)如何为鲁棒性提供基础,以及像 Lipschitz 分析和区间边界传播这样的现代技术如何被调整以验证复杂神经网络的行为。随后,“应用与跨学科联系”部分将揭示这些思想令人惊讶和深远的影响力。我们将看到,寻求可验证的保证不仅是计算机科学家面临的问题,更是一个统一的原则,为基因组学、合成生物学和环境管理等不同领域提供了新工具,将现代人工智能与科学和工程的基础挑战联系起来。

原理与机制

谈论任何“可验证的”事物都是一个大胆的声明。它不仅承诺某物在理想条件下能工作,而且承诺当它面对一系列现实世界的不完美和干扰时也不会失效。当我们验证一座桥梁时,我们不只是用一辆车来测试它;我们保证它在达到规定重量限制内的任何交通模式下都能保持完整性。可验证鲁棒性就是为复杂系统(从航天器到你手机里的人工智能)做出并验证此类承诺的科学。但是,我们怎么可能提供一个覆盖了我们未曾测试过的无限多种场景的保证呢?答案不在于不可能实现的穷尽测试,而在于深刻的数学原理,这些原理使我们能够一次性地对整个可能性集合进行推理。

保证的本质

在深入探讨机制之前,我们必须理解一个根本性的,或许也令人谦卑的真理:​​一份证书的价值取决于其所基于的假设​​。一份鲁棒性证书是一个数学证明,它证明一个系统将如预期般运行,前提是现实世界的不确定性与证明中使用的数学不确定性模型相匹配。如果我们的模型是错误的,这份证书可能就一文不值。

想象一位工程师在设计卫星的姿态控制系统。他们可能会将两个反作用轮的不确定性建模为独立的随机变化,从而假设其不确定性矩阵具有对角结构,我们称之为 Δdesign\boldsymbol{\Delta}_{design}Δdesign​。然后,他们使用强大的工具,如​​结构奇异值 (μ\muμ) 分析​​,来合成一个控制器,该控制器对于此对角集合内的任何不确定性都可被证明是稳定的。证书颁发了:μΔdesign(M)<1\mu_{\boldsymbol{\Delta}_{design}}(M) \lt 1μΔdesign​​(M)<1。但如果,在寒冷的外层空间真空中,热效应导致轮子的惯性以一种相关的方式变化——一个增加,另一个减少呢?这种物理现实由一个完全不同的结构来描述,比如说,一个非对角矩阵 Δtrue\boldsymbol{\Delta}_{true}Δtrue​。这个仅为集合 Δdesign\boldsymbol{\Delta}_{design}Δdesign​ 证明的稳定性保证,根本不适用于现实世界的扰动,尽管有“可验证的”控制器,卫星仍然可能失控翻滚。这是我们的第一课,也是最重要的一课:理解并正确建模不确定性的结构不仅仅是一个技术细节,它是任何保证所依赖的根基。

最简单的规则:不要放大噪声

那么,我们如何开始构建一个保证呢?最古老也最简单的鲁棒性原理是​​小增益定理 (Small Gain Theorem)​​。想象一下麦克风和扬声器之间的反馈回路。如果回路中的总放大增益——扬声器的声音被麦克风拾取,重新放大,再传回扬声器——小于 1,系统就是稳定的。我们熟悉的反馈尖啸声发生在环路增益超过 1 时,导致一个微小的噪声被放大成震耳欲聋的嚎叫。

在更一般的术语中,如果我们有一个标称系统 MMM 和一个不确定性 Δ\DeltaΔ 处于反馈回路中,如果环路增益小于 1,系统就保证是稳定的。一个充分条件就是 ∥M∥∥Δ∥<1\Vert M \Vert \Vert \Delta \Vert \lt 1∥M∥∥Δ∥<1,其中 ∥⋅∥\Vert \cdot \Vert∥⋅∥ 代表系统的“大小”或诱导范数。这个条件告诉我们,如果系统的放大倍数与不确定性的大小之积小于 1,我们就是安全的。

这是一个强有力的起点,但它可能非常保守。为什么?因为它将不确定性 Δ\DeltaΔ 视为一个整体的“团块”,仅由其可能的最大尺寸来表征。但正如我们已经了解到的,不确定性的结构至关重要。考虑一个假设系统,其不确定性有两个分量 δ1\delta_1δ1​ 和 δ2\delta_2δ2​。如果我们将不确定性块 Δ\DeltaΔ 仅视为某个尺寸的任何矩阵(一种“非结构化”分析),小增益定理可能会告诉我们,只有当不确定性的大小 ρ\rhoρ 小于(比如说)0.10.10.1 时,系统才能保证稳定。然而,如果我们知道不确定性是对角的——也就是说,δ1\delta_1δ1​ 和 δ2\delta_2δ2​ 不会交叉耦合——我们就可以进行“结构化”分析。通过利用这一知识,我们可能会发现,对于任何大小 ρ\rhoρ 高达 1.01.01.0 的不确定性,系统实际上都是稳定的,这在我们的可验证鲁棒性上实现了十倍的提升。这种通过利用结构来减少保守性的探索,是更先进方法背后的驱动力,并且对于验证神经网络的鲁棒性至关重要。

驯服野兽:验证非线性

来自控制理论的原理为我们提供了优美的基础,但神经网络引入了一个巨大的挑战:它们是强非线性的。与线性系统不同,网络的“增益”或敏感度不是固定的;它会根据接收到的特定输入而急剧变化。输入空间中一个网络平坦且稳定的区域,可能紧邻着一个极其陡峭和敏感的区域。我们如何能对这样一个多变、如变色龙般的函数做出保证呢?

工程师和数学家已经发展出两大类优美的策略来解决这个问题。第一种方法是为函数找到一个“速度极限”——限制其输出变化的速度。第二种方法是为函数的输出构建一个“笼子”——追踪它可能取到的所有可能值的完整集合。

机制一:函数的“速度极限”

一个函数在特定点的陡峭程度由其导数,或更一般地,其​​雅可比矩阵 (Jacobian matrix)​​ JxJ_xJx​ 捕捉。向量函数 fff 在输入 xxx 处的“局部速度极限”由其雅可比矩阵的谱范数 ∥Jx∥2\Vert J_x \Vert_2∥Jx​∥2​ 给出。这个值是该函数的局部 ​​Lipschitz 常数​​。如果我们能在一个完整区域内找到这个范数的上界 LLL,我们就能做出一个强有力的陈述。对于该区域内的任意两点 x1x_1x1​ 和 x2x_2x2​,它们输出之间的距离最多是输入之间距离的 LLL 倍:∥f(x1)−f(x2)∥2≤L∥x1−x2∥2\Vert f(x_1) - f(x_2) \Vert_2 \le L \Vert x_1 - x_2 \Vert_2∥f(x1​)−f(x2​)∥2​≤L∥x1​−x2​∥2​。

这为我们提供了一种直接验证鲁棒性的方法。假设一个网络正确分类了输入 xxx,并且正确类别的 logit 值 fy(x)f_y(x)fy​(x) 比最强竞争类别 fj(x)f_j(x)fj​(x) 的 logit 值高出一定的​​余量 (margin)​​ m(x)m(x)m(x)。现在,我们考虑一个受扰动的输入 x+δx+\deltax+δ,其中扰动的大小最多为 rrr。正确类别的输出最多可能减少 LrL rLr,而竞争类别的输出最多可能增加 LrL rLr。为了使分类保持正确,初始余量必须足够大,以吸收来自双方的最坏情况变化。这导出了一个用于可验证鲁棒性的极其简洁的条件:

m(x)>2rLm(x) > 2 r Lm(x)>2rL

安全余量必须大于扰动半径与函数速度极限乘积的两倍。这个原则清晰地揭示了几何(余量)、扰动大小(rrr)和函数属性(LLL)之间的联系。

这也揭示了网络设计中看似微小的选择如何对验证产生直接影响。总的 Lipschitz 常数 LLL 取决于激活函数的导数。常见的 ​​ReLU​​ 激活函数的最大导数为 111。相比之下,更平滑的 ​​GELU​​ 激活函数的导数峰值约为 1.1281.1281.128。这意味着,在其他条件相同的情况下,使用 GELU 的网络将具有更高的最坏情况 Lipschitz 常数。根据我们的公式,更大的 LLL 意味着可验证半径 rrr 必须更小。这说明了一个有趣的权衡:GELU 可能会提供更好的训练性能,但基于这种“速度极限”方法,它可能导致较弱的鲁棒性证书。

这种利用局部检查和 Lipschitz 界限来证明全局属性的思想是数学中的一个深刻概念。它不仅用于机器学习,还用于验证复杂动态系统的稳定性,在这种系统中,人们可能在网格点上检查一个稳定性条件,并使用 Lipschitz 常数来保证该条件在它们之间的空间也成立。

机制二:包容可能性的云团

除了限制函数变化的速度,我们还可以尝试直接计算所有可能输出的集合。最直接的方法是​​区间边界传播 (Interval Bound Propagation, IBP)​​。

这个想法简单而强大。我们首先将输入扰动表示为一个区间。对于一个输入 x0x_0x0​ 和一个半径为 ε\varepsilonε 的 ℓ∞\ell_\inftyℓ∞​ 扰动,每个输入坐标 xix_ixi​ 不再是一个固定的数字,而是位于区间 [x0,i−ε,x0,i+ε][x_{0,i} - \varepsilon, x_{0,i} + \varepsilon][x0,i​−ε,x0,i​+ε] 内。然后我们逐层地在网络中“传播”这个方框,计算每个神经元的可能值的最终区间。

对于一个线性层 y=Wx+by = Wx+by=Wx+b,逻辑非常直观。为了找到输出 yiy_iyi​ 的最低可能值,我们应该将 WWW 对应行中的正权重与最低可能的输入配对,将负权重与最高可能的输入配对。这个过程为预激活值提供了一个新的、更大的方框。对于 ReLU 激活函数 ReLU⁡(z)=max⁡(0,z)\operatorname{ReLU}(z) = \max(0,z)ReLU(z)=max(0,z),输出区间就是 [max⁡(0,lz),max⁡(0,uz)][\max(0, l_z), \max(0, u_z)][max(0,lz​),max(0,uz​)]。

通过重复这个过程直到最后一层,我们为每个输出 logit 获得一个可能值的区间。验证检查随之变得直接:如果真实类别的 logit 的下界大于其他所有类别的 logit 的上界,那么对于初始扰动框内的每一个输入,分类都保证是正确的。

IBP 快速而简单,但它产生的界限在经过多层传播后可能会变得非常宽松。更先进的技术,例如基于将网络表述为​​混合整数线性规划 (Mixed-Integer Linear Program, MILP)​​ 的技术,可以提供更紧的松弛。这些方法用一组线性不等式取代非线性的 ReLU 神经元,这些不等式在给定区间内完美地包围了它们的行为。这些方法产生的最终证书的质量,关键取决于用于每个神经元的中间区间界限的紧密程度。使用宽松、通用的界限可能导致非常弱的最终证书,而花时间在每一层计算紧密的预激活界限可以极大地增强结果,揭示了一个基本原则:​​局部精度孕育全局确定性​​。

那么,证书有什么用?

有了这些机制,我们可以为给定的输入计算一个​​可验证半径 (certified radius)​​——这是一个最大的扰动球体的大小,在这个球体内的扰动下,预测被证明是恒定的。这个单一的数字是我们分析的顶峰。但它在实践中意味着什么?

它使我们能够超越标准准确率,谈论​​鲁棒准确率 (robust accuracy)​​。对于给定的扰动预算 ε\varepsilonε,我们可以问:我们的数据集中有多大比例不仅被正确分类,而且被验证为对于任何大小不超过 ε\varepsilonε 的扰动都是正确的?这个指标,有时称为 R@ε\varepsilonε,在对抗性世界中为模型的可靠性提供了一个更有意义的衡量标准。

最后,值得一问的是,我们真正得到的是什么样的保证。大多数验证方法提供的是分类稳定性的保证——即预测的标签不会改变。这类似于证明一个系统是内部稳定的,意味着其内部状态不会崩溃。然而,这并不能自动保证良好的性能。一个系统可能被验证为对于一个集合中的每个不确定性都是稳定的,但对于其中某些不确定性,其输入-输出增益——一种性能衡量指标——却可能变得任意大。一个真正鲁棒的系统,是我们不仅能对其稳定性,还能对其性能提供统一界限的系统。这仍然是一个活跃且具有挑战性的前沿领域,提醒我们,对确定性的追求是一段不断深化原理和精细化区分的旅程。

应用与跨学科联系

现在我们已经探讨了可验证鲁棒性的原理和机制,我们可能会倾向于将其视为一种高度专业化的工具,一种用来防御计算机程序免受深奥攻击的巧妙技巧。但这样做将只见树木,不见森林。对可验证鲁棒性的追求并非计算机科学中的一个小众问题;它反映了一个跨越科学与工程的永恒且普遍的挑战:在一个根本上不确定的世界里,我们如何构建可靠、可信和安全的系统并做出相应的决策?

一个深刻科学原理的真正魅力在于它能够照亮不同的领域,揭示自然运作和人类智慧中隐藏的统一性。在本章中,我们将踏上一段见证这种统一力量的旅程。我们将看到可验证鲁棒性的核心思想——即提供数学证明,确保系统行为在一整套可能条件下保持正确——不仅用于防御神经网络,还用于解码我们 DNA 的秘密、设计生命生态系统、管理宝贵的自然资源,甚至理解通信本身的基本限制。

巩固机器学习的基础

在我们走得太远之前,让我们首先看看这些思想是如何丰富它们最近蓬勃发展的机器学习领域的。

从抽象的团块到物理现实

我们常说对抗性扰动存在于一个特定半径的抽象数学“球”内——准确地说,是一个 ℓp\ell_pℓp​ 范数球。这是一个方便的数学抽象,但它可能感觉与现实世界脱节。将对应于天空的像素变成对应于毛皮的像素在物理上合理吗?也许不合理。当我们将扰动集定义为基于真实的物理过程时,验证的真正威力才得以显现。

想象一个简单的图像分类器正在看一张图片。世界不是静止的;太阳移动,云彩飘过,室内灯光闪烁。这些都是光照的变化。我们可以用一个简单的仿射变换来模拟亮度和对比度的全局变化:每个像素 xix_ixi​ 变成 αxi+β\alpha x_i + \betaαxi​+β。我们的对手不再是一个抽象的球,而是被限制在从一个物理上现实的范围内选择任何可能的对比度 α\alphaα 和亮度 β\betaβ。对于一个简单的分类器,验证其鲁棒性变成了一项非常直接的任务。模型的决策通常是 α\alphaα 和 β\betaβ 的一个简单函数,我们只需要在允许的范围内找到“最坏”的可能光照条件,看它是否能被欺骗。这通常就像检查允许的 (α,β)(\alpha, \beta)(α,β) 值方框的角点一样简单。通过这样做,我们不再只是构建一个鲁棒的算法;我们正在构建一个我们能证明其对光与影的物理变幻具有鲁棒性的相机系统。

从零开始的鲁棒性:训练过程

一个模型最终的鲁棒性关键取决于其创建过程。期望在一盘散沙上建起一座坚固的房子是徒劳的。训练大型模型最常用的方法——随机梯度下降法——是一块砖一块砖地(或者说一个“小批量”数据一个小批量数据地)构建这个基础。在每一步,它通过对一小部分数据样本的梯度进行平均来估计改进模型的方向。

但如果其中一些数据被损坏了呢?一个错误标记的样本、一个传感器故障、一束宇宙射线——这些都可能产生一个指向完全错误方向的梯度。我们在学校都学过的简单算术平均值,是极其脆弱的。一个任意坏的数据点可以把它想拉多远就拉多远,从而可能毒害整个训练步骤。如果训练过程本身不鲁棒,我们又怎能期望最终的模型是鲁棒的呢?

在这里,一个来自经典鲁棒统计学的优美思想前来搭救:用​​几何中位数 (geometric median)​​ 取代算术平均值。一组点(在我们的例子中是梯度向量)的几何中位数是那个最小化到所有其他点的距离之和的点。与均值不同,它不容易被离群点左右。一个任意坏的梯度可以拉动它,但其他“好的”梯度会把它拉回来,从而达到一种平衡。只要一个小批量中的大多数梯度是“好的”(即未被损坏),几何中位数就能保证提供一个有界的、合理的真实梯度方向估计。它的误差不会爆炸;它有一个有限的“崩溃点”。相比之下,算术平均值的崩溃点为零——一个坏点就能摧毁它。通过确保每一步的鲁棒性,我们为整个学习过程构建了一个更坚实的基础。

超越神经网络:经典方法的几何学

鲁棒性的思想并不仅限于深度神经网络那些巴洛克式的架构。它们同样适用于机器学习中那些经典的、通常更直观的算法。考虑其中最简单的一个:kkk-近邻 (KNN) 分类器。为了对一个新点进行分类,它只需在其训练数据中的 kkk 个最近邻居中进行投票。

它的决策边界是一个复杂的、由训练点位置定义的镶嵌表面。我们如何验证一个点 xxx 的分类对小扰动是鲁棒的呢?答案在于一个简单而优雅的几何论证。假设我们对 xxx 进行小量扰动,将其移动到一个新位置 x′x'x′。根据三角不等式,从 x′x'x′ 到任何训练点的距离变化不会超过扰动的大小。现在,想象在 xxx 的 kkk 个最近邻居集合周围有一条“护城河”。这条护城河的宽度是第 kkk 个邻居与第 (k+1)(k+1)(k+1) 个邻居之间的距离差。如果这条护城河的宽度超过我们允许扰动宽度的两倍,那么前 kkk 个邻居之外的点就无法“跳”进来,而内部的点也无法“跳”出去。kkk 个最近邻居的集合保持不变,预测就被验证为是鲁棒的。这提供了一个关于可验证鲁棒性含义的优美、直观的图景:它就是安全边际,是我们决策周围护城河的宽度。

通往科学的桥梁

一个原理深度的真正考验是它跨越学科界限的能力。可验证鲁棒性为解决自然科学中的基本问题提供了一种新的语言和一套新的工具,在这些领域中,数据总是充满噪声、不完整和不确定。

解码生命之书:基因组学与生物信息学

基因组是生命的说明书,但阅读它是一件棘手的事情。在计算生物学中,我们建立模型来解释 DNA 序列,也许是为了预测一个基因是否活跃或识别其功能。但现实世界的 DNA 测序并不完美。有时,一个碱基无法被确定地识别,并被标记为“N”,代表“未知”。一个鲁棒的模型必须能够处理这种模糊性,而其预测不会崩溃。

我们如何构建一个序列模型,比如循环神经网络 (Recurrent Neural Network, RNN),使其可被证明对这些“N”是鲁棒的?事实证明,鲁棒性并非一种凭空产生的神奇属性。如果一个模型在训练时从未见过“N”,那么它在测试时对“N”的反应是不可预测的,这取决于其初始化的随机怪癖,而非任何学到的原则。解决方案是将鲁棒性作为训练过程的一个明确目标。通过使用​​数据增强 (data augmentation)​​——在训练序列中随机撒入“N”同时保持标签不变——我们迫使模型学会根据周围的上下文进行预测,从而有效地学会忽略缺失信息或进行推断。这是一个强有力的教训:鲁棒性不仅是事后验证的;它通常是一个必须被主动设计和学习的属性。

更深入地看,基因间的相互作用本身是理解生物通路的钥匙。一项正向遗传筛选可能会测量数千个双突变体的适应度,从而创建一个巨大的矩阵,其中每个条目代表两个基因之间的相互作用(或“上位性”)。生物学家早就知道基因是以模块或通路的形式协同工作的。这种模块性对相互作用矩阵施加了一种特殊的结构:它应该近似是​​低秩 (low-rank)​​ 的,这意味着它的信息可以被压缩成少数对应于主要通路的显性模式。

然而,实验数据是一个雷区。许多双突变体可能无法存活或无法测量,在矩阵中留下大片缺失的条目。标准的测量噪声为每个观测值增加了一点模糊。而灾难性的失败,比如一个被污染的培养皿,可能会引入巨大且任意的误差——这些误差虽然稀疏但致命。挑战在于从这个不完整、有噪声且被损坏的矩阵中恢复出干净的、低秩的通路结构。这对于经典方法来说是不可能的。

但这正是​​鲁棒主成分分析 (Robust Principal Component Analysis, RPCA)​​ 框架被设计来解决的问题。通过将恢复问题表述为一个旨在将观测矩阵分解为一个低秩分量 (LLL) 和一个稀疏误差分量 (SSS) 的优化问题,我们能够成功。我们使用核范数 (nuclear norm) 作为秩的凸替代,使用 ℓ1\ell_1ℓ1​ 范数作为稀疏性的替代。这项强大的技术可以被证明能从噪声和损坏中解开底层的通路结构,有效地针对已知的测量病理验证恢复出的结构。然而,这里有一个关键的微妙之处:这仅在底层低秩信号是非相干的 (incoherent)——即其能量是分散的,而不是集中在少数几个基因上时才有效。如果一个通路的信号看起来太像一个稀疏的尖峰,那么从根本上就无法区分信号和噪声,这是一个关于可识别性极限的优美例子。

设计生态系统:合成生物学与系统生物学

从微观到宏观,科学家们不仅在观察自然,还在设计自然。在合成生物学中,研究人员旨在设计微生物群落——微小的、相互作用的生态系统——以执行有用的任务,如生产生物燃料或清理污染物。任何工程设计中的一个主要关注点都是​​稳定性 (stability)​​。设计的生态系统会是鲁棒的,还是会在最轻微的干扰下崩溃?

我们可以使用经典的 Lotka-Volterra 方程来模拟一个包含 nnn 个物种的群落的种群动态。一个共存平衡点——所有物种共同生存的状态——的稳定性由系统雅可比矩阵的特征值决定。为了使平衡点稳定,所有特征值都必须具有负实部。但是定义这个矩阵的生物学参数——生长率、相互作用强度——从来都无法被精确地知道。它们受到不确定性的影响。

我们如何验证我们设计的生态系统对于一整套可能的参数值都是稳定的?在这里,控制理论为我们提供了一个强大的工具:Gershgorin 圆盘定理 (Gershgorin Circle Theorem)。该定理允许我们为雅可比矩阵的每一行在复平面上画一个圆盘。我们知道矩阵的所有特征值都必须位于这些圆盘的并集之内。通过为我们的标称系统计算这些圆盘的属性,我们可以确定一个“鲁棒性裕度”。如果这个裕度大于由于参数不确定性导致的圆盘可能的最大位移,我们就得到了一个稳定性的证书。我们已经证明了系统在所有考虑的扰动下都将保持稳定。这是最纯粹形式的可验证鲁棒性,应用于确保一个活的、工程化的系统的可靠运行。

来自过去的回响与未来的信号

鲁棒性的原则是如此基本,以至于它们在科学史上反复出现。在一个领域看似新颖的想法,往往是对另一个领域深刻真理的重新发现。

祖先:纠错码

远在人工智能出现之前,工程师们就面临着一个类似的问题:如何在一个嘈杂的信道上可靠地通信。当你串流电影或听一张有划痕的 CD 里的音乐时,你正受益于纠错码的魔力。而在它们的核心,正蕴含着与可验证鲁棒性完全相同的原则。

想象一下你想表示 MMM 个不同的消息(或类别)。你给每个消息分配一个唯一的码字,一个长长的比特串。你的码的“最小距离” dmin⁡d_{\min}dmin​,是把一个有效码字变成另一个有效码字所需的最少比特翻转次数。现在,假设一个嘈杂的信道最多可以翻转 kkk 个比特来损坏你传输的码字。你如何保证接收者总能恢复原始消息?

答案是一个优美而简单的规则:如果你的码的最小距离至少为 dmin⁡≥2k+1d_{\min} \ge 2k+1dmin​≥2k+1,那么就能保证完美恢复。为什么?一个有 kkk 个错误的接收消息与原始码字的汉明距离为 kkk。由于最小距离条件,它到任何其他码字的距离必须至少为 (2k+1)−k=k+1(2k+1) - k = k+1(2k+1)−k=k+1。因此,原始码字是唯一的、严格最接近的匹配。接收者只需找到最近的有效码字,错误就被纠正了。这不仅仅是一个类比;它是一个形式上的等价。构建一个可验证鲁棒的分类器,使其能抵抗一个能改变最多 kkk 个特征的对手的挑战,在这种情况下,与设计一个能纠正 kkk 个错误的纠错码的问题是相同的。现代对可验证人工智能的追求,正站在像 Richard Hamming 和 Claude Shannon 这样的巨人肩膀上。

网络上的鲁棒性:图信号处理

我们的世界越来越被网络所描述——社交网络、交通网络、大脑连接体。图信号处理 (Graph Signal Processing, GSP) 是一个新兴领域,它将经典信号处理的强大工具扩展到定义在这些复杂、不规则结构上的数据。我们可以通过图[拉普拉斯算子的特征值](@article_id:315305)来定义图上的“频率”概念,我们可以对图信号进行滤波,例如,平滑它们或找到社群结构。

但如果网络本身是不确定的或动态的呢?也许我们只有一个社交网络连接的嘈杂快照。我们能设计一个对这种拓扑不确定性鲁棒的图滤波器吗?答案再次取决于验证。图滤波器的性能取决于图的谱(其特征值)。对图的边的随机扰动会导致特征值的移动。我们滤波器输出的稳定性取决于两件事:底层谱的稳定性,以及我们滤波器的平滑度。

矩阵扰动理论,通过像 Davis-Kahan 定理这样的结果告诉我们,如果特征空间被一个“谱隙 (spectral gap)”分开,它们就是稳定的。但这里有一个更普遍的原则在起作用:一个“尖锐”的滤波器,即被设计用来对频率进行非常精细区分的滤波器,对谱的微小变化极其敏感。另一方面,一个平滑、变化缓和的滤波器则鲁棒得多。我们面临一个贯穿整个工程学的基本权衡:​​性能与鲁棒性​​。更强的选择性是以脆弱性为代价的。一个鲁棒的图滤波器必须是一个平滑的滤波器,这个教训远远超出了图的世界。

不确定性下的现实世界决策

最终,我们研究鲁棒性是因为我们必须在一个不确定的世界里做出具有真实后果的决策。我们将要考虑的最后一个应用将这一点清晰地展现出来。

管理我们星球的资源

考虑一个依赖两口井获取淡水的沿海社区。抽水有成本,该镇希望将其最小化。然而,在海岸附近过度抽水会带来严重风险:它可能降低淡水水力压头,导致海水入侵并污染含水层。这个风险不是固定的;它取决于不确定的环境因素,如降雨(补给)和海平面异常。

这是一个多目标优化问题:我们想同时最小化成本和最小化风险。使用 ε\varepsilonε-约束方法,我们可以将其重新表述为:在我们保证海水入侵风险低于某个阈值 ε\varepsilonε 的前提下,我们能实现的最低成本是多少?关键在于保证。我们不希望风险平均低;我们希望无论在已知的不确定性范围内发生什么,风险都低。

为了解决这个问题,我们必须进行​​鲁棒优化 (robust optimization)​​。我们写下风险必须小于 ε\varepsilonε 的约束。然后我们确定不确定参数的最坏情况——在这种情况下,是最小的降雨量和最高的海平面。通过强迫我们的约束即使在这种最坏情况下也成立,我们构建了一个可以被有效解决的、单一的、确定性的优化问题。解决方案为我们提供了一个抽水策略 (x1,x2)(x_1, x_2)(x1​,x2​),它不仅仅是在某种平均意义上最优的,而且被验证为在所有可能的现实环境条件下都是安全的。我们可能会比在“最佳情况”世界里支付稍高的抽水成本,但我们买到了更有价值的东西:一份抵御环境灾难的安全证书。

一条统一的线索

我们的旅程结束了。我们看到了同一个基本思想——在一个不确定性集合上寻求对正确行为的可证明保证——出现在令人眼花缭乱的各种情境中。它确保一张图片在任何光线下都能被识别。它保护人工智能的训练不受损坏数据的影响。它保证了人造生态系统的稳定性。它支撑着我们数字世界的可靠性。它使我们能够推断细胞的隐藏机制,并就我们共享的环境做出安全的决策。

因此,可验证鲁棒性远不止是对抗性样本的一种防御。它是一种信任的语言,一种在复杂世界中构建韧性和可靠性的数学工具。它是一条美丽的线索,将信息论的历史基础与人工智能的前沿以及科学与工程的永恒挑战编织在一起。而在我们知识图景的如此多角落里发现这样一个简单而强大的思想,其本身就是科学发现的一大乐趣。