上篇讲到了非局部均值滤波方法，何曾想2005年的这篇去噪滤波的论文居然能走这么远，成了Transformer的核心。

Nonlocal attention

---

相似度计算

在Nonlocal attention中，相似度计算通过衡量不同位置（或元素）之间的相关性或相似度，为后续的加权求和提供权重信息。在nonlocal滤波中，常用的相异度计算方法是欧氏距离的平方，然而在网络中还没有办法实现范数距离，因此使用相似系数计算距离的系列，即计算内积，点这里。

描述样本（或样本特征）间相似程度的统计量很多，目前用得最多的是距离和相似系数，距离多用于样本的分类，相似系数多用于特征的分类。

相异度矩阵

相异度矩阵（Dissimilarity Matrix）用于表示数据点之间的相似度或距离。在非局部滤波（Non-local Means Filtering）中，相异度矩阵用于计算图像中不同像素块之间的相似度，进而确定权重。

相异度矩阵$\mathbf{D}$是一个$n\times n$的矩阵，其中$n$是数据点的数量。矩阵中的每个元素$D(i,j)$表示数据点$i$和数据点$j$之间的相似度（或距离）。相似度可以是多种度量方式，常见的包括欧氏距离（高斯核欧氏距离）、余弦相似度等。

用鸢尾花数据集举例，观察相异度矩阵的样子。鸢尾花数据集150个样本，这个相异度矩阵是$150\times 150$。由于一类中的样本和其他类中的样本相似性弱，因此从相异度矩阵能看出三个类别。蓝色表示距离小，黄色表示距离大。这个数据集中1-50个样本是第一类，以此类推。

---

标量的线性组合
$$\begin{array}{rl}{y}_i& =\sum _j{a}_{ij}{x}_j\\ & =a_{i1}{x}_1+a_{i2}{x}_2+\cdots +a_{in}{x}_i,i=1,2,\dots ,n\end{array}$$

向量点积形式
$$y_i=[a_{i1},a_{i2},\dots ,a_{in}]\left[\begin{array}{c}{x}_1\\ x_2\\ ⋮\\ x_i\end{array}\right]$$

矩阵形式

$$\left[\begin{array}{c}{y}_1\\ y_2\\ ⋮\\ y_i\end{array}\right]=\left[\begin{array}{cccc}{a}_{11}& a_{12}& \cdots & a_{1n}\\ a_{21}& a_{22}& \cdots & a_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ a_{n1}& a_{n2}& \cdots & a_{nn}\end{array}\right]\left[\begin{array}{c}{x}_1\\ x_2\\ ⋮\\ x_i\end{array}\right]$$

简写形式
$$\mathbf{y}=\mathbf{A}\mathbf{x}$$

---

向量的线性组合
$${\mathbf{y}}_i=\sum _j{a}_{ij}{\mathbf{x}}_j,i=1,2,\dots ,n$$

${\mathbf{y}}_i$的矩阵向量乘法表示
$${\mathbf{y}}_i^{\top }=[a_{i1},a_{i2},\dots ,a_{in}]\left[\begin{array}{c}{\mathbf{x}}_1^{\top }\\ {\mathbf{x}}_2^{\top }\\ ⋮\\ {\mathbf{x}}_n^{\top }\end{array}\right]=a_{i1}{x}_1^{\top }+a_{i2}{x}_2^{\top }+\cdots +a_{in}{x}_n^{\top }$$

矩阵形式

$$\left[\begin{array}{c}{\mathbf{y}}_1^{\top }\\ {\mathbf{y}}_2^{\top }\\ ⋮\\ {\mathbf{y}}_n^{\top }\end{array}\right]=\left[\begin{array}{cccc}{a}_{11}& a_{12}& \cdots & a_{1n}\\ a_{21}& a_{22}& \cdots & a_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ a_{n1}& a_{n2}& \cdots & a_{nn}\end{array}\right]\left[\begin{array}{c}{\mathbf{x}}_1^{\top }\\ {\mathbf{x}}_2^{\top }\\ ⋮\\ {\mathbf{x}}_n^{\top }\end{array}\right]$$

$$\mathbf{Y}=\mathbf{A}\mathbf{X}$$
其中，
样本矩阵
$$\mathbf{X}=\left[\begin{array}{c}{\mathbf{x}}_1^{\top }\\ {\mathbf{x}}_2^{\top }\\ ⋮\\ {\mathbf{x}}_n^{\top }\end{array}\right]=\left[\begin{array}{cccc}{x}_{11}& x_{12}& \cdots & x_{1n}\\ x_{21}& x_{22}& \cdots & x_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ x_{n1}& x_{n2}& \cdots & x_{nn}\end{array}\right]$$
注意力系数矩阵
$$\mathbf{A}=\left[\begin{array}{cccc}{a}_{11}& a_{12}& \cdots & a_{1n}\\ a_{21}& a_{22}& \cdots & a_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ a_{n1}& a_{n2}& \cdots & a_{nn}\end{array}\right]$$
输出矩阵
$$\mathbf{Y}=\left[\begin{array}{c}{\mathbf{y}}_1^{\top }\\ {\mathbf{y}}_2^{\top }\\ ⋮\\ {\mathbf{y}}_n^{\top }\end{array}\right]=\left[\begin{array}{cccc}{y}_{11}& y_{12}& \cdots & y_{1n}\\ y_{21}& y_{22}& \cdots & y_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ y_{n1}& y_{n2}& \cdots & y_{nn}\end{array}\right]$$

---

Nonlocal attention

卷积操作在局部区域进行特征提取。non-local处理将特征图上的特征点表示为所有特征点的加权和，在全局范围内用其他位置的特征增强当前位置的特征。

通用的non-local操作定义：

$${\mathbf{y}}_i=\frac{1}{C_i}\sum _{\forall j}s({\mathbf{x}}_i,{\mathbf{x}}_j)\psi ({\mathbf{x}}_j)$$

式中，$\mathbf{x}$为对应位置上的输入特征，$\mathbf{y}$为增强后的输出，$s({\mathbf{x}}_i,{\mathbf{x}}_j)$计算${\mathbf{x}}_i$和${\mathbf{x}}_j$之间的相似性，$\psi (\cdot )$则用于对$j$的特征进行变换，$C_i$用于对输出进行归一化。

简而言之，non-local的核心是计算当前位置的特征与特征图所有特征间的相似性，然后根据相似性对所有特征加权输出。

在实现时，相似性函数$s$则可以有以下选择（通过实验发现函数$s$的具体实现影响不大）：

以下是Nonlocal Network中给出的相似度计算公式：

1. Gaussian Function（高斯函数）

公式为：

$$s({\mathbf{x}}_i,{\mathbf{x}}_j)={\mathrm{e}}^{{\mathbf{x}}_i^{\top }{\mathbf{x}}_j}$$

其中，${\mathbf{x}}_i$和${\mathbf{x}}_j$分别表示两个位置（或元素）的特征向量。这个公式直接计算了特征向量之间的点积，并通过指数函数进行放大，以得到相似度权重。

2. Embedded Gaussian（嵌入高斯）

公式为：

$$s({\mathbf{x}}_i,{\mathbf{x}}_j)={\mathrm{e}}^{\theta ({\mathbf{x}}_i{)}^{\top }\varphi ({\mathbf{x}}_j)}$$

其中，$\theta ({\mathbf{x}}_i)$和$\varphi ({\mathbf{x}}_j)$分别表示对${\mathbf{x}}_i$和${\mathbf{x}}_j$进行的线性变换（通常通过1x1卷积实现）。这种方法通过嵌入空间中的点积来计算相似度。

3. Dot Product（点积）

公式为：

$$s({\mathbf{x}}_i,{\mathbf{x}}_j)=\theta ({\mathbf{x}}_i{)}^{\top }\varphi ({\mathbf{x}}_j)$$

与Embedded Gaussian类似，这种方法也使用了线性变换后的特征向量进行点积运算。

4. Concatenation（拼接）

公式为：

$$s({\mathbf{x}}_i,{\mathbf{x}}_j)=\text{ReLU}(w_f^{\top }[\theta ({\mathbf{x}}_i),\varphi ({\mathbf{x}}_j)])$$

其中，$[\theta ({\mathbf{x}}_i),\varphi ({\mathbf{x}}_j)]$表示将$\theta ({\mathbf{x}}_i)$和$\varphi ({\mathbf{x}}_j)$拼接成一个更长的向量，$w_f$是一个可学习的权重向量。这种方法通过拼接和线性变换来捕捉不同位置之间的复杂关系，并通过ReLU函数引入非线性。

函数$\theta$、$\varphi$、$\psi$选择为线性变换，${\mathbf{W}}_{\theta }$、${\mathbf{W}}_{\varphi }$和${\mathbf{W}}_{\psi }$为可学习的权重矩阵，一般为$1\times 1$的卷积。

---

通过softmax函数对计算得到的相似度进行归一化处理，以确保权重之和为1。

---

根据信息检索领域的一些术语分别起了名字，即查询（Query）、关键词（Key）和内容（Value）。通过 Query 和 Key 计算相似度，生成注意力权重，再对 Value 加权求和。自注意力（例如Transformer）它们是同一值，尽管是不同的线性变换。一般K和V是同样的。

${\mathbf{W}}_{\theta }\to {\mathbf{W}}_Q$
${\mathbf{W}}_{\varphi }\to {\mathbf{W}}_K$
${\mathbf{W}}_{\psi }\to {\mathbf{W}}_V$

---

图书馆检索系统

Query (Q)	你的研究问题
Keys (K)	每本书的目录、索引、关键词（检索系统匹配的依据）
Values (V)	每本书的实际内容
相似度计算	系统比较你的问题与每本书的目录匹配程度
Softmax(权重)	根据匹配程度，决定每本书在最终报告中占多大比例
加权求和	研究员助理按比例提取各书内容，合成一份报告

比图书馆更精确的比喻：专家委员会

• 你的问题 (Q) = 委托研究课题
• 专家的简历 (K) = 他们的专长领域（用来匹配）
• 专家的知识 (V) = 他们的实际知识
• 权重 = 每位专家在委员会中的发言权重
• 加权输出 = 委员会提交的综合报告

复杂问题通常涉及多个交叉领域，单个专家有盲点，委员会可以互补。

---

矩阵表示，这只是为了实现。

但是，需要计算所有点的输出，怎么办呢？循环？矩阵工作室不喜欢，GPU不喜欢。一切为了利用GPU的并行计算功能。

reshape

在非局部注意力机制中，为了方便计算相似度并进行加权求和，首先需要对高维特征（如图像块）进行reshape。

假设输入特征图$\mathbf{X}$，其尺寸为$H\times W\times d$，其中$H$和$W$是特征图的高度和宽度，$d$是特征数（通道数）。将特征图$\mathbf{X}$reshape成一个二维矩阵$\mathbf{X}$，其形状为$n\times d$，其中，$n=HW$，这样每个行向量代表了一个位置的特征向量。

$$\mathbf{X}=\text{reshape}(\mathbf{X},(H\times W,d))$$

图$n\times d$维的数据矩阵$\mathbf{X}$的结构，其中第$n$行代表转置后的数据向量${\mathbf{x}}_i^{\top }$。图中展示了一个$n\times d$的矩阵：每行对应一个 token（如一个词或图像 patch）；每列对应一个特征维度。

矩阵运算

---

这两幅图说明如何通过矩阵乘法实现。

1. 计算相异度矩阵（模式识别中的基础概念，后面紧跟）
   
2. 加权求和
   

注：如果公式对你来说只是运算，那太可悲了。我很同情这样讲解nonlocal的人，对线性变换的意义完全不理解。

---

加权求和是将每一个向量（彩色条）用它对应的相似度（彩色点）作为权重相乘，并求和。这里如若对矩阵乘积运算很熟悉，了解它的几何意义，而不是只会计算，那对该矩阵运算想做什么一目了然。然而，上面引用的那个图的黄线和黄点即说明了如何进行矩阵运算。这里简单说明线性变换的几何意义。

线性变换相当于空间变换，即从一个空间变换到另一个空间，变换矩阵的每一行实际上是变换空间的基向量，左边的每一行（彩色点）实际上在新空间的表示系数，空间变换就是基向量的线性组合。如果你的线性代数老师没有讲线性变换的几何意义，那就让你的老师回家卖红薯去吧。这里用矩阵后乘表示。

强调：虽然是两两计算内积，但是两个矩阵的地位是不同的，对于每个$q$，计算与$K$中所有点的内积，结果一行是每个$q$在$K$中对应的权系数。无论归一化，还是后面Transformer中除以$\sqrt{d_k}$都是对行进行处理。

补充说明

• Self-Attention 的输入用矩阵$\mathbf{X}$进行表示，则使用线性变换矩阵${\mathbf{W}}_Q$、${\mathbf{W}}_K$和${\mathbf{W}}_V$计算$\mathbf{Q}$、$\mathbf{K}$、$\mathbf{V}$矩阵。线性变换的目的是特征变换，类比PCA，目的是降维，比如降维为原来的$1/2$。降维是模式识别的基本概念，学过模式识别的都知道它的作用。不同的是，${\mathbf{W}}_Q$、${\mathbf{W}}_K$和${\mathbf{W}}_V$是可学习的权重矩阵。
• Transformer的自注意力中的相似度计算简单使用两点的点积，特征变换后的两点内积。
• 这个softmax归一化公式实际上有问题。公式中的 Softmax 是对相异度矩阵的每一行用Softmax进行归一化，即每一行的和都变为 1。代码中这样写没有问题，这个函数可以独立处理矩阵的每一维。那些不能区分数学语言和函数语言的人，我表示无能为力。
• 为什么用softmax进行归一化？softmax通过指数运算（exp函数）对输入值进行放大，从而放大了输入值之间的差异。高斯滤波、双边滤波和非局部滤波的权重都是距离的（负）指数函数。其实概率分布中很多都是指数函数，这说明什么呢？说明自然界中很多现象都适合用指数函数描述。

---

计算过程

2. 线性变换：
   • 为了计算自注意力，首先对输入序列进行线性变换，生成三个不同的向量：查询向量（Query）、关键词向量（Key）和内容向量（Value）。分别表示为$Q$、$K$和$V$。

$$Q=\mathbf{X}{\mathbf{W}}_Q,K=\mathbf{X}{\mathbf{W}}_K,V=\mathbf{X}{\mathbf{W}}_V$$

其中$\mathbf{X}$是输入序列，${\mathbf{W}}_Q$、${\mathbf{W}}_K$和${\mathbf{W}}_V$是可学习的权重矩阵。

3. 计算相异度矩阵：
   • 计算查询向量和关键词向量之间的点积，得相异度矩阵$S$。

$$S=\frac{Q{K}^{\top }}{\sqrt{d_k}}$$

4. 应用 Softmax：
应用 Softmax 函数对相异度矩阵$S$行归一化 ，得注意力权重矩阵$A$。

$$A=\text{softmax}(S)$$

5. 加权求和：

• 使用注意力权重矩阵$A$对内容向量$V$进行加权求和，得到输出向量$Y$。

$$Y=AV$$

---

网络实现，这只是矩阵表示的网络实现

Nonlocal的块中加了一个残差连接，残差学习的作用不用说了吧。

---

1. 线性变换
   $$\begin{array}{r}\underset{n\times l}{\underbrace{\mathbf{Q}}}=\underset{n\times d}{\underbrace{\mathbf{X}}}\underset{d\times l}{\underbrace{{\mathbf{W}}_Q}}\\ \underset{n\times l}{\underbrace{\mathbf{K}}}=\underset{n\times d}{\underbrace{\mathbf{X}}}\underset{d\times l}{\underbrace{{\mathbf{W}}_K}}\\ \underset{n\times l}{\underbrace{\mathbf{V}}}=\underset{n\times d}{\underbrace{\mathbf{X}}}\underset{d\times l}{\underbrace{{\mathbf{W}}_V}}\end{array}$$

2. 计算注意力权重矩阵
   $$\underset{n\times n}{\underbrace{\mathbf{A}}}=\mathrm{softmax}\left[\mathbf{Q}{\mathbf{K}}^{\top }\right]$$

3. 加权求和
   $$\underset{n\times l}{\underbrace{\mathbf{H}}}=\underset{n\times n}{\underbrace{\mathbf{A}}}\underset{n\times l}{\underbrace{\mathbf{V}}}$$

4. 线性变换（为了残差连接）
   $$\underset{n\times d}{\underbrace{\mathbf{Y}}}=\underset{n\times l}{\underbrace{\mathbf{H}}}\underset{l\times d}{\underbrace{{\mathbf{W}}_Y}}$$

5. 残差连接
   $$\underset{n\times d}{\underbrace{\mathbf{Z}}}=\underset{n\times d}{\underbrace{\mathbf{X}}}+\underset{n\times d}{\underbrace{\mathbf{Y}}}$$