De-En, Ja-En, Ro-En
EXTRACTIVE
De-En, Ja-En, Ro-En
EXTRACTIVE
We evaluated our attention transformations on three language pairs. We focused on small datasets, as they are the most affected by coverage mistakes. We use the IWSLT 2014 corpus for De-En, the KFTT corpus for Ja-En BIBREF19 , and the WMT 2016 dataset for Ro-En. The training sets have 153,326, 329,882, and 560,767 parallel sentences, respectively. Our reason to prefer smaller datasets is that this regime is what brings more adequacy issues and demands more structural biases, hence it is a good test bed for our methods. We tokenized the data using the Moses scripts and preprocessed it with subword units BIBREF20 with a joint vocabulary and 32k merge operations. Our implementation was done on a fork of the OpenNMT-py toolkit BIBREF21 with the default parameters . We used a validation set to tune hyperparameters introduced by our model. Even though our attention implementations are CPU-based using NumPy (unlike the rest of the computation which is done on the GPU), we did not observe any noticeable slowdown using multiple devices.
We evaluated our attention transformations on three language pairs. We focused on small datasets, as they are the most affected by coverage mistakes. We use the IWSLT 2014 corpus for De-En, the KFTT corpus for Ja-En BIBREF19 , and the WMT 2016 dataset for Ro-En. The training sets have 153,326, 329,882, and 560,767 parallel sentences, respectively. Our reason to prefer smaller datasets is that this regime is what brings more adequacy issues and demands more structural biases, hence it is a good test bed for our methods. We tokenized the data using the Moses scripts and preprocessed it with subword units BIBREF20 with a joint vocabulary and 32k merge operations. Our implementation was done on a fork of the OpenNMT-py toolkit BIBREF21 with the default parameters . We used a validation set to tune hyperparameters introduced by our model. Even though our attention implementations are CPU-based using NumPy (unlike the rest of the computation which is done on the GPU), we did not observe any noticeable slowdown using multiple devices.
1805.08241
Introduction </s> Ne ural Ġmachine Ġtranslation Ġ( N MT ) Ġemerged Ġin Ġthe Ġlast Ġfew Ġyears Ġas Ġa Ġvery Ġsuccessful Ġparadigm ĠB IB REF 0 Ġ, ĠB IB REF 1 Ġ, ĠB IB REF 2 Ġ, ĠB IB REF 3 Ġ. ĠWhile ĠN MT Ġis Ġgenerally Ġmore Ġfluent Ġthan Ġprevious Ġstatistical Ġsystems , Ġadequ acy Ġis Ġstill Ġa Ġmajor Ġconcern ĠB IB REF 4 Ġ: Ġcommon Ġmistakes Ġinclude Ġdropping Ġsource Ġwords Ġand Ġrepeating Ġwords Ġin Ġthe Ġgenerated Ġtranslation . </s> Previous Ġwork Ġhas Ġattempted Ġto Ġmitigate Ġthis Ġproblem Ġin Ġvarious Ġways . ĠB IB REF 5 Ġincorporate Ġcoverage Ġand Ġlength Ġpenalties Ġduring Ġbeam Ġsearch âĢĶ a Ġsimple Ġyet Ġlimited Ġsolution , Ġsince Ġit Ġonly Ġaffects Ġthe Ġscores Ġof Ġtranslation Ġhypotheses Ġthat Ġare Ġalready Ġin Ġthe Ġbeam . ĠOther Ġapproaches Ġinvolve Ġarchitectural Ġchanges : Ġproviding Ġcoverage Ġvectors Ġto Ġtrack Ġthe Ġattention Ġhistory ĠB IB REF 6 Ġ, ĠB IB REF 7 Ġ, Ġusing Ġg ating Ġarchitectures Ġand Ġadaptive Ġattention Ġto Ġcontrol Ġthe Ġamount Ġof Ġsource Ġcontext Ġprovided ĠB IB REF 8 Ġ, ĠB IB REF 9 Ġ, Ġor Ġadding Ġa Ġreconstruction Ġloss ĠB IB REF 10 Ġ. ĠB IB REF 11 Ġalso Ġuse Ġthe Ġnotion Ġof Ġfertility Ġimplicitly Ġin Ġtheir Ġproposed Ġmodel . ĠTheir ĠâĢ ľ f ertility Ġconditioned Ġdec oder âĢ Ŀ Ġuses Ġa Ġcoverage Ġvector Ġand Ġan ĠâĢ ľ ext ract Ġgate âĢ Ŀ Ġwhich Ġare Ġincorporated Ġin Ġthe Ġdecoding Ġrecurrent Ġunit , Ġincreasing Ġthe Ġnumber Ġof Ġparameters . </s> In Ġthis Ġpaper , Ġwe Ġpropose Ġa Ġdifferent Ġsolution Ġthat Ġdoes Ġnot Ġchange Ġthe Ġoverall Ġarchitecture , Ġbut Ġonly Ġthe Ġattention Ġtransformation . ĠName ly , Ġwe Ġreplace Ġthe Ġtraditional Ġsoft max Ġby Ġother Ġrecently Ġproposed Ġtransformations Ġthat Ġeither Ġpromote Ġattention Ġsp arsity ĠB IB REF 12 Ġor Ġupper Ġbound Ġthe Ġamount Ġof Ġattention Ġa Ġword Ġcan Ġreceive ĠB IB REF 13 Ġ. ĠThe Ġbounds Ġare Ġdetermined Ġby Ġthe Ġfertility Ġvalues Ġof Ġthe Ġsource Ġwords . ĠWhile Ġthese Ġtransformations Ġhave Ġgiven Ġencouraging Ġresults Ġin Ġvarious ĠN LP Ġproblems , Ġthey Ġhave Ġnever Ġbeen Ġapplied Ġto ĠN MT , Ġto Ġthe Ġbest Ġof Ġour Ġknowledge . ĠFurthermore , Ġwe Ġcombine Ġthese Ġtwo Ġideas Ġand Ġpropose Ġa Ġnovel Ġattention Ġtransformation , Ġconstrained Ġsparse max , Ġwhich Ġproduces Ġboth Ġsparse Ġand Ġbounded Ġattention Ġweights , Ġyielding Ġa Ġcompact Ġand Ġinterpret able Ġset Ġof Ġalign ments . ĠWhile Ġbeing Ġin - between Ġsoft Ġand Ġhard Ġalign ments Ġ( Figure ĠFIG REF 20 Ġ), Ġthe Ġconstrained Ġsparse max Ġtransformation Ġis Ġend - to - end Ġdifferent iable , Ġhence Ġam enable Ġfor Ġtraining Ġwith Ġgradient Ġback prop ag ation . </s> To Ġsum Ġup , Ġour Ġcontributions Ġare Ġas Ġfollows : </s> P rel im in aries </s> Our Ġunderlying Ġmodel Ġarchitecture Ġis Ġa Ġstandard Ġattention al Ġenc oder - dec oder ĠB IB REF 1 Ġ. ĠLet ĠIN LINE FORM 0 Ġand ĠIN LINE FORM 1 Ġdenote Ġthe Ġsource Ġand Ġtarget Ġsentences , Ġrespectively . ĠWe Ġuse Ġa ĠBi - L ST M Ġenc oder Ġto Ġrepresent Ġthe Ġsource Ġwords Ġas Ġa Ġmatrix ĠIN LINE FORM 2 Ġ. ĠThe Ġconditional Ġprobability Ġof Ġthe Ġtarget Ġsentence Ġis Ġgiven Ġas ĠDIS PLAY FORM 0 </s> where ĠIN LINE FORM 0 Ġis Ġcomputed Ġby Ġa Ġsoft max Ġoutput Ġlayer Ġthat Ġreceives Ġa Ġdec oder Ġstate ĠIN LINE FORM 1 Ġas Ġinput . ĠThis Ġstate Ġis Ġupdated Ġby Ġan Ġauto - reg ressive ĠL ST M , ĠIN LINE FORM 2 Ġ, Ġwhere ĠIN LINE FORM 3 Ġis Ġan Ġinput Ġcontext Ġvector . ĠThis Ġvector Ġis Ġcomputed Ġas ĠIN LINE FORM 4 Ġ, Ġwhere ĠIN LINE FORM 5 Ġis Ġa Ġprobability Ġdistribution Ġthat Ġrepresents Ġthe Ġattention Ġover Ġthe Ġsource Ġwords , Ġcommonly Ġobtained Ġas ĠDIS PLAY FORM 0 </s> where ĠIN LINE FORM 0 Ġis Ġa Ġvector Ġof Ġscores . ĠWe Ġfollow ĠB IB REF 14 Ġand Ġdefine ĠIN LINE FORM 1 Ġas Ġa Ġbil in ear Ġtransformation Ġof Ġenc oder Ġand Ġdec oder Ġstates , Ġwhere ĠIN LINE FORM 2 Ġis Ġa Ġmodel Ġparameter . </s> S parse Ġand ĠCon str ained ĠAttention </s> In Ġthis Ġwork , Ġwe Ġconsider Ġalternatives Ġto ĠE q . ĠEQ REF 5 Ġ. ĠSince Ġthe Ġsoft max Ġis Ġstrictly Ġpositive , Ġit Ġforces Ġall Ġwords Ġin Ġthe Ġsource Ġto Ġreceive Ġsome Ġprobability Ġmass Ġin Ġthe Ġresulting Ġattention Ġdistribution , Ġwhich Ġcan Ġbe Ġwasteful . ĠMoreover , Ġit Ġmay Ġhappen Ġthat Ġthe Ġdec oder Ġattends Ġrepeatedly Ġto Ġthe Ġsame Ġsource Ġwords Ġacross Ġtime Ġsteps , Ġcausing Ġrepet itions Ġin Ġthe Ġgenerated Ġtranslation , Ġas ĠB IB REF 7 Ġobserved . </s> With Ġthis Ġin Ġmind , Ġwe Ġreplace ĠE q . ĠEQ REF 5 Ġby ĠIN LINE FORM 0 Ġ, Ġwhere ĠIN LINE FORM 1 Ġis Ġa Ġtransformation Ġthat Ġmay Ġdepend Ġboth Ġon Ġthe Ġscores ĠIN LINE FORM 2 Ġand Ġon Ġupper Ġbounds ĠIN LINE FORM 3 Ġthat Ġlimit Ġthe Ġamount Ġof Ġattention Ġthat Ġeach Ġword Ġcan Ġreceive . ĠWe Ġconsider Ġthree Ġalternatives Ġto Ġsoft max , Ġdescribed Ġnext . </s> F ertility ĠB ounds </s> We Ġexperiment Ġwith Ġthree Ġways Ġof Ġsetting Ġthe Ġfertility Ġof Ġthe Ġsource Ġwords : Ġconstant , Ġguided , Ġand Ġpredicted . ĠWith Ġconstant , Ġwe Ġset Ġthe Ġfert ilities Ġof Ġall Ġsource Ġwords Ġto Ġa Ġfixed Ġinteger Ġvalue ĠIN LINE FORM 0 Ġ. ĠWith Ġguided , Ġwe Ġtrain Ġa Ġword Ġalign er Ġbased Ġon ĠIBM ĠModel Ġ2 Ġ( we Ġused Ġfast _ align Ġin Ġour Ġexperiments , ĠB IB REF 17 Ġ) Ġand , Ġfor Ġeach Ġword Ġin Ġthe Ġvocabulary , Ġwe Ġset Ġthe Ġfert ilities Ġto Ġthe Ġmaximal Ġobserved Ġvalue Ġin Ġthe Ġtraining Ġdata Ġ( or Ġ1 Ġif Ġno Ġalignment Ġwas Ġobserved ). ĠWith Ġthe Ġpredicted Ġstrategy , Ġwe Ġtrain Ġa Ġseparate Ġfertility Ġpredictor Ġmodel Ġusing Ġa Ġbi - L ST M Ġtag ger . ĠAt Ġtraining Ġtime , Ġwe Ġprovide Ġas Ġsupervision Ġthe Ġfertility Ġestimated Ġby Ġfast _ align . ĠSince Ġour Ġmodel Ġworks Ġwith Ġfertility Ġupper Ġbounds Ġand Ġthe Ġword Ġalign er Ġmay Ġmiss Ġsome Ġword Ġpairs , Ġwe Ġfound Ġit Ġbeneficial Ġto Ġadd Ġa Ġconstant Ġto Ġthis Ġnumber Ġ( 1 Ġin Ġour Ġexperiments ). ĠAt Ġtest Ġtime , Ġwe Ġuse Ġthe Ġexpected Ġfert ilities Ġaccording Ġto Ġour Ġmodel . </s> Exper iments </s> We Ġevaluated Ġour Ġattention Ġtransformations Ġon Ġthree Ġlanguage Ġpairs . ĠWe Ġfocused Ġon Ġsmall Ġdatasets , Ġas Ġthey Ġare Ġthe Ġmost Ġaffected Ġby Ġcoverage Ġmistakes . ĠWe Ġuse Ġthe ĠI W SL T Ġ2014 Ġcorpus Ġfor ĠDe - En , Ġthe ĠK FT T Ġcorpus Ġfor ĠJa - En ĠB IB REF 19 Ġ, Ġand Ġthe ĠW MT Ġ2016 Ġdataset Ġfor ĠRo - En . ĠThe Ġtraining Ġsets Ġhave Ġ153 , 326 , Ġ329 , 882 , Ġand Ġ560 , 767 Ġparallel Ġsentences , Ġrespectively . ĠOur Ġreason Ġto Ġprefer Ġsmaller Ġdatasets Ġis Ġthat Ġthis Ġregime Ġis Ġwhat Ġbrings Ġmore Ġadequ acy Ġissues Ġand Ġdemands Ġmore Ġstructural Ġbiases , Ġhence Ġit Ġis Ġa Ġgood Ġtest Ġbed Ġfor Ġour Ġmethods . ĠWe Ġtoken ized Ġthe Ġdata Ġusing Ġthe ĠMoses Ġscripts Ġand Ġpre process ed Ġit Ġwith Ġsub word Ġunits ĠB IB REF 20 Ġwith Ġa Ġjoint Ġvocabulary Ġand Ġ32 k Ġmerge Ġoperations . ĠOur Ġimplementation Ġwas Ġdone Ġon Ġa Ġfork Ġof Ġthe ĠOpen N MT - py Ġtool kit ĠB IB REF 21 Ġwith Ġthe Ġdefault Ġparameters Ġ. ĠWe Ġused Ġa Ġvalidation Ġset Ġto Ġtune Ġhyper param eters Ġintroduced Ġby Ġour Ġmodel . ĠEven Ġthough Ġour Ġattention Ġimplementations Ġare ĠCPU - based Ġusing ĠNum Py Ġ( un like Ġthe Ġrest Ġof Ġthe Ġcomputation Ġwhich Ġis Ġdone Ġon Ġthe ĠGPU ), Ġwe Ġdid Ġnot Ġobserve Ġany Ġnoticeable Ġslowdown Ġusing Ġmultiple Ġdevices . </s> As Ġbas elines , Ġwe Ġuse Ġsoft max Ġattention , Ġas Ġwell Ġas Ġtwo Ġrecently Ġproposed Ġcoverage Ġmodels : </s> We Ġalso Ġexperimented Ġcombining Ġthe Ġstrategies Ġabove Ġwith Ġthe Ġsparse max Ġtransformation . </s> As Ġevaluation Ġmetrics , Ġwe Ġreport Ġtoken ized ĠB LE U , ĠMET E OR Ġ( ĠB IB REF 22 Ġ, Ġas Ġwell Ġas Ġtwo Ġnew Ġmetrics Ġthat Ġwe Ġdescribe Ġnext Ġto Ġaccount Ġfor Ġover Ġand Ġunder - translation . </s> Con clusions </s> We Ġproposed Ġa Ġnew Ġapproach Ġto Ġaddress Ġthe Ġcoverage Ġproblem Ġin ĠN MT , Ġby Ġreplacing Ġthe Ġsoft max Ġattention al Ġtransformation Ġby Ġsparse Ġand Ġconstrained Ġalternatives : Ġsparse max , Ġconstrained Ġsoft max , Ġand Ġthe Ġnewly Ġproposed Ġconstrained Ġsparse max . ĠFor Ġthe Ġlatter , Ġwe Ġderived Ġefficient Ġforward Ġand Ġbackward Ġpropagation Ġalgorithms . ĠBy Ġincorporating Ġa Ġmodel Ġfor Ġfertility Ġprediction , Ġour Ġattention Ġtransformations Ġled Ġto Ġsparse Ġalign ments , Ġavoiding Ġrepeated Ġwords Ġin Ġthe Ġtranslation . </s> Acknowled gments </s> We Ġthank Ġthe ĠUn b abel ĠAI ĠResearch Ġteam Ġfor Ġnumerous Ġdiscussions , Ġand Ġthe Ġthree Ġanonymous Ġreviewers Ġfor Ġtheir Ġinsightful Ġcomments . ĠThis Ġwork Ġwas Ġsupported Ġby Ġthe ĠEuropean ĠResearch ĠCouncil Ġ( ERC ĠSt G ĠDeep SP IN Ġ7 58 969 ) Ġand Ġby Ġthe ĠFund a Ã§ Ã£o Ġpara Ġa ĠCi Ãª nc ia Ġe ĠTec n olog ia Ġthrough Ġcontracts ĠUID / EE A / 5000 8 / 2013 , ĠPT DC / EE I - S II / 70 92 / 2014 Ġ( Learn Big ), Ġand ĠCM UP ER I / T IC / 00 46 / 2014 Ġ( Go Local ). </s> Proof Ġof ĠProposition Ġ </s> We Ġprovide Ġhere Ġa Ġdetailed Ġproof Ġof ĠProposition ĠSEC REF 15 Ġ. </s> Forward ĠProp ag ation </s> The Ġoptimization Ġproblem Ġcan Ġbe Ġwritten Ġas ĠDIS PLAY FORM 0 </s> The ĠLag rang ian Ġfunction Ġis : ĠDIS PLAY FORM 0 </s> To Ġobtain Ġthe Ġsolution , Ġwe Ġinvoke Ġthe ĠKar ush - K uh n - T ucker Ġconditions . ĠFrom Ġthe Ġstation arity Ġcondition , Ġwe Ġhave ĠIN LINE FORM 0 Ġ, Ġwhich Ġdue Ġto Ġthe Ġprimal Ġfeasibility Ġcondition Ġimplies Ġthat Ġthe Ġsolution Ġis Ġof Ġthe Ġform : ĠDIS PLAY FORM 0 </s> From Ġthe Ġcomplement arity Ġslack ness Ġcondition , Ġwe Ġhave Ġthat ĠIN LINE FORM 0 Ġimplies Ġthat ĠIN LINE FORM 1 Ġand Ġtherefore ĠIN LINE FORM 2 Ġ. ĠOn Ġthe Ġother Ġhand , ĠIN LINE FORM 3 Ġimplies ĠIN LINE FORM 4 Ġ, Ġand ĠIN LINE FORM 5 Ġimplies ĠIN LINE FORM 6 Ġ. ĠHence Ġthe Ġsolution Ġcan Ġbe Ġwritten Ġas ĠIN LINE FORM 7 Ġ, Ġwhere ĠIN LINE FORM 8 Ġis Ġdetermined Ġsuch Ġthat Ġthe Ġdistribution Ġnormal izes : ĠDIS PLAY FORM 0 </s> with ĠIN LINE FORM 0 Ġand ĠIN LINE FORM 1 Ġ. ĠNote Ġthat ĠIN LINE FORM 2 Ġdepends Ġitself Ġon Ġthe Ġset ĠIN LINE FORM 3 Ġ, Ġa Ġfunction Ġof Ġthe Ġsolution . ĠIn ĠÂ§ ĠSEC REF 44 Ġ, Ġwe Ġdescribe Ġan Ġalgorithm Ġthat Ġsearches Ġthe Ġvalue Ġof ĠIN LINE FORM 4 Ġefficiently . </s> Grad ient ĠBack prop ag ation </s> We Ġnow Ġturn Ġto Ġthe Ġproblem Ġof Ġback prop ag ating Ġthe Ġgrad ients Ġthrough Ġthe Ġconstrained Ġsparse max Ġtransformation . ĠFor Ġthat , Ġwe Ġneed Ġto Ġcompute Ġits ĠJacob ian Ġmatrix , Ġi . e ., Ġthe Ġderivatives ĠIN LINE FORM 0 Ġand ĠIN LINE FORM 1 Ġfor ĠIN LINE FORM 2 Ġ. ĠLet Ġus Ġfirst Ġexpress ĠIN LINE FORM 3 Ġas ĠDIS PLAY FORM 0 </s> with ĠIN LINE FORM 0 Ġas Ġin ĠE q . ĠEQ REF 37 Ġ. ĠNote Ġthat Ġwe Ġhave ĠIN LINE FORM 1 Ġand ĠIN LINE FORM 2 Ġ. ĠThus , Ġwe Ġhave Ġthe Ġfollowing : ĠDIS PLAY FORM 0 </s> and ĠDIS PLAY FORM 0 </s> Finally , Ġwe Ġobtain : ĠDIS PLAY FORM 0 </s> and ĠDIS PLAY FORM 0 </s> where ĠIN LINE FORM 0 Ġ. </s> [ t ] ĠP ard alos Ġand ĠKov oor 's ĠAl gorithm Ġ[ 1 ] Ġinput : ĠIN LINE FORM 0 ĠInitial ize Ġworking Ġset ĠIN LINE FORM 1 ĠInitial ize Ġset Ġof Ġsplit Ġpoints : ĠIN LINE FORM 2 </s> Initial ize ĠIN LINE FORM 0 Ġ, ĠIN LINE FORM 1 Ġ, ĠIN LINE FORM 2 Ġ, ĠIN LINE FORM 3 Ġ. ĠIN LINE FORM 4 ĠComp ute ĠIN LINE FORM 5 ĠSet ĠIN LINE FORM 6 ĠIf ĠIN LINE FORM 7 Ġ, Ġset ĠIN LINE FORM 8 Ġ; Ġif ĠIN LINE FORM 9 Ġ, Ġset ĠIN LINE FORM 10 ĠReduce Ġset Ġof Ġsplit Ġpoints : ĠIN LINE FORM 11 ĠUpdate Ġtight - sum : ĠIN LINE FORM 12 ĠUpdate Ġslack - sum : ĠIN LINE FORM 13 ĠUpdate Ġworking Ġset : ĠIN LINE FORM 14 ĠDef ine ĠIN LINE FORM 15 ĠSet ĠIN LINE FORM 16 Ġoutput : ĠIN LINE FORM 17 Ġ. </s> Lin ear - Time ĠEvaluation </s> Finally , Ġwe Ġpresent Ġan Ġalgorithm Ġto Ġsolve Ġthe Ġproblem Ġin ĠE q . ĠEQ REF 14 Ġin Ġlinear Ġtime . </s> BI B REF 16 Ġdescribe Ġan Ġalgorithm , Ġreproduced Ġhere Ġas ĠAl gorithm ĠSEC REF 38 Ġ, Ġfor Ġsolving Ġa Ġclass Ġof Ġsing ly - con str ained Ġconve x Ġquad r atic Ġproblems , Ġwhich Ġcan Ġbe Ġwritten Ġin Ġthe Ġform Ġabove Ġ( where Ġeach ĠIN LINE FORM 0 Ġ): ĠDIS PLAY FORM 0 </s> The Ġsolution Ġof Ġthe Ġproblem Ġin ĠE q . ĠEQ REF 45 Ġis Ġof Ġthe Ġform ĠIN LINE FORM 0 Ġ, Ġwhere ĠIN LINE FORM 1 Ġis Ġa Ġconstant . ĠThe Ġalgorithm Ġsearches Ġthe Ġvalue Ġof Ġthis Ġconstant Ġ( which Ġis Ġsimilar Ġto ĠIN LINE FORM 2 Ġin Ġour Ġproblem ), Ġwhich Ġlies Ġin Ġa Ġparticular Ġinterval Ġof Ġsplit - points Ġ( line ĠSEC REF 38 Ġ), Ġiter atively Ġshrinking Ġthis Ġinterval . ĠThe Ġalgorithm Ġrequires Ġcomputing Ġmed ians Ġas Ġa Ġsub r outine , Ġwhich Ġcan Ġbe Ġdone Ġin Ġlinear Ġtime ĠB IB REF 24 Ġ. ĠThe Ġoverall Ġcomplexity Ġin ĠIN LINE FORM 3 ĠB IB REF 16 Ġ. ĠThe Ġsame Ġalgorithm Ġhas Ġbeen Ġused Ġin ĠN LP Ġby ĠB IB REF 23 Ġfor Ġa Ġbudget ed Ġsummar ization Ġproblem . </s> To Ġshow Ġthat Ġthis Ġalgorithm Ġapplies Ġto Ġthe Ġproblem Ġof Ġevaluating ĠIN LINE FORM 0 Ġ, Ġit Ġsuff ices Ġto Ġshow Ġthat Ġour Ġproblem Ġin ĠE q . ĠEQ REF 14 Ġcan Ġbe Ġrewritten Ġin Ġthe Ġform Ġof ĠE q . ĠEQ REF 45 Ġ. ĠThis Ġis Ġindeed Ġthe Ġcase , Ġif Ġwe Ġset : ĠDIS PLAY FORM 0 </s> Examples Ġof ĠTrans lations </s> We Ġshow Ġsome Ġexamples Ġof Ġtranslations Ġobtained Ġfor Ġthe ĠGerman - English Ġlanguage Ġpair Ġwith Ġdifferent Ġsystems . ĠBlue Ġhighlights Ġthe Ġparts Ġof Ġthe Ġreference Ġthat Ġare Ġcorrect Ġand Ġred Ġhighlights Ġthe Ġcorresponding Ġproblematic Ġparts Ġof Ġtranslations , Ġincluding Ġrepet itions , Ġdropped Ġwords Ġor Ġmist rans lations .
Introduction Neural machine translation (NMT) emerged in the last few years as a very successful paradigm BIBREF0 , BIBREF1 , BIBREF2 , BIBREF3 . While NMT is generally more fluent than previous statistical systems, adequacy is still a major concern BIBREF4 : common mistakes include dropping source words and repeating words in the generated translation. Previous work has attempted to mitigate this problem in various ways. BIBREF5 incorporate coverage and length penalties during beam search—a simple yet limited solution, since it only affects the scores of translation hypotheses that are already in the beam. Other approaches involve architectural changes: providing coverage vectors to track the attention history BIBREF6 , BIBREF7 , using gating architectures and adaptive attention to control the amount of source context provided BIBREF8 , BIBREF9 , or adding a reconstruction loss BIBREF10 . BIBREF11 also use the notion of fertility implicitly in their proposed model. Their “fertility conditioned decoder” uses a coverage vector and an “extract gate” which are incorporated in the decoding recurrent unit, increasing the number of parameters. In this paper, we propose a different solution that does not change the overall architecture, but only the attention transformation. Namely, we replace the traditional softmax by other recently proposed transformations that either promote attention sparsity BIBREF12 or upper bound the amount of attention a word can receive BIBREF13 . The bounds are determined by the fertility values of the source words. While these transformations have given encouraging results in various NLP problems, they have never been applied to NMT, to the best of our knowledge. Furthermore, we combine these two ideas and propose a novel attention transformation, constrained sparsemax, which produces both sparse and bounded attention weights, yielding a compact and interpretable set of alignments. While being in-between soft and hard alignments (Figure FIGREF20 ), the constrained sparsemax transformation is end-to-end differentiable, hence amenable for training with gradient backpropagation. To sum up, our contributions are as follows: Preliminaries Our underlying model architecture is a standard attentional encoder-decoder BIBREF1 . Let INLINEFORM0 and INLINEFORM1 denote the source and target sentences, respectively. We use a Bi-LSTM encoder to represent the source words as a matrix INLINEFORM2 . The conditional probability of the target sentence is given as DISPLAYFORM0 where INLINEFORM0 is computed by a softmax output layer that receives a decoder state INLINEFORM1 as input. This state is updated by an auto-regressive LSTM, INLINEFORM2 , where INLINEFORM3 is an input context vector. This vector is computed as INLINEFORM4 , where INLINEFORM5 is a probability distribution that represents the attention over the source words, commonly obtained as DISPLAYFORM0 where INLINEFORM0 is a vector of scores. We follow BIBREF14 and define INLINEFORM1 as a bilinear transformation of encoder and decoder states, where INLINEFORM2 is a model parameter. Sparse and Constrained Attention In this work, we consider alternatives to Eq. EQREF5 . Since the softmax is strictly positive, it forces all words in the source to receive some probability mass in the resulting attention distribution, which can be wasteful. Moreover, it may happen that the decoder attends repeatedly to the same source words across time steps, causing repetitions in the generated translation, as BIBREF7 observed. With this in mind, we replace Eq. EQREF5 by INLINEFORM0 , where INLINEFORM1 is a transformation that may depend both on the scores INLINEFORM2 and on upper bounds INLINEFORM3 that limit the amount of attention that each word can receive. We consider three alternatives to softmax, described next. Fertility Bounds We experiment with three ways of setting the fertility of the source words: constant, guided, and predicted. With constant, we set the fertilities of all source words to a fixed integer value INLINEFORM0 . With guided, we train a word aligner based on IBM Model 2 (we used fast_align in our experiments, BIBREF17 ) and, for each word in the vocabulary, we set the fertilities to the maximal observed value in the training data (or 1 if no alignment was observed). With the predicted strategy, we train a separate fertility predictor model using a bi-LSTM tagger. At training time, we provide as supervision the fertility estimated by fast_align. Since our model works with fertility upper bounds and the word aligner may miss some word pairs, we found it beneficial to add a constant to this number (1 in our experiments). At test time, we use the expected fertilities according to our model. Experiments We evaluated our attention transformations on three language pairs. We focused on small datasets, as they are the most affected by coverage mistakes. We use the IWSLT 2014 corpus for De-En, the KFTT corpus for Ja-En BIBREF19 , and the WMT 2016 dataset for Ro-En. The training sets have 153,326, 329,882, and 560,767 parallel sentences, respectively. Our reason to prefer smaller datasets is that this regime is what brings more adequacy issues and demands more structural biases, hence it is a good test bed for our methods. We tokenized the data using the Moses scripts and preprocessed it with subword units BIBREF20 with a joint vocabulary and 32k merge operations. Our implementation was done on a fork of the OpenNMT-py toolkit BIBREF21 with the default parameters . We used a validation set to tune hyperparameters introduced by our model. Even though our attention implementations are CPU-based using NumPy (unlike the rest of the computation which is done on the GPU), we did not observe any noticeable slowdown using multiple devices. As baselines, we use softmax attention, as well as two recently proposed coverage models: We also experimented combining the strategies above with the sparsemax transformation. As evaluation metrics, we report tokenized BLEU, METEOR ( BIBREF22 , as well as two new metrics that we describe next to account for over and under-translation. Conclusions We proposed a new approach to address the coverage problem in NMT, by replacing the softmax attentional transformation by sparse and constrained alternatives: sparsemax, constrained softmax, and the newly proposed constrained sparsemax. For the latter, we derived efficient forward and backward propagation algorithms. By incorporating a model for fertility prediction, our attention transformations led to sparse alignments, avoiding repeated words in the translation. Acknowledgments We thank the Unbabel AI Research team for numerous discussions, and the three anonymous reviewers for their insightful comments. This work was supported by the European Research Council (ERC StG DeepSPIN 758969) and by the Fundação para a Ciência e Tecnologia through contracts UID/EEA/50008/2013, PTDC/EEI-SII/7092/2014 (LearnBig), and CMUPERI/TIC/0046/2014 (GoLocal). Proof of Proposition  We provide here a detailed proof of Proposition SECREF15 . Forward Propagation The optimization problem can be written as DISPLAYFORM0 The Lagrangian function is: DISPLAYFORM0 To obtain the solution, we invoke the Karush-Kuhn-Tucker conditions. From the stationarity condition, we have INLINEFORM0 , which due to the primal feasibility condition implies that the solution is of the form: DISPLAYFORM0 From the complementarity slackness condition, we have that INLINEFORM0 implies that INLINEFORM1 and therefore INLINEFORM2 . On the other hand, INLINEFORM3 implies INLINEFORM4 , and INLINEFORM5 implies INLINEFORM6 . Hence the solution can be written as INLINEFORM7 , where INLINEFORM8 is determined such that the distribution normalizes: DISPLAYFORM0 with INLINEFORM0 and INLINEFORM1 . Note that INLINEFORM2 depends itself on the set INLINEFORM3 , a function of the solution. In § SECREF44 , we describe an algorithm that searches the value of INLINEFORM4 efficiently. Gradient Backpropagation We now turn to the problem of backpropagating the gradients through the constrained sparsemax transformation. For that, we need to compute its Jacobian matrix, i.e., the derivatives INLINEFORM0 and INLINEFORM1 for INLINEFORM2 . Let us first express INLINEFORM3 as DISPLAYFORM0 with INLINEFORM0 as in Eq. EQREF37 . Note that we have INLINEFORM1 and INLINEFORM2 . Thus, we have the following: DISPLAYFORM0 and DISPLAYFORM0 Finally, we obtain: DISPLAYFORM0 and DISPLAYFORM0 where INLINEFORM0 . [t] Pardalos and Kovoor's Algorithm [1] input: INLINEFORM0 Initialize working set INLINEFORM1 Initialize set of split points: INLINEFORM2 Initialize INLINEFORM0 , INLINEFORM1 , INLINEFORM2 , INLINEFORM3 . INLINEFORM4 Compute INLINEFORM5 Set INLINEFORM6 If INLINEFORM7 , set INLINEFORM8 ; if INLINEFORM9 , set INLINEFORM10 Reduce set of split points: INLINEFORM11 Update tight-sum: INLINEFORM12 Update slack-sum: INLINEFORM13 Update working set: INLINEFORM14 Define INLINEFORM15 Set INLINEFORM16 output: INLINEFORM17 . Linear-Time Evaluation Finally, we present an algorithm to solve the problem in Eq. EQREF14 in linear time. BIBREF16 describe an algorithm, reproduced here as Algorithm SECREF38 , for solving a class of singly-constrained convex quadratic problems, which can be written in the form above (where each INLINEFORM0 ): DISPLAYFORM0 The solution of the problem in Eq. EQREF45 is of the form INLINEFORM0 , where INLINEFORM1 is a constant. The algorithm searches the value of this constant (which is similar to INLINEFORM2 in our problem), which lies in a particular interval of split-points (line SECREF38 ), iteratively shrinking this interval. The algorithm requires computing medians as a subroutine, which can be done in linear time BIBREF24 . The overall complexity in INLINEFORM3 BIBREF16 . The same algorithm has been used in NLP by BIBREF23 for a budgeted summarization problem. To show that this algorithm applies to the problem of evaluating INLINEFORM0 , it suffices to show that our problem in Eq. EQREF14 can be rewritten in the form of Eq. EQREF45 . This is indeed the case, if we set: DISPLAYFORM0 Examples of Translations We show some examples of translations obtained for the German-English language pair with different systems. Blue highlights the parts of the reference that are correct and red highlights the corresponding problematic parts of translations, including repetitions, dropped words or mistranslations.
What are the language pairs explored in this paper?
14b74ad5a6f5b0506511c9b454e9c464371ef8c4
What Ġare Ġthe Ġlanguage Ġpairs Ġexplored Ġin Ġthis Ġpaper ?
De - En , ĠJa - En , ĠRo - En
<s> What Ġare Ġthe Ġlanguage Ġpairs Ġexplored Ġin Ġthis Ġpaper ? </s> Introduction </s> Ne ural Ġmachine Ġtranslation Ġ( N MT ) Ġemerged Ġin Ġthe Ġlast Ġfew Ġyears Ġas Ġa Ġvery Ġsuccessful Ġparadigm ĠB IB REF 0 Ġ, ĠB IB REF 1 Ġ, ĠB IB REF 2 Ġ, ĠB IB REF 3 Ġ. ĠWhile ĠN MT Ġis Ġgenerally Ġmore Ġfluent Ġthan Ġprevious Ġstatistical Ġsystems , Ġadequ acy Ġis Ġstill Ġa Ġmajor Ġconcern ĠB IB REF 4 Ġ: Ġcommon Ġmistakes Ġinclude Ġdropping Ġsource Ġwords Ġand Ġrepeating Ġwords Ġin Ġthe Ġgenerated Ġtranslation . </s> Previous Ġwork Ġhas Ġattempted Ġto Ġmitigate Ġthis Ġproblem Ġin Ġvarious Ġways . ĠB IB REF 5 Ġincorporate Ġcoverage Ġand Ġlength Ġpenalties Ġduring Ġbeam Ġsearch âĢĶ a Ġsimple Ġyet Ġlimited Ġsolution , Ġsince Ġit Ġonly Ġaffects Ġthe Ġscores Ġof Ġtranslation Ġhypotheses Ġthat Ġare Ġalready Ġin Ġthe Ġbeam . ĠOther Ġapproaches Ġinvolve Ġarchitectural Ġchanges : Ġproviding Ġcoverage Ġvectors Ġto Ġtrack Ġthe Ġattention Ġhistory ĠB IB REF 6 Ġ, ĠB IB REF 7 Ġ, Ġusing Ġg ating Ġarchitectures Ġand Ġadaptive Ġattention Ġto Ġcontrol Ġthe Ġamount Ġof Ġsource Ġcontext Ġprovided ĠB IB REF 8 Ġ, ĠB IB REF 9 Ġ, Ġor Ġadding Ġa Ġreconstruction Ġloss ĠB IB REF 10 Ġ. ĠB IB REF 11 Ġalso Ġuse Ġthe Ġnotion Ġof Ġfertility Ġimplicitly Ġin Ġtheir Ġproposed Ġmodel . ĠTheir ĠâĢ ľ f ertility Ġconditioned Ġdec oder âĢ Ŀ Ġuses Ġa Ġcoverage Ġvector Ġand Ġan ĠâĢ ľ ext ract Ġgate âĢ Ŀ Ġwhich Ġare Ġincorporated Ġin Ġthe Ġdecoding Ġrecurrent Ġunit , Ġincreasing Ġthe Ġnumber Ġof Ġparameters . </s> In Ġthis Ġpaper , Ġwe Ġpropose Ġa Ġdifferent Ġsolution Ġthat Ġdoes Ġnot Ġchange Ġthe Ġoverall Ġarchitecture , Ġbut Ġonly Ġthe Ġattention Ġtransformation . ĠName ly , Ġwe Ġreplace Ġthe Ġtraditional Ġsoft max Ġby Ġother Ġrecently Ġproposed Ġtransformations Ġthat Ġeither Ġpromote Ġattention Ġsp arsity ĠB IB REF 12 Ġor Ġupper Ġbound Ġthe Ġamount Ġof Ġattention Ġa Ġword Ġcan Ġreceive ĠB IB REF 13 Ġ. ĠThe Ġbounds Ġare Ġdetermined Ġby Ġthe Ġfertility Ġvalues Ġof Ġthe Ġsource Ġwords . ĠWhile Ġthese Ġtransformations Ġhave Ġgiven Ġencouraging Ġresults Ġin Ġvarious ĠN LP Ġproblems , Ġthey Ġhave Ġnever Ġbeen Ġapplied Ġto ĠN MT , Ġto Ġthe Ġbest Ġof Ġour Ġknowledge . ĠFurthermore , Ġwe Ġcombine Ġthese Ġtwo Ġideas Ġand Ġpropose Ġa Ġnovel Ġattention Ġtransformation , Ġconstrained Ġsparse max , Ġwhich Ġproduces Ġboth Ġsparse Ġand Ġbounded Ġattention Ġweights , Ġyielding Ġa Ġcompact Ġand Ġinterpret able Ġset Ġof Ġalign ments . ĠWhile Ġbeing Ġin - between Ġsoft Ġand Ġhard Ġalign ments Ġ( Figure ĠFIG REF 20 Ġ), Ġthe Ġconstrained Ġsparse max Ġtransformation Ġis Ġend - to - end Ġdifferent iable , Ġhence Ġam enable Ġfor Ġtraining Ġwith Ġgradient Ġback prop ag ation . </s> To Ġsum Ġup , Ġour Ġcontributions Ġare Ġas Ġfollows : </s> P rel im in aries </s> Our Ġunderlying Ġmodel Ġarchitecture Ġis Ġa Ġstandard Ġattention al Ġenc oder - dec oder ĠB IB REF 1 Ġ. ĠLet ĠIN LINE FORM 0 Ġand ĠIN LINE FORM 1 Ġdenote Ġthe Ġsource Ġand Ġtarget Ġsentences , Ġrespectively . ĠWe Ġuse Ġa ĠBi - L ST M Ġenc oder Ġto Ġrepresent Ġthe Ġsource Ġwords Ġas Ġa Ġmatrix ĠIN LINE FORM 2 Ġ. ĠThe Ġconditional Ġprobability Ġof Ġthe Ġtarget Ġsentence Ġis Ġgiven Ġas ĠDIS PLAY FORM 0 </s> where ĠIN LINE FORM 0 Ġis Ġcomputed Ġby Ġa Ġsoft max Ġoutput Ġlayer Ġthat Ġreceives Ġa Ġdec oder Ġstate ĠIN LINE FORM 1 Ġas Ġinput . ĠThis Ġstate Ġis Ġupdated Ġby Ġan Ġauto - reg ressive ĠL ST M , ĠIN LINE FORM 2 Ġ, Ġwhere ĠIN LINE FORM 3 Ġis Ġan Ġinput Ġcontext Ġvector . ĠThis Ġvector Ġis Ġcomputed Ġas ĠIN LINE FORM 4 Ġ, Ġwhere ĠIN LINE FORM 5 Ġis Ġa Ġprobability Ġdistribution Ġthat Ġrepresents Ġthe Ġattention Ġover Ġthe Ġsource Ġwords , Ġcommonly Ġobtained Ġas ĠDIS PLAY FORM 0 </s> where ĠIN LINE FORM 0 Ġis Ġa Ġvector Ġof Ġscores . ĠWe Ġfollow ĠB IB REF 14 Ġand Ġdefine ĠIN LINE FORM 1 Ġas Ġa Ġbil in ear Ġtransformation Ġof Ġenc oder Ġand Ġdec oder Ġstates , Ġwhere ĠIN LINE FORM 2 Ġis Ġa Ġmodel Ġparameter . </s> S parse Ġand ĠCon str ained ĠAttention </s> In Ġthis Ġwork , Ġwe Ġconsider Ġalternatives Ġto ĠE q . ĠEQ REF 5 Ġ. ĠSince Ġthe Ġsoft max Ġis Ġstrictly Ġpositive , Ġit Ġforces Ġall Ġwords Ġin Ġthe Ġsource Ġto Ġreceive Ġsome Ġprobability Ġmass Ġin Ġthe Ġresulting Ġattention Ġdistribution , Ġwhich Ġcan Ġbe Ġwasteful . ĠMoreover , Ġit Ġmay Ġhappen Ġthat Ġthe Ġdec oder Ġattends Ġrepeatedly Ġto Ġthe Ġsame Ġsource Ġwords Ġacross Ġtime Ġsteps , Ġcausing Ġrepet itions Ġin Ġthe Ġgenerated Ġtranslation , Ġas ĠB IB REF 7 Ġobserved . </s> With Ġthis Ġin Ġmind , Ġwe Ġreplace ĠE q . ĠEQ REF 5 Ġby ĠIN LINE FORM 0 Ġ, Ġwhere ĠIN LINE FORM 1 Ġis Ġa Ġtransformation Ġthat Ġmay Ġdepend Ġboth Ġon Ġthe Ġscores ĠIN LINE FORM 2 Ġand Ġon Ġupper Ġbounds ĠIN LINE FORM 3 Ġthat Ġlimit Ġthe Ġamount Ġof Ġattention Ġthat Ġeach Ġword Ġcan Ġreceive . ĠWe Ġconsider Ġthree Ġalternatives Ġto Ġsoft max , Ġdescribed Ġnext . </s> F ertility ĠB ounds </s> We Ġexperiment Ġwith Ġthree Ġways Ġof Ġsetting Ġthe Ġfertility Ġof Ġthe Ġsource Ġwords : Ġconstant , Ġguided , Ġand Ġpredicted . ĠWith Ġconstant , Ġwe Ġset Ġthe Ġfert ilities Ġof Ġall Ġsource Ġwords Ġto Ġa Ġfixed Ġinteger Ġvalue ĠIN LINE FORM 0 Ġ. ĠWith Ġguided , Ġwe Ġtrain Ġa Ġword Ġalign er Ġbased Ġon ĠIBM ĠModel Ġ2 Ġ( we Ġused Ġfast _ align Ġin Ġour Ġexperiments , ĠB IB REF 17 Ġ) Ġand , Ġfor Ġeach Ġword Ġin Ġthe Ġvocabulary , Ġwe Ġset Ġthe Ġfert ilities Ġto Ġthe Ġmaximal Ġobserved Ġvalue Ġin Ġthe Ġtraining Ġdata Ġ( or Ġ1 Ġif Ġno Ġalignment Ġwas Ġobserved ). ĠWith Ġthe Ġpredicted Ġstrategy , Ġwe Ġtrain Ġa Ġseparate Ġfertility Ġpredictor Ġmodel Ġusing Ġa Ġbi - L ST M Ġtag ger . ĠAt Ġtraining Ġtime , Ġwe Ġprovide Ġas Ġsupervision Ġthe Ġfertility Ġestimated Ġby Ġfast _ align . ĠSince Ġour Ġmodel Ġworks Ġwith Ġfertility Ġupper Ġbounds Ġand Ġthe Ġword Ġalign er Ġmay Ġmiss Ġsome Ġword Ġpairs , Ġwe Ġfound Ġit Ġbeneficial Ġto Ġadd Ġa Ġconstant Ġto Ġthis Ġnumber Ġ( 1 Ġin Ġour Ġexperiments ). ĠAt Ġtest Ġtime , Ġwe Ġuse Ġthe Ġexpected Ġfert ilities Ġaccording Ġto Ġour Ġmodel . </s> Exper iments </s> We Ġevaluated Ġour Ġattention Ġtransformations Ġon Ġthree Ġlanguage Ġpairs . ĠWe Ġfocused Ġon Ġsmall Ġdatasets , Ġas Ġthey Ġare Ġthe Ġmost Ġaffected Ġby Ġcoverage Ġmistakes . ĠWe Ġuse Ġthe ĠI W SL T Ġ2014 Ġcorpus Ġfor ĠDe - En , Ġthe ĠK FT T Ġcorpus Ġfor ĠJa - En ĠB IB REF 19 Ġ, Ġand Ġthe ĠW MT Ġ2016 Ġdataset Ġfor ĠRo - En . ĠThe Ġtraining Ġsets Ġhave Ġ153 , 326 , Ġ329 , 882 , Ġand Ġ560 , 767 Ġparallel Ġsentences , Ġrespectively . ĠOur Ġreason Ġto Ġprefer Ġsmaller Ġdatasets Ġis Ġthat Ġthis Ġregime Ġis Ġwhat Ġbrings Ġmore Ġadequ acy Ġissues Ġand Ġdemands Ġmore Ġstructural Ġbiases , Ġhence Ġit Ġis Ġa Ġgood Ġtest Ġbed Ġfor Ġour Ġmethods . ĠWe Ġtoken ized Ġthe Ġdata Ġusing Ġthe ĠMoses Ġscripts Ġand Ġpre process ed Ġit Ġwith Ġsub word Ġunits ĠB IB REF 20 Ġwith Ġa Ġjoint Ġvocabulary Ġand Ġ32 k Ġmerge Ġoperations . ĠOur Ġimplementation Ġwas Ġdone Ġon Ġa Ġfork Ġof Ġthe ĠOpen N MT - py Ġtool kit ĠB IB REF 21 Ġwith Ġthe Ġdefault Ġparameters Ġ. ĠWe Ġused Ġa Ġvalidation Ġset Ġto Ġtune Ġhyper param eters Ġintroduced Ġby Ġour Ġmodel . ĠEven Ġthough Ġour Ġattention Ġimplementations Ġare ĠCPU - based Ġusing ĠNum Py Ġ( un like Ġthe Ġrest Ġof Ġthe Ġcomputation Ġwhich Ġis Ġdone Ġon Ġthe ĠGPU ), Ġwe Ġdid Ġnot Ġobserve Ġany Ġnoticeable Ġslowdown Ġusing Ġmultiple Ġdevices . </s> As Ġbas elines , Ġwe Ġuse Ġsoft max Ġattention , Ġas Ġwell Ġas Ġtwo Ġrecently Ġproposed Ġcoverage Ġmodels : </s> We Ġalso Ġexperimented Ġcombining Ġthe Ġstrategies Ġabove Ġwith Ġthe Ġsparse max Ġtransformation . </s> As Ġevaluation Ġmetrics , Ġwe Ġreport Ġtoken ized ĠB LE U , ĠMET E OR Ġ( ĠB IB REF 22 Ġ, Ġas Ġwell Ġas Ġtwo Ġnew Ġmetrics Ġthat Ġwe Ġdescribe Ġnext Ġto Ġaccount Ġfor Ġover Ġand Ġunder - translation . </s> Con clusions </s> We Ġproposed Ġa Ġnew Ġapproach Ġto Ġaddress Ġthe Ġcoverage Ġproblem Ġin ĠN MT , Ġby Ġreplacing Ġthe Ġsoft max Ġattention al Ġtransformation Ġby Ġsparse Ġand Ġconstrained Ġalternatives : Ġsparse max , Ġconstrained Ġsoft max , Ġand Ġthe Ġnewly Ġproposed Ġconstrained Ġsparse max . ĠFor Ġthe Ġlatter , Ġwe Ġderived Ġefficient Ġforward Ġand Ġbackward Ġpropagation Ġalgorithms . ĠBy Ġincorporating Ġa Ġmodel Ġfor Ġfertility Ġprediction , Ġour Ġattention Ġtransformations Ġled Ġto Ġsparse Ġalign ments , Ġavoiding Ġrepeated Ġwords Ġin Ġthe Ġtranslation . </s> Acknowled gments </s> We Ġthank Ġthe ĠUn b abel ĠAI ĠResearch Ġteam Ġfor Ġnumerous Ġdiscussions , Ġand Ġthe Ġthree Ġanonymous Ġreviewers Ġfor Ġtheir Ġinsightful Ġcomments . ĠThis Ġwork Ġwas Ġsupported Ġby Ġthe ĠEuropean ĠResearch ĠCouncil Ġ( ERC ĠSt G ĠDeep SP IN Ġ7 58 969 ) Ġand Ġby Ġthe ĠFund a Ã§ Ã£o Ġpara Ġa ĠCi Ãª nc ia Ġe ĠTec n olog ia Ġthrough Ġcontracts ĠUID / EE A / 5000 8 / 2013 , ĠPT DC / EE I - S II / 70 92 / 2014 Ġ( Learn Big ), Ġand ĠCM UP ER I / T IC / 00 46 / 2014 Ġ( Go Local ). </s> Proof Ġof ĠProposition Ġ </s> We Ġprovide Ġhere Ġa Ġdetailed Ġproof Ġof ĠProposition ĠSEC REF 15 Ġ. </s> Forward ĠProp ag ation </s> The Ġoptimization Ġproblem Ġcan Ġbe Ġwritten Ġas ĠDIS PLAY FORM 0 </s> The ĠLag rang ian Ġfunction Ġis : ĠDIS PLAY FORM 0 </s> To Ġobtain Ġthe Ġsolution , Ġwe Ġinvoke Ġthe ĠKar ush - K uh n - T ucker Ġconditions . ĠFrom Ġthe Ġstation arity Ġcondition , Ġwe Ġhave ĠIN LINE FORM 0 Ġ, Ġwhich Ġdue Ġto Ġthe Ġprimal Ġfeasibility Ġcondition Ġimplies Ġthat Ġthe Ġsolution Ġis Ġof Ġthe Ġform : ĠDIS PLAY FORM 0 </s> From Ġthe Ġcomplement arity Ġslack ness Ġcondition , Ġwe Ġhave Ġthat ĠIN LINE FORM 0 Ġimplies Ġthat ĠIN LINE FORM 1 Ġand Ġtherefore ĠIN LINE FORM 2 Ġ. ĠOn Ġthe Ġother Ġhand , ĠIN LINE FORM 3 Ġimplies ĠIN LINE FORM 4 Ġ, Ġand ĠIN LINE FORM 5 Ġimplies ĠIN LINE FORM 6 Ġ. ĠHence Ġthe Ġsolution Ġcan Ġbe Ġwritten Ġas ĠIN LINE FORM 7 Ġ, Ġwhere ĠIN LINE FORM 8 Ġis Ġdetermined Ġsuch Ġthat Ġthe Ġdistribution Ġnormal izes : ĠDIS PLAY FORM 0 </s> with ĠIN LINE FORM 0 Ġand ĠIN LINE FORM 1 Ġ. ĠNote Ġthat ĠIN LINE FORM 2 Ġdepends Ġitself Ġon Ġthe Ġset ĠIN LINE FORM 3 Ġ, Ġa Ġfunction Ġof Ġthe Ġsolution . ĠIn ĠÂ§ ĠSEC REF 44 Ġ, Ġwe Ġdescribe Ġan Ġalgorithm Ġthat Ġsearches Ġthe Ġvalue Ġof ĠIN LINE FORM 4 Ġefficiently . </s> Grad ient ĠBack prop ag ation </s> We Ġnow Ġturn Ġto Ġthe Ġproblem Ġof Ġback prop ag ating Ġthe Ġgrad ients Ġthrough Ġthe Ġconstrained Ġsparse max Ġtransformation . ĠFor Ġthat , Ġwe Ġneed Ġto Ġcompute Ġits ĠJacob ian Ġmatrix , Ġi . e ., Ġthe Ġderivatives ĠIN LINE FORM 0 Ġand ĠIN LINE FORM 1 Ġfor ĠIN LINE FORM 2 Ġ. ĠLet Ġus Ġfirst Ġexpress ĠIN LINE FORM 3 Ġas ĠDIS PLAY FORM 0 </s> with ĠIN LINE FORM 0 Ġas Ġin ĠE q . ĠEQ REF 37 Ġ. ĠNote Ġthat Ġwe Ġhave ĠIN LINE FORM 1 Ġand ĠIN LINE FORM 2 Ġ. ĠThus , Ġwe Ġhave Ġthe Ġfollowing : ĠDIS PLAY FORM 0 </s> and ĠDIS PLAY FORM 0 </s> Finally , Ġwe Ġobtain : ĠDIS PLAY FORM 0 </s> and ĠDIS PLAY FORM 0 </s> where ĠIN LINE FORM 0 Ġ. </s> [ t ] ĠP ard alos Ġand ĠKov oor 's ĠAl gorithm Ġ[ 1 ] Ġinput : ĠIN LINE FORM 0 ĠInitial ize Ġworking Ġset ĠIN LINE FORM 1 ĠInitial ize Ġset Ġof Ġsplit Ġpoints : ĠIN LINE FORM 2 </s> Initial ize ĠIN LINE FORM 0 Ġ, ĠIN LINE FORM 1 Ġ, ĠIN LINE FORM 2 Ġ, ĠIN LINE FORM 3 Ġ. ĠIN LINE FORM 4 ĠComp ute ĠIN LINE FORM 5 ĠSet ĠIN LINE FORM 6 ĠIf ĠIN LINE FORM 7 Ġ, Ġset ĠIN LINE FORM 8 Ġ; Ġif ĠIN LINE FORM 9 Ġ, Ġset ĠIN LINE FORM 10 ĠReduce Ġset Ġof Ġsplit Ġpoints : ĠIN LINE FORM 11 ĠUpdate Ġtight - sum : ĠIN LINE FORM 12 ĠUpdate Ġslack - sum : ĠIN LINE FORM 13 ĠUpdate Ġworking Ġset : ĠIN LINE FORM 14 ĠDef ine ĠIN LINE FORM 15 ĠSet ĠIN LINE FORM 16 Ġoutput : ĠIN LINE FORM 17 Ġ. </s> Lin ear - Time ĠEvaluation </s> Finally , Ġwe Ġpresent Ġan Ġalgorithm Ġto Ġsolve Ġthe Ġproblem Ġin ĠE q . ĠEQ REF 14 Ġin Ġlinear Ġtime . </s> BI B REF 16 Ġdescribe Ġan Ġalgorithm , Ġreproduced Ġhere Ġas ĠAl gorithm ĠSEC REF 38 Ġ, Ġfor Ġsolving Ġa Ġclass Ġof Ġsing ly - con str ained Ġconve x Ġquad r atic Ġproblems , Ġwhich Ġcan Ġbe Ġwritten Ġin Ġthe Ġform Ġabove Ġ( where Ġeach ĠIN LINE FORM 0 Ġ): ĠDIS PLAY FORM 0 </s> The Ġsolution Ġof Ġthe Ġproblem Ġin ĠE q . ĠEQ REF 45 Ġis Ġof Ġthe Ġform ĠIN LINE FORM 0 Ġ, Ġwhere ĠIN LINE FORM 1 Ġis Ġa Ġconstant . ĠThe Ġalgorithm Ġsearches Ġthe Ġvalue Ġof Ġthis Ġconstant Ġ( which Ġis Ġsimilar Ġto ĠIN LINE FORM 2 Ġin Ġour Ġproblem ), Ġwhich Ġlies Ġin Ġa Ġparticular Ġinterval Ġof Ġsplit - points Ġ( line ĠSEC REF 38 Ġ), Ġiter atively Ġshrinking Ġthis Ġinterval . ĠThe Ġalgorithm Ġrequires Ġcomputing Ġmed ians Ġas Ġa Ġsub r outine , Ġwhich Ġcan Ġbe Ġdone Ġin Ġlinear Ġtime ĠB IB REF 24 Ġ. ĠThe Ġoverall Ġcomplexity Ġin ĠIN LINE FORM 3 ĠB IB REF 16 Ġ. ĠThe Ġsame Ġalgorithm Ġhas Ġbeen Ġused Ġin ĠN LP Ġby ĠB IB REF 23 Ġfor Ġa Ġbudget ed Ġsummar ization Ġproblem . </s> To Ġshow Ġthat Ġthis Ġalgorithm Ġapplies Ġto Ġthe Ġproblem Ġof Ġevaluating ĠIN LINE FORM 0 Ġ, Ġit Ġsuff ices Ġto Ġshow Ġthat Ġour Ġproblem Ġin ĠE q . ĠEQ REF 14 Ġcan Ġbe Ġrewritten Ġin Ġthe Ġform Ġof ĠE q . ĠEQ REF 45 Ġ. ĠThis Ġis Ġindeed Ġthe Ġcase , Ġif Ġwe Ġset : ĠDIS PLAY FORM 0 </s> Examples Ġof ĠTrans lations </s> We Ġshow Ġsome Ġexamples Ġof Ġtranslations Ġobtained Ġfor Ġthe ĠGerman - English Ġlanguage Ġpair Ġwith Ġdifferent Ġsystems . ĠBlue Ġhighlights Ġthe Ġparts Ġof Ġthe Ġreference Ġthat Ġare Ġcorrect Ġand Ġred Ġhighlights Ġthe Ġcorresponding Ġproblematic Ġparts Ġof Ġtranslations , Ġincluding Ġrepet itions , Ġdropped Ġwords Ġor Ġmist rans lations .