Posts

This blog explains an apllication of randomized queue algorithms. Permutation client memory challenge A client program Permutation.java that takes an integer k as a command-line argument; reads in a sequence of strings from standard input using StdIn.readString(); and prints exactly k of them, uniformly at random. Print each item from the sequence at most once. More detail could be found at programming assignment specification and checklist, codes available in algs4/queues/src/....

本文介绍注意力机制如何应用于阅读理解类任务, 并介绍了由此任务催生的一些注意力变种. 注意力机制应用于阅读理解 The Standford question and answer dataset (SQuAD) 是由 Rajpurkar 等人提出的一个较有挑战性的阅读理解数据集。该数据集包含 10 万个（问题，原文，答案）三元组，原文来自于 536 篇维基百科文章，而问题和答案的构建主要是通过众包的方式，让标注人员提出最多 5 个基于文章内容的问题并提供正确答案，且答案出现在原文中。SQuAD 和之前的完形填空类阅读理解数据集如 CNN/DM，CBT 等最大的区别在于：SQuAD 中的答案不在是单个实体或单词，而可能是一段短语，这使得其答案更难预测。SQuAD 包含公开的训练集和开发集，以及一个隐藏的测试集，其采用了与 ImageNet 类似的封闭评测的方式，研究人员需提交算法到一个开放平台，并由 SQuAD 官方人员进行测试并公布结果。 由于 SQuAD 的答案限定于来自原文，模型只需要判断原文中哪些词是答案即可，因此是一种抽取式的 QA 任务而不是生成式任务。简单的 SQuAD 的模型框架可以参考seq2seq：Embed 层，Encode 层 和 Decode 层。Embed 层负责将原文和问题中的 tokens 映射为向量表示；Encode 层主要使用 RNN 来对原文和问题进行编码，这样编码后每个 token 的向量表示就蕴含了上下文的语义信息；Decode 层则基于 query-aware 的原文表示来预测答案起始位置。 但这个文本数据集涉及问题，原文，答案三个部分, 特别是需要根据问题在原文中搜寻答案的范围, 这就涉及如果把问题的信息提取出来并作用于原文. 目前各种前沿模型的关注点几乎都是在如何捕捉问题和原文之间的交互关系，也就是在 Encode 层和 Decode 层之间, 使用一个 Interaction 层处理编码了问题语义信息的原文表示，即 query-aware 的原文表示，再输入给 Decode 层。而本来应用机器翻译Attention机制就能很好的处理这种交互。 虽然注意力机制大同小异，但是不同的注意力权重（打分函数）带来的效果是不一样的。比较常用的是就是使用全局注意力机制中提到的 $$ \begin{aligned} score_{general}(t’ t) &= s^\top_{t’} W_\alpha h_t, \\ \end{aligned} $$ 就是用一个交互矩阵$W_\alpha$来捕捉问题和原文之间的交互关系....

时序决策 以经典的Atari游戏为例，agent在t时刻观测一段包含M个帧的视频$s_t = (x_{t-M+1}, …, x_t) \in S$, 然后agent做决策, 决策是选择做出一个动作 $a_t \in A = { 1, …, |A| }$(A为可选的离散动作空间 ), 这个动作会让agent获得一个奖励$r_t$. 这就是时序决策过程, 是一个通用的决策框架，可以建模各种时序决策问题，例如游戏，机器人等. Agent 观察环境，基于policy $\pi\left(a_{t} \mid s_{t}\right)$ 做出响应动作，其中 $s_{t}$是当前环境的观察值(Observation 是环境State对Agent可见的部分)。Action会获得新的 Reward $r_{t+1}$, 以及新的环境反馈 $s_{t+1}$. Note: It is important to distinguish between the state of the environment and the observation, which is the part of the environment state that the agent can see, e.g. in a poker game, the environment state consists of the cards belonging to all the players and the community cards, but the agent can observe only its own cards and a few community cards....

注意力机制如何起源的 神经网络中的注意力机制启发自人类的视觉注意力机制，能够（高分辨率地）聚焦于图像中需要重点关注的目标区域（节省大脑资源），同时（低分辨率地）感知周围的图像，然后随着时间的推移调整焦点（状态调整）。 在神经网路中，注意力机制是为了解决什么问题？ 在深度学习还没流行的时候, 传统的算法早已应用了注意力机制的思想. 比如一个非线性回归问题，对于代表位置的输入变量${x_1, …, x_m}$ 和 代表位置对应的输出值${y_1, …, y_m}$, 如何预测新的$x_n$对应的输出? Baseline 就是求均值, $$\frac{1}{m} \sum_{i=1}^{m} y_i$$ 当然更好的方案(Watson, Nadaraya, 1964)是根据不同的输入$x_i$给与$y_i$不同的权重, $$y = \sum_{i=1}^{m} \alpha(x, x_i) y_i $$ 这里$x$代表一个新的输入(作为query), 根据$x$和已有的位置$x_i$(作为key)进行某种运算, 得到$x_i$对应的输出$y_i$(作为value)的权重. 如果每一个权重都是一个Guassians分布, 并正则化, 则一个加权的回归预测模型就是:$$f(x) = \sum_i y_i \frac{k(x_i, x)}{\sum_j k(x_j, x)}$$ 这个算法的"深度学习"版本, 就是其权重是通过优化器(如sgd)学习得来, 并且把平均运算改为加权池化(weighted pooling). 如何简单直观地理解注意力机制 虽然注意力机制一开始被应用于图像识别领域，但是后来推广到神经机器翻译(NMT)中(Seq2Seq for Machine Translation, Sutskever, Vinyals, Le ‘14). NMT也是注意力机制在NLP领域最早最成功的应用之一. 在上图中，Echt，Dicke和Kiste词被送到编码器中，并且在特殊信号（未显示）之后，解码器开始生成翻译后的句子。解码器不断生成单词，直到产生特殊的句子结尾标记(如<eos>)。也就是说解码器仅根据最后一个隐含状态$h_3$来生成序列. 假如这个句子很短, 那么效果其实是很好的. 不过对于比较长的句子, 那么这个架构的弱点就暴露无疑了. 首先, 编码器能否把句子的所有信息(语言学上的和常识等知识)都理解/捕捉到? 其次, 受限于目前的实现技术(主要是硬件), 单个隐含状态(如$h_3$这个向量)的维度大小是有限的, 而句子长度以及语言的组合情况是无限的, 单靠$h_3$自身是存储信息能力是有限的. 再者, 解码器是否有足够的解码能力从一个隐含状态中解码出所有的信息? 虽然大部分句子是相对紧凑的, 但语言有个特点, 就是一个词有可能和前面好几步之外的词有联系, 比如一些指代词用于指代文本最开头出现的名词; 语义上, 某个句子的理解, 可能依赖于前面多个句子; 当然往大了说, 要理解一篇文章或一本书, 我们通常需要理解并联系多个段落, 多个章节....

Union-find applications: Percolation Problem discriptions Percolation data type. To model a percolation system, create a data type Percolation with the following API: public class Percolation { public Percolation(int n); // create n-by-n grid, with all sites blocked public void open(int row, int col); // open site (row, col) if it is not open already public boolean isOpen(int row, int col); // is site (row, col) open? public boolean isFull(int row, int col); // is site (row, col) full?...

Word2vec Mikolov et al. How to represent meanings? 如何在数学上表达词义？ Vector space models (VSMs) 表示把单词映射到(嵌入)连续的矢量空间, 而且理论上语义相似的单词会映射到空间中临近的位置。VSMs是一个历史悠久的NLP理论，但所有实现方法都不同程度依赖于Distributional Hypothesis, 即出现在相同（相似）的上下文中的单词具有相同（相似）的语义意义。利用此原则的方法大致可以分为两类: Count-based methods (例如, Latent Semantic Analysis))和Predictive models(例如 neural net language models (NNLM))。 具体的区别详见Baroni et al.. 但总的来说，Count-based methods 统计词汇间的共现频率，然后把co-occurs matrix 映射到向量空间中；而Predictive models直接通过上下文预测单词的方式来学习向量空间（也就是模型参数空间）。 Word2vec 是一种计算特别高效的predictive model, 用于从文本中学习word embeddings。它有两种方案, Continuous Bag-of-Words model (CBOW) 和 Skip-Gram model (Section 3.1 and 3.2 in Mikolov et al.). 从算法上讲, 两种方案是相似的, 只不过 CBOW 会从source context-words ('the cat sits on the')预测目标单词(例如"mat"); 而skip-gram则相反, 预测目标单词的source context-words。Skip-gram这种做法可能看起来有点随意....

循环神经网络 当人类阅读时，会根据对之前单词的理解和记忆来辅助理解当前看到的每个单词。也就是人能够很好地处理语言的长距离依赖特性（long-term dependency）。在自然语言处理任务中，很多传统的模型无法做到这一点，比如前馈神经网络；而传统的n-gram模型固然可以通过把把n系数增大来捕捉长距离依赖，但带来的非常巨大的内存消耗。 循环神经网络（Recurrent Neural Networks, RNNs)可以看做是多个共享参数的前馈神经网络不断叠加的结果  这里的核心是想办法解码历史信息, 即通过递归方程$s_i = R(x_i, s_{i−1})$让$s_i$解码序列$x_{1:n}$. 比如把所有历史信息累加就是一种非常简单粗暴的方式, 这样得到的是连续词袋模型(continuous-bag-of-words model)$s_i = R_{CBOW}(x_i, s_{i-1}) = x_i + s_{i−1}$, 虽然简单，但这种RNN其实忽略了数据的时序性质。 一般意义上的RNN是指Elman Network or Simple-RNN (S-RNN)(Elman [1990]), $s_i = R_{SRNN}(x_i, s_{i-1}) = g(x_iW^x + s_{i−1}W^s + b)$, 也就是把历史信息先进行线性变换(乘以矩阵), 再和bias加起来, 再通过一个非线性激活函数(tanh或ReLU). 添加了线性变换再进行非线性激活, 使网络对输入的顺序变得敏感。 在使用时, 给定输入序列（单词序列或语音）得出输出序列的过程如下： 把每个词$x_{t}$(以向量表示)逐个输入RNN 每一时间步$t$都有对应的隐含状态$s_t$，用于解码历史信息: $s_t = g(Ux_t + Ws_{t-1} + b)$....

What you will get from this Python digest: 1, Learn advanced python programming. 2, Learn new concepts, patterns, and methods that will expand your programming abilities, helping move you from a novice to an expert programmer. 3, Practice going from a problem description to a solution, using a series of assignments. Operator Emulating numeric types In-place operation: One modifies the data-structure itself object.__iadd__(self, other) object.__isub__(self, other) object.__imul__(self, other) object.__imatmul__(self, other) object....

CSAPP 非常巧妙的把程序设计及优化、数字电路基础、指令集体系、汇编语言、存储器体系结构、链接与装载、进程、虚存等来自不同学科的核心知识点和在一起，并以程序员的视角呈现; 告诉我们作为一个程序员，究竟需要对计算机的硬件了解到什么程度？ 本笔记是 CMU CSAPP 的学习笔记, 使用 CMU 15-213, UW CSE351 的课程视频, lab, 作业, project 辅助练习. Computer Systems: A Programmer’s Perspective (csapp), 豆瓣-深入理解计算机系统 卡内基梅隆大学 CMU 15-213 Introduction to Computer Systems (ICS) 华盛顿大学 UW CSE351: The Hardware/Software Interface 信息的表达与操作 Information is Bits + Context. Study systems by tracing the lifetime of the hello program, from the time it is created by a programmer, until it runs on a system, prints its simple message, and terminates....

文本分类 文本分类是很多业务问题中广泛使用到的NLP/监督机器学习（ML）。文本分类的目标是自动将文本/文档分类为一个或多个预定义类别。目前的成熟思路是用词向量解码文本，然后使用传统机器学习模型或者深度神经网络模型来做分类。 文本分类是学术界和工业界非常活跃的研究领域。本文主要介绍用于文本分类的几种神经网络模型方法，并比较它们的性能，代码实现主要基于Keras。文中代码都在这个DeepTextGitHub项目中. 文本分类的一些示例包括： 从社交媒体中了解受众情绪（😁 😐 😥） 检测垃圾邮件和非垃圾邮件 自动标记客户查询 将新闻文章📰分类为预定义主题 端到端文本分类流水线 端到端文本分类流水线由以下组件组成： 训练文本：输入文本，有监督模型能够通过已标注数据来学习和预测所需的类。 特征向量：特征向量是用于解码输入数据特征的信息的向量。 标签：预定义的类别/类，作为模型预测的目标。 算法模型：能够处理文本分类的算法（在我们的例子中：CNN，RNN，HAN, Fasttext） 预测：已经在历史数据集上训练过的模型，可以用于执行标签预测。 这里使用汽车消费者的评测数据集，在tsv文件中, 第一列是序号对我们没用, 第二列是label(0, 1)，分别代表（消极，积极）评价，第三列是文本. 1 操控性舒服、油耗低，性价比高 0 动力的确有点点让我相信了up的确是个代步车而已! 1 1。车的外观很喜欢。2。省油，现在磨合期7.3，相信以后还会下降。 1 内饰的做工和用料同级别同价位最厚道的 0 减震系统太硬！ 数据处理使用的类，具体见代码链接 class DataProcessor(object): """ Base class for data converters for sequence classification data sets. helper funcitons [read_tsv, read_text, read_json] """ ... class SampleProcessor(DataProcessor): """ Sample processor for the classification data set. Tranform the text to tensor for training if use pre-train model, need vocabulary file usage: process data files >>> processer = SampleProcessor(config, ) provide your own data in list format [train_X, train_Y, test_X, test_Y] >>> processer = SampleProcessor(config, data) """ 词向量 使用包含外部知识的embedding表达字词是目前的主流方法，经典的如word2vec，GLoVe，较新进的 ELMo，BERT，等预训练向量，集成了关于单词的新信息（词汇和语义），这些信息已经在非常大的数据集上进行了训练和提炼。...