Download Dependency Parsing PDF

TitleDependency Parsing
LanguageEnglish
File Size439.0 KB
Total Pages54
Table of Contents
                            Introduction
Dependency Parsing - Output
Dependency Parsing - Approaches
Graph-based Dependency Parsing
Chu-Liu-Edmonds
Arc Scoring / Learning
                        
Document Text Contents
Page 1

Graph-based Dependency Parsing
(Chu-Liu-Edmonds algorithm)

Sam Thomson (with thanks to Swabha Swayamdipta)

University of Washington, CSE 490u

February 22, 2017

Page 2

Outline

I Dependency trees

I Three main approaches to parsing

I Chu-Liu-Edmonds algorithm

I Arc scoring / Learning

Page 27

Chu-Liu-Edmonds

Consists of two stages:

I Contracting (everything before the recursive call)

I Expanding (everything after the recursive call)

Page 28

Chu-Liu-Edmonds - Preprocessing

I Remove every edge incoming to ROOT
I This ensures that ROOT is in fact the root of any solution

I For every ordered pair of nodes, vi , vj , remove all but the
highest-scoring edge from vi to vj

Page 53

Learning

Recall that when we have a parameterized model, and we have a
decoder that can make predictions given that model. . .

we can use structured perceptron, or structured hinge loss:

Lθ(xi , yi ) = max
y∈Y
{scoreθ(y) + cost(y , yi )} − scoreθ(yi )

Page 54

Learning

Recall that when we have a parameterized model, and we have a
decoder that can make predictions given that model. . .
we can use structured perceptron, or structured hinge loss:

Lθ(xi , yi ) = max
y∈Y
{scoreθ(y) + cost(y , yi )} − scoreθ(yi )

Similer Documents