2015年8月12日星期三

当心Intel® Management Engine埋下openssl的雷

Intel的电脑经常会默认安装一个叫做Intel® Management Engine的软件。这个东西会导致严重的安全漏洞,甚至让很多程序无法运行。

举个例子,我今天自己在windows下编译了一个curl然后运行,发现出错了。报告

curl.exe - Ordinal Not Found
The ordinal 385 could not be located in the dynamic link library C:\os\curl-7.43.0\builds\libcurl-vc14-x64-release-static-ssl-dll-zlib-dll-sspi\bin\curl.exe.

后来我用depends.exe发现,它引用了c:\program files (x86)\intel\icls client\LIBEAY32.DLL这个文件。

而icls client是Intel® Management Engine的一部分,它安装后会把自己加到PATH环境变量中,它还带了两个openssl的dll。这种软件几百年都不会更新一次,想想去年openssl的heart bleed bug。 所以,赶紧,我建议,卸载这个破软件了事。

2015年8月11日星期二

Reduce, Broadcast and AllReduce

在做机器学习的时候,经常要做这样一个操作:每台机器计算出一个vector,然后把这些vector汇总加起来,再广播回去

传统模式

如下面这组图所示:

1.png

2.png

3.png

4.png

总体来说,它可以分为两步:

  1. Reduce。 即map-reduce中的那个reduce。
  2. Broadcast。 把reduce的结果broadcast到所有节点。

直接以这样两步走的方式解决此问题会很低效。如果vector长度很大,那么负责汇聚的那个节点,就会成为性能瓶颈。

树状模式

于是就有了基于tree的map-reduce来解决这个问题。这种方式被广泛用在了Vowpal Wabbit和spark中。

tree1.png

tree2.png

tree3.png

broadcast的过程与reduce的过程类似,我就不画了。

下面举个例子分析下它需要花多少时间。 假设我们有75台机器,采用5叉树的方式来汇聚。那么需要5层。 第一层75台机器。 第二层15台机器。 第三层3台机器。 第四层1台机器。

假设每个Vector的大小是1GB,而带宽是10Gb/s,那么reduce阶段至少需要(5+5+3)*8/10=10秒才能传输完。

采用上一种方案,reduce需要75*1*8/10=60秒。相比之下有很大的改进。

All to All 模式

All to All的模式是每台机器和每台机器都得建立一个连接。

初始状态是这样:

  value1 value2 value3 value4
机器1 1 3 2 1
机器2 2 5 4 5
机器3 8 10 9 7
机器4 6 2 3 6

然后,第i行的数据都汇总到第i%n台机器上。(n为机器数)
如下表所示。红色的代表新修改的值。

  value1 value2 value3 value4
机器1 17 3 2 1
机器2 2 20 4 5
机器3 8 10 18 7
机器4 6 2 3 19

然后broadcast出去

  value1 value2 value3 value4
机器1 17 20 18 19
机器2 17 20 18 19
机器3 17 20 18 19
机器4 17 20 18 19

然后还是按上面的例子算下时间。可以发现,网络开销和机器数量无关。每台机器都需要传输大约2GB*(1-1/n)的数据出去,接收1GB * (1-1/n)的数据进来。所以,大约2秒就可以完成。

汇总比较一下:

  所需时间
传统方法 60秒*2
Tree 10秒*2
All to All 2秒

结合实际

Yahoo的vowpal wabbit是率先把tree allreduce与hadoop结合起来。

spark在reduce阶段提供了tree的模式,实现方法是通过多轮的map-reduce。在broadcast阶段,它默认采用bittorrent的方式做broadcast,这也算是一大创举吧

2015年7月11日星期六

L1-regularized logistic regression

先挖个坑吧,以后慢慢填。

刚读到台大几个学生写的一篇关于L1-regularized logistic regression(L1LR)综述性的论文:“A Comparison of Optimization Methods and Software for Large-scale L1-regularized Linear Classification”。使我很受益,他们把各种思路和方法都罗列了出来,使得我可以按图索骥,一一尝试。不至于自己独自瞎忙活。所以我先挖个坑,逐渐的慢慢更新。

关于问题的背景请参考我的Logistic Regression笔记。我认为L1-regularized logistic regression的核心是如何对一个非平滑(non-smooth)的非线性凸函数求最小值的问题。这在数学上是一个很广的topic,够写厚厚一本书了。我在此试图以L1LR为例探一探路。

关于subgradient与BFGS的关系,在这篇A Quasi-Newton Approach to Nonsmooth Convex Optimization Problems in Machine Learning 论文中讲的比较好。

Boyd的插值法

http://stanford.edu/~boyd/l1_logreg/

论文: An Interior-Point Method for Large-Scale `1-Regularized Logistic Regression

Glmnet

论文: Regularization paths for generalized linear models via coordinate descent . Jerome H. Friedman, Trevor Hastie, and Robert Tibshirani. Journal of Statistical Software, 33(1):1–22, 2010.

L-BFGS-B

这是一个比较经典的算法了,也可以用在这个问题上。

OWLQN

论文: OrthantWise Limited-memory Quasi-Newton "Scalable Training of L1-Regularized Log-Linear Models(2007)"

视频:

Scalable Training of L1-regularized Log-linear Models

OWL-QN主要的改动有这么几点:

1、 梯度在传递给BFGS用之前,要转换成pseudo gradient。

2、 在计算方向的时候,算出的\(H_k∇f_k\)要用\(∇f_k\)修正,sign不同就要取0。
下面的代码中dir是\(-H_k∇f_k\), g是\(∇f_k\)。\(∇f_k\)是pseudo gradient

    private static void constrainSearchDir(double[] dir, double[] g) {
          for (int i = 0; i != g.length; ++i) {
                if (dir[i] * g[i] >= 0.0) {
                       dir[i] = 0.0;
                }
          }
    }

3、 计算出的newX也需要做投影。根据旧的x求newX的规则是

newX[i]=x[i] + step * dir[i];  
newX[i]=newX[i]*((x[i] == 0.0) ? -grad[i] : x[i])>0?newX[i]:0;  

4、 LBFGS中用来计算逆Hessian矩阵的y(i)(即\(\Delta g\)),用的是未修正的梯度。不是那个pseudo gradient,而是OWLQN修正之前的那个梯度!

关于OWL-QN的一些思考

OWL-QN所选择的pseudo gradient其实是f(x)的所有subgradient中最靠近0的一个(范数最小的一个)。

计算逆Hessian矩阵的y(i)之所以用未修正的梯度是因为|x|的二阶导数等于0(当x不等于0)。

另外,论文中未提及,但是实践中发现,OWLQN会break wolfe condition。所以line search的算法只能用backtracking,又因为初始步长是1,所以每次算出来的step必然是<=1的。

OWLQN的 实现

下面罗列一下我所看见的OWLQN的实现(共计4个),并做一下比较

C/C++:

  1. 论文的原始作者提供了demo代码,发布在research.microsoft.com上。它没有检查curvature condition,它使用αp来计算充分下降条件。

  2. libLBFGS 作者是一个日本人Naoaki Okazaki,任教于日本东北大学。 可以说是他首先把OWLQN的坑都踩了一遍。他是首个指出OWLQN不能和MoreThuente一维搜索算法一起用。他没有检查curvature condition,他使用 Δx 来判断充分下降条件.

Java:
stanfordnlp 中也有 OWLQN 的实现。 stanfordnlp顾名思义,是由Stanford NLP group开发并维护的一个机器学习库。它没有检查curvature condition,它使用 Δx 来判断充分下降条件。它每次循环会检查\(y \cdot s > 0 \) 来维护H正定。

Scala:
breeze 我感觉这个库基本上是从stanfordnlp衍生过来的。 It enforces Wolfe and strong Wolfe conditions,所以我很怀疑它实际中是否真的可用,但是实际上spark mllib就是用的它的实现。它使用 αp 来判断充分下降条件。

但是作者又在注释中写到 “Technically speaking, this is not quite right. dir should be (newX - state.x) according to the paper and the author. However, in practice, this seems fine. And interestingly the MSR reference implementation does the same thing (but they don't do wolfe condition checks.).”

参考

Optimization Methods for l1-Regularization Mark Schmidt,2009
A comparison of numerical optimizers for logistic regression Thomas P. Minka October 22, 2003
我的BFGS的笔记
我的Logistic Regression笔记

2015年6月23日星期二

java处理大数组真是让人头疼

我在spark中创建了一个长度为10亿,类型为double[]的accumlator。结果,发现函数send不出去,driver无法把这个函数send给worker

15/06/23 04:57:52 ERROR yarn.ApplicationMaster: User class threw exception: java.lang.OutOfMemoryError: Requested array size exceeds VM limit
java.lang.OutOfMemoryError: Requested array size exceeds VM limit
  at java.util.Arrays.copyOf(Arrays.java:2271)
  at java.io.ByteArrayOutputStream.grow(ByteArrayOutputStream.java:113)
  at java.io.ByteArrayOutputStream.ensureCapacity(ByteArrayOutputStream.java:93)
  at java.io.ByteArrayOutputStream.write(ByteArrayOutputStream.java:140)
  at java.io.ObjectOutputStream¥BlockDataOutputStream.drain(ObjectOutputStream.java:1870)
  at java.io.ObjectOutputStream¥BlockDataOutputStream.setBlockDataMode(ObjectOutputStream.java:1779)
  at java.io.ObjectOutputStream.writeObject0(ObjectOutputStream.java:1186)
  at java.io.ObjectOutputStream.writeObject(ObjectOutputStream.java:347)
  at org.apache.spark.serializer.JavaSerializationStream.writeObject(JavaSerializer.scala:44)
  at org.apache.spark.serializer.JavaSerializerInstance.serialize(JavaSerializer.scala:81)
  at org.apache.spark.util.ClosureCleaner¥.ensureSerializable(ClosureCleaner.scala:312)
  at org.apache.spark.util.ClosureCleaner¥.org¥apache¥spark¥util¥ClosureCleaner¥¥clean(ClosureCleaner.scala:305)
  at org.apache.spark.util.ClosureCleaner¥.clean(ClosureCleaner.scala:132)
  at org.apache.spark.SparkContext.clean(SparkContext.scala:1891)
  at org.apache.spark.rdd.RDD¥¥anonfun¥mapPartitions¥1.apply(RDD.scala:683)
  at org.apache.spark.rdd.RDD¥¥anonfun¥mapPartitions¥1.apply(RDD.scala:682)
  at org.apache.spark.rdd.RDDOperationScope¥.withScope(RDDOperationScope.scala:148)
  at org.apache.spark.rdd.RDDOperationScope¥.withScope(RDDOperationScope.scala:109)
  at org.apache.spark.rdd.RDD.withScope(RDD.scala:286)
  at org.apache.spark.rdd.RDD.mapPartitions(RDD.scala:682)
  at org.apache.spark.api.java.JavaRDDLike¥class.mapPartitionsToDouble(JavaRDDLike.scala:177)
  at org.apache.spark.api.java.AbstractJavaRDDLike.mapPartitionsToDouble(JavaRDDLike.scala:47)
  at com.sunchangming.MyLogisticObjectiveFunction.calculateImpl1(MyLogisticObjectiveFunction.java:159)
  at com.sunchangming.MyLogisticObjectiveFunction.calculate(MyLogisticObjectiveFunction.java:42)
  at com.sunchangming.MyQNMinimizer.minimize(MyQNMinimizer.java:453)
  at com.sunchangming.JavaLR.main(JavaLR.java:219)
  at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
  at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:57)
  at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
  at java.lang.reflect.Method.invoke(Method.java:606)
  at org.apache.spark.deploy.yarn.ApplicationMaster¥¥anon¥2.run(ApplicationMaster.scala:483)

后来我想了一个取巧的办法,把这个accumlator的初始值为null,于是send出去了,但是处理完之后driver收不回来,还是同样的错误。

15/06/23 05:54:55 ERROR executor.Executor: Exception in task 1319.0 in stage 1.0 (TID 1458)
java.lang.OutOfMemoryError: Requested array size exceeds VM limit
   at java.util.Arrays.copyOf(Arrays.java:2271)
   at java.io.ByteArrayOutputStream.grow(ByteArrayOutputStream.java:113)
   at java.io.ByteArrayOutputStream.ensureCapacity(ByteArrayOutputStream.java:93)
   at java.io.ByteArrayOutputStream.write(ByteArrayOutputStream.java:140)
   at java.io.ObjectOutputStream$BlockDataOutputStream.drain(ObjectOutputStream.java:1870)
   at java.io.ObjectOutputStream$BlockDataOutputStream.setBlockDataMode(ObjectOutputStream.java:1779)
   at java.io.ObjectOutputStream.writeObject0(ObjectOutputStream.java:1186)
   at java.io.ObjectOutputStream.writeObject(ObjectOutputStream.java:347)
   at org.apache.spark.serializer.JavaSerializationStream.writeObject(JavaSerializer.scala:44)
   at org.apache.spark.serializer.JavaSerializerInstance.serialize(JavaSerializer.scala:81)
   at org.apache.spark.executor.Executor$TaskRunner.run(Executor.scala:252)
   at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1145)
   at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:615)
   at java.lang.Thread.run(Thread.java:724)

对应的代码如下:
Executor:run():
  val accumUpdates = Accumulators.values
  val directResult = new DirectTaskResult(valueBytes, accumUpdates, task.metrics.orNull)
  val serializedDirectResult = ser.serialize(directResult)

无奈了。

2015年6月22日星期一

关于win 10升级的一些....

呃,最近媒体上关于win 10如何免费升级的消息满天飞,我不知道我周围有多少人关心这个,也不知道哪些可以讲哪些不能讲……

先放些图吧。

这是我在win 8.1上收到的升级通知

只有家庭版和专业版才会接到这样的升级通知,企业版不会。

它主要有这样两点考虑:

  1. 企业版有单独的销售策略,企业版并不能免费升级。企业版要想升级到win 10,企业是要因此而花钱的(可能已经以年费的方式掏过了)
  2. 企业内不应该允许个人随便升级操作系统。企业应该有自己的版本管理策略,由企业自己决定什么时候升,怎么升。

理论来说,只有正版才能升级,盗版不能升级。 因为升级的过程中要连接微软的服务器进行激活。

然后高潮来了。360/qq版的win 10是怎么回事。

  1. 会不会有删不掉的内置应用?
    360/qq版的win 10是这两个公司委托微软做的一个特别版。安装文件是微软做的,带有微软的数字签名,装完后里面不会有删不掉的东西。不像Android,定制版总是搞一些卸不掉的应用。

  2. 盗版能激活吗?
    不能。微软并没有提供key给360/qq。安装过程中所连接的激活服务器,依然是微软的服务器。

另外,安装360/qq定制版的过程中遇到任何问题,微软不管,由这两家中国公司负责技术支持。

所以,在我看来,奇虎和腾讯只是windows的两条推广渠道,而不是销售渠道。win 10并不是完全免费了,它也是有定价的,该卖还是要卖的。对个人用户来说,正版windows的销售渠道只有一个:微软的在线商店。没有代理商、分销商之类的。也没有实物。能买到的就是一个key和一个iso下载链接。

一年内免费是说催促大家在一年内赶紧升级。并不是说装了win 10以后还要再掏钱。

win 10的一个重大的改变是:会在开始菜单旁边内置cortana。cortana是一个类似于siri/google now的东西。cortana的中文识别做的挺不错的,比siri好。

2015年6月17日星期三

Spark 1.1中下载jar包时的一个小错误

我在用yarn中跑spark时,总是遇见一个这样的错误:

java.io.FileNotFoundException: D:\data\yarnnm\local\usercache\chasun\appcache\application_1434537262045_0033\container_1434537262045_0033_01_000054\netlib-native\_ref-win-x86\_64-1.1-natives.jar (Access is denied)
  at java.io.FileOutputStream.open(Native Method)
  at java.io.FileOutputStream.(FileOutputStream.java:221)
  at org.spark-project.guava.common.io.Files¥FileByteSink.openStream(Files.java:223)
  at org.spark-project.guava.common.io.Files¥FileByteSink.openStream(Files.java:211)
  at org.spark-project.guava.common.io.ByteSource.copyTo(ByteSource.java:203)
  at org.spark-project.guava.common.io.Files.copy(Files.java:436)
  at org.spark-project.guava.common.io.Files.move(Files.java:651)
  at org.apache.spark.util.Utils¥.fetchFile(Utils.scala:437)
  at org.apache.spark.executor.Executor¥¥anonfun¥org¥apache¥spark¥executor¥Executor¥¥updateDependencies¥6.apply(Executor.scala:372)
  at org.apache.spark.executor.Executor¥¥anonfun¥org¥apache¥spark¥executor¥Executor¥¥updateDependencies¥6.apply(Executor.scala:370)
  at scala.collection.TraversableLike¥WithFilter¥¥anonfun¥foreach¥1.apply(TraversableLike.scala:772)
  at scala.collection.mutable.HashMap¥¥anonfun¥foreach¥1.apply(HashMap.scala:98)
  at scala.collection.mutable.HashMap¥¥anonfun¥foreach¥1.apply(HashMap.scala:98)
  at scala.collection.mutable.HashTable¥class.foreachEntry(HashTable.scala:226)
  at scala.collection.mutable.HashMap.foreachEntry(HashMap.scala:39)
  at scala.collection.mutable.HashMap.foreach(HashMap.scala:98)
  at scala.collection.TraversableLike¥WithFilter.foreach(TraversableLike.scala:771)
  at org.apache.spark.executor.Executor.org¥apache¥spark¥executor¥Executor¥¥updateDependencies(Executor.scala:370)
  at org.apache.spark.executor.Executor¥TaskRunner.run(Executor.scala:166)
  at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1145)
  at java.util.concurrent.ThreadPoolExecutor¥Worker.run(ThreadPoolExecutor.java:615)
  at java.lang.Thread.run(Thread.java:724)

我花了2-3个小时才找出原因。

它原来的fetch file的代码是这样的:

    if (targetFile.exists && !Files.equal(cachedFile, targetFile)) {
        if (conf.getBoolean("spark.files.overwrite", false)) {
          targetFile.delete()
          logInfo((s"File $targetFile exists and does not match contents of $url, " +
            s"replacing it with $url"))
        } else {
          throw new SparkException(s"File $targetFile exists and does not match contents of $url")
        }
   }
   Files.copy(cachedFile, targetFile)

这里的Files.equal会把两个文件逐字节的比较,如果相同就返回true。 但是有这么一种情况: 目标文件存在,确实也和cachedFile内容相同,但是它只是一个符号连接,指向一个system wide的readonly的文件。那么下面对targetFile进行Files.copy就会触发"Access is denied"。嗯,异常的名字却是FileNotFoundException。

这种情况发生于:yarn有一个public file cache(下图中的Public Localizer),如果jar包在这个file cache中,就会被软链接过来。

详情见: http://hortonworks.com/blog/resource-localization-in-yarn-deep-dive/

这个BUG在这个https://github.com/apache/spark/commit/7981f969762e77f1752ef8f86c546d4fc32a1a4f commit中被修补了。

2015年6月6日星期六

Rosenbrock Function

Rosenbrock function是最优化课本中经常出现的函数。stanfordnlp的代码中也经常拿它测试各种最优化方法的正确性和性能。

Rosenbrock function定义如下:

$$ f(x,y)=100(y-x^2)^2+(1-x)^2 $$

函数图像如下:

image

它的一阶导数为:

$$ \frac {\partial }{\partial y} f (x,y) = -200{x}^{2}+200y $$

$$ \frac {\partial }{\partial x}f (x,y) =-400(-{x}^{2}+y)x-2+2x $$

它的二阶导数(Hessian Matrix)为:

$$ \left[ \begin {array}{cc} 1200{x}^{2}-400y+2 & -400x \\ -400x & 200\end {array} \right] $$

当它取极值的时候它的一阶导数等于0。所以由\( \frac {\partial }{\partial y} f (x,y) =0 \) 可得 \( y=x^2 \)。代入\( \frac {\partial }{\partial x} f (x,y) =0 \)的式子中可解得它只有唯一解x=1,y=1。

把(1,1)代入Hessian矩阵中得到

$$ \left[ \begin {array}{cc} 802&-400 \\ -400&200 \end {array} \right] $$

它是正定的。所以f(x,y)在(1,1)这一点取得极小值。

等高线图如下:

> with(plots);

> contourplot(100*(-x^2+y)^2+(1-x)^2, x = -3 .. 3, y = -20 .. 20, contours = 20);

image

当使用牛顿迭代法的时候需要用到Hessian矩阵的逆:

> LinearAlgebra:-MatrixInverse( VectorCalculus:-Hessian(100*(-x^2+y)^2+(1-x)^2, [x, y]) );

$$ H^{-1} = \left[ \begin {array}{cc} \frac{1}{2(200{x}^{2}-200y+1)}&{\frac {x}{200{x}^{2}-200y+1}} \\ {\frac {x}{200{x}^{2}-200y+1}}&{\frac {600{x}^{2}-200y+1}{40000{x}^{2}-40000y+200}}\end {array} \right] $$

在它右边乘以梯度后得到

$$ p=\frac{1}{200x^2-200y+1}\begin{bmatrix} x-1 \\ -200x^4+(400y+1)x^2-2x-200y^2+y
\end{bmatrix} $$

p就是牛顿迭代法中的搜索方向。