RNN梯度消失及其解决办法
月份：2019年5月
Attention
一. 定义
我们有一个query向量，和一段key向量，这里query可以理解为一个包含比较多信息的全局向量，我们利用这个query对所有key向量进行相似度计算，然后softmax归一化得到attention概率权重，最后我们对每个key所对应的权重和value进行加权求和，得到最终的输出向量然后去做分类或者预测等任务。
本质是（带权）特征筛选
在Transformer中，在encoder self-attention中，QKV都来自encoder的上一层输出；在decoder self-attention中, QKV都来自decoder的上一层输出,但注意mask(在 time_step 为 t 的时刻，我们的解码输出应该只能依赖于 t 时刻之前的输出，而不能依赖 t 之后的输出)；在encoder-decoder attention中，Q来自decoder的上一层输出，KV来自encoder的上一层输出。
二. 分类
计算区域
Soft Attention/Global Attention，这是比较常见的Attention方式，对所有key求权重概率，每个key都有一个对应的权重，是一种全局的计算方式。
Local Attention，这种方式其实是以上两种方式的一个折中，对一个窗口区域进行计算。先用Hard方式定位到某个地方，以这个点为中心可以得到一个窗口区域，在这个小区域内用Soft方式来算Attention。
Hard Attention，这种方式是直接精准定位到某个key，其余key就都不管了，相当于这个key的概率是1，其余key的概率全部是0。
三. 相似度计算
点乘，拼接，cos相似度
四. 常见task
- 1）机器翻译：encoder用于对原文建模，decoder用于生成译文，attention用于连接原文和译文，在每一步翻译的时候关注不同的原文信息。
- 2）文本分类：一般是对一段句子进行attention，得到一个句向量去做分类。
- 3）摘要生成：encoder用于对原文建模，decoder用于生成新文本，从形式上和机器翻译都是seq2seq任务，但是从任务特点上看，机器翻译可以具体对齐到某几个词，但这里是由长文本生成短文本，decoder可能需要capture到encoder更多的内容，进行总结。
五.常见问题
- Attention和全连接层的区别
- 全连接的作用的是对一个实体进行从一个特征空间到另一个特征空间的映射，而注意力机制是要对来自同一个特征空间的多个实体进行整合。
- 全连接的权重对应的是一个实体上的每个特征的重要性，而注意力机制的输出结果是各个实体的重要性。
- 全连接的权重一般与位置有关而且是固定的，而注意力机制与位置无关使得权重与输入有关所以是动态的。
- Self-attention(q=k=v) 和 RNN的区别
- RNN长距离依赖需要经过大量的时间步，训练慢，并且有可能因为梯度消失只能建立短距离依赖(RNN对于50个词之前的词顺序就不敏感了，而对于100个词之前的就完全忘了)，self-attention可以直接计算两个远距离信息之间的依赖关系。
- Self-attention并没有解决并行问题，并行问题通过Transformer的positional encoding加入位置信息辅助解决，因为是同时feed进去位置信息。
六. 参考
二叉树路径问题
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树，以及目标和 sum = 22，
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。
package gongel;
public class onehundred_twelve {
/**
* DFS
*/
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null)
return false;
if (root.left == null && root.right == null)
return sum - root.val == 0;
return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
}
}
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
bool hasPathSum(TreeNode *root, int sum) {
if (root == nullptr)
return false;
if (root->left == nullptr && root->right == nullptr)
return sum - root->val == 0;
return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
}
};
给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树，以及目标和 sum = 22，
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
返回:
[
[5,4,11,2],
[5,8,4,5]
]
package gongel;
import java.util.ArrayList;
import java.util.List;
public class Onehundred_thirteen {
/**
* DFS+回溯
*/
private List<List<Integer>> ans = new ArrayList<>();
public void finpath(TreeNode root, int sum, List<Integer> temp) {
if (root != null) {
if (root.left == null && root.right == null && sum == root.val) {//必须在根节点结束
temp.add(root.val);
ans.add(new ArrayList<>(temp));//一定要新建一个List，否则ans中只存在一个temp
temp.remove(temp.size() - 1);
return;
}
temp.add(root.val);
finpath(root.left, sum - root.val, temp);
finpath(root.right, sum - root.val, temp);
temp.remove(temp.size() - 1);//回溯
}
}
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<Integer> temp = new ArrayList<>();
finpath(root, sum, temp);
return ans;
}
}
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
vector<vector<int>> pathSum(TreeNode *root, int sum) {
vector<int> temp;
vector<vector<int>> ans;
helper(root, sum, temp, ans);
}
void helper(TreeNode *root, int sum, vector<int> &temp, vector<vector<int>> &ans) {
if (root == nullptr)
return;
if (root->left == nullptr && root->right == nullptr) {
if (sum == root->val) {
temp.push_back(root->val);
ans.push_back(temp);
temp.pop_back();
}
}
temp.push_back(root->val);
helper(root->left, sum - root->val, temp, ans);
helper(root->right, sum - root->val, temp, ans);
temp.pop_back();
}
};
给定一个非空二叉树，返回其最大路径和。
本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
示例 1:
输入: [1,2,3]
1
/ \
2 3
输出: 6
示例 2:
输入: [-10,9,20,null,null,15,7]
-10
/ \
9 20
/ \
15 7
输出: 42
package gongel;
public class Onehundred_twentyFour {
/**
* 略难！
* 最大路径和：根据当前节点的角色，路径和可分为两步：
* 一：当前节点作为父节点的一个子节点
* 1.只有当前节点
* 2.当前节点+左子树
* 3.当前节点+右子树
* 这三种情况的最大值，第四种情况不可能，因为当前节点+左右子树和父节点就不在一条路径上
*
* 二：以当前节点为根节点
* 1.只有当前节点
* 2.当前节点+左子树
* 3.当前节点+右子树
* 4.当前节点+左右子树
* 这四种情况的最大值即为以当前节点为根的最大路径和
* 此最大值要和已经保存的最大值比较，得到整个树的最大路径值
*/
private int maxValue = Integer.MIN_VALUE;
public int getMaxValue(TreeNode root) {
if (root == null)
return 0;
int leftMax = getMaxValue(root.left);
int rightMax = getMaxValue(root.right);
int max1 = leftMax + root.val;
int max2 = rightMax + root.val;
int max3 = leftMax + rightMax + root.val;
//下面没有与root.val比较是因为maxValue已经初始化root.val，但也可以加上比较
maxValue = Math.max(maxValue, Math.max(max1, Math.max(max2, Math.max(max3, root.val))));
//返回的值不包括“当前节点+左右子树”，否则与父节点断开
return Math.max(root.val, Math.max(max1, max2));
}
public int maxPathSum(TreeNode root) {
if (root == null)
return 0;
//maxValue = root.val;maxValue已经为最小值了，
getMaxValue(root);
return maxValue;
}
}
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
int maxPathSum(TreeNode *root) {
int max_val = INT_MIN;
get_max(root, max_val);
return max_val;
}
int get_max(TreeNode *root, int &max_val) {
if (root == nullptr)
return 0;
int left_max = get_max(root->left, max_val);
int right_max = get_max(root->right, max_val);
int max_one = root->val + left_max;
int max_two = root->val + right_max;
int max_three = root->val + left_max + right_max;
max_val = max(max_val, max(max_one, max(max_two, max(max_three, root->val))));
return max(root->val, max(max_one, max_two));
}
};
给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。
例如，从根到叶子节点路径 1->2->3 代表数字 123。
计算从根到叶子节点生成的所有数字之和。
说明: 叶子节点是指没有子节点的节点。
示例 1:
输入: [1,2,3]
1
/ \
2 3
输出: 25
解释:
从根到叶子节点路径 1->2 代表数字 12.
从根到叶子节点路径 1->3 代表数字 13.
因此，数字总和 = 12 + 13 = 25.
示例 2:
输入: [4,9,0,5,1]
4
/ \
9 0
/ \
5 1
输出: 1026
解释:
从根到叶子节点路径 4->9->5 代表数字 495.
从根到叶子节点路径 4->9->1 代表数字 491.
从根到叶子节点路径 4->0 代表数字 40.
因此，数字总和 = 495 + 491 + 40 = 1026.
法一：不需要回溯所以可以直接算
public class Onehundred_twentyNine {
/**
* dfs
*/
private int ans = 0;
public void helper(TreeNode root, int father) {
if (root != null) {
int current = 10 * father + root.val;
if (root.left == null && root.right == null) {//到达叶子节点
ans += current;
return;
}
helper(root.left, current);
helper(root.right, current);
}
}
public int sumNumbers(TreeNode root) {
helper(root, 0);
return ans;
}
}
法二：利用回溯的方法，但没有回溯
public class Onehundred_twentyNine {
private int ans = 0;
public void dfs(TreeNode root, String path) {
if (root == null)
return;
if (root.left == null && root.right == null) {
String newPth = path + String.valueOf(root.val);
ans += Integer.parseInt(newPth);
return;
}
String newPth = path + String.valueOf(root.val);
dfs(root.left, newPth);
dfs(root.right, newPth);
}
public int sumNumbers(TreeNode root) {
if (root == null)
return 0;
dfs(root, "");
return ans;
}
}
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
int sumNumbers(TreeNode *root) {
int ans = 0;
helper(root, "", ans);
return ans;
}
void helper(TreeNode *root, string path, int &ans) {
if (root == nullptr)
return;
if (root->left == nullptr && root->right == nullptr) {
stringstream ss;
ss << (path + to_string(root->val));
int temp;
ss >> temp;
ans += temp;
}
helper(root->left, path + to_string(root->val), ans);
helper(root->right, path + to_string(root->val), ans);
}
};
给定一个二叉树，返回所有从根节点到叶子节点的路径。 说明: 叶子节点是指没有子节点的节点。 示例: 输入: 1 / \ 2 3 \ 5 输出: ["1->2->5", "1->3"] 解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3
package gongel;
import java.util.ArrayList;
import java.util.List;
public class Twohundred_firtySeven {
/**
* dfs:不用回溯，因为link并没有改变，一般用list必须对回溯，回溯可以返回上一级
*/
private List<String> ans = new ArrayList<>();
public void dfs(TreeNode root, String link) {
if (root != null) {
if (root.left == null && root.right == null) {//到达叶子节点
ans.add(link + root.val);//叶子节点不用+"->"，比首节点更好判断
return;
}
dfs(root.left, link + root.val + "->");//不需要回溯，因为link没有改变
dfs(root.right, link + root.val + "->");
}
}
public List<String> binaryTreePaths(TreeNode root) {
if (root != null)
dfs(root, new String());
return ans;
}
}
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
vector<string> binaryTreePaths(TreeNode *root) {
vector<string> ans;
helper(root, "", ans);
return ans;
}
void helper(TreeNode *root, string path, vector<string> &ans) {
if (root == nullptr)
return;
if (root->left == nullptr && root->right == nullptr) {
ans.push_back(path + to_string(root->val));
return;
}
helper(root->left, path + to_string(root->val) + "->", ans);
helper(root->right, path + to_string(root->val) + "->", ans);
}
};
给定一个二叉树，它的每个结点都存放着一个整数值。
找出路径和等于给定数值的路径总数。
路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。
示例：
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
10
/ \
5 -3
/ \ \
3 2 11
/ \ \
3 -2 1
返回 3。和等于 8 的路径有:
1. 5 -> 3
2. 5 -> 2 -> 1
3. -3 -> 11
package gongel;
public class Fourhundred_thirtySeven {
/**
* 不从根节点出发即树的遍历，不从叶节点结束即不需要判断是否到了叶节点
* 先序遍历（任何遍历都可以）每一个节点，然后每个节点进行dfs
*/
private int ans = 0;
public void dfs(TreeNode root, int sum) {
if (root != null) {
if (sum == root.val) {
ans++;
// return; 不需要return，因为即使出现负值，还会有子节点加上去
}
dfs(root.left, sum - root.val);
dfs(root.right, sum - root.val);
}
}
public int pathSum(TreeNode root, int sum) {
if (root != null) {
dfs(root, sum);
pathSum(root.left, sum);
pathSum(root.right, sum);
}
return ans;
}
}
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
private:
int ans = 0;
public:
int pathSum(TreeNode *root, int sum) {
if (root != nullptr) {
helper(root, sum);
pathSum(root->left, sum);
pathSum(root->right, sum);
}
return ans;
}
void helper(TreeNode *root, int sum) {
if (root == nullptr)
return;
if (sum == root->val)
ans += 1;
helper(root->left, sum - root->val);
helper(root->right, sum - root->val);
}
};
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。
示例 :
给定二叉树
1
/ \
2 3
/ \
4 5
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
注意：两结点之间的路径长度是以它们之间边的数目表示。
package gongel;
public class Fivehundred_fortyThree {
/**
* 和 124题二叉树中的最大路径和 有异曲同工之妙
*/
public int ans = 0;
public int dfs(TreeNode root) {
if (root == null)
return 0;
int left = dfs(root.left);//返回左子树的最大深度
int right = dfs(root.right);//返回右子树的最大深度
ans = Math.max(ans, left + right);//最终结果的最大值
return Math.max(left, right) + 1;//求当前节点的深度（左右子树的高度最大值）
}
public int diameterOfBinaryTree(TreeNode root) {
dfs(root);
return ans;
}
}
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
int diameterOfBinaryTree(TreeNode *root) {
int max_val = 0;
helper(root, max_val);
return max_val;
}
int helper(TreeNode *root, int &max_val) {
if (root == nullptr)
return 0;
int left_max = helper(root->left, max_val);
int right_max = helper(root->right, max_val);
max_val = max(max_val, left_max + right_max);//高度=路径加+1
return max(left_max, right_max) + 1;//高度
}
};
给定一颗根结点为 root 的二叉树，书中的每个结点都有一个从 0 到 25 的值，分别代表字母 'a' 到 'z'：值 0 代表 'a'，值 1 代表 'b'，依此类推。 找出按字典序最小的字符串，该字符串从这棵树的一个叶结点开始，到根结点结束。 （小贴士：字符串中任何较短的前缀在字典序上都是较小的：例如，在字典序上 "ab" 比 "aba" 要小。叶结点是指没有子结点的结点。） 示例 1： 输入：[0,1,2,3,4,3,4] 输出："dba" 示例 2： 输入：[25,1,3,1,3,0,2] 输出："adz" 示例 3： 输入：[2,2,1,null,1,0,null,0] 输出："abc" 提示： 给定树的结点数介于 1 和 8500 之间。 树中的每个结点都有一个介于 0 和 25 之间的值。
法一：回溯
public class Ninehundred_eightyEight {
/**
* dfs+回溯
* 从根节点到叶子节点：逆序插入
* 每次到达叶子结点就与全局ans进行比较更新
*/
private String ans = null;
public void dfs(TreeNode root, StringBuffer sb) {
if (root != null) {
if (root.left == null && root.right == null) {
sb.insert(0, (char) (root.val + 'a'));
if (ans == null || sb.toString().compareTo(ans) < 0) {
ans = sb.toString();
}
sb.deleteCharAt(0);
return;
}
sb.insert(0, (char) (root.val + 'a'));
dfs(root.left, sb);
dfs(root.right, sb);
sb.deleteCharAt(0);
}
}
public String smallestFromLeaf(TreeNode root) {
dfs(root, new StringBuffer());
return ans;
}
}
法二：不回溯，因为path没有改变
public class Ninehundred_eightyEight {
private String ans = null;
public void dfs(TreeNode root, StringBuffer path) {
if (root == null)
return;
if (root.left == null && root.right == null) {
StringBuffer newPath = new StringBuffer(path);
newPath.insert(0, (char) 'a' + root.val);
if (ans == null)
ans = newPath.toString();
if (ans.compareTo(newPath.toString()) > 0)
ans = newPath.toString();
return;
}
StringBuffer newPath = new StringBuffer(path);
newPath.insert(0, (char) 'a' + root.val);
dfs(root.left, newPath);
dfs(root.right, newPath);
}
public String smallestFromLeaf(TreeNode root) {
if (root == null)
return new String();
dfs(root, new StringBuffer());
return ans;
}
}
class Solution {
public:
string smallestFromLeaf(TreeNode *root) {
string ans;
helper(root, "", ans);
return ans;
}
void helper(TreeNode *root, string path, string &ans) {
if (root == nullptr)
return;
if (root->left == nullptr && root->right == nullptr) {
path.insert(0, 1, (char) (root->val + 'a'));
if (ans.empty() || ans > path)
ans = path;
return;
}
path.insert(0, 1, (char) (root->val + 'a'));
helper(root->left, path, ans);
helper(root->right, path, ans);
}
};
LightGBM
一.概述
LightGBM 由微软提出，主要用于解决 GDBT 在海量数据中遇到的问题，以便其可以更好更快地用于工业实践中。对 XGBoost 具有训练速度快、内存占用低的特点
- 单边梯度抽样算法；
- 直方图算法；
- 互斥特征捆绑算法；
- 基于最大深度的 Leaf-wise 的垂直生长算法；
- 类别特征最优分割；
- 特征并行和数据并行；
- 缓存优化。
二. 详述
- 单边梯度抽样算法
- GBDT 算法的梯度大小可以反应样本的权重，梯度越小说明模型拟合的越好，单边梯度抽样算法（Gradient-based One-Side Sampling, GOSS）利用这一信息对样本进行抽样，减少了大量梯度小的样本，在接下来的计算锅中只需关注梯度高的样本，极大的减少了计算量。GOSS 算法保留了梯度大的样本，并对梯度小的样本进行随机抽样，为了不改变样本的数据分布，在计算增益时为梯度小的样本引入一个常数进行平衡。
- 直方图算法
- 直方图算法的基本思想是将连续的特征离散化为 k 个离散特征，同时构造一个宽度为 k 的直方图用于统计信息（含有 k 个 bin）。利用直方图算法我们无需遍历数据，只需要遍历 k 个 bin 即可找到最佳分裂点。
- 直方图加速：通过父节点的直方图与相邻叶节点的直方图相减的方式构建，从而减少了一半的计算量。
- XGBoost 在进行预排序时只考虑非零值进行加速，而 LightGBM 也采用类似策略：只用非零特征构建直方图。
- 互斥特征捆绑算法
- 将一些特征进行融合绑定，则可以降低特征数量。
- 带深度限制的 Leaf-wise 算法
- Level-wise(XGBoost)：基于层进行生长，直到达到停止条件；
- Leaf-wise(LightGBM)：每次分裂增益最大的叶子节点，直到达到停止条件。
- 类别特征最优分割
- LightGBM 原生支持类别特征，采用 many-vs-many 的切分方式将类别特征分为两个子集，实现类别特征的最优切分
三. 参考
Dialogue system papers
ICSL
- 【ACL-2019】A Novel Bi-directional Interrelated Model for Joint Intent Detection and Slot Filling
- 【NAACL-HLT-2018】Slot-Gated Modeling for Joint Slot Filling and Intent Prediction
- 【ACL-2019】Joint Slot Filling and Intent Detection via Capsule Neural Networks
- 【NAACL-18】A Bi-model based RNN Semantic Frame Parsing Model for Intent Detection and Slot Filling
- 【INTERSPEECH-16】Attention-Based Recurrent Neural Network Models for Joint Intent Detection and Slot Filling
- 【IJCAI-16】A Joint Model of Intent Determination and Slot Filling for Spoken Language Understanding
Other
- 【ACL-2019】Deep Unknown Intent Detection with Margin Loss
- 【AAAI-2019】Unsupervised Transfer Learning for Spoken Language Understanding in Intelligent Agents
- 【EMNLP-2018】Zero-shot User Intent Detection via Capsule Neural Networks
- 【CoRR-2017】Multi-Domain Adversarial Learning for Slot Filling in Spoken Language Understanding
- 【INTERSPEECH-2016】Multi-Domain Joint Semantic Frame Parsing using Bi-directional RNN-LSTM
- 【SIGDIAL-2013】Deep Neural Network Approach for the Dialog State Tracking Challenge
- 【EMNLP-15】A Model of Zero-Shot Learning of Spoken Language Understanding