ࡱ> \]`!^K)V"|r*BHD xڥMhQggѬD$vcMڄ*C/QAOB[XIH ɪAAуz3ГC (xH9 W|% o{oH@?!-$˒3눔v9{ D }Mb=#c1p>@|=a(.KF]K#d;r8,qm5iZ1b?w>DBt..lD7~i"C;,'/msM hY]n6?N\$gxq><\zN\S~J6w@Wq,[TvFojjե+CqъĩBͰyfrӁSn^? u=|{_1K 7ļ: ;WYGV]; 0nnpeVn,MnQ_*n Qqǿ:E\c,ie:ZR&E!ѿo57?s_Klggʟ¢)? QH{QMu'l,Ui-+ q#z|}@{{Ӊ&<*s~z'5'-2XYa]3XQ2ڠq[B<`4V*lS] i9ޜd(npXڼV&ռ,wPNG  IHDR_L<Л`PLTE1Vv(«jzkU)SG=byA : bKGDH cmPPJCmp0712HsIDATXGXr8 %ը.sYR|C`g;!pP( >{Qb*EXOq˦ 󋦧l|di*"rys)4X%V++\`}\ߜ~#.%6w)MW_Ϡ#]=o1BEJ?Gg@73,~^?oϞ] .* w4-jJU!?^?j$N1*Õa;]){|d_OQ̟''~CU*I 7}Pق'>09*xďIx~!oXw!~b.*?/C68 =)[><*ՒUh"jdֵb6X5c;.cʀjn. '3*@ +˶_7QEčmZ'L&fvZ>0/S_嬓W&l.lp,46&?6q'wxR)=%lpFm: ڻKt .MZ4,3ZԲ5-0@n~ki3.˨Ae8Hu&ZGm:ƻY,<ڼ@=׷Yw>:I& c#|rkˮv 1{/P0$l9S64 )*^( (Ne:F.@clKFrA8[;H Z umж/ZNG{9¦5Vv Oc&.jA8yj:p|ۍwULWS0-d|+Hk~^enUq#U p7_ҙHN{E)=Pé)>wJ춑ըC$/HMW( j\7i7|u$qrtvΓP;FnL^fէs~&&P~0)9I|41U' P=xcdd`` @c112BYL%bpu(,xڥk@L~kvkeT^t76 ]BŃ'wŃozTz_Lq9CԟU!`;y\^QJú]<0Uby.-dlm?\!{" ztr1^"x<x\A4̧nL ÏY ~&RՃPNG  IHDRXPLTEKvvvAAA=hhh܌444ddd999ԝ]󸸸\|bbb즦Ş2mmm```---ޖfffDDDUq^â.)))xxx2r~⎎{{{PPP>>>b<<<000SSSNNNJJJZZZXXXKUUUGGGil666]]]O6LLL0FFF7Vi`kkkqqqooo}}}ttt~~~sssjjj}uuuґppprrrnnn|||ӿ___/nSm'''ڑY9F4ʁ8WWWP{ILה[ەvAِª퀿lO򝪲U?GL7g>}}Ҩژdo8aq{yhwGݠSZbg5p~yob}GJLғȕ333,rrԉ@ўv(D({Ly^FfQ;P.*У>GeU^vL 5PF)CmaSEm6m*#S렼)]T(Mo0ҳ,DgUDJӂ`a&V(P0фlPDx5* g"'NG[JE&dT4t^1!IV{HY4BXE/obN|'}$Púm*Oiq(5BW2#-&^sCqbZLFeEsb'yRn4*B c5AuSUS.Hjgv]0ÑTg?#TH"\/V  9PPsJX:5ʷm98iykb-?!HjF[S패dO.dA0j=5YAx<eX%qm=/@ξ|XY*x!3)RnWו y H\\6]G=g/~yVtcZ~ɓ9;Vj{@jpAFA3?Bv bSˉcxl z7xïԳT7iɔZ=''kX3+>o!o.RR l=<IENDB``!~U6U~gâ$8X xڝK/CALoKo[-ADGB#D,T\4GFJ,,GŽ b֊XB,E9Ra$9! g3HE rktʽTkcV 3_2 r,Fa:gmd P&X}p pEF!6oVJzF ]kI91fꇁ϶dMb*QFނ< y6)mA@^]ԟ̊1cVR!WE?\_AX!_6,sUļVqCo>f;e3$y+V.a.m J>e\wC_ "8i1F^_1(3?q$8/݆?_!>hqL1( #8: 1ht J{e uE`~w'tן`!;ɿ]V: 8wxcdd``eb``baV d,FYzP1n:\ B@?b 30xq@0&dT200 KXB2sSRsv,X~ >I[T TpiլA|8?׀>!g`kFV΁ށ E'z('? _X U@|C(_q/c |RPTEǢ3# q#<ç2Of+ 13yP |TL乏DS"JV7/ȣpƩ`wT(ʛ ?`J>HQ80+L(gJC'D?Ã*Í7bnP;27)?לO O #t\Gkp\N^ @c112BYL%bpuUIbF\ g#7ׁɈUC,d\pWʼn'8 1޳l #t P){to [ s1x:090M2"8 Cv0o(+KRs@2u(2t5'τ k_`!YvP xXi x xt'xcdd``fed``baV d,FYzP1n:L؅,56~) @ 730熪aM,,He`(/ @201d++&1X +|.OOKdF\ L~l 0:<ߠ}L +ssNs:D} -L #l1eD7W+ Ps:0M䂆8d 3v0o(.+KRsA2u(2t5'τ zcn|U׷2?`v,PNG  IHDR@--pisRGB pHYsqPLTE&&`IDAT8ݔK D'TQXJB$_gP_O%JhD_F@Bx#h@҇@+OH05xi3H HAj0Pkg"n{@U(M@H7q!9_V@ҧ^K6"wJ\Z臏 RƠ'kR򤁼C=hQr~jt鴿_H"IENDB`ntq;@aZ&hNPNG  IHDR<74sRGB pHYsCrPLTE0;:_IDAT8 _*.:BFT/`08Im-%!A<4~ u'%9xa̡+hfv-@Ƕ?8wmԏIENDB``!;loof5]@   xcdd``> @c112BYL%bpul9hy|Cw3iriNTܨN*D` VJOD/G^L/LGCDEFGHIL   X[\]^_ ab  hijkl mnop1 tBvwxyz{|}~ 2$^K)V"|b$XڼV&ռ,wx2$9_= *f,2 2$b1;KNnQf b$ÏY ~&RՃT e 2$~U6U~g2$;ɿ]V$2$O18 { 2$NG^Rf!]$$$$2$); KpDz*~-/e2$ܱ&SaFu 2$vP xXia "$b$U׷2?`v,j#b$q;@aZ&hN|$2$loof5]Cj&$2$K;15HXI'2$:Źg~.EhWAJ) 0AA ffffff@ۉ8ʚ;ʚ;g4BdBd z[ 0pppp@ <4ddddL 0~ 0___PPT10 ppH___PPT9*"n_4ln,|PNG  IHDR +tsRGB PLTEff3fQ} cmPPJCmp0712cOtRNS@fIDATc`PA-Q-0 yx`YsIENDB`[nQy  a*lD!@PNG  IHDR exsRGBNPLTEkc{絔έֽεƭƥƽ{s cmPPJCmp0712x~tRNS AyIDATMI0{d{1@Gs @c3|bXֻ$镰3дY ;6TJ~UCo@{} P{4$]$gc>/13"+^ZCLKs}XmIENDB`?Z-FDevi Xiong et al. ICT, CAS, BeijingO  =1QMaximum Entropy Based Phrase Reordering Model for Statistical Machine TranslationBR&,",&,+",Deyi Xiong, Qun Liu and Shouxun Lin Multilingual Interaction Technology & Evaluation Lab Institute of Computing Technology Chinese Academy of Sciences {dyxiong, liuqun, sxlin} at ict dot ac dot cn Homepage: http://mtgroup.ict.ac.cn/~devi/ """" "s".g  *g   y Outline"^Previous work Maximum entropy based phrase reordering System overview Experiments Conclusions  Previous WorkContent-independent reordering models E.g. distance-based or flat reordering models Learn nothing for reordering from real-world bitexts Content-dependent reordering models Lexicalized reordering models [Tillmann, 04; Och et. al. 04; & ] Totally dependent on bilingual phrases With a large number of parameters to estimate Without generalization capabilities&.5%@y&.5%  @&R>E+ %Can We Build Such a Reordering Model?,& $$$Content-dependent but not restricted by phrases Without introduction of too large number of parameters but still powerful With generalization capabilities -Build It Conditioned on Features, not Phrases:.""" "Features can be: Some special words or their classes in phrases Syntactic properties of phrases Surface attributes like distance of swapping Advantages of feature-based reordering: Flexibility Less parameters Generalization capabilities \|(:| : q+Feature-based Reordering"Discriminative Reordering Model proposed by Zens & Ney in NAACL 2006 Workshop on SMT We have become aware of this work when we prepare the talk Very close to our work But still different: Implemented under the IBM constraints Using different feature selection mechanism NUgSUgS ,,V"Outline"^Previous work Maximum entropy based phrase reordering System overview Experiments Conclusions *_()Reordering as Classification$Regard reordering as a problem of classification Two classes problem under ITG constraints {straight, inverted} Multi-class problem if positions are considered under the IBM constraints Our work focused on the reordering under the ITG constraintsl1Z+ZZJZ=Z1+J =W $MaxEnt-based Reordering Model (MERM)"%  MA reordering framework for BTG MERM under this framework Feature function:--TTraining for MERM"Training procedures: 3 steps Learning reordering examples Generating features ( ) from reordering examples Parameter ( ) estimation using off-the-shelf MaxEnt toolkits :$ . Reordering Example" FeatureseLexical feature: source or target boundary words Collocation feature: combinations of boundary words 2f!! AWhy Do We Use Boundary Words as Features: Information Gain Ratio BB" ]$Outline"fPrevious work Maximum entropy based phrase reordering System overview (Bruin) Experiments Conclusions Bg6" Translation Model%Built upon BTG The whole model is built in the log-linear form The score to apply lexical rules is calculated using features similar to many state-of-the-art systems The score to apply merging rules is divided into two parts The reordering model score The increment of language model score NBABA 1GDifferent Reordering Models Are Embedded in the Whole Translation ModelHH"oThe reordering framework MaxEnt-based reordering model Distance-based reordering model Flat reordering modelP2CKY-style Decoder"Core algorithm Borrowed from CKY parsing algorithm Edge pruning Histogram pruning Thresholding pruning Language model incorporation Record the leftmost & rightmost n words for each edge $ '6$ ' 6"R \g&Outline"^Previous work Maximum entropy based phrase reordering System overview Experiments Conclusions *_F  h%Experiment Design"To test MERM against various reordering models, we carried out experiments on: Bruin with MERM Bruin with monotone search Bruin with distance-based reordering model Bruin with flat reordering model Pharaoh, a distance-based state-of-the-art system (Koehn 2004)4OOj'Systems Settings"3Small Scale Experiments"LNIST MT 05 Training data: FBIS (7.06M + 9.15M) Language model: 3-gram trained on 81M English words (most from UN corpus) using SRILM toolkit Development set: 580 sentences length of at most 50 Chinese characters from NIST MT 02 IWSLT 04 Small data track 20k sentences for training of TM and LM 506 sentences as the development set N  _  _ 8 MERM Training"m(Results on Small Scale Data"AScaling to Large Bitexts"Just used lexical features for MaxEnt reordering model Training data 2.4M sentence pairs (68.1M Chinese words and 73.8M English words) Two 3-gram language models One was trained on the English side The other was trained on the Xinhua portion of the Gigaword corpus with 181.1M words Used simple rules to translate number, time expressions and Chinese person names New BLEU score: 0.291 EZBZZyZgZZZEBy  g>MResults Comparison" n)Outline"^Previous work Maximum entropy based phrase reordering System overview Experiments Conclusions "_R @ Comparisons "B Conclusions "MaxEnt-based reordering model is Feature-based Content-dependent Capable of generalization Trained discriminatively Easy to be integrated into systems under the IBM constraints :!!p* Future Work "More features Syntactic features Global features of the whole sentences & Other language pairs English-Arabic Chinese-MongolianN<!<! C Thank you!   7Training "Run GIZA++ in both directions Use grow-diag-final refinement rules Maximum phrase length: 7 words on the Chinese side Length ratio: max(|s|, |t|)/min(|s|, |t|) <= 3>'Y  |,&Language Model Incorporation (further)''"The edge spans only part of the source sentence The history of LM is not available the language model score has to be approximated by computing the score for the generated target words alone Combination of two neighbor edges only need to compute the increment of the LM score: v0"40"4 OTree" - Related Definitions" U/The Algorithm of Extracting Reordering ExamplesZFor each sentence pair do Extract bilingual phrases Update the links for the four corners of each extracted phrases For each corner do If it has a STRAIGHT link with phrase a and b Extract the pattern: <a; b> STRAIGHT If it has a INVERT link with phrase a and b Extract the pattern: <a; b> INVERT[.',%[.  , /!#$%'(, / 0 4 56>?GHIJRSX^ab c!i"o#r$s%t&u'v(~)3  ` !3̙` Q.<ffff3` 3333fff` 3K=̙fff` 3fffff` ff3ff3` aNR>ff` 3fY33` 3f3f>?" dd@&f?ldd(@fm<)6=m+7%l', n?" dd@   @@``PT    = 7 ,`(p>>K0 TL@E(    <# #" `T,M # LUSQdkYkHrh7h_     0 # " # 8USQdkYkHre,g7h_ ,{N~ ,{ N~ ,{V~ ,{N~  X  C "A logo"7 A s *8'# #" `M  # ^*C  B 0%# "   # ~ *COLING-ACL 2006C  C 01# "6 # `*C ` E C *Alab_logo"I&ZP  s *޽h ?"` 3f3f___PPT10i. "+D=' = @B +___PPT9JpJJ Profile9 K0 80P(    <& #" `@ & LUSQdkYkHrh7h_    04& "C,3  & NUSQdkYkHroRh7h_ X   C "A logo"7`  C *Alab_logo"I&ZP  s *޽h ?"` 3f3f___PPT10i. "+D=' = @B + 0 ~v$(  $ $ 0T& P   & P*   $ 08&    & \* d $ c $ ?  & $ 0&  0 & 8USQdkYkHre,g7h_ ,{N~ ,{ N~ ,{V~ ,{N~   $ 6@& _P  & Z*  $ 6& _  & \* H $ 0޽h ? 3380___PPT10.p֎K0  0(  x  c $  x  c $C',  H  0޽h ? 33___PPT10i.PG0+D=' = @B + K0 (0(  (x ( c ${T,M  & x ( c $|  H ( 0޽h ? 3f3f___PPT10i.@MS+D=' = @B + K0 00(  0x 0 c $,0T,M  0 x 0 c $0 0 H 0 0޽h ? 3f3f___PPT10i.+D=' = @B +  K0 |$(  |r | S -0qM  0 r | S .0 0 H | 0޽h ? 3f3f___PPT10i.N3+D=' = @B + K0 40(  4x 4 c $,30S'Y/  0 x 4 c $40= 0 H 4 0޽h ? 3f3f___PPT10i.n(+D=' = @B + $K0 $(  r  S 4C0T,M  0 r  S D0 0 H  0޽h ? 3f3f___PPT10i.ɤPn+D=' = @B + K0 |<(  |~ | s *P0T,M  0 ~ | s *P0 0 H | 0޽h ? 3f3f___PPT10i.@MS+D=' = @B + K0 80(  8x 8 c $`0  0 x 8 c $a0 0 H 8 0޽h ? 3f3f___PPT10i."+D=' = @B +M K0 LDt(  tr t S Xt0T,M  0 x t c $,u0Y 0  t0 NA ? ? ]  0 t0 NA ? ?p    0f t s *A ? ? oY H t 0޽h ? 3f3f___PPT10i. Q+D=' = @B +  K0 pn(  pr p S ؄0T,M  0 x p c $0w 0  p0 NA ? ?z    0 p0 NA ? ?j  0H p 0޽h ? 3f3f___PPT10i.h+D=' = @B +   K0   @f (  r  S 80T,M  0   <̕0/7 :b1E  <(0-` :b2EX   0kQ   6Ȝ0 w t&<b1; b2> STRAIGHT2 2 A A8 7c   % 7    6T0c )  :b4E   607)   :b3EZ  s *   0d0p   p"<b3; b4> INVERT2 2 AAj  s *0ۉ) w  E.g. <o ?e^|the Macao government; gsQ |related departments of> INVERT0I@AA,"f  s *0ۉ}w E.g. <N)Y g ht k[|Are there any baseball games today; T |?> STRAIGHT0G<A A, %LB  c $DZ<H  0޽h ? 3f3f___PPT10i.s+D=' = @B + K0 0 D/(  Dx D c $0T,M  0 x D c $0 0   D0 H ? ?& }   08 D 0D03*)  X<N NN|with them; OcT||keep contact> INVERT0-$AA, XB  D 0DԔC@ @   D0 TA ? ? f)   0f D s *A ? ? L,  D 00p ]  EFeature selection 2AH D 0޽h ? 3f3f___PPT10i. T+D=' = @B +y% K0 x$p$P<qL$(  Lx L c $0Z  0    / qL #">2 r/  0 L <0 ?e   Q .00899752  )=7,  L <0 ? e  hE1)=7,  L <0 ?e  Q .00758598  )=7, L <J ? e hC1)=7, L < J ?e   Q .00994372  )=7, L <$J ? e  hE2)=7, L <,!J ?e   O.011371)=7, L <*J ? e  hC2)=7, L <t3J ?e   P.0153117  )=7, L < =J ?  e  jC1E1)=7, L <FJ ?e   P.0192932  )=7, "L <7J ? e  jC2E2)=7, #L <XJ ?e  O.023363)=7, 'L <bJ ? e  jC1C2)=7, (L <cJ ?e P.0239286  )=7, ,L <tJ ? e jE1E2)=7, -L 6}J ?e! T.0263687  )=7, 1L 6J ? !e TC1C2E1E2  )=7, 2L 6@J ?e(! R.02655)=7, 6L 6 J ? (e! SPhrases)=7, 7L <tJ ?e/( MIGR)=7, ;L <J ? /e( Qfeature)=7,fB L 01 ? !!`B ?L 01 ? `B @L 01 ? `B AL 01 ?  `B BL 01 ?   `B CL 01 ?  `B DL 01 ?  `B EL 01 ?  fB FL 6o ? fB GL 6o ? / `B HL 01 ?e/efB LL 6o ?/`B ML 01 ?  t8   cLq  ` VL 0 TB WL c $D ``2 XL 6Jd3 BE 2 YL 6pJd BE  ZL 0JD7+  6C1 2A [L 0$JP 77  6E1 2A `L 0JC*  6C2 2A aL 0\JP 7  6E2 2AF   dL p{  ` eL 0 TB fL c $D ``2 gL 6Jd3 BE 2 hL 6XJd BE LB kL c $D d  LB lL c $D   mL 0dJ z  ITarget boundary words 2ALB nL c $DdgLB oL c $Dg pL 0\Jz  ISource boundary words 2AH L 0޽h ? 3f3f___PPT10i.0+D=' = @B + K0 <(  ~  s *|JT,M  J ~  s *|J J H  0޽h ? 3f3f___PPT10i.@MS+D=' = @B +C K0 B: l(  lx l c $JT,M  J x l c $J J   l0 NA I? ?Zp I H H l 0޽h ? 3f3f___PPT10i.+D=' = @B +  K0 J(  r  S KD&/  K x  c $K/ K   0 TA J? ? b J F f   s *A K? ?3   K  0 6A L?  s  L F x  <A O? O *  OH  0޽h ? 3f3f___PPT10i.uט+D=' = @B + K0  *(  r  S KT,M  K x  c $pK K H  0޽h ? 3f3f___PPT10i.vh+D=' = @B + "K0 <(  ~  s *,*KT,M  K ~  s *+K K H  0޽h ? 3f3f___PPT10i.@MS+D=' = @B + %K0 $(  r  S L9KT,M  K r  S  :K K H  0޽h ? 3f3f___PPT10i.L+D=' = @B +" &K0 !0(  r  S HKT,M  K  @Y  0 #"!@Y  K  <DRK?d Y  cMonotone/flat/distance/MERM)=7,  <[K? d   On = 40;)=7,  <dK?d   Ob = 100)=7,  <mK?*d   LSame)=7,  <oK?d *  MBruin)=7,  <yK?aYd  l$Limited distortions to 4 (default 0)%%)=7,   <@K? ad  Pn = 100;  )=7,   <K?a d  \b = 100 (default 20))=7,   <K?*ad  LSame)=7,   <K?a*d  OPharaoh)=7,   < K?@Ya R Reordering  )=7,  <зK? @a U Stack pruning)=7,  <K?@ a \Phrase table pruning)=7,  < K?*@a T Phrase table  )=7,  <DK?@*a OSystems)=7,`B  0o ?@Y@ZB  s *1 ?aYaZB  s *1 ?d Yd `B  0o ? Y `B  0o ?@ ZB  s *1 ?*@* ZB  s *1 ?@ ZB  s *1 ? @ ZB  s *1 ?@ `B  0o ?Y@Y  #0 TA '? ?p3 6  ' K &0 TA (? ?F 3 2  ( KH  0޽h ? 3f3f___PPT10i.!+D=' = @B + K0 $(  r  S dKT,M  K r  S K K H  0޽h ? 3f3f___PPT10i.wp+D=' = @B +G K0 F>@%}(  r  S KT,M  K $  } #"6* WWVWWWVWW \ <DK?)] Q89.6K)=7, [ <Q ?"`]) ^Collocation Features)=7, Y <D Q?) ] Q16.9K)=7, X <$Q ?"` )] ZLexical Features)=7, V <!Q?)   P9.3k)=7, U <`+Q ?"` )  fInverted Reordering Examples)=7, S <t4Q?)Y   Q79.5k)=7, R <T6Q ?"`Y )  fStraight Reordering Examples)=7, Q ZFQ_ж_ж?Y  RIWSLT 04  )=7, P <OQ?) Y  P1.7M)=7, O <QQ ?"` )Y  ^Collocation Features)=7, M <aQ?)  P112K)=7, L < kQ ?"`)  ZLexical Features)=7, J <sQ?)U P367K)=7, I <eQ ?"`U) fInverted Reordering Examples)=7, G <Q?)U P2.7M)=7, F <PQ ?"`)U fStraight Reordering Examples)=7, E ZXQ_ж_ж?Y  T NIST MT 05  )=7, D <Q?) KNum)=7, B <NL v O Bruin (MaxEnt): he will attend the meeting held in the Indonesian capital Jakarta on world leaders Pharaoh: he will participate in the leader of the world on 6 Indonesian capital of Jakarta at the meeting Bruin (Distortion): he will join the world 's leaders of the Indonesian capital of Jakarta meeting held on 6 Bruin (monotone): he will participate in the world leaders on 6 the Indonesian capital of Jakarta at the meeting of the Ref: he will attend the meeting of world leaders to be held on the 6th in the Indonesian capital of JakartaLAEEEA EA8EAEA>EA EEA:EAEA EAEA<EA E AEA EALE$%^ ( 6A ?m7^ ( 6A ?7^ ( 6A ? 7 ^ ( 6A ? 7 H ( 0޽h ? 3f3f___PPT10i.Ǻ+D=' = @B + #K0 `<(  ~  s *ST,M  S ~  s *S S H  0޽h ? 3f3f___PPT10i.@MS+D=' = @B +* K0 )!"F(  r  S ST,M  S  q  F #"&I  S 5 <S?9q  OSmall)=7, 3 <S?@ 9  OLarge)=7, / <S?Z@  K/)=7, - <T?Z  ZParameter number)=7,  <\ T?9 q  XDiscriminative)=7,  <T?@ 9  MMLE)=7,  <T?Z @  K/)=7,  <0&T? Z  ^Parameter estimation)=7,  <`/T?9q MYes)=7,  <h8T?@ 9 LNo)=7,  <pAT?Z@  K/)=7,  <dJT?Z U Generalized  )=7,  <ST?9q MYes)=7,   <\T?@ 9 MYes)=7,   <0WT?Z@  LNo)=7,   <nT?Z [Content-dependent)=7,   <XxT?9q jMaxEnt)=7,  <8zT?@ 9 U lexicalized  )=7,  <T?Z@  W distance/flat)=7,  <ؓT?Z T )=7,`B  0o ?qZB  s *1 ?qZB  s *1 ?qZB  s *1 ?q`B  0o ? q `B  0o ? ZB  s *1 ?ZZ ZB   s *1 ?@ @ ZB " s *1 ?99 `B # 0o ?qq ZB . s *1 ? q H  0޽h ? 3f3f___PPT10i.+D=' = @B + K0 @$(  r  S (TT,M  T r  S T T H  0޽h ? 3f3f___PPT10i. 1H+D=' = @B + (K0 $(  r  S ̵TT,M  T r  S T T H  0޽h ? 3f3f___PPT10i.ȤŐ+D=' = @B + K0 P (   r   S TT,   T H   0޽h ? 3f3f___PPT10i._t+D=' = @B + K0 0$(  r  S TT,M  T r  S dT T H  0޽h ? 3f3f___PPT10i.zpl+D=' = @B += )K0 <4(  r  S F T,M  F  x  c $F  F   0 NA P? ?6   P  H  0޽h ? 3f3f___PPT10i.-t7+D=' = @B +e K0 d\X(  Xr X S TT,M  T B X 0tT]]  <tree> (MONO (Ukraine|LNKQpQ) (MONO (MONO (MONO (because of|V) (INVERT (INVERT (the chaos|vmqN) (caused by|_S)) (the presidential election|;`~ >N))) (in the|ۏeQ)) (third week of|,{ NhT))) </tree>C K __>3 H X 0޽h ? 3f3f___PPT10i. '+D=' = @B +&  K0 %%0=` 4%(  r  S TT,  T <t   ] #"&@?@@   <PT ?'  P )=7,  <U ?B '  P )=7,  <T U ?\ B  P )=7,  < U ?w \  P )=7,   <U ? w  P )=7,   <'U ?'   P )=7,   <)U ?B'  P )=7,   <0U ?\B  P )=7,   6?U ?w\  P )=7,  <GU ?w  P )=7,  <OU ?' L  P )=7,  6,XU ?BL'  P )=7,  6L`U ?\LB P )=7,  <hU ?wL\ P )=7,  <pU ?Lw P )=7,  <xU ?'  L P )=7,  6U ?B' L P )=7,  6dU ?\BL P )=7,  <U ?w\L P )=7,  <̙U ?wL P )=7,  <U ?'   P )=7,  <4U ?B'  P )=7,  <TU ?\B P )=7,  <U ?w\ P )=7,  6U ?w P )=7,fB  6o ? `B  01 ? `B   01 ?L L`B ! 01 ? `B " 01 ? fB # 6o ? fB $ 6o ? `B % 01 ?ww `B & 01 ?\\ `B ' 01 ?BB `B ( 01 ?' ' fB ) 6o ?  RB * s *Dr RB + s *D${ $ , 00UAx( 5f 2A - 08UD 5e 2A . 0U *K X Every crossing point is a corner! 2!E 2 0U-  9A 2EX2 5 0WPX2 D 0pRB I s *D8 8RB J s *D  K 6UH = top right 2 A L 6U*  @ bottom right 2 A M 6`Uv <top left 2 A N 6U*v  ? bottom left 2 AX O 0X P 00 S 00Uc `   .STRAIGHT link and INVERT link can not co-exist/ l2 E EEE E EE^B V 6Do  Y 0HUC"? } 9B 2ERB _ s *Dw RB ` s *D" H  0޽h ?/@OP 3f3f___PPT10i.n X+D=' = @B + !K0 l(  lr l S s& &  l s s&0e0e 3"0e`T,M  & H l 0޽h ? 3f3f___PPT10i.W+D=' = @B +  0 (  X  C $   &  S l&$ 0  &  H  0޽h ? 3380___PPT10.  0 ,(  ,X , C $   0 , S $ 0$ 0  0  H , 0޽h ? 3380___PPT10.@9[ 0 pTk(  TX T C $   J T S J$ 0  J m=IGR measures: how precisely the feature predicates the class =H T 0޽h ? 3380___PPT10. g  0 X(  XX X C $   0 X S %0$ 0  0  H X 0޽h ? 3380___PPT10.ۨ  0 \(  \X \ C $   0 \ S ,@0$ 0  0  H \ 0޽h ? 3380___PPT10.ۨ  0 `(  `X ` C $   0 ` S Pq0$ 0  0  H ` 0޽h ? 3380___PPT10.ۨ  0 h(  hX h C $   0 h S 0$ 0  0  H h 0޽h ? 3380___PPT10.ۨ   0 p(  pX p C $   K p S  K$ 0  K  H p 0޽h ? 3380___PPT10.p   0  (  X  C $   0  S xQ#$ 0  #  H  0޽h ? 3380___PPT10.Nj.   0 P(  X  C $   U  S U$ 0  U  H  0޽h ? 3380___PPT10.t0|\   0 `(  X  C $   0  S 0$ 0  0  H  0޽h ? 3380___PPT10.t0|\  0 (  X  C $   K  S K$ 0  K  H  0޽h ? 3380___PPT10.x׾o  0 (  X  C $   K  S $'K$ 0  K  H  0޽h ? 3380___PPT10.x׾o  0  (  X  C $   K  S K$ 0  K  H  0޽h ? 3380___PPT10.x׾o  0 `(  X  C $   T  S dT$ 0  T  H  0޽h ? 3380___PPT10.~l  0 p(  X  C $   Q  S lQ$ 0  Q  H  0޽h ? 3380___PPT10.~l  0 0(  X  C $   T  S T$ 0  T  H  0޽h ? 3380___PPT10.F  0 p(  X  C $   S  S S$ 0  S  H  0޽h ? 3380___PPT10.  0 (  X  C $   T  S T$ 0  T  H  0޽h ? 3380___PPT10.  0 (  X  C $   T  S T$ 0  T  H  0޽h ? 3380___PPT10.  0 d(  dX d C $   S d S S$ 0  S  H d 0޽h ? 3380___PPT10.ϊ  0 h(  hX h C $   T h S (T$ 0  T  H h 0޽h ? 3380___PPT10.ϊ" 0  ((  ^  S $   0  c $^0$ 0  0  H  0޽h ? 3380___PPT10.@9$ 0 ((  ^  S $   J  c $J$ 0  J  H  0޽h ? 3380___PPT10.@9   0 (  X  C $   0  S Ё0$ 0  0  H  0޽h ? 3380___PPT10.`~P  0 (  X  C $   0  S 0$ 0  0  H  0޽h ? 3380___PPT10.`~P  0 (  X  C $   V  S xV$ 0  V  H  0޽h ? 3380___PPT10.@e\& 0 ((  ^  S $   K  c $D6K$ 0  K  H  0޽h ? 3380___PPT10.@9) 0 p((  ^  S $   S  c $S$ 0  S  H  0޽h ? 3380___PPT10.@9 + 0 (  X  C $   0  S M0$ 0  0  H  0޽h ? 3380___PPT10.ͤ  % 0 (  X  C $   K  S hFK$ 0  K  H  0޽h ? 3380___PPT10.ͤ  ' 0 (  X  C $   K  S K$ 0  K  H  0޽h ? 3380___PPT10.ͤ  ( 0 (  X  C $   S  S S$ 0  S  H  0޽h ? 3380___PPT10.ͤ  * 0 (  X  C $   T  S T$ 0  T  H  0޽h ? 3380___PPT10.ͤ  , 0 (  X  C $   H   S  H $ 0  H   H  0޽h ? 3380___PPT10..~9x[l Q;}NKۇՔ JDB=*A"mW죻)I!!!><>I?~M뜙;2[Klٜ{=3Յ5Ad1Xd:ZƓɤџAVvO m vS)TCyy>5޽:6:\|Jn7lj Z: O9's+p| C]p}J${'Z(^dz Q?kr 1(BoŸ@+Y{fd~r1du=Nd'vݩ~M{Bq2ʋ 36I - J<=lotK,VSsq"{!}Քnfq~o~~Csi_o*[_7]zJ)9vCWGB0ܾ'p˘~~(N4-||p? iq5 vEBE"&?ZJ|ɟ)N[ S{55t$B{#'o+Xk=M1\7WS $LGQb/HUN^ Y TnھZWu^59#Us}Ay1:;-y#&qcl)@/v3tQz)[sҫ'3$yWi-vF,I8XƔfڳ#r, qZvjE4p/6aU،u* : 1ё8V|>@=yބ$~HkGR T[ݦ=5xO F~L}|Zyw ۳Kޗ-1&2/K|.6V-)g / mԥKx7T@:"}AnM'Y/ƪ1,p=s'Xwu_!o7z]phLzg< TxX]LU>sgwa( 0[(#Lj 5I,aMa 4]KD҄SVS&6'jLfJbQa=;̆]@+gswwsso o]zGHGA\6zC@l[f|W+9 FAv0Dš=WD{ÿNt?WrC:cJd=R,avVµNmrN:c63OSN'1|n%y1.1Mvٲo,<ɱ:B #Fߨ~W7# ws7?z.}Lhbu&?G|:iM5t)֒KǮ'e[|LWR$bo[t`P5N| ӿ}Eo;ySƘgUCLHYV1uA8E#6sj&Qze\Uods [~S\f%X<~(tÕU {`o !<9ԛ"! !ԯ[^|*p: 9`wO~{Lss;$w Wcg~tU4Z{":wM0kh?n9*ZNRYHR!(uv??e;12 g{@5jgI Jv,b:. ݿ]{bz(f>m`[PO?ߪoX{ri}S>tƴ1!\>SfL-T<"-AN;IOrA%m{ψɚ.<'̕> 3 zPzw IYpSX!zQ>BoOA3{C37LB&xYolSU?ﾶ[O7m-unca0`f`H05lV' f!"qFYD 5QC&D (ls彲e!Y}sϽ\)oOK4zTpP Y?1Om0@uЅ=@bIQd *?B6)m vF:c2dHkpЍX>'WAؾ>; !GCXZ Y_ܣ;3mXq]`e7 IsdK3+4{g`M~a_h&Vi3`2iNƆ G/! u:l3P2 F\ìЖPNO|\?)vS<|@ bB6JK1W?ɽ7Q'lTZZ'_" 7B"WReek,F }’uy%,dCKG,$a#}, =j^mc N5VwTA B{R6ZD]%^Cؗ^x6n X EcX[QN{CXKkxzWNW ./63Mt]fC_B 0M=Y@_^#459mwnjbiN{t~^K^%Ob[&}K\Sc|.Rzy$).03c-S,qB/ް IB8.qb!?xn~ˆ٭R#qB^3wz [HBs\bR3>5l Ɲ:)HKr3>W"̂}N%&rW.3aTqMܚzG3xzSx7rFƖ743>Vfz'ն\ /mT; ™l6rP-;|^:(ǫeRc;6lQ?ǦM[^Oj==$6ǤVr)l<Rnq ?*6SvXoW?t,Ǜ, =H̿CnSi4 ]i[LU;uj$ݧe+|ի}ykG mZn䡆z!ԤI ayXe|,~`>n ӪY9},w5ߟ~/ U*.V@$Β\ T0Fy[/@zNN1 e ʧ2-{Tɜ^uˈv- 6H+3_72#=-?g`^1g?'fc6E+v@@3D{{-O,юԂd6r@(/x67{ %FcUOZ*㢲.=~mLށm]& "xYmlSe>zW֍mi b#a#BC[V֮0d1@CDT&3ƘIb$Q@$$(Dasޏr[:ו}lg9;M!OVS>4wj*Y7955ڧrOIaIH_zd\G&}~{{˱/4?T; `jM4ZɻW̘f:Pc<7r|boFې6)^ (ɧ(׊'R>Auf'+/n@OYC"1A]/+6sbR(vR즐+Q} r)nS G 5@1DL]-e)M?*\We]t44M f@hP ;gP.j[:@ o(*FLG7L/R#.m| uPPm$0S9FGvxgL:I=@vz/Dݏj˾,>]{?3v< =: N*,J)xUkuU~~6n .I X:&0b >~qz 4NFk];_\|=vJ}]DSG~ѽO_fy>b?}:BlptݪvjSN23k7Q,'na+z\i+l7oDCqeg*yKC,Tͻ%=+\lBeo|¿*l|Ea&吲b«xnx/)@. ه(c[S=I7e |}]X 6ҡtut=_aV2q&{6Oţuͯ>VYgL|EbqbA~ch]>~bh}l^܉ 뫿߻ݹd޳,w[0WAƃͫ#|t-'!F^셏=\^/ $d:j ri_ؚ =1 uGj! m|R n]t[.;N䵒10ĝGY<Ɩq^iv׻4j7d;8?kyg';Z杝,#]杖tL'MNyBN7y&\&xg>KwVɺw)2RHMY,c+eVjK\cKh XVpqd6y.bo>Cq"xX]LU>wvYʀe)%q+ TӒŤ5EMHɬ;vev$'`ԘjJiDcMƶbjc saVf9;g9;wApI x`f|)u USPRu6'J:!6a| > J%9 8!'S޺}ȶԐO%*:h,u=ق 8 /y2l@LQ-Y;pMFT{0~j+3R~jɽ)ٴL'_eiTzf'2M'T歃EblOrz6ЍoK4U<,Ӗ.?W|7kf?`@>O t'Tg?]?_cGvT.QC&j 5b>͓imOX7ݟ!5x7$_ݮ-\ũ4|/5JYWlWAdqbw>YHz,R"m$(ֆՠ+w4 pB؟ITvM M˾6R?{VXwi»x*+EX}nƍH_wx1n1᫚tJ,bX0u_Q 19g* 7$̈́$>]N *' oO ׉?zz\ mtKb_pnViX9,g=Pf,Sƿq@֢UWVqe'zWOiW?Z'~ߕkt~Ejj|ɀ3+?`oW~+? c:?1oxWKTQιfy|bf"FERac:2ޱ6H*!j< ;Liq\}H8+r^f٬cS4I+3,U9;lDHYݕ!jb\:{prʶX$u8o?*>ThCŀم~^ZaϪ] F#HzxwPMM>7.u0"aΠ~W uZc~ c_Hjxz@sy^VP}B)1C!9Z!Lȑj9ڨ8@ *>l=NNŰ9uӹe?7{aA(dUu @+FcnQ: 0~qMjJ?UXY׉}7jL=.⃂QAnOϭ҆ϚS"R/=CdSAFbdK?(Tv̝uwֵY];sܹ{9~J?ZN<ȎzưpQ gpIX:( >B ["{Nt mN^O9lO>p'32p=+cua?OЏvդ~ه#\@~Q)oKB?'4n-jE繠v{Ѵ8EJw+cR1gq?9ya|29a/`\h]6߯Xv)da!~fSΎ"qF5yM9>ku1Ix :,*H%Ɲ滆161ߣ`]N}R;#k^Aá ;+6!7V7)n8L3o(Fe_'t p%KD/W^ձs&u.R9K-8CaDQ >ii_߈8ϟ[d|9 c?d8L?5\Ȟȝ*C_r1gBc\Ym3WgI/!}|9={+-KlYm=Å|: 1nx_KQ#ioQ'3Uou83z:7U`Wngo-YaL*ɍ[.@A;5 JO?w\XYuFu9NMgwCc@gG8NgC7Toe?Ȃhuw ʏ;3ȕm~<*||2>XO2^jo4j*x> RwFT?^uWG$bI29x[l Q;}NKۇՔ JDB=*A"mW죻)I!!!><>I?~M뜙;2[Klٜ{=3Յ5Ad1Xd:ZƓɤџAVvO m vS)TCyy>5޽:6:\|Jn7lj Z: O9's+p| C]p}J${'Z(^dz Q?kr 1(BoŸ@+Y{fd~r1du=Nd'vݩ~M{Bq2ʋ 36I - J<=lotK,VSsq"{!}Քnfq~o~~Csi_o*[_7]zJ)9vCWGB0ܾ'p˘~~(N4-||p? iq5 vEBE"&?ZJ|ɟ)N[ S{55t$B{#'o+Xk=M1\7WS $LGQb/HUN^ Y TnھZWu^59#Us}Ay1:;-y#&qcl)@/v3tQz)[sҫ'3$yWi-vF,I8XƔfڳ#r, qZvjE4p/6aU،u* : 1ё8V|>@=yބ$~HkGR T[ݦ=5xO F~L}|Zyw ۳Kޗ-1&2/K|.6V-)g / mԥKx7T@:"}AnM'Y/ƪ1,p=s'Xwu_!o7z]phLzg< TxX]LU>sgwa( 0[(#Lj 5I,aMa 4]KD҄SVS&6'jLfJbQa=;̆]@+gswwsso o]zGHGA\6zC@l[f|W+9 FAv0Dš=WD{ÿNt?WrC:cJd=R,avVµNmrN:c63OSN'1|n%y1.1Mvٲo,<ɱ:B #Fߨ~W7# ws7?z.}Lhbu&?G|:iM5t)֒KǮ'e[|LWR$bo[t`P5N| ӿ}Eo;ySƘgUCLHYV1uA8sPvMٜ/KYcG|+fR8t 2Tw LIHSx$,`vlci٬ƴp?Xb8f_QpX!}9oٽOm} KyC|BW: uI'3 ;`ti 0ݫ.Zww[ַW/21kpdM9!QcOJy~8kj-Ե͢m0f&㯞10HXc2YtƆ4rLq|RO-]\3EO> 9_mA }H\D"7݅7);Nօ-gN-?oΏM\^Od1_ ƥ7;~}OE?d]ڊ dبzRN}&B\_XِGߋ J=~yA-kPr%g|+Ey*3i\ntҽd4^n'fҝnj cHBӰI|$I)CfӬt;Mth(> ŗ(b)XJ*"4/c(SisܻٝdlX,'sw;s{o߼#8!`5C 4j.Szn۪B0 q< ,Mm9_+d~pZQ5uBfgq3NPp1HbṲ0>q@վk(vT#V9Oi첶־UV`s{^$6㿙]ўJ֟r?.B:PhjM{=}nacFGq\F%qJs@j4=-mZIfi h@o ~5Y^g}og#2%43P{$o.oiԇLЮ1zZebo!ZUq]cMĤElی1u0e'žOUA_Lp(.f?gad'o/9o/x2{lƿHlmr=?wy1OɌ3]0CX$mFf̓X8^"&~:oL$eE&Tv}qW)_C59|F}V*=2eYfZ^樓yN*lŸ4"|?#J+2󸾑p(Cue^{}oxo[gp_֐la$OiteV$v%&) +|fllJ3$.mg$l*NLZ翹d ]] 3h".*R}׃L[p_jw y{iY+m_8D[Zo[Ug_ 99lq?5|؊:4Q(-|#@.`rH 迁Z;~}7O%I7oɩ.6L)_ ]SoZEn#x=?AB=J<Z:PO~P>/d'̿^Op[S'crjrvj q<67FF=k3׬xXKQ?Yή T`lEZZ+m_ڲA(I$QP=KQEDPԃC$%=sgfY4gE rf;{GU_ D1dB]Z_D~iwʩ@5A;#;H{Œ ¯0FѲOH)RR"BB$Y"9(bs JYIغO`GcrG.ƂXo~eUpB^V: xTqւ 9!7՚а4KKn3-rPaQU]g}PEjl4r/zp'ݾ' Ɗڌ+oS( *>RF>`fz'+?eDG@ʥM[OjLR@ާ-zzw|:{)(&FZn #gCD%AtºּJ%I &? ~x Q(   PYlQ_ Equation.30 Microsoft lQ_ 3.0ZlQ_ Equation.30 Microsoft lQ_ 3.0[lQ_ EquOh+'0T hp    õƬ 1  Devi XiongProfile Devi Xiong69iMicrosoft PowerPointP@ґ*@@0GSg  )'    """)))UUUMMMBBB999|PP3f333f3333f3ffffff3f̙3ff333f333333333f33333333f33f3ff3f3f3f3333f33̙33333f333333f3333f3ffffff3f33ff3f3f3f3fff3ffffffffff3ffff̙fff3fffff3fff333f3f3ff3ff33f̙̙3̙ff̙̙̙3f̙3f333f3333f3ffffff3f̙3f3f3f333f3333f3ffffff3f̙3f3ffffffffff!___www@<$4'A x(xKʦ """)))UUUMMMBBB999|PP3f3333f333ff3fffff3f3f̙f3333f3333333333f3333333f3f33ff3f3f3f3333f3333333f3̙33333f333ff3ffffff3f33f3ff3f3f3ffff3fffffffff3fffffff3f̙ffff3ff333f3ff33fff33f3ff̙3f3f3333f333ff3fffff̙̙3̙f̙̙̙3f̙3f3f3333f333ff3fffff3f3f̙3ffffffffff!___www____________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________ __________________ ________ ___________ __________ ____________ ___ ______ݼLotntnLֻoLootLotݻmnmKssnmmnܼݻsgJgmmJJϴ׻üⶑnݴϑܼϴ޽sntⵑϵ޻ϴömCCn޻ϴ޼mJnڭ޼⵻ݵݼݽ׼ܼỻ޼ݼݺϮϮS(   pYlQ_ Equation.30 Microsoft lQ_ 3.0ZlQ_ Equation.30 Microsoft lQ_ 3.0[lQ_ Equation.30 Microsoft lQ_ 3.0\lQ_ Equation.30 Microsoft lQ_ 3.0_lQ_ Equation.30 Microsoft lQ_ 3.0`lQ_ Equation.30 Microsoft lQ_ 3.0dlQ_ Equation.30 Microsoft lQ_ 3.0elQ_ Equation.30 Microsoft lQ_ 3.0'klQ_ Equation.30 Microsoft lQ_ 3.0(llQ_ Equation.30 Microsoft lQ_ 3.0IwlQ_ Equation.30 Microsoft lQ_ 3.0JxlQ_ Equation.30 Microsoft lQ_ 3.0KylQ_ Equation.30 Microsoft lQ_ 3.0LzlQ_ Equation.30 Microsoft lQ_ 3.0O{lQ_ Equation.30 Microsoft lQ_ 3.0P}lQ_ Equation.30 Microsoft lQ_ 3.0/ 0DDArialSans~0z[ 0D[SOalSans~0z[ 0 DBook Antiqua~0z[ 00DTimes New RomanYlQ_ Equation.30 Microsoft lQ_ 3.0ZlQ_ Equation.30 Microsoft lQ_ 3.0[lQ_ Equation.30 Microsoft lQ_ 3.0\lQ_ Equation.30 Microsoft lQ_ 3.0_lQ_ Equation.30 Microsoft lQ_ 3.0`lQ_ Equation.30 Microsoft lQ_ 3.0dlQ_ Equation.30 Microsoft lQ_ 3.0elQ_ Equation.30 Microsoft lQ_ 3.0'klQ_ Equation.30 Microsoft lQ_ 3.0(llQ_ Equation.30 Microsoft lQ_ 3.0IwlQ_ Equation.30 Microsoft lQ_ 3.0JxlQ_ Equation.30 Microsoft lQ_ 3.0KylQ_ Equation.30 Microsoft lQ_ 3.0LzlQ_ Equation.30 Microsoft lQ_ 3.0O{lQ_ Equation.30 Microsoft lQ_ 3.0P}lQ_ Equation.30 Microsoft lQ_ 3.0/ 0DArialBlacr0z[ 0D[SOalBlacr0z[ 0 DBook Antiquar0z[ 00DTimes New Roman0z[ 0@DWingdingsRoman0z[ 0PDFranklin Gothic Mediumz[ 0"`DVerdana Gothic Mediumz[ 0"pDGungsuhChethic Mediumz[ 01DNSeeOuhChethic Mediumz[ 0DArial Blackhic Mediumz[ 0" A .  @n?" dd@  @@``    IF   D   r !!"#a$%& ) ,  /01234~67>GCDEFGHIL   X[\]^_ ab  hijkl mnop1 tBvwxyz{|}~ 2$^K)V"|b$XڼV&ռ,wx2$9_= *f,2 2$b1;KNnQf b$ÏY ~&RՃT e 2$~U6U~g2$;ɿ]V$2$O18 { 2$NG^Rf!]$$$$2$); KpDz*~-/e2$ܱ&SaFu 2$vP xXia "$b$U׷2?`v,j#b$q;@aZ&hN|$2 B !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~$loof5]Cj&$2$K;15HXI'2$:Źg~.EhWAJ) 0AA ffffff@ۉ8ʚ;ʚ;g4GdGd z[ 0ppp@ <4ddddL 0r 0___PPT10 ppH___PPT9*"n_4ln,|PNG  IHDR +tsRGB PLTEff3fQ} cmPPJCmp0712cOtRNS@fIDATc`PA-Q-0 yx`YsIENDB`[nQy  a*lD!@PNG  IHDR exsRGBNPLTEkc{PowerPoint Document(iMDocumentSummaryInformation8lation.30 Microsoft lQ_ 3.0\lQ_ Equation.30 Microsoft lQ_ 3.0_lQ_ Equation.30 Microsoft lQ_ 3.0`lQ_ Equation.30 Microsoft lQ_ 3.0dlQ_ Equation.30 Microsoft lQ_ 3.0elQ_ Equation.30 Microsoft lQ_ 3.0'klQ_ Equation.30 Microsoft lQ_ 3.0(llQ_ Equation.30 Microsoft lQ_ 3.0IwlQ_ Equation.30 Microsoft lQ_ 3.0JxlQ_ Equation.30 Microsoft lQ_ 3.0KylQ_ Equation.30 Microsoft lQ_ 3.0LzlQ_ Equation.30 Microsoft lQ_ 3.0O{lQ_ Equation.30 Microsoft lQ_ 3.0P}lQ_ Equation.30 Microsoft lQ_ 3.0/ 0DArialBlac~0z[ 0"D[SOalBlac~0z[ 0 DBook Antiqua~0z[ 00DTimes New Roman0z[ 0@DWingdingsRoman0z[ 0PDFranklin Gothic Mediumz[ 0"`DVerdana Gothic Mediumz[ 0"pDGungsuhChethic Mediumz[ 01DNSeeOuhChethic Mediumz[ 0DArial Blackhic Mediumz[ 0" A .  @n?" dd@  @@``    IF   D   r !!"#a$%& ) ,  /01234~67>GCDEFGHIL   X[\]^_ ab  hijkl mnop1 tBvwxyz{|}~ 2$^K)V"|b$XڼV&ռ,wx2$9_= *f,2 2$b1;KNnQf b$ÏY ~&RՃT e 2$~U6U~g2$;ɿ]V$2$O18 { 2$NG^Rf!]$$$$2$); KpDz*~-/e2$ܱ&SaFu 2$vP xXia "$b$U׷2?`v,j#b$q;@aZ&hN|$2$loof5]Cj&$2$K;15HXI'2$:Źg~.EhWAJ) 0AA ffffff@ۉ8ʚ;ʚ;g4BdBd z[ 0pppp@ <4ddddL 0~ 0___PPT10 ppH___PPT9*"n_4ln,|PNG  IHDR +tsRGB PLTEff3fQ} cmPPJCmp0712cOtRNS@fIDATc`PA-Q-0 yx`YsIENDB`[nQy  a*lD!@PNG  IHDR exsRGBNPLTEkc{絔έֽεƭƥƽ{s cmPPJCmp0712x~tRNS AyIDATMI0{d{1@Gs @c3|bXֻ$镰3дY ;6TJ~UCo@{} P{4$]$gc>/13"+^ZCLKs}XmIENDB`?Z-FDevi Xiong et al. ICT, CAS, BeijingO  =1QMaximum Entropy Based Phrase Reordering Model for Statistical Machine TranslationBR&,",&,+",Deyi Xiong, Qun Liu and Shouxun Lin Multilingual Interaction Technology & Evaluation Lab Institute of Computing Technology Chinese Academy of Sciences {dyxiong, liuqun, sxlin} at ict dot ac dot cn Homepage: http://mtgroup.ict.ac.cn/~devi/ """" "s".g  *g   y Outline"^Previous work Maximum entropy based phrase reordering System overview Experiments Conclusions  Previous WorkContent-independent reordering models E.g. distance-based or flat reordering models Learn nothing for reordering from real-world bitexts Content-dependent reordering models Lexicalized reordering models [Tillmann, 04; Och et. al. 04; & ] Totally dependent on bilingual phrases With a large number of parameters to estimate Without generalization capabilities&.5%@y&.5%  @&R>E+ %Can We Build Such a Reordering Model?,& $$$Content-dependent but not restricted by phrases Without introduction of too large number of parameters but still powerful With generalization capabilities -Build It Conditioned on Features, not Phrases:.""" "Features can be: Some special words or their classes in phrases Syntactic properties of phrases Surface attributes like distance of swapping Advantages of feature-based reordering: Flexibility Less parameters Generalization capabilities \|(:| : q+Feature-based Reordering"Discriminative Reordering Model proposed by Zens & Ney in NAACL 2006 Workshop on SMT We have become aware of this work when we prepare the talk Very close to our work But still different: Implemented under the IBM constraints Using different feature selection mechanism NUgSUgS ,,V"Outline"^Previous work Maximum entropy based phrase reordering System overview Experiments Conclusions *_()Reordering as Classification$Regard reordering as a problem of classification Two classes problem under ITG constraints {straight, inverted} Multi-class problem if positions are considered under the IBM constraints Our work focused on the reordering under the ITG constraintsl1Z+ZZJZ=Z1+J =W $MaxEnt-based Reordering Model (MERM)"%  MA reordering framework for BTG MERM under this framework Feature function:--TTraining for MERM"Training procedures: 3 steps Learning reordering examples Generating features ( ) from reordering examples Parameter ( ) estimation using off-the-shelf MaxEnt toolkits :$ . Reordering Example" FeatureseLexical feature: source or target boundary words Collocation feature: combinations of boundary words 2f!! AWhy Do We Use Boundary Words as Features: Information Gain Ratio BB" ]$Outline"fPrevious work Maximum entropy based phrase reordering System overview (Bruin) Experiments Conclusions Bg6" Translation Model%Built upon BTG The whole model is built in the log-linear form The score to apply lexical rules is calculated using features similar to many state-of-the-art systems The score to apply merging rules is divided into two parts The reordering model score The increment of language model score NBABA 1GDifferent Reordering Models Are Embedded in the Whole Translation ModelHH"oThe reordering framework MaxEnt-based reordering model Distance-based reordering model Flat reordering modelP2CKY-style Decoder"Core algorithm Borrowed from CKY parsing algorithm Edge pruning Histogram pruning Thresholding pruning Language model incorporation Record the leftmost & rightmost n words for each edge $ '6$ ' 6"R \g&Outline"^Previous work Maximum entropy based phrase reordering System overview Experiments Conclusions *_F 絔έֽεƭƥƽ{s cmPPJCmp0712x~tRNS AyIDATMI0{d{1@Gs @c3|bXֻ$镰3дY ;6TJ~UCo@{} P{4$]$gc>/13"+^ZCLKs}XmIENDB`?Z-FDevi Xiong et al. ICT, CAS, BeijingO  =%3QMaximum Entropy Based Phrase Reordering Model for Statistical Machine TranslationBR h%Experiment Design"To test MERM against various reordering models, we carried out experiments on: Bruin with MERM Bruin with monotone search Bruin with distance-based reordering model Bruin with flat reordering model Pharaoh, a distance-based state-of-the-art system (Koehn 2004)4OOj'Systems Settings"3Small Scale Experiments"LNIST MT 05 Training data: FBIS (7.06M + 9.15M) Language model: 3-gram trained on 81M English words (most from UN corpus) using SRILM toolkit Development set: 580 sentences length of at most 50 Chinese characters from NIST MT 02 IWSLT 04 Small data track 20k sentences for training of TM and LM 506 sentences as the development set N  _  _ 8 MERM Training"m(Results on Small Scale Data"AScaling to Large Bitexts"Just used lexical features for MaxEnt reordering model Training data 2.4M sentence pairs (68.1M Chinese words and 73.8M English words) Two 3-gram language models One was trained on the English side The other was trained on the Xinhua portion of the Gigaword corpus with 181.1M words Used simple rules to translate number, time expressions and Chinese person names New BLEU score: 0.291 EZBZZyZgZZZEBy  g>MResults Comparison" n)Outline"^Previous work Maximum entropy based phrase reordering System overview Experiments Conclusions "_R @ Comparisons "B Conclusions "MaxEnt-based reordering model is Feature-based Content-dependent Capable of generalization Trained discriminatively Easy to be integrated into systems under the IBM constraints :!!p* Future Work "More features Syntactic features Global features of the whole sentences & Other language pairs English-Arabic Chinese-MongolianN<!<! C Thank you!   7Training "Run GIZA++ in both directions Use grow-diag-final refinement rules Maximum phrase length: 7 words on the Chinese side Length ratio: max(|s|, |t|)/min(|s|, |t|) <= 3>'Y  |,&Language Model Incorporation (further)''"The edge spans only part of the source sentence The history of LM is not available the language model score has to be approximated by computing the score for the generated target words alone Combination of two neighbor edges only need to compute the increment of the LM score: v0"40"4 OTree" - Related Definitions" U/The Algorithm of Extracting Reordering ExamplesZFor each sentence pair do Extract bilingual phrases Update the links for the four corners of each extracted phrases For each corner do If it has a STRAIGHT link with phrase a and b Extract the pattern: <a; b> STRAIGHT If it has a INVERT link with phrase a and b Extract the pattern: <a; b> INVERT[.',%[.  , /!#$%'(, / 0 4 56>?GHIJRSX^ab c!i"o#r$s%t&u'v(~)  xX_h[U9777Y&ntcdӤZFeYMYdi5[=Lp(8CP*?Jw==ion#_8?ߟeW ,5P]m*@-elbhraB*I;!Psz;/}A,RN= ]L7@{?^xũ$y8?*W`Eȏ" =\n&9Ǽ ( *Sǵ\ oo۶tR#ui-Of {iK1ϋ|N_|q:~M'7X3uo[~ a}.ԣ!d#勷OO3񍏾}7vRD_;coAK"{_/3JV5EfBF(ªu]N[0jvpb6jkWq5mC0NO)LpAá ;+6!7V7)n8L3o(Fe_'t p%KD/W^ձs&u.R9K-8CaDQ >ii_߈8ϟ[d|9 c?d8L?5\Ȟȝ*C_r1gBc\Ym3WgI/!}|9={+-KlYm=Å|: 1nx_KQ#ioQ'3Uou83z:7U`Wngo-YaL*ɍ[.@A;5 JO?w\XYuFu9NMgwCc@gG8NgC7Toe?Ȃhuw ʏ;3ȕm~<*||2>XO2^jo4j*x> RwFT?^uWG$bI29x[l Q;}NKۇՔ JDB=*A"mW죻)I!!!><>I?~M뜙;2[Klٜ{=3Յ5Ad1Xd:ZƓɤџAVvO m vS)TCyy>5޽:6:\|Jn7lj Z: O9's+p| C]p}J${'Z(^dz Q?kr 1(BoŸ@+Y{fd~r1du=Nd'vݩ~M{Bq2ʋ 36I - J<=lotK,VSsq"{!}Քnfq~o~~Csi_o*[_7]zJ)9vCWGB0ܾ'p˘~~(N4-||p? iq5 vEBE"&?ZJ|ɟ)N[ S{55t$B{#'o+Xk=M1\7WS $LGQb/HUN^ Y TnھZWu^59#Us}Ay1:;-y#&qcl)@/v3tQz)[sҫ'3$yWi-vF,I8XƔfڳ#r, qZvjE4p/6aU،u* : 1ё8V|>@=yބ$~HkGR T[ݦ=5xO F~L}|Zyw ۳Kޗ-1&2/K|.6V-)g / mԥKx7T@:"}AnM'Y/ƪ1,p=s'Xwu_!o7z]phLzg< TxX]LU>sgwa( 0[(#Lj 5I,aMa 4]KD҄SVS&6'jLfJbQa=;̆]@+gswwsso o]zGHGA\6zC@l[f|W+9 FAv0Dš=WD{ÿNt?WrC:cJd=R,avVµNmrN:c63OSN'1|n%y1.1Mvٲo,<ɱ:B #Fߨ~W7# ws7?z.}Lhbu&?G|:iM5t)֒KǮ'e[|LWR$bo[t`P5N| ӿ}Eo;ySƘgUCLHYV1uA8sPvMٜ/KYcG|+fR8t 2Tw LIHSx$,`vlci٬ƴp?Xb8f_QpX!}9oٽOm} KyC|BW: uI'3 ;`ti 0ݫ.Zww[ַW/21kpdM9!QcOJy~8kj-Ե͢m0f&㯞10HXc2YtƆ4rLq|RO-]\3EO> 9_mA }H\D"7݅7);Nօ-gN-?oΏM\^Od1_ ƥ7;~}OE?d]ڊ dبzRN}&B\_XِGߋ J=~yA-kPr%g|+Ey*3i\ntҽd4^n'fҝnj cHBӰI|$I)CfӬt;Mth(> ŗ(b)XJ*"4/c(SisܻٝdlX,'sw;s{o߼#8!`5C 4j.Szn۪B0 q< ,Mm9_+d~pZQ5uBfgq3NPp1HbṲ0>q@վk(vT#V9Oi첶־UV`s{^$6㿙]ўJ֟r?.B:PhjM{=}nacFGq\F%qJs@j4=-mZIfi h@o ~5Y^g}og#2%43P{$o.oiԇLЮ1zZebo!ZUq]cMĤElی1u0e'žOUA_Lp(.f?gad'o/9o/x2{lƿHlmr=?wy1OɌ3]0CX$mFf̓X8^"&~:oL$eE&Tv}qW)_C59|F}V*=2eYfZ^樓yN*lŸ4"|?#J+2󸾑p(Cue^{}oxo[gp_֐la$OiteV$v%&) +|fllJ3$.mg$l*NLZ翹d ]] 3h".*R}׃L[p_jw y{iY+m_8D[Zo[Ug_ 99lq?5|؊:4Q(-|#@.`rH 迁Z;~}7O%I7oɩ.6L)_ ]SoZEn#x=?AB=J<Z:PO~P>/d'̿^Op[S'crjrvj q<67FF=k3׬xXKQ?Yή T`lEZZ+m_ڲA(I$QP=KQEDPԃC$%=sgfY4gE rf;{GU_ D1dB]Z_D~iwʩ@5A;#;H{Œ ¯0FѲOH)RR"BB$Y"9(bs JYIغO`GcrG.ƂXo~eUpB^V: xTqւ 9!7՚а4KKn3-r(SwPmchlrv}{? /b~x R(   `&,",&,+",Deyi Xiong, Qun Liu and Shouxun Lin Multilingual Interaction Technology & Evaluation Lab Institute of Computing Technology Chinese Academy of Sciences {dyxiong, liuqun, sxlin} at ict dot ac dot cn Homepage: http://mtgroup.ict.ac.cn/~devi/ """" "s".g  *g   y՜.+,0<     ĻʾhICTOQ## 0Arial Book AntiquaTimes New Roman WingdingsFranklin Gothic MediumVerdana GungsuhChe κ Arial BlackComic Sans MSProfileMicrosoft ʽ 3.0RMaximum Entropy Based Phrase Reordering Model for Statistical Machine TranslationOutlinePrevious Work&Can We Build Such a Reordering Model?.Build It Conditioned on Features, not PhrasesFeature-based ReorderingOutlineReordering as Classification%MaxEnt-based Reordering Model (MERM)Training for MERMReordering Example FeaturesBWhy Do We Use Boundary Words as Features: Information Gain Ratio OutlineTranslation ModelHDifferent Reordering Models Are Embedded in the Whole Translation ModelCKY-style DecoderOutlineExperiment DesignSystems SettingsSmall Scale ExperimentsMERM TrainingResults on Small Scale DataScaling to Large BitextsResults ComparisonOutline Comparisons Conclusions Future Work Thank you! Training'Language Model Incorporation (further)TreeRelated Definitions0The Algorithm of Extracting Reordering Examples  õ Outline"^Previous work Maximum entropy based phrase reordering System overview Experiments Conclusions  Previous WorkContent-independent reordering models E.g. distance-based or flat reordering models Learn nothing for reordering from real-world bitexts Content-dependent reordering models Lexicalized reordering models [Tillmann, 04; Och et. al. 04; & ] Totally dependent on bilingual phrases With a large number of parameters to estimate Without generalization capabilities&.5%@y&.5%  @&R>E+ %Can We Build Such a Reordering Model?,& $$$Content-dependent but not restricted by phrases Without introduction of too large number of parameters but still powerful With generalization capabilities -Build It Conditioned on Features, not Phrases:.""" "Features can be: Some special words or their classes in phrases Syntactic properties of phrases Surface attributes like distance of swapping Advantages of feature-based reordering: Flexibility Less parameters Generalization capabilities \|(:| : q+Feature-based Reordering"Discriminative Reordering Model proposed by Zens & Ney in NAACL 2006 Workshop on SMT We have become aware of this work when we prepare the talk Very close to our work But still different: Implemented under the IBM constraints Using different feature selection mechanism NUgSUgS ,,V"Outline"^Previous work Maximum entropy based phrase reordering System overview Experiments Conclusions *_()Reordering as Classification$Regard reordering as a problem of classification Two-class problem under ITG constraints {straight, inverted} Multi-class problem if positions are considered under the IBM constraints Our work focused on the reordering under the ITG constraintsl1Z)ZZJZ=Z1)J =W $MaxEnt-based Reordering Model (MERM)"%  MA reordering framework for BTG MERM under this framework Feature function:--TTraining for MERM"Training procedures: 3 steps Learning reordering examples Generating features ( ) from reordering examples Parameter ( ) estimation using off-the-shelf MaxEnt toolkits :$ . Reordering Example" FeatureseLexical feature: source or target boundary words Collocation feature: combinations of boundary words 2f!! AWhy Do We Use Boundary Words as Features: Information Gain Ratio BB" ]$Outline"fPrevious work Maximum entropy based phrase reordering System overview (Bruin) Experiments Conclusions Bg6" Translation Model%Built upon BTG The whole model is built in the log-linear form The score to apply lexical rules is calculated using features similar to many state-of-the-art systems The score to apply merging rules is divided into two parts The reordering model score The increment of language model score NBABA 1GDifferent Reordering Models Are Embedded in the Whole Translation ModelHH"oThe reordering framework MaxEnt-based reordering model Distance-based reordering model Flat reordering modelP2CKY-style Decoder"Core algorithm Borrowed from CKY parsing algorithm Edge pruning Histogram pruning Thresholding pruning Language model incorporation Record the leftmost & rightmost n words for each edge $ '6$ ' 6"R \g&Outline"^Previous work Maximum entropy based phrase reordering System overview Experiments Conclusions *_F  h%Experiment Design"To test MERM against various reordering models, we carried out experiments on: Bruin with MERM Bruin with monotone search Bruin with distance-based reordering model Bruin with flat reordering model Pharaoh, a distance-based state-of-the-art system (Koehn 2004)4OOj'Systems Settings"3Small Scale Experiments"LNIST MT 05 Training data: FBIS (7.06M + 9.15M) Language model: 3-gram trained on 81M English words (most from UN corpus) using SRILM toolkit Development set: 580 sentences length of at most 50 Chinese characters from NIST MT 02 IWSLT 04 Small data track 20k sentences for training of TM and LM 506 sentences as the development set N  _  _ 8 MERM Training"m(Results on Small Scale Data"AScaling to Large Bitexts"Just used lexical features for MaxEnt reordering model Training data 2.4M sentence pairs (68.1M Chinese words and 73.8M English words) Two 3-gram language models One was trained on the English side The other was trained on the Xinhua portion of the Gigaword corpus with 181.1M words Used simple rules to translate number, time expressions and Chinese person names BLEU score: 0.22 0.291 EZBZZyZjZZZEBy  b>MResults Comparison" n)Outline"^Previous work Maximum entropy based phrase reordering System overview Experiments Conclusions "_R @ Comparisons "B Conclusions "MaxEnt-based reordering model is Feature-based Content-dependent Capable of generalization Trained discriminatively Easy to be integrated into systems under the IBM constraints :!!p* Future Work "More features Syntactic features Global features of the whole sentences & Other language pairs English-Arabic Chinese-MongolianN<!<! C Thank you!   7Training "Run GIZA++ in both directions Use grow-diag-final refinement rules Maximum phrase length: 7 words on the Chinese side Length ratio: max(|s|, |t|)/min(|s|, |t|) <= 3>'Y  |,&Language Model Incorporation (further)''"The edge spans only part of the source sentence The history of LM is not available the language model score has to be approximated by computing the score for the generated target words alone Combination of two neighbor edges only need to compute the increment of the LM score: v0"40"4 OTree" - Related Definitions" U/The Algorithm of Extracting Reordering ExamplesZFor each sentence pair do Extract bilingual phrases Update the links for the four corners of each extracted phrases For each corner do If it has a STRAIGHT link with phrase a and b Extract the pattern: <a; b> STRAIGHT If it has a INVERT link with phrase a and b Extract the pattern: <a; b> INVERT[.',%[.  , /!#$%'(, / 0 4 56>?GHIJRSX^ab c!i"o#r$s%t&u'v(~) K0 80(  8x 8 c $z   x 8 c $z  H 8 0޽h ? 3f3f___PPT10i."+D=' = @B + K0 `$(  r  S PT,M   r  S ȡ  H  0޽h ? 3f3f___PPT10i.k+D=' = @B +rvA)? ~Root EntrydO)4!PicturesfCurrent User,SummaryInformation(!TQL`      a"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKMNOPRSTUVWXYZ[^_|bcdefghijklmnopqrstuvwxyz{}~ 0z[ 0@DWingdingsRoman0z[ 0PDFranklin Gothic Mediumz[ 0"`DVerdana Gothic Mediumz[ 0"pDGungsuhChethic Mediumz[ 01DNSeeOuhChethic Mediumz[ 0DArial Blackhic Mediumz[ 0"DComic Sans MSc Mediumz[ 0B A .  @n?" dd@  @@``    IF   D   r !!"#a$%& ) ,  /01234~67>GCDEFGHIL   X[\]^_ ab  hijkl mnop1 tBvwxyz{|}~ 2$^K)V"|b$XڼV&ռ,wx2$9_= *f,2 2$b1;KNnQf b$ÏY ~&RՃT e 2$~U6U~g2$;ɿ]V$2$O18 { 2$NG^Rf!]$$$$2$); KpDz*~-/e2$ܱ&SaFu 2$vP xXia "$b$U׷2?`v,j#b$q;@aZ&hN|$2$loof5]Cj&$2$K;15HXI'2$:Źg~.EhWAJ) 0AA ffffff@ۉ8ʚ;ʚ;g4BdBd z[ 0pppp@ <4ddddL 0~ 0___PPT10 ppH___PPT9*"n_4ln,|PNG  IHDR +tsRGB PLTEff3fQ} cmPPJCmp0712cOtRNS@fIDATc`PA-Q-0 yx`YsIENDB`[nQy  a*lD!@PNG  IHDR exsRGBNPLTEkc{絔έֽεƭƥƽ{s cmPPJCmp0712x~tRNS AyIDATMI0{d{1@Gs @c3|bXֻ$镰3дY ;6TJ~UCo@{} P{4$]$gc>/13"+^ZCLKs}XmIENDB`?Z-FDevi Xiong et al. ICT, CAS, BeijingO  =13QMaximum Entropy Based Phrase Reordering Model for Statistical Machine TranslationBR&,",&,+",Deyi Xiong, Qun Liu and Shouxun Lin Multilingual Interaction Technology & Evaluation Lab Institute of Computing Technology Chinese Academy of Sciences {dyxiong, liuqun, sxlin} at ict dot ac dot cn Homepage: http://mtgroup.ict.ac.cn/~devi/ """" "s".g  *g   y Outline"^Previous work Maximum entropy based phrase reordering System overview Experiments Conclusions  Previous WorkContent-independent reordering models E.g. distance-based or flat reordering models Learn nothing for reordering from real-world bitexts Content-dependent reordering models Lexicalized reordering models [Tillmann, 04; Och et. al. 04; & ] Totally dependent on bilingual phrases With a large number of parameters to estimate Without generalization capabilities&.5%@y&.5%  @&R>E+ %Can We Build Such a Reordering Model?,& $$$Content-dependent but not restricted by phrases Without introduction of too large number of parameters but still powerful With generalization capabilities -Build It Conditioned on Features, not Phrases:.""" "Features can be: Some special words or their classes in phrases Syntactic properties of phrases Surface attributes like distance of swapping Advantages of feature-based reordering: Flexibility Less parameters Generalization capabilities \|(:| : q+Feature-based Reordering"Discriminative Reordering Model proposed by Zens & Ney in NAACL 2006 Workshop on SMT We have become aware of this work when we prepare the talk Very close to our work But still different: Implemented under the IBM constraints Using different feature selection mechanism NUgSUgS ,,V"Outline"^Previous work Maximum entropy based phrase reordering System overview Experiments Conclusions *_()Reordering as Classification$Regard reordering as a problem of classification Two-class problem under the ITG constraints {straight, inverted} Multi-class problem if positions are considered under the IBM constraints Our work focused on the reordering under the ITG constraintsl1Z-ZZJZ=Z1-J =W $MaxEnt-based Reordering Model (MERM)"%  MA reordering framework for BTG MERM under this framework Feature function:--TTraining for MERM"Training procedures: 3 steps Learning reordering examples Generating features ( ) from reordering examples Parameter ( ) estimation using off-the-shelf MaxEnt toolkits :$ . Reordering Example" FeatureseLexical feature: source or target boundary words Collocation feature: combinations of boundary words 2f!! AWhy Do We Use Boundary Words as Features: Information Gain Ratio BB" ]$Outline"fPrevious work Maximum entropy based phrase reordering System overview (Bruin) Experiments Conclusions Bg6" Translation Model%Built upon BTG The whole model is built in the log-linear form The score to apply lexical rules is calculated using features similar to many state-of-the-art systems The score to apply merging rules is divided into two parts The reordering model score The increment of language model score NBABA 1GDifferent Reordering Models Are Embedded in the Whole Translation ModelHH"oThe reordering framework MaxEnt-based reordering model Distance-based reordering model Flat reordering modelP2CKY-style Decoder"Core algorithm Borrowed from CKY parsing algorithm Edge pruning Histogram pruning Thresholding pruning Language model incorporation Record the leftmost & rightmost n words for each edge $ '6$ ' 6"R \g&Outline"^Previous work Maximum entropy based phrase reordering System overview Experiments Conclusions *_F  h%Experiment Design"To test MERM against various reordering models, we carried out experiments on: Bruin with MERM Bruin with monotone search Bruin with distance-based reordering model Bruin with flat reordering model Pharaoh, a distance-based state-of-the-art system (Koehn 2004)4OOj'Systems Settings"3Small Scale Experiments"LNIST MT 05 Training data: FBIS (7.06M + 9.15M) Language model: 3-gram trained on 81M English words (most from UN corpus) using SRILM toolkit Development set: 580 sentences length of at most 50 Chinese characters from NIST MT 02 IWSLT 04 Small data track 20k sentences for training of TM and LM 506 sentences as the development set N  _  _ 8 MERM Training"m(Results on Small Scale Data"AScaling to Large Bitexts"Just used lexical features for MaxEnt reordering model Training data 2.4M sentence pairs (68.1M Chinese words and 73.8M English words) Two 3-gram language models One was trained on the English side The other was trained on the Xinhua portion of the Gigaword corpus with 181.1M words Used simple rules to translate number, time expressions and Chinese person names BLEU score: 0.22 0.291 EZBZZyZjZZZEBy  bfFMResults Comparison" n)Outline"^Previous work Maximum entropy based phrase reordering System overview Experiments Conclusions "_R @ Comparisons "B Conclusions "MaxEnt-based reordering model is Feature-based Content-dependent Capable of generalization Trained discriminatively Easy to be integrated into systems under the IBM constraints :!!p* Future Work "More features Syntactic features Global features of the whole sentences & Other language pairs English-Arabic Chinese-MongolianN<!<! C Thank you!   7Training "Run GIZA++ in both directions Use grow-diag-final refinement rules Maximum phrase length: 7 words on the Chinese side Length ratio: max(|s|, |t|)/min(|s|, |t|) <= 3>'Y  |,&Language Model Incorporation (further)''"The edge spans only part of the source sentence The history of LM is not available the language model score has to be approximated by computing the score for the generated target words alone Combination of two neighbor edges only need to compute the increment of the LM score: v0"40"4 OTree" - Related Definitions" U/The Algorithm of Extracting Reordering ExamplesZFor each sentence pair do Extract bilingual phrases Update the links for the four corners of each extracted phrases For each corner do If it has a STRAIGHT link with phrase a and b Extract the pattern: <a; b> STRAIGHT If it has a INVERT link with phrase a and b Extract the pattern: <a; b> INVERT[.',%[.  , /!#$%'(, / 0 4 56>?GHIJRSX^ab c!i"o#r$s%t&u'v(~)  K0   8@ (  8x 8 c $hy.  . x 8 c $target(2C  8 6c I  >source(2C  8 6m s tZ  Fstraight" (2 e 8 6,w s Z  Finverted" (2 e  H 8 0޽h ? 3f3f___PPT10i."+D=' = @B + K0 `$(  r  S hQT,M  Q r  S Q Q H  0޽h ? 3f3f___PPT10i.k+D=' = @B +r+A8? z;~_ S(   pYlQ_ Equation.30 Microsoft lQ_ 3.0ZlQ_ Equation.30 Microsoft lQ_ 3.0[lQ_ Equation.30 Microsoft lQ_ 3.0\lQ_ Equation.30 Microsoft lQ_ 3.0_lQ_ Equation.30 Microsoft lQ_ 3.0`lQ_ Equation.30 Microsoft lQ_ 3.0dlQ_ Equation.30 Microsoft lQ_ 3.0elQ_ Equation.30 Microsoft lQ_ 3.0'klQ_ Equation.30 Microsoft lQ_ 3.0(llQ_ Equation.30 Microsoft lQ_ 3.0IwlQ_ Equation.30 Microsoft lQ_ 3.0JxlQ_ Equation.30 Microsoft lQ_ 3.0KylQ_ Equation.30 Microsoft lQ_ 3.0LzlQ_ Equation.30 Microsoft lQ_ 3.0O{lQ_ Equation.30 Microsoft lQ_ 3.0P}lQ_ Equation.30 Microsoft lQ_ 3.0/ 0DDArialSans~0z[ 0D[SOalSans~0z[ 0 DBook Antiqua~0z[ 00DTimes New Roman0z[ 0@DWingdingsRoman0z[ 0PDFranklin Gothic Mediumz[ 0"`DVerdana Gothic Mediumz[ 0"pDGungsuhChethic Mediumz[ 01DNSeeOuhChethic Mediumz[ 0DArial Blackhic Mediumz[ 0"DComic Sans MSc Mediumz[ 0B A .  @n?" dd@  @@``    IF   D   r !!"#a$%& ) ,  /01234~67>GCDEFGHIL   X[\]^_ ab  hijkl mnop1 tBvwxyz{|}~ 2$^K)V"|b$XڼV&ռ,wx2$9_= *f,2 2$b1;KNnQf b$ÏY ~&RՃT e 2$~U6U~g2$;ɿ]V$2$O18 { 2$NG^Rf!]$$$$2$); KpDz*~-/e2$ܱ&SaFu 2$vP xXia "$b$U׷2?`v,j#b$q;@aZ&hN|$2$loof5]Cj&$2$K;15HXI'2$:Źg~.EhWAJ) 0AA ffffff@ۉ8ʚ;ʚ;g4BdBd z[ 0pppp@ <4ddddL 0~ 0___PPT10 ppH___PPT9*"n_4ln,|PNG  IHDR +tsRGB PLTEff3fQ} cmPPJCmp0712cOtRNS@fIDATc`PA-Q-0 yx`YsIENDB`[nQy  a*lD!@PNG  IHDR exsRGBNPLTEkc{絔έֽεƭƥƽ{s cmPPJCmp0712x~tRNS AyIDATMI0{d{1@Gs @c3|bXֻ$镰3дY ;6TJ~UCo@{} P{4$]$gc>/13"+^ZCLKs}XmIENDB`?Z-FDevi Xiong et al. ICT, CAS, BeijingO  =/3QMaximum Entropy Based Phrase Reordering Model for Statistical Machine TranslationBR&,",&,+",Deyi Xiong, Qun Liu and Shouxun Lin Multilingual Interaction Technology & Evaluation Lab Institute of Computing Technology Chinese Academy of Sciences {dyxiong, liuqun, sxlin} at ict dot ac dot cn Homepage: http://mtgroup.ict.ac.cn/~devi/ """" "s".g  *g   y Outline"^Previous work Maximum entropy based phrase reordering System overview Experiments Conclusions  Previous WorkContent-independent reordering models E.g. distance-based or flat reordering models Learn nothing for reordering from real-world bitexts Content-dependent reordering models Lexicalized reordering models [Tillmann, 04; Och et. al. 04; & ] Totally dependent on bilingual phrases With a large number of parameters to estimate Without generalization capabilities&.5%@y&.5%  @&R>E+ %Can We Build Such a Reordering Model?,& $$$Content-dependent but not restricted by phrases Without introduction of too large number of parameters but still powerful With generalization capabilities -Build It Conditioned on Features, not Phrases:.""" "Features can be: Some special words or their classes in phrases Syntactic properties of phrases Surface attributes like distance of swapping Advantages of feature-based reordering: Flexibility Less parameters Generalization capabilities \|(:| : q+Feature-based Reordering"Discriminative Reordering Model proposed by Zens & Ney in NAACL 2006 Workshop on SMT We have become aware of this work when we prepa ʾĸģǶ OLE  õƬ#_EMnonenoneroupiongre the talk Very close to our work But still different: Implemented under the IBM constraints Using different feature selection mechanism NUgSUgS ,,V"Outline"^Previous work Maximum entropy based phrase reordering System overview Experiments Conclusions *_()Reordering as Classification$Regard reordering as a problem of classification Two-class problem under the ITG constraints {straight, inverted} Multi-class problem if positions are considered under the IBM constraints Our work focused on the reordering under the ITG constraintsl1Z-ZZJZ=Z1-J =W $MaxEnt-based Reordering Model (MERM)"%  MA reordering framework for BTG MERM under this framework Feature function:--TTraining for MERM"Training procedures: 3 steps Learning reordering examples Generating features ( ) from reordering examples Parameter ( ) estimation using off-the-shelf MaxEnt toolkits :$ . Reordering Example" FeatureseLexical feature: source or target boundary words Collocation feature: combinations of boundary words 2f!! AWhy Do We Use Boundary Words as Features: Information Gain Ratio BB" ]$Outline"fPrevious work Maximum entropy based phrase reordering System overview (Bruin) Experiments Conclusions Bg6" Translation Model%Built upon BTG The whole model is built in the log-linear form The score to apply lexical rules is calculated using features similar to many state-of-the-art systems The score to apply merging rules is divided into two parts The reordering model score The increment of language model score NBABA 1GDifferent Reordering Models Are Embedded in the Whole Translation ModelHH"oThe reordering framework MaxEnt-based reordering model Distance-based reordering model Flat reordering modelP2CKY-style Decoder"Core algorithm Borrowed from CKY parsing algorithm Edge pruning Histogram pruning Thresholding pruning Language model incorporation Record the leftmost & rightmost n words for each edge $ '6$ ' 6"R \g&Outline"^Previous work Maximum entropy based phrase reordering System overview Experiments Conclusions *_F  h%Experiment Design"To test MERM against various reordering models, we carried out experiments on: Bruin with MERM Bruin with monotone search Bruin with distance-based reordering model Bruin with flat reordering model Pharaoh, a distance-based state-of-the-art system (Koehn 2004)4OOj'Systems Settings"3Small Scale Experiments"LNIST MT 05 Training data: FBIS (7.06M + 9.15M) Language model: 3-gram trained on 81M English words (most from UN corpus) using SRILM toolkit Development set: 580 sentences length of at most 50 Chinese characters from NIST MT 02 IWSLT 04 Small data track 20k sentences for training of TM and LM 506 sentences as the development set N  _  _ 8 MERM Training"m(Results on Small Scale Data"AScaling to Large Bitexts" Just used lexical features for MaxEnt reordering model Training data 2.4M sentence pairs (68.1M Chinese words and 73.8M English words) Two 3-gram language models One was trained on the English side The other was trained on the Xinhua portion of the Gigaword corpus with 181.1M words Used simple rules to translate number, time expressions and Chinese person names BLEU score: 0.22 0.29 EZBZZyZiZZZEBy  bfFMResults Comparison" n)Outline"^Previous work Maximum entropy based phrase reordering System overview Experiments Conclusions "_R @ Comparisons "B Conclusions "MaxEnt-based reordering model is Feature-based Content-dependent Capable of generalization Trained discriminatively Easy to be integrated into systems under the IBM constraints :!!p* Future Work "More features Syntactic features Global features of the whole sentences & Other language pairs English-Arabic Chinese-MongolianN<!<! C Thank you!   7Training "Run GIZA++ in both directions Use grow-diag-final refinement rules Maximum phrase length: 7 words on the Chinese side Length ratio: max(|s|, |t|)/min(|s|, |t|) <= 3>'Y  |,&Language Model Incorporation (further)''"The edge spans only part of the source sentence The history of LM is not available the language model score has to be approximated by computing the score for the generated target words alone Combination of two neighbor edges only need to compute the increment of the LM score: v0"40"4 OTree" - Related Definitions" U/The Algorithm of Extracting Reordering ExamplesZFor each sentence pair do Extract bilingual phrases Update the links for the four corners of each extracted phrases For each corner do If it has a STRAIGHT link with phrase a and b Extract the pattern: <a; b> STRAIGHT If it has a INVERT link with phrase a and b Extract the pattern: <a; b> INVERT[.',%[.  , /!#$%'(, / 0 4 56>?GHIJRSX^ab c!i"o#r$s%t&u'v(~) K0 `$(  r  S hQT,M  Q r  S Q Q H  0޽h ? 3f3f___PPT10i.k+D=' = @B +r;AԎ? ;q~_ S(   pYlQ_ Equation.30 Microsoft lQ_ 3.0ZlQ_ Equation.30 Microsoft lQ_ 3.0[lQ_ Equation.30 Microsoft lQ_ 3.0\lQ_ Equation.30 Microsoft lQ_ 3.0_lQ_ Equation.30 Microsoft lQ_ 3.0`lQ_ Equation.30 Microsoft lQ_ 3.0dlQ_ Equation.30 Microsoft lQ_ 3.0elQ_ Equation.30 Microsoft lQ_ 3.0'klQ_ Equation.30 Microsoft lQ_ 3.0(llQ_ Equation.30 Microsoft lQ_ 3.0IwlQ_ Equation.30 Microsoft lQ_ 3.0JxlQ_ Equation.30 Microsoft lQ_ 3.0KylQ_ Equation.30 Microsoft lQ_ 3.0LzlQ_ Equation.30 Microsoft lQ_ 3.0O{lQ_ Equation.30 Microsoft lQ_ 3.0P}lQ_ Equation.30 Microsoft lQ_ 3.0/ 0DDArialSans~0z[ 0D[SOalSans~0z[ 0 DBook Antiqua~0z[ 00DTimes New Roman0z[ 0@DWingdingsRoman0z[ 0PDFranklin Gothic Mediumz[ 0"`DVerdana Gothic Mediumz[ 0"pDGungsuhChethic Mediumz[ 01DNSeeOuhChethic Mediumz[ 0DArial Blackhic Mediumz[ 0"DComic Sans MSc Mediumz[ 0B A .  @n?" dd@  @@``    IF   D   r !!"#a$%& ) ,  /01234~67>GCDEFGHIL   X[\]^_ ab  hijkl mnop1 tBvwxyz{|}~ 2$^K)V"|b$XڼV&ռ,wx2$9_= *f,2 2$b1;KNnQf b$ÏY ~&RՃT e 2$~U6U~g2$;ɿ]V$2$O18 { 2$NG^Rf!]$$$$2$); KpDz*~-/e2$ܱ&SaFu 2$vP xXia "$b$U׷2?`v,j#b$q;@aZ&hN|$2$loof5]Cj&$2$K;15HXI'2$:Źg~.EhWAJ) 0AA ffffff@ۉ8ʚ;ʚ;g4BdBd z[ 0pppp@ <4ddddL 0~ 0___PPT10 ppH___PPT9*"n_4ln,|PNG  IHDR +tsRGB PLTEff3fQ} cmPPJCmp0712cOtRNS@fIDATc`PA-Q-0 yx`YsIENDB`[nQy  a*lD!@PNG  IHDR exsRGBNPLTEkc{絔έֽεƭƥƽ{s cmPPJCmp0712x~tRNS AyIDATMI0{d{1@Gs @c3|bXֻ$镰3дY ;6TJ~UCo@{} P{4$]$gc>/13"+^ZCLKs}XmIENDB`?Z-FDevi Xiong et al. ICT, CAS, BeijingO  =/3QMaximum Entropy Based Phrase Reordering Model for Statistical Machine TranslationBR&,",&,+",Deyi Xiong, Qun Liu and Shouxun Lin Multilingual Interaction Technology & Evaluation Lab Institute of Computing Technology Chinese Academy of Sciences {dyxiong, liuqun, sxlin} at ict dot ac dot cn Homepage: http://mtgroup.ict.ac.cn/~devi/ """" "s".g  *g   y Outline"^Previous work Maximum entropy based phrase reordering System overview Experiments Conclusions  Previous WorkContent-independent reordering models E.g. distance-based or flat reordering models Learn nothing for reordering from real-world bitexts Content-dependent reordering models Lexicalized reordering models [Tillmann, 04; Och et. al. 04; & ] Totally dependent on bilingual phrases With a large number of parameters to estimate Without generalization capabilities&.5%@y&.5%  @&R>E+ %Can We Build Such a Reordering Model?,& $$$Content-dependent but not restricted by phrases Without introduction of too large number of parameters but still powerful With generalization capabilities -Build It Conditioned on Features, not Phrases:.""" "Features can be: Some special words or their classes in phrases Syntactic properties of phrases Surface attributes like distance of swapping Advantages of feature-based reordering: Flexibility Less parameters Generalization capabilities \|(:| : q+Feature-based Reordering"Discriminative Reordering Model proposed by Zens & Ney in NAACL 2006 Workshop on SMT We have become aware of this work when we prepare the talk Very close to our work But still different: Implemented under the IBM constraints Using different feature selection mechanism NUgSUgS ,,V"Outline"^Previous work Maximum entropy based phrase reordering System overview Experiments Conclusions *_()Reordering as Classification$Regard reordering as a problem of classification Two-class problem under the ITG constraints {straight, inverted} Multi-class problem if positions are considered under the IBM constraints Our work focused on the reordering under the ITG constraintsl1Z-ZZJZ=Z1-J =W $MaxEnt-based Reordering Model (MERM)"%  MA reordering framework for BTG MERM under this framework Feature function:--TTraining for MERM"Training procedures: 3 steps Learning reordering examples Generating features ( ) from reordering examples Parameter ( ) estimation using off-the-shelf MaxEnt toolkits :$ . Reordering Example" FeatureseLexical feature: source or target boundary words Collocation feature: combinations of boundary words 2f!! AWhy Do We Use Boundary Words as Features: Information Gain Ratio BB" ]$Outline"fPrevious work Maximum entropy based phrase reordering System overview (Bruin) Experiments Conclusions Bg6" Translation Model%Built upon BTG The whole model is built in the log-linear form The score to apply lexical rules is calculated using features similar to many state-of-the-art systems The score to apply merging rules is divided into two parts The reordering model score The increment of language model score NBABA 1GDifferent Reordering Models Are Embedded in the Whole Translation ModelHH"oThe reordering framework MaxEnt-based reordering model Distance-based reordering model Flat reordering modelP2CKY-style Decoder"Core algorithm Borrowed from CKY parsing algorithm Edge pruning Histogram pruning Thresholding pruning Language model incorporation Record the leftmost & rightmost n words for each edge $ '6$ ' 6"R \g&Outline"^Previous work Maximum entropy based phrase reordering System overview Experiments Conclusions *_F  h%Experiment Design"To test MERM against various reordering models, we carried out experiments on: Bruin with MERM Bruin with monotone search Bruin with distance-based reordering model Bruin with flat reordering model Pharaoh, a distance-based state-of-the-art system (Koehn 2004)4OOj'Systems Settings"3Small Scale Experiments"LNIST MT 05 Training data: FBIS (7.06M + 9.15M) Language model: 3-gram trained on 81M English words (most from UN corpus) using SRILM toolkit Development set: 580 sentences length of at most 50 Chinese characters from NIST MT 02 IWSLT 04 Small data track 20k sentences for training of TM and LM 506 sentences as the development set N  _  _ 8 MERM Training"m(Results on Small Scale Data"AScaling to Large Bitexts" Just used lexical features for MaxEnt reordering model Training data 2.4M sentence pairs (68.1M Chinese words and 73.8M English words) Two 3-gram language models One was trained on the English side The other was trained on the Xinhua portion of the Gigaword corpus with 181.1M words Used simple rules to translate number, time expressions and Chinese person names BLEU score: 0.22 0.29 EZBZZyZiZZZEBy  bfFMResults Comparison" n)Outline"^Previous work Maximum entropy based phrase reordering System overview Experiments Conclusions "_R @ Comparisons "B Conclusions "MaxEnt-based reordering model is Feature-based Content-dependent Capable of generalization Trained discriminatively Easy to be integrated into systems under the IBM constraints :!!p* Future Work "More features Syntactic features Global features of the whole sentences & Other language pairs English-Arabic Chinese-MongolianN<!<! C Thank you!   7Training "Run GIZA++ in both directions Use grow-diag-final refinement rules Maximum phrase length: 7 words on the Chinese side Length ratio: max(|s|, |t|)/min(|s|, |t|) <= 3>'Y  |,&Language Model Incorporation (further)''"The edge spans only part of the source sentence The history of LM is not available the language model score has to be approximated by computing the score for the generated target words alone Combination of two neighbor edges only need to compute the increment of the LM score: v0"40"4 OTree" - Related Definitions" U/The Algorithm of Extracting Reordering ExamplesZFor each sentence pair do Extract bilingual phrases Update the links for the four corners of each extracted phrases For each corner do If it has a STRAIGHT link with phrase a and b Extract the pattern: <a; b> STRAIGHT If it has a INVERT link with phrase a and b Extract the pattern: <a; b> INVERT[.',%[.  , /!#$%'(, / 0 4 56>?GHIJRSX^ab c!i"o#r$s%t&u'v(~)r? ~_ S(   YlQ_ Equation.30 Microsoft lQ_ 3.0Z   " ?   3!1AQa"q2B#$Rb34rC%Scs5&DTdE£t6UeuF'Vfv7GWgw5!1AQaq"2B#R3$brCScs4%&5DTdEU6teuFVfv'7GWgw ?TI%)$IJ^i3b;هQK5tջ-xoWulΣ2ܛFc֬򑹙~dgFx.?yLUW_s1}bkqK.?yZu~iV][LYa-?YN?ԻnOyiY 4~E82zM5~kkU|ЎC[:p+Yy-:馐Ue~KOVG.mt8bZ}G]{26HAywR'!ywR$')KOS$xo8NYp($6jHG[?Ed.V`n?8hJdfYpTI%)$IN>zoլۘvk= O}k^;c{5Gg`tC,h9{XݏwJ{կ̮[sXG:T XG-k /!_Wo`;_Zs֠szҺ'ΓЩ5SVϴ[kF=an唥(ߤTI%)$o.+y\"$Ҟ^s0~gr:]z6b ӊO}̲y5mps:%Yvkۺ?s\{^z7cfv}h\.tbgw-o2Y;?[]ܸ:J"Lqw@ī3ݏswWcx#kcQ",I10'sߩ5X&+qk|i=5QS$_t~G'YA=I.WgdGJe=RK }v3>ҳN@aSsa]mM>J~~siɬ (#k "fw'ixS_ $ a߬}b_]Oۅ%ׁ^;kzŗNu2kCO%gU/< -@$UTI%)pKl:Xo`w֗tP-3^&J~bS򱼗$J_F_ZOӕ9>э>7~Ov\fa۱no|s~}o^}hL:{+jA8;3ԳPg8]V.a~Tںmh䵣J?E fvvxxٸX۱h}v4 *hu6k鹎ڜYeokvc{\cuUu4 hݚ[VWeOuv4ױ4s\\kH)+N'R#Z2K[@?iˠe3'8-[Wф%YT#_W*nU:k'Ut_d?GP˼?EnT9S;:dwvNk1J!C*CV[-k-s?j?닋oSӕ]T1u`cS5l40ԭ YktdKa$UW?TI%,f4pGU>ίc{\^}?{||2Nj@;55孟?iS_Zl&vxjk[?ƦgMw%E\#}WuֱEXK3 jם?}5ФR26u+. bo%0M.R@SU֚쬖9k蹫_wHꬴ>x5W{s?u_^W5z/F!}krZ[1-gQ]S&TF{KbS%wګk m~-X}1YvVV[:ԇu,ӡ-дOU{?o?̞)\z̡\>1`ʲvV;SP_Uu<}+>/^O{G³}h}A~vC^{pn6SpYﶡknvR I(?TAŷ/*N= /p֎JJL%ԿAv*Is}Kj _[SK [$p? J;fוslsk7{{R=dI)B۪sUUִj=}Zkj{p#p$no,76/ۮe3mJ?ooF lcfն4sY1RF^gGu]oT7>瓹et. ~Ll[?uz?Z-0Tӓc~Ӧc>:3@v$#6q[oj\WgT7]hkGU[kKl}eʜI5s\\sܦZ_c/T=M?9oBLtu,qmg̕_6ms>]ߤ71qu֑N~uU1-:Eo-1# 略]0fgsV*?aCYF DC&cWܽ֋Y~ۍC3%Ww3+p=6NTV?ƞyu1FeZ?_vVcEfsGizWo5$dzI$UI$SN*&c hm@mlf)_%'c =*ۏDdZ'PǧT^%f :nA>گ<ǜzcld'Q: nK,"ycr/`̹kK}u@sVwn?dZ H> ~-o?,AӪmX/̖hwm͖ڛ,5{p#6Iz1~Y߬8S-f(|m PWo=e}]=8t׵iv0}->G9tL5qmeCҡ} 76{- N9{~gPFG$x1Og?bQ۫ƵԶvŇcݴVROV3?Eo}d?W:WCbTLH^V:`}{}N}]Cյ',fɊY=#s"Dqz\ǹ1y cEKv[Z>ՂFEShiq-krۯetj{j`-p;}Wfz~`p,u8W+w %VIg/2z11bϤzwNΑhǭ`.yNn?IuRXxl,k-nk]WeJR q|fËe#zc\~Tin=[=8UҲ?2MmZܸL}C)i6R={^tw{+Y\)cK˯-߱9ݒ`)?g~=>8uw^Mt73aۛSֹ{UExmT٭ZWAYM^o}O`u,k=58`6rԮI*˔I$ץ5GFSj;tcbmz00فҰqX#lZ╿ҿ>tޟM9W/{w~=p~az*ͯ5{q_Q7?X>M}>ݽK?C\w+L?/%*俅Oy(>kr3`q/ƗP~MieZmR8p]m3;iSY/>浔?Gq)9jG,!o?F~GDǂ}d',}5;??+ؼ[q1oȬU2*ÿgp/_!'O-|2^5]c3zyS'u?יS660ϧEql.A%}!]ӣk}ܱeG~x/_=|/leTNfzcw2|'lC^?1}wP\ OoNVFgMɨQvEMԴ795^Z~|׭7*||w궏3pj+dI)I$SPhotoshop 3.08BIM%8BIMHH8BIM&?8BIM x8BIM8BIM 8BIM 8BIM' 8BIMH/fflff/ff2Z5-8BIMp8BIM8BIM8BIM@@8BIM8BIMI Untitled-1nullboundsObjcRct1Top longLeftlongBtomlongRghtlongslicesVlLsObjcslicesliceIDlonggroupIDlongoriginenum ESliceOrigin autoGeneratedTypeenum ESliceTypeImg boundsObjcRct1Top longLeftlongBtomlongRghtlongurlTEXTnullTEXTMsgeTEXTaltTagTEXTcellTextIsHTMLboolcellTextTEXT horzAlignenumESliceHorzAligndefault vertAlignenumESliceVertAligndefault bgColorTypeenumESliceBGColorTypeNone topOutsetlong leftOutsetlong bottomOutsetlong rightOutsetlong8BIM( ?8BIM8BIM JFIFHH Adobe_CMAdobed            " ?   3!1AQa"q2B#$Rb34rC%Scs5&DTdE£t6UeuF'Vfv7GWgw5!1AQaq"2B#R3$brCScs4%&5DTdEU6teuFVfv'7GWgw ?TI%)$IJ^i3b;هQK5tջ-xoWulΣ2ܛFc֬򑹙~dgFx.?yLUW_s1}bkqK.?yZu~iV][LYa-?YN?ԻnOyiY 4~E82zM5~kkU|ЎC[:p+Yy-:馐Ue~KOVG.mt8bZ}G]{26HAywR'!ywR$')KOS$xo8NYp($6jHG[?Ed.V`n?8hJdfYpTI%)$IN>zoլۘvk= O}k^;c{5Gg`tC,h9{XݏwJ{կ̮[sXG:T XG-k /!_Wo`;_Zs֠szҺ'ΓЩ5SVϴ[kF=an唥(ߤTI%)$o.+y\"$Ҟ^s0~gr:]z6b ӊO}̲y5mps:%Yvkۺ?s\{^z7cfv}h\.tbgw-o2Y;?[]ܸ:J"Lqw@ī3ݏswWcx#kcQ",I10'sߩ5X&+qk|i=5QS$_t~G'YA=I.WgdGJe=RK }v3>ҳN@aSsa]mM>J~~siɬ (#k "fw'ixS_ $ a߬}b_]Oۅ%ׁ^;kzŗNu2kCO%gU/< -@$UTI%)pKl:Xo`w֗tP-3^&J~bS򱼗$J_F_ZOӕ9>э>7~Ov\fa۱no|s~}o^}hL:{+jA8;3ԳPg8]V.a~Tںmh䵣J?E fvvxxٸX۱h}v4 *hu6k鹎ڜYeokvc{\cuUu4 hݚ[VWeOuv4ױ4s\\kH)+N'R#Z2K[@?iˠe3'8-[Wф%YT#_W*nU:k'Ut_d?GP˼?EnT9S;:dwvNk1J!C*CV[-k-s?j?닋oSӕ]T1u`cS5l40ԭ YktdKa$UW?TI%,f4pGU>ίc{\^}?{||2Nj@;55孟?iS_Zl&vxjk[?ƦgMw%E\#}WuֱEXK3 jם?}5ФR26u+. bo%0M.R@SU֚쬖9k蹫_wHꬴ>x5W{s?u_^W5z/F!}krZ[1-gQ]S&TF{KbS%wګk m~-X}1YvVV[:ԇu,ӡ-дOU{?o?̞)\z̡\>1`ʲvV;SP_Uu<}+>/^O{G³}h}A~vC^{pn6SpYﶡknvR I(?TAŷ/*N= /p֎JJL%ԿAv*Is}Kj _[SK [$p? J;fוslsk7{{R=dI)B۪sUUִj=}Zkj{p#p$no,76/ۮe3mJ?ooF lcfն4sY1RF^gGu]oT7>瓹et. ~Ll[?uz?Z-0Tӓc~Ӧc>:3@v$#6q[oj\WgT7]hkGU[kKl}eʜI5s\\sܦZ_c/T=M?9oBLtu,qmg̕_6ms>]ߤ71qu֑N~uU1-:Eo-1# 略]0fgsV*?aCYF DC&cWܽ֋Y~ۍC3%Ww3+p=6NTV?ƞyu1FeZ?_vVcEfsGizWo5$dzI$UI$SN*&c hm@mlf)_%'c =*ۏDdZ'PǧT^%f :nA>گ<ǜzcld'Q: nK,"ycr/`̹kK}u@sVwn?dZ H> ~-o?,AӪmX/̖hwm͖ڛ,5{p#6Iz1~Y߬8S-f(|m PWo=e}]=8t׵iv0}->G9tL5qmeCҡ} 76{- N9{~gPFG$x1Og?bQ۫ƵԶvŇcݴVROV3?Eo}d?W:WCbTLH^V:`}{}N}]Cյ',fɊY=#s"Dqz\ǹ1y cEKv[Z>ՂFEShiq-krۯetj{j`-p;}Wfz~`p,u8W+w %VIg/2z11bϤzwNΑhǭ`.yNn?IuRXxl,k-nk]WeJR q|fËe#zc\~Tin=[=8UҲ?2MmZܸL}C)i6R={^tw{+Y\)cK˯-߱9ݒ`)?g~=>8uw^Mt73aۛSֹ{UExmT٭ZWAYM^o}O`u,k=58`6rԮI*˔I$ץ5GFSj;tcbmz00فҰqX#lZ╿ҿ>tޟM9W/{w~=p~az*ͯ5{q_Q7?X>M}>ݽK?C\w+L?/%*俅Oy(>kr3`q/ƗP~MieZmR8p]m3;iSY/>浔?Gq)9jG,!o?F~GDǂ}d',}5;??+ؼ[q1oȬU2*ÿgp/_!'O-|2^5]c3zyS'u?יS660ϧEql.A%}!]ӣk}ܱeG~x/_=|/leTNfzcw2|'lC^?1}wP\ OoNVFgMɨQvEMԴ795^Z~|׭7*||w궏3pj+dI)I$S8BIM!SAdobe PhotoshopAdobe Photoshop CS8BIMhttp://ns.adobe.com/xap/1.0/ 1 209 180 1 72/1 72/1 2 2006-07-14T09:39:38+08:00 2006-07-14T09:39:38+08:00 2006-07-14T09:39:38+08:00 Adobe Photoshop CS Windows adobe:docid:photoshop:83d09613-12d9-11db-9121-f13e618284db image/jpeg XICC_PROFILE HLinomntrRGB XYZ  1acspMSFTIEC sRGB-HP cprtP3desclwtptbkptrXYZgXYZ,bXYZ@dmndTpdmddvuedLview$lumimeas $tech0 rTRC< gTRC< bTRC< textCopyright (c) 1998 Hewlett-Packard CompanydescsRGB IEC61966-2.1sRGB IEC61966-2.1XYZ QXYZ XYZ o8XYZ bXYZ $descIEC http://www.iec.chIEC http://www.iec.chdesc.IEC 61966-2.1 Default RGB colour space - sRGB.IEC 61966-2.1 Default RGB colour space - sRGBdesc,Reference Viewing Condition in IEC61966-2.1,Reference Viewing Condition in IEC61966-2.1view_. \XYZ L VPWmeassig CRT curv #(-27;@EJOTY^chmrw| %+28>ELRY`gnu| &/8AKT]gqz !-8COZfr~ -;HUcq~ +:IXgw'7HYj{+=Oat 2FZn  % : O d y  ' = T j " 9 Q i  * C \ u & @ Z t .Id %A^z &Ca~1Om&Ed#Cc'Ij4Vx&IlAe@e Ek*Qw;c*R{Gp@j>i  A l !!H!u!!!"'"U"""# #8#f###$$M$|$$% %8%h%%%&'&W&&&''I'z''( (?(q(())8)k))**5*h**++6+i++,,9,n,,- -A-v--..L.../$/Z///050l0011J1112*2c223 3F3334+4e4455M555676r667$7`7788P8899B999:6:t::;-;k;;<' >`>>?!?a??@#@d@@A)AjAAB0BrBBC:C}CDDGDDEEUEEF"FgFFG5G{GHHKHHIIcIIJ7J}JK KSKKL*LrLMMJMMN%NnNOOIOOP'PqPQQPQQR1R|RSS_SSTBTTU(UuUVV\VVWDWWX/X}XYYiYZZVZZ[E[[\5\\]']x]^^l^__a_``W``aOaabIbbcCccd@dde=eef=ffg=ggh?hhiCiijHjjkOkklWlmm`mnnknooxop+ppq:qqrKrss]sttptu(uuv>vvwVwxxnxy*yyzFz{{c{|!||}A}~~b~#G k͂0WGrׇ;iΉ3dʋ0cʍ1fΏ6n֑?zM _ɖ4 uL$h՛BdҞ@iءG&vVǥ8nRĩ7u\ЭD-u`ֲK³8%yhYѹJº;.! zpg_XQKFAǿ=ȼ:ɹ8ʷ6˶5̵5͵6ζ7ϸ9к<Ѿ?DINU\dlvۀ܊ݖޢ)߯6DScs 2F[p(@Xr4Pm8Ww)KmAdobed@     u!"1A2# QBa$3Rqb%C&4r 5'S6DTsEF7Gc(UVWdte)8fu*9:HIJXYZghijvwxyzm!1"AQ2aqB#Rb3 $Cr4%ScD&5T6Ed' sFtUeuV7)(GWf8vgwHXhx9IYiy*:JZjz ?ߺ^׽u~{ߺ^9$H8Kfvb@U@.Iߴ S\ױxuC#GȞoRmd _WMbXReD/TҹjVk FM^[dgU`xWMc#y0U߾R{o_?f">,ȕozt.^]{~n) 6ez 0R;STH v iw&5*,XRBH $@`*qv|o{[w S pMi{{U> [7Oyf5Y&,XlqU[ 2kV^f]Y6I&s&DDqY<8YBYHF kfnnxTSR1S@sN9#|E~D? G%ZK-{>Ov?DWE>nd[_n*_?^{?ʷTm~A eϕo啕zu%*Ss)R/K>U߾R{o_?׾#;,|}MK}GvY/V~Jר?`7^_7?/Pnd[_n*_?^{?ʷTm~A 2:w7[W35cF#[yWzgJO Vϱ%ܔ""_G tM>6pO3l=)2~z|4ߺ^׽u~{ߺ^t6ݍG\(FSdu+).ϑ6N*V5xHd1}$LO*CުyI H*⸩uHm}x"F+,jMQ=P(Q5$]^!A,@DoASíM)/e_9vgG]g6%`o[U[*)HXyĖQށ#CO ~Ъc**XmsRW~#|dr?ݖsl/ػxBU|G_A*/>ޞ H|] CE*SQL^FP9P_icmf3J~#PW\T1-gx!g5{ʄ-F}/9{v;"Hk#IA_0O „bԄc''A׽u~{ߺ^׽u~{ߺ^׽u߿u:7dFψ>dikT̓(t٘ڵuxg 9J=T#ɣJ>Ր[z1`ļ2ԟͰ?6?>ߺ^׽u~{ߺ]_ߺZ¡AZOŌUx(Ry*>BXI5nᐫsȷ%يA G[t5*eXS e<+ nbէhPȺzdt>}{\h)|/W}Y-QM4 w]^V4?{7uJ (YC=}N)O=~Zk!:kRUTZB[s Hb,//??Y^ȋ_}i_o]sqbbL-W_E?TOWX"k^/xwŰص&4E ZIeZP[cAnRI}?=Hbǟ ӏG<:_>mBoKh)_[n2PRЮ͢$>k#p^>ӑvqrǶd >$EjTrHG[`"O({zI={ZO(}ׯi>kOi%Tz'i?^?է?Q״C׵Wߪ=zzVPG^}^֟J_~OZC+*+ר}:p~ʾ]juֵQkU܎,Vzҝo Uꯀ][FEv)*Qx Ѥzm;vx)Ԣsn]vddVVj Ы C@4|;&?W?OpƟ:ߺ^׽u~{ߺ\I}^/|o+5_jn'cնT yI%yʻ(:@W҇Ėz('TeuP}m+^x,otf;kkrr |^ o`1չg'W 㡟!_YS!#a$45#Uf$P(S@$ g ?/N_뽣(ckdNq4p&54[3S&;e ;$2_pG9ӷ6w ƾvҫBfRNFu(&+ЊaM2^1?! v^ؘNͅzamDX1tؼl Ujd2uE]CUS ,䓍;on;޾51P(Z*  S 1[§''ԓSД>G컧zߺXJ aqb.=uk+o#4$$'_aWi$ݢ,Ēy$r9;s5bjI OM3^59>ycVu g? ~>ׯz\ny~z51 ^q[noUˣ7zin?ͿQWY./0߿饸_߻6E^ g? ~>ׯ~\ny~z51 ^q[noUˣ7zin?ͿQWY./0߿饸_߻6E^#lౙ,[NJ V#Wu:j,~>ZVzxYܟ=ۉZi*"S8nܪ }|{sq{''uum ;'txq;wUghm|.6OOqyk6ֲOOId@CZWc$Ӡ 23+$SAp.??='L^q1v=g7 F)_K5S瞠,#ҠG3s}wښE"@5 X9m%Zm#QU6V]q[s6fv0c0<6:%H॥@UPqs=%܌K3}OFh*"*=ߺ^׽u~{ߺE?G?Bܕ1uY i+&»{bRnU, dsb~KWyddMVLQZ @5O)_Nm'|ah>ӁZ S?,~~iw.7\tEkɞâvcaσ/ؙ1calكl\~2)C+]Aщ B FAۋƴ3Jbx$uOs_.)jڵt?k{|G 0* CvHZ dpTIR8s8Es j" F5iXRBcF  ,k Sٚq'ч^׽u~{ߺ^׽u~{ߺ^׽u~{ߺ^W:>??,r^t:%)SvK:Pթ_ܕ&מvXe&*OnkIy迷fi- E0[&z/ۛ_z;^=(۝Q i\t LoC@upƬvOo dLKHc+6J%AU qSr>? u~ߺ^׽u~z׺ד|ڿzpu>hW:zM8ۿ |pIW[QUP:5Dyn]r~eMW3EirIDe@t hJRЅ @<U * |@?_.:+g̭ Nƪ.ڊ.*݅6#4{{1ђ?Oy)sS4E#˛,oW/tZR:oG` !jEIYCuoM# < { ϏJzߺ^׽u~{ߺ^׽u~{ߺ^׽u~{ߺ^֟?nZƏ8ы]裔|}*}1K .z@v+:5['}L[nȃT,LJQO5v" Q*AO[M7%>+gN΍ٕj|v@} _Į=EɰiR35f`GD . px(?:W*G_]^׺ߺ^׽u~q<{|3_o15y:荼Ɋ:97!HrEOyV'%Qȥg_piJFFѠ[z5V:oTy_m_q/쾷;sC펨m>ڦLJݸdGe7FxYiʛO72m[dKG"dJSĎ %I*YbMgy-X~ ?TOgM|齷!cmlmTtB]1 ,a"I2ѲOO,RG+ɴSђ@6 UI@x4r*H{iw "hN8xz2?_a~{ߺ^{{^׺u{{^׺{׮={\{^?_~?g^ڻ _A^oooigK@vUB6*{Q2̀cV[nsǑ6` V]4AEp@:y, <&ۇ zPQA[&.;zPnN sM) V;hOuoR[X[H_vwҖ |`)ACp2~BheE7Rd[khث+A U:Gli?l\)/sO@7o޹?S?L1[q{͙Ҙ'.e={li?~wS/ _VGnsf(I˿{8bz?z?^rM&(? O~yw|ڮщDkpI̜˛eչiE:ƋcVJ ҴۤWo3#R̊r%kbГJ[Y%KczM3,VS1nJަ?Ur9<-yݼ^eIH<ƭ&OžFpDg(D(WC?_T^6 atqT4u2hi㥤5c%EQPz,KۨDϰZmjc?48Z9~e?[͕yyxσe`+Whw;X.?bZZc@ν{[?O_߽iN;}w?cug^vJ*ꌍtm۴V,6E,$m%,Ȳ<26oڥڷHfUĆB)GZWPK`(:,J&ƈL3CI?E_+:kWLmșͯCKԈBK$bwIdh9yiW^h}הwi61STnh!d RAZ9dGP=1槍5$_O:- on/m_m➷sUU#夵=7iXyyY""-sTҞAsV;.c(s*ӰhUOĿGڛcm7/wndv[U`3zh2.8k1,}lʋ$r)kY"!"0A`[{^׺u[_oSc_wKIl^+\R1{4㉷[yR7 ;,4&##GtZa  n??]kznMKݛo3rRu0n&>FYH&9kGSs͒EѷQFpWH6I52I>77o][C%fLO|&1,Ŕ0+Z'S2u,[V&}Nblc9?ځȐ7&Y2){i`B E4VȑR?L6G^hskE .)5UF.^ sJÛ0avaqo; vЬI$R@E @J:o1O ,?0KQl: /=մev\4FAv.z@nX6k؉(7"{:Sq4 IM} fz%#5'"od>w}{{^׺ߺ^׽uǿu=Wp9Y%Rٍmoz14 騉@X̩F?z׶5'/T}|:%׺u|?}=a].o6.>:$bwYol UI&+(Z&fq%,F>pv۷KE"^)ɐ0UY#b$HK+lbpAf>A0h+-zsjwHnxw6T>goft._jnWIR*i HHdWNa˕I EtH! UX2 ]DBSA?1C߲^oׯ^SoQ_'i|ŝU9mõ';~4{{!GNbhq.AUhRiOuHv.@ʊTDMdvUf3BZhW()_!}|؜ +1le)'y<|R4QUE[EUG,R"nXOqo=B]ee4ee4!"Y]UѪTGMOl{[ߩ׺Ci,vߐ03՛ ӫhzfB{*a4ڙZYo#-Ė\ZUS㈥ ID@RF=$?"j.)_K19m|gLuN&Y)c@/-csg1[6![(ڽ^wޝAhmІRf>hmiLF͏ɜΩs,4r$F[ |2 ݕT捀 wW-^V,)ɽdJ2{|jՎ Hӯh6qN$bvPeQSQȼ$Rmsx@~Y?[ sz :OTX7[Y*_gmYb YCش" ֞lר}:{+v";wV>zV:MˊQn]?7ܦڊʵ1j&'0O iC(3Y6sG|Z\G.k7[|9m#[T@rUwb'[yn]{c%=f$4-f\f8#[pÏ}3+K -cV|B!b3H _bHs+Hlr@Onm#՝w6V6>AŅ<HO:77HUQUHЈ-~ dg= ~:{{^׺uߺ^׽u )GWRdQc᫢QKWKPAQMQxYYIvI!&̤`H*FAdrZ 0*EAU:GIt>-mb>i?.6ۧ7]>G?m_{?y94#{ > j߿\G'׾QyO[W^b>^i?.7^B}3>ڿj0sIAu略hG}cWXO }-G?]3>ڜ+ޏ0 qi?/S}-7K\WRM5Bc08F=**Q:cz`f}\4SsAUq+AӪJ U պu۟oz~]{j %a~pG߆gb`{q&1xeTS1Rc-,ꨧaQ✈yrc;UpN X'c e?MSh5g,̓ψ?_;m[nnoluLy fSY5t ^)HR%żoq pU `r8 Օ]"t3|[}D|sܝqmBɼ7&? 6Bi MT Llmof;gmr$-E1NFYU$c$z>.$hvZx5(?k?>?3_+鎷'o =evLxHD YA# 5I/s.fۮ{^\MJ)~{ߺ^׽uߺ^׽u~{ߺ^׽u~{ߺ^׽u~{ߺ^׽uďya_^Z‡:X]Xl-"`Lc1r@R{uV,ҪU/P]EE 2j ؀ QEcrFLЖ5g,~~wWVyj{i0zxfrDž ܻj[w3C*^s5458p>oo6c\\âJڀIY#yIi/a+'ZP,T?튰??T?%I0wSw]$LG{fjiijN|f,.)'<Ϲ;s'У)KDgI6eS B՗@q륿uVa"\oׯp+MkeHV-G DrGh Aj'~ZhËtxM{zI^*H)pj[6 annm/1 4i3kqE<0ʾ6|RD f(Mx473\ M"P?N}D|rV(:`{sA Jn̮KYv%&{RAY[<%Fލɿ22&z'R-[m> /Gҥ D;dRx#Y`LSsӏoyPsPĊt8o?җe|՝վFItjX= \2.&: !JiO3+}o/F. m ->XG9.fZJ5#@\]]=gMݝxYu(Xj8AI*5Ѡ\oeu{O2Fu]LjI +Ӳ87M83{s_$:tHuîSgr}q J]䶿͉'2m;[Ǣ+QX,Yy2z_+˻b`}VYhⲔW]{7u1BF>:T=-EF7;?oSnC$ 1{haߎ-nזdzJ!c\]޷nM7nii h [?AiVp_K_޴>Lb~[ )tԻ}mN:4r9UG 16 <=ٓw>^0A+)Y _ ӀBŏ7S\Uޯ%kk˹/s-jԳHr_>O-swΑۧ5/b}KpQf{fݏ/）?Rݝ[L59Oɱ ;Y߱k:(@PX8~r׽u~{ߺ^ߺ]\{zZl=?Sv,ϚM=!:g~v>#ﳸͻKxEbIdikʆP"Akm\7Hqab4(M$"*"Mi$bu I$1ԸzO X=ȿ퇭Glc{}G,ў"{d`?9cY7_l'XyQgȿ퇯iGg^?Gm~X=El={M?[:>翺?kr/anћ_ d2>Y|v0|Bm쾾)O`YXF{J4mͲuƫNKc;[ P$;}d8YJfBڊ2znV24dX^qR*hh+М}=i=,{[:Gan^zǮ6n=|o;mmMjihib5y&8;*6v7{Me 1VbpD*"DRBzF`@zpq։͏ y?YaòV'0$z?GYcw)!Մu mM|Mە+YJãkde |c6ȠmCZ!vkgwo=ÿf6ϖ|{sgr.d#TVTYKhT eW[r FƊ0"Q@tFPd$2jOOAgWcKGt!~/aw-qM/YsV^:9?e?KkbhR[`kӵѶJ  ׻H#Ѻ3oLg{G.@&yTLZivȣ5c*i> b 1x#BӢtU]iS7m,zm`հ ѲHnRtn{cCBxwi5^^V>6uyp olyR^"YG+pn'93s3ll]ﻀt)vrBj S~?Vw͌QYw~ce,N4x@wkGP$g5\ʤQm~_–銂 " A4r8:1Ool5,տgE+Чt|y*.7[jh1RSm]$*\E$P̬8<2ġ //@I&>`a#C{{^׺u{ߺM\; frՔV&'Ȱc)䪭Hgv<*ϻ Eoe摂RX$)HUfcE>þOdK=ͽw>ۂv-.3`VVgx][ifMܥ%! t,1O&#1Y؜6 [UxıbH:&g]{^׺u{{:[4&l|y\C]KjH{KޯhgpuK_G}Hqqs0-v- SRy'\<)(,hڨ#Ո_Nۀ9><:Qֺ͋lCfdP>/cae/qv$YURԀ5#>:{uݏSu[M> 1@7\l&:ߦ(lB!>|fs~i~6 u1eoOU]3ܹ +5*6rcXP2iRJP֦}CU<Ԏ#t_ezEZrv^_{:b;k`n`3s w sI(h u-ć;?\K~\WfXuYԴ7O.-tYxCwZ;[A5ߛ'DZ ]u#0ةy>>om6Ϭu"[ɚZ)EHG>~wsֻ%VUe>;YCP.dfZ2uǻQW}p]=emO-ND:{ 3/{]vHd…av7pj4>ApG֯_/I.nP5؞!OTx=i[v%?ձ$x>w>sZ(#QWaIƏ!KCXFv' T}]?{{^׺u{ߺT %eUAޝi;u5Nl~A^3s!`M-o{uVRlEm"FP*Q\ Xh?Qb\~h|p{=u{{^׺u{Ko#׺V ]#U~^omK'duɸ7dcdV3%LB_c;ͮ[mV6"YFI@:bfEv0ɢ6*T!IQdOV$(v`9nE*̓?ƚUWa3$i;{ 9*}^LF`9^lGH+ءvx^O)" Ez!0=bIb{bN;vgplxЕ!z.YY'I&iYfIfF.YGrKI$i;I&I955MGN^׺uQU(WWAEEI& 14G{z&kxHꊣ3(I4oUf؀TzV:<1e,6{w(u:j*#J (_-Uy|gAHlPQAoc8xRP#-ۉ NpIpĒMLl%ۜĎ2+ߦ5,n| =ħ+ݝTcGESSӪ^ NT H Xbpu4vMαhX,6*)ڮ[" $=ݴ[]nvyZImi 7Y!D ZR1 ~=_{CGMؿk/Q(aИT(<8)!Per=w)r7.򽂬V$6AQ`V|15aW/.ɟwyL,~nOz~콵LwI4^a欕C[],5$č* ':<}̑x[tQ<0F%jN0h3#PHH'ׯ_Z=[bh[seE  xSw/J|_ ;&=`=:uõw|ʺ|[yTNJ1$Rvykj:4Q2EAb-i}.ݘͅaolubv?[pRM_^XV"hii !6Qeܿ]Cea;|ײ)bRBc'߽g6vKeVyg(դHBi$$ŅLT_3j`;t/ς;wm]vo?u|^ SK[ru^: u$/,Jqf =>{$.*3U@$@'ճn.qw]ΐ*K40H4*" =&V(ҬpgrOu*=#_szz'%7kvf* ]w}Q&T`5`E0˧{_I^Gnw/B+M+CJ\?r$67ɛ˺DP Ψ\ EC dt쿈_ޚsnzRP䪶kpSchc'eqG4N.cp筋j{=}@%VT`x\so!޹[p$f 4bH:X2+*h|3g%8j䥣ńVuDi20[ݳI!7+Qj?MW\ommw|v>aҺ'C=3zkN`V3\Ef1Idh$Ե5Q4r:: ~XX%捵eF*Z FSADPv>sƒFgpUE FUу)R`̪WimM6쭩܋,1Ktx@K.ΐqv2剴mL,I T⅙=ƕ"4:Eَ?o?o?~|ӶW49BNk7f̜ V+cb4fr6Ƿs#US1bhV|AǷ^϶;mI,Α̠*I'qҋ ^˳;W-\;~;m'"qy|5-jM B\6q獏h6cou@tIP4 z[>{oSxvl5YiCJC=_gE7@_os9Kt!?$<dW?^BO7@_o/jv?׿s 1ggh峾;꾭62#m5Mf,PfSPRUmw--exBx ԥY(Ae55{I7$!n$Xi]$uTr0^,SJEY| Wk("^1mf|~[1]MO(]Otww{ ͤFiVw~X|mKD 5fg+6Mpo/)gk!m>%nL F#Q|Ύ#$ ?:wo{e]aM"avl rd`=0{uh6|dx10I$_FJ<ʻHy/.e Fְ8^ԮꟁV:a<juVԑwMF2aZ:-p[== 3F|;+v iUg02ZG*;4q?z׷_m[oݥZ;!;*`Q+"[׫XK3.-ֆ5w q*bHpE oHJ8}=C׽u~{ߺ^׽uݳyc4|bK iս[^=j$U{Q3䞖x'T=sN'/oe~( h 9Y?iB>|'NI?(5:Y|kUj5#JTWE zHk5U.K3ddSQUW_TLlC;J#$·aU]0(UZ1A''zV֡d+ATP8b:__㑊lu)tjOf ,Eb 3|%g4R?WcO!K}L)S0?l<sw_݅]ԘUT5 %jT]P%-^Qڤ?F a4ndgI{9x68gՁcCVvSN>]r_W/N,i[;Z~`mɐHI )yhU3Յ^cl<o\=Ƈ\o)F٥A*$汹s9ɛLSpf+'}^uMYTM>%NuUDv(-M*RUu+LM3{DdwrZP*ZP*@:Ŷvml56olw5M uf02t=b: aHMՙy%X~$u0v4+릟n)0p@ t<,_+z>.o9۴Rf0/ YZzjmŞVTEE<6#hL8S9xKi}5iW.XQ֤TU k&mql7aV) Xu 2Hd$+!Htf~W_M(B^ٽS7ch/6^4RV&`31P/EyrYWbs! +B Ռ_y}ܽ߶F yܞb$X2xcEmՔK RyԻ?gőCu,ɳ>Ȍ4v^ rI&9m0o1r)D j8҃S95W('%mܩ4\Xp[^^F1^\ĤE19K_0>pt} uN+ae7Xߛ''5Qy**:-LHșiʬ c=9m,*hBS0"ڿlm7%7,+U>Piq@ j@C(c쁿oWg./{ǿ{2}T|fb v.W'yN5 6و\+TrǺܧ܈ni/M#$QZ{zݐbHOZ712|[z6-K%g.f6qgB`qpr8?}u.$Plߢ r @#L h}ar%ƥF˶8ש~(t SLu2Ҡ PS%WfBUO6 vfԦf` Z1:Soi,c^*.5` Z+jN<`g*r)=o' uRM5m:yS(w7X>XQGIb9%|0(~/aяdܡӼ׌Q0GYvΙ(2p~Ž@q*>T=Z&g?__t&ysa0B5Ozl=E,wVo,i-T'V" 6=2[3i5@+"4 ZzcܾM~䍺bl,cXMgR69D"*gvj=Zaw.Wt9U]'?: _ 2RUuU\>?.L*;vggd%D@*@Bd]u?zy>}O&h]#cjkbq*yP0=P)]Cs;[^,;TR#WԱI:ǾJ=Iםuv}L->C#YJ:c%Bzfwgf$?ܹnK;m1 N v!VES1 }]m~ݒstYvd(S,#8Sz6獼NMݻk6뤤)q0UTlħz$;*DYisn2NjEsSGc@=:#dl7Wvѥ[QXx6eu;0u'3?ۖ16L֛or#|~oJ:n $2@h{qg{_K HH KSp1=,ݛt;Uq5dĽ(M*Cc2Uk.9̦;7+Ui&(fks%8cb@ɢ4$`q=t nm,~yc3 f&4$ώ:OWYl$%D) ˕ "R>򳖶ܛϴ @P8kǮA{ß=.pYmo cV '4A֑*?aGڿ7i~ݘ;5Yڸe))4@X[ulsm\oqCt5xh\u4>ٹO$fu1',g4J|[|.Zz# z޵=?lew|rDCy/sx[>i7[xdB8yg= `kX!?[1:gǰJߺ^׽u~{ߺ^ԍ A~x֟n|m-KG!7/h0S}z+GTSt͗0# ,y|6hF*zC4g}Hg&hUc :hptO>@e>_,%Lrl^ەg,LHu56&ُ+뽺QaCI,2|1S@ǻjI0T̖AB뒭x㴵ѻ/@2V2 , +IUV $qĽaoAnRhnnxs-9P0;-k8F][bB*/.}"?MWjͱݡQCZXdbxo'䍬ղڲD.G#U:dhE5{qO|E,qV|lF@+M?HJ3ҟ2~v)tț[1ru P]k{zJ0]wUF+v#~{9b2Ҿx$̋M.3ժhrwd6 P*JdVx*|GTu~Xl9qmKO9K+Y#][i\F=}:hcֱϐ'e|ZʣW{4,1Kf;iUS7~oO Ԭ>|+fG!n+T#O0O$zqQ[`^v,UC,Nghh-~ z7ntALD spۓzS:Mׂm#prJoU4~tOͯhuVuFVhӁP+|slQ?nuv|v͟3lUMS).x<>GqĘHpX,K,Pm^nۖ5))ɼ\v!۶C(;XގK-KX h:N׽u~{ߺ^׽u >rm5Æ/#Y?7<7_[}}mƿ~?]5~VN:?"GuWw~|-?]_mӏZկW[D?P"TC^O/ ~{7!ws5/otZh<_>%iz^vֿ.np?\> 5>?ӫcUJhzՃ3_4J{;o*5Z_co~׃W|፧4Zz鞳VrI<G]i*׭E/6 9ORW ~ޯ?,OU`ĥ|*cOˬ;~{7={_Q5x?Oj>&|_,?@YٖJ?|it_{\hhײ_jy<:x^$>54fW<;no߿_UIƟ 뫧iՍ=uv5yN;ލ_gs_w:z}:};?__W_M4xZ|=R覼(ik5-Z4^=tnZI?~}^< /H @___vW;o/[^W1/W/:uW_+yWr~}OQ-~V 3KE?Ë}|o]qMӮ ~GiZ-8۞qG~/4Lux߿|/ _oϭ/ht?Îuh/}_{o~DG4ݯt>&\֯rvo~IO>G ~=su~{ߺ^׽u~lQ_ Equation.30 Microsoft lQ_ 3.0[lQ_ Equation.30 Microsoft lQ_ 3.0\lQ_ Equation.30 Microsoft lQ_ 3.0_lQ_ Equation.30 Microsoft lQ_ 3.0`lQ_ Equation.30 Microsoft lQ_ 3.0dlQ_ Equation.30 Microsoft lQ_ 3.0elQ_ Equation.30 Microsoft lQ_ 3.0'klQ_ Equation.30 Microsoft lQ_ 3.0(llQ_ Equation.30 Microsoft lQ_ 3.0IwlQ_ Equation.30 Microsoft lQ_ 3.0JxlQ_ Equation.30 Microsoft lQ_ 3.0KylQ_ Equation.30 Microsoft lQ_ 3.0LzlQ_ Equation.30 Microsoft lQ_ 3.0O{lQ_ Equation.30 Microsoft lQ_ 3.0P}lQ_ Equation.30 Microsoft lQ_ 3.0/ 0DDArialSansH}0z[ 0D[SOalSansH}0z[ 0 DBook AntiquaH}0z[ 00DTimes New Roman0z[ 0@DWingdingsRoman0z[ 0PDFranklin Gothic Mediumz[ 0"`DVerdana Gothic Mediumz[ 0"pDGungsuhChethic Mediumz[ 01DNSeeOuhChethic Mediumz[ 0DArial Blackhic Mediumz[ 0"DComic Sans MSc Mediumz[ 0B A .  @n?" dd@  @@``   0KG   D   r !!"#a$%& ) ,  /01234~67>GCDEFGHIL   X[\]^_ ab  hijkl mnop1 tBvwxyz{|}~ 2$^K)V"|b$XڼV&ռ,wx2$9_= *f,2 2$b1;KNnQf $2$~U6U~g2$;ɿ]VR$.(V$7ނ!('W,2$O18 { 2$NG^Rf!]$$$$2$); KpDz*~-/e2$ܱ&SaFu 2$vP xXia "$b$U׷2?`v,j#b$q;@aZ&hN|$2$loof5]Cj&$2$K;15HXI'2$:Źg~.EhWAJ) 0AA ffffff@ۉ8ʚ;ʚ;g4BdBd z[ 0pppp@ <4ddddL 0 } 0___PPT10 ppH___PPT9*"n_4ln,|PNG  IHDR +tsRGB PLTEff3fQ} cmPPJCmp0712cOtRNS@fIDATc`PA-Q-0 yx`YsIENDB`[nQy  a*lD!@PNG  IHDR exsRGBNPLTEkc{絔έֽεƭƥƽ{s cmPPJCmp0712x~tRNS AyIDATMI0{d{1@Gs @c3|bXֻ$镰3дY ;6TJ~UCo@{} P{4$]$gc>/13"+^ZCLKs}XmIENDB`?Z-FDevi Xiong et al. ICT, CAS, BeijingO  =/3QMaximum Entropy Based Phrase Reordering Model for Statistical Machine TranslationBR&,",&,+",Deyi Xiong, Qun Liu and Shouxun Lin Multilingual Interaction Technology & Evaluation Lab Institute of Computing Technology Chinese Academy of Sciences {dyxiong, liuqun, sxlin} at ict dot ac dot cn Homepage: http://mtgroup.ict.ac.cn/~devi/ """" "s".g  *g   y Outline"^Previous work Maximum entropy based phrase reordering System overview Experiments Conclusions  Previous WorkContent-independent reordering models E.g. distance-based or flat reordering models Learn nothing for reordering from real-world bitexts Content-dependent reordering models Lexicalized reordering models [Tillmann, 04; Och et. al. 04; & ] Totally dependent on bilingual phrases With a large number of parameters to estimate Without generalization capabilities&.5%@y&.5%  @&R>E+ %Can We Build Such a Reordering Model?,& $$$Content-dependent but not restricted by phrases Without introduction of too large number of parameters but still powerful With generalization capabilities -Build It Conditioned on Features, not Phrases:.""" "Features can be: Some special words or their classes in phrases Syntactic properties of phrases Surface attributes like distance of swapping Advantages of feature-based reordering: Flexibility Less parameters Generalization capabilities \|(:| : q+Feature-based Reordering"Discriminative Reordering Model proposed by Zens & Ney in NAACL 2006 Workshop on SMT We have become aware of this work when we prepare the talk Very close to our work But still different: Implemented under the IBM constraints Using different feature selection mechanism NUgSUgS ,,V"Outline"^Previous work Maximum entropy based phrase reordering System overview Experiments Conclusions *_()Reordering as Classification$Regard reordering as a problem of classification Two-class problem under the ITG constraints {straight, inverted} Multi-class problem if positions are considered under the IBM constraints Our work focused on the reordering under the ITG constraintsl1Z-ZZJZ=Z1-J =W $MaxEnt-based Reordering Model (MERM)"%  MA reordering framework for BTG MERM under this framework Feature function:--TTraining for MERM"Training procedures: 3 steps Learning reordering examples Generating features ( ) from reordering examples Parameter ( ) estimation using off-the-shelf MaxEnt toolkits :$ . Reordering Example" FeatureseLexical feature: source or target boundary words Collocation feature: combinations of boundary words 2f!! AWhy Do We Use Boundary Words as Features: Information Gain Ratio BB" ]$Outline"fPrevious work Maximum entropy based phrase reordering System overview (Bruin) Experiments Conclusions Bg6" Translation Model%Built upon BTG The whole model is built in the log-linear form The score to apply lexical rules is calculated using features similar to many state-of-the-art systems The score to apply merging rules is divided into two parts The reordering model score The increment of language model score NBABA 1GDifferent Reordering Models Are Embedded in the Whole Translation ModelHH"oThe reordering framework MaxEnt-based reordering model Distance-based reordering model Flat reordering modelP2CKY-style Decoder"Core algorithm Borrowed from CKY parsing algorithm Edge pruning Histogram pruning Thresholding pruning Language model incorporation Record the leftmost & rightmost n words for each edge $ '6$ ' 6"R \g&Outline"^Previous work Maximum entropy based phrase reordering System overview Experiments Conclusions *_F  h%Experiment Design"To test MERM against various reordering models, we carried out experiments on: Bruin with MERM Bruin with monotone search Bruin with distance-based reordering model Bruin with flat reordering model Pharaoh, a distance-based state-of-the-art system (Koehn 2004)4OOj'Systems Settings"3Small Scale Experiments"LNIST MT 05 Training data: FBIS (7.06M + 9.15M) Language model: 3-gram trained on 81M English words (most from UN corpus) using SRILM toolkit Development set: 580 sentences length of at most 50 Chinese characters from NIST MT 02 IWSLT 04 Small data track 20k sentences for training of TM and LM 506 sentences as the development set N  _  _ 8 MERM Training"m(Results on Small Scale Data"AScaling to Large Bitexts" Just used lexical features for MaxEnt reordering model Training data 2.4M sentence pairs (68.1M Chinese words and 73.8M English words) Two 3-gram language models One was trained on the English side The other was trained on the Xinhua portion of the Gigaword corpus with 181.1M words Used simple rules to translate number, time expressions and Chinese person names BLEU score: 0.22 0.29 EZBZZyZiZZZEBy  bfFMResults Comparison" n)Outline"^Previous work Maximum entropy based phrase reordering System overview Experiments Conclusions "_R @ Comparisons "B Conclusions "MaxEnt-based reordering model is Feature-based Content-dependent Capable of generalization Trained discriminatively Easy to be integrated into systems under the IBM constraints :!!p* Future Work "More features Syntactic features Global features of the whole sentences & Other language pairs English-Arabic Chinese-MongolianN<!<! C Thank you!   7Training "Run GIZA++ in both directions Use grow-diag-final refinement rules Maximum phrase length: 7 words on the Chinese side Length ratio: max(|s|, |t|)/min(|s|, |t|) <= 3>'Y  |,&Language Model Incorporation (further)''"The edge spans only part of the source sentence The history of LM is not available the language model score has to be approximated by computing the score for the generated target words alone Combination of two neighbor edges only need to compute the increment of the LM score: v0"40"4 OTree" - Related Definitions" U/The Algorithm of Extracting Reordering ExamplesZFor each sentence pair do Extract bilingual phrases Update the links for the four corners of each extracted phrases For each corner do If it has a STRAIGHT link with phrase a and b Extract the pattern: <a; b> STRAIGHT If it has a INVERT link with phrase a and b Extract the pattern: <a; b> INVERT[.',%[.  , /!#$%'(, / 0 4 56>?GHIJRSX^ab c!i"o#r$s%t&u'v(~)7  ` !3̙` Q.<ffff3` 3333fff` 3K=̙fff` 3fffff` ff3ff3` aNR>ff` 3fY33` 3f3f>?" dd@&f?ldd(@fm<)6=m+7%l', n?" dd@   @@``PT    = 7 ,`(p>>K0 XP@F(    <* #" `T,M  LUSQdkYkHrh7h_     0|- "  8USQdkYkHre,g7h_ ,{N~ ,{ N~ ,{V~ ,{N~  X  C "A logo"7 A s *83 #" `M   ^*C  B 0l7 "    ~ *COLING-ACL 2006C  C 0= "6  `*C d F C .Amitel_logo".gP  s *޽h ?"` 3f3f___PPT10i. "+D=' = @B +___PPT9JpJJ Profile= K0 <4P(    < #" `@  LUSQdkYkHrh7h_    0l "C,3   NUSQdkYkHroRh7h_ X   C "A logo"7d  C .Amitel_logo".gP  s *޽h ?"` 3f3f___PPT10i. "+D=' -v= @B +x 0 (      0   P     P*     0#       Z*    6)  _P    X*    60  _    Z* H   0޽h ? 3380___PPT10.7r 8\DH? !MRoot EntrydO)WPicturesfCurrent User5SummaryInformation(!T`      !"#$%&'()*+,-./0123456789:;<=>?@CDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~