Analysis of Semi-Supervised Learning with the Yarowsky Algorithm
Analysis of Semi-Supervised Learning with the Yarowsky Algorithm
复制标题
DOI：
10.5555/3020488.3020508
复制
发表时间：
2007-07
期刊：
影响因子：
--
通讯作者：
Gholamreza Haffari;Anoop Sarkar
中科院分区：
文献类型：
--
作者：
Gholamreza Haffari;Anoop Sarkar
Yarowsky算法是一种基于规则的半监督学习算法，已成功应用于计算语言学中的一些问题。直到（Abney 2004）分析了该算法的一些具体变体，并提出了一些新的自举算法，人们才从数学上很好地理解了该算法。在本文中，我们扩展了Abney的工作，并表明他提出的一些算法实际上是基于交叉熵的新定义优化（上界）目标函数，该定义基于概率分布之间的布雷格曼距离的特定实例。此外，我们提出了一些新的基于规则的半监督学习算法，并展示了基于图的半监督学习中调和函数和最小多路切的联系。
The Yarowsky algorithm is a rule-based semi-supervised learning algorithm that has been successfully applied to some problems in computational linguistics. The algorithm was not mathematically well understood until (Abney 2004) which analyzed some specific variants of the algorithm, and also proposed some new algorithms for bootstrapping. In this paper, we extend Abney's work and show that some of his proposed algorithms actually optimize (an upper-bound on) an objective function based on a new definition of cross-entropy which is based on a particular instantiation of the Bregman distance between probability distributions. Moreover, we suggest some new algorithms for rule-based semi-supervised learning and show connections with harmonic functions and minimum multi-way cuts in graph-based semi-supervised learning.