Semi-Supervised Convex Training for Dependency Parsing
Article Structure
Abstract
We present a novel semi-supervised training algorithm for learning dependency parsers.
Introduction
Supervised learning algorithms still represent the state of the art approach for inferring dependency parsers from data (McDonald et al., 2005a; McDonald and Pereira, 2006; Wang et al., 2007).
Dependency Parsing Model
Given a sentence X = (x1, ..., sun) (cc,- denotes each word in the sentence), we are interested in computing a directed dependency tree, Y, over X.
Supervised Structured Large Margin Training
Supervised structured large margin training approaches have been applied to parsing and produce promising results (Taskar et al., 2004; McDonald et al., 2005a; Wang et al., 2006).
Semi-supervised Structured Large Margin Objective
The objective of standard semi-supervised structured SVM is a combination of structured large margin losses on both labeled and unlabeled data.
Semi-supervised Convex Training for Structured SVM
Although semi-supervised structured SVM learning has been an active research area, semi-supervised structured SVMs have not been used in many real applications to date.
Efficient Optimization Strategy
To solve the convex optimization problem shown in Equation (10), we used a gradient descent approach which simply uses stochastic gradient steps.
Experimental Results
Given a convex approach to semi-supervised structured large margin training, and an efficient training
Conclusion and Future Work
In this paper, we have presented a novel algorithm for semi-supervised structured large margin training.
Topics
semi-supervised
Appears in 39 sentences as: Semi-supervised (3) semi-supervised (38)
In Semi-Supervised Convex Training for Dependency Parsing
- We present a novel semi-supervised training algorithm for learning dependency parsers.Page 1, “Abstract”
- By combining a supervised large margin loss with an unsupervised least squares loss, a dis-criminative, convex, semi-supervised learning algorithm can be obtained that is applicable to large-scale problems.Page 1, “Abstract”
- heavy dependence on annotated corpora—many researchers have investigated semi-supervised learning techniques that can take both labeled and unlabeled training data as input.Page 1, “Introduction”
- Unfortunately, although significant recent progress has been made in the area of semi-supervised learning, the performance of semi-supervised learning algorithms still fall far short of expectations, particularly in challenging real-world tasks such as natural language parsing or machine translation.Page 1, “Introduction”
- A large number of distinct approaches to semi-supervised training algorithms have been investigated in the literature (Bennett and Demiriz, 1998; Zhu et al., 2003; Altun et al., 2005; Mann and McCallum, 2007).Page 1, “Introduction”
- Among the most prominent approaches are self-training, generative models, semi-supervised support vector machines (S3VM), graph-based algorithms and multi-view algorithms (Zhu, 2005).Page 1, “Introduction”
- Self-training is a commonly used technique for semi-supervised learning that has been ap-Page 1, “Introduction”
- Consequently, most previous work that has attempted semi-supervised or unsupervised approaches to parsing have not produced results beyond the state of the art supervised results (Klein and Manning, 2002; Klein and Manning, 2004).Page 2, “Introduction”
- As a result, many researchers have put effort on developing algorithms for semi-supervised SVMs (S3VMs) (Bennett and Demiriz, 1998; Altun et al., 2005).Page 2, “Introduction”
- In particular, they present an algorithm for multi-class unsupervised and semi-supervised SVM learning, which relaxes the original non-convex objective into a close convex approximation, thereby allowing a global solution to be obtained.Page 2, “Introduction”
- Thus, in this paper, we focus on semi-supervised language learning, where we can make use of both labeled and unlabeled data.Page 2, “Introduction”
See all papers in Proc. ACL 2008 that mention semi-supervised.
See all papers in Proc. ACL that mention semi-supervised.
Back to top.
dependency parsing
Appears in 20 sentences as: dependency parser (1) dependency parsers (5) Dependency Parsing (3) dependency parsing (12)
In Semi-Supervised Convex Training for Dependency Parsing
- We present a novel semi-supervised training algorithm for learning dependency parsers .Page 1, “Abstract”
- To demonstrate the benefits of this approach, we apply the technique to learning dependency parsers from combined labeled and unlabeled corpora.Page 1, “Abstract”
- Supervised learning algorithms still represent the state of the art approach for inferring dependency parsers from data (McDonald et al., 2005a; McDonald and Pereira, 2006; Wang et al., 2007).Page 1, “Introduction”
- As we will demonstrate below, this approach admits an efficient training procedure that can find a global minimum, and, perhaps surprisingly, can systematically improve the accuracy of supervised training approaches for learning dependency parsers .Page 2, “Introduction”
- ing semi-supervised convex objective to dependency parsing , and obtain significant improvement over the corresponding supervised structured SVM.Page 3, “Introduction”
- Finally, we apply this algorithm to dependency parsing and show improved dependency parsing accuracy for both Chinese and English.Page 3, “Introduction”
- This formulation is sufficiently general to capture most dependency parsing models, including probabilistic dependency models (Eisner, 1996; Wang et al., 2005) as well as non-probabilistic models (McDonald et al., 2005a).Page 3, “Dependency Parsing Model”
- This approach corresponds to the training problem posed in (McDonald et al., 2005a) and has yielded the best published results for English dependency parsing .Page 4, “Supervised Structured Large Margin Training”
- This procedure works efficiently on the task of training a dependency parser .Page 6, “Efficient Optimization Strategy”
- algorithm for achieving a global optimum, we now investigate its effectiveness for dependency parsing .Page 6, “Experimental Results”
- We applied the resulting algorithm to learn dependency parsers for both English and Chinese.Page 6, “Experimental Results”
See all papers in Proc. ACL 2008 that mention dependency parsing.
See all papers in Proc. ACL that mention dependency parsing.
Back to top.
unlabeled data
Appears in 18 sentences as: unlabeled data (19)
In Semi-Supervised Convex Training for Dependency Parsing
- Following the common theme of “more data is better data” we also use both a limited labeled corpora and a plentiful unlabeled data resource.Page 1, “Introduction”
- (2006a) successfully applied self-training to parsing by exploiting available unlabeled data , and obtained remarkable results when the same technique was applied to parser adaptation (McClosky et al., 2006b).Page 2, “Introduction”
- However, the standard objective of an S3VM is non-convex on the unlabeled data , thus requiring sophisticated global optimization heuristics to obtain reasonable solutions.Page 2, “Introduction”
- We simply replace the non-convex loss on unlabeled data with an alternative loss that is jointly convex with respect to both the model parameters and (the encoding of) the self-trained prediction targets.Page 2, “Introduction”
- More specifically, for the loss on the unlabeled data part, we substitute the original unsupervised structured SVM loss with a least squares loss, but keep constraints on the inferred prediction targets, which avoids trivialization.Page 2, “Introduction”
- This loss function has the advantage that the entire training objective on both the labeled and unlabeled data now becomes convex, since it consists of a convex structured large margin loss on labeled data and a convex least squares loss on unlabeled data .Page 2, “Introduction”
- Thus, in this paper, we focus on semi-supervised language learning, where we can make use of both labeled and unlabeled data .Page 2, “Introduction”
- In particular, we investigate a semi-supervised approach for structured large margin training, where the objective is a combination of two convex functions, the structured large margin loss on labeled data and the least squares loss on unlabeled data .Page 2, “Introduction”
- The objective of standard semi-supervised structured SVM is a combination of structured large margin losses on both labeled and unlabeled data .Page 4, “Semi-supervised Structured Large Margin Objective”
- We introduce an efficient approximation—least squares loss—for the structured large margin loss on unlabeled data below.Page 4, “Semi-supervised Structured Large Margin Objective”
- for structured large margin training, whose objective is a combination of two convex terms: the supervised structured large margin loss on labeled data and the cheap least squares loss on unlabeled data .Page 5, “Semi-supervised Convex Training for Structured SVM”
See all papers in Proc. ACL 2008 that mention unlabeled data.
See all papers in Proc. ACL that mention unlabeled data.
Back to top.
dependency tree
Appears in 9 sentences as: dependency tree (6) Dependency trees (1) dependency trees (2)
In Semi-Supervised Convex Training for Dependency Parsing
- Figure l: A dependency treePage 3, “Introduction”
- Given a sentence X = (x1, ..., sun) (cc,- denotes each word in the sentence), we are interested in computing a directed dependency tree , Y, over X.Page 3, “Dependency Parsing Model”
- We assume that a directed dependency tree Y consists of ordered pairs (sci —> any) of words in X such that each word appears in at least one pair and each word has in-degree at most one.Page 3, “Dependency Parsing Model”
- Dependency trees are assumed to be projective here, which means that if there is an arc (cc,- —> 553-), then :0,- is an ancestor of all the wordsPage 3, “Dependency Parsing Model”
- 1We assume all the dependency trees are projective in our work (just as some other researchers do), although in the real word, most languages are non-projective.Page 3, “Supervised Structured Large Margin Training”
- We represent a dependency tree as a k x k adjacency matrix.Page 4, “Supervised Structured Large Margin Training”
- As mentioned in Section 3, a dependency tree Yj is represented as an adjacency matrix.Page 5, “Semi-supervised Convex Training for Structured SVM”
- Thus we need to enforce some constraints in the adjacency matrix to make sure that each Yj satisfies the dependency tree constraints.Page 5, “Semi-supervised Convex Training for Structured SVM”
- For experiment on English, we used the English Penn Treebank (PTB) (Marcus et al., 1993) and the constituency structures were converted to dependency trees using the same rules as (Yamada and Matsumoto, 2003).Page 6, “Experimental Results”
See all papers in Proc. ACL 2008 that mention dependency tree.
See all papers in Proc. ACL that mention dependency tree.
Back to top.
labeled data
Appears in 7 sentences as: labeled data (7)
In Semi-Supervised Convex Training for Dependency Parsing
- However, a key drawback of supervised training algorithms is their dependence on labeled data , which is usually very difficult to obtain.Page 1, “Introduction”
- This loss function has the advantage that the entire training objective on both the labeled and unlabeled data now becomes convex, since it consists of a convex structured large margin loss on labeled data and a convex least squares loss on unlabeled data.Page 2, “Introduction”
- In particular, we investigate a semi-supervised approach for structured large margin training, where the objective is a combination of two convex functions, the structured large margin loss on labeled data and the least squares loss on unlabeled data.Page 2, “Introduction”
- for structured large margin training, whose objective is a combination of two convex terms: the supervised structured large margin loss on labeled data and the cheap least squares loss on unlabeled data.Page 5, “Semi-supervised Convex Training for Structured SVM”
- By combining the convex structured SVM loss on labeled data (shown in Equation (5)) and the convex least squares loss on unlabeled data (shown in Equation (8)), we obtain a semi-supervised structured large margin lossPage 5, “Semi-supervised Convex Training for Structured SVM”
- 0 Step 2, based on the learned parameter weights from the labeled data , update 6 and Yj on each unlabeled sentence alternatively:Page 6, “Efficient Optimization Strategy”
- One obvious direction is to use the whole Penn Treebank as labeled data and use some other unannotated data source as unlabeled data for semi-supervised training.Page 8, “Conclusion and Future Work”
See all papers in Proc. ACL 2008 that mention labeled data.
See all papers in Proc. ACL that mention labeled data.
Back to top.
SVM
Appears in 7 sentences as: SVM (7)
In Semi-Supervised Convex Training for Dependency Parsing
- In particular, they present an algorithm for multi-class unsupervised and semi-supervised SVM learning, which relaxes the original non-convex objective into a close convex approximation, thereby allowing a global solution to be obtained.Page 2, “Introduction”
- More specifically, for the loss on the unlabeled data part, we substitute the original unsupervised structured SVM loss with a least squares loss, but keep constraints on the inferred prediction targets, which avoids trivialization.Page 2, “Introduction”
- ing semi-supervised convex objective to dependency parsing, and obtain significant improvement over the corresponding supervised structured SVM .Page 3, “Introduction”
- The objective of standard semi-supervised structured SVM is a combination of structured large margin losses on both labeled and unlabeled data.Page 4, “Semi-supervised Structured Large Margin Objective”
- Although semi-supervised structured SVM learning has been an active research area, semi-supervised structured SVMs have not been used in many real applications to date.Page 4, “Semi-supervised Convex Training for Structured SVM”
- By combining the convex structured SVM loss on labeled data (shown in Equation (5)) and the convex least squares loss on unlabeled data (shown in Equation (8)), we obtain a semi-supervised structured large margin lossPage 5, “Semi-supervised Convex Training for Structured SVM”
- Unlike previous proposed approaches, we introduce a convex objective for the semi-supervised learning algorithm by combining a convex structured SVM loss and a convex least square loss.Page 8, “Conclusion and Future Work”
See all papers in Proc. ACL 2008 that mention SVM.
See all papers in Proc. ACL that mention SVM.
Back to top.
learning algorithm
Appears in 6 sentences as: learning algorithm (3) learning algorithms (3)
In Semi-Supervised Convex Training for Dependency Parsing
- By combining a supervised large margin loss with an unsupervised least squares loss, a dis-criminative, convex, semi-supervised learning algorithm can be obtained that is applicable to large-scale problems.Page 1, “Abstract”
- Supervised learning algorithms still represent the state of the art approach for inferring dependency parsers from data (McDonald et al., 2005a; McDonald and Pereira, 2006; Wang et al., 2007).Page 1, “Introduction”
- Unfortunately, although significant recent progress has been made in the area of semi-supervised learning, the performance of semi-supervised learning algorithms still fall far short of expectations, particularly in challenging real-world tasks such as natural language parsing or machine translation.Page 1, “Introduction”
- The basic idea is to bootstrap a supervised learning algorithm by alternating between inferring the missing label information and retraining.Page 2, “Introduction”
- They also show connections between these algorithms and other related machine learning algorithms .Page 2, “Introduction”
- Unlike previous proposed approaches, we introduce a convex objective for the semi-supervised learning algorithm by combining a convex structured SVM loss and a convex least square loss.Page 8, “Conclusion and Future Work”
See all papers in Proc. ACL 2008 that mention learning algorithm.
See all papers in Proc. ACL that mention learning algorithm.
Back to top.
loss function
Appears in 5 sentences as: loss function (4) loss functions (1)
In Semi-Supervised Convex Training for Dependency Parsing
- Instead of devising various techniques for coping with non-convex loss functions , we approach the problem from a different perspective.Page 2, “Introduction”
- Although using a least squares loss function for classification appears misguided, there is a precedent for just this approach in the early pattern recognition literature (Duda et al., 2000).Page 2, “Introduction”
- This loss function has the advantage that the entire training objective on both the labeled and unlabeled data now becomes convex, since it consists of a convex structured large margin loss on labeled data and a convex least squares loss on unlabeled data.Page 2, “Introduction”
- The resulting loss function has a hat shape (usually called hat-loss), which is non-convex.Page 4, “Semi-supervised Structured Large Margin Objective”
- These positive results are somewhat surprising since a very simple loss function was used onPage 7, “Experimental Results”
See all papers in Proc. ACL 2008 that mention loss function.
See all papers in Proc. ACL that mention loss function.
Back to top.
Treebank
Appears in 4 sentences as: Treebank (3) treebank (1)
In Semi-Supervised Convex Training for Dependency Parsing
- For experiment on English, we used the English Penn Treebank (PTB) (Marcus et al., 1993) and the constituency structures were converted to dependency trees using the same rules as (Yamada and Matsumoto, 2003).Page 6, “Experimental Results”
- For Chinese, we experimented on the Penn Chinese Treebank 4.0 (CTB4) (Palmer et al., 2004) and we used the rules in (Bikel, 2004) for conversion.Page 6, “Experimental Results”
- We evaluate parsing accuracy by comparing the directed dependency links in the parser output against the directed links in the treebank .Page 7, “Experimental Results”
- One obvious direction is to use the whole Penn Treebank as labeled data and use some other unannotated data source as unlabeled data for semi-supervised training.Page 8, “Conclusion and Future Work”
See all papers in Proc. ACL 2008 that mention Treebank.
See all papers in Proc. ACL that mention Treebank.
Back to top.
natural language
Appears in 3 sentences as: natural language (3)
In Semi-Supervised Convex Training for Dependency Parsing
- Unfortunately, although significant recent progress has been made in the area of semi-supervised learning, the performance of semi-supervised learning algorithms still fall far short of expectations, particularly in challenging real-world tasks such as natural language parsing or machine translation.Page 1, “Introduction”
- plied to several natural language processing tasks (Yarowsky, 1995; Charniak, 1997; Steedman et al., 2003).Page 2, “Introduction”
- Another direction is to apply the semi-supervised algorithm to other natural language problems, such as machine translation, topic segmentation and chunking.Page 8, “Conclusion and Future Work”
See all papers in Proc. ACL 2008 that mention natural language.
See all papers in Proc. ACL that mention natural language.
Back to top.
state of the art
Appears in 3 sentences as: state of the art (3)
In Semi-Supervised Convex Training for Dependency Parsing
- Supervised learning algorithms still represent the state of the art approach for inferring dependency parsers from data (McDonald et al., 2005a; McDonald and Pereira, 2006; Wang et al., 2007).Page 1, “Introduction”
- Consequently, most previous work that has attempted semi-supervised or unsupervised approaches to parsing have not produced results beyond the state of the art supervised results (Klein and Manning, 2002; Klein and Manning, 2004).Page 2, “Introduction”
- In recent years, SVMs have demonstrated state of the art results in many supervised learning tasks.Page 2, “Introduction”
See all papers in Proc. ACL 2008 that mention state of the art.
See all papers in Proc. ACL that mention state of the art.
Back to top.
