ARTS- Week 7

Algorithm

题目链接

https://leetcode-cn.com/problems/redundant-connection/

在本问题中, 树指的是一个连通且无环的无向图。

输入一个图，该图由一个有着 N 个节点 (节点值不重复 1, 2, ..., N) 的树及一条附加的边构成。附加的边的两个顶点包含在 1 到 N 中间，这条附加的边不属于树中已存在的边。

结果图是一个以边组成的二维数组。每一个边的元素是一对[u, v] ，满足 u < v，表示连接顶点 u 和 v 的无向图的边。

返回一条可以删去的边，使得结果图是一个有着 N 个节点的树。如果有多个答案，则返回二维数组中最后出现的边。答案边 [u, v] 应满足相同的格式 u < v。

题目分析

通过并查集可以进行解决，主要思路如下，首先有一个判断，多余的一条边一定是没有添加额外联通域信息的边，即不走这条边，其他节点能够连接在一起。

在连通域问题上，该问题表现为，通过合并这条边上两个节点，count 数目没有减少，就是对应冗余的边。

代码实现

class Solution {public:    vector<int> findRedundantConnection(vector<vector<int>>& edges) {        int N = edges.size();        vector<int> parent_idx(N);        vector<int> d_size(N, 1);
        for(int i = 0; i < N; i++){            parent_idx[i] = i;        }
        int count = N;        vector<int> result;        if(N == 0){            return result;        }        for(auto edge: edges){            // printf("%d %d\n", edge[0], edge[1]);            int p = find(parent_idx, edge[0]-1);            int q = find(parent_idx, edge[1]-1);            if(p == q){                result.push_back(edge[0]);                result.push_back(edge[1]);                return result;            }            if(d_size[p] > d_size[q]){                parent_idx[q] = p;                d_size[p] += d_size[q];            }            else{                parent_idx[p] = q;                d_size[q] += d_size[p];            }            count--;        }        result.push_back(edges[0][0]);        result.push_back(edges[0][1]);        return result;
    }
    int find(vector<int>& parent_idx, int p){        int root_idx = p;        while(parent_idx[root_idx] != root_idx){            root_idx = parent_idx[root_idx];        }        while(p != root_idx){            int temp = parent_idx[p];            parent_idx[p] = root_idx;            p = temp;        }        return root_idx;    }}; 



Review

按照上周的计划，本周 review 的内容为 transformer 在视觉中的应用 ViT。review 的文章为以下三篇，之所以是三篇，其中一篇是论文本身，另外两篇则是对该论文的讲解。如果对 transformer 不了解，可以参考上周关于 transformer 的介绍 ARTS - week 6 - InfoQ 写作平台。

三篇文章链接分别为 1. 2010.11929.pdf (arxiv.org) 原文 2.https://www.analyticsvidhya.com/blog/2021/03/an-image-is-worth-16x16-words-transformers-for-image-recognition-at-scale-vision-transformers/ 形象画的解释 3. “An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale” Paper Summary & Analysis | by Cornell Data Science | Nerd For Tech | Mar, 2021 | Medium （算法人员拆解的基本方法）

什么问题？

论文的名称是“An Image is Worth 16*16 Words, Transformers for Image Recognition at Scale”, 本论文是在图像分类的任务中，替代 CNN 的一次尝试，取得的效果也非常乐观。之前的论文要么还是需要 CNN 作为特征提取器，要么就是无法大规模扩展（at scale) (Note: 虽然本文也尝试了结合 CNN 作为 embedding 的工具，但是是作为一个实验分析进行的，根本方法还是没有使用 CNN，因此非常值得一读)

使用方法？

1. 将图片切分为 N*N 的区域，如下图所示切分为 3*3，共计 9 个 patch. ViT 中 Patches 就当做是 NLP 任务中的 words

2. 通过 linear projection 将 patch 转换为 patch embedding;

3. 将 patch 的位置信息和第二步的 patch embedding 合并；（VIT 作者尝试过 1D 的 位置信息和 2D 的，最终发现 1D 的信息更好，但是觉得这里总还有更好的方式去结合 2D 位置信息）

4. Transformer Encoder 的结构和 Attention all you need 里面介绍的基本一致；（multi head attention, batch norm, res unit, feed forward 结构仍然为 linear)

5. 因为该任务为分类任务，因此不需要 decoder 部分，一个 MLP head 即可完成分类任务

整体使用范式是：先在一个巨大的数据集上面进行 pretrain, 然后在较小数据集上面 fine tune.

效果？

该方法取得很理想的效果，无论是在精度上面还是在计算效率方面，有两张图可以进行说明

上图是对于 dataset 大小和模型精度的比较,横轴为预训练集的大小，纵轴为 image net top 1 精度，BiT 是基于 resnet 的目前 SOTA 的训练方法。在数据集仅有 1.3M 的时候，CNN 架构的方法还是有优势的，但是随着数据集的增大，CNN 方法开始进入瓶颈期，但是 ViT 的方法仍然没有饱和状态，后期该团队应该会对更大规模的训练集进行测试。

第二张图则是对计算量（FLOPs)进行分析，Hybrid 是 VIT 的一个变种，将每个 patch 通过 CNN 来提取特征，作为 patch embedding, 而非上文介绍的 linear projection。（按照直觉，CNN 是模仿生物学的视觉机制，应该能够更好的辅助特征提取，文中多次提到的 inductive bias 应该就是指这种机制），但是在上图中发现，在计算量较小的时候，通过 cnn 提取特征作为 embedding 确实能够取得更好的性能，但是随着计算量的增大，linear projection 的优势开始显现。

后面两篇文章相当于将原文拆开了，有重新组织一下，结合起来读，对文章会有更好的理解。

Tips

上周介绍 frpc 作为远程桌面的启动工具，确实很好用，但是本周就踩到了大坑，希望后面的人不要踩到这里了。

配置云服务器的时候，要开放对应端口进行转接，切记进行配置的时候，通过 ip.cn 查看下接入电脑的 IP，然后只给当前 ip 授权，完成任务后取消授权，千万不要开放 IP 给 all。否则会被黑客扫描到，进入系统，勒索比特币（别问我怎么知道的）

Share

本周分享的观点是：目前有很多机遇 transformer 的论文开始出现，并且取得了不亚于 CNN 的效果, 如 VIT， Swin Transformer, GPT 3。可能 transformer 真的会是统一 CV 和 NLP 任务的神器。做算法的人，建议多读下相关文章，不要被时代抛弃。