Fast Online Lexicon Learning for Grounded Language Acquisition
Chen, David

Article Structure

Abstract

Learning a semantic lexicon is often an important first step in building a system that learns to interpret the meaning of natural language.

Introduction

Learning to understand the semantics of human languages has been one of the ultimate goals of natural language processing (NLP).

Background

A common way to learn a leXicon across many different contexts is to find the common parts of the formal representations associated with different occurrences of the same words or phrases (Siskind, 1996).

Online Lexicon Learning Algorithm

While the algorithm presented by Chen and Mooney (2011) produced good lexicons, it only works in batch settings and does not scale well to large datasets.

Collecting Additional Data with Mechanical Turk

One of the motivations for studying ambiguous supervision is the potential ease of acquiring large amounts of training data.

Experiments

We evaluate our new lexicon learning algorithm as well as the other modifications to the navigation system using the same three tasks as Chen and Mooney (2011).

Related Work

The earliest work on cross-situational word learning was by Siskind (1996) who developed a rule-based system to solve the referential ambiguity problem.

Conclusion

Learning the semantics of language from the perceptual context in which it is uttered is a useful approach because only minimal human supervision is required.

Topics

semantic parser

Appears in 17 sentences as: semantic parser (7) Semantic Parsers (1) semantic parsers (7) semantic parser’s (1) semantic parsing (1)
In Fast Online Lexicon Learning for Grounded Language Acquisition
  1. Once a semantic parser is trained, it can be used at test time to transform novel instructions into formal navigation plans which are then carried out by a virtual robot (MacMahon et al., 2006).
    Page 2, “Background”
  2. To train a semantic parser using KRISP (Kate and Mooney, 2006), they had to supply a MRG, a context-free grammar, for their formal navigation plan language.
    Page 4, “Online Lexicon Learning Algorithm”
  3. The second task is evaluating the performance of the semantic parsers trained on the disambiguated data.
    Page 6, “Experiments”
  4. For the second and third tasks, we train a semantic parser on the automatically disambiguated data, and test on sentences from the third, unseen map.
    Page 6, “Experiments”
  5. Other than the modifications discussed, we use the same components as their system including using KRISP to train the semantic parsers and using the execution module from MacMahon et al.
    Page 6, “Experiments”
  6. Table 3: Partial parse accuracy of the semantic parsers trained on the disambiguated navigation plans.
    Page 6, “Experiments”
  7. 5.2 Training Semantic Parsers
    Page 6, “Experiments”
  8. Next we look at the performance of the semantic parsers trained on the inferred navigation plans.
    Page 6, “Experiments”
  9. Using the new MRG for KRISP to train the semantic parser produced slightly lower precision but higher recall, with similar overall F1 score.
    Page 6, “Experiments”
  10. Using the new MRG to train the semantic parsers further improved performance on both tasks.
    Page 6, “Experiments”
  11. The trained semantic parser’s precision, recall, and F1 were 88.87, 58.76, and 70.74, respectively.
    Page 7, “Experiments”

See all papers in Proc. ACL 2012 that mention semantic parser.

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

Back to top.

natural language

Appears in 11 sentences as: natural language (11)
In Fast Online Lexicon Learning for Grounded Language Acquisition
  1. Learning a semantic lexicon is often an important first step in building a system that learns to interpret the meaning of natural language .
    Page 1, “Abstract”
  2. Learning to understand the semantics of human languages has been one of the ultimate goals of natural language processing (NLP).
    Page 1, “Introduction”
  3. Traditional learning approaches have relied on access to parallel corpora of natural language sentences paired with their meanings (Mooney, 2007; Zettlemoyer and Collins, 2007; Lu et al., 2008; Kwiatkowski et al., 2010).
    Page 1, “Introduction”
  4. By using a MRG that correlates better to the structure of natural language , we further improve the performance on the navigation task.
    Page 1, “Introduction”
  5. Formally, the system is given training data in the form: {(el,a1,w1),(eg,a2,w2),...,(en,an,wn)}, where 67; is a written natural language instruction, at, is an observed action sequence, and w, is a description of the virtual world.
    Page 2, “Background”
  6. KRISP learns string-kernel classifiers that maps natural language substrings to MRG production rules.
    Page 4, “Online Lexicon Learning Algorithm”
  7. Consequently, it is important that the production rules in the MRG mirror the structure of natural language (Kate, 2008).
    Page 4, “Online Lexicon Learning Algorithm”
  8. While these rules are quite expressive, they often do not correspond well to any words or phrases in natural language .
    Page 4, “Online Lexicon Learning Algorithm”
  9. While this process of expanding the production rules resulted in many more rules, these expanded rules usually correspond better with words or phrases in natural language .
    Page 4, “Online Lexicon Learning Algorithm”
  10. There are two types of data we are interested in collecting: natural language navigation instructions and follower data.
    Page 5, “Collecting Additional Data with Mechanical Turk”
  11. It verified that we are indeed collecting useful information and that non-experts are fully capable of training the system by demonstrating how to use natural language in relevant contexts.
    Page 8, “Experiments”

See all papers in Proc. ACL 2012 that mention natural language.

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

Back to top.

Mechanical Turk

Appears in 10 sentences as: Mechanical Turk (10)
In Fast Online Lexicon Learning for Grounded Language Acquisition
  1. We show that by changing the grammar of the formal meaning representation language and training on additional data collected from Amazon’s Mechanical Turk we can further improve the results.
    Page 1, “Abstract”
  2. gorithm can scale to larger datasets, we present results on collecting and training on additional data from Amazon’s Mechanical Turk .
    Page 2, “Introduction”
  3. We validate this claim by collecting additional training data for the navigation domain using Mechanical Turk (Snow et al., 2008).
    Page 5, “Collecting Additional Data with Mechanical Turk”
  4. Thus, we created two tasks on Mechanical Turk .
    Page 5, “Collecting Additional Data with Mechanical Turk”
  5. The instructions used for the follower problems were mainly collected from our Mechanical Turk instructor task with some of the instructions coming from data collected by MacMahon (2007) that was not used by Chen and Mooney (2011).
    Page 5, “Collecting Additional Data with Mechanical Turk”
  6. In addition to SGOLL and SGOLL with the new MRG, we also look at augmenting each of the training splits with the data we collected using Mechanical Turk .
    Page 6, “Experiments”
  7. training data with additional instructions and follower traces collected from Mechanical Turk produced the best results.
    Page 7, “Experiments”
  8. Even after incorporating the new Mechanical Turk data into the training set, SGOLL still takes much less time to build a lexicon.
    Page 7, “Experiments”
  9. We have performed a pilot data collection of new training examples using Mechanical Turk .
    Page 7, “Experiments”
  10. In addition, we showed that changing the MRG and collecting additional training data from Mechanical Turk further improve the performance of the overall navigation system.
    Page 8, “Conclusion”

See all papers in Proc. ACL 2012 that mention Mechanical Turk.

See all papers in Proc. ACL that mention Mechanical Turk.

Back to top.

n-gram

Appears in 9 sentences as: n-gram (9)
In Fast Online Lexicon Learning for Grounded Language Acquisition
  1. To learn the meaning of an n-gram 21), Chen and Mooney first collect all navigation plans 9 that co-occur with w. This forms the initial candidate meaning set for 21).
    Page 2, “Background”
  2. Even though they use beam-search to limit the size of the candidate set, if the initial candidate meaning set for a n-gram is large, it can take a long time to take just one pass through the list of all candidates.
    Page 3, “Online Lexicon Learning Algorithm”
  3. : function Update(training example (67;, 1%)) for n-gram w that appears in 67; do
    Page 3, “Online Lexicon Learning Algorithm”
  4. 14: Increase the count of examples, each n-gram w and each subgraph g 15: end function
    Page 3, “Online Lexicon Learning Algorithm”
  5. 18: function OutputLexicon() 19: for n-gram w that has been observed do
    Page 3, “Online Lexicon Learning Algorithm”
  6. Specifically, for each n-gram w, we look at all the subgraphs 9 that co-occurred with it, and compute a score for the pair (w, 9).
    Page 4, “Online Lexicon Learning Algorithm”
  7. In contrast to Chen and Mooney’s algorithm though, we add the constraint of minimum support by not creating lexical entries for any n-gram w that appeared in less than minSup training examples.
    Page 4, “Online Lexicon Learning Algorithm”
  8. Moreover, the memory requirement can be quite high if there are many different subgraphs 9 associated with each n-gram w. To deal with such scalability issues, we could use beam-search and only keep the top k: candidates associated with each w. Another important step is to define canonical orderings of the nodes in the graphs.
    Page 4, “Online Lexicon Learning Algorithm”
  9. In contrast to the previous approach that computed common subgraphs between different contexts in which an n-gram appeared, we instead focus on small, connected subgraphs and introduce an algorithm, SGOLL, that is an order of magnitude faster.
    Page 8, “Conclusion”

See all papers in Proc. ACL 2012 that mention n-gram.

See all papers in Proc. ACL that mention n-gram.

Back to top.

learning algorithm

Appears in 7 sentences as: learning algorithm (7)
In Fast Online Lexicon Learning for Grounded Language Acquisition
  1. Their lexicon learning algorithm finds the common connected subgraph that occurs with a word by taking intersections of the graphs that represent the different contexts in which the word appears.
    Page 1, “Introduction”
  2. In addition to the new lexicon learning algorithm , we also look at modifying the meaning representation grammar (MRG) for their formal semantic language.
    Page 1, “Introduction”
  3. In this section we review the leXicon learning algorithm introduced by Chen and Mooney (2011) as well as the overall task they designed to test semantic understanding of navigation instructions.
    Page 2, “Background”
  4. In addition to introducing a new lexicon learning algorithm , we also made another modification to the original system proposed by Chen and Mooney (2011).
    Page 4, “Online Lexicon Learning Algorithm”
  5. We evaluate our new lexicon learning algorithm as well as the other modifications to the navigation system using the same three tasks as Chen and Mooney (2011).
    Page 6, “Experiments”
  6. Here SGOLL has a decidedly large advantage over the lexicon learning algorithm from Chen and Mooney, requiring an order of magnitude less time to run.
    Page 7, “Experiments”
  7. We have introduced a novel, online lexicon learning algorithm that is much faster than the one proposed by Chen and Mooney and also performs better on the navigation tasks they devised.
    Page 7, “Experiments”

See all papers in Proc. ACL 2012 that mention learning algorithm.

See all papers in Proc. ACL that mention learning algorithm.

Back to top.

meaning representation

Appears in 4 sentences as: Meaning Representation (1) meaning representation (2) meaning representations (1)
In Fast Online Lexicon Learning for Grounded Language Acquisition
  1. We show that by changing the grammar of the formal meaning representation language and training on additional data collected from Amazon’s Mechanical Turk we can further improve the results.
    Page 1, “Abstract”
  2. Building a lexicon of the formal meaning representations of words and phrases, either implicitly or explicitly, is usually an important step in inferring the meanings of entire sentences.
    Page 1, “Introduction”
  3. In addition to the new lexicon learning algorithm, we also look at modifying the meaning representation grammar (MRG) for their formal semantic language.
    Page 1, “Introduction”
  4. 3.1 Changing the Meaning Representation Grammar
    Page 4, “Online Lexicon Learning Algorithm”

See all papers in Proc. ACL 2012 that mention meaning representation.

See all papers in Proc. ACL that mention meaning representation.

Back to top.

n-grams

Appears in 4 sentences as: n-grams (4)
In Fast Online Lexicon Learning for Grounded Language Acquisition
  1. and the corresponding navigation plan, we first segment the instruction into word tokens and construct n-grams from them.
    Page 4, “Online Lexicon Learning Algorithm”
  2. From the corresponding navigation plan, we find all connected subgraphs of size less than or equal to m. We then update the co-occurrence counts between all the n-grams w and all the connected subgraphs 9.
    Page 4, “Online Lexicon Learning Algorithm”
  3. We also update the counts of how many examples we have encountered so far and counts of the n-grams w and subgraphs 9.
    Page 4, “Online Lexicon Learning Algorithm”
  4. This is mainly due to the additional minimum support constraint we added which discards many noisy lexical entries from infrequently seen n-grams .
    Page 6, “Experiments”

See all papers in Proc. ACL 2012 that mention n-grams.

See all papers in Proc. ACL that mention n-grams.

Back to top.

co-occurrence

Appears in 3 sentences as: co-occurrence (3)
In Fast Online Lexicon Learning for Grounded Language Acquisition
  1. 10: for connected subgraph g of p; such that the size of g is less than or equal to m do 11: Increase the co-occurrence count of g and w by l 12: end for 13: end for
    Page 3, “Online Lexicon Learning Algorithm”
  2. From the corresponding navigation plan, we find all connected subgraphs of size less than or equal to m. We then update the co-occurrence counts between all the n-grams w and all the connected subgraphs 9.
    Page 4, “Online Lexicon Learning Algorithm”
  3. This allows us to determine if two graphs are identical in constant time and also lets us use a hash table to quickly update the co-occurrence and subgraph counts.
    Page 4, “Online Lexicon Learning Algorithm”

See all papers in Proc. ACL 2012 that mention co-occurrence.

See all papers in Proc. ACL that mention co-occurrence.

Back to top.

end-to-end

Appears in 3 sentences as: End-to-end (1) end-to-end (2)
In Fast Online Lexicon Learning for Grounded Language Acquisition
  1. Finally, the third task is to complete the end-to-end navigation task.
    Page 6, “Experiments”
  2. Finally, we evaluate the system on the end-to-end navigation task.
    Page 6, “Experiments”
  3. Table 4: End-to-end navigation task completion rates.
    Page 7, “Experiments”

See all papers in Proc. ACL 2012 that mention end-to-end.

See all papers in Proc. ACL that mention end-to-end.

Back to top.

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