Applying S acking and Co pus T ans o ma ion
o a Chunking Task
Jos´eA.T oyano,V´ıc o J. D´ıaz, Fe nando En ´ıquez,
Vicen e Ca illo, and Fe m´ın C uz
Depa men o Languages and Compu e Sys ems,
Uni e si y o Se ille, A . Reina, Me cedes s/n 41012, Se illa (Spain)
[email p o ec ed]
Abs ac . In his pape we p esen an applica ion o he s acking ech-
nique o a chunking ask: named en i y ecogni ion. S acking consis s in
applying machine lea ning echniques o combining he esul s o diffe-
en models. Ins ead o using se e al co pus o se e al agge gene a o s
o ob ain he models needed in s acking, we ha e applied h ee ans o -
ma ions o a single aining co pus and hen we ha e used he ou e -
sions o he co pus o ain a single agge gene a o . Taking as baseline
he esul s ob ained wi h he o iginal co pus (Fβ=1 alue o 81.84), ou
expe imen s show ha he h ee ans o ma ions imp o e his baseline
( he bes one eaches 84.51), and ha applying s acking also imp o es
his baseline eaching an Fβ=1 measu e o 88.43.
1 In oduc ion
The e a e many asks in na u al language p ocessing ha consis in associa ing
some kind o ca ego y o a g oup o wo ds. Named En i y Ex ac ion, Shallow
Pa sing, o Seman ic Role Iden ifica ion a e h ee good examples. In his ype o
asks, we can iden i y wo sub asks: one ha finds he bounda ies o he g oup
o wo ds (chunk) and a second p ocess ha associa es he co ec ag o his
g oup. In his pape we p esen a se ies o expe imen s on a clea example o
chunking: he NER (Named En i y Recogni ion) p oblem. We show ha co pus
ans o ma ion and sys em combina ion echniques imp o e he pe o mance in
his ask.
The NER ask consis s in he iden ifica ion o he g oup o wo ds ha o m a
named en i y. IOB no a ion is usually employed o ma k he en i ies in a co pus.
In his no a ion, he B ag deno es he beginning o a name, he I ag is assigned
o hose wo ds ha a e wi hin (o a he end o ) a name, and he O ag is
ese ed o hose wo ds ha do no belong o any named en i y.
In he de elopmen o ou expe imen s we ha e used a Spanish co pus agged
wi h NER in o ma ion, and a e- ainable agge gene a o based on Ma ko
Models. In o de o imp o e he pe o mance o he NER ask we ha e defined
h ee ans o ma ions ha gi e us modified e sions o he aining co pus, and
we ha e ained he agge gene a o wi h hem o ob ain diffe en agge s.
Finally we ha e applied a s acking (machine lea ning) scheme o combine he
esul s o he models.
Expe imen s show ha he h ee ans o ma ions imp o e he esul s o he
NER ask, and ha sys em combina ion achie es be e esul s han he bes o
he pa icipan models in isola ion.
2 Resou ces, E alua ion and Baseline
The wo main esou ces employed in ou expe imen s a e he co pus and he
agge gene a o . The co pus p o ides a wide se o named en i y examples in
Spanish. I was used in he Named En i y Recogni ion sha ed ask o CoNLL-
02 [14] and i is dis ibu ed in h ee diffe en files, a ain co pus, and wo
es co pus. We ha e used he addi ional es co pus in s acking expe imen s o
gene a e he aining da abase.
The e a e ou ca ego ies in he co pus axonomy: PER (people), LOC
(places), ORG (o ganiza ions) and MISC ( es o en i ies). Howe e , he NER
ask does no need he ca ego y in o ma ion, so we ha e simplified he co pus
by emo ing he ca ego y in o ma ion om he ags. Figu e 1 shows a agmen
o he o iginal co pus, and i s simplified e sion used in he NER ask.
The o he main esou ce is he agge gene a o . We ha e chosen TnT [1],
one o he mos widely used e- ainable agge in NLP applica ions. I is based
upon second o de Ma ko Models, consis ing o wo d emission p obabili ies
and ag ansi ion p obabili ies compu ed om ig ams o ags. As a fi s s ep
i compu es he p obabili ies om a agged co pus h ough maximum likeli-
hood es ima ion, hen i implemen s a linea in e pola ion smoo hing me hod
o manage he spa se da a p oblem. I also inco po a es a suffix analysis o
dealing wi h unknown wo ds, assigning ag p obabili ies acco ding o he wo d
ending.
Wo d Tag
La O
Delegaci´on B-ORG
de I-ORG
la I-ORG
Agencia I-ORG
EFE I-ORG
en O
Ex emadu a B-LOC
ansmi i ´aO
hoy O
... ...
NEE co pus
Wo d Tag
La O
Delegaci´on B
de I
la I
Agencia I
EFE I
en O
Ex emadu a B
ansmi i ´aO
hoy O
... ...
NER co pus
Fig. 1. O iginal co pus and co pus agged only o he ecogni ion sub ask
Table 1. Baseline, TnT ained wi h NER cop pus
P ecision Recall Fβ=1
Baseline 81.40% 82.28% 81.84
To e alua e ou expe imen s, we ha e used he classical measu es p ecision,
ecall and Fβ=1.P ecision is defined as he pe cen age o co ec ly ex ac ed
en i ies. Recall is defined as he p opo ion o en i ies ha he sys em has been
able o ecognize om he o al co ec en i ies in he es co pus. The o e all
Fβ=1 measu e combines ecall and p ecision, gi ing o bo h he same ele ance:
Fβ=1 =2P ecision Recall
P ecision +Recall
We will use Fβ=1 measu e o compa ing he esul s o ou expe imen s. I is
a good pe o mance indica o o a sys em and i is usually used as compa ison
c i e ion. Table 1 shows he esul s ob ained when TnT is ained wi h he NER
co pus , we will adop hese esul s as he baseline o u he expe imen s in
his pape .
3 Co pus T ans o ma ion
In o de o ha e diffe en iews o he NER p oblem, we ha e defined h ee
ans o ma ions ha applied o he o iginal co pus gi e us h ee addi ional e -
sions o i . This way, he agge gene a o lea ns in ou diffe en ways and he
esul ing models can specialize in he ecogni ion o named en i ies o diffe en
na u e.
3.1 Vocabula y Reduc ion
In his ans o ma ion we employ a echnique simila o ha used in [12] eplac-
ing he wo ds in he co pus wi h okens ha con ain ele an in o ma ion o
ecogni ion. One o he p oblems ha we y o sol e is he ea men o unknown
wo ds: he wo ds ha do no appea in he aining co pus and, he e o e, he
agge can no make any assump ion abou hem. In he NER ask, he lack o
in o ma ion o an unknown wo d can be mi iga ed wi h i s ypog aphic in o ma-
ion because capi aliza ion is a good indica o o he p esence o a p ope name.
We also include in his ans o ma ion he knowledge gi en by non-capi alized
wo ds ha equen ly appea be o e, a e o inside named en i ies. We call hem
igge wo ds and hey a e o g ea help in he iden ifica ion o en i y bounda ies.
Bo h pieces o in o ma ion, igge wo ds and ypog aphic clues, a e ex ac ed
om he o iginal co pus h ough he applica ion o he ollowing ules:
–Each wo d is eplaced by a ep esen a i e oken, o example, i s a s cap
o capi alized wo ds. These wo d pa e ns a e iden ified using a small se o
egula exp essions.
Wo d Tag
La O
Delegaci´on B
de I
la I
Agencia I
EFE I
en O
Ex emadu a B
ansmi i ´aO
hoy O
... ...
NER co pus
Wo d Tag
La O
s a s cap B
de I
la I
s a s cap I
all cap I
en O
s a s cap B
ansmi i ´aO
lowe O
... ...
NER-V co pus
Wo d Tag
La de O
s a s cap noun B
de p ep I
la de I
s a s cap noun I
all cap noun I
en p ep O
s a s cap noun B
ansmi i ´a e b O
lowe ad O
... ...
NER-P co pus
Fig. 2. Changing he wo ds
–No all wo ds a e eplaced wi h i s co esponding oken, he igge wo ds
emain as hey appea in he o iginal co pus. The lis o igge wo ds is
compu ed au oma ically coun ing he wo ds ha mos equen ly appea
a ound o inside an en i y.
Figu e 2 shows he esul o applying ocabula y educ ion (NER-V co pus).
The esul s o he expe imen TnT-V a ep esen edinTable2,wecansee ha
his ans o ma ion makes TnT imp o e om 81.84 o 83.63.
3.2 Addi ion o Pa -o -Speech In o ma ion
In his case we will make use o ex e nal knowledge o add new in o ma ion
o he o iginal co pus. Each wo d will be eplaced wi h a compound ag ha
in eg a es wo pieces o in o ma ion:
–The esul o applying he fi s ans o ma ion ( ocabula y educ ion).
–The pa -o -speech (POS) ag o he wo d.
To ob ain he POS ag o a wo d we ha e ained TnT wi h he Spanish
co pus CLiC-TALP [4]. We make use o a compound ag in he subs i u ion
Table 2. Resul s o co pus ans o ma ion
P ecision Recall Fβ=1
Baseline 81.40% 82.28% 81.84
TnT-V 81.76% 85.59% 83.63
TnT-P 81.51% 84.79% 83.12
TnT-N 82.77% 86.33% 84.51
because he POS ag does no p o ide enough in o ma ion o ecognize an en-
i y. We comple e his in o ma ion wi h he knowledge gi en by ypog aphical
ea u es and igge wo ds. Figu e 2 shows he esul o he applica ion o his
ans o ma ion (NER-P co pus). Adding POS in o ma ion also esul s in a pe -
o mance imp o emen o TnT in he NER ask. Table 2 p esen s he esul s o
he expe imen TnT-P, in his case TnT eaches an Fβ=1 measu e o 83.12.
3.3 Changing he Tags
We eplace he o iginal IOB no a ion wi h a mo e exp essi e one ha includes
in o ma ion abou he posi ion o wo ds inside and a ound en i ies. In o de o
conside he posi ion inside en i ies, we ha e added wo new ags E and BE ha
a e assigned, espec i ely, o wo ds ha end a mul i-wo d named en i y and o
single-wo d named en i ies. The meaning o he ags assigned o wo ds inside
en i ies a e now:
–B, ha deno es he beginning o a named en i y wi h mo e han one wo d.
–BE, ha is assigned o a single-wo d named en i y.
–I, ha is assigned o wo ds ha a e inside o a mul iple-wo d named en i y,
excep o he las wo d.
–E, assigned o he las wo d o a mul iple-wo d named en i y.
We can also add mo e in o ma ion o wo ds ou side en i ies, pa icula ly we
a e in e es ed in hose wo ds ha appea jus be o e o a e an en i y. We spli
he meaning o he non-in o ma i e O ag in o ou ags:
–BEF, ha is assigned o hose wo ds ha appea be o e an en i y.
–AFT, assigned o wo ds ha appea a e an en i y.
Wo d Tag
La O
Delegaci´on B
de I
la I
Agencia I
EFE I
en O
Ex emadu a B
ansmi i ´aO
hoy O
... ...
NER co pus
Wo d Tag
La BEF
Delegaci´on B
de I
la I
Agencia I
EFE E
en BET
Ex emadu a BE
ansmi i ´aAFT
hoy O
... ...
NER-N co pus
Fig. 3. Changing he ags

–BET, o wo ds ha a e be ween wo en i ies.
–O, o wo ds ou side en i ies and no adjacen o en i ies
This new ag se gi e mo e ele ance o he posi ion o a wo d, o cing he
agge s o lea n which wo ds appea mo e equen ly a he beginning, a he
end, inside o a ound a named en i y.
Figu e 3 shows he esul o applying his new ag se o a co pus agmen .
Changing he ag se also leads o be e esul s in he NER ask han hose
ob ained wi h he o iginal co pus. The esul s o he expe imen TnT-N a e
showed in Table 2. In his case, TnT imp o es om 81.84 o 84.51, he bes
esul o all he ans o ma ions s udied.
4 Sys em Combina ion
Sys em combina ion is no a new app oach in NPL asks, i has been used in
se e al p oblems like pa o speech agging [7], wo d sense disambigua ion [10],
pa sing [8], noun ph ase iden ifica ion [13] and e en in named en i y ex ac-
ion [6]. The mos popula echniques a e o ing and s acking (machine lea ning
me hods), and he diffe en iews o he p oblem a e usually ob ained using
se e al agge s o se e al aining co po a. In his pape , howe e , we a e in-
e es ed in in es iga e how s acking beha es when he combined sys ems a e
ob ained wi h ans o med e sions o he same aining co pus.
4.1 S acking
S acking consis s in applying machine lea ning echniques o combining he
esul s o diffe en models. The main idea is o build a sys em ha lea ns he
way in which each model is igh o makes a mis ake. In his way he final
decision is aken acco ding o a pa e n o co ec and w ong answe s.
In o de o be able o lea n he way in which e e y model is igh o w ong, we
use a aining da abase. Each example in he aining da abase includes he ou
ags p oposed by he models o a gi en wo d and he ac ual ag. F om his poin
o iew, deciding he ag gi en he ags p oposed by se e al models is a ypical
classifica ion p oblem. Figu e 4 shows a small da abase w i en in “a ff” o ma ,
he no a ion employed by weka [16] o ep esen aining da abases. Weka is a
collec ion o machine lea ning algo i hms o da a mining asks, and is he ool
ha we ha e used in ou s acking expe imen s.
An impo an ad an age o using s acking as combining me hod is ha we
can include in he da abase he e ogeneous in o ma ion. Making use o his ea-
u e, we do no only include he ags o a gi en wo d in i s egis e , bu he
ags assigned by he ou models o i s p e ious and ollowing wo ds a e also
included. This way, he egis e s o ou da abase ha e wel e ea u es ins ead o
jus ou co esponding o he ou ags o he wo d we a e in e es ed in.
We ha e used a co pus wi h new examples o gene a e he da abase, so we can
ensu e ha de da abase used in s acking is independen o he models ( aining
co pus) and i is also independen o he e alua ion p ocess ( es co pus).
@ ela ion combina ion
@a ibu e TnT {O, B, I}
@a ibu e TnT-V {O, B, I}
@a ibu e TnT-N {O, B, I}
@a ibu e TnT-P {O, B, I}
@da a
I, I, I, B, I
O, O, O, O, O
B, B, B, B, B
I, I, I, I, I
O, I, I, I, I
B, I, I, I, I
O, O, O, O, O
O, O, O, O, O
B, B, B, O, O
Fig. 4. A aining da a base. Each egis e co esponds o a wo d
Table 3. Resul s o s acking wi h a decision ee as lea ning echnique
P ecision Recall Fβ=1
Baseline 81.40% 82.28% 81.84
Decision T ee 87.96% 88.44% 88.20
Table 3 shows he esul s o he expe imen Decision T ee, ca ied ou using
a decision ee [11] as s acking echnique.
A decision ee uses a bina y ee o p edic he alue o a a ge a iable om
hose o a se o p edic o a iables. The ee is buil by successi ely spli ing
nodes acco ding o an in o ma ion gain c i e ion. A p uning c i e ion is also
applied o confine he ee size o app op ia e limi s. This echnique is one o
he bes and mos commonly used lea ning algo i hm in classifica ion.
The Fβ=1 measu e is 88.20, which is be e han he baseline (81.84) and also
be e han he bes o pa icipan models in he s acking expe imen (TnT-N
wi h 84.59).
4.2 Using O he Machine Lea ning Algo i hms
Apa om allowing he use o he e ogeneous in o ma ion, he use o machine
lea ning as combina ion me hod has ano he impo an ad an age: i is possible
o choose among a la ge a ie y o schemes and echniques o find he mos
sui able o a specific p oblem. We ha e expe imen ed wi h se e al machine
lea ning algo i hms included in he weka package o compa e hei pe o mance
when hey a e ained wi h he da abase ha we ha e c ea ed. Mos o hem a e
ule-based because his kind o classifie s beha es be e wi h disc e e da abases:
–Bagging [2]is based on he gene a ion o se e al aining da a se s aking
as base a unique da a se . Each new e sion is ob ained by sampling wi h
Table 4. Resul s o s acking wi h diffe en classifie s
P ecision Recall Fβ=1
Baseline 81.40% 82.28% 81.84
Decision Table 86.52% 87.59% 87.05
Random T ee 86.43% 87.84% 87.13
Pa 87.70% 87.84% 87.72
Bagging 88.20% 88.42% 88.31
Rippe 88.88% 87.98% 88.43
eplacemen he o iginal da abase. Each new da a se can be used o ain
a model and he answe s o all models can be combined o ob ain a join
answe . Gene ally, bagging leads o be e esul s han hose ob ained wi h
a single classifie . The p ice o pay is ha his kind o combina ion me hods
inc ease he compu a ional cos associa ed o lea ning. In ou expe imen
we ha e used decision ees as base lea ne wi h his scheme.
–Decision Table [9] is a ule-based classifie . The model consis s o a schema,
in which only he mos ep esen a i e a ibu es o he da abase a e included,
and a body ha has labelled ins ances o he da abase defined by he ea u es
o he schema.
–Pa [15] is he ule-based e sion o decision ees, i uses a di ide and con-
que s a egy, building a pa ial decision ee in each i e a ion and con e ing
he bes lea o he ee in o a ule.
–Rippe [5] applies an i e a i e and inc emen al p uning p ocess o ob ain an
e o educ ion. A a fi s s age i gene a es a se o ules ha is op imized
by gene a ing new ules wi h andomized da a and p uning hem.
–Random T ee [16] is an adap a ion o decision ee in which e e y node
conside only a subse o he a ibu es o he da abase, his subse is chosen
andomly.
Table 4 shows he esul s o he expe imen s. All o hem p esen good esul s,
he bes one is achie ed wi h Rippe (88.43) imp o ing mo e han six pe cen
poin s he baseline. This pe o mance is simila o s a e-o - he-a ecognize s,
wi h compa able esul s o hose ob ained by one o he bes NER sys ems o
Spanish ex s [3].
5 Conclusions and Fu u e Wo k
In his pape we ha e shown ha he combina ion o se e al agge s is an effec i e
echnique o imp o ing a chunking ask like named en i y ecogni ion. Taking
as baseline he esul s ob ained when a agge gene a o (TnT) is ained wi h
a co pus, we ha e in es iga ed al e na i e me hods o aking mo e ad an age
o he knowledge p o ided by he co pus. By means o co pus ans o ma ion
we ha e ob ained h ee diffe en iews o he aining co pus, wi h hem we
ha e ob ained h ee agge s ha imp o e he esul s ob ained wi h he o iginal
e sion o he co pus.
Once we had ou diffe en agge s we ha e applied s acking, combining hem
by gene a ing a aining da abase o examples and applying machine lea ning.
We ha e expe imen ed wi h se e al classifie s eaching a bes esul o 88.43 in
he Fβ=1 measu e, mo e han six pe cen poin s be e han he baseline (81.84).
This pe o mance is simila o s a e o he a NER sys ems, wi h compa able
esul s o hose ob ained by he bes sys em in he CoNLL-02 compe i ion [3].
Much u u e wo k emains. We a e in e es ed in applying he ideas o his
pape in he ecogni ion o en i ies in specific domains, and in he g ow h o
co pus, using he join ly assigned ag as ag eemen c i e ion in co- aining o
ac i e lea ning schemes.
Re e ences
1. B an s, T.: TnT. A s a is ical pa -o -speech agge . In P oceedings o he 6 h
Applied NLP Con e ence (ANLP00). USA (2000) 224–231
2. B eiman, L.: Bagging p edic o s. In Machine Lea ning Jou nal 24 (1996) 123–140
3. Ca e as, X., L. M`a quez y L. Pad ´o: Named En i y Ex ac ion using AdaBoos .
In CoNLL02 Compu a ional Na u al Language Lea ning. Taiwan (2002) 167–170
4. Ci i , M.: Gu´ıa pa a la ano aci´on mo osin ´ac ica del co pus CLiC-TALP. X-
TRACT Wo king Pape WP-00/06. (2000)
5. Cohen, W. W.: Fas Effec i e Rule Induc ion. In P oceedings o he 12 h In e na-
ional Con e ence on Machine Lea ning. Mo gan Kau mann (1995) 115–123
6. Flo ian, R., I yche iah, A., Jing, H., Zhang, T.: Named En i y Recogni ion h ough
Classifie Combina ion. In P oceedings o CoNLL-2003. Canada (2003) 168–171
7. Hal e en, . H., Za el, J. , Daelemans, W.: Imp o ing accu acy in wo d class ag-
ging h ough he combina ion o machine lea ning sys ems. Compu a ional Lin-
guis ics 27 (2001) 199–230
8. Hende son, J. C., B ill, E.: Exploi ing di e si y in na u al language p ocessing.
Combining pa se s. In 1999 Join Sigda Con e ence on Empi ical Me hods in Na -
u al Language P ocessing and Ve y La ge Co po a. ACL. USA (1999) 187–194
9. Koha i, R.: The Powe o Decision Tables. In P oceedings o he Eu opean Con e -
ence on Machine Lea ning. LNCS 914. (1995) 174–189.
10. Pede sen, T.: A simple app oach o building ensembles o nai e bayesian classifie s
o wo d sense disambigua ion. In P oceedings o NAACL00. USA (2000) 63–69
11. Quinlan, J.R.: Induc ion o decision ees. In Machine Lea ning 1 (1986) 81–106.
12. R¨ossle , M.: Using Ma ko Models o Named En i y ecogni ion in Ge man news-
pape s. In P oceedings o he Wo kshop on Machine Lea ning App oaches in Com-
pu a ional Linguis ics. I aly (2002) 29–37
13. Tjong Kim Sang, E.F., Daelemans, W., Dejean, H., Koeling, R., K ymolowsky,
Y., Punyakanok, V., Ro h, D.: Applying sys em combina ion o base noun ph ase
iden ifica ion. In P oceedings o COLING00. Ge many (2000) 857–863
14. Tjong Kim Sang, E.F.: In oduc ion o he CoNLL-2002 Sha ed Task: Language-
Independen Named En i y Recogni ion. In P oceedings o CoNLL-2002.Taiwan
(2002) 155–158
15. Wi en, I.H., F ank, E.: Gene a ing accu a e ule se s wi hou global op imiza ion.
In P oceedings o he 15 h In e na ional Con e ence on Machine Lea ning. Mo gan
Kau man (1998). 144–151
16. Wi en, I.H., F ank, E.: Da a Mining. Machine Lea ning Algo i hms in Ja a. Mo -
gan Kau mann Publishe s (2000)