0 引言

条件随机场（Conditional Random Field，CRF）是给定一组输入随机变量条件下另一组输出变量的条件概率分布模型，其特点是输出随机变量构成了马尔可夫随机场。

1 概率无向图模型

引言：概率无向图模型，又称为马尔可夫随机场，是一个可以由无向图
表示的联合概率分布。

1.1 定义

设有联合概率分布 $P(Y)$ , 由无向图 $G=(V,E)$ 表示，在图G中，结点表示随机变量，边表示随机变量之间的依赖关系。 如果联合概率分布 $P(Y)$ 满足成对、局部或全局马尔可夫性，就称此联合概率分布为概率无向图模型，或马尔可夫随机场（Markov Random Field）。

• 成对马尔可夫性：
• 局部马尔可夫性：
• 全局马尔可夫性：

1.2 概率无线图模型的因子分解

1.2.1 团与最大团

1.2.2 因子分解

2 条件随机场的定义与形式

2.1 条件随机场的定义

2.1.1 整体架构

• 条件随机场是给定随机变量 $X$ 条件下，随机变量 $Y$ 的马尔可夫随机场。
• 线性链条件随机场可用于标注问题。这时，在条件概率模型 $P(Y|X)$ 中，$Y$ 是输出变量，表示标记序列，$X$ 是输入变量，表示需要标注的观测序列，也把标记序列称为状态序列。
• 学习时，利用训练数据集通过极大似然估计或正则化的极大似然估计得到条件概率模型 $P\hat (Y|X)$ 。
• 预测时，对于给定的输入序列 $x$，求出条件概率 $P\hat(y|x)$ 最大的输出序列 $\hat{y} $

2.1.2 条件随机场的定义

2.1.3 线性链条件随机场的定义

2.2 条件随机场的参数化形式

2.3 条件随机场的简化形式

2.4 条件随机场的矩阵形式

1. 隐马尔可夫模型的基本概念

1.1 定义

隐马尔可夫模型是关于时序的概率模型，描述由一个隐藏的马尔可夫链随机生成不可观测的状态随机序列，再由各个状态生成一个观测从而产生观测随机序列的过程。

• 马尔可夫链：隐藏的马尔可夫链随机生成的状态的序列
• 每个状态生成一个观测，而由此产生的观测的随机序列，称为观测序列

1.2 三要素

隐马尔可夫模型由初始状态概率向量 $\pi$ 、状态转移概率矩阵 $A$ 和 观测概率矩阵 $B$ 决定。 $ \pi $ 和 $A$ 决定状态序列，$B$ 决定观测序列。

1.3 两个基本假设

• 齐次马尔可夫性假设：假设隐藏的马尔可夫链在任意时刻 $t$ 的状态只依赖于其前一时刻的状态，与其他时刻的状态集观测无关，也与时刻 $t$ 无关
• 观测独立性假设：假设任意时刻的观测只依赖于该时刻的马尔可夫链的状态，与其他观测及状态无关

1.4 隐马尔可夫模型的3个基本问题

• 概率计算问题。 给定模型 $\lambda=(A,B,\pi)$ 和观测序列$O=(o_1, o_2, … , o_T)$ ，计算在模型 $\lambda$ 下观测序列 $O$ 出现的概率 $P(O|\lambda)$
• 学习问题。已知观测序列 $O=(o_1, o_2, … , o_T)$ ，估计模型 $ \lambda = (A, B, \pi)$ 参数，使得在该模型下观测序列概率 $P(O|\lambda)$ 最大。即用最大似然估计的方法估计参数。
• 预测问题，也称为解码问题。已知模型 $\lambda=(A,B,\pi) $ 和观测序列$O=(o_1, o_2, … , o_T)$ ，求对给定观测序列条件概率 $P(I|O)$ 最大的状态序列 $I=(i_1, i_2, …, i_T)$ 。即给定观测序列，求最有可能的对应的状态序列。

2. 概率计算算法

2.1 直接计算法

给定模型 $\lambda=(A,B,\pi)$ 和观测序列 $O=(o_1, o_2, … , o_T)$ ，计算在模型 $\lambda$ 下观测序列 $O$ 出现的概率 $P(O|\lambda)$

通过列举所以可能的长度为 $T$ 的状态序列 $I=(i_1, i_2, …, i_T)$， 求各个状态序列 $I$ 与观测序列 $O=(o_1, o_2, … , o_T)$ 的联合概率 $ P(O, I | \lambda)$，然后对所有可能的状态序列求和，得到 $P(O|\lambda)$

• 时间复杂度 $O(TN^T)$

2.2 前向算法

• 前向概率：给定隐马尔可夫模型 $\lambda $，定义到时刻 $t$ 部分观测序列为 $o_1, o_2, … , o_t $ 且状态为 $q_i$ 的概率为前向概率，记作

  $$\alpha_t(i) = P( o_1, o_2, ... , o_t , i_t = q_i | \lambda)$$

• 结合动态规划递推求解 $ \alpha_t(i) $ 即观测序列概率 $P(O|\lambda)$

• 时间复杂度 $O(TN^2)$

2.3 后向算法

• 后向概率：给定隐马尔可夫模型 $\lambda $，定义在时刻 $t$ 状态为 $qi$ 的条件下，从 $t+1$ 到 $T$ 的部分观测序列为 $o{t+1}, o_{t+2}, … , o_T $ 的概率为后向概率，记作

  $$\beta_t(i) = P( o_{t+1}, o_{t+2}, ... , o_T, i_t = q_i | \lambda)$$

• 结合动态规划递推求解 $ \beta_t(i) $ 即观测序列概率 $P(O|\lambda)$

• 时间复杂度 $O(TN^2)$

3. 学习算法

3.1 监督学习方法

状态数据和观测序列都存在的训练数据，利用极大似然估计发来估计隐马尔可夫模型的参数

• 转移概率
• 观测概率
• 初始状态概率

3.2 Baum-Welch算法

Todo

4. 预测算法

4.1 近似算法

贪心思想，在每个时刻 $t$ 选择该时刻最有可能出现的状态，优点是计算简单，缺点是不能保证预测的状态序列整体是最优可能的状态序列。

4.2 维特比算法

用动态规划求概率最大路径（最优路径），这时一条路径对应着一个状态序列。

下一步规划：补充EM算法，CRF

1.并查集概念

并查集，在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。

2. 实现方法

2.1 API

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class UF:
    def __init__(self):
        self.parents = []
        self.ranks = []
        pass

    def find(self, x):
        pass

    def is_connected(self, x, y):
        pass

    def union(self, x, y):
        pass

2.2 具体实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class UF:
    def __init__(self):
        self.parents = []
        self.ranks = []

    def find(self, x):
        # 尾递归
        if x != self.parents[x]:
            self.parents[x] = self.find(self.parents[x])
        return self.parents[x]

    def is_connected(self, x, y):
        return self.find(x) == self.find(y)

    def union(self, x, y):
        parent_x = self.find(x)
        parent_y = self.find(y)

        # 加入ranks 防止树过高
        rank_x = self.ranks[parent_x]
        rank_y = self.ranks[parent_y]

        if rank_x == rank_y:
            self.parents[parent_y] = parent_x
            self.ranks[parent_x] += 1
        elif rank_x > rank_y:
            self.parents[parent_y] = parent_x
        else:
            self.parents[parent_x] = parent_y

2.3 Todo

0. 引言

Todo

1. word2vec

Todo

2. glove

Todo

3. elmo

Todo

4. gpt

Todo

5. gpt2

Todo

6. bert

Todo

7. roberta

7.1 静态Masking vs 动态Masking

• 静态Masking：Bert对每一个序列随机选择15%的Tokens替换成[MASK]，为了消除与下游任务的不匹配，还对这15%的Tokens进行（1）80%的时间替换成[MASK]；（2）10%的时间不变；（3）10%的时间替换成其他词。但整个训练过程，这15%的Tokens一旦被选择就不再改变，也就是说从一开始随机选择了这15%的Tokens，之后的N个epoch里都不再改变了。
• 动态Masking：RoBERTa一开始把预训练的数据复制10份，每一份都随机选择15%的Tokens进行Masking，也就是说，同样的一句话有10种不同的mask方式。然后每份数据都训练N/10个epoch。这就相当于在这N个epoch的训练中，每个序列的被mask的tokens是会变化的。

7.2 with NSP vs without NSP

原本的Bert为了捕捉句子之间的关系，使用了NSP任务进行预训练，就是输入一对句子A和B，判断这两个句子是否是连续的。在训练的数据中，50%的B是A的下一个句子，50%的B是随机抽取的。而RoBERTa去除了NSP，而是每次输入连续的多个句子，直到最大长度512（可以跨文章）。

7.3 更大的mini-batch

原本的BERTbase 的batch size是256，训练1M个steps。RoBERTa的batch size为8k。

7.4 更多的数据，更长时间的训练

RoBERTa用了更多的数据。性能确实再次彪升。当然，也需要配合更长时间的训练。

8. Albert

8.1 对Embedding因式分解

ALBERT采用了一种因式分解的方法来降低参数量。首先把one-hot向量映射到一个低维度的空间，大小为E，然后再映射到一个高维度的空间，说白了就是先经过一个维度很低的 embedding matrix，然后再经过一个高维度matrix把维度变到隐藏层的空间内，从而把参数量从$O(V×H)O(V×H)O(V×H)$降低到了$O(V×E+E×H)O(V×E+E×H)O(V×E+E×H) $，当 $E<<H$时参数量减少的很明显。

8.2 跨层的参数共享（Cross-layer parameter sharing）

全连接层与attention层都进行参数共享，也就是说共享encoder内的所有参数，同样量级下的Transformer采用该方案后实际上效果是有下降的，但是参数量减少了很多，训练速度也提升了很多。

8.3 句间连贯（Inter-sentence coherence loss）

在ALBERT中，为了只保留一致性任务去除主题识别的影响，提出了一个新的任务 sentence-order prediction（SOP），SOP的正样本和NSP的获取方式是一样的，负样本把正样本的顺序反转即可。SOP因为实在同一个文档中选的，其只关注句子的顺序并没有主题方面的影响。并且SOP能解决NSP的任务，但是NSP并不能解决SOP的任务，该任务的添加给最终的结果提升了一个点。

8.4 移除dropout

ALBERT在训练了100w步之后，模型依旧没有过拟合，于是乎作者果断移除了dropout，没想到对下游任务的效果竟然有一定的提升。这也是业界第一次发现dropout对大规模的预训练模型会造成负面影响。

9. DistillBert

Todo

10. xlnet

• 自回归 vs 自编码，通过全排列及mask实现

• Bert输入存在mask噪声，输出条件独立，缺乏生成能力

• 双流Attention，自己预测自己，自己又不能看见自己

参考

• 改进版的RoBERTa到底改进了什么？
• 一文揭开ALBERT的神秘面纱

速记

稳定性记忆方法：高复杂度（ $O(n^2)$ ）选择排序是例外，低复杂度（ $O(nlogn)$ ）归并排序是例外。

选择排序不稳定举例：(7) 2 5 9 3 4 [7] 1…当我们利用直接选择排序算法进行排序时候,(7)和1调换,(7)就跑到了[7]的后面了,原来的次序改变了,这样就不稳定了.

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

def quick_sort(array, start, end):
    """快速排序"""
    if start >= end:  
        return
    mid = array[start]  
    low = start  
    high = end 
    while low < high:
        while low < high and array[high] >= mid:
            high -= 1
        array[low] = array[high]
        
        while low < high and array[low] < mid:
            low += 1
        array[high] = array[low]

    array[low] = mid  

    quick_sort(alist, start, low - 1)  
    quick_sort(alist, low + 1, end)  

# Test
array = [54, 26, 93, 17, 77, 31, 44, 55, 20]
quick_sort(array, 0, len(array) - 1)          # 闭区间 [0, len(array) -1]
print(array)

归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

def merge_sort(array):
    if len(array) == 1:
        return array
    mid = len(array) // 2
    left_array = merge_sort(array[:mid])
    right_array = merge_sort(array[mid:])
    
    return merge(left_array, right_array)
    

def merge(left_array, right_array):
    array = []
    i = 0
    j = 0
    while i < len(left_array) and j < len(right_array):
        if left_array[i] <= right_array[j]:
            array.append(left_array[i])
            i += 1
        else:
            array.append(right_array[j])
            j += 1
    while i < len(left_array):
        array.append(left_array[i])
        i += 1
    while j < len(right_array):
        array.append(right_array[j])
        j += 1
    
    return array


# Test
array = [54, 26, 93, 17, 77, 31, 44, 55, 20]
array = merge_sort(array)          
print(array)

topK问题

暴力解法

最基本的思路，将N个数进行完全排序，从中选出排在前K的元素即为所求。有了这个思路，我们可以选择相应的排序算法进行处理，目前来看快速排序，堆排序和归并排序都能达到$O(NlogN)$的时间复杂度。

优先队列

可以采用数据池的思想，选择其中前K个数作为数据池，后面的N-K个数与这K个数进行比较，若小于其中的任何一个数，则进行替换。这种思路的算法复杂度是$O(N*K)$

大根堆

大根堆维护一个大小为K的数组，目前该大根堆中的元素是排名前K的数，其中根是最大的数。此后，每次从原数组中取一个元素与根进行比较，如小于根的元素，则将根元素替换并进行堆调整（下沉），即保证大根堆中的元素仍然是排名前K的数，且根元素仍然最大；否则不予处理，取下一个数组元素继续该过程。该算法的时间复杂度是O(N*logK)，一般来说企业中都采用该策略处理topK问题，因为该算法不需要一次将原数组中的内容全部加载到内存中，而这正是海量数据处理必然会面临的一个关卡。

快速排序

利用快速排序的分划函数找到分划位置K，则其前面的内容即为所求。该算法是一种非常有效的处理方式，时间复杂度是O(N)（证明可以参考算法导论书籍）。对于能一次加载到内存中的数组，该策略非常优秀。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

def topK(array, K):
    left = 0
    right = len(array) - 1
    index = quick_sort(array, left, right)
    while index+1 != K:
        if index+1 < K:
            index = quick_sort(array, index+1, right)
        elif index+1 > K:
            index = quick_sort(array, left, index-1)
    return array[:K]

def quick_sort(array, left, right):
    # print(left, right)
    mid = array[left]
    while left < right:
        while left < right and array[right] < mid:
            right -= 1
        array[left] = array[right]
        while left < right and array[left] >= mid:
            left += 1
        array[right] = array[left]
    array[left] = mid
    return left


# Test
array = [54, 26, 93, 17, 77, 31, 44, 55, 20]
array = topK(array, K=8)          
print(array)

参考

1. topK算法问题
2. 海量数据处理 - 10亿个数中找出最大的10000个数（top K问题）
3. 十大排序python实现

引子

• 问题：流式数据（Streaming Data），数据长度为n但不知道，如何从中等概率随机选择一个数据？
  
• 解法：我们以概率1选择第一个数据，以1/2的概率选择第二个数据，以此类推，以1/m的概率选择第m个对象（如果后面某一数据一旦选中，替换掉以前选中的数据）。当所有数据流过时，每个对象具有相同的被选中的概率1/n。
  
• 证明：$P_m = \frac{1}{m} \cdot \frac{m}{m+1} \cdot \frac{m+1}{m+2} \cdot *** \cdot \frac{n-2}{n-1} \cdot \frac{n-1}{n} = \frac{1}{n}$

• Python代码

  1 2 3 4 5 6 7 8

  import random def sample(n): res = 1 for i in range(1, n+1): num = random.randint(1, i): if i == num: res = i return res

蓄水池抽样

• 问题：流式数据（Streaming Data），数据长度为n但不知道，如何从中等概率随机选择k（k < n）个数据？
• 解法：先选中前k个数据（当作一个蓄水池），然后以k/(k+1)的概率选择第k+1个数据，以k/(k+2)的概率选择第k+2个数据，以此类推以k/m的概率选择第m个数据，一旦后面有某个数据被选中，则随机替换蓄水池中的一个数据。最终每个数据被选中的概率均为k/n。
• 证明： $$\begin{align} P_m &= \frac{k}{m} (\frac{m+1-k}{m+1} +\frac{k}{m+1} \frac{k-1}{k}) (\frac{m+2-k}{m+2} +\frac{k}{m+2}\frac{k-1}{k}) ...(\frac{n-k}{n} +\frac{k}{n}\frac{k-1}{k}) \\ &= \frac{k}{n} \end{align}$$
• Python代码

1
2
3
4
5
6
7
8
9
10

import random
def sample(n, k):
    res = [0] * k
    for i range(k):
        res[i] = i+1
    for i range(k, n):
        num = random.randint(0, i)
        if num < k:
            res[num]  = i+1
    return res

参考

• 蓄水池抽样
• 蓄水池抽样算法(Reservoir Sampling)

阿里小蜜部门1-简历评估面试 35min 已凉

1. 自我介绍
2. 介绍项目
3. Bert层数那么高为啥还能收敛？
4. 文本匹配的方法可以分为哪几类？各自优缺点
5. 介绍TextCNN
6. 介绍LSTM
7. 梯度消失的解决方法
8. 最大熵

阿里小蜜部门2-1面 1h

1. 自我介绍
2. 算法题 leetcode: twoSum，数据量很大，hash表算法
3. 介绍项目
4. 如BERT模型的准确率到了瓶颈，怎么解决？

Todo

背景

由于下层的Layer的参数发生改变，导致上层的输入的分布发生改变，最后深度神经网络难以训练。（注意：底层为最下层）

• Internal Covariate Shift (内部协变量偏移): 在深层网络训练的过程中，由于网络中参数变化而引起内部结点数据分布发生变化的这一过程
• Internal Covariate Shift 带来的问题
  • 上层网络需要不停调整来适应输入数据分布的变化，导致网络学习速度的降低
  • 网络的训练过程容易陷入梯度饱和区，减缓网络收敛速度

Batch Normalization

• 算法流程图
  
  
  ($\epsilon$是为了增加训练稳定性而加入的小的常量数据)

• 测试阶段如何使用Batch Normalization？

  • BN在每一层计算的$\mu$与$\sigma^2$都是基于当前batch中的训练数据，但是这就带来了一个问题：在预测阶段，有可能只需要预测一个样本或很少的样本，没有像训练样本中那么多的数据，此时$\mu$与$\sigma^2$的计算一定是有偏估计，这个时候该如何进行计算？
  • 利用BN训练好模型后，我们保留了每组mini-batch训练数据在网络中每一层的$\mu{batch}$与$\sigma^2{batch}$。此时我们使用整个样本的统计量来对Test数据进行归一化，具体来说使用均值与方差的无偏估计： $$\mu_{test} = E(\mu_{batch})$$ $$\sigma^2_{test} = \frac{m}{m-1}E(\sigma^2_{batch})$$
  • 得到每个特征的均值与方差的无偏估计后，我们对test数据采用同样的normalization方法： $$BN(x_{test}) = \gamma \frac{X_{test} - \mu_{test}}{\sqrt{\sigma^2_{test} + \epsilon}} + \beta$$

• batch_normalization做了normalization后为什么要变回来？即 scale and shift
  
  如果只做normalize在某些情况下会出现问题，比如对象是Sigmoid函数的output，而且output是分布在Sigmoid函数的两侧，normalize会强制把output分布在Sigmoid函数的中间的非饱和区域，这样会导致这层网络所学习到的特征分布被normalize破坏。而上面算法的最后一步，scale and shift可以令零均值单位方差的分布（normalize之后的分布）通过调节$\gamma$和$\beta$变成任意更好的分布（对于喂给下一层网络来说）。因为这个$\gamma$和$\beta$是在训练过程中可以学习得到参数。

BN的优势

• BN使得网络中每层输入数据的分布相对稳定，加速模型学习速度
• BN允许网络使用饱和性激活函数（例如sigmoid，tanh等），缓解梯度消失问题
• BN使得模型对网络中的参数不那么敏感，简化调参过程，使得网络学习更加稳定
• BN具有一定的正则化效果
  
  在Batch Normalization中，由于我们使用mini-batch的均值与方差作为对整体训练样本均值与方差的估计，尽管每一个batch中的数据都是从总体样本中抽样得到，但不同mini-batch的均值与方差会有所不同，这就为网络的学习过程中增加了随机噪音，与Dropout通过关闭神经元给网络训练带来噪音类似，在一定程度上对模型起到了正则化的效果。

BN的缺陷

• 不适用于mini-batch非常小的训练环境
• 不适用于RNN，因为它是一个动态的网络结构，同一个batch中训练实例有长有短，导致每一个时间步长必须维持各自的统计量，这使得BN并不能正确的使用。

参考

• Batch Normalization原理与实战
• 深度学习中 Batch Normalization为什么效果好？
• 请问batch_normalization做了normalization后为什么要变回来？