programming, research resources, 技术

机器学习 machine learning chinese Gradient Boosting

http://www.cnblogs.com/LeftNotEasy/archive/2011/01/19/svd-and-applications.html

http://www.cnblogs.com/LeftNotEasy/archive/2011/01/02/machine-learning-boosting-and-gradient-boosting.html

 

 

前言:

本来上一章的结尾提到,准备写写线性分类的问题,文章都已经写得差不多了,但是突然听说最近Team准备做一套分布式的分类器,可能会使用Random Forest来做,下了几篇论文看了看,简单的random forest还比较容易弄懂,复杂一点的还会与boosting等算法结合(参见iccv09),对于boosting也不甚了解,所以临时抱佛脚的看了看。说起boosting,强哥之前实现过一套Gradient Boosting Decision Tree(GBDT)算法,正好参考一下。

最近看的一些论文中发现了模型组合的好处,比如GBDT或者rf,都是将简单的模型组合起来,效果比单个更复杂的模型好。组合的方式很多,随机化(比如random forest),Boosting(比如GBDT)都是其中典型的方法,今天主要谈谈Gradient Boosting方法(这个与传统的Boosting还有一些不同)的一些数学基础,有了这个数学基础,上面的应用可以看Freidman的Gradient Boosting Machine。

本文要求读者学过基本的大学数学,另外对分类、回归等基本的机器学习概念了解。

本文主要参考资料是prml与Gradient Boosting Machine。

 

Boosting方法:

Boosting这其实思想相当的简单,大概是,对一份数据,建立M个模型(比如分类),一般这种模型比较简单,称为弱分类器(weak learner)每次分类都将上一次分错的数据权重提高一点再进行分类,这样最终得到的分类器在测试数据与训练数据上都可以得到比较好的成绩。

image

上图(图片来自prml p660)就是一个Boosting的过程,绿色的线表示目前取得的模型(模型是由前m次得到的模型合并得到的),虚线表示当前这次模型。每次分类的时候,会更关注分错的数据,上图中,红色和蓝色的点就是数据,点越大表示权重越高,看看右下角的图片,当m=150的时候,获取的模型已经几乎能够将红色和蓝色的点区分开了。

Boosting可以用下面的公式来表示:image

训练集中一共有n个点,我们可以为里面的每一个点赋上一个权重Wi(0 <= i < n),表示这个点的重要程度,通过依次训练模型的过程,我们对点的权重进行修正,如果分类正确了,权重降低,如果分类错了,则权重提高,初始的时候,权重都是一样的。上图中绿色的线就是表示依次训练模型,可以想象得到,程序越往后执行,训练出的模型就越会在意那些容易分错(权重高)的点。当全部的程序执行完后,会得到M个模型,分别对应上图的y1(x)…yM(x),通过加权的方式组合成一个最终的模型YM(x)。

我觉得Boosting更像是一个人学习的过程,开始学一样东西的时候,会去做一些习题,但是常常连一些简单的题目都会弄错,但是越到后面,简单的题目已经难不倒他了,就会去做更复杂的题目,等到他做了很多的题目后,不管是难题还是简单的题都可以解决掉了。

 

Gradient Boosting方法:

其实Boosting更像是一种思想,Gradient Boosting是一种Boosting的方法,它主要的思想是,每一次建立模型是在之前建立模型损失函数的梯度下降方向。这句话有一点拗口,损失函数(loss function)描述的是模型的不靠谱程度,损失函数越大,则说明模型越容易出错(其实这里有一个方差、偏差均衡的问题,但是这里就假设损失函数越大,模型越容易出错)。如果我们的模型能够让损失函数持续的下降,则说明我们的模型在不停的改进,而最好的方式就是让损失函数在其梯度(Gradient)的方向上下降。

下面的内容就是用数学的方式来描述Gradient Boosting,数学上不算太复杂,只要潜下心来看就能看懂:)

    可加的参数的梯度表示:

假设我们的模型能够用下面的函数来表示,P表示参数,可能有多个参数组成,P = {p0,p1,p2….},F(x;P)表示以P为参数的x的函数,也就是我们的预测函数。我们的模型是由多个模型加起来的,β表示每个模型的权重,α表示模型里面的参数。为了优化F,我们就可以优化{β,α}也就是P。

image

我们还是用P来表示模型的参数,可以得到,Φ(P)表示P的likelihood函数,也就是模型F(x;P)的loss函数,Φ(P)=…后面的一块看起来很复杂,只要理解成是一个损失函数就行了,不要被吓跑了。

image   既然模型(F(x;P))是可加的,对于参数P,我们也可以得到下面的式子:image   这样优化P的过程,就可以是一个梯度下降的过程了,假设当前已经得到了m-1个模型,想要得到第m个模型的时候,我们首先对前m-1个模型求梯度。得到最快下降的方向,gm就是最快下降的方向。

image    这里有一个很重要的假设,对于求出的前m-1个模型,我们认为是已知的了,不要去改变它,而我们的目标是放在之后的模型建立上。就像做事情的时候,之前做错的事就没有后悔药吃了,只有努力在之后的事情上别犯错:

image    我们得到的新的模型就是,它就在P似然函数的梯度方向。ρ是在梯度方向上下降的距离。

image    我们最终可以通过优化下面的式子来得到最优的ρ:

image

    可加的函数的梯度表示:

上面通过参数P的可加性,得到了参数P的似然函数的梯度下降的方法。我们可以将参数P的可加性推广到函数空间,我们可以得到下面的函数,此处的fi(x)类似于上面的h(x;α),因为作者的文献中这样使用,我这里就用作者的表达方法:

image    同样,我们可以得到函数F(x)的梯度下降方向g(x)

image    最终可以得到第m个模型fm(x)的表达式:

image

 

    通用的Gradient Descent Boosting的框架:

下面我将推导一下Gradient Descent方法的通用形式,之前讨论过的:

image    对于模型的参数{β,α},我们可以用下面的式子来进行表示,这个式子的意思是,对于N个样本点(xi,yi)计算其在模型F(x;α,β)下的损失函数,最优的{α,β}就是能够使得这个损失函数最小的{α,β}。image 表示两个m维的参数:

image    写成梯度下降的方式就是下面的形式,也就是我们将要得到的模型fm(x)的参数{αm,βm}能够使得fm的方向是之前得到的模型Fm-1(x)的损失函数下降最快的方向:

image

对于每一个数据点xi都可以得到一个gm(xi),最终我们可以得到一个完整梯度下降方向

image

image    为了使得fm(x)能够在gm(x)的方向上,我们可以优化下面的式子得到,可以使用最小二乘法:

image    得到了α的基础上,然后可以得到βm。  image    最终合并到模型中:

image

算法的流程图如下

image     之后,作者还说了这个算法在其他的地方的推广,其中,Multi-class logistic regression and classification就是GBDT的一种实现,可以看看,流程图跟上面的算法类似的。这里不打算继续写下去,再写下去就成论文翻译了,请参考文章:Greedy function Approximation – A Gradient Boosting Machine,作者Freidman。

 

总结:

本文主要谈了谈Boosting与Gradient Boosting的方法,Boosting主要是一种思想,表示“知错就改”。而Gradient Boosting是在这个思想下的一种函数(也可以说是模型)的优化的方法,首先将函数分解为可加的形式(其实所有的函数都是可加的,只是是否好放在这个框架中,以及最终的效果如何)。然后进行m次迭代,通过使得损失函数在梯度方向上减少,最终得到一个优秀的模型。值得一提的是,每次模型在梯度方向上的减少的部分,可以认为是一个“小”的或者“弱”的模型,最终我们会通过加权(也就是每次在梯度方向上下降的距离)的方式将这些“弱”的模型合并起来,形成一个更好的模型。

有了这个Gradient Descent这个基础,还可以做很多的事情。也在机器学习的道路上更进一步了:)

Standard
life is fun, 技术

浅谈401(K)

退休计划有很多种,本文只重点谈最常见的 401(K)。为了让之简单易懂,难免有不周全之处,望指正。

为了让这篇文章更吸引人,我先谈一下参加401(K)的好处:

1) 降低现在的 TAXABLE INCOME

2) FREE MONEY from 雇主

3) 不用自己操太多的心,就能ACCUMULATE 退休后的经济来源

4) 大部分情况下比不加入401(K)要省税

现在我们先讲一下401(K) 是怎么WORK的

大部分的公司都提供401(K)计划。你只要是QUALIFIED的员工(比方说工作一年以上),你就可以参加。你参加了,公司就会帮你建一个401(K) 帐户。你的每一张PAYCHECK,公司会按照一定的比例(你自己选择这个比例)扣除放到你的401(K)帐户里。比方说你每个工资单税前收入4000,你选择12.5% 的DEDUCTION,公司就会在每个PAY DAY放500进你的401(K)帐户。

这样做最大的好处是,本来你的TAXABLE INCOME 是4000 的,这下变成了3500。换句话讲,将来你的W2上的第一个数字就不再是你的原始工资,而是 原始工资 减去 401K CONTRIBUTION。E.g.,假如本来你的年薪是10万,但你放了1万进你的401K,你今年就只要按照9万收入来付税。

同时一般公司会有MATCH PROGRAM,比方说,MATCH 4%,意思就是每个PAYCHECK,公司会再放160块钱进去(4000×4%)。要提一下的是,每年国家都规定了个人CONTRIBUTE TO 401(K) 的上限,比方说,2008年的LIMIT是15 ,500。(这个是个人的投入,不包括公司的MATCH)。

401(K)帐户里的钱就都是你自己的啦,接下来你要做的事情就是管理这个401(K)帐户。 一般来说,管理401(K)PLAN比较简单,PLAN 会给你一些可选择的金融产品,10来个到三四十个不等,大部分是基金(FUND),有股票的(STOCK FUND),也有债劵的(BOND FUND)。一般的原则是,年轻的要偏重投资在股票上,接近退休的则要偏重在债劵上。

就这样,不需要你操太多心,你的401(K)帐户就这样每个月增长着。等到你退休,没有了工资收入,但这时候你的 401(K)就已经积累了相当一部分财富。你可以从你的401(K)里面往外取钱来支付你的日常开销。要注意的是,你退休后从401(K)里取出来的钱是要作为你的正常收入来交收入税的。换句话说,假如你一年取出5万的话,这个5万要像你现在的工资一样交收入税的。现在政府规定的取钱的最低年龄是59.5 岁,到了那个年龄才可以往外取钱。当然,你也可以暂时不拿出来用,但同时也有规定,到70.5岁之后就必须开始往外取钱。

有两种情况在59.5岁之前从401(K)计划里取钱的。一是买房子的时候,可以从401(K)里面“借钱”支付首付。这个的机理和MORTGAGE一样,你每个月要连本带息还,但是,你是管自己“借” AND “还”给自己。 第二个就是,你偏要取,在这种情况下,不仅你取出来的钱要交INCOME TAX, 还要另交10%的PENALTY。

这个401(K)究竟是怎么省税的呢,

其实很简单,就是一个DEFERRED TAX的概念。我们举个最简单的例子,一个人今年59岁,年薪10万,明年退休。他如果今年把1万放进401K, 他的401K里就多一万,如果不放,他的银行帐号里就多7500.(假设他今年的税率是25%)。到了明年,他从401K里把这一万取出来,会拿到多少呢,一般情况下,会超过7500。为什么呢,因为他一年不需要从401K里取10万的话,他的税率就会低一些,假设20%的话,他就能取出8000,比不存401K多出来500。

用一句话概括就是,401K 把现在高税率的TAX 推迟到了退休后的低税率。

而且从这个小的例子,我们也不难看出,越高收入的人(换句话说,高税率的人),可以从401K里省更多的税,因为退休前后的税率差更大。更不用说,要是退休前在纽约这样高收入税的州,退休后搬到得克萨斯(低收入税)去生活了。

几个重点总结一下:

1. 公司要是有401(K)MATCH的话,一定要参与401(K)计划
2. 收入越高的人越要参与,假如家庭年薪超过15万的话,基本上就要放满
3. 对于年轻人来讲(40岁以前),应该把绝大多数钱都投在股票基金上

中国有句古话叫“未雨绸缪”,现在积极参与和投资401(K),退休后就会有一个幸福无忧的生活,岂不快哉。

Standard
research resources, 技术

Compressive sensing zz

第一篇是陶哲轩写的。

 

这是数学家陶哲轩在他自己的blog上写的一篇科普文章,讨论的是近年来在应用数学领域里最热门的话题之一:)。所谓压缩感知,最核心的概念在于试图从原理上降低对一个信号进行测量的成本。比如说,一个信号包含一千个数据,那么按照传统的信号处理理论,至少需要做一千次测量才能完整的复原这个信号。这就相当于是说,需要有一千个方程才能精确地解出一千个未知数来。但是压缩感知的想法是假定信号具有某种特点(比如文中所描述得在小波域上系数稀疏的特点),那么就可以只做三百次测量就完整地复原这个信号(这就相当于只通过三百个方程解出一千个未知数)。可想而知,这件事情包含了许多重要的数学理论和广泛的应用前景,因此在最近三四年里吸引了大量注意力,得到了非常蓬勃的发展。陶哲轩本身是这个领域的奠基人之一(可以参考《陶哲轩:长大的神童》一文),因此这篇文章的权威性毋庸讳言。另外,这也是比较少见的由一流数学家直接撰写的关于自己前沿工作的普及性文章。需要说明的是,这篇文章是虽然是写给非数学专业的读者,但是也并不好懂,也许具有一些理工科背景会更容易理解一些。

【作者 Terence Tao;译者 山寨盲流,他的更多译作在;校对 木遥】

最近有不少人问我究竟”压缩感知”是什么意思(特别是随着最近这个概念名声大噪),所谓“单像素相机”又是怎样工作的(又怎么能在某些场合比传统相机有优势呢)。这个课题已经有了大量文献,不过对于这么一个相对比较新的领域,还没有一篇优秀的非技术性介绍。所以笔者在此小做尝试,希望能够对非数学专业的读者有所帮助。

具体而言我将主要讨论摄像应用,尽管压缩传感作为测量技术应用于比成像广泛得多的领域(例如天文学,核磁共振,统计选取,等等),我将在帖子结尾简单谈谈这些领域。

相机的用途,自然是记录图像。为了简化论述,我们把图像假设成一个长方形阵列,比如说一个1024×2048像素的阵列(这样就总共是二百万像素)。为了省略彩色的问题(这个比较次要),我们就假设只需要黑白图像,那么每个像素就可以用一个整型的灰度值来计量其亮度(例如用八位整型数表示0到255,16位表示0到65535)。

接下来,按照最最简化的说法,传统相机会测量每一个像素的亮度(在上述例子中就是二百万个测量值),结果得到的图片文件就比较大(用8位灰度值就是2MB,16位灰度就是4MB)。数学上就认为这个文件是用超高维矢量值描绘的(在本例中就是约二百万维)。

在我开始讲“压缩感知”这个新故事之前,必须先快速回顾一下“老式压缩”的旧故事。(已经了解图像压缩算法的读者可以跳过这几段。)

上述的图片会占掉相机的很多存储空间(上传到计算机里还占磁盘空间),在各种介质之间传输的时候也要浪费时间。于是,相机带有显著压缩图像的功能就顺理成章了(通常能从2MB那么大压缩到十分之一——200KB的一小坨)。关键是尽管“所有图片”所构成的空间要占用2MB的“自由度”或者说“熵”,由“有意义的图片”所构成的空间其实要小得多,尤其是如果人们愿意降低一点图像质量的话。(实际上,如果一个人真的利用所有的自由度随机生成一幅图片,他不大可能得到什么有意义的图像,而是得到相当于电视荧屏上的静电雪花那样的随机噪声之类。)

怎么样压缩图像?方式多种多样,其中有些非常先进,不过我来试试用一种不太高科技的(而且也不太精确的)说法来描述一下这些先进技术。图像通常都含有大片无细节部分–比如在风景照里面,将近一半的画面都可能被单色的天空背景占据。我们假设提取一个大方块,比方说100×100像素,其中完全是同一颜色的——假设是全白的吧。无压缩时,这个方块要占10000字节存储空间(按照8位灰度算);但是我们可以只记录这个方块的维度和坐标,还有填充整个方块的单一颜色;这样总共也只要记录四五个字节,省下了可观的空间。不过在现实中,压缩效果没有这么好,因为表面看来没有细节的地方其实是有着细微的色差的。所以,给定一个无细节方块,我们记录其平均色值,就把图片中这一块区域抽象成了单色色块,只留下微小的残余误差。接下来就可以继续选取更多色彩可见的方块,抽象成单色色块。最后剩下的是亮度(色彩强度)很小的,肉眼无法察觉的细节。于是就可以抛弃这些剩余的细节,只需要记录那些“可见”色块的大小,位置和亮度。日后则可以反向操作,重建出比原始图像质量稍低一些,占空间却小得多的复制图片。

其实上述的算法并不适合处理颜色剧烈变动的情况,所以在实际应用中不很有效。事实上,更好的办法不是用均匀色块,而是用“不均匀”的色块——比方说右半边色彩强度平均值大于左半边这样的色块。这种情况可以用(二维)Haar小波系统来描述。后来人们又发现一种”更平滑的”小波系统更能够避免误差,不过这都是技术细节,我们就不深入讨论了。然而所有这些系统的原理都是相同的:把原始图像表示为不同“小波(类似于上文中的色块)”的线性叠加,记录显著的(高强度的)小波的系数,放弃掉(或者用阈值排除掉)剩下的小波系数。这种“小波系数硬阈值”压缩算法没有实际应用的算法(比如JPEG 2000标准中所定义的)那么精细,不过多少也能描述压缩的普遍原理。

总体来讲(也是非常简化的说法),原始的1024×2048图像可能含有两百万自由度,想要用小波来表示这个图像的人需要两百万个不同小波才能完美重建。但是典型的有意义的图像,从小波理论的角度看来是非常稀疏的,也就是可压缩的:可能只需要十万个小波就已经足够获取图像所有的可见细节了,其余一百九十万小波只贡献很少量的,大多数观测者基本看不见的“随机噪声”。(这也不是永远适用:含有大量纹理的图像–比如毛发、毛皮的图像——用小波算法特别难压缩,也是图像压缩算法的一大挑战。不过这是另一个故事了。)

接下来呢,如果我们(或者不如说是相机)事先知道两百万小波系数里面哪十万个是重要的,那就可以只计量这十万个系数,别的就不管了。(在图像上设置一种合适的“过滤器”或叫“滤镜”,然后计量过滤出来的每个像素的色彩强度,是一种可行的系数计量方法。)但是,相机是不会知道哪个系数是重要的,所以它只好计量全部两百万个像素,把整个图像转换成基本小波,找出需要留下的那十万个主导基本小波,再删掉其余的。(这当然只是真正的图像压缩算法的一个草图,不过为了便于讨论我们还是就这么用吧。)

那么,如今的数码相机当然已经很强大了,没什么问题干吗还要改进?事实上,上述的算法,需要收集大量数据,但是只需要存储一部分,在消费摄影中是没有问题的。尤其是随着数据存储变得很廉价,现在拍一大堆完全不压缩的照片也无所谓。而且,尽管出了名地耗电,压缩所需的运算过程仍然算得上轻松。但是,在非消费领域的某些应用中,这种数据收集方式并不可行,特别是在传感器网络中。如果打算用上千个传感器来收集数据,而这些传感器需要在固定地点呆上几个月那么长的时间,那么就需要尽可能地便宜和节能的传感器——这首先就排除了那些有强大运算能力的传感器(然而——这也相当重要——我们在接收处理数据的接收端仍然需要现代科技提供的奢侈的运算能力)。在这类应用中,数据收集方式越“傻瓜”越好(而且这样的系统也需要很强壮,比如说,能够忍受10%的传感器丢失或者各种噪声和数据缺损)。

这就是压缩传感的用武之地了。其理论依据是:如果只需要10万个分量就可以重建绝大部分的图像,那何必还要做所有的200万次测量,只做10万次不就够了吗?(在实际应用中,我们会留一个安全余量,比如说测量30万像素,以应付可能遭遇的所有问题,从干扰到量化噪声,以及恢复算法的故障。)这样基本上能使节能上一个数量级,这对消费摄影没什么意义,对传感器网络而言却有实实在在的好处。

不过,正像我前面说的,相机自己不会预先知道两百万小波系数中需要记录哪十万个。要是相机选取了另外10万(或者30万),反而把图片中所有有用的信息都扔掉了怎么办?

解决的办法简单但是不太直观。就是用非小波的算法来做30万个测量——尽管我前面确实讲过小波算法是观察和压缩图像的最佳手段。实际上最好的测量其实应该是(伪)随机测量——比如说随机生成30万个“滤镜”图像并测量真实图像与每个滤镜的相关程度。这样,图像与滤镜之间的这些测量结果(也就是“相关性”)很有可能是非常小非常随机的。但是——这是关键所在——构成图像的2百万种可能的小波函数会在这些随机的滤镜的测量下生成自己特有的“特征”,它们每一个都会与某一些滤镜成正相关,与另一些滤镜成负相关,但是与更多的滤镜不相关。可是(在极大的概率下)2百万个特征都各不相同;更有甚者,其中任意十万个的线性组合仍然是各不相同的(以线性代数的观点来看,这是因为一个30万维线性子空间中任意两个10万维的子空间极有可能互不相交)。因此,基本上是有可能从这30万个随机数据中恢复图像的(至少是恢复图像中的10万个主要细节)。简而言之,我们是在讨论一个哈希函数的线性代数版本。

然而这种方式仍然存在两个技术问题。首先是噪声问题:10万个小波系数的叠加并不能完全代表整幅图像,另190万个系数也有少许贡献。这些小小贡献有可能会干扰那10万个小波的特征,这就是所谓的“失真”问题。第二个问题是如何运用得到的30万测量数据来重建图像。

我们先来关注后一个问题。如果我们知道了2百万小波中哪10万个是有用的,那就可以使用标准的线性代数方法(高斯消除法,最小二乘法等等)来重建信号。(这正是线性编码最大的优点之一——它们比非线性编码更容易求逆。大多数哈希变换实际上是不可能求逆的——这在密码学上是一大优势,在信号恢复中却不是。)可是,就像前面说的那样,我们事前并不知道哪些小波是有用的。怎么找出来呢?一个单纯的最小二乘近似法会得出牵扯到全部2百万系数的可怕结果,生成的图像也含有大量颗粒噪点。要不然也可以代之以一种强力搜索,为每一组可能的10万关键系数都做一次线性代数处理,不过这样做的耗时非常恐怖(总共要考虑大约10的17万次方个组合!),而且这种强力搜索通常是NP完备的(其中有些特例是所谓的“子集合加总”问题)。不过还好,还是有两种可行的手段来恢复数据:

• 匹配追踪:找到一个其标记看上去与收集到的数据相关的小波;在数据中去除这个标记的所有印迹;不断重复直到我们能用小波标记“解释”收集到的所有数据。

• 基追踪(又名L1模最小化):在所有与录得数据匹配的小波组合中,找到一个“最稀疏的”,也就是其中所有系数的绝对值总和越小越好。(这种最小化的结果趋向于迫使绝大多数系数都消失了。)这种最小化算法可以利用单纯形法之类的凸规划算法,在合理的时间内计算出来。

需要注意到的是,这类图像恢复算法还是需要相当的运算能力的(不过也还不是太变态),不过在传感器网络这样的应用中这不成问题,因为图像恢复是在接收端(这端有办法连接到强大的计算机)而不是传感器端(这端就没办法了)进行的。

现在已经有严密的结果显示,对原始图像设定不同的压缩率或稀疏性,这两种算法完美或近似完美地重建图像的成功率都很高。匹配追踪法通常比较快,而基追踪算法在考虑到噪声时则显得比较准确。这些算法确切的适用范围问题在今天仍然是非常热门的研究领域。(说来遗憾,目前还没有出现对P不等于NP问题的应用;如果一个重建问题(在考虑到测量矩阵时)是NP完备的,那它刚好就不能用上述算法解决。)

由于压缩传感还是一个相当新的领域(尤其是严密的数学结果刚刚出现),现在就期望这个技术应用到实用的传感器上还为时尚早。不过已经有概念验证模型出现了,其中最著名的是Rice大学研制的单像素相机。

最后必须提到的是,压缩传感技术是一种抽象的数学概念,而不是具体的操作方案,它可以应用到成像以外的许多领域。以下只是其中几个例子:

• 磁共振成像(MRI)。在医学上,磁共振的工作原理是做许多次(但次数仍是有限的)测量(基本上就是对人体图像进行离散拉东变换(也叫X光变换)),再对数据进行加工来生成图像(在这里就是人体内水的密度分布图像)。由于测量次数必须很多,整个过程对患者来说太过漫长。压缩传感技术可以显著减少测量次数,加快成像(甚至有可能做到实时成像,也就是核磁共振的视频而非静态图像)。此外我们还可以以测量次数换图像质量,用与原来一样的测量次数可以得到好得多的图像分辨率。

• 天文学。许多天文现象(如脉冲星)具有多种频率震荡特性,使其在频域上是高度稀疏也就是可压缩的。压缩传感技术将使我们能够在时域内测量这些现象(即记录望远镜数据)并能够精确重建原始信号,即使原始数据不完整或者干扰严重(原因可能是天气不佳,上机时间不够,或者就是因为地球自传使我们得不到全时序的数据)。

• 线性编码。压缩传感技术提供了一个简单的方法,让多个传送者可以将其信号带纠错地合并传送,这样即使输出信号的一大部分丢失或毁坏,仍然可以恢复出原始信号。例如,可以用任意一种线性编码把1000比特信息编码进一个3000比特的流;那么,即使其中300位被(恶意)毁坏,原始信息也能完全无损失地完美重建。这是因为压缩传感技术可以把破坏动作本身看作一个稀疏的信号(只集中在3000比特中的300位)。

许多这种应用都还只停留在理论阶段,可是这种算法能够影响测量和信号处理中如此之多的领域,其潜力实在是振奋人心。笔者自己最有成就感的就是能看到自己在纯数学领域的工作(例如估算傅立叶子式的行列式或单数值)最终具备造福现实世界的前景。

第二篇

压缩感知是近年来极为热门的研究前沿,在若干应用领域中都引起瞩目。关于这个题目,松鼠会已经翻译了两篇文章,一篇来自于压缩感知技术最初的研究者陶哲轩(链接),一篇来自威斯康辛大学的数学家艾伦伯格(本文正文)。这两篇文章都是普及性的,但是由于作者是专业的研究人员,所以事实上行文仍然偏于晦涩。因此我不揣冒昧,在这里附上一个画蛇添足的导读,以帮助更多的读者更好了解这个新颖的研究领域在理论和实践上的意义。

压缩感知从字面上看起来,好像是数据压缩的意思,而实则出于完全不同的考虑。经典的数据压缩技术,无论是音频压缩(例如 mp3),图像压缩(例如 jpeg),视频压缩(mpeg),还是一般的编码压缩(zip),都是从数据本身的特性出发,寻找并剔除数据中隐含的冗余度,从而达到压缩的目的。这样的压缩有两个特点:第一、它是发生在数据已经被完整采集到之后;第二、它本身需要复杂的算法来完成。相较而言,解码过程反而一般来说在计算上比较简单,以音频压缩为例,压制一个 mp3 文件的计算量远大于播放(即解压缩)一个 mp3 文件的计算量。

稍加思量就会发现,这种压缩和解压缩的不对称性正好同人们的需求是相反的。在大多数情况下,采集并处理数据的设备,往往是廉价、省电、计算能力较低的便携设备,例如傻瓜相机、或者录音笔、或者遥控监视器等等。而负责处理(即解压缩)信息的过程却反而往往在大型计算机上进行,它有更高的计算能力,也常常没有便携和省电的要求。也就是说,我们是在用廉价节能的设备来处理复杂的计算任务,而用大型高效的设备处理相对简单的计算任务。这一矛盾在某些情况下甚至会更为尖锐,例如在野外作业或者军事作业的场合,采集数据的设备往往曝露在自然环境之中,随时可能失去能源供给或者甚至部分丧失性能,在这种情况下,传统的数据采集-压缩-传输-解压缩的模式就基本上失效了。

压缩感知的概念就是为了解决这样的矛盾而产生的。既然采集数据之后反正要压缩掉其中的冗余度,而这个压缩过程又相对来说比较困难,那么我们为什么不直接「采集」压缩后的数据?这样采集的任务要轻得多,而且还省去了压缩的麻烦。这就是所谓的「压缩感知」,也就是说,直接感知压缩了的信息。

可是这看起来是不可能的事情。因为压缩后的数据并不是压缩前的数据的一个子集,并不是说,本来有照相机的感光器上有一千万个像素,扔掉其中八百万个,剩下的两百万个采集到的就是压缩后的图像,──这样只能采集到不完整的一小块图像,有些信息被永远的丢失了而且不可能被恢复。如果要想采集很少一部分数据并且指望从这些少量数据中「解压缩」出大量信息,就需要保证:第一:这些少量的采集到的数据包含了原信号的全局信息,第二:存在一种算法能够从这些少量的数据中还原出原先的信息来。
有趣的是,在某些特定的场合,上述第一件事情是自动得到满足的。最典型的例子就是医学图像成像,例如断层扫描(CT)技术和核磁共振(MRI)技术。对这两种技术稍有了解的人都知道,这两种成像技术中,仪器所采集到的都不是直接的图像像素,而是图像经历过全局傅立叶变换后的数据。也就是说,每一个单独的数据都在某种程度上包含了全图像的信息。在这种情况下,去掉一部分采集到的数据并不会导致一部分图像信息永久的丢失(它们仍旧被包含在其它数据里)。这正是我们想要的情况。
上述第二件事就要归功于陶哲轩和坎戴的工作了。他们的工作指出,如果假定信号(无论是图像还是声音还是其他别的种类的信号)满足某种特定的「稀疏性」,那么从这些少量的测量数据中,确实有可能还原出原始的较大的信号来,其中所需要的计算部分是一个复杂的迭代优化过程,即所谓的「L1-最小化」算法。

把上述两件事情放在一起,我们就能看到这种模式的优点所在。它意味着:我们可以在采集数据的时候只简单采集一部分数据(「压缩感知」),然后把复杂的部分交给数据还原的这一端来做,正好匹配了我们期望的格局。在医学图像领域里,这个方案特别有好处,因为采集数据的过程往往是对病人带来很大麻烦甚至身体伤害的过程。以 X 光断层扫描为例,众所周知 X 光辐射会对病人造成身体损害,而「压缩感知」就意味着我们可以用比经典方法少得多的辐射剂量来进行数据采集,这在医学上的意义是不言而喻的。

这一思路可以扩展到很多领域。在大量的实际问题中,我们倾向于尽量少地采集数据,或者由于客观条件所限不得不采集不完整的数据。如果这些数据和我们所希望重建的信息之间有某种全局性的变换关系,并且我们预先知道那些信息满足某种稀疏性条件,就总可以试着用类似的方式从比较少的数据中还原出比较多的信号来。到今天为止,这样的研究已经拓展地非常广泛了。
但是同样需要说明的是,这样的做法在不同的应用领域里并不总能满足上面所描述的两个条件。有的时候,第一个条件(也就是说测量到的数据包含信号的全局信息)无法得到满足,例如最传统的摄影问题,每个感光元件所感知到的都只是一小块图像而不是什么全局信息,这是由照相机的物理性质决定的。为了解决这个问题,美国 Rice 大学的一部分科学家正在试图开发一种新的摄影装置(被称为「单像素照相机」),争取用尽量少的感光元件实现尽量高分辨率的摄影。有的时候,第二个条件(也就是说有数学方法保证能够从不完整的数据中还原出信号)无法得到满足。这种时候,实践就走在了理论前面。人们已经可以在算法上事先很多数据重建的过程,但是相应的理论分析却成为了留在数学家面前的课题。

但是无论如何,压缩感知所代表的基本思路:从尽量少的数据中提取尽量多的信息,毫无疑问是一种有着极大理论和应用前景的想法。它是传统信息论的一个延伸,但是又超越了传统的压缩理论,成为了一门崭新的子分支。它从诞生之日起到现在不过五年时间,其影响却已经席卷了大半个应用科学。

Standard
life is fun, 技术

当代中国思想微弱的声音:郎咸平,袁腾飞

当代中国思想微弱的声音:

郎咸平:对中国经济入木三分有理有据的分析;对中国文化本质的概括:浮躁,投机取巧。(三国演义)

袁腾飞:中国历史的解读,发出了独立思想的声音。对某些历史人物的褒贬过于偏激,但是大部分分析堪称精辟。

 

放眼当代中国,能发出自己的声音的,也就此二君了。

Standard