1 1 1 7

T a r g e t L a n g u a g e -A w a r e C o n s t r a i n e d I n f e r e n c e f o r C r o s s -l i n g u a l D e p e n d e n c y P a r s i n g

T a o M e n g U n i v e r s i t y o f C a l i f o r n i a , L o s A n g e l e s t m e n g @ c s . u c l a . e d u N a n y u n P e n g U n i v e r s i t y o f S o u t h e r n C a l i f o r n i a n p e n g @ i s i . e d u K a i -W e i C h a n g U n i v e r s i t y o f C a l i f o r n i a , L o s A n g e l e s k w @ k w c h a n g . n e t A b s t r a c t P r i o r w o r k o n c r o s s -l i n g u a l d e p e n d e n c y p a r si n g o f t e n f o c u s e s o n c a p t u r i n g t h e c omm o na l i t i e s b e tw e e n s o u r c e a n d t a r g e t l a n g u a g e s a n d o v e r l o o k s t h e p o t e n t i a l o f l e v e r a g i n g l i ng u i s t i c p r o p e r t i e s o f t h e l a n g u a g e s t o f a c i li t a t e t h e t r a n s f e r . I n t h i s p a p e r , w e s h o w t h a t w e a k s u p e r v i s i o n s o f l i n g u i s t i c k n o w le d g e f o r t h e t a r g e t l a n g u a g e s c a n im p r o v e a c r o s s -l i n g u a l g r a p h -b a s e d d e p e n d e n c y p a r s e r s u b s t a n t i a l l y . S p e c i fi c a l l y , w e e x p l o r e s e v e r a l t y p e s o f c o r p u s l i n g u i s t i c s t a t i s t i c sa n d c omp i l e t h em i n t o c o r p u s -w i s e c o n s t r a i n t s t o g u i d e t h e i n f e r e n c e p r o c e s s d u r i n g t h e t e s t t im e . W e a d a p t tw o t e c h n i q u e s , L a g r a n g i a n r e l a x a t i o n a n d p o s t e r i o r r e g u l a r i z a t i o n , t o c o n d u c t i n f e re n c e w i t h c o r p u s -s t a t i s t i c s c o n s t r a i n t s . E xp e r im e n t s s h o w t h a t t h e L a g r a n g i a n r e l a x a t i o n a n d p o s t e r i o r r e g u l a r i z a t i o n i n f e r e n c e im p r o v e t h e p e r f o rm a n c e s o n 1 5 a n d 1 7 o u t o f 1 9 t a r g e t l a n g u a g e s , r e s p e c t i v e l y . T h e im p r o v em e n t s a r e e s p e c i a l l y s i g n i fi c a n t f o r t a r g e t l a n g u a g e s t h a t h a v e d i f f e r e n t w o r d o r d e r f e a t u r e s f r om t h e s o u r c e l a n g u a g e .

1 I n t r o d u c t i o n N a t u r a l l a n g u a g e p r o c e s s i n g (N L P ) t e c h n i q u e s h a v e a c h i e v e d r em a r k a b l e p e r f o rm a n c e i n a v a r ie t y o f t a s k s w h e n s u f fi c i e n t t r a i n i n g d a t a i s a v a i la b l e . H o w e v e r , o b t a i n i n g h i g h -q u a l i t y a n n o t at i o n s f o r l o w -r e s o u r c e l a n g u a g e t a s k s i s c h a l l e n gi n g , a n d t h i s p o s e s g r e a t c h a l l e n g e s t o p r o c e s s l o w -r e s o u r c e l a n g u a g e s . T o b r i d g e t h e g a p , c r o s sl i n g u a l t r a n s f e r h a s b e e n p r o p o s e d t o t r a n s f e r m o de l s t r a i n e d o n h i g h -r e s o u r c e l a n g u a g e s ( e . g . , E ng l i s h ) t o l o w -r e s o u r c e l a n g u a g e s ( e . g . , T am i l ) t o c om b a t t h e r e s o u r c e s c a r c i t y p r o b l em . R e c e n t s t u d i e s h a v e d em o n s t r a t e d s u c c e s s e s o f t r a n s f e rr i n g m o d e l s a c r o s s l a n g u a g e s w i t h o u t r e t r a i n i n g f o r N L P t a s k s , s u c h a s n am e d e n t i t y r e c o g n i t i o n ( X i e e t a l .,2 0 1 8 ) , d e p e n d e n c y p a r s i n g ( T i e d em a n n,2 0 1 5 ;A g ić e t a l . ,2 0 1 4 ) , a n d q u e s t i o n a n sw e r i n g ( J o t y e t a l . ,2 0 1 7 ) , u s i n g a s h a r e d m u l t i -l i n g u a l w o r d em b e d d i n g s p a c e (Sm i t h e t a l . , 2 0 1 7 ) o r d e l e x i c a l i z a t i o n a p p r o a c h e s ( Z em a n a n d R e s n i k , 2 0 0 8 ; M cD o n a l d e t a l ., 2 0 1 3 ) .

O n e k e y c h a l l e n g e f o r c r o s s -l i n g u a l t r a n s f e r i s t h ed i f f e r e n c e sam o n g l a n g u a g e s ; f o r e x am p l e , l a n g u a g e s m a y h a v e d i f f e r e n t w o r d o r d e r s . W h e n t r a n s f e r r i n g a m o d e l l e a r n e d f r om a s o u r c e l a ng u a g e t o t a r g e t l a n g u a g e s , t h e p e r f o rm a n c e m a y d r o p s i g n i fi c a n t l y d u e t o t h e d i f f e r e n c e s . T o t a c k l e t h i s p r o b l em , v a r i o u s a p p r o a c h e s h a v e b e e n p r op o s e d t o b e t t e r c a p t u r e t h ec omm o n a l i t i e s b e tw e e n t h e s o u r c e a n d t h e t a r g e t l a n g u a g e s ( M cD o n a l d e t a l . , 2 0 1 1 ; G u o e t a l ., 2 0 1 6 ; T ä c k s t r öm e t a l . , 2 0 1 3 ; A g ić , 2 0 1 7 ; A hm a d e t a l ., 2 0 1 9 ) ; h o w e v e r , t h e y o v e r l o o k t h e p o t e n t i a l t o l e v e r a g e l i n g u i s t i c k n o w l e d g e a b o u t t h e t a r g e t l a n g u a g e t o a c c o u n t f o r t h e d i f f e r e n c e sb e tw e e n t h e s o u r c e a n d t h e t a rg e t l a n g u a g e s t o f a c i l i t a t e t h e t r a n s f e r . I n t h i s p a p e r , w e p r o p o s e a c om p l em e n t a r y a pp r o a c h t h a t s t u d i e s h o w t o l e v e r a g e t h e l i n g u i st i c k n o w l e d g e a b o u t t h e t a r g e t l a n g u a g e s t o h e l p t h e t r a n s f e r . S p e c i fi c a l l y , w e u s e c o r p u s l i n g u i s t i c s t a t i s t i c s o f t h e t a r g e t l a n g u a g e s a s w e a k s u p e r v is i o n s i g n a l s t o g u i d e t h e t e s t -t im ei n f e r e n c e p r oc e s s w h e n p a r s i n g w i t h a g r a p h -b a s e d p a r s e r . T h i s a p p r o a c h i s e f f e c t i v e a s t h e m o d e l o n l y n e e d t o b e t r a i n e d o n c eo n t h e s o u r c e l a n g u a g e a n d a p p l i e d t o m a n y t a r g e t l a n g u a g e s u s i n g d i f f e r e n t c o n s t r a i n t s w i t h o u t r e t r a i n i n gt h e m o d e l . W e a r g u e t h a t c e r t a i n c o r p u s l i n g u i s t i c s t a t i s t i c s s u c h a s t h e w o r d o r d e r ( e . g . , h o w o f t e n a n a d j e ct i v e a p p e a r s b e f o r e o r a f t e r a n o u n ) c a n b e e a s i l y o b t a i n e d f r om a v a i l a b l e r e s o u r c e s s u c h a s W o r l d A t l a s o f L a n g u a g e S t r u c t u r e s (W A L S ) (D r y e r a n d H a s p e lm a t h, 2 0 1 3 ) . T o i n c o r p o r a t e t h e c o r p u s l i ng u i s t i c s t a t i s t i c s t o a c r o s s -l i n g u a l p a r s e r , w e c omp i l e t h em i n t o c o r p u s -w i s e c o n s t r a i n t s a n d a d o p t tw o f am i l i e s o f m e t h o d s : 1 ) L a g r a n g i a n r e l a xa t i o n ( L R ) a n d 2 ) p o s t e r i o r r e g u l a r i z a t i o n ( P R ) t o s o l v e t h e c o n s t r a i n e d i n f e r e n c e p r o b l em . T h e a lg o r i t hm s t a k e t h e o r i g i n a l g r a p h -b a s e d p a r s i n g i nf e r e n c e a s a s u b -r o u t i n e , a n d L R i t e r a t i v e l y a d j u s t s t h e p a i r -w i s e p o t e n t i a l s u n t i l t h e c o n s t r a i n t s a r e a n d 1 7 o u t o f 1 9 l a n g u a g e s w h e n u s i n g L a g r a n g i a n r e l a x a t i o n a n d p o s t e r i o r r e g u l a r i z a t i o n t e c h n i q u e s , r e s p e c t i v e l y . T h e im p r o v em e n t s a r e e s p e c i a l l y s u b s t a n t i a l w h e n t h e t a r g e t l a n g u a g e f e a t u r e s a r e d i s t a n t f r om t h e s o u r c e l a n g u a g e . d e n o t e s t h e l e n g t h o f t h ek -t h s e n t e n c e , a g r a p hb a s e d p a r s e r l e a r n s a s c o r e m a t r i xS ( k ) , w h e r e S ( k ) i j d e n o t e s t h e s c o r e t o f o rm a n a r c f r om w o r d w k i t o w o r d w k j . L e t y k b e a n i n d i c a t o r f u n c t i o n t h a t y k ( i , j )2{ 0 , 1 }d e n o t e s t h e a r c f r omw k i t o w k j . T h e m a x im um d i r e c t e d s p a n n i n g t r e e i n f e re n c e c a n b e f o rm u l a t e d a s a n i n t e g e r l i n e a r p r og r amm i n g ( I L P ) p r o b l em : •U n a r yc o n s t r a i n t s c o n s i d e r s t a t i s t i c s r e g a r di n g a p a r t i c u l a r PO S t a g ( PO S ) .

•B i n a r yc o n s t r a i n t s c o n s i d e r s t a t i s t i c s r e g a r di n g a p a i r o f PO S t a g s ( PO S 1 ,PO S 2 ) . S p e c i fi c a l l y , a u n a r y c o n s t r a i n t s p e c i fi e s t h e r a t i o ro f t h e h e a d s o f a p a r t i c u l a rPO Sa p p e a r s o n t h e l e f t o f t h a t PO S . 2 S im i l a r l y , a b i n a r y c o n s t r a i n t s p e c i fi e s t h e r a t i o ro fPO S 1 b e i n g o n t h e l e f t o f PO S 2 w h e n t h e r e i s a n a r c b e tw e e nPO S 1 a n d PO S 2 .

T h e r a t i o srf o r t h e c o n s t r a i n t s a r e c a l l e d c o rp u s s t a t i s t i c s , w h i c h c a n b e e s t im a t e d i n o n e o f t h e f o l l o w i n g w a y s : a ) l e v e r a g i n g e x i s t i n g l i n g u i s t i c s r e s o u r c e s o r c o n s u l t i n g l i n g u i s t s ; b ) l e v e r a g i n g a h i g h e r -r e s o u r c e l a n g u a g e t h a t i s s im i l a r t o t h e t a rg e t l a n g u a g e ( e . g . , F i n n i s h a n d E s t o n i a n ) t o c o l l e c t t h e s t a t i s t i c s . I n t h i s p a p e r , w e e x p l o r e t h e fi r s t o pt i o n a n d l e v e r a g e t h e W A L S f e a t u r e s , w h i c h p r ov i d e a r e f e r e n c e f o r w o r d o r d e r t y p o l o g y , t o e s t im a t e t h e r a t i o s .

C om p i l e C o n s t r a i n t s F r om W A L S F e a t u r e s . F o r a p a r t i c u l a r l a n g u a g e , o n c e w e c o l l e c t t h e c o r p u s -s t a t i s t i c s o f a p a i r o f PO S t a g s , w e c a n f o rm u l a t e a b i n a r y c o n s t r a i n t . T h e r e a r e d i f f e r e n t w a y s t o e s t im a t e t h e c o r p u s -s t a t i s t i c s . F o r e x amp l e , Ö s t l i n g( 2 0 1 5 ) u t i l i z e s a sm a l l am o u n t o f p a ra l l e l d a t a t o e s t im a t e t h e d om i n a n t w o r d o r d e r s . I n t h i s p a p e r , w e s im p l y u t i l i z e a sm a l l s u b s e t o f W A L S f e a t u r e s t h a t s h o w t h e d om i n a n t o r d e r o f s om e PO S p a i r s ( e . g . a d j e c t i v e a n d n o u n ) i n a l a ng u a g e . T h e y c a n b e d i r e c t l y c om p i l e d i n t o b i n a r y c o n s t r a i n t s .

S im i l a r l y , w e c a n e s t im a t e t h e r a t i o f o r u n a r y c o n s t r a i n t s b a s e d o n W A L S f e a t u r e s . F o r a p a r t i cu l a r PO S t a g , w e c h o o s e a l l W A L S f e a t u r e s r e l a t e d t o i t t o f o rm u l a t e a f e a t u r e v e c t o r f . T h e m a p p i n g f r om t h e v e c t o r ft o t h e u n a r y c o n s t r a i n t r a t i o ri s l e a r n a b l e : f o r e a c h l a n g u a g e w i t h a n n o t a t e d d a t a , w e c a n g e t a W A L S f e a t u r e v e c t o rf l a n g a n d a r a t i o r l a n g f r om t h e a n n o t a t i o n . W e o n l y n e e d a sm a l l am o u n t o f d a t a t o e s t im a t er l a n g w e l l . G i v e n a s e t o f l a n g u a g e s w i t h f e a t u r e v e c t o r s a n d e s t im a t e d r at i o s , w e c a n l e a r n t h e m a p p i n g b y a s im p l e l i n e a r r e g r e s s i o n , a n d a p p l y i t t o e s t im a t e t h e r a t i o o f a n y t a r g e t l a n g u a g e t o c om p i l e a u n a r y c o n s t r a i n t .

2 . 3 F o rm u l a t e C o n s t r a i n t s I n t h e f o l l o w i n g , w e m a t h em a t i c a l l y f o rm u l a t e t h e c o r p u s -w i s e c o n s t r a i n t s . N o t e t h a t t h e s e c o n - C o n s t r a i n t : I n a n AD P -NOUN a r c i n H i n d i , AD P i s m o r e l i k e l y t o b e o n t h e r i g h t . t h e c o r p u s -s t a t i s t i c s c o n s t r a i n t w h e nr = 0 o r r=1.

G i v e n a s e t o f c o r p u s -s t a t i s t i c s c o n s t r a i n t s C={ C 1 ,C 2 , . . . ,C n }w i t h c o r r e s p o n d i n g c o r p u s s t a t i s t i c s r={ r 1 , r 2 , . . . , r n } , t h e o b j e c t i v e o f t h e c o n s t r a i n e d i n f e r e n c e i s :

w h e r eYd e n o t e s t h e s e t o f a l l p o s s i b l e d e p e n d e n c y t r e e s . A s a l l t h e c o n s t r a i n t s c a n b e w r i t t e n a s a l i n e a r i n e q u a l i t y w i t h r e s p e c t t o y k ( i , j ) . E q . ( 4 ) i s a n I L P .

I n f e r e n c e w i t h C o r p u s -S t a t i s t i c s C o n s t r a i n t s

T ( 1 ) . I n t h i s w a y , a n e f fi c i e n t i n f e r e n c e a l g o r i t hm s u c h a s m a x im um d i r e c t e d s p a n n i n g t r e e a l g or i t hm ( C h u a n d L i u , 1 9 6 5 ) c a n b e u s e d .

H o w e v e r , w i t h t h e c o r p u s -w i s e c o n s t r a i n t s , d ir e c t l y s o l v i n g E q . ( 4 ) i s i n f e a s i b l e . T h e r e f o r e , w e e x p l o r e tw o a l g o r i t hm s f o r i n f e r e n c e w i t h c o r p u ss t a t i s t i c s c o n s t r a i n t s : L a g r a n g i a n r e l a x a t i o n a n d p o s t e r i o r r e g u l a r i z a t i o n ( G a n c h e v e t a l .,2 0 1 0 ) .

T h e L a g r a n g i a n r e l a x a t i o n a l g o r i t hm i n t r o d u c e s L a g r a n g i a n m u l t i p l i e r s t o r e l a x t h e c o n s t r a i n t o pt im i z a t i o n p r o b l em t o a n u n c o n s t r a i n e d o p t im i z at i o n p r o b l em , a n d e s t im a t e s t h e L a g r a n g i a n m u lt i p l i e r s w i t h g r a d i e n t -b a s e d m e t h o d s . T h e p o s t er i o r r e g u l a r i z a t i o n a l g o r i t hm u s e s t h e c o n s t r a i n t s o f t h e t a r g e t l a n g u a g e 3 . 1 L a g r a n g i a n R e l a x a t i o n L a g r a n g i a n r e l a x a t i o n h a s b e e n a p p l i e d i n v a r i o u s N L P a p p l i c a t i o n s (R u s h a n d C o l l i n s , 2 0 1 2 , 2 0 1 1 ) .

I n E q . ( 4) , e a c h c o n s t r a i n tC i i n v o l v e s tw o i ne q u a l i t y c o n s t r a i n t s : R( C i ,Y ) r i + ✓ 0 , a n dr i + ✓ R( C i ,Y ) 0 .I n s t e a d o f t r e a ti n g t h e s e tw o c o n s t r a i n t s s e p a r a t e l y , w e c o n s i d e r a h e u r i s t i c t o o p t im i z e w i t h e q u a l i t y c o n s t r a i n t s R( C i ,Y ) =r i , i2 [ N]a n d t e rm i n a t e e a r l i e r w h e n c o n s t r a i n t s i n E q . (4 ) a r e s a t i s fi e d . D es p i t e t h i s a p p r o a c h d o e s n o t g u a r a n t e e t h e s o l ut i o n i s o p t im a l i f a l l t h e c o n s t r a i n t s a r e s a t i s fi e d a s t h e o r i g i n a l L a g r a n g i a n r e l a x a t i o n a l g o r i t hm d o e s , i n p r a c t i c e , t h e i n f e r e n c e c o n v e r g e s f a s t e r ( a s t h e n um b e r o f L a g r a n g i a n m u l t i p l i e r s i s h a l f ) a n d t h e p a r s i n g p e r f o rm a n c e m a i n t a i n s .

I n t h e f o l l o w i n g , w e d e r i v e t h e c o n s t r a i n e d i n f e r e n c e a l g o r i t hm f o r c o r p u s -s t a t i s t i c s c o ns t r a i n t s . F i r s t , w e r e w r i t e t h e e q u a l i t y c o n s t r a i n

, l e a r n i n g r a t e d e c a y ⌘ , i n i t i a l l e a r n i n g r a t e ↵ 0 O u t p u t :p a r s e t r e e s Ŷ 1 : ↵ ↵ 0 2 : i 0 ,i 2[ N] 3 : r e p e a t 4 :

Ŷ a r g m a x Y2Y L ( Y , ; C )

r e t u r n Ŷ T o s o l v e t h e d u a l f o rm , w e i n i t i a l i z e i t o b e 0 . A t i t e r a t i o n t , w e fi r s t l y c o n d u c t a n c o n s t r a i n ta u gm e n t e d i n f e r e n c e w i t h a fi x e d ( t ) :

A sF( C) i s a l i n e a r f u n c t i o n w . r . t y k , w e c omb i n e i t w i t hS ( k ) i j y k ( i , j ) . I n t h i s w a y , t h e i n f e r e n c e p r o b l em E q . ( 6 ) c a n b e t r e a t e d a s a s p e c i a l c a s e o f E q . ( 1 ) w i t h a d i f f e r e n t s c o r i n g m a t r i xS ( k ) . I n t h i s w a y , w e c a n t r e a t t h e i n f e r e n c e o n e v e r y s e n t e n c e i n d e p e n d e n t l y a n d l e v e r a g e e x i s t i n g i nf e r e n c e t e c h n i q u e s . A f t e r s o l v i n g t h e c o n s t r a i n t -a u gm e n t e d i n f e re n c e , w e c om p u t e t h e r a t i o o f e v e r y c o n s t r a i n t r i ( t ) = R( C i , Ŷ( t ) ) , a n d u s e g r a d i e n t a s c e n t a lg o r i t hm t o u p d a t e t h e L a g r a n g i a n m u l t i p l i e r s

H e r e↵ ( t ) d e n o t e t h e s t e p s i z e a t i t e r a t i o nt . T h e a l g o r i t hm i s s h o w n i n A l g o r i t hm 1 .

r . t t h e g i v e n c o n s t r a i n t s , a n d l o o k s f o r t h e c l o s e s t f e a s i b l e d i s t r i b u t i o n q ⇤ ( Y) t o t h e m o d e l d i s t r i b u t i o n p ✓ ( Y| W ) .

T h e b e s t p a r s e t r e e i s g i v e n b y a r g m a x Y q ⇤ ( Y) . S p e c i fi c a l l y , w e d e fi n e t h e f e a s i b l e s e t a s :

w h e r e R( C , q) = P k P ( i , j ) : ( k , i , j) 2C + q k ( i , j )

T

KL( q ( Y) k p ✓ ( Y| W ) ) . ( 7) I f t h e f e a s i b l e s e t h a s t h e e x p e c t a t i o n f o rm :

E q . ( 7 ) h a s a s im p l e c l o s e f o rm s o l u t i o n ( G a n c h e v e t a l . , 2 0 1 0 ) : ( 1 0 ) . T o s h o w t h a t t h e i ne q u a l i t yR( C , q( Y) ) r ,i n Qc a n b e f o rm u l a t e d i n t h e f o rm o f E q . ( 8 ) , w e s e t

( q ⇤ k ( i , j ) /p ✓ ( y k ( i , j ) | w k ) e x p ( ⇤ • ( k , i , j ) ) ,

( 1 2 ) h e r e q ⇤ k ( i , j )d e n o t e t h e a r c -l e v e l d i s t r i b u t i o n q ⇤ ( y k ( i , j ) = 1 )s a t i s f y i n g E q . ( 3 ) . W e t h e n d o MA P i n f e r e n c e b a s e d o nq , w h i c h i s a c t u a l l y a m i n im a l s p a n n i n g t r e e p r o b l em s am e a s b e f o r e . A l g o r i t hm2s umm a r i z e s t h e p r o c e s s .

E x p e r im e n t s I n t h i s s e c t i o n

, w e e v a l u a t e t h e p r o p o s e d a lg o r i t hm s b y t r a n s f e r r i n g a n E n g l i s h d e p e n d e n c y p a r s e r t o 1 9 t a r g e t l a n g u a g e s c o v e r i n g 1 3 l a n g u a g e f am i l i e s o f r e a l l o w -r e s o u r c e l a n g u a g e s . W e fi r s t i n t r o d u c e t h e e x p e r im e n t a l s e t u p i n c l u d i n g d a t a s e l e c t i o n a n d c o n s t r a i n t d e t a i l s a n d t h e n d i s c u s s t h e r e s u l t s a s w e l l a s i n -d e p t h a n a l y s i s . o n E n g l i s h a n d t r a n s f e r i t t o 1 9 t a r g e t l a n g u a g e s i n UD T r e e B a n k v 2 . 2 ( N i v r e e t a l ., 2 0 1 8 ) . 4 T h e m o d e l t a k e s w o r d s a n d p r e d i c t e d PO S t a g sfoot_1 a s i np u t , a n d a c h i e v e t r a n s f e r b y l e v e r a g i n g p r e -t r a i n e d m u l t i -l i n g u a l F a s t T e x t (B o j a n o w s k i e t a l . , 2 0 1 7 ) em b e d d i n g s t h a t p r o j e c t t h e w o r d em b e d d i n g s f r om d i f f e r e n t l a n g u a g e s i n t o t h e s am e s p a c e u si n g a n o f fl i n e t r a n s f o rm a t i o n m e t h o d ( Sm i t h e t a l . , 2 0 1 7 ; C o n n e a u e t a l . , 2 0 1 8 ) . T h e S e l fA t t -G r a p h m o d e l u s e s a T r a n s f o rm e r (V a sw a n i e t a l ., 2 0 1 7 ) w i t h r e l a t i v e p o s i t h i -1 , -1 , 1 3 4 . 3 5 2 . 4 5 3 . 4 + 1 9 . 1 5 1 . 3 4 9 . 1 + 1 4 . 8 D r a v i d i a n t a -1 , -1 , 1 3 6 . 1 4 2 . 8 4 3 . 4 + 7 . 3 4 3 . 1 4 3 . 0 + 6 . 9 T u r k i c t r -1 , -1 , 1 3 1 . 2 3 5 . 2 3 7 . 1 + 5 . 9 3 5 . 1 3 6 . 3 c d a 1 , 1 , 1 7 6 . 6 7 6 . 6 7 6 . 5 -0 . 1 7 6 . 6 7 6 . 6 + 0 . 0 I E .G e rm a n i c n l 0 , 1 , 1 6 7 . 5 6 7 . 6 6 7 . 5 + 0 . 0 6 7 . 9 6 7 . 9 + 0 . r a t i o f o r u n a r y c o n s t r a i n t C1 , w e u s e t h e W A L S f e a t u r e s 8 2 A ,8 3 A ,8 5 A ,8 6 A ,8 7 A ,8 8 A ,8 9 At h a t a r e r e l a t e d t o NOUN t o f o rm f e a t u r e v e c t o r s , a n d d o e g r e s s i o n o n l a n g u a g e s i n t h e t e s t e t e x c e p t t h e t a r g e t l a n g u a g e t o p r e d i c t t h e c o n s t r a i n t r a t i o .

T h e p r o c e s s g u a r a n t e e s t h e t a r g e t l a n g u a g e r em a i n u n s e e n d u r i n g t h e r a t i o e s t im a t i o n p r o c e s s . T h e r a t i o s o n t h e r e g r e s s i o n t r a i n i n g l a n g u a g e s a r e e st im a t e d b y s am p l i n g 1 0 0s e n t e n c e s i n t h e t r a i n i n g s e t p e r l a n g u a g e . W e a l s o c o n s i d e r a n o r a c l e s e t t i n g w h e r e w e c o l l e c t a " g r o u n d -t r u t h " r a t i o o f e a c h c o n s t r a i n t f o r t h e t a r g e t l a n g u a g e t o e s t im a t e a n u p p e r b o u n d o f o u r i n f e r e n c e a l g o r i t hm s . I n t h e o r a c l e s e t t i n g , w e e s t im a t e t h e r a t i o o n t h e w h o l e t r a i n i n g c o r p u s o f t h e t a r g e t l a n g u a g e a n d s e t t h e m a r g i n t o ✓=0. 0 1 .

. 2 P a r s i n g P e r f o rm a n c e s W e fi r s t c om p a r e t h e p e r f o rm a n c e s o f t h e c r o s sl i n g u a l d e p e n d e n c y p a r s e r w i t h o r w i t h o u t c o n -

s t r a i n t s . T a b l e1i l l u s t r a t e s t h e r e s u l t s f o r t h e 1 9 t a r g e t l a n g u a g e s w e s e l e c t e d , 6

a l o n g w i t h t h e p e rf o rm a n c e o n t h e s o u r c e l a n g u a g e ( E n g l i s h ) . T h e p e r f o rm a n c e o n E n g l i s h i s n o t a s h i g h a s t h e d ep e n d e n c y p a r s e r s s p e c i a l i z e d f o r E n g l i s h , b e c a u s e t o a c h i e v e t r a n s f e r , w e h a v e t o f r e e z e t h e p r et r a i n e d m u l t i -l i n g u a l w o r d em b e d d i n g s . Y e t t h i s p a r s e r a c h i e v e d t h e b e s t s i n g l e -s o u r c e t r a n s f e r p e rf o rm a n c e s a c c o r d i n g t o A hm a d e t a l .( 2 0 1 9 ) . A s i s s h o w n i n T a b l e1 , t h e im p r o v em e n t s b y o u r c o n s t r a i n e d i n f e r e n c e a l g o r i t hm s a r e d r am a t i c i n a f e w l a n g u a g e s t h a t h a v e v e r y d i s t i n c t w o r d o r d e r f e a t u r e s f r om t h e s o u r c e l a n g u a g e . F o r e xam p l e , t h e p a r s i n g p e r f o rm a n c e o f H i n d i ( h i ) imp r o v e s a b o u t 1 5% i n U A S w i t h W A L

S f e a t u r e s v i a b o t h L a g r a n g i a n r e l a x a t i o n a n d p o s t e r i o r r e gu l a r i z a t i o n i n f e r e n c e . T h e im p r o v em e n t s a r e l e s s 1 1 2 4 o b v i o u s f o r l a n g u a g e s t h a t a r e i n t h e s am e f ami l y a s

E n g l i s h s u c h a s D a n i s h ( d a ) a n d D u t c h ( n l ) . T h i s i s e x p e c t e d a s t h e c o r p u s l i n g u i s t i c s t a t i s t i c s o f t h e s e l a n g u a g e s a r e s im i l a r t o E n g l i s h t h u s t h e c o n s t r a i n t s a r e m o s t l y s a t i s fi e d w i t h t h e b

a s e l i n e p a r s e r . C om p a r i n g L a g r a n g i a n r e l a x a t i o n a n d p o st e r i o r r e g u l a r i z a t i o n , w e fi n d p o s t e r i o r r e g u l a r i z at i o n b e i n g m o r e r o b u s t a n d l e s s s e n s i t i v e t o t h e e rr o r s i n t h e c o r p u s -s t a t i s t i c s e s t im a t i o n , w h i l e L ag r a n g i a n r e l a x a t i o n g i v e s a h i g h e r im p r o v em e n t o n a v e r a g e . O v e r a l l , t h e tw o p r o p o s e d c o n s t r a i n e d i n f e r e n c e a l g o r i t hm s im p r o v e d t h e t r a n s f e r p e r f o rm a n c e b y 3 . 5% a n d 3 . 1% p e r U A S o n a v e r a g e o n 1 9 t a r g e t l a n g u a g e s . F o r l a n g u a g e s l i k e F i n n i s h ( fi ) a n d E s t o n i a n ( e t ) , t h e W A L S s e t t i n g w o r k s e v e n b e t t e r t h a n t h e o r ac l e . W e s u s p e c t t h e r e a s o n b e i n g t h e l a r g e m a r g i n w e s e t i n t h e W A L S s e t t i n g . W h e n t h e e s t im a t e d c o r p u s -s t a t i s t i c s i s d i f f e r e n t f r om t h e r e a l r a t i o i n t h e t e s t s e t , t h e l a r g e m a r g i n r e l a x e s t h e c o ns t r a i n t s , t h u s c o u l d r e s u l t i n b e t t e r p e r f o rm a n c e s .

D i s c u s s i o n . D e s p i t e t h e m a j o r e x p e r im e n t s a n d a n a l y s i s a r e c o n d u c t e d u s i n g E n g l i s h a s t h e o n l y s o u r c e l a n g u a g e , o u r a p p r o a c h i s g e n e r a l a n d d o e s n o t h a v e r e s t r i c t i o n o n t h e c h o i c e o f t h e s o u r c e l a ng u a g e ( s ) . T o v e r i f y t h i s c l a im

, w e r u n e x p e r im e n t s w i t h H e b r e w a s t h e s o u r c e l a n g u a g e . U n d e r t h e o ra c l e s e t t i n g , L a g r a n g i a n r e l a x a t i o n a n d p o s t e r i o r r e g u l a r i z a t i o n im p r o v e t h e b a s e l i n e b y 4 . 4% a n d 4 . 1% , r e s p e c t i v e l y . W e o b s e r v e d t h a t i f w e c om p i l e W A L S f e a t u r e s i n t o h a r d c o n s t r a i n t s ( i . e . , s e t r= 0 o r 1 ) , t h e c o ns t r a i n t i n f e r e n c e f r am e w o r k o n l y im p r o v e s p e r f o rm a n c e o n h a l f o f t h e l a n g u a g e s . F o r e x am p l e , i n E s t o n i a n ( e t ) , t h e p e r f o rm a n c ed r o p sa b o u t 3% .

T h i s i s b e c a u s e W A L S o n l y p r o v i d e s t h e d om in a n t o r d e r . T h e r e f o r e , t r e a t i n g W A L S a s h a r d c o ns t r a i n t s i n t r o d u c e s e r r o r t o t h e i n f e r e n c e . F i n a l l y , w e a s s um e i f w e c a n a c c e s s t o n a t i v e s p e a k e r s , t h e c o r p u s -s t a t i s t i c s c a n b e e s t im a t e d b y

a f e w p a r t i a l a n n o t a t i o n s o f p a r s e t r e e s . I n o u r s imu l a t i o n , u s i n g l e s s t h a n 3 0 0 a r c s , w e c a n a c h i e v e t h e s am e p e r f o rm a n c e a s u s i n g t h e o r a c l e . C o n s t . s t a t i s t i c s im p r o v em e n t + P r o j . N /A + 0 . 1 C 1 0 . 3 0 / 0 . 3 6 / 0 . 9 4 + 6 . 9 C 2 0 . 0 0 / 0 . 0 6 / 1 . 0 0 + 1 1 . 3 C 3 0 . 1 4 / 0 . 2 7 / 0 . 1 2 + 0 . 5 A l l N /A + 1 8 . 1 u s e i t a s f e a t u r e s ( Amm a r e t a l ., 2 0 1 6 ; N a s e em e t a l . , 2 0 1 2 ; R a s o o l i a n d C o l l i n s , 2 0 1 7 ; Z h a n g a n d B a r z i l a y , 2 0 1 5 ;D r y e r, 2 0 0 7 ) . T ä c k s t r öm e t a l .

. 3 C o n t r i b u t i o n s o f I n d i v i d u a l C o n s t r a i n t s W e a n a l y z e t h e c o n t r i b u t i o n o f e a c h c o n s t r a i n t d em o n s t r a t e d i n T a b l e2 . H e r e w e u s e t h e o ra c l e s e t t i n g t o r e d u c e t h e n o i s e i n t r o d u c e d b y c o r p u s -s t a t i s t i c s e s t im a t i o

( 2 0 1 3 ) f u r t h e r p r o p o s e t o d e c om p o s e t h e s e f e at u r e s f r om m o d e l s f o r a d a p t i n g t a r g e t l a n g u a g e s .

W a n g a n d E i s n e r ( 2 0 1 8 a ) u s e t h e s t a t i s t i c s o f s u r -f a c e p a r t -o f -s p e e c h ( PO S ) t a g s o f t a r g e t l a n g u a g e s t o l e a r n t h e w o r d o r d e r . W a n g a n d E i s n e r ( 2 0 1 8 b ) u s e PO S t a g s o f t a r g e t l a n g u a g e s t o g e t h e r w i t h a s im i l a r l a n g u a g e , a n d d e s i g n a s t o c h a s t i c p e rm ut a t i o n p r o c e s s t o s y n t h e t i c