HG has no computational advantages over OT: consequences for the theory of OT online algorithms
HG has no computational advantages over OT: consequences for the theory of OT online algorithms
复制标题
HG 相对 OT 没有计算优势：对 OT 在线算法理论的影响
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Giorgio Magri
中科院分区：
文献类型：
--
作者：
Giorgio Magri
最近，许多作者都认可调和语法（HG）作为最优理论（OT）的替代品。这一举措的一个论据是基于计算方面的考虑：OT 表面上看起来像是一种异国情调的框架，在机器学习中没有相应的框架，而用 HG 替代允许将机器学习的方法和结果导入到计算音系学中；例如，参见 Potts 等人。 (2010)、Pater (2009)、Hayes 和 Wilson (2008)、Coetzee 和 Pater (2008)、Boersma 和 Pater (2007, 2008)、Jesney 和 Tessier (2007, 2008) 等。本文表明，这种支持 HG 并反对 OT 的论点是错误的：我证明了一个简单、普遍的结果，即 HG 的算法可以相当简单地适应 OT。因此，HG 相对于 OT 没有计算优势。这个简单的结果对计算 OT 具有深远的影响，因为它允许将机器学习的经典方法和技术导入到计算 OT 中。我通过展示这种新的计算 OT 方法的丰硕成果，展示了它为 OT 在线算法理论带来了实质性进展。特别是，我展示了它基于经典感知器算法的收敛性，为 Boersma（1997）（非随机）渐进学习算法的一个微小变体提供了收敛证明。
Various authors have recently endorsed Harmonic Grammar (HG) as a replacement of Optimality Theory (OT). One argument for this move is based on computational considerations: OT looks prima facie like an exotic framework with no correspondent in Machine Learning, and the replacement with HG allows methods and results form Machine Learning to be imported within Computational Phonology; see for instance Potts et al. (2010), Pater (2009), Hayes and Wilson (2008), Coetzee and Pater (2008), Boersma and Pater (2007, 2008), Jesney and Tessier (2007, 2008), among others. This paper shows that this argument in favor of HG and against OT is wrong: I prove a simple, general result that says that algorithms for HG can be rather trivially adapted to OT. Thus, HG has no computational advantages over OT. This simple result has far reaching implications for Computational OT, as it allows classical methods and techniques from Machine Learning to be imported within Computational OT. I illustrate the fruitfulness of this new approach to Computational OT by showing that it leads to substantial progress in the theory of online algorithms for OT. In particular, I show that it leads to a convergence proof for a slight variant of Boersma’s (1997) (non-stochastic) Gradual Learning Algorithm, based on convergence for the classical Perceptron Algorithm.