Dependency Parsing: Unveiling the Structure of Sentences

Have you ever wondered how computers understand the relationships between words in a sentence? Dependency parsing is a powerful technique in natural language processing (NLP) that helps us do just that. It focuses on identifying the dependencies between words, revealing the grammatical structure of a sentence in a way that's intuitive and computationally useful.

What is Dependency Parsing?

Dependency parsing analyzes the grammatical structure of a sentence by establishing links between individual words. These links, or dependencies, show which word is governed by (or depends on) another. This is different from phrase structure parsing, which focuses on grouping words into nested phrases. Instead, dependency parsing creates a tree-like structure where each word is connected to its head (the word it depends on) and labeled with a dependency relation, indicating the type of relationship between them.

Imagine the sentence: "United canceled the flight." A dependency parser would identify "canceled" as the root of the sentence and link "United" to "canceled" with a relation like "NSUBJ" (nominal subject), and "flight" to "canceled" with a relation like "OBJ" (object).

Key Concepts in Dependency Parsing

Head: The word that governs another word in a dependency relation. Think of it as the parent in the tree structure.
Dependent: The word that is governed by a head. It's the child in the tree structure.
Dependency Relation: A label that describes the grammatical relationship between the head and the dependent (e.g., subject, object, modifier).
Root: The main verb of the sentence, which has no incoming dependencies.

Common Dependency Relations

There are various types of dependency relations that capture the different ways words can relate to each other. Here are some examples, illustrating the head and the dependent.

Relation	Example with Head and Dependent	Explanation
NSUBJ	United canceled the flight.	Nominal subject of the verb.
OBJ	United diverted the flight to Reno.	Direct object of the verb.
IOBJ	We booked her the flight to Miami.	Indirect object of the verb.
COMPOUND	We took the morning flight.	Parts of a compound word
NMOD	flight to Houston.	Nominal modifier.
AMOD	Book the cheapest flight.	Adjectival modifier.
DET	The flight was canceled.	Determiner.
CONJ	We flew to Denver and drove to Steamboat.	Conjunct.
CASE	Book the flight through Houston.	Case marker.
CC	We flew to Denver and drove to Steamboat.	Coordinating Conjunction.
APPOS	United, a unit of UAL, matched the fares.	Appositional modifier.

Dependency Trees: Rules and Properties

The result of dependency parsing is a dependency tree, a directed graph showing the relationships between words. To ensure the tree is well-formed and computationally useful, it adheres to certain constraints:

Single Root: There is only one root node, which represents the main verb or clause of the sentence. This root has no incoming dependencies.
Single Head: Every word (except the root) has exactly one incoming dependency, meaning each word has only one head.
Connectivity: There is a unique path from the root to every word in the sentence. This ensures all words are connected to the main structure of the sentence.

These rules guarantee that the dependency structure is connected, that each word depends on only one head, and that the entire sentence is connected to a single root.

Projectivity: When Word Order Matters

Projectivity is an additional constraint related to the order of words in the sentence. A dependency tree is projective if, for every dependency arc, all words lying between the head and the dependent are also dependents of the head (either directly or indirectly). In simpler terms, a dependency tree is projective if it can be drawn without any crossing edges.

For instance, consider the sentence: "JetBlue canceled our flight this morning which was already late." The relationship between "flight" and "late" is non-projective because "this" and "morning" fall between them, and there is no path from "flight" to "this" and "morning".

Projectivity becomes important for two reasons:

Many dependency treebanks (collections of sentences with their dependency structures) were automatically derived from phrase-structure treebanks, and these tend to be projective.
Some parsing algorithms, particularly transition-based parsers (discussed below), are designed to produce only projective trees.

While English is mostly projective, many other languages exhibit non-projective structures, making it important to consider non-projective parsing methods.

Dependency Treebanks: Learning from Data

Treebanks are essential resources for dependency parsing. They're used to train parsers, evaluate their accuracy, and study linguistic phenomena. These treebanks contain sentences annotated with their dependency structures, created either by human annotators or by correcting the output of automatic parsers. The largest open community project for dependency trees is the Universal Dependencies project.

The Universal Dependencies (UD) project is the largest and most prominent initiative in dependency parsing, offering annotated treebanks for almost 200 languages. It helps ensure the parser accuracy and can be used across multiple languages.

Here are a few examples from the Universal Dependencies project:

Spanish: Subiremos al tren a las cinco. “We will be boarding the train at five.”
Basque: Ekaitzak itsasontzia hondoratu du. “The storm has sunk the ship.”
Mandarin Chinese: 但我昨天才收到信 “But I didn’t receive the letter until yesterday”

Approaches to Dependency Parsing

There are two main approaches to dependency parsing:

1. Transition-Based Dependency Parsing

Transition-based parsing is a greedy approach that uses a set of predefined transitions to build the dependency tree incrementally. It relies on a stack, a buffer of input words, and an oracle that guides the parsing process by suggesting the next transition to apply.

The parser examines the top of the stack and the input buffer, making decisions based on the oracle's advice. These decisions build the parse structure in a single left-to-right pass over the input sentence.

Common Transition Operators:

LEFTARC: Asserts a dependency from the top of the stack to the second element on the stack, removing the second element.
RIGHTARC: Asserts a dependency from the second element on the stack to the top, removing the top element.
SHIFT: Moves the next word from the input buffer onto the stack.

For example, consider the sentence "Book me the morning flight". The parser would start with a stack containing the root node and an input buffer containing the sentence. It would then apply a series of SHIFT, LEFTARC, and RIGHTARC operations to build the dependency tree. A simplified trace might look like this:

SHIFT root onto stack
SHIFT "Book" onto the stack
SHIFT "me" onto the stack
RIGHTARC connects "Book" to "me"
...and so on

The main strength of transition-based parsing is its speed and simplicity. However, its greedy nature can lead to errors if the oracle makes a wrong decision early on.

The transition-based approach uses an oracle to train by supervised machine learning. It draws the data from dependency trees.

Generating training data

The data is generated by supplying orcale to sentences to be parsed along with its reference parses from the treebank.

Featured-based Classifier

These feature-based classifiers generally use the same features as part-of-speech tagging. The features include:

Word forms
Lemmas
Parts of speech
The head
The dependency relation to the head

Neural Classifier

A neural classifier is a standard architecture that passes the sentence through an encoder. It then takes the representation of the top two words on the stack and the first word of the buffer, concatenates them, and presents to a feedforward network that predicts the transition to take.

2. Graph-Based Dependency Parsing

Graph-based parsing takes a different approach. It views the dependency parsing problem as finding the highest-scoring dependency tree within a graph of all possible dependencies. These methods work by:

Encoding the search space as directed graphs
Employing methods drawn from graph theory to search the space for optimal solutions.

Instead of making greedy decisions, graph-based parsers score entire trees and select the one with the maximum score.

Key Steps in Graph-Based Parsing:

Create a complete graph: Construct a directed graph where each word is a node and there's a directed edge between every pair of words, representing all possible head-dependent relationships.
Assign scores to edges: Use a scoring function to assign a score to each edge in the graph, reflecting the likelihood of that dependency.
Find the maximum spanning tree: Search for the maximum spanning tree (MST) of the graph. The MST is the tree with the highest total score, representing the most likely dependency tree for the sentence.

Finding the maximum spanning tree can be done efficiently using algorithms like the Chu-Liu-Edmonds algorithm. Unlike transition-based parsers, graph-based parsers can produce non-projective trees, making them suitable for languages with flexible word order.

Assigning scores

Edge-factored parsing models make the assumption that the score for the tree is the sum of the scores of the edges that compromise the tree.

Feature-based Algorithm

Wordforms, lemmas, and parts of speech of the headword and its dependent.
Corresponding features from the contexts before, after and between the words.
Word embeddings.
The dependency relation itself.
The direction of the relation (to the right or left).
The distance from the head to the dependent.

Neural Algorithm

It runs the sentence through an encoder, and then passes the encoded representation of the two words through a network that estimates a score for the edge.

Evaluation Metrics for Dependency Parsing

To evaluate the performance of dependency parsers, we use metrics that measure the accuracy of the predicted dependency trees compared to a gold-standard treebank.

Common Evaluation Metrics:

Labeled Attachment Score (LAS): The percentage of words that are assigned both the correct head and the correct dependency relation.
Unlabeled Attachment Score (UAS): The percentage of words that are assigned the correct head, regardless of the dependency relation label.
Label Accuracy Score (LS): The percentage of tokens with correct labels, ignoring where the relations are coming from.

Higher scores indicate better parser performance. These metrics help us compare different parsing algorithms and track improvements in accuracy.

Real-World Applications of Dependency Parsing

Dependency parsing is a valuable tool in various NLP applications:

Machine Translation: Understanding the dependency structure helps in translating sentences accurately between languages.
Information Extraction: Identifying relationships between entities in text, such as people, organizations, and locations.
Question Answering: Analyzing the dependency structure helps in understanding the question and finding the relevant information in the text.
Sentiment Analysis: Identifying the relationships between words helps in understanding the sentiment expressed in the sentence.

Conclusion

Dependency parsing is a fundamental technique in NLP that provides a way to understand the grammatical structure of sentences by revealing the relationships between words. By identifying the head, dependent, and dependency relation for each word, we can gain valuable insights into the meaning and intent of the text. With various approaches and ongoing advancements, dependency parsing continues to play a vital role in helping computers understand and process human language.

Data Coder

Search This Blog