Homotopy-Based Semi-Supervised Hidden Markov Models for Sequence Labeling

Proceedings of the 22nd International Conference on Computational Linguistics (Coling 2008), pages 305–312 Manchester, August 2008 Homotopy-based Semi-Supervised Hidden Markov Models for Sequence Labeling∗ Gholamreza Haffari and Anoop Sarkar School of Computing Science Simon Fraser University Burnaby, BC, Canada {ghaffar1,anoop}@cs.sfu.ca Abstract This paper explores the use of the homo- topy method for training a semi-supervised Hidden Markov Model (HMM) used for sequence labeling. We provide a novel polynomial-time algorithm to trace the lo- cal maximum of the likelihood function for HMMs from full weight on the la- beled data to full weight on the unla- beled data. We present an experimental analysis of different techniques for choos- ing the best balance between labeled and unlabeled data based on the characteris- tics observed along this path. Further- more, experimental results on the field seg- mentation task in information extraction show that the Homotopy-based method significantly outperforms EM-based semi- supervised learning, and provides a more accurate alternative to the use of held-out data to pick the best balance for combin- ing labeled and unlabeled data. 1 Introduction In semi-supervised learning, given a sample con- taining both labeled data L and unlabeled data U, the maximum likelihood estimator Θmle maxi- mizes: L(Θ) := � (x,y)∈L log P(x, y|Θ) + � x∈U log P(x|Θ) (1) where y is a structured output label, e.g. a se- quence of tags in the part-of-speech tagging task, or parse trees in the statistical parsing task. When the number of labeled instances is very small com- pared to the unlabeled instances, i.e. |L| ≪ |U|, ∗ We would like to thank Shihao Ji and the anonymous reviewers for their comments. This research was supported in part by NSERC, Canada. ∗ c⃝ 2008. Licensed under the Creative Commons Attribution-Noncommercial-Share Alike 3.0 Unported li- cense (http://creativecommons.org/licenses/by-nc-sa/3.0/). Some rights reserved. the likelihood of labeled data is dominated by that of unlabeled data, and the valuable information in the labeled data is almost completely ignored. Several studies in the natural language process- ing (NLP) literature have shown that as the size of unlabeled data increases, the performance of the model with Θmle may deteriorate, most notably in (Merialdo, 1993; Nigam et al., 2000). One strat- egy commonly used to alleviate this problem is to explicitly weigh the contribution of labeled and un- labeled data in (1) by λ ∈ [0, 1]. This new parame- ter controls the influence of unlabeled data but is estimated either by (a) an ad-hoc setting, where labeled data is given more weight than unlabeled data, or (b) by using the EM algorithm or (c) by using a held-out set. But each of these alternatives is problematic: the ad-hoc strategy does not work well in general; the EM algorithm ignores the la- beled data almost entirely; and using held-out data involves finding a good step size for the search, but small changes in λ may cause drastic changes in the estimated parameters and the performance of the resulting model. Moreover, if labeled data is scarce, which is usually the …

Content truncated to 500 words