卷积神经网络

卷积神经网络(Convolutional Neural Networks:CNN)是人工神经网络(ANN)的一种,是深度学习的一种学习算法。它在图像识别和分类、自然语言处理广告系统中都有应用。

有意思是,卷积神经网络的提出其实就是来自于生物视觉模型。1981年的诺贝尔医学奖,颁发给了David Hubel、Torsten Wiesel。他们的工作给人们呈现了视觉系统是如何将来自外界的视觉信号传递到视皮层,并通过一系列处理过程(包括边界检测、运动检测、立体深度检测和颜色检测),最后在大脑中构建出一幅视觉图像。这个发现激发了人们对于神经系统的进一步思考,神经-中枢-大脑的工作过程,或许是一个不断迭代、不断抽象的过程。如下图所示,从原始信号摄入开始(瞳孔摄入像素Pixels),首先进行初步处理(大脑皮层某些细胞发现边缘和方向),抽象(大脑判定眼前的物体的形状是圆形的),然后进一步抽象(大脑进一步判定该物体是只气球)。

convolutional deep belief network

六十年代的生理学的发现,促成了计算机人工智能在四十年后的突破性发展。1989年,Yann LeCun (纽约大学教授,现Facebook AI研究室主任) 提出了卷积神经网络,这是第一个真正成功训练多层网络结构的学习算法,但在当时的计算能力下效果欠佳。直到2006年,Geoffrey Hinton提出基于深信度网(Deep Belief Net)和限制波尔兹曼机(Restricted Boltzmann Machine)的学习算法,重新点燃了人工智能领域对于神经网络的热情。

卷积神经网络现在计算机视觉领域表现出众。ImageNet Classification with Deep Convolutional Neural Networks,这篇发表于NIPS2012的文章,是Hinton与其学生为了回应别人对于Deep Learning的质疑而将CNN结合GPU并行技术用于Imagenet Challenge(图像识别目前最大的数据库,被誉为计算机视觉圣杯),最终取得了非常惊人的结果。他们的算法在2012年取得世界最好结果,使分类错误率从26.2%下降到16%。2013年Matthew Zeiler的算法继续将错误率下降到11.2%。Matthew Zeiler还创立了Clarifai,让我们可以有机会使用他们的图像识别算法对图片标注分类或图像搜索。

imageNet classification with CNN
The convnet from Krizhevsky et al.'s NIPS 2012 ImageNet classification paper.

在月初Kaggle结束的Galaxy Zoo challenge中,参赛者要对星系图像进行分类(Spiral/Elliptical, Merging/Not merging, Clockwise/Anti-clockwise),获胜的算法也是使用了卷积神经网络。Sander Dieleman已放出了代码和详尽的文档: My solution for the Galaxy Zoo challenge

2014年3月,Facebook刚刚公布了他们在CVPR2014的文章:DeepFace: Closing the Gap to Human-Level Performance in Face Verification。他们用四百万人脸图片训练了一个九层的卷积神经网络来获得脸部特征,神经网络处理的参数高达1.2亿。他们在著名的公共测试数据集LFW(labeled face in the wild,1:1地判断是否两个照片是一个人)上达到了97.25%的正确率。这个数字已经基本接近人眼的辨识水平。北京Face++团队的算法达到97.27%的正确率,在美图秀秀中就有应用,他们的主页提供了API、demo展示和论文。现在的最新进展是,香港中文大学基于 Fisher Discriminant Analysis的算法将Face Verification正确率提高到98.52%,超过了人类水平(97.53%)。

faceplusplus system overview
System overview in Face++ paper in ICCV2013

除了计算机视觉领域,卷积神经网络在人工智能和robotics也有很大潜力。Hinton的另外一个学生创立了人工智能公司DeepMind,没有商业产品,只凭一篇论文,就已被Google招聘式收购。 他们使用深度学习(CNN)结合强化学习(Reinforcement Learning),在Stella模拟机上让机器自己玩了7个Atari 2600的游戏,结果不仅战胜了其他机器人,甚至在其中3个游戏中超越了人类游戏专家。很有意思,具体可以见InfoQ的看DeepMind如何用Reinforcement learning玩游戏,以及论文原文Playing Atari with Deep Reinforcement Learning

2014年公开课计划

整个寒假都没有可以跟的课,老外果然都过圣诞节去了。新的一年有三门课非常给力:Convex Optimization、Statistical Learning和Networks, Crowds and Markets。

Convex Optimization的老师是经典教材《Convex Optimization》的作者Stephen Boyd。

Statistical Learning,老师是Trevor Hastie和Rob Tibshirani,俩人都是大名鼎鼎的《The Elements of Statistical Learning》、《An Introduction to Statistical Learning, with Applications in R》作者之一。《The Elements of Statistical Learning》的另一个作者Jerome Friedman发明了Gradient Boosting。

edX上Networks, Crowds and Markets在3月3日开课,这门课的老师也很强大:Cornell的Jon Kleinberg, David Easley, Eva Tardos。Jon Kleinberg是社交网络研究的神牛,2013年还拿了ACM SIGKDD 2013 Innovation Award。David Easley和Jon Kleinberg合著了《Networks, Crowds and Markets》;Eva Tardos和Jon Kleinberg合著了《Algorithm Design》的作者。这两本都是我比较喜欢的教材。《Networks, Crowds and Markets》之前读到一半,正好这次可以跟着课把书读完。

椭圆曲线和Dual_EC_DRBG后门

这两天爆出NSA收买RSA将NSA推荐的算法,Dual_EC_DRBG,设置为BSafe中默认的随机数生成算法。为了推广这种算法,其实早在2007年NSA就执意将其写入了NIST(美国国家标准技术管理委员会)的确定性随机数生成器推荐标准(Special Publication 800-90,SP800-90),即使它速度极慢。同年Dual_EC_DRBG就在Crypto 2007会议上被指出存在被植入后门的可能,但不能认定算法设计者是否知道后门的参数,也不能认定NIST有意在算法中植入后门。2013年9月Edward Snowden泄漏的内部备忘录显示NSA曾向某加密算法植入后门,再到12月路透社爆出RSA被收买,现在看起来是NSA精心选取参数值下后门。有意思的是,比特币也使用了ECC来生成随机数,但是比特币神秘创始人中本聪在2009年发明比特币的时采用了小众的secp256k1的曲线参数而不是有问题的secp256r1(NIST P-256),神奇地躲过了密码学子弹。
那么Dual_EC_DRBG漏洞在哪,为什么随机数生成器的漏洞会让加密算法被攻破?先要从椭圆曲线和随机数生成器说起。

椭圆曲线
椭圆曲线密码学(Elliptic curve cryptography,ECC)由Koblitz和Miller分别独立提出,是迄今为止安全性最高的一种公钥密码算法。椭圆曲线E的形式是:

y^2=x^3+ax+b, a,b \in F_p

有限域Fq,q一般是2的m次方或大素数p,也可以是某素数p的m次方。参数a,b确定椭圆曲线E。
它的安全性基于有限域椭圆曲线离散对数问题(Elliptic Curve Discrete Logarithm Problem,ECDLP)的难解性:
给定素数p和椭圆曲线E,对Q=dG,在已知G,Q的情况下求出小于p的正整数d。可以证明由d和G计算Q容易,而由Q和G计算d则是指数级的难度。
G对应为椭圆曲线E的基点,d为私钥由自己选择,然后生成对应公钥Q=dG,得到密钥对(d, Q),私钥自己保存,(p, a, b, G, Q)是已知的,但是由p和G计算私钥d很难,保证了加密算法的强度。
还有2种公钥密码体制分别基于大整数分解问题(Integer Factorization Problem,IFP)的难解性,如RSA,和有限域离散对数问题(Discrete Logarithm Problem,DLP)的难解性,如Diffie-Hellman、ElGamal。但是ECC问题要比DLP问题更难解,并且ECC用更少的密钥长度提供相同的加密强度。
这次出问题的Dual_EC_DRBG,全称Dual Elliptic Curve Deterministic Random Bit Generation,是基于椭圆曲线的确定性随机数生成器。

随机数生成器
随机数在密码学中具有十分重要的地位,被广泛用于密钥产生、初始化向量、时间戳、认证挑战码、密钥协商、大素数产生等等方面。随机数产生器用于产生随机数,分为非确定性随机数生成器和确定性随机数生成器两类:
非确定性随机数生成器(NRBG)基于完全不可预测的物理过程。确定性随机数生成器(伪随机数生成器,DRBG)在指定初始种子之后,利用某些算法产生一个确定的比特序列,“确定性”因此得名。如果种子是保密的而且算法设计得很完善,那么可以认为输出的比特序列是不可预测的。
加密算法需要高度随机性的“种子”来生成密钥,因此随机数生成器会直接影响加密强度和安全性,脆弱的随机数生成器被攻破会击溃整个加密算法,比如Android随机生成数字串安全密钥中的漏洞就导致了部分比特币的失窃。

Dual_EC_DRBG后门
这个后门的发现可以追溯到六年前,NIST在2007年发布了确定性随机数产生器推荐标准SP800-90修订版。这是一个推荐性的标准,描述了一些产生随机比特流的方法,这些随机比特流可能被用于直接或者间接的产生随机数,并用于相关使用密码学的应用中。NIST SP800-90提供了4种标准算法:Hash_DRBG(基于SHA系列算法)、HMAC_DRBG(基于HMAC函数)、CTR_DRBG(基于分组密码函数AES)、Dual_EC_DRBG(基于椭圆曲线)。
在4个月后的Crypto 2007会议上,Dan Shumow和Niels Fergusonsuo作了一个报告,宣称标准中的Dual_EC_DRBG设计存在严重漏洞,具体可以参看报告On the Possibility of a Back Door in the NIST SP800-90 Dual Ec Prng...智商不够用了,我的理解是:
P, Q是ECC上两个基点,且满足eQ=P,点Q常量可以确定万能钥匙。如果攻击者知道私钥d满足Q=dP,计算eQ=P是容易的,存在a*e=1 mod p。反过来如果攻击者知道e,以及一些已知的随机值,攻击者可以计算出点G,然后可能能确定DRBG的内部状态,并预测DRBG后来的输出。一个“局外人”可能并不知道这种特殊关系的存在,但是如果知道了P和Q之间关系的“密钥”,攻击者可以利用Dual_EC_DRBG存在的后门得到该算法后续所有的随机数值,从而破坏不可预测的性质,预测其使用的密钥,进而攻破整个加密算法。

DES S-BOX的传说
DES中S盒来路不明是密码学届的一个著名的谜团,也和NSA有关。1975,IBM刚搞出DES(Data Encryption Standard)时候,NSA就对S-Box做了修改,并将密钥长度由128bit缩减为56bit,但未说明原因,直到80年代差分分析被公开学术界发现后,人们发现针对DES16轮的差分攻击效率甚至不如穷举,于是怀疑在设计DES的S盒和加密轮数时,差分攻击的方法就已经被发现了,而NSA那个修改证明是为了对抗可能的差分分析。

神经网络与数据压缩

神经网络除了用于Regreesion和Classification,还可以与用于数据压缩Data Compression。自联想神经网络Auto-Associative Neural Network是三层BP网络,它的特点是输出是对输入的一种重构,即输出等于输入或者允许输入输出有一定的误差存在。如果中间层Hidden Layer节点少于输入层Input Layer,中间层可以用更少节点表示输入层的数据同时可以在输出层重构出输入层数据,这就是数据压缩和解压的过程。

从另一个角度来看,中间层提取出数据中最重要的特征,用更少维度表示输入数据。如果我们在网络中不使用sigmoid函数,而使用线性函数,这就是主成分分析PCA模型。

在深度学习中,上述结构被称作自编码神经网络Autoencoder Neural Network。

PhantomJS+CasperJS备份微博

备份微博通常调用新浪微博提供的API就可以了,但是我并不关注文本数据,更需要得到一条微博原原本本的显示内容,就像archive.org对网站进行备份一样,可以将微博截图快照下来。

对于网页快照,可以使用PhantomJS进行截图。PhantomJS是一个支持JavaScript API的无界面、运行于服务端的WebKit环境(Headless WebKit with JavaScript API),Headless这里的意思是渲染页面在后台完成。PhantomJS可以用来进行前端自动化测试、网络状况监控、网页渲染后自动截图等。但是微博快照和网页快照不同,微博快照在网页渲染后,只是截取页面上指定的区域(DOM),依赖于PhantomJS的CasperJS提供了更强大的函数封装、方法和语法糖,可以完成定义排序浏览器导航步骤、填充提交表单、点击跟踪链接、指定DOM元素区域截图等任务,当然也可以实现备份微博。

首先使用CasperJS模拟用户登陆微博过程,填写用户名密码并提交表单。

var casper = require("casper").create();
casper.start('http://www.weibo.com/login.php', function() {
    this.fill('div[class="W_login"]', {'loginname':'YOURUSERNAME'}, false);
    this.fill('div[class="W_login"]', {'password':'YOURPASSWORD'}, false);
    this.click('a[class="W_btn_d"]');
});

用CasperJS给页面上指定的区域(DOM)截图非常简单:调用captureSelector,给页面中'.WB_feed_type'选择器匹配的元素截图,输出的文件名为微博的mid号。

casper.thenOpen('http://weibo.com/u/UID',function() {
    mid=this.getElementAttribute(".WB_feed_type", "mid");
    this.captureSelector(mid+'.png',".WB_feed_type");
});

最后获得的微博截图效果如下,加入cron定时任务就能自动备份。现在个人微博首页只显示5条最新微博,可以每次将5条微博全部备份,同时设定合理的更新间隔时间,可以避免只备份最新微博但是在更新间隔时间里新增了多条微博的问题。类似的,稍加改动还可以应用于备份twitter豆瓣的timeline。

weibo_capture

close