Graph-Based Posterior Regularization for Semi-Supervised Structured Prediction

Proceedings of the Seventeenth Conference on Computational Natural Language Learning, pages 38–46, Sofia, Bulgaria, August 8-9 2013. c⃝2013 Association for Computational Linguistics Graph-Based Posterior Regularization for Semi-Supervised Structured Prediction Luheng He Jennifer Gillenwater Computer and Information Science University of Pennsylvania {luhe,jengi}@cis.upenn.edu Ben Taskar Computer Science and Engineering University of Washington taskar@cs.washington.edu Abstract We present a flexible formulation of semi- supervised learning for structured mod- els, which seamlessly incorporates graph- based and more general supervision by ex- tending the posterior regularization (PR) framework. Our extension allows for any regularizer that is a convex, differentiable function of the appropriate marginals. We show that surprisingly, non-linearity of such regularization does not increase the complexity of learning, provided we use multiplicative updates of the structured ex- ponentiated gradient algorithm. We il- lustrate the extended framework by learn- ing conditional random fields (CRFs) with quadratic penalties arising from a graph Laplacian. On sequential prediction tasks of handwriting recognition and part-of- speech (POS) tagging, our method makes significant gains over strong baselines. 1 Introduction Recent success of graph-based semi-supervised learning builds on access to plentiful unsupervised data and accurate similarity measures between data examples (Zhu et al., 2003; Joachims, 2003; Belkin et al., 2005; Zhu and Lafferty, 2005; Al- tun et al., 2005; Zhu, 2005; Chapelle et al., 2006; Subramanya and Bilmes, 2009; Subramanya et al., 2010; Das and Petrov, 2011). Many ap- proaches, such as Joachims (2003) and Subra- manya and Bilmes (2009) use graph-based learn- ing in the transductive setting, where unlabeled ex- amples are classified without learning a parametric predictive model. While predicted labels can then be leveraged to learn such a model (e.g. a CRF), this pipelined approach misses out on the benefits of modeling sequential correlations during graph propagation. In this work we seek to better inte- grate graph propagation with estimation of a struc- tured, parametric predictive model. To do so, we build on the posterior regulariza- tion (PR) framework of Ganchev et al. (2010). PR is a principled means of providing weak super- vision during structured model estimation. More concretely, PR introduces a penalty whenever the model’s posteriors over latent variables contra- dict the specified weak supervision. Ganchev et al. (2010) show how to efficiently optimize a likelihood-plus-posterior-penalty type objective in the case where the penalty is linear in the model’s marginals. Yet, there are many forms of supervi- sion that cannot be expressed as a linear function of marginals. For example, graph Laplacian regu- larization. In this work, we extend PR to allow for penalties expressed as any convex, differentiable function of the marginals and derive an efficient optimization method for such penalties. In our experiments, we explore graph Lapla- cian posterior regularizers for two applications: handwriting recognition and POS tagging. The methods of Altun et al. (2005), Subramanya et al. (2010), and Das and Petrov (2011) are the most closely related to this work. Altun et al. (2005) describes coupling a graph regularizer with a max- margin objective for pitch accent prediction and handwriting recognition tasks. Their …

Content truncated to 500 words