Monthly Archives: May 2009

观近期诸新闻事件有感

先引用一段:

北京时间1987年9月14日21时07分,北京市计算机应用技术研究所成功发送了中国第一封电子邮件,这封邮件的内容是:“Across the Great Wall we can reach every corner in the world.(越过长城,走向世界)”。这标志这中国与国际计算机网络已经成功连接。

虽然现在Great Fire Wall的出现让这句话变得有点黑色幽默,但我们也许不得不承认,当年这几位科学家这个纯技术与学术研究的工作,它对中国的意义也许超过了90年前、60年前、20年前那些先辈们的头颅与热血。

NLP笔记(1): 关于单词

构词法

变形(inflection):指对词根形式进行系统地修改,比如加前缀后缀,它并不显著地改变词语的类别和语义,主要用于变换时态(例如英语中的进行时就是加后缀ing)、单复数形式(例如英语中的复数通常就是加后缀s)等等。

派生(derivation):变化不是很系统化,词类和词义会发生改变。例如:compute – computer – computerize – computerization

复合(compouding):比如doghouse这样的词

接语(cliticization):我的理解就是类似I’ve这种形式的东西

名词和代词:英语的名词比较简单,变形只有一种——复数。在其他语言中常见的名词变形有:单复数、性别(如法语的二性、德语的三性、以及据说某些语言有数十种性别)、格(在英语中名词只有“所有格”的形式不同,另外代词的主格和宾格形式是不同的,在其他语言中还有更复杂的什么位置格等等)

动词:英语中的动词变形大概有如下几种:第三人称单数现在进行时、过去时、过去分词、现在进行时等等,数量比较有限,与此相反,芬兰语、土耳其语等等可以有多达上万种变形。

形容词:英语中的形容词变形也不多,只有+ly变副词,+er,+est变比较级和最高级等。在有的语言中,形容词是必须与所修饰的名词的数、性、格相配的,所以就又复杂得多了。

由此可见英语实在算是一种很简单的语言了啊~ 所以英语的stemming相对简单,用一些规则就可以差不多完成,但对于那些变形超级复杂的语言,或者是需要完整地识别出这个词是经过了怎样的变形时,就需要用Finite-State Transducer来搞了。

最后记一下常用的缩写:NN: 单数名词;NNS: 复数名词;VB: 动词原形;VBZ: 动词第三人称单数;VBD: 动词过去式;VBG: 现在分词;MD: 情态动词;JJ: 形容词;AT: 冠词;IN: 介词;NP: 名词短语;VP: 动词短语;PP: 介词短语;S: 句子

我对Wolfram Alpha的几点看法

Wolfram Alpha最近炒得很热,如果你不是火星人的话应该听说过了,到网上搜了一下评论,中文的大都在人云亦云,英文的倒有一些不错的,比如这篇。下面说说我的几点看法:

首先,说它是“Google杀手”什么的我看是纯属炒作了,这个东西跟google的服务几乎没有什么交集:我的理解是它试图对用户的问题给出十分精确的结果,而不是一堆有点关系的网页,但我感觉更多时候用户需要的并不是精确的结果,甚至用户自己都不确定他真正想要的是什么,而传统搜索引擎正好可以满足这一点,在这里WA是无法取代传统引擎的。

然后,我比较关心它对知识的提取是如何进行的。看到一篇介绍文章说做这个系统用了十年,不知是真是假,如果这十年都是用来人肉搭建知识库的话,我觉得这样做是没有前途的,知识的爆炸式增长使得人工的成本很快就会无法承受。我觉得真正要做的应该是在传统的搜索引擎上套上一个一个足够强大的Information Extraction,自动从检索结果中提取中有用的知识。可惜貌似没有看到WA在这个方向的努力。当然,这个也肯定不是什么新奇的idea了,IE我还不太熟,不知道现在能够做到什么程度了。

另外,用户的输入如果是自然语言的话就经常不能很好地处理,在Query处理上做的功夫明显不够,这也算是缺点之一吧。

不过这个引擎对于数学上的符号计算和软件Mathematica一样强大,毕竟是老本行,这点没得挑。所以就把它当作Mathematica的免费在线版也不错,呵呵。另外对这个问题的答案也和Google一样geek:Answer to life, the universe, and everything.

IR笔记(9): Ranking SVM

昨天随便在网上翻到一篇论文:T. Joachims, Optimizing Search Engines using Clickthrough Data, SIGKDD 02. 发现很有意思,在这里简单写一下。其实基本就是原文的翻译,而且还有很多理解不准确的地方,请大牛指正。

这篇文章感觉应该是所谓Learning to Rank的一个方法吧,大意就是通过分析日志,利用用户的点击信息对检索结果进行更好的排序。在这篇文章里把排序问题转换成了一个分类问题,然后用支持向量机(SVM)训练出一个模型来搞,感觉很好玩。

首先是通常分析系统日志,得到很多“某条结果比另一条结果更相关”这样的信息。需要注意的是这种信息通常是不能简单地通过数一下每个结果链接被点击了多少次来得出的,因为对于通常的Web Search而言,很少有用户能有耐心翻到好几页好几十页之后去看,比如在极端情况下,前几十页全是垃圾,第1000条结果才是最相关的,那么这个结果也几乎不可能有人点击的,反倒是前面的垃圾信息被点击得多些。作者在这里有一个简单的实验,对于不同的IR系统(有的很好,有的较差),统计所谓的Average Ranking,也就是用户所点击的那些结果的排名的平均值(比如用户点击了第1,5,7条结果,那么Average Ranking就是(1+5+7)/3),这样如果理想情况下,用户非常有耐心的话,应该是比较差的系统的Average Ranking会偏高,因为用户感兴趣的信息往往被排在了后面。实验结果与此相反,几个IR系统的结果都差不多,都在6左右。也就是说即使结果较差,用户仍然只关心前面的若干条。这个结果可以说明不能简单地通常计数来排序。

这篇文章里用了一个更有说服力的方法,举例如下,比如用户点击了第1,3,7条结果,我们可以认为用户是从前到后读下来的,也就是说用户认为第3条结果比第2条结果更相关,同样,第7条结果比第2,4,5,6条更相关。这样我们就得到了若干“针对某个Query q,文档d_i比文档d_j更相关”这样的信息。

对于q和d,我们可以定义一些Feature(比如q是否在d的标题中出现,q和d在向量空间中的cos相似度,d自身的PageRank等等)得到一个向量函数$$Phi (q,d_i)$$。类比用SVM解决二分类问题,我们的目标就是找到一个向量w,$$wPhi (q,d_i) > wPhi (q,d_j)$$就表示d_i比d_j更相关,我们应该train出一个w使得这些条件尽可能地满足。这个问题可以套用SVM解决,当然,再加上Kernel Trick的话也可以处理非线性特征的问题。对于SVM的细节我一直弄不太明白,这里就不胡扯淡了,总之是可以这样来搞的。弄一些训练集(即{Query、对应的返回结果、用户的点击情况}这样的Triple),训练出这个w来以后,对于新的Query,就可以用它来排序了。

路在何方

呃……这是一篇可以无视的“碎碎念”文……

其实我本不是一个有雄心的人,从小时候就是这样。没胆量,没脾气,没魄力,听老师的话,听家长的话,规规矩矩平平庸庸。中考时候一没留神,抽疯考进了一个不靠托关系走门路能达到的最nb高中的最nb班,班主任第一件事就是给我们做思想工作,大意就是让我们调整好心态,随时做好被bs的准备。因为班里全都是周围各个县市的中考前几名,谁都有可能面临忽然从状元到垫底的命运。几年下来,我的成绩在班里稳居中游,属于最不让老师操心的那种,清华北大断然无望,上个211又基本没有问题。我也乐得逍遥自在,没事搞搞电脑,玩玩Crack,再yy一下遥不可及的传说中的NOIP,即便在高三那段最疯狂的时间也是如此。小地方的孩子,眼光自然狭窄了些,虽不像那个笑话里“放羊—攒钱—娶媳妇—生小孩—小孩再放羊”这么夸张,但那时的想法是,如果以后竟然能以最喜欢的计算机编程混到饭吃,实在已是人生中最大的乐事。

可能就是大学里这个ACM比赛改变了我的部分想法,忽然发现自己可以是TJU No.1,可以是中国Top50,心里开始飘飘然了些,以前从来没有过的想法也开始冒了出来。渐渐地,开始体会到“为天地立心,为生民立命,为往圣继绝学,为万世开太平”是怎样的境界,“对爱情的渴望,对知识的追求,对人类苦难不可遏制的同情”是如何的胸怀。从前只是为那些天才而折服,YY得多了,渐渐地却开始幻想:自己说不定竟然能忝列其中呢……于是,做个优秀程序员不再是我的首选,我开始尝试投身学术研究,这恐怕是我这种性格的人所能做的最可能对别人有贡献的事了吧。然而,目标高了才发现路的艰难,任何一个方向都充满了我只能仰望的人物,我甚至连第一步都不知道如何迈出。

有时候我也怀疑自己是否真的是这块料,有时候就想如果没有这一切,比如随便找一个普通的工作,是不是反而会过得比较轻松?然而天性使然,每个人生来都会觉得自己有多么多么地与众不同,不肯承认自己只是在芸芸众生中平庸的一员。子曰五十而知天命,在这之前我怕是仍然会矛盾下去的吧,哈哈。

路在何方,我不清楚,就先走下去再说吧。