• Category Archives: Study

study

压缩感知

最近看到两个两个大牛的毕业论文里有压缩感知的(Compressed Sensing, CS)概念,才知道压缩感知是近10年来极为热门的学术大坑。

example obama
压缩感知问题源自稀疏表示问题,两者的本质都是要在一定的约束条件下求得欠定方程的最稀疏解。Donoho在这个领域功不可没,也是压缩感知研究领域具有奠基性工作的人物。压缩感知的发现是个传说,2004年加州理工学院教授(现在在斯坦福)的Emmanuel Candes,Donoho的学生,在研究Shepp-Logan Phantom图像,这是医学图像处理领域用来进行仿真测试的标准模拟图像。Candes检查的图像质量非常差,充满了噪声,他想到一种名叫L1-minimization的数学算法能去除掉噪声条纹,结果算法真的起作用了,而且他发现在图像变干净的同时,图像的细节出人意料得完美,简直就像变魔术一样。

“It was as if you gave me the first three digits of a 10-digit bank account number — and then I was able to guess the next seven,” he says. He tried rerunning the experiment on different kinds of phantom images; they resolved perfectly every time.

Emmanuel Candes后来向加州大学洛杉矶分校的同事陶哲轩介绍了自己的发现,陶哲轩是世界上搞调和分析的顶尖高手之一,于是陶哲轩、Emmanuel Candes和Donoho神牛们完善了理论,联手挖出了Compressed Sensing的大坑。

传统信号或者图像采样一般采用奈奎斯特-香农采样定理(Nyquist–Shannon sampling theorem):即采样频率至少要大于模拟信号频率最大值(那奎斯特采样频率)的二倍,才能保证模拟信号在数字化过程中信息没有损失。在很多的应用场合,如医学成像、模式识别、无线通信等领域,高采样率带来的问题成为了制约信号获取、存储、传输及处理等信号与信息处理领域进一步发展的瓶颈。科学松鼠会一篇文章很好地介绍了压缩感知的应用背景:

压缩感知和数据压缩不同,经典的数据压缩技术是从数据本身的特性出发,寻找并剔除数据中隐含的冗余度,从而达到压缩的目的。这样的压缩有两个特点:第一、它是发生在数据已经被完整采集到之后;第二、它本身需要复杂的算法来完成。相较而言,解码过程反而一般来说在计算上比较简单。

但是压缩和解压缩的不对称性正好同人们的需求是相反的。在大多数情况下,采集并处理数据的设备,往往是廉价、省电、计算能力较低的便携设备。而负责处理(即解压缩)信息的过程往往在更高计算能力的大型计算机上进行。也就是说,我们是在用廉价节能的设备来处理复杂的计算任务,而用大型高效的设备处理相对简单的计算任务。

压缩感知可以解决这样的矛盾,从尽量少的数据中提取尽量多的信息:如果数码相机镜头收集到了大量的数据,然后在压缩时丢弃掉90%的数据,何不一开始收集数据就丢弃那90%的数据,直接采集去除冗余的信息,不仅可以省去了压缩的麻烦还能节省电量和空间。类似的在医学上,压缩感知可以显著减少断层扫描(CT)或磁共振成像(MRI)测量次数。

所以压缩感知理论是信号处理领域一次颠覆性的飞跃,它提出了一种新的信号采集或者测量方式:在信号满足稀疏性假设的前提下,可以以低于Nyquist标准对其采样,并且有一种算法可以足够精确地恢复出原始信号,即信号的采集可以突破Nyquist频率的限制。

compressed sensing

最后收集了一些压缩感知的资料,要狂补数学TT:
1. Rice大学的Compressive Sensing Resources,最权威最全面的Compressive Sensing资源主页
2. An Introduction to Compressed Sensing,Emmanuel Candes在斯坦福的课程
3. Emmanuel Candes教授“21世纪计算”大会演讲:压缩感知,信号采集的重大突破
4. 陶哲轩的compressive sensing课程
5. Igor Carron收集的Compressive Sensing: The Big Picture, Compressed Sensing Listing, Compressive Sensing Videos, Compressive Sensing Codes
6. cvchina压缩感知的系列文章,包括CMU关于Compressive sensing的课件
7. 松鼠会科普文章:压缩感知与单像素照相机填补空缺——压缩感知

投票理论和Arrow不可能性定理

chaotic elections我们想当然认为公平的制度,在逻辑推理面前不堪一击。投票理论的水也好深!

排序投票制
考虑一个简单的例子,假设选举有ABC三个候选人,选民对这三个人的内心偏好列如下:
2人认为A>B>C; 3人认为A>C>B; 2人认为C>B>A; 4人认为B>C>A
按照一票制,A得5票,B得4票,C得2票,A当选。
按照两票制(最优+次优),A得5票,B得8票,C得9票,C当选,原先票数最高的A反而垫底。
还有数学家J. Borda在法国大革命时期批评法兰西科学院选举制度时提出的Borda计票法。Borda认为如果每个人只投一票或者更多票不公平,他建议每個选民依照喜好排序候选人,在有三个候选人的情况下,每个人给心目中的最优者投两票,次优者投一票,第三名不投票。按照Borda计票法,结果会变成A得10票,B得12票,C得11票,最后当选的是B。

以上三者都可以看成排序投票制的特例,所谓排序投票制就是每个人给候选人在心中排好一个偏好次序,然后给每个次序上的人投一定票数。而数学家Donald G. Saari提出(暂没找到paper):

如果有n>3名候选人,可以使得在选民偏好不变的情况下,构造一个排序投票制让任何候选人都通过选择一个合适的排序投票制当选!

孔多塞制和孔多塞投票悖论
投票理论在法国大革命时期浮现成为学术界的一门研究领域,除了J. Borda外,还有另一位投票理论家孔多塞Condorcet,有意思的是他反对Borda计票法,他提出的是一种成双比对法,孔多塞制:将每个选项与所有其他的选项成对比较,一次一个,而击败所有其他选项的选项便是赢家。只要一个选项在大多数选票上的位置高于另一个选项,那么它便击败了那个选项。

当候选人n>2时,以投票的多数规则来确定社会或集体的选择可能产生循环的结果。假设有三个选举人对三个候选人倾向如下:A>B>C; B>C>A; C>A>B。多数人偏好A>B,多数也偏好B>C,按照逻辑上的一致性,这种偏好应当是可传递的transivity,即多数人偏好A>C。但实际正好相反,多数人偏好C>A。没有一个能够获得多数票而通过,这就是孔多塞投票悖论

投票制度的混沌性
考虑淘汰制的选举,假设选举有ABC三个候选人,选民对这三个人的内心偏好列如下:
35人认为A>C>B;33人认为B>A>C;32人认为C>B>A
可以有三种不同的选举顺序:
1. AB进行PK,A得到35票,B得到65票,B胜出。本来很想投C的人只能投给次优的B。然后BC进行PK,B只得到33票,C得到67票,C胜出。
2. AC进行PK,A得到68票,C得到32票,A胜出。然后AB进行PK,B胜出。
3. BC进行PK,B得到33票,C得到67票,C胜出。然后AC进行PK,A胜出。

所以在淘汰赛制中,选举制度最终结果和选举顺序不同,简单淘汰制度的选举容易被操纵,尤其是当选民的意向比较平均的时候,只要选举的顺序被精心安排,任一选手都有可能最后胜出!

同样是上文的例子,如果采用一票制,A得到35票,B得到33票,C得到32票,A胜出。假定排名最后的C突然退出选举,是否要因为退出一位排名最后的选举人进行重新选举?如果进行重新选举,则A得到35票,B得到65票,B反而胜出。

这个两例子反映出投票制度的混沌性,或者说结果对扰动的敏感依赖性:某一个次要竞争者的变化,也许会影响到重量级竞争者的崛起或者覆灭。一个类似但是复杂得多的例子是在2008年年初的民主党党内初选中,希拉里和奥巴马双雄鼎立,希拉里略占优势。而爱德华兹一直屈居第三,终于在“超级星期二”来临之前的1月底宣布退出竞争,他的退出很快打破了希拉里和奥巴马的平衡,部分地促成了奥巴马在超级星期二之后的十连胜,最终逼得希拉里退选。

Arrow不可能性定理
1972年诺贝尔经济学奖的获得者Kenneth Arrow在《社会选择与个人价值》中,考虑的是比选举更为细致的社会福利函数Social welfare function,给定一个集体中每个成员对候选人一组偏好顺序序列,那么一个“社会选择机制”能够在多好的程度上得到一个综合的排序,输出一个整合了各种意见的排序?

一个合理的选举制度,它必须满足一些条件:
1. 帕雷托最优
如果在每个人的排序中A都优于B,在输出结果中A也应当优于B。
2. 无关因素独立性
假设社会福利函数返回的排序中,A在B的前。但这时某些投票的人对A、B外的第三人C的看法变卦了,不应当影响到结果中A和B的相对排序,社会福利函数的结果A还是在B的前面。
3. 非独裁性
这个函数的输出意见不能总是等于同一个人的输入意见,不存在一个人的意见总是凌驾于所有人的意见之上。反过来,独裁性就是指社会福利函数最终返回的结果,恰好和某个投票人的个人意向完全相同,那么就说明那个人独裁了这一次的选举,“被独裁”的选民很有可能对独裁这件事并无兴趣或一无所知,就如鸽笼原理,只是恰好落到了他头上而已。

最后Arrow得出的结论是,只要有三个或更多的候选者,就不可能存在一个函数,或者说社会选择机制,同时满足帕雷托最优、无关候选人独立性以及非独裁性这三个条件。

三个条件里最苛刻的是其实是无关因素独立性,受制于投票机制的混沌特征,是非常难于满足的。所以不管是投票还是民主集中制,我们都不可能通过公共选择的方式获得一个所有人都认同的、逻辑一致的价值。

最后是一些参考:Arrow不可能性定理今天你想投票了吗社会选择理论

比赛中的数据可视化

上个月在Kaggle看到一个关于Kaggle自己的leaderboard数据可视化任务:表格形式反映比赛排名太枯燥,如何可视化地反映出比赛中随时间交替排名激烈的竞争场面?

To an observer, the leaderboard is a spreadsheet. They see funny team names, numbers with too many decimals, strange column titles, and none of the history behind the battle. We run a veritable nerd olympics, but instead of smashing the 100m world record, we're elbowing for a few decimal places of some esoteric quantity called a capped binomial deviance. It's faceless. It's cold. It fails to tell the story of the battle. And you know what that means?This means war.

提交上来的候选作品思路都差不多,时间为横轴排名为竖轴,可以一目了然看出排名随时间的变化趋势,并且也很容易看出一个队伍是从什么时间点加入比赛的,老外管这个叫Bumps Chart,还跟英国剑桥牛津的划船赛有关。后来Bumps Chart其实就曲线图,但是特别在只有两个时间点。

battles of the best

还有一个比较特别的作品使用Bubble Chart,横轴是每支队伍竖轴是比分,每个泡泡表示一个提交,加入比赛的时间点特别标出。想到ACM比赛就可以这么进行数据可视化处理(当然现在的表格表示挺好的):比赛队伍/通过的题目数/提交次数/程序耗时/时间有五维,比赛队伍用不同颜色泡泡表示,通过的题目数是竖轴,程序耗时是横轴,提交次数可以用泡泡大小来表示,最后时间轴左右拖动显示一个时间点的比赛状态。可以参照Hans Rosling在2006年TED大会上的演讲:数据可视化透视世界发展状况。
kaggle WaterGunRaceChart

经久不绝的问题 洞穴奇案

美国著名法学家富勒在《哈佛法律评论》中提出了一个虚拟的人吃人案件,这个名为"洞穴探险"的极端案例被称为"史上最伟大的虚拟案例"。
案例简述:省略很多细节,推荐阅读富勒的原文THE CASE OF THE SPELUNCEAN EXPLORERS中文Wiki版本,很详细。

4299年5月上旬,在纽卡斯国,五名洞穴探险人不幸遇到塌方,受困山洞,等待外部的救援。十多日后,他们通过携带的无线电与外界取得联络,得知尚需数日才能获救,但水尽粮绝,为了生存,大家约定通过投骰子吃掉一人,牺牲一个以救活其余四人。威特摩尔是这一方案的提议人,不过投骰子之前又收回了意见,其他四人却执意坚持,结果恰好是威特摩尔被选中,在受困的第23天威特摩尔被同伴杀掉吃了。在受困的第32天,剩下四人被救, 随后他们以故意杀人罪被起诉,初审法庭经过特别裁决确认上面所述的事实,根据《刑法典》规定:"任何故意剥夺他人生命的人都必须被判处死刑。"法官判定四位被告谋杀威特摩尔的罪名成立,判处绞刑。

因为其涉及到法律的"本性",甚至是超出法理哲学讨论的范围,像放大镜一样照出了隐藏在道德、法律、规则、正义、文化和制度之间"剪不断理还乱"的紧密联系:
法律在何种条件下才能体现其本意? 在什么条件下牺牲某些人的利益以换取其他人的生存这种做法才能够被接受? 在利益冲突的时候,谁有权威仲裁利益双方行为的合理性? 法律、道德、正义的区别和联系? 在远离社会的自然状态下,社会的法律是否具有管制效力? 如果答案为否,那么当幸存者回到人类社会的时候,该社会的法律是否具有审判他们行为的"合法"权威?...

富勒还在案例后构造了最高法院五名大法官的五份判决意见,(二有罪二无罪一弃权,最高法院五位法官立场2:2的平局,意味着初审法院的判决得到维持,四名被告人被执行死刑),总结出五种不同的法理观点,代表了法理哲学中的五个流派。每一种观点都振振有词,具有合法或者合理的逻辑基础。
1998年,美国法学家Peter Suber重提洞穴奇案。根据过去几十年法理哲学理论的进展,又增加了九名虚拟大法官(四有罪四无罪一弃权),一共总结出14种不同观点。实际上,洞穴奇案至今也没有统一的答案。

PS: 历史上的两个真实案例:1842年美国诉霍尔姆斯案(United States v. Holmes) 和1884年的女王诉杜德利与斯蒂芬案(R v Dudley and Stephens)

情人节特别课堂: 稳定婚姻问题

趁着情人节的气氛,给大家介绍一个有趣的问题:稳定婚姻问题,青春期的GGMM一定要看...hehe会有收获的^^
这个问题曾在一个OIER的空间里看到过,他讲得是班级的男女生谈朋友的配对==....其实就是这个问题,可惜现在找不到那个空间了orz...不过这两天发现科学松鼠会的一篇文章我要我们在一起介绍了这个问题,于是自己修改了下,来给GGMM们上课啦,有空还准备编个程玩玩。
(PS:以前还讨论过最佳约会策略(摘取最大麦穗),也推荐青春期的GGMM去受教~~)

稳定婚姻问题The Stable Marriage Problem最早是由两个美国数学家David Gale&Lloyd Shapley于1962年在American Mathematical Monthly上提出的,这个问题和图论有关(求完全二分图的稳定完备匹配,这是一个NP问题)。对于以前没有接触过这个问题的人,这个理论最出人意外的结论是:传统的求爱、结婚过程是male-optimal(男生主动)的,也就是说,男性能够得到尽可能好的心上人,女性却不然。这里我们就不科普了,直接上问题:

给定若干个男生和同样多的女生,他们每个人都对所有的异性有一个心理的偏好次序(无并列)。具体点说就是每个男生都凭自己好恶给MM排个名次:我最爱a,其次爱b,再次爱c...同样,每个MM也同样给每个男生打分。
问题1:是否存在一种男女配对组合构成一种稳定的组合关系? 稳定组合的意思是说,不存在两个非伴侣的异性对彼此的评价比对各自伴侣的评价还要高。
问题2:在已知每个人对异性的偏好顺序的情况下,怎样求出这种稳定组合方式?(如果它存在的话)

对于以上两个的问题的答案当然是肯定的。Gale 和Shapley不但提出了这个问题本身,而且给出了一种著名的解法Gale-Shapley算法(延迟认可算法)
激动人心求婚过程是这样进行的(如果觉得太快了的话,那就认为是表白吧):
第一天,让这些男生去向他们最心仪的女生表白。等所有男生表白完毕后,所有的收到表白女生们都从自己的表白者中选择自己最喜欢的人接受为男朋友。没人表白的女生只能暂时等一等了,不要着急,表白会有的。以上过程称为“一轮”。之后的每一轮都按照类似的方式进行。
第二天还处于单身状态的男生们每个人再次向自己还没有表白过的女生中自己最喜欢的人表白(无论人家是否已经有了男朋友),然后,等所有单身男生表白完毕后,所有的收到表白女生们都从自己的表白者中选择自己最喜欢的人接受为男朋友。如果原来有男朋友而表白者中有自己更喜欢的,不要犹豫,换之。等到尘埃落定之后,再开始如上所述的新的一轮表白。
依此类推。可以证明的是,这个过程一定是会终止的,也就是说,不会陷入任何死循环。并且一旦终止,每个人都会找到一个伴侣。更关键的是,这个过程最终得到的一定是如前所述的“稳定组合”。

真正有趣的部分还在后面。 ... Read More

close