Training Conditional Random Fields
Using Incomplete Annotations
Yuta Tsuboi *1*3, Hisashi Kashima *1, Shinsuke Mori *2,Hiroki Oda, and Yuji Matsumoto *3.
*1 IBM Research, Tokyo Research Laboratory.
*2 Academic Center for Computing and Media Studies, Kyoto
University*3 Graduate School of Information Science, Nara Institute of Scienceand Technology© 2008 IBM Corporation

Training Conditional Random Fields Using Incomplete Annotations

Contents

Incomplete annotations in corpus building.
– Partial annotations & Ambiguous annotations– Word segmentation & Part-of-speech tagging task
Training CRFs using Incomplete annotations– Representation of incomplete annotations– Supervised learning setting– Marginal likelihood for CRFs
Experiments– A domain adaptation task of Japanese word segmentation using
partial annotations by domain-specific word lists– POS tagging task using ambiguous annotations which arecontained in Penn treebank corpus.
2© 2008 IBM Corporation

Incomplete Annotations in Corpus Building
Partial annotations– Some parts of a sentence are manually annotated.
– e.g. the domain adaptation task of Japanese word segmentation

Ambiguous annotations

y?

A?

?

xaccb

– Some parts of a sentence are annotated by a set of candidate
labels instead of a single label.
– e.g. POS tags in Penn treebank corpus.

3yA A or B BCxabcc© 2008 IBM Corporation

Background
Word Segmentation & Part-of-speech Tagging Task
Word Segmentation Task ：detecting word boundaries for nonsegmented languages, such as Japanese, and Chinese.
– e.g. Japanese phrase ``切り傷やすり傷‘‘ (incised wound or abrasion):
切り

傷

cut

infl.

injury

やcut

すり

傷

infl.

infl.

injurypickpocket
file (or rasp)

incised woundorabrasion: word candidate“｜” : correct boundary“￤” : incorrect boundary
infl. : inflectional suffix of verbs

Part-of-speech Tagging Task ：identifying words as nouns, verbs,adjectives, adverbs, etc.
– .English： flies

verb or noun?

Statistical methods are commonly used for these problems.
4© 2008 IBM Corporation

Background
Word Segmentation & Part-of-speech Tagging as
Structured Output Prediction
Word Segmentation : Character boundary sequencelabel sequence

word

wordy○

××○

Word boundary

word

○

××

○:wordboundary
×:non-wordboundary○x
切り

傷やす(incised woundorりabrasion)

Part-of-speech Tagging: Word sequence

5傷POS sequence

yDT

NN

VBDDT

NN

SYM

xThe

mansawagirl.

DT: determiner
NN: common noun
VBD: verb, past tense
SYM: symbol, ….
© 2008 IBM Corporation

An example of partial annotations
In the situation of domain adaptation, it is useful toallow partial annotations.
1. Annotators can concentrate on the important parts ofsentences, which can be identified by domain-specificresources or active learning techniques.
2. Linguistically complicated parts can be left without annotation
so that the number of noisy annotations might be reduced.
1. Domain
specific wordy○

×

2. Functional words

word○

×○

○

word

○

word

○

word

○

word

○×x
咬合dental occlusion6とはis上下の歯のか…

the dental bite of both upper and lower tooth….
© 2008 IBM Corporation

An example of ambiguous annotations
Penn treebank English corpus includes more than
100 sentences containing POS ambiguities

Frequent POS ambiguous words in Penn treebank
corpus (Wall Street Journal).

Ambiguous annotations are more common in thetasks which deal with semantics, such as information
extraction tasks.
7© 2008 IBM Corporation

Training Conditional Random Fields Using Incomplete Annotations

Contents

Incomplete annotations in corpus building.
– Partial annotations & Ambiguous annotations– Word segmentation & Part-of-speech tagging task
Training CRFs using Incomplete annotations– Representation of incomplete annotations– Supervised learning setting– Marginal likelihood for CRFs
Experiments– A domain adaptation task of Japanese word segmentation using
partial annotations by domain-specific word lists– POS tagging task using ambiguous annotations which arecontained in Penn treebank corpus.
8© 2008 IBM Corporation

Representation for partial and ambiguous annotations
a sequence of the possible value set:

LLt

Y for t 1LT

Partial Annotations– The partial annotation at position t is a case where the set Lt is a singleton
and the rest is Y.
Partial annotation

L

{○,×}

{○,×}

{○,×}

{○,×}

{○}

{×}

{×}

{○}

{○,×}

x
切り

傷

やす

9

傷の

Ambiguous annotation

Ambiguous Annotations– Lt represents a set ofcandidate labelsat the position t.

り

L

｛DT｝

｛NN｝

｛VBZ｝

｛VBG,JJ}{SYM}

xThatsuitispending.

© 2008 IBM Corporation

Supervised learning using incomplete annotations
Training data is pairs of input x and label setsequence L
L Y for t 1LT .
t

Training data (correct x-L pair)

L(1)

{A,B}

{A,B}

{A}

{B}

{B,C}

x(1)

bcaaa

ModelTraining(map):

X→Y

L(2) {C} {C} {B}
x(2)

ab…

10PredictioncSentence-wiseannotations canbe represented.

yx

Unlabeled data?

?

?

?

baca© 2008 IBM Corporation

Conditional Random Fields (CRFs)

State of the art model for structured output prediction

CRFs model the conditional probability Pθ ( y | x) of a label
sequence y given an observed sequence x.
The score of ｙPθ (y | x)exp θ, Φ( x, y )exp θ, Φ(x, ~y)~y Y

The summed score of all thepossible ys. (Efficientcomputation algorithm isknown)

Φ：X×Y Rd : map from a pair of x and y to a feature vectorθ∈ Rd : the vector of model parameters.
Prediction:yˆ

arg maxPθ y | xy Y11© 2008 IBM Corporation

The advantage of CRFs in NLP
Supporting over-wrapping features and label correlations

Advantage of discriminative model– Using freely correlated features, such as both unigram andbigram, or substrings and string itself
In generative model, it is hard to estimate the joint probability p(x, y )of these features from limited samples

Advantage of structured output learning– Representing correlations between elements in the output
structure (e.g. yt-1 and yt) as feature φｙｙ. T(x, y )

xyt 1

(x, y t )yy

( y t 1, y t )○○12×© 2008 IBM CorporationThe original CRF learning algorithm requires
completely annotated sequence (x, y)
The incompletely annotated data (x, L) is not directly
applicable to CRFs.
– Conventional objective function for CRFs (log-likelihood):
(i )

O(θ)

(i )

logPθ (y | x )i datacompletely annotated sequence

y(i)
x(i)
13A Bb c

AaBaA

L(i) {A,B} {A,B} A

B

{B,C}

ax(i)

aabca

© 2008 IBM Corporation

Training CRFs using YL as the training data where YL
denote all of the possible label sequence consistent withL. (Marginalized Likelihood)

YLLA

{A,B}

A

B

{B,C}

xbcaaaexpansiony A A A B B

A B A B Bx b c a a ab c a a ay A A A B C

A B A B Cx b c a a ab c a a a

The CRF objective function for incomplete annotations

O(θ)

logPθ (YL( i ) | x (i ) )i data14Pθ (y | x (i ) )log
i datay Y (i )L© 2008 IBM Corporation

The score for YL (all of the possible label sequence
consistent with L) is efficiently computable using adynamic programming technique under the Markovassumption.

exp θ,Reuse the previous (t-1)-thcomputation which isconsistent with L1,L2,…Lt-1x, yy YL
AAB

ABCD∑

∑

Partial Annotation
15AAA

BBCD∑

AA

BBBCCCC

DDDD∑

AD∑

∑

∑

Ambiguous Annotation© 2008 IBM Corporation

Summary of the proposed method

The proposed problem definition can deal with partial
annotations, ambiguous annotations, and complete
annotations in the same manner.
– Non-concave (learningO(θ)

local maxima) objective function for CRF(i )logPθ (YL( i ) | x )i data(i )log
i dataPθ (y | x )y Y (i )L– To optimize the function, we can use variants of gradientbased methods, such as conjugate gradient, L-BFGS, ….
16© 2008 IBM Corporation

Training Conditional Random Fields Using Incomplete Annotations

Contents

Incomplete annotations in corpus building.
– Partial annotations & Ambiguous annotations– Word segmentation & Part-of-speech tagging task
Training CRFs using Incomplete annotations– Representation of incomplete annotations– Supervised learning setting– Marginal likelihood for CRFs
Experiments– A domain adaptation task of Japanese word segmentation using
partial annotations by domain-specific word lists– POS tagging task using ambiguous annotations which arecontained in Penn treebank corpus.
17© 2008 IBM Corporation

Domain adaptation experiments for the Japanese word
segmentation task

Partial annotations were given the occurrences ofwords in the domain specific word list.
Domain adaptation task: daily conversation

Complete (sentence-wise)
annotations on source
domain sentences(11,700 sentences)medical reference manualTraining

Prediction

CRF
X→YPartial annotations
on target domain
sentencestargetdomain500
sentences

Evaluated by 2fold crossvalidation

The number of partial annotations were varied, and theorder of the annotation is determined by an active learning.
18© 2008 IBM Corporation

Domain adaptation task of Japanese word segmentation

Features and Performance Measure

As the features for observed variables, we use the n-gram (n=1,2,3)
characters and character types around the current character boundary.
We also used lexical features consulting a dictionary.
– General domain dictionary and Target domain dictionary:
Implementing the first order Markov CRFs and using L2 regularizer
The performance measure in the experiments is F measure score Ｆ=2PR/(R+P)

19© 2008 IBM Corporation

Two other possible methods dealing with partialannotations
1. Filling unlabeled parts by prediction which is consistent withpartial annotations (argmax as training data).

LA

{A,B}

A

{A,B}

xbcaa

arg maxP~θ y | xy YLyAB̂

AÂ

xbcaa

Train
CRF

2. Training point-wise classifier which exclude label correlations.
y(1) ATrain(1)
L A {A,B} A {A,B}b c a axpoint-x
20bc

aay(2)x(2) bc

Aaawiseclassifier© 2008 IBM Corporation

This experimental result suggests that the proposed
method maintains CRFs’ advantage over the point-wiseclassifier and properly incorporates partial annotations.

Source domain
CRF

CRFs aretrainedusing themostprobablesequencespredicted by
the source
domain CRF
model

LogisticRegression
21© 2008 IBM Corporation

Training Conditional Random Fields Using Incomplete Annotations

Contents

Incomplete annotations in corpus building.
– Partial annotations & Ambiguous annotations– Word segmentation & Part-of-speech tagging task
Training CRFs using Incomplete annotations– Representation of incomplete annotations– Supervised learning setting– Marginal likelihood for CRFs
Experiments– A domain adaptation task of Japanese word segmentation using
partial annotations by domain-specific word lists– POS tagging task using ambiguous annotations which arecontained in Penn treebank corpus.
22© 2008 IBM Corporation

POS tagging task using ambiguous annotations
which are contained in Penn treebank corpus.
Experiment Settings
Training data
That/DT suit/NN is/VBZ pending/VBG|JJ ./SYM… calls/VBZ for/IN MCI/NNP to/TO provide/VBdata/NN|NNS service/NN ,/SYM…

“POS ambiguoussentences”

…

(118)

… on/IN the/DT pending/VBG spinoff/NN disclosed/VBD that/IN….

POS unique sentences…

(1/10 or 2/10)

Test data

POS unique sentences…. than/IN the/DT pending/JJ deal/NN suggests/VBZ ./SYM(8/10）…
5 trials for different data sets
23

© 2008 IBM Corporation

For the comparison with the proposed method,
we employed heuristic rules which disambiguate
annotated candidate POS tags in the POS ambiguoussentences.
Heuristic POS disambiguation rules
That/DT suit/NN is/VBZ pending/VBG|JJ ./SYM →That/DT suit/NN is/VBZ pending/VBG ./SYM
1. rand: random selection
pending/VBG|JJ→ pending/JJ
2. first: selecting the first tag of the description order
pending/VBG|JJ → pending/VBG
3. frequent： selecting the most frequent tag in the corpus
pending/VBG|JJ → pending/VBG （where #VBG ＞ #JJ.）
4. discarded: the POS ambiguous sentences are ignored in training data.
24© 2008 IBM Corporation

The proposed method always outperformed otherheuristic POS disambiguation
Evaluation measures：Results

25

A: a word set and is composed of the word one ofwhose occurrences is ambiguously annotated© 2008 IBM Corporation

Conclusions

We introduced– supervised learning setting incorporating partial
annotations, ambiguous annotations, and completeannotations.
– a parameter estimation method for CRFs using
incomplete annotations under Markov assumption.

26© 2008 IBM Corporation