《镜子大全》《朝华午拾》分享 http://blog.sciencenet.cn/u/liwei999 曾任红小兵,插队修地球,1991年去国离乡,不知行止。

博文

【科研笔记:NLP “毛毛虫” 笔记,从一维到二维】 精选

已有 2987 次阅读 2016-4-19 00:00 |个人分类:立委科普|系统分类:科研笔记|关键词:formalism,FSA,乔姆斯基,形式语言,文法| 形式语言, FSA, 乔姆斯基, 文法, formalism

根据乔姆斯基的形式语言理论,无论对象是计算机语言还是自然语言,其语言分析(parsing)的文法需要一个形式系统工具(formalism)表达。这个体系是层级(hierarchical乔姆斯基谱系_百度百科)的,对于语言分析的表现力因此强弱不同,所对应的算法及其自动机也因此具有不同的计算复杂度。这些都是经典到不能再经典的老生常谈了,细节可以看wiki百科或编译理论的教科书。

自然语言parsing中讨论最多的formalisms 是 FSA和CFG,传统的观点虽然足够权威,但大多不得要领。其说法是,FSA 有线性高效算法,用起来也直观(模式匹配而已),但表达力不够。乔姆斯基本人批评说它不适合做自然语言分析,因为FSA从原理上不能涵盖据说是自然语言本性的中心递归(center recursion)结构:这是个似是而非的论点,我们在乔姆斯基批判等博文(见文后《相关》链接)中已经多次论及,这里不再重复。CFG 是传统的短语结构文法派使用最多的工具,由于可以应对递归而倍受青睐,但没有线性实现的算法。白老师根据多年的观察,第一次提出,适合自然语言分析的formalism很可能是个穿越乔姆斯基层级体系内部边界(白老师形象地称作“乔家大院”)的“毛毛虫”。

这是令人耳目一新的新鲜观点,与我几十年的NLP实践体验非常吻合。我把这条我们从导师辈传承火种并坚持摸索30年的毛毛虫叫做 FSA++,因为毛毛虫的基础仍是 FSA但有很多扩展突破。其算法始终没有超出线速的要求,对应的文法也不是单层的大一统,而是很多个小文法叠加(cascade)成一个多层处理的pipeline,可以做到任意层面的分析深度。自然语言 parsing 因此而变得前所未有地灵活和深入。应对自然语言里的递归现象也因此易如反掌。

这是一个自然语言领域的极为重要的议题,可惜的是学术界的统计一面倒使得相关研究和讨论几乎绝迹。

本篇笔记就是一些零星的心得笔记,是多年实践的初步总结,记下来与白老师及同仁分享。NLP后学看不懂没关系,因为教科书和学术论文中少见这一类训练和讨论。不是你的错,and you are not alone,看个热闹或无视可矣。

有一个新发现,关于“毛毛虫”的。其实也不新,只是先前可能熟视无睹,没特别注意这个特点。

在线性模式匹配的 fsa++ 里面,多层的所谓 cascaded 的处理是必要的。因为有些匹配与另外的匹配有某种线性相交,如果同一层处理,往往不可兼得。顾了这头,顾不了那头。

到了 dag(directed acyclic graph)式依存句法树为基础的平面 fsa++,当然仍然可以或应该根据模块化原则分层处理,包括parsing的“休眠唤醒”。 但是对层次是依赖却由于模式的不同减弱了。完全可以在同一层做n个有相交的子树模式匹配。每个模式是从不同角度来的子树规则,各自对付不同的子现象。

无论线性还是平面,编码规则有个minimal nodes 的原则,即规则最小化。最小(必要)还足够(充分)才是好规则,好的语言学概括。只有规则最小化,才可以有效预防规则量的线性组合爆炸,增强parsing的鲁棒性,也增强对现象的覆盖(差全率 recall)

最小化原则针对规则的个体,是对规则码农而言。与其相对应,规则整体(规则集,or 文法)在编译后执行(running)的时候,则是遵循最大原则,来保证规则之间的优先次序。对于线性模式,就是 longest matching principle(另一个线性原则是,left-to-right principle or right-to-left principle,算是人为规定的 config,根据每一层模块的匹配方向而定。)这些都是清楚明白的,但是到了二维世界,匹配原则就有些模糊了。

Longest principle 的对应物如果是 embedded patterns,当然就是大树吃小树,这个没有疑问,也符合逻辑。但更多的时候其实不是完全的 properly embedded,而是某种相交。这时候,如果毛毛虫的创造者硬性规定某个 quasi-longest principle 也是可以的,譬如相交的一端,比另一端多 n 个节点,超过阈值了,就算它赢。这样做似乎也可能带来一些好处,因为旗鼓相当自然可以算匹配双赢(只要结论不造成逻辑冲突),但是一头沉的情形似乎应该是东风压倒西风才合理。

但实际上,这个火候似乎不好掌握,不妨考虑放开,后果自负,由语言学家自己根据数据制导掌控,而不是从毛毛虫内部控制。当然也有其他的 priority 掌控方式可以实施,此处不细谈。

总结一下,一维毛毛虫成长为二维毛毛虫以后,规则执行层面的制约减弱了,使得规则的适用度增强了。减弱的第一条是,平面世界没有线性左右的区别,因此 left to right 的原则不再适用(入口 node 的原则还可以有很多说法或 config,此处不提)。减弱的第二条就是,longest principle 只遮盖很少的 proper 子树的情况。

这个转变带来的好处就是,结构层面的规则在最小化以后,可以全面开花地同时作用于数据结构,实施休眠唤醒,减叶加枝,parsing patching 或 IE 抽取等工作。

其副作用还有待更多的实践和总结。


【相关】


[转载]【白硕 - 穿越乔家大院寻找“毛毛虫”】

【泥沙龙笔记:NLP 专门语言是规则系统的斧头】


 乔姆斯基批判

乔姆斯基谱系_百度百科

 语言创造简史

智元:理论家的围墙和工程师的私货】 


【新智元笔记:李白对话录 - RNN 与语言学算法】

【立委科普:结构歧义的休眠唤醒演义】



【置顶:立委科学网博客NLP博文一览(定期更新版)】 


 《朝华午拾》总目录







http://blog.sciencenet.cn/blog-362400-971043.html

上一篇:《新智元笔记:机器的秒杀人类与霍金的杞人忧天》
下一篇:【泥沙龙笔记:NLP 专门语言是规则系统的斧头】

2 谢平 bridgeneer

该博文允许注册用户评论 请点击登录 评论 (1 个评论)

数据加载中...

Archiver|手机版|科学网 ( 京ICP备14006957 )

GMT+8, 2018-12-16 09:52

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部