ARTS - week 6

Algorithm

题目链接

https://leetcode-cn.com/problems/recover-a-tree-from-preorder-traversal/

我们从二叉树的根节点 root 开始进行深度优先搜索。

在遍历中的每个节点处，我们输出 D 条短划线（其中 D 是该节点的深度），然后输出该节点的值。（如果节点的深度为 D，则其直接子节点的深度为 D + 1。根节点的深度为 0）。

如果节点只有一个子节点，那么保证该子节点为左子节点。

给出遍历输出 S，还原树并返回其根节点 root。

题目分析

通过栈来保存节点信息和深度信息，找到第一个比自己 level 小的节点，就是父节点，其他的点可以 pop 出去，因为是按照先序遍历来进行的，则找到该节点的时候，其他节点均位于另一颗子树上面。代码如下所示

代码实现

/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode() : val(0), left(nullptr), right(nullptr) {} *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public:    TreeNode* recoverFromPreorder(string S) {        stack<pair<TreeNode*, int>> node_stack;        int value = 0;        int pos = 0;        int level = 0;        while(pos < S.size()){            level = 0;            while(pos < S.size() && S[pos] == '-'){                pos++;                level++;            }            value = 0;            while(pos < S.size() && isdigit(S[pos])){                value = 10 * value + (S[pos] - '0');                 pos++;            }            TreeNode* node = new TreeNode(value);            if(node_stack.size() > 0 && node_stack.top().second < level){                node_stack.top().first->left = node;            }            else if(node_stack.size() > 0){                while(node_stack.size() > 0 && node_stack.top().second >= level){                    node_stack.pop();                }                node_stack.top().first->right = node;            }            node_stack.emplace(node, level);        }        while(node_stack.size() > 1){            node_stack.pop();        }        return node_stack.top().first;    }}; 



Review

继续 review 上周的 transformer 介绍文章，上一篇地址https://xie.infoq.cn/article/01dad5e404dfd7d74b683d9b8， 原文地址 http://jalammar.github.io/illustrated-transformer/， 上一篇我们介绍了 encoder 的核心环节，self attention, 这一篇着重介绍 decoder 部分

encoder 剩余部分

下图将 encoder 整个流程进行了概括，包括了 self-attention 机制（Z_0, Z_1)等均为 self-attention 的 output, 同时也概括了 multi-headed attention 的用法，生成 8 个 head, 然后 concat 到一起，通过一个 W_o 获得最终输出。

作者选用 multi-headed 的方法，认为该方法有两个优势

1. 可以让模型关注不同的位置

2. 有更多的表达空间

（本文作者注：当然，缺点也很明显，就是更大的计算量，不知道作者有没有尝试，z_0,...z7,合并到一个 channel 里面，看下效果是否相同，从而验证这个结论）

还有一个信息没有考虑到，就是 words 之间的位置关系 ，同样的 word, 不同的顺序“我想打 bob”，“bob 想打我”是意思不一样的话，在 NLP 任务中，位置信息不可忽视，如何整合位置信息的呢？

是将 word embedding 和 time series 信息进行合并，因此整个流程如下图所示

decoder

decoder 部分分为 self attention 输入和 encoder-decoder attention 输入

self attention 是利用 output 的已有时序数据输入， encoder-decoder attention 输入来源有两部分， Q 的来源是 bottom 层的输出，K，V 的来源则是对应层的 decoder,如下图所示。（K，V， Q 是我在原图打的补丁，影响美观，但是更加清晰了）

关于如何进行训练，主要是将目标和输出放到一个分布上面，然后计算 cross entropy 或者 kl 散度

关于 NLP 的 transformer 介绍到这里，下周介绍关于视觉的 transformer

Tips

想要远程 windows 桌面的时候，但是公网地址不确定，可以采用 frp 方法进行端口映射，并且将 windows 里面 frpc 设置为自启动，就可以通过腾讯云等公有云的虚拟机进行转接。

下载地址 https://github.com/fatedier/frp/releases

腾讯云配置 frps, 并且设置自启动

本地电脑配置 frpc,并设置自启动

Share

本周分享的观点是：在网络特征提取方面，很多用到了 affine transform, 作为变形方法，更简单的则是双线性插值，但是实际上，TPS 方法能够找到更精确的点，可以预期获得更好的提升。mask rcnn 的 roi aline 模式胜在速度和精度的均衡，但是如果真的追求超高精度，并且对速度要求不高，可以尝试下 tps 方法。推荐一篇论文 a direct method for modeling non-rigid motion with thin plate spline