QuadTree阅读笔记
- Q1 论文试图解决什么问题？
- 还是视觉Transformer中，试图引入线性的Attention，解决高分辨率图片的处理中，token数目很大、计算开销较大的问题。不同的是，本文试图通从数据结构的角度引入线性Attention。
- Q2 这是否是一个新的问题？
- 线性Transformer并不是一个新的问题，但是通过数据结构的方式实现是一个较新的方式。
- Q3 这篇文章要验证一个什么科学假设？
- 过去的Transformer加速工作中，要么使用强制局部性对Attention特有的长距离关系捕捉有损害；要么会对图像的细节有所损害。
- 本文试图通过数据结构的方式能够平等地捕捉各种距离的关系，同时也能对更重要的部分使用更加细致的注意力。
- Q4 有哪些相关研究？如何归类？谁是这一课题在领域内值得关注的研究员？
- 线性近似的Transformer在视觉任务中表现地不好；
- PVT使用了下采样的 $K$ 和 $V$，对像素级别的信息有损失；
- Swin使用了窗口注意力机制，对Transformer的长距离信息有所损害；
- Q5 论文中提到的解决方案之关键是什么？
- 使用一种四叉树的思想，对于每层构建一个特征金字塔；我们的目标是获得最高分辨率的注意力图上，$(QK)V$ 的结果。首先我们生成最高分辨率特征层上的 $QKV$，然后通过平均池化或者
stride=2卷积的方式获得粗粒度特征层上的 $QKV$。 - 计算某个块的注意力分数时，从特征金字塔的顶层到底层进行计算。对于每层计算出注意力分数后，取前 $K$ 大的块继续向下递归，在这 $K$ 个块对应的 $4K$ 个块中继续选取前 $K$ 大的块再往下递归。
- QuadTree-A 直接使用原始的注意力分数。QuadTree-B 对于每层特征图维护一个可学习的加权系数，防止比较粗粒度的特征图占据过大的权重。
- 复杂度：需要计算最顶层特征的整个特征图；然后对于下面每层只需要计算 $K$ 次。假设一共下采样了 $m$ 次，总体复杂度为 $O\left(n\left(\frac{n}{4^m}+4K\right)d\right)$ 。论文中对于分类任务，$m=2,K=8$ 。
- 实际代码实现中，对于整个注意力图的并行求法较难实现，似乎需要自己写一些
.cpp和.cu算子，暂时没太看懂具体实现。
- 使用一种四叉树的思想，对于每层构建一个特征金字塔；我们的目标是获得最高分辨率的注意力图上，$(QK)V$ 的结果。首先我们生成最高分辨率特征层上的 $QKV$，然后通过平均池化或者
- Q6 论文中的实验是如何设计的？
- 论文在使用交叉注意力（特征匹配、立体匹配任务），自注意力（图像分类、目标检测）上的任务上进行了实验；在相同FLops下，取得了最好的效果。（后续论文中，基于CosFormer的VVT和QuadTree的效果基本类似。其中QuadTree的复杂度不完全为 $O(nd^2)$ ，而VVT有着非常恐怖的常数项。因此在图像分辨率继续增高时，VVT的效果会略好。）
- 对于两种QuadTree分别进行了实验。QuadTree-B 的精度略高，并且Flops几乎没有增长。
- Q7 用于定量评估的数据集是什么？代码有没有开源？
- ImageNet、COCO。代码已开源。
- Q8 论文中的实验及结果有没有很好地支持需要验证的科学假设？
- 是的。在模型参数量、Flops与过去工作相近时，模型的精度得到了较高幅度的提升。
- Q9 这篇论文到底有什么贡献？
- 首个使用数据结构处理Attention机制，试图降低其复杂度的工作。在多个benchmark上取得了不错的效果，并起到了Attention加速的效果。
- Q10 下一步呢？有什么工作可以继续深入？
- 第一，这个数据结构的复杂度其实仍为 $O(n^2d)$ ，只是带有一个较小的常数项。能否变成严格的 $O(nd\log n)$ ？我认为将其变为严格的 $\log n$ 是十分有必要的，这代表可以处理更加高分辨率的图像、甚至是视频。
- 第二，这里的超参数设置是根据不同任务进行调参的。能否将其变成一种可学习的参数，类似于Deformable Attention那样？这样就可以在比较重要的特征层，选取更多的patch进行递归。这么做会导致实现起来更加困难吗？
0 Abstract
引入四叉树注意力机制（QuadTree Attention），对原有PVT加入改进：在每层中，只选取注意力分数最高的 $K$ 个块，在下一层中只在这最相关的 $K$ 个块中计算注意力分数。
在包括分类、检测、分割在内的多种任务中取得了不错的效果。
1 Introduction
先插入一个想法：DenseNet 的连接方式是将之前的特征图和当前特征图 Concat。这种Concat的结构能否在Transformer中利用起来？
过去的工作中：
- 线性近似的Transformer在视觉任务中表现地不好；
- PVT使用了下采用的 $K$ 和 $V$，对像素级别的信息有损失；
- Swin使用了窗口注意力机制，对Transformer的长距离信息有所损害；
本文设计了一种同时抓住局部细节和长距离依赖的高效Transformer：
- 构建了token金字塔，并以从粗到细的方式计算注意力。
- 如果两个精细级别的token所对应的粗粒token区域没有相关性，则可快速跳过它们。
2 Method
- 借用了四叉树的思想：递归地将二维空间细分为四个象限。
- 为了构建特征金字塔，对 $Q,K,V$ 进行下采样：
- $Q,K$ 使用平均池化层；
- 对于使用交叉注意力的任务，$V$ 使用平均池化；对于使用自注意力的任务，$V$ 使用步长为 $2$ 的卷积层。
- 每一层只计算 $K$ 个块的Attention，复杂度 $O(NKd)$
2.1 QuadTree-A
我们想要求的是最精细层的Attention map。用它的第 $i$ 个 query $q_i$ 为例，我们需要计算从其他所有的 key 中获得的信息。假设一共有 $l$ 层，层的编号越小，即在token金字塔的越顶层、Attention map越稀疏。总的信息可以表示为：
$$m_i = \sum_{1\le l \le L}m_i^l = \sum_{1\le l \le L} \sum_{j \in \Omega_i^{l}} s_{ij}^l v_j^l$$
- 其中 $m_i^l$ 表示第 $l$ 层计算的局部信息；
- $\Omega_i^l = \Gamma_i^l – \Gamma_i^{l+1}$ ，其中 $\Gamma_i^l$ 对应于 $l-1$ 层的 top-$K$ token，$\Gamma_i^1$ 覆盖整个图像。（即 $\Omega_{i}$ 表示这一层中，非 top-$K$ 相关的区域）
- $s_{ij}^l$ 表示第 $l$ 层中 $q_i$ 和 $k_j$ 的注意力分数。它使用递归的方式进行计算：$s_{ij}^l = s_{ij}^{l-1}t_{ij}^l$ ，其中 $t_{ij}$ 为这个粗粒度层中，$i,j$ 所属的大块的 Attention score。
- 如果 $j$ 属于的大块不在 $i$ 所在大块的 top-$K$ ，则递归结束，直接使用大块的Attention Score。否则，继续递归下去。
2.2 QuadTree-B
$$m_i = \sum_{1\le l \le L}w_i^l m_i^l$$
其中 $w_i^l$ 为可学习参数，表示这一层Attention Score的加权贡献。