Archive for the ‘Uncategorized’ Category

随想

October 12, 2012

不爱看哲学了,尤其是认知论方面,因为已经远远落后于自然科学的发展。

爱看伦理,法律,政治之类。更现实,也更前沿。受justice的影响?

不太喜欢抽象的东西了,更喜欢看关于具体事例的讨论。

但还是记不住细节。工作里太多细节,在业余爱好中要躲开。

苏菲的世界太罗嗦了,对话体信息量太低了。是我的爱好变了还是要求高了?

时间越来越少,没法耗在尝试上。所以书看得越来越少,因为越来越挑。不是好事。要能找到个志同道合口味相近的就好。

为啥就没有和justice类似的课程呢。

TED没啥好啊。大部分都浅尝辄止,吸引眼球多,真正有趣的东西少。为啥大家都这么推崇?

What is the right thing to do 1: The first question of Prof. Sandel.

April 13, 2010

 

Justice: what is the right thing to do is a series of public lectures currently being given at Harvard on morality. The lecturer is Michael Sandel, who is known for his review for the book Theory of Justice. He has been teaching this Justice course at Harvard for the last 20 years. It has been a hit, not only on the campus of Harvard, with a record-breaking 1115 audiences in 2007, but also, rather unexpectedly, among the Chinese blog community.

I think one of the reasons why such a scholastic course gains global popularity is that, Prof. Sandels raised a very interesting and indeed intriguing question at the very beginning of the course. (Description of the killing 6 vs. killing 1 question, and the classroom discussion thereafter)

At first glance, this seems to be an easy question which has an obvious answer. But the answer is not obvious any more if you are asked to base your answer on solid, consistent principles of justice. blah blah

What is justice? What is the just thing to do in various situation? The most tempting answer is Utilitarian’s view: to do whatever maximizes the total welfare of the society. This is in fact the answer by Adam Smith and marks the beginning of modern economics. (need opinions from the professionals). But people has realized that this is only part of the story; fairness is, in many situations, as important as efficiency.

Coincidentally (or not?), there is a similar transition in the engineering field. There has long been a sub-field(profession? community? theory?) devoted specifically to maximizing efficiency, namely operation research, which I happen to be working on. But recently, the operation research community has been putting more and more effort on the issue of fairness and trying to rigorously quantify the tradeoff between fairness and efficiency. (Example from airs traffic). See also the paper by my advisor’s advisor.

More links related to the course:
– Course website: link
– The official lecture videos on Youtube (in English): link
– An introduction of the lecture by a Harvard CS professor Mitzenmacher, who has taken the course himself year ago: link
– An introduction from a blog in Chinese: link
– The lecturer is also invited by the Carnegie Council to join discussions with other well-known scholars: link

优化与分离的等价性(1)

November 14, 2009

优化与分离的等价性(The equivalence of optimization and separation)是凸优化中非常基本也是非常NB的一个定理。说基本是因为它告诉我们在一个凸集上做优化时,这个凸集的哪些信息真正需要的?说NB是因为我们所需要的信息时如此之少:我们不需要知道这个凸集的顶点,不需要知道它的形状,甚至我们不需要关于这个凸集的一个显式的描述,我们需要的只是以下这种能力:给定一个点,断言这个点在凸集内,或者找到一个超平面能够把这个点跟凸集分离开来。优化与分离的等价性揭示了凸优化的一些最本质的性质。

这个描述起来很简单的结果,其证明却涉及很多技术细节。本文只介绍证明的基本直观思路,这一结论的完整证明,公认最好的参考书是Grotschel, Lovasz和Shrijiver的Geometric Algorithms and Combinatorial Optimization。

本文分为两部分,第一部分介绍分离=>优化的证明,第二部分介绍优化=>分离的证明。

当然在证明之前,需要说明何为优化,何为分离,何为等价。这里假设K是我们要考虑的凸集。

这里的优化特指对线性目标函数的优化:给定c, 找出K里的一个x,使得对于K里的任何点y,都有c*x <= c*y。也就是说,我们要找到一个可行的x使线性目标函数c*x在K上最小。

所谓分离,是指对于任何给定的点x,我要么能正确地断言断言y在K里,否则,如果x不在K里的话,我能找到一个超平面,使x和K分别在超平面的两边。也就是说,我能找到这么一个c(超平面的法向量),使c*x <= c*y对于K里的所有y都成立。

所谓等价,指的是多项式时间上的等价:假如我有分离的能力,那么我只要进行多项式次的分离,就能完成优化的任务;反之亦然。

由于计算机上只能进行有限精度的计算,所以上面的优化和分离的等价都是在有限精度的意义上说的(亦即所谓的弱优化与弱分离)。具体而言,对有优化,我们不需要找到真正最优的那个x,而只需要“几乎最优”的那个x,也就是说,对于给定的误差e, 我们只需要找出K里的一个x,使得对于K里的任何点y,都有c*x <= c*y+e;对分离而言,我们只需要正确地断言x“几乎属于”K(x属于K或者x虽然在K外,但在K的边界附近一个厚度为e的“薄壳”内),或者找到一个超平面“几乎能分离”x和K(c*x <= c*y+e,对于K里的几乎所有y都成立,不成立的那些y都在K的边界附近一个厚度为e的“薄壳”内)。事实上,我们紧紧要求优化和分离只在有限精度上成立,是这一结果能得到证明的关键—-如果我们要求的是严格的优化和分离,我们反而无法证明我们的结论。

分离=>优化

如果我们具有分离的能力,如果能够利用这种能力去优化呢。证明最NB但也是最不直观的地方在我们能利用分离的能力来设计一种所谓椭圆算法(“Ellipsoid Algorithm”),利用椭圆算法,我们能把我们分离的能力转化为判断K中是否存在一个点x使c*x小于一个给定的值的能力。有了后面这种能力,利用二分法我们很容易就能(近似地)最小化c*x的点。

椭圆算法是如此之牛B,值得专开一段讲讲它的历史地位和理论意义。众所周知,Dantzig同学在六十年代某次做作业的时候顺手发明了解线性规划的单纯型算法。单纯型算法至今仍然是线性规划的最有效的算法。但不幸的是,单纯性算法在最坏情况下是指数级的。(当然,这种最坏情况在实际中很少出现,如何衡量单纯型法在实际中的平均性能,是当前武林另一绝学Smoothed Anaysis所研究的内容)。七十年代末八十年代初,苏联和美国的数位牛人Shor, Yudin, Nemirovski发明了椭圆算法,并以此证明了分离和优化的多项式等价性。然后Karmarkar将椭圆算法修改应用到线性规划上,得到了历史上第一个线性规划的多项式算法,从而证明LP是在P中。这一系列结果是如此地重要,并且在当时是相当出乎意料,以至于竟然上了纽约时报等新闻媒体的头条,这对于一项纯理论纯学术的成果来说是空前绝后的。然而椭圆算法虽然理论上是多项式,在实际中却效率很低,这与理论上是指数级但实际中效率很高的单纯型法正好相反。这一理论与实际的不符合一直在内点法(Interior Point Method)出现后才部分地得以解决。后来Nemirovski和Nemhauser发明了多项数级的解一般凸优化的内点法,从而证明凸优化也在P内,乃为后话了。

言归正传,椭圆算法干的这么一件事情。给定一个凸集K,假设我们有对于K的分离能力(所谓separation oracle),那么椭圆算法能够找到K里面的一个点,或者断言K是空的。椭圆算法的做法是构造一系列椭圆,这些椭圆都包含了K,并且体积一个比一个小。最后的那个椭圆要么其中心在K内(这个中心就是我们要找的那个点),要么椭圆的体积是如此至小,使它里面不可能再包含一个凸集K了。椭圆算法成功的关键在于以下五点:(1)给定一个椭圆,我们调用separation oracle就能判断椭圆的中心是否在K里,如果不在的话,separation oracle能够给出一个(经过椭圆中心的)分离超平面,利用这个分离超平面,我们能显式地再构造一个新的椭圆,它依然包含K(事实上,它是包含原来椭圆被超平面切下来那一部分的最小椭圆,所谓的Lower-John Ellipsoid),并且这个新的椭圆的体积比原来椭圆要小;(2)我们能够证明前后两个椭圆体积缩小的比率是一个常数,所以椭圆的体积是指数级下降的,从而即使最初椭圆的体积是指数级的,我们的算法仍然只需要进行多项式级那么多步;关于椭圆体积的证明利用到det(A)的一些上下界结果;3)以上算法能开始的前提是我们知道包含K的第一个椭圆,所以“优化=分离”必须加一个前提:我们知道包含K的一个大椭圆;当然如果K是一个由线性不等式给定polytope,这就不成问题,因为我们就能直接从线性不等式的系数中估计数这个大椭圆;(4)我们必须知道我们我们最后椭圆的体积小到什么程度后我们能够停止;对于K是polytope的情况,我们再一次能够从其线性不等式中得到这个K体积的一个下界,如果椭圆的体积(记住这个椭圆包含了这个polytope)小于这个下界的话,说明这个polytope只可能是空的;对于一般的凸集K,我们没有这个下界,但由于我们要求的只是近似的优化,所以我们只需要保证最后的椭圆的体积小到能够满足精度的要求就行;(5)椭圆算法所有计算都是有限精度的(包括开方和除法运算),我们能够证明,只要精度足够的高,我们的结论仍然成立,关于这一点的证明是最技术的部分。

现在,给了我们separation orale,我们就能实现椭圆算法。注意到如果拥有关于K的separation oracle,我们也就拥有了关于K‘的separation oracle,其中K‘是K和一个半平面交集。为了判断K中是否存在x使c’x大于等于给定的值b,我们令K’等于K和{y|c*y>=b}的交集。利用K’的separation oracle,我们能够实现关于K’的椭圆算法,算法有两种可能的结果:(1)算法找到K’中的一个点x,根据定义, x就是K中使c*x>=b的点;(2)算法找到一个椭圆,这个椭圆包含K‘,并且体积很小。由于这个椭圆的体积很小,我们能够保证K’即使不是空,它里面的点x也都满足c*x<b-e,亦即近似不能满足c*x>=b,这种精度的近似对于我们来说已经足够了。

综上所述,给定一个目标函数系数c和一个目标函数的界b,我们能近似地判断K里的点是否都满足c*x>b(这样的话c*x的最小值就比b大),或者找出一个使c*x<b的x(这样c*x的最小值就比b小)。利用二分法我们就能以任意精度找到使c*x最小化的那个最优解x。这样我们证明了(近似)分离=>(近似)优化。

这里我们再次强调,要在K上进行优化,我们只需要K的separation oracle,以及知道包含K的一个椭圆,除此以外,我们不需要知道关于K的任何其他全局或者局部信息。K是凸集保证了分离超平面的存在性。以上证明的直观idea是,每次调用separation oracle,我们都使我们搜索可行解得范围缩小,并且是指数级地缩小,最后这个范围是是如此之小,使这范围里面的点都是近似最优。

遗传算法与蒙娜丽莎

December 10, 2008

这几天我订阅的几个网站都在转载同一个消息:某人利用遗传算法,只用50个半透明的多边形就重现了达芬奇名画《蒙娜丽莎》(http://rogeralsing.com/2008/12/07/genetic-programming-evolution-of-mona-lisa/)。

这只是遗传算法一个很典型也很简单的应用,之所以引人关注,是因为作者利用图像这种可视化的方式直观地呈现出算法结果的质量。我觉得在教授遗传算法或全局优化的课上,这是一个很好的例子和练习。

这个例子让人觉得遗传算法确实”威力强大“。但”No Free Lunch Theorem“指出,在求解优化问题时,如果不利用问题结构的信息,任何算法在平均意义上都不比瞎猜更好。遗传算法之所在这个蒙娜丽莎问题上有不错的性能,是因为这个问题解空间的结构有一些很好的性质:

  1. 任何解都是可行解。换而言之,任何一种多边形的放置方式都是可以接受的。
  2. 相邻的解有相近的目标函数值。换而言之,如果多边形的放置方式相似,则所得到的画的效果(用与达芬奇原画的相似程度衡量)也相近。
  3. 目标函数的形状很好:最优解所在的峰远高于其他地方,很有可能几乎就是一个单峰函数,或者虽然是多峰,但这些峰的高度都接近最优解。因此,就算只是随便一个局部最优的解,看起来已经足够好了。

一个抛硬币的问题

November 24, 2008
网上看到的一个抛硬币问题,想了我一晚上,仍没有最终解决:
一个面朝上概率为1/2的硬币,抛2^k次,统计其中连续k个面出现的次数T_k。注意,我们允许重叠,如k=3时,”HHHHHTHH”的T_k=3。求k->infinity时,T_k的极限分布。
 
以下将连续抛n次硬币的结果看成长度为n的一个字符串。出现连续k个H称为一个“k连串”。
 
首先想到的是直接求分布。由于事件{字符串不含k连串}或{字符串含t个k连串}都不容易描述,所以试图用递归的方法。对于不含k连串的概率倒是能弄出一个递推公式来:
 
P(长度为n的字符串不含k连串) = (1/2)^2*[3+n-k-1 – \sum_{i=1}^{n-k-1}  P(长度为i的字符串不含k连串)]
 
但无法从上述递推公式推导出通项。似乎能证明P(T_k=0)的极限比1/2小。用matlab算了k=1,2,…,15时的P(T_k=0),似乎趋向于0.4。但更大的k就算不了了。
 
然后想到转换成一个马尔可夫链。令Xt={从t到t+k-1的子串}。譬如说对于k=2, “HHHTH”对应于X1=HH, X2=HH, X3=HT, X4=TH,或用二进制表示是11,11,10,01。可以证明{Xi}是马尔可夫链,状态空间是所有的k位二进制数,其转移矩阵是P(i -> (2i mod 2^k)) = P( i -> (2i mod 2^k) +1 ) = 1/2,P(其他)=0,或者说是长得像以下这个样子(记p=1/2):
 
  0
0
0
0
0
1
0
1
0
0
1
1
1
0
0
1
0
1
1
1
0
1
1
1
000            
001            
010            
011            
100            
101            
110            
111            
 
则T_k就是在2^k步内访问”111″的次数。由于题目要求极限分布,所以在想能不能用马氏链的极限性质来解决。这是个有限状态不可约链,所以是正常返的,其唯一的稳态分布是pi = (2^k, 2^k, …, 2^k),根据Ergodic Theorem,当步数趋向无限时,访问”111″的次数占总步数的比例almost surely趋向于1/2^k。这一结论让我猜测2^k步内访问”111″的次数(即T_k)也趋向于1,即P(T_k = 1) = 1 as k->infinity,但这与之前P(T_k = 0)<1/2的观察矛盾。仔细分析发现原因是Ergodic Thm的极限过程与原题的不一样。
 
于是试图直接求2^k步内访问”111″的次数。这个马氏链的状态空间大小是2^k,所以先来压缩一下它。
 
 
我们重新定义状态。Yt={从t+k-1往回数,连续H的个数}(若连续H的个数超过k,则Yt=k)。譬如k=3时,“KKHHH”对应于Y1=1,Y2=2,Y3=4。我们注意到Yt与Xt的关系是Yt={Xt从右边数起连续1的个数}。换句话说,k=3时,当X1=000或010或100或110时,Y1=0;当X1=001或101时,Y1=1;当X1=011时,Y1=2;当X1=111时,Y1=3。
 
至此状态空间大小从原来的2^k缩小到k。这个仍然是转移概率矩阵已知,不可约正常返的离散时间马尔可夫链。现在要求其在2^k步内访问状态k的次数的分布的极限。
 
如何求这个次数的分布呢?

二人Family Cellphone Plan的分账问题

November 9, 2008

A和B共用一个700分钟的手机family plan。根据电话公司的规则,此plan的收费标准为:如果每个月二人总分钟数不超过700分钟,则收费70元;超过700分钟的部分,每分钟0.2元。

账单例子:若A和B分别打了200分钟和350分钟,则总时间为200+350=550<700,所以账单金额为70元;若A和B分别打了300分钟和500分钟,则总时间为300+500=800>700,所以账单金额为70+(800-700)*0.2=90元。

则A和B应该怎样公平地分摊每个月的账单呢?具体而言,如何设计一种分账规则,满足以下5条公平性要求:

  1. 二人付钱之和等于本月的账单金额;
  2. 任何一个人付的钱不超过账单金额;
  3. 分钟数少的人付的钱不大于分钟数多的人;
  4. 某人的分钟不变或者减少,他付的钱不会增加;
  5. * 如果某人的分钟数没有超过350分钟,则他付的钱不多于35元。

问题:这样一种规则存在吗?第5条要求是否过强?跟Arrow不可能定理有关系吗?

什么样的公共服务应该收费

November 8, 2008

看今天新闻,公安部推出身份证查询服务,每查一次5元。有人质疑这种收费行为,认为不应将公民信息提供给企业赚钱。

那什么样的政府服务应该收钱呢?去民政部领结婚证是要收费的,但似乎从没人质疑这种收费。在美国,去交通部考驾照是要交钱的,似乎也没人有意见。但去办SSN是不用交钱,在国内换身份证貌似也不用。如何决定收与不收?

理论上说,免费的服务,最终都是税收埋单。那是否意味着受益面广的服务应该免费,收益面窄的应该收费呢?

A proof of the Strong Law of Large Numbers

October 17, 2008

Use the fact that for all e>0, P(|S_n/n|>e i.o.)=0 implies P(|S_n/n| does not converge to 0)=0.

To prove P(|S_n/n|>e i.o.)=0, we use Borel-Cantelli and only need to prove

/sum_{n=1}^{Infinity} P(|S_n/n|>e) < infinity.

To prove the above, we use Chernoff bound

P(|S_n/n|>e)<=exp(-nI(e))

and the fact that I(e)>0(?).

What’s the difference between the above and Komogolov‘s SLLN?