Data-Driven Graph Construction for Semi-Supervised Graph-Based Learning in NLP

Proceedings of NAACL HLT 2007, pages 204–211, Rochester, NY, April 2007. c⃝2007 Association for Computational Linguistics Data-Driven Graph Construction for Semi-Supervised Graph-Based Learning in NLP Andrei Alexandrescu Dept. of Computer Science and Engineering University of Washington Seattle, WA, 98195 andrei@cs.washington.edu Katrin Kirchhoff Dept. of Electrical Engineering University of Washington Seattle, WA 98195 katrin@ee.washington.edu Abstract Graph-based semi-supervised learning has recently emerged as a promising approach to data-sparse learning problems in natu- ral language processing. All graph-based algorithms rely on a graph that jointly rep- resents labeled and unlabeled data points. The problem of how to best construct this graph remains largely unsolved. In this paper we introduce a data-driven method that optimizes the representation of the initial feature space for graph construc- tion by means of a supervised classifier. We apply this technique in the frame- work of label propagation and evaluate it on two different classification tasks, a multi-class lexicon acquisition task and a word sense disambiguation task. Signifi- cant improvements are demonstrated over both label propagation using conventional graph construction and state-of-the-art su- pervised classifiers. 1 Introduction Natural Language Processing (NLP) applications benefit from the availability of large amounts of an- notated data. However, such data is often scarce, particularly for non-mainstream languages. Semi- supervised learning addresses this problem by com- bining large amounts of unlabeled data with a small set of labeled data in order to learn a classifica- tion function. One class of semi-supervised learn- ing algorithms that has recently attracted increased interest is graph-based learning. Graph-based tech- niques represent labeled and unlabeled data points as nodes in a graph with weighted edges encoding the similarity of pairs of samples. Various tech- niques are then available for transferring class la- bels from the labeled to the unlabeled data points. These approaches have shown good performance in cases where the data is characterized by an underly- ing manifold structure and samples are judged to be similar by local similarity measures. However, the question of how to best construct the graph forming the basis of the learning procedure is still an under- investigated research problem. NLP learning tasks present additional problems since they often rely on discrete or heterogeneous feature spaces for which standard similarity measures (such as Euclidean or cosine distance) are suboptimal. We propose a two-pass data-driven technique for graph construction in the framework of label propa- gation (Zhu, 2005). First, we use a supervised clas- sifier trained on the labeled subset to transform the initial feature space (consisting of e.g. lexical, con- textual, or syntactic features) into a continuous rep- resentation in the form of soft label predictions. This representation is then used as a basis for measur- ing similarity among samples that determines the structure of the graph used for the second, semi- supervised learning step. It is important to note that, rather than simply cascading the supervised and the semi-supervised learner, we optimize the combina- tion with respect to the properties required of the graph. We present several techniques for such op- timization, including …

Content truncated to 500 words