Local & non-local
Local这个词主要是针对感受野(receptive field)来说的。以卷积操作为例，它的感受野大小就是卷积核大小，而我们一般都选用33，55之类的卷积核，它们只考虑局部区域，因此都是local的运算。同理，池化(Pooling)也是。
而non-local指的就是感受野可以很大，不是一个局部领域，比如全连接就是non-local的，而且是global的。但是全连接带来了大量的参数，给优化带来困难。这也是卷积神经网络近年来流行的原因，考虑局部区域，参数大大减少了，能够训得动了。
local不足：
(1) 捕获长范围依赖的效率太低；
(2) 由于网络很深，需要小心的设计模块和梯度；
(3) 当需要在比较远位置之间来回传递消息时，这是局部操作是困难的.
Non-local block
y i = 1 c ( x ) ∑ v j f ( x i , x j ) g ( x j ) y_{i}= \frac{1}{c(x)}\sum _{vj}f(x_{i},x_{j})g(x_{j}) yi=c(x)1vj∑f(xi,xj)g(xj)
- 输入是x，输出是y，可以是图像、序列和视频，通常是特征图。
- i i i 和 j j j 分别代表输入的某个位置，通用来说这个位置可以是时间、空间和时空。
- x i ∈ R f i n ∗ 1 x_i \in R^{fin*1} xi∈Rfin∗1是一个向量，是该node的特征
- f ( x i , x j ) ∈ R 0 f(x_i,x_j)\in R^0 f(xi,xj)∈R0是一个计算任意两点相似关系的函数
- g ( x j ) ∈ R f o u t ∗ 1 g(x_j)\in R^{fout*1} g(xj)∈Rfout∗1是一个映射函数，可以看成是计算一个点的特征。
- c ( x ) ∈ R 0 c(x)\in R^0 c(x)∈R0是归一化函数，保证变换前后整体信息不变。
其中，映射函数
g
(
x
j
)
∈
R
f
o
u
t
∗
1
g(x_j)\in R^{fout*1}
g(xj)∈Rfout∗1 可以采用1x1卷积，代表线性嵌入，其形式为：
g
(
x
j
)
=
W
g
x
j
g(x_{j})=W_{g}x_{j}
g(xj)=Wgxj
相似性度量函数f的选择有多种，然而不同的non-local block的形式效果差不多，说明是non-local block的结构在起作用，而对具体的表达方式不敏感。：
-
Gaussian: f ( x i , x j ) = e x i T x j ， c ( x ) = ∑ ∀ j f ( x i , x j ) f(x_{i},x_{j})=e^{x_{i}^{T}x_{j}}，c(x)= \sum _{\forall j}f(x_{i},x_{j}) f(xi,xj)=exiTxj，c(x)=∀j∑f(xi,xj)
对两个位置进行点乘，然后通过指数映射，放大差异。
如果把C(x)考虑进去，那么就是softmax形式： y = s o f t max ( x T W θ T W ϕ x ) g ( x ) y=soft \max(x^{T}W_{\theta}^{T}W_{\phi}x)g(x) y=softmax(xTWθTWϕx)g(x)
就是目前常用的位置注意力机制的表达式，所以说语义分割中大部分通道注意力机制都是本文的特殊化。 -
Embedded Gaussian: f ( x i , x j ) = e θ ( x i ) T ϕ ( x j ) ， c ( x ) = ∑ ∀ j f ( x i , x j ) f(x_{i},x_{j})=e^{\theta(x_{i})^{T}\phi(x_{j})}，c(x)= \sum _{\forall j}f(x_{i},x_{j}) f(xi,xj)=eθ(xi)Tϕ(xj)，c(x)=∀j∑f(xi,xj)
前面的gaussian形式是直接在当前空间计算，而(2)更加通用，在嵌入空间中计算高斯距离。这里： θ ( x i ) = W θ x i ϕ ( x j ) = W ϕ x j \begin{matrix} \theta(x_{i})=W_{\theta}x_{i}\\ \phi(x_{j})=W_{\phi}x_{j}\\ \end{matrix} θ(xi)=Wθxiϕ(xj)=Wϕxj -
Dot Product: f ( x i , x j ) = θ ( x i ) T ϕ ( x j ) f(x_{i},x_{j})= \theta(x_{i})^{T}\phi(x_{j}) f(xi,xj)=θ(xi)Tϕ(xj)其中C(x)=N，像素个数。
-
Concatenation: f ( x i , x j ) = R e L U ( w f T [ θ ( x i ) , ϕ ( x j ) ] ) f(x_{i},x_{j})=ReLU(w_{f}^{T}\left[ \theta(x_{i}), \phi(x_{j})\right]) f(xi,xj)=ReLU(wfT[θ(xi),ϕ(xj)]) 这相当于embedded的两个点拼接作为带ReLU激活函数全连接层的输入。它在visual reasoning中用的比较多。
为了能让non-local操作作为一个组件，可以直接插入任意的神经网络中，作者把non-local设计成residual block的形式，让non-local操作去学x的residual： z i = W z y i + x i z_{i}=W_{z}y_{i}+x_{i} zi=Wzyi+xi可以看出，上面构造成了残差形式。上面的做法的好处是可以随意嵌入到任何一个预训练好的网络中，因为只要设置 W z W_z Wz初始化为0，那么就没有任何影响，然后在迁移学习中学习新的权重。这样就不会因为引入了新的模块而导致预训练权重无法使用。
具体流程如下：
- 首先网络输入是X= (batch, h, w, 1024) ，经过Embedded Gaussian中的两个嵌入权重变换 W θ W_{\theta} Wθ， W ϕ W_{\phi} Wϕ得到(batch, h, w, 512), (batch, h, w, 512), 其实这里的目的是降低通道数，减少计算量；
- 然后分别对这两个输出进行reshape操作，变成(batch, hw, 512)，后对这两个输出进行矩阵乘(其中一个要转置)，计算相似性，得到(batch, hw, hw),
- 然后在第2个维度即最后一个维度上进行softmax操作，得到(batch, hw, hw), 意这样做就是空间注意力，相当于找到了当前图片或特征图中每个像素与其他所有位置像素的归一化相关性；
- 然后将g也采用一样的操作，先通道降维，然后reshape；
- 然后和 (batch, hw, hw)进行矩阵乘，得到(batch, h, w, 512), 即将空间注意力机制应用到了所有通道的每张特征图对应位置上，本质就是输出的每个位置值都是其他所有位置的加权平均值，通过softmax操作可以进一步突出共性。
- 最后经过一个1x1卷积恢复输出通道，保证输入输出尺度完全相同。
结论：
- 使用四个相似度计算模型，发现影响不大，但是都比baseline效果好。
- 以ResNet50为例，测试加在不同stage下的结果。可以看出在res2,3,4部分得到的结果相对baseline提升比较大，但是res5就一般了，这有可能是由于第5个stage中的feature map的spatial size比较小，信息比较少，所以提升比较小。
- 尝试添加不同数量的non local block ,结果如下。可以发现，添加越多的non local 模块，其效果越好，但是与此同时带来的计算量也会比较大，所以要对速度和精度进行权衡。
- Non-local 与3D卷积的对比，发现要比3D卷积计算量小的情况下，准确率有较为可观的提升。
- 作者还将Non-local block应用在目标检测、实例分割、关键点检测等领域。可以将non-local block作为一个trick添加到目标检测、实例分割、关键点检测等领域, 可能带来1-3%的提升。
不足：
(1) 只涉及到了位置注意力模块，而没有涉及常用的通道注意力机制
(2) 可以看出如果特征图较大，那么两个(batch,hxw,512)矩阵乘是非常耗内存和计算量的，也就是说当输入特征图很大存在效率底下问题，虽然有其他办法解决例如缩放尺度，但是这样会损失信息，不是最佳处理办法。
Non-local与CNN、self-attention、FCN、GCN的联系和区别
可以将CNN、self-attention、GCN视为Non-local的特例
1. GCN
f ( x i , x j ) ∈ R 0 f(x_i,x_j)\in R^0 f(xi,xj)∈R0定义为 i 和 j 两个node之间是否有边，1表示有边相连，0表示没有边。
2. CNN
y
i
=
∑
j
=
0
L
−
1
∑
k
=
0
L
−
1
W
j
k
x
i
−
L
2
+
j
,
i
−
L
2
+
k
y_{i}= \sum _{j=0}^{L-1}\sum _{k=0}^{L-1}W_{jk}x_{i- \frac{L}{2}+j,i- \frac{L}{2}+k}
yi=j=0∑L−1k=0∑L−1Wjkxi−2L+j,i−2L+k
其中
L
L
L为卷积核长度， 公式简写为：
y
i
=
∑
j
=
0
L
−
1
∑
k
=
0
L
−
1
g
j
k
(
x
i
−
L
2
+
j
,
i
−
L
2
+
k
)
y_{i}= \sum _{j=0}^{L-1}\sum _{k=0}^{L-1}g_{jk}(x_{i- \frac{L}{2}+j,i- \frac{L}{2}+k})
yi=j=0∑L−1k=0∑L−1gjk(xi−2L+j,i−2L+k)
-
对node做空间变换，即 g j k ( x i − L 2 + j , i − L 2 + k ) g_{jk}(x_{i- \frac{L}{2}+j,i- \frac{L}{2}+k}) gjk(xi−2L+j,i−2L+k), 而且对不同点做的空间变换不同
-
虽然没显式地针对node与node之间地相关性进行建模，但是每个node的空间变换不相同，这个不相同隐式地包含了点与点之间的相关性，不过这个相关性相对输入而言是静态的，即无论输入怎么变，点与点之间的相关性一经训练完成就再也不会变化。
如：BN中的γ对每个通道有一个加权，BN中的γ是静态的，训练结束后每个通道的加权不会根据输入的变化而变化， -
y i y_i yi 仅取决于 i 附近的node（卷积核的size决定其范围）。
3. self-attention
g ( x j ) = W g x j g(x_j)=W_gx_j g(xj)=Wgxj， f ( x i , x j ) = x i T W θ T W ϕ x j f(x_{i},x_{j})=x_{i}^{T}W_{\theta}^{T}W_{\phi}x_{j} f(xi,xj)=xiTWθTWϕxj，其中 W g , W θ , W ϕ ∈ R f o u t × f i n W_{g},W_{\theta},W_{\phi}\in R^{fout \times fin} Wg,Wθ,Wϕ∈Rfout×fin
-
对node做空间变换 g ( x j ) g(x_j) g(xj)，但是对每个点的空间变换是相同的
-
通过 f ( x i , x j ) f(x_{i},x_{j}) f(xi,xj)对每个空间变化之后的特征进行加权， f ( x i , x j ) f(x_{i},x_{j}) f(xi,xj) （即self-attention）显式地对node与node之间的相关性进行了建模，而且这个相关性相对输入而言是动态的。
如：SENet会通过SE模块去学每个通道的加权（论文中叫attention），训练结束后每个通道上的attention会因为输入不同而发生变化。
-
y i y_i yi 取决于上一层所有的node
4. FCN
non-local block利用两个点的相似性对每个位置的特征做加权，而全连接层则是利用position-related的weight对每个位置做加权。
于是，全连接层可以看成non-local block的一个特例：
- 任意两点的相似性仅跟两点的位置有关，而与两点的具体坐标无关，即 f ( x i , x j ) = w i j f(x_{i},x_{j})=w_{ij} f(xi,xj)=wij
- g是identity函数， g ( x j ) = x j g(x_j)=x_j g(xj)=xj
- 归一化系数为1。归一化系数跟输入无关，全连接层不能处理任意尺寸的输入。
代码https://github.com/AlexHex7/Non-local_pytorch
https://zhuanlan.zhihu.com/p/33345791
https://www.cnblogs.com/jins-note/p/11884182.html
https://zhuanlan.zhihu.com/p/147654689