程序代写代做代考 algorithm B tree Parsing

Parsing

Lizhen Qu

Overview of the NLP Lectures

•  Introduction to natural language processing (NLP).

•  Regular expressions, sentence splitting, tokenization,
part-of-speech tagging.

•  Language models.

•  Vector semantics.

•  Parsing.
–  Dependency parsing.

•  Semantics.

Relation Extraction

•  Find worksFor(entity_a, entity_b) relation from text.

Mark has worked for Telstra.

Per Org

John works for Facebook.

Christina asks why it is better to work at Facebook than Google.

training data

Per Org

Per Org Org

worksFor

Mark Zuckerberg said he would have worked for Microsoft.
Per Org

Use Shortest Paths between Entity Mentions

<-nsubj-prep->pobj->

<-nsubj-ccomp->prep->pobj->

<-nsubj-prep->pobj->

<-nsubj-advcl->prep->pobj-> (Christina, Google)

(John, Facebook)

(Mark, Telstra)

(Zuckerberg, Microsoft)

Dependency Grammar

•  Syntactic structure consists of lexical items,
linked by binary asymmetric relations called
dependencies.

•  head dependent
•  head (governor) : grammatically most important.
•  dependent (modifier): modifier, object, or complement.

Dependency Trees

•  Without labels.

•  With labels.

Dependency Parsing

•  Formal definition for unlabeled dependency trees:

•  Dependency parsing: task of mapping an input string to a
dependency graph satisfying certain conditions.

Dependency graph D = (V,E) where

• V is the set of nodes (words in a input sequence).

• E is the set of arcs indicating grammatical relations.

• vi ! vj or (vi, vj) 2 E denotes an arc from head vi to dependent vj .

Projective Dependency Tree

Ram saw a dog yesterday which was a Yorkshire Terrier

Non-Projective Dependency Tree

Ram saw a dog yesterday which was a Yorkshire Terrier

Crossing lines!

English has very few non-projective cases.

Well-Formedness

•  A dependency graph is well-formed iff

–  Single head: Each word has only one head.

–  Acyclic: The graph should be acyclic.

–  Connected: There is a path between any pairs of nodes.

–  Projective: iif an edge from word A to word B implies that
there exists a directed path in the graph from A to every
word between A and B in the sentences.

Parsing Algorithms

•  Graph-based parsing
–  CYK, Eisner, McDonald

•  Transition-based parsing
–  Covington, Yamada and Matsumuto, Nivre etc.

Nivre’s Algorithm (Arc-eager) [3]

•  Transition-based.

• 

Parser configuration < S, I,A >:

• S is the stack. S[0] is the topmost node.

• I is the list of remaining input words. I[0] is the leftmost word.

• A is the set of current dependencies (arcs) for the dependency graph.

INPUT: a word sequence v = v1|…|vn, a set of rules R.

Left-Arc (LA) < vi|S, vj |I, A >)< S, vj |I, A [ {(vj , vi)} vi vj 2 R @vk(vk, vi) 2 A Right-Arc (RA) < vi|S, vj |I, A >)< vj |vi|S, I, A [ {(vi, vj)} vi ! vj 2 R @vk(vk, vj) 2 A Reduce (R) < vi|S, I, A >)< S, I,A > 9(vk, vi) 2 A

Shift (S) < S, vj |I, A >)< vj |S, I, A >

Parser Transitions

single head

Parsing Details

•  Slight modifications:
–  Each dependency graph has an artificial root in order to

form a tree.
–  Parsing starts with an initial configuration and

terminates when it reaches through a
sequence of transitions.

•  Nondeterministic transitions?
–  Priority ordering of transitions.

–  Guided parsing.

LA > RA >
if S[0] can be a transitive head of I[0], then Shift, otherwise Reduce.

< [ROOT ],n, ; >
< [ROOT ],nil, A >

Grammatical Rules for the Example

Noun ! Adj

ROOT ! V erb

Noun ! Det

V erb ! Prep

V erb ! Noun

figure ! on

on ! screen

Example