Archive | algorithm RSS feed for this section

【转】数学之美系列十七:闪光的不一定是金子 谈谈搜索引擎作弊问题(Search Engine Anti-SPAM)

自从有了搜索引擎,就有了针对搜索引擎网页排名的作弊(SPAM)。以至于用户发现在搜索引擎中排名靠前的网页不一定就是高质量的,用句俗话说,闪光的不一定是金子。

搜索引擎的作弊,虽然方法很多,目的只有一个,就是采用不正当手段提高自己网页的排名。早期最常见的作弊方法是重复关键词。比如一个卖数码相机的网站,重复地罗列各种数码相机的品牌,如尼康、佳能和柯达等等。为了不让读者看到众多讨厌的关键词,聪明一点的作弊者常用很小的字体和与背景相同的颜色来掩盖这些关键词。其实,这种做法很容易被搜索引擎发现并纠正。在有了网页排名(page rank)以后,作弊者发现一个网页被引用的连接越多,排名就可能越靠前,于是就有了专门卖链接和买链接的生意。比如,有人自己创建成百上千个网站,这些网站上没有实质的内容,只有到他们的客户网站的连接。这种做法比重复关键词要高明得多,但是还是不太难被发现。因为那些所谓帮别人提高排名的[......]

阅读全文

Tags: , ,

Comments { 0 }

【转】数学之美系列十六:不要把所有的鸡蛋放在一个篮子里 — 谈谈最大熵模型

[我们在投资时常常讲不要把所有的鸡蛋放在一个篮子里,这样可以降低风险。在信息处理中,这个原理同样适用。在数学上,这个原理称为最大熵原理(the maximum entropy principle)。这是一个非常有意思的题目,但是把它讲清楚要用两个系列的篇幅。]

前段时间,Google 中国研究院的刘骏总监谈到在网络搜索排名中,用到的信息有上百种。更普遍地讲,在自然语言处理中,我们常常知道各种各样的但是又不完全确定的信息,我们需要用一个统一的模型将这些信息综合起来。如何综合得好,是一门很大的学问。

让我们看一个拼音转汉字的简单的例子。假如输入的拼音是”wang-xiao-bo”,利用语言模型,根据有限的上下文(比如前两个词),我们能给出两个最常见的名字“王小波”和“王晓波”。至于要唯一确定是哪个名字就难了,即使利用较长的上下文也做不到。当然,我们知道如果通篇文章是介绍文学的,作家[......]

阅读全文

Tags:

Comments { 0 }

【转】数学之美系列十五:繁与简 自然语言处理的几位精英

我在数学之美系列中一直强调的一个好方法就是简单。但是,事实上,自然语言处理中也有一些特例,比如有些学者将一个问题研究到极致,执著追求完善甚至可以说完美的程度。他们的工作对同行有很大的参考价值,因此我们在科研中很需要这样的学者。在自然语言处理方面新一代的顶级人物麦克尔 · 柯林斯 (Michael Collins) 就是这样的人。

柯林斯:追求完美
柯林斯从师于自然语言处理大师马库斯 (Mitch Marcus)(我们以后还会多次提到马库斯),从宾夕法利亚大学获得博士学位,现任麻省理工学院 (MIT) 副教授(别看他是副教授,他的水平在当今自然语言处理领域是数一数二的),在作博士期间,柯林斯写了一个后来以他名字命名的自然语言文法分析器 (sentence parser),可以将书面语的每一句话准确地进行文法分析。文法分析是很多自然语言应用的基础。虽然柯林斯的师兄布莱尔 (Eric B[......]

阅读全文

Tags:

Comments { 0 }

【转】数学之美十四:谈谈数学模型的重要性

[注:一直关注数学之美系列的读者可能已经发现,我们对任何问题总是在找相应的准确的数学模型。为了说明模型的重要性,今年七月份我在 Google 中国内部讲课时用了整整一堂课来讲这个问题,下面的内容是我讲座的摘要。]

在包括哥白尼、伽利略和牛顿在内的所有天文学家中,我最佩服的是地心说的提出者托勒密。虽然天文学起源于古埃及,并且在古巴比伦时,人们就观测到了五大行星(金、木、水、火、土)运行的轨迹,以及行星在近日点运动比远日点快。(下图是在地球上看到的金星的轨迹,看过达芬奇密码的读者知道金星大约每四年在天上画一个五角星。

kingstar

 

但是真正创立了天文学,并且计算出诸多天体运行轨迹的是两千年前古罗马时代的托勒密。虽然今天我们可能会嘲笑托勒密犯的简单的错误,但是真正了解托勒密贡献的人都会对他肃然起敬。托勒密发明了球坐标,定义了包括赤道和零度经线在内的经纬线,他提出了黄道,还发明了弧度制[......]

阅读全文

Tags: ,

Comments { 0 }

【转】数学之美系列十三:信息指纹及其应用

任何一段信息文字,都可以对应一个不太长的随机数,作为区别它和其它信息的指纹(Fingerprint)。只要算法设计的好,任何两段信息的指纹都很难重复,就如同人类的指纹一样。信息指纹在加密、信息压缩和处理中有着广泛的应用。

我们在图论和网络爬虫一文中提到,为了防止重复下载同一个网页,我们需要在哈希表中纪录已经访问过的网址(URL)。但是在哈希表中以字符串的形式直接存储网址,既费内存空间,又浪费查找时间。现在的网址一般都较长,比如,如果在 Google 或者百度在查找数学之美,对应的网址长度在一百个字符以上。下面是百度的链接

http://www.baidu.com/s?ie=gb2312&bs=%CA%FD%D1%A7%D6%AE%C3%C0&sr=&z=&cl=3&f=8
&wd=%CE%E2%BE%FC+%CA%FD%[......]

阅读全文

Tags: ,

Comments { 0 }