#2801~2806# 数学之美(完)

2801# 数学之美-Statistical Language Models

Google 的使命是 "整合全球信息,让人人能获取,使人人能受益",研究如何让机器对信息、语言做最好的处理和理解。乔姆斯基提出 “形式语言” 以后,人们更坚定了利用语法规则的办法进行文字处理的信念。

此前,数学家兼信息论的祖师爷就提出了用数学的办法处理自然语言的想法(浪潮之巅里对此人印象极为深刻),当时的计算机条件根本无法满足大量信息处理的需要。

还有一位首先成功利用数学方法解决自然语言处理问题的是语音和语言处理大师Fred Jelinek,当时贾里尼克在 IBM 公司做学术休假,领导了一批杰出的科学家利用大型计算机来处理人类语言问题。统计语言模型就是在那个时候提出的。

自然语言处理(NLP:Natural Language Process)的领域机器翻译可以包括:语音识别、印刷体、手写体识别、拼写纠错、汉字输入、文献查询。文中没有提及的有情感分析(Sentiment Analysis)和机器翻译(美国标准局NIST对所有的机器翻译系统进行了评测,Google 的系统是不仅是全世界最好的,而且高出所有基于规则的系统很多。
)。

我们都需要知道一个文字序列是否能构成一个大家能理解的句子,显示给使用者。对这个问题,我们可以用一个简单的统计模型来解决这个问题。此处作者用条件概率公式解释了及其对于语言识别的模式(马尔可夫假设)。

数学的精妙就在于把一些复杂的问题变得如此的简单,也是本书的主题。

2802#数学之美-NLP中文分词

中文分词是统计语言模型在中文处理中的一个应用,含有分词的语言包括中日韩等在自然书写时没有分割的语言,在计算机处理时首先应进行分词处理。

一般分词办法就是查字典,这种方法最早是由北京航天航空大学梁南元教授提出。 “查字典” 法把一个句子从左向右扫描一遍,遇到字典里有的词便进行标识,遇到复合词(比如 “上海大学”)就找最长的词匹配,遇到不认识的字串就分割成单字词,于是简单的分词就完成了。

90年前后,清华大学郭进博士用统计语言模型成功解决分词二义性问题,将汉语分词错误率降低了一个数量级。因此只要利用统计语言模型计算出每种分词后句子出现的概率,并找出其中概率最大的,就能够找到最好的分词方法。

实现的技巧,穷举所有可能的分词方法并计算出每种可能性下句子的概率,计算量是相当大的。因此,可以把它看成是一个动态规划(Dynamic Programming) 的问题,并利用 “维特比” 算法快速地找到最佳分词。

Ref. Computational Linguistics” (《计算机语言学》)

2803#数学之美-信息论

一些关键词:隐含马尔可夫模型 条件概率 贝叶斯公式 马尔可夫链 信息熵 冗余度 互信息

七十年代,当时 IBM 的 Fred Jelinek(关于贾的更多故事可以看《浪潮之巅》) 和卡内基·梅隆大学的 Jim and Janet Baker 分别独立地提出用隐含马尔可夫模型来识别语音,语音识别的错误率相比人工智能和模式匹配等方法降低了三倍。

八十年代李开复坚持采用隐含马尔可夫模型的框架, 成功地开发了世界上第一个大词汇量连续语音识别系统 Sphinx。

1948 年,Shannon提出了“信息熵”(Entropy)(一般用符号 H 表示,单位比特,从而解决了对信息的量化度量问题,信息熵很有意思,详见Wikipedia)用来度量信息的大小。

原理则是假设一条信息的信息量大小和它的不确定性有直接的关系。可以认为,信息量的度量就等于不确定性的多少。信息量的比特数和所有可能情况的对数函数 log 有关,一个比特是一位二进制数,计算机中的一个字节是八个比特。

e.g. 一本五十万字的中文书,信息量大约是 250 万比特,如果用一个好的算法压缩一下,整本书可以存成一个 320KB 的文件。

冗余度:如果用两字节的国标编码存储这本书,大约需要 1MB 大小,是压缩文件的三倍。这两个数量的差距,在信息论中称作"冗余度"(Redundancy)。

如果一本书重复的内容很多,它的信息量就小,冗余度就大。不同语言的冗余度差别很大,而汉语在所有语言中冗余度是相对小的。这和人们普遍的认识”汉语是最简洁的语言"是一致的。

信息熵正是对不确定性的衡量,因此信息熵可以直接用于衡量统计语言模型的好坏。

信息论中仅次于熵的另外两个重要的概念是“互信息”(Mutual Information) 和“相对熵”(Kullback-Leibler Divergence)。 互信息是信息熵的引申概念,它是对两个随机事件相关性的度量。

2804#数学之美-检索原理——布尔运算

George Boole是十九世纪英国一位小学数学老师(他生前没有人认为他是数学家,原因就是布尔运算本身= =)。

布尔在工作之余,喜欢阅读数学论著、思考数学问题。1854 年“思维规律”(An Investigation of the Laws of Thought, on which are founded the Mathematical Theories of Logic and Probabilities)一书,第一次向人们展示了如何用数学的方法解决逻辑问题。

布尔运算所包含的元素运算的元素只有两个1 (TRUE, 真) 和 0。直到 1938 年Shanon在他的硕士论文中指出用布尔代数来实现开关电路,才使得布尔代数成为数字电路的基础。所有的数学和逻辑运算,加、减、乘、除、乘方、开方等等,全部能转换成二值的布尔运算。

早期的文献检索查询系统大多基于数据库,严格要求查询语句符合布尔运算。今天的搜索引擎相比之下要聪明的多,它自动把用户的查询语句转换成布尔运算的算式。当然在查询时,不能将每篇文献扫描一遍,来看看它是否满足上面三个条件,因此需要建立一个索引。

因此,整个索引就变得非常之大,以至于不可能用一台计算机存下。大家普遍的做法是根据网页的序号将索引分成很多份(Shards),分别存储在不同的服务器中。每当接受一个查询时,这个查询就被分送到许许多多服务器中,这些服务器 同时并行处理用户请求,并把结果送到主服务器进行合并处理,最后将结果返回给用户。不管索引如何复杂,查找的基本操作仍然是布尔运算。

布尔运算把逻辑和数学联系起来了。它的最大好处是容易实现和速度快,这对于海量信息查找非常关键。

不足是只能给出是与否的判断,而不能给出量化的度量。因此所有搜索引擎在内部检索完毕后,都要对符合要求的网页根据相关性排序,然后才返回给用户。

2805#数学之美-图论

离散数学是当代数学的一个重要分支,也是计算机科学的数学基础。它包括数理逻辑、集合论、图论和近世代数四个分支,数理逻辑便基于布尔运算。简历搜索引擎的引索主要依靠图论中的遍历算法(Traverse),图论的起源可追溯到数学家欧拉。

关于图的算法有很多,但最重要的是图的遍历算法,也就是如何通过弧访问图的各个节点。

此处介绍了两种图的算法,以地图绘制为例,为了达到通过弧访问图的每个节点,可以分为:“广度优先算法”(BFS),尽可能广地访问每个节点所直接连接的其他节点;
”深度优先算法”(DFS),因为它是一条路走到黑。

图论的遍历算法可以理解为,互联网是一张大地图,每个网页是一个节点,超链接是连接他们的弧。浏览器是通过这些隐含的网址转到相应的网页中的。这些隐含在文字背后的网址称为”超链接"。有了超链接,我们可以从任何一个网页出发,用图的遍历算法,自动地访问到每一个网页并把它们存起来。完成这个功能的程序叫做网络爬虫,或者在一些文献中称为"机器人" (Robot)。

在网络爬虫中,我们使用一个称为"哈希表"(Hash Table)的列表而不是一个记事本纪录网页是否下载过的信息。因此,一个商业的网络爬虫需要有成千上万个服务器,并且由快速网络连接起来。如何建立这样复杂的网络系统,如何协调这些服务器的任务,就是网络设计和程序设计的艺术了。

在计算机中一个好的算法,应该向阿卡 47 冲锋枪那样简单、有效、可靠性好而且容易读懂(或者说易操作),而不应该是故弄玄虚。Google 工程师Amit Singhal就是为 Google 设计阿卡 47 冲锋枪的人,在公司内部,Google 的排序算法便是以他的名字命名的。Singhal早年是从搜索大师Salton,毕业后就职于AT&T 实验室,并在这里确立了他在学术界的地位。

2806#数学之美-余弦定理与新闻分类

余弦定理和新闻的分类似乎是两件八杆子打不着的事。但是它们确有紧密的联系。具体说,新闻的分类很大程度上依靠余弦定理。Google 的新闻是自动分类和整理的。所谓新闻的分类无非是要把相似的新闻放到一类中。计算机其实读不懂新闻,它只能快速计算。这就要求我们设计一个算法来算出任意两篇新闻的相似性。为了做到这一点,我们需要想办法用一组数字来描述一篇新闻。

向量代数中,向量实际上是多维空间中有方向的线段,如果两个向量的方向一致(夹角为0)那么这两个向量就相近。确定两向量是否一致,就用到余弦定理计算向量夹角了。

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

产生信息指纹的关键算法是伪随机数产生器算法prng,最早的prng算法是由冯诺伊曼提出来的。他的办法很简单,即将一个数的平方掐头去尾,取中间的几位数。e.g. 一个四位的二进制数 1001(相当于十进制的9),其平方为 01010001 (十进制的 81)掐头去尾剩下中间的四位 0100。当然这种方法产生的数字并不很随机,也就是说两个不同信息很有可能有同一指纹。
信息指纹的用途远不止网址的消重,信息指纹的的孪生兄弟是密码。信息指纹的一个特征是其不可逆性, 也就是说,无法根据信息指纹推出原有信息,这种性质正是网络加密传输所需要的。值得一提的事,SHA1以前被认为是没有漏洞的,现在已经被中国的王小云教授证明存在漏洞。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 211,639评论 6 492
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 90,277评论 3 385
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 157,221评论 0 348
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 56,474评论 1 283
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 65,570评论 6 386
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,816评论 1 290
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,957评论 3 408
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,718评论 0 266
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,176评论 1 303
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,511评论 2 327
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,646评论 1 340
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,322评论 4 330
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,934评论 3 313
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,755评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,987评论 1 266
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 46,358评论 2 360
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 43,514评论 2 348

推荐阅读更多精彩内容

  • 很早之前看了几篇博文,只留下模糊印象 。这次是在学习人工智能的基础知识后再看,其中研究自然语言的方法从基于规则转变...
    轻舟阅读 5,872评论 0 9
  • 第一章 文字和语言vs数字和信息### 数字、文字和自然语言一样,都是信息的载体。语言和数学的产生都是为了同一个...
    luckstarjianshu阅读 2,718评论 0 0
  • 1.1 统计语言模型 香农(Claude Shannon)就提出了用数学的办法处理自然语言。首先成功利用数学方法解...
    wzz阅读 1,936评论 0 10
  • 写在之前 如需转载,请注明出处。如有侵权或者其他问题,烦请告知。 第1章文字和语言 vs 数字和信息 文字和语言与...
    hainingwyx阅读 1,142评论 0 2
  • 数学常常给人一种深奥和复杂的感觉,但它的本质常常是简单而直接的。美德就如同华贵的宝石,在朴素的衬托下最显华丽。数学...
    张聪_2048阅读 707评论 0 1