Training Conditional Random Fields Using Incomplete Annotations
Yuta Tsuboi, Hisashi Kashima
Tokyo Research Laboratory,
IBM Research, IBM Japan, Ltd
Yamato, Kanagawa 242-8502, Japan{yutat,hkashima}@jp.ibm.com

Shinsuke Mori
Academic Center for Computing andMedia Studies, Kyoto University
Sakyo-ku, Kyoto 606-8501, Japan
forest@i.kyoto-u.ac.jp

Hiroki Oda
Shinagawa, Tokyo, Japan
oda@fw.ipsj.or.jp

Yuji Matsumoto
Graduate School of Information Science,
Nara Institute of Science and Technology
Takayama, Ikoma, Nara 630-0101, Japanmatsu@is.naist.jp

Abstract
We address corpus building situations,where complete annotations to the whole
corpus is time consuming and unrealistic.
Thus, annotation is done only on crucialpart of sentences, or contains unresolved
label ambiguities. We propose a parameter estimation method for Conditional Random Fields (CRFs), which enables us to
use such incomplete annotations. We showpromising results of our method as applied
to two types of NLP tasks: a domain adaptation task of a Japanese word segmentation using partial annotations, and a partof-speech tagging task using ambiguous
tags in the Penn treebank corpus.

1 Introduction
Annotated linguistic corpora are essential forbuilding statistical NLP systems. Most of thecorpora that are well-known in NLP communities are completely-annotated in general. However
it is quite common that the available annotations
are partial or ambiguous in practical applications.
For example, in domain adaptation situations, it istime-consuming to annotate all of the elements in a
sentence. Rather, it is efficient to annotate certain
parts of sentences which include domain-specificexpressions. In Section 2.1, as an example of such
efficient annotation, we will describe the effectiveness of partial annotations in the domain adaptation task for Japanese word segmentation (JWS).
In addition, if the annotators are domain experts
c 2008.
⃝
Licensed under the Creative Commons
Attribution-Noncommercial-Share Alike 3.0 Unported license (http://creativecommons.org/licenses/by-nc-sa/3.0/).
Some rights reserved.

rather than linguists, they are unlikely to be confident about the annotation policies and may preferto be allowed to defer some linguistically complex
decisions. For many NLP tasks, it is sometimes
difficult to decide which label is appropriate in aparticular context. In Section 2.2, we show thatsuch ambiguous annotations exist even in a widelyused corpus, the Penn treebank (PTB) corpus.
This motivated us to seek to incorporate suchincomplete annotations into a state of the art machine learning technique. One of the recent advances in statistical NLP is Conditional Random
Fields (CRFs) (Lafferty et al., 2001) that evaluate
the global consistency of the complete structures
for both parameter estimation and structure inference, instead of optimizing the local configurations
independently. This feature is suited to many NLP
tasks that include correlations between elementsin the output structure, such as the interrelation ofpart-of-speech (POS) tags in a sentence. However,conventional CRF algorithms require fully annotated sentences. To incorporate incomplete annotations into CRFs, we extend the structured output problem in Section 3. We focus on partial annotations or ambiguous annotations in this paper.
We also propose a parameter estimation method
for CRFs using incompletely annotated corpora in
Section 4. The proposed method marginalizes out
the unknown labels so as to optimize the likelihoodof a set of possible label structures which are consistent with given incomplete annotations.
We conducted two types of experiments and observed promising results in both of them. One wasa domain adaptation task for JWS to assess the
proposed method for partially annotated data. The
other was a POS tagging task using ambiguous annotations that are contained in the PTB corpus. We
summarize related work in Section 6, and conclude

切

り

cut

infl.

傷

や

injury

す

り

infl.

cut

infl.

傷
injurypickpocket
file (or rasp)

incised woundorabrasion

Figure 1: An example of word boundary ambiguities: infl. stands for an inflectional suffix of a verb.
in Section 7.

2

Incomplete Annotations

2.1 Partial Annotations
In this section, we describe an example of an efficient annotation which assigns partial word boundaries for the JWS task.
It is not trivial to detect word boundaries fornon-segmented languages such as Japanese or Chinese. For example, the correct segmentation of
the Japanese phrase “切り傷やすり傷” (incisedwound or abrasion) is shown by the lowest boxes
segmented by the solid lines in Figure 1. However, there are several overlapping segmentation
candidates, which are shown by the other boxes,and possible segmentation by the dashed lines.
Thus, the decisions on the word segmentation require considering the context, so simple dictionary
lookup approach is not appropriate. Therefore statistical methods have been successfully used for
JWS tasks. Previous work (Kudo et al., 2004)
showed CRFs outperform generative Markov models and discriminative history-based methods in
JWS. In practice, a statistical word segment analyzer tends to perform worse for text from different domains, so that additional annotations foreach target domain are required. A major cause oferrors is the occurrence of unknown words. For example, if “すり傷” (abrasion) is an unknown word,
the system may accept the word sequence of “切り傷やすり傷” as “切り傷” (incised wound), “やすり” (file), and “傷” (injury) by mistake.
On one hand, lists of new terms in the target
domain are often available in the forms of technical term dictionaries, product name lists, or othersources. To utilize those domain word lists, Mori
(2006) proposed a KWIC (KeyWord In Context)
style annotation user interface (UI) with which auser can delimit a word in a context with a single
user action. In Figure 2, an annotator marks the occurrences of “すり傷”, a word in the domain word⃝⃝

感染、角膜のこ
皮膚に切り傷や泥まみれの深い

すり傷
すり傷
すり傷

、角膜潰瘍、を負った場合や、皮下深く

Figure 2: An example of KWIC style annotation:marked lines are identified as a correct segmentation.
list, if they are used as a real word in their context. The “すり傷” in the first row is a part of another word “こすり傷” (scratch), and the annotator
marks the last two rows as correctly segmented examples. This UI simplifies annotation operations
for segmentation to yes/no decisions, and this simplification can also be effective for the reductionof the annotation effort for other NLP tasks. For
example, the annotation operations for unlabeleddependency parsing can be simplified into a seriesof yes/no decisions as to whether or not given two
words have syntactic dependency. Compared withsentence-wise annotation, the partial annotation is
not only effective in terms of control operations,but also reduces annotation errors because it does
not require annotating the word boundaries that anannotator is unsure of. This feature is crucial forannotations made by domain experts who are notlinguists. 1 We believe partial annotation is effective in creating corpora for many other structured
annotations in the context of the domain adaptations.
2.2 Ambiguous Annotations
Ambiguous annotations in this paper refer to a setof candidate labels annotated for a part of a structured instance. For example, the following sentence from the PTB corpus includes an ambiguous
annotation for the POS tag of “pending”:
That/DT suit/NN is/VBZ pending/VBG|JJ ./. ,where words are paired with their part-of-speech
tag by a forward slash (“/”).2 Uncertainty concerning the proper POS tag of “pending” is represented
by the disjunctive POS tag (“VBG and JJ”) as indicated by a vertical bar.
The existence of the ambiguous annotations isdue to the task definition itself, the procedure man1
The boundary policies of some words are different evenamong linguists. In addition, the boundary agreement is evenlower in Chinese (Luo, 2003).
2
These POS tags used here are DT:determiner,
NN:common noun, VBZ:present tense 3rd person singularverb, VBG:gerund or present participle verb, JJ:adjective,
NNS:plural noun, RBR:comparative adverb, IN:prepositionor subordinating conjunction, and RB:adverb.

frequency
15
10
7
4

word
data
more
pending
than

POS tags
NN|NNSJJR|RBR
JJ|VBG
IN|RB

Table 1: Words in the PTB with ambiguous POSs.
ual for the annotators, or the inadequate knowledge of the annotators. Ideally, the annotations
should be disambiguated by a skilled annotator forthe training data. However, even the PTB corpus, whose annotation procedure is relatively welldefined, includes more than 100 sentences containing POS ambiguities such as those listed in Table 1. Although the number of ambiguous annotations is not considerably large in PTB corpus, corpora could include more ambiguous annotations when we try to build wider coverage corpora. Also, ambiguous annotations are more common in the tasks that deal with semantics, such as
information extraction tasks so that learning algorithms must deal with ambiguous annotations.

3

Problem Definition

In this section, we give a formal definition of thesupervised structured output problem that uses partial annotations or ambiguous annotations in the
training phase. Note that we assume the input andoutput structures are sequences for the purpose of
explanation, though the following discussion is applicable to other structures, such as trees.
Let x=(x1 , x2 , · · · , xT ) be a sequence of observed variables xt ∈ X and y=(y1 , y2 , · · · , yT )be a sequence of label variables yt ∈ Y . Then the
supervised structured output problem can be defined as learning a map X → Y . In the Japaneseword segmentation task, x can represent a given
sequence of character boundaries and y is a sequence of the corresponding labels, which specify whether the current position is a word boundary.3 In the POS tagging task, x represents a word
sequence and y is a corresponding POS tag sequence. An incomplete annotation, then, is defined
as a sequence of subset of the label set instead of asequence of labels. Let L=(L1 , L2 , · · · , LT ) be asequence of label subsets for an observed sequence
3

Peng et al. (2004) defined the word segmentation problem as labeling each character as whether or not the previous
character boundary of the current character is a word boundary. However, we employ our problem formulation since itis redundant to assign the first character of a sentence as theword boundary in their formulation.

x, where Lt ∈ 2Y − {∅}. The partial annotation
at position s is where Ls is a singleton and the rest
Lt̸=s is Y . For example, if a sentence with 6 character boundaries (7 characters) is partially annotated using the KWIC UI described in Section 2.1,
a word annotation where its boundary begins witht = 2 and ends with t = 5 will be represented as:
L = ({⃝, ×}, {⃝}, {×}, {×}, {⃝}, {⃝, ×}),{z}|
partial annotation

where ⃝ and × denote the word boundary label and the non-word boundary label, respectively.
The ambiguous annotation is represented as a set
which contains candidate labels. The example sentence including the ambiguous POS tag in Section 2.2 can be represented as:
L = ({DT}, {NN}, {VBZ}, {VBG, JJ} , {.}).
| {z }
ambiguous annotation

Note that, if all the elements of a given sequence
are annotated, it is the special case such that thesize of all elements is one, i.e. |Lt | = 1 for allt = 1, · · · , T . The goal in this paper is training
a statistical model from partially or ambiguously
annotated data, D = {(x(n) , L(n) )}N
n=1 .

4 Marginalized Likelihood for CRFs
In this section, we propose a parameter estimation
procedure for the CRFs (Lafferty et al., 2001) incorporating partial or ambiguous annotations. Let
Φ(x, y) : X × Y → ℜd denote a map from a pairof an observed sequence x and a label sequence yto an arbitrary feature vector of d dimensions, andθ ∈ ℜd denotes the vector of the model parameters. CRFs model the conditional probability of alabel sequence y given an observed sequence x as:P„ (y|x) =e„·Φ(x,y)，Z„,x,Y(1)

where · denotes the inner product of the vectors,
and the denominator is the normalization term thatguarantees the model to be a probability:∑Z„,x,S =e„·Φ(x,y) .
y∈S

Then once θ has been estimated, the label sequence can be predicted by ŷ =argmaxy∈Y P„ (y|x). Since the original CRF
learning algorithm requires a completely labeledsequence y, the incompletely annotated data
(x, L) is not directly applicable to it.

Let YL denote all of the possible label sequence
consistent with L. We propose to use the conditional probability of the subset YL given x:∑
P„ (YL |x) =P„ (y|x),(2)y∈YL

which marginalizes the unknown ys out. Thenthe maximum likelihood estimator for this model
can be obtained by maximizing the log likelihood
function:
LL(θ) =N∑ln P„ (YL(n) |x

(n)

)

(3)

=

ln Z„,x(n) ,Y (n) − ln Z„,x(n) ,Y)This modeling naturally embraces label ambiguities in the incomplete annotation.4
Unfortunately, equation (3) is not a concave
function5 so that there are local maxima in theobjective function. Although this non-concavity
prevents efficient global maximization of equation(3), it still allows us to incorporate incomplete annotations using gradient ascent iterations (Sha andPereira, 2003). Gradient ascent methods require
the partial derivative of equation (3):N∑∑
∂ LL(θ)= P„ (y|YL(n) , x(n) )Φ(x(n) , y)∂θ
n=1 y∈Y (n)L∑−P„ (y|x(n) )Φ(x(n) , y) , (4)
y∈Y

where
P„ (y|YL , x) =e„·Φ(x,y)Z„,x,YL

Template
c−1 , c+1 ,c−2 c−1 , c−1 c+1 , c+1 c+2 ,c−2 c−1 c+1 , c−1 c+1 c+2
c−1 , c+1

.

L

n=1

Types
Characters
Character types
Term in dic.
Term in dic. starts at
Term in dic. ends at#words145,925
16,34829,216

Table 3: Feature templates: Each subscript stands
for the relative distance from a character boundary.

n=1
N (
∑

(A)
(B)
(C)

domain#sentences
conversation
11,700conversation
1,300
medical manual
1,000
Table 2: Data statistics.

(5)

is a conditional probability that is normalized overYL .
Equations (3) and (4) include the summationsof all of the label sequences in Y or YL . It is notpractical to enumerate and evaluate all of the label
configurations explicitly, since the number of all of
the possible label sequences is exponential on thenumber of positions t with |Lt | > 1. However, under the Markov assumption, a modification of the4
It is common to introduce a prior distribution over the parameters to avoid over-fitting in CRF learning. In the experiments in Section 5, we used a Gaussian prior with the mean 0
2
and the variance σ 2 so that − ||„||
is added to equation (3).
2σ 2
5Since its second order derivative can be positive.

Forward-Backward algorithm guarantees polynomial time computation for the equations (3) and(4). We explain this algorithm in Appendix A.

5 Experiments
We conducted two types of experiments, assessing
the proposed method in 1) a Japanese word segmentation task using partial annotations and 2) a
POS tagging task using ambiguous annotations.
5.1 Japanese Word Segmentation Task
In this section, we show the results of domain
adaptation experiments for the JWS task to assess
the proposed method. We assume that only partial annotations are available for the target domain.
In this experiment, the corpus for the source domain is composed of example sentences in a dictionary of daily conversation (Keene et al., 1992).
The text data for the target domain is composedof sentences in a medical reference manual (Beers,
2004) . The sentences of all of the source domain
corpora (A), (B) and a part of the target domain
text (C) were manually segmented into words (seeTable 2).
The performance measure in the experiments isthe standard F measure score, F = 2RP/(R + P )where# of correct words
× 100# of words in test data
# of correct words
P =× 100.
# of words in system output
R=

In this experiment, the performance was evaluatedusing 2-fold cross-validation that averages the results over two partitions of the data (C) into the

95

94.5
94

F

93.5
93

92.5

Proposed method
Argmax as training data
Point-wise classifier

92

91.5
91

0

100 200 300 400 500 600 700 800 900 1000
Number of word annotations

Figure 3: Average performances varying the number of word annotations over 2 trials.
data for annotation and training (C1) versus thedata for testing (C2).
We implemented first order Markov CRFs. As
the features for the observed variables, we use thecharacters and character type n-gram (n=1, 2, 3)around the current character boundary.
The
character types are categorized into Hiragana,
Katakana, Kanji, English alphabet, Arabic numerals, and symbols. We also used lexical features
consulting a dictionary: one is to check if anyof the above defined character n-grams appear ina dictionary (Peng et al., 2004), and the other is
to check if there are any words in the dictionarythat start or end at the current character boundary.
We used the unidic6 (281K distinct words) as thegeneral purpose dictionary, and the Japanese Standard Disease Code Master (JSDCM)7 (23K distinct words) as the medical domain dictionary. The
templates for the features we used are summarizedin Table 3. To reduce the number of parameters,
we selected only frequent features in the source domain data (A) or in about 50K of the unsegmented
sentences of the target domain.8 The total numberof distinct features was about 300K.
A CRF that was trained using only the source
domain corpus (A), CRFS , achieved F =96.84 in
the source domain validation data (B). However,it showed the need for the domain adaptation that
this CRFS suffered severe performance degradation (F =92.3) on the target domain data. This
experiment was designed for the case in which auser selects the occurrences of words in the word
list using the KWIC interface described in Section 2.1. We employed JSDCM as a word list
in which 224 distinct terms appeared on averageover 2 test sets (C1). The number of word an6

Ver. 1.3.5; http://www.tokuteicorpus.jp/dist/Ver. 2.63; http://www2.medis.or.jp/stdcd/byomei/
8
The data (B) and (C), which were used for validation andtest, were excluded from this feature selection process.
7

notations varied from 100 to 1000 in this experiment. We prioritized the occurrences of eachword in the list using a selective sampling technique. We used label
et al.,∑ entropy (Andersonsss2006), H(yt ) =yts ∈Yts P„˜(yt |x) ln P„˜(yt |x), as importance metric of each word occurrence,
where θ̃ is the model parameter of CRFS , and yts =(yt , yt+1 , · · · , ys ) ∈ Yts is a subsequence startingat t and ending at s in y. Intuitively, this metricrepresents the prediction confidence of CRFS .9 As
training data, we mixed the complete annotations(A) and these partial annotations on data (C1) because that performance was better than using only
the partial annotations.
We used conjugate gradient method to find the
local maximum value with the initial value being
set to be the parameter vector of CRFS . Since theamount of annotated data for the target domain was
limited, the hyper-parameter σ was selected using
the corpus (B).
For the comparison with the proposed method,
the CRFs were trained using the most probablelabel sequences consistent with L (denoted asargmax). The most probable label sequences werepredicted by the CRFS . Also, we used a point-wiseclassifier, which independently learns/classifies
each character boundary and just ignores the unannotated positions in the learning phase. As thepoint-wise classifier, we implemented a maximum
entropy classifier which uses the same features andoptimizer as CRFs.
Figure 3 shows the performance comparisonsvarying the number of word annotations. The
combination of both the proposed method and theselective sampling method showed that a small
number of word annotations effectively improved
the word segmentation performance. In addition, the proposed method significantly outperformed argmax and point-wise classifier based on
the Wilcoxon signed rank test at the significancelevel of 5%. This result suggests that the proposed method maintains CRFs’ advantage over the
point-wise classifier and properly incorporates partial annotations.
5.2 Part-of-speech Tagging Task
In this section, we show the results of the POS tagging experiments to assess the proposed method
using ambiguous annotations.
9

We selected word occurrences in a batch mode since eachtraining of the CRFs takes too much time for interactive use.

ambiguous sentences (training)
unique sentences (training)
unique sentences (test)

Ex.1 Ex.2
118
1,480 2,960
11,840

Table 4: Training and test data for POS tagging.
As mentioned in Section 2.2, there are words
which have two or more candidate POS tags in the
PTB corpus (Marcus et al., 1993). In this experiment, we used 118 sentences in which some words(82 distinct words) are annotated with ambiguous
POS tags, and these sentences are called the POS
ambiguous sentences. On the other hand, we callsentences in which the POS tags of these terms are
uniquely annotated as the POS unique sentences.
The goal of this experiment is to effectively improve the tagging performance using both these
POS ambiguous sentences and the POS uniquesentences as the training data. We assume that theamount of training data is not sufficient to ignore
the POS ambiguous sentences, or that the POS ambiguous sentences make up a substantial portion of
the total training data. Therefore we used a smallpart (1/10 or 1/5) of the POS unique sentences fortraining the CRFs and evaluated their performanceusing other (4/5) POS unique sentences. We conducted two experiments in which different numbers of unique sentences were used in the training
phases, and these settings are summarized in Table 4.
The feature sets for each word are the caseinsensitive spelling, the orthographic features of
the current word, and the sentence’s last word. The
orthographic features are whether a spelling begins
with a number or an upper case letter; whether
it begins with an upper case letter and contains aperiod (“.”); whether it is all upper case letters or
all lower case letters; whether it contains a punctuation mark or a hyphen; and the last one, two,and three letters of the word. Also, the sentence’s
last word corresponds to a punctuation mark (e.g.
“.”, “?”, “!”). We employed only features that appeared more than once. The total number of resulting distinct features was about 14K. Althoughsome symbols are treated as distinct tags in the
PTB tag definitions, we aggregated these symbols
into a symbol tag (SYM) since it is easy to restore
original symbol tags from the SYM tag. Then, thenumber of the resulting tags was 36.
For the comparison with the proposed method(mrg), we used three heuristic rules that disambiguated the annotated candidate POS tags in the

POS ambiguous sentences. These rules selected a
POS tag 1) at random, 2) as the first one in thedescription order10 , 3) as the most frequent tagin the corpus. In addition, we evaluated the casewhen the POS ambiguous sentences are 4) discarded from the training data.
For evaluation, we employed the Precision(P) and Average Precision for Ambiguous words(APA):# of correctly tagged word
×100，
# of all word occurrences
1 ∑ # of the correctly tagged w
APA =
×100，
|A|
# of all occurrences of w
P=w∈A

where A is a word set and is composed of the word
for which at least one of its occurrences is ambiguously annotated. Here, we employed APA to evaluate each ambiguous words equally, and |A| was
82 in this experiment. Again, we used the conjugate gradient method to find the local maximum
value with the initial value being set to be the parameters obtained in the CRF learning for the discarded setting.
Table 5 shows the average performance of POS
tagging over 5 different POS unique data. Since
the POS ambiguous sentences are only a fractionof all of the training data, the overall performance(P) was slightly improved by the proposed method.
However, according to the performance for ambiguously annotated words (APA), the proposed
method outperformed other heuristics for POS disambiguation. The P and APA scores between
the proposed method and the comparable methods
are significantly different based on the Wilcoxon
signed rank test at the 5% significance level. Although the performance improvement in this POS
tagging task was moderate, we believe the proposed method will be more effective to the NLP
tasks whose corpus has a considerable number ofambiguous annotations.

6 Related Work
Pereira and Schabes (1992) proposed a grammar
acquisition method for partially bracketed corpus.
Their work can be considered a generative modelfor the tree structure output problem using partial
annotations. Our discriminative model can be extended to such parsing tasks.
10

Although the order in which the candidate tags appear
has not been standardized in the PTB corpus, we assume thatannotators might order the candidate tags with their confidence.

Ex.1
Ex.2

P
APA
P
APA

mrg
94.39
73.10
95.08
76.70

random
94.27
71.58
94.98
74.27

first
94.26
72.65
94.97
75.28

frequent
94.27
71.68
94.97
74.32

discarded
94.19
71.91
94.98
75.16

Table 5: The average POS tagging performance over 5 trials.
Our model is interpreted as one of the CRFs
with hidden variables (Quattoni et al., 2004).
There are previous work which handles hidden
variables in discriminative parsers (Clark and Curran, 2006; Petrov and Klein, 2008). In their methods, the objective functions are also formulated assame as equation (3).
For interactive annotation, Culotta et al. (2006)
proposed corrective feedback that effectively reduces user operations utilizing partial annotations.
Although they assume that the users correct entire label structures so that the CRFs are trained as
usual, our proposed method extends their system
when the users cannot annotate all of the labels ina sentence.

7 Conclusions and Future WorkWe are proposing a parameter estimation method
for CRFs incorporating partial or ambiguous annotations of structured data. The empirical results
suggest that the proposed method reduces the domain adaptation costs, and improves the prediction
performance for the linguistic phenomena that are
sometimes difficult for people to label.
The proposed method is applicable to otherstructured output tasks in NLP, such as syntactic
parsing, information extraction, and so on. However, there are some NLP tasks, such as the wordalignment task (Taskar et al., 2005), in which it is
not possible to efficiently calculate the sum scoreof all of the possible label configurations. Recently, Verbeek and Triggs (2008) independently
proposed a parameter estimation method for CRFs
using partially labeled images. Although the objective function in their formulation is equivalent
to equation (3), they used Loopy Belief Propagation to approximate the sum score for their application (scene segmentation). Their results imply these approximation methods can be used forsuch applications that cannot use dynamic programming techniques.

Acknowledgments
We would like to thank the anonymous reviewers
for their comments. We also thank Noah Smith,Ryu Iida, Masayuki Asahara, and the membersof the T-PRIMAL group for many helpful discussions.

References
Anderson, Brigham, Sajid Siddiqi, and Andrew Moore.
2006. Sequence selection for active learning. Technical Report CMU-IR-TR-06-16, Carnegie Mellon
University.
Beers, Mark H. 2004. The Merck Manual of Medical
Information (in Japanese). Nikkei Business Publications, Inc, Home edition.
Clark, Stephen and James R. Curran. 2006. Partial training for a lexicalized-grammar parser. In
Proceedings of the Annual Meeting of the North
American Association for Computational Linguistics, pages 144–151.
Culotta, Aron, Trausti Kristjansson, Andrew McCallum, and Paul Viola. 2006. Corrective feedback andpersistent learning for information extraction. Artificial Intelligence Journal, 170:1101–1122.
Keene, Donald, Hiroyoshi Hatori, Haruko Yamada, andShouko Irabu, editors. 1992. Japanese-English Sentence Equivalents (in Japanese). Asahi Press, Electronic book edition.
Kudo, Taku, Kaoru Yamamoto, and Yuji Matsumoto.
2004.
Applying conditional random fields toJapanese morphological analysis. In Proceedings ofEmpirical Methods in Natural Language Processing.
Lafferty, John, Andrew McCallum, and Fernando
Pereira. 2001. Conditional random fields: Probabilistic models for segmenting and labeling sequence
data. In Proceedings of the 18th International Conference on Machine Learning.
Luo, Xiaoquan. 2003. A maximum entropy chinesecharacter-based parser. In Proceedings of the Conference on Empirical Methods in Natural Language
Processing, pages 192–199.
Marcus, Mitchell P., Mary Ann Marcinkiewicz, andBeatrice Santorini. 1993. Building a large annotatedcorpus of English: The Penn treebank. Computational Linguistics, 19(2).
Mori, Shinsuke. 2006. Language model adaptation
with a word list and a raw corpus. In Proceedingsof the 9th International Conference on Spoken Language Processing.

Peng, Fuchun, Fangfang Feng, and Andrew McCallum.
2004. Chinese segmentation and new word detection
using conditional random fields. In Proceedings ofthe International Conference on Computational Linguistics.
Pereira, Fernando C. N. and Yves Schabes. 1992.
Inside-outside reestimation from partially bracketed
corpora. In Proceedings of Annual Meeting Association of Computational Linguistics, pages 128–135.

precomputation of the α„,x,L [t, j], andβ„,x,L [t, j]matrices with given θ, x, and L. The matrices αand β are defined as follows, and should be calculated in the order of t = 1, · · · , T , and t =T + 1, · · · , 1, respectively

Petrov, Slav and Dan Klein. 2008. Discriminative
log-linear grammars with latent variables. In Advances in Neural Information Processing Systems,
pages 1153–1160, Cambridge, MA. MIT Press.

Taskar, Ben, Simon Lacoste-Julien, and Dan Klein.
2005. A discriminative matching approach to wordalignment. In Proceedings of the Conference on Empirical Methods in Natural Language Processing.
Verbeek, Jakob and Bill Triggs. 2008. Scene segmentation with CRFs learned from partially labeled images. In Advances in Neural Information Processing
Systems, pages 1553–1560, Cambridge, MA. MIT
Press.

Appendix A

Computation of Objectiveand Derivative functions

Here we explain the effective computation procedure for equation (3) and (4) using dynamic programming techniques.
Under the first-order Markov assumption11 , twotypes of features are usually used: one is pairs ofan observed variable and a label variable (denoted
as f (xt , yt ) : X × Y ), the other is pairs of twolabel variables (denoted as g(yt−1 , yt ) : Y × Y )at time t. Then the feature
can be de∑Tvector+1
composed as Φ(x, y) =ϕ(xt , yt−1 , yt )t=1
where ϕ(xt , yt−1 , yt ) = f (xt , yt ) + g(yt−1 , yt ).
In addition, let S and E be special label variables to encode the beginning and ending of a sequence, respectively. We define ϕ(xt , yt−1 , yt ) tobe ϕ(xt , S, yt ) at the head t = 1 and g(yt−1 , E) at
the tail where t = T + 1. The technique of the effective calculation of the normalization value is the11

Note that, although the rest of the explanation based on
the first-order Markov models for purposes of illustration, thefollowing arguments are easily extended to the higher orderMarkov CRFs and semi-Markov CRFs.

if j ∈/ Lt
else if t = 1else

β„,x,L [t, j]


0



g(j, E)= θ ·∑
lne„·ﬃ(xt ,j,k)+β[t+1,k]

if j ∈/ Lt
else if t = T + 1
elsei∈Lt−1

Quattoni, Ariadna, Michael Collins, and Trevor Darrell.
2004. Conditional random fields for object recognition. In Advances in Neural Information Processing
Systems.
Sha, Fei and Fernando Pereira. 2003. Shallow parsing with conditional random fields. In Proceedingsof Human Language Technology-NAACL, Edmonton, Canada.

α„,x,L [t, j]


0



ϕ(xt , S, j)= θ ·∑
lneα[t−1,i]+„·ﬃ(xt ,i,j)k∈Lt+1

Note that L = (Y, · · · , Y ) is used to calculate all
the entries in Y . In the rest of this section, we omit
the subscripts θ, x, and L of α, β, Z unless misunderstandings could occur. The time complexityof the α[t, j] or β[t, j] computation is O(T |Y |2 ).
Finally, equations (3) and (4) are efficiently calculated using α, β. The logarithm of Z in equation(3) is calculated as:∑eα„,L [T,j]+„·g(j,E) .
ln Z„,YL = lnj∈LTSimilarly, the first and second terms of equation(4) can be computed as:∑∑
εL (T, i, E)g(i, E)
P„,L (y|x)Φ(x, y) =
y∈YL

+

T ∑
∑
t=1 j∈Lti∈LT

γL (t, j)f (xt , j) +∑εL (t, i, j)g(i, j)

i∈Lt−1

where θ, x are omitted in this equation, and γ„,x,Land ε„,x,L are the marginal probabilities:
γ„,x,L (t, j) = P„,L (yt = j|x)
= eα[t,j]+β[t,j]−ln ZYL , andε„,x,L (t, i, j) = P„,L (yt−1 = i, yt = j|x)
= eα[t−1,i]+„·ﬃ(xt ,i,j)+β[t,j]−ln ZYL .
Note that YL is replaced with Y and L =(Y, · · · , Y ) to compute the second term.