Transactions of the Association for Computational Linguistics, vol. 3, pp. 359–373, 2015. Action Editor: Joakim Nivre.
Submission batch: 4/2015; Published 6/2015.
2015 Association for Computational Linguistics. Distributed under a CC-BY-NC-SA 4.0 Licence.
c
(cid:13)
AGraph-basedLatticeDependencyParserforJointMorphologicalSegmentationandSyntacticAnalysisWolfgangSeekerand¨OzlemC¸etino˘gluInstitutf¨urMaschinelleSprachverarbeitungUniversityofStuttgart{seeker,ozlem}@ims.uni-stuttgart.deAbstractSpace-delimitedwordsinTurkishandHe-brewtextcanbefurthersegmentedintomean-ingfulunits,butsyntacticandsemanticcon-textisnecessarytopredictsegmentation.Atthesametime,predictingcorrectsyntac-ticstructuresreliesoncorrectsegmentation.Wepresentagraph-basedlatticedependencyparserthatoperatesonmorphologicallatticestorepresentdifferentsegmentationsandmor-phologicalanalysesforagiveninputsentence.Thelatticeparserpredictsadependencytreeoverapathinthelatticeandthussolvesthejointtaskofsegmentation,morphologicalanalysis,andsyntacticparsing.WeconductexperimentsontheTurkishandtheHebrewtreebankandshowthatthejointmodeloutper-formsthreestate-of-the-artpipelinesystemsonbothdatasets.Ourworkcorroboratesfind-ingsfromconstituencylatticeparsingforHe-brewandpresentsthefirstresultsforfulllat-ticeparsingonTurkish.1IntroductionLinguistictheoryhasprovidedexamplesfrommanydifferentlanguagesinwhichgrammaticalinforma-tionisexpressedviacasemarking,morphologicalagreement,orclitics.Intheselanguages,configura-tionalinformationislessimportantthaninEnglishsincethewordsareovertlymarkedfortheirsyntac-ticrelationstoeachother.Suchmorphologicallyrichlanguagesposemanynewchallengestotoday’snaturallanguageprocessingtechnology,whichhasoftenbeendevelopedforEnglish.Oneofthefirstchallengesisthequestiononhowtorepresentmorphologicallyrichlanguagesandwhatarethebasicunitsofanalysis(Tsarfatyetal.,2010).TheTurkishtreebank(Oflazeretal.,2003),forexample,representswordsassequencesofinflectionalgroups,semanticallycoherentgroupsofmorphemesseparatedbyderivationalboundaries.ThetreebankforModernHebrew(Sima’anetal.,2001)choosesmorphemesasthebasicunitofrep-resentation.Aspace-delimitedwordinthetreebankcanconsistofseveralmorphemesthatmaybelongtoindependentsyntacticcontexts.BothTurkishandHebrewshowhighamountsofambiguitywhenitcomestothecorrectsegmentationofwordsintoinflectionalgroupsandmorphemes,respectively.Withinasentence,cependant,theseam-biguitiescanoftenberesolvedbythesyntacticandsemanticcontextinwhichthesewordsappear.Astandard(dependency)parsingsystemde-cidessegmentation,morphologicalanalysis(includ-ingPOS),andsyntaxoneaftertheotherinapipelinesetup.Whilepipelinesarefastandefficient,theycannotmodelinteractionbetweenthesedifferentlevelsofanalysis,however.Ithasthereforebeenarguedthatjointmodelingofthesethreetasksismoresuitabletotheproblem(Tsarfaty,2006).Inpreviousresearch,severaltransition-basedparsershavebeenproposedtomodelPOS/morphologicaltaggingandparsingjointly(Hatorietal.,2011;BohnetandNivre,2012;Bohnetetal.,2013).SuchparsingsystemshavebeenfurtherextendedtoalsosolvethesegmentationprobleminChinese(Ha-torietal.,2012;LiandZhou,2012;Zhangetal.,2014).Transition-basedparsersareattractivesince
je
D
o
w
n
o
un
d
e
d
F
r
o
m
h
t
t
p
:
/
/
d
je
r
e
c
t
.
m
je
t
.
e
d
toi
/
t
un
c
je
/
je
un
r
t
je
c
e
–
p
d
F
/
d
o
je
/
.
1
0
1
1
6
2
/
t
je
un
c
_
un
_
0
0
1
4
4
1
5
6
6
7
9
4
/
/
t
je
un
c
_
un
_
0
0
1
4
4
p
d
.
F
b
oui
g
toi
e
s
t
t
o
n
0
8
S
e
p
e
m
b
e
r
2
0
2
3
360
theydonotrelyonglobaloptimizationandthusdealwellwiththeincreasedmodelcomplexitythatcomeswithjointmodeling.Nonetheless,graph-basedmodelshavebeenproposedaswell,e.g.byLietal.(2011)forjointPOStagginganddependencyparsing.Theirparsersmodelthejointproblemdi-rectlyatthecostofincreasedmodelcomplexity.Inthispaper,wepresentagraph-baseddepen-dencyparserforlatticeparsingthathandlesthein-creasedcomplexitybyapplyingdualdecomposi-tion.Theparseroperatesonmorphologicallat-ticesandpredictswordsegmentation,morphologi-calanalysis,anddependencysyntaxjointly.Itde-composestheproblemintoseveralsubproblemsandusesdualdecompositiontofindacommonsolution(Kooetal.,2010;Martinsetal.,2010).Thesub-problemsaredefinedsuchthattheycanbesolvedef-ficientlyandagreementisfoundinaniterativefash-ion.Decomposingtheproblemthuskeepsthecom-plexityofthejointparseronatractablelevel.WetesttheparserontheTurkishandtheHe-brewtreebank.Thesegmentationproblemintheselanguagescanbetackledwiththesameapproacheventhoughtheirunderlyinglinguisticmotivationisquitedifferent.Inourexperiments,thelatticede-pendencyparseroutperformsthreestate-of-the-artpipelinesystems.LatticeparsingforHebrewhasbeenthoroughlyinvestigatedinconstituencypars-ing(CohenandSmith,2007;GoldbergandTsarfaty,2008;GoldbergandElhadad,2013),demonstratingtheviabilityofjointmodeling.Tothebestofourknowledge,ourworkisthefirsttoapplyfulllatticeparsingtotheTurkishtreebank.WeintroducethesegmentationprobleminTurk-ishandHebrewinSection2andpresentthelatticeparserinSection3.Sections4and5describetheexperimentsandtheirresultsandwediscussrelatedworkinSection6.WeconcludewithSection7.2WordSegmentationinTurkishandHebrewAlotofmorphosyntacticinformationisovertlymarkedonwordsinmorphologicallyrichlanguages.Itisalsocommontoexpresssyntacticinforma-tionthroughderivationorcomposition.Asacon-sequencethesewords,orthographicallywrittento-gether,actuallyhaveword-internalsyntacticstruc-tures.Moreover,word-externalrelationsmayde-pendontheword-internalstructures,e.g.,awordcouldbegrammaticallyrelatedtoonlypartsofan-otherwordinsteadofthewhole.Forinstance,intheTurkishsentenceekmekaldım,eachwordhastwoanalyses.ekmekmeans‘bread’orthenominal‘planting’whichisderivedfromtheverbstemek‘plant’withthenominalizationsuffixmek.aldımhasthemeaning‘Ibought’whichde-composesasal-dı-m‘buy-Past-1sg’.Italsomeans‘Iwasred’,whichisderivedfromtheadjectiveal‘red’,inflectedforpasttense,1stpersonsingular.Dependingontheselectedmorphologicalanaly-sisforeachword,syntaxandsemanticsofthesen-tencechange.Whenthefirstanalysisisselectedforbothwords,thesyntacticrepresentationofthesen-tenceisgiveninFigure1,whichcorrespondstothemeaning‘Iboughtbread’.Whenthenominal‘plant-ing’isselectedforthefirstword,itisagrammaticalsentencealbeitwithanimplausablemeaning.Whenthederivationalanalysisofthesecondwordisse-lected,regardlessofthemorphologicalanalysisofthefirstword,thesentenceisungrammaticalduetosubject-verbagreementfailure.Althoughallmor-phologicalanalysesforthesetwowordsarecorrectinisolation,whentheyoccurinthesamesyntacticcontextonlysomecombinationsaregrammatical.ekmekaldımNoun+NomVerb+Past+1sgOBJIboughtbread.Figure1:Dependencyrepresentationforekmekaldım.Thissmallexampledemonstratesthatthesyntac-ticstructuredependsonthemorphologicaldisam-biguationofthewords.Atthesametime,itshowsthatsyntaxcanhelppicktherightmorphologicalanalysis.Forajointsystemtodecidethemorphologicalandsyntacticrepresentationtogether,allpossibleanalysesmustbeavailabletothesystem.Thepos-siblemorphologicalanalysesofawordcanbeeffi-cientlyrepresentedinalatticestructure.ThelatticerepresentationofthesentenceinFigure1isgiveninFigure2,withdoublecirclesdenotingwordbound-
je
D
o
w
n
o
un
d
e
d
F
r
o
m
h
t
t
p
:
/
/
d
je
r
e
c
t
.
m
je
t
.
e
d
toi
/
t
un
c
je
/
je
un
r
t
je
c
e
–
p
d
F
/
d
o
je
/
.
1
0
1
1
6
2
/
t
je
un
c
_
un
_
0
0
1
4
4
1
5
6
6
7
9
4
/
/
t
je
un
c
_
un
_
0
0
1
4
4
p
d
.
F
b
oui
g
toi
e
s
t
t
o
n
0
8
S
e
p
e
m
b
e
r
2
0
2
3
361
aries.Asentencelatticeistheconcatenationofitswordlattices.Amorphologicalanalysisofawordisafullpathfromtheinitialstatetothefinalstateofitslattice.Labelsonthetransitionsarethesurfaceformandunderlyingmorphologicalrepresentationofsegments.112345ekmek/Noun+Nomek/Verbmek/Inf+Noun+Nomaldım/Verb+Past+1sgal/Adjdım/Verb+Past+1sgFigure2:Amorphologicallatticeforekmekaldım.LatticesalsocapturewellthesegmentationofwordsinHebrew.DifferentfromTurkish,Hebrewsegmentscanbesyntacticunitslikedeterminers,prepositions,orrelativizersattachedtostemseg-ments.InanexamplegivenbyGoldbergandTsar-faty(2008),thewordhneim‘thepleasant/made-pleasant’hasthreeanalysescorrespondingtothelat-ticeinFigure3.123hneim/VBh/DTneim/VBneim/JJFigure3:Thelatticeforhneim(GoldbergandTsarfaty,2008).BoththeHebrewandtheTurkishtreebankanno-tatedependenciesbetweenunitssmallerthanwords.IntheTurkishtreebank,aspace-delimitedwordissegmentedintooneormoresegmentsdependingonitsmorphologicalrepresentation.Thenumberofsegmentsisdeterminedbythenumberofderiva-tions.Ifitwasderivedntimes,itisrepresentedasn+1segments.Thederivationalboundariesarepartofthemorphologicalrepresentation.IntheTurkishdependencyparsingliterature(Eryi˘gitetal.,2008;C¸etino˘gluandKuhn,2013)thesesegments1Surfaceformsonthetransitionsaregivenforconvenience.IntheTurkishtreebank,onlyfinalsegmentshavesurfaceforms(offullwords),thesurfaceformsofnon-finalsegmentsarerep-resentedasunderscores.arecalledinflectionalgroups(IGs).IGsconsistofoneormoreinflectionalmorphemes.Theheadofanon-finalIGistheIGtoitsrightwithadependencyrelationDERIV.TheheadofafinalIGcouldbeanyIGofanotherword.TheHebrewtreebankdefinesrelationsbetweenmorphemes(Sima’anetal.,2001).Thosemor-phemescorrespondtowhatisusuallyconsideredaseparatesyntacticunitinEnglish.InHebrewscript,wordclasseslikeprepositionsandconjunctionsarealwayswrittentogetherwiththefollowingword.ContrarytoTurkish,syntacticheadsofbothnon-finalandfinalsegmentscanbeinternalorexternaltothesamespace-delimitedword.Forconvenience,wewillusetokentorefertothesmallestunitofprocessingfortheremainderofthepaper.ItcorrespondstoIGsinTurkishandmor-phemesinHebrew.Atransitioninamorphologicallatticethereforerepresentsonetoken.Wewillusewordtorefertospace-delimitedwords.2Instan-dardparsing,thesetwotermsusuallycoincidewithatokeninasentencebeingseparatedfromthesur-roundingonesbyspace.3LatticeParsingOnecanthinkoflatticeparsingastwotasksthattheparsersolvessimultaneously:theparserneedstofindapaththroughthelatticeanditneedstofindaparsetree.Importantly,theparsersolvesthistaskundertheconditionthattheparsetreeandthepathagreewitheachother,i.e.thetokensthattheparsetreespansovermustformthepaththroughthelat-tice.Decomposingtheprobleminthiswaydefinesthethreecomponentsfortheparser.LetxbeaninputlatticeandT={ROOT,t1,t2,…,tn}bethesetoftokensinx.Inwhatfollows,weassumetwodifferentstruc-tures,latticesanddependencytrees.Dependencytreesarerepresentedasdirectedacyclictreeswithaspecialrootnode(ROOT),whereaslatticesaredirectedacyclicgraphswithonedefinedstartstateandonedefinedendstate(seeFigures2and3).Fordependencytrees,wewillusethetermsnodeandarctorefertotheverticesandtheedgesbetweenthevertices,respectively.Tokensarerepresentedas2Thisisatechnicaldefinitionofwordandhasnoambitiontomakeclaimsaboutthelinguisticdefinitionofaword.
je
D
o
w
n
o
un
d
e
d
F
r
o
m
h
t
t
p
:
/
/
d
je
r
e
c
t
.
m
je
t
.
e
d
toi
/
t
un
c
je
/
je
un
r
t
je
c
e
–
p
d
F
/
d
o
je
/
.
1
0
1
1
6
2
/
t
je
un
c
_
un
_
0
0
1
4
4
1
5
6
6
7
9
4
/
/
t
je
un
c
_
un
_
0
0
1
4
4
p
d
.
F
b
oui
g
toi
e
s
t
t
o
n
0
8
S
e
p
e
m
b
e
r
2
0
2
3
362
nodesinthedependencytree.Forlattices,weusethetermsstateandtransitiontorefertotheverticesandtheiredgesinthelattice.Tokensarerepresentedastransitionsbetweenstatesinthelattice.FindThePath.Atokenbigraminalatticexisapairoftwotransitionsht,t0i,suchthatthetargetstateoftinxcoincideswiththesourcestateoft0inx.Achainofoverlappingbigramsthatstartsfromtheinitialstateandendsinthefinalstateformsapaththroughthelattice.WerepresenttheROOTto-kenasthefirsttransition,i.e.asingletransitionthatleavestheinitialstateofthelattice.Givenalatticex,wedefinetheindexsetofto-kenbigramsinthelatticetobeS:={ht,t0i|t,t0∈T,cible(X,t)=source(X,t0)}.Forlater,wefur-thermoredefineS|t:={hk,ti|hk,ti∈S,k∈T}tobethesetofbigramsthathavetatthesecondposition.Aconsecutivepaththroughthelatticeisdefinedasanindicatorvectorp:=hpsis∈Swhereps=1meansthatbigramsispartofthepath,oth-erwiseps=0.WedefinePasthesetofallwell-formedpaths,i.e.allpathsthatleadfromtheinitialtothefinalstate.Weusealinearmodelthatfactorsoverbigrams.GivenascoringfunctionfPthatassignsscorestopaths,thepathwiththehighestscorecanbefoundbyˆp=argmaxp∈PfP(p)withfP(p)=Xs∈Spsw·φSEG(s)whereφSEGisthefeatureextractionfunctionforto-kenbigrams.Thehighest-scoringpaththroughthelatticecanbefoundwiththeViterbialgorithm.Weusethisbigrammodellateralsoasastandalonedisambiguatorformorphologicallatticestofindthehighest-scoringpathinalattice.FindTheTree.WedefinetheindexsetofarcsinadependencytreeasA:={hh,d,li|h∈T,d∈T−{ROOT},l∈L,h6=d}withLbeingasetofdependencyrelations.Adependencytreeisdefinedasanindicatorvectory:=hyaia∈Awhereya=1meansthatarcaisintheparse,otherwiseya=0.WedefineYtobethesetofallwell-formeddepen-dencytrees.WefollowKooetal.(2010)andassumeanarc-factoredmodel(McDonaldetal.,2005)tofindthehighest-scoringparse.GivenascoringfunctionfTthatassignsscorestoparses,theproblemoffindingthehighestscoringparseisdefinedasˆy=argmaxy∈YfT(oui)withfT(oui)=Xa∈Ayaw·φARC(un)whereφARCisthefeatureextractionfunctionforsin-glearcsandwistheweightvector.WeusetheChu-Liu-Edmondsalgorithm(CLE)tofindthehighest-scoringparse(ChuandLiu,1965;Edmonds,1967).Notethatthealgorithmincludesalltokensofthelat-ticeintothespanningtree,notjustsometokensonsomepath.Chu-Liu-Edmondsfurthermoreenforcesthetreepropertiesoftheoutput,i.e.acyclicityandexactlyoneheadpertoken.AgreementConstraints.Tomakethepathandtheparsetreeagreewitheachother,weintroduceanadditionaldependencyrelationNORELintoL.WedefineatokenthatisattachedtoROOTwithrela-tionNORELtobenotonthepaththroughthelattice.Thesearcsarenotscoredbythestatisticalmodel,theysimplyserveasameansforCLEtomarkto-kensasnotbeingpartofthepathbyattachingthemtoROOTwiththisrelation.TheparsercanpredicttheNORELlabelonlyonarcsattachedtoroot.Weintroducetwoagreementconstraintstoensurethat(je)alltokensnotonthepatharemarkedwithNORELandmustbeattachedtoROOTand(ii)to-kenscannotbedependentsoftokensmarkedwithNOREL.ThefirstconstraintisimplementedasanXOR(⊕)factor(Martinsetal.,2011b)overtokenbigramsandarcs.Itstatesthatforatokent,eitheroneofitsbigrams3oritsNOREL-arcmustbeactive.Thereisonesuchconstraintforeachtokeninthelattice.Ms∈S|tps⊕yhROOT,t,NORELiforallt∈T(1)Thesecondconstraintensuresthatatokenthatispartofthepathwillnotbeattachedtoatokenthat3Thelatticeensuresthatalwaysonlyoneofthebigramswiththesametokeninsecondpositioncanbepartofapath.
je
D
o
w
n
o
un
d
e
d
F
r
o
m
h
t
t
p
:
/
/
d
je
r
e
c
t
.
m
je
t
.
e
d
toi
/
t
un
c
je
/
je
un
r
t
je
c
e
–
p
d
F
/
d
o
je
/
.
1
0
1
1
6
2
/
t
je
un
c
_
un
_
0
0
1
4
4
1
5
6
6
7
9
4
/
/
t
je
un
c
_
un
_
0
0
1
4
4
p
d
.
F
b
oui
g
toi
e
s
t
t
o
n
0
8
S
e
p
e
m
b
e
r
2
0
2
3
363
isnot.Itthusguaranteesthecoherenceofthede-pendencytreeoverthepaththroughthelattice.Itisimplementedasanimplication(=⇒)factor(Mar-tinsetal.,2015).ItstatesthatanactiveNORELarcforatokenhimpliesaninactivearcforallarcshav-inghashead.Thereisonesuchconstraintforeachpossiblearcintheparse.yhROOT,h,NORELi=⇒¬yhh,d,li(2)forallhh,d,li∈A,h6=ROOT,l6=NORELDecidingonapaththroughthelatticepartitionsthetokensintotwogroups:theonesonthepathandtheonesthatarenot.BymeansoftheNORELlabel,theCLEisalsoabletopartitionthetokensintotwogroups:theROOT-NORELtokensandtheproperdependencytreetokens.Thetwoagreementconstraintsthenmakesurethatthetwopartioningsagreewitheachother.ThefirstconstraintexplicitlylinksthetwopartitioningsbyrequiringeachtokentoeitherbelongtothepathortotheROOT-NORELtokens.Thesecondconstraintensuresthatthepar-titioningbytheCLEisconsistent,i.e.tokensat-tachedtoROOTwithNORELcannotmixwiththeothertokensinthetreestructure.Beforetheparseroutputstheparsethetokensthatdonotbelongtothepath/treearediscarded.Theobjectivefunctionofthelatticeparserisargmaxy∈Y,p∈PfT(oui)+fP(p)subjecttothetwoagreementconstraintsinEqua-tions(1)et(2).WeuseAlternatingDirectionsDualDecomposi-tionorAD3(Martinsetal.,2011a)4tofindtheop-timalsolutiontothisconstrainedoptimizationprob-lem.CLEcanbeimplementedsuchthatitsworstcasecomplexityisO(T2),whiletheViterbialgo-rithmneededtofindthepathisofworstcasecom-plexityO(QT2),whereQisthenumberofstatesinthelattice.Insteadofcombiningthesetwoprob-lemsdirectly,whichwouldmultiplytheircomplex-ity,AD3combinesthemadditively,suchthatthecomplexityoftheparserisO(k(T2+QT2))withkbeingthenumberofiterationsthatAD3isrun.4http://www.ark.cs.cmu.edu/AD3/Second-orderParsing.Tofacilitatesecond-orderfeatures,weusegrandparent-siblingheadautomataasproposedinKooetal.(2010),whichweextendtoincludedependencyrelations.Theheadautomataallowtheparsertomodelconsecutivesiblingandgrandparentrelations.Thearchitectureoftheparserdoesnotneedtobechangedatalltoincludethesecond-orderfactors.Theheadautomataaresimplyanothercomponent.TheycomputesolutionsoverthesamesetofarcindicatorvariablesastheCLEandAD3thusensuresthattheoutputofthetwoalgo-rithmsagreesonthetreestructure(Kooetal.,2010).Thesecond-orderfactorsdominatethecomplexityoftheentireparser,sincesolvingtheheadautomataisofcomplexityO(T4L).Pruning.Weuserule-basedandheuristics-basedpruningtoreducethesearchspaceoftheparser.Arcsbetweentokensthatlieoncompetingpathsthroughthelatticearecutawayasthesetokenscanneverbeinasyntacticrelation.FortheTurkishtree-bank,weintroduceanadditionalrulebasedontheannotationschemeofthetreebank.Inthetreebank,theIGsofawordformachainwitheachIGhavingtheirheadimmediatelytotherightandonlythelastIGchoosingtheheadfreely.Forthenon-finalIGs,wethereforerestricttheheadchoicetoallIGsthatcanimmediatelyfollowitinthelattice.Inordertorestrictthenumberofheads,wetrainasimplepairwiseclassifierthatpredictsthe10bestheadsforeachtoken.Itusesthefirst-orderfeaturesoftheparser’sfeaturemodel.FeatureModel.Theparserextractsfeaturesforbigrams(chemin),arcs(first-order),consecutivesib-lings,andgrandparentrelations(bothsecondorder).Itusesstandardfeatureslikewordform,lemma,POS,morphologicalfeatures,headdirection,andcombinationsthereof.Contextfeaturesaremoredifficultinlatticepars-ingthaninstandardparsingastheleftandrightcon-textofatokenisnotspecifiedbeforeparsing.Wefirstextractedcontextfeaturesfromalltokensthatcanfolloworprecedeatokeninthelattice.Thisledtooverfittingeffectsasthemodelwaslearningspecificlatticepatterns.Wethereforeuselatentleftandrightcontextandextractfeaturesfromonlyoneoftheleft/rightneighbortokens.Thelatentcontextistheleft/rightcontexttokenwiththehighestscore
je
D
o
w
n
o
un
d
e
d
F
r
o
m
h
t
t
p
:
/
/
d
je
r
e
c
t
.
m
je
t
.
e
d
toi
/
t
un
c
je
/
je
un
r
t
je
c
e
–
p
d
F
/
d
o
je
/
.
1
0
1
1
6
2
/
t
je
un
c
_
un
_
0
0
1
4
4
1
5
6
6
7
9
4
/
/
t
je
un
c
_
un
_
0
0
1
4
4
p
d
.
F
b
oui
g
toi
e
s
t
t
o
n
0
8
S
e
p
e
m
b
e
r
2
0
2
3
364
fromthepathfeatures(rawbigramscores,theyarenotchangedbyAD3).Theparserextractscontextfromonetokenineachdirection.Distancefeaturesarealsomoredifficultinlat-ticessincethelineardistancebetweentwotokensdependsontheactualpathchosenbytheparser.Wedefinedistancesimplyasthelengthoftheshortestpathbetweentwotokensinthelattice,butthisdis-tancemaynotcoincidewiththeactualpath.Contextfeaturesanddistancefeaturesshowthatlatticedependencyparsingposesinterestingnewchallengestofeaturedesign.Usinglatentcontextfeaturesisonewayofhandlinguncertaincontext,comparealsothedelayedfeaturesinHatorietal.(2011).Athoroughinvestigationofdifferentop-tionsisneededhere.Learning.Wetrainadiscriminativelinearmodelusingpassive-aggressiveonlinelearning(Crammeretal.,2003)withcost-augmentedinference(Taskaretal.,2005)andparameteraveraging(FreundandSchapire,1999).WeuseHamminglossoverthearcsoftheparsetreeexcludingNORELarcs.Themodeltrainsoneparametervectorthatincludesfea-turesfromthetreeandfromthepath.ThemaximumnumberofiterationsofAD3issetto1000duringtrainingandtesting.Thealgo-rithmsometimesoutputsfractionalsolutions.Dur-ingtraining,themodelisupdatedwiththesefrac-tionalsolutions,weightingthefeaturesandthelossaccordingly.Duringtesting,fractionalsolutionsareprojectedtoanintegersolutionbyfirstrunningthebest-pathalgorithmwiththepathposteriorsoutputbyAD3andafterwardsrunningCLEontheselectedpathweightedbythearcposteriors(Martinsetal.,2009).Intheexperiments,fractionalsolutionsoccurinabout9%ofthesentencesintheTurkishdevelop-mentsetduringtesting.4ExperimentalSetup4.1TheTurkishDataThetrainingsetforTurkishisthe5,635sentencesoftheMETU-SabancıTurkishTreebank(Oflazeretal.,2003).The300sentencesoftheITUvalidationset(Eryi˘git,2012)areusedfortesting.Asthereisnoseparatedevelopmentset,wesplitthetrainingsetinto10partsandused2ofthemasdevelopmentdata.Allmodelsrunonthisdevelopmentsetaretrainedontheremaining8parts.Wealsoreportre-sultsfrom10-foldcrossvalidationonthefulltrain-ingset(10cv).WeusethedetachedversionoftheTurkishtree-bank(Eryi˘gitetal.,2011)wheremultiwordexpres-sionsarerepresentedasseparatetokens.Thetrain-ingsetofthisversioncontains49sentenceswithloops.Wemanuallycorrectedthesesentencesandusethecorrectedversioninourexperiments.5TheTurkishrawinputisfirstpassedthroughamorphologicalanalyzer(Oflazer,1994)inordertocreatemorphologicallatticesasinputtotheparser.Goldanalysesareaddedtothetraininglatticesifthemorphologicalanalyzerfailedtooutputthecorrectanalyses.Forthepipelinesystems,theinputlatticesaredisambiguatedbyrunningamorphologicaldisam-biguator.WetrainourowndisambiguatorusingthebigrammodelfromtheparserandfindthebestpaththroughthelatticewiththeViterbialgorithm.Thedisambiguatorusesthesamebigramfeaturesasthelatticeparser.ThemorphologicaldisambiguatoristrainedontheTurkishtreebankasinC¸etino˘glu(2014).4.2TheHebrewDataThedataforHebrewcomesfromtheSPMRLSharedTask2014(Seddahetal.,2014),whichisbasedonthetreebankforModernHebrew(Sima’anetal.,2001).Itprovideslatticesandpredisam-biguatedinputfiles.Thetraininganddevelopmentlatticescontainedanumberofcircularstructuresduetoself-loopsinsomestates.Weautomaticallyre-movedthetransitionscausingthesecycles.InputlatticesfortrainingwerepreparedasforTurkishbyaddingthegoldstandardpathsifnec-essary.ComparedtotheTurkishdata,theHebrewlatticesaresolargethattrainingtimesforthelat-ticeparserbecameunacceptable.Wethereforeusedourmorphologicaldisambiguatortopredictthe10bestpathsforeachlattice.Alltransitionsinthelat-ticethatwerenotpartofoneofthese10pathswerediscarded.Notethatthenumberofactualpathsintheseprunedlatticesismuchhigherthan10,sincethepathsconvergeaftereachword.Allexperiments5Thecorrectedversionisavailableonthesecondauthor’swebpage.
je
D
o
w
n
o
un
d
e
d
F
r
o
m
h
t
t
p
:
/
/
d
je
r
e
c
t
.
m
je
t
.
e
d
toi
/
t
un
c
je
/
je
un
r
t
je
c
e
–
p
d
F
/
d
o
je
/
.
1
0
1
1
6
2
/
t
je
un
c
_
un
_
0
0
1
4
4
1
5
6
6
7
9
4
/
/
t
je
un
c
_
un
_
0
0
1
4
4
p
d
.
F
b
oui
g
toi
e
s
t
t
o
n
0
8
S
e
p
e
m
b
e
r
2
0
2
3
365
withthejointmodelforHebrewareconductedontheprunedlattices.AsforTurkishwepreprocesstheinputlatticesforallbaselineswithourownmor-phologicaldisambiguator.4.3BaselinesWecomparethelatticeparser(JOINTforTurkish,JOINT10forHebrew)tothreebaselines:MATE,TURBO,andPIPELINE.Thefirsttwobaselinesystemsareoff-the-shelfdependencyparsersthatcurrentlyrepresentthestate-of-the-art.Mateparser6(Bohnet,2009;Bohnet,2010)isagraph-baseddependencyparserthatusesCarreras’decoder(Carreras,2007)andap-proximatesearch(McDonaldandPereira,2006)toproducenon-projectivedependencystructures.Tur-boParser7(Martinsetal.,2013)isagraph-basedparserthatusesadualdecompositionapproachandoutputsnon-projectivestructuresnatively.Thethirdbaselinesystemrunsthelatticeparseronapre-disambiguatedlattice,i.e.inapipelinesetup.Allthreebaselinesarepipelinesetupsandusethesamedisambiguatortopredictapaththroughthelat-tice.Thebigramfeaturesinthedisambiguatorarethesameasinthejointmodel.Thereisthusnodif-ferencebetweenthelatticeparserandthebaselineswithrespecttothefeaturesthatareavailableduringsegmentation.Asopposedtolatticeparsing,base-linesystemsaretrainedonthegoldstandardseg-mentation(andthusgoldmorphologicalanalyses)inthetrainingdata,sinceautomaticallypredictedpathswouldnotguaranteetobecompatiblewiththegolddependencystructures.Thepurposeofthefirsttwobaselinesistocom-parethejointparsertothecurrentstate-of-the-art.However,thefeaturesetsaredifferentbetweenthejointparserandtheoff-the-shelfbaselines.Adiffer-enceinperformancebetweenthejointparserandthefirsttwobaselinesystemsmaythussimplybecausedbyadifferenceinthefeatureset.Thethirdbaselineeliminatesthisdifferenceinthefeaturesetssinceitistheactuallatticeparserthatisrunonadisam-biguatedlattice.Becausethemorphologicaldisam-biguatorforthePIPELINEbaselineisusingthesamefeaturesetasthelatticeparser(thebigrammodel),6http://code.google.com/p/mate-tools7http://www.ark.cs.cmu.edu/TurboParser/,version2.0.1thefactthatthejointparseristrainedandtestedonfulllatticesistheonlydifferencebetweenthesetwosystems.ThePIPELINEbaselinethusallowsustotestdirectlytheeffectofjointdecodingcomparedtoapipelinesetup.4.4EvaluationStandardlabeledandunlabeledattachmentscoresarenotapplicablewhenparsingwithuncertainseg-mentationsincethenumberoftokensintheoutputoftheparsermaynotcoincidewiththenumberoftokensinthegoldstandard.Previousworkthereforesuggestsalternativemethodsforevaluation,e.g.bymeansofprecision,recall,andf-scoreovertokens,seee.g.Tsarfaty(2006)orCohenandSmith(2007).Theuncertaintyofsegmentationfurthermoremakesitveryhardtoevaluatetheotherlevelsofanalysisindependentlyofthesegmentation.Inor-dertodecidewhetherthemorphologicalanalysisofatoken(oritssyntacticattachment)iscorrect,onealwaysneedstofindoutfirsttowhichtokeninthegoldstandarditcorresponds.Byestablishingthiscorrespondence,thesegmentationisalreadybeingevaluated.Evaluatingsyntaxisolatedfromtheotherlevelsofanalysisisthereforenotpossibleingeneral.Hatorietal.(2012)countadependencyrelationcorrectonlywhenboththeheadandthedependenthavethecorrectmorphologicalanalysis(herePOS)andsegmentation.Goldberg(2011,page53)pro-posesasimilarapproach,butonlyrequiressurfaceformstomatchbetweengoldstandardandpredic-tion.Thesemetricscomputeprecisionandrecallovertokens.Eryi˘gitetal.(2008)andEryi˘git(2012)defineanaccuracy(IGeval)forTurkishparsingbytakingadvantageoftheannotationschemeintheTurkishtreebank:Anon-finalIGintheTurkishtree-bankalwayshasitsheadimmediatelytotheright,al-wayswiththesamelabel,whichmakesitpossibletoignoretheinnerdependencyrelations,i.e.theseg-mentation,ofadependentword.Themetricthere-foreonlyneedstocheckforeachwordwhethertheheadofthelastIGisattachedtothecorrectIGinanotherword.Themetricincludesaback-offstrat-egyincasetheheadword’ssegmentationiswrong.Adependencyarcisthencountedascorrectifitat-tachestoanIGinthecorrectwordandthePOStagoftheheadIGisthesameasinthegoldstandard.
je
D
o
w
n
o
un
d
e
d
F
r
o
m
h
t
t
p
:
/
/
d
je
r
e
c
t
.
m
je
t
.
e
d
toi
/
t
un
c
je
/
je
un
r
t
je
c
e
–
p
d
F
/
d
o
je
/
.
1
0
1
1
6
2
/
t
je
un
c
_
un
_
0
0
1
4
4
1
5
6
6
7
9
4
/
/
t
je
un
c
_
un
_
0
0
1
4
4
p
d
.
F
b
oui
g
toi
e
s
t
t
o
n
0
8
S
e
p
e
m
b
e
r
2
0
2
3
366
ParsingEvaluation.WefollowHatorietal.(2012)anduseastrictdefinitionofprecisionandrecall(PREC,REC,F1)overtokenstoevaluatethefulltask.Wefirstalignthetokensofawordintheparseroutputwiththetokensofthecorrespond-ingwordinthegoldstandardusingtheNeedleman-Wunschalgorithm(NeedlemanandWunsch,1970),whichwemodifysoitdoesnotallowformis-matches.Atokenintheparseroutputthatisnotinthegoldstandardisthuspairedwithagapandviceversa.Twotokensmusthavethesamemorphologi-calanalysisinordertomatch.8Atruepositiveisdefinedasapairofmatchingto-kenswhoseheadsarealsoalignedandmatch.Forlabeledscores,thedependencyrelationsmustmatchaswell.Precisionisdefinedasthenumberoftruepositivesoverthenumberoftokensinthepredic-tion,recallisdefinedasthenumberoftrueposi-tivesoverthenumberoftokensinthegoldstandard.F-scoreistheharmonicmeanofprecisionandrecall.Thismetricisverystrictandrequiresalllevelsofanalysistobecorrect.Inordertoevaluatethesyntaxasindependentlyaspossible,wefurthermorereportIGevalforTurkish,withandwithouttheaforemen-tionedbackoffstrategy(IGevalandIGevalSTRICT).ForHebrew,wereportonaversionofprecisionandrecallasdefinedabovethatonlyrequiresthesurfaceformsofthetokenstomatch.9ThismetricisalmosttheoneproposedinGoldberg(2011).Allreportedevaluationmetricsignorepunctuation.WedonotuseTedEvalasdefinedinTsarfatyetal.(2012)eventhoughithasbeenusedprevi-ouslytoevaluatedependencyparsingwithuncer-tainsegmentation(Seddahetal.,2013;Zhangetal.,2015).Thereasonisthatitisnotaninher-entlydependency-basedframeworkandthecon-versionfromconstituencystructurestodependencystructuresinterfereswiththemetric.10Themetric8Themethoddoesnotcreatecross,many-to-one,orone-to-manyalignments,whichcanbeimportantbecauseinveryrarecasesthesametokenoccurstwiceinoneword.9ThemetricwouldnotworkforTurkish,asthesurfaceformsofnon-finalIGsareallrepresentedasunderscores.10Asanexperiment,wetookaTurkishtreebanktreeandcre-atedartificialparsesbyattachingonetokentoadifferentheadeachtime.Allothertokensremainedattachedtotheircorrecthead,andsegmentationiskeptgold.Thisgaveus11parsesthatcontainedexactlyoneattachmenterrorandoneparseiden-ticalwiththegoldstandard.RunningTedEvaloneachoftheproposedinGoldberg(2011)implementsthesameideaswithouteditdistanceandisdefineddirectlyfordependencies.SegmentationEvaluation.Weusethesametoken-basedprecisionandrecalltomeasurethequalityofsegmentationandmorphologicalanalysiswithoutsyntax.Foratokentobecorrect,ithastohavethesamemorphologicalanalysisasthetokeninthegoldstandardtowhichitisaligned.Wefur-thermorereportwordaccuracy(ACCw),whichisthepercentageofwordsthatreceivedthecorrectseg-mentation.5ResultsSegmentationandMorphology.Table1showsthequalityofsegmentationandmorphologicalanal-ysis.ThebaselineforTurkishistheTurkishmorphologicaldisambiguatorbySaketal.(2008),trainedontheTurkishtreebank.ForHebrew,thebaselineisthedisambiguatedlatticesprovidedbytheSPMRL2014SharedTask.11Thebigrammodelisourownmorphologicaldisambiguator.Thejointmodelisthefulllatticeparser,whichhasaccesstosyntacticinformation.Theresultsshowthatthebigrammodelisclearlyoutperformingthebaselinesforbothlanguages.ThefeaturemodelofthebigrammodelwasdevelopedontheTurkishdevelopmentset,butthemodelalsoworkswellforHebrew.Comparingthebigrammodeltothejointmodelshowsthatoverall,thejointmodelperformsbetterthanthebigrammodel.How-ever,thejointmodelmainlyscoresinrecallratherthaninprecision,thebigrammodelisevenaheadofthejointmodelinprecisionforHebrew.Thejointmodeloutperformsthebigrammodelandthebase-linealsoinwordaccuracy.Theresultsdemonstratethatsyntacticinformationisrelevanttoresolveam-biguityinsegmentationandmorphologyforTurkishandHebrew.11incorrectparsesgaveus5differentscores.Thedifferencesarecausedbythetransformationofdependencytreestocon-stituencytrees,becausetheconstituencytreeshavedifferenteditdistancescomparedtothegoldstandard.Consequently,thismeansthatsomeattachmenterrorsofthedependencyparserarepunishedmorethanothersinanunpredictableway.11AdescriptiononhowtheselatticeareproducedisgiveninSeddahetal.(2013,page159)
je
D
o
w
n
o
un
d
e
d
F
r
o
m
h
t
t
p
:
/
/
d
je
r
e
c
t
.
m
je
t
.
e
d
toi
/
t
un
c
je
/
je
un
r
t
je
c
e
–
p
d
F
/
d
o
je
/
.
1
0
1
1
6
2
/
t
je
un
c
_
un
_
0
0
1
4
4
1
5
6
6
7
9
4
/
/
t
je
un
c
_
un
_
0
0
1
4
4
p
d
.
F
b
oui
g
toi
e
s
t
t
o
n
0
8
S
e
p
e
m
b
e
r
2
0
2
3
367
TurkishHebrewdatasystemPRECRECF1ACCwPRECRECF1ACCwdevBASELINE89.5988.1488.8687.9785.9984.0785.0280.30BIGRAMMODEL90.6989.5290.1089.4586.8486.3086.5783.46JOINTMODEL90.8090.2290.5189.9486.6887.4987.0884.67testBASELINE89.4688.5188.9987.9581.7979.8380.8074.85BIGRAMMODEL89.9689.2389.5988.7184.4483.2283.8379.60JOINTMODEL90.1989.7489.9789.2583.8883.9983.9480.28Table1:Pathselectionquality.LABELEDUNLABELEDIGevalSTRICTIGevaldatasystemPRECRECF1PRECRECF1UASIGLASIGUASIGLASIGdevMATE62.5461.7362.1469.4468.5468.9870.6060.1074.8863.46TURBO63.5462.7163.1270.6869.7670.2272.2261.2476.5864.73PIPELINE63.8663.0363.4470.6569.7370.1972.2661.8276.6465.49JOINT64.2163.79∗64.0070.9670.50∗70.7372.66∗62.4076.6165.5910cvMATE63.2862.4962.8870.3769.5069.9471.7561.2675.8464.42TURBO63.8263.0363.4271.1270.2470.6872.7761.8976.9365.09PIPELINE64.9764.1764.5771.7170.8371.2773.6663.5277.6866.82JOINT65.2764.84†65.0672.05∗71.58†71.8273.9363.8577.7466.83testMATE64.6464.1264.3870.6270.0470.3371.9961.8477.0865.98TURBO65.3664.8365.0971.6671.0871.3773.1662.7678.3767.02PIPELINE66.4065.8666.1372.3071.7272.0174.3364.4079.6169.02JOINT67.3366.99∗67.1672.94∗72.58∗72.7675.0265.3279.4568.99Table2:ParsingresultsforTurkish.Statisticallysignificantdifferencesbetweenthejointsystemandthepipelinesystemaremarkedwith†(p<0.01)and∗(p<0.05).SignificancetestingwasperformedusingtheWilcoxonSignedRankTest(notforF1).Turkish.Table2presentstheresultsoftheeval-uationofthethreebaselinesystemsandthelatticeparserontheTurkishdata.ThePIPELINEandtheJOINTsystemgivebetterresultsthantheothertwobaselinesacrosstheboard.Thisshowsthatthefea-turesetofthelatticeparserisbettersuitedtotheTurkishtreebankthanthefeaturesetofMateparserandTurboparser.Itisnotasurprisingresultthough,sincethelatticeparserwasdevelopedforTurkishwhereastheothertwoparsersweredevelopedforothertreebanks.TheJOINTsystemoutperformsthePIPELINEsys-temwithrespecttothefirstthreemetrics.Thesemetricsevaluatesyntax,segmentation,andmorpho-logicalanalysisjointly.Higherscoresheremeanthattheseaspectsincombinationhavebecomebet-ter.ThedifferencesbetweenthePIPELINEandtheJOINTmodelareconsistentlystatisticallysignificantwithrespecttorecall,butonlyinsomecaseswithre-specttoprecision.Thesyntacticinformationthatisavailabletothejointmodelthusseemstoimproverecallratherthanprecision.ThelasttwocolumnsinTable2showanevalu-ationusingIGeval.TheIGevalmetricisdesignedtoevaluatethesyntacticqualitywithlessattentiontomorphologicalanalysisandsegmentation.Here,bothPIPELINEandJOINTachieveverysimilarre-sultsandnoneofthedifferencesisstatisticalsignif-icant.Theseresultssuggestthatagoodpartoftheimprovementsinthelatticeparseroccursinthemor-phologicalanalysis/segmentation,whereasthequal-ityofsyntacticannotationbasicallystaysthesamebetweenthepipelineandthejointmodel.Hebrew.TheexperimentalresultsontheHebrewdataareshowninTable3.Thethreebaselinesper-formverysimilarly.Allthreebaselinesystemsarerunontheoutputofthesamedisambiguator,which
l
D
o
w
n
o
a
d
e
d
f
r
o
m
h
t
t
p
:
/
/
d
i
r
e
c
t
.
m
i
t
.
e
d
u
/
t
a
c
l
/
l
a
r
t
i
c
e
-
p
d
f
/
d
o
i
/
.
1
0
1
1
6
2
/
t
l
a
c
_
a
_
0
0
1
4
4
1
5
6
6
7
9
4
/
/
t
l
a
c
_
a
_
0
0
1
4
4
p
d
.
f
b
y
g
u
e
s
t
t
o
n
0
8
S
e
p
e
m
b
e
r
2
0
2
3
368
meansthatthefeaturemodelsoftheparsersseemtobeequallywellsuitedtotheHebrewtreebank.ThefeaturemodelofthelatticeparserthatisusedinthePIPELINEbaselinewasnotadaptedtoHebrewinanyway,butwasusedasitwasdevelopedfortheTurk-ishdata.Comparedtothethreebaselines,thejointmodeloutperformsthemforbothlabeledandunlabeledscores.AstheonlydifferencebetweenPIPELINEandJOINTisthefactthatthelatterperformsjointdecoding,theresultssupportthefindingsincon-stituencyparsingbyTsarfaty(2006),CohenandSmith(2007),andGoldbergandTsarfaty(2008),namelythatjointdecodingisabettermodelforHe-brewparsing.Judgingfromstatisticalsignificance,theJOINTmodelimprovesrecallratherthanpreci-sion,apicturethatwefoundforTurkishaswell.LABELEDUNLABELEDdatasystemPRECRECF1PRECRECF1devMATE65.4165.0065.2070.6570.2170.43TURBO65.1264.7264.9270.4470.0070.22PIPELINE65.6465.2365.4470.6570.2170.43JOINT1066.8267.44†67.1371.4772.13∗71.80testMATE63.1662.2562.7067.5266.5567.03TURBO63.0662.1662.6167.2766.3166.79PIPELINE63.6362.7263.1767.6266.6567.14JOINT1063.8163.89†63.8567.7967.88†67.84Table3:Statisticallysignificantdifferencesbetweenthejointsystemandthepipelinesystemaremarkedwith†(p<0.01)and∗(p<0.05).SignificancetestingwasperformedusingtheWilcoxonSignedRankTest(notforF1).AsdescribedinSection4.4,wecannotevaluatethesyntaxentirelyindependentlyonHebrew,butwecaneliminatethemorphologicallevel.Table4showstheresultsoftheevaluationwhenonlysyn-taxandsurfaceformsarematched.Theoverallpic-turecomparedtotheevaluationshowninTable3doesnotchange,however.Alsowhendisregardingthequalityofmorphology,theJOINTmodeloutper-formsthePIPELINE,notablywithrespecttorecall.6RelatedWorkGraph-basedParsing.Ourbasicarchitecturere-semblesthejointconstituencyparsingandPOStag-gingmodelbyRushetal.(2010),butourmodelLABELEDUNLABELEDdatasystemPRECRECF1PRECRECF1devMATE68.0567.6267.8374.7074.2474.47TURBO67.9767.5467.7574.5874.1274.35PIPELINE68.5668.1468.3574.8474.3774.60JOINT1069.2369.87†69.5574.8875.58†75.23testMATE66.1765.2265.6971.6270.6071.11TURBO66.1465.1965.6671.3870.3570.86PIPELINE66.8165.8566.3371.8270.7971.30JOINT1066.6366.72†66.6871.4871.57†71.52Table4:ParsingresultsforHebrew,evaluatedwithoutmorphology.Statisticallysignificantdifferencesbetweenthejointsystemandthepipelinesystemaremarkedwith†.SignificancetestingwasperformedusingtheWilcoxonSignedRankTestwithp<0.01(notforF1).needsadditionalconstraintstoenforceagreementbetweenthetwotasks.Martinsetal.(2011a)andMartinsetal.(2015)showhowsuchfirst-orderlogicconstraintscanberepresentedassubproblemsindualdecomposition.Similarapproaches,wheresuchconstraintsareusedtoensurecertainproper-tiesintheoutputstructures,havebeenusede.g.insemanticparsing(Dasetal.,2012),compressivesummarization(AlmeidaandMartins,2013),andjointquotationattributionandcoreferenceresolu-tion(Almeidaetal.,2014).Parsersthatusedualde-compositionareproposedinKooetal.(2010)andMartinsetal.(2010).FromKooetal.(2010),weadoptedtheideaofusingtheChu-Liu-Edmondsal-gorithmtoensuretreepropertiesintheoutputaswellassecond-orderparsingwithheadautomata.Lietal.(2011)extendseveralhigher-ordervari-antsoftheEisnerdecoder(Eisner,1997)suchthatPOStagsarepredictedjointlywithsyntax.Thecomplexityoftheirjointmodelsincreasesbypoly-nomialsofthetagsetsize.Duetothedualdecompo-sitionapproach,thecomplexityofourparserstaysequaltothecomplexityofthemostcomplexsub-problem,whichisthesecond-orderheadautomatainourcase.Transition-basedParsing.Jointmodelsintransition-basedparsingusuallyintroduceavariantoftheshifttransitionthatperformstheadditionaltask,e.g.itadditionallypredictsthePOStagandpossiblymorphologicalfeaturesofatokenthatisbeingshifted(Hatorietal.,2011;BohnetandNivre,
l
D
o
w
n
o
a
d
e
d
f
r
o
m
h
t
t
p
:
/
/
d
i
r
e
c
t
.
m
i
t
.
e
d
u
/
t
a
c
l
/
l
a
r
t
i
c
e
-
p
d
f
/
d
o
i
/
.
1
0
1
1
6
2
/
t
l
a
c
_
a
_
0
0
1
4
4
1
5
6
6
7
9
4
/
/
t
l
a
c
_
a
_
0
0
1
4
4
p
d
.
f
b
y
g
u
e
s
t
t
o
n
0
8
S
e
p
e
m
b
e
r
2
0
2
3
369
2012;Bohnetetal.,2013).Optimizationoverthejointmodelisachievedbybeamsearch.Toalsosolvethewordsegmentationtask,severalmodelsforChinesewereproposedthatparseonthelevelofsinglecharacters,formingwordsfromcharacterswithaspecialappendtransition(Hatorietal.,2012;LiandZhou,2012)orpredictingwordinternalstructurealongwithsyntax(Zhangetal.,2014).Tousesuchatransition-basedsystemforthesegmen-tationtaskinTurkishorHebrew,theshifttransitionwouldhavetobechangedtodotheoppositeoftheappendtransitionintheChineseparsers:segmentanincomingtokenintoseveralones,forexamplebasedontheoutputofamorphologicalanalyzer.Easy-firstParsing.Maetal.(2012)introduceavariantoftheeasy-firstparser(GoldbergandEl-hadad,2010un)thatusesanadditionaloperationtoPOStaginputtokens.TheoperationsareorderedsuchthattheparsercanonlyintroduceadependencyarcbetweentwotokensthathavereceivedaPOStagalready.Tratz(2013)presentsasimilarsystemforArabicthatdefinesseveralmoreoperationstodealwithsegmentationambiguity.Sampling-basedParsing.Zhangetal.(2015)presentajointmodelthatreliesonsamplingandgreedyhill-climbingfordecoding,butallowsforar-bitrarilycomplexscoringfunctionsthusopeningac-cesstoglobalandcross-levelfeatures.Suchfea-turescouldbesimulatedinourmodelbyaddingad-ditionalfactorsintheformofsoftconstraints(con-straintswithoutput,seeMartinsetal.(2015)),butthiswouldintroduceaconsiderablenumberofaddi-tionalfactorswithanotableimpactonperformance.ConstituencyParsing.Jointmodelshavealsobeeninvestigatedinconstituencyparsing,notablyforHebrew.Tsarfaty(2006)alreadydiscussesfulljointmodels,butthefirstfullparserswerepresentedinCohenandSmith(2007),GoldbergandTsar-faty(2008),andlaterGoldbergandElhadad(2013).GreenandManning(2010)presentasimilarparserforArabic.Amongthese,someauthorsemphasizetheimportanceofincludingscoresfromthemor-phologicalmodelintotheparsingmodel,whereasothermodelsdonotusethematall.Inourparser,themodelistrainedjointlyforbothtaskswithoutweightingthetwotasksdifferently.ParsingHebrewandTurkish.JointmodelsforHebrewparsingweremostlyinvestigatedforcon-stituencyparsing(seeabove).TherehasbeensomeworkspecificallyonHebrewdependencyparsing(GoldbergandElhadad,2009;GoldbergandEl-hadad,2010b;Goldberg,2011),butnotinthecon-textofjointmodels.TurkishdependencyparsingwaspioneeredinEryi˘gitandOflazer(2006)andEryi˘gitetal.(2008).Theycompareparsingbasedoninflectionalgroupstoword-basedparsingandconcludethattheformerismoresuitableforTurkish.C¸etino˘gluandKuhn(2013)arefirsttodiscussjointmodelsforTurkishandpresentexperimentsforjointPOStaggingandparsing,butuseapipelinetodecideonsegmenta-tionandmorphologicalfeatures.Tothebestofourknowledge,therecurrentlyexistsnoworkonfulllat-ticeparsingforTurkish.7ConclusionMorphologicallyrichlanguagesposemanychal-lengestostandarddependencyparsingsystems,oneofthembeingthatthenumberoftokensintheoutputisnotalwaysknownbeforehand.Solvingthisprob-leminapipelinesetupleadstoefficientsystemsbutsystematicallyexcludesinteractionbetweenthelex-ical,morphological,andsyntacticlevelofanalysis.Inthiswork,wehavepresentedagraph-basedlatticedependencyparserthatoperatesonmorpho-logicallatticesandsimultaneouslypredictsade-pendencytreeandapaththroughthelattice.WetestedthejointmodelontheTurkishtreebankandthetreebankofModernHebrewanddemonstratedthatthejointmodeloutperformsthreestate-of-the-artpipelinemodels.WepresentedthefirstresultsforfulllatticeparsingontheTurkishtreebank.TheresultsontheHebrewtreebankcorroboratefindingsinconstituencyparsing(CohenandSmith,2007;GoldbergandTsarfaty,2008).AcknowledgmentsWethankouranonymousreviewersfortheirhelp-fulcomments.WealsothankAndersBj¨orkelundformanyusefuldiscussions.ThisworkwasfundedbytheDeutscheForschungsgemeinschaft(DFG)viaSFB732,projectsD2andD8.
l
D
o
w
n
o
a
d
e
d
f
r
o
m
h
t
t
p
:
/
/
d
i
r
e
c
t
.
m
i
t
.
e
d
u
/
t
a
c
l
/
l
a
r
t
i
c
e
-
p
d
f
/
d
o
i
/
.
1
0
1
1
6
2
/
t
l
a
c
_
a
_
0
0
1
4
4
1
5
6
6
7
9
4
/
/
t
l
a
c
_
a
_
0
0
1
4
4
p
d
.
f
b
y
g
u
e
s
t
t
o
n
0
8
S
e
p
e
m
b
e
r
2
0
2
3
370
ReferencesMiguelAlmeidaandAndreMartins.2013.FastandRobustCompressiveSummarizationwithDualDe-compositionandMulti-TaskLearning.InProceed-ingsofthe51stAnnualMeetingoftheAssociationforComputationalLinguistics(Volume1:LongPapers),pages196–206,Sofia,Bulgaria,August.AssociationforComputationalLinguistics.MarianaS.C.Almeida,MiguelB.Almeida,andAndr´eF.T.Martins.2014.AJointModelforQuotationAt-tributionandCoreferenceResolution.InProceedingsofthe14thConferenceoftheEuropeanChapteroftheAssociationforComputationalLinguistics,pages39–48,Gothenburg,Sweden,April.AssociationforCom-putationalLinguistics.BerndBohnetandJoakimNivre.2012.ATransition-BasedSystemforJointPart-of-SpeechTaggingandLabeledNon-ProjectiveDependencyParsing.InPro-ceedingsofthe2012JointConferenceonEmpiricalMethodsinNaturalLanguageProcessingandCom-putationalNaturalLanguageLearning,pages1455–1465,Jeju,SouthKorea.AssociationforComputa-tionalLinguistics.BerndBohnet,JoakimNivre,IgorBoguslavsky,RichrdFarkas,FilipGinter,andJanHaji.2013.JointMor-phologicalandSyntacticAnalysisforRichlyInflectedLanguages.TransactionsoftheAssociationforCom-putationalLinguistics,1:415–428.BerndBohnet.2009.EfficientParsingofSyntacticandSemanticDependencyStructures.InProceedingsoftheThirteenthConferenceonComputationalNatu-ralLanguageLearning(CoNLL2009):SharedTask,pages67–72,Boulder,Colorado,June.AssociationforComputationalLinguistics.BerndBohnet.2010.Veryhighaccuracyandfastdepen-dencyparsingisnotacontradiction.InProceedingsofthe23rdInternationalConferenceonComputationalLinguistics,pages89–97,Beijing,China.InternationalCommitteeonComputationalLinguistics.XavierCarreras.2007.ExperimentswithaHigher-OrderProjectiveDependencyParser.InProceedingsoftheCoNLLSharedTaskSessionofEMNLP-CoNLL2007,pages957–961,Prague,CzechRepublic,June.AssociationforComputationalLinguistics.¨OzlemC¸etino˘gluandJonasKuhn.2013.TowardsJointMorphologicalAnalysisandDependencyPars-ingofTurkish.InProceedingsoftheSecondIn-ternationalConferenceonDependencyLinguistics(DepLing2013),pages23–32,Prague,CzechRepub-lic,August.CharlesUniversityinPrague,Matfyz-press,Prague,CzechRepublic.¨OzlemC¸etino˘glu.2014.TurkishTreebankasaGoldStandardforMorphologicalDisambiguationandItsInfluenceonParsing.InNicolettaCalzolari(Confer-enceChair),KhalidChoukri,ThierryDeclerck,HrafnLoftsson,BenteMaegaard,JosephMariani,Asun-cionMoreno,JanOdijk,andSteliosPiperidis,editors,ProceedingsoftheNinthInternationalConferenceonLanguageResourcesandEvaluation(LREC’14),Reykjavik,Iceland,may.EuropeanLanguageRe-sourcesAssociation(ELRA).Yoeng-JinChuandTseng-HongLiu.1965.OntheShortestArborescenceofaDirectedGraph.ScientiaSinica,14(10):1396–1400.ShayB.CohenandNoahA.Smith.2007.Jointmorpho-logicalandsyntacticdisambiguation.InProceedingsofthe2007JointConferenceonEmpiricalMethodsinNaturalLanguageProcessingandComputationalNaturalLanguageLearning,pages208–217,Prague,CzechRepublic.AssociationforComputationalLin-guistics.KobyCrammer,OferDekel,ShaiShalev-Shwartz,andYoramSinger.2003.Onlinepassive-aggressivealgo-rithms.InProceedingsofthe16thAnnualConferenceonNeuralInformationProcessingSystems,volume7,pages1217–1224,Cambridge,Massachusetts,USA.MITPress.DipanjanDas,Andr´eF.T.Martins,andNoahA.Smith.2012.AnExactDualDecompositionAlgorithmforShallowSemanticParsingwithConstraints.In*SEM2012:TheFirstJointConferenceonLexicalandCom-putationalSemantics–Volume1:Proceedingsofthemainconferenceandthesharedtask,andVolume2:ProceedingsoftheSixthInternationalWorkshoponSemanticEvaluation(SemEval2012),pages209–217,Montr´eal,Canada,7-8June.AssociationforCompu-tationalLinguistics.JackEdmonds.1967.OptimumBranchings.Jour-nalofResearchoftheNationalBureauofStandards,71B(4):233–240.JasonEisner.1997.BilexicalGrammarsandaCubic-TimeProbabilisticParser.InProceedingsofthe5thInternationalWorkshoponParsingTechnologies(IWPT),pages54–65,MIT,Cambridge,MA,sep.G¨uls¸enEryi˘gitandKemalOflazer.2006.Statisticalde-pendencyparsingofTurkish.InProceedingsofthe11thConferenceoftheEuropeanChapteroftheAs-sociationforComputationalLinguistics,pages89–96,Trento,Italy.AssociationforComputationalLinguis-tics.G¨uls¸enEryi˘git,JoakimNivre,andKemalOflazer.2008.DependencyParsingofTurkish.ComputationalLin-guistics,34(3):357–389.G¨uls¸enEryi˘git,TugayIlbay,andOzanArkanCan.2011.MultiwordExpressionsinStatisticalDepen-dencyParsing.InProc.oftheSPMRLWorkshopofIWPT,pages45–55,Dublin,Ireland.
l
D
o
w
n
o
a
d
e
d
f
r
o
m
h
t
t
p
:
/
/
d
i
r
e
c
t
.
m
i
t
.
e
d
u
/
t
a
c
l
/
l
a
r
t
i
c
e
-
p
d
f
/
d
o
i
/
.
1
0
1
1
6
2
/
t
l
a
c
_
a
_
0
0
1
4
4
1
5
6
6
7
9
4
/
/
t
l
a
c
_
a
_
0
0
1
4
4
p
d
.
f
b
y
g
u
e
s
t
t
o
n
0
8
S
e
p
e
m
b
e
r
2
0
2
3
371
G¨uls¸enEryi˘git.2012.TheImpactofAutomaticMorpho-logicalAnalysis&DisambiguationonDependencyParsingofTurkish.InNicolettaCalzolari,KhalidChoukri,ThierryDeclerck,MehmetU˘gurDo˘gan,BenteMaegaard,JosephMariani,JanOdijk,andSte-liosPiperidis,editors,ProceedingsoftheEighthIn-ternationalConferenceonLanguageResourcesandEvaluation(LREC-2012),pages1960–1965,Istanbul,Turkey,May.EuropeanLanguageResourcesAssocia-tion(ELRA).ACLAnthologyIdentifier:L12-1056.YoavFreundandRobertE.Schapire.1999.Largemar-ginclassificationusingtheperceptronalgorithm.Ma-chineLearning,37(3):277–296.YoavGoldbergandMichaelElhadad.2009.HebrewDependencyParsing:InitialResults.InProceedingsofthe11thInternationalConferenceonParsingTech-nologies(IWPT’09),pages129–133,Paris,France,October.AssociationforComputationalLinguistics.YoavGoldbergandMichaelElhadad.2010a.AnEf-ficientAlgorithmforEasy-FirstNon-DirectionalDe-pendencyParsing.InHumanLanguageTechnologies:The2010AnnualConferenceoftheNorthAmericanChapteroftheAssociationforComputationalLinguis-tics,pages742–750,LosAngeles,California,June.AssociationforComputationalLinguistics.YoavGoldbergandMichaelElhadad.2010b.Easy-FirstDependencyParsingofModernHebrew.InProceed-ingsoftheNAACLHLT2010FirstWorkshoponSta-tisticalParsingofMorphologically-RichLanguages,pages103–107,LosAngeles,Californie,Etats-Unis,June.Associ-ationforComputationalLinguistics.YoavGoldbergandMichaelElhadad.2013.Wordseg-mentation,unknown-wordresolution,andmorpholog-icalagreementinahebrewparsingsystem.Computa-tionalLinguistics,39(1):121–160.YoavGoldbergandReutTsarfaty.2008.Asinglegener-ativemodelforjointmorphologicalsegmentationandsyntacticparsing.InProceedingsofthe46thAnnualMeetingoftheAssociationforComputationalLinguis-tics,pages371–379,Columbus,Ohio.AssociationforComputationalLinguistics.YoavGoldberg.2011.AutomaticSyntacticProcessingofModernHebrew.Ph.D.thesis,BenGurionUniversity,BeerSheva,Israel.SpenceGreenandChristopherD.Manning.2010.Bet-terArabicParsing:Baselines,Evaluations,andAnal-ysis.InProceedingsofthe23rdInternationalCon-ferenceonComputationalLinguistics(Coling2010),pages394–402,Beijing,Chine,August.Coling2010OrganizingCommittee.JunHatori,TakuyaMatsuzaki,YusukeMiyao,andJun’ichiTsujii.2011.IncrementalJointPOSTag-gingandDependencyParsinginChinese.InProceed-ingsof5thInternationalJointConferenceonNatu-ralLanguageProcessing,pages1216–1224,ChiangMai,Thaïlande,November.AsianFederationofNatu-ralLanguageProcessing.JunHatori,TakuyaMatsuzaki,YusukeMiyao,andJun’ichiTsujii.2012.IncrementalJointApproachtoWordSegmentation,POSTagging,andDependencyParsinginChinese.InProceedingsofthe50thAn-nualMeetingoftheAssociationforComputationalLinguistics(Volume1:LongPapers),pages1045–1053,JejuIsland,Korea,July.AssociationforCom-putationalLinguistics.TerryKoo,AlexanderM.Rush,MichaelCollins,TommiJaakkola,andDavidSontag.2010.DualDecomposi-tionforParsingwithNon-ProjectiveHeadAutomata.InProceedingsofthe2010ConferenceonEmpiri-calMethodsinNaturalLanguageProcessing,pages1288–1298,Cambridge,MA,October.AssociationforComputationalLinguistics.ZhongguoLiandGuodongZhou.2012.UnifiedDepen-dencyParsingofChineseMorphologicalandSyntacticStructures.InProceedingsofthe2012JointConfer-enceonEmpiricalMethodsinNaturalLanguagePro-cessingandComputationalNaturalLanguageLearn-ing,pages1445–1454,JejuIsland,Korea,July.Asso-ciationforComputationalLinguistics.ZhenghuaLi,MinZhang,WanxiangChe,TingLiu,Wen-liangChen,andHaizhouLi.2011.JointModelsforChinesePOSTaggingandDependencyParsing.InProceedingsofthe2011ConferenceonEmpiri-calMethodsinNaturalLanguageProcessing,pages1180–1191,Edinburgh,Écosse,ROYAUME-UNI,July.Associa-tionforComputationalLinguistics.JiMa,TongXiao,JingboZhu,andFeiliangRen.2012.Easy-FirstChinesePOSTaggingandDependencyParsing.InProceedingsofCOLING2012,pages1731–1746,Mumbai,India,December.TheCOLING2012OrganizingCommittee.AndreMartins,NoahSmith,andEricXing.2009.Con-ciseIntegerLinearProgrammingFormulationsforDe-pendencyParsing.InProceedingsoftheJointCon-ferenceofthe47thAnnualMeetingoftheACLandthe4thInternationalJointConferenceonNaturalLan-guageProcessingoftheAFNLP,pages342–350,Sun-tec,Singapore,August.AssociationforComputationalLinguistics.AndreMartins,NoahSmith,EricXing,PedroAguiar,andMarioFigueiredo.2010.TurboParsers:Depen-dencyParsingbyApproximateVariationalInference.InProceedingsofthe2010ConferenceonEmpiricalMethodsinNaturalLanguageProcessing,pages34–44,Cambridge,MA,October.AssociationforCompu-tationalLinguistics.AndreMartins,MarioFigueiredo,PedroAguiar,NoahSmith,andEricXing.2011a.AnAugmentedLa-
l
D
o
w
n
o
a
d
e
d
f
r
o
m
h
t
t
p
:
/
/
d
i
r
e
c
t
.
m
i
t
.
e
d
u
/
t
a
c
l
/
l
a
r
t
i
c
e
-
p
d
f
/
d
o
i
/
.
1
0
1
1
6
2
/
t
l
a
c
_
a
_
0
0
1
4
4
1
5
6
6
7
9
4
/
/
t
l
a
c
_
a
_
0
0
1
4
4
p
d
.
f
b
y
g
u
e
s
t
t
o
n
0
8
S
e
p
e
m
b
e
r
2
0
2
3
372
grangianApproachtoConstrainedMAPInference.InLiseGetoorandTobiasScheffer,editors,Proceed-ingsofthe28thInternationalConferenceonMachineLearning(ICML-11),ICML’11,pages169–176,NewYork,New York,Etats-Unis,June.ACM.AndreMartins,NoahSmith,MarioFigueiredo,andPe-droAguiar.2011b.DualDecompositionwithManyOverlappingComponents.InProceedingsofthe2011ConferenceonEmpiricalMethodsinNaturalLan-guageProcessing,pages238–249,Edinburgh,Scot-land,UK.,July.AssociationforComputationalLin-guistics.AndreMartins,MiguelAlmeida,andNoahA.Smith.2013.TurningontheTurbo:FastThird-OrderNon-ProjectiveTurboParsers.InProceedingsofthe51stAnnualMeetingoftheAssociationforComputationalLinguistics(Volume2:ShortPapers),pages617–622,Sofia,Bulgaria,August.AssociationforComputa-tionalLinguistics.Andr´eF.T.Martins,M´arioA.T.Figueiredo,PedroM.Q.Aguiar,NoahA.Smith,andEricP.Xing.2015.AD3:AlternatingDirectionsDualDecompositionforMAPInferenceinGraphicalModels.JournalofMachineLearningResearch,16:495–545.RyanMcDonaldandFernandoPereira.2006.On-linelearningofapproximatedependencyparsingal-gorithms.InProceedingsofthe11thConferenceoftheEuropeanChapteroftheAssociationforCompu-tationalLinguistics,pages81–88,Trento,Italy.Asso-ciationforComputationalLinguistics.RyanMcDonald,FernandoPereira,KirilRibarov,andJanHajic.2005.Non-ProjectiveDependencyParsingusingSpanningTreeAlgorithms.InProceedingsofHumanLanguageTechnologyConferenceandConfer-enceonEmpiricalMethodsinNaturalLanguagePro-cessing,pages523–530,Vancouver,BritishColumbia,Canada,October.AssociationforComputationalLin-guistics.SaulB.NeedlemanandChristianD.Wunsch.1970.Ageneralmethodapplicabletothesearchforsimilaritiesintheaminoacidsequenceoftwoproteins.Journalofmolecularbiology,48(3):443–453.KemalOflazer,BilgeSay,DilekZeynepHakkani-T¨ur,andG¨okhanT¨ur.2003.BuildingaTurkishTree-bank.InAnneAbeille,editor,BuildingandExploitingSyntactically-annotatedCorpora.KluwerAcademicPublishers,Dordrecht.KemalOflazer.1994.Two-levelDescriptionofTurk-ishMorphology.LiteraryandLinguisticComputing,9(2):137–148.AlexanderM.Rush,DavidSontag,MichaelCollins,andTommiJaakkola.2010.OnDualDecompositionandLinearProgrammingRelaxationsforNaturalLan-guageProcessing.InProceedingsofthe2010Confer-enceonEmpiricalMethodsinNaturalLanguagePro-cessing,pages1–11,Cambridge,MA,October.Asso-ciationforComputationalLinguistics.Has¸imSak,TungaG¨ung¨or,andMuratSarac¸lar.2008.TurkishLanguageResources:MorphologicalParser,MorphologicalDisambiguatorandWebCorpus.InProc.ofGoTAL2008,pages417–427.Djam´eSeddah,ReutTsarfaty,SandraK¨ubler,MarieCan-dito,JinhoD.Choi,Rich´ardFarkas,JenniferFos-ter,IakesGoenaga,KoldoGojenolaGalletebeitia,YoavGoldberg,SpenceGreen,NizarHabash,MarcoKuhlmann,WolfgangMaier,JoakimNivre,AdamPrzepi´orkowski,RyanRoth,WolfgangSeeker,Yan-nickVersley,VeronikaVincze,MarcinWoli´nski,AlinaWr´oblewska,andEricVillemontedelaClergerie.2013.OverviewoftheSPMRL2013SharedTask:ACross-FrameworkEvaluationofParsingMorphologi-callyRichLanguages.InProceedingsoftheFourthWorkshoponStatisticalParsingofMorphologically-RichLanguages,pages146–182,Seattle,Washington,Etats-Unis,October.AssociationforComputationalLin-guistics.Djam´eSeddah,SandraK¨ubler,andReutTsarfaty.2014.IntroducingtheSPMRL2014SharedTaskonParsingMorphologically-richLanguages.InProceedingsoftheFirstJointWorkshoponStatisticalParsingofMor-phologicallyRichLanguagesandSyntacticAnalysisofNon-CanonicalLanguages,pages103–109,Dublin,Ireland,August.DublinCityUniversity.KhalilSima’an,AlonItai,YoadWinter,AlonAltman,andNoaNativ.2001.Buildingatree-bankofmodernHebrewtext.TraitementAutomatiquedesLangues,42(2):247–380.BenTaskar,VassilChatalbashev,DaphneKoller,andCarlosGuestrin.2005.LearningStructuredPredic-tionModels:ALargeMarginApproach.InProceed-ingsofthe22thAnnualInternationalConferenceonMachineLearning,pages896–903,Bonn,Germany.ACM.StephenTratz.2013.ACross-TaskFlexibleTransi-tionModelforArabicTokenization,AffixDetection,AffixLabeling,POSTagging,andDependencyPars-ing.InProceedingsoftheFourthWorkshoponSta-tisticalParsingofMorphologically-RichLanguages,pages34–45,Seattle,Washington,Etats-Unis,October.As-sociationforComputationalLinguistics.ReutTsarfaty,Djam´eSeddah,YoavGoldberg,SandraKuebler,YannickVersley,MarieCandito,JenniferFoster,InesRehbein,andLamiaTounsi.2010.Sta-tisticalParsingofMorphologicallyRichLanguages(SPMRL)What,HowandWhither.InProceedingsoftheNAACLHLT2010FirstWorkshoponStatisticalParsingofMorphologically-RichLanguages,pages1–
l
D
o
w
n
o
a
d
e
d
f
r
o
m
h
t
t
p
:
/
/
d
i
r
e
c
t
.
m
i
t
.
e
d
u
/
t
a
c
l
/
l
a
r
t
i
c
e
-
p
d
f
/
d
o
i
/
.
1
0
1
1
6
2
/
t
l
a
c
_
a
_
0
0
1
4
4
1
5
6
6
7
9
4
/
/
t
l
a
c
_
a
_
0
0
1
4
4
p
d
.
f
b
y
g
u
e
s
t
t
o
n
0
8
S
e
p
e
m
b
e
r
2
0
2
3
373
12,LosAngeles,Californie,Etats-Unis,June.AssociationforComputationalLinguistics.ReutTsarfaty,JoakimNivre,andEvelinaAndersson.2012.JointEvaluationofMorphologicalSegmen-tationandSyntacticParsing.InProceedingsofthe50thAnnualMeetingoftheAssociationforCompu-tationalLinguistics(Volume2:ShortPapers),pages6–10,JejuIsland,Korea,July.AssociationforCom-putationalLinguistics.ReutTsarfaty.2006.IntegratedMorphologicalandSyn-tacticDisambiguationforModernHebrew.InPro-ceedingsoftheCOLING/ACL2006StudentResearchWorkshop,pages49–54,Sydney,Australia,July.As-sociationforComputationalLinguistics.MeishanZhang,YueZhang,WanxiangChe,andTingLiu.2014.Character-LevelChineseDependencyParsing.InProceedingsofthe52ndAnnualMeetingoftheAssociationforComputationalLinguistics(Vol-ume1:LongPapers),pages1326–1336,Baltimore,Maryland,June.AssociationforComputationalLin-guistics.YuanZhang,ChengtaoLi,ReginaBarzilay,andKareemDarwish.2015.RandomizedGreedyInferenceforJointSegmentation,POSTaggingandDependencyParsing.InProceedingsofthe2015ConferenceoftheNorthAmericanChapteroftheAssociationforComputationalLinguistics:HumanLanguageTech-nologies,pages42–52,Denver,Colorado,May–June.AssociationforComputationalLinguistics.
l
D
o
w
n
o
a
d
e
d
f
r
o
m
h
t
t
p
:
/
/
d
i
r
e
c
t
.
m
i
t
.
e
d
u
/
t
a
c
l
/
l
a
r
t
i
c
e
-
p
d
f
/
d
o
i
/
.
1
0
1
1
6
2
/
t
l
a
c
_
a
_
0
0
1
4
4
1
5
6
6
7
9
4
/
/
t
l
a
c
_
a
_
0
0
1
4
4
p
d
.
f
b
y
g
u
e
s
t
t
o
n
0
8
S
e
p
e
m
b
e
r
2
0
2
3
374
Télécharger le PDF