最长数对链

646. 最长数对链

给出 n 个数对。 在每一个数对中,第一个数字总是比第二个数字小。

现在,我们定义一种跟随关系,当且仅当 b < c 时,数对(c, d) 才可以跟在 (a, b) 后面。我们用这种形式来构造一个数对链。

给定一个对数集合,找出能够形成的最长数对链的长度。你不需要用到所有的数对,你可以以任何顺序选择其中的一些数对来构造。

示例 :

输入: [[1,2], [2,3], [3,4]]
输出: 2
解释: 最长的数对链是 [1,2] -> [3,4]
注意:

给出数对的个数在 [1, 1000] 范围内。
import java.util.*;

public class Sixhundred_fortySix {
    public int findLongestChain(int[][] pairs) {
        if (pairs == null || pairs.length == 0 || pairs[0].length == 0)
            return 0;
        Arrays.sort(pairs, new Comparator<int[]>() {
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        });
        int ans = 1;
        int temp = pairs[0][1];
        for (int i = 1; i < pairs.length; i++) {
            if (pairs[i][0] > temp) {
                ans += 1;
                temp = pairs[i][1];
            }
        }
        return ans;
    }
}

 

learning rate和batch size

一. learning rate

  • 学习率如果过大,可能会使损失函数直接越过全局最优点,此时表现为loss过大或者为nan
  • 学习率如果过小,损失函数的变化速度很慢,会大大增加网络的收敛复杂度,并且很容易被困在局部最小值或者鞍点(目标函数在此点上的梯度(一阶导数)值为 0, 但从该点出发的一个方向是函数的极大值点,而在另一个方向是函数的极小值点)

二. batch size

  • 大的batchsize, 需要的batch数目减少了,所以可以减少训练时间,
  • 大的batch size梯度的计算更加稳定,因为模型训练曲线会更加平滑。
  • 大的batch size导致模型泛化能力下降。
    • 大的batch size性能下降是因为训练时间不够长,本质上并不少batch size的问题,在同样的epochs下的参数更新变少了,因此需要更长的迭代次数。
    • 大的batch size收敛到sharp minimum,而小的batch size收敛到flat minimum,后者具有更好的泛化能力。

三. learning rate和batch size的关系

  1. 常用:通常当我们增加batchsize为原来的N倍时,要保证经过同样的样本后更新的权重相等,按照线性缩放规则,学习率应该增加为原来的N倍。
  2. 不常用:如果要保证权重的方差不变,则学习率应该增加为原来的sqrt(N)倍

关于增大batch size对于梯度估计准确度的影响,分析如下:假设batch size为m,对于一个mini batch,loss为:, 梯度为:

整个minibatch的梯度方差为:

由于每个样本是随机从训练样本集sample得到的,满足i.i.d.假设,因此样本梯度的方差相等,等价于SGD的梯度方差,可以看到batch size增大m倍,相当于将梯度的方差减少m倍,因此梯度更加准确。

如果要保持方差和原来SGD一样,相当于给定了这么大的方差带宽容量,那么就可以增大lr,充分利用这个方差容量,在上式中添加lr,同时利用方差的变化公式,得到等式

因此可将lr增加sqrt(m)倍,以提高训练速度,这也是在linear scaling rule之前很多人常用的增大lr的方式。

四.参考

命名实体抽取的challenges

  • 模型层面:
  • 数据层面:
    • 有监督学习依赖于高成本的人工标注数据
  • 优化层面:
    • 与分类任务不同,信息抽取任务的类别分布有显著差异:正例样本远远少于负例样本;错误和歧义通常集中于某几个特定的类别对之间

  • 中英文差异
    • 分词的规范:中文因其自身语言特性的局限,字(词)的界限往往很模糊,关于字(词)的抽象定义和词边界的划定尚没有一个公认的、权威的标准。
    • 歧义词切分:中文中的歧义词是很普遍,即同一个词有多种切分方式
    • 未登录词(新词)识别:未登录词又称新词。这类词通常指两个方面,一是词库中没有收录的词,二是训练语料没有出现过的词。

中文分詞的難點有哪些?

[论文笔记][2017NIPS]Attention Is All You Need

一、Introduction

RNN结构限制了训练的并行,尤其在序列很长的情况下,无法并行训练会导致内存无法装载太大的batch。

二、Model Architecture

 

Encoder: 一共6层,每层有两个子层:multi-head self-attention和position-wise fully connected feed-forward network(包含residual connection和layer normalization)

Decoder:一共6层,每层有三个子层:multi-head self-attention、encoder-decoder attention(也叫context-attention)和position-wise fully connected feed-forward network

  • Scaled Dot-Product Attention:

  • Multi-Head Attention:

  • Applications of Attention in our Model:(三种)

  • Position-wise Feed-Forward Networks:

  • Positional Encoding:

绝对编码:偶数位置,使用正弦编码,在奇数位置,使用余弦编码

相对编码:对于词汇之间的位置偏移 k, [公式] 可以表示成 [公式] 和 [公式]组合的形式

 

三、Refs

paper/zhihu1/zhihu2