Arrow不可能性定理

Thu 05 February 2015

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

一个合理的选举制度，它必须满足一些条件：

1. 帕雷托最优 如果在每个人的排序中A都优于B，在输出结果中A也应当优于B。

2. 无关因素独立性 假设社会福利函数返回的排序中，A在B的前。但这时某些投票的人对A、B外的第三人C的看法变卦了，不应当影响到结果中A和B的相对排序，社会福利函数的结果A还是在B的前面。

3. 非独裁性 这个函数的输出意见不能总是等于同一个人的输入意见，不存在一个人的意见总是凌驾于所有人的意见之上。反过来，独裁性就是指社会福利函数最终返回的结果，恰好和某个投票人的个人意向完全相同，那么就说明那个人独裁了这一次的选举，“被独裁”的选民很有可能对独裁这件事并无兴趣或一无所知，就如鸽笼原理，只是恰好落到了他头上而已。

Arrow不可能性定理充分反应出个人决策和群体抉择之间的巨大差异,表明在社会事务中想要做出令人满意的集体决策几乎是不可能的。Muller—Satterthwaite不可能性定理则从不同的角度进一步说明设计一个合理的集体决策规则是多么的困难。这些不可能性定理所预示的结论是悲观的。

fail-fast 和 fail-safe 机制

Wed 19 November 2014

fail-fast 机制是 Java 集合 (Collection) 中的一种是一种错误检测机制，JDK 并不保证 fail-fast 机制一定会发生。如果在迭代器迭代的过程中会检查对集合的结构进行任何的修改，每次获得下一个元素时，如果发现有任何修改，会立刻抛出异常 ConcurrentModificationException，而不是等遍历完了再抛出异常。所有迭代器的实现都是快速失败的设计。

快速失败 fail-fast 和故障安全 fail-safe 之间的不同是什么？

迭代器故障安全 fail-safe 以克隆方式工作，因此它不会影响集合中的任何修改。所有 java.util 包中的集合类都是 fail-fast，而 java.util.concurrent 中的类比如 CopyOnWriteArrayList 都是 fail-safe。

Contrary to fail-fast Iterator, fail-safe iterator doesn't throw any Exception ...

卷积神经网络

Sat 26 April 2014

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

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

六十年代的生理学的发现，促成了计算机人工智能在四十年后的突破性发展。1989年，Yann LeCun (现纽约大学教授，FacebookAI研究室主任) 提出了卷积神经网络，这是第一个真正成功训练多层网络结构的学习算法，但在当时的计算能力下效果欠佳。直到2006年，Geoffrey Hinton提出基于深信度网 ...

2014年公开课计划

Sat 04 January 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日开课，这门课的老师也很强大 ...

椭圆曲线和Dual_EC_DRBG后门

Fri 20 December 2013

这两天爆出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 ...

神经网络与数据压缩

Sat 19 October 2013

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

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

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

压缩感知

Thu 27 June 2013

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

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