编辑器背后的数据结构

大约刚上大二的时候,想做一个编辑器控件。不是一个用Scintilla套上外壳的编辑器,而是一个能被套上外壳的控件。当然它最后也成为了我众多流产了的练手项目中的一员,不过人人黑历史里还留存着当时的一张截图

那段时间也对编辑器所使用的数据结构非常感兴趣。我们需要一种数据结构,能够支持字符串高效地索引、遍历、插入和删除。当时找的一些论文和书还躺在硬盘里一直没删,如今拿出来再嚼一嚼。下面介绍几种在编辑器中常见的数据结构。

Continue reading “编辑器背后的数据结构”

贝叶斯分类器

这是3月25日我在TM组机器学习讨论会上的分享。

Content


  1. 贝叶斯决策论
  2. 朴素贝叶斯分类器
  3. 半朴素贝叶斯分类器
  4. 贝叶斯网络

1. 贝叶斯决策论


贝叶斯决策论是一种基于概率的决策理论。当所有相关的概率都已知的理想情况下,贝叶斯决策论考虑如何基于这些概率和误判损失来选择最优的类别标记。

Example

哈工大与哈师大的同学举办大型联♂谊♀会,两个学校分别有500人参与。在联谊会上随机找到一个同学,请猜测他是那个学校的学生?

如果我们一点额外信息都不知道的话,只能随机猜测给出答案。如果我们能够提前知道一点点信息的话,就能够更大程度地猜中正确答案。比如,性别信息:

 

如此的话,假若这个同学是男生,我们肯定会猜测他是哈工大的学生。而从贝叶斯决策论的角度来看,我们需要比较以下两个概率大小:

  • P(工大学生=是 | 性别 = X)
  • P(师大学生=是 | 性别 = X)

上述两个概率被称作后验概率。后验概率往往难以直接获得,我们需要采用一定的手段进行计算。一些算法采用直接对后验概率进行建模的方法,例如SVM、决策树等,这些模型称为判别式模型。而先对联合概率进行建模、进而计算后验概率的模型,称为生成式模型

\(P(c|\boldsymbol{x})=\frac{P(\boldsymbol{x}, c)}{P(\boldsymbol{x})}=\frac{P(c)P(\boldsymbol{x}|c)}{P(\boldsymbol{x})}\)

由此可以计算得到,P(工大学生=是 | 性别 = 男)为4/5,P(师大学生=是 | 性别 = 男)为1/5.

在上面的例子中,我们直接使用了后验概率对类别进行估计。实际问题中,如果将某一类估计错误的代价比较大的话,可以选择在后验概率前乘以一个系数,变为期望损失。分类也从最小化分类错误率变为最小化期望损失。

在上面的式子中,\(P(c)\)代表的是类先验概率。在样本足够大的情况下,直接使用频率即可作为这一概率;\(P(\boldsymbol{x}|c)\)叫做类条件概率,它跟属性x的联合概率有关。上面的例子中,x只有一维,而在实际问题中,往往会选择很多个Feature。此时他们的联合概率就变得难以计算,因此我们需要一些手段对它们进行估计。

Continue reading “贝叶斯分类器”

Goodbye WordPress

花了点时间把博客从Wordpress换到了Ghost上。一是觉得Wordpress有点慢,TTFB(Time To First Byte)常年在1s左右,状态不好能到几秒十几秒。换到Ghost之后,基本稳定在400毫秒。要是把服务器换回旧金山应该还会更好一点。二是我基本上就用Markdown随便写一写,有高亮有公式就够了,Ghost后台也足够简洁,自己把Prism.js代码高亮和MathJax公式加上就好。

不过迁移的时候,导出插件把我的代码全都弄乱了……还需要人工调教,甚至每段代码中<<之后的代码全部丢失!!如果你也打算从Wordpress导出Ghost格式的数据,一定要记得备份代码!

再就是基本找不到称心的主题,还是先用默认的Casper吧,加了个封面之后感觉倒是好了很多。

站在镜像源背后的男人

@雨翌 说想知道镜像源是如何工作的,我们就来说一说这个。其实要做一个镜像源,需要搞定的有两件事:一是如何向广大用户提供下载服务,一条httpd start就搞定了;二是如何与上游同步,然而这种东西也一条rsync就搞定了:joy:

关于rsync

rsync提供了一种快速的文件同步的机制。一般的diff算法需要分别遍历两个文件,然而这种功能并不适用于远程传输:如果我能够同时获得需要同步的两个文件,再diff他们就没什么意义了。rsync使用的算法并不是特别复杂,可以Google The rsync algorithm 搜到Andrew Tridgell在1996年的论文,man rsync可以得到使用说明。

Continue reading “站在镜像源背后的男人”

Brainfuck JIT Compiler in Rust

Hello JIT


JIT不是一个神秘的玩意。

—— Tondbal ik Ni

我们都知道,对于解释型的语言实现来说,性能是大家关注的焦点。比如,这位 Tondbal ik Ni 曾经还说过:

P*没上JIT,慢的一逼!

—— Tondbal ik Ni

似乎这句话总是隐含着另一层意思:实现JIT,难!而当我们再一联想到JVM这种庞然大东西的时候,很自然的就

然而!JIT原理并不复杂,做出一个玩具JIT Compiler更是非常轻松。之所以JVMs那么庞大而复杂,原因之一在于它们做了大大大量的优化工作。

我们今天就要来看看JIT究竟是个什么东西!

Just-in-Time Compiler


JIT Compiler,究其根本还是一个Compiler。一个Ahead-of-Time Compiler的编译过程往往会有这些(既不充分也不必要的)步骤:

  • 词法分析
  • 语法分析
  • 语法制导定义或翻译
  • 中间代码生成
  • 代码优化
  • 目标代码生成

对于解释器来说,往往将编译工作进行到中间某一步后就直接进行解释执行了,并不生成目标代码。而JIT Compiler却是要生成目标代码的,最终执行的是编译好后的Native Code。只不过,它将目标代码生成的部分推迟到了执行期才进行。这样的好处有:

  • 无需重新编译就可以实现跨平台
    参考Java,它将平台差异隔离在了中间代码部分(指Java ByteCode)。
  • 运行时优化
    当年大欢还在用Gentoo的时候曾经开过嘲讽:本地编译,优化开的细,比你Arch强多了(然而后来还是倒戈到了Arch 666666)而一个JIT Compiler不仅知道目标平台的信息,更知道程序的运行时信息,因此往往可以有更多的优化。
  • 解释/编译混合
    这其实也可以看作是一种优化措施,即执行次数多的代码JIT编译后执行,执行次数少的代码解释执行。因为JIT还是需要一步编译的过程,如果代码执行次数少,很可能抵消不了编译过程带来的时间开销。

所以,其实优化是JIT Compiler中相当重要的一部分。如果我们不要优化,那可是简单了很多哟。

Core of JIT


如果你能看懂这段代码,那就说明你已经掌握了JIT的精髓了:

#include <stdio.h> 
#include <string.h>
#include <sys/mman.h> 

char f[] = {0x48, 0xC7, 0xC0, 0x00, 0x00, 0x00, 0x00, 0xC3}; 

int main(){  
    int a = 5; memcpy(&f[3], &a, 4); 
    char* mem = mmap(NULL, sizeof(f), PROT_WRITE | PROT_EXEC, MAP_ANON | MAP_PRIVATE, -1, 0); 
    memcpy(mem, f, sizeof(f)); 
    printf("%dn", ((int (*)())mem)()); munmap(mem, sizeof(f)); 
    return 0;
 }

其中mmap的作用是申请按照PageSize对齐的内存,并可以修改页面保护属性。

所以一个JIT Compiler编译的主要步骤就是:

  • 申请一块可写、并且将来可以改成可执行的内存。
  • 生成机器代码,写入内存。
  • 修改内存页面属性,Call it!

So easy,下面进入脑残环节。

An interpreter for Brainf*ck


我们将实现一个Brainfuck的解释器,随后再实现一个JIT编译器。之所以选择Brainfuck,自然是因为它相当简单,完全可以当做中间代码进行处理,省去了词法语法分析、中间代码生成等与编译原理直接相关的部分。

解释器写起来就太简单了。Brainfuck预设我们有一块无限大的内存,初值均为0。数据指针指向第一个字节。它支持8种操作:

  • >
    数据指针右移一格
  • <
    数据指针左移一格
  • +
    数据指针指向的内存内容+1
  • -
    数据指针指向的内存内容-1
  • .
    putchar
  • ,
    getchar
  • [
    如果当前内存内容 == 0,则向后跳转至对应的]
  • ]
    如果当前内存内容 != 0,则向前跳转至对应的[

翻译器部分可以作为大一的C语言实验哈哈哈哈

A JIT Compiler for Brainf*ck


如果要手撸JIT Compiler,则需要对目标平台有一定的了解。我们这里的目标平台是x86_64,这个网址 可以在线将汇编生成为x86或x64的机器代码。

第一步:申请PageSize对齐的内存
这一步除了使用mmap,还可以使用posix_memalign。

第二步:生成函数框架
在这里我们将一整个Brainfuck程序编译成一个函数。这个函数接受一个参数,即我们事先申请好的一块内存作为数据区域。对于x64来说,Linux等类Unix系统遵循的调用约定是System V AMD64 ABI,函数的第一个参数由Rdi传递。因此我们生成的函数的开始与结束部分如下:

pub fn compile_and_run(&mut self, code: &str) {  
    self.jit_code.emit_push_r(Reg::Rbp); 
    self.jit_code.emit_mov_rr(Reg::Rbp, Reg::Rsp); 
    self.emit_push_regs(); //Save regs 
    self.jit_code.emit_mov_ri(Reg::Rbx, 0); //Rbx = data_pointer 
    self.jit_code.emit_mov_rr(Reg::Rdx, Reg::Rdi); //Rdx = memory_base 

    //more code here... 

    self.emit_pop_regs(); //Load regs that saved before 
    self.jit_code.emit_mov_rr(Reg::Rsp, Reg::Rbp);
    self.jit_code.emit_pop_r(Reg::Rbp);     self.jit_code.emit_ret(); 
}

上面的代码中,各个emit函数的作用是生成相应的机器代码,放入内存中。例如emit_push_r(Reg::Rbp)将生成机器码0x55,它对应的汇编为push rbp

接下来就是根据Brainfuck各个操作生成机器码了。例如>操作:

self.jit_code.emit_inc_r(Reg::Rbx);  

So easy. 需要额外说明的只有两点:

一是我们可能需要重定位操作。当我们的buffer空间不够的时候,需要对其进行扩大,这样的话我们代码所在的 地址就会变动。而有一些指令(比如Relative跳转、RelativeCall等)它的操作数是当前RIP(即程序计数器PC)与目标地址的 Offset,这就需要当我们最终结束生成这个函数时,再对这些指令的操作数进行计算。

二是对于[操作来说,需要一个patch back的过程。当我们在编译过程中遇到它的时候,我们并不知道跳转的目的地址是哪里。只有在遇到对应的]时,才能更新它的跳转地址。

第三步:Call it!

let mut memory: Vec<u8>= vec![0; 10000];  
let func: extern "C" fn(*mut u8) = unsafe { mem::transmute(self.jit_code.function()) };  
func(memory.as_mut_ptr());  

Performance Comparison


我找了一个用Brainfuck写的Mendelbrot程序进行测试,它会在控制台输出Mendelbrot的ASCII图(大神请受我一拜 )。除了上面自己实现的解释器和JIT编译器外,我还找了一个Brainfuck的编译器bfc进行测试。

测试结果大致如下:

Interpreter: ~1min
JIT: ~4.31s
bfc: ~4.21s

代码请参 https://github.com/dontpanic92/rainfuck

最后,由于将汇编翻译为机器码是一件体力活,我们还可以使用一些现成的工具。例如DynASM,通过预处理的方式将C + ASM混合代码处理为C语言代码(即省去了我们显示emit的部分)。或者,也可以考虑使用LibJIT或LibGCCJIT等库。

Reference


  1. http://blog.reverberate.org/2012/12/hello-jit-world-joy-of-simple-jits.html
  2. http://www.hydrocodedesign.com/2014/01/17/jit-just-in-time-compiler-rust/
  3. http://www.jonathanturner.org/2015/12/building-a-simple-jit-in-rust.html

使用Reflexil修改Unity3D游戏逻辑

曾经有个游戏叫做《新剑侠传奇》,曾经停留在一个尴尬的版本1.0.7。作为一名抠脚大汉,自然要坐在在电脑前为广大玩家发福利!

故事背景

游戏发售之后出现了一些Bug,官方在更新至1.0.7版本后决定回炉。然而这一版本依然有一些玩家比较需要的Feature没有实现。在长达两周多的回炉阶段,我的补丁横空出现啦!

技术背景

MSIL可以较为轻易地反编译回C#/VB代码,如果不做代码混淆的话,可读性非常高。目前很多国产单机游戏都选择Unity 3D做为引擎:scream: ,并使用C#作为主要逻辑的实现语言。这为我们修改游戏逻辑创造了相当好的条件。

实现功能

  • 打击感增强
    通过在命中目标后停顿画面0.1秒实现。
  • 新增操作模式
    《新》是一个具备跟随视角的3D游戏,鼠标旋转视角,鼠标点击怪物为普攻,感觉略坑爹。新增操作模式采用类似龙之谷的方式:默认隐藏鼠标,鼠标移动旋转视角,鼠标点击为普攻,ctrl键呼出鼠标。
  • 摄像机位置记忆
    每次剧情之后摄像机都会回到初始位置,不会记忆上次用户调整的摄像机与人物的距离。
  • 暂停游戏
    进入战斗或者开始剧情之后,终于可以随意去上厕所了……
  • 跳过开始动画
    打开游戏时无需强制观看片头。
  • 画面改善:对比度增强、Bloom、HDR
    使用Unity内置Shader实现。

工具准备

  1. .NET Reflector
    我们用 .NET Reflector 来对 .NET Managed DLL 进行反编译工作。对于没有进行混淆或加密操作的程序,可以得到可读性很高的代码。
    0<em>1448775094110</em>1.png
  2. Reflexil
    Reflexil 可以在已经编译好的Managed DLL中插入MSIL代码。它提供了.NET Relfector的插件,安装好后即可直接插入IL代码。
  3. XamarinStudio (MonoStudio)
    其实这个有无皆可。但是如果不想所有代码全部使用IL手写的话,还是搞一个比较好。

代码修改

拿打击感增强作为一个例子,我们来看一下如何修改。Unity 3D游戏的主体逻辑都在/xxxx_Data/Managed/Assembly-CSharp.dll中。这个游戏的逻辑由几百个类/枚举构成,如果游戏大量使用了Unity插件(比如可视化编程:see<em>no</em>evil: ),可能还会更多。

增强打击感的方法是在玩家命中敌人后画面停顿0.1秒。所以我们需要在命中时记录当前时间、停顿画面,然后在0.1秒后取消停顿。

经过浏览代码,发现负责进行攻击的逻辑集中在Fighter类中。我们需要修改的有两个函数:一个是CalcHurt,发生在玩家已经命中怪物之 后,用于计算伤害;另一个是Update,每次迭代更新逻辑时都会调用这个函数。我们还需要一个Field用于记录停顿时间,可以直接在类上右击通过 Reflexil添加。

打开CalcHurt方法,在Reflexil中添加IL代码。IL代码非常简单易懂,而且我们并不需要掌握所有的IL指令。简介可以参考Introduction to IL Assembly Language,或者在Common Language Infrastructure (CLI) | ECMA-335中有所有指令的列表。

在修改完IL代码后,.NET Reflector会重新加载并反编译代码。如果指令有错误,.NET Reflector会无法反汇编成功。

停顿功能使用了Unity提供的Time.settimeScale函数,获取时间使用Time.getrealtimeSinceStartup。这些函数可以参考Unity 3D Manual

举例来说,

Time.set_timeScale(0.001f); InjectedField = Time.get_realtimeSinceStartup + 0.1;  

的IL代码如下:

ldc.r4 0.0001 call Time.set_timeScale call Time.get_realtimeSinceStartup ldc.rc 0.1 add stsfld InjectedField #InjectedFiled为静态成员  

就是这么简单啦。

使用XamarinStudio

如果不想所有代码全部手写,可以使用XamarinStudio新写一个Class,将所有新的逻辑放在这里。然后再修改原来的Assembly-CSharp.dll时,所有位置都变成函数调用就行了。

在编写新Class时,需要把游戏的Managed目录中的相关DLL作为引用添加进我们的工程里。对于这个游戏来说,我们主要用到了 UnityEngine、Assembly-CSharp、Assembly-CSharp-firstpass、Assembly- UnityScript-firstpass。

写好Class后,可以使用Reflexil将改Class添加进Assemby-CSharp的引用中。
0<em>1448778641887</em>3.png

请原谅时间久远电脑上已经没有XamarinStudio了:joy:

替换原始文件

没什么问题之后,就可以去论坛或者贴吧收获一番经验了~

关于Intel超线程技术

原回答自知乎:奔腾四和SNB之后的超线程技术一样吗?

1.Pentium 4 HT(NetBurst)和Core i7(Nehalem)中的超线程技术一样吗?

Intel的超线程技术在2002年2月发布的志强处理器中首次出现,并在同年12月发布的Pentium 4 HT中同样加入了这一技术[1]。关于此时的Intel的超线程技术的论文比较多,比如(Deborah T. Marr et al, 2002)[2]。论文中提到,architecture state在各个逻辑线程中是独立存在的,而其余几乎所有资源都是共享的。Architecture state主要包括的是各种寄存器,例如通用寄存器、控制寄存器CR以及APIC寄存器等;而共享的包括缓存、执行部件、分支预测、控制逻辑以及总线。

而后来在Nehalem核心(Core i7)中重新回归的超线程技术,我没有找到官方详细的论文。不过找到了一个德克萨斯A&M大学博士生的论文,关于Nahalem核心的[3]。文中同样提到:对于同一个物理核上的逻辑核心,它们之间

  • 独立:寄存器状态、返回栈缓冲(用于预测函数返回指令)、指令TLB(用于加速虚拟地址与物理地址的转换)
  • 分隔(静态划分):各种缓冲
  • 竞争共享:分为SMT-sensitive 和SMT-insensitive。保留栈(用于实现乱序执行)、数据TLB、二级TLB等属于SMT-sensitive,所有执行单元均为SMT-insensitive。

以及共享Cache。

所以结构上看,基本一致。

两篇论文中都有提到CPU的Pipeline(流水线结构)。当Nehalem开启超线程时,将从两个线程中取指令,之后送入后端乱序执行引擎执 行。而[1]中提到得Pentium 4在开启超线程后的做法则更为详细:两套指针分别记录两个线程的PC,解码后存入Execution Trace Cache(其为一级指令缓存的主要部分)。两个线程再按照时钟周期依次访问这个Cache。如果有一个线程stall住了,则另一个随意用。

大致来看,主要步骤基本相同。不过细节不太清楚。

2.什么是超线程?

超线程(即Simultaneous multithreading[4])属于线程级并行方法。在说超线程技术(多线程技术)之前,我们先来看一下超标量技术。

超标量技术是一种指令级并行技术,具备超标量特性的CPU具有同时发射多条指令的能力,这样CPU就可以充分利用各种执行部件。举例来说,如果单发 射一条加法指令,那么在执行过程中只有加法部件(或算数计算部件)被利用起来;如果我有两条指令:add R1, R2; shr R3, 3(加法和右移),如果两条指令同时执行,那么加法部件和移位部件就同时利用起来了。

然而能够同时执行的前提是:两条指令之间不能有相关性。例如第一条指令需要写R1,第二条指令需要读R1,那么这两条指令无法同时执行。由此即诞生出了乱序执行(Out of Order)技术:如果第三条指令与前两条指令没有相关性,则可以先执行第三条指令。

超线程技术则可以更加充分地利用执行部件:同时执行两条线程,进一步降低了指令之间的相关性。同时,如果一个线程需要访存(意味着大量的时钟周期可能被浪费)、或是分支预测失败(意味着需要清空流水线),超线程的优势就更明显了。

然而对于超线程技术的优劣则有激烈的讨论,主要集中在性能的提升的同时芯片面积与功耗等也在增加,这样的trade-off是否合适。

3.关于超线程技术消失又重现

Pentium Pro、Pentium 2、Pentium 3所使用的架构均为P6架构,Pentium 4使用Netburst架构,后续的Core 2使用的是Core架构,从Core i系列开始进入Nehalem/Sandy Bridge架构等[5]。

然而,NetBurst是相对独立的一个架构,让人记忆深刻的就是超长的流水线和相当高的频率。而Core架构是基于P6的变种Pentium M的架构改进而来的。在Intel的一个Slides中也可以得知,NetBurst和P6的Pipeline差异较大,Nehalem的基础需要在二者 中做出选择。而最后做出让多线程回归的决定,也是一种“抉择”[6]。

Reference

  1. Hyper-threading
  2. Marr D, Binns F, Hill D L, et al. Hyper-Threading Technology Architecture and Microarchitecture[J]. Intel Technology Journal, 2002, 6(1):1.
    http://www.cs.sfu.ca/~fedorova/Teaching/CMPT886/Spring2007/papers/hyper-threading.pdf
  3. Thomadakis M E. The Architecture of the Nehalem Processor and Nehalem-EP SMP Platforms[J]. Jfe Technical Report, 2011.
    http://sc.tamu.edu/systems/eos/nehalem.pdf
  4. Simultaneous multithreading
  5. Nehalem (microarchitecture) P6 (microarchitecture) Intel Core (microarchitecture)
  6. http://web.stanford.edu/class/ee380/Abstracts/100217-slides.pdf

深度学习简介及单词的向量化表示

Content

  • 深度学习简介
  • NLP与深度学习
  • 单词的向量化表示

1. 深度学习简介

首先应当明确的是,深度学习是机器学习中的一个领域。然而与传统机器学习所不同的是,传统的机器学习的重点在于特征的设计。在设计过特征之后,就变成了研究如何调整权重、优化参数来得到一个最优的结果。

图片1

然而特征设计所涉及的知识、经验的储备往往只有博士级别的研究人员才能够得心应手,而且特征设计的优劣往往直接影响最终的分类结果。与之相反,深度学习应用的是多层特征学习,其中特征学习指的是计算机能够自动地学习到特征的表示,这就解决了手工选择特征局限性较大的问题。深度学习提供了一个近乎统一的框架。它够表达各种信息,能够自动学习,并且非常灵活。这个框架也同样支持监督学习与非监督学习两种学习方式。

除此之外,深度学习还具备以下特点:

  1. 数据量增大时,深度学习的获益更多;
  2. 能够利用多核CPU、GPU加速
  3. 不断涌出的新模型、新算法
  4. 最终性能的提升

2. NLP与深度学习

事实上,在NLP领域,深度学习已经开始展现它的威力了。在应用方面,机器翻译、情感分析、问答系统等都依靠深度学习取得了重大的进步;而在NLP的各个层次上,例如语音识别、形态分析、句法分析、语义解释等,深度学习也发挥了重要的作用。接下来

选区_006

语音

在语音层面,传统的表示形式采用了表格的形式来表示每一个音素。而在深度学习中,将每一个音素表示为向量。

字形

对于一个单词来说,传统的表示形式将词根、前缀和后缀分开表示,例如un-interest-ed。而在深度学习中,往往将一个词素表示为一个向量。

图片3

句法

传统的表示方法会显示地标注出每一个短语的具体类别,例如VP、NP等。而在深度学习中,会将一个词或短语均表示为向量。

语义

lambda演算是一种在语义层面的传统表示方式。例如,将likes视作接受两个参数的函数,每一次合并都相当于柯里化的过程:

图片4

而在深度学习中,仍然将语义表示为向量的合并。

可以看出,向量形式是NLP中所有层次的表达形式。


3. 文本的向量化表示

意义

语言文字或一些符号具备一定的意义。例如,苹果和apple所指代的意义相同。而对于一个外星人来讲,■△▲〓※↓↑〓↓说不定就代表“苹果”。因此,如果想要让计算机理解这一层意义,那么它也需要一种表示;反之,如果我们认为某种表示是计算机所理解的“苹果”,那么即便我们无法阅读(例如■△▲〓※↓↑〓↓),这也是在合理范围之中的。

意义在计算机中的表示

一种表达意义的方式是利用同义词和上位词。例如,熊猫属于动物一类,我们可以用“动物”来表达熊猫的某些方面的意义。再比如,good和well有时意义相近,那么我们可以用well来代表good的某些方面的意义。

然而,这样的表示的问题在于:

  • 缺乏语义差别的信息
  • 难以适应新词
  • 主观
  • 需要人工标注
  • 相似度难以计算

究其根本原因,在于这种方式将单词视为了一种原子符号。或者说,如果在向量空间中对其进行表示的话,我们把它叫做one-hot:

选区_007

one-hot的问题在于,无法表示单词之间的意义相近的关系。例如,hotel和motel两个词,如果利用one-hot形式来表示的话:

hotel  = [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0]

motel = [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0]

我们无法使用向量运算来获得它们之间意义上的相似度。

You shall know a word by the company it keeps.

–J.R.Firth

J.R.Firth是50年代著名的语言学家,他的这句话被誉为当代NLP领域中最成功的思想之一。对于一个单词的意义,较好的方式是考虑它的上下文。

图片5

而这个“上下文”,则有不同的范围可以选择:其一是将整个文档作为上下文,另一种是选择一个较小的固定的窗口作为上下文。对于“全文档共现”来说,单词向量的维数是文档的个数,如果这一单词在某一篇文档中出现,则该维置1。全文档共现的方式能够挖掘单词的隐含语义。例如,对于“足球”和“教练”来说,它们很有可能在多篇文档中共同出现,则它们的向量也有多维同为1;如果取and的话,就可以获得它们之间的相似程度。

而对于基于窗口的共现来说,其能够同时获得语法与语义的信息。下面我们通过一个例子来看一下基于窗口共现方式的词向量学习过程。

我们选取三句话:

  • I like deep learning.
  • I like NLP.
  • I enjoy flying.

窗口大小取为1,即向前看1一个词、向后看1个词,窗口中一共3个词。通过对共现次数的计数,可以得到以下的矩阵:

图片6

我们可以发现,这个矩阵有这样的几个问题。一是维度过高,它与整个vocabulary相关,因此维度也会随着词汇量的增加而增加;而是矩阵十分稀疏,这将导致难以训练出有效的模型。我们可以通过两种方法来降低词向量的维度:一是用数学方法对这个矩阵进行降维(如SVD奇异值分解);或是不通过这个矩阵,而是直接估计出词向量。

SVD奇异值分解

通过SVD分解,可以将一个mxn的矩阵分解为3个维度分别为rxn、rxr、mxr的矩阵。我们所需要的词向量信息都存储在第一个rxn的矩阵当中。第二个rxr的矩阵是一个对角矩阵,通过调整对角线上的数值可以对第一个rxn矩阵的列进行排序,从而让比较重要的维排在前面。

图片7

使用numpy可以很容易地进行SVD分解计算:

U, s, Vh = numpy.linalg.svd(X, full_matrices=False)

下图是取前两维生成的plot:

图片1

可以看出,相对相近的单词距离更近。

使用SVD方法时,可以进行一些hack,例如通过阈值或过滤的方法对停用词进行处理、添加权重、使用Pearson相关系数代替count等。

图片2

然而,SVD奇异值分解有一些弊端。例如,计算复杂度与m×n相关、难以加入新的单词等。最后,它与深度学习的审美不同:深度学习通常追求从某一个例子中学习一些东西然后再移动到下一个,而SVD方法却需要对所有语料进行整体地处理。

直接学习低维向量

除了利用SVD方法把高维矩阵降维处理外,还可以直接学习低维向量。例如word2vec,他直接预测每个单词相邻单词的概率。除了word2vec,2014年出现了Glove: Global Vectors for Word Representation. Pennington et al. (2014)。它们可以向语料库中不断添加新词。

word2vec的核心思想是:当窗口长度为c时,预测与中心词共现的单词。其目标函数为:

图片3

其中p为

图片4

然而当单词量增大后,其计算将会变得缓慢。因此,我们可以通过采取采样、简化概率函数等方式进行近似。

  基于频数的方法 直接预测方法
优势 训练速度快充分利用了统计信息

性能更好可以获得到比单词相似性更复杂的信息

劣势 主要用来获得单词之间的相似度当频数较少时,获得的比重不合适

与语料库的大小有关没有利用统计信息

 

Reference

http://cs224d.stanford.edu/