RECURRENT NEURAL NETWORKS TUTORIAL, PART 3 – BACKPROPAGATION THROUGH TIME AND VANISHING GRADIENTS

在之前的部分我们实现了RNN,但是并未深入探究时间反向传播算法,本文将对这一点作详细说明。我们将了解关于梯度消失问题的知识,它促使了LSTM和GRU的出现,而这两者都是NLP领域非常常见的模型。##BACKPROPAGATION THROUGH TIME (BPTT)首先我们回顾一下RNN的基本等式:我们也定义了损失函数(交叉熵):在这里,$$y_t$$是 $$t$$时刻的正确的词语, $$tilde{y_t}$$ 是我们的预测。因为我们把一整个序列(句子)当做是输入,那么错误等同于每个时间step(词语)的错误的和。![](/images/2016/06/rnn-bptt1.png)需要注意,我们的目标是计算基于参数$$U, V, W$$错误的梯度,并且通过SGD来学习到好的参数。类似于我们将错误相加的做法,对于一个训练样本,我们将各个时间点的梯度相加。$$frac{partial{E}}{partial{W}} = sum_{t} frac{partial{E_t}}{partial{W}}$$我们使用链式求导法则来计算这些梯度,这就是反向传播算法:从错误处反向计算。以下我们使用$$E_3$$作为例子。其中,$$z_3 = V s_3$$,并且$$otimes$$指的是向量外积。在这里我们需要注意到,$$frac{partial{E_3}}{partial{V}}$$只取决于当前时刻的值$$tilde{y_3}, y_3, s_3$$。如果你明确了这一点,那么计算$$V$$的梯度只是矩阵计算罢了。但是,对于$$frac{partial{E_3}}{partial{W}}$$和$$V$$就不一样了。我们写出链式法则:可以看到,$$s_3 = tanh(U x_t + W s_2)$$取决于$$s_2$$,而$$s_2$$又取决于$$W$$和$$s_1$$,以此类推。所以我们计算$$W$$的偏导,我们不能把$$s_2$$当做一个常量,相反我们需要一遍遍的应用链式法则:我们把每个时间点对于梯度贡献综合起来。换句话说,因为$$W$$在直到我们需要输出的时刻都被用到,所以我们需要计算$$t=3$$时刻直到$$t=0$$时刻:这其实和深度前馈神经网络里的标准的反向传播算法是类似的。主要的不同点在于我们把每个时间点的$$W$$的梯度综合起来。传统的神经网络的不同层之间不共享参数,于是我们也不需要综合什么。但是在我看来,BPTT只不过是在没有展开的RNN上的标准BP算法的别名罢了。类似于标准的BP算法,你也可以定义一个徳塔项来表示反向传播的内容。例如:$$delta_{2}^{(3)} = frac{partial{E_3}}{partial{z_2}} = frac{partial{E_3}}{partial{s_3}} frac{partial{s_3}}{partial{s_2}} frac{partial{s_2}}{partial{z_2}}$$,其中$$z_2 =…

0 Comments

RECURRENT NEURAL NETWORKS TUTORIAL, PART 2 – IMPLEMENTING A RNN WITH PYTHON, NUMPY AND THEANO

本文将用Python实现完整的RNN,并且用Theano来优化。语言模型我们的目标是使用RNN建立一个语言模型。以下我们举例说明什么是语言模型。例如,你说了一句包括$$m$$个词语的句子,语言模型可以为这句话出现的概率打分:$$P(w_1,cdots,w_m) = prod_{i=1}^m P(w_i mid w_1,cdots,w_{i-1})$$ 每一个词语的概率都取决于它之前的所有的词的概率。这样的模型有什么用处呢?可以用于机器翻译或者语音识别中的正确句子打分以概率生成新的句子注意到在上面的公式内,我们使用了所有的之前的词的概率,实际上这在计算和存储时的耗费都是巨大的,通常而言只会取2~4个词左右。预处理并训练数据1.标记化原始的文本需要被标记化,例如需要把文本标记为句子,句子标记为词语,并且还需要处理标点符号。我们将使用NLTK的word_tokenizesent_tokenize方法。2.移除低频词移除低频词不管是对于训练和预测都是有帮助的。这里我们设置一个上限vocabulary_size为8000,出现次数少于它的词都会被替换为UNKNOWN_TOKEN输入,而当输出是UNKNOWN_TOKEN时,它将被随机替换为一个不在词表内的词,亦或者持续预测直到不出现UNKNOWN_TOKEN为止。3.放置句子开始和结束标记为了解句子的开始和结束,我们把SENTENCE_START放置在句子开头,并且把SENTENCE_END放置在句子结尾。4.建立训练数据的矩阵RNN的输入和输出都是向量而不是字符串,我们需要把词与向量一一对应,通过index_to_word和word_to_index。比如一个训练的例子$$x$$为[0, 179, 341, 416](注意到其中每个元素都是长度为vocabulary_size的one-hot向量,所以$$x$$实际上是一个矩阵),那么其label-$$y$$为[179, 341, 416, 1],注意到我们的目标是预测下一个词,所以$$y$$就是$$x$$移动一位,并添加上最后的一个元素(预测词)的结果,其中SENTENCE_START和SENTENCE_END分别为0和1.123456789101112131415161718192021222324252627282930313233343536373839404142vocabulary_size = 8000unknown_token = "UNKNOWN_TOKEN"sentence_start_token = "SENTENCE_START"sentence_end_token = "SENTENCE_END"# Read the data and append SENTENCE_START and SENTENCE_END tokensprint…

0 Comments

char-rnn-chinese

本文主要根据Multi-layer Recurrent Neural Networks (LSTM, GRU, RNN) for character-level language models in Torch的内容来进行试验。 #准备工作 根据原文“This code is written in Lua and requires Torch. Additionally, you need to install the nngraph…

0 Comments

Note of Recommendation System in Action

本文主要关于项亮的《推荐系统实践》的笔记。推荐系统的评测方式以下也是一项最终能上线的推荐算法的依次测试顺序,离线评测将数据集分为训练集和测试集,离线对算法进行评测用户调查在上线之前通过调查得到用户满意度的信息在线评测进行AB测试,对比推荐算法指标推荐系统的评测指标满意度是推荐系统的最重要标准无法离线计算,只能通过用户调查和在线实验得到可通过停留时间、点击率和转化率来统计预测准确度最重要的离线测试标准主要方法是,在离线数据集内的训练集训练的结果与测试集对比,比较重合度。又分为评分预测和Top N推荐对于评分预测,有均方根误差(RMSE)和平均绝对误差(MAE)计算两种方式,相差不大,前者对于偏离项惩罚大,后者对于评分取整的情况会降低误差。对于Top N推荐,通常通过准确率和招呼率来评测假设$R(u)$和$T(u)$分别是训练集和测试集上的推荐,那么两者的交集长度除以$R(u)$的长度就是precision,交集长度除以$T(u)$就是recall。评分预测关注预测用户看了电影后会给电影什么样的评分,而Top N是找到用户最有可能感兴趣的电影覆盖率coverage粗略定义为推荐系统发掘的物品占全部物品的比率,精确定义为物品流行度与全部物品流行度的比率可通过信息熵和基尼系数来计算两者都是计算不同物品流行度之间的平衡度推荐系统一般具有马太效应:强者更强多样性要覆盖满足用户广大的兴趣,可以用不同的物品相似度度量函数来定义不同的多样性多样性和相似性是trade off的,需要达到一定的平衡,让推荐效果最好新颖性推荐用户未见过的物品,最简单的是推荐流行度低的物品难点在于不牺牲精度的前提下提高多样性和新颖性惊喜度推荐结果和用户的历史兴趣不相似,但却让用户觉得满意,那么就可以说推荐结果的惊喜度很高,而推荐的新颖性仅仅取决于用户是否听说过这个推荐结果。信任度用户对推荐系统的信任度高,能增加用户与推荐系统的交互提升用户对推荐系统的信任度的方法增加推荐系统的透明度:对用户的推荐需要进行解释提高用户的社交关系进行推荐实时性实时更新追踪用户的行为和状态的变化能够将新加入的物品推荐给用户鲁棒性反作弊性作弊方法行为注入攻击评分系统攻击:大批给某物品打高分如何对抗作弊采用作弊代价高的行为作为推荐系统采纳的数据使用数据前进行检测、清理商业目标不同利益方关注不同  

0 Comments

Ubuntu 16.04下为TITAN 1080 显卡安装驱动(Cuda&CudNN)及Gpu版TensorFlow

近来入坑了TITAN 1080显卡,在Ubuntu 16.04下为装好驱动以使用Gpu版TensorFlow可不简单,踩了许多坑之后写下此篇为记录。下载Cuda按装官方教程,我们可以应该安装Cuda8.0和Cudnn V5.1,在此下载CUDA 8.0 Downloads | NVIDIA Developer在这里最好选runfile local,因为选deb的话会遇到apt get的源损坏问题。降级gcc和g++由于Cuda不支持新版本的gcc和g++,所以如果建议先降级到4版本,方法见ubuntu 中 gcc/g++版本降级安装显卡驱动sudo apt-get install nvidia-367安装Cuda关闭你的图形界面sudo service lightdm stop此时电脑应该会黑屏,CTRL + ALT + F1进入命令行,登录,cd 到你存放下载的目录,执行sudo bash cuda_8.0.44_linux.run然后你会看到如Do you accept the previously…

0 Comments

个人面经(百度、腾讯、鹏元数据、行云智能数据岗)

记录自找工作以来个人的面试经历与一些思考。百度数据挖掘一面(电话面)介绍项目问题基础知识:java的多态、map和垃圾回收如何用网络知识让抢火车票更快快排的思想、时间和空间复杂度、如果是整数排序有没有O(n)的解法逻辑回归线性回归区别linux怎么查看某文件当前被哪些进程访问vim如何查找替换百度运维一面(电话面)聊项目python字符串的替换SQL的优化LInux 如何找进程杀进程百度运维二面(现场面)聊项目手写冒泡行云智能一面(现场面)遇到面试官是西电校友聊项目CNN的思想:pooling的方式、卷积的思想设计模式有什么了解多线程多进程的了解快排的思想手写代码二叉树删除中科乐创一面(现场面)最尴尬的一次,面试官是南洋理工的,聊了聊我的项目就似乎对我不感兴趣,就开始和我聊家常。。。鹏元数据一面(现场面)聊项目做了张试卷如 推导极大似然估计聚类与分类区别,列举常用聚类算法及程序包一些简单的SQL命令编程题:列举一串数字内奇偶数出现次数及引申出的结合他们业务的评级转换矩阵的打印腾讯基础研究一面(现场面)聊项目聚类与分类区别,常用聚类算法思考:诸如此类列举算法的问题,最好是迅速流利的列举出多个,不要有迟疑,不过对于其基本含义要有了解。场景题,两个含有数字的文件,找出同时出现在两个文件内的数字;若文件太大放不进内存该怎么办?思考:这种问题可小可大,可难可易。因为哪怕再小的问题在规模变大也就是涉及到大数据都是不简单的,这个问题,对于小文件,两三行代码即可搞定,那么你写出来之后,面试官基本上就会进一步问你:如果文件很大,无法同时把这两个文件装进内存,怎么办?我当时回答的是用Pandas的read_csv分块读取,这是个很不好的回答,因为掉包不是基本功。我回头想了想,也许这个答案是用generator比较好。  

0 Comments

Sort Algorithms of Linear Time Complexity

常用排序算法如归并、快排、堆排序等基于比较的排序方法都是不能突破$O(n log n)$时间复杂度的,本文着重介绍几种线性时间复杂度的排序方法。基于比较的排序为何不能突破$O(n log n)$时间复杂度?因为$N$个数有$N!$个可能的排列情况,也就是说基于比较的排序算法的判定树有$N!$个叶子结点,比较次数至少为$log(N!)= O(N log N)$ (斯特林公式)而线性复杂度的排序方法通常来说有计数排序、桶排序和基数排序三种。计数排序计数排序(Counting sort)是一种稳定的线性时间排序算法,Θ(n + k)的时间复杂度。n 是待排序数组的大小,k 是辅助数组 count 的大小。因为它并不是基于比较的的排序算法,所以它没有O(NlogN)的下限。并且在一定的条件下,使用该算法比使用快排能带来更好的效率。例如在基数排序中就运用了计数排序,因为它只需要额外的10个元素大小的辅助数组,线性的效率,并保证了稳定性。原理计数排序的主要思想是将待排序元素的值作为下标,利用辅助数组 count 记录所有的元素出现的次数。即 count[i] 的值代表元素 i 在原始数组中出现的次数。这样,原始数组的所有元素就被有有序地记录下来。当然,只知道某个元素出现的次数是不足以排序的。仔细观察 count 数组,发现对 count 数组进行累加(count[i] += count[i-1])后,count[i] 的含义就变成了原始数组 i…

0 Comments