Notebook slides

Sequence Labelling¶

POS tagging
Log-linear models
IOB encoding
Named entity recognition
Evaluating sequence labelers
Maximum-entropy Markov models
Conditional random fields
Beam search

Parts of speech (POS)¶

Group words with similar grammatical properties
Penn Treebank is the most commonly used POS tag set for English
- Has 36 POS tags and 12 other tags (for punctuation and currency symbols)
- For example, distinguishes four types of nouns and six types of verbs


NN	noun, singular or mass	cat, rain
NNS	noun, plural	cats, tables
NNP	proper noun, singular	John, IBM
NNPS	proper noun, plural	Muslims, Philippines

Granularity of tags can differ

Sequence Labelling as Structured Prediction¶

Input Space $\Xs$ : sequences of items to label
Output Space $\Ys$ : sequences of output labels
Model: $s_{\params}(\x,\y)$
Prediction: $\argmax_\y s_{\params}(\x,\y)$

Local Models / Classifiers¶

A fully factorised or local model:

$p_\params(\y|\x) = \prod_{i=1}^n p_\params(y_i|\x,i,y_{1,\ldots,i-1}) \approx \prod_{i=1}^n p_\params(y_i|\x,i)$

Assumption: labels are independent of each other given the input
Inference in this model is trivial: greedy decoding

$\prob_\params(\text{"PRP MD VB"} \bar \text{"it will rain"}) \approx \\\\ \prob_\params(\text{"PRP"}\bar \text{"it will rain"},1) \cdot \\ \prob_\params(\text{"MD"} \bar \text{"it will rain"},2) \cdot \\ \prob_\params(\text{"VB"} \bar \text{"it will rain"},3)$

Does this remind you of anything you've seen in previous lectures?

Bias: $\repr_0(\x,i) = 1$

Word at token to tag: $\repr_w(\x,i) = \begin{cases}1 \text{ if }x_i=w \\\\ 0 \text{ else} \end{cases}$

In [8]:

def feat_1(x,i):
    return {
        'bias': 1.0,
        'word:' + x[i]: 1.0,
    }

train = list(zip(tokens[:-200], pos[:-200]))
dev = list(zip(tokens[-200:], pos[-200:]))

local_1 = seq.LocalSequenceLabeler(feat_1, train, class_weight='balanced')

We can assess the accuracy of this model on the development set.

In [9]:

seq.accuracy(dev, local_1.predict(dev))

Out[9]:

0.8872215709261431

In [12]:

util.Carousel(local_1.errors(dev,
                             filter_gold=lambda y: y=='NN',
                             filter_guess=lambda y: y=='NNP'))

Out[12]:

Previous Next

"walkout", "commute", "wage" are misclassified as proper nouns
For $f_{\text{word},w}$ feature template weights are $0$

The word has not appeared in the training set!

First-order Markov assumption¶

Probability of a label depends only on (the input and) the previous label

Example¶

$\prob_\params(\text{"O I-per I-per"} \bar \text{"president Bill Clinton"}) = \\ \prob_\params(\text{"O"}\bar \text{"president Bill Clinton"},\text{"<PAD>"},1) ~ \cdot \\ \prob_\params(\text{"I-per"} \bar \text{"president Bill Clinton"},\text{"O"},2) ~ \cdot \\ \prob_\params(\text{"I-per"} \bar \text{"president Bill Clinton"},\text{"I-per"},3) \\$

Sequence Labelling POS tagging Log-linear models IOB encoding Named entity recognition Evaluating sequence labelers Maximum-entropy Markov models Conditional random fields Beam search

	0	1	2	3	4	5	6	7	8	9	10	11	12	13
0	They	marched	from	the	Houses	of	Parliament	to	a	rally	in	Hyde	Park	.
1	PRP	VBD	IN	DT	NNS	IN	NN	TO	DT	NN	IN	NNP	NNP	.

	Tag	Count	Unique Tokens	Example
0	NN	9307	2087	's special tribunal/NN has filed
1	NNP	8189	2069	the facility Saturday/NNP .
2	IN	7759	94	actions play into/IN the hands
3	DT	6310	40	Both/DT Eritrea and
4	JJ	4875	1214	says the ousted/JJ dictator has
5	NNS	4803	1102	has threatened sanctions/NNS against both
6	.	2992	3	as well ./.
7	VBD	2429	470	Mr. Annan said/VBD he has
8	VBN	2060	588	fighter were killed/VBN , when
9	,	1953	1	Jack Hooper ,/, the deputy

bias	word:walkout
1.0	1.0
3.73	0.00
3.73	0.00

,	and	throw	the	daily	commute	of	its	seven	million
,	CC	VB	DT	JJ	NN	IN	PRP$	CD	CD
,	CC	VB	DT	RB	NNP	IN	PRP$	CD	CD

bias	word:commute
1.0	1.0
3.73	0.00
3.73	0.00

The	walkout	will	shutdown	the	city
DT	NN	MD	VB	DT	NN
DT	NNP	MD	NN	DT	NN

deadlocked	over	such	issues	as	wage	increases	and	at	what
VBN	IN	JJ	NNS	IN	NN	NNS	CC	IN	WP
NNP	RP	PDT	NNS	IN	NNP	NNS	CC	IN	WP

eligible	to	receive	a	full	pension	.
JJ	TO	VB	DT	JJ	NN	.
JJ	TO	VB	DT	JJ	NNP	.

Union	head	Roger	Toussaint	calls
NN	NN	NNP	NNP	VBZ
NNP	VB	NNP	NNP	VBZ

in	effect	to	prevent	massive	traffic	jams	on	New	York
IN	NN	TO	VB	JJ	NN	NNS	IN	NNP	NNP
IN	NN	TO	VB	JJ	NNP	NNP	IN	NNP	NNP

hope	Cambodia	can	be	a	model	for	the	rest	of
NN	NNP	MD	VB	DT	NN	IN	DT	NN	IN
VBP	NNP	MD	VB	DT	NNP	IN	DT	NN	IN

Clinton	's	visit	will	raise	awareness	about	H.I.V.	and	help
NNP	POS	NN	MD	VB	NN	IN	NNP	CC	VB
NNP	POS	VB	MD	VB	NNP	IN	NNP	CC	VB

all	acts	of	abuse	and	brutality	and	treats	allegations	of
DT	NNS	IN	NN	CC	NN	CC	VBZ	NNS	IN
PDT	NNS	IN	NN	CC	NNP	CC	NNP	NNS	IN

it	was	released	by	the	News	of	the	World	newspaper
PRP	VBD	VBN	IN	DT	NN	IN	DT	NNP	NN
PRP	VBD	VBN	IN	DT	NNP	IN	DT	NNP	NN

is	head	of	Mogadishu	's	ambulance	service	,	says	at
VBZ	NN	IN	NNP	POS	NN	NN	,	VBZ	IN
VBZ	VB	IN	NNP	POS	NNP	NN	,	VBZ	IN

1	2	3	4	5	6	7
I	predict	that	it	will	rain	tonight
PRP	VBP	IN	PRP	MD	VB	NN

Contract	talks	between	the	two
NN	NNS	IN	DT	CD
NNP	NNS	IN	DT	CD

prompting	soldiers	to	launch	an	artillery	barrage	.
VBG	NNS	TO	VB	DT	NN	NN	.
VBG	NNS	TO	VB	DT	NNP	NNP	.

soldiers	to	launch	an	artillery	barrage	.
NNS	TO	VB	DT	NN	NN	.
NNS	TO	VB	DT	NNP	NNP	.

two	decades	of	violence	and	lawlessness	since	the	fall	of
CD	NNS	IN	NN	CC	NN	IN	DT	NN	IN
CD	NNS	IN	NN	CC	NNP	IN	DT	VB	IN

The	founder	of	Microsoft	,	Bill
DT	NN	IN	NNP	,	NNP
DT	NNP	IN	NNP	,	NNP

university	students	eager	for	a	glimpse	of	the	world	's
NN	NNS	JJ	IN	DT	NN	IN	DT	NN	POS
NN	NNS	NNP	IN	DT	NNP	IN	DT	NN	POS

the	government	landed	a	high	tech	deal	when	leading	chipmaker
DT	NN	VBD	DT	JJ	NN	NN	WRB	VBG	NN
DT	NN	VBN	DT	JJ	NNP	NN	WRB	VBG	NNP

high	tech	deal	when	leading	chipmaker	Intel	Corporation	announced	it
JJ	NN	NN	WRB	VBG	NN	NNP	NNP	VBD	PRP
JJ	NNP	NN	WRB	VBG	NNP	NNP	NNP	VBD	PRP

The	ingredient	,	called	artemisinin	,	is	extracted	from
DT	NN	,	VBN	NN	,	VBZ	VBN	IN
DT	NN	,	VBD	NNP	,	VBZ	VBN	IN

form	of	malaria	,	called	falciparum	.
NN	IN	NN	,	VBD	NN	.
VB	IN	NN	,	VBD	NNP	.

using	the	euro	as	their	currency	have	not	done	as
VBG	DT	NN	IN	PRP$	NN	VBP	RB	VBN	RB
VBG	DT	NN	IN	PRP$	NNP	VBP	RB	VBN	IN

do	not	yet	know	the	origin	of	the	dead	birds
VBP	RB	RB	VB	DT	NN	IN	DT	JJ	NNS
VB	RB	RB	VB	DT	NNP	IN	DT	JJ	NNS

,	Valery	Sitnikov	,	said	bio-terrorism	can	not	be	ruled
,	NNP	NNP	,	VBD	NN	MD	RB	VB	VBN
,	NNP	NNP	,	VBD	NNP	MD	RB	VB	VBN

four	murders	and	was	the	co-founder	of	the	infamous	Crips
CD	NNS	CC	VBD	DT	NN	IN	DT	JJ	NNP
CD	NNS	CC	VBD	DT	NNP	IN	DT	NNP	NNP

In	two	other	death	penalty	cases	he	has	refused
IN	CD	JJ	NN	NN	NNS	PRP	VBZ	VBN
IN	CD	JJ	NN	NNP	NNS	PRP	VBZ	VBN

After	the	registration	period	ends	,	applicants
IN	DT	NN	NN	VBZ	,	NNS
IN	DT	NNP	NN	VBZ	,	NNS

,	which	will	determine	the	make-up	of	the	presidential	ballot
,	WDT	MD	VB	DT	NN	IN	DT	JJ	NN
,	WDT	MD	VB	DT	NNP	IN	DT	JJ	NN

Competitive	diving	is	one	of	the
JJ	NN	VBZ	CD	IN	DT
NNP	NNP	VBZ	CD	IN	DT

Recreational	diving	is	also	a	growing
JJ	NN	VBZ	RB	DT	VBG
NNP	NNP	VBZ	RB	DT	VBG

diving	is	also	a	growing	amateur	sport	in	the	U.S.
NN	VBZ	RB	DT	VBG	NN	NN	IN	DT	NNP
NNP	VBZ	RB	DT	VBG	NNP	NN	IN	DT	NNP

Unfortunately	,	the	joy	of	jumping	off	the
RB	,	DT	NN	IN	VBG	RP	DT
NNP	,	DT	NNP	IN	NNP	RP	DT

diving	board	at	the	local	swimming	pool	has	too	often
VBG	NN	IN	DT	JJ	NN	NN	VBZ	RB	RB
NNP	NN	IN	DT	JJ	NNP	NNP	VBZ	RB	RB

board	at	the	local	swimming	pool	has	too	often	been
NN	IN	DT	JJ	NN	NN	VBZ	RB	RB	VBN
NN	IN	DT	JJ	NNP	NNP	VBZ	RB	RB	VBN