CRF

同朴素贝叶斯一样，HMM是生成式模型。它可以做线性序列预测分析，为了计算复杂度上的可行性，其假设观测变量仅依赖于隐含变量。然而，实际中观测变量之间也存在不可忽略的依赖关系，这导致HMM的假设会严重影响模型的精确性。

CRF现在是自然语言处理领域中多个任务的state-of-art方法，包括分词、词性标注，浅解析（shallow parsing）等。并且在命名实体识别、基因预测、图像标注、物体识别等领域有着重要的应用。

CRF是判别式模型。

概率图模型

一般地，在概率图模型中，节点表示随机变量，边表示依赖关系。概率图模型的表示的前提是对图的划分，也就是因子分解，可以按有向图和无向图分别讨论。

马尔可夫性

给定一个随机变量$y$及其联合概率分布$p(y)$和它的无向图表示$G$，下面给出关于马尔可夫性的三个等价定义。

• 成对马尔可夫性：设$u,v$是无向图中没有连接的两个点，$o$是其他节点，则有$p(u,v|o)=p(u|o)p(v|o)$
• 局部马尔可夫性：设$u$是无向图中任意一个节点，$w$是与$u$有连接的节点，$o$是其他节点，则有$p(v,o|w)=p(v|w)p(o|w)$
• 全局马尔可夫性：设$u,v$是被节点集$o$分隔开的任意节点集合，则有$p(u,v|o)=p(u|o)p(v|o)$

总结一下意思就是：无连接的变量在以中继变量为条件的情况下相互独立。

有向图

定义在有向图上的条件概率模型的联合分布为所有节点条件概率的乘积，比如贝叶斯网络，马尔可夫链等。

无向图

满足马尔可夫性的联合概率分布被称为概率无向图模型，也叫做马尔可夫随机场。定义在无向图上的条件概率模型的联合分布为最大团上非负函数的乘积（这也称为概率无向图模型的因子分解）。这里最大团（极大团）指的是不能再添加节点的团（团指的是两两相交的节点集）。形式化定义单个节点$v$的概率为$v$在所有最大团上的乘积，即

其中$\Psi_c(v_c) \ge 0$称为节点$v$在团$c$上的势函数。$Z$是归一化因子满足$Z=\sum_vp(v)$（其实最大熵模型也可以看成是势函数的乘积）。

CRF的表示

CRF是定义在无向图上的判别式模型，是给定随机变量$x$的条件下，随机变量$y$的马尔可夫随机场。按照无向图上的定义，可以有

这就是CRF的基本形式。下面分别介绍线性链CRF和任意结构的CRF。

线性链CRF

CRF的一种特殊形式，也是比较常用的形式-线性链式。在这种情况下，相邻点变成了最大团，即满足马尔可夫性

假设$x=(x_1,…x_{n+1})$，$y=(y_1,…y_{n+1})$（都是向量），链的长度为$n+1$，所以最大团的数量为$n$，上式就可以写成：

给定势函数$\Psi_j(x,y)$的形式为

其中，$j$表示序列位置（与$n$相关）。所以线性链的CRF可以表示为

其中，$Z_{\lambda}(x)$就是在$y$上对$p_{\lambda}(y|x)$求和的结果，这结构与最大熵的形式类似。

与HMM的模式类似，应用模型之前还需要解决一些问题，分别是

1. 给定序列集合$X$和对应的标注数据$Y$，如何训练CRF模型参数使得$p(Y|X,\mathcal{M})$最大
2. 给定模型$\mathcal{M}$和输入序列$X$，如何求输出序列$Y$

这里就不考虑求$p(X|\mathcal{M})$了，因为CRF是判别式模型。

模型训练

目标是估计参数$\lambda$。给定数据集$T$，参数估计常用的方法就是MLE了，我们再取一个log，考虑regularization，推导如下：

这里$\sigma^2$是控制regularization权重的超参数。上式可分为3部分，分别对$\lambda_k$求导

其结果刚好是训练数据集上特征$f_i$的期望值的$N$（训练集数据个数*(n+1)）倍。

上面倒数第二行第一个求和符号的范围可以退化成$x\in X$，其结果刚好是模型分布上特征$f_i$的期望值的$N$（训练集数据个数*(n+1)）倍。

综上，我们可以得到

继而，令上式等于0，就可以求出$\lambda_k$的值。这里，$\hat{E}(f_k)$可以通过简单的统计特征$f_k$在数据集中的出现的次数实现。而想要直接计算$E(f_k)$就不容易了，因为CRF这里处理的是序列数据，序列组合导致可能性指数上升。

解决方法是利用HMM也用到的前后向算法的修改版。
定义函数$T_j(s)$为状态$s$在输入位置$j$时，位置$j+1$的可能状态集合。定义函数$T_j^{-1}(s)$为$T_j(s)$的反函数，即输出状态$s$的前置集合。定义序列初始状态为$\vdash$，终止状态为$\dashv$。在此基础上定义前向、后向函数：

• 前向函数：$\alpha_j(s|x)=\sum_{s’\in T_j^{-1}(s)}\alpha_{j-1}(s’|x)\cdot \Psi_j(s’,s,x)$，初始化$\alpha_0(\vdash|x)=1$
• 后向函数：$\beta_j(s|x)=\sum_{s’\in T_j(s)}\beta_{j+1}(s’|x)\cdot \Psi_j(s,s’,x)$，初始化$\beta_{|x|+1}(\dashv|x)=1$

其中，与上文的势函数对应，$\Psi_j(s’,s,x)=\exp(\sum_{i=1}^m\lambda_if_j(y_{i-1}=s’,y_i=s,x,j))$。根据前向、后向函数的定义，可以有

因此，$E(f_k)$的计算就变得可行了

其中$S$是状态集合。这相当于计算了所有可能状态序列的可能，$\alpha, \beta$的值只需要计算一次，存储起来就好。前后向算法的时间复杂度为$O(|S|^2n)$。

至此，$\lambda$的更新变得可行，模型训练ok。

序列标注

序列标注即要在给定模型参数情况下找到输入序列对应的概率最大的标注序列，可以采用维特比算法的思想。定义: $\delta_j(s|x)$表示序列到位置$j$时，状态为$s$的最大概率，即

还需要数组$\phi_j(s)$记录下$j$位置状态为$s$时$j-1$位置的状态是什么。
算法的步骤如下：

1. 从开始状态初始$\vdash$化，对所有的状态$s\in S$，令
   $\delta_1(s|x)=\Psi_1(\vdash,s,x)$.
   $\phi_1(s)=\vdash$
2. 递归计算，对每一个$s\in S, 1\le j\le n$
   $\delta_j(s|x)=\max_{s’\in S}\delta_{j-1}(s’)\cdot \Psi_j(s’,s,x)$
   $\phi_j(s)=arg\max_{s’\in S}\delta_{j-1}(s’)\cdot \Psi_j(s’,s,x)$
3. 结束迭代
   $p_{max}=\max_{s’\in S}\delta_{n}(s’)$
   $y_n=arg\max_{s’\in S}\delta_n(s’|x)$
4. 回溯
   根据$\phi$数组和$y_n$求出整个$y$序列。

任意结构CRF

TODO

参考文献
[1]. Classical Probabilistic Models and Conditional Random Fields.pdf

定义

最大熵模型也是判别模型，其基本思想是最大熵思想，即在给定关于概率分布不完全信息的情况下，仅有的无偏假设就是使得模型尽可能地均匀，通俗点说就是对一个随机事件的概率分布进行预测时，预测应当满足全部已知的约束，而对未知的情况不要做任何主观假设。在这种思想下，合适的模型就是在满足给定限制情况下最大化模型的熵。对于条件模型$p(y|x)$，其条件熵的定义为

其中，$Z$包含$x,y$的所有可能组合。

训练样本由输入、标签表征。这里引入特征函数的概念，特征函数和以前看到的特征不大一样，它是对输入和输出同时抽取特征，表示为$f(x,y)$。特征函数可以定义为二值函数，如果$x,y$满足一定的事实，那么$f(x,y)$为1，否则为0。

约束

假设训练数据集$T$有$n$条数据，特征个数为$m$个，第$i$个特征对应的特征函数为$f_i(x,y)$。令由训练数据得到的经验联合分布为$\hat{p}(x,y)$，那么特征$f_i$关于经验分布的期望值为

同样地，在模型分布上的特征函数均值可以表示为

其中，$Z$是$x,y$所有可能组合。（这里因为$x,y$所有可能组合会很多，计算上不可行）。$x$仅考虑训练集中的$x$，而$y$则是所有可能的取值，但是在实际中，$y$的可能取值是有限的、比较少的，所以这里的计算也是高效的。

至此，得到第一种约束。如果模型可以从数据中获取足够多的信息，就可以认为经验值约等于期望值，即

第二种约束为概率本身的限制，即：

类似地，可以得到

目标函数

按照最优化问题的优化习惯，将最大化问题改写成最小化问题

模型训练

带约束的优化问题可以参考拉格朗日乘子法，引入参数$\lambda=(\lambda_1,…,\lambda_{m+1})$，令

考虑上式与原始优化问题之间联系，对于约束问题，如果有一个不满足条件，那么将对应的$\lambda$分量扩展到$\infty$，那么整个公式的值就变成了$+\infty$。所以可以得到

因为函数$\Gamma(p,\lambda)$是$p(y|x)$的凸函数，所以根据拉格朗日对偶性有

首先看$\min_{p(y|x)}\Gamma(p,\lambda)$:
我们可以求$\Gamma(p,\lambda)$对$p(y|x)$的导数。逐项考虑，首先

第二项

第三项比较简单，就不单独列出来了，所以$\Gamma(p,\lambda)$对$p(y|x)$的导数可以表示为：

令上式等于0可以得到：

为了使$p(y|x)$的表达式只与特征函数有关，我们最好消去$\hat{p}(x)$。注意到$\sum_y p(y|x)=1$，将上式两边对$y$求和，可以得到

进一步可以得到

综上所述，最大熵模型也就是

第二步，求解$\lambda^{}$:
令$\Psi_{p^{}}= \min_{p(y|x)}\Gamma(p,\lambda)$，下一步就是

可以证明，最大熵模型是适定的（well-defined），其解存在且唯一。

参考文献
[1]. Classical Probabilistic Models and Conditional Random Fields.pdf
[2]. 统计学习方法. 李航

introduction

单词向量化在近些年一直是被广泛研究的课题，虽然state-of-the-art方法（word2vec）提供了通过低维矩阵嵌入方法有效地计算词之间相似性的方法，但是他们的motivation通常是不明确的。他们通用的模式是维护单词-上下文共现矩阵，初始化向量化的单词向量$u_w$、上下文单词向量$v_c$，然后使用一个可以近似表示$X_{w,c}$（$w,c$的共现次数）的函数$f(u_w,v_c)$，通过优化这个函数不断地更新$u_w,v_c$的值。（注意上下文也是一个单词，这个单词在当前单词的上下文环境中）

wordrank

wordrank把单词向量化定义成一个rank的问题，也就是：给定一个单词$w$，我们想要输出一个上下文列表$\lbrace c_1,c_2,…\rbrace$单词列表，并且要求与单词$w$共现的上下文单词出现在列表的前面。具体地，单词全集为$W$，上下文全集为$C$，$\Omega$是给定数据单词、上下文的共现矩阵，$\Omega_w$是与$w$共现的上下文集合，$\Omega_c$同理。

定义单词$w$的词向量为$u_w\in U$，上下文$c$的向量为$v_c\in V$，词和上下文的相关性越大，他们的向量内积就越大。给定单词$w$，上下文$c$的rank可以定义为其他上下文向量与单词向量乘积比当前上下文向量与但词向量乘积大的个数，也就是有多少个上下文不必当前的”差”，即：

其中函数$I(x)$是0、1损失函数，当$x\leq 0$时输出为1，否则为0。由于函数$I(x)$是不连续的函数，我们将其近似为连续函数$l(x)$，要求$l$是$I(x)$的凸上界，可以使用的候选有$l(x)=max(0,1-x)$或者$l(x)=log_2(1+2^{-x})$，所以可以得到：

我们希望rank模型将与当前单词有关的context的rank值变小，所以模型的目标函数可以是：

其中$r_{w,c}$是用以量化$w,c$之间关联的权重，定义为：

其中，$x_{max},\epsilon$是超参数，可以看出共现次数越大，权重越大。$\rho(\cdot)$是一个单调递增的凹rank损失函数，量化rank的”好坏”，首先，递增是明显的，要求是凹函数是因为希望其一阶导数非递增，从而使得相关性低的context拥有较小的敏感度（增长得慢，attention减少，想想y=x-1和y=logx），使得模型的健壮性得到提高，是很关键的一步。可能的损失函数有：

$\alpha,\beta$是超参数，控制模型“放弃rank高的上下文、注重rank低的上下文”的程度，the rate at which the algorithm gives up is determined by the hyperparameters a and b。

optimization

目标函数可以等价定义为

这是一个包含对$\Omega$和$C$求和的公式，当语料库很大时，问题就会变得难以处理。随机梯度下降（SGD）可以解决$\Omega$这一层的问题，但是$C$这一层的却难以解决，除非函数$\rho(\cdot)$是一个线性函数。可惜的是，函数$\rho(\cdot)$的特性要求其不是线性函数。

解决方法是对函数$\rho(\cdot)$进行一阶泰勒分解，由于其凹函数的性质，可以有

对于所有的$x$和$\xi$都成立，并且当$x=\xi$时等号成立。
令$\Xi=\lbrace \xi_{w,c} \rbrace_{(w,c)\in\Omega}$，于是我们可以得到一个$J(U,V)$的上界

其中$(w,c,c^{‘}) \in \Omega\times (C-\lbrace c \rbrace)$，等号成立的条件是

最小化上面这个函数就等于最小化原目标函数的上界，也就是最小化目标函数了。并且$\overline{J}(U,V,\Xi)$很好地支持SGD（内层不需要求和）。

algorithm

• 学习率$\eta$
• 重复
  • 阶段 1
  • 重复
    • 从$\Omega$中均匀采样$(w,c)$
    • 从$C-\lbrace c\rbrace$中均匀采样$(c^{‘})$
    • // update
    • $u_w\gets u_w-\eta\cdot r_{w,c}\cdot \rho’(\xi_{w,c})\cdot l(\langle u_w, v_c-v_{c^{‘}}\rangle) \cdot (v_c-v_{c^{‘}})$
    • $v_c\gets v_c-\eta\cdot r_{w,c}\cdot \rho’(\xi_{w,c})\cdot l(\langle u_w, v_c-v_{c^{‘}}\rangle) \cdot u_w$
    • $v_{c^{‘}}\gets v_{c^{‘}}-\eta\cdot r_{w,c}\cdot \rho’(\xi_{w,c})\cdot l(\langle u_w, v_c-v_{c^{‘}}\rangle) \cdot u_w$
  • 直到$U$和$V$都收敛
  • 阶段2
  • 对所有的$(w,c)\in \Omega$
    • $\xi_{w,c}=\left( \sum_{c^{‘}\in C-\lbrace c\rbrace} l(\langle u_w, v_c-v_{c^{‘}}\rangle)+\beta \right)/\alpha$
• 直到所有的$U,V,\Xi$都收敛

阶段1的时间复杂度为$O(|\Omega|)$，阶段2的时间复杂度为$O(|\Omega||C|)$，复杂度较高。考虑到阶段2其实包含矩阵乘法运算，可以考虑使用一些高效的矩阵乘法算法。训练完成后，$U,V$分别就是对应的词向量。

引用
[1]. WordRank: Learning Word Embeddings via Robust Ranking

课程调度这个题目一共有3个，以下分别描述其题目和解法。

Course Schedule 1

一共有标号从0到n-1的n个课程，有些课程需要在其他课程的基础上才能学，现在给定课程总数n和先决课程对（目标课程，先决课程）。输出这些课程能否学完

Solution 1

BFS拓扑排序可以做，DFS查找回路也可以。

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

public class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        if (prerequisites.length==0 || prerequisites[0].length==0) return true;
        List<Set<Integer>> in = new ArrayList<>(), out = new ArrayList<>();
        for (int i=0; i<numCourses; i++) {
            in.add(new HashSet<>());
            out.add(new HashSet<>());
        }

        for (int i=0; i<prerequisites.length; i++) {
            in.get(prerequisites[i][0]).add(prerequisites[i][1]); // pre-course
            out.get(prerequisites[i][1]).add(prerequisites[i][0]); // later-course
        }

        List<Integer> ready = new ArrayList<>();
        for (int i=0; i<numCourses; i++)
            if (in.get(i).size() == 0) ready.add(i);

        while (ready.size() > 0) {
            int pos = ready.remove(0);
            Set<Integer> set = out.get(pos);
            for (Object it : set.toArray()) {
                in.get((int)it).remove(pos);
                if (in.get((int)it).size() == 0) ready.add((int)it);
            }

        }

        for (int i=0; i<numCourses; i++)
            if (in.get(i).size() > 0) return false;
        return true;

    }
}

Course Schedule 2

在上一题的基础上输出，如果可以学完，输出任意一个顺序即可，否则，输出一个空的顺序[]。

Solution 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
30
31
32
33
34
35
36
37
38

public class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] ret = new int[numCourses];
        List<Set<Integer>> in = new ArrayList<>(), out = new ArrayList<>();
        for (int i=0; i<numCourses; i++) {
            in.add(new HashSet<>());
            out.add(new HashSet<>());
        }

        for (int i=0; i<prerequisites.length; i++) {
            in.get(prerequisites[i][0]).add(prerequisites[i][1]); // pre-course
            out.get(prerequisites[i][1]).add(prerequisites[i][0]); // later-course
        }

        int k = 0;
        List<Integer> ready = new ArrayList<>();
        for (int i=0; i<numCourses; i++) {
            if (in.get(i).size()==0 && out.get(i).size()==0) ret[k++] = i;
            else if (in.get(i).size()==0 && out.get(i).size()>0) ready.add(i);
        }

        while (ready.size() > 0) {
            int pos = ready.remove(0);
            ret[k++] = pos;
            Set<Integer> set = out.get(pos);
            for (Object it : set.toArray()) {
                in.get((int)it).remove(pos);
                if (in.get((int)it).size() == 0) ready.add((int)it);
            }
        }

        for (int i=0; i<numCourses; i++)
            if (in.get(i).size() > 0) return new int[0];
        return ret;

    }
}

Course Schedule 3

一共有标号从0到n-1的n个课程，每个课程都有一个持续时间。给定每个课程的持续时间t和最晚结束时间d对（t,d），要求找到能够完成的课程的最大数量。其中，1 <= d, t, n <= 10,000，同一时刻不能同时学习两门课。

[[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]

output: 3

Solution 3

先对每个课程按最晚结束时间从小到大排序。在前k-1个课程处理之后，对与第k个课程（tk,dk），前k个课程的最晚结束时间为dk，如果前k-1个课程中最优课程组合的总时长为x

• 如果此时tk + x > dk，那么这个课程就不能直接放进去，处理方法是将这个课程放进去，然后从已选课程中删除时长最大的课程（删除时长最大的肯定是最好的选择，最大堆）

• 否则，直接将当前课程放进去即可

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

class Solution {

public:
    
    int scheduleCourse(vector<vector<int>>& courses) {
        int ret = 0, sum = 0, n = 0;
        priority_queue<int> pq;
        sort(courses.begin(), courses.end(), [](const vector<int>& a, const vector<int>& b){
            if (a[1] == b[1]) return a[0] < b[0];
            return a[1] < b[1];
        }); 

        for (int i=0; i<courses.size(); i++) {
            pq.push(courses[i][0]);
            sum += courses[i][0];
            if (sum > courses[i][1]) {
                sum -= pq.top();
                pq.pop();
            }
        }

        return pq.size();
    }
};

题目描述

给定数组nums和滑动窗口长度k，求滑动窗口由左向右滑动时窗口内元素的中位数。

Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

Window position                Median
---------------               -----
[1  3  -1] -3  5  3  6  7       1
 1 [3  -1  -3] 5  3  6  7       -1
 1  3 [-1  -3  5] 3  6  7       -1
 1  3  -1 [-3  5  3] 6  7       3
 1  3  -1  -3 [5  3  6] 7       5
 1  3  -1  -3  5 [3  6  7]      6

解题思路

容易想到用set的思想，由于数组可能会有重复，所以使用的数据结构为multiset。思想如下：

• 维护一个名为window的multiset
• 每次通过迭代器获取中位数

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

vector<double> medianSlidingWindow(vector<int>& nums, int k) {
    multiset<int> ms(nums.begin(), nums.begin()+k);
    vector<double> ret;
    for (int i=k; i<=nums.size(); i++) {
        // k/2处，基数数组正好是中位数，偶数数组则是中间偏右的那一个
        auto mid = next(ms.begin(), k/2);
        if (k % 2 == 0) ret.push_back((double(*mid) + *prev(mid))/2.0);
        else ret.push_back(*mid);
        if (i == nums.size()) break;
        ms.insert(nums[i]);
        // 删除要用迭代器，否则将会删除所有值相同的元素
        // lower_bound取到值相同的最左边的元素
        ms.erase(ms.lower_bound(nums[i-k]));
    }
    return ret;
}

时间复杂度为O(kn)。

更好的方法

• 使用一个指针mid用以指向median值（基数指向中间那个元素、偶数指向中间两个元素的后一个）。
• 向window中加入/删除元素时，考虑两边比较麻烦（没做对==!）。这里的做法是保证mid左边的元素个数不变，不管右侧如何，这样结束后还是mid该在的位置
  • 添加元素时，如果添加的元素在mid左边，mid左移一位
  • 删除元素时，如果删除的元素在mid左边，mid右移一位

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

vector<double> medianSlidingWindow(vector<int>& nums, int k) {
    multiset<int> window(nums.begin(), nums.begin() + k);
    auto mid = next(window.begin(), k / 2);
    vector<double> medians;
    for (int i=k; ; i++) {

        // Push the current median.
        medians.push_back((double(*mid) + *prev(mid, 1 - k%2)) / 2);

        // If all done, return.
        if (i == nums.size())
            return medians;

        // Insert nums[i].
        window.insert(nums[i]);
        // 只保证左边的元素个数不变，右边不用管
        // 如果新插入的在左边，则左移一位，保证左边元素数量不变
        if (nums[i] < *mid)
            mid--;

        // Erase nums[i-k].
        // 只保证左边的元素个数不变，右边不用管
        // 如果删除的在左边，右移一位保证左边的元素个数不变
        if (nums[i-k] <= *mid)
            mid++;
        window.erase(window.lower_bound(nums[i-k]));
    }
}

Find Median from Data Stream

实现一个数据结构，满足两种操作：

1. 加入元素
2. 计算结构中元素的中位数

解题思路

• 使用两个优先队列（大根堆），将数据分成两部分，左边存较小的一部分，右边存较大一部分的相反数
• 计算中位数时，如果左边的个数大于右边，则左边的堆顶就是中位数；否则，两个堆的堆顶元素计算中位数
• 需要加入一个新的数时，先push进左边的堆，然后从左边的堆中pop出最大值到右边的堆
• 如果左侧堆的数量小于右侧的数量，右侧弹出一个元素并将其相反数放入左侧堆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

priority_queue<int> left;
priority_queue<int> right;
MedianFinder() {}
    
void addNum(int num) {
    left.push(num); // push到左侧
    right.push(-left.top()); // 左侧的最大值push到右侧
    left.pop();
    if (left.size() < right.size()) { // 确保左右两边的数量关系
        int tmp = -right.top();
        right.pop();
        left.push(tmp);
    }
}
    
double findMedian() {
    return left.size()>right.size()?double(left.top()) : (double(left.top())-right.top())/2;
}

thread

1

#include <thread>

构造

其他成员

• get_id : 获取线程 ID
• joinable : 检查线程是否可被 join
• join : 同步操作，线程所有的操作完成此函数才返回，阻塞调用此函数的线程。调用此函数后，对应thread对象变成non-joinable，并可以安全销毁
• detach : 将目标线程与调用线程分离开，调用此函数后，对应thread对象变成non-joinable，并可以安全销毁（这里很奇怪—!）
• swap : void swap (thread& x) noexcept，与x互换状态
• native_handle : 返回可以访问此线程详细实现信息的值
• hardware_concurrency [static] : 返回硬件线程上下文的数量

mutex

Mutex 又称互斥量，C++ 11中与 Mutex 相关的类（包括锁类型）和函数都声明在 头文件中.

std::mutex

std::mutex 对象提供了独占所有权的特性——即不支持递归地对 std::mutex 对象上锁(重复上锁)，其相关函数如下：

• 构造函数，std::mutex不允许拷贝构造，也不允许 move 拷贝，最初产生的 mutex 对象是处于 unlocked 状态的
• lock()，调用线程将锁住该互斥量。线程调用该函数会发生下面 3 种情况：(1). 如果该互斥量当前没有被锁住，则调用线程将该互斥量锁住，直到调用 unlock之前，该线程一直拥有该锁。(2). 如果当前互斥量被其他线程锁住，则当前的调用线程被阻塞住。(3). 如果当前互斥量被当前调用线程锁住，则会产生死锁(deadlock)
• unlock()， 解锁，释放对互斥量的所有权
• try_lock()，尝试锁住互斥量，如果互斥量被其他线程占有，则当前线程也不会被阻塞。线程调用该函数也会出现下面 3 种情况，(1). 如果当前互斥量没有被其他线程占有，则该线程锁住互斥量，直到该线程调用 unlock 释放互斥量。(2). 如果当前互斥量被其他线程锁住，则当前调用线程返回 false，而并不会被阻塞掉。(3). 如果当前互斥量被当前调用线程锁住，则会产生死锁(deadlock)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

std::mutex mtx;
volatile int counter(0);
void func() {
    for (int i=0; i<10000; ++i) {
        if (mtx.try_lock()) {   // 没被上锁时才自增
            ++counter;
            mtx.unlock();
        }
    }
}
int main (int argc, const char* argv[]) {
    std::thread threads[10];
    for (int i=0; i<10; ++i)
        threads[i] = std::thread(func);
    for (auto& th : threads) th.join();
    std::cout << counter << " successful increases of the counter.\n";
    return 0;
}

std::recursive_mutex

recursive_mutex与mutex类似。但是和 std::mutex 不同的是，std::recursive_mutex 允许同一个线程对互斥量多次上锁（即递归上锁），来获得对互斥量对象的多层所有权，std::recursive_mutex 释放互斥量时需要调用与该锁层次深度相同次数的 unlock()，可理解为 lock() 次数和 unlock() 次数相同

std::time_mutex

定时Mutex类，有两个特殊函数：

• try_lock_for : 接受一个时间范围，表示在这一段时间范围之内线程如果没有获得锁则被阻塞住，超时则返回false
• try_lock_until : 接受一个时间点作为参数，在指定时间点未到来之前线程如果没有获得锁则被阻塞住，超时则返回false

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

#include <chrono>

void fireworks() {
  // 等待获取锁，每200ms打印一个'-'
  while (!mtx.try_lock_for(std::chrono::milliseconds(200))) {
    std::cout << "-";
  }
  // 获取锁后休息1秒，然后打印'*'
  std::this_thread::sleep_for(std::chrono::milliseconds(1000));
  std::cout << "*\n";
  mtx.unlock();
}

std::recursive_timed_mutex

std::recursive_timed_mutex之于std::timed_mutex如同std:recursive_mutex之于std::mutex，就是允许重复上锁。

std::lock_guard

方便线程对互斥量上锁，不用考虑销毁、异常时的解锁问题。

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

#include <stdexcept>

void print_even (int x) {
    if (x%2 == 0) std::cout << x << " is even\n";
    else throw (std::logic_error("not even"));
}

void print_thread_id (int id) {
    try {
        // 实用局部的lock_guard锁定mtx保证在销毁、异常中的解锁
        std::lock_guard<std::mutex> lck (mtx);
        print_even(id);
    }
    catch (std::logic_error&) {
        std::cout << "[exception caught]\n";
    }
}

std::unique_lock

方便线程对互斥量上锁，但提供了更好的上锁和解锁控制。

1
2
3
4
5
6
7
8

void print_block (int n, char c) {
    // 临界区 (lck生存周期内对std::cout的互斥访问权)
    std::unique_lock<std::mutex> lck (mtx);
    for (int i=0; i<n; ++i) {
        std::cout << c;
    }
    std::cout << '\n';
}

future

1

#include <future>

std::future

从异步任务中获取结果，通过查询future的状态（future_status）可获取异步操作的结果。future_status有三种状态：

• deferred：异步操作还没开始
• ready：异步操作已经完成
• timeout：异步操作超时

1
2
3
4
5
6
7
8
9
10
11

std::future_status status;
    do {
        status = future.wait_for(std::chrono::seconds(1));
        if (status == std::future_status::deferred) {
            std::cout << "deferred\n";
        } else if (status == std::future_status::timeout) {
            std::cout << "timeout\n";
        } else if (status == std::future_status::ready) {
            std::cout << "ready!\n";
        }
    } while (status != std::future_status::ready);

获取future结果有三种方式：get、wait、wait_for

• get等待异步操作结束并返回结果
• wait只是等待异步操作完成，没有返回值
• wait_for是超时等待返回结果。

头文件中包含了以下几个类和函数：

• Providers 类：std::promise, std::package_task
• Futures 类：std::future, shared_future
• Providers 函数：std::async()
• 其他类型：std::future_error, std::future_errc, std::future_status, std::launch

std::promise

std::promise为获取线程函数中的某个值提供便利，在线程函数中给外面传进来的promise赋值，当线程函数执行完成之后就可以通过promis获取该值了，值得注意的是取值是间接的通过promise内部提供的future来获取的.

1
2
3
4
5
6
7

std::promise<int> pr;
    std::thread t (
        [] (std::promise<int>& p) { p.set_value_at_thread_exit(9); } ,
        std::ref(pr)
    );
    std::future<int> f = pr.get_future();
    auto r = f.get();

• promise 对象可以保存某一类型 T 的值，该值可被 future 对象读取（可能在另外一个线程中），因此 promise 也提供了一种线程同步的手段
• 在 promise 对象构造时可以和一个共享状态（通常是std::future）相关联，并可以在相关联的共享状态(std::future)上保存一个类型为 T 的值。
• 可以通过 get_future 来获取与该 promise 对象相关联的 future 对象，调用该函数之后，两个对象共享相同的共享状态
  • promise 对象是异步 Provider，它可以在某一时刻设置共享状态的值
  • future 对象可以异步返回共享状态的值，或者在必要的情况下阻塞调用者并等待共享状态标志变为 ready，然后才能获取共享状态的值
• promise对象可以通过set_value函数设置共享状态的值
• std::promise::set_value_at_thread_exit : 设置共享状态的值，但是不将共享状态的标志设置为 ready，当线程退出时该 promise 对象会自动设置为 ready

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

void print_int(std::future<int>& fut) {
    int x = fut.get(); // 获取共享状态的值.
    std::cout << "value: " << x << '\n'; // 打印 value: 10.
}

int main () {
    std::promise<int> prom; // 生成一个 std::promise<int> 对象.
    std::future<int> fut = prom.get_future(); // 和 future 关联.
    std::thread t(print_int, std::ref(fut)); // 将 future 交给另外一个线程t.
    prom.set_value(10); // 设置共享状态的值, 此处和线程t保持同步.
    t.join();
    return 0;
}

std::promise::set_exception为 promise 设置异常，此后 promise 的共享状态变标志变为 ready。下面程序的意义是：线程1从终端接收一个整数，线程2将该整数打印出来，如果线程1接收一个非整数，则为 promise 设置一个异常(failbit) ，线程2 在std::future::get 是抛出该异常。

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

void get_int(std::promise<int>& prom) {
    int x;
    std::cout << "Please, enter an integer value: ";
    std::cin.exceptions (std::ios::failbit);   // throw on failbit
    try {
        std::cin >> x;                         // sets failbit if input is not int
        prom.set_value(x);
    } catch (std::exception&) {
        prom.set_exception(std::current_exception());
    }
}

void print_int(std::future<int>& fut) {
    try {
        int x = fut.get();
        std::cout << "value: " << x << '\n';
    } catch (std::exception& e) {
        std::cout << "[exception caught: " << e.what() << "]\n";
    }
}

int main ()
{
    std::promise<int> prom;
    std::future<int> fut = prom.get_future();

    std::thread th1(get_int, std::ref(prom));
    std::thread th2(print_int, std::ref(fut));

    th1.join();
    th2.join();
    return 0;
}

std::packaged_task

std::packaged_task包装了一个可调用的目标（如function, lambda expression, bind expression, or another function object）,以便异步调用，它和promise在某种程度上有点像，promise保存了一个共享状态的值，而packaged_task保存的是一个函数。

1
2
3
4

std::packaged_task<int()> task([](){ return 7; });
std::thread t1(std::ref(task));
std::future<int> f1 = task.get_future();
auto r1 = f1.get();

std::async

std::async先将异步操作用std::packaged_task包装起来，然后将异步操作的结果放到std::promise中，这个过程就是创造未来的过程。外面再通过future.get/wait来获取这个未来的结果，std::async的原型async(std::launch::async | std::launch::deferred, f, args...)，第一个参数是线程的创建策略，有两种策略，默认的策略是立即创建线程：

• std::launch::async：在调用async就开始创建线程
• std::launch::deferred：延迟加载方式创建线程。调用async时不创建线程，直到调用了future的get或者wait时才创建线程

第二个参数是线程函数，第三个参数是线程函数的参数.

1
2
3
4
5
6
7
8
9

std::future<int> f1 = std::async(
    std::launch::async,
    []() {return 8;}
);
std::future<int> f2 = std::async(
    std::launch::async,
    [](int x) {return 8+x;},
    100
);

std::condition_variable

1

#include <condition_variable>

std::condition_variable 是条件变量，其构造方法如下：

当 std::condition_variable 对象的某个 wait 函数被调用的时候，它使用 std::unique_lock(通过 std::mutex) 来锁住当前线程。当前线程会一直被阻塞，直到另外一个线程在相同的 std::condition_variable 对象上调用了 notify_one或者’notify_all’ 函数来唤醒当前线程。

wait函数有两种形式：

• void wait( std::unique_lock<std::mutex>& lock ) : 一直阻塞直到notify_one或者’notify_all’ 函数被调用。
• template< class Predicate > void wait( std::unique_lock<std::mutex>& lock, Predicate pred ) : 只有当谓词pred()不为真的时候才等待，否则直接跳过wait

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

std::mutex mtx; // 全局互斥锁.
std::condition_variable cv; // 全局条件变量.
bool ready = false; // 全局标志位.

void do_print_id(int id)
{
    std::unique_lock <std::mutex> lck(mtx);
    while (!ready) // 如果标志位不为 true, 则等待...
        cv.wait(lck); // 当前线程被阻塞, 当全局标志位变为 true 之后,
    // 线程被唤醒, 继续往下执行打印线程编号id.
    std::cout << "thread " << id << '\n';
}

void go()
{
    std::unique_lock <std::mutex> lck(mtx);
    ready = true; // 设置全局标志位为 true.
    cv.notify_all(); // 唤醒所有线程.
}

int main()
{
    std::thread threads[10];
    // spawn 10 threads:
    for (int i = 0; i < 10; ++i)
        threads[i] = std::thread(do_print_id, i);

    std::cout << "10 threads ready to race...\n";
    go(); // go!

  for (auto & th:threads)
        th.join();

    return 0;
}

引用
[1]. C++11 并发指南二
[2]. C++11 并发指南三
[3]. C++11 并发指南
[4]. C++11 并发指南五

概念

凸包(Convex Hull)是一个计算几何（图形学）中的概念。凸包的求解方法之一是由葛立恒(Graham)发明的。给定二维平面上的点集，凸包就是将最外层的点连接起来构成的凸多边型，它能包含点集中所有点。

求解方法

选取点集中纵坐标最小的点，如果纵坐标相同则选择横坐标较小的点，设为点H（如下图）

考虑除H之外所有点和H构成的向量，按与向量$(1,0)$之间的夹角从小到大的顺序进行排序；对于夹角一样的点，则考虑其距离，如下图所示;夹角的大小由余弦值决定，因为cos函数在$[0,\pi]$上递减，所以cos值越大的点夹角越小，这里可能会遇到数值的精确度问题，开方精确度有差异的话最好比较平方大小。向量$a,b$的余弦值计算方法为

$(3,0)$即为基点，这里$(4,0),(5,0)$与基点共线，$(0,3),(1,2),(2,1)$与基点共线。但是这里的处理方法是不一样的。在逆时针扫描过程中，开始阶段，共线状态的点按距离远近进行排序，近的先；而对于最后的共线点，我们需要把距离远的点放前面，$(0,3)$先于$(1,2)$先于$(2,1)$。所以统一的处理方法是，共线的点先按距离由小到大排序，然后看排在最后面的点，如果有共线的就按他们的顺序反转。（不是最后的没关系，比如上图如果还有个$(1,1)$点，那么$(1,2),(2,1)$排在$(0,3)$前面没有影响）

最后一步，就是处理排好序的点集。逆时针扫描，基点和第一个点肯定在凸包中，然后逐个加入栈中。看第一个图，栈中点包括$(H,K)$时，向量$CK$相对于$KH$往逆时针方向偏，$C$入栈(方向不变也可以)，下一个点是$D$，由于$DC$相对于$CK$往顺时针方向偏，所以将$C$出栈；由于$DK$和$KH$满足条件，所以将$D$入栈，下一个点看$L$，以此类推。。。那么问题是如何判断两个向量是否是逆时针旋转关系呢？

可以通过向量的叉积，向量$a\times b$的方向通过右手定则判断，具体地，四指并拢指向$a$的方向，四指转动一定角度（小于180度）指向$b$的方向，大拇指的方向就是$a\times b$的方向，如下图所示

那么如何通过计算得到方向呢？由于二维向量的叉积会产生第三个维度，所以可以假设$a=(a_1,a_2)=(a_1,a_2,0),b=(b_1,b_2)=(b_1,b_2,0)$，$a\times b$计算如下

第三维的分量为$a_1b_2-a_2b_1$，举个栗子判断一下不难发现，逆时针方向转动的向量第三维分量大于0，顺时针转动的小于0.比如图中的$a\times b$指向z轴正向。所以通过计算$a_1b_2-a_2b_1$就可以知道转动方向了。

以下是c++实现

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

vector<Point> outerTrees(vector<Point>& points) {
    if (points.size() < 4) return points;
    Point bottom = points[0];
    int index = 0;
    for (int i=0; i<points.size(); i++) { // search for lowest node 
        Point point = points[i];
        if (point.y==bottom.y && point.x<bottom.x) {bottom = point; index = i;}
        if (point.y < bottom.y) {bottom = point; index = i;}
    }
    swap(points[0], points[index]);
    sort(points.begin()+1, points.end(), [bottom](const Point &p1, const Point &p2){
        double d1 = (p1.x-bottom.x)*(p1.x-bottom.x)+(p1.y-bottom.y)*(p1.y-bottom.y);
        double d2 = (p2.x-bottom.x)*(p2.x-bottom.x)+(p2.y-bottom.y)*(p2.y-bottom.y);
        double x1 = 1.0*(p1.x-bottom.x)*abs(p1.x-bottom.x)/d1;
        double x2 = 1.0*(p2.x-bottom.x)*abs(p2.x-bottom.x)/d2;

        if (x1 != x2) return x1 > x2; // angle from small to big
        return d1 < d2; // distance from close to far
    });
    int rl = points.size()-2, rr = points.size()-1;
    while (rl >= 1) { // reverse co-linear nodes from behind if necessary
        Point p1 = points[rl];
        Point p2 = points[rr];
        double d1 = (p1.x-bottom.x)*(p1.x-bottom.x)+(p1.y-bottom.y)*(p1.y-bottom.y);
        double d2 = (p2.x-bottom.x)*(p2.x-bottom.x)+(p2.y-bottom.y)*(p2.y-bottom.y);
        double x1 = 1.0*(p1.x-bottom.x)*abs(p1.x-bottom.x)/d1;
        double x2 = 1.0*(p2.x-bottom.x)*abs(p2.x-bottom.x)/d2;
        if (x1 == x2) rl--;
        else break;
    }
    if (++rl < rr && rl >= 1)while (rl < rr) swap(points[rl++], points[rr--]);

    vector<Point> ret;
    ret.push_back(points[0]);
    ret.push_back(points[1]);
    for (int i=2; i<points.size(); i++) { remove clock-wize node
        int num = 0;
        while (ret.size() > 2) {
            // last vector
            int v1x=ret[ret.size()-1].x-ret[ret.size()-2].x, v1y=ret[ret.size()-1].y-ret[ret.size()-2].y;
            // current vector
            int v2x=points[i].x-ret[ret.size()-1].x, v2y=points[i].y-ret[ret.size()-1].y;
            // cross product x1*y2-x2*y1, positive is ok
            if (v1x*v2y-v2x*v1y < 0) ret.pop_back();
            else break;
        }
        ret.push_back(points[i]);
    }
    return ret;
}

类似题目

LeeCode题目Erect the Fence就是求点的凸包问题。

还有类似的题目：求二维平面上多个点构成的最大三角形。思路是先求多个点的凸包，然后枚举凸包中的点，找到最大三角形。（$S=\sqrt{p(p-a)(p-b)(p-c)},p=\frac{a+b+c}{2}$）.

引用
[1]. Graham’s Scan法求解凸包问题
[2]. 百度百科-向量积

Softmax函数

Softmax函数的作用是归一化，对于向量$z=(z_1,…,z_n)$，Softmax函数的形式如下：

Softmax Regression形式

Softmax regression是logistic regression的多分类版本，也是线性分类器，假设一共有$K$个类别，样本特征空间维度为$n$。其基本形式如下

其中，$\theta$是系数矩阵，维度为$n\times K$，$x$是维度为$n$的样本，输出一个$K\times 1$的向量，选择最大值对应的类为结果。

训练

为了方便描述，假设$z=\theta^Tx$，所以有$f(x)=softmax(z)$。
损失函数的定义与logistic regression类似，采用交叉熵形式。假设当前样本为$x_i$，输出为$y_i$，属于第$k$类，输出为$y_i$，对应的真实结果为$\hat{y_i}=[0 0 … 1 … 0]$，第$k$位为1，其余位为0。优化方法采用梯度下降。对所有的样本$x_1,…,x_m$，首先损失函数为：

首先，根据$y_i$的分量可知，对$y_i$求导的导数只有第$k$个分量的梯度不为0

然后再求$y_{ik}$对$z_i$的导数（其他的$y_{i}$分量梯度都是0，就不用考虑了）。具体来说，考虑$y_{ik}$对$z_{ij}$的导数。
如果$j==k$，那么

所以有

如果$j!=k$，那么

所以有

由于$\hat{y_i}$只有第$k$位为1，其余位都为0，所以综上所述

有了$z_i=\theta^Tx_i$的梯度，$\theta$（其中，$\theta_j$是$\theta$的第$j$列）的梯度就简单了

有了梯度就可以使用梯度下降方法更新权值了$\theta=\theta-\frac{\partial L}{\partial \theta}$。这是随机梯度下降的梯度表示，对完整梯度下降的表示为

但是，上面方法训练出来的模型还存在冗余问题，具体来说对于$\theta$的每一列$\theta_k$满足

也就是说会有无穷多个能达到最优解的参数，解决方法是给损失函数加上一个权重衰减项

所以有

Softmax和logistic regression的关系

根据上文描述的Softmax存在的参数冗余性，构造一个二分类情况下的softmax分类器，形式如下

把上式中的$\theta$因子全部减去$\theta_1^T$，则有

这样就又回到logistic regression的格式了！

引用
[1]. UFLDL Softmax回归
[2]. 手打例子一步一步带你看懂softmax函数以及相关求导过程

RNN中文名为递归神经网络，是深度学习理论的典型模型之一。DNN和CNN都假设输入是相互独立的，但在某些情况中，比如机器翻译，输入往往还应该包含上下文信息，所以DNN和CNN在处理时序或者顺序数据时会丢失上下文信息。RNN就是处理时序数据的典型代表，其延伸版本LSTM已经在诸多领域取得了辉煌的成绩。

vanilla RNNs

以vanilla RNNs为例，为了达到记忆效果，其RNN的基本结构及展开结构如下：

展开后的结构通俗易懂，其中$x_i$时序列输入，比如单词中的字母序列，$o_i$表示输出序列，比如当前字母的下一个字母，$s_i$表示隐层的值，$U,V,W$是连接权值矩阵（共享），$s_i$经过$V$映射得到$y_i$，$y_i$经过softmax(这里的softmax只做归一化操作，不改变维度)得到结果$o_i$。

前向传播

前向传播和DNN的前向传播类似，不同点在于RNN中隐层的输入不仅包含当前时刻的输入，还包含前一时刻的隐层输入。前向传播可由以下公式给出：

Back Propagation Through Time

反向训练的过程与DNN的反响传导类似，不同点在于权值共享和隐层的处理，基本思路还是链式求导法则,误差函数可以是平方误差，也可以是交叉熵，这里选用交叉熵

激活函数可以是tanh，也可以是LeRU。训练过程就是计算参数梯度累加值，最后更新参数。对一个序列$t=1,…,T$，训练过程如下：

需要说明的是第3行$d_y=\frac{\partial E_t}{\partial y_t}$，其中推导比较麻烦，见文献[4]。由于在$t$时刻时就已经对$s_{t-1}$进行求导了，所以下一次需要加上这个导数，每一轮中对下一轮的$s$求导结果存储在$ d_{s_{raw}}$中，下一轮到的时候让$s_t$梯度加上$ d_{s_{raw}}$即可。此外式中的$d_{s_{raw}}$表示的是$Ws_{t-1}+Ux_t+b_1$的梯度，如果写成$s_{raw}=Ws_{t-1}+Ux_t+b_1,s_t=f(s_{raw})$可能会更好理解。训练完成得到各参数梯度和后，使用梯度下降思想更新参数即可。

RNN的用途

one to many ：输入一个图片，输出一句描述图片的话。
many to one ：输入一句话，判断是正面还是负面情绪。
many to many ：有个延时的，譬如机器翻译。
many to many ：输入一个视频，判断每帧类别。

RNN的限制

vanilla RNN无法解决长时依赖问题(即当前的输出与前面很长的一段序列有关，一般超过十步就无能为力了)，vanilla RNN存在着梯度爆炸和梯度消散的问题（因为梯度需要不断乘以矩阵$U,V,W$，如果矩阵最大特征值大于1，乘多次以后就会出现梯度爆炸；如果小于1，乘多次则会出现梯度消散（联想一下多次乘以一个标量，大于1则爆炸，小于1则接近0））。

解决这个问题的方案：

• 梯度爆炸：梯度裁剪的方式避免，譬如梯度大于5就强制梯度等于5
• 梯度消散：LSTM（LSTM也可能出现梯度爆炸，所以需要梯度裁剪）

vanilla RNN简单，但是效果不好！

LSTM（Long Short Term Memory）

上一节描述了vanilla RNN以及其局限性，vanilla RNN结构简单，LSTM的结构就稍微复杂点，如下图所示：

在LSTM中引入了细胞结构的概念，并引入“门”结构来去除或者增加信息到细胞状态的能力，门是一种让信息选择式通过的方法，他们包含一个 sigmoid 神经网络层和一个 pointwise 乘法操作。这里箭头合并符号表示向量堆叠拼接，(比如$w_1x_1+w_2x_2+b$可以写成$[w_1\ w_2][x_1\ x_2]^T+b=WX^T+b$)，箭头合并表示拷贝复用。

LSTM 拥有三个门，分别是：
忘记门

忘记门读取上一状态的隐层输出$h_{t-1}$和$x_t$，输出一个与$C_{t-1}$长度相同的向量，每个元素都是$[0,1]$之间的数字，表示$C_{t-1}$的通过率，1 表示完全保留，0 表示完全舍弃。

输入门

这一步是要更新细胞状态，先将旧细胞状态$C_{t-1}$与$f_t$相乘，丢弃掉我们确定需要丢弃的信息。$\hat{C_t}$使用的激活函数是tanh，输出范围是$[-1,1]$，比sigmoid有更广的范围。$i_t$的功能与$f_t$类似，决定$\hat{C_t}$的通过情况。然后将$C_{t-1}$与$f_t$乘积加到$C_{t-1}$上更新细胞状态为$C_t$.

输出门

首先，运行一个sigmoid层来确定$[h_{t-1}, x_t]$的哪个部分将输出出去。接着，我们把细胞状态通过 tanh 进行处理（得到一个在 -1 到 1 之间的值）并将它和sigmoid门的输出相乘，最终我们仅仅会输出我们确定输出的那部分。

引用
[1]. 斯坦福大学深度学习资料 CS231n
[2]. Standford CS231n 循环神经网络 简要笔记
[3]. 简书：理解 LSTM 网络
[4]. softmax分类器+cross entropy损失函数的求导

题目描述

给定一个非空数组$a_0,a_1,…,a_{n-1}$满足$0\le a_i \le 2^{31}$，找到两个元素异或的最大值。
要求时间复杂度为O(n)。

Input: [3, 10, 5, 25, 2, 8]

Output: 28

Explanation: The maximum result is 5 ^ 25 = 28.

解题思路

思路是Trie Tree，第一步将每一个元素按二进制位存储在树中，第二步对于每一个元素$a_i$，尝试找到树中能和$a_i$构成最大异或值的元素，记录这个最大值。

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
36
37
38
39
40
41

struct TrieNode {
    TrieNode *son[2]; // 0
    int val;
    TrieNode(int v) :val(v) {
        son[0] = NULL;
        son[1] = NULL;
    }
};
class Solution {
public:
int findMaximumXOR(vector<int>& nums) {
    TrieNode *root = new TrieNode(-1), *p;
    for (int i=0; i<nums.size(); i++) {  // 建树
        int cur = nums[i];
        TrieNode *father=root;
        for (int k=31; k>=0; k--) {
            int x = (cur>>k) & 1;
            if (father->son[x] == NULL) {
                p = new TrieNode(x);
                father->son[x] = p;
            } else p = father->son[x];
            father = p;
        }
    }
    int ret = 0;
    vector<int> res;
    for (int j=0; j<nums.size(); j++) { // 找最值
        int cur = nums[j], tmp=0;
        p = root;
        for (int i=31; i>=0; i--) {     // 按位找
            int x = (cur>>i) & 1;
            if (p->son[1^x] != NULL) {
                tmp += 1<<i;
                p = p->son[1^x];
            } else p = p->son[0^x];
        }
        ret = max(ret, tmp);
    }
    return ret;
}
};

再来看看解题报告上别人写的NB解法，大致思想是从高到低确定最终结果的每一位上究竟是0还是1，通过迭代剔除不可能的元素

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

public int findMaximumXOR(int[] nums) {
    int max = 0, mask = 0;
    for (int i = 31; i >= 0; i--) {
        mask |= (1 << i); // 掩码每轮多一个1
        HashSet<Integer> set = new HashSet<Integer>();
        for (int num : nums)
            set.add(num & mask); // 计算通过掩码能得到的最大值

        /* Use 0 to keep the bit, 1 to find XOR
         * 0 ^ 0 = 0
         * 0 ^ 1 = 1
         * 1 ^ 0 = 1
         * 1 ^ 1 = 0
         */
        int tmp = max | (1 << i); // in each iteration, there are pair(s) whoes Left bits can XOR to max
        for (int prefix : set) {
            if (set.contains(tmp ^ prefix))
                max = tmp;
        }
    }
    return max;
}