chapter14 dependency Parsing1

CS224d-Lecture6:Dependency Parsing

Dependency Parsing

Unlabled Dependency Parses

  • root is a special root symbol
  • Each dependency is a pair (h, m) where h is the index of a head word, m is the index of a modifier word. In the figures, we represent a dependency (h, m) by a directed edge from h to m
  • Dependencies in the above example are (0, 2), (2, 1), (2, 4), and (4, 3). (We take 0 to be the root symbol.)

Conditions on Dependency Structures

  • 从root到任何一个word都有一条直接路径
  • no crossing (比如右下角的笔记就不行~)

对于 "John saw Mary" 有5中dependency parse

有crossing的结构叫 non-projective structure

dependency parsing resource:

  • Conll 2007
  • McDonald
  • dependency banks

一个 treebank 通过 lexicalization 可以转换成 dependency bank.也就是一个lexicalizated PCFG可以转换为一个 dependency bank.

efficiency of dependency parsing

dynamic programming - Jason Eisner

  • very efficiencyat Parsing
  • very useful representations


什么是dependency structure

describing the structure of a sentence by taking each word and saying what it's a dependent on.So, if it's a word that kind of modifies or is an argument of another word that you're saying, it's a dependent of that word.

ambiguity: PP attachments

attachment ambiguities:

A key parsing decision is how we 'attach' vairous constituents

  • PPs 介词短语, adverbial or participial phrase 副词和分词短语, infinitives 不定式, coordinations 并列关系

Catalan numbers: \(C_n=(2n)!/[n+1]!n!\) ??需要在查资料!!


dependency Grammar and Dependency structure

universal dependency

  • the arrow connects a head (governor, superior, regent) with a dependent (modifier, inferior, subordinate)

  • usually, dependencies from a tree(connected, acyclic 非周期的, single-head)

Question: compare CFGs and PCFGs and do they, dependency grammars look strongly lexicalized,they're between words and does that makes it harder to generalize?

dependency conditioning preferences

关于如何确定dependency? 有以下几点perferences?

dependency parsing

这里需要注意一点:是否有交叉 crossing(non-projective). 在图中的例子中,是有crossing的。

但是dependency tree的定义是 no crossing。

methods of dependency Parsing


paper presentation:

Improving distributional similarity with lessions learned from word embeddings, Omer Levy, Yoav Goldberg, Ido Dagan

shift reduced parsing???

Greedy transition-based parsing

The parser:

  • a stack \(\sigma\), written with top to the right
  • which starts with the ROOT symbol
  • a buffer \(beta\), written with the top to the left
  • which starts with the input sentence
  • s set of dependency arcs A
  • which starts off empty
  • a set of actions

\(Left-Arc_r\) \(\sigma|w_i|w_j,\beta,A \rightarrow \sigma|w_j, \beta, A\bigcup{r(w_j,w_i)}\)

表示stack \(\sigma\) 中的两个元素 \(w_i\leftarrow w_j\)


Question: dependency parsing的准确率是否会出现waterfall般的下降,buz one decision will prevent sone other decisions.

it's not bad. dependency parse evaluation suffers much less badly from waterfall effects than CFG parsing when which is worse in that respect.

feature representation


evaluation of dependency parsing

why train a neural dependency parser? Indicator Features Revisited.

our approach:

learn a dense and compact feature representation.

a neural dependency parser

A Fast and Accurate Dependency Parser using Neural Networks


distributed representations

Model Architecture

Non-linearities between layers: Why they are needed

Google announcement of Parsey McParseface, SyntaxNet