Shift Reduce Parser

java -cp .:stanford-parser.jar:stanford-postagger-3.5.0.jar:stanford-srparser-2014-10-23-models.jar ShiftReduceDemo -model edu/stanford/nlp/models/srparser/englishSR.ser.gz -tagger english-left3words-distsim.tagger

Note that we need to include the jar file where the parser models are stored,
as well as specifying the tagger model (which came from the Stanford Tagger
package). This should load the tagger, parser, and parse the example sentence,
finishing in under 20 seconds. The output:

> Reading POS tagger model from stanford-postagger-full-2014-10-23/models/english-left3words-distsim.tagger ... done [1.2 sec].  
> Loading parser from serialized file edu/stanford/nlp/models/srparser/englishSR.ser.gz ...done [14.8 sec].  
>  (ROOT (S (NP (PRP$ My) (NN dog)) (VP (VBZ likes) (S (VP (TO to) (VP (VB shake) (NP (PRP$ his) (VBN stuffed) (NN chickadee) (NN toy)))))) (. .))) `

### How Shift-Reduce Parsing Works

The Shift-Reduce Parser parses by maintaining a state of the current parsed
tree, with the words of the sentence on a queue and partially completed trees
on a stack, and applying transitions to the state until the queue is empty and
the current stack only contains a finished tree.

The initial state is to have all of the words in order on the queue, with an
empty stack. The transitions which can be applied are:

  * Shift. A word moves from the queue onto the stack. 
  * Unary reduce. The label of the first constituent on the stack changes. There is a different unary transition for every possible unary node in the treebank used for training. 
  * Binary reduce. The first two nodes on the stack are combined with a new label. These are either right sided or left sided, indicating which child is treated as the head. Once again, there is a different binary transition for every possible binary node. This includes temporary nodes, as trees are built as binarized trees and then later debinarized. 
  * Finalize. A tree is not considered finished until the parser chooses the finalize transition. 
  * Idle. In the case of beam searching, Zhu et al. showed that training an idle transition compensates for different candidate trees using different numbers of transitions. 

Transitions are determined by featurizing the current state and using a
multiclass perceptron to determine the next transition. Various legality
constraints are applied to the transitions to make sure the state remains
legal and solvable.

Part-of-speech tags are not assigned by this parser, and are in fact used as
features. This is accomplished by pretagging the text, meaning the `pos`
annotator needs to be used in StanfordCoreNLP, for example.

Training is conducted by iterating over the trees repeatedly until some
measure of convergence is reached. There are various ways to process the trees
during each iteration. The one used by default is to start from the basic
state and apply the transitions chosen by the parser until it gets a
transition wrong, i.e., it can no longer rebuild the gold tree. The features
used at the time of the incorrect decision have their weights adjusted, with
the correct transition getting the feature weights increased and the incorrect
transition decreased.

#### Beam Search

In general, the parser uses greedy transitions, continuing until the sentence
is finalized. It is also possible to use it in beam search mode, though. In
this mode, the parser keeps an agenda of the highest scoring candidate states.
At each step, each of the states has a transition applied, updating the agenda
with the new highest scoring states. This process continues until the highest
scoring state on the agenda is finalized.

Models need to be specifically trained to work with beam search. Otherwise,
scores actually get worse. While this increases accuracy quite a bit, it also
has the drawback of significantly increasing the size of the model. A model
not trained for beam search only ever has features which were present in
states reached by the gold sequence of transitions on the gold training trees.
A model trained to use beam search trains negative features for incorrect
states on the beam, resulting in many more features and therefore a much
larger model.

### Training the Shift-Reduce Parser

Read this section if you want to train your own Shift-Reduce Parser. This
requires you have data in the standard Treebank format.

#### Basic Guidelines

New English `WSJ` models can be trained as follows:

Concretely, on the NLP machines, this would be

More details on how it trains are below. The key summary is that some time
later, probably an hour on a decent machine, there will be a new file
`model.ser.gz` which is the newly trained Shift-Reduce Parser. This model can
be tested as follows:

However, this ignores a key aspect of the Shift-Reduce Parser. This parser
does not produce its own tags and instead expects to use automatically
produced tags as features when parsing. The commands above will work, but they
will train a model using the gold tags in the treebank. It is generally better
to train on the tags provided by the tagger which will be used as test time.
This can be done with the flags `-pretag -taggerSerializedFile <tagger>`

The `bidirectional` model is significantly slower than the `left3words` model,
but is somewhat more accurate. It is still faster than the parsing itself.
Alternatively, one can just use the `left3words` tagger for better speed and
slightly less accuracy.

#### Other Languages

It is possible to train the Shift-Reduce Parser for languages other than
English. An appropriate HeadFinder needs to be provided. This and other
options are handled by specifying the `-tlpp` flag, which lets you choose the
class for a `TreebankLangParserParams`. A language appropriate tagger is also
required.

For example, here is a command used to train a Chinese model. The options not
already explained are explained in the next section.

The resulting model is both faster and more accurate than any other model we
have, including the Chinese RNN model.

#### FeatureFactory classes

The features for the Perceptron are extracted using a FeatureFactory. By
default, the parser uses
`edu.stanford.nlp.parser.shiftreduce.BasicFeatureFactory`. This FeatureFactory
includes most of the basic features you would want, such as features for the
head word of the current stack node and several previous stack nodes, the word
and tag of incoming queue items, and combinations of those strings.

Another included FeatureFactory is the DistsimFeatureFactory. This can be used
by setting the `-featureFactory` argument:

Multiple FeatureFactory classes can be combined by using a semicolon separated
list. For example: