Thanksgiving 假日，忙里偷闲，和几个同学到坐车到Outlet采购冬季衣服，准备度过Boston的寒冬。

我们到的时候，好多车子都在那了，大家都赶在这几天采购打折货。这个地方和香港这种购物天堂还真是没法比，平时购物没有那么方便了，只能在节假日开车到很远的地方去。Outlet是这边比较有名的卖场，不过规模比起国内大城市或者香港的大型shopping mall还是有些差距的。风格比较别致，和一般的shopping mall不同，长得像一条村子，每个屋子是一个商店。

打过折后（一般是五折到七折），价钱还是比较实惠的。30-50美元就能买个不错的衣服，冬季的外套一般要100-300美元。逛了一个下午，终究有所斩获，买了一件外套，一些衬衣，毛衣，还有手套，以及一个被大家嘲笑的帽子——就像电视里面东北猎人戴的那种，有点怪，不过特别暖和。本来还想到Timberland看看有没有合适的鞋子，每一双过冬。不过，Timberland今天特别火，无数人在它门外排队，等待被放进店里。结果，我们最后连门都没进。

深秋了，这些天的最低温度已经降到了华氏30度以下，深夜从实验室走回寝室的时候，切身体会到寒意逼人。这是人生中第一次在高纬度地区度过一个完整的冬天，不知道是怎样的一种体验。

freeware和Microsoft的争论，在CSAIL内部显得特别有趣。

最近，CSAIL的内部邮件列表又出现Richard Stallman的影子。奇文共欣赏，这里贴出来分享一下

邮件1: 一位同学提到他的硬盘修好了，重装了windows。结果，引来了Stallman先生的哀叹。

As for me, I got lucky. After a couple hours of refusing to find the HD, the laptop booted and I copied all my data. I am now installing the OEM version of Windows

-- xxxx

How sad.

-- Richard Stallman

邮件二：另外一位同学提到Dell给他送来的电脑预装了Windows Vista。Richard Stallman利用这个机会在群发的回信中再次强调了Windows的罪恶。并且热切呼吁不要写在Windows下面运行的程序——每一个这样的程序都间接地延长了Windows这个罪恶体系的生命，呵呵。

My desktop machine broke and so Dell sent me a bunch of parts to try. But none of them fixed the problem. So they sent me a new machine, but it has Vista pre-installed. Yeah, yeah, I know Windows is evil (I'm working on Tablet PC code, so I need Windows).

-- xxxxx

Windows Vista is much more evil than previous versions. (See BadVista.org.) Perhaps you should complain and insist they send you a replacement machine with the same Windows version that you had.

I hope that you're not writing software to RUN on Windows. Each program written to run on Windows adds to the social inertia that keeps Windows going. A year from now, will someone say, "I know Windows is evil, but I'm using Aaron Adler's code so I need Windows"?

-- Richard Stallman

这位同学已经在原信中可怜的申述自己其实知道windows is evil，依然引来了Stallman的批评。

在这里的邮件中，我看到不少在提到windows的时候，都要写上Yeah, yeah, I know windows is evil, but I have to .... 似乎是一种例行的申辩了。似乎，使用windows是一件很见不得人的事情似的。

其实，Microsoft以及它旗下的软件在个人电脑软件发展中发挥了无可替代的重要作用。虽然商业上的手段受到争议，微软仍不失为一个伟大的公司。Richard Stallman作为自由软件运动的奠基人，这数十年来一直不遗余力的推广自由软件，精神实在令人敬佩。不过，感觉他有点偏激了。产业方式和自由方式为什么不能相互包容呢。

有些朋友似乎想看看这里的算法作业。恩，很多都是针对算法领域的一些专门问题，不太适合在这说。不过，正好上周的作业里面有一道题目很经典，呵呵。

题材嘛，就是关于约会和选择恋人的策略——其实大家发现搞算法的那帮人想问题和普通人还真不太一样——这里说的是经典算法，不是Learning算法。

下面是译成中文的原题：

考虑一个选择终身伴侣的问题。假设你要从k个候选人里面选择一个人作为你的终身伴侣（嗯，MIT的学生通常在这个方面比较势利）。你可以选择先和某个人约会一段时间，衡量一下你和这个人的适合程度，然后做出一个重要决定——你究竟要选择这个人永结同心，还是和他或者她彻底分手。作为一个负责人的人，你必须遵循这样的规则，在和一个人没有彻底分手之前，你不能选择约会其他人。如果你选择和一个人彻底分手，你将再也没有机会重新选择他或者她。而且，请你明白，在你约会一个人之前，你不可能了解关于他或者她的信息，或者对其做出判断。

你的目标是尽量选择最合适的人做伴侣。这里面的困境在于，如果你决定接纳当前这位作为终身伴侣，那么你将丧失选择更好的人选的机会；反之，如果你决定和他或者她分手，那么你将可能错失一个最好的人选。

在你做出最终决定之后，你会有机会见到全部的候选人，这样你就知道你选择的那个人究竟在这些人里面排名多少。如果你用了一个好的策略，你很可能最后会发现你的终身伴侣排名很靠前，如果你用了一个不好的策略，你有很大的机会发现其实你找了个排名很后的。

请完成如下问题

1. 请证明任何确定性的决策过程在最坏的情况下都是非常糟的。也就是说，无论候选人的人数是多少，无论你选择什么样的决策过程，都存在一种候选人序列，使得依据这种策略选择出来的人是里面最差的。
2. 请设计一种随机策略，使得无论有多少候选人，你都起码有25%的机会选到最好的那位作为终身伴侣。
3. 为了实现你对于伴侣的高期望，请设计一种随机策略使得你选择的候选人的实际排名尽可能靠前。这种策略至少应该保证，无论候选人的数量k有多大，你都可以以非常高的概率选到排在前 12 log(k) 名的人。（注：这道题其实问的东西要难一点，设计的要求更高，这里放宽了一点要求）
4. 请据此评论在MIT谈恋爱的后果。

解答写起来公式多一些，这里不多叙述了。这里简要分析一下而已。

1. 这种最差例子很容易找的。大概意思就是，无论你有什么样的策略和算法，我都可以找个人——这个家伙可能对你恨之入骨，呵呵。让他追踪你的决策过程，他模拟运行你的算法，如果你的算法第一个不接受，他第二个找一个差一点的，第二个还不接受，他就往序列里面排进更差的作为第三个，直到算法接受了某一个后，他往序列后面排进特别好的。然后你开始拿你的算法去这样构造出来的序列里面挑伴侣，保证挑到最差的。
2. 这个算法有点那个。你把你的候选人随机分成参考集和目标集，各占一半。你先把参考集的人逐个约会一遍，每约会一个分手一个——告诉对方他或者她是拿来训练你的model的——唉，不知道那个人会不会第二天拿把刀来砍你。然后你在目标集玩真的。一直约会下去，直到找到一个人比参考集的全部人都好的，就把这个人选为终身伴侣。如果，直到最后一个你还没碰上，你就选最后一个作为伴侣。因为你划分参考集和目标集是靠抛硬币划分的，那么你有四分之一的机会出现这样的情况：第一名的出现在目标中，第二名出现在参考集中，这样按照你的规则，在这种情况，必然会选择最好那个。所以你选择最好的机会是四分之一。
3. 这个题目有点复杂，不多说了。需要用Chernoff不等式。
4. 嘿嘿。。。。。。

整个问题最后的结论是——不要苦心孤诣的去选最好的伴侣了，抛硬币又省心效果又好，哈哈。

秋意已浓。校园中满地的黄叶，金黄的北国秋色与常绿的南方相比，别有一番景致。

很多人在这个月都要做一些新的事情，包括我：

这个学期剩下的几次作业将在这个月结束，我们将开始我们的Course Project——两门课程的Project都是不命题，自由发挥——这其实让人更摸不着底，不知道做到什么程度才叫好。

香港的同学们，战斗的气氛似乎越来越浓了——连在万里之外的我都感受到了战前的紧张。在这里，先预祝欢子今年申请梦想成真。不过，如果你现在就这么紧张，怎么熬到Offer到的那天阿，呵呵。

给苹果的本子换装了Leopard——苹果的新一代操作系统。有一些UI上的改进蛮Cool的，Safari 3.0和新的Apple Mail也很不错，不过没有更多的震撼。有少数第三方软件的功能在新系统下不work了，有点恼人。

现在Machine Learning课的作业题看上去有点意思了，这里选两道适当简化后和大家分享一下。对Learning有兴趣的朋友没事的时候，不妨想想。

1. 假定Kernel Matrix (Gram Matrix)的特征值下界为b，请导出Kernel SVM所得到的系数alpha的上界。
2. 导出有限维空间中突多面体(Convex Polygon)分类器的VC-dimension。

如果对某些术语不熟悉的话，这里给一个通俗点的版本。当n,d,p符合什么关系的时候，总能在d-维空间找到n个点，使得对于这n点的任意一个子集，总能找到一个p个面的多面体，让子集中的点全在多面体内部，而不属于子集的点全在多面体的外部。

大家知道一个n点的集合，会有(2^n)个子集，怎样才能做到，对于所有的2^n个子集，我都能各自找到相应的多面体，让子集和它的补集分开？当p太小的时候不一定能满足的，p至少要多大呢。

这其实像几何题多一些。不过，我相信，仔细想过这个之后，对于线性分类器融合(Ensemble of Linear classifier)会有更深的认识。