一种基于生语料的无监督的语法规则学习方法

    【译者注：自然语言理解绝不是一种单纯的数学游戏，也不是单纯的语言哲学所描述的体系，因此，过分地讨论算法和语言教条都不是有前途的道路。自然语言理解是介于信息积累和语言教条综合执行的过程，因此，未来的方向也许主要停留在关注语言学习的研究方法上。
本文正是利用信息统计的手段解决传统规则学习的一种有价值的探索。因此，译者深受启发，便连夜翻译出来，希望该文也能成为大家的一盏灯。由于译者英语水平有限，加上专业知识不足，翻译必有错谬之处，请各位道友争相指正。
本文原地址：kybele.psych.cornell.edu/~edelman/adios-nips-workshop.pdf】
Shimon Edelman                        Zach Solan, David Horn, Eytan Ruppin
Department of Psychology                           Sackler Faculty of Exact Sciences
Cornell University                                        Tel Aviv University
Ithaca, NY 14853, USA                               Tel Aviv, Israel 69978
se37@cornell.edu                                        {frsolan,horn,rupping}@post.tau.ac.il
摘要 

我们将自己开发的无监督语言学习模型ADIOS [1]，与计算语言学和语法理论的最新工作做了一下比较。我们的方法，就一般原理来看，类似于结构语法（比如，依赖于结构生成方式，但不又像当前生成理论由词汇反映语法知识那样），而就计算特性来看，系统又类似于语法树链接方法（比如，明显具有上下文相关特性)。我们的算法学习到的表达式完全源于语料数据（无标注），而现有关于认知和结构语法以及TAGs的文献中，这些都是由人工来制定的。因而，我们的成果完善并延伸了计算学、尤其是语言学在语言学习方面的研究。该研究也表明了语言的经验化和形式化研究也可以得到有效的结合。

1 利用去冗余的方式进行无监督学习

去冗余是无监督学习的一般方法（也是目前可行的唯一方法）[2, 3]。书面语信息（或者翻录语音）相对于所用词典信息，多少是有些冗余的。因而，该特性能够让一个省略空格的文本语料的词语得以自动还原，这主要通过每个字母的信息熵最小化方法[4]。

信息熵最小化方法也会遇到一种尴尬的情况，那就是基础词串接连嵌入更长的基础序列，这导致推导而得的表达式不可以用于新文本的处理（即，不具有生成能力；cf. [5], p.188）。据我们观察，由于不同句子会有同样的词语序列，就是基于词的表达式的信息仍然是相当冗余的。这样的词语序列并不一定是完全紧密相邻的；事实上，经典语言分布理论[6]以及现代NLP方法[7]中，也需要针对一系列完全对齐序列中（语段）的可变槽语段的分析技术。模式—一截语段和一些等价类（补充型分布符号）可以出现在可变槽中—是我们的系统ADIOS（Automatic DIstillation Of Structure) [1]的主要表达形式。

我们的目标是，在统计和形式方法[9]之间建立起桥梁，通过上下文无监督自动结构学习，解决当前计算语言学中所涉及的语法习取问题，并将之与某些形式语法理论建立起联系。第2节概要描述了ADIOS 模型所采用的主要计算原理（算法细节和实验结果，参见[1, 10]）。第3、4节分别从计算语言学和形式语言学的角度比较我们的模型。最后在第5节讨论了未来的挑战。

2 ADIOS的原理

ADIOS的表达能力和它的无监督学习能力依赖于3个基础： (1) 模式价值的概率推导， (2) 基于上下文的生成，以及 (3) 递归构造更复杂的模式。下面对这3个基础作以简要的描述。

图1： (a) 一个由简单语料形成的多叉有向图， 共有4个句子，句子部分拧成线束，了一个模式：is that a {dog, cat, horse} ?。 (b) 抽取的模式及其等价类被高亮显示(虽属于序列但不被模式覆盖的边没有改动，如#104)。 (c) 新的有价值的模式使用了已经学习到的等价类(如#200)。详细内容见[1]。

模式价值的概率推导。ADIOS 将语料的句子表示成高度冗余的有向图，该图可想像成一团线，其中许多线在一些部分可能拧成线束(Figure 1)。一个线束的形成开始于两个或者更多的线在某处纠结一起，再平行一段距离，然后在离开的线多于继续下来的线时就结束了。

图2：动态决定线束的核心。主要思想是决定同一个线束上两个元素ei 和 ej的归属关系，这根据向前和向后沿着线束路径计算ei到ej的概率： 要成为候选线束的新元素，只要它的加入会引起相应的PR和PL增大，就可以保留下来(如，P(A) < P(B|A) < P(C|AB) < P(D|ABC) > P(E|ABCD)，因此，线束结束于D节点)。 在图中，相关的一些概率是很容易计算的：比如，P(C|AB) = 3/4 ，因为有4条路线经过A和B，而其中只有3条路线继续经过C。

对于特定的语料，可能有许多线束，每一根线（句子）都可能参与某几个。面对的计算挑战是如何识别有价值的线束，以便平衡高压缩率（表示线束“词汇”的数量）和高质量的生成能力（拼接不同线束中片段而产生新句子的能力）。解决该问题的直观图示见图2。

基于上下文的生成。 一个模式就是一束句子的概要描述，这些句子完全相同，除了在某个地方有变化(Figure 3)，变化位置可为几个符号之一—对应于该模式的等价类的成员。因为该变化能力受限于该模式所在的上下文中，因此，模式之间的生成能力，相对于那些用范畴（词性）和规则（语法）进行全局校验的方法而言，显然更加保守一些。基于上下文的模式的ADIOS，不同于传统的规则，它的可靠性既能看作结构语法（后面论述），又能看作Langacker([11], p.46)的结论：“从大量特定演讲者的言语中尽可能提取全部一般化模式，其大部分是有限范围的，而且一些形式根本不能被一般模式所同化。从这种角度看，这时并不希望有完全的一般化规则，相反，需要一个包含一些生成程度较弱的特殊形式和模式的连续体系”。

图3：从一部分CHILDES语料 [8]提取的两个典型模式。 上百个这样的模式和等价类（带下划线）一起构成了原始数据的压缩表示。 通过这些模式能够描述或生成的短语有：let’s change her...; I thought you gonna change her...; I was going to go to the...; 这些无一个出现在训练语料中，这表明了ADIOS的生成能力。 在左边显示了具体的生成过程，即深度优先搜索一个模式所示的树。细节见[1]。

递归构造复杂模式。 通过两个相关机制，ADIOS实现了长距离的相关性：模式的层级嵌套和自我复用的模式递归。每当一个新的有价值的模式被发现，ADIOS的基本数据结构图将重新布线，以便模式所覆盖的线束用一根新弧线来表示；这种重布线是基于上下文的，就像模式本身应该归属所在位置一样[1]。 一旦重新布线，那些可能跨越新提取线束的潜在远距离符号，就变成了邻居。因而，模式形成了层次结构，因为他们的成分要么是终端（即，完全特定字符串），要么是其他模式。更重要是，模式可以引用自身，这一点意味着实现了真正的递归(实际上，不限於实施条件的话，递归的深度只取决于可多次后继布线的数据)。

3 有关计算方法

自然语言处理 (NLP)有两类无监督学习方法，一类是企图寻找好的结构化原词集，一类是对预定义原词集寻找好的参数设置。很明显ADIOS属于第一类。更重要的是，我们的算法能够直接学习生语料，而大部分的其他系统要利用词性标注语料，或者语法树库（人工句法分析库[13]）。在此我们比较几个这样的方法。

利用标注语料全局语法优化。 Stolcke 和 Omohundro [14]在给定语料下，通过不断扩大靠近目标语法的概率，学习结构（隐马模型的结构，或者随机的上下文无关语法）。 该方法在每次迭代时，所有语料均要参与特征学习，因此，它是全局计算的，与此方法相比， ADIOS 是局部的，因为它的推导仅仅作用于当前线束。 另一个重要差别是，不用词性所表示的一般范畴规则，我们寻找的是上下文相关的模式。也许正因为它的全局性和语境不受限的规则， Stolcke和Omohundro的方法很难适用于大规模自然语言应用[14]。Clark也得出过类似结论，他认为词性标记不足以学习语法（“大量语法都有特殊词语的特质”[15], p.36）。Clark的算法[16]企图从标注文本中学习基于短语结构的语法，该方法开始利用局部的分布信息，然后利用互信息指标过滤掉不正确的非终端（即，在模式的前缀和后缀之间要求较高的互信息值）。最后，他的算法对结果聚类，以便获取最短描述长度(MDL)的表示，选取过程如下：从最长似然语法开始，然后贪婪地选择那些会最大程度减少描述长度的截段。在贪婪的优化方法上（但不在局部搜索好的模式，也不能处理无标注的语料数据），我们的方法类似于Clark的算法。

基于树库的概率学习。 Bod的算法从复合树上搜集语料概率信息，他说道：“[. . . ]讲话人和听话人之间传递的知识不能被理解为一种语法机制，而是基于语言经验的统计总和，每次感知和生成新的言语时，这些统计总和均有所变化。在语言上我们所遵循的规律可以看作一种突生现象，但他们不能归纳进某种一致的非冗余的系统，那种系统能直接就可以明确定义出这些新生言语的结构([13], p.145)。因此，它的基于记忆和模拟的语言模型并不是典型的去冗余的无监督学习；我们在此提到它，主要因为它采用了类似的数据表示结构（随机树置换语法[17]）和第4节要讨论的一些形式内容。

模式学习的分裂和聚合。 由Wolff开发的无监督学习算法的优点是不需要标注数据。在1988年的一节篇章中，描述了它的系统[5]，Wolff进行了早期无监督的语言或一些相关行为数据学习的探索。他的表示的组成元素有：SYN (结构语段), PAR (实例聚合体) 和 M (终端符号)。尽管我们的模式和等价类类似于前两者，但是，Wolff的学习规范比ADIOS要简单一些：每次迭代时，两个最频繁出现的邻近SYN元素就连接在一起。但是，该系统有一个唯一的保证，阻止无监督学习算法通常有的过生成问题：不允许PAR元素在一定上下文中各个成员间自由替换，总是需要根据特定上下文来重构。很遗憾，由于实施原因，Wolff的系统没有在非受限自然语言中做过测试。

4 有关语言学的方法

我们的工作是数据驱动型，而不是理论驱动型，因为我们对系统要生成的规则类型不做预先假设 (参见第2节关于Langacker [11]的引述)。 很明显，ADIOS学习得到的具有递归层次和参数化的模式及其它们在新句子的处理和生成方式上，很像一些广泛研究的结构语法形式的特征。ADIOS与这些形式结构之间的异同在本节后面有简略讨论。我们在那些主要由语言心理学为基础的方法（认知语法和结构语法）与那些以纯计算为基础的方法（局部和树链接语法）之间做一些比较。

认知语法。ADIOS的主要方法原则 — 将具有不同复杂性的词汇单元组织起来，而且在学习和表示上，使用了一般的认知原理—完全基于Langacker [11]所制定的认知语法的。认知语法一般企图人工制作结构，那将反映他们所认为的语言逻辑，而ADIOS 是通过经验而不是照搬他们的方法来发现语言的原词。

结构语法。 ADIOS 和各种结构语法[18, 19]有许多相似性 (尽管后者是人工制作的)。结构语法是有许多元素组成，各元素之间在复杂性和特有的自由度是不同的：比如，习语“big deal”是一个完全实例化而不可改变的结构，而 表达式“the X, the Y” (比如“the more，the better”；参见 [20]) 是部分实例化的模板。ADIOS 学习到的模式，也会随着复杂性和实例化程度的差异而不同(比如，不是每一个模式都有等价类)。更重要的是， 我们怀疑这些模式抓住了大量句子的语义信息，就像结构被用于以一种适合于语言的结构限制的形式表达信息概念或语义内容的媒介一样。这种论断的正确评估需要出现一种新的语义理论，可以处理自然语言的所有复杂性—当前形式理论[21]尚不具备这点。我们赞同Jackendoff的立场：“[. . . ] 我们显然拒绝概念结构[. . . ]意味着一切。相反，我们宁愿说他们意味着：他们只是在意义上做了应该做的事情，比如推导和判断。” ([22], p.306)。

树链接语法。在捕获语言内在的规则性，在语料中的多交叉路径上，ADIOS 更像Gross[23]的有限状态局部语法方法。但是，要注意的是，我们基于模式的表达式有类似的两种操作：置换和连接，这就是树链接语法的特征，或者是由Joshi [25]等人开发的TAG的特征。尤其，置换和连接表现在ADIOS的模式之间的关系上：比如，一个模式成为另一个模式的组成部分（参见第2节）。一个模式Pi 和它的等价类 E(Pi)；任何其他的模式 Pj属于 E(Pi) ，能看作Pi的可替换部分。同样，如果Pj 属于 E(Pi)，Pk属于E(Pi) 并且 Pk 属于E(Pj)，那么， 模式Pj 可以与模式Pi连接。由于在TAG操作和ADIOS模式之间存在对应关系，我们相信，后者更能表示弱上下文形式语言所描述的规则性[25]。此外， ADIOS模式从数据学习而来，他们已经将约束条件融进了置换和连接操作中，而这些在旧的TAG框架中却需要人工制定。

5 前景与挑战

将我们无监督的学习方法(对于一些生语料数据，比如转录的儿童语言，进行学习展示了较大的前景[1])与最近一些计算语言学和语法理论的工作做了些比较。ADIOS关于语言知识表示的方法类似于结构语法(如，结构生成而不是词汇语法), 和树邻接语法(如，明显接受弱上下文语言)。ADIOS的表示完全来自于无标注语料数据，而当前公开的认知和结构语法以及TAG都是人工制定的。因而，我们的成果完善并延伸了计算学、尤其是语言学在认知/结构语法方面的研究。

要进一步推动完整的语言理解，还将面对一项关键挑战：开发一种评估无监督语言学习系统效能的可行方法，既可以测试 (1) 关于语言法则的中性特征，和 (2)过去半个世纪以来语言学家们总结的大量的认知现象。

从生语料进行无监督语法推导很难测试，因为任何供测试用的“可靠标准”的表达式(比如 Penn Treebank [26])，不可避免带有设计者的语言偏见，这可能并不是合理的，而且在语言学家自身[16]之间也会存在冲突。正如Wolff 所述，一个儿童“. . . 必须从语言例子中概括，但不能过度概括到语言中不存在的言语范围。奇怪的是两种概括就儿童的经验来看都为0频次。”  ([5], p.183, italics in the original)。 暂不将解释的责任归于尚不明朗的进化过程 (即先天语法假设)，我们建议，一个像ADIOS的系统应该这样被测试，让系统接受大量人工生成的数据，观测其效果，同时，也让人来评估系统生成的句子 (注意，语言心理学在此过程中起到关键作用)。

这样纯经验评估的方法，会浪费对语言学家几十年来所搜集的大量宝贵的语言规律的考察机会。尽管一些经验主义者会视之为一种公平的代价，可以隔离他们感觉到的超出心理和计算现实的失控理论，但是，我们相信应该能寻找一个中间方法，并且也能够找到，只要语言学家能够被说服去以一种非纯理论的方式尝试和呈现他们的主要发现成果。从最近的语法评述来看，语法趋向于语言学家之外 (如[27])，每个语言学习系统的设计者都关注的核心问题好像是相关性(如，互引用)和相关性条件(如，孤点条件)，尤其在多语类型比较（跨语言）方面更明显[19]。

致谢。本项目由US-Israel 两国科学基金赞助。

参考文献

[1] Z. Solan, E. Ruppin, D. Horn, and S. Edelman. Automatic acquisition and efficient representation of syntactic structures. In S. Thrun, editor, Advances in Neural Information Processing, volume 15, Cambridge, MA, 2003. MIT Press.

[2] H. B. Barlow.

Sensory mechanisms, the 去冗余, and intelligence. In The

mechanisation of thought processes, pages 535–539. H.M.S.O., London, 1959.

[3] H. B. Barlow. What is the computational goal of the neocortex? In C. Koch and J. L. Davis, editors,

Large-scale neuronal theories of the brain, chapter 1, pages 1–22. MIT Press, Cambridge,

MA, 1994.

[4] N. Redlich. Redundancy reduction as a strategy for unsupervised learning.

Neural Computation,

5:289–304, 1993.

[5] J. G. Wolff. Learning syntax and meanings through optimization and distributional analysis. In

Y. Levy, I. M. Schlesinger, and M. D. S. Braine, editors, Categories and Processes in Language

Acquisition, pages 179–215. Lawrence Erlbaum, Hillsdale, NJ, 1988.

[6] Z. S. Harris. Distributional structure. Word, 10:140–162, 1954.

[7] M. van Zaanen. ABL: Alignment-Based Learning. In COLING 2000 -Proceedings of the 18th

International Conference on Computational Linguistics, pages 961–967, 2000.

[8] B. MacWhinney and C. Snow.

The Child Language Exchange System. Journal of Computational

Lingustics, 12:271–296, 1985.

[9] F. Pereira. Formal grammar and information theory: Together again?

Philosophical Transactions

of the Royal Society, 358(1769):1239–1253, 2000.

[10] Z. Solan, E. Ruppin, D. Horn, and S. Edelman. Unsupervised efficient learning and representation

of language structure. In R. Alterman and D. Kirsh, editors, Proc. 25th Conference of the

Cognitive Science Society, Hillsdale, NJ, 2003. Erlbaum. in press.

[11] R. W. Langacker. Foundations of cognitive grammar, volume I: theoretical prerequisites. Stanford

University Press, Stanford, CA, 1987.

[12] D. Klein and C. D. Manning. Natural language grammar induction using a constituent-context

model. In T. G. Dietterich, S. Becker, and Z. Ghahramani, editors, Advances in Neural Information

Processing Systems 14, Cambridge, MA, 2002. MIT Press.

[13] R. Bod. Beyond grammar: an experience-based theory of language. CSLI Publications, Stanford,

US, 1998.

[14] A. Stolcke and S. Omohundro. Inducing probabilistic grammars by Bayesian model merging.

In R. C. Carrasco and J. Oncina, editors, Grammatical Inference and Applications, pages 106–

118. Springer, 1994.

[15] A. Clark.

Unsupervised Language Acquisition: Theory and Practice. PhD thesis, COGS,

University of Sussex, 2001.

[16] A. Clark. Unsupervised induction of Stochastic Context-Free Grammars using distributional

clustering. In Proceedings of CoNLL 2001, Toulouse, 2001.

[17] R. Scha, R. Bod, and K. Sima’an. A memory-based model of syntactic analysis: data-oriented

parsing. J. of Experimental and Theoretical Artificial Intelligence, 11:409–440, 1999.

[18] A. E. Goldberg. Constructions: a new theoretical approach to language.

Trends in Cognitive

Sciences, 7:219–224, 2003.

[19] W. Croft. Radical Construction Grammar: syntactic theory in typological perspective. Oxford

University Press, Oxford, 2001.

[20] P. Kay and C. J. Fillmore. Grammatical constructions and linguistic generalizations: the What’s

X Doing Y? construction. Language, 75:1–33, 1999.

[21] P. M. Pietroski. The character of natural language semantics. In A. Barber, editor, Epistemology

of Language. Oxford University Press, Oxford, UK, 2003. to appear.

[22] R. Jackendoff. Foundations of language. Oxford University Press, Oxford, 2002.

[23] M. Gross. The construction of local grammars. In E. Roche and Y. Schab`es, editors, Finite-

State Language Processing, pages 329–354. MIT Press, Cambridge, MA, 1997.

[24] M. M¨uhlmann. Variable Length Markov Chains: Methodology, computing and

achler and P. B¨

software. Seminar for Statistics Report 104, ETH Z¨urich, 2002.

[25] A. Joshi and Y. Schabes. Tree-Adjoining Grammars. In G. Rozenberg and A. Salomaa, editors,

Handbook of Formal Languages, volume 3, pages 69 – 124. Springer, Berlin, 1997.

[26] M. P. Marcus, B. Santorini, and M. A. Marcinkiewicz. Building a large annotated corpus of

English: The Penn Treebank. Computational Linguistics, 19(2):313–330, 1994.

[27] C. Phillips. Syntax. In L. Nadel, editor, Encyclopedia of Cognitive Science, volume 4, pages

319–329. Macmillan, London, 2003.