Archive | algorithm RSS feed for this section

论CAS在幼儿园点名中的应用

宝贝的幼儿园老师都是漂亮活泼又富有爱心的小天使一样的人物,非常神奇的教会了宝贝们很多我们家长们都搞不定的事情,非常有办法的完全不用发火的将这些淘气的小家伙们修理的服服贴贴,在小宝贝们眼里简直就是神一般的存在,当然在家长眼里也是。

如果你以为这就是全部,那就大错特错了。就在这两天发现了,她们居然也是深谙各种计算机中的算法。不得不偷着怀疑这些白天在学校里的陪孩子们玩的小姑娘们下班后是不是在菊厂或者其他公司写代码。IMG_20171029_214307

这不这两天在家长群里发了消息,就小露了一手。这个案例的背景是要收集到每个宝贝的家长对一个重要通知的确认。上级的重要通知,每个家的家长都要确认。如果你说请在群里回复“收到”那简直弱爆了。最终怎么确认每个都收到了。

看看我们美女老师设计的算法。如右图所示,每个家长的回复一个序号+宝贝名+收到,序号是根据前面的回复次序i++上来,并且每个回复要求追加在前面一个回复的后面。[......]

阅读全文

Tags: ,

Comments { 0 }

【转】数学之美系列十七:闪光的不一定是金子 谈谈搜索引擎作弊问题(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 }