CAP定理和NoSQL

CAP定理(CAP theorem)是由大牛 Eric Brewer 在2000年PODC上首次提出的。起先它是个猜想,Brewer 认为在分布式计算系统中对某个数据不存在一个算法同时满足数据一致性(consistency),读操作是否总能读到前一个写操作的结果,即是说在分布式环境中,多点读出的数据是否是同一份最新的数据副本;可用性(Availability),时刻能进行对数据的读写访问,所有的请求都应该成功并且收到返回;分区容错(partition-tolerance),无论任何消息丢失,系统都可用。2002年 Gilbert 和 Lynch 证明了 Brewer 的猜想使之成为了定理。

NoSQL 一定程度上就是基于这个理论提出来的,因为传统的关系型数据库都具有 ACID (原子性、一致性、隔离性、持久性)属性,对一致性要求很高。NoSQL 数据库都以水平扩展著称,为了提高系统性能和可扩展性,所以在 CAP 的选择上面,都倾向于坚持P,牺牲C(consistency)或牺牲A(Availability)来进行设计。

CAP选择
考虑CA:放弃 partition-tolerance 意味着把所有的机器搬到一台机器内部,一旦某个操作失败,整个系统就出错。代表是传统的关系型数据库、Vertica(Column-oriented)等,这些数据库对于分区容忍性方面比较不感冒,主要采用复制(Replication)来保证数据的安全性。
考虑CP:这种系统将数据分布在多个网络分区的节点上,并保证这些数据的一致性,但是对于可用性的支持方面有问题。一旦遇到 partition 事件,受影响的服务需要等待数据一致,因此在等待期间就无法对外提供服务,只能对部分数据进行读写。在多个节点上控制这一点会相当复杂,像 Google 的一般做法是将主分区归属在单一个数据中心里面,然后交给 Paxos 算法去解决跨区域的问题。代表有 BigTable(Column-oriented)、HBase(Column-oriented)、MongoDB(Document)、Redis(Key-value)。
考虑AP:系统只要每次对写都返回成功,对读都返回固定的某个值。Werner Vogel(Amazon CTO)认为不一致是可以容忍的,这有两个理由:一是可以在高并发条件下提高读写性能;二是处理一些分区状况——多数决模型(majority model)有可能使系统的一部分表现为不可用,虽然那些节点正运行良好。他在2008年发布在 ACM Queue上 的一篇数据库方面的重要文章,阐述了 NoSQL 数据库的理论基石——最终一致性(Eventual Consistency)。Quorum NRW策略和Gossip协议可以用来维护最终一致性。这类系统的代表有 Dynamo(Key-value)、Voldemort(Key-value)、Cassandra(Column-oriented)。

CAP 的三选二也不是绝对的非黑即白的有或无,这三种性质都可以在程度上衡量:可用性在0%到100%之间连续变化的,一致性分很多级别,连分区也可以细分为不同含义。虽然不可能在同一时刻满足 Consistency、Availability 和 Partition-tolerance 全部的3个要求,但是 Guy Pardon 的文章 A CAP Solution(Proving Brewer Wrong 将条件放松到系统可以分时达到 CAP,提出了一个满足 CAP 的解决方案。Twitter 的首席工程师 Nathan Marz 的文章 How to beat the CAP theorem 提出正是因为要不断的更新数据库中的数据,再加上 CAP ,才导致那些即便使用最终一致性的系统也会变得无比复杂。如果系统中不存在会改变的数据(append-only immutable data),所有的更新都作为创建新数据的方式存在,数据的处理由 CRUD 变为 CR,把读数据转化为一次请求(对整个数据集执行一个函数操作),这样就可以避免最终一致性的复杂性,转而拥抱 CAP。

卷积神经网络

卷积神经网络(Convolutional Neural Networks:CNN)是人工神经网络(ANN)的一种,是深度学习的一种学习算法。它在图像识别和分类、自然语言处理广告系统中都有应用。

有意思是,卷积神经网络的提出其实就是来自于生物视觉模型。1981年的诺贝尔医学奖,颁发给了David Hubel、Torsten Wiesel。他们的工作给人们呈现了视觉系统是如何将来自外界的视觉信号传递到视皮层,并通过一系列处理过程(包括边界检测、运动检测、立体深度检测和颜色检测),最后在大脑中构建出一幅视觉图像。这个发现激发了人们对于神经系统的进一步思考,神经-中枢-大脑的工作过程,或许是一个不断迭代、不断抽象的过程。如下图所示,从原始信号摄入开始(瞳孔摄入像素Pixels),首先进行初步处理(大脑皮层某些细胞发现边缘和方向),抽象(大脑判定眼前的物体的形状是圆形的),然后进一步抽象(大脑进一步判定该物体是只气球)。

convolutional deep belief network

六十年代的生理学的发现,促成了计算机人工智能在四十年后的突破性发展。1989年,Yann LeCun (纽约大学教授,现Facebook AI研究室主任) 提出了卷积神经网络,这是第一个真正成功训练多层网络结构的学习算法,但在当时的计算能力下效果欠佳。直到2006年,Geoffrey Hinton提出基于深信度网(Deep Belief Net)和限制波尔兹曼机(Restricted Boltzmann Machine)的学习算法,重新点燃了人工智能领域对于神经网络的热情。

卷积神经网络现在计算机视觉领域表现出众。ImageNet Classification with Deep Convolutional Neural Networks,这篇发表于NIPS2012的文章,是Hinton与其学生为了回应别人对于Deep Learning的质疑而将CNN结合GPU并行技术用于Imagenet Challenge(图像识别目前最大的数据库,被誉为计算机视觉圣杯),最终取得了非常惊人的结果。他们的算法在2012年取得世界最好结果,使分类错误率从26.2%下降到16%。2013年Matthew Zeiler的算法继续将错误率下降到11.2%。Matthew Zeiler还创立了Clarifai,让我们可以有机会使用他们的图像识别算法对图片标注分类或图像搜索。

imageNet classification with CNN
The convnet from Krizhevsky et al.’s NIPS 2012 ImageNet classification paper.

在月初Kaggle结束的Galaxy Zoo challenge中,参赛者要对星系图像进行分类(Spiral/Elliptical, Merging/Not merging, Clockwise/Anti-clockwise),获胜的算法也是使用了卷积神经网络。Sander Dieleman已放出了代码和详尽的文档: My solution for the Galaxy Zoo challenge

2014年3月,Facebook刚刚公布了他们在CVPR2014的文章:DeepFace: Closing the Gap to Human-Level Performance in Face Verification。他们用四百万人脸图片训练了一个九层的卷积神经网络来获得脸部特征,神经网络处理的参数高达1.2亿。他们在著名的公共测试数据集LFW(labeled face in the wild,1:1地判断是否两个照片是一个人)上达到了97.25%的正确率。这个数字已经基本接近人眼的辨识水平。北京Face++团队的算法达到97.27%的正确率,在美图秀秀中就有应用,他们的主页提供了API、demo展示和论文。现在的最新进展是,香港中文大学基于 Fisher Discriminant Analysis的算法将Face Verification正确率提高到98.52%,超过了人类水平(97.53%)。

faceplusplus system overview
System overview in Face++ paper in ICCV2013

除了计算机视觉领域,卷积神经网络在人工智能和robotics也有很大潜力。Hinton的另外一个学生创立了人工智能公司DeepMind,没有商业产品,只凭一篇论文,就已被Google招聘式收购。 他们使用深度学习(CNN)结合强化学习(Reinforcement Learning),在Stella模拟机上让机器自己玩了7个Atari 2600的游戏,结果不仅战胜了其他机器人,甚至在其中3个游戏中超越了人类游戏专家。很有意思,具体可以见InfoQ的看DeepMind如何用Reinforcement learning玩游戏,以及论文原文Playing Atari with Deep Reinforcement Learning

2014年公开课计划

整个寒假都没有可以跟的课,老外果然都过圣诞节去了。新的一年有三门课非常给力:Convex Optimization、Statistical Learning和Networks, Crowds and Markets。

Convex Optimization的老师是经典教材《Convex Optimization》的作者Stephen Boyd。

Statistical Learning,老师是Trevor Hastie和Rob Tibshirani,俩人都是大名鼎鼎的《The Elements of Statistical Learning》、《An Introduction to Statistical Learning, with Applications in R》作者之一。《The Elements of Statistical Learning》的另一个作者Jerome Friedman发明了Gradient Boosting。

edX上Networks, Crowds and Markets在3月3日开课,这门课的老师也很强大:Cornell的Jon Kleinberg, David Easley, Eva Tardos。Jon Kleinberg是社交网络研究的神牛,2013年还拿了ACM SIGKDD 2013 Innovation Award。David Easley和Jon Kleinberg合著了《Networks, Crowds and Markets》;Eva Tardos和Jon Kleinberg合著了《Algorithm Design》的作者。这两本都是我比较喜欢的教材。《Networks, Crowds and Markets》之前读到一半,正好这次可以跟着课把书读完。

椭圆曲线和Dual_EC_DRBG后门

这两天爆出NSA收买RSA将NSA推荐的算法,Dual_EC_DRBG,设置为BSafe中默认的随机数生成算法。为了推广这种算法,其实早在2007年NSA就执意将其写入了NIST(美国国家标准技术管理委员会)的确定性随机数生成器推荐标准(Special Publication 800-90,SP800-90),即使它速度极慢。同年Dual_EC_DRBG就在Crypto 2007会议上被指出存在被植入后门的可能,但不能认定算法设计者是否知道后门的参数,也不能认定NIST有意在算法中植入后门。2013年9月Edward Snowden泄漏的内部备忘录显示NSA曾向某加密算法植入后门,再到12月路透社爆出RSA被收买,现在看起来是NSA精心选取参数值下后门。有意思的是,比特币也使用了ECC来生成随机数,但是比特币神秘创始人中本聪在2009年发明比特币的时采用了小众的secp256k1的曲线参数而不是有问题的secp256r1(NIST P-256),神奇地躲过了密码学子弹。
那么Dual_EC_DRBG漏洞在哪,为什么随机数生成器的漏洞会让加密算法被攻破?先要从椭圆曲线和随机数生成器说起。

椭圆曲线
椭圆曲线密码学(Elliptic curve cryptography,ECC)由Koblitz和Miller分别独立提出,是迄今为止安全性最高的一种公钥密码算法。椭圆曲线E的形式是:

$$y^2=x^3+ax+b, a,b \in F_p$$

有限域Fq,q一般是2的m次方或大素数p,也可以是某素数p的m次方。参数a,b确定椭圆曲线E。
它的安全性基于有限域椭圆曲线离散对数问题(Elliptic Curve Discrete Logarithm Problem,ECDLP)的难解性:
给定素数p和椭圆曲线E,对Q=dG,在已知G,Q的情况下求出小于p的正整数d。可以证明由d和G计算Q容易,而由Q和G计算d则是指数级的难度。
G对应为椭圆曲线E的基点,d为私钥由自己选择,然后生成对应公钥Q=dG,得到密钥对(d, Q),私钥自己保存,(p, a, b, G, Q)是已知的,但是由p和G计算私钥d很难,保证了加密算法的强度。
还有2种公钥密码体制分别基于大整数分解问题(Integer Factorization Problem,IFP)的难解性,如RSA,和有限域离散对数问题(Discrete Logarithm Problem,DLP)的难解性,如Diffie-Hellman、ElGamal。但是ECC问题要比DLP问题更难解,并且ECC用更少的密钥长度提供相同的加密强度。
这次出问题的Dual_EC_DRBG,全称Dual Elliptic Curve Deterministic Random Bit Generation,是基于椭圆曲线的确定性随机数生成器。

随机数生成器
随机数在密码学中具有十分重要的地位,被广泛用于密钥产生、初始化向量、时间戳、认证挑战码、密钥协商、大素数产生等等方面。随机数产生器用于产生随机数,分为非确定性随机数生成器和确定性随机数生成器两类:
非确定性随机数生成器(NRBG)基于完全不可预测的物理过程。确定性随机数生成器(伪随机数生成器,DRBG)在指定初始种子之后,利用某些算法产生一个确定的比特序列,“确定性”因此得名。如果种子是保密的而且算法设计得很完善,那么可以认为输出的比特序列是不可预测的。
加密算法需要高度随机性的“种子”来生成密钥,因此随机数生成器会直接影响加密强度和安全性,脆弱的随机数生成器被攻破会击溃整个加密算法,比如Android随机生成数字串安全密钥中的漏洞就导致了部分比特币的失窃。

Dual_EC_DRBG后门
这个后门的发现可以追溯到六年前,NIST在2007年发布了确定性随机数产生器推荐标准SP800-90修订版。这是一个推荐性的标准,描述了一些产生随机比特流的方法,这些随机比特流可能被用于直接或者间接的产生随机数,并用于相关使用密码学的应用中。NIST SP800-90提供了4种标准算法:Hash_DRBG(基于SHA系列算法)、HMAC_DRBG(基于HMAC函数)、CTR_DRBG(基于分组密码函数AES)、Dual_EC_DRBG(基于椭圆曲线)。
在4个月后的Crypto 2007会议上,Dan Shumow和Niels Fergusonsuo作了一个报告,宣称标准中的Dual_EC_DRBG设计存在严重漏洞,具体可以参看报告On the Possibility of a Back Door in the NIST SP800-90 Dual Ec Prng…智商不够用了,我的理解是:
P, Q是ECC上两个基点,且满足eQ=P,点Q常量可以确定万能钥匙。如果攻击者知道私钥d满足Q=dP,计算eQ=P是容易的,存在a*e=1 mod p。反过来如果攻击者知道e,以及一些已知的随机值,攻击者可以计算出点G,然后可能能确定DRBG的内部状态,并预测DRBG后来的输出。一个“局外人”可能并不知道这种特殊关系的存在,但是如果知道了P和Q之间关系的“密钥”,攻击者可以利用Dual_EC_DRBG存在的后门得到该算法后续所有的随机数值,从而破坏不可预测的性质,预测其使用的密钥,进而攻破整个加密算法。

DES S-BOX的传说
DES中S盒来路不明是密码学届的一个著名的谜团,也和NSA有关。1975,IBM刚搞出DES(Data Encryption Standard)时候,NSA就对S-Box做了修改,并将密钥长度由128bit缩减为56bit,但未说明原因,直到80年代差分分析被公开学术界发现后,人们发现针对DES16轮的差分攻击效率甚至不如穷举,于是怀疑在设计DES的S盒和加密轮数时,差分攻击的方法就已经被发现了,而NSA那个修改证明是为了对抗可能的差分分析。

神经网络与数据压缩

神经网络除了用于Regreesion和Classification,还可以与用于数据压缩Data Compression。自联想神经网络Auto-Associative Neural Network是三层BP网络,它的特点是输出是对输入的一种重构,即输出等于输入或者允许输入输出有一定的误差存在。如果中间层Hidden Layer节点少于输入层Input Layer,中间层可以用更少节点表示输入层的数据同时可以在输出层重构出输入层数据,这就是数据压缩和解压的过程。

从另一个角度来看,中间层提取出数据中最重要的特征,用更少维度表示输入数据。如果我们在网络中不使用sigmoid函数,而使用线性函数,这就是主成分分析PCA模型。

在深度学习中,上述结构被称作自编码神经网络Autoencoder Neural Network。

压缩感知

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

真正有趣的部分还在后面。 继续阅读“情人节特别课堂: 稳定婚姻问题”