CS626: NLP, Speech and the Web

CS626: NLP, Speech and the Web

Pushpak Bhattacharyya

CSE Dept., IIT Bombay

Lecture 16, 18: Probabilistic parsing;

Parsing phenomena 26

August, 2014

(lect 17 was on MDL and morphology by Vasu)

Example of Sentence labeling:

Parsing

[

[

[

[

[

Come][

[

July]]]]

[

,]

[

and]

[

[

[

the] [

IIT] [

campus]]

[

[

is]

[

[

abuzz]

[

[

with]

[

[

[

new] [

and] [

returning]]

[

students]]]]]]

[

.]]]

Noisy Channel Modeling

Source sentence

Target parse

T*= argmax [P(T|S)]

T

= argmax [P(T).P(S|T)]

T

= argmax [P(T)], since given the parse the T sentence is completely

determined and P(S|T)=1

Language Models



N-grams: sequence of n consecutive words/characters



Probabilistic / Stochastic Context Free Grammars:



Simple probabilistic models capable of handling recursion



A CFG with probabilities attached to rules



Rule probabilities  how likely is it that a

particular rewrite rule is used?

PCFGs



Why PCFGs?



Intuitive probabilistic models for tree-structured languages



Algorithms are extensions of HMM algorithms



Better than the n-gram model for language

modeling.

Data driven parsing is tied up with what is seen in the training data

 “Stand right walk left.” Often a message on the airport escalators.

 “Walk left” can come from :- “After climbing , we realized the walk left was still considerable.”

 “Stand right” can come from: - “The stand right though it seemed at that time, does not stand the scrutiny now.”

 Then the given sentence “Stand right walk left” will never be parsed correctly.

Chomsky Hierarchy

Properties of the hierarchy:-



The containment is proper.



Grammar is not

learnable even for the lowest type from

positive examples alone.

Type 3 or regular grammar Type 2 or CFG Type 1 or CSG

Type 0

3 2

1

0 Type Type Type

Type   

Laws of machine learning



“Learning from vaccuum (zero knowledge) is impossible”.



“Inductive bias decides what to learn”.



In case of POS tagger, bias is the tagset we assume

Some language phenomena

PP-attachment



Happens for verb phrases



Phenomen



Basic form



Example:-



Saw boys with bat_and_ball



Saw mountains with telescope

2

1

P - N

N -

V 

Tree for V-N1-P-N2

VP

V NP

N PP

N

N

P

N

VP

V N

P N

PP

N

P N

P

N

Noun Attachement Verb Attachement

Wh-pronoun dropping



Category A:-



I know the boy whom you met yesterday.



I know the boy you met yesterday.



Category B:-



I know the boy who met you yesterday.



*I know the boy met you yesterday. (disregard the possibility of “...know <that>...”



Rule: Wh-pronoun can be dropped if it refers to the object of the sentence

corresponding to the subordinate clause

Wh-pronoun (2)

Complex sentences

Main Clause Subordinate clause

A) “I know the boy” “You met the boy yesterday”

B) “I know the boy” “The boy met you

yesterday”

Wh-pronoun (3)



Category B



The man who lives in Delhi saw the picture.



The man lives in Delhi saw the picture. (*)



Category A

1.

The man whom you met yesterday saw the picture.

 The man you met yesterday saw the picture.

2.

The man whom you argued with saw the picture.

 The man you argued with saw the picture.

Parsing example:

constituency, dependency,

deep semantics

How to parse?



Example



“Deeds people do, follow them to the end.”



Basic Sentence Structure

Subject Predicate

Verb Complement

(“Object” in some cases)

Constituency Parsing



Sentences are said to be composed of constituents (or phrases).



Constituent parse tree for the core of our example: “Deeds follow them.”

S

NP V

P NN

S Deeds

VP V

follow them

Dependency Parsing



Captures dependencies between entities



A step closer to deep semantics



Dependency parse tree for the core of our example: “Deeds follow them ”

root

follow

Deeds

them (V_main)

nsubj dobj(direct object)

Deep Semantics



WSD resolved



Attachment resolved



Co-reference resolved

follow

deeds them

agent object

(synonym: pursue)

Complex Sentence



A sentence is said to be complex if it has more than one verb.



“Deeds people do, follow them”

Constituency

S

NP VP

NNS S’ V NP

Deeds

NP VP

NNS

people V

do

follow PRON

them

“Deeds people do, follow them”

Dependency

Root

follow (v-main)

Deeds them

do

people

nsubj dobj

Wh-clause

nsubj

“Deeds people do, follow them”

Deep Semantics

follow (synonym: pursue)

: 01 them

agent object

: 01 do

people deeds

agent object

“Deeds people do, follow them”

Constituency

S

NP VP

NNS S’ V NP

Deeds

NP VP

NNS

people V

do

follow PRON them

“Deeds people do, follow them to the end”

PP

P NP

to DT NN

the end

Dependency

Root

follow (v-main)

Deeds them

do

people

nsubj dobj

Wh-clause

nsubj

to

end

the

“Deeds people do, follow them to the end”

pobj

det

Deep Semantics

follow (synonym: pursue)

:

01 them

agent object

: 01 do

people Deeds

agent object

“Deeds people do, follow them to the end”

end

go1

@definite

(Entry-point) (Entry-point)

Probability of a sentence

Probability of sentence

P(W_0, W_1, W_2, W_3…., W_i,…W_n)

•Frequentist approach

corpora the

in sentences S S

P #

) #

( 

•N-grams based approach

) ...

| ( )...

| ( )

| ( ).

| ( ).

( )

...., (

)

( _{1 0 1 0 2 0 1 3 0 1 2 0 1}

0  

 P W W W_n P W P W W P W W W P W W W W P W_n W W_n S

P

assumption bigram

,

)

| ( )

(

1

1

1

0







 

n

i

i

i W

W P W

P

Probability of sentence

• POS tag based

•W₀ – t₀ W₁ – t₁ W₂ – t₂ …. W_n – t_n







sequnece Tag

T

T W P S

P ( ) ( , )

•Parse tree based







trees parse All Tr

Tr W P W

P( ) ( , )

)

| ( ).

( )

,

( W Tr P Tr P W Tr

P 

)

| ( . )

| (

)

| ( ).

( )

, (

1

0

1 i i

n

i

i

i

t P w t

t P

T W P T P T

S P











) (Tr

 P

Uses of P(W)

1. Quality ensuring in translation output

2. Natural language generation. (Generating sentences from non textual inputs like pie charts)

3. Automatic summary generation

4. Speech to text and text to speech – next word prediction

Back to probabilistic parsing

Several Important Points



Phrases capture hierarchy



Span of phrases?



What pairs form dependency?



What is the label on the dependency arc?



Which disambiguation?



Words



Attachments



Co-reference

All these are amenable to machine learning

Formal Definition of PCFG



A PCFG consists of



A set of terminals {w

}, k = 1,….,V

{w

} = { child, teddy, bear, played…}



A set of non-terminals {N

}, i = 1,…,n

{N

} = { NP, VP, DT…}



A designated start symbol N



A set of rules {N

 

}, where 

is a sequence of terminals & non-terminals

NP  DT NN



A corresponding set of rule probabilities

Rule Probabilities



Rule probabilities are such that

E.g., P( NP  DT NN) = 0.2 P( NP  NN) = 0.5

P( NP  NP PP) = 0.3



P( NP  DT NN) = 0.2



Means 20 % of the training data parses use the rule NP  DT NN

i

P(N

) 1

i 

   

Probabilistic Context Free Grammars



S  NP VP 1.0



NP  DT NN 0.5



NP  NNS 0.3



NP  NP PP 0.2



PP  P NP 1.0



VP  VP PP 0.6



VP  VBD NP 0.4



DT  the 1.0



NN  gunman 0.5



NN  building 0.5



VBD  sprayed 1.0



NNS  bullets 1.0



P  with 1.0

Example Parse t ₁



The gunman sprayed the building with bullets.

S_1.0

NP_0.5 VP_0.6 DT_1.0 NN_0.5

VBD_1.0 NP_0.5

PP_1.0

DT_1.0 NN_0.5

P_1.0 NP_0.3

NNS_1.0

bullets with

building the

The gunman

sprayed

P (t₁) = 1.0 *

0.5 * 1.0 * 0.5 * 0.6 * 0.4 * 1.0

* 0.5 * 1.0 * 0.5 * 1.0 * 1.0 *

0.3 * 1.0 =

0.00225 VP_0.4

Another Parse t ₂

S_1.0

NP_0.5 VP_0.4

DT_1.0 NN_0.5VBD_1.0

NP_0.5 PP_1.0 DT_1.0 NN_0.5 P_1.0 NP_0.3

NNS_1.0 bullet s

buildingwith th

e The gunman sprayed

NP_0.2

P (t₂)

= 1.0 * 0.5 * 1.0 * 0.5 * 0.4 * 1.0 * 0.2 * 0.5 * 1.0 * 0.5 * 1.0 * 1.0 * 0.3 * 1.0

= 0.0015



The gunman sprayed the building with bullets.

Probability of a sentence



Notation :



w

– subsequence w

….w



N

dominates w

….w

or yield(N

) = w

….w

N_j

1

1 1

1

: ( )

( ) ( , )

= ( ) ( | ) ( )

m

m m

t

m t

t yield t w

P w P w t

P t P w t P t













Where t is a parse tree of the

sentence

the..sweet..teddy ..bear NP

• Probability of a sentence = P(w

)

(

| ) = 1 P w t

 If t is a parse tree

for the sentence w

, this will be 1

!!

Assumptions of the PCFG model



Place invariance :

P(NP  DT NN) is same in locations 1 and 2



Context-free :

P(NP  DT NN | anything outside “The child”)

= P(NP  DT NN)



Ancestor free : At 2,

P(NP  DT NN|its ancestor is VP)

= P(NP DT NN)

S NP

The child

VP

NP

The toy

1

2

Probability of a parse tree



Domination :We say N _j dominates from k to l, symbolized as , if W _k,l is derived from N _j



P (tree |sentence) = P (tree | S _1,l )

where S_1,l means that the start symbol S dominates the word sequence W_1,l



P (t |s) approximately equals joint probability

of constituent non-terminals dominating the

sentence fragments (next slide)

Probability of a parse tree (cont.)

S_1,l

NP_1,2 VP_3,l

N_2,2 V_3,3 PP_4,l

P_4,4 NP_5,l W_2,2

W_4,4 DT_1,1

W_1,1 W_3,3

W_5,5 W_l,l P ( t|s ) = P (t | S_1,l )

=

P ( NP

, DT

, w

N

, w

VP

, V

, w

PP

, P

, w

NP

, w

|

)

= P ( NP_1,2 , VP_3,l | S_1,l) * P ( DT_1,1 , N_2,2 | NP_1,2) *

P(w_1,1 | DT_1,1) * P (w_2,2 | N_2,2) * P (V_3,3, PP_4,l | VP_3,l) * P(w_3,3 | V_3,3) * P( P_4,4, NP_5,l | PP_4,l ) * P(w_4,4|P_4,4) * P (w_5…l | NP_5,l)

(Using Chain Rule, Context Freeness and Ancestor Freeness )

Exercise: Probabilistic Dependency Tree



Take the cue from PCFG



Probability of a sentence is the probability that the sentence is the yield of S, or the probability that S dominates the sentence



This probability is the probability of different non-terminals dominating segments in the sentence



Get a probabilistic formulation of

dependency tree

Problems with probabilities in PCFG



Grammar rules



S -> aSb P = 0.7



S -> ε P = 0.3



Language of the above grammar



P( t| ) = 0.7*0.7*0.3 = 0.147



Where is the rest of 0.853?

 ^{ε, ab, a b , a b a b ...} 

:

L



2 2

b a

S

S

S a

a

b

b

ε

Problems with probabilities



Grammar rules



S -> aSb P = 0.7



S -> ab P = 0.2



S -> ε P = 0.1



Language of the above grammar



P( t| ) = 0.2 + 0.7*0.1 = 0.27



Where is the rest of 0.73?

 ^{ε, ab, a b , a b a b ...} 

:

L



b a

S (0.7)

S (0.1)

a b

ε S (0.2)

ab

HMM ↔ PCFG



O observed sequence ↔ w _1m sentence



X state sequence ↔ t parse tree



 model ↔ G grammar



Three fundamental questions

HMM ↔ PCFG



How likely is a certain observation given the model? ↔ How likely is a sentence given the grammar?



How to choose a state sequence which best

explains the observations? ↔ How to choose a parse which best supports the sentence?

arg max ( | , )

X

P X O  arg max ( |

, )

t

P t w G

↔

(

| ) P w G ( | )

P O  ^↔

HMM ↔ PCFG



How to choose the model parameters that best explain the observed data? ↔ How to choose rule probabilities which maximize the probabilities of the observed sentences?

arg max ( P O | )



 _{arg max (}

_{| )}

G

P w G

↔

Interesting Probabilities

The gunman sprayed the building with bullets 1 2 3 4 5 6 7 8

(4, 5)



N

NP

(4, 5)



What is the probability of having a NP at this position such that it will derive

“the building” ? -

What is the probability of starting from N

and deriving “The gunman sprayed”, a NP and “with bullets” ? -

Inside Probabilities

Outside Probabilities

Interesting Probabilities



Random variables to be considered



The non-terminal being expanded.

E.g., NP



The word-span covered by the non-terminal.

E.g., (4,5) refers to words “the building”



While calculating probabilities, consider:



The rule to be used for expansion : E.g., NP  DT NN



The probabilities associated with the RHS non-

terminals : E.g., DT subtree’s inside/outside

probabilities & NN subtree’s inside/outside

probabilities

Outside Probability



 _j (p,q) : The probability of beginning with N ¹

& generating the non-terminal N ^j _pq and all words outside w _p ..w _q

1( 1) ( 1)

( , ) ( ,

, | )

j

p q P w

N

w

G

 

w

………w

w

…w

w

……… w

N

N

Inside Probabilities



 _j (p,q) : The probability of generating the words w _p ..w _q starting with the non-terminal

N ^j _pq . _{( , ) ( |}

_{, )}

j

p q P w

N

G

 

w

………w

w

…w

w

……… w





N

N

Outside & Inside Probabilities:

example

The gunman sprayed the building with bullets

1 2 3 4 5 6 7

4,5

(4, 5) for "the building"

(The gunman sprayed, , with bullets | )

NP

P NP G





N

NP

(4, 5) for "the building" (the building |

, )

NP

P NP G

 

Shared Sub-Problems: Example

CKY Parsing: CNF



CKY parsing requires that the grammar consist of ε-free, binary rules =

Chomsky Normal Form



All rules of the form:



A  BC or Aa



What does the tree look like?



What if my CFG isn’t in CNF?

A → B C D → w

CKY Algorithm

Illustrating CYK [Cocke, Younger, Kashmi] Algo



S  NP VP 1.0



NP  DT NN 0.5



NP  NNS 0.3



NP  NP PP 0.2



PP  P NP 1.0



VP  VP PP 0.6



VP  VBD NP 0.4

• DT  the 1.0

• NN  gunman 0.5

• NN  building 0.5

• VBD  sprayed 1.0

• NNS  bullets 1.0

• P  with 1.0

CYK: Start with (0,1)

0

The

gunman

sprayed

the

building

with

bullets

.

To From

1 2 3 4 5 6 7

0 DT_0-1

1 ---

2 --- --- -- 3 --- ---

--

--- -

4 ---

-

--- --

--- -

--- -

5 ---

-

--- --

--- -

--- -

--- -

6 ---

-

--- --

--- -

--- -

--- -

--- -

CYK: Keep filling diagonals

0

The

gunman

sprayed

the

building

with

bullets

.

To From

1 2 3 4 5 6 7

0 DT_0-1

1 --- NN_1-2 2 --- ---

-- 3 --- ---

--

--- -

4 ---

-

--- --

--- -

--- -

5 ---

-

--- --

--- -

--- -

--- -

6 ---

-

--- --

--- -

--- -

--- -

--- -

CYK: Try getting higher level structures

0

The

gunman

sprayed

the

building

with

bullets

.

To From

1 2 3 4 5 6 7

0 DT_0-1 NP_0-2 1 --- NN_1-2 2 --- ---

-- 3 --- ---

--

--- -

4 ---

-

--- --

--- -

--- -

5 ---

-

--- --

--- -

--- -

--- -

6 ---

-

--- --

--- -

--- -

--- -

--- -

CYK: Diagonal continues

0

The

gunman

sprayed

the

building

with

bullets

.

To From

1 2 3 4 5 6 7

0 DT_0-1 NP_0-2 1 --- NN_1-2 2 --- ---

--

VBD_2-3 3 --- ---

--

--- -

4 ---

-

--- --

--- -

--- --

5 ---

-

--- --

--- -

--- --

--- -

6 ---

-

--- --

--- -

--- --

--- -

--- -

CYK (cont…)

0

The

gunman

sprayed

the

building

with

bullets

.

To From

1 2 3 4 5 6 7

0 DT_0-1 NP_0-2 --- 1 --- NN_1-2 --- 2 --- ---

--

VBD_2-3 3 --- ---

--

---

4 ---

-

--- --

--- --- ---

5 ---

-

--- --

--- --- ---

--- -

6 ---

-

--- --

--- --- ---

--- -

--- -

CYK (cont…)

0

The

gunman

sprayed

the

building

with

bullets

.

To From

1 2 3 4 5 6 7

0 DT_0-1 NP_0-2 --- 1 --- NN_1-2 --- 2 --- ---

--

VBD_2-3 3 --- ---

--

--- DT_3-4

4 ---

-

--- --

--- --- ---

5 ---

-

--- --

--- --- ---

--- -

6 ---

-

--- --

--- --- ---

--- -

--- -

CYK (cont…)

0

The

gunman

sprayed

the

building

with

bullets

.

To From

1 2 3 4 5 6 7

0 DT_0-1 NP_0-2 --- --- -- 1 --- NN_1-2 --- ---

-- 2 --- ---

--

VBD_2-3 --- -- 3 --- ---

--

--- DT_3-4 4 --- ---

--

--- --- --

NN_4-5 5 --- ---

--

--- --- --

--- --- 6 --- ---

--

--- --- --

--- ---

--- -

CYK: starts filling the 5 ^th column

0

The

gunman

sprayed

the

building

with

bullets

.

To From

1 2 3 4 5 6 7

0 DT_0-1 NP_0-2 --- -

--- -- 1 --- NN_1-2 ---

-

--- -- 2 --- ---

--

VBD_2-3 --- -- 3 --- ---

--

--- -

DT_3-4 NP_3-5

4 ---

-

--- --

--- -

--- --

NN_4-5

5 ---

-

--- --

--- -

--- --

--- -

6 ---

-

--- --

--- -

--- --

--- -

--- -

CYK (cont…)

0

The

gunman

sprayed

the

building

with

bullets

.

To From

1 2 3 4 5 6 7

0 DT_0-1 NP_0-2 --- -

--- -

1 --- NN_1-2 --- -

--- -

2 --- --- --

VBD_2-

3

--- -

VP_2-5 3 --- ---

--

--- -

DT_3-4 NP_3-5

4 ---

-

--- --

--- -

--- -

NN_4-5

5 ---

-

--- --

--- -

--- -

--- -

6 ---

-

--- --

--- -

--- -

--- -

--- -

CYK (cont…)

0

The

gunman

sprayed

the

building

with

bullets

.

To From

1 2 3 4 5 6 7

0 DT_0-1 NP_0-2 --- -

--- -

1 --- NN_1-2 --- -

--- -

--- -

2 --- --- --

VBD_2-

3

--- -

VP_2-5 3 --- ---

--

--- -

DT_3-4 NP_3-5

4 ---

-

--- --

--- -

--- -

NN_4-5

5 ---

-

--- --

--- -

--- -

--- -

6 ---

-

--- --

--- -

--- -

--- -

--- -

CYK: S found, but NO termination!

0

The

gunman

sprayed

the

building

with

bullets

.

To From

1 2 3 4 5 6 7

0 DT_0-1 NP_0-2 --- -

--- -

S_0-5 1 --- NN_1-2 ---

-

--- -

--- -

2 --- --- --

VBD_2-

3

--- -

VP_2-5 3 --- ---

--

--- -

DT_3-4 NP_3-5

4 ---

-

--- --

--- -

--- -

NN_4-5

5 ---

-

--- --

--- -

--- -

--- -

6 ---

-

--- --

--- -

--- -

--- -

--- -

CYK (cont…)

0

The

gunman

sprayed

the

building

with

bullets

.

To From

1 2 3 4 5 6 7

0 DT_0-1 NP_0-2 --- -

--- -

S_0-5 1 --- NN_1-2 ---

-

--- -

--- -

2 --- --- --

VBD_2-

3

--- -

VP_2-5 3 --- ---

--

--- -

DT_3-4 NP_3-5

4 ---

-

--- --

--- -

--- -

NN_4-5

5 ---

-

--- --

--- -

--- -

--- -

P_5-6

6 ---

-

--- --

--- -

--- -

--- -

--- -

CYK (cont…)

0

The

gunman

sprayed

the

building

with

bullets

.

To From

1 2 3 4 5 6 7

0 DT_0-1 NP_0-2 --- -

--- -

S_0-5 --- -

1 --- NN_1-2 --- -

--- -

--- -

--- -

2 --- --- --

VBD_2-

3

--- -

VP_2-5 --- -

3 --- --- --

--- -

DT_3-4 NP_3-5 --- -

4 ---

-

--- --

--- -

--- -

NN_4-5 --- -

5 ---

-

--- --

--- -

--- -

--- -

P_5-6

6 ---

-

--- --

--- -

--- -

--- -

--- -

CYK: Control moves to last column

0

The

gunman

sprayed

the

building

with

bullets

.

To From

1 2 3 4 5 6 7

0 DT_0-1 NP_0-2 --- -

--- -

S_0-5 --- -

1 --- NN_1-2 --- -

--- -

--- -

--- -

2 --- --- --

VBD_2-

3

--- -

VP_2-5 --- -

3 --- --- --

--- -

DT_3-4 NP_3-5 --- -

4 ---

-

--- --

--- -

--- -

NN_4-5 --- -

5 ---

-

--- --

--- -

--- -

--- -

P_5-6

6 ---

-

--- --

--- -

--- -

--- -

--- -

NP_6-7 NNS_6-7

CYK (cont…)

0

The

gunman

sprayed

the

building

with

bullets

.

To From

1 2 3 4 5 6 7

0 DT_0-1 NP_0-2 --- -

--- -

S_0-5 --- -

1 --- NN_1-2 --- -

--- -

--- -

--- -

2 --- --- --

VBD_2-

3

--- -

VP_2-5 --- -

3 --- --- --

--- -

DT_3-4 NP_3-5 --- -

4 ---

-

--- --

--- -

--- -

NN_4-5 --- -

5 ---

-

--- --

--- -

--- -

--- -

P_5-6 PP_5-7

6 ---

-

--- --

--- -

--- -

--- -

--- -

NP_6-7 NNS_6-7

CYK (cont…)

0

The

gunman

sprayed

the

building

with

bullets

.

To From

1 2 3 4 5 6 7

0 DT_0-1 NP_0-2 --- -

--- --

S_0-5 --- -

1 --- NN_1-2 --- -

--- --

--- -

--- -

2 --- --- --

VBD_2-3 --- --

VP_2-5 --- -

3 --- --- --

--- -

DT_3-4 NP_3-5 --- -

NP_3-7

4 ---

-

--- --

--- -

--- --

NN_4-5 --- -

--- -

5 ---

-

--- --

--- -

--- --

--- -

P_5-6 PP_5-7

6 ---

-

--- --

--- -

--- --

--- -

--- -

NP_6-7 NNS_6-7

CYK (cont…)

0

The

gunman

sprayed

the

building

with

bullets

.

To From

1 2 3 4 5 6 7

0 DT_0-1 NP_0-2 --- -

--- -

S_0-5 --- -

1 --- NN_1-2 --- -

--- -

--- -

--- -

2 --- --- --

VBD_2-

3

--- -

VP_2-5 --- -

VP_2-7 3 --- ---

--

--- -

DT_3-4 NP_3-5 --- -

NP_3-7

4 ---

-

--- --

--- -

--- -

NN_4-5 --- -

--- -

5 ---

-

--- --

--- -

--- -

--- -

P_5-6 PP_5-7

6 ---

-

--- --

--- -

--- -

--- -

--- -

NP_6-7 NNS_6-7

CYK: filling the last column

0

The

gunman

sprayed

the

building

with

bullets

.

To From

1 2 3 4 5 6 7

0 DT_0-1 NP_0-2 --- -

--- -

S_0-5 --- -

1 --- NN_1-2 --- -

--- -

--- -

--- -

--- -

2 --- --- --

VBD_2-

3

--- -

VP_2-5 --- -

VP_2-7 3 --- ---

--

--- -

DT_3-4 NP_3-5 --- -

NP_3-7

4 ---

-

--- --

--- -

--- -

NN_4-5 --- -

--- -

5 ---

-

--- --

--- -

--- -

--- -

P_5-6 PP_5-7

6 ---

-

--- --

--- -

--- -

--- -

--- -

NP_6-7 NNS_6-7

CYK: terminates with S in (0,7)

0

The

gunman

sprayed

the

building

with

bullets

.

To From

1 2 3 4 5 6 7

0 DT_0-1 NP_0-2 --- -

--- -

S_0-5 --- -

S_0-7 1 --- NN_1-2 ---

-

--- -

--- -

--- -

--- -

2 --- --- --

VBD_2-3 --- -

VP_2-5 --- -

VP_2-7 3 --- ---

--

--- -

DT_3-4 NP_3-5 --- -

NP_3-7

4 ---

-

--- --

--- -

--- -

NN_4-5 --- -

--- -

5 ---

-

--- --

--- -

--- -

--- -

P_5-6 PP_5-7

6 ---

-

--- --

--- -

--- -

--- -

--- -

NP_6-7 NNS_6-7

CYK: Extracting the Parse Tree



The parse tree is obtained by keeping back pointers.

S (0-7) NP (0-

2)

VP (2- 7)

VBD (2- 3)

NP (3- 7)

DT (0- 1)

NN (1- 2)

The gunma

n

sprayed

NP (3- 5)

PP (5- 7) DT (3-

4)

NN (4- 5)

P (5- 6)

NP (6-7) NNS (6-7) the building with

bullets

Probabilistic parse tree

construction

Probabilistic Context Free Grammars



S  NP VP 1.0



NP  DT NN 0.5



NP  NNS 0.3



NP  NP PP 0.2



PP  P NP 1.0



VP  VP PP 0.6



VP  VBD NP 0.4



DT  the 1.0



NN  gunman 0.5



NN  building 0.5



VBD  sprayed 1.0



NNS  bullets 1.0



P  with 1.0

Calculating Inside probabilities  _j (p,q)

Base case:

( , ) ( |

, ) (

| )

j

k k P w

N

G P N

w

G

   



Base case is used for rules which derive the words or terminals directly

E.g., Suppose N ^j = NN is being considered &

NN  building is one of the rules with probability 0.5

5,5

5,5

(5, 5) ( | , )

( | ) 0.5

NN

P building NN G P NN building G

 

  

Induction Step: Assuming Grammar in Chomsky Normal Form

Induction step :

w

N

N

N

w

w

w

1

,

( , ) ( | , )

( ) *

( , ) * ( 1, )

j

j pq pq

q

j r s

r s d p r s

p q P w N G

P N N N

p d

d q













 



 



Consider different splits of the words - indicated by d E.g., the huge building



Consider different non-terminals to be used in the rule:

NP  DT NN, NP  DT NNS are available options Consider summation over all these.

Split here for d=2 d=3

The Bottom-Up Approach



The idea of induction



Consider “the gunman”



Base cases : Apply unary rules DT  the Prob = 1.0 NN  gunman Prob = 0.5



Induction : Prob that a NP covers these 2 words

= P (NP  DT NN) * P (DT deriving the word

“the”) * P (NN deriving the word “gunman”)

= 0.5 * 1.0 * 0.5 = 0.25

The gunman

NP_0.5

DT_1.0 NN_0.5

Parse Triangle (probability of output observation, the sentence)

1 1

1 1 1 1 1

(

| ) (

| ) (

|

, ) (1, )

P w G  P N  w G  P w N G   m

• A parse triangle is constructed for calculating



(p,q)

• Probability of a sentence using 

(p,q):

Parse Triangle

The (1)

gunman (2)

sprayed (3)

the (4)

building (5)

with (6)

bullets (7) 0

1 2 3 4 5 6

• Fill diagonals with 

( , ) k k

DT

1.0

 

NN

0.5

 

NN

0.5

 

NNS

1.0

 

VBD

1.0

 

DT

1.0

 

P

1.0

 

from to

Parse Triangle

The (1)

gunman (2)

sprayed (3)

the (4)

building (5)

with (6)

bullets (7) 1

2 3 4 5 6 7

• Calculate using induction formula

DT

1.0

 

NN

0.5

 

NN

0.5

 

NNS

1.0

 

VBD

1.0

 

DT

1.0

 

P

1.0

 

(1, 2) (the gunman |

, )

( ) * (1,1) * (2, 2)

0.5 *1.0 * 0.5 0.25

NP

DT NN

P NP G

P NP DT NN



 



 

 

NP

0.25

 

Example Parse t ₁

S_1.0

NP_0.5 VP_0.6

DT_1.0 NN_0.5

VBD_1.0 NP_0.5

PP_1.0

DT_1.0 NN_0.5

P_1.0 NP_0.3

NNS_1.0

bullet s

with building

th e The gunman

sprayed VP_0.4

Rule used here is

VP  VP PP



The gunman sprayed the building with bullets.

Another Parse t ₂

S_1.0

NP_0.5 VP_0.4

DT_1.0 NN_0.5VBD_1.0

NP_0.5 PP_1.0 DT_1.0 NN_0.5 P_1.0 NP_0.3

NNS_1.0 bullet s

buildingwith th

e The gunmansprayed

NP_0.2

Rule used here is

VP  VBD NP



The gunman sprayed the building with bullets.

β calculation

(3, 7) (sprayed the building with bullets |

, )

( ) * (3, 5) * (6, 7)

( ) * (3, 3) * (4, 7)

0.6 *1.0 * 0.3 0.4 *1.0 * 0.015 0.186

VP

VP PP

VBD NP

P VP G

P VP VP PP P VP VBD NP



 

 



 

 

  

0 The ₁ gunman ₂ sprayed ₃ the ₄ building ₅ with ₆ bullets ₇

Parse tree for the given sentence using probabilistic CYK parsing

•Two parse trees are possible because the sentence has attachment ambiguity .

• Total 16 multiplications are required to make both the parse trees using probabilistic CYK.

•Number of multiplications is less in comparison to a probabilistic

parsing which prepares the two parse trees independently with 28

multiplication.

The 1

gunman 2

Sprayed 3

the 4

Building 5

with 6

Bullets 7 0 β_DT (0-1)

=1.0

β_NP (0-2)

=0.25

β_S(0-7)

=0.006

1 β_NN (1-2)

=0.5

2 β_VBD(2-3)

=1.0

β_VP (2-5)

=0.1

β_VP(2-7)

=0.024

3 β_DT(3-4)

=1.0

β_NP (3-5)

=0.25

β_NP(3-7)

=0.015

4 β_NN (4-5)

=0.5

5 β_P(5-6)

=1.0

β_PP(5-7)

=0.3

6 β_NP/NNS(6-7)

=1.0