Understanding the Yarowsky Algorithm

By Steven P. Abney. 2004

153 citations recorded by the source corpus.

Many problems in computational linguistics are well suited for bootstrapping (semisupervised learning) techniques. The Yarowsky algorithm is a well-known bootstrapping algorithm, but it is not mathematically well understood. This article analyzes it as optimizing an objective function. More specifically, a number of variants of the Yarowsky algorithm (though not the original algorithm itself) are shown to optimize either likelihood or a closely related objective function K.

Subfields: Artificial Intelligence

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

Semi-supervised learning, causality, and the conditional cluster assumption (2019, methodology): “This is a wrapper algorithm that initialises the learner based on the labelled data, updates the labels for the unlabelled data, and then retrains based on all labelled data available, possibly iterating this procedure (Abney, 2004; Blum and Mitchell, 1998; Scudder, 1965).”
Training Deep Neural Networks on Noisy Labels with Bootstrapping (2014, methodology): “The algorithm was analyzed by Abney (Abney, 2004) and more recently by (Haffari & Sarkar, 2012).”
Deep Contextualized Self-training for Low Resource Dependency Parsing (2019, methodology): “A prominent technique for training machine learning models on labeled and unlabeled data is self-training (Yarowsky, 1995; Abney, 2004).”
Bootstrapped Graph Diffusions: Exposing the Power of Nonlinearity (2017, background): “Self-training is arguably the earliest approach to SSL, dating back ve decades to Scudder [34], and extensively studied by the NLP community [1, 38, 40].”
Multi-view Regression Via Canonical Correlation Analysis (2007, methodology): “…no further distributional assumptions (aside from a bounded second moment on the output variable), such as the commonly used, overly-stringent assumption that the distribution of the views be conditionally 3 independent given the label [Blum and Mitchell, 1998, Dasgupta et al., 2001, Abney, 2004].”
Word sense disambiguation: A survey (2009, methodology): “A number of variations of the original Yarowsky’s algorithm were presented by Abney [2004]. As a major drawback of co- and self-training, we cite the lack of a method for selecting optimal values for parameters like the pool size p, the number of iterations and the number of most confident examples ”
Contrastive Pessimistic Likelihood Estimation for Semi-Supervised Classification (2015, result): “We note that this is in contrast with the supervised setting, where most classiﬁers are capable of handling mismatched data assumptions rather well and adding more labeled data typically improves performance.”
Generalized Expectation Criteria for Semi-Supervised Learning with Weakly Labeled Data (2010, methodology): “Abney (2004) provides a deeper understanding of these methods by demonstrating th t they optimize a natural objective function.”
Bootstrapped Graph Diffusions: Exposing the Power of Nonlinearity (2018, background): “Self-training is arguably the earliest approach to SSL, dating back five decades to Scudder [33], and extensively studied by the NLP community [1, 35, 37].”
Cross-Domain Learning from Multiple Sources: A Consensus Regularization Perspective (2010, background): “In addition, Dasgupta et al. [25] and Abney [26], [ 27 ] provided PAC bounds on the error of co-Training in terms of the”
An Information Theoretic Framework for Multi-view Learning (2008, methodology): “The work of Dasgupta et al. [2001], Abney [2004] shows how unreasonably strong this extra assumption is, with regards to classiﬁcation.”
Transductive learning for statistical machine translation (2007, methodology): “Our transductive learning algorithm, Algorithm 1, is inspired by the Yarowsky algorithm (Yarowsky, 1995; Abney, 2004).”
Bootstrapping Entity Alignment with Knowledge Graph Embedding (2018, methodology): “To obtain a holistic observation of both labeled and unlabeled entities, we deﬁne a probability distribution (cid:30) x to describe all the labeling possibilities of x [Abney, 2004].”
Semi-Supervised Learning for Natural Language (2005, methodology): “(Abney, 2004) analyzes variants of Yarowsky's bootstrapping algorithms in terms of optimizing a well-defined objective.”
Bootstrapped Graph Diffusions (2018, background): “Self-training is arguably the earliest approach to SSL, dating back five decades to Scudder [35], and extensively studied by the NLP community [1, 39, 41] The wrapper applies the base algorithm in steps, where at the end of each step, the highest-confidence predictions are converted to become new…”
Semi-supervised model adaptation for statistical machine translation (2007, methodology): “Our model adaptation algorithm, Algorithm 1, is inspired by the Yarowsky algorithm (Yarowsky 1995; Abney 2004).”