deque in Python

deque是一种容器数据类型,包含在collections模块中。deque是一种类似list(list-like)的容器,具备在任一端快速插入和删除元素的特性。

deques是栈和队列的一种通用形式(deque发音为”deck”,是double-ended queu的简称),具有以下特点:

  • Thread-safe
  • Memory efficient,在任一端插入和删除元素的复杂度近似为O(1)
  • maxlen指定deque可以保存的元素数目上限,如果不指定,deque可以保存任意多的元素,否则仅能保存maxlen个元素,这种情况下在deque为满时,任一端的插入导致另一端元素的删除。

使用

导入deque:

from collections import deque

deque构造函数

class collections.deque([iterable[, maxlen]])

RNNs简介

什么是RNNs?

RNNs 背后的思想是利用顺序的信息(sequential information)。在传统的神经网络中,我们假定所有的输入(以及输出)是彼此相互独立的。但这对于很多任务来说却是一个糟糕的想法。举个例子,如果你要预测一个句子中的下一个词,你最好知道哪些词出现在这个词之前。RNNs之所以称之为 recurrent ,因为它们对序列中的每个元素执行相同的任务,同时输出依赖于前面的计算。另一种理解RNNs的方式是它们具有记忆能够捕获到目前为止已经计算的信息。从理论上讲,RNNs可以利用任意长序列中的信息,但在实际中它们限于仅往后看若干步。(why?)一个典型的RNN看起来如下所示:

A recurrent neural network and the unfolding in time of the computation involved in its forward computation.

上图显示了一个展开(unrolled or unfolded)成全网络的RNN。这里的展开我指的是写出整个句子对应的网络。例如,如果我们关心的句子由5个单词组成,那么网络将被展开成一个5层的网络,每个单词对应一层。

  • x_t 是时刻t的输入。例如,x_1可以是一个one-hot向量,对应于句子中的第二个单词。
  • s_t是时刻t的隐藏状态。它是网络的“记忆”。它的计算基于先前的隐藏状态以及当前时刻的输入:s_t=f(Ux_t + Ws_{t-1})。函数f通常是一个非线性函数,如tanh或ReLU。s_{-1}一般初始化为0,我们需要它计算第一个隐藏态。
  • o_t是时刻t的输出。例如,如果我们想要预测一个句子中的下一个词,它将是一个概率向量,其中每个概率对应词汇表中对应单词出现的概率。o_t=softmax(Vs_t)

一些注意的点:

  • 你可以将隐藏态s_t想象为网络的memory。s_t捕捉在所有先前的步骤中发生的信息。输出o_t仅仅基于时刻$t$时的memory进行计算。实际情况会更复杂,因为s_t不能捕捉太久之前的信息。
  • 与传统的神经网络不同,其在每一层使用不同的参数,RNN在所有层共享相同的参数(上图中的U, V, W)。这反映了一个事实,即RNN在每一步执行同样的任务,仅仅是输入不同。这极大地减少了要学习的参数数目。
  • 在上图中,每一步都有一个输出,在实际情况中,根据任务有的输出是不必要的。比如,当我们在预测一个句子表达的情绪是积极还是消极时,我们仅关心最后的输出,而不是每个词的sentiment。类似的,每一步的输入也不是必须的。RNN主要的特征在于其隐藏态。

RNNs可以做什么?

RNNs在许多NLP任务中表现出了巨大的成功。最常使用的一种RNNs的类型为LSTMs,比起原始的RNNs,其更擅长捕捉长期(long-term)的依赖。以下给出在NLP中RNNs的一些样例应用。

语言建模和文本生成

给定一个由单词组成的句子,在给定前面词的情况下预测每个词的概率。语言建模使我们能度量一个句子的可能性,这是机器翻译的一个重要输入(因为高概率的句子通常是正确的)。能够预测下一个词的副作用是我们得到一个生成模型,通过采样输出概率将能使模型产生新的文本。并且,取决于我们的训练数据,我们可以生成各种东西。在语言建模中,输入通常是由单词(例如,编码为one-hot向量)构成的序列,输出是由预测词构成的序列。在训练网络的时候,我们设置o_t = x_{t+1},因为我们想让步骤t处的输出成为下一个实际词。

下面是关于语言建模和文本生成的一些研究论文:

机器翻译

机器翻译与语言建模相似的地方在于输入都是由源语言(比如,德语)中的单词构成的序列。在机器翻译中,我们想要输出一个由目标语言(比如,英语)中的单词构成的序列。一个重要的区别在于输出只有在完整的输入被处理后才开始,因为我们要得到的翻译句子的第一个单词可能需要从完整输入序列捕获的信息。

RNN for Machine Translation

关于机器翻译的一些研究论文:

语音识别

给定一个由声音信号构成的序列,预测一个由语音片段组成的序列以及相应的概率。

注意:上述中的概率指的是某个语音片段的概率。

关于语音识别的研究论文:

生成图像描述

结合卷机神经网络(convNets),RNNs一直以来被作为模型的一部分,用来为无标签图片生成描述。这种组合的模型甚至能够将生成的词与在图片中发现的特征对齐。

Deep Visual-Semantic Alignments for Generating Image Descriptions

训练RNNs

训练一个RNN跟训练一个传统的神经网络是类似的。我们也使用BP算法,但是会稍做修改。由于在RNN中,参数在所有时刻共享,梯度计算不仅依赖于当前时刻,还依赖于先前的时刻。例如,为了计算在$t=4$时的梯度,我们需要考虑前3个时刻的梯度,然后把它们加起来。这称之为Backpropagation Through Time (BPTT) 。当使用BPTT训练一个原始的RNN时,将存在困难学习长期的依赖(比如,存在于很远时刻之间的依赖),这是由称之为梯度消失/梯度膨胀问题导致的。已经存在某种机制来应对这些问题,并且RNNs的某些类型(如LSTMs)被特别设计来解决这些问题。

RNN扩展

多年以来,研究者们已经开发出了更复杂类型的RNNs来应对原始RNNs模型的缺点。下面提供一个简要的overview。

Bidirectional RNNs(双向RNNs),它背后的想法是在时刻$t$的输出不仅依赖于先前的元素,也依赖于后续的元素。比如,要预测一个句子中缺失的单词,你会查看其左右的上下文。

Bidirectional RNN

Deep (Bidirectional) RNNs

Deep Bidirectional RNN

LSTM networks

LSTM相比原始的RNNs在结构上没有根本的不同,但使用了不同的函数去计算隐藏态。在LSTM中,memory称之为cells,可以将其想象为黑盒子,它们接受先前的隐藏态h_{t-1}和当前的输入x_t作为输入。在内部,这些cells决定在memory中保留什么(以及擦除什么)。最后将先前的状态,当前的记忆以及输入结合起来。这种类型的单元被证明在捕获长期依赖上十分高效。如果你有兴趣了解更多,这篇博文给出了一个十分出色的解释

总结

在这篇博文中,我简要介绍了RNNs是什么以及RNNs可以做什么。在下一篇博文中,我将使用Python和Theano实现一个语言模型RNN的初级版本。

一种元素划分方法

描述

给定一个整数数组nums和一个整数kk表示数组中的一个位置,取值为[0,nums.size()-1]中的一个值,该位置元素即为pivot,在一次遍历中,将元素划分为小于、等于和大于pivot的三组。

Solution

维护四个子数组:bottom(元素小于pivot),middle (元素等于pivot),unclassifiedtop(元素大于pivot)。一开始所有的元素都是unclassified,遍历这个组的元素,根据当前元素与pivot的相对关系将元素移动到bottommiddletop组。

举个具体的例子:假设数组nums[-3,0,-1,1,1,?,?,?,4,2],其中1?分别表示pivot和unclassified元素。对于第一个未分类的元素,nums[5],共有三种可能性:

  • nums[5] < pivot,例如nums[5] = -5。我们将其与第一个1进行交换,得到新数组为[-3,0,-1,-5,1,1,?,?,4,2]

  • nums[5] == pivot,例如nums[5] = 1。我们无需任何移动,只需继续考察下一个未分类的元素,新数组为[-3,0,-1,1,1,1,?,?,4,2]

  • nums[5] > pivot,例如nums[5] = 3。我们将其与未分类的最后一个元素进行交换,得到新数组为[-3,0,-1,1,1,?,?,3,4,2]

C++ 实现

void partition(vector<int>& nums, int k) {
    int pivot = nums[k];
    // invairants:
    // bottom: nums[0, smaller - 1]
    // middle: nums[smaller, equal - 1]
    // unclassified: nums[equal, larger - 1]
    // top: nums[larger, nums.size() - 1]
    int smaller = 0, equal = 0, larger = nums.size();
    // keep iterating as long as there is an unclassified element
    while (equal < larger) {
        if (nums[equal] < pivot) {
            swap(nums[smaller++], nums[equal++]);
        } else if (nums[equal] == pivot) {
            ++equal;
        } else {
            swap(nums[equal], nums[--larger]);
        }
    }
}

每次迭代将未分类元素的数目减1,每次迭代的时间开销是O(1),总的时间复杂度为O(n)。很明显,空间复杂度为O(1)