Transactions of the Association for Computational Linguistics, 2 (2014) 27–40. Action Editor: Kristina Toutanova.
Submitted 1/2013; Überarbeitet 7/2013; Published 2/2014. C
(cid:13)
2014 Verein für Computerlinguistik.
AutomaticDetectionandLanguageIdentificationofMultilingualDocumentsMarcoLui♥♣,JeyHanLau♠andTimothyBaldwin♥♣♥DepartmentofComputingandInformationSystemsTheUniversityofMelbourne♣NICTAVictoriaResearchLaboratory♠DepartmentofPhilosophyKing’sCollegeLondonmhlui@unimelb.edu.au,jeyhan.lau@gmail.com,tb@ldwin.netAbstractLanguageidentificationisthetaskofautomat-icallydetectingthelanguage(S)presentinadocumentbasedonthecontentofthedocu-ment.Inthiswork,weaddresstheproblemofdetectingdocumentsthatcontaintextfrommorethanonelanguage(multilingualdocu-ments).Weintroduceamethodthatisabletodetectthatadocumentismultilingual,iden-tifythelanguagespresent,andestimatetheirrelativeproportions.Wedemonstratetheef-fectivenessofourmethodoversyntheticdata,aswellasreal-worldmultilingualdocumentscollectedfromtheweb.1IntroductionLanguageidentificationisthetaskofautomaticallydetectingthelanguage(S)presentinadocumentbasedonthecontentofthedocument.Languageidentificationtechniquescommonlyassumethatev-erydocumentiswritteninoneofaclosedsetofknownlanguagesforwhichthereistrainingdata,andisthusformulatedasthetaskofselectingthemostlikelylanguagefromthesetoftraininglan-guages.Inthiswork,weremovethismonolingualassumption,andaddresstheproblemoflanguageidentificationindocumentsthatmaycontaintextfrommorethanonelanguagefromthecandidateset.Weproposeamethodthatconcurrentlydetectsthatadocumentismultilingual,andestimatesthepropor-tionofthedocumentthatiswrittenineachlanguage.Detectingmultilingualdocumentshasavarietyofapplications.Mostnaturallanguageprocessingtechniquespresupposemonolingualinputdata,soinclusionofdatainforeignlanguagesintroducesnoise,andcandegradetheperformanceofNLPsys-tems(Alexetal.,2007;CookandLui,2012).Au-tomaticdetectionofmultilingualdocumentscanbeusedasapre-filteringsteptoimprovethequalityofinputdata.Detectingmultilingualdocumentsisalsoimportantforacquiringlinguisticdatafromtheweb(Scannell,2007;AbneyandBird,2010),andhasapplicationsinminingbilingualtextsforstatisticalmachinetranslationfromonlineresources(Resnik,1999;Nieetal.,1999;Lingetal.,2013).Therehasbeenparticularinterestinextractingtextresourcesforlow-densitylanguagesfrommultilingualwebpagescontainingboththelow-densitylanguageandanotherlanguagesuchasEnglish(YamaguchiandTanaka-Ishii,2012;KingandAbney,2013).KingandAbney(2013,p1118)specificallymentiontheneedforanautomaticmethod“toexamineamul-tilingualdocument,andwithhighaccuracy,listthelanguagesthatarepresentinthedocument”.Weintroduceamethodthatisabletodetectmulti-lingualdocuments,andsimultaneouslyidentifyeachlanguagepresentaswellasestimatethepropor-tionofthedocumentwritteninthatlanguage.Weachievethiswithaprobabilisticmixturemodel,us-ingadocumentrepresentationdevelopedformono-linguallanguageidentification(LuiandBaldwin,2011).Themodelpositsthateachdocumentisgen-eratedassamplesfromanunknownmixtureoflan-guagesfromthetrainingset.WeintroduceaGibbssamplertomapsamplestolanguagesforanygivensetoflanguages,andusethistoselectthesetoflan-guagesthatmaximizestheposteriorprobabilityofthedocument.
l
D
Ö
w
N
Ö
A
D
e
D
F
R
Ö
M
H
T
T
P
:
/
/
D
ich
R
e
C
T
.
M
ich
T
.
e
D
u
/
T
A
C
l
/
l
A
R
T
ich
C
e
–
P
D
F
/
D
Ö
ich
/
.
1
0
1
1
6
2
/
T
l
A
C
_
A
_
0
0
1
6
3
1
5
6
6
8
5
5
/
/
T
l
A
C
_
A
_
0
0
1
6
3
P
D
.
F
B
j
G
u
e
S
T
T
Ö
N
0
7
S
e
P
e
M
B
e
R
2
0
2
3
28
Ourmethodisabletolearnalanguageidenti-fierformultilingualdocumentsfrommonolingualtrainingdata.Thisisanimportantpropertyastherearenostandardcorporaofmultilingualdocumentsavailable,whereascorporaofmonolingualdocu-mentsarereadilyavailableforareasonablylargenumberoflanguages(LuiandBaldwin,2011).Wedemonstratetheeffectivenessofourmethodempir-ically,firstlybyevaluatingitonsyntheticdatasetsdrawnfromWikipediadata,andthenbyapplyingittoreal-worlddata,showingthatweareabletoiden-tifymultilingualdocumentsintargetedwebcrawlsofminoritylanguages(KingandAbney,2013).Ourmaincontributionsare:(1)wepresentamethodforidentifyingmultilingualdocuments,thelanguagescontainedthereinandtherelativepropor-tionofthedocumentineachlanguage;(2)weshowthatourmethodoutperformsstate-of-the-artmeth-odsforlanguageidentificationinmultilingualdoc-uments;(3)weshowthatourmethodisabletoes-timatetheproportionofthedocumentineachlan-guagetoahighdegreeofaccuracy;Und(4)weshowthatourmethodisabletoidentifymultilingualdoc-umentsinreal-worlddata.2BackgroundMostlanguageidentificationresearchfocusesonlanguageidentificationformonolingualdocuments(Hughesetal.,2006).InmonolingualLangID,thetaskistoassigneachdocumentDauniquelanguageLi∈L.Someworkhasreportednear-perfectaccu-racyforlanguageidentificationoflargedocumentsinasmallnumberoflanguages(CavnarandTren-kle,1994;McNamee,2005).Jedoch,inordertoattainsuchaccuracy,alargenumberofsimplifyingassumptionshavetobemade(Hughesetal.,2006;BaldwinandLui,2010A).Inthiswork,wetackletheassumptionthateachdocumentismonolingual,i.e.itcontainstextfromasinglelanguage.Inlanguageidentification,documentsaremod-eledasastreamofcharacters(CavnarandTrenkle,1994;Kikui,1996),oftenapproximatedbythecor-respondingstreamofbytes(Kruengkraietal.,2005;BaldwinandLui,2010A)forrobustnessovervari-ablecharacterencodings.Inthiswork,wefollowBaldwinandLui(2010A)intrainingasinglemodelforlanguagesthatnaturallyusemultipleencodings(e.g.UTF8,Big5andGBencodingsforChinese),asissuesofencodingarenotthefocusofthisresearch.Thedocumentrepresentationusedforlanguageidentificationgenerallyinvolvesestimatingtherel-ativedistributionsofparticularbytesequences,se-lectedsuchthattheirdistributionsdifferbetweenlanguages.Insomecasestherelevantsequencesmaybeexternallyspecified,suchasfunctionwordsandcommonsuffixes(Giguet,1995)orgrammati-calwordclasses(DueireLinsandGonc¸alves,2004),thoughtheyaremorefrequentlylearnedfromla-beleddata(CavnarandTrenkle,1994;Grefenstette,1995;Prager,1999A;LuiandBaldwin,2011).Learningalgorithmsappliedtolanguageidenti-ficationfallintotwogeneralcategories:Bayesianclassifiersandnearest-prototype(Rocchio-style)classifiers.BayesianapproachesincludeMarkovprocesses(Dunning,1994),naiveBayesmethods(Grefenstette,1995;LuiandBaldwin,2011;Tiede-mannandLjubeˇsi´c,2012),andcompressivemod-els(Teahan,2000).Thenearest-prototypemethodsvaryprimarilyinthedistancemeasureused,includ-ingmeasuresbasedonrankorderstatistics(Cav-narandTrenkle,1994),informationtheory(Bald-winandLui,2010A),stringkernels(Kruengkraietal.,2005)andvectorspacemodels(Prager,1999A;McNamee,2005).Languageidentificationhasbeenappliedindo-mainssuchasUSENETmessages(CavnarandTrenkle,1994),webpages(Kikui,1996;Mar-tinsandSilva,2005;LiuandLiang,2008),websearchqueries(CeylanandKim,2009;BoscaandDini,2010),miningthewebforbilingualtext(Resnik,1999;Nieetal.,1999),buildingminor-itylanguagecorpora(Ghanietal.,2004;Scannell,2007;Bergsmaetal.,2012)aswellasalarge-scaledatabaseofInterlinearGlossedText(Xiaetal.,2010),andtheconstructionofalarge-scalemultilin-gualwebcrawl(CallanandHoy,2009).2.1MultilingualDocumentsLanguageidentificationoverdocumentsthatcontaintextfrommorethanonelanguagehasbeenidentifiedasanopenresearchquestion(Hughesetal.,2006).Commonexamplesofmultilingualdocumentsarewebpagesthatcontainexcerptsfromanotherlan-guage,anddocumentsfrommultilingualorganiza-tionssuchastheEuropeanUnion.
l
D
Ö
w
N
Ö
A
D
e
D
F
R
Ö
M
H
T
T
P
:
/
/
D
ich
R
e
C
T
.
M
ich
T
.
e
D
u
/
T
A
C
l
/
l
A
R
T
ich
C
e
–
P
D
F
/
D
Ö
ich
/
.
1
0
1
1
6
2
/
T
l
A
C
_
A
_
0
0
1
6
3
1
5
6
6
8
5
5
/
/
T
l
A
C
_
A
_
0
0
1
6
3
P
D
.
F
B
j
G
u
e
S
T
T
Ö
N
0
7
S
e
P
e
M
B
e
R
2
0
2
3
29
EnglishFrenchItalianGermanDutchJapanesecharacterthepourdiaufvooはbyte74686520706F7572064692020617566766F6E381AFTable1:Examplesofper-languagebytesequencesselectedbyinformationgain.TheAustraliasianLanguageTechnologyWork-shop2010hostedasharedtaskwhereparticipantswererequiredtopredictthelanguage(S)presentinaheld-outtestsetcontainingmonolingualandbilin-gualdocuments(BaldwinandLui,2010B).ThedatasetwaspreparedusingdatafromWikipedia,andbilingualdocumentswereproducedusingasegmentfromapageinonelanguage,andasegmentfromthesamepageinanotherlanguage.Weusethedatasetfromthissharedtaskforourinitialexperiments.Totheauthors’knowledge,theonlyotherworktodirectlytackleidentificationofmultiplelanguagesandtheirrelativeproportionsinasingledocumentistheLINGUINIsystem(Prager,1999A).Thesystemisbasedonavectorspacemodel,andcosinesimi-laritybetweenafeaturevectorforthetestdocumentandafeaturevectorforeachlanguageLi,computedasthesumoffeaturevectorsforallthedocumentsforlanguageLiinthetrainingdata.Theelementsinthefeaturevectorsarefrequencycountsoverbyten-grams(2≤n≤5)andwords.Languageiden-tificationformultilingualdocumentsisperformedthroughtheuseofvirtualmixedlanguages.Prager(1999A)showshowtoconstructvectorsrepresenta-tiveofparticularcombinationsoflanguagesinde-pendentoftherelativeproportions,andproposesamethodforchoosingcombinationsoflanguagestoconsiderforanygivendocument.Languageidentificationinmultilingualdocu-mentscouldalsobeperformedbyapplicationofsu-pervisedlanguagesegmentationalgorithms.Givenasystemthatcansegmentadocumentintola-beledmonolingualsegments,wecanthenextractthelanguagespresentaswellastherelativepropor-tionoftextineachlanguage.Severalmethodsforsupervisedlanguagesegmentationhavebeenpro-posed.Teahan(2000)proposedasystembasedontextcompressionthatidentifiesmultilingualdocu-mentsbyfirstsegmentingthetextintomonolingualblocks.RehurekandKolkus(2009)performlan-guagesegmentationbycomputingarelevancescorebetweentermsandlanguages,smoothingacrossad-joiningtermsandfinallyidentifyingpointsoftransi-tionbetweenhighandlowrelevance,whicharein-terpretedasboundariesbetweenlanguages.Yam-aguchiandTanaka-Ishii(2012)useaminimumde-scriptionlengthapproach,embeddingacompressivemodeltocomputethedescriptionlengthoftextseg-mentsineachlanguage.Theypresentalinear-timedynamicprogrammingsolutiontooptimizethelo-cationofsegmentboundariesandlanguagelabels.3MethodologyLanguageidentificationformultilingualdocumentsisamulti-labelclassificationtask,inwhichadoc-umentcanbemappedontoanynumberoflabelsfromaclosedset.Intheremainderofthispaper,wedenotethesetofalllanguagesbyL.Wede-noteadocumentDwhichcontainslanguagesLxandLyasD→{Lx,Ly},whereLx,Ly∈L.Wedenoteadocumentthatdoesnotcontainalan-guageLxbyD→{Lx},thoughwegenerallyomitallthelanguagesnotcontainedinthedocumentforbrevity.Wedenoteclassifieroutputusing.;e.g.D.{Der,Lb}indicatesthatdocumentDhasbeenpredictedtocontaintextinlanguagesLaandLb.3.1DocumentRepresentationandFeatureSelectionWerepresenteachdocumentDasafrequencydis-tributionoverbyten-gramsequencessuchasthoseinTable1.Eachdocumentisconvertedintoavectorwhereeachentrycountsthenumberoftimesapar-ticularbyten-gramispresentinthedocument.Thisisanalogoustoabag-of-wordsmodel,wherethevo-cabularyof“words”isasetofbytesequencesthathasbeenselectedtodistinguishbetweenlanguages.TheexactsetoffeaturesisselectedfromthetrainingdatausingInformationGain(IG),aninformation-theoreticmetricdevelopedasasplit-tingcriterionfordecisiontrees(Quinlan,1993).IG-basedfeatureselectioncombinedwithanaiveBayesclassifierhasbeenshowntobeparticularlyeffectiveforlanguageidentification(LuiandBaldwin,2011).
l
D
Ö
w
N
Ö
A
D
e
D
F
R
Ö
M
H
T
T
P
:
/
/
D
ich
R
e
C
T
.
M
ich
T
.
e
D
u
/
T
A
C
l
/
l
A
R
T
ich
C
e
–
P
D
F
/
D
Ö
ich
/
.
1
0
1
1
6
2
/
T
l
A
C
_
A
_
0
0
1
6
3
1
5
6
6
8
5
5
/
/
T
l
A
C
_
A
_
0
0
1
6
3
P
D
.
F
B
j
G
u
e
S
T
T
Ö
N
0
7
S
e
P
e
M
B
e
R
2
0
2
3
30
3.2GenerativeMixtureModelsGenerativemixturemodelsarepopularfortextmod-elingtaskswhereamixtureofinfluencesgovernsthecontentofadocument,suchasinmulti-labeldoc-umentclassification(McCallum,1999;Ramageetal.,2009),andtopicmodeling(Bleietal.,2003).Suchmodelsnormallyassumefullexchangeabilitybetweentokens(i.e.thebag-of-wordsassumption),andlabeleachtokenwithasinglediscretelabel.Multi-labeltextclassification,topicmodelingandourmodelforlanguageidentificationinmultilingualdocumentssharethesamefundamentalrepresenta-tionofthelatentstructureofadocument.Eachla-belismodeledwithaprobabilitydistributionovertokens,andeachdocumentismodeledasaproba-bilisticmixtureoflabels.AspresentedinGriffithsandSteyvers(2004),theprobabilityoftheithtoken(wi)givenasetofTlabelsz1···zTismodeledas:P(wi)=TXj=1P(wi|zi=j)P(zi=j)(1)Thesetoftokenswisthedocumentitself,whichinallcasesisobserved.Inthecaseoftopicmodel-ing,thetokensarewordsandthelabelsaretopics,andzislatent.Whereastopicmodelingisgener-allyunsupervised,multi-labeltextclassificationisasupervisedtextmodelingtask,wherethelabelsareasetofpre-definedcategories(suchasRUBBER,IRON-STEEL,TRADE,etc.inthepopularReuters-21578dataset(Lewis,1997)),andthetokensareindividualwordsindocuments.zisstilllatent,butconstrainedinthetrainingdata(i.e.documentsarelabeledbuttheindividualwordsarenot).Someap-proachestolabelingunseendocumentsrequirethatzforthetrainingdatabeinferred,andmethodsfordoingthisincludeanapplicationoftheExpectation-Maximization(EM)Algorithmus(McCallum,1999)andLabeledLDA(Ramageetal.,2009).Themodelthatweproposeforlanguageidentifi-cationinmultilingualdocumentsissimilartomulti-labeltextclassification.IntheframeworkofEqua-tion1,eachper-tokenlabelziisalanguageandthevocabularyoftokensisnotgivenbywordsbutratherbyspecificbytesequences(Section3.1).Thekeydifferencewithmulti-labeltextclassificationisthatweusemonolingual(i.e.mono-label)trainingdata.Hence,ziseffectivelyobservedforthetrainingdata(sincealltokensmustsharethesamelabel).Toinferzforunlabeleddocuments,weutilizeaGibbssam-pler,closelyrelatedtothatproposedbyGriffithsandSteyvers(2004)forLDA.Thesamplingprobabilityforalabelzifortokenwinadocumentdis:P(zi=j|z−i,w)∝φ(w)j·θ(D)J(2)Phi(w)j=P(wi|zi=j,z−i,w−i)θ(D)j=P(zi=j|z−i)IntheLDAmodel,θ(D)jisassumedtohaveaDirich-letdistributionwithhyperparameterα,andtheworddistributionforeachtopicφ(w)jisalsoassumedtohaveaDirichletdistributionwithhyperparameterβ.Griffiths(2002)describesagenerativemodelforLDAwherebothφ(w)jandθ(D)jareinferredfromtheoutputofaGibbssampler.Inourmethod,weestimateφ(w)jusingmaximumlikelihoodestima-tion(MLE)fromthetrainingdata.Estimatingφ(w)jthroughMLEisequivalenttoamultinomialNaiveBayesmodel(McCallumandNigam,1998):ˆφ(w)j=n(w)j+βn(.)j+Wβ(3)wheren(w)jisthenumberoftimeswordwoccurswithlabelj,andn(.)jisthetotalnumberofwordsthatoccurwithlabelj.Bysettingβto1,weobtainstandardLaplaciansmoothing.Hence,onlyˆθ(D)jisupdatedateachstepintheGibbssampler:ˆθ(D)j=n(D)−i,j+αn(D)−i+Tα(4)wheren(D)−i,jisthenumberoftokensindocumentdthatarecurrentlymappedtolanguagej,andn(D)−iisthetotalnumberoftokensindocumentd.Inbothcases,thecurrentassignmentofziisexcludedfromthecount.Tisthenumberoflanguages(i.e.thesizeofthelabelset).Forsimplicity,wesetαto0.WenotethatintheLDAmodel,αandβinfluencethesparsityofthesolution,andsoitmaybepossibletotunetheseparametersforourmodelaswell.Weleavethisasanavenueforfurtherresearch.
l
D
Ö
w
N
Ö
A
D
e
D
F
R
Ö
M
H
T
T
P
:
/
/
D
ich
R
e
C
T
.
M
ich
T
.
e
D
u
/
T
A
C
l
/
l
A
R
T
ich
C
e
–
P
D
F
/
D
Ö
ich
/
.
1
0
1
1
6
2
/
T
l
A
C
_
A
_
0
0
1
6
3
1
5
6
6
8
5
5
/
/
T
l
A
C
_
A
_
0
0
1
6
3
P
D
.
F
B
j
G
u
e
S
T
T
Ö
N
0
7
S
e
P
e
M
B
e
R
2
0
2
3
31
3.3LanguageIdentificationinMultilingualDocumentsThemodeldescribedinSection3.2canbeusedtocomputethemostlikelydistributiontohavegen-eratedanunlabeleddocumentoveragivensetoflanguagesforwhichwehavemonolingualtrainingdata,bylettingthesetoftermswbethebyten-gramsequencesweselectedusingper-languageinforma-tiongain(Section3.1),andallowingthelabelsztorangeoverthesetofalllanguagesL.Usingtrain-ingdata,wecomputeˆφ(w)J(Equation3),andthenweinferP(Lj|D)foreachLj∈Lfortheunla-beleddocument,byrunningtheGibbssampleruntilthesamplesforziconvergeandthentabulatingzioverthewholedandnormalizingby|D|.Naively,wecouldidentifythelanguagespresentinthedoc-umentbyD.{Lxif∃(zi=Lx|D)},butclosely-relatedlanguagestendtohavesimilarfrequencydis-tributionsoverbyten-gramfeatures,andhenceitislikelythatsometokenswillbeincorrectlymappedtoalanguagethatissimilartothe“correct”language.Weaddressthisissuebyfindingthesubsetoflan-guagesλfromthetrainingsetLthatmaximizesP(λ|D)(asimilarapproachistakeninMcCallum(1999)).ThroughanapplicationofBayes’theorem,P(λ|D)∝P(D|λ)·P(λ),notingthatP(D)isanormalizingconstantandcanbedropped.Weas-sumethatP(λ)isconstant(i.e.anysubsetoflan-guagesisequallylikely,areasonableassumptionintheabsenceofotherevidence),andhencemaximizeP(D|λ).ForanygivenD=w1···wnandλ,weinferP(D|λ)fromtheoutputoftheGibbssampler:P(D|λ)=NYi=1P(wi|λ)(5)=NYi=1Xj∈λP(wi|zi=j)P(zi=j)(6)wherebothP(wi|zi=j)andP(zi=j)areesti-matedbytheirmaximumlikelihoodestimates.Inpractice,exhaustiveevaluationofthepowersetofLisprohibitivelyexpensive,andsowegreed-ilyapproximatetheoptimalλusingAlgorithm1.Inessence,weinitiallyrankallthecandidatelanguagesbycomputingthemostlikelydistributionoverthefullsetofcandidatelanguages.Then,foreachofthetop-Nlanguagesinturn,weconsiderwhetherAlgorithm1DetectLang(L,D)LN←top-Nz∈LbyP(z|D)λ←{Lu}foreachLt∈LNdoλ0←λ∪LtifP(D|λ)+T
PDF Herunterladen