WASP User's Manual

1. What is WASP?

WASP is a statistical learning algorithm for semantic parsing. Semantic parsing is the construction of complete, formal meaning representations given input sentences. A semantic parser is learned given a set of sentences annotated with their correct meaning representations.

Here is a sample meaning representation (MR) written in a meaning-representation language (MRL) called CLang, which is used for encoding coach advice given to simulated soccer-playing agents in the RoboCup domain:

((bowner our {4}) (do our {6} (pos (left (half our)))))

If our player 4 has the ball, then our player 6 should stay in the left side of our half.

2. What is in this Distribution?

This distribution contains:

• The code for training the semantic parser from training data;
• The code for running the learned semantic parser;
• The code for evaluating the learned semantic parser;
• Corpora in two application domains: RoboCup and Geoquery, complete with sample configuration files and domain-specific code so that you can train and run the semantic parser right away! (These corpora were used in Kate et al. (2005) and Wong & Mooney (2006).)

3. How to Use WASP?

First, you have to compile the Java code. All Java code is in the src directory. To compile the code, do the following:

cd src
find . -name '*.java' | xargs javac -O

All programs are in the wasp.main and wasp.main.eval packages:

• wasp.main.Trainer - the program that trains the semantic parser from training data;
• wasp.main.Parser - the program that does semantic parsing based on previously-learned parsing models;
• wasp.main.eval.ParserEvaluator - the program that evaluates the semantic parser by reading its output MRs and comparing them against the gold-standard MRs. This program also generates statistics using various evaluation metrics.

The following sections will quickly walk you through the training, testing and evaluation stages.

3.1. Training the Semantic Parser

The program that trains the semantic parser requires the following command-line arguments to run:

java wasp.main.Trainer config-file model-dir mask-file

• config-file - the configuration file that contains the current settings for the trainer;
• model-dir - the directory for storing the learned semantic parsing model;
• mask-file - the example mask that specifies the training set.

For your convenience, we included two sample configuration files in this distribution, namely data/robocup-clang/config (for the RoboCup domain) and data/geo-funql/config (for the Geoquery domain). Let us take a look at the configuration file for RoboCup:

wasp.nl=en
wasp.mrl=robocup-clang
wasp.mrl.grammar=/usr/share/wasp/data/robocup-clang/mrl-grammar
wasp.corpus.file=/usr/share/wasp/data/robocup-clang/corpus.xml
wasp.align.model=giza++
wasp.align.giza++.exec=/usr/local/bin/GIZA++
wasp.translation.model=scfg
wasp.scfg.init=/usr/share/wasp/data/robocup-clang/scfg-init-rules

The configuration file is a Java property list, where each line is a key-value pair. The most important settings are at the top:

3.2. Using the Semantic Parser

The program that does semantic parsing based on previously-learned translation models accepts similar command-line arguments as the trainer does:

java wasp.main.Parser config-file model-dir mask-file output-file

• config-file - the configuration file that contains the current settings for the parser;
• model-dir - the directory where the learned semantic parsing model is stored (this corresponds to the output directory of the trainer);
• mask-file - the example mask that specifies the test set;
• output-file - the output XML file for storing the automatically-generated parses.

The configuration file is the same as before. However, there is a parser-specific setting that you need to specify:

wasp.kbest=1

This specifies the maximum number of top-scoring parses to return. Set this to 1 for Viterbi decoding. This setting is ignored by the trainer and the parser evaluator.

The output XML file follows roughly the same format as the corpus file. Instead of gold-standard MRs, it contains the top-scoring translations given by the parser. Some examples may not have any translations at all. Like the trainer, the Parser program writes a message log to the standard error stream.

3.3. Evaluating the Semantic Parser

The ParserEvaluator program reads the output of the parser, compares the top-scoring parse of each example against the gold-standard MR, and generates statistics using various evaluation metrics:

java wasp.main.eval.ParserEvaluator config-file output-file input-file-1 input-file-2 ...

• config-file - the configuration file that contains the current settings for the parser evaluator;
• output-file - the output file for storing the evaluation results;
• input-file-n - the input XML files that contain parses generated by the parser.

The configuration file is the same as before. The input XML files are the output of the Parser program. If there are more than one input files, then each one should be produced by a separately-trained semantic parser. For example, there would be one input file for each fold in the 10-fold cross validation setting. Macro-averaging is used to obtain average statistics across all folds.

The parser evaluator generates the following statistics:

• Precision - the percentage of translations that are correct;
• Recall - the percentage of test sentences that are correctly translated;
• F-measure - the harmonic mean of precision and recall.

The definition of correctness is domain-specific. For example, in the RoboCup domain, an MR translation is correct if it exactly matches the gold-standard MR, up to permutation of arguments of certain predicates (e.g. and and or).

The output of the parser evaluator is a plain text file with the following format: It starts with the main section where the gold-standard MRs and the automatically-generated parses are listed. Incorrect parses are preceded by asterisks (*). After the main section are the statistics. There is a section for each evaluation metric. Here is a sample section for the precision metric:

begin precision
mean 0.8636014401946894
95%-confidence-interval 0.8173097234842457 0.9098931569051332
end precision

Obviously, the first line begins the section for precision, and the last line ends it. The second line is the mean precision across all input files. The third line is the range of values within which the mean precision may lie with 95% confidence. The sections for recall and F-measure follow the same format.

There is also a separate section for the precision-recall (PR) curve. A PR curve is obtained by varying the score threshold. In a PR curve, the x axis is the recall level, and the y axis is the mean precision. A PR curve is represented as a list of (x, y) pairs.

4. How to Create New Application Domains?

Why stick with the sample data sets that are given to you? Create your own data set in a new application domain! This section explains everything about extending WASP to your exciting new application.

Here are the things you need to do to create a new application domain:

1. Find an unambiguous context-free grammar of the target MRL. Write it down in an MRL grammar file.
2. Create a corpus.
3. Create a string tokenizer specific to the target MRL.
4. Define what it means for an MR to be correct in this domain.
5. Create a set of initial SCFG rules, if necessary.
6. Write a bit of code to link the pieces together.

We will cover these tasks in the following subsections.

4.1. Creating an MRL Grammar File

Recall that WASP requires the target MRL to have an unambiguous context-free grammar, and the MRL grammar file is a text file that contains all production rules of this grammar. Each line of this file represents a production rule. Here is a sample production rule:

*n:Action -> ({ ( pos *n:Region ) })

The token before the arrow (->) is the LHS nonterminal. Everything between the ({ and }) tokens are the RHS string of terminals and nonterminals. Tokens with the prefix *n: are nonterminals. So both *n:Action and *n:Region are nonterminals. On the other hand, (, pos and ) are terminal symbols. All symbols must be separated by whitespace. Also there must be space between the LHS nonterminal and the arrow, and so on.

4.2. Creating a Corpus

The corpus is stored in an XML file. Note that the file must be valid XML! A minimal corpus file should look like this:

<?xml version="1.0"?>
<examples>
<example id="0">
<nl lang="en">
...
</nl>
<mrl lang="robocup-clang">
...
</mrl>
</example>
...
</examples>

All examples have a unique ID which is a non-negative integer. Every sentence has a language tag (e.g. en). There is a language tag for every MR as well (e.g. robocup-clang). These tags correspond to those specified in the configuration file (wasp.nl and wasp.mrl, respectively).

4.3. Creating an MRL-Specific Tokenizer

Every MRL has its own string tokenizer. You provide one by extending the class wasp.mrl.MRLGrammar:

public class MyMRLGrammar extends MRLGrammar {
    public Symbol[] tokenize(String str) {
        ...
    }
    public String combine(Symbol[] syms) {
        ...
    }
    ...
}

The tokenize method tokenizes an MRL string. This method returns an array of symbols. Symbols are created using the read(String token) method of the class wasp.data.Symbol. The combine method is simply the inverse of tokenize.

The classes wasp.domain.RoboCupCLangGrammar and wasp.domain.GeoFunqlGrammar implement the RoboCup and Geoquery tokenizers.

4.4. Defining the Notion of MR Correctness

The definition of MR correctness is domain-specific. For example, in the RoboCup domain, an MR is correct if it exactly matches the gold-standard MR. In the Geoquery domain, a query is correct if it retrieves the same answer from the U.S. geography database as the gold-standard query does.

Again, you define the notion of MR correctness in your domain by extending the class wasp.mrl.MRLGrammar:

public class MyMRLGrammar extends MRLGrammar {
    ...
    public boolean[][] evaluate(Examples examples, Examples gold) {
        ...
    }
    ...
}

The evaluate method takes two sets of examples, one having the MR translations to evaluate (examples), one having the gold-standard MRs (gold), and returns a list of Boolean arrays such that the i-th element of the j-th array is true if and only if the i-th top-scoring parse of the j-th example in examples is correct. This method allows for batch processing of MRs. It is useful because processing each MR individually can be very inefficient (e.g. in the Geoquery domain).

4.5. Creating Initial SCFG Rules

Currently, the only translation model supported is based on synchronous context-free grammars (SCFG). Here is a sample SCFG rule:

*n:Directive -> ({ position *n:Player#1 *n:Region#2 })({ ( do *n:Player#1 ( pos *n:Region#2 ) ) })

The token before the arrow (->) is the LHS nonterminal. Between the ({ and })({ tokens is the NL portion of the RHS string. Between the })({ and }) tokens is the MRL portion of the RHS string. All nonterminals on the RHS are indexed, as indicated by the non-negative integers following the pound signs (#). For every nonterminal in the NL portion of the RHS string, there is exactly one identical nonterminal in the MRL portion that has the same index. The same is true for wildcard symbols.

Given an MRL grammar, a set of initial rules are always created and added to the learned SCFG:

• Given a unary MRL production *n:X -> ({ *n:Y }), the unary rule *n:X -> ({ *n:Y#1 })({ *n:Y#1 }) is always added to the SCFG.
• Given a MRL production *n:X -> ({ *t:Y }), where *t:Y is a wildcard symbol, the rule *n:X -> ({ *t:Y#1 })({ *t:Y#1 }) is always added to the SCFG.

It is sometimes useful to provide additional initial rules that are always included in the learned SCFG. For example, initial rules can be used to represent a dictionary of foreign terms that refer to domain-specific entities:

*n:CityName -> ({ ausuchin })({ ' austin ' })
*n:CityName -> ({ nyuu yooku })({ ' new york ' })
...

Additional initial rules are stored in a text file. Each line of this file represents an SCFG rule. This file is used by the trainer, and it only accepts rules whose RHS symbols are all terminals, with no word gaps on the NL side. The absolute pathname of the text file is specified in the configuration file via the key wasp.scfg.init.

Following an SCFG rule, there can be a list of modifiers. One such modifier is tied-to rule, where rule is the representation of another rule with the same LHS nonterminal. It is said that the two rules have their parameters tied. This can be used for more robust parameter estimation.

4.6. Putting the Pieces Together

There are a few more methods of the class MRLGrammar that you have to implement:

public class MyMRLGrammar extends MRLGrammar {
    ...
    public int getStart() {
        ...
    }
    public int countNonterms() {
        ...
    }
    protected void readModifiers(Production prod, String[] line, Int index) {
        ...
    }
}

The getStart method returns the integer ID of the start symbol of the MRL grammar. You can get the integer ID using the method Dictionary.nonterm(String str). The countNonterms method returns the number of possible nonterminals in this grammar. The readModifiers method allows you to define your own MRL production modifiers (see the Javadoc for more information). If you do not want to define any modifiers, you can leave this method empty.

After defining your own subclass of MRLGrammar, you have to link it to a new language tag. Language tags are defined in the MRLGrammar.createNew() method. You should use the same tag in your corpus and your configuration file. Your configuration file should also point to the MRL grammar file, the corpus, and the initial SCFG rules that you have created. Once you have done that, you are all set!

5. Other Topics

5.1. Fully-Supervised WASP

Instead of relying on GIZA++, the trainer can extract SCFG rules from gold-standard word alignments. Gold-standard word alignments are generally less noisy, and the resulting semantic parser is often much more precise, although word alignments are more time-consuming to annotate than plain MRs.

The RoboCup and Geoquery corpora included in this distribution come with gold-standard word alignments. These alignments are derived from previous annotations by Ge & Mooney (2005).

The gold-standard word alignments can be found inside the augsyn tags in the corpus XML files. The tags are called augsyn because the annotations are originally semantically-augmented parse trees (Ge & Mooney, 2005). For clarity, the annotations that we provide are degenerate parse trees that are only one level deep. (Full syntactic parses can be found inside the syn tags.)

Consistent with the use of MRL productions in WASP, semantic labels in our corpora are pointers to nodes in the gold-standard MR parse trees:

If-[Rule:1] the ball-[Condition:2] is-[Condition:2] in-[Condition:2] our-[Team:4] half-[Region:3] ...