Machine Learning/Random Projection

这次突然打算写点dimension reduction的东西，虽然可以从PCA， manifold learning之类的东西开始，但很难用那些东西说出好玩的东西。这次选择的是一个不太出名但很有趣的方法，随机映射。但某些地方它一直是被当成LSH方法来介绍的，关于这点我不想过多追究，这里我认为他是一个降维。

Problem Statement

首先我们来看一个问题，如果你手头有一组数据$X \in R^n$，它的维数太高，从而不得不进行降维至$R^k$，你会怎么办？

相信不少人反射性地求它的$x’x$，然后转化为延最大方差展开的问题。当然这个方法很数学，也很漂亮，但它需要求解固有值和固有向量。对于测试用的小数据一切似乎都很好，但如果我给你的是50G大小csv格式的Twitter发言呢？如果需要对全部单词降维，恐怕半个月都不用吧。因此我们需要个更加快速的方法。

那么现在再来想，既然要快，那我们就用个最简单的方法：随机在高维空间里选几个单位向量$e_i$，但注意，这里我们仅仅要求是单位向量，并没有要求它们之间必须正交$<e_i,e_j>=0$，因此你可以放开手脚随便选。最后，我们把高维数据投影到选择的这一组基上。也就完成了降维。

乍一看这个方法似乎很扯，随便选的轴如何能保证降维效果？但它是有数学依据的，叫做Johnson-Lindenstrauss Lemma。这个定理保证了任何降维方法的精度上下限，因此，我们先来看看这个东西。

Johnson-Lindenstrauss Lemma

假设我们有数据$x \in R^n$，而我们通过一种方法$f(x)$将其降维成$y \in R^k$，那么，将为前后任意两点$a,b$之间的距离有不等式保证：

$(1-\epsilon )\| a-b \| ^2 \le \| f(a)-f(b) \| ^2 \le (1+ \epsilon ) \| a-b \|^2$

当然，原论文里面还包含了很多其他的东西，包括$ \epsilon $的值会有一个大致的推断，以及目标维数不能太小等等其他问题。但这里并不是重点，我也不太想多说。对于随机映射来说，只要注意到下面几点就行了：

不定式中的精度仅仅受制于维数、数据大小等因素，与将为方法无关。
在维数差不是很大时，总可以保证一个相对较高的精度，不论用什么方法。

到这里一切就很明显了，既然精度有上界，那我们也就不必担心轴的选取，那么最简单的方法自然就是随机挑选了，这也就产生的Random Projection这一方法。

Random Projection

前面说了这么多，相信看到这里也不需要过多解释了。简单来说， Random Projection流程就是

选择影射矩阵$R \in \mathcal{R}^{K \times N}$。
用随机数填充影射矩阵。可以选择uniform或者gaussian。
归一化每一个新的轴（影射矩阵中的每一行）。
对数据降维$y=R\mathcal{X}$。

上个小节里面的JL-lemma保证的降维的效果不会太差。

既然没有很数学的方法来说明这个方法靠谱，我们从直观上来看看。

首先假设我们有数据$\mathcal{X}=\{ x | f^{i}(\theta)+\sigma \}$，其中$\theta$是一组参数， $\sigma$则是高斯噪声。回想PCA方法，我们很自然的认为所有的特征都是正交的，我们既没有考虑它是不是有多个中心，也没有考虑是不是有特殊结构，然而对于实际数据，很多时候并不是这样。比如我们把取$f(\theta)=S^{i}(\theta _i)N(A, \sigma^i) \in R^3$，其中$S^{i} \in SO(3)$，这样我们得到的数据可能会像$\times$或者$*$一样，显然用PCA并不能得到好的结果。

在这种情况下，考虑在非常高维度的空间，可以想象random projection这种撞大运的方法总会选到一些超平面能够接近数据的特征，同时也能够想象如果目标维数过低，那么命中的概率就会大大降低。

闲话

最后是闲话，我对这次的博客不满意，写的很乱，逻辑不清淅，本来起笔之前想了不少好玩的东西，结果最后没能塞进来。就当成简单的RP的介绍看吧。本身我对这个方法不是很感冒，只是因为听到有人说有这么一种方法可以快速求解Laplacian Eigenmaps问题，结果稍微看了一下发现那人是在扯淡。 RP只不过是个简单的降维方法而已，精度和一般的方法差的还是比较远。真正的加速Eigenmaps还是得从sparse matrix的特征值分解上来吧。

另外前阵子去了趟美国，芝加哥-新泽西-纽约三地。说实话，作为一个自认为英语完全不行的人，我不太喜欢美国，去之前的准备也很消极， ds-160都没认真填，签证官向我要ps和资金证明，我也没好气的告诉他没有。本来心想干脆拒了我，这样我也能有借口给对面说我去不了。但没想到最后竟然在起飞前48小时左右批了下来，既然不能退票，最后只好匆匆忙忙的准备，超机场赶。

我买的票的成田机场到芝加哥的，为了轻便，只带了一台电脑和一个钱包，匆匆忙忙坐上jr朝东京赶，去到恰好赶上broading。

路上是11个小时，这是我第一次去地球另一侧，也体验了一把倒时差的感觉。全日空什么都好，就是椅子坐不住，脖子上有一个小突起，搞得一夜没能睡着，只能一直看好莱坞和娱乐节目。一直到第二天早上，吃早饭的时候我都睁不开眼了。因为时差，去到美国也是大白天，又等了半个小时，坐上united airlines的飞机匆匆忙忙赶往新泽西。

到了nj，大中午，太阳晒得不想动，于是窝在airtrain铁道下面等着蹭shuttle，到目的地都下午了。到附近的店里买了turkey sandwich，巨大无比，里面塞了生蔬菜和烤(?)火鸡， 6刀，膻味浓重，吃起来挺恶心，又买了瓶可乐， 2刀，开电脑发现wifi还要密码，于是索性睡了。

等醒的时候已经第二天下午了，先跑到小饭店里吃了个pizza， 16刀（？），量特别足，只可惜味道依然挺恶心，随后就是漫无目的的闲逛，我住的地方距离ny倒挺进，坐火车几十分钟就能到。美国的火车不怎么人道，提示非常少，我买了张nj transit的票，却完全不知道怎么用，看到来了个ny station的车，想上却被拦住了，列出员告诉我不能上，要等对面铁轨的车，当时没搞明白，后来才知道两个铁轨跑的不是同一家公司的车。

不知为什么ny没有自动检票，下车之前会有一个五大三粗的哥们查票，跟中国差不多，拿个打孔机在票上按几下，如果在没有检票机的地方下车的话票就被收走了。

从车站出来，旁边就是madison square garden，但我印象最深的不是这，而是扑面而来的拉客大队。会有各种人举着牌子拉客，有些事旅游车，其他的则完全听不懂了。所谓旅游车类似环线公交，上面露天，可以看风景，并且卖的票都是24小时或者72小时一类，可以中途下车再上。

本来想自己走，不过中途被一黑人哥们拉住了，向我介绍他们那车，问了下30多刀，坐上去之后才知道，去的地方非常少，基本就是市里一周，这车最大的作用就是从MSG把我弄到了liberty statue，既然来了美国，那也就打起精神去看了看自由女神。沿着街边能看到一排买票的，怎么看都跟中国的黄牛是一个性质，最后手痒，看到一个带着彩色尖刺帽子的黑人兄弟，买了他的票， 20刀。

在港口排了1个小时的队，终于到了入口处，一问才知道官方只卖15刀，能挣30%，美国黄牛真好干。

至于船，没什么特别的地方，我在日本国内也经常坐船，显然比这种小游轮好多了。说是一小时，除去返航启航最后只有30min，拿个绿色的像也不过远远的看了几分钟。其他时间海风吹得我想睡觉。

上岸，又到time square等地方看了看，四处是人，很拥挤。路上顺便买了几十刀的礼物，出门一查产地，清一色made in china。

至于芝加哥，对我来说完全类似。

总之我很失望，美国不但不像中国美分描述的跟天堂一样，反而非常平庸，而所谓的内在美我也没看出来，自由民主不是美利坚的专利，想要那些，世界上有几十个国家都提供。

回到东京已经傍晚，靠在车窗边上，看着熟悉的风景，我觉得我这辈子不会再去美国了。

巴特西

Machine Learning/Random Projection

最新文章

热门文章