0%

Mapreduce

论文地址: MapReduce: Simplified Data Processing on Large Clusters

Mapreduce分布式编程模型,理解起来比较简单,主要总结一下模型+实现细节

编程模型

将任务划分为Map和Reduce两个阶段由用户实现,每个阶段输入输出key-value对(形象理解可以看论文中的例子)

  1. Map 输入key-value,经过处理输出新的中间 key-value对,由MapReduce执行程序,将相同中间key聚集发送给某一个reduce执行程序
  2. Reduce 输入一个中间key和key对应的value列表,reduce执行具体聚集操作后,获得最终的输出key-value
阅读全文 »

GFS

论文地址:The Google File System

google file system,入门大数据必读三篇文章之一,最近懒得看视频,小研究一波这篇论文,读完发现这种系统论文要比人工智能论文难读一些,涉及的技术比较多,粗浅的总结一下。

论文结构

论文结构有点像我的毕业论文,首先从系统的结构出发,描述系统架构、组成等,从静态角度了解系统组成,然后从动态系统交互出发,描述系统交互,主要数据和操作流,最后单独两章描述mater节点的主要职责以及系统如何实现fault tolerance.

  1. intro 介绍

    没讲很多背景,直接讲GFS这套解决方案与以往的GFS不同点,解决不同问题:

    1. 分布式系统中组件经常失效(norm rather than exception)
    2. 按照以往的标准,目前文件大小都很大
    3. 目前对文件操作主要是添加和顺序读
    4. 面向应用设计GFS,增加了整个系统的灵活性
  2. DESIGN OVERVIEW

    系统的组成+一致性模型,基本讲明白了系统怎么实现的文件系统功能

  3. SYSTEM INTERACTIONS

    描述了系统与client读写文件的交互流程,在这过程中如何保证GFS特性(从使用的角度,描述系统)

  4. MASTER OPERATION

    阐述master节点的职责,client与GFS交互中不直接相关的操作(从管理的角度)

  5. FAULT TOLERANCE AND DIAGNOSIS

    阐述容错机制(从策略角度)

  6. MEASUREMENTS + EXPERIENCES + RELATED WORK + CONCLUSIONS

    实验验证+经验总结+相关工作+总结

阅读全文 »

基于统计的文档语义表示

在深度学习模型到来之前,通常使用统计学方法获得表示的文档语义的特征向量,主要方法包括

  1. TF-IDF
  2. 基于SVD分解的LSA(潜在语义索引/分析 Latent Semantic Indexing/Analysis)
  3. LDiA 隐形迪利克雷分布

其中前两种分布理解较为简单,LDiA涉及比较多的概率分布知识

TF-IDF

term frequency–inverse document frequency,用以评估一字词对于一个文件集或一个语料库中的其中一份文件的重要程度。字词的重要性随着它在文件中出现的次数成正比增加(TF),但同时会随着它在语料库中出现的频率成反比下降(IDF)

阅读全文 »

树状数组(Binary indexed tree)

A Fenwick tree or binary indexed tree is a data structure that can efficiently update elements and calculate prefix sums in a table of numbers.

来自Wikipedia

树状数组是一种求解前缀和问题的简单数据结构,能够在O(logn)的时间复杂度内解决区间求和问题,主要支持两种操作

  1. 单点修改
  2. 区间操作

主要思路

类比任何数均可以拆分为有限个不同2的幂次的求和,原论文作者认为一串序列的求和同样可以拆分为有限个不同长度为2的幂次的序列的和。在数字的拆分中,其二进制表示中1的个数即为不同2的幂次,例如 “10”,“12”

阅读全文 »

GPT

GPT作为NLP预训练语言模型的基石之一,从gpt1,gpt2到gpt3,不断扩大模型规模,将问题从fine-tuning拓展到zero-shot,试图解决更基础,但是更困难的无监督学习问题,三篇论文中的模型结构相同,不同的是试图解决的问题。

GPT1

Improving Language Understanding by Generative Pre-Training

要解决的问题

NLP中有监督训练数据较少,存在大量的无标签文本数据,如何使用这些数据解决NLP领域中各类问题?GPT提出了 自监督预训练+fine tuning 的方式,主要解决两个问题

  1. 预训练的训练目标是什么?损失函数是什么?
  2. 预训练得到的特征表示如何迁移到下游任务中?

解决方案

使用语言模型作为预训练的目标,在下游任务上做有监督的fine tuning

阅读全文 »

Subword分词:BPE&word-piece

在读transforme论文时,论文中在两个NMT任务中分别使用了两种编码算法byte pair encoding和word-piece,似乎子词嵌入模型是解决OOV问题不二选择,稍微了解一下

BPE

为了解决NMT中的OOV问题,基于子词模型(sub-word)以及Byte pair encoding思想提出了BPE算法,解决了词表大小压缩问题

Byte pair encoding

一种简单的数据压缩算法,寻找byte串中重复出现多次的byte对(pair of consecutive bytes),使用串中未出现过的byte替代,直到byte串中不存在重复多次的byte串。

wekipedia的例子:

阅读全文 »

2212. 射箭比赛中的最大得分

打周赛遇到的一道非常典型的0-1背包问题,但是因为太久没写过背包问题,写了40分钟才写出来,再温习一遍。

什么是0-1背包?

一共有N个物品,每个物品有对应的重量weight[i] 和价值value[i],给定一个固定容量W的背包,问能够放入背包的最大价值是多少?非常经典又相对简单的动态规划问题,关键还是在于定义状态以及状态转移公式。

贪心的角度出发,假设我选取某个物品后,新的贪心目标变为 在剩余物品和空间的条件下,选取最大价值的物品,因此父问题到子问题的转化可以定义为:(按照从左到右一个一个选的思路)

  • 父问题:是否选取第i个物品,使得总价值最大
  • 子问题:父问题 选 / 不选 第i个物品, 背包剩余 W-w[i] / W空间,如何在前i-1物品中合适选取使得子问题价值最大
阅读全文 »

BERT

论文地址:BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding

提出了一个基于transformer的预训练模型,引领了在大规模数据上预训练深度模型,在下游任务上微调的风潮,其主要贡献在两点

  1. 引领了预训练模型的风潮
  2. 特殊的训练机制,实现了”真”双向语言模型

论文结构

明显该论文的工作是基于ELMo和GPT改进,内容组织也是围绕着 前人工作+自己改进+实验效果展开的

  1. 摘要 Abstract

    提了一下 GPT和ELMo,强调BERT是区别于两者的基于transformer的“真”双向模型,并列举实验效果

  2. 介绍 Intro

    主要是围绕着直接解决的问题以及相对于前人解决方案的优越性进行阐述

    1. 首先强调 sentence-level 和 token-level 两种不同类型任务,需要聚焦于不同level的模型
    2. 又介绍了目前两种主要的预训练应用手段,一是特征提取,用预训练模型做特征提取,输入到下游任务模型;二是微调,预训练模型在下游任务数据上继续训练,微调参数
    3. 然后列举GPT和ELMo主流预训练模型存在的问题: 局限于语言模型的特性,无法实现真”双向”
    4. 引出了自己通过MLM+“next sentence prediction”,实现真双向,同时解决sentence level和token level两个问题

    自己提出问题,自己解决问题,自圆其说

阅读全文 »

Transformer

论文地址:Attention Is All You Need

本文提出一个区别于传统RNN、CNN的基于attention机制的网络架构-transformer,在具备RNN捕捉序列特征能力的基础上,实现了并行计算,降低了计算成本(看论文名字就知道作者对论文内容非常自信)

论文结构

总结下来发现这篇论文没讲故事,就是单纯的讲自己的工作,非常的简洁

  1. 摘要 abstract

    从问题提出->解决方案->效果,三句话介绍NMT->encoder-decoder->transformer模型,剩余的句子全在列举是实验效果,非常简洁

  2. 介绍 intro

    还是围绕着 rnn、encoder-decoder、attention这三个主要内容

    • 首先介绍rnn在LM和NMT中广泛应用,取得了SOTA成果,但是其还是存在无法并行计算的问题(介绍了为什么)
    • 然后介绍了attention机制能够跨距离建模依赖,但是目前研究大部分还是与rnn结合在一起
    • 最后引出了本文完全基于attention机制的transformer模型
  3. 背景 background

    • 列举了其他为了降低计算量的研究(convS2S, ByteNet),但是降低效果不如transformer(证明自己工作的价值)
    • 通过列举参考文献,证明 self-attention,decoder-encoder两种设计的有效性(证明自己解决方案的科学性)
阅读全文 »

798.得分最高的最小轮调

第一次写一点思路都没有,扣了半天最终放弃,直奔题解,发现题目主要有两个难点

  1. 从轮调位置角度考虑转换到每个元素位置考虑
    • 我的思路一直局限在从选k出发,如何计算出每个k位置的分数?怎么找到一种贪心或者动态规状态传递的方式
    • 没有从元素的角度出发,某个元素满足小于等于index时,k一定在某个范围内,所有元素决定的k的范围交集次数最多的就是最优解(表达不出来这种思维的转变)
  2. 如何记录最大交集次数?
    • 看完一半题解就想到创建一个数组,每计算出一个k的范围,就将范围内记录全部加一
    • 题解提供的差分数组思路”针不错”
阅读全文 »