Randomized Greedy Inference for Joint Segmentation, POS Tagging and Dependency Parsing

Human Language Technologies: The 2015 Annual Conference of the North American Chapter of the ACL, pages 42–52, Denver, Colorado, May 31 – June 5, 2015. c⃝2015 Association for Computational Linguistics Randomized Greedy Inference for Joint Segmentation, POS Tagging and Dependency Parsing Yuan Zhang, Chengtao Li, Regina Barzilay Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology {yuanzh, ctli, regina}@csail.mit.edu Kareem Darwish ALT Research Group Qatar Computing Research Institute kdarwish@qf.org.qa Abstract In this paper, we introduce a new approach for joint segmentation, POS tagging and de- pendency parsing. While joint modeling of these tasks addresses the issue of error prop- agation inherent in traditional pipeline archi- tectures, it also complicates the inference task. Past research has addressed this challenge by placing constraints on the scoring function. In contrast, we propose an approach that can handle arbitrarily complex scoring functions. Specifically, we employ a randomized greedy algorithm that jointly predicts segmentations, POS tags and dependency trees. Moreover, this architecture readily handles different seg- mentation tasks, such as morphological seg- mentation for Arabic and word segmentation for Chinese. The joint model outperforms the state-of-the-art systems on three datasets, ob- taining 2.1% TedEval absolute gain against the best published results in the 2013 SPMRL shared task.1 1 Introduction Parsing accuracy is greatly impacted by the qual- ity of preprocessing steps such as tagging and word segmentation. Li et al. (2011) report that the dif- ference between using the gold POS tags and us- ing the automatic counterparts reaches about 6% in dependency accuracy. Prior research has demon- strated that joint prediction alleviates error propaga- tion inherent in pipeline architectures, where mis- takes cascade from one task to the next (Bohnet et 1The source code is available at https://github. com/yuanzh/SegParser. al., 2013; Tratz, 2013; Hatori et al., 2012; Zhang et al., 2014a). However, jointly modeling all the processing tasks inevitably increases inference com- plexity. Prior work addressed this challenge by in- troducing constraints on scoring functions to keep inference tractable (Qian and Liu, 2012). In this paper, we propose a method for joint pre- diction that imposes no constraints on the scoring function. The method is able to handle high-order and global features for each individual task (e.g., parsing), as well as features that capture interactions between tasks. The algorithm achieves this flexibil- ity by operating over full assignments that specify segmentation, POS tags and dependency tree, mov- ing from one complete configuration to another. Our approach is based on the randomized greedy algorithm from our earlier dependency parsing sys- tem (Zhang et al., 2014b). We extend this algorithm to jointly predict the segmentation and the POS tags in addition to the dependency parse. The search space for the algorithm is a combination of parse trees and lattices that encode alternative morpho- logical and POS analyses. The inference algorithm greedily searches over this space, iteratively mak- ing local modifications to POS tags and dependency trees. To overcome local optima, we employ multi- ple restarts. This simple, yet powerful approach can be eas- ily applied …

Content truncated to 500 words