Adapting Discriminative Reranking to Grounded Language Learning
Kim, Joohyun and Mooney, Raymond

Article Structure

Abstract

We adapt discriminative reranking to improve the performance of grounded language acquisition, specifically the task of learning to follow navigation instructions from observation.

Introduction

Grounded language acquisition involves learning to comprehend and/or generate language by simply observing its use in a naturally occurring context in which the meaning of a sentence is grounded in perception and/or action (Roy, 2002; Yu and Ballard, 2004; Gold and Scassel-lati, 2007; Chen et al., 2010).

Background

2.1 Navigation Task

Modified Reranking Algorithm

In reranking, a baseline generative model is first trained and generates a set of candidate outputs for each training example.

Reranking Features

This section describes the features (I) extracted from parses produced by the generative model and used to rerank the candidates.

Experimental Evaluation

5.1 Data and Methodology

Related Work

Discriminative reranking is a common machine learning technique to improve the output of generative models.

Future Work

In the future, we would like to explore the construction of better, more-general reranking features that are less prone to over-fitting.

Conclusions

In this paper, we have shown how to adapt discriminative reranking to grounded language learning.

Topics

reranking

Appears in 46 sentences as: rerank (2) reranker (3) Reranking (6) reranking (38)
In Adapting Discriminative Reranking to Grounded Language Learning
  1. We adapt discriminative reranking to improve the performance of grounded language acquisition, specifically the task of learning to follow navigation instructions from observation.
    Page 1, “Abstract”
  2. Unlike conventional reranking used in syntactic and semantic parsing, gold-standard reference trees are not naturally available in a grounded setting.
    Page 1, “Abstract”
  3. Since their system employs a generative model, discriminative reranking (Collins, 2000) could p0-tentially improve its performance.
    Page 1, “Introduction”
  4. By training a discriminative classifier that uses global features of complete parses to identify correct interpretations, a reranker can significantly improve the accuracy of a generative model.
    Page 1, “Introduction”
  5. Reranking has been successfully employed to improve syntactic parsing (Collins, 2002b), semantic parsing (Lu et al., 2008; Ge and Mooney, 2006), semantic role labeling (Toutanova et al., 2005), and named entity recognition (Collins, 2002c).
    Page 1, “Introduction”
  6. Standard reranking requires gold-standard interpretations (e.g.
    Page 1, “Introduction”
  7. Therefore, it is impossible to directly apply conventional discriminative reranking to such problems.
    Page 1, “Introduction”
  8. We show how to adapt reranking to work with such weak supervision.
    Page 1, “Introduction”
  9. Additionally, we extensively revise the features typically used in parse reranking to work with the PCFG approach to grounded language learning.
    Page 1, “Introduction”
  10. Section 3 presents our modified approach to reranking and Section 4 describes the novel features used to evaluate parses.
    Page 1, “Introduction”
  11. The baseline generative model we use for reranking employs the unsupervised PCFG induction approach introduced by Kim and Mooney (2012).
    Page 2, “Background”

See all papers in Proc. ACL 2013 that mention reranking.

See all papers in Proc. ACL that mention reranking.

Back to top.

parse tree

Appears in 29 sentences as: Parse Tree (1) parse tree (17) parse trees (14)
In Adapting Discriminative Reranking to Grounded Language Learning
  1. successful task completion) can be used as an alternative, experimentally demonstrating that its performance is comparable to training on gold-standard parse trees .
    Page 1, “Abstract”
  2. parse trees ) to train the discriminative classifier.
    Page 1, “Introduction”
  3. They also altered the processes for constructing productions and mapping parse trees to MRs in order to make the construction of semantic interpretations more compositional and allow the efficient construction of more complex representa-
    Page 2, “Background”
  4. A simplified version of a sample parse tree for Kim and Mooney’s model is shown in Figure 2.
    Page 3, “Background”
  5. Therefore, we modify it to rerank the parse trees generated by Kim and Mooney (2012)’s model.
    Page 3, “Modified Reranking Algorithm”
  6. The approach requires three subcomponents: l) a GEN function that returns the list of top n candidate parse trees for each NL sentence produced by the generative model, 2) a feature function (I) that maps a NL sentence, 6, and a parse tree, y, into a real-valued feature vector (19(6, 3/) 6 Rd, and 3) a reference parse tree that is compared to the highest-scoring parse tree during training.
    Page 3, “Modified Reranking Algorithm”
  7. However, grounded language learning tasks, such as our navigation task, do not provide reference parse trees for training examples.
    Page 3, “Modified Reranking Algorithm”
  8. Instead, our modified model replaces the gold-standard reference parse with the “pseudo-gold” parse tree
    Page 3, “Modified Reranking Algorithm”
  9. Thus, the third component in our reranking model becomes an evaluation function EXEC that maps a parse tree y into a real number representing the success rate (w.r.t.
    Page 3, “Modified Reranking Algorithm”
  10. The final plan MRs are produced from parse trees using compositional semantics (see Kim and Mooney (2012) for details).
    Page 4, “Modified Reranking Algorithm”
  11. Consequently, the n-best parse trees for the baseline model do not necessarily produce the n-best distinct plans, since many parses can produce the same plan.
    Page 4, “Modified Reranking Algorithm”

See all papers in Proc. ACL 2013 that mention parse tree.

See all papers in Proc. ACL that mention parse tree.

Back to top.

gold-standard

Appears in 22 sentences as: gold-standard (23)
In Adapting Discriminative Reranking to Grounded Language Learning
  1. Unlike conventional reranking used in syntactic and semantic parsing, gold-standard reference trees are not naturally available in a grounded setting.
    Page 1, “Abstract”
  2. successful task completion) can be used as an alternative, experimentally demonstrating that its performance is comparable to training on gold-standard parse trees.
    Page 1, “Abstract”
  3. Standard reranking requires gold-standard interpretations (e.g.
    Page 1, “Introduction”
  4. However, grounded language learning does not provide gold-standard interpretations for the training examples.
    Page 1, “Introduction”
  5. Instead of using gold-standard annotations to determine the correct interpretations, we simply prefer interpretations of navigation instructions that, when executed in the world, actually reach the intended destination.
    Page 1, “Introduction”
  6. Instead, our modified model replaces the gold-standard reference parse with the “pseudo-gold” parse tree
    Page 3, “Modified Reranking Algorithm”
  7. To circumvent the need for gold-standard reference parses, we select a pseudo-gold parse from the candidates produced by the GEN function.
    Page 3, “Modified Reranking Algorithm”
  8. In a similar vein, when reranking semantic parses, Ge and Mooney (2006) chose as a reference parse the one which was most similar to the gold-standard semantic annotation.
    Page 3, “Modified Reranking Algorithm”
  9. Typically, when used for reranking, the averaged perceptron updates its weights using the feature-vector difference between the current best predicted candidate and the gold-standard reference (line 6 in Algorithm 1).
    Page 4, “Modified Reranking Algorithm”
  10. In our initial modified version, we replaced the gold-standard reference parse with the pseudo-gold reference, which has the highest execution rate amongst all candidate parses.
    Page 4, “Modified Reranking Algorithm”
  11. It is calculated by comparing the system’s MR output to the gold-standard MR.
    Page 7, “Experimental Evaluation”

See all papers in Proc. ACL 2013 that mention gold-standard.

See all papers in Proc. ACL that mention gold-standard.

Back to top.

perceptron

Appears in 10 sentences as: PERCEPTRON (2) perceptron (8)
In Adapting Discriminative Reranking to Grounded Language Learning
  1. Reranking using an averaged perceptron (Collins, 2002a) has been successfully applied to a variety of NLP tasks.
    Page 3, “Modified Reranking Algorithm”
  2. Algorithm 1 AVERAGED PERCEPTRON TRAINING WITH RESPONSE-BASED UPDATE Input: A set of training examples (ei,y§‘), where 6, is a NL sentence and = arg maXyEGENQai) EXEC _ Output: The parameter vector W, averaged over all iterations 1. .
    Page 3, “Modified Reranking Algorithm”
  3. 1: procedure PERCEPTRON
    Page 3, “Modified Reranking Algorithm”
  4. Additionally, we improve the perceptron training algorithm by using multiple reference parses to update the weight vector W. Although we determine the pseudo-gold reference tree to be the candidate parse y* such that y* = arg maxyEGEN(e) EXEC(y), it may not actually be the correct parse for the sentence.
    Page 3, “Modified Reranking Algorithm”
  5. Our modified averaged perceptron procedure with such a response-based update is shown in Algorithm 1.
    Page 4, “Modified Reranking Algorithm”
  6. Typically, when used for reranking, the averaged perceptron updates its weights using the feature-vector difference between the current best predicted candidate and the gold-standard reference (line 6 in Algorithm 1).
    Page 4, “Modified Reranking Algorithm”
  7. However, this ignores all other candidate parses during perceptron training.
    Page 4, “Modified Reranking Algorithm”
  8. Therefore, we also consider a further modification of the averaged perceptron algorithm which updates its weights using multiple candidate parses.
    Page 4, “Modified Reranking Algorithm”
  9. Table 2 presents reranking results for our proposed response-based weight update (Single) for the averaged perceptron (cf.
    Page 7, “Experimental Evaluation”
  10. In addition, since this response-based supervision is weak and ambiguous, we have also presented a method for using multiple reference parses to perform perceptron weight updates and shown a clear further improvement in end-task performance with this approach.
    Page 9, “Conclusions”

See all papers in Proc. ACL 2013 that mention perceptron.

See all papers in Proc. ACL that mention perceptron.

Back to top.

generative model

Appears in 9 sentences as: generative model (8) generative models (1)
In Adapting Discriminative Reranking to Grounded Language Learning
  1. Since their system employs a generative model , discriminative reranking (Collins, 2000) could p0-tentially improve its performance.
    Page 1, “Introduction”
  2. By training a discriminative classifier that uses global features of complete parses to identify correct interpretations, a reranker can significantly improve the accuracy of a generative model .
    Page 1, “Introduction”
  3. The baseline generative model we use for reranking employs the unsupervised PCFG induction approach introduced by Kim and Mooney (2012).
    Page 2, “Background”
  4. Our proposed reranking model is used to discriminatively reorder the top parses produced by this generative model .
    Page 3, “Background”
  5. In reranking, a baseline generative model is first trained and generates a set of candidate outputs for each training example.
    Page 3, “Modified Reranking Algorithm”
  6. The approach requires three subcomponents: l) a GEN function that returns the list of top n candidate parse trees for each NL sentence produced by the generative model , 2) a feature function (I) that maps a NL sentence, 6, and a parse tree, y, into a real-valued feature vector (19(6, 3/) 6 Rd, and 3) a reference parse tree that is compared to the highest-scoring parse tree during training.
    Page 3, “Modified Reranking Algorithm”
  7. This section describes the features (I) extracted from parses produced by the generative model and used to rerank the candidates.
    Page 4, “Reranking Features”
  8. Certainty assigned by the base generative model .
    Page 5, “Reranking Features”
  9. Discriminative reranking is a common machine learning technique to improve the output of generative models .
    Page 8, “Related Work”

See all papers in Proc. ACL 2013 that mention generative model.

See all papers in Proc. ACL that mention generative model.

Back to top.

semantic parsing

Appears in 8 sentences as: semantic parser (1) semantic parsers (1) semantic parses (2) semantic parsing (4)
In Adapting Discriminative Reranking to Grounded Language Learning
  1. Unlike conventional reranking used in syntactic and semantic parsing , gold-standard reference trees are not naturally available in a grounded setting.
    Page 1, “Abstract”
  2. Reranking has been successfully employed to improve syntactic parsing (Collins, 2002b), semantic parsing (Lu et al., 2008; Ge and Mooney, 2006), semantic role labeling (Toutanova et al., 2005), and named entity recognition (Collins, 2002c).
    Page 1, “Introduction”
  3. More specifically, one must learn a semantic parser that produces a plan pj using a formal meaning representation (MR) language introduced by Chen and Mooney (2011).
    Page 2, “Background”
  4. In a similar vein, when reranking semantic parses , Ge and Mooney (2006) chose as a reference parse the one which was most similar to the gold-standard semantic annotation.
    Page 3, “Modified Reranking Algorithm”
  5. Table 1 shows oracle accuracy for both semantic parsing and plan execution for single sentence and complete paragraph instructions for various values of n. For oracle parse accuracy, for each sentence, we pick the parse that gives the highest Fl score.
    Page 7, “Experimental Evaluation”
  6. Ge and Mooney (2006) employ a similar approach when reranking semantic parses .
    Page 7, “Experimental Evaluation”
  7. It has been shown to be effective for various natural language processing tasks including syntactic parsing (Collins, 2000; Collins, 2002b; Collins and Koo, 2005; Charniak and Johnson, 2005; Huang, 2008), semantic parsing (Lu et al., 2008; Ge and Mooney, 2006), part-of-speech tagging (Collins, 2002a), semantic role labeling (Toutanova et al., 2005), named entity recognition (Collins, 2002c).
    Page 8, “Related Work”
  8. to work on learning semantic parsers from execution output such as the answers to database queries (Clarke et al., 2010; Liang et al., 2011).
    Page 9, “Related Work”

See all papers in Proc. ACL 2013 that mention semantic parsing.

See all papers in Proc. ACL that mention semantic parsing.

Back to top.

Unigram

Appears in 8 sentences as: Unigram (8)
In Adapting Discriminative Reranking to Grounded Language Learning
  1. Long-range Unigram .
    Page 5, “Reranking Features”
  2. in the parse tree: f(L2 «a left) = l and f(L4 «A turn) 2 l. Two-level Long-range Unigram .
    Page 5, “Reranking Features”
  3. Unigram .
    Page 5, “Reranking Features”
  4. Grandparent Unigram .
    Page 5, “Reranking Features”
  5. b) Descended Action Unigram .
    Page 6, “Reranking Features”
  6. c) Grandparent Descended Action Unigram .
    Page 6, “Reranking Features”
  7. Same as Descended Action Unigram , but additionally includes the parent nonterminal as well as the current one: f(Turn(LEFT)|L2,L1) = l.
    Page 6, “Reranking Features”
  8. d) Long-range Descended Action Unigram .
    Page 6, “Reranking Features”

See all papers in Proc. ACL 2013 that mention Unigram.

See all papers in Proc. ACL that mention Unigram.

Back to top.

Bigram

Appears in 4 sentences as: Bigram (3) bigram (1)
In Adapting Discriminative Reranking to Grounded Language Learning
  1. Bigram .
    Page 5, “Reranking Features”
  2. Indicates whether a given bigram of nonterminal/terminals occurs for given a parent nonterminal: f (L1 —> L2 : L3) = l.
    Page 5, “Reranking Features”
  3. Grandparent Bigram .
    Page 5, “Reranking Features”
  4. Same as Bigram , but also includes the nonterminal above the parent nonterminal: f(L3 —> L5 : L6|L1) = l.
    Page 5, “Reranking Features”

See all papers in Proc. ACL 2013 that mention Bigram.

See all papers in Proc. ACL that mention Bigram.

Back to top.

language acquisition

Appears in 3 sentences as: language acquisition (3)
In Adapting Discriminative Reranking to Grounded Language Learning
  1. We adapt discriminative reranking to improve the performance of grounded language acquisition , specifically the task of learning to follow navigation instructions from observation.
    Page 1, “Abstract”
  2. Grounded language acquisition involves learning to comprehend and/or generate language by simply observing its use in a naturally occurring context in which the meaning of a sentence is grounded in perception and/or action (Roy, 2002; Yu and Ballard, 2004; Gold and Scassel-lati, 2007; Chen et al., 2010).
    Page 1, “Introduction”
  3. However, to our knowledge, there has been no previous attempt to apply discriminative reranking to grounded language acquisition , where gold-standard reference parses are not typically available for training reranking models.
    Page 8, “Related Work”

See all papers in Proc. ACL 2013 that mention language acquisition.

See all papers in Proc. ACL that mention language acquisition.

Back to top.

PDF available from www.aclweb.org.
Send us an email