【转】浅谈自然语言处理 – 早期机器翻译

浅谈自然语言处理 – 早期机器翻译
知乎作者：李嘉铭
“Siri，零除以零是多少？”“假如你有0块饼干，要分给0个朋友，每个人能分到几块？你看，这个问题没有任何意义吧？甜饼怪会难过，因为没有饼干吃，而你也会难过，因为你一个朋友都没有。”
自然语言处理简史 – 早期机器翻译
上次我们聊到19世纪40年代到60年代之间自然语言处理研究的创立，以及初期遇到的一些困难。在美国政府决定停止给自然语言处理研究提供资金之后，在其他国家中研究仍在继续。根据《机器翻译史》中提到的，加拿大率先研发了METEO System用于翻译天气预报。它支持英语和法语之间的互译，在1980年正式被启用并且抢了初级翻译员的饭碗。无独有偶，Systran公司在1968年创立并研发了用于欧洲语言之间互相翻译的软件，它的软件在70年代首次被包括NATO，国际核能组织，以及通用汽车公司等所使用。
如果你还记得上次的聊天软件ELIZA，你可能会觉得这么短时间内绝对不可能出现机器翻译软件。METEO System和Systran是如何做到的？难道美国政府严重高估了自然语言处理的难度？为了回答这些问题，我们首先得了解早期机器翻译系统是如何运作的。
三步实现机器翻译
早期机器翻译系统通常是一句一句翻译的（现在大部分翻译软件仍然如此），对于每一句句子，它分为三个步骤：
从句子中提取语法信息。
按照目标语言把语法结构进行重新排列。
把每个词从源语言翻译成目标语言。

这个简单翻译系统受到了会双语的翻译者们的启发，它会在之后的自然语言系统中不断的重复出现，所以我们需要一步一步仔细理解它。
假设我们受雇于加拿大政府，帮助他们翻译天气预告，我们要把如下的一句句子翻译为法文：“蒙特利尔的天气是多云。”我不懂法文，而且我也并不精通翻译，所以我得慢慢来。我手上有如下一些东西：中法词典一本、初级语法书一本、还有稍微懂一些法语的我的朋友小明。
从句子中提取语法信息
词性
首先我得搞清楚每一个词的词性，词性的划分是根据词在句子中所起到的语法作用而来的，一般有名词、动词、形容词之类的。我在词典里找到“蒙特利尔”，它是个名词，我把名词标上之后继续去找下一个词“的”的词性。很快我就把整句句子里的词性全标记上了：“蒙特利尔/名词 的/助词 天气/名词 是/动词 多云/形容词 。/。”
语法分析树
我所需要的下一样东西是这句句子的语法分析树，或者简称分析树。顾名思义，语法分析树是把文本按照语法拆分成树状结构的结果。要简单的理解分析树的话，可以先从数学公式开始，因为数学公式的语法其实比自然语言的语法简单的多。比如我们要计算x + y * z，我们得先算乘法再算加法，而分析树的作用就是写清楚：是先乘法还是先加法。同样，在自然语言中分析树的作用就是写清楚形容词描述的到底是哪个名词，以及句子的主语是哪个之类的。
左边的是x + y * z正确的分析树，右边的则是(x + y) * z的分析树。**

回到我们刚刚的例子“蒙特利尔的天气是多云。”，我知道“蒙特利尔”和“的”应该组合在一起，因为根据语法书上的说法，名词 + 助词=>名词助词短语，我还知道“是多云”应该组合在一起，因为动词 + 形容词 => 动词短语。以此类推，组合到最后的结果是：名词短语 + 动词短语 + 。 => 完整的句子!正式的语法树长得如下：（如果看不懂那些词性的英文简写没关系，都是语言学的术语，大部分我也看不懂，感兴趣的话这里有中文的常用词性的列表。）
“蒙特利尔的天气是多云。”的语法分析树

按照目标语言把语法结构进行重新排列
我现在得把分析树转换成法语的句式，于是我问我朋友小明：“这个分析树所对应的句式是什么？”。他看了一眼以后回答：“应该是“（中文无对应词）/冠词 天气/名词 在/助词 蒙特利尔/名词 是/动词 多云/形容词 。/。”，你知道有个东西叫谷歌翻译的对吧？”我不理会他关爱智障一般的眼神，把他给的句式抄了下来。如果你只看词性的话，你会发现基本上它只是把中文的句式结构在某些部分颠倒了一下，其实和英文里的句式差不多。
把每个词从源语言翻译成目标语言
我拿出我的中法词典并且开始查找“天气”和与之相对应的冠词，我找到的是”La météo”。我继续把接下去每一个中文词都找到与之对应的法语词。最后我得到的结果长得像这样：“La/冠词 météo/名词 à/助词 Montréal/名词 est/动词 nuageuse/形容词 ./。”，我把标注的词性去掉之后句子变成了：“La météo à Montréal est nuageuse.”，看上去貌似是对的。
有限状态机和词典
我们刚刚展示了分三步的机器翻译系统是如何运作的，我们还介绍了两个十分重要的语言学概念：词性和分析树。词性告诉我们一个词到底是名词、动词、还是其他什么类型的词，而分析树则用树形结构表示了我们脑中词和词之间的关系。与此同时，在每一个步骤中我们还用到我们手上有额外的一些东西。
第一步里，我们假设手上有能够查询词性的词典，我们之前说到过词可能会有多种词性和意思，然而因为我们只需要翻译一种类型的内容，像是对于METEO System的话，只需要翻译天气预报，因此词的意思和词性一般没有歧义。所以我们才能准确无误的用词典找到正确的词性，并且不用担心需要在多个可能的词性里选择一个，因为一般只有一种可能。
在我们把词性标注完成之后，我们还画出了整个句子的结构树，对于我们人来说，我们直觉上知道哪些词应该组合在一起，因为那样才说得通。然而对于机器来说，他们并没有直觉，而必须依赖规则和逻辑，他们需要一个内在的状态来记录某些关键信息，比如：“我是否看到过一个动词？这句句子是不是少一个宾语？我刚看到一个’the’所以它之后跟的应该是名词。”。如果一个程序拥有内在的状态并且根据一系列的规则和逻辑来改变自己所在的状态的话，我们叫它有限状态机(Finite State Machine)。
能够帮助理解有限状态机最好的例子其实是游戏的AI，我们拿吃豆人来打比方，控制吃豆人里的敌军的有限状态机基本上只有7种状态，敌军通过判断吃豆人有没有吃到强化药剂来判断需要追还是需要逃。”追吃豆人”和“逃离吃豆人”就是两种状态，而“吃豆人吃了强化药剂”是用来改变AI状态的规则，一旦满足了一定的规则，有限状态机就会进入一个新的状态。用于自然语言的有限状态机比吃豆人的AI要复杂许多，但是工作原理还是一样的，每次有限状态机都会从初始状态开始，检查现在满足了哪个规则，并且根据那个规则进入新的一个状态，之后再次检查规则……它会重复这些操作直到进入结束状态。有限状态机在编程中有着广泛的运用，有兴趣的话可以进一步了解一下。
吃豆人AI的有限状态机

回到我们的机器翻译上来，在用有限状态机生成了结构树之后，在第二步中，我们用到了我的朋友小明，小明帮我们把结构树转换成了法语的语法句式。但可怜的机器翻译系统一个朋友都没有，不过它可以用有限状态机来完成这一步。其实这个过程和之前把源语言的句子转换成结构树类似，只是把输入输出颠倒了一下，现在的输入是分析树，而输出的则是目标语言的语法句式，两者之间技术上没啥区别。
最后一步中，我用了中法词典，和我第一步用的词性词典所类似，翻译程序可以轻易的储存并且使用中法词典而不用担心词的意思有歧义。至此，我们把我们所需要的所有资源全都列出来了，而我们的工作也被使用有限状态机和词典的机器翻译软件所取代了。
有限状态机的弊端
如果我们把ELIZA和包括METEO System的机器翻译软件相比较，显然比起之前找关键词的做法，有限状态机的结果好得多，它程序的体积足够小，小到40年前的电脑也能装的下，并且能够胜任局限于某个话题的翻译工作，但是有限状态机有没有任何弊端？为什么我们不能把同一个机器翻译系统用于比天气预报和政府文件更加广的主题上？
有限状态机主要的问题之一在于程序员和研究人员需要帮它写出所有的规则和状态，并且所写的规则和状态的好坏和最终翻译的质量直接相关。如果写的规则过于细化，它只会在一些边边角角的极端情况下被用到，而且程序员需要写更加多的规则才能涵盖所有可能的情况。但如果写的规则过于宽泛，则过于广泛的在错误的情形下使用那些规则会导致翻译系统的错误率升高。即使对于这方面的专家来说，掌握这两者之间的平衡也是一件难事。与此同时，如果你要把一个系统应用于更加广泛的领域上时，随之而来的是更多可能的输入，更多可能的歧义，以及更多需要写的规则和更多的人力。
YouTube截取的AI Bug

在这里，我想再次用电子游戏AI的例子来说明有限状态机的弊端。电子游戏AI需要应对许多复杂的情形，正因为如此它们才会经常有各种各样的bug。我在玩一个RPG游戏的时候，有一次看到一个AI控制的人物突然失去了梦想，不停地撞墙，几秒后会停止一小会儿，然后又开始继续撞墙。以下的图展示了一个写的不好的有限状态机AI是如何造成这种bug的：
有限状态机AI bug示意图

受限制于有限状态机天生的弊端，每一款早期的机器翻译软件只能被用于一个领域，如果我想要翻译天气预报，我可以用软件A，但如果我同时也想翻译其他的东西，比如我想翻译餐厅的菜单，那我不得不用另一个软件B。这个问题困扰着计算机科学家们，其中有些人开始思考如下的问题：“我可不可以让机器为我们生成那些规则？这样我就可以躺在沙发上刷手机而不用去费尽心思工作了。”有趣的是，那些人后来成了机器学习领域的先驱，他们为自然语言处理带来了新的生机。没有他们的努力，现代的自然语言处理也就无从谈起，关于他们的工作，还请听下回分解。
注：文章开始的Siri关于零除以零的对白翻译自英文版Siri，翻译摘自搜狐。正式的说，使用有限状态机的翻译系统被称作增强跃迁网络(Augmented transition network)。
引用
Machine translation: a concise history - John Hutchins
THE METEO SYSTEM
我使用了Stanford Parser用于生成语法分析树，并用了Syntax Tree Generator来生成分析树的图片。我用了gif.com生成了AI bug的视频.
图片来源：吃豆人
数学分析树
甜饼怪