polipo pac

最近又跟墙斗争了,吗的,升级安卓5之后Nexus 5手机特别耗电,最近终于找到原因了。google认为wifi没有连接,所以一直保持3g的连接,然后导致一些服务也在不停连接,然后就很耗电。这TM不能忍。

考虑到手机还要经常上一些国内的网站,一直保持VPN也不是办法。突然发现,android现在支持在连接wifi的时候设置pac,那就爽了。考虑到教育网翻墙快,我就设想设置一个跳板服务器,通过跳板服务器翻墙。又考虑到好多设备要翻墙,可以搞个缓存,于是就用到了polipo

Polipo配置:

因为教育网的服务器不能翻墙,要设置polipo的转发,主要就是转发。之前设置过shadowsocks,直接转发到shadowsocks端口即可。没有shadowsocks,直接使用ssh转发也可以,只要是socks的都行。主要是shadowsocks比较专业。其他设置查看man。

PAC:

既然wifi就支持PAC,就不需要其他翻墙软件了。我尝试过好几种方案。如根据解析的IP是否是国外,根据dns是否能解析等。最后还是觉得根据域名来比较好,网上有个gfwlist。然后将这里面的域名搞出来,但还是不全,比如gvt1.com就不在里面,没有他就不能在google play上下载东西(gvt1.com好像是google的CDN网络)。我还得考虑google scholar的问题,得用tor翻墙,否则会被认为是机器人。最后的PAC见github

现在手机就好了,以前7个小时的电池能用1天了,爽!而且国内网站不卡,完美。

Neural Network

神经网络是很早之前就听到过的,而且相信不少人也知道他是干什么的,但应该很少人亲自从底写一个测测神经网络是不是真的那么牛B。

最早的神经网络应用是手写文字的识别和车辆自动导航,也是CMU的走在前面。在20世纪前还是有很多人研究的,但是20世纪初就渐渐不行了,遇到瓶颈了。最近计算能力强了,有了deep learning,神经网络又火了。我先搞搞20世纪前的神经网络再说。(过了一年,我牛b多了,这篇太sb,可以看新的神经网络近似函数。)

基本原理:

nn

 

输入向量,如图像是每一个像素点,或者平面上的坐标点(x,y)。如果没有隐藏层,网络只能进行线性划分,而有一个隐含层则能近似所有函数(据说)。可能因为这一点导致到现在才出现deep learning. 因为只有一层隐含层对于复杂问题比较难训练。而对我一层足够了。输入信号根据权重相互组合,可以是线性也可以是非线性,输入到下一层,触发响应函数如sigmoid函数。一层层下去,就能得到输出信号。

道理我都懂,可是为什么正确的。关键在于怎么训练。每一个数据输入,都能得到计算出的结果,然后与预期结果比较,根据这个差值调节信号组合的权重。比如根据输出层的差值调节隐含层到输出层权重。这个求导即可。详见Networks and Learning Machines第130页。但是从隐含层调节输入到隐含层的权重就比较麻烦,因为不知道隐含层的期望值。这可以用导数的性质解决,同样见Networks and Learning Machines。

初步实验:

最好的实验就是XOR,因为非线性而且简单。但也不是一下子成功,因为训练的时候涉及一点参数,刚开始根本不知道设置多少。只有4个数据怎么训练,需要循环的训练,否则基本没有效果。代码见github。从测试结果看,还是很有适应性的。

xor

 

双螺旋分类:

two spiral常常用来测试分类器的性能。加一个二次项会让结果比较好。代码见github。我也用matlab内置的神经网络训练器nnstart来了一发,对比结果见下。效果好像差不多。

builtinnnmynn

 

总之,神经网络确实帅,“我根本不知道他是怎么工作的”,就是这么神奇。但是写代码还是有点蛋疼,我这个c++版本很简陋,也没有进行封装,只是为了看看神经网络是不是真的屌。

 

Ellipsoid Method

椭球法是古老的优化方法,现在看来效率不高,现在主要用的是内点法单纯形法。但我觉得ellipsoid method的思想比较独特,有必要好好了解一下。

主要思想:

考虑一个函数,只有一个最小值而且是凸的。先找到一个凸的集合包含这个点,然后按照一定规则收缩这个集合,到最后这个集合很小且包含那个点,那就达到目的了。

主要有两个问题,1.是怎样的集合 2.如何收缩集合。集合可以是一个多面体,这时就是cutting-plane method。收缩是根据subgradient g来的,因为f(x) >= f(x0) + g'(x-x0)。 可以舍去那一部分平面。达到收缩的目的。但是这里cutting-plane method慢啊,主要是找下一个x0很慢,要保证迭代少,必须要使x0尽可能平方集合。

所以就有了ellipsoid method。每次x0就是椭球的中心,然后使的椭球能包含上一次迭代的椭球和剩下的平面的交即可。这个简单也是最重要的部分,有人早就解决了。详见half ball lemma.

迭代过程:

为了把椭圆从矩阵的形式转换为能画的形式,费了一点劲。但是完美的结果,让我彻底相信了这个方法。迭代只有三步。但证明还是有点麻烦,见上面的half ball lemma。

ellipsoid_step1 ellipsoid_step2 ellipsoid_step3

上图是第一步迭代到第三步,可以看出椭圆越来越小,但是包含那个最优点。大概40步就有比较理想的结果。具体代码见github

参考:

  1. localization methods 
  2. EE364b