DATAANALYSISANDSELECTIONFORSTATISTICALMACHINETRANSLATIONBySaulehEetemadiADISSERTATIONSubmittedtoMichiganStateUniversityinpartialoftherequirementsforthedegreeofElectricalEngineeringŒDoctorofPhilosophy2016ABSTRACTDATAANALYSISANDSELECTIONFORSTATISTICALMACHINETRANSLATIONBySaulehEetemadiStatisticalMachineTranslationhasreceivedattentionfromtheacademiccommu-nityoverthepastdecadewhichhasledtoimprovementsinmachinetranslationquality.Asaresultitiswidelyadoptedintheindustry(Google,Microsoft,Twitter,Facebook,...etc.)aswellasthegovernment(http://nist.gov).Thebiggestfactorinthisimprovementhasbeentheavailabilityofeverincreasingsourcesoftrainingdataasdigitalmultilingualcommunicationandinformationdisseminationbecomeubiquitous.Relativelylittleresearchhasbeendoneontrainingdataanalysisandselection,despitetrainingdatabeingthemaincontributorofmachinetranslationquality.Inthiswork,weexaminefundamentalpropertiesoftranslatedandauthoredtext.Weintroduceanewlinguisticallymotivatedfeature(PartofSpeechTagMinimalTranslationUnits)thatoutperformspriorworkinsentenceleveltranslationdirectiondetection.Next,wedevelopacross-domaindatamatrixthatenablescomparisonbetweendifferentfeaturesinthetranslationdirectiondetectiontask.Weextendourpreviouslyintroducedfeaturefortranslationdirectiondetectiontousestatisticallytrainedbrownclustersinsteadofpartofspeechtags.Thisnewfeatureoutperformsallpriorworkinallcross-domaindatamatrixcombinations.Dataselectioninmachinetranslationisperformedindifferentscenarioswithdifferentobjec-tivesincluding:reducingtrainingresourceconsumption,domainadaptation,improvingqualityorreducingdeploymentsize.Wedevelopanef(computationalcomplexityandmemorycon-sumptionislinearintrainingdatasize)frameworkfortrainingdataselectionandcompressioncalledVocabularySaturationFilter(VSF).InourexperimentsweshowthemachinetranslationsystemtrainedondataselectedusingVSFiscomparabletopriordataselectionmethodswithquadraticcomputationalcomplexity.However,VSFissensitivetodataorder.Thereforeweexper-imentwithdifferentorderingsofthedataandcomparetheresults.Finally,wedevelopahighlyscalableandxibledataselectionframeworkwherearbitrarysentencelevelfeaturescanbeusedfordataselection.Inaddition,avariablethresholdfunctioncanbeusedtoincorporateanyscoringfunctionthatisconstantthroughouttheselectionprocess.Afterintroducingthisframework,inspiredbythefeaturesweintroducedfordetectingtranslationdirection,weusejointmodelsofsourceandtargetusingMinimalTranslationUnits(MTU)inadditiontosourcesidecontextusingbrownclusterstocomparevariousfeaturesandthresholdfunctionswithinthisframework.Werunend-to-endexperimentsusingdataselectedbyvariousmethodsandcomparethestatisticaltranslationmodelsusingvarioustestsetsandphrasetablecomparisonmetrics.CopyrightbySAULEHEETEMADI2016Toanyonewhowillreadanduseit!vACKNOWLEDGEMENTSIstartedmyPh.D.in2006shortlyafterIjoinedMicrosoftResearchasasoftwareengineer.Indeed,myjobatMicrosoftResearchwastheonlyaspectofmylifethatdidnotchangeduringtheseyears.Wewererenting,thenweboughtacondo.Iwasoverweight,IstartedthenewsportofBrazilianJujitsu,Ilostweightandeventuallyearnedablackbelt.Iwenttopilgrimage.Then,Iwentagain.Ibecameafather.Wetravelledtomanydifferentcountriesmanytimes.Weleftthecondo,becamealandlordandstartedrentingagain.Wehadourseconddaughter.Werenovatedourhouse.Mywifewentthroughlifethreateningsurgeriesandrecovered.Ilostmygrandfatherandgrandmotherandsoon....WhenIstarted,Ineverthoughtitwouldtakeme10yearstodefendmydissertationandgraduate.WhileIalwaysknew,I'mnotgoingtogiveup,IneverknewhowmuchhelpIneeded.Firstandforemost,mydeepestgratitudeisfortheOnewhopresentedmewiththischallengealongwithmanyotherchallengesinlife,soImaybecomebetter.Iwouldliketothankmyadviser,Dr.Radha.WhilehewarnedmeofthedifofdoingaPh.D.andworkingafulltimejobatthesametime,hisintricatecombinationofpatience,supportandchallengewasinstrumentalinhelpingmetoovercomethisdif.Ifitwasn'tfortheincrediblehelpandsupportofmyco-advisorDr.KristinaToutanova,IwouldnothavebeenabletocompletemyPh.D.Iwanttoexpressmygratitudetoherformentoringmeandprovidingmewithsupportiveandcriticalfeedback.IwouldalsoliketothankDr.RongJinwhoservedonmycommitteebeforeleavingMSU.Ifitwasn'tforhissuggestiontohaveaco-advisorthatcanmentormeintheareaofStatisticalMachineTranslation,IwouldnothavehadKristinaasmyco-advisor.IalsowanttothankDr.EsfahanianwhoagreedtoreplaceDr.Jininmycommitteeonlyfewmonthsbeforemydefense.I'mthankfultomycommitteemembersDr.DellerandDr.Aviyentefortheirsupportandfeedbackaswell.I'mextremelythankfultomymangersandcolleaguesattheMachineTranslationGroupinMicrosoftResearchwhowerealwayssupportiveandencouragingtowardsthepursuitofmyPh.D.viMymanagers,Steve,Andreas,Federico,Mei-Yuh,ArulandVishalwerealwaysxibleandsup-portiveofmyPh.D.andforthat,I'mverythankful.WhileIlackedtheofhavinglabmatesformanyyears,JonClarkandQinGaothisgapastheyjoinedourgroupfewyearsagowhiletheywerePh.D.studentsaswell.Westartedhavingweeklymeetingswhichwasincrediblyhelpfulinpushingustowardsgraduationandforthis,I'mverythankful.IhadmanyfruitfuldiscussionswithmycolleagueandmentorDr.WilliamLewiswhoalsosharedmypassionfortheroleofdatainmachinetranslation.Hisoptimism,dedicationandsupportwasapositiveforcethroughoutmyPhD.SincethepursuitofPhDwastheotherbigthinginmylifeaftermyjob,thesubjecthadcomeuponceormorewithallcolleaguesI'vehadthroughouttheyears.Icannotnamethemallhere,butwithoutexception,theywereallencouragingandplayedapositiveroleinthisendeavourandforthatI'mverythankful.Whilebeingsupportedatworkandschoolbyincrediblepeople,IstillneededtimetoworkonmyPh.D.aftermyresponsibilitiesatwork.Mywifeandsoulmate,HodahasbeenincrediblygraciousandthroughouttheseyearswhileshestartedandhermastersdegreeinArchitecture,startedherPh.D.inConstructionManagement,hadtwokidsanddefendedherPh.D.lastyear.Thanks!Attheageof36,Ihavenowofbeeninschoolforover30years.FromthedayIwenttokindergartentillthisveryday,mymomalwaysencouragedmeandbelievedinme.Shegotmeintogoodschools,shestayeduplatetohelpmewithmyhomework,getgoodgrades,stayingoodschools,getintouniversityandsoon.ThewordscannotbegintodescribehowmuchsheformyeducationandsuccessandforthisI'mforeverthankful.Mydadalwayswasandcontinuestobemyrolemodel.Heblessedmewithhiswisdom,greatadvice,directionandsupportthroughouttheyearsandIcannotthankhimenoughforthis.Ihavebeenawayfrommyparentsnowforoveradecadeinpursuitofhighereducationandcareer.Althoughthispursuithastakenmuchlongerthananticipated,theyremainedencouragingandsupportiveandforthisI'mforeverindebttothem.IalwaysfromdiscussionsaboutcareerandhighereducationwithmyyoungerbrotherviiAmeen,throughouthisyearsatMicrosoftaswellasthetwoyearssincehestartedhisPh.D.atUCDavis.MyparentsinlawhavealsoblesseduswithvisitingushereintheStatesandhelpinguswithourtwodaughtersinadditiontobeinggreathostsformywifeanddaughtersduringthesummermonthswhileIwasnotwiththem.I'mincrediblythankfulandindebttothem.Manyfriendsandfamilieshavesupportedmewiththeirthoughtsandprayersthroughouttheyears.WhileIcannotnameallofthemhere,Idothankthemfortheirhelpandsupport.Finally,mydaughtersAulaandHannahhaveprovidedmewithincrediblejoy,challengeandheadacheforthebetterhalfofmyPh.D.WhileIhavespentmanynights,weekendsandsummermonthsawayfromthemworkingonmydissertation,Iwasalwayswelcomedandacceptedbythem.Ifitwasn'tforthem,althoughthisdissertationmighthavebeencompletedearlier,butoverallIamabetterpersonbecauseofthem.ThankYou!viiiTABLEOFCONTENTSLISTOFTABLES.......................................xiiLISTOFFIGURES.......................................xiiiCHAPTER1INTRODUCTION...............................1CHAPTER2BACKGROUND................................52.1EstimatingLanguageModelProbability.......................72.2EstimatingTranslationModelProbability......................92.2.1WordAlignment...............................92.2.2PhraseTable..................................102.3MachineTranslationEvaluation...........................10CHAPTER3LITERATUREREVIEW...........................133.1Introduction......................................133.2ApplicationScenarios.................................163.3NotationandTerminology..............................183.4ProblemFormulation.................................203.5SentenceLevelScoringFunctions..........................243.5.1ContextDependentFunctions........................243.5.1.1N-GramCoverageFunctions....................243.5.1.2Phrase-TableBasedFunctions...................273.5.1.3LanguageModelBasedFunctions.................293.5.1.4DecoderBasedFunctions.....................313.5.2ContextIndependentFunctions........................333.5.2.1LanguageModelBasedFunctions.................333.5.2.2AlignmentModelBasedFunctions................353.5.2.3OtherScoringFunctions......................383.6FeatureCombinationandParameterTuning.....................403.7SelectionAlgorithms.................................413.7.1ThresholdBasedFiltering..........................413.7.2GreedySearch................................423.7.3SubmodularOptimization..........................423.8ActiveLearning....................................443.9Batch-ModeLearning.................................453.10EvaluationMethods..................................473.11ComparativeSummaryofCitedWork........................483.12RelatedResearchAreas................................513.13Summary.......................................52CHAPTER4TRANSLATIONDIRECTIONDETECTION.................54ix4.1Introduction......................................554.2RelatedWork.....................................584.3BilingualFeaturesforTranslationDirection..............594.3.1POSTagMTUs................................594.3.2Distortion...................................604.4SingleDomainExperiments.............................604.4.1Data......................................604.4.2PreprocessingandFeatureExtraction....................614.4.3Results....................................624.4.4Analysis....................................624.5Cross-DomainExperiments..............................634.5.1DataMatrix..................................644.5.2PreprocessingandFeatureExtraction....................654.5.3Online.............................664.5.4EvaluationMethod..............................674.5.5Results....................................684.6ConclusionandFutureWork.............................71CHAPTER5EFFECTIVEANDEFFICIENTDATASELECTION............735.1VocabularySaturationFilter.............................735.2ComparisontonearOptimumSolution........................755.2.1ExperimentalSetup..............................755.2.2Results....................................765.3DataOrder.......................................785.4ExperimentSetup...................................785.5ExperimentResults..................................805.6EffectsofVSFonn-gramdistribution........................825.7Conclusion......................................84CHAPTER6THESATURATIONFILTERFRAMEWORK................856.1FeatureSpace.....................................866.1.1SourceVocabulary..............................876.1.2SourceandTargetVocabulary........................876.1.3BigramSourceVocabulary..........................876.1.4SourceVocabularywithContext.......................886.1.5MinimalTranslationUnit...........................886.1.6MinimalTranslationUnitwithTargetBrownCluster............886.2ThresholdFunction..................................896.3IncrementalAlgorithm................................906.4ExperimentSetup...................................916.5ExperimentResults..................................926.5.1FeatureComparison..............................946.5.2ThresholdFunctionComparison.......................976.6Conclusion......................................108xCHAPTER7CONCLUSION................................110BIBLIOGRAPHY........................................111xiLISTOFTABLESTable3.1ExplorationversusExploitation..........................27Table3.2RelatedWork....................................50Table4.1POSMTUfeatureswithhighestweight.FE#indicatesthenumberoftimesthisfeatureappearedwhentranslatingfromFrenchtoEnglish...........62Table4.2featuresandtheirlabels........................63Table4.3Cross-DomainDataSets..............................64Table5.1English-sideSentenceCounts(inmillions)fordifferentthresholdsforVSF,VSFafterorderingthedatabasedonnormalizedcombinedalignmentscoreandrandombaselines................................79Table5.2English-sideWordCountsfordifferentthresholdsforVSF,VSFafterorderingthedatabasedonnormalizedcombinedalignmentscoreandrandombaselines..80Table5.3Wordalignmenttimes(hh:mm)fordifferentthresholdsforVSF,VSFaftermodelscoreordering,andarandombaseline...................81Table5.4BLEUScoreresultsforVSF,S+VSF(SortedVSF),andRandomBaselineatdifferentthresholdst.................................81Table5.5OOVratesforVSF,S+VSF(SortedVSF),andRandomBaselineatdifferentthresholdst......................................82Table6.1Dataselectionfeaturesandtheirlabels.......................92Table6.2IncrementalFeatureSaturationFilteralgorithmsizesforeachfeature.......93Table6.3IncrementalSaturationFilteralgorithmsizesfordifferentthresholdfunctions...93xiiLISTOFFIGURESFigure2.1NoisyChannelModelforStatisticalMachineTranslation[50]..........6Figure2.2Probabilityoffipassedtheexamflandfifailedtheexamflwordsequencesac-cordingtoLanguageModelstrainedonpublishedbookseveryyearsince1900withasmoothingfactorofthree([42])....................8Figure3.1TaxonomyofdataselectioninMachineTranslation...............15Figure3.2DataSelection:Thisdiagramdemonstratestheroleofeachdatasetinthedataselectionprocess................................20Figure4.1EuroParlWordCloudDataVisualization(TranslatedvsOriginal)........56Figure4.2EffectsofChunkSizeonTranslationeseDetectionAccuracy..........57Figure4.3Sentenceleveltranslationdirectiondetectionprecisionusingdifferentfea-tureswithn-gramlengthsof1through5......................61Figure4.4POSTaggedandBrownClusterAlignedSentencePairs.............65Figure4.5ComparingareaundertheROCcurveforthetranslationdirectiondetectiontaskwhentrainingandtestingondifferentcorporausingeachoftheeightfeaturesets.SeeTable4.2forexperimentlabeldescription............67Figure4.6Translationdetectionperformancematrixfortrainingandtestingonthreedifferentcorpora.Eachrowcorrespondstoresultsoftrainingonacorpuswhiletestresultsarelaidoutinacolumnofthe33matrix.UnlikeFigure4.5wherewereportAUCvaluesforalln-grams,inthisdiagramweonlyreportthehighestAUCvalueforeachfeature.Thenumbernexttoeachdatapointindicatesthen-gramlengththatachievesthehighestperformanceforthatfeature.SeeTable4.2forexperimentlabeldescription..........68Figure4.7Translationdetectionperformancematrixfortrainingandtestingonthreedifferentcorpora-Weranexperimentsforn-gramsofuptolengthveforeachfeature(SeeTable4.2forfeaturelabeldescriptions).UnlikeFigure4.5wherewereportAUCvaluesforalln-gramlengths,inthisgraphweonlypresentthehighestAUCnumberforeachfeature.Eachmarkertypeindi-catesatrainingandtestsetcombination.Theformatofexperimentlabelsinthelegendis[TrainingSet]-[TestSet]andEU:EuroParl,H:Hansard,HC:HansardCommittees.Forexample,EU-HCmeanstrainingonEuroParlcor-pusandtestingonHansardCommitteescorpus..................70xiiiFigure4.8TranslationdirectiondetectionAUCperformancerankforeachtrainingandtestsetcombination.ForcorpuscombinationabbreviationsseedescriptionofFigure4.7.ForfeaturelabeldescriptionsseeTable4.2.............72Figure5.1UnigramEckvs.UnigramVSF..........................76Figure5.2BigramEckvs.UnigramVSF..........................77Figure5.3ComparativeBLEUscoresfortwoVSFimplementations,againstarandomlysampledbaseline..................................82Figure5.4ComparativeOOVratesfortwoVSFimplementations,againstarandomlysampledbaseline..................................83Figure5.5log2-scaleUnigramFrequencyscatterplotbeforeVSFversusafterVSF....84Figure6.1BLEUscorecomparisonofdifferentdataselectionfeatureswithconstantthresholdwiththeWMT2009testset.......................95Figure6.2BLEUscorecomparisonofdifferentdataselectionfeatureswithconstantthresholdwiththeWMT2013testset.......................95Figure6.3Comparisonoftotalnumberofuniquesourcephrasesextractedforeachdataselectionfeature...................................96Figure6.4Comparisonoftotalnumberofuniquephrasepairsextractedforeachdataselectionfeature...................................96Figure6.5Averagenumberoftargetphrasespersourcephraseforeachdataselectionfeature........................................96Figure6.6Samplingbiasinrandomdataselection.X-Axisislogarithmoffrequencyforwordsinallthedata.Y-Axisislogarithmoffrequencyforwordsinselecteddata.Thegraphisgeneratedforsubsetsofthedatainsizes1M,4M,8Mand16M(JSD:JensenŒShannonDivergence).....................98Figure6.7Samplingbiasinuniformthresholdfunction.X-Axisislogarithmoffre-quencyforwordsinallthedata.Y-Axisislogarithmoffrequencyforwordsinselecteddata.Thegraphisgeneratedforsubsetsofthedatainsizes1M,4M,8Mand16M(JSD:JensenŒShannonDivergence)..............99Figure6.8Samplingbiasindataselectionusinglogarithmoffrequencythresholdfunc-tion.X-Axisislogarithmoffrequencyforwordsinallthedata.Y-Axisislogarithmoffrequencyforwordsinselecteddata.Thegraphisgeneratedforsubsetsofthedatainsizes1M,4M,8Mand15M(JSD:JensenŒShannonDivergence).....................................100xivFigure6.9Samplingbiasindataselectionusingentropythresholdfunction.X-Axisislogarithmoffrequencyforwordsinallthedata.Y-Axisislogarithmoffrequencyforwordsinselecteddata.Thegraphisgeneratedforsubsetsofthedatainsizes1M,4M,9Mand17M(JSD:JensenŒShannonDivergence)...101Figure6.10BLEUscorecomparisonofdifferentdataselectionthresholdfunctionusingsourcevocabularyfeaturewiththeWMT2009testset...............102Figure6.11BLEUscorecomparisonofdifferentdataselectionthresholdfunctionusingsourcevocabularyfeaturewiththeSpeechEX1conversationaltestset([67])...102Figure6.12BLEUscorecomparisonofdifferentdataselectionthresholdfunctionusingsourcevocabularyfeaturewiththeWMT2009testset...............103Figure6.13BLEUscorecomparisonofdifferentdataselectionthresholdfunctionusingsourcevocabularyfeaturewiththeSpeechEX1conversationaltestset([67])...104Figure6.14Thresholdfunctionscomparisonforaveragenumberoftargetphrasespersourcephrasesextractedforsourcevocabularyfeature..............104Figure6.15Thresholdfunctionscomparisonforaveragenumberoftargetphrasespersourcephrasesextractedforbigramsourcevocabularyfeature..........105Figure6.16Thresholdfunctionscomparisonfortotalnumberofphrasepairsextractedforsourcevocabularyfeature............................105Figure6.17Thresholdfunctionscomparisonfortotalnumberofphrasepairsextractedforbigramsourcevocabularyfeature........................105Figure6.18Thresholdfunctionscomparisonfornumberofuniquesourcephrasesex-tractedforsourcevocabularyfeature........................106Figure6.19Thresholdfunctionscomparisonfornumberofuniquesourcephrasesex-tractedforbigramsourcevocabularyfeature....................106Figure6.20BLEUscorecomparisonfortheselectionoflowerdatasizesusinglogarithmoffrequencythresholdfunctionandMTUfeatureatdifferentselectionsizes...107Figure6.21BLEUscorecomparisonfortheselectionoflowerdatasizesusinglogarithmoffrequencythresholdfunctionandMTUwithtargetBrownclusterfeatureatdifferentselectionsizes.............................108xvCHAPTER1INTRODUCTIONWiththedigitalagethereisevermorenaturallanguagepreservedindigitalformat.Theavailabilityofnaturallanguageincreaseswitheverynewspiece,newarticle,blogpost,recordedconversationandvirtuallyeverythingspokenorwrittenbybillionsofpeopleontheplanet.Itisonlynaturaltodevelopalgorithmsandtechniquesenablinghumanstoconsume,absorbandleveragethiseverexpandingsourceofdata.Forexample,summarisationenablespeopletoabsorbmoreinformationwithlesseffort.Sentimentdetectionbuildsontopofthatandprovidesaggregateinformationon,forexample,productreviewswrittenbyconsumers.MachineTranslationprovidescosteffectiveandseamlessaccesstoinformationthatwouldhavebeenotherwiseinaccessible.Researchersdevelopincreasinglymorecomplexalgorithmstoperformthesetaskswithhigherprecision.Manyofthesealgorithmsarenotinherentlydecomposableintopiecesthatcanefruninparallel.Also,notallresearchershaveaccesstolargescaleclusterstodeveloporrunsuchdecomposablealgorithms.Anexampleofthisisdeepneuralnetworks.Althoughtheoriginalideawasdevelopedinthe70s,ithasonlyrecentlybeenusedeffectivelyandsuccessfullyinarangeofnaturallanguageprocessingproblemssuchasspeechrecognitionandmachinetranslation.Thisimpliesitispossibleforarangeofcurrentlyavailablealgorithmsthatarenotscalable,toonlybeusedinseveralyearsordecadeswithimprovedcomputationpower.Thishasmotivatedanewapproachtothisgab.Theapproachistocompacttrainingdatatoasmallenoughsizesuchthatthealgorithmscantrainonitinareasonableamountoftime.Anexampleofsuchworkintheofmachinelearningiscore-sets([36]).ThefocusofthisthesisisthetrainingdatausedinMachineTranslation.MachineTranslationhasbeenaroundforseveraldecades.ThequalityofMachineTranslationhoweverhasimprovedoverthepastseveralyearswiththedevelopmentofstatisticalmethodsthatcanlearnfromexistingtranslationdatainsteadofhavinglinguistsdeveloptranslationrulesforeachlanguage1pair.MachineTranslationhasreceivedasecondboostwiththedevelopmentofdatacollectionmethodsthathaveharvestedthedigitalresourcessuchasthewebtocomposemoreandmoretrainingdata.WhiletheconsensusisthatmoredataimprovesmachinetranslationtheefforttocollectmoredatahasdiminishedfordominantlanguagessuchasEnglish,SpanishandFrenchsincethecomputationcapacitytoeftrainamachinetranslationsystemonsuchlargedatasetshasbeensaturated.Takethelanguagemodelingtask.Thesizeoftheindexedwebisestimatedtobe50billionwebpages[105].Assuminganaveragewordsperpageof429.2([78]),thisisapproximately21.4terawords.Thesizeofthedeepwebisestimatedtobe500timestheindexedweb([14]).Thatbringsthetotalestimatednaturallanguageavailableonthewebcloseto10.7petawords.ThelargestlanguagemodeleverreportedtobebuiltisbyGoogleover1terawords[38].Thatis5%oftheindexedweband0.09%oftheentireweb.Thesecondtypeoftrainingdataisparalleldata.French-Englishhasthelargestpubliclyavailableparallelcorpuswithcloseto40millionsentencepairsor2.8billiontotalwords[21].Whilethereisalotmoreparalleldataavailablereportedbytheindustry([66]),thereislittleefforttocollectsuchdatasincethetrainingalgorithmsarealreadycomputationallysaturatedwithexistinghardware.Inthisthesis,wefocusonafundamentalaspectofmachinetranslationtrainingdata.Parallelnaturallanguagedataisuniquetomachinetranslation.Itisalsothemainandkeytypeoftrainingdataformachinetranslation.Insomerecentworkinmachinetranslationusingdeepneuralnetworksitistheonlytypeoftrainingdata([94]).Asfarasweareaware,paralleldatahasonlybeenusedforthepurposeofdirectlyorindirectlytrainingamachinetranslation.TheonlyothertaskthatcanalsobeperformedusingparalleldataisTranslationesedetection.InaparallelcorpussettingwecallthisTranslationDirectionDetectionorTDDforshort.Theofthistaskisthatitcanbeevaluatedobjectively,accuratelyandmeaningfully.Incomparison,theevaluationofamachinetranslationalgorithmoverparalleldataisofallcomputationallycomplex.Second,theevaluationislessmeaningfulasasentencecanbetranslatedcorrectlyinmanydifferentwaysandforthatreason,,theevaluationisnotaccurateasacompletelyvalidtranslationcanbeevaluatedasincorrectduetoreferencemismatch.TDDdoesnothave2anyoftheseissues.Thusitisasuitabletaskforexplorationandaccuratecomparisonofmanydifferentfeaturefunctions.InChapter4wedevelopandcomparetheeffectivenessofdifferentfeaturesinselectingsentencepairsofadirection.AlthoughthesefeaturesaredevelopedandevaluatedinthecontextofTDD,weshowinChapter5thatsomeofthesefeaturesarealsomosteffectiveindataselection.ThedataselectionliteratureinmachinetranslationisreviewedinChapter3.Wefocusonthequalityimprovementandtrainingresourcelimitationscenariofromtheliteratureusingdatacompactingtechniquestotrainonthemostinformativesubsetofthedatawhenitisnotpracticaltotrainontheentiredataset.InChapter5,weintroducealinearbutsuboptimalsearchalgorithmforoptimizingacommonlyusedsurrogateobjectivefunction(n-gramcoverage)fordataselection.Weshowthequalityofthemachinetranslationoutputproducedbymodelstrainedonthedatasetchosenbyoursuboptimalalgorithmisnotstatisticallydifferentfromtheoutputproducedbymodelstrainedontheoptimalsubset.Inotherwords,weareabletoproducesamequalitymachinetranslationoutputusingalinearandsuboptimalalgorithm.Finally,inChapter6weintroduceaxibleframeworkfordataselectionthatisabletouseanysentencepairlevelfeaturealongwithanarbitrarythresholdfunction.WeproposeusingmoresophisticatedfeaturesfromChapter4withthesamelinearsearchalgorithm.Thesefeaturesusewordalignmentinformationcombinedwithsemanticfeaturesfrombrownclusterstocapturejointlexicalandsemanticinformation.Thesefeaturesareabletocaptureinformationthathasnotbeendirectlyusedinpriordataselectionmethods.Inaddition,wefurtherinvestigatetheeffectsofdataselectiononvocabularydistributionandimprovetheJensenŒShannondivergencebetweenselecteddataandselectionpoolusinganentropybasedvariablethresholdfunction.Improvinguponthepreviouslyintroducedefsearchalgorithmweareabletopartitionverylargedatasets(mostpriorworkdonotscaletosuchlargedatasets)intoanorderedandtunablenumberofpartitions1andoutperformallpriorworkthatcanscaletosuchlargedatasets.Weperform1Partitionsareintheorderofmoredesirabledata.Thedesirednumbersentencepairscanbe3endtoendstatisticalmachinetranslationexperimentscomparingdifferentfeaturesetsandvariablethresholdfunctions.WeusetranslationmodelstatisticsinadditiontoBLEUscoretocomparetheeffectivenessofvariousselectiontechniques.selectedbyselectingpartitionsinorder.4CHAPTER2BACKGROUNDTranslationbetweendifferentlanguagesisnearlyasoldasspokenandwrittenlanguageitself.Duetothelaborioustaskoftranslation,theinterestinusingcomputersfortranslationcameaboutassoonascomputersbecameavailable.WarrenWeaver,co-authorofthelandmarkworkoncommunication,TheMathematicalTheoryofCommunication,withClaudShannonofBellLab-oratories,iswidelyrecognizedasthepioneerofMachineTranslation.OnMarch4th,1947,inhislettertoProfessorNorbertWienerofMassachusettsInstituteofTechnologyhewrote([103]):WhenIlookatanarticleinRussian,IsayfiThisisreallywritteninEnglish,butithasbeencodedinsomestrangesymbols.Iwillnowproceedtodecode.flHaveyoueverthoughtaboutthis?Asalinguistandexpertoncomputers,doyouthinkitisworththinkingabout?Also,inhis1949fiTranslationflmemoranduminreferencetoShannon'sworkonTheoryofCommunication,hewrites([103]):ProbablyonlyShannonhimself,atthisstage,canbeagoodjudgeofthepossi-bilitiesinthisdirection;butaswasexpressedinW.W.'soriginallettertoWiener,itisverytemptingtosaythatabookwritteninChineseissimplyabookwritteninEn-glishwhichwascodedintothefiChinesecode.flIfwehaveusefulmethodsforsolvingalmostanycryptographicproblem,mayitnotbethatwithproperinterpretationwealreadyhaveusefulmethodsfortranslation?InspiredbytheworkofWarner,intheirseminalwork,fiTheMathematicsofStatisticalMa-chineTranslatoion:ParameterEstimationfl([23]),Brownetal.introducedtheconceptofusingShannon'sNoisyChannelModel([89])forthepurposeofStatisticalMachineTranslation(Fig-ure2.1).AnoisychannelframeworkformachinetranslationworkssimilartohowWarnerde-5Figure2.1NoisyChannelModelforStatisticalMachineTranslation[50]scribedinhismemorandum:Forexample,anEnglishsentencegoesthroughafinoisyflchannelandcomesoutasFrench.Nowgiventheobservedfinoisyflsentence(whichisnowinFrench),whatisthemostlikelyEnglishsentenceatthesourceofthenoisychannel?RecoveringtheoriginalEnglishrequiresreasoningabout1)HowtheEnglishlanguageiswritten(fisourcemodelingfl)and2)HowEnglishisturnedintoFrench(fichannelmodelingfl)([55]).Formally,whentranslatingaFrenchwordsequence,f,toEnglish,weassumeaFrenchnativespeakerhadasequenceofEnglishwords,e,inmindwhenproducingtheFrenchwordsequence.TheprocessoftranslatingfintoEnglishistotheEnglishwordsequence‹ethatmaximizesP(ejf).UsingBayes'rule,wecanwrite:P(ejf)=P(fje)P(e)P(f)(2.1)SincethedenominatorinEquation2.1isconstantforallvaluesofe,themaximizationproblemfor‹ecanbeformulatedasEquation2.2,alsoknownastheFundamentalEquationofMachineTranslation([23]).6‹e=argmaxeP(fje)P(e)(2.2)Thisequationpresentsthethreefundamentalcomputationalproblemsofstatisticalmachinetranslation:1.Estimatingthelanguagemodelprobability,P(e).2.Estimatingthetranslationmodelprobability,P(fje).3.FindingthewordsequenceethatmaximizesEquation2.2(Alsocalleddecoding).2.1EstimatingLanguageModelProbabilityAlanguagemodelisformallyasafunctionthattakesawordsequenceinagivenlanguageasinputandreturnstheprobabilitythatthewordsequencewasproducedbyanativespeakerofthatlanguage([57]).LanguageModel:PLM(e1;e2;:::;en)(2.3)ForExample1:PLM(passedtheexam)>PLM(failedtheexam).N-Gramlanguagemodelsaretheleadingmethodforlanguagemodeling.Thismethodisbasedonthelikelihoodthatindividualwordsfolloweachother.TomakethelanguagemodelingproblemtractableaMarkovChainwithaedmemory.ThememorylengthusedintheMarkovChainiscalledthelanguagemodelorder2.Atrigram3languagemodelassumesaMarkovchainoflength1SeeFigure2.2formoredetailsonthisexample([42])2BytheorderofalanguagemodelistwoplusthememorylengthoftheassumedMarkovchain.Thatis,abigramlanguagemodelassumesamemorylessMarkovchain.3Alanguagemodelwithorder3isalsocalledatrigramlanguagemodel.7Figure2.2ProbabilityoffipassedtheexamflandfifailedtheexamflwordsequencesaccordingtoLanguageModelstrainedonpublishedbookseveryyearsince1900withasmoothingfactorofthree([42]).two.Thatis,theprobabilityofthenextwordinasequenceofwordsisonlydependentonitsprevioustwowords.PLM(e1;e2;:::;en)=nÕi=1PLM(eije1;:::;ei1)=nÕi=1PLM(eijeim1;:::;ei1)(MarkovChainwithmemorym)(2.4)An-gramlanguagemodelisestimatedusingalargecorpusinthedesiredlanguagebygatheringn-gramcountsofvariouslengthsuptothelanguagemodelorderandcalculatingsufstatisticsforthelanguagemodel.Inthisthesis,weregularlybuildanduselanguagemodelingtoolsusingoff-the-shelftoolssuchasKenLM([46])andSRILM([93]).Sinceourcontributionsinthisthesisarenotdirectlyrelatedtolanguagemodels,ageneralunderstandingoflanguagemodelsandhowtheyareusedasdescribedaboveissufforunderstandingthisthesis.Formoreinformationsee[57].82.2EstimatingTranslationModelProbabilityThereareseveraldifferentmodelingtechniquesdevelopedforestimatingtranslationmodelprob-abilities.Wordbasedmodels([23]),phrasebasedmodels([58])andhierarchicalphrasebasedmodels([29])aresomeofthemostcommonlyusedmodels.Aprerequisiteforallofthesemodel-ingtechniquesiswordalignment.2.2.1WordAlignmentGivenasentencepairthataretranslationsofeachother,thewordalignmenttaskistoaligneachwordinonesentencetoitstranslationintheothersentence.Thisisformallyusinganalignmentfunction,a:i!jwhichmapsthewordinpositioniinonesentencetoanotherwordinpositionjintheothersentencewherethesetwowordsaretranslationsofeachother.OneofthemaincontributionsofBrownetal.wasmodelingthisalignmentfunctionanddevelopinganExpectationMaximizationalgorithmtoestimateit([23]).InitssimplestformthealignmentfunctioncanbemodeledusingIBMModel1([23])inEquation2.5whereeistheEnglishortargetsentencewithlengthle,fistheFrenchorsourcesentencewithlengthlf,eistheasP(lejlf)andaisthealignmentfunction.P(aje;f)=P(e;ajf)P(e;f)chainrule(2.5)P(e;ajf)=e(lf+1)leleÕj=1P(ejjfa(j))(2.6)Afterreplacementand([57])wecancalculateP(aje;f)asbelow.P(aje;f)=leÕj=1P(ejjfa(j)ålfi=0P(ejjfi)(2.7)IBMModel1onlytakesintoaccountlexicalinformationforalignment.Morecomplexmodelshavebeendeveloped(IBMModels2,3,4and5)toconsiderthepositionofsourceandtargetwords9inthesentence,fertility4anddistortion5.Forthepurposeofthisthesisunderstandingtheconceptofwordalignmentisessential,butestimationmethodsandfurtherdetailsaboutalignmentmodelsarenotnecessary.Givenaword-alignedparallelcorpus6theprobabilityofeachtargetword(s)givenasourcewordcanbeestimatedbygatheringsufcountsfromthecorpusandapplyingthechainrule(Formoredetailssee[57]and[55]).2.2.2PhraseTableWordbasedtranslationmodelsdonotallowforthestatisticalmodelstodirectlylearnthetrans-lationofphraseslongerthanlengthone.Phrasebasedmodelshavebeendevelopedtoaddressthisy.Differentphraseextractiontechniqueshavebeendevelopedforthispurpose.Thephraseextractionprocesstakesaword-alignedparallelcorpusasinputandoutputsatranslationtablewithentriescorrespondingtosourcephrase,targetphraseandtheprobabilityofthetargetphrasegiventhesourcephrase.Formoredetailssee[57]and[58].2.3MachineTranslationEvaluationAutomaticevaluationmethodsformachinetranslationoutputhasbeenoneofthekeycontribut-ingfactorstotheimprovementofmachinetranslationqualityoverthepastdecade.AmongstdifferentevaluationmetricssuchasBLEU7([83])andMETEOR([12]),BLEUiscur-rentlythemostpopularautomaticevaluationmetric([57]).InthisthesiswemakeextensiveuseofBLEUforcomparingthequalityofthetranslationsystemtrainedondifferenttrainingdata,en-4Thefertilityofawordinthecontextofmachinetranslationisasthenumberofwordsonthetargetgeneratedby(oralignedto)asinglewordinthesourcesentence.5Inthecontextofmachinetranslationdistortionisastherelativepositionofwordinthetargetsentencecomparedtothepositionofitscorrespondingwordinthesource.6Aparallelcorpusissimplyacollectionofsentencepairsintwolanguageswhereeachsentenceispairedwithitscorrespondingtranslationsentence.7BLEU:BiLingualEvaluationUnderstudy10ablingustohaveanobjectivecomparisonbetweenvariousdataselectiontechniquesintheabsenceofahumantranslationevaluator.Similartootherevaluationtechniques,BLEUmakesuseofreferencetranslations.BLEUisaprecisionbasedmetric.Thatis,ittakesintoaccountthenumbern-gramsinthetranslationthatoccurinanyofthereferencetranslationsandignoresanyn-graminthereferencetranslationsthatdonotappearintheproducedtranslation.Thedownsideofthisapproachisthatatranslationoutputcangetaperfectscoreifitonlygeneratesasinglematchingunigram.ThisproblemisaddressedinBLEUbyintroducingabrevitypenalty(Equation2.8).brevity-penalty=min(1;output-lengthreference-length)(2.8)Theprecisionforeachn-gramlengthiscalculatedbycountingthetotalnumberofn-gramsintheoutputthatalsoexistsinthereferencedividedbythetotalnumberofn-gramsofthatlengththatappearinreferencetranslation(Equation2.9).precisioni=ångi2Outputångi2Reference1ångi2Reference(2.9)ngi:n-gramoflengthiABLEUscorecanbecalculatedforann-gramofuptoacertainlength(BLEU-n).BLEU-n=brevity-penaltyeåni=1lilogprecisioni(2.10)Then-gramlengthoffouranduniformlambdaweightsisacommonusedforevaluation([57]).ThisEquation2.10toEquation2.11BLEU-4=min(1;output-lengthreference-length)4Õi=1precisioni(2.11)11FormoredetailsonmultiplereferencesandmoredetaileddiscussiononBLEUandothereval-uationmetricssee[57].Inthischapter,wecoveredabriefhistoryofmachinetranslation,keyideasandconceptsessen-tialforunderstandingthisthesis.ForacomprehensiveanddetaileddiscussiononvarioustopicsrelatedtoStatisticalMachineTranslation,seethebookwrittenwiththesametitlebyKoehn([57]).12CHAPTER3LITERATUREREVIEW3.1IntroductionTrainingdataforstatisticalmachinetranslationhasincreasedoverthepastseveralyearsandiscontinuingtogrowevenfurtherasdigitalmultilingualcommunicationandinformationdisseminationbecomeubiquitous.However,thedataisalsocominginanincreasinglywiderspectrumofquality,fromsentencelevelprofessionaltranslationstocrowd-sourcedtranslations,tomachine-generatedoutputsfromfreeonlinetranslators.Thisisoneofthereasonswhydataselectionandcleaninghasbecomeacommonstepinthedevelopmentofmachinetranslationsystems.Atthesametime,whiletrainingdataforstatisticalmachinetranslationisabundantinsomelanguagepairs,developmentofhighqualitymachinetranslationsystemsforlow-resourcelanguagesremainsachallengeduetolackoftrainingdata.Usinghumantranslatorstoproducenewtrainingdatahasbeenacommonsolutiontothisproblem([6,5,24,44]),yetthecostoftranslationhasbeenalimitingfactor.Asaresult,dataselectiontechniqueshavebeendevelopedtoselectmonolingualdatathat,iftranslated,canimprovethequalityofamachinetranslationsystemthemost.Whileindustryleadersinthehavetheinfrastructureandresourcestobuildanditerateoverevergrowingdatasets,thisisnotcosteffectiveforsmallbusinessesandacademics.And,eveninthepresenceofabundanttrainingdataforstatisticalmachinetranslation,itisstilldesirabletoselectasubsetofthedatathatenablesthebesttranslationqualityinastatisticalmachinetranslationsystem.Finally,ofmobileapplicationswhichgenerallyhaveconstrainedmemorylimitationsareanotherimportantapplicationofdataselectioninmachinetranslation.Asaresult,aofdatacleaningandselectionhasformedintheofmachinetrans-lation,andsomeofthemostpracticalmethodsfordatacleaningandselectionhaveappearedinsystemsubmissionpapers.Thischapterattemptstoexhaustivelyreviewtheliteratureinmachine13translationdataselectionandofferacomparativeoverviewoftheproposedmethodsineachappli-cationscenario.Alldataselectionandcleaningalgorithmsselectasubsetofsomeoriginaldataset.Theydifferinthreemaincharacteristics:1.ApplicationScenario:Theapplicationscenarioforeachmethod(e.g.resourcereductionforhighorlow-resourcelanguages,qualityimprovementingeneralordomainadaptationsettings)thetypeofdatathatisbeingselected(parallelormonolingual),andtheproblemthatthemethodaimstosolve(e.g.maximizetranslationqualitywithminimaltrainingtimememoryconsumption).2.ScoringFunctions:Sinceitisinfeasibletotrainamachinetranslationsystemoneachsubsetofthedataandevaluatethequalityoftheresultingsystemforeachsubset,researchershavedevelopedscoringfunctions(features)onsubsetsofthedata,whichareexpectedtocorrelatewiththeusefulnessofthedatasubsetfortrainingahigh-qualitymachinetranslationsystem.Differentapplicationscenariosmotivatedifferentscoringfunctions.3.SelectionAlgorithms:Givenoneormorescoringfunctionsforevaluatingasubsetofdata,weneedtothesubsetthatmaximizesthisscoringfunctionsubjecttosomeconstraints.Dependingonthepropertiesofthescoringfunction,exactorapproximatesearchalgorithmshavebeendeveloped.Intherestofthechapterwereviewthevariationsintheliteraturebasedonthemaincom-ponentslistedabove(Fig.3.1).Nextweprovideacomparativeoverviewofliteratureonhoweachworkhascombinedthecomponentsaboveandhowtheycomparewithotherresearch.Thischapterisorganizedasfollows:InSection3.2webreakoutanddetailtheapplicationscenariosfoundationaltodataselectionalgorithms,asreviewedin(1)above.InSection3.4,weformalizethedataselectionproblemasaconstrainedoptimizationproblemandelaborateondifferentfor-mulationsofsuchproblemscorrespondingtodifferentapplicationscenarios.Anexhaustivelistof1NumbersinFig.3.1indicaterelatedsectionnumbersinthischapter.14DataSelectioninMachineTranslationApplicationScenariosLimitedRe-sourcesTrainingRe-sourcesDeploymentRe-sourcesHumanLabelingRe-sourcesImproveQualityNoiseReduc-tionUnhelpfulDataRe-ductionDomainImprove-mentSentenceScoringFunctionsContextDepen-dentLanguageModelPhraseTableDecodern-gramStatisticContextIndepen-dentAlignmentModelOtherSelectionAlgo-rithmsThresholdBasedFilteringGreedySearchSub-modularOpt.BatchModelLearningActiveLearningEvaluationMethodsFeatureCombina-tionProblemFormula-tion3.23.103.63.43.53.5.23.5.13.73.7.13.7.23.7.33.93.83.5.2.33.5.2.23.5.2.13.5.1.33.5.1.23.5.1.13.5.1.4Figure3.1TaxonomyofdataselectioninMachineTranslation1dataselectionscoringfunctionsispresentedinSection3.5followedbyfeaturecombinationandparametertuninginSection3.6.Thescoringfunctionsareorganizedbasedonthestatisticalmodel(e.g.,languagemodel,translationmodel,...)theyuse.SearchmethodsusedtosolveoptimizationproblemsarelistedinSections3.7,3.8and3.9.MethodsofevaluatingtheeffectivenessofdataselectionmethodsarediscussedinSection3.10.Weprovideacomparativesummaryofallpriorworkinsection3.11,alongwithrecommendationsforapplyingthesemethods,andlistrelatedareasofresearchinSection3.12.153.2ApplicationScenariosDataselectionisperformedinavarietyofscenarios.Therearetwobroadapplicationscenariocategories:thosewherethegoalistominimizeresourceconsumption,andthosefocusedonqual-ityimprovementsornoisereduction.Theseinturncanbebrokendownintosub-categories,asdescribedbelow,allbasedonselectioncriteriaandscoringfunctions,whichwillbediscussedinmoredetailinSection3.4:1.SatisfyingResourceConstraints:Acommonscenarioindataselectionformachinetranslationisthattrainingdatasizeneedstobereducedduetosomeresourceconstraints([66,40,26]).Applicationscenariosinthiscategorydifferbasedontheconstrainedre-source.Althoughmodelpruningcanbeusedtosatisfydeploymentsizeconstraints([41]),selectingasubsetofthetrainingdatacanbeusedtosatisfyanyoftheresourceconstraintlistedbelow.Withanexponentialnumberofsubsetstochoosefrom,thegoalistochooseasubsetofthetrainingdatathatwillultimatelyresultinthehighesttranslationquality.a)TrainingResources:Withtheincreasingavailabilityoftrainingdataforstatisticalmachinetranslation,trainingresourcerequirements(e.g.,numberofcomputers,mainmemorysizeortrainingtime)increaseaswell.Thegoalhereistoreducetrainingresourcerequirementsbytrainingonasubsetofthetrainingdatawithlittleornoimpactontranslationquality.b)DeploymentSize:Inscenarioswhereatranslationsystemishostedondeviceswithlimitedhardwarecapabilities,suchasmobiledevices,itisdesirabletoproducetrans-lationmodelsthataresmallinsizeandcanbehostedonsuchdeviceswithminimumimpactontranslationquality.Onemethodforachievingthisobjectiveisbyselectingasubsetofthetrainingdata([33]).Alternatively,thisobjectivecanbeachievedbypruningthetranslationmodels(Suchmethodsareoutsidethescopeofthisthesis.See[110]foracomparisonofdifferentpruningmethods).16c)ManualTranslationCost:Whenimprovingtranslationqualityforlowresourcelan-guages2wherepre-existingparalleltrainingdataislimited,acommonapproachistoselectasubsetofamonolingualcorpustobemanuallytranslatedbyhumansandaddedtothetrainingdata([5,6]).Sincethereisacostelementinvolved,thegoalistoachievehighestimprovementataedcostormeetapredeterminedqualitybarwithminimumcost.2.QualityImprovement:Unliketheresourceconstraintscenario,thefocusofapplicationsthatfollowthisscenarioisonqualityimprovement.Inthesescenarios,thegoalistoselectadatasubsetwhichwillresultinahigherqualitySMT3systemcomparedtoanSMTsystemtrainedonthefulldataset.Thiscanbedonebyoutsentencesthatarenoisyorthathaveadiftranslationphenomena(e.g.,phrasebasedtranslationsystemsoftenlearnincorrectphrasetranslationsfromfreelytranslated4text),orselectingasubsetthatisrelevanttoadomaindifferentfromthedomainoftheinputdata.Althoughdatasizewilloftenbereducedinthesescenarios,thatisaside-effect,notthegoal.a)Noisereduction:Acommonsourceoftrainingdataisfromcrawledmultilingualwebsites([86]).Webdatacanbeverynoisy,hence,noisereductionhasbecomeacommonpreprocessingstepforthiskindofdata([32]).Forparalleldata,apairofsentencesthatarenotgoodtranslationsofeachothercanbeconsiderednoise.b)ReductionofUnhelpfulData:Althoughtheobjectiveissimilarandalsopartiallyachievedbynoisereduction,itmaybedesirabletooutdatathatarenottradi-tionallyasnoise.Forexample,non-literaltranslationsarenotdesirablefortrainingphrase-basedstatisticalMTsystems(atleastusingcurrenttechnology)..2LowResourceLanguagesarelanguagesthathaverelativelylittlemonolingualorparalleldataavailablefortraining,tuningandevaluation.3SMT:StatisticalMachineTranslation4Freetranslationorfreelytranslatedtextcontrarytoliteral,directorword-for-wordtranslationconveystheoverallmeaningofasentenceorphrasewithoutnecessarilyaword-for-wordcorre-spondencebetweensourceandtranslatedtext[45].17c)DomainImprovement:Acommonapproachforimprovingtranslationqualityistotraindomaintranslationmodels([74,8]).Tothatend,asubsetofthetrainingdatathatismorerepresentativeofthetargetdomaincanbeselected.Inthistask,anin-domaindatasetisusedtoguidethetrainingdataselectionprocess.3.3NotationandTerminologyPriorworkindataselectioninmachinetranslationhaveborrowedterminologyandnotationfromseveralrelatedincludingactivelearning,machinelearningandqualityestimation.Welistthetermsusedintheliteratureforeachconceptindataselectionandpresentthetermsandnotationsweusethroughoutthischapter.Dataselectioninmachinetranslationhasalsobeenreferredtoasdatacleaning([49,80]),noisereduction([95,52,81]),improvingtrainingdataquality([70,2])andactivelearning([5,7]).Althoughweuseallofthesetermsinthecontextofcorrespondingscenariosormethods,werefertothegeneraltaskofselectingasubsetofdatafortrainingasfidataselectionflindependentofitspurposeormethod.Thedataselectiontaskistoselectthefibestflsubsetofthedataformachinetranslationmodeltraining.WerefertothefullsetofavailabledataasfiselectionpoolflorSpoolanddenotethefibestflsubsetbyfioptimumsubsetfl,S,regardlessoftheoptimizationcriteria.Theunitofdataisalwayssentencesorsentencepairs5.Wedonotcalloutparalleldataorsentencepairsversusmonolingualdataorsentenceswhenitisapparentfromthecontext.Whendistinctionbetweentwosidesofaparallelcorpusisnecessary,weusetheletterfisflwithappropriatecasingtoindicatethesourcesideoftheparalleldataandfitflforthetargetside.Theselectionpoolisalsocalledunlabeleddatainsomepriorwork([43]).Insomescenariosthereisaseedparallelormonolingualcorpusgivenaspartofthedataselectiontask.WecallthisdatasetthefiseedcorpusflanddenoteitbySseed.Inthisscenario,theassumptionisthattheseedcorpusisalready5Thetermstranslationunitsorutterancescouldalsobeused,buttheyarefunctionallyequiva-lentinthiscontext.18selectedandthetaskistoselectasubsetoftheselectionpooltobeaddedtotheseedcorpus.Dataselectiontasksfordomainadaptationarealsogivenanfiin-domainfldevelopmentset,Sinandanfiout-of-domainfldevelopmentset,Sout.Insomecases,thefiselectionpoolflisalsousedastheout-of-domaindevelopmentset.Asinglesentenceinanyofthesetsaboveislowercasesitodenotetheithsentenceinthedataset.Inmostproposedmethodsfordataselection,oneormorefunctionsareusedtoevaluatetheusefulnessofasentenceorsentencepair.Theliteraturecallssuchfunctions:features,featurefunctions,objectivefunctionsandfiscoringfunctionsfl.Wechosethelasttermanddenoteitasf(si).Manymethodsproposedfordataselectionuseiterativeselectionalgorithmswhereoneormoresentencesfromtheselectionpoolareselectedineachiteration.Whilethealgorithmhasselectedjsentences,thesentencesthathavebeenselectedsofararecalledthefiselectedpoolflandaredenotedasSj1(sentences1throughj).Inthiscontextitisassumedthataftereachiteration,thefiselectedpoolflisaddedtothefiseedcorpusfl.Theremainingsentencesarenotedasficandidatepoolfl,Scandidate.Scoringfunctionsthatdependontheselectedpoolarecalledficontextdependentflscoringfunctionsandaredenotedasf(sj+1jSj1).TranslationofsentencesiusingmodelstrainedondatasetSisdenotedasti=TX(S)(si)whereX(S)isanymodeltrainedondatasetS(e.g.,languagemodel,LM(S),alignmentmodel,AM(S),ortranslationmodel,TM(S)).Lowercasesm1indicateswords1throughminsentence,s.PLM(S)(si)representstheprobabilityofsentencesiappearingintheevaluationsetaccordingtoalanguagemodeltrainedoncorpusS.PTM(S)(si;ti)andPAM(S)(si;ti)areinterpretedsimilarlyforatransla-tionmodelandanalignmentmodel.Figure3.2demonstratestheroleofeachdatasetinthedataselectionprocess.Theselectionpoolcanbeusedtobuildstatisticalmodels(e.g.,languagemodel,translationmodel,...)toprovidestatisticalinsight.Thesemodelsarecomputedonceandnotupdated.Ontheotherhand,statisticalmodelscomputedusingtheselectedpoolseparatelyorcombinedwiththeseedcorpusareupdatedastheselectedpoolchangesduringthedataselectionprocess.Scoringfunctionsthatdependonthemodelsthatneedtobeupdatedarecalledcontextdependentscoringfunctions.Inaddition,adecoderusingmodelsbuiltbytheselectionorselectedpoolcanbeusedasanotherinputto19Figure3.2DataSelection:Thisdiagramdemonstratestheroleofeachdatasetinthedataselectionprocess.contextdependentorcontextindependentscoringfunction.Adevelopmentsetcanbeusedtotrainweightswhenmorethanonefeaturefunctionsisused.Ultimately,thescoringfunctionisusedtoscoresentencesorsentencepairsintheselectionpoolwithanoptimizerusedtoselecttheoptimumsubsetoftheselectionpool.Theoptimizationstepisoftendonebygreedilyaddingsentencepairsfromselectionpoolintotheselectedpool.Forcontextdependentfunctions,themodelsorstatisticsneedtoberecomputedaftertheselectionofeachsentencepair,orNsentencepairsinthecaseofbatchlearning.3.4ProblemFormulationDataselectioncanbeformulatedasaconstrainedoptimizationproblem.Theconstraintisthattheoptimumsubsethasagivenmaximumsize,whichisusuallymeasuredbythenumberofsentencesorsentencepairsinthesubset,denotedbyjSj(Sizecanalsobemeasuredintotalnumberof20characters,tokens,tokentypes,etcdependingonthescenario.)Thetruescoringfunctionthatadataselectionmethodaimstomaximizemeasurestheexpectedtranslationqualityusingdatadrawnfromsomedesiredtargetdistribution(whichcouldbeofgeneraldomainoratargetdomaininthecaseofdomainadaptation).Belowweformulateaconstrainedoptimizationprobleminagenericform,whichexpresseswhatdataselectionmethodsaimtoachieveintheory.Sinceitisimpracticaltosolvethiscon-strainedoptimizationproblem6,differentdataselectionmethodsusealternativeformulations.Thetruescoringfunctionistoselectasubset,S,fromtheselectionpool,Spool,thatmaximizesexpectedtranslationquality7whentranslatedusingmodelstrainedonSforanydatasample,D,thatisdrawnfromsomedesiredtargetdistributionP(ngram),subjecttosomesizeorresourceconstraintC,asshowninEquation3.1.S=argmaxSˆSpool;Size(S)<CEhBLEUDref;TX(S)(Dsrc)(3.1)Dsrc:SourcesideofDDref:ReferencetranslationforDsrc(3.2)ThevalueforEhBLEUDref;TX(S)(Dsrc),isusuallyestimatedusingablindtestset,STest,drawnfromthedesiredtargetdistributionP(ngram)(Equation3.3).S=argmaxSˆSpool;Size(S)<CBLEUSTestref;TX(S)STestsrc(3.3)Consequently,thetaskofdataselectionistothebestsubsetofsentencesthatwillresultinhighesttranslationqualityasapproximatedonablindtestsetwhichisnotavailableduringtraining.Someapplicationscenariosprovideaconstraintonthesizeofthesubset.Therearethereforetwotechnicalproblemstosolve:6Thenumberofsubsetsofsizemfromasetofsizenisn!m!(nm)!.Sincethisvalueisexpo-nentialinnk,itisimpracticaltodoanexhaustivesearchenumeratingallsubsets.7WewilluseBLEUastheautomatedmetrichere,butothermeasuresarecertainlyviable.BilingualEvaluationUnderstudyisthemostpopularautomaticevaluationmetricbasedonn-grammatchesbetweentranslationoutputandreferencetranslations([57,82])211.EfestimationofthequalityofanMTsystemtrainedonasetSusinganunseentestset.2.FindingthedatasubsetSthatmaximizesthisestimatedquality.Avarietyofmodelshavebeenforthequalitymentionedabove.TheyeitheruseasinglescoringfunctionondatasubsetSoramodelwhichcombinesmultiplescoringfunctionsorinthecaseofactivelearning,anSMTsystem(orsomeelementsofit,likealanguageortranslationmodel)whichistrainedonthetrainingdataandevaluatedagainstablindtestset.Anexampleofascoringfunctionisn-gram8coverageofthedatasubsetwithrespecttotheselectionpool.Thusasubsetthatcoversalargerportionofalln-gramsisassumedtoresultinahigherqualityMTsystem.Multiplescoringfunctionscanalsobecombinedusingalinearmodelforestimation.Equation3.4belowshowsaformulationoftheoptimizationproblemfromEquation3.3whereacombinationofscoringfunctionsisusedtomodeltranslationquality.S=argmaxSˆSpool;Size(S)<CFeatureCountåi=1liFi(S)(3.4)Fi(S):corpuslevelscoringfunctionli:featureweightOnceamodelforscoringthegoodnessofdatasubsetshasbeentheremainingproblemissearchingforthebestsubsetofagivenmaximumsize.Dependingonthescoringfunctions,thesearchproblemcanbeextremelyhardandnecessitatingapproximatesearchtechniques.Forpracticalpurposes,thescoringfunctionsoverdatasubsetscanbedecomposedintoincrements8Inthischapter,unlessotherwisewordn-gramsarereferredtoassimplyn-gramsforbrevity.Awordn-gramisasequenceofnwordsthatappearinnaturallanguagetext.22whenaddingeachsentenceonebyoneinagivenorder.Giventhisdecomposition,acorpussubsetcanbeselectedincrementallybyaddingindividualsentences.Equation(Equation3.5)showssuchadecomposition.S=argmaxSˆSpool;Size(S)<CjSjåj=1FeatureCountåi=1lifi(sjjSj11)(3.5)fi(sjjSj11):contextdependentsentencelevelscoringfunctionEquation3.5assumesconditionalindependenceforthescoringfunctionbetweensentencesintheselectionpoolgiventheselectedpool.OntheotherhandEquation3.6assumescompletein-dependence.Ifthesentencelevelscoresareindependentofpreviouslyselectedsentences(e.g.,sentencelength),asimplethresholdbasedalgorithmwillprovidetheoptimumsolution([53])totheconstraintoptimizationproblemwithcomputationalcomplexityofO(jUjlogjUj)forsortingsentencesbasedontheirfeaturefunctionvalueandO(jSj)forsatisfyingtheresourceconstraint.Thisisoftenthecaseforscoringfunctionsmotivatedbydatacleaningandnoisere-duction(Forexample,thesourcetotargetsentencelengthratio.)Sentencelevelscoringfunctionsthataremotivatedbyminimizingresourceconstraintsareoftendependentonpreviouslyselectedsentences(e.g.,numberofnewn-gramsinasentence).S=argmaxSˆSpool;Size(S)<Cås2SFeatureCountåi=1lifi(s)(3.6)fi(s):sentencelevelscoringfunctionInsuchcases(Equation3.6)anincrementalsearchalgorithm(e.g.greedysearch)isoftenusedtosolvetheconstrainedoptimizationproblem.SelectionalgorithmsarediscussedinmoredetailinSection3.7.233.5SentenceLevelScoringFunctionsAsexplainedinSection3.4,theconstrainedoptimizationproblemisoftenbrokendownusingacombinationofsentencelevelscoringfunctionstoenablesolvingtheoptimizationproblemefciently.Thesefunctionscanbecategorizedasfollows.ContextIndependentFunctionswhichdependonnothingbutthecandidatesentencesinquestion.ContextDependentFunctionswhichdependontheselectedpool.Thresholdcanonlybeusedforcontextindependentfunctions.Forcontextdependentfunctions,agreedyincrementalsearchalgorithmisoftenusedtosolvetheoptimizationproblem.3.5.1ContextDependentFunctionsThevaluesorscoresofcontextdependentfunctionsdependonstatisticsfromtheselecteddata,inadditiontothesentencebeingscored.Inatypicaldataselectionalgorithm,allsentencesarescoredandoneormore9sentenceswithhighestscoreareaddedtotheselectedpool.Thisrequiresthestatisticsinusetoberecomputedinadditiontoallcandidatesentencescores.Wecategorizethescoringfunctionsinthisgroupbasedonthestatisticsormodelsthatneedtobecalculatedovertheselectedsentencesinordertoassignscorestocandidatesentences.3.5.1.1N-GramCoverageFunctionsFunctionsinthisgrouparemotivatedbyasubsetoftheselectionpoolthatbestrepresentstheentiresetusingn-gramstatistics.Inotherwords,whenselectingasubsetoftrainingdata,itisoftendesirabletopreservethevocabularyanditscontext(n-grams).Thesimplestwayofusingn-gramstatisticsforthispurposeistoensurealln-gramsofuptoacertainlengtharepresentin9Batch-learningtechniquesareoftenusedtomakedataselectionmethodspractical.SeeSec-tion3.9fordetails.24theselectedsubset.Forthispurpose,itissuftokeepthen-gramcountfortheselectedpool.Foreachcandidatesentence,thescoreisequaltothenumberofnewn-gramsitcontainswherethen-gramlengthislessthanorequaltoN.f1(sjjSj11)=1norm(sj)Nån=1ång2NG(sj;n)weight(ng;j1)(3.7)NG(s;n):Alln-gramsofsizeninsentencesweight(ng;m):Weightofn-gramnggivenselectedpoolSm1areselectednorm(s):NormalizationfactorforsentencesEquation3.7coversmuchofthepriorworkdependingonthechoiceofweight(ng;m)andnorm(s).Ecketal.presentseveralscoringfunctionswithweight(ng)equalto1([33]).Intheirsimplestscoringfunctiontheyonlycountthenumberofnewn-gramsinasentenceandnormalizebythelengthofthesentence(Equation3.8).weight1(ng;m)=8><>:0ng2mSi=1NG(sm;n)1otherwise(3.8)norm1(s)=jNG(s;n)jInthisapproachrareandfrequentn-gramsarevaluedequally.Intheirefforttoassignahigherweighttomorefrequentn-gramsintheselectionpool,Spool,Ecketal.usethen-gramfrequencyastheweightintheirimprovedscoringfunction(Equation3.9).Usingnormalizationfactorsofjsjiwhereitakesonvaluesof0,1and2,areothervariationsattemptedbythiswork.weight2(ng;m)=8><>:0ng2mSi=1NG(sm;n)Freq(ng;Spool)otherwise(3.9)Freq(ng;S)=ås2Sång2NG(s;len(ng))125Aclearshortcomingofthisfunction(Equation3.9)isthatonceann-gramexistsintheselectedsentences,itisofzerovaluewhenselectingnewsentences.Thisdoesnotallowforthescoringfunctiontodiscriminateagainstann-gramwithfrequentoccurrencesintheselectedsentencesversusann-gramthathasonlyappearedonce.Thisisthemotivationforintroducingafeaturedecayfunctionforthen-gramweight([4,16]).weight3(ng;m)=Freq(ng;S)elFreq(ng;fs1:::smg)(3.10)l:ExponentialdecayhyperparameterFortheirlastvariationontheweightfunction,Ecketal.usethecosinesimilaritybetweenTF-IDF10vectorsoftheselectedpoolandsentencesinthecandidatepool([33]).InaninformationretrievalsettingforTF-IDF,allsentencesintheselectedpoolplaytheroleofthesearchquerywhileeachsentenceinthecandidatepoolisconsideredapotentialmatchingdocument.Thegoalinthiscaseistothedocument(candidatesentence)thatismostdissimilartothesearchquery(selectedpool).theweightfunction,weight(ng;m),asfollows,resultsinEquation3.7whichusescosinesimilarityofTF-IDFvectorsasabove,asthesentencescoringfunction.tf(ng;S)=Freq(ng;S)idf(ng;S)=jSjåsi2S1(ng2NG(si;len(ng)))1(ng2NG)=8><>:1ng2NG0otherwiseweight4(ng;m)=tf(ng;Sm1)Logidf(ng;SjSjm+1)(3.11)SincethegoaloftheTF-IDFweightfunctionistothemostdissimilarsentence,theoveralloptimizationproblem(Equation3.6)turnsintoaminimization,unlikeothern-grambasedscoringfunctions.10TermFrequency-InverseDocumentFrequency263.5.1.2Phrase-TableBasedFunctionsScoringfunctionsinthissectionrequireaphrasetable.Dependingonthefunction,thefiseedcorpusfl,thefiselectionpoolfl,thefiselectedpoolflorficandidatepoolfloracombinationofthemareusedtotrainthephrasetable.Whenselectingfromamonolingualpoolofsentences,afullSMTsystemtrainedontheseedcorpuscanbeusedtoturnthemonolingualcorpusintoaparallelcorpustotrainthephrasetable[43].Haffariintroducestheideaofexplorationversusexploitationinthiscontext([43]).Theideaistofiexploreflbyselectingsentenceswithnewphrasepairstoexpandcoveragewhilefiexploitingflphrasepairsthatarenotnew,toimprovetheirprobabilityestimation.WeuseTable3.1tofurtherexplainthisidea.Phrasepairsthatoccurfrequentlyintheselectionpoolbutdonotoccuroroccurrarelyintheseedcorpusareofmostvalue.Iftheydonotexistintheseedcorpus(A),theyaddnewcoverage(exploration).Ontheotherhand,theyprovidebetterestimationiftheyoccurrarelyintheseedcorpus(B,exploitation).Phrasepairswithlowfrequencyintheselectionpoolcanalsobeusefuliftheyoccurrarelyintheseedcorpus(D)ordonotoccuratall(C).Althoughthisintuitionisexplainedinthecontextofphrase-pairsitisapplicableton-gramandlanguagemodelbasedscoringfunctionsaswell.SelectionPoolPhrasePairshighfrequencylowfrequencyzerofrequencySeedCorpushighfrequencylowfrequencyBDzerofrequencyACTable3.1ExplorationversusExploitationA:Improvedcoverageforimportant11phrasepairsB:ImprovedestimationforimportantphrasepairsC:ImprovedcoverageforphrasepairsD:ImprovedestimationforphrasepairsHaffariintroducesaphrasepairutilityfunctiontocaptureexplorationversusexploitation(Equation3.12).Thesentencescoringfunctionisthencomputedusingarithmetic(Equation3.13)11Theassumptionhereisthataphrasepairthatoccursfrequentlyintheselectionpool,islikelytobeusedinatranslationtask,andthereforeimportant.27orgeometric(Equation3.14)averageofthephrasepairutilityfunctionoverallphrasepairs.PPUtil(ppj(s;t)j11)=P(PP1=ppjPP12j1Sk=1PPs(sk;tk))P(PP2=ppjPP22jSjSk=jPPs(sk;tk))(3.12)pp:Aphrasepairmappingaphraseinonelanguagetoitstranslationinasecondlanguage.PPs(s;t):Thesetofallphrasespairsextractedfromsentencepair(s,t).f2((sj;tj)j(s;t)j11)=0@Õpp2PPs((sj;tj))LogPPUtil(ppj(s;t)j11)1A1jSj(3.13)f3((sj;tj)j(s;t)j11)=1jSjåpp2PPs((sj;tj))PPUtil(ppj(s;t)j11)(3.14)Ambatitakesadifferentapproachinusingaphrasetableforscoringsentences([4]).Thegoalistogiveahigherscoretosourcephraseswherethephrasetableismoreuncertainabouttheirtrans-lation.Sinceentropyisameasureofuncertainty,Ambatiphrasalentropy(Equation3.15)tocalculatethelevelofuncertaintyaphrasetablehasregardingasourcephrase.PhrEnt12(psj(s;t)j1)=åpt2Trans(ps)PTM(Sj1)(ptjps)logPTM(Sj1)(ptjps)jTrans(ps)jTrans(ps):Targetphrasesforphrasepsaccordingtophrasetabletrainedon(s;t)j1(3.15)Usingphrasalentropy,thescoringfunctionforasentenceisasthesumofthephrasalentropyoverallsourcephrasesinasentence.Thisscoringfunctioncanbeextendedtousetwo12ByconditionalentropyofH(YjX)isasåx2X;y2Yp(x;y)logp(yjx).But,theprovidedforPhrEnthereismissingaPTM(Sj1)(ps)insidethesummationbutoutsidethelog.Werecognizethisinaccuracybutkeeptheformulaconsistentwiththereferencedwork([4]).28differentphrasetables(onetrainedfromsourcelanguagetotargetlanguageandtheothertargettosource).Usingthesecondphrasetable,uncertaintyabouttargetphrasescanalsobetakenintoaccount.3.5.1.3LanguageModelBasedFunctionsLanguagemodelbasedscoringfunctionsaresimilarton-grambasedscoringfunctions.Inbothcases,n-gramsarethebasisforscoringsentences.Theadvantageoflanguagemodelbasedscoringfunctionsistheirhigheraccuracyinestimatingn-gramprobability,especiallywhenthedataissparse(Thisisduetoback-offandsmoothingstrategiesusedinlanguagemodeling.)Ontheotherhand,trainingalanguagemodelhasahighercomputationalcomplexitycomparedtocollectingn-gramstatisticsforn-grambasedscoringfunctions.Intheabsenceofaphrasetable(whenparalleldataisnotavailableorlesscomputationalintensityisdesirable),Haffarietal.suggestsusingalanguagemodeloverallpossiblephrases(alln-gramsofuptoacertainsize)tocalculatetheequivalentofthephrasepairutilityfunctioninEquation3.12,n-gramutility.N-gramutilityfollowsthesameprinciple,butusesn-gramsandtwolanguagemodels(onelanguagemodeltrainedontheseedcorpusandanothertrainedontheselectionpool)insteadofphrasepairsandtwophrasetables(Equation3.16).NGramUtility(ngj(s;t)j11)=PLM(SjSjj)(NG1=ng)PLM(Sj11)(NG2=ng)(3.16)PLM(Sj11)(NG=ng):Probabilityofn-gramngaccordingtolanguagemodeltrainedonSj11.Thesentencescoringfunctionisthenasanarithmeticorgeometricaverageofthen-gramutilityfunctionofalln-gramsuptoacertainlengthderivedfromthesentence.InaslightvariationtoEquation3.16,Mandaletal.useperplexity13insteadofprobabilityusingthesame13Theperplexityofarandomvariableisastwo(oranygivenbasenumber)tothepowerofitsentropy.Innaturallanguageprocessingthisfunctioniscommonlyusedasameasureofhowsurprisedalanguagemodeliswhenobservingasequenceofwords.29languagemodels([71]).Liuetal.attempttoassignthehighestscoretosentenceswithmostinformativen-grams([69]).Theymeasureinformativenessofn-gramsbyn-gram14entropy.Inaddition,theymultiplytheentropybythesquarerootofthen-gramlengthtoencouragelongerphrasesastheysuggestlongerphrasescontributetobettertranslation.NGEntropy(ngjSj11)=log PLM(SjSjj)(ng)!plen(ng)1ng2NG(SjSjj)15(3.17)Equation3.17usesindividualentropyasameasureofinformativeness.Wewouldliketopointoutthatamoreappropriateuseofentropywouldbeusingitasameasureofuncertainty.Forthispurpose,givenan-gramngofsizem,fw1:::wmg,theentropyofthen-gramcanbeinthecontextofalln-gramsofsizem+1,fw1:::wm+1g,thathaven-gramngastheir(Equation3.18).NGEntropyLM(Sj1)(wm1)=åw2Vocab(Sj1)PLM(Sj1)(wjwm1)logPLM(Sj1)(wjwm1)Vocab(Sj1):ThesetofalluniquewordsinSj1.(3.18)Finally,Ambatiattemptstomaketheprobabilitydistributionfunctionoftheselectedpoolascloseaspossibletotheprobabilitydistributionfunctionoftheselectionpool.Twolanguagemodelsaretrainedforthispurpose.Thelanguagemodelistrainedontheseedcorpusandselectedpool,whilethesecondlanguagemodelistrainedontheselectionpool.Theaimisto14Forallpracticalpurposesintheirwork([69]),aphraseisthesameasann-gramastheyconsiderphrasesforasentencetobealln-gramsofuptoacertainlength.15SeeEquation3.7forofNG(SjSjj).30minimizetheKullback-Leiblerdivergence16betweenthesetwoprobabilitydistributionfunctions.Toachievethis,thescoringfunctionforasentenceequalsthesumofitsn-gramcontributionstototheoverallKLdivergence(Equation3.19).KL-Div(ng)=PLM(Sj11)(ng)logPLM(Sj11)(ng)PLM(SjSj1)(ng)(3.19)BasedonEquation3.19,thesentencelevelscoringfunctionisthesumoftheKL-Divfunctionoverallpossiblen-gramsinasentence.3.5.1.4DecoderBasedFunctionsDecoderbasedscoringfunctionsrequireafullSMTsystemtobetrainedovertheseedcorpus,theselectionpoolorboth.Ifthegoalistoselectfromaparallelpoolofsentences,thesimpleapproachistouseafullSMTsystemtrainedovertheseedcorpustotranslatesentencesintheselectionpool.Thescoringfunctionforasentenceisbasedontheerrororthedistancebetweentheproducedtranslationandthetargetsideofthesentencepair.TheideaisthatiftheSMTsystemmakesanerroronasentence,thesentenceislikelytocontainusefulinformation.Mostofthefunctionsintroducedinthiscategoryassumetheselectionpoolismonolingualandthereforeuseothermeanstomeasurethelikelihoodthatthedecoderwillproduceanerroneoustranslation.HaffariusesanSMTtrainedontheseedcorpustotranslatethemonolingualselectionpool.Thescoringfunctionisobtainedbynormalizingthemodelscoreproducedbythedecoderusingsentencelength.Onedrawbackofthisscoringfunctionisthat,althoughdecoderscoreisanobjec-tivescorewhencomparingtranslationsofthesamesourcesentence,itisnotacomparablescorewhenconsideringdifferentsourcesentences.However,differencesinthisscorecanbeameaningfulmeasureandcaneffectivelybeusedfordataselection([44,4]).16Kullback-Leiblerdivergenceisaninformationtheoreticmeasureofthedistancebetweentwoprobabilitydistributions.31AnotherapproachtomeasuringtranslationerrorisusingRoundTripTranslationAccuracy(([44])).InthismethodtwoSMTsystemsaretrainedontheseedcorpus,oneineachdirection.Foreachsentenceintheselectionpool,itistranslatedoncefromsourcetotargetandthenfromtargettosource.Thescoringfunctionisthentheerrorfunctionbetweenthetranslationandtheoriginalsentence.Inter-SystemDisagreementisanotherapproachdevelopedbyMandaletal.([71]).Inthismethoddifferentstatisticalmachinetranslationsystems(e.g.,ahierarchicalsystemaswellasaphrasebasedsystem)aretrainedonaseedcorpus.Next,sentencesinaparalleldevelopmentsetaretranslatedusingallstatisticaltranslationsystems.Foreachtranslationsystem,aninter-systemdisagreementerroriscalculatedforitstranslationoutputusingallothersystems'outputasreferences.Thetargetsideofthedevelopmentsetisthenusedtotrainalinearregressionmodelthatpredictsthetranslationerrorbasedontheinter-systemdisagreementerrorfromeachtranslationsystem.Oncethelinearregressionmodelislearned,inter-systemdisagreementerrorsarecalculatedfortheselectionpoolandfedintothelinearregressionmodeltoproducethescoringfunction.Theideaisthatthesentenceswherethetranslationoutputfromdifferentsystemsdifferthemostarethemostpoorlytranslatedsentencesandthereforemostinformativeifaddedtotrainingdatawithhumantranslation.TheworkofAnanthakrishnanetal.differsfromallotherworkinthiscategory,sinceitdoesnotuseasentencelevelscoringfunction([6]).Instead,theytrainasentencelevelpairwisecomparatortosortsentencesintheselectionpoolbasedontheirestimatedtranslationerrorreduc-tion.Thepairwisecomparatorusesn-gramfeaturestocomparesentences.However,weincludethisworkinthissection,sinceadecoderwithmodelstrainedontheseedcorpusisusedtocreatethedevelopmentset.First,aparallelcorpusisrequiredtocreatethedevelopmentset.Next,thesourcesideoftheparallelcorpusisdecodedandtheTER17iscalculatedforeachsentencepair.Ananthakrishnanetal.suggestifthesentencewiththehighestTERisaddedtotheseedcorpus,itwilllikelyreducethetranslationerrorthemost.Sortingthesentencepairsinthedevelopment17TranslationEditRate(TER)measurestheamountofeditingahumanwouldneedtoperformonamachinetranslationoutputtoexactlymatchareferencetranslation([90]).32setaccordingtotheirTERscoreproducesthenaldevelopmentset.Theytrainthepairwisecom-paratorweightstobestmatchtheorderofsentencesinthedevelopmentset.Afterthecomparatoristrained,itisusedtosortthesentences.Thescoringfunctioninthiscaseistherankofeachsentenceinthesortedlist.Finally,Kauchakattemptstoestimatethecontributionofeachsentencepairintheselectionpoolbysamplingalargenumberofrandomsubsetsoftheselectionpoolwithreplacementandtrainingastatisticalmachinetranslationsystemsovereachsubsetofthetrainingdata.Aftercal-culatingtheperformance(e.g.,BLEUscore)ofeachsystem,acontributionscoreisestimatedforreachsentencepairbasedonitsmembershipindifferentsubsetsandtheperformanceofthosesubsets.Thismethodisverycomputationallyintensiveanditsuseisnotfeasibleinpracticalsce-narios.However,itcanbecalculatedonsmalldatasetsandusedasanoraclescoretoevaluateotherdataselectionfeaturesortunehyperparametersforvariousdataselectionmethods([51]).3.5.2ContextIndependentFunctionsContextindependentfunctionshavemostlybeeninspiredbyfeaturesusedintheareaofTranslationQualityEstimation([98]).InTranslationQualityEstimation,givenasentenceanditstranslation,thequalityofthetranslationisestimatedintheabsenceofareferencetranslation.Wehavegroupedthesefunctionsbasedonthestatisticormodelthatisrequiredfortheircomputation.3.5.2.1LanguageModelBasedFunctionsLanguagemodelscanbeusedindifferentwaystoassesstheusefulnessofasentenceorsentencepair.Denkowskietal.useanexternalsourceandtargetlanguagemodeltrainedoncleandatatooutungrammaticalsentences(Equation3.20).Inthiscasethescoringfunctionisthelengthnormalizedlanguagemodelscoreofthesentence([32]).Allauzenetal.usethelanguagemodelperplexityscoreofthesentenceasitsscoringfunctiontooutforeignlanguagesentences([3])(Equation3.21).33f4(si)=PLM(Sclean)(si)(3.20)f5(sijSclean)=2HindLM(Sclean)(si)(3.21)HindLM(S)(si)=PLM(S)(si)logPLM(S)(si)(individualentropy)Yasudaetal.usealanguagemodeltrainedonanin-domain18developmentsettoscoresen-tencesintheselectionpool([108]).Inthisapproachthescoringfunctionequalsthegeometricalaverageofthesourceandtargetentropy19ofthesentencepairaccordingtotheindomainlanguagemodels(Equation3.20).f6(sijSin)=rHindLM(Sin-src)(si)HindLM(Sin-tgt)(si)(3.22)Sincethelanguagemodelusedincomputingtheentropyisanestimateofthetrueprobabilitydistributionfunction,cross-entropy20isusedinstead.Auniformprobabilitydistributionfunctionisusedtoestimatecross-entropy.Thegoalinthismethodistogivesentencessimilartothein-domaindevelopmentsetahigherscore.However,theshortcomingofthismethodisthatitwillalsogivegenerallypopularsentences(thatarealsopopularinthein-domaindevelopmentset)ahighscoreaswell.Thisisnotdesirableinadomain-adaptationdataselectiontask.MooreandLewisaddressthisissuebyintroducingasecondlanguagemodeltrainedonageneral-domainde-velopmentset([74]).Intheirapproach,theyusethecross-entropydifferenceofthetwolanguagemodelstoscoresentences(Equation3.23).f7(sijSin;Sout)=HindLM(Sin)(si)HindLM(Sout)(si)(3.23)18Theseedcorpuscanbeusedforthispurposeaswell.19Entropy,H(X),measurestheamountofinformationoruncertaintyinarandomvariable([72]).20Cross-Entropyofarandomvariable,X,withthetrueprobabilitydistributionfunctionofP(X)andanestimatedprobabilitydistributionfunctionofQ(X)isformallyasthesumoftheentropyofXplustheKL-divergencebetweenP(X)andQ(X):H(P(X);Q(X))=H(X;P(X))+DKL(P(X)jjQ(X))([30]).34Axelrodetal.extendthecross-entropydifferencemethodtoincludethetargetsideofpar-alleldata([10]).Intheirmethod,bilingualcross-entropydifference,twoseparatein-domainandgeneral-domainlanguagemodelsaretrainedforthesourceandtargetlanguage.Foragivensentencepair,itsscoreiscalculatedbyaddingthecross-entropydifferenceofsourceandtargettogether(Equation3.24).f8(sijSin;Sout)=f7(sisrcjSin-src;Sout-src)+f7(sitgtjSin-tgt;Sout-tgt)(3.24)3.5.2.2AlignmentModelBasedFunctionsAlignment21basedscoringfunctionsareonlyapplicabletoparalleltrainingdataselection.Thesescoringfunctionsattempttoquantifythetranslationqualityandaccuracyofthesentencepair.Anywordalignmentmodel(e.g.,HMM-basedwordalignmentmodel[99])canbeusedtocomputethisscoringfunctionbyaligningeachwordinasentencetocorrespondingword(s)initspair.Anumberofscoringfunctionscanbecomputedusingthisalignmentmodel.KhadiviandNeysuggesttraininganalignmentmodel22onallsentencesintheselectionpool.ThescoreforeachsentenceequalstheaverageViterbialignmentprobabilitiesaccordingtosource-to-targetandtarget-to-sourcealignmentmodels(Equation3.25).21Awordalignmentmodelisastatisticalmodeltrainedandusedtoalignindividualwordsinasentencetotheirtranslationsinthetranslatedsentence.Aword-alignedsentencepaircontainsalignmentlinksusedtoalignwordsinonesentencetotheother([23]).22Intheirwork,KhadiviandNeyuseIBMmodel1,HMMandIBMmodel2insuccessiontotrainthemodel.But,theirscoringfunctiondoesnotdependonanyparticularalignmentmodel.Hence,anyalignmentmodelcanbeused.35f9((si)m1;(ti)n1)=1mlogmaxam1PAM(si)m1;am1j(ti)n1+1nlogmaxan1PAM(ti)n1;an1j(si)m1(3.25)(si)m1:words1throughminsentencesi:am1:targetwordalignmentlinkforsourcewords1throughm:Taghipouretal.introducealignmententropyasascoringfunction.Alignmententropy,asinEquation3.26,isasmoothmeasureofuniformdistributionofalignmentlinks.Inotherwords,givenanalignmentlinkcountofn,howuncertainthemodelisaboutpredictingthewordcorrespondingtothelink23.Thehighestvalueforalignmententropyisachievedwhenallwordshavethesamenumberofalignmentlinksassociatedwiththem.f10(si;ti)=1nå(si)n1p1((si)n1)logp1((si)n1)1må(ti)m1p1((ti)m1)logp1((ti)m1)(3.26)p1((si)k)=a((si)k)åka((si)k)a((si)k):Thenumberoflinksthatendonword(si)kTheyalsouseanumberoffeaturesinspiredbytheworkofMunteanuandMarcuonfiexploita-tionofnon-parallelcorpusformachinetranslationflbasedonnumberofalignmentlinksandword23Wethinkamorenaturalderivationforalignmententropyofasentenceisaveragingalignmententropiesofeachsourceortargetwordaccordingtoallpossiblealignments.Thiswillprovideameasureofhowuncertainanalignmentmodelisaboutwordalignmentsinasentence.ThisisamorenaturaluseofentropycomparedtotheuncertaintyaboutawordgiventhenumberofViterbialignmentlinksfortheword.36fertility24.f11(si)=Nsrc(si)Ntgt(si)(3.27)f12(si)=Nsrc(si)jsij(3.28)f13(si)=Ntgt(si)jsij(3.29)f14(si)=argmaxwi2sifertility(wi)(3.30)Nsrc(s):NumberofnullalignedsourcewordsinsentencesNtgt(s):NumberofnullalignedtargetwordsinsentencesDenkowskietal.addthefollowingscoringfunctionstothelistabove([32]).f15(si)=Asrc(si)jsij(3.31)f16(si)=Atgt(si)jsij(3.32)Asrc(s):NumberofalignedsourcewordsinsentencesAtgt(s):NumberofalignedtargetwordsinsentencesAmbatiusesbidirectionalalignmentscorestoprovidethescoreforasinglealignmentinasentencepair([4]).Denkowskietal.assignasentencepairscorebyaveragingthesealignmentscores([32])(Equation3.33).f17(si;ti)=qPAM(sijti)PAM(tijsi)(3.33)Inaddition,Ambatiproposeusingthedistancebetweenthebidirectionalalignmentscoresforthehighestprobabilityalignmentandthesecondhighestprobabilityalignmentforasourceortargetwordasameasureofalignmentuncertainty.Thecloserthedistance,themoreuncertainthealignmentmodelisaboutthealignmentforthewordinquestion(Equation3.34).Although,they24Inwordalignment,fertilityofawordisasthenumberofalignmentlinksinitiatedfromthatword.37havenotextendedthisscoringfunctiontothesentencelevel,anaverageoverallsourceortargetwordscanbeusedtoprovideasentencelevelscoringfunction.3.5.2.3OtherScoringFunctionsWeprovidealistofsentencelevelscoringfunctionsthatdonotthescoringfunctioncategoriesabove.Theseincludelength-basedfunctions,character-basedfunctionsandfunctionsindicatingliteralnessoftranslation.Length-basedfunctionsareprimarilyusedtooutnoisydata.Inthefollowinglengthbasedfunctions,sentencelengthcanbecalculatedasthenumberoftokens/wordsornumberofcharacters.Adevelopmentsetcanbeusedtotunethresholdsfortheselengthbasedfunctions[52,95].Alternatively,anunsupervisedoutlierthresholdcanbedevelopedbasedonthecandidatesentencepoolitself([32]).1.Sourcesentencetotargetsentencelengthratioandviceversa([52,95,32])2.Differenceofsourceandtargetsentencelengths[95])3.Sentenceslength([32])4.Lengthoflongesttokeninthesentence([32])Afewothersimplescoringfunctionscanalsobeusedtooutnoisydata.1.Sentenceendpunctuationagreement([52])2.Percentageofalphanumericcharacters([52,32])3.Existenceofcontrolcharactersandinvalidunicodecharacters([32])4.Co-occurrenceofspecialtokenssuchasemailaddress,URL,dateornumberonbothsidesofasentencepair([95]).Inadditiontothefunctionsabove,Hanetal.introducetwofunctionstoassesslexicalandsyntacticcompatibilityofasentencepair([45]).Theirapproachistoassignscorestosentence38pairsaccordingtothepotentialforastaticalmachinetranslationtolearnformthesentencepair.Theideaisthatsentencepairswithliteraltranslationsaremorelikelytobeusefulcomparedtoanabstractorconceptualtranslation.First,theyattempttoestimatetheliteralnessofatranslationgivenasentencepairusinglexicalfeatures.Thisfeatureiscalculatedbyexpandingthewordsofsourceandtargetsentencesbyasynonymdictionaryandthencountingthenumberofwordsthataretranslationsofeachothergivenabilingualdictionary.Theynormalizethisvaluebythetotalnumberofwordsanduseitasthefunctionscore(Equation3.34).f18(si;ti)=SkBiDicsrc!tgtSynonymssrc(sik)T SkSynonymstgt(tik)!SkSynonymstgt(tik)+SkSynonymssrc(sik)T SkBiDictgt!srcSynonymstgt(tik)!SkSynonymssrc(sik)(3.34)BiDicsrc!tgt(wi):Translationsforwordwiaccordingtoagivendictionary.Synonymssrc(wi):Synonymsforwordwiaccoringtoagivendictionary.sik:kthwordinsentencesiIntheirsecondapproach,Hanetal.usepartofspeechtagstoevaluatethegrammaticalcompat-ibilityofasentencepair([45]).First,theymanuallymapcommonPOStagsofthetwolanguages(e.g.,thefinounflPOStaginEnglishismappedtothefinounflPOStaginChinese).Foragivensentencepair,thenumberofoccurrencesofeachsourcetaganditstargetcounterparttagiscal-culated.Theirdistanceiscomputedusingtheratioofthesmallercounttothelargercount.Aweightedaverage25ofthedistancemeasuresforallcommontagsisusedtocalculatethecross-lingualgrammaticalcompatibility(Equation3.35).25Theweightsaretrainedusingamanuallyanalyzeddevelopmentsetofsize1000.39f19(si;ti)=åtagltagmin(Count(si;tag);Count(ti;tag))+1max(Count(si;tag);Count(ti;tag))+1(3.35)3.6FeatureCombinationandParameterTuningSomedataselectionscenariosandscoringfunctionsrequireparametertuning.1.Scoringfunctionparameter(s):Somescoringfunctionscontainaparameterthatneedstobetuned(e.g.,[45]).2.FeatureCombination:Sincedifferentscoringfunctionscapturedifferentaspectsofthedata,itisoftendesirabletocombinemorethanonefunctionfordataselection.Forthispurposeacombinationmodel(e.g.,linear)isrequiredalongwithanalgorithmtooptimummodelparameters(e.g.,[52]).3.Thresholdtuning:Dataselectionmethodsthatuseathresholdtodata,requirethethresholdparametertobetuned(e.g.,[32]).Acommonrequirementforparametertuningandfeaturecombinationistheavailabilityofadevelopmentset.Inasupervisedlearningscenario,humanannotatorsareusedtocreatethedevelopmentset.Forexample,Hanetal.usehumanannotatorstolabelsentencepairsasliteraltranslationsversusconceptualtranslationstocreateadevelopmentset.Sincethisisanexpensiveandtimeconsumingtask,alternativetechniquesfordevelopmentdatacreationinsemi-supervisedlearningmethodshavebeendeveloped([52,95,7]).1.Mixingcleanandnoisydata:Intheirwork,KhadiviandNeyaddnoisydatatocleandata(labeledaccordingly)asthedevelopmentsettotraintheirnoisealgorithm.2.SinglePassActiveLearning:Intheirefforttotrainweightsforapairwisesentencecom-parator,Ananthakrishnanetal.useaparallelcorpusorderedbyTER26(between26TER:TranslationEditRate[90]40referencetranslationsandtranslationsofdecoderusingmodelstrainedonseedcorpus)astheirdevelopmentset([6]).Haffariusesasimilarmethodtogenerateadevelopmentsettotraintheirfeaturecombinationmodelweights([43]).3.UsingSelectionPool:Denkowskietal.usethecandidateselectionpoolofsentencestocomputeoutlierdetectionparameters([32]).Theycalculateaverageandstandarddeviationontheselectionpoolforanumberoffeatures(e.g.,sentencelengthratioandalphanumericdensity)tooutoutliers.3.7SelectionAlgorithmsGivenaconstrainedoptimizationproblemformulation,consistingofscoringfunctions,acombi-nationmodelandsizeconstraints,aselectionalgorithmisusedtosolvetheoptimizationproblem.3.7.1ThresholdBasedFilteringAcontextindependentfunctioncanbecomputedforallsentencepairsinonepassandthesubsetoftrainingdatathatpassesacertainthresholdcanbeselectedinlineartime.MethodsthatdependonathresholdtunethethresholdpriortoForexample,Denkowskietal.setsthethresh-oldsforlengthbasedatavg(sN1)2stddev(sN1).Otherselectionmethodswithcontextindependentscoringfunctionsiterativelyselecthighestscoringfunctionsuntiltheconstraintismet.ThesemethodsrequirethesentencestobesortedpriortoForalineartime,radixsortcanbeused.TheworkofMooreandLewisisanexampleofconstraintbasedassentencesaresortedbasedontheircross-entropydifferencebeforetheisapplied.Clas-basedapproachessuchas[95,52]followthesameparadigm.Sincetheseapproachescombinemultiplefeatures,theytrainaonadevelopmentsetandthenapplythetotheselectionpooltolabelsentencesasselectedversusnotselected,orcleanversusnoisy.413.7.2GreedySearchTheselectionmethodformostmethodswithcontextdependentscoringfunctionsisgreedysearch.Thehighestscoringsentenceisselectedineachiterationandthemodelsusedforthescoringfunctionsareupdated.Thisprocessisrepeateduntilaconstraint(e.g.,thetotalnumberofwordsinselectedpooloraminimumqualitybar)ismet.[33],[44]and[6]areexamplesofthisselectionmethod.Duetohighcomputationalcomplexity,forpracticalpurposes,greedyselectionalgorithmsareoftenpairedwithbatch-learningtechniques(seeSection3.9).3.7.3SubmodularOptimizationKirchhoffandBilmeshaverecentlyintroducedsubmodularityfordataselectioninstatisticalma-chinetranslation([53]).Submodularfunctionsareaclassofsetfunctionsthatformalizethecon-ceptoffidiminishingreturnsfl.Thismakesthemanaturaltheoreticalframeworkfordataselection.Formally,afunction,F,iscalledsubmodularifaddinganinstancextoasetSincreasesF(S)morethan(orequal)ifitwasaddedtoasupersetofS,SˆS0(Equation3.36).F(S[fxg)F(S)F(S0[fxg)F(S0)(3.36)Ingeneral,solvingEquation3.4exactlyisNP-complete.However,ifthesetfunctionFissubmodulartheproblemcanbesolvedusingagreedyalgorithmwithworst-casesolutionofF(X)>(11=e)f(Xopt).Thatis,intheworstcase,thefunctionvalueforthesolutionfromthegreedyalgorithmisapproximately0:63oftheoptimumsolution[53].Moreover,dependingonthecurvatureofthesubmodularfunction,theworstcaseguaranteecanbeimproved.Graphbasedsubmodularfunctionsareanaturalfordataselectionaseachsentenceisrepresentedasanodeinthegraphandedgeweightsarecomputedbasedonthesimilarityofthetwosentences.Theorderofgraphconstructioncomplexityisquadraticinthenumberofsentences.Thismakesthisclassofsubmodularfunctionsimpracticalforlargedatasets.AnotherclassofsubmodularfunctionsthataremorepracticalforlargedatasetsisbasedonbipartitegraphsG=(V;U;E;w).Inthissetting42sentencesaretheleftvertices,V.Features(e.g.,n-grams)aretherightvertices,U,withweightw.Connectingeachsentencetoitsfeaturesaddsuptothesetofedges,E.Inthissetting,KirchhoffandBilmesafeature-basedsubmodularfunctionasfollows.f(X)=åu2Uwufu(mu(X))(3.37)Assumingwutobepositive,mu(X)tobeanon-negativemodularfunction27andfutobeanon-negative,non-decreasingconcavefunction,F(X)asinEquation3.37issubmodular.Thisisaxibleframeworkfordataselectionthatisscalabletolargedatasizes.Usingthisframeworkrequiresthecomponentsbelow:1.U:Uisthesetoffeaturespresentinallsentencesintheselectionpool.N-gramsareanaturalchoiceforthis.2.mu(x):Thisfunctioncalculatestherelevanceofeachfeatureutosentencex.KirchhoffandBilmesusetfidf(u;x)forthisfunction.Themainconstraintwiththisfunctionisthatithastobemodular.3.w(u):Eachfeaturecanhaveaweightfunctiontopresentitsimportance.Inadomain-adaptationtask,thefrequencyofthen-graminanin-domaindevelopmentsetcanbeusedforthisweightfunction.4.fu(a):Thisdecayfunctiondeterminestherateofdiminishingreturnsforredundantinstancesofafeatureu.Asthisconcavefunctionbecomesthefeaturelosesitsabilitytoprovideadditionalimprovementtothevalueofacandidatesubset.KirchhoffandBilmesexperimentwithsquarerootandlogarithmicfunctions.ThegreedyalgorithmproposedbyKirchhoffandBilmesissimilarthegreedyalgorithmsmen-tionedinSection3.7.2.Theiralgorithmchoosesthesentenceinthesentencepoolthat,ifaddedto27Asetfunctionismodularifandonlyifthevalueofthefunctionoverasetequalsthesumofthefunctionvalueoveritsindividualelements.43theselectedsentences,improvesthesubmodularfunction'svalueovertheselectedsentencesthemost.Thisstepisrepeateduntilthebudgetconstraintismet.3.8ActiveLearningActivelearningisatechniqueusedinmachinelearningwherethealgorithmcanchoosethenewdatafromwhichitlearns[88].Thistechniqueisoftenemployedinproblemswhereunlabeleddataisabundantwhiletheprocessofobtaininglabeleddataisexpensiveortime-consuming.Inanactivelearningframework,thelearningalgorithmqueriesanoracle28fornewdatapointstobelabeled.First,thelearningalgorithmcanobtainnewdatapointsinseveralways.1.PoolBased:Thelearningalgorithmselectsdatapointsfromapoolofunlabeleddata.2.StreamBased:Allavailableunlabeleddataisstreamedthroughthelearningalgorithmandthelearningalgorithmcanchoosetoqueryforthedatapointordiscard.3.QuerySynthesis:Thelearningalgorithmgeneratesnewdatapointstobelabeledbytheoracle.ThelearningalgorithmcanuseseveralstrategiesforselectingnewdatapointssuchasUncer-taintySampling,QuerybyCommittee,ExpectedModelChange,ExpectedErrorReduction,Vari-anceReductionandDensity-WeightedMethods([88]).Activelearningselectsnewdatapointsinaniterativeprocess.Ineachstep,itselectsnewdatapoint(s),queriestheoracleforthelabelandlearnsfromtheresults.Incontrast,inpassivelearning,thelearningalgorithmhasnocontributiontothedataselectionandlabelingprocess.Fromanotherperspective,inpassivelearningthedataselectionprocessdoesnotusethelearningalgorithmtoselectnewdatapointsforlabeling.Al-though,thedataselectiontaskforpassivelearningcanalsobeiterative,thekeydistinctionisthatthelearningalgorithmdoesnotplayaroleinthedataselectiontask.28Anoraclecanbeahumanorahumanlabeleddatasetthatprovidesthetruelabelforaquery.Inthecontextofmachinetranslation,theoracleisahumantranslatororaparallelcorpuswherethesourcetexthasalreadybeentranslatedbyhumans.44Instatisticalmachinetranslationadataselectionmethodcanbeasanactivelearningmethodonlyifitfollowstheiterativedataselectionprocessdescribedabove.ContextDependentFunctionslistedinSection3.5.1thisparadigm.Inaddition,theselectionprocessmustuseanelementofstatisticalmachinetranslationlearningtobeconsideredactivelearning.Althoughonlysomepriorworkrefertotheirmethodasactivelearning[44,4,7],allscoringfunctionslistedinSections3.5.1.2,3.5.1.3and3.5.1.4theactivelearningframework.3.9Batch-ModeLearningBatch-modelearningisapplicabletobothactivelearningaswellasdataselectionforpassivelearning.Theideaistoselectnewdatapointsinbatchesratherthanoneatatime.Withoutbatch-modelearning,afterasingledatapointisselectedandlabeledbytheoracle,thelearningmodel(e.g.,LanguageModelorTranslationModel)orthedataselectionscoringfunctionstatistic(e.g.,n-gramfrequencyinselectedsentences)isupdatedwiththenewdatapoint,andalldatapointscoresarerecomputed.Thisprocesscanbeverytimeconsuming,especiallyifSMTmodelsneedtoberetrainedinordertorecomputedatapointscores.Batch-modelearningaddressesthisconcernbyselectingmultiplenewdatapointsatatimeandthereforereducingthenumberoftimesthelearningmodelhastobeupdatedandsentencescoresneedtoberecalculated.UsingthetopNsentenceswithhighestscoresoftendoesnotproducethebestresultssinceitfailstoconsideroverlapbetweendatapoints.Thisiscommonlyaddressedbyminimizingoverlapbetweendatapointswithinabatch.ToselectabatchofsizeK,Ananthakrishnanetal.gothroughthedataKtimes29([6]).Eachtimetheyselectthesentencewithmaximumscoreandupdatethescoringfunctiontoexcludefeatures(inthiscasen-grams)usedinscoringtheselectedsentences.InspiredbytheworkofDasguptaandHsuonHierarchicalSampling30,Haffarietal.pro-29Inthisbatch-modelearningstrategytheideaistoavoidretrainingallSMTmodelsafterselec-tionofeachsentence.Alessexpensiveupdateisusedtoimprovethediversityofthebatchwhereonlythescoringfunctionisupdated.Aftertheentirebatchisselected,thenallSMTmodelsareupdated.30HierarchicalSamplingattemptstoleveragetheclusterstructureofthedataforsamplinginan45poseHierarchicalAdaptiveSamplingforfeaturecombinationandbatch-learningatthesametime([43]).TheirworkdiffersfromHierarchicalSamplingbynothavingastatichierarchi-calclusterovertheselectionpool.Instead,thehierarchyiscreateddynamicallyinsteps.UnlikeHierarchicalSampling,theiralgorithmalwaysselectssamplesfromtheclusternodethathasbeenselectedforfurtherpartitioning.Ateachstep,Ksentencesarerandomlychosenfromtheselectedclusternodeandqueriedforhumantranslations.TheselectedsentencesareaddedtothesetofselectedsentencepairsandtheSMTmodelsareretrainedonthelargersetofselectedsentencepairs.Thetwopointsbelowareessentialtounderstandtherestofthisalgorithm.1.Choiceofclusterforfurtherpartitioning:AclusternodewithlowestaveragemodelscorewhentranslatedusingtheupdatedSMTmodelsischosenforfurtherpartitioning.2.Partitioningmechanismforachosenclusternode:Thesentencesinthepartitionaresortedaccordingtotheirsimilaritytotheselectedsentences.Theapercentageofthesen-tencesareputinthechildclusternode,andtherestinthesecondchildclusternode.Ineffect,HierarchicalAdaptiveSamplingiscombiningthefiaveragemodelscoreflfeaturewiththefisimilaritytotheselectedsentencesflfeature.Whilethefiaveragemodelscoreflfeatureselectstheclusterthatismostdiftotranslate,thefisimilaritytotheselectedsentencesflfeatureensuresdiversity.However,inpractice,thesetwofeaturescanbereplacedbymanyofthescoringfunctionsintroducedinSection3.5.Inadditiontoitshighcomputationalcomplexity,anothershortcomingofthisapproachisthatitdoesnotensurediversitywithinasinglebatch.Inafollowupactivelearningsetting([31]).Inthiswork,astatichierarchicalclusterstructureoftheunlabeleddataisgiven.Asetofclusternodesforsamplingismaintainedthroughoutthealgorithm.Initially,thesamplingsetonlycontainstherootnodeoftheclusterwhichcontainsallnodes.Randomsamplesaredrawnfromthesamplingsetandqueriedfromtheoracle.Basedonthesequeries,eachnodeinthehierarchicalclustermaintainsstatisticsaboutitspositiveandnegativelabels.Clusternodesinthesamplingsetwithmixedlabelsandmorepurechildnodesareremovedfromthesamplingsetandtheirchildnodesareadded.Thesestepsarerepeateduntilallnodesreachalevelofpurity.Thismethodismotivatedbyaddressingthefisamplingbiasflproblem([87])inactivelearningandprovidestheoreticalguaranteesforabetterlearningperformancethanrandomsampling.46totheirworkreferencedabove,Ananthakrishnanetal.introducethreelevelsofscoringfunctions([7]):1.NeverUpdated:Thesefunctionsareonlycomputedonceforsentencesintheselectionpoolandareneverupdated.Theyusen-gramoverlapwithanin-domaindevelopmentsetasameasureofdomainrelevanceforthispurpose.2.UpdatedPerBatch:Thesefunctionsareupdatedafterabatchofsentencesareselectedandqueriedforhumantranslation.TheycomputetranslationdifbyretrainingtheSMTmodelswiththenewbatchandderivetranslationdiffeaturesbasedontheperformanceofnewmodelsforthenextbatchofsentences.3.UpdatedPerSentence:Thesefunctionsarerecomputedeverytimeasinglesentenceisaddedtothepool.N-gramoverlapwithexistingsentencesinthebatch(batchdiversity)isusedforthispurposeandhastobeupdatedpersentence.Althoughonlybatchdiversityisrecomputedaftertheselectionofeachsentence,Ananthakrishnanetal.useallthreefunctionsabovetoselectthehighestscoringsentenceineachstep.Thisiscontinueduntilthebatchsizeisreached.3.10EvaluationMethodsAllpriorworkevaluatetheeffectivenessofdataselectionmethodsbytrainingonaselectedpar-allelcorpusandtestingonarandomlyheld-outtestset.Indataselectionfordomainadaptationscenarios([74,8]thetestsetisanin-domaintestset.Asformoststatisticalmachinetranslationtasks,BLEUisthemostcommonevaluationmethod.Whileinsomecasesselectingasubsetofthedataoutperformscasesusingtheentiredataset[53,33],thegeneraltrendisthatselectingmoredataimprovesevaluationresults.Forthisreason,comparisonbetweendifferentselectionmethodsisoftendonebyrunningeachselectionalgorithmmultipletimes.Eachtimetheselectionconstraint(e.g.,maximumnumberofwordsselected)issettoadifferentpercentageofthedata.47AnSMTsystemistrainedoneachselectedsubsetandtestedontheheld-outtestset.Thisprovidesseveralcomparisonpointsbetweentheselectionmethods.Theobjectiveincostfocusedselectionmethodsistomeetaqualitybaratminimumcost([19]).Inthesescenarios,differentselectionmethodsarecomparedbasedontheircosttoreachaBLEUscore.3.11ComparativeSummaryofCitedWorkTheworkofEcketal.isnoteworthyastheworkpublishedondataselectionforstatisticalmachinetranslation([33]).Featuresintroducedinthisworksuchasn-gramcoverageandtfidfarestillthebasisformuchofthemostrecentwork.ApracticalextensionoftheirworkistheVo-cabularySaturationFilter([66])whichrelaxesthedependencyonpreviouslyselectedsentences;thisallowsforlinear-timeapplicationofn-gramcoveragetoverylargedatasets.Anotherexten-siontotheworkofEcketal.isusingfeaturedecayfunctions([5,18])toimplementtheideaofdiminishingreturns.Whileintheiroriginalwork,Ecketal.maintainedn-gramcountstatistics,otherwork([44,68])usedlanguagemodelsformoreaccurateprobabilityestimationinstead.MooreandLewisintroducecross-entropydifferencewhichhasbecomeoneofthemostcom-monlyusedapproachesindataselectioninthedomainadaptationsetting[74].Bilingualcross-entropydifferenceisanaturalextensionofthisworkthattakesbothsidesoftheparalleldataintoconsideration([8]).TheworkofHaffarietal.isuniquelyobjectiveinthattheyusetheperformanceofatranslationsystemtrainedontheselecteddataintranslatingnewdataasameasureoftranslationdifandthustheusefulnessofnewdata([43]).Theirapproachtoactivelearningiscomputationallyintensive.Intheirextensiontothiswork,Ananthakrishnanetal.addressthecomputationalintensityproblembytrainingatocomparesentencesbasedontheirtranslationdif.InafollowupworktheycombinetheapproachesofEcketal.,MooreandLewisandHaffarietal.todevelopamulti-layeractivelearningstrategythatcombinestranslationdif,domainappropriatenessanddiversityintoasingleframework([7]).TheworkofKirchhoffandBilmesoffersthemosteffectivedataselectionsearchframework48withtheoreticalguarantees([53]).Althoughtheydonotintroduceanynewfeaturesintheirsub-modularoptimizationmethodfordataselection,theyofferaxibleframeworkwherecustomfunctionscanbeusedforsentencefeatures,relevancescores,featureweightsandadecayfunc-tion.TheworkofAmbatietal.isuniqueinthat,theyintroduceacustomizedactivelearningstrategyforcrowdsourcingwhileintroducingnewfeaturessuchasphrasalentropyandKL-divergence[4].BloodgoodandCallison-Burchofferacostfocusedactivelearningstrategybyaskingacrowdfortranslationofphraseswithinasentenceinsteadoffullsentencetranslation([19]).Usingthismethodtheyareabletooutperformallpreviousapproachesonaperwordtranslationpricingscheme.Taghipouretal.andKhadiviandNeyuseabasedapproachtooutnoisydatawhileDenkowskietal.usesimpleaverageandstandarddeviationstatisticstoachievethesamegoal([95,52,32]).Hanetal.haveauniqueapproachtodataselectionwheretheyuselexicalandsyntacticcom-patibilitybetweensourceandtargetsentencestoestimatetheliteralnessofthetranslation([45]).Theirideaistoselectmoreliteraltranslationsasastatisticalmachinetranslationsystemcanonlylearnfromliteraltranslationsandwouldnotfromfreetranslations.FinallytheworkofKauchakisuniqueastheyprovidethemostobjectivemeasureofsentencepairusefulnessforSMT,althoughtheirmethodisnotpracticalforanyreal-worldscenario([51]).Intheirwork,theycreate500randomsubsetsfromtheselectionpooltotrain500differentsetsofmodels.Theusefulnessofeachsentencepairisestimatedbasedonitsmembershipintrainingdatafordifferentmodelsetsandthemodelsets'performance.RelatedworksintheliteraturehavebeenlistedinTable3.2accordingtothemaincomponentsoftrainingdataselectionlisted.49ReferenceScenarioFeaturesAlgorithm[33]LowResourceLanguage31N-gramCoverageTF-IDFGreedySearch[44]LowResourceLanguageRoundTripTranslationAccuracyPhrasePairUtilityN-gramUtilityN-gramCoverageDecoderTranslationModelScoreGreedySearchHAS32[71]LowResourceLanguageInter-SystemDisagreementLanguageModels'PerplexityRatioGreedySearchThresholdFiltering[61]DomainAdaptationTF-IDFThresholdFiltering[95]NoiseReductionWordAlignmentProbabilityWordtoNullAlignmentCountWordtoNullAlignmentRatioAlignmentEntropyTop-3WordFertilitiesFactoidCo-AppearanceSentenceLengthRatioLMProbabilityDifferenceLMProbabilityRatio[32]NoiseReductionLanguageModelScoreCombinedAlignmentScoreLengthRatioAlphanumericIntensityMaximumTokenLengthThresholdFiltering[6]LowResourceLanguageExpectedTranslationErrorReductionGreedySearch[45]NoiseReductionLexicalCompatibilityGrammaticalCompatibilityThresholdFiltering[104]TrainingResourceReductionTF-IDFSubmodularOpt.[69]TrainingResourceReductionWeightedPhraseEntropyWeightedSub-treeEntropyGreedySearch[74]DomainAdaptationCrossEntropyDifferenceThresholdFiltering[27]TrainingResourceReductionN-gramCo-OccurrenceGreedySearch[9]DomainAdaptationCrossEntropyDifferenceThresholdFiltering[40]TrainingResourceReductionAverageAlignmentProbabilityGreedySearch[4]LowResourceLanguagePhraseProbabilityUnseenN-gramsGreedySearch[52]NoiseReductionSentenceLengthRatioAlphanumericCharacterPresenceSentenceEndingSymbolSimilarityAutomaticLanguageAlignmentProbability[19]QualityImprovementUnseenN-GramsThresholdFiltering[51]LowResourceLanguageEstimatedContributionScoreThresholdFilteringGreedySearch[80]NoiseReductionMinimumN-GramOccurrenceSentenceLengthGreedySearch[3]NoiseReductionLMPerplexityThresholdFiltering[108]DomainAdaptationLMPerplexityThresholdFiltering[34]QualityImprovementN-gramCo-OccurrenceGreedySearch[66]TrainingResourceReductionMinimumN-GramOccurrenceAlignmentProbabilityThresholdFilteringTable3.2RelatedWork503.12RelatedResearchAreasDataselectioninmachinetranslationiscloselyrelatedtoqualityestimation.Inaqualityestima-tiontask,givenasentenceanditstranslationusinganSMTdecoder,thequalityofthetranslationisestimatedwithoutareferencetranslation([91]).Thisisaverysimilartasktodataselection.Infactmanyfeaturesusedindataselectionhavebeeninspiredbyfeaturesusedinqualityestimation([32]).Dataselectionisapracticalmethodofadaptingstatisticalmachinetranslationmodelstoadomainandisoftenusedindomainadaptationtasks.Otherdomainadaptationtechniquesincludetranslationmodeladaptation([28]).Mostoftheactivelearningliteratureinmachinelearningisfocusedontaskswithalimitednumberoffeatures.Therefore,thefocusisonselectingdatapointsthataremostusefulinlearningfeatureweights.Activelearningformachinetranslationisuniqueinthatthenumberoffeaturestobelearnedisverylargeor,forallpracticalpurposes,unlimitedforlargedatasets.Theactivelearningtaskinthiscaseistoidentifydatapointswiththemostusefulfeaturesinadditiontodatapointsthatarethemostusefulinestimatingtheweightsforthefeatures.Thismakesactivelearningformachinetranslationuniqueintheactivelearningliterature.Co-trainingandself-trainingarealsocloselyrelatedareastodataselectionformachinetrans-lation([107,43]).Bothtechniquesareusedwhenlabeleddataisscarceandunlabeleddataisabundant.Inasimpleco-trainingsetting,twotrainedonlabeleddataclassifythesameunlabeleddatasetusingtwodifferentbutcomplimentaryfeaturesets.Iftheagreeintheirlabels,thedatapointsandtheirlabelsareaddedastrainingdataandareretrained.Inself-training,unlabeleddataislabeledusingasingleertrainedonthelimitedlabeleddata.Datapointswithhighareaddedtothetrainingasnewdatapoints.Thesetechniqueshavebeenleveragedindataselectionformachinetranslationaswell.Inhiswork,Haffariexperimentswithself-trainingwhiletheworkof[71]usesfeaturesthatareclosely31LowResourceLanguage32HierarchicalAdaptiveSampling51relatedtoco-training.Finally,anotherrelatedresearchareaismodelpruninginstatisticalmachinetranslation.Indataselectionscenarioswithmodelsizedeploymentconstraintsmodelpruningcanbeusedasanalternativetodataselection.Theresearchinthisareafocusesonphrasetablepruning([106])andlanguagemodelpruning([41]).3.13SummaryInpractice,performingadataselectiontaskforstatisticalmachinetranslationrequiresaddressingtwotechnicalquestions:1.ScoringFunction:Howisthevalueofasentenceorsentencepairobjectivelyevaluated?2.SelectionAlgorithm:Givenascoringfunctionandaconstrainthowistheoptimumdatasubsetselected?Inthischapterwereviewedalonglistofobjectivefunctionsalongwithanumberofselec-tionalgorithms.Thiscombinationoffersanoverwhelmingnumberofdifferenttoperformadataselectiontask.However,inpractice,thenumberofapplicablesolutionscanbenarroweddownbytheapplicationscenario(Section3.2)anddatasize.Multipledataselectionscenariosareoftenemployedinthedevelopmentofasinglestatisticalmachinetranslationsystem.Forexample,whendevelopingageneralpurposemachinetranslationserviceforEnglish$Frenchtherearethreedifferentissueswithtrainingdatathatcanbeaddressedusingdataselection.1.Muchoftheavailableparalleldataiscollectedthroughwebcrawlingandisnoisy.2.Thereistoomuchparalleldatatotrainanditerateoninatimelymanner([66]).3.Evenifwecouldtrainonallthedata,ifweweretodeploytheSMTsystemonanofmobiledevice,themodelsizesaretoolarge.52InthisscenariothedatacanbecleanedusingcontextindependentscoringfunctionslistedinEquation3.20-3.33andSection3.5.2.3.Investingincreatingadevelopmentsettotrainaclas-([95])wouldenabletrainingweightsformultiplescoringfunctions.Iffewscoringfunctionsareused,usingaverageandstandarddeviationforthresholdbased([32])canbeeffectiveaswell.Thenoiselevelofasentencepaircanbeestimatedindependentlyusingcontextindependentscoringfunctions.However,whenthereistoomuchcleandata,selectingasubsetofthedatathatcanperformthebestonablindtestsetismorecomplicated.Activelearningprovidesanidealsolutionasitisthemostobjective.OntheotherhanditrequiresretrainingafullSMTsystemoneveryiterationwhichmakesitimpracticalforlargedatasets.Activelearninginherentlyusescontextdependentscoringfunctionssinceitusesmodelsbuiltfromtheselectedpooltoevaluatenewsentencesfromtheselectionpool.Othercontextdependentscoringfunctions([33])usein-crementalstatisticsfromtheselectedpooltoscorenewsentencesintheselectionpool.Ageneralandefframeworkfortheuseofcontextdependentscoringfunctionsissubmodularopti-mization([53]).ForverylargedatasetsthatacomputationalcomplexityofO(NlogN)isnotpractical,VSF33([66])offersalinearsolution.Thedeploymentresourcerestrictionscenarioissimilartotrainingresourcelimitationscenariowiththeexceptionthatphrasetableorlanguagemodelpruningisaviablealternativetodataselection.AnothercommonscenarioforthedataselectiontaskinSMTisdevelopinganSMTsystemforlowresourcelanguages.Inthisscenariothereisasmallparallelseedcorpusandalargemonolingualselectionpool.Theideaistoselectalimitednumberofsentencesfromtheselectionpooltobemanuallytranslatedbyhumansandaddedtotheseedcorpus.Inthisscenarioactivelearningstrategieshaveprovedtobethemostsuccessful([7,4,44].TheactivelearningstrategiescanbeusedwithanyofthecontextdependentscoringfunctionsreviewedinSection3.5.1whilebatch-modelearningstrategiesreviewedinSection3.9canbeusedtospeedupthedataselectionprocess.33VSF:VocabularySaturationFilter([66])53CHAPTER4TRANSLATIONDIRECTIONDETECTIONThegoalofthisdissertationistoselectasubsetofparalleltrainingdatathatresultsintrans-lationmodelsthatyieldhighestqualitytranslationoutput.AsdescribedinChapter3thistaskisoftenbrokendowntosentencelevelfeaturefunctions.Byaselectedparalleldatasubsetcannotbeimmediatelyandindependentlyevaluatedwithoutrelyingonthedownstreamtranslationmodeltrainingtaskandtestset.Thedownstreamtaskitselfcantakeonmanyvariations(e.g.,trainingaphrasebasedsystem[109]versushierarchicalphrasedbasedtranslationmodel[29]ortree-to-stringtranslationmodel[85])withmanytuningparameters(maximumphraselength,max-imumdistortion,pruningparameters,...)inadditiontothechoiceofdevelopmentsetandturningmethod(e.g.,PRO[47],MERT[79]orMIRA[102]).Finally,therearedifferentevaluationmeth-ods(BLEU[83],METEOR[12]orhumanevaluation[83]).Inadditiontoallvariationsintrainingastatisticalmachinetranslationsystem,thetrainingprocessisalsocomputationallyintensive.Theaforementionedfactorsmakesanobjective,fairandaccuratecomparisonbetweenawiderangeoffeaturefunctionsintractable.Thereforeinthischapterweselectedataskforparalleldatathatcanbeobjectively,independentlyandaccuratelyevaluatedwithouttheneedforaanydownstreamtask.Thisenablesustoexploreawiderangeofsentencepairfeaturefunctionsindifferentsettings(samedomainversuscross-domain)andaccuratelymeasuretheireffectiveness.Theonlytaskthatmeetsthecriteriamentionedaboveisthe"TranslationDirectionDetection"task.Inthischapter,wethetask,reviewrelatedwork,introducearangeofnewfeaturesandeval-uatetheireffectivenessinanexistingdataset.Inaddition,wedevelopathreewaycross-domaindatasetandevaluatetheeffectivenessofpreviouslyintroducedfeaturesaswellasnewfeatureinthiscross-domainsetting.ThebestperformingfeaturesareusedinChapter5andChapter??toimprovetheperformanceofthedataselectiontaskforstatisticalmachinetranslation.544.1IntroductionIthasbeenknownformanyyearsinlinguisticsthattranslatedtexthasdistinctpatternscomparedtooriginalorauthoredtext[11].ThetermfiTranslationeseflisoftenusedtorefertothecharacteristicsoftranslatedtext.PatternsofTranslationesecanbecategorizedasfollows[101]:1.:Theprocessoftranslationisoftencoupledwithaprocessatseverallevels.Forexample,theretendstobelesslexicalvarietyintranslatedtextandrarewordsareoftenavoided.2.Explicitation:Translatorsoftenhavetobemoreexplicitintheirtranslationsduetolackoftheculturalcontextthatspeakersofthesourcelanguagehave.Anothermanifestationofthispatternismakingargumentsmoreexplicitwhichcanbeobservedintheheavyuseofcohesivemarkerslikefithereforeflandfimoreoverflintranslatedtext[59].3.Normalization:Translatedtextoftencontainsmoreformalandrepeatinglanguage.4.Interference:Atranslatorislikelytoproduceatranslationthatisstructurallyandgrammat-icallyclosertothesourcetextortheirnativelanguage.InFigure4.1thesizeofawordinthefiTranslatedflsectionisproportionaltothedifferencebetweenthefrequencyofthewordinoriginalandinthetranslatedtext[37].Forexample,itisapparentthatthewordfitheflisover-representedintranslatedEnglishasnotedbyotherresearch[101].Inaddition,cohesivemarkersareclearlymorecommonintranslatedtext.InthepastfewyearstherehasbeenworkonmachinelearningtechniquesforidentifyingTrans-lationese.StandardmachinelearningalgorithmslikeSVMs[13]andBayesianLogisticRegression[59]havebeenemployedtotrainforoneofthefollowingtasks:i.Givenachunkoftextinalanguage,classifyitasfiOriginalflorfiTranslatedfl.ii.Givenachunkoftranslatedtext,predictthesourcelanguageofthetranslation.iii.Givenatextchunkpairandtheirlanguages,predictthedirectionoftranslation.55Figure4.1EuroParlWordCloudDataVisualization(TranslatedvsOriginal)1Inadditiontoourstatedmotivationofexploringtheeffectivenessofdifferentfeaturefunctionsinparalleldatacltherearetwomotivationsstatedinpriorresearchforthetasksabove:empiricalvalidationoflinguistictheoriesaboutTranslationese[101],andsecond,improvingstatisticalmachinetranslationbyleveragingtheknowledgeofthetranslationdirectionintrainingandtestdata[63,65,64].FewparallelcorporaincludingacustomizedversionofEuroParl[48]andaprocessedversionofHansard[60]arelabeledfortranslatedversusoriginaltext.Usingtheselimitedresources,ithasbeenshownthattakingthetranslationdirectionintoaccountwhentrainingastatisticalmachinetranslationsystemcanimprovetranslationquality[65].However,improvingstatisticalmachinetranslationusingtranslationdirectioninformationhasbeenlimitedbyseveralfactors.1.LimitedLabeledData:Theamountoflabeleddataislimitedbylanguageanddomainandthereforebyitselfisnotenoughtomakeaimprovementinstatisticalmachinetranslation.2.Cross-DomainScalability:CurrentmethodsofTranslationesedetectiondonotscaleacross1ThiswordcloudwascreatedusingthewordcloudandtmRpackages[37]fromEuroParlparalleldataannotatedfortranslationdirection[48]obtainedfromhttp://www.hucompute.org/ressourcen/corpora/56.56differentcorpora.Forexample,atrainedonEuroParlcorpus[56]hadin-domainaccuracyof92.7%butout-of-domainaccuracyof64.8%[59].3.TextChunkSize:ThereportedhighaccuracyofTranslationesedetectionisbasedonrela-tivelylarge(approximately1500tokens)textchunks[59].Whensimilartasksareperformedatthesentenceleveltheaccuracydropsby15percentagepointsormore[60].Figure4.2showshowdetectionaccuracydropswiththereductionoftheinputtextchunksize.Sinceparalleldataareoftenavailableatthesentencelevelorsmallchunksoftext,existingdetec-tionmethodsaren'tsuitableforthistypeofdata.Figure4.2EffectsofChunkSizeonTranslationeseDetectionAccuracy2Motivatedbytheselimitationsandtheaforementionedgoalofthischapter,inthisworkwefocusonimprovingsentence-levelaccuracybyusingbilingualfeaturesatthesentencelevel.Inadditiontoimprovingaccuracy,thesefeaturesmaybebetterabletoexistingtheoriesordiscovernewlinguisticphenomenathatoccurinthetranslationprocess.Weuseafastlineartrainedwithonlinelearning,VowpalWabbit[62].TheHansardFrench-Englishdataset[60]isusedfortrainingandtestdatainallexperiments.2ThisisareproductionoftheresultsofKoppelandOrdan[59]usingfunctionwordfrequenciesasfeaturesforalogisticregression.Basedonthedescriptionofhowtextchunkswerecreated,theresultsofthepaper(92.7%accuracy)arebasedontextchunksizesofapproximately1500tokens.574.2RelatedWorkVolanskyetal.[101]provideacomprehensivelistofmonolingualfeaturesusedforTranslationesedetection.ThesefeaturesincludePOSn-grams,charactern-grams,functionwordfrequency,punc-tuationfrequency,meanwordlength,meansentencelength,wordn-gramsandtype/tokenratio.WhiledistinctpatternsofTranslationesehavebeenstudiedwidelyinthepast,theworkofBaroniandBernardini[13]isthetointroduceacomputationalmethodfordetectingTranslationesewithhighaccuracy.Priorworkhasshownin-domainaccuracycanbeveryhighatthechunk-leveliffullylexicalizedfeaturesareused[101],butthenthephenomenalearnedareclearlynotgener-alizableacrossdomains.Forexample,inFigure4.1,itcanbeobservedthatcontentwordslikeficommissionfl,ficouncilflorfiunionflcanbeusedeffectivelyforwhiletheydonotcaptureanygenerallinguisticphenomenaandareunlikelytoscaletoothercorpora.Thisisalsobyanaveragehumanperformanceof72.7%precisionwith82.1%recallonasimilartaskwherethetestsubjectswerenotfamiliarwiththedomainandwerenotabletousedomain-lexicalfeatures[13].Amoregeneralfeaturesetstillwithhighin-domainaccuracyisPOStagswithlexicalizationoffunctionwords[13,60].Webuildonthisfeaturesetandexplorebilingualfeatures.Weareawareofonlyonepriorworkthatpresentedacross-domainevaluation.KoppelandOrdan[59]usealogisticregressionwithfunctionwordunigramfrequenciestoachieve92.7%accuracywithtenfoldcrossvalidationontheEuroParl[56]corpusand86.3%ontheIHTcorpus.HowevertestingtheEuroParltrainedontheIHTcorpusyieldsanaccuracyof64.8%(andtheaccuracyis58.8%whentheistrainedonIHTandtestedonEuroParl).Theinthisstudyaretrainedandtestedontextblocksofapproximately1500tokens,andthereisnocomparativeevaluationofmodelsusingdifferentfeaturesets.WearealsoawareofonepriorworksthatinvestigateTranslationesedetectionaccuracyatthesentencelevel.Kurokawaetal[60]usetheHansardEnglish-Frenchcorpusfortheirexperiments.ForsentenceleveltranslationdirectiondetectiontheyreachF-scoreof77%usingwordn-gramsandstayslightlybelow70%F-scorewithPOSn-gramsusinganSVM.Thisisalso58theonlyworktoconsiderfeaturesofthetwoparallelchunks(oneoriginal,onetranslated).Theysimplyusedtheunionofthen-grammixed-POS3featuresofthetwosides;thesearemonolingualfeaturesoftheoriginalandtranslatedtextanddonotlookattranslationphenomenadirectly.Theirworkisalsotheonlyworktolookatsentenceleveldetectionaccuracyandreport15percentagepointsdropinaccuracywhengoingfromchunkleveltosentencelevelOurworkinthischapterisuniqueinseveralways:1)Weexploreseveralbilingualfeaturesnotexploredbefore,2)Weimproveonthebestresultsreportedforsentence-levelaccuracyand3)Wedevelopacross-domaindatasetandoutperformallpriormethodsinallcross-domainsettings.4.3BilingualFeaturesforTranslationDirectionWeareinterestedinlearningcommonlocalizedlinguisticphenomenathatoccurduringthetrans-lationprocesswhentranslatinginonedirectionbutnottheother.4.3.1POSTagMTUsMinimaltranslationunits(MTUs)forasentencepairareaspairsofsourceandtargetwordsetsthatsatisfythefollowingconditions[84,111].1.NoalignmentlinksbetweendistinctMTUs.2.MTUsarenotdecomposableintosmallerMTUswithoutviolatingthepreviousrule.WeusePOStagstocapturelinguisticstructuresandMTUstomaplinguisticstructuresofthetwolanguages.ToobtainPOSMTUsfromaparallelcorpus,theparallelcorpusiswordaligned.Next,thesourceandtargetsideofthecorpusaretaggedindependently.Finally,wordsarereplacedwiththeircorrespondingPOStaginword-alignedsentencepairs.MTUswereextractedfromthePOStaggedword-alignedsentencepairsfromlefttorightandlistedinsourceorder.3OnlyreplacingcontentwordswiththeirPOStagswhileleavingfunctionwordsasis.59Unigram,bi-gram,andhigherordern-gramfeatureswerebuiltoverthissequenceofPOSMTUs.Forexample,forthesentencepairinFigure4.4,thefollowingPOSMTUswillbeextracted:VBZ)D,PRP)(N,V),RB)ADV,JJ)N,.)PUNC.4.3.2DistortionInadditiontothemappingoflinguisticstructures,anotherinterestingphenomenonisthereorder-ingoflinguisticstructuresduringtranslation.Onehypothesisisthatwhentranslatingfromaed-ordertoafree-orderlanguage,theorderofthetargetwillbeverybythesource(almostmonotonetranslation),butwhentranslatingintoaedorderlanguage,morere-orderingisrequiredtoensuregrammaticalityofthetarget.TocapturethispatternweadddistortiontoPOSTagMTUfeatures.Weexperimentwithabsolutedistortion(wordpositiondifferencebetweensourceandtargetofalink)aswellasHMMdistortion(wordpositiondifferencebetweenthetar-getofalinkandthetargetofthepreviouslink).Webinthedistortionsintothreebins:fi=0fl,fi>0flandfi<0fl,toreducesparsity.4.4SingleDomainExperimentsForthetranslationdirectiondetectiontaskexplainedinsection4.1,weuseafastlineartrainedwithonlinelearning,VowpalWabbit[62].Trainingdataandfeaturesareexplainedinsection4.4.1and4.4.2.4.4.1DataForthistaskwerequireaparallelcorpuswithsentencepairsavailableinbothdirections(sentencesauthoredinlanguageAandthentranslatedtolanguageBandviceversa).WhilethecustomizedversionofEuroParl[48]containssentencepairsformanylanguagepairs,noneofthelanguagepairshavesentencepairsavailableinbothdirections(e.g.,itdoescontainsentencesauthoredinEnglishandtranslatedintoFrenchbutnotviceversa).TheCanadianHansardcorpusontheother60Figure4.3Sentenceleveltranslationdirectiondetectionprecisionusingdifferentfeatureswithn-gramlengthsof1through5.handtherequirementasithas742,408sentencepairstranslatedfromFrenchtoEnglishand2,203,504sentencespairsthatweretranslatedfromEnglishtoFrench[60].WeusetheHansarddatafortrainingFortrainingtheHMMwordalignmentmodelusedtofeatures,weusealargersetoftenbillionwordsofparalleltextfromtheWMTEnglish-Frenchcorpus.4.4.2PreprocessingandFeatureExtractionWeusedalanguage4,deduplication5andlengthratiotocleanthedata.Afterwewereleftwith1,890,603English-Frenchsentencepairsand640,117French-Englishsentencepairs.TheStanfordPOStagger[96]wasusedtotagtheEnglishandtheFrenchsidesofthecorpus.TheHMMalignmentmodel[100]trainedonWMTdatawasusedtoword-aligntheHansardcorpuswhilereplacingwordswiththeircorrespondingPOStags.DuetodifferencesinwordbreakingbetweenthePOStaggertoolandourwordalignmenttoolthereweresomemis-matches.Forsimplicitywedroppedtheentiresentencepairwheneveratokenmismatchoccurred.Thisleftuswith401,569POStagalignedsentencepairsintheFrenchtoEnglishdirectionand4Acharactern-gramlanguagemodelisusedtodetectthelanguageofsourceandtargetsidetextandthemoutiftheydonotmatchtheirannotatedlanguage.5Duplicatesentencespairsareout.611,184,702pairsintheotherdirection.Wechosetocreateabalanceddatasetandreducedthenum-berofEnglish-Frenchsentencesto401,679with20,000sentencepairsheldoutfortestingineachdirection.POSMTU(E)F)FE#EF#Example1NNPS)(N,C)33612quebecers(NNPS))québécoises(N)et(C)desquébécois2IN)(CL,V)691027afewdaysago(IN))ily(CL)a(V)quelques3PRP)(N,V)18663he(PRP)is)ledéputé(N)à(V)4(NNP,POS))A15528quebec(NNP)'s(POS)history)histoirequébécoises(A)5(FW,FW))ADV7195pro(FW)bono(FW)work)bénévolement(ADV)travailler6(RB,MD))V2112moneyalone(RB)could(MD)solve)argentsufV)àrésoudreTable4.1POSMTUfeatureswithhighestweight.FE#indicatesthenumberoftimesthisfeatureappearedwhentranslatingfromFrenchtoEnglish.64.4.3ResultsTheresultsofourexperimentsonthetranslationdirectiondetectiontaskarelistedinTable4.5.Wewouldliketopointoutseveralresultsfromthetable.First,whenusingonlyunigramfeatures,thehighestaccuracyisachievedbythefiPOS-MTU+HMMDistortionflfeature,whichusesPOSminimaltranslationunitstogetherwithdistortion.ThehighestaccuracyoverallifobtainedbyafiPOS-MTUfltrigrammodel,showingtheadvantageofbilingualfeaturesoverpriorworkusingonlyaunionofmonolingualfeatures(reproducedbythefiEnglish-POS+French-POSflration).Whilehigherorderfeaturesgenerallyshowbetterin-domainaccuracy,theadvantageoflow-orderbilingualfeaturesmightbeevenhigherincross-domain4.4.4AnalysisAninterestingaspectofthisworkisthatitisabletoextractfeaturesthatcanbelinguisticallyinterpreted.Althoughlinguisticanalysisofthesefeaturesisoutsidethescopeofthiswork,welistPOSMTUfeatureswithhighestpositiveornegativeweightsinTable4.1.Althoughthetopfeature,6FordescriptionofEnglishPOStagssee[73]and[1]forFrench62LabelDescriptionENU.LEXEnglishwordn-gramsFRA.LEXFrenchwordn-gramsENU.POSEnglishPOSTagn-gramsFRA.POSFrenchPOSTagn-grmasENU.BCEnglishBrownClustern-gramsFRA.BCFrenchBrownClustern-gramsPOS.MTUPOSMTUn-gramsBC.MTUBrownClusterMTUn-gramsTable4.2featuresandtheirlabels.NNPS)(N,C)7,inthiscontextisoriginatingfromacommonphraseusedbyFrenchspeakingmembersoftheCanadianParliament,québécoisesetdesquébécois,itdoeshighlightanunderlyinglinguisticphenomenonthatisnottotheCanadianParliament.WhentranslatingapluralnounfromEnglishtoFrenchitislikelythatonlythemasculineformofthenounappears,whileifitwasauthoredinFrenchwithbothformsofthenouns,asinglepluralnounwouldappearinEnglishasEnglishdoesn'thavemasculineandfeminineformsoftheword.AmorecompleteformofthisfeaturewouldhavebeenNNPS)(N,C,N),butsincewordalignmentmodels,ingeneral,discourageone-to-manyalignments,theextractedMTUonlycoversthenounandconjunction.4.5Cross-DomainExperimentsThegoalthissectionistocomparenovelandpreviouslyintroducedfeaturesinacross-domainsetting.Duetothevolumeofexperimentsrequiredforcomparison,foraninitialstudy,weselectalimitednumberoffeaturesetsforcomparison.PriorworksclaimPOSn-gramfeaturescapturelinguisticphenomenaoftranslationandshouldgeneralizeacrossdomains[60].WechosesourceandtargetPOSn-gramfeaturesforn=1:::5totestthisclaim.Anotherfeaturewehavechosenisthebestperformingfeaturefromsingledomainexperiments:POSMTU8n-gramfeatures.POSMTUsincorporatesourceandtargetsideinformationinadditiontowordalignment.Priorworkhasalsoclaimedlexicalfeaturessuchaswordn-gramsdonotgeneralizeacrossdomainsdueto7NNPS:PluralNoun,N:Noun,C:Conjunction8MinimalTranslationUnits[84]63CorpusAuthoredLanguageTranslationLanguageTrainingSentencesTestSentencesEuroParlEnglishFrench62k6kEuroParlFrenchEnglish43k4kHansardEnglishFrench1,697k169kHansardFrenchEnglish567k56kHansard-CommitteesEnglishFrench2,930k292kHansard-CommitteesFrenchEnglish636k63kTable4.3Cross-DomainDataSetscorpusvocabulary[101].Wetestthishypothesisusingsourceandtargetwordn-gramfeatures.Usingn-gramsoflength1through5werun45(Ninedatamatrixentriestimesn-gramlengthsofve)experimentsforeachfeaturesetmentionedabove.Inadditiontothefeaturesmentionedabove,wemakeasmalltothefeatureusedtoobtainthebestsingledomainsentencelevelperformancetoderiveanewtypeoffeatures.WeintroduceBrowncluster[22]MTUsinstead.OuruseofBrownclustersisinspiredbyrecentsuccessontheiruseinstatisticalmachinetranslationsystems[15].Finally,wealsoincludesourceandtargetBrownclustern-gramsasacomparisonpointtobetterunderstandtheireffectivenesscomparedtoPOSn-gramsandtheircontributiontotheeffectivenessofBrownclusterMTUs.Giventhese8featuretypessummarizedinTable4.2,n-gramlengthsofupto5andthe33datamatrixexplainedinthenextsection,werun360experimentsforthiscross-domainstudy.4.5.1DataMatrixWechosetheEnglish-Frenchlanguagepairforourcross-domainexperimentsbasedonpriorworkandavailabilityoflabeleddata.Existingsentence-paralleldatasetsusedfortrainingmachinetrans-lationsystems,donotnormallycontaingold-standardtranslationdirectioninformation,andaddi-tionalprocessingisnecessarytocompileadatasetwithsuchinformation(labels).Kurokawaetal[60]extracttranslationdirectioninformationfromtheEnglish-FrenchHansardparalleldatasetusingspeakerlanguagetags.Weusethisdataset,andtreatthetwosectionsfimainparliamentaryproceedingsflandficommitteehearingsflastwodifferentcorpora.Thesetwocorporahaveslightlydifferentdomains,althoughtheysharemanycommontopicsaswell.Weadditionallychoosea64Figure4.4POSTaggedandBrownClusterAlignedSentencePairsthirdcorpus,whosedomainismoredistinctfromthesetwo,fromtheEuroParlEnglish-Frenchcorpus.[48]providedacustomizedversionofEuroparlwithtranslationdirectionlabels,butthisdatasetonlycontainssentencesthatwereauthoredinEnglishandtranslatedtoFrench,anddoesnotcontainexamplesforwhichtheoriginallanguageofauthoringwasFrench.WethusprepareanewdatasetfromEuroParlandwillmakeitpubliclyavailableforuse.TheoriginalunprocessedversionofEuroParl[56]containsspeakerlanguagetags(originallanguageofauthoring)fortheFrenchandEnglishsidesoftheparallelcorpus.Weoutinconsistenciesinthecorpus.First,weoutsectionswherethelanguagetagismissingfromoneorbothsides.Wealsooutsectionswithlanguagetags.Parallelsectionswithdifferentnumberofsentencesarealsodiscardedtomaintainsentencealignment.Thisleavesuswiththreedatasets(twoHansardandoneEuroParl)withtranslationdirectioninformationavailable,andwhichcontainsentencesauthoredinbothlanguages.Weholdout10%ofeachdatasetfortestingandusetherestfortraining.Our33corpusdatamatrixconsistsofallninecombinationsoftrainingononecorpusandtestingonanother(Table4.3).4.5.2PreprocessingandFeatureExtractionSimilartopreprocessingstepsforsingledomainexperiments,wecleanalldatasetsusingthefollowingsimpletechniques.Sentenceswithlowalphanumericdensityarediscarded.Acharactern-grambasedlanguagedetectiontoolisusedtoidentifythelanguageofeach65sentence.Wediscardsentenceswithadetectedlanguageotherthantheirlabel.Wediscardsentenceswithinvalidunicodecharactersorcontrolcharacters.Sentenceslongerthan2000charactersareexcluded.Next,anHMMwordalignmentmodel[100]trainedontheWMTEnglish-Frenchcorpus[20]word-alignssentencepairs.Wediscardsentencepairswherethewordalignmentfails.WeusetheStanfordPOStagger[96]forEnglishandFrenchtotagallsentencepairs.AcopyofthealignmentwithwordsreplacedwiththeirPOStagsisalsogenerated.FrenchandEnglishBrownclustersaretrainedseparatelyontheFrenchandEnglishsidesoftheWMTEnglish-Frenchcorpus[20].TheproducedmodelsassignclusterIDstowordsineachsentencepair.WecreateacopyofthealignmentwithclusterIDsinsteadofwordsaswell.Theofourchoice(Section4.5.3)extractsn-gramfeatureswithnasanop-tion.Inpreparationfortrainingandtesting,featureextractiononlyneedstoproducetheunigramfeatureswhilepreservingtheorder(n-gramsofhigherlengthareautomaticallyextractedbythePOS,word,andBrownclustern-gramfeaturesaregeneratedbyusingtherespectiverepresen-tationforsequencesoftokensinthesentences.ForPOSandBrownclusterMTUfeatures,thesequenceofMTUsisastheleft-to-rightinsourceordersequence(duetoreordering,theexactenumerationorderofMTUsmatters).Forexample,forthesentencepairinFigure4.4,thesequenceofBrownclusterMTUsis:73)(390,68),208)24,7689)3111,7321)1890,2)16.4.5.3OnlineWechosetheVowpalWabbit[62](VW)onlinelinearsinceitisfast,scalableandithasspecial(bagofwordsandn-gramgeneration)optionsfortextWefoundthatVWwascomparableinaccuracytoabatchlogisticregression.Fortrainingandtestingthe,wecreatedbalanceddatasetswiththesamenumberoftrainingexamplesinbothdirections.ThiswasachievedbyrandomlyremovingsentencepairsfromtheEnglishtoFrench66Figure4.5ComparingareaundertheROCcurveforthetranslationdirectiondetectiontaskwhentrainingandtestingondifferentcorporausingeachoftheeightfeaturesets.SeeTable4.2forexperimentlabeldescription.directionuntilitmatchestheFrenchtoEnglishdirection.Forexample,636ksentencepairsarerandomlychosenfromthe2,930ksentencepairsinEnglishtoFrenchHansard-CommitteescorpustomatchthenumberofexamplesintheFrenchtoEnglishdirection.4.5.4EvaluationMethodWeareinterestedincomparingtheperformanceofvariousfeaturesetsintranslationdirectiondetection.Performanceevaluationofdifferentfeaturesobjectivelyischallengingintheabsenceofadownstreamtask.,dependingonthepreferredbalancebetweenprecisionandrecall,differentfeaturescanbesuperior.IdeallyanROCgraph[35]visualizesthetradeoffbetweenprecisionandrecallandcanserveasanobjectivecomparisonbetweendifferentfeaturesets.However,itisnotpracticaltopresentROCgraphsfor360experiments.Hence,weresorttotheAreaUndertheROCgraph(AUC)measureasagoodmeasuretoprovideanobjectivecomparison.Theoretically,theareaunderthecurvecanbeinterpretedastheprobability67Figure4.6Translationdetectionperformancematrixfortrainingandtestingonthreedifferentcorpora.Eachrowcorrespondstoresultsoftrainingonacorpuswhiletestresultsarelaidoutinacolumnofthe33matrix.UnlikeFigure4.5wherewereportAUCvaluesforalln-grams,inthisdiagramweonlyreportthehighestAUCvalueforeachfeature.Thenumbernexttoeachdatapointindicatesthen-gramlengththatachievesthehighestperformanceforthatfeature.SeeTable4.2forexperimentlabeldescription.thatthescoresarandomnegativeexamplehigherthanarandompositiveexample[35].Asapointofreference,wealsoprovideF-scoresforexperimentalsettingsthatarecomparabletothepriorworkreviewedinSection??.4.5.5ResultsFigure4.5presentsAUCpointsforallexperiments.Rowsandcolumnsarelabeledwithcorpusnamesfortrainingandtestdatasetsrespectively.Forexample,thegraphonthethirdrowandcolumncorrespondstotrainingontheHansard-CommitteescorpusandtestingonEuroParl.WithineachgraphwecomparetheAUCperformanceofdifferentfeatureswithn-gramlengthsof681through5.Graphsonthediagonaldemonstratehigherperformancecomparedtooffdiagonalgraphs.Thisthebasicassumptionthatcross-domaintranslationdirectiondetectionisamorediftaskasthegraphsonthediagonalcorrespondtoin-domaindetection.TheoverallperformanceisalsohigherwhentrainedontheHansardcorpusandtestedonHansard-Commiteeandviceversa.ThisisbecuasetheHansardcorpusismoresimilartotheHansard-CommitteescorpuscomparedtotheEuroParlcorpus.Itisalsoobservablethatthevariationinperformanceofdifferentfeaturesdiminishesasthetrainingandtestcorporabecomemoredissimilar.Forinstance,thisphenomenoncanbeobservedonthesecondrowofgraphswherethefeaturesaremostspreadoutwhentestedontheHansardcorpus.TheyarelessspreadoutwhentestedontheHansard-Committeescorpus,andcompressedtogetherwhentestedontheEuroParlcorpus.Thesamephenomenoncanbeobservedfortrainedonothercorpora.Fordifferentfeaturetypes,differentn-gramorderofthefeaturesisbest,dependingonthefea-turegranularity.Tomakeiteasiertoobservepatternsintheperformanceofdifferentfeaturetypes,Figure4.7showstheperformanceforeachfeaturetypeandeachtrain-testcorpuscombinationasasinglepoint,byusingthebestn-gramorderforthatfeature/datacombination.Eachofthe9train/testdatacombinationsisshownasacurveoverfeaturetypes.WecanseethatMTUfeatures(whichlookatbothlanguagesatthesametime)outperformindividualsourceortargetfeatures(POSorBrowncluster)foralldatasets.Brownclustersareunsupervisedandcanprovidedifferentlevelsofgranularity.Ontheotherhand,POStagsusuallyprovideaedgranularityandrequirelexiconsorlabeleddatatotrain.WeseethatBrownclustersoutperformcorrespondingPOStagsacrossdatasettings.Asanexample,whentrainingandtestingontheHansardcorpusFRA.BCoutperformsFRA.POSbycloseto20AUCpoints.LexicalfeaturesoutperformmonolingualPOSandBrownclusterfeaturesinmostsettingsalthoughtheiradvantagesdiminishasthetrainingandtestcorpusbecomemoredissimilar.ThisissomewhatcontrarytopriorclaimsthatlexicalfeatureswillnotgeneralizewellacrossdomainsŒweseethatlexicalfeaturesdocaptureimportantgeneralizationsacrossdomainsandmodelsthat69Figure4.7Translationdetectionperformancematrixfortrainingandtestingonthreedifferentcorpora-Weranexperimentsforn-gramsofuptolengthveforeachfeature(SeeTable4.2forfeaturelabeldescriptions).UnlikeFigure4.5wherewereportAUCvaluesforalln-gramlengths,inthisgraphweonlypresentthehighestAUCnumberforeachfeature.Eachmarkertypeindicatesatrainingandtestsetcombination.Theformatofexperimentlabelsinthelegendis[TrainingSet]-[TestSet]andEU:EuroParl,H:Hansard,HC:HansardCommittees.Forexample,EU-HCmeanstrainingonEuroParlcorpusandtestingonHansardCommitteescorpus.70useonlyPOStagfeatureshavelowerperformance,bothinandout-of-domain.Figure4.8showstherankofeachfeatureamongstall8differentfeaturesforeachentryinthecross-corpusdatamatrix(SimilartoFigure4.7thehighestperformingn-gramlengthhasbeenchosenforeachfeature).BrownclusterMTUsoutperformallotherfeatureswithrankoneinalldatasetcombinations.SourceandtargetPOStagfeaturesarethelowestperformingfeaturesin8outof9datasetcombinations.ThePOS.MTUhasitslowestranks(7and8)whenitistrainedontheEuroParlcorpusanditshighestranks(2and3)whentrainedontheHansard-Committeescorpus.HighnumberoffeaturesinPOS.MTUrequiresalargedatasetfortraining.ThevariationinperformanceforPOS.MTUcanbeexplainedbythedifferenceintrainingdatasizebetweenEuroParlandHansard-Committees.Finally,whileFRA.LEXandENU.LEXaremostlyinrank2and3(afterBC.MTU)theyhavetheirlowestranks(6and4)incorss-corpussettings(HC-EUandHC-H).Finally,wereportprecisionandrecallnumberstoenablecomparisonbetweenourexperimentsandpreviousworkreportedinSection4.2.WhentrainingandtestingontheHansardcorpus,BC.MTUachieves0.80precisionwith0.85recall.Incomparison,ENU.POSachieves0.65preci-sionwith0.64recallandPOS.MTUachieves0.73precisionand0.74recall.Thesearethehighestperformanceofeachfeaturewithn-gramsofuptolength5.4.6ConclusionandFutureWorkFromamongeightstudiedsetsoffeatures,BrownclusterMTUswerethemosteffectiveatidenti-fyingtranslationdirectionatthesentencelevel.Theyweresuperiorinbothin-domainandcross-domainsettings.AlthoughEnglish-LexicalfeaturesdidnotperformaswellasBrownclusterMTUs,theyperformedbetterthanmostothermethods.Infuturework,weplantoinvestigatelexicalMTUsandtoconsiderfeaturesetscontaininganysubsetoftheeightormorebasicfeaturetypeswehaveconsideredhere.Withtheseexperimentswehopetogainfurtherinsightintotheperformanceoffeaturesetsininoutout-of-domainsettingsandtoimprovethestate-of-the-artinrealistictranslationdirectiondetectiontasks.Additionally,weplantousethistoextend71Figure4.8TranslationdirectiondetectionAUCperformancerankforeachtrainingandtestsetcombination.ForcorpuscombinationabbreviationsseedescriptionofFigure4.7.ForfeaturelabeldescriptionsseeTable4.2.theworkofTwitto-Shmuel([97])bybuildingamoreaccurateandlargerparallelcorpuslabeledfortranslationdirectiontofurtherimproveSMTquality.72CHAPTER5EFFECTIVEANDEFFICIENTDATASELECTIONLackofaneffectiveandefdataselectionalgorithmisapparentfromtheliteraturereviewinChapter3.MosteffectivedataselectionmethodsinvolveretrainingafullsetofSMTmodelsateverystepofthedataselectionprocess(e.g.,[43,7]).Thesemethodsarebarelypracticalforsmalldatasetswith100Ksentencesintrainingdata,letalonemediumorlargedatasetswithoverfewmillionsentences.Thecontributionofmoreefmethodsisintwofolds:1)Introducingasurrogatefunction(e.g.,maximumnumberofunseentokentypescoveredwithminimumnum-berofsentences([33]))toeliminatetheneedforretrainingafullSMTsystemand2)providingamechanismtooptimizethesurrogateobjectivefunction(e.g.,GreedySearch,alsoin[33]).Inthischapterwechallengetheofachievingtheoptimumvalueforthesimplesurro-gatefunctiondescribedabovebyprovidingasimpleandefalgorithmthatachievessimilarresultsusingthesamesurrogatefunctionandalinearsearchalgorithmthatdoesnotprovideanytheoreticalguaranteesforachievingtheoptimumsolution.Werunexperimentsatseveraldatasetsizesandcompareitwithrandomselection.Inaddition,weexperimentwithdifferentorderingsofthedataandprovideexperimentalresults.5.1VocabularySaturationFilterThemostcommonfeaturefunctionthathasbeenusedwithsomevariations(seeChapter3)fordataselectioninstatisticalmachinetranslationisthenumberofnewn-gramsinasentencepair.Theobjectiveofthepreviouslyintroducedsearchalgorithms(e.g.,[33])istomaximizethenumberofuniquen-gramsinasubsetofthedatawithaconstraintonthetotalnumberoftokens.AsexplainedinChapter3thisisdoneusingagreedyalgorithmwiththecomplexityofO(jSSelectionPoolj2).Incontrastweproposealinearalgorithm,O(jSSelectionPoolj),thatachievescomparableresults.Aversionofthisalgorithm(VocabularySaturationFilterorVSF)ismakingasingle73passthroughthedataandselectingsentencepairssuchthatforalln-gramsthereisatleastoneselectedsentencethatcontainsthatn-gram.Thealgorithmwouldgothroughthesentencepairsinanarbitraryorderandonlyselectasentencepair,ifitcontainsanewn-gram.Toincreasethexibilityofthealgorithmweintroduceafiminimumoccurrenceflthreshold,t,whichisequaltooneinthealgorithmdescribedabove.Thealgorithmwillselectasentenceifandonlyifitcontainsatleastonen-gramthathasoccurredlessthanttimesintheselectedpool.TheimplementationofVSFisdescribedinAlgorithm1below.Input:SelectionPool,t,`Output:SelectedPoolforeachsp2SelectionPooldoNGsrc EnumNgrams(sp:src,`);NGtgt EnumNgrams(sp:tgt,`);selected false;foreachng2NGsrcdoifSrcCnt[ng]<tthenselected true;break;endendifnotselectedthenforeachng2NGtgtdoifTgtCnt[ng]<tthenselected true;break;endendendifselectedthenSelectedPool.Add(sp);foreachng2NGsrcdoSrcCnt[ng]++;endforeachng2NGtgtdoTgtCnt[ng]++;endendendAlgorithm1:PseudocodeforimplementingVSF.`:n-gramlength,t:n-gramthreshold,sp:sentencepair.745.2ComparisontonearOptimumSolutionAlthoughthefeaturefunctionfinumberofnewn-gramspersentenceflwasintroducedbyEcketal.,KirchhoffandBilmeshaveshownthefunctiontobesub-modularandhenceagreedysearchalgorithmguaranteesachievingconstantfactorapproximationoftheoptimumsolution([53,33]).SincethecomplexityofthegreedyalgorithmisO(jSSelectionPoolj2),itisimpracticalforlargedatasets.Thereforeweseektodiscoverwhethertheextracomplexityofnearoptimumsolu-tionimpactsthetranslationqualityoftheSMTsystemcomparedtousingalinearselectionalgorithmsuchasVSF.fj(sentence)=jån=124åunseenngramsFreq(ngram)35jsentencej(5.1)ForcomparisonthefeaturefunctioninEquation5.1,introducedbyEcketal.,isusedinthegreedysearchalgorithm.5.2.1ExperimentalSetupTocompareVSFagainstthegreedyalgorithmproposedbyEcketal.weselectedtheEnglish-LithuanianparallelcorpusfromJRC-ACQUIS([92]).Weselectedthecorpusforthefollowingreasons:VSFperformanceonthisparticulardatasetwasatitslowestcomparedtoanumberofotherdatasets,sotherewasroomforimprovementbyapotentiallybetteralgorithm.Withalmost50milliontokenscombined(EnglishandLithuanian)wewereabletooptimizethegreedyalgorithmproposedbyEcketal.andrunitonthisdatasetinareasonableamountoftime.Theexperimentsrunbytheoriginalpaperin2005wererunononly800,000tokens.WealsousedanHMMalignmentmodel[100]forwordalignmentandatree-to-stringtransla-tionsystem([85])fortrainingthetranslationmodelalongwitha4-gramlanguagemodel.755.2.2ResultsUsingthegreedyalgorithmwithn-gramlengthsettoone(j 1inEquation5.1)only10%(5,020,194tokenstotal)ofthedataissorted,sincealln-gramsofsizeonehavebeenobservedbythatpointandtheweightfunctionfortheremainingsentencesreturnszero.Inotherwords,sincetherearenounseenunigramsafter10%ofthedatahasbeensorted,inEquation5.1,thenumeratorbecomeszerothereafterandthereforetheremaining90%ofsentencepairsarenotsorted.ThismustbetakenintoconsiderationwhenexaminingthecomparisonbetweenunigramVSFandtheEckalgorithmwithn-gramlengthsettooneinFigure5.1.VSFwithitslowestsetting,thatisthresholdt=1,selects20%ofthedata,sothischartmaynotbeafaircomparisonbetweenthetwoalgorithms.Figure5.1UnigramEckvs.UnigramVSFInanattempttodoafairercomparison,wealsoexperimentedwithn-gramsoflengthtwointheEckalgorithm,where50%ofthedatacanbesorted(sinceallunigramsandbigramsareobservedbythatpoint).AsseeninFigure5.2,theBLEUscoresfortheEckandVSFsystemsbuiltonthe76similarsizeddatascoreverycloselyontheWMT2009testset.1Inaddition,wedevelopedthefollowingtwoextensionstothegreedyalgorithm,noneofwhichresultedinagaininBLEUscoreoverVSFwithn-gramlengthssetuptothree.Incorporatingtargetsentencen-gramsinadditiontosourcesidesentencen-grams.Dividingtheweightofann-gram(itsfrequency)byaconstantnumbereachtimeasentencethatcontainsthen-gramisselected,asopposedtosettingtheweightofann-gramtozeroafterithasbeenseenforthetime.2Inrelativelysmalldatasetsthereisnotadifferencebetweenthetwoalgorithms.Thegreedyalgorithmdoesnotscaletolargerdatasetsandhighern-grams.Sinceaprincipalfocusofourworkisonscalingtoverylargedatasets,andsincethegreedyalgorithmcouldnotscaletoevenmoderatelysizeddatasets,wedecidedtocontinueourfocusonVSFandimprovementstothatalgorithm.Figure5.2BigramEckvs.UnigramVSF1ThecarefulreadermaynotethatthereisnoofWMT2009([25])testsetforLithuanian,sinceLithuanianisnot(yet)alanguageusedintheWMTcompetition.Thetestsetmentionedherewascreatedfroma1,000sentencesamplefromtheEnglish-sideoftheWMT2009testsets,whichwethenmanuallytranslatedintoLithuanian.2Furtherdetailsofthetothegreedyalgorithmarenotdiscussedhereastheydidnotyieldimprovementsoverthebaselinealgorithm.775.3DataOrderAsapparentfromtheVSFalgorithmdescription,theorderinwhichthealgorithmgoesthroughthedataplaysakeyroleintheselecteddataset.Weexploredfewdifferentorderingofthedata.1.LongestsentenceThemotivationforsortingsentencesindescendingorderoflengthisthatlongersentencesaremorelikelytohavediversevocabularyandbyincludingthemthealgorithmwillchosemorevocabularyitemswithfewertotalnumberofsentencesortokens.2.ShortestsentenceWordalignmentismoreaccurateforshortersentencesastherearefewertotalnumberofalignmentstochosefromandthereforephrasesextractedfromshortersentencestendtobelesserroneous.Theideaisthatsortingsentencesinascendingorderoflengthwillallowtoextractmoreaccuratephrasepairsforvocabularyitemsandresultinahigherqualitymachinetranslationsystem.3.HighestalignmentscoreAlthoughwordalignmentisaresourceintensivetask,itispossibletouseanexistingwordalignmentmodeltoextractViterbialignments.TheViterbialignmentscorecanthenbeusedasadirectandmoreaccuratemeasureofalignmentqualityinsteadofsentencelength.Whileexperimentswererunforallthreeorderings,inadditiontoarandomorder,onlyusingalignmentscoreorderingyieldedanimprovementoverrandomordering.Wereportexperimentresultsforrandomandalignmentscoreorderinginthenextsection.5.4ExperimentSetupTrainingandtuningtoolsusedforexperimentsarethesameasdescribedinSection5.2.1above.WechoseEnglish-FrenchlanguagepairasitisthelanguagepairwithhighestnumberofparallelsentencepairsavailablefromtheWMTcorpus.A5-gramFrenchlanguagemodeltrainedoverthe78t=RandomVSFOrderedVSF11.83M1.83M1.68M22.53M2.53M2.34M53.62M3.62M3.35M104.62M4.62M4.29M205.83M5.83M5.44M407.26M7.26M6.83M608.21M8.21M7.78M1009.53M9.53M9.13M15010.67M10.67M10.33M20011.53M11.53M11.23M25012.22M12.22M11.97MAll22.5MTable5.1English-sideSentenceCounts(inmillions)fordifferentthresholdsforVSF,VSFafterorderingthedatabasedonnormalizedcombinedalignmentscoreandrandombaselines.FrenchsideoftheEnFrGWcorpuswaskeptconstantandusedforallexperiments(onlyparalleltrainingdataischangedthroughouttheseexperiments).MinimumErrorRateTraining(MERT)[79]wasusedfortuningthelambdavaluesforallsystems,usingtheofWMT2010devdata.WeusedWMT2009and2010testsets,usedintheWMTcompetitionsintherespectiveyearsastestsets.TodiscerntheeffectsofVSFatdifferentdegreesoffisaturationfl,wetriedVSFwithdifferentthresholdvaluest,rangingfrom1to250.ForeachtvalueweactuallyranVSFtwice.Inthecase,wedidnoexplicitsortingofthedata.Inthesecondcase,werankedthedatausingthemethoddescribedinSection5.3.Finally,wecreatedrandombaselinesforeacht,whereeachrandombaselineispairedwiththerelevantVSFrun,controlledforthenumberofsentences(sincethasnorelevanceforrandomsamples).Thedifferenttvaluesandtheresultingtrainingdatasizes(sentenceandwordcounts)areshowninTables5.1and5.2.Sinceourinterestinthisstudyisscalingparalleldata,foralltrainingsweusedthesamelanguagemodel,whichwasbuiltoveralltrainingdata(theFrenchsideofthefullEnFrGW).Becausemonolingualtrainingscalesmuchmorereadilythanparallel,thisseemedreasonable.Further,usingonelanguagemodelcontrolsoneparameterthatwouldotherwiseacross79t=RandomVSFOrderedVSF146.1M64.52M65.74M263.99M87.41M88.12M591.55M121.3M120.86M10116.83M151.53M149.95M20147.31M186.99M184.14M40183.46M228.14M224.29M60207.42M254.89M250.68M100240.88M291.45M287.02M150269.77M322.5M318.33M200291.4M345.37M341.69M250308.83M363.44M360.32MAll583.97MTable5.2English-sideWordCountsfordifferentthresholdsforVSF,VSFafterorderingthedatabasedonnormalizedcombinedalignmentscoreandrandombaselines.experiments.Theresultisamuchmorefocusedviewonparalleltrainingdiffs.5.5ExperimentResultsWetrainedmodelsovereachsetofdata.InadditiontocalculatingBLEUscoresforeachresultingsetofmodelsin(Table5.4),wealsocomparedOOV3rates(Table5.5)andperformancedifferences(Table5.3).Theformerisanotherwindowintothefiqualityfloftheresultingmodels,inthatitdescribesvocabularycoverage(inotherwords,howmuchvocabularyisrecoveredfromthefulldata).ThelattergivessomeindicationregardingthetimesavingsafterrunningVSFatdifferentthresholds.OntheWMT2009dataset,bothsetsofVSFmodelsoutperformedtherelevantrandombase-lines.OntheWMT2010testset,thepre-sortedVSFoutperformedallrandombaselines,withtheunsortedVSFoutperformingmostrandombaselines,exceptatt=60andt=200forWMT2010.Clearly,thet=200resultsshowthatthereislessvalueinVSFasweapproachthetotaldatasize.Themostinstructivebaseline,however,istheonebuiltoveralltrainingdata.Itisquiteobviousthatatlowthresholdvalues,thesampleddataisnotacloseapproximationofthefulldata:not3OOV:OutOfVocablaryrateindicatesthenumberoftokensfromthesourcesideofatestsetthatdidnotmatchanyphrasesfromthephrasetabletrainedonparalleltrainingdata.80t=RandomVSFOrderedVSF11:072:171:5621:332:552:3952:154:053:47102:434:494:50203:235:255:14404:126:165:56604:456:417:151005:317:327:551506:078:208:182006:368:318:522507:309:199:11All13:12Table5.3Wordalignmenttimes(hh:mm)fordifferentthresholdsforVSF,VSFaftermodelscoreordering,andarandombaselineWMT2009WMT2010t=RandomVSFS+VSFRandomVSFS+VSF123.7623.8323.8425.6925.7825.68223.9124.0424.0725.7626.2126.14524.0524.2924.4026.1026.4026.321024.1524.3724.4526.2126.6326.322024.2024.4024.5526.3026.4626.564024.3724.4324.6526.4026.5526.536024.3224.4324.6426.5626.5626.6110024.3724.4924.7126.4626.7526.7015024.3724.6124.7126.6726.6726.7020024.4824.6324.6926.5626.6526.7825024.4124.5724.8526.6226.7426.68All24.3726.54Table5.4BLEUScoreresultsforVSF,S+VSF(SortedVSF),andRandomBaselineatdifferentthresholdst.enoughvocabularyandcontextualinformationispreservedforthedatatobetakenasaproxyforthefulldata.However,withtvaluesaround20-60werecoverenoughBLEUandOOVstomakethedatasetsreasonableproxies.Further,becauseweseearelativereductionindatasizesof32-44%,modelsizereductionsof27-39%,andperformanceimprovementsof41-50%atthesetvaluesfurtherarguesforthevalueofVSFatthesesettings.Evenatt=250,wehavetrainingdatathatis54%ofthefulldatasize,yetfullyrecoversBLEU.81WMT2009WMT2010t=RandomVSFS+VSFRandomVSFS+VSF16304244506094204452588374395559385393552034334749235035610494336335458344344204533353354323393414042333033140333633760419329330407333336100389330329391333335150397330330384332332200381328330371331332250356329328370333331All325331Table5.5OOVratesforVSF,S+VSF(SortedVSF),andRandomBaselineatdifferentthresholdst.Figure5.3ComparativeBLEUscoresfortwoVSFimplementations,againstarandomlysampledbaseline.5.6EffectsofVSFonn-gramdistributionInanattempttobetterunderstandthebehaviorofVSFandhowVSFchangesthen-gramdistribu-tionsofvocabularyitemsinasampleascomparedtothefullcorpus,wecreatedlog2-scalescatterplots,asseeninFigure5.5.Intheseplots,unigramfrequenciesofdata(i.e.,thefullcor-pus,EnFrGW)areontheverticalaxis,andunigramfrequenciesoftheVSFdataareonthehorizontalaxis.Thethreeplotsshowthreedifferentsettingsfort.Therefollowingobservationscanbemadeabouttheseplots:82Figure5.4ComparativeOOVratesfortwoVSFimplementations,againstarandomlysampledbaseline.1.Onthehorizontalaxisbeforewereachlog2(t),alldatapointsfallonthex=yline.2.Asthethresholdincreasesthescatterplotgetsclosertothex=yline.3.VSFhasthehighestimpactonthefimediumflfrequencyunigrams,thatis,thosewithafrequencyhigherthanthethreshold.ThethirdpointspeaksthemosttotheeffectsthatVSFhasondata:Verylowfrequencyitems,thosewithfrequenciesbelowthethresholdt,areunaffectedbythealgorithm,sinceweguaranteeincludingallcontextsinwhichtheyoccur.Lowfrequencyitemsareatthelowerleftoftheplots,andtheirfrequenciesfollowthex=yline(point1above).Mediumfrequencyitems,however,thosewithfrequenciesimmediatelyabovet,arethemostaffectedbythealgorithm.Thefibulgeflintheplotsshowswherethesemediumfrequencyitemsbegin,andonecanseeplainlythattheirdistributionsareperturbed.Thefibulgefldissipatesasfrequenciesincrease,untiltheeffectsdiminishasweapproachmuchhigherfrequencies.ThelatterisaconsequenceofasimplifyingheuristicappliedinVSF(asdescribedinSection5.1):tisnotahardceiling,butratherasoftone.Vocabularyitemsthatoccurveryfrequentlyinacorpuswillbecountedmanymoretimesthant;forveryhighfrequencyitems,theirsampleddistributionsmayapproachthoseobservedinthefullcorpus,andconvergeonthex=yline.WesuspectthattheBLEUlossthatresultsfromtheapplicationofVSFistheresultoftheperturbeddistributionsformedium83(a)VSFt=1(b)VSFt=40(c)VSFt=200Figure5.5log2-scaleUnigramFrequencyscatterplotbeforeVSFversusafterVSFfrequencyitems.Adjustingtohighertvaluesdecreasesthedegreeoftheperturbation,asnotedinthesecondpoint,whichlikewiserecoverssomeoftheBLEUlossobservedinlowersettings.WeinvestigatethisphenomenafurtherinChapter6.5.7ConclusionInthischapterweintroducedanewdataselectiontechnique(VocabularySaturationFilter).Whilethismethodishighlyscalableandlinearindatasize,weshowedthatitiscomparabletothestateoftheartindataselection.Weconductedseveralexperimentswithvariousdatasizesandshowedthatitperformsbetterthanrandomdataselection.Inaddition,weexperimentwithvariousorderingsofthedataandshowedthatorderingthedatabasedonalignmentscoreresultsinhighertranslationqualityoutput.Wecomparedandanalyzedtheeffectsofdataselectiononvocabularydistributionandsuggestedusingavariablethresholdasanimprovement.WeimplementvariablethresholdsandanalyzevocabularydistributioninChapter6.84CHAPTER6THESATURATIONFILTERFRAMEWORKWedemonstratedtheadvantagesofVocabularySaturationFilterinChapter5.Inthesaturationframeworkthegoalistohaveenoughsamplesforeachfeaturesuchthatitcanbelearnedef.Forexample,inthecaseofalexicalfeature,thegoalistoobserveenoughinstancesofthelexicalitemsuchthatitcanbetranslatedcorrectlyinasentence.Twoquestionsarisefromthisgoal:1.Whatarethekeyfeaturesofasentencepairthatcorrespondtoitscontributiontohigherqualitymachinetranslationoutput?2.Howmanyinstancesofeachfeatureinasentencepairshouldbeobservedinthetrainingdataforittobelearnedeffectivelybythestatisticaltranslationsystem?VSF(asdescribedinChapter5)onlyusessourcelexicalvocabularyitemsasfeaturesofasentencepairandaconstantnumber(threshold)foreachfeaturetobelearnedeffectively.TheideabeingthatifallsourcevocabularyitemshavebeenseenatleastNtimes,thestatisticaltranslationsystemisabletotranslatethemwithminimumerror.Althoughthechoiceoffeatureandthresholdwasquitesimple,weshoweditisveryeffectiveandcomparabletothestateoftheartwhilebeinghighlyscalable.InthischapterweexpandthefeaturespacetocoverwordalignmentandsemanticinformationusingMinimalTranslationUnits,BrownClustersandseveralcombinationsofthem.Wealsoexplorehighern-gramordersinthisfeaturespacetoincorporatecontextinformation.Inaddition,weexploredifferentvariablethresholdfunctionssuchasindividualentropyandlogfrequencyanduniformthreshold.Thegoalsofusingvariablethresholdisthreefolds:1.AsshowninChapter5,dataselectionchangestheempiricalprobabilitydistributionofwordsintheselecteddatacomparedtotheselectionpool,causingasamplingbias.Usingvariable85thresholdfunctionsweareabletominimizethissamplingbias(Section6.5.2).2.Whenthenumberofuniquefeaturesishighcomparedtothenumberofsentencepairsintheselectionpool,usingthesmallestconstantthresholdof"one"canresultinselectingmostorallofthedata.Usingavariablethresholdwillenableusingricherfeatureswhileselectinganarbitraryamountofdata(Section6.3).3.Avariablethresholdallowsforgivingahigherweighttothemostimportantfeatures.Thiswillresultinmoreinstancesforthesefeaturesandultimatelyallowforahigheraccuracyestimationforthem(Section6.2).4.Usingavariablethresholdalsoenablesincorporatingarbitrarysideinformationinthese-lectionalgorithmsuchasalignmentscoreandcrossentropydifference([74])inthecaseofdomainadaptation.Finally,wedevelopascalable,incrementalandadaptivealgorithmthatisabletoselectasubsetofthedataaccordingtothefeaturesetandthresholdfunctionwithanarbitrarydesiredsize.Thisisdonebyproducingincrementalbinswithgranularity.Thesubsetisthenselectedbyselectingthenumberofdesiredbinsintheorderproducedbythealgorithm.6.1FeatureSpaceThesaturationframeworkisabletouseanyfeaturethatcanbecalculatedforasentencepair,independentofothersentencepairs.InthecontextoftheSFF1eachuniquefeaturenewinformation(ornewinstanceofarandomvariable)thatcanbeusedtoestimatethestatisticaltranslationmodelsmoreaccurately.Weexploredseveralsentence-pairfeaturesusedinChapter4forparalleldataanalysis.Thesefeatureshavethreemaincomponents:1.SourceandTargetLexicalItems:LexicalitemsarethebasicfeaturesusedinVSF.1SaturationFilterFramework862.BrownClusters:Brownclustersarestatisticallylearnedfeaturesthatcanbeusedasinde-pendentfeaturesorcombinedwithotherfeaturestoprovidesemanticawarenesstothem.3.MinimalTranslationUnits:MinimalTranslationUnitsenhancethefeaturespacebyincor-poratingwordalignmentinformation.PleaseseeChapter4fordetaileddescriptionoftheindividualfeaturesabove.Thesefeaturescanbecombinedinmanydifferentways.Sinceevaluationofeachfeaturecombinationtakesseveralweeks(includingvariationsinthresholdfunctions)totrainstatisticalmachinetranslationmodelsforevaluation,itisnotpracticaltoexploreallvariations.Therefore,wehaveselectedafewvariationsthataretheoreticallymotivated.6.1.1SourceVocabularyThisfeatureisselectedasabaselinefromChapter5.Featuresareindividualwordsinthesourcesideoftheparalleldata.6.1.2SourceandTargetVocabularyThisisasimplevariationofVSF,asitincorporatessourceandtargetvocabularyasseparatein-dividualfeaturesfromthesourceandtargetsideoftheparalleldata.ThisisalsoincludedasabaselineasChapter5onlyincludesexperimentsforthebasicversionofVSF(UnigramSourceVocabulary).6.1.3BigramSourceVocabularyBigramsourcevocabularyisanothersimplevariationsofVSFandusedhereasacomparisonpointtothebaseline.Inthisfeatureallpairsofneighboringlexicalitemsinthesourcesideoftheparalleldataareusedasfeatures.ThisfeaturehasthenaturaleffectofgivingmorefrequentlexicalitemsahigherthresholdsincetheynaturallyparticipateinmoreuniquebiŒgrams.876.1.4SourceVocabularywithContextForthisfeaturewetaketheBrownclusterofthepreviousandnextwordforeachlexicalitemtocreateanewfeature.Thisfeatureenablesustodistinguishbetweenthesamelexicalitemappearingindifferentsemanticcontexts.Thisallowsthedataselectionalgorithmtoensurealllexicalitemshavebeenseenindifferentsemanticcontextsandthereforeensurethestatisticaltranslationmodelcanprovidetranslationsforwordsindifferentcontextsaccordinglyandhenceprovidehigherqualitymachinetranslationoutput.SimilartobiŒgramsourcevocabulary,asmorefrequentwordsoftenappearinmorediversecontexts,thisfeatureresultsinanaturallyhigherthresholdformorefrequentlexicalitems(comparedtosourcevocabularywithuniformthreshold).6.1.5MinimalTranslationUnitThisisthefeaturethatincorporateswordalignmentinformationintothedataselectionprocess.Althoughincorporatingsourceandtargetvocabularyenablesthesaturationframeworktocoversourceandtargetvocabulary,usingMTUs2ensuresallpossibletranslationsofeachsourcewordareconsideredinthedataselectionprocess.PleaseseeChapter4formoredetails.6.1.6MinimalTranslationUnitwithTargetBrownClusterUsingMTUswithtargetcontextisavariationbetweenSourceVocabularywithContextandMTU.Whilesourcevocabularywithcontext,considersthewordclassessurroundingthesourceword,MTUwithtargetBrownclusterconsiderssourcewordandthewordclassofitstranslation.Usingthisfeatureitispossibletodistinguishbetweendifferentsensesofawordwhenthetargetlan-guagedoesnotsharethesamesensesforitstranslation.Forexample,itcandistinguishbetweenthecasewheretheEnglishword"bank"isalignedtotheFrenchword"banque"andtheFrenchword"bank".ThepotentialadvantageofthisfeatureoverMTUsisthatitcanmakethisdistinctionwithasmallerfeaturespace.ThenumberofpossiblefeaturesforMTUwithtargetBrownclus-2MinimalTranslationUnits88terisjSourceVocabularyjjWordClassesjwhileitisjSourceVocabularyjjTargetVocabularyjforMTU3.Sincethenumberofwordclassesismanyordersofmagnitudessmallerthanthevocabularysize,thiscanincreaseefyaswellasreducenoiseduetobadalignments.6.2ThresholdFunctionInthesaturationframework,thefeaturethresholdcanbeanyarbitraryfunctionaslongasitdoesn'tchangethroughouttheselectionprocess.Thisrestrictionallowsforscalableimplementa-tionofthealgorithmasitcanberunondifferentpartitionsofthedataindependentlyandaggregatetheresultsafterward.NgandJordan([77])haveshownthatthenumberofsamplesrequiredtoreachasymptoticerrorforgenerative(suchasNaiveBayes)isalogarithmicfunctioninthenumberoffeatures.Statisticalmachinetranslationcanbeformulatedasasetofgenerativeeachpredictingonetargetwordgivensourcewordsasfeatures.UsingthisformulationandresultsfromNgandJordan,machinetranslationreachesasymptoticerrorasalogarithmfunc-tionofthenumbersourcefeaturesobservedforeachtargetword.Forthisreason,wethegeneralformofthethresholdfunctionasshowninEquation6.1toincludealogarithmfunction.Thisformulationallowsforthelogarithmofnumberofsourcefeaturespertargetwordstobeusedinthethresholdfunctions.t(f)=h(f)logg(f)(6.1)h(f):Tuningfunctionthatcanbetunedtoachievedesireddatasize.g(f):Anarbitraryfunctionthatcanusestatisticsoffeaturef.f:featureAlthoughmanyvariationsofthefunctionsh(f)andg(f)canbeused,motivatedbypriorwork([33,17,66])weintroducethefollowingvariablethresholdfunctions.3InTable6.2,MTUwithuniformthresholdofoneselects12.88millionsentencepairswhileMTUwithtargetBrownclustersselects11.76millionsentenceswiththesamethreshold.891.Uniform:ThisfunctionisusedasabaselinecomparisontoVSFwherethefeaturethresholdisaconstantfunctionforallfeatures.Inthisvariation,h(f)logg(f)issettoaconstantintegernumberforallfeatures(g(f)=2;h(f)=c).2.IndividualEntropy:Dataselectioncanalsobereferredtoasdatacompression.Theideaistohavearichervocabulary(features)inasmallersetofdatawhilepreservingtheoriginalprobabilitydistribution.Settingg(f)=P(f)=Count(f)åf2F(Count(f))andh(f)=kP(f)willturnthethresholdfunctionintoindividualentropywhichisanaturalandintuitivefunctiontouseasweapproachtheproblemasadatacompressionproblem.The"IndividualEntropy"ofaninstanceofarandomvariable,P(X=x)logP(X=x),isthetheoreticallimitoftheaveragenumberofbitsusedtorepresentrandomvariableX=xinacompressedformat.TheargumentforusingthisfunctionistotreatdataselectionasadatacompressionproblemandsetthethresholdlimitforfeatureF=ftobeaconstantfactoroftheindividualentropyofP(F=f).3.Logarithmic:UsingresultfromtheworkofNgandJordan,weliketosetthethresholdforthenumberoftargetwordstobeincludedinselecteddatatobethelogarithmofthenumberofsourcefeaturesfortargetwords.Sincehighernumberofsourcewordsiscorrelatedwithhighernumberofsourcewordspertargetword,weusethefrequencyofsourcewords(orfeaturesingeneral)asathresholdfunction.Theintuitionbehindthisstrategyisthatitismoreimportanttolearnfrequentfeaturesastheyaremorelikelytoalsoappearintestdata.Inthiscase,g(f)=Count(f)andh(f)=k.6.3IncrementalAlgorithmApracticalshortcomingoftheVSFselectionalgorithmwastuningthethresholdvalue.Wesolvethisproblemusinganincrementalalgorithmwhichsplitsthedataintoseveralorderedpartitions.Dependingonthedesireddatasize,anumberofbinsareselectedandtherestarediscarded.WeachievethisbyafiThresholdGrowthFunctionfl,G(t).Weiteratethroughthedatamultiple90times.Ineachiteration,weselectnewparallelsentencesusingthethresholdfunctiontocreateanewpartitionandremovethemfromtheselectionpool.Inthenextiteration,weincreasethethresholdusingthegrowthfunctionandrepeatwhileallthedataispartitioned.Thetradeoffinthegrowthfunctionisbetweenxibilityandefy.Aslowgrowthfunctionwillcreatesmallerpartitionsallowingtoselectthedesiredamountofdatawithhigheraccuracy,butitwilltakemoreiterationstopartitionallthedata.Ontheotherhand,afastgrowthfunctionwilltakelessiterationstorunbutwillsplitthedataintofewerpartitionswhichofferslessxibilityinachievingthedesireddatasize.Incontrast,withVSFonewouldhavetosetthethresholdvaluettoadesiredvalue,runthealgorithmandthenbasedontheamountofdataselected,increaseordecreasethethresholdvalueandrunthealgorithmagain,untildesiredamountofdataisselected.ComputationalcomplexityofthisincrementalalgorithmisO(NC)whereNisthenumberofsentencesinselectionpoolandCisthenumberoftimespartitionscreatedbythealgorithm(ValueofCisdependentonG(t)).Althoughthisalgorithmdoesnotrequirethedatatobeallloadedinmemory,inourimplementation,toincreaseefy,weloadallthedatainmemoryandgraduallyremoveitfrommemoryasweselecteachpartitionandwriteittothedisk.Therefore,forourimplementationthememoryrequirementisO(N).6.4ExperimentSetupForstatisticalmachinetranslationtraining,similartoChapter5,weuseEnglish-FrenchlanguagepairasitisthelanguagepairwithhighestnumberofparallelsentencepairsavailablefromtheWMTcorpus([21])with22.5millionsentencepairs.WealsousedanHMMalignmentmodel[100]forwordalignmentandaphrasaldecoder([75])usingadistortionlimitof5andahier-archicallexicalreorderingmodel([39]).Weusea4-gramlanguagemodeltrainedonthetargetsideofthetrainingdatausingKneserŒNeysmoothing([54]).Thelanguagemodeliskeptcon-stantforallexperiments.WeonlytrainthetranslationmodelfollowedbyMinimumErrorRateTraining(MERT)[79]fortuningthelambdavaluesforallsystems,usingtheofWMT2010developmentdataset([21]).91LabelDescriptionW_SRCSourceVocabularyW_BISourceandTargetVocabularyWBi_SRCSourceBi-gramVocabularyCW_SRCSourceVocabularywithContextMTU_BIMinimalTranslationUnitCMTU_TGTMinimalTranslationUnitwithTargetBrownClusterRandomRandomSelectionTable6.1Dataselectionfeaturesandtheirlabels.Fordataselection,inallexperimentsweusetheincrementalalgorithmwithanexponentialgrowthfunction,G(ti)=2G(ti1),whereiistheiterationnumber.Weattempttohavedatasetsselectedwithsizesatexponentialintervalsof1M,2M,4M,8M,16Mandallthedata(22.5M)forthebaseline.Forconstantthresholdexperiments,incaseswithhighnumberofuniquefeatures,theminimumthresholdoffioneflselectsalargepercentageofthedata(Forexample,theMTUfeatureselects13Msentencepairswithaconstantthresholdofone).Inthesecases,whilenotalwayspossible,wehavetriedtokeepthedatasetsizesasclosetotheexponentialintervalslistedaboveaspossible.Forthethresholdfunctionweexperimentwithuniformthreshold,logarithmoffrequencyandindividualentropyasdetailedinSection6.2.ThedataselectionfeaturesusedinourexperimentsarelistedinTable6.1.6.5ExperimentResultsThegoaloftheseexperimentsaretoevaluatetheeffectivenessofeachfeatureandvariablethresh-oldfunction.Firstwecompareallfeaturesusingaconstantthresholdfunctionusingtheexpo-nentialgrowthfunctiondescribedabove.Thisresultsin22uniquesubsetsoftheentire22.5Msentencepairdataset(SeeTable6.2).92FeatureDataSizesRandom1.00M,2.00M,4.00M,8.00M,16.00M,22.50M(all)W_SRC0.98M,1.97M,4.15M,8.08M,15.85MW_BI42.19M,3.99M,7.90M,15.95MWBi_SRC59.38M,16.33MCW_SRC616.54MMTU_BI712.88M,16.30MCMTU_TGT811.76M,16.54MTable6.2IncrementalFeatureSaturationFilteralgorithmsizesforeachfeature.Wealsocomparetheindividualentropy,logarithmoffrequencyandconstantthresholdfunc-tions(Table6.3).FeatureThresholdFunctionDataSizesW_SRCConstant0.97M,1.97M,4.15M,8.08M,15.84MW_SRCIndividualEntropy1.17M,2.30M,4.66M,9.35M,17.60MW_SRCLogarithmofFrequency0.91M,2.43M,4.56M,8.02M,15.68MWBi_SRCConstant9.38M,16.33MWBi_SRCIndividualEntropy1.39M,2.30M,4.37M,8.46M,15.46MWBi_SRCLogarithmofFrequency3.23M,4.41M,8.23M,16.65MCMTU_TGTLogarithmofFrequency0.68M,1.90M,4.41M,6.29M,15.97MMTU_BILogarithmofFrequency0.54M,1.61M,6.01M,11.03M,15.32MTable6.3IncrementalSaturationFilteralgorithmsizesfordifferentthresholdfunctions.Differentselectiontechniquesareevaluatedusingthemetricsbelow.1.BLEUscore:WereporttheBLEUscoreofeachtranslationsystemonWMT2009andWMT2013testsets([21]).2.UniqueSourcePhrases:Thenumberofuniquesourcephrasesextractedfromparalleldata.3.UniquePhrasePairs:Thetotalnumberofphrasepairsextractedfromparalleldata.4Constantthresholdoffioneflselects2.19Msentencepairs.Thusa1Mdatasetisnotavailableforthisfeature.5Constantthresholdoffioneflselects9.38Msentencepairs.6Constantthresholdoffioneflselects16.64Msentencepairs.7Constantthresholdoffioneflselects12.88Msentencepairs.8Constantthresholdoffioneflselects11.76Msentencepairs.934.AverageTargetPhrasePerSource:Theratioofthetwometricsabove(uniquephrasepairsdividedbyuniquesourcephrases).5.EmpiricalDistributionDistance:TheJensenŒShannondivergencebetweenempiricalprob-abilitydistributionfunctionsofselecteddataandselectionpool(Equation6.2).JSD(PjjQ)=12DKL(PjjM)+12DKL(QjjM)(6.2)M=12(P+Q)DKL(PjjQ)=åiP(i)logP(i)Q(i)6.5.1FeatureComparisonFirst,wecomparetheeffectivenessofdifferentfeaturesinthesaturationframeworkusingconstantthresholds.TheBLEUscorecomparisonbetweenfeaturesarepresentedinFigure6.1andFigure6.2usingWMT2009andWMT2013testsets.94Figure6.1BLEUscorecomparisonofdifferentdataselectionfeatureswithconstantthresholdwiththeWMT2009testset.Figure6.2BLEUscorecomparisonofdifferentdataselectionfeatureswithconstantthresholdwiththeWMT2013testset.95Wefurthercomparedifferentdataselectionfeaturesusingtotalnumberofphrasepairs(Fig-ure6.4),numberofuniquesourcephrases(Figure6.3)andtheaveragenumberoftargetphrasespersourcephrase(Figure6.5).Figure6.3Comparisonoftotalnumberofuniquesourcephrasesextractedforeachdataselectionfeature.Figure6.4Comparisonoftotalnumberofuniquephrasepairsextractedforeachdataselectionfeature.Figure6.5Averagenumberoftargetphrasespersourcephraseforeachdataselectionfeature.96Itisnotablethatallfeaturesperformbetterthanrandomdataselection.Inadditionwemakethefollowingobservationswhencomparingdifferentfeatures.1.Featureswithsourcecontext(WBi_SrcandCW_Src)havethehighestBLEUscoreperfor-mancegiventheirsize(Figure6.1andFigure6.2).2.MTUfeatureprovidesmosttargetphrasespersourcewithleastamountofdata(Figure6.5).3.SourcewordwithBrownclustercontext(CW_SRC)hastheleastnumberofuniquesourcephraseswithhighestphraseratioandcomparableorhigheroverallBLEUscore.Thissug-geststhisfeatureisabletooutnoisyorunimportantsourcephrases.6.5.2ThresholdFunctionComparisonAsexplainedearlier,theempiricalprobabilitydistributionofwordschangeasaresultofdatase-lection(alsoknownassamplingbias).Figure6.6showsthisphenomenainrandomdataselection.Weuseadensityscatterplottodemonstratechangestothedistribution.Inadensityscatterplotdarkercolorsareusedtoshowconcentrationoroverlappingdatapoints.ForexampleinFigure6.6fordatasizeof1M,thedarkbluestartingattheoriginmovingalongthehorizontalaxisrepresentsthemanyvocabularyitemsthatwereobservedintheselectionpoolbutaremissinginrandomlyselecteddatasetsizeof1millionsentencepairs.Asmoredataisselected(4M,8Mand16M),thedarkbluemovesclosertothex=ylineasthewordprobabilitiesinselectionpoolandse-lecteddatagetcloser.Itisalsoclearthatthedistancebetweenthedistributions(measuredusingJensenŒShannonDivergence)dropsastheselectionsizeincreases.97Figure6.6Samplingbiasinrandomdataselection.X-Axisislogarithmoffrequencyforwordsinallthedata.Y-Axisislogarithmoffrequencyforwordsinselecteddata.Thegraphisgeneratedforsubsetsofthedatainsizes1M,4M,8Mand16M(JSD:JensenŒShannonDivergence).Usingaconstantthresholdcausesthesamplingbiastoincrease(comparedtorandomselec-tion).WemeasurethedistancebetweenthetwodistributionsusingJensen-ShannonDivergence(markedontheplotwithJSD).ThiscanbeobservedinFigure6.7.Theconstantthresholdfre-quencycanalsobeobservedinthisgraphinthedatasetsizeof4Maspointsgetscatteredawayfromthex=ylineafterx=5.Thisisduetoacut-offfrequencyof25=32.Anywordwithfrequencyoflessthan32continuestohavethesamefrequencyintheselecteddatawhilewordswithhigherfrequenciesstarttomoveawayfromthex=yaxis.98Figure6.7Samplingbiasinuniformthresholdfunction.X-Axisislogarithmoffrequencyforwordsinallthedata.Y-Axisislogarithmoffrequencyforwordsinselecteddata.Thegraphisgeneratedforsubsetsofthedatainsizes1M,4M,8Mand16M(JSD:JensenŒShannonDiver-gence).Thesamplingbiasisimprovedusingalogarithmoffrequencyfunction,buttheJensen-Shannondivergenceisstillhigherthanrandomdataselection(Figure6.8).Thecomparisonwithuniformcanbeobservedclearlyinthedifferencebetweenthe4MdatasizebetweenFigure6.8andFig-ure6.7.Sincethelogarithmoffrequencythresholdfunctionhasahigherthresholdforhigherfrequencywords,datapointsmoveawayfromthex=ylinewithamilderslopeafterthex=5line.99Figure6.8Samplingbiasindataselectionusinglogarithmoffrequencythresholdfunction.X-Axisislogarithmoffrequencyforwordsinallthedata.Y-Axisislogarithmoffrequencyforwordsinselecteddata.Thegraphisgeneratedforsubsetsofthedatainsizes1M,4M,8Mand15M(JSD:JensenŒShannonDivergence).Usinganentropythresholdfunction,theJensen-Shannondivergenceimprovesdramaticallyasitisnearlyhalfofwhatitisforrandomdataselection(Figure6.9).Thiscanbeobservedbytherelativeclosenessofdatapointstothex=yaxisforalldatasizescomparedtotheircounterpartsinotherthresholdfunction(Figure6.7,Figure6.8,Figure6.6).100Figure6.9Samplingbiasindataselectionusingentropythresholdfunction.X-Axisislogarithmoffrequencyforwordsinallthedata.Y-Axisislogarithmoffrequencyforwordsinselecteddata.Thegraphisgeneratedforsubsetsofthedatainsizes1M,4M,9Mand17M(JSD:JensenŒShannonDivergence).Theentropythresholdfunctionpreservesthevocabularydistributionbetterthanrandomselec-tion,uniformthresholdandlogarithmoffrequencythresholdfunction.Next,wecomparethesemethodsusingBLEUscoreontheWMT2009andtheSpeechEX1conversational([67])testsets.First,wecomparethethresholdfunctionsusingthesourcevocabularyfeature(Figure6.10andFigure6.11).101Figure6.10BLEUscorecomparisonofdifferentdataselectionthresholdfunctionusingsourcevocabularyfeaturewiththeWMT2009testset.Figure6.11BLEUscorecomparisonofdifferentdataselectionthresholdfunctionusingsourcevocabularyfeaturewiththeSpeechEX1conversationaltestset([67]).102TheentropythresholdfunctionandlogarithmoffrequencythresholdfunctionsoutperformuniformthresholdatsmallselectionsizesintheWMT2009testsetbutperformsimilarlyatlargerselectionsizes.However,intheconversationaltestsettheentropythresholdfunctionoutperformsothermethodsformostselectionsizes.Wethesebyrunningthesameexperimentusingbigramsourcevocabulary(Figure6.12andFigure6.13)asthisfeatureisoneofthebestperformingfeaturesinthefeaturecomparisonplots(Figure6.1andFigure6.2).Figure6.12BLEUscorecomparisonofdifferentdataselectionthresholdfunctionusingsourcevocabularyfeaturewiththeWMT2009testset.103Figure6.13BLEUscorecomparisonofdifferentdataselectionthresholdfunctionusingsourcevocabularyfeaturewiththeSpeechEX1conversationaltestset([67]).Wefurtherexplorephrasetablestatisticstobetterunderstandthedifferencesindifferentthresh-oldfunctions.InFigure6.14andFigure6.15theentropythresholdfunctionhasahigheraveragenumberoftargetphrasespersourcephraseinthe1millionselectionsize,despitehavingaloweruniquenumberofphrasesandtotalnumberofphrasepairs(Figure6.16,Figure6.17,Figure6.18andFigure6.19)forbothfeatures(SourceVocabularyandBigramSourceVocabulary).Figure6.14Thresholdfunctionscomparisonforaveragenumberoftargetphrasespersourcephrasesextractedforsourcevocabularyfeature.104Figure6.15Thresholdfunctionscomparisonforaveragenumberoftargetphrasespersourcephrasesextractedforbigramsourcevocabularyfeature.Figure6.16Thresholdfunctionscomparisonfortotalnumberofphrasepairsextractedforsourcevocabularyfeature.Figure6.17Thresholdfunctionscomparisonfortotalnumberofphrasepairsextractedforbigramsourcevocabularyfeature.105Figure6.18Thresholdfunctionscomparisonfornumberofuniquesourcephrasesextractedforsourcevocabularyfeature.Figure6.19Thresholdfunctionscomparisonfornumberofuniquesourcephrasesextractedforbigramsourcevocabularyfeature.Theentropythresholdfunctionexcelsintwoareas:1)insmallselectionsizesand2)intestsetsthatconsistsofmostlyhighfrequencyvocabularyitems(i.e.theSpeechEX1testset([67])).Inthecaseofsmallselectionsizesitisclearthatdespitehavingfewerorequalnumberphrasepairs,thedataselectedusingtheentropythresholdfunctionresultsinaphrasetablewithhigheraveragenumberoftargetphrasespersourcephrase.Astheselecteddatasetgrowsandlessfrequentwordsarealsoselected,theaveragenumberoftargetphrasespersourcephraseinphrasetablestrainedondataselectedusingdifferentthresholdfunctionsconverge.ThisisinlinewithhigherBLEUscoreintheconversationaltestsetasitmostlycontainshighfrequencyvocabularyitems.Oneofthelimitationsoftheuniformthresholdfunctionisthatinthecaseoffeatureswithhighnumberofuniquevalues(e.g.MTU),athresholdvalueofoneselectsmostofthedata(57%inthe106caseofMTU).Variablethresholdfunctionscanovercomethislimitationbygivinghigherprioritytomorefrequentormoreimportantfeatureinstances.Weruntwoexperimentswithsuchfeatures(MTUandMTUwithBrownclusters)todemonstratethis.Figure6.20andFigure6.21showhowBLEUscoreperformanceiseffectedusingthelogarithmoffrequencythresholdfunctionatvariousdatasizeswiththeWMT2009testset.Figure6.20BLEUscorecomparisonfortheselectionoflowerdatasizesusinglogarithmoffre-quencythresholdfunctionandMTUfeatureatdifferentselectionsizes.107Figure6.21BLEUscorecomparisonfortheselectionoflowerdatasizesusinglogarithmoffre-quencythresholdfunctionandMTUwithtargetBrownclusterfeatureatdifferentselectionsizes.Figure6.21andFigure6.20demonstratealthoughMTUandMTUwithtargetBrownclusterarenotabletoselectdatasizessmallerthanapproximately50%ofthedata,thiscanbeachievedusingavariablethresholdfunctionwhiletheBLEUscoreperformancedropsoffsmoothlysimilartofeatureswithlessnumberofuniquefeatures.6.6ConclusionInthischapterweextendedtheVSFalgorithmtoaxibleandefdataselectionframeworkwhichisabletotakeadvantageofhighlycomplexfeatureswhileremainingefInaddition,saturationframeworkusesanincrementalalgorithmthatallowsforselectingdatasetswithanydesirablesize.WhilecomparingusageofdifferentfeatureswithinthisframeworkweshowedfeaturesthatleveragesourcecontextperformbestwhileusingBrownclustersascontexthasanoiseeffectaswell.Inaddition,whileexploringdifferentthresholdfunctionsweshowedtheentropythresholdfunctionpreservesthevocabularydistributionthebestusingJensenŒShannon108divergencemetric.TheentropythresholdfunctionalsoprovidesthehighestBLEUscorewhenselectingsmalldatasizesaswellastestsetswithlimitedbuthighfrequencyvocabularyitems.109CHAPTER7CONCLUSIONInthisthesisweexploredparalleldataanalysistechniqueswhileintroducingvarioussentencelevelfeaturesforthetranslationdirectiondetectiontask.Wepresentedasetoffeaturesthatoutperformallpriorwork.Furthermore,wedevelopedthecross-domaindatasetforthetranslationdirec-tiondetectiontaskandintroducednewfeaturesthatoutperformallpriorworkinallcross-domaindatasets.Wepresentedacomprehensiveoverviewoftheliteratureonthedataselectiontaskforstatisticalmachinetranslation.InChapter5,wedevelopedahighlyscalabledataselec-tionmethod(VSF)thatoutperformedstateoftheartinlargedatasets.FinallyinChapter6,weintroducedaxibleandscalabledataselectionframeworkthatcanleveragesentencepairlevelfeaturesaswellasvariousthresholdfunctions.WeleveragedthefeatureswedevelopedinChap-ter4andexploredadvantagesanddisadvantagesofeachfeature.Wefurtheranalyzedtheeffectsofdataselectiononvocabularydistributionanddemonstratedusinganentropybasedthresholdfunc-tionbestpreservesvocabularydistribution(usingJensenŒShannondivergence).Infuturework,weplantodevelopacomparativetranslationmodelanalysistooltofurtherexploretheeffectsofdataselectionontranslationmodelsandunderstandsomeoftheeffectsobservedintranslationmodelstatistics(suchasnoisereductioneffectswithsourcevocabularyandBrownclustercontexts).Acommonproblemwithlargedatasetsisnoise.Weplanonextendingthisworktoperformdatacleaningaswell.Onthealgorithmicside,weplanonextendingthisalgorithmtoadistributedcomputingenvironmenttoimproveitsscalability.110BIBLIOGRAPHY111BIBLIOGRAPHY[1]AnneAbeillé,LionelClément,andFrançoisToussenel.Buildingatreebankforfrench.InAnneAbeillé,editor,Treebanks,volume20ofText,SpeechandLanguageTechnology,pages165Œ187.SpringerNetherlands,2003.ISBN978-1-4020-1335-5.[2]YvonneAdesam.TheMultilingualForest:InvestigatingHigh-qualityParallelCorpusDevelopment.PhDthesis,StockholmUniversity,DepartmentofLinguistics,2012.[3]AlexandreAllauzen,HélèneBonneau-Maynard,Hai-SonLe,AurélienMax,GuillaumeWisniewski,Fran\ccoisYvon,GillesAdda,JosepM.Crego,AdrienLardilleux,ThomasLavergne,andArtemSokolov.LIMSI@WMT11.InProceedingsoftheSixthWorkshoponStatisticalMachineTranslation,WMT'11,page309Œ315,Stroudsburg,PA,USA,2011.AssociationforComputationalLinguistics.ISBN978-1-937284-12-1.[4]V.Ambati.ActiveLearningandCrowdsourcingforMachineTranslationinLowResourceScenarios.PhDthesis,UniversityofSouthernCalifornia,2011.[5]V.Ambati,S.Vogel,andJ.Carbonell.Activelearningandcrowd-sourcingformachinetranslation.LanguageResourcesandEvaluation(LREC),7:2169Œ2174,2010.[6]S.Ananthakrishnan,R.Prasad,D.Stallard,andP.Natarajan.Discriminativesampleselec-tionforstatisticalmachinetranslation.InProceedingsofthe2010ConferenceonEmpiricalMethodsinNaturalLanguageProcessing,page626Œ635,2010.[7]S.Ananthakrishnan,R.Prasad,D.Stallard,andP.Natarajan.Asemi-supervisedbatch-modeactivelearningstrategyforimprovedstatisticalmachinetranslation.InProceedingsoftheFourteenthConferenceonComputationalNaturalLanguageLearning,page126Œ134,2010.[8]A.Axelrod,X.He,andJ.Gao.Domainadaptationviapseudoin-domaindataselection.InProceedingsofthe2011ConferenceonEmpiricalMethodsinNaturalLanguageProcess-ing,page355Œ362,2011.[9]A.Axelrod,Q.J.Li,andW.D.Lewis.Applicationsofdataselectionviacross-entropydifferenceforreal-worldstatisticalmachinetranslation.ProceedingsIWSLT2012,2012.[10]AmittaiAxelrod,XiaodongHe,andJianfengGao.Domainadaptationviapseudoin-domaindataselection.InProceedingsoftheConferenceonEmpiricalMethodsinNaturalLanguageProcessing,pages355Œ362.AssociationforComputationalLinguistics,2011.[11]MonaBaker.Corpuslinguisticsandtranslationstudies:Implicationsandapplications.Textandtechnology:inhonourofJohnSinclair,233:250,1993.[12]SatanjeevBanerjeeandAlonLavie.Meteor:Anautomaticmetricformtevaluationwithimprovedcorrelationwithhumanjudgments.InProceedingsoftheaclworkshoponin-trinsicandextrinsicevaluationmeasuresformachinetranslationand/orsummarization,volume29,pages65Œ72,2005.112[13]MarcoBaroniandSilviaBernardini.Anewapproachtothestudyoftranslationese:Machine-learningthedifferencebetweenoriginalandtranslatedtext.LiteraryandLin-guisticComputing,21(3):259Œ274,2006.[14]MichaelKBergman.Whitepaper:thedeepweb:surfacinghiddenvalue.Journalofelectronicpublishing,7(1),2001.[15]AustinMatthewsWaleedAmmarArchnaBhatia,WestonFeely,GregHannemanEvaSchlingerSwabhaSwayamdipta,YuliaTsvetkov,andAlonLavieChrisDyer.Thecmumachinetranslationsystemsatwmt2014.ACL2014,page142,2014.[16]ErgunBiçiciandDenizYuret.Instanceselectionformachinetranslationusingfeaturedecayalgorithms.InProceedingsoftheSixthWorkshoponStatisticalMachineTranslation,pages272Œ283.AssociationforComputationalLinguistics,2011.[17]ErgunBiciciandDenizYuret.Instanceselectionformachinetranslationusingfeaturedecayalgorithms.InProceedingsoftheSixthWorkshoponStatisticalMachineTranslation,page272Œ283,2011.[18]ErgunBiçici,QunLiu,andAndyWay.Parallelfda5forfastdeploymentofaccuratestatisti-calmachinetranslationsystems.InProceedingsofACL2014NithWorkshoponStatisticalMachineTranslation.AssociationforComputationalLinguistics,2014.[19]MichaelBloodgoodandChrisCallison-Burch.Buckingthetrend:Large-scalecost-focusedactivelearningforstatisticalmachinetranslation.InProceedingsofthe48thAnnualMeetingoftheAssociationforComputationalLinguistics,page854Œ864,Uppsala,Sweden,July2010.AssociationforComputationalLinguistics.[20]OndrejBojar,ChristianBuck,ChrisCallison-Burch,ChristianFedermann,BarryHaddow,PhilippKoehn,ChristofMonz,MattPost,RaduSoricut,andLuciaSpecia.Findingsofthe2013workshoponstatisticalmachinetranslation.InProceedingsoftheEighthWorkshoponStatisticalMachineTranslation,pages1Œ44,2013.[21]OndrejBojar,ChristianBuck,ChristianFedermann,BarryHaddow,PhilippKoehn,Jo-hannesLeveling,ChristofMonz,PavelPecina,MattPost,HerveSaint-Amand,etal.Find-ingsofthe2014workshoponstatisticalmachinetranslation.InProceedingsoftheNinthWorkshoponStatisticalMachineTranslation,pages12Œ58.AssociationforComputationalLinguisticsBaltimore,MD,USA,2014.[22]PeterFBrown,PeterVDesouza,RobertLMercer,VincentJDellaPietra,andJeniferCLai.Class-basedn-grammodelsofnaturallanguage.Computationallinguistics,18(4):467Œ479,1992.[23]PeterFBrown,VincentJDellaPietra,StephenADellaPietra,andRobertLMercer.Themathematicsofstatisticalmachinetranslation:Parameterestimation.Computationallin-guistics,19(2):263Œ311,1993.113[24]C.Callison-BurchandM.Dredze.Creatingspeechandlanguagedatawithamazon'sme-chanicalturk.InProceedingsoftheNAACLHLT2010WorkshoponCreatingSpeechandLanguageDatawithAmazon'sMechanicalTurk,page1Œ12,2010.[25]ChrisCallison-Burch,PhilippKoehn,ChristofMonz,andJoshSchroeder.Findingsofthe2009WorkshoponStatisticalMachineTranslation.InProceedingsoftheFourthWorkshoponStatisticalMachineTranslation,Athens,Greece,March2009.AssociationforCompu-tationalLinguistics.[26]W.ChaoandZ.Li.Agraph-basedbilingualcorpusselectionapproachforSMT.InPro-ceedingsofthe25thPAsiaConferenceonLanguage,InformationandComputation,2011.[27]WenHanChaoandZhouJunLi.Improvedgraph-basedbilingualcorpusselectionwithsen-tencepairrankingforstatisticalmachinetranslation.In201123rdIEEEInternationalConferenceonToolswithIntelligence(ICTAI),pages446Œ451,November2011.[28]BoxingChen,RolandKuhn,andGeorgeFoster.Acomparisonofmixtureandvectorspacetechniquesfortranslationmodeladaptation.InProceedingsofAMTA.AssociationforCom-putationalLinguistics,2014.[29]DavidChiang.Ahierarchicalphrase-basedmodelforstatisticalmachinetranslation.InPro-ceedingsofthe43rdAnnualMeetingonAssociationforComputationalLinguistics,pages263Œ270.AssociationforComputationalLinguistics,2005.[30]ThomasM.CoverandJoyA.Thomas.ElementsofInformationTheory.Wiley-Interscience,NewYork,NY,USA,1991.ISBN0-471-06259-6.[31]SanjoyDasguptaandDanielHsu.Hierarchicalsamplingforactivelearning.InProceedingsofthe25thinternationalconferenceonMachinelearning,pages208Œ215.ACM,2008.[32]MichaelDenkowski,GregHanneman,andAlonLavie.TheCMU-Avenuefrench-englishtranslationsystem.InProceedingsoftheNAACL2012WorkshoponStatisticalMachineTranslation,2012.[33]M.Eck,S.Vogel,andA.Waibel.Lowcostportabilityforstatisticalmachinetranslationbasedinn-gramfrequencyandtf-idf.InInternationalWorkshoponSpokenLanguageTranslation(IWSLT),2005.[34]SaulehEetemadiandHayderRadha.Effectsofparallelcorpusselectiononstatisticalma-chinetranslationquality.InProceedingsofthePNorthwestRegionalNLPWorkshop,2010.[35]TomFawcett.Anintroductiontorocanalysis.Patternrecognitionletters,27(8):861Œ874,2006.[36]DanFeldman,MelanieSchmidt,andChristianSohler.Turningbigdataintotinydata:Constant-sizecoresetsfork-means,pcaandprojectiveclustering.InProceedingsoftheTwenty-FourthAnnualACM-SIAMSymposiumonDiscreteAlgorithms,pages1434Œ1453.SIAM,2013.114[37]IanFellows.wordcloud:WordClouds,2013.Rpackageversion2.4.[38]AlexFranzandThorstenBrants.Allourn-gramarebelongtoyou.GoogleMachineTranslationTeam,20,2006.[39]MichelGalleyandChristopherDManning.Asimpleandeffectivehierarchicalphrasereorderingmodel.InProceedingsoftheConferenceonEmpiricalMethodsinNaturalLan-guageProcessing,pages848Œ856.AssociationforComputationalLinguistics,2008.[40]R.Gangadharaiah,R.Brown,andJ.Carbonell.Activelearninginexample-basedmachinetranslation.InProceedingsofthe17thNordicConferenceofComputationalLinguisticsNODALIDA,2009.[41]JoshuaGoodmanandJianfengGao.Languagemodelsizereductionbypruningandclus-tering.InINTERSPEECH,pages110Œ113,2000.[42]Google.GoogleBooksNgramViewer.books.google.com/ngrams|.URLhttp://books.google.com/ngrams.[43]G.Haffari.MachineLearningApproachesforDealingwithLimitedBilingualTrainingDatainStatisticalMachineTranslation.PhDthesis,SIMONFRASERUNIVERSITY,2009.[44]G.Haffari,M.Roy,andA.Sarkar.Activelearningforstatisticalphrase-basedmachinetranslation.InProceedingsofHumanLanguageTechnologies:The2009AnnualConfer-enceoftheNorthAmericanChapteroftheAssociationforComputationalLinguistics,page415Œ423,2009.[45]XiwuHan,HanzhangLi,andTiejunZhao.Trainthemachinewithwhatitcanlearn:corpusselectionforSMT.InProceedingsofthe2ndWorkshoponBuildingandUsingComparableCorpora:fromParalleltoNon-parallelCorpora,BUCC'09,page27Œ33,Stroudsburg,PA,USA,2009.AssociationforComputationalLinguistics.ISBN978-1-932432-53-4.[46]KennethKenlm:Fasterandsmallerlanguagemodelqueries.InProceedingsoftheSixthWorkshoponStatisticalMachineTranslation,pages187Œ197.AssociationforComputationalLinguistics,2011.[47]MarkHopkinsandJonathanMay.Tuningasranking.InProceedingsoftheConferenceonEmpiricalMethodsinNaturalLanguageProcessing,pages1352Œ1362.AssociationforComputationalLinguistics,2011.[48]ZahurulIslamandAlexanderMehler.Customizationoftheeuroparlcorpusfortranslationstudies.InLREC,page2505Œ2510,2012.[49]J.Jiang,A.Way,andJ.Carson-Berndsen.Latticescorebaseddatacleaningforphrase-basedstatisticalmachinetranslation.2010.[50]DanJurafskyandJamesHMartin.Speech&languageprocessing.PearsonEducationIndia,2000.[51]D.Kauchak.Contributionstoresearchonmachinetranslation.ProQuest,2006.115[52]S.KhadiviandH.Ney.Automaticofbilingualcorporaforstatisticalmachinetranslation.NaturalLanguageProcessingandInformationSystems,page263Œ274,2005.[53]KatrinKirchhoffandJeffBilmes.Submodularityfordataselectioninmachinetranslation.InEmpiricalMethodsinNaturalLanguageProcessing(EMNLP),October2014.[54]ReinhardKneserandHermannNey.Improvedbacking-offform-gramlanguagemodel-ing.InAcoustics,Speech,andSignalProcessing,1995.ICASSP-95.,1995InternationalConferenceon,volume1,pages181Œ184.IEEE,1995.[55]KevinKnight.Astatisticalmttutorialworkbook,1999.[56]PhilippKoehn.Europarl:AParallelCorpusforStatisticalMachineTranslation.InConfer-enceProceedings:thetenthMachineTranslationSummit,pages79Œ86,Phuket,Thailand,2005.AAMT,AAMT.[57]PhilippKoehn.Statisticalmachinetranslation.CambridgeUniversityPress,2009.[58]PhilippKoehn,FranzJosefOch,andDanielMarcu.Statisticalphrase-basedtranslation.InProceedingsofthe2003ConferenceoftheNorthAmericanChapteroftheAssociationforComputationalLinguisticsonHumanLanguageTechnology-Volume1,pages48Œ54.AssociationforComputationalLinguistics,2003.[59]MosheKoppelandNoamOrdan.Translationeseanditsdialects.InProceedingsofthe49thAnnualMeetingoftheAssociationforComputationalLinguistics:HumanLanguageTechnologies-Volume1,page1318Œ1326.AssociationforComputationalLinguistics,2011.[60]DavidKurokawa,CyrilGoutte,andPierreIsabelle.Automaticdetectionoftranslatedtextanditsimpactonmachinetranslation.Proceedings.MTSummitXII,ThetwelfthMachineTranslationSummitInternationalAssociationforMachineTranslationhostedbytheAsso-ciationforMachineTranslationintheAmericas,2009.[61]Y.Lü,J.Huang,andQ.Liu.Improvingstatisticalmachinetranslationperformancebytrainingdataselectionandoptimization.InProceedingsofthe2007JointConferenceonEmpiricalMethodsinNaturalLanguageProcessingandComputationalNaturalLanguageLearning(EMNLP-CoNLL),page343Œ350,2007.[62]JLangford,LLi,andAStrehl.Vowpalwabbitonlinelearningproject,2007.[63]GennadiLembersky,NoamOrdan,andShulyWintner.AdaptingtranslationmodelstotranslationeseimprovesSMT.InProceedingsofthe13thConferenceoftheEuropeanChapteroftheAssociationforComputationalLinguistics,page255Œ265.AssociationforComputationalLinguistics,2012.[64]GennadiLembersky,NoamOrdan,andShulyWintner.Languagemodelsformachinetrans-lation:Originalvs.translatedtexts.ComputationalLinguistics,38(4):799Œ825,2012.[65]GennadiLembersky,NoamOrdan,andShulyWintner.Improvingstatisticalmachinetrans-lationbyadaptingtranslationmodelstotranslationese.2013.116[66]WilliamLewisandSaulehEetemadi.Dramaticallyreducingtrainingdatasizethroughvo-cabularysaturation.InProceedingsoftheEighthWorkshoponStatisticalMachineTransla-tion,page281Œ291,Bulgaria,August2013.AssociationforComputationalLinguis-tics.[67]WilliamD.Lewis,ChristianFedermann,andYingXin.Applyingcross-entropydif-ferenceforselectingparalleltrainingdatafrompubliclyavailablesourcesforconver-sationalmachinetranslation.InProceedingsofIWSLT2015,December2015.URLhttp://research.microsoft.com/apps/pubs/default.aspx?id=259751.[68]P.Liu,Y.Zhou,andC.Zong.Approachtoselectingbestdevelopmentsetforphrase-basedstatisticalmachinetranslation.Proc.ofthe23rdPACLIC,Hongkong,page325Œ334,2009.[69]P.Liu,Y.Zhou,andC.Zong.Dataselectionforstatisticalmachinetranslation.InNaturalLanguageProcessingandKnowledgeEngineering(NLP-KE),2010InternationalConfer-enceon,page1Œ5,2010.[70]P.Liu,Y.Zhou,andC.Q.Zong.Approachestoimprovingcorpusqualityforstatisticalmachinetranslation.InMachineLearningandCybernetics(ICMLC),2010InternationalConferenceon,volume6,page3293Œ3298,2010.[71]A.Mandal,D.Vergyri,W.Wang,J.Zheng,A.Stolcke,G.Tur,D.Hakkani-Tur,andN.F.Ayan.Efdataselectionformachinetranslation.InSpokenLanguageTechnologyWorkshop,2008.SLT2008.IEEE,page261Œ264,2008.[72]ChristopherDManningandHinrichSchütze.Foundationsofstatisticalnaturallanguageprocessing.MITpress,1999.[73]MitchellP.Marcus,MaryAnnMarcinkiewicz,andBeatriceSantorini.Buildingalargeannotatedcorpusofenglish:Thepenntreebank.Comput.Linguist.,19(2):313Œ330,June1993.ISSN0891-2017.[74]RobertC.MooreandWilliamLewis.Intelligentselectionoflanguagemodeltrainingdata.InProceedingsoftheACL2010ConferenceShortPapers,page220Œ224,2010.[75]RobertC.MooreandChrisQuirk.Fasterbeam-searchdecodingforphrasalstatisticalma-chinetranslation.InProceedingsofMTSummitXI.EuropeanAssociationforMachineTranslation,September2007.[76]DragosStefanMunteanuandDanielMarcu.Improvingmachinetranslationperformancebyexploitingnon-parallelcorpora.ComputationalLinguistics,31(4):477Œ504,2005.[77]AndrewNgandMichaelJordan.Ondiscriminativevs.generativeAcomparisonoflogisticregressionandnaivebayes.AdvancesinNIPS14,2002.[78]AlexandrosNtoulas,MarcNajork,MarkManasse,andDennisFetterly.Detectingspamwebpagesthroughcontentanalysis.InProceedingsofthe15thinternationalconferenceonWorldWideWeb,pages83Œ92.ACM,2006.117[79]FranzJosefOch.Minimumerrorratetraininginstatisticalmachinetranslation.InProceed-ingsofthe41stACL,Sapporo,Japan,2003.[80]T.Okita.Datacleaningforwordalignment.InProceedingsoftheACL-IJCNLP2009StudentResearchWorkshop,page72Œ80,2009.[81]T.Okita,S.K.Naskar,andA.Way.Noisereductionexperimentsinmachinetranslation.[82]KishorePapineni,SalimRoukos,ToddWard,andWei-JingZhu.Bleu:Amethodforauto-maticevaluationofmachinetranslation.InProceedingsofthe40thAnnualMeetingonAs-sociationforComputationalLinguistics,ACL'02,pages311Œ318,Stroudsburg,PA,USA,2002.AssociationforComputationalLinguistics.[83]KishorePapineni,SalimRoukos,ToddWard,andWei-JingZhu.Bleu:amethodforau-tomaticevaluationofmachinetranslation.InProceedingsofthe40thannualmeetingonassociationforcomputationallinguistics,pages311Œ318.AssociationforComputationalLinguistics,2002.[84]ChrisQuirkandArulMenezes.Doweneedphrases?:Challengingtheconventionalwis-dominstatisticalmachinetranslation.InProceedingsoftheMainConferenceonHumanLanguageTechnologyConferenceoftheNorthAmericanChapteroftheAssociationofComputationalLinguistics,HLT-NAACL'06,pages9Œ16,Stroudsburg,PA,USA,2006.AssociationforComputationalLinguistics.[85]ChrisQuirk,ArulMenezes,andColinCherry.Dependencytreetranslation:Syntacticallyinformedphrasalsmt.InProceedingsofACL2005,2005.[86]PhilipResnik.Miningthewebforbilingualtext.InProceedingsofthe37thannualmeetingoftheAssociationforComputationalLinguisticsonComputationalLinguistics,pages527Œ534.AssociationforComputationalLinguistics,1999.[87]HinrichSchütze,EmreVelipasaoglu,andJanOPedersen.PerformancethresholdinginpracticaltextInProceedingsofthe15thACMinternationalconferenceonInformationandknowledgemanagement,pages662Œ671.ACM,2006.[88]BurrSettles.Activelearningliteraturesurvey.UniversityofWisconsin,Madison,52:55Œ66,2010.[89]ClaudeElwoodShannon.Amathematicaltheoryofcommunication.ACMSIGMOBILEMobileComputingandCommunicationsReview,2001.[90]MatthewSnover,BonnieDorr,RichardSchwartz,LinneaMicciulla,andJohnMakhoul.Astudyoftranslationeditratewithtargetedhumanannotation.InProceedingsofassociationformachinetranslationintheAmericas,pages223Œ231,2006.[91]L.Specia,D.Raj,andM.Turchi.Machinetranslationevaluationversusqualityestimation.Machinetranslation,24(1):39Œ50,2010.118[92]RalfSteinberger,BrunoPouliquen,AnnaWidiger,CameliaIgnat,TErjavec,andDanT¸s.TheJRC-Acquis:amultilingualalignedparallelcorpuswith20+languages.InInProceedingsofthe5thInternationalConferenceonLanguageResourcesandEvaluation(LREC'2006,page2142Œ2147,2006.[93]AndreasStolckeetal.Srilm-anextensiblelanguagemodelingtoolkit.InINTERSPEECH,2002.[94]IlyaSutskever,OriolVinyals,andQuocVVLe.Sequencetosequencelearningwithneuralnetworks.InAdvancesinneuralinformationprocessingsystems,pages3104Œ3112,2014.[95]K.Taghipour,N.Afhami,S.Khadivi,andS.Shiry.Adiscriminativeapproachtooutnoisysentencepairsfrombilingualcorpora.In20105thInternationalSymposiumonTelecommunications(IST),pages537Œ541,December2010.[96]KristinaToutanovaandChristopherD.Manning.Enrichingtheknowledgesourcesusedinamaximumentropypart-of-speechtagger.InProceedingsofthe2000JointSIGDATConfer-enceonEmpiricalMethodsinNaturalLanguageProcessingandVeryLargeCorpora:HeldinConjunctionwiththe38thAnnualMeetingoftheAssociationforComputationalLinguis-tics-Volume13,EMNLP'00,pages63Œ70,Stroudsburg,PA,USA,2000.AssociationforComputationalLinguistics.[97]NaamaTwitto-Shmuel.ImprovingStatisticalMachineTranslationbyAutomatictionofTranslationese.PhDthesis,UniversityofHaifa,2013.[98]NicolaUefandHermannNey.Word-levelestimationformachinetransla-tion.ComputationalLinguistics,33(1):9Œ40,2007.[99]StephanVogel,HermannNey,andChristophTillmann.Hmm-basedwordalignmentinstatisticaltranslation.InProceedingsofthe16thConferenceonComputationalLinguistics-Volume2,COLING'96,pages836Œ841,Stroudsburg,PA,USA,1996.AssociationforComputationalLinguistics.[100]StephanVogel,HermannNey,andChristophTillmann.Hmm-basedwordalignmentinstatisticaltranslation.InProceedingsofthe16thconferenceonComputationallinguistics-Volume2,pages836Œ841.AssociationforComputationalLinguistics,1996.[101]VeredVolansky,NoamOrdan,andShulyWintner.Onthefeaturesoftranslationese.LiteraryandLinguisticComputing,pagefqt031,2013.[102]TaroWatanabe,JunSuzuki,HajimeTsukada,andHidekiIsozaki.Onlinelarge-margintrainingforstatisticalmachinetranslation.InInProc.ofEMNLP,2007.[103]WarrenWeaver.Translation.Machinetranslationoflanguages,14:15Œ23,1955.[104]KaiWei,YuzongLiu,KatrinKirchhoff,andJeffBilmes.Usingdocumentsummarizationtechniquesforspeechdatasubsetselection.InProceedingsofNAACL-HLT,page721Œ726,2013.119[105]Worldwidewebsize.ThesizeoftheWorldWideWeb(WorldWideWebSize.com).World-WideWebSize.com|.URLhttp://www.worldwidewebsize.com/.[106]JoernWuebker,ArneMauser,andHermannNey.Trainingphrasetranslationmodelswithleaving-one-out.InProceedingsofthe48thAnnualMeetingoftheAssociationforCompu-tationalLinguistics,pages475Œ484.AssociationforComputationalLinguistics,2010.[107]DavidYarowsky.Unsupervisedwordsensedisambiguationrivalingsupervisedmethods.InProceedingsofthe33rdannualmeetingonAssociationforComputationalLinguistics,pages189Œ196.AssociationforComputationalLinguistics,1995.[108]K.Yasuda,R.Zhang,H.Yamamoto,andE.Sumita.Methodofselectingtrainingdatatobuildacompactandeftranslationmodel.InProceedingsoftheThirdInternationalJointConferenceonNaturalLanguageProcessing,volume2,page655Œ660,2008.[109]RichardZens,FranzJosefOch,andHermannNey.Phrase-basedstatisticalmachinetrans-lation.InKI2002:AdvancesinIntelligence,pages18Œ32.Springer,2002.[110]RichardZens,DaisyStanton,andPengXu.Asystematiccomparisonofphrasetableprun-ingtechniques.InProceedingsofthe2012JointConferenceonEmpiricalMethodsinNat-uralLanguageProcessingandComputationalNaturalLanguageLearning,pages972Œ983.AssociationforComputationalLinguistics,2012.[111]HuiZhang,KristinaToutanova,ChrisQuirk,andJianfengGao.Beyondleft-to-right:Mul-tipledecompositionstructuresforsmt.InHLT-NAACL,pages12Œ21,2013.120