基于句法的統(tǒng)計機器翻譯的翻譯規(guī)則快速匹配方法課件

1、Fast Translation Rule Matching for Syntax-based StatisticalMachine Translation基于句法的統(tǒng)計機器翻譯的翻譯規(guī)則快速匹配方法Hui Zhang, Min Zhang, Haizhou Li, Chew Lim TanIn EMNLP2009駱衛(wèi)華報告2009-6-19動機現(xiàn)有匹配方法規(guī)則集的超樹表示基于超樹的匹配算法實驗結(jié)果總結(jié)動機基于森林的翻譯翻譯規(guī)則匹配基于已抽取規(guī)則的解碼動機問題規(guī)則匹配和解碼非常耗時規(guī)則數(shù)量巨大在265w句對(樹高度3)上生成規(guī)則文件大小30G(不過濾)解碼算法優(yōu)化Beam search wit

2、h pruningCube pruning規(guī)則匹配算法優(yōu)化？動機改進匹配算法提高匹配速度改進規(guī)則表示方法加載更多規(guī)則放寬參數(shù)限制：樹高度現(xiàn)有匹配方法翻譯規(guī)則匹配算法基于樹片段的窮舉搜索基于規(guī)則的窮舉搜索規(guī)則表：( CP ( IP ( VP ) ) ( DEC ) ) the | _ | of | _ 2:2 1:4 2.3854e-05 1e-07 0.000441261 0.0375863 -3.23683e-05 -0.000515897 -5.32183 -13.0477 1.29399( CP ( IP ( VP ) ) ( DEC ) ) to | _ | _1:2 2:3 0.00

3、0588023 1e-07 0.0118465 0.0968351 -0.000650801 -0.0136365 -5.32183 -9.75755 34.7395( CP ( IP ( VP ) ) ( DEC ) ) to | the | _ | _ 1:3 2:4 0.000483222 1e-07 0.00111862 0.0242182 -0.000552588 -0.00124435 -5.32183 -12.1175 3.28033( CP ( IP ( VP ) ) ( DEC 的 ) ) s | _ 1:2 0.0139025 0.270723 0.00245631 0.0

4、0467418 -0.0402974 -0.0024043 -2.32674 -8.33583 143.969( CP ( IP ) ( DEC ) ) s | _ | _ 1:2 2:3 0.000845534 1e-07 0.000491488 0.00467418 -0.000716712 -0.000572699 -3.86862 -11.4867 6.1641( CP ( IP ) ( DEC ) ) , | _ | _ 1:2 2:3 0.00162891e-07 0.00392479 0.0658115 -0.00162 -0.00435942 -3.86862 -9.40906

5、 49.2236現(xiàn)有匹配方法基于樹片段的窮舉搜索輸入：句法樹或森林F，翻譯規(guī)則表R輸出：匹配的翻譯規(guī)則步驟對于F中每一個結(jié)點N枚舉其所有可能以N為根的子樹片段對于每一個子樹片段G將其與rR中的左端相比較，匹配成功，則返回rNPADJPNPJJNN有關(guān)規(guī)定現(xiàn)有匹配方法基于樹片段的窮舉搜索h：句法壓縮森林的一個結(jié)點f(h)：以h為根的可能的樹片段數(shù)目f(h) = 0 如果h為葉結(jié)點 否則現(xiàn)有匹配方法基于規(guī)則的窮舉搜索輸入：句法樹或森林F，翻譯規(guī)則表R輸出：匹配的翻譯規(guī)則步驟把rR的左端按照自頂向下，從左到右的次序分解為超邊序列H按次序取出H中的每個超邊h：按照自頂向下，從左到右的次序與F進行匹配匹

6、配成功，則返回rIP = NP VP; NP = NP NP; NP = NN;NN = 聲明現(xiàn)有匹配方法基于規(guī)則的窮舉搜索對于F中的每個結(jié)點需匹配所有規(guī)則R通常規(guī)模巨大實際速度比基于樹片段的搜索更慢規(guī)則集的超樹表示基本思想超樹匹配句法壓縮森林和翻譯規(guī)則集均表示為超樹超樹的每個頂點只訪問一次規(guī)則集的超樹表示公共部分規(guī)則集的超樹表示IPNPVPNPNPNNNN新華社聲明規(guī)則集的超樹表示規(guī)則集的超樹表示超樹(Hyper-tree)超頂點(Hyper-node)超頂點(Hyper-node)超頂點(Hyper-node)超頂點(Hyper-node)超路徑(Hyper-path)TOP規(guī)則集的超樹表

7、示超結(jié)點的精簡表示如果超結(jié)點沒有與之相連的規(guī)則，則從根結(jié)點到該超結(jié)點的超路徑不存在對應的翻譯規(guī)則超圖匹配算法IPNPVPADJPNPNNVPNPVVNN句法森林規(guī)則表TOPIPNP VP NPVP NPNP VPVV, NNADJ NP,VV, , NP,VP超圖匹配算法(1)TOPIPVPIPIPSFP:IP超圖匹配算法(2)TOPIPNP VP NPIPNPVPVPNPTFNS:RFNS:RFP:超圖匹配算法(3)TOPIPIPNPVPVPNPVP NPTFNS:VP NPRFNS:VP NPRFP:VP NP(VP NP)超圖匹配算法(4)TOPIPIPNPVPVPNPTFNS:NP V

8、PNP VPVP NPRFNS:VP NPRFP:VP NP(VP NP)NP VP(NP VP)超圖匹配算法(5)VP NP(VP NP)NP VP(NP VP)SFP:RFP:VP NP(VP NP)NP VP(NP VP)超圖匹配算法(6)IPVPNPVVNNTOPIPVP NPVV, TFNS:VVRFNS:VV超圖匹配算法(7)IPVPNPVVNNTOPIPVP NPVV, TFNS:NPRFNS:VVNP(VV NP)RFP:VV, (VV NP)超圖匹配算法(8)IPVPNPVVNNTOPIPVP NPVV, TFNS:VVRFNS:VVVV, NN超圖匹配算法(9)IPVPNP

9、VVNNTOPIPVP NPVV, TFNS:NNRFNS:VVVV, NNNN(VV NN)RFP:VV, (VV NP)VV,NN(VV NN)超圖匹配算法(10)VP NP(VP NP)NP VP(NP VP)SFP:RFP:VP NP(VP NP)NP VP(NP VP)NP VP(NP VP)超圖匹配算法時間復雜度N:每個超結(jié)點的最大孩子數(shù)M:超結(jié)點的最大結(jié)點序列數(shù)K:句法壓縮森林中每個結(jié)點的最大超邊數(shù)C:句法壓縮森林中具有相同孩子表示的超邊數(shù)R:每個結(jié)點匹配的樹片段的最大數(shù)目時間復雜度：實驗結(jié)果句法分析器: Charniak parser句法訓練集：CTB5句法規(guī)則訓練集：FBIS(250k句對）詞對齊：Giza+語言模型：Gigaword 3新華部分4元(KN)開發(fā)集：NIST2002測試集：NIST2003調(diào)參工具：Koe