字符级机器翻译

最近利用神经网络的机器翻译很火,我认为NMT(Neural machine translation)能有所发展的原因有以下几点:

  1. 数据丰富,WMT15算是与ImageNet同样量级的数据,是训练大型神经网络所必须的。
  2. Bahdanau提出的Attention关系将机器翻译的性能推进一大步。
  3. 很明显能产生经济效益,市场巨大。
  4. 存在很多问题,即研究前景。毕竟相对CNN给图像识别带来的巨大提升,NMT的提升并不是很明显。

我针对的是其中的一个问题:规避大词典。原来都是先把一个数据集中所有单词找出来,把最常用的一些(如90%)做成一个大词典,显然这是冗余的,words和word完全没必要区分。动不动就是50K的单词表,非常耗内存,在像Czech这类语言上更加不行。关键是冗余不优雅。很多研究者都注意到这个问题:

  • subword,就是统计一下符号的频率,如“est”可能是一个符号,能组成“w est,b est”等词,因此称为subword。我觉得还是不够自然,而且效果并不是很好。
  • Hybrid Word-Character Models,相当于把未知的词训练成RNN小单元,据说华为很早就申请专利了。我表示,不能有word。
  • Junyoung Chung提出的不需要显式分隔的模型。提出bi-scale的RNN,我觉得很有意思,但我有个疑问,这跟base的RNN有什么区别?论文中也显示,确实差不多。我不知道为什么性能那么好。由于没有训练时间、训练所用内存等更多信息我无法作出判断。
  • 还有Wang Ling提出的,但是完全不是NMT,需要借助IBM model来对齐和分层训练,而且效果不好。

综上,利用RNN编码一个单词是比较合理自然的想法。可以说人人都能想到,关键是给出高效可行的实现。我实现了个高效纯字符级的机器翻译——Deep Character-Level Neural Machine Translation(DCNMT)。但是有个缺点,需要知道分隔符,也就是空格。不要太苛刻了,对于人来说,阅读“itisalsomoredifficultforhumantoreadwithoutthedelimiter”这种也是不方便的。而且对于中文日文这种没有分隔符的语言,没有必要使用大词典,直接上字符级,因为句子短啊,不存在训练难的问题。所以先将就着用吧。总得来说,DCNMT有几个优点:

  1. 所需训练循环周期比词级的少,在EN-FR上,只要遍历4次数据就差不多了,而词级大概要5次,这很容易get。但是因为更新速度慢一点,导致所花时间差不多。
  2. 内存用的不多。但还是很多,因为theano为了计算快,RNN的中间结果是缓存的,导致有5个RNN的DCNMT用了很多内存(跟词级的差不多)。但这容易解决,见chen的paper还有deepmind的一篇
  3. 能翻译错拼的单词,在论文中我只给出了几个例子,后续给出定量分析。我觉得这是一个diǎo点。

详见论文(An Efficient Character-Level Neural Machine Translation),我也不玩虚的,代码和训好的模型都在github上,反正我也没有毕业问题,管他能不能发呢。

总的架构看图:

我也很佩服自己,怎么能写出这么复杂结构的代码,写完之后改了3个bug(我太tm diǎo了)。多亏了巨人Bahdanau等写的好框架Blocksexamples。我的偶像啊!很高兴,他也star了我的实现。仔细看,有5个RNN子模型,其实跟bi-scale思想类似,先把组成词的字符用RNN编码后,只向上传最后的编码(相当与词级模型的embedding),而不是原来的全部(字符的embedding),因此能节约Encoder和Decoder的内存,也容易训练。 整个流程应该很清楚吧,不清楚可以看论文。。。

训练模型

被爱可可老师发到微博之后,关注的人一下子多了点,有点诚惶诚恐。我觉得很多哥们会在训练的时候遇到问题。如有哥们遇到数据集问题,有哥们遇到版本问题(TypeError: __init__() got an unexpected keyword argument ‘children’)。这是我写这篇博客的原因,我希望能实现更好的实用的模型。几个注意点:

  1. 必须先手动下载对应的数据啊,就在wmt15上,还可能要对validation set和test set做一些处理。可以先选数据量小如en-fi的测试测试,一测就是1周。然后就方便了运行Github仓库中的train.sh就行了。
  2. 务必保持库的更新啊,Blocks更新还算快的,API随时改。我会尽量与最新保持兼容,而不兼顾老版本。
  3. 如果还有问题,请在评论中提问。

测试模型

我训练了几个模型,由于机器和时间受限,没来得及训练其他模型,详见论文github。我希望有人能帮忙训练更深的模型。我不知道这个模型的上限是多少。

如果对机器翻译不敢兴趣,也可以从中学点什么。这个代码中,用了GRU,stacked GRU,stacked Bidirectional GRU以及GRU的变种,关于RNN的几乎的用到了(苦笑)。还有关键的Attention,虽然有点复杂。

欢迎提问,以及改善这个模型。机器翻译很有意义,所以想能做点什么。

 

 

继续阅读

RNN建模时间序列

RNN建模时间序列

RNN简介

下图是最简单的RNN。 x 为输入序列,我们需要将他展开为 x_0, x_1, ... x_t,因为实际应用中序列是有限长的。展开的过程即下图的左边到右边。


RNN

图中 s_t 为隐含层,可以认为是记忆单元,即 s_t 概括了 x_0x_{t-1} 的信息,利用 x_t, s_t 可以预测输出 o_t. 训练时需要使用o_t 与真实的输出做比较,即产生一个误差,最小化这个误差就是对这个RNN的训练过程。具体可以参考网友的介绍
可以用数学公式来描述这个过程。

    \[s_t=f(Ux_t + Ws_{t-1})\]

    \[o_t = \mathrm{softmax}(Vs_t)\]

    \[cost = \sum_t f_{err}(o_t, \hat o_t)\]

其中f 为激活函数,可以是sigmoid或者tanh等其他类型的函数。Wiki上有详细的介绍。f_{err} 可以是Cross entropy(分类常用的误差函数),也可以是简单的RMSE,根据不同的情况选择不同的误差函数,只要可导(可次导)就行。

开导的目标函数就可以使用一些库的自动求导功能进行求解。如Theano可以直接进行符号求导,可以节省很多代码以及bug。

LSTM原理

RNN有个致命的缺点就是对长序列的建模效果不好,可以认为RNN记忆单元不行。因此 Hochreiter & Schmidhuber (1997) 提出了新的模型LSTM(Long short-term memory), 如下图.


enter image description here

网上有很多资源对其进行了详细的描述:

  1. Understanding LSTM Networks
  2. Implementing a GRU/LSTM RNN with Python and Theano

我简单说下, LSTM的单个单元的操作如下:

    \begin{align*} i &=\sigma(x_tU^i + s_{t-1} W^i)\\ f &=\sigma(x_t U^f +s_{t-1} W^f) \\ o &=\sigma(x_t U^o + s_{t-1} W^o) \\ g &=\tanh(x_t U^g + s_{t-1}W^g) \\ c_t &= c_{t-1} \circ f + g \circ i \\ s_t &=\tanh(c_t) \circ o \end{align*}

同样这复杂的操作通过程序的自动求导就很简单,可以看这个例子

基本与RNN类似,增加了记忆单元 c 和遗忘门f。 原理就是在RNN的基础上,利用记忆单元来更好的对长序列进行概括(记忆)。

除LSTM还有很多变种,如GRU, LSTM with peephole connections等,这篇文章做了一些比较。

RNN应用

RNN主要用于序列建模,有几种模型,如下图。


enter image description here


时间序列建模

这是别的实验室一个项目的测试,数据集不好放出来,而且由于数据实在太少,效果比较一般,他目的是根据已有的数据,预测下一周的cpu busy和cpu context switches。由于是预测未来,我们需要对过去进行总结。RNN就是做这样一件事情:对过去出现过的模式进行概括记忆,看看未来会不会再次出现并预测。问题就是怎么通过RNN预测什么。

模型

在我实现的模型中,我利用0分钟到n分的数据 [x_0, x_1, ... x_n] 预测下一个时间段的数据如 [x_s, x_{s+1},...x_{s+n}], 是一个many to many的模型。在我测试的模型中,我选取n=288 即一整天的数据,s=1 即下一个5分钟。可以表示为:
目标: [x_1, x_2, x_3, ..., x_{1+n}]
输入: [x_0, x_1, x_2, ... , x_n]
但这样的模型在实际应用中是不行的,每次输入只有一个数据点,在测试时会导致很大的偏差。我采取的办法是将m 个时间点叠加,将输入变为

    \begin{align*} x_0, \quad x_{36}, \quad x_{72}, .... \\ x_1, \quad x_{37}, \quad x_{73}, .... \\ x_2, \quad x_{38}, \quad x_{74}, ... \\ ..., \quad ..., \quad ....\\ x_{m}, \quad x_{m+36},x_{m+72} \end{align*}

注意纵向为特征,即 x_0, x_1, ..x_{m} 为一个特征。36的间隔也可以选择合适的,我随便选了一个。
对应输出就变为m 长的向量(m 为 feature_length),也可以输出一个单一的预测值 x_{m+1}。我认为在测试时,不知道未来数据的情况下,使用向量更合理。如下:

    \begin{align*} x_1, \quad x_{37}, \quad x_{73}, .... \\ x_2, \quad x_{38}, \quad x_{74}, ....\\ x_3, \quad x_{39}, \quad x_{75}, ...\\ ..., \quad ..., \quad ....\\ x_{m+1}, \quad x_{m+37},x_{m+73} \end{align*}

简单的说,就是单步我要从[x_0, x_1, x_2, ... , x_m] 预测 [x_1, x_2, x_3, ..., x_{1+m}],注意第一个模型的不同之处。我训练时我一次输入几组就是seq_length。
feature_length 越长就越可以防止抖动,但是对局部细节刻画就比较难。
seq_length越长记忆的越多,可能导致过拟合,也会导致训练的困难以及数据量太小了。太短抓不住特征。

实验平台

  • 操作系统:Linux
  • 深度学习库:Theano + Blocks, 可以使用以下命令安装

pip install git+git://github.com/mila-udem/blocks.git \
-r https://raw.githubusercontent.com/mila-udem/blocks/master/requirements.txt

实验效果

在cpu context switches表现较好。我选取CPU1, CPU7, CPU8进行测试。其实都差不多, 需要调参,没有足够时间。第7周数据在训练的时候是不用的,只用前5周数据量还是太小。我用第6周的数据预测第7周。下图中蓝线代表真实数据,绿色部分是用第六周的数据一个个预测但使用真实值代替下次输入的预测值。红色部分完全使用预测值。

CPU Context Switches

CPU7: rmse: 0.06

Screenshot_20160526_232717

CPU Busy

CPU7: rmse: 0.148

Screenshot_20160526_232739
 

继续阅读

微信聊天记录分析

解密聊天记录数据库


微信6.2.5使用sqlcipher进行AES加密,因此我们要得到密钥,根据编译的信息,可以得知微信使用 key=md5(IMEI+uin) | cut -c -7 , 即取md5的前7位做为密钥。解密微信聊天数据库就是简单的一行代码,(注意sqlcipher新版本(3.x)默认不向下兼容,需要使用,cipher_use_hmac 是兼容1.1.x,kdf_iter 是兼容2.1.x的)。

IMEI很容易获取,uin在shared_prefs/多个文件中存在,如com.tencent.mm_preferences.xml,auth_info_key_prefs.xml, system_config_prefs.xml。理论上是在system_config_prefs.xml文件中的default_uin,注意有可能是负的,之前我没有意识到这个问题,导致一直解码不成功,直到看了这个博客。ps. 负数是因为溢出 int32(2639833126) = -1655134170 。

解密曾经登录过的帐号


网上的解密聊天记录都是以登录帐号为基础的,直到我阴差阳错发现这个牛逼的微信聊天记录导出应用。重点不是在他能导出,而是他能导出之前登录过的帐号的聊天记录。仔细的思考一下,一旦有过登录,微信就会生成一个32位长的用户文件目录如 da60995c77c8cd8b47f69cc38e7a52cc ,一看就知道是个md5的hash。根据测试,在不同的机子上这个文件夹名是不变的,也就是说只跟微信ID(wx_user_name, uin…)有关,所以是跟微信哪个id是一一映射的? 感觉还是跟uin有关。

分析那个应用的包网络通信,发现他跟服务器通信只用了文件目录名如 da60995c77c8cd8b47f69cc38e7a52cc ,所以可以肯定能够通过目录名逆推uin。我尝试了不同的组合 wx_uin,wechat_uin... ,都不对。看来只能反编译。

反编译

直觉上来说,反编译微信的难度太大。还是反编译那个聊天记录导出应用好了。写应用的那哥们还是比较专业的,都做了加密和混淆,而且貌似是手动的,导致里面的字符串都难以识别。经过努力,还是破解了那哥们的加密方式,看得懂应用源码中的字符串就事半功倍,不到1小时就发现原来

TM就是前面加了”mm”。注意 uin=-1655134170 是负的。。至此,就能够逆推uin,也就是说你手机丢了,别人还是能够破解你的微信聊天记录,因为uin是int啊,找md5不要太快!

聊天记录整理


这方面已经很人做了,比如github上的wechat-dump,效果还是可以的,稍微有点问题,日后再改

日后改了一些东西,最重要的是微信的头像文件不再单一保存,而是用 avatar.index 来索引,保存在一个大文件中avatar.block.0000x。经测试,可以得知用户头像以avatar.index中的数值为起始位置,找到avatar.block.0000x相应连续的96×96×3×4个连续字节就算用户头像的bitmap(png.bm)。具体见代码

 

 

国庆期间,别人在玩,我在写代码。这波不亏

 

参考


继续阅读