A nice navigation page for comming conference about IR & NLP and other related fields.
http://www.cs.sfu.ca/~bzhou/personal/conference.html
2008年12月31日星期三
2008年12月7日星期日
一些搜索引擎的基础技术资料
必读资料：
（一） 搜索引擎介绍性Paper/书籍
（1） Arvind Arasu， Junghoo Cho， Hector Garcia-Molina， Andreas Paepcke，Sriram Raghavan, Search the Web, <http://citeseer.ist.psu.edu/527114.html> 以及该paper的参考文献：8，11，22，38
（2） Junghoo Cho 的一些相关论文，重点是他的博士论文，请参考：<http://oak.cs.ucla.edu/~cho/>（3） 李晓明，闫宏飞，王继民 《搜索引擎原理、技术与系统》
（二） 编程书籍《code complete》，中文名《代码大全》。此书目前一共出版了两版，建议以一版作为精读，另一版作为对比阅读。
选读资料：
（一） 数据挖掘的基础方法和思想可以参考：《Introduction to Data Mining》，中文名《数据挖掘导论》 <http://www.china-pub.com/computers/common/info.asp?id=30045>
（二） 自然语言处理可以参考：《Foundations of Statistical Natural Language Processing》中文名《统计自然语言处理基础》<http://www.china-pub.com/computers/common/info.asp?id=22710>
（三） 需要学习的技能/工具语言/平台（1） linux使用和shell编程可以参考：《sed与awk》<http://www.china-pub.com/computers/common/info.asp?id=13255>
（2） Unix下的网络编程
Richard Stevens, 《TCP/IP 详解》
Richard Stevens, Unix Network Programming，中文名《Unix网络编程》
Richard Stevens, Advanced Programming in the Unix Environment，中文名《Unix环境高级编程》
建议的学习方式：
1、学习《UNIX环境高级编程》
2、结合《TCP/IP 详解》第一卷的知识，用《Unix网络编程》第一卷提到的方法和工具，进行学习和练习，多写点代码，多用 tcpdump 等工具观察实际的网络数据流。
2008年12月1日星期一
SIGIR 2009 Call for papers
The 32nd Annual ACM SIGIR Conference July 19-23 2009
Important Dates
Nov 17, 2008 Requests for mentoring must be submitted
Jan 19, 2009 Abstracts for full research papers due
Jan 26, 2009 Full research paper submissions due
Feb 2, 2009 Workshop proposals due
Feb 23, 2009 Posters, demonstration, and tutorial proposals due
Mar 2, 2009 Doctoral consortium proposals due
Mar 9, 2009 Notification of workshop acceptances
Apr 11, 2009 All other acceptance notification
Important Dates
Nov 17, 2008 Requests for mentoring must be submitted
Jan 19, 2009 Abstracts for full research papers due
Jan 26, 2009 Full research paper submissions due
Feb 2, 2009 Workshop proposals due
Feb 23, 2009 Posters, demonstration, and tutorial proposals due
Mar 2, 2009 Doctoral consortium proposals due
Mar 9, 2009 Notification of workshop acceptances
Apr 11, 2009 All other acceptance notification
2008年11月25日星期二
TREC evaluation measures
TREC evaluation measures:
1. AP(Average Precision) is defined as:
where :
rj is the number of retrieved relevant document
#Docj(i) is the number of retrieved document when the i-th relevant document is retrieved for the j-th query.
2. MAP(Mean Average Precision) is the average AP for all queries.
3. (R-Precision) is the precision of the first R retrieved document. Where R is the number of relevant document for each query. For a perfect system, the R-Precision is 1.0.
3. TopN precision is the precision of the first N retrieved documents.
1. AP(Average Precision) is defined as:
where :
rj is the number of retrieved relevant document
#Docj(i) is the number of retrieved document when the i-th relevant document is retrieved for the j-th query.
2. MAP(Mean Average Precision) is the average AP for all queries.
3. (R-Precision) is the precision of the first R retrieved document. Where R is the number of relevant document for each query. For a perfect system, the R-Precision is 1.0.
3. TopN precision is the precision of the first N retrieved documents.
2008年11月23日星期日
诡异的qq问题
昨晚登陆qq时碰到一个很诡异问题，qq无法登陆，但可以正常登陆qq邮箱、浏览网页也没有异常（比较奇怪，往常都是可以登陆qq，但无法浏览网页）。当时想到以下几种可能：
1、qq版本不对应
2、端口被屏蔽掉了
3、qq文件损坏了
4、电脑在joking？
5、中毒了
于是乎，先备份qq文件，然后卸载现有qq版本，然后上qq官方网站下载了07Release、08beta、09Preview 所有可能的version，然后一个个地安装，都不好使，无奈只得再一个个地卸载。至此，排除1.
之后，又在本机上换了另一个qq号登陆，它。。。竟然好用，有点崩溃。
于是又换了另外一台机器登陆，还是不好用。排除2-4.
那就杀毒吧，趋势在线、360、QQ医生都用了，都没有查出病毒。无奈之下干起了老本行：挨个进程检查；查看系统启动项，没有异常，之后进入安全模式....一切都不管用。
就这样折腾了一晚上还是没有解决，然后就在郁闷中度过了一晚。第二天起床后继续昨天未完的任务，不过能想到得都已近检查过了，剩下唯一的可能就是qq服务器有问题了，不过别得号码正常，难不成。。。我的qq号码进入服务器黑名单了？ 不过想想不应该啊，我也没用彩虹外挂、珊瑚虫版本，又没有做过暴力破解的勾当，是老实的不能再老实得平民了，难道这也有错？
无奈之下，只好求助于qq客服，得知当qq服务器处在调整期时，部分号码段可能会受影响不能正常登陆。。。 难道这也可以，这样难得的事情也能让我碰上，这算是幸运还是不幸呢？真得很无奈，都有点无语了。点背也许是我的问题，不过qq是不是也应该事先、人道地通知一下用户呢，起码有个心里准备也好。。。
后记：晚上，qq终于可以正常登陆了，就像往常一样，好像什么都没有发生一样。
为了防止意外，又做了以下预防措施：
1、备份数据
2、增强密码保护策略
3、把MSN快捷方式放在了一个显眼得位置。
1、qq版本不对应
2、端口被屏蔽掉了
3、qq文件损坏了
4、电脑在joking？
5、中毒了
于是乎，先备份qq文件，然后卸载现有qq版本，然后上qq官方网站下载了07Release、08beta、09Preview 所有可能的version，然后一个个地安装，都不好使，无奈只得再一个个地卸载。至此，排除1.
之后，又在本机上换了另一个qq号登陆，它。。。竟然好用，有点崩溃。
于是又换了另外一台机器登陆，还是不好用。排除2-4.
那就杀毒吧，趋势在线、360、QQ医生都用了，都没有查出病毒。无奈之下干起了老本行：挨个进程检查；查看系统启动项，没有异常，之后进入安全模式....一切都不管用。
就这样折腾了一晚上还是没有解决，然后就在郁闷中度过了一晚。第二天起床后继续昨天未完的任务，不过能想到得都已近检查过了，剩下唯一的可能就是qq服务器有问题了，不过别得号码正常，难不成。。。我的qq号码进入服务器黑名单了？ 不过想想不应该啊，我也没用彩虹外挂、珊瑚虫版本，又没有做过暴力破解的勾当，是老实的不能再老实得平民了，难道这也有错？
无奈之下，只好求助于qq客服，得知当qq服务器处在调整期时，部分号码段可能会受影响不能正常登陆。。。 难道这也可以，这样难得的事情也能让我碰上，这算是幸运还是不幸呢？真得很无奈，都有点无语了。点背也许是我的问题，不过qq是不是也应该事先、人道地通知一下用户呢，起码有个心里准备也好。。。
后记：晚上，qq终于可以正常登陆了，就像往常一样，好像什么都没有发生一样。
为了防止意外，又做了以下预防措施：
1、备份数据
2、增强密码保护策略
3、把MSN快捷方式放在了一个显眼得位置。
2008年10月31日星期五
路由器 VS 交换机
今天校办一个老师打电话让我帮她们组建办公室局域网，于是风风火火跑到奥林匹克电子城，不幸的是少坐了一站就下车了，之后一顿瞎找，问了N多人之后总算到达了电子城。
进如电子城之后，看到“玲琅满目”的电子产品之后，我的头就有点晕晕的感觉（我不太习惯、也不喜欢大商场的那种气氛），于是按就近原则，选择了最近的一家咨询了一下。鉴于我的实际需求，店员建议我买一款5口的交换机即可满足一般需求了，且选择了TP Link这一大众化品牌，考虑到价格不是很贵（70RMB），在预算之内，于是匆匆忙忙交钱闪人了。
回到学校之后，马上将之连入网路，可这时问题来了，那个曾经熟悉的、通过Web方式管制的（http://192.168.1.1/）界面死活不出来，为此使出了浑身解数，枚举了所有可能，然而问题还没有得到解决，没办法只能求助于Google——这个对我而言超“无敌”、超“王道”的工具，翻阅了数页“百度知道”、“雅虎知识堂”的QA之后，才恍然大悟：原来我买的是交换机，而我实际需要的则是一个路由器。
那一刻，我开始悔恨啊，后悔当初怎么就没有把网络给学明白呀，竟然犯这么低级、弱智的错误，于是恶补了一下这方面的知识，谨防再次犯类似的错误。
以下是我从网上搜集的一些关于交换机、路由器区别方面的知识，置此以备用，同时也喜欢能对他人有做帮助。以下文字的版权归属于互联网以及匿名作者，特此申明！
////////////////////////////////////////////////////////////////////
最近看到很多人在询问交换机、集线器、路由器是什么，功能如何，有何区别，笔者就这些问题简单的做些解答。
首先说HUB,也就是集线器。它的作用可以简单的理解为将一些机器连接起来组成一个局域网。而交换机（又名交换式集线器）作用与集线器大体相同。但是两者在性能上有区别：集线器采用的式共享带宽的工作方式，而交换机是独享带宽。这样在机器很多或数据量很大时，两者将会有比较明显的。而路由器与以上两者有明显区别，它的作用在于连接不同的网段并且找到网络中数据传输最合适的路径 ，可以说一般情况下个人用户需求不大。路由器是产生于交换机之后，就像交换机产生于集线器之后，所以路由器与交换机也有一定联系，并不是完全独立的两种设备。路由器主要克服了交换机不能路由转发数据包的不足。
总的来说，路由器与交换机的主要区别体现在以下几个方面：
（1）工作层次不同
最初的的交换机是工作在OSI／RM开放体系结构的数据链路层，也就是第二层，而路由器一开始就设计工作在OSI模型的网络层。由于交换机工作在OSI的第二层（数据链路层），所以它的工作原理比较简单，而路由器工作在OSI的第三层（网络层），可以得到更多的协议信息，路由器可以做出更加智能的转发决策。
（2）数据转发所依据的对象不同
交换机是利用物理地址或者说MAC地址来确定转发数据的目的地址。而路由器则是利用不同网络的ID号（即IP地址）来确定数据转发的地址。IP地址是在软件中实现的，描述的是设备所在的网络，有时这些第三层的地址也称为协议地址或者网络地址。MAC地址通常是硬件自带的，由网卡生产商来分配的，而且已经固化到了网卡中去，一般来说是不可更改的。而IP地址则通常由网络管理员或系统自动分配。
（3）传统的交换机只能分割冲突域，不能分割广播域；而路由器可以分割广播域
由交换机连接的网段仍属于同一个广播域，广播数据包会在交换机连接的所有网段上传播，在某些情况下会导致通信拥挤和安全漏洞。连接到路由器上的网段会被分配成不同的广播域，广播数据不会穿过路由器。虽然第三层以上交换机具有VLAN功能，也可以分割广播域，但是各子广播域之间是不能通信交流的，它们之间的交流仍然需要路由器。
（4）路由器提供了防火墙的服务
路由器仅仅转发特定地址的数据包，不传送不支持路由协议的数据包传送和未知目标网络数据包的传送，从而可以防止广播风暴。
交换机一般用于LAN-WAN的连接，交换机归于网桥，是数据链路层的设备，有些交换机也可实现第三层的交换。 路由器用于WAN-WAN之间的连接，可以解决异性网络之间转发分组，作用于网络层。他们只是从一条线路上接受输入分组，然后向另一条线路转发。这两条线路可能分属于不同的网络，并采用不同协议。相比较而言，路由器的功能较交换机要强大，但速度相对也慢，价格昂贵，第三层交换机既有交换机线速转发报文能力，又有路由器良好的控制功能，因此得以广泛应用。
目前个人比较多宽带接入方式就是ADSL，因此笔者就ADSL的接入来简单的说明一下。现在购买的ADSL猫大多具有路由功能（很多的时候厂家在出厂时将路由功能屏蔽了，因为电信安装时大多是不启用路由功能的，启用DHCP。打开ADSL的路由功能），如果个人上网或少数几台通过ADSL本身就可以了，如果电脑比较多你只需要再购买一个或多个集线器或者交换机。考虑到如今集线器与交换机的 价格相差十分小，不是特殊的原因，请购买一个交换机。不必去追求高价，因为如今产品同质化十分严重，我最便宜的交换机现在没有任 何问题。给你一个参考报价，建议你购买一个8口的，以满足扩充需求，一般的价格100元左右。接上交换机，所有电脑再接到交换机上就行了。余下所要做的事情就只有把各个机器的网线插入交换机的接口，将猫的网线插入uplink接口。然后设置路由功能，DHCP等， 就可以共享上网了。
看完以上的解说读者应该对交换机、集线器、路由器有了一些了解，目前的使用主要还是以交换机、路由器的组合使用为主，具体的组合方式可根据具体的网络情况和需求来确定。
进如电子城之后，看到“玲琅满目”的电子产品之后，我的头就有点晕晕的感觉（我不太习惯、也不喜欢大商场的那种气氛），于是按就近原则，选择了最近的一家咨询了一下。鉴于我的实际需求，店员建议我买一款5口的交换机即可满足一般需求了，且选择了TP Link这一大众化品牌，考虑到价格不是很贵（70RMB），在预算之内，于是匆匆忙忙交钱闪人了。
回到学校之后，马上将之连入网路，可这时问题来了，那个曾经熟悉的、通过Web方式管制的（http://192.168.1.1/）界面死活不出来，为此使出了浑身解数，枚举了所有可能，然而问题还没有得到解决，没办法只能求助于Google——这个对我而言超“无敌”、超“王道”的工具，翻阅了数页“百度知道”、“雅虎知识堂”的QA之后，才恍然大悟：原来我买的是交换机，而我实际需要的则是一个路由器。
那一刻，我开始悔恨啊，后悔当初怎么就没有把网络给学明白呀，竟然犯这么低级、弱智的错误，于是恶补了一下这方面的知识，谨防再次犯类似的错误。
以下是我从网上搜集的一些关于交换机、路由器区别方面的知识，置此以备用，同时也喜欢能对他人有做帮助。以下文字的版权归属于互联网以及匿名作者，特此申明！
////////////////////////////////////////////////////////////////////
最近看到很多人在询问交换机、集线器、路由器是什么，功能如何，有何区别，笔者就这些问题简单的做些解答。
首先说HUB,也就是集线器。它的作用可以简单的理解为将一些机器连接起来组成一个局域网。而交换机（又名交换式集线器）作用与集线器大体相同。但是两者在性能上有区别：集线器采用的式共享带宽的工作方式，而交换机是独享带宽。这样在机器很多或数据量很大时，两者将会有比较明显的。而路由器与以上两者有明显区别，它的作用在于连接不同的网段并且找到网络中数据传输最合适的路径 ，可以说一般情况下个人用户需求不大。路由器是产生于交换机之后，就像交换机产生于集线器之后，所以路由器与交换机也有一定联系，并不是完全独立的两种设备。路由器主要克服了交换机不能路由转发数据包的不足。
总的来说，路由器与交换机的主要区别体现在以下几个方面：
（1）工作层次不同
最初的的交换机是工作在OSI／RM开放体系结构的数据链路层，也就是第二层，而路由器一开始就设计工作在OSI模型的网络层。由于交换机工作在OSI的第二层（数据链路层），所以它的工作原理比较简单，而路由器工作在OSI的第三层（网络层），可以得到更多的协议信息，路由器可以做出更加智能的转发决策。
（2）数据转发所依据的对象不同
交换机是利用物理地址或者说MAC地址来确定转发数据的目的地址。而路由器则是利用不同网络的ID号（即IP地址）来确定数据转发的地址。IP地址是在软件中实现的，描述的是设备所在的网络，有时这些第三层的地址也称为协议地址或者网络地址。MAC地址通常是硬件自带的，由网卡生产商来分配的，而且已经固化到了网卡中去，一般来说是不可更改的。而IP地址则通常由网络管理员或系统自动分配。
（3）传统的交换机只能分割冲突域，不能分割广播域；而路由器可以分割广播域
由交换机连接的网段仍属于同一个广播域，广播数据包会在交换机连接的所有网段上传播，在某些情况下会导致通信拥挤和安全漏洞。连接到路由器上的网段会被分配成不同的广播域，广播数据不会穿过路由器。虽然第三层以上交换机具有VLAN功能，也可以分割广播域，但是各子广播域之间是不能通信交流的，它们之间的交流仍然需要路由器。
（4）路由器提供了防火墙的服务
路由器仅仅转发特定地址的数据包，不传送不支持路由协议的数据包传送和未知目标网络数据包的传送，从而可以防止广播风暴。
交换机一般用于LAN-WAN的连接，交换机归于网桥，是数据链路层的设备，有些交换机也可实现第三层的交换。 路由器用于WAN-WAN之间的连接，可以解决异性网络之间转发分组，作用于网络层。他们只是从一条线路上接受输入分组，然后向另一条线路转发。这两条线路可能分属于不同的网络，并采用不同协议。相比较而言，路由器的功能较交换机要强大，但速度相对也慢，价格昂贵，第三层交换机既有交换机线速转发报文能力，又有路由器良好的控制功能，因此得以广泛应用。
目前个人比较多宽带接入方式就是ADSL，因此笔者就ADSL的接入来简单的说明一下。现在购买的ADSL猫大多具有路由功能（很多的时候厂家在出厂时将路由功能屏蔽了，因为电信安装时大多是不启用路由功能的，启用DHCP。打开ADSL的路由功能），如果个人上网或少数几台通过ADSL本身就可以了，如果电脑比较多你只需要再购买一个或多个集线器或者交换机。考虑到如今集线器与交换机的 价格相差十分小，不是特殊的原因，请购买一个交换机。不必去追求高价，因为如今产品同质化十分严重，我最便宜的交换机现在没有任 何问题。给你一个参考报价，建议你购买一个8口的，以满足扩充需求，一般的价格100元左右。接上交换机，所有电脑再接到交换机上就行了。余下所要做的事情就只有把各个机器的网线插入交换机的接口，将猫的网线插入uplink接口。然后设置路由功能，DHCP等， 就可以共享上网了。
看完以上的解说读者应该对交换机、集线器、路由器有了一些了解，目前的使用主要还是以交换机、路由器的组合使用为主，具体的组合方式可根据具体的网络情况和需求来确定。
2008年10月30日星期四
经典培训故事18则[ZZ]
Form: BBS of DLUT
1、曾经有个小国到中国来，进贡了三个一模一样的金人，金壁辉煌，把皇帝高兴坏了。可是这小国不厚道，同时出一道题目：这三个金人哪个最有价值？皇帝想了许多的办法，请来珠宝匠检查，称重量，看做工，都是一模一样的。怎么办？使者还等着回去汇报呢。泱泱大国，不会连这个小事都不懂吧？最后，有一位退位的老大臣说他有办法。皇帝将使者请到大殿，老臣胸有成足地拿着三根稻草，插入第一个金人的耳朵里，这稻草从另一边耳朵出来了。第二个金人的稻草从嘴巴里直接掉出来，而第三个金人，稻草进去后掉进了肚子，什么响动也没有。老臣说：第三个金人最有价值！使者默默无语，答案正确。这个故事告诉我们，最有价值的人，不一定是最能说的人的人。老天给我们两只耳朵一个嘴巴，本来就是让我们多听少说的。善于倾听，才是成熟的人最基本的素质。
2、陈阿土是台湾的农民，从来没有出过远门。攒了半辈子的钱，终于参加一个旅游团出了国。国外的一切都是非常新鲜的，关键是，陈阿土参加的是豪华团，一个人住一个标准间。这让他新奇不已。早晨，服务生来敲门送早餐时大声说道：“GOODMORNING SIR！”陈阿土愣住了。这是什么意思呢？在自己的家乡，一般陌生的人见面都会问：“您贵姓？”于是陈阿土大声叫道：“我叫陈阿土！”如是这般，连着三天，都是那个服务生来敲门，每天都大声说：“GOODMORNING SIR！”而陈阿土亦大声回道：“我叫陈阿土！”但他非常的生气。这个服务生也太笨了，天天问自己叫什么，告诉他又记不住，很烦的。终于他忍不住去问导游，“GOODMORNING SIR！”是什么意思，导游告诉了他，天啊！！真是丢脸死了。陈阿土反复练习“GOODMORNING SIR！”这个词，以便能体面地应对服务生。又一天的早晨，服务生照常来敲门，门一开陈阿土就大声叫道：“GOODMORNING SIR！”与此同时，服务生叫的是：“我是陈阿土！”这个故事告诉我们，人与人交往，常常是意志力与意志力的较量。不是你影响他，就是他影响你，而我们要想成功，一定要培养自己的影响力，只有影响力大的人才可以成为最强者。
3、有三个人要被关进监狱三年，监狱长给他们三个一人一个要求。美国人爱抽雪茄，要了三箱雪茄。法国人最浪漫，要一个美丽的女子相伴。而犹太人说，他要一部与外界沟通的电话。三年过后，第一个冲出来的是美国人，嘴里鼻孔里塞满了雪茄，大喊道：“给我火，给我火！”原来他忘了要火了。接着出来的是法国人。只见他手里抱着一个小孩子，美丽女子手里牵着一个小孩子，肚子里还怀着第三个。最后出来的是犹太人，他紧紧握住监狱长的手说：“这三年来我每天与外界联系，我的生意不但没有停顿，反而增长了200％，为了表示感谢，我送你一辆劳施莱斯！”这个故事告诉我们，什么样的选择决定什么样的生活。今天的生活是由三年前我们的选择决定的，而今天我们的抉择将决定我们三年后的生活。我们要选择接触最新的信息，了解最新的趋势，从而更好的创造自己的将来。
4、去过庙的人都知道，一进庙门，首先是弥陀佛，笑脸迎客，而在他的北面，则是黑口黑脸的韦陀。但相传在很久以前，他们并不在同一个庙里，而是分别掌管不同的庙。弥乐佛热情快乐，所以来的人非常多，但他什么都不在乎，丢三拉四，没有好好的管理账务，所以依然入不敷出。而韦陀虽然管账是一把好手，但成天阴着个脸，太过严肃，搞得人越来越少，最后香火断绝。佛祖在查香火的时候发现了这个问题，就将他们俩放在同一个庙里，由弥乐佛负责公关，笑迎八方客，于是香火大旺。而韦陀铁面无私， 锱珠必较，则让他负责财务，严格把关。在两人的分工合作中，庙里一派欣欣向荣景象。其实在用人大师的眼里，没有废人，正如武功高手，不需名贵宝剑，摘花飞叶即可伤人，关键看如何运用。
5、一个人去买鹦鹉，看到一只鹦鹉前标：此鹦鹉会两门语言，售价二百元。另一只鹦鹉前则标道：此鹦鹉会四门语言，售价四百元。该买哪只呢？两只都毛色光鲜，非常灵活可爱。这人转啊转，拿不定主意。结果突然发现一只老掉了牙的鹦鹉，毛色暗淡散乱，标价八百元。这人赶紧将老板叫来：这只鹦鹉是不是会说八门语言？店主说：不。这人奇怪了：那为什么又老又丑，又没有能力，会值这个数呢？店主回答：因为另外两只鹦鹉叫这只鹦鹉老板。这故事告诉我们，真正的领导人，不一定自己能力有多强，只要懂信任，懂放权，懂珍惜，就能团结比自己更强的力量，从而提升自己的身价。相反许多能力非常强的人却因为过于完美主义，事必躬亲，什么人都不如自己，最后只能做最好的攻关人员，销售代表，成不了优秀的领导人。
6、A，在合资公司做白领，觉得自己满腔抱负没有得到上级的赏识，经常想：如果有一天能见到老总，有机会展示一下自己的才干就好了！！A的同事B，也有同样的想法，他更进一步，去打听老总上下班的时间，算好他大概会在何时进电梯，他也在这个时候去坐电梯，希望能遇到老总，有机会可以打个招呼。他们的同事C更进一步。他详细了解老总的奋斗历程，弄清老总毕业的学校，人际风格，关心的问题，精心设计了几句简单却有份量的开场 白，在算好的时间去乘坐电梯，跟老总打过几次招呼后，终于有一天跟老总长谈了一次，不久就争取到了更好的职位。愚者错失机会，智者善抓机会，成功者创造机会。机会只给准备好的人，这准备二字，并非说说而已。
7、一个心理学教授到疯人院参观，了解疯子的生活状态。一天下来，觉得这些人疯疯癫癫，行事出人意料，可算大开眼界。想不到准备返回时，发现自己的车胎被人下掉了。“一定是哪个疯子干的！”教授这样愤愤地想道，动手拿备胎准备装上。事情严重了。下车胎的人居然将螺丝也都下掉。没有螺丝有备胎也上不去啊！教授一筹莫展。在他着急万分的时候，一个疯子蹦蹦跳跳地过来了，嘴里唱着不知名的欢乐歌曲。他发现了困境中的教授，停下来问发生了什么事。教授懒得理他，但出于礼貌还是告诉了他。疯子哈哈大笑说：“我有办法！”他从每个轮胎上面下了一个螺丝，这样就拿到三个螺丝将备胎装了上去。教授惊奇感激之余，大为好奇：“请问你是怎么想到这个办法的？”疯子嘻嘻哈哈地笑道：“我是疯子，可我不是呆子啊！”其实，世上有许多的人，由于他们发现了工作中的乐趣，总会表现出与常人不一样的狂热，让人难以理解。许多人在笑话他们是疯子的时候，别人说不定还在笑他呆子呢。做人呆呆，处事聪明，在中国尤其不失为一种上佳做人姿态。
8、有一个博士分到一家研究所，成为学历最高的一个人。有一天他到单位后面的小池塘去钓鱼，正好正副所长在他的一左一右，也在钓鱼。他只是微微点了点头，这两个本科生，有啥好聊的呢？不一会儿，正所长放下钓竿，伸伸懒腰，蹭蹭蹭从水面上如飞地走到对面上厕所。博士眼睛睁得都快掉下来了。水上飘？不会吧？这可是一个池塘啊。正所长上完厕所回来的时候，同样也是蹭蹭蹭地从水上飘回来了。怎么回事？博士生又不好去问，自己是博士生哪！过一阵，副所长也站起来，走几步，蹭蹭蹭地飘过水面上厕所。这下子博士更是差点昏倒：不会吧，到了一个江湖高手集中的地方？博士生也内急了。这个池塘两边有围墙，要到对面厕所非得绕十分钟的路，而回单位上又太远，怎么办？博士生也不愿意去问两位所长，憋了半天后，也起身往水里跨：我就不信本科生能过的水面，我博士生不能过。只听咚的一声，博士生栽到了水里。两位所长将他拉了出来，问他为什么要下水，他问：“为什么你们可以走过去呢？”两所长相视一笑：“这池塘里有两排木桩子，由于这两天下雨涨水正好在水面下。我们都知道这木桩的位置，所以可以踩着桩子过去。你怎么不问一声呢？”学历代表过去，只有学习力才能代表将来。尊重经验的人，才能少走弯路。一个好的团队，也应该是学习型的团队。
9、A对B说：“我要离开这个公司。我恨这个公司！”B建议道：“我举双手赞成你报复！！破公司一定要给它点颜色看看。不过你现在离开，还不是最好的时机。”A问：？？？B说：“如果你现在走，公司的损失并不大。你应该趁着在公司的机会，拼命去为自己拉一些客户，成为公司独挡一面的人物，然后带着这 些客户突然离开公司，公司才会受到重大损失，非常被动。”A觉得B说的非常在理。于是努力工作，事遂所愿，半年多的努力工作后，他有了许多的忠实客户。再见面时B问A：现在是时机了，要跳赶快行动哦！A淡然笑道：老总跟我长谈过，准备升我做总经理助理，我暂时没有离开的打算了。其实这也正是B的初衷。一个人的工作，永远只是为自己的简历。只有付出大于得到，让老板真正看到你的能力大于位置，才会给你更多的机会替他创造更多利润。
10、有一位表演大师上场前，他的弟子告诉他鞋带松了。大师点头致谢，蹲下来仔细系好。等到弟子转身后，又蹲下来将鞋带解松。有个旁观者看到了这一切，不解地问：“大师，您为什么又要将鞋带解松呢？”大师回答道：“因为我饰演的是一位劳累的旅者，长途跋涉让他的鞋事松开，可以通过这个细节表现他的劳累憔悴.”“那你为什么不直接告诉你的弟子呢？”“他能细心地发现我的鞋带松了，并且热心地告诉我，我一定要保护他这种热情的积极性，及时地给他鼓励，至于为什么要将鞋带解开，将来会有更多的机会教他表演，可以下一次再说啊。”人一个时间只能做一件事，懂抓重点，才是真正的人才。
11、有个富家子弟特别爱吃饺子，每天都要吃。但他又特别刁，只吃馅，两头的皮尖尖就丢到后面的小河里去。好景不长，在他十六岁那年，一把大火烧了他的全家，父母急怒中相继病逝。这下他身无分文，又不好意思要饭。邻居家大嫂非常好，每餐给他吃一碗面糊糊。他则发奋读书，三年后考取官位回来，一定要感谢邻居大嫂。大嫂对他讲：不要感谢我。我没有给你什么，都是我收集的当年你丢的饺子皮尖，晒干后装了好凡麻袋，本来是想备不时之需的。正好你有需要，就又还给你了。大官思考良久，良久。。。。有一个有名的三八理论：八小时睡觉，八小时工作，这个人人一样。人与人之间的不同，是在于业余时间怎么渡过。时间是最有情，也最无情的东西，每人拥有的都一样，非常公平。但拥有资源的人不一定成功，善用资源的人才会成功。白天图生存，晚上求发展，这是二十一世纪对人才的要求。
12、两个人在森林里，遇到了一只大老虎。A就赶紧从背后取下一双更轻便的运动鞋换上。 B急死了，骂道：“你干嘛呢，再换鞋也跑不过老虎啊！”A说：“我只要跑得比你快就好了。”二十一世纪，没有危机感是最大的危机。特别是入关在即，电信，银行，保险，甚至是公务员这些我们以为非常稳定和有保障的企业，也会面临许多的变数。当更多的老虎来临时，我们没有有准备好自己的跑鞋？
13、父子两住山上，每天都要赶牛车下山卖柴。老父较有经验，坐镇驾车，山路崎岖，弯道特多，儿子眼神较好，总是在要转弯时提醒道：“爹，转弯啦！”有一次父亲因病没有下山，儿子一人驾车。到了弯道，牛怎么也不肯转弯，儿子用尽各种方法，下车又推又拉，用青草诱之，牛一动不动。到底是怎么回事？儿子百思不得其解。最后只有一个办法了，他左右看看无人，贴近牛的耳朵大声叫道：“爹，转弯啦！”牛应声而动。牛用条件反射的方式活着，而人则以习惯生活。一个成功的人晓得如何培养好的习惯来代替坏的习惯，当好的习惯积累多了，自然会有一个好的人生。
14、五岁的汉克和爸爸妈妈哥哥一起到森林干活，突然间下起雨来，可是他们只带了一块雨披。爸爸将雨披给了妈妈，妈妈给了哥哥，哥哥又给了汉克。汉克问道：“为什么爸爸给了妈妈，妈妈给了哥哥，哥哥又给了我呢？”爸爸回答道：“因为爸爸比妈妈强大，妈妈比哥哥强大，哥哥又比你强大呀。我们都会保护比较弱小的人。”汉克左右看了看，跑过去将雨披撑开来挡在了一朵风雨中飘摇的娇弱小花上面。这个故事告诉我们，真正的强者不一定是多有力，或者多有钱，而是他对别人多有帮助。责任可以让我们将事做完整，爱可以让我们将事情做好。
15、有位秀才第三次进京赶考，住在一个经常住的店里。考试前两天他做了三个梦，第一个梦是梦到自己在墙上种白菜，第二个梦是下雨天，他戴了斗笠还打伞，第三个梦是梦到跟心爱的表妹脱光了衣服躺在一起，但是背靠着背。这三个梦似乎有些深意，秀才第二天就赶紧去找算命的解梦。算命的一听，连拍大腿说：“你还是回家吧。你想想，高墙上种菜不是白费劲吗？戴斗笠打雨伞不是多此一举吗？跟表妹都脱光了躺在一张床上了，却背靠背，不是没戏吗？”秀才一听，心灰意冷，回店收拾包袱准备回家。店老板非常奇怪，问：“不是明天才考试吗，今天你怎么就回乡了？”秀才如此这般说了一番，店老板乐了：“哟，我也会解梦的。我倒觉得，你这次一定要留下来。你想想，墙上种菜不是高种吗？戴斗笠打伞不是说明你这次有备无患吗？跟你表妹脱光了背靠靠躺在床上，不是说明你翻身的时候就要到了吗？”秀才一听，更有道理，于是精神振奋地参加考试，居然中了个探花。积极的人，象太阳，照到哪里哪里亮，消极的人，象月亮，初一十五不一样。想法决定我们的生活，有什么样的想法，就有什么样的未来。
16、在动物园里的小骆驼问妈妈：“妈妈妈妈，为什么我们的睫毛那么地长？”骆驼妈妈说：“当风沙来的时候，长长的睫毛可以让我们在风暴中都能看得到方向。”小骆驼又问：“妈妈妈妈，为什么我们的背那么驼，丑死了！”骆驼妈妈说：“这个叫驼峰，可以帮我们储存大量的水和养分，让我们能在沙漠里耐受十几天的无水无食条件。”小骆驼又问：“妈妈妈妈，为什么我们的脚掌那么厚？”骆驼妈妈说：“那可以让我们重重的身子不至于陷在软软的沙子里，便于长途跋涉啊。”小骆驼高兴坏了：“哗，原来我们这么有用啊！！可是妈妈，为什么我们还在动物园里，不去沙漠远足呢？”天生我才必有用，可惜现在没人用。一个好的心态+一本成功的教材+一个无限的舞台=成功。每人的潜能是无限的，关键是要找到一个能充分发挥潜能的舞台。
17、有七个人曾经住在一起，每天分一大桶粥。要命的是，粥每天都是不够的。一开始，他们抓阄决定谁来分粥，每天轮一个。于是乎每周下来，他们只有一天是饱的，就是自己分粥的那一天。后来他们开始推选出一个道德高尚的人出来分粥。强权就会产生腐败，大家开始挖空心思去讨好他，贿赂他，搞得整个小团体乌烟障气。然后大家开始组成三人的分粥委员会及四人的评选委员会，互相攻击扯皮下来，粥吃到嘴里全是凉的。最后想出来一个方法：轮流分粥，但分粥的人要等其它人都挑完后拿剩下的最后一碗。为了不让自己吃到最少的，每人都尽量分得平均，就算不平，也只能认了。大家快快乐乐，和和气气，日子越过越好。同样是七个人，不同的分配制度，就会有不同的风气。所以一个单位如果有不好的工作习气，一定是机制问题，一定是没有完全公平公正公开，没有严格的奖勤罚懒。如何制订这样一个制度，是每个领导需要考虑的问题。
18、我想跟什么样的人合作曾经有人采访比尔盖次成功的秘决。比尔盖次说：因为又有更多的成功人士在为我工作。陈安之的超级成功学也有提到：先为成功的人工作，再与成功的人合作，最后是让成功的人为你工作。成功的人很多，但在我生活中我不认识，也没有办法去为他工作，而让成功的人为我工作，在现阶段，我更没有这个实力。只有合作，是我最喜欢和最欣赏的。我也力图借助一个宽松的环境和积极的团队，与更多的人公平合作，以便在未来替自己经营一个抵抗风险的事业。我最喜欢合作的人应该有以下几个特点：一。不甘心。二十一世纪，最大的危机是没有危机感，最大的陷阱是满足。人要学会用望远镜看世界，而不是用近视眼看世界。顺境时要想着为自己找个退路，逆境时要懂为自己找出路.二.学习力强.学历代表过去,学习力掌握将来.懂得从任何的细节,所有的人身上学习和感悟,并且要懂得举一反三。主要的是，学习，其实是学与习两个字。学一次，做一百次，才能真正掌握。学，做，教是一个完整的过程，只有达到教的程度，才算真正吃透。而且在更多时候，学习是一种态度。只有谦卑的人，才真正学到东西。大海之所以成为大海，是因为它比所有的河流都低。三。行动力强。只有行动才会有结果。行动不一样，结果才不一样。知道不去做，等于不知道，做了没有结果，等于没有做。不犯错误，一定会错，因为不犯错误的人一定没有尝试。错了不要紧，一定要善于总结，然后再做，一直到正确的结果出来为止。四。要懂付出。要想杰出一定得先付出。斤斤计较的人，一生只得两斤。没有点奉献精神，是不可能创业的。要先用行动让别人知道，你有超过所得的价值，别人才会开更高的价。五。有强烈的沟通意识。沟通无极限，这更是一种态度，而非一种技巧。一个好的团队当然要有共同的愿景，非一日可以得来。需要无时不在的沟通，从目标到细节，甚至到家庭等等，都在沟通的内容之列。六。诚恳大方。每人都有不同的立场，不可能要求利益都一致。关键是大家都要开诚布公地谈清楚，不要委屈求全。相信诚信才是合作的最好基石。七。有最基本的道德观。曾经有一个记者在家写稿时，他的四岁儿子吵着要他陪。记者很烦，就将一本杂志的封底撕碎，对他儿子说：“ 你先将这上面的世界地图拼完整，爸爸就陪你玩。”过了不到五分钟，儿子又来拖他的手说：“爸爸我拼好了，陪我玩！”记者很生气：“小孩子要玩是可以理解的，但如果说谎话就不好了。怎么可能这么快就拼好世界地图！”儿子非常委屈：“可是我真的拼好了呀！”记者一看，果然如此：不会吧？家里出现了神童？他非常好奇地问：“你是怎么做到的？”儿子说：世界地图的背面是一个人的头像。我反过来拼，只要这个人好了，世界就完整了。所以做事先做人。做人做好了，他的世界也就是好的。
2008年10月28日星期二
计算Tribonaci队列
计算Tribonaci队列, 规则是T(n) = T(n - 1) + T(n - 2) + T(n -3)，其中T(0) = T(1) = 1，T(2) = 2。
/** Get the value of T(n - 1), and retrieve the result of T(n - 2) and T(n - 3).
@param[in] n The n in T(n).
@param[out] mid Value of T(n - 2).
@param[out] right Value of T(n - 3).
@return Value of T(n - 1).
*/
int find_trib(int n, int & mid, int & right)
{
if (3 == n)
{
mid = 1;
right = 1;
return 2;
}
else
{
int temp;
mid = find_trib(n - 1, right, temp);
return mid + right + temp;
}
}
/** Find value of T(n).
@param[in] The n in T(n).
@return Value of T(n).
@note T(n) = T(n - 1) + T(n - 2) + T(n - 3) (n > 2)
T(0) = T(1) = 1, T(2) = 2.
*/
int tribonaci(int n)
{
if (n <>{
return 0; // Undefined feature.
}
if (0 == n 1 == n)
{
return 1;
}
if (2 == n)
{
return 2;
}
int mid, right;
int left = find_trib(n, mid, right);
return left + mid + right;
}
2008年10月25日星期六
关于C的一些常见问题
From：
一道趣味题
不借助于第三个变量，怎样交换两个变量的值？
方法一：
a=a^b;
b=a^b;
a=a^b;
方法二：
a=a+b;
b=a-b;
a=a-b;
当然，这里所指的两个变量是同一类型的整数。如果是两个字符串，只要类似交换两个指针指即可。其它情况未考虑。
一些嵌入式系统编程的测试题目
1 . 用预处理指令#define 声明一个常数，用以表明1年中有多少秒（忽略闰年问题）
#define SECONDS_PER_YEAR (60 * 60 * 24 * 365)UL
我在这想看到几件事情：
• #define 语法的基本知识（例如：不能以分号结束，括号的使用，等等）
• 懂得预处理器将为你计算常数表达式的值，因此，直接写出你是如何计算一年中有多少秒而不是计算出实际的值，是更清晰而没有代价。
• 意识到这个表达式将使一个16位机的整型数溢出-因此要用到长整型符号L,告诉编译器这个常数是的长整型数。
• 如果你在你的表达式中用到UL（表示无符号长整型），那么你有了一个好的起点。
2 . 写一个“标准”宏MIN ，这个宏输入两个参数并返回较小的一个。
#define MIN(A,B) （（A） <= (B) ? (A) : (B))
这个测试是为下面的目的而设的：
• 标识#define在宏中应用的基本知识。这是很重要的，因为直到嵌入(inline)操作符变为标准C的一部分，宏是方便产生嵌入代码的唯一方法，对于嵌入式系统来说，为了能达到要求的性能，嵌入代码经常是必须的方法。
• 三重条件操作符的知识。这个操作符存在C语言中的原因是它使得编译器能产生比if-then-else更优化的代码，了解这个用法是很重要的。
• 懂得在宏中小心地把参数用括号括起来 • 我也用这个问题开始讨论宏的副作用，例如：当你写下面的代码时会发生什么事？ least = MIN(*p++, b);
3. 预处理器标识#error的目的是什么？
输出编译时出错信息，一般大型项目中都要用到，如同ASSERT（）。另外一个对应的是#warning()，输出编译时警告信息。
5. 用变量a给出下面的定义
a) 一个整型数（An integer）
b)一个指向整型数的指针（ A pointer to an integer）
c)一个指向指针的的指针，它指向的指针是指向一个整型数（ A pointer to a pointer to an intege）
d)一个有10个整型数的数组（ An array of 10 integers）
e) 一个有10个指针的数组，该指针是指向一个整型数的。（An array of 10 pointers to integers）
f) 一个指向有10个整型数数组的指针（ A pointer to an array of 10 integers）
g) 一个指向函数的指针，该函数有一个整型参数并返回一个整型数（A pointer to a function that takes an integer as an argument and returns an integer）
h)一个有10个指针的数组，该指针指向一个函数，该函数有一个整型参数并返回一个整型数（ An array of ten pointers to functions that take an integer argument and return an integer ）
答案是：
a) int a; // An integer
b) int *a; // A pointer to an integer
c) int **a; // A pointer to a pointer to an integer
d) int a[10]; // An array of 10 integers
e) int *a[10]; // An array of 10 pointers to integers
f) int (*a)[10]; // A pointer to an array of 10 integers
g) int (*a)(int); // A pointer to a function a that takes an integer argument and returns an integer
h) int (*a[10])(int); // An array of 10 pointers to functions that take an integer argument and return an integer
人们经常声称这里有几个问题是那种要翻一下书才能回答的问题，我同意这种说法。当我写这篇文章时，为了确定语法的正确性，我的确查了一下书。但是当我被面试的时候，我期望被问到这个问题（或者相近的问题）。因为在被面试的这段时间里，我确定我知道这个问题的答案。应试者如果不知道所有的答案（或至少大部分答案），那么也就没有为这次面试做准备，如果该面试者没有为这次面试做准备，那么他又能为什么出准备呢？
6. 关键字static的作用是什么？
这个简单的问题很少有人能回答完全。在C语言中，关键字static有三个明显的作用：
• 在函数体，一个被声明为静态的变量在这一函数被调用过程中维持其值不变。
• 在模块内（但在函数体外），一个被声明为静态的变量可以被模块内所用函数访问，但不能被模块外其它函数访问。它是一个本地的全局变量。
• 在模块内，一个被声明为静态的函数只可被这一模块内的其它函数调用。那就是，这个函数被限制在声明它的模块的本地范围内使用。 大多数应试者能正确回答第一部分，一部分能正确回答第二部分，同是很少的人能懂得第三部分。这是一个应试者的严重的缺点，因为他显然不懂得本地化数据和代码范围的好处和重要性。
7．关键字const有什么含意？
我只要一听到被面试者说：“const意味着常数”，我就知道我正在和一个业余者打交道。去年Dan Saks已经在他的文章里完全概括了const的所有用法，因此ESP(译者：Embedded Systems Programming)的每一位读者应该非常熟悉const能做什么和不能做什么.如果你从没有读到那篇文章，只要能说出const意味着“只读”就可以了。尽管这个答案不是完全的答案，但我接受它作为一个正确的答案。（如果你想知道更详细的答案，仔细读一下Saks的文章吧。）
如果应试者能正确回答这个问题，我将问他一个附加的问题： 下面的声明都是什么意思？
const int a;
int const a;
const int *a;
int * const a;
int const * a const; /******/
前两个的作用是一样，a是一个常整型数。
第三个意味着a是一个指向常整型数的指针（也就是，整型数是不可修改的，但指针可以）。
第四个意思a是一个指向整型数的常指针（也就是说，指针指向的整型数是可以修改的，但指针是不可修改的）。最后一个意味着a是一个指向常整型数的常指针（也就是说，指针指向的整型数是不可修改的，同时指针也是不可修改的）。如果应试者能正确回答这些问题，那么他就给我留下了一个好印象。顺带提一句，也许你可能会问，即使不用关键字const，也还是能很容易写出功能正确的程序，那么我为什么还要如此看重关键字const呢？我也如下的几下理由：
• 关键字const的作用是为给读你代码的人传达非常有用的信息，实际上，声明一个参数为常量是为了告诉了用户这个参数的应用目的。如果你曾花很多时间清理其它人留下的垃圾，你就会很快学会感谢这点多余的信息。（当然，懂得用const的程序员很少会留下的垃圾让别人来清理的。） • 通过给优化器一些附加的信息，使用关键字const也许能产生更紧凑的代码。
• 合理地使用关键字const可以使编译器很自然地保护那些不希望被改变的参数，防止其被无意的代码修改。简而言之，这样可以减少bug的出现。
8. 关键字volatile有什么含意?并给出三个不同的例子。 一个定义为volatile的变量是说这变量可能会被意想不到地改变，这样，编译器就不会去假设这个变量的值了。精确地说就是，优化器在用到这个变量时必须每次都小心地重新读取这个变量的值，而不是使用保存在寄存器里的备份。下面是volatile变量的几个例子：
• 并行设备的硬件寄存器（如：状态寄存器）
• 一个中断服务子程序中会访问到的非自动变量(Non-automatic variables)
• 多线程应用中被几个任务共享的变量
回答不出这个问题的人是不会被雇佣的。我认为这是区分C程序员和嵌入式系统程序员的最基本的问题。搞嵌入式的家伙们经常同硬件、中断、RTOS等等打交道，所有这些都要求用到volatile变量。不懂得volatile的内容将会带来灾难。 假设被面试者正确地回答了这是问题（嗯，怀疑是否会是这样），我将稍微深究一下，看一下这家伙是不是直正懂得volatile完全的重要性。
• 一个参数既可以是const还可以是volatile吗？解释为什么。
• 一个指针可以是volatile 吗？解释为什么。
• 下面的函数有什么错误： int square(volatile int *ptr) { return *ptr * *ptr; } 下面是答案：
• 是的。一个例子是只读的状态寄存器。它是volatile因为它可能被意想不到地改变。它是const因为程序不应该试图去修改它。
• 是的。尽管这并不很常见。一个例子是当一个中服务子程序修该一个指向一个buffer的指针时。
• 这段代码有点变态。这段代码的目的是用来返指针*ptr指向值的平方，但是，由于*ptr指向一个volatile型参数，编译器将产生类似下面的代码：
int square(volatile int *ptr)
{
int a,b;
a = *ptr;
b = *ptr;
return a * b;
}
由于*ptr的值可能被意想不到地该变，因此a和b可能是不同的。结果，这段代码可能返不是你所期望的平方值！正确的代码如下：
long square(volatile int *ptr)
{
int a;
a = *ptr;
return a * a;
}
9. 位操作（Bit manipulation）
嵌入式系统总是要用户对变量或寄存器进行位操作。给定一个整型变量a，写两段代码，第一个设置a的bit 3，第二个清除a 的bit 3。
在以上两个操作中，要保持其它位不变。 对这个问题有三种基本的反应
• 不知道如何下手。该被面者从没做过任何嵌入式系统的工作。
• 用bit fields。Bit fields是被扔到C语言死角的东西，它保证你的代码在不同编译器之间是不可移植的，同时也保证了的你的代码是不可重用的。我最近不幸看到Infineon为其较复杂的通信芯片写的驱动程序，它用到了bit fields因此完全对我无用，因为我的编译器用其它的方式来实现bit fields的。从道德讲：永远不要让一个非嵌入式的家伙粘实际硬件的边。
• 用 #defines 和 bit masks 操作。这是一个有极高可移植性的方法，是应该被用到的方法。最佳的解决方案如下：
#define BIT3 (0x1 <<>
static int a;
void set_bit3(void)
{
a = BIT3;
}
void clear_bit3(void)
{
a &= ~BIT3;
}
一些人喜欢为设置和清除值而定义一个掩码同时定义一些说明常数，这也是可以接受的。我希望看到几个要点：说明常数、=和&=~操作。
10.访问固定的内存位置（Accessing fixed memory locations）
嵌入式系统经常具有要求程序员去访问某特定的内存位置的特点。在某工程中，要求设置一绝对地址为0x67a9的整型变量的值为0xaa66。编译器是一个纯粹的ANSI编译器。写代码去完成这一任务。 这一问题测试你是否知道为了访问一绝对地址把一个整型数强制转换（typecast）为一指针是合法的。这一问题的实现方式随着个人风格不同而不同。典型的类似代码如下：
int *ptr;
ptr = (int *)0x67a9;
*ptr = 0xaa55;
A more obscure approach is: 一个较晦涩的方法是：
*(int * const)(0x67a9) = 0xaa55;
即使你的品味更接近第二种方案，但我建议你在面试时使用第一种方案。
11. 中断是嵌入式系统中重要的组成部分，这导致了很多编译开发商提供一种扩展—让标准C支持中断。具代表事实是，产生了一个新的关键字__interrupt。下面的代码就使用了__interrupt关键字去定义了一个中断服务子程序(ISR)，请评论一下这段代码的。
__interrupt double compute_area (double radius)
{
double area = PI * radius * radius;
rintf("\nArea = %f", area);
return area;
}
这个函数有太多的错误了，以至让人不知从何说起了：
• ISR 不能返回一个值。如果你不懂这个，那么你不会被雇用的。
• ISR 不能传递参数。如果你没有看到这一点，你被雇用的机会等同第一项。
• 在许多的处理器/编译器中，浮点一般都是不可重入的。有些处理器/编译器需要让额处的寄存器入栈，有些处理器/编译器就是不允许在ISR中做浮点运算。此外，ISR应该是短而有效率的，在ISR中做浮点运算是不明智的。
• 与第三点一脉相承，printf()经常有重入和性能上的问题。如果你丢掉了第三和第四点，我不会太为难你的。不用说，如果你能得到后两点，那么你的被雇用前景越来越光明了。
12 . 下面的代码输出是什么，为什么？
void foo(void)
{
unsigned int a = 6;
int b = -20;
(a+b > 6) ? puts("> 6") : puts("<= 6");
}
这个问题测试你是否懂得C语言中的整数自动转换原则，我发现有些开发者懂得极少这些东西。不管如何，这无符号整型问题的答案是输出是 ”>6”。原因是当表达式中存在有符号类型和无符号类型时所有的操作数都自动转换为无符号类型。 因此-20变成了一个非常大的正整数，所以该表达式计算出的结果大于6。这一点对于应当频繁用到无符号数据类型的嵌入式系统来说是丰常重要的。如果你答错了这个问题，你也就到了得不到这份工作的边缘。
13. 评价下面的代码片断：
unsigned int zero = 0;
unsigned int compzero = 0xFFFF; /*1's complement of zero */
对于一个int型不是16位的处理器为说，上面的代码是不正确的。应编写如下：
unsigned int compzero = ~0;
这一问题真正能揭露出应试者是否懂得处理器字长的重要性。在我的经验里，好的嵌入式程序员非常准确地明白硬件的细节和它的局限，然而PC机程序往往把硬件作为一个无法避免的烦恼。 到了这个阶段，应试者或者完全垂头丧气了或者信心满满志在必得。如果显然应试者不是很好，那么这个测试就在这里结束了。但如果显然应试者做得不错，那么我就扔出下面的追加问题，这些问题是比较难的，我想仅仅非常优秀的应试者能做得不错。提出这些问题，我希望更多看到应试者应付问题的方法，而不是答案。不管如何，你就当是这个娱乐吧…
14. 动态内存分配（Dynamic memory allocation）
尽管不像非嵌入式计算机那么常见，嵌入式系统还是有从堆（heap）中动态分配内存的过程的。那么嵌入式系统中，动态分配内存可能发生的问题是什么？ 这里，我期望应试者能提到内存碎片，碎片收集的问题，变量的持行时间等等。这个主题已经在ESP杂志中被广泛地讨论过了（主要是 P.J. Plauger, 他的解释远远超过我这里能提到的任何解释），所有回过头看一下这些杂志吧！让应试者进入一种虚假的安全感觉后，我拿出这么一个小节目：
下面的代码片段的输出是什么，为什么？
char *ptr;
if ((ptr = (char *)malloc(0)) == NULL)
puts("Got a null pointer");
else
puts("Got a valid pointer");
这是一个有趣的问题。最近在我的一个同事不经意把0值传给了函数malloc，得到了一个合法的指针之后，我才想到这个问题。这就是上面的代码，该代码的输出是“Got a valid pointer”。 malloc返回指向分配地址的void类型指针或者当分配空间不够时返回NULL空指针。返回非void类型的指针时，要进行类型转换。存储空间是确保类型对齐的。当参数为0的时候，则在堆中分配“0长度”项目，返回有效指针，一般的编译器实际是分配一个字节或者一个int长度的内存。 我们可以看看malloc.c的代码，里面写了：
if (size == 0)
size = 1;
size = (size + BYTES_PER_PARA - 1) & ~(BYTES_PER_PARA - 1);
就明确地为参数为0的调用分配了一个字节，而后面的语句则更把这个1字节扩展为一个最小分配粒度，在vc6.0下，这个粒度是16字节。换句话说，当用参数0调用malloc的时候，系统其实至少分配了16个可用字节的内存给那个指针。
15 Typedef 在C语言中频繁用以声明一个已经存在的数据类型的同义字。也可以用预处理器做类似的事。例如，思考一下下面的例子：
#define dPS struct s *
typedef struct s * tPS;
以上两种情况的意图都是要定义dPS 和 tPS 作为一个指向结构s指针。哪种方法更好呢？（如果有的话）为什么？
这是一个非常微妙的问题，任何人答对这个问题（正当的原因）是应当被恭喜的。答案是：typedef更好。思考下面的例子：
dPS p1,p2;
tPS p3,p4;
第一个扩展为
struct s * p1, p2;
上面的代码定义p1为一个指向结构的指，p2为一个实际的结构，这也许不是你想要的。第二个例子正确地定义了p3 和p4 两个指针。
16 . C语言同意一些令人震惊的结构,下面的结构是合法的吗，如果是它做些什么？
int a = 5, b = 7, c;
c = a+++b;
这个问题将做为这个测验的一个愉快的结尾。不管你相不相信，上面的例子是完全合乎语法的。问题是编译器如何处理它？水平不高的编译作者实际上会争论这个问题，根据最处理原则，编译器应当能处理尽可能所有合法的用法。因此，上面的代码被处理成： c = a++ + b; 因此, 这段代码持行后a = 6, b = 7, c = 12。 如果你知道答案，或猜出正确答案，做得好。如果你不知道答案，我也不把这个当作问题。我发现这个问题的最大好处是这是一个关于代码编写风格，代码的可读性，代码的可修改性的好的话题。
////////////////////////////////////////////////////////////////////////////////////
常量字符串相同的情况
问:相同的字符串vc里面会采用同一地址，对吧？比如：
char *p1 = "asbsdg";
char *p2 = "asbsdg";
答:不见得。
问:那怎么判断？好像以前我看过试卷上有一题，就是默认它相同的。
答:没法判断。
问:/Gf /GF 不是取消重复字符串吗？怎么没作用。
答:/GF不是“取消”重复字符串，而是把常量字符串做统一映射，减少exe体积并提高执行效率。如果你的字符串不是常量，估计就没效果。
问:哦，就是另外分配内存时，当然不同了。那什么情况下，会不同地址？
答:非常量，或者编译器认为字符串会被人为改变的时候。
问:嗯。编译器认为字符串会被人为改变的时候，就是定义成volatile时？
答:不是。你可以试试：
const char * str1 = "This is constent string";
const char * str2 = "This is constent string";
const char str3[] = "This is constent string";
const char str4[] = "This is constent string";
char * str5 = "This is constent string";
问:结果是str1 = str2= str5, str3!= str4。你说的不相同出现在什么时候呢？除了字符数组外。 答:暂时找不到例子。
/GF的作用主要是作用于EXE文件而不是程序运行期的内存结构。
/Gf 是把相同的string 存储在EXE文件的同一个位置。
/GF是运行时，把这些string放入只读内存空间。如果你尝试改写它们的内容，就会弹出内存不可写的异常。
问:编译器默认有/Gf的选项吗？因为好像不加这个选项，如果我改写str5的字符，也会异常的。 答:默认应该是开启的。这个东西以前好像是叫“字符串折叠”。
问:呵呵，我现在就是不知道常量字符串地址不同的情况，那我先假设不成立，等遇到后再说。
现在，我关于相同字符串常量的地址赋值有点明白了，你呢？ 最后，请大家看下面这段程序： const char * str1 = "This is constent string";
const char * str2 = "This is constent string";
const char str3[] = "This is constent string";
const char str4[] = "This is constent string";
char *str5 = "This is constent string";
str5[1] = 'a'; //exception
str5 = (char *)0x1021 ; //normal
str1 = (char *)0x1021 ; //normal
2008年10月23日星期四
[转载]数学之美番外篇：平凡而又神奇的贝叶斯方法 By 刘未鹏(pongba)
数学之美番外篇：平凡而又神奇的贝叶斯方法
By 刘未鹏(pongba)
C++的罗浮宫(http://blog.csdn.net/pongba)
TopLanguage(http://groups.google.com/group/pongba)
概率论只不过是把常识用数学公式表达了出来。
——拉普拉斯
记得读本科的时候，最喜欢到城里的计算机书店里面去闲逛，一逛就是好几个小时；有一次，在书店看到一本书，名叫贝叶斯方法。当时数学系的课程还没有学到概率统计。我心想，一个方法能够专门写出一本书来，肯定很牛逼。后来，我发现当初的那个朴素归纳推理成立了——这果然是个牛逼的方法。
——题记
目录
0. 前言
1. 历史
1.1 一个例子：自然语言的二义性
1.2 贝叶斯公式
2. 拼写纠正
3. 模型比较与贝叶斯奥卡姆剃刀
3.1 再访拼写纠正
3.2 模型比较理论（Model Comparasion）与贝叶斯奥卡姆剃刀（Bayesian Occam’s Razor）
3.3 最小描述长度原则
3.4 最优贝叶斯推理
4. 无处不在的贝叶斯
4.1 中文分词
4.2 统计机器翻译
4.3 贝叶斯图像识别，Analysis by Synthesis
4.4 EM 算法与基于模型的聚类
4.5 最大似然与最小二乘
5. 朴素贝叶斯方法（又名“愚蠢者的贝叶斯（idiot’s bayes）”）
5.1 垃圾邮件过滤器
5.2 为什么朴素贝叶斯方法令人诧异地好——一个理论解释
6. 层级贝叶斯模型
6.1 隐马可夫模型（HMM）
7. 贝叶斯网络
0. 前言
这是一篇关于贝叶斯方法的科普文，我会尽量少用公式，多用平白的语言叙述，多举实际例子。更严格的公式和计算我会在相应的地方注明参考资料。贝叶斯方法被证明是非常 general 且强大的推理框架，文中你会看到很多有趣的应用。
1. 历史
托马斯·贝叶斯（Thomas Bayes）同学的详细生平在这里。以下摘一段 wikipedia 上的简介：
所谓的贝叶斯方法源于他生前为解决一个“逆概”问题写的一篇文章，而这篇文章是在他死后才由他的一位朋友发表出来的。在贝叶斯写这篇文章之前，人们已经能够计算“正向概率”，如“假设袋子里面有N个白球，M个黑球，你伸手进去摸一把，摸出黑球的概率是多大”。而一个自然而然的问题是反过来：“如果我们事先并不知道袋子里面黑白球的比例，而是闭着眼睛摸出一个（或好几个）球，观察这些取出来的球的颜色之后，那么我们可以就此对袋子里面的黑白球的比例作出什么样的推测”。这个问题，就是所谓的逆概问题。
实际上，贝叶斯当时的论文只是对这个问题的一个直接的求解尝试，并不清楚他当时是不是已经意识到这里面包含着的深刻的思想。然而后来，贝叶斯方法席卷了概率论，并将应用延伸到各个问题领域，所有需要作出概率预测的地方都可以见到贝叶斯方法的影子，特别地，贝叶斯是机器学习的核心方法之一。这背后的深刻原因在于，现实世界本身就是不确定的，人类的观察能力是有局限性的（否则有很大一部分科学就没有必要做了——设想我们能够直接观察到电子的运行，还需要对原子模型争吵不休吗？），我们日常所观察到的只是事物表面上的结果，沿用刚才那个袋子里面取球的比方，我们往往只能知道从里面取出来的球是什么颜色，而并不能直接看到袋子里面实际的情况。这个时候，我们就需要提供一个猜测（hypothesis，更为严格的说法是“假设”，这里用“猜测”更通俗易懂一点），所谓猜测，当然就是不确定的（很可能有好多种乃至无数种猜测都能满足目前的观测），但也绝对不是两眼一抹黑瞎蒙——具体地说，我们需要做两件事情：1. 算出各种不同猜测的可能性大小。2. 算出最靠谱的猜测是什么。第一个就是计算特定猜测的后验概率，对于连续的猜测空间则是计算猜测的概率密度函数。第二个则是所谓的模型比较，模型比较如果不考虑先验概率的话就是最大似然方法。
1.1 一个例子：自然语言的二义性
下面举一个自然语言的不确定性的例子。当你看到这句话：
The girl saw the boy with a telescope.
你对这句话的含义有什么猜测？平常人肯定会说：那个女孩拿望远镜看见了那个男孩（即你对这个句子背后的实际语法结构的猜测是：The girl saw-with-a-telescope the boy ）。然而，仔细一想，你会发现这个句子完全可以解释成：那个女孩看见了那个拿着望远镜的男孩（即：The girl saw the-boy-with-a-telescope ）。那为什么平常生活中我们每个人都能够迅速地对这种二义性进行消解呢？这背后到底隐藏着什么样的思维法则？我们留到后面解释。
1.2 贝叶斯公式
贝叶斯公式是怎么来的？
我们还是使用 wikipedia 上的一个例子：
一所学校里面有 60% 的男生，40% 的女生。男生总是穿长裤，女生则一半穿长裤一半穿裙子。有了这些信息之后我们可以容易地计算“随机选取一个学生，他（她）穿长裤的概率和穿裙子的概率是多大”，这个就是前面说的“正向概率”的计算。然而，假设你走在校园中，迎面走来一个穿长裤的学生（很不幸的是你高度近似，你只看得见他（她）穿的是否长裤，而无法确定他（她）的性别），你能够推断出他（她）是男生的概率是多大吗？
一些认知科学的研究表明（《决策与判断》以及《Rationality for Mortals》第12章：小孩也可以解决贝叶斯问题），我们对形式化的贝叶斯问题不擅长，但对于以频率形式呈现的等价问题却很擅长。在这里，我们不妨把问题重新叙述成：你在校园里面随机游走，遇到了 N 个穿长裤的人（仍然假设你无法直接观察到他们的性别），问这 N 个人里面有多少个女生多少个男生。
你说，这还不简单：算出学校里面有多少穿长裤的，然后在这些人里面再算出有多少女生，不就行了？
我们来算一算：假设学校里面人的总数是 U 个。60% 的男生都穿长裤，于是我们得到了 U * P(Boy) * P(PantsBoy) 个穿长裤的（男生）（其中 P(Boy) 是男生的概率 = 60%，这里可以简单的理解为男生的比例；P(PantsBoy) 是条件概率，即在 Boy 这个条件下穿长裤的概率是多大，这里是 100% ，因为所有男生都穿长裤）。40% 的女生里面又有一半（50%）是穿长裤的，于是我们又得到了 U * P(Girl) * P(PantsGirl) 个穿长裤的（女生）。加起来一共是 U * P(Boy) * P(PantsBoy) + U * P(Girl) * P(PantsGirl) 个穿长裤的，其中有 U * P(Girl) * P(PantsGirl) 个女生。两者一比就是你要求的答案。
下面我们把这个答案形式化一下：我们要求的是 P(GirlPants) （穿长裤的人里面有多少女生），我们计算的结果是 U * P(Girl) * P(PantsGirl) / [U * P(Boy) * P(PantsBoy) + U * P(Girl) * P(PantsGirl)] 。容易发现这里校园内人的总数是无关的，可以消去。于是得到
P(GirlPants) = P(Girl) * P(PantsGirl) / [P(Boy) * P(PantsBoy) + P(Girl) * P(PantsGirl)]
注意，如果把上式收缩起来，分母其实就是 P(Pants) ，分子其实就是 P(Pants, Girl) 。而这个比例很自然地就读作：在穿长裤的人（ P(Pants) ）里面有多少（穿长裤）的女孩（ P(Pants, Girl) ）。
上式中的 Pants 和 Boy/Girl 可以指代一切东西，所以其一般形式就是：
P(BA) = P(AB) * P(B) / [P(AB) * P(B) + P(A~B) * P(~B) ]
收缩起来就是：
P(BA) = P(AB) / P(A)
其实这个就等于：
P(BA) * P(A) = P(AB)
难怪拉普拉斯说概率论只是把常识用数学公式表达了出来。
然而，后面我们会逐渐发现，看似这么平凡的贝叶斯公式，背后却隐含着非常深刻的原理。
2. 拼写纠正
经典著作《人工智能：现代方法》的作者之一 Peter Norvig 曾经写过一篇介绍如何写一个拼写检查/纠正器的文章（原文在这里，徐宥的翻译版在这里，这篇文章很深入浅出，强烈建议读一读），里面用到的就是贝叶斯方法，这里我们不打算复述他写的文章，而是简要地将其核心思想介绍一下。
首先，我们需要询问的是：“问题是什么？”
问题是我们看到用户输入了一个不在字典中的单词，我们需要去猜测：“这个家伙到底真正想输入的单词是什么呢？”用刚才我们形式化的语言来叙述就是，我们需要求：
P(我们猜测他想输入的单词 他实际输入的单词)
这个概率。并找出那个使得这个概率最大的猜测单词。显然，我们的猜测未必是唯一的，就像前面举的那个自然语言的歧义性的例子一样；这里，比如用户输入： thew ，那么他到底是想输入 the ，还是想输入 thaw ？到底哪个猜测可能性更大呢？幸运的是我们可以用贝叶斯公式来直接出它们各自的概率，我们不妨将我们的多个猜测记为 h1 h2 .. （ h 代表 hypothesis），它们都属于一个有限且离散的猜测空间 H （单词总共就那么多而已），将用户实际输入的单词记为 D （ D 代表 Data ，即观测数据），于是
P(我们的猜测1 他实际输入的单词)
可以抽象地记为：
P(h1 D)
类似地，对于我们的猜测2，则是 P(h2 D)。不妨统一记为：
P(h D)
运用一次贝叶斯公式，我们得到：
P(h D) = P(h) * P(D h) / P(D)
对于不同的具体猜测 h1 h2 h3 .. ，P(D) 都是一样的，所以在比较 P(h1 D) 和 P(h2 D) 的时候我们可以忽略这个常数。即我们只需要知道：
P(h D) ∝ P(h) * P(D h) （注：那个符号的意思是“正比例于”，不是无穷大，注意符号右端是有一个小缺口的。）
这个式子的抽象含义是：对于给定观测数据，一个猜测是好是坏，取决于“这个猜测本身独立的可能性大小（先验概率，Prior ）”和“这个猜测生成我们观测到的数据的可能性大小”（似然，Likelihood ）的乘积。具体到我们的那个 thew 例子上，含义就是，用户实际是想输入 the 的可能性大小取决于 the 本身在词汇表中被使用的可能性（频繁程度）大小（先验概率）和 想打 the 却打成 thew 的可能性大小（似然）的乘积。
下面的事情就很简单了，对于我们猜测为可能的每个单词计算一下 P(h) * P(D h) 这个值，然后取最大的，得到的就是最靠谱的猜测。
一点注记：Norvig 的拼写纠正器里面只提取了编辑距离为 2 以内的所有已知单词。这是为了避免去遍历字典中每个单词计算它们的 P(h) * P(D h) ，但这种做法为了节省时间带来了一些误差。但话说回来难道我们人类真的回去遍历每个可能的单词来计算他们的后验概率吗？不可能。实际上，根据认知神经科学的观点，我们首先根据错误的单词做一个 bottom-up 的关联提取，提取出有可能是实际单词的那些候选单词，这个提取过程就是所谓的基于内容的提取，可以根据错误单词的一些模式片段提取出有限的一组候选，非常快地缩小的搜索空间（比如我输入 explaination ，单词里面就有充分的信息使得我们的大脑在常数时间内把可能性 narrow down 到 explanation 这个单词上，至于具体是根据哪些线索——如音节——来提取，又是如何在生物神经网络中实现这个提取机制的，目前还是一个没有弄清的领域）。然后，我们对这有限的几个猜测做一个 top-down 的预测，看看到底哪个对于观测数据（即错误单词）的预测效力最好，而如何衡量预测效率则就是用贝叶斯公式里面的那个 P(h) * P(D h) 了——虽然我们很可能使用了一些启发法来简化计算。后面我们还会提到这样的 bottom-up 的关联提取。
3. 模型比较与奥卡姆剃刀
3.1 再访拼写纠正
介绍了贝叶斯拼写纠正之后，接下来的一个自然而然的问题就来了：“为什么？”为什么要用贝叶斯公式？为什么贝叶斯公式在这里可以用？我们可以很容易地领会为什么贝叶斯公式用在前面介绍的那个男生女生长裤裙子的问题里是正确的。但为什么这里？
为了回答这个问题，一个常见的思路就是想想：非得这样吗？因为如果你想到了另一种做法并且证明了它也是靠谱的，那么将它与现在这个一比较，也许就能得出很有价值的信息。那么对于拼写纠错问题你能想到其他方案吗？
不管怎样，一个最常见的替代方案就是，选择离 thew 的编辑距离最近的。然而 the 和 thaw 离 thew 的编辑距离都是 1 。这可咋办捏？你说，不慌，那还是好办。我们就看到底哪个更可能被错打为 thew 就是了。我们注意到字母 e 和字母 w 在键盘上离得很紧，无名指一抽筋就不小心多打出一个 w 来，the 就变成 thew 了。而另一方面 thaw 被错打成 thew 的可能性就相对小一点，因为 e 和 a 离得较远而且使用的指头相差一个指头（一个是中指一个是小指，不像 e 和 w 使用的指头靠在一块——神经科学的证据表明紧邻的身体设施之间容易串位）。OK，很好，因为你现在已经是在用最大似然方法了，或者直白一点，你就是在计算那个使得 P(D h) 最大的 h 。
而贝叶斯方法计算的是什么？是 P(h) * P(D h) 。多出来了一个 P(h) 。我们刚才说了，这个多出来的 P(h) 是特定猜测的先验概率。为什么要掺和进一个先验概率？刚才说的那个最大似然不是挺好么？很雄辩地指出了 the 是更靠谱的猜测。有什么问题呢？既然这样，我们就从给最大似然找茬开始吧——我们假设两者的似然程度是一样或非常相近，这样不就难以区分哪个猜测更靠谱了吗？比如用户输入tlp ，那到底是 top 还是 tip ？（这个例子不怎么好，因为 top 和 tip 的词频可能仍然是接近的，但一时想不到好的英文单词的例子，我们不妨就假设 top 比 tip 常见许多吧，这个假设并不影响问题的本质。）这个时候，当最大似然不能作出决定性的判断时，先验概率就可以插手进来给出指示——“既然你无法决定，那么我告诉你，一般来说 top 出现的程度要高许多，所以更可能他想打的是 top ”）。
以上只是最大似然的一个问题，即并不能提供决策的全部信息。
最大似然还有另一个问题：即便一个猜测与数据非常符合，也并不代表这个猜测就是更好的猜测，因为这个猜测本身的可能性也许就非常低。比如 MacKay 在《Information Theory : Inference and Learning Algorithms》里面就举了一个很好的例子：-1 3 7 11 你说是等差数列更有可能呢？还是 -X^3 / 11 + 9/11*X^2 + 23/11 每项把前项作为 X 带入后计算得到的数列？此外曲线拟合也是，平面上 N 个点总是可以用 N-1 阶多项式来完全拟合，当 N 个点近似但不精确共线的时候，用 N-1 阶多项式来拟合能够精确通过每一个点，然而用直线来做拟合/线性回归的时候却会使得某些点不能位于直线上。你说到底哪个好呢？多项式？还是直线？一般地说肯定是越低阶的多项式越靠谱（当然前提是也不能忽视“似然”P(D h) ，明摆着一个多项式分布您愣是去拿直线拟合也是不靠谱的，这就是为什么要把它们两者乘起来考虑。），原因之一就是低阶多项式更常见，先验概率（ P(h) ）较大（原因之二则隐藏在 P(D h) 里面），这就是为什么我们要用样条来插值，而不是直接搞一个 N-1 阶多项式来通过任意 N 个点的原因。
以上分析当中隐含的哲学是，观测数据总是会有各种各样的误差，比如观测误差（比如你观测的时候一个 MM 经过你一不留神，手一抖就是一个误差出现了），所以如果过分去寻求能够完美解释观测数据的模型，就会落入所谓的数据过配（overfitting）的境地，一个过配的模型试图连误差（噪音）都去解释（而实际上噪音又是不需要解释的），显然就过犹不及了。所以 P(D h) 大不代表你的 h （猜测）就是更好的 h。还要看 P(h) 是怎样的。所谓奥卡姆剃刀精神就是说：如果两个理论具有相似的解释力度，那么优先选择那个更简单的（往往也正是更平凡的，更少繁复的，更常见的）。
过分匹配的另一个原因在于当观测的结果并不是因为误差而显得“不精确”而是因为真实世界中对数据的结果产生贡献的因素太多太多，跟噪音不同，这些偏差是一些另外的因素集体贡献的结果，不是你的模型所能解释的——噪音那是不需要解释——一个现实的模型往往只提取出几个与结果相关度很高，很重要的因素（cause）。这个时候观察数据会倾向于围绕你的有限模型的预测结果呈正态分布，于是你实际观察到的结果就是这个正态分布的随机取样，这个取样很可能受到其余因素的影响偏离你的模型所预测的中心，这个时候便不能贪心不足地试图通过改变模型来“完美”匹配数据，因为那些使结果偏离你的预测的贡献因素不是你这个有限模型里面含有的因素所能概括的，硬要打肿脸充胖子只能导致不实际的模型，举个教科书例子：身高和体重的实际关系近似于一个二阶多项式的关系，但大家都知道并不是只有身高才会对体重产生影响，物理世界影响体重的因素太多太多了，有人身材高大却瘦得跟稻草，有人却是横长竖不长。但不可否认的是总体上来说，那些特殊情况越是特殊就越是稀少，呈围绕最普遍情况（胖瘦适中）的正态分布，这个分布就保证了我们的身高——体重相关模型能够在大多数情况下做出靠谱的预测。但是——刚才说了，特例是存在的，就算不是特例，人有胖瘦，密度也有大小，所以完美符合身高——体重的某个假想的二阶多项式关系的人是不存在的，我们又不是欧几里德几何世界当中的理想多面体，所以，当我们对人群随机抽取了 N 个样本（数据点）试图对这 N 个数据点拟合出一个多项式的话就得注意，它肯定得是二阶多项式，我们要做的只是去根据数据点计算出多项式各项的参数（一个典型的方法就是最小二乘）；它肯定不是直线（我们又不是稻草），也不是三阶多项式四阶多项式.. 如果硬要完美拟合 N 个点，你可能会整出一个 N-1 阶多项式来——设想身高和体重的关系是 5 阶多项式看看？
3.2 模型比较理论（Model Comparasion）与贝叶斯奥卡姆剃刀（Bayesian Occam’s Razor）
实际上，模型比较就是去比较哪个模型（猜测）更可能隐藏在观察数据的背后。其基本思想前面已经用拼写纠正的例子来说明了。我们对用户实际想输入的单词的猜测就是模型，用户输错的单词就是观测数据。我们通过：
P(h D) ∝ P(h) * P(D h)
来比较哪个模型最为靠谱。前面提到，光靠 P(D h) （即“似然”）是不够的，有时候还需要引入 P(h) 这个先验概率。奥卡姆剃刀就是说 P(h) 较大的模型有较大的优势，而最大似然则是说最符合观测数据的（即 P(D h) 最大的）最有优势。整个模型比较就是这两方力量的拉锯。我们不妨再举一个简单的例子来说明这一精神：你随便找枚硬币，掷一下，观察一下结果。好，你观察到的结果要么是“正”，要么是“反”（不，不是少林足球那枚硬币:P ），不妨假设你观察到的是“正”。现在你要去根据这个观测数据推断这枚硬币掷出“正”的概率是多大。根据最大似然估计的精神，我们应该猜测这枚硬币掷出“正”的概率是 1 ，因为这个才是能最大化 P(D h) 的那个猜测。然而每个人都会大摇其头——很显然，你随机摸出一枚硬币这枚硬币居然没有反面的概率是“不存在的”，我们对一枚随机硬币是否一枚有偏硬币，偏了多少，是有着一个先验的认识的，这个认识就是绝大多数硬币都是基本公平的，偏得越多的硬币越少见（可以用一个 beta 分布来表达这一先验概率）。将这个先验正态分布 p(θ) （其中 θ 表示硬币掷出正面的比例，小写的 p 代表这是概率密度函数）结合到我们的问题中，我们便不是去最大化 P(D h) ，而是去最大化 P(D θ) * p(θ) ，显然 θ = 1 是不行的，因为 P(θ=1) 为 0 ，导致整个乘积也为 0 。实际上，只要对这个式子求一个导数就可以得到最值点。
以上说的是当我们知道先验概率 P(h) 的时候，光用最大似然是不靠谱的，因为最大似然的猜测可能先验概率非常小。然而，有些时候，我们对于先验概率一无所知，只能假设每种猜测的先验概率是均等的，这个时候就只有用最大似然了。实际上，统计学家和贝叶斯学家有一个有趣的争论，统计学家说：我们让数据自己说话。言下之意就是要摒弃先验概率。而贝叶斯支持者则说：数据会有各种各样的偏差，而一个靠谱的先验概率则可以对这些随机噪音做到健壮。事实证明贝叶斯派胜利了，胜利的关键在于所谓先验概率其实也是经验统计的结果，譬如为什么我们会认为绝大多数硬币是基本公平的？为什么我们认为大多数人的肥胖适中？为什么我们认为肤色是种族相关的，而体重则与种族无关？先验概率里面的“先验”并不是指先于一切经验，而是仅指先于我们“当前”给出的观测数据而已，在硬币的例子中先验指的只是先于我们知道投掷的结果这个经验，而并非“先天”。
然而，话说回来，有时候我们必须得承认，就算是基于以往的经验，我们手头的“先验”概率还是均匀分布，这个时候就必须依赖用最大似然，我们用前面留下的一个自然语言二义性问题来说明这一点：
The girl saw the boy with a telescope.
到底是 The girl saw-with-a-telescope the boy 这一语法结构，还是 The girl saw the-boy-with-a-telescope 呢？两种语法结构的常见程度都差不多（你可能会觉得后一种语法结构的常见程度较低，这是事后偏见，你只需想想 The girl saw the boy with a book 就知道了。当然，实际上从大规模语料统计结果来看后一种语法结构的确稍稍不常见一丁点，但是绝对不足以解释我们对第一种结构的强烈倾向）。那么到底为什么呢？
我们不妨先来看看 MacKay 在书中举的一个漂亮的例子：
图中有多少个箱子？特别地，那棵书后面是一个箱子？还是两个箱子？还是三个箱子？还是.. 你可能会觉得树后面肯定是一个箱子，但为什么不是两个呢？如下图：
很简单，你会说：要是真的有两个箱子那才怪了，怎么就那么巧这两个箱子刚刚好颜色相同，高度相同呢？
用概率论的语言来说，你刚才的话就翻译为：猜测 h 不成立，因为 P(D h) 太小（太巧合）了。我们的直觉是：巧合（小概率）事件不会发生。所以当一个猜测（假设）使得我们的观测结果成为小概率事件的时候，我们就说“才怪呢，哪能那么巧捏？！”
现在我们可以回到那个自然语言二义性的例子，并给出一个完美的解释了：如果语法结构是 The girl saw the-boy-with-a-telecope 的话，怎么那个男孩偏偏手里拿的就是望远镜——一个可以被用来 saw-with 的东东捏？这也忒小概率了吧。他咋就不会拿本书呢？拿什么都好。怎么偏偏就拿了望远镜？所以唯一的解释是，这个“巧合”背后肯定有它的必然性，这个必然性就是，如果我们将语法结构解释为 The girl saw-with-a-telescope the boy 的话，就跟数据完美吻合了——既然那个女孩是用某个东西去看这个男孩的，那么这个东西是一个望远镜就完全可以解释了（不再是小概率事件了）。
自然语言二义性很常见，譬如上文中的一句话：
参见《决策与判断》以及《Rationality for Mortals》第12章：小孩也可以解决贝叶斯问题
就有二义性：到底是参见这两本书的第 12 章，还是仅仅是第二本书的第 12 章呢？如果是这两本书的第 12 章那就是咄咄怪事了，怎么恰好两本书都有第 12 章，都是讲同一个问题，更诡异的是，标题还相同呢？
注意，以上做的是似然估计（即只看 P(D h) 的大小），不含先验概率。通过这两个例子，尤其是那个树后面的箱子的例子我们可以看到，似然估计里面也蕴含着奥卡姆剃刀：树后面的箱子数目越多，这个模型就越复杂。单个箱子的模型是最简单的。似然估计选择了更简单的模型。
这个就是所谓的贝叶斯奥卡姆剃刀（Bayesian Occam’s Razor），因为这个剃刀工作在贝叶斯公式的似然（P(D h) ）上，而不是模型本身（ P(h) ）的先验概率上，后者是传统的奥卡姆剃刀。关于贝叶斯奥卡姆剃刀我们再来看一个前面说到的曲线拟合的例子：如果平面上有 N 个点，近似构成一条直线，但绝不精确地位于一条直线上。这时我们既可以用直线来拟合（模型1），也可以用二阶多项式（模型2）拟合，也可以用三阶多项式（模型3），.. ，特别地，用 N-1 阶多项式便能够保证肯定能完美通过 N 个数据点。那么，这些可能的模型之中到底哪个是最靠谱的呢？前面提到，一个衡量的依据是奥卡姆剃刀：越是高阶的多项式越是繁复和不常见。然而，我们其实并不需要依赖于这个先验的奥卡姆剃刀，因为有人可能会争辩说：你怎么就能说越高阶的多项式越不常见呢？我偏偏觉得所有阶多项式都是等可能的。好吧，既然如此那我们不妨就扔掉 P(h) 项，看看 P(D h) 能告诉我们什么。我们注意到越是高阶的多项式，它的轨迹弯曲程度越是大，到了八九阶简直就是直上直下，于是我们不仅要问：一个比如说八阶多项式在平面上随机生成的一堆 N 个点偏偏恰好近似构成一条直线的概率（即 P(D h) ）有多大？太小太小了。反之，如果背后的模型是一条直线，那么根据该模型生成一堆近似构成直线的点的概率就大得多了。这就是贝叶斯奥卡姆剃刀。
这里只是提供一个关于贝叶斯奥卡姆剃刀的科普，强调直观解释，更多理论公式请参考 MacKay 的著作 《Information Theory : Inference and Learning Algorithms》第 28 章。
3.3 最小描述长度原则
贝叶斯模型比较理论与信息论有一个有趣的关联：
P(h D) ∝ P(h) * P(D h)
两边求对数，将右式的乘积变成相加：
ln P(h D) ∝ ln P(h) + ln P(D h)
显然，最大化 P(h D) 也就是最大化 ln P(h D)。而 ln P(h) + ln P(D h) 则可以解释为模型（或者称“假设”、“猜测”）h 的编码长度加上在该模型下数据 D 的编码长度。使这个和最小的模型就是最佳模型。
而究竟如何定义一个模型的编码长度，以及数据在模型下的编码长度则是一个问题。更多可参考 Mitchell 的 《Machine Learning》的 6.6 节，或 Mackay 的 28.3 节）
3.4 最优贝叶斯推理
所谓的推理，分为两个过程，第一步是对观测数据建立一个模型。第二步则是使用这个模型来推测未知现象发生的概率。我们前面都是讲的对于观测数据给出最靠谱的那个模型。然而很多时候，虽然某个模型是所有模型里面最靠谱的，但是别的模型也并不是一点机会都没有。譬如第一个模型在观测数据下的概率是 0.5 。第二个模型是 0.4 ，第三个是 0.1 。如果我们只想知道对于观测数据哪个模型最可能，那么只要取第一个就行了，故事到此结束。然而很多时候我们建立模型是为了推测未知的事情的发生概率，这个时候，三个模型对未知的事情发生的概率都会有自己的预测，仅仅因为某一个模型概率稍大一点就只听他一个人的就太不民主了。所谓的最优贝叶斯推理就是将三个模型对于未知数据的预测结论加权平均起来（权值就是模型相应的概率）。显然，这个推理是理论上的制高点，无法再优了，因为它已经把所有可能性都考虑进去了。
只不过实际上我们是基本不会使用这个框架的，因为计算模型可能非常费时间，二来模型空间可能是连续的，即有无穷多个模型（这个时候需要计算模型的概率分布）。结果还是非常费时间。所以这个被看作是一个理论基准。
4. 无处不在的贝叶斯
以下我们再举一些实际例子来说明贝叶斯方法被运用的普遍性，这里主要集中在机器学习方面，因为我不是学经济的，否则还可以找到一堆经济学的例子。
4.1 中文分词
贝叶斯是机器学习的核心方法之一。比如中文分词领域就用到了贝叶斯。Google 研究员吴军在《数学之美》系列中就有一篇是介绍中文分词的，这里只介绍一下核心的思想，不做赘述，详细请参考吴军的文章（这里）。
分词问题的描述为：给定一个句子（字串），如：
南京市长江大桥
如何对这个句子进行分词（词串）才是最靠谱的。例如：
1. 南京市/长江大桥
2. 南京/市长/江大桥
这两个分词，到底哪个更靠谱呢？
我们用贝叶斯公式来形式化地描述这个问题，令 X 为字串（句子），Y 为词串（一种特定的分词假设）。我们就是需要寻找使得 P(YX) 最大的 Y ，使用一次贝叶斯可得：
P(YX) ∝ P(Y)*P(XY)
用自然语言来说就是 这种分词方式（词串）的可能性 乘以 这个词串生成我们的句子的可能性。我们进一步容易看到：可以近似地将 P(XY) 看作是恒等于 1 的，因为任意假想的一种分词方式之下生成我们的句子总是精准地生成的（只需把分词之间的分界符号扔掉即可）。于是，我们就变成了去最大化 P(Y) ，也就是寻找一种分词使得这个词串（句子）的概率最大化。而如何计算一个词串：
W1, W2, W3, W4 ..
的可能性呢？我们知道，根据联合概率的公式展开：P(W1, W2, W3, W4 ..) = P(W1) * P(W2W1) * P(W3W2, W1) * P(W4W1,W2,W3) * .. 于是我们可以通过一系列的条件概率（右式）的乘积来求整个联合概率。然而不幸的是随着条件数目的增加（P(WnWn-1,Wn-2,..,W1) 的条件有 n-1 个），数据稀疏问题也会越来越严重，即便语料库再大也无法统计出一个靠谱的 P(WnWn-1,Wn-2,..,W1) 来。为了缓解这个问题，计算机科学家们一如既往地使用了“天真”假设：我们假设句子中一个词的出现概率只依赖于它前面的有限的 k 个词（k 一般不超过 3，如果只依赖于前面的一个词，就是2元语言模型（2-gram），同理有 3-gram 、 4-gram 等），这个就是所谓的“有限地平线”假设。虽然这个假设很傻很天真，但结果却表明它的结果往往是很好很强大的，后面要提到的朴素贝叶斯方法使用的假设跟这个精神上是完全一致的，我们会解释为什么像这样一个天真的假设能够得到强大的结果。目前我们只要知道，有了这个假设，刚才那个乘积就可以改写成： P(W1) * P(W2W1) * P(W3W2) * P(W4W3) .. （假设每个词只依赖于它前面的一个词）。而统计 P(W2W1) 就不再受到数据稀疏问题的困扰了。对于我们上面提到的例子“南京市长江大桥”，如果按照自左到右的贪婪方法分词的话，结果就成了“南京市长/江大桥”。但如果按照贝叶斯分词的话（假设使用 3-gram），由于“南京市长”和“江大桥”在语料库中一起出现的频率为 0 ，这个整句的概率便会被判定为 0 。 从而使得“南京市/长江大桥”这一分词方式胜出。
一点注记：有人可能会疑惑，难道我们人类也是基于这些天真的假设来进行推理的？不是的。事实上，统计机器学习方法所统计的东西往往处于相当表层（shallow）的层面，在这个层面机器学习只能看到一些非常表面的现象，有一点科学研究的理念的人都知道：越是往表层去，世界就越是繁复多变。从机器学习的角度来说，特征（feature）就越多，成百上千维度都是可能的。特征一多，好了，高维诅咒就产生了，数据就稀疏得要命，不够用了。而我们人类的观察水平显然比机器学习的观察水平要更深入一些，为了避免数据稀疏我们不断地发明各种装置（最典型就是显微镜），来帮助我们直接深入到更深层的事物层面去观察更本质的联系，而不是在浅层对表面现象作统计归纳。举一个简单的例子，通过对大规模语料库的统计，机器学习可能会发现这样一个规律：所有的“他”都是不会穿 bra 的，所有的“她”则都是穿的。然而，作为一个男人，却完全无需进行任何统计学习，因为深层的规律就决定了我们根本不会去穿 bra 。至于机器学习能不能完成后者（像人类那样的）这个推理，则是人工智能领域的经典问题。至少在那之前，声称统计学习方法能够终结科学研究（原文）的说法是纯粹外行人说的话。
4.2 统计机器翻译
统计机器翻译因为其简单，自动（无需手动添加规则），迅速成为了机器翻译的事实标准。而统计机器翻译的核心算法也是使用的贝叶斯方法。
问题是什么？统计机器翻译的问题可以描述为：给定一个句子 e ，它的可能的外文翻译 f 中哪个是最靠谱的。即我们需要计算：P(fe) 。一旦出现条件概率贝叶斯总是挺身而出：
P(fe) ∝ P(f) * P(ef)
这个式子的右端很容易解释：那些先验概率较高，并且更可能生成句子 e 的外文句子 f 将会胜出。我们只需简单统计（结合上面提到的 N-Gram 语言模型）就可以统计任意一个外文句子 f 的出现概率。然而 P(ef) 却不是那么好求的，给定一个候选的外文局子 f ，它生成（或对应）句子 e 的概率是多大呢？我们需要定义什么叫 “对应”，这里需要用到一个分词对齐的平行语料库，有兴趣的可以参考 《Foundations of Statistical Natural Language Processing》第 13 章，这里摘选其中的一个例子：假设 e 为：John loves Mary 。我们需要考察的首选 f 是：Jean aime Marie （法文）。我们需要求出 P(ef) 是多大，为此我们考虑 e 和 f 有多少种对齐的可能性，如：
John (Jean) loves (aime) Marie (Mary)
就是其中的一种（最靠谱的）对齐，为什么要对齐，是因为一旦对齐了之后，就可以容易地计算在这个对齐之下的 P(ef) 是多大，只需计算：
P(JohnJean) * P(lovesaime) * P(MarieMary)
即可。
然后我们遍历所有的对齐方式，并将每种对齐方式之下的翻译概率 ∑ 求和。便可以获得整个的 P(ef) 是多大。
一点注记：还是那个问题：难道我们人类真的是用这种方式进行翻译的？highly unlikely 。这种计算复杂性非常高的东西连三位数乘法都搞不定的我们才不会笨到去使用呢。根据认知神经科学的认识，很可能我们是先从句子到语义（一个逐层往上（bottom-up）抽象的 folding 过程），然后从语义根据另一门语言的语法展开为另一门语言（一个逐层往下（top-down）的具体化 unfolding 过程）。如何可计算地实现这个过程，目前仍然是个难题。（我们看到很多地方都有 bottom-up/top-down 这样一个对称的过程，实际上有人猜测这正是生物神经网络原则上的运作方式，对视觉神经系统的研究尤其证明了这一点，Hawkins 在 《On Intelligence》 里面提出了一种 HTM （Hierarchical Temporal Memory）模型正是使用了这个原则。）
4.3 贝叶斯图像识别，Analysis by Synthesis
贝叶斯方法是一个非常 general 的推理框架。其核心理念可以描述成：Analysis by Synthesis （通过合成来分析）。06 年的认知科学新进展上有一篇 paper 就是讲用贝叶斯推理来解释视觉识别的，一图胜千言，下图就是摘自这篇 paper ：
首先是视觉系统提取图形的边角特征，然后使用这些特征自底向上地激活高层的抽象概念（比如是 E 还是 F 还是等号），然后使用一个自顶向下的验证来比较到底哪个概念最佳地解释了观察到的图像。
4.4 EM 算法与基于模型的聚类
聚类是一种无指导的机器学习问题，问题描述：给你一堆数据点，让你将它们最靠谱地分成一堆一堆的。聚类算法很多，不同的算法适应于不同的问题，这里仅介绍一个基于模型的聚类，该聚类算法对数据点的假设是，这些数据点分别是围绕 K 个核心的 K 个正态分布源所随机生成的，使用 Han JiaWei 的《Data Ming： Concepts and Techniques》中的图：
图中有两个正态分布核心，生成了大致两堆点。我们的聚类算法就是需要根据给出来的那些点，算出这两个正态分布的核心在什么位置，以及分布的参数是多少。这很明显又是一个贝叶斯问题，但这次不同的是，答案是连续的且有无穷多种可能性，更糟的是，只有当我们知道了哪些点属于同一个正态分布圈的时候才能够对这个分布的参数作出靠谱的预测，现在两堆点混在一块我们又不知道哪些点属于第一个正态分布，哪些属于第二个。反过来，只有当我们对分布的参数作出了靠谱的预测时候，才能知道到底哪些点属于第一个分布，那些点属于第二个分布。这就成了一个先有鸡还是先有蛋的问题了。为了解决这个循环依赖，总有一方要先打破僵局，说，不管了，我先随便整一个值出来，看你怎么变，然后我再根据你的变化调整我的变化，然后如此迭代着不断互相推导，最终收敛到一个解。这就是 EM 算法。
EM 的意思是“Expectation-Maximazation”，在这个聚类问题里面，我们是先随便猜一下这两个正态分布的参数：如核心在什么地方，方差是多少。然后计算出每个数据点更可能属于第一个还是第二个正态分布圈，这个是属于 Expectation 一步。有了每个数据点的归属，我们就可以根据属于第一个分布的数据点来重新评估第一个分布的参数（从蛋再回到鸡），这个是 Maximazation 。如此往复，直到参数基本不再发生变化为止。这个迭代收敛过程中的贝叶斯方法在第二步，根据数据点求分布的参数上面。
4.5 最大似然与最小二乘
学过线性代数的大概都知道经典的最小二乘方法来做线性回归。问题描述是：给定平面上 N 个点，（这里不妨假设我们想用一条直线来拟合这些点——回归可以看作是拟合的特例，即允许误差的拟合），找出一条最佳描述了这些点的直线。
一个接踵而来的问题就是，我们如何定义最佳？我们设每个点的坐标为 (Xi, Yi) 。如果直线为 y = f(x) 。那么 (Xi, Yi) 跟直线对这个点的“预测”：(Xi, f(Xi)) 就相差了一个 ΔYi = Yi – f(Xi) 。最小二乘就是说寻找直线使得 (ΔY1)^2 + (ΔY2)^2 + .. （即误差的平方和）最小，至于为什么是误差的平方和而不是误差的绝对值和，统计学上也没有什么好的解释。然而贝叶斯方法却能对此提供一个完美的解释。
我们假设直线对于坐标 Xi 给出的预测 f(Xi) 是最靠谱的预测，所有纵坐标偏离 f(Xi) 的那些数据点都含有噪音，是噪音使得它们偏离了完美的一条直线，一个合理的假设就是偏离路线越远的概率越小，具体小多少，可以用一个正态分布曲线来模拟，这个分布曲线以直线对 Xi 给出的预测 f(Xi) 为中心，实际纵坐标为 Yi 的点 (Xi, Yi) 发生的概率就正比于 EXP[-(ΔYi)^2]。（EXP(..) 代表以常数 e 为底的多少次方）。
现在我们回到问题的贝叶斯方面，我们要想最大化的后验概率是：
P(hD) ∝ P(h) * P(Dh)
又见贝叶斯！这里 h 就是指一条特定的直线，D 就是指这 N 个数据点。我们需要寻找一条直线 h 使得 P(h) * P(Dh) 最大。很显然，P(h) 这个先验概率是均匀的，因为哪条直线也不比另一条更优越。所以我们只需要看 P(Dh) 这一项，这一项是指这条直线生成这些数据点的概率，刚才说过了，生成数据点 (Xi, Yi) 的概率为 EXP[-(ΔYi)^2] 乘以一个常数。而 P(Dh) = P(d1h) * P(d2h) * .. 即假设各个数据点是独立生成的，所以可以把每个概率乘起来。于是生成 N 个数据点的概率为 EXP[-(ΔY1)^2] * EXP[-(ΔY2)^2] * EXP[-(ΔY3)^2] * .. = EXP{-[(ΔY1)^2 + (ΔY2)^2 + (ΔY3)^2 + ..]} 最大化这个概率就是要最小化 (ΔY1)^2 + (ΔY2)^2 + (ΔY3)^2 + .. 。 熟悉这个式子吗？
5. 朴素贝叶斯方法
朴素贝叶斯方法是一个很特别的方法，所以值得介绍一下。我们用朴素贝叶斯在垃圾邮件过滤中的应用来举例说明。
5.1 贝叶斯垃圾邮件过滤器
问题是什么？问题是，给定一封邮件，判定它是否属于垃圾邮件。按照先例，我们还是用 D 来表示这封邮件，注意 D 由 N 个单词组成。我们用 h+ 来表示垃圾邮件，h- 表示正常邮件。问题可以形式化地描述为求：
P(h+D) = P(h+) * P(Dh+) / P(D)
P(h-D) = P(h-) * P(Dh-) / P(D)
其中 P(h+) 和 P(h-) 这两个先验概率都是很容易求出来的，只需要计算一个邮件库里面垃圾邮件和正常邮件的比例就行了。然而 P(Dh+) 却不容易求，因为 D 里面含有 N 个单词 d1, d2, d3, .. ，所以P(Dh+) = P(d1,d2,..,dnh+) 。我们又一次遇到了数据稀疏性，为什么这么说呢？P(d1,d2,..,dnh+) 就是说在垃圾邮件当中出现跟我们目前这封邮件一模一样的一封邮件的概率是多大！开玩笑，每封邮件都是不同的，世界上有无穷多封邮件。瞧，这就是数据稀疏性，因为可以肯定地说，你收集的训练数据库不管里面含了多少封邮件，也不可能找出一封跟目前这封一模一样的。结果呢？我们又该如何来计算 P(d1,d2,..,dnh+) 呢？
我们将 P(d1,d2,..,dnh+) 扩展为： P(d1h+) * P(d2d1, h+) * P(d3d2,d1, h+) * .. 。熟悉这个式子吗？这里我们会使用一个更激进的假设，我们假设 di 与 di-1 是完全条件无关的，于是式子就简化为 P(d1h+) * P(d2h+) * P(d3h+) * .. 。这个就是所谓的条件独立假设，也正是朴素贝叶斯方法的朴素之处。而计算 P(d1h+) * P(d2h+) * P(d3h+) * .. 就太简单了，只要统计 di 这个单词在垃圾邮件中出现的频率即可。关于贝叶斯垃圾邮件过滤更多的内容可以参考这个条目，注意其中提到的其他资料。
一点注记：这里，为什么有这个数据稀疏问题，还是因为统计学习方法工作在浅层面， 世界上的单词就算不再变多也是非常之多的，单词之间组成的句子也是变化多端，更不用说一篇文章了，文章数目则是无穷的，所以在这个层面作统计，肯定要被数据稀疏性困扰。我们要注意，虽然句子和文章的数目是无限的，然而就拿邮件来说，如果我们只关心邮件中句子的语义（进而更高抽象层面的“意图”（语义，意图如何可计算地定义出来是一个人工智能问题），在这个层面上可能性便大大缩减了，我们关心的抽象层面越高，可能性越小。单词集合和句子的对应是多对一的，句子和语义的对应又是多对一的，语义和意图的对应还是多对一的，这是个层级体系。神经科学的发现也表明大脑的皮层大致有一种层级结构，对应着越来越抽象的各个层面，至于如何具体实现一个可放在计算机内的大脑皮层，仍然是一个未解决问题，以上只是一个原则（principle）上的认识，只有当 computational 的 cortex 模型被建立起来了之后才可能将其放入电脑。
5.2 为什么朴素贝叶斯方法令人诧异地好——一个理论解释
朴素贝叶斯方法的条件独立假设看上去很傻很天真，为什么结果却很好很强大呢？就拿一个句子来说，我们怎么能鲁莽地声称其中任意一个单词出现的概率只受到它前面的 3 个或 4 个单词的影响呢？别说 3 个，有时候一个单词的概率受到上一句话的影响都是绝对可能的。那么为什么这个假设在实际中的表现却不比决策树差呢？有人对此提出了一个理论解释，并且建立了什么时候朴素贝叶斯的效果能够等价于非朴素贝叶斯的充要条件，这个解释的核心就是：有些独立假设在各个分类之间的分布都是均匀的所以对于似然的相对大小不产生影响；即便不是如此，也有很大的可能性各个独立假设所产生的消极影响或积极影响互相抵消，最终导致结果受到的影响不大。具体的数学公式请参考这篇 paper 。
6. 层级贝叶斯模型
层级贝叶斯模型是现代贝叶斯方法的标志性建筑之一。前面讲的贝叶斯，都是在同一个事物层次上的各个因素之间进行统计推理，然而层次贝叶斯模型在哲学上更深入了一层，将这些因素背后的因素（原因的原因，原因的原因，以此类推）囊括进来。一个教科书例子是：如果你手头有 N 枚硬币，它们是同一个工厂铸出来的，你把每一枚硬币掷出一个结果，然后基于这 N 个结果对这 N 个硬币的 θ （出现正面的比例）进行推理。如果根据最大似然，每个硬币的 θ 不是 1 就是 0 （这个前面提到过的），然而我们又知道每个硬币的 p(θ) 是有一个先验概率的，也许是一个 beta 分布。也就是说，每个硬币的实际投掷结果 Xi 服从以 θ 为中心的正态分布，而 θ 又服从另一个以 Ψ 为中心的 beta 分布。层层因果关系就体现出来了。进而 Ψ 还可能依赖于因果链上更上层的因素，以此类推。
6.1 隐马可夫模型（HMM）
吴军在数学之美系列里面介绍的隐马可夫模型（HMM）就是一个简单的层级贝叶斯模型：
那么怎么根据接收到的信息来推测说话者想表达的意思呢？我们可以利用叫做“隐含马尔可夫模型”（Hidden Markov Model）来解决这些问题。以语音识别为例，当我们观测到语音信号 o1,o2,o3 时，我们要根据这组信号推测出发送的句子 s1,s2,s3。显然，我们应该在所有可能的句子中找最有可能性的一个。用数学语言来描述，就是在已知 o1,o2,o3,...的情况下，求使得条件概率 P (s1,s2,s3,...o1,o2,o3....) 达到最大值的那个句子 s1,s2,s3,...
吴军的文章中这里省掉没说的是，s1, s2, s3, .. 这个句子的生成概率同时又取决于一组参数，这组参数决定了 s1, s2, s3, .. 这个马可夫链的先验生成概率。如果我们将这组参数记为 λ ，我们实际上要求的是：P(SO, λ) （其中 O 表示 o1,o2,o3,.. ，S表示 s1,s2,s3,..）
当然，上面的概率不容易直接求出，于是我们可以间接地计算它。利用贝叶斯公式并且省掉一个常数项，可以把上述公式等价变换成
P(o1,o2,o3,...s1,s2,s3....) * P(s1,s2,s3,...)
其中
P(o1,o2,o3,...s1,s2,s3....) 表示某句话 s1,s2,s3...被读成 o1,o2,o3,...的可能性, 而 P(s1,s2,s3,...) 表示字串 s1,s2,s3,...本身能够成为一个合乎情理的句子的可能性，所以这个公式的意义是用发送信号为 s1,s2,s3...这个数列的可能性乘以 s1,s2,s3.. 本身可以一个句子的可能性，得出概率。
这里，s1,s2,s3...本身可以一个句子的可能性其实就取决于参数 λ ，也就是语言模型。所以简而言之就是发出的语音信号取决于背后实际想发出的句子，而背后实际想发出的句子本身的独立先验概率又取决于语言模型。
7. 贝叶斯网络
吴军已经对贝叶斯网络作了科普，请直接跳转到这里。更详细的理论参考所有机器学习的书上都有。
参考资料：
一堆机器学习，一堆概率统计，一堆 Google ，和一堆 Wikipedia 条目，一堆 paper 。
By 刘未鹏(pongba)
C++的罗浮宫(http://blog.csdn.net/pongba)
TopLanguage(http://groups.google.com/group/pongba)
概率论只不过是把常识用数学公式表达了出来。
——拉普拉斯
记得读本科的时候，最喜欢到城里的计算机书店里面去闲逛，一逛就是好几个小时；有一次，在书店看到一本书，名叫贝叶斯方法。当时数学系的课程还没有学到概率统计。我心想，一个方法能够专门写出一本书来，肯定很牛逼。后来，我发现当初的那个朴素归纳推理成立了——这果然是个牛逼的方法。
——题记
目录
0. 前言
1. 历史
1.1 一个例子：自然语言的二义性
1.2 贝叶斯公式
2. 拼写纠正
3. 模型比较与贝叶斯奥卡姆剃刀
3.1 再访拼写纠正
3.2 模型比较理论（Model Comparasion）与贝叶斯奥卡姆剃刀（Bayesian Occam’s Razor）
3.3 最小描述长度原则
3.4 最优贝叶斯推理
4. 无处不在的贝叶斯
4.1 中文分词
4.2 统计机器翻译
4.3 贝叶斯图像识别，Analysis by Synthesis
4.4 EM 算法与基于模型的聚类
4.5 最大似然与最小二乘
5. 朴素贝叶斯方法（又名“愚蠢者的贝叶斯（idiot’s bayes）”）
5.1 垃圾邮件过滤器
5.2 为什么朴素贝叶斯方法令人诧异地好——一个理论解释
6. 层级贝叶斯模型
6.1 隐马可夫模型（HMM）
7. 贝叶斯网络
0. 前言
这是一篇关于贝叶斯方法的科普文，我会尽量少用公式，多用平白的语言叙述，多举实际例子。更严格的公式和计算我会在相应的地方注明参考资料。贝叶斯方法被证明是非常 general 且强大的推理框架，文中你会看到很多有趣的应用。
1. 历史
托马斯·贝叶斯（Thomas Bayes）同学的详细生平在这里。以下摘一段 wikipedia 上的简介：
所谓的贝叶斯方法源于他生前为解决一个“逆概”问题写的一篇文章，而这篇文章是在他死后才由他的一位朋友发表出来的。在贝叶斯写这篇文章之前，人们已经能够计算“正向概率”，如“假设袋子里面有N个白球，M个黑球，你伸手进去摸一把，摸出黑球的概率是多大”。而一个自然而然的问题是反过来：“如果我们事先并不知道袋子里面黑白球的比例，而是闭着眼睛摸出一个（或好几个）球，观察这些取出来的球的颜色之后，那么我们可以就此对袋子里面的黑白球的比例作出什么样的推测”。这个问题，就是所谓的逆概问题。
实际上，贝叶斯当时的论文只是对这个问题的一个直接的求解尝试，并不清楚他当时是不是已经意识到这里面包含着的深刻的思想。然而后来，贝叶斯方法席卷了概率论，并将应用延伸到各个问题领域，所有需要作出概率预测的地方都可以见到贝叶斯方法的影子，特别地，贝叶斯是机器学习的核心方法之一。这背后的深刻原因在于，现实世界本身就是不确定的，人类的观察能力是有局限性的（否则有很大一部分科学就没有必要做了——设想我们能够直接观察到电子的运行，还需要对原子模型争吵不休吗？），我们日常所观察到的只是事物表面上的结果，沿用刚才那个袋子里面取球的比方，我们往往只能知道从里面取出来的球是什么颜色，而并不能直接看到袋子里面实际的情况。这个时候，我们就需要提供一个猜测（hypothesis，更为严格的说法是“假设”，这里用“猜测”更通俗易懂一点），所谓猜测，当然就是不确定的（很可能有好多种乃至无数种猜测都能满足目前的观测），但也绝对不是两眼一抹黑瞎蒙——具体地说，我们需要做两件事情：1. 算出各种不同猜测的可能性大小。2. 算出最靠谱的猜测是什么。第一个就是计算特定猜测的后验概率，对于连续的猜测空间则是计算猜测的概率密度函数。第二个则是所谓的模型比较，模型比较如果不考虑先验概率的话就是最大似然方法。
1.1 一个例子：自然语言的二义性
下面举一个自然语言的不确定性的例子。当你看到这句话：
The girl saw the boy with a telescope.
你对这句话的含义有什么猜测？平常人肯定会说：那个女孩拿望远镜看见了那个男孩（即你对这个句子背后的实际语法结构的猜测是：The girl saw-with-a-telescope the boy ）。然而，仔细一想，你会发现这个句子完全可以解释成：那个女孩看见了那个拿着望远镜的男孩（即：The girl saw the-boy-with-a-telescope ）。那为什么平常生活中我们每个人都能够迅速地对这种二义性进行消解呢？这背后到底隐藏着什么样的思维法则？我们留到后面解释。
1.2 贝叶斯公式
贝叶斯公式是怎么来的？
我们还是使用 wikipedia 上的一个例子：
一所学校里面有 60% 的男生，40% 的女生。男生总是穿长裤，女生则一半穿长裤一半穿裙子。有了这些信息之后我们可以容易地计算“随机选取一个学生，他（她）穿长裤的概率和穿裙子的概率是多大”，这个就是前面说的“正向概率”的计算。然而，假设你走在校园中，迎面走来一个穿长裤的学生（很不幸的是你高度近似，你只看得见他（她）穿的是否长裤，而无法确定他（她）的性别），你能够推断出他（她）是男生的概率是多大吗？
一些认知科学的研究表明（《决策与判断》以及《Rationality for Mortals》第12章：小孩也可以解决贝叶斯问题），我们对形式化的贝叶斯问题不擅长，但对于以频率形式呈现的等价问题却很擅长。在这里，我们不妨把问题重新叙述成：你在校园里面随机游走，遇到了 N 个穿长裤的人（仍然假设你无法直接观察到他们的性别），问这 N 个人里面有多少个女生多少个男生。
你说，这还不简单：算出学校里面有多少穿长裤的，然后在这些人里面再算出有多少女生，不就行了？
我们来算一算：假设学校里面人的总数是 U 个。60% 的男生都穿长裤，于是我们得到了 U * P(Boy) * P(PantsBoy) 个穿长裤的（男生）（其中 P(Boy) 是男生的概率 = 60%，这里可以简单的理解为男生的比例；P(PantsBoy) 是条件概率，即在 Boy 这个条件下穿长裤的概率是多大，这里是 100% ，因为所有男生都穿长裤）。40% 的女生里面又有一半（50%）是穿长裤的，于是我们又得到了 U * P(Girl) * P(PantsGirl) 个穿长裤的（女生）。加起来一共是 U * P(Boy) * P(PantsBoy) + U * P(Girl) * P(PantsGirl) 个穿长裤的，其中有 U * P(Girl) * P(PantsGirl) 个女生。两者一比就是你要求的答案。
下面我们把这个答案形式化一下：我们要求的是 P(GirlPants) （穿长裤的人里面有多少女生），我们计算的结果是 U * P(Girl) * P(PantsGirl) / [U * P(Boy) * P(PantsBoy) + U * P(Girl) * P(PantsGirl)] 。容易发现这里校园内人的总数是无关的，可以消去。于是得到
P(GirlPants) = P(Girl) * P(PantsGirl) / [P(Boy) * P(PantsBoy) + P(Girl) * P(PantsGirl)]
注意，如果把上式收缩起来，分母其实就是 P(Pants) ，分子其实就是 P(Pants, Girl) 。而这个比例很自然地就读作：在穿长裤的人（ P(Pants) ）里面有多少（穿长裤）的女孩（ P(Pants, Girl) ）。
上式中的 Pants 和 Boy/Girl 可以指代一切东西，所以其一般形式就是：
P(BA) = P(AB) * P(B) / [P(AB) * P(B) + P(A~B) * P(~B) ]
收缩起来就是：
P(BA) = P(AB) / P(A)
其实这个就等于：
P(BA) * P(A) = P(AB)
难怪拉普拉斯说概率论只是把常识用数学公式表达了出来。
然而，后面我们会逐渐发现，看似这么平凡的贝叶斯公式，背后却隐含着非常深刻的原理。
2. 拼写纠正
经典著作《人工智能：现代方法》的作者之一 Peter Norvig 曾经写过一篇介绍如何写一个拼写检查/纠正器的文章（原文在这里，徐宥的翻译版在这里，这篇文章很深入浅出，强烈建议读一读），里面用到的就是贝叶斯方法，这里我们不打算复述他写的文章，而是简要地将其核心思想介绍一下。
首先，我们需要询问的是：“问题是什么？”
问题是我们看到用户输入了一个不在字典中的单词，我们需要去猜测：“这个家伙到底真正想输入的单词是什么呢？”用刚才我们形式化的语言来叙述就是，我们需要求：
P(我们猜测他想输入的单词 他实际输入的单词)
这个概率。并找出那个使得这个概率最大的猜测单词。显然，我们的猜测未必是唯一的，就像前面举的那个自然语言的歧义性的例子一样；这里，比如用户输入： thew ，那么他到底是想输入 the ，还是想输入 thaw ？到底哪个猜测可能性更大呢？幸运的是我们可以用贝叶斯公式来直接出它们各自的概率，我们不妨将我们的多个猜测记为 h1 h2 .. （ h 代表 hypothesis），它们都属于一个有限且离散的猜测空间 H （单词总共就那么多而已），将用户实际输入的单词记为 D （ D 代表 Data ，即观测数据），于是
P(我们的猜测1 他实际输入的单词)
可以抽象地记为：
P(h1 D)
类似地，对于我们的猜测2，则是 P(h2 D)。不妨统一记为：
P(h D)
运用一次贝叶斯公式，我们得到：
P(h D) = P(h) * P(D h) / P(D)
对于不同的具体猜测 h1 h2 h3 .. ，P(D) 都是一样的，所以在比较 P(h1 D) 和 P(h2 D) 的时候我们可以忽略这个常数。即我们只需要知道：
P(h D) ∝ P(h) * P(D h) （注：那个符号的意思是“正比例于”，不是无穷大，注意符号右端是有一个小缺口的。）
这个式子的抽象含义是：对于给定观测数据，一个猜测是好是坏，取决于“这个猜测本身独立的可能性大小（先验概率，Prior ）”和“这个猜测生成我们观测到的数据的可能性大小”（似然，Likelihood ）的乘积。具体到我们的那个 thew 例子上，含义就是，用户实际是想输入 the 的可能性大小取决于 the 本身在词汇表中被使用的可能性（频繁程度）大小（先验概率）和 想打 the 却打成 thew 的可能性大小（似然）的乘积。
下面的事情就很简单了，对于我们猜测为可能的每个单词计算一下 P(h) * P(D h) 这个值，然后取最大的，得到的就是最靠谱的猜测。
一点注记：Norvig 的拼写纠正器里面只提取了编辑距离为 2 以内的所有已知单词。这是为了避免去遍历字典中每个单词计算它们的 P(h) * P(D h) ，但这种做法为了节省时间带来了一些误差。但话说回来难道我们人类真的回去遍历每个可能的单词来计算他们的后验概率吗？不可能。实际上，根据认知神经科学的观点，我们首先根据错误的单词做一个 bottom-up 的关联提取，提取出有可能是实际单词的那些候选单词，这个提取过程就是所谓的基于内容的提取，可以根据错误单词的一些模式片段提取出有限的一组候选，非常快地缩小的搜索空间（比如我输入 explaination ，单词里面就有充分的信息使得我们的大脑在常数时间内把可能性 narrow down 到 explanation 这个单词上，至于具体是根据哪些线索——如音节——来提取，又是如何在生物神经网络中实现这个提取机制的，目前还是一个没有弄清的领域）。然后，我们对这有限的几个猜测做一个 top-down 的预测，看看到底哪个对于观测数据（即错误单词）的预测效力最好，而如何衡量预测效率则就是用贝叶斯公式里面的那个 P(h) * P(D h) 了——虽然我们很可能使用了一些启发法来简化计算。后面我们还会提到这样的 bottom-up 的关联提取。
3. 模型比较与奥卡姆剃刀
3.1 再访拼写纠正
介绍了贝叶斯拼写纠正之后，接下来的一个自然而然的问题就来了：“为什么？”为什么要用贝叶斯公式？为什么贝叶斯公式在这里可以用？我们可以很容易地领会为什么贝叶斯公式用在前面介绍的那个男生女生长裤裙子的问题里是正确的。但为什么这里？
为了回答这个问题，一个常见的思路就是想想：非得这样吗？因为如果你想到了另一种做法并且证明了它也是靠谱的，那么将它与现在这个一比较，也许就能得出很有价值的信息。那么对于拼写纠错问题你能想到其他方案吗？
不管怎样，一个最常见的替代方案就是，选择离 thew 的编辑距离最近的。然而 the 和 thaw 离 thew 的编辑距离都是 1 。这可咋办捏？你说，不慌，那还是好办。我们就看到底哪个更可能被错打为 thew 就是了。我们注意到字母 e 和字母 w 在键盘上离得很紧，无名指一抽筋就不小心多打出一个 w 来，the 就变成 thew 了。而另一方面 thaw 被错打成 thew 的可能性就相对小一点，因为 e 和 a 离得较远而且使用的指头相差一个指头（一个是中指一个是小指，不像 e 和 w 使用的指头靠在一块——神经科学的证据表明紧邻的身体设施之间容易串位）。OK，很好，因为你现在已经是在用最大似然方法了，或者直白一点，你就是在计算那个使得 P(D h) 最大的 h 。
而贝叶斯方法计算的是什么？是 P(h) * P(D h) 。多出来了一个 P(h) 。我们刚才说了，这个多出来的 P(h) 是特定猜测的先验概率。为什么要掺和进一个先验概率？刚才说的那个最大似然不是挺好么？很雄辩地指出了 the 是更靠谱的猜测。有什么问题呢？既然这样，我们就从给最大似然找茬开始吧——我们假设两者的似然程度是一样或非常相近，这样不就难以区分哪个猜测更靠谱了吗？比如用户输入tlp ，那到底是 top 还是 tip ？（这个例子不怎么好，因为 top 和 tip 的词频可能仍然是接近的，但一时想不到好的英文单词的例子，我们不妨就假设 top 比 tip 常见许多吧，这个假设并不影响问题的本质。）这个时候，当最大似然不能作出决定性的判断时，先验概率就可以插手进来给出指示——“既然你无法决定，那么我告诉你，一般来说 top 出现的程度要高许多，所以更可能他想打的是 top ”）。
以上只是最大似然的一个问题，即并不能提供决策的全部信息。
最大似然还有另一个问题：即便一个猜测与数据非常符合，也并不代表这个猜测就是更好的猜测，因为这个猜测本身的可能性也许就非常低。比如 MacKay 在《Information Theory : Inference and Learning Algorithms》里面就举了一个很好的例子：-1 3 7 11 你说是等差数列更有可能呢？还是 -X^3 / 11 + 9/11*X^2 + 23/11 每项把前项作为 X 带入后计算得到的数列？此外曲线拟合也是，平面上 N 个点总是可以用 N-1 阶多项式来完全拟合，当 N 个点近似但不精确共线的时候，用 N-1 阶多项式来拟合能够精确通过每一个点，然而用直线来做拟合/线性回归的时候却会使得某些点不能位于直线上。你说到底哪个好呢？多项式？还是直线？一般地说肯定是越低阶的多项式越靠谱（当然前提是也不能忽视“似然”P(D h) ，明摆着一个多项式分布您愣是去拿直线拟合也是不靠谱的，这就是为什么要把它们两者乘起来考虑。），原因之一就是低阶多项式更常见，先验概率（ P(h) ）较大（原因之二则隐藏在 P(D h) 里面），这就是为什么我们要用样条来插值，而不是直接搞一个 N-1 阶多项式来通过任意 N 个点的原因。
以上分析当中隐含的哲学是，观测数据总是会有各种各样的误差，比如观测误差（比如你观测的时候一个 MM 经过你一不留神，手一抖就是一个误差出现了），所以如果过分去寻求能够完美解释观测数据的模型，就会落入所谓的数据过配（overfitting）的境地，一个过配的模型试图连误差（噪音）都去解释（而实际上噪音又是不需要解释的），显然就过犹不及了。所以 P(D h) 大不代表你的 h （猜测）就是更好的 h。还要看 P(h) 是怎样的。所谓奥卡姆剃刀精神就是说：如果两个理论具有相似的解释力度，那么优先选择那个更简单的（往往也正是更平凡的，更少繁复的，更常见的）。
过分匹配的另一个原因在于当观测的结果并不是因为误差而显得“不精确”而是因为真实世界中对数据的结果产生贡献的因素太多太多，跟噪音不同，这些偏差是一些另外的因素集体贡献的结果，不是你的模型所能解释的——噪音那是不需要解释——一个现实的模型往往只提取出几个与结果相关度很高，很重要的因素（cause）。这个时候观察数据会倾向于围绕你的有限模型的预测结果呈正态分布，于是你实际观察到的结果就是这个正态分布的随机取样，这个取样很可能受到其余因素的影响偏离你的模型所预测的中心，这个时候便不能贪心不足地试图通过改变模型来“完美”匹配数据，因为那些使结果偏离你的预测的贡献因素不是你这个有限模型里面含有的因素所能概括的，硬要打肿脸充胖子只能导致不实际的模型，举个教科书例子：身高和体重的实际关系近似于一个二阶多项式的关系，但大家都知道并不是只有身高才会对体重产生影响，物理世界影响体重的因素太多太多了，有人身材高大却瘦得跟稻草，有人却是横长竖不长。但不可否认的是总体上来说，那些特殊情况越是特殊就越是稀少，呈围绕最普遍情况（胖瘦适中）的正态分布，这个分布就保证了我们的身高——体重相关模型能够在大多数情况下做出靠谱的预测。但是——刚才说了，特例是存在的，就算不是特例，人有胖瘦，密度也有大小，所以完美符合身高——体重的某个假想的二阶多项式关系的人是不存在的，我们又不是欧几里德几何世界当中的理想多面体，所以，当我们对人群随机抽取了 N 个样本（数据点）试图对这 N 个数据点拟合出一个多项式的话就得注意，它肯定得是二阶多项式，我们要做的只是去根据数据点计算出多项式各项的参数（一个典型的方法就是最小二乘）；它肯定不是直线（我们又不是稻草），也不是三阶多项式四阶多项式.. 如果硬要完美拟合 N 个点，你可能会整出一个 N-1 阶多项式来——设想身高和体重的关系是 5 阶多项式看看？
3.2 模型比较理论（Model Comparasion）与贝叶斯奥卡姆剃刀（Bayesian Occam’s Razor）
实际上，模型比较就是去比较哪个模型（猜测）更可能隐藏在观察数据的背后。其基本思想前面已经用拼写纠正的例子来说明了。我们对用户实际想输入的单词的猜测就是模型，用户输错的单词就是观测数据。我们通过：
P(h D) ∝ P(h) * P(D h)
来比较哪个模型最为靠谱。前面提到，光靠 P(D h) （即“似然”）是不够的，有时候还需要引入 P(h) 这个先验概率。奥卡姆剃刀就是说 P(h) 较大的模型有较大的优势，而最大似然则是说最符合观测数据的（即 P(D h) 最大的）最有优势。整个模型比较就是这两方力量的拉锯。我们不妨再举一个简单的例子来说明这一精神：你随便找枚硬币，掷一下，观察一下结果。好，你观察到的结果要么是“正”，要么是“反”（不，不是少林足球那枚硬币:P ），不妨假设你观察到的是“正”。现在你要去根据这个观测数据推断这枚硬币掷出“正”的概率是多大。根据最大似然估计的精神，我们应该猜测这枚硬币掷出“正”的概率是 1 ，因为这个才是能最大化 P(D h) 的那个猜测。然而每个人都会大摇其头——很显然，你随机摸出一枚硬币这枚硬币居然没有反面的概率是“不存在的”，我们对一枚随机硬币是否一枚有偏硬币，偏了多少，是有着一个先验的认识的，这个认识就是绝大多数硬币都是基本公平的，偏得越多的硬币越少见（可以用一个 beta 分布来表达这一先验概率）。将这个先验正态分布 p(θ) （其中 θ 表示硬币掷出正面的比例，小写的 p 代表这是概率密度函数）结合到我们的问题中，我们便不是去最大化 P(D h) ，而是去最大化 P(D θ) * p(θ) ，显然 θ = 1 是不行的，因为 P(θ=1) 为 0 ，导致整个乘积也为 0 。实际上，只要对这个式子求一个导数就可以得到最值点。
以上说的是当我们知道先验概率 P(h) 的时候，光用最大似然是不靠谱的，因为最大似然的猜测可能先验概率非常小。然而，有些时候，我们对于先验概率一无所知，只能假设每种猜测的先验概率是均等的，这个时候就只有用最大似然了。实际上，统计学家和贝叶斯学家有一个有趣的争论，统计学家说：我们让数据自己说话。言下之意就是要摒弃先验概率。而贝叶斯支持者则说：数据会有各种各样的偏差，而一个靠谱的先验概率则可以对这些随机噪音做到健壮。事实证明贝叶斯派胜利了，胜利的关键在于所谓先验概率其实也是经验统计的结果，譬如为什么我们会认为绝大多数硬币是基本公平的？为什么我们认为大多数人的肥胖适中？为什么我们认为肤色是种族相关的，而体重则与种族无关？先验概率里面的“先验”并不是指先于一切经验，而是仅指先于我们“当前”给出的观测数据而已，在硬币的例子中先验指的只是先于我们知道投掷的结果这个经验，而并非“先天”。
然而，话说回来，有时候我们必须得承认，就算是基于以往的经验，我们手头的“先验”概率还是均匀分布，这个时候就必须依赖用最大似然，我们用前面留下的一个自然语言二义性问题来说明这一点：
The girl saw the boy with a telescope.
到底是 The girl saw-with-a-telescope the boy 这一语法结构，还是 The girl saw the-boy-with-a-telescope 呢？两种语法结构的常见程度都差不多（你可能会觉得后一种语法结构的常见程度较低，这是事后偏见，你只需想想 The girl saw the boy with a book 就知道了。当然，实际上从大规模语料统计结果来看后一种语法结构的确稍稍不常见一丁点，但是绝对不足以解释我们对第一种结构的强烈倾向）。那么到底为什么呢？
我们不妨先来看看 MacKay 在书中举的一个漂亮的例子：
图中有多少个箱子？特别地，那棵书后面是一个箱子？还是两个箱子？还是三个箱子？还是.. 你可能会觉得树后面肯定是一个箱子，但为什么不是两个呢？如下图：
很简单，你会说：要是真的有两个箱子那才怪了，怎么就那么巧这两个箱子刚刚好颜色相同，高度相同呢？
用概率论的语言来说，你刚才的话就翻译为：猜测 h 不成立，因为 P(D h) 太小（太巧合）了。我们的直觉是：巧合（小概率）事件不会发生。所以当一个猜测（假设）使得我们的观测结果成为小概率事件的时候，我们就说“才怪呢，哪能那么巧捏？！”
现在我们可以回到那个自然语言二义性的例子，并给出一个完美的解释了：如果语法结构是 The girl saw the-boy-with-a-telecope 的话，怎么那个男孩偏偏手里拿的就是望远镜——一个可以被用来 saw-with 的东东捏？这也忒小概率了吧。他咋就不会拿本书呢？拿什么都好。怎么偏偏就拿了望远镜？所以唯一的解释是，这个“巧合”背后肯定有它的必然性，这个必然性就是，如果我们将语法结构解释为 The girl saw-with-a-telescope the boy 的话，就跟数据完美吻合了——既然那个女孩是用某个东西去看这个男孩的，那么这个东西是一个望远镜就完全可以解释了（不再是小概率事件了）。
自然语言二义性很常见，譬如上文中的一句话：
参见《决策与判断》以及《Rationality for Mortals》第12章：小孩也可以解决贝叶斯问题
就有二义性：到底是参见这两本书的第 12 章，还是仅仅是第二本书的第 12 章呢？如果是这两本书的第 12 章那就是咄咄怪事了，怎么恰好两本书都有第 12 章，都是讲同一个问题，更诡异的是，标题还相同呢？
注意，以上做的是似然估计（即只看 P(D h) 的大小），不含先验概率。通过这两个例子，尤其是那个树后面的箱子的例子我们可以看到，似然估计里面也蕴含着奥卡姆剃刀：树后面的箱子数目越多，这个模型就越复杂。单个箱子的模型是最简单的。似然估计选择了更简单的模型。
这个就是所谓的贝叶斯奥卡姆剃刀（Bayesian Occam’s Razor），因为这个剃刀工作在贝叶斯公式的似然（P(D h) ）上，而不是模型本身（ P(h) ）的先验概率上，后者是传统的奥卡姆剃刀。关于贝叶斯奥卡姆剃刀我们再来看一个前面说到的曲线拟合的例子：如果平面上有 N 个点，近似构成一条直线，但绝不精确地位于一条直线上。这时我们既可以用直线来拟合（模型1），也可以用二阶多项式（模型2）拟合，也可以用三阶多项式（模型3），.. ，特别地，用 N-1 阶多项式便能够保证肯定能完美通过 N 个数据点。那么，这些可能的模型之中到底哪个是最靠谱的呢？前面提到，一个衡量的依据是奥卡姆剃刀：越是高阶的多项式越是繁复和不常见。然而，我们其实并不需要依赖于这个先验的奥卡姆剃刀，因为有人可能会争辩说：你怎么就能说越高阶的多项式越不常见呢？我偏偏觉得所有阶多项式都是等可能的。好吧，既然如此那我们不妨就扔掉 P(h) 项，看看 P(D h) 能告诉我们什么。我们注意到越是高阶的多项式，它的轨迹弯曲程度越是大，到了八九阶简直就是直上直下，于是我们不仅要问：一个比如说八阶多项式在平面上随机生成的一堆 N 个点偏偏恰好近似构成一条直线的概率（即 P(D h) ）有多大？太小太小了。反之，如果背后的模型是一条直线，那么根据该模型生成一堆近似构成直线的点的概率就大得多了。这就是贝叶斯奥卡姆剃刀。
这里只是提供一个关于贝叶斯奥卡姆剃刀的科普，强调直观解释，更多理论公式请参考 MacKay 的著作 《Information Theory : Inference and Learning Algorithms》第 28 章。
3.3 最小描述长度原则
贝叶斯模型比较理论与信息论有一个有趣的关联：
P(h D) ∝ P(h) * P(D h)
两边求对数，将右式的乘积变成相加：
ln P(h D) ∝ ln P(h) + ln P(D h)
显然，最大化 P(h D) 也就是最大化 ln P(h D)。而 ln P(h) + ln P(D h) 则可以解释为模型（或者称“假设”、“猜测”）h 的编码长度加上在该模型下数据 D 的编码长度。使这个和最小的模型就是最佳模型。
而究竟如何定义一个模型的编码长度，以及数据在模型下的编码长度则是一个问题。更多可参考 Mitchell 的 《Machine Learning》的 6.6 节，或 Mackay 的 28.3 节）
3.4 最优贝叶斯推理
所谓的推理，分为两个过程，第一步是对观测数据建立一个模型。第二步则是使用这个模型来推测未知现象发生的概率。我们前面都是讲的对于观测数据给出最靠谱的那个模型。然而很多时候，虽然某个模型是所有模型里面最靠谱的，但是别的模型也并不是一点机会都没有。譬如第一个模型在观测数据下的概率是 0.5 。第二个模型是 0.4 ，第三个是 0.1 。如果我们只想知道对于观测数据哪个模型最可能，那么只要取第一个就行了，故事到此结束。然而很多时候我们建立模型是为了推测未知的事情的发生概率，这个时候，三个模型对未知的事情发生的概率都会有自己的预测，仅仅因为某一个模型概率稍大一点就只听他一个人的就太不民主了。所谓的最优贝叶斯推理就是将三个模型对于未知数据的预测结论加权平均起来（权值就是模型相应的概率）。显然，这个推理是理论上的制高点，无法再优了，因为它已经把所有可能性都考虑进去了。
只不过实际上我们是基本不会使用这个框架的，因为计算模型可能非常费时间，二来模型空间可能是连续的，即有无穷多个模型（这个时候需要计算模型的概率分布）。结果还是非常费时间。所以这个被看作是一个理论基准。
4. 无处不在的贝叶斯
以下我们再举一些实际例子来说明贝叶斯方法被运用的普遍性，这里主要集中在机器学习方面，因为我不是学经济的，否则还可以找到一堆经济学的例子。
4.1 中文分词
贝叶斯是机器学习的核心方法之一。比如中文分词领域就用到了贝叶斯。Google 研究员吴军在《数学之美》系列中就有一篇是介绍中文分词的，这里只介绍一下核心的思想，不做赘述，详细请参考吴军的文章（这里）。
分词问题的描述为：给定一个句子（字串），如：
南京市长江大桥
如何对这个句子进行分词（词串）才是最靠谱的。例如：
1. 南京市/长江大桥
2. 南京/市长/江大桥
这两个分词，到底哪个更靠谱呢？
我们用贝叶斯公式来形式化地描述这个问题，令 X 为字串（句子），Y 为词串（一种特定的分词假设）。我们就是需要寻找使得 P(YX) 最大的 Y ，使用一次贝叶斯可得：
P(YX) ∝ P(Y)*P(XY)
用自然语言来说就是 这种分词方式（词串）的可能性 乘以 这个词串生成我们的句子的可能性。我们进一步容易看到：可以近似地将 P(XY) 看作是恒等于 1 的，因为任意假想的一种分词方式之下生成我们的句子总是精准地生成的（只需把分词之间的分界符号扔掉即可）。于是，我们就变成了去最大化 P(Y) ，也就是寻找一种分词使得这个词串（句子）的概率最大化。而如何计算一个词串：
W1, W2, W3, W4 ..
的可能性呢？我们知道，根据联合概率的公式展开：P(W1, W2, W3, W4 ..) = P(W1) * P(W2W1) * P(W3W2, W1) * P(W4W1,W2,W3) * .. 于是我们可以通过一系列的条件概率（右式）的乘积来求整个联合概率。然而不幸的是随着条件数目的增加（P(WnWn-1,Wn-2,..,W1) 的条件有 n-1 个），数据稀疏问题也会越来越严重，即便语料库再大也无法统计出一个靠谱的 P(WnWn-1,Wn-2,..,W1) 来。为了缓解这个问题，计算机科学家们一如既往地使用了“天真”假设：我们假设句子中一个词的出现概率只依赖于它前面的有限的 k 个词（k 一般不超过 3，如果只依赖于前面的一个词，就是2元语言模型（2-gram），同理有 3-gram 、 4-gram 等），这个就是所谓的“有限地平线”假设。虽然这个假设很傻很天真，但结果却表明它的结果往往是很好很强大的，后面要提到的朴素贝叶斯方法使用的假设跟这个精神上是完全一致的，我们会解释为什么像这样一个天真的假设能够得到强大的结果。目前我们只要知道，有了这个假设，刚才那个乘积就可以改写成： P(W1) * P(W2W1) * P(W3W2) * P(W4W3) .. （假设每个词只依赖于它前面的一个词）。而统计 P(W2W1) 就不再受到数据稀疏问题的困扰了。对于我们上面提到的例子“南京市长江大桥”，如果按照自左到右的贪婪方法分词的话，结果就成了“南京市长/江大桥”。但如果按照贝叶斯分词的话（假设使用 3-gram），由于“南京市长”和“江大桥”在语料库中一起出现的频率为 0 ，这个整句的概率便会被判定为 0 。 从而使得“南京市/长江大桥”这一分词方式胜出。
一点注记：有人可能会疑惑，难道我们人类也是基于这些天真的假设来进行推理的？不是的。事实上，统计机器学习方法所统计的东西往往处于相当表层（shallow）的层面，在这个层面机器学习只能看到一些非常表面的现象，有一点科学研究的理念的人都知道：越是往表层去，世界就越是繁复多变。从机器学习的角度来说，特征（feature）就越多，成百上千维度都是可能的。特征一多，好了，高维诅咒就产生了，数据就稀疏得要命，不够用了。而我们人类的观察水平显然比机器学习的观察水平要更深入一些，为了避免数据稀疏我们不断地发明各种装置（最典型就是显微镜），来帮助我们直接深入到更深层的事物层面去观察更本质的联系，而不是在浅层对表面现象作统计归纳。举一个简单的例子，通过对大规模语料库的统计，机器学习可能会发现这样一个规律：所有的“他”都是不会穿 bra 的，所有的“她”则都是穿的。然而，作为一个男人，却完全无需进行任何统计学习，因为深层的规律就决定了我们根本不会去穿 bra 。至于机器学习能不能完成后者（像人类那样的）这个推理，则是人工智能领域的经典问题。至少在那之前，声称统计学习方法能够终结科学研究（原文）的说法是纯粹外行人说的话。
4.2 统计机器翻译
统计机器翻译因为其简单，自动（无需手动添加规则），迅速成为了机器翻译的事实标准。而统计机器翻译的核心算法也是使用的贝叶斯方法。
问题是什么？统计机器翻译的问题可以描述为：给定一个句子 e ，它的可能的外文翻译 f 中哪个是最靠谱的。即我们需要计算：P(fe) 。一旦出现条件概率贝叶斯总是挺身而出：
P(fe) ∝ P(f) * P(ef)
这个式子的右端很容易解释：那些先验概率较高，并且更可能生成句子 e 的外文句子 f 将会胜出。我们只需简单统计（结合上面提到的 N-Gram 语言模型）就可以统计任意一个外文句子 f 的出现概率。然而 P(ef) 却不是那么好求的，给定一个候选的外文局子 f ，它生成（或对应）句子 e 的概率是多大呢？我们需要定义什么叫 “对应”，这里需要用到一个分词对齐的平行语料库，有兴趣的可以参考 《Foundations of Statistical Natural Language Processing》第 13 章，这里摘选其中的一个例子：假设 e 为：John loves Mary 。我们需要考察的首选 f 是：Jean aime Marie （法文）。我们需要求出 P(ef) 是多大，为此我们考虑 e 和 f 有多少种对齐的可能性，如：
John (Jean) loves (aime) Marie (Mary)
就是其中的一种（最靠谱的）对齐，为什么要对齐，是因为一旦对齐了之后，就可以容易地计算在这个对齐之下的 P(ef) 是多大，只需计算：
P(JohnJean) * P(lovesaime) * P(MarieMary)
即可。
然后我们遍历所有的对齐方式，并将每种对齐方式之下的翻译概率 ∑ 求和。便可以获得整个的 P(ef) 是多大。
一点注记：还是那个问题：难道我们人类真的是用这种方式进行翻译的？highly unlikely 。这种计算复杂性非常高的东西连三位数乘法都搞不定的我们才不会笨到去使用呢。根据认知神经科学的认识，很可能我们是先从句子到语义（一个逐层往上（bottom-up）抽象的 folding 过程），然后从语义根据另一门语言的语法展开为另一门语言（一个逐层往下（top-down）的具体化 unfolding 过程）。如何可计算地实现这个过程，目前仍然是个难题。（我们看到很多地方都有 bottom-up/top-down 这样一个对称的过程，实际上有人猜测这正是生物神经网络原则上的运作方式，对视觉神经系统的研究尤其证明了这一点，Hawkins 在 《On Intelligence》 里面提出了一种 HTM （Hierarchical Temporal Memory）模型正是使用了这个原则。）
4.3 贝叶斯图像识别，Analysis by Synthesis
贝叶斯方法是一个非常 general 的推理框架。其核心理念可以描述成：Analysis by Synthesis （通过合成来分析）。06 年的认知科学新进展上有一篇 paper 就是讲用贝叶斯推理来解释视觉识别的，一图胜千言，下图就是摘自这篇 paper ：
首先是视觉系统提取图形的边角特征，然后使用这些特征自底向上地激活高层的抽象概念（比如是 E 还是 F 还是等号），然后使用一个自顶向下的验证来比较到底哪个概念最佳地解释了观察到的图像。
4.4 EM 算法与基于模型的聚类
聚类是一种无指导的机器学习问题，问题描述：给你一堆数据点，让你将它们最靠谱地分成一堆一堆的。聚类算法很多，不同的算法适应于不同的问题，这里仅介绍一个基于模型的聚类，该聚类算法对数据点的假设是，这些数据点分别是围绕 K 个核心的 K 个正态分布源所随机生成的，使用 Han JiaWei 的《Data Ming： Concepts and Techniques》中的图：
图中有两个正态分布核心，生成了大致两堆点。我们的聚类算法就是需要根据给出来的那些点，算出这两个正态分布的核心在什么位置，以及分布的参数是多少。这很明显又是一个贝叶斯问题，但这次不同的是，答案是连续的且有无穷多种可能性，更糟的是，只有当我们知道了哪些点属于同一个正态分布圈的时候才能够对这个分布的参数作出靠谱的预测，现在两堆点混在一块我们又不知道哪些点属于第一个正态分布，哪些属于第二个。反过来，只有当我们对分布的参数作出了靠谱的预测时候，才能知道到底哪些点属于第一个分布，那些点属于第二个分布。这就成了一个先有鸡还是先有蛋的问题了。为了解决这个循环依赖，总有一方要先打破僵局，说，不管了，我先随便整一个值出来，看你怎么变，然后我再根据你的变化调整我的变化，然后如此迭代着不断互相推导，最终收敛到一个解。这就是 EM 算法。
EM 的意思是“Expectation-Maximazation”，在这个聚类问题里面，我们是先随便猜一下这两个正态分布的参数：如核心在什么地方，方差是多少。然后计算出每个数据点更可能属于第一个还是第二个正态分布圈，这个是属于 Expectation 一步。有了每个数据点的归属，我们就可以根据属于第一个分布的数据点来重新评估第一个分布的参数（从蛋再回到鸡），这个是 Maximazation 。如此往复，直到参数基本不再发生变化为止。这个迭代收敛过程中的贝叶斯方法在第二步，根据数据点求分布的参数上面。
4.5 最大似然与最小二乘
学过线性代数的大概都知道经典的最小二乘方法来做线性回归。问题描述是：给定平面上 N 个点，（这里不妨假设我们想用一条直线来拟合这些点——回归可以看作是拟合的特例，即允许误差的拟合），找出一条最佳描述了这些点的直线。
一个接踵而来的问题就是，我们如何定义最佳？我们设每个点的坐标为 (Xi, Yi) 。如果直线为 y = f(x) 。那么 (Xi, Yi) 跟直线对这个点的“预测”：(Xi, f(Xi)) 就相差了一个 ΔYi = Yi – f(Xi) 。最小二乘就是说寻找直线使得 (ΔY1)^2 + (ΔY2)^2 + .. （即误差的平方和）最小，至于为什么是误差的平方和而不是误差的绝对值和，统计学上也没有什么好的解释。然而贝叶斯方法却能对此提供一个完美的解释。
我们假设直线对于坐标 Xi 给出的预测 f(Xi) 是最靠谱的预测，所有纵坐标偏离 f(Xi) 的那些数据点都含有噪音，是噪音使得它们偏离了完美的一条直线，一个合理的假设就是偏离路线越远的概率越小，具体小多少，可以用一个正态分布曲线来模拟，这个分布曲线以直线对 Xi 给出的预测 f(Xi) 为中心，实际纵坐标为 Yi 的点 (Xi, Yi) 发生的概率就正比于 EXP[-(ΔYi)^2]。（EXP(..) 代表以常数 e 为底的多少次方）。
现在我们回到问题的贝叶斯方面，我们要想最大化的后验概率是：
P(hD) ∝ P(h) * P(Dh)
又见贝叶斯！这里 h 就是指一条特定的直线，D 就是指这 N 个数据点。我们需要寻找一条直线 h 使得 P(h) * P(Dh) 最大。很显然，P(h) 这个先验概率是均匀的，因为哪条直线也不比另一条更优越。所以我们只需要看 P(Dh) 这一项，这一项是指这条直线生成这些数据点的概率，刚才说过了，生成数据点 (Xi, Yi) 的概率为 EXP[-(ΔYi)^2] 乘以一个常数。而 P(Dh) = P(d1h) * P(d2h) * .. 即假设各个数据点是独立生成的，所以可以把每个概率乘起来。于是生成 N 个数据点的概率为 EXP[-(ΔY1)^2] * EXP[-(ΔY2)^2] * EXP[-(ΔY3)^2] * .. = EXP{-[(ΔY1)^2 + (ΔY2)^2 + (ΔY3)^2 + ..]} 最大化这个概率就是要最小化 (ΔY1)^2 + (ΔY2)^2 + (ΔY3)^2 + .. 。 熟悉这个式子吗？
5. 朴素贝叶斯方法
朴素贝叶斯方法是一个很特别的方法，所以值得介绍一下。我们用朴素贝叶斯在垃圾邮件过滤中的应用来举例说明。
5.1 贝叶斯垃圾邮件过滤器
问题是什么？问题是，给定一封邮件，判定它是否属于垃圾邮件。按照先例，我们还是用 D 来表示这封邮件，注意 D 由 N 个单词组成。我们用 h+ 来表示垃圾邮件，h- 表示正常邮件。问题可以形式化地描述为求：
P(h+D) = P(h+) * P(Dh+) / P(D)
P(h-D) = P(h-) * P(Dh-) / P(D)
其中 P(h+) 和 P(h-) 这两个先验概率都是很容易求出来的，只需要计算一个邮件库里面垃圾邮件和正常邮件的比例就行了。然而 P(Dh+) 却不容易求，因为 D 里面含有 N 个单词 d1, d2, d3, .. ，所以P(Dh+) = P(d1,d2,..,dnh+) 。我们又一次遇到了数据稀疏性，为什么这么说呢？P(d1,d2,..,dnh+) 就是说在垃圾邮件当中出现跟我们目前这封邮件一模一样的一封邮件的概率是多大！开玩笑，每封邮件都是不同的，世界上有无穷多封邮件。瞧，这就是数据稀疏性，因为可以肯定地说，你收集的训练数据库不管里面含了多少封邮件，也不可能找出一封跟目前这封一模一样的。结果呢？我们又该如何来计算 P(d1,d2,..,dnh+) 呢？
我们将 P(d1,d2,..,dnh+) 扩展为： P(d1h+) * P(d2d1, h+) * P(d3d2,d1, h+) * .. 。熟悉这个式子吗？这里我们会使用一个更激进的假设，我们假设 di 与 di-1 是完全条件无关的，于是式子就简化为 P(d1h+) * P(d2h+) * P(d3h+) * .. 。这个就是所谓的条件独立假设，也正是朴素贝叶斯方法的朴素之处。而计算 P(d1h+) * P(d2h+) * P(d3h+) * .. 就太简单了，只要统计 di 这个单词在垃圾邮件中出现的频率即可。关于贝叶斯垃圾邮件过滤更多的内容可以参考这个条目，注意其中提到的其他资料。
一点注记：这里，为什么有这个数据稀疏问题，还是因为统计学习方法工作在浅层面， 世界上的单词就算不再变多也是非常之多的，单词之间组成的句子也是变化多端，更不用说一篇文章了，文章数目则是无穷的，所以在这个层面作统计，肯定要被数据稀疏性困扰。我们要注意，虽然句子和文章的数目是无限的，然而就拿邮件来说，如果我们只关心邮件中句子的语义（进而更高抽象层面的“意图”（语义，意图如何可计算地定义出来是一个人工智能问题），在这个层面上可能性便大大缩减了，我们关心的抽象层面越高，可能性越小。单词集合和句子的对应是多对一的，句子和语义的对应又是多对一的，语义和意图的对应还是多对一的，这是个层级体系。神经科学的发现也表明大脑的皮层大致有一种层级结构，对应着越来越抽象的各个层面，至于如何具体实现一个可放在计算机内的大脑皮层，仍然是一个未解决问题，以上只是一个原则（principle）上的认识，只有当 computational 的 cortex 模型被建立起来了之后才可能将其放入电脑。
5.2 为什么朴素贝叶斯方法令人诧异地好——一个理论解释
朴素贝叶斯方法的条件独立假设看上去很傻很天真，为什么结果却很好很强大呢？就拿一个句子来说，我们怎么能鲁莽地声称其中任意一个单词出现的概率只受到它前面的 3 个或 4 个单词的影响呢？别说 3 个，有时候一个单词的概率受到上一句话的影响都是绝对可能的。那么为什么这个假设在实际中的表现却不比决策树差呢？有人对此提出了一个理论解释，并且建立了什么时候朴素贝叶斯的效果能够等价于非朴素贝叶斯的充要条件，这个解释的核心就是：有些独立假设在各个分类之间的分布都是均匀的所以对于似然的相对大小不产生影响；即便不是如此，也有很大的可能性各个独立假设所产生的消极影响或积极影响互相抵消，最终导致结果受到的影响不大。具体的数学公式请参考这篇 paper 。
6. 层级贝叶斯模型
层级贝叶斯模型是现代贝叶斯方法的标志性建筑之一。前面讲的贝叶斯，都是在同一个事物层次上的各个因素之间进行统计推理，然而层次贝叶斯模型在哲学上更深入了一层，将这些因素背后的因素（原因的原因，原因的原因，以此类推）囊括进来。一个教科书例子是：如果你手头有 N 枚硬币，它们是同一个工厂铸出来的，你把每一枚硬币掷出一个结果，然后基于这 N 个结果对这 N 个硬币的 θ （出现正面的比例）进行推理。如果根据最大似然，每个硬币的 θ 不是 1 就是 0 （这个前面提到过的），然而我们又知道每个硬币的 p(θ) 是有一个先验概率的，也许是一个 beta 分布。也就是说，每个硬币的实际投掷结果 Xi 服从以 θ 为中心的正态分布，而 θ 又服从另一个以 Ψ 为中心的 beta 分布。层层因果关系就体现出来了。进而 Ψ 还可能依赖于因果链上更上层的因素，以此类推。
6.1 隐马可夫模型（HMM）
吴军在数学之美系列里面介绍的隐马可夫模型（HMM）就是一个简单的层级贝叶斯模型：
那么怎么根据接收到的信息来推测说话者想表达的意思呢？我们可以利用叫做“隐含马尔可夫模型”（Hidden Markov Model）来解决这些问题。以语音识别为例，当我们观测到语音信号 o1,o2,o3 时，我们要根据这组信号推测出发送的句子 s1,s2,s3。显然，我们应该在所有可能的句子中找最有可能性的一个。用数学语言来描述，就是在已知 o1,o2,o3,...的情况下，求使得条件概率 P (s1,s2,s3,...o1,o2,o3....) 达到最大值的那个句子 s1,s2,s3,...
吴军的文章中这里省掉没说的是，s1, s2, s3, .. 这个句子的生成概率同时又取决于一组参数，这组参数决定了 s1, s2, s3, .. 这个马可夫链的先验生成概率。如果我们将这组参数记为 λ ，我们实际上要求的是：P(SO, λ) （其中 O 表示 o1,o2,o3,.. ，S表示 s1,s2,s3,..）
当然，上面的概率不容易直接求出，于是我们可以间接地计算它。利用贝叶斯公式并且省掉一个常数项，可以把上述公式等价变换成
P(o1,o2,o3,...s1,s2,s3....) * P(s1,s2,s3,...)
其中
P(o1,o2,o3,...s1,s2,s3....) 表示某句话 s1,s2,s3...被读成 o1,o2,o3,...的可能性, 而 P(s1,s2,s3,...) 表示字串 s1,s2,s3,...本身能够成为一个合乎情理的句子的可能性，所以这个公式的意义是用发送信号为 s1,s2,s3...这个数列的可能性乘以 s1,s2,s3.. 本身可以一个句子的可能性，得出概率。
这里，s1,s2,s3...本身可以一个句子的可能性其实就取决于参数 λ ，也就是语言模型。所以简而言之就是发出的语音信号取决于背后实际想发出的句子，而背后实际想发出的句子本身的独立先验概率又取决于语言模型。
7. 贝叶斯网络
吴军已经对贝叶斯网络作了科普，请直接跳转到这里。更详细的理论参考所有机器学习的书上都有。
参考资料：
一堆机器学习，一堆概率统计，一堆 Google ，和一堆 Wikipedia 条目，一堆 paper 。
2008年10月17日星期五
第七届全国搜索引擎和网上信息挖掘学术研讨会征文通知
第七届全国搜索引擎和网上信息挖掘学术研讨会征文通知
2009年5月22-24日, 大连 The 7th National Symposium of Search Engine and Web Mining(May 22-24, 2009, DaLian)
第七届全国搜索引擎和网上信息挖掘学术研讨会（SEWM2009）由中国计算机学会主办，大连理工大学承办。该系列会议每年举行一次，现已成为国内海量网络信息处理与应用领域最主要的学术活动之一。此次会议将为网络信息搜索与挖掘领域的学者交流最新研究成果、进行广泛的学术讨论提供便利，并且将邀请国内该领域的著名学者做精彩报告，同时将保持SEWM会议的传统，组织搜索和挖掘相关技术的评测。
征稿范围（征求但不限于如下主题）
信息检索模型、算法及基础理论
面向行业的信息检索
跨语言和多语言信息检索、面向信息检索的机器翻译技术
交互式检索、用户界面和可视化、用户模型及分析、基于任务的信息检索
智能问题回答系统
文本分类、文本聚类及相关的机器学习方法
数据挖掘、文本挖掘信息过滤与信息抽取
语义网络与本体
文本倾向性分析、意见挖掘及舆情监控
网络信息检索的建模、实现和应用及搜索引擎设计
信息检索中的机器学习
生物信息学
语音、图像处理与理解
自然语言理解在信息检索中的应用
投稿要求
论文必须未公开发表过，一般不超过6000字；中、英文稿均可接受； 论文应包括题目、作者姓名、作者单位、摘要、关键字、正文和参考文献；另附作者地址、邮编、电话或传真及E-mail地址； 参选优秀学生论文的稿件请注明（须由在校博士生、硕士生或本科生）为第一作者； 会议采用电子投稿，请将Word或PDF格式的文件发到：sewm2009@dlut.edu.cn (超过2M的文件请先压缩；请注意接收会议组织机构发出的收稿确认电子邮件) 会议咨询：杨志豪（0411-84706009-3926），林鸿飞（0411-84706550）
会议联系Email：sewm2009@dlut.edu.cn
会议网站: http://sewm2009.dlut.edu.cn/
论文出版 会议录用论文将被推荐到《Journal of Computational Information Systems》正刊(英文稿件，全部EI检索)、《计算机研究与发展》正刊、《模式识别与人工智能》正刊、《小型微型计算机系统》正刊、《计算机工程与应用》正刊、《广西师范大学学报》正刊、《郑州大学学报》正刊等期刊上发表。会议还将评出优秀学生论文，颁发证书并给予奖励。
重要日期
投稿截止：2008年11月1日
录用通知：2008年12月1日
修改定稿：2008年12月15日
2008年10月15日星期三
送给那些大工单身贵族的箴言[转载]
这是一个老贴了，经典，再拿出来晒晒……（此帖转自考研论坛）爸教育我说：“中国的男女比例是118:100，如果不好好读书，你就是那个‘18’！” 于是我学习，长大了，我考上了大工，发现大工的男女比例是4:1，我是那个‘3’！ 一入大工深似海，世界极小极小， 大工极大极大，女生极少极少， 男生极好极好， 此地“和尚拈花望月，恐龙坐地成仙。” 此地“美女如云，恐龙如星，抬眼望，朗朗夜空，万里无云，满天繁星。” 大工自古无娇娘，残花败柳一行行。 自古红颜多薄命，大工女生万万岁。 看背影，急煞千军万马；猛回头，喝退各路诸侯。 如果说美女是青草，那么大工寸草不生；如果说美女是白云，那么大工万里无云。 来到这里，我就后悔没有早恋，但是现在已经晚了，每次见到比我小的那些莘莘学子们在十年的寒窗里面苦读， 我就想告诉他们，用发自肺腑惊天地泣鬼神的声音：“千万不要考大工，就算要考也要先早恋。。。” 如果你爱她，送她去大工，因为那里是女生的天堂； 如果你恨他，送他去大工，因为那里是男生的地狱。。。 每个大工女生都曾是无泪的天使， 当遇到自己喜欢的男孩时，便会流泪——于是变为凡人。 所以大工男生一定不敢辜负大工女生，因为女生为他放弃了整个天堂！ 每个大工男生都曾是地狱的恶魔， 当遇到自己喜欢的女孩时，便会动心——于是变为凡人。 但是绝大多数女生一定会辜负那男生， 于是大工男生又要回到那可怕的地狱！ 用市场经济学的角度思考，供求关系导致价格变化， 因为女生资源的短缺造成了女生的卖方市场，价格居高不下， 一路牛市，不见熊市， 而很多客观因素所导致的“女生地方保护主义“严重阻碍了市场的自动调节功能， 长此以往，恶性循环， 这对于货真价实的大工男生来说是非常不公平的， 我们要打破帝国主义的“剪刀差”， 我们要消灭爱情剥削， 我们要夺回剩余感情，寻找平等的快乐，实现共同幸福， 很多很多实例（帅哥配恐龙）成为了习惯， 很多很多习惯（重女轻男）成了文化， 很多很多文化（女尊男悲）成了酱缸， 很多很多酱缸使更多更多的大工男生一步一步深陷其中， 越是挣扎得厉害溺死得越快， 最后在整个大学四年， 就算是起的比鸡早，吃的比猪差，干的比驴还多， 也还不一定能够找到女朋友。。。 大工于是就成为了一潭死水，由男生们那些可怜的青春酿成的死水， 于是大工男生对女友的要求，就只剩了两点：女的，活的， 我们要跳出酱缸， 我们要打破美女的学校保护主义， 我们要追求爱情的自由和平等， 我们不要用血泪来酝酿那苦苦的死水， 我们要把春波荡漾出去，把春意从围墙之外迎进来， 也许你说四个男生中还有那么一个幸运儿啊， 可是事实是如此的无情， 有时候不识庐山真面目，只缘没有进入“大工女生的男朋友”这样一座围城， 里面的人痛苦地并不比外面的人少， 为那些不可爱的女生， 端茶送水，铺床叠被，前仆后继，夜以继日，披星戴月，奋不顾身，以不变应万变，万变不离其宗， 全心全意为女朋友服务， 还要花很多心思构建TMD预防系统， 防止那剩下的三个男生，甚至是三十个对她痴心不死，欲罢不能，垂涎欲滴，癞蛤蟆想吃恐龙肉， 更加担心女朋友变心， 担心女朋友花心， 担心女朋友分心， 担心女朋友。。。。。 何不放弃这些食之无味的鸡肋呢？ 放弃她们并不可惜啊， 放弃了一棵吸血的魔树我们得到的是一片油绿的森林， 天涯何处无芳草， 百步之类必有芳草， 好马不吃回头草， 兔子不吃窝边草， 我们要当野草让失恋的烈火烧掉我们的叶子吧， 泥土之下的根茎将会在下一个春天发出更多的叶子， 有个浪漫的传说：“每个人都是单翼的天使，唯有彼此拥抱才能展翅飞翔。” 据说我们来到这个世上就是为了寻找另一半的 ，我千辛万苦在大工寻觅着， 可是，我们的翅膀居然都是一顺边的！！ 仅有的那几个顺另外一边的女生都被高年级的、其他学校的、她高中的、她以前认识的。。。。 抱着远走高飞了，飞了。。。 也许在茫茫的人海中偶尔也有翅膀长另外一边的幸存者， 可是就算你们相抱了你们也飞不起来，你抱不动她， 昔日的爱情，已被格式化； 现在的爱情，该页无法显示或暂时不可用； 将来的爱情，内存严重不足，请关闭部分程序后重试。。。 但是生活必须继续下去， 于是我们就开始嘻笑怒骂对我们的可悲进行调侃， 我爱的人明花有主， 爱我的惨不忍睹， 不在寂寞中恋爱， 就在寂寞中变态！ 两女： A：听说你男朋友是大工的？B：唉，我哪有这么好的福气。。。 两男： C： 听说你女朋友是大工的？D：放屁！你女朋友才是大工的呢！ 上课时听见，后排两个男生： A：“我诅咒你以后的女朋友是咱大工的！” B：“我诅咒你以后的女朋友是咱们班的！” 曹操：“快快打探，我方还剩多少人马？” 蒋干：“只剩大工学生那么多了！” 曹操：“哈哈，天无绝人之路啊，我们尚可一战，再去打探！” 蒋干：“哎呀，主公不好，我方人马只剩大工女生那么多了！” 曹操（跌坐）：“天亡我也，看来只能速速北归了，快快再去打探！” 蒋干（一会，干回来伏曹身上痛哭）：“5555。。。。” 曹操：“如何？” 蒋干（哽咽）：“主公，我方兵马只剩大工美女那么多了！” 曹操（仰天长叹，痛不欲生）：“嗨，这样说来，我方已全军覆没了。。。” 渐渐地我们读书： 一个头两个大熬三更背四书五颜六色七荤八素九成不懂十分郁闷！ 只好： 找点十间喝九泡八七茶六鸟五湖四海神游解闷三天两头奢侈一顿！ 人呐： 一辈子两意三心四体不勤五谷不分六艺不精苦苦七待那八九十分！ 可笑： 这十方九洲八荒七荻六合五行四野三光两界中你我渺渺一点痴心！ 开始我只是喜欢上大工这个尤物，后来我就爱上了考研这门艺术； 开始我只是喜欢上学习这个尤物，后来我就爱上了考试这门艺术； 开始我只是喜欢上 QQ 这个尤物，后来我就爱上了聊天这门艺术； 开始我只是喜欢上 MM 这个尤物，后来我就爱上了失恋这门艺术。 我们的口号是，只抢大工的馒头，不碰大工的女生！ 我们是多么需要一个女生在我们身边， 要不然这样的大学将是无聊的遗憾的可悲的可怜的， 我不禁仰天长啸，难道我就这样过我的大学四年？ 天亮啦，早读啦，读完了， 上课啦，下课啦， 放学啦，熄灯啦， 失眠啦， 天又亮啦，无聊啦，遇见啦，爱上啦，追求啦，失败啦， 再爱上，再追求啦，失恋啦， 堕落啦,，游戏啦，CS啦， 上网啦，考试啦，复习啦， 通宵啦，放假啦，开学啦， 毕业啦，混够啦，老啦， 后悔啦我不愿意这样，也不能这样， 我要跳出这个怪圈， 我要飞出这个酱缸， 哪怕只有一只翅膀， 我要去别的地方寻找我的另外一半， 那就是， 东财，海事，师范，大外。。。。 甚至是技院， 只有走出去才是我们的希望， 我们的上帝耶稣， 我们的真主阿拉， 我们的佛主如来， 我们的毛主席， 我们的大救星， 坚信大工男生是可爱的一群人， 是一群值得大连各大高校美女爱的男生， 成为我们女朋友之后她们一定会很快乐很幸福， 我们要高举“普遍撒网，重点培养”的思想，贯彻“一个中心，两个基本点”：以寻找到女朋友为中心， 基本选择美女，基本适合条件， 还要认真学习三个代表思想：代表最先进的寻找女朋友的方，,代表最合适的选择要求，代表最广大的女朋友入选范围。与时俱进，要走群众路线，团结一切可以团结的力量，建立一个最广大的统一战线。还要虚心听取同学们的意见，走美女与恐龙相结合的道路。 认真执行立志寻觅女朋友时的“十三个不要”： 1，恐龙的不要； 2，有男朋友的不要； 3，行为过于开放的不要； 4，低于1.55CM的不要； 5，不是学生的不要； 6，是大工的不要； 7，读了研的不要； 8，1988年以后的不要； 9，1984年以前的不要； 10，有残疾的不要； 11，酷爱打扮花钱夸张的不要； 12，不温柔的不要； 13，男人的不要！ 对单身妹妹，要始终争取；对有夫之妇，从未放弃； 对十八岁以上女孩，注意发掘；对小于十八的，要有战略性眼光。 我们喜欢的女孩最好像黛玉一样有才气，像宝钗一样懂事，像可卿一样漂亮，像湘云一样豪爽， 像李纨一样忠贞，像探春一样能干，像凤姐一样精明， 还要像元春一样有福气。 但是千千万万不要像黛玉一样弱不禁风，宝钗一样自私， 可卿一样风流薄命，湘云一样不通世务，迎春一样呆头呆脑， 惜春一样心灰意冷，妙玉一样矫柔造作，贾母一样老。 勿以不够漂亮而不联系，勿以过于漂亮而放弃。 一旦发现合适的美女就去“追”她，就以迅雷不及掩耳盗铃之势， 象狂奔的蜗牛， 名花虽有主，我来松松土， 无耻是我们的作风， 卑鄙是我们的手段， 真爱是我们的口头禅， 不谙世事的小MM是我们的盘中餐， 切记“我们是害虫，我们是害虫”， 要有“花”堪折直须折，莫待无“花”空折枝。 有觅则觅， 有美女要觅， 没有美女创造美女也要觅， 有觅不觅非君子。 要牢固树立能够找到这样的美女的信念，为伟大的告别单身事业奋斗终身。 终会有一天，红旗重新在克里姆林宫上空飘扬，《国际歌》在白宫响起，东京上空飘起美丽的蘑菇云，共产主义之光照耀全球，大工的男生们找到了他们的女朋友。。。。。
2008年10月11日星期六
Java Language Keywords (转载)
From：http://dev.csdn.net/article/81956.shtm
Java Language Keywords
Here's a list of keywords in the Java language. These words are reserved — you cannot use any of these words as names in your programs. true, false, and null are not keywords but they are reserved words, so you cannot use them as names in your programs either.
abstract continue for new switch
assert*** default goto* package synchronized
boolean do if private this
break double implements protected throw
byte else import public throws
case enum**** instanceof return transient
catch extends int short try
char final interface static void
class finally lon g strictfp** volatile
const* float native super while
* not used
** added in 1.2
*** added in 1.4
**** added in 5.0
Key: strictfp**
使用对象：类、方法
自Java2以来，Java语言增加了一个关键字strictfp，虽然这个关键字在大多数场合比较少用，但是还是有必要了解一下。
strictfp的意思是FP-strict，也就是说精确浮点的意思。在Java虚拟机进行浮点运算时，如果没有指定strictfp关键字时，Java的编译器以及运行环境在对浮点运算的表达式是采取一种近似于我行我素的行为来完成这些操作，以致于得到的结果往往无法令你满意。而一旦使用了strictfp来声明一个类、接口或者方法时，那么所声明的范围内Java的编译器以及运行环境会完全依照浮点规范IEEE-754来执行。因此如果你想让你的浮点运算更加精确，而且不会因为不同的硬件平台所执行的结果不一致的话，那就请用关键字strictfp。
你可以将一个类、接口以及方法声明为strictfp，但是不允许对接口中的方法以及构造函数声明strictfp关键字，例如下面的代码：
1. 合法的使用关键字strictfp
strictfp interface A {}
public strictfp class FpDemo1 {
strictfp void f() {}
}
2. 错误的使用方法
interface A {
strictfp void f();
}
public class FpDemo2 {
strictfp FpDemo2() {}
}
一旦使用了关键字strictfp来声明某个类、接口或者方法时，那么在这个关键字所声明的范围内所有浮点运算都是精确的，符合IEEE-754规范的。例如一个类被声明为strictfp，那么该类中所有的方法都是strictfp的。
Keys: volatile
使用对象：字段介绍：因为异步线程可以访问字段，所以有些优化操作是一定不能作用在字段上的。volatile有时可以代替synchronized。
Keys：transient
使用对象：字段
介绍：字段不是对象持久状态的一部分，不应该把字段和对象一起串起。
Java Language Keywords
Here's a list of keywords in the Java language. These words are reserved — you cannot use any of these words as names in your programs. true, false, and null are not keywords but they are reserved words, so you cannot use them as names in your programs either.
abstract continue for new switch
assert*** default goto* package synchronized
boolean do if private this
break double implements protected throw
byte else import public throws
case enum**** instanceof return transient
catch extends int short try
char final interface static void
class finally lon g strictfp** volatile
const* float native super while
* not used
** added in 1.2
*** added in 1.4
**** added in 5.0
Key: strictfp**
使用对象：类、方法
自Java2以来，Java语言增加了一个关键字strictfp，虽然这个关键字在大多数场合比较少用，但是还是有必要了解一下。
strictfp的意思是FP-strict，也就是说精确浮点的意思。在Java虚拟机进行浮点运算时，如果没有指定strictfp关键字时，Java的编译器以及运行环境在对浮点运算的表达式是采取一种近似于我行我素的行为来完成这些操作，以致于得到的结果往往无法令你满意。而一旦使用了strictfp来声明一个类、接口或者方法时，那么所声明的范围内Java的编译器以及运行环境会完全依照浮点规范IEEE-754来执行。因此如果你想让你的浮点运算更加精确，而且不会因为不同的硬件平台所执行的结果不一致的话，那就请用关键字strictfp。
你可以将一个类、接口以及方法声明为strictfp，但是不允许对接口中的方法以及构造函数声明strictfp关键字，例如下面的代码：
1. 合法的使用关键字strictfp
strictfp interface A {}
public strictfp class FpDemo1 {
strictfp void f() {}
}
2. 错误的使用方法
interface A {
strictfp void f();
}
public class FpDemo2 {
strictfp FpDemo2() {}
}
一旦使用了关键字strictfp来声明某个类、接口或者方法时，那么在这个关键字所声明的范围内所有浮点运算都是精确的，符合IEEE-754规范的。例如一个类被声明为strictfp，那么该类中所有的方法都是strictfp的。
Keys: volatile
使用对象：字段介绍：因为异步线程可以访问字段，所以有些优化操作是一定不能作用在字段上的。volatile有时可以代替synchronized。
Keys：transient
使用对象：字段
介绍：字段不是对象持久状态的一部分，不应该把字段和对象一起串起。
2008年9月29日星期一
Autoregressive Model
A model which depends only on the previous outputs of the system is called an autoregressive model (AR), while a model which depends only on the inputs to the system is called a moving average model (MA), and of course a model based on both inputs and outputs is an autoregressive-moving-average model (ARMA). Note that by definition, the AR model has only poles while the MA model has only zeros.
2008年9月26日星期五
好公司：让员工站在公司的肩膀上（转载）
转载自：http://bschool.hexun.com/2008-09-25/109248161.html
一个好的公司，不能是做加法的公司。不是说1个人可以产生1块钱，10个人可以产生10块钱的公司。好的公司一定是做乘法的公司。好的公司，尤其是非常成功，并且长久成功的公司，一定是在基础机构上面投资最多的公司；一个好的公司，一定要让员工站在自己的肩膀上。
一天中午，从MountView过来的Google做PageRank算法的朋友阳萌，和大家一起去吃水饺。在吃饭期间，我们不可避免地聊起了Google，当然还有微软。
基础设施
Google和微软，从大的角度来说，他们很像：他们都是软件公司。但软件公司多了，Oracle也是软件公司，Adobe也是，Netscape也是，还有很多很多的软件公司。但Google和微软和他们又都不一样，显得很另类。从行业来说，微软主营的是操作系统和办公套件，Google专注互联网上的搜索，看似行业不一样，但他们在不同的行业又有一点相同。
这一点相同的地方，就是他们都是平台提供商。
平台这个被滥用的词，挺难准确地表达我想表达的意思。我要说的就是，就是他们都希望做好东西，让别人在自己的基础上做开发，而不仅仅满足于别人用自己的应用程序本身。做为公司，它们是这样对待外部的用户和合作伙伴的，但更重要的是，他们也是这样对待自己的员工的。
比如说Windows，首先要说，它是个不错的应用程序，否则也就没有它做平台的份儿了。但它真正的成功是让开发者在上面开发应用。如果我们看到微软内部，各个部门互相提供大量的编程接口，这成就了微软内部的很多的创新。在微软内部，大家都争着为其他部门提供更好的“编程接口”好让他们用自己的服务。也就是说，在微软公司里面，自己可以在其上开发的“平台”很多，所以可以做出更好的东西。
Google的搜索当然不错，但在它的背后，也是一个大的平台，让Google的工程师可以更高效地开发程序。比如GFS（Google File System），就提供了便宜的、巨大的、高容错的、高性能的存储。这样的平台，估计现在全球范围内不多。还有Mapreduce，这个让一个程序并发地跑在数万台电脑上的程序框架，让一个刚刚加入公司的程序员就可以操纵数万台电脑，一晚上处理到几个TB的数据；再比如说Bigtable这样的东东。
这些东西，借用阳萌的话说，其实是一个公司提供给员工的基础设施。
放大个人的力量
在微软和在Google工作的人，或许和在很多的成功的大公司里的人一样，都有种交织在一起的幸运感和失落感，至少我是有的。让你觉得幸运的是，这个环境是如此的完美，干什么都有很多的工具，很多的知识库，还有很多团队在支持者自己。其中分工是如此之细，每个分工上都有最专业的人用最高效的方式提供支持。
比如在微软，最喜欢的一个内部网站就是http://toolkit，各种各样的内部的小工具，全是微软平台上的，工程师为自己解决自己的问题写的。如果要建个新的邮件地址，随便谁都可以马上在autogroup里面申请一个abc@microsoft.com这样的邮件，三分钟不要，就可以发布到互联网上去，接收邮件了。要解决问题，近百万篇知识库文章，找什么有什么。想学东西，内部的培训资料看也看不完。就算找人，各种牛人一把一把的让你问。总之，很多人都会觉得，在这个公司做一个工程师真幸福。
但失落感也同时在于此。优秀的公司是个系统，在系统里面，每个人都很伟大。离开了系统，离开了支持，自己头上的光环就立刻消失，才发现干什么都很难，因为没有现成的东西支持着自己。所谓橘生淮南则为橘，橘生淮北而为枳。有自知之明的人应该知道，自己只是那一株橘子，而真正伟大的是土壤。
阳萌也有类似的感慨。Google内部的好资源太多，外面有的，Linux阵营有的，Google内部都会自己实现一遍，让自己觉得这里什么都有。建立在这些平台上面可以做出来的东西，比自己不用这些资源的产出大不止百倍。这感觉就好像用汇编语言也能写东西，用Windows下的VB也能写东西，但是有了好的平台和工具，画同样一个窗口花的时间是完全不同的。
这也就证明了Windows+VB是比芯片+汇编好得多的平台。但问题就在于，所有这些好东西，根本没有办法拿出来用。
做加法还是做乘法的公司
一个好的公司，不能是做加法的公司。不是说1个人可以产生1块钱，10个人可以产生10块钱的公司。
好的公司一定是做乘法的公司。4个人可以产生4块钱，5个人应该就可产生8块钱。这个乘法的基础，就是大家都在做基础设施，自己站在别人的肩膀上，也让别人站在自己的肩膀上。
但很显然，微软和Google支持员工的基础设施还是有很明显的区别的。
微软更多的还是在包装好的软件的层面。这和微软过去30多年的积累有关。比如微软里的一个工具，可以方便地做出单机或者局域网环境的好的系统——微软工具的快速开发是被业界称道的，但是它没有办法把自己的数据中心向员工开放。因为，从本质上来说，微软不是一个围绕着数据中心起家的公司，微软的数据中心的成本，也不足以支撑这个体系。毕竟，在微软诞生的年月里，现在规模的数据中心的概念还无法想象。
而Google更多的是在于服务上面。Google从第一天就是建在数据中心基础上的公司，他的基础设施显然也是对于所有的员工开放的。一个普通的工程师获取的支持，不是一段代码，而是跑着一个服务的上万台电脑。有种说法，Google已经成为世界头几大的PC制造商了，只不过他们的PC都是自己用，而不销售而已。
如果从这个角度上来说，微软的支持是一节电池，一个发动机，可以组装成一个个玩具车；而Google的支持更像一个交流电网，一个电话系统，可以做出基于这些网络的应用。而没有这些模块支持的人，好似在森林里赤手空拳的找到了一根木棍。
所以微软依然会在他擅长的软件领域取得巨大的成功，无论是安装在桌子里的电脑，放在硬件设备上的软件。而Google则会在围绕互联网数据中心的领域取得成功。这些，都是可在公司的DNA里面的。
给我们的启示
无论是程序还是公司，架构很重要，就是如何把人员和资源搭成梯子，文化上有让别人更伟大的导向，让一个刚刚进公司的人，可以迅速的做到比他进入其他公司的同龄人获得更多的支持，这才是一个公司的结构上的成功。
好的公司，尤其是非常成功，并且长久成功的公司，一定是在基础机构上面投资最多的公司；一个好的公司，一定要让员工站在自己的肩膀上。
一个好的公司，不能是做加法的公司。不是说1个人可以产生1块钱，10个人可以产生10块钱的公司。好的公司一定是做乘法的公司。好的公司，尤其是非常成功，并且长久成功的公司，一定是在基础机构上面投资最多的公司；一个好的公司，一定要让员工站在自己的肩膀上。
一天中午，从MountView过来的Google做PageRank算法的朋友阳萌，和大家一起去吃水饺。在吃饭期间，我们不可避免地聊起了Google，当然还有微软。
基础设施
Google和微软，从大的角度来说，他们很像：他们都是软件公司。但软件公司多了，Oracle也是软件公司，Adobe也是，Netscape也是，还有很多很多的软件公司。但Google和微软和他们又都不一样，显得很另类。从行业来说，微软主营的是操作系统和办公套件，Google专注互联网上的搜索，看似行业不一样，但他们在不同的行业又有一点相同。
这一点相同的地方，就是他们都是平台提供商。
平台这个被滥用的词，挺难准确地表达我想表达的意思。我要说的就是，就是他们都希望做好东西，让别人在自己的基础上做开发，而不仅仅满足于别人用自己的应用程序本身。做为公司，它们是这样对待外部的用户和合作伙伴的，但更重要的是，他们也是这样对待自己的员工的。
比如说Windows，首先要说，它是个不错的应用程序，否则也就没有它做平台的份儿了。但它真正的成功是让开发者在上面开发应用。如果我们看到微软内部，各个部门互相提供大量的编程接口，这成就了微软内部的很多的创新。在微软内部，大家都争着为其他部门提供更好的“编程接口”好让他们用自己的服务。也就是说，在微软公司里面，自己可以在其上开发的“平台”很多，所以可以做出更好的东西。
Google的搜索当然不错，但在它的背后，也是一个大的平台，让Google的工程师可以更高效地开发程序。比如GFS（Google File System），就提供了便宜的、巨大的、高容错的、高性能的存储。这样的平台，估计现在全球范围内不多。还有Mapreduce，这个让一个程序并发地跑在数万台电脑上的程序框架，让一个刚刚加入公司的程序员就可以操纵数万台电脑，一晚上处理到几个TB的数据；再比如说Bigtable这样的东东。
这些东西，借用阳萌的话说，其实是一个公司提供给员工的基础设施。
放大个人的力量
在微软和在Google工作的人，或许和在很多的成功的大公司里的人一样，都有种交织在一起的幸运感和失落感，至少我是有的。让你觉得幸运的是，这个环境是如此的完美，干什么都有很多的工具，很多的知识库，还有很多团队在支持者自己。其中分工是如此之细，每个分工上都有最专业的人用最高效的方式提供支持。
比如在微软，最喜欢的一个内部网站就是http://toolkit，各种各样的内部的小工具，全是微软平台上的，工程师为自己解决自己的问题写的。如果要建个新的邮件地址，随便谁都可以马上在autogroup里面申请一个abc@microsoft.com这样的邮件，三分钟不要，就可以发布到互联网上去，接收邮件了。要解决问题，近百万篇知识库文章，找什么有什么。想学东西，内部的培训资料看也看不完。就算找人，各种牛人一把一把的让你问。总之，很多人都会觉得，在这个公司做一个工程师真幸福。
但失落感也同时在于此。优秀的公司是个系统，在系统里面，每个人都很伟大。离开了系统，离开了支持，自己头上的光环就立刻消失，才发现干什么都很难，因为没有现成的东西支持着自己。所谓橘生淮南则为橘，橘生淮北而为枳。有自知之明的人应该知道，自己只是那一株橘子，而真正伟大的是土壤。
阳萌也有类似的感慨。Google内部的好资源太多，外面有的，Linux阵营有的，Google内部都会自己实现一遍，让自己觉得这里什么都有。建立在这些平台上面可以做出来的东西，比自己不用这些资源的产出大不止百倍。这感觉就好像用汇编语言也能写东西，用Windows下的VB也能写东西，但是有了好的平台和工具，画同样一个窗口花的时间是完全不同的。
这也就证明了Windows+VB是比芯片+汇编好得多的平台。但问题就在于，所有这些好东西，根本没有办法拿出来用。
做加法还是做乘法的公司
一个好的公司，不能是做加法的公司。不是说1个人可以产生1块钱，10个人可以产生10块钱的公司。
好的公司一定是做乘法的公司。4个人可以产生4块钱，5个人应该就可产生8块钱。这个乘法的基础，就是大家都在做基础设施，自己站在别人的肩膀上，也让别人站在自己的肩膀上。
但很显然，微软和Google支持员工的基础设施还是有很明显的区别的。
微软更多的还是在包装好的软件的层面。这和微软过去30多年的积累有关。比如微软里的一个工具，可以方便地做出单机或者局域网环境的好的系统——微软工具的快速开发是被业界称道的，但是它没有办法把自己的数据中心向员工开放。因为，从本质上来说，微软不是一个围绕着数据中心起家的公司，微软的数据中心的成本，也不足以支撑这个体系。毕竟，在微软诞生的年月里，现在规模的数据中心的概念还无法想象。
而Google更多的是在于服务上面。Google从第一天就是建在数据中心基础上的公司，他的基础设施显然也是对于所有的员工开放的。一个普通的工程师获取的支持，不是一段代码，而是跑着一个服务的上万台电脑。有种说法，Google已经成为世界头几大的PC制造商了，只不过他们的PC都是自己用，而不销售而已。
如果从这个角度上来说，微软的支持是一节电池，一个发动机，可以组装成一个个玩具车；而Google的支持更像一个交流电网，一个电话系统，可以做出基于这些网络的应用。而没有这些模块支持的人，好似在森林里赤手空拳的找到了一根木棍。
所以微软依然会在他擅长的软件领域取得巨大的成功，无论是安装在桌子里的电脑，放在硬件设备上的软件。而Google则会在围绕互联网数据中心的领域取得成功。这些，都是可在公司的DNA里面的。
给我们的启示
无论是程序还是公司，架构很重要，就是如何把人员和资源搭成梯子，文化上有让别人更伟大的导向，让一个刚刚进公司的人，可以迅速的做到比他进入其他公司的同龄人获得更多的支持，这才是一个公司的结构上的成功。
好的公司，尤其是非常成功，并且长久成功的公司，一定是在基础机构上面投资最多的公司；一个好的公司，一定要让员工站在自己的肩膀上。
2008年9月20日星期六
IR、NLP领域相关会议
生物：BioCreative， TREC Genomics Track
自然语言：ACL，CoNLL，NAACL
机器学习：ICML，NIPS，COLT，ECML
数据挖掘：ICDM，KDD， SIGKDD， PAKDD
信息检索：SIGIR， AIRS
人工智能：IJCAI， AAAI，CIKM
Web技术：WWW
自然语言：ACL，CoNLL，NAACL
机器学习：ICML，NIPS，COLT，ECML
数据挖掘：ICDM，KDD， SIGKDD， PAKDD
信息检索：SIGIR， AIRS
人工智能：IJCAI， AAAI，CIKM
Web技术：WWW
2008年9月19日星期五
2008年9月14日星期日
Search Engine Group VS 863 Plan
过几天师兄就要出国了，以后组内的事情就由我负责了，感觉好有压力啊。
这个学期863项目就要结题了，可到目前为止，系统还没有做完，Paper还没写呢。。。
这段时间忙着做实验，但愿实验过程一切顺利，早日把Paper写出来，才有精力完善系统啊
Faith！！！
这个学期863项目就要结题了，可到目前为止，系统还没有做完，Paper还没写呢。。。
这段时间忙着做实验，但愿实验过程一切顺利，早日把Paper写出来，才有精力完善系统啊
Faith！！！
2008年9月11日星期四
2008年8月31日星期日
Part of Speech Taggers
Freely downloadable
Stanford POS tagger
Loglinear tagger in Java (by Kristina Toutanova)
MBT: Memory-based Tagger
Based on TiMBL
TreeTagger
A decision tree based tagger from the University of Stuttgart (Helmut Scmid). It's language independent, but comes complete with parameter files for English, German, Italian, Dutch, French, Old French, Spanish, Bulgarian, and Russian. (Linux, Sparc-Solaris, Windows, and Mac OS X versions. Binary distribution only.) Page has links to sites where you can run it online.
SVMTool
POS Tagger based on SVMs (uses SVMlight). LGPL.
ACOPOST (formerly ICOPOST)
Open source C taggers originally written by by Ingo Schröder. Implements maximum entropy, HMM trigram, and transformation-based learning. C source available under GNU public license.
MXPOST: Adwait Ratnaparkhi's Maximum Entropy part of speech tagger
Java POS tagger. A sentence boundary detector (MXTERMINATOR) is also included. Original version was only JDK1.1; later version worked with JDK1.3+. Class files, not source.
fnTBL
A fast and flexible implementation of Transformation-Based Learning in C++. Includes a POS tagger, but also NP chunking and general chunking models.
mu-TBL
An implementation of a Transformation-based Learner (a la Brill), usable for POS tagging and other things by Torbjörn Lager. Web demo also available. Prolog.
YamCha
SVM-based NP-chunker, also usable for POS tagging, NER, etc. C/C++ open source. Won CoNLL 2000 shared task. (Less automatic than a specialized POS tagger for an end user.)
QTAG Part of speech tagger
An HMM-based Java POS tagger from Birmingham U. (Oliver Mason). English and German parameter files. [Java class files, not source.]
The TOSCA/LOB tagger.
Currently available for MS-DOS only. But the decision to make this famous system available is very interesting from an historical perspective, and for software sharing in academia more generally. LOB tag set.
Brill's Transformation-based learning Tagger
A symbolic tagger, written in C.
Original Xerox Tagger
A common lisp HMM tagger available by ftp.
Lingua-EN-Tagger
Perl POS tagger by Maciej Ceglowski and Aaron Coburn. Version 0.11. (A bigram HMM tagger.)
Free, but require registration
TATOO
The ISSCO tagger. HMM tagger. Need to register to download.
PoSTech Korean morphological analyzer and tagger
Online registration.
TnT - A Statistical Part-of-Speech Tagger
Trainable for various languages, comes with English and German pre-compiled models. Runs on Solaris and Linux.
Usable by email or on the web, but not distributed freely
Memory-based tagger
From ILK group, Catholic University Brabant (Jakub Zavrel/Walter Daelemans). Does Dutch, English, Spanish, Swedish, Slovene. Other MBL demos are also available.
Birmingham tagger
Accepts only plain ASCII email message contents. The tagset used is similar to the Brown/LOB/Penn set.
CLAWS tagger
The UCREL CLAWS tagger is available for trial use on the web. (It's limited to 300 words though -- this site is more of an advertisement for licensing the real thing -- available as software for Suns or as a paid service.) You can also find info on CLAWS tagsets, though that page doesn't seem to link to the C7 tagset.
The AMALGAM tagger
The AMALGAM Project also has various other useful resources, in particular a web guide to different tag sets in common use. The tagging is actually done by a (retrained) version of the Brill tagger (q.v.).
Xerox XRCE MLTT Part Of Speech Taggers
Tags any of 14 languages (European and Arabic), online on the web.
Portuguese taggers on the web: Projecto Natura and a QTAG adaptation.
Not free
Lingsoft
Lingsoft in Finland has (symbolic) analysis tools for many European languages. More information can be obtained by emailing info@lingsoft.fi. There is an online demo.
Conexor
Conexor in Finland has demonstrations of EngCG-style taggers and parsers, for English, Swedish, and Spanish.
Xerox
Xerox has morphological analyzers and taggers for many languages. There are demos of some of their tools on the web. More information can be obtained by contacting Daniella Russo.
Infogistics
Infogistics, an Edinburgh spinoff has a tagging and NP/Verb group chunker available commercially, including an evaluation version.
No longer available
LT POS and LT TTT
The Edinburgh Language Technology Group tagger and text tokenizer (and sentence splitter were binary-only Solaris tools which no longer seem to be available.
Stanford POS tagger
Loglinear tagger in Java (by Kristina Toutanova)
MBT: Memory-based Tagger
Based on TiMBL
TreeTagger
A decision tree based tagger from the University of Stuttgart (Helmut Scmid). It's language independent, but comes complete with parameter files for English, German, Italian, Dutch, French, Old French, Spanish, Bulgarian, and Russian. (Linux, Sparc-Solaris, Windows, and Mac OS X versions. Binary distribution only.) Page has links to sites where you can run it online.
SVMTool
POS Tagger based on SVMs (uses SVMlight). LGPL.
ACOPOST (formerly ICOPOST)
Open source C taggers originally written by by Ingo Schröder. Implements maximum entropy, HMM trigram, and transformation-based learning. C source available under GNU public license.
MXPOST: Adwait Ratnaparkhi's Maximum Entropy part of speech tagger
Java POS tagger. A sentence boundary detector (MXTERMINATOR) is also included. Original version was only JDK1.1; later version worked with JDK1.3+. Class files, not source.
fnTBL
A fast and flexible implementation of Transformation-Based Learning in C++. Includes a POS tagger, but also NP chunking and general chunking models.
mu-TBL
An implementation of a Transformation-based Learner (a la Brill), usable for POS tagging and other things by Torbjörn Lager. Web demo also available. Prolog.
YamCha
SVM-based NP-chunker, also usable for POS tagging, NER, etc. C/C++ open source. Won CoNLL 2000 shared task. (Less automatic than a specialized POS tagger for an end user.)
QTAG Part of speech tagger
An HMM-based Java POS tagger from Birmingham U. (Oliver Mason). English and German parameter files. [Java class files, not source.]
The TOSCA/LOB tagger.
Currently available for MS-DOS only. But the decision to make this famous system available is very interesting from an historical perspective, and for software sharing in academia more generally. LOB tag set.
Brill's Transformation-based learning Tagger
A symbolic tagger, written in C.
Original Xerox Tagger
A common lisp HMM tagger available by ftp.
Lingua-EN-Tagger
Perl POS tagger by Maciej Ceglowski and Aaron Coburn. Version 0.11. (A bigram HMM tagger.)
Free, but require registration
TATOO
The ISSCO tagger. HMM tagger. Need to register to download.
PoSTech Korean morphological analyzer and tagger
Online registration.
TnT - A Statistical Part-of-Speech Tagger
Trainable for various languages, comes with English and German pre-compiled models. Runs on Solaris and Linux.
Usable by email or on the web, but not distributed freely
Memory-based tagger
From ILK group, Catholic University Brabant (Jakub Zavrel/Walter Daelemans). Does Dutch, English, Spanish, Swedish, Slovene. Other MBL demos are also available.
Birmingham tagger
Accepts only plain ASCII email message contents. The tagset used is similar to the Brown/LOB/Penn set.
CLAWS tagger
The UCREL CLAWS tagger is available for trial use on the web. (It's limited to 300 words though -- this site is more of an advertisement for licensing the real thing -- available as software for Suns or as a paid service.) You can also find info on CLAWS tagsets, though that page doesn't seem to link to the C7 tagset.
The AMALGAM tagger
The AMALGAM Project also has various other useful resources, in particular a web guide to different tag sets in common use. The tagging is actually done by a (retrained) version of the Brill tagger (q.v.).
Xerox XRCE MLTT Part Of Speech Taggers
Tags any of 14 languages (European and Arabic), online on the web.
Portuguese taggers on the web: Projecto Natura and a QTAG adaptation.
Not free
Lingsoft
Lingsoft in Finland has (symbolic) analysis tools for many European languages. More information can be obtained by emailing info@lingsoft.fi. There is an online demo.
Conexor
Conexor in Finland has demonstrations of EngCG-style taggers and parsers, for English, Swedish, and Spanish.
Xerox
Xerox has morphological analyzers and taggers for many languages. There are demos of some of their tools on the web. More information can be obtained by contacting Daniella Russo.
Infogistics
Infogistics, an Edinburgh spinoff has a tagging and NP/Verb group chunker available commercially, including an evaluation version.
No longer available
LT POS and LT TTT
The Edinburgh Language Technology Group tagger and text tokenizer (and sentence splitter were binary-only Solaris tools which no longer seem to be available.
2008年7月18日星期五
Accepted papers of ACM CIKM 2006
ACM Fifteenth Conference on Information and Knowledge Management (CIKM2006)
November 6-11, 2006
http://sa1.sice.umkc.edu/cikm2006/
Sheraton Crystal City Hotel Arlington, VA 22202
Sponsored by: ACM SIGIR, and SIGWEB
*****************************************************************************
Number of submissions: 537
We accepted 15% as full papers and 10% as poster papers.
Accepted full papers: 81
Accepted poster papers: 56
Accepted Full Papers
---------------------------
Automatic Computation of Semantic Proximity Using Taxonomic Knowledge
Cai-Nicolas Ziegler
Kai Simon
Georg Lausen
Secure search in enterprise webs: tradeoffs in efficient implementation for
document level security
Peter Bailey
David Hawking
Brett Matson
Performance Thresholding in Practical Text Classification
Hinrich Schuetze
Efficient Model Selection for Regularized Linear Discriminant Analysis
Jieping Ye
Tao Xiong
Qi Li
Ravi Janardan
Jinbo Bi
Vladimir Cherkassky
Chandra Kambhamettu
Ranking Web Objects from Multiple Communities
Le Chen
Lei Zhang
Feng Jing
Ke-Feng Deng
Wei-Ying Ma
Window Join Approximation over Data Streams with Importance Semantics
Qiang Zhu
Wen Chi Hou
Adegoke Ojewole
Ranking Robustness: A Novel Framework to Predict Query Performance
Yun Zhou
W. Bruce Croft
Annotation Propagation Revisited for Key Preserving Views
Floris Geerts
Gao Cong
Wenfei Fan
Text Classification Improved through Multigram Models
Dou Shen
Improving Novelty Detection for General Topics Using Sentence Level
Information Patterns
Xiaoyan Li
An Integer Programming Approach for Frequent Itemset Hiding
Vassilios Verykios
Aris Gkoulalas-Divanis
Vector and Matrix Operations Programmed with UDFs in a Relational DBMS
Carlos Ordonez
Javier Garcia-Garcia
Exploiting Asymmetry in Hierarchical Topic Extraction
Sreenivas Gollapudi
Rina Panigrahy
3DString: A Feature String Kernel for 3D Object Classification on Voxelized
Data
Karsten Borgwardt
Johannes Aßfalg
Hans-Peter Kriegel
KDDCS: A Load-Balanced In-Network Data-Centric Storage Scheme for Sensor
Networks
Mohamed Aly
Kirk Pruhs
Panos K. Chrysanthis
Efficient Processing of Complex Similarity Queries in RDBMS through Query
Rewriting
Caetano Traina
Agma Traina
Marcos Rodrigues Vieira
Adriano Siqueira Arantes
Christos Faloutsos
Movie review mining and summarization
Li Zhuang
Feng Jing
Xiao-Yan Zhu
Lei Zhang
Capturing Community Search Expertise for Personalized Web Search using
Snippet-Indexes
Oisin Boydell
Barry Smyth
Validating Associations in Biological Databases
Francisco M Couto
Pedro M Coutinho
Mario Silva
Query Optimization using Restructured Views
Rada Chirkova
Fereidoon Sadri
Estimating Corpus Size via Queries
Ravi Kumar
Andrew Tomkins
Andrei Broder
Marcus Fontoura
Vanja Josifovski
Rajeev Motwani
Ying Xu
Rina Panigrahy
Shubha Nabar
Concept Similarity Mining without Frequency Information from Domain
Describing Taxonomies
Jong Wook Kim
K. Selcuk Candan
In Search of Meaning for Time Series Subsequence Clustering: Matching
Algorithms Based on a New Distance Measure
Dina Goldin
Ricardo Mardales
George Nagy
Distributed Spatio-Temporal Similarity Search
Demetrios Zeinalipour-Yazti
Song Lin
Dimitrios Gunopulos
Concept Frequency Distribution in Biomedical Text Summarization
Lawrence Reeve
Hyoil Han
Saya V. Nagori
Jonathan Yang
Tami Schwimmer
Ari D. Brooks
Mining Compressed Commodity Workflows From Massive RFID Data Sets
Hector Gonzalez
Jiawei Han
Xiaolei Li
Topic Evolution and Social Interactions: How Authors effect Research
Ding Zhou
Xiang Ji
Hongyuan Zha
C. Lee Giles
Improve query I/O performance by permuting and refining block request
sequences
Xiaoyu Wang
Mitch Cherniack
Mining Blog Stories Using Community-based and Temporal Clustering
Arun Qamra
Belle Tseng
Edward Chang
Concept-based Document Readability in Domain Specific Information Retrieval
Xin Yan
Dawei Song
Xue Li
Privacy Preserving Sequential Pattern Mining In Distributed Databases
Vishal Kapoor
Pascal Poncelet
Francois Trousset
M. Teisseire
Cache-Oblivious Nested-Loop Joins
Bingsheng He
Qiong Luo
A Dictionary for Approximate String Search and Longest Prefix Search
Sreenivas Gollapudi
Rina Panigrahy
Discovering and Exploiting Keyword and Attribute-Value Co-occurrences to
Improve P2P Routing Indices
Matthias Bender
Sebastian Michel
Nikos Ntarmos
Peter Triantafillou
Gerhard Weikum
Christian Zimmer
A Document-Centric Approach to Static Index Pruning in Text Retrieval
Systems
Stefan Buettcher
Charles Clarke
Effective and Efficient Classification on a Search-Engine Model
Kunal Punera
Aris Anagnostopoulos
Andrei Broder
SaLSa: Computing the Skyline without Scanning the Whole Sky
Marco Patella
Ilaria Bartolini
Paolo Ciaccia
Query Result Ranking over E-commerce Web Databases
Weifeng Su
Adaptive Non-linear Clustering in Data Streams
Ankur Jain
Zhihua Zhang
Edward Chang
Constrained Subspace Skyline Computation
Evangelos Dellis
Ilya Vladimirskiy
Bernhard Seeger
Yannis Theodoridis
Akrivi Vlachou
An Approximate Multi-Word Matching Algorithm for Robust Document Retrieval
Atsuhiro Takasu
Document Re-ranking Using Cluster Validation and Label Propagation
Lingpeng Yang
Donghong Ji
Guodong Zhou
Classification spanning correlated data streams
Rong She
Yabo Xu
Ke Wang
Jian Pei
Processing Relaxed Skylines in PDMS Using Distributed Data Summaries
Katja Hose
Christian Lemke
Kai-Uwe Sattler
Structure-Based Querying of Proteins Using Wavelets
Parthasarathy Srinivasan
Keith Marsolo
Kotagiri Ramamohanarao
A combination of trie-trees and inverted files for the indexing of
set-valued
Manolis Terrovitis
Spyros Passas
Panos Vassiliadis
Timos Sellis
Efficient Join Processing over Uncertain Data
Sarvjeet Singh
Reynold Cheng
Yuni Xia
Sunil Prabhakar
Rahul Shah
Jeffrey Vitter
Optimisation methods for ranking functions with multiple parameters
Stephen Robertson
Michael Taylor
Hugo Zaragoza
Nick Craswell
Chris Burges
On GMAP
Stephen Robertson
A Probabilistic Relevance Propagation Model for Hypertext Retrieval
Azadeh Shakery
Chengxiang Zhai
Summarizing Local Context to Personalize Global Web Search
Paul - Alexandru Chirita
Wolfgang Nejdl
Claudiu Firan
Describing Differences between Databases
Heiko Müller
Johann-Christoph Freytag
Ulf Leser
Voting for Candidates: Adapting Data Fusion Techniques for an Expert Search
Task
Craig Macdonald
Iadh Ounis
Finding Highly Correlated Pairs Efficiently with Powerful Pruning
Jian Zhang
Joan Feigenbaum
Investigating the Exhaustivity Dimension in Content-Oriented XML Element
Retrieval Evaluation
Paul Ogilvie
A Study on the Effects of Personalization and Task Information on Implicit
Feedback Performance
Ryen White
Diane Kelly
POLESTAR - Collaborative Knowledge Management and Sensemaking Tools for
Intelligence Analysts
Nicholas Pioch
John Everett
Incremental Hierarchical Clustering of Text Documents
Nachiketa Sahoo
Jamie Callan
Ramayya Krishnan
George Duncan
Rema Padman
Multi-Evidence, Multi-Criteria, Lazy Associative Document Classification
Adriano Veloso
Wagner Meira Jr.
Marco Cristo
Mohammed Zaki
Marcos Goncalves
Coupling Feature Selection and Machine Learning Methods for Navigational
Query Identification
Yumao Lu
Xin Li
Fuchun Peng
Nawaaz Ahmed
Utility Scoring of Product Reviews
Zhu Zhang
Balaji Varadarajan
Task-based Process Know-how Reuse and Proactive Information Delivery in
TaskNavigator
Oleg Rostanin
Harald Holz
Takeshi Suzuki
Kaoru Maeda
Andreas Dengel
Katsumi Kanasaki
On the Structural Properties of Massive Telecom Call Graphs: Findings and
Implications
Dipanjan Chakraborty
Gautam Das
Siva Gurumurthy
Koustuv Dasgupta
Sougata Mukherjea
Anupam Joshi
Amit A. Nanavati
Processing Range-Constrained Distance Queries and Searching Nearest
Neighbors on Wavelet Synopses over Multiple Streams
Ming-Syan Chen
Hao-Ping Hung
Term Context Models for Information Retrieval
Jeremy Pickens
Andrew MacFarlane
A Fast and Robust Method for Web Page Template Detection and Removal
Altigran Silva
Edleno Moura
Joao Cavalcanti
Karane Vieira
Juliana Freire
Nick Pinto
Bayesian Adaptive User Profiling with Explicit & Implicit Feedback
Philip Zigoris
Yi Zhang
Evaluation by comparing result sets in context
Paul Thomas
David Hawking
A Data Stream Language and System Designed for Power and Extensibility
Yijian Bai
Hetal Thakkar
Chang Luo
Haixun Wang
Carlo Zaniolo
A System for Query-Specific Document Summarization
Ramakrishna Varadarajan
Vagelis Hristidis
Noun Phrase Semantic Interpretation with Cross-linguistic Evidence
Roxana Girju
Efficiently Clustering Transactional Data with Weighted Coverage Density
Hua Yan
keke Chen
Ling Liu
Joonsoo Bae
Incorporating Query Difference for Learning Retrieval Functions in World
Wide Web Search
Hongyuan Zha
Zhaohui Zheng
Haoying Fu
Gordon Sun
Heuristic Containment Check of Partial Tree-Pattern Queries in the Presence
of Index Graphs
Dimitri Theodoratos
Stefanos Souldatos
Pawel Placek
Timos Sellis
Theodore Dalamagas
Tracking Dragon-Hunters with Language Models
Anton Leuski
Victor Lavrenko
TRIPS and TIDES: New Algorithms for Tree Mining
Parthasarathy Srinivasan
Shirish Tatikonda
Tahsin Kurc
Estimating Average Precision with Incomplete and Imperfect Judgments
Javed Aslam
Emine Yilmaz
Knowing a Web Page by the Company It Keeps
Xiaoguang Qi
Brian Davison
Designing Semantics-Preserving Cluster Representatives for Scientific Input
Conditions
Aparna Varde
Mohammed Maniruzzaman
Elke Rundensteiner
Carolina Ruiz
David Brown
Richard Sisson
Eigen-Trend: Trend Analysis in the Blogosphere based on Singular Value
Decompositions
Yun Chi
Junichi Tatemura
Belle Tseng
Pruning Strategies for Mixed-Mode Querying
Vo Anh
Alistair Moffat
Accepted Poster Papers
-----------------------------
Retrieval Evaluation With Incomplete Relevance Data: A Comparative Study of
Three Measures
Leif Grönqvist
Per Ahlgren
Semi-automatic Annotation and MPEG-7 Authoring of Dance Videos
KANNAN RAJKUMAR
Balakrishnan Ramadoss
Resource-Aware Kernel Density Estimators over Streaming Data
Christoph Heinz
Bernhard Seeger
An Efficient One-Phase Holistic Twig Join Algorithm for XML Data
Zhewei Jiang
Cheng Luo
Wen Chi Hou
Qiang Zhu
Chi-Fang Wang
Representing Documents with Named Entities for Story Link Detection (SLD)
Chirag Shah
W. Bruce Croft
David Jensen
Query Taxonomy Generation for Web Search
ChenMing Hung
Pu-Jeng Cheng
Multi-Task Text Segmentation and Alignment Based on Weighted Mutual
Information
Bingjun Sun
Ding Zhou
Hongyuan Zha
John Yen
Approximate Reverse k-Nearest Neighbor Queries in General Metric Spaces
Peer Kröger
Elke Achtert
Christian Böhm
Peter Kunath
Matthias Renz
Alexey Pryakhin
Estimation, Sensitivity, and Generalization in Parameterized Retrieval
Models
Donald Metzler
A structure-oriented relevance feedback method from XML retrieval
Lobna Hlaoua
Karen Sauvagnat
Mohand Boughanem
Q-Rank: Re-Ranking Search Results Using Query Logs
Silviu Cucerzan
Ziming Zhuang
Integration of Cluster Ensemble and EM based Text Mining for Microarray
Gene Cluster Identification and Annotation
Xiaohua Hu
Xiaodan Zhang
Xiaohua Zhou
Best-k Queries on Database Systems
Tao Tao
Chengxiang Zhai
Mapping directories and OWL ontologies with AROMA
Jérôme David
Fabrice GUILLET
Henri BRIAND
Practical Private Data Matching Deterrent to Spoofing Attacks
Yanjiang Yang
Robert Deng
Feng Bao
The Visual Funding Navigator: Analysis of the NSF Funding Information
Shixia Liu
Nan Cao
Hao Lv
Hui Su
Towards Interactive Indexing for Large Chinese Calligraphic Character
Databases
Yi Zhuang
Yueting Zhuang
Qing Li
Lei Chen
Combining Classifiers to Organize Online Databases
Juliana Freire
Luciano Barbosa
Introduction to a new Farsi Stemmer
Alireza Mokhtaripour
Matching and Evaluation of Disjunctive Predicates for Data Stream Sharing
Richard Kuntschke
Alfons Kemper
Mining Coherent Patterns from Heterogeneous Microarray Data
Xiang Zhang
Wei Wang
Probabilistic Document-Context Based Relevance Feedback with Limited
Relevance Judgments
H. C. Wu
Robert W. P. Luk
K. F. Wong
K. L. Kwok
Rank Synopses for Efficient Time Travel on the Web Graph
Klaus Berberich
Srikanta Bedathur
Gerhard Weikum
A Neighborhood-Based Approach for Clustering of Linked Document Collections
Ralitsa Angelova
Stefan Siersdorfer
Adapting Association Patterns for Text Categorization: Weaknesses and
Enhancements
Tieyun Qian
Hui Xiong
Yuanzhen Wang
Enhong Chen
A Comparative Study on Classifying the Functions of Web Page Blocks
Xiangye Xiao
Qiong Luo
Xing Xie
Wei-Ying Ma
Effective and Efficient Similarity Search in Time Series
Andrea Tagarelli
Sergio Greco
Massimiliano Ruffolo
The Query Vector Document Model
Fabrizio Silvestri
Diego Puppin
Ranking in Context using Vector Spaces
Massimo Melucci
Hierarchical, Perceptron-like Learning for Ontology Based Information
Extraction
Yaoyong Li
Kalina Bontcheva
Hamish Cunningham
Direct Comparison of Commercial and Academic Retrieval System: an initial
study
Yefei Peng
Daqing He
Boosting Relevance Model Performance with Query Term Dependence
Koji Eguchi
W. Bruce Croft
Amnesic Online Synopses for Moving Objects
Michalis Potamias
Kostas Patroumpas
Timos Sellis
Collaborative Filtering in Dynamic Usage Environments
Olfa Nasraoui
Jeff Cerwinske
Carlos Rojas
Fabio Gonzalez
Multi-Query Optimization of Sliding Window Aggregates by Schedule
Synchronization
Lukasz Golab
Kumar Gaurav Bijay
M. Tamer Ozsu
Robust Periodicity Detection Algorithms
Parthasarathy Srinivasan
Sameep Mehta
Soundararajan Srinivasan
Search Result Summarization and Disambiguation via Contextual Dimensions
Sachindra Joshi
Krishna P Chitrapura
Raghuram Krishnapuram
PEPX: A Query-Friendly Probabilistic XML Database
Yi Chen
Te Li
Qihong Shao
Processing Information Intent via Weak Labeling
Anthony Tomasic
John Zimmerman
Isaac Simmons
Maximizing the sustained throughput of distributed continuous queries
Themis Palpanas
Ioana Stanoi
George Mihaila
Christian Lang
Query-specific clustering of Search Results based on Document-Context
Similarity Scores
Edward Dang
Integrated RFID Data Modeling: An Approach for Querying Physical Objects in
Pervasive Computing
Shaorong Liu
Fusheng Wang
Peiya Liu
Modeling Performance-Driven Workload Characterization of Web Search Systems
Claudine Badue
Ricardo Baeza-Yates
Artur Ziviani
Nivio Ziviani
Berthier Ribeiro-Neto
Constructing Better Document and Query Models with Markov Chains
Guihong Cao
Jian-Yun Nie
Jing Bai
IR Principles for Content-based Indexing and Retrieval of Brain Images
Bing Bai
Paul Kantor
Nicu Cornea
Deborah Silver
Exploring Feature Selection for Multi-Label Text Classification using
Ranked Retrieval Measures
J. Scott Olsson
Douglas Oard
Improving Query Translation with Confidence Estimation for Cross Language
Information Retrieval
Youssef Kadri
HUX: A Schema-centric Approach for Updating XML Views
Ling Wang
Elke Rundensteiner
Murali Mani
Ming Jiang
Pisa : Progressive Mining of Sequential Patterns
Ming-Syan Chen
Jian-Chih Ou
Jen-Wei Huang
Chi-Yao Tseng
Mining Multiple Private Databases using a Privacy Preserving kNN Classifier
Li Xiong
Subramanyam Chitti
Ling Liu
Pseudo-Anchor Text Extraction for Searching Vertical Objects
Shuming Shi
Zaiqing Nie
Ji-Rong Wen
Fei Xing
Mingjie Zhu
Continuous Keyword Search on Multiple Text Streams
Vagelis Hristidis
Oscar Valdivia
Michail Vlachos
Philip Yu
Information Retrieval from Relational Databases using Semantic Queries
Anand Ranganathan
Zhen Liu
Filtering or Adapting: Two Strategies to Exploit Noisy Parallel Corpora for
CLIR
Lixin Shi
Jian-Yun Nie
Efficient Mining of Max Frequent Patterns in a Generalized Environment
Donghui Zhang
Daniel Kunkle
Gene Cooperman
Measuring the Meaning in Time Series Clustering of Text Search Queries
Kristina Klinkner
Bing Liu
Rosie Jones
November 6-11, 2006
http://sa1.sice.umkc.edu/cikm2006/
Sheraton Crystal City Hotel Arlington, VA 22202
Sponsored by: ACM SIGIR, and SIGWEB
*****************************************************************************
Number of submissions: 537
We accepted 15% as full papers and 10% as poster papers.
Accepted full papers: 81
Accepted poster papers: 56
Accepted Full Papers
---------------------------
Automatic Computation of Semantic Proximity Using Taxonomic Knowledge
Cai-Nicolas Ziegler
Kai Simon
Georg Lausen
Secure search in enterprise webs: tradeoffs in efficient implementation for
document level security
Peter Bailey
David Hawking
Brett Matson
Performance Thresholding in Practical Text Classification
Hinrich Schuetze
Efficient Model Selection for Regularized Linear Discriminant Analysis
Jieping Ye
Tao Xiong
Qi Li
Ravi Janardan
Jinbo Bi
Vladimir Cherkassky
Chandra Kambhamettu
Ranking Web Objects from Multiple Communities
Le Chen
Lei Zhang
Feng Jing
Ke-Feng Deng
Wei-Ying Ma
Window Join Approximation over Data Streams with Importance Semantics
Qiang Zhu
Wen Chi Hou
Adegoke Ojewole
Ranking Robustness: A Novel Framework to Predict Query Performance
Yun Zhou
W. Bruce Croft
Annotation Propagation Revisited for Key Preserving Views
Floris Geerts
Gao Cong
Wenfei Fan
Text Classification Improved through Multigram Models
Dou Shen
Improving Novelty Detection for General Topics Using Sentence Level
Information Patterns
Xiaoyan Li
An Integer Programming Approach for Frequent Itemset Hiding
Vassilios Verykios
Aris Gkoulalas-Divanis
Vector and Matrix Operations Programmed with UDFs in a Relational DBMS
Carlos Ordonez
Javier Garcia-Garcia
Exploiting Asymmetry in Hierarchical Topic Extraction
Sreenivas Gollapudi
Rina Panigrahy
3DString: A Feature String Kernel for 3D Object Classification on Voxelized
Data
Karsten Borgwardt
Johannes Aßfalg
Hans-Peter Kriegel
KDDCS: A Load-Balanced In-Network Data-Centric Storage Scheme for Sensor
Networks
Mohamed Aly
Kirk Pruhs
Panos K. Chrysanthis
Efficient Processing of Complex Similarity Queries in RDBMS through Query
Rewriting
Caetano Traina
Agma Traina
Marcos Rodrigues Vieira
Adriano Siqueira Arantes
Christos Faloutsos
Movie review mining and summarization
Li Zhuang
Feng Jing
Xiao-Yan Zhu
Lei Zhang
Capturing Community Search Expertise for Personalized Web Search using
Snippet-Indexes
Oisin Boydell
Barry Smyth
Validating Associations in Biological Databases
Francisco M Couto
Pedro M Coutinho
Mario Silva
Query Optimization using Restructured Views
Rada Chirkova
Fereidoon Sadri
Estimating Corpus Size via Queries
Ravi Kumar
Andrew Tomkins
Andrei Broder
Marcus Fontoura
Vanja Josifovski
Rajeev Motwani
Ying Xu
Rina Panigrahy
Shubha Nabar
Concept Similarity Mining without Frequency Information from Domain
Describing Taxonomies
Jong Wook Kim
K. Selcuk Candan
In Search of Meaning for Time Series Subsequence Clustering: Matching
Algorithms Based on a New Distance Measure
Dina Goldin
Ricardo Mardales
George Nagy
Distributed Spatio-Temporal Similarity Search
Demetrios Zeinalipour-Yazti
Song Lin
Dimitrios Gunopulos
Concept Frequency Distribution in Biomedical Text Summarization
Lawrence Reeve
Hyoil Han
Saya V. Nagori
Jonathan Yang
Tami Schwimmer
Ari D. Brooks
Mining Compressed Commodity Workflows From Massive RFID Data Sets
Hector Gonzalez
Jiawei Han
Xiaolei Li
Topic Evolution and Social Interactions: How Authors effect Research
Ding Zhou
Xiang Ji
Hongyuan Zha
C. Lee Giles
Improve query I/O performance by permuting and refining block request
sequences
Xiaoyu Wang
Mitch Cherniack
Mining Blog Stories Using Community-based and Temporal Clustering
Arun Qamra
Belle Tseng
Edward Chang
Concept-based Document Readability in Domain Specific Information Retrieval
Xin Yan
Dawei Song
Xue Li
Privacy Preserving Sequential Pattern Mining In Distributed Databases
Vishal Kapoor
Pascal Poncelet
Francois Trousset
M. Teisseire
Cache-Oblivious Nested-Loop Joins
Bingsheng He
Qiong Luo
A Dictionary for Approximate String Search and Longest Prefix Search
Sreenivas Gollapudi
Rina Panigrahy
Discovering and Exploiting Keyword and Attribute-Value Co-occurrences to
Improve P2P Routing Indices
Matthias Bender
Sebastian Michel
Nikos Ntarmos
Peter Triantafillou
Gerhard Weikum
Christian Zimmer
A Document-Centric Approach to Static Index Pruning in Text Retrieval
Systems
Stefan Buettcher
Charles Clarke
Effective and Efficient Classification on a Search-Engine Model
Kunal Punera
Aris Anagnostopoulos
Andrei Broder
SaLSa: Computing the Skyline without Scanning the Whole Sky
Marco Patella
Ilaria Bartolini
Paolo Ciaccia
Query Result Ranking over E-commerce Web Databases
Weifeng Su
Adaptive Non-linear Clustering in Data Streams
Ankur Jain
Zhihua Zhang
Edward Chang
Constrained Subspace Skyline Computation
Evangelos Dellis
Ilya Vladimirskiy
Bernhard Seeger
Yannis Theodoridis
Akrivi Vlachou
An Approximate Multi-Word Matching Algorithm for Robust Document Retrieval
Atsuhiro Takasu
Document Re-ranking Using Cluster Validation and Label Propagation
Lingpeng Yang
Donghong Ji
Guodong Zhou
Classification spanning correlated data streams
Rong She
Yabo Xu
Ke Wang
Jian Pei
Processing Relaxed Skylines in PDMS Using Distributed Data Summaries
Katja Hose
Christian Lemke
Kai-Uwe Sattler
Structure-Based Querying of Proteins Using Wavelets
Parthasarathy Srinivasan
Keith Marsolo
Kotagiri Ramamohanarao
A combination of trie-trees and inverted files for the indexing of
set-valued
Manolis Terrovitis
Spyros Passas
Panos Vassiliadis
Timos Sellis
Efficient Join Processing over Uncertain Data
Sarvjeet Singh
Reynold Cheng
Yuni Xia
Sunil Prabhakar
Rahul Shah
Jeffrey Vitter
Optimisation methods for ranking functions with multiple parameters
Stephen Robertson
Michael Taylor
Hugo Zaragoza
Nick Craswell
Chris Burges
On GMAP
Stephen Robertson
A Probabilistic Relevance Propagation Model for Hypertext Retrieval
Azadeh Shakery
Chengxiang Zhai
Summarizing Local Context to Personalize Global Web Search
Paul - Alexandru Chirita
Wolfgang Nejdl
Claudiu Firan
Describing Differences between Databases
Heiko Müller
Johann-Christoph Freytag
Ulf Leser
Voting for Candidates: Adapting Data Fusion Techniques for an Expert Search
Task
Craig Macdonald
Iadh Ounis
Finding Highly Correlated Pairs Efficiently with Powerful Pruning
Jian Zhang
Joan Feigenbaum
Investigating the Exhaustivity Dimension in Content-Oriented XML Element
Retrieval Evaluation
Paul Ogilvie
A Study on the Effects of Personalization and Task Information on Implicit
Feedback Performance
Ryen White
Diane Kelly
POLESTAR - Collaborative Knowledge Management and Sensemaking Tools for
Intelligence Analysts
Nicholas Pioch
John Everett
Incremental Hierarchical Clustering of Text Documents
Nachiketa Sahoo
Jamie Callan
Ramayya Krishnan
George Duncan
Rema Padman
Multi-Evidence, Multi-Criteria, Lazy Associative Document Classification
Adriano Veloso
Wagner Meira Jr.
Marco Cristo
Mohammed Zaki
Marcos Goncalves
Coupling Feature Selection and Machine Learning Methods for Navigational
Query Identification
Yumao Lu
Xin Li
Fuchun Peng
Nawaaz Ahmed
Utility Scoring of Product Reviews
Zhu Zhang
Balaji Varadarajan
Task-based Process Know-how Reuse and Proactive Information Delivery in
TaskNavigator
Oleg Rostanin
Harald Holz
Takeshi Suzuki
Kaoru Maeda
Andreas Dengel
Katsumi Kanasaki
On the Structural Properties of Massive Telecom Call Graphs: Findings and
Implications
Dipanjan Chakraborty
Gautam Das
Siva Gurumurthy
Koustuv Dasgupta
Sougata Mukherjea
Anupam Joshi
Amit A. Nanavati
Processing Range-Constrained Distance Queries and Searching Nearest
Neighbors on Wavelet Synopses over Multiple Streams
Ming-Syan Chen
Hao-Ping Hung
Term Context Models for Information Retrieval
Jeremy Pickens
Andrew MacFarlane
A Fast and Robust Method for Web Page Template Detection and Removal
Altigran Silva
Edleno Moura
Joao Cavalcanti
Karane Vieira
Juliana Freire
Nick Pinto
Bayesian Adaptive User Profiling with Explicit & Implicit Feedback
Philip Zigoris
Yi Zhang
Evaluation by comparing result sets in context
Paul Thomas
David Hawking
A Data Stream Language and System Designed for Power and Extensibility
Yijian Bai
Hetal Thakkar
Chang Luo
Haixun Wang
Carlo Zaniolo
A System for Query-Specific Document Summarization
Ramakrishna Varadarajan
Vagelis Hristidis
Noun Phrase Semantic Interpretation with Cross-linguistic Evidence
Roxana Girju
Efficiently Clustering Transactional Data with Weighted Coverage Density
Hua Yan
keke Chen
Ling Liu
Joonsoo Bae
Incorporating Query Difference for Learning Retrieval Functions in World
Wide Web Search
Hongyuan Zha
Zhaohui Zheng
Haoying Fu
Gordon Sun
Heuristic Containment Check of Partial Tree-Pattern Queries in the Presence
of Index Graphs
Dimitri Theodoratos
Stefanos Souldatos
Pawel Placek
Timos Sellis
Theodore Dalamagas
Tracking Dragon-Hunters with Language Models
Anton Leuski
Victor Lavrenko
TRIPS and TIDES: New Algorithms for Tree Mining
Parthasarathy Srinivasan
Shirish Tatikonda
Tahsin Kurc
Estimating Average Precision with Incomplete and Imperfect Judgments
Javed Aslam
Emine Yilmaz
Knowing a Web Page by the Company It Keeps
Xiaoguang Qi
Brian Davison
Designing Semantics-Preserving Cluster Representatives for Scientific Input
Conditions
Aparna Varde
Mohammed Maniruzzaman
Elke Rundensteiner
Carolina Ruiz
David Brown
Richard Sisson
Eigen-Trend: Trend Analysis in the Blogosphere based on Singular Value
Decompositions
Yun Chi
Junichi Tatemura
Belle Tseng
Pruning Strategies for Mixed-Mode Querying
Vo Anh
Alistair Moffat
Accepted Poster Papers
-----------------------------
Retrieval Evaluation With Incomplete Relevance Data: A Comparative Study of
Three Measures
Leif Grönqvist
Per Ahlgren
Semi-automatic Annotation and MPEG-7 Authoring of Dance Videos
KANNAN RAJKUMAR
Balakrishnan Ramadoss
Resource-Aware Kernel Density Estimators over Streaming Data
Christoph Heinz
Bernhard Seeger
An Efficient One-Phase Holistic Twig Join Algorithm for XML Data
Zhewei Jiang
Cheng Luo
Wen Chi Hou
Qiang Zhu
Chi-Fang Wang
Representing Documents with Named Entities for Story Link Detection (SLD)
Chirag Shah
W. Bruce Croft
David Jensen
Query Taxonomy Generation for Web Search
ChenMing Hung
Pu-Jeng Cheng
Multi-Task Text Segmentation and Alignment Based on Weighted Mutual
Information
Bingjun Sun
Ding Zhou
Hongyuan Zha
John Yen
Approximate Reverse k-Nearest Neighbor Queries in General Metric Spaces
Peer Kröger
Elke Achtert
Christian Böhm
Peter Kunath
Matthias Renz
Alexey Pryakhin
Estimation, Sensitivity, and Generalization in Parameterized Retrieval
Models
Donald Metzler
A structure-oriented relevance feedback method from XML retrieval
Lobna Hlaoua
Karen Sauvagnat
Mohand Boughanem
Q-Rank: Re-Ranking Search Results Using Query Logs
Silviu Cucerzan
Ziming Zhuang
Integration of Cluster Ensemble and EM based Text Mining for Microarray
Gene Cluster Identification and Annotation
Xiaohua Hu
Xiaodan Zhang
Xiaohua Zhou
Best-k Queries on Database Systems
Tao Tao
Chengxiang Zhai
Mapping directories and OWL ontologies with AROMA
Jérôme David
Fabrice GUILLET
Henri BRIAND
Practical Private Data Matching Deterrent to Spoofing Attacks
Yanjiang Yang
Robert Deng
Feng Bao
The Visual Funding Navigator: Analysis of the NSF Funding Information
Shixia Liu
Nan Cao
Hao Lv
Hui Su
Towards Interactive Indexing for Large Chinese Calligraphic Character
Databases
Yi Zhuang
Yueting Zhuang
Qing Li
Lei Chen
Combining Classifiers to Organize Online Databases
Juliana Freire
Luciano Barbosa
Introduction to a new Farsi Stemmer
Alireza Mokhtaripour
Matching and Evaluation of Disjunctive Predicates for Data Stream Sharing
Richard Kuntschke
Alfons Kemper
Mining Coherent Patterns from Heterogeneous Microarray Data
Xiang Zhang
Wei Wang
Probabilistic Document-Context Based Relevance Feedback with Limited
Relevance Judgments
H. C. Wu
Robert W. P. Luk
K. F. Wong
K. L. Kwok
Rank Synopses for Efficient Time Travel on the Web Graph
Klaus Berberich
Srikanta Bedathur
Gerhard Weikum
A Neighborhood-Based Approach for Clustering of Linked Document Collections
Ralitsa Angelova
Stefan Siersdorfer
Adapting Association Patterns for Text Categorization: Weaknesses and
Enhancements
Tieyun Qian
Hui Xiong
Yuanzhen Wang
Enhong Chen
A Comparative Study on Classifying the Functions of Web Page Blocks
Xiangye Xiao
Qiong Luo
Xing Xie
Wei-Ying Ma
Effective and Efficient Similarity Search in Time Series
Andrea Tagarelli
Sergio Greco
Massimiliano Ruffolo
The Query Vector Document Model
Fabrizio Silvestri
Diego Puppin
Ranking in Context using Vector Spaces
Massimo Melucci
Hierarchical, Perceptron-like Learning for Ontology Based Information
Extraction
Yaoyong Li
Kalina Bontcheva
Hamish Cunningham
Direct Comparison of Commercial and Academic Retrieval System: an initial
study
Yefei Peng
Daqing He
Boosting Relevance Model Performance with Query Term Dependence
Koji Eguchi
W. Bruce Croft
Amnesic Online Synopses for Moving Objects
Michalis Potamias
Kostas Patroumpas
Timos Sellis
Collaborative Filtering in Dynamic Usage Environments
Olfa Nasraoui
Jeff Cerwinske
Carlos Rojas
Fabio Gonzalez
Multi-Query Optimization of Sliding Window Aggregates by Schedule
Synchronization
Lukasz Golab
Kumar Gaurav Bijay
M. Tamer Ozsu
Robust Periodicity Detection Algorithms
Parthasarathy Srinivasan
Sameep Mehta
Soundararajan Srinivasan
Search Result Summarization and Disambiguation via Contextual Dimensions
Sachindra Joshi
Krishna P Chitrapura
Raghuram Krishnapuram
PEPX: A Query-Friendly Probabilistic XML Database
Yi Chen
Te Li
Qihong Shao
Processing Information Intent via Weak Labeling
Anthony Tomasic
John Zimmerman
Isaac Simmons
Maximizing the sustained throughput of distributed continuous queries
Themis Palpanas
Ioana Stanoi
George Mihaila
Christian Lang
Query-specific clustering of Search Results based on Document-Context
Similarity Scores
Edward Dang
Integrated RFID Data Modeling: An Approach for Querying Physical Objects in
Pervasive Computing
Shaorong Liu
Fusheng Wang
Peiya Liu
Modeling Performance-Driven Workload Characterization of Web Search Systems
Claudine Badue
Ricardo Baeza-Yates
Artur Ziviani
Nivio Ziviani
Berthier Ribeiro-Neto
Constructing Better Document and Query Models with Markov Chains
Guihong Cao
Jian-Yun Nie
Jing Bai
IR Principles for Content-based Indexing and Retrieval of Brain Images
Bing Bai
Paul Kantor
Nicu Cornea
Deborah Silver
Exploring Feature Selection for Multi-Label Text Classification using
Ranked Retrieval Measures
J. Scott Olsson
Douglas Oard
Improving Query Translation with Confidence Estimation for Cross Language
Information Retrieval
Youssef Kadri
HUX: A Schema-centric Approach for Updating XML Views
Ling Wang
Elke Rundensteiner
Murali Mani
Ming Jiang
Pisa : Progressive Mining of Sequential Patterns
Ming-Syan Chen
Jian-Chih Ou
Jen-Wei Huang
Chi-Yao Tseng
Mining Multiple Private Databases using a Privacy Preserving kNN Classifier
Li Xiong
Subramanyam Chitti
Ling Liu
Pseudo-Anchor Text Extraction for Searching Vertical Objects
Shuming Shi
Zaiqing Nie
Ji-Rong Wen
Fei Xing
Mingjie Zhu
Continuous Keyword Search on Multiple Text Streams
Vagelis Hristidis
Oscar Valdivia
Michail Vlachos
Philip Yu
Information Retrieval from Relational Databases using Semantic Queries
Anand Ranganathan
Zhen Liu
Filtering or Adapting: Two Strategies to Exploit Noisy Parallel Corpora for
CLIR
Lixin Shi
Jian-Yun Nie
Efficient Mining of Max Frequent Patterns in a Generalized Environment
Donghui Zhang
Daniel Kunkle
Gene Cooperman
Measuring the Meaning in Time Series Clustering of Text Search Queries
Kristina Klinkner
Bing Liu
Rosie Jones
2008年7月11日星期五
Tutorials and Reviews on Boosting
Cited from:http://www.cs.ucsd.edu/~aarvey/boosting_papers.html
Tutorials and Reviews on Boosting
- A short introduction to boosting by Freund and Schapire, 1999. An introduction to the theory and application of boosting.
- AdaBoost in action by Freund. An applet that shows how AdaBoost behaves during the training phase.
- Schapire's "boosting approach to machine learning".
- Ron Meir and Gunnar Ratsch's introduction to boosting and leveraging.
Reading Lists
I've highlighted the most important papers, even if they are ealier in the progression.
The AdaBoost Approach
- A decision-theoretic generalization of on-line learning and an application to boosting. Freund and Schapire 1995/7. You have to look at this paper, but you don't have to read it.
- Improved Boosting Algorithms Using Confidence-rated Predictions. Schapire and Singer 1999. Sections 1-4 are an absolute must read. Very concise and packed with useful interpretations.
- The boosting approach to machine learning: An overview. Schapire 2002. Section 6. Supplement with the original Friedman, Hastie, Tibshirani paper if desired. Describes an alternative and gentler loss (a.k.a. potential, potential loss, cost, etc) function.
- Boosting the Margin: A New Explanation for the Effectiveness of Voting Methods. Schapire et al. 1998. Sections 1,5,6. Understanding the idea is more important than the actual proofs.
- Boosting Algorithms as Gradient Descent. Mason et al. 2000. Similar in spirit to the view of Friedman, Hastie, and Tibshirani 1998. Sections 1 and 2 develop the AnyBoost framework, which is a helpful generalizations to AdaBoost.
The Boost By Majority Approach
- Boosting a weak learning algorithm by majority. Freund 1990/5. The first part of section 2 (before 2.1) describes the "boost by majority game".
- Improved Boosting Algorithms Using Confidence-rated Predictions. Schapire and Singer 1999. Sections 1-4 are an absolute must read. Very concise and packed with useful interpretations.
- An adaptive version of the boost by majority algorithm. Freund 1999/2000. IMHO, the biggest jump in boosting since Schapire's original algorithm. There are two main parts to the paper: 1) infinitely many iterations with infinitely small movements and 2) setting alpha by satisfying the constraints: a) expected value of $h(x)y$ is 0 w.r.t. the new weighting and b) the average difference in potential. If you understand these two ideas and their motivations (from Schapire and Singer 99 and Freund 1990/95) the algorithm falls out naturally.
- Drifting games. Schapire 2000. A very nice generalization of the boost by majority paradigm to the more "natural" space. This interpretation is also useful for understanding BrownBoost.
- Continuous Drifting games. Freund and Opper 2002. An extension of Schapire's drifting games to continuous domains. Both BrownBoost and NormalBoost are natural consequences of this work.
The Bregmen Divergences, Geometry, and Optimization Approach
- Boosting as Entropy Projection. Kivinen and Warmuth 1999. An interesting and very different approach that minimizes convex divergence measures.
- Logistic Regression, AdaBoost and Bregman Distances. Collins, Schapire, Singer 2000. Similar to Kivinen and Warmuth; however, it provides a few very practical results for converting AdaBoost to LogitBoost using an alternative loss function. Also ties in well with some of the statistical approaches to boosting.
- Linear Programming Boosting via Column Generation. Demiriz, Bennett, and Shawe-Taylor 2002. Introduction of LPBoost and general relationship to linear programming and boosting. A very complete discussion, showing how LPBoost can be used in many of the classic statistical settings.
- Totally Corrective Boosting Algorithms that Maximize the Margin. Warmuth, Liao, and Ratsch 2006. Puts the LPBoost and geometric (Bregman divergence of Kivinen and Warmuth) together. Instead of minimizing the correlation of the hypothesis and the subsequent weighting of the training set, TotalBoost minimizes the corrleations between
all previous hypotheses and the next weighting. This leads to sparser sets of hypotheses and a very nifty iteration bound. - Boosting Algorithms for Maximizing the Soft Margin. Warmuth, Glocer, and Ratsch 2007. Simple moral: TotalBoost overfits, SoftBoost is noise resistant. SoftBoost comes with an iteration bound and noise resistance using slack variables in SVM literature.
Statistical Approaches to Boosting
- Additive Logistic Regression: a Statistical View of Boosting. Friedman, Hastie, Tibshirani 1999. An interesting paper that casts boosting into the classic log likelihood model that all of statistics follows. The resulting algorithmic contribution, LogitBoost, can be implement in a AdaBoost framework (LogLossBoost in JBoost) using an alternative weighting. Be sure to read rejoinders as some of them gave me a chuckle.
- Friedman has a paper on \epsilon boosting which sounds very interesting, though I have yet to read it.
- Tong Zhang has a lot of very good papers. I'll list the highlights when I finish reading them... this may take a while.
- The question of consistency was a big deal in the statistics community and was approached by a large variety of people. They showed variants of boosting were consistent, but never AdaBoost. I believe Peter Bartlett gets credit for finally showing that AdaBoost is consistent.
- Evidence Contrary to the Statistcal View of Boosting. Mease and Wyner 2008. This paper is extremely important to read if you plan on doing research in boosting for practical purposes. It is not bulletproof (I'm sure someone will be able to find issues with it), but it is a well thought out and executed idea that uses empirical evidence instead of theory to drive boosting research. Some of the details of the paper may be proven slightly incorrect, but I believe taht the overall idea will stand up to scrutiny.
Misc Background Reading
- The strength of weak learnability. Schapire 1990. Cool algorithm, cool analysis, cool write up. Unfortunately rendered useless by majority vote methods.
- Any of the tutorials. There are a lot of really good boosting tutorials that cover the whole spectrum of applied to theoretical.
- The alternating decision tree learning algorithm. Freund and Mason 1999. An interesting way to use boosting with decision trees/stumps.
- Any of the empirical comparisons of different voting methods.
- The ideas of bagging and arcing are frequently mentioned in boosting papers. These are ideas of the extremely well respected statistician Leo Breiman. While they haven't caught on in the same way that boosting has (see "Boosting the margin..." for an explanation) they are interesting ideas and bagging (along with bootstrapping) is widely used for variance reduction of any estimator.
Boosting Software
In a non-accidental ordering:- JBoost. Powerful, extendible, highly tunable, efficient, and integratable into your own software. A bit of a learning curve, but well worth it.
- BoosTexter (also an implementation available in JBoost). Schapire's code for the text categorizing BoosTexter.
- GBM for R by Greg Ridgeway. A powerful and standardized module used mostly by statisticians.
- WEKA. User friendly.
订阅：
博文 (Atom)
博文
