![](https://csdnimg.cn/release/download_crawler_static/3205820/bg13.jpg)
1.2. DEPENDENCY PARSING 7
Broadly speaking, these approaches can be divided into two classes, which we will call data-
driven and grammar-based, respectively. An approach is data-driven if it makes essential use of
machine learning from linguistic data in order to parse new sentences. An approach is grammar-based
if it relies on a formal grammar, defining a formal language, so that it makes sense to ask whether a
given input sentence is in the language defined by the grammar or not. It is important to note that
these categorizations are orthogonal, since it is possible for a parsing method to make essential use
of machine learning and use a formal grammar, hence to be both data-driven and grammar-based.
However, most of the methods that we cover fall into one of these classes only.
The major part of the book, chapters 3–4 to be exact, is devoted to data-driven methods for
dependency parsing, which have attracted the most attention in recent years. We focus on supervised
methods, that is, methods presupposing that the sentences used as input to machine learning have
been annotated with their correct dependency structures. In supervised dependency parsing, there
are two different problems that need to be solved computationally. The first is the learning problem,
which is the task of learning a parsing model from a representative sample of sentences and their
dependency structures. The second is the parsing problem, which is the task of applying the learned
model to the analysis of a new sentence.
4
We can represent this as follows:
• Learning: Given a training set
D of sentences (annotated with dependency graphs), induce a
parsing model M that can be used to parse new sentences.
• Parsing: Given a parsing model M and a sentence S, derive the optimal dependency graph G
for S according to M.
Data-driven approaches differ in the type of parsing model adopted, the algorithms used to learn
the model from data, and the algorithms used to parse new sentences with the model. In this book,
we focus on two classes of data-driven methods, which we call transition-based and graph-based,
respectively. These classes contain most of the methods for data-driven dependency parsing that
have been proposed in recent years.
Transition-based methods start by defining a transition system, or state machine, for mapping
a sentence to its dependency graph. The learning problem is to induce a model for predicting the
next state transition, given the transition history, and the parsing problem is to construct the optimal
transition sequence for the input sentence,given the induced model.This is sometimes referred to as
shift-reduce dependency parsing, since the overall approach is inspired by deterministic shift-reduce
parsing for context-free grammars. Transition-based approaches are treated in chapter 3.
Graph-based methods instead define a space of candidate dependency graphs for a sentence.
The learning problem is to induce a model for assigning scores to the candidate dependency graphs
for a sentence, and the parsing problem is to find the highest-scoring dependency graph for the input
sentence, given the induced model. This is often called maximum spanning tree parsing, since the
problem of finding the highest-scoring dependency graph is equivalent, under certain assumptions,
4
The parsing problem is sometimes referred to as the inference problem or decoding problem, which are the general terms used in
machine learning for the application of a learned model to new data.