Center Smoothing: Certified Robustness for Networks with Structured Outputs

中心平滑：经过认证的具有结构化输出的网络的鲁棒性

Summary

写完笔记之后最后填，概述文章的内容，以后查阅笔记的时候先看这一段。

center smooth：对于给定的输入 $x$ 与函数 $f$，以及对 $x$ 的 $l_2$ 扰动半径 ${ϵ}_1$。中心平滑的目的是：在输出空间中计算一个最小半径为 $r$ 的包围球，该球的球心为 $\bar{f}(\mathbf{x})$，这时候的最小包围球包含至少一半的 $f\left(\mathbf{x}+\mathcal{N}\left(0,{\sigma }_{cs}^{2}I\right)\right)$。这时候的 $\bar{f}$ 为 $f$ 平滑函数，$\bar{f}(\mathbf{x})$为 $f(x)$在点 $x$ 的平滑输出结果。整个过程如下表示：
$$\forall x^{\prime }\text{ s.t. }{\Vert x-x^{\prime }\Vert }_2\le {ϵ}_1,d\left(\bar{f}(x),\bar{f}\left(x^{\prime }\right)\right)\le {ϵ}_2$$
意义在于：给定输入的扰动范围为 ${ϵ}_1$，经过平滑后的 $\bar{f}$ 能可证明地保证输出变化在 $ \epsilon_2$ 内。解决了 Randomized Smoothing只能局限于具有一维实值输出的分类任务和模型，从而能扩展到可证明的结构化输出（图像、文本、集合）问题。

Research Objective

作者的研究目标。

结构化输出（图像、文本、集合）的可证明鲁棒性

Problem Statement

问题陈述，要解决什么问题？

1. 对于图像、文本、集合等结构化输出的问题，可证明的鲁棒性的目标是什么并不是很明显。
2. 可证明的对抗鲁棒性研究主要局限于研究具有一维实值输出的分类任务和模型。

Methods

解决问题的方法/算法是什么？

1. center smoothing：对于给定的输入 $x$，中心平滑使用高斯平滑分布对 $x$ 附近的一组点进行采样，计算每个点上的函数值 $f(x)$，并返回包含输出中至少一半点的最小球的中心空间。
2. 为了优化上述问题，通过计算与样本中所有其他点的中值距离最小的点来近似中心空间的位置。

定义 $\mathcal{P}$ 下 $f$ 的平滑版本 $\bar{f}$ 作为在 $M$ 中半径最小的球的中心，该球至少包含一半的 $f(x+\mathcal{P})$ 概率质量：
$${\bar{f}}_{\mathcal{P}}(x)=\underset{z}{\mathrm{argmin}}r\text{ s.t. }\mathbb{P}[f(X)\in \mathcal{B}(z,r)]\ge \frac{1}{2}$$
B ( z , r ) = { z ′ ∣ d ( z , z ′ ) ≤ r } \mathcal{B}(z, r)=\left\{z^{\prime} \mid d\left(z, z^{\prime}\right) \leq r\right\} B(z,r)={z′∣d(z,z′)≤r}

1. $\bar{f}$ 为 $f$ 的平滑版本，$f(x)$ 为 $M$中的一个输出元素
2. $\mathcal{P}$ 为平滑噪音的分布，$\delta$为每一个采样
3. $z$ 为输出空间 $M$ 中的一个元素
4. $X=x+\mathcal{P}$代表 $x+\delta$的概率分布，对于输入空间 $\mathcal{D}$ 中的一个元素采样 $x$, 对其进行加平滑噪音

center smooth：
$$\forall x^{\prime }\text{ s.t. }{\Vert x-x^{\prime }\Vert }_2\le {ϵ}_1,\mathbb{P}\left[f\left(X^{\prime }\right)\in \mathcal{B}(\bar{f}(x),R)\right]>\frac{1}{2}$$

$$d\left(\bar{f}(x),\bar{f}\left(x^{\prime }\right)\right)\le 2R$$

$$\begin{array}{rl}d\left(\bar{f}(x),\bar{f}\left(x^{\prime }\right)\right)& \le d(\bar{f}(x),y)+d\left(y,\bar{f}\left(x^{\prime }\right)\right)\\ & \le R+r^{\ast }\left(x^{\prime }\right)\end{array}$$

$$r^{\ast }\left(x^{\prime }\right)\le R$$

$\mathcal{B}(\bar{f}(x^{\prime }),r^{\ast }(x^{\prime }))$：$\bar{f}(x^{\prime })$ 为半径最小的球的中心，至少包含 $f(x^{\prime }+P)$ 概率质量的一半， $r^{\ast }(x^{\prime })$ 为最小半径的值

$ \mathcal{B}(\bar{f}(x),R)$：$\bar{f}(x)$ 为球的中心，对于所有满足 $\Vert x-x^{\prime }{\Vert }_2\stackrel{\cdot }{\le }{ϵ}_1$ 的 $x\prime$，包含 $f(x\prime +P)$ 的概率质量的一半以上，$R$ 为球的半径。

上述结果从理论上为我们提供了 $f$ 的平滑版本 $\bar{f}$，具有可证明的鲁棒性保证。因为经过平滑后的$\bar{f}(x)$与所有$f\left(\mathbf{x}+\mathcal{N}\left(0,{\sigma }_{cs}^{2}I\right)\right)$的中心距离能够被bound住，因为一个对抗扰动很难去改变$f\left(\mathbf{x}+\mathcal{N}\left(0,{\sigma }_{cs}^{2}I\right)\right)$的中心，所以平滑版本的$\bar{f}$能够保证输出的变化的上限。

Evaluation

作者如何评估自己的方法，有没有问题或者可以借鉴的地方。

Conclusion

作者给了哪些strong conclusion, 又给了哪些weak conclusion?

Notes

在这些框架外额外需要记录的笔记。

Gaussian Smoothing

$$\bar{h}(x)=\underset{c\in \mathcal{Y}}{\mathrm{argmax}}\mathbb{P}[h(x+\delta )=c]$$

$$p_{ϵ}=\Phi \left({\Phi }^{-1}(p)-ϵ/\sigma \right)$$

累计分布函数 $\Phi$（CDF）是概率分布函数（PDF）的积分。这很好理解。

逆累计分布函数 ${\Phi }^{-1}$（ICDF)简单地说，是累计分布函数的反函数。

CDF：已知横轴（某一事件）（值）求纵轴（概率）；

ICDF：已知纵轴（概率）求横轴（某一事件）（值）；

常用希腊字母

以下是常用希腊字母及其在数学、统计学和科学中的读法：

• α (alpha)：常用表示显著性水平，一般读作 “阿尔法”。
• β (beta)：常用表示回归系数或错误率，读作 “贝塔”。
• γ (gamma)：常用表示形状参数或比率，读作 “伽玛”。
• δ (delta)：常用表示误差或变化量，读作 “德尔塔”。
• ε (epsilon)：常用表示小量或误差项，读作 “艾普西隆”。
• ζ (zeta)：常用表示 Riemann zeta 函数，读作 “泽塔”。
• η (eta)：常用表示效应量或预测误差，读作 “艾塔”。
• θ (theta)：常用表示角度或参数，读作 “西塔”。
• κ (kappa)：常用表示柯西分布或相关系数，读作 “卡帕”。
• λ (lambda)：常用表示特征值或密度函数，读作 “兰姆达”。
• μ (mu)：常用表示均值或期望值，读作 “缪”。
• ν (nu)：常用表示自由度或频率，读作 “纽”。
• ξ (xi)：常用表示方差或未知量，读作 “克西”。
• π (pi)：常用表示圆周率或概率密度函数，读作 “派”。
• ρ (rho)：常用表示相关系数或密度函数，读作 “柔”。
• σ (sigma)：常用表示标准差或方差，读作 “西格玛”。
• τ (tau)：常用表示 Kendall tau 相关系数或时间常数，读作 “陶”。
• υ (upsilon)：常用表示假设检验中的自由度，读作 “宇普西隆”。
• φ (phi)：常用表示正态分布的概率密度函数，读作 “斐”。
• χ (chi)：常用表示卡方分布，读作 “卡伊”。
• ψ (psi)：常用表示角度函数或叶赛尔函数，读作 “普赛”。
• ω (omega)：常用表示角频率或参数，读作 “欧米伽”。

霍夫丁不等式（Hoeffding’s inequality）

1.简述

在概率论中，霍夫丁不等式给出了随机变量的和与其期望值偏差的概率上限，该不等式被Wassily Hoeffding于1963年提出并证明。霍夫丁不等式是Azuma-Hoeffding不等式的特例，它比Sergei Bernstein于1923年证明的Bernstein不等式更具一般性。这几个不等式都是McDiarmid不等式的特例。

2.霍夫丁不等式

2.1.伯努利随机变量特例

掷硬币，假设正面朝上概率为 p ，反面朝上概率为 1-p ，投掷 n 次，则正面朝上次数的期望值为 np 。更进一步，有以下不等式：
$$P(H(n)\le k)=\sum _{i=0}^k\left(\genfrac{}{}{0ex}{}{n}{i}\right)p^i(1-p{)}^{n-i}$$
其中， H(n) 是 n 次投掷中，正面朝上的次数。

对某一 $\epsilon >0$ ，有 $k=(p-\epsilon )n$ ，上述不等式确定的霍夫丁上界将会按照指数级变化：
$$P(H(n)\le (p-\epsilon )n)\le exp(-2{\epsilon }^{2}n)(\mathrm{2.1.1})$$
类似地，可以得到：
$$P(H(n)\ge (p+\epsilon )n)\le exp(-2{\epsilon }^{2}n)(\mathrm{2.1.2})$$
综合(2.1.1)(2.1.2)，可得：
$$P((p-\epsilon )n\le H(n)\le (p+\epsilon )n)\ge 1-2exp(-2{\epsilon }^{2}n)(\mathrm{2.1.3})$$
令 $\epsilon =\sqrt{\ln n/n}$ ，代入(2.1.3)，有：
$$P(|H(n)-pn|\le \sqrt{\ln n/n})\ge 1-2exp(-2\ln n)=1-2/n^2(\mathrm{2.1.4})$$
(2.1.4)即为霍夫丁不等式的伯努利随机变量特例。

2.2.一般形式

令 $X_1，\dots ，X_n$ 为独立的随机变量，且 $X_i\in [a,b]，i=1，\dots ，n$ 。这些随机变量的经验均值可表示为：
$$\bar{X}=\frac{X_1+\cdots +X_n}{n}$$
霍夫丁不等式叙述如下：
$$\forall t>0，P(\bar{X}-E[\bar{X}]\ge t)\le exp(-\frac{2n^2{t}^2}{\begin{array}{c}{\sum }_{i=1}^n(b_i-a_i{)}^2\end{array}})(\mathrm{2.2.1})$$
令 $\bar{X}=-\bar{X}$ ，代入上述不等式，可得：
$$\forall t>0，P(E[\bar{X}]-\bar{X}\ge t)\le exp(-\frac{2n^2{t}^2}{\begin{array}{c}{\sum }_{i=1}^n(b_i-a_i{)}^2\end{array}})(\mathrm{2.2.2})$$
综合(2.2.1)(2.2.2)，可得霍夫丁不等式的另一种形式：
$$\forall t>0，P(|\bar{X}-E[\bar{X}]|\ge t)\le 2exp(-\frac{2n^2{t}^2}{\begin{array}{c}{\sum }_{i=1}^n(b_i-a_i{)}^2\end{array}})(\mathrm{2.2.3})$$
若令 $S_n=X_1+\cdots +X_n$ ，霍夫丁不等式可叙述为：
$$
\forall{t>0}，\quad P(S_n-E[S_n]\ge t)\le exp(-\frac{2t^2}{\begin{matrix} \sum_{i=1}^n (b_i-a_i)^2 \end{matrix}}) \quad (2.2.4)\

\forall{t>0}，\quad P(E[S_n]-S_n\ge t)\le exp(-\frac{2t^2}{\begin{matrix} \sum_{i=1}^n (b_i-a_i)^2 \end{matrix}}) \quad (2.2.5)\

\forall{t>0}，\quad P(|S_n-E[S_n]|\ge t)\le 2exp(-\frac{2t^2}{\begin{matrix} \sum_{i=1}^n (b_i-a_i)^2 \end{matrix}}) \quad (2.2.6)\
$$
从(2.2.1)推导(2.2.4)，只需对不等式 $\bar{X}-E[\bar{X}]\ge t$ 左右两边同乘系数 $n$ ，再令 $t=nt$ 即可。不难看出，当 $X_i$ 为伯努利随机变量时，(2.2.6)即可转化为(2.1.4)。

需要注意的是， $X_i$ 若为无放回抽样时的随机变量，该等式依然成立，尽管此时这些随机变量已不再独立。相关证明可查看Hoeffding在1963年发表的论文。在无放回抽样时，若想要更好的概率边界，可查看Serfling在1974年发表的论文。

学习链接：https://zhuanlan.zhihu.com/p/45342697

随机变量时，(2.2.6)即可转化为(2.1.4)。

需要注意的是， $X_i$ 若为无放回抽样时的随机变量，该等式依然成立，尽管此时这些随机变量已不再独立。相关证明可查看Hoeffding在1963年发表的论文。在无放回抽样时，若想要更好的概率边界，可查看Serfling在1974年发表的论文。

学习链接：https://zhuanlan.zhihu.com/p/45342697